Random access machineВведение
Random access machine (RAM) - абстрактная машина относящаяся к классу
регистровых машин, эквивалентна универсальной машине Тьюринга. Модель RAM
включает бесконечное* число регистров в которых могут храниться любые**
целые числа, как положительные так и отрицательные. Обращение к регистрам
осуществляется по их индексам - индексы могут быть любыми целыми числами,
положительными или отрицательными. Регистр с индексом 0 является "особым":
он связан с потоками ввода/вывода и участвует во всех операциях машины,
т. е. во всех командах регистр [0] является "скрытым" аргументом.
_______________________________________________________
* разумеется, только в теории
** аналогично
Система командУправление программой
Halt - останов
Вввод/вывод
read - получить со стандартного ввода число и записать в регистр [0]
write - отправить число из регистра [0] на стандартный вывод
readc - получить со стандартного ввода символ и записать его код в
регистр [0]
writec - отправить число из регистра [0] на стандартный вывод в качестве
кода символа
Работа с регистрами
store [x]/[[x]] - загрузить значение регистра [0] в регистр [x] или
регистр на который указывает регистр [x]
load x/[x]/[[x]] - загрузить в регистр [0] непосредственное значение,
значение регистра [x] или значение регистра на который
указывает регистр [x]
add x/[x]/[[x]] - прибавить к значению регистра [0] непосредственное
значение, значение регистра [x] или значение регистра
на который указывает регистр [x], результат записать в
регистр [0]
Пример работы с регистрами
load 1
store [2]
load 777
store [[2]]
add [[2]]
store [[2]]
load [1]
write
результат:
1554
neg - изменить знак числа в регистре [0]
lshift/rshift x/[x]/[[x]] - побитовый сдвиг значения в регистре [0]
влево/вправо на указанное непосредственное
значение, значение регистра [x] или значение
регистра на который указывает регистр [x]
Организация циклов*
while/done - до тех пор пока в регистре [0] число больше нуля - уменьшать
его на единицу и переходить к следующей команде, иначе -
перейти на команду следующую за командой done (с учётом
возможной вложенности)
Пример использования цикла
load 3
while
store [1]
add 120
writec
load [1]
done
результат:
xyz
_______________________________________________________
* в оригинальных описаниях для организации ветвлений и циклов предлагается
использовать метки и условные/безусловные не имеющие прямого отображения
в bash
Собственно эмулятор
8<-----------------------------------------------------------------------------
#!/bin/bash
if [ -z "$1" ]
then
echo -e "Random access machine v 1.0\nUsage: `basename $0` filename"
exit
fi
if [ ! -e "$1" ]
then
echo "$1: no such file"
exit
fi
if [ ! -f "$1" ]
then
echo "$1: not a file"
exit
fi
C=""
while :
do
read l; b=$?
c=$(echo "${l%% *}")
a=$(echo "${l##* }")
case $c in
[Aa][Dd][Dd] ) d=$(echo ${a##*[}); d=$(echo ${d%%]*})
case $a in
\[\[[-0-9]*\]\] ) if ((d>0))
then C="$C
((t=r[$d]));
if ((t>0));
then ((x+=r[t]));
elif ((t<0));
then ((x+=l[\$(echo \${t:1})]));
fi;"
elif ((d<0))
then C="$C
((t=l[$(echo ${d:1})]));
if ((t>0));
then ((x+=r[t]));
elif ((t<0));
then ((x+=l[\$(echo \${t:1})]));
fi;"
fi ;;
\[[-0-9]*\] ) if ((d>0))
then C="$C
((x+=r[$d]));"
elif ((d<0))
then C="$C
((x+=l[$(echo ${d:1})]));"
fi ;;
[-0-9]* ) C="$C ((x+=$d));" ;;
*)
esac ;;
[Dd][Oo][Nn][Ee] ) C="$C done;" ;;
[Hh][Aa][Ll][Tt] ) C="$C exit;" ;;
[Ll][Oo][Aa][Dd] ) d=$(echo ${a##*[}); d=$(echo ${d%%]*})
case $a in
\[\[[-0-9]*\]\] ) if ((d>0))
then C="$C
((t=r[$d]));
if ((t>0));
then ((x=r[t]));
elif ((t<0));
then ((x=l[\$(echo \${t:1})]));
fi;"
elif ((d<0))
then C="$C
((t=l[$(echo ${d:1})]));
if ((t>0));
then ((x=r[t]));
elif ((t<0));
then ((x=l[\$(echo \${t:1})]));
fi;"
fi ;;
\[[-0-9]*\] ) if ((d>0))
then C="$C ((x=r[$d]));"
elif ((d<0))
then C="$C ((x=l[$(echo ${d:1})]));"
fi ;;
[-0-9]* ) C="$C x=$d;" ;;
*)
esac ;;
[Ll][Ss][Hh][Ii][Ff][Tt] ) d=$(echo ${a##*[}); d=$(echo ${d%%]*})
case $a in
\[\[[-0-9]*\]\] ) if ((d>0))
then C="$C
((t=r[$d]));
if ((t>0));
then ((x<<=r[t]));
elif ((t<0));
then ((x<<=l[\$(echo \${t:1})]));
fi;"
elif ((d<0))
then C="$C
((t=l[$(echo ${d:1})]));
if ((t>0));
then ((x<<=r[t]));
elif ((t<0));
then ((x<<=l[\$(echo \${t:1})]));
fi;"
fi ;;
\[[-0-9]*\] ) if ((d>0))
then C="$C
((x<<=r[$d]));"
elif ((d<0))
then C="$C
((x<<=l[$(echo ${d:1})]));"
fi ;;
[-0-9]* ) C="$C ((x<<=$d));" ;;
*)
esac ;;
[Nn][Ee][Gg] ) C="$C ((x-=x<<1));" ;;
[Rr][Ee][Aa][Dd] ) C="$C read x;" ;;
[Rr][Ee][Aa][Dd][Cc] ) C="$C read -n1 t; x=\`printf '%d' \"'\$t\"\`;" ;;
[Rr][Ss][Hh][Ii][Ff][Tt] ) d=$(echo ${a##*[}); d=$(echo ${d%%]*})
case $a in
\[\[[-0-9]*\]\] ) if ((d>0))
then C="$C
((t=r[$d]));
if ((t>0));
then ((x>>=r[t]));
elif ((t<0));
then ((x>>=l[\$(echo \${t:1})]));
fi;"
elif ((d<0))
then C="$C
((t=l[$(echo ${d:1})]));
if ((t>0));
then ((x>>=r[t]));
elif ((t<0));
then ((x>>=l[\$(echo \${t:1})]));
fi;"
fi ;;
\[[-0-9]*\] ) if ((d>0))
then C="$C
((x>>=r[$d]));"
elif ((d<0))
then C="$C
((x>>=l[$(echo ${d:1})]));"
fi ;;
[-0-9]* ) C="$C ((x>>=$d));" ;;
*)
esac ;;
[Ss][Tt][Oo][Rr][Ee] ) d=$(echo ${a##*[}); d=$(echo ${d%%]*})
case $a in
\[\[[-0-9]*\]\] ) if ((d>0))
then C="$C
((t=r[$d]));
if ((t>0));
then ((r[t]=x));
elif ((t<0));
then ((l[\$(echo \${t:1})]=x));
fi;"
elif ((d<0))
then C="$C
((t=l[$(echo ${d:1})]));
if ((t>0));
then ((r[t]=x));
elif ((t<0));
then ((l[\$(echo \${t:1})]=x));
fi;"
fi ;;
\[[-0-9]*\] ) if ((d>0))
then C="$C
((r[$d]=x));"
elif ((d<0))
then C="$C
((l[$(echo ${d:1})]=x));"
fi ;;
* ) ;;
esac ;;
[Ww][Hh][Ii][Ll][Ee] ) C="$C while !((x-1<0)); do ((x--));" ;;
[Ww][Rr][Ii][Tt][Ee] ) C="$C echo \$x;" ;;
[Ww][Rr][Ii][Tt][Ee][Cc] ) C="$C t=\$x; ((t&=0xff)); o=;
while ((t));
do o=\"\$((t&7))\$o\"; ((t>>=3));
done;
printf \"\\0\$o\";" ;;
* ) ;;
esac
printf .
[ $b -eq 1 ] && break
done<"$1"
printf '\n'
eval "$C"
8<-----------------------------------------------------------------------------
Примеры программ
Абсолютное значение введённого числа
READ
STORE [1]
NEG
WHILE
LOAD [1]
NEG
STORE [1]
LOAD 0
DONE
LOAD [1]
WRITE
"Hello World!"
LOAD 478560413000
STORE [1]
LOAD 5
STORE [-1]
WHILE
LOAD [1]
WRITEC
RSHIFT 8
STORE [1]
DONE
LOAD 32
WRITEC
LOAD 431316168535
STORE [1]
LOAD [-1]
WHILE
LOAD [1]
WRITEC
RSHIFT 8
STORE [1]
DONE
LOAD 33
WRITEC
Умножение
READ
STORE [1]
STORE [-1]
READ
STORE [2]
STORE [-2]
NEG
WHILE
LOAD [-1]
NEG
STORE [1]
LOAD 0
DONE
LOAD [-1]
NEG
WHILE
LOAD [-2]
NEG
STORE [2]
LOAD 0
DONE
LOAD [2]
STORE [-1]
NEG
WHILE
LOAD [-1]
NEG
STORE [-1]
LOAD 0
DONE
LOAD [-1]
STORE [-2]
LOAD 0
STORE [-1]
LOAD [-2]
WHILE
STORE [-2]
LOAD [-1]
ADD [1]
STORE [-1]
LOAD [-2]
DONE
LOAD [-1]
WRITE
Числа Фибоначчи
LOAD 1
STORE [1]
STORE [2]
LOAD 14
WHILE
STORE [-1]
LOAD [1]
ADD [2]
WRITE
STORE [3]
LOAD [2]
STORE [1]
LOAD [3]
STORE [2]
LOAD [-1]
DONE
_______________________________________________________
Использованы материалы:Wikipedia: Random access machine (англ.)
Wilisandbox: Random access machine (рус.)
Advanced Bash-Scripting GuideWikipedia: BrainfuckХабрахабр: Интерпретатор Brainfuck на BashХабрахабр: Эмулятор РАМ-машины
Zoaron
2011 dec.