S-Expressions (expressões simbólicas) • Capítulo 9

Listas e Lisps


lisp

ALL CAPS • TÃO CERTO E TÃO ERRADO.

Lisps são famosos por ter pouca distinção entre dados e código. Elas usam as mesmas estruturas para representar ambos. Isso as permite fazerem muitas coisas poderosas que outras linguagens não podem fazer. Se queremos este poder para nossa linguagem de programação teremos que separar o processo de ler entrada, e avaliar a entrada que armazenamos.

O resultado final deste capítulo diferirá apenas um pouco em termos de comportamento do capítulo anterior. Isto é porque vamos gastar algum tempo mudando como as coisas funcionam internamente. Isto é chamado refatorar e fará nossa vida muito mais fácil mais adiante. Como no preparo uma refeição, só porque estamos colocando comida em pratos não significa que estamos perdendo tempo. Às vezes a antecipação é ainda melhor que comer!

Para armazenar o programa teremos que criar uma estrutura interna de lista que é construída recursivamente com números, símbolos e outras listas. Em Lisp, esta estrutura é comumente chamada de S-Expression significando Symbolic Expression (expressão simbólica). Nós ampliaremos nossa estrutura lval para ser capaz de representá-la. O comportamento de avaliação das S-Expressions é o comportamento típico de Lisps, que já estamos acostumados até aqui. Para avaliar uma S-Expression nós olhamos ao primeiro item na lista, e assumimos que é o operador. A seguir olhamos para todos os outros itens na lista, e tomamo-los como operandos para obter o resultado.

Introduzindo S-Expressions vamos finalmente entrar no mundo de Lisp.

Apontadores


Em C, nenhum conceito de listas pode ser explorado sem lidar devidamente com apontadores. Apontadores são um aspecto de C famosamente mal-compreendido. Eles são difíceis de ensinar porque enquanto são conceitualmente muito simples, eles vêm com toda uma nova terminologia, e muitas vezes não tem um caso de uso claro. Isto faz eles parecerem muito mais monstruosos do que realmente são. Felizmente para nós, temos alguns casos de uso ideais, e ambos são extremamente típicos em C, e provavelmente serão como você vai acabar usando apontadores 90% das vezes.

O motivo porque precisamos apontadores em C tem a ver com como a chamada de funções funciona. Quando você chama uma função em C, os argumentos são passados por valor. Isto significa que uma cópia deles é passada para a função que você chama. Isto é verdade para int, long, char, e tipos struct definidos pelo usuários como o lval. A maioria das vezes isto é ótimo, mas ocasionalmente isto causa alguns problemas.

Um problema comum ocorre quando temos um grande struct contendo muitos outros sub structs que desejamos passar por aí. Cada vez que chamamos uma função precisamos criar uma outra cópia dele. De repente a quantidade de dados que precisa ser copiada pra todo lado só pra chamar uma função pode se tornar enorme.

Um segundo problema é este: Quando definimos um struct, ele é sempre de um tamanho fixo. Ele tem um tamanho limitado de campos, e cada um destes campos precisa ser um struct que é ele próprio limitado em tamanho. Se quero chamar uma função apenas com uma lista de coisas, onde o número de coisas varia de chamada para chamada, claramente não posso usar um struct para fazer isso.

Para contornar estes problemas os desenvolvedores de C (ou, você sabe... alguém) apareceu com uma ideia inteligente. Eles imaginaram a memória do computador como uma única lista de bytes. Nesta lista, cada byte pode ser dado o seu próprio índice global, ou posição. Mais ou menos como o número de uma casa. O primeiro byte é numerado 0, o segundo é 1, etc.

Nesse caso, todos os dados no computador, incluindo os structs e as variáveis usadas no programa rodando atualmente, começam em algum índice nesta lista enorme. Se, em vez de copiar o dado para a função, nós copiemos um número representando o índice onde este dados começa, a função sendo chamada pode buscar qualquer quantidade de dados que ela quiser.

Usando endereços em vez de dados de verdade, permitimos uma função acessar e modificar alguma localização em memória sem ter que copiar qualquer dado. Funções podem também usar apontadores para fazer outras coisas, como jogar dados para algum endereço fornecido como entrada.

Como o tamanho total da memória do computador é fixo, o número de bytes necessário para representar um endereço é sempre o mesmo. Mas se mantermos controle sobre ele, o número de bytes que o endereço aponta pode crescer ou encolher. Isto significa que podemos criar uma estrutura de dados com tamanho variado e ainda passá-la para uma função, que pode inspecioná-la e modificá-la.

Então um apontador é apenas um número. Um número representando o índice inicial de algum dado na memória. O tipo do apontador indica a nós e ao compilador, qual tipo de dado pode ser acessado nesta localização.

Podemos declarar tipos de apontadores sufixando os existentes com o caractere *. Já vimos alguns exemplos disso com mpc_parser_t*, mpc_ast_t*, e char*.

