docs/The_Four_Operations.md

   1 # The Four Fundamental Operations of Definite Action
   2
   3 All definite actions (computer program) can be defined by four fundamental patterns of combination:
   4
   5 1. Sequence
   6 2. Branch
   7 3. Loop
   8 4. Parallel
   9
  10 ## Sequence
  11
  12 Do one thing after another.  In joy this is represented by putting two symbols together, juxtaposition:
  13
  14     foo bar
  15
  16 Operations have inputs and outputs.  The outputs of `foo` must be compatible in "arity", type, and shape with the inputs of `bar`.
  17
  18 ## Branch
  19
  20 Do one thing or another.
  21
  22     boolean [F] [T] branch
  23
  24
  25        t [F] [T] branch
  26     ----------------------
  27               T
  28
  29
  30        f [F] [T] branch
  31     ----------------------
  32           F
  33
  34
  35     branch == unit cons swap pick i
  36
  37     boolean [F] [T] branch
  38     boolean [F] [T] unit cons swap pick i
  39     boolean [F] [[T]] cons swap pick i
  40     boolean [[F] [T]] swap pick i
  41     [[F] [T]] boolean pick i
  42     [F-or-T] i
  43
  44 Given some branch function `G`:
  45
  46     G == [F] [T] branch
  47
  48 Used in a sequence like so:
  49
  50     foo G bar
  51
  52 The inputs and outputs of `F` and `T` must be compatible with the outputs for `foo` and the inputs of `bar`, respectively.
  53
  54     foo F bar
  55
  56     foo T bar
  57
  58 ### `ifte`
  59
  60 Often it will be easier on the programmer to write branching code with the predicate specified in a quote.  The `ifte` combinator provides this (`T` for "then" and `E` for "else"):
  61
  62     [P] [T] [E] ifte
  63
  64 Defined in terms of `branch`:
  65
  66     ifte == [nullary not] dip branch
  67
  68
  69 In this case, `P` must be compatible with the stack and return a Boolean value, and `T` and `E` both must be compatible with the preceeding and following functions, as described above for `F` and `T`.  (Note that in the current implementation we are depending on Python for the underlying semantics, so the Boolean value doesn't *have* to be Boolean because Python's rules for "truthiness" will be used to evaluate it.  I reflect this in the structure of the stack effect comment of `branch`, it will only accept Boolean values, and in the definition of `ifte` above by including `not` in the quote, which also has the effect that the subject quotes are in the proper order for `branch`.)
  70
  71 ## Loop
  72
  73 Do one thing zero or more times.
  74
  75     boolean [Q] loop
  76
  77
  78        t [Q] loop
  79     ----------------
  80        Q [Q] loop
  81
  82
  83        ... f [Q] loop
  84     --------------------
  85        ...
  86
  87 The `loop` combinator generates a copy of itself in the true branch.  This is the hallmark of recursive defintions.  In Thun there is no equivalent to conventional loops.  (There is, however, the `x` combinator, defined as `x == dup i`, which permits recursive constructs that do not need to be directly self-referential, unlike `loop` and `genrec`.)
  88
  89     loop == [] swap [dup dip loop] cons branch
  90
  91     boolean [Q] loop
  92     boolean [Q] [] swap [dup dip loop] cons branch
  93     boolean [] [Q] [dup dip loop] cons branch
  94     boolean [] [[Q] dup dip loop] branch
  95
  96 In action the false branch does nothing while the true branch does:
  97
  98     t [] [[Q] dup dip loop] branch
  99           [Q] dup dip loop
 100           [Q] [Q] dip loop
 101           Q [Q] loop
 102
 103 Because `loop` expects and consumes a Boolean value, the `Q` function must be compatible with the previous stack *and itself* with a boolean flag for the next iteration:
 104
 105     Q == G b
 106
 107     Q [Q] loop
 108     G b [Q] loop
 109     G Q [Q] loop
 110     G G b [Q] loop
 111     G G Q [Q] loop
 112     G G G b [Q] loop
 113     G G G
 114
 115
 116 ### `while`
 117
 118 Keep doing `B` _while_ some predicate `P` is true.  This is convenient as the predicate function is made nullary automatically and the body function can be designed without regard to leaving a Boolean flag for the next iteration:
 119
 120
 121
 122                 [P] [B] while
 123     --------------------------------------
 124        [P] nullary [B [P] nullary] loop
 125
 126
 127     while == swap [nullary] cons dup dipd concat loop
 128
 129
 130     [P] [B] while
 131     [P] [B] swap [nullary] cons dup dipd concat loop
 132     [B] [P] [nullary] cons dup dipd concat loop
 133     [B] [[P] nullary] dup dipd concat loop
 134     [B] [[P] nullary] [[P] nullary] dipd concat loop
 135     [P] nullary [B] [[P] nullary] concat loop
 136     [P] nullary [B [P] nullary] loop
 137
 138
 139
 140 ## Parallel
 141
 142 The *parallel* operation indicates that two (or more) functions *do not interfere* with each other and so can run in parallel.  The main difficulty in this sort of thing is orchestrating the recombining ("join" or "wait") of the results of the functions after they finish.
 143
 144 The current implementaions and the following definitions *are not actually parallel* (yet), but there is no reason they couldn't be reimplemented in terms of e.g. Python threads.  I am not concerned with performance of the system just yet, only the elegance of the code it allows us to write.
 145
 146 ### `cleave`
 147
 148 Joy has a few parallel combinators, the main one being `cleave`:
 149
 150                    ... x [A] [B] cleave
 151     ---------------------------------------------------------
 152        ... [x ...] [A] infra first [x ...] [B] infra first
 153     ---------------------------------------------------------
 154                        ... a b
 155
 156 The `cleave` combinator expects a value and two quotes and it executes each quote in "separate universes" such that neither can affect the other, then it takes the first item from the stack in each universe and replaces the value and quotes with their respective results.
 157
 158 (I think this corresponds to the "fork" operator, the little upward-pointed triangle, that takes two functions `A :: x -> a` and `B :: x -> b` and returns a function `F :: x -> (a, b)`, in Conal Elliott's "Compiling to Categories" paper, et. al.)
 159
 160 Just a thought, if you `cleave` two jobs and one requires more time to finish than the other you'd like to be able to assign resources accordingly so that they both finish at the same time.
 161
 162 ### "Apply" Functions
 163
 164 There are also `app2` and `app3` which run a single quote on more than one value:
 165
 166                      ... y x [Q] app2
 167      ---------------------------------------------------------
 168         ... [y ...] [Q] infra first [x ...] [Q] infra first
 169
 170
 171             ... z y x [Q] app3
 172      ---------------------------------
 173         ... [z ...] [Q] infra first
 174             [y ...] [Q] infra first
 175             [x ...] [Q] infra first
 176
 177 Because the quoted program can be `i` we can define `cleave` in terms of `app2`:
 178
 179     cleave == [i] app2 [popd] dip
 180
 181 (I'm not sure why `cleave` was specified to take that value, I may make a combinator that does the same thing but without expecting a value.)
 182
 183     clv == [i] app2
 184
 185        [A] [B] clv
 186     ------------------
 187          a b
 188
 189 ### `map`
 190
 191 The common `map` function in Joy should also be though of as a *parallel* operator:
 192
 193     [a b c ...] [Q] map
 194
 195 There is no reason why the implementation of `map` couldn't distribute the `Q` function over e.g. a pool of worker CPUs.
 196
 197 ### `pam`
 198
 199 One of my favorite combinators, the `pam` combinator is just:
 200
 201     pam == [i] map
 202
 203 This can be used to run any number of programs separately on the current stack and combine their (first) outputs in a result list.
 204
 205        [[A] [B] [C] ...] [i] map
 206     -------------------------------
 207        [ a   b   c  ...]
 208
 209 ### Handling Other Kinds of Join
 210
 211 The `cleave` operators and others all have pretty brutal join semantics: everything works and we always wait for every sub-computation.  We can imagine a few different potentially useful patterns of "joining" results from parallel combinators.
 212
 213 #### first-to-finish
 214
 215 Thinking about variations of `pam` there could be one that only returns the first result of the first-to-finish sub-program, or the stack could be replaced by its output stack.
 216
 217 The other sub-programs would be cancelled.
 218
 219 #### "Fulminators"
 220
 221 Also known as "Futures" or "Promises" (by *everybody* else.  "Fulinators" is what I was going to call them when I was thinking about implementing them in Thun.)
 222
 223 The runtime could be amended to permit "thunks" representing the results of in-progress computations to be left on the stack and picked up by subsequent functions.  These would themselves be able to leave behind more "thunks", the values of which depend on the eventual resolution of the values of the previous thunks.
 224
 225 In this way you can create "chains" (and more complex shapes) out of normal-looking code that consist of a kind of call-graph interspersed with "asyncronous" ... events?
 226
 227 In any case, until I can find a rigorous theory that shows that this sort of thing works perfectly in Joy code I'm not going to worry about it.  (And I think the Categories can deal with it anyhow?  Incremental evaluation, yeah?)
 228
 229