Question

Lambda term can be:

  • variable
  • lambda abstraction (for example \x.t)
  • application. If t and s are lambda terms, then ts is an application.

So, application with abstraction in the left part (for example (\x.t)a) looks good. It looks like function calling. But what does application mean when left part is a variable or other application? What does mean ab, ((\x.x)a)b or a(\x.x) if a and b are variables?

Was it helpful?

Solution

((\x.x)b)c is a function application. Here It applies b to c.

((\x.x)b)c
= bc

a(\x.y) is a function application, applying the function a to its sole argument, which happens to be a function, namely the function that returns y (a free variable).

One of the featues of the lamdba calculus is the ease in which functions can be applied to functions and functions can take other functions as arguments. Your two examples show both cases nicely.

EDIT There are (at least) two versions of the lambda calculus: the untyped and the typed. In the untyped calculus, which you are using here, anything can be applied to anything. In the typed calculus there exist base types which are not functions, such as the type of propositions and the type of "individuals." So you would only be able to write ab if the type of a were a function type mapping the type of b to something.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top