Projeto: Uma Linguagem de Programação

O avaliador, que determina o significado de expressões em uma linguagem de programação, é apenas outro programa.

Construir sua própria linguagem de programação é surpreendentemente fácil (desde que você não mire alto demais) e muito esclarecedor.

A principal coisa que quero mostrar neste capítulo é que não há nenhuma mágica envolvida na construção de uma linguagem de programação. Muitas vezes tive a sensação de que algumas invenções humanas eram tão imensamente inteligentes e complicadas que eu nunca seria capaz de entendê-las. Mas, com um pouco de leitura e experimentação, elas frequentemente acabam sendo bastante comuns.

Vamos construir uma linguagem de programação chamada Egg. Será uma linguagem pequena e simples—mas suficientemente poderosa para expressar qualquer computação que você consiga imaginar. Ela permitirá abstração simples baseada em funçãos.

Análise sintática

A parte mais imediatamente visível de uma linguagem de programação é sua sintaxe, ou notação. Um parser é um programa que lê um trecho de texto e produz uma estrutura de dados que reflete a estrutura do programa contido nesse texto. Se o texto não formar um programa válido, o parser deve apontar o erro.

Nossa linguagem terá uma sintaxe simples e uniforme. Tudo em Egg é uma expressão. Uma expressão pode ser o nome de uma associação, um número, uma string ou uma aplicação. Aplicações são usadas para chamadas de função, mas também para construções como if ou while.

Para manter o parser simples, strings em Egg não suportam nada como escapes com barra invertida. Uma string é simplesmente uma sequência de caracteres que não são aspas duplas, envolvida por aspas duplas. Um número é uma sequência de dígitos. Nomes de associações podem consistir em qualquer caractere que não seja espaço em branco e que não tenha um significado especial na sintaxe.

Aplicações são escritas da mesma forma que em JavaScript, colocando parênteses após uma expressão e tendo qualquer número de argumentos entre esses parênteses, separados por vírgulas.

do(define(x, 10),
   if(>(x, 5),
      print("large"),
      print("small")))

A uniformidade da linguagem Egg significa que coisas que são operadores em JavaScript (como >) são associações normais nesta linguagem, aplicadas como quaisquer outras funçãos. Como a sintaxe não tem o conceito de bloco, precisamos de uma construção do para representar a execução de várias coisas em sequência.

A estrutura de dados que o parser usará para descrever um programa consiste em objetos de expressão, cada um com uma propriedade type indicando o tipo de expressão e outras propriedades para descrever seu conteúdo.

Expressões do tipo "value" representam strings ou números literais. Sua propriedade value contém o valor de string ou número que representam. Expressões do tipo "word" são usadas para identificadores (nomes). Esses objetos têm uma propriedade name que contém o nome do identificador como string. Por fim, expressões "apply" representam aplicações. Elas têm uma propriedade operator que se refere à expressão que está sendo aplicada, além de uma propriedade args que contém um array de expressões de argumento.

A parte >(x, 5) do programa anterior seria representada assim:

{
  type: "apply",
  operator: {type: "word", name: ">"},
  args: [
    {type: "word", name: "x"},
    {type: "value", value: 5}
  ]
}

Essa estrutura de dados é chamada de árvore de sintaxe. Se você imaginar os objetos como pontos e as ligações entre eles como linhas conectando esses pontos, como mostrado no diagrama a seguir, a estrutura tem um formato semelhante a uma árvore. O fato de que expressões contêm outras expressões, que por sua vez podem conter mais expressões, é semelhante à forma como galhos de uma árvore se ramificam e se subdividem.

Compare isso com o parser que escrevemos para o formato de arquivo de configuração no Capítulo 9, que tinha uma estrutura simples: ele dividia a entrada em linhas e tratava essas linhas uma de cada vez. Havia apenas algumas formas simples que uma linha podia ter.

Aqui precisamos encontrar uma abordagem diferente. As expressões não são separadas em linhas, e elas têm uma estrutura recursiva. Expressões de aplicação contêm outras expressões.

Felizmente, esse problema pode ser resolvido muito bem escrevendo uma função de parser que seja recursiva de uma forma que reflita a natureza recursiva da linguagem.

Definimos uma função parseExpression que recebe uma string como entrada. Ela retorna um objeto contendo a estrutura de dados da expressão no início da string, junto com a parte da string que sobra após analisar essa expressão. Ao analisar subexpressões (o argumento de uma aplicação, por exemplo), essa função pode ser chamada novamente, produzindo a expressão do argumento bem como o texto restante. Esse texto, por sua vez, pode conter mais argumentos ou pode ser o parêntese de fechamento que termina a lista de argumentos.

