docs/source/Thun.md

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