-*- fill-column:73; ais523autofill:t; -*-
Commands are given in the form (removed from stack -- added to stack),
in pseudo-Overload (that is, () delimit a quoting list, etc.). The
leftmost value always refers to the TOS. x, x1, x2, x3, etc. refer to
'anything that might be at that point'; likewise for y, y1, y2, y3, etc..
{ and } are used to refer to 'either a quoting or a nonquoting list'. If
a command changes program flow in an unusual manner, the change to the
program and IP (written as [_ip]) will be shown below in the format
(before -- after); a semicolon is used to separate different lists in the
'before' and 'after' if more than one list is relevant.
Each command also has an example. (As these examples are unquoted, it's
occasionally nontrivial to figure out whether a punctuation mark is part
of the example or part of the sentence; therefore the examples should not
be taken to be normative.)
Pointers as commands
]x[ ( -- )
([_ip]]x[;[x]y -- ]x[;[x][_ip]y)
A pointer causes an unconditional jump to the command to which it
points.
Quoting lists as commands
(x) ( -- (x))
A quoting list pushes a copy of itself onto the stack.
Example: [x](abc)(def)(]x[) leaves the stack as ((]x[)(def)(abc))
without changing the program.
z(x) ( -- (x))
(z[_ip](x) -- z[_ip])
When modified by z, a quoting list pushes itself onto the stack,
removing itself from any list it might have been in before. (This
modifies the program). Any pointers that pointed to or within the
original list now point to the corresponding place on or within the
stack.
Example: z[x](abc)z(def)z(]x[) leaves the stack as
((]x[)(def)[x](abc)) and the program as zzz.
Nonquoting lists as commands
, ( -- (]x[))
([x][_ip], -- [x],[_ip])
, pushes a pointer to the occurrence of , that was called onto the
stack. As with all the pointer-pushing commands, it's in a quoted
list.
Example: ,? is equivalent to (,)A (they both leave an unquoted , on
top of the stack.)
. ([x1]x -- (]x1[) [x1]x)
. pushes a pointer to the old TOS onto the stack.
Example: .? is equivalent to : (they both push a copy of the TOS onto
the stack), but .z? is a no-op (because it moves the TOS back onto the
stack, in the same position).
z. (]x[ -- [(x becomes the stack)]) or ({]x[} -- [(x becomes the stack)])
This causes whatever TOS points to to become the stack. The old TOS is
detached from the old stack (in case anything's still pointing to the
old stack). As the variable table's immediately after the stack, this
also has the effect of changing the variable table.
Example: 5U.z. leaves the stack as (<><[#2]><[#3]><[#4]><[#5]>);
anything that was previously on the stack is now gone, as the list
used to store the stack has been changed.
* ({x1 x2 x3...} {y1 y2 y3...} -- {y1 y2 y3... x1 x2 x3...})
This concatenates two lists; anything that pointed to an element of
either of the lists continues to point to its analogue in the
concatenated list, but anything that pointed to one of the lists
themselves will now point to an empty detached list with the same
quoting status. The resulting list is quoting if both original lists
were quoting, or nonquoting if both original lists were nonquoting;
it's unspecified whether it's quoting or not if the original lists
differed in quoting status. The elements of the list that was on top
of the stack come last in the concatenation.
If either of the top two stack elements isn't a list, it's listified
in the normal manner by enclosing it in a quoting list before the
concatenation.
Example: 23* is equivalent to (:*)(::**)* or to (:*::**), which
happens to be a representation of the number 6. (* can in fact be used
for multiplication, although it leaves a non-normalized answer). 23*N
is exactly equivalent to 6.
^ ({x1 x2 x3...} -- )
([_ip]^y... -- ^[y1]y...;{[_ip]x1 x2 x3...]y1[})
If y is a pointer itself, y1 instead points to y's target.
^ is like 'eval' in other languages. It detaches the TOS, then appends
a pointer to the next command (or where the next command points if
it's a pointer; this makes recursive programs possible without using
infinite heap space) to the old TOS, and moves the IP to the first
element of the old TOS.
Example: (123)^ is exactly equivalent to 123, and .(123)^; is exactly
equivalent to .123; or ([#123]). (This method of parsing ASCII strings
to numbers is not recommended without first checking that the string
contains nothing but digits, because it could lead to arbitrary code
being executed.)
~ (x1 x2 -- x2 x1)
Effect on pointers: ([y1]x1 [y2]x2 -- [y2]x2 [y1]x1)
~ swaps the top two elements of the stack.
Example: (1)(2)~ is equivalent to (2)(1).
` (x {x1 x2 x3...} -- x)
([_ip]^y... -- ^[y1]y...;{[_ip]x1 x2 x3...]y1[})
` is exactly equivalent to ~^ (it swaps the top two stack elements,
and then interprets the new top element as code and runs it like a
subroutine).
Example: 'k1` returns a function that always returns the identity
function (it means the same as the Unlambda `ki).
& ({x1 x2 x3...} {y1 y2 y3...} -- {x1 x2 x3... y1 y2 y3...})
& is exactly equivalent to ~* (it concatenates the top two stack
elements in the reverse order to *).
Example: (feel)(un)&(ing)* is equivalent to (unfeeling); this
technique can be used to translate lambda-calculus expressions into
Overload.
@ (x1 x2 x3 -- x1 x3 x2)
Effect on pointers: ([y1]x1 [y2]x2 [y3]x3 -- [y1]x1 [y3]x3 [y2]x2)
@ swaps the second and third stack elements.
Example: (1)(2)(3)@~ is equivalent to (3)(2)(1).
? (]y1[ -- x1) or ({]y1[} -- x1) where [y1]x1 appears elsewhere
? detaches TOS (which must be a pointer or a list containing nothing
but a pointer), and pushes a copy of what the old TOS pointed to onto
the stack. If TOS was a one-past-the-end pointer, it instead pushes an
empty nonquoting list onto the stack (one-past-the-ends are converted
into <> whenever an explicit value is needed).
Example: z(ab[x]cde)(]x[)? is equivalent to z(abcde)(c)A.
z? (]y1[ -- x1) or ({]y1[} -- x1) where [y1]x1 appears elsewhere
When modified by z, ? detaches TOS (which must be a pointer or a list
containing nothing but a pointer), and moves what it pointed to onto
the stack, removing what it pointed to from its original location. If
TOS was a one-past-the-end pointer, it instead pushes an empty
nonquoting list onto the stack (one-past-the-ends are converted into
<> whenever an explicit value is needed).
Example: z(ab[x]cde)(]x[)z? is equivalent to z(abde)(c)A.
= (]y1[ x -- ) or ({]y1[} x -- ) changing [y1]x1 to [y1]x;x
= detaches TOS (which must be a pointer or a list containing nothing
but a pointer), and moves the second stack element to take the place
of what it was pointing to, detaching what it was pointing to to make
room.
Example: z(ab[x]cde)(f)(]x[)= is equivalent to z(ab(f)de).
/ (]y1[ x -- ) or ({]y1[} x -- ) changing [y1]x1 to x [y1]x1
/ detaches TOS (which must be a pointer or a list containing nothing
but a pointer), and moves the second stack element between what TOS
was pointing to and the element before it (or at the start of the list
containing the element TOS was pointing to if it was pointing to the
first element of a list).
Example: z(ab[x]cde)(f)(]x[)/ is equivalent to z(ab(f)cde).
\ (]y1[ -- ) or ({]y1[} -- ) detaching [y1]x1
\ detaches TOS (which must be a pointer or a list containing nothing
but a pointer), and also detaches whatever it was pointing to (doing
nothing but causing the pointer to end up pointing to a nonquoting
list in an undelimited list if it was pointing one-past-the-end
beforehand).
Examples: z(ab[x]cde)(]x[)\ is equivalent to z(abde).
.\ is equivalent to !.
: (x -- x x)
: pushes a copy of TOS onto the stack. Any pointers that pointed to or
into TOS end up pointing to the original (second on the stack), rather
than the new copy.
Examples: (a): is equivalent to (a)(a).
(:apSS):apSS is equivalent to (:apSS)(:apSS)apSS
or (:apSS)("(:apSS"))SS
or ("(:apSS"))S(:apSS)S
so it prints (:apSS):apSS. (This is not the simplest
Overload quine, but it's one of the most obvious.)
! (x -- )
! detaches TOS. (If nothing was pointing at or within TOS, this has
the same effect as popping the stack.)
Example: (a)(b)! is equivalent to (a).
z! (x -- )
z! detaches TOS. Its contents are removed from its delimiters; the
delimiters stay behind as an empty list (getting immediately
garbage-collected unless something was pointing at them), and the old
TOS's contents become an undelimited list. If TOS doesn't have
delimiters, the effect is the same as if ! were used.
Example: (abc).A~z! leaves a pointer to the undelimited list abc on
the stack. (This effect is hard to achieve without using z!).
_ ({x1 x2 x3...} x -- )
([_ip]_[y1]y -- [y1]y;{[_ip]x1 x2 x3... z(x)A]y1[})
_ quotes the second stack element, prepends z, appends A, appends it
to TOS, and then does ^. The practical effect of this is that the
second stack element will disappear temporarily whilst the TOS is
executed, and will reappear afterwards; this is the 'dip' combinator
from Joy.
Example: (~)_ is equivalent to @.
} (x -- x+1)
} detaches TOS, and pushes a representation of a number 1 greater than
it onto the stack. The representation used is unspecified (although it
will always be normalised if TOS was normalised), and if TOS wasn't a
representation of a number the behaviour is undefined.
Example: 4} is equivalent to 5.
{ (x -- x?x-1:0)
{ detaches TOS, and pushes a representation of a number 1 less than it
onto the stack, or a representation of 0 if there was a 0 on top of
the stack. The representation used is unspecified (it can be
non-normalised even if TOS was normalised), and if TOS wasn't a
representation of a number the behaviour is undefined.
Example: 4{N is equivalent to 3.
+ (x1 x2 -- x1+x2)
+ detaches the top two stack elements, and pushes a representation of
their sum onto the sack. The representation used is unspecified (it
will be normalised if TOS was previously normalised, even if the
second stack element wasn't), and if either of the top two stack
elements wasn't a representation of a number the behaviour is
undefined.
Example: 35+ is equivalent to 8.
- (y1 y2 -- y2-y1) with integers or pointers;
({y1} y2 -- y2-y1), (y1 {y2} -- y2-y1), or ({y1} {y2} -- y2-y1) with
pointers.
- works with both integers and pointers, and has two separate
meanings.
If the top two stack elements are both pointers or lists containing
nothing but pointers, then both are detached, and a representation of
the 'difference' between the pointers is pushed onto the stack. This
'difference' is defined as the number of consecutive D commands that
would transform the first pointer into the second (using the original
definition of D, if it's been redefined; unless this command is
redefined itself, it's immune to command redefinition). If no number
of consecutive D commands would transform the first pointer into the
second, or both pointers point to the same target (that is, zero D
commands would transform the first into the second), a representation
of 0 is pushed onto the stack.
Otherwise, the top two stack elements are interpreted as numbers and
detached (there is undefined behaviour if either of them wasn't a
number). If the number that the TOS represented was less than the
number that the second stack element represented, an unspecified
representation of their difference (not necessarily normalised, even
if both original numbers were normalised) is pushed onto the
stack. Otherwise, an unspecified representation of 0 is pushed onto
the stack.
Examples: (a[x]bc[y]de)(]y[)(]x[)-N is equivalent to (abcde)2.
63-N is equivalent to 3.
36-N is equivalent to 0.
' ( -- (x))
([_ip]'xy -- 'x[_ip]y)
' pushes a quoting list containing a copy of the element that would be
the next command to be executed onto the stack, then transfers
execution unconditionally to what would be the next-but-one
command. In the case where ' is last in a list, it pushes (<>) onto
the stack, then transfers execution to the end of the list; when this
happens, it's unspecified whether or not a <> is inserted at the end
of the list that the ' is in.
Example: '*8*S is equivalent to (*)8*S or (********)S, and outputs
eight stars.
z' ( -- (x))
(z[_ip]'xy -- z'[_ip]y)
z' is almost the same as ', but moves the next command to be executed
into a quoting list and places it on the stack, instead of copying;
this leads to the program being modified. There definitely won't be a
stray <> inserted when z' is used at the end of a list.
Example: (z'a)l will push (a) onto the stack, then push a quoting list
containing a pointer to the z onto the stack (because on the second
iteration the a will have gone and the next element will be the
l-added pointer pointing back to the z), and then exit the loop
(because the next command reached will be the pointer to return from
the loop that will have been added by the ^ implied by the l).
0 ( -- (!()))
0 pushes (!()) onto the stack; therefore, if the resulting list is
interpreted as a function, it will act differently if ! has been
redefined.
Example: 0 has the same effect as (!()).
1 ( -- ())
1 pushes an empty quoting list onto the stack.
Example: 1^ has no effect.
2 ( -- (:*))
2 pushes (:*) (the normalised representation of 2) onto the stack. The
resulting list will act differently if it's interpreted as a function
and either : or * has been redefined.
Example: 22+ is equivalent to 22*N.
3, 4, 5, 6, 7, 8, and 9 are defined in a similar way to 2; each pushes a
normalised representation of the appropriate digit onto the stack.
; (x1 x10 x100... ]y1[ -- x1+x10*10+x100*100+...) or
(x1 x10 x100... {]y1[} -- x1+x10*10+x100*100+...)
; takes the TOS (interpreting it as a number), adds it to ten times
the second stack element, adds the total to a hundred times the third
stack element, and so on in increasing powers of 10. This continues
until a stack element that's either a pointer or a list containing
nothing but a pointer is found. All the numbers and the pointers are
detached, and a normalised representation of the resulting sum is
pushed onto the stack. If TOS happens to be a pointer or list
containing only a pointer, it's detached and a normalised
representation of 0 is pushed onto the stack. All representations so
pushed are quoting lists. If any of the elements checked is neither a
pointer, a list containing only a pointer, or a quoting list, the
behaviour is undefined. (This command is intended as a wimpmode for
decimal numbers, but knowing Overload it's probably got other uses as
well.)
Example: ,65536; is equivalent to 48^N. (Yes, ^ can be used to do
exponentiation; 8 pushes (:::::::*******) onto the stack, so when it's
executed, the original string (:::***) (for 4) and seven copies are
pushed onto the stack, and then concatenated, leading to
4*4*4*4*4*4*4*4 or 65536.)
A (]y1[ -- ]y2[) or ({]y1[} -- {]y2[}) given [y1]{[y2]x1 x2...},
or changing [y1]]x1[ to ([y2]]x1[), or changing {... x1 [y1]} to
{... x1 <[y2]>}, or as zA
A causes a pointer at TOS (or a list containing nothing but a pointer)
to point to the first element of the list it was pointing to. If it
was pointing to a pointer, that pointer is placed into a quoting list
to give the command somewhere to point TOS to; if it was pointing
one-past-the-end, an empty nonquoting list is created there to give
the command somewhere to point TOS to.
If there isn't a pointer or list containing nothing but a pointer at
TOS, A instead has the same effect as zA.
Example: 4.A? is equivalent to 4(:)zA.
zA ({x1 x2...} -- x1)
zA replaces a list at TOS with its first element. It has no effect on
a pointer, an it causes an empty list to become nonquoting (because
the one-past-the-end position, its implied 'first element', becomes
<>). For purposes of determining what happens to pointers, the first
element of TOS is detached from it, then TOS is detached, and then the
old first element of TOS is pushed onto the stack.
Example: 'aA pushes the nonquoting list normally represented as a
onto the stack. (zA, or A in situations where it has the same effect
as zA (like this one), are simple ways to place nonquoting lists onto
the stack.)
a (]y1[ -- ]y2[) or ({]y1[} -- {]y2[}) given [y2]{... x1 [y1]x2 x3...}, or
changing ...x1 [y1]x2 x3... to [y2](...x1 x2 x3...), or as za
a causes a pointer at TOS to point to the list containing the element
it's pointing to. If it's pointing to an element of a nondelimited
list (which cannot be pointed to), the nondelimited list is made into
a quoting list and TOS is changed to point to that.
If there isn't a pointer or list containing nothing but a pointer at
TOS, a instead has the same effect as za.
Examples: .a?pS prints out the entire stack, including a pointer to the
stack at TOS, on standard output.
,aS prints ,aS on standard output; this is a
quine-by-cheating, as the program reads its own source
code. (This situation involves a nondelimited list.)
za (x -- (x))
za places a quoting list around TOS (any pointers pointing to it end
up pointing inside the new quoting list).
Example: za(!z)& is one way to implement k.
C ( -- (]y1[ ]y2[...)) where [y1], [y2], etc. point to the first
elements of nondelimited lists
C pushes a list containing a pointer to the first element of each
nondelimited list currently in the program's memory onto the
stack. (Lists that have been garbage-collected don't count).
Example: I can't think of one right now.
c (too complicated to fit into one of these diagrams; see text)
c is the call/cc operator, which Overload shares with languages like
Scheme and Unlambda. It generates a continuation consisting of what
the state of the program would be if c returned without doing
anything, pushes it onto the stack, and then does the same as `
(i.e. swaps the top two stack elements and evaluates the new TOS). If
the continuation is called, it takes the program back in time to the
calculated state that would have occurred if c has done nothing,
except that the top element of the stack, and anything it points to,
are preserved and remain where they were before (i.e. the TOS remains
on top of the stack). It's unspecified what happens to anything
pointing to the TOS or within it when the continuation is called, if
such pointers don't get garbage-collected; they'll either continue
pointing to the TOS, or they'll point to a copy of it in an
unspecified context. (Therefore, this situation should be avoided in
portable programs by avoiding situations in which the TOS contains a
pointer to something which points back to or within the TOS). However,
pointers from within the TOS to within the TOS will be handled
correctly.
The state recorded by c contains the IP, program, stack, variables,
and any nondelimited lists, but not the hashtable, command
definitions, or IP movement definitions.
The c command is not guaranteed to work if any of the
originally-defined commands have been redefined.
It is completely legal for a continuation to 'escape' the function
called using the c command (see the second example
below). Continuations consist of Overload code themselves, and can
even be deparsed and printed by pS if you want to inspect them for
debugging (there is no guarantee that they'll be readable, however).
Examples: (a)(b)(c)(~!~!~!(d)`)c is equivalent to (a)(b)(c)(d).
1c:^ is an infinite loop. (Due to the way the stack behaves,
a program consisting of only c:^ is also an infinite loop,
due to the implied <> on the stack to start with; but there
are shorter infinite loops in Overload (l is an infinite
loop for example).)
D (]y1[ -- ]y2[) or ({]y1[} -- {]y2[}) with {...x1 [y1]x2 [y2]x3...} or
changing {...x1 [y1]x2} to {...x1 [y1]x2 [y2]<>}, or as zD
D changes a TOS to point to the element after the one it's currently
pointing to in the same list (changing a one-past-the-end position to
<> if that's needed to make the command make sense; if it was pointing
to the last element, it points one-past-the-end instead.)
If TOS isn't a pointer or list containing nothing but a pointer, D has
the same effect as zD.
Example: (ab[x]cde)(]x[)D? is equivalent to (abcde)(d)A.
zD ({x1 x2 x3...} -- {x2 x3...})
zD detaches the first element of the list at TOS; if TOS is actually a
pointer, it's instead detached and replaced with an empty quoting
list.
Example: (abcde)D is equivalent to (bcde).
d (]y1[ -- ]y2[) or ({]y1[} -- {]y2[}) with {...x1 [y2]x2 [y1]x3...} or
{[y1]x1 x2... x9 [y2]}
d causes a pointer at TOS to point to the previous element of the same
list it's pointing to. If it was pointing to the first element of a
list, it's retargeted to point one-past-the-end in that list.
Examples: (ab[x]cde)(]x[)d? is equivalent to (abcde)(b)A.
(abcde).A:d-N is equivalent to (abcde)5.
e (x {y1 y2 y3...} -- {x(y1) x(y2) x(y3)...})
(N.B. in this example, x(y1) denotes 'application of x to y1'; this is
written at a higher level than most other examples. See the text for
more details.)
The TOS is treated as a function. It's detached and remembered; in
turn, each of the elements of the second stack element are pushed onto
the stack, the commands in the remembered TOS are run, and the
resulting TOS is detached and remembered. Once all the elements in the
second stack element have been used, a list (of unspecified quoting
status) containing all the remembered calculated TOSs (not the
original TOS, which is now allowed to be garbage-collected if
nothing's pointing to it) is pushed onto the stack, leaving the
elements in the same order. Elements in the original second stack
element are processed from first to last. If the second stack element
is a pointer rather than a list, it's made into a quoting list
containing just that pointer so the e command can be run.
Any temporaries used by the e command are part of the state that can
be recorded in a continuation by c. The e command is not guaranteed to
work if any originally defined command has been redefined.
Examples: (abc)(a)e is equivalent to ((a)(b)(c)), apart from the
unspecifiedness of the quoting status in the first example;
(abc)(:)e! is equivalent to (a)A(b)A(c)A.
f ({x1 x2 x3... } y -- )
([_ip]f -- f[_y1];{[_ip]x1 x2 x3... x1 x2 x3... ...[(y times)] ]_y1[})
f is equivalent to the command sequence `^ (and won't necessarily work
if either of those commands have been redefined). For its most common
use, it treats the second stack element as a number, repeats the first
stack element that many times, and interprets the repeated stack
element as code and runs it as if it were a subroutine. The code and
repeat-count are popped.
Example: 9((*)S)f outputs *********.
g (x -- [(1 if x was 0, or 0 otherwise)])
g replaces the top element of the stack with a representation of 1 if
it was a representation of 0, or a representation of 0 if it was a
representation of some other number. If the top element of the stack
isn't a number, it behaves as the command sequence ()` would do (if `
has been redefined, or ~ or ^ have been redefined, instead the
behaviour is undefined). The representation used and the quotingness
of the output list are undefined.
Example: V:1O-g((Too big!<[$b]>)S<>)f reads a number, and prints an
error message and returns if the entered number was greater than 10.
H