- An identifier: Some collection of symbols not including dot or lambda
- A function expression: $\lambda x.expr$
- A function application: $f\text{}expr$

Expression

An expression is one of the following:

- An identifier: Some collection of symbols not including dot or lambda
- A function expression: $\lambda x.expr$
- A function application: $f\text{}expr$

Written as a grammar it looks like:

<expr> = x # IDENTIFIER | e1 e2 # application | λx . e # abstraction

In practice this means that if we see $(\lambda x.x)\text{}5$ it can be evaluated to $5$ .

That is to say that Lambda Calculus is concerned with denoting functions of one variable (or argument), and calling them with some value, we call the former an "abstraction" and the latter a function "application".

The semantics of lambda calculus use substitution to evaluate programs, given a function application, we first evaluate the expression on the right and suppose it evaluates to some value v, then we look in the body of the lambda, and recursively replace any instance of x with the value v, unless we hit another lambda which uses the same variable x, in that case we stop recursing there or if we find a value.

Lambda Evaluation of Euclidean Distance

Write down how lambda calculus would evaluate $$(((\lambda x.\lambda y.\sqrt{{x}^{2}+{y}^{2}})1+2)2+2)$$

Referential Transparency

An identifier is said to be referentially transparent if the identitifer can always be substituted for its definition without changing the programs behavior

Consider the following python code:

def not_good(x): x = x + 1 print(x) x = 3 not_good(x) ~> prints 4 print(x) ~> prints 3, because x was bound as a parameter (copy) --- (if we now replace the not_good function by it's body) x = 3 x += 1 ~> actually changed x... print(x) ~> 4 print(x) ~> 4 --- (another example would be datetime.now()) print(datetime.now()) ~> a print(datetime.now()) ~> b (where a < b)

Therefore the identifier `not_good`

is not referentially transparent. In pure functional languages, every identifier is referentially transparent. Which means that the value of a function application is independent of the context in which it occurs, and we know that the value of $f(a,b,c)$ only ever depends on the values of $f,a,b,c$.

This is beneficial if we wan to reason about programs, because no function ever has any side effects so there's no need to consider global state.