Интерпретатор

25

Основываясь на комментарии Джорджа Эдисона к этому вопросу , напишите наименьший интерпретирующий себя переводчик.

  • Вы можете использовать язык по вашему выбору.
  • Пустые языки не учитываются. Ваша программа должна быть длиной не менее двух символов.
  • Программе не нужно интерпретировать весь язык, только полное по Тьюрингу подмножество языковых возможностей (которое содержит интерпретатор).
  • Куайны не в счет.
  • Не используйте встроенную evalфункцию вашего языка или ее эквивалент. То же самое applyи т. Д.
Хоа Лонг Там
источник
1
(Хм .. я должен кое-что сделать /usr/bin/cat) как насчет полноты по Тьюрингу?
Мин-Тан
@ SHiNKiROU: Спасибо, я не думал об этом как о тесте. Обновлено.
Hoa Long Tam
Связанный: Язык с наименьшим интерпретатором, написанным сам по себе при переполнении стека, хотя есть несколько (только один?) Ответов, которые действительно соблюдают приведенные здесь правила.
dmckee
1
Нужно ли переписывать этот синтаксический анализатор Scheme или мы можем считать, что с языком хоста все в порядке?
JB
@JB: Утилиты для обработки строк языка в порядке, включая sexpпарсер.
Hoa Long Tam

Ответы:

19

КИ - 260

,(1p0(2d())(41(2d())('#((1p0()(10()(1d,1p$)=)<)$2d,1p$)(40(1d,1c$^)(''(1d,^)('0
'9('0-(,'0'9('0-2p10*+1p$)(!1d)~)$^)(0($)'$(^)'^(&)'&(c)'c(p)'p(d)'d(=)'=(<)'<(
>)'>(~)'~(.)'.(,)',(!)'!(+)'+(-)'-(*)'*(/)'/(%)'%()38p(1p3p0(3d)((2)(3)=p1d1p$)
=)$)~)=)=,2p$&)=)=)<)$$

320 → 260: нажмите простые сопоставления символов и команд, затем сложите их. Это вдвое уменьшает размер кода для каждого случая (есть 18 случаев), но для свертывания требуется 30 символов.

Это еще один из моих построенных языков (базовый переводчик, размещенный на Gist ). Он уникален тем, что язык распознает фрагменты кода. То есть строки инструкций в этом языке на основе стека используются с тем же эффектом, что и структуры данных или замыкания в других языках:

1^      # Push a 1, and "lift" it to be a code literal.
(5 +)   # Define a code literal.
&       # Join the two code literals, forming (1 5 +)
$       # Execute the code literal.

Интерпретатор создает фрагмент кода всей программы перед ее запуском, поэтому его также можно считать компилятором. Из-за этого наложение интерпретатора не приводит к экспоненциальным накладным расходам во время выполнения.

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


Справочник по языку:

Получить переводчика здесь

Блоки

  • ( ... )

    Создайте «блок», который фактически представляет собой список инструкций без контекста. Внутренне это может быть даже машинный код.

  • блок $

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

  • ценность ^

    Поднимите значение. А именно, превратить его в блок, который толкает это значение.

    Пример :

       1 ^
    == (1)
    
  • блок1 блок2 &

    Соедините два блока, образуя один, который запускает оба в последовательности.

    Пример :

       (1) (2) &
    == (1 2)
    

Манипулирование стеком

  • N c

    Скопируйте n-е значение стека.

    Пример :

       5 4 3 2 1 0 3c
    == 5 4 3 2 1 0 3
    
  • N p

    Соберите n-е значение стека (уберите его и перенесите на передний план).

    Пример :

       5 4 3 2 1 0 3p
    == 5 4 2 1 0 3
    
  • N d

    Удалите n значений из стека. 0dэто неоперация.

    Пример :

       5 4 3 2 1 0 3d
    == 5 4 3
    

