Programación lógica y no determinismo

Uno de los mayores problemas que encuentro en el paradigma lógico es que, debido a las peculiaridades de su mecanismo operacional, es difícil extraer patrones de programación que puedan aplicarse de forma práctica en otros contextos (a diferencia de lo que ocurre con la programación funcional). No obstante, una de las características más útiles de la programación lógica a la hora de plantear la resolución de un problema es el no determinismo, un concepto que sí es posible trasladar a otros paradigmas.

Este artículo no pretender ser una introducción a la programación lógica, pero tomaremos algunos programas Prolog como punto de partida. En programación lógica un programa es un conjunto de cláusulas definidas y, dado un objetivo, el interés reside en conocer para qué valores de las variables del objetivo este es consecuencia lógica del programa. Por ejemplo, el siguiente programa modela la relación “ser subconjunto de”, donde el predicado powerset/2 tiene éxito cuando la segunda lista es un subconjunto de la primera:

powerset([], []).
powerset([_|T], P) :- powerset(T, P).
powerset([H|T], [H|P]) :- powerset(T, P).

Si la lista de entrada no contiene elementos, entonces el único subconjunto posible de la lista vacía es la propia lista vacía []. Cuando la lista de entrada tiene al menos un elemento y P es un subconjunto de la cola, entonces hay dos posibles opciones: no incluir la cabeza de la lista de entrada en la solución (segunda cláusula) o sí incluirla (tercera cláusula).

?- powerset([1,2,3], S).
S = [] ;
S = [3] ;
S = [2] ;
S = [2,3] ;
S = [1] ;
S = [1,3] ;
S = [1,2] ;
S = [1,2,3].

A partir de este programa, para un objetivo como ?- powerset([1,2,3], S) el mecanismo de resolución de la programación lógica es capaz de computar automáticamente todos los subconjuntos S de la lista [1,2,3] aplicando pasos de inferencia de manera no determinista. Decimos que este programa es no determinista ya que en algunos puntos de la ejecución de este objetivo existen múltiples pasos de inferencia posibles y Prolog los explora todos.

Programación con efectos y no determinismo

Aunque el no determinismo es una característica intrínseca de la programación lógica y no está disponible de forma directa en otros lenguajes, es posible simular el efecto de las computaciones no deterministas mediante el uso de listas. Por ejemplo, podemos escribir una función en Haskell que reciba una lista y genere todos los subconjuntos de la misma:

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (h:t) = concatMap (\p -> [p, h:p]) (powerset t)

Si la lista de entrada no contiene ningún elemento, entonces el conjunto potencia de la lista vacía solo contiene la propia lista vacía. Si la lista de entrada tiene al menos un elemento h (la cabeza), entonces por cada subconjunto p de la cola generamos dos subconjuntos: el propio subconjunto p y el subconjunto (h:p) que incluye la cabeza.

