----- Original Message -----
From: Mark van Gulik <ghoul6@...>
To: <concatenative@egroups.com>
Sent: Sunday, June 04, 2000 2:32 PM
Subject: [stack] Re: Joy in Avail

> "stevan apter" <apter@...> wrote:
> > Subject: Re: Joy in Avail
> >
> >> I believe the K implementation Stevan Apter <apter@...> submitted
> >> earlier is more concise and much more comprehensive (neither feature was a
> >> goal for me at this time). On the other hand, it required the Joy
> >> expressions to be quoted (via 'I"'). I may have misunderstood the K code,
> >> but it seemed that some Joy operations were defined via 'I"' quoted Joy
> >> expresions, but others were defined via K code directly. I didn't see any
> >> mixtures, and I don't understand the implementation well enough to hazard a
> >> guess whether it would be possble to mix the Joy and K code in a definition.
>
> Thank you for that beautifully detailed description of your Joy interpreter
> in K.

my pleasure.

>
> > X and Y are two ways to recursively evaluate the stack. remember that
> > in my implementation, the stack is a list s. ()E/s takes any stack and
> > reduces it to a single evaluated item. ()E\s takes an stack, reduces
> > it, and returns a list each of whose items is the stack reduction up
> > to that point. X and Y are designed to be used directly, in k (see
> > below).
> ...
> > E:{:[~4=4:y;(,y),x;7=4:v:. y;v x;6=4:v;(,$y),x;x _f/v]}
> > X:()E/
> > Y:()E\
>
> So your X function takes a stack and a program... (?).

a stack and a *list* of programs. see below.

Hm, I'm lost on this
> one. I realize the Joy interpreter E is kind of 'invoked' via X or Y, but
> where does the Joy program go? Oh wait, that was extracted as a side-effect
> from the input stream, right? So X returns the result of running the next
> "line" of code on the given stack, but Y returns a list of states the stack
> passes through during evaluation. I assume Y is for debugging?

/ and \ are fundamental k iterators. consider

6+/2 5 7
20
6+\2 5 7
6 8 13 20

(these can also be written: +/[6;2 5 7] and +\[6;2 5 7])

/ (over) is an adverb which takes a verb, in this case, the two-place (or
transitive) verb +, and returns a two-place verb f[x;y] which has the following
semantics:

start by setting r to x = 6
apply f to r and y[0], return r = 8
apply f to r and y[1], return r = 13
apply f to r and y[2], return r = 20

in other words, apply f to r and y[i] for i = 0 to -1+length of y. the case
for verbs and functions of more than two arguments is straightforward:

r:f/[x;y1;...;yn] and r:f\[x;y1;...;yn] for f of n+1 args

the case for verbs and functions of one argument is related, but technically
overloaded:

r:f/x keeps applying f to its result r until r=x or r=the previous r

as you can see, \ (scan) has the same syntax, but the derived verb returns
a list of the r's.

E is a two place function - its first argument is the stack, and its second
argument is something to evaluate. so x E/y computes the state of the stack
x after E has successively evaluated items in y, and x E\y returns a list of
all the intermediate stack-states. to evaluate *one* thing: E[x;y i].

there are no side-effects to E (J uses a side-effect to print the stack at
the console).

() is the empty list: the initial state of the stack. so ()E/ is a one-place
function (a curry of E/, which is in turn a derived function, as per above);
functions are first-class, so we can just define X by assigning that one-place
function to 'X'.

>
>
> > now to your question: i defined e.g. swapd as:
> >
> > I"[swap]dip"
>
> Ah, now I see why it's 'I"'. You're piping a string into the interpreter as
> input.

I is just a function - it takes a string, and busts it up into a k
list. that list is input to E via X.

>
> > as the parse of the joy concatenation [swap]dip. the resulting
> > k list is
> >
> > (,`swap;`dip)
> >
> > a two item list, whose first item is a one-item list of the symbol
> > `swap and whose second item is the symbol `dip. i use I because
> > it allows k to define joy programs as lists more consisely than
> > the primitive list notation of k.
>
> Ok, so you actually parse the string with Joy's (minimal) syntax rules.

right.

> But
> the resulting list is non-executable.

