progress in F
stevan apter — 2006-06-22 21:12:17
"controls"
[pair![dupd!]$'!$swap!false!pair!@!] cond "[c][t][f]cond!"
[[]cond!] if "[c][t]if!"
[unit!cons!dup![;;%]$[while!],,if!] while "[c][t]while!"
[unit![pred!]swap!,'$,[]swap!while!%] do "n[f]do!"
"adverbs"
[':$[dup!count!]$swap!
[';$[consd!]$dup!swapd![[,!]$]$]do!%%] over "s[..][f]over!"
[swap!dup!proto!swap!unit!rot!over!] reduce "[..][f]reduce!"
['+reduce!] sum "[..]sum!"
"stack"
[[]swap![cons!]do!dupd!swap!'!$] get "i get!"
[[]swap!swapd![[cons!]$]do!['%$]$swap!!]set "x i set!"
get and set are useful:
10 20 30 40 2 get!
10 20 30 40 20
gets the nth item down on the stack, makes a copy, puts it at
the top.
10 20 30 40 50 2 set!
10 50 30 40
takes the item just below the index and overwrites the nth item
down on the stack.
map is giving me a headache.
sa@dfa.com — 2006-06-23 14:05:55
map in F:
[[dup!count!]$[pair![]swap!!]$swap!
[';$dup![swap!'!$]$pair![swons!]$!]
do!%%\] map! "[..][f]map!"
for example:
[[1 2 3][4 5 6 7][8 9 10 11 12]][count!]map!
[3 4 5]
[[1 2 3][4 5 6][7 8 9]][!+*]map!
[5 44 119]
joy equivalents:
$ is dup, ; is uncons, % is pop, \ is reverse, ! is i, and 'x is [x].
x y pair -> [x y]
http://www.nsl.com/k/f/prelude.f
concatenative@yahoogroups.com wrote on 06/22/2006 05:12:17 PM:
>
> "controls"
>
> [pair![dupd!]$'!$swap!false!pair!@!] cond "[c][t][f]cond!"
> [[]cond!] if "[c][t]if!"
> [unit!cons!dup![;;%]$[while!],,if!] while "[c][t]while!"
> [unit![pred!]swap!,'$,[]swap!while!%] do "n[f]do!"
>
> "adverbs"
>
> [':$[dup!count!]$swap!
> [';$[consd!]$dup!swapd![[,!]$]$]do!%%] over "s[..][f]over!"
> [swap!dup!proto!swap!unit!rot!over!] reduce "[..][f]reduce!"
> ['+reduce!] sum "[..]sum!"
>
> "stack"
>
> [[]swap![cons!]do!dupd!swap!'!$] get "i get!"
> [[]swap!swapd![[cons!]$]do!['%$]$swap!!]set "x i set!"
>
>
> get and set are useful:
>
> 10 20 30 40 2 get!
> 10 20 30 40 20
>
> gets the nth item down on the stack, makes a copy, puts it at
> the top.
>
> 10 20 30 40 50 2 set!
> 10 50 30 40
>
> takes the item just below the index and overwrites the nth item
> down on the stack.
>
> map is giving me a headache.
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-23 17:57:17
sa@... <
sa@...> wrote:
> map in F:
> [[dup!count!]$[pair![]swap!!]$swap!
> [';$dup![swap!'!$]$pair![swons!]$!]
> do!%%\] map! "[..][f]map!"
F is a facinating language. I've spent a while trying to read some of
your code; not because it's especially hard to read, but because the
math is interesting.
I wonder... Could you discuss some of the design choices? For example,
you decided that "!" would be required to execute every word, thereby
indicating that the most useful thing a word can do is to leave its
address on the stack. Most concatenative languages assume that the
most common thing is to execute a word, not leave an address. I think
I can see your reasoning here -- you're not concerned about terseness
or usability, but rather about mathematical purity. I'd like to hear
your take on this.
-Billy
sa@dfa.com — 2006-06-23 18:26:24
hi billy - nice to see i've snagged your attention (awoken you
from your concatenative slumber?)
actually, a word leaves not its address on the stack, but its
value:
[1 2 3] v "assign [1 2 3] to v"
v "use v"
[1 2 3] "leaves its value on the stack"
! "unquote"
1 2 3
as a matter of fact, i find F easier to use than its cousins.
it's denser (less whitespace), but nearly as terse, since e.g.
swap!dup!proto!swap!unit!rot!over!
which happens to be the code for "reduce" would otherwise be
written
swap dup proto swap unit rot over
it's a little worse in False, where a symbol leaves itself
on the stack, and then you use ; to retrieve its value, and
! to execute:
swap;!dup;!proto;!swap;!unit;!rot;!over;!
which is more like what you describe. but i don't see any
value in breaking things down to that extent.
design choices? i don't know that i had any to begin with,
apart from what i indicated earlier. i begain with False,
added a few operations for manipulating lists, then added
the K operations. in the course of things, i kept simplifying.
at this point, it feels about right, but the real test is what
non-trivial programming is like. up til now, it's taken
me about 10-15 minutes to implement each combinator, which
isn't too bad.
concatenative@yahoogroups.com wrote on 06/23/2006 01:57:17 PM:
> sa@... <sa@...> wrote:
> > map in F:
> > [[dup!count!]$[pair![]swap!!]$swap!
> > [';$dup![swap!'!$]$pair![swons!]$!]
> > do!%%\] map! "[..][f]map!"
>
> F is a facinating language. I've spent a while trying to read some of
> your code; not because it's especially hard to read, but because the
> math is interesting.
>
> I wonder... Could you discuss some of the design choices? For example,
> you decided that "!" would be required to execute every word, thereby
> indicating that the most useful thing a word can do is to leave its
> address on the stack. Most concatenative languages assume that the
> most common thing is to execute a word, not leave an address. I think
> I can see your reasoning here -- you're not concerned about terseness
> or usability, but rather about mathematical purity. I'd like to hear
> your take on this.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-23 19:54:37
sa@... <
sa@...> wrote:
> hi billy - nice to see i've snagged your attention (awoken you
> from your concatenative slumber?)
Indeed :-).
> actually, a word leaves not its address on the stack, but its
> value:
Right; my typo.
I can see that one (of many) nice things about that is that there are
no "special" words. Classic Forth has a few different type of special
words; you don't need any of them.
> as a matter of fact, i find F easier to use than its cousins.
> it's denser (less whitespace), but nearly as terse, since e.g.
> swap!dup!proto!swap!unit!rot!over!
> which happens to be the code for "reduce" would otherwise be
> written
> swap dup proto swap unit rot over
It reminds me of colorforth, actually. In colorforth each word is
preceded by a token that indicates how the parser is to read the next
word; F is a bit simpler in that it doesn't have the token syntax, but
instead defines semantics for the word !.
A side topic: colorForth has the advantage that things other than
ASCII words can be embedded in the source code -- for example, in the
normal distribution, variables are embedded, so that when you edit the
source for something you're currently running you see the current
values of the variables. Another example is icons, or tables.
Of course, nothing prevents you from making a 'smart' editor for F
that could do all of that.
> it's a little worse in False, where a symbol leaves itself
> on the stack, and then you use ; to retrieve its value, and
> ! to execute:
> swap;!dup;!proto;!swap;!unit;!rot;!over;!
> which is more like what you describe. but i don't see any
> value in breaking things down to that extent.
I agree.
> design choices? i don't know that i had any to begin with,
:-)
> apart from what i indicated earlier. i begain with False,
> added a few operations for manipulating lists, then added
> the K operations. in the course of things, i kept simplifying.
It looks like a fun language.
Question: what language is it implemented in?
-Billy
stevan apter — 2006-06-23 22:02:53
>
> It looks like a fun language.
thanks - yeah, i think so.
>
> Question: what language is it implemented in?
in K (k2). i think the only primitive which would be difficult
to implement in another language (e.g. scheme or c) is @, which is K's
cross-product indexing. difficult, but not impossible. if anyone
here has the ambition to produce a c implementation, i'd be happy
to assist (read: kibbitz.)
btw, my resolve to avoid i/o in F has broken down. i've added
1 2 3 "s" 4 5 6
stops to let you examine the stack and the queue.
1 2 3 "w" 4 5 6
takes the top of the stack, formats it, writes it to stdout, then
continues on.
1 2 3 "r" 4 5 6
stops, reads from stdin, parses it, prepends it to the queue, then
continues on.
non-singleton strings are comments.
i'm satisfied that the notation makes it clear that i/o is a "sub-
language" of F.
this is all just to make debugging easier, although i can imagine
adding further i/o operators.
>
> -Billy
>
Mackenzie Straight — 2006-06-23 23:47:53
On 6/23/06, stevan apter <
sa@...> wrote:
> >
> > It looks like a fun language.
>
> thanks - yeah, i think so.
>
> >
> > Question: what language is it implemented in?
>
> in K (k2). i think the only primitive which would be difficult
> to implement in another language (e.g. scheme or c) is @, which is K's
> cross-product indexing. difficult, but not impossible. if anyone
> here has the ambition to produce a c implementation, i'd be happy
> to assist (read: kibbitz.)
There are C implementations of many K verbs (to varying degrees of
correctness, but I believe @ is fine) in
http://codealchemy.org/~eiz/darcs/ok/ok_runtime.c if anyone is
interested. In particular, ok_slice and ok_slice_item implement K's
indexing. It's too bad I don't really have time to work on it anymore.
stevan apter — 2006-06-24 00:13:38
and a guest appearance by the one and only eiz. say a
few words into the microphone eiz.
----- Original Message -----
From: "Mackenzie Straight" <eizneckam@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, June 23, 2006 7:47 PM
Subject: Re: [stack] progress in F
> On 6/23/06, stevan apter <sa@...> wrote:
> > >
> > > It looks like a fun language.
> >
> > thanks - yeah, i think so.
> >
> > >
> > > Question: what language is it implemented in?
> >
> > in K (k2). i think the only primitive which would be difficult
> > to implement in another language (e.g. scheme or c) is @, which is K's
> > cross-product indexing. difficult, but not impossible. if anyone
> > here has the ambition to produce a c implementation, i'd be happy
> > to assist (read: kibbitz.)
>
> There are C implementations of many K verbs (to varying degrees of
> correctness, but I believe @ is fine) in
> http://codealchemy.org/~eiz/darcs/ok/ok_runtime.c if anyone is
> interested. In particular, ok_slice and ok_slice_item implement K's
> indexing. It's too bad I don't really have time to work on it anymore.
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
stevan apter — 2006-06-25 17:55:26
>
> I wonder... Could you discuss some of the design choices? For example,
> you decided that "!" would be required to execute every word, thereby
> indicating that the most useful thing a word can do is to leave its
> address on the stack. Most concatenative languages assume that the
> most common thing is to execute a word, not leave an address. I think
> I can see your reasoning here -- you're not concerned about terseness
> or usability, but rather about mathematical purity. I'd like to hear
> your take on this.
>
> -Billy
here's a concrete example where the F approach comes in handy.
i was working on the 'converge' combinator this morning. 'converge'
expects a quotation q on top of the stack, and beneath that, an initial
value s. it repeatedly applies q to s until either the result matches
s or is the same twice in a row. e.g.
0 [1+5 min!]converge!
5
i.e. add 1 up to 5. the combinator sets up an initial state
[0 0]
consisting of the current result and the initial value. when
the quotation is executed, the current result is updated:
[1 0]
[2 0]
[3 0]
[4 0]
[5 0]
i wanted to write 'converge' as a recursion:
[initial-state-setup
[test]
[true]
[false converge!]
cond!] converge
the problem is when the recursion happens, the state already
exists. so i rewrote this as:
[[initial-state-setup]!
[test]
[true]
[false 2 converge drop!!]
cond!] converge
when the recursion happens, "converge" causes the program
to be placed on the stack, the first two elements of which:
[[initial-state-setup] ! ....]
are dropped, and the result
[ .... ]
is executed.
whether in general it's a good idea to write "self-modifying" code,
this application seems fine to me, and quite general. we (or at
least i) often write recursions in two parts: the entry point
sets up the initial state, and then the recursion is handled by
a second entry point.
a second thought occurred to me this morning. the way F works,
when a name is encountered, its value is retrieved and placed on
the result stack. but it would be (literally) a one character
change to the implementation to have it work like joy: instead
of placing the value on the result stack, it could be prepended
to the queue, which is exactly what ! does when it encounters a
quotation. this is the way XY works, and there is a reason i've
never liked it.
if you define
[2+] plus2
then
3 plus2
5
but suppose you want to define something you'll use as a *data
list*, e.g.
[1 2 3] v123
now, if you say
v123
1 2 3
you get three items on the stack. so you have to say
[[1 2 3]] v123
to get the *list* of 1 2 3.
obviously, joy doesn't have this problem, since it doesn't contain
assignment. in joy's definition metalanguage, you don't have to
quote the body of the program:
plus2 == 2 +
v123 == [1 2 3]
but it seems to me that any concatenative language which wants to
support assignment will have to deal with this problem (possibly
by having two types of assignment.)
sa@dfa.com — 2006-06-27 15:20:00
how would you write joy's 'stack' and 'unstack' functions in terms of
the remaining primitives?
in trying to solve this problem for F, i was led to alter behavior
which i think is pretty standard for stack languages, viz., what
happens when a function expecting n elements is applied to a stack
containing fewer than n elements.
instead of a "short stack" error, i have the function in question
behave like the identity function:
2 +
2
so now suppose that the stack is
10 20 30 40
so
[] cons!
10 20 30 [40]
cons!
10 20 [30 40]
cons!
10 [20 30 40]
cons!
[10 20 30 40]
cons!
[10 20 30 40]
the 'converge' combinator applies the quotation at the top of
the stack until the result is the same twice in a row or the
initial state reoccurs. so,
10 20 30 40 [] [cons!] converge!
[10 20 30 40]
the 'unstack' function also uses 'converge': it expects a
quotation at the top of the stack which is made the new
stack.
10 20 30 40 [50 60] unstack!
50 60
'unstack' applies 'stack' to the stack beneath the quotation,
pops it off, converges the 'uncons' program on the quotation,
then pops off the two elements on top:
10 20 30 40 [50 60][stack!pop!]dip![uncons!]converge!pop!pop!
50 60
n.b.: [] uncons -> null []. [] matches the initial state, so
'converge' terminates, and then we pop null and [].
William Tanksley, Jr — 2006-06-28 11:53:44
sa@... <
sa@...> wrote:
> how would you write joy's 'stack' and 'unstack' functions in terms of
> the remaining primitives?
[...]
> instead of a "short stack" error, i have the function in question
> behave like the identity function:
That's a great solution to implementing stack and unstack. Any
function that depends on the depth of the stack for its operation,
however, is by definition badly factored; therefore although I
recognise the need/desire to imitate Joy, I don't like those two
words, and I seriously don't like any systemic behavior that depends
on the depth of the stack.
Even though it requires you to add another primitive, I would rather
define a DEPTH word that simply returned the current depth of the
stack, so that the evil could be contained entirely within one word
rather than spread throughout the system.
-Billy (eeeeevil)
sa@dfa.com — 2006-06-28 14:31:19
concatenative@yahoogroups.com wrote on 06/28/2006 07:53:44 AM:
> sa@... <sa@...> wrote:
> > how would you write joy's 'stack' and 'unstack' functions in terms of
> > the remaining primitives?
> [...]
> > instead of a "short stack" error, i have the function in question
> > behave like the identity function:
>
> That's a great solution to implementing stack and unstack. Any
> function that depends on the depth of the stack for its operation,
> however, is by definition badly factored; therefore although I
> recognise the need/desire to imitate Joy, I don't like those two
> words, and I seriously don't like any systemic behavior that depends
> on the depth of the stack.
these words are in a class by themselves, and i'm not surprised
that you dislike them. my main reason for seeking an implementation
was not to imitate joy directly, but rather to give myself (or
rather F) the resources to define joy's recursive combinators.
wherever a combinator must save the stack, do something, and
then restore the stack, the "something" has to be framed by
operations involving 'stack' and 'unstack'. at least, so it
seems to me.
>
> Even though it requires you to add another primitive, I would rather
> define a DEPTH word that simply returned the current depth of the
> stack, so that the evil could be contained entirely within one word
> rather than spread throughout the system.
we're talking about two kinds of evil: a primtive (DEPTH) which
contaminates every definition which uses it, and the handling of
an edge-condition in the processing of the stack. i'm not
convinced that the latter actually is evil. i'd like to see
a principled argument for that conclusion. (there's already
a practical one: it makes debugging more arduous.)
>
> -Billy (eeeeevil)
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-29 00:30:44
sa@... <
sa@...> wrote:
> > That's a great solution to implementing stack and unstack. Any
> > function that depends on the depth of the stack for its operation,
> > however, is by definition badly factored; therefore although I
> > recognise the need/desire to imitate Joy, I don't like those two
> > words, and I seriously don't like any systemic behavior that depends
> > on the depth of the stack.
> these words are in a class by themselves, and i'm not surprised
> that you dislike them. my main reason for seeking an implementation
> was not to imitate joy directly, but rather to give myself (or
> rather F) the resources to define joy's recursive combinators.
> wherever a combinator must save the stack, do something, and
> then restore the stack, the "something" has to be framed by
> operations involving 'stack' and 'unstack'. at least, so it
> seems to me.
No, you're totally right. This is why I also don't like Joy's habit of
saving and restoring the entire stack. I would rather define things
such that no full-stack saving and restoring is needed; most other
pre-Joy concatenative languages work that way, so there's no doubt it
can be done. (Of course, you're proving that you can do the same
things as Joy, so I accept that you must perform full-stack saving and
restoring.)
> > Even though it requires you to add another primitive, I would rather
> > define a DEPTH word that simply returned the current depth of the
> > stack, so that the evil could be contained entirely within one word
> > rather than spread throughout the system.
> we're talking about two kinds of evil: a primtive (DEPTH) which
> contaminates every definition which uses it, and the handling of
> an edge-condition in the processing of the stack. i'm not
> convinced that the latter actually is evil. i'd like to see
> a principled argument for that conclusion. (there's already
> a practical one: it makes debugging more arduous.)
The primitive named 'DEPTH' can be searched for using any text
utility. The edge condition cannot be determined to be absent except
by whole-program semantic analysis (and sometimes that isn't
possible); you can't even show that it's present without luck that
enables you to execute exactly the right conditions to run across it
AND notice the effects. Which one would you like to think about when
developing a 1 million lines of code system?
I would rather have the edge condition return an immediate error. The
sooner the better.
And I'm not even talking about static typechecking here. I will say
that if you've got static typechecking this isn't a problem -- you can
make that edge condition behave anyhow you'd like, because the
programmer can control within the word whether the edge condition will
apply.
-Billy
stevan apter — 2006-06-29 11:20:34
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, June 28, 2006 8:30 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> sa@... <sa@...> wrote:
> > > That's a great solution to implementing stack and unstack. Any
> > > function that depends on the depth of the stack for its operation,
> > > however, is by definition badly factored; therefore although I
> > > recognise the need/desire to imitate Joy, I don't like those two
> > > words, and I seriously don't like any systemic behavior that depends
> > > on the depth of the stack.
>
> > these words are in a class by themselves, and i'm not surprised
> > that you dislike them. my main reason for seeking an implementation
> > was not to imitate joy directly, but rather to give myself (or
> > rather F) the resources to define joy's recursive combinators.
> > wherever a combinator must save the stack, do something, and
> > then restore the stack, the "something" has to be framed by
> > operations involving 'stack' and 'unstack'. at least, so it
> > seems to me.
>
> No, you're totally right. This is why I also don't like Joy's habit of
> saving and restoring the entire stack. I would rather define things
> such that no full-stack saving and restoring is needed; most other
> pre-Joy concatenative languages work that way, so there's no doubt it
> can be done. (Of course, you're proving that you can do the same
> things as Joy, so I accept that you must perform full-stack saving and
> restoring.)
forth and factor, to take two examples, have >r and r> (have i got
their names right?), and possibly something like DEPTH as well, isn't
that so? i think if you have those at your disposal, you have enough
to define e.g. 'linrec'.
i think we've discussed this in the past: in joy, you can have
something like
X [1 2 3][+]map
which evaluates
X 1 +
X 2 +
X 3 +
and leaves
X [x y z]
on the stack. how would you implement this behavior without some
mechanism for saving and restoring the stack before and after each
application of +?
>
> > > Even though it requires you to add another primitive, I would rather
> > > define a DEPTH word that simply returned the current depth of the
> > > stack, so that the evil could be contained entirely within one word
> > > rather than spread throughout the system.
>
> > we're talking about two kinds of evil: a primtive (DEPTH) which
> > contaminates every definition which uses it, and the handling of
> > an edge-condition in the processing of the stack. i'm not
> > convinced that the latter actually is evil. i'd like to see
> > a principled argument for that conclusion. (there's already
> > a practical one: it makes debugging more arduous.)
>
> The primitive named 'DEPTH' can be searched for using any text
> utility. The edge condition cannot be determined to be absent except
> by whole-program semantic analysis (and sometimes that isn't
> possible); you can't even show that it's present without luck that
> enables you to execute exactly the right conditions to run across it
> AND notice the effects. Which one would you like to think about when
> developing a 1 million lines of code system?
>
> I would rather have the edge condition return an immediate error. The
> sooner the better.
>
> And I'm not even talking about static typechecking here. I will say
> that if you've got static typechecking this isn't a problem -- you can
> make that edge condition behave anyhow you'd like, because the
> programmer can control within the word whether the edge condition will
> apply.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
Christopher Diggins — 2006-06-29 16:40:28
> > That's a great solution to implementing stack and unstack. Any
> > function that depends on the depth of the stack for its operation,
> > however, is by definition badly factored; therefore although I
> > recognise the need/desire to imitate Joy, I don't like those two
> > words, and I seriously don't like any systemic behavior that depends
> > on the depth of the stack.
I have a similar issue in Cat. A function which only looks at the top two
items of a stack, behaves effectively like a pure binary function in the
average functional language. However, if we introduce any primitives in its
definition which manipulate or even observe the stack as a whole, it becomes
more akin to a procedure in an imperative language with a side-effect.
The solution I am leaning towards is to label functions with no side-effects
as being "clean", while functions which examine the entire stack are
"dirty". This is my attempt to resolve the differences between the idea of
pure functional programming and imperative programming.
Some discussion of this approach and alternatives can be found at
http://www.artima.com/forums/flat.jsp?forum=106&thread=166178&start=0&msRange=15
[Non-text portions of this message have been removed]
sa@dfa.com — 2006-06-29 17:46:24
my implementation of 'stack' doesn't "observe the stack as a whole".
there's no primitive in F which can do that. what 'stack' does
is, first, push [] onto the stack, and then repeatedly apply
'cons' (which is a primitive) until the stack is empty, at which
point the operation terminates.
nor does 'stack' depend on the depth of the stack. in fact, i
share billy's suspicion of any function which does.
slava had what i thought might be a good objection (to treating
stack underflow as application of the identity function):
consider the 'swap' primitive:
2 3 \
3 2
you can define something similar (in F):
[pair!_unpair!] swap
i.e. make a pair of the top two elements on the stack, reverse
it, put the elements back on the stack. but
2 \
2
swap!
2 0
it doesn't really matter why 'swap' does this. in general it
will be true that compound words which attempt to emulate
primitives will behave differently from those primitives
when applied to a short stack.
i think it is a good objection, but not a fatal one. it
would be fatal only if one required that compound words
behaved like primitives in all ways, which i do not.
concatenative@yahoogroups.com wrote on 06/29/2006 12:40:28 PM:
> > > That's a great solution to implementing stack and unstack. Any
> > > function that depends on the depth of the stack for its operation,
> > > however, is by definition badly factored; therefore although I
> > > recognise the need/desire to imitate Joy, I don't like those two
> > > words, and I seriously don't like any systemic behavior that depends
> > > on the depth of the stack.
> I have a similar issue in Cat. A function which only looks at the top two
> items of a stack, behaves effectively like a pure binary function in the
> average functional language. However, if we introduce any primitives in
its
> definition which manipulate or even observe the stack as a whole, it
becomes
> more akin to a procedure in an imperative language with a side-effect.
>
> The solution I am leaning towards is to label functions with no
side-effects
> as being "clean", while functions which examine the entire stack are
> "dirty". This is my attempt to resolve the differences between the idea
of
> pure functional programming and imperative programming.
>
> Some discussion of this approach and alternatives can be found at
>
http://www.artima.com/forums/flat.jsp?forum=106&thread=166178&start=0&msRange=15
>
>
> [Non-text portions of this message have been removed]
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
Christopher Diggins — 2006-06-29 21:52:02
> my implementation of 'stack' doesn't "observe the stack as a whole".
> there's no primitive in F which can do that. what 'stack' does
> is, first, push [] onto the stack, and then repeatedly apply
> 'cons' (which is a primitive) until the stack is empty, at which
> point the operation terminates.
I said "... if we introduce any primitives in its definition which
manipulate or even observe the stack ...".
Obviously what you just described not only observes the entire stack, it
manipulates it!
[Non-text portions of this message have been removed]
stevan apter — 2006-06-29 22:37:58
----- Original Message -----
From: "Christopher Diggins" <cdiggins@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, June 29, 2006 5:52 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> > my implementation of 'stack' doesn't "observe the stack as a whole".
> > there's no primitive in F which can do that. what 'stack' does
> > is, first, push [] onto the stack, and then repeatedly apply
> > 'cons' (which is a primitive) until the stack is empty, at which
> > point the operation terminates.
>
> I said "... if we introduce any primitives in its definition which
> manipulate or even observe the stack ...".
>
> Obviously what you just described not only observes the entire stack, it
> manipulates it!
this is (or could become) a dispute over vocabulary.
the primitive + has valence 2 and charge 1. by that i mean
that it consumes 2 elements from the stack and leaves 1. 'dup'
has valence 1 and charge 2. and so forth.
now, what is valence of 'stack', and what is the charge of
'unstack'. i think it makes sense to say that the valence
of 'stack' is infinite (or variable), and the charge of 'unstack'
is infinite (or variable). (the charge of 'stack' is 1: if
there are n elements on the input stack, there will be n+1
elements on the output stack. the valence of 'unstack' is 1.)
what i meant when i said that no F primitive "observes the
stack as a whole" i meant that no F primitive has infinite
(or variable) valence.
the 'stack' *combinator* has infinite valence, but it's
not a primitive. indeed, that was the problem: how to
define such a combinator given that all primitives have
fixed, finite valence. (and ditto for 'unstack' and
charge.)
>
>
> [Non-text portions of this message have been removed]
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
John Cowan — 2006-06-29 22:20:44
Christopher Diggins scripsit:
> I have a similar issue in Cat. A function which only looks at the top two
> items of a stack, behaves effectively like a pure binary function in the
> average functional language. However, if we introduce any primitives in its
> definition which manipulate or even observe the stack as a whole, it becomes
> more akin to a procedure in an imperative language with a side-effect.
How so? All Joy words are functions from a stack to a stack, with the
exception of those which do file operations.
> The solution I am leaning towards is to label functions with no side-effects
> as being "clean", while functions which examine the entire stack are
> "dirty". This is my attempt to resolve the differences between the idea of
> pure functional programming and imperative programming.
What's the difference between looking at one, or two, or three, or ..., and looking
at all of them? It seems completely arbitrary to me.
--
So that's the tune they play on John Cowan
their fascist banjos, is it?
cowan@...
--Great-Souled Sam
http://www.ccil.org/~cowan
Martin Young — 2006-06-29 23:25:21
Hi Stevan,
On Thu, 2006-06-29 at 18:37 -0400, stevan apter wrote:
> what i meant when i said that no F primitive "observes the
> stack as a whole" i meant that no F primitive has infinite
> (or variable) valence.
>
> the 'stack' *combinator* has infinite valence, but it's
> not a primitive. indeed, that was the problem: how to
> define such a combinator given that all primitives have
> fixed, finite valence. (and ditto for 'unstack' and
> charge.)
Could you explain why it's important to you that primitives have fixed
finite valence and charge yet it's not important for combinators?
The only reason I can think of is that fixed valence and charge help
when performing automatic analysis and optimisation. However, a
combinator with variable valence or charge would be just as much an
effective block to static analysis as such a primitive.
Put pragmatically you can't statically unroll a loop with an unbound
number or iterations regardless of whether you can decompose the code
itself into fixed valence primitives.
Regards,
Martin.
Christopher Diggins — 2006-06-29 23:57:07
> What's the difference between looking at one, or two, or three, or ...,
and looking
at all of them? It seems completely arbitrary to me.
I find it useful to think about functions in a concatenative language as
both producers and consumers of elements on the top of the stack. You can
then define the type of a function as the number and type of the stack
elements that it consumes and the elements that it produces.
This makes it easier to define a mapping from an arbitrary functional or
imperative language to a concatenative language, which is why I am
developing Cat: as a backend to the Heron langauge, and potentially other
languages.
This also is useful for constructing a type-system for a concatenative
language.
Consider how the defintion of a function might be better described if we had
a type-system for describing the arguments and results of functions.
[Non-text portions of this message have been removed]
stevan apter — 2006-06-30 03:20:21
hi martin
in fact, all the primitives of F have fixed finite valence,
but the two primitive combinators ! (i) and ` (dip) have variable
charge. a program, all the atoms of which have fixed valence,
will have fixed valence. as you say, the main use for these
concepts is in the area of automatic analysis and optimization.
i invoked these concepts in order to explain my decision to
replace 'stack underflow error' with a different, non-error
behavior. i still think it's remarkable that 'stack' and
'unstack' (whatever you may think of them) depend on this
behavior, and that replicating the behavior of certain joy
combinators (whatever you think of them) appears to require
these programs.
for example, if you define 'map' so that the quotation which
is mapped to items of a list doesn't "reach beyond" those
items to the stack below, then you can define it in F this
way:
[[$count!]`[pair![]\!]`\
[':`$[\'!`]`pair![swons!]`!]
do!%%_] map
for example,
10 20 30 [[1 2 3][4 5 6][7 8 9]][!+*] map!
10 20 30 [5 44 119]
but suppose you want to have:
10 20 30 [[2 3][4 5 6][9]][!+*] Map!
10 20 30 [150 44 780]
that is, the first application of [!+*] sees 30 2 3, the
second sees 4 5 6, the third sees 20 30 9.
for this, you need 'stack':
[[[stack!]`]`
[[unit!]map!',eachright!]`
',eachleft![unit!.last!]map!] Map
i'm still not an expert F-er, so probably both programs
could be tightened up, but i think my general claim still
stands.
btw, in the joy dialect of F, 'map' is:
[[dup count] dip [pair [] swap i] dip swap [quote uncons dip dup
[swap quote i dip] dip pair quote swons dip i] do pop pop rev] map
----- Original Message -----
From: "Martin Young" <martin@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, June 29, 2006 7:25 PM
Subject: [stack] Re: 'stack' and 'unstack' in F
> Hi Stevan,
>
> On Thu, 2006-06-29 at 18:37 -0400, stevan apter wrote:
> > what i meant when i said that no F primitive "observes the
> > stack as a whole" i meant that no F primitive has infinite
> > (or variable) valence.
> >
> > the 'stack' *combinator* has infinite valence, but it's
> > not a primitive. indeed, that was the problem: how to
> > define such a combinator given that all primitives have
> > fixed, finite valence. (and ditto for 'unstack' and
> > charge.)
>
> Could you explain why it's important to you that primitives have fixed
> finite valence and charge yet it's not important for combinators?
>
> The only reason I can think of is that fixed valence and charge help
> when performing automatic analysis and optimisation. However, a
> combinator with variable valence or charge would be just as much an
> effective block to static analysis as such a primitive.
>
> Put pragmatically you can't statically unroll a loop with an unbound
> number or iterations regardless of whether you can decompose the code
> itself into fixed valence primitives.
>
> Regards,
> Martin.
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
stevan apter — 2006-06-30 03:22:26
how many elements, and of what types, does cat's equivalent
of 'i' produce? in my lingo, does cat have combinators of
variable charge?
----- Original Message -----
From: "Christopher Diggins" <cdiggins@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, June 29, 2006 7:57 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> > What's the difference between looking at one, or two, or three, or ...,
> and looking
> at all of them? It seems completely arbitrary to me.
>
> I find it useful to think about functions in a concatenative language as
> both producers and consumers of elements on the top of the stack. You can
> then define the type of a function as the number and type of the stack
> elements that it consumes and the elements that it produces.
>
> This makes it easier to define a mapping from an arbitrary functional or
> imperative language to a concatenative language, which is why I am
> developing Cat: as a backend to the Heron langauge, and potentially other
> languages.
>
> This also is useful for constructing a type-system for a concatenative
> language.
>
> Consider how the defintion of a function might be better described if we had
> a type-system for describing the arguments and results of functions.
>
>
> [Non-text portions of this message have been removed]
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-30 13:43:07
stevan apter <
sa@...> wrote:
> what i meant when i said that no F primitive "observes the
> stack as a whole" i meant that no F primitive has infinite
> (or variable) valence.
If you accept your proposed rule (that operating on a stack without
enough values is a valid no-op), every primitive that takes any
arguments has variable valence. Am I missing something?
> the 'stack' *combinator* has infinite valence, but it's
> not a primitive. indeed, that was the problem: how to
> define such a combinator given that all primitives have
> fixed, finite valence. (and ditto for 'unstack' and
> charge.)
The primitives may appear to have fixed valence, but they don't -- the
recursion and conditional constructs (or loop construct) make the
valence variable. So just iterate over the stack.
-Billy
William Tanksley, Jr — 2006-06-30 13:54:16
stevan apter <
sa@...> wrote:
> how many elements, and of what types, does cat's equivalent
> of 'i' produce? in my lingo, does cat have combinators of
> variable charge?
By the way, I can't answer for cat, but strongForth has NO words with
variable valence or charge. All words produce a static stack effect,
even the conditionals and EXECUTE (which is equivalent to 'i').
Actually, the word EXECUTE doesn't exist; instead it's replaced by
EXECUTE(. The open parenthesis indicates that it's a parsing word; it
consumes source code to determine the stack effect of the quotation
it's allowed to execute. Quotations are also staticly typechecked, so
it's impossible to compile a program that isn't typesafe in this
sense.
Here's a crude example using Joylike syntax together with
strongForth's type notation:
[( -- int) 3 4 +] execute( -- int)
strongForth lacks some important features which would make it more
generally useful. The most important of these is array operations on
dynamicly resizable arrays.
-Billy
William Tanksley, Jr — 2006-06-30 14:04:53
stevan apter <
sa@...> wrote:
> i invoked these concepts in order to explain my decision to
> replace 'stack underflow error' with a different, non-error
> behavior. i still think it's remarkable that 'stack' and
> 'unstack' (whatever you may think of them) depend on this
> behavior, and that replicating the behavior of certain joy
> combinators (whatever you think of them) appears to require
> these programs.
This may be faulty logic. It's true that Joy combinators require those
programs, and so if you're precisely imitating Joy you need stack and
unstack; but it's not true that stack or unstack REQUIRE the behavior
we're discussing. There are many alternates -- for example, a
conditional version of ! or converge that will act the way you're
describing, or a primitive that returns the current stack depth.
The problem with your suggestion is that it's a whole-language change;
it can be used anywhere invisibly, and in fact is easy to use
accidentally. In fact, it's way easier to use accidentally than it is
to use on purpose, except for the single purpose you propose
(consuming the entire stack).
-Billy
sa@dfa.com — 2006-06-30 15:52:15
concatenative@yahoogroups.com wrote on 06/30/2006 09:43:07 AM:
> stevan apter <sa@...> wrote:
> > what i meant when i said that no F primitive "observes the
> > stack as a whole" i meant that no F primitive has infinite
> > (or variable) valence.
>
> If you accept your proposed rule (that operating on a stack without
> enough values is a valid no-op), every primitive that takes any
> arguments has variable valence. Am I missing something?
in one sense, i guess so: a primitive has valence n when there
are at least n items on the stack, else it has valence 0/charge 0.
alternatively, you could say that every primitive has valence n,
but that "+" (any primitive) is the identity function when there
are fewer than n items on the stack.
>
> > the 'stack' *combinator* has infinite valence, but it's
> > not a primitive. indeed, that was the problem: how to
> > define such a combinator given that all primitives have
> > fixed, finite valence. (and ditto for 'unstack' and
> > charge.)
>
> The primitives may appear to have fixed valence, but they don't -- the
> recursion and conditional constructs (or loop construct) make the
> valence variable. So just iterate over the stack.
? i don't understand this. there are no recursion or conditional
or looping primitives in F. can you perhaps expand on this?
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
sa@dfa.com — 2006-06-30 16:31:54
concatenative@yahoogroups.com wrote on 06/30/2006 10:04:53 AM:
> stevan apter <sa@...> wrote:
> > i invoked these concepts in order to explain my decision to
> > replace 'stack underflow error' with a different, non-error
> > behavior. i still think it's remarkable that 'stack' and
> > 'unstack' (whatever you may think of them) depend on this
> > behavior, and that replicating the behavior of certain joy
> > combinators (whatever you think of them) appears to require
> > these programs.
>
> This may be faulty logic. It's true that Joy combinators require those
> programs, and so if you're precisely imitating Joy you need stack and
> unstack; but it's not true that stack or unstack REQUIRE the behavior
> we're discussing. There are many alternates -- for example, a
> conditional version of ! or converge that will act the way you're
> describing, or a primitive that returns the current stack depth.
well, what i actually said was that 'stack' could be defined with
my method, but absent DEPTH or some equivalent primitive of variable
valence, it couldn't.
>
> The problem with your suggestion is that it's a whole-language change;
> it can be used anywhere invisibly, and in fact is easy to use
> accidentally. In fact, it's way easier to use accidentally than it is
> to use on purpose, except for the single purpose you propose
> (consuming the entire stack).
actually, i rely on the behavior for 'unstack' as well, but
otherwise what you say is probably right. and i'm not sure
it doesn't have other applications.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-30 17:49:15
sa@... <
sa@...> wrote:
> > If you accept your proposed rule (that operating on a stack without
> > enough values is a valid no-op), every primitive that takes any
> > arguments has variable valence. Am I missing something?
> in one sense, i guess so: a primitive has valence n when there
> are at least n items on the stack, else it has valence 0/charge 0.
> alternatively, you could say that every primitive has valence n,
> but that "+" (any primitive) is the identity function when there
> are fewer than n items on the stack.
So what am I missing? It looks like you're agreeing with me that every
primitive in your proposed system has variable valence (and charge).
Your "alternatively" phrase is a bit confusing -- are you trying to
claim that because a function's valence is constant, a primitive that
implements two different functions therefore has a constant valence?
> > > the 'stack' *combinator* has infinite valence, but it's
> > > not a primitive. indeed, that was the problem: how to
> > > define such a combinator given that all primitives have
> > > fixed, finite valence. (and ditto for 'unstack' and
> > > charge.)
> > The primitives may appear to have fixed valence, but they don't -- the
> > recursion and conditional constructs (or loop construct) make the
> > valence variable. So just iterate over the stack.
> ? i don't understand this. there are no recursion or conditional
> or looping primitives in F. can you perhaps expand on this?
Isn't 'converge' a looping primitive? Its valence is certainly variable.
-Billy
sa@dfa.com — 2006-06-30 18:06:36
concatenative@yahoogroups.com wrote on 06/30/2006 01:49:15 PM:
> sa@... <sa@...> wrote:
> > > If you accept your proposed rule (that operating on a stack without
> > > enough values is a valid no-op), every primitive that takes any
> > > arguments has variable valence. Am I missing something?
>
> > in one sense, i guess so: a primitive has valence n when there
> > are at least n items on the stack, else it has valence 0/charge 0.
> > alternatively, you could say that every primitive has valence n,
> > but that "+" (any primitive) is the identity function when there
> > are fewer than n items on the stack.
>
> So what am I missing? It looks like you're agreeing with me that every
> primitive in your proposed system has variable valence (and charge).
> Your "alternatively" phrase is a bit confusing -- are you trying to
> claim that because a function's valence is constant, a primitive that
> implements two different functions therefore has a constant valence?
yeah, that's what i was trying to do, but i guess i didn't
get away with it. :)
seriously though, i think i can claim that F has 30 primitives,
29 of which are associated with symbols, and one of which --
the identity function -- has no symbol; and that a symbol
denotes the function with which it is associated unless the
stack is short, in which case it denotes the identity function.
>
> > > > the 'stack' *combinator* has infinite valence, but it's
> > > > not a primitive. indeed, that was the problem: how to
> > > > define such a combinator given that all primitives have
> > > > fixed, finite valence. (and ditto for 'unstack' and
> > > > charge.)
>
> > > The primitives may appear to have fixed valence, but they don't --
the
> > > recursion and conditional constructs (or loop construct) make the
> > > valence variable. So just iterate over the stack.
>
> > ? i don't understand this. there are no recursion or conditional
> > or looping primitives in F. can you perhaps expand on this?
>
> Isn't 'converge' a looping primitive? Its valence is certainly variable.
'converge' isn't a primitive. here's its definition (in the Joy dialect):
[Converge last]
and here is 'Converge':
[[dupd dupd quote pair dip swapd] i [[bot quote i dip swap dup] dip
pair [pair dup unpair swap in] dip swap] [pop first rev 1 swap drop]
[[rev unpair cons] dip unpair 2 [Converge []] dot drop i] cond]
really, there aren't any recursive or looping primitives in F. just
'i' and 'dip'.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-30 18:23:48
sa@... <
sa@...> wrote:
> > > i invoked these concepts in order to explain my decision to
> > > replace 'stack underflow error' with a different, non-error
> > > behavior. i still think it's remarkable that 'stack' and
> > > 'unstack' (whatever you may think of them) depend on this
> > > behavior, and that replicating the behavior of certain joy
> > > combinators (whatever you think of them) appears to require
> > > these programs.
> >
> > This may be faulty logic. It's true that Joy combinators require those
> > programs, and so if you're precisely imitating Joy you need stack and
> > unstack; but it's not true that stack or unstack REQUIRE the behavior
> > we're discussing. There are many alternates -- for example, a
> > conditional version of ! or converge that will act the way you're
> > describing, or a primitive that returns the current stack depth.
> well, what i actually said was that 'stack' could be defined with
> my method, but absent DEPTH or some equivalent primitive of variable
> valence, it couldn't.
That statement is neither useful nor true. (No offense meant, just
good clean fun.)
I'll prove by counterexample that it's untrue: I can define a language
in which 'stack' could be defined without any variable valence
primitives -- not even a variable loop. This hypothetical language has
a stack that's a constant depth (probably a circular buffer), so
saving it to an array requires a constant number of operations. This
is an extreme counterexample, and I suspect that some gentler one
probably exists -- but at the same time, note that one concatenative
language actually works this way (Chuck Moore's machine forth and
colorforth).
The reason I said that your statement wasn't useful is that you said
"stack can be defined with my method" (which is true), and then "stack
can not be defined without primitives of variable valence" (since your
solution requires all primitives to have variable valence, it also
excludes your method). So therefore even if we assume that the second
statement is true, it doesn't say anything about my solution that it
doesn't also say about yours.
I just thought of a gentler counterexample: a primitive named 'empty?'
could be used to implement 'stack'. It returns true when the stack is
empty, false otherwise. Its valence is undetectably close to zero,
because it doesn't actually consume anything; its charge is a constant
1. (It's not as good of a counterexample as my previous one, because
it may be argued that its valence is 1 when the stack's full and 0
when the stack's empty -- but that would be a pretty subtle argument.)
> > The problem with your suggestion is that it's a whole-language change;
> > it can be used anywhere invisibly, and in fact is easy to use
> > accidentally. In fact, it's way easier to use accidentally than it is
> > to use on purpose, except for the single purpose you propose
> > (consuming the entire stack).
> actually, i rely on the behavior for 'unstack' as well, but
> otherwise what you say is probably right. and i'm not sure
> it doesn't have other applications.
You're right: one possible application would be using your behavior to
define DEPTH :-). My point was just that misusing it is very easy and
invisible (you can't test a program by running it at the command line,
because it might behave differently 'in vivo'), and using it correctly
is hard for any job that doesn't naturally start with "first, consume
the entire stack". In fact, every time you deliberately use it, you
must start by first consuming the entire stack (and then possibly put
some of it back).
-Billy
William Tanksley, Jr — 2006-06-30 18:51:16
sa@... <
sa@...> wrote:
> > sa@... <sa@...> wrote:
> > > > If you accept your proposed rule (that operating on a stack without
> > > > enough values is a valid no-op), every primitive that takes any
> > > > arguments has variable valence. Am I missing something?
> > > in one sense, i guess so: a primitive has valence n when there
> > > are at least n items on the stack, else it has valence 0/charge 0.
> > > alternatively, you could say that every primitive has valence n,
> > > but that "+" (any primitive) is the identity function when there
> > > are fewer than n items on the stack.
> > So what am I missing? It looks like you're agreeing with me that every
> > primitive in your proposed system has variable valence (and charge).
> > Your "alternatively" phrase is a bit confusing -- are you trying to
> > claim that because a function's valence is constant, a primitive that
> > implements two different functions therefore has a constant valence?
> yeah, that's what i was trying to do, but i guess i didn't
> get away with it. :)
Yup, you're a sneaky guy, always trying to get away with things :-).
Good thing I'm here to keep an eye on you.
> seriously though, i think i can claim that F has 30 primitives,
> 29 of which are associated with symbols, and one of which --
> the identity function -- has no symbol; and that a symbol
> denotes the function with which it is associated unless the
> stack is short, in which case it denotes the identity function.
So when you used the word 'function' earlier, you actually meant
'primitive', and when you used 'primitive' you meant 'predefined
symbol'. I don't have any problem with that claim, but it doesn't seem
to add anything to the discussion -- it seems like a mere search and
replace, with no change to the logic or conclusions.
In either case, the programs users type in will have to deal with
variable valence whether they want to or not. A language using DEPTH
will only have to deal with it only when it actually appears in the
text.
> > > > > the 'stack' *combinator* has infinite valence, but it's
> > > > > not a primitive. indeed, that was the problem: how to
> > > > > define such a combinator given that all primitives have
> > > > > fixed, finite valence. (and ditto for 'unstack' and
> > > > > charge.)
> > > > The primitives may appear to have fixed valence, but they don't --
> > > > the recursion and conditional constructs (or loop construct) make
> > > > the valence variable. So just iterate over the stack.
> > > ? i don't understand this. there are no recursion or conditional
> > > or looping primitives in F. can you perhaps expand on this?
> > Isn't 'converge' a looping primitive? Its valence is certainly variable.
> 'converge' isn't a primitive. here's its definition (in the Joy dialect):
My mistake. Okay, then "!" makes the valence as variable as you want
it to be, because its valence is variable and includes the possiblity
of executing itself. Same thing, really.
> really, there aren't any recursive or looping primitives in F. just
> 'i' and 'dip'.
Nice :-). I like it.
-Billy
stevan apter — 2006-06-30 19:49:59
>
> > really, there aren't any recursive or looping primitives in F. just
> > 'i' and 'dip'.
>
> Nice :-). I like it.
>
i'm mulling your earlier comments, but i always have time to
respond to a compliment. :)
actually, all we need is 'dip', since 'i' is just [] swap dip. but
i wanted to keep ! for consistency with False, and to make the distinction
between F and Joy semantics clean.
stevan apter — 2006-06-30 20:29:06
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, June 30, 2006 2:51 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> sa@... <sa@...> wrote:
> > > sa@... <sa@...> wrote:
> > > > > If you accept your proposed rule (that operating on a stack without
> > > > > enough values is a valid no-op), every primitive that takes any
> > > > > arguments has variable valence. Am I missing something?
> > > > in one sense, i guess so: a primitive has valence n when there
> > > > are at least n items on the stack, else it has valence 0/charge 0.
> > > > alternatively, you could say that every primitive has valence n,
> > > > but that "+" (any primitive) is the identity function when there
> > > > are fewer than n items on the stack.
>
> > > So what am I missing? It looks like you're agreeing with me that every
> > > primitive in your proposed system has variable valence (and charge).
> > > Your "alternatively" phrase is a bit confusing -- are you trying to
> > > claim that because a function's valence is constant, a primitive that
> > > implements two different functions therefore has a constant valence?
>
> > yeah, that's what i was trying to do, but i guess i didn't
> > get away with it. :)
>
> Yup, you're a sneaky guy, always trying to get away with things :-).
> Good thing I'm here to keep an eye on you.
that is reassuring.
>
> > seriously though, i think i can claim that F has 30 primitives,
> > 29 of which are associated with symbols, and one of which --
> > the identity function -- has no symbol; and that a symbol
> > denotes the function with which it is associated unless the
> > stack is short, in which case it denotes the identity function.
>
> So when you used the word 'function' earlier, you actually meant
> 'primitive', and when you used 'primitive' you meant 'predefined
> symbol'. I don't have any problem with that claim, but it doesn't seem
> to add anything to the discussion -- it seems like a mere search and
> replace, with no change to the logic or conclusions.
yes, i haven't been as precise as i should have been. F has functions,
but every one of them is a primitive, and vice-versa, and every
primitive lives on a symbol (i.e. not a digit or a character or
a square bracket or a blank), and every symbol is a primitive.
>
> In either case, the programs users type in will have to deal with
> variable valence whether they want to or not. A language using DEPTH
> will only have to deal with it only when it actually appears in the
> text.
i also regret introducing both the terms 'variable' and 'infinite',
and then muddling them. as i understand it, a function has variable
valence if it can take one or two or three or .. arguments; and a
function has infinite valence if it takes the entire stack as a
single argument. DEPTH has infinite valence. variable-valence
functions are, i think, sometimes called "multigrade functions,"
and i can't imagine why one would ever want them in a concatenative
language.
i just wanted to avoid having any functions which could see the
entire stack as a single object.
stevan apter — 2006-06-30 20:35:13
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, June 30, 2006 2:23 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> sa@... <sa@...> wrote:
> > > > i invoked these concepts in order to explain my decision to
> > > > replace 'stack underflow error' with a different, non-error
> > > > behavior. i still think it's remarkable that 'stack' and
> > > > 'unstack' (whatever you may think of them) depend on this
> > > > behavior, and that replicating the behavior of certain joy
> > > > combinators (whatever you think of them) appears to require
> > > > these programs.
> > >
> > > This may be faulty logic. It's true that Joy combinators require those
> > > programs, and so if you're precisely imitating Joy you need stack and
> > > unstack; but it's not true that stack or unstack REQUIRE the behavior
> > > we're discussing. There are many alternates -- for example, a
> > > conditional version of ! or converge that will act the way you're
> > > describing, or a primitive that returns the current stack depth.
>
> > well, what i actually said was that 'stack' could be defined with
> > my method, but absent DEPTH or some equivalent primitive of variable
> > valence, it couldn't.
>
> That statement is neither useful nor true. (No offense meant, just
> good clean fun.)
>
> I'll prove by counterexample that it's untrue: I can define a language
> in which 'stack' could be defined without any variable valence
> primitives -- not even a variable loop. This hypothetical language has
> a stack that's a constant depth (probably a circular buffer), so
> saving it to an array requires a constant number of operations. This
> is an extreme counterexample, and I suspect that some gentler one
> probably exists -- but at the same time, note that one concatenative
> language actually works this way (Chuck Moore's machine forth and
> colorforth).
wow - a circular stack - a stircle.
>
> The reason I said that your statement wasn't useful is that you said
> "stack can be defined with my method" (which is true), and then "stack
> can not be defined without primitives of variable valence" (since your
> solution requires all primitives to have variable valence, it also
> excludes your method). So therefore even if we assume that the second
> statement is true, it doesn't say anything about my solution that it
> doesn't also say about yours.
>
> I just thought of a gentler counterexample: a primitive named 'empty?'
> could be used to implement 'stack'. It returns true when the stack is
> empty, false otherwise. Its valence is undetectably close to zero,
> because it doesn't actually consume anything; its charge is a constant
> 1. (It's not as good of a counterexample as my previous one, because
> it may be argued that its valence is 1 when the stack's full and 0
> when the stack's empty -- but that would be a pretty subtle argument.)
'empty?' takes the entire stack as an argument, returns 1 if it's
empty, else 0. so in my lingo, it has infinite valence.
>
> > > The problem with your suggestion is that it's a whole-language change;
> > > it can be used anywhere invisibly, and in fact is easy to use
> > > accidentally. In fact, it's way easier to use accidentally than it is
> > > to use on purpose, except for the single purpose you propose
> > > (consuming the entire stack).
>
> > actually, i rely on the behavior for 'unstack' as well, but
> > otherwise what you say is probably right. and i'm not sure
> > it doesn't have other applications.
>
> You're right: one possible application would be using your behavior to
> define DEPTH :-). My point was just that misusing it is very easy and
> invisible (you can't test a program by running it at the command line,
> because it might behave differently 'in vivo'), and using it correctly
> is hard for any job that doesn't naturally start with "first, consume
> the entire stack". In fact, every time you deliberately use it, you
> must start by first consuming the entire stack (and then possibly put
> some of it back).
well, the same could be said of many of joy's combinators. i
just don't see this as a compelling argument.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-06-30 20:57:43
stevan apter <
sa@...> wrote:
> i'm mulling your earlier comments, but i always have time to
> respond to a compliment. :)
Grin.
> actually, all we need is 'dip', since 'i' is just [] swap dip. but
> i wanted to keep ! for consistency with False, and to make the distinction
> between F and Joy semantics clean.
IMO you did the right thing. I like the result.
-Billy
William Tanksley, Jr — 2006-06-30 21:19:21
stevan apter <
sa@...> wrote:
> > I'll prove by counterexample that it's untrue: I can define a language
> > in which 'stack' could be defined without any variable valence
> > primitives -- not even a variable loop. This hypothetical language has
> > a stack that's a constant depth (probably a circular buffer), so
> > saving it to an array requires a constant number of operations. This
> > is an extreme counterexample, and I suspect that some gentler one
> > probably exists -- but at the same time, note that one concatenative
> > language actually works this way (Chuck Moore's machine forth and
> > colorforth).
> wow - a circular stack - a stircle.
Heh, yup. No suprise that Chuck would have used one -- engineers are
always using circular buffers. (schtuffers?)
> > I just thought of a gentler counterexample: a primitive named 'empty?'
> > could be used to implement 'stack'. It returns true when the stack is
> > empty, false otherwise. Its valence is undetectably close to zero,
> > because it doesn't actually consume anything; its charge is a constant
> > 1. (It's not as good of a counterexample as my previous one, because
> > it may be argued that its valence is 1 when the stack's full and 0
> > when the stack's empty -- but that would be a pretty subtle argument.)
> 'empty?' takes the entire stack as an argument, returns 1 if it's
> empty, else 0. so in my lingo, it has infinite valence.
In your lingo, then, every one of your primitives has infinite valence
-- they also take the entire stack as an argument and branch based on
whether it's full or empty. Right?
> > You're right: one possible application would be using your behavior to
> > define DEPTH :-). My point was just that misusing it is very easy and
> > invisible (you can't test a program by running it at the command line,
> > because it might behave differently 'in vivo'), and using it correctly
> > is hard for any job that doesn't naturally start with "first, consume
> > the entire stack". In fact, every time you deliberately use it, you
> > must start by first consuming the entire stack (and then possibly put
> > some of it back).
> well, the same could be said of many of joy's combinators.
I don't like the behavior of Joy's combinators, and have argued so. I
don't like how they insist on saving and restoring the stack "behind
my back." But my argument above doesn't apply to Joy's combinators,
because they're just library functions, not a fundamental language
feature.
> i just don't see this as a compelling argument.
You don't have to define Joy's problems into your language. You can
implement a single primitive, DEPTH, that allows you to pretend to be
Joyful, but in reality your language is being False.
Seriously: Joy's combinators, unlike your language feature, are just
library functions. If I don't like how 'if' saves and restores the
stack (and I don't), I don't have to use it -- I can define my own
'if', and I'd be certain that my programs would work the way I wanted.
If I don't like how F's primitives behave, that's too bad -- I can't
escape them (unless I stop using F).
-Billy
stevan apter — 2006-07-01 03:17:26
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, June 30, 2006 5:19 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> stevan apter <sa@...> wrote:
> > > I'll prove by counterexample that it's untrue: I can define a language
> > > in which 'stack' could be defined without any variable valence
> > > primitives -- not even a variable loop. This hypothetical language has
> > > a stack that's a constant depth (probably a circular buffer), so
> > > saving it to an array requires a constant number of operations. This
> > > is an extreme counterexample, and I suspect that some gentler one
> > > probably exists -- but at the same time, note that one concatenative
> > > language actually works this way (Chuck Moore's machine forth and
> > > colorforth).
>
> > wow - a circular stack - a stircle.
>
> Heh, yup. No suprise that Chuck would have used one -- engineers are
> always using circular buffers. (schtuffers?)
so >r and r> rotate the stack left and right one position? a nice
way to store/retrieve things. (i'm almost kidding - i wouldn't expect
moore to do this .. but i would!)
>
> > > I just thought of a gentler counterexample: a primitive named 'empty?'
> > > could be used to implement 'stack'. It returns true when the stack is
> > > empty, false otherwise. Its valence is undetectably close to zero,
> > > because it doesn't actually consume anything; its charge is a constant
> > > 1. (It's not as good of a counterexample as my previous one, because
> > > it may be argued that its valence is 1 when the stack's full and 0
> > > when the stack's empty -- but that would be a pretty subtle argument.)
>
> > 'empty?' takes the entire stack as an argument, returns 1 if it's
> > empty, else 0. so in my lingo, it has infinite valence.
>
> In your lingo, then, every one of your primitives has infinite valence
> -- they also take the entire stack as an argument and branch based on
> whether it's full or empty. Right?
no, i don't think so. + has valence 2 - it only cares about the top
two items. 'empty?' has to have the entire stack, in order to count
the elements. i admit that i don't know how to reconcile this idea
with the slogan that everything is a function of stacks to stacks.
e.g. in my implementation, the function which dispatches the + code
calls a function, viz. {x+y} on the top two arguments of the stack.
>
> > > You're right: one possible application would be using your behavior to
> > > define DEPTH :-). My point was just that misusing it is very easy and
> > > invisible (you can't test a program by running it at the command line,
> > > because it might behave differently 'in vivo'), and using it correctly
> > > is hard for any job that doesn't naturally start with "first, consume
> > > the entire stack". In fact, every time you deliberately use it, you
> > > must start by first consuming the entire stack (and then possibly put
> > > some of it back).
>
> > well, the same could be said of many of joy's combinators.
>
> I don't like the behavior of Joy's combinators, and have argued so. I
> don't like how they insist on saving and restoring the stack "behind
> my back." But my argument above doesn't apply to Joy's combinators,
> because they're just library functions, not a fundamental language
> feature.
>
> > i just don't see this as a compelling argument.
>
> You don't have to define Joy's problems into your language. You can
> implement a single primitive, DEPTH, that allows you to pretend to be
> Joyful, but in reality your language is being False.
:)
for now, i'm not convinced that these are problems.
>
> Seriously: Joy's combinators, unlike your language feature, are just
> library functions. If I don't like how 'if' saves and restores the
> stack (and I don't), I don't have to use it -- I can define my own
> 'if', and I'd be certain that my programs would work the way I wanted.
> If I don't like how F's primitives behave, that's too bad -- I can't
> escape them (unless I stop using F).
well, you could always just change the script. There's one data-
structure (O) which associates symbols with functions, e.g.
("$" ;y[1;{(x;x)}]) / dup
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2006-07-01 08:00:16
stevan apter <
sa@...> wrote:
I'll be gone for a week -- one final message:
> > stevan apter <sa@...> wrote:
> > Heh, yup. No suprise that Chuck would have used one -- engineers are
> > always using circular buffers. (schtuffers?)
> so >r and r> rotate the stack left and right one position? a nice
> way to store/retrieve things. (i'm almost kidding - i wouldn't expect
> moore to do this .. but i would!)
'drop' rotates the stack one element, of course... I don't know
whether there's a word to rotate it the other way.
> > > > I just thought of a gentler counterexample: a primitive named 'empty?'
> > > > could be used to implement 'stack'. It returns true when the stack is
> > > > empty, false otherwise. Its valence is undetectably close to zero,
> > > > because it doesn't actually consume anything; its charge is a constant
> > > > 1. (It's not as good of a counterexample as my previous one, because
> > > > it may be argued that its valence is 1 when the stack's full and 0
> > > > when the stack's empty -- but that would be a pretty subtle argument.)
> > > 'empty?' takes the entire stack as an argument, returns 1 if it's
> > > empty, else 0. so in my lingo, it has infinite valence.
> > In your lingo, then, every one of your primitives has infinite valence
> > -- they also take the entire stack as an argument and branch based on
> > whether it's full or empty. Right?
> no, i don't think so. + has valence 2 - it only cares about the top
> two items. 'empty?' has to have the entire stack, in order to count
> the elements. i admit that i don't know how to reconcile this idea
> with the slogan that everything is a function of stacks to stacks.
> e.g. in my implementation, the function which dispatches the + code
> calls a function, viz. {x+y} on the top two arguments of the stack.
What's going on? Why are ALL your words allowed to know how deep the
stack is, while my single smart word gets penalized for knowing? Your
words ALL have the function of 'empty?', except that they're more
complex (empty? doesn't change its stack behavior at all; your words
do).
> > You don't have to define Joy's problems into your language. You can
> > implement a single primitive, DEPTH, that allows you to pretend to be
> > Joyful, but in reality your language is being False.
> :)
> for now, i'm not convinced that these are problems.
That's cool. I think your proposal has problems much worse than Joy's,
but they seem so obvious that after all this talk I'm pretty certain
you understand them and don't see them as problems. That's okay, I
guess -- I don't see how they wouldn't cripple the language, but
whatever works.
> > Seriously: Joy's combinators, unlike your language feature, are just
> > library functions. If I don't like how 'if' saves and restores the
> > stack (and I don't), I don't have to use it -- I can define my own
> > 'if', and I'd be certain that my programs would work the way I wanted.
> > If I don't like how F's primitives behave, that's too bad -- I can't
> > escape them (unless I stop using F).
> well, you could always just change the script. There's one data-
> structure (O) which associates symbols with functions, e.g.
> ("$" ;y[1;{(x;x)}]) / dup
Please explain -- what does "change the script" do? And don't all your
functions behave specially when the stack's empty, so no matter what
you assign, it'll still behave the same way?
-Billy
stevan apter — 2006-07-01 12:51:03
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, July 01, 2006 4:00 AM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> stevan apter <sa@...> wrote:
>
> I'll be gone for a week -- one final message:
>
> > > stevan apter <sa@...> wrote:
> > > Heh, yup. No suprise that Chuck would have used one -- engineers are
> > > always using circular buffers. (schtuffers?)
>
> > so >r and r> rotate the stack left and right one position? a nice
> > way to store/retrieve things. (i'm almost kidding - i wouldn't expect
> > moore to do this .. but i would!)
>
> 'drop' rotates the stack one element, of course... I don't know
> whether there's a word to rotate it the other way.
>
> > > > > I just thought of a gentler counterexample: a primitive named 'empty?'
> > > > > could be used to implement 'stack'. It returns true when the stack is
> > > > > empty, false otherwise. Its valence is undetectably close to zero,
> > > > > because it doesn't actually consume anything; its charge is a constant
> > > > > 1. (It's not as good of a counterexample as my previous one, because
> > > > > it may be argued that its valence is 1 when the stack's full and 0
> > > > > when the stack's empty -- but that would be a pretty subtle argument.)
>
> > > > 'empty?' takes the entire stack as an argument, returns 1 if it's
> > > > empty, else 0. so in my lingo, it has infinite valence.
>
> > > In your lingo, then, every one of your primitives has infinite valence
> > > -- they also take the entire stack as an argument and branch based on
> > > whether it's full or empty. Right?
>
> > no, i don't think so. + has valence 2 - it only cares about the top
> > two items. 'empty?' has to have the entire stack, in order to count
> > the elements. i admit that i don't know how to reconcile this idea
> > with the slogan that everything is a function of stacks to stacks.
> > e.g. in my implementation, the function which dispatches the + code
> > calls a function, viz. {x+y} on the top two arguments of the stack.
>
> What's going on? Why are ALL your words allowed to know how deep the
> stack is, while my single smart word gets penalized for knowing? Your
> words ALL have the function of 'empty?', except that they're more
> complex (empty? doesn't change its stack behavior at all; your words
> do).
from the implementation's perspective, there are really only three
functions - x, y, and z. each of them takes two arguments - a valence n,
and a function f - and returns one result - a function. that anonymous
function takes the entire stack and the entire queue, pops n elements
from the stack, applies f, takes the result of that application, and
either (x) appends it to the stack as a unit, (y) appends the separate
elements of the result to the stack, or (z) prepends the separate
elements of the result to the queue (for further evaluation.) + is
an 'x' function - given two lists, it adds them and appends the
resultant list to the stack as a unit (remember that F has atomic
extension.) 'dup' is a 'y' function - it returns two elements which
are appended to the stack. 'i' is a 'z' function - it takes a
quotation, prepends the elements of the quotation to the queue, which
are then subsequently evaluated.
when i say that no primitive in F sees the entire stack, i mean for
example that + sees only the two elements which the anonymous function
produced by 'x' passes to it. the fact that the anonymous function --
the "dispatcher" -- sees the entire stack is a mere implementation
detail. in a "real" implementation, i would expect this to be
handled quite differently. but at a conceptual level, all of the
primitives can be said to have fixed, finite valence.
here's how i would modify my implementation to support DEPTH: every
primitive p has fixed, finite valence n, but the dispatcher calls
p with n+1 arguments, the first being the depth of the stack.
every primitive except DEPTH ignores that argument; DEPTH returns
it. here's DEPTH in the F implementation:
x[0;{x}]
n is 0, the primitive corresponding to + is the identity function.
>
> > > You don't have to define Joy's problems into your language. You can
> > > implement a single primitive, DEPTH, that allows you to pretend to be
> > > Joyful, but in reality your language is being False.
>
> > :)
> > for now, i'm not convinced that these are problems.
>
> That's cool. I think your proposal has problems much worse than Joy's,
> but they seem so obvious that after all this talk I'm pretty certain
> you understand them and don't see them as problems. That's okay, I
> guess -- I don't see how they wouldn't cripple the language, but
> whatever works.
>
> > > Seriously: Joy's combinators, unlike your language feature, are just
> > > library functions. If I don't like how 'if' saves and restores the
> > > stack (and I don't), I don't have to use it -- I can define my own
> > > 'if', and I'd be certain that my programs would work the way I wanted.
> > > If I don't like how F's primitives behave, that's too bad -- I can't
> > > escape them (unless I stop using F).
>
> > well, you could always just change the script. There's one data-
> > structure (O) which associates symbols with functions, e.g.
> > ("$" ;y[1;{(x;x)}]) / dup
>
> Please explain -- what does "change the script" do? And don't all your
> functions behave specially when the stack's empty, so no matter what
> you assign, it'll still behave the same way?
i mean you could e.g. add DEPTH by add the suggested code above
to the O data-structure.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2006-07-12 00:36:05
stevan apter <
sa@...> wrote:
[I said:]
> > No, you're totally right. This is why I also don't like Joy's habit of
> > saving and restoring the entire stack. I would rather define things
> > such that no full-stack saving and restoring is needed; most other
> > pre-Joy concatenative languages work that way, so there's no doubt it
> > can be done. (Of course, you're proving that you can do the same
> > things as Joy, so I accept that you must perform full-stack saving and
> > restoring.)
> forth and factor, to take two examples, have >r and r> (have i got
> their names right?), and possibly something like DEPTH as well, isn't
> that so? i think if you have those at your disposal, you have enough
> to define e.g. 'linrec'.
Yes, Forth has those; in spite of my admiration of Factor, I don't
know how it does those things. (BTW, the use of DEPTH is discouraged
in Forth.)
> i think we've discussed this in the past: in joy, you can have
> something like
> X [1 2 3][+]map
[which]
> leaves
> X [x y z]
> on the stack. how would you implement this behavior without some
> mechanism for saving and restoring the stack before and after each
> application of +?
You'd do it simply by not saving and restoring the stack, and thereby
expecting the programmer to code in a way that acts responsibly with
the stack. In your example, a general non-stack-saving replacement for
"[+]map" would be "[+]cons map" (this doesn't preserve the X value,
but that's very easy to do -- and if I don't want to preserve the X
value, I shouldn't have to). "[over+]map" is essentially the same
thing as your stack-preserving map, and "[X+]map" works with a loss of
generality.
In general, it's easy to come up with an equivalent program that
doesn't rely on stack-saving semantics. I can't think of a time when
it wouldn't be more efficient -- especially if you consider the
overhead of saving and restoring the stack. It would always be closer
to "linear logic" (a style of programming in which each given data
item is only used once unless it's explicitly copied), since by
definition implicitly saving the stack is performing an implicit copy.
The opposite is difficult. What if you want to write some complex
program that computes something by consuming values from the stack
until the result converges in some way? If your converge functions all
preserve the stack, by definition you can't use them to consume it. If
your converge functions don't preserve the stack, you can always write
the quotations you're going to pass to take care of their own stack
saving. "[over+]map" is an example of doing this. Because the
quotation doesn't _assume_ stack saving, it'll work no matter whether
map saves the stack or not.
Here's an excercise for you. Suppose I have a function in a Forthlike
Joy whose source is "[1 2 3]map". Obviously, this function consumes
three stack parameters and returns a list of three numbers. How would
you translate that into Joy (i.e. a language with a stack-preserving
"map"), without knowing or looking at the number of items in the list?
-Billy
sa@dfa.com — 2006-07-12 13:09:38
concatenative@yahoogroups.com wrote on 07/11/2006 08:36:05 PM:
> stevan apter <sa@...> wrote:
> [I said:]
> > > No, you're totally right. This is why I also don't like Joy's habit
of
> > > saving and restoring the entire stack. I would rather define things
> > > such that no full-stack saving and restoring is needed; most other
> > > pre-Joy concatenative languages work that way, so there's no doubt it
> > > can be done. (Of course, you're proving that you can do the same
> > > things as Joy, so I accept that you must perform full-stack saving
and
> > > restoring.)
>
> > forth and factor, to take two examples, have >r and r> (have i got
> > their names right?), and possibly something like DEPTH as well, isn't
> > that so? i think if you have those at your disposal, you have enough
> > to define e.g. 'linrec'.
>
> Yes, Forth has those; in spite of my admiration of Factor, I don't
> know how it does those things. (BTW, the use of DEPTH is discouraged
> in Forth.)
>
> > i think we've discussed this in the past: in joy, you can have
> > something like
> > X [1 2 3][+]map
> [which]
> > leaves
> > X [x y z]
>
> > on the stack. how would you implement this behavior without some
> > mechanism for saving and restoring the stack before and after each
> > application of +?
>
> You'd do it simply by not saving and restoring the stack, and thereby
> expecting the programmer to code in a way that acts responsibly with
> the stack. In your example, a general non-stack-saving replacement for
> "[+]map" would be "[+]cons map" (this doesn't preserve the X value,
> but that's very easy to do -- and if I don't want to preserve the X
> value, I shouldn't have to). "[over+]map" is essentially the same
> thing as your stack-preserving map, and "[X+]map" works with a loss of
> generality.
it's a little hard for me to tell, but i think my notation
might have led you astray. consider
10 20 30 [1 2 3][+]map
10 20 30 [31 32 33]
'map' saves the stack below [31 32 33] (i.e. 10 20 30). it
pushes 1, so the stack is 10 20 30 1, then executes +, leaving
10 20 31. it sets 31 aside, restores the stack to 10 20 30,
pushes 2, &c. finally, it has the results [31 32 33]; it
restores the stack once more, and pushes the result.
that's my understanding of how joy's 'map' works.
William Tanksley, Jr — 2006-07-12 19:26:28
sa@... <
sa@...> wrote:
> it's a little hard for me to tell, but i think my notation
> might have led you astray. consider
> 10 20 30 [1 2 3][+]map
> 10 20 30 [31 32 33]
What did I do wrong? This looks like what I'd expect. Will one of my
functions fail to produce this result (aside from the one that throws
away the initial 30)?
> 'map' saves the stack below [31 32 33] (i.e. 10 20 30). it
> pushes 1, so the stack is 10 20 30 1, then executes +, leaving
> 10 20 31. it sets 31 aside, restores the stack to 10 20 30,
> pushes 2, &c. finally, it has the results [31 32 33]; it
> restores the stack once more, and pushes the result.
Yeah, that look like what I expected.
-Billy
stevan apter — 2006-07-12 22:59:53
i think what you're saying is this (i haven't checked to see
whether your functions do this):
the programmer should know that +, applied to each of [1 2 3],
requires an additional argument, which is to be found on the
stack. if the function were, say, +*, then each application
would require two additional arguments, which are to be found on
the stack. then, depending on the programmer's intentions, he
should explicitly do just that: collect the additional values
from the stack, and construct the appropriate list to map +
(or +*) on:
10 20 30 [[30 1][30 2][30 3]] ...
what's bad about joy's map is that it usurps this control from
the programmer.
if i've got this right, then there are two things i would say.
first, joy's map (and f's - but see below) doesn't require
that the programmer know anything about the function to be
mapped, or the nature of the items in the list on to which
the function is to be mapped.
.. [X Y Z][..] map
will consume as many items from the stack as [..] requires,
in addition to each of X, Y, Z. so
10 20 30 [1 [2 3][]][i+*]map
10 20 30 [620 150 500]
second, as you can see from this example, the function to
be mapped begins with 'i'. this is because (at least in
my implementation) the function to be mapped can be a list
function, like 'count', or an atomic function, like +*.
this is a minor point.
in F, i've implemented two sets of combinators, e.g. 'map'
and 'Map'. 'map' is weak: if the function doesn't find
as many values as it requires in each item of the list, it
fails with a stack underflow. 'Map' is like joy's 'map',
and in fact is defined using the weaker 'map'.
here are the definitions in F's joy dialect:
[[dup count [] top] dip swap [quote uncons dip dup top
[cons unit apply first swons] dipd] do pop pop rev] map
[quote stack dipd [quote unit map quote join right] dip
quote join left [unit apply last] map] Map
as you can see, 'Map' uses 'stack', 'map' does not.
nb:
quote x -> [x]
x y z top -> z x y
[x y z] rev -> [z y x]
x [y z w] f -> [x y f i x z f i x w f i]
'apply' is joy's 'infra'.
i think perhaps our differences on this matter (and possibly
others as well) can be reduced to this: i see joy and F as
high-level languages, while you see them as more forth-like.
in that case, you would give greater weight to considerations
which preoccupy forthians, mainly efficiency and programmer-
control.
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, July 12, 2006 3:26 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> sa@... <sa@...> wrote:
> > it's a little hard for me to tell, but i think my notation
> > might have led you astray. consider
> > 10 20 30 [1 2 3][+]map
> > 10 20 30 [31 32 33]
>
> What did I do wrong? This looks like what I'd expect. Will one of my
> functions fail to produce this result (aside from the one that throws
> away the initial 30)?
>
> > 'map' saves the stack below [31 32 33] (i.e. 10 20 30). it
> > pushes 1, so the stack is 10 20 30 1, then executes +, leaving
> > 10 20 31. it sets 31 aside, restores the stack to 10 20 30,
> > pushes 2, &c. finally, it has the results [31 32 33]; it
> > restores the stack once more, and pushes the result.
>
> Yeah, that look like what I expected.
>
> -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-07-13 19:24:30
stevan apter <
sa@...> wrote:
> i think what you're saying is this (i haven't checked to see
> whether your functions do this):
> the programmer should know that +, applied to each of [1 2 3],
> requires an additional argument, which is to be found on the
> stack.
Hmm... Yes, the programmer should (and does) know this, and must know
it for either of our models.
> if the function were, say, +*, then each application
> would require two additional arguments, which are to be found on
> the stack. then, depending on the programmer's intentions, he
> should explicitly do just that: collect the additional values
> from the stack, and construct the appropriate list to map +
> (or +*) on:
> 10 20 30 [[30 1][30 2][30 3]] ...
I don't see why you'd ever want to do that. Parsing through the data
is map's job. You want to pass a quotation to map that does what map
needs. One thing that will work elegantly in this case is to take a
quotation that takes two values and curry a constant value onto it to
get a new quotation that only takes one value. That's simple, commonly
used in functional programming, and fairly fast.
> what's bad about joy's map is that it usurps this control from
> the programmer.
Not really. Not only do I not see that as useful control, I'm also not
so much worried about any possible functionality loss -- anything one
system can do, the other system can do perhaps a little less comfort.
The real question in any approach to programming language design is
"what operations does this design make comfortable?" If you're
thinking of adding GOTO to a pure structural language, it'll perhaps
make some things much more comfortable -- but at what cost to the
language?
By the way, I believe that every function that uses a stack-restoring
'map' can be written to work independantly of the stack-restoring
behavior of 'map'. (Proof by lassitude: I haven't been able to find a
counterexample.) I'm certain that some of them will run slower, of
course.
So there's no loss of control either way. I think the main
consideration is one of style and safety.
In terms of safety, stack-restoring means that some operations will
have an effect when used in some locations that they won't when used
in other locations. This removes referential transparency in a very
odd way, for no obvious gain.
In terms of style, stack-restoring encourages code that depends on it;
for obvious example, one would write a map function that, if 'i' were
used instead of map to execute it on an arbitrary element of the list,
would have a different result than what would be seen by examining the
equivalent element of the result list from map.
For example,
[1 2 3][+]map head
is not the same stack effect as
[1 2 3]head [+] i
Worse problems can be seen if [+] is replaced with an arbitrary quotation.
It seems clear to me that the best style is to use static stack
effects whenever possible -- even 'i' can be staticly typesafe if the
programmer specifies what type of quotation is passed to it.
The only substantial advantage given by stack-saving combinators like
Joy's map, if, and so on is to people who are writing non-static stack
effects, because non-static stack effects are hard to clean up with
anything less than a full stack save and restore. And that behavior is
not something we have any need to make easier.
> if i've got this right, then there are two things i would say.
> first, joy's map (and f's - but see below) doesn't require
> that the programmer know anything about the function to be
> mapped, or the nature of the items in the list on to which
> the function is to be mapped.
Same for my 'map'. You should add that the person writing the
quotation being passed to 'map' does have to know the nature of the
items on the list being passed to 'map', but shouldn't have to know
anything about the environment 'map' is being called in.
If the programmer(s) adhere to these guidelines, then it won't matter
whether 'map' saves and/or restores the stack, because the passed
function will only access the data it knows is there.
> .. [X Y Z][..] map
> will consume as many items from the stack as [..] requires,
> in addition to each of X, Y, Z. so
That's a very unclear description of what happens -- it actually won't
consume anything from the stack, because the stuff is still there on
the stack when it finishes. In my recommended version of map it would
consume the stuff, of course. In Joy's it would only be able to look
at the stuff, and only as much stuff as a single execution of [..]
would require.
Do you not find that confusing?
> 10 20 30 [1 [2 3][]][i+*]map
> 10 20 30 [620 150 500]
> second, as you can see from this example, the function to
> be mapped begins with 'i'. this is because (at least in
> my implementation) the function to be mapped can be a list
> function, like 'count', or an atomic function, like +*.
> this is a minor point.
What's your point? I see that the function begins with 'i', but I
don't know what I'm being asked to conclude from that. I can't imagine
an implementation of 'map' that disallowed list functions -- that
would seem pointless.
> in F, i've implemented two sets of combinators, e.g. 'map'
> and 'Map'. 'map' is weak: if the function doesn't find
> as many values as it requires in each item of the list, it
> fails with a stack underflow. 'Map' is like joy's 'map',
> and in fact is defined using the weaker 'map'.
Yes, your 'map' meets all my requirements and then some. It actually
seems to me to act more like a typical applicative version of 'map'.
> i think perhaps our differences on this matter (and possibly
> others as well) can be reduced to this: i see joy and F as
> high-level languages, while you see them as more forth-like.
Nope. It's an issue of language design, not as high or low level.
Joy's stack shenanigans are like Fortran's computed GOTOs -- nice to
have, but IFs really are better language design.
(And obviously, you see Forth as a low-level language, while I see it
as the framework on which an application-specific concatenative
language is built. Make no mistake, Forth offers fewer amenities than
Joy -- but that doesn't make it the opposite of high-level.)
> in that case, you would give greater weight to considerations
> which preoccupy forthians, mainly efficiency and programmer-
> control.
Forthians do have something to teach concatenativians. You can't
dismiss everything we have to say as being merely about speed
concerns. This one isn't even peripherially about speed. It's about
safety, style, and predictability -- hmm, and reusability.
-Billy
stevan apter — 2006-07-23 17:54:09
i don't know why it took me so long to realize that 'stack',
'unstack', 'r>' and '>r' are instances of a more generalized
'cont' operation.
$, the 'cont' combinator, expects a program p on top of the stack.
p expects two quotations q and s. q is the current queue, and
beneath that, s is the current stack minus p. p leaves s' and q'
on the stack, which are made the new stack and queue:
s^p^$ q -> s' q'
s^q^p -> s'^q'
then:
J>'stack"o
[[[dup unit join]
dip]
cont]
J>'unstack"o
[['last dip]
cont]
J>'queue"o
[[[rev uncons rev swap]
dip swap unit join]
cont]
J>'unqueue"o
[[rev uncons rev [
unit join]
dip]
cont]
'cont' is general, in that it puts the future evolution of the
program state (the stack and the queue) directly under the control
of the programmer.
for K fans, 'cont' is defined:
{x,e[x;(-1_ y;z);*-1#y]1}
[Non-text portions of this message have been removed]
John Cowan — 2006-07-23 18:19:52
stevan apter scripsit:
> i don't know why it took me so long to realize that 'stack',
> 'unstack', 'r>' and '>r' are instances of a more generalized
> 'cont' operation.
Welcome to Scheme (SML, Haskell).
--
John Cowan <
cowan@...>
Yakka foob mog. Grug pubbawup zink wattoom gazork. Chumble spuzz.
-- Calvin, giving Newton's First Law "in his own words"
William Tanksley, Jr — 2006-07-23 19:33:35
stevan apter <
sa@...> wrote:
> i don't know why it took me so long to realize that 'stack',
> 'unstack', 'r>' and '>r' are instances of a more generalized
> 'cont' operation.
Sounds very interesting. Could you run that by me one more time? I
don't get it at all.
-Billy
stevan apter — 2006-07-23 20:32:08
$ requires that the program leave two quotations on the stack.
for example,
1 2 3 'id $ 4 5 6
contemplate the trace:
J>1 2 3 'id $ 4 5 6
? 1 2 3 'id $ 4 5 6
1 ? 2 3 'id $ 4 5 6
1 2 ? 3 'id $ 4 5 6
1 2 3 ? 'id $ 4 5 6
1 2 3 'id ? $ 4 5 6
[1 2 3] [4 5 6] ? id
[1 2 3] [4 5 6] ? [] !
[1 2 3] [4 5 6] [] ? !
[1 2 3] [4 5 6] ?
1 2 3 ? 4 5 6
1 2 3 4 ? 5 6
1 2 3 4 5 ? 6
1 2 3 4 5 6 ?
when $ evaluates, the stack is 1^2^3^[id] and the queue is 4^5^6.
$ packages up the stack and queue as two quotations, then evaluates
the program, in this case [id]. the result is a new stack and a
new queue.
now consider 'stack', which is defined:
[[[|unit,]`]$] stack
that is,
[[[dup unit join] dip] cont] stack
the stack trace:
J>1 2 3 stack 4 5 6
? 1 2 3 stack 4 5 6
1 ? 2 3 stack 4 5 6
1 2 ? 3 stack 4 5 6
1 2 3 ? stack 4 5 6
1 2 3 ? [[| unit ,] `] $ 4 5 6
1 2 3 [[| unit ,] `] ? $ 4 5 6
[1 2 3] [4 5 6] ? [| unit ,] `
[1 2 3] [4 5 6] [| unit ,] ? `
[1 2 3] ? | unit , [4 5 6]
[1 2 3] [1 2 3] ? unit , [4 5 6]
[1 2 3] [1 2 3] ? ' ' ` , [4 5 6]
[1 2 3] [1 2 3] '' ? ` , [4 5 6]
[1 2 3] ? ' [1 2 3] , [4 5 6]
[1 2 3] '[1 2 3] ? , [4 5 6]
[1 2 3 [1 2 3]] ? [4 5 6]
[1 2 3 [1 2 3]] [4 5 6] ?
1 2 3 [1 2 3] ? 4 5 6
1 2 3 [1 2 3] 4 ? 5 6
1 2 3 [1 2 3] 4 5 ? 6
1 2 3 [1 2 3] 4 5 6 ?
----- Original Message -----
From: William Tanksley, Jr
To: concatenative@yahoogroups.com
Sent: Sunday, July 23, 2006 3:33 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
stevan apter <sa@...> wrote:
> i don't know why it took me so long to realize that 'stack',
> 'unstack', 'r>' and '>r' are instances of a more generalized
> 'cont' operation.
Sounds very interesting. Could you run that by me one more time? I
don't get it at all.
-Billy
Yahoo! Groups Links
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2006-07-23 21:11:24
stevan apter <
sa@...> wrote:
> $ requires that the program leave two quotations on the stack.
> for example,
> contemplate the trace:
Thank you, that was exactly what I needed. So $ takes a function,
wraps up the stack and the rest-of-the-program for it into 2 lists,
and the function is then able to manipulate those lists however it
wishes. When the function returns, $ finishes by restoring the stack
and queue from those 2 lists.
I'm not sure I agree with you on the elegance of this $ operator. It
does a LOT, wouldn't you say? It doesn't so much seem to replace the
stack operator as incorporate (or require) it, since one of the many
things it has to do is push the stack into a list.
On the other hand, the $ operator does seem to do the same thing for
stack/unstack that the dip operator does for >R/R>: it removes the
need to track the pair of operators, and therefore makes it impossible
to "get it wrong".
I think I'd be happier with a different breakdown, though: one
operator to do that with the stack, and another operator to do it with
the queue.
-Billy
stevan apter — 2006-07-24 11:22:36
of course you're right that $ incorporates 'stack', and if
that was all that was achieved it would be of little interest.
but it goes well beyond that, since it gathers together under
one primitive all operations from whole program state to whole
program state.
----- Original Message -----
From: William Tanksley, Jr
To: concatenative@yahoogroups.com
Sent: Sunday, July 23, 2006 5:11 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
stevan apter <sa@...> wrote:
> $ requires that the program leave two quotations on the stack.
> for example,
> contemplate the trace:
Thank you, that was exactly what I needed. So $ takes a function,
wraps up the stack and the rest-of-the-program for it into 2 lists,
and the function is then able to manipulate those lists however it
wishes. When the function returns, $ finishes by restoring the stack
and queue from those 2 lists.
I'm not sure I agree with you on the elegance of this $ operator. It
does a LOT, wouldn't you say? It doesn't so much seem to replace the
stack operator as incorporate (or require) it, since one of the many
things it has to do is push the stack into a list.
On the other hand, the $ operator does seem to do the same thing for
stack/unstack that the dip operator does for >R/R>: it removes the
need to track the pair of operators, and therefore makes it impossible
to "get it wrong".
I think I'd be happier with a different breakdown, though: one
operator to do that with the stack, and another operator to do it with
the queue.
-Billy
Yahoo! Groups Links
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2006-07-24 13:42:10
stevan apter <
sa@...> wrote:
> of course you're right that $ incorporates 'stack', and if
> that was all that was achieved it would be of little interest.
> but it goes well beyond that, since it gathers together under
> one primitive all operations from whole program state to whole
> program state.
I see; that does seem to be of interest. With $, you don't need any
kind of hidden access to "magic" variables like DEPTH or IP. By the
way, is $ mnemonic for $tate (state)?
Whoops, there's still another magic variable -- the dictionary. If $
is supposed to truly provide the whole program state, it must also
provide access to the dictionary. The most logical way is no doubt as
another list, probably a list of pairs.
I'm not conceding that I like $, by the way ;-). I'm just admitting
that I see your point in defining it (I think).
-Billy
sa@dfa.com — 2006-07-24 17:00:56
concatenative@yahoogroups.com wrote on 07/24/2006 09:42:10 AM:
> stevan apter <sa@...> wrote:
> > of course you're right that $ incorporates 'stack', and if
> > that was all that was achieved it would be of little interest.
> > but it goes well beyond that, since it gathers together under
> > one primitive all operations from whole program state to whole
> > program state.
>
> I see; that does seem to be of interest. With $, you don't need any
> kind of hidden access to "magic" variables like DEPTH or IP. By the
> way, is $ mnemonic for $tate (state)?
yes, because i can't type the cent character, which would be mnemonic
for "continuation". :)
>
> Whoops, there's still another magic variable -- the dictionary. If $
> is supposed to truly provide the whole program state, it must also
> provide access to the dictionary. The most logical way is no doubt as
> another list, probably a list of pairs.
yes, the program state = [env stack queue], but since F doesn't
permit reassignment, there's no point in making env part of the
continuation. that is, the access F programs have to the environment
is limited to (i) first-time assignment of a name to a value, and (ii)
use of a variable.
>
> I'm not conceding that I like $, by the way ;-). I'm just admitting
> that I see your point in defining it (I think).
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-07-24 17:35:29
sa@... <
sa@...> wrote:
> > I see; that does seem to be of interest. With $, you don't need any
> > kind of hidden access to "magic" variables like DEPTH or IP. By the
> > way, is $ mnemonic for $tate (state)?
> yes, because i can't type the cent character, which would be mnemonic
> for "continuation". :)
Oh, right -- it's kinda like "call/cc". Hmm. Yes, I guess it is,
kinda. (The name "continuation" doesn't communicate to me -- I now see
that's what you meant by "cont" in your original post.)
Technically, all "call/cc" needs is to pass the queue to the called
function -- stacking and unstacking the entire stack is needless,
since the entire stack will be passed to the function no matter what,
and the function is free to manipulate the resulting stack in any way.
The _only_ reasons I can see for doing it is that you either want to
implement stack/unstack in terms of $, or you want to allow
cooperative multitasking. The first one seems like an intrinsicly bad
idea; the second one seems just as well done by providing three
state-fetching words instead of just one (fetch-stack, fetch-queue,
fetch-dictionary), because each of those three words can be used in
other ways without requiring the overhead of the other two fetches and
restores.
I guess what I'm saying is that if you want to implement call/cc you
should be doing less (only pass the queue), and if you want to save
the entire execution state you should be doing more (also pass the
dictionary).
> > Whoops, there's still another magic variable -- the dictionary. If $
> > is supposed to truly provide the whole program state, it must also
> > provide access to the dictionary. The most logical way is no doubt as
> > another list, probably a list of pairs.
> yes, the program state = [env stack queue], but since F doesn't
> permit reassignment, there's no point in making env part of the
> continuation. that is, the access F programs have to the environment
> is limited to (i) first-time assignment of a name to a value, and (ii)
> use of a variable.
I'm not sure about this argument -- you're arguing that giving direct
access to the dictionary would allow you to do things that you
couldn't do without the direct access, which seems to be an argument
in *favor* of the direct access.
-Billy
stevan apter — 2006-07-24 21:15:26
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 24, 2006 1:35 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> sa@... <sa@...> wrote:
> > > I see; that does seem to be of interest. With $, you don't need any
> > > kind of hidden access to "magic" variables like DEPTH or IP. By the
> > > way, is $ mnemonic for $tate (state)?
>
> > yes, because i can't type the cent character, which would be mnemonic
> > for "continuation". :)
>
> Oh, right -- it's kinda like "call/cc". Hmm. Yes, I guess it is,
> kinda. (The name "continuation" doesn't communicate to me -- I now see
> that's what you meant by "cont" in your original post.)
i've renamed it 'state', which seems better on all accounts.
>
> Technically, all "call/cc" needs is to pass the queue to the called
> function -- stacking and unstacking the entire stack is needless,
> since the entire stack will be passed to the function no matter what,
> and the function is free to manipulate the resulting stack in any way.
> The _only_ reasons I can see for doing it is that you either want to
> implement stack/unstack in terms of $,
yes
or you want to allow
> cooperative multitasking. The first one seems like an intrinsicly bad
> idea;
i don't see why.
the second one seems just as well done by providing three
> state-fetching words instead of just one (fetch-stack, fetch-queue,
> fetch-dictionary), because each of those three words can be used in
> other ways without requiring the overhead of the other two fetches and
> restores.
>
> I guess what I'm saying is that if you want to implement call/cc you
> should be doing less (only pass the queue), and if you want to save
> the entire execution state you should be doing more (also pass the
> dictionary).
i might be driven in that direction if there was any cost attached
to placing the stack or the queue on the stack, but since both are
lists, the operation is free. (so too is setting the stack and queue)
i recognize that this might not be true given a different implementation,
but for me it's not a consideration. where x is a list x,,x -- appending
the unit-list of x to x -- costs nothing.
>
> > > Whoops, there's still another magic variable -- the dictionary. If $
> > > is supposed to truly provide the whole program state, it must also
> > > provide access to the dictionary. The most logical way is no doubt as
> > > another list, probably a list of pairs.
>
> > yes, the program state = [env stack queue], but since F doesn't
> > permit reassignment, there's no point in making env part of the
> > continuation. that is, the access F programs have to the environment
> > is limited to (i) first-time assignment of a name to a value, and (ii)
> > use of a variable.
>
> I'm not sure about this argument -- you're arguing that giving direct
> access to the dictionary would allow you to do things that you
> couldn't do without the direct access, which seems to be an argument
> in *favor* of the direct access.
in f, assignment of a name to a value (i.e. creating a variable) has
the syntax
value undefined-name
and use of a variable has the syntax
defined-name
there's no way to un-assign a name (i.e. undefine a variable.)
if i were to provide direct access to the environment, i would have
to support first-class dictionaries or the equivalent. i don't want
to do the former. an equivalent might be, as you suggest, a pair
whose first element was a list of names and whose second was a list
of variables. then, given 'env' and 'unenv', i could define 'set',
'get', and 'del'.
it's a thought.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-07-24 22:15:43
stevan apter <
sa@...> wrote:
> > The _only_ reasons I can see for doing it is that you either want to
> > implement stack/unstack in terms of $,
[...]
> > seems like an intrinsicly bad idea;
> i don't see why.
I could be wrong :-). I think my dislike for dip-like solutions is
betraying me, honestly. (dip provides you with a second stack, but
doesn't let you manage it, thereby making it impossible to screw it up
-- a good thing and a sometimes inconvenient thing both at the same
time.)
> > I guess what I'm saying is that if you want to implement call/cc you
> > should be doing less (only pass the queue), and if you want to save
> > the entire execution state you should be doing more (also pass the
> > dictionary).
> i might be driven in that direction if there was any cost attached
> to placing the stack or the queue on the stack, but since both are
> lists, the operation is free. (so too is setting the stack and queue)
> i recognize that this might not be true given a different implementation,
> but for me it's not a consideration. where x is a list x,,x -- appending
> the unit-list of x to x -- costs nothing.
That's a really good point. It's good to have an operation that's
mathematically clean and very computationally inexpensive.
> if i were to provide direct access to the environment, i would have
> to support first-class dictionaries or the equivalent. i don't want
> to do the former. an equivalent might be, as you suggest, a pair
> whose first element was a list of names and whose second was a list
> of variables. then, given 'env' and 'unenv', i could define 'set',
> 'get', and 'del'.
> it's a thought.
Alternately, you could say "the third stack value is the dictionary,
not currently supported. Don't mess with it." :-).
-Billy
stevan apter — 2006-07-25 10:36:08
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 24, 2006 6:15 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> stevan apter <sa@...> wrote:
> > > The _only_ reasons I can see for doing it is that you either want to
> > > implement stack/unstack in terms of $,
> [...]
> > > seems like an intrinsicly bad idea;
>
> > i don't see why.
>
> I could be wrong :-). I think my dislike for dip-like solutions is
> betraying me, honestly. (dip provides you with a second stack, but
> doesn't let you manage it, thereby making it impossible to screw it up
> -- a good thing and a sometimes inconvenient thing both at the same
> time.)
i've never used (or implemented) a return stack in any of my toy
languages, and in fact i'm not entirely clear on how it works in
forth. in F, 'dip' swaps the first two items on the stack and
pushes them onto the queue, where first the program will evaluate,
and then the element which was formerly on top of the stack will
evaluate.
a pattern i find myself using repeatedly is a combination of 'dip',
'pair' (to shorten the stack), 'bot' and 'top' (i.e. 'rot' and '-rot'),
and 'unpair' (to unpack paired elements.) it's just too painful to
try to work with more than four or five stack elements.
with the 'queue' and 'unqueue' words (i.e. 'r>' and '>r'), i have
another method for temporarily moving things out of the way -- using
the far end of the queue as a temporary holding place for elements
on top of the stack. (and as we know 'dip' can then be defined as
'queue ! unqueue'.) as you say, this mechanism is prone to error
through carelessness.
btw, are you familiar with reva-forth? if so, do you have any
opinions?
William Tanksley, Jr — 2006-07-25 18:51:51
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > I could be wrong :-). I think my dislike for dip-like solutions is
> > betraying me, honestly. (dip provides you with a second stack, but
> > doesn't let you manage it, thereby making it impossible to screw it up
> > -- a good thing and a sometimes inconvenient thing both at the same
> > time.)
> i've never used (or implemented) a return stack in any of my toy
> languages, and in fact i'm not entirely clear on how it works in
> forth. in F, 'dip' swaps the first two items on the stack and
> pushes them onto the queue, where first the program will evaluate,
> and then the element which was formerly on top of the stack will
> evaluate.
Forth's return stack is vaguely like your queue, except that the
return stack doesn't hold anything from the currently executing word.
That information is maintained in the IP (instruction pointer).
Because Forth doesn't include any currently executing information on
the return stack, manipulation of the return stack won't affect the
current word's execution, only the execution of words after the
current word returns.
> a pattern i find myself using repeatedly is a combination of 'dip',
> 'pair' (to shorten the stack), 'bot' and 'top' (i.e. 'rot' and '-rot'),
> and 'unpair' (to unpack paired elements.) it's just too painful to
> try to work with more than four or five stack elements.
Forth doesn't have list manipulations, but if it did most Forthers
would discourage their use for the purpose of stack manipulations. The
#1 best way to not suffer the pain of dealing with large numbers of
stack elements is to design so that you don't need large numbers of
stack elements :-); after that, use the return stack/queue. I
personally would prefer the stack manipulation sublanguage (I've
mentioned it to you before) to using the return stack; it's much more
self-documenting, and usually faster.
> with the 'queue' and 'unqueue' words (i.e. 'r>' and '>r'), i have
> another method for temporarily moving things out of the way -- using
> the far end of the queue as a temporary holding place for elements
> on top of the stack. (and as we know 'dip' can then be defined as
> 'queue ! unqueue'.) as you say, this mechanism is prone to error
> through carelessness.
So's anything that changes the future execution, really -- I shouldn't
have been critical. It's a fine solution. The *exact* equivalent of
Forth's >R word would be a word that searched to find the end of the
current word, and popped the TOS into that location in the queue. R>
would do the opposite. Of course, if you really wanted perfect
imitation of unchecked Forth, you'd also have to include a word that
crashed the runtime if the >R position on the queue was reached before
a R> was executed -- but somehow I suspect you won't see that as a
positive feature ;-). (It's not positive, it's just simple and fast.)
> btw, are you familiar with reva-forth? if so, do you have any
> opinions?
I've seen it before. Looking again, I like it -- it's simple and
clean, a nice representative Forth. It imitates some of the best
recent Forths, without going as far as colorForth does (in colorForth
the editor is formally a part of the language).
-Billy
stevan apter — 2006-07-26 21:23:24
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, July 25, 2006 2:51 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> stevan apter <sa@...> wrote:
> > From: "William Tanksley, Jr" <wtanksleyjr@...>
> > > I could be wrong :-). I think my dislike for dip-like solutions is
> > > betraying me, honestly. (dip provides you with a second stack, but
> > > doesn't let you manage it, thereby making it impossible to screw it up
> > > -- a good thing and a sometimes inconvenient thing both at the same
> > > time.)
>
> > i've never used (or implemented) a return stack in any of my toy
> > languages, and in fact i'm not entirely clear on how it works in
> > forth. in F, 'dip' swaps the first two items on the stack and
> > pushes them onto the queue, where first the program will evaluate,
> > and then the element which was formerly on top of the stack will
> > evaluate.
>
> Forth's return stack is vaguely like your queue, except that the
> return stack doesn't hold anything from the currently executing word.
> That information is maintained in the IP (instruction pointer).
> Because Forth doesn't include any currently executing information on
> the return stack, manipulation of the return stack won't affect the
> current word's execution, only the execution of words after the
> current word returns.
>
> > a pattern i find myself using repeatedly is a combination of 'dip',
> > 'pair' (to shorten the stack), 'bot' and 'top' (i.e. 'rot' and '-rot'),
> > and 'unpair' (to unpack paired elements.) it's just too painful to
> > try to work with more than four or five stack elements.
>
> Forth doesn't have list manipulations, but if it did most Forthers
> would discourage their use for the purpose of stack manipulations. The
> #1 best way to not suffer the pain of dealing with large numbers of
> stack elements is to design so that you don't need large numbers of
> stack elements :-);
yes, this is the key to working productively in these stack languages.
for some time i've been aware of the very different criteria for naming
code fragments used by programmers working in concatenative and applicative
languages. in an applicative language (at least, the ones i'm familiar with)
there's an implicit rule that you don't abstract to a named subfunction
unless (i) you're going to invoke it from more than one superfunction, and
(ii) the subfunction "merits" a name by "expressing a well-formed thought."
(quotes indicate that these are vague, but meaningful ideas, of the "i don't
know how to define it, but i recognize one when i see it" variety.) in
concatenative languages, these rules are simply too difficult to apply, or
so it seems to me. moreover, you're like to get lots more named fragments
than you will in an applicative language.
after that, use the return stack/queue. I
> personally would prefer the stack manipulation sublanguage (I've
> mentioned it to you before) to using the return stack; it's much more
> self-documenting, and usually faster.
you're referring to shuffle-notation? i've added a version of that
to F, but it's probably too strong for your tastes. :) here's the
relevant section of the document:
Patterns
F incorporates a version of the pattern sublanguage of XY.
A pattern is a list whose head is a scheme and whose tail is a template
A scheme is a name or a list of schemes. The case of the first letter in a name is significant. If lower-case, the name matches a
single element. If upper-case, the name must occur as the final element of a list of schemes, and will match zero or more elements,
viz. the remainder of the list whose initial elements are matched by schemes preceding the terminal name.
A template is a list. If s is a symbol in the template which also occurs in the scheme, the value matched by s is substituted for s
in the template.
F has two operations involving patterns. Both are implemented as commands, rather than primitives.
"S" applies a pattern to the stack and pushes the result onto the stack.
"Q" applies a pattern to the stack and prepends the result to the queue.
Examples:
F>10 20 [[a b]b a] "S"
20 10
F>[2 + 3] [[a b c]a c b] "Q"
5
F>[2 + 3] [[a b c]a c b] "S"
2 3 +
F>10 [20 30 40 50][[a [b c D]]D c b a] "S"
[40 50] 30 20 10
stevan apter — 2006-07-26 21:29:23
>
> F>[2 + 3] [[a b c]a c b] "Q"
that's wrong. should be:
F>[2 + 3] [[[a b c]]a c b] "Q"
> 5
>
> F>[2 + 3] [[a b c]a c b] "S"
ditto:
F>[2 + 3] [[[a b c]]a c b] "S"
> 2 3 +
>
> F>10 [20 30 40 50][[a [b c D]]D c b a] "S"
> [40 50] 30 20 10
>
William Tanksley, Jr — 2006-07-27 03:47:42
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > Forth doesn't have list manipulations, but if it did most Forthers
> > would discourage their use for the purpose of stack manipulations. The
> > #1 best way to not suffer the pain of dealing with large numbers of
> > stack elements is to design so that you don't need large numbers of
> > stack elements :-);
> yes, this is the key to working productively in these stack languages.
Agreed.
I think it's worth noting that it's also a general rule of thumb for
writing efficient code -- don't have your functions consume vast
amounts of disorganized, dynamic data at once, or require deep digging
for data. So it's not just "busywork" to have to clean up your code to
be nice for a concatenative language; in general, it's a good thing
for your code. (There are, of course, exceptions to this rule.)
> for some time i've been aware of the very different criteria for naming
> code fragments used by programmers working in concatenative and applicative
> languages. in an applicative language (at least, the ones i'm familiar with)
> there's an implicit rule that you don't abstract to a named subfunction
> unless (i) you're going to invoke it from more than one superfunction, and
> (ii) the subfunction "merits" a name by "expressing a well-formed thought."
> (quotes indicate that these are vague, but meaningful ideas, of the "i don't
> know how to define it, but i recognize one when i see it" variety.) in
> concatenative languages, these rules are simply too difficult to apply, or
> so it seems to me.
I don't see why rule (i) should be hard to apply; in fact, it can be
easier to find common code, because of the lack of named parameters
makes similar code look similar (similar to the property called
"referential transparency"), and it's possible to "factor out" common
code simply by cutting and pasting (whereas you need a special tool to
extract a method when there are named parameters mixed in with the
code).
Rule (ii) is applicable to both types of languages, though; and I
agree that it's not easy in either.
> moreover, you're like to get lots more named fragments
> than you will in an applicative language.
This is true. One point I'd consider is that stack-based languages
have a very low call overhead, so it's cheap to factor code out. (The
overhead is low because applicative languages, in general, have to
copy every parameter every time any function's called. The only solid
way around that is whole-program optimization.)
> > after that, use the return stack/queue. I
> > personally would prefer the stack manipulation sublanguage (I've
> > mentioned it to you before) to using the return stack; it's much more
> > self-documenting, and usually faster.
> you're referring to shuffle-notation? i've added a version of that
> to F, but it's probably too strong for your tastes. :) here's the
> relevant section of the document:
Grin. You know my taste well. I'm a connoisseur of fine whines.
> Patterns
> F incorporates a version of the pattern sublanguage of XY.
> A pattern is a list whose head is a scheme and whose tail is a template
(Clipped.)
Looks nice to me. Like you said, a little rich, but not without a
pleasant aftertaste.
-Billy
stevan apter — 2006-07-27 11:19:49
>
> > moreover, you're like to get lots more named fragments
> > than you will in an applicative language.
>
> This is true. One point I'd consider is that stack-based languages
> have a very low call overhead, so it's cheap to factor code out. (The
> overhead is low because applicative languages, in general, have to
> copy every parameter every time any function's called. The only solid
> way around that is whole-program optimization.)
this isn't true. e.g. k doesn't copy on call. it creates a pointer
and bumps the reference count.
anyway, the reason named fragments proliferate at a faster rate
in cl's is that you spend more code moving things into position
on the stack in order to do meaningful work, and factoring
will apply to both types of code. for example, the code to
take X Y Z W to W Z X Y so that 'foo' can evaluate properly
is, from the point of view of factoring, equivalent to 'foo'
itself, whereas in an applicative language, you just call 'foo'
with 'foo[W;Z;X;Y]'. W, X, Y, and Z aren't ordered until you
lock them into place in a call.
William Tanksley, Jr — 2006-07-27 13:29:21
stevan apter <
sa@...> wrote:
> > > moreover, you're like to get lots more named fragments
> > > than you will in an applicative language.
> > This is true. One point I'd consider is that stack-based languages
> > have a very low call overhead, so it's cheap to factor code out. (The
> > overhead is low because applicative languages, in general, have to
> > copy every parameter every time any function's called. The only solid
> > way around that is whole-program optimization.)
> this isn't true. e.g. k doesn't copy on call. it creates a pointer
> and bumps the reference count.
It's still true -- you still have to build the stack frame and copy
*something* into it. You actually have to do a little more than I
mentioned, since you additionally have to access a reference counter
in memory.
> anyway, the reason named fragments proliferate at a faster rate
> in cl's is that you spend more code moving things into position
> on the stack in order to do meaningful work, and factoring
> will apply to both types of code. for example, the code to
> take X Y Z W to W Z X Y so that 'foo' can evaluate properly
> is, from the point of view of factoring, equivalent to 'foo'
> itself, whereas in an applicative language, you just call 'foo'
> with 'foo[W;Z;X;Y]'. W, X, Y, and Z aren't ordered until you
> lock them into place in a call.
That's certainly another reason why named fragments would proliferate,
yes. (For all the good and bad that your point implies!) I will add
that most people don't write _many_ stack shufflings as definitions of
their own -- it happens, but not commonly. Perhaps a reason for that
is that if you perform a stack manipulation twice, it's a clue that
you need to rethink your stack order.
This is IMO a great reason to have a simple, clear stack manipulation
lexer, with a syntax designed so that each stack manipulator can be
read as a gestalt and so that stack manipulations aren't easy to
confuse with other code. This is one problem I've had with many of the
stack shuffle parsers people have suggested -- they look like
quotations, or they look like strings.
My suggestion is to build a stack op compiler into the language's lexer.
-Billy
sa@dfa.com — 2006-07-27 13:58:39
concatenative@yahoogroups.com wrote on 07/27/2006 09:29:21 AM:
> stevan apter <sa@...> wrote:
> > > > moreover, you're like to get lots more named fragments
> > > > than you will in an applicative language.
> > > This is true. One point I'd consider is that stack-based languages
> > > have a very low call overhead, so it's cheap to factor code out. (The
> > > overhead is low because applicative languages, in general, have to
> > > copy every parameter every time any function's called. The only solid
> > > way around that is whole-program optimization.)
>
> > this isn't true. e.g. k doesn't copy on call. it creates a pointer
> > and bumps the reference count.
>
> It's still true -- you still have to build the stack frame and copy
> *something* into it. You actually have to do a little more than I
> mentioned, since you additionally have to access a reference counter
> in memory.
>
> > anyway, the reason named fragments proliferate at a faster rate
> > in cl's is that you spend more code moving things into position
> > on the stack in order to do meaningful work, and factoring
> > will apply to both types of code. for example, the code to
> > take X Y Z W to W Z X Y so that 'foo' can evaluate properly
> > is, from the point of view of factoring, equivalent to 'foo'
> > itself, whereas in an applicative language, you just call 'foo'
> > with 'foo[W;Z;X;Y]'. W, X, Y, and Z aren't ordered until you
> > lock them into place in a call.
>
> That's certainly another reason why named fragments would proliferate,
> yes. (For all the good and bad that your point implies!) I will add
> that most people don't write _many_ stack shufflings as definitions of
> their own -- it happens, but not commonly. Perhaps a reason for that
> is that if you perform a stack manipulation twice, it's a clue that
> you need to rethink your stack order.
>
> This is IMO a great reason to have a simple, clear stack manipulation
> lexer, with a syntax designed so that each stack manipulator can be
> read as a gestalt and so that stack manipulations aren't easy to
> confuse with other code. This is one problem I've had with many of the
> stack shuffle parsers people have suggested -- they look like
> quotations, or they look like strings.
>
> My suggestion is to build a stack op compiler into the language's lexer.
so e.g. you would want something like
ab--ba ...
where x--y means "match x, reorder to y"?
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
William Tanksley, Jr — 2006-07-28 01:27:32
sa@... <
sa@...> wrote:
> so e.g. you would want something like
> ab--ba ...
> where x--y means "match x, reorder to y"?
Exactly. So ab--ba is "swap".
I do like your pattern language's power (truly!), but I find its
spaciness a little less readable.
-Billy
stevan apter — 2006-07-28 16:16:43
i like the leaner notation as well. in practice, you'll
be using shuffles more often than patterns. so i've
implemented the simpler form as a (hitherto illegal)
symbol-form, viz.
F>10 20 ab:ba
20 10
with shuffles and patterns, several operators become
redundant, viz. pop, dup, swap, cons, and uncons. a
significant fork, so i've produced a version of F
with the primitives remapped (and the pattern operators
integrated into the language itself).
F is still here:
http://www.nsl.com/k/f/f.htm
and the variant, F_, here:
http://www.nsl.com/k/f_/f.htm
shuffles are atomic, and this has consequences for
expressivity. so e.g.
J>10 20 30 40 swap pop swap dup
10 40 20 20
J>
J>10 20 30 40 abcd:adbb
10 40 20 20
J>
we can do things with the quotation
[swap pop swap dup]
we can't do with the shuffle
abcd:adbb
viz. program-transformation.
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, July 27, 2006 9:27 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> sa@... <sa@...> wrote:
> > so e.g. you would want something like
> > ab--ba ...
> > where x--y means "match x, reorder to y"?
>
> Exactly. So ab--ba is "swap".
>
> I do like your pattern language's power (truly!), but I find its
> spaciness a little less readable.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
stevan apter — 2006-07-28 16:49:34
and of course we can do things with patterns we
can't do with either.
a pattern is a quotation which is a diagram of
the stack or queue in the 'before' state and
the stack or queue in the 'after' state. so we
can write pattern-combinators which transform
patterns into patterns. but we can't write
shuffle-combinators, and we can't decode the
before and after states of a general quotation.
----- Original Message -----
From: "stevan apter" <sa@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, July 28, 2006 12:16 PM
Subject: Re: [stack] Re: 'stack' and 'unstack' in F
> i like the leaner notation as well. in practice, you'll
> be using shuffles more often than patterns. so i've
> implemented the simpler form as a (hitherto illegal)
> symbol-form, viz.
>
> F>10 20 ab:ba
> 20 10
>
> with shuffles and patterns, several operators become
> redundant, viz. pop, dup, swap, cons, and uncons. a
> significant fork, so i've produced a version of F
> with the primitives remapped (and the pattern operators
> integrated into the language itself).
>
> F is still here:
>
> http://www.nsl.com/k/f/f.htm
>
> and the variant, F_, here:
>
> http://www.nsl.com/k/f_/f.htm
>
> shuffles are atomic, and this has consequences for
> expressivity. so e.g.
>
> J>10 20 30 40 swap pop swap dup
> 10 40 20 20
> J>
>
> J>10 20 30 40 abcd:adbb
> 10 40 20 20
> J>
>
> we can do things with the quotation
>
> [swap pop swap dup]
>
> we can't do with the shuffle
>
> abcd:adbb
>
> viz. program-transformation.
>
> ----- Original Message -----
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> To: <concatenative@yahoogroups.com>
> Sent: Thursday, July 27, 2006 9:27 PM
> Subject: Re: [stack] Re: 'stack' and 'unstack' in F
>
>
> > sa@... <sa@...> wrote:
> > > so e.g. you would want something like
> > > ab--ba ...
> > > where x--y means "match x, reorder to y"?
> >
> > Exactly. So ab--ba is "swap".
> >
> > I do like your pattern language's power (truly!), but I find its
> > spaciness a little less readable.
> >
> > -Billy
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
sa@dfa.com — 2006-07-31 12:58:17
from the F doc:
Patterns and Shuffles
F incorporates a version of the pattern sublanguage of XY.
A pattern is a list whose head is a scheme and whose tail is a template
A scheme is a name or a list of schemes. The case of the first letter in a
name is significant. If lower-case, the name matches a single element. If
upper-case, the name must occur as the final element in a list of schemes,
and will match zero or more elements, viz. the remainder of the list whose
initial elements are matched by schemes preceding the terminal name.
A template is a list. If s is a symbol in the template which also occurs in
the scheme, the value matched by s is substituted for s in the template.
F contains four primitive operations on patterns.
) applies a pattern to the stack and pushes the result onto the
stack.
( applies a pattern to the stack and prepends the result to the
queue.
} applies a pattern to the queue and pushes the result onto the
stack.
{ applies a pattern to the queue and prepends the result to the
queue.
As an example of how patterns can simplify programming in F, compare the
definition of cond as given in the prelude:
[pair![dupd!]dip!quote!!dip!swap!false!pair!index!!] cond
with an equivalent definition using the stack-to-pattern operator (:
[[[d i t f]d[[t f]]d i!false!join!index!!](] pcond
pcond expects a data-item d, a condition i of d, a program t to evaluate on
d if d i is true (i.e. not false), and a program f to evaluate on d if d i
is false.
The template evaluates the condition and uses the result to index out the
appropriate program, which is then evaluated on the data-item.
The pattern version is arguably clearer than the version which makes use of
stack operators. One objection to the use of patterns is that the resulting
programs violate the Concatenativity property: a concatenative program can
be cut into two sub-programs, both of which are concatenative programs, as
long as the cut does not fall within the boundaries of a quotation. For
example, cond can be cut into:
[pair![dupd!]dip!quote!!dip!] acond
[swap!false!pair!index!!] bcond
and then cond can be defined as:
[acond!bcond!] cond
But pcond cannot be cut into smaller programs, because every pattern-based
program has the structure [pattern pattern-operator] and patterns are
quotations. In other words, the meaning of symbols in the pattern-template
depends on the assignments implied by the pattern-scheme.
F also supports shuffle-symbols, a simplified, weaker version of (. For
example, swap is:
F>10 20 ab-ba
20 10
Shuffles can reduce stack-noise, but the resulting programs still have the
Concatenativity property. For example, cond can be defined as:
[ditf-dditf pair!unit!quote!!dip!swap!false!join!index!!] scond
concatenative@yahoogroups.com wrote on 07/27/2006 09:27:32 PM:
> sa@... <sa@...> wrote:
> > so e.g. you would want something like
> > ab--ba ...
> > where x--y means "match x, reorder to y"?
>
> Exactly. So ab--ba is "swap".
>
> I do like your pattern language's power (truly!), but I find its
> spaciness a little less readable.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>