Estudio de la semántica de programas a través de los interpretes



Descargar 40,28 Kb.
Fecha de conversión11.03.2017
Tamaño40,28 Kb.

Intérpretes

  • Estudio de la semántica de programas a través de los interpretes
  • Proceedimientos que toman árboles abstractos de sintaxis de un programa y realizan el cálculo indicado.
  • Es un programa que consulta estructuras de datos y realiza acciones dependiendo de la estructura.
  • Parser, unparser,apply, reductores del cálculo lambda.
  • Los intérpretes que desarrollaremos revelaran la semántica de lenguajes de programación para entender los lenguajes que estudiaremos

Intérpretes

  • En el curso se desarrollará un intérprete simple.
  • Este reflejará la semántica fundamental de muchos lenguajes de programación moderna.
  • Lo construiremos en etapas comenzando por las formas más simples como son: literales, variables y aplicaciones.Después agregaremos otras formas una por una.
  • Una parte importante de la especificación de cualquier lenguaje de programación es el conjunto de valores que el lenguaje manipulará:valores expresados y valores denotados.

Intérpretes

  • Los valores expresados son los posibles valores de expresiones, y los valores denotados son los valores afectados a variables.
  • Por ejemplo, existen muchas clases de valores expresados tales como números, parejas, caracteres y cadenas, pero solo hay un tipo de valores denotados: celdas que contienen valores expresados.
  • Por simplicidad, nuestro lenguaje tendrá solo dos tipos de valores expresados: enteros y procedimientos.

Intérpretes

  • Por el momento, los valores denotados serán los mismos que los valores expresados. Escribiremos esto como sigue:
  • Expressed Value=Number+Procedure
  • Denoted Value=Number+Procedure
  • Usamos ecuaciones como estas como recordatorio informal de valores expresados y denotados, para cada uno de nuestros intérpretes.
  • También hacemos distinción entre lenguaje definido y lenguaje de definición.
  • En nuestro caso el lenguaje de definición es Scheme.

Sintaxis abstracta

  • ::= lit (datum)
  • |
  • | app (rator rands)
  • ::=|()
  • ::=( )|( {,}*)
  • ::=
  • ::= varref (var)

Expresiones típicas de nuestro lenguaje

  • 3
  • n
  • +(3, n)
  • add1(+(3, n))
  • (add1)(+(3, n))
  • Los árboles de sintaxis abstracta son construidos, como antes, con
  • registros con definiciones de tipos basados en los nombres
  • abstractos dados por la gramática.
  • (define-record lit (datum))
  • (define-record varref (var))
  • (define-record app (rator rands))

Registros variantes y variant-case

  • Un tipo que combina uno o mas tipos es llamado union type.
  • Un árbol es la unión de nodos interiores y hojas
  • Un union type cuyos alternativas son records se les llama registros variantes.
  • Scheme no provee directamente tipos variantes, pero pueden usarse implicitamente por medio del uso de predicados para cada tipo.
  • En el curso se usaran con cierta frecuencia los registros variantes, por lo cual conviene tener de ramificación sobre este tipo de registro.

Registros variantes y variant-case

  • Mas aún, cuando el tipo ha sido identificado, es útil afectar todos o algunos de los valores de sus campos con variables nombradas después de sus campos.
  • La forma especial que realiza ambos servicios es el variant-case cuya sintáxis es:
  • (variant-case record-expression
  • ( name1 field-list1 consequent1)
  • ( namen field-listn consequentn)
  • (else alternative))

Intérprete simple usando variant-case

  • (define eval-exp
  • (lambda (exp)
  • (variant-case exp
  • (lit (datum) datum)
  • (varref (var) (apply-env init-env var))
  • (app (rator vrands)
  • (let ((proc (eval-exp rator))
  • (args (eval-rands rands)))
  • (apply-proc proc args)))
  • (else (error “Invalid abstract syntax: “ exp)))))
  • (define eval-rands
  • (lambda (rands)
  • (map eval-exp rands)))

