Écrire un interprète de quart

10

EDIT: Comme certains d'entre vous le soupçonnaient, il y avait un bug dans l'interprète officiel: l'ordre de composition .était inversé. J'avais deux versions de l'interprète et j'ai utilisé la mauvaise ici. Les exemples ont également été écrits pour cette version incorrecte. J'ai corrigé l'interpréteur dans le référentiel et les exemples ci-dessous. La description de >était également un peu ambiguë, j'ai donc corrigé cela. De plus, je m'excuse d'avoir pris si longtemps, j'ai été pris dans des trucs réels.

EDIT2: Mon interprète avait un bug dans l'implémentation .qui se reflétait dans les exemples (ils s'appuyaient sur un comportement non défini). Le problème est désormais résolu.

introduction

Shift est un langage de programmation fonctionnel ésotérique que j'ai créé il y a quelques années, mais que j'ai publié aujourd'hui. Il est basé sur la pile, mais possède également un curry automatique comme Haskell.

spécification

Il existe deux types de données dans Shift:

  • Fonctions, qui ont une arité positive arbitraire (nombre d'entrées), et qui renvoient une liste de sorties. Par exemple, une fonction qui duplique sa seule entrée a l'arité 1 et une fonction qui échange ses deux entrées a l'arité 2.
  • Les blancs, qui sont tous identiques et n'ont d'autre but que de ne pas être des fonctions.

Un programme Shift se compose de zéro ou plusieurs commandes , dont chacune est un seul caractère ASCII. Il y a 8 commandes au total:

  • !( appliquer ) extrait une fonction fet une valeur xde la pile et s'applique fà x. Si fa l'arité 1, la liste f(x)est ajoutée au début de la pile. S'il a de l'arité n > 1, une nouvelle (n-1)fonction -ary gest poussée dans la pile. Il faut des entrées et des retours .x1,x2,...,xn-1f(x,x1,x2,...,xn-1)
  • ?( vide ) pousse un blanc dans la pile.
  • +( clone ) pousse dans la pile une fonction unaire qui duplique son entrée: toute valeur xest mappée [x,x].
  • >( shift ) pousse dans la pile une fonction unaire qui prend une nfonction -ary f, et retourne une (n+1)fonction -ary gqui ignore son premier argument x, appelle fles autres et claque xdevant le résultat. Par exemple, shift(clone)est une fonction binaire qui prend des entrées a,bet des retours [a,b,b].
  • /( fork ) pousse dans la pile une fonction ternaire qui prend trois entrées a,b,c, et retourne [b]si aest un blanc, et [c]sinon.
  • $( Appel ) pousse sur la pile une fonction binaire qui apparaît une fonction fet une valeur x, et l' applique fà xexactement comme le !fait.
  • .( chaîne ) pousse dans la pile une fonction binaire qui fait apparaître deux fonctions fet g, et renvoie leur composition: une fonction hqui a la même arité que f, et qui prend ses entrées normalement, leur s'applique f, puis s'applique entièrementg au résultat (appels autant de fois que son arité le dicte), avec les éléments inutilisés de la sortie de frester dans le résultat de h. Par exemple, supposons qu'il fs'agit d'une fonction binaire qui clone son deuxième argument et qu'elle gsoit appelée . Si la pile contient [f,g,a,b,c]et nous le faisons .!!, alors elle contient [chain(f,g),a,b,c]; si nous faisons !!ensuite, fest d'abord appliqué à a,b, produisant[a,b,b], gest ensuite appliqué aux deux premiers éléments de celui-ci puisque son arité est 2, produisant [a(b),b], et la pile sera finalement [a(b),b,c].
  • @( disons ) pousse une fonction unaire qui retourne simplement son entrée, et affiche 0s'il s'agissait d'un blanc et 1s'il s'agissait d'une fonction.

Notez que toutes les commandes, sauf !simplement pousser une valeur dans la pile, il n'y a aucun moyen d'effectuer une entrée, et la seule façon de sortir quoi que ce soit est d'utiliser @. Un programme est interprété en évaluant les commandes une par une, en imprimant 0s ou 1s chaque fois que "say" est appelé et en quittant. Tout comportement non décrit ici (appliquer un blanc, appliquer une pile de longueur 0 ou 1, appeler "chaîne" sur un blanc, etc.) n'est pas défini: l'interpréteur peut se bloquer, échouer en silence, demander une entrée, ou autre chose.

La tâche

Votre tâche consiste à écrire un interprète pour Shift. Il doit extraire de STDIN, de la ligne de commande ou de l'argument de fonction un programme Shift à interpréter et l'imprimer vers STDOUT ou renvoyer la sortie résultante (éventuellement infinie) de 0s et 1s. Si vous écrivez une fonction, vous devez pouvoir accéder aux sorties de longueur infinie d'une certaine manière (générateur en Python, liste paresseuse en Haskell, etc.). Alternativement, vous pouvez prendre une autre entrée, un nombre n, et renvoyer au moins des ncaractères de la sortie si elle est plus longue que n.

Le nombre d'octets le plus bas gagne et les failles standard sont interdites.

Cas de test

Ce programme Shift imprime 01:

?@!@@!

En partant de la gauche: appuyez sur un blanc, appuyez sur dire , puis appliquez le mot sur le blanc. Cela sort 0. Ensuite, appuyez deux fois sur say et appliquez le deuxième say au premier. Cela sort 1.

Ce programme boucle pour toujours, ne produisant aucune sortie:

$+.!!+!!

Poussez call et clone , puis appliquez-leur une chaîne (nous avons besoin de deux !s car la chaîne est une fonction binaire). Maintenant, la pile contient une fonction qui prend un argument, le duplique et appelle la première copie sur le second. Avec +!!, nous dupliquons cette fonction et l'appelons sur elle-même.

Ce programme imprime 0010:

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

Poussez un blanc et dites . Ensuite, composez une fonction binaire qui copie son deuxième argument b, puis copie le premier aet le compose avec lui-même, puis applique la composition à la copie de b, en retournant [a(a(b)),b]. Appliquez-le à dire et vide, puis appliquez dire aux deux éléments restants sur la pile.

Ce programme s'imprime 0. Pour chacun !!!que vous y ajoutez, il en imprime un supplémentaire 0.

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

Poussez un blanc et dites . Ensuite, composez une fonction ternaire qui prend f,g,xen entrée et en retour [f,f,g,g(x)]. Clonez cette fonction et appliquez-la à elle-même, disons , et au blanc. Cette application ne modifie pas la pile, nous pouvons donc appliquer à nouveau la fonction autant de fois que nous le souhaitons.

Ce programme imprime la séquence infinie 001011011101111..., où le nombre de 1s augmente toujours de un:

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

Le référentiel contient une version annotée.

code-golf interpreter stack Zgarb
la source
Je suis un peu confus ici. Lorsque vous écrivez "prend" comme dans la commande shift, voulez-vous dire pop ou voulez-vous dire appliqué par la commande apply?
tecywiz121
1
De plus, je ne suis vraiment pas sûr de vos spécifications comment la chaîne est censée fonctionner. Pourriez-vous le clarifier avec un exemple s'il vous plaît?
tecywiz121
@ tecywiz121 Voici comment je le comprends: disons que vous avez deux fonctions en haut de la pile, f(x1, x2, ..., xn)et g(y1, y2, ..., ym). L'appel .apparaît tous les deux et pousse une fonction h(z1, z2, ..., zn). Maintenant, vous pouvez manger tous ces arguments en les étirant progressivement avec !. Après de ntelles applications, la fonction restante n'avait qu'un seul argument, et à ce stade, elle calcule f(z1, z2, ..., zn)(c'est- fà- dire qu'elle s'applique à tous les arguments que vous avez analysés), ce qui pousse de nouvelles valeurs, puis consomme immédiatement les mvaleurs de la pile et les appelle g.
Martin Ender
@ MartinBüttner Si Zgarb pense que cela est conforme aux règles, vous pouvez utiliser un deuxième paramètre d'entrée définissant la taille maximale de la sortie. Ce serait également une solution au problème de l'évaluation paresseuse.
randomra
@ tecywiz121 .fonctionne exactement comme Martin l'a décrit, sauf que si frenvoie une liste de mvaleurs inférieures à , le résultat n'est pas défini (la composition a une arité n, donc elle ne peut pas manger plus d'arguments de la pile). Essentiellement, la sortie de fest utilisée comme une pile temporaire, sur laquelle gsont poussées et appliquées des mtemps en utilisant !, et le résultat est ajouté à la pile principale.
Zgarb

Réponses:

12

Python 2, 752 667 534 506 445 436 427 404 398 393 octets

Ce n'est en aucun cas court ... mais j'ai fait de mon mieux. Toute suggestion de golf serait très appréciée ...

EDIT6: Il s'agit maintenant d'un script au lieu d'une fonction. Enregistrez-le dans un fichier (shift.py, forex), puis exécutez-le avec $ python shift.py '<my_input>'. Assurez-vous de mettre l'entrée entre guillemets simples, ou bash deviendra fou avec les caractères saisis.

EDIT7: Aaaaaaand ... ce n'est plus lisible. Mais je me suis débarrassé de 23 octets de plus, donc c'est bien, je suppose? Je publierai également une version non golfée.

EDIT8: Encore un golf, grâce à @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

EDIT: merci à @DLosc pour l'aide au golf! Géré pour le réduire de 85 octets.

EDIT2: coupez une tonne de wrappers inutiles et laissez-la tomber de 133 octets!

EDIT3: ... et 28 de plus grâce à @ Sp3000 et @orlp dans le chat!

EDIT4: avec l'aide de @orlp & @ Sp3000, tous les décorateurs ont été supprimés et il est désormais plus court de 61 octets.

EDIT5: aidez-moi, je ne peux pas arrêter de jouer au golf .... 9 octets de plus sont partis. Se débarrasser de l'instruction d'impression finale économiserait 7 autres, mais si vous exécutez m () dans une boucle, toute la sortie est sur la même ligne ... est-ce correct?

Voici une version non golfée:

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

L'idée de base est que la liste python fonctionne très bien comme une pile, et en stockant u=k.append, non seulement j'enregistre des caractères, mais je peux également l'utiliser @ucomme décorateur pour pousser des fonctions (plus maintenant!).

Étant donné que le couple de fonctions qui agissent sur les fonctions de n-aire doit pouvoir accepter un nombre arbitraire d'arguments, j'ai dû utiliser *args, ce qui signifiait que mon plan d'origine de suivi f.func_code.co_argcount devait être remplacé par une arité attribut décorateur .

En termes de gestion de programmes infinis, l'interpréteur s'exécute jusqu'à ce qu'il atteigne la profondeur récursive maximale; le gestionnaire RuntimeError en bas le fait sortir tranquillement à ce point, et il imprime ensuite la chaîne de sortie actuelle.

Cas de test:

>>> 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
la source
1
Ma première réaction: @ _ @ Sérieusement, cependant, beau travail - mettre des fonctions réelles sur la pile est une solution vraiment intéressante. Quelques conseils: 1) Les opérateurs ternaires peuvent généralement être raccourcis d'une manière ou d'une autre . 2) Vous pouvez remplacer ['1','0'][...]par juste '10'[...]. 3) Pourquoi x is 0et non x==0(ou x<1)? 4) Ne vous embêtez pas à préciser RuntimeError, exceptça suffira. 5) Puisque vous utilisez Python 2, les tabulations et les espaces comptent comme différents niveaux d'indentation - en gros, mais devraient vous faire économiser environ 25 octets.
DLosc
1
Vous devriez pouvoir le couper x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))- les opérateurs logiques sont toujours en court-circuit, mais utilisent moins de caractères que le ternaire. Ensuite , enregistrez un autre octet en utilisant x.a-1comme condition (0 / false si xest 1, non nulle / true autrement) et l' échange de la « puis » et « autre » expressions: x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y). (Je dois jouer au golf maintenant que vous m'avez dépassé ...; ^))
DLosc
1
Après avoir rencontré un problème similaire avec le mien, je comprends ce qui échoue maintenant - si x.a==1c'est vrai mais x(y)renvoie quelque chose de faux, il essaie également d'évaluer u(...). Mais il semble que vous n'ayez pas besoin de sauvegarder les 3 octets minables qui vous auraient donné! Je concède, monsieur: vous m'avez dépassé.
DLosc
1
Un seul problème: le format de sortie spécifié n'a pas d'espaces - vous pouvez résoudre par différentes stratégies , vous ne savez pas laquelle est la plus courte. Bien sûr, votre programme gère le RuntimeErrortemps que le mien demande simplement à l'utilisateur de rediriger stderr ... nous sommes donc probablement même en jeu. ; ^)
DLosc
1
À quoi *_servent les lambdas?
mbomb007
4

