Elmord's Magic Valley

Software, lingüística e rock'n'roll. Às vezes em Português, sometimes in English.

Posts com a tag: lisp

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 interpretada). (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 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. (Usarei JavaScript 1.8, o que significa que o código provavelmente só funciona no Firefox. Se houver demanda, traduzo para ECMAScript padrão*.)

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];

    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.

* "1995 - Brendan Eich reads up on every mistake ever made in designing a programming language, invents a few more, and creates LiveScript. Later, in an effort to cash in on the popularity of Java the language is renamed JavaScript. Later still, in an effort to cash in on the popularity of skin diseases the language is renamed ECMAScript." (A Brief, Incomplete, and Mostly Wrong History of Programming Languages)

** 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

Posts recentes

Comentários recentes

Tags

em-portugues (213) comp (133) prog (65) life (46) in-english (44) unix (33) pldesign (32) lang (31) random (28) about (26) mind (24) lisp (23) mundane (22) web (17) fenius (17) ramble (16) img (13) rant (12) hel (12) scheme (10) privacy (10) freedom (8) academia (7) esperanto (7) copyright (7) music (7) bash (7) lash (7) home (6) mestrado (6) shell (6) conlang (5) misc (5) emacs (4) politics (4) book (4) php (4) worldly (4) editor (4) latex (4) etymology (4) android (4) film (3) kbd (3) security (3) network (3) wrong (3) c (3) tour-de-scheme (3) poem (2) philosophy (2) comic (2) llvm (2) cook (2) treta (2) lows (2) physics (2) perl (1) german (1) wm (1) en-esperanto (1) audio (1) translation (1) old-chinese (1) kindle (1) pointless (1)

Elsewhere

Quod vide


Copyright © 2010-2019 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.