Elmord's Magic Valley

Computers, languages, and computer languages. Às vezes em Português, sometimes in English.

Posts com a tag: lisp

Lisp meets PHP

2015-09-02 04:25 -0300. Tags: comp, prog, pldesign, php, lisp, lows, in-english, em-portugues

[This post is also available in English.]

Como eu andei comentando por aí, eu comecei a implementar uma linguagem Lisp-like que compila para PHP 5.2, chamada lows. Não sei quando vou mexer nesse projeto de novo, mas deixo aqui algumas notas para o meu eu futuro e para quem tiver interesse.

Prelúdio

Tudo começou no domingo retrasado, quando eu resolvi dar uma mexida no blog system, for a change. Mexer no blog sempre é uma experiência ambivalente, pois por um lado tem uma porção de idéias que eu gostaria de implementar nele, mas por outro lado eu tenho que fazer isso em PHP, porque é a única coisa que roda no inf.ufrgs.br (e eu não pretendo pagar por hospedagem any time soon). Eu comentei com uma pessoa que se eu tivesse a opção, eu já teria reescrito o blog em Scheme há muito tempo. Ela me perguntou por que eu não fazia algo para rodar Scheme em PHP, e eu comentei que já tinha pensado em fazer um compilador de Lisp para PHP, mas que achava que era muita mão só para poder escrever o blog em Lisp. Assim, eu segui meu domingo fuçando no blog em PHP.

Depois de uma porção de gambiarras e mais uma porção de concessões às bizarrices do PHP (e.g., existem os métodos mágicos __call, __callStatic e __get, mas não existe um __getStatic, sabe-se lá por quê), eu consegui reescrever a parte do blog responsável por mensagens multilíngües de uma maneira que me agradasse, e até já não estava mais achando tão horrível escrever o código em PHP.

No final do dia, depois de ter testado o código no meu servidor local, eu resolvi fazer upload da nova versão para o inf.ufrgs.br. Para minha surpresa, o PHP começou a reportar uma porção de erros no código. Turns out que a versão do PHP que roda no inf.ufrgs.br é a "5.2.6-1+lenny16". Para quem não sabe, lenny é o codinome do Debian 5. O Debian 5 foi lançado em 2009 e não recebe mais atualizações desde 2012. Três releases estáveis do Debian saíram desde então (as releases estáveis do Debian saem a cada mais ou menos dois anos). Meanwhile, eu estava rodando PHP 5.6.12 em um Debian testing em casa, e praticamente todo o código que eu tinha escrito usava features introduzidas no PHP 5.3.

Depois de tentar sem muito sucesso mudar um pouco o código para ver se conseguia fazê-lo rodar no PHP 5.2, eu resolvi largar de mão e deixar para mexer no código outro dia. Porém: (1) eu não estava a fim de enfeiar o código só para fazê-lo rodar em um PHP velho; (2) more generally, eu não estava a fim de mexer em PHP de novo; e (3) eu não estava conseguindo dormir aquele dia. Conclusão: comecei a escrever um tradutor Lisp→PHP, primariamente for the lol. Mais uma noite mal-dormida, e eis que eu tinha um tradutor (ou compilador, como preferir) Lisp→PHP que fazia pouca coisa, mas o suficiente para me convencer de que a idéia era pelo menos viável. Nasceu assim o lows, ou Lisp for Old Web Servers.

Idéia

A idéia do projeto é criar uma linguagem Lisp-like que satisfaça os seguintes objetivos:

Compilar para PHP 5.2. A idéia é eu poder rodar o código resultante no inf.ufrgs.br (e idealmente escrever a próxima versão do blog em lows), então eu preciso "targetar" especificamente PHP 5.2. Eu também podia tentar convencer a galera da admrede a atualizar o servidor, mas (1) acho pouco provável que isso aconteça any time soon, e eu não estava a fim de esperar; (2) a essa altura eu já tinha tomado a limitação a PHP 5.2 como um desafio (lembre-se de que eu comecei o projeto para matar tempo enquanto o sono não vinha); (3) já existe um projeto similar, chamado Pharen, que targeta PHP 5.5, e eu queria um diferencial (a.k.a. desculpa) para justificar o meu projeto.

Gerar código PHP relativamente straightforward. Tanto quanto possível, o código PHP resultante da compilação deve ser uma tradução mais ou menos direta do código lows original. A idéia é facilitar a depuração (e em particular a tarefa de encontrar o código lows correspondente a um erro reportado no código PHP), e também a esperança de que quanto mais direto for o código resultante, menor o impacto na performance de escrever o código em lows ao invés de diretamente em PHP.

Integrar facilmente com PHP. Deve ser possível usar funções, classes, etc. do PHP a partir de código lows e vice-versa, sem necessidade de conversões, anotações e afins.

Manter uma essência Lisp-like. A idéia não é simplesmente criar um redressing de PHP em S-expressions, mas sim uma linguagem que permita programar em um estilo semi-funcional e "Lispy" e evite as bizarrices do PHP na medida do possível (ao mesmo tempo em que introduz outras bizarrices).

Esse conjunto de objetivos influencia tanto a implementação (que deve gerar um PHP relativamente limpo/direto) quanto o design da linguagem (que não deve fugir muito do PHP para permitir a tradução relativamente direta e a compatibilidade com código PHP).

Transformando Lisp em PHP

Expressões e statements

Um desafio que eu encontrei logo no começo é o fato de que o PHP faz uma distinção entre expressões e statements, que (mostly) não existe em Lisp. Em particular, coisas como if, let (declaração de variáveis locais) e progn (executa uma seqüência de expressões e retorna o valor da última, mais ou menos análogo a um bloco entre chaves em PHP, mas que produz um valor) são expressões em lows. O if em princípio até poderia ser traduzido para o operador ternário (test? then : else), e o let poderia ser mais-ou-menos contornado já que atribuição é uma expressão em PHP. O problema é que PHP não tem um operador vírgula como em C. Coisas como:

(+ 1 (let ((x 23)
           (y 42))
       (* x y)))

não possuem uma tradução direta para PHP, pois não é possível escrever 1 + ($x=23, $y=42, $x*$y). Uma solução gambiarrenta seria gerar:

1 + ((($x=23) || TRUE) ? ((($y=42) || TRUE) ? ($x*$y)
                                            : whatever)
                       : whatever)

o que simula o operador vírgula usando só um branch do operador ternário, mas: (1) isso não funciona no caso geral (em particular, se uma das expressões é um progn contendo um echo ou alguma outra coisa statementosa); (2) isso vai totalmente contra a idéia de gerar código straightforward. A solução é mover as atribuições para antes da soma, mas, no caso geral, só mover qualquer coisa que não seja uma expressão em PHP para antes da expressão não é suficiente: se os branches de um condicional contêm expressões com efeitos colaterais, não é possível movê-las para fora do condicional. Por exemplo, em algo como:

(defun print-and-return (val)
  (echo "O valor é " val "\n")
  val)

(+ 1 (if (> x y)
         (let ((a (print-and-return (- x y))))
           (* a a))
       0))

não é possível traduzir a soma para:

$a = print_and_return($x-$y);
1 + (($x>$y)? ($a*$a) : 0)

pois print_and_return não pode ser chamada antes que o teste $x>$y seja realizado.