ghci> powerset [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

En la implementación de esta función hemos enlazado explícitamente dos computaciones no deterministas:

1. powerset t genera todos los posibles subconjuntos de la cola;

2. para cada subconjunto p generado por la primera computación no determinista, [p, h:p] genera dos subconjuntos de la lista de entrada; uno sin incluir la cabeza y otro incluyéndola.

Siempre que enlazamos dos computaciones no deterministas realizamos las mismas operaciones: transformar cada resultado de la primera computación no determinista en una lista de resultados y combinar los nuevos resultados aplanando la lista. Una posible implementación de esta operación es la siguiente:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap _ [] = []
concatMap f (h:t) = f h ++ concatMap f t

En Haskell, las mónadas se utilizan para modelar computaciones con efectos y, en particular, las listas representan computaciones no deterministas que pueden generar cero, uno o más resultados. De hecho, la definición de la función lazo (>>=) para la instancia de Monad [] es precisamente la de concatMap. Esto nos permite utilizar la notación do para implementar funciones no deterministas con un estilo más cercano a Prolog.

powerset :: [a] -> [[a]]
powerset [] = pure []
powerset (h:t) = do p <- powerset t
                    [p, h:p]

No determinismo, no mónadas, no nada

Por supuesto, podemos aprovechar este estilo de programación en cualquier otro lenguaje sin necesidad de mónadas ni de la notación do, aunque esta sintaxis sea especialmente conveniente. Solo necesitamos una definición equivalente a la de concatMap. Por ejemplo, en JavaScript el prototipo de Array cuenta con el método flatMap que hace las veces de concatMap para los arrays:

function powerset(xs) {
    if(xs.length === 0)
        return [[]];
    const [h, ...t] = xs;
    return powerset(t).flatMap(p => [p, [h, ...p]]);
}

Para terminar, vamos a ver un ejemplo más complejo en el que este patrón puede simplificar la implementación de un programa encadenando varias computaciones no deterministas. El predicado permutation/2 tiene éxito cuando la segunda lista es una permutación de la primera:

append([], X, X).
append([H|T], X, [H|S]) :- append(T, X, S).

permutation([], []).
permutation([H|T], P) :-
    permutation(T, S),
    append(X, Y, S),
    append(X, [H|Y], P).

La única permutación de la lista vacía es la lista vacía. Si la lista contiene al menos un elemento, entonces:

1. para cada posible permutación S de la cola;

2. para cada posible par de listas X e Y cuya concatenación es la permutación S;

3. generamos una permutación de la lista de entrada insertando la cabeza H entre X e Y.

Este predicado puede generar por reevaluación todas las posibles permutaciones de la lista de entrada:

?- permutation([1,2,3], P).
P = [1,2,3] ;
P = [2,1,3] ;
P = [2,3,1] ;
P = [1,3,2] ;
P = [3,1,2] ;
P = [3,2,1].

Nótese que en la definición de permutation/2 estamos usando otra característica particular de la programación lógica: la reversibilidad, que nos permite utilizar el mismo predicado append/3 tanto para separar listas como para concatenarlas. En otros lenguajes debemos definir previamente la función para calcular todas las posibles particiones de la lista:

function split(xs) {
    var slices = [];
    for(var i = 0; i <= xs.length; i++)
        slices.push({
            fst: xs.slice(0,i),
            snd: xs.slice(i)
        });
    return slices;
}

function permutation(xs) {
    if(xs.length === 0)
        return [[]];
    const [h, ...t] = xs;
    return permutation(t)
        .flatMap(split)
        .flatMap(p => [[...p.fst, h, ...p.snd]]);
}

Esta definición permite una lectura más declarativa del código donde, para cada permutación de la cola y para cada separación posible de la misma, generamos una permutación de la lista de entrada intercalando la cabeza en cada posible posición intermedia.

nodejs> permutation([1,2,3]);
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]

Conclusiones

La programación lógica dispone de algunas características únicas que permiten formular los problemas de forma clara y concisa. En particular, el no determinismo proporciona un marco de programación muy poderoso que es especialmente útil cuando es necesario explorar un gran espacio de búsqueda.

Trasladar este patrón de diseño a otros lenguajes puede simplificar la implementación de operaciones no deterministas, generando código más legible y mantenible que su alternativa imperativa. Para ello, las computaciones no deterministas se suelen representar como funciones que producen listas o arrays como resultado.

La idea principal aquí expuesta es técnicamente simple: utilizar listas para codificar múltiples soluciones y combinar computaciones no deterministas mediante una suerte de concatMap. Sin embargo, el objetivo de este artículo es poner de relieve que la programación lógica puede aportar un nuevo enfoque a la hora de resolver determinados tipos de problemas, y que estas técnicas pueden resultar de utilidad fuera del propio paradigma lógico.

Por último, es importante tener en cuenta que no siempre es lo más adecuado utilizar este patrón en todos los casos en los que sea posible. Por ejemplo, la función split del programa anterior también admite una formulación basada en concatMap, pero el código resultante es menos legible que el proporcionado anteriormente:

function split(xs) {
    if(xs.length === 0)
        return [{fst: [], snd: []}];
    const [h, ...t] = xs;
    return [{fst: [], snd: xs}]
        .concat(split(t)
            .flatMap(p => [{
                fst: [h].concat(p.fst),
                snd: p.snd
            }]));
}