composition.fz
# This file is part of the Fuzion language implementation. # # The Fuzion language implementation is free software: you can redistribute it # and/or modify it under the terms of the GNU General Public License as published # by the Free Software Foundation, version 3 of the License. # # The Fuzion language implementation is distributed in the hope that it will be # useful, but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public # License for more details. # # You should have received a copy of the GNU General Public License along with The # Fuzion language implementation. If not, see <https://www.gnu.org/licenses/>. # ----------------------------------------------------------------------- # # Tokiwa Software GmbH, Germany # # Source code of Fuzion standard library feature composition # # Author: Fridtjof Siebert (siebert@tokiwa.software) # # ----------------------------------------------------------------------- # composition -- a collection of features for function composition # # see https://mlochbaum.github.io/BQN/tutorial/combinator.html # https://combinatorylogic.com/table.html # # Talk at Strange Loop 2016 by Amar Shah: Point-Free or Die: Tacit Programming in Haskell and Beyond # https://www.youtube.com/watch?v=seVSlKazsNk # # Talk at CppNorth 2023 by Conor Hoekstra: Function Composition in Programming Languages - Conor Hoekstra - CppNorth 2023 # https://www.youtube.com/watch?v=JELcdZLre3s # # Paper by Conor Hoekstra: Combinatory Logic and Combinators in Array Languages # https://web.archive.org/web/20220617020347id_/https://dl.acm.org/doi/pdf/10.1145/3520306.3534504 # # BQN tutorial: https://mlochbaum.github.io/BQN/tutorial/index.html # # Talk for Fullstack Academy by Gabriel Lebec: Lambda Calculus - Fundamentals of Lambda Calculus & Functional # Pragramming in JavaScript # https://www.youtube.com/watch?v=3VQ382QG-y4 # # David C Keenan # To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction # https://dkeenan.com/Lambda/ # # Bird names from Raymond M Smullyan. 2000. To Mock a Mockingbird: and other # logic puzzles including an amazing adventure in combinatory logic. Oxford # University Press, USA. # # Combinator birds: https://www.angelfire.com/tx4/cus/combinator/birds.html # public composition is # I # identity # Bird: Idiot (Smullyan) or Ibis (Gabriel Lebec) # BQN: ⊣⊢ # Haskell: id public id(T type) T -> T => x->x # M # self application # Bird: Mockingbird # BQN: ? # Haskell: (cannot define) # # This is not representable in Fuzion, we would need arguments with generic arguments # here. Using pseudo-syntax ((T,U type) <type using T,U>) to denote a type that is # itself type parameteric...: # # public M(f ((T,U type) T -> U)) ((V,W type) V->W) => f f # # we can emulate this if we require the argument to be given twice: public M(T, U, V type, f0 (T->U)->(T->V), f1 T->U) T->V => f0 f1 # applying M to id: public Mid(T type) => M T T T x->x x->x # NYI: should also work: (composition.this.id T) (composition.this.id T) # applying M to M # public MM(T type) => M T T T x->(MM x) x->(MM x) # M* # self application once removed # Bird: Mockingbird # BQN: ? # Haskell: ? # public Mstar(f (T->T,T)->T) T->T => x-> f f x # ? # reverse apply # Bird: thrush # BQN: ? # Haskell: $ # # this is already defined in universe: # public infix |>(T, U type, x T, f T->U) U => f x # T # hold an argument # Bird: thrush # BQN: ? # Haskell: flip id public thrush(T, U, V type, x T, f (T,U)->V) U->V => y->f x y # NYI just `f x` with partial application should do , but does not # V # hold a pair of arguments # Bird: vireo # BQN: ? # Haskell: flip . flip id public vireo(T, U, V, W type, x T, y U, f (T,U,V)->W) V->W => z->f x y z # NYI just `f x y` with partial application should do , but does not # K # Elementary Cancellator, first # Bird: Kestrel # BQN: ⊣ # Haskell const public left(T, U type) (T,U) -> T => (x,y) -> x public constant(T, U type) (T,U) -> T => (x,y) -> x # S # hook, monadic after # Bird: Starling # BQN: ⟜ # Haskell: <*> public after1(f (T, U) -> V, g T -> U) T -> V => x -> f x (g x) # B # Elementare Compositor, composition # Bird: Bluebird # BQN: ∘ # Haskell: . public compose(f U -> V, g T -> U) T -> V => f ∘ g # B1 # Elementare Compositor, 1° <- 2° composition # Bird: Blackbird # BQN: ∘ # Haskell: .: or ... public atop(f V -> W, g (T,U) -> V) (T,U) -> W => (x,y) -> f (g x y) # B # composition of one unary function f and one binary function g... # Bird: Bluebird # BQN: ⊸ public before1(f V -> U, g (U, V) -> W) V -> W => x -> g (f x) x public before2(f T -> U, g (U, V) -> W) (T,V) -> W => (x,y) -> g (f x) y # C # Elementary Permutator, reverse arguments # Bird: Cardinal # BQN: ˜ # Haskell: flip public flip(f (T,U) -> V) (U,T) -> V => (x,y) -> f y x # W # Elementary Duplicator # Bird: Warbler # BQN: ~ # Haskell: join public join(f (T,T) -> U) T->U => x -> f x x # Ψ - psi # composition of binary and unary function # Bird: ? # BQN: ○ # Haskell: on public over(f (U,U) -> V, g T -> U) (T,T) -> V => (x,y) -> f (g x) (g y) # Φ (S′) # composition of two unary functions and one binary function # Bird: ? # BQN: 3-train? # Haskell: liftA2 public fork(f (U1,U2) -> V, g T1 -> U1, h T2 -> U2) (T1,T2) -> V => (x,y) -> f (g x) (h y) # Φ1 # composition of two unary functions and one binary function # Bird: Pheasant (Hoekstra) # BQN: 3-train? # Haskell: ? public fork2(f (U1,U2) -> V, g (T1,T2) -> U1, h (T1,T2) -> U2) (T1,T2) -> V => (x,y) -> f (g x y) (h x y) # D # composition of one binary function f and one unary function g... # Bird: Dove # BQN: ⟜ # Haskell: public after2(f (V, U) -> W, g T -> U) (V,T) -> W => (x,y) -> f x (g y) # D2 # composition of one binary function g and tow unary functions f, h # Bird: Dovekie # BQN: a⊸b⟜c # Haskell: public d2(f T -> V, g (V,W) -> X, h U -> W) (T,U) -> X => (x,y) -> g (f x) (h y) # KI # second # left ∘ flip # Bird: Kite # BQN: ⊢ # Haskell: const id public right(T, U type) (T,U) -> U => (x,y) -> y # ? # Constant cancellator? # Bird: ? # BQN: ˙ public const1(T, U type, v T) U -> T => x -> v public const2(T, U, V type, v T) (U,V) -> T => (x,y) -> v # The Y fixed-point combinator # \f.(\x.f(xx))(\x.f(xx)) # NYI: possible? # The Z fixed-point combinator # \f.(\x.f(\v.xxv))(\x.f(\v.xxv)) # \f.M(\x.f(\v.Mxv)) # NYI: possible? # fixed-point combinator using Lazy: # # this can be used as follows: # # f (Lazy i32)->i32 := x->3 # say (fix i32 f) # # g (Lazy (list i32))->list i32 := x->3:x # say ((fix (list i32) g).take 10) # fix(A type, f Lazy ((Lazy A)->A)) => f.call (fix A f)