MAC0316/5754 - Segundo Exercício-Programa

Segundo Exercício-Programa: Interpretador Estendido

MAC0316/MAC5754 - Conceitos de Linguagens de Programação

O segundo exercício-programa é o Extended Interpreter proposto por Sriram Krishnamurthy (o autor do PLAI), com as modificações especificadas abaixo.

Modificações em relação à proposta original

Faremos três modificações no enunciado original do Prof. Krishnamurthy. As duas primeiras são burocráticas e a terceira é de conteúdo.

Estas são as modificações burocráticas:

Substitua as ocorrências de "DrScheme" por "DrRacket".
Em vez de entregar dois arquivos (xinterp.ss e xinterp-lazy.ss), siga a convenção de entrega definida ao final desta página.

Vejamos agora a modificação não burocrática. Na proposta original de S. Krishnamurthy, a forma with aparece tanto na sintaxe concreta como na sintaxe abstrata da linguagem CFWAE. Como a definição do tipo CFWAE inclui uma variante with, essa proposta permite (mas não obriga) que um parser gere árvores sintáticas contendo nós with. Em outras palavras, o enunciado original permite que você decida se o seu parser vai ou não vai gerar árvores sintáticas contendo nós with. Essa decisão separa as possíveis soluções em duas categorias:

Num tipo de solução, o parser traduz ocorrências concretas da forma sintática with em nós with da árvore sintática.
No outro tipo de solução, o parser converte ocorrências concretas da forma sintática with em chamadas a funções anônimas, da maneira descrita no PLAI e vista em classe. Cada ocorrência da forma with no programa concreto gera um nó app da árvore sintática. Neste tipo de solução, as árvores sintáticas nunca conterão nós with. Embora permitidos pela sintaxe abstrata, tais nós não serão utilizados.

Na alternativa 2, o with é apenas um modo conveniente ("acúcar sintático") para representar uma chamada a uma função anônima. Essa alternativa simplifica a implementação do interpretador, pois somente o parser precisa lidar com a forma with. Além disso, considero que a alternativa 2 é a "mais educativa", pois ela mostra, de modo bem concreto, que formas como a with (ou como a forma let do Scheme) não são construções essenciais.

Em vez de deixar a seu critério a escolha entre os dois tipos de soluções acima, resolvi especificar que deve ser implementada uma solução do tipo 2. É essa a diferença básica entre este exercício-programa e o proposto por S. Krishnamurthy. Tudo o que segue é consequência dessa decisão.

Já que nossas árvores sintáticas nunca conterão nós with, podemos eliminar da sintaxe abstrata o tipo correspondente a esses nós, ou seja, podemos remover a variante with do define-type para CFWAE. Podemos remover também a definição do tipo Binding, pois esse tipo aparece somente na variante with. Essas alterações devem ser aplicadas ao código que está na seção Support Code do enunciado original. Em vez do modelo especificado na seção Support Code, use o seguinte modelo de código (sem fazer nenhuma alteração nele):

(define-type CFAE
  [num (n number?)]
  [binop (op procedure?) (lhs CFAE?) (rhs CFAE?)]
  [id (name symbol?)]
  [if0 (c CFAE?) (t CFAE?) (e CFAE?)]
  [fun (args (listof symbol?)) (body CFAE?)]
  [app (f CFAE?) (args (listof CFAE?))])

(define-type Env
  [mtEnv]
  [anEnv (name symbol?) (value CFAE-Value?) (env Env?)])

(define-type CFAE-Value
  [numV (n number?)]
  [closureV (params (listof symbol?))
            (body CFAE?)
            (env Env?)])

;; parse : expression -> CFAE
;; This procedure parses an expression into a CFAE
(define (parse sexp)
  ...)

;; interp : CFAE -> CFAE-Value
;; This procedure interprets the given CFAE and produces a result
;; in the form of a CFAE-Value (either a closureV or a numV)
(define (interp expr)
  ...)

Note que o tipo CFWAE do modelo original foi renomeado para CFAE, já que o with desapareceu da sintaxe abstrata (embora continue presente na sintaxe concreta CFWAE). Agora a função parse recebe uma s-expression com uma expressão CFWAE e devolve a instância do tipo CFAE que é a raiz da árvore sintática correspondente.

Na segunda parte do exercício-programa (avaliação preguiçosa), o tipo CFAE-Value deve conter uma variante exprV:

(define-type CFAE-Value
  [numV (n number?)]
  [closureV (params (listof symbol?))
            (body CFAE?)
            (env Env?)]
  [exprV (expr CFAE?) (env Env?)]))

Caso você decida implementar avaliação preguiçosa com caching (a implementação de caching é opcional - quem a fizer receberá um bônus na nota deste EP), sua variante exprV terá um terceiro campo. Esse campo deverá ser uma box mutável, análoga à usada na seção 8.2 do PLAI (vide código na página 78 e listagens nas figuras 8.3 e 8.4).

Sobre a entrega

Este EP deve ser feito individualmente. Entregue sua solução até o dia 3 de maio, pelo sistema Paca/Moodle.

Deve ser entregue um arquivo tar.gz ou zip que satisfaça os seguintes requisitos:

O nome do arquivo deve ser da forma ep2-<seu-nome>.tar.gz ou ep2-<seu-nome>.zip. Por exemplo: ep2-fulano-de-tal.zip. No nome do arquivo devem ser omitidos os acentos do seu nome. Além disso, a separação entre palavras não deve ser feita com espaços. Ou seja, o arquivo não deve se chamar "ep2-joão-da-silva.zip" nem "ep2 joao da silva.zip".
O desempacotamento do arquivo tar.gz ou zip deve produzir um diretório com o mesmo nome do arquivo, menos o sufixo .tar.gz ou .zip. (Exemplo: ep2-fulano-de-tal.) Todos os arquivos desempacotados devem estar dentro desse diretório.
O diretório desempacotado deve conter:
- o seu arquivo xinterp.ss, com a primeira parte do exercício-programa (avaliação ávida);
- o seu arquivo xinterp-lazy.ss, com a segunda parte do exercício-programa (avaliação preguiçosa).

Last modified: Thu Apr 14 23:02:57 BRT 2011