stack ← {repl←0} ##.joy program             ⍝ Subset of the Joy language.

Evaluates character-vector Joy [program]:

      joy'2 3 4 + *'                ⍝ 2×3+4
14
      joy'[1 2 3 4 5] 0 [+] fold'   ⍝ +/⍳5
15
      joy'[1 2 3 4 5] [dup *] map'  ⍝ (⍳5)*2
[1 4 9 16 25]

If an error occurs,  the stack and operator stream are returned with a │ between
the offending operator and its argument(s).

      joy'2 3 + 0 / 2 *'            ⍝ divide-by-0 error
5 0│/ 2 *

If optional left argument [repl←0] is set, [joy]  prompts  for  additional input
after evaluating its argument expression. Such an interactive session is termin-
ated by operator: quit.

      1 joy'2 dup +'                ⍝ 1 joy ... => interactive session:
                   4│[] cons        (* ⊂,⍵      *)
                 [4]│[2 3]          (* ⍵,⊂2 3   *)
           [4] [2 3]│swap           (* ⌽ ⍵      *)
           [2 3] [4]│concat         (* ⊃,/⍵     *)
             [2 3 4]│1 swons        (* ⍵ ,⍨ ⊂1  *)
           [1 2 3 4]│[10 *] map     (* 10ר⍵    *)
       [10 20 30 40]│1 [*] fold     (* ×/⍵      *)
              240000│quit           (* ⎕OFF ⍵   *)
240000

The Joy machine  consists  of a right-growing  stack of values to the left and a
stream of operators to the right of separator: │.  The operator  immediately  to
the right of the separator interacts with the item(s) to its left to reduce  the
state of the machine.  This process repeats  until either an error occurs or the
operator stream is exhausted. At this point, if left argument [repl] is 0, [joy]
terminates  returning  the  current  machine  state.  Otherwise, if [repl] is 1,
further input is solicited until operator <quit> is entered, as shown above.

References
----------
Joy Programming Language:
http://www.latrobe.edu.au/humanities/research/research-projects/past-projects/joy-programming-language

Various Joy resources from Kevin Albrecht:
http://www.kevinalbrecht.com/code/joy-mirror/joy.html

Concatenative Languages:
http://concatenative.org/wiki/view/Concatenative%20language

Stevan Apter: Functional Programming in Joy and K:
http://archive.vector.org.uk/art10000360

Stevan Apter: Interview with Manfred von Thun, the originator of Joy:
http://archive.vector.org.uk/art10000350

Manfred von Thun: Joy in Joy - a metacircular interpreter:
http://www.kevinalbrecht.com/code/joy-mirror/jp-joyjoy.html

Stevan Apter's concatenative language XY has roots in both Joy and K:
http://nsl.com/k/xy/xy.htm

Brent Kerby: The Theory of Concatenative Combinators:
http://tunes.org/%7Eiepos/joy.html

Thanks to Stevan Apter for references.

"Joy is a functional programming language which is not based on the  application
 of functions to arguments but on the composition of functions.  It does not use
 lambda-abstraction of expressions but instead it uses quotation of expressions.
 A large number of combinators are used to perform dequotation,  they  have  the
 effect of higher order functions.  Several of them can be used to eliminate re-
 cursive definitions. Programs in Joy are compact and often look just like post-
 fix notation.  Writing  programs  and reasoning about them is made easy because
 there is no substitution of actual for formal parameters." Manfred von Thun.

Playing with Joy
----------------
In an interactive session the separator, which is  placed  initially  at  column
position ⌊⎕PW÷4, may be adjusted at any time by adding or removing spaces to its
left during input:

      1 joy''
                    │2 3 +  (* separator starts at ⌊⎕pw÷4                   *)
                   5│       (* move separator to left by deleting blanks    *)
        5│
        5│2 +               (* separator continues here until moved again   *)
        7│
             7│dup *        (* and so on                                    *)
            49│
            49│quit         (* remember to quit !                           *)
