Skip to content
This repository
Newer
Older
100644 657 lines (387 sloc) 31.604 kb
8385e4e8 »
2008-11-12
1 Bruno Marchal's Combinator Chemistry
8b0099db »
2008-11-13 updated with first post text
2 ===
b054a07e »
2008-11-11 a link page for Bruno Marchal's Combinator Chemistry posts
3
4 ![Bruno Marchal](http://iridia.ulb.ac.be/~marchal/courses/Saturday_20070602_LNash/t_blackboard_1.png)
5
ecb6be8a »
2008-11-15 better to put the links up top
6 [Bruno Marchal](http://iridia.ulb.ac.be/~marchal/ "Bruno Marchal’s Home Page") wrote up a concise and challenging introduction to combinatory logic, in the form of a series of emails:
b054a07e »
2008-11-11 a link page for Bruno Marchal's Combinator Chemistry posts
7
ecb6be8a »
2008-11-15 better to put the links up top
8 1. [COMBINATORS I](http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html)
9 2. [COMBINATORS II](http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html)
10 3. [COMBINATORS III](http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html)
11 4. [COMBINATORS IV](http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html)
12 5. [COMBINATORS V](http://www.mail-archive.com/everything-list@eskimo.com/msg05955.html)
13 6. [COMBINATORS VI](http://www.mail-archive.com/everything-list@eskimo.com/msg05957.html)
14 7. [COMBINATORS VIII](http://www.mail-archive.com/everything-list@eskimo.com/msg05959.html)
15
16 (There is no VII, to the best of my knowledge, it was combined with VI.)
17
18 The texts are reproduced below with Bruno's permission. I have added some wikipedia links to the introduction. Any brilliance is his, any errors are mine. I will post more as I find time.
b054a07e »
2008-11-11 a link page for Bruno Marchal's Combinator Chemistry posts
19
cb92b9f8 »
2008-11-15 all texts now reproduced
20 [COMBINATORS I](http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html): The Chemistry of Combinators
b054a07e »
2008-11-11 a link page for Bruno Marchal's Combinator Chemistry posts
21 ---
22
8b0099db »
2008-11-13 updated with first post text
23 Hi,
24
25 For those who are interested in the comp hypothesis, it is hardly a luxury to dig a little bit in computer science. If only to go toward explicit definition of notion like computations, computational history, consistent extensions, models, etc. I open this thread for the very long term.
26
27 One of the jewel of computer science is the theory of [combinators](http://en.wikipedia.org/wiki/Combinators "Combinatory logic - Wikipedia, the free encyclopedia").
28
29 They have been discovered and presented in a talk by [Moses Schoenfinkel](http://en.wikipedia.org/wiki/Schoenfinkel "Moses Schönfinkel - Wikipedia, the free encyclopedia") (from Moscow) in 1920. And rediscovered independently by [Haskell Curry](http://en.wikipedia.org/wiki/Haskell_Curry "Haskell Curry - Wikipedia, the free encyclopedia") (USA) in 1930. [Church](http://en.wikipedia.org/wiki/Alonzo_Church "Alonzo Church - Wikipedia, the free encyclopedia") rediscovered them too under the form of closed lambda _expression_, for which he will postulate his famous "Church thesis": the closed lambda _expression_ are enough to define all computable functions (from N to N, where N = the set of positive integers).
30
31 There is no "Schoenfinkel thesis" nor any "Curry thesis", as opposed to "Church thesis". Indeed the goal of both Schoenfinkel and Curry was to "rebuild" an alternative to the whole of mathematics. One of Schoenfinkel's motivation was to eliminate all variables. Curry's motivation was to find the most elementary finitary operations rich enough to (re)build mathematics, and this preferably without formal sets, but only a finite set of primitive operations.
32
33 Actually Combinatory Logic can "easily" be shown rich enough to represent the partial recursive function, so that the combinators gives a nice and pleasant computer programming language. (And indeed LISP and functionnal programming languages are all descendants or cousins of the combinators/lambda calculus). But at some fundamental level combinatory logic is much more than a programming language: it is really a possible road to tackle the problem of the nature of mathematics, and with comp: the nature of reality. Also, combinatory logic is very fine grained, and this will enable us to introduce at a very cheap price important nuances.
34
ecb6be8a »
2008-11-15 better to put the links up top
35 Here is a short description of combinatory logic (beware: in the preceding post I made a typo error):
8b0099db »
2008-11-13 updated with first post text
36
37 STATIC:
38
39 1. K is a molecule (called the "kestrel" is Smullyan's terminology)
40 2. S is a molecule (the "Starling")
41 3. if x and y are molecules then (x y) is a molecule. From this you can easily enumerate all possible molecules: K, S, (K K), (K S), (S K), (S S), ((K K) K), ((K S) K) ...
42
43 DYNAMICS: (X and Y are put for any molecules)
44
45 1. ((K X) Y) = X (Law of the Kestrel)
46 2. (((S X) Y) Z) = ((X Z) (Y Z)) (Law of the Starling)
47
48 1) means that on any molecules X the molecules (K X) is stable and does not evolves (except by the evolution of X perhaps). I will say that a molecules of the shape (K X) is a charged Kestrel.
49 Now if (K X) comes to interact with some other molecules Y giving ((K X) Y) you get an explosion leaving as result of the reaction just the molecule X.
50
51 So for example:
52
bead294a »
2008-11-13 second post up
53 K is stable
54 (K K) is stable
55 (K (K K)) is stable
56 ((K K) K) is unstable, indeed it matches the law "1)", with X = K, and Y = K, so the reaction is trigged giving K.
8b0099db »
2008-11-13 updated with first post text
57
bead294a »
2008-11-13 second post up
58 ((K (K K)) (K K)) gives (K K), ok?
8b0099db »
2008-11-13 updated with first post text
59
60
61
62 Well the price of having a conceptually very simple syntax (static) is that the notation can be very quickly a little bit cumbersome. The tradition is to neglect the left parenthesis abbreviating
63 (((a b) c) d) by abcd. The laws becomes:
64
bead294a »
2008-11-13 second post up
65 KXY = X
66 SXYZ = XZ(YZ)
8b0099db »
2008-11-13 updated with first post text
67
68 The examples becomes
69
bead294a »
2008-11-13 second post up
70 K is stable
71 KK is stable
72 K(KK) is stable
73 KKK is unstable and "decays" into K, and finally
8b0099db »
2008-11-13 updated with first post text
74
bead294a »
2008-11-13 second post up
75 K(KK)(KK) gives (KK) ok?
8b0099db »
2008-11-13 updated with first post text
76
77 What gives S(KK)(KK) ? Solution: it remains S(KK)(KK). It is stable because S needs "three" molecules to trigger its dynamic. So S(KK)(KK)(KK) gives KK(KK)(KK(KK)), as SKKK gives KK(KK) which is still unstable and gives K.
78
79 Exercises (Taken from the course "My First Everything Theory" Primary school Year 2127 :)
80
81 Evaluate:
82
bead294a »
2008-11-13 second post up
83 (SS)KKK = ?
84 KKK(SS) = ?
85 (KK)(KK)(KK) = ?
86 (KKK)(KKK)(KKK) = ?
8b0099db »
2008-11-13 updated with first post text
87
88 Evaluate:
89
bead294a »
2008-11-13 second post up
90 K
91 KK
92 KKK
93 KKKK
94 KKKKK
95 KKKKKK
96 KKKKKKK
97 KKKKKKKK
98 KKKKKKKKK
99 KKKKKKKKKK
8b0099db »
2008-11-13 updated with first post text
100
101 A little more advanced exerciaes: is there a molecule, let us called it I, having the following dynamic: (X refers to any molecule).
102
bead294a »
2008-11-13 second post up
103 IX = X
8b0099db »
2008-11-13 updated with first post text
104
105 So a solution is some molecule made up from K and S which applied on any molecule give as result of the reaction that very molecule unchanged.
106
107 For example KXS is not a solution, although it gives X, it is not of the shape (molecule X).
108
109
110 Of course you can learn a lot by searching "combinators" or "lambda calcul" on the net. Two samples: For those "who knows", [here is a paper on Kolmogorov Complexity viewed through the combinators](http://homepages.cwi.nl/~tromp/cl/CL.pdf). It can be used as a quick introduction to combinators.
111
cb92b9f8 »
2008-11-15 all texts now reproduced
112 [COMBINATORS II](http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html) (solution of exercises)
bead294a »
2008-11-13 second post up
113 ---
114
115 I recall all you need to know:
116
117
118 Kxy = x
119 Sxyz = xz(yz)
120
121
122 That's all! (Well you are supposed to remember also that abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)).
123
124 I recall the exercices taken from "My First Everything Theory" Primary school Year 2127 :) Solution are below. Evaluate:
125
126 (SS)KKK =
127 KKK(SS) = ?
128 (KK)(KK)(KK) = ?
129 (KKK)(KKK)(KKK) = ?
130
131
132 Evaluate:
133
134
135 K
136 KK
137 KKK
138 KKKK
139 KKKKK
140 KKKKKK
141 KKKKKKK
142 KKKKKKKK
143 KKKKKKKKK
144 KKKKKKKKKK
145
146
147 A little more advanced exercices: is there a molecule, let us called it I, having the following dynamic: (X refers to any molecule).
148
149 IX = X I = ?
150
151
152 (Note I will use in this context the words molecules, birds, combinators, programs as synonymous).
153
706d11d0 »
2008-11-14 added 3rd and 4th texts
154 **SOLUTIONS:**
bead294a »
2008-11-13 second post up
155
156 (SS)KKK = SK(KK)K = KK(KKK) = K
157 KKK(SS) = K(SS)
158 (KK)(KK)(KK) = KK(KK)(KK) = K(KK)
159 (KKK)(KKK)(KKK) = KKK = K
160
161
162 Note that the passage (KK)(KK)(KK) = KK(KK)(KK) comes just from a use of the parentheses abbreviation rule which help to see the match with the dynamic of K : Kxy = x, and indeed KK(KK), when occuring at a beginning, matches Kxy with x = K and y = (KK) = KK.
163
164
165 K = K
166 KK = KK
167 KKK = K
168 KKKK = KK
169 KKKKK = K
170 KKKKKK = KK
171 KKKKKKK = K
172 KKKKKKKK = KK
173 KKKKKKKKK = K
174 KKKKKKKKKK = KK
175
176
177 ok? (this was easy! if you have not succeed it means you are imagining difficulties). The next exercise is slightly less easy, we are to program some identity operator.
178
179
180 Ix = x I = ?
181
182
183 We must find a program (that is a combinator, that is a combination of K and S) which applied on any X gives that X. We want for example that
184
185
186 I(KK) = (KK)
187 I(SSS) = SSS etc.
188
189
190 So we want that for all x Ix = x. But only Kxy is able to give x so x = Kx? and we want Kx? matching the rule for S (we have only this one), it is easy because whatever ? represents, Kx? gives x. So we can take ? = (K x) or (S x) or etc.
191
192 This gives x = Kx(Kx) (or x = Kx(Sx) ) so that the rule S can be applied so that
193
194
195 x = Kx(Kx) = SKKx (or x = Kx(Sx) = SKS)
196
197
198 Thus SKKx = x, and so a solution is
199
200 I = SKK
201
202
203 It is our first program! Another one is I = SKS (actually SK<anything stable> would work).
204
205
206 Let us verify. i.e. let us test SKK and SKS on KK:
207
208
209 SKK(KK) = K(KK)(K(KK)) = KK
210 SKS(KK) = K(KK)(S(KK)) = KK
211
212
213 more general verification:
214
215 SKKx = Kx(Kx) = x
216
217
218 Any problem? You see that programming is really inverse-executing.
219
220
706d11d0 »
2008-11-14 added 3rd and 4th texts
221 **New programming exercises:**
bead294a »
2008-11-13 second post up
222
223
224 Find combinators M, B, W, L, T such that
225
226
227 Mx = xx (Hint: use your "subroutine" I, as a "macro" for SKK)
228
229 Bxyz = x(yz)
230
231 Wxy = xyy
232
233 Lxy = x(yy)
234
235 Txy = yx
236
237
cb92b9f8 »
2008-11-15 all texts now reproduced
238 [COMBINATORS III](http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html)
706d11d0 »
2008-11-14 added 3rd and 4th texts
239 ---
240
241 Resume:
242
243 Kxy = x
244 Sxyz = xz(yz)
245
246 That's all. (You are supposed to remember also that abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)), so Kxy is put for ((K x) y), and Sxyz is put for (((S x) y) z), and xz(yz) is put for ((x z)(y z)). We just don't write the left parentheses).
247
248 I recall the last exercises:
249
250 Find combinators M, B, W, L, T and C such that Mx = xx (Hint: use your "subroutine" I, as a "macro" for SKK)
251
252 Bxyz = x(yz)
253 Wxy = xyy
254 Lxy = x(yy)
255 Txy = yx
256 Cxyz = xzy (I add this one)
257
258 I solve the two firsts one: M and B:
259
260 I recall we have already program the identity combinator I, which is such that Ix = x for any combinators x. it is I = SKK, and we can use it as a "subroutine".
261
262 1) We want find a combinator M such that Mx = xx.
263
264 We reason again by inverse-execution. We must transform xx in a way such that it matches the right part of the dynamic of K or S. The simplest way is by using I. Indeed xx = Ix(Ix), and this match the S rule.
265
266 Thus:
267
268 Mx = Ix(Ix)
269 = SIIx
270
271 and thus:
272 M = SII
273 = S(SKK)(SKK).
274
275 2) We want to find a combinator B such that Bxyz = x(yz)
276
277 We need to find an expression equal (by the dynamic rule) to something matching the right part of the S dynamic. We can use I, M or K and S. Here K and S will be enough. Indeed
278
279 Bxyz = x(yz)
280 = (Kxz)(yz) because x = Kxz
281 = S(Kx)yz verify with all the parentheses if you don't see it.
282 = KSx(Kx)yz because S = (KSx)
283 = S(KS)Kxyz
284
285 Thus:
286 B = S(KS)K
287
288 All right?
289
290 Note to understand what will follow it is not really necessary to develop skills in the art of finding those programs, but you should be able to verify them if you want to have the needed passive knowledge. Let us verify B on any x y z:
291
292 Bxyz = S(KS)Kxyz = KSx(Kx)yz = S(Kx)yz = Kxz(yz) =x(yz). OK?
293
294 Nevertheless I give you time (for the fun) to try to find W, L, T and C. Could you find a combinator called INFINITY which is perpetually unstable? That is INFINITY gives INFINITY, which gives INFINITY etc. (by the K S dynamical rule).
295
296 To sum up our work:
297
298 I = SKK
299 M = SII = S(SKK)(SKK)
300 B = S(KS)K
301
302 Try to find W, with Wxy = xyy, L, with Lxy = x(yy), T with Txy = yx, C with Cxyz = xzy, and INFINITY, with INFINITY dynamically transform into INFINITY itself. No question? Soon (that is after we solve the last problems) we will have enough to make precise some nuances between "mind" and "matter". Already!
303
cb92b9f8 »
2008-11-15 all texts now reproduced
304 [COMBINATORS IV](http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html)
706d11d0 »
2008-11-14 added 3rd and 4th texts
305 ---
306
307 Resume:
308
309 Kxy = x
310 Sxyz = xz(yz)
311
312 That's all. (You are supposed to remember also that abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)), so Kxy is put for ((K x) y), and Sxyz is put for (((S x) y) z), and xz(yz) is put for ((x z)(y z)). We just don't write the left parentheses).
313
314 We have seen:
315
316 Ix = x, a solution for I is I = SKK
317 Mx = xx, a solution for M is M = SII = S(SKK)(SKK)
318 Bxyz = x(yz), a solution for B is B = S(KS)K
319
320 I recall the last exercises:
321
322 Find combinators W, L, T, C and INFINITY such that
323
324 Wxy = xyy
325 Lxy = x(yy)
326 Txy = yx
327 Cxyz = xzy
328 INFINITY gives INFINITY (by the dynamical rules for K and S).
329
330 SOLUTIONS:
331
332 One:
333
334 Wxy = xyy
335 = (xy)y because xyy abbreviates xyy
336 = (xy)(Iy) because y = Iy
337 = SxIy dynamics of S
338 = (SxI)y abbrev.
339 = Sx(KIx)y because I = KIx
340 = (Sx(KIx))y abbrev.
341 = (SS(KI)x)y dynamics of S
342 = SS(KI)xy abbrev.
343
344 Thus:
345
346 W = SS(KI) = SS(K(SKK))
347
348 Two:
349
350 Lxy = x(yy)
351 = x(My) because My = yy (Mx = xx).
352 = BxMy dynamics of B
353 = Bx(KMx)y 'cause KMx = M
354 = SB(KM)xy dyn. of S, on ((Bx)((KM)x)
355
356 Thus:
357
358 L = SB(KM) = S(S(KS)K)(KS(SKK)(SKK))
359
360 Of course SB(KM) is a better presentation, giving that we know already B and M. But I give the (abbreviated) combinator (in term of S and K) to be sure you see it is indeed a combinator (a combination of S and K).
361
362 3)
363
364 Txy = yx
365 = y(Kxy) 'cause x = Kxy
366 = (Iy)(Kxy) 'cause y = (Iy)
367 = SI(Kx)y dyn. of S (which explain the transformation just above btw)
368 = B(SI)Kxy dyn. of B
369
370 Thus:
371
372 T = B(SI)K = S(KS)K(S(SKK))K
373
374 4)
375
376 Cxyz = xzy
377 = xz(Kyz)
378 = Sx(Ky)z
379 = B(Sx)Kyz
380 = BBSxKyz
381 = BBSx(KKx)yz
382 = (BBS)x(KKx)yz
383 = S(BBS)(KK)xyz
384
385 Thus:
386
387 C = S(BBS)(KK)
388 = S((S(KS)K)(S(KS)K)S)(KK) cf B = S(KS)K
389
390 5) INFINITY Well this one is easy!
391
392 Mx = xx, thus MM gives MM which gives MM, etc.
393
394 Thus:
395
396 INFINITY = MM = SII(SII) = S(SKK)(SKK)(S(SKK)(SKK))
397
398 It is a simple example of a perpetually unstable molecule.
399
400 All right so far? To find those programs, the heuristic has been to use K and I to change some combination of variables (like xzy) into a form such that a known dynamic can be used (in general the one of S, or of B). B, for example, is useful to shift parentheses on the left. Such exercises need a bit of training and a taste for programming or puzzles. I hope that you are able to verify (at least) a solution. Let us verify that L admits another solution based on the use of C:
401
402 L = CBM (by which I mean CBM behaves like it is aked for L to behave, i.e. Lxy = x(yy)
403
404 Indeed:
405
406 CBMxy = BxMy (because Cabc=acb, or Cxyz = xzy)
407 = x(My)
408 = x(yy).
409
410 Such a sequence of application of the dynamical rules will be what I mean by the term "computation". This will be justify when we will see that the combinators are Turing-equivalent. Any program can be matched by a combinator.
411
412 Note also this. We see that SB(KM) and CBM are two different programs computing L. But SB(KM), that is S(S(KS)K)(KS(SKK)(SKK)), and CBM, that is S((S(KS)K)(S(KS)K)S)(KK)(S(KS)K)(S(SKK)(SKK)) are different combinators doing the same things. We will use the (extensionality) rule which identifies the combinators which have the same behavior. When two combinators are syntactically identical, we will use the expression "strictly identical" (written ==). A (more simple) example is:
413
414 I = SKK = SKS = SK(KK) = ....
415
416 They all give an identity combinator. But none can be obtained from this other by a reduction, i.e. an application of the dynamical rule from left to right (like in a computation).
417
418 Finally, because the combinators we have met so far will play some persisting role in the sequel, they deserve names. I give you the (birdy) terminology of Smullyan:
419
420 * K is the kestrel. It is "the" eliminator. K(KK)(SSS) eliminates (SSS) for example.
421 * S is the starling. S does many things at once: it duplicates, composes, and permutates its arguments: Sxyz = xz(yz). Look carefully.
cd319e7e »
2008-11-19 Spelling fixed, thanks to Hiroki Yoshioka
422 * T is the thrush. It is a crude permutator. It permutates its arguments: Txy = yx.
706d11d0 »
2008-11-14 added 3rd and 4th texts
423 * M is the mocking bird itself! It is just a crude duplicator: Mx = xx.
424 * C is the cardinal. C is called the elementary or regular permutator. It is less crude than the trush. Much more easy to use, like in general the regular combinators, which by definition are those combinators which leaves unchanged they first argument. All combinators seen so far are regular except the trush.
425 * W is the warbler. It is the elementary duplicator (less crude than the mocking bird!).
426 * B is the elementary compositor. Bxyz = x(yz). Suppose that f = log, and g = sin, then Bfgx = log(sin x), so that Bfg gives f * g. That is the composition of the functions f and g. I forget to say that B is called the blue bird.
427 * L is the lark: it is an hybrid of a warbler or a mocking bird and a compositor.
428
429 Exercise:
430
431 We have seen how to program the blue bird B, the cardinal C and the Warbler W with the kestrel K and the starling S. Could you define the starling S from B, W and C? I give you the first line:
432
433 Sxyz = xz(yz)
434 = Cx(yz)z
435 = ...
436
cb92b9f8 »
2008-11-15 all texts now reproduced
437 [COMBINATORS V](http://www.mail-archive.com/everything-list@eskimo.com/msg05955.html)
438 ---
439
440 We have seen how to program the blue bird B, the cardinal C and the Warbler W with the kestrel K and the starling S. Could you define the starling S from B, W and C? It is not so simple. Now if we succeed, this will give us a second equivalent theory.
441
442 I mean the sets:
443
444 {S K}
445
446 {W B C K}
447
448 generates by composition the same set of birds. Later we will see those sets are maximal. They generate all the birds. It is two equiavlent presentations of the same "everything theory". The first has two primitive bird, the second has 4 primitives birds (because it can be shown you cannot define W from B C K, nor B from W C K, etc.)
449
f9fda912 »
2008-11-15 fixed a formatting problem
450 To show the sets {S K} and {W B C K} generate the same combinators (birds) we must show how to define W, B, C and K from {S K}. But this has been done (see previous post), for example W = SS(KI), B = S(KS)K and C = S(BBS)(KK).
cb92b9f8 »
2008-11-15 all texts now reproduced
451
452 So it remains to show inversely that S can be defined from W, B, and C (and K except S does not eliminate any input and it is thus doubtless we need K).
453
454 I gave you the first line:
455
456 Sxyz = xz(yz)
457 = Cx(yz)z
458
459 Ah someone asks me why? Recall Cxyz= xzy, with x y z arbitrary combinators, thus Cx(yz)z = xz(yz) (the first argument of C was x, the second was (yz) and the third was z).
460
461 Oops students are coming. I let you do the following more easy exercise:
462
463 Verify that S = B(BW)(BBC). That is verify that B(BW)(BBC)xyz = xz(yz). This should be much easier.
464
465 [COMBINATORS VI](http://www.mail-archive.com/everything-list@eskimo.com/msg05957.html)
466 ---
467
468 I will provide a detailed solution of the last problem for those who have perhaps missed the beginning.
469
470 Verify that S = B(BW)(BBC). That is verify that B(BW)(BBC)xyz = xz(yz) This should be much easier.
471
472 One awful solution would be, reminding that B = S(KS)K, and that W = SS(KI) and that C = S(BBS)(KK), that is S((S(KS)K)(S(KS)K)S)(KK), to substitute those the occurence of B, W and C by they SK-programs, giving:
473
474 S = B(BW)(BBC) =
475 S(KS)K((S(KS)K)SS(K(SKK)))((S(KS)K)(S(KS)K)(S((S(KS)K)(S(KS)K)S)(KK)))
476
477 ... and then applying that _expression_ on xyz.
478
479 Obviously we have not programmed the elementary compositor B, the elementary permutator C and the elementary duplicator W for not using them. Yet this gave an interesting definition of S in term of itself and this rises the question if there is not some general recursion phenomenon there and indeed there will be a very general such phenomenon captured by a combinator which is neither an eliminator, nor a permutator, nor a duplicator, nor even an identificator (like Ix = x) and which was called the paradoxical combinators by Curry and Feys and is known today as the fixed point combinator but that's for later.
480
481 So I recall:
482
483 Bxyz = x(yz)
484 Wxy = xyy
485 Cxyz = xzy
486
487 And 'course:
488
489 Kxy = x
490 Sxyz = xz(yz)
491
492 And let us verify that S = B(BW)(BBC) I recall "=" means "act similarly"; thus we must show that:
493
494 B(BW)(BBC)xyz = Sxyz = xz(yz)
495
496 Well Bxyz = x(yz) and please remember that Bxyz abbreviates (((B x) y) z) and in particular
497
498 B(BW)(BBC)x abbreviates (((B (BW)) (BBC)) x) and that that matches!
499
500 Another practical way (more practical than by adding the left parenthesis!) is to fully abbreviate the _expression_ (like I do usually) and remember that B (here) is trigged by its dynamic when presented with three arguments and that argument are *arbitrary* combinators:
501
502 so the _expression_ B(BW)(BBC)xyz is
503
504 B (BW) (BBC) x y z
505 1 2 3
506
507 and you can write the dynamic of B by B123 = 1(23), meaning that 1 denotes its first argument (BW), 2 its second (BBC) and 3 denotes x, so that
508
509 B(BW)(BBC)x gives (BW)((BBC)x) that is (fully abbreviated)
510
511 BW(BBCx). We must yet apply it to y and then z:
512
513 BW(BBCx)y
514
515 Oh! here we have a choice! Indeed the B-dynamic match the first occurrence of B and the second one. A famous result, known as Church Rosser Theorem tells us that as far as thereduction will converge on some stable molecule, the path, and thus those choice does not matter: we will get the same stable molecule. Soon or later we will come back on this, but let us just choose the leftmost reduction (another theorem will make some advertising for that strategy, but things will appear to be non trivial though ...). So we apply the B-rule on leftmost B in: B W (BBCx) y giving W((BBCx)y) that is (fully abbrev.) W(BBCxy), and now we have also a choice: either we apply W(BBCxy) directly on z, or we reduce it further. You could verify those alternate path as exercise; let us apply W(BBCxy) directly on z. This gives W(BBCxy)z (and Wab = abb) thus W(BBCxy)z gives (BBCxy)zz = (fully abbrev.) BBCxyzz, and this gives by the B-rule B123 = 1(23), (where 1, the first argument of B is B itself, and 2 is C and 3 is x) B(Cx)yzz which by the B rule again (with 1 = (Cx), 2 = y, 3 = z) gives (Cx)(yz)z, which by the C-rule C123= 132 (with 1 = x, 2 = (yz) 3 = z gives xz(yz). That's Sxyz and so we have shown that B(BW)(BBC) behaves like S.
516
517 To sum up: S = B(BW)(BBC) because
518
519 B(BW)(BBC)xyz
520 = BW(BBCx)yz
521 = W(BBCxy)z
522 = (BBCxy)zz
523 = B(Cx)yzz
524 = Cx(yz)z
525 = xz(yz) which what Sxyz gives.
526
527
528
529 Of course the original exercise I gave was harder: program S from B, W and C. It consisted in finding that B(BW)(BBC) or something similar. But how could we have found such _expression_? A nice thing is that the verification above, which just use the dynamics of B, C and W gives us the answer: just copy the execution above in the reverse order (cf programming here is inverse execution). I do it and I comment:
530
f9fda912 »
2008-11-15 fixed a formatting problem
531 ?xyz = < B, C, ...>xyz = xz(yz)
cb92b9f8 »
2008-11-15 all texts now reproduced
532
f9fda912 »
2008-11-15 fixed a formatting problem
533 xz(yz) so this is what we want as the result of B C W application on xyz. So we must transform xz(yz) as <B,C ..>xyz, that is get those final "x)y)z)", or xyz in fully abb. form.
cb92b9f8 »
2008-11-15 all texts now reproduced
534
535 Cx(yz)z what a clever move! we are at once close to xyz, except that we have two parentheses too much, and one z to much. To suppress one z we will isolate it by moving the right parenthesis to the left. That's the inversion of the B-rule, so we arrive at:
536
537 B(Cx)yzz and applying again the B-rule, we get
538
539 (BBCxy)zz I let some left parenthesis so that the W-rule applicability is highlightened
540
541 W(BBCxy)z And now there just remains a right parenthesis we would like to push on the left, which we can do by two successive inverse B rule: The first gives (with 1 = W, 2 = (BBCx) and 3 = y:
542
543 BW(BBCx)yz the second gives with 1 = (BW), 2 = (BBC) and 3 = x:
544
545 B(BW)(BBC)xyz we got what we wanted: S = B(BW)(BBC).
546
547 Both gives xz(yz) when given x y and z (in that order!).
548
549 COMBINATORS VI (sequel)
550 ---
551
552 *Question*: is there a systematic method such that giving any behavior like
553
554 Xxyztuv = x(yx)(uvut) (or what you want)
555
556 can generate systematically a corresponding SK or BWCK -combinator? The answer is yes. I let you meditate the question. (This point will be made clear when we will meet the terrible little cousins of the combinators which are the *lambda _expression_*, (and which in our context will just abbreviate complex combinators), but I propose to progress and make sure that the SK combinator are Turing Universal.
557
558 I am not yet decided when I really should introduce you to the paradoxical combinators, which are rather crazy. Smullyan call them wise birds, but I guess it is an euphemism!
559
560 Mmhhh... Showing turing-universality through the use of some paradoxical combinator is easy (once we have defined the numbers), but there is a risk you take bad habits! Actually we don't need the paradoxical combinators to prove the turing universality of the SK forest, mmmmh...
561
562 Well actually I will be rather busy so I give you the definition of a paradoxical combinator and I let you search one.
563
564 First show that for any combinator A there is a combinator B such that AB = B. B is called a fixed point of A. (like the center of a wheel C is a fixed point of the rotations of the wheel: RC = C). It is a bit amazing that all combinators have a fixed point and that is what I propose you try to show. Here are hints for different arguments. 1) Show how to find a fixed point of A (Arbitrary combinator) using just B, M and A. (Mx = xx I recall). 2) The same using just the Lark L (Lxy = x(yy) I recall). Now, a paradoxical combinator Y is just a combinator which applied on that A will give the fixed point of A; that is YA will give a B such that AB = B, that is A(YA) gives YA, or more generally Y is a combinator satisfying Yx = x(Yx).
565
566 [COMBINATORS VIII](http://www.mail-archive.com/everything-list@eskimo.com/msg05959.html)
567 ---
568
569 Be sure you have understood the preceding posts before reading this one. For archives and even better archives, see the links below.
570
571 **The Paradoxical combinators**
572
573 I recall that a combinator X is a fixed point of a combinator Z if ZX = X. For example, all combinators (birds) are fixed point of the identity combinator, given that for any x Ix = x. Curiously enough in many forest all combinators have a fixed point.
574
575 The "paradoxical combinator", or "fixed point combinator" is a combinator which find that fixed point of any given combinators.
576
577
578 PROPOSITION 1: *if a forest contains a bluebird B, where Bxyz = x(yz), and a MockingBird M, that is Mx = xx, then ALL birds have indeed a fixed point P.*
579
580 Proof: All bird x have BxM(BxM) as a fixed point, that is BxM(BxM) is always a fixed point of x, indeed:
581
582 BxM(BxM) = x(M(BxM)) = x(BxM(BxM)). OK?
583
584
585 PROPOSITION 2: *If a forest contains a lark L, i.e. Lxy = x(yy), then again ALL birds will have a fixed point. Indeed all birds x have Lx(Lx) as a fixed point:*
586
587 Lx(Lx) = x(Lx(Lx)) (directly from the dynamic of L). OK?
588
589
590 Saying that all birds in a forest have a fixed point is not the same as saying that there is, in the forest a bird capable of finding that fixed point. Let us show that if the forest contains a starling and a lark, then there is such a bird (called a paradoxical combinator, or a fixed point combinator. raymond called them "wise bird", and I was used to call them "crazy bird" given that they can have some crazy behavior).
591
592 To find a fixed point combinator, it is enough, for example, to find a bird which on x will generate Lx(Lx).
593
594 But Lx(Lx) is just SLLx
595
596 And thus SLL is a fixed point combinator. SLLx = x(SLLx) given that SLLx = Lx(Lx). OK?
597
598 (Of course SLL is an abbreviated name for combinator
599
600 S(S(S(KS)K)(KS(SKK)(SKK)))(S(S(KS)K)(KS(SKK)(SKK)))
601
602 given that we have shown L = SB(KM); and B = S(KS)K, and M = SI I= S(SKK)(SKK) cf solution 2 in COMBINATORS IV (see links below).
603
604 Obviously, a forest which contains S and K, like our current "everything theory", contains L (or a B and a M) and, thus, is such that all birds have a fixed point. Such a forest also contains fixed point combinators. Some day we will justify why any SK-forest contains really all possible birds.
605
606
607 **WHAT'S the USE of PARADOXICAL combinators?**
608
609 Well, you should be able to solve an exercise like finding a combinator A such that its dynamics is described by Axyz = y(yx)zz. Some other day we will make this precise by giving an *algorithm* for solving such problem (which solutions exist in all "sufficiently rich forest like the SK or BWCK forest). With the fixed point combinators you should be able to solve "recursive equations" like: find a A such that its dynamics is described recursively by Axyz = xxA(Ayy)z. How? Just find a B such that Baxyz = xxa(ayy)z (A has been replaced by a variable a). This is a traditional (non recursive) exercise. Then YB gives the solution of the recursive equation. (Y is the traditional name for a paradoxical combinator). Exercise: why?
610
611
612 **EXERCISES**:
613
614 Find an infinite eliminator E, that is a bird which eliminates all its variables: Ex = E, Exy = E, etc. Find an perpetual permutator, that is a bird which forever permutes its two inputs: its dynamics is as follow: Pxy =: Pyx =: Pxy =: Pyx etc. (I recall "=:" is the reduction symbol of the dynamics; it is the left to right reading of the "dynamics"). Etc. I mean: solve the following equations (little letters like x, y z are put for any combinator, A is put for the precise combinator we are ask searching for):
615
616 Ax = A
617 Ax = xA
618 Axy = Ayx
619 Ax = AAx
620 A = AA
621 Ax = AA
622 Ax = x(Ax)
623
624 Obviously, Y is useful for the recursive programming. This will be illustrate when when we will do some logic and some arithmetic (soon on a screen near you). After that you should be able to program any function with a combinator. And after that we will make a move enabling us to come back to our basic problems: where does mind and matter come from, ..., how to put a reasonable measure on the set of all computations, ...
625
626 Summary:
627
628 1. [COMBINATORS I](http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html)
629 2. [COMBINATORS II](http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html)
630 3. [COMBINATORS III](http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html)
631 4. [COMBINATORS IV](http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html)
632 5. [COMBINATORS V](http://www.mail-archive.com/everything-list@eskimo.com/msg05955.html)
633 6. [COMBINATORS VI](http://www.mail-archive.com/everything-list@eskimo.com/msg05957.html)
634 7. [COMBINATORS VIII](http://www.mail-archive.com/everything-list@eskimo.com/msg05959.html)
635
636 (There is no VII, to the best of my knowledge, it was combined with VI.) Also:
637
638 * abc abbreviates ((a b) c)
639 * Kxy = x
640 * Sxyz = xz(yz)
641 * Combinators combine.
642
bead294a »
2008-11-13 second post up
643 Bruno
644
8b0099db »
2008-11-13 updated with first post text
645 *(c) 2005-2008, Bruno Marchal.*
646
647 ---
911b194e »
2008-11-13 updated footer
648
649 *If you enjoyed Bruno's posts, may I suggest a few of my own explaining some Ruby programming ideas in terms of combinators?*
51b01f1a »
2008-11-12 shamelessly promoting my own posts about combinators
650
94aa33b7 »
2009-02-02 Updated links, especially to combinators
651 [Kestrels](http://github.com/raganwald/homoiconic/tree/master/2008-10-29/kestrel.markdown#readme), [The Thrush](http://github.com/raganwald/homoiconic/tree/master/2008-10-30/thrush.markdown#readme), [Songs of the Cardinal](http://github.com/raganwald/homoiconic/tree/master/2008-10-31/songs_of_the_cardinal.markdown#readme), [Quirky Birds and Meta-Syntactic Programming](http://github.com/raganwald/homoiconic/tree/master/2008-11-04/quirky_birds_and_meta_syntactic_programming.markdown#readme), [Aspect-Oriented Programming in Ruby using Combinator Birds](http://github.com/raganwald/homoiconic/tree/master/2008-11-07/from_birds_that_compose_to_method_advice.markdown#readme), and [The Enchaining and Obdurate Kestrels](http://github.com/raganwald/homoiconic/tree/master/2008-11-12/the_obdurate_kestrel.md#readme).
51b01f1a »
2008-11-12 shamelessly promoting my own posts about combinators
652
7d4a695d »
2011-11-16 dasherize the mores
653 ---
f69ce703 »
2011-11-12 Link to the book
654
ef808c99 »
2011-11-16 fixed the tagline for the combinators book
655 NEW! [Kestrels, Quirky Birds, and Hopeless Egocentricity](http://leanpub.com/combinators), all of my writing about combinators, collected into one convenient and inexpensive e-book!
f69ce703 »
2011-11-12 Link to the book
656
6d10b6a0 »
2010-12-10 updated footers
657 Follow [me](http://reginald.braythwayt.com) on [Twitter](http://twitter.com/raganwald). I work with [Unspace Interactive](http://unspace.ca), and I like it.
Something went wrong with that request. Please try again.