Esta é a primeira parte do parser:

function parseExpression(program) {
  program = skipSpace(program);
  let match, expr;
  if (match = /^"([^"]*)"/.exec(program)) {
    expr = {type: "value", value: match[1]};
  } else if (match = /^\d+\b/.exec(program)) {
    expr = {type: "value", value: Number(match[0])};
  } else if (match = /^[^\s(),#"]+/.exec(program)) {
    expr = {type: "word", name: match[0]};
  } else {
    throw new SyntaxError("Unexpected syntax: " + program);
  }

  return parseApply(expr, program.slice(match[0].length));
}

function skipSpace(string) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

Como Egg, assim como JavaScript, permite qualquer quantidade de espaço em branco entre seus elementos, precisamos remover repetidamente o espaço em branco do início da string do programa. A função skipSpace ajuda nisso.

Após ignorar qualquer espaço inicial, parseExpression usa três expressões regulares para identificar os três elementos atômicos que Egg suporta: strings, números e palavras. O parser constrói um tipo diferente de estrutura de dados dependendo de qual expressão corresponde. Se a entrada não corresponder a uma dessas três formas, ela não é uma expressão válida, e o parser lança um erro. Usamos o construtor SyntaxError aqui. Esta é uma classe de exceção definida pelo padrão, como Error, mas mais específica.

Em seguida, cortamos a parte que foi reconhecida da string do programa e a passamos, junto com o objeto da expressão, para parseApply, que verifica se a expressão é uma aplicação. Se for, ele analisa uma lista de argumentos entre parênteses.

function parseApply(expr, program) {
  program = skipSpace(program);
  if (program[0] != "(") {
    return {expr: expr, rest: program};
  }

  program = skipSpace(program.slice(1));
  expr = {type: "apply", operator: expr, args: []};
  while (program[0] != ")") {
    let arg = parseExpression(program);
    expr.args.push(arg.expr);
    program = skipSpace(arg.rest);
    if (program[0] == ",") {
      program = skipSpace(program.slice(1));
    } else if (program[0] != ")") {
      throw new SyntaxError("Expected ',' or ')'");
    }
  }
  return parseApply(expr, program.slice(1));
}

Se o próximo caractere no programa não for um parêntese de abertura, isso não é uma aplicação, e parseApply retorna a expressão que recebeu. Caso contrário, ele ignora o parêntese de abertura e cria o objeto da árvore de sintaxe para essa expressão de aplicação. Em seguida, chama recursivamente parseExpression para analisar cada argumento até encontrar um parêntese de fechamento. A recursão é indireta, através de parseApply e parseExpression chamando um ao outro.

Como uma expressão de aplicação pode ela mesma ser aplicada (como em multiplier(2)(1)), parseApply deve, após analisar uma aplicação, chamar a si mesma novamente para verificar se outro par de parênteses vem a seguir.

Isso é tudo que precisamos para analisar Egg. Envolvemos isso em uma função conveniente parse que verifica se chegou ao fim da string de entrada após analisar a expressão (um programa Egg é uma única expressão) e que nos fornece a estrutura de dados do programa.

function parse(program) {
  let {expr, rest} = parseExpression(program);
  if (skipSpace(rest).length > 0) {
    throw new SyntaxError("Unexpected text after program");
  }
  return expr;
}

console.log(parse("+(a, 10)"));
// → {type: "apply",
//    operator: {type: "word", name: "+"},
//    args: [{type: "word", name: "a"},
//           {type: "value", value: 10}]}

Funciona! Não fornece informações muito úteis quando falha e não armazena a linha e a coluna em que cada expressão começa, o que poderia ser útil ao relatar erros depois, mas é suficiente para nossos propósitos.

O avaliador

O que podemos fazer com a árvore de sintaxe de um programa? Executá-la, claro! E é isso que o avaliador faz. Você fornece a ele uma árvore de sintaxe e um objeto de escopo que associa nomes a valores, e ele avaliará a expressão que a árvore representa e retornará o valor produzido.

const specialForms = Object.create(null);

function evaluate(expr, scope) {
  if (expr.type == "value") {
    return expr.value;
  } else if (expr.type == "word") {
    if (expr.name in scope) {
      return scope[expr.name];
    } else {
      throw new ReferenceError(
        `Undefined binding: ${expr.name}`);
    }
  } else if (expr.type == "apply") {
    let {operator, args} = expr;
    if (operator.type == "word" &&
        operator.name in specialForms) {
      return specialForms[operator.name](expr.args, scope);
    } else {
      let op = evaluate(operator, scope);
      if (typeof op == "function") {
        return op(...args.map(arg => evaluate(arg, scope)));
      } else {
        throw new TypeError("Applying a non-function.");
      }
    }
  }
}

