# DFA and NFA to DFA in Joy

## icpdesign — 2005-09-13 12:40:33

    I found an article by J.V. Noble (Finite State Machines in Forth) that

    describes an elegant implementation of Finite State Machines using

    FORTH  http://www.jfar.org/article001.html

    I am very eager to learn Joy Language by examples, I read many

    examples from the main web site of Joy, but even though the language

    looks very interesting to me, i need more examples/articles to learn

    how to design algorithms/applications in Joy.

    For example I would like to read articles on how to write a compiler

    (from parsing to generating machine code) in Joy.

    I believe writing a book 'Modern Compiler Implementation in Joy' would

    be very interesting;

    Kind regards

    Taoufik

## Ivan Tomac — 2005-09-13 14:23:30

    --- In concatenative@yahoogroups.com, "icpdesign"

    <taoufik.dachraoui@w...> wrote:

     > For example I would like to read articles on how to write a

     compiler

     > (from parsing to generating machine code) in Joy.

    >

    > I believe writing a book 'Modern Compiler Implementation in Joy'

     would

     > be very interesting;

    >

     This is a bit off topic but somewhat related. I've recently been

    reading about the SSA form and it's functional equivalent, ANF

    (Administrative Normal Form) and it got me thinking, since those two

    intermediate representations are both based on lambda calculus, is

    there a combinatorial representation that can be as useful?

    Somehow compiling a concatenative language down to SSA or ANF form

    seems redundant - in case of ANF it's almost like converting Joy-like

    code to some primitive dialect of Scheme. There has to be a more

    suitable intermediate form for concatenative languages.

    I've tried to find some papers on this but the only thing I've found

    so far is a paper called "A combinator-based compiler for a functional

    language" by Hudak and Kranz. Unfortunatly it's only available to ACM

    members so I haven't been able to access it

    (http://portal.acm.org/citation.cfm?id=800523).

    I suspect (this is just a hunch - I could be totally wrong) that a

    stack based intermediate representation is not ideal. Possibly

    something closer to FP and FL would be more suitable. I don't have

    anything concrete to back this up though.

    Ivan

## icpdesign — 2005-09-13 14:43:08

    I was probably not clear, but I meant to use Joy to write compilers

    for other language and was not asking on how to write a compiler for

    Joy.

    The reason I find writing a book 'Modern Compiler implementation in

    Joy' is probably a good idea, is because it will certainly show the

    elegance and power of Joy Language, since implementing an optimized

    compiler contains many challenges.

    It is probably good to have a place where we can find many known

    algorithms found in computer science books written in Joy (ex. NFA-

     >DFA, sorting (quick sort, buble sort, radix sort,...) , shortest

     path, ...)

    Taoufik

     --- In concatenative@yahoogroups.com, "Ivan Tomac" <e1_t@y...> wrote:

    > --- In concatenative@yahoogroups.com, "icpdesign"

    > <taoufik.dachraoui@w...> wrote:

    > > For example I would like to read articles on how to write a

    > compiler

    > > (from parsing to generating machine code) in Joy.

    > >

    > > I believe writing a book 'Modern Compiler Implementation in Joy'

    > would

    > > be very interesting;

    > >

    >

    > This is a bit off topic but somewhat related. I've recently been

    > reading about the SSA form and it's functional equivalent, ANF

    > (Administrative Normal Form) and it got me thinking, since those

    two

    > intermediate representations are both based on lambda calculus, is

    > there a combinatorial representation that can be as useful?

    >

    > Somehow compiling a concatenative language down to SSA or ANF form

    > seems redundant - in case of ANF it's almost like converting Joy-

    like

    > code to some primitive dialect of Scheme. There has to be a more

    > suitable intermediate form for concatenative languages.

    >

    > I've tried to find some papers on this but the only thing I've

    found

    > so far is a paper called "A combinator-based compiler for a

    functional

    > language" by Hudak and Kranz. Unfortunatly it's only available to

    ACM

    > members so I haven't been able to access it

    > (http://portal.acm.org/citation.cfm?id=800523).

    >

    > I suspect (this is just a hunch - I could be totally wrong) that a

    > stack based intermediate representation is not ideal. Possibly

    > something closer to FP and FL would be more suitable. I don't have

    > anything concrete to back this up though.

    >

    > Ivan

## icpdesign — 2005-09-13 14:43:00

    I was probably not clear, but I meant to use Joy to write compilers

    for other language and was not asking on how to write a compiler for

    Joy.

    The reason I find writing a book 'Modern Compiler implementation in

    Joy' is probably a good idea, is because it will certainly show the

    elegance and power of Joy Language, since implementing an optimized

    compiler contains many challenges.

    It is probably good to have a place where we can find many known

    algorithms found in computer science books written in Joy (ex. NFA-

     >DFA, sorting (quick sort, buble sort, radix sort,...) , shortest

     path, ...)

    Taoufik

     --- In concatenative@yahoogroups.com, "Ivan Tomac" <e1_t@y...> wrote:

    > --- In concatenative@yahoogroups.com, "icpdesign"

    > <taoufik.dachraoui@w...> wrote:

    > > For example I would like to read articles on how to write a

    > compiler

    > > (from parsing to generating machine code) in Joy.

    > >

    > > I believe writing a book 'Modern Compiler Implementation in Joy'

    > would

    > > be very interesting;

    > >

    >

    > This is a bit off topic but somewhat related. I've recently been

    > reading about the SSA form and it's functional equivalent, ANF

    > (Administrative Normal Form) and it got me thinking, since those

    two

    > intermediate representations are both based on lambda calculus, is

    > there a combinatorial representation that can be as useful?

    >

    > Somehow compiling a concatenative language down to SSA or ANF form

    > seems redundant - in case of ANF it's almost like converting Joy-

    like

    > code to some primitive dialect of Scheme. There has to be a more

    > suitable intermediate form for concatenative languages.

    >

    > I've tried to find some papers on this but the only thing I've

    found

    > so far is a paper called "A combinator-based compiler for a

    functional

    > language" by Hudak and Kranz. Unfortunatly it's only available to

    ACM

    > members so I haven't been able to access it

    > (http://portal.acm.org/citation.cfm?id=800523).

    >

    > I suspect (this is just a hunch - I could be totally wrong) that a

    > stack based intermediate representation is not ideal. Possibly

    > something closer to FP and FL would be more suitable. I don't have

    > anything concrete to back this up though.

    >

    > Ivan

## John.Cowan — 2005-09-13 15:16:51

    Ivan Tomac scripsit:

     > This is a bit off topic but somewhat related. I've recently been

    > reading about the SSA form and it's functional equivalent, ANF

    > (Administrative Normal Form) and it got me thinking, since those two

    > intermediate representations are both based on lambda calculus, is

    > there a combinatorial representation that can be as useful?

     The first thing is to read Henry Baker's paper on Forth and Linear Lisp:

    http://home.pipeline.com/~hbaker1/ForthStack.html .

    --

    John Cowan  jcowan@...  www.ccil.org/~cowan  www.reutershealth.com

    If I have seen farther than others, it is because I was standing on

    the shoulders of giants.

            --Isaac Newton

## phimvt@lurac.latrobe.edu.au — 2005-09-14 08:13:24

    On Tue, 13 Sep 2005, icpdesign wrote:

     > I was probably not clear, but I meant to use Joy to write compilers

    > for other language and was not asking on how to write a compiler for

    > Joy.

     If you just want to see how (extremely simple) translations can be done,

    on the Joy page look at

        The basic library  symlib.joy  (symbol manipulation, translation)

          which is used by the paper "Fast small truth tables"

          and in the special library  plglib.joy (propositional logic);

        The special library grmlib.joy  (grammars)

    If you look at them from the Joy page, you will also see the test

    files and the outputs.

     > The reason I find writing a book 'Modern Compiler implementation in

    > Joy' is probably a good idea, is because it will certainly show the

    > elegance and power of Joy Language, since implementing an optimized

    > compiler contains many challenges.

     Indeed, but the language in which the compiler is written does

    not really help in solving the optimisation difficulties. Once

    an optimisation problem has been solved, compilers written in any

    language can then use it.

    [..]

      - Manfred

## Greg Buchholz — 2005-09-14 16:23:23

    --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...> wrote:

     > The first thing is to read Henry Baker's paper on Forth and Linear

    > Lisp: http://home.pipeline.com/~hbaker1/ForthStack.html .

    >

         I wonder if any work been done on a linear version of Joy with no

    garbage collector, like in...

      Lively Linear Lisp -- 'Look Ma, No Garbage!'

        http://home.pipeline.com/~hbaker1/LinearLisp.html

    ...I started looking into creating a Joy compiler which kept all data

    on the stack, but soon realized that quite a few of Joy's primitives

    have a non-linear implementation.  That's not too surprising since

    'dup' is a non-linear operation.   Making it worse is the fact that

    (unlike 'dup') many comibnators (ifte, map, linrec, etc.) have

    multiple pointers to the entire stack (i.e. not to a fixed number of

    the top N stack items).  For example, if you think of 'ifte' as a

    function from stacks->stacks, a Scheme implementation might look like...

     (define (ifte stack)

        (match-let (((f t b . rest) stack))

             (if (car (b rest))

                 (t rest)

                 (f rest))))

    ...where "match-let" does a destructuring bind (pattern matching) on

    the stack.  You can see that the executing the predicate quotation "b"

    needs a pointer to the "rest" of the stack and the arms of the

    conditional need a pointer to the rest of the stack.  'ifte'

    implemented in a linear Joy might look like...

                         (* rest [b] [t] [f] ifte                  *)

    ifte == [stack] 3dip (* ball up the "rest" into a list         *)

            2infra_dip   (* execute the "b" quotation on ["rest"]  *)

            [first] 2dip (* grab the boolean from the fake stack   *)

            branch       (* the linear conditional                 *)

    3dip == (* dip under top 3 stack items *)

    2dip == (* dip under 2 stack items *)

    2infra_dip == (* dip under top 2 stack items and use infra *)

    That's essentially performing a 'dup' on the entire rest of the stack

    (which seems inefficient).  There are a couple of ways dealing with

    this.  First we could try and eliminate these non-linear combinators,

    trying to come up with another set of primitives.  But that might

    clutter up the code by making some (now hidden) stack shuffling more

    explicit.  We could perform a stack-effect inference before we execute

    the non-linear combinators and only 'dup' the N items we determine get

    'popped'.  Unless the inference was done statically at compile time,

    it might be more expensive than simply copying the remaining stack.

    Or we could implement a lazy version of the 'stack' combinator, which

    copies stack items to a scratch area on demand.  Any other thoughts?

    Thanks,

    Greg Buchholz

## Ivan Tomac — 2005-09-15 00:13:55

    --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...> wrote:

     > Ivan Tomac scripsit:

    >

    > > This is a bit off topic but somewhat related. I've recently been

    > > reading about the SSA form and it's functional equivalent, ANF

    > > (Administrative Normal Form) and it got me thinking, since those two

    > > intermediate representations are both based on lambda calculus, is

    > > there a combinatorial representation that can be as useful?

    >

    > The first thing is to read Henry Baker's paper on Forth and Linear Lisp:

    > http://home.pipeline.com/~hbaker1/ForthStack.html .

    >

     I've read about Linear Lisp before but using something resembling

    Linear Lisp as an intermediate form doesn't seem much different to

    just using ANF (or SSA) and adding the additional restriction that all

    variables can only ever be read once. You still have variables.

    On the other hand having a more Forth like intermediate representation

    may be less useful (or rather less practical) for doing optimizations

    such as dead code elimination, constant propagation and similar things.

    Ivan

## Ivan Tomac — 2005-09-15 00:22:12

    --- In concatenative@yahoogroups.com, "Greg Buchholz"

    <sleepingsquirrel@y...> wrote:

     > --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...> wrote:

    > > The first thing is to read Henry Baker's paper on Forth and Linear

    > > Lisp: http://home.pipeline.com/~hbaker1/ForthStack.html .

    > >

    >

    >     I wonder if any work been done on a linear version of Joy with no

    > garbage collector, like in...

    >

     Joy doesn't need a garbage collector as deallocation is always explicit.

    In other words pop could simply pop the stack in case the element on

    top of the stack is an atom or in case of a list it could free the

    list recursively.

    This relies on complete duplication of the element on top of the stack

    when dup is executed (i.e. duplicating pointers simply won't work here).

    Ivan

## John.Cowan — 2005-09-15 01:46:36

    Ivan Tomac scripsit:

     > I've read about Linear Lisp before but using something resembling

    > Linear Lisp as an intermediate form doesn't seem much different to

    > just using ANF (or SSA) and adding the additional restriction that all

    > variables can only ever be read once. You still have variables.

     The point of the paper is that Linear Lisp can be compiled to a Forth

    intermediate form in which the variables disappear.  So it would be

    more accurate to say that you appear to have variables, but they

    do not correspond to named run-time locations.  Everything's on

    the stack.

     > On the other hand having a more Forth like intermediate representation

    > may be less useful (or rather less practical) for doing optimizations

    > such as dead code elimination, constant propagation and similar things.

     By the same token, a concatenative language can be decompiled to

    Linear Lisp.

     > Joy doesn't need a garbage collector as deallocation is always explicit.

    > In other words pop could simply pop the stack in case the element on

    > top of the stack is an atom or in case of a list it could free the

    > list recursively.

    > This relies on complete duplication of the element on top of the stack

    > when dup is executed (i.e. duplicating pointers simply won't work here).

     Indeed, you never need a garbage collector if you are constrained to

    never have two pointers point at the same thing.  This is an expensive

    restriction, to be sure.

    Both Joy0 and Joy1 have garbage collectors.

    --

    Is not a patron, my Lord [Chesterfield],        John Cowan

    one who looks with unconcern on a man           http://www.ccil.org/~cowan

    struggling for life in the water, and when      http://www.reutershealth.com

    he has reached ground encumbers him with help?          jcowan@...

            --Samuel Johnson

## Ivan Tomac — 2005-09-15 02:56:03

    --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...> wrote:

     > Ivan Tomac scripsit:

    >

    > > I've read about Linear Lisp before but using something resembling

    > > Linear Lisp as an intermediate form doesn't seem much different to

    > > just using ANF (or SSA) and adding the additional restriction

     that all

     > > variables can only ever be read once. You still have variables.

    >

    > The point of the paper is that Linear Lisp can be compiled to a

     Forth

     > intermediate form in which the variables disappear.  So it would be

    > more accurate to say that you appear to have variables, but they

    > do not correspond to named run-time locations.  Everything's on

    > the stack.

    >

    > > On the other hand having a more Forth like intermediate

     representation

     > > may be less useful (or rather less practical) for doing

     optimizations

     > > such as dead code elimination, constant propagation and similar

     things.

     >

    > By the same token, a concatenative language can be decompiled to

    > Linear Lisp.

    >

     Yes. But that still leaves you to convert a concatenative program into

    an intermediate form based on lambda calculus.

    What I'm asking is (I probably didn't make that clear in my previous

    post) is there an intermediate form based on combinatory calculus that

    is as practical as SSA and ANF are when it comes to optimizations?

     > > Joy doesn't need a garbage collector as deallocation is always

     explicit.

     > > In other words pop could simply pop the stack in case the element

     on

     > > top of the stack is an atom or in case of a list it could free the

    > > list recursively.

    > > This relies on complete duplication of the element on top of the

     stack

     > > when dup is executed (i.e. duplicating pointers simply won't work

     here).

     >

    > Indeed, you never need a garbage collector if you are constrained to

    > never have two pointers point at the same thing.  This is an

     expensive

     > restriction, to be sure.

    >

     True. However this is how Linear Lisp works as well - all duplication

    is explicit and complete - nothing is shared.

     > Both Joy0 and Joy1 have garbage collectors.

    >

    > --

    > Is not a patron, my Lord [Chesterfield],        John Cowan

    > one who looks with unconcern on a man

     http://www.ccil.org/~cowan

     > struggling for life in the water, and when

     http://www.reutershealth.com

     > he has reached ground encumbers him with help?          jcowan@r...

    >         --Samuel Johnson

     Ivan

## Narcoleptic Electron — 2005-09-15 05:24:55

    On 9/14/05, Ivan Tomac <e1_t@...> wrote:

     > --- In concatenative@yahoogroups.com, "Greg Buchholz"

    > <sleepingsquirrel@y...> wrote:

    > > --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...> wrote:

    > > > The first thing is to read Henry Baker's paper on Forth and Linear

    > > > Lisp: http://home.pipeline.com/~hbaker1/ForthStack.html .

    > > >

    > >

    > >     I wonder if any work been done on a linear version of Joy with no

    > > garbage collector, like in...

    > >

    >

    > Joy doesn't need a garbage collector as deallocation is always explicit.

    > In other words pop could simply pop the stack in case the element on

    > top of the stack is an atom or in case of a list it could free the

    > list recursively.

    > This relies on complete duplication of the element on top of the stack

    > when dup is executed (i.e. duplicating pointers simply won't work here).

    >

     A more efficient approach would be a copy-on-write scheme, employing a

    reference count behind the scenes.

    (The off-the-top-of-my-head implementation is something like the

    following: the stack holds pointers to reference-counted values.

    'dup' duplicates the pointer and increments the reference count on the

    value.  When about to manipulate the 'copy' in any way (language

    permitting), the reference count is checked: if greater than 1,

    decrement it and make a copy (with reference count of 1) that the

    pointer now points to.  When 'drop'/'pop' is called, the reference

    count on the object is reduced, and the object is deallocated if it is

    0.)

    Reference counts are only problematic when there are cyclical retains.

     I can't think of a way that such a cycle could happen with this

    scheme.  Anyone?

## Martin Young — 2005-09-15 07:37:51

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

     > A more efficient approach would be a copy-on-write scheme,

     employing a

     > reference count behind the scenes.

    >

    > (The off-the-top-of-my-head implementation is something like the

    > following: the stack holds pointers to reference-counted values.

    > 'dup' duplicates the pointer and increments the reference count on

     the

     > value.  When about to manipulate the 'copy' in any way (language

    > permitting), the reference count is checked: if greater than 1,

    > decrement it and make a copy (with reference count of 1) that the

    > pointer now points to.  When 'drop'/'pop' is called, the reference

    > count on the object is reduced, and the object is deallocated if

     it is

     > 0.)

    >

    > Reference counts are only problematic when there are cyclical

     retains.

     >  I can't think of a way that such a cycle could happen with this

    > scheme.  Anyone?

     That's exactly how MONKEY (implmented in C) does garbage

    collection.  So far, no uncollectable data have appeared (bugs and

    misfeatures excepted).

## John.Cowan — 2005-09-15 13:13:51

    Narcoleptic Electron scripsit:

     > Reference counts are only problematic when there are cyclical retains.

    >  I can't think of a way that such a cycle could happen with this

    > scheme.  Anyone?

     Joy currently has no primitives analogous to set-car! and set-cdr! for

    creating circular lists.  However, it would be necessary to have a

    reference count for every list cell.  That's expensive in space.

    Furthermore, reference counting isn't necessarily cheap in either time

    or space, since it's necessary to update the counts recursively and to

    use a private stack to keep track.

    --

    May the hair on your toes never fall out!       John Cowan

            --Thorin Oakenshield (to Bilbo)         jcowan@...

## Narcoleptic Electron — 2005-09-15 16:48:41

    Martin Young wrote:

     > Narcoleptic Electron wrote:

    > > A more efficient approach would be a copy-on-write scheme,

    > > employing a reference count behind the scenes.

    > >

    > That's exactly how MONKEY (implmented in C) does garbage

    > collection.  So far, no uncollectable data have appeared (bugs and

    > misfeatures excepted).

     I'll check it out!  Thanks.

    John.Cowan wrote:

     > Narcoleptic Electron scripsit:

    > > Reference counts are only problematic when there are cyclical retains.

    > >  I can't think of a way that such a cycle could happen with this

    > > scheme.  Anyone?

    >

    > Joy currently has no primitives analogous to set-car! and set-cdr! for

    > creating circular lists.  However, it would be necessary to have a

    > reference count for every list cell.  That's expensive in space.

    > Furthermore, reference counting isn't necessarily cheap in either time

    > or space, since it's necessary to update the counts recursively

     Counts would not need to be updated recursively-- only one level in.

    Consider an example: a pointer to a list is on the top of the stack.

    'dup' is called.  The list's reference count is incremented, none of

    the list contents are touched, and a new pointer to the list is

    pushed.  Now some operation is to happen on the list, so:

    - The reference count on the list is decremented.

    - The list is copied.  What this means: the list 'object' is shallow

    copied, and the reference count on each item in the list is

    incremented.  Nothing recursive.

    - The pointer at the top of the list now points to the new list value.

    - The operation happens.

    There is still a little overhead (space for reference counts, time in

    incrementing), but this still beats a deep (recursive) copy every time

    'dup' is called.  The price has to be paid somewhere.

     > and to use a private stack to keep track.

     I'm not sure what you mean here.

## John.Cowan — 2005-09-15 20:08:13

    Narcoleptic Electron scripsit:

     > Counts would not need to be updated recursively-- only one level in.

     The problem comes in when you free a list: you then have to decrement

    the reference counts of the members, and potentially free them too,

    and so on.  Google for "recursive freeing".

    And because you can get a pointer to the middle of a list in Joy, you

    still can't escape one reference count per cons cell.

    --

    John Cowan                                   jcowan@...

            "You need a change: try Canada"  "You need a change: try China"

                    --fortune cookies opened by a couple that I know

## Narcoleptic Electron — 2005-09-15 20:24:59

    On 9/15/05, John.Cowan <cowan@...> wrote:

     > Narcoleptic Electron scripsit:

    > > Counts would not need to be updated recursively-- only one level in.

    >

    > The problem comes in when you free a list: you then have to decrement

    > the reference counts of the members, and potentially free them too,

    > and so on.  Google for "recursive freeing".

     The keyword there is "potentially", rather than "necessarily", as

    would be the case in the "deep copy dup" scenario.  You only need to

    recurse until you hit a reference count that's greater than 0.  In my

    previous example, that is one level.

     > And because you can get a pointer to the middle of a list in Joy, you

    > still can't escape one reference count per cons cell.

     I didn't say that one could escape that.  Even if you could get a

    pointer to the middle of a list, I don't know how this could be

    avoided.  This is the space drawback I mentioned.  There are no free

    lunches, but some are cheaper than others, and  "Deep copy dup" still

    seems comparatively expensive.

## Narcoleptic Electron — 2005-09-15 20:27:12

    On 9/15/05, Narcoleptic Electron <narcoleptic.electron@...> wrote:

     > Martin Young wrote:

    > > Narcoleptic Electron wrote:

    > > > A more efficient approach would be a copy-on-write scheme,

    > > > employing a reference count behind the scenes.

    > > >

    > > That's exactly how MONKEY (implmented in C) does garbage

    > > collection.  So far, no uncollectable data have appeared (bugs and

    > > misfeatures excepted).

    >

    > I'll check it out!  Thanks.

     Google has failed me.  Do you have a URL for Monkey info?

## Martin Young — 2005-09-15 20:41:28

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

     > Google has failed me.  Do you have a URL for Monkey info?

     Sorry, no I don't.

    MONKEY is my own Joy-alike; should have mentioned that in my post.

    There's nothing clever about the GC in MONKEY and no special results

    to report.  It does exactly what you suggested (ref count in each

    list cell, doesn't worry about cyclic structures).  It has all the

    advantages and disadvantages discussed on this list.  I used it

    precisely to avoid the cost of a deep-dup.

    The only interesting feature, and I've get to build a correctly

    functioning implementation of this, is that the recursive garbage

    collection can be done in-place and in zero-space.  That is, you can

    use collected cells to store a pseudo-return stack for the recursive

    collector.  Thus it uses no memory in the MONKEY domain, and no

    (recursion-caused) stack space in the implementation language.

## William Tanksley, Jr — 2005-09-15 22:19:19

    Greg Buchholz <sleepingsquirrel@...> wrote:

     >     I wonder if any work been done on a linear version of Joy with no

    > garbage collector, like in...

    >   Lively Linear Lisp -- 'Look Ma, No Garbage!'

    >     http://home.pipeline.com/~hbaker1/LinearLisp.html

     I like Baker's essay titled "Linear Logic: The Forth Shall Be First"

    is more appropos to this group :-), and to your question.

     > ...I started looking into creating a Joy compiler which kept all data

    > on the stack, but soon realized that quite a few of Joy's primitives

    > have a non-linear implementation.  That's not too surprising since

    > 'dup' is a non-linear operation.

     dup is only nonlinear if you choose to expose pointers. It's linear if

    it duplicates the data itself. Yes, that's potentially slow (although

    Baker argues that it's not neccesarily so -- consider his hash-based

    consing VM), but the slow operations can be avoided and replaced with

    others which are not slow. Programmers are good at that.

    (Or so the argument goes -- I have little experience to argue one way

    or the other.)

     >Making it worse is the fact that

    > (unlike 'dup') many comibnators (ifte, map, linrec, etc.) have

    > multiple pointers to the entire stack (i.e. not to a fixed number of

    > the top N stack items).  For example, if you think of 'ifte' as a

    > function from stacks->stacks, a Scheme implementation might look like...

     Yes, frankly I've never liked that about Joy. I think we'd have to say

    that a pure version of Joy as it's defined now couldn't be linear; but

    I do think it's reasonable to speak of a Linear Joy, with just enough

    changes to be linear.

     > this.  First we could try and eliminate these non-linear combinators,

    > trying to come up with another set of primitives.  But that might

    > clutter up the code by making some (now hidden) stack shuffling more

    > explicit.

     This is the only solution that's really stable, IMO. Everything else

    hides work that actually *has* to be done, making efficient-looking

    code actually inefficient. If you're going to write a linear-logic

    language, it should *look* linear. That way, also, mistakes won't be

    hidden.

     > Greg Buchholz

     -Billy

## William Tanksley, Jr — 2005-09-15 23:55:23

    Ivan Tomac <e1_t@...> wrote:

     > --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...> wrote:

    > > Ivan Tomac scripsit:

    > > By the same token, a concatenative language can be decompiled to

    > > Linear Lisp.

    > Yes. But that still leaves you to convert a concatenative program into

    > an intermediate form based on lambda calculus.

     Unless, of course, you could write an efficient compiler for an

    intermediate form naturally derived from the concatentative calculus.

    I suspect, but do not have proof, that this isn't hard.

     > What I'm asking is (I probably didn't make that clear in my previous

    > post) is there an intermediate form based on combinatory calculus that

    > is as practical as SSA and ANF are when it comes to optimizations?

     I think that a dataflow graph would be at least as good -- if my

    understanding is correct, SSA has to be converted into a dataflow

    graph anyhow. And dataflow isn't hard to extract from concatenative

    notation; I believe it's linear time.

    I think that SSA is merely an intermediate step that gets rid of

    multiple assignment as seen in languages like C, thereby allowing

    lambda-based rules to be applied in order to permit dataflow analysis.

    IIRC.

     > Ivan

     -Billy

## Ivan Tomac — 2005-09-16 01:19:14

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@g...> wrote:

     > Ivan Tomac <e1_t@y...> wrote:

    > > --- In concatenative@yahoogroups.com, "John.Cowan" <cowan@c...>

     wrote:

     > > > Ivan Tomac scripsit:

    > > > By the same token, a concatenative language can be decompiled to

    > > > Linear Lisp.

    >

    > > Yes. But that still leaves you to convert a concatenative program

     into

     > > an intermediate form based on lambda calculus.

    >

    > Unless, of course, you could write an efficient compiler for an

    > intermediate form naturally derived from the concatentative

     calculus.

    That is exactly what I'm saying - converting concatenative programs

    into a lambda-calculus based form seems redundant.

     > I suspect, but do not have proof, that this isn't hard.

    >

     I suspect that it's no harder then writing an efficient backend for a

    lambda calculus based language which is still not trivial (the keyword

    being efficient).

     > > What I'm asking is (I probably didn't make that clear in my

     previous

     > > post) is there an intermediate form based on combinatory calculus

     that

     > > is as practical as SSA and ANF are when it comes to optimizations?

    >

    > I think that a dataflow graph would be at least as good -- if my

    > understanding is correct, SSA has to be converted into a dataflow

    > graph anyhow. And dataflow isn't hard to extract from concatenative

    > notation; I believe it's linear time.

    >

     If my understanding is correct, SSA is a data and control flow graph.

     > I think that SSA is merely an intermediate step that gets rid of

    > multiple assignment as seen in languages like C, thereby allowing

    > lambda-based rules to be applied in order to permit dataflow

     analysis.

     > IIRC.

    >

     Many functional languages use intermediate forms that are similar to

    SSA. GHC's Spineless Taggless G-Machine

    (http://citeseer.csail.mit.edu/peytonjones92implementing.html) for

    example is a variant of ANF which is very similar to SSA.

    Here's an interesting paper about ANF:

    http://citeseer.ist.psu.edu/chakravarty03functional.html

     >

    > -Billy

     Ivan

## William Tanksley, Jr — 2005-09-16 02:57:43

    Ivan Tomac <e1_t@...> wrote:

     >"William Tanksley, Jr" <wtanksleyjr@g...> wrote:

    > > I suspect, but do not have proof, that this isn't hard.

    > I suspect that it's no harder then writing an efficient backend for a

    > lambda calculus based language which is still not trivial (the keyword

    > being efficient).

     "Efficient" is ambiguous; I think the two systems are different enough

    that any comparison will only show that one always beats the other at

    some benchamrks and loses at some others :-).

    More usefully, I suspect that a brain-dead trivial optimizer for a

    decent concatenative language is far more effective at producing code

    that is both small and fast than an equivalently brain-dead optimizer

    for a lambda-based language. I haven't written even a trivial

    optimizer for a concatenative language, but I did write a brain-dead

    trivial optimizer for Oberon. It took me WAY longer than the 1 day it

    took my friend to write an optimizer for Forth, and his results were

    generally useful (my results only optimised a few special cases, and

    were a little buggy anyhow).

    So my suspicions are a bit grounded in reality -- but I also suspect

    that after 10 years of research, both methods will be neck-and-neck.

     > > I think that a dataflow graph would be at least as good -- if my

    > > understanding is correct, SSA has to be converted into a dataflow

    > > graph anyhow. And dataflow isn't hard to extract from concatenative

    > > notation; I believe it's linear time.

    > If my understanding is correct, SSA is a data and control flow graph.

     http://en.wikipedia.org/wiki/Static_single_assignment_form

    No, it's a way to convert assignment-based code into single-assignment

    code (i.e. all variables become constants). You can construct a data

    and control flow graph more easily from the result. Again, the whole

    SSA step is unneeded with a concatenative language (unless someone

    insists on using locals ;-).

     > Ivan

     -Billy

## Narcoleptic Electron — 2005-09-16 19:43:09

    On 9/15/05, Martin Young <martin@...> wrote:

     > The only interesting feature, and I've get to build a correctly

    > functioning implementation of this, is that the recursive garbage

    > collection can be done in-place and in zero-space.  That is, you can

    > use collected cells to store a pseudo-return stack for the recursive

    > collector.  Thus it uses no memory in the MONKEY domain, and no

    > (recursion-caused) stack space in the implementation language.

     Keep me posted!

## phimvt@lurac.latrobe.edu.au — 2005-09-19 09:17:51

    On Thu, 15 Sep 2005, William Tanksley, Jr wrote:

     > Greg Buchholz <sleepingsquirrel@...> wrote:

     [..]

     > >Making it worse is the fact that

    > > (unlike 'dup') many comibnators (ifte, map, linrec, etc.) have

    > > multiple pointers to the entire stack (i.e. not to a fixed number of

    > > the top N stack items).  For example, if you think of 'ifte' as a

    > > function from stacks->stacks, a Scheme implementation might look like...

    >

    > Yes, frankly I've never liked that about Joy. I think we'd have to say

    > that a pure version of Joy as it's defined now couldn't be linear; but

    > I do think it's reasonable to speak of a Linear Joy, with just enough

    > changes to be linear.

     Some time ago I had an idea that might be useful for at least

    some of the troublesome cases. I'll illustrate with the ifte combinator:

    Suppose we have the stack with lots of stuff:

      1 2 3 4 5 10 11 12 20 21

    and an ifte program

      [pop pop succ succ + >] [thenpart] [elsepart] ifte

    The ifpart will consume from 21 down to 10. These consumed values

    have to be restored before the thenpart or the elsepart can be

    executed. One remedy: in addition to the normal mode of operation,

    have another, "restoring mode", used mainly inside tests as in

    ifte, linrec and others. In restoring mode any consumed values

    are placed on a relatively small "restoring stack". It is somewhat

    similar to what Forth programmers do manually on the Forth return

    stack, except that it is automatic in restoring mode. In the

    example, in restoring mode the following happens:

       1. the first pop removes the 21 by shifting it onto the

          restoring stack.

       2. the second pop does the same to the 20.

       3. the first succ replaces the 12 by 1 to give 13, but shifts

          the original 12 onto the restoring stack. The computed

          13 is flagged with "not original".

       4. the second succ is operating on the 13 whose original (12)

          has already been shifted. So, no new shift is needed,

          and the 14 is also flagged "not original".

       5. The + adds 11 and 14 to give 25. The 11 is newly consumed,

          but the 14 is not one of the originals, it was the result

          of a previous operation, . So only the 11 is shifted onto

          the restoring stack.

       6. The > compares the 10 and the 25 (to give false). In so

          doing, it consumes the original 10 which has to be shifted.

          But the other argument, 25 was produced by an operation,

          and hence no new shift is needed.

       7. The computed truth value false is saved, the saved values

          are shifted back to the stack, the previous, presumably

          normal mode is reinstated, and the elsepart is executed.

    The contorted example illustrates most aspects of the mechanism

    for the restoring mode. At least for the ifte, linrec and similar

    combinators the number of values consumed by the ifpart are not

    very great, so the overhead is not excessive. But having the

    interpreter doing the shifting and restoring automatically

    certainnly beats the errorprone way of doing it manually.

    Of course it comes at the cost of having these two modes of

    operation, and in the new restoring mode having to decide

    whether to shift or not.

    I should think that the usefulness of such a device is not

    restricted to Joy with its combinator which find their parameters

    on the stack. It could also be used in Forth or other languages

    in which the text of the parameters is enclosed not in [ and ]

    (and hence pushed as a quotation) but syntactically as in

        IF ifpart THEN thenpart ELSE elsepart END

        IF ifpart THEN elsepart LIN rec1part REC rec2part END

    or similar.

     > > this.  First we could try and eliminate these non-linear combinators,

    > > trying to come up with another set of primitives.  But that might

    > > clutter up the code by making some (now hidden) stack shuffling more

    > > explicit.

     Yes, there may be some non-linear combinators for which the

    automatic restoring mode does not work. But I don't know which

    ones they may be.

      - Manfred

## John.Cowan — 2005-09-19 12:23:38

    phimvt@... scripsit:

     > I should think that the usefulness of such a device is not

    > restricted to Joy with its combinator which find their parameters

    > on the stack. It could also be used in Forth or other languages

    > in which the text of the parameters is enclosed not in [ and ]

    > (and hence pushed as a quotation) but syntactically as in

    >     IF ifpart THEN thenpart ELSE elsepart END

    >     IF ifpart THEN elsepart LIN rec1part REC rec2part END

    > or similar.

     In fact, Forth does not syntactically control the if-part, and is not

    aware that a program is executing one: the syntax is

    	ifpart IF thenpart ELSE elsepart THEN

    The word "then" is used in a different sense from the usual.

    --

    Using RELAX NG compact syntax to        John Cowan

    develop schemas is one of the simple    http://www.reutershealth.com

    pleasures in life....                   http://www.ccil.org/~cowan

            --Jeni Tennison                 <jcowan@...>

## William Tanksley, Jr — 2005-09-20 01:16:34

    phimvt@... <phimvt@...> wrote:

     > William Tanksley, Jr wrote:

    > > Greg Buchholz <sleepingsquirrel@...> wrote:

    > [..]

    > > >Making it worse is the fact that

    > > > (unlike 'dup') many comibnators (ifte, map, linrec, etc.) have

    > > > multiple pointers to the entire stack (i.e. not to a fixed number of

    > > > the top N stack items).  For example, if you think of 'ifte' as a

    > > > function from stacks->stacks, a Scheme implementation might look like...

    > > Yes, frankly I've never liked that about Joy. I think we'd have to say

    > > that a pure version of Joy as it's defined now couldn't be linear; but

    > > I do think it's reasonable to speak of a Linear Joy, with just enough

    > > changes to be linear.

    > Some time ago I had an idea that might be useful for at least

    > some of the troublesome cases. I'll illustrate with the ifte combinator:

     The ifte combinator is one of the troublesome cases -- it's nonlinear,

    because it duplicates pointers without duplicating data.

     > Suppose we have the stack with lots of stuff:

    >   1 2 3 4 5 10 11 12 20 21

    > and an ifte program

    >   [pop pop succ succ + >] [thenpart] [elsepart] ifte

    > The ifpart will consume from 21 down to 10. These consumed values

    > have to be restored before the thenpart or the elsepart can be

    > executed. One remedy: in addition to the normal mode of operation,

    > have another, "restoring mode", used mainly inside tests as in

    > ifte, linrec and others. In restoring mode any consumed values

    > are placed on a relatively small "restoring stack". It is somewhat

    > similar to what Forth programmers do manually on the Forth return

    > stack, except that it is automatic in restoring mode. In the

    > example, in restoring mode the following happens:

     I think it would be better to make stack shuffles really really easy,

    so that people don't have to wonder what mode they're in.

    So the above notation might be:

      [abcd--abcdab succ succ + >] [thenpart] [elsepart] ifte

    That's linear (or at least it can be, if the language is linear) --

    the only duplication is explicit.

     > very great, so the overhead is not excessive. But having the

    > interpreter doing the shifting and restoring automatically

    > certainnly beats the errorprone way of doing it manually.

     I don't understand this. I've never seen it done automatically before

    looking at Joy, and I don't find it convenient -- it's just another

    thing to remember, for me. You still have to keep track of the same

    stack items, but now you have to remember that some words "throw away"

    some of the stack state you generate. If you find tracking stack state

    inconvenient, why are you programming in a concatenative language, and

    how could it be convenient to have a context where stack manipulations

    sometimes get ignored?

    My argument is doubly strong for linear languages, in which that sort

    of thing just can't happen. If you do that automatic duplication, your

    language isn't linear.

     >   - Manfred

     -Billy

## phimvt@lurac.latrobe.edu.au — 2005-09-21 05:57:57

    On Mon, 19 Sep 2005, John.Cowan wrote:

     > phimvt@... scripsit:

    >

    > > I should think that the usefulness of such a device is not

    > > restricted to Joy with its combinator which find their parameters

    > > on the stack. It could also be used in Forth or other languages

    > > in which the text of the parameters is enclosed not in [ and ]

    > > (and hence pushed as a quotation) but syntactically as in

    > >     IF ifpart THEN thenpart ELSE elsepart END

    > >     IF ifpart THEN elsepart LIN rec1part REC rec2part END

    > > or similar.

    >

    > In fact, Forth does not syntactically control the if-part, and is not

    > aware that a program is executing one: the syntax is

    >

    > 	ifpart IF thenpart ELSE elsepart THEN

    >

    > The word "then" is used in a different sense from the usual.

     Yes, thank you. I was aware of how Forth does it, that is why I said "or

    similar". But thinking about this suggested another use for the restoring

    mode is in implementing the nullary combinator, which behaves like this:

        10 11 12 [*] nullary    ==>   10 11 12 121

    The restoring mode could be used here to save the values 11 and 12

    which would otherwise be lost by the multiplication.

    It had not occurred to me before that

            [ifpart] [thenpart] [elsepart] ifte

        ==  [ifpart] nullary [thenpart] [elsepart] branch

        ==  [ifpart] [thenpart] [elsepart] [nullary] dipd branch

    and hence

            ifte  ==  [nullary] dipd branch

    where the branch combinator takes two quotations and below that a truth

    value and hence behaves rather like Forth's conditional. The dipd

    combinator is like the dip combinator in that it takes a quotation

    but instead of saving and restoring one value it does the same for two.

    One might usefully combine the action of nullary and dipd by defining

            nullarydd == [nullary] dipd

    and then

            ifte  ==  nullarydd branch

    Thank you

       - Manfred

     >

    > --

    > Using RELAX NG compact syntax to        John Cowan

    > develop schemas is one of the simple    http://www.reutershealth.com

    > pleasures in life....                   http://www.ccil.org/~cowan

    >         --Jeni Tennison                 <jcowan@...>

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## phimvt@lurac.latrobe.edu.au — 2005-09-21 06:42:24

    On Mon, 19 Sep 2005, William Tanksley, Jr wrote:

     > phimvt@... <phimvt@...> wrote:

    > > William Tanksley, Jr wrote:

    > > > Greg Buchholz <sleepingsquirrel@...> wrote:

    > > [..]

    > > > >Making it worse is the fact that

    > > > > (unlike 'dup') many comibnators (ifte, map, linrec, etc.) have

    > > > > multiple pointers to the entire stack (i.e. not to a fixed number of

    > > > > the top N stack items).  For example, if you think of 'ifte' as a

    > > > > function from stacks->stacks, a Scheme implementation might look like...

    >

    > > > Yes, frankly I've never liked that about Joy. I think we'd have to say

    > > > that a pure version of Joy as it's defined now couldn't be linear; but

    > > > I do think it's reasonable to speak of a Linear Joy, with just enough

    > > > changes to be linear.

    >

    > > Some time ago I had an idea that might be useful for at least

    > > some of the troublesome cases. I'll illustrate with the ifte combinator:

    >

    > The ifte combinator is one of the troublesome cases -- it's nonlinear,

    > because it duplicates pointers without duplicating data.

     What the ifte combbinator duplicates depends very much on the

    implmentation. You could have it always duplicate data or always

    duplicate pointers, or you could have it duplicate numbers and other

    small values but duplicate pointers for large values such as strings

    or quotations (lists). The current implementation of Joy takes the third,

    mixed alternative. But the user will never be aware of which of the

    three alternative implementation methods is chosen.

     > > Suppose we have the stack with lots of stuff:

    > >   1 2 3 4 5 10 11 12 20 21

    > > and an ifte program

    > >   [pop pop succ succ + >] [thenpart] [elsepart] ifte

    >

    > > The ifpart will consume from 21 down to 10. These consumed values

    > > have to be restored before the thenpart or the elsepart can be

    > > executed. One remedy: in addition to the normal mode of operation,

    > > have another, "restoring mode", used mainly inside tests as in

    > > ifte, linrec and others. In restoring mode any consumed values

    > > are placed on a relatively small "restoring stack". It is somewhat

    > > similar to what Forth programmers do manually on the Forth return

    > > stack, except that it is automatic in restoring mode. In the

    > > example, in restoring mode the following happens:

    >

    > I think it would be better to make stack shuffles really really easy,

    > so that people don't have to wonder what mode they're in.

     Users should not need to know how the stack is implemented - as

    a linked list or as an array. The current Joy uses a linked list,

    which makes combinators like ifte, linrec and others particularly

    easy to implement. If an array is chosen, those same combinators

    should have the same semantics - in particular, executing the

    ifpart should not destroy values on the stack. The "restoring

    mode" was a suggestion to make the restoring automatic for

    an array implementation. Users need not know that an array is used

    together with an auxiliary "restoring stack". So users certainly

    do not have to worry what mode they are in.

     > So the above notation might be:

    >

    >   [abcd--abcdab succ succ + >] [thenpart] [elsepart] ifte

    >

    > That's linear (or at least it can be, if the language is linear) --

    > the only duplication is explicit.

     Sure, it is one way. Currently Joy has the branch combinator

    (rather than the ifte as in your example) which does not rely

    on any automatic saving and restoring. Presumably similar

    cousins of linrec, binrec and others could be implemented

    which force the user to make the shuffling explicit.

    [But incidentally - and I'm not so sure about this because I

    have forgotten the details of the shuffle notation:

    Are you sure the shuffle operator you have is correct? It

    seems to me that the succ succ + > sequence consumes three

    values, but your shuffler only restores two. Could you please

    check on this?

     >

    > > very great, so the overhead is not excessive. But having the

    > > interpreter doing the shifting and restoring automatically

    > > certainnly beats the errorprone way of doing it manually.

    >

    > I don't understand this. I've never seen it done automatically before

    > looking at Joy, and I don't find it convenient -- it's just another

    > thing to remember, for me. You still have to keep track of the same

    > stack items, but now you have to remember that some words "throw away"

    > some of the stack state you generate. If you find tracking stack state

    > inconvenient, why are you programming in a concatenative language, and

    > how could it be convenient to have a context where stack manipulations

    > sometimes get ignored?

     Well, even the trivial sequence + > throws away the value generated by

    the +. The combinators do the same - throw away what is not needed,

    but keep or restore what is needed.

     > My argument is doubly strong for linear languages, in which that sort

    > of thing just can't happen. If you do that automatic duplication, your

    > language isn't linear.

     I don't understand the rationale behind linearity well enough to answer

    this properly. Why does it make such a difference whether the duplication

    is done manually or automatically? (I do recall that Lisp can be

    implemented linearly with automatic duplication.) Could you expand,

    please?

      - Manfred

## William Tanksley, Jr — 2005-10-17 21:42:08

    phimvt@... <phimvt@...> wrote:

     > On Mon, 19 Sep 2005, William Tanksley, Jr wrote:

    > > phimvt@... <phimvt@...> wrote:

    > > > William Tanksley, Jr wrote:

    > > > > Greg Buchholz <sleepingsquirrel@...> wrote:

    > > > > >Making it worse is the fact that

    > > > > > (unlike 'dup') many comibnators (ifte, map, linrec, etc.) have

    > > > > > multiple pointers to the entire stack (i.e. not to a fixed number of

    > > > > > the top N stack items).  For example, if you think of 'ifte' as a

    > > > > > function from stacks->stacks, a Scheme implementation might look like...

    > > > > Yes, frankly I've never liked that about Joy. I think we'd have to say

    > > > > that a pure version of Joy as it's defined now couldn't be linear; but

    > > > > I do think it's reasonable to speak of a Linear Joy, with just enough

    > > > > changes to be linear.

    > > The ifte combinator is one of the troublesome cases -- it's nonlinear,

    > > because it duplicates pointers without duplicating data.

    > What the ifte combbinator duplicates depends very much on the

    > implmentation. You could have it always duplicate data or always

    > duplicate pointers, or you could have it duplicate numbers and other

    > small values but duplicate pointers for large values such as strings

    > or quotations (lists). The current implementation of Joy takes the third,

    > mixed alternative. But the user will never be aware of which of the

    > three alternative implementation methods is chosen.

     Those three alternatives all have one thing in common: they all

    *appear* to copy all the data, without requiring any request on the

    part of the programmer. They may or may not perform all of the work of

    copying, but they achieve the semantics.

    And those semantics are precisely what linear logic avoids; that's the

    strength and weakness of linear logic.

     > Sure, it is one way. Currently Joy has the branch combinator

    > (rather than the ifte as in your example) which does not rely

    > on any automatic saving and restoring. Presumably similar

    > cousins of linrec, binrec and others could be implemented

    > which force the user to make the shuffling explicit.

     Those would be linear -- using those, and NOT using the traditional

    ifte and others, would make a linear dialect of Joy.

     > > > very great, so the overhead is not excessive. But having the

    > > > interpreter doing the shifting and restoring automatically

    > > > certainnly beats the errorprone way of doing it manually.

    > > I don't understand this. I've never seen it done automatically before

    > > looking at Joy, and I don't find it convenient -- it's just another

    > > thing to remember, for me. You still have to keep track of the same

    > > stack items, but now you have to remember that some words "throw away"

    > > some of the stack state you generate. If you find tracking stack state

    > > inconvenient, why are you programming in a concatenative language, and

    > > how could it be convenient to have a context where stack manipulations

    > > sometimes get ignored?

    > Well, even the trivial sequence + > throws away the value generated by

    > the +. The combinators do the same - throw away what is not needed,

    > but keep or restore what is needed.

     Not true -- they keep and restore /everything/ except the specific

    things they're documented as using. This means that ANY changes the

    programmer makes to the stack get thrown away, without being looked at

    -- they're simply replaced by the old value of the stack.

     > > My argument is doubly strong for linear languages, in which that sort

    > > of thing just can't happen. If you do that automatic duplication, your

    > > language isn't linear.

    > I don't understand the rationale behind linearity well enough to answer

    > this properly. Why does it make such a difference whether the duplication

    > is done manually or automatically? (I do recall that Lisp can be

    > implemented linearly with automatic duplication.) Could you expand,

    > please?

     Lisp cannot be implemented linearly with automatic duplication;

    automatic duplication is the antithesis and contradiction of linear

    logic. To make Lisp linear, you have to _remove_ all of the implicit

    duplication it already contains, and give the programmer new

    operations and semantics to allow him to work without that automatic

    duplication.

    The rationale behind all of this depends on your perspective -- I

    can't speak for the people researching linear logic, but do a search

    for it and they can speak for themselves.

    I find linear logic interesting because linear concatenative languages

    have a special advantage over linear lambda-based languages, because

    concatenative languages do not need any special syntactic rules to

    preserve linearity (lambda-based languages need to add a rule like

    "lambda variables can only be used once").

     >   - Manfred

     -Billy

## phimvt@lurac.latrobe.edu.au — 2005-10-19 07:05:22

    On Mon, 17 Oct 2005, William Tanksley, Jr wrote:

    [..]

    > Lisp cannot be implemented linearly with automatic duplication;

    > automatic duplication is the antithesis and contradiction of linear

    > logic. To make Lisp linear, you have to _remove_ all of the implicit

    > duplication it already contains, and give the programmer new

    > operations and semantics to allow him to work without that automatic

    > duplication.

    Thank you. I was wrong in my assumption.

    > The rationale behind all of this depends on your perspective -- I

    > can't speak for the people researching linear logic, but do a search

    > for it and they can speak for themselves.

    >

    > I find linear logic interesting because linear concatenative languages

    > have a special advantage over linear lambda-based languages, because

    > concatenative languages do not need any special syntactic rules to

    > preserve linearity (lambda-based languages need to add a rule like

    > "lambda variables can only be used once").

    I have not studied linear logic or linear Lisp in any detail,

    so my discussion here will have to be very tentative.

    Let CoL be some unspecified concatenative language (Forth, Joy,

    CK,others).  Let LCoL be a similarly unspecified linear concatenative

    language which is a proper subset of CoL. Equivalently, let CoL be LCoL

    extended by some or even many nonlinear features. I can think of two kinds

    of reason why one might prefer LCoL to CoL:

      1. LCol is a better source language for writing programs.

      2. LCoL is a better target language for implementations.

    1. LCoL as a source language. Maybe it is better for human brains that

    have to write programs and to modify and otherwise manipulate programs.

    One problem is that we have neither a specification of LCoL not any

    nontrivial programs written in LCoL. To make a meaningful comparison, such

    programs should be written in two versions, one in LCoL and one in CoL.

    The claimed advantage of LCoL might be that there is nothing going on

    behind the scenes, that "everything is explicit". Well, not everything, of

    course, the program counter (also called instruction pointer) advances

    automatically, the top-of-stack pointer - if there is one - is modified

    automatically, data are shifted automatically from registers to on-chip

    memory, to all sorts of caches, to virtual memory and so on. But all these

    are not intended to be included in "everything", and rightly so. However,

    what gets on and off the stack is intended to be included, and there may

    be good _psychological_ reasons for the kind of explicitness that

    linearity dictates. But one really needs to see a few sample program

    pairs, in LCoL and in CoL, to see that the explicitness is an advantage.

    2. LCoL could be a target language, in the sense that CoL could be

    internally (and probably invisibly) translated into LCoL. Many languages,

    Joy included, need automatic memory management - either a garbage

    collector or reference counting. As I understand it, one claimed advantage

    of linear Lisp is that it eliminates the need for memory management. I do

    not understand how linear Lisp does this, but surely it must be at some

    cost elsewhere, probably the cost of a lot of copying. Some very detailed

    - and sobering - comparisons of the runtime efficiency of Lisp and linear

    Lisp have been reported and discussed: Google "Linear Lisp Prolog Boyer".

    Whatever the relative advantages of Lisp and linear Lisp may be, the

    relative implementation advantages of CoL and LCoL could be quite

    different.  So there may indeed be a good argument to use LCoL as

    a target language, but the details remain to be seen.

    Of course these two kind of reasons for preferring LCoL over CoL are

    not exclusive, and it is quite possible that LCoL should be the

    programming language and also the internal language. This is true

    for Forth, for Joy and for (interpreted) Lisp - the internal language

    has the same abstract syntax as the external language written in ASCII.

    It is this that makes the PROGRAM = DATA identity possible at least

    in Lisp and in Joy - I do not know about Forth.

    One final point, and I am somewhat hesitant here. Linear Lisp

    prohibits using data in lambda variables twice without prior explicit

    copying. LCoL is to prohibit using data on the stack twice without

    prior explicit copying. Would it then not be sensible to prohibit using

    code twice without prior explicit copying? Then any code for a loop

    should be copied before each cycle around the loop. Any code in

    a defined function should be copied before using the function,

    and in particular every recursive call should be preceded by a copying.

    Silly idea? Yes, of course, it would slow down execution tremendously,

    and it would be a programming nightmare. But why the asymmetry between

    data and code? Why linearity for data but not for code? Why indeed.

    I look forward to more discussions on this interesting topic.

    Thanks Billy for starting it.

      - Manfred

## William Tanksley, Jr — 2005-10-22 16:30:41

    phimvt@... <phimvt@...> wrote:

     > On Mon, 17 Oct 2005, William Tanksley, Jr wrote:

    > > I find linear logic interesting because linear concatenative languages

    > > have a special advantage over linear lambda-based languages, because

    > > concatenative languages do not need any special syntactic rules to

    > > preserve linearity (lambda-based languages need to add a rule like

    > > "lambda variables can only be used once").

    > Let CoL be some unspecified concatenative language (Forth, Joy,

    > CK,others).  Let LCoL be a similarly unspecified linear concatenative

    > language which is a proper subset of CoL. Equivalently, let CoL be LCoL

    > extended by some or even many nonlinear features. I can think of two kinds

    > of reason why one might prefer LCoL to CoL:

    >   1. LCol is a better source language for writing programs.

    >   2. LCoL is a better target language for implementations.

     I'm not sure that works, for two reasons. First, "better" is hard to

    measure in general; it's much easier to measure for specific purposes;

    but this means that a "best" language for one purpose might not be for

    some other. Second, both linear logic and concatenative languages are

    very lightly researched, which means that some of their greatest

    strengths haven't been developed.

    I think that even after the research on linearity has made progress,

    it'll remain a fringe technique, because it takes some work to make it

    work. On the other hand, on some machine types it may become the only

    way to write programs; some variant of linear logic would be useful on

    a reversible computation machine.

     > One problem is that we have neither a specification of LCoL not any

    > nontrivial programs written in LCoL.

     We could write linear programs now in Joy, though. Of course, we'd

    have to understand linearity well first, and I for one haven't taken

    the time.

     > To make a meaningful comparison, such

    > programs should be written in two versions, one in LCoL and one in CoL.

    > The claimed advantage of LCoL might be that there is nothing going on

    > behind the scenes, that "everything is explicit".

     The intro to http://home.pipeline.com/~hbaker1/ForthStack.html does a

    great job at explaining the motivation. It's not simply that a linear

    language looks better or is shorter; it's that linear code more

    closely models the "real world" and therefore can be compiled more

    efficiently.

     > One final point, and I am somewhat hesitant here. Linear Lisp

    > prohibits using data in lambda variables twice without prior explicit

    > copying. LCoL is to prohibit using data on the stack twice without

    > prior explicit copying. Would it then not be sensible to prohibit using

    > code twice without prior explicit copying? Then any code for a loop

    > should be copied before each cycle around the loop. Any code in

    > a defined function should be copied before using the function,

    > and in particular every recursive call should be preceded by a copying.

    > Silly idea? Yes, of course, it would slow down execution tremendously,

    > and it would be a programming nightmare. But why the asymmetry between

    > data and code? Why linearity for data but not for code? Why indeed.

     Yup, you're right. But with code it's a bit easier -- code is usually

    immutable, so there's no difference between copying the code and

    copying a pointer to the code. In essence, linear logic would mean

    that truly self-modifying code would be actually impossible (but

    modifying some other block of code that can get executed later would

    be quite possible).

     >   - Manfred

     -Billy

## Greg Buchholz — 2005-10-24 01:09:53

    --- "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > phimvt@... <phimvt@...> wrote:

    > >

    > The intro to http://home.pipeline.com/~hbaker1/ForthStack.html does a

    > great job at explaining the motivation. It's not simply that a linear

    > language looks better or is shorter; it's that linear code more

    > closely models the "real world" and therefore can be compiled more

    > efficiently.

         I'd also recommend Baker's "'Use-Once' Variables and Linear

    Objects"...

        http://home.pipeline.com/~hbaker1/Use1Var.html

    ...and the Clean language, with its uniqueness typing...

        http://www.cs.ru.nl/~clean/

     > > Why linearity for data but not for code? Why indeed.

         That's a good question that I think deserves further research.  One

    practical answer though is that we're content with running (relatively

    small) programs with a (mostly) statically known size.  This is in

    contrast to the intermediate values produced by a pure functional

    language which tend to grow so fast so as to exhaust limited memory

    resources in the absence of garbage collection.  Or similarily, think of

    a Turing machine.  We can have a small finite state machine (code), but

    we need an infinite tape (data) if we want to calculate all computable

    things.

    Greg Buchholz

    __________________________________

    Yahoo! Mail - PC Magazine Editors' Choice 2005

    http://mail.yahoo.com