Lambda calculus (ConceptTopic, 3)

From Hi.gher. Space

(Difference between revisions)
(add)
m (ontology)
 
(6 intermediate revisions not shown)
Line 1: Line 1:
 +
<[#ontology [kind topic] [cats Essays]]>
== Basic ==
== Basic ==
=== Identity, "Idiot" ===
=== Identity, "Idiot" ===
-
<[#img [hash VBA4W3DCY8G6JSK22VNSE5EQ2T]]>
+
<[#embed [hash VBA4W3DCY8G6JSK22VNSE5EQ2T]]>
Always returns its parameter.
Always returns its parameter.
Line 7: Line 8:
=== Mockingbird ===
=== Mockingbird ===
-
<[#img [hash KNBVGH2GH9JFP7FJAKZ1MNXTTC]]>
+
<[#embed [hash KNBVGH2GH9JFP7FJAKZ1MNXTTC]]>
Gives the same result as applying its parameter to itself.
Gives the same result as applying its parameter to itself.
Line 13: Line 14:
=== Omega ===
=== Omega ===
-
<[#img [hash 87N568B8CHQ9A153JJ2MR28KXE]]>
+
<[#embed [hash 87N568B8CHQ9A153JJ2MR28KXE]]>
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.
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.
Line 19: Line 20:
=== Why ===
=== Why ===
-
<[#img [hash K4Y66VZRXZYSC9EBJAC2AG7JEH]]>
+
<[#embed [hash K4Y66VZRXZYSC9EBJAC2AG7JEH]]>
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.
Line 25: Line 26:
=== Kestrel ===
=== Kestrel ===
-
<[#img [hash 6FP9RBVYK6NYR98EZEJ7A4YF82]]>
+
<[#embed [hash 6FP9RBVYK6NYR98EZEJ7A4YF82]]>
Always returns the first of two parameters (and ignores the second). Usually treated as "true".
Always returns the first of two parameters (and ignores the second). Usually treated as "true".
Line 31: Line 32:
=== Kite ===
=== Kite ===
-
<[#img [hash VYZSM5HM5Y7JMC1WKZ28GEM855]]>
+
<[#embed [hash VYZSM5HM5Y7JMC1WKZ28GEM855]]>
Always returns the second of two parameters (and ignores the first). Usually treated as "false".
Always returns the second of two parameters (and ignores the first). Usually treated as "false".
Line 37: Line 38:
=== Identity once removed ===
=== Identity once removed ===
-
<[#img [hash 4Q8G0FE60TQEJ40ME48WRBYAMJ]]>
+
<[#embed [hash 4Q8G0FE60TQEJ40ME48WRBYAMJ]]>
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?
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?
Line 43: Line 44:
=== Thrush ===
=== Thrush ===
-
<[#img [hash QTREJ2F8BSPE4A1BRF8EJS0PAP]]>
+
<[#embed [hash QTREJ2F8BSPE4A1BRF8EJS0PAP]]>
*Symbol: <tt>T</tt>
*Symbol: <tt>T</tt>
=== Konstant Mocker ===
=== Konstant Mocker ===
-
<[#img [hash ZWVB2N9ZYNMRWWKG5HS9CRTNT2]]>
+
<[#embed [hash ZWVB2N9ZYNMRWWKG5HS9CRTNT2]]>
*Symbol: <tt>Kω</tt>
*Symbol: <tt>Kω</tt>
=== Crossed Konstant Mocker ===
=== Crossed Konstant Mocker ===
-
<[#img [hash FGXNRC7V24842427PMCWTXM478]]>
+
<[#embed [hash FGXNRC7V24842427PMCWTXM478]]>
*Symbol: <tt>C(Kω)</tt>
*Symbol: <tt>C(Kω)</tt>
=== Lark ===
=== Lark ===
-
<[#img [hash A0Y9R259YZ6ARK2ECSJNWAZHD5]]>
+
<[#embed [hash A0Y9R259YZ6ARK2ECSJNWAZHD5]]>
*Symbol: <tt>L</tt>
*Symbol: <tt>L</tt>
=== Owl ===
=== Owl ===
-
<[#img [hash Q2F0T7XFZMYQY6ZYWYNYPETKF6]]>
+
<[#embed [hash Q2F0T7XFZMYQY6ZYWYNYPETKF6]]>
*Symbol: <tt>O</tt>
*Symbol: <tt>O</tt>
=== Warbler ===
=== Warbler ===
-
<[#img [hash ETTHR645DPVMP2XVNF2NWQ7SB1]]>
+
<[#embed [hash ETTHR645DPVMP2XVNF2NWQ7SB1]]>
*Symbol: <tt>W</tt>
*Symbol: <tt>W</tt>
=== Crossed Warbler ===
=== Crossed Warbler ===
-
<[#img [hash CAFXG11Y1MKPYPT0N62XJ4JCBY]]>
+
<[#embed [hash CAFXG11Y1MKPYPT0N62XJ4JCBY]]>
*Symbol: <tt>CW</tt>
*Symbol: <tt>CW</tt>
Line 79: Line 80:
== Advanced ==
== Advanced ==
=== Turing ===
=== Turing ===
-
<[#img [hash 9SBSCKZYSH5H2SKRBQR2WSDHJ9]]>
+
<[#embed [hash 9SBSCKZYSH5H2SKRBQR2WSDHJ9]]>
-
Applying the Turing bird to itself gives you the Theta bird, which is a fixed-point combinator similar to the Omega bird.
+
Applying the Turing bird to itself gives you the Theta bird, which is a fixed-point combinator similar to the [[#Why|Why]] bird.
*Symbol: <tt>U</tt>
*Symbol: <tt>U</tt>
=== Cardinal ===
=== Cardinal ===
-
<[#img [hash F8EYE3D85KXRCFP0M0A9GXA2ZE]]>
+
<[#embed [hash F8EYE3D85KXRCFP0M0A9GXA2ZE]]>
Returns the "crossed" version of its parameter, hence why "crossed" birds are usually written as <tt>Cx</tt>.
Returns the "crossed" version of its parameter, hence why "crossed" birds are usually written as <tt>Cx</tt>.
Line 91: Line 92:
=== Bluebird ===
=== Bluebird ===
-
<[#img [hash THPPRVGQXHP5MKXT4T35E3CHS3]]>
+
<[#embed [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.)
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.)
Line 97: Line 98:
=== Vireo ===
=== Vireo ===
-
<[#img [hash 67P3MC3C8B8CMN562XVGED3DCP]]>
+
<[#embed [hash 67P3MC3C8B8CMN562XVGED3DCP]]>
*Symbol: <tt>V</tt>
*Symbol: <tt>V</tt>
=== Robin ===
=== Robin ===
-
<[#img [hash R4VDG4KSMZW1MK30CYAKW5QA80]]>
+
<[#embed [hash R4VDG4KSMZW1MK30CYAKW5QA80]]>
*Symbol: <tt>R</tt>
*Symbol: <tt>R</tt>
=== Starling ===
=== Starling ===
-
<[#img [hash WDCHY1GNTD4DT5T2SK1EPVWR1R]]>
+
<[#embed [hash WDCHY1GNTD4DT5T2SK1EPVWR1R]]>
All birds can be derived from some combination of [[#Kestrel|Kestrels]] and Starlings. Roughly, the Kestrel "destroys", while the Starling "creates".
All birds can be derived from some combination of [[#Kestrel|Kestrels]] and Starlings. Roughly, the Kestrel "destroys", while the Starling "creates".
Line 113: Line 114:
=== Jay ===
=== Jay ===
-
<[#img [hash XRP2WSJADQB022EMPEEHM6M7FM]]>
+
<[#embed [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.
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.
Line 138: Line 139:
  W = C(BωR)
  W = C(BωR)
  S = B(BW)(BBC)
  S = B(BW)(BBC)
 +
 +
== Application of one parameter ==
 +
*Each table cell is the result of applying the bird '''at the top of its column''' to the bird '''at the start of its row'''.
 +
{| class='wikitable'
 +
!&nbsp;||Y||T||L||O||W||U||B||V||R||S||J
 +
|-
 +
!I
 +
|Ω||I*||ω||ω||ω||ω||I*||'''R'''||I**||'''O'''||?
 +
|-
 +
 +
|Ω||?||Ω||?||?||?||?||?||?||?||?
 +
|-
 +
!K
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!Y
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!T
 +
|?||?||?||?||?||?||?||?||?||?||'''R'''
 +
|-
 +
!L
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!O
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!W
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!U
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!B
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!V
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!R
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!S
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|-
 +
!J
 +
|?||?||?||?||?||?||?||?||?||?||?
 +
|}
== Logic ==
== Logic ==

Latest revision as of 23:27, 11 February 2014

Basic

Identity, "Idiot"

(image)

Always returns its parameter.

  • Symbol: I

Mockingbird

(image)

Gives the same result as applying its parameter to itself.

  • Symbol: ω

Omega

(image)

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

(image)

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

  • Symbol: Y

Kestrel

(image)

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

  • Symbol: K

Kite

(image)

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

(image)

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

(image)

  • Symbol: T

Konstant Mocker

(image)

  • Symbol:

Crossed Konstant Mocker

(image)

  • Symbol: C(Kω)

Lark

(image)

  • Symbol: L

Owl

(image)

  • Symbol: O

Warbler

(image)

  • Symbol: W

Crossed Warbler

(image)

  • Symbol: CW

Advanced

Turing

(image)

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

  • Symbol: U

Cardinal

(image)

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

  • Symbol: C

Bluebird

(image)

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

(image)

  • Symbol: V

Robin

(image)

  • Symbol: R

Starling

(image)

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

  • Symbol: S

Jay

(image)

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)

Application of one parameter

  • Each table cell is the result of applying the bird at the top of its column to the bird at the start of its row.
 YTLOWUBVRSJ
I ΩI*ωωωωI*RI**O?
ω Ω?Ω????????
K ???????????
Y ???????????
T ??????????R
L ???????????
O ???????????
W ???????????
U ???????????
B ???????????
V ???????????
R ???????????
S ???????????
J ???????????

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