Re: [stack] Joy in Avail

stevan apter — 2000-06-03 11:25:30

> 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.

> 



 
hi mark



i think i can answer some of your questions.



the core of my joy interpreter is the set of functions:



E:{:[~4=4:y;(,y),x;7=4:v:. y;v x;6=4:v;(,$y),x;x _f/v]}

X:()E/

Y:()E\

O:Parse.out

I:Parse.in

R:{`0:O r:x E/y;r}

S:{`0:,/O'r:x E\y;*|r}

J:{s:();o:(R;S);while[#r:{`0:"joy>";0:`}[];:["\\"=*r;o|:;s:(*o)[s;I r]]]}



J starts the joy console.  while there is input r, let the stack (s) be R

of the stack and the parse of the input.  i.e. s:R[s;I r].



R is defined as the stack (x) evaluated (E) over the input (y).  a side

effect of R is to print (`0:) the new stack at the console.



E is the evaluator:  if the input is not a symbol (~4=4:y) then prepend

it to the stack, else if the evaluation of the input is a function (7=4:

v:. y) then apply it to the stack, else if the evaluated input is null

(6=4:v) then prepend the format of the input to the stack, else the

evaluated input must be a list of some form (i.e. a joy program), so 

recursively evaluate it (x _f/v).



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).



O and I currently point to my quick and dirty joy parser/unparser.  but

you can swap in any syntax you like, merely by redefining Parse.out and

Parse.in.



my goal was to be able to implement joy primitives as k functions.  for

example, the basic stack functions are:



id:(::)                        / identity returns the stack

false:{0,x}                    / put 0 on the stack

true:{1,x}                     / put 1 on the stack

stack:{(,x),x}                 / put the enlisted stack on the stack

newstack:{x;()}                / return the empty stack

unstack:{x[0],1_ x}            / unlist the top of the stack

pop:1_                         / drop the top of the stack

dup:{x[,0],x}                  / prepend the enlisted top of the stack

swap:{@[x;1 0;:;2#x]}          / reverse the top 2 in place

rollup:{x[1 2 0],3_ x}         / etc.

rolldown:{x[2 0 1],3_ x}

choice:{(x[0 1]x 3),3_ x}



now to your question:  i defined e.g. swapd as:



    I"[swap]dip"



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.



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.  



in brief, there are three ways to use the k implementation of joy:



    as an interactive interpreter via J[]



    as a sublanguage within k, using I, O, and X (or Y):



        X I"1 2 +"

    ,3



        Y I"1 2 +"

    (()

     ,1

     2 1

     ,3)



    as a set of subfunctions, each of which takes a stack, i.e.,



        plus 1 2

    ,3



hope this helps (a revised version is included below - i still

haven't found the time to complete the implementation)



--



/ joy in k



/ joy <-> k (quick & dirty)



\d Parse

types:{:[4:x;type x;_f'x]}

type:{:[(*x)_in*Ops;Ops[1;Ops[0]?*x];&/x _lin"_.0123456789";.@[x;&x="_";:;"-"];"\""=*x;1_-1_ x;"'"=*x;x 1;`$x]}

parts:{a:ol x;b:"["=*:'a;a[&b],:;a:@[a;&~b;ob];r:(,/a)_dv"";@[r;&"["=*:'r;_f 1_-1_]}

sa:{,/@[x;&uq[x]&x=y;:[;" ",y," "]]}

ol:{(&1(~=)':ls x)_ x}

ob:{1_'(&uq[x]&x=" ")_ x:" ",x}

uq:{~(0<':b)|b:(~=)\(~(!#x)_lin,/0 1+/:x _ss"\\\"")&x="\""}

ls:{~|':~=/+\'uq[" ",x]&/:(" ",x)=/:"[]"}

nl:{@[x;&x _lin"\n\t";:;" "]}

vm:{:[4:x;x,"";1_,/" ",'x]}

in:{types parts(nl vm x)sa/"[]",*Ops}

out:{(1_,/(" ",term@)'|x),"\n"}

term:{:[-3=t:4:x;"\"",x,"\"";1>t;list@_f'x;t=3;"'",x;t=5;_f(+($!x;x[]);`dict);$(Ops[0],,x)Ops[1]?x]}

list:{"[",(1_,/" ",'$x),"]"}

Ops:("&|~+-*/%=<>";`and`or`not`plus`minus`mul`idiv`div`eq`lt`gt)

\d ^



/ eval, console, &c.



E:{:[~4=4:y;(,y),x;7=4:v:. y;v x;6=4:v;(,$y),x;x _f/v]}

X:()E/

Y:()E\

O:Parse.out

I:Parse.in

R:{`0:O r:x E/y;r}

S:{`0:,/O'r:x E\y;*|r}

J:{s:();o:(R;S);while[#r:{`0:"joy>";0:`}[];:["\\"=*r;o|:;s:(*o)[s;I r]]]}



/ utilities



Two:{(,Dot[x;2#y]),2 _ y}

One:{@[y;0;x]}

Dot:{:[-3=4:y;.($x),"[",(1_,/";",'"\"",'y,'"\""),"]";x . y]}

Num:{(_ci;::)[(b~z)&a~y]x[b:Ic z;a:Ic y]}

Ic:{:[3=4:*x;_ic x;x]}

Rel:{x[Ic z;Ic y]}

Each:{y{*(,x)E/y}\:x}

Ary:{((1_ y)E/*y),(x+1)_ y}

App:{(((x#1_ y),\:(x+1)_ y)E/\:*y),(x+1)_ y}

Dip:{(x#1_ y),((1+x)_ y)E/*y}

Type:{:[4=4:x;x;~4:x;();-3=4:x;"";*0#x]}

Leaf:{(&/@:'x)|(@x)|-3=4:x}



/ assignment



is:Two[{.[`$x;();:;y]}]



/ general operators



id:(::)

false:{0,x}

true:{1,x}

stack:{(,x),x}

newstack:{x;()}

unstack:{x[0],1_ x}

pop:1_

dup:{x[,0],x}

swap:{@[x;1 0;:;2#x]}

rollup:{x[1 2 0],3_ x}

rolldown:{x[2 0 1],3_ x}

choice:{(x[0 1]x 3),3_ x}

opcase:Two[{((1_'-1_ x),,*|x)((Type@*:)'-1_ x)?Type@*y}]

swapd:I"[swap]dip"

dupd:I"[dup]dip"

popd:I"[pop]dip"

popop:I"pop pop"



/ i/o



put:{}

get:{}

load:{(1_ x)E/I@0:x[0],".joy"}



/ atomic operators



max:or:Two[Num[|]]

min:and:Two[Num[&]]

not:One[~:]

neg:One[-:]

plus:Two[Num[+]]

minus:Two[Num[-]]

mul:Two[*]

div:Two[{y%x}]

rem:Two[{y!x}]

flr:One[_:]

idiv:I"div flr"

sign:One[{(-x<0)+0<x}]

abs:One[_abs]

pred:One[Num[+;-1]]

succ:One[Num[+;1]]



/ list operators



rand:Two[{y _draw x}]

enum:One[!:]

cut:Two[{y _ x}]

find:Two[{y?x}]

up:One[<:]

down:One[>:]

sub:Two[{y@x}]

upsort:I"up sub"

downsort:I"down sub"

cons:Two[{(,y),x}]

swons:I"swap cons"

first:One[*:]

second:One[{x 1}]

third:One[{x 2}]

last:One[*|:]

rest:One[1_]

of:Two[{x:[1=4:y;y;`$y]}]

at:I"swap of"

drop:Two[_]

take:Two[#]

size:One[#:]

reverse:One[|:]

uncons:{((1_;*:)@\:*x),1_ x}

unswons:I"uncons swap"

flatten:One[,/]

transpose:One[+:]

concat:Two[{y,x}]

swoncat:Two[,]

transpose:One[+:]

dict:One[{..[x;(;0);`$]}]



/ predicates



null:One[{:[@x;x=0;~#x]}]

small:One[{:[@x;x<2;2>#x]}]

gt:Two[Rel[>]]

lt:Two[Rel[<]]

eq:Two[Rel[=]]

le:Two[Rel[~>]]

ge:Two[Rel[~<]]

ne:Two[Rel[~=]]

equal:Two[~]

has:Two[_in]

in:Two[{y _in x}]

hasl:Two[_lin]

lin:Two[{y _lin x}]



/ general combinators



i:{(1_ x)E/*x}

x:{x E/*x}

y:{}

b:{((2_ x)E/x 1)E/*x}

nullary:Ary[0]

unary:Ary[1]

binary:Ary[2]

ternary:Ary[3]

dip:Dip[1]

dipd:Dip[2]

dipdd:Dip[3]

app1:App[1]

app2:App[2]

app3:App[3]

app4:App[4]

cleave:{((2_ x){*x E/y}/:2#x),3_ x}

construct:{}

ifte:{((3_ x)E/x@~~*(3_ x)E/x 2),4_ x}

cond:{c:*x;s:1_ x;while[1<#c;if[*s E/*c;:s E/c 1];c:2_ c]}

whiledo:{s:2_ x;while[*s:s E/x 1;s:s E/*x];s}

primrec:{:[x 2;(x[2],_f[@[x;2;-;1]])E/*x;(3_ x)E/x 1]}

linrec:{:[*(4_ x)E/x 3;(4_ x)E/x 2;(_f(4#x),(4_ x)E/x 1)E/*x]}

tailrec:{:[*(3_ x)E/x 2;(3_ x)E/x 1;_f(3#x),(3_ x)E/*x]}

binrec:{:[*(4_ x)E/x 3;(4_ x)E/x 2;((*_f@)'x{@[x;4;:;y]}/:2#(4_ x)E/x 1)E/*x]}  / ?

genrec:{:[*(4_ x)E/x 3;(4_ x)E/x 2;(`genrec,(4#x),(4_ x)E/x 1)E/*x]}

condlinrec:{}



/ atomic combinators



branch:{((3_ x)E/x@~~z),4_ x}

times:{x[0]{y E/x}[x 1]/2_ x}



/ list combinators



infra:{(,x[1]E/*x),2_ x}

step:{{((,z),y)E/x}[*x]/[2_ x;x 1]}

map:{(,(1_'@[x;1;:;]'x 1){*x E/y}\:*x),2_ x}

fold:{(,{*(z;y)E/x}[*x]/[x 1;x 2]),3_ x}

filter:{1_@[x;1;@[;&*map x]]}

split:{((x[1]@&:;x[1]@&~:)@\:*map x),2_ x}

some:{@[map x;0;|/]}

all:{@[map x;0;&/]}



/ tree combinators



treestep:{:[Leaf x 1;step x;(,(*_f@)'x[1]{@[y;1;:;x]}\:x),2_ x]}

treerec:{:[Leaf x 2;(2_ x)E/x 1;((,`treerec,2#x),(2_ x))E/*x]}

treegenrec:{}



/ test routines



unitlist:I"[]cons"

shunt:I"[swons]step"

reverselist1:I"[]swap shunt"

reverselist2:I"[]swap infra"

restlist:I"[null][unitlist][dup rest][cons]linrec"

frontlist:I"[null][unitlist][uncons][[cons]map popd dup first rest swons]linrec"

subseqlist1:I"frontlist[restlist]map"

subseqlist2:I"[null][unitlist][uncons dup[frontlist[cons]map popd]dip][concat]linrec"

powerlist1:I"[null] [[] cons] [uncons][dup swapd [cons] map popd concat] linrec"

powerlist2:I"[null] [[] cons] [uncons][dup swapd [cons] map popd swoncat] linrec"

treesum:I"0 swap[+]treestep"

treesize:I"0 swap[pop succ]treestep"

treeshunt:I"[swons]treestep"

treeflatten:I"[]swap treeshunt reverse"



qsort:I"[small] [] [uncons [>] split] [swapd dip cons concat] binrec"

    

J[]

stevan apter — 2000-06-03 11:39:43

> 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.



 
good question (which i neglected to answer!)



yes, any k function can use I, since it's just another k function, but i can't

think of a situtation where i would want to do that.



one reason i abandoned work on the interpreter is that it doesn't conform strictly

enough to manfred's definition of the language.  in part, this was because i didn't

(don't) understand how metasyntax like "HIDE", "IN", and "==" work.



by the way, has anyone here been in communication with manfred?  (i've been

assuming that he's not on the mailing list.)  is he continuing work on joy?

(the joy section of his website doesn't seem to have been updated in quite

a while).  



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?

wtanksley@bigfoot.com — 2000-06-05 16:54:46

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



 >by the way, has anyone here been in communication with 

>manfred?  (i've been

>assuming that he's not on the mailing list.)  is he continuing 

>work on joy?

>(the joy section of his website doesn't seem to have been 

>updated in quite a while).  



 
He's working on a book on it, and he's subscribed to the list.



-Billy