Intérprete de auto-interpretação

25

Com base em um comentário de George Edison a essa pergunta , escreva o menor intérprete de auto-interpretação.

  • Você pode usar o idioma de sua escolha.
  • Idiomas vazios não contam. Seu programa deve ter pelo menos dois caracteres.
  • O programa não precisa interpretar o idioma inteiro , apenas um subconjunto completo de recursos de idioma do Turing (que contém o intérprete).
  • Quines não contam.
  • Não use a função interna do seu idioma evalou equivalente. O mesmo vale para applyetc.
Hoa Long Tam
fonte
11
(Hmm .. eu deveria fazer alguma coisa com /usr/bin/cat) e quanto à integridade de Turing?
Ming-Tang
@ SHiNKiROU: Obrigado, eu não pensei nisso como um teste. Atualizada.
Hoa Long Tam
Relacionado: Idioma com o menor intérprete escrito em si próprio no Stack Overflow, embora sejam poucas (apenas uma?) Respostas que realmente cumpram as regras fornecidas aqui.
dmckee
11
Temos que reescrever o analisador sexp do Scheme ou podemos considerar que o idioma do host está ok?
JB
@JB: Os utilitários de processamento de strings do idioma são bons, incluindo o sexpanalisador.
Hoa Long Tam

Respostas:

19

CI - 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: Empurre mapeamentos simples de caractere para instrução e dobre-os. Isso reduz pela metade o tamanho do código por caso (há 18 casos), mas custa 30 caracteres para fazer a dobra.

Esta é outra das minhas linguagens construídas (intérprete base hospedado no Gist ). É único, pois o idioma reifica fragmentos de código. Ou seja, seqüências de instruções nessa linguagem baseada em pilha são usadas para o mesmo efeito que estruturas de dados ou fechamentos em outros idiomas:

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.

O intérprete cria um fragmento de código de todo o programa antes de executá-lo, para que também possa ser considerado um compilador. Por esse motivo , empilhar o intérprete não resulta em sobrecarga exponencial do tempo de execução.

O intérprete deriva todos os seus operadores diretamente do intérprete host. No entanto, ele faz a análise por si só, portanto a maioria do código é apenas sequências que traduzem caracteres em seus respectivos literais de código. Isso não é o mesmo que usar eval, mas revela como qualquer implementação de linguagem de programação depende da semântica de sua linguagem / arquitetura host.


Referência de idioma:

Obtenha o intérprete aqui

Blocos

  • ( ... )

    Crie um "bloco", que é efetivamente uma lista de instruções sem contexto. Internamente, pode até ser código de máquina.

  • quadra $

    Ligue para um bloco. O receptor recebe a pilha global, que inclui o bloco que está sendo chamado.

  • valor ^

    Aumente um valor. Ou seja, transforme-o em um bloco que empurra esse valor.

    Exemplo :

       1 ^
    == (1)
    
  • block1 block2 &

    Una dois blocos, formando um que executa ambos em sequência.

    Exemplo :

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

Manipulação de pilha

  • n c

    Copie o enésimo valor da pilha.

    Exemplo :

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

    Arranque o enésimo valor da pilha (remova-o e coloque-o na frente).

    Exemplo :

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

    Solte n valores da pilha. 0dé um não-op.

    Exemplo :

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

Operadores relacionais

  • ab (on_true) (on_false) =

    Teste se a é igual a b. Consuma tudo, exceto o primeiro argumento, e chame on_true ou on_false. Se um argumento é zero e o outro é qualquer outro tipo, o resultado será falso. Caso contrário, aeb devem ser inteiros.

    Exemplo :

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

    Teste se a é menor que b. aeb devem ser inteiros.

    Exemplo :

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

    Teste se a é maior que b. aeb devem ser inteiros.

    Exemplo :

       3 5 (1d 5) () >
    == 3
    
  • um lo hi (on_true) (on_false) ~

    Teste se lo <= a <= oi. a, lo e hi devem ser números inteiros.

    Exemplo :

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

I / O

  • c .

    Coloque o caractere c (consumindo-o da pilha).

  • ,

    Pegue um personagem e empurre-o para a pilha. Se o final do arquivo foi atingido, -1 é pressionado.

  • c !

    Desmarque um personagem. Assim como ungetc em C, apenas uma resposta é permitida.

Literais inteiros

  • 'c

    Empurre o caractere c.

  • [0-9] +

    Empurre um número inteiro decimal.

Aritmética

  • ab +
  • ab -
  • ab *

    Adicione / subtraia / multiplique dois números.

    Exemplo :

       3 5 + 7 3 + *
    == 80
    
  • ab /

  • ab %

    Divisão e módulo. Ao contrário de C, eles se aproximam do infinito negativo.

