Towards a Neural Lambda Calculus: Neurosymbolic AI Applied to the Foundations of Functional Programming

João Marcos Flach; Álvaro F. Moreira; Luis C. Lamb

doi:10.5753/jbcs.2026.6101

Authors

João Marcos Flach Federal University of Rio Grande do Sul https://orcid.org/0000-0003-0452-3098
Álvaro F. Moreira Federal University of Rio Grande do Sul https://orcid.org/0000-0002-9224-2781
Luis C. Lamb Federal University of Rio Grande do Sul https://orcid.org/0000-0003-1571-165X

DOI:

https://doi.org/10.5753/jbcs.2026.6101

Keywords:

Machine Learning, Lambda Calculus, Neurosymbolic AI, neural networks, Transformer Model, Sequence-to-Sequence Models, Computational Models

Abstract

Over the last decade, deep neural network models have become the dominant paradigm in machine learning. The use of artificial neural networks in symbolic learning has seen growing relevance in recent years. To study the capabilities of neural networks in the domain of symbolic AI, researchers have explored the ability of deep neural networks to learn arithmetic operations, perform logical inference, and execute computer programs. However, executing computer programs remains highly challenging for neural networks. As a result, success in this area has been limited, often requiring biased elements in the learning process and restricting the range of executable programs. In this work, we analyze the ability of neural networks to learn how to execute programs as a whole. To do so, we propose a distinct approach. Instead of using an imperative programming language with complex structures, we use the lambda calculus (λ-calculus), a simple and Turing-complete mathematical formalism. This formalism serves as the basis for modern functional programming languages and lies at the heart of computability theory since its initial definition by Alonzo Church. We introduce the an integrated neural learning and lambda-calculus formalization. We also explore the execution of a program in λ-Calculus based on reductions and show that learning to perform these reductions is enough to execute any program.

Downloads

Download data is not yet available.

References

Arabshahi, F., Singh, S., and Anandkumar, A. (2018). Combining symbolic expressions and black-box function evaluations in neural programs. In 6th International Conference on Learning Representations, ICLR 2018. DOI: 10.48550/arxiv.1801.04342.

Barendregt, H. (1984). The Lambda Calculus: Its Syntax and Semantics. North-Holland Linguistic Series. North-Holland. DOI: 10.1016/c2009-0-14341-6.

Besold, T. R., Garcez, A. d., Bader, S., Bowman, H., Domingos, P., Hitzler, P., Kühnberger, K.-U., Lamb, L. C., Lowd, D., Lima, P. M. V., et al. (2022). Neural-symbolic Learning and Reasoning: A survey and interpretation. Neuro-Symbolic Artificial Intelligence: The State of the Art. DOI: http://dx.doi.org/10.3233/FAIA210348.

Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901. DOI: 10.48550/arxiv.2005.14165.

Cardone, F. and Hindley, J. R. (2006). History of lambda-calculus and combinatory logic. Handbook of the History of Logic, 5:723-817. Available at:[link].

Cho, K., van Merrienboer, B., Bahdanau, D., and Bengio, Y. (2014). On the properties of neural machine translation: Encoder-decoder approaches. DOI: 10.3115/v1/w14-4012.

Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2):345-363. DOI: 10.2307/2371045.

d'Avila Garcez, A. S., Lamb, L. C., and Gabbay, D. (2009). Neural-Symbolic Cognitive Reasoning. Springer, Berlin. DOI: 10.1007/978-3-540-73246-4.

de Bruijn, N. (1972). Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the church-rosser theorem. Indagationes Mathematicae (Proceedings), 75(5):381-392. DOI: 10.1016/1385-7258(72)90034-0.

De Raedt, L., Kersting, K., Natarajan, S., and Poole, D. (2016). Statistical Relational Artificial Intelligence: Logic, Probability, and Computation. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers. DOI: 10.2200/S00692ED1V01Y201601AIM032.

Dietterich, T. G. (2017). Steps toward robust artificial intelligence. AI Magazine, 38(3):3-24. DOI: 10.1609/aimag.v38i3.2756.

Garcez, A. d. and Lamb, L. C. (2023). Neurosymbolic AI: The 3rd Wave. Artificial Intelligence Review, pages 1-20. DOI: 10.1007/s10462-023-10448-w.

Garcez, A. S. d., Lamb, L. C., and Gabbay, D. M. (2006). Connectionist computations of intuitionistic reasoning. Theoretical Computer Science, 358(1):34-55. DOI: 10.1016/j.tcs.2005.11.043.

Gaur, M. and Sheth, A. P. (2024). Building trustworthy neurosymbolic AI systems: Consistency, reliability, explainability, and safety. AI Mag., 45(1):139-155. DOI: 10.1002/AAAI.12149.

