FAQ for comp.lang.functional Frequently Asked Questions forcomp.lang.functionalEdited byGraham Hutton,University of NottinghamVersion of November 2002(This document is no longer being updated) 1. This document 2. General topics 2.1. Functional languages 2.2. History and motivation 2.3. Textbooks 2.4. Journals and conferences 2.5. Schools and workshops 2.6. Education 3. Technical topics 3.1. Purity 3.2. Currying 3.3. Monads 3.4. Parsers 3.5. Strictness 3.6. Performance 3.7. Applications 4. Other resources 4.1. Web pages 4.2. Research groups 4.3. Newsgroups 4.4. Bibliographies 4.5. Translators 5. Languages 5.1. ASpecT 5.2. Caml 5.3. Clean 5.4. Erlang 5.5. FP 5.6. Gofer 5.7. Haskell 5.8. Hope 5.9. Hugs 5.10. Id 5.11. J 5.12. Miranda 5.13. Mercury 5.14. ML 5.15. NESL 5.16. OPAL 5.17. Oz 5.18. Pizza 5.19. Scheme 5.20. Sisal 1. This document Comp.lang.functional is an unmoderatedusenet newsgroup for the discussion of all aspects of functional programminglanguages, including their design, application, theoretical foundation, andimplementation. Articles posted to this (and other) newsgroups are archivedon the web at:http://www.dejanews.com/.This document is a Frequently Asked Questions list (FAQ) forcomp.lang.functional, and providesbrief answers to a number of common questions concerning functional programminglanguages, and some pointers to relevant literature and internet resources.The latest version of this document is available on the web from:http://www.cs.nott.ac.uk/~gmh/faq.html.Much of the information in this document has been taken from publicsources, mostly from articles posted tocomp.lang.functional.Because of the way that this document was compiled, a complete list ofcontributors is not available. Any opinions expressed in this documentare those of the individual contributors, and may not be representativeof views of the editor, or of others in the functional programming community.Every effort has been made to ensure that the content of this document iscorrect and up-to-date, but no guarantees are given for the accuracy ofthe information provided here. Your corrections and contributions areencouraged!The original version of this Frequently Asked Questions list was compiledand edited byMark P. Jones.All questions, comments, corrections, and suggestions regarding this documentshould be addressed to the current editor,Graham Hutton. 2. General topics This section gives brief answers to a number of general questionsconcerning functional programming languages, and some pointersto relevant literature and internet resources. 2.1. Functional languages What is a "functional programming language"?Opinions differ, even withinthe functional programming community, on the precise definition of whatconstitutes a functional programming language. However, here is adefinition that, broadly speaking, represents the kind of languages thatare discussed in comp.lang.functional:Functional programming is a style of programming that emphasizesthe evaluation of expressions, rather than execution of commands.The expressions in these language are formed by using functions tocombine basic values. A functional language is a language thatsupports and encourages programming in a functional style.For example, consider the task of calculating the sum of the integers from 1to 10. In an imperative language such as C, this might be expressed usinga simple loop, repeatedly updating the values held in an accumulator variabletotal and a counter variable i:total = 0;for (i=1; i 2.3. Textbooks Are there any textbooks about functional programming?Yes, here are a selection:Programming: "Introduction to functional programming using Haskell", 2nd edition,Richard Bird, Prentice Hall Europe, 1998. ISBN 0-13-484346-0. "The Haskell school of expression: Learning functional programmingthrough multimedia", Paul Hudak, Cambridge University Press, 2000.ISBN 0-521-64338-4. Further information is available on the web from:http://haskell.org/soe. "Haskell: The craft of functional programming", 2nd edition,Simon Thompson, Addison-Wesley, 1999. ISBN 0-201-34275-8. Furtherinformation is available on the web from:http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e. "ML for the working programmer", 2nd Edition, L.C. Paulson, CambridgeUniversity Press, 1996. ISBN 0-521-56543-X. Further information is availableon the web from:http://www.cl.cam.ac.uk/users/lcp/MLbook/.Algorithms and data structures: "Purely functional data structures", Chris Okasaki,Cambridge University Press, 1998. ISBN 0-521-63124-6. "Algorithms: A functional programming approach", Fethi Rabhi andGuy Lapalme, Addison-Wesley, 1999. ISBN 0-201-59604-0. Further information is available on the web from:http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html.Implementation: "The implementation of functional programming languages", Simon PeytonJones, Prentice Hall, 1987. ISBN 0-13-453333-X. "Compiling with continuations", Andrew Appel, Cambridge UniversityPress, 1992. ISBN 0-521-41695-7. Further information is available on theweb from:http://www.cup.org/Titles/416/0521416957.html.There are several other textbooks available, particularly in the programmingand implementation categories. A comparison of a number of functionalprogramming textbooks is made in the following article:"Comparative review of functional programming textbooks (Bailey, Birdand Wadler, Holyer, Paulson, Reade, Sokoloski, Wikstrom)", SimonThompson, Computing Reviews, May 1992 (CR number 9205-0262). 2.4. Journals and conferences Are there any journals and conferences about functional programming?Yes, here are a selection:Journals: The Journal of Functional Programming (JFP), published by CambridgeUniversity Press. Further information is available on the web from:http://www.dcs.gla.ac.uk/jfp/. The Journal of Functional and Logic Programming (JFLP), an electronicjournal published by MIT Press, and available on the web from:http://www.cs.tu-berlin.de/journal/jflp/. Lisp and Symbolic Computation, published by Kluwer.Conferences: The International Conference on Functional Programming (ICFP). This conference combines and replaces the earlier conferences on Lisp andFunctional Programming (LFP), and Functional Programming Languages andComputer Architecture (FPCA). Further information about the nextICFP conference (October 2002 at the time of writing) isavailable on the web from:http://icfp2002.cs.brown.edu/. Mathematics of Program Construction (MPC). Further informationabout the most recent MPC conference (July 2000 at the time of writing)is available on the web from:http://seide.di.uminho.pt/~mpc2000/. Principles of Programming Languages (POPL). Further informationabout the next POPL conference (January 2001 at the time ofwriting) is available on the web from:http://www.daimi.au.dk/~popl01/.European Symposium on Programming (ESOP). Further information aboutthe next ESOP conference (April 2001 at the time of writing) isavailable on the web from:http://www.md.chalmers.se/~dave/esop/.Most of these conferences have proceedings published by the ACM press, orin the Springer Verlag LNCS (Lecture Notes in Computer Science) series.In addition to the above, Philip Wadler edits a column on functionalprogramming for the Formal Aspects of Computer Science Newsletter,which is published by the British Computing Society Formal Aspectsof Computing group and Formal Methods Europe. 2.5. Schools and workshops Are there any schools and workshops on functional programming?Yes, here are a selection:Schools:Summer School and Workshop on Advanced Functional Programming,August 19-24, 2002, Oxford, England. Further information isavailable on the web from:http://www.functional-programming.org/afp/.The Third International Summer School on Advanced FunctionalProgramming Techniques, September 12-19, 1998, Braga, Portugal.Further information is available on the web from:http://www.di.uminho.pt/~afp. Spring School on Advanced Functional Programming Techniques,May 24-31, 1995, Baastad, Sweden. The proceedings of the schoolwere published in the Springer Verlag LNCS (Lecture Notes in ComputerScience) series, number 925. The Second International Summer School on Advanced FunctionalProgramming Techniques, August 25-30, 1996, Washington, USA.The proceedings of the school were published in the SpringerVerlag LNCS (Lecture Notes in Computer Science) series, number 1129.Further information is available on the web from:http://www.cse.ogi.edu/PacSoft/summerschool96.html.Workshops:Haskell Workshop, September 2, 2001, Florence,Italy. Held in conjunction with PLI 2001. Further informationis available on the web from:http://www.cs.uu.nl/people/ralf/hw2001.htmlHaskell Workshop, September 17, 2000, Montreal,Canada. Held in conjunction with PLI 2000. Further informationis available on the web from:http://www.cs.nott.ac.uk/~gmh/hw00.htmlThird Haskell Workshop, October 1, 1999, Paris, France.Held in conjunction with ICFP'99. Further information isavailable on the web from:http://www.haskell.org/HaskellWorkshop.htmlWorkshop on Algorithmic Aspects of Advanced Programming Languages,September 29-30, 1999, Paris, France.Further information is available on the web from:http://www.cs.columbia.edu/~cdo/waaapl.html.1st Scottish Functional Programming Workshop,August 29-September 1, 1999, Stirling, Scotland.Further information is available on the web from:http://www.cee.hw.ac.uk/~gjm/sfp/.From 1988 to 1998 the Glasgow functional programming group organised ayearly workshop in Scotland. Further information is available on theweb from:http://www.dcs.gla.ac.uk/fp/workshops/. The 9th International Workshop on the Implementation of FunctionalLanguages, Sept 10-12, 1997, St. Andrews, Scotland.Further information is available on the web from:http://www.dcs.st-and.ac.uk/~ifl97. The Haskell Workshop, June 7, 1997, Amsterdam, The Netherlands.Held is conjunction with ICFP'97. Further information is available onthe web from:http://www.cse.ogi.edu/~jl/ACM/Haskell.html. The 2nd Fuji International Workshop on Functional and LogicProgramming, November 1-4, 1996, Shonan Village, Japan.Further information is available on the web from:http://www.kurims.kyoto-u.ac.jp/~ohori/fuji96.html. The 1st Workshop on Functional Programming in Argentina,September 12, 1996, Buenos Aires, Argentina. Further informationis available on the web from:http://www-lifia.info.unlp.edu.ar/~lambda/first/english/. 2.6. Education Are functional programming languages useful in education?Functional languages are gathering momentum in education because theyfacilitate the expression of concepts and structures at a high levelof abstraction. Many university computing science departments nowmake use of functional programming in their undergraduate courses;indeed, a number of departments teach a functional language as theirfirst programming language. Further information about the use offunctional programming languages in education (including links torelevant conferences and workshops) is available on the web from:http://www.cs.kun.nl/fple/. 3. Technical topics This section gives brief answers to a number of technical questionsconcerning functional programming languages, and some pointersto relevant literature and internet resources. 3.1. Purity What is a "purely functional" programming language?This question has been the subject of some debate in the functionalprogramming community.It is widely agreed that languages such as Haskell and Miranda are"purely functional", while SML and Scheme are not. However, there aresome small differences of opinion about the precise technical motivationfor this distinction. One definition that has been suggested is as follows:The term "purely functional" is often used to describelanguages that perform all their computations via functionapplication. This is in contrast to languages, such as Scheme andStandard ML, that are predominantly functional but also allow`side effects' (computational effects caused by expressionevaluation that persist after the evaluation is completed).Sometimes, the term "purely functional" is also used in a broadersense to mean languages that might incorporate computational effects,but without altering the notion of `function' (as evidenced by thefact that the essential properties of functions are preserved.)Typically, the evaluation of an expression can yield a `task', whichis then executed separately to cause computational effects. Theevaluation and execution phases are separated in such a way thatthe evaluation phase does not compromise the standard propertiesof expressions and functions. The input/output mechanisms ofHaskell, for example, are of this kind.See also: "What is a purely functional language", Amr Sabry,Journal of Functional Programming, 8(1):1-22, CambridgeUniversity Press, January 1998. 3.2. Currying What is "currying", and where does it come from?Currying has its origins in the mathematical study of functions. It wasobserved by Frege in 1893 that it suffices to restrict attention tofunctions of a single argument. For example, for any two parameterfunction f(x,y), there is a one parameter function f' such that f'(x)is a function that can be applied to y to give (f'(x))(y) = f (x,y).This corresponds to the well known fact that the sets (AxB -> C) and(A -> (B -> C)) are isomorphic, where "x" is cartesian product and"->" is function space. In functional programming, function applicationis denoted by juxtaposition, and assumed to associate to the left, sothat the equation above becomes f' x y = f(x,y).Apparently, Frege did not pursue the idea further. It was rediscoveredindependently by Schoenfinkel, together with the resultthat all functions having to do with the structure of functions can bebuilt up out of only two basic combinators, K and S. About a decadelater, this sparked off the subject of combinatory logic, invented byHaskell Curry. The term "currying" honours him; the function f' in theexample above is called the "curried" form of thefunction f. From a functional programming perspective, curryingcan be described by a function:curry : ((a,b) -> c) -> (a -> b -> c)The inverse operation is, unsurprisingly, refered to as uncurrying:uncurry : (a -> b -> c) -> ((a,b) -> c)For further reading, see: "Highlights of the history of the lambda-calculus", J. Barkley Rosser,ACM Lisp and Functional Programming, 1982. "Ueber die Bausteine der mathematischen Logik", Moses Sch\"onfinkel,Mathematische Annalen, 92, 1924. An English translation, "On thebuilding blocks of mathematical logic", appears in "From Frege toG\"odel", Jean van Heijenoort, Harvard University Press, Cambridge, 1967. "Combinatory logic", Haskell B. Curry and Robert Feys, North-Holland,1958. This work also contains many references to earlier work byCurry, Church, and others. 3.3. Monads What is a "monad", and what are they used for? The concept of a monad comes from category theory; full details canbe found in any standard textbook on the subject. Much of theinterest in monads in functional programming is the result of recentpapers that show how monads can be used to describe all kinds ofdifferent programming language features (for example, I/O, manipulationof state, continuations and exceptions) in purely functional languagessuch as Haskell: "Comprehending monads", Philip Wadler, Mathematical Structures inComputer Science, Special issue of selected papers from 6thConference on Lisp and Functional Programming, 1992.Available on the web from:http://www.cs.bell-labs.com/~wadler/topics/monads.html#monads "The essence of functional programming", Philip Wadler, Invited talk,19th Symposium on Principles of Programming Languages, ACM Press,Albuquerque, January 1992. Available on the web from:http://www.cs.bell-labs.com/~wadler/topics/monads.html#essence"Imperative functional programming", Simon Peyton Jones and PhilipWadler, 20th Symposium on Principles of Programming Languages, ACMPress, Charlotte, North Carolina, January 1993. Available on theweb from:http://www.cs.bell-labs.com/~wadler/topics/monads.html#imperative"How to declare an imperative", Philip Wadler, ACM Computing Surveys,to appear. Available on the web from:http://www.cs.bell-labs.com/~wadler/topics/monads.html#monadsdeclare 3.4. Parsers How can I write a "parser" in a functional programming language? A parser is a program that converts a list of input tokens, usuallycharacters, into a value of the appropriate type. A simple example mightbe a function to find the integer value represented by a string of digits.A more complex example might be to translate programs written in aparticular concrete syntax into a suitable abstract syntax as the firststage in the implementation of a compiler or interpreter. There aretwo common ways to write a parser in a functional language: Using a parser generator tool. Some functional language implementationssupport tools that generate a parser automatically from a specificationof the grammar. See: Happy: a parser generator system for Haskell and Gofer,similar to the tool `yacc' for C. Available on the web from:http://www.dcs.gla.ac.uk/fp/software/happy/.Ratatosk: a parser and scanner generator for Gofer. Available by ftp from: Host: ftp.diku.dk; Directory: /pub/diku/dists. ML-Yacc and ML-Lex: an LALR parser generator and a lexical analysergenerator for Standard ML. Included with SML/NJ, available by ftp from: Host: ftp.research.bell-labs.com; Directory: /dist/smlnj.Using combinator parsing. Parsers are represented by functions andcombined with a small set of combinators, leading to parsers thatclosely resemble the grammar of the language being read. Parserswritten in this way can use backtracking. See: "How to replace failure with a list of successes", Philip Wadler,FPCA '85, Springer Verlag LNCS 201, 1985. "Higher-order functions for parsing", Graham Hutton, Journal ofFunctional Programming, Volume 2, Number 3, July 1992. Availableon the web from:http://www.cs.nott.ac.uk/~gmh/bib.html#parsing. 3.5. Strictness What does it mean to say that a functional programminglanguage is "strict" or "non-strict"?Here's one (operational) way to explain the difference: In a strict language, the arguments to a function are always evaluatedbefore it is invoked. As a result, if the evaluation of an expressionexp does not terminate properly (for example, because it generates arun-time error or enters an infinite loop), then neither will anexpression of the form f(exp). ML and Scheme are both examples of this.In a non-strict language, the arguments to a function are not evaluateduntil their values are actually required. For example, evaluating anexpression of the form f(exp) may still terminate properly, even ifevaluation of exp would not, if the value of the parameter is not used inthe body of f. Miranda and Haskell are examples of this approach.There is much debate in the functional programming community about therelative merits of strict and non-strict languages. It is possible,however, to support a mixture of these two approaches; for example,some versions of the functional language Hope do this. 3.6. Performance What is the performance of functional programs like?In some circles, programs written in functional languages have obtaineda reputation for lack of performance. Part of this results from thehigh-level of abstraction that is common in such programs and from powerfulfeatures such as higher-order functions, automatic storage management, etc.Of course, the performance of interpreters and compilers for functionallanguages keeps improving with new technological developments.Here are a selection of references for further reading:Over 25 implementations of different functional languages have been comparedusing a single program, the "Pseudoknot" benchmark, which is a floating-pointintensive application taken from molecular biology. See:"Benchmarking implementations of functional languages with 'Pseudoknot',a float-intensive benchmark", Pieter H. Hartel et al, Journal ofFunctional Programming, 6(4):621-655, July 1996.Available on the web from:ftp://ftp.fwi.uva.nl/pub/computer-systems/functional/reports/.The paper below compares five implementations of lazy functional languages: "Benchmarking implementations of lazy functional languages", P.H.Hartel and K.G. Langendoen, FPCA 93, ACM, pp 341-349. Available by ftp from: Host: ftp.fwi.uva.nl; Directory: pub/functional/reports.Experiments with a heavily optimising compiler for Sisal, a strict functionallanguage, show that functional programs can be faster than Fortran. See:"Retire FORTRAN? A debate rekindled", D.C. Cann, Communications ofthe ACM, 35(8), pp. 81-89, August 1992.Postscript versions of a number of papers from the 1995 conference on HighPerformance Functional Computing (HPFC) are available on the web from:ftp://sisal.llnl.gov/pub/hpfc/index.html. 3.7. Applications Where can I find out about applications of functional programming?Here are a selection of places to look: "Special issue on state-of-the-art applications of pure functionalprogramming languages", edited by Pieter Hartel and Rinus Plasmeijer, Journalof Functional Programming, Volume 5, Number 3, July 1995. "Applications of functional programming", edited by Colin Runcimanand David Wakeling, UCL Press, 1995. ISBN 1-85728-377-5.An online list of real-world applications of functional programming ismaintained, which includes programs written in several differentfunctional languages. The main criterion for being considered areal-world application is that the program was written primarily toperform some task, rather than to experiment with functional programming.Further details are available on the web from:http://www.cs.bell-labs.com/~wadler/realworld/. 4. Other resources This section gives some pointers to other internet resourceson functional programming. 4.1. Web pages Philip Wadler's guide to functional programming on the web:http://cm.bell-labs.com/cm/cs/who/wadler/guide.html. Philip Wadler's list of real-world application of functional programming:http://www.cs.bell-labs.com/~wadler/realworld/. The SEL-HPC WWW functional programming archive:http://hypatia.dcs.qmw.ac.uk/SEL-HPC/Articles/FuncArchive.html.Jon Mountjoy's functional languages page:http://carol.wins.uva.nl/~jon/func.html.Claus Reinke's functional programming bookmarks:http://website.lineone.net/~claus_reinke/FP.html. 4.2. Research groups The Chalmers functional programming group:http://www.md.chalmers.se/Cs/Research/Functional/.The Glasgow functional programming group:http://www.dcs.gla.ac.uk/fp.The Nijmegen functional programming group:http://www.cs.kun.nl/~clean.The Nottingham foundations of programming group:http://www.cs.nott.ac.uk/Research/fop/index.html.The St Andrews functional programming group:http://www-fp.dcs.st-and.ac.uk/.The Yale functional programming group:http://www.cs.yale.edu/HTML/YALE/CS/haskell/yale-fp.html.The York functional programming group:http://www.cs.york.ac.uk/fp/. 4.3. Newsgroups For discussion about ML:comp.lang.ml.For discussion about Scheme:comp.lang.scheme.For discussion about Lisp:comp.lang.lisp.For discussion about APL, J, etc:comp.lang.apl. 4.4. Bibliographies Mike Joy's bibliography on functional programming languages,in refer(1) format: Host: ftp.dcs.warwick.ac.uk; Directory: /pub/biblio.Tony Davie's bibliography of over 2,600 papers, articles andbooks on functional programming, available as a text fileor a hypercard stack by ftp from: Host: tamdhu.dcs.st-and.ac.uk; Directory: /pub/staple."State in functional programming: an annotated bibliography", editedby P. Hudak and D. Rabin, available as a dvi or postscript fileby ftp from: Host: nebula.cs.yale.edu; Directory: /pub/yale-fp/papers.Wolfgang Schreiner's annotated bibliography of over 350 publications onparallel functional programming (most with abstracts), availableon the web from:http://www.risc.uni-linz.ac.at/people/schreine/papers/pfpbib.ps.gz. 4.5. Translators The smugweb system for typesetting Haskell code in TeX, available from:http://www5.informatik.uni-jena.de/~joe/smugweb.html.The miratex package for typesetting Miranda(TM) code in TeX, available from:http://www.cs.tcd.ie/www/jgllgher/miratex/index.html.Denis Howe's translators from Miranda(TM) to LML and Haskell, available from:http://wombat.doc.ic.ac.uk/pub/mira2lml;http://wombat.doc.ic.ac.uk/pub/mira2hs. 5. Languages This section gives a brief overview of a number of programming languagesthat support aspects of the functional paradigm, and some pointers torelevant literature and internet resources. The table below classifiesthe languages into strict/non-strict and sequential/concurrent, and maybe useful when searching for suitable languages for particular applications.Some of the languages have multiple versions with different classifications(see the language overviews for further details), but for simplicity onlythe most common version of each language is considered in the table. Sequential: Concurrent: Strict: ASpecT Caml FP J Mercury ML OPAL Scheme Erlang NESL Oz Pizza Sisal Non-strict: Gofer Haskell Hope Hugs Miranda Clean Id 5.1. ASpecT ASpecT is a strict functional language, developed at the University ofBremen, originally intended as an attempt to provide an implementationfor (a subset of) Algebraic Specifications of Abstract Datatypes. Thesystem was designed to be as user-friendly as possible, includingoverloading facilities and a source-level debugger. For reasons ofefficiency, the system uses call-by-value evaluation and referencecounting memory management.Over the years more and more features have been added, including subsorting,functionals, and restricted polymorphism. The ASpecT compiler translatesthe functional source code to C, resulting in fast and efficient binaries.ASpecT has been ported to many different platforms, including Sun3, Sun4,Dec VAX, IBM RS6000, NeXT, Apple A/UX, PC (OS/2, Linux), Amiga and AtariST/TT. The ASpecT compiler is available by ftp from: Host: ftp.Uni-Bremen.DE; Directory: /pub/programming/languages/ASpecT.The most important application of ASpecT to date is the interactivegraph visualization system daVinci; currently (September '96), version2.0.x is composed of 34.000 lines of ASpecT code, 12.000 lines of Ccode and 8000 lines of Tcl/Tk code. daVinci is an X11 program, and isavailable for UNIX workstations from Sun, HP, IBM, DEC, SGI, and forIntel PCs with a UNIX operating system. Further information aboutdaVinci is available on the web from:http://www.Informatik.Uni-Bremen.DE/~davinci. 5.2. Caml Caml is a dialect of the ML language developed at INRIA that does notcomply to the Standard, but actually tries to go beyond the Standard,in particular in the areas of separate compilation, modules, and objects.Two implementations of Caml are available:The older implementation, Caml Light, is distinguished by itssmall size, modest memory requirements, availability on microcomputers,simple separate compilation, interface with C, and portable graphicsfunctions. It runs on most Unix machines, on the Macintosh and onPCs under Ms Windows and MSDOS. The current version at the time of writingis 0.71.A more ambitious implementation, Objective Caml (formerly known as CamlSpecial Light), is also available. It adds the following extensions toCaml Light: Full support for objects and classes, here combined for thefirst time with ML-style type reconstruction; A powerful module calculus in the style of Standard ML, butproviding better support for separate compilation; A high-performance native code compiler, in addition to a CamlLight-style bytecode compiler.Objective Caml is available for Unix and Windows 95/NT, with thenative-code compiler supporting the following processors: Alpha,Sparc, Pentium, Mips, Power, HPPA.Both implementations of Caml are available by ftp from: Host: ftp.inria.fr; Directory: /lang/caml-light.Further information about Caml is available on the web from:http://pauillac.inria.fr/caml/index-eng.html (English);http://pauillac.inria.fr/caml/index-fra.html (French). 5.3. Clean The Concurrent Clean system is a programming environment for thefunctional language Concurrent Clean, developed at the University ofNijmegen in The Netherlands. The system is one of the fastestimplementations of functional languages available at the time of writing.Through the use of uniqueness typing, it is possible to write purelyfunctional interactive programs, including windows, menus, dialogs, etc.It is also possible to develop real-life applications that interface withnon-functional systems. With version 1.0, the language emerged from anintermediate language to a proper programming language. Features providedby the language include: Lazy evaluation; Modern input/output; Annotations for parallelism; Automatic strictness analysis; Annotations for evaluation order; Inferred polymorphic uniqueness types; Records, mutable arrays, module structure; Existential types, type classes, constructor classes; Strong typing, based on the Milner/Mycroft scheme.Concurrent Clean is available for PCs (Microsoft Windows, Linux), Macintoshes (Motorola, PowerPC), and Sun4s (Solaris, SunOS).The system is available by ftp from: Host: ftp.cs.kun.nl; Directory: /pub/Clean.Further information about Concurrent Clean is available on the web from:http://www.cs.kun.nl/~clean.A book describing the background and implementation of ConcurrentClean is also available:"Functional programming and parallel graph rewriting", RinusPlasmeijer and Marko van Eekelen, Addison Wesley, InternationalComputer Science Series. ISBN 0-201-41663-8 5.4. Erlang Erlang is a dynamically typed concurrent functional programming languagefor large industrial real-time systems. Features of Erlang include: Modules; Recursion equations; Explicit concurrency; Pattern matching syntax; Dynamic code replacement; Foreign language interface; Real-time garbage collection; Asynchronous message passing; Relative freedom from side effects; Transparent cross-platform distribution; Primitives for detecting run-time errors.Erlang is freely available on the web from:http://www.erlang.org.Erlang is distributed together with full source code for anumber of applications, including: Inets - HTTP 1.0 server and FTP client; Orber - CORBA v2.0 Object Request Broker (ORB); ASN.1 - compile-time and runtime package for ASN.1; SNMP - extensible SNMP v1/v2 agent and MIB compiler; Mnesia - distributed real-time database for Erlang; Mnemosyne - optional query language for Mnesia.See also:"Concurrent programming in Erlang" (second edition), J. Armstrong,M. Williams, R. Virding, and Claes Wikström, Prentice Hall, 1996.ISBN 0-13-508301-X. 5.5. FP FP is a side-effect free, combinator style language, described in:"Can programming be liberated from the von Neumann style?", JohnBackus, Communications of the ACM, 21, 8, pp.613-641, 1978.A interpreter and a compiler (to C) for FP are available by ftp from: Host: gatekeeper.dec.com; Directory: pub/usenet/comp.sources.unix/volume13/funcproglang; Directory: pub/usenet/comp.sources.unix/volume20/fpc.The Illinois FP system supports a modified version of FP that has a moreAlgol-like syntax and structure, and is described in the followingarticle:"The Illinois functional programming interpreter", Arch D. Robison,Proceedings of the SIGPLAN '87 Symposium on Interpreters andInterpretive Techniques, SIGPLAN notices, Volume 22, Number 7, July 1987. 5.6. Gofer The Gofer system provides an interpreter for a small language basedclosely on the current version of the Haskell report. In particular,Gofer supports lazy evaluation, higher-order functions, polymorphictyping, pattern-matching, support for overloading, etc.The most recent version of Gofer, 2.30a, is available by ftp from: Host: ftp.cs.nott.ac.uk; Directory: /nott-fp/languages/gofer.Gofer runs on a wide range of machines including PCs, Ataris, Amigas,etc. as well as larger Unix-based systems. A version for the AppleMacintosh is also available, by ftp from: Host: ftp.dcs.glasgow.ac.uk; Directory: /pub/haskell/gofer/macgofer.Please note the spelling of Gofer, derived from the notion that functionallanguages are GO(od) F(or) E(quational) R(easoning). This is not to beconfused with `Gopher', the widely used internet distributed informationdelivery system. 5.7. Haskell In the mid-1980s, there was no "standard" non-strict, purely-functionalprogramming language. A language-design committee was set up in 1987,and the Haskell language is the result. At the time of writing, Haskell98 is the latest version of the language. Further information aboutHaskell, including the latest version of the Haskell report, isavailable on the web from:http://www.haskell.org/;http://www-i2.informatik.rwth-aachen.de/Forschung/FP/Haskell/.At the time of writing, there are three different Haskell systemsavailable, developed by groups at Chalmers, Glasgow and Yale. Thesesystems are available by ftp from the following sites: Host: ftp.cs.chalmers.se; Directory: /pub/haskell. Host: ftp.dcs.glasgow.ac.uk; Directory: /pub/haskell. Host: haskell.cs.yale.edu; Directory: /pub/haskell. Host: ftp.cs.nott.ac.uk; Directory: /haskell. Host: src.doc.ic.ac.uk; Directory: /pub/computing/programming/languages/haskell.You can join the Haskell mailing list by emailingmajordomo@dcs.gla.ac.uk,with a message body of the form:subscribe haskell Forename Surname <email@address>. 5.8. Hope Hope is a small polymorphically-typed functional language, and was thefirst language to use call-by-pattern. Hope was originally strict, butthere are versions with lazy lists, or with lazy constructors butstrict functions. Further information is available on the web from:http://www.soi.city.ac.uk/~ross/Hope/. 5.9. Hugs Hugs, the Haskell User's Gofer System, is an interpreted implementationof Haskell with an interactive development environment much like thatof Gofer.Further information about Hugs is available on the web from:http://www.haskell.org/hugs/ 5.10. Id Id is a dataflow programming language, whose core is a non-strictfunctional language with implicit parallelism. It has the usualfeatures of many modern functional programming languages, includinga Hindley/Milner type inference system, algebraic types and definitionswith clauses and pattern matching, and list comprehensions. 5.11. J J was designed and developed by Ken Iverson and Roger Hui. It issimilar to the language APL, departing from APL in using using theASCII alphabet exclusively, but employing a spelling scheme thatretains the advantages of the special alphabet required by APL. Ithas added features and control structures that extend its power beyondstandard APL. Although it can be used as a conventional proceduralprogramming language, it can also be used as a pure functional programminglanguage. Further information about J is available on the web from:http://www.jsoftware.com. 5.12. Miranda Miranda was designed in 1985-6 by David Turner with the aim of providinga standard non-strict purely functional language, and is described inthe following articles: "Miranda: a non-strict functional language with polymorphic types",D.A. Turner, Proceedings FPLCA, Nancy, France, September 1985(Springer LNCS vol 201, pp 1-16). "An overview of Miranda", D.A. Turner, SIGPLAN Notices, vol 21,no 12, pp 158-166, December 1986.Miranda was the first widely disseminated language with non-strictsemantics and polymorphic strong typing, and is running at over 600sites, including 250 universities. It is widely used for teaching,often in conjunction with "Introduction to Functional Programming", byBird and Wadler, which uses a notation closely based on Miranda. Ithas also had a strong influence on the subsequent development of thefield, and provided one of the main inputs for the design of Haskell.The Miranda™ system is a commercial product of Research Software Limited.Miranda release two (the current version at the time of writing) supportsunbounded precision integers and has a module system with provision forparameterized modules and a built in "make" facility. The compiler worksin conjunction with a screen editor and programs are automaticallyrecompiled after edits. There is also an online reference manual.Further information about Miranda is available on the web from:http://miranda.org.ukMiranda is not in the public domain but is free for personal andeducational use. 5.13. Mercury Mercury is a logic/functional programming language, which combinesthe clarity and expressiveness of declarative programming with advanced static analysis and error detection facilities. It has astrong type system, a module system (allowing separate compilation),a mode system, algebraic data types, parametric polymorphism,support for higher-order programming, and a determinism system--- all of which are aimed at both reducing programming errorsand providing useful information for programmers and compilers.The Mercury compiler is written in Mercury itself, and compilesto C. The compiler is available for a variety of platformsrunning Unix and Microsoft operating systems.Further information about Mercury is available on the web from:http://www.cs.mu.oz.au/mercury. 5.14. ML ML stands for meta-language, and is a family of advanced programminglanguages with (usually) functional control structures, strictsemantics, a strict polymorphic type system, and parameterized modules.It includes Standard ML, Lazy ML, CAML, CAML Light, and variousresearch languages. Implementations are available on many platforms,including PCs, mainframes, most models of workstation, multi-processorsand supercomputers. ML has many thousands of users, and is taught toundergraduates at many universities.There is a moderated usenet newsgroup, comp.lang.ml, for discussion oftopics related to ML. A list of frequently asked questions for thisnewsgroup (which includes pointers to many of the differentimplementations and variants of ML) is available by ftp from: Host: pop.cs.cmu.edu; Directory: /usr/rowan/sml-archive/.The Standard ML language is formally defined by:"The Definition of Standard ML - Revised", Robin Milner, Mads Tofte,Robert Harper, and David MacQueen, MIT, 1997. ISBN 0-262-63181-4.Further information is available on the web from:http://mitpress.mit.edu/promotions/books/MILDPRF97. "Commentary on Standard ML", Robin Milner and Mads Tofte, MIT,1990. ISBN 0-262-63137-7.Further information is available on the web from:http://mitpress.mit.edu/promotions/books/MILCPF90.There is now a revised version of Standard ML, sometimes referred to as"Standard ML '97" to distinguish it from the original 1990 version. Thenew version combines modest changes in the language with a majorrevision and expansion of the SML Basis Library. Further detailsabout Standard ML '97 are available on the web from:http://cm.bell-labs.com/cm/cs/what/smlnj/sml97.html. 5.15. NESL NESL is a fine-grained, functional, nested data-parallel language,loosly based on ML. It includes a built-in parallel data-type,sequences, and parallel operations on sequences (the element type of asequence can be any type, not just scalars). It is based on eagerevaluation, and supports polymorphism, type inference and a limited useof higher-order functions. Currently, it does not have support formodules and its datatype definition is limited. Except for I/O andsome system utilities it is purely functional (it does not supportreference cells or call/cc). The NESL compiler is based on delayedcompilation and compiles separate code for each type a function isused with (compiled code is monomorphic). The implementation thereforerequires no type bits, and can do some important data-layout optimizations(for example, double-precision floats do not need to be boxed, and nestedsequences can be laid out efficiently across multiple processors.) Forseveral small benchmark applications on irregular and/or dynamic data(for example, graphs and sparse matrices) it generates code comparablein efficiency to machine-specific low-level code (for example, Fortran or C.)The current implementation of NESL runs on workstations, the ConnectionMachines CM2 and CM5, the Cray Y-MP and the MasPar MP2.Further information about NESL is available on the web from:http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/www/nesl.htmlor by ftp from: Host: nesl.scandal.cs.cmu.edu; Directory: nesl.You can join to the NESL mailing list by emailingnesl-request@cs.cmu.edu. 5.16. OPAL The language OPAL has been designed as a testbed for the development offunctional programs. Opal molds concepts from Algebraic Specificationand Functional Programming, which shall favor the formal developmentof large production-quality software that is written in a purelyfunctional style. The core of OPAL is a strongly typed, higher-order,strict applicative language that belongs to the tradition of Hope andML. The algebraic flavour of OPAL shows up in the syntactical appearanceand in the preference of parameterization to polymorphism.OPAL is used for research on the highly optimizing compilation of applicativelanguages. This has resulted in a compiler which produces very efficientcode. The OPAL compiler itself is entirely written in OPAL. Installationis straightforward and has been successfully performed for SPARCs,DECstations, NeXTs, and PCs running LINUX.Further information about OPAL is available by ftp from: Host: ftp.cs.tu-berlin.de; Directory: /pub/local/uebb/. 5.17. Oz Oz is a concurrent constraint programming language designed forapplications that require complex symbolic computations, organizationinto multiple agents, and soft real-time control. It is based on a newcomputation model providing a uniform foundation for higher-orderfunctional programming, constraint logic programming, and concurrentobjects with multiple inheritance. From functional languages Ozinherits full compositionality, and from logic languages Oz inheritslogic variables and constraints (including feature and finite domainconstraints.) Search in Oz is encapsulated (no backtracking) andincludes one, best and all solution strategies.DFKI Oz is an interactive implementation of Oz featuring am Emacs programminginterface, a concurrent browser, an object-oriented interface to Tcl/Tk,powerful interoperability features (sockets, C, C++), an incrementalcompiler, a garbage collector, and support forstand-alone applications. Performance is competitive with commercialProlog and Lisp systems. DFKI Oz is available for many platformsrunning Unix/X, including Sparcs and 486 PCs, and has been used forapplications including simulations, multi-agent systems, naturallanguage processing, virtual reality, graphical user interfaces,scheduling, placement problems, and configuration.Further information about Oz is available on the web from:http://www.ps.uni-sb.de/oz/or by ftp from: Host: ftp.ps.uni-sb.de; Directory: /pub/oz.Specific questions on Oz may be emailedoz@ps.uni-sb.de.You can join the Oz users mailing list by emailingoz-users-request@ps.uni-sb.de. 5.18. Pizza Pizza is a strict superset of Java that incorporates three ideas fromfunctional programming: Parametric polymorphism; Higher-order functions; Algebraic data types.Pizza is defined by translation into Java and compiles into the JavaVirtual Machine, requirements which strongly constrain the designspace. Thus Pizza programs interface easily with Java libraries, andprograms first developed in Pizza may be automatically converted toJava for ease of maintenance. The Pizza compiler is itself written inPizza, and may be used as a replacement for Sun's Java compiler(except that the Pizza compiler runs faster). Pizza was designed by Martin Odersky and Philip Wadler, and implementedby Odersky. The design is described in the following paper: "Pizza into Java: translating theory into practice", Martin Oderskyand Philip Wadler, 24th ACM Symposium on Principles of ProgrammingLanguages, Paris, January 1997.The paper, downloads, and other information on Pizza is available onthe web from any of the following locations (which mirror each other):http://www.cis.unisa.edu.au/~pizza;http://cm.bell-labs.com/cm/cs/who/wadler/pizza/welcome.html;http://wwwipd.ira.uka.de/~pizza;http://www.math.luc.edu/pizza/;ftp://ftp.eecs.tulane.edu/pub/maraist/pizza/welcome.html.Pizza has received a `cool' award from Gamelan(http://www-c.gamelan.com/.) 5.19. Scheme Scheme is a dialect of Lisp that stresses conceptual elegance andsimplicity. It is specified in R4RS and IEEE standard P1178. Schemeis much smaller than Common Lisp; the specification is about 50 pages.Scheme is often used in computer science curricula and programminglanguage research, due to its ability to simply represent manyprogramming abstractions.Further information about Scheme is available on the web from:http://www.schemers.org.There is an unmoderated usenet newsgroup,comp.lang.scheme,for the discussion of topics related to Scheme. A list of frequentlyasked questions (which includes details of the many books and papersconcerned with Scheme) for this newsgroup is available by ftp from: Host: ftp.think.com; Directory: /public/think/lisp/. 5.20. Sisal Sisal (Streams and Iteration in a Single Assignment Language) is afunctional language designed with several goals in mind: to supportclear, efficient expression of scientific programs; to free applicationprogrammers from details irrelevant to their endeavors; and, to allowautomatic detection and exploitation of the parallelism expressed insource programs.Sisal syntax is modern and easy to read; Sisal code looks similar toPascal, Modula, or Ada, with modern constructs and long identifiers.The major difference between Sisal and more conventional languages isthat it does not express explicit program control flow.Sisal semantics are mathematically sound. Programs consist of functiondefinitions and invocations. Functions have no side effects, taking asinputs only explicitly passed arguments, and producing only explicitlyreturned results. There is no concept of state in Sisal. Identifiersare used, rather than variables, to denote values, rather than memorylocations.The Sisal language currently exists for several shared memory andvector systems that run Berkeley Unix(tm), including the SequentBalance and Symmetry, the Alliant, the Cray X/MP and Y/MP, Cray 2, anda few other less well-known ones. Sisal is available on sequentialmachines such as Sparc, RS/6000, and HP. Sisal also runs under MS-DOSand Macintosh Unix (A/UX). It's been shown to be fairly easy to portthe entire language system to new machines.Further information about Sisal is available on the web from:http://www.llnl.gov/sisal/SisalHomePage.html.The original version of this Frequently Asked Questions list (FAQ) was compiled and edited byMark P. Jones.All questions, comments, corrections, and suggestions regarding this documentshould be addressed to the current editor,Graham Hutton. |
|
