Pointers or mutually referential values

Hi,

I've written a number of compilers, mostly implemented in C. I often
find that it's necessary, or at least useful, to implement data
structures with elements (like AST nodes) that reference each other.
For example, in my current project, a parser and analyser for VHDL,
statements may have labels. A label would ideally have a reference to
a statement, while a statement would have a reference to its label.
And the label ought to be (at least partially) defined in a symbol
table before the parsing of the statement is complete, in case the
statement contains a reference to the label. Example: a labelled
"loop" statement containing an "exit" or "next" iterator control
statement with a label argument.

In a C implementation, it's pretty trivial to malloc() a structure,
leave some pointers set to NULL in the interim, then just update the
pointers when the time is right. But this is clearly not a
"functional" way of thinking. I'm implementing a combinator-based
parser in SML, and find myself thinking of implementing more or less
the same scheme, but since it's SML, using combinations of OPTION
datatypes and references. However, this still strikes me as being
contrary to the spirit and elegance of functional programming. I'm not
an SML novice by any means, but I don't see an elegant way to hide
this messiness behind a cute "functional pearl" or clean
encapsulation. The closest I've come up with is to encapsulate a pair
of cross-references (almost like an adjoint, or in C a two-element
dually-linked list), but that just hides the hackery rather that
making it more elegant.

Are there any nice(r) FP solutions for handling this sort of problem
out there?

Regards,

- Kenn

kennheinrich@sympatico.ca <kennheinrich@sympatico.ca> schrieb:
> Hi,
>
> I've written a number of compilers, mostly implemented in C. I often
> find that it's necessary, or at least useful, to implement data
> structures with elements (like AST nodes) that reference each other.
> For example, in my current project, a parser and analyser for VHDL,
> statements may have labels. A label would ideally have a reference to
> a statement, while a statement would have a reference to its label.
> And the label ought to be (at least partially) defined in a symbol
> table before the parsing of the statement is complete, in case the
> statement contains a reference to the label. Example: a labelled
> "loop" statement containing an "exit" or "next" iterator control
> statement with a label argument.
>
> In a C implementation, it's pretty trivial to malloc() a structure,
> leave some pointers set to NULL in the interim, then just update the
> pointers when the time is right. But this is clearly not a
> "functional" way of thinking. I'm implementing a combinator-based
> parser in SML, and find myself thinking of implementing more or less
> the same scheme, but since it's SML, using combinations of OPTION
> datatypes and references. However, this still strikes me as being
> contrary to the spirit and elegance of functional programming. I'm not
> an SML novice by any means, but I don't see an elegant way to hide
> this messiness behind a cute "functional pearl" or clean
> encapsulation. The closest I've come up with is to encapsulate a pair
> of cross-references (almost like an adjoint, or in C a two-element
> dually-linked list), but that just hides the hackery rather that
> making it more elegant.
>
> Are there any nice(r) FP solutions for handling this sort of problem
> out there?

I don't see how this can be done in strict languages, but in Haskell
you can write a function

replace' :: AST -> Map String AST -> (AST, Map Label AST)

which creates the mapping and replaces strings by references
simultaneously. Make sure that the computation
of the mapping does not use the resulting AST.

Then you can tie the knot via a recursive let:

replace :: AST -> AST
replace ast = let (ast', defs) = replace' ast defs
in ast'

Google for "repmin Haskell" for some background information.

kennheinrich@sympatico.ca wrote:
> I've written a number of compilers, mostly implemented in C. I often
> find that it's necessary, or at least useful, to implement data
> structures with elements (like AST nodes) that reference each other.
> For example, in my current project, a parser and analyser for VHDL,
> statements may have labels. A label would ideally have a reference to
> a statement, while a statement would have a reference to its label.
> And the label ought to be (at least partially) defined in a symbol
> table before the parsing of the statement is complete, in case the
> statement contains a reference to the label. Example: a labelled
> "loop" statement containing an "exit" or "next" iterator control
> statement with a label argument.
>
> In a C implementation, it's pretty trivial to malloc() a structure,
> leave some pointers set to NULL in the interim, then just update the
> pointers when the time is right. But this is clearly not a
> "functional" way of thinking. I'm implementing a combinator-based
> parser in SML, and find myself thinking of implementing more or less
> the same scheme, but since it's SML, using combinations of OPTION
> datatypes and references. However, this still strikes me as being
> contrary to the spirit and elegance of functional programming. I'm not
> an SML novice by any means, but I don't see an elegant way to hide
> this messiness behind a cute "functional pearl" or clean
> encapsulation. The closest I've come up with is to encapsulate a pair
> of cross-references (almost like an adjoint, or in C a two-element
> dually-linked list), but that just hides the hackery rather that
> making it more elegant.
>
> Are there any nice(r) FP solutions for handling this sort of problem
> out there?

You can define recursive data structures in Haskell and sometimes in OCaml
but not in SML. The solution is typically to use references and a dummy
value (rather than an option type).

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com/products/?u