docs/The_Four_Operations.rst

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