[Caml-list] handling forward references in a compiler

[Caml-list] handling forward references in a compiler

[dido]

I'm writing a compiler for a language that allows undeclared forward
references in OCaml, and I'm just wondering how one is supposed to
handle these sorts of things without resorting to imperative features or
multiple passes.  Using imperative features, I'd be able to create a
hash table of forward referenced symbols, containing lists of locations
where these forward referenced symbols occur, and when the forward
referenced symbol is finally declared, look for it in the hash table and
resolve all the forward references there and then.  But this requires
that I put a temporary value in the intermediate representation that can
be changed later.  Another option is to make a second pass through the
generated intermediate representation, and fixing up the forward
references after all of the declarations have been processed, but this
seems like a second traversal that can be avoided.

Anyone have any better ideas?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] handling forward references in a compiler

[skaller]

On Tue, 2004-05-25 at 19:52, dido@imperium.ph wrote:
> I'm writing a compiler for a language that allows undeclared forward
> references in OCaml, and I'm just wondering how one is supposed to
> handle these sorts of things without resorting to imperative features or
> multiple passes.

What's wrong with multiple passes?

Felix uses many passes. It doesn't backpatch though.
I make a hash table keyed by a fresh integer
with data of each definition, and a set of hash tables
representing scopes, keyed by the identifier with
data the integer.

In the next pass, I bind uses by looking up the
name in the scopes to find the integer.

The effect is that scopes are all mutually recursive,
and lookup is always random access within a scope:
forward reference declarations are never needed
because the whole scope is always searched.

For example:

fun f():int { return g(); }
fun g():int { return f(); }

works just fine. You can also write:

val x = y;
val y = 1;

which also binds just fine .. although it doesn't
do anything sensible at run time.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] handling forward references in a compiler

[Evan Martin]

On Tue, May 25, 2004 at 05:52:13PM +0800, dido@imperium.ph wrote:
> I'm writing a compiler for a language that allows undeclared forward
> references in OCaml, and I'm just wondering how one is supposed to
> handle these sorts of things without resorting to imperative features or
> multiple passes.

Thanks for asking this question.  I'm actually stuck on almost the same
problem right now.  I resorted to doing both:  filling out hash tables
in an initial pass.  I figure that the global namespace is not
dynamic--in contrast with locally-scoped bindings--so it's ok to use it
imperatively; I never need any version of it except for the final one.
In other words, there's only one full, accurate picture of the global
namespace (while the local bindings vary from scope to scope), so I
might as well take a pass to figure it out completely.

But I'm eager to read what others have to say.

-- 
Evan Martin
martine@danga.com
http://neugierig.org

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] handling forward references in a compiler

[Marcin 'Qrczak' Kowalczyk]

W liście z wto, 25-05-2004, godz. 17:52 +0800, dido@imperium.ph napisał:

> I'm writing a compiler for a language that allows undeclared forward
> references in OCaml, and I'm just wondering how one is supposed to
> handle these sorts of things without resorting to imperative features or
> multiple passes.

These are indeed two most obvious choices. I prefer the second one.

In the first pass we scan only "heads" of definitions, creating an
environment which maps strings to some unique ids. In the second pass
we know the meaning of each identifier, so we can process code normally
no matter which identifiers have their definitions before or after.

> Another option is to make a second pass through the
> generated intermediate representation, and fixing up the forward
> references after all of the declarations have been processed, but this
> seems like a second traversal that can be avoided.

There is no need to have a separate pass which only patches references.
You just lookup references in the previously constructed environment
as necessary, when processing the code tree in the next pass which also
does whatever it was supposed to do anyway.

In a compiler I implemented it was not that easy to scan heads of
definitions, because some syntactic sugar was not yet resolved, so it
would have to be resolved twice. To avoid this, the pass which gathers
defined names also produces a modified list of definitions, with
resolved toplevel syntactic sugar, with bound names represented by
unique ids, but with everything else - in particular all embedded
expressions - left unprocessed. They are processed in the next pass,
which resolves used identifiers and expression-level syntactic sugar,
and produces a new code representation for further processing.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners