Re: Convert imperative to functional?

"#HUANG YUE#" <huangyue@pmail.ntu.edu.sg> writes:


> One of my friends is taking the course of "programming
> language". And he got to know imperative and funtional language. He
> asked me whether it is possible to convert imperative back to
> functional structures? Easy for program analysis?


It is possible to convert any program in one Turing-complete language
to a program in another Turing-complete language, so it follows that
it is possible to convert imperative programs to functional ones. It
doesn't, however, follow that the functional programs are in a
"natural" functional style. The simplest approach is to let the store
be an explicit parameter and result to all function calls, but that
requires a comlex management of that monolithic store parameter, which
often defeats program analysis. Some more complex transformations
attempt to make more natural functional programs, but may occasionally
have to fall back to the pass-the-store style for some programs.


> Is there some compiler able to do such similar thing? Is it a
> fresh idea? Or ridiculous?


Several modern compilers convert intermediate code into a
semi-functional form, for the express purpose of having easier program
analysis and transformation. The most common of these forms is the
SSA (static single assignement) form, but several people have proposed
and used more functional variants. See, for example,
http://www.cs.ubc.ca/local/reading/proceedings/cascon96/htm/english/abs/mason.htm


Torben Mogensen

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