Создание кратчайшего полного по Тьюрингу интерпретатора [закрыто]

Программа 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 , сохраняя драгоценные байты :)

Python, 250 байт.

Это решение длиннее, чем решение Илья Н. на 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"]

Удачное кодирование: -)

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

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)]

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

поэтому i () ожидает допустимый код Капутта . Тестовые примеры:

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"]

Удачное кодирование: -)

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

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)]

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

поэтому i () ожидает допустимый код Капутта . Тестовые примеры:

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"]

Удачное кодирование: -)

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

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)]

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

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

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)]

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

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

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)]

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

Соберите приведенный ниже код, используя 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 источник.

#include "/dev/tty"

Не мой, но взгляните на 210 бит самоинтерпретатор двоичного лямбда-исчисления здесь . . 1119288]

Основываясь на моей предыдущей записи кода-golf , вот (немного обобщенный для ввода-вывода) 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

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

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

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

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

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

Интерпретатор (написано в SLA): iq

3 символа!

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

perl -ne'push@a,split;if(eof){$i=0;while($i>=0){($a,$b,$c)=@a[$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;
    }
  }
}

Вышеупомянутый интерпретатор псевдо -машинный код для компьютера с одним набором команд с использованием инструкции subleq . По сути, исходный код должен быть просто набором чисел, разделенных пробелами. Простая тестовая программа для проверки моих результатов (должна печатать «Hi» и новую строку 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

106-байтовое решение был размещен на конкурсе codegolf.com . Он написан на perl и интерпретирует Brainfuck . Сейчас нет возможности просмотреть его, afaik.

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

Моя собственная запись, реализация 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 - указатель памяти. Основной цикл - это вспомогательная операция, записанная с помощью тернарного оператора. Последняя строка - это умный способ вывести число, содержащееся в памяти.

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

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