change ast to use immutable lists instead of functional ones

[GoogleCodeExporter]

The FreeBoogie AST now uses singly linked lists. The rationale was that:
(1) we want immutable lists (in general, immutable AST), 
(2) there is no class for immutable lists in the Java API, and 
(3) implementing singly linked lists ourselves didn't require support from
AstGen.

However, there are disadvantages:
(1) David Cok complained that this leads to hard-to-maintain code. I
respectfully disagree but, even so, I expect others to feel the same.
(2) Performance: The JVM does not support tail calls and won't support them
for a while [http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4726340].
This leads to slowness (not sure how much) and the _necessity_ of setting a
higher stack.
(3) Exceptions backtraces are hard to read.
(4) You can't loop over the list using the nice foreach syntax. The natural
recursive implementation is somewhat cumbersome in Java because defining a
new function requires typing lots of crap. In general, you can't use
Iterator and related facilities.

Since Google Collections have been recently added as an external dependency
we now have a nice ImmutableList class for free. Using it would allow us to
keep the AST immutable (thus avoiding ASTs that change from "under your
feet") and avoid the problems outlined above. The downside: This requires
changing pretty much every existing visitor.

Original issue reported on code.google.com by radugrig...@gmail.com on 25 Jul 2009 at 9:32

[GoogleCodeExporter]

Original comment by radugrig...@gmail.com on 27 Jul 2009 at 10:53

[GoogleCodeExporter]

This issue was updated by r549.

New abstract grammar in branches/changing-ast.

Original comment by radugrig...@gmail.com on 27 Jul 2009 at 11:24

[GoogleCodeExporter]

Original comment by radugrig...@gmail.com on 3 Aug 2009 at 9:03

• Changed state: Started

[GoogleCodeExporter]

This issue was closed by revision r584.

Original comment by radugrig...@gmail.com on 17 Aug 2009 at 1:46

• Changed state: Fixed