Создание кратчайшего интерпретатора Turing

Ответ 1

Python, 250 байт.

Это длиннее ilya n. Python, но язык немного легче понять. Каждая команда на этом языке (я называю это Kaputt, немецкое слово "сломан" ) - это один байт. Определены следующие 6 команд:

• 0: нажмите нуль в стек
• 1: нажмите один на стек
• I: (if) Вывести значение из стека (которое должно быть нулевым или одно). Запустите следующий блок кода (до "I" ), если он один; пропустите блок, если он равен нулю.
• I: (endif) Заканчивает блок if и нажимает один, если блок не был запущен (потому что "I" выскочил ноль). Ниже приведено объяснение последнего.
• D: (def) Выводит имя указанной функции из стека (см. ниже) и связывает следующий блок (до "D" ) с этим именем.
• D: (enddef) Завершает определение функции.
• Любой другой байт: проверьте, есть ли функция (однобайтная, но см. ниже). Если это так, запустите эту функцию; если нет, нажмите этот байт в стек для немедленного использования D.

Вложенные ifs являются законными; Вложенные определения функций не являются. Тот факт, что I (endif) толкает один, если и только если соответствующий if-блок не был запущен, допускает следующую идиому, похожую на структуру if/else/endif:

# [code that left a one or zero on the stack]
I    # abbreviated "(" below
# [code to be run if it was a one]
0iI  # abbreviated "/" below
# [code to be run if it was a zero]
1iIi # abbreviated ")" below
# [continuing...]

Обратите внимание, что комментарии, строки, пробелы и т.д. на самом деле не разрешены.

Вот несколько примеров общих функций. Они используют приведенные выше аббревиатуры ( / ).

<D(/)d

определяет функцию < (pop), которая выдает значение из стека, не используя его ни для чего.

&D((1/0)/<0)d

определяет функцию & (и), которая выталкивает два значения стека и нажимает один, если оба значения равны единице, в противном случае толкает ноль.

~D((11/10)/(01/00))d

определяет функцию ~ (swap), которая меняет верхние два значения в стеке.

RD(R/<)d

определяет функцию R (remove), которая рекурсивно удаляет все из вершины стека, а затем удаляет еще два значения (верхний из которых должен быть равен нулю).

Следующая функция интерпретатора ожидает программу p, которая представляет собой строку (или любую другую итерабельность байтов) и входной стек S, который является (возможно, пустым) списком байтов. После запуска интерпретатора этот список содержит выходной стек.

def i(p,S,F=0):
 A=S.append
 F=F or{}
 C=0
 k=[]
 for c in p:
  h=0in k
  if c=="d":C=0
  elif C!=0:C+=[c]
  elif c=="I":k+=[int(h or S.pop())]
  elif c=="i":k.pop()or A("1")
  elif 1-h:
   if c=="D":C=F[S.pop()]=[]
   else:i(F.get(c)or A(c)or"",S,F)

Очевидно, что не было места для проверки ошибок, поэтому i() ожидает законный код Kaputt. Тестовые примеры:

script = "<D(/)d"                 # < = pop
script += "&D((1/0)/<0)d"         # & = and
script += "~D((11/10)/(01/00))d"  # ~ = swap
script += "RD(R/<)d"              # R = remove
script += "|D(<1/(1/0))d"         # | = or
script=script.replace("(","I")   
script=script.replace("/","0iI")
script=script.replace(")","1iIi") # ( and / and ) are no real commands of the language.

S=[]
i(script+"1111010111111111R",S)
assert S == ["1","1","1","1","0"]

S=[]
i(script+"00&",S)
assert S == ["0"]

S=[]
i(script+"01~",S)
assert S == ["1","0"]

S=[]
i(script+"00|",S)
assert S == ["0"]

S=[]
i(script+"01|",S)
assert S == ["1"]

Счастливое кодирование: -)

Изменить: В интерпретаторе нет ничего, что заставляет токены быть только одним байтом. Требование этого было больше для согласованности со встроенными командами (которые являются однобайтными, потому что это делает интерпретатор короче). Если вы передадите список строк вместо строки, вы можете написать более читаемый код Kaputt следующим образом:

script = """
inc D
    (
        (
            0 0
        /
            1 0
        )
    /
        1
    )
d
""".replace("(","I").replace("/","0 i I").replace(")","1 i I i").split()

Это определяет функцию inc, которая увеличивает двубитное число поверх стека (младший бит).

Тест:

for n in xrange(4):
    S=[]
    i(script + [str((n & 2)/2), str(n & 1), "inc"], S)
    assert S == [str(((n+1) & 2)/2), str((n+1) & 1)]

Позволить многобайтовым именам функций расширение языка: -)

Ответ 2

Программа Python, которая интерпретирует только что созданный язык:

from random import randint
z = [randint(0,1), None]  # example: input data is 0 or 1
x = '_b_ed_a_i____d_ai'   # this program will set p = data[1] = not data[0]

# input x[i], data z[k]
# jumper j
# p is +1 or -1 each step
# commands:
#    a   set data = 0 or 1
#    b   j += 0 or +-9 depending on data
#    d   move data left or right
#    e   perform jump left or right
#    j   set jumper to 0
#    i   end program
# output: p or some data[x], both possible

g = globals()
p = i = 1
a = b = d = j = e = k = 0
while i:
    h = x[i]
    g[h] = p = -p
    i += 1 + j*e
    if a: z[k] = i % 2
    if z[k]: j += 9*b
    k += d
    g[h] = 0        
#    print(a, b, d, e, i, j, k, h, z)

print('Input:', z, 'Output:', p > 0)

Оптимизированная версия:

g=globals()
p=i=1
a=b=d=j=e=k=0
while i:
 h=x[i]
 g[h]=p=-p
 i+=1+j*e
 if a:z[k]=i%2
 if z[k]:j+=9*b
 k+=d
 g[h]=0

114 байт

Обновление: Я хочу добавить, что точкой моей программы является не создание какого-либо практического языка, и даже не для того, чтобы каким-то образом иметь "лучший" (== "короткий" ) переводчик, но чтобы продемонстрировать интересные программные трюки. Например, я полагаюсь на прямой доступ к глобальным переменным через globals(), поэтому я даже не тестирую команду j, сохраняя драгоценные байты:)

Ответ 3

#include "/dev/tty"

Ответ 4

Соберите код ниже, используя A86, чтобы получить 150-байтовый интерпретатор BF!

    add dh,10h
    push dx
    add dh,10h
    push dx
    mov bl,80h
    lea dx,[bx+2]
    add bl,byte ptr [bx]
    mov byte ptr [bx+1],al
    mov ah,3dh
    int 21h
    pop ds,es
    jc l14
    mov bx,ax
    mov ah,3fh  
    mov cx,di
    xor dx,dx
    int 21h
    jc l14
    mov bx,ax
    xor ax,ax
    rep stosw
    xor di,di
    xor si,si
    inc ch
l1:
    cmp si,bx
    jae l14
    lodsb
    mov bp,8
    push l1
l2: 
    dec bp
    js ret
    cmp al,[bp+l15]
    jne l2
l3:
    mov cl,[bp+8+l15]
    jmp cx
l4:
    inc di  
    ret
l5:
    dec di
    ret
l6:
    es inc byte ptr [di]
    ret
l7:
    es dec byte ptr [di]
    ret
l8:
    mov ah,2
    es mov dl,[di]
    int 21h
    ret
l9:
    mov ah,8
    int 21h
    es mov [di],al
    ret
l10:
    es cmp byte ptr [di],dh
    jne ret
l11:    
    cmp si,bx
    jae l14
    lodsb
    cmp al,']'
    jne l11
    ret
l12:
    es cmp byte ptr [di],dh
    je ret
l13:    
    dec si
    jz l14
    cmp byte ptr [si-1],'['
    jne l13
l14:
    ret
l15:
    db '>'
    db '<'
    db '+'
    db '-'
    db '.'
    db ','
    db '['
    db ']'
    db offset l4-100h
    db offset l5-100h
    db offset l6-100h
    db offset l7-100h
    db offset l8-100h
    db offset l9-100h
    db offset l10-100h
    db offset l12-100h

Укажите имя файла в командной строке, не требуя двойных кавычек, в качестве источника BF.

