Re: Using Prolog to Compile Things

Nick Roberts <nickroberts@callnetuk.com> writes:


>Has anyone on this ng experience or knowledge of the use of Prolog to
>implement a native-code compiler for a typical high-level imperative
>language? I am toying with the idea of using Prolog for the lexer, the
>parser, the intermediate (library) code generator, and the end-code
>generator (and even, in effect, for linking!), i.e. the 'whole shebang'.


I have written a couple of compilers in Prolog. In many ways, Prolog
is an excellent language for writing compilers, but it does have some
important disadvantages.


Much of the task of compilation is manipulating trees of various
kinds, and this is a task which Prolog and other logic or functional
languages do very well.


Another advantage of Prolog is the use of unbound variables and
partially instantiated data structures. Often during code generation
you may want to make several passes over some data structure (e.g. the
parse tree), filling in the values of different attributes with each
pass. In Prolog you can leave uninitialized attributes as unbound
variables, and have each pass bind the appropriate variables. This
contrasts with some languages such as ML or Mercury where you would
normally initialize the attributes with dummy values and then each
pass would make a copy of the parse tree in order to set the new
attributes.


Prolog does have some significant disadvantages. One is that Prolog
is often quite inefficient. For example, it's very difficult to get a
lexer written in Prolog to run fast.


Another disadvantage is that Prolog doesn't have records with named
fields. If you want access fields by name, then you need to write a
bunch of named access predicates, which is quite tedious. (Existing
Prolog implementations generally don't do inlining, so using named
access predicates also exacerbates the efficiency problems.)


Another disadvantage, probably more important than the previous two,
is that Prolog has very little in the way of static checking. This
works OK for small projects, but makes things very difficult when
writing large systems. If you plan to write 5000 lines of code or
more, then I would very strongly recommend using a language with
static type checking and a proper module system (some Prolog systems
do have module systems, but they are not standardized and vary
significantly between different Prolog systems). And Prolog's support
for unbound variables and nondeterminism, although useful, can also
cause a lot of problems if you accidentally forget to initialize a
variable or if you accidentally introduce nondeterminism. Other logic
programming languages such as Mercury and Visual Prolog (which,
despite the name, is quite different from Prolog) do a lot better
here.


If you do use Prolog, then I strongly recommend that you document the
types, modes, and determinism of the predicates in your program very
carefully. This is especially important if you ever want anyone other
than yourself to maintain the program. But compilers are usually not
small projects, so I think you would probably be better off choosing a
language which has more support for static checking, such as Mercury.


Of course, I'm one of the developers of Mercury, so my opinion in that
respect is no doubt biased ;-). But Mercury was developed with my
experience of implementing compilers in Prolog in mind, and so it was
designed to address many of Prolog's faults in that area. The Mercury
compiler is written in Mercury, so it has certainly been stress-tested
in that area.


> I'm particularly interested in the idea of using Prolog's natural
> searching abilities to search for truly optimal code.


I think this is a mirage. It's pretty easy to express searching
algorithms in any language. But finding _feasible_ algorithms to
produce "truly optimal code" is going to be difficult in any language.
Prolog's searching abilities won't really help much here.
--
Fergus Henderson <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
[It's my impression that in too many cases the only way to find perfectly
optimal code would be to enumerate and check an impractically large set
of possibilities. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.