Term Rewriting vs. Functional Programming

Hi,

For a while now, I have been looking for clues about the difference
between functional programming and term rewriting, both on a practical
level and on a theoretical level. I would greatly appreciate any
opinions on this issue. I will present some of my own ideas below, but
I would very much like people to comment on them and tell me why they
are completely wrong ;) I am particularly interested in what term
rewriting systems have to offer over functional programming languages.


On a practical level, I am comparing functional programming (FP)
languages such as Haskell or Clean to term rewrite systems (TRS) such
as ASF+SDF, Stratego, ELAN, etc. First off, most of these TRSs offer
sophisticated parsing technology (SDF); as far as I am concerned, this
is not really part of the TRS per se and is not important for the
comparison I am after.

Superficially, probably the most obvious difference is that a TRS do
tree traversal automatically, whereas this needs to be done manually by
the FP programmer. However, this distinction is not as clearcut as it
might seem. In fact, most TRSs allow the program to influence the
traversal mechanism in some way (strategies in Stratego, of course, but
also traversal functions in ASF+SDF, for example). On the FP side, it
is possible to abstract the traversal mechanism away, either language
dependent with updatable fold algebras [1], or, better yet, with
generic algebraic fold operators [2], although the latter needs some
language support.

Higher order functions and currying in FP have less obvious TRS
counterparts, although perhaps the case can be made that dynamic rules
in Stratego are similar? I/O is probably better thought out in FP than
it is in TRS; although Stratego supports interfacing with C, AFAIK
there is no support for either Clean's uniqueness typing or monadic
style programming.

Some term rewrite systems offer more sophisticated pattern matching
mechanisms (known as "theories" in the rho-calculus, below). For
example, ASF+SDF offers "list matching", which is a form of associative
matching; ELAN offers a more general associative/commutative matching.
I don't know of any functional counterparts to this, although it might
be possible to abstract away from this in the same style as the fold
algebras mentioned below (this is a hypothesis, not a statement of fact
:-)

FP programs allow to generate cylic structures, which may be where the
analogy breaks down. So, this appears to be one feature where FP is
strictly more powerful than TRS. However, when I compare, for example,
Clean, whose semantics is explicitely based on graph rewriting, to an
actual graph rewriting system (GRS) such as Agg, it seems to me that
Agg is much more powerful than Clean, which begs the question, what
does Clean have to offer me that Agg does not?  One obvious difference
is that Clean limits rules to algebraic (term-like rather than
graph-like) left hand sides, and, as before, requires the programmer to
do the traversal. This avoids the subgraph isomorphism problem (which
is NP-complete), but at great cost of flexibility.

On a theoretical level, the lambda calculus is usually said to form the
basis for functional programming (or graph rewriting; but see previous
remark). For term rewriting, some people are advocating the rho
(rewriting) calculus [3], which differs from the lambda calculus in
that it makes pattern matching explicit. However, I would think that
the rho calculus is as applicable to FP as it is to TRS, and in fact
might be a more elegant framework to reason about FP than the lambda
calculus. Moreover, it seems to me that most of the theory of TRS is
directly applicable to FP.

Anyway, that's just a few thoughts on the difference, or lack thereof.
Any comments would be greatly appreciated,

Edsko

[1] Ralf Lammel et al., Dealing with Large Bananas
[2] --, Strategic polymorphism requires just two combinators!
[3] Horatiu Cirstea and Claude Kirchner. The rewriting calculus - Part
I and II

I know very little about this but here's my 2p anyway... :-)

Edsko de Vries wrote:
> dependent with updatable fold algebras [1], or, better yet, with
> generic algebraic fold operators [2], although the latter needs some
> language support.

Can you elaborate on "language support" here?

> Some term rewrite systems offer more sophisticated pattern matching
> mechanisms (known as "theories" in the rho-calculus, below).

Are they matched in linear time?

> For
> example, ASF+SDF offers "list matching", which is a form of associative
> matching; ELAN offers a more general associative/commutative matching.
> I don't know of any functional counterparts to this, although it might
> be possible to abstract away from this in the same style as the fold
> algebras mentioned below (this is a hypothesis, not a statement of fact
> :-)