Ответ 5

Не мой, но посмотрите на 210-сильный бинарный лямбда-исчисление-самоучитель здесь.

Ответ 6

Написано в Perl, длиной 140 символов, включая вызов оболочки и флаги:

perl -ne'[email protected],split;if(eof){$i=0;while($i>=0){($a,$b,$c)[email protected][$i..$i+2];$b>-1?$a[$b]-=$a[$a]:print chr$a[$a];$i=$b>-1&&$a[$b]<=0?$c:$i+3;}}'

Считываемая версия:

#!/usr/bin/perl -n
push @prog, split /\s+/, $_;
if(eof) {
  $i = 0;
  while($i >= 0) {
    ($a, $b, $c) = @prog[$i .. $i + 2];
    if($b > -1) {
      $prog[$b] -= $prog[$a];
    } else {
      print chr $prog[$a];
    }
    if($b > -1 and $prog[$b] <= 0) {
      $i = $c;
    } else {
      $i + 3;
    }
  }
}

Вышеприведенный интерпретатор для псевдо-машинного кода для One Instruction Set Computer с помощью команды subleq. В принципе, исходный код должен быть просто связкой чисел, разделенных пробелами. Простая тестовая программа для проверки моих результатов (должна печатать "Привет" и новая строка Unix):

0 0 6 72 105 10 3 -1 9 4 -1 12 5 -1 15 0 0 -1

Считываемая версия тестового ввода (работает так же хорошо):

0    0     6
72   105   10
3   -1     9
4   -1     12
5   -1     15
0    0    -1

Ответ 7

Моя собственная запись, реализация OISC в Ruby. Это 85 байтов в длину, и я уверен, что можно было бы сжать еще несколько с некоторыми аккуратными трюками. Программы должны содержать данные в коде (строка номеров, разделенных пробелами). На данный момент я не могу предоставить рабочую программу, написанную в OISC, но я сделаю это позже.

p,m=0,gets.chomp.split.map(:to_i)
while p>0
p=(m[m[b]]-=m[m[a]])>0?p+3:c
end
$><<m[0]

Код довольно прост. m - это "память", содержащая программу и данные. Первая строка инициализирует m с предоставленным кодом и p - указатель памяти. Основной цикл - это операция subleq, написанная тройным оператором. Последняя строка - это умный способ вывода числа, содержащегося в памяти.

Ответ 8

Основываясь на мой предыдущий заголовок кода-гольфа, вот (слегка обобщенный для IO) OISC в

Fortran77

Отмечается и без загрузочного леса (655 символов):

  subroutine o(n,m)
  integer m(n)              
  l=1;                      
  do while (l.ne.0)
     i=m(l)
     j=m(l+1)
     k=m(l+2)
     mi=mg(n,m,i)
     mj=mg(n,m,j)
     if(j.eq.(n+2)) then
        write(6,*)mj-mi
     else
        m(l+1)=mj-mi
     endif
     if (m(l+1).lt.0) then
        l=mg(n,m,k)
     else
        l=l+3
     endif
  end do
  return
  end
  function mg(n,m,i)
  integer m(n)
  if (i.eq.n+2) then
     read(5,*)mg
  elseif (i.eq.n+1) then
     mg=0
  else
     mg=m(i)
  endif
  return
  end

с комментариями, загрузкой эшафот и т.д. (2435 символов):

      program c
      parameter (n=1024)        ! The size to use for memeory
      integer m(n)              ! represent the memory
c     Load a program into memory
      i=1
 1    read(5,*,end=2)l
c     write (6,*) "Load ",l," into location ",i
      m(i)=l
      i=i+1
      goto 1
c     Run the computer
 2    call o(n,m)
      stop
      end

      subroutine o(n,m)
