In short, my main confusion is between the two concept variable and lambda expression:

I am reading this reference here:

The syntax of (pure) lambda expressions is defined as follows:

  1. A variable is a lambda expression (we will use single, lower-case letters for variables).
  2. If M and N are lambda expressions, then so are each of the following:

    a) (M)
    b) λid.M
    c) MN

We can express the rules given above that define the language of lambda expressions using a context-free grammar: exp → ID | ( exp ) | λ ID . exp // abstraction | exp exp // application

From rule #1 and the context-free grammar, I think the author means that ID refers to variable, and variable ∈ lambda expression. But I am not sure whether lambda expression ∈ variable.

May I know whether I can use a "complex" expressions (e.g. a non-variable lambda expression) as id in λid.M? Intuitively, I interpret variable represented by an ID with a single letter, but I could not find reference to support my conjecture. (or in other words, how is variable defined in lambda calculus, if this is not too broad a question?)


migrated from mathematica.stackexchange.com Aug 25 '14 at 4:39

This question came from our site for users of Wolfram Mathematica.

  • 2
    $\begingroup$ The phrase “A variable is a lambda expression” follows the same pattern as “a fish is an animal” or “burglary is a crime”. It does not assert that the two things are the same. $\endgroup$ – MJD Aug 25 '14 at 14:07
  • 1
    $\begingroup$ "ID" here is an abbreviation for "identifier", which is computer science jargon for "variable name". The idea here is that we have some collection of variable names (“identifiers”) already, and a λ-expression can be either a simple variable, or something in one of the three more complex forms given. For example, supposing that a and b are variables, then λa.b and λa.(a a) are λ-expressions. $\endgroup$ – MJD Aug 28 '14 at 17:23

No, it cannot. Variables are lambda expressions, but not all lambda expressions are variables. You may, however, compose functions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.