Para criar um apontador para algum dado, precisamos pegar o seu índice, ou endereço. Para obter o endereço de algum dado usamos o operador endereço de: &. Novamente você já viu isso antes quando passamos um apontador para mpc_parse para que ela jogasse a saída no nosso mpc_result_t.

Finalmente, para obter o dado de um endereço (operação chamada de de-referenciar), usamos o operador * no lado esquerdo da variável. Para obter o dado no campo de um apontador para uma estrutura, usamos a flecha ->. Isto você viu no capítulo 7.

O Stack & O Heap


Eu disse que a memória pode ser visualizada como uma longa lista de bytes. Na verdade é melhor imaginá-la como dividida em duas seções. Estas seções são chamadas o stack (ou, a pilha) e o heap (tradução a grosso modo, o monte).

Alguns de vocês pode ter ouvido histórias sobre essas localizações misteriosas, tais como "a pilha sempre cresce para baixo mas o heap cresce para cima", ou "podem haver muitas pilhas/stacks, mas apenas um heap". Este tipo de coisa não importa muito. Lidar com a pilha e o heap em C pode ser complexo, mas não precisa ser um mistério. Em essência, eles são apenas duas seções da memória usadas para duas tarefas diferentes.

O Stack, ou a pilha

construção

A Pilha • Tipo a que você faz com tijolos.

O Stack é a memória onde seu programa vive. É onde todas suas variáveis temporárias e estruturas de dados existem enquanto você as manipula e as altera. Cada vez que você chama uma função, uma nova área do stack é separada para ela usar. Dentro desta área são colocadas variáveis locais, cópias de quaisquer argumentos passados à função, assim como alguns dados contabilizando coisas como quem chamou a função, e o que fazer quando terminar. Quando a função terminar, a área que usou é desalocada, pronta para ser usada novamente por outra coisa.

Gosto de pensar na pilha como o local de uma construção. Cada vez que precisamos fazer algo novo, reservamos uma pequena seção do espaço o suficiente para ferramentas e materiais, e trabalhamos nela. Podemos ir a outras partes do lugar, ou até mesmo sair do lugar, se precisarmos de certas coisas, mas todo nosso trabalho é feito nessa seção reservada. Tendo terminado a tarefa, levamos o que construímos para um novo lugar e limpamos aquela seção do espaço que usamos para fazê-lo.

O Heap

storage

O Heap • U LOCK. KEEP KEY.

O Heap (ou, monte) é uma seção de memória reservada para armazenar objetos com vida útil mais longa. A memória nesta área precisa ser manualmente alocada e desalocada. Para alocar nova memória, utiliza-se a função malloc. Esta função recebe como entrada o número de bytes desejados, e retorna um apontador para o novo bloco de memória com aquela quantidade de bytes reservada.

Ao terminar de usar a memória nesse espaço, ela deve ser liberada novamente. Para fazer isso, o apontador recebido da malloc deve ser passado para a função free.

Usar o Heap é mais complicadinho que o Stack, porque precisa que o programador lembre de chamar free e de chamá-la corretamente. Caso contrário, o programa pode continuamente alocar mais e mais memória. Isto se chama um vazamento de memória, ou memory leak. Uma regra fácil para evitar isso é se certificar que para cada malloc haja um (e apenas um) free. Se isto puder ser garantido, o programa deve estar tratando o Heap corretamente.

Eu imagino o Heap como um grande serviço de self-storage ou auto armazenamento. Chamamos a recepção com malloc e pedimos um certo número de caixas. Com estas caixas podemos fazer o que quiser, e sabemos que elas vão persistir não importa quão bagunçado o local da construção fique. Podemos trazer ou levar coisas entre o self-storage e o local da construção. É útil armazenar materiais e objetos grandes que só precisamos usar de vez em quando. O único problema é que temos que lembrar de chamar a recepção do self-storage novamente com free quando acabarmos. Senão teremos requisitado todas as caixas, não teremos mais espaço e pagaremos uma conta alta.

Parsing Expressions


Como estamos agora pensando em S-Expressions (expressões simbólicas), e não mais em notação polonesa, precisamos atualizar nosso parser (analisador sintático). A sintaxe para S-Expressions é simples. É apenas um certo número de outras expressões entre parênteses, onde uma expressão pode ser um número, operador, ou outra S-Expression. Podemos modificar nossas regras de parsing existentes para refletir isso. Também vamos renomear nossa regra operator para symbol. Faremos isso antecipando a adição de mais operadores, variáveis e função mais tarde.

mpc_parser_t* Number = mpc_new("number");
mpc_parser_t* Symbol = mpc_new("symbol");
mpc_parser_t* Sexpr  = mpc_new("sexpr");
mpc_parser_t* Expr   = mpc_new("expr");
mpc_parser_t* Lispy  = mpc_new("lispy");

