In lambda calculus, can the parameter of abstraction be a non-variable lambda expression?

225 Views Asked by At

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.

Question:
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?)

1

There are 1 best solutions below

1
On

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