[Haskell-cafe] Compiler's bane

[Andrew Coppin]

Brandon S. Allbery KF8NH wrote:
> On 2008 Sep 3, at 14:34, Andrew Coppin wrote:
>> The amusing (?) part is that the interpretter itself is essentially 
>> quite simple. I've implemented it several times before now. But what 
>> I'm trying to do it make it print out elaborately formatted execution 
>> traces so that a human user can observe how execution proceeds. This 
>> transforms an essentially simple algorithm into something quite 
>> nausiatingly complex, with many subtle bugs and issues.
>
> This seems odd to me:  I would expect to wrap a WriterT around it, log 
> unformatted actions there, and dump it to a file at the end to be read 
> by an analyzer tool which can optionally reformat the log to be 
> human-readable.

Well actually, the interpretter itself takes an expression and returns a 
large, complex data structure representing the reduction sequence. Then 
a second function takes the reduction sequence and transforms it into a 
target-neutral markup structure. Finally, one of several rendering 
backends transforms this into something displayable - text, HTML, LaTeX, 
whatever. There are no monads involved. Anywhere.

Actually, that's not completely true. The interpretter takes a set of 
transformation rules as an argument, and attempts to apply each rule in 
sequence, and then recursively over all subexpressions. The logic for 
this makes extensive use of the Maybe monad. (I spent ages looking for a 
function Maybe x -> Maybe x -> Maybe x that would keep Just and throw 
away Nothing, rather than (>>=) which does the opposite. Eventually I 
discovered that this is actually mplus. It wasn't easy...)

The basic interpretter is just one function, that does a little pattern 
matching. It's one module of a few dozen lines. But as soon as you want 
to *record* the transformations applied, suddenly everything gets very 
much more complicated. And when you start wanting to have many possibly 
rules to apply, and turning individual rules on and off, and applying 
rules only to certain parts of the expression... it all starts to get 
very complicated.

I've spent about 3 hours this afternoon trying to get my renamer to 
work. I *had* a working renamer, but then I discovered that 
locally-unique names are insufficient. You must have _globally_ unique 
names. This is much harder; you cannot now rename each subexpression 
independently. You must put the whole algorithm into a state monad. The 
algorithm is maddeningly subtle to get right. It's still not working 
properly. It *almost* works, but not quite. I think I know how to fix it 
- we'll see tomorrow - but isn't it just typical that an "uninteresting" 
part of the program turns out to be harder than the interesting bits?

My head hurts...