Написать переводчик смены

10

РЕДАКТИРОВАТЬ: Как некоторые из вас подозревали, была ошибка в официальном переводчике: порядок композиции в .был обратный. У меня было две версии переводчика, и я использовал неправильную. Примеры были также написаны для этой неправильной версии. Я исправил переводчик в репозитории, и примеры ниже. Описание >также было немного двусмысленным, поэтому я исправил это. Кроме того, извинения за то, что это заняло так много времени, я застрял в некоторых реальных вещах.

РЕДАКТИРОВАТЬ 2: У моего интерпретатора была ошибка в реализации, .которая была отражена в примерах (они полагались на неопределенное поведение). Теперь проблема исправлена.

Введение

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

Спецификация

В Shift есть два типа данных:

  • Функции, которые имеют произвольную положительную арность (количество входов) и возвращают список выходов. Например, функция, которая дублирует свой единственный вход, имеет арность 1, а функция, которая меняет два своих входа, имеет арность 2.
  • Бланки, которые все идентичны и не имеют никакой другой цели, кроме как не быть функциями.

Программа Shift состоит из нуля или более команд , каждая из которых представляет собой один символ ASCII. Всего 8 команд:

  • !( применить ) извлекает функцию fи значение xиз стека и применяется fк x. Если fимеет арность 1, список f(x)добавляется в начало стека. Если он имеет арность n > 1, новая (n-1)-арная функция помещается gв стек. Он принимает входные данные и возвращает .x1,x2,...,xn-1f(x,x1,x2,...,xn-1)
  • ?( пусто ) толкает пробел в стек.
  • +( клон ) помещает в стек унарную функцию, которая дублирует входные данные: любое значение xотображается на [x,x].
  • >( shift ) помещает в стек унарную функцию, которая принимает n-ary-функцию f, и возвращает (n+1)-ary-функцию, gкоторая игнорирует свой первый аргумент x, вызывает fоставшиеся и привязывает xперед результатом. Например, shift(clone)это двоичная функция, которая принимает входные данные a,bи возвращает [a,b,b].
  • /( fork ) помещает в стек троичную функцию, которая принимает три входа a,b,cи возвращает, [b]если aпусто, и в [c]противном случае.
  • $( Вызов ) толкает в стек двоичную функцию , которая появляется функцией fи значение x, и применяет fк xточности так , как !делает.
  • .( цепочка ) помещает в стек двоичную функцию, которая выдает две функции fи gи возвращает их композицию: функция, hкоторая имеет ту же самую арность f, что и которая обычно принимает свои входные данные, применяется fк ним, а затем полностью применяется gк результату (вызывает это столько раз, сколько диктует его арность), с неиспользованными предметами из результата, fоставшимися в результате h. Например, предположим, что fэто двоичная функция, которая клонирует свой второй аргумент и gназывается call . Если стек содержит [f,g,a,b,c]и мы .!!, то он содержит [chain(f,g),a,b,c]; если мы делаем !!дальше, то fсначала применяется a,b, производя[a,b,b], затем gприменяется к первым двум элементам этого, поскольку его арность равна 2, производя [a(b),b], и стек, наконец, будет [a(b),b,c].
  • @( скажем ) выдвигает унарную функцию, которая просто возвращает свой ввод и печатает, 0если она была пустой, и 1если это была функция.

Обратите внимание, что все команды, кроме !простого переноса значения в стек, не позволяют выполнять ввод, и единственный способ вывести что-либо - использовать @. Программа интерпретируется путем оценки команд одна за другой, вывода 0s или 1s при каждом вызове «say» и выхода. Любое поведение, не описанное здесь (применение пробела, применение стека длиной 0 или 1, вызов «цепочки» для пробела и т. Д.) Не определено: интерпретатор может аварийно завершить работу, потерять молчание, запросить ввод или что-то еще.

Задание

