8.12

Entrega 4🔗

Deadline: 10 de Noviembre 2024

⚠ 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, pueden iniciar un nuevo branch en git con: 

$ git checkout -b entrega4

⚠ Comentario

Recuerde que es opcional que hagan el merge con el repositorio de referencia cdi, porque resolver/debuggear los conflictor podría ser muy laborioso. Si deciden no hacer el merge, miren el código del nuevo parser y AST como referencia para los cambios que deben hacer. Recuerden seguir la misma sintaxis concreta que usa el código de referencia y que se detalla en este enunciado. Esto es importante, pues su código será revisado con tests escritos usando dicha sintaxis.

Si deciden hacer el merge, pueden hacerlo 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, deberán resolverlos manualmente.

1.1 Desarrollo y entrega del código🔗

Recuerden hacer un git commit cada vez que avanzan 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 necesiten ayuda.

Para entregar su solución, hagan un release en Github con nombre entrega4 y entreguen el hash del commit correspondiente en el comentario de la tarea de U-cursos.

Recuerden documentar lo que intentaron y lograron hacer, y cualquier otro detalle relevante a su implementación (e.g. cuál spec avanzada eligieron, decisiones de diseño que tomaron, etc). Para esto tienen dos alternativas:

1.2 Testing🔗

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

2 Lambdas y Clausuras🔗

Extiendan el lenguage fuente con funciones anónimas:

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

Para ello, sigan las notas del curso e implementen 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

Tomen 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.

Deben 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, deben reportar un error de aridad cuando se aplique una lambda a una cantidad incorrecta de argumentos.

Recuerden 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

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

Siguiendo las notas del curso, extiendan 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 orden 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