Re: imperative-to-functional compiler

nojb <n.oje.bar@gmail.com> writes:


> Suppose you want to translate an imperative language (e.g. a suitable
> subset of Pascal) into a functional language that does not have
> mutable variables (e.g. ML).


ML does have mutable variables, but I will answer for the case where the
functional language doesn't.


> Is this possible?


Certainly. You can translate any Turing-complete language to any other.


> What would be the algorithms/theory that would be relevant to handle
> the mutability of the variables on the Pascal side?. Is SSA relevant?


SSA is certainly relevant, but it is not purely functional. There is a
variant of SSA called "functional intermediate form", which adds scoping
to SSA and replaces labels by function definitions and jumps by
tail-calls. This can be used to translate variable updates to parameter
passing. However, it only handles updates of scalar variables, not of
record fields, array elements and such. To handle that, you need to
represent data structures such as arrays and records as functional data
structures and be careful about sharing.


Functional languages that do not provide mutable variables often add
abstractions that make it easier to emulate mutable variables and data
structures. Haskell, for example, provides monads (and specifically
the state monad) that allow mutable variables to be implemented in a
way that is both fully functional and efficient. This can ease the
translation from an imperative language.


Torben

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