Linguagens de Programação

Enunciado do Trabalho Prático

Departamento de Informática
Universidade de Évora

2005/2006

Versão 1.0b

1   Prólogo

O objectivo deste trabalho é implementar, em Java, um interpretador de Cálculo-λ.

O trabalho divide-se numa base e nos anexos, devendo todos os trabalhos entregues implementar a base.

2   O Cálculo-λ

2.1   Sintaxe

A sintaxe usada para os termos do Cálculo-λ será a dada pela gramática abaixo. 
  <termo> ::= <variável>                              (Variável)
          |   (\<variável>.<termo>)                   (Abstracção)
          |   (<termo> <termo>)                       (Aplicação)
          |   (let <variável> = <termo> in <termo>)   (let)
Nesta sintaxe, o carácter barra-inclinada-para-trás ‘\’ faz o papel do símbolo ‘λ’ e as variáveis têm um nome constituído por uma única letra minúscula.

Para não sobrecarregar os termos com parêntesis, adoptam-se as seguintes convenções:

De acordo com estas convenções, o termo-λ 
    (let f = (\x.(\y.((\z.z) (x y)) y)) in
      (let g = (\x.(\y.(\z.(z ((x y) z))))) in
        (((g a) b) f)))
poder-se-á escrever como 
    let f = \x.\y.(\z.z) (x y) y in
      let g = \x.\y.\z.z (x y z) in
        g a b f

2.2   Avaliação

A avaliação de um termo-λ far-se-á através da redução β, seguindo uma estratégia à escolha.

3   Base

O trabalho base consiste na implementação de um interpretador da linguagem descrita. Este interpretador deverá ler um termo-λ da sua entrada padrão (standard input) e, caso não ocorra nenhum erro sintáctico, escrever o termo lido e o resultado da sua avaliação no terminal.

Durante a fase da análise sintáctica, o programa apresentado deverá construir uma árvore de sintaxe abstracta, que servirá depois de base para a avaliação a efectuar.

Nesta parte do trabalho poderá ser considerado que uma substituição nunca ocasiona a captura de variáveis (ver o anexo A).

3.1   Comentários

Além das construções da linguagem, o trabalho deverá suportar a inclusão de comentários no código.

Um comentário inicia-se com o carácter ponto-e-vírgula ‘;’ ou pela sequência ‘->’ (caracteres menos e maior que) e estende-se até ao fim da linha. (A notação ‘->’ destina-se a anotar o código com a forma reduzida do termo-λ.)

4   Anexos

Estes anexos são independentes entre si, pelo que a implementação realizada poderá integrar um qualquer subconjunto deles.

4.1   Anexo A

Este anexo consiste na inclusão de código na implementação que evite a captura de variáveis durante uma substituição.

4.2   Anexo B

Neste anexo, os termos seguintes são acrescentados à linguagem base. 
  <termo> ::= <inteiro> | + | - | * | /
Quaisquer destes novos termos são constantes e não reduzem mais. No entanto, enquanto que os inteiros (sem sinal) não podem ser aplicados, os outros símbolos denotam funções com dois argumentos, que realizam as operações usuais.

Tratando-se de funções de dois argumentos, a sua aplicação a um argumento tem como resultado uma função de um argumento. Por exemplo, o termo ‘+ 5’ é uma função que soma 5 ao seu argumento. Assim, o termo

let f = + 5 in f 10
reduzirá para o termo ‘15’.

Considera-se que a realização de uma destas operações corresponde a um passo de redução e que só poderá ser efectuada quando ambos os argumentos tiverem reduzido para inteiros. Assim, o termo

* (- 14 5) (\x.x x)
só poderá reduzir até ‘* 9 (\x.x x)’, visto que ‘\x.x x’ não é um inteiro nem nunca reduzirá para um.

4.3   Anexo C

Neste anexo acrescentam-se os termos 
  <termo> ::= (if <termo> then <termo> else <termo>) | = | true | false | <inteiro>
onde ‘true’ e ‘false’ são constantes que correspondem aos valores lógicos e que se comportam como os inteiros. O termo ‘=’ é, também, uma constante e denota a função que testa se dois inteiros são iguais. A sua aplicação a dois argumentos só reduz para um valor lógico se aqueles reduzirem para inteiros (ver no anexo B o comportamento do inteiros e das funções com dois argumentos).

