# Lambda Calculus: Lexical syntax

Lambda Calculus was invented by Alonzo Church as a formal system to model computations using functions to define abstractions and applications. It is the most simplest programming language.

### Lexical Syntax:

#### Symbols or keywords:

Lambda Calculus reserves very few symbols for use.

The Greek letter `λ`

has become the unofficial keyword to represent start of a function.

A dot `.`

is used to separate function parameter and function body.

Paratheses `()`

is optionally used to group function application.

#### Identifiers:

In Lambda Calculus, unlike other programming languages, any sequence of non-blank characters can be used as identifiers.

#### Lambda 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.

```
<expression> ::= <name> | <function> | <application>
```

A `name`

may be any sequence of non-blank characters.

`example: "lambda", "calculus", "10", "15", "+", "-->"`

##### Function:

A `λ function`

is an abstraction over a `λ expression`

.

```
<function> ::= λ<name>.<body>
```

`example: λx.x`

The above `λ expression`

is a function abstraction(or simply a function) generally knows as an `identity`

function which returns the parameter passed to the function.

The `x`

after the `λ`

represents the name of the parameter used in the function abstraction.
The `.`

after name `x`

separates it from the expression `x`

which is called function’s body.

The `<body>`

can be a `λ expression`

including another function or `function application`

.

```
<body> ::= <expression>
```

for example `λx.λy.x`

is a function where `λy.x`

is the function body which is another function.

###### Bound variable:

A function’s name is also called as the function’s `bound variable`

and it is like a parameter in a function.

##### Function Application:

A `function application`

has the following syntax:

```
<application> ::= (<function expression> <argument expression>)
```

where

```
<function expression> ::= <expression>
<argument expression> ::= <expression>
```

`example: (λx.x λa.λb.b)`

In a function application the function expression(or function abstraction) is *applied* to the argument expression.

There are two approaches to evaluate a function application, `applicative order`

and `normal order`

In `applicative order`

all occurrences of the function expression’s bound variable is replaced by the value of the argument expression.

In `normal order`

all occurrences of the function expression’s bound variable is replaced by unevaluated argument expression.

we will see more about functions and function applications in the next post