Ejercicios · FLP · Asignación y paso por referencia¶
Asignación y paso por referencia (EOPL §4.1 a §4.5). Cada enlace abre una actividad que se trabaja directo en el navegador, sin instalar nada. Las secciones siguen las de la sesión y en su mismo orden.
Los programas están escritos como los reciben los intérpretes del curso:
let m = 0 in begin set m = add1(m); m end. Las primitivas van antes del
paréntesis y con comas, la aplicación lleva paréntesis y va sin comas,
(f z 2), y set y setref devuelven 1. Hay tres intérpretes, los de
Corte 2 en la versión de la tercera edición del libro: 0
ReferenciasExplicitas, 1 Asignacion y 2 PasoPorReferencia. Los tres
tienen el mismo ambiente inicial, x = 4, y = 2, z = 5 sobre a = 4,
b = 5, c = 6; en los dos últimos esas seis variables ocupan las celdas 0
a 5 del almacén. Cada actividad dice con cuál corre. Los programas no son los
de clase: mismo lenguaje, ronda nueva. Lo que aquí se afirma sobre valores,
celdas y ambientes se midió corriéndolo contra los intérpretes en Racket,
celda por celda.
Casi todas las actividades dibujan: al comprobar, la página muestra la cadena de ambientes con el almacén debajo y una flecha de cada referencia a su celda.
Valor y efecto¶
Valor y efecto¶
Lo que cambia cuando una expresión, además de dar un valor, escribe una celda
(EOPL §4.1). El primer bloque separa ligadura de asignación:
let w = 7 in +(let w = add1(w) in w, w) vale 15, y con set la misma suma
vale 16. El segundo pregunta cuándo una subexpresión se puede cambiar por su
valor; el caso que más cuesta es un procedimiento que no asigna nada y aun así
devuelve 1 y luego 5, porque lee una celda que otro escribe. Después se mide
el orden de evaluación y se pesa el precio del aliasing.
El orden de evaluación¶
Siete programas donde el resultado depende de un orden concreto: los
operandos de una primitiva de izquierda a derecha, las ligaduras de un let
antes de crear el eslabón, los operandos de una aplicación antes que el
operador. Uno se salva de detenerse solo por ese orden: f empieza ligado a 5
y el operando le asigna un procedimiento antes de que se verifique.
El almacén¶
El almacén¶
Cuatro bloques sobre la lista de celdas de EOPL §4.2: qué le hace cada
operación al almacén, qué queda después de una secuencia de newref y
setref!, qué se puede afirmar de una referencia y por qué el almacén está
hecho con un set! sobre una variable global. Una celda puede guardar una
referencia a otra, y dos (newref 5) dan dos celdas distintas.
El almacén en código¶
Aquí se escribe código. Cinco retos que levantan src/almacen.rkt: la lista
igual salvo en una posición, newref sobre el almacén global, deref con su
verificación, el almacén numerado que se mira desde el REPL, e
intercambiar! sobre la interfaz. El más exigente pasa la misma referencia
dos veces.
Referencias explícitas¶
Referencias explícitas¶
Ocho programas del lenguaje de EOPL §4.2, donde el programa reserva, lee y
escribe celdas a mano. let b = a copia una referencia y no una celda; un
procedimiento que recibe una referencia por valor escribe en la celda del
llamador; tres newref que nadie liga dejan tres celdas que ya no se pueden
leer; y setref sobre un número se detiene.
Dibujar la cadena con referencias explícitas¶
Al revés que las anteriores: en vez de leer la cadena hay que construirla. En
este lenguaje el ambiente guarda valores, y algunos son referencias: una
referencia que lleva a otra, el eslabón de una llamada que comparte celda con
el de afuera, un letrec que escribe una celda que vive afuera.
Referencias implícitas: set¶
Las producciones de set y begin¶
Las producciones de set y begin (EOPL §4.3) en los dos sentidos: qué
programas genera la gramática, cómo se reparte un programa en los campos de
begin-exp, qué habría que cambiar para admitir un set sobre (f 1) y la
diferencia entre valor expresado y denotado. begin set x = set y = 7; +(x, y)
end se parsea y vale 8.
Clausuras que comparten estado¶
Una clausura captura el ambiente donde se creó, y ese ambiente guarda
referencias. Cuatro programas se predicen con la regla del intérprete y con
una que copiara los valores al crearse la clausura, y se abren las dos trazas
con su almacén: cobrar da 60 con celdas compartidas y 30 con la copia. Las
dos últimas tarjetas son dos contadores que solo se diferencian en dónde está
el let c = 0: uno vale 5 y el otro 9.
Las cláusulas de la asignación¶
Las cláusulas de 1 Asignacion, línea por línea: qué devuelve apply-env y
por qué set la necesita así, cuántas celdas reserva cada programa y qué
pasaría si una cláusula se escribiera de otra forma. Sin el (map newref …)
del let, el datatype rechaza el eslabón.
Dibujar la cadena con celdas¶
Cuatro programas para escribir la cadena de un momento, ahora con
referencias: cada ligadura se escribe (a-ref 6) y lo que hay en la celda se
ve en el almacén. En uno la celda de una llamada anterior sigue en el
almacén aunque su eslabón ya no esté en la cadena; en otro el marco del
letrec deja una clausura en cada celda impar.
Trazas completas con asignación¶
Cinco programas para trazar completos, con el valor y los conteos: un
acumulador que la recursión actualiza desde afuera, un parámetro que se
asigna sin que la variable de afuera se entere, tres llamadas que escriben la
misma celda, un procedimiento recursivo al que un set no alcanza a cambiar,
y un programa que no crea ningún ambiente y aun así cambia dos celdas.
letrec con referencias¶
Buscar un nombre de letrec reserva una celda con una clausura recién hecha.
Siete programas para contar celdas y clausuras: un letrec que nadie nombra
no reserva nada, una recursión de tres llamadas reserva seis celdas, y
set g = 5 sobre el nombre del letrec escribe en una celda que nadie
vuelve a leer.
El ambiente que liga nombres a referencias¶
Aquí se escribe código. Cinco retos sobre src/ambiente.rkt: reservar una
celda por valor, apply-env que devuelve la referencia, leer y asignar una
variable, el marco de letrec que reserva una celda en cada búsqueda y el
ambiente inicial que se construye de nuevo en cada programa. Las pruebas
distinguen capturar el marco de capturar lo que el marco extiende.
Cierre: un intérprete con almacén¶
También con código: un intérprete pequeño con almacén y las cláusulas de
var-exp, let-exp, set-exp y begin-exp, y una forma nueva, incr x,
con su variante y su cláusula. Dos incr en una suma dan 1 + 2.
Paso por valor y paso por referencia¶
Las dos políticas¶
El mismo programa con paso por valor y con paso por referencia (EOPL §4.5),
con las dos trazas y los dos almacenes dibujados. rotar da 123 por valor y
231 por referencia; +(m, 0) vale lo mismo que m y aun así no comparte su
celda; y un procedimiento pasado por referencia termina convertido en un 0.
Alias¶
Seis programas sobre 2 PasoPorReferencia (EOPL §4.5.1): dos parámetros que
son alias de la misma variable, un alias que pasa por dos llamadas y deja
101101, una variable del ambiente inicial que dos llamadas llevan de 4 a 12, y
un nombre de letrec que no se deja cambiar.
Dibujar la cadena con paso por referencia¶
Cuatro programas para escribir la cadena dentro de un procedimiento. Un parámetro cuyo operando fue una variable guarda la misma referencia que ella, aunque el eslabón de la variable no esté en la cadena: el almacén dibujado lo muestra con dos flechas que llegan a la misma celda.
El paso por referencia en código¶
Tres retos sobre un intérprete pequeño: evaluar-operando, la aplicación que
liga los parámetros a esas referencias y alias?, que dice si dos nombres
denotan la misma celda comparando posiciones y no contenidos.