stevan apter — 2004-07-18 16:51:21

hi all

this is an interim report on some work i've been doing on a new
(toy) language, which i'm calling 'xy'. the code is here:

www.nsl.com/k/xy/xy.k

xy is written in k (naturally), and has the atoms, lists, and
verbs of k. the look and feel of the notation is joy-like.

all the stack-riented words are defined in terms of extended
stack notation. semicolons enclose associations of a name and
a definition. e.g.

; swap { [a b] b a } ;
; pick { [a b c] a b c a } ;

; car { [[a A]] a } ;
; cdr { [[a A]] A } ;
; cons { [a b] [a] b , } ;
; uncons { [[a A]] a A } ;

i've adopted several definitions of slava's, which you can see
at:

www.nsl.com/k/xy/xy.xy

the car of one of these definitions is a pattern, and the cdr
is code containing elements of the pattern.

the underlying xy machinery consists of a result stack x and an
input queue y, hence the name 'xy'.

within one of these definitions, the symbol _x denotes the
result, and _y denotes the input queue.

all xy primitives access both x and y, although some, like +,
make no use of y. among the primitives are:

\s like joy's "unstack"

"clear the result stack" is defined:

; \c [] \s ;

the equivalent of joy's "stack" word is:

; \g { [] \c _x } ;

a parameterized callcc is:

