Re: [q-lang-users] Speeding up Q

[Albert G. <Dr....@t-...>]

Dr Libor Spacek wrote:
> Since Tim Haynes mentioned Clean, I would be interested 
> to know what you see as the main advantages/differences 
> of Pure over Clean?

Well, I probably shouldn't be talking about Pure as if it already
existed (just in case you're wondering if Pure was an April fools joke
after all -- no, it's not!). But my brain is hurting after hours of
coding the LLVM code generator for the pattern-matching automaton, so I
might as well use this as an excuse for a little coffee break. And it
can't hurt to build up some more hype in advance. ;-)

Btw, this might also be a nice read in this context:
http://www.lisperati.com/landoflisp/

Here's a *very* brief rundown of the main features of these languages
(sorry if this comes over as a bit simplistic, but I'm afraid that I
can't go into all the subleties and more esoteric features here):

- Haskell: purely functional (monads for side-effects), lazy
- Clean: dito, but "uniqueness" types for side effects
- ML: impure (allows side-effects), eager (there are lazy versions)

These all belong to the "Hindley-Milner strongly typed" camp, with all
the safety and inconveniences that offers. In addition, with Haskell and
Clean you also have to jump through hoops to get side effects, which is
good for the compiler writer and also greatly facilitates optimization
and auto-parallelization, but is a *big* inconvenience for many
programmers who actually want to *use* those languages for real-world
problems. Moreover, while pervasive laziness seems like a good feature,
it does have its performance penalties and, more importantly, it
sometimes makes it harder to write good programs (space leaks issue).

In contrast, Q and Pure are dynamically typed and allow side-effects
(well, Pure itself is in fact purely functional but it allows "unsafe"
calls into C without any ado), which is more in line with Lisp-like
languages. They also offer Lisp-like reflection capabilities, which is
something where *all* the languages from the strongly typed camp fall
short. In Q, the reflectiveness is limited to expressions, but in Pure
it will be much broader, allowing fully dynamic modifications of the
running program as in Lisp. Q also supports lazy evaluation through its
user-definable special forms (which is kind of like the "futures" in
Alice ML, but the "thunking" is handled automatically). Pure doesn't
have this right now, but it won't be hard to add.

I also think that Pure's syntax is nicer, better than ML's somewhat
complicated definition syntax and Haskell's layout-based block structure
(call me old-fashioned, but free-format languages were invented for good
reasons). But YMMV.

But the biggest difference between all those languages (including Lisp)
and Q/Pure is that the latter are based on general term rewriting rather
than the lambda calculus, which essentially boils down to the simple
feature that there is no distinction between "constructors" and "defined
functions". This might not seem like a big deal, but it makes the
language much more expressive:

1. You can have constructor equations, which is great for expressing
axioms like associativity or idempotence.

2. You can do symbolic calculations involving expressions with free
variables.

3. You can extend the definition of any function or operator to your own
data structures, at any time.

Unless you want to do symbolic algebra, 1 and 2 probably are not much
more than a convenience, but I consider 3 really as a major advantage,
because it gives you much better ad-hoc polymorphism than even Lisp.

Now Haskellers might argue that they have type classes for that, but
you'll have to jump through a lot of hoops to achieve the same kind of
polymorphism, while in Q/Pure it's just there, without even *planning*
for it. To me, that's the most striking advantage of term rewriting as a
programming language. Of course, this comes at a price: In a TR language
the only "argument mismatch" exceptions that you get any more are those
in guards (if the condition doesn't evaluate to a truth value), unless
you explicitly add definitions which throw such exceptions. Whether you
like that pretty much depends on which kind of programmer you are: do
you want a sharp knife, or are you worried about accidentally cutting
your feet off? ;-)

Hope that this clarified the differences a bit.

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag