Hasta que entiendas recursión...

El uso de recursión, tanto para definir algunas estructuras de datos, como para expresar algoritmos que resuelven problemas de computación, tiene un lugar especial en mi corazón.

Las definiciones recursivas resultan compactas, libres de efectos de borde o estado mutable, y terminan presentando un problema complejo como un conjunto de relaciones entre versiones más simples del mismo problema, o de problemas más simples.

Y eso es algo que hay que enseñarle a las nuevas generaciones.

Uno de los esfuerzos académicos más importantes es enseñar a usar recursión y razonar recursivamente. Se hace difícil con la proliferación de tutoriales y «mejores prácticas» que desprecian a la recursión. Son muchos los desarrolladores convencidos que la recursión es mala, innecesaria, difícil, y confusa, prefiriendo expresar todo con iteraciones. Y para muchos de ellos es verdad, porque han aprendido con lenguajes de programación donde la recursión es ciudadano de segunda, e incluso pobremente soportada, como por compromiso.

En el plan de estudios de la USB tenemos materias en las cuales se discuten estructuras de datos y algoritmos recursivos. A estos últimos muchas veces se les «dá la vuelta» hasta convertirlos en iterativos para apaciguar a las masas. En general hay un balance hacia «no le tengas miedo a la recursión, pero de que vuelan, vuelan».

Eventualmente llegan a materias como Traductores e Interpretadores, donde toda la discusión es matemática y recursiva. Porque todos los lenguajes son formalmente recursivos, reconocerlos (cuando se puede) involucra un proceso recursivo, y el colofón es que existen lenguajes recursivos capaces de hablar de sí mismos, y «pasan cosas». Esa capacidad de usar el lenguaje para hablar del propio lenguaje, la autoreferencia, es abono para paradojas y cuestiones interesantes en relación a la manifestación del pensamiento.

Para los inocentes que piensan que programación no requiere matemáticas, los espera el Laboratorio de Lenguajes de Programación I. No les queda más remedio que razonar y operar recursivamente, pues más de dos tercios del trabajo se hace con lenguajes de programación en los que solamente se pueden expresar programas recursivos; y en el otro tercio, se les plantea un problema que es necesariamente recursivo y las iteraciones no sirven de mucho. En particular, aprendemos a usar Prolog, un lenguaje que, aunque técnicamente es de propósito general, es mejor aplicarlo a problemas de naturaleza recursiva, en la cual haya manipulación de símbolos, patrones, y relaciones.

Durante las pocas semanas que tenemos para discutir la técnica de Programación usando Lógica, única de Prolog, nos vemos en la necesidad de recortar muchas facetas nicho, y nos enfocamos en una técnica fundamental. Prolog es particularmente práctico para problemas en los cuales hay que encontrar una solución por construcción, verificando que cumpla ciertas restricciones. Generalmente el problema es de naturaleza combinatoria, en cada paso hay muchas alternativas posibles, y no existe un algoritmo eficiente para encontrar la solución. Hay que «explorar el espacio de soluciones», hasta dar con la solución, o agotar todas las alternativas. En esa explicación, mostramos a los estudiantes problemas triviales en los cuales la búsqueda es «fuerza bruta», y eventualmente mostramos problemas en los cuales hay que ser un poco más astuto.

La técnica se llama «generar-probar» (generate-test) y consiste en aprovechar la recursión para construir una solución candidata, e inmediatamente verificar si cumple con todas las condiciones. Si es así, pues resuelto el problema. Pero si no cumple, aprovechar que el lenguaje «regresa» (backtracks) a la decisión anterior para reconsiderarla, posiblemente generando una nueva solución.

En el Grupo de Lenguajes de Programación nos costó mucho tiempo llegar a una forma razonable de evaluar las destrezas en esta técnica. Después de varias ediciones del curso, llegamos a un balance conveniente en enviar una «tarea» compuesta de varios ejercicios. Uno o dos de los ejercicios siempre es simple por «fuerza bruta» sin miramientos, uno que requiere un poco más de astucia generalmente en el estilo de búsqueda, y un ejercicio mucho más complicado. Este último siempre es el de mayor peso en la evaluación, y está cuidadosamente calibrado 1 tal que, si se hace por «fuerza bruta», la primera solución tarde al menos dos o tres días en calcularse suponiendo que el código es correcto -- esto con la intención de que tengan que ser realmente astutos al atacarlo, incluyendo no dejarlo para el último día.