mpca_lang(MPCA_LANG_DEFAULT,
  "                                          \
    number : /-?[0-9]+/ ;                    \
    symbol : '+' | '-' | '*' | '/' ;         \
    sexpr  : '(' <expr>* ')' ;               \
    expr   : <number> | <symbol> | <sexpr> ; \
    lispy  : /^/ <expr>* /$/ ;               \
  ",
  Number, Symbol, Sexpr, Expr, Lispy);

Devemos também lembrar de limpar/liberar essas regras ao sair.

mpc_cleanup(5, Number, Symbol, Sexpr, Expr, Lispy);

Estrutura da Expressão


Precisamos duma maneira de armazenar S-Expressions como lval. Isto significa que vamos também precisar armazenar Symbols e Numbers. Vamos adicionar dois novos tipos ao enum. O primeiro é LVAL_SYM, que vamos usar para representar operadores como +. O segundo novo tipo é LVAL_SEXPR, que vamos usar para representar S-Expressions.

enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR };

S-Expressions são listas de tamanho variável de outros valores. Como aprendemos no começo deste capítulo, não podemos criar structs de tamanho variável, então vamos precisar usar um apontador. Vamos criar um campo apontador cell que aponta para um local onde armazenamos uma lista de lval*. Mais especificamente, apontadores para os outros lval individuais. Nosso campo deve portanto ser um tipo apontador duplo lval**. Um apontador para apontadores de lval. Também vamos precisar controlar quantos lval* estão nessa lista, então adicionamos um campo extra count para gravar isso.

Para representar símbolos vamos usar uma string. Também vamos mudar a representação dos erros para uma string. Isto significa que podemos armazenar uma mensagem de erro única em vez de um código de erro. Isto fará a reportagem de erros melhor e mais flexível, e podemos nos livrar do enum de erros original. Nosso lval atualizado fica assim:

typedef struct lval {
  int type;
  long num;
  /* Tipos Error e Symbol tem alguns dados string */
  char* err;
  char* sym;
  /* Contagem e Apontador para uma lista de "lval*" */
  int count;
  struct lval** cell;
} lval;

Existem apontadores para apontadores para apontadores?

Existe uma velha piada de programação que diz que você avalia programadores C pelo número de estrelas (asteriscos) nos apontadores deles.

Programadores iniciantes podem apenas usar char* e de vez em quando algum int*, então são chamados programadores uma estrela. A maioria dos programadores intermediários contém algum apontador duplo como lval**. Estes programadores são portando chamados programadores duas estrelas. Encontrar um apontador triplo é uma coisa especial. Você deve estar vendo o trabalho de alguém imponente e terrível, escrevendo código que não foi feito para ser lido por olhos mortais. Por isso, ser chamado um programador três estrelas é raramente um elogio.

Que eu saiba, um apontador quádruplo nunca foi visto no mundo afora.

O que a palavra-chave struct faz ali?

Nossa definição nova do lval precisa conter uma referência a si própria. Isto significa que temos que modificar um pouco como ela é definida. Antes de abrir chaves podemos colocar o nome do struct e a seguir referenciar isso dentro da definição usando struct lval. Embora um struct pode se referenciar ao seu próprio tipo, ele precisa conter apenas apontadores para seu próprio tipo, não o seu próprio tipo diretamente. Caso contrário, o tamanho do struct se referenciaria a si mesmo, e cresceria infinitamente em tamanho quando você tentasse calculá-lo!

Construtores & Destruidores


Podemos mudar nossas funções de construção de lval para retornar apontadores para um lval, em vez de um lval diretamente. Isto tornará mais fácil o controle das variáveis lval. Para isso precisamos usar malloc com a função sizeof para alocar espaço o suficiente para o struct lval, e a seguir preencher os campos com as informações relevantes usando o operador seta ->.

Quando construímos um lval seus campos podem conter apontadores para outras coisas que foram alocadas no heap. Isto significa que precisamos ser cuidadosos. Sempre que terminamos de usar um lval também precisamos apontar as coisas que ele está apontando no heap. Teremos que fazer uma regra para nós mesmos. Sempre que liberarmos a memória alocada para um lval, também temos que liberar todas as coisas que ele estiver apontando.

/* Constroi um apontador para um novo lval Number */ 
lval* lval_num(long x) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_NUM;
  v->num = x;
  return v;
}
/* Constroi um apontador para um novo lval Error */ 
lval* lval_err(char* m) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_ERR;
  v->err = malloc(strlen(m) + 1);
  strcpy(v->err, m);
  return v;
}
/* Constroi um novo apontador para um novo lval Symbol */ 
lval* lval_sym(char* s) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SYM;
  v->sym = malloc(strlen(s) + 1);
  strcpy(v->sym, s);
  return v;
}
/* Um apontador para um novo lval Sexpr vazio */
lval* lval_sexpr(void) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}

O que é NULL?