Ваша задача - написать переводчика для Shift. Он должен принимать из STDIN, командной строки или аргумента функции интерпретируемую программу Shift и печатать в STDOUT или возвращать результирующий (возможно, бесконечный) вывод 0s и 1s. Если вы пишете функцию, вы должны каким-то образом получить доступ к выходам бесконечной длины (генератор в Python, ленивый список в Haskell и т. Д.). В качестве альтернативы вы можете взять другой ввод, число nи вернуть хотя бы nсимволы вывода, если он длиннее n.

Побеждает меньшее количество байтов, и стандартные лазейки запрещены.

Тестовые случаи

Эта программа Shift печатает 01:

?@!@@!

Начиная слева: нажмите пробел, нажмите сказать , затем примените слово к пробелу. Это выводы 0. Затем дважды нажмите « сказать» и примените второе слово к первому. Это выводы 1.

Эта программа зацикливается навсегда, не выводя ничего:

$+.!!+!!

Нажмите call и clone , затем примените к ним цепочку (нам нужно два !s, так как цепочка является двоичной функцией). Теперь в стеке есть функция, которая принимает один аргумент, дублирует его и вызывает первую копию второго. С +!!, мы дублируем эту функцию и вызываем ее на себя.

Эта программа печатает 0010:

?@$.++>!.!!.!!.!!!!+?/!!!@!@>!!!

Нажмите пробел и скажите . Затем создайте двоичную функцию, которая копирует свой второй аргумент b, затем копирует первый aи составляет его с собой, затем применяет композицию к копии b, возвращая [a(a(b)),b]. Примените его, чтобы сказать и пусто, затем примените слово к двум элементам, остающимся в стеке.

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

?@+$>!>!+>!///!!>!>!.!!.!!.!!+!!!!

Нажмите пробел и скажите . Затем составьте троичную функцию, которая принимает в f,g,xкачестве входных данных и возвращает [f,f,g,g(x)]. Клонируйте эту функцию и примените ее к себе, скажем , и к пробелу. Это приложение не меняет стек, поэтому мы можем применить функцию снова столько раз, сколько захотим.

Эта программа печатает бесконечную последовательность 001011011101111..., где число 1s всегда увеличивается на единицу:

@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!

Репозиторий содержит аннотированную версию.

Zgarb
источник
Я немного запутался здесь. Когда вы пишете "берет", как в команде shift, вы имеете в виду pops или вы подразумеваете применение команды apply?
tecywiz121
1
Кроме того, я действительно не уверен из вашей спецификации, как цепочка должна работать. Не могли бы вы уточнить это на примере, пожалуйста?
tecywiz121
@ tecywiz121 Вот как я понимаю: скажем, у вас есть две функции в верхней части стека, f(x1, x2, ..., xn)и g(y1, y2, ..., ym). Вызов .вызывает оба из них и толкает функцию h(z1, z2, ..., zn). Теперь вы можете съесть все эти аргументы, постепенно вычеркивая их !. После nтаких приложений оставшаяся функция имела только один аргумент, и в этот момент она вычисляет f(z1, z2, ..., zn)(то есть fприменяется ко всем аргументам, в которых вы каррировали), который выдвигает некоторые новые значения, а затем сразу же получает mзначения из стека и вызывает gих.
Мартин Эндер
@ MartinBüttner Если Zgarb считает, что он соответствует правилам, вы можете использовать второй входной параметр, определяющий максимальный размер вывода. Это также будет решением проблемы с отложенной оценкой.
Рандомра
@ tecywiz121 .работает точно так же, как описал Мартин, за исключением того, что если он fвозвращает список mзначений, меньших значений, результат не определен (композиция имеет арность n, поэтому она не может использовать больше аргументов из стека). По сути, выходные данные fиспользуются в качестве временного стека, на который gпроталкиваются и применяются mвремена !, а результат этого добавляется в основной стек.
Згарб

Ответы:

12

Python 2, 752 667 534 506 445 436 427 404 398 393 байта