Diversos

  • #comentário de código

    O #personagem comenta tudo até o final da linha.

  • )

    Usado para finalizar blocos. Também pode ser usado para finalizar o programa inteiro.

  • Todos os outros caracteres são ignorados.

Joey Adams
fonte
24

Cálculo binário lambda, 232 bits (29 bytes)

0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010

Veja http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding para obter detalhes

John Tromp
fonte
2
Por que essa não é a resposta aceita: D: BLC é incrível!
cat
Você pode explicar tudo?
PyRulez
11
Infelizmente, a Wikipedia removeu a página Binary Lambda Calculus. Minha página tromp.github.io/cl/cl.html se vincula a uma cópia preservada e a um artigo que escrevi explicando o funcionamento do intérprete.
John Tromp
13

Não posso me responsabilizar por este , mas pensei em compartilhar este incrível:

Brainf *** (423)

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]
Peter Olson
fonte
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!;

O BlockScript é uma linguagem trivial baseada em pilha de espaguetes que criei especificamente para esse desafio. O intérprete de base é blockscript.c .

Programa de amostra (imprime os 15 primeiros números de Fibonacci):

{[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!
;

O intérprete lê o código fonte e a entrada do programa a partir da entrada padrão, nessa ordem. Isso significa que, para executar um intérprete dentro de um intérprete, copie e cole:

# 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!
;

Como o filme Inception , você praticamente não pode ir além de três níveis. Não é uma questão de tempo, mas de espaço. O BlockScript vaza memória profusamente, e isso tem a ver com a forma como a própria linguagem é projetada.


Referência de idioma:

Obtenha o intérprete aqui

No BlockScript, a "pilha" não é uma matriz que é substituída por operações subseqüentes como você pode estar acostumado. Na verdade, é implementado como uma lista vinculada imutável e uma pilha persiste durante o programa. Além disso, nenhum operador (exceto @) remove valores da pilha. No entanto, as modificações da pilha afetam apenas o bloco em que ocorrem.

Seleção de valor

  • a através z

    Busque o item 0-25º da pilha e empurre-o para a pilha. arefere-se ao cabeçalho, ou item empurrado mais recentemente, da pilha.

  • A através Z

    Busque o item 0-25º do quadro atual e empurre-o para a pilha.

  • [

    Abra um "quadro" para selecionar itens da referência da pilha (veja abaixo) no cabeçalho da pilha. [não exige uma correspondência ], mas os quadros têm escopo lexicamente. No BlockScript, "escopo" é determinado por chaves ( {... }) que formam blocos. Assim, abrir um quadro dentro de um bloco não terá efeito no código fora do bloco.

  • ]

    Feche o quadro atual, retornando ao quadro anterior (se houver).

Blocos

  • { ... }

    Crie um "bloco" e empurre-o para a pilha. Dentro de um bloco, a pilha começará do que era antes do bloco, exceto que a pilha do chamador será empurrada para cima. As pilhas são persistentes e imutáveis ​​no BlockScript, portanto, os blocos são encerramentos. O idioma {[significa abrir um bloco e, em seguida, abrir um quadro para começar a selecionar argumentos (usando Aatravés Z). O valor de retorno de um bloco é o cabeçalho da pilha quando }é atingido.

    Exemplo:

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

    Isso imprime 123BCD123DCB123BCD123DCB…. As letras minúsculas se referem aos valores da pilha, enquanto as letras maiúsculas se referem aos argumentos (porque o quadro está definido como a pilha do chamador). A!pega o chefe do chamador (que é garantidamente o bloco que está sendo chamado) e o chama. Se você está se perguntando por que ele reverte BCDtodas as vezes, é porque B. C. D.envia esses argumentos na ordem inversa antes do bloco se chamar.

  • !

    Ligue para um bloco. Empurre o valor de retorno para a pilha.

Referências de pilha

  • &

    Crie uma referência de pilha e empurre-a para a pilha. Pense nisso como "superconvenientes", pois efetivamente pega todos os itens da pilha e forma uma "tupla". O idioma &[significa que tudo a, b, creferidas antes de agora pode ser acessado com A, B, C(para o restante do bloco ou até que ]seja encontrado).

    Em parte porque &captura mais valores do que normalmente precisa, o BlockScript vaza memória por design.

  • @

    Alterne para a pilha apontada pela referência da pilha a. Esse operador é um pouco estranho, mas o auto-intérprete BlockScript o usa algumas vezes para evitar ter que empurrar os mesmos argumentos duas vezes. Os efeitos de @(ou qualquer operação de pilha, nesse caso) são limitados ao bloco em que é invocado. Além disso, o quadro não é afetado @, portanto, o quadro pode ser usado para obter os valores necessários após a troca de pilhas.

Expressão condicional

  • ? <em verdadeiro> : <em falso>

    Expressão condicional, assim como o operador ternário em C. Ou seja, se afor "true" (ou seja, não for igual ao número inteiro zero), faça <em true> , caso contrário <em false> .

I / O

Nota: A entrada e a saída são feitas em UTF-8. Um "caractere" é um número inteiro correspondente a um índice Unicode.

  • ,

    Obtenha o próximo caractere de entrada e empurre-o para a pilha. Se o final da entrada for alcançado, pressione -1 em vez disso.

  • .

    Coloque o caractere na cabeça da pilha.

Literais de número inteiro / caractere

Nota: Inteiros e caracteres são a mesma coisa no BlockScript.

  • 'c

    Empurre o caractere c.

  • [0-9] +

    Empurre um número inteiro decimal.

Aritmética

Esses operadores trabalham apenas em valores inteiros.

  • +Calcule b+ a(pressionando o resultado, mas não descartando nenhum valor).
  • -Computar b- a.
  • *Computar b* a.
  • /Computar b/ a(divisão inteira; arredonda para o infinito negativo).
  • %Calcule b% a(módulo inteiro; arredonda para o infinito negativo).

Operadores relacionais

Esses operadores trabalham apenas em valores inteiros.

  • <Se bfor menor que a, pressione 1, depois pressione 0.
  • >
  • =

Diversos

  • # Comentar até o final da linha
  • O programa deve terminar com ;
  • Todos os outros caracteres são ignorados.
Joey Adams
fonte
2
Cristo. Gostaria de compartilhar as especificações como você fez para a CI?
Casey #
@ Casey: adicionada uma referência.
Joey Adams
11
Você estaria interessado em saber que está sonhando? ... No nível 4.
Mateen Ulhaq
3

Zozotez LISP : 414

linefeeds adicionados para obter um bom bloco não são necessários e não são contados.

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

Em teoria, ele deve ser capaz de rodar sozinho, mas como o intérprete original é um binário do BrainFuck e é um intérprete, só consegui testar cada parte. Quando atribuída a si mesma e a uma expressão simples (p p), acho que precisa de mais tempo do que os 40 minutos que esperei até agora e estou usando o meu rápido jitbfpara executá-lo, que (mis) usa o Perl Inline-C para executar o código C em tempo real.

É impossível implementar o Zozotez inteiro no Zozotez, pois ele não tem meios de alterar contras e :(setq / define) precisa disso para atualizar as ligações. Também não implementei argumentos explícitos de start / progn ou & rest, macros e argumentos especiais de impressão, pois não o usei no intérprete. Incluí p(imprimi) mesmo que não o use, para que os programas precisem imprimir explicitamente seus cálculos, assim como o intérprete original.

O mesmo não destruído:

;; 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)))
Sylwester
fonte
0

