From: Subject: Date: Sat, 2 Dec 2016 03:25:30 -0000 MIME-Version: 1.0 Content-Type: multipart/related; type="text/html"; boundary="----MultipartBoundary--DK8yaVFtLdnZe1Dhj6yUqZWzpPzQpfmT2Uj6tLZ1lQ----" ------MultipartBoundary--DK8yaVFtLdnZe1Dhj6yUqZWzpPzQpfmT2Uj6tLZ1lQ---- Content-Type: text/html Content-ID: Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/Users/Vichoko/Dropbox/Aplicaciones/U-Cursos/CC4101-1%20Lenguajes%20de%20Programaci%C3%B3n%202016/mis_documentos/Apuntes/estudio_c2.md

E= ntra desde Lazy hasta Garbage Collection Clase 11 a 19

Eager vs Lazy (Clase 11 y 12)

Forma de interpretar expresiones *No confundir eager-lazy con estatico-dinamico

Eager

Encuentra expresi=C3=B3n y la interpreta directamente. Version actual de nuestro interprete.

Lazy

Evaluas cosas cuando las necesitas para darle significado a un programa.=

Ejemplos Lazy

Haskell: Lenguaje fx puro, tipado estatico + inferencia de tipos.
Shell: Cada programa puede ser un generador o consumidor de strings. P= uede recibir un string infinito y ser cap=C3=A1z de procesarlo por partes, = y quiz=C3=A1s imprimir algo infinito.

Implementar Lazyness

En nuestro lenguaje. Tenemos dos opciones:

Call-by-name: Se asignan nombres a expresiones, se evalua la expresion = segun sea necesario.
Call-by-need: Mismo concepto, pero adem=C3=A1s se tiene un cach=C3=A9 p= or expresion que guarda valor.

Call-by-name

Asignar nombres a expresiones.

Nuevo tipo de valor: Expre= sion Closure

Misma idea de cerrar definicion de funciones, pero ahora con respecto a= cualquier expresion que no entregue de forma inmediata un nuevo tipo de va= lor.

(deftype Val
  (numV n)
  (closureV param body env)
  (exprV expr env)) ; una expresi=
on es la expresion misma, y el ambiente en el
                    ; que fue definida

Funcion que reduzca= exprV a Val

;; strict :: Val -> Val (sin exprV)
(define (strict expr)
  (match expr
    ; si encontramos una exprV, usar el interpretador para interpretarlo
    [(exprV expr env) (strict (interp expr env))]
    [else expr]))

Nuestro primer acercamiento (Call-by-name) incluye una func= i=C3=B3n strict que fuerza la interpretaci=C3=B3n de una expre= si=C3=B3n a un valor. La cual se llama expl=C3=ADcitamente cuando se necesi= ta el valor.=20 Por ejemplo:

