Hello,
this remark applies to Scala 2.7.7.

I am using sealed, purely functional, case class hierarchies like this one :

sealed abstract class Op
abstract class BinOp extends Op
case object And extends BinOp
case object Or extends BinOp
abstract class UnOp extends Op
case object Not extends UnOp

sealed abstract class Expr
case class Ident(name:String) extends Expr
case class UnExpr( op:Unop, kid:Expression ) extends Expr
case class BinExpr(op: BinOp, left:Expression, right:Expression) extends Expr

to model abstract syntax trees and do some rewriting on them.

I've written my rewriting engine in a purely functional style, using trampolines (instead of mutually tail recursive functions because of the incomplete TCO support) to avoid overflowing the stack when doing various actions in pre/in/post order during traversal of deep trees.

Because of the purely functional coding style, I use Stacks, Maps and HashMaps to bind and unbind data with these AST nodes as the rewriting progresses top down, bottom up, breadth first or depth first.

As nothing can distinguish Expr instances having an identical structure, it would make sense to have all such instances represented by a single object in memory, and to have hashCode memoized at creation time, and equals redefined to be reference equality. This would provide a dramatic speedup, reduce memory footprint, would avoid stack overflow problems when inserting such things in HashTables, etc...

Because of the "bad" behaviour of :

• memory allocation : instance with identical structure are not shared

• hashCode : recursive but not tail recursive and not memoized

• equality test : recursive but not tail recursive

for such case class hierarchies, the code is slow, eats up a lot of memory, and triggers stack overflows when inserting deep terms in Maps or HashMaps (whereas these things cause no problems in CAML for instance).

The only solution I've found to sidestep this is to manually maintain a pool unique instances (doing structural hashing and instance numbering), and to manually overload the hashCode and equals methods, which is a bit boring and non scalable. I'm under the impression that this structural hashing could be automated by the run time, or that the code could be transformed by the compiler to achieve this in the case of sealed hierarchies of case classes with no mutable fields.

This would make scala more efficient for language processing applications of this kind.

The remark would also apply to all generic containers instanciated for sealed case class hierarchies, like lists (lists suffixes could be globally unique in an application)

best regards.