Haskell's Role In Prototypes
Review of a Paper from Hudak and Jones

Review 1 - Assignment One - Comp 432

Author: Frank Kruchio
frank.kruchio (AT) paradise.net.nz

Lecturer: Dr Neil Leslie

April 26, 5PM, 2002

List of Tables

Level of abstraction in programming and its impact on productivity.

Abstract:

The roots of the functional programming language Haskell, originate from $\lambda$ calculus. Haskell allows the users of the language to use advanced techniques that are not available and therefore poorly understood by the users of imperative programming languages. Higher-order functions, parametric polymorphism and lazy evaluation (the ability to evaluate infinite lists) are just a few of the advanced but commonly used techniques of expert Haskell programmers. There is concrete evidence that Haskell is more suitable as a prototyping language than imperative languages. Haskell is an excellent language for prototyping due to its powerful language features, modular structure, code reusability and concise syntax. Hudak and Jones reflect on using Haskell on a real world problem, where Haskell shows its strength but these very same strengths are poorly understood or misunderstood by conventional programmers.

Introduction

Haskell as a functional programming language has become popular in recent years because of its simple syntax, conciseness, and clarity. Functional programming is a style of programming that emphasises the use of functions in contrast to object-oriented(imperative style) programming, which emphasises the use of objects. A goal of any programming language is to aid the rapid and accurate development of a diverse range of software. While paper [3] by Hudak and Jones is nearly a decade old, it is interesting to observe Haskell's potential in productivity. In 1993, when this experiment was conducted, Haskell was a relative newcomer, not withstanding the fact that the $\lambda$ calculus had been in place for a long time before that. Even ten years ago, Haskell superseded C++, Ada, Awk and Lisp; which were all `mature', commonly used languages at the time.

Programming languages have fundamental differences. These differences are especially evident between the functional and imperative classes of languages. While computationally they are equivalent, the roots of functional programming languages are in $\lambda$ calculus. A good programmer should have the ability to choose a particular language from a class of programming languages, that is most suitable for the current job.

It makes one think and ask if this or a similar experiment were conducted again today; how would the outcome change. If Haskell could displace commonly used languages nearly a decade ago, then it is necessary to consider the reasons for withholding widespread use. The ability to recognise the potential in Haskell and functional programming appears to require a change in the mind-set of the main stream programmer. This review will consider these issues and highlight the key points in the Hudak/Jones paper.

Arguments and Key Points

Haskell is obviously a mature and competent language today. This statement is based on the following facts. Firstly, in the experiment that was described by Hudak/Jones [3](p 8), all the required objectives were met by the use of the functional programming language Haskell. Second, a working prototype was created with a minimum amount of work: consisting of only 85 lines of code that allowed room for incremental enhancement. From the 85 lines of Haskell code, 29 lines were incorporated in the code in form of type synonyms and type signatures. The expressivity of Haskell is evident, when we compare the best performing programming language with the worst; 56 lines of Haskell code can be compared to 1100 lines of C++ code. The type signatures in Haskell are optional. This means that the compiler could infer type information, removing the 29 lines of type signatures reduces the code to a mere 56 lines.

Some would argue that, the order of productivity may not be 20:1 as the ratio of lines suggests; but the productivity gain is obvious. No other language in the experiment can even come close to this conciseness in code length. In general the conciseness of a Haskell solution is due to the following points:

Simple syntax and layout rule.
The ability to use higher-order functions to abstract out common control constructs.
List manipulating functions in the Prelude.hs that are developed with code reuse in mind.
Pattern matching ([] _).

If programming experts failed in an attempt to solve a real world problem and a college graduate succeeded, questions would be raised concerning the programming language. The first of these would relate to the specific language used. We learned, that Haskell is a programming language that appears to be better suited to solve a large subset of the real world problems.

Haskell's Strength In Prototypes

Prototyping in the software development life-cycle has an important role. Prototypes help to clarify the problem, user requirements and reduce costly design errors at an early stage in the development. In Haskell the prototyping is helped by the literate Haskell approach, where one can imagine a file called requirements.lhs. A programmer can literally turn the document into the end product by adding code in the file to confirm the specifications. Code and documentation can be one in Haskell, Hudak/Jones calls this the ``executable specification'' and an ``executable L^ATEX2_e document'' [3]. Barendregt also pointed out that ``Lambda calculi are prototype programming languages'' [2].

