Version 0.5.0
Not negative.
n !-
----------- n < 0
false
n !-
---------- n >= 0
true
Return a Boolean value indicating if a number is greater than or equal to zero.
... b a <{}
-----------------
... [] b a
Tuck an empty list just under the first two items on the stack.
... a <{}
----------------
... [] a
Tuck an empty list just under the first item on the stack.
Is the item on the top of the stack "truthy"?
You often want to test the truth value of an item on the stack without consuming the item.
combinator
Build a list of values from a generator program G and a stopping
predicate P.
[P] [G] anamorphism
-----------------------------------------
[P] [pop []] [G] [dip swons] genrec
The range function generates a list of the integers from 0 to n - 1:
[0 <=] [-- dup] anamorphism
joy? 5
5
joy? [0 <=] [-- dup]
5 [0 <=] [-- dup]
joy? anamorphism
[4 3 2 1 0]
Note that the last value generated (0) is at the bottom of the list. See the Recursion Combinators notebook.
combinator
Short-circuiting Boolean AND
Accept two quoted programs, run the first and expect a Boolean value, if
it's true pop it and run the second program (which should also return a
Boolean value) otherwise pop the second program (leaving false on the
stack.) The quoted programs are run with nullary.
[A] [B] and
----------------- A -> true
B
[A] [B] and
----------------- A -> false
false
TODO: this is derived in one of the notebooks I think, look it up and link to it, or copy the content here.
combinator
"apply one"
Given a quoted program on TOS and anything as the second stack item run the program without disturbing the rest of the stack and replace the two args with the first result of the program.
... x [Q] app1
---------------------------------
... [x ...] [Q] infra first
This is the same effect as the unary combinator.
Just a specialization of nullary really. Its parallel cousins
are more useful.
combinator
Like app1 with two items.
... y x [Q] . app2
-----------------------------------
... [y ...] [Q] . infra first
[x ...] [Q] infra first
Unlike app1, which is essentially an alias for unary,
this function is not the same as binary. Instead of running
one program using exactly two items from the stack and pushing one
result (as binary does) this function takes two items from the
stack and runs the program twice, separately for each of the items, then
puts both results onto the stack.
This is not currently implemented as parallel processes but it can (and should) be done.
combinator
Like app1 with three items.
... z y x [Q] . app3
-----------------------------------
... [z ...] [Q] . infra first
[y ...] [Q] infra first
[x ...] [Q] infra first
combinator
Like app1 with any number of items.
... xN ... x2 x1 x0 [Q] n . appN
--------------------------------------
... [xN ...] [Q] . infra first
...
[x2 ...] [Q] infra first
[x1 ...] [Q] infra first
[x0 ...] [Q] infra first
This function takes a quoted function Q and an integer and runs the
function that many times on that many stack items. See also app2.
combinator
Run two quoted programs
[P] [Q] b
---------------
P Q
This combinator may seem trivial but it comes in handy.
combinator
Run a quoted program using exactly two stack values and leave the first item of the result on the stack.
... y x [P] binary
-----------------------
... a
Runs any other quoted function and returns its first result while consuming exactly two items from the stack.
built-in
Convert the item on the top of the stack to a Boolean value.
For integers 0 is false and any other number is true; for lists the
empty list is false and all other lists are true.
combinator built-in
Use a Boolean value to select and run one of two quoted programs.
false [F] [T] branch
--------------------------
F
true [F] [T] branch
-------------------------
T
a b c d [...] ccccons
---------------------------
[a b c d ...]
Do cons four times.
Use a Boolean value to select one of two items.
a b false choice
----------------------
a
a b true choice
---------------------
b
It's a matter of taste whether you implement this in terms of branch or
the other way around.
combinator
Run two programs in parallel, consuming one additional item, and put their results on the stack.
... x [A] [B] cleave
------------------------
... a b
1 2 3 [+] [-] cleave
--------------------------
1 2 5 -1
One of a handful of useful parallel combinators.
combinator
Run two programs in parallel, consuming two additional items, and put their results on the stack.
... x y [A] [B] clop
--------------------------
... a b
Like cleave but consumes an additional item from the stack.
1 2 3 4 [+] [-] clop
--------------------------
1 2 7 -1
combinator
Take two values and three quoted programs on the stack and run one of the three depending on the results of comparing the two values.
a b [G] [E] [L] cmp
------------------------- a > b
G
a b [G] [E] [L] cmp
------------------------- a = b
E
a b [G] [E] [L] cmp
------------------------- a < b
L
combinator
Take a quoted program from the stack, cons the next item onto it, then
dip the whole thing under what was the third item on the stack.
a b [F] . codi
--------------------
b . F a
This is one of those weirdly specific functions that turns out to be useful in a few places.
combinator
This is part of the make-generator function. You would not use this
combinator directly.
See make-generator and the
"Generator Programs" notebook
as well as
Recursion Theory and Joy by Manfred von Thun.
built-in
Concatinate two lists.
[a b c] [d e f] concat
----------------------------
[a b c d e f]
built-in
Given an item and a list, append the item to the list to make a new list.
a [...] cons
------------------
[a ...]
Cons is a venerable old function from Lisp.
Its inverse operation is uncons.
combinator built-in
The dip combinator expects a quoted program on the stack and below it
some item, it hoists the item into the expression and runs the program
on the rest of the stack.
... x [Q] . dip
---------------------
... . Q x
This along with infra are enough to update any datastructure.
See the "Traversing Datastructures with Zippers" notebook.
Note that the item that was on the top of the stack (x in the example above)
will not be treated specially by the interpreter when it is reached
again. This is something of a footgun. My advice is to avoid putting
bare unquoted symbols onto the stack, but then you can't use symbols as
"atoms" and also use dip and infra to operate on compound
datastructures with atoms in them. This is a kind of side-effect of the
Continuation-Passing Style. The dip combinator could "set aside" the
item and replace it after running Q but that means that there is an
"extra space" where the item resides while Q runs. One of the nice
things about CPS is that the whole state is recorded in the stack and
pending expression (not counting modifications to the dictionary.)
combinator
Like dip but expects two items.
... y x [Q] . dipd
-------------------------
... . Q y x
See dip.
combinator
Like dip but expects three items. :
... z y x [Q] . dipdd
-----------------------------
... . Q z y x
See dip.
combinator
Like dip but expects four items. :
... z y x w [Q] . dipddd
-------------------------------
... . Q z y x w
See dip.
The disenstacken function expects a list on top of the stack and makes
that the stack discarding the rest of the stack.
1 2 3 [4 5 6] disenstacken
--------------------------------
6 5 4
Note that the order of the list is not changed, it just looks that way because the stack is printed with the top on the right while lists are printed with the top or head on the left.
Given a number greater than zero put all the Natural numbers (including zero) less than that onto the stack.
3 down_to_zero
--------------------
3 2 1 0
Expects an integer and a quote on the stack and returns the quote with n items removed off the top.
[a b c d] 2 drop
----------------------
[c d]
combinator
Apply a function F and dup the item under it on the stack.
a [F] dupdip
------------------
a F a
a [F] dupdip
a [F] dupd dip
a [F] [dup] dip dip
a dup [F] dip
a a [F] dip
a F a
A very common and useful combinator.
combinator
Run a copy of program F under the next item down on the stack.
a [F] dupdipd
-------------------
F a [F]
Expects a list on the stack and pushes true if it's empty and false otherwise.
It doesn't consume the list.
Put the stack onto the stack replacing the contents of the stack.
... a b c enstacken
-------------------------
[c b a ...]
This is a destructive version of stack. See the note under
disenstacken about the apparent but illusory reversal of the stack.
built-in
Compare the two items on the top of the stack for equality and replace them with a Boolean value.
a b eq
-------------
Boolean
(a = b)
Replace a list with its first two items.
[a b ...] first_two
-------------------------
a b
Given a list of lists, concatinate them.
[[1 2] [3 [4] 5] [6 7]] flatten
-------------------------------------
[1 2 3 [4] 5 6 7]
Note that only one "level" of lists is flattened. In the example above
[4] is not unquoted.
combinator
Run two quoted programs in parallel and replace them with their results.
... [F] [G] fork
----------------------
... f g
The basic parallelism combinator, the two programs are run independently.
Replace a list with its fourth item.
[a b c d ...] fourth
--------------------------
d
Take two integers from the stack and replace them with their Greatest Common Denominator.
Euclid's Algorithm
built-in
Greater-than-or-equal-to comparison of two numbers.
a b ge
--------------
Boolean
(a >= b)
combinator
General Recursion Combinator.
[if] [then] [rec1] [rec2] genrec
---------------------------------------------------------------------
[if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
Note that this definition includes the genrec symbol itself, it is
self-referential. This is possible because the definition machinery does
not check that symbols in defs are in the dictionary. genrec is the
only self-referential definition.
See the Recursion Combinators notebook.
From "Recursion Theory and Joy" by Manfred von Thun:
"The genrec combinator takes four program parameters in addition to whatever data parameters it needs. Fourth from the top is an if-part, followed by a then-part. If the if-part yields true, then the then-part is executed and the combinator terminates. The other two parameters are the rec1-part and the rec2-part. If the if-part yields false, the rec1-part is executed. Following that the four program parameters and the combinator are again pushed onto the stack bundled up in a quoted form. Then the rec2-part is executed, where it will find the bundled form. Typically it will then execute the bundled form, either with i or with app2, or some other combinator."
The way to design one of these is to fix your base case [then] and the
test [if], and then treat rec1 and rec2 as an else-part
"sandwiching" a quotation of the whole function.
For example, given a (general recursive) function F:
F == [I] [T] [R1] [R2] genrec
If the [I] if-part fails you must derive R1 and R2 from: :
... R1 [F] R2
Just set the stack arguments in front, and figure out what R1 and R2
have to do to apply the quoted [F] in the proper way. In effect, the
genrec combinator turns into an [ifte] combinator with a quoted copy of
the original definition in the else-part:
F == [I] [T] [R1] [R2] genrec
== [I] [T] [R1 [F] R2] ifte
Tail recursive functions are those where R2 is the i combinator:
P == [I] [T] [R] tailrec
== [I] [T] [R [P] i] ifte
== [I] [T] [R P] ifte
Expects an integer and a quote on the stack and returns the item at the nth position in the quote counting from 0.
[a b c d] 2 getitem
-------------------------
c
If the number isn't a valid index into the quote getitem will cause
some sort of problem (the exact nature of which is
implementation-dependant.)
Expect a number on the top of the stack and cons that many items from under it onto a new list.
a b c d e 3 grabN
-----------------------
a b [c d e]
A weird function used in app2 that does this:
... 1 2 3 4 5 grba
-------------------------------
... 1 2 3 [4 3 2 1 ...] 5
It grabs the stack under the top item, and substitutes it for the second item down on the stack.
This function "grabs" an item from the stack along with a copy of the stack.
It's part of the app2 definition.
built-in
Greater-than comparison of two numbers.
a b gt
--------------
Boolean
(a > b)
combinator built-in
Append a quoted expression onto the pending expression.
[Q] . i
-------------
. Q
This is a fundamental combinator. It is used in all kinds of places. For
example, the x combinator can be defined as dup i.
combinator
If-Then-Else combinator, a common and convenient specialization of branch.
[if] [then] [else] ifte
---------------------------------------
[if] nullary [else] [then] branch
combinator
Take a quoted program from the stack and run it twice, first under the top item, then again with the top item.
... a [Q] ii
------------------
... Q a Q
It's a little tricky to understand how this works so here's an example trace:
1 2 3 4 [++] • [dip] dupdip i
1 2 3 4 [++] [dip] • dupdip i
1 2 3 4 [++] • dip [++] i
1 2 3 • ++ 4 [++] i
1 2 4 • 4 [++] i
1 2 4 4 • [++] i
1 2 4 4 [++] • i
1 2 4 4 • ++
1 2 4 5 •
In some cases (like the example above) this is the same effect as using app2 but most of the time it's not:
1 2 3 4 [+] ii
--------------------
1 9
1 2 3 4 [+] app2
----------------------
1 2 5 6
combinator
Accept a quoted program and a list on the stack and run the program with the list as its stack. Does not affect the stack (below the list.)
... x y z [a b c] [Q] infra
---------------------------------
c b a Q [z y x ...] swaack
... [a b c] [F] swons swaack [i] dip swaack
... [[F] a b c] swaack [i] dip swaack
c b a [F] [...] [i] dip swaack
c b a [F] i [...] swaack
c b a F [...] swaack
d e [...] swaack
... [e d]
This is one of the more useful combinators. It allows a quoted
expression to serve as a stack for a program, effectively running it in a
kind of "pocket universe". If the list represents a datastructure then
infra lets you work on its internal structure.
combinator
built-in
Create a new Joy function definition in the Joy dictionary. A definition is given as a quote with a name followed by a Joy expression.
[sqr dup mul] inscribe
This is the only function that modifies the dictionary. It's provided as a
convenience, for tinkering with new definitions before entering them into
the defs.txt file. It can be abused, which you should avoid unless you
know what you're doing.
built-in
Less-Than-or-Equal-to comparison of the two items on the top of the stack, replacing them with a Boolean value.
a b le
-------------
Boolean
(a <= b)
combinator built-in
Expect a quoted program Q and a Boolean value on the stack. If the
value is false discard the quoted program, otherwise run a copy of Q
and loop again.
false [Q] loop
--------------------
true [Q] . loop
--------------------------
. Q [Q] loop
This, along with branch and fork, is one of the four main combinators
of all programming. The fourth, sequence, is implied by juxtaposition.
That is to say, in Joy F G is like G(F(...)) in a language bassed on
function application. Or again, to quote the Joy Wikipedia
entry,
In Joy, the meaning function is a homomorphism from the syntactic monoid onto the semantic monoid. That is, the syntactic relation of concatenation of symbols maps directly onto the semantic relation of composition of functions.
Anyway, branch, fork, and loop are the fundamental combinators in
Joy. Just as branch has it's more common and convenient form ifte,
loop has while.
built-in
Less-Than comparison of the two items on the top of the stack, replacing them with a Boolean value.
a b lt
-------------
Boolean
(a < b)
Given an initial state value and a quoted generator function build a generator quote.
state [generator function] make-generator
-----------------------------------------------
[state [generator function] codireco]
230 [dup ++] make-generator
---------------------------------
[230 [dup ++] codireco]
And then:
[230 [dup ++] codireco] 5 [x] times pop
---------------------------------------------
230 231 232 233 234
See the "Generator_Programs" notebook.
combinator
Given a list of items and a quoted program run the program for each item in the list (with the rest of the stack) and replace the old list and the program with a list of the results.
5 [1 2 3] [++ *] map
--------------------------
5 [10 15 20]
This is a common operation in many languages. In Joy it can be a parallelism combinator due to the "pure" nature of the language.
Expects two integers on the stack and removes the lesser of them, if they are equal just remove one.
Expects two integers on the stack and removes the greater of them, if they are equal just remove one.
built-in
Not-Equal comparison of the two items on the top of the stack, replacing them with a Boolean value.
a b neq
-------------
Boolean
(a = b)
Invert the Boolean value on the top of the stack.
true not
--------------
false
false not
---------------
true
Take the item on the top of the stack and cons it onto [nullary].
[F] nulco
-------------------
[[F] nullary]
True if the item on the top of the stack is an empty list, false if it's a list but not empty, and an error if it's not a list.
combinator
Run a quoted program without using any stack values and leave the first item of the result on the stack.
... [P] nullary
---------------------
... a
... [P] nullary
... [P] [stack] dip infra first
... stack [P] infra first
... [...] [P] infra first
... [a ...] first
... a
A very useful function that runs any other quoted function and returns it's first result without disturbing the stack (under the quoted program.)
combinator
Short-circuiting Boolean OR
Accept two quoted programs, run the first and expect a Boolean value, if
it’s false pop it and run the second program (which should also return a
Boolean value) otherwise pop the second program (leaving true on the
stack.) The quoted programs are run with nullary.
[A] [B] or
---------------- A -> false
B
[A] [B] or
---------------- A -> true
true
dup the second item on the stack over the first.
a b over
--------------
a b a
There are many many ways to define this function.
[swap] [tuck]
[[pop]] [nullary]
[[dup]] [dip] [swap]
[unit] [dupdip]
[unit] [dupdipd] [first]
And so on...
A fine old word from Forth.
combinator
Take a list of quoted functions from the stack and replace it with a list
of the first results from running those functions (on copies of the
rest of the stack.)
5 7 [[+][-][*][/][%]] pam
-------------------------------
5 7 [12 -2 35 0 5]
Plus or minus. Replace two numbers with their sum and difference.
a b pm
-----------------
(a+b) (a-b)
Take two numbers a and n from the stack and raise a to the nth
power. (n is on the top of the stack.)
a n pow
-------------
(aⁿ)
2 [2 3 4 5 6 7 8 9] [pow] map
-----------------------------------
2 [4 8 16 32 64 128 256 512]
combinator
From the "Overview of the language JOY"
The primrec combinator expects two quoted programs in addition to a data parameter. For an integer data parameter it works like this: If the data parameter is zero, then the first quotation has to produce the value to be returned. If the data parameter is positive then the second has to combine the data parameter with the result of applying the function to its predecessor.
5 [1] [*] primrec
Then primrec tests whether the top element on the stack (initially the 5) is equal to zero. If it is, it pops it off and executes one of the quotations, the [1] which leaves 1 on the stack as the result. Otherwise it pushes a decremented copy of the top element and recurses. On the way back from the recursion it uses the other quotation, [*], to multiply what is now a factorial on top of the stack by the second element on the stack.
0 [Base] [Recur] primrec
------------------------------
Base
n [Base] [Recur] primrec
------------------------------------------ n > 0
n (n-1) [Base] [Recur] primrec Recur
Simple and useful specialization of the genrec combinator:
n [B] [Q] primrec
---------------------------------------------
n [0 <=] [pop B] [dup --] [i Q] genrec
The derviation of primrec is given in an appendix of the
Recursion Combinators notebook.
Just as sum sums a list of numbers, this function multiplies them
together.
1 [swap] [[mul]] [step]
Or,
[1] [[mul]] [primrec]
Take two items from the stack and put them into a new list.
joy? 1 2 3 4
1 2 3 4
joy? quote-two
1 2 [3 4]
"Quote D" Wrap the second item on the stack in a list.
a b quoted
----------------
[a] b
This comes from the original Joy stuff.
Expect a number n on the stack and replace it with a list:
[(n-1)...0].
5 range
-----------------
[4 3 2 1 0]
-5 range
--------------
[]
If n is less than 1 the resulting list is empty.
Take a number n from the stack and replace it with a list
[0...n].
5 range_to_zero
---------------------
[0 1 2 3 4 5]
Note that the order is reversed compared to range.
Replace the first item in a list with the item under it.
a [b ...] reco
--------------------
[a ...]
Reverse the list on the top of the stack.
[1 2 3] reverse
---------------------
[3 2 1]
[a b ...] second
----------------------
b
Use a Boolean value to select one of two items from a sequence. :
[a b] false select
------------------------
a
[a b] true select
-----------------------
b
The sequence can contain more than two items but not fewer.
Move the top item from one list to another.
[x y z] [a b c] shift
---------------------------
[a x y z] [b c]
Like concat but reverse the top list into the second.
[a b c] [d e f] shunt
---------------------------
[f e d a b c]
This is more efficient than concat so prefer it if you don't need to
preserve order.
Replace a list with its size.
[23 [cats] 4] size
------------------------
3
Return true if the item on the top of the stack is a list with zero or one item in it,
false if it is a list with more than one item in it,
and an error if it is not a list.
Split a list (second on the stack) at the position given by the number on the top of the stack.
[1 2 3 4 5 6 7] 4 split_at
--------------------------------
[5 6 7] [4 3 2 1]
Take a list and a number n from the stack, take n items from the top
of the list and shunt them onto a new list that replaces the number n
on the top of the stack.
Split a list (second on the stack) at the position given by the number on
the top of the stack such that concat would reconstruct the original
list.
[1 2 3 4 5 6 7] 4 split_list
----------------------------------
[1 2 3 4] [5 6 7]
built-in
Put the stack onto the stack.
... c b a stack
---------------------------
... c b a [a b c ...]
This function forms a pair with unstack, and together they form the
complement to the "destructive" pair enstacken and disenstacken.
Grab the stack under the top item and put it onto the stack.
... 1 2 3 stackd
------------------------
... 1 2 [2 1 ...] 3
combinator
Run a quoted program on each item in a sequence.
... [] [Q] step
---------------------
...
... [a] [Q] step
----------------------
... a Q
... [a b c] [Q] . step
----------------------------------------
... a . Q [b c] [Q] step
See the Recursion Combinators notebook.
combinator
Like step but with 0 as the initial value.
[...] [F] step_zero
-------------------------
0 [...] [F] step
built-in
Subtract the number on the top of the stack from the number below it.
a b sub
-------------
(a-b)
combinator
Given a quoted sequence of numbers return the sum.
[1 2 3 4 5] sum
---------------------
15
built-in
Swap stack. Take a list from the top of the stack, replace the stack with the list, and put the old stack onto it.
1 2 3 [4 5 6] swaack
--------------------------
6 5 4 [3 2 1]
This function works as a kind of "context switch". It's used in the
definition of infra.
Swap the second and third items on the stack.
a b c swapd
-----------------
b a c
combinator
A specialization of the genrec combinator.
Some recursive functions do not need to store additional data or pending
actions per-call. These are called "tail recursive" functions. In Joy,
they appear as genrec definitions that have i for the second half of
their recursive branch.
See the Recursion Combinators notebook.
Expects an integer n and a list on the stack and replace them with a list
with just the top n items in reverse order.
[a b c d] 2 take
----------------------
[b a]
combinator
Run a quoted program using exactly three stack values and leave the first item of the result on the stack.
... z y x [P] ternary
-------------------------
... a
Runs any other quoted function and returns its first result while consuming exactly three items from the stack.
combinator
Expect a quoted program and an integer n on the stack and do the
program n times.
... n [Q] . times
----------------------- w/ n <= 0
... .
... 1 [Q] . times
-----------------------
... . Q
... n [Q] . times
------------------------------------- w/ n > 1
... . Q (n-1) [Q] times
dup the item on the top of the stack under the second item on the
stack.
a b tuck
--------------
b a b
(Combinator)
Run a quoted program using exactly one stack value and leave the first item of the result on the stack.
... x [P] unary
---------------------
... a
Runs any other quoted function and returns its first result while consuming exactly one item from the stack.
Removes an item from a list and leaves it on the stack under the rest of
the list. You cannot uncons an item from an empty list.
[a ...] uncons
--------------------
a [...]
This is the inverse of cons.
Expect two non-empty lists on the stack and uncons the first item from each and put them in a new list.
joy? [1 2] [3 4] uncons-pair
[1 3] [2] [4]
Expect two non-empty lists on the stack and uncons the first item from each.
joy? [1 2] [3 4] uncons-two
1 3 [2] [4]
combinator
Unquote (using i) the list that is second on the stack.
1 2 [3 4] 5 unquoted
--------------------------
1 2 3 4 5
Take a list from the top of the stack and concat it to the stack.
joy? 1 2 3 [4 5 6]
1 2 3 [4 5 6]
joy? unstack
1 2 3 6 5 4
combinator
A specialization of loop that accepts a quoted predicate program P
and runs it nullary.
[P] [F] while
------------------- P -> false
[P] [F] while
--------------------- P -> true
F [P] [F] while
combinator
Take a quoted function F and run it with itself as the first item on
the stack.
[F] x
-----------
[F] F
The simplest recursive pattern.
See the Recursion Combinators notebook as well as Recursion Theory and Joy by Manfred von Thun.
Replace the two lists on the top of the stack with a list of the pairs from each list. The smallest list sets the length of the result list.
[1 2 3] [4 5 6] zip
-------------------------
[[1 4] [2 5] [3 6]]