Los ejercicios del primer tipo son muy fáciles de diseñar. Los ejercicios del segundo tipo, usualmente se fabrican a partir de problemas de combinatoria o búsqueda, como los que se encuentran en libros de problemas de combinatoria. Personalmente, tengo una colección amplia de ejercicios como esos, resueltos en Prolog y en lenguajes menos apropiados, así que podía escoger de allí. El último ejercicio de cada tarea siempre es del tercer tipo, y es más trabajo para nosotros que para los alumnos. Creaciones que van desde lo artístico (pun intended), pasando por lo deportivo, hasta llegar a navegación, inspiradas en acertijos que encuentro (o me encuentran vía partes interesadas).

Me quedó un ejercicio que nunca pude proponer como tarea. Combina recursión, auto-referencia, relaciones, y números. Considerando que el nombre de la colega que me lo hizo llegar es palíndromo, quedó perfecto después que adapté la última pregunta para ser relevante.

Selección simple

Los estudiantes de Lenguajes de Programación I siempre tuvieron que enfrentar preguntas de Selección Simple, con factor de corrección, y cuando preguntaban «Profe, ¿qué quiere decir con X?» la respuesta era «exactamente eso».

El ejercicio que nunca fue propuesto, habría tenido el siguiente enunciado en lo que habría sido un crossover colosal:

I heard you don't like tests dawg, so I got you a test within a test

Escriba un programa en Prolog que triunfe contestando el siguiente examen de selección simple de manera perfecta:

  1. La primera pregunta cuya respuesta es b es la pregunta

    a. 2

    b. 3

    c. 4

    d. 5

    e. 6

  2. Solamente hay dos preguntas consecutivas con la misma respuesta. ¿Cuáles son?

    a. 2 y 3

    b. 3 y 4

    c. 4 y 5

    d. 5 y 6

    e. 6 y 7

  3. La respuesta a esta pregunta es la misma que la respuesta a la pregunta

    a. 1

    b. 2

    c. 4

    d. 7

    e. 6

  4. ¿Cuántas preguntas tienen respuesta a?

    a. 0

    b. 1

    c. 2

    d. 3

    e. 4

  5. La respuesta a esta pregunta es la misma que la respuesta a la pregunta

    a. 10

    b. 9

    c. 8

    d. 7

    e. 6

  6. Hay tantas preguntas con respuesta a como preguntas con respuesta

    a. b

    b. c

    c. d

    d. e

    e. Ninguna de las anteriores.

  7. Según el orden alfabético, la respuesta a esta pregunta y la respuesta a la siguiente pregunta, están ¿a cuántas letras de distancia?

    a. 4 letras

    b. 3 letras

    c. 2 letras

    d. 1 letras

    e. Son la misma letra.

  8. ¿Cuántas preguntas tienen como respuesta una vocal?

    a. 2

    b. 3

    c. 4

    d. 5

    e. 6

  9. El número de preguntas cuya respuesta es consonante es un

    a. Primo.

    b. Factorial.

    c. Cuadrado.

    d. Cubo.

    e. Divisible entre cinco.

  10. ¿42?

    a. a

    b. b

    c. c

    d. d

    e. e

Implemente el predicado prove/0 que triunfe imprimiendo

    (1) r1
    (2) r2
    ...
    (10) r10

donde r1, r2, ..., r10 son las letras que corresponden a las respuestas que resultan en un examen perfecto.

La respuesta debe emitirse en menos de cinco (5) segundos.

Khé?

Ese problema se puede resolver con papel y lápiz. Como un Sudoku sin pistas. Vas a tener que escribir y borrar mucho. Va a poner a prueba tu capacidad de hablar, de hablar de lo que estás hablando, y de hablar de lo que estás hablando sobre lo que estabas hablando al principio. Y si te están hablando, perdiste.

Ese problema también lo puedes resolver con cualquier lenguaje de programación en el cual puedas simular backtracking, sea la tacita, la culebra, la gema, el roedor drogado, el rancho, o el nefasto. Vas a echar muchas líneas de código, bien por ti. Vas a tener que corregir defectos que no tienen que ver con el problema, sino con el problema en que te metiste al usar el lenguaje equivocado, y el problemón por huirle a la recursión. Pero así se aprende.

