Thun.md

   1 # Thun
   2
   3 A Dialect of Joy.
   4
   5 Version 0.5.0
   6
   7 > Simple pleasures are the best.
   8
   9 [Joy](https://en.wikipedia.org/wiki/Joy_%28programming_language%29) is a
  10 programming language created by Manfred von Thun that is easy to use and
  11 understand and has many other nice properties.  **Thun** is a dialect of
  12 Joy that attempts to stay very close to the spirit of Joy but does not
  13 precisely match the behaviour of the original version written in C.
  14 (In the rest of this document I'll use the names Joy and Thun
  15 interchangably.)
  16
  17
  18 ## Grammar
  19
  20 The grammar of Joy is very simple.  A Joy expression is zero or more Joy
  21 terms separated by blanks. Terms can be integers in decimal notation,
  22 Booleans `true` and `false`, lists enclosed by square brackets `[` and `]`,
  23 or symbols (names of functions.)
  24
  25     joy ::= term*
  26
  27     term ::= integer | bool | '[' joy ']' | symbol
  28
  29     integer ::= [ '-' ] ('0'...'9')+
  30
  31     bool ::= 'true' | 'false'
  32
  33     symbol ::= char+
  34
  35     char ::= <Any non-space other than '[' and ']'.>
  36
  37 Symbols can be composed of any characters except blanks and square
  38 brackets.  Integers can be prefixed with a minus sign to denote negative
  39 numbers.  The symbols `true` and `false` are reserved to denote their
  40 respective Boolean values.
  41
  42 That's it.  That's the whole of the grammar.
  43
  44
  45 ## Types
  46
  47 The original Joy has several datatypes (such as strings and sets)
  48 but the Thun dialect currently only uses four:
  49
  50 * Integers, signed and unbounded by machine word length (they are
  51   [bignums](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic).)
  52 * Boolean values ``true`` and ``false``.
  53 * Lists quoted in `[` and `]` brackets.
  54 * Symbols (names).
  55
  56
  57 ## Stack, Expression, Dictionary
  58
  59 Joy is built around three things: a __stack__ of data items, an
  60 __expression__ representing a program to evaluate, and a __dictionary__
  61 of named functions.
  62
  63 ### Stack
  64
  65 Joy is
  66 [stack-based](https://en.wikipedia.org/wiki/Stack-oriented_programming_language).
  67 There is a single main __stack__ that holds data items, which can be
  68 integers, bools, symbols (names), or sequences of data items enclosed in
  69 square brackets (`[` or `]`).
  70
  71 We use the terms "stack", "quote", "sequence", "list", and others to mean
  72 the same thing: a simple linear datatype that permits certain operations
  73 such as iterating and pushing and popping values from (at least) one end.
  74
  75 > In describing Joy I have used the term quotation to describe all of the
  76 > above, because I needed a word to describe the arguments to combinators
  77 > which fulfill the same role in Joy as lambda abstractions (with
  78 > variables) fulfill in the more familiar functional languages. I use the
  79 > term list for those quotations whose members are what I call literals:
  80 > numbers, characters, truth values, sets, strings and other quotations.
  81 > All these I call literals because their occurrence in code results in
  82 > them being pushed onto the stack. But I also call [London Paris] a
  83 > list. So, [dup \*] is a quotation but not a list.
  84
  85 From ["A Conversation with Manfred von Thun" w/ Stevan Apter](http://archive.vector.org.uk/art10000350)
  86
  87 ### Expression
  88
  89 A Joy __expression__ is just a sequence or list of items.  Sequences
  90 intended as programs are called "quoted programs".  Evaluation proceeds
  91 by iterating through the terms in an expression putting all literals
  92 (integers, bools, or lists) onto the main stack and executing functions
  93 named by symbols as they are encountered.  Functions receive the current
  94 stack, expression, and dictionary and return the next stack, expression,
  95 and dictionary.
  96
  97 ### Dictionary
  98
  99 The __dictionary__ associates symbols (names) with Joy expressions that
 100 define the available functions of the Joy system.  Together the stack,
 101 expression, and dictionary are the entire state of the Joy interpreter.
 102
 103
 104 ## Interpreter
 105
 106 The Joy interpreter is extrememly simple. It accepts a stack, an
 107 expression, and a dictionary, and it iterates through the expression
 108 putting values onto the stack and delegating execution to functions which
 109 it looks up in the dictionary.
 110
 111 ![Joy Interpreter Flowchart](https://git.sr.ht/~sforman/Thun/blob/trunk/joy_interpreter_flowchart.svg)
 112
 113 All control flow works by
 114 [Continuation Passing Style](https://en.wikipedia.org/wiki/Continuation-passing_style).
 115 __Combinators__ (see below) alter control flow by prepending quoted programs to the pending
 116 expression (aka "continuation".)
 117
 118
 119 ## Literals, Functions, Combinators
 120
 121
 122 ### Literals
 123
 124 Literal values (integers, Booleans, lists) are put onto the stack.
 125
 126 ### Functions
 127
 128 Functions take values from the stack and push results onto it.
 129
 130 ### Combinators
 131
 132 __Combinators__ are functions which accept quoted programs on the stack
 133 and run them in various ways.  These combinators reify specific
 134 control-flow patterns (such as `ifte` which is like `if.. then.. else..`
 135 in other languages.)  Combinators receive the current expession in
 136 addition to the stack and return the next expression.  They work by
 137 changing the pending expression the interpreter is about to execute.
 138
 139 ### Basis Functions
 140
 141 Thun has a set of *basis* functions which are implemented in the host
 142 language.  The rest of functions in the Thun dialect are defined in terms
 143 of these:
 144
 145 - Combinators: `branch` `dip` `i` `loop`
 146 - Stack Chatter: `clear` `dup` `pop` `stack` `swaack` `swap`
 147 - List Manipulation: `concat` `cons` `first` `rest`
 148 - Math: `+` `-` `*` `/` `%`
 149 - Comparison: `<` `>` `>=` `<=` `!=` `<>` `=`
 150 - Logic: `truthy` `not`
 151 - Programming: `inscribe`
 152
 153 ### Definitions
 154
 155 Thun can be extended by adding new definitions to the
 156 [defs.txt](https://git.sr.ht/~sforman/Thun/tree/trunk/item/implementations/defs.txt)
 157 file and rebuilding the binaries.  Each line in the file is a definition
 158 consisting of the new symbol name followed by an expression for the body
 159 of the function.
 160
 161 The `defs.txt` file is just joy expression, one per line, that have a
 162 symbol followed by the definition for that symbol, e.g.:
 163
 164     sqr dup mul
 165
 166 The definitions form a DAG (Directed Acyclic Graph) (there is actually a
 167 cycle in the definition of `genrec` but that's the point, it is a cycle
 168 to itself that captures the cyclical nature of recursive definitions.)
 169
 170 I don't imagine that people will read `defs.txt` to understand Joy code.
 171 Instead people should read the notebooks that derive the functions to
 172 understand them.  The reference docs should help, and to that end I'd
 173 like to cross-link them with the notebooks.  The idea is that the docs
 174 are the code and the code is just a way to make precise the ideas in the
 175 docs.
 176
 177 ### Adding Functions to the Dictionary with `inscribe`
 178
 179 You can use the `inscribe` command to put new definitions into the
 180 dictionary at runtime, but they will not persist after the program ends.
 181 The `inscribe` function is the only function that changes the dictionary.
 182 It's meant for prototyping.  (You could abuse it to make variables by
 183 storing "functions" in the dictionary that just contain literal values as
 184 their bodies.)
 185
 186     [foo bar baz] inscribe
 187
 188 This will put a definition for `foo` into the dictionary as `bar baz`.
 189
 190
 191 ## Problems
 192
 193 ### Symbols as Data
 194
 195 Nothing prevents you from using symbols as data:
 196
 197     joy? [cats]
 198     [cats]
 199
 200 But there's a potential pitfall: you might accidentally get a "bare"
 201 unquoted symbol on the stack:
 202
 203     joy? [cats]
 204     [cats]
 205     joy? first
 206     cats
 207
 208 That by itself won't break anything (the stack is just a list.)
 209 But if you were to use, say, `dip`, in such a way as to put the symbol
 210 back onto the expression, then when the interpreter encounters it, it
 211 will attempt to evaluate it, which is almost certainly not what you want.
 212
 213     cats
 214     joy? [23] dip
 215     Unknown: cats
 216     cats
 217
 218 At the very least you get an "Unknown" error, but if the symbol names a
 219 function then the interpreter will attempt to evaluate it, probably
 220 leading to an error.
 221
 222 I don't see an easy way around this.  Be careful?  It's kind of against
 223 the spirit of the thing to just leave a footgun like that laying around,
 224 but perhaps in practice it won't come up.  (Because writing Joy code by
 225 derivation seems to lead to bug-free code, which is the kinda the point.)
 226
 227
 228 --------------------------------------------------
 229
 230 Copyright © 2014 - 2023 Simon Forman
 231
 232 This file is part of Thun
 233