Straightforwardly, it is likely to be ugly. You can probably clean it up
using macros (e.g. camlp4). However, I believe commutative matching of
multiple-arguments needs to be non-linear in general.

It would be interesting to study the pattern matching implementation of a
TRS written in an FPL (that has pattern matching).

> FP programs allow to generate cylic structures, which may be where the
> analogy breaks down. So, this appears to be one feature where FP is
> strictly more powerful than TRS.

It is also one feature that is not very commonly used in functional
programming.

> Agg is much more powerful than Clean, which begs the question, what
> does Clean have to offer me that Agg does not?

I would guess performance.

> On a theoretical level, the lambda calculus is usually said to form the
> basis for functional programming (or graph rewriting; but see previous
> remark). For term rewriting, some people are advocating the rho
> (rewriting) calculus [3], which differs from the lambda calculus in
> that it makes pattern matching explicit. However, I would think that
> the rho calculus is as applicable to FP as it is to TRS, and in fact
> might be a more elegant framework to reason about FP than the lambda
> calculus. Moreover, it seems to me that most of the theory of TRS is
> directly applicable to FP.

This is fascinating and I'd like to learn more about it. Can you post links
to any interesting (preferably tutorial) work that you come across?

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

Jon Harrop wrote: 
>
> It is also one feature that is not very commonly used in functional
> programming.

I don't agree. It depends on the language - non-strict languages usually
make cyclic structures both easier to create and more useful. For
example, cyclic structures are much more often used in Haskell then in
OCaml.

Of course, this also depends on programmer.

Also, for a meaningful discussion we should define what is a cyclic
structure. What about good old (mutally) recursive functions?

Best regards
Tomasz

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

Edsko de Vries schrieb:
> For a while now, I have been looking for clues about the difference
> between functional programming and term rewriting, both on a practical
> level and on a theoretical level. I would greatly appreciate any
> opinions on this issue. I will present some of my own ideas below, but
> I would very much like people to comment on them and tell me why they
> are completely wrong ;) I am particularly interested in what term
> rewriting systems have to offer over functional programming languages.

On a theoretical level I would say, they are different, because FPs are
programming languages and term rewriting systems are not, in a strict
sense. Given a term rewriting system and a term, inferencing a normal
form of the term is comparable to the execution of a functional program.
But term rewriting is not only about normal form building. You can
investigate system which do not yield normal forms. Either because they
are not desterministic or because they do not terminate.

Nevertheless, I think there are people who use term rewriting to
describe the semantics of pure functional programming languages, which
obviously states that there are some similarities between them.


> Superficially, probably the most obvious difference is that a TRS do
> tree traversal automatically, whereas this needs to be done manually by
> the FP programmer. However, this distinction is not as clearcut as it
> might seem. In fact, most TRSs allow the program to influence the
> traversal mechanism in some way (strategies in Stratego, of course, but
> also traversal functions in ASF+SDF, for example).

No, tree traversal is also done by functional programming languages. It
is just called control flow in languages with side-effects. In pure
functional languages it is the evalution order of a program. When
studying first order rewriting system people often try to use confluent
systems, which are independent of the tree traversal order in their
result. But that order influences dramatically performance and the
results inbetween.

> On the FP side, it
> is possible to abstract the traversal mechanism away, either language
> dependent with updatable fold algebras [1], or, better yet, with
> generic algebraic fold operators [2], although the latter needs some
> language support.
>
> Higher order functions and currying in FP have less obvious TRS
> counterparts, although perhaps the case can be made that dynamic rules
> in Stratego are similar? I/O is probably better thought out in FP than
> it is in TRS; although Stratego supports interfacing with C, AFAIK
> there is no support for either Clean's uniqueness typing or monadic
> style programming.

It is also possible to model folds and other higher-order functions
explicitly with rewrite rules.

> Some term rewrite systems offer more sophisticated pattern matching
> mechanisms (known as "theories" in the rho-calculus, below). For
> example, ASF+SDF offers "list matching", which is a form of associative
> matching; ELAN offers a more general associative/commutative matching.
> I don't know of any functional counterparts to this, although it might
> be possible to abstract away from this in the same style as the fold
> algebras mentioned below (this is a hypothesis, not a statement of fact
> :-)

