0.1.1 July 2018

I dedicate this textbook to my parents—my mother, Mary Cunningham, and my father, the late Harold “Sonny” Cunningham—and to my wife, Diana Cunningham.

I thank Mother and Dad for their love and encouragement throughout my nearly 64 years on this earth. They taught me the importance of hard work, both physical and mental. They taught me the importance of faith in God and of personal integrity. I hope I have been a good student.

I write this sitting at a desk in my mother’s home late one evening in July 2018. I remember a time more than a half century ago when I was struggling with an elementary school writing assignment. Mother wrote an example page that I remember as amazing. I thank her for that encouragement. I still suffer from a deficit of creativity at times, but I was able to write this approximately 400-page textbook.

I look around and see a plaque for an award my father received for serving his church as a Sunday School teacher for 40 years. It reminds me of the many positive contributions he made to his community and his church, many unseen by others. I hope I am also making positive contributions to the various communities, physical and virtual, in which I live and work.

I thank Diana, my wife of 42 years, for her love and friendship—for being my companion on the journey of life. This textbook is an effort that has spanned more than a quarter century. She has lived it nearly as much as I have. Many times she has urged me to stop work and get some sleep, as she did just now.

0.1.2 November 2019 Addendum

My mother passed away in June 2019 at the age of 91 years and 8 months. We miss her dearly! Her family and friends will remember for as long as we live.

We love you, Mom, and look forward to the reunion of our family in heaven.

0.7.1 Notes on Functional Programming with Haskell

I created the course CSci 555, Functional Programming, at the University of Mississippi and first taught it during the Spring 1991 semester.

I adopted the first edition of Bird and Wadler [15] as the initial textbook for the course. I thank Richard Bird and Philip Wadler for writing this excellent textbook. I thank Jeremy Gibbons for suggesting that book in a response to an inquiry I posted to a Usenet newsgroup in Summer 1990.

I also used Wentworth’s RUFL (Rhodes University Functional Language) interpreter and his tutorial [178] in the first two offerings of the course. I thank Peter Wentworth for sending me (unsolicited, in response to my Usenet post) his interpreter and tutorial on a floppy disk through snail mail from the then-sanctioned South Africa.

My approach was also shaped by my research on formal methods and my previous teaching on that topic. I created the course Program Semantics and Derivation (CSci 550) and first taught it in Spring 1990 [40,41]. I followed that with the course Theory of Concurrent Programming (Engr 664), which I first taught in Fall 1990. I thank my dissertation advisor Gruia-Catalin Roman for developing my interests in formal methods, Jan Tijmen Udding for teaching a graduate course on program derivation that piqued my interests, and the other researchers or authors who have influenced my thinking: Edsger Dijkstra, Tony Hoare, David Gries, Mani Chandy, Jayadev Misra, Edward Cohen, and many others.

For the third offering of CSci 555 in Fall 1993, I switched the course to use the Gofer interpreter for the Haskell language. I thank the international committee of researchers, including Simon Peyton Jones, Paul Hudak, Philip Wadler, and others, who have developed and sustained Haskell since the late 1980s. I also thank Mark Jones for developing the lightweight Gofer interpreter and making it and its successor HUGS widely available.

Because of the need for a tutorial like Wentworth’s and an unexpected delay in getting copies of the Bird and Wadler textbook [15] from Prentice Hall that semester, I began writing, on an emergency basis, what evolved into my Notes on Functional Programming with Haskell [42].

Some parts of the Notes were based on my handwritten class notes from the the 1991 and 1992 offerings of the course. Many pages of the Notes were written “just-in-time” in late-night sessions before I taught them the next day. I thank Prentice Hall (now Pearson) for its delay in shipping books across the “big pond”, my wife Diana Cunningham for tolerating my disruptive schedule, and my Fall 1993 students for not complaining too vigorously about a quite raw set of class notes.

I continued to develop the Notes for the Fall 1994 and Fall 1995 offerings of the course. In early 1996, I created a relatively stable version of the Notes that I continued to use in subsequent offerings of CSci 555. I thank my students and others who pointed out typos and suggested improvements during the 1993-1996 period.

I thank David Gries for encouraging me to expand these notes into a textbook. I am doing that, albeit over 20 years later than Gries intended.

I formatted the Notes using LaTeX augmented by BibTeX for the bibliography and makeIndex for the index. I thank Donald Knuth, Leslie Lamport, and the many others who have developed and maintained TeX, LaTeX, and the other tools and packages over four decades. They form an excellent system for creating beautiful scientific documents.

I used GNU Emacs for writing and editing the source files for the Notes. I thank Richard Stallman and the many others who developed, maintained, and popularized Emacs over more than four decades.

For the Spring 1997 offering of CSci 555, I started using the new HUGS interpreter and the 1st edition of Thompson’s textbook [171] (now it its 3rd edition [173]). I thank Simon Thompson for writing his excellent, comprehensive introductory textbook on Haskell programming.

Over the next 17 years, I corrected a few errors but otherwise the Notes were stable. However, I did create supplementary notes for CSci 555 and related courses. These drew on the works of Abelson and Sussman [1], Thompson [171–173], Parnas [20,134], and others. I formated these notes with HTML, Microsoft Word and Powerpoint, or plain text.

I decided to use Haskell as one of the languages in the Fall 2014 offering of Organization of Programming Languages (CSci 450). But I needed to change the language usage from the Haskell 98 standard and HUGS to the new Haskell 2010 standard and the Glasgow Haskell Compiler (GHC) and its interactive user interface GHCi. I edited the Notes through chapter 10 on Problem Solving to reflect the changes in Haskell 2010.

0.7.2 Organization of Programming Languages

ACM Curriculum ’78 [5] influenced how most computer science academic programs were structured when they are established in the 1970s and 1980s. It defined eight core courses, most of which are still prominent in contemporary computer science curricula.

Organization of Programming Languages (CS 8) is one of those core courses. Curriculum ’78 describes CS 8 as “an applied course in programming language constructs emphasizing the run-time behavior of programs” and providing “appropriate background for advanced level courses involving formal and theoretical aspects of programming languages and/or the compilation process” [5].

I first taught the required Organization of Programming Languages (CSci 450) course at the University of Mississippi in Fall 1995. I took over that class for another instructor and used the textbook the Department Chair had already selected. The textbook was the 2nd Edition of Sebesta’s book [157].

Although the Sebesta book, now in its 11th edition, is probably one of the better and more popular books for CS 8-type courses, I found it difficult for me to use that semester. It and its primary competitors seem to be large, expensive tomes that try to be all things to all instructors and students. I personally find the kind of survey course these books support to be a disjointed hodgepodge. There is much more material than I can cover well in one semester. I abandoned the Sebesta book mid-way through the semester and have never wanted to use it again.

I had a copy of Kamin’s textbook [108] and used two of its interpreters after abandoning Sebesta’s book. It seemed to work better than Sebesta. So I ended the semester with a positive view of the Kamin approach.

My only involvement with CSci 450 for the next 18 years was to schedule and staff the course (as Department Chair 2001-15). In 2013, I began planning to teach CSci 450 again.

I decided to try an experiment. I planned to use the Kamin approach for part of the course but to redevelop the interpreters in the Lua language. Lua is a minimalist, dynamically typed language that can support multiple paradigms.

I chose Lua because (a) learning it would be a new experience for almost all of my students, (b) as a small language it should be easy for students to learn, (c) its flexibility would enable me to explore how to extend the language itself to provide new features, (d) its associated LPEG library supported the development of simple parsers, and (e) its use in computer games might make it interesting to students. I thank the Lua authors—Roberto Ierusalimschy, Waldemar Celes, and Luiz Henrique de Figueiredo—for developing this interesting platform and making it available. I thank Ierusalimschy for developing LPEG and for writing an excellent textbook on Lua programming [105].

I used the Fall 2013 offering of my Software Language Engineering (CSci 658) course to explore Lua programming and interpreters. I thank the students in that class for their feedback and suggestions—Michael Macias, Blake Adams, Cornelius Hughes, Zhendong Zhao, Joey Carlisle, and others.

However, in Summer 2014, I did not believe I was ready to undertake the interpreter-based approach in the large Fall 2014 class. Instead, I planned to try a multiple paradigm survey. I planned to begin with Haskell statically typed functional programming (using my Notes), then cover Lua dynamically typed, multiparadigm programming, and then use the logic language Prolog. I had taught Haskell, Lua, and Prolog in elective courses in the past.

I was comfortable with the Haskell part, but I found a required course a more challenging environment in which to teach Haskell than an elective. Covering Haskell took nearly two-thirds of the semester, leaving Lua in one-third, and squeezing out coverage of the logic language and most of the interpreter material.

I was scheduled to teach CSci 450 again in Fall 2016. For this offering, I decided to (a) begin with Lua and then follow with Haskell (the reverse order from 2014) and (b) to use the interpreter approach in the Lua segment. I adopted the 4th edition of Scott’s textbook [156] to support the general material (but did not use the book much).

Unfortunately, that offering suffered from immature teaching materials for both Lua and for the interpreter approach. I was unable to invest sufficient time in Summer 2016 to prepare course materials and revise the interpreters. Also, students, who mostly had experience with Java, had considerable difficulty modifying and debugging the dynamically typed Lua programs with 1000+ lines of code. (For various reasons, I decided to use the new Elm language instead of Haskell in the last three weeks of the semester.)

I thank the students in the Fall 2014 and Fall 2016 CSci 450 classes for giving me valuable feedback on what works and what does not—much more on the latter than the former. I also thank my Teaching Assistant (TA) for CSci 450 in the Fall 20a6 semester, Ajay Sharma, for his assistance. I learned that a large, required course like CSci 450 needs more mature teaching materials and tools than a small, elective course does. It should have been obvious!

0.7.3 Exploring Languages with Interpreters and Functional Programming

In Summer 2016, I participated in the eLearning Training Course (eTC) at the University of Mississippi to become eligible to teach online. As a part of that course, I was expected to prepare a syllabus and at least one module for some class. I chose to focus on CSci 555, Functional Programming.

This stimulated me to begin reorganizing my previous Notes on Functional Programming with Haskell to be a textbook for an online course on functional programming. I thank the eTC instructors Patty O’Sullivan and Wan Latartara, for (unintentionally) pushing me to begin developing this textbook.

For the textbook, I expanded the Notes by adapting materials I had originally developed for other purposes—such as papers with former graduate students Pallavi (Tadepalli) Darbhamulla, Yi Liu, and Cuihua Zhang—and some notes from my courses on functional programming, multiparadigm programming, software architecture, and software language engineering. I thank Darbhamulla, Liu, and Zhang. I also thank former graduate student James Church (author of a Haskell-based book [32]) for his feedback and encouragement to repackage my class notes as a textbook.

Unfortunately, I devoted too much time to this project in Summer 2016 and not enough to developing Lua-based materials and tools for the Fall 2016 offering of CSci 450, as I discussed above.

The eTC also sensitized me to the need to produce accessible instructional materials (e.g., materials compatible with screen readers for the visually impaired). I decided to expand my use of Pandoc-flavored Markdown and the Pandoc tools for producing materials in a variety of accessible formats (HTML, possibly LaTeX/PDF).

In Summer 2016, I had materials in a variety of formats. The Notes on Functional Programming with Haskell used LaTeX, BibTeX, and makeIndex. This is a great format for producing printed scientific documents, but not as good for display on the Web. Some of my other materials used HTML, which is great for the Web, but not for printed documents. I also had some material in Microsoft Office formats, Pandoc-flavored Markdown, and plain text (e.g., program comments).

Pandoc-flavored Markdown offered a means for achieving both greater flexibility and greater accessibility. Of course, sometimes I have to compromise on the appearance in some formats.

The Pandoc tool uses a language-processing approach, is implemented in Haskell, and supports Lua as its builtin scripting language. So it is a good fit for this textbook project. I thank John MacFarlane and many others who have developed and maintained the excellent Pandoc tools.

In Spring and Summer 2017, I combined the efforts from the previous years and sought to expand the Haskell-based functional programming course materials to include materials for the interpreter-based approach to the programming languages course and new Haskell-related material on type classes.

I redirected the work from developing materials for an online course to developing a textbook for the types of courses I describe in the “Course 1 and Course 2” section above.

In Fall 2017, I taught CSci 450 from the 2017 version of the textbook. Given my more mature materials, it worked better than the Lua-based course the previous year. But that effort identified the need for additional work on the textbook: shorter, more focused chapters, some explicit discussion of software testing, more attention to the language-processing issues, etc.

I thank my Fall 2017 and Fall 2018 TA for CSci 450, Kyle Moore, for his suggestions and corrections in a number of areas. I also thank the Spring 2017 Multiparadigm Programming (CSci 556) and Fall 2017 CSci 450 students for their feedback on the textbook materials.

I thank my long-time colleague, and current Department Chair, Dawn Wilkins, for her general suggestions on the CSci 450 course and the textbook and for the Department’s continued support of my textbook writing efforts.

I also thank Armando Suarez, my Spring 2018 TA for Senior Project and student in Software Language Engineering that semester, for his suggestions on my materials and approach to those courses—some of which I have applied to this textbook and its associated courses.