it's just a list. actually, it doesn't contain any function-data. for
example, the joy program 2 3 + is parsed into (2;3;`plus) - a list of
three elements: an int, an int, and the symbol of the k function which
implements joy's +. in the evaluator E, i test to see whether the data
type of the k object whose symbol is `plus is a function. if it is, i
apply it to the stack. if not, i put the string "plus" on the stack.
(strings and symbols are different in k).

> Would it be possible to define a new
> operator Z such that Z"[swap]dip" yields a function of type stack->stack?
> This could be tricky if quotations are allowed to be deconstructed (a
> problem I'm having with an attempt at a typed Joy in Avail).

yikes - that never occurred to me.

ok, consider this. suppose we represent the stack, not as a list, but as
a function. the empty stack is the function

N:{x;()}

it takes anything x and returns the empty list. now what is it to push
a constant item onto the stack? it is a function C which takes the stack
x and prepends y to the application of x to the next item:

C:{(,y),x z}

the application of a function to the stack is a function A which takes
the stack x and applies the function y to the application of x to the
next item:

A:{y x z}

(note that 'x', 'y', and 'z' are the default first, second, and third
arguments for a k function.)

the compiler for joy looks a lot like the evaluator:

F:{:[~4=4:y;C[x;y];7=4:v:. y;A[x;y];6=4:v;C[x;$y];x _f/v]}
Z:N F/
W:N F\

the difference is that start-state for Z and W is the "empty function",
N rather than the empty list. Z returns a function, which of course
must be evaluated (on no arguments):

f:Z I"2 3 plus 4 minus"
f
{y x z}[{(,y),x z}[{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus];4];`minus]
f[]
,1

(we can modify this to start with an arbitrary one-place function instead of N.
for example, the function {x} which takes x and returns x:

g:{x}F/I"2 3 plus 4 minus"
g 10 20 30
1 10 20 30

g:{x}F/I"2 plus"
g[,10 20]
,12 22
)

the scan version of Z produces a list of the intermediate functions:

h:W I"2 3 plus 4 minus"
h 0
{x;()}
h 1
{(,y),x z}[{x;()};2]
h 2
{(,y),x z}[{(,y),x z}[{x;()};2];3]
h 3
{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus]
h 4
{(,y),x z}[{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus];4]
h 5
{y x z}[{(,y),x z}[{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus];4];`minus]

and, if each function in h is applied to nil (another way of running a function
of no arguments) then you get a list of the intermediate results:

h@'_n / each h applied to nil
(()
,2
3 2
,5
4 5
,1)

thanks *very* much for the idea. if nothing else, it demonstrates
an interesting constructive equivalence between concatenativity and
applicativity (if those are words).

>
>
> > a more satisfying implementation of joy would attempt to define as
> > many of the joy operators as possible this way, i.e. as lists rather
> > than k functions.
>
> Yes, defining most Joy operators via Joy leads to better axiomatization.
> But, again, can the list operators be mapped to K functions? Maybe you're
> doing this automatically, or it's a simple matter of applying E (or a
> derivative) to the list. I'm still a bit confused about this.

i'm not sure i understand, but i think what my interpreter is doing
is simpler than you think. probably a side-by-side keyboard session
would dispel your confusion in minutes, if not seconds.

>
>
> > qsort:I"[small] [] [uncons [>] split] [swapd dip cons concat] binrec"
>
> I like this implementation. I saw a three-liner in Clean (a functional
> language) long ago and was likewise impressed.

it's manfred's implementation, from one of the joy papers.

The obvious question for me
> is: What would qsort look like in K? In addition, how short a sort can you
> write, even if you don't care about the efficiency? I.e., even a *cubic*
> time algorithm would be acceptable.

k has <x and >x, implemented as a distribution sort (as described by knuth,
i believe). so in the best case, which is most of the time for finance,
it achieves linear time, but can get really really bad if the data isn't
distributed "well". k tries to do a distribution sort, and if it finds
that it's taking too long, it switches to something else - possibly quick-
sort. as i said, in practice we've always had mindblowing sort performance.
(specs and benchmarks are, or were, given on the kx website, or possibly
in the mailing list archives).

>
>
> ------------------------------------------------------------------------
> Bids starting at $7 for thousands of products - uBid.com
> http://click.egroups.com/1/3027/6/_/_/_/960143531/
> ------------------------------------------------------------------------
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
>

> (we can modify this to start with an arbitrary one-place function instead of N.

i see that i didn't go quite far enough:

C:{(,y),x z}
A:{y x z}
N:{x}
F:{:[~4=4:y;C[x;y];7=4:v:. y;A[x;v];6=4:v;C[x;$y];x _f/v]}
Z:N F/
W:N F\

reverselist:Z I"[]swap infra"
reverselist
{y x z}[{y x z}[{(,y),x z}[{x};()];{@[x;1 0;:;2#x]}];{(,x[1]E/*x),2_ x}]

this version of F compiles into symbol-free functions (there was a typo in the
previous version).

note that if you want Z (or W, X, Y) to do the parsing:

Z:N F/I@
reverselist:Z"[]swap infra"

From: Mark van Gulik [mailto:ghoul6@...]

>"stevan apter" <apter@...> wrote:
>> i've been reading up on the subject of continuations (thank
>> you christian
>> tismer) and it seems as though first-class continuations
>> would be relatively
>> simple to implement in joy. any thoughts on this one?

>A continuation in Joy would simply be a pair consisting of the
>stack, and
>the remaining stream of symbols (which would be in the form of
>a quotation).

That's a LOT more than is needed for a continutation in applicative
languages. I can certainly see why theory would lead you to believe that,
but I suspect that it's more than we strictly need.

I believe that there's sufficient information simply in the execution
pointer, and no stack state is needed. There's only one program in Forth
using continuations that way, but it seems to work very well.

-Billy

----- Original Message -----
From: <wtanksley@...>
To: <concatenative@egroups.com>
Sent: Monday, June 05, 2000 10:05 PM
Subject: RE: [stack] Re: Joy in Avail

> From: Mark van Gulik [mailto:ghoul6@...]
> >"stevan apter" <apter@...> wrote:
> >> i've been reading up on the subject of continuations (thank
> >> you christian
> >> tismer) and it seems as though first-class continuations
> >> would be relatively
> >> simple to implement in joy. any thoughts on this one?
>
> >A continuation in Joy would simply be a pair consisting of the
> >stack, and
> >the remaining stream of symbols (which would be in the form of
> >a quotation).
>
> That's a LOT more than is needed for a continutation in applicative
> languages. I can certainly see why theory would lead you to believe that,
> but I suspect that it's more than we strictly need.
>
> I believe that there's sufficient information simply in the execution
> pointer, and no stack state is needed. There's only one program in Forth
> using continuations that way, but it seems to work very well.

i haven't programmed in a language which supported first-class
continuations, so i have no feel for how one would use them.
despite having read several "continuations demystified" papers,
i'm still not sure i understand what's involved in having them
available.

the only half-way compelling example i've seen thus far (and i
didn't understand the solution) was this one: suppose you've
got a tree t and a simple routine tw which walks the tree and
at each node prints the node name and the depth. output might
be:

0 t
1 a
2 b
2 c
1 d
2 e
3 f
3 g
2 h
etc.

so now imagine that you've got two structurally isomorphic
trees t and u (the original example required only weak
isomorphism). somehow, continuations enable you to use
two coroutines - tw on t and tw on u - to print "in parallel":

0 t u
1 a aa
2 b bb
etc.

i have vague intimiations of what must be going on, but i
can't quite bring it into focus.

my first thought wrt joy was similar to mark's: the current
execution context = the pair:

current state of the stack
everything left to evaluate

in my implementation

x E/y

is the evaluation loop: x is the initial state of the stack,
and y is a list of items to evaluate - a program. (i may have
misled mark in a previous note by insisting that y was a list
of programs - indeed, it is a list, but it is probably correct
to refer to it as a single program.)

i can rewrite x E/y as an explicit loop:

eval:{
while[#y / while there are items in the program list
x:E[x;*y] / let the stack be E of the stack and the first item of y
y:1_ y] / drop the top item from y
x} / return the stack

as you can see, the evaluation primitive E never gets to see
anything but the top item of y. my hunch is that if E were
modified to take y, instead of *y, then the appropriate
continuation primitives could be defined.

i would be grateful if someone could show me why this dog
won't hunt.

>
> -Billy
>
> ------------------------------------------------------------------------
> Everyday Is Kid's Day
> Dad Only Has One
> Click Here To Make It Special
> http://click.egroups.com/1/5038/6/_/_/_/960257046/
> ------------------------------------------------------------------------
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
>

From: stevan apter [mailto:apter@...]

>i haven't programmed in a language which supported first-class
>continuations, so i have no feel for how one would use them.
>despite having read several "continuations demystified" papers,
>i'm still not sure i understand what's involved in having them
>available.

Put bluntly, continuations are like GOTOs on steroids, except that they're
accounted for by theory.

Come to think of it, the reason continuations traditionally need extra
information is that continuation theory was developed for applicative
languages.

>the only half-way compelling example i've seen thus far (and i
>didn't understand the solution) was this one: suppose you've
>got a tree t and a simple routine tw which walks the tree and
>at each node prints the node name and the depth. output might
>be:

There's an example of this in Forth at
http://www.forth.org.ru/~mlg/ef94/ef94-2-paper.txt
, in which the author discusses continuations in terms of backtracking.
Backtracking is a special-purpose use for continuations. There are other
papers on the same site; some of them gave me interesting info, but others
are in Russian, which I don't know.

One interesting thing about this paper is that as in my hypothesis, the
continuation is nothing but an address. There's no need to store current
values of parameters, because there are no parameters in a concatenative
language.

-Billy

a version of conk has been posted at www.kx.com/technical/contribs/stevan
under the joy directory.

a script containing two examples can be found there as well.

to run conk, download k and the two scripts, and say:

k conk

at the prompt

k>script load

then say e.g.

k>prog order

a manual will follow shortly, along with examples.

to escape from the prompt into k, an empty return.

Re: [stack] Re: Joy in Avail

stevan apter — 2000-06-04 20:02:31

stevan apter — 2000-06-04 20:33:40

wtanksley@bigfoot.com — 2000-06-06 02:05:05

stevan apter — 2000-06-06 12:25:11

wtanksley@bigfoot.com — 2000-06-08 20:03:12

stevan apter — 2000-06-12 23:18:33