SASL (2nd version)(ID:734/sas006)

Lazy evaluation SASL 

• Country: uk
  • languages for uk
  • uk/1972
• Began: 1972
  • Languages for 1972
  • 1970s languages
  • Third generation
  • High Cold War
• Type:Polymorphic
  • Polymorphic

• Function

Wolfgang Kreutzer, Paddy Krishnan and Bruce J. McKenzie "A Brief History of Functional Programming" view details Abstract: History teaches us to separate worthwhile ideas from short lived fashions and learning about the history of a subject is an important prerequisite for better understanding of current practice. Hudak (1989) gives a detailed and very readable account of the history and foundations of functional programming languages, which we will briefly summarise here.

In 1930 the logician Haskell Curry invented the theory on which many of functional programming's most important ideas have been based (Curry, 1951). Shortly thereafter Alonzo Church (1941) published a paper on what he called the lambda calculus, a model of computation which is commonly considered the root of the functional programming style. Davie (1992), Michaelson (1989) and Hindley & Seldin (1986) provide good introductions to the lambda calculus, while Barendregt (1984) offers a more advanced and formal treatment. LISP was the first programming language which could be used in a functional style. It was invented in 1960 by McCarthy at MIT. LISP was unique among programming languages of that time in that it supported lists as a dynamic data structure, i.e. one whose size and components can change at the time of a program's execution. It also allowed the use of recursion in processing lists and trees. Lisp used ideas taken from lambda calculus to describe "anonymous" (i.e.\ functions without any explicit name) and "higher order" functions (i.e. functions which may take other functions as arguments or generate a newly constructed function as a result). These ideas were quite revolutionary at that time, but they subsequently proved to be very powerful and important for many types of computer applications. Modern versions of LISP such as SCHEME and COMMON LISP offer even better facilities for implementing higher order functions (Abelson et al., 1985; Springer & Friedman, 1989; Steele & Sussman, 1978).

Higher order operations were also extensively used in a programming language called APL, which was invented by Iverson in 1962. APL was intended as an algebraic programming language for array processing, but it also has a functional core. At about the same time in England Landin and Strachey investigated the use of lambda calculus to model the core ideas of imperative languages, a project which later resulted in denotational semantics  as a formal technique for the definition of programming languages (Stoy, 1977; Strachey, 1966). In 1964 Landin proposed the SECD machine as an abstract interpreter for lambda expressions, and this idea formed the basis of the VDL  notation used to give a formal definition for the semantics of the programming PL/1. In an influential 1966 paper Landin described the ISWIM family of languages and identified many central ideas which influenced many later functional language designs. Some years later at Edinburgh University Burstall et al. (1971) invented a version of LISP with an ALGOL -like syntax and a functional subset, which they called POP-2. This later grew into a whole family of languages used mainly for writing "artificial intelligence" applications. Until the late 1970s imperative programming was firmly established in software development and functional programming remained only of academic interest, without much practical significance. This only started to change when John Backus, one of the key developers of FORTRAN, received the prestiguous annual ACM Turing Award in 1978. In his acceptance speech he listed some of the problems associated with an imperative style and suggested how a functional language could solve some of these (Backus, 1978). This generated a brief surge of interest, but his FP language never evolved into a practical tool. The honour of being the first widely used functional programming language instead falls to a language called ML (for "Meta Language"), a hybrid functional/imperative programming tool developed in 1978 by Milner  to help him build a computer assisted proof system. ML   relies on imperative features to communicate with the outside world. Although discouraged, assignments are also possible. ML pioneered the idea of "polymorphic type systems" (Cardelli & Wegner, 1985; Hindley, 1969; Milner, 1978)), which have since been used by virtually all modern functional languages. It is still arguably the most widely used functional programming system today, particularly after a standardised version called "Standard ML", or SML was released by Milner in 1984, borrowing a number of ideas from another functional language called HOPE. Today a large number of universities use SML as a teaching tool. HOPE itself had been designed by Burstall and others at the University of Edinburgh (Burstall et al., 1980) in 1980. It was the first language with fully general pattern matching and facilities for user-defined algebraic data types. While Edinburgh, Oxford and Cambridge were major research centers for functional programming and have remained influential in this regard, interesting work also took place at the universities of St. Andrews (in Scotland) and Kent (in Canterbury). This strand of development is associated with David Turner , who designed and implemented a number of functional programming languages which he then used in teaching. SASL (Turner, 1976) was designed in 1979, as a more readable version of LISP with lazy evaluation. This was followed in 1981 by the KRC language (Turner, 1981). KRC   already had guarded equations, pattern matching and list comprehensions, features which now have become standard within the functional culture. MIRANDA was the next of Turner's (1985) language designs. It added a polymorphic type system and used what he called modules to better support large scale software development. A first implementation of MIRANDA was released in 1982 and it is unique among functional languages in that its implementations are not freely available in the public domain, but have to be paid for.


  
Figure 2.2: A Pedigree of Functional Programming Languages

