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 a modificação especificada abaixo.

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

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

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:

  1. Num tipo de solução, o parser traduz ocorrências concretas da forma sintática with em nós with da árvore sintática.

  2. 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 modificaçõ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): 

(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?)]))

O que deve ser entregue

Entregue um arquivo tar.gz ou zip que satisfaça os seguintes requisitos:

Valid CSS! Valid XHTML 1.0! Last modified: Mon Apr 19 16:06:22 BRT 2010