8.8

Entrega 4

Deadline: 12 de Noviembre 2023

⚠ Importante

Recuerde las reglas del código de conducta.

Objetivos básicos de la entrega:

Objetivo extra:

La evaluación se hace con specs grading (vea los detalles aquí).

1 Para empezar

Para partir, puede iniciar un nuevo branch en git con: 

$ git checkout -b entrega4

⚠ Comentario

Recuerde que es opcional hacer el merge con cdi. Si decide no hacer el merge, mire el código del nuevo parser y AST como referencia para los cambios que debe hacer.

luego puede actualizar el código de su intérprete de referencia con 

$ git fetch cdi
$ git merge cdi/entrega4
es muy posible que la operación merge no funcione directamente a causa de conflictos. En este caso, debe resolver los conflictos manualmente.

1.1 Desarrollo y entrega del código

Recuerde hacer un git commit cada vez que avanza en su desarrollo, y subir el código a su repositorio github para facilitar el acceso al código a los auxiliares en caso de que necesite ayuda.

Para entregar su solución, haga un release en github con nombre entrega4 y entregue el hash del commit en U-cursos, junto con un archivo README.md con lo que intentaron hacer, lo que lograron hacer, y qué decisiones de diseño importantes tomaron en el proceso.

1.2 Testing

Recuerde que la documentación para escribir los tests se encuentra en bbctester/README.md.

2 Lambdas y Clausuras

Extienda el lenguage fuente con funciones anónimas:

‹expr›: ... | ( lambda ( IDENTIFIER ... ) ‹expr› )

Para eso, siga las notas del curso e implemente clausuras para representar funciones anónimas como valores.

Por ejemplo:

(tup (lambda () true) (lambda (x y) (+ x y)))

Retorna:

(tup <clos:0> <clos:2>)

Para aplicar clausuras, vamos a usar una sintaxis específica, usando el keyword @:

‹expr›: ... | ( @ ‹expr› ‹expr› ... )

Por ejemplo:

(@ (lambda (x y) (+ x y)) 1 2)

Noten que las clausuras nombradas con let y funciones definidas con def NO comparten namespace (las funciones definidas con def siguen siendo "globales").

Por ejemplo:

(
  (def (f x) (+ x -1))
  (let (f (lambda (x) (if x 7 13)))
    (tup (@ f true) (f 3)))
)

Retorna:

(tup 7 2)

porque la primera aplicación (@ f true) busca una variable local f y la segunda aplicación (f 3) busca una función global f.

⚠ Comentario

Tome en cuenta que esta es la sintaxis/semántica implementada en el oráculo, y les solicitamos seguirla, por simplicidad.

Este diseño fue elegido porque permite separar sin ambiguedad el uso de lambdas del uso de funciones globales, pues tienen costos de ejecución distintos.

Debe agregar también una verificación dinámica de tipos para la aplicación de lambdas (@), es decir, reportar error cuando se intenta aplicar algo que no es una clausura. Además, debe reportar un error de aridad cuando se aplique una lambda a una cantidad incorrecta de argumentos.

Recuerde que los mensajes de error que producen deben tener el mismo formato que especifica el enunciado. Por ejemplo, los siguientes programas

(@ 1 true)
(@ false 1 2)
(@ (tup -2 true) 6)

(@ (lambda (x y) (+ y x)) 4)
(@ (lambda () (tup 1 2)) false 6 (tup))

producen respectivamente los siguientes errores:

Type error: Expected closure but got 1
Type error: Expected closure but got false
Type error: Expected closure but got (tup -2 true)

Arity mismatch: closure expected 2 arguments but got 1
Arity mismatch: closure expected 0 arguments but got 3

Recuerde que los errores de tipos y de aridad son de tiempo de ejecución (runtime).

Siguiendo las notas del curso, extienda su compilador para soportar funciones como valores de primera clase: Se puede pasar una función a otras funciones y retornar funciones.

Las funciones definidas con def deberían ahora poder recibir funciones como argumento, pero para poder retornarlas el usuario deberá envolverlas en una expresión lambda.

Por ejemplo:

(
  (def (add3 x) (+ 3 x))
  (def (map-pair f p) (tup (@ f (get p 0)) (@ f (get p 1))))

  (map-pair (lambda (x) (add3 x)) (tup 39 2))
)

Retorna:

(tup 42 5)

Es decir, deben integrarse totalmente con las funciones anónimas producidas por lambda.

Por ejemplo:

(
  (def (fib n) (if (<= n 1) 1 (+ (fib (+ n -1)) (fib (+ n -2)))))
  (def (pair-fun f g p) (tup (@ f (get p 0)) (@ g (get p 1))))

  (pair-fun (lambda (x) (+ 3 x))
          (lambda (y) (pair-fun (lambda (n) (fib n)) (lambda (z) (+ z y)) (tup y y)))
          (tup 39 6))
)

Retorna:

(tup 42 (tup 13 12))

3 Objetivo Extra: Recursión (0.5pto)

Para funciones de primer ordén la recursión es gratis: el código de cada función tiene una etiqueta y es suficiente hacer un call a esa etiqueta. ¡No es tan simple para lambdas! Añada una expresión letrec para definir funciones anónimas recursivas:

‹expr›: ... | ( letrec ( ( IDENTIFIER ( lambda ( IDENTIFIER ... ) ‹expr› ) ) ... ) ‹expr› )

Por ejemplo:

(letrec
  ((even (lambda (n) (if (<= n 0) true (@ odd (+ n -1)))))
    (odd  (lambda (n) (if (<= n 1) true (@ even (+ n -1))))))
  (@ odd 13))

Retorna:

true