Majestic Lisp: Implementando let em termos de clausuras

Como dito no post anterior, uma declaração local de variáveis envolve a criação de um contexto léxico onde uma variável seja válida e, portanto, tenha também um "tempo de vida". Na prática, em Majestic Lisp, apenas funções poderiam realizar tal façanha.

> ((fn (y x) (+ x y))
   3 2)
5

É importante lembrar que aqui estamos lidando com um contexto de interpretação. Em outras palavras, estamos deliberadamente ignorando qualquer consideração a respeito de compilação de uma expressão como essa, ou mesmo do let, que pretendemos implementar¹.

Na situação acima, a operação (+ x y) é executada em um contexto onde x e y são bem-definidos. Assim como na lógica de primeira-ordem, fn (em outros Lisps, geralmente representado como lambda, ou pela letra grega homônima) é um quantificador para y e x. Em outras palavras, fn garante que y e x tenham valores atribuídos a si quando o corpo da função anônima for executado.

Em um breve paralelo com a lógica de primeira-ordem, podemos tomar o quantificador existencial como exemplo. Veja que possíveis valores para \(x\) passam a ser bem-definidos quando qualificamos que procuramos \(x\) no conjunto dos números naturais; a semântica é completamente diferente, todavia, o princípio de tornar \(x\) bem-definido é o mesmo.

\[ \exists x \in \mathbb{N}\,:\,(x < 2) \]

Para que a definição de um contexto léxico seja mais palatável que declarar uma função anônima, criamos um macro: uma regra sintática que, antes da interpretação, transforma-se em outra expressão. Vejamos:

> (let ((x 2)
        (y 3))
    (+ x y))
5

A expressão acima expande-se perfeitamente para o exemplo anterior, que envolvia uma função anônima. O algoritmo de expansão de let envolve alguns passos, que enumero e exemplifico a seguir.

1. Separe os pares de definições de variáveis do let em duas listas de símbolos e de valores.

A expressão

((x 2) (y 3))

torna-se:

((y x) (3 2))

O fato de as listas estarem "invertidas" é algo meramente arbitrário, e não influencia no resultado final. Essa inversão, porém, é conveniente, dado que a natureza de construção de uma lista envolve o uso da operação cons que, na prática, adiciona um novo elemento ao início de uma lista².

2. Construa uma função anônima, tal que sua lambda-list³ seja a lista de símbolos anteriormente gerada, e o corpo seja o corpo apresentado em let.

Assim, teremos a função anônima:

(fn (y x) (+ x y))

3. Crie uma lista que, sintaticamente, demonstre a aplicação dessa função anônima à lista de valores anteriormente criada.

Aqui, temos duas opções. Podemos usar a forma especial apply…

(apply (fn (y x) (+ x y))
       (list 2 3))

…ou, já que vamos emitir diretamente uma sintaxe de aplicação, podemos cortar caminho e falar diretamente na aplicação da função sobre apenas os elementos da lista de valores. Com as excusas da má-indentação em prol do didatismo, teremos:

(
  (fn (y x) (+ x y)) ; função aplicada
  3 2                ; argumentos passados
  )

Inserir apenas os elementos de uma lista em outra lista envolve o uso de uma operação comumente chamada splicing, que pode ser efetuada em um quasiquote através de um unquote-splice (que erroneamente chamei no post anterior de unquote-list, mas que já corrigi na especificação de Majestic). unquote-splice geralmente é sinalizado pelo token ,@.

