Hi everybody,
I apologize for the very long time it took to prepare this. This is a
draft, and I intend to change a lot of things before the final version.
Pretty much everything I wanted to describe is in there, except
continuations. Feedback is welcome.
Slava
------8<------
THE CONCATENATIVE LANGUAGE FACTOR
* Introduction
Factor supports various data types; atomic types include numbers of
various kinds, strings of characters, and booleans. Compound data types
include lists consisting of cons cells, vectors, and string buffers.
Factor encourages programming in a functional style where new objects
are returned and input parameters remain unmodified, but does not
enforce this. No manifest type declarations are necessary, and all data
types use exactly one slot each on the stack (unlike, say, FORTH).
The internal representation of a Factor program is a linked list. Linked
lists that are to be executed are referred to as ``quotations.'' The
interpreter iterates the list, executing words, and pushing all other
types of objects on the data stack. A word is a unique data type because
it can be executed. Words come in two varieties: primitive and compound.
Primitive words have an implementation coded in the host language (C or
Java). Compound words are executed by invoking the interpreter
recursively on their definition, which is also a linked list.
* A note about code examples
Factor words are separated out into multiple ``vocabularies''. Each code
example given here is preceeded with a series of declarations, such as
the following:
USE: math
USE: streams
When entering code at the interactive interpreter loop, most
vocabularies are already in the search path, and the USE: declarations
can be omitted. However, in a source file they must all be specified, by
convention at the beginning of the file.
* Control flow
Control flow rests on two basic concepts: recursion, and branching.
Words with compound definitions may refer to themselves, and there is
exactly one primitive for performing conditional execution:
USE: combinators
1 10 < [ "10 is less than 1." print ] [ "whoa!" print ] ifte
==> 10 is less than 1.
Here is an example of a word that uses these two concepts:
: contains? ( element list -- remainder )
#! If the proper list contains the element, push the
#! remainder of the list, starting from the cell whose car
#! is elem. Otherwise push f.
dup [
2dup car = [ nip ] [ cdr contains? ] ifte
] [
2drop f
] ifte ;
An example:
USE: lists
3 [ 1 2 3 4 ] contains?
==> [ 3 4 ]
5 [ 1 2 3 4 ] contains?
==> f
It recurses down the list, until it reaches the end, in which case the
outer ifte's 'false' branch is executed.
A quick overview of the words used here, along with their stack effects:
Shuffle words:
dup ( x -- x x )
nip ( x y -- y )
2dup ( x y -- x y x y )
2drop ( x y -- )
Linked list deconstruction:
car ( [ x | y ] -- x )
cdr ( [ x | y ] -- y ) - push the "tail" of a list.
Equality:
= ( x y -- ? )
More complicated control flow constructs, such as loops and higher order
functions, are usually built with the help of another primitive that
simply executes a quotation at the top of the stack, removing it from
the stack:
USE: math
USE: prettyprint
[ 2 2 + . ] call
==> 4
Here is an example of a word that applies a quotation to each element of
a list. Note that it uses 'call' to execute the given quotation:
: each ( list quotation -- )
#! Push each element of a proper list in turn, and apply a
#! quotation to each element.
#!
#! In order to compile, the quotation must consume one more
#! value than it produces.
over [
>r uncons r> tuck >r >r call r> r> each] [
2drop
] ifte ;
An example:
USE: lists
USE: math
USE: stack
[ 1 2 3 4 ] [ dup * . ] each
==> 1
4
9
16
A quick overview of the words used here:
Printing top of stack:
. ( x -- ) print top of stack in a form that is valid Factor syntax.
Shuffle words:
over ( x y -- x y x )
tuck ( x y -- y x y )
>r ( x -- r:x ) - move top of data stack to/from 'extra hand'.r> ( r:x -- x )
Writing >r foo r> is analogous to '[ foo ] dip' in Joy. Occurrences of
>r and r> must be balanced within a single word definition.Linked list deconstruction:
uncons ( [ x | y ] -- x y )
* Variables
Factor supports a notion of ``variables''. Whereas the stack is used for
transient, intermediate values, variables are used for more permanent
data.
Variables are retreived and stored using the 'get' and 'set' words. For
example:
USE: math
USE: namespaces
USE: prettyprint
"~" get .
==> "/home/slava"
5 "x" set
"x" get 2 * .
==> 10
The set of available variables is determined using ``dynamic scope''.
A ``namespace'' is a set of variable name/value pairs. Namespaces can be
pushed onto the ``name stack'', and later popped. The 'get' word
searches all namespaces on the namestack in turn. The 'set' word stores
a variable value into the namespace at the top of the name stack.
While it is possible to push/pop the namestack directly using the words
>n and n>, most of the time using the 'bind' combinator is moredesirable.
Good examples of namespace use are found in the I/O system.
Factor provides two sets of words for working with I/O streams: words
whose stream operand is specified on the stack (freadln, fwrite,
fprint...) and words that use the standard input/output stream (read,
write, print...).
An I/O stream is a namespace with a slot for each I/O operation. I/O
operations taking an explicit stream operand are all defined as follows:
: freadln ( stream -- string )
[ "freadln" get call ] bind ;
: fwrite ( string stream -- )
[ "fwrite" get call ] bind ;
: fclose ( stream -- )
[ "fclose" get call ] bind ;
( ... et cetera )
The second set of I/O operations, whose stream is the implicit 'standard
input/output' stream, are defined as follows:
: read ( -- string )
"stdio" get freadln ;
: write ( string -- )
"stdio" get fwrite ;
( ... et cetera )
In the global namespace, the 'stdio' variable corresponds to a stream
whose operations read/write from the standard file descriptors 0 and 1.
However, the 'with-stream' combinator provides a way to rebind the
standard input/output stream for the duration of the execution of a
single quotation. The following example writes the source of a word
definition to a file named 'definition.txt':
USE: prettyprint
USE: streams
"definition.txt" <filebw> [ "with-stream" see ] with-stream
The 'with-stream' word is implemented by pushing a new namespace on the
namestack, setting the 'stdio' variable therein, and execution the given
quotation.
On Sun, 12 Sep 2004, Slava Pestov wrote:
> Hi everybody,[..]
>
> I apologize for the very long time it took to prepare this. This is a
> draft, and I intend to change a lot of things before the final version.
> Pretty much everything I wanted to describe is in there, except
> continuations. Feedback is welcome.
>
> Slava
Thanks for this. Since you marked it "draft" and asked for
comments, I won't put it into the final version just yet.
(I did not get any criticism for my two bits when I sent them.)
Keep it up.
- Manfred
here's a draft of the XY paper, with one section -- Programming
in XY -- incomplete. at this point, i've shut down further work
on cK to concentrate on XY, so i won't be writing anything on
that language.
the permanent link for the paper below (which i will continue
to work on) is:
http://www.nsl.com/k/xy/xy.txt
comments, suggestions, and criticism welcome.
--------------------
THE CONCATENATIVE PROGRAMMING LANGUAGE XY
*
(FIRST DRAFT)
* Introduction
XY is a concatenative programming language with roots in Joy and K.
The elements of XY are unary functions, each of which takes and returns
a pair of the form:
[stack queue]
The stack is a list which represents the past of the computation.
The queue is a list which represents the future of the computation.
XY is written in K in continuation-passing style.
The datatypes of XY are the atoms and lists of K: integers, floats,
characters, symbols, dictionary, null, and lists.
The 20 K verbs are the primitive functions of XY:
~ ! @ # $ % ^ & * - _ = + | : < , > . ?
If v is a verb, then v denotes the associated dyadic function, v:
denotes the the associated monad, and v. denotes the commute of the
dyad. For example,
x y - x minus y
x -: negate x
x y -. y minus x
* Lists and Quotations
XY supports both lazy lists ("quotations") and eager lists.
Quotations are written using square brackets:
[2 3 +]
[2 3 +]
Eager lists are written using parentheses:
(2 3 +)
5
An eager list such as (2 3 +) is recursively transformed at parse-time
into the expression
[2 3 +] /
which pushes [2 3 +] onto the stack, and then evaluates it.
* Evaluation
In the course of execution, XY has two objects: a list of values X
and a list of tokens z^Y, where z is the next token to be processed
and Y is a list of the remaining tokens. X is the result stack and
Y is the input queue. Evaluation of z consists of applying z to the
list [X Y]. The result of the application is a new stack X' and a
new queue Y'.
z is either an atom or a list. An atom is either an integer, a float,
a character, a dictionary, null, or a symbol. A symbol is either
defined or undefined.
If z is anything other than a defined symbol, its evaluation rule is:
[X z^Y] -> [X^z Y]
That is, z is removed from the queue and appended to the stack.
XY maintains a dictionary W which maps symbols to evaluation rules.
For each defined symbol, there is an evaluation rule in W. For example,
the evaluation rule for the primitive + is:
[X^x1^x2 Y] -> [X^x1+x2 Y]
That is, + takes X^x1^x2 and Y, pops x1 and x2, adds them, appends the
result to X, and returns the new stack and the unaltered queue Y.
* Core
<- stack [X^z Y] -> [z Y]
<- replaces the stack with the item found at the top
of the stack:
10 20 [2 3 +] <-
2 3 +
<- is Joy's "unstack" operator.
-> queue [X^z Y] -> [X z]
-> replaces the queue with the item found at the top
of the stack:
10 20 [2 3 +] -> 30 40 50
10 20 5
-> has no analogue in Joy.
/ use [X^z Y] -> [X z^Y]
/ prepends to the queue the item found at the top of the stack.
10 20 [2 3 +] / 30 40 50
10 20 5 30 40 50
/ is Joy's "i" combinator.
\ mention [X z^Y] -> [X^z Y]
\ moves the item found at the head of the queue to the top of
the stack:
10 20 \ + 30 40
10 20 + 30 40
\ has no analogue in Joy.
; define [X name^..code..^;^Y] -> [X Y]
; add-mul + * ;
2 3 4 add-mul
14
All definitions in XY are inline.
{ stack pattern [X template^..code..^}^Y] -> [X^Z Y]
{ matches names in the template to elements on the stack, and
then substitutes those values for matching names in the code.
_x denotes the stack, and _y the queue, as they are at run-time.
The result of the subtitution Z is appended to the stack:
10 20 30 { [a b] a b b a }
10 20 30 30 20
{{ queue pattern [X template^..code..^}}^Y] -> [X Z^Y]
{{ matches and substitutes like {, but instead of appending
the Z to the stack, it prepends it to the queue:
10 20 30 {{ [a b] a b + a * }}
10 1000
* Auxilliary
The following words are included in the current implementation, but are not
used.
.a amend shallow amend with assignment: @[x;y;:;z]
.d dmend deep amend with assignment: .[x;y;:;z]
.g get "name" .g -> value of name
.s set value "name" .s -> associate name with value
.p parse invoke the XY parser
.r represent invoke the XY representation function
.i input accept input to the stack
.o output produce output from the stack
.e execute alternate evaluate P, if that fails evaluate Q
.xy XY evaluate X and z^Y.
* Scripts
XY supports scripts. An XY script is a text file which contains XY code.
Typically, the filename ends in ".xy", although this is not necessary.
On initialization, XY loads the system script xy.xy, which contains core
definitions, including stack manipulation words like dup and swap, K adverbs
like over, each, and prior, and Joy combinators like linrec and dip.
At this point, XY does not support comments.
* Programming in XY
This section will contain examples.
* Implementation
Interpretation in XY consists of the standard read-eval-print loop. The
three steps correspond to three functions: the parser p, the evaluator e,
and the function r, which takes a list (either the stack or the queue) and
represents it as a string, suitable for printing.
The evaluator takes a stack x and a queue to be evaluated y:
e:{({if[T>0;t[x;y]];a[*y,();x,()](1_ y),()}.)/(x;y)}
e repeatedly evaluates x and y. At each step, it checks to see whether
the trace variable T is positive. If so, it displays the current states
of x and y:
t:{if[(#x)|#y;`0:(40$r x)," : ",-40$r y;:[#y;if[#0:`;T::0];`0:,""]]}
It then applies the following algorithm: if the queue is empty or the
stack is null, it returns the current stack and queue; else if the next
element to be evaluated is not a defined symbol, it appends it to the stack
and returns that and the queue; else it applies the evaluation rule for
that symbol:
a:{:[(~#z)&_n~x;(y;z);~4=4:x;(y,,x;z);(#**W)=i:W[0;0]?x;(y,x;z);W[1;i][y;z]]}
* Open Questions
- Can { and {{ be defined in terms of the other core words?
* Links
XY: http://www.nsl.com/papers/xy.htm.
K: http://www.kx.com
i've added comments to XY:
// this comment ends at the newline
notationally, this is rather nice, since not only does it echo
k's use of / for commentary, but it complements the use of \
for atomic quotation.
that is, the word \ takes the next item on the queue and moves
it to the stack:
2 3 \ + 4 5
2 3 + 4 5
in queue programming (as opposed to stack programming) this
comes up with some frequency, so i decided to support a syntactic
form as well:
2 3 \+ 4 5
2 3 + 4 5
prefix anything with \ to move it to the stack.
this means that \\ can't be a word in XY, since it already
means "move \ to the stack."