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