También lo puedes resolver muchísimo mejor con cualquier lenguaje de programación que tenga continuaciones. Vas a tener que ser cuidadoso con la plomería, considerando que hay varios casos de salida a considerar, y terminarás corrigiendo errores relacionados con usar una técnica correcta de forma equivocada, a muy bajo nivel.

Si sigues leyendo, encontrarás una solución en Prolog.

Calculando el examen perfecto

La técnica

La técnica «generate-test» es adecuada para problemas de búsqueda, en particular cuando hay «fuerza bruta» involucrada. Una manera de resolver este problema es generar una posible respuesta al examen (diez respuestas) y luego verificar si la respuesta «cumple» con todas las reglas.

En este sentido, el problema es bastante simple. El lector astuto ya habrá calculado que hay 9765625 maneras posibles de contestar el examen. Habría que generar todas las respuestas desde aaaaaaaaaa hasta eeeeeeeeee, para cada una verificar que las condiciones se cumplan, e imprimir cuando se cumplan todas.

Las restricciones están expresadas como relaciones entre las respuestas. No son simples condicionales, y además algunos requieren hacer conteos y otras operaciones. Como el examen tiene que resultar perfecto sabemos que tan pronto falla una de las condiciones, esa solución no es viable y podemos descartarla.

Como es frecuente en este tipo de problemas, el programa fue pensado y escrito «top-down». Es conveniente tener familiaridad con el funcionamiento del lenguaje, más allá de las pistas en los comentarios.2

El predicado principal solve/0 trata de encontrar la respuesta perfecta usando el predicado auxiliar answer(-List), que unificará L con una lista de forma ad-hoc, la cual es usada por el predicado auxiliar sheet(+List) para mostrarla en pantalla.

solve :- answer(L),      % Answer perfectly
         sheet(L).       % Print answers.

% Go through list printing question number N and answer letter A
sheet([]) :- !.
sheet([N/A|Rest]) :- 
  write('('), write(N), write(') '), write(A), nl,
  sheet(Rest).

Cada respuesta posible es una letra entre a y e. El predicado member/2 de Prolog tiene varias maneras de emplearse. Una de ellas es instanciar una variable libre con los valores de una lista. Cada vez que se reconsidera la invocación, el predicado procede con el siguiente valor hasta agotarlo. El predicado letters/1 permitirá tener un generador de valores posibles por cada variable asociada a una respuesta.

letters(X) :- member(X,[a,b,c,d,e]).

El flujo principal de resolución está en el predicado answer(-List). Este predicado instanciará una lista de diez elementos, uno por cada pregunta con su respectiva respuesta. Esa lista comienza con «parejas» conformadas por todos los números de pregunta definidos, y variables libres (vacías, sin unificar) correspondientes a las respuestas que tenemos que completar. Puede resultar curioso el uso de la barra (/) para hacer las parejas. En Prolog, escribir 1/a no es una división, y escribir 1/2 no es una división hasta que se use como una división. En otras palabras, podría haber escrito p(1,a) o 1-a, e igual funciona ajustando sheet(+List) para usar la misma forma. Es un lenguaje para procesamiento simbólico antes que numérico.

En la primera parte de answer(-List) «proponemos» una posible respuesta. Para cada variable correspondiente a una respuesta (One, Two,...) asociamos una de las cinco posibles letras, empleando el predicado auxiliar letters(-Atom). Esto es, cada vez que el programa reconsidere alguna de las invocaciones de letters(Var), cambiará la letra en dicha variable hasta agotar las posibilidades pendientes en esa invocación particular, si las agotó, reconsidera la invocación anterior. Eso ocurre automáticamente pues Prolog incluye backtracking como parte de su funcionamiento. Sin ciclos anidados ni necesidad de «recordar» por donde voy.

Una vez generada una posible solución, la segunda mitad de answer(-List) verifica las condiciones una por una. Si una condición no se cumple, el lenguaje reconsidera la instrucción anterior para probar otra posibilidad. Esto es, si la primera condición falla, se reconsidera la última variable asociada; si la segunda condición falla, se reconsidera la primera condición. Esto porque algunas condiciones tienen más de una forma de comprobarse.