; callcc { [q n] [_x _y n continue] q i } ;
; continue { [x_ y_ n] \c x_ i n -: _x # i y_ /s } ;

; callcc0 0 callcc ;
; callcc1 1 callcc ;

a working xy version of chris's parlor-trick factor-exercise can
be found here:

www.nsl.com/k/xy/stuff/choose.xy
www.nsl.com/k/xy/stuff/parlortrick.xy

'i' and 'ifte' are the only primitive combinators. xy definitions
for linrec, infra, and cond:

; linrec { [c t e f] c i c t e f _x linrec_ } ;
; linrec_ { [b c t e f x] x \s b t [e i c t e f linrec f i] ifte } ;

; infra pair \g |: uncons |: / |: \s |: \g |: uncons , i i \g unit \ swap , \s ;

; cond { [a] a #: 1 = [a *:] [a [0 0] . i a [0 1] . 1 a _ _x cond_] ifte } ;
; cond_ { [b t e x] x \s b t [e cond] ifte } ;

xy doesn't have anything like a "return stack", but it's pretty
convenient to have something like factor's >r and r>. that is,
an operator to take a value from the stack and stash it somewhere
out of the way, and then later recall it to the stack.

my solution is to have / and \ (the equivalents of >r and <r)
use *the other end* of the input queue y, as though it was a stack.
for that reason, y has the characteristics of both a queue AND a
stack. a colleague suggested that i call it a "quack".

here's an example:

"2dip" def
-rot / / i \ \

clear

1 trace 2 3 111 222 [+] 2dip
: 1 trace 2 3 111 222 [+] 2dip
1 : trace 2 3 111 222 [+] 2dip
: 2 3 111 222 [+] 2dip
2 : 3 111 222 [+] 2dip
2 3 : 111 222 [+] 2dip
2 3 111 : 222 [+] 2dip
2 3 111 222 : [+] 2dip
2 3 111 222 [+] : 2dip
2 3 111 222 [+] : -rot / / i \ \
2 3 111 222 [+] : { [a b c] c a b } / / i \ \
2 3 : [+] 111 222 / / i \ \
2 3 [+] : 111 222 / / i \ \
2 3 [+] 111 : 222 / / i \ \
2 3 [+] 111 222 : / / i \ \
2 3 [+] 111 : / i \ \ 222
2 3 [+] : i \ \ 222 111
2 3 [+] : // \ \ 222 111
2 3 : + \ \ 222 111
5 : \ \ 222 111
5 111 : \ 222
5 111 222

/ and \ cache to and from the end of the input queue.

// takes the top of the result stack, quotes it, and pushes it back
onto the front of the input queue, so that it will be the next item
processed.

\\ takes the next item on the input queue (the one about to be
processed) and pushes it onto the result stack. for example,

2 3 \\ + //
: 2 3 \\ + //
2 : 3 \\ + //
2 3 : \\ + //
2 3 + : //
2 3 : +
5

// is actually a generalization of the 'i' combinator:

2 3 [+] //
: 2 3 [+] //
2 : 3 [+] //
2 3 : [+] //
2 3 [+] : //
2 3 : +
5

Slava Pestov — 2004-07-19 02:32:11

Hi Steve,

Good to hear about your experiments with concatenative languages again!

> ; cons { [a b] [a] b , } ;

I don't understand this.

> the car of one of these definitions is a pattern, and the cdr
> is code containing elements of the pattern.

Does this mean code can be inspected and constructed at runtime?

> a parameterized callcc is:
>
> ; callcc { [q n] [_x _y n continue] q i } ;
> ; continue { [x_ y_ n] \c x_ i n -: _x # i y_ /s } ;
>
> ; callcc0 0 callcc ;
> ; callcc1 1 callcc ;

Nice!

> // takes the top of the result stack, quotes it, and pushes it back
> onto the front of the input queue, so that it will be the next item
> processed.
>
> \\ takes the next item on the input queue (the one about to be
> processed) and pushes it onto the result stack. for example,

Interesting.

I notice your language has side effects (variable assignment). What made
you choose this approach, compared to your earlier cK (which if I recall
was purely functional)?

Slava

stevan apter — 2004-07-19 10:08:39

----- Original Message -----
From: "Slava Pestov" <slava@...>
To: <concatenative@yahoogroups.com>
Sent: Sunday, July 18, 2004 10:32 PM
Subject: Re: [stack] XY

> Hi Steve,
>
> Good to hear about your experiments with concatenative languages again!
>
>
> > ; cons { [a b] [a] b , } ;
>
> I don't understand this.

cons expects two items on the stack, a and b:

[a b]

what it will leave on the stack is

[a] b ,

the join of the enlist of a with b. alternatively:

[unit] dip ,

(but don't be misled into thinking that these are factor's "cons
cells". they're not. e.g.

10 20 cons
[10 20]
10 [20] cons
[10 20]

i debated about whether to error trap the first case, the way
joy does:

{ [a b] b list? [[a] b ,] ["not a list" error] ifte }

then decided it wasn't necessary at this stage.)

>
> > the car of one of these definitions is a pattern, and the cdr
> > is code containing elements of the pattern.
>
> Does this mean code can be inspected and constructed at runtime?

you mean, can {}-expressions be constructed? yes, for example,

1 trace

10 20 [ { ] i [a b] b a }
: 10 20 [{] i [a b] b a }
10 : 20 [{] i [a b] b a }
10 20 : [{] i [a b] b a }
10 20 [{] : i [a b] b a }
10 20 [{] : // [a b] b a }
10 20 : { [a b] b a }
: 20 10
20 : 10
20 10

as in joy and factor, programs-as-lists can also be constructed
and manipulated at run-time, then executed with 'i'.

>
> > a parameterized callcc is:
> >
> > ; callcc { [q n] [_x _y n continue] q i } ;
> > ; continue { [x_ y_ n] \c x_ i n -: _x # i y_ /s } ;
> >
> > ; callcc0 0 callcc ;
> > ; callcc1 1 callcc ;
>
> Nice!
>
> > // takes the top of the result stack, quotes it, and pushes it back
> > onto the front of the input queue, so that it will be the next item
> > processed.
> >
> > \\ takes the next item on the input queue (the one about to be
> > processed) and pushes it onto the result stack. for example,
>
> Interesting.
>
> I notice your language has side effects (variable assignment). What made
> you choose this approach, compared to your earlier cK (which if I recall
> was purely functional)?

i added .s and .g (your 'set' and 'get') in order to make chris's
continuation exercises work. i don't regard either one as essential
vocabulary.

>
> Slava
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>

stevan apter — 2004-07-20 22:27:40

i've fixed a few bugs, and further trimmed the set of primitives.
here they are:

k: ~!@#$%^&*_-+=|<,>?.:

f dyad
f: monad
f. commute dyad

k system functions, n:, &c.

( ) comment 2 3 ( not executed ) + -> 5

{ } pattern-set { [a b] a b + a * }

{{ }} pattern-get {{ a [b] [c d] }}

/s stack 1 2 3 /s 4 5 6 -> 1 2 3 [4 5 6]
\s queue 1 2 3 \s 4 5 6 -> 1 2 3 [1 2 3] 4 5 6

\\ quote 1 2 3 \\ + -> 1 2 3 +
// unquote 1 2 3 [+] // -> 1 5

/ cache 1 2 3 / 4 5 6 -> 1 2 4 5 6 3
\ uncache 1 2 3 / 4 \ 5 6 -> 1 2 4 3 5 6

; define ; inc 1 + ;

: amend [1 2 3] 1 99 @ -> [1 99 3]

.s set [-1 +] "dec" .s
.g get "dip" .g -> [swap / i \]

.p parse "[1 2 3]" .p -> [[1 2 3]]
.r represent [[1 2 3]] .r -> "[1 2 3]"

.i read 10 .i -> 10 "what you type"
.o write "print this" write

words word-list words -> [@4 .4 @3 .3 exit ..
error error "signal this message" error
stop stop 2 3 stop + -> stops before + in console
trace trace 1 trace -> print step and wait for <enter>
trap trap 0 trap -> on error, go idle

exit exit
k exit to k

i believe that this is sufficient to define all the joy combinators.
for example:

; infra { [a p] \g / a p , i \g \ \g |: uncons , i } ;

stevan apter — 2004-07-20 23:45:54

oops - a few mistakes in the earlier draft.

---------

xy primitives:

k: ~!@#$%^&*_-+=|<,>?.:

f dyad
f: monad
f. commute dyad

system functions, n:, &c.

( ) comment 2 3 ( not executed ) + -> 5

{ } pattern-set { [a b] a b + a * }

{{ }} pattern-get {{ a [b] [c d] }}

\s stack 1 2 [4 5 6] \s -> 4 5 6
/s queue 1 2 3 /s 4 5 6 -> 1 2 3

\\ quote 1 2 3 \\ + -> 1 2 3 +
// unquote 1 2 3 [+] // -> 1 5

/ cache 1 2 3 / 4 5 6 -> 1 2 4 5 6 3
\ uncache 1 2 3 / 4 \ 5 6 -> 1 2 4 3 5 6

; define ; inc 1 + ;

: amend [1 2 3] 1 99 : -> [1 99 3]

.s set [-1 +] "dec" .s
.g get "dip" .g -> [swap / i \]

.p parse "[1 2 3]" .p -> [[1 2 3]]
.r represent [[1 2 3]] .r -> "[1 2 3]"

.i read 10 .i -> 10 "what you type"
.o write "print this" write

words word-list words -> [@4 .4 @3 .3 exit ..
error error "signal this message" error
stop stop 2 3 stop + -> stops before + in console
trace trace 1 trace -> print step and wait for <enter>
trap trap 0 trap -> on error, go idle

exit exit
k exit to k