O avaliador tem código para cada um dos tipos de expressão. Uma expressão de valor literal produz seu valor. (Por exemplo, a expressão 100 avalia para o número 100.) Para uma associação, devemos verificar se ela está de fato definida no escopo e, se estiver, obter o valor da associação.

Aplicações são mais complexas. Se forem uma forma especial, como if, não avaliamos nada—apenas passamos as expressões de argumento, junto com o escopo, para a função que trata essa forma. Se for uma chamada normal, avaliamos o operador, verificamos se é uma função e a chamamos com os argumentos avaliados.

Usamos valores de função comuns de JavaScript para representar os valores de função de Egg. Voltaremos a isso mais adiante, quando a forma especial fun for definida.

A estrutura recursiva de evaluate se assemelha à estrutura do parser, e ambas refletem a estrutura da própria linguagem. Também seria possível combinar o parser e o avaliador em uma única função e avaliar durante a análise, mas separá-los dessa forma torna o programa mais claro e flexível.

Isso é realmente tudo o que é necessário para interpretar Egg. É simples assim. Mas, sem definir algumas formas especiais e adicionar alguns valores úteis ao ambiente, ainda não dá para fazer muita coisa com essa linguagem.

Formas especiais

O objeto specialForms é usado para definir sintaxe especial em Egg. Ele associa palavras a funções que avaliam essas formas. Atualmente está vazio. Vamos adicionar if.

specialForms.if = (args, scope) => {
  if (args.length != 3) {
    throw new SyntaxError("Wrong number of args to if");
  } else if (evaluate(args[0], scope) !== false) {
    return evaluate(args[1], scope);
  } else {
    return evaluate(args[2], scope);
  }
};

A construção if de Egg espera exatamente três argumentos. Ela avaliará o primeiro e, se o resultado não for o valor false, avaliará o segundo. Caso contrário, o terceiro será avaliado. Essa forma if é mais parecida com o operador ternário ?: do JavaScript do que com o if do JavaScript. É uma expressão, não uma instrução, e produz um valor—ou seja, o resultado do segundo ou terceiro argumento.

Egg também difere do JavaScript na forma como trata o valor da condição em if. Ele considera apenas o valor false como falso, não coisas como zero ou a string vazia.

O motivo pelo qual precisamos representar if como uma forma especial, em vez de uma função comum, é que todos os argumentos de funções são avaliados antes da função ser chamada, enquanto if deve avaliar apenas ou seu segundo ou seu terceiro argumento, dependendo do valor do primeiro.

A forma while é semelhante.

specialForms.while = (args, scope) => {
  if (args.length != 2) {
    throw new SyntaxError("Wrong number of args to while");
  }
  while (evaluate(args[0], scope) !== false) {
    evaluate(args[1], scope);
  }

  // Como undefined não existe em Egg, retornamos false,
  // por falta de um resultado significativo
  return false;
};

Outro bloco básico é do, que executa todos os seus argumentos de cima para baixo. Seu valor é o valor produzido pelo último argumento.

specialForms.do = (args, scope) => {
  let value = false;
  for (let arg of args) {
    value = evaluate(arg, scope);
  }
  return value;
};

Para poder criar associações e atribuir novos valores a elas, também criamos uma forma chamada define. Ela espera uma palavra como primeiro argumento e uma expressão que produza o valor a ser atribuído a essa palavra como segundo argumento. Como define, assim como tudo, é uma expressão, ela deve retornar um valor. Vamos fazer com que retorne o valor que foi atribuído (assim como o operador = do JavaScript).

specialForms.define = (args, scope) => {
  if (args.length != 2 || args[0].type != "word") {
    throw new SyntaxError("Incorrect use of define");
  }
  let value = evaluate(args[1], scope);
  scope[args[0].name] = value;
  return value;
};

O ambiente

O escopo aceito por evaluate é um objeto com propriedades cujos nomes correspondem a nomes de associações e cujos valores correspondem aos valores aos quais essas associações estão ligadas. Vamos definir um objeto para representar o escopo global.

Para poder usar a construção if que acabamos de definir, precisamos ter acesso a valores Boolean. Como existem apenas dois valores booleanos, não precisamos de sintaxe especial para eles. Simplesmente associamos dois nomes aos valores true e false e os usamos.

const topScope = Object.create(null);

topScope.true = true;
topScope.false = false;

Agora podemos avaliar uma expressão simples que nega um valor booleano.

