Why is point-free form so interesting?
Christopher Diggins
point-free form is somehow better than a form with names from the
standpoint of tools (e.g. analyzers, compilers, translators,
optimizers, etc.). Note: this is completely separate from any
statements about the usability of point-free form for programmers.
That is a controversial idea that I would rather avoid debating (I
have nothing useful to add to that debate anyway)
Here are some bullet points that describe what I percieve to be the
main advantages of point-free form:
- less ambiguity (is foo a parameter or definition?)
- fewer evaluation rules (no alpha-conversion, no beta-conversion)
- flat structure versus tree
- maps more nicely to imperative programs: semi-colon (or in some
languages newline, and sometimes comma) is essentially a composition
operator
- syntactic analysis can be performed on tokens rather than parse tree
- fewer parantheses: all interesting computations are compositions,
rather than applications.
- ease of transformation
- rewriting rules are fundamentally easier (linear as opposed to trees)
Any other additions to this list, corrections, or clarifications would
be much appreciated!
One question is: can we reasonably claim with any formality that a
linear form is somehow easier to work with than a tree?
Cheers,
Christopher
http://cdiggins.com
Christopher Diggins
permission to me to forward to the entire list.
As a general rule of thumb I prefer Cat related discussions to remain
on the mailing list where possible, so that ideas and explanations can
be archived publicly for future reference. Unless, of course, there
are extenuating circumstances.
---------- Forwarded message ----------
From: Colin <goo...@icemx.net>
Date: Jun 22, 2007 6:13 AM
Subject: Re: Why is point-free form so interesting?
To: Christopher Diggins <cdig...@gmail.com>
On 6/22/07, Colin <goo...@icemx.net> wrote:
> On Jun 16, 9:02 pm, "Christopher Diggins" <cdigg...@gmail.com> wrote:
> > I have been struggling to formalize/rationalize my intuition that
> > point-free form is somehow better than a form with names from the
> > standpoint of tools (e.g. analyzers, compilers, translators,
> > optimizers, etc.).
>
> My feeling is that these two forms can be transformed into each other
> rather easily?
Yes you are correct. The question is which one is the one we want to work with.
> Compiling code with names into a pure stack machine gives you point
> free, chasing the stack gives you names...
>
> > Here are some bullet points that describe what I percieve to be the
> > main advantages of point-free form:
> >
> > - less ambiguity (is foo a parameter or definition?)
>
> The grammar shouldn't be ambiguous...
It isn't, I meant ambiguity from a programmer's standpoint.
> > - fewer evaluation rules (no alpha-conversion, no beta-conversion)
>
> Don't know what that is.
http://ling.ucsd.edu/~barker/Lambda/
> > - flat structure versus tree
>
> This sounds rather limiting to me, and in fact I am planning on
> constructing an expression tree in Mog in order to optimise...
What are you optimizing? What scenarios is the MetaCat optimizer
unable to handle as is, or with minor extensions?
> Am I
> barking up the wrong tree here?
I believe so, see below.
> > - maps more nicely to imperative programs: semi-colon (or in some
> > languages newline, and sometimes comma) is essentially a composition
> > operator
> > - syntactic analysis can be performed on tokens rather than parse tree
> > - fewer parantheses: all interesting computations are compositions,
> > rather than applications.
> > - ease of transformation
> > - rewriting rules are fundamentally easier (linear as opposed to trees)
>
> So syntactically you will detect e.g. "1 add" and can convert it into
> an "inc", but what about "1 bla_bla_something_that_generates_an_int
> add"? That's why I want the tree to optimise...
I would use the type-checker to search for the smallest subexpression
with the type ( -> int). However, if this is known to be a well-typed
program the type is guaranteed to be an int, so we just need to look
for any subexpression with type ( -> 'a). This kind of subexpression
matches the metacat variable $a. A subexpression will always be a
linear sequence of terms, so no tree is needed.
> Currently my idea is to add two macro systems to Mog, one linear one
> like MetaCat after building the AST (which mainly represents the
> linear form of the program), and one later, when I've got some kind of
> expression tree.
Hopefuly I've cleared things up.
> > One question is: can we reasonably claim with any formality that a
> > linear form is somehow easier to work with than a tree?
>
> >From my current, rather limited point of view there's one main thing I
> like about the linear form: It gives me a unique ordering on functions
> with side effects; this could make things easier when used as
> scripting language, or anything else with lots of system calls,
> compared to Haskell...?
This is a good point.
> Ciao, Colin
Cheers,
Christopher