Annexe
Syntaxe des lambda-termes :
<expr> ::= <var>
| <func> <arg> # Applications.
| lambda <var> . <expr> # Abstractions.
<func> ::= <var>
| (l <var> . <expr>)
| <func> <arg>
<arg> ::= <var>
| (lambda <var> . <expr>)
| (<func> <arg>)
<var> ::= a| b| .... | Z
<const> ::= 0 | ... | 9 | <const>+
Combinateur prédéfinis :
- I ≡ (lx.x) - Identité
- S ≡ (lxyz.(xz)(yz)) - Substitution
- B ≡ (lxyz.x(yz)) - Composition
- Y ≡ (lf.(lx.f(xx))(lx.f(xx))) - Point fixe
- K ou T ≡ (lxy.x) - Vrai
- F ≡ (lxy.y) - Faux
- J ≡ (labcd.ab(adc))
- C ≡ (lxyz.xzy)
Exemples