Graves, A., Wayne, G., and Danihelka, I. (2014). Neural Turing machines. arXiv preprint arXiv:1410.5401. DOI: 10.48550/arXiv.1410.5401.

Hinton, G. (2025). Nobel lecture: Boltzmann machines. Reviews of Modern Physics, 97(3):030502. DOI: 10.1103/RevModPhys.97.030502.

Kaiser, Ł. and Sutskever, I. (2015). Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228. DOI: 10.48550/arXiv.1511.08228.

Kautz, H. (2022). The Third AI Summer: AAAI Robert Engelmore memorial lecture. AI Magazine, 43(1):105-125. DOI: 10.1002/aaai.12036.

Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. DOI: 10.48550/arXiv.1412.6980.

Lample, G. and Charton, F. (2019). Deep learning for symbolic mathematics. arXiv preprint arxiv:1912.01412. DOI: 10.48550/arXiv.1912.01412.

LeCun, Y., Bengio, Y., and Hinton, G. (2015). Deep learning. Nature, 521(7553):436. DOI: 10.1038/nature14539.

Levenshtein, V. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics doklady, 10(8):707-710. Available at:[link].

Li, Z., Liu, H., Zhou, D., and Ma, T. (2024). Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations. DOI: 10.48550/arXiv.2402.12875.

Lipton, Z. C., Berkowitz, J., and Elkan, C. (2015). A critical review of recurrent neural networks for sequence learning. arXiv preprint arXiv:1506.00019. DOI: 10.48550/arxiv.1506.00019.

Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. (2023). Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations. DOI: 10.48550/arXiv.2210.10749.

Maddison, C. and Tarlow, D. (2014). Structured generative models of natural source code. In International Conference on Machine Learning, pages 649-657. PMLR. DOI: 10.48550/arxiv.1401.0514.

Marcus, G. and Davis, E. (2019). Rebooting AI: Building artificial intelligence we can trust. Vintage. Book.

Michaelson, G. (2011). An Introduction to Functional Programming Through Lambda Calculus. Dover books on mathematics. Dover Publications. Book.

Mou, L., Li, G., Liu, Y., Peng, H., Jin, Z., Xu, Y., and Zhang, L. (2014). Building program vector representations for deep learning. arXiv preprint arXiv:1409.3358. DOI: 10.1007/978-3-319-25159-2_49.

Nicolau, M., Tavares, A. R., Zhang, Z., Avelar, P. H. C., Flach, J. M., Lamb, L. C., and Vardi, M. Y. (2025). Understanding boolean function learnability on deep neural networks: PAC learning meets neurosymbolic models. In Proceedings of The 19th International Conference on Neurosymbolic Learning and Reasoning NeSy 2025, PMLR, volume 284, pages 719-735. Available at:[link].

Peng, B., Narayanan, S., and Papadimitriou, C. (2024). On limitations of the transformer architecture. In First Conference on Language Modeling. DOI: 10.48550/arXiv.2402.08164.

Pierce, B. C. (2002). Types and programming languages. MIT press. Book.

Roose, K. (2022). The brilliance and weirdness of chatgpt. The New York Times. Available at:[link].

Rumelhart, D. E. and McClelland, J. L. (1986). Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1: Foundations. MIT Press. Book.

Russell, S. and Norvig, P. (2021). Artificial Intelligence A Modern Approach. DOI: 10.5555/773294.

Sutskever, I., Vinyals, O., and Le, Q. V. (2014). Sequence to sequence learning with neural networks. Advances in Neural Information Processing Systems, 4:3104-3112. DOI: 10.48550/arXiv.1409.3215.

Thompson, S. (2011). Haskell: the craft of functional programming. Addison-Wesley. Book.

Trask, A., Hill, F., Reed, S. E., Rae, J., Dyer, C., and Blunsom, P. (2018). Neural arithmetic logic units. Advances in neural information processing systems, 31. DOI: 10.48550/arXiv.1808.00508.

Valiant, L. (2018). What needs to be added to machine learning? In Proceedings of ACM Turing Celebration Conference - China, TURC '18, page 6, New York, NY, USA. Association for Computing Machinery. DOI: 10.1145/3210713.3210716.

Valiant, L. G. (2003). Three problems in computer science. J. ACM, 50(1):96–99. DOI: 10.1145/602382.602410.

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30. DOI: 10.48550/arXiv.1706.03762.

Zaremba, W. and Sutskever, I. (2014). Learning to execute. arXiv preprint arXiv:1410.4615. DOI: 10.48550/arXiv.1410.4615.

Zhang, H., Li, L. H., Meng, T., Chang, K.-W., and Van Den Broeck, G. (2023). On the paradox of learning to reason from data. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI '23. DOI: 10.24963/ijcai.2023/375.