Beregnbarhet og implementasjon : - aspekter ved funksjonelle språk

Abstract

In this master thesis we investigate lambda calculus and the theory of combinatory logic. Two computational models strongly related to functional programming languages. The lambda calculus is a theoretical foundation and a framework for describing functions and their evaluation. The theory of combinatory logic can be viewed a theory of computation based on a notation that eliminates the need for variables in applications. We also study Lisp, the SECD-machine and graph reduction, highlighting how the theoretical findings from lambda calculus and combinatory logic is used in programming languages and program execution.