Это ни в коем случае не коротко ... но я сделал все возможное. Любые предложения по гольфу будут очень признательны ...

EDIT6: теперь это скрипт вместо функции. Сохраните его в файл (shift.py, forex), затем запустите его с помощью $ python shift.py '<my_input>'. Убедитесь, что входные данные заключены в одинарные кавычки, иначе bash сойдет с ума от введенных символов.

EDIT7: Aaaaaaand ... это больше не читается. Но я избавился от еще 23 байтов, так что это хорошо, я думаю? Я тоже выложу версию без гольфа.

EDIT8: еще один гольф, благодаря @Zgarb.

k,d=[],[]
u=k.append
def z(f,a=1):f.a=a;return f
exec "i=!x:x(*map(k.pop,[-1]*x.a)));e=dict(zip('?+>/$.@',[0,!x:u(x)<u(x)),!x:u(!a,*_:x(*_)<u(a),x.a+1))),!x,y,z:u((z,y)[x<1]),3),!x,y:u(!*_:x(y,*_),x.a-1))if x.a>1 else x(y),2),!x,y:u(!*_:x(*_)<i(y),x.a)),2),!x:d.append(`+(x>0)`)<u(x))]))".replace('!',"z(lambda ")
for _ in raw_input():
 try:[i,u][_ in e](e.get(_,e['$']))
 except:break
print d

РЕДАКТИРОВАТЬ: спасибо @DLosc за помощь в игре в гольф! Удалось уменьшить его на 85 байт.

РЕДАКТИРОВАТЬ 2: вырезать тонну ненужных упаковщиков, и бросил его еще на 133 байта!

EDIT3: ... и еще 28 благодаря @ Sp3000 и @orlp в чате!

EDIT4: с помощью @orlp & @ Sp3000 удалил все декораторы и теперь он на 61 байт короче.

РЕДАКТИРОВАТЬ5: помочь meeeeee, я не могу перестать играть в гольф в этом .... еще 9 байтов прошло. Избавление от окончательного оператора печати спасло бы еще 7, но затем, если вы запустите m () в цикле, все выходные данные будут в одной строке ... это нормально?

Вот негольфированная версия:

stack = []
push = stack.append

def arity(func,a=1): #give each of our functions an arity
    func.arity = a
    return func

def do(func): ##pop the args off the stack, then call the function
    args = map(stack.pop,[-1]*func.arity)
    func(*args)

def call(func,arg): #apply is just do(call)
    if func.arity == 1:
        func(arg)
    else:
        def curried(*a): #a quick little currier
            func(arg, *a)
        curried = arity(curried, func.arity - 1)
        push(curried)

def clone(arg):
    push(arg)
    push(arg)

def shift(func):
    def shifted(a, *arg):
        func(*arg)
        push(a)
    shifted = arity(shifted, func.arity + 1)
    push(shifted)

def fork(a, b, c):
    if a == 0:
        push(b)
    else:
        push(c)

def chain(func, gunc):
    def composition(*args):
        func(*args)
        do(gunc)
    composition = arity(composition, func.arity)
    push(composition)

def say(arg):
    print '10'[arg == 0],
    push(arg)

commands = {'?': 0,
            '+': arity(clone),
            '>': arity(shift),
            '/': arity(fork, 3),
            '$': arity(call, 2),
            '.': arity(chain, 2),
            '@': arity(say)}

def interpret(input_string):
    for command in input_string:
        try:
            if command == '!':
                do(call)
            else:
                push(commands[command])
        except RuntimeError: #this handles max recursion depth errors
            break            # for infinite programs
    print

if __name__ == "__main__":
    interpret(raw_input())

Основная идея состоит в том, что список python очень хорошо работает как стек, и, сохраняя u=k.append, я не только сохраняю символы, но я также могу использовать их @uкак декоратор для проталкивания функций (больше нет!).

