Re: functional programming language compiler using ANTLR?

John wrote:
> [I don't know any reason that parsing a functional language would be
> different from parsing an imperative one.


This is indeed the case. However, the grammars of functional
languages tend to be easier than those for imperative languages. I see
two possible influences in that direction:


1) Many (not all) functional languages are defined as a core language
plus a set of rules to translate the full language into core language
constructs. This tends to regularize the syntax and semantics of the
full language.
2) In functional languages, top-down LL parsing can be expressed very
elegantly and simply. IOW at least the first draft of a new functional
language tends to be LL(1).


> The code generation would be quite different, of course. -John]


Partly.
Some things remain the same. Others differ vastly.


Examples:


FPL implementations with a VM tend to be greatly different. For example,
there exist functional VMs that do graph reduction (this makes it more
efficient to interpret certain ubiquitous functional idioms).


Tail call optimization is mandatory. Loops in a functional program are
written as linear recursion (even if the programmer is not aware of
it), and linear recursion takes linear stack space without that
optimization, constant stack space with it.


Functional languages are almost unusable unless they support first-order
functions (i.e. functions constructed during run-time, either by
substituting functions into other functions, or by partly evaluating
them with a known parameters). Making this efficient is one of the
principal tasks of implementing a functional language.


Generating machine code is very similar. At the machine level, a
functional language moves data between registers and memory just like an
ordinary imperative language, and the issues are the same.


A functional compiler can optimize much more aggressively than an
imperative one. A subroutine call will not clobber any variables, and
there's no need to worry about aliases. This makes data-flow-based
optimizations much more simple.




I'm pretty sure that are other notable aspects. This is just what comes
off the top of my head.


Regards,
Joachim
--

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