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.

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.

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

0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010

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

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

Brainf *** (423)

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]

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.

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

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.

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