Так как пара функций, которые действуют на функции n-arity, должны иметь возможность принимать произвольное количество аргументов, я должен был использовать *args, что означало, что мой первоначальный план отслеживания f.func_code.co_argcount должен был быть заменен на arity атрибут декоратора .

С точки зрения обработки бесконечных программ, интерпретатор работает, пока не достигнет максимальной рекурсивной глубины; обработчик RuntimeError внизу имеет тихий выход в этот момент и затем выводит текущую строку вывода.

Тестовые случаи:

>>> tests
['?@!@@!', '$+.!!+!!', '?@$..!!+.!!+>!.!!!!+?/!!!@!@>!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!!!!', '@?/!@>!.!!??/!!>!.!!+.!!.+>!.!!$$.!!$.!!$.!!+.!!$>!>!.!!$>!>!.!!+>!.!!$>!>!>!.!!+>!>!.!!///!!>!>!>!.!!+!!!!!']
>>> for t in tests: m(t)
0 1

0 0 1 0
0
0 0
0 0 0
0 0 0 0
0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
sirpercival
источник
1
Моя первая реакция: @ _ @ Если серьезно, хорошая работа - размещение реальных функций в стеке - это действительно аккуратное решение. Несколько советов: 1) Тернарные операторы обычно могут быть сокращены так или иначе . 2) Вы можете заменить ['1','0'][...]просто '10'[...]. 3) Почему бы x is 0и нет x==0(или x<1)? 4) Не надо уточнять RuntimeError, просто exceptсделаю. 5) Поскольку вы используете Python 2, табуляция и пробелы считаются разными уровнями отступов - конечно, но должны сэкономить ~ 25 байт.
DLosc
1
Вы должны быть в состоянии сократить это до x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))- логические операторы все еще коротки, но используют меньше символов, чем троичные. Затем сохраните другие байты, используя в x.a-1качестве условия (0 / ложного , если xэто 1, отлично от нуля / верно в противном случае) и поменять местами « затем» и «еще» выражения: x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y). (Надо еще раз поиграть в гольф, когда ты меня
обошел
1
После того, как я столкнулся с аналогичной проблемой, я понимаю, что сейчас не x.a==1получается - если это правда, но x(y)возвращает что-то ложное, он тоже пытается оценить u(...). Но, похоже, вам не нужно экономить те жалкие 3 байта, которые вам дали бы! Я признаю, сэр: вы превзошли меня.
DLosc
1
Всего лишь одно замечание: указанный формат вывода не имеет пробелов - вы можете решить с помощью различных стратегий , не зная, какая из них самая короткая. Конечно, ваша программа обрабатывает RuntimeErrorwhile, а моя просто просит пользователя перенаправить stderr ... так что мы, вероятно, даже на придирках. ; ^)
DLosc
1
Для чего *_нужны лямбды?
mbomb007
4

Ghostscript

Пока не играю в гольф, так как мне все еще нужно отработать функцию разбора.

Эта реализация использует _и :вместо >и /, и требует, чтобы все символы программы были разделены пробелами. Это происходит потому , что >и /не являются допустимыми именами в Postscript, и операторы не саморазгранично, но это будет исправлено , когда я пишу анализатор.

Первая часть кода должна быть достаточно прозрачной, поскольку она просто повторяет определения операторских функций. Магия происходит в определении !.

/switch {
    /y exch def
    /x exch def
    {x} {y} ifelse
} bind def

/unwrap {
    dup type (arraytype) eq {aload pop} if
} bind def

/! { % IN: <x> <f> OUT: <g>|<f(x)>
    [ 3 1 roll unwrap] cvx %prefix argument into function
    dup /fun exch def %bind

    [ count 1 roll ] { %run the function sandboxed so it can't take any additional args
        2 dict begin
        /=only {} def % suppress output
            {
                fun
            } stopped /err exch def clear err
        end
    } .runandhide


    exch {
        $error /errorname get
        (stackunderflow) ne {
            handleerror
        } if

        $error /newerror false put

        unwrap
    } {
        unwrap exec
    } ifelse
} def

