Newsgroups: comp.lang.functional,comp.answers,news.answers Path: news1.ucsd.edu!ihnp4.ucsd.edu!munnari.OZ.AU!news.mel.connect.com.au!news.mira.net.au!Germany.EU.net!main.Germany.EU.net!EU.net!newsfeed.internetmci.com!usenet.eel.ufl.edu!warwick!nott-cs!mpj From: mpj@cs.nott.ac.uk (Mark Jones) Subject: comp.lang.functional Frequently Asked Questions (monthly posting) Message-ID: Followup-To: comp.lang.functional Summary: This posting contains a list of frequently asked questions (and their answers) about functional programming languages and their implementations. Supersedes: Organization: University of Nottingham, Department of Computer Science Date: Mon, 29 Jul 1996 10:48:55 GMT Approved: news-answers-request@MIT.Edu Expires: Fri, 30 Aug 1996 18:00:00 GMT Lines: 1175 Xref: news1.ucsd.edu comp.lang.functional:5538 comp.answers:15819 news.answers:63205 Archive-name: func-lang-faq Url: http://www.cs.nott.ac.uk/Department/Staff/mpj/faq.html Last-modified: July 29, 1996 ---------------------------------------------------------------------- A Frequently Asked Questions list (FAQ) for comp.lang.functional ---------------------------------------------------------------------- Here is the latest version of the FAQ, generated from the HTML version which is available on the World Wide Web from: http://www.cs.nott.ac.uk/Department/Staff/mpj/faq.html For those without access to the Web, a plain text version of this document is available by ftp from: host : ftp.cs.nott.ac.uk directory: pub/nott-fp/comp.lang.functional Your comments on the FAQ are most welcome. ---------------------------------------------------------------------- New this month: o Updated details for second edition of "Concurrent Programming in Erlang" in the entry for Erlang in Section 3. o Added a pointer to Philip Wadler's Guide to Functional Programming on the Web in Section 4.3. o Section 4.2 describes the mira2hs-1.05 and mira2lml-0.00 translators, for translating from Miranda(TM) to LML and Haskell, respectively. Unfortunately, these programs do not appear to be available from their original source -- can anyone suggest an alternative source? ---------------------------------------------------------------------- TABLE OF CONTENTS: 1) GENERAL QUESTIONS: 1.1) What is a functional language? 1.2) Where can I find out more about the history and motivation for functional programming? 1.3) Are there any books about functional programming? 1.4) Where is a good place to look for information about current research in functional languages? 1.5) Where can I find out about the use of functional languages in education? 1.6) What other newsgroups might be of interest to readers of comp.lang.functional? 1.7) Is comp.lang.functional archived anywhere? 2) FREQUENT TOPICS OF DISCUSSION: 2.1) What is a monad? 2.2) How can I write a parser in a functional language? 2.3) What does it mean to say that a language is strict/non-strict? 2.4) Where can I find out about applications of functional programming? 2.5) What about the performance of functional programs? 2.6) What is a purely functional language? 2.7) What is "currying", and where does it come from? 2.8) Other subjects 3) LANGUAGE IMPLEMENTATIONS: ASpecT, Caml, Clean, Erlang, FP, Gofer, Haskell, Hope, Hugs, Id, IFP, J, Miranda(TM), ML, NESL, OPAL, Scheme and Sisal. 4) OTHER RESOURCES: 4.1) Bibliographies: 4.2) Translators: 4.3) Miscellaneous: 5) CREDITS AND DISCLAIMERS: ---------------------------------------------------------------------- 1) GENERAL QUESTIONS: Comp.lang.functional is an unmoderated usenet newsgroup for the discussion of functional programming languages, including their design, application, theoretical foundation and implementation. 1.1) What is a functional language? Opinions differ, even within the functional programming community, on the precise definition of ``functional programming languages''. Here is a definition that, broadly speaking, represents the kind of languages that are discussed in this newsgroup: Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these language are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style. For example, consider the task of calculating the sum of the integers from 1 to 10. In an imperative language, this might be expressed using a loop, repeatedly updating the values held in counter and accumulator variables: total = 0; for (i=1; i<=10; ++i) total += i; In a functional language, the same program would be expressed without any variable updates. For example, in Haskell or Miranda, the required sum can be calculated by evaluating the expression: sum [1..10]. Here, [1..10] is an expression that represents the list of integers from 1 to 10, while sum is a function that can be used to calculate the sum of an arbitrary list of values. The same idea could also be used in strict languages like ML or Scheme, but it is more common to find such programs written with an explicit loop, often expressed as a form of recursion. Nevertheless, there is still no need to update the values of the variables involved. SML let fun sum i tot = if i=0 then tot else sum (i-1) (tot+i) in sum 10 0 end Scheme (define sum (lambda (from total) (if (= 0 from) total (sum (- from 1) (+ total from))))) (sum 10 0) Of course, it is often possible to write programs in an imperative language using a functional style, and vice versa. It is then a matter of opinion whether a particular language can be described as functional or not. 1.2) Where can I find out more about the history and motivation for functional programming? Here are a couple of references that should help: o "Conception, Evolution, and Application of Functional Programming Languages", Paul Hudak, ACM Computing Surveys, Volume 21, Number 3, pp.359--411, 1989. o "Why functional programming matters", John Hughes, The Computer Journal, Volume 32, Number 2, April 1989. 1.3) Are there any books about functional programming? Yes, there are quite a few. For details about programming in a functional language: o "Introduction to functional programming", Richard Bird and Philip Wadler, Prentice Hall, 1988. ISBN 0-13-484189-1. o "ML for the working programmer", L.C. Paulson, Cambridge University Press, 1991. ISBN 0-521-39022-2. And for those with an interest in implementation: o "The implementation of functional programming languages", Simon Peyton Jones, Prentice Hall, 1987. ISBN 0-13-453333-X. o "Compiling with continuations", Andrew Appel, Cambridge University Press, 1992. ISBN 0-521-41695-7. For brevity, I've restricted this list to two books in each of the above categories, one concerned with non-strict languages, the other with strict languages. There are several other good books in each category. The following article may also be of interest to those looking for books about functional programming: o Simon Thompson, Comparative review of functional programming textbooks (Bailey, Bird and Wadler, Holyer, Paulson, Reade, Sokoloski, Wikstrom), Computing Reviews, May 1992 (CR number 9205-0262). 1.4) Where is a good place to look for information about current research in functional languages? Here are some good places to start: Journals: o The Journal of Functional Programming, published by CUP. o Lisp and Symbolic Computation, published by Kluwer. o Journal of Functional and Logic Programming (electronic journal), published by MIT Press (http://www.cs.tu-berlin.de/journal/jflp/). Conference proceedings: o Lisp and Functional programming (LFP). o Functional Programming Languages and Computer Architecture (FPCA). o Principles of Programming Languages (POPL). o European Symposium on Programming (ESOP). Most of these are published by the ACM press, or in the Springer Verlag LNCS (Lecture Notes in Computer Science) Series. There are also two new conferences that are particularly relevant to functional programming: Functional Programming Languages in Education (FPLE), the first meeting of which was held in Nijmegen, The Netherlands, December 1995. Proceedings available in Springer LNCS 1022. ICFP '96: The First ACM SIGPLAN International Conference on Functional Programming, to be held in Philadelphia, PA, May 24-26, 1996. Upcoming workshops and summer schools include: The Second Fuji International Workshop on Functional and Logic Programming, November 1--4, 1996, Shonan Village, Japan. http://www.kurims.kyoto-u.ac.jp/~ohori/fuji96.html The Second International Summer School on Advanced Functional Programming Techniques in Olympia, WA, USA. http://www.cse.ogi.edu/PacSoft/summerschool96.html The 1st Workshop on Functional Programming in Argentina. http://www-lifia.info.unlp.edu.ar/ingles/jaiio-fp.htm (Additional contributions to this section are welcome!) 1.5) Where can I find out about the use of functional languages in education? Functional languages are gathering momentum in education because they facilitate the expression of concepts and structures at a high level of abstraction. Information about the use of functional programming languages in education is available on the Web from: http://www.cs.kun.nl/fple/. 1.6) What other newsgroups might be of interest to readers of comp.lang.functional? There are several newsgroups dealing with related languages and ideas, including: o comp.lang.ml for discussion related to ML o comp.lang.scheme for discussion about Scheme o comp.lang.lisp for discussion about Lisp o comp.lang.apl for discussion about APL, J, etc. 1.7) Is comp.lang.functional archived anywhere? No, as far as I know, there is no public archive of comp.lang.functional (but, of course, many readers keep copies of old articles for their personal use). The possibility of establishing a public archive has been raised a number of times in the past but have not been pursued due to an apparent lack of interest, and concerns that archiving might discourage novices from posting articles. ---------------------------------------------------------------------- 2) FREQUENT TOPICS OF DISCUSSION: 2.1) What is a monad? The concept of a monad comes from category theory; I'll spare you the full details since you can find these in standard text books on the subject. Much of the recent interest in monads in functional programming is the result of recent papers that show how monads can be used to describe all kinds of different programming language features -- for example, I/O, manipulation of state, continuations and exceptions -- in purely functional languages like Haskell: o Philip Wadler, Comprehending Monads (from the ACM conference on LISP & Functional Programming, Nice, France, 1990). o Philip Wadler, The Essence of Functional Programming (from ACM Principles of Programming Languages 1992). o Simon Peyton Jones and Philip Wadler, Imperative Functional Programming (from ACM Principles of Programming Languages 1993). These papers are essential reading for anyone interested in the use of monads for functional programming. Copies of these papers are currently available by anonymous ftp from ftp.dcs.glasgow.ac.uk in the subdirectory pub/glasgow-fp/papers. 2.2) How can I write a parser in a functional language? A parser is a program that converts a list of input tokens, usually characters, into a value of the appropriate type. A simple example might be a function to find the integer value represented by a string of digits. A more complex example might be to translate programs written in a particular concrete syntax into a suitable abstract syntax as the first stage in the implementation of a compiler or interpreter. There are two common ways to write a parser in a functional language: o Using a parser generator tool. Some functional language implementations support tools that generate a parser automatically from a specification of the grammar (in much the same way that a C programmer uses yacc). Different tools are available, depending on the language and implementation used. Some specific, often requested examples are: o Happy: a parser generator system for Haskell and Gofer, similar to the tool `yacc' for C. The current public version of Happy is version 0.8, and is available from ftp.dcs.glasgow.ac.uk (130.209.240.50) in the directory pub/haskell/happy. Details about Happy can be also reviewed from its World Wide Web page http://www.dcs.gla.ac.uk/fp/software/happy. o ML-Yacc and Lexgen: an LALR parser generator and a lexical analyzer generator for Standard ML. Included in the distribution of SML/NJ which is available by anonymous ftp from ftp.research.att.com in the directory dist/ml. o Ratatosk: A Parser Generator and Scanner Generator for Gofer. Ratatosk is available by anonymous ftp from ftp.diku.dk in the directory pub/diku/dists. o Using combinator parsing. Parsers are represented by functions and combined with a small set of combinators, leading to parsers that closely resemble the grammar of the language being read. Parsers written in this way can use backtracking. The techniques of combinator parsing have been known for quite some time. Two comparatively recent papers on the subject are: o "How to Replace Failure with a List of Successes", Philip Wadler, FPCA '85, Springer Verlag LNCS 201, 1985. o "Higher-order functions for parsing", Graham Hutton, Journal of Functional Programming, 2, 3, July 1992. The second paper, which includes some references to other related papers, is available from http://www.cs.nott.ac.uk/Department/Staff/gmh/. Simple parsing libraries written in Gofer and Lazy ML are available from the same place. 2.3) What does it mean to say that a language is strict/non-strict? Here's one (operational) way to explain the difference: In a strict language, the arguments to a function are always evaluated before it is invoked. As a result, if the evaluation of an expression exp does not terminate properly (for example, because it generates a run-time error or enters an infinite loop), then neither will an expression 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 evaluated until their values are actually required. For example, evaluating an expression of the form f(exp) may still terminate properly, even if evaluation of exp would not, if the value of the parameter is not used in the body of f. Miranda and Haskell are examples of this approach. It is possible to support a mixture of these two approaches; some versions of Hope do this. 2.4) Where can I find out about applications of functional programming? A list of real world applications of functional programming is available on the World Wide Web from: http://www.dcs.gla.ac.uk/fp/realworld. The list includes programs written in several different functional languages. The main criterion for being considered real-world is that the program was written primarily to perform some task, not primarily to experiment with functional programming. A special issue of the Journal of Functional Programming, Volume 5, Part 3, July 1995, deals with state-of-the-art applications of pure functional programming languages. 2.5) What about the performance of functional programs? In some circles, programs written in functional languages, have obtained a reputation for lack of performance. Part of this results from the high-level of abstraction that is common in such programs and from powerful features like higher-order functions, automatic storage management, etc. Of course, the performance of functional languages keeps improving with new developments in compiler technology. The paper below compares five current implementations of lazy functional languages: o ``Benchmarking implementations of lazy functional languages'' P. H. Hartel and K. G. Langendoen FPCA 93, ACM, pp 341-349 (By ftp: ftp.fwi.uva.nl, directory pub/functional). Experiments with a heavily optimising compiler for Sisal, a strict functional language, show that functional programs can be faster than Fortran: o ``Retire FORTRAN? A debate rekindled'' D. C. Cann, CACM, 35(8), pp. 81-89, Aug. 1992 Postscript versions of a number of papers from the recent conference on High Performance Functional Computing (HPFC) are available on the World Wide Web from ftp://sisal.llnl.gov/pub/hpfc/index.html or by anonymous ftp from ftp://sisal.llnl.gov/pub/hpfc/papers95. Over 25 implementations of different functional languages have been compared using a single program, the `Pseudoknot' benchmark, which is a floating-point intensive application taken from molecular biology. The principal aspects studied are compile time and execution time for the various implementations. An important consideration is how the program can be modified and tuned to obtain maximal performance on each language implementation. A paper describing the pseudoknot benchmark is currently available from ftp://ftp.fwi.uva.nl/pub/computer-systems/functional/reports/, and will be published in the Journal of Functional Programming. 2.6) What is a purely functional language? This question has been the subject of some debate in recent messages posted to comp.lang.functional. It is widely agreed that languages like Haskell and Miranda are `purely functional', while SML and Scheme are not. However, there are some small differences of opinion about the precise technical motivation for this distinction. One definition that has been suggested is as follows: The term `purely functional language' is often used to describe languages which perform all their computations via function application. This is in contrast to languages, like Scheme and Standard ML, which are predominantly functional but also allow `side effects' (computational effects caused by expression evaluation which persist after the evaluation is completed). Sometimes, the term `purely functional' is also used in a broader sense to mean languages which might incorporate computational effects, but without altering the notion of `function' (as evidenced by the fact that the essential properties of functions are preserved.) Typically, the evaluation of an expression can yield a `task' which is then executed separately to cause computational effects. The evaluation and execution phases are separated in such a way that the evaluation phase does not compromise the standard properties of expressions and functions. The input/output mechanisms of Haskell, for example, are of this kind. 2.7) What is "currying", and where does it come from? (The following discussion draws heavily from Rosser's history of the lambda-calculus [1] and on some notes prepared by Stefan Kahrs.) The lambda-calculus originated in order to study functions more carefully. It was observed by Frege in 1893 that it suffices to restrict attention to functions of a single argument. For example, for any two parameter function f(x,y), there is a one parameter function f' such that f'(x) is a function which can be applied to y to give (f'(x))(y) = f (x,y). By convention, we denote function application by juxtaposition, and assume that it associates to the left so that this equation becomes f' x y = f(x,y). From a mathematical perspecive, this corresponds to the well known fact that the sets (AxB->C) and (A->(B->C)) are isomorphic ["x" is cartesian product, "->" is function space]. Apparently, Frege did not pursue the idea further. It was rediscovered independently by Sch\"onfinkel [2] together with the astonishing conclusion that all functions having to do with the structure of functions can be built up out of only two basic combinators, K and S. About a decade later, this sparked off the subject of combinatory logic invented by Haskell Curry [4]. The term "currying" honours him; we typically refer to the function f' in the example above as the "curried" form of the function f. From a functional perspective, we can describe currying 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) References: 1. Rosser, J. Barkley, "Highlights of the history of the lambda-calculus", ACM Lisp and Functional Programming, 1982. 2. Sch\"onfinkel, Moses, "Ueber die Bausteine der mathematischen Logik", Mathematische Annalen, 92, 1924. An English translation, "On the building blocks of mathematical logic", appears in [3]. 3. van Heijenoort, Jean, "From Frege to G\"odel", Harvard University Press, Cambridge, 1967. 4. Curry, Haskell B., and Feys, Robert, "Combinatory Logic", North-Holland, 1958. Also contains many references to earlier work by Curry, Church, and others. 2.8) Other subjects: There probably ought to be something here about programming with GUIs (Fudgets, eXene, etc.), Input/Output, General Foundations (basics of lambda calculus, perhaps?), and parallelism. Anybody want to write some brief comments addressing one/some of these? (Some sections are already in preparation.) ---------------------------------------------------------------------- 3) LANGUAGE IMPLEMENTATIONS: ASpecT ASpecT is a strict functional language, developed at the University of Bremen, originally intended as an attempt to provide an implementation for (a subset of) Algebraic Specifications of Abstract Datatypes. The system was designed to be as user-friendly as possible, including overloading facilities and a source-level debugger. Efficiency called for call-by-value evaluation and reference counting memory management. Over the years more and more features were added, including subsorting, functionals and restricted polymorphism. The ASpecT compiler translates the functional source code to C, resulting in fast and efficient binaries. ASpecT is available by anonymous FTP from ftp.Uni-Bremen.DE in the directory /pub/programming/languages/ASpecT. ASpecT has been ported to many platforms like Sun3, Sun4, Dec VAX, IBM RS6000, NeXT, Apple A/UX, PC (OS/2, Linux), Amiga and Atari ST/TT. The most important application of ASpecT to date is the interactive graph visualization system daVinci; currently (May '95), version 1.4.2 is composed of 24.000 lines of ASpecT and 16.000 lines of C code. daVinci is available by anonymous FTP from ftp.Uni-Bremen.DE in the directory /pub/graphics/daVinci. daVinci is an OPEN LOOK program, available for Sun SPARCstations (with SunOS 4.1.x and Solaris 2.x), HP workstations (with HP-UX), IBM RS6000 (with AIX) or PC's (with Linux or FreeBSD). For more information please contact the project daVinci by e-mail: daVinci@Informatik.Uni-Bremen.DE or try the URL: http://www.Informatik.Uni-Bremen.DE/~inform/forschung/daVinci/daVinci.html. Caml Caml is a dialect of the ML language developed at INRIA that does not comply 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 one, Caml Light, is distinguished by its small size, modest memory requirements, availability on microcomputers, simple separate compilation, interface with C, and portable graphics functions. It runs on most Unix machines, on the Macintosh and on PCs under Ms Windows and MSDOS. The current version is 0.71. A more ambitious implementation, Objective Caml (formerly known as Caml Special Light), is also available. It adds the following extensions to Caml Light: o Full support for objects and classes -- here combined for the first time with ML-style type reconstruction. o A powerful module calculus in the style of Standard ML, but providing better support for separate compilation. o A high-performance native code compiler (in addition to a Caml Light-style bytecode compiler). Objective Caml is available for Unix and Windows 95/NT, with the native-code compiler supporting the following processors: Alpha, Sparc, Pentium, Mips, Power, HPPA. Both implementations are available by ftp: ftp.inria.fr, directory lang/caml-light. Further information is available on the web at http://pauillac.inria.fr/caml/index-eng.html (english) or http://pauillac.inria.fr/caml/index-fra.html (french). Clean The Concurrent Clean system is a programming environment for the functional language Concurrent Clean, developed at the University of Nijmegen in The Netherlands. The system is one of the fastest implementations of functional languages available at the moment. Through the use of uniqueness typing, its I/O libraries make it possible to do modern, yet purely functional I/O (including windows, menus, dialogs etc.) in Concurrent Clean. With the Concurrent Clean system, it is possible to develop real-life applications in a purely functional language, interfacing with non-functional systems. With version 1.0, the language emerged from an intermediate language to a proper programming language. Particular features include: o lazy and purely functional o strongly typed - based on Milner/Mycroft scheme o existential types, type classes, constructor classes o inferred polymorphic uniqueness types o records, 'mutable' arrays, module structure o modern I/O o built-in strictness analyser but also programmer-influenced o evaluation order by annotations o annotations for parallelism ftp: host ftp.cs.kun.nl, directory pub/Clean available for: Mac (Motorola, PowerPC), PC (OS2, Linux), Sun 4 (Solaris, SunOS). Information about Clean is also available on the World Wide Web: http://www.cs.kun.nl/~clean. There is a book describing the background of Concurrent Clean and its implementation on sequential and parallel architectures: "Functional Programming and Parallel Graph Rewriting", Rinus Plasmeijer and Marko van Eekelen, Addison Wesley, International Computer Science Series. Hardcover, 571 pages. ISBN 0-201-41663-8 Erlang Concurrent functional programming language for large industrial real-time systems. Untyped. Pattern matching syntax. Recursion equations. Explicit concurrency, asynchronous message passing. Relatively free from side effects. Transparent cross-platform distribution. Primitives for detecting run-time errors. Real-time GC. Modules. Dynamic code replacement (change code in running real-time system, without stopping system). Foreign language interface. Availability: Free version (available to Universities subject to non-commercial license) with no support. Commercial versions with support are available (Ericsson Software Technology AB, Erlang Systems Division). Info: erlang@erix.ericsson.se, World Wide Web: http://www.ericsson.se/cslab/erlang/, ftp Info: euagate.eua.ericsson.se:/pub/eua/erlang/info. See also: "Concurrent Programming in Erlang" (second edition), J. Armstrong, M. Williams, R. Virding & Claes Wikstrm, Prentice Hall, 1996. ISBN 0-13-508301-X. A DOS/Windows version of Erlang 4.2, requiring a 386/486 machine with at least 4 Mbytes of memory is now available by anonymous ftp from: ftp: euagate.eua.ericsson.se:/pub/eua/erlang/release FP Backus' side-effect free, combinator style language described by: "Can Programming be Liberated from the Von Neumann Style?", J. Backus, Communications of the ACM, 21, 8, pp.613-641, 1978. There are (at least) three easily accessible implementations of FP. Two of these are available from any site that archives comp.sources.unix. For example, at gatekeeper.dec.com you will find these in: o pub/usenet/comp.sources.unix/volume13/funcproglang o pub/usenet/comp.sources.unix/volume20/fpc The first of these is an interpreter, the second a translator from FP to C. The third implementation, IFP is described separately below. Gofer The Gofer system provides an interpreter for a small language based closely on the current version of the Haskell report. In particular, Gofer supports lazy evaluation, higher-order functions, polymorphic typing, pattern-matching, support for overloading, etc. The most recent version of Gofer, 2.30a, is available by ftp: ftp.cs.nott.ac.uk/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 Apple Macintosh has been produced and is available by anonymous ftp from ftp.dcs.glasgow.ac.uk in the directory pub/haskell/gofer/macgofer. Please note the spelling, derived from the notion that functional languages are GO(od) F(or) E(quational) R(easoning). This is not to be confused with `Gopher', the widely used Internet distributed information delivery system! Haskell In the mid-1980s, there was no "standard" non-strict, purely-functional programming language. A language-design committee was set up in 1987, and the Haskell language is the result. The Haskell committee released its report on 1 April 1990. A revised "Version 1.2" appeared in SIGPLAN Notices 27(5) (May 1992), along with a tutorial on Haskell by Hudak and Fasel. At the time of writing, there are three different Haskell systems available, developed by groups at Chalmers, Glasgow and Yale (several others are being developed). These systems are available from the following sites: o Chalmers: ftp.cs.chalmers.se:pub/haskell o Glasgow: ftp.dcs.glasgow.ac.uk:pub/haskell o Yale: haskell.cs.yale.edu:pub/haskell o Nottingham: ftp.cs.nott.ac.uk:pub/haskell. o Imperial: src.doc.ic.ac.uk:pub/computing/programming/languages/haskell mirrors the Glasgow site. Specialized material, or recent releases of these systems may sometimes only be available from the systems ``home site''. Machine-readable versions of the Haskell report, tutorials, and some programs are also available at these sites. A description of the current status of the various Haskell implementations is occasionally posted on the Haskell mailing list, and sometimes on comp.lang.functional. Copies of this document are often kept on the Haskell sites mentioned above. For example, this information may be found in pub/haskell/papers/Haskell.status at the Yale site (haskell.cs.yale.edu). Hope A small polymorphically-typed functional language. First language to use call-by-pattern. Hope was originally strict, but there are versions with lazy lists, or with lazy constructors but strict functions. A fully lazy interpreter is available by ftp from ftp-ala.doc.ic.ac.uk:pub/papers/R.Paterson/hope.tar.gz. More information about Hope is available on the World Wide Web from http://www-ala.doc.ic.ac.uk/~rap/Hope/. Hugs Hugs, the Haskell User's Gofer System, is an interpreted implementation of Haskell with an interactive development environment much like that of Gofer. Almost all of the features of Haskell 1.2 are implemented with the exception of the module system (like Gofer, module headers and import declarations are parsed, but are otherwise ignored). For example, Hugs supports Haskell style type classes, a full prelude, derived instances, defaults, overloaded numeric literals and pattern matching, and bignum arithmetic. Further information about Hugs is available on the World Wide Web from http://www.cs.nott.ac.uk/Department/Staff/mpj/hugs.html or by anonymous ftp from ftp://ftp.cs.nott.ac.uk/pub/haskell/hugs. Id The core of Id is a non-strict functional language with implicit parallelism. It has the usual features of many modern functional languages, including a Hindley/Milner type inference system, algebraic types and definitions with clauses and pattern matching, and list comprehensions. IFP The Illinois FP system is a modified version of Backus' FP with a more Algol-like syntax and structure. Described in: "The Illinois Functional Programming Interpreter", Arch D. Robison, Proceedings of the SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques, SIGPLAN notices vol 22, no 7, July 1987. ftp: a.cs.uiuc.edu. Versions for Unix and MSDOS. J J was designed and developed by Ken Iverson and Roger Hui. It is similar to the language APL, departing from APL in using using the ASCII alphabet exclusively, but employing a spelling scheme that retains the advantages of the special alphabet required by APL. It has added features and control structures that extend its power beyond standard APL. Although it can be used as a conventional procedural programming language, it can also be used as a pure functional programming language. Official site: http://www.jsoftware.com. Also relevant: ftp://watserv1.uwaterloo.ca/languages/j/index.html. Miranda(TM) Miranda was designed in 1985-6 by David Turner with the aim of providing a standard non-strict purely functional language. It is described in: o D. A. Turner ``Miranda: A Non-Strict Functional Language with Polymorphic Types'', Proceedings FPLCA, Nancy, France, September 1985 (Springer LNCS vol 201, pp 1-16). o D. A. Turner ``An Overview of Miranda'', SIGPLAN Notices, vol 21, no 12, pp 158-166 (December 1986). Miranda was the first widely disseminated language with non-strict semantics and polymorphic strong typing, and is now running at over 600 sites, including 250 universities. It is widely used for teaching, often in conjunction with "Introduction to Functional Programming", by Bird and Wadler, which uses a notation closely based on Miranda. It has also had a strong influence on the subsequent development of the field and provided one of the main inputs for the design of the later language Haskell (see separate entry). Miranda was awarded a medal for technical achievement by the British Computer Society (BCS Awards, 1990). The Miranda system is a commercial product of Research Software Limited. Miranda release two (the current version) supports unbounded precision integers and has a module system with provision for parameterized modules and a built in "make" facility. The compiler works in conjunction with a screen editor and programs are automatically recompiled after edits. There is an online reference manual. Note that the word "Miranda" is a trademark (TM) of Research Software Limited. There are no public domain versions of Miranda. Further information about Miranda may be obtained from mira-request@ukc.ac.uk or Research Software Ltd, 23 St Augustines Road, Canterbury CT1 1XP, ENGLAND, phone: (+44) 227 471844, fax: (+44) 227 454458 ML ML (which stands for Meta-Language) is a family of advanced programming languages with [usually] functional control structures, strict semantics, a strict polymorphic type system, and parameterized modules. It includes Standard ML, Lazy ML, CAML, CAML Light, and various research languages. Implementations are available on many platforms, including PCs, mainframes, most models of workstation, multi-processors and supercomputers. ML has many thousands of users, is taught at many universities (and is the first programming language taught at some). There is a moderated usenet newsgroup, comp.lang.ml, for the discussion of topics related to ML. A list of frequently asked questions for ML is posted to this group each month by the moderator, Rowan Davies. The FAQ may also be retrieved from ftp://pop.cs.cmu.edu/usr/rowan/sml-archive/faq.txt. The first paragraph above is taken directly from this FAQ. There are several implementations of ML including Poly/ML, SML/NJ, PoplogML, Edinburgh, ANU ML, Micro ML, sml2c, Caml Light, and the ML kit. Further details for each of these systems are included in the FAQ. The Standard ML language is formally defined by: o "The Definition of Standard ML", Robin Milner, Mads Tofte and Robert Harper, MIT, 1990. ISBN: 0-262-63132-6 o "Commentary on Standard ML", Robin Milner and Mads Tofte, MIT, 1991 ISBN: 0-262-63137-7 There are a number of texts describing programming in ML. Again, full details are given in the FAQ. NESL NESL is a fine-grained, functional, nested data-parallel language. The current implementation runs on workstations, the Connection Machines CM2 and CM5, the Cray Y-MP and the MasPar MP2. NESL is loosely based on ML. It includes a built-in parallel data-type, sequences, and parallel operations on sequences (the element type of a sequence can be any type, not just scalars). It is based on eager evaluation, and supports polymorphism, type inference and a limited use of higher-order functions. Currently it does not have support for modules and its datatype definition is limited. Except for I/O and some system utilities it is purely functional (it does not support reference cells or call/cc). The compiler is based on delayed compilation and compiles separate code for each type a function is used with (compiled code is monomorphic). The implementation therefore requires no type bits, and can do some important data-layout optimizations (e.g. double-precision floats don't need to be boxed, and nested sequences can be laid out efficiently across multiple processors). For several small benchmark applications on irregular and/or dynamic data (e.g graphs and sparse matrices) it generates code comparable in efficiency to machine-specific low-level code (e.g. Fortran or C). A NESL home page is available on the WWW from http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/www/nesl.html. The system is available via anonymous ftp from nesl.scandal.cs.cmu.edu (currently 128.2.222.128), in the file nesl/nesl.tar.gz (0.7Mbytes). There is a README file in the nesl directory that contains further information. You can be added to the NESL mailing list by sending e-mail to nesl-request@cs.cmu.edu. The examples and documentation are also available separately. OPAL The language OPAL has been designed as a testbed for the development of functional programs. Opal molds concepts from Algebraic Specification and Functional Programming, which shall favor the (formal) development of (large) production-quality software that is written in a purely functional style. The core of OPAL is a strongly typed, higher-order, strict applicative language which belongs to the tradition of HOPE and ML. The algebraic flavour of OPAL shows up in the syntactical appearance and the preference of parameterization to polymorphism. OPAL is used for research on the highly optimizing compilation of applicative languages. This has resulted in a compiler which produces very efficient code. The OPAL compiler itself is entirely written in OPAL. Papers describing OPAL, and the OPAL compilation system itself, are available by anonymous ftp from: ftp.cs.tu-berlin.de. This includes an overview of OPAL in the file: pub/local/uebb/papers/DesignImplOpal.ps.gz, and a language tutorial: pub/local/uebb/papers/TutorialOpal.ps.gz. The compilation system is in the pub/local/uebb/ocs directory. Installation is straightforward and has been successfully performed for SPARCs, DECstations, NeXTs, and PCs running LINUX. Oz Oz is a concurrent constraint programming language designed for applications that require complex symbolic computations, organization into multiple agents, and soft real-time control. It is based on a new computation model providing a uniform foundation for higher-order functional programming, constraint logic programming, and concurrent objects with multiple inheritance. From functional languages Oz inherits full compositionality, and from logic languages Oz inherits logic variables and constraints (including feature and finite domain constraints). Search in Oz is encapsulated (no backtracking) and includes one, best and all solution strategies. DFKI Oz is an interactive implementation of Oz featuring a programming interface based on GNU Emacs, a concurrent browser, an object-oriented interface to Tcl/Tk, powerful interoperability features (sockets, C, C++), an incremental compiler, a garbage collector, and support for stand-alone applications. Performance is competitive with commercial Prolog and Lisp systems. DFKI Oz is available for many platforms running Unix/X, including Sparcs and 486 PCs. Applications DFKI Oz has already been used for include simulations, multi-agent systems, natural language processing, virtual reality, graphical user interfaces, scheduling, placement problems, and configuration. Version 1.0 of DFKI Oz was released on January 23, 1995 and is available by anonymous ftp from ps-ftp.dfki.uni-sb.de in pub/oz, or through the WWW from http://ps-www.dfki.uni-sb.de/. Tutorials, reference manuals, and research papers are available from the same sources. You may start with "A Survey of Oz" (8 pages) and continue with "An Oz Primer" (110 pages). For specific questions you may mail to oz@dfki.uni-sb.de. To join the Oz users mailing list, contact oz-users-request@dfki.uni-sb.de. Scheme Scheme is a dialect of Lisp that stresses conceptual elegance and simplicity. It is specified in R4RS and IEEE standard P1178. (See question [1-7] for details on standards for Scheme.) Scheme is much smaller than Common Lisp; the specification is about 50 pages. Scheme is often used in computer science curricula and programming language research, due to its ability to represent many programming abstractions with its simple primitives. There is an unmoderated usenet newsgroup, comp.lang.scheme for the discussion of topics related to Scheme, and a list of frequently asked questions for Scheme is posted to the group each month by Mark Kantrowitz. The FAQ list is also available online from several sources; for example, it can be obtained by anonymous ftp from ftp.think.com in the file /public/think/lisp/scheme-faq.text. There are many books and papers dealing with Scheme. Please consult the comp.lang.scheme frequently asked questions list for further details. Information about Scheme is available from the world wide web at http://www-swiss.ai.mit.edu/scheme-home.html. The Scheme Repository is accessible by anonymous ftp at ftp.cs.indiana.edu:/pub/scheme-repository, and contains a Scheme bibliography, copies of the R4RS report, IEEE P1178 specification and other papers, sample Scheme code for a variety of purposes, several utilities, and some implementations. Sisal Sisal (Streams and Iteration in a Single Assignment Language) is a functional language designed with several goals in mind: to support clear, efficient expression of scientific programs; to free application programmers from details irrelevant to their endeavors; and, to allow automatic detection and exploitation of the parallelism expressed in source programs. Sisal syntax is modern and easy to read; Sisal code looks similar to Pascal, Modula, or Ada, with modern constructs and long identifiers. The major difference between Sisal and more conventional languages is that it does not express explicit program control flow. Sisal semantics are mathematically sound. Programs consist of function definitions and invocations. Functions have no side effects, taking as inputs only explicitly passed arguments, and producing only explicitly returned results. There is no concept of state in Sisal. Identifiers are used, rather than variables, to denote values, rather than memory locations. The Sisal language currently exists for several shared memory and vector systems that run Berkeley Unix(tm), including the Sequent Balance and Symmetry, the Alliant, the Cray X/MP and Y/MP, Cray 2, and a few other less well-known ones. Sisal is available on sequential machines such as Sparc, RS/6000, and HP. Sisal also runs under MS-DOS and Macintosh Unix (A/UX). It's been shown to be fairly easy to port the entire language system to new machines. ftp: sisal.llnl.gov (128.115.19.65) A Sisal home page is available on the WWW from http://www.llnl.gov/sisal/SisalHomePage.html. For more information, pleases send an email request to: sisal-info-request@sisal.llnl.gov See also: "Retire FORTRAN? A debate rekindled", David Cann, CACM, 35(8), pp.81-89, Aug 1992 ---------------------------------------------------------------------- 4) OTHER RESOURCES: 4.1) Bibliographies: o Mike Joy maintains a bibliography on Functional Languages, in refer(1) format. It is available by anonymous ftp from: ftp.dcs.warwick.ac.uk in the files: pub/biblio/functional.README and pub/biblio/functional.refer.Z o Tony Davie maintains a bibliography of over 2,600 papers, articles and books on functional programming and functional systems. It can be obtained by anonymous ftp from tamdhu.dcs.st-and.ac.uk in the directory pub/staple, either as a hypercard stack in pubs.sit.Hqx, or as a (compressed) text file in pubs.txt.Z. o Wolfgang Schreiner has compiled an annotated bibliography on parallel functional programming that lists more than 350 publications mostly including their full abstracts. You can retrieve the bibliography by anonymous ftp from ftp.risc.uni-linz.ac.at (193.170.36.100) in pfpbib2.dvi.Z (or pfpbib2.ps.Z). o State in Functional Programming: An Annotated Bibliography, edited by P. Hudak and D. Rabin, is available by anonymous ftp from nebula.cs.yale.edu in the files: state-bib.{ps,dvi}.{Z,gz} 4.2) Translators: o Miranda(TM) to LML and Miranda(TM) to Haskell translators written by Denis Howe are available by anonymous ftp from wombat.doc.ic.ac.uk (146.169.22.42) in directory pub/fp, files mira2hs-1.05 and mira2lml-0.00. 4.3) Miscellaneous: o The Free On-Line Dictionary of Computing is available by Gopher and FTP from wombat.doc.ic.ac.uk. It is not restricted to functional programming but does include quite a few FP terms. o There are a number of pages on the World-Wide-Web that may be useful to those with an interest in functional programming. These include: o Jon Mountjoy's functional languages page: http://carol.fwi.uva.nl/~jon/func.html. o Philip Wadler has written "A Guide to Functional Programming on the Web", available from: http://www.dcs.glasgow.ac.uk/~wadler/guide.html. o The SEL-HPC WWW Functional programming archive: http://www.lpac.ac.uk/SEL-HPC/Articles/FuncArchive.html. o Mark Leone's programming language research page: http://www.cs.cmu.edu/afs/cs.cmu.edu/user/mleone/web/language-research.html. o John Farrell's functional programming page (not currently maintained, but still useful): ftp://coral.cs.jcu.edu.au/web/FP/home.html. o Research group pages: - The Chalmers functional programming page: http://www.cs.chalmers.se/ComputingScience/Research/Functional/. - The Glasgow functional programming page: http://www.dcs.gla.ac.uk/fp. - The Nottingham functional programming page: http://www.cs.nott.ac.uk/Research/fpg/index.html. - The St Andrews functional programming page: http://www.dcs.st-andrews.ac.uk/CompSci/Rsch/Functional/welcome.html. - The Yale functional programming page: http://www.cs.yale.edu/HTML/YALE/CS/haskell/yale-fp.html. - The York functional programming page: http://dcpu1.cs.york.ac.uk:6666/fpg/fpg.html. (For more information on the World-Wide Web, see the WWW FAQ, available by anonymous FTP from rtfm.mit.edu as pub/usenet/news.answers/www/faq.) o Philip Wadler edits a column on functional programming for the Formal Aspects of Computer Science Newsletter, which is published by the British Computing Society Formal Aspects of Computing group and Formal Methods Europe. o The following tools have been developed to allow typesetting of functional programming languages using LaTeX: o Smugweb is a system for typesetting Haskell code that takes advantage of TeX's formatting of mathematical expressions. Further information is available from: http://www.minet.uni-jena.de/~joe/smugweb.html. o The miratex package works by preprocessing Miranda(TM) literate scripts to produce LaTeX files, in which the ASCII based Miranda code has been converted to TeX math. Further information is available from: http://www.cs.tcd.ie/www/jgllgher/miratex/index.html. ---------------------------------------------------------------------- 5) CREDITS AND DISCLAIMERS: The information in this article has been taken from public sources, mostly from articles posted on comp.lang.functional during the past few years. This FAQ includes contributions from many different people -- because of the way that the FAQ was compiled, I regret to say that I do not have a complete list of contributors. The aim of this FAQ is to provide information about functional languages and to reflect widely held views in the functional programming community. Any opinions expressed in this message are those of the individual contributors, and may not be representative either of my own personal views, or of others in the community. It is very likely that this FAQ contains some significant errors and omissions: There are no guarantees for the accuracy of the information provided here. Of course, your corrections and contributions are encouraged! ---------------------------------------------------------------------- For suggestions, comments or questions about this FAQ, please contact mpj@cs.nott.ac.uk ---------------------------------------------------------------------- .