CODEWITHSUNDEEP
variableslambda-calculus
modeller
modeller

Reputation: 3850

In lambda calculus, can variable be expression in general?

For better understanding of functional programming, I am reading the wiki page for lambda calculus here.

The definition says:

If x is a variable and M ∈ Λ, then (λx.M) ∈ Λ

Intuitively I thought variable are / represented by single-letter id's. But since here we deal with strict math definitions, I just want to double confirm this understanding: in general, can expression be classified as variable?

e.g. if x is a variable, is expression (x + x) a variable in lambda calculus? i.e. is it ok to write (λ(x+x).M) as an lambda calculus abstraction?

(Concern is in some context this is true. e.g. Here: An expression such as 4x^3 is a variable)

Upvotes: 0

Views: 113

Answers (1)

Random Dev
Random Dev

Reputation: 52290

No, (x + x) is no variable (indeed it's not even a expression in naive lambda calculus). I think you mix the terms variables and expressions somehow (or want some kind of pattern-matching?).

So let's follow the core-definition of lambda-calculus and expressions:

The definition itself is not that hard (indeed you linked it yourself with the wiki-page). It's mentioned right from the start:

  • you have a set of variables V: (v_1, v_2, ...) (of course you can name them as you want - it's only important that you remmber that these are considered different symbols in your calculus)
  • the symbols λ, ., ( and )

This is it - thats all of the "Tokens" for this grammar/calculus.

Now there are a couple of rules how you can form Expressions from these:

  • each Variable is a expression
  • Abstraction: if E is a expression and x is a Variable then (λx.E) is a expression (here x and E are templates or Metavariables - you have to fill them with some real Expression to make this an Expression!)
  • Application: if A and B are expressions than (A B) is a expression.

So possible expressions are:

  • v_50
  • (λv_4.v_5)
  • ((λv_4.v_5) v_50)
  • ....

This is all when it comes to expressions.

You see: if you don't allow (x+x) as a symbol or name for a variable from the start it can never be a variable - indeed no expression is a variable even if there are some expressions consisting only of one said variable - if you called something expression it will never be a variable (again) ;)

PS: of course there are a couple of conventions to keep the parentheses a bit down - but for a start you don't need those.

Upvotes: 1

Related Questions