In 2018, I began restructuring the 2017 version of the textbook to better meet the needs of the CSci 450 course. I changed the title to Exploring Languages with Interpreters and Functional Programming.

I incorporated additional chapters from the Notes on Functional Programming with Haskell and other materials that had not been previously included. I also developed new chapters on software testing, the language processing pipeline, and the Imperative Core language interpreter. I plan to develop additional interpreters, such as one for a Scheme-like language.

Because of this project, I have come to appreciate how much time, effort, and attention to detail must be invested to develop a good programming language organization textbook. I think Samuel Kamin, Robert Sebesta, Michael Scott, Norman Ramsey, Shriram Krishnamurthi, and other authors for their investment in writing and updating their books.

I retired from the full-time faculty in May 2019. As one of my post-retirement projects, I plan to continue work on this textbook. However, the work went slowly until 2022 because of the COVID-19 pandemic disruptions, my continued work with two PhD students until mid-2021, and various personal factors. In January 2022, I began refining the existing content, integrating separately developed materials, reformatting the document (e.g., using CSS), constructing a bibliography (e.g., using citeproc), and improving the build workflow and use of Pandoc features.

As I have noted above, I maintain this preface as text in Pandoc’s dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed. I continue to learn how better to apply the Pandoc-related tools to accomplish this.

2.2.1 What is abstraction?

As computing scientists and computer programmers, we should remember the maxim:

Simplicity is good; complexity is bad.

The most effective weapon that we have in the fight against complexity is abstraction. What is abstraction?

Abstraction is concentrating on the essentials and ignoring the details.

Sometimes abstraction is described as remembering the “what” and ignoring the “how”.

Large complex problems can only be made understandable by decomposing them into subproblems. Ideally, we should be able to solve each subproblem independently and then compose their solutions into a solution to the larger problem.