Реляционные операторы

  • ab (on_true) (on_false) =

    Проверьте, равно ли а б. Поглотить все, кроме первого аргумента, и вызвать on_true или on_false. Если один аргумент равен нулю, а другой - любого другого типа, результат будет ложным. В противном случае a и b должны быть целыми числами.

    Пример :

       3 3 ('0+ .) (1d) =
    == 3 '0+ .
    
  • ab (on_true) (on_false) <

    Проверьте, если а меньше, чем б. a и b должны быть целыми числами.

    Пример :

       3 5 (1d 5) () <
    == 3 1d 5
    == 5
    
  • ab (on_true) (on_false) >

    Проверьте, если а больше, чем б. a и b должны быть целыми числами.

    Пример :

       3 5 (1d 5) () >
    == 3
    
  • Ло привет (on_true) (on_false) ~

    Проверьте, что lo <= a <= hi. a, lo и hi должны быть целыми числами.

    Пример :

       3 0 10 ('0+ .) (1d) ~
    == 3 '0+ .
    

I / O

  • с .

    Положите символ с (потребляя его из стека).

  • ,

    Получить персонажа и положить его в стек. Если достигнут конец файла, нажимается -1.

  • с !

    Unget персонаж. Точно так же, как ungetc в C, разрешен только один возврат.

Целочисленные литералы

  • 'c

    Нажмите на символ c.

  • [0-9] +

    Нажмите десятичное целое.

арифметика

  • аб +
  • аб -
  • аб *

    Добавить / вычесть / умножить два числа.

    Пример :

       3 5 + 7 3 + *
    == 80
    
  • аб /

  • аб %

    Деление и модуль. В отличие от C, они округляются в сторону отрицательной бесконечности.

Разнообразный

  • код #комментария

    #Характер закомментирует все до конца строки.

  • )

    Используется для окончания блоков. Может использоваться и для завершения всей программы.

  • Все остальные символы игнорируются.

Джои Адамс
источник
24

Двоичное лямбда-исчисление, 232 бита (29 байт)

0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010

См. Http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding для получения подробной информации.

Джон Тромп
источник
2
Почему это не принятый ответ D: BLC удивительно!
кот
Вы можете объяснить это вообще?
PyRulez
1
К сожалению, Википедия удалила страницу двоичного лямбда-исчисления. Моя страница tromp.github.io/cl/cl.html содержит ссылки на сохраненную копию и на статью, которую я написал, объясняющую работу переводчика.
Джон Тромп
13

Я не могу взять кредит на этот , но я думал, что поделюсь этим удивительным:

Брейнф *** (423)

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]
Питер Олсон
источник
10

BlockScript - 535