[A essa altura talvez lhe ocorra (como me ocorreu) o pensamento: "Ok, e por que a gente simplesmente não proíbe expressões complexas desse tipo aninhadas em outras expressões? Quando é que eu vou usar isso anyway?" Mas esse é justamente o tipo de limitação tosca de que nós estamos tentando fugir criando uma nova linguagem ao invés de programar em PHP! "Do not tell me “that’s what you get for doing weird things”. If two features exist, someday, someone will find a reason to use them together."]

A solução que eu encontrei foi traduzir o (if ...) para um bloco if em PHP, armazenar o valor do if em uma variável temporária, e usar a variável temporária na soma. O exemplo anterior fica algo como:

if ($x>$y) {
    $a = print_and_return($x-$y);
    $tmp = $a*$a;
} else {
    $tmp = 0;
}

1 + $tmp

Isso significa que para traduzir uma expressão como (+ ...), pode ser necessário emitir blocos de código antes da tradução da soma propriamente dita. Conseqüentemente, a função de tradução não pode ser simplesmente algo como:

translate[(+ lhs rhs)] = translate[lhs] + translate[rhs]

pois tanto a tradução de lhs quanto de rhs podem requerer a inserção de blocos de código antes da soma (e a soma, por sua vez, pode estar aninhada em outra expressão).

A solução que eu encontrei para esse problema foi fazer as funções de tradução retornarem dois valores: a expressão equivalente em PHP, e uma lista de "efeitos", que são basicamente (mas não necessariamente) instruções para emitir código nas redondezas da tradução. Por exemplo, a função de tradução aplicada ao if do exemplo gera a expressão $tmp (que pode ser inserida no meio de outra expressão que usa o valor do if), e o efeito (EmitBefore bloco-if-em-PHP), que indica que o bloco-if-em-PHP deve ser inserido antes da expressão que contém o if na geração do código PHP. Como a inserção só pode ser realizada fora de uma expressão, o efeito é propagado pelas funções de tradução de expressões, até que ele chega em uma função que emite statements (e.g., o corpo de um bloco if do PHP, ou o corpo de uma função) e pode então ser emitido. Pseudocodiciosamente (oops, hmm):

translate[(+ lhs rhs)] =
   let
       lhs-trans; lhs-effects = translate[lhs]
       rhs-trans; rhs-effects = translate[rhs]
   in
       lhs + rhs; lhs-effects ++ rhs-effects


translate-statement[item] =
   let
       item-trans; item-effects = translate[item]
   in
       (código correspondente aos EmitBefore em item-effects) ++ item-trans ;
       (efeitos em item-effects excluindo os EmitBefore já processados)

O mesmo mecanismo pode ser usado para emitir código em outras situações (e.g., no caso do lambda, como veremos adiante), ou para coletar e propagar informações durante a tradução. Por exemplo, quando uma variável x que não possui declaração visível é usada, é emitido um efeito (Global x). A função que traduz o corpo de uma função coleta esses efeitos para gerar declarações do tipo global $x; no começo da função.

lambda

O próximo desafio foi traduzir o lambda para PHP. PHP >=5.3 possui closures (meio toscas – é necessário declarar explicitamente que variáveis são capturadas pela closure – mas elas existem), mas PHP 5.2 não. A próxima coisa que eu pensei foi usar uma classe "callable" com um método mágico __invoke, mas turns out que classes chamáveis só foram introduzidas em PHP 5.3 também. Porém, as funções que aceitam coisas chamáveis em PHP, como call_user_func e usort, aceitam arrays da forma Array(objeto, nome-de-método) como chamáveis. Pois, aí está algo que o lambda pode retornar.

Capturar as variáveis em uma closure mostrou-se bem mais fácil do que eu antecipava, graças às referências do PHP. Uma closure em lows é representada por uma classe com um membro/slot/propriedade/atributo/whatever para cada variável capturada. Quando a classe é instanciada, as variáveis são passadas por referência para o construtor. Dentro do corpo do lambda, referências a variáveis capturadas x são traduzidas para $this->x; como $this->x foi inicializado com uma referência ao $x capturado, o corpo do lambda vê a mesma variável $x através do atributo, inclusive refletindo modificações à mesma.

Como exemplo, algo como:

(defun adder (x)
  (lambda (n)
    (+ x n)))

(defun main ()
  (let ((f (adder 10)))
    (call_user_func f 5)))

vira algo como:

class Closure1 {
    function __construct(&$x) {
        // Captura de variáveis.
        $this->x = &$x;
    }

    function __invoke($n) {
        // Corpo do lambda.
        return $this->x + $n;
    }
}

function adder($x) {
    // Cria a closure, passando a variável a ser capturada para o seu construtor,
    // e retorna um valor que, quando chamado, chama o método "__invoke" da closure.
    return Array(new Closure1($x), "__invoke");
}

function main() {
    $f = adder(10);
    return call_user_func($f, 5);
}

E assim, o PHP e suas referências nos surpreendem positivamente (o que é uma surpresa in itself).

By the way, o mecanismo de efeitos aqui é usado para duas coisas: (1) a geração da classe antes da função que contém o lambda é feita propagando um efeito (EmitBeforeToplevel definição-da-classe); (2) cada referência a uma variável externa ao lambda gera um efeito (CapturedVar x); esses efeitos são coletados pela função que traduz o lambda para saber que atributos devem ser inicializados na classe e que argumentos devem ser passados ao construtor. Quando eu criei a treta dos efeitos eu não tinha pensado em todas essas aplicações, então mui me alegrou descobrir que eu podia reusar o mecanismo para essas coisas.

Name clashes

Em PHP, variáveis locais têm como escopo a função inteira onde se encontram, não apenas o bloco onde foram declaradas. Conseqüentemente, em código como:

(let ((x 23))
  (echo "x aqui vale 23: " x "\n")
  (let ((x 42))
    (echo "x aqui dentro vale 42: " x "\n"))
  (echo "x aqui fora ainda vale 23: " x "\n"))

não se pode usar o mesmo nome para as duas variáveis x na tradução, pois a definição mais interna de x sobrescreveria a mais externa. A solução e renomear uma das (ou ambas as) variáveis. O ideal seria fazer o mínimo de renomeações possível, para facilitar a leitura e depuração do código resultante. Porém, a implementação atual simplesmente renomeia todas as variáveis (adicionando um prefixo _número_), já que testar quando uma variável deve ser renomeada não é muito simples. Essa decisão não é local: mesmo não havendo nenhuma variável x visivelmente declarada no ponto onde ocorre um (let ((x 23)) ...), ainda assim é necessário renomear o x se em um ponto posterior da função uma variável global x for referenciada.

O algoritmo de renomeação / geração de nomes temporários assume que nomes iniciados por _número_ são reservados para o compilador. Acredito que isso não seja um problema na prática. (Para o caso de variáveis locais, uma variável _42_ vai ser renomeada para algo como _1__42_ de qualquer forma.) Um problema mais sério dessa abordagem é no escopo global, em particular nos nomes gerados para as classes que implementam closures (e.g., _1_Closure), pois esses nomes podem conflitar com closures criadas em outros arquivos (e.g., quando os resultados da tradução de múltiplos arquivos são incluídos com include em um programa PHP). Talvez uma solução seja incluir o nome do arquivo no nome da classe, ou gerar um hash a partir do código da closure (mas isso ainda gera conflito se um lambda idêntico aparece em outro arquivo), or something. I don't know. Também seria bom se o nome da classe fosse informativo o suficiente para indicar de onde saiu a definição no código original (e.g., _1_Closure_arquivo_função_linha). [Side remark: namespaces não existem em PHP 5.2.]