In programming, the subproblem solution is often expressed with some kind of abstraction represented in a programming notation. From the outside, each abstraction should be simple and easy for programmers to use correctly. The programmers should only need to know the abstraction’s interface (i.e., some small number of assumptions necessary to use the abstraction correctly).`

2.2.2 Kinds of abstraction

Two kinds of abstraction are of interest to computing scientists: procedural abstraction and data abstraction.

Procedural abstraction:

the separation of the logical properties of an action from the details of how the action is implemented.

Data abstraction:

the separation of the logical properties of data from the details of how the data are represented.

In procedural abstraction, programmers focus primarily on the actions to be carried out and secondarily on the data to be processed.

For example, in the top-down design of a sequential algorithm, a programmer first identifies a sequence of actions to solve the problem without being overly concerned about how each action will be carried out.

If an action is simple, the programmer can code it directly using a sequence of programming language statements.

If an action is complex, the programmer can abstract the action into a subprogram (e.g., a procedure or function) in the programming language. The programmer must define the subprogram’s name, parameters, return value, effects, and assumptions—that is, define its interface. The programmer subsequently develops the subprogram using the same top-down design approach.

In data abstraction, programmers primarily focus on the problem’s data and secondarily on its actions. Programmers first identify the key data representations and develop the programs around those and the operations needed to create and update them.

We address procedural and data abstraction further in Chapters 6 and 7.

2.2.3 Procedures and functions

Generally we make the following distinctions among subprograms:

• A procedure is (in its pure form) a subprogram that takes zero or more arguments but does not return a value. It is executed for its effects, such as changing values in a data structure within the program, modifying its reference or value-result arguments, or causing some effect outside the program (e.g., displaying text on the screen or reading from a file).

• A function is (in its pure form) a subprogram that takes zero or more arguments and returns a value but that does not have other effects.

• A method is a procedure or function often associated with an object or class in an object-oriented program. Some object-oriented languages use the metaphor of message-passing. A method is the feature of an object that receives a message. In an implementation, a method is typically a procedure or function associated with the (receiver) object; the object may be an implicit parameter of the method.

Of course, the features of various programming languages and usual practices for their use may not follow the above pure distinctions. For example, a language may not distinguish between procedures and functions. One term or another may be used for all subprograms. Procedures may return values. Functions may have side effects. Functions may return multiple values. The same subprogram can sometimes be called either as a function or procedure.

Nevertheless, it is good practice to maintain the distinction between functions and procedures for most cases in software design and programming.

2.4.1 Java

Consider the following Java program fragment from file Counting.java:

    int count =  0 ;
    int maxc  = 10 ;
    while (count <= maxc) {
        System.out.println(count) ;
        count = count + 1 ;
    }

In this fragment, the program’s state includes at least the values of the variables count and maxc, the sequence of output lines that have been printed, and an indicator of which statement to execute next (i.e., location or program counter).

The assignment statement changes the value of count and the println statement adds a new line to the output sequence. These are side effects of the execution.

Similarly, Java executes these commands in sequence, causing a change in which statement will be executed next. The purpose of the while statement is to cause the statements between the braces to be executed zero or more times. The number of times depends upon the values of count and maxc and how the values change within the while loop.

We call this state implicit because the aspects of the state used by a particular statement are not explicitly specified; the state is assumed from the context of the statement. Sometimes a statement can modify aspects of the state that are not evident from examining the code fragment itself.

The Java variable count is mutable because its value can change. After the declaration, count has the value 0. At the end of the first iteration of the while loop, it has value 1. After the while loop exits, it has a value 10. So a reference to count yields different values depending upon the state of the program at that point.

The Java variable maxc is also mutable, but this code fragment does not change its value. So maxc could be replaced by an immutable value.

Of course, the Java fragment above must be included within a main method to be executed. A main method is the entry point of a Java program.

    public class Counting {
        public static void main(String[] args) {
            /* Java code fragment above */
        }
     }

Imperative languages are the “conventional” or “von Neumann languages” discussed by John Backus in his 1977 Turing Award address [6]. (See Section 2.7.) They are suited to traditional computer architectures.

Most of the languages in existence today are primarily imperative in nature. These include Fortran, C, C++, Java, Scala, C#, Python, Lua, and JavaScript.

2.4.2 Other languages

The Scala [132,151] program CountingImp.scala is equivalent to the Java program described above. The program CountingImp2.scala is also equivalent, except that it makes the maxc variable immutable. That is, it can be bound to an initial value, but its binding cannot be changed subsequently.

2.5.1 Functional paradigm

In the functional paradigm the underlying model of computation is the mathematical concept of a function [101].

In a computation, a function is applied to zero or more arguments to compute a single result; that is, the result is deterministic (or predictable).

    counter :: Int -> Int -> String 
    counter count maxc 
        | count <= maxc = show count ++ "\n" 
                          ++ counter (count+1) maxc 
        | otherwise     = ""

    main = do 
        putStrLn (counter 0 10) 

2.5.2 Relational (or logic) paradigm

In the relational (logic) paradigm, the underlying model of computation is the mathematical concept of a relation (or a predicate) [101].

A computation is the (nondeterministic) association of a group of values—with backtracking to resolve additional values.

    counter(X,Y,S) :- count(X,Y,R), atomics_to_string(R,'\n',S).

    count(X,X,[X]). 
    count(X,Y,[])     :- X  > Y. 
    count(X,Y,[X|Rs]) :- X < Y, NX is X+1, count(NX,Y,Rs).

    count(X,X,[X]).

    count(X,Y,[]) :- X > Y.

    count(X,Y,[])

    count(1,1,Z).

    count(X,1,[1]).

    main :- counter(0,10,S), write(S).

2.6.1 Procedural paradigm

The procedural paradigm is a subcategory of the imperative paradigm. It organizes programs primarily using procedural abstractions. A procedural program consists of a sequence of steps that access and modify the program’s state.

Some of the steps are abstracted out as subprograms—procedures or functions—that can be reused. In some cases, subprograms may be nested inside other subprograms, thus limiting the part of the program in which the nested subprogram can be called.

The procedural programming approach arose in programming languages such as Fortran, Algol, PL/I, Pascal, and C from the 1950’s to the 1970’s and beyond. In this chapter, we use the Python programming language to illustrate of its features.

    # File CountingProc.py
    def counter(count,maxc):
        def has_more(count,maxc): # new variables
            return count <= maxc 
        def adv():
            nonlocal count     # from counter
            count = count + 1
        while has_more(count,maxc):
            print(f'{count}')  # Python 3.6+ string interpolation
            adv()

    counter(0,10)

2.6.2 Modular paradigm

Modular programming refers more to a design method for programs and program libraries than to languages.

Modular programming means to decompose a program into units of functionality (i.e., modules) that can be developed separately and then recomposed. These modules can hide (i.e., encapsulate) key design and implementation details within the modu

The module’s public features can be accessed through its interface; its private features cannot be accessed from outside the module. Thus a module supports the principle of information hiding. This method also keeps the interactions among modules at a minimum, maintaining a low degree of coupling.

We discuss modular programming in more depth in Chapters 6 and 7.

A language that provides constructs for defining modules, packages, namespaces, or separate compilation units can assist in writing modular programs.

In this chapter, we examine some aspects of the modular paradigm using the imperative language Python. We examine modular programming in the purely functional programming language Haskell on Chapters 6 and 7 and later chapters.

    # File CountingMod.py
    count =  0
    maxc  = 10

    def has_more():
        return count <= maxc

    def adv():
        global count 
        count = count + 1

    def counter():
        while has_more():
            print(f'{count}')
            adv()

    from CountingMod import counter
    counter()

    import CountingMod

    CountingMod.count = 10
    CountingMod.maxc  = 20
    CountingMod.counter()

    # File CountingModA.py
    from Arith import reset, adv, get_count, has_more

    def counter():
        while has_more():
            count = get_count()
            print(f'{count}')
            adv()

    # File Arith.py 
    _start  =  0
    _stop   = 10
    _change =  1
    _count  = _start

    def reset(new_start, new_stop, new_change):
        global _start, _stop, _change, _count
        _start = new_start
        _stop  = new_stop
        _count = _start
        if new_change == 0:
            print('Error: Attempt to reset increment to 0; not reset.')
        else:
            _change = new_change

    def adv():
        global _count 
        _count = _count + _change

    def get_count():
        return _count

    def has_more():
        if _change > 0:
            return _count <= _stop
        else:
            return _count >= _stop

    # File Geom.py
    _start  =   1
    _stop   = 100
    _change =   2
    _count  = _start

    def reset(new_start, new_stop, new_change):
        global _start, _stop, _change, _count
        _start = new_start
        _stop  = new_stop
        _count = start
        if abs(new_change) <= 1:
            print('Error: Attempt to set abs(_change) <= 1; not reset.')
        else:
            _change = new_change

    def adv():
        global _count 
        _count = _count * _change

    def get_count():
        return _count

    def has_more():
        return _count <= _stop

2.6.3 Object-based paradigms

The dominant paradigm since the early 1990s has been the object-oriented paradigm. Because this paradigm is likely familiar with most readers, we examine it and related object-based paradigms in the next chapter.

2.6.4 Concurrent paradigms

TODO: Perhaps describe a paradigm like actors and give an example in Elixir [68,168].

2.7.1 Excerpts from Backus’s Turing Award Address [6]

Programming languages appear to be in trouble. Each successive language incorporates, with little cleaning up, all the features of its predecessors plus a few more. Some languages have manuals exceeding 500 pages; others cram a complex description into shorter manuals by using dense formalisms. … Each new language claims new and fashionable features, such as strong typing or structured control statements, but the plain fact is that few languages make programming sufficiently cheaper or more reliable to justify the cost of producing and learning to use them.

Since large increases in size bring only small increases in power, smaller, more elegant languages such as Pascal continue to be popular. But there is a desperate need for a powerful methodology to help us think about programs, and no conventional language even begins to meet that need. In fact, conventional languages create unnecessary confusion in the way we think about programs. … In order to understand the problems of conventional programming languages, we must first examine their intellectual parent, the von Neumann computer. What is a von Neumann computer? When von Neumann and others conceived of it … [in the 1940’s], it was an elegant, practical, and unifying idea that simplified a number of engineering and programming problems that existed then. Although the conditions that produced its architecture have changed radically, we nevertheless still identify the notion of “computer” with this … concept.

In its simplest form a von Neumann computer has three parts: a central processing unit (or CPU), a store, and a connecting tube that can transmit a single word between the CPU and the store (and send an address to the store). I propose to call this tube the von Neumann bottleneck. The task of a program is to change the contents of the store in some major way; when one considers that this task must be accomplished entirely by pumping single words back and forth through the von Neumann bottleneck, the reason for its name becomes clear.

Ironically, a large part of the traffic in the bottleneck is not useful data but merely names of data, as well as operations and data used only to compute such names. Before a word can be sent through the tube its address must be in the CPU; hence it must either be sent through the tube from the store or be generated by some CPU operation. If the address is sent form the store, then its address must either have been sent from the store or generated in the CPU, and so on. If, on the other hand, the address is generated in the CPU, it must either be generated by a fixed rule (e.g., “add 1 to the program counter”) or by an instruction that was sent through the tube, in which case its address must have been sent, and so on.

Surely there must be a less primitive way of making big changes in the store than by pushing vast numbers of words back and forth through the von Neumann bottleneck. Not only is this tube a literal bottleneck for the data traffic of a problem, but, more importantly, it is an intellectual bottleneck that has kept us tied to word-at-a-time thinking instead of encouraging us to think in terms of the larger conceptual units of the task at hand. …

Conventional programming languages are basically high level, complex versions of the von Neumann computer. Our … old belief that there is only one kind of computer is the basis our our belief that there is only one kind of programming language, the conventional—von Neumann—language. The differences between Fortran and Algol 68, although considerable, are less significant than the fact that both are based on the programming style of the von Neumann computer. Although I refer to conventional languages as “von Neumann languages” to take note of their origin and style, I do not, of course, blame the great mathematician for their complexity. In fact, some might say that I bear some responsibility for that problem.

Von Neumann programming languages use variables to imitate the computer’s storage cells; control statements elaborate its jump and test instructions; and assignment statements imitate its fetching, storing, and arithmetic. The assignment statement is the von Neumann bottleneck of programming languages and keeps us thinking in word-at-at-time terms in much the same way the computer’s bottleneck does.

Consider a typical program; at its center are a number of assignment statements containing some subscripted variables. Each assignment statement produces a one-word result. The program must cause these statements to be executed many times, while altering subscript values, in order to make the desired overall change in the store, since it must be done one word at a time. The programmer is thus concerned with the flow of words through the assignment bottleneck as he designs the nest of control statements to cause the necessary repetitions.

Moreover, the assignment statement splits programming into two worlds. The first world comprises the right sides of assignment <statements. This is an orderly world of expressions, a world that has useful algebraic properties (except that those properties are often destroyed by side effects). It is the world in which most useful computation takes place.

The second world of conventional programming languages is the world of statements. The primary statement in that world is the assignment statement itself. All the other statements in the language exist in order to make it possible to perform a computation that must be based on this primitive construct: the assignment statement.

This world of statements is a disorderly one, with few useful mathematical properties. Structured programming can be seen as a modest effort to introduce some order into this chaotic world, but it accomplishes little in attacking the fundamental problems created by the word-at-a-time von Neumann style of programming, with its primitive use of loops, subscripts, and branching flow of control.

Our fixation on von Neumann languages has continued the primacy of the von Neumann computer, and our dependency on it has made non-von Neumann languages uneconomical and has limited their development. The absence of full scale, effective programming styles founded on non-von Neumann principles has deprived designers of an intellectual foundation for new computer architectures. …

2.7.2 Aside on the disorderly world of statements

Backus states that “the world of statements is a disorderly one, with few mathematical properties”. Even in 1977 this was a bit overstated since work by Hoare on axiomatic semantics [96], by Dijkstra on the weakest precondition (wp) calculus [63], and by others had already appeared.

However, because of the referential transparency property of purely functional languages, reasoning can often be done in an equational manner within the context of the language itself. We examine this convenient approach later in this book.

In contrast, the wp-calculus and other axiomatic semantic approaches must project the problem from the world of programming language statements into the world of predicate calculus, which is much more orderly. We leave this study to courses on program derivation and programming language semantics.

Note: For this author’s take on this formal methods topic, see my materials for University of Mississippi course Program Semantics and Derivation (CSci 550) [40,41].

2.7.3 Perspective from four decades later

In his Turing Award Address, Backus went on to describe FP, his proposal for a functional programming language. He argued that languages like FP would allow programmers to break out of the von Neumann bottleneck and find new ways of thinking about programming.

FP itself did not catch on, but the widespread attention given to Backus’ address and paper stimulated new interest in functional programming to develop by researchers around the world. Modern languages like Haskell developed partly from the interest generated.

In the 21st Century, the software industry has become more interested in functional programming. Some functional programming features now appear in most mainstream programming languages (e.g., in Java 8+). This interest seems to driven primarily by two concerns:

• managing the complexity of large software systems effectively

• exploiting multicore processors conveniently and safely

The functional programming paradigm is able to address these concerns because of such properties such as referential transparency, immutable data structures, and composability of components. We look at these aspects in later chapters.

3.3.1 Objects

For languages in the object-based paradigms, we require that objects exhibit three essential characterics. Some writers consider one or two other other characteristics as essential. Here we consider these as important but non-essential characteristics of the object model.

3.3.2 Classes

A class is a template or factory for creating objects.

• A class describes a collection of related objects (i.e., instances of the class).

• Objects of the same class have common operations and a common set of possible states.

• The concept of class is closely related to the concept of type.

A class description includes definitions of:

• operations on objects of the class

• the set of possible states

As an example, again consider a simulation of a classroom. There might be a class StudentDesk from which specific instances can be created as needed.

An object-based language is class-based if the concept of class occurs as a language feature and every object has a class.

Class-based languages include Clu, C++, Java, Scala, C#, Smalltalk, Ruby, and Ada 95. Ada 83 and Modula are not class-based.

At their core, JavaScript and Lua are object-based but not class-based.

In statically typed, class-based languages such as Java, Scala, C++, and C# classes are treated as types. Instances of the same class have the same (nominal) type.

However, some dynamically typed languages may have a more general concept of type: If two objects have the same set of operations, then they have the same type regardless of how the object was created. Languages such as Smalltalk and Ruby have this characteristic—sometimes informally called duck typing. (If it walks like a duck and quacks like a duck, then it is a duck.)

See Chapter 5 for more discussion of types.

3.3.3 Inheritance

A class C inherits from class P if C’s objects form a subset of P’s objects.

• Class C’s objects must support all of the class P’s operations (but perhaps are carried out in a special way).

• Class C may support additional operations and an extended state (i.e., more information fields).

• Class C is called a subclass or a child or derived class.

• Class P is called a superclass or a parent or base class.

• Class P is sometimes called a generalization of class C; class C is a specialization of class P.

The importance of inheritance is that it encourages sharing and reuse of both design information and program code. The shared state and operations can be described and implemented in base classes and shared among the subclasses.

As an example, again consider the student desks in a simulation of a classroom. The StudentDesk class might be derived (i.e., inherit) from a class Desk, which in turn might be derived from a class Furniture. In diagrams, there is a convention to draw arrows (e.g., $\longleftarrow$) from the subclass to the superclass.

Furniture $\longleftarrow$ Desk $\longleftarrow$ StudentDesk

The simulation might also include a ComputerDesk class that also derives from Desk.

Furniture $\longleftarrow$ Desk $\longleftarrow$ ComputerDesk

We can also picture the above relationships among these classes with a class diagram as shown in Figure 3.1.

In Java and Scala, we can express the above inheritance relationships using the extends keyword as follows.

    class Furniture  // extends cosmic root class for references
    {   ...   }      // (java.lang.Object, scala.AnyRef)

    class Desk extends Furniture
    {   ...   }

    class StudentDesk extends Desk
    {   ...   }

    class ComputerDesk extends Desk
    {   ...   }

Both StudentDesk and ComputerDesk objects will need operations to simulate a move of the entity in physical space. The move operation can thus be implemented in the Desk class and shared by objects of both classes.

Invocation of operations to move either a StudentDesk or a ComputerDesk will be bound to the general move in the Desk class.

The StudentDesk class might inherit from a Chair class as well as the Desk class.

Furniture $\longleftarrow$ Chair $\longleftarrow$ StudentDesk

Some languages support multiple inheritance as shown in Figure 3.2 for StudentDesk (e.g., C++, Eiffel, Python 3). Other languages only support a single inheritance hierarchy.

Because multiple inheritance is both difficult to use correctly and to implement in a compiler, the designers of Java and Scala did not include multiple inheritance of classes as features. Java has a single inheritance hierarchy with a top-level class named Object from which all other classes derive (directly or indirectly). Scala is similar, with the corresponding top-level class named AnyRef.

    class StudentDesk extends Desk, Chair  // NOT VALID in Java
    {   ...   }

To see some of the problems in implementing multiple inheritance, consider the above example. Class StudentDesk inherits from class Furniture through two different paths. Do the data fields of the class Furniture occur once or twice? What happens if the intermediate classes Desk and Chair have conflicting definitions for a data field or operation with the same name?

The difficulties with multiple inheritance are greatly decreased if we restrict ourselves to inheritance of class interfaces (i.e., the signatures of a set of operations) rather than a supporting the inheritance of the class implementations (i.e., the instance data fields and operation implementations). Since interface inheritance can be very useful in design and programming, the Java designers introduced a separate mechanism for that type of inheritance.

The Java interface construct can be used to define an interface for classes separately from the classes themselves. A Java interface may inherit from (i.e., extend) zero or more other interface definitions.

    interface Location3D
    {   ...   }

    interface HumanHolder
    {   ...   }

    interface Seat extends Location3D, HumanHolder
    {   ...   }

A Java class may inherit from (i.e., implement) zero or more interfaces as well as inherit from (i.e., extend) exactly one other class.

    interface BookHolder
    {   ...   }

    interface BookBasket extends Location3D, BookHolder
    {   ...   }

    class StudentDesk extends Desk implements Seat, BookBasket
    {   ...   }

Figure 3.3 shows this interface-based inheritance hierarchy for the classroom simulation example. The dashed lines represent the implements relationship.

This definition requires the StudentDesk class to provide actual implementations for all the operations from the Location3D, HumanHolder, BookHolder, Seat, and BookBasket interfaces. The Location3D operations will, of course, need to be implemented in such a way that they make sense as part of both the HumanHolder and BookHolder abstractions.

The Scala trait provides a more powerful, and more complex, mechanism than Java’s original interface. In addition to signatures, a trait can define method implementations and data fields. These traits can be added to a class in a controlled, linearized manner to avoid the semantic and implementation problems associated with multiple inheritance of classes. This is called mixin inheritance.

Java 8+ generalizes interfaces to allow default implementations of methods.

Most statically typed languages treat subclasses as subtypes. That is, if C is a subclass of P, then the objects of type C are also of type P. We can substitute a C object for a P object in all cases.

However, the inheritance mechanism in languages in most class-based languages (e.g., Java) does not automatically preserve substitutability. For example, a subclass can change an operation in the subclass to do something totally different from the corresponding operation in the parent class.

3.3.4 Subtype polymorphism

The concept of polymorphism (literally “many forms”) means the ability to hide different implementations behind a common interface. Polymorphism appears in several forms in programming languages. We will discuss these more later.

Subtype polymorphism (sometimes called polymorphism by inheritance, inclusion polymorphism, or subtyping) means the association of an operation invocation (i.e., procedure or function call) with the appropriate operation implementation in an inheritance (subtype) hierarchy.

This form of polymorphism is usually carried out at run time. That implementation is called dynamic binding. Given an object (i.e., class instance) to which an operation is applied, the system will first search for an implementation of the operation associated with the object’s class. If no implementation is found in that class, the system will check the superclass, and so forth up the hierarchy until an appropriate implementation is found. Implementations of the operation may appear at several levels of the hierarchy.

The combination of dynamic binding with a well-chosen inheritance hierarchy allows the possibility of an instance of one subclass being substituted for an instance of a different subclass during execution. Of course, this can only be done when none of the extended operations of the subclass are being used.

As an example, again consider the simulation of a classroom. As in our discussion of inheritance, suppose that the StudentDesk and ComputerDesk classes are derived from the Desk class and that a general move operation is implemented as a part of the Desk class. This could be expressed in Java as follows:

    class Desk extends Furniture
    {   ...
        public void move(...)
        ...
    }

    class StudentDesk extends Desk
    {   ...
        // no move(...) operation here
        ...
    }

    class ComputerDesk extends Desk
    {   ...
        // no move(...) operation here
        ...
    }

As we noted before, invocation of operations to move either a StudentDesk or a ComputerDesk instance will be bound to the general move in the Desk class.

Extending the example, suppose that we need a special version of the move operation for ComputerDesk objects. For instance, we need to make sure that the computer is shut down and the power is disconnected before the entity is moved.

To do this, we can define this special version of the move operation and associate it with the ComputerDesk class. Now a call to move{java} a ComputerDesk a object will be bound to the special move operation, but a call to move a StudentDesk object will still be bound to the general move operation in the Desk class.

The definition of move in the ComputerDesk class is said to override the definition in the Desk class.

In Java, this can be expressed as follows:

    class Desk extends Furniture 
    {   ...
        public void move(...)
        ...
    }

    class StudentDesk extends Desk
    {   ...
        // no move(...) operation here
        ...
    }

    class ComputerDesk extends Desk
    {   ...
        public void move(...)
        ...
    }

A class-based language is object-oriented if class hierarchies can be incrementally defined by an inheritance mechanism and the language supports polymorphism by inheritance along these class hierarchies.

Object-oriented languages include C++, Java, Scala, C#, Smalltalk, and Ada 95. The language Clu is class-based, but it does not include an inheritance facility.

Other object-oriented languages include Objective C, Object Pascal, Eiffel, and Oberon 2.

3.4.1 Object-oriented Python example

TODO: This example mostly illustates class-based Python. It needs to be extended to show effective use of inheritance and subtyping. Possibly create two differnet subclasses to override the hook methods or leave them abstract and make concrete in subclass–as in Arith and Geom modules for the modular examples.

Python 3 is a dynamically typed language with support for imperative, procedural, modular, object-oriented, and (to a limited extent) functional programming styles [144]. It’s object model supports state, operations, identity, and an independent lifecycle. It provides some support for encapsulation. It has classes, single and multiple inheritance, and subtype polymorphism.

Let’s again examine the counting problem from Chapter 2 from the standpoint of object-oriented programming in Python 3. The following code defines a class named CountingOO. It defines four instance methods and two instance variables.

Note: By instance variable and instance method we mean variables and instances associated with an object, an instance of a class.

    class CountingOO:                  # (1)

        def __init__(self,c,m):        # (2,3)
            self.count = c             # (4)
            self.maxc  = m

        def has_more(self,c,m):        # (5)
            return c <= m 

        def adv(self):                 # (6)
            self.count = self.count + 1
    
        def counter(self):             # (7)
            while self.has_more(self.count,self.maxc):
                print(f'{self.count}') # (8)
                self.adv()

The following notes explain the numbered items in the above code.

1. By default, a Python 3 class inherits from the cosmic root class object. If a class inherits from some other class, then we place the parent class’s name in parenthesis after the class name, as with class Times2 below. (Python 3 supports multiple inheritance, so there can be multiple class names separated by commas.)

2. Python 3 classes do not normally have explicit constructors, but we often define an initialization method which has the special name __init__.

3. Unlike object-oriented languages such as Java, Python 3 requires that the receiver object be passed explicitly as the first parameter of instance methods. By convention, this is a parameter named self.

4. An instance of the class CountingOO has two instance variables, count and maxc. Typically, we create these dynamically by explicitly assigning a value to the name. We can access these values in expressions (e.g., self.count).

5. Method has_more() is a function that takes the receiver object and values for the current count and maximum values and returns True if and only there are additional values to generate. (Although an instance method, it does not access the instance’s state.)

6. Method adv() is a procedure that accesses and modifies the state (i.e., the instance variables), setting self.count to a new value closer to the maximum value self.maxc.

7. Method counter() is a procedure intended as the primary public interface to an instance of the class. It uses function method has_more() to determine when to stop the iteration, procedure method adv() to advance the variable count from one value to the next value, and the print function to display the value on the standard output device.

8. Expression f'{self.count}' is a Python 3.7 interpolated string.

In terms of the Template Method design pattern [83], counter is intended as a template method that encodes the primary algorithm and is not intended to be overridden. Methods has_more() and adv() are intended as hook methods that are often overriden to give different behaviors to the class.

Consider the following fragment of code.

    ctr = CountingOO(0,10)
    ctr.counter()

The first line above creates an instance of the CountingOO class, initializes its instance variables count and maxc to 0 and 10, and stores the referene in variable ctr. The call ctr.counter() thus prints the values 0 to 10, one per line, as do the programs from Chapter 2.

However, we can create a subclass that overrides the definitions of the hook methods has_more() and adv() to give quite different behavior without modifying class CountingOO.

    class Times2(CountingOO):    # inherits from CountingOO

        def has_more(self,c,m):  # overrides
            return c != 0 and abs(c) <= abs(m)

        def adv(self):           # overrides
            self.count = self.count * 2

Now consider the following code fragment.

    ctr2 = Times2(-1,10)
    ctr2.counter()

This generates the sequence of values -1, -2, -4, and -8, printed one per line.

The call to any method on an instance of class Times2 is polymorphic. The system dynamically searches up the class hierarchy from Times2 to find the appropriate function. It finds has_more() and adv() in Times2 and counter() in parent class CountingOO.

The code for this section is in source file CountingOO.py.

3.4.2 Object-oriented Scala example

The program CountingOO.scala is an object-oriented Scala [131,151] program similar to the Python version given above.

3.5.1 Prototype concepts

A prototype-based language does not have the concept of class as defined above. It just has objects. Instead of using a class to instantiate a new object, a program copies (or clones) an existing object—the prototype—and modifies the copy to have the needed attributes and operations.

Each prototype consists of a collection of slots. Each slot is filled with either a data attribute or an operation.

This cloning approach is more flexible than the class-based approach.

In a class-based language, we need to define a new class or subclass to create a variation of an existing type. For example, we may have a Student class. If we want to have students who play chess, then we would need to create a new class, say ChessPlayingStudent, to add the needed data attributes and operations.

Aside: Should Student be the parent ChessPlayingStudent? or should ChessPlayer be the parent? Or should we have fields of ChessPlayingStudent that hold Student and ChessPlayer objects?

In a class-based language, the boundaries among categories of objects specified by classes should be crisply defined. That is, an object is in a particular class or it is not. Sometimes this crispness may be unnatural.

In a prototype-based language, we simply clone a student object and add new slots for the added data and operations. This new object can be a prototype for further objects.

In a prototype-based language, the boundaries between categories of objects created by cloning may be fuzzy. One category of objects may tend to blend into others. Sometimes this fuzziness may be more natural.

Consider categories of people associated with a university. These categories may include Faculty, Staff, Student, and Alumnus. Consider a student who gets a BSCS degree, then accepts a staff position as a programmer and stays a student by starting an MS program part-time, and then later teaches a course as a graduate student. The same person who started as a student thus evolves into someone who is in several categories later. And he or she may also be a chess player.

Instead of static, class-based inheritance and polymorphism, some languages exhibit prototype-based delegation. If the appropriate operation cannot be found on the current object, the operation can be delegated to its prototype, or perhaps to some other related, object. This allows dynamic relationships along several dimensions. It also means that the “copying” or “cloning” may be partly logical rather than physical.

Prototypes and delegation are more basic mechanisms than inheritance and polymorphism. The latter can often be implemented (or perhaps “simulated”) using the former.

Self [158,175], NewtonScript [123,130], JavaScript [4,231], Lua [105,116,165], and Io [36,62,164] are prototype-based languages. (Package prototype.py can also make Python behave in a prototype-based manner.)

Let’s look at Lua as a prototype-based language.

Note: The two most widely used prototype languages are JavaScript and Lua. I choose Lua here because it is simpler and can also execute conveniently from the command line. I have also used Lua extensively in the past and have not yet used JavaScript extensively.

3.5.2 Lua as an object-based language

Lua is a dynamically typed, multiparadigm language [105,116]. The language designers stress the following design principles [117]:

• portability
• embeddability
• efficiency
• simplicity

To realize these principles, the core language implementation:

• can only use standard C and the standard C library

• must be efficient in use of memory and processor time (i.e., keep the interpreter small and fast)

• must support interoperability with C programs in both directions (i.e., can call or be called by C programs)

C is ubiquitous, likely being the first higher-level language implemented for any new machine, whether a small microcontroller or a large multiprocessor. So this implementation approach supports the portability, embeddability, and efficiency design goals.

Because of Lua’s strict adherence to the above design principles, it has become a popular language for extending other applications with user-written scripts or templates. For example, it is used for this purpose in some computer games and by Wikipedia. Also, Pandoc, the document conversion tool used in production of this textbook, enables scripts to be written in Lua. (The Pandoc program itself is written in Haskell.)

The desire for a simple but powerful language led the designers to adopt an approach that separates mechanisms from policy. As noted on the Lua website [117]:

A fundamental concept in the design of Lua is to provide meta-mechanisms for implementing features, instead of providing a host of features directly in the language. For example, although Lua is not a pure object-oriented language, it does provide meta-mechanisms for implementing classes and inheritance. Lua’s meta-mechanisms bring an economy of concepts and keep the language small, while allowing the semantics to be extended in unconventional ways.

Lua provides a small set of quite powerful primitives. For example, it includes only one data structure—the table (dictionary, map, or object in other languages)—but ensures that it is efficient and flexible for a wide range of uses.

Lua’s tables are objects as described in Section 3.3. Each object has its own:

• state (i.e., values associated with keys)
• identity independent of state
• lifecycle independent of the code that created it

In addition, a table can have its own operations by associating function closures with keys.

Note: By function closure, we mean the function’s definition plus aspects of its environment necessary (e.g., variables variables outside the function) necessary for the function to be executed.

So a key in the table represents a slot in the object. The slot can be occupied by either a data attribute’s value or the function closure associated with an operation.

Lua tables do not directly support encapsulation, but there are ways to build structures that encapsulate key data or operations.

Lua’s metatable mechanism, particularly the __index metamethod, enables an access to an undefined key to be delegated to another table (or to result in a call of a specified function).

Thus tables and metatables enable the prototype-based paradigm as illustrated in the next section.

As in Python 3, Lua requires that the receiver object be passed as an argument to object-based function and procedure calls. By convention, it is passed as the first argument, as shown below.

    obj.method(obj, other_arguments)

Lua has a bit of syntactic sugar—the : operator—to make this more convenient. The following Lua expression is equivalent to the above.

    obj:method(other_arguments) 

The Lua interpreter evaluates the expression obj to get the receiver object (i.e., table), then retrieves the function closure associated with the key named method from the receiver object, then calls the function, passing the receiver object as its first parameter. In the body of the function definition, the receiver object can be referenced by parameter name self.

We can use a similar notation to define functions to be methods associated with objects (tables).

3.5.3 Prototype-based Lua example

The Lua code below, from file CountingPB.lua, implements a Lua module similar to the Python 3 CountingOO class given in Section 3.4.1. It illustrates how to define Lua modules as well as prototypes.

    -- File CountingPB.lua 
    local CountingPB = {count = 1, maxc = 0} -- (1)

    function CountingPB:new(mixin)           -- (2)
       mixin = mixin or {}                   -- (5)
       local obj = { __index = self }        -- (4)
       for k, v in pairs(mixin) do           -- (5)
          if k ~= "__index" then
             obj[k] = v
          end
       end
       return setmetatable(obj,obj)          -- (6,7)
    end

    function CountingPB:has_more(c,m)        -- (2)
       return c <= m
    end

    function CountingPB:adv()                -- (2)
       self.count = self.count + 1
    end

    function CountingPB:counter()            -- (2)
       while self:has_more(self.count,self.maxc) do
          print(self.count)
          self:adv()
        end
    end
    
    return CountingPB                        -- (3)

The following notes explain the numbered steps in the above code.

1. Create module object CountingPB as a Lua table with default values for data attributes count and maxc. This object is also the top-level prototype object.

2. Define methods (i.e., functions) new(), has_more(), adv(), and counter() and add them to the CountingPB table. The key is the function’s name and the value is the function’s closure.

   Method new() is the constructor for clones.

3. Return CountingPB when the module file CountingPB.lua is imported with a require call in another Lua module or script file.

Method new is what constructs the clones. This method:

4. Creates the clone initially as a table with only the __index set to the object that called new (i.e., the receiver object self).

5. Copies the method new’s parameter mixin’s table entries into the clone. This enables existing data and method attributes of the receiver object self to be redefined and new data and method attributes to be added to the clone.

   If parameter mixin is undefined or an empty table, then no changes are made to the clone.

6. Sets the clone’s metatable to be the clone’s table itself. In step 4, we had set its metamethod __index to be the receiver object self.

7. Returns the clone object (a table) as is the convention for Lua modules.

If a Lua program accesses an undefined key of a table (or object), then the interpreter checks to see whether the table has a metatable defined.

• If no metatable is set, then the result of the access is a nil (meaning undefined).

• If a metatable is set, then the interpreter uses the __index metamethod to determine what to do. If __index is a table, then the access is delegated to that table. If __index is set a function closure, then the interpreter calls that function. If there is no __index, then it returns a nil.

We can load the CountingPB.lua module as follows:

    local CountingPB = require "CountingPB"

Now consider the Lua assignment below:

    x = CountingPB:new({count = 0, maxc = 10})

This creates a clone of object CountingPB and stores it in variable x. This clone has its own data attributes count and maxc, but it delegates method calls back to object CountingPB.

If we execute the call x:counter(), we get the following output:

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

Now consider the Lua assignment:

    y = x:new({count = 10, maxc = 15})

This creates a clone of object in x and stores the clone in variable y. The y object has different values for count and maxc, but it delegates the method calls to x, which, in turn, delegates them on to CountingPB.

If we execute the call y:counter(), we get the following output:

    10
    11
    12
    13
    14
    15

Now, consider the following Lua assignment:

    z = y:new( { maxc = 400,
                 has_more = function (self,c,m)
                    return c ~= 0 and math.abs(c) <= math.abs(m)
                 end,
                 adv = function(self)
                    self.count = self.count * 2
                 end,
                 bye = function(self) print(self.msg) end 
                 msg = "Good-Bye!" } )

This creates a clone of object y that keeps x’s current value of count (which is 16 after executing y:counter()), sets a new value of maxc, overrides the definitions of methods has_more() and adv(), and defines new method bye() and new data attribute msg.

If we execute the call z:counter() followed by z:bye(), we get the following output:

    16
    32
    64
    128
    256
    Good-Bye!

The Lua source code for this example is in file CountingPB.lua. The example calls are in file CountingPB_Test.lua.

3.5.4 Observations

How does the prototype-based (PB) paradigm compare with the object-oriented (OO) paradigm?

• The OO paradigm as implemented in a language usually enforces a particular discipline or policy and provides syntactic and semantic support for that policy. However, it makes programming outside the policy difficult.

• The PB paradigm is more flexible. It provides lower-level mechanisms and little or no direct support for a particular discipline or policy. It allows programmers to define their own policies, simple or complex policies depending on the needs. These policies can be implemented in libraries and reused. However, PB can result in different programmers or different software development shops using incompatible approaches.

Whatever paradigm we use (OO, PB, procedural, functional, etc.), we should be careful and be consistent in how we design and implement programs.

4.2.1 Factorial function specification

We can give two mathematical definitions of factorial, fact and fact’, that are equivalent for all natural number arguments. We can define fact using the product operator as follows:

fact$(n) = \prod_{i=1}^{i=n}\,i$

For example,

fact$(4) = 1 \times 2 \times 3 \times 4$.

By definition

fact$(0) = 1$

which is the identity element of the multiplication operation.

We can also define the factorial function fact’ with a recursive definition (or recurrence relation) as follows:

fact’$(n) = 1$, if $n = 0$
fact’$(n) = n \times$ fact’$(n-1)$, if $n \geq 1$

Since the domain of fact’ is the set of natural numbers, a set over which induction is defined, we can easily see that this recursive definition is well defined.

• For $n = 0$, the base case, the value is simply $1$.

• For $n \geq 1$, the value of fact’$(n)$ is recursively defined in terms of fact’$(n-1)$. The argument of the recursive application decreases toward the base case.

In the Review of Relevant Mathematics appendix, we prove that fact$(n)$ $=$ fact’$(n)$ by mathematical induction.

The Haskell functions defined in the following subsections must compute fact$(n)$ when applied to argument value $n \geq 0$.

4.2.2 Factorial function using if-then-else: fact1

One way to translate the recursive definition fact’ into Haskell is the following:

    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 

• The first line above is the type signature for function fact1. In general, type signatures have the syntax object :: type.

  Haskell type names begin with an uppercase letter.

  The above defines object fact1 as a function (denoted by the -> symbol) that takes one argument of type integer (denoted by the first Int) and returns a value of type integer (denoted by the last Int).

  Haskell does not have a built-in natural number type. Thus we choose type Int for the argument and result of fact1.

  The Int data type is a bounded integer type, usually the integer data type supported directly by the host processor (e.g., 32- or 64-bits on most current processors), but it is guaranteed to have the range of at least a 30-bit, two’s complement integer ($-2^{29}$ to $2^{29}$).

• The declaration for the function fact1 begins on the second line. Note that it is an equation of the form

  fname parms = body

  where fname is the function’s name, parms are the function’s parameters, and body is an expression defining the function’s result.

  Function and variable names begin with lowercase letters optionally followed by a sequence of characters each of which is a letter, a digit, an apostrophe (') (sometimes pronounced “prime”), or an underscore (_).

  A function may have zero or more parameters. The parameters are listed after the function name without being enclosed in parentheses and without commas separating them.

  The parameter names may appear in the body of the function. In the evaluation of a function application the actual argument values are substituted for parameters in the body.

• Above we define the body function fact1 to be an if-then-else expression. This kind of expression has the form

  if condition then expression1 else expression2

  where

  condition is a Boolean expression, that is, an expression of Haskell type Bool, which has either True or False as its value

  expression1 is the expression that is returned when the condition is True

  expression2 is the expression (with the same type as expression1) that is returned when the condition is False

  Evaluation of the if-then-else expression in fact1 yields the value 1 if argument n has the value 0 (i.e., n == 0) and yields the value n * fact1 (n-1) otherwise.

• The else clause includes a recursive application of fact1. The whole expression (n-1) is the argument for the recursive application, so we enclose it in parenthesis.

  The value of the argument for the recursive application is less than the value of the original argument. For each recursive application of fact to a natural number, the argument’s value thus moves closer to the termination value 0.

• Unlike most conventional languages, the indentation is significant in Haskell. The indentation indicates the nesting of expressions.

  For example, in fact1 the n * fact1 (n-1) expression is nested inside the else clause of the if-then-else expression.

• This Haskell function does not match the mathematical definition given above. What is the difference?

  Notice the domains of the functions. The evaluation of fact1 will go into an “infinite loop” and eventually abort when it is applied to a negative value.

In Haskell there is only one way to form more complex expressions from simpler ones: apply a function.

Neither parentheses nor special operator symbols are used to denote function application; it is denoted by simply listing the argument expressions following the function name. For example, a function f applied to argument expressions x and y is written in the following prefix form:

    f x y

However, the usual prefix form for a function application is not a convenient or natural way to write many common expressions. Haskell provides a helpful bit of syntactic sugar, the infix expression. Thus instead of having to write the addition of x and y as

    add x y

we can write it as

    x + y

as we have since elementary school. Here the symbol + represents the addition function.

Function application (i.e., juxtaposition of function names and argument expressions) has higher precedence than other operators. Thus the expression f x + y is the same as (f x) + y.

4.2.3 Factorial function using guards: fact2

An alternative way to differentiate the two cases in the recursive definition is to use a different equation for each case. If the Boolean guard (e.g., n == 0) for an equation evaluates to true, then that equation is used in the evaluation of the function. A guard is written following the | symbol as follows:

    fact2 :: Int -> Int 
    fact2 n 
        | n == 0    = 1 
        | otherwise = n * fact2 (n-1)

Function fact2 is equivalent to the fact1. Haskell evaluates the guards in a top-to-bottom order. The otherwise guard always succeeds; thus it’s use above is similar to the trailing else clause on the if-then-else expression used in fact1.

4.2.4 Factorial function using pattern matching: fact3 and fact4

Another equivalent way to differentiate the two cases in the recursive definition is to use pattern matching as follows:

    fact3 :: Int -> Int 
    fact3 0 = 1 
    fact3 n = n * fact3 (n-1)

The parameter pattern 0 in the first leg of the definition only matches arguments with value 0. Since Haskell checks patterns and guards in a top-to-bottom order, the n pattern matches all nonzero values. Thus fact1, fact2, and fact3 are equivalent.

To stop evaluation from going into an “infinite loop” for negative arguments, we can remove the negative integers from the function’s domain. One way to do this is by using guards to narrow the domain to the natural numbers as in the definition of fact4 below:

    fact4 :: Int -> Int 
    fact4 n 
        | n == 0 =  1 
        | n >= 1 =  n * fact4 (n-1) 

Function fact4 is undefined for negative arguments. If fact4 is applied to a negative argument, the evaluation of the program encounters an error quickly and returns without going into an infinite loop. It prints an error and halts further evaluation.

We can define our own error message for the negative case using an error call as in fact4' below.

    fact4' :: Int -> Int 
    fact4' n 
        | n == 0    =  1 
        | n >= 1    =  n * fact4' (n-1)
        | otherwise = error "fact4' called with negative argument"

In addition to displaying the custom error message, this also displays a stack trace of the active function calls.

4.2.5 Factorial function using built-in library function: fact5

The four definitions we have looked at so far use recursive patterns similar to the recurrence relation fact’. Another alternative is to use the library function product and the list-generating expression [1..n] to define a solution that is like the function fact:

    fact5 :: Int -> Int 
    fact5 n = product [1..n]

The list expression [1..n] generates a list of consecutive integers beginning with 1 and ending with n. We study lists beginning with Chapter 13.

The library function product computes the product of the elements of a finite list.

If we apply fact5 to a negative argument, the expression [1..n] generates an empty list. Applying product to this empty list yields 1, which is the identity element for multiplication. Defining fact5 to return 1 is consistent with the function fact upon which it is based.

Which of the above definitions for the factorial function is better?

Most people in the functional programming community would consider fact4 (or fact4') and fact5 as being better than the others. The choice between them depends upon whether we want to trap the application to negative numbers as an error or to return the value 1.

4.2.6 Testing

Chapter 12 discusses testing of the Factorial module designed in this chapter. The test script is TestFactorial.hs.

5.2.1 Types and subtypes

Conceptually, a type is a set of values (i.e., possible states or objects) and a set of operations defined on the values in that set.

Similarly, a type S is (a behavioral) subtype of type T if the set of values of type S is a “subset” of the values in set T an set of operations of type S is a “superset” of the operations of type T. That is, we can safely substitute elements of subtype S for elements of type T because S’s operations behave the “same” as T’s operations.

This is known as the Liskov Substitution Principle [119,205].

Consider a type representing all furniture and a type representing all chairs. In general, we consider the set of chairs to be a subset of the set of furniture. A chair should have all the general characteristics of furniture, but it may have additional characteristics specific to chairs.

If we can perform an operation on furniture in general, we should be able to perform the same operation on a chair under the same circumstances and get the same result. Of course, there may be additional operations we can perform on chairs that are not applicable to furniture in general.

Thus the type of all chairs is a subtype of the type of all furniture according to the Liskov Substitution Principle.

5.2.2 Constants, variables, and expressions

Now consider the types of the basic program elements.

A constant has whatever types it is defined to have in the context in which it is used. For example, the constant symbol 1 might represent an integer, a real number, a complex number, a single bit, etc., depending upon the context.

A variable has whatever types its value has in a particular context and at a particular time during execution. The type may be constrained by a declaration of the variable.

An expression has whatever types its evaluation yields based on the types of the variables, constants, and operations from which it is constructed.

5.2.3 Static and dynamic

In a statically typed language, the types of a variable or expression can be determined from the program source code and checked at “compile time” (i.e., during the syntactic and semantic processing in the front-end of a language processor). Such languages may require at least some of the types of variables or expressions to be declared explicitly, while others may be inferred implicitly from the context.

Java, Scala, and Haskell are examples of statically typed languages.

In a dynamically typed language, the specific types of a variable or expression cannot be determined at “compile time” but can be checked at runtime.

Lisp, Python, JavaScript, and Lua are examples of dynamically typed languages.

Of course, most languages use a mixture of static and dynamic typing. For example, Java objects defined within an inheritance hierarchy must be bound dynamically to the appropriate operations at runtime. Also Java objects declared of type Object (the root class of all user-defined classes) often require explicit runtime checks or coercions.

5.2.4 Nominal and structural

In a language with nominal typing, the type of value is based on the type name assigned when the value is created. Two values have the same type if they have the same type name. A type S is a subtype of type T only if S is explicitly declared to be a subtype of T.

For example, Java is primarily a nominally typed language. It assigns types to an object based on the name of the class from which the object is instantiated and the superclasses extended and interfaces implemented by that class.

However, Java does not guarantee that subtypes satisfy the Liskov Substitution Principle. For example, a subclass might not implement an operation in a manner that is compatible with the superclass. (The behavior of subclass objects are this different from the behavior of superclass objects.) Ensuring that Java subclasses preserve the Substitution Principle is considered good programming practice in most circumstances.

In a language with structural typing, the type of a value is based on the structure of the value. Two values have the same type if they have the “same” structure; that is, they have the same public data attributes and operations and these are themselves of compatible types.

In structurally typed languages, a type S is a subtype of type T only if S has all the public data values and operations of type T and the data values and operations are themselves of compatible types. Subtype S may have additional data values and operations not in T.

Haskell is primarily a structurally typed language.

5.2.5 Polymorphic operations

Polymorphism refers to the property of having “many shapes”. In programming languages, we are primarily interested in how polymorphic function names (or operator symbols) are associated with implementations of the functions (or operations).

In general, two primary kinds of polymorphism exist in programming languages:

1. Ad hoc polymorphism, in which the same function name (or operator symbol) can denote different implementations depending upon how it is used in an expression. That is, the implementation invoked depends upon the types of function’s arguments and return value.

   There are two subkinds of ad hoc polymorphism.

   1. Overloading refers to ad hoc polymorphism in which the language’s compiler or interpreter determines the appropriate implementation to invoke using information from the context. In statically typed languages, overloaded names and symbols can usually be bound to the intended implementation at compile time based on the declared types of the entities. They exhibit early binding.

      Consider the language Java. It overloads a few operator symbols, such as using the + symbol for both addition of numbers and concatenation of strings. Java also overloads calls of functions defined with the same name but different signatures (patterns of parameter types and return value). Java does not support user-defined operator overloading; C++ does.

      Haskell’s type class mechanism, which we examine in a later chapter, implements overloading polymorphism in Haskell. There are similar mechanisms in other languages such as Scala and Rust.

   2. Subtyping (also known as subtype polymorphism or inclusion polymorphism) refers to ad hoc polymorphism in which the appropriate implementation is determined by searching a hierarchy of types. The function may be defined in a supertype and redefined (overridden) in subtypes. Beginning with the actual types of the data involved, the program searches up the type hierarchy to find the appropriate implementation to invoke. This usually occurs at runtime, so this exhibits late binding.

      The object-oriented programming community often refers to inheritance-based subtype polymorphism as simply polymorphism. This the polymorphism associated with the class structure in Java.

      Haskell does not support subtyping. Its type classes do support class extension, which enables one class to inherit the properties of another. However, Haskell’s classes are not types.

2. Parametric polymorphism, in which the same implementation can be used for many different types. In most cases, the function (or class) implementation is stated in terms of one or more type parameters. In statically typed languages, this binding can usually be done at compile time (i.e., exhibiting early binding).

   The object-oriented programming (e.g., Java) community often calls this type of polymorphism generics or generic programming.

   The functional programming (e.g., Haskell) community often calls this simply polymorphism.

5.2.6 Polymorphic variables

A polymorphic variable is a variable that can “hold” values of different types during program execution.

For example, a variable in a dynamically typed language (e.g., Python) is polymorphic. It can potentially “hold” any value. The variable takes on the type of whatever value it “holds” at a particular point during execution.

Also, a variable in a nominally and statically typed, object-oriented language (e.g., Java) is polymorphic. It can “hold” a value its declared type or of any of the subtypes of that type. The variable is declared with a static type; its value has a dynamic type.

A variable that is a parameter of a (parametrically) polymorphic function is polymorphic. It may be bound to different types on different calls of the function.

5.3.1 Integers: Int and Integer

The Int data type is usually an integer data type supported directly by the host processor (e.g., 32- or 64-bits on most current processors), but it is guaranteed to have the range of at least a 30-bit, two’s complement integer.

The type Integer is an unbounded precision integer type. Unlike Int, host processors usually do not support this type directly. The Haskell library or runtime system typically supports this type in software.

Haskell integers support the usual literal formats (i.e., constants) and typical operations:

• Infix binary operators such as + (addition), - (subtraction), * (multiplication), and ^ (exponentiation)

• Infix binary comparison operators such as == (equality of values), /= (inequality of values), <, <=, >, and >=

• Unary operator - (negation)

For integer division, Haskell provides two-argument functions:

• div such that div m n returns the integral quotient truncated toward negative infinity from dividing m by n

• quot such that quot m n returns the integral quotient truncated toward 0 from dividing m bem n

• mod (i.e., modulo) and rem (i.e., remainder) such that

      (div m n) * n + mod m n == m
      (quot m n)* n + rem m n == m 

To make these definitions more concrete, consider the following examples. Note that the result of mod has the same sign as the divisor and rem has the same sign as the dividend.

    div  7 3  == 2 
    quot 7 3  == 2 
    mod  7 3  == 1          -- same sign as divisor
    rem  7 3  == 1          -- same sign as dividend

    div  (-7) (-3) == 2 
    quot (-7) (-3) == 2
    mod  (-7) (-3) == (-1)  -- same sign as divisor
    rem  (-7) (-3) == (-1)  -- same sign as dividend

    div  (-7) 3 == (-3) 
    quot (-7) 3 == (-2)
    mod  (-7) 3 == 2        -- same sign as divisor
    rem  (-7) 3 == (-1)     -- same sign as dividend

    div  7 (-3) == (-3) 
    quot 7 (-3) == (-2) 
    mod  7 (-3) == (-2)     -- same sign as divisor
    rem  7 (-3) == 1        -- same sign as dividend

Haskell also provides the useful two-argument functions min and max, which return the minimum and maximum of the two arguments, respectively.

Two-arguments functions such as div, rem, min, and max can be applied in infix form by including the function name between backticks as shown below:

    5 `div` 3   -- yields 1 
    5 `rem` 3   -- yields 2
    5 `min` 3   -- yields 3 
    5 `max` 3   -- yields 5

5.3.2 Floating point numbers: Float and Double

The Float and Double data types are usually the single and double precision floating point numbers supported directly by the host processor.

Haskell floating point literals must include a decimal point; they may be signed or in scientific notation: 3.14159, 2.0, -2.0, 1.0e4, 5.0e-2, -5.0e-2.

Haskell supports the usual operations on floating point numbers. Division is denoted by / as usual.

In addition, Haskell supports the following for converting floating point numbers to and from integers:

• floor returns the largest integer less than its floating point argument.

• ceiling returns the smallest integer greater than its floating point argument

• truncate returns its argumentas an integer truncated toward 0.

• round returns it argument as an integer rounded away from 0.

• fromIntegral returns its integer argument as a floating point number in a context where Double or Float is required. It can also return its Integer argument as an Int or vice versa.

5.3.3 Booleans: Bool

The Bool (i.e., Boolean) data type is usually supported directly by the host processor as one or more contiguous bits.

The Bool literals are True and False. Note that these begin with capital letters.

Haskell supports Boolean operations such as && (and), || (or), and not (logical negation).

Functions can match against patterns using the Boolean constants. For example, we could define a function myAnd as follows:

    myAnd :: Bool -> Bool -> Bool
    myAnd True  b = b
    myAnd False _ = False

Above the pattern _ is a wildcard that matches any value but does not bind a value that can be used on the right-hand-side of the definition.

The expressions in Haskell if conditions and guards on function definitions must be Bool-valued expressions. They can include calls to functions that return Bool values.

5.3.4 Characters: Char

The Char data type is usually supported directly by the host processor by one or more contiguous bytes.

Haskell uses Unicode for its character data type. Haskell supports character literals enclosed in single quotes—including both the graphic characters (e.g., ’a’, ’0’, and ’Z’) and special codes entered following the escape character backslash \ (e.g., '\n' for newline, '\t' for horizontal tab, and '\\' for backslash itself).

In addition, a backslash character \ followed by a number generates the corresponding Unicode character code. If the first character following the backslash is o, then the number is in octal representation; if followed by x, then in hexadecimal notation; and otherwise in decimal notation.

For example, the exclamation point character can be represented in any of the following ways: ’!’, '\33', '\o41', '\x21'

5.3.5 Functions: t1 -> t2

If t1 and t2 are types then t1 -> t2 is the type of a function that takes an argument of type t1 and returns a result of type t2.

Function and variable names begin with lowercase letters optionally followed by a sequences of characters each of which is a letter, a digit, an apostrophe (') (sometimes pronounced “prime”), or an underscore (_).

Haskell functions are first-class objects. They can be arguments or results of other functions or be components of data structures. Multi-argument functions are curried-–that is, treated as if they take their arguments one at a time.

For example, consider the integer addition operation (+). (Surrounding the binary operator symbol with parentheses refers to the corresponding function.) In mathematics, we normally consider addition as an operation that takes a pair of integers and yields an integer result, which would have the type signature

    (+) :: (Int,Int) -> Int

In Haskell, we give the addition operation the type

    (+) :: Int -> (Int -> Int) 

or just

    (+) :: Int -> Int -> Int

since Haskell binds -> from the right.

Thus (+) is a one argument function that takes some Int argument and returns a function of type Int -> Int. Hence, the expression ((+) 5) denotes a function that takes one argument and returns that argument plus 5.

We sometimes speak of this (+) operation as being partially applied (i.e., to one argument instead of two).

This process of replacing a structured argument by a sequence of simpler ones is called currying, named after American logician Haskell B. Curry who first described it.

The Haskell library, called the standard prelude (or just Prelude), contains a wide range of predefined functions including the usual arithmetic, relational, and Boolean operations. Some of these operations are predefined as infix operations.

5.3.6 Tuples: (t1,t2,...,tn)

If t1, t2, $\cdots$, tn are types, where n is finite and n >= 2, then is a type consisting of n-tuples where the various components have the type given for that position.

Each element in a tuple may have different types. The number of elements in a tuple is fixed.

Examples of tuple values with their types include the following:

    ('a',1) :: (Char,Int)
    (0.0,0.0,0.0) :: (Double,Double,Double) 
    (('a',False),(3,4)) :: ((Char, Bool), (Int, Int))

We can also define a type synonym using the type declaration and the use the synonym in further declarations as follows:

    type Complex = (Float,Float)
    makeComplex :: Float -> Float -> Complex
    makeComplex r i = (r,i)`

