Lambda Calculus

6 Key excerpts on "Lambda Calculus"

• 

  eBook - ePub

  An Introduction to Functional Programming Through Lambda Calculus

  • Greg Michaelson(Author)
  • 2013(Publication Date)
  • Dover Publications

    (Publisher)

  The λ calculus was devised by Alonzo Church in the 1930s as a model for computability and has subsequently been central to contemporary computer science. It is a very simple but very powerful language based on pure abstraction. It can be used to formalize all aspects of programming languages and programming, and is particularly suited for use as a ‘machine code’ for functional languages and functional programming.

  In the rest of this chapter we are going to look at how λ calculus expressions are written and manipulated. This may seem a bit disjointed at first: it is hard to introduce all of a new topic simultaneously and so some details will be rather sketchy to begin with. A set of useful functions will be built up bit by bit. The functions introduced in this chapter to illustrate various aspects of λ calculus will be used as building blocks in later chapters. Each example may assume knowledge of previous examples and so it is important that you work through the material slowly and consistently.

  2.4 λ expressions

  The λ calculus is a system for manipulating λ expressions. A λ expression may be a name to identify an abstraction point, a function to introduce an abstraction or a function application to specialize an abstraction:

  A name may be any sequence of non-blank characters, for example: A λ function is an abstraction over a λ expression and has the form: where: for example:

  The λ precedes and introduces a name used for abstraction. The name is called the function’s bound variable and is like a formal parameter in a Pascal function declaration. The ‘.’ separates the name from the expression in which abstraction with that name takes place. This expression is called the function’s body.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Lectures on the Curry-Howard Isomorphism

  • Morten Heine Sørensen, Pawel Urzyczyn(Authors)
  • 2006(Publication Date)
  • Elsevier Science

    (Publisher)

  Chapter 1

  Type-free λ-calculus

  M.H. Sørensen; P. Urzyczyn

  The λ-calculus is a model of computation. It was introduced a few years before another such model, Turing machines . With the latter, computation is expressed by reading from and writing to a tape, and performing actions depending on the contents of the tape. Turing machines resemble programs in imperative programming languages, like Java or C.

  In contrast, in λ-calculus one is concerned with functions, and these may both take other functions as arguments, and return functions as results. In programming terms, λ-calculus is an extremely simple higher-order, functional programming language.

  In this chapter we only cover the type-free or untyped λ-calculus. Later we introduce several variants where λ-terms are categorized into various types .

  1.1 A gentle introduction

  Computation in λ-calculus is expressed with λ-terms . These are similar to the nameless function notation n  ↦ n 2 used in mathematics. However, a mathematician employs the latter notation to denote functions as mathematical objects (defined as sets of pairs). In contrast, λ-terms are formal expressions (strings) which, intuitively, express functions and applications of functions in a pure form. Thus, a λ-term is one of the following:

  •  

  a variable ;

  •  

  an abstraction λxM , where x is a variable and M is a λ-term;

  •  

  an application MN (of M to N )} where M and N are λ-terms.

  In an abstraction λxM , the variable x represents the function argument (or formal parameter ), and it may occur in the body M of the function, but it does not have to. In an application MN there is no restriction on the shape of the operator M or the argument N ; both can be arbitrary λ-terms.

  For instance, the λ-term I  = λxx intuitively denotes a function that maps any argument to itself, i.e. the identity function. As another example, K  = λx λyx represents a function mapping any argument x to the constant function that always returns x . Finally, IK expresses application of the function I to the argument K

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Alan Turing

  • S. Barry Cooper, J. van Leeuwen(Authors)
  • 2013(Publication Date)
  • Elsevier Science

    (Publisher)

  λ -Definability*

  Henk Barendregt, Giulio Manzonetto and Rinus Plasmeijer trace through to today — The Imperative and Functional Programming Paradigm

  (J. Symbolic Logic, vol. 2 (1937), p. 153–163)

  1 Models of computation

  In Turing (1936) a characterisation is given of those functions that can be computed using a mechanical device. Moreover it was shown that some precisely stated problems cannot be decided by such functions. In order to give evidence for the power of this model of computation, Turing (1937) showed that machine computability has the same strength as definability via λ -calculus, introduced in Church (1936) . This model of computation was also introduced with the aim of showing that undecidable problems exist.

  Turing machine computability forms a very simple model that is easy to mechanise. Lambda Calculus computability, on the other hand, is a priori more powerful. Therefore, it is not obvious that it can be executed by a machine. In showing the equivalence of both models, Turing shows us that λ -calculus computations are performable by a machine, so demonstrating the power of Turing machine computations. This gave rise to the combined

  Church-Turing Thesis The notion of intuitive computability is exactly captured by λ -definability or by Turing computability .

  Computability via Turing machines gave rise to imperative programming. Computability described via λ -calculus gave rise to functional programming. As imperative programmes are more easy to run on hardware, this style of software became predominant. We present major advantages of the functional programming paradigm over the imperative one, that are applicable, provided one is willing to explicitly deal with simple abstractions.

  2 Functional programming

  2.1 Features from Lambda Calculus

  Rewriting . Lambda terms form a set of formal expressions subjected to possible rewriting (or reduction

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Logic from Russell to Church

  • Dov M. Gabbay, John Woods(Authors)
  • 2009(Publication Date)
  • North Holland

    (Publisher)

  Lambda-Calculus and Combinators in the 20th Century

  Felice Cardone; J. Roger Hindley

  1 INTRODUCTION

  The formal systems that are nowadays called λ -calculus and combinatory logic were both invented in the 1920s, and their aim was to describe the most basic properties of function-abstraction, application and substitution in a very general setting. In λ -calculus the concept of abstraction was taken as primitive, but in combinatory logic it was defined in terms of certain primitive operators called basic combinators.

  The present article will sketch the history of these two topics, until approximately the year 2000.

  We shall assume the reader is familiar with at least one of the many versions of these systems in the current literature. A few key technical details will be given as footnotes, however.1 Often “combinatory logic” will be abbreviated to “CL” and “λ -calculus” to “λ ”. We shall distinguish between “pure” versions of λ or CL (theories of conversion or reduction with nothing more) and “applied” versions (containing extra concepts such as logical constants, types or numbers).

  To understand the early history it is worth remembering that the situation in logic and the foundations of mathematics was much more fluid in the early 1900s than it is today; Russell’s paradox was relatively recent, Gödel’s theorems were not yet known, and a significant strand of work in logic was the building of systems intended to be consistent foundations for the whole of mathematical analysis. Some of these were based on a concept of set, others on one of function, and there was no general consensus as to which basis was better. In this context λ and CL were originally developed, not as autonomous systems but as parts of more elaborate foundational systems based on a concept of function.

  Today, λ and CL are used extensively in higher-order logic and computing. Rather like the chassis of a bus, which supports the vehicle but is unseen by its users, versions of λ or CL underpin several important logical systems and programming languages. Further, λ

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Get Programming with Haskell

  • Will Kurt(Author)
  • 2018(Publication Date)
  • Manning

    (Publisher)

  Lambda Calculus. In Lambda Calculus, you represent everything as functions: true and false are functions, and even all the integers can be represented as functions.

  Church’s goal was initially to resolve some problems in the mathematical field of set theory. Unfortunately, Lambda Calculus didn’t solve these problems, but something much more interesting came out of Church’s work. It turns out that Lambda Calculus allows for a universal model of computation, equivalent to a Turing machine!

  What is a Turing machine?

  A Turing machine is an abstract model of a computer developed by the famous computer scientist Alan Turing. From a theoretical standpoint, the Turing machine is useful because it allows you to reason about what can and can’t be computed, not just on a digital computer, but any possible computer. This model also allows computer scientists to show equivalence between computing systems if they can each simulate a Turing machine. You can use this to show, for example, that there’s nothing that you can compute in Java that you can’t also compute in assembly language.

  This discovery of the relationship between Lambda Calculus and computing is called the Church-Turing thesis (for more information, see www.alanturing.net/turing_archive/pages/reference%20articles/The%20Turing-Church%20Thesis.html ). The wonderful thing about this discovery is that you have a mathematically sound model for programming!

  Most programming languages that you use are marvelous pieces of engineering but provide little assurance about how programs will behave. With a mathematical foundation, Haskell is able to remove entire classes of bugs and errors from the code you write. Cutting-edge research in programming languages is experimenting with ways to mathematically prove that programs will do exactly what you expect. Additionally, the nonmathematical nature of most programming language designs means the abstractions you can use are limited by engineering decisions in the language. If you could program math, you’d be able to both prove things about your code and have access to the nearly limitless abstractions that mathematics allows. This is the aim of functional programming: to bring the power of mathematics to the programmer in a usable way.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A++ and the Lambda Calculus

  Principles of Functional Programming

  • Georg P. Loczewski(Author)
  • 2018(Publication Date)
  • tredition

    (Publisher)

  XVI . The following phrase puts everything to a point:

  Abstraction is all there is to talk about: it is both the object and the means of discussion. Guy L. Steele Jr .

  ARS provides a base for imperative programming and object-oriented programming as well and can be applied to programming in almost any programming language.

  ARS , the basic operations of the Lambda Calculus in their generalized form are defined as follows:

  Abstraction: Give something a name.

  Reference: Reference an abstraction by name.

  Synthesis: Combine two or more abstractions to create something new.

  These operations may sound rather trivial and abstract but taken as principles of programming they change the style and method of programming thoroughly.

  The generalization of the Lambda Calculus consists in defining the concept of abstraction simply by ‘give something a name’. The name hides all the details of the defined. Abstraction thus defined requires an explicit definition of a name .

  The Lambda Calculus does not allow for an explicit definition of a name. The only possibility to associate a name to a value in the Lambda Calculus is by calling a function with an argument. This operation corresponds to the synthesis operation however and not to the creation of an abstraction. Lambda-abstractions in the Lambda Calculus are ‘per se’ anonymous.

  Sign up to read

  Learn more about book