Code Golf: Interprète Turing-Complete le plus court

Question

J'ai juste essayé de créer le plus possible la langue de l'interprète. Souhaitez-vous rejoindre et essayer?

Règles du jeu:

• Vous devez spécifier un langage de programmation que vous êtes à l'interprétation. Si c'est une langue que vous avez inventé, il devrait venir avec une liste de commandes dans les commentaires.
• Votre code doit commencer avec un exemple de programme et de données affecté à votre code et de données variables.
• Votre code devrait prendre fin avec la sortie de votre résultat. Il est préférable qu'il y a des instructions de débogage à chaque étape intermédiaire.
• Votre code doit être exécutable comme l'a écrit.
• Vous pouvez supposer que les données sont des 0 et des 1 (int, string ou boolean, de votre choix) et la sortie d'un seul bit.
• La langue doit être Turing-complet dans le sens que, pour tout algorithme écrit sur un modèle standard, tels que la machine de Turing, chaînes de Markov, ou similaire de votre choix, il est assez évident (ou expliquée) comment écrire un programme qui, après avoir été executred par votre interpréteur exécute l'algorithme.
• La longueur du code est définie comme la longueur du code, après le retrait de l'entrée de la partie, la sortie de la partie, des instructions de débogage et de non-nécessaire d'espaces. Veuillez ajouter le code résultant, et sa longueur à la poste.
• Vous ne pouvez pas utiliser les fonctions qui font de compilateur exécuter du code pour vous, comme eval(), exec() ou similaire.

C'est un Wiki de la Communauté, ce qui signifie que ni la question ni des réponses d'obtenir les points de réputation de votes. Mais la voix de toute façon!

Answer 1

Python, 250 octets.

Celui-ci est plus long que ilya n. s'Python solution, mais la langue est un peu plus facile à saisir. Chaque commande dans cette langue (je l'appelle Kaputt, le mot allemand pour "cassé") est un octet. 6 commandes sont définies:

• 0: Pousser un zéro sur la pile
• 1: Pousser un sur la pile
• I: (si) Pop une valeur hors de la pile (qui doit être égal à zéro ou un). Exécutez le bloc de code suivant (jusqu'à ce que "i") si c'est un; passez le bloc si c'est un zéro.
• i: (endif) se Termine le bloc si et pousse un si le bloc était pas exécuter (parce que le "I" sauté de zéro). Voir ci-dessous pour une explication de ce dernier.
• D: (def) Afche le nom de l'à-être-de la fonction définie en dehors de la pile (voir ci-dessous) et se lie le bloc suivant (jusqu'à ce que "d") à ce nom.
• d: (enddef) se Termine la définition de la fonction.
• Toute autre octet: Vérifier s'il existe une fonction par la présente (un octet; mais voir l'édition ci-dessous) nom. Dans ce cas, exécutez cette fonction; dans le cas contraire, appuyez sur ce octets sur la pile pour une utilisation immédiate en D.

Imbriqués les fi sont légales; fonction imbriquée définitions ne sont pas. Le fait qu' i (endif) pousse un si et seulement si le correspondant si le bloc n'a pas été exécutée permet pour la marche suivante ressemblant à un if/else/endif structure:

# [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...]

Notez que les commentaires, mais les sauts de ligne, les espaces etc. ne sont pas autorisés.

Voici quelques exemples de fonctions communes. Ces programmes utilisent des abréviations ( / ) mentionné ci-dessus.

<D(/)d

définit la fonction < (pop) qui s'affiche une valeur en dehors de la pile sans les utiliser pour quoi que ce soit.

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

définit la fonction & (et) qui apparaît deux valeurs de la pile, et pousse un si les deux valeurs sont proches, pousse un zéro autrement.

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

définit la fonction ~ (swap) qui échange les deux valeurs sur la pile.

RD(R/<)d

définit la fonction R (supprimer) qui supprime récursivement tous ceux à partir du haut de la pile, puis supprime les deux autres valeurs (le haut de, qui devrait être égale à zéro).

La suite de l'interprète de la fonction s'attend à ce que le programme p, qui est une chaîne de caractères (ou de tout autre objet iterable octets), et l'entrée de la pile S, qui est une liste (éventuellement vide) d'octets. Après l'interprète a terme, cette liste contient la sortie de la pile.

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)

Évidemment, il n'y a pas de place pour la vérification des erreurs, de sorte i() attend juridique Kaputt code. Des cas de Test:

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

Amusez-vous bien :-)

Edit: Il n'y a rien d'inhérent à l'interprète que les forces de jetons d'être un octet seulement. Exigeant, ce n'était plus pour des raisons de cohérence avec les commandes intégrées (qui sont d'un octet, parce que l'interprète le plus court). Si vous passez une liste de chaînes de caractères au lieu d'une chaîne, vous pouvez écrire plus lisible Kaputt code comme ceci:

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

Ceci définit une fonction inc qui incrémente le à deux du nombre de bits sur le haut de la pile (LSB sur le dessus).

Test:

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

Appelons multi-octets de la fonction, le nom d'une extension du langage :-)

Answer 2

Programme en Python qui interprète une langue que je viens de créer:

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)

Version optimisée:

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 octets

Mise à jour: je tiens à ajouter que le but de mon programme est de ne pas créer une pratique de la langue, et de ne même pas en quelque sorte le "meilleur" (=='plus court') interprète, mais plutôt de démontrer intéressant de programmation des tours. Par exemple, je me fonde sur l'accès direct aux variables globales par le biais globals(), de sorte que je n'ai même jamais test pour j de commande, économiser de précieux octets :)

Answer 3

#include "/dev/tty"

Answer 4

Assemblez le code ci-dessous en utilisant A86 pour obtenir un interprète BF de 150 octets!

     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
 

Spécifiez un nom de fichier sur la ligne de commande, sans guillemets, en tant que source BF.

Answer 5

Pas le mien, mais jetez un coup d'oeil à l'auto-interprète binaire lambda calcul binaire 210 bits ici .