Re: [stack] stack operations vs function transformation
stevan apter — 2005-04-09 15:37:24
From: "stevan apter" <
sa@...>
>
> L, R, and S (used to be X) shift and swap the arguments of a function.
> you can also have D (dup) and P (pop), which operate this way:
>
> let t be the following function of three arguments:
>
> t:{[a;b;c]a+b*c}
>
> D t
> {[a;b]a*b+b} / note that D modifies the function body as well
>
> P t
> {[a;b;c;d]a*b+c}
>
> compare:
>
> 2 5 dup + *
> 20
> D[t]. 2 5
> 20
>
> 2 3 4 5 pop + *
> 14
> P[t]. 2 3 4 5
> 14
C (compose? construct? conjoin?) takes two functions, f of
n arguments and g of m arguments, and returns a function h of
(m+n)-1 arguments. for example,
C[f3;f4] -> {[a;b;c;d;e;f]f3[f4[a;b;c;d];e;f]}
another example, f and g both dyadic:
C[+;*]. 1 2 3 = (1*2)+3 = {[a;b;c]+[*[a;b];c]}
to construct the equivalent of f[g[x;y];h[z;w]], e.g.
(x*y)+(z-w),
L L C[R C[+;*];-]
{[c;d;a;b]{[c;a;b]+[*[a;b];c]}[-[a;b];c;d]}
>
> in http://www.nsl.com/k/f.k
>
> now i wonder whether it is possible to construct a language in which
> the stack is entirely "virtual", and all data-movement is replaced
> by the transformation of functions.
stevan apter — 2005-04-10 14:24:28
From: "William Tanksley, Jr" <
wtanksleyjr@...>
>
> stevan apter <sa@...> wrote:
> > now i wonder whether it is possible to construct a language in which
> > the stack is entirely "virtual", and all data-movement is replaced
> > by the transformation of functions.
>
> Sure, or so I'd think. It seems like an extension of optimization --
> although taken to such an extent that it probably wouldn't be optimal
> anymore.
well, i'm not really thinking about the performance aspect at all.
consider the following set of operators:
X exchange (swap)
L left shift
R right shift
P pop
D dup
C conjoin
I identity
K constant
S substitute
A apply
B X A
U D A
Y self-reference (curry's Y)
Z conditional (if f[x] then g[x] else h[x;...])
this set doesn't pretend to be minimal or complete, or even
particularly well-designed. but here's the factorial, expressed
using only the three primitives ~: (not) * (times) and - (minus):
Y[Z[~:][K[1]]D C[*]X C[B]X[-][1]]5
120
ignore the k syntax. with left-associative sugar:
Y (Z ~: (K 1) (D (C * X (C B (X -) 1))))
in
http://www.nsl.com/k/f.k
>
> -Billy
stevan apter — 2005-04-10 14:34:16
compare with this, in haskell:
s f g x = f x (g x)
k x y = x
b f g x = f (g x)
c f g x = f x g
y f = f (y f)
cond p f g x = if p x then f x else g x
fac = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))
from:
http://www.willamette.edu/~fruehr/haskell/evolution.html
----- Original Message -----
From: "stevan apter" <sa@...>
To: <concatenative@yahoogroups.com>
Sent: Sunday, April 10, 2005 10:24 AM
Subject: Re: [stack] stack operations vs function transformation
>
>
> From: "William Tanksley, Jr" <wtanksleyjr@...>
>
> >
> > stevan apter <sa@...> wrote:
> > > now i wonder whether it is possible to construct a language in which
> > > the stack is entirely "virtual", and all data-movement is replaced
> > > by the transformation of functions.
> >
> > Sure, or so I'd think. It seems like an extension of optimization --
> > although taken to such an extent that it probably wouldn't be optimal
> > anymore.
>
> well, i'm not really thinking about the performance aspect at all.
>
> consider the following set of operators:
>
> X exchange (swap)
> L left shift
> R right shift
> P pop
> D dup
> C conjoin
> I identity
> K constant
> S substitute
> A apply
> B X A
> U D A
> Y self-reference (curry's Y)
> Z conditional (if f[x] then g[x] else h[x;...])
>
> this set doesn't pretend to be minimal or complete, or even
> particularly well-designed. but here's the factorial, expressed
> using only the three primitives ~: (not) * (times) and - (minus):
>
> Y[Z[~:][K[1]]D C[*]X C[B]X[-][1]]5
> 120
>
> ignore the k syntax. with left-associative sugar:
>
> Y (Z ~: (K 1) (D (C * X (C B (X -) 1))))
>
> in http://www.nsl.com/k/f.k
>
>
> >
> > -Billy
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
stevan apter — 2005-04-21 22:10:00
it would be premature to write up my results at this point, but
i've made a start at defining a basis for this language.
for example, the factorial function can be defined as:
`- swap 1 `apply swap <- `* <- dup 1 0 `= apply pop swap => y
`x pushes x onto the stack.
'swap' takes a function with arguments .. a b and swaps
a and b. for example, 2 3 `- swap = 3 2 -.
'dup' takes a function with arguments .. a b, drops b,
and replaces all references to b in the function with a.
for example, 2 `+ dup = 2 2 +.
'pop' takes a function with arguments .. a b and adds
an argument to produce a function with arguments .. a b c.
for example, 2 3 4 `+ pop = 2 3 +.
'apply' is not a primitive (see below.) it takes a function f
and a value v and applies f to v. for example, 2 `+ apply produces
a function which applied to a number adds 2 to it.
'<-' and '->' are left- and right-construction. for example,
`+ `* -> is a function that adds a to the product of b and c,
and `+ `* <- is a function that adds the product of a and b
to c.
'<=' and '=>' are left- and right-conditional. for example,
suppose that the stack is
a b c
and suppose that f and g are functions of a single argument,
and h is a function of three arguments. then, for
`f `g `h =>
if f applied to a is true, then g is applied to a, else h is
applied to a, b, c. and for
`f `g `h <=
if f applied to c is true, then g is applied to c, else h is
applied to a, b, c.
additionally, there are the following combinators:
'left' rotates the argument-list of a function one to the left.
'right' rotates the argument-list of a function one to the right.
'fun' and 'val' are like car and cdr for functions. fun of a
function increases its valence (i.e. arity) by 1, and val of
a function returns the corresponding value. for example,
2 `+ apply fun = +
2 `+ apply val = 2
the following identity holds for all functions f:
`f fun `f val apply = f
with this basis, it is possible to define some of the familiar
combinators (using joy notation for definition, lambda shorthand
to the right):
i == :: identity (::) is the k identity primitive)
k == `i swap constant
j == `k `i -> fun fun a[c][b[d]]
u == `apply dup a[a]
b == `i `i -> fun fun a[b[c]]
e == `b right swap left b[a[c]]
f == `b swap a[c[b]]
s == `j dup a[c][b[c]]
c == `j`i left right swap a[c][b]
y == `c swap`u e `u b y-combinator
apply == `i `i j a[b]
current work in
http://www.nsl.com/k/f.k.
i'm not entirely sure where this work is heading. is it too
opaque to serve as a practical method of programming? i don't
know yet.
onward.
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, April 09, 2005 11:59 AM
Subject: Re: [stack] stack operations vs function transformation
>
> stevan apter <sa@...> wrote:
> > now i wonder whether it is possible to construct a language in which
> > the stack is entirely "virtual", and all data-movement is replaced
> > by the transformation of functions.
>
> Sure, or so I'd think. It seems like an extension of optimization --
> although taken to such an extent that it probably wouldn't be optimal
> anymore.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2005-04-26 08:22:28
On Thu, 21 Apr 2005, stevan apter wrote:
> it would be premature to write up my results at this point, but
> i've made a start at defining a basis for this language.
>
> for example, the factorial function can be defined as:
>
> `- swap 1 `apply swap <- `* <- dup 1 0 `= apply pop swap => y
>
> `x pushes x onto the stack.
>
> 'swap' takes a function with arguments .. a b and swaps
> a and b. for example, 2 3 `- swap = 3 2 -.
Should that be 2 3 `- swap = 3 2 `- (the second - quoted)?
Otherwise it is difficult to get swap as its own inverse:
2 3 `- swap swap = 2 3 `-
or just `- swap swap = `-
or even swap swap = id
But maybe you don't want swap as its own inverse...?
> 'dup' takes a function with arguments .. a b, drops b,
> and replaces all references to b in the function with a.
> for example, 2 `+ dup = 2 2 +.
>
> 'pop' takes a function with arguments .. a b and adds
> an argument to produce a function with arguments .. a b c.
> for example, 2 3 4 `+ pop = 2 3 +.
Similarly here:
2 3 `+ dup pop = 2 3 `+
or just `+ dup pop = `+
or even dup pop = id
The last three remind me of the pre-history of Joy:
I initially thought of swap, dup and pop as simple combinators
which modify the meaning of the part of the program to their right.
Later I changed the prespective - the three modify the
meaning of the part of the program on their left, the part
which builds the stack in readiness for any operators on the
right. It amounts to the same thing, of course, but the
change in perspective was (psychologically) illuminating.
> 'apply' is not a primitive (see below.) it takes a function f
> and a value v and applies f to v. for example, 2 `+ apply produces
> a function which applied to a number adds 2 to it.
>
> '<-' and '->' are left- and right-construction. for example,
> `+ `* -> is a function that adds a to the product of b and c,
> and `+ `* <- is a function that adds the product of a and b
> to c.
>
> '<=' and '=>' are left- and right-conditional. for example,
> suppose that the stack is
>
> a b c
>
> and suppose that f and g are functions of a single argument,
> and h is a function of three arguments. then, for
>
> `f `g `h =>
>
> if f applied to a is true, then g is applied to a, else h is
> applied to a, b, c. and for
>
> `f `g `h <=
>
> if f applied to c is true, then g is applied to c, else h is
> applied to a, b, c.
> additionally, there are the following combinators:
>
> 'left' rotates the argument-list of a function one to the left.
>
> 'right' rotates the argument-list of a function one to the right.
Will this be enough by way of counterparts of stack shufflers?
Won't ou need something that can do the work of dip in Joy?
> 'fun' and 'val' are like car and cdr for functions. fun of a
> function increases its valence (i.e. arity) by 1, and val of
> a function returns the corresponding value. for example,
>
> 2 `+ apply fun = +
> 2 `+ apply val = 2
>
> the following identity holds for all functions f:
>
> `f fun `f val apply = f
>
> with this basis, it is possible to define some of the familiar
> combinators (using joy notation for definition, lambda shorthand
> to the right):
>
> i == :: identity (::) is the k identity primitive)
> k == `i swap constant
> j == `k `i -> fun fun a[c][b[d]]
> u == `apply dup a[a]
> b == `i `i -> fun fun a[b[c]]
> e == `b right swap left b[a[c]]
> f == `b swap a[c[b]]
> s == `j dup a[c][b[c]]
> c == `j`i left right swap a[c][b]
> y == `c swap`u e `u b y-combinator
>
> apply == `i `i j a[b]
Amazing..
> current work in http://www.nsl.com/k/f.k.
>
> i'm not entirely sure where this work is heading. is it too
> opaque to serve as a practical method of programming? i don't
> know yet.
It doesn't matter all that much whether it is a practical method
for programming. There are plenty of very useful virtual machine
languages that one would not want to use to write programs, but which
are excellent for implementing a virtual machine. Three examples:
1) the combinatory abstract machine underlying CAML, and 2)
the combinatory machine underlying (first Miranda, and now) Haskell,
3) Landin's SECD machine for the lambda calculus (or ISWIM, his Lisp).
Joy is rather different in that the language is its own machine
language (At least in its current incarnation).
One final comment. I take it that you don't want to empasise the
(or any) stack, so you don't want to allow
+ + + dup
as a complete program, althought it is in (most?) concatenative
languages - it expects a stack with four numbers and returns a
stack with their sum twice. But keep in mind that even in Joy
at least, the stack is part of the semantics - "programs denote
functions from stacks to stacks". However, it is always possible
in all functional languages to give a purely syntactic rewriting
system, with rules such as
2 3 + ==> 5
2 3 swap ==> 3 2
but no mention of a stack at all. Come to think of it, your
enterprise might be somewhat similar to the lazy implementation
technique of Miranda and Haskell which is based on graph rewriting.
The best reference I know is Peyton-Jones "Implementation of
functional languages" (or something like that).
> onward.
Indeed.
Keep it up.
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-04-28 09:30:21
On Thu, 21 Apr 2005, stevan apter wrote:
{..]
> 'swap' takes a function with arguments .. a b and swaps
> a and b. for example, 2 3 `- swap = 3 2 -.
It occurred to me that one can do something like this in Joy:
DEFINE
SWAP == [swap] swoncat;
DUP == [dup] swoncat;
...
Then
2 3 [-] SWAP i
== 2 3 [swap -] i
== 2 3 swap -
== 3 2 -
== 1
And interestingly, SWAP SWAP == id.
But you need to call the resultant program with the i combinator.
Similarly:
5 [*] DUP i
== 25
[..]
> i'm not entirely sure where this work is heading.
It occurred to me that perhaps you are on the way to re-invent
combinatory logic (that's the SK(I) stuff). Your primitives
seem to follow a linear (concatenative?) syntax, but you may
find that you will need some kind of parentheses to over-ride
the most frequent order of application. I conjecture that your
concatenations A B mostly mean: apply B to A, which could be
written as B@A. Then A B C D would mean D@(C@(B@A)). But there
will be times when one wants (D@C)@(B@A) or even ((D@(C@B)@A.
A purely linear notation cannot do this well. You might find
it useful to write any intended parentheses explicitly:
((A B) C) D
(A B) (C D)
A (B (C D))
But perhaps you are inventing something quite new which is not
just combinatory logic in another notation. Maybe it is a
novel virtual machine language, which may but need not have
a human readable form.
Good luck, whatever. And keep us informed.
- Manfred
stevan apter — 2005-04-28 11:01:32
----- Original Message -----
From: <phimvt@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, April 28, 2005 5:30 AM
Subject: Re: [stack] stack operations vs function transformation
>
> On Thu, 21 Apr 2005, stevan apter wrote:
>
> {..]
>
> > 'swap' takes a function with arguments .. a b and swaps
> > a and b. for example, 2 3 `- swap = 3 2 -.
>
> It occurred to me that one can do something like this in Joy:
> DEFINE
> SWAP == [swap] swoncat;
> DUP == [dup] swoncat;
> ...
> Then
> 2 3 [-] SWAP i
> == 2 3 [swap -] i
> == 2 3 swap -
> == 3 2 -
> == 1
> And interestingly, SWAP SWAP == id.
> But you need to call the resultant program with the i combinator.
>
> Similarly:
> 5 [*] DUP i
> == 25
>
> [..]
>
> > i'm not entirely sure where this work is heading.
>
> It occurred to me that perhaps you are on the way to re-invent
> combinatory logic (that's the SK(I) stuff). Your primitives
> seem to follow a linear (concatenative?) syntax, but you may
> find that you will need some kind of parentheses to over-ride
> the most frequent order of application. I conjecture that your
> concatenations A B mostly mean: apply B to A, which could be
> written as B@A. Then A B C D would mean D@(C@(B@A)). But there
> will be times when one wants (D@C)@(B@A) or even ((D@(C@B)@A.
> A purely linear notation cannot do this well. You might find
> it useful to write any intended parentheses explicitly:
> ((A B) C) D
> (A B) (C D)
> A (B (C D))
>
>
> But perhaps you are inventing something quite new which is not
> just combinatory logic in another notation. Maybe it is a
> novel virtual machine language, which may but need not have
> a human readable form.
thanks very much for your observations manfred.
the linear syntax was produced for the benefit of this mail
group - as you can probably tell from looking at my working
script, the current state of things involves formulating a
set of combinators (or pseudo-combinators) which are useful
and complete for the manipulation of multi-argument lambdas.
i don't actually have a parser/interpreter (yet, if ever)
for anything but native K.
as roger hui confirmed to me in an email, it is possible to
write J entirely in tacit form. and indeed, there is an
algorithm which converts non-tacit J into tacit form. ("tacit
form" is J-speak for variable- or "point-" free programming.)
J uses a non-standard set of combinators - hook, fork, &c.
but J functions are restricted to one or two arguments. so
the analogous problem for K (and for any PL which admits
functions of more than two arguments) is to find a small set
of combinators which permit the perspicuous construction and
transformation of such functions.
a pure K lambda has the form
{[arg-1;..;arg-n] body}[val-1]..[val-m] where 0 <= m < n
where the body consists of a tree whose nodes are in the
argument-list.
e.g.
{[a;b;c;d;e]a[b[c]][d]}[+][!:]
a is +, b is !:, c, d, e are free. the lambda has valence 3;
i.e. it takes three arguments c, d, and e, but uses only c
and d.
i'm trying to find/design a set of combinators which would
allow me to construct functions like this from primitives like
+ and !:, but which possess greater psychological transparency
than e.g. SK(I). my intuition is that such a set will contain
two kinds of combinators: one kind, for manipulating the
order and number of arguments, and another, for constructing
the branches of the implied parse-trees. (and an application
primitive, which applies a function of n arguments to a value
to produce a function of n-1 arguments.)
developing ..
>
> Good luck, whatever. And keep us informed.
>
> - Manfred
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2005-05-13 07:53:41
On Thu, 28 Apr 2005, stevan apter wrote:
>
> ----- Original Message -----
> From: <phimvt@...>
> To: <concatenative@yahoogroups.com>
> Sent: Thursday, April 28, 2005 5:30 AM
> Subject: Re: [stack] stack operations vs function transformation
> > On Thu, 21 Apr 2005, stevan apter wrote:
[..]
> the linear syntax was produced for the benefit of this mail
> group - as you can probably tell from looking at my working
> script, the current state of things involves formulating a
> set of combinators (or pseudo-combinators) which are useful
> and complete for the manipulation of multi-argument lambdas.
> i don't actually have a parser/interpreter (yet, if ever)
> for anything but native K.
I read your post when it first came out, and I have been
stewing over the expression "linear syntax" for a while now.
Possibly I am reading things into it that you did not intend,
But here it goes:
In almost all languages expressions can be nested; in the procedural
languages statements can be also be nested in conditionals and loops.
Forth also allows nesting of conditionals and loops, and Joy allows
nesting of quotations, typically for use by combinators. Can we do without
any nesting at all?
Let us say a concatenative language is FLAT if it does not allow (or does
not need) nesting. This is a purely syntactic concept, and ordinary
recursion does not count as nesting in this sense, although it
involves a nesting in execution.
For Joy this would elminate all the recursive combinators, but
one can always use ordinary recursion of course. What else is
eliminated?
I can see two problems that arise: how to deal with stack manipulation
deep in the stack, and how to deal with conditionals. In Joy the dip
combinator, possibly itself nested, handles deep stack manipulation,
whereas in Forth the same effect is achieved by saving to and restoring
from the return stack. In Forth and Joy conditionals, of slightly
different kinds, are absolutely essential, including for use in recursive
definitions. So, what could a flat concatenative language look like?
For deep stack manipulation there is the Forth solution of using an
auxiliary stack. Another solution has sometimes been proposed on this
group: indexing into the stack, something along these lines: if N is on
top of the stack, then the "fetch" operator will move the N-th item below
the N to the top of the stack, and a corresponding "store" operation can
do the reverse. A few other operators of this kind may also be needed.
For conditionals there is a machine language solution: indexing into
the code for the program counter PC. If N is on top of the stack,
GOTO the instruction N above or below, depending on the sign of N.
This even allows a computed GOTO, if N was computed by some previous
calculation. To get the effect of conditionals, a variant is needed
that looks at item below the N and only jumps if that item is true
or is to be interpreted as such.
So, a rather low level flat concatenative machine language can
probably defined; assembly language programmer will have to
refine what I said. Possibly all of what I said can already be done
in Forth. The fact that it is so low level and unstructured with
the GOTOs is not necessarily fatal - its main interest could be
as an implementation language for a higher level form.
So, this is what I came up with while mullinng over the notion
of "linear syntax" - an I realise it might have nothing to do
with what you had in mind. But reading the latter part of
your post again leads me to think that I am not too far off.
[..]
> i'm trying to find/design a set of combinators which would
> allow me to construct functions like this from primitives like
> + and !:, but which possess greater psychological transparency
> than e.g. SK(I). my intuition is that such a set will contain
> two kinds of combinators: one kind, for manipulating the
> order and number of arguments, and another, for constructing
> the branches of the implied parse-trees. (and an application
> primitive, which applies a function of n arguments to a value
> to produce a function of n-1 arguments.)
Take the (quoted) function [* *] which multiplies three numbers. Then
give it one number, say 5, to produce a (quoted) function of two numbers.
Easy:
[* *] 5 swons ==> [5 * *]
or 5 [* *] cons ==> [5 * *]
Notice there is no application, just a sw/c-onsing - a simple form of
concatenation. But maybe you did not want quotationns at all. (Of course
the quotation may be invisible to the user.)
If the next argument is 4, one would write
[* *] 5 swons 4 swons ==> either [4 5 * *] or [20 *]
possibly by calling the operator "apply" rather than "swons",
especially if the first multiplication is to be done as soon as
possible, to give 20.
Must fly ..
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-05-18 07:20:22
I have been working more on various reproducing programs in Joy, quite
different from the infinite ("lazy") lists. Most of them do something
apart from reproducing, some of them even do something useful like
sorting, either just that, or with a call count, or with some trace. You
might like to look at the new paper:
http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-survrep.joy
EnJoy
- Manfred
William Tanksley, Jr — 2005-05-18 15:54:18
phimvt@... <
phimvt@...> wrote:
> In almost all languages expressions can be nested; in the procedural
> languages statements can be also be nested in conditionals and loops.
> Forth also allows nesting of conditionals and loops, and Joy allows
> nesting of quotations, typically for use by combinators. Can we do without
> any nesting at all?
> Let us say a concatenative language is FLAT if it does not allow (or does
> not need) nesting. This is a purely syntactic concept, and ordinary
> recursion does not count as nesting in this sense, although it
> involves a nesting in execution.
I would say that Forth could be made ALMOST flat by defining all the
if and loop operators to take addresses (rather than using the current
nested definitions), and using ' (the "address of" operator) to take
the address of existing words. The result would look something like
Joy, except that where Joy would use a quotation, flatForth would take
the address of a named definition (the body of which is, of course,
elsewhere).
Examples:
Joy:
x == [10 +] swap if.
Forth:
: x IF 10 + THEN ;
flatForth:
: addTen 10 + ;
: x ' addTen if ;
This is not quite completely flat. The problem is in the ' word (and
the : word): those words form a kind of syntax which, although much
more limited than quotations or blocks, nonetheless violate the
perfect flatness. They could be replaced by lexical syntax, of course;
'addTen could be handled by the lexer to mean the address of the
defined word, and :addTen could likewise be handled by the lexer to
start a definition. Chuck Moore's colorForth works very much this way
(although it still uses if blocks).
> For Joy this would elminate all the recursive combinators, but
> one can always use ordinary recursion of course. What else is
> eliminated?
If you allow taking the address of words (which, as I said, is a
slight violation of flatness), you're okay with keeping the
combinators.
> For conditionals there is a machine language solution: indexing into
> the code for the program counter PC. If N is on top of the stack,
> GOTO the instruction N above or below, depending on the sign of N.
> This even allows a computed GOTO, if N was computed by some previous
> calculation. To get the effect of conditionals, a variant is needed
> that looks at item below the N and only jumps if that item is true
> or is to be interpreted as such.
Good point. Conditional returns could also replace IFs in much the
same manner. I'm not sure that either one is purely flat, though; both
cause the semantics of the language to depend very much on the block
structure of the code. Numeric GOTOs (really JMPs) depend on the
current definition extending to the location being jumped to, and
conditional returns cause the rest of the current definition to not be
executed. Both break concatenative properties.
> - Manfred
-Billy
phimvt@lurac.latrobe.edu.au — 2005-05-20 08:29:07
On Wed, 18 May 2005, William Tanksley, Jr wrote:
> phimvt@... <phimvt@...> wrote:
> > In almost all languages expressions can be nested; in the procedural
> > languages statements can be also be nested in conditionals and loops.
> > Forth also allows nesting of conditionals and loops, and Joy allows
> > nesting of quotations, typically for use by combinators. Can we do without
> > any nesting at all?
>
> > Let us say a concatenative language is FLAT if it does not allow (or does
> > not need) nesting. This is a purely syntactic concept, and ordinary
> > recursion does not count as nesting in this sense, although it
> > involves a nesting in execution.
>
> I would say that Forth could be made ALMOST flat by defining all the
> if and loop operators to take addresses (rather than using the current
> nested definitions), and using ' (the "address of" operator) to take
> the address of existing words. The result would look something like
> Joy, except that where Joy would use a quotation, flatForth would take
> the address of a named definition (the body of which is, of course,
> elsewhere).
Yes, I thought that what I was talking about was not too far from
being part of Forth already. I do not agree, though, that flatForth
would have to take the address of a named definition to get the effect
of Joy quotation. I tink it ought to be possible to do without naming
the particular piece of code for the quotation.
> Examples:
>
> Joy:
> x == [10 +] swap if.
> Forth:
> : x IF 10 + THEN ;
> flatForth:
> : addTen 10 + ;
> : x ' addTen if ;
Maybe I don't quite understand the example, so I'll try something
different. Suppose we have a number on top of the stack, and
if it is less than 10 we want to square it, otherwise we want
to multiply it by 7.
In Joy: ... [10 <] [dup *] [7 *] ifte ...
In FlatL: writing over several lines
...
10
<
4 # 4 steps to be jumped
IF-FALSE-JUMP(FORWARD) # to the 7
dup
*
2 # 2 steps to be jumped
JUMP(FORWARD) # to the ...
7
*
...
You can probably tell that I have never written an Assembly program,
but I have written toy compilers that do this sort of thing.
> This is not quite completely flat. The problem is in the ' word (and
> the : word): those words form a kind of syntax which, although much
> more limited than quotations or blocks, nonetheless violate the
> perfect flatness. They could be replaced by lexical syntax, of course;
> 'addTen could be handled by the lexer to mean the address of the
> defined word, and :addTen could likewise be handled by the lexer to
> start a definition. Chuck Moore's colorForth works very much this way
> (although it still uses if blocks).
I don't see using a defined word as breaking flatness:
DEFINE square == dup *.
2 3 + square 10 *. ==> 50
I think a definition should be seen as extending the language
as if square were a primitive - just like dup.
> > For Joy this would elminate all the recursive combinators, but
> > one can always use ordinary recursion of course. What else is
> > eliminated?
>
> If you allow taking the address of words (which, as I said, is a
> slight violation of flatness), you're okay with keeping the
> combinators.
I would try to put the equivalent of a quotation not into a defined
word but exactly where it is to be used. Maybe jump arount it
to get to the combinator which could be primitive or defined,
and make the combinator execute the counterpart of the quotation
as often as needed.
> > For conditionals there is a machine language solution: indexing into
> > the code for the program counter PC. If N is on top of the stack,
> > GOTO the instruction N above or below, depending on the sign of N.
> > This even allows a computed GOTO, if N was computed by some previous
> > calculation. To get the effect of conditionals, a variant is needed
> > that looks at item below the N and only jumps if that item is true
> > or is to be interpreted as such.
>
> Good point. Conditional returns could also replace IFs in much the
> same manner. I'm not sure that either one is purely flat, though; both
> cause the semantics of the language to depend very much on the block
> structure of the code. Numeric GOTOs (really JMPs) depend on the
> current definition extending to the location being jumped to, and
> conditional returns cause the rest of the current definition to not be
> executed. Both break concatenative properties.
Yes, I should be more precise with my GOTOs/JUMPs. How is this:
All jumps must stay inside the current definition, or inside the
(anonymous) main currently executed. So no evil jumps into procedures,
and not even the more modest GOTOs allowed by Pascal (jump into
an enclosing procedure).
Thanks
- Manfred
William Tanksley, Jr — 2005-05-20 17:58:51
phimvt@... <
phimvt@...> wrote:
> On Wed, 18 May 2005, William Tanksley, Jr wrote:
> > phimvt@... <phimvt@...> wrote:
> > > In almost all languages expressions can be nested; in the procedural
> > > languages statements can be also be nested in conditionals and loops.
> > > Forth also allows nesting of conditionals and loops, and Joy allows
> > > nesting of quotations, typically for use by combinators. Can we do without
> > > any nesting at all?
> > > Let us say a concatenative language is FLAT if it does not allow (or does
> > > not need) nesting. This is a purely syntactic concept, and ordinary
> > > recursion does not count as nesting in this sense, although it
> > > involves a nesting in execution.
> > I would say that Forth could be made ALMOST flat by defining all the
> > if and loop operators to take addresses (rather than using the current
> > nested definitions), and using ' (the "address of" operator) to take
> > the address of existing words. The result would look something like
> > Joy, except that where Joy would use a quotation, flatForth would take
> > the address of a named definition (the body of which is, of course,
> > elsewhere).
> Yes, I thought that what I was talking about was not too far from
> being part of Forth already. I do not agree, though, that flatForth
> would have to take the address of a named definition to get the effect
> of Joy quotation. I tink it ought to be possible to do without naming
> the particular piece of code for the quotation.
I agree with that, although I don't agree that it's fully flat either.
I was offering not a contradiction of your solution, but an alternate
way of doing things. I don't see any unbreakable advantages to doing
things one way or the other -- except that by using named definitions
you can write almost exactly Joy code (except that the
pseudoquotations are immutable). Using JMPs you have to do more
calculation, and in addition I would claim that your code is less
flat.
I'll explain why it's less flat below; first let me explain flatness
as I see it. Let me know if I'm totally misunderstanding, since you're
the first one to use the word "flat" in this context, and you
therefore have the right to define it.
Flat: Flatness is the absence of all syntactic (compile-time) nesting.
A test for flatness: a definition is flat if and only if it can be cut
apart into two valid definitions on any blank space. A definition is
partially flat to the extent that it can be so cut. This could be
expressed numericly, by dividing the number of cuttable spaces by the
total number of spaces.
(Some languages may make spaces implicit. You know what I mean -- any
joint between words counts as a space.) For the sake of this example,
I don't count spaces that are part of word definition syntax, because
we're not comparing the definition syntax of the languages. If I were
doing language design, I would count everything. Also for the sake of
this example, I use the same definition syntax for all the languages.
Quotation markers count as words. Thus, [ 10 + ] has 3 internal
spaces, and [ [ 10 + ] 3 - ] has 7 internal spaces. The word being
defined is written with a preceding colon, and counts as only one word
(the colon isn't counted; this is like Colorforth). The trailing
semicolon is counted as a word.
So in ColorJoy,
:x [ 10 + ] swap if ;
flatness = 4/7 ~ 0.571.
In ColorForth (adjusting the stack a bit to make things fair --
Forth's if is different from Joy's):
:x swap if 10 + then ;
flatness = 3/6 = 0.500.
In flatForth (using Joy's if):
:addTen 10 + ;
:x ' addTen swap if ;
flatness = 8/9 ~ 0.888. (The only non-flat part is the joint between '
and addTen.)
In JumpFor(th)Joy:
:x swap 2 ?IF 10 + ;
flatness = 4/6 ~ 0.666. (Everything after the ?IF is non-flat, because
you can't textually split the definition on either of those spaces
without making one of the resulting functions invalid.)
> Maybe I don't quite understand the example, so I'll try something
> different. Suppose we have a number on top of the stack, and
> if it is less than 10 we want to square it, otherwise we want
> to multiply it by 7.
So to go through all your examples again:
ColorJoy:
:x [ 10 < ] [ dup * ] [ 7 * ] ifte ;
flatness = 5/14 ~ .357
ColorFlatForth:
:timesSeven 7 * ;
:squared dup * ;
:x ' addTen swap ifelse ;
flatness = 12/13 ~ 0.923
ColorJumpForJoy: :x 10 < 2 ?IF=>ELSE dup * 2 ?ELSE 7 * ;
flatness = 7/11 ~ 0.636
Ah, I think I finally managed to come up with fair numbers.
> You can probably tell that I have never written an Assembly program,
> but I have written toy compilers that do this sort of thing.
:-)
> > This is not quite completely flat. The problem is in the ' word (and
> > the : word): those words form a kind of syntax which, although much
> > more limited than quotations or blocks, nonetheless violate the
> > perfect flatness. They could be replaced by lexical syntax, of course;
> > 'addTen could be handled by the lexer to mean the address of the
> > defined word, and :addTen could likewise be handled by the lexer to
> > start a definition. Chuck Moore's colorForth works very much this way
> > (although it still uses if blocks).
> I don't see using a defined word as breaking flatness:
No, that's not what I meant -- what breaks flatness for flatForth is
the fact that the ' operator is syntactically tied to the word that
appears after it in the source.
> DEFINE square == dup *.
> 2 3 + square 10 *. ==> 50
> I think a definition should be seen as extending the language
> as if square were a primitive - just like dup.
Right.
Although to be perfectly formal, definitions themselves aren't flat --
you can't split a program containing a definition in half and wind up
with two valid programs.
colorForth gets around this in a facinating way -- rather than keeping
state that says "I am currently in the middle of a definition", in
colorForth every word has its own color (or emphasis, or font, or
whatever you want -- but Chuck happens to use color). A green word
gets compiled, a purple word is a dynamic value (it gets updated in
the editor while the program runs), a white word is a comment, a
yellow word gets executed, and a red word defines a new name in the
dictionary. You can therefore split a definition in half at any space,
and so long as you run the two programs one after the other, all will
be well. (Of course, if you try to run the second one first, you'll
probably get undefined words.)
But for normal use, we choose to consider flatness within definitions,
rather than flatness within entire programs. I think this is
praiseworthy; structured programming is a good thing, and structures
are by definition not flat.
> > > For Joy this would elminate all the recursive combinators, but
> > > one can always use ordinary recursion of course. What else is
> > > eliminated?
> > If you allow taking the address of words (which, as I said, is a
> > slight violation of flatness), you're okay with keeping the
> > combinators.
> I would try to put the equivalent of a quotation not into a defined
> word but exactly where it is to be used.
Understandable. I would try to put it *near* to where it's used. At
the same time, it's also truly important to me to keep the complexity
of each word low, and it's undeniable that nesting quotations (or
anything else) raises complexity.
> Maybe jump arount it
> to get to the combinator which could be primitive or defined,
> and make the combinator execute the counterpart of the quotation
> as often as needed.
I know, but that unavoidably banishes flatness.
> - Manfred
-Billy
wtanksle — 2005-06-15 16:59:08
"William Tanksley, Jr" <wtanksleyjr@g...> wrote:
>Flat: Flatness is the absence of all syntactic (compile-time)
>nesting.
>A test for flatness: a definition is flat if and only if it can
>be cut apart into two valid definitions on any blank space. A
>definition is partially flat to the extent that it can be so
>cut. This could be expressed numericly, by dividing the number
>of cuttable spaces by the total number of spaces.
I don't know whether my definition matches how other people were using
the word, but I just realised that the perfect way to produce flatness
is with a lazy concatenative language. Because the language is lazy,
you don't need ifs; you just need a conditional drop. All of the
syntax can become just ordinary words; even quotations marks [ and ]
would just lazily group words that appeared at the same runtime level
of nesting.
Of course, the result could sometimes be odd-looking... Imagine this:
: b 2 / ] ;
: a [ 10 ;
a b i .
=> 5
I'll let you think about that...
-Billy
sa@dfa.com — 2005-06-16 18:23:09
concatenative@yahoogroups.com wrote on 06/15/2005 12:59:08 PM:
> "William Tanksley, Jr" <wtanksleyjr@g...> wrote:
> >Flat: Flatness is the absence of all syntactic (compile-time)
> >nesting.
>
> >A test for flatness: a definition is flat if and only if it can
> >be cut apart into two valid definitions on any blank space. A
> >definition is partially flat to the extent that it can be so
> >cut. This could be expressed numericly, by dividing the number
> >of cuttable spaces by the total number of spaces.
>
> I don't know whether my definition matches how other people were using
> the word, but I just realised that the perfect way to produce flatness
> is with a lazy concatenative language. Because the language is lazy,
> you don't need ifs; you just need a conditional drop. All of the
> syntax can become just ordinary words; even quotations marks [ and ]
> would just lazily group words that appeared at the same runtime level
> of nesting.
>
> Of course, the result could sometimes be odd-looking... Imagine this:
>
> : b 2 / ] ;
> : a [ 10 ;
> a b i .
> => 5
>
> I'll let you think about that...
a small XYish interpreter, with a queue and stack:
store a and b as tokenized strings, viz.
2 / ]
[ 10
now interpret as follows:
a -> append val(a) to the queue = [ 10
b -> append val(b) to the queue = [ 10 2 / ]
i -> append i to the queue = [ 10 2 / ] i
now evaluate as usual ..
>
> -Billy
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2005-07-13 05:59:14
While I was away I have been thinking about flatness, macros(or other
definitions), and concatenative semantics.
In what follows, by "standard languages" I mean the usual programming
languages but excluding any in which programs are given in some graphical
or other uncommon format. I mention three levels of concatenation:
(1) of characters, (2) of symbols, (3) of factors as in Joy and Forth.
1. In all standard languages a program is a sequence of characters or
bytes, including spaces and newlines. (I ignore another variant in which
a program is a sequence of lines, where a line is a sequence of
characters). For any such language it is possible to define macros
(with or without parameters) whose bodies are sequences of characters.
Here is an example, only slightly insane, of a parameterless macro
definiton and its use:
#I "up *] m" (* definition of macro I,
indicated by #, say, body in double quotes *)
[1 2 3 4] [d%Iap (* use of macro I, indicated by %, say *)
[1 2 3 4] [dup *] map (* macro I has been expanded *)
=> [1 4 9 16] (* result after execution *)
The point of the insane example is that such character macros need not
respect any higher syntax rules. In some sense the language of
concatenated sequences of character is completely flat. But it is not a
concatenative language because concatenation of characters does not map
onto composition of functions - characters do not denote functions.
2. In all standard languages a program is a sequence of symbols, where
a symbol is a sequence of printing characters separated by whitespace
characters (or other devices such as change of character class).
For any such language it is possible to define macros (with or without
parameters) whose bodies are sequences of symbols. As an example I'll
use one put forward by Billy:
On Wed, 15 Jun 2005, wtanksley wrote:
[..]
> Of course, the result could sometimes be odd-looking... Imagine this:
>
> : b 2 / ] ;
> : a [ 10 ;
> a b i .
> => 5
I welcome that it is so odd-looking, exactly the sort of example I want.
It so happens that most of the symbols in the example happen to be
single character symbols. So, to drive home the point that the body
of the definition is a sequence of symbols here is another in the same
spirit:
: b * ] map ;
: a [ dup ;
[1 2 3 4] a b .
=> [1 4 9 16]
Again a sequence of symbols is completely flat, just as in the earlier
case, but it assumes that the symbols have been read by the scanner
or tokeniser of the language (Joy in this case), but not by the parser.
The macros do not have to respect the syntax of the language, in both
examples the macros do not respect the special roles of [ and ].
Hence we cannot say that the concatenation of symbols maps onto the
composition of functions which the symbols denote: some symbols,
[ and ] in particular, or IF and THEN in Forth, do not denote functions.
3. In Joy and Forth we have something like the following grammar:
a) The body of a definition is a term.
b) A term is a sequence of factors
c) A factor is either atomic ( 42 + <= first map ... )
or it is a term enclosed in [ and ] ( Joy )
or it is a term enclosed in IF and THEN ( Forth )
Because of a), the body of a definition has to go through the parser
and not just through the scannner. Consequently the two previous macros
are not acceptable definitions, even less so the first character macro.
But of course we can have legal definitions such as
DEFINE
a == dup * ;
b == [a] map.
[1 2 3 4] a b.
=> [1 4 9 16]
A language that obeys a recursive grammar such as the above appears to
be irreducibly non-flat, but it can have a concatenative semantics:
concatenation of terms maps onto composition of functions. I have
tried to give a concatenative sematics to some flat version of Joy,
but either it fails to have a concatenative semantics (like (2) above),
or it fails to be flat (like (3) above). My guess is that flatness
and concatenative semantics are incompatible in the case of Joy.
I am less certain about this conjecture in the case of Forth.
It would be interesting to see that my conjecture is false. In
particular, I am intrigued by what Billy also said:
> I don't know whether my definition matches how other people were using
> the word, but I just realised that the perfect way to produce flatness
> is with a lazy concatenative language. Because the language is lazy,
> you don't need ifs; you just need a conditional drop. All of the
^^^ ^^^^^^^^^^^^^^^^
> syntax can become just ordinary words; even quotations marks [ and ]
> would just lazily group words that appeared at the same runtime level
> of nesting.
I don't really understand what you meant about the ifs and conditional
drops, or how laziless makes flatness and concatenativve semantics
compatible. Could you elaborate, please?
- Manfred
Ivan Tomac — 2005-07-14 02:06:00
--- In
concatenative@yahoogroups.com, phimvt@l... wrote:
> > I don't know whether my definition matches how other people were
using
> > the word, but I just realised that the perfect way to produce
flatness
> > is with a lazy concatenative language. Because the language is
lazy,
> > you don't need ifs; you just need a conditional drop. All of the
> ^^^ ^^^^^^^^^^^^^^^^
> > syntax can become just ordinary words; even quotations marks [
and ]
> > would just lazily group words that appeared at the same runtime
level
> > of nesting.
>
> I don't really understand what you meant about the ifs and
conditional
> drops, or how laziless makes flatness and concatenativve semantics
> compatible. Could you elaborate, please?
>
Consider the following Joy program:
LIBRA
cpop == [pop] [] branch .
cpop is the conditional drop operator I suspect Billy was talking
about.
Essentially what it does is, given a boolean value, it will either not
do anything (if it's false) or it will drop the element on top of the
stack (if the value is true). For example:
[1] [pop 2] true cpop i put .
Laziness is required to delay the execution of [1] and [pop 2]
otherwise the cpop operator couldn't simulate an if operator.
I think I should add that it's not enough for the language to be lazy
for this to work - the language also needs to allow variable stack
effects.
In other words if there were n elements on stack prior to execution of
cpop, there will either be n or n-1 elements upon it's completion.
> - Manfred
Ivan
Ivan Tomac — 2005-07-14 02:09:47
--- In
concatenative@yahoogroups.com, "Ivan Tomac" <e1_t@y...> wrote:
> cpop, there will either be n or n-1 elements upon it's completion.
>
Oops, that should be n-1 or n-2 elements (forgot to count the boolean
value).
Ivan
William Tanksley, Jr — 2005-07-14 04:12:40
phimvt@... <
phimvt@...> wrote:
> The point of the insane example is that such character macros need not
> respect any higher syntax rules. In some sense the language of
> concatenated sequences of character is completely flat. But it is not a
> concatenative language because concatenation of characters does not map
> onto composition of functions - characters do not denote functions.
Right -- I would go on to say that the reason concatenative languages
are interesting to work in is that the semantics of the language
(sequential functions) matches the semantics of the medium (sequential
characters).
> 2. In all standard languages a program is a sequence of symbols, where
> a symbol is a sequence of printing characters separated by whitespace
> characters (or other devices such as change of character class).
> For any such language it is possible to define macros (with or without
> parameters) whose bodies are sequences of symbols. As an example I'll
> use one put forward by Billy:
My example was not about macros -- it was about a hypothetical almost
completely lazy concatenative language.
> On Wed, 15 Jun 2005, wtanksley wrote:
> > Of course, the result could sometimes be odd-looking... Imagine this:
> > : b 2 / ] ;
> > : a [ 10 ;
> > a b i .
> > => 5
> I welcome that it is so odd-looking, exactly the sort of example I want.
> It so happens that most of the symbols in the example happen to be
> single character symbols. So, to drive home the point that the body
> of the definition is a sequence of symbols here is another in the same
> spirit:
> : b * ] map ;
> : a [ dup ;
> [1 2 3 4] a b .
> => [1 4 9 16]
> Again a sequence of symbols is completely flat, just as in the earlier
> case, but it assumes that the symbols have been read by the scanner
> or tokeniser of the language (Joy in this case), but not by the parser.
In my language there is no parser (or rather, almost no parser; I
chose to keep the definition parser in order to make the familiar : ;
definitions). Because the language is lazy, the functions themselves
choose when to execute and what to do.
> The macros do not have to respect the syntax of the language, in both
> examples the macros do not respect the special roles of [ and ].
Those aren't macros; the language has no static syntax; and most
importantly, [ and ] have no special roles (aside from their
activities as functions).
> Hence we cannot say that the concatenation of symbols maps onto the
> composition of functions which the symbols denote: some symbols,
> [ and ] in particular, or IF and THEN in Forth, do not denote functions.
The big point I was trying to make was that in a lazy language [ and ]
CAN be functions.
[...]
> A language that obeys a recursive grammar such as the above appears to
> be irreducibly non-flat, but it can have a concatenative semantics:
> concatenation of terms maps onto composition of functions.
I agree.
One question.
A flat language possesses a property which I had previously attributed
to concatenative languages, but which is not always true of
concatenative languages: any split of a single valid flat program
produces two valid flat programs. This seems like a very useful
property, and in fact some version of it is required for realistic use
of concatenative languages (such as factoring).
> I have
> tried to give a concatenative sematics to some flat version of Joy,
> but either it fails to have a concatenative semantics (like (2) above),
> or it fails to be flat (like (3) above). My guess is that flatness
> and concatenative semantics are incompatible in the case of Joy.
> I am less certain about this conjecture in the case of Forth.
> It would be interesting to see that my conjecture is false.
It's obvious that both Forth and Joy possess subsets that are both
concatenative and flat. Joy is non-flat in its blocks and its
definitions; Forth is non-flat in its control structures, the
address-of operator, and its definitions.
Joy's definitions could be rewritten to use blocks, like "[ 10 + ]
'incr' defined". This would make blocks the only non-flat part of Joy.
Forth, likewise, could be reworked to use Joy-style conditionals and a
simple address-of lexeme, leaving definitions as the only non-flat
part of Forth.
> In
> particular, I am intrigued by what Billy also said:
> > I don't know whether my definition matches how other people were using
> > the word, but I just realised that the perfect way to produce flatness
> > is with a lazy concatenative language. Because the language is lazy,
> > you don't need ifs; you just need a conditional drop. All of the
> > syntax can become just ordinary words; even quotations marks [ and ]
> > would just lazily group words that appeared at the same runtime level
> > of nesting.
> I don't really understand what you meant about the ifs and conditional
> drops, or how laziless makes flatness and concatenativve semantics
> compatible. Could you elaborate, please?
Sorry; sure!
Okay, we know that in a lazy language, words only get executed if they
actually have an effect, right? So in a lazy language, "dup 2 * drop"
wouldn't be executed at all (or at worst, it would have the same
semantics as "dup drop"). This suggests that conditional execution
could be replaced by a simple conditional drop (if-else is left as an
excercise to the reader). We know that iteration can be replaced by
automatic array iteration, of course. Definitions can be replaced by
labels, as in colorForth or assembler.
So this provides us with a concatenative, flat language which is
nonetheless quite powerful and even structured (although at a
functional level rather than a syntactic one). More structure can be
provided... but I'll stop at this point and ask if I'm making any
sense. If so, I can explain how [ and ] can be implemented as
functions.
> - Manfred
-Billy
stevan apter — 2005-07-14 11:08:02
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
>... but I'll stop at this point and ask if I'm making any
> sense. If so, I can explain how [ and ] can be implemented as
> functions.
>
this hovers just beyond my ability to comprehend.
[ and ] are functions. but functions of what to what?
f == [ 2
g == 3 + ] i
so
f g
5
let me take a stab at defining [ and ] operationally.
[ is defined to push itself onto the stack. every
function other than ] is redefined to be sensitive to
whether [ is on the stack. if it isn't, it behaves
normally. if it is, it pushes itself onto the stack.
] is defined to find everything .. up to the last [
and replace that [ with [..].
if this is right (and the result does appear to be
perfectly flat the way you mean), then i don't see
what it has to do with laziness. can you amplify?
stevan apter — 2005-07-14 11:35:40
>
> let me take a stab at defining [ and ] operationally.
>
> [ is defined to push itself onto the stack. every
> function other than ] is redefined to be sensitive to
> whether [ is on the stack. if it isn't, it behaves
> normally. if it is, it pushes itself onto the stack.
>
> ] is defined to find everything .. up to the last [
> and replace that [ with [..].
now that i think about it, this probably doesn't
work. if [ and ] are functions, then how do you
produce the quotation
[ [ ]
i.e. the list whose sole element is [?
sa@dfa.com — 2005-07-14 18:13:08
the, or at any rate *one* answer is: since [ and ] are
functions, quote them. e.g. in XY
2 3 \+
pushes 2, then 3, then + onto the stack. so
[ \] ]
[ ] ]
[ \[ ]
[ [ ]
which works fine. it was easy to flatten XY:
http://www.nsl.com/k/xy/xy7.k
[ is defined to push [[ on the stack (a special marker
for "open list")
] is defined to grab everything up to the last [[, enlist
the contents, and push the result onto the queue.
if [[ is on the stack, then every word encountered until
all [['s have been "cleared" is treated as a "thing" and
pushed onto the stack. that is, every word except \
(quotation) and ; (definition).
there are still a few problems, but i imagine they can
be solved, if not in XY, then perhaps in some other
flat language:
; f 2 [ 3 ;
; g + ] i ;
f and g are properly defined, but
f
causes
2 [[ 3
to be on the stack, so subsequently,
g
is not "interpreted". i.e. the result of
f g
is
2 [ 3 g
i have to figure out how to treat "get the value of <name>"
like \ and ;.
i'm still unclear about the connections between flatness
and laziness.
concatenative@yahoogroups.com wrote on 07/14/2005 07:35:40 AM:
> >
> > let me take a stab at defining [ and ] operationally.
> >
> > [ is defined to push itself onto the stack. every
> > function other than ] is redefined to be sensitive to
> > whether [ is on the stack. if it isn't, it behaves
> > normally. if it is, it pushes itself onto the stack.
> >
> > ] is defined to find everything .. up to the last [
> > and replace that [ with [..].
>
> now that i think about it, this probably doesn't
> work. if [ and ] are functions, then how do you
> produce the quotation
>
> [ [ ]
>
> i.e. the list whose sole element is [?
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
sa@dfa.com — 2005-07-15 12:47:11
i hope no one minds that i continue to post my thoughts
on this topic.
at first, i thought that flatness was inconsistent with
intensional lists (quotations), since if
[ 1 2 3 ]
could be factored as
[ 1 2 3 ]
--- -----
f g
such that
f g
[ 1 2 3 ]
then it could also be factored as
[ 1 2 3 ]
-----
h
such that
[ h ]
[ 1 2 3 ]
which precludes creating the singleton quotation [ h ].
in other words, if eval(x}=eval(y) then [x] = [y], which
is plainly not the case for quotations in Joy or XY.
then i realized that intensionality can be preserved by
means of quotation:
[ \h ]
[ h ]
[ h ]
[ 1 2 3 ]
making this change in XY (1.7) means that scripts written
for 1.6 will no longer work. it also means adding six
more primitives to the core: [ ] `[ ( ) `(. but the
tradeoff seems reasonable, since the parser gets much
simpler.
oddly enough, i only required 24 functions (a-z but not
g or q) to implement XY 1.6, and to add flatness, i only
needed two more. so the implementation now consists of 26
functions a-z, which i guess means that it's done.
concatenative@yahoogroups.com wrote on 07/14/2005 02:13:08 PM:
>
>
>
>
>
> the, or at any rate *one* answer is: since [ and ] are
> functions, quote them. e.g. in XY
>
> 2 3 \+
>
> pushes 2, then 3, then + onto the stack. so
>
> [ \] ]
> [ ] ]
>
> [ \[ ]
> [ [ ]
>
> which works fine. it was easy to flatten XY:
>
> http://www.nsl.com/k/xy/xy7.k
>
> [ is defined to push [[ on the stack (a special marker
> for "open list")
>
> ] is defined to grab everything up to the last [[, enlist
> the contents, and push the result onto the queue.
>
> if [[ is on the stack, then every word encountered until
> all [['s have been "cleared" is treated as a "thing" and
> pushed onto the stack. that is, every word except \
> (quotation) and ; (definition).
>
> there are still a few problems, but i imagine they can
> be solved, if not in XY, then perhaps in some other
> flat language:
>
> ; f 2 [ 3 ;
> ; g + ] i ;
>
> f and g are properly defined, but
>
> f
>
> causes
>
> 2 [[ 3
>
> to be on the stack, so subsequently,
>
> g
>
> is not "interpreted". i.e. the result of
>
> f g
>
> is
>
> 2 [ 3 g
>
> i have to figure out how to treat "get the value of <name>"
> like \ and ;.
>
> i'm still unclear about the connections between flatness
> and laziness.
>
>
> concatenative@yahoogroups.com wrote on 07/14/2005 07:35:40 AM:
>
> > >
> > > let me take a stab at defining [ and ] operationally.
> > >
> > > [ is defined to push itself onto the stack. every
> > > function other than ] is redefined to be sensitive to
> > > whether [ is on the stack. if it isn't, it behaves
> > > normally. if it is, it pushes itself onto the stack.
> > >
> > > ] is defined to find everything .. up to the last [
> > > and replace that [ with [..].
> >
> > now that i think about it, this probably doesn't
> > work. if [ and ] are functions, then how do you
> > produce the quotation
> >
> > [ [ ]
> >
> > i.e. the list whose sole element is [?
> >
> >
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
Narcoleptic Electron — 2005-07-15 16:42:32
On 7/15/05,
sa@... <
sa@...> wrote:
> then i realized that intensionality can be preserved by
> means of quotation:
>
> [ \h ]
> [ h ]
> [ h ]
> [ 1 2 3 ]
To make sure I understand this: in Joy, the square brackets have two
jobs: they signify both lists and quotations. You have separated
these, so that [] indicates a list, and \ indicates quotation.
If so, consider this: if the language were purely lazy, the quotation
operator could itself be a normal function. Eg:
[ h \ ]
Then the quotation function is first class, and you could do things
like quoting the quotation function:
[ \ \ ]
I could be way off on all of this.
John.Cowan — 2005-07-15 17:10:23
Narcoleptic Electron scripsit:
> To make sure I understand this: in Joy, the square brackets have two
> jobs: they signify both lists and quotations. You have separated
> these, so that [] indicates a list, and \ indicates quotation.
Yes, I think so, but I think your way of putting it is confusing, given
that in Joy "quotation" means a list suitable for execution. Square brackets
enclose a list and ensure that symbols mentioned in the list are implicitly
quoted; indeed, there is no specific syntax for symbol quoting in Joy, and
to get a symbol s onto the stack one executes
[s] first
or
"s" intern
> If so, consider this: if the language were purely lazy, the quotation
> operator could itself be a normal function. Eg:
>
> [ h \ ]
>
> Then the quotation function is first class, and you could do things
> like quoting the quotation function:
>
> [ \ \ ]
That would quote the symbol \, not the function it names.
--
Her he asked if O'Hare Doctor tidings sent from far John Cowan
coast and she with grameful sigh him answered that www.ccil.org/~cowan
O'Hare Doctor in heaven was. Sad was the man that word www.reutershealth.com
to hear that him so heavied in bowels ruthful. All
jcowan@...
she there told him, ruing death for friend so young,
algate sore unwilling God's rightwiseness to withsay. Ulysses, "Oxen"
sa@dfa.com — 2005-07-15 17:18:54
in XY (either version)
[ \\ ]
[\]
that is, you can quote the quotation operator. in other
words, quotation is first-class.
concatenative@yahoogroups.com wrote on 07/15/2005 12:42:32 PM:
> On 7/15/05, sa@... <sa@...> wrote:
> > then i realized that intensionality can be preserved by
> > means of quotation:
> >
> > [ \h ]
> > [ h ]
> > [ h ]
> > [ 1 2 3 ]
>
> To make sure I understand this: in Joy, the square brackets have two
> jobs: they signify both lists and quotations. You have separated
> these, so that [] indicates a list, and \ indicates quotation.
>
> If so, consider this: if the language were purely lazy, the quotation
> operator could itself be a normal function. Eg:
>
> [ h \ ]
>
> Then the quotation function is first class, and you could do things
> like quoting the quotation function:
>
> [ \ \ ]
>
> I could be way off on all of this.
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
sa@dfa.com — 2005-07-15 18:05:47
concatenative@yahoogroups.com wrote on 07/15/2005 01:10:23 PM:
> Narcoleptic Electron scripsit:
>
> > To make sure I understand this: in Joy, the square brackets have two
> > jobs: they signify both lists and quotations. You have separated
> > these, so that [] indicates a list, and \ indicates quotation.
>
> Yes, I think so, but I think your way of putting it is confusing, given
> that in Joy "quotation" means a list suitable for execution.
since all lists are suitable for execution, in joy, "list" and
"quotation" are just different names for the same thing.
i suppose you could make the following distinction: x is a list
if x = x i stack (starting with the empty stack). or perhaps you
need to do that operation recursively. intuitively, a quotation
is a list if every atom is a function whose meaning is "data-like",
in that when executed it pushes itself onto the stack. so
[1 2 3]
is a list, while
[1 2 +]
is not.
Square brackets
> enclose a list and ensure that symbols mentioned in the list are
implicitly
> quoted; indeed, there is no specific syntax for symbol quoting in Joy,
and
> to get a symbol s onto the stack one executes
>
> [s] first
>
> or
>
> "s" intern
>
> > If so, consider this: if the language were purely lazy, the quotation
> > operator could itself be a normal function. Eg:
> >
> > [ h \ ]
> >
> > Then the quotation function is first class, and you could do things
> > like quoting the quotation function:
> >
> > [ \ \ ]
>
> That would quote the symbol \, not the function it names.
>
> --
> Her he asked if O'Hare Doctor tidings sent from far John Cowan
> coast and she with grameful sigh him answered that
www.ccil.org/~cowan
> O'Hare Doctor in heaven was. Sad was the man that word
www.reutershealth.com
> to hear that him so heavied in bowels ruthful. All
jcowan@...
> she there told him, ruing death for friend so young,
> algate sore unwilling God's rightwiseness to withsay. Ulysses, "Oxen"
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
John.Cowan — 2005-07-15 18:33:02
sa@... scripsit:
> since all lists are suitable for execution, in joy, "list" and
> "quotation" are just different names for the same thing.
Well, not quite. A list some of whose members are undefined symbols
is not suitable for execution.
> i suppose you could make the following distinction: x is a list
> if x = x i stack (starting with the empty stack). or perhaps you
> need to do that operation recursively. intuitively, a quotation
> is a list if every atom is a function whose meaning is "data-like",
> in that when executed it pushes itself onto the stack. so
>
> [1 2 3]
>
> is a list, while
>
> [1 2 +]
>
> is not.
My intuitions are quite otherwise: a list is a sequence of Joy values, and
both your examples are perfectly good lists.
--
You know, you haven't stopped talking John Cowan
since I came here. You must have been
http://www.reutershealth.com
vaccinated with a phonograph needle.
jcowan@...
--Rufus T. Firefly
http://www.ccil.org/~cowan
sa@dfa.com — 2005-07-15 18:53:27
concatenative@yahoogroups.com wrote on 07/15/2005 02:33:02 PM:
> sa@... scripsit:
>
> > since all lists are suitable for execution, in joy, "list" and
> > "quotation" are just different names for the same thing.
>
> Well, not quite. A list some of whose members are undefined symbols
> is not suitable for execution.
not in Joy, i agree. in XY, the value of an undefined
symbol x is x. e.g.
undefined
undefined
[2 foo 3] i
2 foo 3
>
> > i suppose you could make the following distinction: x is a list
> > if x = x i stack (starting with the empty stack). or perhaps you
> > need to do that operation recursively. intuitively, a quotation
> > is a list if every atom is a function whose meaning is "data-like",
> > in that when executed it pushes itself onto the stack. so
> >
> > [1 2 3]
> >
> > is a list, while
> >
> > [1 2 +]
> >
> > is not.
>
> My intuitions are quite otherwise: a list is a sequence of Joy values,
and
> both your examples are perfectly good lists.
so you think that quotation is a special case of list, and
i think the opposite.
interesting.
>
> --
> You know, you haven't stopped talking John Cowan
> since I came here. You must have been
http://www.reutershealth.com
> vaccinated with a phonograph needle. jcowan@...
> --Rufus T. Firefly
http://www.ccil.org/~cowan
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
stevan apter — 2005-07-16 12:13:48
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, July 14, 2005 12:12 AM
Subject: Re: [stack] stack operations vs function transformation
> phimvt@... <phimvt@...> wrote:
[:]
>
> > I don't really understand what you meant about the ifs and conditional
> > drops, or how laziless makes flatness and concatenativve semantics
> > compatible. Could you elaborate, please?
>
> Sorry; sure!
>
> Okay, we know that in a lazy language, words only get executed if they
> actually have an effect, right? So in a lazy language, "dup 2 * drop"
> wouldn't be executed at all (or at worst, it would have the same
> semantics as "dup drop").
this is where you lose me billy.
the claim that a concatenative language can't be flat unless it's also
lazy (in your sense) must be wrong, since XY is both concatenative and
(now) flat, but not lazy (in any sense.)
i guess i still don't understand why the evaluation model has anything
to do with flatness or concatenativity.
> This suggests that conditional execution
> could be replaced by a simple conditional drop (if-else is left as an
> excercise to the reader). We know that iteration can be replaced by
> automatic array iteration, of course. Definitions can be replaced by
> labels, as in colorForth or assembler.
>
> So this provides us with a concatenative, flat language which is
> nonetheless quite powerful and even structured (although at a
> functional level rather than a syntactic one). More structure can be
> provided... but I'll stop at this point and ask if I'm making any
> sense. If so, I can explain how [ and ] can be implemented as
> functions.
>
> > - Manfred
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2005-07-16 20:22:36
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > > I don't really understand what you meant about the ifs and conditional
> > > drops, or how laziless makes flatness and concatenativve semantics
> > > compatible. Could you elaborate, please?
> > Okay, we know that in a lazy language, words only get executed if they
> > actually have an effect, right? So in a lazy language, "dup 2 * drop"
> > wouldn't be executed at all (or at worst, it would have the same
> > semantics as "dup drop").
> this is where you lose me billy.
Why?
> the claim that a concatenative language can't be flat unless it's also
> lazy (in your sense) must be wrong, since XY is both concatenative and
> (now) flat, but not lazy (in any sense.)
I don't think I made that claim -- did I? I claim only that a lazy
concatenative language could be _perfectly_ flat (in the sense that
any valid program can be cut at ANY space to produce two valid
programs, even if the cut point is in the middle of a definition). I
don't claim anything about any other languages.
I'm glad to hear that XY isn't lazy in any sense -- I've been waiting
for a language that would automatically debug programs written in it,
but all existing languages seem to be lazy in that sense. ;-)
Manfred is skeptical about languages being able to be both flat and
concatenative, and I was providing a counterexample.
-Billy
stevan apter — 2005-07-16 21:17:19
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, July 16, 2005 4:22 PM
Subject: Re: [stack] stack operations vs function transformation
> stevan apter <sa@...> wrote:
> > From: "William Tanksley, Jr" <wtanksleyjr@...>
> > > > I don't really understand what you meant about the ifs and conditional
> > > > drops, or how laziless makes flatness and concatenativve semantics
> > > > compatible. Could you elaborate, please?
>
> > > Okay, we know that in a lazy language, words only get executed if they
> > > actually have an effect, right? So in a lazy language, "dup 2 * drop"
> > > wouldn't be executed at all (or at worst, it would have the same
> > > semantics as "dup drop").
>
> > this is where you lose me billy.
>
> Why?
is it true that in a lazy functional stack language, no-ops would be
detected and factored out of the execution? what restrictions (apart
from the obvious, like "no side-effects") would you have to impose
to make this computable before execution takes place? in any case,
this isn't how "lazy" is conventionally used, is it? is there some
connection i'm missing?
>
> > the claim that a concatenative language can't be flat unless it's also
> > lazy (in your sense) must be wrong, since XY is both concatenative and
> > (now) flat, but not lazy (in any sense.)
>
> I don't think I made that claim -- did I? I claim only that a lazy
> concatenative language could be _perfectly_ flat (in the sense that
> any valid program can be cut at ANY space to produce two valid
> programs, even if the cut point is in the middle of a definition). I
> don't claim anything about any other languages.
my sense is that you should exempt word-definition itself, if
a word can define a word. e.g.
: foo : goo 2 3 + ; ;
foo
goo
5
but not:
: foo1 : goo 2 ;
: foo2 3 + ;
foo1 foo2
goo
5
>
> I'm glad to hear that XY isn't lazy in any sense -- I've been waiting
> for a language that would automatically debug programs written in it,
> but all existing languages seem to be lazy in that sense. ;-)
i'm not sure i get the joke, but you're right - i misspoke. since
quotations are lazy (they are, after all *quotations*), XY is as
lazy as Joy.
>
> Manfred is skeptical about languages being able to be both flat and
> concatenative, and I was providing a counterexample.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2005-07-18 05:44:08
On Wed, 13 Jul 2005 phimvt@... wrote:
Sorry to be replying to myself ...
[..]
> My guess is that flatness
> and concatenative semantics are incompatible in the case of Joy.
> I am less certain about this conjecture in the case of Forth.
> It would be interesting to see that my conjecture is false.
It is certainly not the case that flatness and concatenative semantics are
always incompatible. Consider assembly language (this is from somebody who
hwas never written an assembly program):
An instruction consists of an opcode, maybe some addresses, and perhaps
some additional flags. A program is a sequence of instructions, and larger
programs can always be concatenated from shorter ones. So this is
flatness.
An instruction produces a change in the CPU, including the program
counter, some registers, the memory, and everything connected to that.
Hence an instruction denotes a unary function from states (of the CPU etc)
to states. A concatenation of instructions denotes the composition of the
functions which the instructions denote. So this is concatenative
semantics.
One might agree that this is fine as far as it goes, but it ignores that
instructions have parts - the opcode, the addresses etc. But I don't think
this matters, really. Alternatively, take machine language: an
instruction is a normally a bit pattern, a sequence of bit that can be
concatenated from shorter sequences (without concatenative semantics, of
course). But such bit patterns could equally well be replaced by something
else, different shades of gray, perhaps. We only use bit patterns because
this makes the hardware easy to make.
Well then - so what is the difference between flat asssembly/machine
languages and non-flat Joy and non-flat Forth? I suggest that is is the
program counter which is exposed in assembly/machine language but hidden
in Joy and Forth (at least the part of Forth that we seem to be
discussing).
Any thoughts?
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-07-18 07:31:30
On Wed, 13 Jul 2005, William Tanksley, Jr wrote:
> phimvt@... <phimvt@...> wrote:
> > The point of the insane example is that such character macros need not
> > respect any higher syntax rules. In some sense the language of
> > concatenated sequences of character is completely flat. But it is not a
> > concatenative language because concatenation of characters does not map
> > onto composition of functions - characters do not denote functions.
>
> Right -- I would go on to say that the reason concatenative languages
> are interesting to work in is that the semantics of the language
> (sequential functions) matches the semantics of the medium (sequential
> characters).
Entirely agree (except you probbably did not reaaly mean "characters").
>
> > 2. In all standard languages a program is a sequence of symbols, where
> > a symbol is a sequence of printing characters separated by whitespace
> > characters (or other devices such as change of character class).
> > For any such language it is possible to define macros (with or without
> > parameters) whose bodies are sequences of symbols. As an example I'll
> > use one put forward by Billy:
>
> My example was not about macros -- it was about a hypothetical almost
> completely lazy concatenative language.
I understand. I used the two kinds of macros (character macros in (1)
and symbol macros in (2)) to illustrate "cuttability" - if you will
forgive the word.
> > On Wed, 15 Jun 2005, wtanksley wrote:
>
> > > Of course, the result could sometimes be odd-looking... Imagine this:
>
> > > : b 2 / ] ;
> > > : a [ 10 ;
> > > a b i .
> > > => 5
>
> > I welcome that it is so odd-looking, exactly the sort of example I want.
> > It so happens that most of the symbols in the example happen to be
> > single character symbols. So, to drive home the point that the body
> > of the definition is a sequence of symbols here is another in the same
> > spirit:
>
> > : b * ] map ;
> > : a [ dup ;
> > [1 2 3 4] a b .
> > => [1 4 9 16]
>
> > Again a sequence of symbols is completely flat, just as in the earlier
> > case, but it assumes that the symbols have been read by the scanner
> > or tokeniser of the language (Joy in this case), but not by the parser.
>
> In my language there is no parser (or rather, almost no parser; I
> chose to keep the definition parser in order to make the familiar : ;
> definitions). Because the language is lazy, the functions themselves
> choose when to execute and what to do.
>
> > The macros do not have to respect the syntax of the language, in both
> > examples the macros do not respect the special roles of [ and ].
>
> Those aren't macros; the language has no static syntax; and most
> importantly, [ and ] have no special roles (aside from their
> activities as functions).
No static syntax? Maybe it is a very minimal syntax: a program
is a sequence of symbols? And you still have a minimal parser:
read symbols until end-of-program.
>
> > Hence we cannot say that the concatenation of symbols maps onto the
> > composition of functions which the symbols denote: some symbols,
> > [ and ] in particular, or IF and THEN in Forth, do not denote functions.
>
> The big point I was trying to make was that in a lazy language [ and ]
> CAN be functions.
Sorry, but I still don't get it. (And I'm not being difficult.)
> [...]
> > A language that obeys a recursive grammar such as the above appears to
> > be irreducibly non-flat, but it can have a concatenative semantics:
> > concatenation of terms maps onto composition of functions.
>
> I agree.
>
> One question.
>
> A flat language possesses a property which I had previously attributed
> to concatenative languages, but which is not always true of
> concatenative languages: any split of a single valid flat program
> produces two valid flat programs. This seems like a very useful
> property, and in fact some version of it is required for realistic use
> of concatenative languages (such as factoring).
This advantage, if it really is one, appears to involve some cost,
though. Compare the 1970's discussion about flow of control in
structured programming: Consensus was that conditionals and loops
are good for you - and they imply a tree structure.
[..]>
> > I don't really understand what you meant about the ifs and conditional
> > drops, or how laziless makes flatness and concatenativve semantics
> > compatible. Could you elaborate, please?
>
> Sorry; sure!
>
> Okay, we know that in a lazy language, words only get executed if they
> actually have an effect, right? So in a lazy language, "dup 2 * drop"
> wouldn't be executed at all (or at worst, it would have the same
> semantics as "dup drop")
This is not what I understand by lazyness. A language is nonstrict
if some of its expressions are defined even if parts of it are not.
The usual implementation is by lazyness: evaluate only when the
value is really needed. (And in most implementations: after the
evaluation replace the expression by that value, so further evaluations
are not required).
What you describe looks more like an optimisation (which could be done
at compile time).
[..]
> but I'll stop at this point and ask if I'm making any
> sense. If so, I can explain how [ and ] can be implemented as
> functions.
Yes, you are making sense. But I'm still puzzled about [ and ]
as functions.
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-07-18 07:45:00
On Thu, 14 Jul 2005, stevan apter wrote:
>
> ----- Original Message -----
> From: "William Tanksley, Jr" <wtanksleyjr@...>
>
>
> >... but I'll stop at this point and ask if I'm making any
> > sense. If so, I can explain how [ and ] can be implemented as
> > functions.
> >
>
> this hovers just beyond my ability to comprehend.
>
> [ and ] are functions. but functions of what to what?
>
>
> f == [ 2
>
> g == 3 + ] i
>
> so
>
> f g
> 5
This would be a perfect example of my type (2), symbol macros.
> let me take a stab at defining [ and ] operationally.
>
> [ is defined to push itself onto the stack. every
> function other than ] is redefined to be sensitive to
> whether [ is on the stack. if it isn't, it behaves
> normally. if it is, it pushes itself onto the stack.
> ] is defined to find everything .. up to the last [
> and replace that [ with [..].
Ingenious. There might be a problem with what could be meant
by the resultant [..] replacement. Will it be just the contents ..,
or will it also include the [ and ] ? In the first case,
how does [1 2 3] differ from 1 2 3 ? In the second case,
how would one handle nested quotations of lists ?
[..]
-
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-07-18 08:07:59
On Fri, 15 Jul 2005, John.Cowan wrote:
> sa@... scripsit:
>
> > since all lists are suitable for execution, in joy, "list" and
> > "quotation" are just different names for the same thing.
>
> Well, not quite. A list some of whose members are undefined symbols
> is not suitable for execution.
Unless one allows error values. In some theoretical treatments
in addition to the normal values one has ERROR, and then everything
has a value, even [peter paul] i, where peter and paul are undefined.
The same is true for more mundane type errors such as 42 concat.
A resulting ERROR value has the same efffect on the stack as an
explicit abort ("forget the rest of this program").
But your essential point still holds, of course.
>
> > i suppose you could make the following distinction: x is a list
> > if x = x i stack (starting with the empty stack). or perhaps you
> > need to do that operation recursively. intuitively, a quotation
> > is a list if every atom is a function whose meaning is "data-like",
> > in that when executed it pushes itself onto the stack. so
> >
> > [1 2 3]
> >
> > is a list, while
> >
> > [1 2 +]
> >
> > is not.
>
> My intuitions are quite otherwise: a list is a sequence of Joy values, and
> both your examples are perfectly good lists.
I have always tried to dodge explaining the difference, if any.
On the one hand I like the simplicity of allowing [1 2 +] as a list.
On the other, people have consistently objected to treating +
as an elemennt of a list.
- Manfred
stevan apter — 2005-07-18 11:20:45
----- Original Message -----
From: <phimvt@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 18, 2005 4:07 AM
Subject: Re: [stack] stack operations vs function transformation
>
> On Fri, 15 Jul 2005, John.Cowan wrote:
>
> > sa@... scripsit:
> >
> > > since all lists are suitable for execution, in joy, "list" and
> > > "quotation" are just different names for the same thing.
> >
> > Well, not quite. A list some of whose members are undefined symbols
> > is not suitable for execution.
>
> Unless one allows error values. In some theoretical treatments
> in addition to the normal values one has ERROR, and then everything
> has a value, even [peter paul] i, where peter and paul are undefined.
> The same is true for more mundane type errors such as 42 concat.
> A resulting ERROR value has the same efffect on the stack as an
> explicit abort ("forget the rest of this program").
>
> But your essential point still holds, of course.
>
> >
> > > i suppose you could make the following distinction: x is a list
> > > if x = x i stack (starting with the empty stack). or perhaps you
> > > need to do that operation recursively. intuitively, a quotation
> > > is a list if every atom is a function whose meaning is "data-like",
> > > in that when executed it pushes itself onto the stack. so
> > >
> > > [1 2 3]
> > >
> > > is a list, while
> > >
> > > [1 2 +]
> > >
> > > is not.
> >
> > My intuitions are quite otherwise: a list is a sequence of Joy values, and
> > both your examples are perfectly good lists.
>
> I have always tried to dodge explaining the difference, if any.
> On the one hand I like the simplicity of allowing [1 2 +] as a list.
> On the other, people have consistently objected to treating +
> as an elemennt of a list.
in XY, [1 2 +] -> [1 2 +] and (1 2 +) -> [3]. [] is lazy and () is
eager. (..) is implemented under the covers as [..] [i] infra. in
both cases, the result is a list. also, +\ -> +, which is the most
direct way to place an XY symbol on the stack.
i think, unless i'm overlooking something, that using only ()s, and
not []s or \, it's not possible to produce the list. the set of values
which can be produced by ()s is a proper subset of that which can be
produced by []s.
another way to get at the difference is to say that () produces lists
all of whose atoms x have the semantic rule x -- x, or as i write it
for XY: [X x^Y] -> [X^x Y].
in any case, i'm comfortable with saying that both [2 3 +] and [2 3]
are lists.
>
> - Manfred
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
stevan apter — 2005-07-18 11:33:06
----- Original Message -----
From: <phimvt@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 18, 2005 3:45 AM
Subject: Re: [stack] stack operations vs function transformation
>
> On Thu, 14 Jul 2005, stevan apter wrote:
>
> >
> > ----- Original Message -----
> > From: "William Tanksley, Jr" <wtanksleyjr@...>
> >
> >
> > >... but I'll stop at this point and ask if I'm making any
> > > sense. If so, I can explain how [ and ] can be implemented as
> > > functions.
> > >
> >
> > this hovers just beyond my ability to comprehend.
> >
> > [ and ] are functions. but functions of what to what?
> >
> >
> > f == [ 2
> >
> > g == 3 + ] i
> >
> > so
> >
> > f g
> > 5
>
> This would be a perfect example of my type (2), symbol macros.
>
> > let me take a stab at defining [ and ] operationally.
> >
> > [ is defined to push itself onto the stack. every
> > function other than ] is redefined to be sensitive to
> > whether [ is on the stack. if it isn't, it behaves
> > normally. if it is, it pushes itself onto the stack.
>
> > ] is defined to find everything .. up to the last [
> > and replace that [ with [..].
>
> Ingenious. There might be a problem with what could be meant
> by the resultant [..] replacement. Will it be just the contents ..,
> or will it also include the [ and ] ? In the first case,
> how does [1 2 3] differ from 1 2 3 ? In the second case,
> how would one handle nested quotations of lists ?
i wound up implementing the following scheme:
[ is defined to push the marker [[ onto the stack.
] takes everything up to the last [[, enlists it,
and pushes the result onto the queue.
the evaluator has to know whether [[ is on the stack.
if it is, primitives other than ] are treated the way
literals are, viz. they're simply pushed onto the stack.
defined words, however, are treated the same way: their
values are pushed onto the queue.
nested lists are no problem: in evaluating [1 [2] 3]
at the point where 2 is at the head of the queue, the
stack consists of .. [[ 1 [[. at the next step we have
.. [[ 1 [[ 2. then the first ] takes everything up to
the last [[, enlists it and places the result on the
queue. so at that point the stack is .. [[ 1 and the
queue is [2] 3 ]. the queue has three items: a list,
a number, and the function ].
as i see it, the main problem with all of this is that
quotation is no longer completely lazy. as i pointed
out in a previous note, if a = [1 2 3], then [a] =
[[1 2 3]]. in order to place the singleton list [a]
on the stack, you need to be able to block evaluation
of a. in XY, this is written [\a]. perhaps this is
an artifact of the way i've chosen to implement flat
list notation in XY, but i can't see how it can be
avoided.
>
> [..]
>
> -
> - Manfred
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
stevan apter — 2005-07-18 21:43:40
i believe that my latest version of XY 2.0 arrives at
the best possible solution for combining (i) concatenative
syntax, (ii) lazy quotation, and (iii) flatness. here's
the idea.
[ is just another literal: it places itself on the stack.
there are no "markers", as in the earlier version.
] is a function: it grabs everything up to the last [ on
the stack, enlists it, and pushes it onto the queue. the
next evaluation step takes the list from the queue and
pushes it onto the stack.
the evaluator operates in two "modes".
if [ is not on the stack, then the ordinary semantic rules
operate.
if [ *is* on the stack, then everything is treated as a
literal *except* ] / and \, which have their usual
definitions, namely:
\ is atomic quotation. e.g. \ + puts + on the stack.
/ is joy's "i" combinator, extended as follows: if x is a
symbol, then x i places the value of x on the stack. e.g.
if foo == 2 + then \ foo / puts [2 +] on the stack.
] operates as described above.
so, for example:
; f [ 1 2 3 ;
; g 4 5 ] ;
f g
[ 1 2 3 g
/
[1 2 3 4 5]
Narcoleptic Electron — 2005-07-18 22:05:31
On 7/18/05, stevan apter <
sa@...> wrote:
> if [ *is* on the stack, then everything is treated as a
> literal *except* ] / and \, which have their usual
> definitions, namely:
>
> \ is atomic quotation. e.g. \ + puts + on the stack.
>
> / is joy's "i" combinator, extended as follows: if x is a
> symbol, then x i places the value of x on the stack. e.g.
> if foo == 2 + then \ foo / puts [2 +] on the stack.
>
> ] operates as described above.
>
> so, for example:
>
> ; f [ 1 2 3 ;
> ; g 4 5 ] ;
> f g
> [ 1 2 3 g
> /
> [1 2 3 4 5]
If taken at face value, and "[" is just another literal, then the
evaluator would need to check
the stack at every evaluation to see if "[" is on it, and conduct
itself accordingly. This would be slow.
Otherwise, specific optimizations need to be provided for the "[" case
so that as soon as "[" goes onto the stack, the evaluator remembers
that it's there. This makes "[" more than just a literal. It is more
like a program that operates on the "evaluator" and changes its state.
William Tanksley, Jr — 2005-07-18 22:24:58
stevan apter <
sa@...> wrote:
> i believe that my latest version of XY 2.0 arrives at
> the best possible solution for combining (i) concatenative
> syntax, (ii) lazy quotation, and (iii) flatness. here's
> the idea.
I'm not a big fan of lazy quotation anyhow. Why not just have lazy
semantics, and let the quotations worry about themselves? That way
your entire language is stateless.
Other than that, your solution is essentially what I was going to
explain, only you've worked out more of the details.
-Billy
stevan apter — 2005-07-18 23:28:59
----- Original Message -----
From: "Narcoleptic Electron" <narcoleptic.electron@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 18, 2005 6:05 PM
Subject: Re: [stack] stack operations vs function transformation
> On 7/18/05, stevan apter <sa@...> wrote:
> > if [ *is* on the stack, then everything is treated as a
> > literal *except* ] / and \, which have their usual
> > definitions, namely:
> >
> > \ is atomic quotation. e.g. \ + puts + on the stack.
> >
> > / is joy's "i" combinator, extended as follows: if x is a
> > symbol, then x i places the value of x on the stack. e.g.
> > if foo == 2 + then \ foo / puts [2 +] on the stack.
> >
> > ] operates as described above.
> >
> > so, for example:
> >
> > ; f [ 1 2 3 ;
> > ; g 4 5 ] ;
> > f g
> > [ 1 2 3 g
> > /
> > [1 2 3 4 5]
>
> If taken at face value, and "[" is just another literal, then the
> evaluator would need to check
> the stack at every evaluation to see if "[" is on it, and conduct
> itself accordingly. This would be slow.
XY gives new meaning to the word "slow". :)
i don't really care. my interest is in designing the right behavior.
the rest is just engineering.
>
> Otherwise, specific optimizations need to be provided for the "[" case
> so that as soon as "[" goes onto the stack, the evaluator remembers
> that it's there. This makes "[" more than just a literal. It is more
> like a program that operates on the "evaluator" and changes its state.
right. there are several tricks which keep the information
about whether and where [ is on the stack instantaneously
available. implementation is simple and straightforward, and
i may, at some point, use one of those methods.
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
stevan apter — 2005-07-18 23:39:48
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 18, 2005 6:24 PM
Subject: Re: [stack] stack operations vs function transformation
> stevan apter <sa@...> wrote:
> > i believe that my latest version of XY 2.0 arrives at
> > the best possible solution for combining (i) concatenative
> > syntax, (ii) lazy quotation, and (iii) flatness. here's
> > the idea.
>
> I'm not a big fan of lazy quotation anyhow. Why not just have lazy
> semantics, and let the quotations worry about themselves? That way
> your entire language is stateless.
XY without in-line word-definition is stateless. that is,
every word is a function [stack queue] -> [stack' queue'].
i could have made it wholly stateless by making every word
a function [stack queue dict] -> [stack' queue' dict'], but
i didn't think of it at the time.
i don't think you have to be a fan of lazy quotation to
dislike how earlier versions of flat XY treated quotations:
; a 10 20 30 ;
[ a + ]
[10 20 30 +]
i.e. lazy with primitives, eager with defined words. ugh.
at this point, XY has both lazy AND eager lists.
(2 3 +)
5
(2 3 5) is translated into [2 3 5] [i] infra.
>
> Other than that, your solution is essentially what I was going to
> explain, only you've worked out more of the details.
i'd still enjoy seeing, even in bare-bones outline, the
language design you have in mind. and i'd definitely like
to hear more about your understanding of "laziness" in this
context, since, like manfred, i find what you've written on
the subject quite puzzling.
>
> -Billy
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2005-07-25 05:02:38
On Mon, 18 Jul 2005, stevan apter wrote:
>
> at this point, XY has both lazy AND eager lists.
>
> (2 3 +)
> 5
>
> (2 3 5) is translated into [2 3 5] [i] infra.
Won't that give you the list [5 3 2] on top of the stack?
Also, your i can execute things other than quotations
(unlike Joy), I take it?
- Manfred
phimvt@lurac.latrobe.edu.au — 2005-07-25 05:21:15
On Mon, 18 Jul 2005, stevan apter wrote:
> > > sa@... scripsit:
> > > > i suppose you could make the following distinction: x is a list
> > > > if x = x i stack (starting with the empty stack). or perhaps you
One way to express the difference (if any) is this:
[..] is a list if and only if [..] i == [..] [] step
(Remember, step is the combinator which sequentially places the elements
of a quotation (second from the top of stack, [..] in the example) onto
the stack and then executes another quotation (on top of stack, [] in the
example) for each member.)
stevan apter — 2005-07-25 10:20:37
----- Original Message -----
From: <phimvt@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, July 25, 2005 1:02 AM
Subject: Re: [stack] stack operations vs function transformation
>
> On Mon, 18 Jul 2005, stevan apter wrote:
>
> >
> > at this point, XY has both lazy AND eager lists.
> >
> > (2 3 +)
> > 5
> >
> > (2 3 5) is translated into [2 3 5] [i] infra.
>
> Won't that give you the list [5 3 2] on top of the stack?
> Also, your i can execute things other than quotations
> (unlike Joy), I take it?
my mistake. (2 3 +) is translated into [[2 3 +]] [i] infra,
which leaves [5] on top of the stack.
i in XY is defined as [X^z Y] -> [X z,Y]. if z is an atom,
then it is prepended to the queue. if z is a quotation, then
its elements are prepended. so e.g.
stack: 1 2 [3 4 5]
queue: i + *
->
stack: 1 2
queue: 3 4 5 + *
->
stack: 1 2 3
queue: 4 5 + *
etc.
stack: 1 2 27
queue:
>
> - Manfred
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
phimvt@lurac.latrobe.edu.au — 2005-07-28 07:52:01
On Mon, 18 Jul 2005, stevan apter wrote:
[..]
> i wound up implementing the following scheme:
>
> [ is defined to push the marker [[ onto the stack.
>
> ] takes everything up to the last [[, enlists it,
> and pushes the result onto the queue.
>
> the evaluator has to know whether [[ is on the stack.
> if it is, primitives other than ] are treated the way
> literals are, viz. they're simply pushed onto the stack.
> defined words, however, are treated the same way: their
> values are pushed onto the queue.
Let me rephrase this in what I hope is equivalent:
CASE current symbol OF
[ : push marker [[ onto stack
] : make a list from the last [[ into a list,
and _append_ it to the queue
anything else : push it onto the stack
END
Now please consider this alternative, in which there is the
possibility of sub-queues:
CASE current symbol OF
[ : start a new sub-queue
] : make a list from the current sub-queue
and _append_ it to the previous queue
anything else : append it to the current queue
END
That would be a way of treating [ and ] inside a sequence
of symbols. Now all symbols denote unary functions, from and
to a collection of queues. That collection is in fact a
stack of queues, quite separate from the usual Joy stack.
Weird? No, it is just the Joy parser, an entirely conventional
recursive descent parser. The stack of queues is constructed
recursively. Something very similar must be inside the Lisp
reader for symbolic expressions. Something like that is also
inside the Pascal compiler for statements, where BEGIN and END
play a similar role as [ and ] in Joy. Again, something
similar occurs (in recursive descent parsing) for expressions
containing ( and ).
There is something else going on, though. Normally one thinks
of a parser/compiler as treating the input program as passive
data, to be translated into some other language - an internal
code, possibly tree code, to be passed onto an interpreter or
another translator, or directly into machine language.
But there is another "perspective": Think of the input program
not as passive data but an active program which produces changes
in the data structures of the parser, similar to the way a runnning
Forth or Joy program produces changes on the stack. In this
perspective a sequence of symbols is indeed flat in the required
sense, each symbol denotes a unary function from parser states to
parser states, and the whole sequence denotes the composition
of the functions denoted by the parts of the sequence.
I was tempted to write QED at the end of this, but I'm not
too convinced that it shows anything of deep interest.
For one thing, parser states are not the sort of thing we
normally compute with. Secondly, languages are usually designed
to allow efficient parsing - without backtracking and without
loops in the parsing process, even if the eventual runtime
execution of the (translated) program requires these.
Nevertheless, there may be something to think about:
flat concatenative semantics for a (sub-)language) which
gets translated into a non-flat language (with or without
concatenative semantics). The target language should allow
at least for loops to be of any use.
Useful? Who knows?
- Manfred