Lambda calculus (ConceptTopic, 3)

From Hi.gher. Space

(Difference between revisions)
(created page)
(add)
Line 11: Line 11:
Gives the same result as applying its parameter to itself.
Gives the same result as applying its parameter to itself.
*Symbol: <tt>ω</tt>
*Symbol: <tt>ω</tt>
-
*<tt>ωω = Ω</tt>
 
=== Omega ===
=== Omega ===
<[#img [hash 87N568B8CHQ9A153JJ2MR28KXE]]>
<[#img [hash 87N568B8CHQ9A153JJ2MR28KXE]]>
-
The result of applying the Mockingbird to itself. Note that this can't take any parameter, since its evaluation results in an infinite loop. Usually treated as "undefined" and is said to be related to infinity.
+
The result of applying the Mockingbird to itself. Also the result of applying the Why bird to the Identity bird. Note that this can't take any parameter, since its evaluation results in an infinite loop. Usually treated as "undefined" and is said to be related to infinity.
*Symbol: <tt>Ω</tt>
*Symbol: <tt>Ω</tt>
Line 24: Line 23:
A fixed-point combinator. Returns a value which remains the same when transformed under the original parameter.
A fixed-point combinator. Returns a value which remains the same when transformed under the original parameter.
*Symbol: <tt>Y</tt>
*Symbol: <tt>Y</tt>
-
*<tt>YI = Ω</tt>
 
=== Kestrel ===
=== Kestrel ===
Line 78: Line 76:
*Symbol: <tt>CW</tt>
*Symbol: <tt>CW</tt>
 +
 +
== Advanced ==
 +
=== Turing ===
 +
<[#img [hash 9SBSCKZYSH5H2SKRBQR2WSDHJ9]]>
 +
 +
Applying the Turing bird to itself gives you the Theta bird, which is a fixed-point combinator similar to the Omega bird.
 +
*Symbol: <tt>U</tt>
 +
 +
=== Cardinal ===
 +
<[#img [hash F8EYE3D85KXRCFP0M0A9GXA2ZE]]>
 +
 +
Returns the "crossed" version of its parameter, hence why "crossed" birds are usually written as <tt>Cx</tt>.
 +
*Symbol: <tt>C</tt>
 +
 +
=== Bluebird ===
 +
<[#img [hash THPPRVGQXHP5MKXT4T35E3CHS3]]>
 +
 +
Returns the composition of its two parameters ''a'' and ''b'', i.e. when the result is applied to a further parameter ''c'', its result is the same as applying ''b'' to ''c'' and then applying ''a'' to that. (Notice that the order of the parameters may seem backwards.)
 +
*Symbol: <tt>B</tt>
 +
 +
=== Vireo ===
 +
<[#img [hash 67P3MC3C8B8CMN562XVGED3DCP]]>
 +
 +
*Symbol: <tt>V</tt>
 +
 +
=== Robin ===
 +
<[#img [hash R4VDG4KSMZW1MK30CYAKW5QA80]]>
 +
 +
*Symbol: <tt>R</tt>
 +
 +
=== Starling ===
 +
<[#img [hash WDCHY1GNTD4DT5T2SK1EPVWR1R]]>
 +
 +
All birds can be derived from some combination of [[#Kestrel|Kestrels]] and Starlings. Roughly, the Kestrel "destroys", while the Starling "creates".
 +
*Symbol: <tt>S</tt>
 +
 +
=== Jay ===
 +
<[#img [hash XRP2WSJADQB022EMPEEHM6M7FM]]>
 +
 +
Similar to the Starling. All birds, except those which ignore some of their parameters, can be derived from some combination of [[#Identity, "Idiot"|Idiots]] and Jays.
 +
*Symbol: <tt>J</tt>
 +
 +
== Starling-Kestrel constructions ==
 +
 +
I = SKK
 +
B = S(KS)K
 +
C = S(BBS)(KK)
 +
 +
O = SI
 +
W = CSI
 +
 +
V = BCT
 +
 +
== Jay-Idiot constructions ==
 +
 +
T = JII
 +
R = JT
 +
C = RRR
 +
B = C(JIC)(JI)
 +
ω = C(C(C(BJT)T)T)T
 +
W = C(BωR)
 +
S = B(BW)(BBC)
 +
 +
== Logic ==
 +
 +
true = K
 +
false = KI
 +
not = V false true
 +
implies = R true
 +
and = R false
 +
or = T true
 +
equiv = CS not
 +
 +
== Arithmetic ==
 +
 +
zero = I
 +
succ = V false
 +
pred = T false
 +
isZero = T true
 +
 +
== External links ==
 +
*[http://dkeenan.com/Lambda/ To Dissect a Mockingbird]

Revision as of 22:31, 24 April 2012

Basic

Identity, "Idiot"

ExPar: [#img] is obsolete, use [#embed] instead

Always returns its parameter.

  • Symbol: I

Mockingbird

ExPar: [#img] is obsolete, use [#embed] instead

Gives the same result as applying its parameter to itself.

  • Symbol: ω

Omega

ExPar: [#img] is obsolete, use [#embed] instead

The result of applying the Mockingbird to itself. Also the result of applying the Why bird to the Identity bird. Note that this can't take any parameter, since its evaluation results in an infinite loop. Usually treated as "undefined" and is said to be related to infinity.

  • Symbol: Ω

Why

ExPar: [#img] is obsolete, use [#embed] instead

A fixed-point combinator. Returns a value which remains the same when transformed under the original parameter.

  • Symbol: Y

Kestrel

ExPar: [#img] is obsolete, use [#embed] instead

Always returns the first of two parameters (and ignores the second). Usually treated as "true".

  • Symbol: K

Kite

ExPar: [#img] is obsolete, use [#embed] instead

Always returns the second of two parameters (and ignores the first). Usually treated as "false".

  • Symbol: KI (because it is the result of applying the Kestrel to the Identity).

Identity once removed

ExPar: [#img] is obsolete, use [#embed] instead

By definition, it gives the same result as applying the first parameter to the second. Alternatively, when called with one parameter it returns that parameter... unless I'm missing something. So what would make it any more worthwhile using than the ordinary Identity bird?

  • Symbol: I* or CT (because it is technically the crossed Thrush, see below).

Thrush

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: T

Konstant Mocker

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol:

Crossed Konstant Mocker

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: C(Kω)

Lark

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: L

Owl

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: O

Warbler

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: W

Crossed Warbler

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: CW

Advanced

Turing

ExPar: [#img] is obsolete, use [#embed] instead

Applying the Turing bird to itself gives you the Theta bird, which is a fixed-point combinator similar to the Omega bird.

  • Symbol: U

Cardinal

ExPar: [#img] is obsolete, use [#embed] instead

Returns the "crossed" version of its parameter, hence why "crossed" birds are usually written as Cx.

  • Symbol: C

Bluebird

ExPar: [#img] is obsolete, use [#embed] instead

Returns the composition of its two parameters a and b, i.e. when the result is applied to a further parameter c, its result is the same as applying b to c and then applying a to that. (Notice that the order of the parameters may seem backwards.)

  • Symbol: B

Vireo

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: V

Robin

ExPar: [#img] is obsolete, use [#embed] instead

  • Symbol: R

Starling

ExPar: [#img] is obsolete, use [#embed] instead

All birds can be derived from some combination of Kestrels and Starlings. Roughly, the Kestrel "destroys", while the Starling "creates".

  • Symbol: S

Jay

ExPar: [#img] is obsolete, use [#embed] instead

Similar to the Starling. All birds, except those which ignore some of their parameters, can be derived from some combination of Idiots and Jays.

  • Symbol: J

Starling-Kestrel constructions

I = SKK
B = S(KS)K
C = S(BBS)(KK)

O = SI
W = CSI

V = BCT

Jay-Idiot constructions

T = JII
R = JT
C = RRR
B = C(JIC)(JI) 
ω = C(C(C(BJT)T)T)T
W = C(BωR)
S = B(BW)(BBC)

Logic

true = K
false = KI
not = V false true
implies = R true
and = R false
or = T true
equiv = CS not

Arithmetic

zero = I
succ = V false
pred = T false
isZero = T true

External links