Hay condiciones que requieren contar items e incluso aritmética. Esas operaciones se hacen en el último momento posible, y fuera de las verificaciones particular, para ahorrar tiempo y no repetir trabajo.

answer([1/One,2/Two,3/Three,4/Four,5/Five,6/Six,7/Seven,8/Eight,9/Nine,10/Ten]) :-
  % Generate possible values for each answer and build an internal
  % list with the proposed solution, to be used of verifying conditions.
  letters(One),       % Try `a` to `e` for One, one at a time, via backtracking
  letters(Two),       % Try `a` to `e` fro Two, one at a time, via backtracking
  letters(Three),     % ...so on and so forth...
  letters(Four),
  letters(Five),
  letters(Six),
  letters(Seven),
  letters(Eight),
  letters(Nine),
  letters(Ten),       % ... until all ten variables are bound
  % Build a list for easier handling while checking
  Answers = [One,Two,Three,Four,Five,Six,Seven,Eight,Nine,Ten],

  % Check questions are answered correctly with the proposed solution.
  question1(Answers),
  question2(Answers),
  question3(Answers),
  howmany(a,Answers,NA),   % Count `a`'s exactly once
  question4(Answers,NA),
  question5(Answers),
  howmany(b,Answers,NB),   % Count `b`'s exactly once
  howmany(c,Answers,NC),   % Count `c`'s exactly once
  howmany(d,Answers,ND),   % Count `d`'s exactly once
  howmany(e,Answers,NE),   % Count `e`'s exactly once
  question6(Answers,NA,NB,NC,ND,NE),
  question7(Answers),
  Vowels is NA + NE,
  question8(Answers,Vowels),
  Consonants is NB + NC + ND,
  question9(Answers,Consonants).

El predicado auxiliar howmany(+Atom,+List,-Number) triunfa unificando en su tercer argumento el número de veces que su primer argumento (una letra) ocurre en su segundo argumento (una lista).

Está escrito en la manera típica de Prolog para predicados que cuentan o buscan: un predicado principal que siembra el contador en cero, y un auxiliar, recursivo, con argumentos adicionales, que hace el recorrido y la cuenta. Las variables en Prolog son inmutables una vez asociadas, por lo que no existe N = N + 1 3 y es necesario usar variables intermedias para hacer aritmética. Así mismo, Prolog no tiene «funciones», sino predicados que necesitan sus argumentos previamente evaluados, por lo que no existe foo(2*N+1) 4.

Finalmente, como hay una sola forma de hacer esa cuenta, el predicado incluye un corte determinístico (la exclamación). Así, si el lenguaje está reconsiderando evaluarlo, lo «salte», pasando a reconsiderar el anterior, de manera que cambien los argumentos.

howmany(X,Answers,N) :- howmany(X,Answers,0,N), !.
howmany(_,[],N,N).
howmany(X,[X|R],C,N) :- C1 is C + 1, howmany(X,R,C1,N).
howmany(X,[Y|R],C,N) :- X \= Y, howmany(X,R,C,N).

Resta verificar que las respuestas cumplan con las condiciones impuestas por el problema. Prolog es el lenguaje donde se inventó el «pattern matching» que hoy es popular entre los lenguajes más avanzados -- se comparan estructuras y sus partes. Al mismo tiempo, el mecanismo de unificación permite comparar valores posicionalmente usando el mismo nombre de variable. Las respuestas propuestas están todas en una lista, lo que permitirá procesarlas en conjunto. Pasaremos la lista con todas las respuestas como argumento a predicados, que usarán «pattern matching» y unificación para comprobar lo que sea pertinente comprobar en cada caso.

Para que la primera respuesta sea correcta, es necesario que la primera b esté en alguna de las posiciones mencionadas como posible respuesta. En Prolog, las reglas se prueban «de arriba abajo» así que no necesito escribir un if, sino enumerar los casos posibles. Al mismo tiempo, basta utilizar la estructura deseada como comparador: si la lista suministrada como argumento tiene la misma estructura y los valores en las posiciones necesarias, la condición se verifica inmediatmanete. Si ninguna condición se cumple, la falla obligará a Prolog a reconsiderar el paso anterior. Aquí, el «pattern matching» hace todo el trabajo: la lista suministrada debe coincidir con la lista patrón, que está entre corchetes; los elementos a la izquierda de la barra son posicionales, a la derecha está el resto de la lista. El guión bajo (_ o underscore) corresponde con «aquí debe haber algo, pero no me importa».