/? 0 def
/+ {{dup}} def
/_ {{/f exch def pop f}} def % using _ instead of >
/: {{? ne 3 1 roll switch}} def % using : instead of /
/$ {{!}} def
/. {{/g exch def exec g}} def 
/@ {{dup ? eq {0}{1} ifelse =only}} def

То , как !работает просто: Во- первых, это добавляет аргумент xв fпредваряя xк содержанию f, толкая его обратно в стек, и называя копию результата fun.

Затем он упаковывает весь стек в массив. .runandhideявляется расширением Ghostscript для запуска изолированного кода, скрывающего содержимое предыдущего массива от процедуры, в которой он вызывается. Команда dictпомещает новый словарь в стек dict, сужая область имен, определенных внутри, до тех пор, пока endон не выскочит обратно. Он также заменяет =only(оператор вывода, в котором я использую @) фиктивный, подавляя вывод во время пробного запуска. stoppedявляется PostScript-эквивалентом tryоператора, найденного в других языках, и возвращает true, если его процедура вызвала ошибку, и false, если он завершился.

После завершения пробного запуска funпрограмма восстанавливает исходный стек из скрытого массива и, если он funзавершен без ошибок, запускает его по-настоящему, сохраняя вывод.

AJMansfield
источник
2

Python3, 685 670 634 633 байта

Я уверен, что это самая длинная вещь, которую я когда-либо играл в гольф. Раньше он был несколько читабельным, но следование советам @ sirpercival устранило этот недостаток!

from re import*
E,*k="E"
P="e(k.pop(),k.pop())"
def H(a,b):global k;k+=list(a)+[N(b)];exec("k+=%s;"%P*Z(N(b)));return[]
def e(a,b):a=sub("(?<!\d)0",repr(N(b,1)).replace("\\",r"\\"),a,1);return Z(a)and[a]or list(eval(a))
D=list(zip("ilhydsSNZ",[3,2,2]+[1]*6,sub("A","N(a)",',b,c:[N([b,c][a>E])]|,b:e(A,N(b))|,b:["H(%s,%s)"%(A,repr(b))]|:print(0+(a>E),end="")or[A]|:[A]*2|:["S(0,%s)"%A]|,b:b+[A]|,b=-1:sub("\d+",lambda m:str(int(m.group())+b),a)|:len(split("\D0",a))-1').split("|")))
for n,r,f in D:exec(n+"=lambda a"+f)
F=dict(zip("/$.@+>?!",D))
for z in input():n,r,f=F[z];k+=z!="!"and[[n+"(%s)"%",".join("0"*r),E][z=="?"]]or eval(P)

kэто стек, который содержит функции , представленные в виде строк , как "h(0,0)"(что с ч айн ). Когда функция передается в качестве аргумента другой функции, он получает repr«d и все числа увеличивается: "h('h(1,1)',0)". Как только все 0s заменяются в функции, все это передается eval, вызывая, таким образом, соответствующую функцию Python - большинство из которых являются лямбда-функциями, сгенерированными из большой строки в строке 6 execстрокой 7.

Увеличение нескольких уровней вложенных функций, их цитирование и экранирование были самой большой головной болью. Я мог бы сэкономить немного больше на операциях с регулярными выражениями, если бы мог предположить, что вложение функций не будет происходить глубже, чем на 9 уровней, но, как указано в комментариях, это, вероятно, не является безопасным предположением.

Разрушенная более ранняя версия кода:

from re import *
E="E"
stack=[]

clone=lambda a:[unnest(a)]*2
shift=lambda a:["shifted(0,%s)"%unnest(a)]
fork=lambda a,b,c:[unnest(c if a!=E else b)]
call=lambda a,b:apply(unnest(a),unnest(b))
chain=lambda a,b:["chained(%s,%s)"%(unnest(a),repr(b))]
def say(a):
 print(1 if a!=E else 0,end="")
 return [unnest(a)]