49

Library
-------
Script ##.scripts._joy contains a number of examples of simple Joy programs:

    fac     factorial:              ⍵ fac → !⍵
    fac-i   iterative factorial         ..
    fac-r   recursive factorial         ..
    fac-y   factorial Y                 ..
    fib     fibonacci:              ⍵ fib → ⍵'th fibonacci number
    fib-i   iterative fibonacci:        ..      ..      ..
    fib-r   recursive fibonacci         ..      ..      ..
    2∧      two-to-the-power-of:    2*⍵
    seq     number sequence         [m..n]
    ack     recursive Ackermann
    ack-y   Ackermann Y
    qsort   Quicksort               ⍵[⍋⍵]
    Y       Y-combinator            [f]Y → f[f]Y
    →       clear the stack

Tracing
¯¯¯¯¯¯¯
The evaluation of a ⊢···⊣ bracketed expression is traced. Traced output is dist-
inguished from regular output by leading dots ···.  Notice the traced  expansion
of defined names (such as append == reverse cons reverse) in the following:

      1 joy scripts._joy
                    │4 [1 2 3] append 0 [+] fold    (* untraced *)
                  10│→                              (* )reset   *)
                    │
                    │⊢4 [1 2 3] append⊣ 0 [+] fold  (* partial tracing *)
····················│4 [1 2 3] append ⊣ 0 [+] fold
···················4│[1 2 3] append ⊣ 0 [+] fold
···········4 [1 2 3]│append ⊣ 0 [+] fold
···········4 [1 2 3]│reverse cons reverse ⊣ 0 [+] fold
···········4 [3 2 1]│cons reverse ⊣ 0 [+] fold
···········[4 3 2 1]│reverse ⊣ 0 [+] fold
···········[1 2 3 4]│⊣ 0 [+] fold
                  10│quit
10
      joy'⊢3[1][*]primrec'                  ⍝ non-interactive [repl←0] trace
····················│3 [1] [*] primrec
···················3│[1] [*] primrec
···············3 [1]│[*] primrec
···········3 [1] [*]│primrec
···········2 [1] [*]│primrec 3 swap *
···········1 [1] [*]│primrec 2 swap * 3 swap *
···········0 [1] [*]│primrec 1 swap * 2 swap * 3 swap *
···················1│1 swap * 2 swap * 3 swap *
·················1 1│swap * 2 swap * 3 swap *
·················1 1│* 2 swap * 3 swap *
···················1│2 swap * 3 swap *
·················1 2│swap * 3 swap *
·················2 1│* 3 swap *
···················2│3 swap *
·················2 3│swap *
·················3 2│*
6

Here is a list of supported operators. Those marked "*" are implemented in Joy:

supported operators ──┐
    top of stack ───┐ │
                    ↓ ↓
                    a│dup      →                a a│
*                 b a│dupd     →              b b a│
                  b a│pop      →                  b│
*                 b a│popd     →                  a│
*               c b a│pop2     →                  c│
*                   a│unit     →                [a]│
                  b a│swap     →                a b│
*               c b a│swapd    →              b c a│
*               c b a│rotate   →              a b c│
*               c b a│rollup   →              a c b│
*               c b a│rolldown →              b a c│
                a [b]│cons     →              [a b]│
*               a [b]│append   →              [b a]│
                [a b]│uncons   →              a [b]│
                [b] a│swons    →              [a b]│
*           a [f] [g]│cleave   →                   │a f a g
              [a] [b]│concat   →              [a b]│
*           x [a] [b]│enconcat →            [a x b]│
*         [a b] [f] g│shunt    →                   │a f g b f g
*             [a] [b]│swoncat  →              [b a]│
                a [f]│dip      →                   │f a
*             b a [f]│dip2     →                   │f b a
*           c b a [f]│dip3     →                   │f c b a
              [a b c]│reverse  →            [c b a]│
