Saltar a contenido

Ejercicios · FLP · Induccion y recursion

El lenguaje del curso, practicado antes de que aparezca el primer intérprete. El repaso de Racket es material de lectura, y estas tres actividades son la parte que no se aprende leyendo: escribir procedimientos, correrlos y ver qué responden. Todo pasa en el navegador, sin instalar nada.

Son cinco actividades y veintiocho procedimientos por escribir. Se pueden hacer en cualquier momento y conviene tenerlas resueltas antes de la sesión sobre inducción y recursión, que supone resuelto lo que aquí se practica.

notación prefija y definiciones

Cinco procedimientos sin recursión, para que la mano se acostumbre a que el operador vaya adelante. El promedio de tres números obliga a decidir qué operación queda en el paréntesis de afuera; la conversión de grados encadena tres. Después aparecen and para juntar dos comparaciones, cond para tres casos que se excluyen y let* para nombrar los resultados intermedios de una cuenta que reparte segundos en horas y minutos.

En el camino salen dos marcas de nombre que se repiten todo el semestre: el signo de interrogación al final de lo que devuelve un booleano y la flecha en medio de lo que convierte. Y sale la comilla, que es lo que separa un símbolo del nombre de una variable.

condicionales: if y cond

Cinco decisiones. Las dos primeras son el mismo problema, el mayor de tres números, escrito con if anidado y después con cond, que es la forma de ver qué aplana el segundo y qué cuesta el primero.

Las otras tres son los casos donde una de las dos formas es la que corresponde: un if metido en mitad de una resta, porque produce un valor y cabe donde vaya un número; una clasificación por rangos donde cada cláusula hereda lo que descartaron las anteriores; y una pregunta por la forma del dato, donde la lista vacía también responde que sí a list? y el orden decide si queda bien clasificada.

recursión lineal y recursión de cola

Seis procedimientos donde la misma cuenta se escribe de las dos maneras. La suma hasta n primero deja la suma esperando a que la llamada vuelva, y después lleva el total adelantado en un acumulador. La diferencia no se queda en el estilo: una de las pruebas suma hasta cincuenta mil y la versión lineal no la pasa.

Siguen el factorial, que cambia la operación y con ella el valor con que arranca el acumulador; el largo de una lista, donde lo que se agota ya no es un número; invertir una lista, que sale volteada sola porque se construye mientras se baja; y Fibonacci con dos acumuladores, que es lo que convierte un cálculo impracticable en uno inmediato.

ligaduras locales: let, let* y letrec

Seis procedimientos con nombres que solo viven dentro de una expresión. Las tres formas se escriben casi igual y se diferencian en una sola cosa: en qué ambiente se evalúan las expresiones que calculan los valores.

Empieza por el caso que solo let resuelve, correr tres valores una posición sin perder ninguno, porque las tres derechas miran los valores originales. Sigue con la cadena que obliga a let*, donde el promedio necesita la cantidad y la suma ya calculadas, y con dos let anidados, que es lo que let* hace por debajo.

Los tres últimos son de letrec. Uno pide escoger la palabra que permite que un procedimiento local se llame a sí mismo; otro esconde un acumulador para que no aparezca en la interfaz; el último define dos procedimientos que se nombran mutuamente. Esa forma es la que reaparece al implementar letrec en el intérprete del curso.

listas simbólicas y procedimientos como valores

Seis procedimientos sobre listas de símbolos. Buscar uno, quedarse con los que son símbolos, quitar los repetidos usando el procedimiento de búsqueda ya escrito, y aplanar una lista anidada, que necesita recursión sobre el primer elemento y sobre el resto al mismo tiempo.

Los dos últimos reciben otro procedimiento como argumento y con eso quedan escritos mapea y filtra, que no vienen con el evaluador de la página. Pasar un procedimiento como un dato cualquiera es lo que más adelante permite guardar una clausura en un ambiente.

Cómo funciona cada actividad

Se llena el esqueleto donde dice ???, se presiona Probar y las pruebas dicen qué pasó. Cuando una falla, el mensaje dice qué llamada se cayó, qué dio y qué debía dar, y los tropiezos más frecuentes traen además su explicación. Al final de cada página hay una consola libre para tantear cualquier otra cosa.

El evaluador de la página entiende define, lambda, if, cond, let, let*, letrec, and, or y las primitivas de listas y aritmética, incluidas todas las combinaciones de car y cdr hasta cuatro niveles, de caar a cddddr. No tiene define-datatype ni cases, ni map, ni filter: por eso dos de los retos consisten en escribirlos. Lo que se entrega en el curso se escribe y se corre en DrRacket.