Complex structure translation with lazy evaluation

Question

Some background: I am writing a generic high-level to low-level compiler. On the high-level side, it understands classes, methods, fields, virtual method calls, etc. and on the low-level side, it understands functions, structures, arrays, etc. Front-ends translate compiled forms of languages like Java (the main focus) and C# into my IR. An intermediate step lowers the classes, methods, fields, and virtual calls, etc. into function calls and structures. The back end spits out C, LLVM IR (the main focus), or potentially others.

Currently, types (like integers, floats, structs, classes, and so on), are (mostly) immutable. Classes allow you to add fields and methods because these don't change the type (i.e. the class pointer). There is only one of any given type per translation unit ("Module") - structs, pointers, arrays, and other "derived" types. In other words, types have structure equivalence, like LLVM - instead of name equivalence, like C++.

The problem I am running into is translating instances of ClassType that the Java front-end spits out into StructType instances (with a vtable pointer and all of the fields of the class) that the LLVM backend understands, in such a way that the system maintains a consistent state throughout the process. One of the difficulties is maintaining structure equivalence - two different classes might be lowered to the same structure, and this must either be detected at the start of the lowering process, or corrected after the lowering process.

This long-winded explanation brings me to my question: can lazy-evaluation languages like Haskell offer a convenient solution? If so, how can this be translated back into Java, perhaps using the "Promise" pattern?

Answer 1

I am not sure if you are looking for a general answer or something more specific, but it sounds something like,

lower :: Eq b => a -> b
lower = undefined

generate :: Eq b => [a] -> [b]
generate xs = go $ map lower xs
    where go [] = []
          go (y:ys) = y : go (filter (not . (==y)) ys)

Which produces unique elements incrementally. The incremental aspect is just due to lazy cons, unless you can also make your Eq instance lazy (e.g. by comparing solely on some kind of structural hash code that might let you skip a more costly code generation step).