A type synonym does not define a new type, but it introduces an alias for an existing type. We can use Complex in declarations, but it has the same effect as using (Float,Float) expect that Complex provides better documentation of the intent.

5.3.7 Lists: [t]

The primary built-in data structure in Haskell is the list, a sequence of values. All the elements in a list must have the same type. Thus we declare lists with notation such as [t] to denote a list of zero or more elements of type t.

A list literal is a comma-separated sequence of values enclosed between [ and ]. For example, [] is an empty list and [1,2,3] is a list of the first three positive integers in increasing order.

We will look at programming with lists in a later chapter.

5.3.8 Strings: String

In Haskell, a string is just a list of characters. Thus Haskell defines the data type String as a type synonym :

    type String = [Char]

We examine lists and strings in a later chapter, but, because we use strings in a few examples in this subsection, let’s consider them briefly.

A String literal is a sequence of zero or more characters enclosed in double quotes, for example, "Haskell programming".

Strings can contain any graphic character or any special character given as escape code sequence (using backslash). The special escape code \& is used to separate any character sequences that are otherwise ambiguous.

For example, the string literal "Hotty\nToddy!\n" is a string that has two newline characters embedded.

Also the string literal "\12\&3" represents the two-element list ['\12','3'].

The function show returns its argument converted to a String.