There is more evidence that Haskell is a good prototyping language. Bagley [1] compared 30 programming languages: in his experiment, Haskell consistently beaten other languages in code brevity. In a large project, complexity grows exponentially and good modularity is an important issue. As Hugh [4] pointed out conventional languages place limits on the way problems can be modularised. Haskell seems to provide the right sort of `glue', in the form of higher-order functions and laziness that supports modularity. People and organisations are reluctant to change programming languages [7]. However, once Haskell's strengths as a prototyping language are realised, it is only a short step from there to gain widespread acceptance as a replacement for common imperative languages.

Haskell's higher-order, polymorphic type system offers benefits for the programmer. Typing provides information to both, the programmer and the compiler. Type errors are one of the most difficult to find errors. The static type system in Haskell provides several benefits:

Reduces errors.
Compile time error check provides early detection of errors.
Provides a binary relationship between syntax and semantics.
Types act as documentation for programmers and at the same time used by the compiler for efficiency.
Promotes creation of more secure programs.

The clear, concise, expressive Haskell code indicates the ability of the language to scale better and higher on more complex projects than conventional languages. Scalability is not just a technical issue. The average person has the ability to concentrate on at most seven things at any given time. It is obviously easier and faster to read and understand 85 lines of Haskell code than the 1100 lines of C++ code. Haskell's approach and `toolkit' of higher-order functions, parametric polymorphism, the usual ad-hoc polymorphism and lazy evaluation provides a powerful way of reusing code. This powerful code reuse provides significant gains in productivity compared to any imperative language today. The benefit of Haskell is the ability to handle the complexity, in a far more convenient way.

It could be argued that, if the experiment were conducted today the end result would be the same. Haskell has further matured, refined in the last few years and no ground-breaking new languages has been introduced since. Ironically, all the competing programming languages had an expert writing the attempted solution except Haskell; where a college graduate had 8 days to `catch up' with the years of experience of the experts [3] (p 4). The code to document ratio was also notably better in the Haskell version.

The functional programming community has a good understanding of what imperative programming languages are. They are aware of the advantages and disadvantages of both, the functional and imperative programming languages. However, this observation does not hold for the majority of the imperative programming community. Programming in Haskell requires a very different mind-set. It is difficult to explain a functional programming language to an imperative programmer, that has no variables, no assignments and no statements only expressions. In general, programmers get the impression that Haskell is restricted as they have no control over program execution. This is not the case. This is an issue when imperative programmers label higher-order functions as a `trick', simply because they do not understand the concept that underlies higher-order functions. It is clear that since the implementation details were left up to the participants, the other programming languages did not have the same tricks available. I have no doubt that expert programmers would be aware of those if they existed.

As Thompson expressed [8](p 3) ``A functional programmer will concentrate on the relationships between values''. This is a very different notion from Alan Kay's ``everything is an object'' approach. The paper concludes that ``sociological and psychological barriers must be overcome''. Programming in Haskell and indeed in any functional programming language requires an approach that can be best described as thinking functionally.

The table on page shows the progress of abstraction in programming in the last 50 years. The available language constructs in Haskell are unique when one compares them to languages such as C++ or Java. There is no need to worry about execution path and side effects of changing variables as we do not need to declare variables in the first place. These all add up when productivity is an obvious concern. Schach [7] points out that when 4-th generation languages were introduced, companies reported a ``10-fold increase in productivity''. Looking at the difference between the conciseness and expressivity of Haskell in the experiment suggests that the same claim could be made when one compares Haskell to current fourth generation languages (4GL) and 5GL languages.

Table 1: Level of abstraction in programming and its impact on productivity.

Generation	Year	Name	Machine code instr. / line
First	1940	binary machine code	1
Second	1950	assemblers	1
Third	1960	Fortran, Algol	5-10
Fourth	1970	C	30
Fifth	1980	Python, SQL	35-40
Sixth	1990	Haskell	80+

Mistakes and Omissions

As Hudak/Jones points out ``correctness and reliability is of obvious concern'' [3](p 4). It would have been useful, to point out in the paper that the Haskell code is also easier to prove mathematically compared to the competing conventional imperative languages. Haskell is well known to express mathematical structures and algorithms elegantly. The quick-sort algorithm is a striking example of the expressivity and conciseness of Haskell.

-- Quicksort in Haskell, using list comprehensions
-- Choose the head as the pivot, divide & conquer
qsort [] = []
qsort (pivot:t) = qsort[ y | y <- t, y <  pivot] 
    ++ [pivot] ++ qsort[ y | y <- t, y >= pivot]

Verifying a functional program is far easier, because of their mathematical, recursive (inductive) nature. Furthermore, Haskell encourages a modular programming style, which is considered a positive approach in both, programming and proofs. The Haskell definition of quick-sort is the most elegant, clear and concise implementation there is. While the list comprehension construct is a syntactic sugar, it is here where its benefit is clearly shown. List comprehension provides a powerful way to express complex constructs with minimum coding. Haskell's clean semantics makes for much easier proofs of program correctness.