% 1. First question with answer `b` is
%     (a) 2 (b) 3 (c) 4 (d) 5 (e) 6

question1([a,b|_]).
question1([b,_,b|_]).
question1([c,_,_,b|_]).
question1([d,_,_,_,b|_]).
question1([e,_,_,_,_,b|_]).

La segunda condición es, por mucho, la más complicada. Hay que determinar si hay exactamente una ocurrencia de dos respuestas consecutivas, y de haberlas, determinar cuáles son para comprobar la respuesta.

El predicado twoinarow(+List,-Int) recorre la lista suministrada contando cada vez que el primer elemento es igual al segundo, y al final unifica el valor resultante en su segundo argumento. En su construcción aplica el mismo comentario que para howmany(+Atom,+List,-Num).

Si el conteo es exactamente uno, determinamos cuáles son por inspección, al tiempo que comprobamos la respuesta. Para eso, el predicado validquestion2(+List) verifica que en la solución propuesta, la respuesta a esta pregunta cumpla con la forma, i.e. para cada respuesta posible, los valores de X tienen que ser los mismos.

% 2. Only two consecutive answers are equal,
%     (a) 2 and 3 (b) 3 and 4 (c) 4 and 5 (d) 5 and 6 (e) 6 and 7
question2(Answers) :-
  twoinarow(Answers,Count),
  Count == 1,
  validquestion2(Answers).

twoinarow(List,Count) :- twoinarow(List,0,Count), !.

twoinarow([],C,C).
twoinarow([Current|[Current|Rest]],N,C) :- !,
  N1 is N + 1,
  twoinarow([Current|Rest],N1,C).
twoinarow([_|R],N,C) :- twoinarow(R,N,C).

validquestion2([_,a,a,_,_,_,_,_,_,_]).
validquestion2([_,b,X,X,_,_,_,_,_,_]).
validquestion2([_,c,_,X,X,_,_,_,_,_]).
validquestion2([_,d,_,_,X,X,_,_,_,_]).
validquestion2([_,e,_,_,_,X,X,_,_,_]).

La tercera condición es la más fácil de comprobar. Nuevamente aprovechamos las habilidades de pattern matching para determinar si la solución propuesta es válida.

% 3. The answer to this question is the same answer to question
%     (a) 1 (b) 2 (c) 4 (d) 7 (e) 6
question3([a,_,a,_,_,_,_,_,_,_]).
question3([_,b,b,_,_,_,_,_,_,_]).
question3([_,_,c,c,_,_,_,_,_,_]).
question3([_,_,d,_,_,_,d,_,_,_]).
question3([_,_,e,_,_,e,_,_,_,_]).

Verificar la cuarta condición sólo necesita el conteo calculado con howmany(+Atom,+List,-Num) justo antes de la invocación, para comprobar que la respuesta correcta está en la solución propuesta.

% 4. How many questions have `a` as an answer?
%     (a) 0 (b) 1 (c) 2 (d) 3 (e) 4
question4([_,_,_,a,_,_,_,_,_,_],0).
question4([_,_,_,b,_,_,_,_,_,_],1).
question4([_,_,_,c,_,_,_,_,_,_],2).
question4([_,_,_,d,_,_,_,_,_,_],3).
question4([_,_,_,e,_,_,_,_,_,_],4).

La quinta condición se verifica con la misma estrategia que para la tercera condición.

% 5. The answer to this question is the same answer to question
%     (a) 10 (b) 9 (c) 8 (d) 7 (e) 6
question5([_,_,_,_,a,_,_,_,_,a]).
question5([_,_,_,_,b,_,_,_,b,_]).
question5([_,_,_,_,c,_,_,c,_,_]).
question5([_,_,_,_,d,_,d,_,_,_]).
question5([_,_,_,_,e,e,_,_,_,_]).

La sexta condición es interesante porque tiene un caso borde sutil. El predicado question6(+List,+Num,+Num,+Num,+Num,+Num) compara la cantidad de respuestas con a con cada una de las otras letras. Esas cantidades se calcularon previamente en el predicado principal. Nuevamente recurrimos a usar «pattern matching» y unificación caso por caso.

