stevan apter — 2005-06-05 23:55:28

a SLACK program consists of an expression followed by zero
or more definitions:

expression
{definition}
:
{definition}

a definition has the form

{name arguments is expression
{definition}
:
{definition}}

a definition may contain references to definitions at its
level or definitions it contains. for example

f x is g x
{g x is if x=0 then 0 else h x-1}
{h x is if x=0 then 0 else g x-1}

f x is g h x+1
{g y is y-3}
{h z is z%2}

a SLACK program is compiled into a binary tree in which all
references to definitions and variables are eliminated.

here's the stripped-down version of the (lazy) evaluator
(no cache, no common-sub-expression elimination):

X.S:{[f;g;x](A;(A;f;x);(A;g;x))}
X.K:{[x;y](A;`I;x)}
X.I:{[x]x}
X.B:{[f;g;x](A;f;(A;g;x))}
X.C:{[f;g;x](A;(A;f;x);g)}
X.S_:{[c;f;g;x](A;(A;c;(A;f;x));(A;g;x))}
X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
X.Y:{[f](A;f;(A;`Y;f))}
X.U:{[f;z](A;(A;f;(A;H;z));(A;T;z))}

Trace:0
trace:{[t]if[Trace;`0:Trace$rep t;if[#0:`;Trace::0]]}

eval:{[t](A~*:)red/t}
red:{[t]trace t;step . t}

