#lang plai #|-------------------------------------------------------------------------------------------------- - - - Gramáticas necesarias - - - --------------------------------------------------------------------------------------------------|# ;; Gramática para representar los árboles de sintaxis abstracta de RCFWAE. 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 RCFWAE [idS (i symbol?)] [binopS (op procedure?) (lh RCFWAE?) (rh RCFWAE?)] [numS (n number?)] [if0S (test-expr RCFWAE?) (then-expr RCFWAE?) (else-expr RCFWAE?)] [withS (id symbol?) (value RCFWAE?) (body RCFWAE?)] [recS (id symbol?) (value RCFWAE?) (body RCFWAE?)] [funS (param symbol?) (body RCFWAE?)] [appS (fun-expr RCFWAE?) (arg RCFWAE?)]) ;; Gramática para representar la versión sin azúcar sintáctica de RCFWAE. 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?)]) #|-------------------------------------------------------------------------------------------------- - - - Análisis sintácitco - - - --------------------------------------------------------------------------------------------------|# ;; Función que recibe una expresión en sintaxis concreta y regresa el árbol de sintaxis abstracta ;; correspondiente. ;; parse: sexp -> RCFWAE (define (parse sexp) (match sexp ; Si es un símbolo: 'foo [(? symbol?) (idS sexp)] ; Si es un número: 1729 [(? number?) (numS sexp)] ; Si es un condicional if0: {if0 {+ 10 -10} 2 3} [(list 'if0 test-expr then-expr else-expr) (if0S (parse test-expr) (parse then-expr) (parse else-expr))] ; Si es un with: {with {a 2} {+ a a}} [(list 'with (list id value) body) (withS id (parse value) (parse body))] ; Si es un rec: {rec {fac {fun {n} {if0 n 1 {* n {fac {- n 1}}}}}} {fac 5}} [(list 'rec (list id value) body) (recS id (parse value) (parse body))] ; Si es una función: {fun {x} x} [(list 'fun (list param) body) (funS param (parse body))] [(cons x xs) (case x ; Si es una operación binaria: {+ 1 {* 2 3}} [(+ - * /) (binopS (elige x) (parse (car xs)) (parse (cadr xs)))] ; Si es una aplicación de función: {{fun {x} x} 2} [else (appS (parse x) (parse (car xs)))])])) ;; Función que hace ilustra la relación entre el lenguaje objetivo y el anfitrión. ;; elige: sexp -> procedure (define (elige sexp) (match sexp ['+ +] ['- -] ['* *] ['/ /])) ;; 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: RCFWAE -> RCFAE (define (desugar sexp) (match sexp [(idS i) (id i)] [(numS n) (num n)] [(binopS op lh rh) (binop op (desugar lh) (desugar rh))] [(if0S test-expr then-expr else-expr) (if0 (desugar test-expr) (desugar then-expr) (desugar else-expr))] [(withS id value body) (app (fun id (desugar body)) (desugar value))] [(recS id value body) (rec id (desugar value) (desugar body))] [(funS param body) (fun param (desugar body))] [(appS fun-expr arg) (app (desugar fun-expr) (desugar arg))])) #|-------------------------------------------------------------------------------------------------- - - - 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)))