En una charla reciente en FLOPS, el autor presentó λFS (lambda finite set), un modelo que combina programación funcional con programación relacional al estilo de Datalog y SQL, además de álgebra tensorial. En λFS, una relación se modela como una función finita representada internamente como una tabla clave-valor, y un sistema de tipos garantiza que la función tenga un soporte finito.
El artículo se centra en la dificultad de incorporar recursión a λFS. La recursión introduce no terminación, lo que obliga a recurrir a la teoría de dominios, un formalismo que el autor reconoce no dominar y que ha perdido popularidad. Además, la presencia de efectos reabre el debate sobre el orden de evaluación, que en los lenguajes relacionales adquiere un significado más amplio que en los lenguajes funcionales.
El autor ilustra el problema con una consulta Q(x) := R(x) and test(x) and S(x), donde R y S son tablas y test es un predicado opaco. Distintos órdenes de evaluación —izquierda a derecha, filtrar por S antes de test, o iterar primero sobre S— producen costes muy diferentes. Más relevante aún: el orden puede determinar si la consulta termina. Un ejemplo muestra que evaluar test antes de intersectar R y S puede caer en un bucle infinito, mientras que intersectar primero termina.
Esta tensión revela un conflicto entre dos perspectivas: la de bases de datos, donde el motor elige la estrategia para optimizar, y la de lenguajes de programación, donde el programador debe poder razonar compositivamente sobre terminación y coste. λFS queda atrapado entre ambas.
El artículo propone tres posibles caminos: evaluación estrictamente izquierda-derecha, con un modelo de costes predecible pero rendimiento pobre en consultas cíclicas; orden no determinista, que delega en el optimizador y convierte la terminación en una propiedad quizá/sí/no; y evaluación paralela, que abandona la noción misma de orden. λFS aún no ha resuelto esta cuestión.