Um conflito de variável mais sutil é quando um let é executado múltiplas vezes e um lambda captura uma variável definida pelo let. Por exemplo, supondo a existência de uma construção while:

(let ((array-of-lambdas (array))
      (i 0))
  (while (< i 5)
    (let ((n 0))
      (array_push array-of-lambdas
                  (lambda ()
                    (set! n (+ n 1))
                    (echo n))))
    (set! i (+ i 1))))

Isso seria traduzido para algo como:

Class _1_Closure {
    function __construct(&$n) {
        $this->n = &$n;
    }

    function __invoke() {
        $this->n = $this->n + 1;
        echo $this->n;
    }
}

$array_of_lambdas = Array();
$i = 0;
while ($i < 5) {
    $n = 0;
    array_push($array_of_lambdas,
               Array(new _1_Closure($n), "__invoke"));
    $i = $i + 1;
}

O problema é que todas as iterações do loop usam a mesma variável $n, que é passada por referência ao construtor da closure; o correto seria cada iteração capturar um $n diferente. A solução é emitir uma chamada a unset($n) no final do while, de maneira que cada iteração crie uma variável nova, mas eu ainda não implementei isso.

PHP formatado

Um dos objetivos do projeto é gerar PHP legível, e isso envolve gerar código com indentação adequada. Depois de alguns false starts (na versão inicial, as funções de tradução geravam strings de código PHP diretamente, e a minha idéia original era usar caracteres especiais do ASCII como indicadores de "increase indentation" e "decrease indentation" quando o código fosse impresso, mas eu me dei conta de que não dava para escolher caracteres para isso porque qualquer caractere pode aparecer em uma string; além disso, misturar geração de código e questões de formatação estava ficando um bocado desagradável), eu resolvi fazer as funções de tradução gerarem estruturas representando árvores de sintaxe abstrata (ASTs) de PHP. Depois da tradução, as árvores são passadas a uma função print-php que trata dos detalhes sórdidos de imprimir o código com quebras de linha, indentações, espaços e parênteses nos lugares apropriados. Separation of concerns FTW.

O futuro

Como o post ficou grande, e eu deveria ir dormir, ficaremos por aqui. Em um post futuro, pretendo falar de algumas features que falta implementar, tais como classes, chamadas de métodos e demais firulas orientadas a objetos, bem como as decisões de design mais tricky (que eram o objetivo inicial do post, mas enfim). Quem tiver interesse, pode dar uma olhada no código no GitHub.


[English version follows.]

As I have been talking about, I started implementing a Lisp-like language which compiles to PHP 5.2, called lows. I don't know when I'm going to work on this project again, but I'll leave here some notes for my future self and whoever might be interested.

Prelude