*             [a] [f]│infra    →                  [│a f]
        [a b ...] [f]│step     →                   │a f b f ...
*       [a b ...] [f]│map      →        [f¨a b ...]│
*     [a b ...] i [f]│fold     →      [f/i,a b ...]│
*       [a b ...] [f]│filter   →  [{f¨⍵)/⍵}a b ...]│
*       [a b ...] [f]│split    →                   │
              n [ops]│times    →              ops⍣n│
            b [t] [f]│branch   →                   │{b:t⋄f}
*         [b] [t] [f]│ifte     →                   │{b:t⋄f}
*         ... b a [f]│nullary  →            ... b a│a f
*       ... c b a [f]│unary    →            ... c b│a f
*    [[p]a][[q]b[d]] │cond     →                   │p:a⋄q:b⋄d
                    a│null     →              a∊0[]│
                    a│small    →      a∊0 1[][atom]│
               .. b a│stack    →    .. b a [a b ..]│
             .. [a b]│unstack  →                b a│
*             [a ...]│size     →                 ≢⍵│
                    n│succ     →                n+1│
                    n│pred     →                n-1│
                  [a]│i        →                   │a
                    a│id       →                  a│
            n [a] [f]│primrec  →      (n-1) [a] [f]│primrec n swap f
        [x y] [a] [f]│primrec  →        [y] [a] [f]│primrec x swap f
*      true [B][R][J]│linrec   →                   │B
*     false [B][R][J]│linrec   →                   │R [T][B][R][J]linrec J
     0/[] [B] [F] [J]│binrec   →                   │B
    n/[a] [B] [F] [J]│binrec   →              n/[a]│F [B] [F] [J] binrec
                     │                             │  [B] [F] [J] binrec J
                  m n│+        →                m+n│
                  m n│-        →                m-n│
                  m n│*        →                m×n│
                  m n│/        →                m÷n│
                  m n│rem      →               ⌊m÷n│
                  m n│div      →              0 n⊤m│
                  m n│<        →                m<n│
                  m n│<=       →                m≤n│
                  m n│=        →                m=n│
                  m n│>=       →                m≥n│
                  m n│>        →                m>n│
                  m n│!=       →                m≠n│
*                   b│not      →               {!⍵}│

In addition  to these  operators, keyword DEFINE is used to name word sequences.
For example primitive combinator "swons" could have been defined:

    DEFINE swons == swap cons .     (* note the terminating "." *)

Bugs and restrictions
---------------------
- Only boolean and whole, non-negative "natural" numbers are supported: 0 1 2 ..
- The only aggregate form is the List; there is no support for sets or strings.
- In interactive mode, only single-line expressions may be entered.

Requirements
------------
[joy] calls operator →nats← for its natural-number arithmetic.

