Re: Practicality of functional and logic languages? (long)

maniattb@cs.rpi.edu (Bill Maniatty) writes:
>Has there been research in creating architectural
>support for functional programming languages?


Yup. There has been effort into both special purpose machines for SK
combinator reduction (Eg. Norma, SKIM) and parallel machines.


Effort has also been made in both efficient implementation on conventional
hardware (EG. the G machine and it's variants) and on conventional
multiprocessor machines. (Eg. buckwheat)


>Most machines have the internal concept of state, which is not assumed in
>functional programming languages (particularly those which enforce a
>single asssignment rule). Just how well could the functional programming
>paradigm be expressed at the machine level?


I'm not sure what you're asking. If you're asking how would one go about
implementing pure functional languages then think of LISP - one uses a
heap.


>What about the power of the functional programming paradigm? Is there an
>important class of problem which cannot be done by Functional Programming?


Anything involving random access data structures (ie. arrays) can be
simulated using balanced trees but will be slower. Haskell has arrays. A
good implementation will be able to detect when the array is being used in
a single threaded fashion and will implement it as an imperative array
using in place updating.


Ie. Arrays CAN be done - but unless your language and compiler offers
support it will be slower.


>Could you write an Operating System using Functional Programming
>techniques for example?


Yup. It's been done.
--------------
Some references:


Functional Operating Systems
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Author: David Turner
Title: Functional programming and communicating processes (some design
                            considerations for a functional operating system)
Journal: Proceedings of the Conference on Parallel Architectures and
                            Languages Europe, Volume II: Parallel Languages
Editor: J.W. de Bakker, A.J. Nijman, P.C. Treleaven
City: Eindhoven, Netherlands
Date: June 1987
Pages: 54-74
Keyword: parle parle87, Kent Applicative Operating System, KAOS, Miranda
Other: published as Lecture Notes in Computer Science 259 by
                            Springer-Verlag


Author: P. Henderson
Title: Purely functional operating systems
Journal: Proceedings of the Workshop on Functional Programming and its
                            Applications
Editor: J. Darlington, P. Henderson, D.A. Turner
Publisher: Cambridge University Press
Date: 1982
Pages: 177-192
Keyword: fpaia


Author: William Stoye
Title: Message-based functional operating systems
Journal: Science of Computer Programming
Volume: 6
Number: 3
Date: 1986
Pages: 291-311
Keyword: scp


Hardware
~~~~~~~~~
Author: Mark Scheeval
Title: NORMA: a graph reduction processor
Journal: Conference Record of the ACM Symposium on LISP and Functional
                            Programming
Date: 1986
Keyword: slfp slfp86


Author: T.J.W. Clarke, P.J.S. Gladstone, C.D. MacLean, A.C. Norman
Title: SKIM - the S,K,I reduction machine
Journal: Conference Record of the 1980 LISP Conference
City: Stanford, California
Date: August 1980
Pages: 128-135
Keyword: slfp slfp80


Author: John Darlington, Mike Reeve
Title: ALICE: a multi-processor reduction machine for the parallel
                            evaluation of applicative languages
Journal: Proceedings of the 1981 Symposium on Functional Programming and
                            Computer Architecture
City: Portsmouth, New Hampshire
Date: October 1981
Pages: 65-75
Keyword: fpca fpca81




Author: Simon L. Peyton Jones, Chris Clack, Jon Salkild, Mark Hardie
Title: GRIP - a high-performance architecture for parallel graph
                            reduction
Journal: Proceedings of the 1987 Symposium on Functional Programming
                            Languages and Computer Architecture
Editor: Gilles Kahn
City: Portland, Oregon
Date: September 1987
Pages: 98-112
Keyword: fpca fplca fpca87 fplca87, supercombinator, intelligent memory
                            IMU
Other: published as Lecture Notes in Computer Science 274 by
                            Springer-Verlag


Implementation on conventional machines
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Author: Benjamin Goldberg
Title: Buckwheat: graph reduction on a shared-memory multiprocessor
Journal: Proceedings of the ACM Conference on LISP and Functional
                            Programming
City: Snowbird, Utah
Date: July 1988
Keyword: slfp slfp88


Author: G.L. Burn, S.L. Peyton Jones, J.D. Robson
Title: The SpinelessG-Machine
Journal: Proceedings of the ACM Conference on LISP and Functional
                            Programming
City: Snowbird, Utah
Date: July 1988
Keyword: slfp slfp88
--
Michael Winikoff
winikoff@cs.mu.oz.au
Final year computer science. University of Melbourne, Australia.
--

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