Ghostscript

Pas encore joué au golf, car j'ai encore besoin de travailler sur la fonction d'analyse.

Cette implémentation utilise _et :au lieu de >et /, et elle nécessite que tous les caractères du programme soient séparés par des espaces. En effet >, /les noms ne sont pas valides dans Postscript et les opérateurs ne se délimitent pas d'eux-mêmes, mais cela sera résolu lorsque j'écrirai l'analyseur.

La première partie du code doit être assez transparente, car elle ne fait que répéter les définitions des fonctions opérateur. La magie opère dans la définition de !.

/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

La façon dont !fonctionne est simple: Tout d' abord, il ajoute l' argument xà fen préfixant xau contenu f, en le poussant en arrière sur la pile, et en nommant une copie du résultat fun.

Il enveloppe ensuite la pile entière sous forme de tableau. .runandhideest une extension Ghostscript pour exécuter du code en bac à sable, cachant le contenu du tableau précédent de la procédure sur laquelle il est invoqué. La dictcommande pousse un nouveau dictionnaire sur la pile de dict, réduisant la portée des noms définis dans jusqu'à ce endqu'il revienne. Il remplace également =only(l'opérateur de sortie que j'utilise dans @) par un faux, supprimant la sortie pendant l'essai. stoppedest l'équivalent PostScript de l' tryinstruction trouvée dans d'autres langages et renvoie true si sa procédure a généré une erreur, et false si elle s'est terminée.