Technical notes
---------------
[joy] is an exercise in tail-calling.  In essence, it's just  a  read-eval-print
loop (or "REPL" see: http://en.wikipedia.org/wiki/Read-eval-print_loop) of which
the principal components are inner dfns: read, eval and prt:

        ┌──read─→─eval─→─prt──┐
        │                     │
        └───────←──────←──────┘

Each function takes (and notionally returns) the tuple (stk I ops) where:

    stk: Items on Joy's stack, implemented as a →list←,
      I: Position of │-separator in interactive session.
    ops: Stream of yet-to-be-applied operators, also a →list←,

.. together with an association list (see →alists←) as left argument, which maps
defined names to their values.

So we can define the type of each of these (read, eval, prt) functions as:

    read eval prt :: State ← Dict ∇ State       ⍝ :: "are of type"

Defining names (with capital letters) for types helps to simplify:

      joy   ::  ⍞ ← ∇ ⍞                         ⍝ type of this function
     Repl   :=  State ← Dict ∇ State            ⍝ state reduction
     Oper   :=  State ← Dict ∇ Sargs            ⍝ primitive operator
    Sargs   :=  Stack, [Value]                  ⍝ vector: (⊂stack),args
     Dict   :=  [Name] [Oseq]                   ⍝ name-value association tuple
    State   :=  Stack Disp Oseq                 ⍝ machine state
     Disp   :=  offset                          ⍝ (-ive during tracing)
     List ⍵ :=  '∘' | ⍵ (List ⍵)                ⍝ f(fr(frr ...))
     Oseq   :=  Word | List Word | List Oseq    ⍝ operator sequence
    Stack   :=  List Value                      ⍝ value stack
    Value   :=  Word  | List Value              ⍝ value
     Word   :=  ⍞                               ⍝ character vector

Within the code,  the convention for naming the first few items of lists borrows
from  Lisp's: car cdr cadr cddr ... but using Joy's terms  "first"  and  "rest".
So: f r fr rr ... for first, rest, first-of-rest rest-of-rest and so forth.

Principal function "eval" is effectively a Select structure with a case for each
of the supported operators.

On entry, the  top few stack items and first operator are named and a case-match
function is defined:

    stk I(op ops)←⍵                     ⍝ stack and next operator
    ...
    f(fr rr)←f r←stk                    ⍝ top few stack items
    c←{op≡⍵~' '}                        ⍝ case match ignoring blanks

The line corresponding to each case has this structure:

        c oper: ⍺(patn rgs efn)⍵
where:
         c: Matching function.
      oper: Name of operator to match: 'cons', 'swap', etc.
         ⍺: Current definition dictionary.
      patn: A vector, the same length as the required number of arguments with
            expected types:
                0: number
                1: non-zero number
                ∧: boolean (true or false)
                ⌷: list
                ⍞: non-empty list
                *: anything
       rgs: A dyadic operator, which checks the conformability (type and number)
            of arguments  and  then for failure calls "err" or for success calls
            its continuation function efn:
       efn: Evaluation function to call next.
         ⍵: Operator-stream, including current operator.

For example:

    c'swons  ':⍺('⌷*'rgs{⍺ ∆((f fr)rr)I ops})⍵     ⍝    [a] b → [b a]
    │ │        │ │   │  │                    │
    │ │        │ │   │  │                    └── operator list
    │ │        │ │   │  └─────────────────── evaluation fn for remaining ops
    │ │        │ │   └────────────────────── argument conformability checking fn
    │ │        │ └────────────────────────── argument pattern vector
    │ │        └──────────────────────────── definitions
    │ └───────────────────────────────────── operator
    └─────────────────────────────────────── operator matching function

Performance:

For no particular reason, the arrangement of the cases within subfunction [eval]
has been optimised for "Ackermann's function" (see ##.scripts._joy). The follow-
ing operator counts are for the reduction of "3 3 ack", where * indicates a def-
ined (non-primitive) operator:

    dip      21942
    cons     20754
    i        10913
    swap      9726
    branch    8539
*   nullary   8539
*   swoncat   8539
    unstack   8539
    stack     8539
    concat    8539
    uncons    7352
    small     4863
*   cond      4863
    pop       3677
    null      3676
*   ack       2432
    pred      2431
    succ      1188
    dup       1187
    DEFINE       1
            ------
    total   121866  (omitting * defined operators)
            ------
(muse:

    Case selection within subfunction [eval] is a sequence of  guards,  each  of
    which applies  the  same  matching  function to a number of constant values.
    This structure occurs frequently enough to make it an attractive  optimisat-
    ion for the dfn evaluator. Such an optimisation might spot the sequence:

        c←{op≡⍵~' '}
        c'dip   ': ...      ⍝ case[0]
        c'cons  ': ...      ⍝  ..  1
        c'i     ': ...      ⍝  ..  2
        c'swap  ': ...      ⍝  ..  3
        ...                 ⍝  ..  n

    and, noting that c is a pure function with no side-effects, convert it to:

        → ((c¨'dip   ' 'cons  ' 'i     ' 'swap  ' ...)⍳1)⊃ L0 L1 L2 L3 ... Ldflt

    where L0 L1 ... Ldflt are internal labels for the corresponding lines.

    Then a clever optimiser might transform the above expression:

        CV ←  'dip   ' 'cons  ' 'i     ' 'swap  ' ...         ⍝ vector of cases
        LV ←   L0       L1       L2       L3      ...  Ldflt  ⍝ vector of labels

        →((c¨CV)⍳1)⊃LV                  ⍝ expand function c
           ¯
    ->  →(({op≡⍵~' '}¨CV)⍳1)⊃LV         ⍝ separation: {f g ⍵}¨ → {f ⍵}¨ {g ⍵}¨
           ¯¯¯¯¯¯¯¯¯¯
    ->  →(({op≡⍵}¨{⍵~' '}¨CV)⍳1)⊃LV     ⍝ ⎕FX-time evaluation: {⍵~' '}¨CV → CV1
                  ¯¯¯¯¯¯¯¯¯¯
    ->  →(({op≡⍵}¨ CV1)⍳1)⊃LV           ⍝ dfn to tacit form: {A f ⍵} → A∘f
           ¯¯¯¯¯¯
    ->  →((op∘≡¨ CV1)⍳1)⊃LV             ⍝ decomposition:  A∘f¨ → (⊂A)f¨
           ¯¯¯¯¯
    ->  →(((⊂op)≡¨ CV1)⍳1)⊃LV           ⍝ match-each: (⊂A)≡¨B → B∊⊂A
           ¯¯¯¯¯¯¯¯¯¯¯
    ->  →((CV1∊⊂op)⍳1)⊃LV               ⍝ iota-1: (A∊⊂B)⍳1 → A⍳⊂B
          ¯¯¯¯¯¯¯¯¯¯¯
    ->  →(CV1⍳⊂op)⊃LV                   ⍝ which is significantly faster.
)

Joy in Joy
----------
While some of Joy's primitive operations are coded directly in APL,  many (those
marked (*) in the table above) are coded in Joy itself - see  towards the end of
the code, via the link ##.joy  at the very top of this page.  The choice of this
split between primitive and synthetic operators is an interesting one, amounting
to choosing a "basis": a set of operators on which all the others are built. The
split chosen for this implementation, as well as the Joy-coding of the operators
reflect JMS's inexperience with the language and both could be greatly improved.
For more about this, see the link to Manfred von Thun's Metacircular Interpreter
above.

Examples:

      joy '2 3 +  4 5 *'                ⍝ 2+3 ⋄ 4×5
5 20
                                        ⍝ Interactive Joy session:
      1 joy scripts._joy                ⍝ see: ##.scripts._joy
                    │2 3 +
                   5│4 5 *
                5 20│swap
                20 5│/
                   4│→                  (* clear stack *)
                    │
                    │                   (* move separator to the right: *)
                                    │
                                    │0 9 seq                    (* ⍳10      *)
               [0 1 2 3 4 5 6 7 8 9]│→                          (* →        *)
                                    │0 11 seq [fib] map         (* fib¨⍳12  *)
      [0 1 1 2 3 5 8 13 21 34 55 89]│0 [+] fold                 (* +/⍵      *)
                                 232│→                          (* →        *)
                                    │DEFINE sum == 0 [+] fold . (* sum ← +/ *)
                                    │0 999 seq sum              (* +/⍳1000  *)
                              499500│→ 30 fac                   (* !30      *)
   265252859812191058636308480000000│→ 100 2∧                   (* 2*100    *)
     1267650600228229401496703205376│→ 3 3 ack                  (* 3 ack 3  *)
                                  61│→ [3 1 4 1 5] qsort        (* ⍵[⍋⍵]    *)
                         [1 1 3 4 5]│→ quit                     (* )off     *)

See also: nats lisp bf list repl

Back to: contents

Back to: Workspaces