NULL é uma constante especial que aponta para o local da memória 0. Em muitos lugares ele é usado como convenção para significar um dado vazio ou um não-valor. Acima nós o usamos para especificar que temos um tipo apontador, mas que não está apontando para nenhum dado. Você verá o NULL aparecer bastante mais adiante, então lembre-se de prestar atenção nele.

Por que você está usando strlen(s) + 1?

Em C, strings são null terminated, isto é, terminadas com null. Isto significa que o último caractere delas é sempre o caractere zero \0. Esta é uma convenção em C para sinalizar o fim de uma string. É importante que todas as strings sejam armazenadas dessa maneira, senão o programa falha de maneiras desagradáveis.

A função strlen retorna somente o número de bytes numa string excluindo o terminador null. Por isso precisamos adicionar um, para nos assegurar que existe espaço suficiente alocado para tudo!

Precisamos agora de uma função especial para deletar lval*. Esta deve chamar free no próprio apontador para liberar a memória adquirida do malloc, mas mais importante, deve inspecionar o tipo do lval, e liberar qualquer memória apontada pelos seus campos. Se combinarmos cada chamada com uma das funções de construção com lval_del podemos nos certificar de não ter vazamentos de memória.

void lval_del(lval* v) {

  switch (v->type) {
    /* Nao faz nada especial para o tipo numero */
    case LVAL_NUM: break;

    /* Para erro ou simbolo, libera os dados string */
    case LVAL_ERR: free(v->err); break;
    case LVAL_SYM: free(v->sym); break;

    /* Caso Sexpr, entao deleta todos os elementos dentro */
    case LVAL_SEXPR:
      for (int i = 0; i < v->count; i++) {
        lval_del(v->cell[i]);
      }
      /* Tambem libera a memoria alocada para conter os apontadores */
      free(v->cell);
    break;
  }

  /* Libera a memoria alocada para o proprio struct "lval" */
  free(v);
}

Lendo Expressões


Primeiro vamos ler o programa e construir um lval* que representa todo ele. A seguir, vamos avaliar este lval* para obter o resultado do nosso programa. Este primeiro estágio deve converter a árvore de sintaxe abstrata em uma S-Expression, e o segundo estágio deve avaliar esta S-Expression usando nossas regras Lisp normais.

Para completar o primeiro estágio podemos olhar recursivamente para cada nó da árvore, e construir tipos lval* diferentes dependendo dos campos tag e contents do nó.

Caso o nó está etiquetado como number ou symbol, então usamos nossos construtores para retornar um lval* diretamente para estes tipos. Caso este nó seja o root, ou uma sexpr, então criamos um lval S-Expression vazio e pacientemente adicionamos cada sub-expressão válida na árvore.

Para adicionar um elemento à uma S-Expression podemos criar uma função lval_add. Esta função adiciona um à contagem count) da expressão, e a seguir usa realloc para realocar a quantidade de espaço necessária para v->cell. Este novo espaço pode ser usado para armazenar o lval* extra necessário. Usando este novo espaço, ela seta o valor final da lista com v->cell[v->count-1] para o valor lval* x recebido.

Lisps não usam Cons cells?

Outros Lisps têm uma definição um pouco diferente do que é uma S-Expression. Na maioria dos outros Lisps, S-Expressions são definidas como ou um atom como o símbolo de um número, ou dois outras S-Expressions unidas, ou "cons-adas" junto.

Isto naturalmente leva a uma implementação usando listas ligadas, uma estrutura de dados diferente da que estamos usando. Escolhi representar S-Expressions como um array de tamanho variável neste livro com objetivo de simplicidade, mas é importante saber que a definição oficial e sua implementação típico são sutilmente diferentes.

lval* lval_read_num(mpc_ast_t* t) {
  errno = 0;
  long x = strtol(t->contents, NULL, 10);
  return errno != ERANGE ?
    lval_num(x) : lval_err("invalid number");
}
lval* lval_read(mpc_ast_t* t) {

  /* Caso Symbol ou Number, devolve a conversao para tal tipo */
  if (strstr(t->tag, "number")) { return lval_read_num(t); }
  if (strstr(t->tag, "symbol")) { return lval_sym(t->contents); }

  /* Caso root (>) ou sexpr entao cria lista vazia */
  lval* x = NULL;
  if (strcmp(t->tag, ">") == 0) { x = lval_sexpr(); } 
  if (strstr(t->tag, "sexpr"))  { x = lval_sexpr(); }

  /* Preenche a lista com qualquer expressao valida contida dentro */
  for (int i = 0; i < t->children_num; i++) {
    if (strcmp(t->children[i]->contents, "(") == 0) { continue; }
    if (strcmp(t->children[i]->contents, ")") == 0) { continue; }
    if (strcmp(t->children[i]->contents, "}") == 0) { continue; }
    if (strcmp(t->children[i]->contents, "{") == 0) { continue; }
    if (strcmp(t->children[i]->tag,  "regex") == 0) { continue; }
    x = lval_add(x, lval_read(t->children[i]));
  }

  return x;
}
lval* lval_add(lval* v, lval* x) {
  v->count++;
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  v->cell[v->count-1] = x;
  return v;
}

