Código: trcfwae.rkt
Descarga aquí
#lang plai
#|--------------------------------------------------------------------------------------------------
- -
- Gramáticas necesarias -
- -
--------------------------------------------------------------------------------------------------|#
;; Gramática para representar los árboles de sintaxis abstracta de TRCFWAE. Estos árboles representan:
;; · Identificadores.
;; · Números.
;; · Operaciones binarias.
;; · Condicional, if0.
;; · Asignaciones locales, with.
;; · Asignaciones locales recursivas, rec.
;; · Funciones anónimas de primera clase, fun.
;; · Aplicación de funciones.
(define-type TRCFWAE
[idS (i symbol?)]
[binopS (op procedure?) (lh TRCFWAE?) (rh TRCFWAE?)]
[numS (n number?)]
[if0S (test-expr TRCFWAE?) (then-expr TRCFWAE?) (else-expr TRCFWAE?)]
[withS (id symbol?) (type Type?) (value TRCFWAE?) (body TRCFWAE?)]
[recS (id symbol?) (value TRCFWAE?) (body TRCFWAE?)]
[funS (param symbol?) (type-param Type?) (type-return Type?) (body TRCFWAE?)]
[appS (fun-expr TRCFWAE?) (arg TRCFWAE?)])
;; Gramática para representar la versión sin azúcar sintáctica de TRCFWAE. Estos árboles representan:
;; · Identificadores.
;; · Números.
;; · Operaciones binarias.
;; · Condicional, if0.
;; · Asignaciones locales recursivas, rec.
;; · Funciones anónimas de primera clase, fun.
;; · Aplicación de funciones.
(define-type RCFAE
[id (i symbol?)]
[num (n number?)]
[binop (op procedure?) (lh RCFAE?) (rh RCFAE?)]
[if0 (test-expr RCFAE?) (then-expr RCFAE?) (else-expr RCFAE?)]
[rec (id symbol?) (value RCFAE?) (body RCFAE?)]
[fun (param symbol?) (body RCFAE?)]
[app (fun-expr RCFAE?) (arg RCFAE?)])
;; Gramática para representar los ambientes de avaluación. Los ambientes son representador por listas
;; en forma de pila, de esta forma un ambiente puede estar vacío o almacenar identificadores con su
;; valor y el siguiente ambiente. Esta versión incluye ambientes recursivos.
;;
;; Un ambiente recursivo, almacenar el cuerpo de la función recursiva en una caja. Aprovechamos los
;; ascpecto imperativos del lenguaje para preservar el estado de la función en la caja, cada que
;; abrimos la caja, obtenemos la misma función.
(define-type Enviroment
[mtSub]
[aSub (id symbol?) (value RCFAE-Value?) (env Enviroment?)]
[aRecSub (id symbol?) (value boxed-RCFAE-Value?) (env Enviroment?)])
;; Predicado que un valor se encuentra en una caja (box?) y que en efecto, el valor que almacena es
;; de tipo RCFAE-Value.
;; boxedd-RCFAE-Value?: any -> boolean
(define (boxed-RCFAE-Value? value)
(and (box? value) (RCFAE-Value? (unbox value))))
;; Gramática para representar los valores devueltos por el intérprete. El intérprete puede devolver:
;; · Números.
;; · Funciones, que más bien son cerraduras. Una cerradura almacena:
;; - Los parámetros de la función.
;; - El cuerpo de la función.
;; - El ambiente donde fue definida.
(define-type RCFAE-Value
[numV (n number?)]
[closureV (param symbol?) (body RCFAE?) (env Enviroment?)])
;; Gramática para representar los ambientes de tipos. Los ambientes son representados por listas en
;; forma de pila, de esta forma un ambiente puede estar vacío o almacenar identificadores con un tipo
;; asociado y el siguiente ambiente.
(define-type TEnviroment
[t-mtSub]
[t-aSub (id symbol?) (type Type?) (env TEnviroment?)])
;; Gramática para representar los tipos del lenguaje.
(define-type Type
[number]
[tarrow (lhs Type?) (rhs Type?)])
#|--------------------------------------------------------------------------------------------------
- -
- Análisis sintácitco -
- -
--------------------------------------------------------------------------------------------------|#
;; Función que recibe una expresión en sintaxis concreta y regresa el árbol de sintaxis abstracta
;; correspondiente.
;; parse: sexp -> TRCFWAE
(define (parse sexp)
(error 'parse "Función no implementada"))
;; Función que recibe una expresión en sintaxis abstracta y regresa una versión desendulzada de
;; ésta. Simplemente convierte with en una aplicación de funciones.
;; desugar: TRCFWAE -> RCFAE
(define (desugar sexp)
(error 'desugar "Función no implementada"))
#|--------------------------------------------------------------------------------------------------
- -
- Análisis semántico -
- -
--------------------------------------------------------------------------------------------------|#
;; Función que recibe una expresión en sintaxis abstracta y regresa su evaluación. Para evaluar usa
;; un ambiente.
;; interp: RCFAE Enviroment -> RCFAE-Value
(define (interp sexp env)
(match sexp
[(id i) (lookup i env)]
[(num n) (numV n)]
[(binop op lh rh) (numV (op (numV-n (interp lh env)) (numV-n (interp rh env))))]
[(if0 test-expr then-expr else-expr)
(if (zero? (numV-n (interp test-expr env)))
(interp then-expr env)
(interp else-expr env))]
[(rec id value body) (interp body (cyclically-bind-and-interp id value env))]
[(fun param body) (closureV param body env)]
[(app fun-expr arg)
(let ([fun-val (interp fun-expr env)])
(interp
(closureV-body fun-val)
(aSub (closureV-param fun-val)
(interp arg env)
(closureV-env fun-val))))]))
;; Función que busca un valor en el ambiente indicado.
;; lookup: symbol Envirotment -> RCFAE-Value
(define (lookup id env)
(match env
[(mtSub) (error 'lookup "Identificador libre")]
[(aSub sub-id value rest-env)
(if (symbol=? id sub-id)
value
(lookup id rest-env))]
[(aRecSub sub-id value rest-env)
(if (symbol=? id sub-id)
(unbox value) ; Se obtiene un closure que hace referencia al mismo ambiente.
(lookup id rest-env))]))
;; Función que crea el ambiente recursivo.
;; cyclically-bind-and-interp: symbol RCFAE Enviroment -> Enviroment
(define (cyclically-bind-and-interp id value env)
; Creamos la caja que almacenará la función recursiva
(let* ([value-holder (box (numV 1729))]
; Creamos el ambiente y lo asociamos a la caja anterior.
[new-env (aRecSub id value-holder env)]
; Interpretamos el valor, esto nos devuelve un closure que tendrá como ambiente el new-env
[named-expr-val (interp value new-env)])
(begin
; Modificamos la caja. Ahora en lugar de almacenar 1729 almacena el closure con la función
; recursiva.
(set-box! value-holder named-expr-val)
; Regresamos el ambiente. La caja del ambiente tiene la nueva modificación.
new-env)))
#|--------------------------------------------------------------------------------------------------
- -
- Sistema Veriricador de Tipos -
- -
--------------------------------------------------------------------------------------------------|#
;; Función que recibe una expresión en sintaxis abstracta y regresa el tipo asociado.
;; typeof: RCFAE TEnviroment -> Type
(define (typeof expr env)
(error 'typeof "Función no implementada"))