Para sumar/restar:

 [(add l r)
 (sumar-num (strict (interp l env)) (strict (interp r env)))`]

Para la condici=C3=B3n de un if:

 [(if0 c t f)=20
  (if (zero-num? (strict (interp c env)=
))
      (interp t env)
      (interp f env))]

La aplicacion de funci=C3=B3n:

[(app fun-expr arg-expr)
  (def fun-val (strict (inter=
p fun-expr env)))
  (def arg-val (exprV arg-exp=
r env))
  (interp (closureV-body fun-val)
           (anEnv (closureV-param fun-val)
                  arg-val (closureV-env fun-val)))=20
  ]

Para cualquier caso que necesitemos un valor expl=C3=ADcitamente, disti= nto a una expresi=C3=B3n (exprV). Nuestros valores son actualmente:

        (deftype Val
          (numV n);strict reduce a esto
          (closureV param body env); o a esto
          (exprV expr env)); pero=
 no a esto, esto es una expr como valor

Los puntos donda l aimplementacon de un lenguaje esta oblig= ado a reducir uan expr a un valor son los puntos de strictness.

Problema

(run '{with {x {+ 4 5}}
             {with {y {+ x x}}
                   {with {z y}
                         {with {x 4}
                               z}}}}
                   )

Se debe reducir la expresi=C3=B3n: {+ 4 5} a (numV 9) multi= ples veces. Se estan haciendo calculos de m=C3=A1s.

Call-by-Need

El r=C3=A9gimen call-by-need (cajas) soluciona este problema guardando e= l valor de interpretar la expresion en un espacio mutable.

Consecuencias de introducir= mutaci=C3=B3n

Algunas funciones tienen side-efects.
Las funcones ya no depende solamente de sus valroes de entrada.

Esto dificulta el testeo y dificulta la programaci=C3=B3n.

Implementaci=C3=B3n

(deftype Val
  (numV n)
  (closureV param body env)
  (exprV expr env cache))

Al crean una exprV se guarda un valor inicial (#f) en caja en cache.
Al calcular el valor se revuisa si esta en la caja, si no esta se calcu= la y guarda en la caja.

Fun `strict` debe ponerse en el caso que la caja sea #f o hay a= lgo:

;; strict :: Val -> Val (sin exprV)
(define (strict expr)
  (match expr
    [(exprV expr env cache)
     (if (=
not (unbox cache))
         ; si nos encontramos con #f, hay que =
evaluar la expresion
         (local ([def val (strict (inte=
rp expr env))])
           (printf "Evaluando exprV a ~v~n" val)
           (set-box! cache val)   ; actualizar el valor en cache
           val)   ; y retornar el valor=
 para su uso inmediato
         (begin   ; sino, solo debemos retornar el valor del cache
           (printf "Usado valor del cache value~v~n" (unbox cache))
           (unbox cache)))]
    [else expr]))

Al aplicar una fun los argumentos deben setearse con la caja= en #f

;; interp :: Expr Env -> V=
al
(define (interp expr env)
  (match expr
    [(num n) (numV n)]
    [(add l r) (sumar-num (strict (interp l env)) (strict (interp r env)))]
    [(sub l r) (restar-num (strict (interp l env)) (strict (interp r env)))=
]
    [(if0 c t f)=20
     (if (zero-num? (strict (interp c e=
nv)))
         (interp t env)
         (interp f env))]
    [(id s) (lookup-env s env)]
    [(fun id body) (closureV id body env)]
    [(app fun-expr arg-expr)
     (def=
 fun-val (strict (in=
terp fun-expr env)))=20
     (def=
 arg-val (exprV arg-=
expr env (box #f)))  ; aqui esta el cambio
     (interp (closureV-body fun-val)
              (anEnv (closureV-param fun-val)
                     arg-val (closureV-env fun-val)))=20
     ]))

Consideraciones

Usando =C3=A9ste cache se supone que la expreson tendra el mismo valor = cada vez que la evaluamos. Haskell (Lazy con cache, i.e. Call-by-need) limita los efectos secundario= s para asegurar =C3=A9sta consistencia y no provee mutacion expl=C3=ADcita.=

Memoization

Asignar un cache a una funci=C3=B3n: Se guardan las entradas con las que= se invoca la fun y los resultados. Cuando se invoc nuevamente con los mismos parametros se busca en cache de M= emoization. Esto funciona en fucniones sin efectos secundarios.

Resumen reg=C3=ADmenes de evalua= ci=C3=B3n

Call by name: Lazy. Los argumentos de una funcion se reemplazan por = las expresiones que se le pasan. Las expresiones se eval=C3=BAan dentro de = la funcion seg=C3=BAn sea necesario. Ej: Se puede pasar un (/ 1 0) y si no se usa, funciona igual.
Call by value: Eager. Se reducen expr a valores antes de llamar a un= a fun.
Call by reference: Los argumentos de una funci=C3=B3n se pasan por r= eferencias (direcciones) a la variable que se le pasa. Ste regimen hace m=C3=A1s dificil al programador seguir los efectos de un= a llamada de funci=C3=B3n y puede introducir bugs sutiles.
Call by need: Cuando se eval=C3=BAa una expresi=C3=B3n, el valor es = almacenado para usos futuros. Se usa mutaci=C3=B3n (Cajas) para implementarse.

Funciones recursivas (Clase 13)

Usando nuestro Interprete eager Queremos lograr:

(run '{with {fac {fun {n}
                {if0 n
                     1
                     {* n {fac {+ n -1}}}}}}
            {fac 5}})

En sintaxis abstracta:

(with binding-id named-expr =
body)

Se interpreta named-expr, reduciendose a un valor. En nuestro ejemplo, una (closureV param body env)
Se bindea ese valor a binding-id extendiendo el ambiente.
Se interpreta el body del with con el nuevo ambiente.

Problema

Al interpretar named-expr se hace con el ambiente que le llega al with (= externo), es decir, (id 'fac) no est=C3=A1 bindeada a nada. Al interpretar se crea la clausura:

(closureV 'n body-que-usa-fac e)

Este e no contiene el bindeo de (id 'fac).

Luego se bindea 'fac a esta= clausura.

Que sabemos que contiene errores. Y el programa se caera en la interpretaci=C3=B3n del cuerpo de la funcion d= entro de la clausura.

Soluci=C3=B3n

El e que queda dentro de la clausura debe referenciar al ambiente que qu= ede despu=C3=A9s de bindear (id 'fac) a la clausura de manera cicli= ca.

El ambiente que debe quedar despues del with, es pseudo-codigo:

Env e =3D externEnviroment();

Env* E_pointer =3D malloc(Sizeof(Env))
Env outEnv =3D (anEnv (id 'fac) (ClosureV 'x body E_pointer) e)

*E_pointer =3D outEnv // Referencia ciclica
return outEnv;

Con =C3=A9sto nos aseguramos que al interpretar el cuerpo de la clausura= (Con el ambiente de la clausura), hayan referencias a la id de la funcion.

Implementaci=C3=B3n

Para nuestro lenguaje debemos definir un nuevo operador para definir fun= ciones recursivas. Esto dado que el with puede recivir cualquier expresion en su campo named-e= xpr. El nuevo operador solo recibe definiciones de funciones como named-exp= r.

; parser ;... [(list 'rec (list id named-expr) body) (rec id (parse named-expr) (parse body))] ;...
Como se pudo ver en el pseudo-codigo, debemos tener una amb= iente que sea una referencia o puntero a otro ambiente, pa= ra lograr la ciclicidad.

(deftype Env (mtEnv) (anEnv id val env) (aRecEnv id val env)) ; guardaremos e= l val en una caja, porque necesitamos cambiarlo ; cada vez que agreguemos un nivel de recursion
Hay que actualizar los lookup-env para este nuevo tipo de a= mbiente. Si el ambiente es una referencia hay que desreferenciarlo, el resto queda i= gual:

; lookup-env :: Sym Env -> Val (define (lookup-env x env) (match env [(mtEnv) (error "identificador libre!!" x)] [(anEnv id val restoEnv) (if (symbol=3D? id x) val (lookup-env x restoEnv))] [(aRecEnv id val restoEnv) (if (symbol=3D? id x) (unbox val) ; ojo que todavia hay que construir val (lookup-env x restoEnv))]))
Interpretal el cuerpo del rec con respecto al ambiente cicl= ico:

;; interp :: Expr Env -> Val (define (interp expr env) (match expr ;... [(rec id named-expr body) ; nam= ed-expr es {fun ...}; interpretar el cuerpo con respecto al ambiente ciclic= o (interp body (cyclic-env id na= med-expr env))]
Y una funcion para crear el ambiente ciclico.=20 Es un poco distinto al pseudo-codigo pero as=C3=AD es m=C3=A1s simple hacer= con racket, conceptualmente es lo mismo. Aqui ocurre la magia:

;; cyclic-env:: id expr env -> env (supuesto: expr es de tipo fun) (define (cyclic-env id expr env) ; inicialmente, no conocemos el valor de la funcion (def value-holder (box 'unspecified)) ; creamos un ambiente ciclico con este valor (def new-env (aRecEnv id value-holder env)) ; interpretamos la expresion que define la funcion con respecto al ambien= te nuevo (def fun-val (interp expr new-env)) ; queremos usar fun-val en futuros calculos ; como todos los closure en fun-val comparten el mismo binding, todos se = actualizan ; al cambiar el valor de la caja (set-box! value-holder fun-val) ; finalmente, retornamos el ambiente new-env)
Nuestro ejemplo

En nuestro ejemplo, necesitamos crear un ambiente ciclico al llegar a (rec id named-expr body) en el interpretador:

(interp '{fac 5} (cyclic-env 'fac (fun 'n ...) (mtEnv)))
Aqui esta la ejecucion linea a linea de (cyclic-env ...)

(def value-holder (box 'unspecified)) asi que value-holder es una caja con el valor 'unspecified

(def new-env (aRecEnv id value-holder env)) new-env es (aRecEnv 'fac (box 'unspecified) (mtEnv))

(def fun-val (interp expr new-env)) expr es de tipo fun, asi que fun-val es de tipo (closureV ..) en ese caso, expr es (fun 'n (if0 ...)) asi que fun-val es (closureV 'n (if0 ...) (aRecEnv 'fac (box 'unspec= ified) (mtEnv)))

(set-box! value-holder fun-val) ahora mutamos el valor de value-holder, o sea, cambia el valor de 'fac en el ambiente (aRecEnv 'fac (box 'unspecified) (mtEnv)) quedando (aRecEnv 'fac (box (closureV ...)) (mtEnv))

escribiendolo en forma completa, el ambiente queda como=20 (aRecEnv 'fac (box (closureV 'n (if0 ...) ref_a_el_mismo_ambiente)) = (mtEnv)) al hacer referencia a si mismo, podemos obtener un valor mas de 'fac a medi= da que sea necesario

new-env finalmente retornamos este nuevo ambiente

Tail-call optimization (Clase 1= 4)

Activation Stack:

Estructura para guardar/registrar que funcioneshas sido invocadas.

Esta pila guarda toda la info acerca del llamado de una funcion, inc= luyendo sus parametros, variables locales, etc.

Llamadas sucesivas hace que crezca el stack hasta que se llegue el c= aso base y se resuelva. Cuando una funcion ('caller') invoca a otra fun ('callee') se guarda la i= nfo de la fun caller en el stack (Estado actual) y se transfiere el control= a la funcion callee.

Cuando callee retorna, devuelve el control a caller (y se quita de sta= ck 'pop').

Se guarda un registro en el stAck por cada invocacion de funcion, lo= que significa que hay un limite a cuantaas llamadas recurivas podemos hace= r =3D> Stack overflow.

Clasificaciones de llamados

Independiente de si son recursivos o no.

Subproblema: Invocamos una funcion para un paso de la compuacion, y = uso su resultado para otra cosa

Reducci=C3=B3n; Si lo ultimo que hace una funcion es invocar a otra = funcion y retornar su resultado.

Ejemplos

(define (foo) (bar) (baz))
En llamada a foo: bar: Invoaci=C3=B3nm es un subproblema. baz: Invocacion es una reduccion. foo retorna su valor.

Para llamar a bar, hay que giardar info en el stack para retomar ejecuc= ion de foo.

Para llamar a baz no es necesario guardar todo.

Esta distincion de los llamados implica una distincion en su stack frame= .

Factorial Recursivo

(define fact (lambda (n) (if (zero? n) 1 (* n (fact (-n 1))))))
Es subproblema porque usa la llamada recursiva de fact para= hacer m=C3=A1s calculos.=20 No es el ultimo llamado de la funcion caller Ultima linea no significa que sea reduccion

Patron para convertir a Reducc= i=C3=B3n

Idea fundamental:

Incluir el computo acomula= do en el llamado.
Ejemplo con factorial:

; ahora la llamada es reduccion. (define fact-iter-acom (lambda (n a) (if (zero? n) a (fact-iter-acom (-n 1) ; Si es u= na reduccion =3D> stack no necesita = crecer (* n a)))) ; la que usa la persona (define fact-iter (lambda (n) (fact-iter-acom n 1)))
Computos: (fact-iter 4) =3D (fact-iter-acom 4 1) =3D (fact-iter acom 3 4) =3D (fact-iter acom 2 12) =3D (fact-iter acom 1 24) =3D (fact-iter acom 0 24) =3D 24

No es necesario guardar el estado de la funcion caller porque esta conte= nido en los parametros de la llamada.=20 Los stack-frame no se guardan.

Comportamiento de control

Comportamiento de control recursivo: (fact ...) Guarda informacion de control hastsa que la funcion invocada retorna.
Comportamiento de control iterativo: (fact-iter)=20 No necesita memoria para guardar contexto de la recursion profunda.

Lema:

El contexto de control (Info que necesito para retomar control) crece co= n la evaluacion de operandos, y no el llamado a funciones

En el caso (fact) tengo que ir guardando el contexto de las llamadas (* = i (fact ...)) para despues ir operando.

Tail-call Optimization:

Racket lo tiene.

Si lo ultimo que hace una funcion es una reduccion, la funcion calle= r no guarda su estado en el stack de activaci=C3=B3n. Cuando la funcion callee retorna, esta retorna su valor directamente al c= aller del caller.

Viene inserta en el interprete.

Ejemplo

#;(d= efine (foo) (bar) (baz)) #;(define (baz) (bar) (foo))
Se llamaran mutuamente sin guardar su estado en el stack pr= oduciendo una recursion infinita.

No hay stack-overflow

Antes de llamar a (bar) se guarda stack-frame, pero al retornar al call= er se popea el frame.

Ultimo ejemplo para captar

(define (my-length lst) (cond [(empty? lst) 0] [else (+ 1 (my-length (rest lst)))]))
No estamos usando tail-call optimization, porque el llamado= esta en una suma.

Tiene que estar en posicion de retorno

Usamos nuestro patr=C3=B3n:

(define my-length-iter (lambda (lst) (my-le= ngth-iter-acc lst 0))) (define my-length-iter-acc (lambda (lst n) (cond [(empty? lst) n] [else (my-length-iter-acc (rest lst)= (add1 n))])))
Recursion simple a tai= l-call

Recursion simple: Lineal, caso base + caso inductivo

Pasos directos:

Fun original =3D> Fun Aux

Agreguen parametro acomuloador a fun aux.

Cambien llamado recursivo para que sea tail call.

Hgan un wrapper para el usuario poniendo los parametros iniciales.
Diferencia entre Tail-call optimization y Tail-recursion optimization=

Tail Recursion: Es un caso especifico donde la funcion que llamo es la m= isma funcion.

Scheme tiene muchas optimizaciones. Tail Call =3D> Tail Recursion. Scheme optimiza tail call asi que recursion ambien. Adem=C3=A1s optimiza pa= r q no haya stack overflow en ningun caso.

Taxonomia de interpretado= res (Clase 15)

Interprete sin recursion y eager

Ambientes

Ambiente actual:

#;(deftype Env (mtEnv) (anEnv id val env))
Que hace?

Mapea id a valor.

Ambientes como funciones

Para cada id queremos un solo valor, asi que la funcion es parcial.

Fun. Parcial:

Una funcion f: X -> Y es parcial si f: X' -> Y es funcion, donde X= ' subconjunto de X ; o sea, f no mapea cada elemento de X a un elemento Y, solo a un subconjun= to de X

Podemos usar funciones de racket para implementar ambientes:

Que reciban una id y retornen un valor.

(def<= /span> empty-<= /span>env (=CE=BB (s) (error "identificador libre!! ~a"= s)))
(define (extend-env s v env) (=CE=BB (id) (if (symbol=3D? id s) v (lookup-env id env)))) ;; de es= ta forma encadenamos las funciones para guardar el ;; ambiente completo
Lookup-env se simplifica
(define (lookup-env x env) (env x))
Podemos ejecutar los mismos programas. ### Interp

(define (interp expr env) (match expr ;... [(app fun-expr arg-expr) (def= fun-val (interp fun= -expr env)) ;;;; aqui hice el cambio para usar extend-env en vez de anEnv ; version original #; (interp (closureV-body fun-val) (anEnv (closureV-param fun-val) (interp arg-expr env) (closureV-env fun-val))) ; version actual (interp (closureV-body fun-val) (extend-env (closureV-param fun-val) (interp arg-expr env) (closureV-env fun-val)))=20 ] ;... ))
Numeros

Representamos lo snumeros de nuestro lenguaje en forma directa como nume= ros de Racket.

Si quisieramos que lo senteros tuvieran un comportamiento distinto (Por = ejemplo, overflow, etc) tenemos que hacer un una implementaci=C3=B3n especi= al de los numeros.

Funciones

Ahora:

(fun id body)
Implementaci= on con Funciones de racket

Actualizar la forma de definir valores:

(deftype Val (numV n) ; antes guardabamos en forma explicita el parametro, cuerpo y ambien= te de la funcion ; (closureV param body env) ; ahora solo guardaremos un valor, una funcio= n de Racket (= incluye su parametro y ambiente) (closureV p) )

Modificar =C3=ACnterp. fun y app

;; interp :: Expr Env -> Val (define (interp expr env) (match expr ;... [(fun id body) (closureV (=CE=BB (ar= g-val) (interp body (extend-env id arg-val env))))] [(app fun-expr arg-expr) ((closureV-p (interp fun-expr env)) (interp arg-expr env)) ]

Listo.

Consideraciones

Como racket tiene scope estatico, nuestro lenguaje lo hereda.

Taxonom=C3=ADa de funciones

Podemos impementar caracteristicas de nuestro interpreta de distintas fo= rmas.

Def: (Interpretador Sintactico)
Un interpretador sintactico es uno que solo usa el lenguaje en que esta = escrito el interprete para guardar los terminos m=C3=A1s basicos del lengua= je interpretado de forma explicita.

Def: (Meta-Interpretador)

Un interpete que usa las caracteristicas del lenguaje en que es= t=C3=A1 escrito el interprete para implementar el comportamiento = del lenguaje interpretado.

Que es nuestro interp?

Los iniciales eran casi sintacticos, hicimos las funciones, pero dependi= mos de racket para los numeros y el parseo de s-expr.

En cambio el que acabamos de hacer usando funciones de racket es un meta= -interp.

Que significa esto?

Si hay correspondencia entre las caracterisitcas del lenguaje a interpre= tar y el que usamos para escribirlo, es facil escribir un meta-interpretado= r.

Usando funciones de racjet heredamos el eagerness de Racket. Para implem= entar lazyness ser=C3=ADa dificil.

En el caso sintactico, debemos implementar cada feature del lenguaje (Di= ficil), pero no tenemos preocupasion en cuanto a lo que comparten los lengu= ajes.

Def: (Interpretador Meta-Circul= ar)

Si el lenguaje a interpretar es el mismo que uso para escribir el interp= rete y son similares en semantica.

Utilidad

Analizar un mismo lenguaje para ver si esta correcto.

"Si tu lenguaje se traga tu mismo le= nguaje, est=C3=A1 bacan..." S=C3=B3crates
Transformando nuestr= o lenguaje

Podemos utilizar directamente las funciones de racket y numeros (Sin env= olverlos en un Val).

Nos deshacemos de numV y closureV Usaremos lambdas directamente y numeros de racket.

Actualizar interprete:

;; interp :: Expr Env -> Val (define (interp expr env) (match expr ; ahora podemos hacer +, -, * en forma directa [(add l r) (+ (interp l env) (interp r env))] [(sub l r) (- (= interp l env) (interp= r env<= /span>))] [(mult l r) (* (inte= rp l en= v) (interp r env))] [(if0 c t f) ; cambiamos zero-num? por zero? ;(if (zero-num? (interp c env)) (if (zero? (interp c env)) (interp t env) (interp f env))] ;... [(fun id body) (=CE=BB (arg-val) (interp body (extend-env id arg-val env)))] [(app fun-expr arg-expr) ((interp fun-expr env) (interp arg-expr env)) ;; aplicar la lambda ] ))

Estados y Mutacion (Clase 16 y= 17)

Def: (Mutacion)

Capacidad de cambiar el valor asociado a un nombre.

Ej:

Cajas

Variables

Que ganamos

Codificar la noci=C3=B3n de estado.

Para interactuar con el mundo real necesitamos estados:

Efectuar un deposito en una cuenta correinte: Saldo =3D Saldo + M= ontoDeposito

Modelar una entidad del mundo real que cambia en el tiempo.

No hay que abusar

Es mala idea usar mutaci=C3=B3n para contadores o otras esgtructuras que= puedan accederse concurrentemente.

Que perdemos

Interpretabilidad de nuestros programas.

Incluir el estado en forma explicita hace dificil deducir cosas acerca d= e nuestros programas.

Por que la respuesta depende del estado de la mutaci=C3=B3n en el tiempo= de ejecuci=C3=B3n.

Implementando mutaci= =C3=B3n en nuestro lenguaje

Queremos:

with {= a {newbo= x 9}} {seq {wi= th {b 3} b} b}

Nuevas operaciones:

newbox --> box (creacion de una caja nueva)

setbox --> set-box! (cambiar el valor de una caja)

openbox --> unbox (obtener el valor actualmente en la caja)

seqn --> begin (ejecutar 2 expresiones en orden, retornando el valo= r de la ultima expresion)

Consideraciones y Implementacio= n

Nuevo tipo de valor:

; tipo de valor para representar las cajas #;(deftype Val (numV n) (closureV param body env) (boxV loc))

Podemos implementarlo usando las de scheme pero es muy trivial.

Hay que entender que dos cajas que contienen lo mismo son cajas dist= intas.

Y que las modificaciones a su contenido se ven de manera dinamica, e= s decir, en tiempo de ejecuci=C3=B3n.

No se pueden implementar a partir del enviroment porque se rompe el = scope estatico.

Tenemos que traspasar los cambios de los valores mutables de manera = secuencial en la ejecuci=C3=B3n de las instrucciones.

Ambiente y Store

Dos repositorios de informaci=C3=B3n.

Ambiente: Encargado de mantener el scope estatico. Se traspasa en la= interpretacion explicitamente para conseguir este efecto.

Store: Regstro de cambios dinamicos. Se traspasa en el orden de ejec= ucion de las intstrucciones.

Cambios

Proceso de dos pasos:

Usar el ambiente para mapear una id a algo
Usar algo para mapear a un valor.

Este algo es un indice, que respresenta un lugar en memoria (loc).

Cambiar env:

(deftype Env (mtEnv) (anEnv id loc env)) (deftype Sto (mtSto) (aSto loc val sto))

Cambiar lookup del ambiente:

(define (lookup-env x env) (match env [(mtEnv) (error "identificador libre!!" x)] [#;(anEnv id val restoEnv) (anEnv id loc restoEnv) (if (symbol=3D? id x) ;val loc (lookup-env x restoEnv))])) ; e implementar una funcion que toma loc y busca en el Store #;(define (lookup-sto l sto) (match sto [(mtSto) (error "no hay valor en ubicacio= n: ~a" l)] [(aSto loc val restoSto) (if (=3D loc l) ; usaremos enteros para representar posiciones en memoria val (lookup-sto l restoSto))]))

Nueva estructura:

Como se necesita propagar cambios dinamicamente necesitamos un wrapper = para lo que retorne el interprete.
(deftype Value*Store (v*s val sto))

Cambiar interp:

Se deben componer ambos lookup para pasar de id a valor.

Ahora recibe el store como parametro.

Debe retornar el store modificado en la interpretacion.

Adecuar todas las llamadas y cases para este nuevo tipo de retorno.<= /p>

Traspasar el store explicitamente a instrucciones sucesivas.

;; interp :: Expr Env Sto -> Val= ue*Store ;... [(id s) (lookup-sto (lookup-env s env) sto)]

Relacion Box con store

{with {switch {newbox 0}}
En el store se guarda el valor 0 en algun luga= r (Ej. loc=3D100). Se construye una caja que apunta a este valor.

env =3D ['switch -> 101] sto =3D [10= 1 -> (boxV 100),=20 100 -> (numV 0)]
Al definir una funci=C3=B3n que cambia el valor de la caja = por 1. Recordemos que el ambiente que guarda es el de la definici=C3=B3n, pero el = store se pasa en tiempo de ejecuci=C3=B3n.

sto =3D [= 102 -> (closureV ...) 101 -> (boxV 100),=20 100 -> (numV 1)] ; cambio aqui
Este store es el que retorna el interp, al aplicar la funci= =C3=B3n y cambiar el valor. Este store actualizado se utiliza en las siguientes instrucciones.

Una aplicaci=C3=B3n sucesiva de la misma funci=C3=B3n actuar=C3=A1 sobre= el mismo ambiente (el de la clausura), pero sobre el store actualizado.
Obtener direccioens de memoria
; la funcion next-location e= s una recursion simple sobre store, agregando 1= por cada ; valor guardado en el store (define (next-location sto) (match sto [(mtSto) 0] [(aSto _ _ rest) (add1 (next-location re= st))]))
Nuevo interp

Sorry por el Wall of text pero cambi=C3=B3 todo:

;; interp :: Expr Env Sto -&g= t; Val*Sto (define (interp expr env sto)=20 (match expr ; num, id y fun no afectan el store, asi que aqui solo nos preocupamos = de ; devolver el valor que actualmente entrega, en conjunto con el sto [(num n) (v*s (numV n) sto)] ; en el caso de id, tenemos que agregar el lookup en el sto ; y crear el par v*s [(id s) (v*s (lookup-sto (lookup-env s env) sto) sto)] [(fun id body) (v*s (closureV id body env) sto)] ; sigamos con el if0 .. primero tenemos que interpretar la condicion del if0 ; el valor lo usaremos para ver que branch interpretamos .. pero tambie= n tenemos ; que preocuparnos de propagar el sto resultante, sino volvemos al prob= lema de ; la clase pasada, donde las definciones que ocurrian en la condicion n= o se ; propagaban a los branches [(if0 c t f) ; recuerden que def de #lang play permite hacer pattern matching (def= (v*s c-val c-sto) (interp c env = sto)) (if (zero-num? c-val) (interp t env c-sto) (interp f env c-sto))] ; en el caso de la suma, tenemos que preocuparnos de lo mismo .. ; {+ expr1 expr2} ; expr1 puede modificar el store, asi que tenemos que interpretar expr1= , ; usando el store que entrega esta operacion para interpretar expr2 ; ; ojo que esto significa que importa el orden en que interpretemos las = expresiones ; {with {b {newbox 4}} ; {+ {openbox b} ; {with {dummy {setbox b 5}} ; {openbox b}}}} ; de izq a der =3D {+ 4 5} .. de der a izq =3D {+ 5 5} ; nosotros seguiremos el orden izq a der en nuestro interprete [(add l r) (def= (v*s l-val l-sto) (interp l env = sto)) (def= (v*s r-val r-sto) (interp r env = l-sto)) (v*s (sumar-num l-val r-val) r-sto)] ; la resta y multiplicacion se implementan de la misma forma [(sub l r) (def= (v*s l-val l-sto) (interp l env = sto)) (def= (v*s r-val r-sto) (interp r env = l-sto)) (v*s (restar-num l-val r-val) r-sto)] [(mult l r) (def= (v*s l-val l-sto) (interp l env = sto)) (def= (v*s r-val r-sto) (interp r env = l-sto)) (v*s (mult-num l-val r-val) r-sto)] [(app fun-expr arg-expr) ; primero interpretar fun-expr, que puede actualizar el store (def= (v*s (closureV id body fenv) fun-sto) (interp fun-expr env sto)) ; despues interpretar arg-expr, que tambien puede actualizar el store (def= (v*s arg-val arg-sto) (interp ar= g-expr env fun-sto)) ; tenemos que pedir un nuevo indice en el store, para guardar el ; el valor del argumento (def= new-loc (next-location arg-sto)) ; y finalmente interpretamos el cuerpo de la funcion, extendiendo ; el ambiente y el store para que el valor del argumento quede disponi= ble (interp body (extend-env id new-loc fenv) (extend-sto new-loc arg-val arg-sto))] ;; ahora hay que interpretar las estructuras nuevas [(seqn expr1 expr2) (def= (v*s val1 sto1) (interp expr1 en= v sto)) (interp expr2 env sto1)] [(newbox val-expr) ; interpretar val-expr (def= (v*s val-val val-sto) (interp va= l-expr env sto)) ; pedir un nuevo indice en val-sto .. (def= new-loc (next-location val-sto)) ; retornamos como valor una caja que apunta al nuevo indice ; y extendemos el store, asignando val-val a este indice en el store (v*s (boxV new-loc) (extend-sto new-loc val-val val-sto)) ] [(openbox box-expr) ; aqui interpretamos box-expr, lo que deberia entregar (boxV loc) (def= (v*s (boxV loc) box-sto) (interp= box-expr env sto)) ; y buscamos el valor asociado a loc en el store (v*s (lookup-sto loc box-sto) box-sto) ] [(setbox box-expr val-expr) ; primero interpretamos box-expr para encontrar el indice del valor a = cambiar (def= (v*s (boxV loc) box-sto) (interp= box-expr env sto)) ; ahora interpretamos val-expr (def= (v*s val-val val-sto) (interp va= l-expr env box-sto)) ; retornamos el valor que vamos a guardar en la caja (dado que el ; interprete tiene que retornar algo), y extendemos el store, asociand= o el ; valor nuevo al indice en memoria al que apunta la caja (v*s val-val (extend-sto loc val-val val-sto))] ))
Flujo de repositorios

El ambiente y store tienen comportamientos distintos durante interpretac= ion.

El store entra y sale de la interp. de sub.expresiones, tiene un flujo d= el tipo "threading" dado que pasa como una aguja que entra y sale por una t= ela.

Esto muestra la diferencia entre nombres y valores. Los valores en el st= ore persisten mucho mas que los nombres. El valor de un calculo puede ser a= signado a otro nombre.

Los nombres tienen scope estatico o lexico, los valores pueden estar dis= ponibles m=C3=A1s alla de su definici=C3=B3n.

Variables (Clase 18)

o.f =3D e

Significa que hay que evaluar la expresion o, lo que deberia entrega= r un objeto

o es una expresion arbitraria ... por ejemplo, podria ser ; buscar un objeto en un ArrayList, y que al evaluarla retorna un objeto<= /p>

Tambien hay que evaluar la expresion e, lo que produce un valor

Finalmente, hay que cambiar el contenido del atributo f de o para qu= e tenga el valor e

void m (int i){i =3D 4};

Cambiar el valor de un identificador.

i es una id, no es una expresion cualquiera que evalua al nombre de una= id.

Es decir, al hacer i =3D 4 no estamos modificando el valor contenido en un contenedor, estamos cambian= do el valor del indetificador.

Al grano: Variables

Tipo de programas que quiero escribir

{with {x 2} {seqn {set x 100} x}} ; deberia entregar el valor 100
Nueva regla AST

{set <id> <s-expr&= gt;} <--- recibe un <id>, no un <s-expr> (set id val-expr)
Parser

[(list 'set id e) (set id (parse e= ))]
Interp

[(set id val-expr) ; primero tenemos que buscar la direccion donde guardamos id (def= loc (lookup-= env id env)) ; despues tenemos que evaluar val-expr (def= (v*s val-val val-sto) (interp va= l-expr env sto)) ; y por ultimo, tenemos que agregar el nuevo valor al store y retornar= lo (v*s val-val (extend-sto loc val-val val-sto)) ]
L-values

La unica parte donde hacemos lookup a medias es en el set porque buscamo= s la loc de la id para modificar su valor.

Este tipo de valores se conoce como L-values porque estan a la izquierda= de las asignaciones en muchos lenguajes. (Excepto R que puedes usar -> = o <- para asignar valores a ids)

Estos L-values corresponden a la ubicacion del identificador.

Ej:

x =3D 2 y =3D x
En la linea 1 no necesitamos saber el valor de x, solo su l= oc.=20 En la linea 2 necesitamos saber su valor para asignarlo a y.

Dicotom=C3=ADa

Que valor entrega este ejemplo

(run '{with {v 0} {with {f {fun {y} {set y 5}}} {seqn {f v} v}}})

0 si la mutacion afecta a y, el parametro formal de la = funcion y no v, el valor del argumento... [Esto es lo que tene= mos implementado en nuestro interprete]

5 si la mutacion afecta al argumento de la funcion.

Esto se ve en la implementacion de la regla de (app ...)
[(app fun-expr arg-expr) (def= (v*s (closureV id body fenv) fun-sto) (interp fun-expr env sto)) (def= (v*s arg-val arg-sto) (interp ar= g-expr env fun-sto)) (def= new-loc (next-location arg-sto)) (interp body ; aqui estamos guardando id en un nuevo lugar en el ambiente (extend-env id new-loc fenv) =20 (extend-sto new-loc arg-val arg-sto))]

env loc sto info

x 100 5 fuera

f 101 closure (Env fuera de fun llega hasta aqui)

x 102 5 (Parametro de la fun, env dentro de fun)

Como siempre guardamos el parametro de la funcion en una nueva ubicacion= en el ambiente, nunca afectaremos el valor del argumento de la funcion.
Este tipo de evaluacion se llama "call-by-value" (Se pa= sar argumentos por valor)

Call-by-reference

Otra opcion es pasar una referencia al argumento, no solo su valor.

Esto implica que los cambios que hagamos a esta referencia se reflejan f= uera de la funcion.

refun

Para implementar esto introduciremos un nuevo tipo de funcion (ref= un ...)

{refun {<= id>} <s-expr>} <--- para call-by-reference ;AST (refun id= body)
Necesitamos una nueva clausura para estas funciones:

(deftype Val ;... ; distinguir entre call-by-value y call-by-<= span class=3D"hljs-keyword">ref en el momento de aplicacion (refclosV param body env))
Interp:

[(app fun-expr arg-expr) ; seguimos interpretando primero la fun-expr ; pero ahora fun-val podria ser closureV o refclosV (def= (v*s fun-val fun-sto) (interp fu= n-expr env sto)) ; asi que hacemos un match ... (match fun-val [(closureV id body fenv) =20 ; en el caso de closureV, hacemos lo mismo que antes (def (v*s arg-val arg-sto) (interp = arg-expr env fun-sto)) (def new-= loc (next-location arg-sto)) (interp body (extend-env id new-loc fenv) (extend-sto new-loc arg-val arg-sto))] [(refclosV id body fenv) ; en el caso de call-by-ref ; arg-expr es de tipo (id name) asi que podemos usar la funcion (id= -name ..) ; para obtener el nombre del argumento ; y despues podemos hacer un lookup para encontrar la ubicacion de = su valor (def loc (look= up-env (id-name arg-expr) env)) (interp body ; y extendemos el ambiente, enlazando el nombre del paramet= ro a la ; ubicacion del argumento .. asi que ahora mutaciones al pa= rametro ; afectan el valor del argumento (extend-env id loc fenv) fun-sto)])]
Consideraciones y Co= nclusiones

Deber=C3=ADan los lenguajes permitir call-by-reference?

Hay que tener en cuentade que el parametro pasa a ser un alias del argu= mento, dado que cualquier cambio al parametro tambien ocurre al argumento.<= /li>

Esto es un problema si el programador no sabe que es call-by-reference.<= /p>

En lenguajes como C ofrece un operador especial y expl=C3=ADcito par= a obtener referencias a variables.

Puede llevar a errores dificiles de diagnosticar Esto no ocurre en lenguaje call-by-value dado que los cambion no agectan = al que invoca la funcion. Se prefiere esta opcion hoy.

Si necesitan cambiar un valor entonces se debe pasar un contenedor exp= licitamente.

Que tiene de bueno?

Eficiencia, no necesitamos espacio extra para guardar los valores de va= riables.

Podemos escribir funcion swap, clave para algoritmos de ordenamiento.

env loc sto info

x 100 5

f 101 closure (Env fuera de fun llega hasta aqui)

y 100 5 (Parametro de la fun, env dentro de fun)

Manejo de memoria (Clase 19)

Materia el libro del dragon de compiladores.

Hasta ahora cada vez que agrego algo al store se encola al store previo.= =20 Es decir, crece indefinidamente.

Cambiar el valor de una caja 100 veces agrega 100 veces los mismos valo= res al store.

Empleado e1 =3D new Empleado(...); Empleado e2 =3D new Empleado(...); // se puede borrar porque perdio referencia //... e2 =3D e1

=C2=BFPorque recoelctar basura?

Eficiencia

Quisieramos programar como si tuvieramos infinita memoria. Como no la tenemos (Cada proceso tiene acceso a una cantidad finita), debem= os recuperar lo que ya no estemos usando para evitar posibles problemas de = memoria.

Manual o Automatico?

Manual, nos arriesgamos a tener Memory Leak o Seg. Fault dependiendo si = no borro o si borro algo que iba a ocupar.

En C se hace asi. Las personas son inteligentes y son los que mejor pued= en indicar un valor no va a ser usado m=C3=A1s. Porque en realidad e sun pr= oblema *no-decidible determinar que es basura.

La forma automatica es mucho m=C3=A1s practica y le quita trabajo al pro= gramador.

Propiedades G-C

1) Que sea util: Tiene que identificar suficiente basura como para que l= a ejecucion del programa continue sin errores de memoria.

2) Que sea correcto: El recolector no deberia liberar un valor que sea u= sado en el futuro.

3) Que sea eficiente: No tenga un sobrecosto excesivo en la ejecucion de= l programa.

Como el proglema de decidir si un valro sera usado en futro es no-decidi= ble, tenemos que aproximar una solucion en forma conservadora.

Solucion tipica

En vez de identificar que es basura, identificar los objetos que son alc= anzables (reachable) desde un conjunto inicial de objetos. Este conjunto se= llama el "root set", incluye las referencias en el stack y variables globa= les. Si no existe un "camino" (una secuencia de referencias) desde algun ob= jeto del root set a un objeto x, significa que el objeto x no puede ser usa= do en un calculo futuro y podemos reciclar la memoria usada para guardarlo.=

Grafo de objetos

____ ____ | |---->| | |o1 | |o2 | objeto o1 hace referencia a o2, por ejemplo, a traves de = un atributo |___| |___|
Ejemplo:

____ = ____ __= __ | | = | |<----| | | | ____ ____ = | | |___| | |---->| |---->| | = | | ^ | | |___| |___| = | | __|_ | | ____ ____ = |___|---->| | = =20 | |---->| | r1 --->| |= ----------------| |___| | | |___| |___| = | =20 | | ^ = | | | __|_ ____ ____ = _V__ | |---->| | | |---= ->| |---->| |<--- r2 stack --->|___| |___| |___| |___| |__= _|
Algunas de estas referencias tienen nombre en nuestro progr= ama (stack, r1 y r2 .. nuestro root set en este ejemplo), otras son anonima= s (p.ej., creacion de objeto anonimo usando new).

Estrategia 1: Contar Referencias=

Llevar una cuenta de las referencias que apunten a un objeto.

Cuando vale 0 =3D> Obj. no es alcanzable.

Problema

No detecta ciclos

Implementacion

Introducir contador por cada objeto del programa.

Actualizar valor cada vez que referenciamos/desreferenciamos un objeti.=

Antes

x.f =3D p
Despues

// primero tenemos que actualizar e= l contador de lo que actualmente esta guardado en x.f, // dado que puede estar referenciado por otros= objetos z =3D x.f c =3D z.count c =3D c - 1 z.count =3D c // si ningun otro objeto hace referencia a el = objeto z, podemos marcarlo como basura if c =3D=3D 0 =3D> Liberar(Z)=20 // ahora hacemos la asignacion y aumentamos el= contador de referencias de p x.f =3D p c =3D p.count c =3D c + 1 p.count =3D c

8 Instrucciones nuevas =3D> ineficiente

Estrategia 2: Scan & Copy

Copiar objetos alcanzables desde la raiz.

Idea basica

Usar 2 heaps:

1) Del programa para guardar sus datos. 2) Del recolector de basura.

Usando el algoritmo de Cheny: 1) Recolector marca todos los valores del rootset como "vivos" 2) Recolector visita los valores a los que hacen referencia los del rootset= , marcandolos como "vivos" 3) Sigue haciendo esto hasta que no queden valores alcanzables desde el roo= tset. 4) Todos los valores vivos son copiados al segundo heap (Los objetos no al= canzables se quedan en el heap original). 5) Se intercambian los heap.

Ejemplo

Hay 5 objetos en memoria: 1, 2, 3, 4, 5. El objeto 1 hace referencia a d= os objetos: primero el objeto 4 y despues el objeto 2. El objeto 4 hace ref= erencia al objeto 5. Nadie hace referencia al objeto 3.

______________ = ______________ | | = | | |_____________| = | | |--> 5 |/_/_/_/_/_/_/| | | |--- 4 |_/_/_/_/_/_/_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | | | 2 |/_/_/_/_/_/_/|<--| | | | 1 | / / / / / / |---| | | | root --->|/_/_/_/_/_/_/|-------| = | | | | = | | |_____________| = |_____________|<------= next, scan heap original (HO) heap rec basura (HB) Usaremos las referencias next y scan (v= er el heap de recoleccion de basura) para llevar un registro de donde neces= itamos copiar el siguiente objeto (next= ) y cual es la siguiente referencia a seguir (scan).=20 Siguiendo la referencia root, vemos que tenemos que copiar el objeto 1 del HO al HB, actualizando la referencia next. ______________ = ______________ | | = | | |_____________| = | | |--> 5 |/_/_/_/_/_/_/| | | |--- 4 |_/_/_/_/_/_/_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | | | 2 |/_/_/_/_/_/_/|<--| | | | 1 |\ \ \ \ \ \ \|---|= | | | root --->|_\_\_\_\_\_\_|-------| |_____________|<------ next | | = 1 | / / / / / / |=20 |_____________| = |/_/_/_/_/_/_/|<------= scan heap original (HO) heap rec basura (HB) El objeto 1 en el HB apunta a dos objeto= s del HO: objeto 4 y objeto 2 (en ese orden).= Asi que ahora hay que copiar el objeto 4 a HB ... ______________ = ______________ | | = | | |_____________| = | | |--> 5 |/_/_/_/_/_/_/| | | |--- 4 |_\_\_\_\_\_\_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | | | 2 |/_/_/_/_/_/_/|<--| | | | 1 |\ \ \ \ \ \ \|---|= | |_____________|<------ next root --->|_\_\_\_\_\_\_|-------| 4 |/_/_/_/_/_/_/| | | = 1 | / / / / / / |<------ scan=20 |_____________| = |/_/_/_/_/_/_/| heap original (HO) heap rec basura (HB) El objeto 4 del HB apunta a el objeto 5 del HO. Vamos a seguir con este proceso = hasta que scan y next apuntan al mismo = lugar, lo que significa que no quedan objetos copiados por escanear, asi qu= e ya copiamos todo lo que se podia acceder desde root.=20 Ahora escaneamos la segunda referencia del objeto 1, por lo que tenemos que copiar el objeto 2 al HB. ______________ = ______________ | | = | | |_____________| = | | |--> 5 |/_/_/_/_/_/_/| | | |--- 4 |_\_\_\_\_\_\_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | | | 2 |\_\_\_\_\_\_\|<--| | |_____________|<------ next 1 |\ \ \ \ \ \ \|---|= | 2 |/_/_/_/_/_/_/| root --->|_\_\_\_\_\_\_|-------| 4 |/_/_/_/_/_/_/|<------ sca= n=20 | | = 1 | / / / / / / | |_____________| = |/_/_/_/_/_/_/| heap original (HO) heap rec basura (HB) Ahora escaneamos el objeto 4 del HB, est= e apunta al objeto 5 del HO, que lo copi= amos al HB. =20 ______________ = ______________ | | = | | |_____________| = | | |--> 5 |\_\_\_\_\_\_\| | | |--- 4 |_\_\_\_\_\_\_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | |_____________|<------ next 2 |\_\_\_\_\_\_\|<--| | 5 |/= _/_/_= /_/_<= /span>/_/| 1 |\ \ \ \ \ \ \|---|= | 2 |/_/_/_/_/_/_/|<------ scan=20 root --->|_\_\_\_\_\_\_|-------| 4 |/_/_/_/_/_/_/| | | = 1 | / / / / / / | |_____________| = |/_/_/_/_/_/_/| heap original (HO) heap rec basura (HB) Ahora escaneamos el objeto 2 del HB, per= o este no apunta a nadie, asi que solo avanzamos la referencia scan en el H= B.=20 ______________ = ______________ | | = | | |_____________| = | | |--> 5 |\_\_\_\_\_\_\| | | |--- 4 |_\_\_\_\_\_\_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | |_____________|<------ next 2 |\_\_\_\_\_\_\|<--| | 5 |/= _/_/_= /_/_<= /span>/_/|&l= t;------ scan=20 1 |\ \ \ \ \ \ \|---|= | 2 |/_/_/_/_/_/_/| root --->|_\_\_\_\_\_\_|-------| 4 |/_/_/_/_/_/_/| | | = 1 | / / / / / / | |_____________| = |/_/_/_/_/_/_/| heap original (HO) heap rec basura (HB) Pasa lo mismo al escanear el objeto 5 de= l HB, solo avanza la referencia scan.=20 ______________ = ______________ | | = | | |_____________| = | | |--> 5 |\_\_\_\_\_\_\| | | |--- 4 |_\_\_\_\_\_\_|<------| = | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | |_____________|<------ next, scan 2 |\_\_\_\_\_\_\|<--| | 5 |/= _/_/_= /_/_<= /span>/_/|&l= t;-------| 1 |\ \ \ \ \ \ \|---| | = |--> 2 |/_/_/_/_/_/_/= | | root --->|_\_\_\_\_\_\_|-------<= span class=3D"hljs-params">| | 4 |/_/_/_/_/_/_/|<--| ---| | | = |--- 1 | / / / / / / | | |_____________| = |/_/_/_/_/_/_/|---| heap original (HO) heap rec basura (HB) Lo ultimo es intercambiar los dos heaps. La referencia root ahora apunta al= HB, y next y scan apuntan al HO: ______________ ______________ | | = | | |_____________| | | |--> 5 |\_\_\_\_\_\_\| | | |--- 4 |_\_\_\_\_\_\= _|<------| | | | | | | | |_____________| | | | 3 |/_/_/_/_/_/_/| | = | | | | | | | | | | | | |_____________| | |_____________| 2 |\_\_\_\_\_\_\|<--| | = 5 |/_/_/_/_/_/_/|<-------| 1 |\ \ \ \ \ \ \|---|= | |--> 2 |/_/_/_/_/_/_/| = | |_\_\_\_\_\_\_|-------| | 4 |/_/_/_/_/_/_= /|<--| ---| | | = |--- 1 | / / / / / / | | next, scan -->|_____________| = root --->|/_/_/_/_/_/_/|---| heap rec basura (HB) heap original (HO) El objeto 3, que no era accesible desde = el root original, no fue copiado al heap nuevo .. y sera sobreescrito la si= guiente vez que se invoque el recolector de basura.
Ventajas:

Simple de implementar

No detecta ciclos

El tiempo de ejecucion es proporcional al numero de objetos vivos.

Se va compactando memoria.

Problemas:

Se necesita memoria extra (Peor caso: 2x)

Es lento escanear, puede interrumpir la ejecucion.

Estrategia 3: Generaciones

Observaciones empiricas

Si un objeto ha sido alcanzable una buena cantidad de tiempo, probablem= ente siga asi.

En la mayoria de los lenguajes, los objetos mueren jovenes.

Rara vez objetos viejos apuntan a objetos nuevos. Cuando se modifica un= objeto viejo, pasa a ser joven.

Idea fundamental

Podemos ahorrar trabajo:

Escaneando objetos jovenes frecuentemente.

Escaneando objetos viejos infrecuentemente.

Estrategia asigna Generaciones a los objetos: G0,= G1, ... (Usualmente se usan 2 gen)

G0: Contiene objetos jovenes, probablemente basura

G1: Objetos m=C3=A1s viejos.

Promovemos un objeto de G0 a G1 si sobrevive a un proceso de recoleccion= de basura.

Revisamos G0 m=C3=A1s seguido que G1. Revisamos G1 luego de hacer varias recolecciones de G0.

Suerte!

Sintesis hecha por Vicente Oyanedel Material tomado de:

C=C3=A1tedras y material de Profesora Jocelyn Simmonds

Libro: Plai - Shriram Krishnamurthi

Diciembre - 2016
------MultipartBoundary--DK8yaVFtLdnZe1Dhj6yUqZWzpPzQpfmT2Uj6tLZ1lQ---- Content-Type: text/css Content-Transfer-Encoding: quoted-printable Content-Location: chrome-extension://febilkbfcbhebfnokafefeacimjdckgl/theme/ClearnessDark.css @charset "utf-8"; h1, h2, h3, h4, h5, h6, p, blockquote { margin: 0px; padding: 0px; } body { font-family: "Helvetica Neue", Helvetica, "Hiragino Sans GB", Arial,= sans-serif; font-size: 13px; line-height: 18px; color: rgb(255, 255, 255);= margin: 10px 13px; background-color: rgb(40, 42, 54); } a { color: rgb(89, 172, 243); } a:hover { color: rgb(167, 216, 255); text-decoration: none; } a img { border: none; } p { margin-bottom: 9px; } h1, h2, h3, h4, h5, h6 { color: rgb(255, 255, 255); line-height: 36px; } h1 { margin-bottom: 18px; font-size: 30px; } h2 { font-size: 24px; } h3 { font-size: 18px; } h4 { font-size: 16px; } h5 { font-size: 14px; } h6 { font-size: 13px; } hr { margin: 0px 0px 19px; border-width: 0px 0px 1px; border-bottom-style: = solid; border-bottom-color: rgb(204, 204, 204); } blockquote { padding: 13px 13px 21px 15px; margin-bottom: 18px; font-family= : georgia, serif; font-style: italic; } blockquote::before { content: "=E2=80=9C"; font-size: 40px; margin-left: -1= 0px; font-family: georgia, serif; color: rgb(238, 238, 238); } blockquote p { font-size: 14px; font-weight: 300; line-height: 18px; margin= -bottom: 0px; font-style: italic; } code, pre { font-family: Monaco, "Andale Mono", "Courier New", monospace; } code { color: rgb(255, 74, 20); padding: 1px 3px; font-size: 12px; border-r= adius: 3px; } pre { display: block; padding: 14px; margin: 0px 0px 18px; line-height: 16p= x; font-size: 11px; border: 1px solid rgb(191, 55, 15); white-space: pre-wr= ap; word-wrap: break-word; } pre code { color: rgb(255, 74, 20); font-size: 11px; padding: 0px; backgrou= nd-color: rgb(40, 42, 54); } @media screen and (min-width: 768px) {=20 body { width: 748px; margin: 10px auto; } } .hljs { display: block; overflow-x: auto; padding: 0.5em; background: rgb(4= 0, 43, 46); } .hljs-keyword, .hljs-selector-tag, .hljs-literal, .hljs-selector-id { color= : rgb(147, 199, 99); } .hljs-number { color: rgb(255, 205, 34); } .hljs { color: rgb(224, 226, 228); } .hljs-attribute { color: rgb(102, 139, 176); } .hljs-code, .hljs-class .hljs-title, .hljs-section { color: white; } .hljs-regexp, .hljs-link { color: rgb(211, 151, 69); } .hljs-meta { color: rgb(85, 113, 130); } .hljs-tag, .hljs-name, .hljs-bullet, .hljs-subst, .hljs-emphasis, .hljs-typ= e, .hljs-built_in, .hljs-selector-attr, .hljs-selector-pseudo, .hljs-additi= on, .hljs-variable, .hljs-template-tag, .hljs-template-variable { color: rg= b(140, 187, 173); } .hljs-string, .hljs-symbol { color: rgb(236, 118, 0); } .hljs-comment, .hljs-quote, .hljs-deletion { color: rgb(129, 142, 150); } .hljs-selector-class { color: rgb(160, 130, 189); } .hljs-keyword, .hljs-selector-tag, .hljs-literal, .hljs-doctag, .hljs-title= , .hljs-section, .hljs-type, .hljs-name, .hljs-strong { font-weight: bold; } ------MultipartBoundary--DK8yaVFtLdnZe1Dhj6yUqZWzpPzQpfmT2Uj6tLZ1lQ------

env	loc	sto	info
x	100	5	fuera
f	101	closure	(Env fuera de fun llega hasta aqui)
x	102	5	(Parametro de la fun, env dentro de fun)

Eager vs Lazy (Clase 11 y 12)

Eager

Lazy

Ejemplos Lazy

Implementar Lazyness

Call-by-name

Nuevo tipo de valor: Expre= sion Closure

Funcion que reduzca= exprV a Val

Problema

Call-by-Need

Consecuencias de introducir= mutaci=C3=B3n

Implementaci=C3=B3n

Fun strict debe ponerse en el caso que la caja sea #f o hay a= lgo:

Al aplicar una fun los argumentos deben setearse con la caja= en #f

Consideraciones

Memoization

Resumen reg=C3=ADmenes de evalua= ci=C3=B3n

Problema

Luego se bindea 'fac a esta= clausura.

Soluci=C3=B3n

Implementaci=C3=B3n

Nuestro ejemplo

Tail-call optimization (Clase 1= 4)

Activation Stack:

Clasificaciones de llamados

Ejemplos

Factorial Recursivo

Patron para convertir a Reducc= i=C3=B3n

Idea fundamental:

Ejemplo con factorial:

Comportamiento de control

Lema:

Tail-call Optimization:

Ejemplo

Ultimo ejemplo para captar

Usamos nuestro patr=C3=B3n:

Recursion simple a tai= l-call

Diferencia entre Tail-call optimization y Tail-recursion optimization=

Taxonomia de interpretado= res (Clase 15)

Ambientes

Que hace?

Ambientes como funciones

Fun. Parcial:

Numeros

Funciones

Implementaci= on con Funciones de racket

Consideraciones

Taxonom=C3=ADa de funciones

Def: (Interpretador Sintactico) Un interpretador sintactico es uno que solo usa el lenguaje en que esta = escrito el interprete para guardar los terminos m=C3=A1s basicos del lengua= je interpretado de forma explicita.

Def: (Meta-Interpretador)

Que es nuestro interp?

Que significa esto?

Def: (Interpretador Meta-Circul= ar)

Utilidad

Transformando nuestr= o lenguaje

Estados y Mutacion (Clase 16 y= 17)

Def: (Mutacion)

Que ganamos

No hay que abusar

Que perdemos

Implementando mutaci= =C3=B3n en nuestro lenguaje

Nuevas operaciones:

Consideraciones y Implementacio= n

Ambiente y Store

Cambios

Relacion Box con store

Obtener direccioens de memoria ; la funcion next-location e= s una recursion simple sobre store, agregando 1= por cada ; valor guardado en el store (define (next-location sto) (match sto [(mtSto) 0] [(aSto _ _ rest) (add1 (next-location re= st))]))

Nuevo interp

Flujo de repositorios

Variables (Clase 18)

o.f =3D e

void m (int i){i =3D 4};

Al grano: Variables

Nueva regla AST

Parser

Interp

L-values

Dicotom=C3=ADa

Call-by-reference

refun

Fun `strict` debe ponerse en el caso que la caja sea #f o hay a= lgo:

Def: (Interpretador Sintactico)
Un interpretador sintactico es uno que solo usa el lenguaje en que esta = escrito el interprete para guardar los terminos m=C3=A1s basicos del lengua= je interpretado de forma explicita.

Obtener direccioens de memoria
`; la funcion next-location e= s una recursion simple sobre store, agregando 1= por cada ; valor guardado en el store (define (next-location sto) (match sto [(mtSto) 0] [(aSto _ _ rest) (add1 (next-location re= st))]))`