Comentário de Hofstadter sobre Lisp (1983)
(gist.github.com/jackrusher)- O texto de Douglas Hofstadter, de 1983, apresenta Lisp, então amplamente usado na pesquisa em IA, como uma linguagem elegante e flexível construída sobre um pequeno núcleo matemático
- A interatividade de Lisp aparece no read-eval-print loop, em que o usuário insere uma expressão, o interpretador a lê, avalia e imprime o resultado, e então espera a próxima entrada
- Os objetos de Lisp são organizados em torno de átomos (atoms) e listas (lists), e
nilocupa uma posição excepcional por ser ao mesmo tempo uma lista vazia e um átomo quote,eval,car,cdr,cons,setq,set,lambda,def,condpermitem tratar código e dados com a mesma estrutura de listas, possibilitando construir novas funções de forma gradual- Composição de funções, expressões condicionais, efeitos colaterais e estilo applicative, além do pensamento recursivo, são conectados por exemplos, e a função final
powercom a metáfora do “porpuquine” sugere a recursão à maneira de Lisp
A posição de Lisp na pesquisa em IA
- Em 1983, a IA era um campo de pesquisa que buscava implementar em computadores comportamentos como flexibilidade, senso comum, insight, criatividade, autoconsciência e humor
- Havia cerca de 2 mil pessoas nos Estados Unidos envolvidas profissionalmente com IA, e um número semelhante de pesquisadores no exterior
- Os pesquisadores de IA divergiam bastante sobre o melhor caminho até a IA, mas na escolha de linguagem de programação quase todos usavam Lisp em comum
- O nome Lisp vem de “list processing” e não é exatamente um acrônimo completo
- O apelo de Lisp está em ser uma linguagem “crisp” e “elegant”
- Enquanto muitas linguagens acumulam muitos recursos arbitrários, algumas como Lisp e Algol são organizadas em torno de um núcleo natural, como um ramo da matemática
- O núcleo de Lisp possui uma “crystalline purity”, e essa pureza contribui não só para a estética, mas também para a flexibilidade
Da lógica matemática à linguagem de processamento de listas
- As raízes profundas de Lisp estão na lógica matemática
- Ideias deixadas por Thoralf Skolem, Kurt Godel e Alonzo Church na lógica das décadas de 1920 e 1930 acabaram incorporadas mais tarde ao Lisp
- A programação de computadores propriamente dita começou nos anos 1940, e linguagens de alto nível como Lisp surgiram nos anos 1950
- A primeira linguagem de processamento de listas não foi Lisp, mas IPL (Information Processing Language)
- A IPL foi desenvolvida em meados dos anos 1950 por Herbert Simon, Allen Newell e J. C. Shaw
- John McCarthy criou Lisp entre 1956 e 1958 com base em ideias anteriores, como uma linguagem algébrica de processamento de listas
- Lisp se espalhou rapidamente entre os jovens pesquisadores ao redor do Artificial Intelligence Project do MIT
- Foi implementada no IBM 704 e se difundiu para outros grupos de IA
- Surgiram vários dialetos, mas todos compartilhavam o elegante núcleo central
Lisp interativo e o REPL
- Diferentemente de muitas outras linguagens de alto nível, Lisp era apresentado como uma linguagem interativa
- O usuário executa Lisp no terminal, vê o prompt e digita uma expressão
- Exemplo: ao digitar
(plus 2 2), o resultado4é exibido e um novo prompt aparece
- Exemplo: ao digitar
- O funcionamento central do interpretador Lisp é o read-eval-print loop
- lê a expressão
- avalia a expressão
- imprime um valor apropriado
- sinaliza que está pronto para ler a próxima expressão
- Graças a essa estrutura, o usuário pode inserir um “desejo” de cada vez e verificar imediatamente o resultado
- Em muitas linguagens não interativas, é preciso escrever e executar o programa inteiro antes, o que exige que várias etapas se encaixem perfeitamente e torna a correção de erros mais indireta e custosa
- Lisp permite desenvolvimento e depuração incrementais ao executar uma expressão por vez
Polish notation e parênteses
- As expressões aritméticas em Lisp usam Polish notation, em que o operador vem antes dos operandos
- Exemplo:
(times (plus 6 3) (difference 6 3))é avaliado como 27
- Exemplo:
- Essa notação foi criada antes dos computadores pelo lógico polonês Jan Lukasiewicz
- As expressões em Lisp têm muitos parênteses
- É comum que expressões longas terminem com vários parênteses de fechamento
- No início isso pode parecer pesado, mas, com o costume, a estrutura lógica passa a ficar intuitivamente visível
- Os exemplos são apresentados em forma de pretty printing, usando indentação para revelar a estrutura
Átomos, listas e nil
- O coração de Lisp é a estrutura manipulável, e todo programa funciona criando, modificando e destruindo estruturas
- Há dois tipos de estrutura
- átomo (atom): objeto básico que não se divide mais
- lista (list): estrutura em que vários elementos aparecem em uma ordem específica
- Todo objeto de Lisp é um átomo ou uma lista, com uma única exceção: nil
nilé ao mesmo tempo átomo e listanilrepresenta a lista vazia()eniltêm o mesmo significado, masnilé usado com mais frequência
- Os elementos de uma lista podem ser átomos ou listas
- Exemplo:
(zonk blee strill (croak flonk))é uma lista de quatro elementos, e o último elemento é outra lista de dois elementos
- Exemplo:
- As próprias sentenças de Lisp também são listas
(plus 2 2)também é uma lista- O interpretador Lisp pode manipular listas e átomos para criar e avaliar novos “comandos”
Valor, quote e eval
- Átomos podem ter valores
- Átomos numéricos têm a si mesmos como valor permanente
- O valor de
nilénil ttambém é um átomo especial que tem a si mesmo como valor permanente
setqatribui um valor a um átomo(setq pie 4)faz o valor depieser 4(setq pie (plus 2 2))também faz o valor depieser 4
- O valor de um átomo pode ser não só um número, mas qualquer objeto de Lisp
- pode ser outro átomo ou uma lista
- quote impede a avaliação e faz com que uma lista ou átomo seja tratado literalmente como dado
(setq pie (plus 2 2))avalia a expressão interna e armazena 4 empie(setq pi '(plus 2 2))armazena a própria lista(plus 2 2)empi
evalreavalia uma expressão armazenada como valor- se o valor de
pifor(plus 2 2), então(eval pi)retorna 4 - O interpretador normalmente avalia só uma etapa, mas com
evalé possível pedir uma avaliação adicional
- se o valor de
car, cdr, cons
- Toda lista que não seja
niltem pelo menos um elemento, e o primeiro elemento é chamado de car- o car de
(eval pi)éeval - o car de
(plus 2 2)éplus
- o car de
- O car não precisa ser necessariamente o nome de uma função
- o car de
((1)(2 2) (3 3 3))é(1)
- o car de
- A lista restante, depois de remover o car, é o cdr
- o cdr de
(a b c d)é(b c d) - e depois vai diminuindo para
(c d),(d)enil
- o cdr de
nilnão tem nem car nem cdr, e tentar obter seu car ou cdr deve produzir erroconscria uma nova lista ao adicionar um novo car na frente de uma lista existente- se
xfor(cake cookie), então(cons 'pie x)cria(pie cake cookie) - nesse caso, o
xexistente não é modificado
- se
- A presença ou ausência de quote muda o resultado
- se o valor de
piefor 4, então(cons pie x)retorna(4 cake cookie) (cons 'pie x)coloca na frente o próprio nome do átomopie
- se o valor de
A diferença entre setq e set
- O interpretador Lisp nem sempre avalia seus argumentos, e
setqé uma exceção representativa - O primeiro argumento de
setqnão é avaliado, sendo tratado diretamente como nome de variável- o
qdesetqsignifica quote, isto é, o primeiro argumento é tratado como se estivesse citado
- o
seté parecido comsetq, mas avalia também o primeiro argumento- se o valor de
xfork, então(set x 7)não alterax, mas muda o valor dekpara 7
- se o valor de
- O texto apresenta a seguinte sequência como exemplo
(setq a 'b)(setq b 'c)(setq c 'a)(set a c)(set c b)
- Depois dessa execução, os valores de
a,becpassam a ser todosa setnão é muito usado, e esse tipo de confusão também não é tão comum
Definição de funções e lambda
- Um grande poder da programação está na capacidade de definir novas operações compostas a partir de operações já existentes e repetir isso para construir um repertório cada vez mais complexo
- Em Lisp, novas funções são definidas com base em funções já conhecidas
racé dado como exemplo de função que retorna o último elemento de uma lista- para obter o último elemento, basta inverter a lista e pegar o car
- definição:
(def rac (lambda (lyst) (car (reverse lyst))))
- O
(lyst)apóslambdarepresenta o parâmetro da função, isto é, a variável fictícia - Depois de definida com
def,racpassa a poder ser usada comocar(rac '(your brains))retornabrains
- A função
readers-digest-condensed-versioncria, a partir de uma lista longa, uma lista curta contendo apenas o primeiro e o último elemento- Se o texto inteiro de Finnegans Wake, de James Joyce, for tratado como uma lista de palavras, o exemplo produz
(riverrun the)
- Se o texto inteiro de Finnegans Wake, de James Joyce, for tratado como uma lista de palavras, o exemplo produz
- A operação inversa, chamada
rejoyce, é uma função imaginária que geraria um romance com início e fim fixados por duas palavras, e sua implementação fica como exercício para o leitor
Retorno de valor, efeitos colaterais e estilo applicative
- Algumas pessoas consideram desejáveis e possíveis dois objetivos em Lisp e linguagens relacionadas
- toda sentença retorna um valor
- o efeito de uma sentença ocorre apenas por meio do valor retornado
- Os dialetos de Lisp abordados no texto satisfazem a primeira condição, mas não necessariamente a segunda
(reverse x)não altera o própriox, mas cria e retorna uma nova lista igual ax, porém em ordem invertida- da mesma forma que
(plus 2 2)não muda o valor de 2
- da mesma forma que
constambém retorna uma nova lista sem modificar a lista existente- Já
setqé um exemplo de comando que deixa um efeito colateral, ao mudar o binding de uma variável- efeitos colaterais podem incluir não só mudança de bindings, mas também entrada e saída
- Os defensores da programação applicative preferem apenas o estilo em que funções calculam valores e os passam adiante sem efeitos colaterais
- Nesse estilo, o binding permitido é o lambda binding, que existe apenas temporariamente durante a chamada de função
- quando o cálculo da função termina, o binding da variável fictícia desaparece
- O narrador do texto considera o estilo applicative elegante, mas acha que ele não é prático para construir grandes programas no estilo da IA
- Em programação applicative estrita, até
defse tornaria um caso extremo não permitido, porque armazena definições permanentes de função na memória
Expressão condicional cond e julgamento
- Para que Lisp faça coisas mais interessantes, ele precisa ser capaz de tomar decisões com base no que acontece no processo, e isso exige expressões condicionais
- Exemplo:
(cond ((eq x 1) 'land) ((eq x 2) 'sea))- se
xfor 1, retornaland - se
xfor 2, retornasea - caso contrário, retorna
nil
- se
eqé a função de Lisp que retornatse os valores de dois argumentos forem iguais, enilse forem diferentes- A forma
condcomeça com o nomeconde contém várias cláusulas- cada cláusula é uma lista de dois elementos: uma condição e um resultado
- as condições são testadas em ordem, e quando a primeira retorna um valor diferente de
nil, o resultado correspondente é avaliado e retornado como valor de todo ocond - as cláusulas seguintes não são mais examinadas
- Se a última cláusula usar
tcomo condição, ela funciona como catch-all e pode devolver um resultado padrão em vez denil- o texto mostra um
condque retornaairquando as condições paralandeseafalham
- o texto mostra um
Potência e estrutura recursiva
- No final do texto aparecem definições de função com um padrão evidente
squareék * kcubeék * square(k)4th-powerék * cube(k)- e assim por diante no mesmo esquema
- Surge então a pergunta se seria possível definir de uma vez uma função de dois parâmetros,
power, que abranja todo esse padrão(power 9 3)deve retornar 729(power 7 4)deve retornar 2,401
- Todas as ferramentas necessárias já foram apresentadas ao longo do texto, e o desafio é deixado à engenhosidade do leitor
- A história final do porpuquine glazunkiano trata a estrutura recursiva como uma fábula
- os espinhos do porpuquine são porpuquines menores
- em Outer Glazunkia sempre há 9 espinhos, e em Inner Glazunkia sempre há 7
- um porpuquine de 0 polegadas não tem espinhos, interrompendo o regresso infinito
- O “buying power” ou “power” desse animal se relaciona com o número de pequenos narizes de porpuquine de 0 polegadas contidos nele, encerrando o texto com uma metáfora ligada ao problema de
powerapresentado antes
Contexto da republicação do texto original
- No começo do Gist, é explicado que este texto é uma introdução ao Lisp escrita por Douglas Hofstadter, encontrada em uma edição antiga da Scientific American de meados dos anos 1980
- Os exemplos ainda podem ser executados no Emacs se alguns aliases forem configurados
plus→+quotient→/times→*difference→-
- No final, diz-se que, se você gostou da forma peculiar como Hofstadter apresenta Lisp, poderá encontrar mais textos semelhantes em seu livro Metamagical Themas
1 comentários
Comentários do Hacker News
Fiquei confuso com os nomes das funções
"oval"e"snot"no exemplo, mas alguns segundos depois percebi que eram erros de digitação de"eval"e"snoc", respectivamenteO código original deveria ser lido como
(cond ((eq (eval pi) pie) (eval (snoc pie pi))) (t (eval (snoc (rac pi) pi))))Baixei o artigo original da Scientific American em https://www.jstor.org/stable/24968822 para conferir, e de fato
oval/snoteram erros de digitação deeval/snoc"oval"e"snot"são mesmo erros de digitação de"eval"e"snoc"E
snocparece serconsinvertido;rac,carinvertidoEste texto mostra novamente que uma causa central da baixa popularidade do Lisp foi a forma como o Lisp era explicado
Esses textos sobre Lisp não me ensinaram nada que eu pudesse usar de fato quando eu era criança, nem mostraram o quanto alguma tarefa X ficava mais fácil em comparação com assembly/C/Pascal etc.
Hoje, eu teria mostrado algo como: “um corretor ortográfico sob medida que levou 7 meses em assembly? Em Lisp, num microcomputador com memória alternada por bancos, isso é quase trivial, e até a coleta de lixo pode ser determinística numa CPU péssima”
Inúmeros textos e livros didáticos sobre Lisp só repetiam listas, recursão e IA, sem mostrar como fazer coisas úteis, então parece uma pena o tempo gasto programando como se fosse com pinças, grãos de arroz e cola
A primeira revista Byte que vi quando era criança trazia código em Lisp para diferenciação simbólica e simplificação algébrica; era difícil de acompanhar, mas havia algo atraente ali
Não teria sido mais fácil em Basic, e mais tarde percebi que aquele código nem era tão excelente assim, mas só depois de conhecer XLisp no PC e SICP no fim dos anos 80 é que realmente me apaixonei por Lisp
Gosto muito da escrita de Hofstadter. Ele captura bem a sensação que tive ao descobrir Lisp
Eu era uma criança aprendendo programação nos anos 80 e, no ensino médio e no começo da faculdade, já tinha mexido um pouco com BASIC, Fortran, Pascal e COBOL; havia diferenças, mas fundamentalmente havia pontos em comum
Então a primeira disciplina de ciência da computação na UC Berkeley foi ministrada em Scheme, um dialeto de Lisp, e foi um choque completo
Como diz Hofstadter, parecia o mais próximo da matemática; lembrava muito aulas de teoria matemática, e foi a primeira linguagem bonita que descobri
Gostei especialmente da citação: “Lisp e Algol são construídos em torno de um núcleo tão natural quanto um ramo da matemática. O núcleo do Lisp tem uma pureza cristalina que não apenas apela ao senso estético, mas também o torna muito mais flexível do que a maioria das linguagens”
Mesmo do ponto de vista de alguém que queria se tornar topólogo algébrico, Scheme está mais para uma expressão elegante e mínima de um estilo de programação disseminado em linguagens com tipagem dinâmica e coleta de lixo
Ele parece “teoria” no sentido de parecer completo, e porque, se você pensar na forma de resolver um problema em Scheme e depois portar para outra linguagem de tipagem dinâmica, ainda pode chegar a uma solução elegante
Scheme era uma linguagem simplificada e organizada em relação ao Lisp tradicional da época, com aspectos como escopo léxico e um único namespace para funções e variáveis
Em 1983, cerca de 20 anos depois do início dessa área, o texto fala de IA para programar computadores com “flexibilidade, bom senso, insight, criatividade, autoconsciência e humor”
É bem divertido, porque essa lista parece uma lista das coisas em que LLMs realmente são ruins
Ainda assim, pelo menos houve um progresso diferente de zero nessa direção
Talvez eu sinta que demonstrem até mais, mas, quando digo isso, até para mim soa meio estranho
Mesmo que muita coisa ainda não tenha se traduzido em resultados, é uma leitura interessante
Os dois textos complementares mencionados junto com este estão nos capítulos 17 a 19 do livro Metamagical Themas, de Hofstadter, junto com outros textos da mesma coluna da Scientific American
[0]: https://www.goodreads.com/book/show/181239.Metamagical_Thema...
O título do livro vem do nome da coluna, que era um anagrama de “Mathematical Games”, a coluna que Martin Gardner escrevia na Scientific American, e que Hofstadter assumiu
O texto diz que aplicar
caroucdranildeveria gerar um erro, como uma divisão por zero, mas em muitos Lisps modernos isso já não é mais assimNo Lisp original definido por John McCarthy,
CAReCDRnão eram definidos paraNIL: <https://dl.acm.org/doi/pdf/10.1145/367177.367199>Mas Common Lisp e Emacs Lisp definem
(car nil)e(cdr nil)comonil: <https://www.lispworks.com/documentation/HyperSpec/Body/f_car...>, <https://www.gnu.org/software/emacs/manual/html_node/elisp/Li...>Em
LISP 2156,(status lispversion)retornou/2156, e(car nil)e(cdr nil)retornaram ambosNILcarecdrtenham sido centrais no nascimento de uma linguagem projetada matematicamenteOs operadores mais básicos e famosos de um “List Processor” foram feitos para operar não sobre listas, mas sobre cons, um elemento específico da representação de máquina que o Lisp usa para construir estruturas de dados
Um cons nem sempre é interpretado como lista, e uma lista muito importante, o caso base de funções recursivas sobre listas, sequer é representada por um cons
Mesmo 60 anos depois, a maioria dos programas Lisp está cheia de operações com cons, e talvez um nome mais preciso tivesse sido “Cons Processor”
Isso lembra que o Lisp nasceu em uma época em que linguagem e implementação precisavam se encaixar, o que torna ainda mais impressionante a conquista de fundamentar uma linguagem de computador na lógica matemática
CARouCDRdenilé um errocar/cdrdenilé um erro, então para um iniciante como eu o código parece bastante pouco ergonômicoAinda assim, prefiro Guile Scheme ao Common Lisp, então é uma pena
nilnão gera erro e simplesmente retornanilde novoSQL também me vem à mente e, pessoalmente, acho uma escolha ruim; se não houver outro nome, eu gostaria de chamar isso de “bleeding nils/NULLs”
É ainda pior se
nilnão for igual afalseem comparações booleanasEm Ruby e Elixir,
nilé tratado comofalse, e Elixir oferece separadamenteand, que aceita apenas booleanos puros, e&&, que tratanilcomofalseEsse design pode deixar o código mais limpo no começo, mas um
nilmal tratado que na verdade é um erro pode aparecer em uma parte completamente diferente, várias pilhas de chamadas depois, tornando a depuração muito mais difícilEu já conhecia as informações sobre Lisp desse texto, mas ainda assim foi uma leitura divertida. Hofstadter tem um jeito de escrever realmente encantador
Em especial, achei engraçada a piada de criar
rejoyce, a operação inversa dereaders-digest-condensed-version, de modo que, ao executar(rejoyce 'Stately 'Yes), uma fada do Lisp geraria desde o início todo o Ulysses como James Joyce poderia ter escritoDemorou um pouco, mas no fim chegamos a esse ponto; e, embora a IA de 2024 não seja exatamente igual ao que ele imaginou em 1983, reproduzir texto a partir de uma semente curta é uma tarefa que combina muito bem com a IA de hoje
Vejo que Lisp ainda permanece como uma das principais linguagens capazes de expressar o conceito de loop estranho tratado por Hofstadter
Lisp não é a única linguagem homoicônica, mas está entre as maiores, dentre as linguagens que as pessoas realmente sabem usar, em que
evalnão recebe uma string a ser parseadaNão gosto quando as pessoas equiparam Lisp a toda a programação funcional
Não é que eu não goste de programação funcional, mas o caráter simbólico de Lisp é muito mais interessante, e acho infinitamente divertido que também seja muito fácil criar código guiado por seções
(go tag), em estilo de programação com GOTORecursos de metaprogramação usando XSLT e XML para gerar XSLT, em vez de escrever diretamente código repetitivo, foram bastante usados
Só que a sintaxe era um problema ainda maior do que a sintaxe de Lisp
Não é fácil criar uma linguagem com uma sintaxe boa para uso cotidiano e, ao mesmo tempo, que não seja trabalhosa de manipular como árvore de sintaxe abstrata; Lisp é um dos poucos exemplos relativamente bem-sucedidos
functoolsdo Python: https://docs.python.org/3/library/functools.htmlEstou criando AGI simbólica sem Lisp e gostaria de ouvir pistas de especialistas
Pelo que entendi, os recursos do lado de Python são funções que aplicam outras funções a iteráveis, como
filter(),map()ereduce(); wrappers que roteiam chamadas, como@singledispatch; funções que oferecem conveniência de controle de fluxo ou desempenho, como@cacheepartial(); e algo comowraps(), que encapsula funções arbitrariamenteA maioria disso parece ser uma conveniência para chamar funções de maneiras incomuns, e não parece chegar ao nível dos elogios a Lisp que tratam “introspecção” como uma preocupação de primeira classe
Quero saber o que Lisp realmente oferece que não está nesses recursos
Eles usam Lisp como meio de transmitir conceitos, e esses conceitos geralmente giram em torno de recursão funcional
Scheme e a cultura ao seu redor também contribuem para isso
Scheme não é apenas uma linguagem funcional, mas enfatiza programação pura mais do que as famílias Lisp anteriores; a linguagem básica oferece estruturas de recursão de cauda em vez de estruturas de repetição e exige que as implementações façam otimização de chamadas de cauda
Em Common Lisp, se você definir
defaliascomo macro, dá para usá-lo como odefaliasdo Emacs: https://stackoverflow.com/questions/24252539/defining-aliase...Gostei do texto de Hofstadter sobre Lisp em Metamagical Themas, e adaptei e organizei o código do último artigo dessa série para Clojure para um grupo de estudos no trabalho
[1] http://johnj.com/posts/oodles/