Majestic Lisp: Interpretando Majestic com Majestic

Aqui, realizaremos a avaliação da expressão exp sob o contexto env. O contexto é algo como uma tabela de relações \(\textrm{símbolo}\, \times\, \textrm{valor}\). Logo mais veremos como esta tabela pode ser criada usando apenas S-expressions.

(def eval.
  (fn (exp env)
    (cond

Alguns tipos de S-expressions, quando interpretadas, resultam em si mesmas. Chamamos estas S-expressions de expressões auto-interpretáveis.

As principais expressões auto-interpretáveis são números, strings e funções primitivas. Propositalmente, utilizaremos as noções de como estes elementos são programados no próprio interpretador de Majestic, e não tocaremos em suas definições.

((numberp exp) exp)
((stringp exp) exp)
((primitivep exp) exp)

Se a expressão em questão for um símbolo, então retornaremos o valor que estiver associado ao símbolo. Não vamos nos preocupar agora com o local onde este símbolo poderia estar definido; este é um problema da função lookup., a ser vista posteriormente.

Há também a possibilidade de um símbolo estar indefinido. Veremos melhor esta possibilidade mais tarde.

((symbolp exp)
 (lookup. exp env))

Se a expressão for uma lista adequada cujo primeiro elemento seja o símbolo quote, então sua interpretação é o segundo símbolo. Isto introduz a ideia de quoting, crucial para a maioria dos Lisps. Utilizando-a, podemos garantir que certas S-expressions sejam tratadas como dados que não serão interpretados imediatamente.

Veja que, geralmente, denota-se uma expressão quotada como 'x. Esta notação é algo que tem muito mais a ver com o leitor de expressões da linguagem que com a forma como a função eval. processa essa expressão. Portanto, para nossa conveniência, é muito mais interessante pensar que o leitor transformará essa expressão em (quote x).

((eq (first exp) 'quote)
 (second exp))

A próxima possibilidade é uma forma que indique uma função anônima. Precisamos criar algum tipo de objeto que descreva a função, que trata-se basicamente de tomar a lista de parâmetros e o corpo da mesma, bem como capturar o contexto onde a função está sendo interpretada.

Para nossa conveniência, criaremos aqui uma representação interna em lista, começada com o símbolo closure. O segundo elemento dessa lista será uma sublista contendo parâmetros e corpo da função, e o terceiro será o contexto no qual esta função está sendo interpretada – que aqui, está contido na variável env.

((eq (first exp) 'fn)
 (list 'closure (rest exp) env))

Outra possibilidade é a condicional cond. Originalmente, Majestic implementa cond como um macro que utiliza if por baixo dos panos. Aqui faremos o contrário e priorizaremos cond.

cond avalia consecutivamente pares de cláusulas em formato de lista. Cada par é composto de um predicado e uma expressão de consequência. Se a avaliação do predicado resultar em um valor diferente do símbolo nil, será retornada a avaliação da expressão a ele associada. Se nenhum predicado obedecer a essa regra, será retornado o símbolo nil em si.

Para que tenhamos o efeito desejado, considere que as fórmulas envolvendo \(\lor\) abaixo representadas sejam interpretadas sequencialmente, e não paralelamente.

Para simplificar o processo, vamos fazer com que o corpo de cond seja despachado para a função evcond, que realizará a interpretação adequada dele sob o contexto env.

((eq (first exp) 'cond)
 (evcond. (rest exp) env))

Quando estamos lidando com uma expressão iniciada por def, esta será uma forma de definir, globalmente, um valor \(y\) associado a um certo símbolo \(x\).

Nesse caso, def realiza uma alteração em um contexto global, que estará acessível em qualquer situação do programa, com uma única ressalva: caso estejamos no escopo de uma função, e esta função possuir o símbolo \(x\) previamente definido como um de seus parâmetros, então uma consulta a este mesmo símbolo \(x\) retornará o valor passado por parâmetro à função em questão, e não o valor definido através de def.

((eq (first exp) 'def)
 (defglobal. (second exp) (third exp) env))

Até agora, tudo o que foi apresentado está relacionado ao que chamamos de formas especiais. Estas formas são formas específicas de interpretar certas S-expressions, que não estão relacionadas ao processo comum de interpretação.

É possível adicionar mais formas especiais que seriam mais regras alternativas de interpretação de expressões, porém precisamos tomar cuidado para que essas regras extras não sejam excessivas.

Caso nenhuma das formas especiais se enquadre, entramos neste caso comum de interpretação, que chamo livremente de interpretação por ordem aplicativa.

A ideia é extremamente simples: primeiro, interpretamos a função f em relação ao contexto env, o que nos renderá uma função primitiva ou uma closure. Em seguida, interpretamos a lista de argumentos da função em relação ao mesmo contexto. Finalmente, aplicamos a função interpretada aos argumentos interpretados.

(t (apply. (eval. (first exp) env)
           (evlist. (rest exp) env))))))

Note que temos aí um processo recursivo e que não deixamos claro como se dá o processo de aplicação. Neste último caso, isso é proposital, pois delegaremos a ideia de aplicação de uma função à função apply, que abordaremos agora.

apply. recebe uma certa função proc e uma lista de argumentos args como parâmetro. Vamos assumir que os argumentos já tenham passado pelo processo de interpretação do passo anterior, não precisando portanto de serem interpretados novamente antes de seu uso.

(def apply.
  (fn (proc args)
    (cond

O primeiro passo é avaliar se o procedimento em questão é uma função primitiva. Em Majestic, isso possui um significado muito específico, mas aqui poderíamos ter, por exemplo, uma verificação para saber se proc é código de máquina, por exemplo.

O interpretador metacircular não lida com este tipo de caso, então delegamo-no para outros lugares. Em especial, utilizaremos a forma especial apply de Majestic para aplicar a função primitiva.

Note que essa forma especial apply não é a função apply., e sim algo externo ao qual estamos recorrendo, algo embutido no interpretador original de Majestic Lisp. Isso deixa bem claro o teor da especificação semântica no interpretador metacircular, pois escolhemos deliberadamente não esclarecer o que acontece aqui, e sim delegar a um recurso subjacente da linguagem utilizada na programação.

((primitivep proc) (apply proc args))

Caso o procedimento em questão seja uma função definida pelo usuário – uma clausura –, então teremos uma forma bem explícita de lidar com isso.

Aplicar uma função nada mais será que:

1. Ligar os símbolos dos argumentos da função a seus respectivos parâmetros;
2. Estender temporariamente o contexto capturado durante a definição da função, de forma que contenham as ligações feitas no passo 1;
3. Interpretar o corpo da função sob este contexto gerado.

Fica claro, inclusive, que a operação \(v\) é, na verdade, um caso especial da operação \(e\) definida acima. Em outras palavras, \(v[\texttt{E}] = e[\texttt{E}, \texttt{nil}]\)².

((eq (first proc) 'closure)
 (eval. (second (second proc))
        (bind. (first (second proc))
               args
               (third proc))))

Poderiam ocorrer outros casos de aplicação no interpretador. Todavia, isto não ocorre aqui.

Uma situação anômala será considerada um erro; portanto, utilizaremos a primitiva err de Majestic para propagar tal erro quando ocorrer.

(t (err "Undefined procedure: {}" proc)))))

As funções auxiliares bind. e pair-up. são responsáveis por ligar um conjunto de variáveis a seus respectivos valores, e então criar um novo contexto com esses pareamentos, reaproveitando um contexto antigo.

Cada conjunto de novos pareamentos é conhecido como sendo um frame no contexto. pair-up. cria um novo frame, bind. adiciona este frame ao contexto antigo (sem modificá-lo).

(def bind.
  (fn (vars vals env)
    (cons (pair-up. vars vals)
          env)))

(def pair-up.
  (fn (vars vals)
    (cond
     ((nilp vars)
      (cond ((nilp vals) nil)
            (t (err "Too many arguments"))))
     ((nilp vals)
      (err "Too few arguments"))
     (t (cons (cons (first vars)
                    (first vals))
              (pair-up. (rest vars)
                        (rest vals)))))))

A consulta de um símbolo em um contexto nada mais é que varrer cada um de seus frames e, nestes frames, procurar nos pares de variáveis se há uma correspondência entre aquele determinado símbolo e algum valor.

Se houver, o valor é retornado; se não, um erro é levantado indicando que a variável não foi definida.

lookup. é responsável por varrer o contexto atrás de frames. assq. é a função auxiliar que varre um frame à procura do símbolo e de seu valor correspondente.

(def lookup.
  (fn (sym env)
    (cond
     ((nilp env)
      (err "Unbound variable {}" sym))
     (t ((fn (vcell)
                 (cond ((nilp vcell)
                        (lookup. sym (rest env)))
                       (t (rest vcell))))
               (assq. sym (first env)))))))

(def assq.
  (fn (sym alist)
    (cond ((nilp alist) nil)
          ((eq sym (first (first alist)))
           (first alist))
          (t (assq. sym (rest alist))))))

Durante o uso da forma especial def, o que se faz é modificar um contexto inicial, que aqui armazenaremos na variável *env*, sendo esta diretamente inacessível para o usuário do interpretador que estamos construindo.

Quando um novo valor é definido através de def, um novo frame é criado e incluído em *env*. Essa operação cria um novo contexto que referencia o valor anterior de *env*. Subsequentemente, *env* passa a apontar para esse novo contexto, sendo, portanto, modificado.

(def defglobal.
  (fn (sym val env)
    (cond ((symbolp sym)
                 (set *env*
                      (bind. (list sym)
                             (list (eval. val env))
                             env))
           sym)
                (t (err "Not a symbol: {}" sym)))))