CHIQRSX9 + (provavelmente não concorrente), 2 bytes

+I

Não há como escrever um intérprete de auto-interpretação nesta linguagem baseada no HQ9 + sem o uso I, que executa um intérprete interno que processa STDIN.

user8397947
fonte
11
Em nenhum lugar das regras diz que os auto-intérpretes incorporados são proibidos. Diz para eval, que é para expressões, não para programas.
Erik the Outgolfer,
Como alguém calcula números primos nesse idioma?
pppery
O @ppperry Xdeve tornar a linguagem Turing completa (portanto, capaz de calcular primos) de uma maneira dependente da implementação.
user8397947
De acordo com a página Esolang, o Xcomando do interpretador Perl aleatoriamente perturba o programa e o executa, o que significa que não se pode usar senão o comando para calcular deterministicamente números primos. Você pode me dar um exemplo de intérprete que permita usar Xda maneira especificada?
pppery
@ppperry Aparentemente, o intérprete escrito em Perl é o único intérprete, então não. Além disso, e se houver um programa que calcula números primos quando "randomizados" com um valor específico?
user8397947
0

Sistema de arquivos simultâneo Befunge 98 - 53 \ 18 bytes (quase certamente trapaceando)

Intérprete completo de 53 bytes sem restrições (embora eu não tenha testado interações de tempo complicadas que envolvem divisão e quebra de IP):

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

Lê a entrada de um arquivo chamado ae a executa. Não está especificado nas regras que não podemos usar código auto-modificável.

Intérprete de 18 bytes que não permite quebra automática (o movimento do IP de uma borda do código e a partir da borda oposta):

]210'ai@
t
><
pppery
fonte