step:{[a;b;c]
:[(2#b)~(A;I) ;func b[2][eval c]
(2#b)~(A;O) ;cond[b 2;c]
(2#b)~(A;C) ;cons[b 2]c
b~H ;eval c[1]2
b~T ;eval c 2
exec[left b]c]}

exec:{[b;c]:[7=4:b;b[c];_n~b;c;A~*b;(A;b;c);b c]}
left:{[b]:[A~*b;red b;b _in!X;X b;b]}
func:{[t]:[7=4:t;(A;I;t);t]}
cons:{[b;c](,eval b),eval c}
cond:{[i;t;e]:[eval i;eval t;eval e]}

sa@dfa.com — 2005-06-07 17:04:08

a SLACK script is a text file containing zero or more SLACK
programs (see below.)

each program begins in column 1, and subordinate definitions
are indented at least one position. e.g.,

[1 2;[3 4;5]]

/ comment

hd [1 2;!-1]

10 20 30@1

7+[1 2;[3 4]]

hd tl [1 2 ; 3 4 5]

\

stop executing when \ in column 1

f g 3
{f x is -x}
{g x is !x}

f 3
{f x is g x}
{g x is x+10}

fac 5
{fac n is if n=0 then 1 else n*fac n-1}

f 3
{f x is if x=0 then 0 else g x-1}
{g x is if x=0 then 0 else f x-1}

the interpreter executes each program and returns the
results as a list.

the cache is implemented, as are lazy lists.

here's the eval, which is a bit larger (my previous
implementations of hd and tl were incorrect.)

/ combinator rewrite rules

X.S:{[f;g;x]p:S x;(A;(A;f;p);(A;g;p))}
X.K:{[x;y](A;`I;x)}
X.I:{[x]x}
X.B:{[f;g;x](A;f;(A;g;x))}
X.C:{[f;g;x](A;(A;f;x);g)}
X.S_:{[c;f;g;x]p:S x;(A;(A;c;(A;f;p));(A;g;p))}
X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
X.Y:{[f]p:S(A;`Y;f);(A;f;p)}
X.U:{[f;z]p:S z;(A;(A;f;(A;H;p));(A;T;p))}

S:{(A;G;:[x _in Z;Z?x;-1+#Z,:,x])} / set cache
G:{:Z[x]:lazy Z x} / get cache

Trace:0
trace:{[t]if[Trace;`0:(Trace>0),:/(-__abs Trace)$rep
t;if[Trace<0;if[#0:`;Trace::0]]]}

eval:{[t]Z::();strict t} / eval (set cache, strict)

red:{[t]trace t;step . t} / reduce

strict:(7=4:*:)red/ / strict evaluation
lazy:(A~*:)red/ / lazy evaluation
list:(~P~*:)red/ / lazy-list evaluation
hd:{x 1}list@ / car
tl:{x 2}list@ / cdr

step:{[a;b;c]
:[(2#b)~(A;I) ;func b[2][strict c] / primitive
(2#b)~(A;O) ;cond[b 2;c] / conditional
(2#b)~(A;C) ;pair[b 2]c / cons -> pair
a~P ;cons[b]c / make a list
b~H ;hd c / head of list
b~T ;tl c / tail of list
A~*b ;exec[red b]c / application
b _in!X ;exec[X b]c / combinator
exec[b]c]} / apply primitive

exec:{[b;c]:[7=4:b;b[c];A~*b;(A;b;c);b c]} / func or apply or index
func:{[t]:[7=4:t;(A;I;t);t]} / evaluate a primitive
pair:{[b;c](A;`I;(P;b;c))} / create a pair
cond:{[a;b;c]:[strict a;lazy b;lazy c]} / nb: srict in condition
cons:{[b;c](,strict b),strict c} / create a list

left to do: common subexpression elimination, interactive
console.

concatenative@yahoogroups.com wrote on 06/05/2005 07:55:28 PM:

> a SLACK program consists of an expression followed by zero
> or more definitions:
>
> expression
> {definition}
> :
> {definition}
>
> a definition has the form
>
> {name arguments is expression
> {definition}
> :
> {definition}}
>
> a definition may contain references to definitions at its
> level or definitions it contains. for example
>
> f x is g x
> {g x is if x=0 then 0 else h x-1}
> {h x is if x=0 then 0 else g x-1}
>
> f x is g h x+1
> {g y is y-3}
> {h z is z%2}
>
> a SLACK program is compiled into a binary tree in which all
> references to definitions and variables are eliminated.
>
> here's the stripped-down version of the (lazy) evaluator
> (no cache, no common-sub-expression elimination):
>
> X.S:{[f;g;x](A;(A;f;x);(A;g;x))}
> X.K:{[x;y](A;`I;x)}
> X.I:{[x]x}
> X.B:{[f;g;x](A;f;(A;g;x))}
> X.C:{[f;g;x](A;(A;f;x);g)}
> X.S_:{[c;f;g;x](A;(A;c;(A;f;x));(A;g;x))}
> X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
> X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
> X.Y:{[f](A;f;(A;`Y;f))}
> X.U:{[f;z](A;(A;f;(A;H;z));(A;T;z))}
>
> Trace:0
> trace:{[t]if[Trace;`0:Trace$rep t;if[#0:`;Trace::0]]}
>
> eval:{[t](A~*:)red/t}
> red:{[t]trace t;step . t}
>
> step:{[a;b;c]
> :[(2#b)~(A;I) ;func b[2][eval c]
> (2#b)~(A;O) ;cond[b 2;c]
> (2#b)~(A;C) ;cons[b 2]c
> b~H ;eval c[1]2
> b~T ;eval c 2
> exec[left b]c]}
>
> exec:{[b;c]:[7=4:b;b[c];_n~b;c;A~*b;(A;b;c);b c]}
> left:{[b]:[A~*b;red b;b _in!X;X b;b]}
> func:{[t]:[7=4:t;(A;I;t);t]}
> cons:{[b;c](,eval b),eval c}
> cond:{[i;t;e]:[eval i;eval t;eval e]}
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>

stevan apter — 2005-06-07 22:55:49

common sub-expression elimination works nicely.

example: the execution tree for the expression

(!3)+!3

is (*unicode alert*):

show"(!3)+!3"
┌─────▀──────┐
│ │
`K ┌─────▀─────┐
│ │
┌──▀───┐ ┌─▀─┐
│ │ │ │
┌▀┐ ┌─▀─┐ ┌▀┐ 3
│ │ │ │ │ │
:: + ┌▀┐ 3 :: !:
│ │
:: !:

before executing, we identify the two instances of
the subtree for !3, cache the subtree, and replace
each instance with a pointer to the cache. when
the pointer is executed the first time, it evaluates
the subtree and replaces the cache with the result,
as can be seen after executing:

Z
,0 1 2

(that is, !3 -> 0 1 2)

the common subexpression elimination code:

/ cache common sub-expressions:

leaves:{[t]:[@t;,();,/(!#t),/:'_f't[]]}
nodes:{[p]{x@>#:'x}@?,/{(-1_1+!#x)#\:x}'p}
paths:nodes leaves@

cse:{[t]
k:&(~(A;I)~2#)'d i[;0]j:&1<#:'i:=d:t ./:p:paths t
{sub[;;y]. x}/[(();t);p i j k]}

sub:{[z;t;p]
q:(A;G;-1+#z,:,t .*p)
t:{.[x;y;:;q]}/[t;p]
(z;t)}

i think it's worthwhile pointing out that the
SLACK implementation is first-to-last wholly
loop-free.

i said earlier that i believe the SLACK compiler/
evaluator is indifferent to the syntax of the
source language. the compiler expects a certain
form of p-tree and produces an e-tree. so any
language which maps to the right kind of p-tree
should work. so, at some point, i'll implement a
little joy parser to test that belief.

i'd be interested in hearing from readers of this
list who've implemented joy in haskell (i know
there've been several), and who've retained or
exploited haskell's innate laziness to advantage.

----- Original Message -----
From: <sa@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, June 07, 2005 1:04 PM
Subject: Re: [stack] a lazy k (update)

> a SLACK script is a text file containing zero or more SLACK
> programs (see below.)
>
> each program begins in column 1, and subordinate definitions
> are indented at least one position. e.g.,
>
> [1 2;[3 4;5]]
>
> / comment
>
> hd [1 2;!-1]
>
> 10 20 30@1
>
> 7+[1 2;[3 4]]
>
> hd tl [1 2 ; 3 4 5]
>
> \
>
> stop executing when \ in column 1
>
> f g 3
> {f x is -x}
> {g x is !x}
>
> f 3
> {f x is g x}
> {g x is x+10}
>
> fac 5
> {fac n is if n=0 then 1 else n*fac n-1}
>
> f 3
> {f x is if x=0 then 0 else g x-1}
> {g x is if x=0 then 0 else f x-1}
>
> the interpreter executes each program and returns the
> results as a list.
>
> the cache is implemented, as are lazy lists.
>
> here's the eval, which is a bit larger (my previous
> implementations of hd and tl were incorrect.)
>
> / combinator rewrite rules
>
> X.S:{[f;g;x]p:S x;(A;(A;f;p);(A;g;p))}
> X.K:{[x;y](A;`I;x)}
> X.I:{[x]x}
> X.B:{[f;g;x](A;f;(A;g;x))}
> X.C:{[f;g;x](A;(A;f;x);g)}
> X.S_:{[c;f;g;x]p:S x;(A;(A;c;(A;f;p));(A;g;p))}
> X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
> X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
> X.Y:{[f]p:S(A;`Y;f);(A;f;p)}
> X.U:{[f;z]p:S z;(A;(A;f;(A;H;p));(A;T;p))}
>
> S:{(A;G;:[x _in Z;Z?x;-1+#Z,:,x])} / set cache
> G:{:Z[x]:lazy Z x} / get cache
>
> Trace:0
> trace:{[t]if[Trace;`0:(Trace>0),:/(-__abs Trace)$rep
> t;if[Trace<0;if[#0:`;Trace::0]]]}
>
> eval:{[t]Z::();strict t} / eval (set cache, strict)
>
> red:{[t]trace t;step . t} / reduce
>
> strict:(7=4:*:)red/ / strict evaluation
> lazy:(A~*:)red/ / lazy evaluation
> list:(~P~*:)red/ / lazy-list evaluation
> hd:{x 1}list@ / car
> tl:{x 2}list@ / cdr
>
> step:{[a;b;c]
> :[(2#b)~(A;I) ;func b[2][strict c] / primitive
> (2#b)~(A;O) ;cond[b 2;c] / conditional
> (2#b)~(A;C) ;pair[b 2]c / cons -> pair
> a~P ;cons[b]c / make a list
> b~H ;hd c / head of list
> b~T ;tl c / tail of list
> A~*b ;exec[red b]c / application
> b _in!X ;exec[X b]c / combinator
> exec[b]c]} / apply primitive
>
> exec:{[b;c]:[7=4:b;b[c];A~*b;(A;b;c);b c]} / func or apply or index
> func:{[t]:[7=4:t;(A;I;t);t]} / evaluate a primitive
> pair:{[b;c](A;`I;(P;b;c))} / create a pair
> cond:{[a;b;c]:[strict a;lazy b;lazy c]} / nb: srict in condition
> cons:{[b;c](,strict b),strict c} / create a list
>
> left to do: common subexpression elimination, interactive
> console.
>
> concatenative@yahoogroups.com wrote on 06/05/2005 07:55:28 PM:
>
> > a SLACK program consists of an expression followed by zero
> > or more definitions:
> >
> > expression
> > {definition}
> > :
> > {definition}
> >
> > a definition has the form
> >
> > {name arguments is expression
> > {definition}
> > :
> > {definition}}
> >
> > a definition may contain references to definitions at its
> > level or definitions it contains. for example
> >
> > f x is g x
> > {g x is if x=0 then 0 else h x-1}
> > {h x is if x=0 then 0 else g x-1}
> >
> > f x is g h x+1
> > {g y is y-3}
> > {h z is z%2}
> >
> > a SLACK program is compiled into a binary tree in which all
> > references to definitions and variables are eliminated.
> >
> > here's the stripped-down version of the (lazy) evaluator
> > (no cache, no common-sub-expression elimination):
> >
> > X.S:{[f;g;x](A;(A;f;x);(A;g;x))}
> > X.K:{[x;y](A;`I;x)}
> > X.I:{[x]x}
> > X.B:{[f;g;x](A;f;(A;g;x))}
> > X.C:{[f;g;x](A;(A;f;x);g)}
> > X.S_:{[c;f;g;x](A;(A;c;(A;f;x));(A;g;x))}
> > X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
> > X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
> > X.Y:{[f](A;f;(A;`Y;f))}
> > X.U:{[f;z](A;(A;f;(A;H;z));(A;T;z))}
> >
> > Trace:0
> > trace:{[t]if[Trace;`0:Trace$rep t;if[#0:`;Trace::0]]}
> >
> > eval:{[t](A~*:)red/t}
> > red:{[t]trace t;step . t}
> >
> > step:{[a;b;c]
> > :[(2#b)~(A;I) ;func b[2][eval c]
> > (2#b)~(A;O) ;cond[b 2;c]
> > (2#b)~(A;C) ;cons[b 2]c
> > b~H ;eval c[1]2
> > b~T ;eval c 2
> > exec[left b]c]}
> >
> > exec:{[b;c]:[7=4:b;b[c];_n~b;c;A~*b;(A;b;c);b c]}
> > left:{[b]:[A~*b;red b;b _in!X;X b;b]}
> > func:{[t]:[7=4:t;(A;I;t);t]}
> > cons:{[b;c](,eval b),eval c}
> > cond:{[i;t;e]:[eval i;eval t;eval e]}
> >
> >
> >
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
> >
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>

stevan apter — 2005-06-07 23:01:59

oops - what a mess. here's the ascii version of that
last message:

-----------

common sub-expression elimination works nicely.

example: the execution tree for the expression

(!3)+!3

is:

show"(!3)+!3"
+-----¯------+
¦ ¦
`K +-----¯-----+
¦ ¦
+--¯---+ +-¯-+
¦ ¦ ¦ ¦
+¯+ +-¯-+ +¯+ 3
¦ ¦ ¦ ¦ ¦ ¦
:: + +¯+ 3 :: !:
¦ ¦
:: !:

before executing, we identify the two instances of
the subtree for !3, cache the subtree, and replace
each instance with a pointer to the cache. when
the pointer is executed the first time, it evaluates
the subtree and replaces the cache with the result,
as can be seen after executing:

Z
,0 1 2

(that is, !3 -> 0 1 2)

the common subexpression elimination code:

/ cache common sub-expressions:

leaves:{[t]:[@t;,();,/(!#t),/:'_f't[]]}
nodes:{[p]{x@>#:'x}@?,/{(-1_1+!#x)#\:x}'p}
paths:nodes leaves@

cse:{[t]
k:&(~(A;I)~2#)'d i[;0]j:&1<#:'i:=d:t ./:p:paths t
{sub[;;y]. x}/[(();t);p i j k]}

sub:{[z;t;p]
q:(A;G;-1+#z,:,t .*p)
t:{.[x;y;:;q]}/[t;p]
(z;t)}

i think it's worthwhile pointing out that the
SLACK implementation is first-to-last wholly
loop-free.

i said earlier that i believe the SLACK compiler/
evaluator is indifferent to the syntax of the
source language. the compiler expects a certain
form of p-tree and produces an e-tree. so any
language which maps to the right kind of p-tree
should work. so, at some point, i'll implement a
little joy parser to test that belief.

i'd be interested in hearing from readers of this
list who've implemented joy in haskell (i know
there've been several), and who've retained or
exploited haskell's innate laziness to advantage.

----- Original Message -----
From: <sa@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, June 07, 2005 1:04 PM
Subject: Re: [stack] a lazy k (update)

>
>
>
>
>
> a SLACK script is a text file containing zero or more SLACK
> programs (see below.)
>
> each program begins in column 1, and subordinate definitions
> are indented at least one position. e.g.,
>
> [1 2;[3 4;5]]
>
> / comment
>
> hd [1 2;!-1]
>
> 10 20 30@1
>
> 7+[1 2;[3 4]]
>
> hd tl [1 2 ; 3 4 5]
>
> \
>
> stop executing when \ in column 1
>
> f g 3
> {f x is -x}
> {g x is !x}
>
> f 3
> {f x is g x}
> {g x is x+10}
>
> fac 5
> {fac n is if n=0 then 1 else n*fac n-1}
>
> f 3
> {f x is if x=0 then 0 else g x-1}
> {g x is if x=0 then 0 else f x-1}
>
> the interpreter executes each program and returns the
> results as a list.
>
> the cache is implemented, as are lazy lists.
>
> here's the eval, which is a bit larger (my previous
> implementations of hd and tl were incorrect.)
>
> / combinator rewrite rules
>
> X.S:{[f;g;x]p:S x;(A;(A;f;p);(A;g;p))}
> X.K:{[x;y](A;`I;x)}
> X.I:{[x]x}
> X.B:{[f;g;x](A;f;(A;g;x))}
> X.C:{[f;g;x](A;(A;f;x);g)}
> X.S_:{[c;f;g;x]p:S x;(A;(A;c;(A;f;p));(A;g;p))}
> X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
> X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
> X.Y:{[f]p:S(A;`Y;f);(A;f;p)}
> X.U:{[f;z]p:S z;(A;(A;f;(A;H;p));(A;T;p))}
>
> S:{(A;G;:[x _in Z;Z?x;-1+#Z,:,x])} / set cache
> G:{:Z[x]:lazy Z x} / get cache
>
> Trace:0
> trace:{[t]if[Trace;`0:(Trace>0),:/(-__abs Trace)$rep
> t;if[Trace<0;if[#0:`;Trace::0]]]}
>
> eval:{[t]Z::();strict t} / eval (set cache, strict)
>
> red:{[t]trace t;step . t} / reduce
>
> strict:(7=4:*:)red/ / strict evaluation
> lazy:(A~*:)red/ / lazy evaluation
> list:(~P~*:)red/ / lazy-list evaluation
> hd:{x 1}list@ / car
> tl:{x 2}list@ / cdr
>
> step:{[a;b;c]
> :[(2#b)~(A;I) ;func b[2][strict c] / primitive
> (2#b)~(A;O) ;cond[b 2;c] / conditional
> (2#b)~(A;C) ;pair[b 2]c / cons -> pair
> a~P ;cons[b]c / make a list
> b~H ;hd c / head of list
> b~T ;tl c / tail of list
> A~*b ;exec[red b]c / application
> b _in!X ;exec[X b]c / combinator
> exec[b]c]} / apply primitive
>
> exec:{[b;c]:[7=4:b;b[c];A~*b;(A;b;c);b c]} / func or apply or index
> func:{[t]:[7=4:t;(A;I;t);t]} / evaluate a primitive
> pair:{[b;c](A;`I;(P;b;c))} / create a pair
> cond:{[a;b;c]:[strict a;lazy b;lazy c]} / nb: srict in condition
> cons:{[b;c](,strict b),strict c} / create a list
>
> left to do: common subexpression elimination, interactive
> console.
>
> concatenative@yahoogroups.com wrote on 06/05/2005 07:55:28 PM:
>
> > a SLACK program consists of an expression followed by zero
> > or more definitions:
> >
> > expression
> > {definition}
> > :
> > {definition}
> >
> > a definition has the form
> >
> > {name arguments is expression
> > {definition}
> > :
> > {definition}}
> >
> > a definition may contain references to definitions at its
> > level or definitions it contains. for example
> >
> > f x is g x
> > {g x is if x=0 then 0 else h x-1}
> > {h x is if x=0 then 0 else g x-1}
> >
> > f x is g h x+1
> > {g y is y-3}
> > {h z is z%2}
> >
> > a SLACK program is compiled into a binary tree in which all
> > references to definitions and variables are eliminated.
> >
> > here's the stripped-down version of the (lazy) evaluator
> > (no cache, no common-sub-expression elimination):
> >
> > X.S:{[f;g;x](A;(A;f;x);(A;g;x))}
> > X.K:{[x;y](A;`I;x)}
> > X.I:{[x]x}
> > X.B:{[f;g;x](A;f;(A;g;x))}
> > X.C:{[f;g;x](A;(A;f;x);g)}
> > X.S_:{[c;f;g;x](A;(A;c;(A;f;x));(A;g;x))}
> > X.B_:{[c;f;g;x](A;c;(A;f;(A;g;x)))}
> > X.C_:{[c;f;g;x](A;(A;c;(A;f;x));g)}
> > X.Y:{[f](A;f;(A;`Y;f))}
> > X.U:{[f;z](A;(A;f;(A;H;z));(A;T;z))}
> >
> > Trace:0
> > trace:{[t]if[Trace;`0:Trace$rep t;if[#0:`;Trace::0]]}
> >
> > eval:{[t](A~*:)red/t}
> > red:{[t]trace t;step . t}
> >
> > step:{[a;b;c]
> > :[(2#b)~(A;I) ;func b[2][eval c]
> > (2#b)~(A;O) ;cond[b 2;c]
> > (2#b)~(A;C) ;cons[b 2]c
> > b~H ;eval c[1]2
> > b~T ;eval c 2
> > exec[left b]c]}
> >
> > exec:{[b;c]:[7=4:b;b[c];_n~b;c;A~*b;(A;b;c);b c]}
> > left:{[b]:[A~*b;red b;b _in!X;X b;b]}
> > func:{[t]:[7=4:t;(A;I;t);t]}
> > cons:{[b;c](,eval b),eval c}
> > cond:{[i;t;e]:[eval i;eval t;eval e]}
> >
> >
> >
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
> >
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>

sa@dfa.com — 2005-07-05 14:58:06

my paper on SLACK has reached "first draft" stage:

http://www.nsl.com/k/slack/slack.htm

and a summary will eventually follow. meanwhile, i
continue to exercise the compiler to find its weak
points.

on a related front, work is underway on a parser
front-end for joy (or something not too different
from that language.)

as you might expect, everything gets simpler: the
parser has fewer cases to manage, the compiler
remains the same, and the reduction engine will
see only a proper subset of the SLACK operators.