# Linear languages

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