Since the geo-server is just one part of a much larger system, implementing the whole system would be a more complex issue than just implementing the geo-server. If the whole system is implemented in Haskell, the overall system maintenance, code readability and understandability is improved due to the Haskell syntax. Further modifications to the whole system can be implemented in a fraction of the time than it requires in, say, C++. According to Jarvis [5](p 35) ``One of the benefits of functional languages is the ease with which programs can be analysed.'' Another testament of the flexibility of the Haskell language is that Haskell can represent the region several different ways. They simply chose not to, as the use of higher-order functions provided them with a more powerful concept to solve this particular problem. [3](p13)

type Region = Point -> Bool

Lazy evaluation is another way how Haskell can work on infinite lists, trees and bring a new powerful aspect to programming that is not available in imperative languages. Lazy evaluation has many benefits. While it is not obvious, Hughes [4] pointed out that laziness supports modularity. Haskell only evaluates an expression once, it has no side-effects like imperative languages do. The underlying implementation uses graphs [8](pp. 339-340) in the evaluation of expressions. There is research currently in progress that experiments with functional languages in a semi-lazy evaluation environment. The theoretical benefits would include the current benefits of lazy evaluation and improved performance over lazy evaluation.

When one speaks of modularity the ability of the language to allow the creation of modular structures is not enough by itself. The language also must support the ability to easily combine these parts. Haskell stands out when this point is examined with its exceedingly good modularity support. One could argue that Haskell redefined the concept of reusability with flawless elegance. Personally, functional programming in Haskell certainly was an eye opener for me after several years of object-oriented programming.

Other languages follow the pattern of the convenient Haskell layout. Python is one example where a similar layout rule used. This is an indication that the imperative programming community is taking functional languages seriously and is ready to adapt good ideas. The adaption of the positive ideas from functional programming will eventually lead to widespread acceptance of Haskell. I would have liked to have seen how the authors think about changing the mind-set of the imperative world to harness the power of Haskell.

Conclusion

Haskell's strength has been shown in a real world problem with impressive results, but these very same strengths are still poorly understood by conventional programmers. Haskell's success can be attributed to the following reasons: functions are first class citizens, higher-order functions, a rich recursive polymorphic structure and lazy evaluation. Haskell provides very high productivity in return for time invested in learning the language. This productivity is a direct consequence of the language's ability to support non-conventional concepts such as higher-order functions, laziness and parametric polymorphism.

Haskell is an excellent language for prototyping due to its powerful language features, modular structure, code reusability and concise syntax.
The resulting prototype is easy to understand, therefore the prototype is easy to modify, extend or maintain.
Higher-order functions and laziness provide a modular code base.
Imperative mind-set and psychological barriers must be overcome.

Bibliography

1: BAGLEY, D.
The great computer language shootout.
http://www.bagley.org/ $\sim$ doug/shootout/, August 2001.
A benchmark comparison of a number of programming languages.
2: BARENDREGT, H.
The impact of the lambda calculus in logic and computer science.
Tech. rep., Association for Symbolic Logic, June 1997.
3: HUDAK, P., AND JONES, M. P.
Haskell vs. ada vs. c++ vs. awk vs. ... an experiment in software prototyping productivity.
Tech. rep., Yale University, Department of Computer Science, New Haven, CT 06518, July 1994.
4: HUGHES, J.
Why functional programming matters.
Tech. rep., Institutionen för Datavetenskap, Chalmers Tekniska Högskola, 41296 Göteborg, Sweden, 1984.
5: JARVIS, S.
Functional programming.
Oxford University Computing Laboratory, 2000.
6: LESLIE, N.
Functional programming.
Centre for Logic, Language and Computation, School of Mathematical and Computing Sciences, Victoria University of Wellington, New Zealand, March 2002.
7: SCHACH, S. R.
Classical and Object-Oriented Software Engineering, fourth ed.
Computer Science Series. McGraw-Hill, 1999.
ISBN 0-071-16761-7.
8: THOMPSON, S.
The Craft of Functional Programming, first ed.
International Computer Science. Addison-Wesley, 1999.
ISBN 0-201-34275-8.

About this document ...

Haskell's Role In Prototypes
Review of a Paper from Hudak and Jones

Review 1 - Assignment One - Comp 432

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.43)

The command line arguments were:
latex2html -antialias_text -scalable_fonts -split 1 review1.tex

The translation was initiated by frank on 2002-05-21

frank 2002-05-21

Haskell's Role In Prototypes Review of a Paper from Hudak and Jones Review 1 - Assignment One - Comp 432

Abstract:

Haskell's Role In Prototypes
Review of a Paper from Hudak and Jones

Review 1 - Assignment One - Comp 432