{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

BlockScript - это тривиальный язык на основе стека спагетти, который я создал специально для этой задачи. Базовый интерпретатор - blockscript.c .

Пример программы (печатает первые 15 чисел Фибоначчи):

{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Интерпретатор считывает как исходный код, так и программный ввод со стандартного ввода в указанном порядке. Это означает, что для запуска интерпретатора внутри интерпретатора внутри интерпретатора просто скопируйте и вставьте:

# Level 1
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 2
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 3
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Как и в фильме « Начало» , вы не можете пройти глубже трех уровней. Это не вопрос времени, а пространство. BlockScript утечка памяти обильно, и это связано с тем, как сам язык разработан.


Справочник по языку:

Получить переводчика здесь

В BlockScript «стек» не является массивом, который перезаписывается последующими операциями, к которым вы привыкли. На самом деле он реализован в виде неизменяемого связанного списка, и стек сохраняется в течение всей программы. Кроме того, ни один оператор (кроме @) не удаляет значения из стека. Однако модификации стека влияют только на блок, в котором они происходят.

Выбор значения

  • a через z

    Извлеките 0-25-й предмет из стека и поместите его в стек. aотносится к заголовку или к последнему добавленному элементу стека.

  • A через Z

    Получите 0-25-й элемент текущего кадра и поместите его в стек.

  • [

    Откройте «рамку», чтобы выбрать элементы из стековой ссылки (см. Ниже) в начале стека. [не требует соответствия ], но рамки имеют лексическую область видимости. В BlockScript «область действия» определяется фигурными скобками ( {... }), которые образуют блоки. Таким образом, открытие кадра внутри блока не повлияет на код вне блока.

  • ]

    Закройте текущий кадр, вернувшись к предыдущему кадру (если есть).

Блоки

  • { ... }

    Создайте «блок» и поместите его в стек. Внутри блока стек будет начинаться с того, что был до блока, за исключением того, что стек вызывающей стороны будет помещен сверху. Стеки являются постоянными и неизменными в BlockScript, поэтому блоки являются замыканиями. Идиома {[означает открыть блок, затем открыть фрейм, чтобы начать выбор аргументов (используя Aсквозной Z). Возвращаемое значение блока - это заголовок стека при }достижении.

    Пример:

    '3 '2 '1 {[ b. d. f. B. C. D. A! } 'D 'C 'B d!;
    

    Это печатает 123BCD123DCB123BCD123DCB…. Буквы в нижнем регистре относятся к значениям стека, а буквы в верхнем регистре относятся к аргументам (потому что фрейм установлен в стеке вызывающей стороны). A!берет голову вызывающего абонента (который гарантированно будет вызываемым блоком) и вызывает его. Если вам интересно, почему он обращается вспять BCDкаждый раз, это потому, что B. C. D.эти аргументы передаются в обратном порядке прямо перед вызовом самого блока.

  • !

    Вызовите блок. Вставьте возвращаемое значение в стек.

Ссылки на стек

  • &

    Создайте ссылку на стек и поместите ее в стек. Думайте об этом как о «супер-минусах», так как он эффективно отбирает каждый элемент в стеке и формирует из него «кортеж». Идиомы &[означает , что все a, b, cупомянутые до настоящего времени могут быть доступны с A, B, C(для оставшейся части блока или пока ]не встретится).

    Частично потому, что &захватывает больше значений, чем обычно требуется, BlockScript утечка памяти по своей конструкции.

  • @

    Переключиться на стек, на который указывает ссылка на стек a. Этот оператор довольно странный, но самоинтерпретатор BlockScript использует его пару раз, чтобы избежать необходимости выдвигать одни и те же аргументы дважды. Эффекты @(или любая стековая операция, в этом отношении) ограничены блоком, в котором он вызывается. Кроме того, на фрейм это не влияет @, поэтому фрейм можно использовать для получения значений, которые вам нужны после переключения стеков.

Условное выражение

  • ? <на true> : <на false>

    Условное выражение, как и тернарный оператор в C. То есть, если a"true" (т. Е. Не равно целому нулю), тогда делать <on true> , иначе делать <on false> .

I / O

Примечание: ввод и вывод выполняются в UTF-8. «Символ» - это целое число, соответствующее индексу Unicode.

  • ,

    Получите следующий символ ввода и поместите его в стек. Если достигнут конец ввода, вместо этого нажмите -1.

  • .

    Выведите символ на верхушку стека.

Целочисленные / символьные литералы

Примечание. Целые числа и символы - это одно и то же в BlockScript.

  • 'c

    Нажмите на символ c.

  • [0-9] +

    Нажмите десятичное целое.

арифметика

Эти операторы работают только с целочисленными значениями.

  • +Вычислить b+ a(сдвигая результат, но не сбрасывая ни одно из значений).
  • -Compute b- a.
  • *Вычислить b* a.
  • /Вычислить b/ a(целочисленное деление; округление до отрицательной бесконечности).
  • %Вычислить b% a(целочисленный модуль; округляет до отрицательной бесконечности).

Реляционные операторы

Эти операторы работают только с целочисленными значениями.

  • <Если bменьше чем a, нажмите 1, иначе нажмите 0.
  • >
  • =

Разнообразный

  • # Комментарий к концу строки
  • Программа должна заканчиваться ;
  • Все остальные символы игнорируются.
Джои Адамс
источник
2
Христос. Хотите поделиться спецификацией, как вы сделали для CI?
Кейси
@Casey: добавлена ​​ссылка.
Джои Адамс
1
Вам было бы интересно узнать, что вы мечтаете? ... На 4 уровне.
Матеин Улхак,
3

Зозотез ЛИСП : 414

Добавлены переводы строк, чтобы получить хороший блок, который не нужен и не учитывается.

((\(E V A L)(E(r)'(())))(\(x e)(?(s x)(V x e)((\(b j)(?(= b ")(a j)(?(= b \)x
(?(= b ?)(?(E(a j)e)(E(a(d j))e)(E(a(d(d j)))e))(?(s b)(A b(E(a j)e)(E(a(d j)
)e))(E(a(d(d b)))(L(a(d b))j e)))))))(E(a x)e)(d x))))(\(x g)(? g(?(= x(a(a
g)))(d(a g))(V x(d g)))x))(\(f h v)(?(= f r)(r)(?(= f p)(p h)(?(= f s)(s h)(?
(= f a)(a h)(?(= f d)(d h)(?(= f =)(= h v)(c h v))))))))(\(k v i)(? k(L(d k)(
d v)(c(c(a k)(E(a v)i))i))i)))

