lambda演算与函数式编程初见
Lambda Calculus
Programming with Math | The Lambda Calculus
Stanford Encyclopedia of Philosophy
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 | lambda x : lambda y : x + y) (1) (2) # pretty cool! ( |
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.