Imprimindo Expressões


Estamos agora bem perto de experimentar todas nossas nova mudanças. Precisamos modificar nossa função para imprimir tipos S-Expressions. Usando isso podemos verificar se a fase de leitura está funcionando corretamente, imprimindo as S-Expressions que lermos e verificando que elas casam com a entrada.

Para imprimir S-Expressions podemos criar uma outra função que varre todas as sub-expressões de uma expressão e imprime-as individualmente separadas por espaços, da mesma maneira que são fornecidas.

void lval_expr_print(lval* v, char open, char close) {
  putchar(open);
  for (int i = 0; i < v->count; i++) {

    /* Imprime o valor contido dentro */
    lval_print(v->cell[i]);

    /* Nao imprime espaco caso ultimo elemento */
    if (i != (v->count-1)) {
      putchar(' ');
    }
  }
  putchar(close);
}
void lval_print(lval* v) {
  switch (v->type) {
    case LVAL_NUM:   printf("%li", v->num); break;
    case LVAL_ERR:   printf("Error: %s", v->err); break;
    case LVAL_SYM:   printf("%s", v->sym); break;
    case LVAL_SEXPR: lval_expr_print(v, '(', ')'); break;
  }
}

void lval_println(lval* v) { lval_print(v); putchar('\n'); }

Não posso declarar essas funções porque elas chamam uma à outra.

A função lval_expr_print chama a função lval_print e vice-versa. Não há outra maneira que possamos ordená-las no código fonte para resolver esta dependência. Em vez disso, precisamos declarar adiantado uma delas, que é declarar uma função sem dá-la um corpo. Isso faz que as outras funções possam chamá-la, e permite você defini-la devidamente mais tarde. Para escrever uma declaração adiantada, escreva a definição da função mas em vez do corpo, coloque um ponto e vírgula ;. Neste exemplo, devemos colocar void lval_print(lval* v); em algum lugar no código fonte antes de lval_expr_print.

Você certamente vai topar com isso mais tarde, e nem sempre vou alertá-lo antes, então tente lembrar de como consertar isso!

Em nosso laço principal, podemos remover a avaliação por enquanto, e em seu lugar, tentar ler o resultado e imprimir o que temos.

lval* x = lval_read(r.output);
lval_println(x);
lval_del(x);

Caso funcionar, você verá algo como o que segue, quando digitar alguma entrada ao seu programa.

lispy> + 2 2
(+ 2 2)
lispy> + 2 (* 7 6) (* 2 5)
(+ 2 (* 7 6) (* 2 5))
lispy> *     55     101  (+ 0 0 0)
(* 55 101 (+ 0 0 0))
lispy>

Avaliando Expressões


O comportamento da nossa função de avaliação é essencialmente o mesmo de antes. Precisamos adaptá-la para lidar com lval* e nossa definição mais descontraída do que constitui uma expressão. Podemos pensar de nossa função de avaliação como um tipo de transformador. Ela recebe um lval* e transforma-o de alguma forma para um novo lval*. Em alguns casos, ela pode simplesmente retornar a mesma coisa. Em outros casos, ela pode modificar o lval* da entrada e retorná-lo. Em muitos casos ela vai deletar a entrada, e devolver algo completamente novo. Quando formos devolver alguma coisa nova, precisamos sempre lembrar de deletar o lval* que recebemos como entrada.

Para S-Expressions, primeiro avaliamos todos os filhos da S-Expression. Se qualquer um desses filhos for um erro, retornamos o primeiro erro que encontrarmos usando uma função que vamos definir mais tarde chamada lval_take.

Caso a S-Expression não tenha filhos, retornamo-la diretamente. Isto corresponde à expressão vazia, indicada por (). Também checamos por expressões únicas. Estas são expressões com apenas um filho como (5). Neste caso retornamos a expressão única contida dentro dos parênteses.

Se nenhum destes for o caso, sabemos que temos uma expressão válida com mais de um filho. Neste caso, separamos o primeiro elemento da expressão usando uma função que definiremos mais tarde chamada lval_pop. A seguir, checamos se ela for um symbol e não qualquer outra coisa. Se for um símbolo, checamos qual símbolo é, e passamo-lo com seus argumentos para uma função builtin_op que faz nossos cálculos. Caso o primeiro elemento não for um símbolo, deletamo-lo junto com os valores passados à função de avaliação, retornando um erro.

Para avaliar todos os outros tipos, apenas os retornamos diretamente.