A construção if tem a mesma prioridade que a let e reduz, num passo, para o termo do ramo then, se a condição tiver reduzido para ‘true’, e para o termo else se a condição tiver reduzido para ‘false’. Se a condição não reduzir para um valor lógico, o termo if não pode reduzir.

4.4   Anexo D

Anexo correspondente à implementação da opção --passos. Quando esta opção for dada ao programa, ele mostrará o traço da avaliação do termo-λ, i.e., o termo-λ resultante de cada passo de redução. Os termos correspondentes aos vários passos serão escritos em linhas distintas, prefixados por ‘-> ’.

5   Implementação

O trabalho deverá ser implementado em Java, recorrendo ao jlex (ou ao jflex) e ao cup para construir, respectivamente, os analisadores lexicográfico e sintáctico.

5.1   Funcionamento

O programa apresentado deverá ler um termo-λ da sua entrada padrão e, se não ocorrer nenhum erro sintáctico, escrever no terminal o termo lido e o resultado da sua redução, na linha seguinte, prefixado por ‘-> ’. Depois de escrever o resultado da redução, o programa terminará. Se for detectado algum erro sintáctico, o programa poderá também terminar.

Internamente, o resultado da análise sintáctica deverá ser uma árvore de sintaxe abstracta. Esta representação do termo lido poderá, depois, ser utilizada directamente no processo de redução do termo ou ser processada com o fito de obter uma representação considerada mais apropriada para o funcionamento do programa.

5.2   Escrita de termos

Os termos deverão ser escritos no terminal numa forma que, possivelmente a menos dos nomes das variáveis ligadas, possa ser lida pelo programa e ser interpretada como o mesmo termo. Deverá ser feito um esforço no sentido de evitar escrever parêntesis inúteis, de acordo com as convenções descritas acima.

Se o termo lido pelo programa for

