Re: Using Prolog to Compile Things

G'day all.


Nick Roberts <nickroberts@callnetuk.com> writes:


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


The moderator commented:


>[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]


This is true, which means you can't just throw nondeterministic
searching at a problem and hope everything happens for you. All that
the searching capabilities of logic languages really buy you in these
sorts of cases is a much more convenient way to express the problem.


A case in point is template-matching bottom-up code generation. A
compiler in an imperative language would use techniques such as
dynamic programming to control the algorithmic complexity and a
compiler in Prolog/Mercury/whatever is no different. However the job
of template matching and collating code sequences for comparison is
much more conveniently expressed in a language with good pattern
matching/ indexing capabilities and nondeterminism (with an
all-solutions facility, naturally) than in a more conventional
programming language.


Writing a template-matching code generator in an imperative language
generally requires the use of a "code generator generator", and
usually a heavily customised one at that, to generate the pattern
matching and collating code from a set of templates and rules. It's
much more convenient (and potentially more efficient) to write your
code generator in a language which does most of it for you.


Cheers,
Andrew Bromage

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