sourcelib/Combinators.xtl

1⍝│ Combinators: the birds Raymond Smullyan names in "To Mock a 2⍝│ Mockingbird" that type-check (a standard library, built into xetal). 3⍝│ Import it with an alias of your choice: "c:" u_se< "Combinators". 4⍝│ docs/birds.md lists them all, with two of Curry's that trains name 5⍝│ (the Phoenix and Psi); the self-applying birds (L, M, M2, U) have no 6⍝│ finite type and are in demos/birds-untyped.xtl. 7⍝│ 8⍝│ Each bird only rearranges, repeats, drops or groups its curried 9⍝│ arguments; its rule is given in Smullyan's notation, where 10⍝│ B x y z = x (y z) means B applied to x, y and z gives x applied to 11⍝│ (y applied to z). 12⍝│ 13⍝│ How the definitions read: a x̲ b is x applied to a and then b (every 14⍝│ function is curried); (e) v applies the function e computes; a 15⍝│ function passed along as a value is quoted, 'y̲. In a call, quoted 16⍝│ function arguments come first, the nearest operand being the bird's 17⍝│ first argument: 'n̲eg 'a̲bs ᶜB̲ -5 is a_bs (n_eg -5). 18 19⍝━━ Identity, constants and duplication 20 21⍝│ The Idiot Bird (identity): I x = x. 22⍝│ >> "c:" u_se< "Combinators" 23⍝│ >> c:I_ 7 24⍝│ 7 25ˡI̲ ← { x → x } ⍝ Idiot Bird (identity) 26 27⍝│ The Kestrel: K x y = x, the first argument kept, the second dropped 28⍝│ (▁, a parameter nothing reads). 29⍝│ >> "c:" u_se< "Combinators" 30⍝│ >> 1 c:K_ 2 31⍝│ 1 32ˡK̲ ← { x ▁ → x } ⍝ Kestrel 33 34⍝│ The Thrush: T x y = y x, the value x given to the function y. 35⍝│ >> "c:" u_se< "Combinators" 36⍝│ >> 3 c:T_ 'n_eg 37⍝│ -3 38ˡT̲ ← { x y̲ → y̲ x } ⍝ Thrush 39 40⍝│ The Warbler: W x y = x y y, the dyadic function x given y twice. 41⍝│ >> "c:" u_se< "Combinators" 42⍝│ >> '* c:W_ 4 43⍝│ 16 44ˡW̲ ← { x̲ y → y x̲ y } ⍝ Warbler 45 46⍝│ The Converse Warbler: W1 x y = y x x, the Warbler with its arguments 47⍝│ the other way round. 48⍝│ >> "c:" u_se< "Combinators" 49⍝│ >> 3 c:W_1 '+ 50⍝│ 6 51ˡW̲1 ← { x y̲ → x y̲ x } ⍝ Converse Warbler 52 53⍝━━ Composition 54 55⍝│ The Bluebird: B x y z = x (y z), x composed with y. 56⍝│ >> "c:" u_se< "Combinators" 57⍝│ >> 'n_eg 'a_bs c:B_ -5 58⍝│ 5 59ˡB̲ ← { x̲ y̲ z → x̲ y̲ z } ⍝ Bluebird: compose 60 61⍝│ The Blackbird: B1 x y z w = x (y z w), x after the dyadic y. 62ˡB̲1 ← { x̲ y̲ z w → x̲ z y̲ w } ⍝ Blackbird 63 64⍝│ The Bunting: B2 x y z w v = x (y z w v), x after the triadic y. 65ˡB̲2 ← { x̲ y̲ z w v → x̲ (z y̲ w) v } ⍝ Bunting 66 67⍝│ The Becard: B3 x y z w = x (y (z w)), three functions composed. 68ˡB̲3 ← { x̲ y̲ z̲ w → x̲ y̲ z̲ w } ⍝ Becard 69 70⍝│ The Cardinal: C x y z = x z y, the dyadic x with its arguments 71⍝│ swapped. 72⍝│ >> "c:" u_se< "Combinators" 73⍝│ >> 10 '- c:C_ 3 74⍝│ -7 75ˡC̲ ← { x̲ y z → z x̲ y } ⍝ Cardinal: swap 76 77⍝│ The Dove: D x y z w = x y (z w), z applied to w before x takes it. 78ˡD̲ ← { x̲ y z̲ w → y x̲ z̲ w } ⍝ Dove 79 80⍝│ The Dickcissel: D1 x y z w v = x y z (w v). 81ˡD̲1 ← { x̲ y z w̲ v → (y x̲ z) w̲ v } ⍝ Dickcissel 82 83⍝│ The Dovekie: D2 x y z w v = x (y z) (w v), both arguments of x 84⍝│ computed first. 85ˡD̲2 ← { x̲ y̲ z w̲ v → (y̲ z) x̲ w̲ v } ⍝ Dovekie 86 87⍝│ The Eagle: E x y z w v = x y (z w v). 88ˡE̲ ← { x̲ y z̲ w v → y x̲ w z̲ v } ⍝ Eagle 89 90⍝│ The Bald Eagle: Eh x y1 y2 y3 z1 z2 z3 = x (y1 y2 y3) (z1 z2 z3). 91ˡE̲h ← { x̲ a̲ b c d̲ e f → (b a̲ c) x̲ e d̲ f } ⍝ Bald Eagle 92 93⍝━━ Permutations 94 95⍝│ The Finch: F x y z = z y x, the function last and the values 96⍝│ reversed. 97⍝│ >> "c:" u_se< "Combinators" 98⍝│ >> (1 c:F_ 2)_ '- 99⍝│ 1 100ˡF̲ ← { x y z̲ → y z̲ x } ⍝ Finch 101 102⍝│ The Goldfinch: G x y z w = x w (y z). 103ˡG̲ ← { x̲ y̲ z w → w x̲ y̲ z } ⍝ Goldfinch 104 105⍝│ The Hummingbird: H x y z = x y z y, y used twice. 106ˡH̲ ← { x̲ y z → (y x̲ z) y } ⍝ Hummingbird 107 108⍝│ The Jay: J x y z w = x y (x w z). 109ˡJ̲ ← { x̲ y z w → y x̲ w x̲ z } ⍝ Jay 110 111⍝│ The Owl: O x y = y (x y). 112ˡO̲ ← { x̲ y̲ → y̲ x̲ 'y̲ } ⍝ Owl 113 114⍝│ The Queer Bird: Q x y z = y (x z), composition the other way round 115⍝│ from B. 116⍝│ >> "c:" u_se< "Combinators" 117⍝│ >> 'n_eg 'a_bs c:Q_ -5 118⍝│ -5 119ˡQ̲ ← { x̲ y̲ z → y̲ x̲ z } ⍝ Queer Bird 120 121⍝│ The Quixotic Bird: Q1 x y z = x (z y). 122ˡQ̲1 ← { x̲ y z̲ → x̲ z̲ y } ⍝ Quixotic Bird 123 124⍝│ The Quizzical Bird: Q2 x y z = y (z x). 125ˡQ̲2 ← { x y̲ z̲ → y̲ z̲ x } ⍝ Quizzical Bird 126 127⍝│ The Quirky Bird: Q3 x y z = z (x y). 128ˡQ̲3 ← { x̲ y z̲ → z̲ x̲ y } ⍝ Quirky Bird 129 130⍝│ The Quacky Bird: Q4 x y z = z (y x). 131ˡQ̲4 ← { x y̲ z̲ → z̲ y̲ x } ⍝ Quacky Bird 132 133⍝│ The Robin: R x y z = y z x, the function moved to the front. 134⍝│ >> "c:" u_se< "Combinators" 135⍝│ >> (1 c:R_ '-)_ 2 136⍝│ 1 137ˡR̲ ← { x y̲ z → z y̲ x } ⍝ Robin 138 139⍝│ The Starling: S x y z = x z (y z), z used twice (J's hook). 140⍝│ >> "c:" u_se< "Combinators" 141⍝│ >> 'n_eg '- c:S_ 3 142⍝│ 6 143ˡS̲ ← { x̲ y̲ z → z x̲ y̲ z } ⍝ Starling 144 145⍝│ The Vireo: V x y z = z x y, a pair: x and y held until a function 146⍝│ z is given them. 147⍝│ >> "c:" u_se< "Combinators" 148⍝│ >> (1 c:V_ 2)_ '- 149⍝│ -1 150ˡV̲ ← { x y z̲ → x z̲ y } ⍝ Vireo: a pair 151 152⍝━━ From Curry's aviary 153 154⍝│ The Phoenix (Curry's S', not in Smullyan's list): Phi x y z w = 155⍝│ x (y w) (z w), the fork [y̲ x̲ z̲] w as a bird: two functions of 156⍝│ the same argument, joined by a third. 157⍝│ >> "c:" u_se< "Combinators" 158⍝│ >> 'a_bs 'n_eg '- c:P_hi 3 159⍝│ -6 160ˡP̲hi ← { x̲ y̲ z̲ w → (y̲ w) x̲ z̲ w } ⍝ Phoenix: a fork 161 162⍝│ Psi (Curry's, not in Smullyan's list): Psi x y z w = x (y z) (y w), 163⍝│ one function of both arguments before another joins them. 164⍝│ >> "c:" u_se< "Combinators" 165⍝│ >> 1 2 'a_bs '- c:P_si -3 166⍝│ -2 -1 167ˡP̲si ← { x̲ y̲ z w → (y̲ z) x̲ y̲ w } ⍝ Psi: on 168 169⍝━━ Once removed 170 171⍝│ C once removed: C* x y z w = x y w z. 172ˡC̲s ← { x̲ y z w → (y x̲ w) z } 173 174⍝│ R once removed: R* x y z w = x z w y. 175ˡR̲s ← { x̲ y z w → (z x̲ w) y } 176 177⍝│ F once removed: F* x y z w = x w z y. 178ˡF̲s ← { x̲ y z w → (w x̲ z) y } 179 180⍝│ V once removed: V* x y z w = x w y z. 181ˡV̲s ← { x̲ y z w → (w x̲ y) z } 182 183⍝│ W once removed: W* x y z = x y z z. 184ˡW̲s ← { x̲ y z → (y x̲ z) z } 185 186⍝━━ Twice removed 187 188⍝│ C twice removed: C** x y z w v = x y z v w. 189ˡC̲ss ← { x̲ y z w v → ((y x̲ z) v) w } 190 191⍝│ R twice removed: R** x y z w v = x y w v z. 192ˡR̲ss ← { x̲ y z w v → ((y x̲ w) v) z } 193 194⍝│ F twice removed: F** x y z w v = x y v w z. 195ˡF̲ss ← { x̲ y z w v → ((y x̲ v) w) z } 196 197⍝│ V twice removed: V** x y z w v = x y v z w. 198ˡV̲ss ← { x̲ y z w v → ((y x̲ v) z) w } 199 200⍝│ W twice removed: W** x y z w = x y z w w. 201ˡW̲ss ← { x̲ y z w → ((y x̲ z) w) w } 202 203⍝━━ Recursion 204 205⍝│ The Sage Bird by recursion: Y f is f (Y f), a fixed point of f. It 206⍝│ works because a function's parameter is evaluated only when used; f 207⍝│ takes itself (as ~s_elf) and its argument. 208⍝│ >> "c:" u_se< "Combinators" 209⍝│ >> u:f_act := { ~s_elf n -> n <= 1 ? 1; n * s_elf n - 1 } 210⍝│ >> 'u:f_act c:Y_ 5 211⍝│ 120 212ˡY̲ ← { f̲ → f̲ ˡY̲ 'f̲ }