lval* lval_eval_sexpr(lval* v) {

  /* Avalia os Filhos */
  for (int i = 0; i < v->count; i++) {
    v->cell[i] = lval_eval(v->cell[i]);
  }

  /* Checa se tem Erros */
  for (int i = 0; i < v->count; i++) {
    if (v->cell[i]->type == LVAL_ERR) { return lval_take(v, i); }
  }

  /* Expressao Vazia */
  if (v->count == 0) { return v; }

  /* Expressao Unica */
  if (v->count == 1) { return lval_take(v, 0); }

  /* Certifica que primeiro elemento eh um Symbol */
  lval* f = lval_pop(v, 0);
  if (f->type != LVAL_SYM) {
    lval_del(f); lval_del(v);
    return lval_err("S-expression Does not start with symbol!");
  }

  /* Chama builtin com operador */
  lval* result = builtin_op(v, f->sym);
  lval_del(f);
  return result;
}
lval* lval_eval(lval* v) {
  /* Avalia S-Expressions */
  if (v->type == LVAL_SEXPR) { return lval_eval_sexpr(v); }
  /* Todos outros tipos lval permanecem a mesma coisa */
  return v;
}

Usamos duas funções que não estão definidas no código acima. Elas são lval_pop e lval_take. Estas são funções de propósito geral para manipular tipos lval S-Expression, que faremos uso aqui e no futuro.

A função lval_pop extrai um único elemento de uma S-Expression no índice i e desloca o resto da lista para trás, para que ela não mais contenha aquele lval*. A seguir ela retorna o valor extraído. Note que ela não deleta a lista da entrada. É como pegar um elemento duma lista e removê-lo, deixando o que sobrar. Isso significa que tanto o elemento removido quanto à lista velha precisam ser deletados em algum momento com lval_del.

A função lval_take é similar à lval_pop, mas ela delete a lista da qual extraiu o elemento. Isso é como pegar um elemento duma lista e deletar o resto. É uma pequena variação de lval_pop, mas torna nosso código mais fácil de ler em alguns lugares. Diferentemente de lval_pop, apenas a expressão que você pega da lista precisa ser deletada com lval_del.

lval* lval_pop(lval* v, int i) {
  /* Encontra o item na posicao "i" */
  lval* x = v->cell[i];

  /* Desloca memoria depois do item na posicao "i" para acima do topo */
  memmove(&v->cell[i], &v->cell[i+1],
    sizeof(lval*) * (v->count-i-1));

  /* Diminui a contagem de itens na lista */
  v->count--;

  /* Realoca a memoria usada */
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  return x;
}
lval* lval_take(lval* v, int i) {
  lval* x = lval_pop(v, i);
  lval_del(v);
  return x;
}

Também precisamos definir a função de avaliação builtin_op. Esta é como a função eval_op usada em nosso capítulo anterior, mas modificada para receber um único lval* representando uma lista de todos os argumentos para usar na operação. Ela precisa fazer algumas checagens de erros mais rigorosas. Se quaisquer das entradas for um lval* não-número, precisamos retornar um erro.

Primeiro, ela checa se todos os argumentos da entrada são números. A seguir, ela extrai o primeiro argumento para começar. Se não há mais sub-expressões e o operador é subtração, ela executa negação unária neste primeiro número. Isto faz expressões como (- 5) avaliarem corretamente.

Se há mais argumentos, ela segue extraindo o próximo da lista e executando aritmética dependendo de qual operador devemos usar. Se um zero é encontrado numa divisão, ela deleta os x e y temporários, e a lista de argumentos a e devolve um erro.

Se não houve nenhum erro, os argumentos da entrada são deletados e uma nova expressão é devolvida.

lval* builtin_op(lval* a, char* op) {
  
  /* Certifica-se que todos argumentos sejam numeros */
  for (int i = 0; i < a->count; i++) {
    if (a->cell[i]->type != LVAL_NUM) {
      lval_del(a);
      return lval_err("Cannot operate on non-number!");
    }
  }
  
  /* Extrai o primeiro elemento */
  lval* x = lval_pop(a, 0);

  /* Caso nenhum argumento e sub, executa negacao unaria */
  if ((strcmp(op, "-") == 0) && a->count == 0) {
    x->num = -x->num;
  }

  /* Enquanto ainda houver elementos sobrando */
  while (a->count > 0) {

    /* Extrai o proximo elemento */
    lval* y = lval_pop(a, 0);

    if (strcmp(op, "+") == 0) { x->num += y->num; }
    if (strcmp(op, "-") == 0) { x->num -= y->num; }
    if (strcmp(op, "*") == 0) { x->num *= y->num; }
    if (strcmp(op, "/") == 0) {
      if (y->num == 0) {
        lval_del(x); lval_del(y);
        x = lval_err("Division By Zero!"); break;
      }
      x->num /= y->num;
    }

    lval_del(y);
  }

  lval_del(a); return x;
}

Isso termina nossas funções de avaliação. Precisamos apenas mudar a main novamente para que passe a entrada por esta avaliação antes de imprimi-la.

lval* x = lval_eval(lval_read(r.output));
lval_println(x);
lval_del(x);