Because strings are represented as lists, all of the Prelude functions for manipulating lists also apply to strings. We look at manipulating lists and strings in later chapters of this textbook.

5.3.9 Advanced Types

In later chapters, we examine other important Haskell type concepts such as user-defined algebraic data types and type classes.

6.3.1 Developing a square root package

Consider the problem of computing the nonnegative square root of a nonnegative number $x$. Mathematically, we want to find the number $y$ such that

$y \geq 0$ and $y^{2} = x$.

A common algorithm in mathematics for computing the above $y$ is to use Newton’s method of successive approximations, which has the following steps for square root:

1. Guess at the value of $y$.

2. If the current approximation (guess) is sufficiently close (i.e., good enough), return it and stop; otherwise, continue.

3. Compute an improved guess by averaging the value of the guess $y$ and $x/y$, then go back to step 2.

To encode this algorithm in Haskell, we work top down to decompose the problem into smaller parts until each part can be solved easily. We begin this top-down stepwise refinement by defining a function with the type signature:

    sqrtIter :: Double -> Double -> Double 

We choose type Double (double precision floating point) to approximate the real numbers. Thus we can encode step 2 of the above algorithm as the following Haskell function definition:

    sqrtIter guess x                                    -- step 2
        | goodEnough guess x = guess
        | otherwise          = sqrtIter (improve guess x) x

