doc/INTRO.md

   1 # _Muddling_ for Lispers and Schemers
   2
   3 This is an overview of the key differences between Muddle and other
   4 lispy languages. Good Muddle is easy for humans to read, but it is
   5 also tasteful: it efficiently matches the operation of the program to
   6 the operation of the Muddle interpreter. Each semantic note is
   7 followed by a review of the performance implications.
   8
   9 ## Objects
  10
  11 Muddle code deals exclusively with Muddle _objects_. Objects are
  12 always passed by value. An object can be a _scalar_ (e.g. `FIX`), with
  13 its value stored directly inside it, or a _collection_ (e.g. `LIST`,
  14 `VECTOR`, `TEMPLATE`), holding a reference to external data. Copying a
  15 collection object yields a new object that refers to the same
  16 collection _body_, but the object itself can have metadata that isn't
  17 shared -- like a `VECTOR`'s current length (see below).
  18
  19 ### Performance
  20
  21 An object is bigger than a pointer, but smaller enough to copy around
  22 easily. Every object is tagged with a type, so dispatching on types
  23 never requires following references. Collection bodies are allocated
  24 in heaplike spaces and managed by a tracing GC; copying references has
  25 no special overhead, but there is a write barrier when modifying
  26 objects stored in collections.
  27
  28 ## Calls
  29
  30 A `FUNCTION` or `FSUBR` may not evaluate all of its arguments; as a
  31 result, the normal call process of evaluating arguments before passing
  32 them to the callee is not practical. Arguments are passed unevaluated,
  33 and may then be evaluated by the callee (usually implicitly, based on
  34 its argument declarations). The main programmer-visible consequences
  35 of this are:
  36 * there are no "special forms"; first-class `FUNCTION`s can operate on
  37   syntax at runtime (and even modify it)
  38 * arguments are evaluated in a deterministic sequence (left-to-right
  39   is the default, but the callee can do anything; adhering to the
  40   Principle of Least Astonishment is recommended)
  41 * stack traces show arguments evaluated in the callee's frame
  42
  43 ### Performance
  44
  45 The by-name calling strategy combined with the ability to redefine any
  46 global allow incredible flexibility for debugging, but neither feature
  47 is recommended to be used widely in production. Accordingly, while the
  48 functionality is always available to interpreted programs, performance
  49 of code that doesn't use such dynamism is the implementation priority;
  50 certain unusual operations, like replacing an applicable function with
  51 a `"CALL"` function, may carry a high runtime cost.
  52
  53 ## Scope
  54
  55 Scoping is dynamic by default. You can create nested bindings to keep
  56 variables relatively local, e.g. with `"AUX"` pseudo-arguments. You
  57 can also create a full lexical scope with `BLOCK`.
  58
  59 ## `LIST`
  60
  61 Unlike other lisps that implement their "lists" with binary trees,
  62 Muddle's `LIST`s are intrusive singly-linked lists: the value is not
  63 behind a pointer like a "car", and *every* object has a `REST`
  64 field. Lists can share tails, but no object can otherwise be an
  65 element of more than one list, or in a list and also anywhere
  66 else. Cyclic or self-containing lists are possible, and must be
  67 handled with care.
  68
  69 ### Performance
  70
  71 `LIST`s can be very efficient for true lists (including lists of
  72 objects that may be `LIST`s, like Muddle code itself). The GC handles
  73 them specially in order to store objects next to their `REST`s
  74 whenever possible. To get efficient allocations, help the GC predict
  75 what you want by building your list idiomatically:
  76 * LIFO order (fastest): consecutive `CONS`es to one list
  77 * FIFO order (slow): `PUTREST` 1-element lists
  78 * fixed-size: `<LIST ...>` (including `MAPF ,LIST`), but if you expect
  79   to extend it right away, you should build it with `CONS` or
  80   `PUTREST`
  81
  82 ## `VECTOR`
  83
  84 Muddle's `VECTOR` is an array-structured container of objects. Like
  85 similar types in other languages, it supports efficient random access
  86 and expensive resizing to a larger allocation. More unusually, it has
  87 stack-like behavior: each `VECTOR` object maintains a current length
  88 that is less than or equal to the allocated length of its body. The
  89 length can be decreased with `REST` or increased (to at most the
  90 body's actual size) with `BACK` / `TOP`, which make objects accessible
  91 again, with their original values. Because all of its allocated
  92 objects are reachable with `TOP` (or potentially through a different
  93 `VECTOR` to the same body), its full allocation is always composed of
  94 initialized, live objects (although those objects can be `LOSE`s).
  95
  96 ### Performance
  97
  98 Choose a `VECTOR` if you want random access, or the stacklike
  99 features.
 100
 101 `REST` is non-destructive; if you won't be using the objects again,
 102 overwriting them with `LOSE`s will allow the GC to free anything they
 103 refer to.
 104
 105 ## User-defined data types
 106
 107 A common idiom for user-defined data types in Muddle is to use a type
 108 with a `TYPEPRIM` of `VECTOR`, and use `ATOM`s that resolve to `FIX`es
 109 as accessors.
 110
 111 ## Control flow
 112
 113 [coroutines, continuations, ...]
 114
 115 There is no TCE for normal calls, but `AGAIN` resembles a
 116 self-tailcall.
 117
 118 ## Misc
 119
 120 Reference semantics can be had by indirecting through a collection. If
 121 you need to accept a value by reference without knowing what kind of
 122 collection it's in, you want a `LOCATIVE`.
 123
 124 # License
 125
 126 Copyright (C) 2018 Keziah Wesley
 127
 128 You can redistribute and/or modify this file under the terms of the
 129 GNU Affero General Public License as published by the Free Software
 130 Foundation, either version 3 of the License, or (at your option) any
 131 later version.
 132
 133 This file is distributed in the hope that it will be useful, but
 134 WITHOUT ANY WARRANTY; without even the implied warranty of
 135 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 136 Affero General Public License for more details.
 137
 138 You should have received a copy of the GNU Affero General Public
 139 License along with this file. If not, see
 140 <http://www.gnu.org/licenses/>.