Os programadores do Lisp se gabam de que o Lisp é uma linguagem poderosa que pode ser criada a partir de um conjunto muito pequeno de operações primitivas . Vamos colocar essa idéia em prática jogando golfe em um intérprete para um dialeto chamado tinylisp
.
Especificação de idioma
Nesta especificação, qualquer condição cujo resultado seja descrito como "indefinido" pode fazer qualquer coisa no seu intérprete: travar, falhar silenciosamente, produzir um registro aleatório do gobbld ou funcionar como esperado. Uma implementação de referência no Python 3 está disponível aqui .
Sintaxe
Tokens em tinylisp são (
, )
ou qualquer seqüência de um ou mais imprimíveis caracteres ASCII exceto parênteses ou espaço. (Ou seja, o seguinte regex:. [()]|[^() ]+
) Qualquer token que consiste inteiramente de dígitos é um literal inteiro. (Os zeros à esquerda estão corretos.) Qualquer token que contenha não dígitos é um símbolo, mesmo exemplos com aparência numérica 123abc
, como 3.14
, e -10
. Todo o espaço em branco (incluindo, no mínimo, caracteres ASCII 32 e 10) é ignorado, exceto na medida em que separa os tokens.
Um programa tinylisp consiste em uma série de expressões. Cada expressão é um número inteiro, um símbolo ou uma expressão s (lista). As listas consistem em zero ou mais expressões entre parênteses. Nenhum separador é usado entre os itens. Aqui estão exemplos de expressões:
4
tinylisp!!
()
(c b a)
(q ((1 2)(3 4)))
Expressões que não são bem formadas (em particular, que possuem parênteses não correspondentes) fornecem um comportamento indefinido. (A implementação de referência fecha automaticamente as parênteses abertas e para de analisar as parênteses próximas sem comparação.)
Tipos de dados
Os tipos de dados de tinylisp são números inteiros, símbolos e listas. Funções e macros internas também podem ser consideradas um tipo, embora seu formato de saída seja indefinido. Uma lista pode conter qualquer número de valores de qualquer tipo e pode ser aninhada arbitrariamente profundamente. Os números inteiros devem ser suportados pelo menos entre -2 ^ 31 e 2 ^ 31-1.
A lista vazia - ()
também chamada de zero - e o número inteiro0
são os únicos valores que são considerados logicamente falsos; todos os outros números inteiros, listas não vazias, componentes internos e todos os símbolos são logicamente verdadeiros.
Avaliação
As expressões em um programa são avaliadas em ordem e os resultados de cada um são enviados para o stdout (mais sobre a formatação de saída posteriormente).
- Um literal inteiro é avaliado por si próprio.
- A lista vazia
()
avaliada por si mesma. - Uma lista de um ou mais itens avalia seu primeiro item e o trata como uma função ou macro, chamando-o com os itens restantes como argumentos. Se o item não for uma função / macro, o comportamento será indefinido.
- Um símbolo é avaliado como um nome, fornecendo o valor vinculado a esse nome na função atual. Se o nome não estiver definido na função atual, ele avalia o valor a ele associado no escopo global. Se o nome não estiver definido no escopo atual ou global, o resultado será indefinido (a implementação de referência fornece uma mensagem de erro e retorna nulo).
Funções e macros incorporadas
Existem sete funções integradas no tinylisp. Uma função avalia cada um de seus argumentos antes de aplicar alguma operação a eles e retornar o resultado.
c
- contras [lista de produtos]. Pega dois argumentos, um valor e uma lista, e retorna uma nova lista obtida adicionando o valor na frente da lista.h
- cabeça ( carro , na terminologia Lisp). Pega uma lista e retorna o primeiro item nela, ou nulo se nulo.t
- cauda ( cdr , na terminologia Lisp). Pega uma lista e retorna uma nova lista contendo todos, exceto o primeiro item, ou nulo se for nulo.s
- subtrair. Toma dois números inteiros e retorna o primeiro menos o segundo.l
- menos que. Toma dois números inteiros; retorna 1 se o primeiro for menor que o segundo, 0 caso contrário.e
igual. Leva dois valores do mesmo tipo (ambos os números inteiros, ambas as listas ou ambos os símbolos); retorna 1 se os dois forem iguais (ou idênticos em todos os elementos), 0 caso contrário. O teste dos componentes internos para igualdade não é definido (a implementação de referência funciona como esperado).v
- avaliação. Pega uma lista, número inteiro ou símbolo, representando uma expressão, e a avalia. Por exemplo, fazer(v (q (c a b)))
é o mesmo que fazer(c a b)
;(v 1)
dá1
.
"Valor" aqui inclui qualquer lista, número inteiro, símbolo ou interno, a menos que especificado de outra forma. Se uma função é listada como tendo tipos específicos, passar tipos diferentes é um comportamento indefinido, assim como passar o número errado de argumentos (a implementação de referência geralmente falha).
Existem três macros internas no tinylisp. Uma macro, diferente de uma função, não avalia seus argumentos antes de aplicar operações a eles.
q
- citação. Pega uma expressão e a retorna sem avaliação. Por exemplo, avaliar(1 2 3)
gera um erro porque tenta chamar1
como uma função ou macro, mas(q (1 2 3))
retorna a lista(1 2 3)
. A avaliaçãoa
fornece o valor associado ao nomea
, mas(q a)
o próprio nome.i
- E se. Toma três expressões: uma condição, uma expressão iftrue e uma expressão iffalse. Avalia a condição primeiro. Se o resultado for falso (0
ou nulo), avalia e retorna a expressão iffalse. Caso contrário, avalia e retorna a expressão iftrue. Observe que a expressão que não é retornada nunca é avaliada.d
- def. Pega um símbolo e uma expressão. Avalia a expressão e a vincula ao símbolo especificado tratado como um nome no escopo global e , em seguida, retorna o símbolo. A tentativa de redefinir um nome deve falhar (silenciosamente, com uma mensagem ou travando; a implementação de referência exibe uma mensagem de erro). Nota: não é necessário citar o nome antes de passá-lod
, embora seja necessário citar a expressão se for uma lista ou símbolo que você não deseja avaliar: por exemplo(d x (q (1 2 3)))
,.
Passar o número errado de argumentos para uma macro é um comportamento indefinido (falhas na implementação de referência). Passar algo que não é um símbolo como o primeiro argumento de d
é um comportamento indefinido (a implementação de referência não gera um erro, mas o valor não pode ser referenciado posteriormente).
Funções e macros definidas pelo usuário
A partir dessas dez built-ins, o idioma pode ser estendido através da construção de novas funções e macros. Estes não têm tipo de dados dedicado; são simplesmente listas com uma certa estrutura:
- Uma função é uma lista de dois itens. O primeiro é uma lista de um ou mais nomes de parâmetros ou um único nome que receberá uma lista de todos os argumentos passados para a função (permitindo, assim, funções de variável variável). A segunda é uma expressão que é o corpo da função.
- Uma macro é igual a uma função, exceto que ela contém nada antes do (s) nome (s) do parâmetro, tornando-a uma lista de três itens. (Tentar chamar listas de três itens que não começam com zero é um comportamento indefinido; a implementação de referência ignora o primeiro argumento e os trata como macros também.)
Por exemplo, a seguinte expressão é uma função que adiciona dois números inteiros:
(q List must be quoted to prevent evaluation
(
(x y) Parameter names
(s x (s 0 y)) Expression (in infix, x - (0 - y))
)
)
E uma macro que pega qualquer número de argumentos, avalia e retorna o primeiro:
(q
(
()
args
(v (h args))
)
)
Funções e macros podem ser chamadas diretamente, ligadas a nomes usando d
e passadas para outras funções ou macros.
Como os corpos das funções não são executados no momento da definição, as funções recursivas são facilmente definíveis:
(d len
(q (
(list)
(i list If list is nonempty
(s 1 (s 0 (len (t list)))) 1 - (0 - len(tail(list)))
0 else 0
)
))
)
Observe, porém, que o exposto acima não é uma boa maneira de definir uma função de comprimento porque ela não usa ...
Recursão de chamada de cauda
A recursão de chamada de cauda é um conceito importante no Lisp. Ele implementa certos tipos de recursão como loops, mantendo assim a pilha de chamadas pequena. Seu intérprete tinylisp deve implementar a recursão adequada da chamada de cauda!
- Se a expressão de retorno de uma função ou macro definida pelo usuário for uma chamada para outra função ou macro definida pelo usuário, seu intérprete não deverá usar recursão para avaliar essa chamada. Em vez disso, ele deve substituir a função e os argumentos atuais pela nova função e argumentos e fazer um loop até que a cadeia de chamadas seja resolvida.
- Se a expressão de retorno de uma função ou macro definida pelo usuário for uma chamada para
i
, não avalie imediatamente a ramificação selecionada. Em vez disso, verifique se é uma chamada para outra função ou macro definida pelo usuário. Nesse caso, troque a função e os argumentos como acima. Isso se aplica a ocorrências arbitrariamente profundamente aninhadas dei
.
A recursão de cauda deve funcionar tanto para recursão direta (uma função se chama) quanto recursão indireta (função a
chama função b
que chama [etc] que chama função a
).
Uma função de comprimento recursivo da cauda (com uma função auxiliar len*
):
(d len*
(q (
(list accum)
(i list
(len*
(t list)
(s 1 (s 0 accum))
)
accum
)
))
)
(d len
(q (
(list)
(len* list 0)
))
)
Essa implementação funciona para listas arbitrariamente grandes, limitadas apenas pelo tamanho máximo máximo.
Escopo
Os parâmetros de função são variáveis locais (na verdade constantes, pois não podem ser modificados). Eles estão no escopo enquanto o corpo dessa chamada dessa função está sendo executada e fora do escopo durante todas as chamadas mais profundas e após o retorno da função. Eles podem "ocultar" nomes definidos globalmente, tornando o nome global temporariamente indisponível. Por exemplo, o código a seguir retorna 5, não 41:
(d x 42)
(d f
(q (
(x)
(s x 1)
))
)
(f 6)
No entanto, o código a seguir retorna 41, porque x
no nível de chamada 1 não é acessível no nível de chamada 2:
(d x 42)
(d f
(q (
(x)
(g 15)
))
)
(d g
(q (
(y)
(s x 1)
))
)
(f 6)
Os únicos nomes no escopo a qualquer momento são 1) os nomes locais da função atualmente em execução, se houver, e 2) nomes globais.
Requisitos de envio
Entrada e saída
Seu intérprete pode ler o programa do stdin ou de um arquivo especificado via stdin ou argumento da linha de comando. Após avaliar cada expressão, ele deve gerar o resultado dessa expressão em stdout com uma nova linha à direita.
- Os números inteiros devem ser impressos na representação mais natural da sua linguagem de implementação. Inteiros negativos podem ser gerados, com sinais de menos.
- Os símbolos devem ser impressos como cadeias, sem aspas ou escapes.
- As listas devem ser exibidas com todos os itens separados por espaço e entre parênteses. Um espaço entre parênteses é opcional:
(1 2 3)
e( 1 2 3 )
ambos são formatos aceitáveis. - A saída de funções e macros internas é um comportamento indefinido. (A interpretação de referência os exibe como
<built-in function>
.)
De outros
O intérprete de referência inclui um ambiente REPL e a capacidade de carregar módulos tinylisp de outros arquivos; estes são fornecidos por conveniência e não são necessários para este desafio.
Casos de teste
Os casos de teste são separados em vários grupos para que você possa testar casos mais simples antes de trabalhar em casos mais complexos. No entanto, eles também funcionarão bem se você despejar todos eles em um arquivo juntos. Só não se esqueça de remover os títulos e a saída esperada antes de executá-lo.
Se você implementou corretamente a recursão de chamada de cauda, o caso de teste final (com várias partes) retornará sem causar um estouro de pilha. A implementação de referência calcula em cerca de seis segundos no meu laptop.
fonte
-1
, ainda posso gerar o valor -1 fazendo(s 0 1)
.F
não estão disponíveis na funçãoG
seF
chamadasG
(como no escopo dinâmico), mas também não estão disponíveis na funçãoH
seH
for uma função aninhada definida dentroF
(como no escopo lexical) - consulte o caso de teste 5. Chamando isso de "léxico" "pode ser enganoso.Respostas:
Python 2,
685675660657646642640 bytesLê a entrada de STDIN e grava a saída em STDOUT.
Embora não seja estritamente necessário, o intérprete suporta funções e macros nulas e otimiza as chamadas finais executadas
v
.Explicação
Análise
Para analisar a entrada, primeiro envolvemos cada ocorrência de
(
e)
com espaços e dividimos a sequência resultante em palavras; isso nos dá a lista de tokens. Mantemos uma pilha de expressõesE
, inicialmente vazia. Analisamos os tokens, em ordem:(
, empurramos uma lista vazia no topo da pilha de expressões;)
, exibimos o valor no topo da pilha de expressões e o anexamos à lista que estava anteriormente abaixo na pilha;Se, ao processar um token comum ou depois de exibir uma expressão da pilha devido a
)
, a pilha de expressões estiver vazia, estamos em uma expressão de nível superior e avaliamos o valor que, de outra forma, teríamos acrescentado, usandoV()
e imprima seu resultado, formatado adequadamente usandoF()
.Avaliação
Mantemos o escopo global,
G
, como uma lista de pares de chave / valor. Inicialmente, ele contém apenas as funções internas (mas não as macros, e nãov
, que tratamos como macro), que são implementadas como lambdas.A avaliação acontece dentro
V()
, que pega a expressão para avaliare
e o escopo localL
, que também é uma lista de pares de chave / valor (ao avaliar uma expressão de nível superior, o escopo local está vazio.)V()
viver dentro de um loop infinito, que é como executamos a otimização de chamada de cauda (TCO), conforme explicado mais adiante.Processamos de
e
acordo com seu tipo:se for a lista vazia ou uma string conversível em int, retornamos imediatamente (possivelmente após a conversão em int); de outra forma,
se for uma string, procuramos em um dicionário construído a partir da concatenação dos escopos global e local. Se encontrarmos um valor associado, retornamos; caso contrário,
e
deve ser o nome de uma macro embutido (ieq
,i
,d
ouv
), e devolvê-lo inalterado. Caso contrário, see
não for uma sequência,e
é uma lista (não vazia), ou seja, uma chamada de função. Avaliamos o primeiro elemento da lista, ou seja, a expressão da função, chamandoV()
recursivamente (usando o escopo local atual); nós chamamos o resultadof
. O restante da lista,,A
é a lista de argumentos.f
pode ser apenas uma string; nesse caso, é uma macro interna (ou a funçãov
), um lambda; nesse caso, é uma função incorporada ou uma lista; nesse caso, é uma função ou macro definida pelo usuário.Se
f
for uma string, ou seja, uma macro interna, nós a manipularemos no local. Se for a macroi
ouv
, avaliamos seu primeiro operando e selecionamos o segundo ou terceiro operando de acordo, no caso dei
, ou usamos o resultado do primeiro operando, no caso dev
; em vez de avaliar a expressão selecionada recursivamente, o que derrotaria o TCO, simplesmente substituímose
pela expressão mencionada e pulamos para o início do loop. Sef
for a macrod
, anexamos um par, cujo primeiro elemento é o primeiro operando, e cujo segundo elemento é o resultado da avaliação do segundo operando, no escopo globalG
, e retornamos o primeiro operando. Caso contrário,f
é a macroq
; nesse caso, simplesmente retornamos seu operando diretamente.De maneira oposta, se
f
for um lambda ou uma lista cujo primeiro elemento não é()
, então é uma função não nula, não uma macro; nesse caso, avaliamos seus argumentos, ou seja, os elementos deA
e substituímosA
pelo resultado.Se
f
é um lambda, nós o chamamos, passando os argumentos descompactadosA
e retornando o resultado.Caso contrário,
f
é uma lista, ou seja, uma função ou macro definida pelo usuário; sua lista de parâmetros é o penúltimo elemento e seu corpo é o último elemento. Como no caso das macrosi
ev
, para executar o TCO, não avaliamos o corpo recursivamente, mas substituímose
pelo corpo e continuamos para a próxima iteração. Ao contrárioi
ev
, no entanto, também substituímos o escopo localL
, pelo novo escopo local da função. Se a lista de parâmetros,,P
é, de fato, uma lista, o novo escopo local é construído fechando a lista de parâmetros,,P
com a lista de argumentosA
; caso contrário, estamos lidando com uma função variável, caso em que o novo escopo local possui apenas um elemento, o par(P, A)
.REPL
Se você quiser brincar com ele, aqui está uma versão REPL do intérprete. Ele suporta a redefinição de símbolos e a importação de arquivos por meio dos argumentos da linha de comando ou da
(import <filename>)
macro. Para sair do intérprete, encerre a entrada (geralmente, Ctrl + D ou Ctrl + Z).Mostrar snippet de código
E aqui está uma sessão de exemplo, implementando a classificação de mesclagem:
Mostrar snippet de código
fonte
import zlib;exec(zlib.decompress(your_code_compressed_in_bytes))
A[0]
a alguma variável de um caractere logo após exceto blocoA
está vazio neste caso), e eu não quero "regredir".C (GNU), 1095 bytes
Grande parte da ação ocorre na
v
função gigante . Em vez de implementar explicitamente a recursão de cauda,v
está estruturado para que muitas das chamadas dev
parav
sejam tratadas pela otimização de recursão de cauda do gcc. Não há coleta de lixo.Isso faz uso pesado de extensões do GCC, portanto, ele só pode ser compilado com o gcc (use o comando
gcc -w -Os tl.c
). Ele também usa algumasscanf
extensões que não estavam disponíveis no Windows, que eu costumo usar. A perspectiva de escrever o analisador com o padrãoscanf
era tão terrível que usei uma VM Linux para testar o programa. A análise semscanf
classes de caracteres provavelmente teria adicionado mais de 100 bytes.Semi-ungolfed
fonte
Ceilão, 2422 bytes
(Acho que este é o meu programa de golfe mais longo até agora.)
Eu poderia ter jogado mais alguns bytes, pois usei alguns identificadores de duas letras em alguns lugares, mas fiquei sem letras únicas significativas para eles. Embora, mesmo assim, não pareça muito com o Ceilão ...
Esta é uma implementação orientada a objetos .
Temos uma interface de valor
V
com as classes de implementaçãoL
(lista - apenas um invólucro em torno de um seqüencial de CeilãoV
),S
(invólucro de símbolo em torno de uma string),I
(número inteiro - invólucro em torno de um número inteiro de Ceilão) eB
(função ou macro incorporada, um invólucro em torno de um Função Ceilão).Eu uso a notação de igualdade padrão do Ceilão implementando o
equals
método (e também ohash
atributo, que é realmente necessário apenas para símbolos), e também ostring
atributo padrão para saída.Temos um atributo booleano
b
(que é verdadeiro por padrão, substituídoI
eL
retornar falso para listas vazias) e dois métodosl
(chamada, ou seja, usar esse objeto como uma função) evO
(avaliar uma etapa). Ambos retornam um valor ou um objeto Continuation que permite a avaliação para mais uma etapa evF
(avaliam completamente) os loops até que o resultado não seja mais uma continuação.Uma interface de contexto permite o acesso a variáveis. Existem duas implementações,
G
para o contexto global (que permite adicionar variáveis usando od
builtin) eLC
para um contexto local, que é ativo ao avaliar a expressão de uma função do usuário (ela volta ao contexto global).A avaliação de símbolos acessa o contexto, as listas (se não estiverem vazias) são avaliadas avaliando primeiro seu primeiro elemento e depois chamando seu método de chamada. A chamada é implementada apenas por listas e built-in - ele primeiro avalia o argumento (se uma função, não uma macro) e, em seguida, faz as coisas realmente interessantes - para os built-in exatamente o que é codificado, para listas, ele cria um novo contexto local e retorna um continuação com isso.
Para os componentes internos, usei um truque semelhante ao usado no meu Shift Interpreter , que permite defini-los com os tipos de argumento de que eles precisam, mas chamá-los com uma sequência genérica usando reflexão (os tipos serão verificados no momento da chamada). Isso evita problemas de conversão / asserção de tipo dentro das funções / macros, mas precisa de funções de nível superior para que eu possa obter seus
Function
objetos de metamodelo .A
p
função (análise) divide a cadeia de caracteres em espaços, novas linhas e parênteses, passa pelos tokens e cria listas usando uma pilha e uma lista em execução.O intérprete (no
run
método, que é o ponto de entrada), pega essa lista de expressões (que são apenas valores), avalia cada uma delas e imprime o resultado.Abaixo está uma versão com comentários e executada através de um formatador.
Uma versão anterior antes de começar a jogar golfe (e ainda com alguns mal-entendidos sobre a avaliação de listas) é encontrada no meu repositório do Github , colocarei esta em breve (então, verifique a primeira versão, se quiser a original).
fonte