Saltar a contenido

Ejercicios · FLP · Tad y ambientes

Estrategias para representar datos: TAD y ambientes. Cada enlace abre una actividad que se trabaja directo en el navegador, sin instalar nada. Los ejemplos no son los de la sesión: mismo tema, ronda nueva.

Van en el orden en que la sesión ve los temas, dos por tema: una de analizar y una de escribir código. En las de analizar cada respuesta muestra su razón, se acierte o no; en las de código, las pruebas dicen qué pasó y los tropiezos frecuentes traen su explicación.

El cliente conoce la representación

¿Sobrevive el cliente?

Quince fragmentos de código que usan un TAD, el natural y el ambiente, y una sola pregunta por fragmento: si la representación cambia, ¿sigue funcionando? La respuesta no depende de qué hace el cliente sino de por dónde toca el dato. Hay uno que pasa con las tres representaciones de la sesión y aun así se rompe, porque apuesta a una propiedad que la especificación nunca prometió.

Arreglar el cliente

Cuatro clientes que metían la mano en la representación —es-uno? comparaba contra (#t), doble multiplicaba, mayor? medía longitudes—, para reescribirlos con la interfaz. La representación del esqueleto es la anidada, que ninguno de los cuatro suponía: la versión vieja no pasa las pruebas y la nueva sí. Al cierre, natural->numero, que es cómo un cliente cuenta sin mirar.

Abstracción de datos

El cliente una sola vez

Un TAD cola con cinco operaciones y tres clientes que solo pueden usarlas: contar los elementos, listarlos del frente al final y encontrar el último. Después la misma cola en otra representación, con dos listas, y los tres clientes se pegan tal cual. Con la primera representación devolver el dato pasa las pruebas; con la segunda ya no, y ahí queda claro quién había hecho trampa.

¿Cumple el contrato?

Un TAD conjunto especificado con cinco ecuaciones y candidatas para implementar cada operación, primero con listas y después con procedimientos. Tres insert distintos cumplen y son tres representaciones legítimas; un remove que quita solo la primera aparición cumple con un insert y no con otro, y ahí está el punto: las operaciones se prueban juntas, porque el contrato habla de cómo se comportan entre sí.

Tres representaciones del mismo TAD

¿Cuánto vale este dato?

Un mismo valor de Racket leído bajo cinco representaciones del natural, tres de la sesión y dos que no aparecen en ella. Se abre por la unaria, que se lee de un vistazo, y de ahí sube hasta (1 2), que vale distinto en cada representación; después si se puede saber cuánto vale sin conocer la representación, y qué pasa con un dato que la definición nunca produce; por último el acarreo y el préstamo, que son lo que mantiene a succ y pred dentro del contrato.

Bignum en base 10

La representación bignum con el dígito menos significativo adelante. succ con acarreo, pred con préstamo y con el cuidado de no dejar un cero al final, las dos conversiones con los números de Racket, y al cierre un multiplica que solo usa suma, is-zero? y pred: produce (4 4 1) sin un solo car, porque todo el trabajo con dígitos lo hizo succ.

El TAD ambiente: la interfaz

Predecir apply-env

Una cadena de cuatro ligaduras, dos del mismo nombre, y preguntas sobre qué devuelve la búsqueda: qué gana cuando un nombre está dos veces, qué pasa al quitar el eslabón de afuera, y por qué extender no modifica el ambiente que ya existía. El segundo bloque pide escribir la misma cadena con let anidados, que es lo que un ambiente representa.

Clientes del ambiente

La representación con listas y su interfaz vienen dadas, con un ambiente donde m está ligada tres veces. Cinco procedimientos que recorren la cadena solo por la interfaz: ligada? responde sin fallar, nombres lista los eslabones con sus repeticiones, cuantas-veces cuenta, valores-de saca las ligaduras que apply-env oculta, y env->lista construye la vista completa sin saber que por dentro ya era una lista.