c     Simulate a simple computer that supports only a single
c     instruction. Memory is a fixed size array of integers.
c
c     The supported instruction is subtract-branch-negative which we
c     give the assembly syntax
c
c     sbn i j k
c
c     and acts by subtracting the value in memeory location i from that
c     in location j and storing the result in j. If the result is
c     negative, the PC is set to k. Because there is only one opcode, it
c     is not represented, so a program consists simply of a series of
c     triplet (i,j,k), and the PC is generally incremented by 3. The
c     program counter starts at 1
c
c     Povisions for IO and halting are by way of special memory
c     location:
c
c     * PC=0 means halt
c     * writes (opcode argument j) to memory location n+1 send
c       output, reads from n+1 evaluate as 0
c     * reads (opcode argument i, j, k) from memory location n+2 fetch
c       input, writes to n+2 are forbidden
c     * All others reads and writes outside of memeory are forbidden

c     n                         ! the size of the computers memory 
      integer m(n)              ! an array representing the computers memory
      l=1;                      ! program counter
      do while (l.ne.0)
         i=m(l)
         j=m(l+1)
         k=m(l+2)
c        write (6,*) "Executing from PC=",l,": (",i,", ",j,", ", k,")"
c        handle the write special case for output
         mi=mg(n,m,i)
         mj=mg(n,m,j)
         if(j.eq.(n+1)) then
            write(6,*)mj-mi
         else
c           write (6,*) "Setting location ",j," to ",mj-mi
            m(l+1)=mj-mi
         endif
         if (m(l+1).lt.0) then
            l=mg(n,m,k)
         else
            l=l+3
         endif
      end do
      return
      end

c     Handle the various read special cases
      function mg(n,m,i)
      integer m(n)
      if (i.eq.n+2) then
         read(5,*)mg
      elseif (i.eq.n+1) then
         mg=0
      else
         mg=m(i)
      endif
c     write (6,*) "Read ",mg," from location ",i
      return
      end

Пример программы:

13
1025
0

14 
1025
0

14
15
0

0
0
0

-1
1
0

приводит к выводу:

$ cat trivial.oisc | ./a.out 
           1
          -1

который как и ожидалось.

Это действительно простой код. Дело здесь не в том, насколько сильно я могу его кодировать, но насколько простой язык вам нужен для полноты Тьюринга.

Ответ 9

106-байтное решение было отправлено в codegolf.com конкурс. Он написан на perl и интерпретирует Brainfuck. На данный момент нет возможности просмотреть его. Afaik.

Это не мое решение, но я считаю, что оно короче текущих записей. Возможное решение должно быть короче, так как нет необходимости использовать Brainfuck в качестве языка Turing.

Ответ 10

URM интерпретатор CoffeeScript, 143 байта (167 с новыми строками).

Эта версия URM состоит из неограниченного количества регистров, с нулевыми, преемниками и операторами перехода. Хорошо известно, что это завершение.

Программа URM записывается в массив c (команды), а входы находятся в массиве r (регистры). После вычисления выход находится в r[0], и это значение отображается.

Интерпретатор с примерной программой и входом, который вычисляет 32 + 13 (и действительно выдает 45):

# Addition program, similar to http://planetmath.org/examplesofunlimitedregistermachines
c = [['j', 1, 2, 4], ['s', 0], ['s', 2], ['j', 1, 1, 0]]

# Input: 32, 13, thus the desired output is: 45
r = [32, 13]

k = 0
while k < c.length
    t = c[k]
    k += 1
    if t[0] == 'z'
        r[t[1]] = 0
    if t[0] == 's'
        if !r[t[1]]?
            r[t[1]] = 0
        r[t[1]] += 1
    if t[0] == 'j' && r[t[1]] == r[t[2]]
        k = t[3]
alert r[0]

Минимальная версия:

k=0
while k<c.length
 t=c[k]
 k+=1
 if t[0]=='z'
  r[t[1]]=0
 if t[0]=='s'
  if !r[t[1]]?
   r[t[1]]=0
  r[t[1]]+=1
 if t[0]=='j'&&r[t[1]]==r[t[2]]
  k=t[3]
alert r[0]

Что мне действительно нравится в этом коде, это очень просто и понятно.

Ответ 11

Пользовательский язык: SLA
Ключевые слова:
i - Интерпретировать SLB q - Выход

Пользовательский язык: SLB
Ключевые слова:
cp ( "текст" ) - интерпретировать текст как программу C

Пример:
cp ( "# include\nint main() {puts (\" Привет! \n\ "); return 0}" )

Переводчик (написано в SLA): i q

3 символа!