[clean-list] GRS vs LTRS

[Pieter Koopman]

Dear Vag,

Vag wrote:
> To put in the nutshell, my point is that dag rewriting is better than 
> graph rewriting as `base' of pure functional programming languages 
> without manual proofs.
Better in the sense easier to reason about: I agree.
Better in the sense we do not need cycles: strongly disagree. There are 
algorithms that only have a reasonable complexity/efficiency due to a 
cycle. Without cycles we would need a more complex algorithm to mimic 
the effect. Cycles are nor used every day, but they do occur in real 
programs (not just Hamming numbers).

Consider a compiler that translates statements to machine instructions. 
This compilers yields the statements as well as the actual address for 
all labels used (in a tuple or record). These positions are feed to the 
compiler in order to generate the correct jumps. You can do this very 
elegantly with a cycle. If you cannot make this cycle you will probably 
need a two stage solution.

Best, Pieter