Lambda Calculus

我的最爱Lambda演算

A Combinatory Compiler

Programming with Math | The Lambda Calculus

Stanford Encyclopedia of Philosophy

Y Combinator

Core

Syntax:

  • Variables: $x$, $y$, $*$, …

  • Lambda-Abstractions: $\lambda x.M$

  • Applications: $M\ M$

Computation( Beta Reduction ): $(\lambda x.M)\ N \rightarrow_\beta M[N/x]$

Higher-order: Functions can be passed as inputs to functions, and equally functions can return functions as an output.

$\alpha$-Reduction: $\lambda x.x\Leftrightarrow\lambda y.y$

$\eta$-Reduction: $\lambda x.(f\ x)\Leftrightarrow f$

Currying

A function takes two numbers and return sum of them:

This method funtion returning funtions to sequentially apply to multiple inputs called Currying.

For example, in Python:

1
2
>>> (lambda x : lambda y : x + y) (1) (2) # pretty cool!
3

More Practical Example

Curry Numerals

Worth it?

Ignore low level implementation, and just overdeal objects themselves.

Functional Programming

A functional program consists of an expression $E$ (representing both the algorithm and the input). This expression $E$ is subject to some rewrite rules. Reduction consists of replacing some part $P$ of $E$ by another expression $P’$ according to the given rewrite rules. … This process of reduction will be repeated until the resulting expression has no more parts that can be rewritten. The expression $E^$ thus obtained is called the *normal form of $E$ and constitutes the output of the functional program

                                              -H. P. Barendregt

Functional programming is characterized by the programming with values, functions and functional forms.

Keywords and phrases: Lambda calculus, free and bound variables, scope, environment, functional programming, combinatorial logic, recursive functions, functional, curried function.ds and phrases: Lambda calculus, free and bound variables, scope, environment, functional programming, combinatorial logic, recursive functions, functional, curried function.