Recordando que en Prolog no hay if, es necesario que todos los casos (cláusulas) de un predicado sean mutuamente exclusivos cuando la condición que se está comprobando así lo es. Es por eso que para las primeras cuatro reglas basta usar unificación posicional. El último caso requiere comprobar explícitamente que las cantidades son diferentes para satisfacer el «ninguna de las anteriores», i.e. no es igual a ninguno de los demás. Así mismo, el corte determinístico es pertinente porque sólo hay una forma de evaluar esta condición.

% 6. Tne number of questions with answer `a` equal the number
%    of questions with answer
%     (a) b (b) c (c) d (d) e (e) none of the above

question6([_,_,_,_,_,a,_,_,_,_],A,A,_,_,_) :- !.
question6([_,_,_,_,_,b,_,_,_,_],A,_,A,_,_) :- !.
question6([_,_,_,_,_,c,_,_,_,_],A,_,_,A,_) :- !.
question6([_,_,_,_,_,d,_,_,_,_],A,_,_,_,A) :- !.
question6([_,_,_,_,_,e,_,_,_,_],A,B,C,D,E) :- A \= B, A \= C, A \= D, A \= E, !.

La séptima condición requiere un poco de trabajo para poder hacer las comparaciones de «distancia alfabética». Hay que notar que la relación «distancia entre» es simétrica, i.e. la distancia entre a y e es la misma que entre e y a, pues nos interesa el valor absoluto.

Así, usaremos un predicado pos(+Atom,+Num) para relacionar el valor numérico con cada letra según el orden alfabético. Eso nos permite escribir el predicado distance(+Atom,+Atom,-Num) que triunfa si la distancia alfabética entre sus dos primeros argumentos, medida en «letras», unifica con el tercer argumento.

Ahora podemos comprobar la condición si las letras en las posiciones particulares tienen la distancia deseada, según el predicado chooseanswer7(+Atom,+Int) que codifica las respuestas posibles.

% 7. Alphabetically, the answer to this question and the answer
%    to the following question are
%      (a) 4 apart (b) 3 apart (c) 2 apart (d) 1 apart (e) the same

question7([_,_,_,_,_,_,This,Following,_,_]) :-
  distance(This,Following,D),
  chooseanswer7(This,D).

chooseanswer7(a,4).
chooseanswer7(b,3).
chooseanswer7(c,2).
chooseanswer7(d,1).
chooseanswer7(e,0).

pos(a,1).
pos(b,2).
pos(c,3).
pos(d,4).
pos(e,5).

distance(X,Y,D) :- pos(X,V0), pos(Y,V1), V is V0-V1, D is abs(V).

La octava condición es similiar a la cuarta, en cuanto que utilizamos la suma del conteo de a y e, para verificar que la respuesta propuesta sea consistente con «pattern matching] directo.

% 8. How many questions have a vowel as an aswer?
%     (a) 2 (b) 3 (c) 4 (d) 5 (e) 6

question8([_,_,_,_,_,_,_,a,_,_],2).
question8([_,_,_,_,_,_,_,b,_,_],3).
question8([_,_,_,_,_,_,_,c,_,_],4).
question8([_,_,_,_,_,_,_,d,_,_],5).
question8([_,_,_,_,_,_,_,e,_,_],6).

La novena condición requiere determinar si el número resultante de sumar los conteos de b, c y d tiene alguna de las propiedades indicadas.

Esta suma tiene que ser al menos 0, si no hubiera respuestas consonantes, y no puede ser más de 10, porque son 10 preguntas en total. De modo que sólo tenemos que preocuparnos por las propiedades de los números entre 0 y 10. Para cada respuesta propuesta, determinamos si la suma está en el conjunto particular.

Hay números que están en varias categorías, por eso es que los casos no son mutuamente excluyentes (no tienen cortes determinísticos).

% 9. The nuber of quesions whose answer is a consonant is
%     (a) prime (b) factorial (c) square (d) cube (e) divisible by five
%    Nota: escoja ser primo antes que otra propiedad

