Zoaron : другие произведения.

Bash: Random access machine

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
 Ваша оценка: 



                           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 Guide
Wikipedia: Brainfuck
Хабрахабр: Интерпретатор Brainfuck на Bash
Хабрахабр: Эмулятор РАМ-машины


Zoaron
2011 dec.


























 
 Ваша оценка: 














Связаться с программистом сайта.







Новые книги авторов СИ, вышедшие из печати:



О.Болдырева "Крадуш. Чужие души"
М.Николаев "Вторжение на Землю"


Как попасть в этoт список







Сайт - "Художники" .. || .. Доска об'явлений "Книги"