We define function sqrtIter to take two arguments—the current approximation guess and nonnegative number x for which we need the square root. We have two cases:

• When the current approximation guess is sufficiently close to x, we return guess.

  We abstract this decision into a separate function goodEnough with type signature:

      goodEnough :: Double -> Double -> Bool 

• When the approximation is not yet close enough, we continue by reducing the problem to the application of sqrtIter itself to an improved approximation.

  We abstract the improvement process into a separate function improve with type signature:

      improve :: Double -> Double -> Double

  To ensure termination of sqrtIter, the argument (improve guess x) on the recursive call must get closer to termination (i.e., to a value that satisfies its base case).

The function improve takes the current guess and x and carries out step 3 of the algorithm, thus averaging guess and x/guess, as follows:

    improve :: Double -> Double -> Double     -- step 3
    improve guess x = average guess (x/guess)

Function application improve y x assumes x >= 0 && y > 0. We call this a precondition of the improve y x function.

Because of the precondition of improve, we need to strengthen the precondition of sqrtIter guess x to x >= 0 && guess > 0.

In improve, we abstract average into a separate function as follows:

    average :: Double -> Double -> Double
    average x y = (x + y) / 2

The new guess is closer to the square root than the previous guess. Thus the algorithm will terminate assuming a good choice for function goodEnough, which guards the base case of the sqrtIter recursion.

How should we define goodEnough? Given that we are working with the limited precision of computer floating point arithmetic, it is not easy to choose an appropriate test for all situations. Here we simplify this and use a tolerance of 0.001.

We thus postulate the following definition for goodEnough:

    goodEnough :: Double -> Double -> Bool 
    goodEnough guess x = abs (square guess - x) < 0.001 

In the above, abs is the built-in absolute value function defined in the standard Prelude library. We define square as the following simple function (but could replace it by just guess * guess):

    square :: Double -> Double 
    square x = x * x 

What is a good initial guess? It is sufficient to just use 1. So we can define an overall square root function sqrt' as follows:

    sqrt' :: Double -> Double
    sqrt' x | x >= 0 = sqrtIter 1 x

(A square root function sqrt is defined in the Prelude library, so a different name is needed to avoid the name clash.)

Function sqrt' x has precondition x >= 0. This and the choice of 1 for the initial guess ensure that functions sqrtIter and improve are applied with arguments that satisfy their preconditions.

6.3.2 Making the package a Haskell module

We can make this package into a Haskell module by putting the definitions in a file (e.g., named Sqrt) and adding a module header at the beginning as follows:

    module Sqrt
        ( sqrt' )
    where
        -- give the definitions above for functions sqrt',
        --   sqrtIter, improve, average, and goodEnough

The header gives the module the name Sqrt and lists the names of the features being exported in the parenthesis that follows the name. In this case, only function sqrt' is exported.

Other Haskell modules that import the Sqrt module can access the features named in its export list. In the case of Sqrt, the other functions—sqrtIter, goodEnough, and improve)— are local to (i.e., hidden inside) the module.

In this book, we often call the exported features (e.g., functions and types) the module’s public features and the ones not exported the private features.