let f = \g.\v.g v in f (\x.\y.x y z) w
ele poderá ser escrito em qualquer uma das seguintes formas 
      let f = \g.\v.g v in f (\x.\y.x y z) w
      let f' = \g'.\v'.g' v' in f' (\x'.\y'.x' y' z) w
      let a = \b.\c.b c in a (\d.\e.d e z) w
      let x0 = \x1.\x2.x1 x2 in x0 (\x3.\x4.x3 x4 z) w
      let x0 = \x0.\x1.x0 x1 in x0 (\x0.\x1.x0 x1 z) w
      let f2 = \g0.\v1.g0 v1 in f2 (\x3.\y4.x3 y4 z) w
      (\f.f (\x.\y.x y z) w) (\g.\v.g v)
      (\f'.f' (\x'.\y'.x' y' z) w) (\g'.\v'.g' v)
      (\a.a (\b.\c.b c z) w) (\d.\e.d e)
      (\x0.x0 (\x1.\x2.x1 x2 z) w) (\x3.\x4.x3 x4)
      (\x0.x0 (\x1.\x2.x1 x2 z) w) (\x0.\x1.x0 x1)
      (\f2.f2 (\x3.\y4.x3 y4 z) w) (\g0.\v1.g0 v1)
ou em alguma variante destas.

5.3   Organização

O método main, que inicia a execução do interpretador, deverá pertencer à classe Main e encontrar-se no ficheiro Main.java.

Deverá ser entregue uma makefile que proceda à compilação do programa através das invocações make ou make all, que provoque a sua execução através do comando make run e que apague os ficheiro criados na compilação através de make clean.

Os ficheiros Makefile, Main.java, lambda.cup e lambda.lex fornecidos podem constituir um ponto de partida, mas não têm de ser usados.

Usando a makefile fornecida, é possível passar argumentos ao interpretador usando o comando

make run ARGS='<argumentos>'
Se o ficheiro termo.lambda contiver o termo-λ a avaliar, o comando
make run < termo.lambda
fará com que o interpretador o leia.

6   Exemplos

6.1   Base

Exemplo 6.1.1

Se o termo a processar for
(\x.\y.x y) z
o interpretador escreverá no terminal, a menos do nome das variáveis ligadas e da inclusão de mais parêntesis 
(\x.\y.x y) z
-> \y.z y

Exemplo 6.1.2

Termo:
x
Saída:
x
ou 
x
-> x

Exemplo 6.1.3

Termo:
\x.x
Saída:
\x.x

Exemplo 6.1.4

Termo:
(\x.x) y
Saída:
(\x.x) y
-> y

Exemplo 6.1.5

Termo:
x y
Saída:
x y

Exemplo 6.1.6

Termo:
x y y
Saída:
x y y

Exemplo 6.1.7

Termo:
f (\x.x) y
Saída:
f (\x.x) y

Exemplo 6.1.8

Termo:
(\x.x) (\y.y) z
Saída: 
(\x.x) (\y.y) z
-> z

Exemplo 6.1.9

Termo:
(\f.\x.f x) (\y.y) z
Saída: 
(\f.\x.f x) (\y.y) z
-> z

Exemplo 6.1.10

Termo:
\f.\x.f x
Saída:
\f.\x.f x

Exemplo 6.1.11

Termo:
(\f.\x.f x) (\y.y)
Saída: 
(\f.\x.f x) (\y.y)
-> \x.x

Exemplo 6.1.12

Termo:
let x = y in z
Saída: 
let x = y in z
-> z

Exemplo 6.1.13

Termo:
let i = \x.x in i
Saída: 
let i = \x.x in i
-> \x.x

Exemplo 6.1.14

Termo:
let i = \x.x in i k
Saída: 
let i = \x.x in i k
-> k

Exemplo 6.1.15

Termo: 
let z = \a.\b.b in                 ; zero
  let s = \n.\c.\d.n c (c d) in    ; sucessor
    s z  ->  \s.\z.s z             ; um
Saída: 
(\z.(\s.s z) (\n.\c.\d.n c (c d))) (\a.\b.b)
-> \c.\d.c d

Exemplo 6.1.16

Termo:
\m.\n.\s.\z.m s (n s z)
Saída:
\m.\n.\s.\z.m s (n s z)

6.2   Anexo A

Exemplo 6.2.1

Termo:
(\x.\y.x y) (\x.x y)
Saída: 
(\x.\y.x y) (\x.x y)
-> \y'.y' y

Exemplo 6.2.2

Termo: 
let    z = \s.\z.z
in let s = \n.\s.\z.n s (s z)
in let u = s z
in let d = s u
in     d u
Saída: 
(\z.(\s.(\u.(\d.d u) (s u)) (s z)) (\n.\s.\z.n s (s z))) (\s.\z.z)
-> \z'.\z''.z' z''

6.3   Anexo B

Exemplo 6.3.1

Termo:
213
Saída:
213

Exemplo 6.3.2

Termo:
+
Saída:
+

Exemplo 6.3.3

Termo:
+ 2
Saída: 
+ 2
-> + 2

Exemplo 6.3.4

Termo:
+ 2 3
Saída: 
+ 2 3
-> 5

Exemplo 6.3.5

Termo:
let f = + in f 5 10
Saída: 
(\f.f 5 10) +
-> 15

Exemplo 6.3.6

Termo:
let f = + 5 in f 10 -> 15
Saída: 
(\f.f 10) (+ 5)
-> 15

Exemplo 6.3.7

Termo: 
let f = \x.+ (* x 2) 1 in
  f 1
Saída: 
(\f.f 1) (\x.+ (* x 2) 1)
-> 3

Exemplo 6.3.8

Termo: 
let c = \n.n (+ 1) 0 in
  c (\s.\z.s (s (s (s (s (s (s z)))))))
Saída: 
(\c.c (\s.\z.s (s (s (s (s (s (s z)))))))) (\n.n (+ 1) 0)
-> 7

Exemplo 6.3.9

Termo:
* (- 14 5) (\x.x x)
Saída: 
* (- 14 5) (\x.x x)
-> * 9 (\x.x x)

6.4   Anexo C

Exemplo 6.4.1

Termo:
0 = 1
Saída:
0 = 1

Exemplo 6.4.2

Termo:
= 0 1
Saída: 
= 0 1
-> false

Exemplo 6.4.3

Termo:
(if true then \x.\y.x else \x.\y.y) a b
Saída: 
(if true then \x.\y.x else \x.\y.y) a b
-> a

Exemplo 6.4.4

Termo:
(if = 1 0 then \x.\y.x else \x.\y.y) a b
Saída: 
(if = 1 0 then \x.\y.x else \x.\y.y) a b
-> b

Exemplo 6.4.5

Necessita que os anexos A e B tenham sido implementados.

Termo: 

let y = \f.(\x.f (x x)) (\x.f (x x)) in
  let g = \f.\n.if = n 0 then 1 else * n (f (- n 1)) in
    (y g) 5  ->  120 ; 5!
Saída: 
(\y.(\g.y g 5) (\f.\n.if = n 0 then 1 else * n (f (- n 1)))) (\f.(\x.f (x x)) (\x.f (x x)))
-> 120

6.5   Anexo D

Exemplo 6.5.1

Termo: 
let z = \a.\b.b in                 ; zero
  let s = \n.\c.\d.n c (c d) in    ; sucessor
    s z  ->  \s.\z.s z             ; um
Saída: 
(\z.(\s.s z) (\n.\c.\d.n c (c d))) (\a.\b.b)
-> (\s.s (\a.\b.b)) (\n.\c.\d.n c (c d))
-> (\n.\c.\d.n c (c d)) (\a.\b.b)
-> \c.\d.(\a.\b.b) c (c d)
-> \c.\d.(\b.b) (c d)
-> \c.\d.c d

7   Epílogo

7.1   Realização

O trabalho será realizado por grupos de até dois alunos.

Faz parte da realização do trabalho a elaboração de exemplos (4 ou 5) que ilustrem quer o correcto funcionamento da implementação feita, quer eventuais problemas que não tenham sido completamente resolvidos.

O código entregue deverá funcionar na máquina alunos.di.uevora.pt.

7.2   Entrega

Os elementos a entregar serão:

O relatório deverá incluir:

Estes elementos deverão ser entregues através do moodle até às 20:00 do dia 4 de Junho de 2006. (Para evitar problemas com entregas em cima da hora limite, a entrega estará aberta até às 23:55, hora do moodle.) Se o relatório for entregue impresso, ele deverá ser colocado no cacifo de um dos docentes da cadeira até às 10:00 do dia 5 de Junho.

Os ficheiros a entregar deverão ser incluídos num arquivo .tar.gz ou .zip. O arquivo entregue deverá ter nome nnnnn-mmmmm.tar.gz (ou .zip), onde nnnnn e mmmmm deverão ser substituídos pelos números dos elementos do grupo. No caso dos trabalhos individuais, o nome do arquivo deverá ser nnnnn.tar.gz (ou .zip).

É da responsabilidade de cada grupo verificar e certificar-se de que o arquivo entregue contém exactamente os elementos que pretendiam entregar.

7.3   Cotações

O trabalho será classificado de 0 a 20 valores.

A cotação da várias partes do trabalho é a seguinte:

Cotação
Base 12
Anexo A 2
Anexo B 2 + 2*
Anexo C 2 + 2*
Anexo D 2
* - estes 2 valores são comuns aos dois anexos: em separado, cada um dos anexos B e C vale 4 valores; em conjunto, os dois anexos valem 6 valores.

Só serão considerado os anexos cujas cotações somadas não excedam os 8 valores.

7.4   Avaliação

Serão avaliadas: a correcção, a qualidade e a completude da solução apresentada; a relevância e a completude dos exemplos e do relatório; a qualidade, a documentação e a apresentação do código (cada linha de código não deverá ter mais de 80 caracteres).

A realização e entrega deste trabalho são facultativas.

O trabalho deverá ser realizado somente por quem o entrega. A detecção de qualquer acto de cópia levará à anulação de todos os trabalhos envolvidos e à impossibilidade de obter aprovação à disciplina, este ano lectivo, por parte dos elementos dos grupos em questão. Os estudantes são encorajados a discutir a resolução das questões levantadas pelo trabalho, mas não deverão ver, dar a ver, emprestar ou pedir emprestado o código do trabalho, e só deverá ser entregue código feito pelos elementos do grupo.

7.5   Bom trabalho