Comentarios sobre el intérprete

  • El campo rands del registro app contiene una lista de árboles sintácticos abstractos para aplicaciones de operandos.
  • El árbol sintáctico abstracto para add1(+(3, n)) y (add1)(+(3, n)) sería
  • #(app
  • #(varref add1)
  • (# (app
  • #(varref +)
  • (# (lit 3) #(varref n)))))

Comentarios sobre el intérprete

  • En el intérprete anterior, el procedimiento principal, eval-exp, le es pasado el árbol sintáctico abstracto de una expresión y regresa el valor de la expresión.
  • Sigue un patrón familiar, despachando en función del tipo de registro en la raíz del árbol.
  • El primer caso es fácil: Si exp es una literal, regresa datum.
  • Si exp es un nodo que representa una variable, el valor de la expresión debe de ser el valor de afectación de la variable.Ahora hay que decidir de donde vamos a obtener dicho valor. Necesitamos dar un environement: una función finita que toma el símbolo y regresa el valor asociado.

Comentarios sobre el intérprete

  • Este environement es consultado para hallar el valor de cualquier variable en el lenguaje.
  • En este lenguaje por el momento habrá un solo environement incial init-env
  • Definimos un ADT para environements tomando el ADT de función finita
  • (define the-empty-env (create-empty-ff))
  • (define extend-env extend-ff*)
  • (define apply-env apply-ff)

Comentarios sobre el intérprete

  • Cuando se evalúa una variable, el intérprete solo necesita consultar su valor en init-env. Entonces tenemos la siguiente clausula del variant-case en eval-exp:
  • Dado que el operador puede ser una expresión, debemos de evaluarla para obtener el procedimiento a llamar. Esto es llevado facilmente a cabo con la llamada recursiva
  • El lenguaje que estamos interpretando usa un orden de evaluación aplicativo: los operandos son evaluados antes de llamar al procedimiento. (eval-rands)
  • (varref (var) (apply-env init-env var))
  • (eval-exp rator)

Comentarios sobre el intérprete

  • Como realizar las aplicaciones depende de la representación de los procedimientos.
  • Aislamos dicha dependencia dentro del procedimiento apply-proc.
  • Volviendo a la representación de procedimientos primitivos

  • ::=
    prim-proc(prim-op)

  • ::= +
  • | -
  • | *
  • | add1
  • | sub1

Comentarios sobre el intérprete

  • Esta especificación dice que hay solo un tipo de procedimiento primitivo, y que hay cinco de estos.
  • Estos procedimientos son representados por records del la forma (define-record prim-proc (prim-op))
  • Esto nos permitirá hacer la distinción de otros tipos de procedimientos.
  • El único elemento almacenado en prim-proc el símbolo que nombra al operador.
  • Los procedimientos make-prim-proc y apply-proc definen un ADT para procedimientos
  • Todos lo que apply-proc hace hasta el momento es verificar que su primer argumento es un procedimiento primitivo y después invoca apply-prim-op

Procedimientos apply-proc y apply-prim-op

  • (define apply-proc
  • (lambda (proc args)
  • (variant-case proc
  • (prim-proc (prim-op) (apply-prim-op args))
  • (else (error “Invalid procedure:” proc)))))
  • (define apply-prim-op
  • (lambda (prim-op args)
  • (case prim-op
  • ((+) (+ (car args) (cadr args)))
  • ((- ) (- (car args) (cadr args)))
  • ((* ) (* (car args) (cadr args)))
  • ((add1) (+ (car args) 1))
  • ((sub1) (- (car args) 1))
  • (else (error “Invalid prim-op name:” prim-op)))))

Comentarios

  • Podriamos haber representado los operadores primitivos de manera
  • que apply-prim-op realice su trabajo. El este caso elegimos representar
  • cada operador por un símbolo: el mismo símbolo que medio ambiente
  • inicial usará como nombre para ese operador primitivo. Por lo tanto
  • podemos construir el medio ambiente inicial como:
  • (define prom-op-names ‘(+ - * add1 sub1))
  • (define init-env
  • (extend-env
  • prim-op-names
  • (map make-prim-proc prim-op-names)
  • the-empty-env))

Comentarios

  • Esto completa nuestro primer intérprete. Antes de poder probarlo,
  • sin embargo, necesitamos una parte que parsee expresiones e invoque
  • eval-exp. Hay varios enfoques para construir esta parte.Una es ignorar
  • los detalles de la sintaxis concreta y escribir nuestras expresiones como
  • estructuras de lista. Entonces en vez de escribir add1(+ (3, n )),
  • escribiremos (add1 (+ 3 n)). Para este enfoque, todo lo que necesitamos
  • es un procedimiento parse, que tome una lista de Scheme, un símbolo, o
  • un número y regrese el correspondiente árbol de sintáxis abstracta
  • >(define run
  • (lambda (x)
  • (eval-exp (parse x))))
  • >(run ‘5)
  • 5
  • >(run ‘(add1 2))
  • 3

Evaluación condicional

  • Para el estudio de la semántica de nuetro lenguaje agregaremos algunas características que aparecen en una amplia gama de lenguajes de programación.
  • Para cada característica, agregaremos una regla de producción a , una especificación formal, e incluiremos una línea de variant-case en eval-exp para manejar el nuevo nodo del árbol de sintáxis abstracta para el nuevo tipo.
  • ::= if then else if (test-exp then-exp else-exp)
  • (define-record if (test-exp then-exp else-exp))
  • ;;; para evitar agregar booleanos 0=false y true=*
  • (define true-value?
  • (lambda (x)
  • (not (zero? x))))
  • --> if 1 then 2 else 3;
  • 2
  • -->if -(3,+(1,2)) then 2
  • else 3;
  • 3

Evaluación condicional

  • Este comportamiento se obtiene agregando la siguiente clausula a eval-exp:
  • (if (test-exp then-exp else-exp)
  • (if (true-value? (eval-exp test-exp))
  • (eval-exp then-exp)
  • (eval-exp else-exp)))
  • Este código utiliza la forma especial if de Scheme para definir la
  • forma if del lenguaje que estamos definiendo, lo cual pone de
  • manifiesto nuestra dependencia en el entendimiento del lenguaje
  • de definición que en éste caso es Scheme.

Afectación local

  • Abordaremos el problema de la creación de variables locales en el contexto de la forma let.
  • Agregamos al lenguaje interpretado una sintaxis en la cual la palabra reservada let es seguida de una seria de declaraciones, la palabra reservada in, y el cuerpo. Por ejemplo
  • let x = 5;
  • y = 6
  • in +(x, y)

Afectación local

  • La forma entera let es una expresión, como lo es también su cuerpo, entonces las formas let pueden anidarse.
  • Las reglas de alcance léxico usual para estructuras de bloque se pueden aplicar: la region de afectación de una declaración let es el cuerpo de la expresión let, y las afectaciones interiores crean hoyos en el alcance de las afectaciones mas externas.
  • Las referencias a x en la primera applicación se refiere a la declaración externa, mientras que las declaraciones en la segunda se refieren a la mas interna lo cual da 18.
  • let x = 3;
  • in let x = *(x, x)
  • in +(x, x)

Sintaxis concreta del let

  • ::= let <decls> in let (decls body)
  • ::={;}*
  • ::== decl (var exp)
  • La sintaxis abstracta usa los siguientes tipos de recgistro:
  • (define-record let (decls body))
  • (define-record decl (var exp))
  • El campo decls del let tendrá una lista no vacía de registros decl.
  • El body del let deberá evaluarse en un environement en el cual las
  • variables declaradas esten afectadas por valores de las expresiones
  • en su lado derecho, mientras que las otras afectaciones deberán tomarse
  • del medio ambiente en el cual la expresion completa de let es evaluada.

Intérprete con let

  • (define eval-exp
  • (lambda (exp env)
  • (variant-case exp
  • (lit (datum) datum)
  • (varref (var) (apply-env env var))
  • (app (rator rands)
  • (let ((proc (eval-exp rator env))
  • (args (eval-rands rands env)))
  • (apply-proc proc args)))
  • (if (test-exp then-exp else-exp)
  • (if (true-value? (eval-exp test-exp env))
  • (eval-exp then-exp env)
  • (eval-exp else-exp env)))
  • (let (decls body)
  • (let ((vars (map decl->var decls))
  • (exps (map decl->exp decls)))
  • (let ((new-env (extend-env vars
  • (eval-rands exps env)
  • env)))
  • (eval-exp body new-env))))
  • (else (error “Invalid abstract syntax:” exp)))))

Procedimientos

  • Para que nuestro intérprete sea útil debemos permitir definir nuevos procedimientos diferentes a los que definimos en nuestro medio ambiente inicial.
  • Usaremos la sintaxis siguiente:
  • Entonces podremos escribir como
  • Dado que proc puede usarse en cualquier parte donde se permita una expresión, también podemos escribir
  • ::= proc proc (formals body)
  • ::= ( ) | ( )
  • ::= {,}*
  • let f = proc (y, z) *(y, -(z, 5))
  • in f(2, 8)
  • (proc (y, z) *(y, -(z, 5)))(2, 8)

Procedimientos

  • Cuando se aplica un procedimiento, su cuerpo es evaluado en un medio ambiente que afecta los parámetros formales del procedimiento con los argumentos de la aplicación.
  • Lo anterior requiere que se retengan las afectaciones al momento que el procedimiento fué creado. Cosidere el ejemplo siguiente:
  • Con el fin de retener dichas afectaciones, este debe ser un paquete cerrado, independiente del medio ambiente en el que es usado.
  • let x = 5;
  • in let f = proc (y, z) *(y, -(z, x));
  • x = 28
  • in f(2, 8)

Procedimientos

  • Dicho paquete es llamado cerradura o closure.
  • A fin de que sea autocontenido, una cerradura debe de contener el cuerpo del procedimiento, la lista de sus parámetros formales, y las afectaciones a sus variables libres.
  • Es conveniente almacenar el medio ambiente de creación completo, en vez de solo guardar las afectaciones a las variables libres.
  • En una versión compilada, en la cual los cálculos de direcciones léxicas ya se realizaron, solo se requiere guardar en el closure el número de parámetros formales, junto con las afectaciones a variables libres y la referencia al código compilado del cuerpo.
  • (define-record closure (formals body env))

Procedimientos

  • Hay que modificar apply-proc para que reconozca closures.
  • Podemos describir los datos que apply-proc necesita reconocer con la ecuación siguiente
  • El procedimiento apply-proc primero checa que tipo de procedimiento fué pasado. Si fué un closure , simplemente invoca al cuerpo del closure en un medio ambiente extendido apropiado.
  • Procedure= Primitive Procedure + closure

Procedimientos

  • (define apply-proc
  • (lambda (proc args)
  • (variant-case proc
  • (prim-proc (prim-op) (apply-prim-op prim-op args))
  • (closure (formals body env)
  • (eval-exp body (extend-env formals args env)))
  • (else (error “Invalid procedure:” proc)))))
  • Cuando una expresión proc es evaluada, todo lo que se hace es
  • construir un closure y regresarlo inmediatamente.

Procedimientos

  • (define eval-exp
  • (lambda (exp env)
  • (variant-case exp
  • (proc (formals body)
  • (make-closure formals body env))
  • …)))
  • El cuerpo del procedimiento no se evalúa aqui: no puede ser evaluado
  • hasta que los valores de los parámetros formales se conocen, cuando
  • el closure es aplicado a algunos argumentos.

Intérprete con procedimientos

  • (define eval-exp
  • (lambda (exp env)
  • (variant-case exp
  • (lit (datum) datum)
  • (varref (var) (apply-env env var))
  • (app (rator rands)
  • (let ((proc (eval-exp rator env))
  • (args (eval-rands rands env)))
  • (apply-proc proc args)))
  • (if (test-exp then-exp else-exp)
  • (if (true-value? (eval-exp test-exp env))
  • (eval-exp then-exp env)
  • (eval-exp else-exp env)))
  • (let (decls body)
  • (let ((vars (map decl->var decls))
  • (exps (map decl->exp decls)))
  • (let ((new-env (extend-env vars
  • (eval-rands exps env)
  • env)))
  • (eval-exp body new-env))))
  • (proc (formals body)
  • (make-closure formals body env))
  • (else (error “Invalid abstract syntax:” exp)))))
  • (define apply-proc
  • (lambda (proc args)
  • (variant-case proc
  • (prim-proc (prim-op)(apply-prim-op
  • prim-op args))
  • (closure (formals body env)
  • (eval-exp body (extend-env formals
  • body env)))
  • (else (error “Invalid procedure:”
  • proc)))))

Asignaciones a variables

  • Queremos agregar a nuestro intérprete asignaciones (:=)
  • Primero hay que cambiar nuestra abstracción de medio ambiente, pues como está no permite modificar el valor de afectación de una variable. Es decir que los valores expresados y los denotados son los mismos.
  • En la modificación introduciremos indirección en las afectaciones, es decir que las variables estaran afectadas por localidades de memoria.
  • Scheme no permite modificar localidades de memoria, pero si permite cambios en elementos mutables de estructuras de datos por medio de por ej. set-cdr!. Usaremos celdas para modelar localidades de memoria y modificaremos el intérprete por medio de los siguientes dos cambios.
  • Denoted Value = Cell (Expressed Value)

Asignaciones a variables

  • (extend-env formals
  • (map make-cell args)
  • env)
  • (extend-env formals args env)
  • Segundo, cuando las variables son referenciadas, es necesario
  • desreferenciarlas ya que sus afectaciones son ahora celdas.
  • Entonces en el variant-case del eval-exp hay que hacer el siguiente
  • cambio.
  • (varref (var)
  • (cell-ref (apply-env
  • env var)))
  • en lugar de
  • (varref (var)(apply-env env var))
  • Este cambio al aplicarlo al paso de parámetros es lo que se conoce como
  • llamada por valor.

Asignaciones a variables

  • en la sintáxis abstracta hay que agregar:
  • ::=:= varassign (var exp)
  • Hay que definir el siguiente tipo de records
  • (define-record varassign (var exp))
  • En eval-exp hay que agregar la cláusula siguiente:
  • (varassign (var exp)
  • (cell-set! (apply-env env var) (eval-exp exp env)))

Intérprete con asignaciones y llamadas por valor

  • (define eval-exp
  • (lambda (exp env)
  • (variant-case exp
  • (lit (datum) datum)
  • (varref (var) (cell-ref (apply-env env var)))
  • (app (rator rands)
  • (let ((proc (eval-exp rator env))
  • (args (eval-rands rands env)))
  • (apply-proc proc args)))
  • (if (test-exp then-exp else-exp)
  • (if (true-value? (eval-exp test-exp env))
  • (eval-exp then-exp env)
  • (eval-exp else-exp env)))
  • (let (decls body)
  • (let ((vars (map decl->var decls))
  • (exps (map decl->exp decls)))
  • (let ((new-env (extend-env vars
  • (eval-rands exps env)
  • env)))
  • (eval-exp body new-env))))
  • (proc (formals body) (make-closure formals body env))
  • (varassign (var exp)
  • (cell-set! (apply-env env var) (eval-exp exp env)))
  • (else (error “Invalid abstract syntax:” exp)))))
  • (define apply-proc
  • (lambda (proc args)
  • (variant-case proc
  • (prim-proc (prim-op)(apply-prim-op
  • prim-op args))
  • (closure (formals body env)
  • (eval-exp body
  • (extend-env
  • formals
  • (map make-cell args)
  • env)))
  • (else (error “Invalid procedure:”
  • proc)))))

Recursión

  • Tenemos 2 enfoques para implementar recursividad
  • El primer enfoque es el de los combinadores Y, el cual es muy importante desde el punto de vista teórico ya que solo requiere de tener la habilidad para crear y aplicar operadores de primara clase. Por ejemplo:
  • Para definir en cálculo lambda
  • un procedimiento para el factorial:
  • (lambda (g)
  • (lambda (n)
  • (if (zero? n) 1 (* n (g (- n 1))))))
  • Pongamos que ésta es llamada f.
  • ¿Como convertirlo a una función recursiva?
  • Hay que definir una función Y tal que (Y f)
  • sea nuestro procedimiento recursivo.
  • La suposición de que la recursión puede ser
  • obtenida por referencia a g puede ser satisfecha
  • si afectamos g con (Y f) con la aplicación (f (Y f))
  • es decir que (Y f) = (f (Y f)).Entonces Y puede ser
  • definida como:
  • (lambda (f)
  • ((lambda (x) (f (x x)))
  • (lambda (x) (f (x x)))))

Recursión

  • Podríamos implementar directamente un combinador Y de orden aplicativo pero sería muy ineficiente.
  • El segundo enfoque es el usado para definir letrec en Scheme.
  • (letrec ((var1 exp1) … (varn expn))
  • body)
  • => (let ((var1 ‘*) …(varn ‘*))
  • (let ((v1 exp1) … (vn expn))
  • (set! var1 v1)
  • (set! varn vn)
  • ‘unspecified)
  • body)

Recursión

  • De esta forma los procedimientos recursivos son creados encerrandolos en un medio ambiente que incluye las variables a las cuales afectarán.
  • Tratar de hacer referencia a alguna de las vari en alguna expj puede dar resultados extraños, pero después de ejecutar los set! todas las celdas contendran los valores correctos.
  • Si cada expi es una expresión lambda, entonces tenemos la garantía de que ninguna variable del letrec será referenciada prematuramente.
  • El orden de evaluación de las expi no es importante.
  • Este enfoque implementa la recursión introduciendo ciclos en la estructura de datos que reperesenta el medio ambiente de la ejecución.

Recursión

  • Por ejemplo, el medio ambiente creado por la rutina que se muestra a continuación contiene una circularidad. El medio ambiente contiene una afectación que apunta a un closure que a su vez contiene una referencia al medio ambiente.
  • (letrec ((fact (lambda (n)
  • (if (zero? n)
  • 1
  • (* n (fact (- n 1)))))))
  • …)
  • fact
  • closure
  • (n)
  • ...

Recursión

  • En la mayoría de los lenguajes solo los procedimientos se pueden definir recursivamente, y se crean ambientes circulares por el mismo mecanismo que crea los procedimientos recursivos.
  • Veremos como agregar recursión a nuestro intérprete sin circularidad.
  • Usaremos una variación en la sintáxis del letrec que restringe el lado derecho de la declaración recursiva a expresiones proc. La sintáxis abstracta es:
  • ::= letrecproc
    in letrecproc(procdels
  • body)

  • ::=
    {;
    }*

  • ::== procdel (var formals body)

Recursión

  • La mano izquierda de la declaración recursiva es el nombre del procedimiento recursivo y la lista de parámetros.
  • A la derecha del sigo = es el cuerpo del procedimiento.
  • Ejemplos:
  • letproc
  • fact(x) = if zero(x) then 1 else *(x, fact(sub1(x)))
  • in fact(6)
  • o
  • letproc
  • even(x) = if zero(x) then 1 else odd(sub1(x));
  • odd(x) = if zero(x) then 0 else even(sub1(x))
  • in odd(13)

ADT de medio ambiente sin closures circulares

  • (define-record extended-rec-env (vars vals old-env))
  • (define extend-rec-env
  • (lambda (procdels env)
  • (make-extend-rec-env
  • (map procdecl->var procdels)
  • (list->vector
  • (map (lambda (procdecl)
  • (make-proc
  • (procdecl->formals procdecl)
  • (procdecl->body procdecl)))
  • procdecls))
  • env)))
  • (define apply-env
  • (lambda (env var)
  • (variant-case env
  • (extended-rec-env (vars vals old-env)
  • (let ((p (ribassoc var vars cals ‘*fail*)))
  • (if (eq? p ‘*fail*)
  • (apply-env old-env var)
  • (make-closure (proc->fornals p) (proc->body p) env))))
  • …)))

Alcance y asignación dinámicos

  • Existen 2 enfoques para reorganizar la información en un medio ambiente.
  • Primer enfoque es, alcance dinámico, el cual es un mecanismo de afectación que agrega expresividad adicional al precio de hacer los programas bastante dificiles de entender.
  • Segundo enfoque es,asignación dinámica, que da mas expresividad al alcance dinámico,sin abandonar la claridad del alcance léxico.

Alcance dinámico

  • Ya dijimos que cuando un procedimiento es aplicado, es el medio ambiente en el cual éste fué creado el que se usa para evaluar el cuerpo.
  • Esto se necesita para que las variables tengan un alcance léxico, pero además se requiere de que se forme un nuevo closure cada que se avalúa una expresión proc.
  • Parecería mas simple evaluar el cuerpo en el ambiente de aplicación. Considere el programa siguiente:
  • Por el alcance léxico el p tomaría el valor de a=3 y la expresión entera dería por resultado 25. Si por el contrario p se evaluara en su ambiente de aplicación daría 35.En éste último caso el alcance es dinámico y no léxico.
  • let a = 3
  • in let p = proc (x) +(x, a);
  • a = 5
  • in *(a, p(2))

Alcance dinámico

  • Lo anterior se conoce como afectación dinámica y obedece la siguiente regla:Una afectación dinámica es existente durante la evaluación del cuerpo asociado con la forma de la afectación. Referencias a una variable afectada dinámicamente se refiere a la más reciente afectación existente de dicha variable.
  • Es mas dificil razonar sobre el alcance dinámico que sobre el léxico pero es mas facil de implementar. Dado que los procedimientos no son cerrados sobre su ambiente de creación, la única información que debemos guardar en un procedimiemnto es la lista de parámetros formales y su cuerpo. La clausula correspondiente en el variant-case de eval-exp es: (proc (formals body) exp).
  • La evaluación de expresiones proc se hace mas simple y eficiente.
  • Cuando apply-proc recibe un record tipo proc , debe de extender el ambiente corriente para obtener el ambiente en el cual evaluar el cuerpo. Esto obliga a pasarlo como parámetro a apply-proc.
  • El ambiente obedece una política LIFO

Intérprete con alcance dinámico

  • (define eval-exp
  • (lambda (exp env)
  • (variant-case exp
  • (lit (datum) datum)
  • (varref (var) (cell-ref (apply-env env var)))
  • (app (rator rands)
  • (let ((proc (eval-exp rator env))
  • (args (eval-rands rands env)))
  • (apply-proc proc args env)))
  • (if (test-exp then-exp else-exp)
  • (if (true-value? (eval-exp test-exp env))
  • (eval-exp then-exp env)
  • (eval-exp else-exp env)))
  • (let (decls body)
  • (let ((vars (map decl->var decls))
  • (exps (map decl->exp decls)))
  • (let ((new-env (extend-env vars
  • (eval-rands exps env)
  • env)))
  • (eval-exp body new-env))))
  • (proc (formals body) exp))
  • (varassign (var exp)
  • (cell-set! (apply-env env var) (eval-exp exp env)))
  • (else (error “Invalid abstract syntax:” exp)))))
  • (define apply-proc
  • (lambda (proc args current-env)
  • (variant-case proc
  • (prim-proc (prim-op)(apply-prim-op
  • prim-op args))
  • (proc (formals body)
  • (eval-exp body
  • (extend-env
  • formals
  • (map make-cell args)
  • current-env)))
  • (else (error “Invalid procedure:”
  • proc)))))

Asignación dinámica

  • Los intérpretes que se han examinado introdujeron afectación con alcance léxico. Estas afectaciones tienen una extensión indefinida, es decir que son retenidas tanto tiempo como se necesiten.
  • Las afectaciones son retenidas en el closure tanto tiempo como se necesite tener acceso a éste.
  • Después vimos como crear afectaciones con alcance dinámico y vimos como tienen existencia dinámica.
  • Ahora exploramos otra alternativa: asignaciones con extensión dinámica en afectaciones con alcance léxico.
  • Esto es llamado afectación fluída o fluid binding.

Asignación dinámica

  • En el lenguaje definido asignación dinámica usando la forma de sintáxis concreta y abstracta siguiente:
  • El efecto de
  • es asignar temporalmente el valor de exp a var, evaluar body, reasignar a var su valor original, y regresar el valor de body. Por ejemplo en:
  • ::=:= during dynassign (var exp body)
  • var:= exp during body
  • let x = 4
  • in let p = proc (y) +(x, y)
  • in +(x := 7 during p(1),
  • p(2))

Asignación dinámica

  • El valor de x, que es libre en p , es 7 en la llamada p(1), pero es regresada a 4 en la llamada p(2), entonces el valor de la expresión es 8+6 = 14.
  • Esto puede implementarse en una clausula del variant-case como sigue:
  • (dynassign (var exp body)
  • (let ((a-cell (apply-env env var))
  • (b-cell (make-cell (eval-exp exp env))))
  • (cell-swap! a-cell b-cell)
  • (let ((value (eval-exp body env)))
  • (cell-swap! a-cell b-cell)
  • value)))


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal