next up previous contents
Next: Haskell: Up: Implementation Previous: Implementation


  It was decided to implement the calculator using a functional programming language, although it would been equally possible to implement it using an imperative one. Functional and imperative programming languages each have their merits and disadvantages. As a general rule one would expect an imperative implementation to be faster and more memory efficient, but a functional one would probably be simpler to program, modify, and experiment with. It is also likely that a functional implementation would have less source code and be less likely to contain bugs.

Imperative languages usually give the programmer almost direct control over the machine's representation of data and low level control over the instructions executed. As such it is possible to choose highly efficient representations and optimise the code which is executed frequently for performance. On the other hand the programmer is exposed to such issues and changing early decisions later on in the development can be complicated and leave the program unstable if not performed with extreme care.

Functional programming languages typically offer a higher level of abstraction, so the programmer is one step further removed from the actual representations and execution. As a result a functional language compiler or interpreter will often need to add its own memory and processing overheads which affect performance. In return for this, however, the programmer does not need to worry about issues like memory management, garbage collection, data structures, execution order, and numerous other such tasks which make the code simpler, easier to develop, and less prone to bugs.

The implementation of this calculator is meant as a tool to help develop, experiment with, and demonstrate the representations and algorithms we have described. Using a functional programming language makes these tasks simpler, and as performance is not a priority it was decided that this would be preferable to implement using an imperative one.

Had we chosen to implement the calculator using an imperative programming language, one data structure which it would have been necessary to implement would have been the stream. This would be a complex task, particularly if we required efficient memory management and high performance. A functional language which incorporates lazy lists already addresses these problems, thus sparing us this effort. In addition, a good compiler for a functional programming language will probably use sophisticated techniques to manage these data structures and would probably perform better than an attempt programmed from scratch in an imperative language without some fair degree of thought.

The choice of a functional language was justified during the course of the implementation and analysis, as some quite fundamental changes were made to the implementation which were facilitated by this choice. For example, in chapter 7.2 were refer to an implementation of the algorithms which keeps track of the lookahead in the input streams required. Using Haskell, it was possible to re-implement the stream representations such each digit also held lookahead information and operations on digits tracked the maximum lookahead, and then use these streams in the algorithms already implemented, without significant change to the existing code. Although it would have been possible to make the same changes in an imperative language, they would have required either significant modification of the code, or a quite remarkable degree of foresight in the early stages design and coding to make the code sufficiently modular and flexible that the changes could have been made easily.

Hughes [16] gives an interesting discussion of these and other benefits of functional programming.

next up previous contents
Next: Haskell: Up: Implementation Previous: Implementation
Martin Escardo