E.g. these "theories" are used to improve the performance of automated
theorem provers based on rewriting systems.

> FP programs allow to generate cylic structures, which may be where the
> analogy breaks down. So, this appears to be one feature where FP is
> strictly more powerful than TRS. However, when I compare, for example,
> Clean, whose semantics is explicitely based on graph rewriting, to an
> actual graph rewriting system (GRS) such as Agg, it seems to me that
> Agg is much more powerful than Clean, which begs the question, what
> does Clean have to offer me that Agg does not?  One obvious difference
> is that Clean limits rules to algebraic (term-like rather than
> graph-like) left hand sides, and, as before, requires the programmer to
> do the traversal. This avoids the subgraph isomorphism problem (which
> is NP-complete), but at great cost of flexibility.
>
> On a theoretical level, the lambda calculus is usually said to form the
> basis for functional programming (or graph rewriting; but see previous
> remark). For term rewriting, some people are advocating the rho
> (rewriting) calculus [3], which differs from the lambda calculus in
> that it makes pattern matching explicit. However, I would think that
> the rho calculus is as applicable to FP as it is to TRS, and in fact
> might be a more elegant framework to reason about FP than the lambda
> calculus. Moreover, it seems to me that most of the theory of TRS is
> directly applicable to FP.

To learn more about term rewriting look into this book: Term Rewriting
and all that. Franz Baader and Tobias Nipkow

This are just my 2cents on this topic.

Jean-Marie Gaillourdet
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFDGK4kNIUNP/ I5YOgRAsY8AJ9ewMPHTYXImTb3q5FV51CD0wXWdQ
Cgrho9
hV2kJ+cpQ8ppL77pXG0McmQ=
=80BC
-----END PGP SIGNATURE-----

Tomasz Zielonka wrote:
> I don't agree. It depends on the language - non-strict languages usually
> make cyclic structures both easier to create and more useful. For
> example, cyclic structures are much more often used in Haskell then in
> OCaml.

But are they used much more often than non-cyclic data structures, even in
Haskell?

> Also, for a meaningful discussion we should define what is a cyclic
> structure. What about good old (mutally) recursive functions?

An excellent point. :-)

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

Jean-Marie Gaillourdet wrote:
> Edsko de Vries schrieb:
> 
>
> On a theoretical level I would say, they are different, because FPs are
> programming languages and term rewriting systems are not, in a strict
> sense. Given a term rewriting system and a term, inferencing a normal
> form of the term is comparable to the execution of a functional program.
> But term rewriting is not only about normal form building. You can
> investigate system which do not yield normal forms. Either because they
> are not deterministic or because they do not terminate.

You can do the same for functional languages. Or rather, you can define
specification languages of which the executable subset is directly usable
as a functional language. And of course, typical functional programming
languages do not guarantee termination.

--
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

* Tomasz Zielonka:

> I don't agree. It depends on the language - non-strict languages usually
> make cyclic structures both easier to create and more useful. For
> example, cyclic structures are much more often used in Haskell then in
> OCaml.

Infinite lists (for example) in Haskell are *not* cyclic.

Florian Weimer schrieb:
> * Tomasz Zielonka:
> 
>
> Infinite lists (for example) in Haskell are *not* cyclic.

IIRC infinite lists turn into cyclic data structures in graph rewriting
engines.

Regards,
Jo

Joachim Durchholz <jo@durchholz.org> wrote:
> Florian Weimer schrieb:
[...] 

> IIRC infinite lists turn into cyclic data structures in graph rewriting
> engines.

For a definitive answer, I would rather look at the definition (dynamic
semantics) of the language than any particular implementation strategy.

-Vesa Karvonen

Vesa Karvonen schrieb:
> Joachim Durchholz <jo@durchholz.org> wrote: 
>
> For a definitive answer, I would rather look at the definition
> (dynamic semantics) of the language than any particular
> implementation strategy.

That's entirely a question of what level currently interests you.

At the semantic level, anything that references itself forms a cycle,
which in a functional context means that cycles are available if you
have recursion of any form (direct or indirect, functions or data).

At the implementation level, I'd say anything where pointer chains form
a cycle is cyclic. A borderline case is a cyclic data structure
represented as an array (easy to do, use indices in place of pointers).

Regards,
Jo