Academic interest in functional programming increased greatly during the second half of the 1980s, spawned by a growing awareness of the so called "software crisis" as well as advances in hardware design. It soon became clear that an agreement on a common tool for research was desirable, so that work could be shared. For this reason a number of people (e.g. Hudak, Wadler and others) met at the end of the 1987 ACM conference on Principles of Programming Languages (POPL) in Portland (Oregon) to begin work on such a language's design. Work started in October 1987 and a first draft became publicly available in April 1990. This was followed by a more formal description of the new language, released in June 1991 (Hudak & Wadler, 1988) and called HASKELL, with revised versions HASKELL 1.2 in June 1991 (Hudak et al., 1992) and HASKELL 1.3 in September 1993 (Hudak et al., 1995). Today a number of implementations of HASKELL exist. These include those at the universities of Glasgow (Scotland), Göetheborg (Sweden) and Yale (USA). More detailed information can be obtained by sending a message to the haskell mailing list or from the Internet newsgroup comp.lang.functional. GOFER and HUGS are both based on HASKELL. GOFER was originally designed by M. Jones as an environment for learning and teaching functional programming as well as a vehicle for experimentation with language extensions. GOFER was not meant as a tool for large scale software construction and run time efficiency has not been one of its primary goals. Implementations exist for a wide range of Unix-based workstations, as well as for the IBM PC and the Apple MacIntosh. GOFER is documented in (Cunningham, 1994a,b; Jones, 1993, 1994) as well as in a German language textbook by Thiemann (1994). Although its design has always followed Haskell quite closely neither is a proper subset of the other. In 1994 this divergence of features had become sufficiently troublesome to some users who saw GOFER primarily as a light-weight HASKELL implementation for teaching that a new version called HUGS (which stands for "Haskell user's Gofer System") was developed (also by Mark Jones). HUGS has none of GOFER's extensions and is a proper subset of HASKELL. Implementations are now also available for all of the platforms supported by GOFER. HUGS is the language we have chosen to use in this book and all implementations of HUGS, GOFER or HASKELL are compatible with our examples and solutions to exercises. MIRANDA is also quite close to this family, and we have summarized its main differences to HASKELL in an appendix.

HASKELL, ML and MIRANDA are by far the most popular functional languages today. While a range of textbooks based on ML (Harrison, 1993; Myers et al., 1993; Paulson, 1991; Reade, 1989; Sokolowski, 1991; Ullman, 1994; Wikström, 1987) and MIRANDA (Hinze, 1992; Holyer, 1991; Thompson, 1995) are already available, textbooks on HASKELL   are beginning to appear (Davie, 1992; Thompson, 1996). The textbooks by Wikström (1987), Myers et al. (1993) and Holyer (1991) are particularly well suited for a beginner. Bird & Wadler (1988) have written a popular introduction to functional programming, using their own ORWELL language, which is, however, quite close to MIRANDA, HASKELL and GOFER, as is CLEAN. The books by Field & Harrison (1988) and Bailey (1990) are based on HOPE, while an early text book by Henderson (1980) using LISP is still well worth reading. MacLennan (1990) uses a language of his own, but he also offers some help in translating it into LISP or SCHEME. In their examples all of these texts with the exception of Wikström (1987) stress numerical applications, symbolic mathematics and systems programming.
      in "Functional Programming with HUGS: An Introduction to Computer Science using a Functional Programming Language" University of Canterbury, New Zealand January 1997 view details
Resources

• Distribution for SASL
  
  "