`((fn ,symbol-list ,body) ,@values-list)

Nosso macro já possui muita utilidade e, de fato, foi a implementação que utilizei por um bom tempo em Majestic Lisp.

Só temos um problema: sep-let-pairs precisaria ser definido antes que let seja. Todavia, sep-let-pairs não é uma função-padrão da linguagem Majestic Lisp. Vejamos uma de suas possíveis implementações a seguir.

(defn sep-let-pairs (pairs syms vals)
  (if (nilp pairs)
      (list syms vals)
      (sep-let-pairs
       (cdr pairs)
       (cons (caar pairs) syms)
       (cons (car (cdar pairs))
             vals))))

Ainda que eu pudesse forçar essa função na especificação (ou pelo menos, na implementação da linguagem), pareceria que estamos lidando com uma "ponta solta", um utilitário que "precisa" existir, mas que nunca foi especificado – ainda que a especificação nada tivesse a ver com a implementação.

Eu precisava de uma solução auto-contida, portátil; uma única expressão que pudesse ser copiada e colada, e que definisse let sem nenhuma dependência extra.

Esse foi o post de hoje, que termina com uma solução e, ao mesmo tempo, com uma indagação; esse problema não é de resolução trivial, ao menos não em uma linguagem que possui apenas escopos global e léxico.

Existem soluções plausíveis para esse problema. A primeira das soluções é ter algum tipo de mutabilidade nos escopos léxicos capturados pelas funções, de forma que pudéssemos extender um escopo com uma referência à própria função, e então reinserir esse escopo na própria definição da função.

Mas isso pressupõe algum tipo de mutabilidade nas células cons da linguagem, algo que pretendo adiar por enquanto, já que Majestic ainda não tem mutabilidade explícita. Ademais, isso envolveria uma mutabilidade "por baixo dos panos" que só resolveria o problema para um contexto léxico apenas, fazendo com que a função não possa ter chamada recursiva caso seu nome fosse "trocado" – o que poderia invocar a necessidade de tornar recur um símbolo especial na linguagem, etc…

Uma ideia um pouco mais amigável é introduzir contexto dinâmico na linguagem, algo que não me agrada muito, mas que poderia ser uma solução. Após consultar o contexto léxico por sepfn e não encontrar correspondência, e antes de passar a uma consulta ao contexto global, Majestic poderia realizar uma consulta a um contexto dinâmico, quando existente. Assim, trocaríamos a função que define sepfn localmente por uma estrutura que definisse sepfn dinamicamente; nesse caso, durante a execução de sepfn, esta função conseguiria encontrar a si mesma no contexto onde fora invocada, estando portanto definida dinamicamente.

Ambas as opções são válidas, mas demandam certo cuidado. Common Lisp possui a estrutura flet que pode ser utilizada para definir funções locais (similar a letfn de Majestic Lisp, que comentarei outra hora), mas que sofre do mesmo problema com recursividade; por isso, caso as funções precisem ser recursivas, recomenda-se o uso da estrutura labels. Pela forma como as coisas estão, acredito que revisar implementações dessas construções seja um bom ponto de partida.

Após trocar algumas ideias com alguns amigos, acabei chegando hoje (19/11/2020) a uma solução prática para o problema: letrec, uma forma especial capaz de definir funções que não apenas podem ser recursivas, mas que também podem chamar-se em recursão mútua.

letrec toma seu nome emprestado de dialetos como Scheme e Racket, e funciona como letrec nessas linguagens, ou similar a labels em Common Lisp.

letrec é um special form porque, diferente de let, let*, letfn e letfn*, esta precisa modificar a forma como expressões são interpretadas, mais especificamente modificando o que cada função ali declarada compreende como sendo seu próprio contexto capturado.

Não expliquei aqui nada sobre letfn e letfn* mas, basicamente, são sintaxes especiais de let e let* para que possamos definir funções locais de um jeito mais confortável.

Em termos de implementação, letrec gera cada uma das funções ali descritas, com a captura de escopo esperada. Em seguida, injeta um contexto léxico nas respectivas funções, onde todas elas sejam conhecidas, mantendo ainda o contexto capturado durante a interpretação das mesmas.

Compartilho na íntegra a descrição dessas funções nos apêndices do livro de Majestic Lisp, atualmente em escrita:

• (letrec bindings body)

Define uma lista de funções que serão bem-definidas durante a execução da expressão body.

bindings é uma lista de definições de funções similares a defn, todavia sem o símbolo defn em seu início. letrec segue as mesmas regras sintáticas de letfn e letfn*.

O funcionamento de letrec aproxima-se muito do uso prático de letfn e letfn*. Todavia, letrec permite a declaração de funções mutuamente recursivas. Para tanto, cada função ali declarada não apenas captura o contexto em que letrec é utilizado, como também deve capturar o próprio contexto criado por letrec após a definição de todas as suas funções.

Como esse tipo de operação exige modificar a forma como funções são declaradas – mais precisamente, modificar a forma como ocorre a captura de contexto –, letrec precisa ser uma forma especial, diferente de letfn e let, que podem ser declarados como macros.

> (letrec ((foo ()
             (do (print "Calling foo")
                 (bar)))
           (bar ()
             (do (print "Calling bar")
                 (baz)))
           (baz ()
             (print "Calling baz")))
    (foo))
Calling foo
Calling bar
Calling baz
nil

> (letrec ((iter (x)
             (if (> x 0)
                 (do (print "Recursion #{}" x)
                     (iter (- x 1)))
                 (print "Finished"))))
    (iter 5))
Recursion #5
Recursion #4
Recursion #3
Recursion #2
Recursion #1
Finished
nil