let prog = parse(`if(true, false, true)`);
console.log(evaluate(prog, topScope));
// → false

Para fornecer aritmética básica e comparação de operadores, também adicionaremos alguns valores de função ao escopo. Para manter o código curto, usaremos Function para sintetizar várias funções de operadores em um loop, em vez de defini-las individualmente.

for (let op of ["+", "-", "*", "/", "==", "<", ">"]) {
  topScope[op] = Function("a, b", `return a ${op} b;`);
}

Também é útil ter uma forma de saída de valores, então vamos encapsular console.log em uma função e chamá-la de print.

topScope.print = value => {
  console.log(value);
  return value;
};

Isso nos dá ferramentas elementares suficientes para escrever programas simples. A função a seguir fornece uma maneira conveniente de analisar um programa e executá-lo em um escopo novo:

function run(program) {
  return evaluate(parse(program), Object.create(topScope));
}

Usaremos cadeias de protótipos de objetos para representar escopos aninhados, de modo que o programa possa adicionar associações ao seu escopo local sem alterar o escopo de nível superior.

run(`
do(define(total, 0),
   define(count, 1),
   while(<(count, 11),
         do(define(total, +(total, count)),
            define(count, +(count, 1)))),
   print(total))
`);
// → 55

Este é o programa que vimos várias vezes antes, que calcula a soma dos números de 1 a 10, expresso em Egg. Ele é claramente mais feio do que o programa equivalente em JavaScript—mas não é ruim para uma linguagem implementada em menos de 150 linhas de código.

Funções

Uma linguagem de programação sem funções é, de fato, uma linguagem de programação ruim. Felizmente, não é difícil adicionar uma construção fun, que trata seu último argumento como o corpo da função e usa todos os argumentos anteriores como os nomes dos parâmetros da função.

specialForms.fun = (args, scope) => {
  if (!args.length) {
    throw new SyntaxError("Functions need a body");
  }
  let body = args[args.length - 1];
  let params = args.slice(0, args.length - 1).map(expr => {
    if (expr.type != "word") {
      throw new SyntaxError("Parameter names must be words");
    }
    return expr.name;
  });

  return function(...args) {
    if (args.length != params.length) {
      throw new TypeError("Wrong number of arguments");
    }
    let localScope = Object.create(scope);
    for (let i = 0; i < args.length; i++) {
      localScope[params[i]] = args[i];
    }
    return evaluate(body, localScope);
  };
};

Funções em Egg obtêm seu próprio escopo local. A função produzida pela forma fun cria esse escopo local e adiciona as associações dos argumentos a ele. Em seguida, ela avalia o corpo da função nesse escopo e retorna o resultado.

run(`
do(define(plusOne, fun(a, +(a, 1))),
   print(plusOne(10)))
`);
// → 11

run(`
do(define(pow, fun(base, exp,
     if(==(exp, 0),
        1,
        *(base, pow(base, -(exp, 1)))))),
   print(pow(2, 10)))
`);
// → 1024

Compilação

O que construímos é um interpretador. Durante a avaliação, ele atua diretamente sobre a representação do programa produzida pelo parser.

Compilação é o processo de adicionar outra etapa entre a análise e a execução de um programa, que transforma o programa em algo que pode ser avaliado de forma mais eficiente ao realizar o máximo de trabalho possível antecipadamente. Por exemplo, em linguagens bem projetadas é evidente, para cada uso de uma associação, a qual associação está sendo referida, sem realmente executar o programa. Isso pode ser usado para evitar procurar a associação pelo nome toda vez que ela é acessada, em vez disso obtendo-a diretamente de algum local de memória predeterminado.

Tradicionalmente, compilação envolve converter o programa para código de máquina, o formato bruto que o processador de um computador pode executar. Mas qualquer processo que converta um programa para uma representação diferente pode ser considerado compilação.

Seria possível escrever uma estratégia alternativa de avaliação para Egg, uma que primeiro converta o programa para um programa JavaScript, use Function para invocar o compilador JavaScript nele e execute o resultado. Quando feito corretamente, isso faria o Egg rodar muito rápido enquanto ainda seria bastante simples de implementar.

Se você se interessa por esse tema e está disposto a dedicar algum tempo, eu o incentivo a tentar implementar tal compilador como exercício.

Trapaceando

Quando definimos if e while, você provavelmente percebeu que eles eram mais ou menos envoltórios triviais sobre os próprios if e while do JavaScript. Da mesma forma, os valores em Egg são apenas valores comuns do JavaScript. Fazer a ponte para um sistema mais primitivo, como o código de máquina que o processador entende, exige mais esforço—mas a forma como funciona se assemelha ao que estamos fazendo aqui.