shifted=lambda a,b:b+[unnest(a)]
def chained(a,b):
 global stack
 stack+=list(a)+[unnest(b)]
 exec("stack+=apply(stack.pop(),stack.pop());"*zeros(unnest(b)))
 return []

nest=lambda a,direction:sub("\d+",lambda m:str(int(m.group())+direction),a)
unnest=lambda a:nest(a,-1)
zeros=lambda a:len(split("\D0",a))-1
def apply(a,b):
 a=sub("(?<!\d)0",repr(nest(b,1)).replace("\\",r"\\"),a,1)
 return [a] if zeros(a) else list(eval(a))

functions=dict(zip("+>/$.@",zip(["clone","shift","fork","call","chain","say"],[1,1,3,2,2,1])))

for cmd in input():
 if"!"==cmd:
  stack+=apply(stack.pop(),stack.pop())
 elif"?"==cmd:
  stack+=[E]
 else:
  name,arity=functions[cmd]
  stack+=[name+"(%s)"%",".join("0"*arity)]

Единственным потенциальным недостатком этой реализации является то, что она использует рекурсию, поэтому программы, которые должны быть бесконечными, достигают максимальной глубины рекурсии довольно быстро. (Возможно, вы захотите перенаправить stderr при запуске бесконечной программы - в противном случае трассировка стека затопит фактический вывод.) Кроме этого, все, кажется, работает.

DLosc
источник
Не могли бы вы написать программу, которая генерирует вышеуказанную программу, а затем выполняет ее? У вас есть много повторяющегося кода, который должен быть сжимаем, как lambda aи k.pop().
mbomb007
@ mbomb007 ... Думаю, мой мозг взорвется. (Но посмотрите недавнее редактирование - я все-таки сделал k.pop()ситуацию немного менее повторяющейся.)
DLosc
Вы можете сделать трюк exec / translate для всех этих лямбд? склеить их все в одну строку?
sirpercival
еще один комментарий: я сомневаюсь, что вы можете положиться на вложение функций <= 9 с этим языком
sirpercival
@sirpercival Да, я думал попробовать это. И нет, я полагаю, нет. : ^ P
DLosc
1

Цейлон, 1167 1057 1031

Я не понимаю это так коротко, как монотипные версии Python ...

import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}

Вот отформатированная (и закомментированная) версия того же кода (с пробелами / символами новой строки / комментариями она становится 4867 байтами):

import ceylon.language.meta.model {
    N=Function
}
import ceylon.collection {
    H=HashMap
}
//↑ Import of stuff we need – with a shorter alias.
// (The comment is down here due to a bug in my comment and space
//  remover – it doesn't remove a comment if it is the first token
//  at all.)

// Our data items are either functions or blanks.
interface D of F | b {}

// There is no point in having many blanks – so here a singleton.
object b satisfies D {}

// The function class. Our functions take a number of data items,
// and return a number of data items.
// We know the arity a, and have also an actual function f, and a number
// or already collected arguments.
class F(shared Integer a, [D+](D+) f, [D*] c = [])
        satisfies D {
    // apply once (= collect one parameter). Returns either the result,
    // or a function with arity one less.
    shared [D+] o(D i) {
        [D+] s = [i].prepend(c);
        return a == 1 then f(*s) else [F(a - 1, f, s)];
    }
    // apply fully (= with all needed parameters).
    // The input size should equal the arity.
    shared [D+] y([D+] i) {
        // merge collected and input arguments.
        return f(*i.prepend(c));
    }
}
// creates a shift function from a ceylon function,
// deriving the arity using reflection.
F m<A>(N<[D+],A> f)
        given A satisfies [D+]
        => F(f.parameterTypes.size, (D+ i) => f.apply(*i));