Теоретически он должен быть в состоянии работать сам, но поскольку оригинальный интерпретатор является двоичным файлом BrainFuck, а сам интерпретатор, я смог протестировать только каждую часть. Когда дано само по себе и простое выражение, (p p)я думаю, что ему нужно больше времени, чем 40 минут, которые я ждал до сих пор, и я использую свой пост jitbfдля его запуска, который (неправильно) использует Perl Inline-C для запуска кода C на лету.

Невозможно реализовать весь Zozotez в Zozotez, так как у него нет средств для изменения минусов и :(setq / define) это необходимо для обновления привязок. Я также не реализовал явный аргумент begin / progn или & rest, макросы и специальные аргументы печати, поскольку не использовал его в интерпретаторе. Я включил p(печать), хотя я не использую его, поэтому программы должны явно печатать свои расчеты, как и оригинальный интерпретатор.

Тот же безгольфен

;; A stand alone Zozotez script need to be
;; contained in one expression, here with
;; all functions provided as arguments to
;; get them bound in the dynamic environment
((\ (E V A L)
  (E(r)'(())))
 ;; E (EVAL)
 (\ (x e)
   (? (s x)
      (V x e)
      ((\ (b j)
         (? (= b ") (a j)
         (? (= b \) x
         (? (= b ?) (? (E(a j)e) (E(a(d j))e) (E(a(d(d j)))e))
         (? (s b)
            (A b (E(a j)e) (E (a(d j))e))
            (E (a(d(d b))) (L(a(d b))j e)))))))
       (E (a x) e)(d x))))
 ;; V (VALUE / symbol->value)
 (\ (x g)
   (? g
      (? (= x (a (a g)))
         (d (a g))
         (V x (d g)))
      x))
 ;; A (APPLY) but just for primitives
 (\ (f h v)
   (? (= f r) (r)
   (? (= f p) (p h)
   (? (= f s) (s h)
   (? (= f a) (a h)
   (? (= f d) (d h)
   (? (= f =)
      (= h v)
      (c h v))))))))
 ;; L ( joint evLis / extend-env)
 (\ (k v i)
   (? k
      (L (d k) 
         (d v)
     (c (c (a k) 
           (E (a v) i)) 
        i))
      i)))
Сильвестер
источник
0

CHIQRSX9 + (вероятно, не конкурирующий), 2 байта

+I

На этом языке HQ9 + нет возможности написать интерпретатор с самоинтерпретацией без использования I, который запускает встроенный интерпретатор, который обрабатывает STDIN.

user8397947
источник
1
Нигде в правилах не говорится, что встроенные собственные интерпретаторы запрещены. Это говорит о том eval, что для выражений, а не программ.
Эрик Outgolfer
Как вычислить простые числа в этом языке?
pppery
Предполагается, что @ppperry Xсделает язык Turing-полным (таким образом, способным вычислять простые числа) зависимым от реализации способом.
user8397947
Согласно странице Esolang, команда интерпретатора Perl Xслучайным образом возмущает программу и выполняет ее, что означает, что нельзя использовать команду, кроме как для детерминированного вычисления простых чисел. Можете ли вы привести пример интерпретатора, который позволит вам использовать Xспособ, который вы указали?
pppery
@ppperry Очевидно, что интерпретатор, написанный на Perl, является единственным интерпретатором, так что нет. Кроме того, что, если есть программа, которая вычисляет простые числа при "рандомизации" с определенным значением?
user8397947
0

Одновременная файловая система Befunge 98 - 53 \ 18 байт (почти наверняка читерство)

Полный 53-байтовый интерпретатор без ограничений (хотя я не тестировал сложные временные взаимодействия, включающие разделение и перенос IP-адресов):

v ;;;;;;;;
>]390'ai@
 t;;;;;;;;
;>zzzzz#;

Читает ввод из файла с именем aи выполняет его. В правилах не указано, что мы не можем использовать самоизменяющийся код.

18-байтовый интерпретатор, который не допускает перенос (IP-перемещение одного края кода и начало с противоположного края):

]210'ai@
t
><
pppery
источник