LAMBDA CALCULUS TERM REDUCTION: EVALUATING LLMS' PREDICTIVE CAPABILITIES

Abstract

This study is part of a research series of optimizing compilers and interpreters of functional programming languages. Lambda Calculus was chosen as the most straightforward functional programming language, which can process any operation available to other functional programming languages but with the simplest syntax. Using machine learning methods allows for uncovering relations inside lambda terms, which might indicate which reduction strategy better suits their reduction. Finding those techniques for lambda terms allows optimizing not only lambda term reduction but also interpreters and compilers of functional programming languages. This research aims to scrutinize LLMs' understanding of Lambda term reduction to predict reduction steps and evaluate prediction accuracy. Artificially generated Lambda terms were employed Utilizing OpenAI's GPT-4 and GPT-3.5 models. However, due to model constraints and cost considerations, experiments were limited to terms with specific token counts. Despite its larger size, results revealed that the GPT-4 model did not significantly outperform GPT-3.5 in understanding reduction procedures. Moreover, while the GPT-3.5 model exhibited improved accuracy with reduced token counts, its performance with more complex prompts was suboptimal. This underscores the LLMs' limitations in grasping Lambda terms and reduction strategies, especially with larger and more intricate terms. Conclusions. The research concludes that general-purpose LLMs like GPT-3.5 and GPT-4 are inadequate for accurately predicting Lambda term reductions and distinguishing between strategies, particularly with larger terms. While fine-tuning may enhance model performance, the current findings highlight the need for further exploration and alternative approaches to achieve a deeper understanding of lambda term reduction using LLMs.