//
// clone: a unary function that duplicates its input: any value x is mapped to [x,x].
//
[D, D] e(D x) => [x, x];

//
// shift: a unary function that takes in an n-ary function f, and returns an
// (n+1)-ary function g that ignores its first argument x, calls f on the
// remaining ones, and tacks x in front of the result. For example,
// shift(clone) is a binary function that takes inputs a,b and returns [a,b,b].
//
[F] t(F f) {
    [D+] g(D+ i) {
        assert (is [D+] r = i.rest);
        return [i[0], *f.y(r)];
    }
    return [F(f.a + 1, g)];
}

//
// fork: a ternary function that takes three inputs a,d,c, and returns [d] if a is a blank,
// and [c] otherwise.
//
[D] k(D a, D d, D c) => a == b then [d] else [c];

//
// call: a binary function that pops a function f and a value x,
//        and applies f to x exactly as ! does.
//
[D+] l(F a, D x) => a.o(x);

//
// chain:  a binary function that pops two functions f and g, and returns their composition:
//         a function h that has the same arity as f, and which takes its inputs normally, applies
//         f to them, and then fully applies g to the result (calls it as many times as its arity
//         dictates), with unused items from the output of f remaining in the result of h. For
//         example, suppose that f is a binary function that clones its second argument, and
//         g is call. If the stack contains [f,g,a,b,c] and we do .!!, then it contains
//         [chain(f,g),a,b,c]; if we do !! next, then f is first applied to a,b, producing
//         [a,b,b], then g is applied to the first two elements of that since its arity is 2,
//         producing [a(b),b], and the stack will finally be [a(b),b,c].
//
[F] n(F f, F g) {
    [D+] h(D+ i) {
        // call f, remember the results.
        [D+] r = f.y(i);
        // first some results from f are the arguments to g:
        assert (is [D+] d = r[0:g.a]);
        // remaining results from f are passed back directly, with the results from g.
        return g.y(d).append(r[g.a...]);
    }
    return [F(f.a, h)];
}

//
// say: a unary function that simply returns its input, and prints 0 if it was a blank,
//      and 1 if it was a function.
// 
[D] y(D x) {
    process.write(x == b then "0" else "1");
    return [x];
}

//
// Interpreter class, which manages the stack and interprets the commands.
// Just call the r method with the individual command characters.
//
class I() {
    // The stack. The only variable in the whole program.
    variable D[] s = [];

    // a hash map of items to be pushed by commands, most build using the m function.
    // The apply command is not here, this is handled separately by the interpreter. 
    value c = H {
        '?'->b,
        '+'->m(`e`),
        '>'->m(`t`),
        '/'->m(`k`),
        '$'->m(`l`),
        '.'->m(`n`),
        '@'->m(`y`)
    };

    // Interprets one command, indicated by a character.
    // Will throw an AssertionError for unknown commands.
    shared void r(Character i) {
        if (i == '!') {
            assert (
                is F f = s[0],
                is D x = s[1]);
            // apply f on x, push the result onto a shortened version of the stack.
            s = f.o(x).append(s[2...]);
        } else {
            assert (is D d = c[i]);
            // push d on top of the stack.
            s = [d].append(s);
        }
    }
}

shared void z() {
    process.readLine()?.collect(I().r);
}

Функции clone e, shift t, fork k, call l, say yи chain nиспользуют последнюю букву имен для сокращенной версии, потому что это дает меньше коллизий. (Общая информация : вилка была первоначально определена следующим образом: [Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];- когда я переименовал blankв bэто сломалось, потому что теперь сравнивают параметры aи bвместо того, чтобы aс заготовкой мне потребовалось некоторое время для отладки.) .

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

Пауло Эберманн
источник
Циклические версии на самом деле в какой-то момент выльются в StackOverflowError, а затем завершаются. В JVM нет оптимизации рекурсивного стека (или, по крайней мере, ни одной, которая бы работала для моей программы).
Пало Эберманн