Agora você deve ser capaz de avaliar expressões corretamente da mesma maneira que no capítulo anterior. Tome um pouco de ar, e brinque um pouco com a nova avaliação. Certifique-se que tudo está funcionando corretamente, e o comportamento está como o esperado. No próximo capítulo vamos fazer bastante uso destas mudanças para implementar alguns recursos novos legais.

lispy> + 1 (* 7 5) 3
39
lispy> (- 100)
-100
lispy>
()
lispy> /
/
lispy> (/ ())
Error: Cannot operate on non-number!
lispy>

Referência


#include "mpc.h"

#ifdef _WIN32

static char buffer[2048];

char* readline(char* prompt) {
  fputs(prompt, stdout);
  fgets(buffer, 2048, stdin);
  char* cpy = malloc(strlen(buffer)+1);
  strcpy(cpy, buffer);
  cpy[strlen(cpy)-1] = '\0';
  return cpy;
}

void add_history(char* unused) {}

#else
#include <editline/readline.h>
#include <editline/history.h>
#endif

/* Add SYM and SEXPR as possible lval types */
enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR };

typedef struct lval {
  int type;
  long num;
  /* Error and Symbol types have some string data */
  char* err;
  char* sym;
  /* Count and Pointer to a list of "lval*"; */
  int count;
  struct lval** cell;
} lval;

/* Construct a pointer to a new Number lval */ 
lval* lval_num(long x) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_NUM;
  v->num = x;
  return v;
}

/* Construct a pointer to a new Error lval */ 
lval* lval_err(char* m) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_ERR;
  v->err = malloc(strlen(m) + 1);
  strcpy(v->err, m);
  return v;
}

/* Construct a pointer to a new Symbol lval */ 
lval* lval_sym(char* s) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SYM;
  v->sym = malloc(strlen(s) + 1);
  strcpy(v->sym, s);
  return v;
}

/* A pointer to a new empty Sexpr lval */
lval* lval_sexpr(void) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}

void lval_del(lval* v) {

  switch (v->type) {
    /* Do nothing special for number type */
    case LVAL_NUM: break;
    
    /* For Err or Sym free the string data */
    case LVAL_ERR: free(v->err); break;
    case LVAL_SYM: free(v->sym); break;
    
    /* If Sexpr then delete all elements inside */
    case LVAL_SEXPR:
      for (int i = 0; i < v->count; i++) {
        lval_del(v->cell[i]);
      }
      /* Also free the memory allocated to contain the pointers */
      free(v->cell);
    break;
  }
  
  /* Free the memory allocated for the "lval" struct itself */
  free(v);
}

lval* lval_add(lval* v, lval* x) {
  v->count++;
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  v->cell[v->count-1] = x;
  return v;
}

lval* lval_pop(lval* v, int i) {
  /* Find the item at "i" */
  lval* x = v->cell[i];
  
  /* Shift memory after the item at "i" over the top */
  memmove(&v->cell[i], &v->cell[i+1],
    sizeof(lval*) * (v->count-i-1));
  
  /* Decrease the count of items in the list */
  v->count--;
  
  /* Reallocate the memory used */
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  return x;
}

lval* lval_take(lval* v, int i) {
  lval* x = lval_pop(v, i);
  lval_del(v);
  return x;
}

void lval_print(lval* v);

void lval_expr_print(lval* v, char open, char close) {
  putchar(open);
  for (int i = 0; i < v->count; i++) {
    
    /* Print Value contained within */
    lval_print(v->cell[i]);
    
    /* Don't print trailing space if last element */
    if (i != (v->count-1)) {
      putchar(' ');
    }
  }
  putchar(close);
}

void lval_print(lval* v) {
  switch (v->type) {
    case LVAL_NUM:   printf("%li", v->num); break;
    case LVAL_ERR:   printf("Error: %s", v->err); break;
    case LVAL_SYM:   printf("%s", v->sym); break;
    case LVAL_SEXPR: lval_expr_print(v, '(', ')'); break;
  }
}

void lval_println(lval* v) { lval_print(v); putchar('\n'); }

lval* builtin_op(lval* a, char* op) {
  
  /* Ensure all arguments are numbers */
  for (int i = 0; i < a->count; i++) {
    if (a->cell[i]->type != LVAL_NUM) {
      lval_del(a);
      return lval_err("Cannot operate on non-number!");
    }
  }
  
  /* Pop the first element */
  lval* x = lval_pop(a, 0);
  
  /* If no arguments and sub then perform unary negation */
  if ((strcmp(op, "-") == 0) && a->count == 0) {
    x->num = -x->num;
  }
  
  /* While there are still elements remaining */
  while (a->count > 0) {
  
    /* Pop the next element */
    lval* y = lval_pop(a, 0);
    
    /* Perform operation */
    if (strcmp(op, "+") == 0) { x->num += y->num; }
    if (strcmp(op, "-") == 0) { x->num -= y->num; }
    if (strcmp(op, "*") == 0) { x->num *= y->num; }
    if (strcmp(op, "/") == 0) {
      if (y->num == 0) {
        lval_del(x); lval_del(y);
        x = lval_err("Division By Zero.");
        break;
      }
      x->num /= y->num;
    }
    
    /* Delete element now finished with */
    lval_del(y);
  }
  
  /* Delete input expression and return result */
  lval_del(a);
  return x;
}

