John Cowan — 2004-05-15 14:22:27

On this group we mostly look at Forth, Joy, cK, and friends from the
viewpoint of being concatenative. Henry Baker's paper on Linear Lisp
(http://home.pipeline.com/~hbaker1/ForthStack.html) shows that it's
possible to compile a dialect of Lisp in which all variables must be
used once and only once directly into concatenative notation. This
combines the advantages of named variables with those of stack
programming languages in a very straightforward way.

Furthermore, it's possible (indeed, easy) to represent the Linear
Lisp in a more conventional notation, so that we can mechanically
transform this linear program:

function quadratic(a, b, c) {
var aprime, bprime;
c
var a1 and a2 = dup(a);
var b1 and b2 = dup(b);
return (-b1 + sqrt(square(b2) - 4 * a1 * c) / (2 * a2);
}

into this Linear Lisp program:

(define quadratic (a b c)
(let* ((a1 a2 (dup a)) (b1 b2 (dup b))
(/ (+ (- b1 (sqrt (- (square b) (* 4 (* a1 c)))))
(* 2 a2))))

and thence to (expanding the definition of "square" inline):

roll3 dup roll4 dup neg roll2 dup * 4 roll5 roll6 * * - sqrt + 2 roll3 * /

Now I'm not much of a concatenative programmer, but if I were faced with
the above code, I'd have a hard time figuring out what it did (or
debugging it if it were buggy), whereas the first two versions are
pretty clear and straightforward. It would require discipline to learn
to use variables only once, but it's a constraint the Linear
Lisp compiler can check very easily.

--
Real FORTRAN programmers can program FORTRAN John Cowan
in any language. --Allen Brown jcowan@...

Slava Pestov — 2004-05-15 18:38:26

John Cowan wrote:

>roll3 dup roll4 dup neg roll2 dup * 4 roll5 roll6 * * - sqrt + 2 roll3 * /
>
>

Here is how I would express the quadratic formula in my Factor language:

: quadratic-d ( c a b -- sqrt[b^2 - 4*a*c] )
sq -rot 4 * * - sqrt ;

: quadratic-complete ( a b c -- a b d )
[ 2dup ] dip -rot quadratic-d ;

: quadratic-root ( x y -- -y/x/2 )
neg swap / 2 / ;

: quadratic-roots ( a b d -- alpha beta )
3dup - quadratic-root [ + quadratic-root ] dip ;

: quadratic ( a b c -- alpha beta )
quadratic-complete quadratic-roots ;

Of course if you expand out all the definitions you end up with this:

: quadratic ( a b c -- alpha beta )
[ 2dup ] dip -rot sq -rot 4 * * - sqrt
3dup - neg swap / 2 / [ + neg swap / 2 / ] dip ;

Which is unreadable.

The key to writing good concatenative code, IMHO, is being able to
*name* each little component, and have it do one thing only. While the
first form of the quadratic formula looks verbose, its not really; it
comes down to 5 lines of code, each one is shorter than a line in other
typical languages.

Slava

stevan apter — 2004-05-16 00:52:08

why did you cut

[ 2dup ] dip -rot sq -rot 4 * * - sqrt

where you did? and why have quadratic-complete use quadratic-d,
rather than have:

quadratic-complete quadratic-d quadratic-roots

in APL-land, we're fond of saying that a function should correspond
to a single thought, and that suggests some form of "top-down" analysis,
at each level finding the "joints" between component thoughts until
you've reached some level where it doesn't pay to drill down further.
maybe you've just got primitives at that level; or, no matter how
much code you have to write, it's still feels like just "one thought".

but there's an opposing force operating as well, which is to avoid
cluttering the name-space. sometimes that expresses itself as the
principle that code should have a name only if it's used in more
than one place. in your example, who else but quadratic would use
quadratic-complete?

i think the same question keeps recurring (my wrangle with billy over
variables, john's linear lisp discussion, &c.), which is: is quadratic
"unreadable" because the language doesn't scale psychologically? because
dup and dip and swap and such visually swamp the mathematical content?
because you can't really understand the intent of the math unless you
grasp what pieces of data are being shuffled into place where the math
can do its work? or does it scale, but is "immersion" required?

----- Original Message -----
From: "Slava Pestov" <slava@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, May 15, 2004 2:38 PM
Subject: Re: [stack] Linear languages

> John Cowan wrote:
>
> >roll3 dup roll4 dup neg roll2 dup * 4 roll5 roll6 * * - sqrt + 2 roll3 * /
> >
> >
> Here is how I would express the quadratic formula in my Factor language:
>
> : quadratic-d ( c a b -- sqrt[b^2 - 4*a*c] )
> sq -rot 4 * * - sqrt ;
>
> : quadratic-complete ( a b c -- a b d )
> [ 2dup ] dip -rot quadratic-d ;
>
> : quadratic-root ( x y -- -y/x/2 )
> neg swap / 2 / ;
>
> : quadratic-roots ( a b d -- alpha beta )
> 3dup - quadratic-root [ + quadratic-root ] dip ;
>
> : quadratic ( a b c -- alpha beta )
> quadratic-complete quadratic-roots ;
>
> Of course if you expand out all the definitions you end up with this:
>
> : quadratic ( a b c -- alpha beta )
> [ 2dup ] dip -rot sq -rot 4 * * - sqrt
> 3dup - neg swap / 2 / [ + neg swap / 2 / ] dip ;
>
> Which is unreadable.
>
> The key to writing good concatenative code, IMHO, is being able to
> *name* each little component, and have it do one thing only. While the
> first form of the quadratic formula looks verbose, its not really; it
> comes down to 5 lines of code, each one is shorter than a line in other
> typical languages.
>
> Slava
>
>
>
> Yahoo! Groups Links
>
>
>
>
>

Slava Pestov — 2004-05-16 02:00:05

stevan apter wrote:

>why did you cut
>
> [ 2dup ] dip -rot sq -rot 4 * * - sqrt
>
>where you did?
>

Because I think a word should not "save" some inputs on the stack for
convinience for future words. I factor so that this does not happen, and
each word consumes all parameters.

> quadratic-complete quadratic-d quadratic-roots
>
>
>

This is a good idea.

>but there's an opposing force operating as well, which is to avoid
>cluttering the name-space.
>

I plan hierarchical packages soon.

> sometimes that expresses itself as the
>principle that code should have a name only if it's used in more
>than one place. in your example, who else but quadratic would use
>quadratic-complete?
>
>

Nobody; it just alerts the reader of the code that this particular piece
of code has the name 'quadratic-complete'.

>i think the same question keeps recurring (my wrangle with billy over
>variables, john's linear lisp discussion, &c.), which is: is quadratic
>"unreadable" because the language doesn't scale psychologically? because
>dup and dip and swap and such visually swamp the mathematical content?
>because you can't really understand the intent of the math unless you
>grasp what pieces of data are being shuffled into place where the math
>can do its work? or does it scale, but is "immersion" required?
>

I won't deny it is a bit harder than doing code with local variables,
but its a good skill IMHO, its fun, and the results are very elegant and
reusable. :-)

Slava

John Carter — 2004-05-17 00:01:04

On Sat, 15 May 2004, John Cowan wrote:

> Henry Baker's paper on Linear Lisp
> (http://home.pipeline.com/~hbaker1/ForthStack.html) shows that it's
> possible to compile a dialect of Lisp in which all variables must be
> used once and only once directly into concatenative notation. This
> combines the advantages of named variables with those of stack
> programming languages in a very straightforward way.

Good One! It's wonderful to see my two favourite ideas in the Computing
Universe meet each other!

You see, Manfred's Joy is such a Joy since it permits such simple
analysis, rewriting and reflection.

Linear Logic, of which Henry Baker has long been a champion, is the world
view our minds naturally cope with.

Pointers and aliasing just isn't how the world we learnt in
kindergarten works.

If the ball is in my hand, it's not in yours. If I pass the ball to you,
it is in your hand and no longer in mine.

At a deeply fundamental level we have this ingrained in us. One object,
One name. Here xor There. Mine xor Yours.

Which is why, more often than not, as soon as we deal with pointers that
create aliases for the same object, we get it wrong. Bugs. Bugs. And more
Bugs. (And don't get me started on the subject of Threads and why we are
fundamentally hopeless at dealing with them.)

Now Linear Logic is essentially the logic of reference counting on the
fingers of one thumb. I have the object, or I don't have the object. If I
don't have the object, either I gave someone else the object, or it's
garbage and can be collected instantly and safely.

So combine Joy with Linear logic, and we will have something that is
easily analysable, rewritable, and in line with some of the most deep seated
notions of our psychology.

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand

The universe is absolutely plastered with the dashed lines exactly one
space long.