Embora a linguagem de brinquedo deste capítulo não faça nada que não possa ser feito melhor em JavaScript, existem situações em que escrever pequenas linguagens ajuda a realizar trabalho de verdade.

Tal linguagem não precisa se parecer com uma linguagem de programação típica. Se o JavaScript não viesse com expressões regulares, por exemplo, você poderia escrever seu próprio parser e avaliador para expressões regulares.

Ou imagine que você está construindo um programa que torna possível criar rapidamente parsers fornecendo uma descrição lógica da linguagem que eles precisam analisar. Você poderia definir uma notação específica para isso e um compilador que a compile em um programa de parser.

expr = number | string | name | application

number = digit+

name = letter+

string = '"' (! '"')* '"'

application = expr '(' (expr (',' expr)*)? ')'

Isso é o que geralmente se chama de linguagem específica de domínio (DSL), uma linguagem adaptada para expressar um domínio restrito de conhecimento. Tal linguagem pode ser mais expressiva do que uma linguagem de propósito geral porque é projetada para descrever exatamente as coisas que precisam ser descritas em seu domínio e nada mais.

Exercícios

Arrays

Adicione suporte a arrays em Egg adicionando as três funções a seguir ao escopo superior: array(...values) para construir um array contendo os valores dos argumentos, length(array) para obter o comprimento de um array e element(array, n) para buscar o n-ésimo elemento de um array.

// Modifique estas definições...

topScope.array = "...";

topScope.length = "...";

topScope.element = "...";

run(`
do(define(sum, fun(array,
     do(define(i, 0),
        define(sum, 0),
        while(<(i, length(array)),
          do(define(sum, +(sum, element(array, i))),
             define(i, +(i, 1)))),
        sum))),
   print(sum(array(1, 2, 3))))
`);
// → 6

Closure

A forma como definimos fun permite que funções em Egg referenciem o escopo ao redor, permitindo que o corpo da função use valores locais que estavam visíveis no momento em que a função foi definida, assim como as funções em JavaScript fazem.

O programa a seguir ilustra isso: a função f retorna uma função que soma seu argumento ao argumento de f, o que significa que ela precisa de acesso ao escopo local dentro de f para poder usar a associação a.

run(`
do(define(f, fun(a, fun(b, +(a, b)))),
   print(f(4)(5)))
`);
// → 9

Volte à definição da forma fun e explique qual mecanismo faz isso funcionar.

Comentários

Seria bom se pudéssemos escrever comentários em Egg. Por exemplo, sempre que encontrarmos um símbolo de hash (#), poderíamos tratar o restante da linha como um comentário e ignorá-lo, de forma semelhante a // em JavaScript.

Não precisamos fazer grandes mudanças no parser para suportar isso. Podemos simplesmente alterar skipSpace para pular comentários como se fossem espaço em branco, de modo que todos os pontos onde skipSpace é chamado agora também pulem comentários. Faça essa alteração.

// Esta é a antiga skipSpace. Modifique-a...
function skipSpace(string) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

console.log(parse("# hello\nx"));
// → {type: "word", name: "x"}

console.log(parse("a # one\n   # two\n()"));
// → {type: "apply",
//    operator: {type: "word", name: "a"},
//    args: []}

Corrigindo o escopo

Atualmente, a única maneira de atribuir um valor a uma associação é define. Essa construção funciona tanto para definir novas associações quanto para dar um novo valor às existentes.

Essa ambiguidade causa um problema. Quando você tenta dar um novo valor a uma associação não local, você acaba definindo uma associação local com o mesmo nome em vez disso. Algumas linguagens funcionam assim por design, mas eu sempre achei uma forma estranha de lidar com escopo.

Adicione uma forma especial set, semelhante a define, que atribui um novo valor a uma associação, atualizando a associação em um escopo externo se ela não existir no escopo interno. Se a associação não estiver definida em lugar nenhum, lance um ReferenceError (outro tipo de erro padrão).

A técnica de representar escopos como objetos simples, que até agora tornou as coisas convenientes, vai atrapalhar um pouco neste ponto. Talvez você queira usar a função Object.getPrototypeOf, que retorna o protótipo de um objeto. Lembre-se também de que você pode usar Object.hasOwn para descobrir se um determinado objeto possui uma propriedade.

specialForms.set = (args, scope) => {
  // Seu código aqui.
};

run(`
do(define(x, 4),
   define(setx, fun(val, set(x, val))),
   setx(50),
   print(x))
`);
// → 50
run(`set(quux, true)`);
// → Algum tipo de ReferenceError