7 This implementation is meant as a tool for exploring the programming
8 model and method of Joy. Python seems like a great implementation
9 language for Joy for several reasons.
11 We can lean on the Python immutable types for our basic semantics and
12 types: ints, floats, strings, and tuples, which enforces functional
13 purity. We get garbage collection for free. Compilation via Cython. Glue
14 language with loads of libraries.
16 `Read-Eval-Print Loop (REPL) <https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop>`__
17 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
19 The main way to interact with the Joy interpreter is through a simple
20 `REPL <https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop>`__
21 that you start by running the package:
26 Joypy - Copyright © 2017 Simon Forman
27 This program comes with ABSOLUTELY NO WARRANTY; for details type "warranty".
28 This is free software, and you are welcome to redistribute it
29 under certain conditions; type "sharing" for details.
30 Type "words" to see a list of all words, and "[<name>] help" to print the
38 The ``<-top`` marker points to the top of the (initially empty) stack.
39 You can enter Joy notation at the prompt and a `trace of
40 evaluation <#The-TracePrinter.>`__ will be printed followed by the stack
58 Stacks (aka list, quote, sequence, etc.)
59 ========================================
61 In Joy, in addition to the types Boolean, integer, float, and string,
62 there is a single sequence type represented by enclosing a sequence of
63 terms in brackets ``[...]``. This sequence type is used to represent
64 both the stack and the expression. It is a `cons
65 list <https://en.wikipedia.org/wiki/Cons#Lists>`__ made from Python
71 import joy.utils.stack
74 print(inspect.getdoc(joy.utils.stack))
79 When talking about Joy we use the terms "stack", "quote", "sequence",
80 "list", and others to mean the same thing: a simple linear datatype that
81 permits certain operations such as iterating and pushing and popping
82 values from (at least) one end.
84 There is no "Stack" Python class, instead we use the `cons list`_, a
85 venerable two-tuple recursive sequence datastructure, where the
86 empty tuple ``()`` is the empty stack and ``(head, rest)`` gives the
87 recursive form of a stack with one or more items on it::
89 stack := () | (item, stack)
91 Putting some numbers onto a stack::
99 Python has very nice "tuple packing and unpacking" in its syntax which
100 means we can directly "unpack" the expected arguments to a Joy function.
104 def dup((head, tail)):
105 return head, (head, tail)
107 We replace the argument "stack" by the expected structure of the stack,
108 in this case "(head, tail)", and Python takes care of unpacking the
109 incoming tuple and assigning values to the names. (Note that Python
110 syntax doesn't require parentheses around tuples used in expressions
111 where they would be redundant.)
113 Unfortunately, the Sphinx documentation generator, which is used to generate this
114 web page, doesn't handle tuples in the function parameters. And in Python 3, this
115 syntax was removed entirely. Instead you would have to write::
119 return head, (head, tail)
122 We have two very simple functions, one to build up a stack from a Python
123 iterable and another to iterate through a stack and yield its items
124 one-by-one in order. There are also two functions to generate string representations
125 of stacks. They only differ in that one prints the terms in stack from left-to-right while the other prints from right-to-left. In both functions *internal stacks* are
126 printed left-to-right. These functions are written to support :doc:`../pretty`.
128 .. _cons list: https://en.wikipedia.org/wiki/Cons#Lists
131 The utility functions maintain order.
132 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
134 The 0th item in the list will be on the top of the stack and *vise
139 joy.utils.stack.list_to_stack([1, 2, 3])
152 list(joy.utils.stack.iter_stack((1, (2, (3, ())))))
163 This requires reversing the sequence (or iterating backwards) otherwise:
173 print(list(joy.utils.stack.iter_stack(stack)))
182 Purely Functional Datastructures.
183 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
185 Because Joy lists are made out of Python tuples they are immutable, so
186 all Joy datastructures are *`purely
187 functional <https://en.wikipedia.org/wiki/Purely_functional_data_structure>`__*.
189 The ``joy()`` function.
190 =======================
195 The ``joy()`` function is extrememly simple. It accepts a stack, an
196 expression, and a dictionary, and it iterates through the expression
197 putting values onto the stack and delegating execution to functions it
198 looks up in the dictionary.
200 Each function is passed the stack, expression, and dictionary and
201 returns them. Whatever the function returns becomes the new stack,
202 expression, and dictionary. (The dictionary is passed to enable e.g.
203 writing words that let you enter new words into the dictionary at
204 runtime, which nothing does yet and may be a bad idea, and the ``help``
211 print(inspect.getsource(joy.joy.joy))
216 def joy(stack, expression, dictionary, viewer=None):
217 '''Evaluate a Joy expression on a stack.
219 This function iterates through a sequence of terms which are either
220 literals (strings, numbers, sequences of terms) or function symbols.
221 Literals are put onto the stack and functions are looked up in the
222 disctionary and executed.
224 The viewer is a function that is called with the stack and expression
225 on every iteration, its return value is ignored.
227 :param stack stack: The stack.
228 :param stack expression: The expression to evaluate.
229 :param dict dictionary: A ``dict`` mapping names to Joy functions.
230 :param function viewer: Optional viewer function.
231 :rtype: (stack, (), dictionary)
236 if viewer: viewer(stack, expression)
238 term, expression = expression
239 if isinstance(term, Symbol):
240 term = dictionary[term]
241 stack, expression, dictionary = term(stack, expression, dictionary)
245 if viewer: viewer(stack, expression)
246 return stack, expression, dictionary
253 The ``joy()`` function accepts a "viewer" function which it calls on
254 each iteration passing the current stack and expression just before
255 evaluation. This can be used for tracing, breakpoints, retrying after
256 exceptions, or interrupting an evaluation and saving to disk or sending
257 over the network to resume later. The stack and expression together
258 contain all the state of the computation at each step.
260 The ``TracePrinter``.
261 ~~~~~~~~~~~~~~~~~~~~~
263 A ``viewer`` records each step of the evaluation of a Joy program. The
264 ``TracePrinter`` has a facility for printing out a trace of the
265 evaluation, one line per step. Each step is aligned to the current
266 interpreter position, signified by a period separating the stack on the
267 left from the pending expression ("continuation") on the right.
269 `Continuation-Passing Style <https://en.wikipedia.org/wiki/Continuation-passing_style>`__
270 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
272 One day I thought, What happens if you rewrite Joy to use
273 `CSP <https://en.wikipedia.org/wiki/Continuation-passing_style>`__? I
274 made all the functions accept and return the expression as well as the
275 stack and found that all the combinators could be rewritten to work by
276 modifying the expression rather than making recursive calls to the
286 print(inspect.getdoc(joy.parser))
291 This module exports a single function for converting text to a joy
292 expression as well as a single Symbol class and a single Exception type.
294 The Symbol string class is used by the interpreter to recognize literals
295 by the fact that they are not Symbol objects.
300 term = int | float | string | '[' joy ']' | symbol
302 A Joy expression is a sequence of zero or more terms. A term is a
303 literal value (integer, float, string, or Joy expression) or a function
304 symbol. Function symbols are unquoted strings and cannot contain square
305 brackets. Terms must be separated by blanks, which can be omitted
306 around square brackets.
309 The parser is extremely simple, the undocumented ``re.Scanner`` class
310 does most of the tokenizing work and then you just build the tuple
311 structure out of the tokens. There's no Abstract Syntax Tree or anything
316 print(inspect.getsource(joy.parser._parse))
323 Return a stack/list expression of the tokens.
331 stack[-1].append(frame)
336 raise ParseError('Extra closing bracket.')
337 frame[-1] = list_to_stack(frame[-1])
341 raise ParseError('Unclosed bracket.')
342 return list_to_stack(frame)
346 That's pretty much all there is to it.
350 joy.parser.text_to_expression('1 2 3 4 5') # A simple sequence.
357 (1, (2, (3, (4, (5, ())))))
363 joy.parser.text_to_expression('[1 2 3] 4 5') # Three items, the first is a list with three items
370 ((1, (2, (3, ()))), (4, (5, ())))
376 joy.parser.text_to_expression('1 23 ["four" [-5.0] cons] 8888') # A mixed bag. cons is
377 # a Symbol, no lookup at
378 # parse-time. Haiku docs.
385 (1, (23, (('four', ((-5.0, ()), (cons, ()))), (8888, ()))))
391 joy.parser.text_to_expression('[][][][][]') # Five empty lists.
398 ((), ((), ((), ((), ((), ())))))
404 joy.parser.text_to_expression('[[[[[]]]]]') # Five nested lists.
411 ((((((), ()), ()), ()), ()), ())
418 The Joy library of functions (aka commands, or "words" after Forth
419 usage) encapsulates all the actual functionality (no pun intended) of
420 the Joy system. There are simple functions such as addition ``add`` (or
421 ``+``, the library module supports aliases), and combinators which
422 provide control-flow and higher-order operations.
428 print(' '.join(sorted(joy.library.initialize())))
433 != % & * *fraction *fraction0 + ++ - -- / // /floor < << <= <> = > >= >> ? ^ _Tree_add_Ee _Tree_delete_R0 _Tree_delete_clear_stuff _Tree_get_E abs add anamorphism and app1 app2 app3 at average b binary bool branch ccons choice clear cleave cmp codireco concat cond cons dinfrirst dip dipd dipdd disenstacken div divmod down_to_zero drop dup dupd dupdd dupdip dupdipd enstacken eq first first_two flatten floor floordiv fork fourth gcd ge genrec getitem gt help i id ifte ii infra inscribe le least_fraction loop lshift lt make_generator map max min mod modulus mul ne neg not nullary of or over pam parse pick pm pop popd popdd popop popopd popopdd pow pred primrec product quoted range range_to_zero rem remainder remove rest reverse roll< roll> rolldown rollup round rrest rshift run second select sharing shunt size sort sqr sqrt stack step step_zero stuncons stununcons sub succ sum swaack swap swoncat swons tailrec take ternary third times truediv truthy tuck unary uncons unique unit unquoted unstack unswons void warranty while words x xor zip •
436 Many of the functions are defined in Python, like ``dip``:
440 print(inspect.getsource(joy.library.dip))
447 def dip(stack, expression, dictionary):
449 The dip combinator expects a quoted program on the stack and below it
450 some item, it hoists the item into the expression and runs the program
451 on the rest of the stack.
459 (quote, (x, stack)) = stack
460 expression = (x, expression)
461 return stack, concat(quote, expression), dictionary
465 Some functions are defined in equations in terms of other functions.
466 When the interpreter executes a definition function that function just
467 pushes its body expression onto the pending expression (the
468 continuation) and returns control to the interpreter.
472 print(joy.library.definitions)
478 *fraction [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
479 *fraction0 concat [[swap] dip * [*] dip] infra
480 anamorphism [pop []] swap [dip swons] genrec
481 average [sum 1.0 *] [size] cleave /
482 binary nullary [popop] dip
483 cleave fork [popd] dip
484 codireco cons dip rest cons
485 dinfrirst dip infra first
486 unstack ? [uncons ?] loop pop
487 down_to_zero [0 >] [dup --] while
489 enstacken stack [clear] dip
490 flatten [] swap [concat] step
492 gcd 1 [tuck modulus dup 0 >] loop pop
493 ifte [nullary not] dipd branch
495 least_fraction dup [gcd] infra [div] concat map
496 make_generator [codireco] ccons
497 nullary [stack] dinfrirst
501 product 1 swap [*] step
503 range [0 <=] [1 - dup] anamorphism
504 range_to_zero unit [down_to_zero] infra
506 size 0 swap [pop ++] step
508 step_zero 0 roll> step
511 ternary unary [popop] dip
514 while swap [nullary] cons dup dipd concat loop
518 Currently, there's no function to add new definitions to the dictionary
519 from "within" Joy code itself. Adding new definitions remains a
520 meta-interpreter action. You have to do it yourself, in Python, and wash
521 your hands afterward.
523 It would be simple enough to define one, but it would open the door to
524 *name binding* and break the idea that all state is captured in the
525 stack and expression. There's an implicit *standard dictionary* that
526 defines the actual semantics of the syntactic stack and expression
527 datastructures (which only contain symbols, not the actual functions.
528 Pickle some and see for yourself.)
530 "There should be only one."
531 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
533 Which brings me to talking about one of my hopes and dreams for this
534 notation: "There should be only one." What I mean is that there should
535 be one universal standard dictionary of commands, and all bespoke work
536 done in a UI for purposes takes place by direct interaction and macros.
537 There would be a *Grand Refactoring* biannually (two years, not six
538 months, that's semi-annually) where any new definitions factored out of
539 the usage and macros of the previous time, along with new algorithms and
540 such, were entered into the dictionary and posted to e.g. IPFS.
542 Code should not burgeon wildly, as it does today. The variety of code
543 should map more-or-less to the well-factored variety of human
544 computably-solvable problems. There shouldn't be dozens of chat apps, JS
545 frameworks, programming languages. It's a waste of time, a `fractal
547 attack <https://en.wikipedia.org/wiki/Thundering_herd_problem>`__ on
550 Literary Code Library
551 ^^^^^^^^^^^^^^^^^^^^^
553 If you read over the other notebooks you'll see that developing code in
554 Joy is a lot like doing simple mathematics, and the descriptions of the
555 code resemble math papers. The code also works the first time, no bugs.
556 If you have any experience programming at all, you are probably
557 skeptical, as I was, but it seems to work: deriving code mathematically
558 seems to lead to fewer errors.
560 But my point now is that this great ratio of textual explanation to wind
561 up with code that consists of a few equations and could fit on an index
562 card is highly desirable. Less code has fewer errors. The structure of
563 Joy engenders a kind of thinking that seems to be very effective for
564 developing structured processes.
566 There seems to be an elegance and power to the notation.