question9([_,_,_,_,_,_,_,_,a,_],V) :- member(V,[2,3,5,7]).  % primes
question9([_,_,_,_,_,_,_,_,b,_],V) :- member(V,[1,2,6]).    % factorials
question9([_,_,_,_,_,_,_,_,c,_],V) :- member(V,[0,1,4,9]).  % squares
question9([_,_,_,_,_,_,_,_,d,_],V) :- member(V,[0,1,8]).    % cubes
question9([_,_,_,_,_,_,_,_,e,_],V) :- member(V,[0,5,10]).   % divides by five

No hace falta verificar nada en la última condición. Cualquier respuesta es válida siempre y cuando cumpla con las otras nueve condiciones. Estoy seguro que esto habría confundido a muchos estudiantes. En el problema original rezaba como se lee en el comentario, por lo que cambiarlo por la respuesta de la vida, el universo, y todo, siempre es apropiado.

% 10. The answer to this question is
%      (a) a (b) b (c) c (d) d (e) e
% 
% No hace falta hacer nada.

Solamente resta ejecutar el predicado. En mis cursos siempre exijo utilizar GNU Prolog, pues implanta ISO Prolog sin predicados especiales5. Este programa está escrito en ISO Prolog6 así que se puede usar GNU Prolog o SWI Prolog, que es lo que uso profesionalmente pues incluye un predicado time/1 conveniente para tomar el tiempo.

emhn@trillian:~$ swipl
?- consult('quiz-within-a-quiz.pro').
true.

?- time(solve).
(1) c
(2) d
(3) e
(4) b
(5) e
(6) e
(7) d
(8) c
(9) b
(10) a
% 29,740,475 inferences, 4.658 CPU in 4.660 seconds (100% CPU, 6384665 Lips)
true .

Esa es la única solución perfecta.

¿Por qué nunca fue propuesto?

Cuando escribí la solución por primera vez, quedó claro que era un problema de los fáciles, incluso con la restricción de tiempo. La búsqueda no es nada sofisticada, y el espacio de soluciones no es tan grande. Al mismo tiempo, me quedó claro que la descripción del problema era de los intermedios, con lo que los estudiantes quizás se irían por un camino inadecuado. Sólo tenía el «shock value» de «quéjesto?».

La primera vez que lo quise proponer, los estudiantes que me asistían en el laboratorio propusieron dos ejercicios buenos, así que lo guardé. La segunda vez, era el único instructor, y se habría combinado con el «deportivo» (que es una joyita, y eso que está simplificado brutalmente). Quería que los estudiantes tuvieran algo simple para atacar, así que preferí poner lo que puse. La tercera vez, habría sido en Septiembre-Diciembre 2017, pero emigré.

Mi colega con nombre (y apellido) palindrómico nunca me dijo si lo implantó «en una vaina normal, no esas loqueras mágicas que usas tú». «Cualquier tecnología lo suficientemente avanzada es totalmente indistinguible de la magia.»7, le dije, y como siempre, me volteó los ojos.

Al menos cuando yo preparaba la tarea...

En la documentación y comentarios es tradicional describir los predicados por su nombre y lista de argumentos foo(+Num,+List,-List). El prefijo + indica que el predicado espera que dicho argumento ya esté unificado con un valor concreto de ese tipo, mientras que el prefijo - indica que el predicado unificará valores concretos de ese tipo con el argumento, por lo que puede pasarse una variable libre. Si un predicado no recibe argumentos se denota foo/0. No se describen los argumentos de los predicados provistos del lenguaje, como member/2, porque para eso está la documentación del lenguaje.

De hecho, el = no se lee como «asignación» sino como «unificación» o «asociación». Una vez que una variable libre se unifica con un valor, no puede unificarse con ningún otro hasta que triunfe o falle el predicado. Solamente puede cambiar de valor en una reconsideración.

Si existe, pero lo que hace es invocar foo con el argumento +(\*(2,N),1). Eso es sumamente útil para manipular estructuras recursivas.

SWI Prolog tiene un predicado if-then-else que es contrario a la filosfía de Prolog. No quería que mis estudiantes «huyeran por la derecha» con ese predicado, sino que aprendieran a usar casos y exclusión mutua como debe ser.

En SWI Prolog abs y otros predicados numéricos evalúan sus argumentos númericos implícitamente y hacen aritmética sin is. Eso es horrible, fuera de especificación, e impide el tipo de cosas que hacemos los que manipulamos estrucutras. Vengan de a uno. I. Will. End. You.

Tercera Ley de Arthur C. Clarke