Une fois l'exécution d'essai funterminée, le programme restaure la pile d'origine à partir du tableau caché et, s'il est funterminé sans erreur, il l'exécute pour de vrai, en conservant la sortie.

AJMansfield
la source
2

Python3, 685 670 634 633 octets

Je suis presque sûr que c'est la plus longue chose que j'ai jamais jouée. Auparavant, il était quelque peu lisible, mais suivre les conseils de @ sirpercival a éliminé cet inconvénient!

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)

kest la pile, qui contient des fonctions représentées comme des chaînes comme "h(0,0)"(qui est c h ain ). Lorsqu'une fonction est passée en argument à une autre fonction, elle obtientrepr « d et tous les numéros incrémentée: "h('h(1,1)',0)". Une fois que tous les 0s sont remplacés dans une fonction, le tout est passé à eval, appelant ainsi la fonction Python appropriée - dont la plupart sont des fonctions lambda générées à partir de la grande chaîne de la ligne 6 par la execligne 7.

Obtenir plusieurs niveaux de fonctions imbriquées incrémentées, citées et échappées correctement était le plus gros casse-tête. Je pourrais économiser un peu plus sur les opérations regex si je pouvais supposer que l'imbrication de fonctions ne se poursuivra pas plus profondément que 9 niveaux, mais comme indiqué dans les commentaires, ce n'est probablement pas une hypothèse sûre.

