Re: [stack] Prolog and Rewriting Strategies

On 26/3/07 6:35 PM, "Christopher Diggins" <[email protected]> wrote:

> Manfred's recent post about Prolog got me thinking about using a Polog
> style language for term rewriting. For example, we could express the
> fact that "swap swap" evaluates to a no-op below:
> 
> inverse(swap, swap) :- true
> inverse('a add, 'a sub) :- true
> $f $g | inverse($f, $g) == id
> 
> [..]
> 
Well, yes, one could do the  term rewriting in a style as you propose:
Give names to various relations between functions (or operators),
and then use the relations as preconditions for rewriting. But where
you wrote
> 
> $f $f | idempotent($f) == $f
> 
that is taken to mean: provided $f is idempotent, $f $f == $f
which I would have written in Prolog as
    
(F,F) == F  :-  idempotent(F)

But you will need to give one definition of idempotency, and a list of those
functions which are idempotent. That list will be exactly as long as saying,
for each function, that they satisfy the defining property of being
idempotent. So it is a choice between ³idempotent (abs)² and ³abs abs ==
abs², and similarly for all the other idempotent functions. It may be that
rewriting is easier your way, but maybe it isn¹t. Certainly, giving names
to the laws adds some complexity to the rewriting system which may not
pay off in the long run. But I am not sure at all. My only experience with
(tree-)rewriting has been with simple desk-calculator evaluators in
teaching,
and later with Joy, which is essentially rewriting a program using a stack
to keep track of where rewriting occurs. (I have said several times that
I do not regard the stack as essential for a concatenative language).
Anyhow, I am just not sure whether the naming simplifies the rewriting.

Nice idea, though. I seem to remember the expression ³conditional rewriting
systems²
in the literature. That might be worth googling for.

  - Manfred









[Non-text portions of this message have been removed]