El investigador Michael Arntzenius (conocido como mietek) publicó en septiembre de 2022 su tesis doctoral «Deconstructing Datalog», donde explora la fusión de Datalog —un lenguaje de programación lógica de los años 80 que extiende el álgebra relacional con consultas recursivas— con la programación funcional tipada. El resultado es Datafun, un lenguaje que integra ambas tradiciones de forma coherente.
La tesis parte de una observación central: las consultas recursivas de Datalog pueden reformularse como puntos fijos de funciones monótonas sobre conjuntos. Por ejemplo, la alcanzabilidad en un grafo se escribe como fix (λR. {start} ∪ {y | x ∈ R, (x,y) ∈ edge}). Este enfoque permite trasladar la semántica de Datalog a un lenguaje funcional equipado con un operador de punto fijo.
Uno de los principales retos fue capturar la condición de estratificación de Datalog, que garantiza que las consultas recursivas estén bien definidas. Datafun la implementa mediante un sistema de tipos que rastrea la monotonicidad de las funciones de forma composicional. El tipado es seguro pero incompleto: rechaza algunos programas monótonos como no monótonos, aunque cubre todo lo que Datalog puede expresar.
En cuanto a eficiencia, la tesis aborda la iteración seminaïve, que evita el trabajo redundante de la iteración ingenua (que puede producir un crecimiento cuadrático en grafos lineales). La idea es calcular solo los cambios incrementales entre iteraciones, inspirada en el cálculo lambda incremental. El capítulo 3 detalla cómo aplicar este método a Datafun, logrando una mejora asintótica significativa.
Datafun demuestra que es posible combinar la simplicidad semántica de Datalog con la expresividad de la programación funcional, abriendo camino a nuevas herramientas de análisis de datos y verificación.