Version antérieure du code non golfée:

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

Le seul défaut potentiel de cette implémentation est qu'elle utilise la récursivité, donc les programmes qui devraient être infinis atteignent assez rapidement la profondeur de récursivité maximale. (Vous voudrez probablement rediriger stderr lorsque vous exécutez un programme infini - sinon la trace de la pile submergera la sortie réelle.) À part cela, tout semble fonctionner.

DLosc
la source
Pourriez-vous écrire un programme qui génère le programme ci-dessus puis l'exécute? Vous avez beaucoup de code récurrent qui devrait être compressible comme lambda aet k.pop().
mbomb007
@ mbomb007 ... Je pense que mon cerveau allait exploser. (Mais voir l'édition récente - J'ai rendu la k.pop()situation un peu moins répétitive, de toute façon.)
DLosc
pouvez-vous faire l'astuce exec / translate pour tous ces lambdas? les coller tous dans une même chaîne?
sirpercival
un autre commentaire: Je doute que vous puissiez compter sur l'imbrication de fonctions <= 9 avec ce langage
sirpercival
@sirpercival Oui, je pensais essayer ça. Et non, je suppose que non. : ^ P
DLosc
1

Ceylan, 1167 1057 1031

Je ne suis pas aussi court que les versions python mono-typées ...

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);}

Voici une version formatée (et commentée) du même code (avec les espaces / nouvelles lignes / commentaires, elle devient 4867 octets):

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);
}

Les fonctions clone e, shift t, fork k, call l, say yet chain nutilisent la dernière lettre des noms pour la version abrégée, car cela a donné moins de collisions. (Anecdote: fourchette a été définie ainsi: [Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];- quand je renomme blankà bce cassé, parce que maintenant comparé les paramètres aet la bplace aavec le blanc m'a pris du temps à déboguer..)

La zfonction est partagée car mon IDE exécute ces fonctions - l'outil de ligne de commande peut également exécuter des fonctions non partagées.

Paŭlo Ebermann
la source
Les versions en boucle lanceront en fait un StackOverflowError à un moment donné, se terminant alors. La JVM n'a aucune optimisation de pile de récursivité (ou du moins aucune qui fonctionnerait pour mon programme).
Paŭlo Ebermann