We can import module Sqrt into a module such as module TestSqrt shown below. By default, the import makes all the definitions exported by Sqrt available within module TestSqrt. The importing module may select the features it wishes to export and may assign local names to the features it does import.

    module TestSqrt
    where

    import Sqrt -- file Sqrt.hs, import all public names 

    main = do
        putStrLn (show (sqrt' 16))
        putStrLn (show (sqrt' 2))

In the above Haskell code, the symbol “--” denotes the beginning of an end-of-line comment. All text after that symbol is text ignored by the Haskell compiler.

The Haskell module for the Square root case study is in file Sqrt.hs. Limited, smoke-testing code is in file SqrtTest.hs.

6.3.3 Reviewing top-down stepwise refinement

The program design strategy known as top-down stepwise refinement is a relatively intuitive design process that has long been applied in the design of structured programs in imperative procedural languages. It is also useful in the functional setting.

In Haskell, we can apply top-down stepwise refinement as follows.

1. Start with a high-level solution to the problem consisting of one or more functions. For each function, identify its type signature and functional requirements (i.e., its inputs, outputs, and termination condition).

   Some parts of each function may be incomplete—expressed as “pseudocode” expressions or as-yet-undefined functions.

2. Choose one of the incomplete parts. Consider the specified type signature and functional requirements. Refine the incomplete part by breaking it into subparts or, if simple, defining it directly in terms of Haskell expressions (including calls to the Prelude, other available library functions, or previously defined parts of the algorithm).

   When refining an incomplete part, consider the various options according to the relevant design criteria (e.g., time, space, generality, understandability, and elegance).

   The refinement of the function may require a refinement of the data being passed.

   If it not possible to design an appropriate function or data refinement, back up in the refinement process and readdress previous design decisions.

3. Continue step 2 until all parts are fully defined in terms of Haskell code and data and the resulting set of functions meets all required criteria.

For as long as possible, we should stay with terminology and notation that is close to the problem being solved. We can do this by choosing appropriate function names and signatures and data types. (In other chapters, we examine Haskell’s rich set of builtin and user-defined types.)

For stepwise refinement to work well, we must be willing to back up to earlier design decisions when appropriate. We should keep good documentation of the intermediate design steps.

The stepwise refinement method can work well for small programs , but it may not scale well to large, long-lived, general purpose programs. In particular, stepwise refinement may lead to a module structure in which modules are tightly coupled and not robust with respect to changes in requirements.

A combination of techniques may be needed to develop larger software systems. In the next section (6.4), we consider the use of modular design techniques.

6.4.1 Information-hiding modules and secrets

According to Parnas, the goals of modular design are to [134]:

1. enable programmers to understand the system by focusing on one module at a time (i.e., comprehensibility).

2. shorten development time by minimizing required communication among groups (i.e., independent development).

3. make the software system flexible by limiting the number of modules affected by significant changes (i.e., changeability).

Parnas advocates the use of a principle he called information hiding to guide decomposition of a system into appropriate modules (i.e., work assignments). He points out that the connections among the modules should have as few information requirements as possible [134].

In the Parnas approach, an information-hiding module:

• forms a cohesive unit of functionality separate from other modules

• hides a design decision—its secret—from other modules

• encapsulates an aspect of system likely to change (its secret)

Aspects likely to change independently of each other should become secrets of separate modules. Aspects unlikely to change can become interactions (connections) among modules.

This approach supports the goal of changeability (goal 2). When care is taken to design the modules as clean abstractions with well-defined and documented interfaces, the approach also supports the goals of independent development (goal 1) and comprehensibility (goal 3).

Information hiding has been absorbed into the dogma of contemporary object-oriented programming. However, information hiding is often oversimplified as merely hiding the data and their representations [177].

The secret of a well-designed module may be much more than that. It may include such knowledge as a specific functional requirement stated in the requirements document, the processing algorithm used, the nature of external devices accessed, or even the presence or absence of other modules or programs in the system [134,136,137]. These are important aspects that may change as the system evolves.

Secret of square root module

The secret of the Sqrt module in the previous section is the algorithm for computing the square root.

6.4.2 Contracts: Preconditions and postconditions

Now let’s consider the semantics (meaning) of functions.

The precondition of a function is what the caller (i.e., the client of the function) must ensure holds when calling the function. A precondition may specify the valid combinations of values of the arguments. It may also record any constraints on any “global” state that the function accesses or modifies.

If the precondition holds, the supplier (i.e., developer) of the function must ensure that the function terminates with the postcondition satisfied. That is, the function returns the required values and/or alters the “global” state in the required manner.

We sometimes call the set of preconditions and postconditions for a function the contract for that function.

Contracts of square root module

In the Sqrt module defined in the previous section, the exported function sqrt' x has the precondition:

    x >= 0

Function sqrt' x is undefined for x < 0.

The postcondition of the function sqrt' x function is that the result returned is the correct mathematical value of the square root within the allowed tolerance. That is, for a tolerance of 0.001:

    (sqrt x - 0.001)^2 < (sqrt x)^2 < (sqrt x + 0.001)^2

We can state preconditions and postconditions for the local functions sqrtIter, improve, average, and goodEnough in the Sqrt module. These are left as exercises.

The preconditions for functions average and goodEnough are just the assertion True (i.e., always satisfied).

Contracts of Factorial module

Consider the factorial functions defined in Chapter 4. (These are in the source file Factorial.hs.)

What are the preconditions and postconditions?

Functions fact1, fact2, and fact3 require that argument n be a natural number (i.e., nonnegative integer) value. If they are applied to a negative value for n, then the evaluation does not terminate. Operationally, they go into an “infinite loop” and likely will abort when the runtime stack overflows.

If function fact4 is called with a negative argument, then all guards and pattern matches fail. Thus the function aborts with a standard error message.

Similarly, function fact4' terminates with a custom error message for negative arguments.

Thus to ensure normal termination, we impose the precondition

    n >= 0

on all these factorial functions.

The postcondition of all six factorial functions is that the result returned is the correct mathematical value of n factorial. For fact4, that is:

fact4 n = fact’(n)

None of the six factorial functions access or modify any global data structures, so we do not include other items in the precondition or postcondition.

Function fact5 is defined to be 1 for all arguments less than zero. So, if this is the desired result, we can weaken the precondition to allow all integer values, for example,

    True

and strengthen the postcondition to give the results for negative arguments, for example:

fact5 n = if n >= 0 then fact’(n) else 1

Caveat: In this chapter, we ignore the limitations on the value of the factorial functions’ argument n imposed by the finite precision of the computer’s integer arithmetic. We readdress this issue somewhat in Chapter 12.

6.4.3 Interfaces for modules

It is important for an information-hiding module to have a well-defined and stable interface. What do we mean by interface?

According to Britton et al [20], an interface is a “set of assumptions … each programmer needs to make about the other program … to demonstrate the correctness of his own program”.

A module interface includes the type signatures (i.e., names, arguments, and return values), preconditions, and postconditions of all public operations (e.g., functions).

As we see in Chapter 7, the interface also includes the invariant properties of the data values and structures manipulated by the module and the definitions of any new data types exported by the module. An invariant must be part of the precondition of public operations except operations that construct elements of the data type (i.e., constructors). It must also be part of the postcondition of public operations except operations that destroy elements of the data type (i.e., destructors).

As we have seen, in Haskell the module not provide direct syntactic or semantic support for preconditions, postconditions, or invariant assertions.

Interface of square root module

The interface to the Sqrt module in the previous section consists of the function signature:

    sqrt' :: Double -> Double

where sqrt' x has the precondition and postcondition defined above. None of the other functions are accessible outside the module Sqrt and, hence, are not part of the interface.

6.4.4 Abstract interfaces for modules

An abstract interface is an interface that does not change when one module implementation is substituted for another [20,138]. It concentrates on module’s essential aspects and obscures incidental aspects that vary among implementations.

Information-hiding modules and abstract interfaces enable us to design and build software systems with multiple versions. The information-hiding approach seeks to identify aspects of a software design that might change from one version to another and to hide them within independent modules behind well-defined abstract interfaces.

We can reuse the software design across several similar systems. We can reuse an existing module implementation when appropriate. When we need a new implementation, we can create one by following the specification of the module’s abstract interface.

Abstract interface of square root module

For the Sqrt example, if we implemented a different module with the same interface (signatures, preconditions, postconditions, etc.), then we could substitute the new module for Sqrt and get the same result.

In this case, the interface is an abstract interface for the set of module implementations.

Caveats: Of course, the time and space performance of the alternative modules might differ. Also, because of the nature of floating point arithmetic, it may be difficult to ensure both algorithms have precisely the same termination conditions.

6.4.5 Client-supplier relationship

The design and implementation of information-hiding modules should be approached from two points of view simultaneously:

supplier:

the developers of the module—the providers of the services

client:

the users of the module—the users of the services (e.g., the designers of other modules)

The client-supplier relationship is as represented in the following diagram:

   ________________             ________________ 
  |                |           |                |
  |     Client     |===USES===>|    Supplier    |
  |________________|           |________________|

    (module user)                   (module)
    

The supplier’s concerns include:

• efficient and reliable algorithms and data structures

• convenient implementation

• easy maintenance

The clients’ concerns include:

• accomplishing their own tasks

• using the supplier module without effort to understand its internal details

• having a sufficient, but not overwhelming, set of operations.

As we have noted previously, the interface of a module is the set of features (i.e., public operations) provided by a supplier to clients.

A precise description of a supplier’s interface forms a contract between clients and supplier.

The client-supplier contract:

1. gives the responsibilities of the client

   These are the conditions under which the supplier must deliver results—when the preconditions of the operations are satisfied (i.e., the operations are called correctly).

2. gives the responsibilities of the supplier

   These are the benefits the supplier must deliver—make the postconditions hold at the end of the operation (i.e., the operations deliver the correct results).

The contract

• protects the client by specifying how much must be done by the supplier

• protects the supplier by specifying how little is acceptable to the client

If we are both the clients and suppliers in a design situation, we should consciously attempt to separate the two different areas of concern, switching back and forth between our supplier and client “hats”.

6.4.6 Design criteria for interfaces

What else should we consider in designing a good interface for an information-hiding module?

In designing an interface for a module, we should also consider the following criteria. Of course, some of these criteria conflict with one another; a designer must carefully balance the criteria to achieve a good interface design.

Note: These are general principles; they are not limited to Haskell or functional programming. In object-oriented languages, these criteria apply to class interfaces.

• Cohesion: All operations must logically fit together to support a single, coherent purpose. The module should describe a single abstraction.

• Simplicity: Avoid needless features. The smaller the interface the easier it is to use the module.

• No redundancy: Avoid offering the same service in more than one way; eliminate redundant features.

• Atomicity: Do not combine several operations if they are needed individually. Keep independent features separate. All operations should be primitive, that is, not be decomposable into other operations also in the public interface.

• Completeness: All primitive operations that make sense for the abstraction should be supported by the module.

• Consistency: Provide a set of operations that are internally consistent in

  • naming convention (e.g.,, in use of prefixes like “set” or “get”, in capitalization, in use of verbs/nouns/adjectives),

  • use of arguments and return values (e.g.,, order and type of arguments),

  • behavior (i.e., make operations work similarly).

  Avoid surprises and misunderstandings. Consistent interfaces make it easier to understand the rest of a system if part of it is already known.

  The operations should be consistent with good practices for the specific language being used.

• Reusability: Do not customize modules to specific clients, but make them general enough to be reusable in other contexts.

• Robustness with respect to modifications: Design the interface of an module so that it remains stable even if the implementation of the module changes. (That is, it should be an abstract interface for an information-hiding module as we discussed above.)

• Convenience: Where appropriate, provide additional operations (e.g.,, beyond the complete primitive set) for the convenience of users of the module. Add convenience operations only for frequently used combinations after careful study.

We must trade off conflicts among the criteria. For example, we must balance:

• completeness versus simplicity

• reusability versus simplicity

• convenience versus consistency, simplicity, no redundancy, and atomicity

We must also balance these design criteria against efficiency and functionality.

7.3.1 Rational number arithmetic

For this example, let’s implement a group of Haskell functions to perform rational number arithmetic, assuming that the Haskell library does not contain such a data type. We focus first on the operations we want to perform on the data.

In mathematics we usually write rational numbers in the form $\frac{\texttt{x}}{\texttt{y}}$ where x and y are integers and y $\neq$ 0.

For now, let us assume we have a special type Rat to represent rational numbers and a constructor function

    makeRat :: Int -> Int -> Rat

to create a Haskell rational number instance from a numerator x and a denominator y. That is, makeRat x y constructs a Haskell rational number with mathematical value $\frac{\texttt{x}}{\texttt{y}}$, where $\texttt{y} \neq 0$.

Let us also assume we have selector functions numer and denom with the signatures:

    numer, denom :: Rat -> Int

Functions numer and denom take a valid Haskell rational number and return its numerator and denominator, respectively.

Requirement:

For any Int values x and y where $\texttt{y} \neq 0$, there exists a Haskell rational number r such that makeRat x y == r and rational number values $\frac{\texttt{numer r}}{\texttt{denom r}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Note: In this example, we use fraction notation like $\frac{\texttt{x}}{\texttt{y}}$ to denote the mathematical value of the rational number. In constrast, r above denotes a Haskell value representing a rational number.

We consider how to implement rational numbers in Haskell later, but for now let’s look at rational arithmetic implemented using the constructor and selector functions specified above.

Given our knowledge of rational arithmetic from mathematics, we can define the operations for unary negation, addition, subtraction, multiplication, division, and equality as follows. We assume that the operands x and y are values created by the constructor makeRat.

    negRat :: Rat -> Rat 
    negRat x = makeRat (- numer x) (denom x)

    addRat, subRat, mulRat, divRat :: Rat -> Rat -> Rat  -- (1)
    addRat x y = makeRat (numer x * denom y + numer y * denom x)
                         (denom x * denom y) 
    subRat x y = makeRat (numer x * denom y - numer y * denom x)
                         (denom x * denom y) 
    mulRat x y = makeRat (numer x * numer y) (denom x * denom y) 
    divRat x y  -- (2) (3)
        | eqRat y zeroRat = error "Attempt to divide by 0"
        | otherwise       = makeRat (numer x * denom y)
                                    (denom x * numer y)

    eqRat :: Rat -> Rat -> Bool 
    eqRat x y = (numer x) * (denom y) == (numer y) * (denom x)

The above code:

1. combines the type signatures for all four arithmetic operations into a single declaration by listing the names separated by commas

2. introduces the parameterless function zeroRat to abstract the constant rational number value 0

   Note: We could represent zero as makeRat 0 1 but choose to introduce a separate abstraction.

3. calls the error function for an attempt to divide by zero

These arithmetic functions do not depend upon any specific representation for rational numbers. Instead, they use rational numbers as a data abstraction defined by the type Rat, constant zeroRat, constructor function makeRat, and selector functions numer and denom.

The goal of a data abstraction is to separate the logical properties of data from the details of how the data are represented.

7.3.2 Rational number data representation

Now, how can we represent rational numbers?

For this package, we define type synonym Rat to denote this type:

    type Rat = (Int, Int) 

For example, (1,7), (-1,-7), (3,21), and (168,1176) all represent the value $\frac{\texttt{1}}{\texttt{7}}$.

As with any value that can be expressed in many different ways, it is useful to define a single canonical (or normal) form for representing values in the rational number type Rat.

It is convenient for us to choose a Haskell rational number representation (x,y) that satisfies all parts of the following Rational Representation Property:

• (x,y) $\in$ (Int,Int)

• y > 0

• if x == 0, then y == 1

• x and y are relatively prime

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

By relatively prime, we mean that the two integers have no common divisors except 1.

This representation keeps the magnitudes of the numerator x and denominator y small, thus reducing problems with overflow arising during arithmetic operations.

This representation also gives a unique representation for zero. For convenience, we define the name zeroRat to represent this constant:

    zeroRat :: (Int,Int)
    zeroRat = (0,1)

We can now define constructor function makeRat x y that takes two Int values (for the numerator and the denominator) and returns the corresponding Haskell rational number in this canonical form.

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                          ++ show x ++ "/0" )         -- (1)
    makeRat 0 _ = zeroRat
    makeRat x y = (x' `div` d, y' `div` d)            -- (2)
        where x' = (signum' y) * x                    -- (3,4)
              y' = abs' y 
              d  = gcd' x' y'

In the definition of makeRat, we use features of Haskell we have not used in the previous examples. the above code:

1. uses the infix ++ (read “append”) operator to concatenate two strings

   We discuss ++ in the chapter on infix operations.

2. puts backticks (`) around an alphanumeric function name to use that function as an infix operator

   The function div denotes integer division. Above the div operator denotes the integer division function used in an infix manner.

3. uses a where clause to introduce x', y', and d as local definitions within the body of makeRat

   These local definition can be accessed from within makeRat but not from outside the function. In contrast, sqrtIter in the Square Root example is at the same level as sqrt', so it can be called by other functions (in the same Haskell module at least).

   The where feature allows us to introduce new definitions in a top-down manner—first using a symbol and then defining it.

4. uses type inference for local variables x', y', and d instead of giving explicit type definitions

   These parameterless functions could be declared

       x', y', d :: Int

   but it was not necessary because Haskell can infer the types from the types involved in their defining expressions.

   Type inference can be used more broadly in Haskell, but explicit type declarations should be used for any function called from outside.

We require that makeRat x y satisfy the precondition:

    y /= 0

The function generates an explicit error exception if it does not.

As a postcondition, we require makeRat x y to return a result (x',y') such that:

• (x',y') satisfies the Rational Representation Property

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Note: Together the two postcondition requirements imply that $\frac{\texttt{x'}}{\texttt{y'}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

The function signum' (similar to the more general function signum in the Prelude) takes an integer and returns the integer -1, 0, or 1 when the number is negative, zero, or positive, respectively.

    signum' :: Int -> Int 
    signum' n | n == 0     =  0 
              | n > 0      =  1 
              | otherwise  = -1 

The function abs' (similar to the more general function abs in the Prelude) takes an integer and returns its absolute value.

    abs' :: Int -> Int
    abs' n | n >= 0    =  n
           | otherwise = -n

The function gcd' (similar to the more general function gcd in the Prelude) takes two integers and returns their greatest common divisor.

    gcd' :: Int -> Int -> Int 
    gcd' x y = gcd'' (abs' x) (abs' y) 
        where gcd'' x 0 = x 
              gcd'' x y = gcd'' y (x `rem` y) 

Prelude operation rem returns the remainder from dividing its first operand by its second.

Given a tuple (x,y) constructed by makeRat as defined above, we can define numer (x,y) and denom (x,y) as follows:

    numer, denom :: Rat -> Int
    numer (x,_) = x
    denom (_,y) = y

The preconditions of both numer (x,y) and denom (x,y) are that their arguments (x,y) satisfy the Rational Representation Property.

The postcondition of numer (x,y) = x is that the rational number values $\frac{\texttt{x}}{\texttt{numer (x,y)}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Similarly, the postcondition of denom (x,y) = y is that the rational number values $\frac{\texttt{denom (x,y)}}{y}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Finally, to allow rational numbers to be displayed in the normal fractional representation, we include function showRat in the package. We use function show, found in the Prelude, here to convert an integer to the usual string format and use the list operator ++ to concatenate the two strings into one.

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)

Unlike Rat, zeroRat, makeRat, numer, and denom, function showRat (as implemented) does not use knowledge of the data representation. We could optimize it slightly by allowing it to access the structure of the tuple directly.

7.3.3 Rational number modularization

There are three groups of functions in this package:

1. the six public rational arithmetic functions negRat, addRat, subRat, mulRat, divRat, and eqRat

2. the public type Rat, constant zeroRat, public constructor function makeRat, public selector functions numer and denom, and string conversion function showRat

3. the private utility functions called only by the second group, but just reimplementations of Prelude functions anyway

    module RationalCore
        (Rat, makeRat, zeroRat, numer, denom, showRat)
    where
        -- Rat,makeRat,zeroRat,numer,denom,showRat definitions

    module Rational1
      ( Rat, zeroRat, makeRat, numer, denom, showRat,
        negRat, addRat, subRat, mulRat, divRat, eqRat )
    where
        import RationalCore
        -- negRat,addRat,subRat,mulRat,divRat,eqRat definitions 

7.3.4 Alternative data representation

In the rational number data representation above, constructor makeRat creates pairs in which the two integers are relatively prime and the sign is on the numerator. Selector functions numer and denom just return these stored values.

An alternative representation is to reverse this approach, as shown in the following module (in file RationalDeferGCD.hs.)

    module RationalDeferGCD
        (Rat, zeroRat, makeRat, numer, denom, showRat)
    where

    type Rat = (Int,Int)

    zeroRat :: (Int,Int)
    zeroRat = (0,1)

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                          ++ show x ++ "/0" )
    makeRat 0 y = zeroRat 
    makeRat x y = (x,y)

    numer :: Rat -> Int
    numer (x,y) = x' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    denom :: Rat -> Int
    denom (x,y) = y' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)

This approach defers the calculation of the greatest common divisor until a selector is called.

In this alternative representation, a rational number (x,y) must satisfy all parts of the following Deferred Representation Property:

• (x,y) $\in$ (Int,Int)

• y /= 0

• if x == 0 , then y == 1

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Furthermore, we require that makeRat x y satisfies the precondition:

    y /= 0

The function generates an explicit error condition if it does not.

As a postcondition, we require makeRat x y to return a result (x',y') such that:

• (x',y') satisfies the Deferred Representation Property

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

The preconditions of both numer (x,y) and denom (x,y) are that (x,y) satisfies the Deferred Representation Property.

The postcondition of numer (x,y) = x' is that the rational number values $\frac{\texttt{x'}}{\texttt{numer (x,y)}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Similarly, the postcondition of denom (x,y) = y is that the rational number values $\frac{\texttt{denom (x,y)}}{y'}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Question:

What are the advantages and disadvantages of the two data representations?

Like module RationalCore, the design secret for this module, RationalDeferGCD, is the rational number data representation.

Regardless of which approach is used, the definitions of the arithmetic and comparison functions do not change. Thus the Rational module can import data representation module RationalCore or RationalDeferGCD.

Figure 7.1 shows the dependencies among the modules we have examined in the rational arithmetic example.

We can consider the RationalCore and RationalDeferGCD modules as two concrete instances (Haskell modules) of a more abstract module we call RationalRep in the diagram.

The module Rational relies on the abstract module RationalRep for an implementation of rational numbers. In the Haskell code above, there are really two versions of the Haskell module Rational that differ only in whether they import RationalCore or RationalDeferGCD.

Chapter 21 introduces user-defined (algebraic) data types. Instead of concrete data types (e.g., the Int pairs used by the type alias Rat), we can totally hide the details of the data representation using modules.

7.3.5 Haskell information-hiding modules

In the Rational Arithmetic example, we defined two information-hiding modules:

1. “RationalRep”, whose secret is how to represent the rational number data and whose interface consists of the data type Rat, constant zeroRat, operations (functions) makeRat, numer, denom, and showRat, and the constraints on these types and functions

2. “Rational”, whose secret is how to implement the rational number arithmetic and whose interface consists of operations (functions) negRat, addRat, subRat, mulRat, divRat, and eqRat, the other module’s interface, and the constraints on these types and functions

We developed two distinct Haskell modules, RationalCore and RationalDeferGCD, to implement the “RationalRep” information-hiding module.

We developed one distinct Haskell module, Rational, to implement the “Rational” information-hiding module. This module can be paired (i.e., by changing the import statement) with either of the other two variants of “RationalRep” module. (Source file Rational1.hs imports module RationalCore; source file Rational2.hs imports module RationalDeferGCD.)

Unfortunately, Haskell 2010 has a relatively weak module system that does not support multiple implementations as well as we might like. There is no way to declare that multiple Haskell modules have the same interface other than copying the common code into each module and documenting the interface carefully. We must also have multiple versions of Rational that differ only in which other module is imported.

Together the Glasgow Haskell Compiler (GHC) release 8.2 (July 2017) and the Cabal-Install package manager release 2.0 (August 2017) support a new extension, the Backpack mixin package system. This new system remedies the above shortcoming. In this new approach, we would define the abstract module “RationalRep” as a signature file and require that RationalCore and RationalDeferGCD conform to it.

Further discussion of this new module system is beyond the scope of this chapter.

7.3.6 Rational number testing

Chapter 12 discusses testing of the Rational modules designed in this chapter. The test scripts for the following modules are in the files shown:

• Module RationalRep

  • TestRatRepCore.hs for module instance RationalCore

  • TestRatRepDefer.hs for module instance RationalDeferGCD

• Module Rational

  • TestRational1.hs for Rational using RationalCore.

  • TestRational2.hs for Rational using RationalDeferGCD.

7.4.1 RationalRep modules

In the Rational Arithmetic example, the interface invariant for the “RationalRep” abstract module is the following.

RationalRep Interface Invariant:

For any valid Haskell rational number r, all the following hold:

• r $\in$ Rat

• denom r > 0

• if numer r == 0, then denom r == 1

• numer r and denom r are relatively prime

• the (mathematical) rational number value is $\frac{\texttt{numer r}}{\texttt{denom r}}$

We note that the precondition for makeRat x y is defined above without any dependence upon the concrete representation.

    y /= 0

We can restate the postcondition for makeRat x y = r generically to require both of the following to hold:

• r satisfies the RationaRep Interface Invariant

• rational number r ’s value is $\frac{\texttt{x}}{\texttt{y}}$

The preconditions of both numer r and denom r are that their argument r satisfies the RationalRep Interface Invariant.

The postcondition of numer r = x' is that the rational number value $\frac{\texttt{x'}}{\texttt{denom r}}$ is equal to the rational number value of r.

Similarly, the postcondition of denom r = y' is that the rational number value $\frac{\texttt{numer r}}{y'}$ is equal to the rational number value of r.{.haskell}

An implementation invariant guides the developers in the design and implementation of the internal details of a module. It relates the internal details to the interface invariant.

7.4.2 Rational modules

The Rational abstract module extends the RationalRep abstract module with new functionality.

• It imports the public interface of the RationalRep abstract module and exports those features in its own public interface. Thus it must maintain the interface invariant for the RationalRep module it uses.

• It does not add any new data types or constructor (or destructor) functions. So it does not need any new invariant components for new data abstractions.

• It adds one unary and four binary arithmetic functions that take rational numbers and return a rational number. It does so by using the data abstraction provided by the RationalRep module. These must preserve the RationalRep interface invariant.

• It adds an equality comparison function that takes two rational numbers and returns a Bool.