lval* lval_eval(lval* v);

lval* lval_eval_sexpr(lval* v) {
  
  /* Evaluate Children */
  for (int i = 0; i < v->count; i++) {
    v->cell[i] = lval_eval(v->cell[i]);
  }
  
  /* Error Checking */
  for (int i = 0; i < v->count; i++) {
    if (v->cell[i]->type == LVAL_ERR) { return lval_take(v, i); }
  }
  
  /* Empty Expression */
  if (v->count == 0) { return v; }
  
  /* Single Expression */
  if (v->count == 1) { return lval_take(v, 0); }
  
  /* Ensure First Element is Symbol */
  lval* f = lval_pop(v, 0);
  if (f->type != LVAL_SYM) {
    lval_del(f); lval_del(v);
    return lval_err("S-expression Does not start with symbol.");
  }
  
  /* Call builtin with operator */
  lval* result = builtin_op(v, f->sym);
  lval_del(f);
  return result;
}

lval* lval_eval(lval* v) {
  /* Evaluate Sexpressions */
  if (v->type == LVAL_SEXPR) { return lval_eval_sexpr(v); }
  /* All other lval types remain the same */
  return v;
}

lval* lval_read_num(mpc_ast_t* t) {
  errno = 0;
  long x = strtol(t->contents, NULL, 10);
  return errno != ERANGE ?
    lval_num(x) : lval_err("invalid number");
}

lval* lval_read(mpc_ast_t* t) {
  
  /* If Symbol or Number return conversion to that type */
  if (strstr(t->tag, "number")) { return lval_read_num(t); }
  if (strstr(t->tag, "symbol")) { return lval_sym(t->contents); }
  
  /* If root (>) or sexpr then create empty list */
  lval* x = NULL;
  if (strcmp(t->tag, ">") == 0) { x = lval_sexpr(); } 
  if (strstr(t->tag, "sexpr"))  { x = lval_sexpr(); }
  
  /* Fill this list with any valid expression contained within */
  for (int i = 0; i < t->children_num; i++) {
    if (strcmp(t->children[i]->contents, "(") == 0) { continue; }
    if (strcmp(t->children[i]->contents, ")") == 0) { continue; }
    if (strcmp(t->children[i]->contents, "}") == 0) { continue; }
    if (strcmp(t->children[i]->contents, "{") == 0) { continue; }
    if (strcmp(t->children[i]->tag,  "regex") == 0) { continue; }
    x = lval_add(x, lval_read(t->children[i]));
  }
  
  return x;
}

int main(int argc, char** argv) {
  
  mpc_parser_t* Number = mpc_new("number");
  mpc_parser_t* Symbol = mpc_new("symbol");
  mpc_parser_t* Sexpr  = mpc_new("sexpr");
  mpc_parser_t* Expr   = mpc_new("expr");
  mpc_parser_t* Lispy  = mpc_new("lispy");
  
  mpca_lang(MPCA_LANG_DEFAULT,
    "                                          \
      number : /-?[0-9]+/ ;                    \
      symbol : '+' | '-' | '*' | '/' ;         \
      sexpr  : '(' <expr>* ')' ;               \
      expr   : <number> | <symbol> | <sexpr> ; \
      lispy  : /^/ <expr>* /$/ ;               \
    ",
    Number, Symbol, Sexpr, Expr, Lispy);
  
  puts("Lispy Version 0.0.0.0.5");
  puts("Press Ctrl+c to Exit\n");
  
  while (1) {
  
    char* input = readline("lispy> ");
    add_history(input);
    
    mpc_result_t r;
    if (mpc_parse("<stdin>", input, Lispy, &r)) {
      lval* x = lval_eval(lval_read(r.output));
      lval_println(x);
      lval_del(x);
      mpc_ast_delete(r.output);
    } else {    
      mpc_err_print(r.error);
      mpc_err_delete(r.error);
    }
    
    free(input);
    
  }
  
  mpc_cleanup(5, Number, Symbol, Sexpr, Expr, Lispy);
  
  return 0;
}

Metas Bônus


  • › Dê um exemplo de uma variável em nosso programa que viva no Stack.
  • › Dê um exemplo de uma variável em nosso programa que viva no <Heap.
  • › O que a função strcpy faz?
  • › O que a função realloc faz?
  • › O que a função memmove faz?
  • › Qual a diferença entre memmove e memcpy?
  • › Amplie análise sintática e avaliação para suportar o operador resto da divisão %.
  • › Amplie análise sintática e avaliação para suportar tipos decimais usando um campo double.

Navegação

‹ Tratamento de Erros

• Conteúdo •

Q-Expressions (expressões citadas) ›