It all began last last Sunday, when I decided to play with my blog system, for a change. Working on the blog system is always an ambivalent experience, because on the one hand there is a bunch of ideas I would like to implement in it, but on the other hand I have to do it in PHP, as that is the only thing that runs at inf.ufrgs.br (and I don't plan to pay for hosting any time soon). I commented to a person that if I had the choice, I would have rewritten the blog in Scheme long ago. She asked my why I didn't make something to run Scheme in PHP, and I said I had already though of writing a compiler from Lisp to PHP, but that I thought it was too much work just to be able to write the blog in Lisp. So, I went on with my Sunday messing with the blog in PHP.

After a number of kludges and another number of concessions to the oddities of PHP (e.g., there are the __call, __callStatic and __get magic methods, but no __getStatic, who knows why), I succeeded in rewriting the part of the blog responsible for multilingual messages in a way that pleased me, and I was even not finding it so horrible to write the code in PHP.

At the end of the day, after having tested the code in my local server, I decided to upload the new version to inf.ufrgs.br. To my surprise, PHP started reporting lots of errors in the code. It turns out that the version of PHP running at inf.ufrgs.br is "5.2.6-1+lenny16". For those who don't know, lenny is the codename of Debian 5. Debian 5 was launched in 2009 and does not get updates since 2012. Three stable Debian releases have been out since then (the stable releases of Debian are launched more or less every two years). Meanwhile, I was running PHP 5.6.12 in a Debian testing at home, and practically all the code I had written used features introduced in PHP 5.3.

After trying without much success to change the code a bit to see if I got it to run on PHP 5.2, I decided to leave it alone and work on the code another day. However: (1) I was not willing to uglify my code just to make it run on an old PHP; (2) more generally, I wasn't willing to work with PHP again; and (3) I was having difficulties to sleep that day. Conclusion: I stared writing a Lisp→PHP translator, primarily for the lol. One more badly-slept night later, and so it was that I had a Lisp→PHP translator (or compiler, if you prefer) that did little, but enough to convince me that the idea was at least feasible. Thus lows, or Lisp for Old Web Servers, was born.

Idea

The idea of the project is to create a Lisp-like language which satisfies the following criteria:

Compile to PHP 5.2. The idea is for me to be able to run the resulting code at inf.ufrgs.br (and ideally write the next version of the blog in lows), so I need to target specifically PHP 5.2. I could also try to convince the admins at INF to upgrade the server, but (1) I don't think that's going to happen any time soon, and I was not willing to wait; (2) at this point I had already taken the limitation to PHP 5.2 as a challenge (remember that I started the project to kill time while I couldn't sleep); (3) there is already a similar project, called Pharen, which targets PHP 5.5, and I wanted a distinctive feature (a.k.a. excuse) to justify my project.

Emit relatively straightforward PHP code. As much as possible, the PHP code resulting from compilation should be a more or less direct translation of the lows source. The idea is to ease debugging (and in particular the task of finding the lows code corresponding to a PHP error message), and also the hope that the more direct the resulting code, the smaller the impact on performance of writing the code in lows rather than directly in PHP.

Integrate easily with PHP. It must be possible to use PHP functions, classes, etc. from lows code and vice-versa, without requiring conversions, annotations and the like.

Keep a Lisp-like essence. The idea is not simply to make a redressing of PHP in S-expressions, but rather a language which enables programming in a semi-functional and "Lispy" style and avoids the oddities of PHP as much as possible (while introducing new oddities of its own).

This set of goals influences both the implementation (which must emit relatively clean/direct PHP code) and the design of the language (which must not stray away too much from PHP to allow a relatively direct translation and compatibiltity with PHP code).

Transforming Lisp into PHP

Expressions and statements

A challenge I found right at the beginning is the fact that PHP makes a distinction between expressions and statements, which (mostly) does not exist in Lisp. In particular, things like if, let (local variable declaration) and progn (runs a sequence of expressions and returns the value of the last one, more or less like a block in braces in PHP, but yielding a value) are expressions in lows. if in principle could be translated to the ternary operator (test? then : else), and let could be more-or-less worked around because assignment is an expression in PHP. The problem is that PHP does not have a comma operator like that of C. Things like:

(+ 1 (let ((x 23)
           (y 42))
       (* x y)))

don't have a direct translation to PHP, because it is not possible to write 1 + ($x=23, $y=42, $x*$y). A kludgy solution would be to emit:

1 + ((($x=23) || TRUE) ? ((($y=42) || TRUE) ? ($x*$y)
                                            : whatever)
                       : whatever)

which emulates the comma operator by using only one branch of the ternary operator, but (1) that doesn't work in the general case (in particular, if one of the expressions is a progn containing an echo or some other statement-y thing); (2) that goes totally against the idea of emitting straightforward code. The solution is to move the assignments to before the addition, but, in general, just moving anything that is not an expression to before the expression is not enough: if the branches of a conditional contain expressions with side effects, they cannot be moved out of the conditional. For instance, in something like:

(defun print-and-return (val)
  (echo "The value is " val "\n")
  val)

(+ 1 (if (> x y)
         (let ((a (print-and-return (- x y))))
           (* a a))
       0))

it is not possible to translate the addition to:

$a = print_and_return($x-$y);
1 + (($x>$y)? ($a*$a) : 0)

because print_and_return cannot be called before the test $x>$y is performed.

[At this point, perhaps it ocurred to you (as ocurred to me) the thought: "Okay, why don't we just forbid complex expressions like these nested in other expressions? When will I use that anyway?" But that is exactly the kind of weird limitation which we are trying to escape from by creating a new language instead of programming in PHP! "Do not tell me “that’s what you get for doing weird things”. If two features exist, someday, someone will find a reason to use them together."]

The solution I found was to translate (if ...) to a PHP if block, store the value of the if expression into a temporary variable, and use the temporary in the addition. The previous example becomes something like:

if ($x>$y) {
    $a = print_and_return($x-$y);
    $tmp = $a*$a;
} else {
    $tmp = 0;
}

1 + $tmp

This means that to translate an expression like (+ ...), it may be necessary to emit blocks of code before the translation of the addition itself. As a consequence, the translation function cannot be just something like:

translate[(+ lhs rhs)] = translate[lhs] + translate[rhs]

because both lhs and rhs may require inserting blocks of code before the addition (and the addition itself may be nested in another expression).

The solution I found for this problem was to make the translation functions return two values: the equivalent expression in PHP, and a list of "effects", which are basically (but not necessarily) instructions to emit code in the surroundings of the translation. For example, the translation function, when applied to the example if, yields the expression $tmp (which can be inserted in the middle of another expression which uses the value of the if, and the effect (EmitBefore PHP-if-block), which indicates that PHP-if-block must be inserted before the expression containing the if when emitting the PHP code. Since the insertion can only be performed outside of an expression, the effect is propagated by the functions responsible for translating expressions, until it arrives at a function which emits statements (e.g., the body of a PHP if block, or a function body), where it can then be emitted. Pseudocodefully:

translate[(+ lhs rhs)] =
   let
       lhs-trans; lhs-effects = translate[lhs]
       rhs-trans; rhs-effects = translate[rhs]
   in
       lhs + rhs; lhs-effects ++ rhs-effects


translate-statement[item] =
   let
       item-trans; item-effects = translate[item]
   in
       (code corresponding to the EmitBefores in item-effects) ++ item-trans ;
       (effects in item-effects excluding those EmitBefores already processed)

The same mechanism can be used to emit code in other situations (e.g., in the case of lambda, as we'll see later), or to collect and propagate information during translation. For example, when a variable x which has no visible declaration is used, a (Global x) effect is generated. The function responsible for translating functions collects those effects to generate global $x; declarations at the beginning of the function.

lambda

The next challenge was to translate lambda to PHP. PHP >=5.3 has closures (somewhat crappy ones – one must declare explicitly which variables are to be captured by the closure – but they exist), but PHP 5.2 doesn't. The next thing I thought was to use a "callable" class with an __invoke magic method, but it turns out that callable classes were introduced only in PHP 5.3 too. However, the functions which accept callable things in PHP, such as call_user_func and usort, accept arrays of the form Array(object, method-name) as callables. So, this is something that lambda can return.

Capturing variables in a closure proved much easier than I anticipated, thanks to PHP references. A closure in lows is represented as a class with a member/slot/property/attribute/whatever for each captured variable. When the class is instantiated, the variables are passed by reference to the constructor. Inside the body of lambda, references to captured variables x are translated to $this->x; because $this->x was initialized with a reference to the captured $x, the lambda body sees the same variable $x through the attribute, even reflecting modifications to it.

As an example, something like:

(defun adder (x)
  (lambda (n)
    (+ x n)))

(defun main ()
  (let ((f (adder 10)))
    (call_user_func f 5)))

turns into something like:

class Closure1 {
    function __construct(&$x) {
        // Variable capture.
        $this->x = &$x;
    }

    function __invoke($n) {
        // lambda body.
        return $this->x + $n;
    }
}

function adder($x) {
    // Create the closure, passing the variables to be captured to the constructor,
    // and returns a value that, when called, calls the closures' "__invoke" method.
    return Array(new Closure1($x), "__invoke");
}

function main() {
    $f = adder(10);
    return call_user_func($f, 5);
}

And so, PHP and its references surprise us positively (which is a surprise in itself).

By the way, the effects mechanism is used here for two things: (1) emitting the class before the function containing the lambda is done by propagating an (EmitBeforeToplevel class-definition) effect; (2) each reference to a variable external to the lambda generates a (CapturedVar x) effect; these effects are collected by the function responsible for translating lambda to find out which attributes must be initialized in the class and which arguments must be passed to the constructor. When I came up with the effects idea I hadn't thought about all those applications, so it much gladdened me to find out I could use the mechanism for those things too.

Name clashes

In PHP, local variables have the scope of the entire function where they are created, not just the block where they were declared. As a consequence, in code like:

(let ((x 23))
  (echo "x here is 23: " x "\n")
  (let ((x 42))
    (echo "x here inside is 42: " x "\n"))
  (echo "x out here still is 23: " x "\n"))

we cannot use the same name for both x variables in the translation, because the innermost definition of x would overwrite the outermost one. The solution is to rename one of the (or both) variables. Ideally we should perform the minimum number of renames possible, to make it easier to read and debug the resulting code. However, the current implementation simply renames all variables (adding a _number_ prefix), since testing when a variable must be renamed is not very simple. This decision is non-local: even if there is no visible declaration of a variable x at the point where a (let ((x 23)) ...) occurs, it is still necessary to rename x if at some later point in the function a global variable x is referenced.

The renaming / temporary name generation algorithm assumes that names beginning with _number_ are reserved to the compiler. I think this is not a problem in practice. (In the case of local variables, a variable _42_ would be renamed to something like _1__42_ anyway.) A more serious problem of this approach is at the global scope, in particular in the names of generated classes which implemente closures (e.g., _1_Closure), because those names may conflict with closures created in other files (e.g., when the translation results of multiple files are included into a single PHP program). Perhaps a solution is to include the file name in the name of the class, or to compute a hash from the closure code (but this would still cause conflicts if an identical lambda appears in another file), or something. I don't know. It would also be nice if the class name were descriptive enough to indicate where the definition came from in the source code (e.g., _1_Closure_file_function_line). [Side remark: namespaces don't exist in PHP 5.2.]

A more subtle variable conflict occurs when a let is executed multiple times and a lambda captures a variable defined by the let. For example, supposing the existence of a while construction:

(let ((array-of-lambdas (array))
      (i 0))
  (while (< i 5)
    (let ((n 0))
      (array_push array-of-lambdas
                  (lambda ()
                    (set! n (+ n 1))
                    (echo n))))
    (set! i (+ i 1))))

This would be translated to:

Class _1_Closure {
    function __construct(&$n) {
        $this->n = &$n;
    }

    function __invoke() {
        $this->n = $this->n + 1;
        echo $this->n;
    }
}

$array_of_lambdas = Array();
$i = 0;
while ($i < 5) {
    $n = 0;
    array_push($array_of_lambdas,
               Array(new _1_Closure($n), "__invoke"));
    $i = $i + 1;
}

The problem is that all iterations of the loop use the same $n variable, which is passed by reference to the closure constructor; the correct would be for each iteration to capture a different $n. The solution is to emit an unset($n) at the end of the while body, so that each iteration would create a new variable, but I haven't implemented this yet.

Pretty-printed PHP

One of the goals of the project is to emit readable PHP code, and this involves emitting properly indented code. After some false starts (in the initial version, the translation functions emitted PHP code strings directly, and my original idea was to use some special ASCII characters to indicate "increase indentation" and "decrease indentation" when printing, but I realized that I could not choose any characters for that because any character can appear in a string; moreover, mixing code generation and formatting questions was becoming rather ugly), I decided to make the translation function emit structures representing PHP abastract syntax trees (ASTs). After translation, the trees are passed to a print-php function, which takes care of the gory details of printing the code with line breaks, indentation, spaces and parentheses at the proper places. Separation of concerns FTW.

The future

As this post turned quite long, and I should get some sleep, we'll finish here. In a future post, I intend to talk about some features that are still missing, such as classes, method calls and other stuff, as well as trickier design decisions (which were the initial goal of this post, but anyway). If you are interested, you can look at the code on GitHub.

1 comentário / comment

Noun-centric vs. verb-centric OO

2013-05-11 01:36 -0300. Tags: comp, prog, lisp, pldesign, em-portugues

As linguagens orientadas a objetos convencionais são o que podemos chamar de noun-centric: as classes são a "unidade estrutural" mais importante, e os métodos (verbos) pertencem a classes (nomes). Um método é chamado sobre exatamente um objeto, e a escolha de que código será executado para a chamada depende da classe do objeto sobre o qual o método é chamado. A sintaxe objeto.método(args) reflete essa idéia.

Algumas outras linguagens, como Common Lisp e Dylan, entretanto, seguem um modelo "verb-centric": os métodos são definidos fora das classes. Métodos de mesmo "nome" (onde nome = símbolo + pacote ao qual pertence) são agrupados sob uma mesma generic function. As classes de todos os argumentos da generic function são consideradas na hora de escolher que código será executado. Em Common Lisp, a sintaxe (método arg1 arg2...) reflete essa ausência de preferência por um dos argumentos e a existência da função como algo externo a qualquer classe. (Não lembro mais de onde saíram os termos "noun-centric" e "verb-centric" para descrever essa diferença, mas eles não são invenção minha.)

As conseqüências na prática são várias. Uma delas é que no modelo verbocêntrico é possível criar novos métodos para classes existentes sem ter que modificá-las. Por exemplo, se você quiser criar um método novo para trabalhar com strings, você pode defini-lo e usá-lo como qualquer outro método sobre strings, ao invés de criar uma distinção artificial entre métodos nativos da classe String ("foo".method(42)) e métodos definidos somewhere else que trabalham com strings (RandomClass.method("foo", 42)). (Ruby, uma linguagem nominocêntrica, resolve esse problema permitindo "redefinições parciais" de classes. Essa solução, entretanto, tem o problema de que todos os métodos sobre uma classe compartilham o mesmo namespace, i.e., se dois arquivos diferentes quiserem definir method sobre uma mesma classe, as definições conflitarão. Em Common Lisp, cada method estaria em seu próprio pacote, o que evita esse problema.)

Outra vantagem do modelo verbocêntrico é que evitam-se decisões arbitrárias quanto a em que classe se deve incluir um método. Por exemplo, imagine que queiramos definir um método (match string regex), que retorna a primeira ocorrência de regex em string. Esse método vai na classe String, ou em RegEx? E se quisermos procurar por outras coisas além de regexes dentro da string (e.g., outras strings)? E se quisermos procurar regexes em coisas que não são strings (e.g., streams)? No modelo verbocêntrico, essa decisão simplesmente não existe; basta definir match para todas as combinações de tipos de argumentos possíveis.

Uma terceira conseqüência desse modelo é que o conceito de "interface" é desnecessário: "implementar uma interface" consiste em especializar os métodos desejados para a classe em questão. (De certa forma, pode-se imaginar cada generic function como uma interface de um método só, e cada definição de método para a generic function como a implementação da interface para uma combinação de classes. De certa forma, pode-se imaginar muitas coisas.) Uma desvantagem disso é que se perde a garantia estática provida pelas interfaces de que de uma dada classe implementa um conjunto de métodos relacionados. (Garantias estáticas não são exatamente um ponto forte do Common Lisp.)

No modelo nominocêntrico, é possível descrever chamadas de métodos em termos de troca de mensagens: quando escrevemos obj.foo(23, 42), podemos pensar que estamos enviando a mensagem foo(23, 42) para o objeto obj. De fato, em Smalltalk, uma das primeiras linguagens orientadas a objeto, as mensagens são objetos de primeira classe, e é possível fazer algumas coisas interessantes com elas (como por exemplo repassá-las para outros objetos, ou definir um método doesNotUnderstand que trata todas as mensagens que uma classe não reconhece). O modelo de troca de mensagens também é interessante em implementações de objetos distribuídos: nesse caso, uma chamada de método sobre um objeto remoto é de fato uma mensagem enviada pela rede para a máquina onde o objeto se encontra. Uma desvantagem do modelo verbocêntrico é que o a descrição em termos de troca de mensagens não é mais aplicável: um método é chamado sobre múltiplos objetos, e portanto não há um "receptor" da mensagem.

quem diga que o CLOS (Common Lisp Object System) não é de fato orientação a objetos, mas sim um paradigma diferente que é capaz de expressar orientação a objetos e (um bocado de) outras coisas (muitas delas não abordadas neste post, tais como before/after methods (que lembram programação orientada a aspectos) e method combinations). Hoje em dia eu me vejo inclinado a concordar com essa posição, já que o CLOS foge da idéia de objetos como caixinhas fechadas manipuladas apenas através dos métodos expostos pela classe correspondente. Encapsulamento é possível em Common Lisp (basta não exportar os nomes dos slots (a.k.a. propriedades, atributos, membros) no pacote onde foram definidos), mas a noção de objeto = dados + operações se perde, de certa forma. Os objetos são apenas os dados, e as operações somos nós estão contidas nas generic functions / métodos.

2 comentários / comments

So many parens

2013-04-17 17:17 -0300. Tags: comp, prog, lisp, em-portugues

Pode-se dividir as pessoas em dois grupos, segundo sua reação ao serem apresentadas a features novas em uma linguagem de programação:

(Na verdade o que provavelmente existe é um continuum de quanta justificativa é necessária para provocar a reação "whoa, que legal" em uma dada pessoa, but I digress.) O que acontece aí é que eu (que estou no primeiro grupo, mostly) freqüentemente acho complicado pensar em um exemplo de uso de uma feature que convença alguém do segundo grupo de que a feature é interessante. Por exemplo, a pessoa me pergunta "mas por que Lisp tem tantos parênteses?", e eu respondo "Macros!", e a pessoa "why macros?", e eu "code transformation!", e a pessoa "why code transformation", e eu "what do you mean, why?".

Pois, agora acho que encontrei um exemplo decentemente convincente. Meu TCC consiste, entre outras coisas, em desenvolver uma linguagem de programação e integrá-la ao ambiente de programação DrRacket. Para isso, estou implementando a linguagem em Racket, um descendente de Scheme, uma linguagem da família Lisp. Dentre as inúmeras bibliotecas que acompanham o Racket, estão a parser-tools/lex e parser-tools/yacc. Essas bibliotecas implementam funcionalidade equiparável aos famosos programas lex e yacc, que geram analisadores léxicos e sintáticos, respectivamente, a partir de arquivinhos de regras.

A diferença, entretanto, é que as parser-tools são implementadas como macros em Racket, de maneira integrada com o resto da linguagem. Por exemplo, ao invés de usar um programa separado que lê um arquivo meio-em-C, meio-em-lex e gera um arquivo em C, a parser-tools/lex provê uma macro lexer que, quando compilada, produz uma função que recebe uma stream e devolve a próxima token encontrada na stream. Algo do tipo:

(define example-lexer
  (lexer
    [expressão  valor-a-retornar]
    [expressão  valor-a-retornar]
    ...))

O parser funciona de maneira análoga. As macros, assim, permitem estender a linguagem com recursos sintáticos novos, sem que se tenha que usar ferramentas externas para fazer transformações de código (que potencialmente exigem reparsear o texto do programa, ao contrário do que acontece com as macros, que já recebem o programa pré-parseado como argumento). A vantagem da sintaxe uniforme (i.e., so-many-parens) é que os novos recursos adicionados mantêm a mesma cara do resto da linguagem, e que o parser do Lisp (que executa antes de a macro ser chamada) pode fazer o seu trabalho sem se preocupar com a semântica dos objetos que está parseando.

A conseqüência dessa integração é que o threshold a partir do qual vale a pena escrever uma transformação de código ao invés de fazer as coisas na mão é muito mais baixo em um Lisp do que em uma linguagem convencional. Por exemplo, certa vez eu estava escrevendo um typechecker/interpretador para uma linguagem simples. Logo que eu comecei a escrever, percebi que seria uma boa eu usar pattern matching para testar com que tipo de expressão o interpretador tinha se deparado. Por exemplo, ao invés de escrever algo do tipo:

;; Avalia a expressão 'expr' no ambiente de variáveis 'env'.
(defun evaluate (expr env)
  (cond 
    ;; Se a expressão for do tipo (+ x y), devolve x+y.
    ((eq (first expr) '+) (+ (evaluate (second expr) env)
                             (evaluate (third expr) env)))
    ;; Se for (if t x y), avalia o teste e a sub-expressão correspondente.
    ((eq (first expr) 'if) (if (evaluate (second expr) env)
                               (evaluate (third expr) env)
                             (evaluate (fourth expr) env)))
    ...))

eu queria poder escrever algo do tipo:

(defun evaluate (expr env)
  (match-case
    ((+ x y) (+ (evaluate x env) (evaluate y env)))
    ((if test then else) (if (evaluate test env)
                             (evaluate then env)
                           (evaluate else env)))
    ...))

Em 17 linhas (não muito bonitas, mas só porque eu não estava muito preocupado com isso quando as escrevi) de Common Lisp, eu implementei uma macro match-case e segui escrevendo o programa. Se ao invés disso eu tivesse que escrever um programa externo para transformar o código, provavelmente não teria valido a pena o esforço.

#<eof>.

9 comentários / comments

Write yourself a Lisp right now!

2012-05-10 00:20 -0300. Tags: comp, prog, lisp, em-portugues

Que tal escrever um interpretador em cem linhas de código? Let's ride!

What?

Um interpretador é um programa que lê um programa em uma dada linguagem e executa as ações descritas por esse programa. (Um compilador, por outro lado, lê um programa em uma linguagem e o traduz para outra linguagem, freqüentemente a linguagem de máquina de um processador. O processador, por sua vez, é um interpretador de linguagem de máquina implementado em hardware. But I digress.) Há duas linguagens envolvidas em um interpretador: a linguagem de implementação (em que o interpretador é escrito) e a linguagem implementada (que o interpretador interpreta). (Em um compilador há três linguagens envolvidas: a linguagem de implementação, a linguagem fonte e a linguagem alvo.) Essas linguagens podem coincidir (e.g., podemos escrever um interpretador de JavaScript em JavaScript), mas mesmo assim as entidades das duas linguagens freqüentemente são distintas (e.g., funções da linguagem implementada podem ser representadas por uma outra estrutura de dados da linguagem de implementação).

Neste post, implementaremos um interpretador para uma linguagem Lisp-like em JavaScript. O objetivo primário é demonstrar o funcionamento geral de um interpretador. Assim, implementaremos apenas um "Lisp" bem básico, que em certos aspectos diverge dos Lisps típicos. Usaremos JavaScript para a implementação, em parte por ser uma linguagem bem conhecida, e em parte para podermos testar o interpretador no browser. O código desenvolvido neste post, prontamente modificável e experimentável, pode ser encontrado aqui.

Parsing

O primeiro passo na interpretação de um programa é a análise sintática, ou parsing. O parser lê o texto de um programa e produz uma estrutura de dados que reflete a estrutura sintática do programa. Por exemplo, ao se deparar com uma expressão do tipo 2*3+4*5 em uma linguagem de programação típica, o parser produzirá uma árvore do tipo:

             +
            / \
           /   \
          *     *
         / \   / \
        2  3  4   5

Essa árvore reflete o agrupamento hierárquico dos elementos da expressão, segundo a sintaxe da linguagem em questão.

Uma vantagem de se implementar um Lisp é que o texto de um programa em Lisp é uma representação direta e uniforme da árvore sintática do programa. A expressão acima, por exemplo, seria representada por (+ (* 2 3) (* 4 5)) em Lisp. Isso torna o parser bastante simples.

De fato, ao contrário do que acontece com a maior parte das linguagens de programação, o significado de um programa em um Lisp tradicional não é definido em termos da sintaxe textual do programa. Ao invés disso, é definido um mapeamento da sintaxe textual para as estruturas em memória, e é a partir das estruturas que se define a semântica da linguagem. (+ 2 3) não "é" uma soma; (+ 2 3) é uma lista, que quando avaliada realizará uma soma. O resultado prático disso para nós neste momento é que é fácil de separar o parsing do resto do processo de interpretação em um Lisp; primeiro definimos os tipos de dados que podem ser encontrados no texto de um programa, e depois nos preocupamos com o que eles significam.

Nossa linguagem terá os seguintes tipos de dados:

Um programa conterá uma seqüência de expressões (formas, em Lispês) independentes. Escreveremos nosso parser como uma função que recebe o texto do programa, faz o parsing de uma forma, e retorna a estrutura correspondente e o que sobrou do texto. Posteriormente, chamaremos o parser repetidamente com o que sobrou de cada passo de parsing, até consumir todo o programa. O parser procurará o primeiro caractere não-em-branco da entrada, e tomará ações distintas dependendo do que ele for. Se for um (, lemos itens até encontrarmos o ) correspondente, e os acumulamos em uma lista. Se for outro caractere, lemos a entrada até o próximo parêntese ou espaço; se o que encontramos consistir apenas de dígitos (possivelmente precedidos por um -), estamos diante de um número; caso contrário, encontramos um símbolo.

function read(text) {
    text = text.trimLeft();        // Pula espaços iniciais.

    if (text == "")
        throw "EOF";

    else if (text[0] == "(") {
        var list = [];
        text = text.substring(1);  // Pula o '('.
        while ([item, text] = read(text), item!=")")
            text.push(item);
        return [list, text];
    }

    else if (text[0] == ")")
        return [")", text.substring(1)];

    else {
        match = text.match(/^[^\s()]+/);  // Lê tudo até o primeiro parêntese ou espaço.
        if (match[0].match(/^-?\d+$/))
            return [Number(match[0]), text.substring(match[0].length)];
        else
            return [match[0], text.substring(match[0].length)];
    }
}

Agora, se chamarmos read("1 2 3"), teremos como resultado [1, " 2 3"], e se chamarmos read("(+ 2 3)"), teremos [["+",2,3], ""]. Podemos nos dar por satisfeitos com o parser por ora.

Semântica

Feito o parsing, podemos fazer a interpretação propriamente dita, isto é, executar as operações indicadas pelo programa. Nossa linguagem é baseada em expressões; o significado de um programa é especificado em termos de como é avaliada (evaluated) cada expressão do programa, i.e., qual é o valor de cada expressão, e possíveis efeitos colaterais de avaliar uma expressão. (Outras linguagens possuem tanto expressões quanto statements, comandos que não possuem valor, mas apenas efeito colateral.)

Números são avaliados para si mesmos; o valor da expressão 2 é o próprio 2.

Símbolos são interpretados como referências a variáveis. Em qualquer ponto da avaliação, há um ambiente (environment), um conjunto de associações de nomes de variáveis aos seus respectivos valores. O valor de um símbolo é o valor da variável nomeada pelo símbolo no ambiente em que ele é avaliado. Se a variável não existir, um erro de execução ocorre.

É importante notar que trechos de programa diferentes podem ser avaliados em ambientes diferentes. É possível criar variáveis locais, visíveis em apenas um trecho do programa. Por exemplo, os parâmetros de uma função são visíveis apenas pelas expressões contidas na função. Cada chamada à função cria um novo ambiente, associando os parâmetros da função aos valores usados naquela chamada. Além dos parâmetros, as expressões da função também verão as variáveis definidas fora da função (desde que elas não tenham os mesmos nomes dos parâmetros). Como se pode ver, ambientes são hierárquicos: o valor de uma expressão é procurado primeiro no ambiente mais recentemente criado (e.g., os parâmetros da função); se a variável não for encontrada aí, ela será procurada em ambientes mais externos, até chegar no ambiente global. Representaremos ambientes no nosso interpretador por objetos simples (associações nome/valor) em JavaScript; ligaremos um ambiente ao ambiente imediatamente mais externo a ele através de um campo _parent no objeto. E.g., {x:1, y:2, _parent: {a:3, b:4}} representa um ambiente com as variáveis x e y, subordinado a um ambiente com as variáveis a e b. Para encontrar uma variável em um ambiente, usaremos a função lookup:

function lookup(name, env) {
    if (env) {
        if (env[name] !== undefined)
            // Se o nome está presente no ambiente atual, retornamo-lo.
            return env[name];
        else
            // Caso contrário, procuramos no ambiente pai.
            return lookup(name, env._parent);
    }
    else {
        // Se mandamos procurar no ambiente pai, e o ambiente pai não existe, paramos aqui.
        throw "Unbound variable " + name;
    }
}

Com isso, podemos começar a escrever o nosso avaliador de expressões. Ele recebe uma expressão para avaliar e o ambiente onde a expressão será avaliada:

function eval(code, env) {
    if (typeof(code) == "number")
        return code;
    else if (typeof(code) == "string")
        return lookup(code, env);

    ...

Falta definirmos como avaliaremos listas. Uma lista é avaliada da seguinte maneira: se o primeiro elemento da lista for o nome de um operador especial (como if), a avaliação segue segundo as regras do operador; caso contrário, o primeiro elemento é tomado como uma função a ser chamada usando os outros elementos como argumentos. Assim, (f x y) é interpretado como a chamada da função f com os argumentos x e y. Finalmente, se a lista for vazia, o resultado é a própria lista vazia.

Nossa linguagem tem quatro operadores especiais. Um deles, lambda, é usado para criar funções. (lambda (x y) (+ x y)) cria uma função que recebe dois argumentos, nomeados x e y, e retorna a soma dos dois. Representaremos as funções do nosso Lisp por um objeto em JavaScript contendo a lista de parâmetros, o corpo da função, e o ambiente em que a função foi criada. (A chamada da função pode ocorrer posteriormente em um ambiente completamente diferente do ambiente em que ela foi criada; queremos, entretanto, que o corpo da função seja avaliado no ambiente original da definição. Caso contrário, se alguém criar uma variável chamada + e chamar a função que acabamos de definir, ela não mais necessariamente somará dois números.)

    else if (code.length == 0)
        return [];  // Se for a lista vazia, retorna vazio.
    else {
        switch (code[0]) {
            case "lambda":
                return { type: "lambda", args: code[1], body: code[2], env: env };

lambda cria uma função, mas não lhe dá um nome. O segundo operador especial da nossa linguagem é o define: (define nome valor) cria uma variável chamada nome no ambiente atual, com o valor especificado. Para avaliar essa expressão, avaliamos o valor, e acrescentamos a variável ao ambiente:

            case "define":
                return env[code[1]] = eval(code[2], env);

O terceiro operador é o if: (if test then else) avalia test; se test for diferente da lista vazia, avalia-se then; senão, avalia-se else. O resultado da expressão inteira é o valor da expressão escolhida segundo o teste.

            case "if":
                if (eval(code[1], env).length !== 0)
                    return eval(code[2], env);
                else
                    return eval(code[3], env);

O último operador é o quote: (quote x) retorna x intacto, sem avaliar. O quote serve para quando queremos tratar um símbolo ou lista como um dado, não como um trecho de código a ser avaliado; (quote (+ 2 3)) simplesmente retorna a lista (+ 2 3) intacta.

            case "quote":
                return code[1];

Por último, o caso em que o primeiro elemento da lista não é um operador especial: devemos avaliar todos os elementos da lista, e chamar a função resultante da avaliação do primeiro:

            default:
                var evals = code.map(function(x) eval(x, env));
                var fun = evals[0];
                var args = evals.slice(1);

Na verdade teremos dois tipos de função no nosso interpretador: funções definidas pelo usuário, que possuem um corpo escrito em Lisp e que deveremos avaliar, e funções embutidas no interpretador (como +), que serão definidas diretamente em JavaScript. Representaremos as funções embutidas por funções do JavaScript; para avaliar uma chamada a uma função embutida, basta chamar a função com o resultado da avaliação dos argumentos:

                if (typeof(fun) == "function")
                    return fun.apply(null, args);

Se se trata de uma função definida pelo usuário, devemos avaliar o corpo da função em um ambiente associando os parâmetros da função com os argumentos com que foi chamada. Além disso, a função deve enxergar as variáveis que existiam quando ela foi definida; logo, o ambiente de definição deve ser linkado como ambiente pai.

                else if (typeof(fun) == "object" && fun.type == "lambda") {
                    var newenv = { _parent: fun.env };
                    for (var i in fun.args)
                        newenv[fun.args[i]] = args[i];

                    return eval(fun.body, newenv);
                }

Por último, se o primeiro item não for uma função, reportamos um erro:

                else
                    throw "Not a function: " + fun;
        }
    }
}

A parte importante do interpretador está pronta. Falta é definir um ambiente padrão, com algumas funções básicas. Eis algumas funções aritméticas:

var stdenv = {
    "+": function(x,y) x+y,
    "-": function(x,y) x-y,
    "*": function(x,y) x*y,
    "/": function(x,y) x/y,

Aqui as definições são bastante simples, pois os números do nosso Lisp são representados por números do JavaScript. Se não fosse esse o caso, teríamos um passo de conversão dos argumentos para números do JavaScript, e do resultado de volta para números do Lisp. As funções de comparação são menos diretas: devemos converter os booleanos do JavaScript (true e false) para os do Lisp (whatever e ()). (Qualquer coisa diferente de () é verdadeira, segundo o if; convencionalmente, se usa o símbolo t para representar "verdadeiro".)

    "=": function(x,y) x==y? "t" : [],
    "<": function(x,y) x<y?  "t" : [],
    ...

Outras funções importantes em um Lisp são as funções de manipulação de listas: (first ls) retorna o primeiro elemento de uma lista, (rest ls) retorna a lista sem o primeiro elemento, e (cons x ls) cria uma lista nova adicionando x à lista original.

    "first": function(ls): return ls[0],
    "rest" : function(ls): return ls.slice(1),
    "cons" : function(x,ls) : return [x].concat(ls),

Além disso, temos os testes null?, que testa se um objeto é a lista vazia, e cons?, que testa se um objeto é uma lista não-vazia.

    "null?": function(x) typeof(x)=="object" && x.length==0? "t" : [],
    "cons?": function(x) typeof(x)=="object" && x.length>0?  "t" : [],
}

E está pronto! Já podemos chamar nosso interpretador:

eval(read("(define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1))))))")[0], stdenv);
alert(eval(read("(fac 5)")[0], stdenv));

Não criamos uma função para ler todas as expressões de um programa e chamar eval com cada uma, nem criamos meios de chamar o interpretador sem escrevermos a chamada no fonte do interpretador ou em um prompt, mas esses são detalhes menores. Você pode usar a interface mencionada no começo do post para experimentar o interpretador.

** O nome do post foi inspirado no Write Yourself a Scheme in 48 Hours, um tutorial de Haskell.

Comentários / Comments

E esse tal de Lisp?

2012-04-10 01:26 -0300. Tags: comp, prog, lisp, em-portugues

Lisp é um negócio muito doido. Considere o seguinte trecho de código:

(+ 2 3)

Essa é uma expressão que, quando avaliada, produz a soma de 2 e 3. Mas mais que isso, essa expressão é uma lista de três elementos: +, 2 e 3.

Esse é o segredo por trás dos quilos de parênteses das linguagens da família Lisp: enquanto em uma linguagem convencional escrevemos os programas em uma sintaxe especial (e.g., 2+3), que é convertida em uma árvore sintática durante a compilação ou interpretação, em Lisp escrevemos a árvore sintática diretamente, usando uma notação uniforme de listas aninhadas. Quando escrevemos 2*3+4*5 em uma linguagem convencional, o compilador/interpretador produz internamente uma estrutura de dados muito similar ao (+ (* 2 3) (* 4 5)) do Lisp.

Aí você se pergunta: por que escrever a árvore sintática diretamente, se o compilador pode fazer isso por mim? Uma resposta é que escrever a árvore sintática diretamente torna a vida de quem escreve o compilador mais fácil. A segunda questão é: o que é que eu tenho a ver com isso? A reposta é que, em Lisp, quem escreve o compilador é VOCÊ!!

A principal característica que distingue os Lisps da maior parte das linguagens de programação é a extensibilidade: você pode adicionar novas construções sintáticas à linguagem, sem ter que alterar o compilador, através do mecanismo de macros. Macros em Lisp não são como as macros localizar-e-substituir do C. As macros do Lisp são funções, que recebem como entrada um trecho de código, e retornam como saída outro trecho de código. Definindo macros, você pode estender a linguagem como bem entender. E como a estrutura do código é uniformemente expressa por listas, você não precisa se preocupar em parsear texto; a macro já recebe a lista parseada que representa o código como entrada.

Por exemplo, imagine que você está programando em uma linguagem sem while. Teoricamente, você não precisa de while se você tiver if e goto. Na prática, é conveniente ter uma construção pronta ao invés de escrever o código com if/goto toda vez. Em uma linguagem como C, se o while não for um comando embutido na linguagem, não há o que fazer; para adicionar o while, teríamos que alterar o compilador. Porém, a transformação de um while em um if/goto é trivial, e poderia ser facilmente automatizada:

while (teste) {     =>    loopstart:
    comando1;               if (teste) {
    comando2;                   comando1;
}                               comando2;
                                goto loopstart;
                            }

A idéia da macro é permitir ao programador adicionar transformações de código desse tipo à linguagem. Em Common Lisp, a transformação que queremos é:

(while teste       =>    (tagbody loopstart
  comando1                 (when teste
  comando2)                  comando1
                             comando2
                             (go loopstart))

Essa transformação pode ser expressa com a seguinte macro:

(defmacro while (test &body body)
  `(tagbody loopstart
     (when ,test
       ,@body
       (go loopstart))))

Embora esse seja um exemplo simples, similar a uma macro localizar-e-substituir, uma macro pode realizar qualquer tipo de transformação no código. A macro é simplesmente uma função que transforma trechos de código em outros trechos de código, e tudo o que pode ser feito por uma função pode ser feito em uma macro. É possível implementar sub-linguagens com macros; por exemplo, poder-se-ia implementar uma macro para converter queries numa sintaxe SQL-like em código correspondente para realizar a query em um banco de dados. (De fato, existem bibliotecas que fazem isso em Common Lisp.) Macros executam em tempo de compilação, e portanto podem ser arbitrariamente complexas sem afetar o desempenho do código em tempo de execução (desde que o código retornado pela macro seja eficiente). As possibilidades são infinitas.

Se você tiver interesse na linguagem, recomendo ler o Practical Common Lisp. Fica o alerta ao leitor: Lisp é um negócio bizarro à primeira vista. Common Lisp, em particular, não é lá muito bonitinho e consistente em alguns aspectos (embora faça muito mais sentido com o tempo do que pode parecer inicialmente). Se você quiser aprender a linguagem a fundo, terá que se aproximar dela com a mente aberta e dar-lhe o benefício da dúvida em algumas ocasiões. Em verdade vos digo: vale muito a pena.

Comentários / Comments

Main menu

Recent posts

Recent comments

Tags

em-portugues (213) comp (148) prog (71) in-english (62) life (49) unix (38) pldesign (37) lang (32) random (28) about (28) mind (26) lisp (25) fenius (22) mundane (22) web (20) ramble (18) img (13) rant (12) hel (12) scheme (10) privacy (10) freedom (8) esperanto (7) music (7) lash (7) bash (7) academia (7) copyright (7) home (6) mestrado (6) shell (6) android (5) conlang (5) misc (5) emacs (5) latex (4) editor (4) etymology (4) php (4) worldly (4) book (4) politics (4) network (3) c (3) tour-de-scheme (3) security (3) kbd (3) film (3) wrong (3) cook (2) treta (2) poem (2) physics (2) x11 (2) audio (2) comic (2) lows (2) llvm (2) wm (2) philosophy (2) perl (1) wayland (1) ai (1) german (1) en-esperanto (1) golang (1) translation (1) kindle (1) pointless (1) old-chinese (1)

Elsewhere

Quod vide


Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.

Powered by Blognir.