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

arXiv: https://arxiv.org/abs/2304.09276 · HTML: https://mlsanity.com/paper/2304.09276/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 18 Apr 2023.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neurosymbolic AI: The 3rd Wave](https://mlsanity.com/paper/2012.05876/) (2020)
- [A Critical Review of Recurrent Neural Networks for Sequence Learning](https://mlsanity.com/paper/1506.00019/) (2015)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [On the Paradox of Learning to Reason from Data](https://mlsanity.com/paper/2205.11502/) (2022)
- [Neural Arithmetic Logic Units](https://mlsanity.com/paper/1808.00508/) (2018)
- [Structured Generative Models of Natural Source Code](https://mlsanity.com/paper/1401.0514/) (2014)
- [Building Program Vector Representations for Deep Learning](https://mlsanity.com/paper/1409.3358/) (2014)
- [Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models](https://mlsanity.com/paper/2009.05908/) (2020)

## Built on by (most cited first, 2 of 2)

- [Neuro-Symbolic AI: Explainability, Challenges, and Future Trends](https://mlsanity.com/paper/2411.04383/) (2024)
- [Bridging the Gap: Representation Spaces in Neuro-Symbolic AI](https://mlsanity.com/paper/2411.04393/) (2024)

## Abstract (arXiv)

Over the last decades, deep neural networks based-models became the dominant paradigm in machine learning. Further, the use of artificial neural networks in symbolic learning has been seen as increasingly relevant recently. To study the capabilities of neural networks in the symbolic AI domain, researchers have explored the ability of deep neural networks to learn mathematical constructions, such as addition and multiplication, logic inference, such as theorem provers, and even the execution of computer programs. The latter is known to be too complex a task for neural networks. Therefore, the results were not always successful, and often required the introduction of biased elements in the learning process, in addition to restricting the scope of possible programs to be executed. In this work, we will analyze the ability of neural networks to learn how to execute programs as a whole. To do so, we propose a different approach. Instead of using an imperative programming language, with complex structures, we use the Lambda Calculus (λ-Calculus), a simple, but Turing-Complete mathematical formalism, which serves as the basis for modern functional programming languages and is at the heart of computability theory. We will introduce the use of integrated neural learning and lambda calculi formalization. Finally, we explore execution of a program in λ-Calculus is based on reductions, we will show that it is enough to learn how to perform these reductions so that we can execute any program. Keywords: Machine Learning, Lambda Calculus, Neurosymbolic AI, Neural Networks, Transformer Model, Sequence-to-Sequence Models, Computational Models