Exploring Languages with Interpreters
and Functional Programming
H. Conrad Cunningham
27 April 2022
Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of April 2022 is a recent version of Firefox from Mozilla.
Instability Warning: This version of ELIFP is in work beginning in January 2022. The author may change its structure and content without warning. No changes are planned to the 2018 version upon which the this version is based. The stable version is on the Fall 2018 CSci 450 course website.
Feedback Request: The author plans to publish this textbook eventually. He invites anyone using this book to give him feedback on its current structure and content: to point out typos and other errors or suggest improvements and extensions. He can be contacted at hcc AT cs DOT olemiss DOT edu.
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 400page 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.
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.
As the title suggests, I designed this textbook to be used for at least two different kinds of courses:
A course on “functional programming” targeted at advanced undergraduate and beginning graduate students who have previously programmed using imperative languages but who have not used functional or relational languages extensively.
This functional and modular programming course focuses on parts of Chapter 2 and 80 and Chapters 430.
I have been teaching such an elective course at the University of Mississippi since 1991 (CSci 555, Functional Programming). I have been teaching the Haskell programming language since 1993. Some of the content of this textbook evolved from class notes I originally developed for the course in the 19916 period.
My approach to the course was initially motivated by the first edition of the classic Bird and Wadler textbook [13,15].
A course on programming language organization targeted at a similar audience.
There are several approaches to teaching the programming languages course. My approach in this textbook focuses on “exploring languages with interpreters”. It seeks to guide students to learn how programming languages work by developing interpreters for simple languages.
This programming language organization course focuses on Chapters 13, Chapters 4049, and parts of Chapters 430 as needed.
Kamin’s excellent textbook Programming Languages: An InterpreterBased Approach [108] motivated my approach. But, instead of using Pascal or C to develop the interpreters as Kamin’s book did, this textbook primarily uses Haskell. Other influences on my approach are the book by Sestoft [159,160], the online books by Krishnamurthi [114,115], and an early manuscript by Ramsey [148] (which is based on Kamin’s book).
I began experimenting with this approach using the Lua language in my graduate Software Language Engineering (CSci 658) course in Fall 2013. I first taught the interpreter approach (using Lua) in the required undergraduate Organization of Programming Languages (CSci 450) course at the University of Mississippi in 2016. I used Haskell with the interpreterbased approach in 2017 and 2018.
Of course, students must become familiar with basic functional programming and Haskell for Course 2 to be possible.
Most real courses will likely be a mix of the two approaches.
Course type 1 is a course on functional and modular programming.
As a course on programming, Course 1 emphasizes the analysis and solution of problems, the development of correct and efficient algorithms and data structures that embody the solutions, and the expression of the algorithms and data structures in a form suitable for processing by a computer. The focus is more on the human thought processes than on the computer execution processes.
As a course on functional programming, Course 1 approaches programming as the construction of definitions for (mathematical) functions and (immutable) data structures. Functional programs consist of expressions that use these definitions. The execution of a functional program entails the evaluation of the expressions making up the program. Thus this course’s focus is on problem solving techniques, algorithms, data structures, and programming notations appropriate for the functional approach.
As a course on modular programming, Course 1 approaches the construction of large programs as sets of modules that collaborate to solve a problem. Each module is a coherent collection of function and data type definitions. A module hides its private features, allowing their use only within the module, and exposes its public features, enabling their use by the other modules in the program.
Course 1 is not a course on functional or modular programming languages. In particular, it does not undertake an indepth study of the techniques for implementing such languages on computers. (That is partly covered in Course 2.) The focus is on the concepts for programming, not on the internal details of the technological artifact that executes the programs.
Of course, we want to be able to execute our programs on a computer and, moreover, to execute them efficiently. Thus we must become familiar with some concrete programming language and use an implementation of that language to execute our programs. To be able to analyze program efficiency, we must also become familiar with the basic techniques that are used to evaluate expressions.
The academic community has long been interested in functional programming. In recent years, the practitioner community has also become interested in functional programming techniques and language features. There is growing use of languages that are either primarily functional or have significant functional subsets—such as Haskell, OCaml, Scala, Clojure, F#, Erlang, and Elixir. Most mainstream languages have been extended with new functional programming features and libraries—for example, Java, C#, Python, JavaScript, and Swift. Other interesting research languages such as Elm and Idris are also generating considerable interest.
In this textbook, we use the Haskell 2010 language. Haskell is a “lazy” functional language whose development began in the late 1980’s. We also use a set of programming tools based on GHC, the Glasgow Haskell Compiler. GHC is distributed in a “batteries included” bundle called the the Haskell Platform. (That is, it bundles GHC with commonly used libraries and tools.)
Most of the concepts, techniques, and skills learned in this Haskellbased course can be applied in other functional and multiparadigm languages and libraries.
More importantly, any time we learn new approaches to problem solving and programming, we become better programmers in whatever language we are working. A course on functional programming provides a novel, interesting, and, probably at times, frustrating opportunity to learn more about the nature of the programming task.
Enjoy the “functional programming” aspects of the course and textbook!
Course type 2 is a course on programming language organization that emphasizes design and implementation of a sequence of interpreters for simple languages.
When we first approach a new programming language, we typically think about the syntax of the language—how the external (e.g., textual) representation of the language is structured.
Syntax is important, but the semantics is more important. The semantics defines what the language means: how it “behaves” at “runtime”.
In Course 2 we primarily focus on the semantics. We express the essential aspects of a expression’s structure (i.e., syntax) with an abstract syntax tree (AST) and then process the AST to obtain a result. For example, we may have:
an interpreter that takes an AST and evaluates it in some environment to obtain its value
a transformer that takes the AST and produces a related but different (e.g., more efficient) program in the same language
a compiler that takes an AST and produces a related program in a different language
By “exploring languages with interpreters”, we can better understand the semantics of the programming languages. We can learn to use languages more effectively. We can explore alternative designs and implementations for languages.
This textbook uses functional and modular programming in Haskell—a paradigm and language that most students in Course 2 do not know—to implement the interpreters. Students learn new language concepts by both learning Haskell and by building language processors.
This textbook assumes the reader has basic knowledge and skills in programming, algorithms, and data structures at least at the level of a threesemester introductory computer science sequence. It assumes that the reader has programming experience using a language such as Java, C++, Python, or C#; it does not assume any previous experience in functional programming. (For example, successful completion of at least CSci 211, Computer Science III, at the University of Mississippi should be sufficient.)
This textbook also assumes the reader has basic knowledge and understanding of introductory computer architecture from a programmer’s perspective. (For example, successful completion of at least CSci 223, Computer Organization and Assembly Language, at the University of Mississippi should be sufficient.)
In addition, this course assumes the reader has basic knowledge and skills in mathematics at the level of a collegelevel course in discrete mathematical structures for computer science students. (For example, concurrent enrollment in Math 301, Discrete Mathematics, at the University of Mississippi should suffice.) The “Review of Relevant Mathematics” chapter (appendix) reviews some of the concepts, terminology, and notation used in this course.
Although I only began to write this textbook in Summer 2016, it is a result of a journey I began long ago. Many other writers, colleagues, students, and friends have helped me during this journey.
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 thensanctioned 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 GruiaCatalin 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 “justintime” in latenight 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 19931996 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.
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 runtime 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 8type 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 midway 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 200115). 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 interpreterbased 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 twothirds of the semester, leaving Lua in onethird, 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!
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 Haskellbased 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 Luabased 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 Pandocflavored 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, Pandocflavored Markdown, and plain text (e.g., program comments).
Pandocflavored 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 languageprocessing 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 Haskellbased functional programming course materials to include materials for the interpreterbased approach to the programming languages course and new Haskellrelated 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 Luabased 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 languageprocessing 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 longtime 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 Schemelike 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 fulltime faculty in May 2019. As one of my postretirement projects, I plan to continue work on this textbook. However, the work went slowly until 2022 because of the COVID19 pandemic disruptions, my continued work with two PhD students until mid2021, 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 Pandocrelated tools to accomplish this.
The goal of this chapter is motivate the study of programming language organization by:
describing the evolution of computers since the 1940’s and its impact upon contemporary programming language design and implementation
identifying key higherlevel programming languages that have emerged since the early 1950’s
To put our study in perspective, let’s examine the effect of computing hardware evolution on programming languages by considering a series of questions.
When were the first “modern” computers developed? That is, programmable electronic computers.
Although the mathematical roots of computing go back more than a thousand years, it is only with the invention of the programmable electronic digital computer during the World War II era of the 1930s and 1940s that modern computing began to take shape.
One of the first computers was the ENIAC (Electronic Numerical Integrator and Computer), developed in the mid1940s at the University of Pennsylvania. When construction was completed in 1946, it cost about $500,000. In today’s terms, that is nearly $7,000,000.
The ENIAC weighed 30 tons, occupied as much space as a small house, and consumed 160 kilowatts of electric power.
Initially, the ENIAC had no main memory. Instead it had 20 accumulators, each 10 decimal digits wide. Later 100 words of core were added.
Similarly, the ENIAC had no external memory as we know it today. It could read and write stacks of punch cards.
The ENIAC was not a stored program computer. It was programmed mostly by connecting cables in plugboards. It took several days of careful work to enter one program. The program was only changed every few weeks.
Aside: Many of the early programmers were women. This is quite a contrast to contemporary programming teams that are mostly male. What happened?
The ENIAC and most other computers of that era were designed for military purposes, such as calculating firing tables for artillery or breaking codes. As a result, many observers viewed the market for such devices to be quite small. The observers were wrong!
Electronics technology has improved greatly in 70 years. Today, a computer with the capacity of the ENIAC would be smaller than a coin from our pockets, would consume little power, and cost just a few dollars on the mass market.
How have computer systems and their use evolved over the past 70 years?
Contemporary processors are much smaller and faster. They use much less power, cost much less money (when mass produced), and operate much more reliably.
Contemporary “main” memories are much larger in capacity, smaller in physical size, and faster in access speed. They also use much less power, cost much less money, and operate much more reliably.
The number of processors per machine has increased from one to many. First, channels and other coprocessors were added, then multiple CPUs. Today, computer chips for common desktop and mobile applications have several processors—cores—on each chip, plus specialized processors such as graphics processing units (GPUs) for data manipulation and parallel computation. This trend toward multiprocessors will likely continue given that physics dictates limits on how small and fast we can make computer processors; to continue to increase in power means increasing parallelism.
Contemporary external storage devices are much larger in capacity, smaller in size, faster in access time, and cost less.
The number of computers available per user has increased from much less than one to many more than one.
Early systems were often locked into rooms, with few or no direct connections to the external world and just a few kinds of input/output devices. Contemporary systems may be on the user’s desktop or in the user’s backpack, be connected to the internet, and have many kinds of input/output devices.
The range of applications has increased from a few specialized applications (e.g., codebreaking, artillery firing tables) to almost all human activities.
The cost of the human staff to program, operate, and support computer systems has probably increased somewhat (in constant dollars).
How have these changes affected programming practice?
In the early days of computing, computers were very expensive and the cost of the human workers to use them relatively less. Today, the opposite holds. So we need to maximize human productivity.
In the early days of computing, the slow processor speeds and small memory sizes meant that programmers had to control these precious resources to be able to carry out most routine computations. Although we still need to use efficient algorithms and data structures and use good coding practices, programmers can now bring large amounts of computing capacity to bear on most problems. We can use more computing resources to improve productivity to program development and maintenance. The size of the problems we can solve computationally has increased beyond what would be possible manually.
In the early days of computing, multiple applications and users usually had to share one computer. Today, we can often apply many processors for each user and application if needed. Increasingly, applications must be able to use multiple processors effectively.
Security on early systems meant keeping the computers in locked rooms and restricting physical access to those rooms. In contemporary networked systems with diverse applications, security has become a much more difficult issue with many aspects.
Currently, industry can devote considerable hardware and software resources to the development of production software.
The first higherlevel programming languages began to appear in the 1950s. IBM released the first compiler for a programming language in 1957–for the scientific programming language Fortran. Although Fortran has evolved considerably during the past 60 years, it is still in use today.
How have the above changes affected programming language design and implementation over the past 60 years?
Contemporary programming languages often use automatic memory allocation and deallocation (e.g., garbage collection) to manage a program’s memory. Although programs in these languages may use more memory and processor cycles than handoptimized programs, they can increase programmer productivity and the security and reliability of the programs. Think Java, C#, and Python versus C and C++.
Contemporary programming languages are often implemented using an interpreter instead of a compiler that translates the program to the processor’s machine code–or be implemented using a compiler to a virtual machine instruction set (which is itself interpreted on the host processor). Again they use more processor and memory resources to increase programmer productivity and the security and reliability of the programs. Think Java, C#, and Python versus C and C++.
Contemporary programming languages should make the capabilities of contemporary multicore systems conveniently and safely available to programs and applications. To fail to do so limits the performance and scalability of the application. Think Erlang, Scala, and Clojure versus C, C++, and Java.
Contemporary programming languages increasingly incorporate declarative features (higherorder functions, recursion, immutable data structures, generators, etc.). These features offer the potential of increasing programming productivity, increasing the security and reliability of programs, and more conveniently and safely providing access to multicore processor capabilities. Think Scala, Clojure, and Java 8 and beyond versus C, C++, and older Java.
As we study programming and programming languages in this and other courses, we need to keep the nature of the contemporary programming scene in mind.
From the instructor’s perspective, key languages and milestones in the history of programming languages include the following.
Note: These descriptions use terminology such as imperative and function that is defined in Chapters 2 and 3 on programming paradigms.
1950’s
Fortran, 1957; imperative; first compiler, mathlike language for scientific programming, developed at IBM by John Backus, influenced most subsequent languages, enhanced versions still in use today (first programming language learned by the author in 1974)
Lisp [121,122,145,182], 1958; mix of imperative and functional features; innovations include being homoiconic (i.e., code and data have same format), extensive use of recursion, syntactic macros, automatic storage management, higherorder functions; related to Church’s lambda calculus theory, developed at MIT by John McCarthy, influenced most subsequent languages/research, enhanced versions still in use today
Algol, 1958, 1960; imperative; innovations included nested block structure, lexical scoping, use of BNF to define syntax, callbyname parameter passing; developed by an international team from Europe and the USA, influenced most subsequent languages
COBOL, 1959; imperative; focus on business/accounting programming, decimal arithmetic, record data structures, key designer Grace Hopper, still in use today (third language learned by instructor in late 1975)
1960’s
Simula; 1962, 1967; imperative; original purpose for discreteevent simulation, developed in Norway by OleJohan Dahl and Kristen Nygaard, Simula 67 is first objectoriented language (in Scandinavian school of objectoriented languages), Simula 67 influenced subsequent objectoriented languages
Snobol, 1962; imperative; string processing, patterns as firstclass data, backtracking on failure, developed at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky
PL/I, 1964; imperative; IBMdesigned language to merge scientific (Fortran), business (COBOL), and systems programming (second language learned by the instructor in early 1975)
BASIC, 1964; imperative; simple language developed for interactive computing in early timesharing and microcomputer environments, developed at Dartmouth College by John G. Kemeny and Thomas E. Kurtz
Algol 68, 1968; imperative; ambitious and rigorously defined successor to Algol 60; designed by international team, greatly influenced computing science theory and subsequent language designs, but not widely or fully implemented because of its complexity
1970’s
Pascal, 1970; imperative; simplified Algol family language designed by Niklaus Wirth (Switzerland) because of frustration with complexity of Algol 68, structured programming, onepass compiler, important for teaching in 1980s and 1990s, PascalP System virtual machine implemented on many early microcomputers (Pascal used by UM CIS in CS1 and CS2 until 1999)
Prolog [33,163], 1972; logic (relational); first and most widely used logic programming language, originally developed by a team headed by Alain Colmerauer (France), rooted in firstorder logic, most modern Prolog implementations based on the Edinburgh dialect (which ran on the Warren Abstract Machine), used extensively for artificial intelligence research in Europe, influenced subsequent logic languages and also Erlang
C, 1972; imperative; systems programming language for Unix operating system, widely used today; developed by Dennis Ritchie at AT&T Bell Labs, influenced many subsequent languages (first used by the author in 1977)
Smalltalk [84], 1972; imperative objectoriented; groundup objectoriented programming language, messagepassing between objects (in American school of objectoriented languages), extensive GUI development environment; developed by Alan Kay and others at Xerox PARC, influenced many subsequent objectoriented languages and user interface approches
ML, 1973; mostly functional; polymorphic type system on top of Lisplike language, pioneering statically typed functional programming, algebraic data types, module system; developed by Robin Milner at the University of Edinburgh as the “meta language” for a theoremproving system, influenced subsequent functional programming languages, modern dialects include Standard ML (SML), CAML, and OCAML
Scheme [81,82,183], 1975; mixed functional and imperative; minimalist dialect of Lisp with lexical scoping, tail call optimization, firstclass continuations; developed by Guy Steele and Gerald Jay Sussman at MIT, influenced subsequent languages/research
Icon, 1977; imperative; structured programming successor to Snobol, uses goaldirected execution based on success or failure of expressions; developed by a team led by Ralph Griswold at the University of Arizona
1980’s
C++, 1980; imperative and objectoriented; C with Simulalike classes; developed by Bjarne Stroustrup (Denmark)
Ada, 1983; imperative and modular; designed by US DoDfunded committee as standard language for military applications, design led by Jean Ichbiah and a team in France, statically typed, block structured, modular, synchronous message passing, objectoriented extensions in 1995 (instructor studied this language while working in the military aerospace industry 198083)
Eiffel, 1985; imperative objectoriented language; designed with strong emphasis on software engineering concepts such as design by contract and commandquery separation; developed by Bertrand Meyer (France)
Objective C, 1986; imperative objectoriented; C with Smalltalklike messaging; developed by Brad Cox and Tom Love at Stepstone, selected by Steve Jobs’ NeXT systems, picked up by Apple when NeXT absorbed, key language for MacOS and iOS
Erlang, 1986; functional and concurrent; messagepassing concurrency on functional programming base (actors), faulttolerant/realtime systems, dynamic typing, virtual machine, originally used in realtime telephone switches; developed by Joe Armstrong, Robert Virding, and Mike Williams at Ericsson (Sweden)
Self [158,175], 1986; imperative prototypebased; dialect of Smalltalk, first prototypebased language, used virtual machine with justintime compilation (JIT); developed by David Ungar and Randall Smith while at Xerox PARC, Stanford University, and Sun Microsystems, language influenced JavaScript and Lua, JIT influenced Java HotSpot JIT development
Perl, 1987; imperative; dynamic programming language originally focused on providing powerful textprocessing facilities based around regular expressions; developed by Larry Wall
1990’s
Haskell [120,173,179], 1990; purely functional language; nonstrict semantics (i.e., lazy evaluation) and strong static typing; developed by an international committee of functional programming researchers, widely used in research community
Python [[144];] [146]], 1991; imperative, originally objectbased; dynamically typed, multiparadigm language; developed by Guido van Rossum (Netherlands)
Ruby [149,169], 1993; imperative, objectoriented; dynamically typed, supports reflective/metaprogramming and internal domainspecific languages; developed by Yukihiro “Matz” Matsumoto (Japan), popularized by Ruby on Rails web framework, influenced subsequent languages
Lua [105,116], 1993; imperative; minimalistic language designed for embedding in any environment supporting standard C, dynamic typing, lexical scoping, firstclass functions, garbage collection, tail recursion optimization, pervasive table/metatable data structure, facilities for prototype objectoriented programming, coroutines, used as scripting language in games; developed by Roberto Ierusalimschy, Luiz Henrique de Figueiredo, and Waldemar Celes (Brazil)
R [167,181], 1993; imperative; designed for statistical computing and graphics, opensource implementation of the language S; developed by Ross Ihaka and Robert Gentleman (New Zealand), influenced programming in the data science community
Java, 1995; imperative objectoriented; statically typed, virtual machine, version 8+ has functional programming features (higherorder functions, streams); developed by Sun Microsystems, now Oracle
JavaScript, 1995 (standardized as ECMAScript); imperative and prototypebased; designed for embedding in web pages, dynamic typing, firstclass functions, prototypebased objectoriented programming, internals influenced by Scheme and Self but using a Javalike syntax; developed by Brendan Eich at Netscape in 12 days to meet a deadline, became popular quickly before language design made clean, evolving slowly because of requirement to maintain backward compatibility
PHP, 1995; imperative; serverside scripting language fordynamic web applications; originally developed by Rasmus Lerdorf (Canada), evolved organically
OCaml (originally Objective Caml), 1996; mostly functional with imperative and objectoriented features; a dialect of ML that adds objectoriented constructs, focusing on performance and practical use; developed by a team lead by Xavier Leroy (France)
2000’s
C#, 2001; imperative objectoriented programming; statically typed, language runs on Microsoft’s Common Language Infrastructure; developed by Microsoft (in response to Sun’s Java)
F#, 2002; OCaml reenvisioned for Microsoft’s Common Language Infrastructure (.Net), replaces OCaml’s object and module systems with .Net concepts; developed by a team led by Don Syme at Microsoft Research in the UK
Scala [132,151], 2003; hybrid functional and objectoriented language; runs on the Java Virtual Machine and interoperates with Java; developed by Martin Odersky’s team at EPFL in Switzerland
Groovy, 2003; imperative objectoriented; dynamically typed “scripting” language, runs on the Java Virtual Machine; originally proposed by James Strachan
miniKanren [26,27,80], 2005; relational; a family of relational programming languages, developed by Dan Friedman’s team at Indiana University, implemented as an extension to other languages (originally Scheme), most popular current usage probably in Clojure
Clojure [75,94,95], 2007; mixed functional and imperative; Lisp dialect, runs on Java Virtual Machine, Microsoft Common Language Runtime, and JavaScript platform, emphasis on functional programming, concurrency (e.g., software transactional memory), and immutable data structures; developed by Rich Hickey
2010’s
Idris [18,19], 2011 (1.0 release 2017); functional; eagerly evaluated, Haskelllike language with dependent types, incorporating ideas from proof assistants (e.g., Coq), intended for practical programming; developed by Edwin Brady (UK)
Julia, 2012 (1.0 release 2018); dynamic programming language designed to address highperformance numerical and scientific programming, intended as a modern replacement for MATLAB, Python, and R
Elixir [68,168], 2012 (1.0 release 2014); functional concurrent programming language; dynamic strong typing, metaprogramming, protocols, Erlang actors, runs on Erlang Virtual Machine, influenced by Erlang, Ruby, and Clojure; developed by a team led by Jose Valim (Brazil)
Elm [60,70], 2012 (0.19.1 release October 2019); simplified, eagerly evaluated Haskelllike functional programming language that compiles to JavaScript, intended primarily for userinterface programming in a browser, supports reactivestyle programming; developed by Evan Czaplicki (original version for his senior thesis at Harvard)
Rust [110,150], 2012 (1.0 release 2015); imperative; systems programming language that incorporates contemporary language concepts and focuses on safety and performance, meant to replace C and C++; developed originally at Mozilla Research by Graydon Hoare
PureScript [79,143], 2013 (0.12 release May 2018); mostly functional; an eagerly evaluated language otherwise similar to Haskell, primarily compiles to humanreadable JavaScript; originally developed by Phil Freeman
Swift, 2014; Apple’s replacement for Objective C that incorporates contemporary language concepts and focuses on program safety; “Objective C without the C”
The evolution continues!
Computer systems, software development practices, and programming languages have evolved considerably since their beginnings in the 1940s and 1950s. Contemporary languages build on many ideas that first emerged in the early decades of programming languages. But they mix the enduring ideas with a few modern innovations and adapt them for the changing circumstances.
This textbook explores both programming and programming language organization with the following approach:
emphasize important concepts and techniques that have emerged during the decades since the 1940s
teach functional and modular programming primarily using the language Haskell, a language that embodies many of the important concepts
explore the design and implementation of programming languages by building interpreters for simple languages
Chapters 2 and 3 explore the concept of programming paradigms.
Choose some programming language not discussed above and investigate the following issues.
Repeat the previous exercise for some other language.
In Summer and Fall 2016, I adapted and revised much of this work in from my previous materials:
Evolving Computer Hardware Affects Programming Languages from my notes Effect of Computing Hardware Evolution on Programming Languages, which were based on a set of unscripted remarks I made in the Fall 2014 offering of CSci 450, Organization of Programming Languages
History of Programming Languages from my notes History of Programming Languages, which were based on a set of unscripted remarks I made in the Fall 2014 offering of CSci 450, Organization of Programming Languages. Those remarks drew on the following:
O’Reilly History of Programming Languages poster [125]
Wikipedia article on History of Programming Languages [180]
In 2017, I continued to develop this material as a part of Chapter 1, Fundamentals, of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I reorganized and expanded the previous Fundamentals chapter into four chapters for the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. These are Chapter 1, Evolution of Programming Languages (this chapter); Chapter 2, Programming Paradigms); chapter 3, ObjectBased Paradigms; and Chapter 80 (an appendix), Review of Relevant Mathematics.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
The evolution of computer hardware since the 1940s; impacts upon programming languages and their subsequent evolution.
The goals of this chapter are to:
introduce the concepts of procedural and data abstraction
examine the characteristics and concepts the primary programming paradigms, imperative and declarative (including functional and relational)
survey other paradigms such as procedural and modular programming
Programming concerns the construction of appropriate abstractions in a programming language. Before we examine programming paradigms, let’s examine the concept of 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).`
Two kinds of abstraction are of interest to computing scientists: procedural abstraction and data abstraction.
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 topdown 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 topdown 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.
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 valueresult 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 objectoriented program. Some objectoriented languages use the metaphor of messagepassing. 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.
According to Timothy Budd, a programming paradigm is “a way of conceptualizing what it means to perform computation, of structuring and organizing how tasks are to be carried out on a computer” [21:3].
Historically, computer scientists have classified programming languages into one of two primary paradigms: imperative and declarative.
This imperativedeclarative taxonomy categorizes programming styles and language features on how they handle state and how they execute programs.
In recent years, many imperative languages have added more declarative features, so the distinction between languages has become blurred. However, the concept of programming paradigm is still meaningful.
A program in the imperative paradigm has an implicit state (i.e., values of variables, program counters, etc.) that is modified (i.e., sideeffected or mutated) by constructs (i.e., commands) in the source language [101].
As a result, such languages generally have an explicit notion of sequencing (of the commands) to permit precise and deterministic control of the state changes.
Imperative programs thus express how something is to be computed. They emphasize procedural abstractions.
Consider the following Java program fragment from file Counting.java
:
int count = 0 ;
int maxc = 10 ;
while (count <= maxc) {
System.out.println(count) ;
= count + 1 ;
count }
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.
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.
A program in the declarative paradigm has no implicit state. Any needed state information must be handled explicitly [101].
A program is made up of expressions (or terms) that are evaluated rather than commands that are executed.
Repetitive execution is accomplished by recursion rather than by sequencing.
Declarative programs express what is to be computed (rather than how it is to be computed).
The declarative paradigm is often divided into two types: functional (or applicative) and relational (or logic).
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).
Consider the following Haskell code from file Counting.hs
:
counter :: Int > Int > String
counter count maxc  count <= maxc = show count ++ "\n"
++ counter (count+1) maxc
 otherwise = ""
This fragment is similar to the Java fragment above. This Haskell
code defines a function counter
(i.e., a procedural abstraction) that takes two integer arguments, count
and maxc
, and returns a string consisting
of a sequence of lines with the integers from count
to maxc
such that each would be printed
on a separate line. (It does not print the string, but it inserts a
newline character at the end of each line.)
In the evaluation (i.e., “execution”) of a function call, Programming
for the {Newton}: Software Development with {NewtonScript}counter
references the values
of count
and maxc
corresponding to the explicit
arguments of the function call. These values are not changed during the
evaluation of that function call. However, the values of the arguments
can be changed as needed for a subsequent recursive call of
counter
.
We call the state of counter
explicit because it is passed in arguments of the function
call. These parameters are immutable (i.e., their values cannot
change) within the body of the function. That is, any reference to count
or maxc
within a call gets the same
value.
In a pure functional language like Haskell, the names like count
and maxc
are said to be referentially
transparent. In the same context (such as the body of the
function), they always have the same value. A name must be defined
before it is used, but otherwise the order of evaluation of the
expressions within a function body does not matter; they can even be
evaluated in parallel.
There are no “loops”. The functional paradigm uses recursive calls to carry out a task repeatedly.
As we see in later chapters, referential transparency is probably the most important property of functional programming languages. It underlies Haskell’s evaluation model (Chapter 8). It also underlies the ability to state and prove “laws” about Haskell programs (e.g., Chapters 25 and 26). Haskell programmers and Haskell compilers can use the “mathematical” properties of the programs to transform programs that are more efficient.
The above Haskell fragment does not really carry out any actions; it
just defines a mapping between the arguments and the return value. We
can “execute” the counter
function above with the arguments 0 and 10 with the following IO
program.
= do
main putStrLn (counter 0 10)
By calling the main
function
from the ghci
interpreter,
we get the same displayed output as the Java program.
Haskell separates pure computation (as illustrated by function counter
) from computation that has
effects on the environment such as input/output (as illustrated by IO
function
main
).
In most programming languages that support functional programming, functions are treated as firstclass values. That is, like other data types, functions can be stored in data structures, passed as arguments to functions, and returned as the results of functions. (The implementation technique for firstorder functions usually involves creation of a lexical closure holding the function and its environment.)
In some sense, functional languages such as Haskell merge the concepts of procedural and functional abstraction. Functions are procedural abstractions, but they are also data.
A function that can take functions as arguments or return functions in the result is called a higherorder function. A function that does not take or return functions is thus a firstorder function. Most imperative languages do not fully support higherorder functions.
The higherorder functions in functional programming languages enable regular and powerful abstractions and operations to be constructed. By taking advantage of a library of higherorder functions that capture common patterns of computation, we can quickly construct concise, yet powerful, programs.
Purely functional languages include Haskell, Idris, Miranda, Hope, Elm, and Backus’s FP.
Hybrid functional languages with significant functional subsets include Scala, F#, OCaml, SML, Erlang, Elixir, Lisp, Clojure, and Scheme.
Mainstream imperative languages such as Java (beginning with version 8), C#, Python, Ruby, Groovy, Rust, and Swift have recent feature extensions that make them hybrid languages as well.
The Scala [132,151] program CountingFun.scala
is equivalent to
the above Haskell program.
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.
Consider the following Prolog [33] code from file Counting.pl
.
In particular, this code runs on the SWIProlog interpreter [163].
X,Y,S) : count(X,Y,R), atomics_to_string(R,'\n',S).
counter(
X,X,[X]).
count(X,Y,[]) : X > Y.
count(X,Y,[XRs]) : X < Y, NX is X+1, count(NX,Y,Rs). count(
This fragment is somewhat similar to the Java and Haskell fragments
above. It can be used to generate a string with the integers from X
to Y
where each
integer would be printed on a separate line. (As with the Haskell
fragment, it does not print the string.)
This program fragment defines a database consisting of four clauses.
The clause
X,X,[X]). count(
defines a fact. For any variable value X
and list
[X]
consisting of the single value X
, count(X,X,[X])
is asserted to be true.
The other three clauses are rules. The lefthandside of
:
is
true if the righthandside is also true. For example,
X,Y,[]) : X > Y. count(
asserts that
X,Y,[]) count(
is true when X > Y
.
The empty brackets denote an empty list of values.
As a logic or relational language, we can query the database for any missing components. For example,
1,1,Z). count(
yields the value Z = [1]
.
However,
X,1,[1]). count(
yields the value X = 1
.
If more than one answer is possible, the program can generate all of
them in some nondeterministic order.
So, in some sense, where imperative and functional languages only run a computation in one direction and give a single answer, Prolog can potentially run a computation in multiple directions and give multiple answers.
As with Haskell, the above Prolog fragment does not really carry out
any computational actions; it just adds facts to the database and
defines general relationships among facts. We can “execute” the query
counter(0,10,S)
above and print the value of S
using the following
rule.
: counter(0,10,S), write(S). main
Example relational languages include Prolog, Parlog, and miniKanren.
Most Prolog implementations have imperative features such as the “cut” and the ability to assert and retract clauses.
TODO: Perhaps add a new example using miniKanren [26,27,80] in some reasonable base language–preferably Java, Python, or Scala.
As we noted, the imperativedeclarative taxonomy described above divides programming styles and language features on how they handle state and how they are executed.
The computing community often speaks of other paradigms—procedural, modular, objectoriented, concurrent, parallel, languageoriented, scripting, reactive, and so forth. The definitions of these “paradigms” may be quite fuzzy and vary significantly from one writer to another.
Sometimes a term is chosen for “marketing” reasons—to associate a language with some trend even though the language may be quite different from others in that paradigm—or to make a language seem different and new even though it may not be significantly different.
These paradigms tend to divide up programming styles and language features along different dimensions than the primary taxonomy described in Sections 2.4 and 2.5. Often the languages we are speaking of are subsets of the imperative paradigm.
This section briefly discusses some of these paradigms. We discuss the prominent objectbased paradigms in the next chapter.
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.
Consider the following Python [144] code from file CountingProc.py
:
# File CountingProc.py
def counter(count,maxc):
def has_more(count,maxc): # new variables
return count <= maxc
def adv():
nonlocal count # from counter
= count + 1
count while has_more(count,maxc):
print(f'{count}') # Python 3.6+ string interpolation
adv()
When called as
0,10) counter(
this imperative Python “procedure” executes similarly to the Java program fragment we examined in Section 2.4.
Python does not distinguish between procedures and functions as we
have defined them. It uses the term “function” for both. Both return
values and can have sideeffects. The value returned may be the special
default value None
.
This Python code uses procedural abstraction more extensively than
the earlier Java fragment. The Python procedure encloses the while
loop in
procedure counter
and abstracts
the loop test and incrementing operation into function has_more
and procedure adv
, respectively.
Like many procedural languages, Python uses lexical scope for variable, procedure, and function names. That is, the scope of a name (i.e., range of code in which it can be accessed) begins at the point it is defined and ends at the end of that block of code (e.g., function, class, or module).
Function has_more
and
procedure adv
are encapsulated
within counter
. They can only be
accessed inside the body of counter
after their definitions.
Parameters count
and maxc
of procedure counter
can be accessed throughout the
body of counter
unless hidden by
another variable or parameter with the same name. They are hidden within
the function has_more
, which
reuses the names for its parameters, but are accessible within procedure
adv
.
But to allow assignment to count
within the nested procedure adv
, the variable must declared as
nonlocal
in the inner procedure. Otherwise, the assignment would have created a
new variable with the name count
within the body of procedure adv
.
Languages like Python, C, Fortran, Pascal, and Lua are primarily procedural languages, although most have evolved to support other styles.
Scala [132,151] is a hybrid
objectfunctional language that enables function definitions to be
nested inside other function definitions. The procedural Scala program
CountingProc.scala
is equivalent to
the Python program above.
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.
First, let’s consider the following Python [144] code from file CountingMod.py
to illustrate use of
modules in Python programs. This module is similar to the procedural
program in the previous section.
This modular program, however, has all the functions and procedures
at the same level of the Python module (file) instead of most being
nested within procedure counter
.
The modular program also uses modulelevel variables instead of local
variables of procedure counter
.
# File CountingMod.py
= 0
count = 10
maxc
def has_more():
return count <= maxc
def adv():
global count
= count + 1
count
def counter():
while has_more():
print(f'{count}')
adv()
This module creates two modulelevel global variables count
and maxc
and defines three modulelevel
Python functions has_more
, adv
, and counter
.
The module assigns initial values to the variables. Their values can be accessed anywhere later in the module unless hidden by parameters or local variables with the same name.
Function has_more()
tests
modulelevel variables count
and
maxc
to determine whether there
are more items in the sequence.
Procedure adv()
assigns a new
value to the modulelevel variable count
. It must declare count
as global
so that
a new local variable is not created.
Variable maxc
is also mutable,
but this module does not modify its value.
Each module is a separate file that can be imported by other Python code. It introduces a separate name space for variables, functions, and other features.
For example, we can import the module above and execute counter with
the following Python code from file CountingModTest1.py
:
from CountingMod import counter
counter()
The fromimport
statement imports feature counter
(a Python function) from the module in file CountingMod.py
.
The imported name counter
can be
used without qualifying it. The other features of CountingMod
(e.g., count
and adv
) cannot be accessed.
As an alternative, we can import the module from file CountingModTest2.py
as follows:
import CountingMod
= 10
CountingMod.count = 20
CountingMod.maxc CountingMod.counter()
This code imports all the features of the module. It requires the
variables and functions to be accessed with the name prefix CountingMod.
(i.e., the module name
followed by a period). This approach enables the importing code to
modify the values of global variables in the imported module.
In this second example, the importing code can both access and modify the global variables of the imported module.
Python does not enforce the encapsulation of modulelevel variable or
function names. All names are public (i.e., can be imported to other
modules). However, programmers can, by convention, designate
modulelevel names as private by beginning the name with a single
underscore character _
. The
alternative import
above will not automatically import such
names.
For example, good modular programming practice might suggest that the
names _count
, _maxc
, _has_more()
, and _adv()
be used in the CountingMod
module above. This naming
convention would designate those as private and leave only counter()
as public.
Most modern languages support “modules” in some way. Other languages (e.g., Standard ML) provide advanced support for modules with the ability to encapsulate features and provide multiple implementations of common interfaces.
To see the flexibility of modular programs, let’s consider a variant of the above that uses two modules.
The first module—CountingModA
from file CountingModA.py
—is shown below.
# File CountingModA.py
from Arith import reset, adv, get_count, has_more
def counter():
while has_more():
= get_count()
count print(f'{count}')
adv()
CountingModA
has similar
overall functionality to the CountingMod
module in the previous
example. However, its counter
procedure uses a has_more
function, an adv
procedure, and a
new get_counter
function
implemented in a separate module named Arith
. The CountingModA
module has no modulelevel
variables and its counter
procedure has no local variables.
The second module—Arith
from
file Arith.py
—is shown below.
# File Arith.py
= 0
_start = 10
_stop = 1
_change = _start
_count
def reset(new_start, new_stop, new_change):
global _start, _stop, _change, _count
= new_start
_start = new_stop
_stop = _start
_count if new_change == 0:
print('Error: Attempt to reset increment to 0; not reset.')
else:
= new_change
_change
def adv():
global _count
= _count + _change
_count
def get_count():
return _count
def has_more():
if _change > 0:
return _count <= _stop
else:
return _count >= _stop
This module makes the modulelevel variables private to the module by convention.
By default, module Arith
generates the same arithmetic sequence as CountingMod
in the previous modular
programming example. However, it generalizes CountingMod
in the following ways:
renaming variable count
to
be _count
and variable maxc
to be _stop
replacing the constant 0
in the
initialization of variable _count
by a new variable _start
, which
is itself initialized to 0
replacing the constant 1
in the
increment of variable _count
by a
new variable _change
, which is
itself initialized to 1
adding a new function get_count
that enables a user module
(e.g., CountingModA
) to get the
current value of the _count
variable
This is called an accessor or getter function.
implementing the function has_more()
and the procedure adv()
used by module CountingModA
These argumentless public functions operate on Arith
’s private modulelevel variables
_start
, _stop
, _change
, and _count
.
adding a new procedure reset()
that enables the values of
_start
, _stop
, _change
, and _count
to be reinitialized to new
values
Now let’s consider an alternative to Arith
, the second module. Module Geom
from file Geom.py
is shown below.
# File Geom.py
= 1
_start = 100
_stop = 2
_change = _start
_count
:
def reset(new_start, new_stop, new_change)
global _start, _stop, _change, _count= new_start
_start = new_stop
_stop = start
_count if abs(new_change) <= 1:
print('Error: Attempt to set abs(_change) <= 1; not reset.')
else:
= new_change
_change
:
def adv()
global _count = _count * _change
_count
:
def get_count()return _count
:
def has_more()return _count <= _stop
Module Geom
has essentially
the same interface as Arith
, but
it generates a geometric sequence instead of an arithmetic sequence.
To use this module, the only change needed to
CountingModA.py
is to import the module Geom
instead of Arith
. This alternative is in module
CountingModG
in file CountingModG.py
.
This twolevel example illustrates the additional flexibility that modular programming can enable.
The modular Scala [132,151] program CountingMod.scala
is equivalent to
the first Python program above. The similar Scala program CountingMod2.scala
uses a Scala
trait to define the interface of the module. It is used in
manner similar to the second Python program above.
TODO: Probably should show a Java 8+ example for this. Also the Scala might need more update to be similar to new modular Python examples.
The dominant paradigm since the early 1990s has been the objectoriented paradigm. Because this paradigm is likely familiar with most readers, we examine it and related objectbased paradigms in the next chapter.
TODO: Perhaps describe a paradigm like actors and give an example in Elixir [68,168].
In this book we focus primarily on the functional paradigm—on the programming language Haskell in particular. Although languages that enable or emphasize the functional paradigm have been around since the early days of computing, much of the later interest in functional programming grew from the 1977 Turing Award lecture.
John W. Backus (December 3, 1924 – March 17, 2007) was a pioneer in research and development of programming languages. He was the primary developer of Fortran while a programmer at IBM in the mid1950s. Fortran is the first widely used highlevel language. Backus was also a participant in the international team that designed the influential languages Algol 58 and Algol 60 a few years later. The notation used to describe the Algol 58 language syntax—BackusNaur Form (BNF)—bears his name. This notation continues to be used to this day.
In 1977, ACM bestowed its Turing Award on Backus in recognition of his career of accomplishments. (This award is sometimes described as the “Nobel Prize for computer science”.) The annual recipient of the award gives an address to a major computer science conference. Backus’s address was titled “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs”.
Although functional languages like Lisp go back to the late 1950’s, Backus’s address did much to stimulate research community’s interest in functional programming languages and functional programming over the past four decades.
The next subsection gives excerpts from Backus’s Turing Award address published as the article “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs” [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 wordatatime 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 wordatattime 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 oneword 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 wordatatime 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 nonvon Neumann languages uneconomical and has limited their development. The absence of full scale, effective programming styles founded on nonvon Neumann principles has deprived designers of an intellectual foundation for new computer architectures. …
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 wpcalculus 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].
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.
This chapter (2) introduced the concepts of abstraction and programming paradigm and surveyed the imperative, declarative, functional, and other paradigms.
Chapter 3 continues the discussion of programming paradigms by examining the objectoriented and related objectbased paradigms.
The subsequent chapters use the functional programming language Haskell to illustrate general programming concepts and explore programming language design and implementation using interpreters.
This chapter used Haskell (and Scala) to illustrate the functional paradigm. Choose a language such as Java, Python, or C#. Describe how it can be used to write programs in the functional paradigm. Consider how well the language supports tail recursion.
TODO: Modify question if more examples are given in chapter.
This chapter used Python (and Scala) to illustrate the procedural paradigm. Choose a different language such as Java, C, C++, or C#. Describe how it can be used to write programs in the procedural paradigm.
TODO: Modify question if more examples are given in chapter.
This chapter used Python (and Scala) to illustrate the modular paradigm. For the same language chosen for previous exercise, describe how it can be used to write programs in the modular paradigm.
TODO: Modify question if more examples are given in chapter.
Repeat the previous two exercises with a different language.
In Summer and Fall 2016, I adapted and revised much of this work from my previous materials:
Abstraction (Section 2.2) from the “What is Abstraction?” section of my Data Abstraction notes [46], which I wrote originally for the first C++ (CSci 490) and Javabased (CSci 211) classes at UM in 1996 but expanded and adapted for other courses in later years. In the midtolate 1990s, the Data Abstraction notes drew on my study of a variety of sources (e.g., Bird and Wadler [13], Dale [61], Gries [85]; Horstmann [99,100], Liskov [119], Meyer [128], Mossenbock [129], Parnas [134], and Thomas [170])
Discussion of the primary programming paradigms (Sections 2.32.6) from Chapter 1 of my Notes on Functional Programming with Haskell [42], which drew on the taxonomy in Hudak’s survey paper [101]. In 2016, I expanded the discussion of the paradigms and included examples. This drew in part from my use and/or teaching of a variety of programming languages since my first programming course in 1974 (e.g., Fortran, Cobol, Pl/I, C, Snobol, Jovial, Ada, Pascal, Haskell, C++, Java, Ruby, Scala, Lua, Elixir, and Python).
Motivating Functional Programming (Section 2.7) from Chapter 1 of my Notes on Functional Programming with Haskell [42]. This includes a long excerpt from the influential Turing Award lecture by John Backus [6].
In 2017, I continued to develop this material as a part of Chapter 1, Fundamentals, of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I reorganized and expanded the previous Fundamentals chapter into four chapters for the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. These are Chapter 1, Evolution of Programming Languages; Chapter 2, Programming Paradigms (this chapter); Chapter 3, Objectbased Paradigms; and Chapter 80, Review of Relevant Mathematics. I added the examples on procedural and modular programming.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional separately developed materials, reformatting the document (e.g., using CSS), constructing a bibliography (e.g., using citeproc), adding crossreferences, and improving the build workflow and use of Pandoc.
In 2022, I aslo revised and expanded the modular programming example
I maintain this chapter 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.
TODO: Update
Abstraction, procedural abstraction, data abstraction, interface, procedures, functions, methods; programming language paradigm, primary paradigms (imperative, declarative, functional, relational or logic language); other paradigms (procedural, modular, objectoriented, concurrent); program state, implicit versus explicit state, execution of commands versus evaluation of expressions, mutable versus immutable data structures, side effects, sequencing, recursion, referential transparency, firstclass values, firstorder and higherorder functions, lexical scope, global versus local variables, public versus private features, information hiding, encapsulation, lexical closure; von Neumann computer, von Neumann language, worlds of expressions and statements, axiomatic semantics, weakest precondition calculus.
The imperativedeclarative taxonomy described in the previous chapter divides programming styles and language features on how they handle state and how they are executed. The previous chapter also mentioned other paradigms such as procedural, modular, objectbased, and concurrent.
The dominant paradigm since the early 1990s has been the objectoriented paradigm. Because this paradigm is likely familiar with most readers, it is useful to examine it in more detail.
Thus the goals of this chapter are to examine the characteristics of:
the objectoriented paradigm
related paradigms such as the objectbased, classbased, and prototypebased paradigms
In contemporary practice, most software engineers approach the design of programs from an objectoriented perspective.
The key idea (notion?) in object orientation is the following: The real world can be accurately described as a collection of objects that interact.
This approach is based on the following assumptions:
Describing large, complex systems as interacting objects make them easier to understand than otherwise.
The behaviors of real world objects tend to be stable over time.
The different kinds of real world objects tend to be stable. (That is, new kinds appear slowly; old kinds disappear slowly.)
Changes tend to be localized to a few objects.
Assumption 1 simplifies requirements analysis, software design, and implementation—makes them more reliable.
Assumptions 2 and 3 support reuse of code, prototyping, and incremental development.
Assumption 4 supports design for change.
The objectoriented approach to software development:
uses the same basic entities (i.e., objects) throughout the software development lifecycle
identifies the basic objects during analysis
identifies lowerlevel objects during design, reusing existing object descriptions where appropriate
implements the objects as software structures (e.g., Java classes)
maintains the object behaviors
<a name=“ObjectModel>
We discuss object orientation in terms of an object model. Our object model includes four basic components:
objects (i.e., abstract data structures)
classes (i.e., abstract data types)
inheritance (hierarchical relationships among abstract data types)
subtype polymorphism
Some writers consider dynamic binding a basic component of object orientation. Here we consider it an implementation technique for subtype polymorphism.
Now let’s consider each of four components of the object model.
For languages in the objectbased 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 nonessential characteristics of the object model.
An object must exhibit three essential characteristics:
state
operations
identity
An object is a separately identifiable entity that has a set of operations and a state that records the effects of the operations. An object is typically a firstclass entity that can be stored in variables and passed to or returned from subprograms.
The state is the collection of information held (i.e., stored) by the object.
It can change over time.
It can change as the result of an operation performed on the object.
It cannot change spontaneously.
The various components of the state are sometimes called the attributes of the object.
An operation is a procedure that takes the state of the object and zero or more arguments and changes the state and/or returns one or more values. Objects permit certain operations and not others.
If an object is mutable, then an operation may change the stored state so that a subsequent operation on that object acts upon the modified state; the language is thus imperative.
If an object is immutable, then an operation cannot change the stored state; instead the operation returns a new object with the modified state.
Identity means we can distinguish between two distinct objects (even if they have the same state and operations).
As an example, consider an object for a student desk in a simulation of a classroom.
A student desk is distinct from the other student desks and, hence, has a unique identity.
The relevant state might be attributes such as location, orientation, person using, items in the basket, items on top, etc.
The relevant operations might be statechanging operations (called mutator, setter, or command operations) such as “move the desk”, “seat student”, or “remove from basket” or might be stateobserving operations (called accessor, getter, observer, or query operations) such as “is occupied” or “report items on desktop”.
A language is objectbased if it supports objects as a language feature.
Objectbased languages include Ada, Modula, Clu, C++, Java, Scala, C#, Smalltalk, and Python 3.
Pascal (without module extensions), Algol, Fortran, and C are not inherently objectbased.
Some writers require that an object have additional characteristics, but this book considers these as important but nonessential characteristics of objects:
encapsulation
independent lifecycle
The state may be encapsulated within the object—that is, not be directly visible or accessible from outside the object.
The object may also have an independent lifecycle—that is, the object may exist independently from the program unit that created it. Its lifetime is not determined by the program unit that created it.
We do not include these as essential characteristics because they do not seem required by the object metaphor.
Also, some languages we wish to categorize as objectbased do not exhibit one or both of these characteristics. There are languages that use a modularization feature to enforce encapsulation separately from the object (or class) feature. Also, there are languages that may have local “objects” within a function or procedure.
In languages like Python 3, Lua, and Oberon, objects exhibit an independent lifecycle but do not themselves enforce encapsulation. Encapsulation may be supported by the module mechanism (e.g., in Oberon and Lua) or partly by a naming convention (e.g., in Python 3).
In C++, some objects may be local to a function and, hence, be allocated on the runtime stack. These objects are deallocated upon exit from the function. These objects may exhibit encapsulation, but do not exhibit independent lifecycles.
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 objectbased language is classbased if the concept of class occurs as a language feature and every object has a class.
Classbased languages include Clu, C++, Java, Scala, C#, Smalltalk, Ruby, and Ada 95. Ada 83 and Modula are not classbased.
At their core, JavaScript and Lua are objectbased but not classbased.
In statically typed, classbased 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.
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 toplevel class named Object
from which
all other classes derive (directly or indirectly). Scala is similar,
with the corresponding toplevel 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
interfacebased 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 classbased 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.
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 wellchosen 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 classbased language is objectoriented if class hierarchies can be incrementally defined by an inheritance mechanism and the language supports polymorphism by inheritance along these class hierarchies.
Objectoriented languages include C++, Java, Scala, C#, Smalltalk, and Ada 95. The language Clu is classbased, but it does not include an inheritance facility.
Other objectoriented languages include Objective C, Object Pascal, Eiffel, and Oberon 2.
Now let’s consider the objectoriented paradigm more concretely. First, let’s review what we mean by an objectoriented language. A language is:
objectbased if it supports objects that satisfy the three essential characteristics (state, operations, and identity) as a language feature
classbased if it is objectbased, has the concept of class as a language feature, and assigns every object to a class
objectoriented if it is classbased, can define class hierarchies incrementally using an inheritance mechanism, and supports polymorphism by inheritance along these class hierarchies
A classbased language is objectoriented if class hierarchies can be incrementally defined by an inheritance mechanism and the language supports polymorphism by inheritance along these class hierarchies.
TODO: This example mostly illustates classbased 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, objectoriented, 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
objectoriented 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.
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.)
Python 3 classes do not normally have explicit constructors, but
we often define an initialization method which has the special name
__init__
.
Unlike objectoriented 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
.
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
).
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.)
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
.
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.
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.
= CountingOO(0,10)
ctr 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.
= Times2(1,10)
ctr2 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
.
The program CountingOO.scala
is an
objectoriented Scala [131,151] program similar to
the Python version given above.
Classes and inheritance are not the only way to support relationships among objects in objectbased languages. Another approach of growing importance is the use of prototypes.
A prototypebased 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 classbased approach.
In a classbased 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 classbased 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 prototypebased 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 prototypebased 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
parttime, 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, classbased inheritance and polymorphism, some languages exhibit prototypebased 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
prototypebased languages. (Package prototype.py
can also
make Python behave in a prototypebased manner.)
Let’s look at Lua as a prototypebased 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.
Lua is a dynamically typed, multiparadigm language [105,116]. The language designers stress the following design principles [117]:
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 higherlevel 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 userwritten 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 metamechanisms for implementing features, instead of providing a host of features directly in the language. For example, although Lua is not a pure objectoriented language, it does provide metamechanisms for implementing classes and inheritance. Lua’s metamechanisms 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:
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 prototypebased paradigm as illustrated in the next section.
As in Python 3, Lua requires that the receiver object be passed as an argument to objectbased function and procedure calls. By convention, it is passed as the first argument, as shown below.
.method(obj, other_arguments) obj
Lua has a bit of syntactic sugar—the :
operator—to make
this more convenient. The following Lua expression is equivalent to the
above.
:method(other_arguments) obj
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).
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 or {}  (5)
mixin local obj = { __index = self }  (4)
for k, v in pairs(mixin) do  (5)
if k ~= "__index" then
[k] = v
objend
end
return setmetatable(obj,obj)  (6,7)
end
function CountingPB:has_more(c,m)  (2)
return c <= m
end
function CountingPB:adv()  (2)
.count = self.count + 1
selfend
function CountingPB:counter()  (2)
while self:has_more(self.count,self.maxc) do
print(self.count)
:adv()
selfend
end
return CountingPB  (3)
The following notes explain the numbered steps in the above code.
Create module object CountingPB
as a
Lua table with default values for data attributes count
and maxc
. This object is also the toplevel
prototype object.
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.
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:
Creates the clone initially as a table with only the __index
set to the
object that called new
(i.e., the
receiver object self
).
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.
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
.
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:
= CountingPB:new({count = 0, maxc = 10}) x
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:
= x:new({count = 10, maxc = 15}) y
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:
= y:new( { maxc = 400,
z = function (self,c,m)
has_more return c ~= 0 and math.abs(c) <= math.abs(m)
end,
= function(self)
adv .count = self.count * 2
selfend,
= function(self) print(self.msg) end
bye = "GoodBye!" } ) msg
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
GoodBye!
The Lua source code for this example is in file CountingPB.lua
. The example calls are
in file CountingPB_Test.lua
.
How does the prototypebased (PB) paradigm compare with the objectoriented (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 lowerlevel 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.
In Chapters 2 and 3 (this chapter), we explored various programming paradigms.
In Chapter 4, we begin examining Haskell, looking at our first simple programs and how to execute those programs with the interactive interpreter.
In subsequent chapters, we look more closely at the concepts of type introduced in this chapter and abstraction introduced in the previous chapter.
This chapter used Python 3 to illustrate the objectoriented
paradigm. Choose a language such as Java, C++, or C#. Describe how it
can be used to write programs in the objectoriented paradigm. Show the
CountingOO
example in the chosen
language.
C is a primarily procedural language. Describe how C can be used
to implement objectbased programs. Show the CountingOO
example in the chosen
language.
Beginning in Summer 2016 and continuing through Fall 2018, I adapted and revised much of this chapter from my previous course materials:
I adapted the ObjectOriented programming paradigm section from my notes Introduction to Object Orientation [52], which I wrote originally for the first C++ (CSci 490) and Javabased (CSci 211) classes at UM in 1996 but expanded and adapted for other courses. These notes—and my approach to objectoriented design and programming in general—were influenced by my study of works by Horstmann [99,100], Budd [22,23], Meyer [128], Thomas [170], WirfsBrock [224,225], Beck [11], Bellin [12], the “Gang of Four” [83], Buschmann [25], Fishwick [74], Johnson [106], Schmid [[154]; Schmid1999a], and many other sources (lost in the mists of time).
Note: In particular, chapters 36 of Horstmann’s C++ book [99]—on “Implementing Classes”, “Interfaces”, “ObjectOriented Design”, and “Invariants”—considerably influenced my views on objectoriented design and programming as I was learning the approach. Similarly, the first edition of Horstmann and Cornell’s Core Java [100] influenced my approach to OOP in Java.
I expanded the Prototypebased programming paradigm section from my 2016 draft notes [43] and Lua example [44] on that topic. These notes and example were influenced by Craig [38], Ierusalimschy [105], Ungar [175], and other sources (e.g., the Lua website [116] and the Wikipedia article “Prototypebased Programming” [211]) and by my experiences developing and my teaching Luabased courses.
Note: I chose Lua instead of Javascript because the former is simpler and “cleaner” and could easily execute from the command line. I also had considerably more Lua programming experience. I had used it in my Software Language Engineering (CSci 658) course in the Fall 2013 and the Fall 2014 and Fall 2016 offerings of Organization of Programming Languages (CSci 450). (Initially, I planned to use Lua as the programming language for the interpreters in this textbook. However, my experiences with CSci 450 in Fall 2016 suggested that I needed more mature teaching materials for the Fall 2017 class. I decided to instead expand my relatively mature Notes on Functional Programming with Haskell [42] and redesign the interpreters to use Haskell.)
TODO: Perhaps add citation for 2013 CSCI 658 course materials? Also identify which Javascript book had influence on my thinking?
In 2017, I incorporated this material into Chapter 1, Fundamentals, of my 2017 Haskellbased programming languages textbook.
In 2018 I reorganized and expanded the previous Fundamentals chapter into four chapters for the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming (ELIFP). These are Chapter 1, Evolution of Programming Languages; Chapter 2, Programming Paradigms; Chapter 3, ObjectBased Paradigms (this chapter); and Chapter 80, Review of Relevant Mathematics.
In 2018, I added the new Python 3 [144] examples in ELIFP Chapters 2 and 3. My approach to Python 3 programming are influenced by Beazley [8], Ramalho [146], and other sources and by my experiences developing and teaching two graduate courses that used Python 3 in 2018.
In 2018, I also revised the discussion of the Lua example and incorporated it into this chapter.
I used Chapter 2 in CSci 450 in Fall 2018 but not this chapter. However, I used both chapters in my Pythonbased Multiparadigm Programming (CSci 556) course in Fall 2018.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
Object (state, operations, identity, encapsulation, independent lifecycle, mutable, immutable), objectbased language, class, type, classbased language, inheritance, subtype, interface, polymorphism, subtype polymorphism (subtyping, inclusion polymorphism, polymorphism by inheritance), dynamic binding, objectoriented language, prototype, clone, slot, delegation, prototypebased language, embeddability, Lua tables, metatables, and metamethods, function closure.
The goals of this chapter are to
introduce the definition of Haskell functions using examples
illustrate the use of the ghci
interactive
REPL (ReadEvaluatePrint Loop) interpreter
Let’s look at our first function definition in the Haskell language, a program to implement the factorial function for natural numbers.
The Haskell source file Factorial.hs
holds the Haskell
function definitions for this chapter. The test script is in source file
TestFactorial.hs
; it is discussed
further in Chapter 12 on
testing of Haskell programs.
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’$(n1)$, 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’$(n1)$. 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$.
fact1
One way to translate the recursive definition fact’ into Haskell is the following:
fact1 :: Int > Int
= if n == 0 then
fact1 n 1
else
* fact1 (n1) n
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 builtin 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 64bits on most current
processors), but it is guaranteed to have the range of at least a
30bit, 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 ifthenelse
expression. This kind of expression has the form
if
conditionthen
expression1else
expression2
where
condition is a Boolean expression, that is, an expression of Haskell type
Bool
, which has eitherTrue
orFalse
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 ifthenelse
expression in fact1
yields the
value 1
if argument n
has the value 0
(i.e.,
n == 0
)
and yields the value n * fact1 (n1)
otherwise.
The else
clause
includes a recursive application of fact1
. The whole expression (n1)
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 (n1)
expression is nested inside the else
clause of
the ifthenelse
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
+ y x
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
.
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 (n1)
Function fact2
is equivalent
to the fact1
. Haskell evaluates
the guards in a toptobottom order. The otherwise
guard always succeeds; thus it’s use above is similar to the trailing
else
clause on the ifthenelse
expression used in fact1
.
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
0 = 1
fact3 = n * fact3 (n1) fact3 n
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 toptobottom 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 (n1)
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' (n1)
 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.
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
listgenerating expression [1..n]
to define a solution that is like the function fact:
fact5 :: Int > Int
= product [1..n] fact5 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.
Chapter 12 discusses testing
of the Factorial module designed in this chapter. The test script is TestFactorial.hs
.
See the Glasgow Haskell Compiler Users Guide [92] for information on the Glasgow Haskell Compiler (GHC) and its use.
GHCi is an environment for using GHC interactively. That is, it is a REPL (ReadEvaluatePrintLoop) command line interface using Haskell. The “Using GHCi” chapter [93] of the GHC User Guide [92] describes its usage.
Below, we show a GHCi session where we load source code file (module)
Factorial.hs
and apply the factorial
functions to various inputs. The instructor ran this in a Terminal
session on an iMac running macOS 10.13.4 (High Sierra) with ghc
8.4.3
installed.
Start the REPL.
bash3.2$ ghci
GHCi, version 8.4.3: http://www.haskell.org/ghc/ :? for help
Load module Fact
that
holds the factorial function definitions. This assumes the
Factorial.hs
file is in the current directory. The
load
command can be abbreviated as just
:l
.
Prelude> :load Factorial
1 of 1] Compiling Factorial ( Factorial.hs, interpreted )
[Ok, one module loaded.
Inquire about the type of fact1
.
*Factorial> :type fact1
fact1 :: Int > Int
Apply function fact1
to
7, 0, 20, and 21. Note that the factorial of 21 exceeds the Int
range.
*Factorial> fact1 7
5040
*Factorial> fact1 0
1
*Factorial> fact1 20
2432902008176640000
*Factorial> fact1 21
4249290049419214848
Apply functions fact2
,
fact3
, fact4
, and fact5
to 7.
*Factorial> fact2 7
5040
*Factorial> fact3 7
5040
*Factorial> fact4 7
5040
*Factorial> fact5 7
5040
Apply functions fact1
,
fact2
, and fact3
to 1. All go into an infinite
recursion, eventually terminating with an error when the runtime stack
overflows its allocated space.
*Factorial> fact1 (1)
*** Exception: stack overflow
*Factorial> fact2 (1)
*Factorial> fact3 (1)
*** Exception: stack overflow
Apply functions fact4
and
fact4'
to 1. They quickly
return with an error.
*Factorial> fact4 (1)
*** Exception: Factorial.hs:(54,1)(56,29):
Nonexhaustive patterns in function fact4
*Factorial> fact4' (1)
*** Exception: fact4' called with negative argument
CallStack (from HasCallStack):
error, called at Factorial.hs:64:17 in main:Factorial
Apply function fact5
to
1. It returns a 1 because it is defined for negative integers.
*Factorial> fact5 (1)
1
Set the +s
option to get information about the time
and space required and the +t
option to get the type of the
returned value.
*Factorial> :set +s
*Factorial> fact1 20
2432902008176640000
0.00 secs, 80,712 bytes)
(*Factorial> :set +t
*Factorial> fact1 20
2432902008176640000
it :: Int
0.05 secs, 80,792 bytes)
(*Factorial> :unset +s +t
*Factorial> fact1 20
2432902008176640000
Exit GHCi.
:quit
Leaving GHCi.
Suppose we had set the environment variable EDITOR
to our
favorite text editor in the Terminal window. For example, on a MacOS
system, your instructor might give the following command in shell (or in
a startup script such as .bash_profile
):
export EDITOR=Aquamacs
Then the :edit
command within GHCi allows us to edit the
source code. We can give a filename or default to the last file
loaded.
:edit
Or we could also use a :set
command to set the editor
within GHCi.
:set editor Aquamacs
...
:edit
See the Glasgow Haskell Compiler (GHC) User’s Guide [92] for more information about use of GHC and GHCi.
In this chapter (4), we looked at our first Haskell functions and how to execute them using the Haskell interpreter.
In Chapter 5, we continue our exploration of Haskell by examining its builtin types.
The Haskell source module Factorial.hs
gives the factorial
functions used in this chapter. The test script in source file TestFactorial.hs
is discussed further
in Chapter 12 on testing of
Haskell programs.
Reimplement functions fact4
and fact5
with type Integer
instead of Int
. Integer
is an
unbounded precision integer type (discussed in the next chapter). Using
ghci
, execute these functions for values 1, 7, 20, 21, and
50 using ghci
.
Develop both recursive and iterative (looping) versions of a factorial fuunction in an imperative language (e.g., Java, C++, Python 3, etc.)
In Summer 2016, I adapted and revised much of this work in from Chapter 3 of my Notes on Functional Programming with Haskell [42] and incorporated it into Chapter 2, Basic Haskell Functional Programming, of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I divided the previous Basic Haskell Functional Programming chapter into four chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. Previous sections 2.12.3 became the basis for new Chapter 4, First Haskell Programs (this chapter); previous Section 2.4 became Section 5.3 in the new Chapter 5, Types; and previous sections 2.52.7 were reorganized into new Chapter 6, Procedural Abstraction, and Chapter 7, Data Abstraction.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
TODO: Update
Factorials, function definition and application, recursion, function
domains, error
, if
, guards,
basic types (Int
, Integer
, Bool
, library
(Prelude) functions, REPL, ghci
commands and use.
The goals of this chapter are to:
examine the general concepts of type systems
explore Haskell’s builtin types
The term type tends to be used in many different ways in programming languages. What is a type?
The chapter on objectbased paradigms discusses the concept of type in the context of objectoriented languages. This chapter first examines the concept more generally and then examines Haskell’s builtin types.
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.
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.
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 frontend 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
userdefined classes) often require explicit runtime checks or
coercions.
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.
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:
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.
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
userdefined 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.
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 objectoriented programming community often refers to inheritancebased 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.
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 objectoriented 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.
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, objectoriented 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.
The type system is an important part of Haskell; the compiler or interpreter uses the type information to detect errors in expressions and function definitions. To each expression Haskell assigns a type that describes the kind of value represented by the expression.
Haskell has both builtin types (defined in the language or its standard libraries) and facilities for defining new types. In the following we discuss the primary builtin types. As we have seen, a Haskell type name begins with a capital letter.
In this textbook, we sometimes refer to the types Int
, Float
, Double
, Bool
, and
Char
as
being primitive because they likely have direct support in the
host processor’s hardware.
Int
and Integer
The Int
data type
is usually an integer data type supported directly by the host processor
(e.g., 32 or 64bits on most current processors), but it is guaranteed
to have the range of at least a 30bit, 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 twoargument 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 twoargument functions min
and max
, which
return the minimum and maximum of the two arguments, respectively.
Twoarguments 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
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.0e2
,
5.0e2
.
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.
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
True b = b
myAnd False _ = False myAnd
Above the pattern _
is a
wildcard that matches any value but does not bind a value that can be
used on the righthandside 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.
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'
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 firstclass objects. They can be arguments or results of other functions or be components of data structures. Multiargument 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.
(t1,t2,...,tn)
If t1
, t2
,
$\cdots$,
tn
are types, where n
is finite and
n >= 2
, then is a type consisting of ntuples
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
= (r,i)` makeComplex 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.
[t]
The primary builtin 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 commaseparated 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.
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 twoelement 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.
In later chapters, we examine other important Haskell type concepts such as userdefined algebraic data types and type classes.
In this chapter (5), we examined general type systems concepts and explored Haskell’s builtin types.
For a similar presentation of the types in the Python 3 language, see reference [45].
In Chapters 6 and 7, we examine methods for developing Haskell programs using abstraction. We explore use of topdown stepwise refinement, modular design, and other methods in the context of Haskell.
For each of the following exercises, develop and test a Haskell function or set of functions.
Develop a Haskell function sumSqBig
that takes three Double
arguments and yields the sum of the squares of the two larger
numbers.
For example, (sumSqBig 2.0 1.0 3.0)
yields 13.0
.
Develop a Haskell function prodSqSmall
that takes three Double
arguments and yields the product of the squares of the two smaller
numbers.
For example, (prodSqSmall 2.0 4.0 3.0)
yields 36.0
.
Develop a Haskell function xor
that takes two Booleans and yields
the “exclusiveor” of the two values. An exclusiveor operation yields
True
when exactly one of its arguments is True
and
yields False
otherwise.
Develop a Haskell Boolean function implies
that takes two Booleans p
and q
and yields the Boolean result p
$\Rightarrow$
q
(i.e., logical implication).
That is, if p
is True
and q
is False
, then
the result is False
;
otherwise, the result is True
.
Note: This function is sometimes called nand
.
Develop a Haskell Boolean function div23n5
that takes an Int
and yields
True
if
and only if the integer is divisible by 2 or divisible by 3, but is not
divisible by 5.
For example, (div23n5 4)
,
(div23n5 6)
,
and (div23n5 9)
all yield True
and (div23n5 5)
,
(div23n5 7)
,
(div23n5 10)
,
(div23n5 15)
,
(div23n5 30)
all yield False
.
Develop a Haskell function notDiv
such that notDiv n d
yields True
if and
only if integer n
is not
divisible by d
.
For example, (notDiv 10 5)
yields False
and
(notDiv 11 5)
yields True
.
Develop a Haskell function ccArea
that takes the
diameters of two concentric circles (i.e., with the same center
point) as Double
values
and yields the area of the space between the circles. That is, compute
the area of the larger circle minus the area of the smaller circle.
(Hint: Haskell has a builtin constant pi
.)
For example, (ccArea 2.0 4.0)
yields approximately 9.42477796
.
Develop a Haskell function mult
that takes two natural
numbers (i.e., nonnegative integers in Int
) and
yields their product. The function must not use the multiplication
(*
) or
division (div
)
operators. (Hint: Multiplication can be done by repeated
addition.)
Develop a Haskell function addTax
that takes two Double
values
such that addTax c p
yield c
with a sales tax of p
percent added.
For example, (addTax 2.0 9.0)
yields 2.18
.
Also develop a function subTax
that is the inverse of addTax
. That is, (subTax (addTax c p) p)
yields c
.
For example, (subTax 2.18 9.0) = 2.0
.
The time of day can be represented by a tuple (hours,minutes,m)
where hours
and minutes
are Int
values
with 1 <= hours <= 12
and 0 <= minutes <= 59
,
and where m
is either the string
value "AM"
or "PM"
.
Develop a Boolean Haskell function comesBefore
that takes two timeofday
tuples and determines whether the first is an earlier time than the
second.
A day on the calendar (usual Gregorian calendar [217] used in
the USA) can be represented as a tuple with three Int
values
(month,day,year)
where the year
is a positive integer, 1 <= month <= 12
,
and 1 <= day <= days_in_month
.
Here days_in_month
is the number
of days in the the given month
(i.e., 28, 29, 30, or 31) for the given year
.
Develop a Boolean Haskell function validDate d
that takes a date tuple
d
and yields True
if and
only if d
represents a valid
date.
For example, validDate (8,20,2018)
and validDate (2,29,2016)
yield True
and validDate (2,29,2017)
and validDate (0,0,0)
yield False
.
Note: The Gregorian calendar [217] was introduced by Pope Gregory of the Roman Catholic Church in October 1582. It replaced the Julian calendar system, which had been instituted in the Roman Empire by Julius Caesar in 46 BC. The goal of the change was to align the calendar year with the astronomical year.
Some countries adopted the Gregorian calendar at that time. Other countries adopted it later. Some countries may never have adopted it officially.
However, the Gregorian calendar system became the common calendar used worldwide for most civil matters. The proleptic Gregorian calendar [218] extends the calendar backward in time from 1582. The year 1 BC becomes year 0, 2 BC becomes year 1, etc. The proleptic Gregorian calendar underlies the ISO 8601 standard used for dates and times in software systems [219].
Develop a Haskell function roman
that takes an Int
) in the
range from 0 to 3999 (inclusive) and yields the corresponding Roman
numeral [220] as a string (using capital
letters). The function should halt with an appropriate error
messages
if the argument is below or above the range. Roman numerals use the
symbols shown in Table 5.1 and are
combined by addition or subtraction of symbols.
Roman  $=$  Decimal 

I  1  
V  5  
X  10  
L  50  
C  100  
D  500  
M  1000 
For the purposes of this exercise, we represent the Roman numeral
for 0 as the empty string. The Roman numerals for integers 120 are
I
, II
, III
, IV
,
V
, VI
, VII
, VIII
,
IX
, X
, XI
, XII
,
XIII
, XIV
, XV
, XVI
,
XVII
, XVII
, XIX
, and
XX
. Integers 40, 90, 400, and 900 are XL
,
XC
, CD
, and CM
.
Develop a Haskell function
minf :: (Int > Int) > Int
that takes a function g
and
yields the smallest integer m
such that 0 <= m <= 10000000
and g m == 0
.
It should throw an error
if there
is no such integer.
In Summer 2016, I adapted and revised the discussion Surveying the Basic Types from chapter 5 of my Notes on Functional Programming with Haskell [42]. In 2017, I incorporated the discussion into Section 2.4 in Chapter 2 Basic Haskell Functional Programming of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I divided the previous Basic Haskell Functional Programming chapter into four chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming [54]. Previous sections 2.12.3 became the basis for new Chapter 4, First Haskell Programs; previous Section 2.4 became Section 5.3 in the new Chapter 5, Types (this chapter); and previous sections 2.52.7 were reorganized into new Chapter 6, Procedural Abstraction, and Chapter 7, Data Abstraction.
In Spring 2018, I wrote the general Type System Concepts section as a part of a chapter that discusses the type system of Python 3 [45] to support my use of Python in graduate CSci 658 (Software Language Engineering) course.
In Summer 2018, I revised the section to become Section 5.2 in Chapter 5 of the Fall 2018 version of ELIFP [54]. I also moved the “Kinds of Polymorphism” discussion from the 2017 List Programming chapter to the new subsection “Polymorphic Operations”. This textbook draft supported my Haskellbased offering of the core course CSci 450 (Organization of Programming Languages).
The type concepts discussion draws ideas from various sources:
my general study of a variety of programming, programming language, and software engineering over three decades [13,20,22,99–101,104,119,128,131,134,135,156,157,171].
the Wikipedia articles on the Liskov Substitution Principle [205], Polymorphism [206], Ad Hoc Polymorphism [208], Parametric Polymorphism [209], Subtyping [210], and Function Overloading [207]
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
In 2022, I also added some discussion on the functions div
, quot
, mod
, rem
, fromIntegral
,
and show
because of their usefulness in the exercises in this and later
chapters.
I maintain this chapter 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.
Type, subtype, Liskov Substitution Principle, types of constants,
variables, and expressions, static vs. dynamic types, nominal
vs. structural types, polymorphic operations (ad hoc, overloading,
subtyping, parametric/generic), early vs. late binding, compile time
vs. runtime, polymorphic variables, basic Haskell types (Int
, Integer
, Bool
, Char
,
functions, tuples, lists, String
), type
aliases,
library (Prelude) functions, proleptic Gregorian calendar system, Roman
numerals.
Chapter 2 introduced the concepts of procedural and data abstraction. This chapter (6) focuses on procedural abstraction. Chapter 7focuses on data abstraction.
The goals of this chapter are to:
illustrate use of procedural abstraction, in particular of the topdown, stepwise refinement approach to design
introduce modular programming using Haskell modules
As defined in Chapter 2, procedural abstraction is the separation of the logical properties of an action from the details of how the action is implemented.
In general, we abstract an action into a Haskell function that takes zero or more arguments and returns a value but does not have other effects. In later chapters, we discuss how input, output, and other effects are handled in a purely functional manner. (For example, in Chapter 10 we examine simple input and output.)
We also collect one or more functions into a Haskell module with appropriate type definitions, data structures, and local functions. We can explicitly expose some of the features and hide others.
To illustrate the development of a group of related Haskell procedural abstractions in this chapter, we use topdown stepwise refinement.
A useful and intuitive design process for a small program is to begin with a highlevel solution and incrementally fill in the details. We call this process topdown stepwise refinement. Here we introduce it with an example.
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:
Guess at the value of $y$.
If the current approximation (guess) is sufficiently close (i.e., good enough), return it and stop; otherwise, continue.
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 topdown 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:
 step 2
sqrtIter guess x  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
= average guess (x/guess) improve guess x
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
= (x + y) / 2 average x y
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
= abs (square guess  x) < 0.001 goodEnough guess x
In the above, abs
is the
builtin 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
= x * x square 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
 x >= 0 = sqrtIter 1 x sqrt' 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.
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
= do
main putStrLn (show (sqrt' 16))
putStrLn (show (sqrt' 2))
In the above Haskell code, the symbol “
” denotes
the beginning of an endofline 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,
smoketesting code is in file SqrtTest.hs
.
The program design strategy known as topdown 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 topdown stepwise refinement as follows.
Start with a highlevel 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 asyetundefined functions.
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.
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 userdefined 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, longlived, 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.
In the previous section, we developed a Haskell module. In this section, let’s consider what a module is more generally.
Software engineering pioneer David Parnas defines a module as “a work assignment given to a programmer or group of programmers” [138]. This is a software engineering view of a module.
In a programming language like Haskell, a module
is also
a program unit defined with a construct or convention. This is a
programming language view of a module.
In a programming language, each module may be stored in a separate file in the computer’s file system. It may also be the smallest external unit processed by the language’s compiler or interpreter.
Ideally, a language’s module features should support the software engineering module methods.
According to Parnas, the goals of modular design are to [134]:
enable programmers to understand the system by focusing on one module at a time (i.e., comprehensibility).
shorten development time by minimizing required communication among groups (i.e., independent development).
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 informationhiding 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 welldefined 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 objectoriented programming. However, information hiding is often oversimplified as merely hiding the data and their representations [177].
The secret of a welldesigned 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.
The secret of the Sqrt
module in
the previous section is the algorithm for computing the square root.
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.
In the Sqrt
module
defined in the previous section, the exported function sqrt' x
has the precondition:
>= 0 x
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).
Factorial
moduleConsider 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
>= 0 n
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.
It is important for an informationhiding module to have a welldefined 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.
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.
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.
Informationhiding modules and abstract interfaces enable us to design and build software systems with multiple versions. The informationhiding 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 welldefined 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.
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.
The design and implementation of informationhiding modules should be approached from two points of view simultaneously:
The clientsupplier 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 clientsupplier contract:
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).
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”.
What else should we consider in designing a good interface for an informationhiding 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 objectoriented 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 informationhiding 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.
In this chapter (6), we considered procedural abstraction and modularity in that context.
In Chapter 7, we consider data abstraction and modularity in that context.
The Haskell source code for this chapter are in files:
Sqrt.hs
for the Square Root case study
SqrtTest.hs
for (limited) “smoke
testing” of the Sqrt
module
Factorial.hs
for the factorial source
code from Chapter 4
TestFactorial.hs
is an extensive
testing module developed in Chapter 12
for the factorial
module
State preconditions and postconditions for the following internal
functions in the Sqrt
module:
sqrtIter
improve
average
goodEnough
square
Develop recursive and iterative (looping) versions of the square root function from this chapter in one or more primarily imperative languages (e.g., Java, C++, C#, Python 3, or Lua)
In Summer and Fall 2016, I adapted and revised much of this work from my previous materials:
Using TopDown Stepwise Refinement (square root module), which is based on Section 1.1.7 of Abelson and Sussman’s Structure and Interpretation of Computer Programs [1] and my example implementations of this algorithm in Scala, Elixir, and Lua as well as Haskell.
Modular Design and Programming from my Data Abstraction [46] and Modular Design [47] notes, which drew ideas over the past 25 years from a variety of sources [20,22,56,58,59,61,99,100,128,129,134,136,137,170,177].
In 2017, I continued to develop this work as sections 2.52.7 in Chapter 2, Basic Haskell Functional Programming), of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I divided the previous Basic Haskell Functional Programming chapter into four chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. Previous sections 2.12.3 became the basis for new Chapter 4, First Haskell Programs; previous Section 2.4 became Section 5.3 in the new Chapter 5, Types; and previous sections 2.52.7 were reorganized into new Chapter 6, Procedural Abstraction (this chapter), and Chapter 7, Data Abstraction. The discussion of contracts for the factorial functions was moved from the 2017 Evaluation and Efficiency chapter to this chapter.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional separately developed materials, reformatting the document (e.g., using CSS), constructing a bibliography (e.g., using citeproc), adding crossreferences, and improving the build workflow and use of Pandoc.
I maintain this chapter 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.
TODO: Update
Procedural abstraction, topdown stepwise refinement, abstract code,
termination condition for recursion, Newton’s method, Haskell module
, module
exports and imports, information hiding, module secret, encapsulation,
precondition, postcondtion, contract, invariant, interface, abstract
interface, design criteria for interfaces, software reuse, use of
Haskell modules to implement informationhiding modules, clientsupplier
contract.
Chapter 2 introduced the concepts of procedural and data abstraction. Chapter 6 focuses on procedural abstraction and modular design and programming. This chapter focuses on data abstraction. 4 The goals of this chapter are to:
illustrate use of data abstraction
reinforce and extend the concepts of modular design and programming using Haskell modules
The chapter uses the development of a rational arithmetic package to illustrate data abstraction.
As defined in Chapter 2, data abstraction is the separation of the logical properties of data from the details of how the data are represented.
In data abstraction, programmers primarily focus on the problem’s data and secondarily on its actions. Programmers first identify the key data entities and develop the programs around those and the operations needed to create and update them.
Data abstraction seeks to make a program robust with respect to change in the data.
As in Chapter 6, let’s begin the study of this design technique with an example.
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:
denom :: Rat > Int numer,
Functions numer
and denom
take a valid Haskell rational
number and return its numerator and denominator, respectively.
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
= makeRat ( numer x) (denom x)
negRat x
divRat :: Rat > Rat > Rat  (1)
addRat, subRat, mulRat,= makeRat (numer x * denom y + numer y * denom x)
addRat x y * denom y)
(denom x = makeRat (numer x * denom y  numer y * denom x)
subRat x y * denom y)
(denom x = makeRat (numer x * numer y) (denom x * denom y)
mulRat x y  (2) (3)
divRat x y  eqRat y zeroRat = error "Attempt to divide by 0"
 otherwise = makeRat (numer x * denom y)
* numer y)
(denom x
eqRat :: Rat > Rat > Bool
= (numer x) * (denom y) == (numer y) * (denom x) eqRat x y
The above code:
combines the type signatures for all four arithmetic operations into a single declaration by listing the names separated by commas
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.
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.
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)
= (0,1) zeroRat
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
0 = error ( "Cannot construct a rational number "
makeRat x ++ show x ++ "/0" )  (1)
0 _ = zeroRat
makeRat = (x' `div` d, y' `div` d)  (2)
makeRat x y where x' = (signum' y) * x  (3,4)
= abs' y
y' = gcd' x' y' d
In the definition of makeRat
,
we use features of Haskell we have not used in the previous examples.
the above code:
uses the infix ++
(read
“append”) operator to concatenate two strings
We discuss ++
in the
chapter on infix operations.
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.
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 topdown manner—first using
a symbol and then defining it.
uses type inference for local variables x'
, y'
, and d
instead of giving explicit type
definitions
These parameterless functions could be declared
d :: Int x', y',
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:
/= 0 y
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
 n == 0 = 0
signum' n  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
 n >= 0 = n
abs' 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'' (abs' x) (abs' y)
gcd' x y where gcd'' x 0 = x
= gcd'' y (x `rem` y) gcd'' x 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:
denom :: Rat > Int
numer,= x
numer (x,_) = y denom (_,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
= show (numer x) ++ "/" ++ show (denom x) showRat 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.
There are three groups of functions in this package:
the six public rational arithmetic functions negRat
, addRat
, subRat
, mulRat
, divRat
, and eqRat
the public type Rat
, constant
zeroRat
, public constructor
function makeRat
, public
selector functions numer
and
denom
, and string conversion
function showRat
the private utility functions called only by the second group, but just reimplementations of Prelude functions anyway
RationalCore
As we have seen, data type Rat
; constant
zeroRat
; functions makeRat
, numer
, denom
, and showRat
; and the functions’
preconditions and postconditions form the interface to the
data abstraction.
The data abstraction hides the information about the representation
of the data. We can encapsulate this group of functions in a
Haskell module as follows. This source code must also be in a file named
RationalCore.hs
.
module RationalCore
Rat, makeRat, zeroRat, numer, denom, showRat)
(where
 Rat,makeRat,zeroRat,numer,denom,showRat definitions
In terms of the informationhiding approach, the secret of the RationalCore
module is the rational number data representation used.
We can encapsulate the utility functions in a separate module, which would enable them to be used by several other modules.
However, given that the only use of the utility functions is within the data representation module, we choose not to separate them at this time. We leave them as local functions in the data abstraction module. Of course, we could also eliminate them and use the corresponding Prelude functions directly.
Rational
Similarly, functions negRat
,
addRat
, subRat
, mulRat
, divRat
, and eqRat
use the core data abstraction
and, in turn, extend the interface to include rational number arithmetic
operations.
We can encapsulate these in another Haskell module that imports the
module giving the data representation. This module must be in a file
named Rational1.hs
.
module Rational1
Rat, zeroRat, makeRat, numer, denom, showRat,
(
negRat, addRat, subRat, mulRat, divRat, eqRat )where
import RationalCore
 negRat,addRat,subRat,mulRat,divRat,eqRat definitions
Other modules that use the rational number package can import module
Rational1
.
The modularization described above:
enables a module to be reused in several different programs
offers robustness with respect to change
The data representation and arithmetic algorithms can change independently.
allows multiple implementations of each module as long as the public (abstract) interface is kept stable
enables understanding of one module without understanding the internal details of modules it uses
costs some in terms of extra code and execution efficiency
But that probably does not matter given the benefits above and the code optimizations carried out by the compiler.
However, the modularization does not hide the representation fully because it uses a concrete data structure—a pair of integers—to represent a rational number. In chapter 21, we see how to use a userdefined data type to hide the representation fully.
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)
= (0,1)
zeroRat
makeRat :: Int > Int > Rat
0 = error ( "Cannot construct a rational number "
makeRat x ++ show x ++ "/0" )
0 y = zeroRat
makeRat = (x,y)
makeRat x y
numer :: Rat > Int
= x' `div` d
numer (x,y) where x' = (signum' y) * x
= abs' y
y' = gcd' x' y'
d
denom :: Rat > Int
= y' `div` d
denom (x,y) where x' = (signum' y) * x
= abs' y
y' = gcd' x' y'
d
showRat :: Rat > String
= show (numer x) ++ "/" ++ show (denom x) showRat 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:
/= 0 y
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 module
s) 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
userdefined (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.
In the Rational Arithmetic example, we defined two informationhiding modules:
“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
“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” informationhiding module.
We developed one distinct Haskell module, Rational
, to
implement the “Rational” informationhiding 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 CabalInstall 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.
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
.
As we see in the rational arithmetic example, a module that provides a data abstraction must ensure that the objects it creates and manipulates maintain their integrity—always have a valid structure and state.
The RationalCore
rational number representation satisfies the Rational Representation
Property.
The RationalDeferGCD
rational number representation satisfies the Deferred Representation
Property.
These properties are invariants for those modules. An invariant for the data abstraction can help us design and implement such objects.
A logical assertion that must always be true for every “object” created by the public constructors and manipulated only by the public operations of the data abstraction.
Often, we separate an invariant into two parts.
An invariant stated in terms of the public features and abstract properties of the “object”.
A detailed invariant giving the required relationships among the internal features of the implementation of an “object”
An interface invariant is a key aspect of the abstract interface of a module. It is useful to the users of the module, as well to the developers.
In the Rational Arithmetic example, the interface invariant for the “RationalRep” abstract module is the following.
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.
/= 0 y
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.
RationalCore
We can state an implementation invariant for the RationalCore
module.
For any valid Haskell rational number r
, all the following hold:
r == (x,y)
for
some (x,y)
$\in$
Rat
y > 0
if x == 0
,
then y == 1
x
and y
are relatively prime
rational number value is $\frac{\texttt{x}}{\texttt{y}}$
The implementation invariant implies the interface invariant given
the definitions of data type Rat
and
selector functions numer
and
denom
. Constructor function
makeRat
does the work to
establish the invariant initially.
RationalDeferGCD
We can state an implementation invariant for the RationalDeferGCD
module.
For any valid Haskell rational number r
, all the following hold:
r == (x,y)
for
some (x,y)
$\in$
Rat
y /= 0
if x == 0
,
then y == 1
rational number value is $\frac{\texttt{x}}{\texttt{y}}$
The implementation invariant implies the interface invariant given
the definitions of Rat
and of the
selector functions numer
and
denom
. Constructor function
makeRat
is simple, but the
selector functions numer
and
denom
do quite a bit of work to
establish the interface invariant.
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
.
Chapter 6 examined procedural abstraction and stepwise refinement and used the method to develop a square root package.
This chapter (7) examined data abstraction and used the method to develop a rational number arithmetic package. The chapters explored concepts and methods for modular design and programming using Haskell, including preconditions, postconditions, and invariants.
We continue to use these concepts, techniques, and examples in the rest of the book. In particular:
Chapter 12 examines how to test the modules developed in this chapter.
Chapter 22 explores the data abstraction concepts and techniques in more depth. In particular, it examines a detailed case study of an abstract data type.
The next chapter, Chapter 8, examines the substitution model for evaluation of Haskell programs and explores efficiency and termination in the context of that model.
The Haskell source code for this chapter includes the following:
Two versions of a lowerlevel “RationalnRep” module that gives implementations of rational number given in the following files.
An upperlevel rational arithmetic module given in the following files.
Rational1.hs
, a variant that imports
the RationalCore
module
Rational2.hs
, a variant that imports
the RationalDeferGCD
module
For each of the following exercises, develop and test a Haskell function or set of functions.
Develop a Haskell module (or modules) for line segments on the twodimensional coordinate plane using the rectangular coordinate system.
We can represent a line segment with two points—the starting point and the ending point. Develop the following Haskell functions:
constructor newSeg
that
takes two points and returns a new line segment
selectors startPt
and
endPt
that each take a segment
and return its starting and ending points, respectively
We normally represent the plane with a rectangular
coordinate system. That is, we use two axes—an x
axis and a y
axis—intersecting at a
right angle. We call the intersection point the origin and
label it with 0 on both axes. We normally draw the x
axis horizontally and label it with
increasing numbers to the right and decreasing numbers to the left. We
also draw the y
axis vertically
with increasing numbers upward and decreasing numbers downward. Any
point in the plane is uniquely identified by its x
coordinate and y
coordinate.
Define a data representation for points in the rectangular coordinate system and develop the following Haskell functions:
constructor newPtFromRect
that takes the x
and y
coordinates of a point and returns a
new point
selectors getx
and gety
that takes a point and returns
the x
and y
coordinates, respectively
display function showPt
that takes a point and returns an appropriate String
representation for the point
Now, using the various constructors and selectors, also develop the Haskell functions for line segments:
midPt
that takes a line
segment and returns the point at the middle of the segment
display function showSeg
that takes a line segment and returns an appropriate String
representation
Note that newSeg
, startPt
, endPt
, midPt
, and showSeg
can be implemented
independently from how the points are represented.
Develop a Haskell module (or modules) for line segments that represents points using the polar coordinate system instead of the rectangular coordinate system used in the previous exercise.
A polar coordinate system represents a point in the plane by its
radial coordinate r
(i.e., the distance from the pole) and its angular
coordinate t
(i.e., the
angle from the polar axis in the reference direction). We
sometimes call r
the magnitude and t
the angle.
By convention, we align the rectangular and polar coordinate systems
by making the origin the pole, the positive portion of the x
axis the polar axis, and let the
first quadrant (where both x
and
y
are positive) be the smallest
positive angles in the reference direction. That is, with a traditional
drawing of the coordinate systems, we measure and the radial coordinate
r
as the distance from the
origin measure the angular coordinate t
counterclockwise from the positive
x
axis.
Using knowledge of trigonometry, we can convert among rectangular
coordinates (x,y)
and polar
coordinates (r,t)
using the
equations:
= r * cos(t)
x = r * sin(t)
y = sqrt(x^2 + y^2)
r = arctan2(y,x) t
Define a data representation for points in the polar coordinate system and develop the following Haskell functions:
constructor newPtFromPolar
that takes the
magnitude r
and angle t
as the polar coordinates of a point
and returns a new point
selectors getMag
and
getAng
that each take a point
and return the magnitude r
and
angle t
coordinates,
respectively
selectors getx
and gety
that return the x
and y
components of the points
(represented here in polar coordinates)
display functions showPtAsRect
and showPtAsPolar
to convert the points to
strings using rectangular and polar coordinates, respectively,
Functions newSeg
, startPt
, endPt
, midPt
, and showSeg
should work as in the previous
exercise.
Modify the solutions to the previous two linesegment module exercises to enable the line segment functions to be in one module that works properly if composed with either of the two data representation modules. (The solutions may have already done this.)
Modify the solution to the previous linesegment exercise to use the Backpack module system.
Modify the modules in the previous exercise to enable the line segment module to work with both data representations in the same program.
Modify the solution to the Rational Arithmetic example to use the Backpack module system.
State preconditions and postconditions for the functions in
abstract module Rational
.
In Summer and Fall 2016, I adapted and revised much of this work from my previous materials:
Discussion of the Rational Arithmetic modules mostly from chapter 5 of my Notes on Functional Programming with Haskell [42], from my Luabased implementations, and from section 2.1 of Abelson and Sussman’s Structure and Interpretation of Computer Programs [1].
Discussion of modular design and programming issues from my Data Abstraction [46] and Modular Design [47] notes, which drew ideas over the past 25 years from a variety of sources [20,22,56,58,59,61,99,100,128,129,134,136,137,170,177].
In 2017, I continued to develop this work as Sections 2.62.7 in Chapter 2, Basic Haskell Functional Programming, of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I divided the previous Basic Haskell Functional Programming chapter into four chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. Previous sections 2.12.3 became the basis for new Chapter 4, First Haskell Programs; previous Section 2.4 became Section 5.3 in the new Chapter 5, Types; and previous sections 2.52.7 were reorganized into new Chapter 6, Procedural Abstraction, and Chapter 7, Data Abstraction (this chapter).
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
TODO: Update
Haskell module
, module
exports and imports, module dependencies, rational number arithmetic,
data abstraction, properties of data, data representation, precondition,
postcondition, invariant, interface invariant, implementation or
representation invariant, canonical or normal forms, relatively prime,
information hiding, module secret, encapsulation, interface, abstract
interface, type inference.
This chapter (8) introduces an evaluation model applicable to Haskell programs. As in the previous chapters, this chapter focuses on use of firstorder functions and primitive data types.
The goals of this chapter (8) are to:
describe an evaluation model appropriate for Haskell programs
enable students to analyze Haskell functions to determine under what conditions they terminate normally and how efficient they are
Building on this model, Chapter 9 informally analyzes simple functions in terms of time and space efficiency and termination. Chapter 29 examines these issues in more depth.
How can we evaluate (i.e., execute) an expression that “calls” a
function like the fact1
function
from Chapter 4?
We do this by rewriting expressions using a substitution model, as we see in this chapter. This process depends upon a property of functional languages called referential transparency.
Referential transparency is probably the most important property of modern functional programming languages.
As defined in Chapter 2, referential transparency means that, within some welldefined context (e.g., a function or module definition), a variable (or other symbol) always represents the same value.
Because a variable always has the same value, we can replace the variable in an expression by its value or vice versa. Similarly, if two subexpressions have equal values, we can replace one subexpression by the other. That is, “equals can be replaced by equals”.
Pure functional programming languages thus use the same concept of a variable that mathematics uses.
However, in most imperative programming languages, a variable represents an address or “container” in which values may be stored. A program may change the value stored in a variable by executing an assignment statement. Thus these mutable variables break the property of referential transparency.
Because of referential transparency, we can construct, reason about, and manipulate functional programs in much the same way we can any other mathematical expressions. Many of the familiar “laws” from high school algebra still hold; new laws can be defined and proved for less familiar primitives and even userdefined operators. This enables a relatively natural equational style of reasoning using the actual expressions of the language. We explore these ideas further in Chapters 25, 26, and 27.
In contrast, to reason about imperative programs, we usually need to go outside the language itself and use notation that represents the semantics of the language {[41]; [85]].
For our purposes here, referential transparency underlies the substitution model for evaluation of expressions in Haskell programs.
The substitution model (or reduction model) involves rewriting (or reducing) an expression to a “simpler” equivalent form. It involves two kinds of replacements:
replacing a subexpression that satisfies the lefthand side of an equation by the righthand side with appropriate substitution of arguments for parameters
replacing a primitive application (e.g., +
or *
) by its
value
The term redex refers to a subexpression that can be reduced.
Redexes can be selected for reduction in several ways. For instance, the redex can be selected based on its position within the expression:
leftmost redex first, where the leftmost reducible subexpression in the expression text is reduced before any other subexpressions are reduced
rightmost redex first, where the rightmost reducible subexpression in the expression text is reduced before any other subexpressions are reduced
The redex can also be selected based on whether or not it is contained within another redex:
outermost redex first, where a reducible subexpression that is not contained within any other reducible subexpression is reduced before one that is contained within another
innermost redex first, where a reducible subexpression that contains no other reducible subexpression is reduced before one that contains others
We will explore these more fully in a Chapter 29. In most circumstances, Haskell uses a leftmost outermost redex first approach.
In Chapter 4, we defined
factorial function fact1
as shown below.
(The source code is in file Factorial.hs
){type=“text/plain”}.)
fact1 :: Int > Int
= if n == 0 then
fact1 n 1
else
* fact1 (n1) n
Consider the expression from else
clause in
fact1
with n
having the value 2
:
2 * fact1 (21)
This has two redexes: subexpressions 21
and fact1 (21)
.
The multiplication cannot be reduced because it requires both of its arguments to be evaluated.
A function parameter is said to be strict if the value of that argument is always required. Thus, multiplication is strict in both its arguments. If the value of an argument is not always required, then it is nonstrict.
The first redex 21
is an innermost redex. Since it is the only innermost redex, it is both
leftmost and rightmost.
The second redex fact1 (21)
is an outermost redex. Since it is the only outermost redex, it is both
leftmost and rightmost.
Now consider the complete evaluation of the expression fact1 2
using
leftmost outermost reduction steps. Below we denote the steps with
$\Longrightarrow$
and give the substitution performed between braces.
fact1 2
$\Longrightarrow$
{
replace fact1 2
using
definition }
if 2 == 0 then 1 else 2 * fact1 (21)
$\Longrightarrow$
{
evaluate 2 == 0
in condition }
if False then 1 else 2 * fact1 (21)
$\Longrightarrow$
{
evaluate if
}
2 * fact1 (21)
$\Longrightarrow$
{
replace fact1 (21)
using definition, add implicit parentheses }
2 * (if (21) == 0 then 1 else (21) * fact1 ((21)1))
$\Longrightarrow$
{
evaluate 21
in condition }
2 * (if 1 == 0 then 1 else (21) * fact1 ((21)1))
$\Longrightarrow$
{
evaluate 1 == 0
in condition }
2 * (if False then 1 else (21) * fact1 ((21)1))
$\Longrightarrow$
{
evaluate if
}
2 * ((21) * fact1 ((21)1))
$\Longrightarrow$
{
evaluate leftmost 21
}
2 * (1 * fact1 ((21)1))
$\Longrightarrow$
{
replace fact1 ((21)1)
using definition, add implicit parentheses }
2 * (1 * (if ((21)1) == 0 then 1
else ((21)1) * fact1 ((21)1)1))
$\Longrightarrow$
{
evaluate 21
in condition }
2 * (1 * (if (11) == 0 then 1
else ((21)1) * fact1 ((21)1)1))
$\Longrightarrow$
{
evaluate 11
in condition }
2 * (1 * (if 0 == 0 then 1
else ((21)1) * fact1 ((21)1)1))
$\Longrightarrow$
{
evaluate 0 == 0
}
2 * (1 * (if True then 1
else ((21)1) * fact1 ((21)1)1))
$\Longrightarrow$
{
evaluate if
}
2 * (1 * 1)
$\Longrightarrow$
{
evaluate 1 * 1
}
2 * 1
$\Longrightarrow$
{
evaluate 2 * 1
}
2
The rewriting model we have been using so far can be called string reduction because our model involves the textual replacement of one string by an equivalent string.
A more efficient alternative is graph reduction. In this technique, the expressions are represented as (directed acyclic) expression graphs rather than text strings. The repeated subexpressions of an expression are represented as shared components of the expression graph. Once a shared component has been evaluated once, it need not be evaluated again.
In the example above, subexpression 21
is reduced three times. However, all of those subexpressions come from
the initial replacement of fact1 2
. Using
graph reduction, only the first of those reductions is necessary.
fact1 2
$\Longrightarrow$
{
replace fact1 2
using definition
}
if 2 == 0 then 1 else 2 * fact1 (21)
$\Longrightarrow$
{
evaluate 2 == 0
in condition }
if False then 1 else 2 * fact1 (21)
}
$\Longrightarrow$
{
evaluate if
}
2 * fact1 (21)
$\Longrightarrow$
{
replace fact1 (21)
using definition, add implicit parentheses }
2 * (if (21) == 0 then 1 else (21) * fact1 ((21)1))
$\Longrightarrow$
{
evaluate 21
because of condition (3 occurrences in graph) }
2 * (if 1 == 0 then 1 else 1 * fact1 (11))
$\Longrightarrow$
{
evaluate 1 == 0
}
2 * (if False then 1 else 1 * fact1 (11))
$\Longrightarrow$
{
evaluate if
}
2 * (1 * fact1 (11))
$\Longrightarrow$
{
replace fact1 ((11)
using definition, add implicit parentheses }
2 * (1 * (if (11) == 0 then 1 else (11) * fact1 ((11)1))
$\Longrightarrow$
{
evaluate 11
because of condition (3 occurrences in graph) }
2 * (1 * (if 0 == 0 then 1 else 0 * fact1 (01))
$\Longrightarrow$
{
evaluate 0 == 0
}
2 * (1 * (if True then 1 else 0 * fact1 (01))
$\Longrightarrow$
{
evaluate if
}
2 * (1 * 1)
$\Longrightarrow$
{
evaluate 1 * 1
}
2 * 1
$\Longrightarrow$
{
evaluate 2 * 1
}
2
In general, the Haskell compiler or interpreter uses a leftmost outermost graph reduction technique. However, if the value of a function’s argument is always needed for a computation, then an innermost reduction can be triggered for that argument. Either the programmer can explicitly require this or the compiler can detect the situation and automatically trigger the innermost reduction order.
Haskell exhibits lazy evaluation. That is, an expression is not evaluated until its value is needed, if ever. An outermost reduction corresponds to this evaluation strategy.
Other functional languages such as Scala and F# exhibit eager evaluation. That is, an expression is evaluated as soon as possible. An innermost reduction corresponds to this evaluation strategy.
We state efficiency (i.e., time complexity or space complexity) of programs in terms of the “BigO” notation and asymptotic analysis.
For example, consider the leftmost outermost graph reduction of
function fact1
above. The number
of reduction steps required to evaluate fact1 n
is 5*n + 3
.
We let the number of steps in a graph reduction be our measure of
time. Thus, the time complexity of fact1 n
is O(n
), which means that the time to
evaluate fact1 n
is bounded
above by some (mathematical) function that is proportional to the value
of n
.
Of course, this result is easy to see in this case. The algorithm is
dominated by the n
multiplications it must carry out. Alternatively, we see that evaluation
requires on the order of n
recursive calls.
We let the number of arguments in an expression graph be our measure of the size of an expression. Then the space complexity is the maximum size needed for the evaluation in terms of the input.
This size measure is an indication of the maximum size of the unevaluated expression that is held at a particular point in the evaluation process. This is a bit different from the way we normally think of space complexity in imperative algorithms, that is, the number of “words” required to store the program’s data.
However, this is not as strange as it may at first appear. As we in later chapters, the data structures in functional languages like Haskell are themselves expressions built by applying constructors to simpler data.
In the case of the graph reduction of fact1 n
, the size of the largest
expression is 2*n + 16
.
This is a multiplication for each integer in the range from 1 to n
plus 16 for the full if
statement.
Thus the space complexity is O(n
).
The BigO analysis is an asymptotic analysis. That is, it estimates the order of magnitude of the evaluation time or space as the size of the input approaches infinity (gets large). We often do worst case analyses of time and space. Such analyses are usually easier to do than averagecase analyses.
The time complexity of fact1 n
is similar to that of a loop
in an imperative program. However, the space complexity of the
imperative loop algorithm is O(1). So fact1
is not space efficient compared
to the imperative loop.
We examine techniques for improving the efficiency of functions below. In Chapter 29, we examine reduction techniques more fully.
A recursive function has one or more recursive cases and one or more base (nonrecursive) cases. It may also be undefined for some cases.
To show that evaluation of a recursive function terminates, we must show that each recursive application always gets closer to a termination condition represented by a base case.
Again consider fact1
defined above.
If fact1
is called with
argument n
greater than 0, the
argument of the recursive application in the else
clause
always decreases to n  1
.
Because the argument always decreases in integer steps, it must
eventually reach 0 and, hence, terminate in the first leg of the
definition.
If we call fact1
with
argument 0, the function terminates immediately.
What if we call fact1
with
its argument less than 0? We consider this issue below.
This chapter (8) introduced an evaluation model applicable to Haskell programs. It provides a framework for analyzing Haskell functions to determine under what conditions they terminate normally and how efficient they are.
Chapter 9 informally analyzes simple functions in terms of time and space efficiency and termination.
Chapter 29 examines these issues in more depth.
Given the following definition of Fibonacci function fib
, show the reduction of fib 4
.
fib :: Int > Int
0 = 0
fib 1 = 1
fib  n >= 2 = fib (n1) + fib (n2) fib n
What are the time and space complexities of fact6
as defined in the previous
exercise?
Given the following definition of fact6
, show the
reduction of fact6 2
.
fact6 :: Int > Int
= factIter n 1
fact6 n
factIter :: Int > Int > Int
0 r = r
factIter  n > 0 = factIter (n1) (n*r) factIter n r
What are the time and space complexities of fact6
as defined in the previous
exercise?
In Summer and Fall 2016, I adapted and revised much of this work from parts of chapters 1 and 13 of my Notes on Functional Programming with Haskell [42]. These chapters had evolved from my study of the work by Bird and Wadler [15], Hudak [101], Wentworth [178], Thompson [171], and others as I was learning functional programming.
In 2017, I continued to develop this work as Chapter 3, Evaluation and Efficiency, of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I divided the previous Evaluation and Efficiency chapter into two chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. Previous sections 3.13.2 became the basis for new Chapter 8, Evaluation Model (this chapter), and previous sections 3.33.5 became the basis for Chapter 9, Recursion Styles and Efficiency. I also moved the discussion of preconditions and postconditions to the new Chapter 6.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
Referential transparency, reducible expression (redex), reduction strategies (leftmost vs. rightmost, innermost vs. outermost), string and graph reduction models, time and space complexity, termination preconditions, postconditions, contracts.
This chapter () introduces basic recursive programming styles and examines issues of efficiency, termination, and correctness. It builds on the substitution model from Chapter 8, but uses the model informally.
As in the previous chapters, this chapter focuses on use of firstorder functions and primitive data types.
The goals of the chapter are to:
explre several recursive programming styles—linear and nonlinear, backward and forward, tail, and logarithmic—and their implementation using Haskell
analyze Haskell functions to determine under what conditions they terminate with the correct result and how efficient they are
explore methods for developing recursive Haskell programs that terminate with the correct result and are efficient in both time and space usage
compare the basic functional programming syntax of Haskell with that in other languages
Given the substitution model described in Chapter 8, we can now consider efficiency and termination in the design of recursive Haskell functions.
In this section, we examine the concepts of linear and nonlinear recursion. The following two sections examine other styles.
A function definition is linear recursive if at most one
recursive application of the function occurs in any leg of the
definition (i.e., along any path from an entry to a return). The various
argument patterns and guards and the branches of the conditional
expression if
introduce paths.
The definition of the function fact4
repeated below is linear
recursive because the expression in the second leg of the definition
(i.e., n * fact4 (n1)
)
involves a single recursive application. The other leg is nonrecursive;
it is the base case of the recursive definition.
fact4 :: Int > Int
fact4 n  n == 0 = 1
 n >= 1 = n * fact4 (n1)
What are the precondition and postcondition for fact4 n
?
As discussed in Chapter 6, we
must require a precondition of n >= 0
to avoid abnormal termination. When the precondition holds, the
postcondition is:
fact4 n =
fact’(n)
What are the time and space complexities of fact4 n
?
Function fact4
recurses to a
depth of n
. As we in for fact1
in Chapter
8, it has time complexity
O(n
), if we count either the
recursive calls or the multiplication at each level. The space
complexity is also O(n
)
because a new runtime stack frame is needed for each recursive call.
How do we know that function fact4 n
terminates?
For a call fact4 n
with n > 0
,
the argument of the recursive application always decreases to n  1
.
Because the argument always decreases in integer steps, it must
eventually reach 0 and, hence, terminate in the first leg of the
definition.
A nonlinear recursion is a recursive function in which the
evaluation of some leg requires more than one recursive application. For
example, the naive Fibonacci number function fib
shown below has two recursive
applications in its third leg. When we apply this function to a
nonnegative integer argument greater than 1, we generate a pattern of
recursive applications that has the “shape” of a binary tree. Some call
this a tree recursion.
fib :: Int > Int
0 = 0
fib 1 = 1
fib  n >= 2 = fib (n1) + fib (n2) fib n
What are the precondition and postcondition for fib n
?
For fib n
, the precondition
n >= 0
to ensure that the function is defined. When called with the
precondition satisfied, the postcondition is:
fib n
= Fibonacci(n)
How do we know that fib n
terminates?
For the recursive case n >= 2
.
the two recursive calls have arguments that are 1 or 2 less than n
. Thus every call gets closer to one
of the two base cases.
What are the time and space complexities of fib n
?
Function fib
is
combinatorially explosive, having a time complexity O(fib n
). The space complexity is
O(n
) because a new runtime stack
frame is needed for each recursive call and the calls recurse to a depth
of n
.
An advantage of a linear recursion over a nonlinear one is that a linear recursion can be compiled into a loop in a straightforward manner. Converting a nonlinear recursion to a loop is, in general, difficult.
In this section, we examine the concepts of backward and forward recursion.
A function definition is backward recursive if the recursive application is embedded within another expression. During execution, the program must complete the evaluation of the expression after the recursive call returns. Thus, the program must preserve sufficient information from the outer call’s environment to complete the evaluation.
The definition for the function fact4
above is backward recursive
because the recursive application fact4 (n1)
in the second leg is embedded within the expression n * fact4 (n1)
.
During execution, the multiplication must be done after return. The
program must “remember” (at least) the value of parameter n
for that call.
A compiler can translate a backward linear recursion into a loop, but the translation may require the use of a stack to store the program’s state (i.e., the values of the variables and execution location) needed to complete the evaluation of the expression.
Often when we design an algorithm, the first functions we come up with are backward recursive. They often correspond directly to a convenient recurrence relation. It is often useful to convert the function into an equivalent one that evaluates more efficiently.
A function definition is forward recursive if the recursive application is not embedded within another expression. That is, the outermost expression is the recursive application and any other subexpressions appear in the argument lists. During execution, significant work is done as the recursive calls are made (e.g., in the argument list of the recursive call).
The definition for the auxiliary function factIter
below has two integer
arguments. The first argument is the number whose factorial is to be
computed. The second argument accumulates the product incrementally as
recursive calls are made.
The recursive application factIter (n1) (n*r)
in the second leg is on the outside of the expression evaluated for
return. The other leg of factIter
and fact6
itself are nonrecursive.
fact6 :: Int > Int
= factIter n 1
fact6 n
factIter :: Int > Int > Int
0 r = r
factIter  n > 0 = factIter (n1) (n*r) factIter n r
What are the precondition and postcondition for factIter n r
?
To avoid termination, factIter n r
requires n >= 0
.
Its postcondition is that:
factIter n r = r *
fact(n)
How do we know that factIter n r
terminates?
Argument n
of the recursive
leg is at least 1 and decreases by 1 on each recursive call.
What is the time and space complexity of factIter n r
?
Function factIter n r
has a
time complexity O(n
). But, if
the compiler converts the factIter
recursion to a loop, the time
complexity’s constant factor should be smaller than that of fact4
.
As shown, factIter n r
has
space complexity of O(n
). But,
if the compiler does an innermost reduction on the second argument
(because its value will always be needed), then the space complexity of
factIter
becomes O(1).
A function definition is tail recursive if it is both forward recursive and linear recursive. In a tail recursion, the last action performed before the return is a recursive call.
The definition of the function factIter
above is thus tail
recursive.
Tail recursive definitions are relatively straightforward to compile into efficient loops. There is no need to save the states of unevaluated expressions for higher level calls; the result of a recursive call can be returned directly as the caller’s result. This is sometimes called tail call optimization (or “tail call elimination” or “proper tail calls”) [202].
In converting the backward recursive function fact4
to a tail recursive auxiliary
function, we added the parameter r
to factIter
. This parameter is sometimes
called an accumulating parameter (or just an
accumulator).
We typically use an accumulating parameter to “accumulate” the result
of the computation incrementally for return when the recursion
terminates. In factIter
, this
“state” passed from one “iteration” to the next enables us to convert a
backward recursive function to an “equivalent” tail recursive one.
Function factIter
defines a
more general function than fact4
. It computes a factorial when we
initialize the accumulator to 1, but it can compute some multiple of the
factorial if we initialize the accumulator to another value. However,
the application of factIter
in
fact6
gives the initial value of
1 needed for factorial.
Consider auxiliary function fibIter
used by function fib2
below. This function adds two
“accumulating parameters” to the backward nonlinear recursive function
fib
to convert the nonlinear
(tree) recursion into a tail recursion. This technique works for
Fibonacci numbers, but the same technique will not work in all
cases.
fib2 :: Int > Int
 n >= 0 = fibIter n 0 1
fib2 n where
0 p q = p
fibIter  m > 0 = fibIter (m1) q (p+q) fibIter m p q
Here we use type inference for fibIter
. Function fibIter
could be declared
fibIter :: Int > Int > Int > Int
but it was not necessary because Haskell can infer the type from the types involved in its defining expressions.
What are the precondition and postcondition for fibIter n p q
?
To avoid abnormal termination, fibIter n p q
requires n >= 0
.
When the precondition holds, its postcondition is:
fibIter n p q =
Fibonacci(n) + (p + q  1)
If called with p
and q
set to 0 and 1, respectively, then
fibIter
returns:
Fibonacci
(n)
How do we know that fibIter n p q
terminates for
$n \geq 0$?
The recursive leg of fibIter n p q
is only evaluated when
n > 0
.
On the recursive call, that argument decreases by 1. So eventually the
computation reaches the base case.
What are the time and space complexities of fibIter
?
Function fibIter
has a time
complexity of O(n
) in contrast
to O(fib n
) for fib
. This algorithmic speedup results
from the replacement of the very expensive operation fib(n1) + fib(n2)
at each level in fib
by the
inexpensive operation p + q
(i.e.,
addition of two numbers) in fibIter
.
Without tail call optimization, fibIter n p q
has space complexity of
O(n
). However, tail call
optimization (including an innermost reduction on the q
argument) can convert the recursion
to a loop, giving O(1) space complexity.
When combined with tailcall optimization and innermost reduction of strict arguments, a tail recursive function may be more efficient than the equivalent backward recursive function. However, the backward recursive function is often easier to understand and, as we see in Chapter 25, to reason about.
We can define the exponentiation operation ^
in terms of
multiplication as follows for integers b
and n >= 0
:
b^n =
$\prod_{i=1}^{i=n} b$
A backward recursive exponentiation function expt
, shown below in Haskell, raises a
number to a nonnegative integer power.
expt :: Integer > Integer > Integer
0 = 1
expt b
expt b n n > 0 = b * expt b (n1)  backward rec
 otherwise = error (
"expt undefined for negative exponent "
++ show n )
Here we use the unbounded integer type Integer
for
the parameters and return value.
Note that the recursive call of expt
does not change the value of the
parameter b
.
Consider the following questions relative to expt
.
What are the precondition and postcondition for expt b n
?
How do we know that expt b n
terminates?
What are the time and space complexities of expt b n
(ignoring any additional
costs of processing the unbounded integer type)?
We can define a tail recursive auxiliary function exptIter
by adding a new parameter to
accumulate the value of the exponentiation incrementally. We can define
exptIter
within a function expt2
, taking advantage of the fact
that the base b
does not change.
This is shown below.
expt2 :: Integer > Integer > Integer
 n < 0 = error (
expt2 b n "expt2 undefined for negative exponent "
++ show n )
= exptIter n 1
expt2 b n where exptIter 0 p = p
= exptIter (m1) (b*p)  tail rec exptIter m p
Consider the following questions relative to expt2
.
What are the precondition and postcondition for exptIter n p
?
How do we know that exptIter n p
terminates?
What are the time and space complexities of exptIter n p
?
The exponentiation function can be made computationally more efficient by squaring the intermediate values instead of iteratively multiplying. We observe that:
^n = b^(n/2)^2 if n is even
b^n = b * b^(n1) if n is odd b
Function expt3
below
incorporates this observation into an improved algorithm. Its time
complexity is O(log2 n
) and
space complexity is O(log2 n
).
(Here we assume that log2
computes the logarithm base 2.)
expt3 :: Integer > Integer > Integer
 n < 0 = error (
expt3 _ n "expt3 undefined for negative exponent "
++ show n )
= exptAux n
expt3 b n where exptAux 0 = 1
exptAux n  even n = let exp = exptAux (n `div` 2) in
exp * exp  backward rec
 otherwise = b * exptAux (n1)  backward rec
Here we are use two features of Haskell we have not used in the previous examples.
Boolean function even
returns
True
if
and only if its integer argument is an even number. Similarly, odd
returns
True
when its argument is an odd number.
The let
clause
introduces exp
as a local
definition within the expression following in
keyword,
that is, within exp * exp
.
The let
feature
allows us to introduce new definitions in a bottomup manner—first
defining a symbol and then using it.
Consider the following questions relative to expt3
.
What are the precondition and postcondition expt3 b n
?
How do we know that exptAux n
terminates?
What are the time and space complexities of exptAux n
?
We have used two different language features to add local definitions
to Haskell functions: let
and where
.
The let
expression
is useful whenever a nested set of definitions is required. It has the
following syntax:
let
local_definitionsin
expression
A let
may be used anywhere that an expression my appear in a Haskell
program.
For example, consider a function f
that takes a list of integers and
returns a list of their squares incremented by one:
f :: [Int] > [Int]
= []
f [] = let square a = a * a
f xs = 1
one :ys) = xs
(yin (square y + one) : f ys
square
represents a
function of one variable.
one
represents a
constant, that is, a function of zero variables.
(y:ys)
represents a pattern match binding against argument xs
of f
.
Reference to y
or ys
when argument xs
of f
is nil results in an error.
Local definitions square
,
one
, y
, and ys
all come into scope simultaneously;
their scope is the expression following the in
keyword.
Local definitions may access identifiers in outer scopes (e.g.,
xs
in definition of (y:ys)
) and
have definitions nested within themselves.
Local definitions may be recursive and call each other.
The let
clause
introduces symbols in a bottomup manner: it introduces symbols before
they are used.
The where
clause
is similar semantically, but it introduces symbols in a topdown manner:
the symbols are used and then defined in a where
that
follows.
The where
clause
is more versatile than the let
. It allows
the scope of local definitions to span over several guarded equations
while a let
’s scope is
restricted to the righthand side of one equation.
For example, consider the definition:
g :: Int > Int
 check3 == x = x
g n  check3 == y = y
 check3 == z = z * z
where check3 = n `mod` 3
= 0
x = 1
y = 2 z
The scope of this where
clause
is over all three guards and their respective righthand sides.
(Note that the where
begins
in the same column as the =
rather than
to the right as in rev’
.)
Note the use of the modulo function mod
as an
infix operator. The backquotes (‘
) around a function name denotes the
infix use of the function.
In addition to making definitions easier to understand, local definitions can increase execution efficiency in some cases. A local definition may introduce a component into the expression graph that is shared among multiple branches. Haskell uses graph reduction, so any shared component is evaluated once and then replaced by its value for subsequent accesses.
The local variable check3
introduces a component shared among all three legs. It is evaluated once
for each call of g
.
In this chapter, we have expressed the functions in Haskell, but they are adapted from the classic textbook Structure and Interpretation of Computer Programs (SICP) [1], which uses Scheme.
To compare languages, let’s examine the expt3
function in Scheme and other
languages.
Below is the Scheme language program for exponentiation similar to to
expt3
(called fastexpt
in SICP [1]). Scheme, a dialect
of Lisp, is an impure, eagerly evaluated functional language with
dynamic typing.
define (expt3 b n)
(cond
(< n 0) (error `expt3 "Called with negative exponent"))
((else (expt_aux b n))))
(
define (expt_aux b n)
(cond
(= n 0) 1)
((even? n) (square (expt3 b (/ n 2))))
((else (* b (expt3 b ( n 1))))))
(
define (square x) (* x x))
(
define (even? n) (= (remainder n 2) 0)) (
Scheme (and Lisp) represents both data and programs as sexpressions (nested list structures) enclosed in balanced parentheses; that is, Scheme is homoiconic. In the case of executable expressions, the first element of the list may be operator. For example, consider:
define (square x) (* x x)) (
The define
operator
takes two arguments:
a symbol being defined, in this case a function signature (square x)
for a function named square
with one formal parameter named
x
an expression defining the value of the symbol, in this case the
expression (* x x)
that
multiplies formal parameter x
by
itself and returns the result
The define
operator
has the side effect of adding the definition of the symbol to the
environment. That is, square
is
introduced as a one argument function with the value denoted by the
expression (* x x)
.
The conditional expression cond
gives an
ifthenelseif expression that evaluates a sequence of predicates until
one evaluates to “true” value and then returns the paired expression.
The else
at the end always evaluates to “true”.
The above Scheme code defines the functions square
, the exponentiation function
expt3
, and the logical predicate
even? {.scheme}
. It uses the primitive Scheme functions

, *
, /
, remainder
, and
=
(equality).
We can evaluate the Scheme expression (expt 2 10)
using a Scheme interpreter (as I did using DrRacket [71,72,140])
and get the value 1024
.
Although Haskell and Scheme are different in many ways—algebraic versus sexpression syntax, static versus dynamic typing, lazy versus eager evaluation (by default), always pure versus sometimes impure functions, etc.—the fundamental techniques we have examined in Haskell still apply to Scheme and other languages. We can use a substitution model, consider preconditions and termination, use tail recursion, and take advantage of firstclass and higherorder functions.
Of course, each language offers a unique combination of features that can be exploited in our programs. For example, Scheme programmers can leverage its runtime flexibility and powerful macro system; Haskell programmers can build on its safe type system, algebraic data types, pattern matching, and other features.
The Racket Scheme [140] code for this subsection is in file
expt3.rkt
.
Let’s now consider other languages.
The language Elixir [68,168] is a relatively new language that executes on the Erlang platform (called the Erlang Virtual Machine or BEAM). Elixir is an eagerly evaluated functional language with strong support for messagepassing concurrent programming. It is dynamically typed and is mostly pure except for input/output. It has patternmatching features similar to Haskell.
We can render the expt3
program into a sequential Elixir program as follows.
def expt3(b,n) when is_number(b) and is_integer(n)
and n >= 0 do
exptAux(b,n)end
defp exptAux(_,0) do 1 end
defp exptAux(b,n) do
if rem(n,2) == 0 do # i.e. even
= exptAux(b,div(n,2))
exp * exp # backward rec
exp else # i.e. odd
* exptAux(b,n1) # backward rec
b end
end
This code occurs within an Elixir module. The def
statement
defines a function that is exported from the module while defp
defines a
function that is private to the module (i.e., not exported).
A definition allows the addition of guard clauses following when
(although
they cannot include userdefined function calls because of restrictions
of the Erlang VM). In function expt3
, we use guards to do some type
checking in this dynamically typed language and to ensure that the
exponent is nonnegative.
Private function exptAux
has
two functions bodies. As in Haskell, the body is selected using pattern
matching proceeding from top to bottom in the module. The first function
body with the header exptAux(_,0)
matches all cases in which the second argument is 0
. All other
situations match the second header exptAux(b,n)
binding parameters b
and n
to the argument values.
The functions div
and rem
denote integer division and
remainder, respectively.
The Elixir =
operator is
not an assignment as in imperative languages. It is a patternmatch
statement with an effect similar to let
in the
Haskell function.
Above the expression
= exptAux(b,div(n,2)) exp
evaluates the recursive call and then binds the result to new local
variable named exp
. This value is
used in the next statement to compute the return value exp * exp
.
Again, although there are significant differences between Haskell and Elixir, the basic thinking and programming styles learned for Haskell are also useful in Elixir (or Erlang). These styles are also key to use of their concurrent programming features.
The Elixir [68]
code for this subsection is in file expt.ex
.
The language Scala [132,151] is a hybrid functional/objectoriented language that executes on the Java platform (i.e., on the Java Virtual Machine or JVM). Scala is an eagerly evaluated language. It allows functions to be written in a mostly pure manner, but it allows intermixing of functional, imperative, and objectoriented features. It has a relatively complex static type system similar to Java, but it supports type inference (although weaker than that of Haskell). It interoperates with Java and other languages on the JVM.
We can render the exponentiation function expt3
into a functional Scala program as
shown below. This uses the Java/Scala extended integer type BigInt
for the base and return
values.
def expt3(b: BigInt, n: Int): BigInt = {
def exptAux(n1: Int): BigInt = // b known from outer
match {
n1 case 0 => 1
case m if (m % 2 == 0) => // i.e. even
val exp = exptAux(m/2)
* exp // backward rec
exp case m => // i.e. odd
* exptAux(m1) // backward rec
b }
if (n >= 0)
exptAux(n)
else
.error ("Cannot raise to negative power " + n )
sys}
The body of function expt3
uses
an ifelse
expression to ensure that the exponent is nonnegative and then calls
exptAux
to do the work.
Function expt3
encloses
auxiliary function exptAux
. For
the latter, the parameters of expt3
are in scope. For example, exptAux
uses b
from expt3
as a constant.
Scala supports pattern matching using an explicit match
operator
in the form:
selector
match {
alternatives}
It evaluates the selector expression and then choses the first alternative pattern that matches this value, proceedings top to botton, left to right. We write the alternative as
case
pattern=>
expression
or with a guard as:
case
patternif
boolean_expression=>
expression
The expression may be a sequence of expressions. The value returned is the value of the last expression evaluated.
In this example, the match
in exptAux
could easily be replaced by an
if
–else if
–else
expression
because it does not depend upon complex pattern matching.
In Haskell, functions are automatically curried. In Scala, we could
alternatively define expt3
in
curried form using two argument lists as follows:
def expt3(b: BigInt)(n: Int): BigInt = ...
Again, we can use most of the functional programming methods we learn for Haskell in Scala. Scala has a few advantages over Haskell such as the ability to program in a multiparadigm style and interoperate with Java. However, Scala tends to be more complex and verbose than Haskell. Some features such as type inference and tail recursion are limited by Scala’s need to operate on the JVM.
The Scala [151]
code for this subsection is in file exptBigInt2.scala
.
Lua [104,116] is a minimalistic, dynamically typed, imperative language designed to be embedded as a scripting language within other programs, such as computer games. It interoperates well with standard C and C++ programs.
We can render the exponentiation function expt3
into a functional Lua program as
shown below.
local function expt3(b,n)
local function expt_aux(n)  b known from outer
if n == 0 then
return 1
elseif n % 2 == 0 then  i.e. even
local exp = expt_aux(n/2)
return exp * exp  backward recursion
else  i.e. odd
return b * expt_aux(n1)  backward recursion
end
end
if type(b) == "number" and type(n) == "number" and n >= 0
and n == math.floor(n) then
return expt_aux(n,1)
else
error("Invalid arguments to expt: " ..
tostring(b) .. "^" .. tostring(n))
end
end
Like the Scala version, we define the auxiliary function
expt_aux
inside of function expt3
, limiting its scope to the outer
function.
This function uses with Lua version 5.2. In this and earlier versions, the only numbers are IEEE standard floating point. As in the Elixir version, we make sure the arguments are numbers with the exponent argument being nonnegative. Given that the numbers are floating point, the function also ensures that the exponent is an integer.
Auxiliary function expt_aux
does
the computational work. It differentiates among the three cases using an
if
–elseif
–else
structure.
Lua does not have a switch statement or pattern matching capability.
Lua is not normally considered a functional language, but it has a number of features that support functional programming—in particular, firstclass and higher order functions and tail call optimization.
In many ways, Lua is semantically similar to Scheme, but instead of having the Lisplike hierarchical list as its central data structure, Lua provides an efficient, mutable, associative data structure called a table (somewhat like a hash table or map in other languages). Lua does not support Schemestyle macros in the standard language.
Unlike Haskell, Elixir, and Scala, Lua does not have builtin immutable data structures or pattern matching. Lua programs tend to be relatively verbose. So some of the usual programming idioms from functional languages do not fit Lua well.
The Lua [116] code
for this subsection is in file expt.lua
.
Elm [60,70] is a new functional language intended primarily for clientside Web programming. It is currently compiled into JavaScript, so some aspects are limited by the target execution environment. For example, Elm’s basic types are those of JavaScript. So integers are actually implemented as floating point numbers.
Elm has a syntax and semantics that is similar to, but simpler than,
Haskell. It has a Haskelllike let
construct for
local definitions but not a where
construct.
It also limits pattern matching to structured types.
Below is an Elm implementation of an exponentiation function similar
to the Haskell expt3
function,
except it is limited to the standard integers Int
. Operator
//
denotes
the integer division operation and %
is remainder
operator.
expt3 : Int > Int > Int
expt3 b n =
let
exptAux m =
if m == 0 then
1
else if m % 2 == 0 then
let
exp = exptAux (m // 2)
in
exp * exp  backward rec
else
b * exptAux (m1)  backward rec
in
if n < 0 then
0  error?
else
exptAux n
One semantic difference between Elm and Haskell is that Elm functions
must be total—that is, return a result for every possible input. Thus,
this simple function extends the definition of expt3
to return 0
for a negative power. An alternative would be to have expt3
return a
Maybe Int
type instead of Int
. We will
examine this feature in Haskell later.
The Elm [60] code
for this subsection is in file expt.elm
.
As we have seen in this chapter, we can develop efficient programs using functional programming and the Haskell language. These may require use to think about problems and programming a bit differently than we might in an imperative or objectoriented language. However, the techniques we learn for Haskell are usually applicable whenever we use the functional paradigm in any language. The functional way of thinking can also improve our programming in more traditional imperative and objectoriented languages.
In Chapter 10, we examine simple input/output concepts in Haskell. In Chapters 11 and 12, we examine software testing concepts.
In subsequent chapters, we explore the list data structure and additional programming techniques.
The Haskell modules for the functions in this chapter are defined in the following source files:
the factorial functions in Factorial.hs
(from Chapter
4)
the other Haskell functions in RecursionStyles.hs
(with a simple
test script in file TestRecursionStyles.hs
){type=“text/plain”}).
Show the reduction of the expression fib 4
substitution model. (This is repeated from the previous
chapter.)
Show the reduction of the expression expt 4 3
using the substitution model.
Answer the questions (precondition, postcondition, termination,
time complexity, space complexity) in the subsection about expt
.
Answer the questions in the subsection about expt
.
Answer the questions in the subsection about expt2
.
Answer the questions in the subsection about expt3
.
Develop a recursive function in Java, C#, Python 3, JavaScript,
or C++ that has the same functionality as expt3
.
Develop an iterative, imperative program in Java, C#, Python 3,
JavaScript, or C++ that has the same functionality as expt3
.
For each of the following exercises, develop a Haskell program. For each function, informally argue that it terminates and give BigO time and space complexities. Also identify any preconditions necessary to guarantee correct operation. Take care that special cases and error conditions are handled in a reasonable way.
Develop a backward recursive function sumTo
such that sumTo n
computes the sum of the
integers from 1 to n
for n >= 0
.
Develop a tail recursive function sumTo'
such that sumTo' n
computes the sum of the
integers from 1 to n
for n >= 0
.
Develop a backward recursive function sumFromTo
such that sumFromTo m n
computes the sum of the
integers from m
to n
for m <= n
.
Develop a tail recursive function sumFromTo'
such that sumFromTo' m n
computes the sum of
the integers from m
to n
for m <= n
.
Suppose we have functions succ
(successor) and pred
(predecessor) defined as follows:
succ, pred :: Int > Int
succ n = n + 1
pred n = n  1
Develop a function add
such
that add m n
computes m + n
.
Function add
cannot use the
integer addition or subtraction operations but can use the succ
ad pred
functions
above.
Develop a function acker
to compute Ackermann’s function, which is function
$A$
defined in Table 9.1.
$A(m,n)$  $=$  $n+1,$  if $m = 0$ 
$A(m,n)$  $=$  $A(m1,1),$  if $m > 0$ and $n = 0$ 
$A(m,n)$  $=$  $A(m1,A(m,m1)),$  if $m > 0$ and $n > 0$ 
Develop a function hailstone
to implement the function
shown in Table 9.2.
$hailstone(n)$  $=$  $1$,  if $n = 1$ 
$hailstone(n)$  $=$  $hailstone(n/2)$,  if $n > 1$, even $n$ 
$hailstone(n)$  $=$  $hailstone(3*n+1)$,  if $n > 1$, odd $n$ 
Note that an application of the hailstone
function to the argument
3
would result in the following “sequence” of “calls” and
would ultimately return the result 1
.
3
hailstone 10
hailstone 5
hailstone 16
hailstone 8
hailstone 4
hailstone 2
hailstone 1 hailstone
For further thought: What is the domain of the hailstone function?
Develop the exponentiation function expt4
that is
similar to expt3
but is tail
recursive.
Develop the following group of functions.
test
such that test a b c
is True
if and
only if a <= b
and
no integer is the range from a
to b
inclusive is divisible by
c
.
prime
such that prime n
is True
if and
only if n
is a prime
integer.
nextPrime
such that nextPrime n
returns the next prime
integer greater than n
Develop function binom
to
compute binomial coefficients. That is, binom n k
returns
$\binom{n}{k}$
for integers n >= 0
and 0 <= k <= n
.
In Summer and Fall 2016, I adapted and revised much of this work from previous work:
the 2016 Scala version of my notes on Recursion Syles, Correctness, and Efficiency [48] (for which previous versions existed in Scala, Elixir, and Lua)
the Haskell factorial, Fibonacci number, and exponentiation functions from my previous examples in Haskell, Elm, Scala, Elixir, and Lua, which, in turn, were adapted from the Scheme programs in Abelson and Sussman’s classic, Schemebased textbook SICP [1]
In 2017, I continued to develop this work as Chapter 3, Evaluation and Efficiency, of my 2017 Haskellbased programming languages textbook.
In Spring and Summer 2018, I divided the previous Evaluation and Efficiency chapter into two chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. Previous sections 3.13.2 became the basis for new Chapter 8, Evaluation Model, and previous sections 3.33.5 became the basis for Chapter 9 (this chapter), Recursion Styles and Efficiency. I also moved some of the discussion of preconditions and postconditions from old chapter 3 to the new chapter 6 and discussion of local definitions from old chapter 4 to new chapter 9 (this chapter).
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
Recursion styles (linear vs. nonlinear, backward vs. forward, tail, and logarithmic), correctness (precondition, postcondition, and termination), efficiency estimation (time and space complexity), transformations to improve efficiency (auxiliary function, accumulator), homiconic, messagepassing concurrent programming, embedded as a scripting language, clientside Web programming.
This is a stub for a possible future chapter. The Haskell Wikibook [179] Simple input and output page discusses the concepts sufficient for the purposes of this point in the textbook.
TODO
TODO
TODO
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
TODO
The goal of this chapter (11) is to survey the important concepts, terminology, and techniques of software testing in general.
Chapter 12 illustrates these techniques by manually constructing test scripts for Haskell functions and modules.
The purpose of a software development project is to meet particular needs and expectations of the project’s stakeholders.
By stakeholder, we mean any person or organization with some interest in the project’s outcome. Stakeholders include entities that:
have a “business” problem needing a solution—the project’s sponsors, customers, and users
care about the broad impacts of the project and its solution—that laws, regulations, standards, best practices, codes of conduct, etc., are followed
are responsible for the development, deployment, operation, support, and maintenance of the software
A project’s stakeholders should create a software requirements specification to state the particular needs and expectations to be addressed.
A software requirements specification seeks to comprehensively describe the intended behaviors and environment of the software to be developed. It should address the “what” but not the “how”. For example, the software requirements specification should describe the desired mapping from inputs to outputs but not unnecessarily restrict the software architecture, software design, algorithms, data structures, programming languages, and software libraries that can be used to implement the mapping.
Once the requirements are sufficiently understood, the project’s developers then design and implement the software system: its software architecture, its subsystems, its modules, and its functions and procedures.
Software testing helps ensure that the software implementation satisfies the design and that the design satisfies the stakeholder’s requirements.
Of course, the requirements analysis, design, and implementation may be an incremental. Software testing can also play a role in identifying requirements and defining appropriate designs and implementations.
According to the Collins English Dictionary [35]:
A test is a deliberate action or experiment to find out how well something works.
The purpose of testing a program is to determine “how well” the program “works”—to what extent the program satisfies its software requirements specification.
Software testing is a “deliberate” process. The tests must be chosen effectively and conducted systematically. In most cases, the test plan should be documented carefully so that the tests can be repeated precisely. The results of the tests should be examined rigorously.
In general, the tests should be automated. Testers can use manually written test scripts (as we do in the Chapter 12) or appropriate testing frameworks [126] (e.g., JUnit [166,174] in Java, Pytest [113,133] in Python, and HUnit [90], QuickCheck [89], or Tasty [91] in Haskell).
Testers try to uncover as many defects as possible, but it is impossible to identify and correct all defects by testing. Testing is just one aspect of software quality assurance.
Meszaros [126, Ch. 3] identifies several goals of test automation. These apply more generally to all software testing. Tests should:
help improve software quality
help software developers understand the system being tested
reduce risk
be easy to develop
be easy to conduct repeatedly
be easy to maintain as the system being tested continues to evolve
We can organize software testing along three dimensions [161]:
We explore these in the following subsections.
Software testing levels categorize tests by the applicable stages of software development.
Note: The use of the term “stages” does not mean that this approach is only applicable to the traditional waterfall software development process. These stages describe general analysis and design activities that must be carried out however the process is organized and documented.
Ammann and Offutt [2] identify five levels of testing, as shown in Figure 11.1. Each level assumes that the relevant aspects of the level below have been completed successfully.
From the highest to the lowest, the testing levels are as follows.
Acceptance testing focuses on testing a completed system to determine whether it satisfies the software requirements specification and to assess whether the system is acceptable for delivery.
The acceptance test team must include individuals who are strongly familiar with the business requirements of the stakeholders.
System testing focuses on testing an integrated system to determine whether it satisfies its overall specification (i.e., the requirements as reflected in the chosen software architecture).
The system test team is usually separate from the development team.
Integration testing focuses on testing each subsystem to determine whether its constituent modules communicate as required. For example, do the modules have consistent interfaces (e.g., compatible assumptions and contracts)?
A subsystem is often constructed by using existing libraries, adapting previously existing modules, and combining these with a few new modules. It is easy to miss subtle incompatibilities among the modules. Integration testing seeks to find any incompatibilities among the various modules.
Integration testing is often conducted by the development team.
Module testing focuses on the structure and behavior of each module separately from the other modules with which it communicates.
A module is usually composed of several related units and their associated data types and data structures. Module testing assesses whether the units and other features interact as required and assess whether the module satisfies its specification (e.g., its preconditions, postconditions, and invariants).
Note: Here we use the term “module” generically. For example, a
module in Java might be a class
, package
, or module
(in Java 9) construct. A module in
Python 3 might be a code file (i.e., module) or a directory structure of
code files (i.e., package). In Haskell, a generic module might be
represented as a closely related group of Haskell module
files.
Module testing is typically done by the developer(s) of a module.
Unit testing focuses on testing the implementation of each program unit to determine whether it performs according to the unit’s specification.
The term “unit” typically refers to a procedural abstraction such as a function, procedure, subroutine, or method.
A unit’s specification is its “contract”, whether represented in terms of preconditions and postconditions or more informally.
Unit testing is typically the responsibility of the developer(s) of the unit.
In objectbased systems, the units (e.g., methods) and the modules (e.g., objects or classes) are often tightly coupled. In this and similar situations, developers often combine unit testing and module testing into one stage called unit testing [2,161].
In this book, we are primarily concerned with the levels usually conducted by the developers: unit, module, and integration testing.
Software testing methods categorize tests by how they are conducted. The Software Testing Fundamentals website [161] identifies several methods for testing. Here we consider four:
In this book, we are primarily concerned with blackbox and graybox testing. Our tests are guided by the contracts and other specifications for the unit, module, or subsystem being tested.
In blackbox testing, the tester knows the external requirements specification (e.g., the contract) for the item being tested but does not know the item’s internal structure, design, or implementation.
Note: This method is sometimes called closedbox or behavioral testing.
This method approaches the system much as a user does, as a black box whose internal details are hidden from view. Using only the requirements specification and public features of the item, the testers devise tests that check input values to make sure the system yields the expected result for each. They use the item’s regular interface to carry out the tests.
Blackbox tests are applicable to testing at the higher levels—integration, systems, and acceptance testing—and for use by external test teams.
The method is also useful for unit and module testing, particularly when we wish to test the item against an abstract interface with an explicit specification (e.g., a contract stated as preconditions, postconditions, and invariants).
How do we design blackbox tests? Let’s consider the possible inputs to the item.
An item being tested has some number of input parameters—some explicit, others implicit. Each parameter has some domain of possible values.
The input domain of the item thus consists of the Cartesian product of the individual domains of its parameters. A test input is thus a tuple of values, one possible value for each parameter [2].
For example, consider testing a public instance method in a Java class. The method has zero or more explicit parameters, one implicit parameter (giving the method access to all the associated instance’s variables), and perhaps direct access to variables outside its associated instance (static variables, other instances’ variables, public variables in other classes, etc.).
In most practical situations, it is impossible to check all possible test inputs. Thus, testers need to choose a relatively small, finite set of input values to test. But how?
In choosing test inputs, the testers can fruitfully apply the following techniques [69,126,139].
Define equivalence classes (or partitions) of the possible inputs based on the kinds of behaviors of interest and then choose representative members of each class.
After studying the requirements specification for the item being tested, the tester first groups together inputs that result in the “same” behaviors of interest and then chooses typical representatives of each group for tests (e.g., from the middle of the group).
The representative values are normal use or “happy path” cases that are not usually problematic to implement [2].
For example, consider the valid integer values for the day of a month (on the Gregorian calendar as used in the USA). It may be useful to consider the months falling into three equivalence classes: 31day months, 30day months, and February.
Choose boundary values—values just inside and just outside the edges of an equivalence class (as defined above) or special values that require unusual handling.
Unlike the “happy path” tests, the boundary values often are values that cause problems [2].
For example, consider the size of a data structure being constructed. The boundary values of interest may be zero, one, minimum allowed, maximum allowed, or just beyond the minimum or maximum.
For a mathematical function, a boundary value may also be at or near a value for which the function is undefined or might result in a nonterminating computation.
Choose input values that cover the range of expected results.
This technique works from the output back toward the input to help ensure that important paths through the item are handled properly.
For example, consider transactions on a bank account. The action might be a balance inquiry, which returns information but does not change the balance in the account. The action might be a deposit, which results in a credit to the account. The action might be a withdrawal, which either results in a debit or triggers an insufficient funds action. Tests should cover all four cases.
Choose input values based on the model used to specify the item (e.g., state machine, mathematical properties, invariants) to make sure the item implements the model appropriately.
For example, a data abstraction should establish and preserve the invariants of the abstraction (as shown in the Rational arithmetic case study in Chapter 7).
Blackbox testers often must give attention to tricky practical issues such as appropriate error handling and datatype conversions.
In whitebox testing, the tester knows the internal structure, design, and implementation of the item being tested as well as the external requirements specification.
Note: This method is sometimes called openbox, clearbox transparentbox, glass box, codebased, or structural testing.
This method seeks to test every path through the code to make sure every input yields the expected result. It may use code analysis tools [2] to define the tests or special instrumentation of the item (e.g., a testing interface) to carry out the tests.
Whitebox testing is most applicable to unit and module testing (e.g., for use by the developers of the unit), but it can also be used for integration and system testing.
In graybox testing, the tester has partial knowledge of the internal structure, design, and requirements of the item being tested as well as the external requirements specification.
Note: “Gray” is the typical American English spelling. International or British English spells the word “grey”.
Graybox testing combines aspects of blackbox and whitebox testing. As in whitebox testing, the tester can use knowlege of the internal details (e.g., algorithms, data structures, or programming language features) of the item being tested to design the test cases. But, as in blackbox testing, the tester conducts the tests through the item’s regular interface.
This method is primarily used for integration testing, but it can be used for the other levels as well.
In ad hoc testing, the tester does not plan the details of the tests in advance as is typically done for the other methods. The testing is done informally and randomly, improvised according the creativity and experience of the tester. The tester strives to “break” the system, perhaps in unexpected ways.
This method is primarily used at the acceptance test level. It may be carried out by someone from outside the software development organization on behalf of the client of a software project.
Software testing types categorize tests by the purposes for which they are conducted. The Software Testing Fundamentals website [161] identifies several types of testing:
Smoke testing seeks to ensure that the primary functions work. It uses of a nonexhaustive set of tests to “smoke out” any major problems.
Functional testing seeks to ensure that the system satisfies all its functional requirements. (That is, does a given input yield the correct result?)
Usability testing seeks to ensure that the system is easily usable from the perspective of an enduser.
Security testing seeks to ensure that the system’s data and resources are protected from possible intruders by revealing any vulnerabilities in the system
Performance testing seeks to ensure that the system meets its performance requirements under certain loads.
Regression testing seeks to ensure that software changes (bug fixes or enhancements) do not break other functionality.
Compliance testing seeks to ensure the system complies to required internal or external standards.
In this book, we are primarily interested in functional testing.
A tester can conduct some type of testing during some stage of software development using some method. For example,
a test team might conduct functional testing (a type) at the system testing level using the blackbox testing method to determine whether the system performs correctly
a programmer might do smoke testing (a type) of the code at the module testing level using the whitebox testing method to find and resolve major shortcomings before proceeding with more complete functional testing
As noted above, in this book we are primarily interested in applying functional testing (type) techniques at the unit, module, or integration testing levels using blackbox or graybox testing methods. We are also interested in automating our tests.
The traditional software development process follows a designcodetest cycle. The developers create a design to satisfy the requirements, then implement the design as code in a programming language, and then test the code.
Testdriven development (TDD) reverses the traditional cycle; it follows a testcodedesign cycle instead. It uses a test case to drive the writing of code that satisfies the test. The new code drives the restructuring (i.e., refactoring) of the code base to evolve a good design. The goal is for the design and code to grow organically from the tests [10,112].
Beck describes the following “algorithm” for TDD [10].
Add a test for a small, unmet requirement.
If there are no unmet requirements, stop. The program is complete.
Run all the tests.
If no tests fail, go to step 1.
Write code to make a failing test succeed.
Run all the tests.
If any test fails, go to step 3.
Refactor the code to create a “clean” design.
Run all the tests.
If any test fails, go to step 3.
Go to step 1 to start a new cycle.
Refactoring [77] (step 5) is critical for evolving good designs and good code. It involves removing duplication, moving code to provide a more logical structure, splitting apart existing abstractions (e.g., functions, modules, and data types), creating appropriate new procedural and data abstractions, generalizing constants to variables or functions, and other code transformations.
TDD focuses on functionaltype unit and module testing using blackbox and graybox methods. The tests are defined and conducted by the developers, so the tests may not cover the full functional requirements needed at the higher levels. The tests often favor “happy path” tests over possible error cases [2].
This book presents programming language concepts using mostly small programs consisting of a few functions and modules. The book does not use TDD techniques directly, but it promotes similar rigor in analyzing requirements. As we have seen in previous chapters, this book focuses on design using contracts (i.e., preconditions, postconditions, and invariants), informationhiding modules, pure functions, and other features we study in later chapters.
As illustrated in Chapter 12, these methods are also compatible with functionaltype unit and module testing using blackbox and graybox methods.
Based on earlier work on the Test Automation Manifesto [127], Meszaros proposes several principles for test automation [126, Ch. 5]. These focus primarily on unit and module testing. The principles include the following:
Write the tests first.
This principle suggests that developers should use TestDriven Development (TDD) [10] as described in Section 11.6.
Design for testability.
Developers should consider how to test an item while the item is being designed and implemented. This is natural when TDD is being used, but, even if TDD is not used, testability should be an important consideration during design and implementation. If code cannot be tested reliably, it is usually bad code.
The application of this principle requires judicious use of the abstraction techniques, such as those illustrated in Chapters 6 and 7 and in later chapters.
Use the front door first.
Testing should be done primarily through the standard public interface of the item being tested. A test involves invoking a standard operation and then verifying that the operation has the desired result. (In terms of the testing methods described in Section 11.5.2, this principle implies use of blackbox and graybox methods.)
Special testing interfaces and operations may sometimes be necessary, but they can introduce new problems. They make the item being tested more complex and costly to maintain. They promote unintentional (or perhaps intentional) overspecification of the item. This can limit future changes to the item—or at least it makes future changes more difficult.
Note: Overspecification means imposing requirements on the software that are not explicitly needed to meet the users’ actual requirements. For example, a particular order may be imposed on a sequence of data or activities when an arbitrary order may be sufficient to meet the actual requirements.
Communicate intent.
As with any other program, a test program should be designed, implemented, tested, and documented carefully.
However, test code is often more difficult to understand than other code because the reader must understand both the test program and the item being tested. The “big picture” meaning is often obscured by the mass of details.
Testers should ensure they communicate the intent of a set of tests. They should use a naming scheme that reveals the intent and include appropriate comments. They should use standard utility procedures from the testing framework or develop their own utilities to abstract out common activities and data.
Don’t modify the system under test.
Testers should avoid modifying a “completed” item to enable testing. This can break existing functionality and introduce new flaws. Also, if the tests are not conducted on the item to be deployed, then the results of the tests may be inaccurate or misleading.
As noted in principles above, it is better to “design for testability” from the beginning so that tests can be conducted through “the front door” if possible.
Keep tests independent.
A test should be designed and implemented to be run independently of all other tests of that unit or module. It should be possible to execute a set of tests in any order, perhaps even concurrently, and get the same results for all tests.
Thus each automated test should set up its needed precondition state, run the test, determine whether the test succeeds or fails, and ensure no artifacts created by the test affect any of the other tests.
If one item depends upon the correct operation of a second item, then it may be useful to test the second item fully before testing the first. This dependency should be documented or enforced by the testing program.
Isolate the system under test.
Almost all programs depend on some programming language, its standard runtime library, and basic features of the underlying operating system. Most modern software depends on much more: the libraries, frameworks, database systems, hardware devices, and other software that it uses.
As much as possible, developers and testers should isolate the system being tested from other items not being tested at that time. They should document the versions and configurations of all other items that the system under test depends on. They should ensure the testing environment controls (or at least records) what versions and configurations are used.
As much as practical, the software developers should encapsulate critical external dependencies within informationhiding components. This approach helps the developers to provide stable behavior over time. If necessary, this also enables the testers to substitute a “test double” for a problematic system.
A test double is a “testspecific equivalent” [126, Ch. 11, Ch. 23] that is substituted for some component upon which the system under test depends. It may replace a component that is necessary but which is not available for safe use in the testing environment. For example, testers might be testing on system that interacts with another that has not yet been developed.
Minimize test overlap.
Tests need to cover as much functionality of a system as possible, but it may be counterproductive to test the same functionality more than once. If the code for that functionality is defective, it likely will cause all the overlapping tests to fail. Following up on the duplicate failures takes time and effort that can better be invested in other testing work.
Minimize untestable code.
Some components cannot be tested fully using an automated test program. For example, code in graphical user interfaces (GUIs), in multithreaded programs, or in test programs themselves are embedded in contexts that may not support being called by other programs.
However, developers can design the system so that as much as possible is moved to separate components that can be tested in an automated fashion.
For example, a GUI can perhaps be designed as a “thin” interactive layer that sets up calls to an application programming interface (API) to carry out most of the work. In addition to being easier to test, such an API may enable other kinds of interfaces in addition to the GUI.
Keep test logic out of production code.
As suggested above, developers should “design for testability” through “the front door”. Code should be tested in a configuration that is as close as possible to the production configuration.
Developers and testers should avoid inserting special test
hooks into the code (e.g.,
if testing then doSomething
) that will not be active in the
production code. In addition to distorting the tests, such hooks can
introduce functional or security flaws into the production code and make
the program larger, slower, and more difficult to understand.
Verify one condition per test.
If one test covers multiple conditions, it may be nontrivial to determine the specific condition causing a failure. This is likely not a problem with a manual test carried out by a human; it may be an efficient use of time to do fewer, broader tests.
However, tests covering multiple conditions are an unnecessary complication for inexpensive automated tests. Each automated test should be “independent” of others, do its own setup, and focus on a single likely cause of a failure. ”
Test concerns separately.
The behavior of a large system consists of many different, “small” behaviors. Sometimes a component of the system may implement several of the “small” behaviors. Instead of focusing a test on broad concerns of the entire system, testers should focus a test on a narrow concern. The failure of such a test can help pinpoint where the problem is.
The key here is to “pull apart” the overall behaviors of the system to identify “small” behaviors that can be tested independently.
Ensure commensurate effort and responsibility.
Developing test code that follows all of these principles can exceed the time it took to develop the system under test. Such an imbalance is bad. Testing should take approximately the same time as design and implementation.
The developers may need to devote more time and effort to “designing for testability” so that testing becomes less burdensome.
The testers may need to better use existing tools and frameworks to avoid too much special testing code. The testers should consider carefully which tests can provide useful information and which do not. There is no need for a test if it does not help reduce risk.
This chapter (11) surveyed software testing concepts. Chapter 12 applies them to testing Haskell modules from Chapters 4 and 7.
TODO
I wrote this chapter in Summer 2018 for the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.
The discussion of the dimensions of software testing — levels, methods, and types — draws on the discussion on the Software Testing Fundamentals website [161] and other sources [2,16,69,139].
The presentation of the goals and principles of test automation draws on the ideas of Meszaros [126,127].
The description of TestDriven Development (TDD) “algorithm” is adapted from that of Beck [10] and Koskela [112].
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
Stakeholder, software requirements specification, test, test plan, testing dimensions (levels, methods, types), testing levels (unit, module, integration, system, and acceptance testing), testing methods (blackbox, whitebox, graybox, and ad hoc testing), input domain, test input, input domain equivalence classes, representatives of normal use or “happy path”, boundary values, covering the range of expected outputs, testing based on the specification model, error handling, datatype conversions, testing types (smoke testing, functional testing, usability testing, security testing, performance testing, regression testing, compliance testing), testdriven development (TDD), designcodetest vs. testcodedesign.
The goal of this chapter (12)is to illustrate the testing techniques by manually constructing test scripts for Haskell functions and modules. It builds on the concepts and techniques surveyed in Chapter 11.
We use two testing examples in this chapter:
the group of factorial functions from Chapters 4 and 9
The series of tests can be applied any of the functions.
the rational arithmetic modules from Chapter 7
Testers commonly organize unit tests on a system using the ArrangeActAssert pattern [10,112].
Arrange: Select input values from the input domain and construct appropriate “objects” to use in testing the test subject.
Act: Apply some operation from the test subject to appropriate input “objects”.
Assert: Determine whether or not the result satisfies the specification.
Each test should create the testspecific input “objects” it needs and remove those and any result “objects” that would interfere with other tests.
Note: In this chapter, we use the word “object” in a general sense of any data entity, not in the specific sense defined for objectbased programming.
In terms of the dimensions of testing described in Chapter 11, this section approaches testing of a group of Haskell functions as follows.
As an example, consider the set of seven factorial functions
developed in Chapters 4 and
9 (in source file Factorial.hs
). All have the
requirement to implement the mathematical function
fact$(n) = \prod_{i=1}^{i=n}\,i$
for any $n \geq 0$. The specification is ambiguous on what should be the result of calling the function with a negative argument.
To carry out blackbox testing, we must arrange our input values. The factorial function tests do not require any special testing “objects”.
We first partition the input domain. We identify two equivalence classes of inputs for the factorial function:
the set of nonnegative integers for which the mathematical
function is defined and the Haskell function returns that value within
the positive Int
range
the set of nonnegative integers for which the mathematical
function is defined but the Haskell function returns a value that
overflows the Int
range
The class 2 values result are errors, but integer overflow is typically not detected by the hardware.
We also note that the negative integers are outside the range of the specification.
Next, we select the following values inside the “lower” boundary of class 1 above:
Then we choose representative values within class 1:
Note: The choice of two representative values might be considered a violation of the “minimize test overlap” principle from Chapter 11. So it could be acceptable to drop the input of 2. Of course, we could argue that we should check 2 as a possible boundary value.
We also select the value 1, which is just outside the lower boundary implied by the $n \geq 0$ requirement.
All of the factorial functions have the type signature (where N
is
1
, 2
, 3
, 4
,
4'
, 5
, or 6
):
factN :: Int > Int
Thus the factN
functions also
have an “upper” boundary that depends on the maximum value of the Int
type on a
particular machine. The author is testing these functions on a machine
with 64bit, two’s complement integers. Thus the largest integer whose
factorial is less than
$2^{63}$
is 20.
We thus select input the following input values:
20, which is just inside the upper boundary of class 1
21, which is just outside class 1 and inside class 2
We can test a factorial function at a chosen input value by simply applying the function to the value such as the following:
0 fact1
A Haskell function has no side effects, so we just need to examine the integer result returned by the function to determine whether it satisfies the function’s specification.
We can test the result of a function by stating a Boolean expression—an assertion—that the value satisfies some property that we want to check.
In simple cases like the factorial function, we can just compare the
actual result for equality with the expected result. If the comparison
yields True
, then the
test subject “passes” the test.
0 == 1 fact1
There are testing frameworks for Haskell (e.g., HUnit [90], QuickCheck [89], or Tasty [91]), but, in this section, we manually develop a simple test script.
We can state a Haskell IO
program to
print the test and whether or not it passes the test. (Simple input and
output will eventually be discussed in a Chapter
10. For now, see the Haskell
Wikibooks [179] page on “Simple
input and output”.)
Below is a Haskell IO
script that
tests class 1 boundary values 0 and 1 and “happy path” representative
values 2 and 5.
pass :: Bool > String
True = "PASS"
pass False = "FAIL"
pass
main :: IO ()
= do
main putStrLn "\nTesting fact1"
putStrLn ("fact1 0 == 1: " ++ pass (fact1 0 == 1))
putStrLn ("fact1 1 == 1: " ++ pass (fact1 1 == 1))
putStrLn ("fact1 2 == 2: " ++ pass (fact1 2 == 2))
putStrLn ("fact1 5 == 120: " ++ pass (fact1 5 == 120))
The do
construct
begins a sequence of IO
commands.
The IO
command putStrLn
outputs a string to the standard output followed by a newline
character.
Testing a value below the lower boundary of class 1 is tricky. The
specification does not require any particular behavior for 1. As we saw
in Chapter 4, some of the
function calls result in overflow of the runtime stack, some fail
because all of the patterns fail, and some fail with an explicit error
call.
However, all these trigger a Haskell exception.
Our test script can catch
these
exceptions using the following code.
putStrLn ("fact1 (1) == 1: "
++ pass (fact1 (1) == 1))
`catch` (\(StackOverflow)
> putStrLn ("[Stack Overflow] (EXPECTED)"))
`catch` (\(PatternMatchFail msg)
> putStrLn ("[Pattern Match Failure]\n...."
++ msg))
`catch` (\(ErrorCall msg)
> putStrLn ("[Error Call]\n...." ++ msg))
To catch the exceptions, the program needs to import the module Control.Exception
from the Haskell library.
import Prelude hiding (catch)
import Control.Exception
By catching the exception, the test program prints an appropriate error message and then continues with the next test; otherwise the program would halt when the exception is thrown.
Testing an input value in class 2 (i.e., outside the boundary of class 1) is also tricky.
First, the values we need to test depend on the default integer
(Int
)
size on the particular machine.
Second, because the actual value of the factorial is outside the
Int
range, we cannot express the test with Haskell Int
s.
Fortunately, by converting the values to the unbounded Integer
type,
the code can compare the result to the expected value.
The code below tests input values 20 and 21.
putStrLn ("fact1 20 == 2432902008176640000: "
++ pass (toInteger (fact1 20) ==
2432902008176640000))
putStrLn ("fact1 21 == 51090942171709440000: "
++ pass (toInteger (fact1 21) ==
51090942171709440000)
++ " (EXPECT FAIL for 64bit Int)" )
The above is a blackbox unit test. It is not specific to any one of
the seven factorial functions defined in Chapters 4 and 9. (These are
defined in the source file Factorial.hs
.) The series of tests
can be applied any of the functions.
The test script for the entire set of functions from Chapters
4 and
9 (and others) are in
the source file TestFactorial.hs
.
In terms of the dimensions of testing described in Chapter 11, this section approaches testing of Haskell modules as follows.
Normally, modulelevel testing requires that unitlevel testing be done for each function first. In cases where the functions within a module are strongly coupled, unitlevel and modulelevel testing may be combined into one phase.
For this section, we use the rational arithmetic example from Chapter 7.
In the rational arithmetic example, we define two abstract
(informationhiding) modules: RationalRep
and Rational
.
Given that the Rational
module depends on the RationalRep
module, we first consider testing the latter.
Chapter 7 defines the abstract
module RationalRep
and presents two distinct implementations, RationalCore
and RationalDeferGCD
.
The two implementations differ in how the rational numbers are
represented using data type Rat
. (See
source files RationalCore.hs
and RationalDeferGCD.hs
.)
Consider the public function signatures of RationalRep
(from Chapter 7):
makeRat :: Int > Int > Rat
numer :: Rat > Int
denom :: Rat > Int
zeroRat :: Rat
showRat :: Rat > String
Because the results of makeRat
and zeroRat
and the inputs to numer
, denom
, and showRat
are abstract, we cannot test
them directly as we did the factorial functions Section 12.3. For example, we cannot just call
makeRat
with two integers and
compare the result to some specific concrete value. Similarly, we cannot
test numer
and denom
directly by providing them some
specific input value.
However, we can test both through the abstract interface, taking advantages of the interface invariant.
RationalRep Interface Invariant (from Chapter 7):
: For any valid Haskell rational number r
, all the following hold:
 `r`{.haskell} $\in$ `Rat`{.haskell}
 `denom r > 0`{.haskell}
 if `numer r == 0`{.haskell}, then `denom r == 1`{.haskell}
 `numer r`{.haskell} and `denom r`{.haskell} are relatively prime
 the (mathematical) rational number value is
$\frac{\texttt{numer r}}{\texttt{denom r}}$
The invariant allows us to check combinations of the functions to see
if they give the expected results. For example, suppose we define x'
and y'
as follows:
= numer (makeRat x y)
x' = denom (makeRat x y) y'
Then the interface invariant and contracts for makeRat
, numer
, and denom
allow us to infer that the
(mathematical) rational number values
$\frac{\texttt{x'}}{\texttt{y'}}$
and
$\frac{\texttt{x}}{\texttt{y}}$
are equal.
This enables us to devise pairs of test assertions such as
1 2) == 1
numer (makeRat 1 2) == 2 denom (makeRat
and
4 (2)) == 2
numer (makeRat 4 (2)) == 1 denom (makeRat
to indirectly test the functions in terms of their interactions with each other. All the tests above should succeed if the module is designed and implemented according to its specification.
Similarly, we cannot directly test the private functions signum'
, abs'
, and gcd'
. But we try to choose inputs
the tests above to cover testing of these functions. (Private functions
should be tested as the module is being developed to detect any more
problems.)
To conduct blackbox testing, we must arrange the input values we
wish to test. The module tests do not require any special test objects,
but each pair of tests both create a Rat
object
with makeRat
and select its
numerator and denominator with numer
and denom
.
However, for convenience, we can define the following shorter names for constants:
= (maxBound :: Int)
maxInt = (minBound :: Int) minInt
TODO: Draw a diagram as discussed
Each pair of tests has two Int
parameters—the x
and y
parameters of makeRat
. Thus we can visualize the
input domain as the integer grid points on an xy
coordinate
plane using the usual rectangular layout from high school algebra.
We note that any input xy
value
along the x
axis does not
correspond to a rational number; the pair of integer values does not
satisfy the precondition for makeRat
and thus result in an error
exception.
For the purposes of our tests, we divide the rest of the plane into the following additional partitions (equivalence classes):
the y
axis
Input arguments where x == 0
may require special processing because of the required unique
representation for rational number zero.
each quadrant of the plane (excluding the axes)
The xy
values in
different quadrants may require different processing to handle the y > 0
and “relatively prime” aspects of the interface invariant.
Given that the module uses the finite integer type Int
, we bound
the quadrants by the maximum and minimum integer values along each
axis.
We identify the following boundary values for special attention in our tests.
Input pairs along the x
axis are outside any of the
partitions.
Input pairs composed of integer values 0, 1, and 1 are on the axes or just inside the “corners” of the quadrants . In addition, these are special values in various mathematical properties.
Input pairs composed of the maximum Int
(maxInt
) and minimum Int
(minInt
) values may be near the outer
bounds of the partitions.
Note: If the machine’s integer arithmetic uses the two’s complement
representation, then minInt
can
cause a problem with overflow because its negation is not in Int
. Because
of overflow, minInt == minInt
.
So we should check both minInt
and maxInt
in
most cases.
In addition, we identify representative values for each quadrant. Although we do not partition the quadrants further, in each quadrant we should choose some input values whose (mathematical) rational number values differ and some whose values are the same.
Thus we choose the following (x,y)
input pairs for testing:
(0,0), (1,0), and (1,0) as error inputs along the x
axis
(0,1), (0,1), (0,9), and (0,9) as inputs along the y
axis
(1,1), (9,9), and (maxInt
,maxInt
) as inputs from the first
quadrant and (1,1), (9,9), and (maxInt
,maxInt
) as
inputs from the third quadrant, all of whom have the same rational
number value
$\frac{1}{1}$.
We also test input pairs (minInt
,minInt
) and (minInt
,minInt
),
cognizant that the results might depend upon the machine’s integer
representation.
(1,1), (9,9), and (maxInt
,maxInt
) as inputs from the second
quadrant and (1,1), (9,9), and (maxInt
,maxInt
) as
inputs from the fourth quadrant, all of whom have the same rational
number value
$\frac{1}{1}$.
We also test input pairs (minInt
,minInt
) and (minInt
,minInt
),
cognizant that the results might depend upon the machine’s integer
representation.
(3,2) and (12,8) as inputs from the first quadrant and (3,2) and (12,8) as inputs from the third quadrant, all of whom have the same rational number value $\frac{3}{2}$.
(3,2) and (12,8) as inputs from the second quadrant and (3,2) and (12,8) as inputs from the fourth quadrant, all of whom have the same rational number value $\frac{3}{2}$.
(maxInt
,1), (maxInt
,1), (maxInt
,1) and
(maxInt
,1) as
input values in the “outer corners” of the quadrants.
We also test input pairs (minInt
,1) and (minInt
,1), cognizant that the results
might depend upon the machine’s integer representation.
As we identified in the introduction to this example, we must carry out a pair of actions in our tests. For example,
12 8) numer (makeRat
and
12 8) denom (makeRat
for the test of the input pair (12,8).
Note: The code above creates each test object (e.g., makeRat 12 8
)
twice. These could be created once and then used twice to make the tests
run slightly faster.
The results of the test actions must then be examined to determine
whether they have the expected values. In the case of the makeRatnumerdenom
tests, it is sufficient to compare the result for equality with the
expected result. The expected result must satisfy the interface
invariant.
For the two actions listed above, the comparison are
12 8) == 3 numer (makeRat
and
12 8) == 2 denom (makeRat
for the test of the input pair (12,8).
As with the factorial functions in Section 12.3, we can bring the various test
actions together into a Haskell IO
program.
The excerpt below shows some of the tests.
pass :: Bool > String
True = "PASS"
pass False = "FAIL"
pass
main :: IO ()
=
main do
 Test 3/2
putStrLn ("numer (makeRat 3 2) == 3: " ++
3 2) == 3))
pass (numer (makeRat putStrLn ("denom (makeRat 3 2) == 2: " ++
3 2) == 2))
pass (denom (makeRat  Test 3/2
putStrLn ("numer (makeRat (3) (2)) == 3: " ++
3) (2)) == 3))
pass (numer (makeRat (putStrLn ("denom (makeRat (3) (2)) == 2: " ++
3) (2)) == 2))
pass (denom (makeRat ( Test 12/8
putStrLn ("numer (makeRat 12 8) == 3: " ++
12 8) == 3))
pass (numer (makeRat putStrLn ("denom (makeRat 12 8) == 2: " ++
12 8) == 2))
pass (denom (makeRat  Test 12/8
putStrLn ("numer (makeRat (12) (8)) == 3: " ++
12) (8)) == 3))
pass (numer (makeRat (putStrLn ("denom (makeRat (12) (8)) == 2: " ++
12) (8)) == 2))
pass (denom (makeRat ( Test 0/0
putStrLn ("makeRat 0 0 is error: "
++ show (makeRat 0 0))
`catch` (\(ErrorCall msg)
> putStrLn ("[Error Call] (EXPECTED)\n"
++ msg))
The first four pairs of tests above check the test inputs (3,2), (3,2), (12,8), and (12,8). These are four test inputs, drawn from the first and third quadrants, that all have the same rational number value $\frac{3}{2}$.
The last test above checks whether the error pair (0,0) responds with an error exception as expected.
For the full test script (including tests of showRat
) examine the source file TestRatRepCore.hs
or TestRatRepDefer.hs
.
So far, the tests have assumed that any rational number object passed
as an argument to numer
, denom
, and showRat
is an object returned by makeRat
.
However, the encapsulation of the data type Rat
within a
RationalRep
module is just a convention. Rat
is really
an alias for (Int,Int)
.
The alias is exposed when the module is imported.
A user could call a function and directly pass an integer pair. If the integer pair does not satisfy the interface invariant, then the functions might not return a valid result.
For example, if we call numer
with the invalid rational number value (1,0), what is returned?
Because this value is outside the specification for RationalRep
,
each implementation could behave differently. In fact, RationalCore
returns the first component of the tuple and RationalDeferGCD
throws a “divide by zero” exception.
The test scripts include tests of the invalid value (1,0) for each of
the functions numer
, denom
, and showRat
.
A good solution to this broken encapsulation problem is (a) to change
Rat
to a
userdefined type and (b) only export the type name but not its
components. Then the Haskell compiler will enforce the encapsulation we
have assumed. We discuss approach in later chapters.
TODO: Write section
The interface to the module Rational
consists of the functions negRat
, addRat
, subRat
, mulRat
, divRat
, and eqRat
, the RationalRep
module’s interface. It does not add any new data types, constructors, or
destructors.
The Rational
abstract module’s functions preserve the interface invariant for the
RationalRep
abstract module, but it does not add any new components to the
invariant.
TODO: Write section
TODO: Draw a diagram to help visualize input domain
TODO: Write section
TODO: Write section
TODO: Write section
TODO: Discuss TestRational1.hs
and TestRational2.hs
TODO: Update after completing chapter
I designed and implemented the Rational
and
RationalCore
modules using the approach described in the early sections of Chapter
7, doing somewhat ad hoc testing of the
modules with the REPL. I later developed the RationalDeferGCD
module, abstracting from the RationalCore
module. After that, I wrote Chapter 7
to describe the example and the development process. Even later, I
constructed the systematic test scripts and wrote Chapters
11 and 12 (this chapter).
As I am closing out the discussion of this example, I find it useful to reflect upon the process.
The problem seemed quite simple, but I learned there are several subtle issues in the problem and the modules developed to solve it. As the saying goes, “the devil is in the details”.
In my initial development and testing of these simple modules, I got the “happy paths” right and covered the primary error conditions. Although singer Bobby McFerrin’s song “Don’t Worry, Be Happy” may give good advice for many life circumstances, it should not be taken too literally for software development and testing.
In writing both Chapter 7 and this chapter, I realized that my
statements of the preconditions, postconditions, and interface
invariants of RationalRep
abstraction needed to be reconsidered and restated more carefully.
Specifying a good abstract interface for a family of modules is
challenging.
In developing the systematic test scripts, I encountered other issues I had either not considered sufficiently or overlooked totally:
the full implications of using the finite data Int
data type
for the rational arithmetic modules
the impact of the underlying integer arithmetic representation (e.g., as two’s complement) on the Haskell code
the effects of calls of functions like numer
, denom
, and showRat
with invalid input
data
a subtle violation of the interface invariant in the RationalDeferGCD
implementations of makeRat
and
showRat
the value of a systematic input domain partitioning for both developing good tests and understanding the problem
It took me much longer to develop the systematic tests and document them than it did to develop the modules initially. I clearly violated the Meszaros’s final principle, “ensure commensurate effort and responsibility” described in the previous chapter (also in Mesazaros [126, Ch. 5]).
For future programming, I learned I need to pay attention to other of Meszaros’s principles such as “design for testability”, “minimize untestable code”, “communicate intent”, and perhaps “write tests first” or at least to develop the tests handinhand with the program.
Chapters 11 and 12 examined software testing concepts and applied them to testing Haskell functions and modules from Chapters 4 and 7.
So far we have limited our examples mostly to primitive types. In Chapters 13 and 14, we explore firstorder, polymorphic list programming in Haskell.
The source code for the group of factorial functions from Chapters
4 and
9 is in following
files:
Factorial.hs
, the source code for the
functions
TestFactorial.hs
, the source code for
the factorial test script
The source code for the rational arithmetic modules from Chapter 7 is in following files:
RationalCore.hs
and RationalDeferGCD.hs
, the source code
for the two implementations of the “RationalRep” abstract
module
TestRatRepCore.hs
and TestRatRepDefer.hs
, the test scripts
for the two above implementations of the “RationalRep” abstract
module
Rational1.hs
and Rational2.hs
, the source code for the
Rational
arithmetic module paired with the two above implementations of the
“RationalRep” abstract module
TestRational1.hs
and TestRational2.hs
, the test scripts
for the Rational
module paired with the two “RationalRep” implementations
Using the approach of this chapter, develop a blackbox
unittesting script for the fib
and fib2
Fibonacci functions
from Chapter 9. Test the functions with your script.
Using the approach of this chapter, develop a blackbox
unittesting script for the expt
, expt2
, and expt3
exponentiation functions from
Chapter 9. Test the functions with your script.
Using the approach of this chapter, develop a blackbox
unit/moduletesting script for the module Sqrt
from
Chapter 6. Test the module with your script.
Using the approach of this chapter, develop a blackbox unit/moduletesting script for the linesegment modules developed in exercises 13 of Chapter 7. Test the module with your script.
I wrote this chapter in Summer 2018 for the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.
The presentation builds on the concepts and techniques surveyed in the Chapter 11, which was written at the same time.
The presentation and use of the ArrangeActAssert pattern draws on the discussion in Beck [10] and Koskela [112].
The testing examples draw on previously existing function and (simple) test script examples and on discussion of the examples in Chapters 4 and 7. However, I did redesign and reimplement the test scripts to be more systematic and to follow the discussion in this new chapter.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
Test, testing level, testing method, testing type, unit and module
testing (levels), blackbox and graybox testing (methods), functional
testing (type), arrangeactassert, input domain, input partitioning,
representative values (for equivalence classes), boundary values,
testing based on the specification, Haskell IO
program,
do
,
putStrLn
,
exceptions.
This chapter introduces the list data type and develops the fundamental programming concepts and techniques for firstorder polymorphic functions to process lists.
The goals of the chapter are to:
introduce Haskell syntax and semantics for programming constructs related to polymorphic list data structures
examine correct Haskell functional programs consisting of firstorder polymorphic functions that solve problems by processing lists and strings
explore methods for developing Haskell listprocessing programs that terminate and are efficient and elegant
examine the concepts and use of data sharing in lists
The Haskell module for this chapter is in ListProg.hs
.
As we have seen, to do functional programming, we construct programs from collections of pure functions. Given the same arguments, a pure function always returns the same result. The function application is thus referentially transparent.
Such a pure function does not have side effects. It does not modify a variable or a data structure in place. It does not throw an exception or perform input/output. It does nothing that can be seen from outside the function except return its value.
Thus the data structures in purely functional programs must be immutable, not subject to change as the program executes.
Functional programming languages often have a number of immutable data structures. However, the most salient one is the list.
We mentioned the Haskell list and string data types in Chapter 5. In this chapter, we look at lists in depth. Strings are just special cases of lists.
[t]
The primary builtin 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 the notation [t]
to denote a list of zero or more
elements of type t
.
A list is is hierarchical data structure. It is either empty or it is a pair consisting of a head element and a tail that is itself a list of elements.
The Haskell list is an example of an algebraic data type. We discuss that concept in Chapter 21.
A matching pair of empty square brackets ([]
), pronounced “nil”, represents the
empty list.
A colon (:
), pronounced
“cons”, represents the list constructor operation between a
head element on the left and a tail list on the
right.
Example lists include:
[]2:[]
3:(2:[])
The Haskell language adds a bit of syntactic sugar to make expressing lists easier. (By syntactic sugar, we mean notation that simplifies expression of a concept but that adds no new functionality to the language. The new notation can be defined in terms of other notation within the language.)
The cons operations binds from the right. Thus
5:(3:(2:[]))
can be written as:
5:3:2:[]
We can write this as a commaseparated sequence enclosed in brackets as follows:
5,3,2] [
Haskell supports two list selector functions, head
and tail
, such
that
head (h:t)
$\Longrightarrow$h
where h
is the head element
of list, and
tail (h:t)
$\Longrightarrow$t
where t
is the tail list.
Aside: Instead of head
, Lisp
uses car
and other languages use
hd
, first
, etc. Instead of tail
, Lisp
uses cdr
and other languages use
tl
, rest
, etc.
The Prelude library supports a number of other useful functions on
lists. For example, length
takes a
list and returns its length.
Note that lists are defined inductively. That is, they are
defined in terms of a base element []
and the list constructor operation
cons (:
). As you
would expect, a form of mathematical induction can be used to prove that
listmanipulating functions satisfy various properties. We will discuss
in Chapter 25.
String
In Haskell, a string is treated as a list of characters.
Thus the data type String
is
defined as a type synonym:
type String = [Char]
In addition to the standard list syntax, a String
literal
can be given by a sequence of characters enclosed in double quotes. For
example, "oxford"
is shorthand for [’o’,’x’,’f’,’o’,’r’,’d’]
`.
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.
Example: "Hello\nworld!\n"
is a string that has two newline characters embedded.
Example: "\12\&3"
represents the list ['\12','3']
.
Because strings are represented as lists, all of the Prelude functions for manipulating lists also apply to strings.
Consider a function to compute the length of a finite string:
len :: String > Int
= if s == [] then 0 else 1 + len (tail s) len s
Note that the argument string for the recursive application of len
is simpler (i.e., shorter) than
the original argument. Thus len
will eventually be applied to a []
argument and, hence, len
’s evaluation will terminate.
How efficient is this function (i.e., its time and space complexity)?
Consider the evaluation of the expression len "five"
using the evaluation model from Chapter
8.
len "five"
$\Longrightarrow$
if "five" == [] then 0 else 1 + len (tail "five")
$\Longrightarrow$
if False then 0 else 1 + len (tail "five")
$\Longrightarrow$
1 + len (tail "five")
$\Longrightarrow$
1 + len "ive"
$\Longrightarrow$
1 + (if "ive" == [] then 0 else 1 + len (tail "ive"))
$\Longrightarrow$
1 + (if False then 0 else 1 + len (tail "ive"))
$\Longrightarrow$
1 + (1 + len (tail "ive"))
$\Longrightarrow$
1 + (1 + len "ve")
$\Longrightarrow$
1 + (1 + (if "ve" == [] then 0 else 1 + len (tail "ve")))
$\Longrightarrow$
1 + (1 + (if False then 0 else 1 + len (tail "ve")))
$\Longrightarrow$
1 + (1 + (1 + len (tail "ve")))
$\Longrightarrow$
1 + (1 + (1 + len "e"))
$\Longrightarrow$
1 + (1 + (1 + (if "e" == [] then 0 else 1 + len (tail "e"))))
$\Longrightarrow$
1 + (1 + (1 + (if False then 0 else 1 + len (tail "e"))))
$\Longrightarrow$
1 + (1 + (1 + (1 + len (tail "e"))))
$\Longrightarrow$
1 + (1 + (1 + (1 + len "")))
$\Longrightarrow$
1 + (1 + (1 + (1 + (if "" == [] then 0 else 1 + len (tail "")))))
$\Longrightarrow$
1 + (1 + (1 + (1 + (if True then 0 else 1 + len (tail "")))))
$\Longrightarrow$
1 + (1 + (1 + (1 + 0)))
$\Longrightarrow$
1 + (1 + (1 + 1))
$\Longrightarrow$
1 + (1 + 2)
$\Longrightarrow$
1 + 3
$\Longrightarrow$
4
If n
is the length of the
list xs
, then len s
requires 4*n
reduction steps involving the recursive leg (first 16 steps above), 2
steps involving the nonrecursive leg (next 2 steps above), and n+1
steps involving the additions (last five steps). Thus, the evaluation
requires 5*n+3
reduction steps. Hence, the number of reduction steps in proportional to
the length of the input list. The time complexity of the function is
thus O(length s
{.haskell]).
The largest expression above is
1 + (1 + (1 + (1 + (if "" == [] then 0 else 1 + len (tail "")))))
This expression has n + 2
(6) binary operators, 2 unary operators, and 1 ternary operator.
Counting arguments (as discussed in Chapter
8), it has size 2 * (n + 2) + 2 + 3
(or 2*n+9
).
Hence, the amount of space required (given lazy evaluation) is also
proportional to the length of the input list. The space complexity of
the function is thus O(length s
).
The above definition of len
only works for strings. How can we make it work for a list of integers
or other elements?
For an arbitrary type a
, we want len
to take objects of type [a]
and return an Int
value.
Thus its type signature could be:
len :: [a] > Int
If a
is a variable name (i.e., it begins with a
lowercase letter) that does not already have a value, then the type
expression a
used as above is a type variable; it
can represent an arbitrary type. All occurrences of a type variable
appearing in a type signature must, of course, represent the
same type.
An object whose type includes one or more type variables can be thought of having many different types and is thus described as having a polymorphic type. (The next subsection gives more detail on polymorphism in general.)
Polymorphism and firstclass functions are powerful abstraction mechanisms: they allow irrelevant detail to be hidden.
Other examples of polymorphic list functions from the Prelude library include:
head :: [a] > a
tail :: [a] > [a]
(:) :: a > [a] > [a]
In the factorial examples in Chapter 4, we used integer patterns and guards to break out various cases of a function definition into separate equations. Lists and other data types may also be used in patterns.
Pattern matching helps enable the form of the algorithm to match the form of the data structure. Or, as others may say, it helps in following types to implementations.
This is considered elegant. It is also pragmatic. The structure of the data often suggests the algorithm that is needed for a task.
In general, lists have two cases that need to be handled: the empty list and the nonempty list. Breaking a definition for a listprocessing function into these two cases is usually a good place to begin.
sum'
Consider a function sum'
to sum all the elements in a finite list of integers. That is, if the
list is
$v_{1}, v_{2}, v_{3}, \cdots, v_{n}$,
then the sum of the list is the value resulting from inserting the addition operator between consecutive elements of the list:
$v_{1} + v_{2} + v_{3} + \cdots + v_{n}$.
Because addition is an associative operation (that is, $(x + y) + z = x + (y + z)$ for any integers $x$, $y$, and $z$), the above additions can be computed in any order.
What is the sum of an empty list?
Because there are no numbers to add, then, intuitively, zero seems to be the proper value for the sum.
In general, if some binary operation is inserted between the elements of a list, then the result for an empty list is the identity element for the operation. Since $0 + x = x = x + 0$ for all integers $x$, zero is the identity element for addition.
Now, how can we compute the sum of a nonempty list?
Because a nonempty list has at least one element, we can remove one element and add it to the sum of the rest of the list. Note that the “rest of the list” is a simpler (i.e., shorter) list than the original list. This suggests a recursive definition.
The fact that Haskell defines lists recursively as a cons of a head element with a tail list suggests that we structure the algorithm around the structure of the beginning of the list.
Bringing together the two cases above, we can define the function
sum'
in Haskell as follows.
This is similar to the Prelude function sum
.
{ Function sum' sums a list of integers. It is similar to
function sum in the Prelude.
}
sum' :: [Int] > Int
= 0  nil list
sum' [] :xs) = x + sum' xs  nonnil list sum' (x
As noted previously, all of the text between the symbol “
” and the
end of the line represents a comment; it is ignored by the
Haskell interpreter.
The text enclosed by the {
and }
is a block
comment, that can extend over multiple lines.
This definition uses two legs. The equation in the first leg is used for nil list arguments, the second for nonnil arguments.
Note the (x:xs)
pattern
in the second leg. The “:
” denotes the
list constructor operation cons.
If this pattern succeeds, then the head element of the list argument
is bound to the variable x
and
the tail of the list argument is bound to the variable xs
. These bindings hold for the
righthand side of the equation.
The use of the cons in the pattern simplifies the expression of
the case. Otherwise the second leg would have to be stated using the
head
and
tail
selectors as follows:
= head xs + sum' (tail xs) sum' xs
We use the simple name x
to represent items of some type and the name xs
, the same name with an s
(for sequence) appended, to
represent a list of that same type. This is a useful convention (adopted
from the classic Bird and Wadler textbook [15]) that helps make a definition easier
to understand.
Remember that patterns (and guards) are tested in the order of occurrence (i.e., left to right, top to bottom). Thus, in most situations, the cases should be listed from the most specific (e.g., nil) to the most general (e.g., nonnil).
The length of a nonnil argument decreases by one for each
successive recursive application. Thus (assuming the list is finite)
sum'
will eventually be
applied to a []
argument and
terminate.
For a list consisting of elements 2, 4, 6, and 8, that is, 2:4:6:8:[]
,
function sum'
computes
2 + (4 + (6 + (8 + 0)))
giving the integer result 20.
Function sum'
is backward
linear recursive; its time and space complexity are both
O(n
), where n
is the length of the input
list.
We could, of course, redefine this to use a tailrecursive auxiliary
function. With tail call optimization, the recursion could be
converted into a loop. It would still be O(n
) in time
complexity (but with a smaller constant factor) but O(1) in space.
product'
Now consider a function product'
to multiply together a
finite list of integers.
The product of an empty list is 1 (which is the identity element for multiplication).
The product of a nonempty list is the head of the list multiplied by the product of the tail of the list, except that, if a 0 occurs anywhere in the list, the product of the list is 0.
We can thus define product'
with two base cases and
one recursive case, as follows. This is similar to the Prelude function
product
.
product' :: [Integer] > Integer
= 1
product' [] 0:_) = 0
product' (:xs) = x * product' xs product' (x
Note the use of the wildcard pattern underscore “_
” in the second leg above. This
represents a “don’t care” value. In this pattern it matches the tail,
but no value is bound; the righthand side of the equation does not need
the actual value.
0 is the zero element for the multiplication operation on integers. That is, for all integers $x$:
$0 * x = x * 0 = 0$
For a list consisting of elements 2, 4, 6, and 8, that is, 2:4:6:8:[]
,
function product'
computes:
2 * (4 * (6 * (8 * 1)))
which yields the integer result 384.
For a list consisting of elements 2, 0, 6, and 8, function product'
“short circuits” the
computation as:
2 * 0
Like sum'
, function product'
is backward linear
recursive; it has a worstcase time complexity of O(n
),
where
$n$
is the length of the input list. It terminates because the argument of
each successive recursive call is one element shorter than the previous
call, approaching the first base case.
As with sum'
, we could
redefine this to use a tailrecursive auxiliary function, which could
evaluate in O(n
) space with tail call optimization.
Note that sum'
and product'
have similar
computational patterns. In Chapter
15, we look at how to capture the
commonality in a single higherorder function.
length'
As another example, consider the function for the length of a finite
list that we discussed earlier (as len
). Using list patterns we can
define length’
as follows:
length' :: [a] > Int
= 0  nil list
length' [] :xs) = 1 + length' xs  nonnil list length' (_
Note the use of the wildcard pattern underscore “_
”. In
this pattern it matches the head, but no value is bound; the righthand
side of the equation does not need the actual value.
Given a finite list for its argument, does this function terminate? What are its time and space complexities?
This definition is similar to the definition for length
in the
Prelude.
remdups
Consider the problem of removing adjacent duplicate elements from a list. That is, we want to replace a group of adjacent elements having the same value by a single occurrence of that value.
As with the above functions, we let the form of the data guide the form of the algorithm, following the type to the implementation.
The notion of adjacency is only meaningful when there are two or more of something. Thus, in approaching this problem, there seem to be three cases to consider:
The argument is a list whose first two elements are duplicates; in which case one of them should be removed from the result.
The argument is a list whose first two elements are not duplicates; in which case both elements are needed in the result.
The argument is a list with fewer than two elements; in which case the remaining element, if any, is needed in the result.
Of course, we must be careful that sequences of more than two duplicates are handled properly.
Our algorithm thus can examine the first two elements of the list. If they are equal, then the first is discarded and the process is repeated recursively on the list remaining. If they are not equal, then the first element is retained in the result and the process is repeated on the list remaining. In either case the remaining list is one element shorter than the original list. When the list has fewer than two elements, it is simply returned as the result.
If we restrict the function to lists of integers, we can define
Haskell function remdups
as
follows:
remdups :: [Int] > [Int]
:y:xs)
remdups (x x == y = remdups (y:xs)
 x /= y = x : remdups (y:xs)
= xs remdups xs
Note the use of the pattern (x:y:xs)
.
This pattern match succeeds if the argument list has at least two
elements: the head element is bound to x
, the second element to y
, and the tail list to xs
.
Note the use of guards to distinguish between the cases where the
two elements are equal (==
) and where
they are not equal (/=
).
In this definition the case patterns overlap, that is, a list with at least two elements satisfies both patterns. But since the cases are evaluated top to bottom, the list only matches the first pattern. Thus the second pattern just matches lists with fewer than two elements.
What if we wanted to make the list type polymorphic instead of just integers?
At first glance, it would seem to be sufficient to give remdups
the polymorphic type [a] > [a]
.
But the guards complicate the situation a bit.
Evaluation of the guards requires that Haskell be able to compare
elements of the polymorphic type a
for equality (==
) and
inequality (/=
). For some
types these comparisons may not be supported. (For example, suppose the
elements are functions.) Thus we need to restrict the polymorphism to
types in which the comparisons are supported.
We can restrict the range of types by using a context
predicate. The following type signature restricts the polymorphism of
type variable a
to the builtin
type class Eq
, the group
of types for which both equality (==
) and
inequality (/=
)
comparisons have been defined:
remdups :: Eq a => [a] > [a]
Another useful context is the class Ord
, which is
an extension of class Eq
. Ord
denotes
the class of objects for which the relational operators <
, <=
, >
, and
>=
have been defined in addition to ==
and /=
.
Note: Chapter 22 explores the concepts of type class, instances, and overloading in more depth.
In most situations the type signature can be left off the declaration
of a function. Haskell then attempts to infer an appropriate type. For
remdups
, the type inference
mechanism would assign the type Eq [a] => [a] > [a]
. However, in general, it is good practice to give explicit type
signatures.
Like the previous functions, remdups
is backward linear recursive;
it takes a number of steps that is proportional to the length of the
list. This function has a recursive call on both the duplicate and
nonduplicate legs. Each of these recursive calls uses a list that is
shorter than the previous call, thus moving closer to the base case.
Table 13.1 shows Haskell parameter patterns, corresponding arguments, and the results of the attempted match.
Pattern  Argument  Succeeds?  Bindings 

1 
1 
yes  none 
x 
1 
yes  x
$\leftarrow$
1 
(x:y) 
[1,2] 
yes  x
$\leftarrow$
1 , y
$\leftarrow$
[2] 
(x:y) 
[[1,2]] 
yes  x
$\leftarrow$
[1,2] , y
$\leftarrow$
[] 
(x:y) 
["olemiss"] 
yes  x
$\leftarrow$
"olemiss" , y
$\leftarrow$
[] 
(x:y) 
"olemiss" 
yes  x
$\leftarrow$
’o’ , y
$\leftarrow$
"lemiss" 
(1:x) 
[1,2] 
yes  x
$\leftarrow$
[2] 
(1:x) 
[2,2] 
no  none 
(x:_:_:y) 
[1,2,3,4,5,6] 
yes  x
$\leftarrow$
1 , y
$\leftarrow$
[4,5,6] 
[] 
[] 
yes  none 
[x] 
["Cy"] 
yes  x
$\leftarrow$
"Cy" 
[1,x] 
[1,2] 
yes  x
$\leftarrow$
2 
[x,y] 
[1] 
no  none 
(x,y) 
(1,2) 
yes  x
$\leftarrow$
1 , y
$\leftarrow$
2 
Suppose we have the declaration:
= [1,2,3] xs
As we learned in the data structures course, we can implement this
list as a singly linked list xs
with three cells with the values 1
, 2
, and 3
, as shown in
Figure 13.1.
Consider the following declarations (which are illustrated in Figure 13.1):
= 0:xs
ys = tail xs zs
where
0:xs
returns a list that has a new cell containing 0
in front of
the previous list
tail xs
returns the list consisting of the last two elements of xs
If the linked list xs
is
immutable (i.e., the values and pointers in the three cells cannot be
changed), then neither of these operations requires any copying.
The first just constructs a new cell containing 0
, links it to
the first cell in list xs
, and
initializes ys
with a reference
to the new cell.
The second just returns a reference to the second cell in list
xs
and initializes zs
with this reference.
The original list xs
is
still available, unaltered.
This is called data sharing. It enables the programming language to implement immutable data structures efficiently, without copying in many key cases.
Also, such functional data structures are persistent because existing references are never changed by operations on the data structure.
Consider evaluation of the expression head xs
. It
must create a copy of the head element (in this case 1
). The result
does not share data with the input list.
Similarly, the list returned by function remdups
(defined above) does not share
data with its input list.
head
and tail
What should tail
return if
the list is nil?
One choice is to return a nil list []
. However, it seems illogical for an
empty list to have a tail.
Consider a typical usage of the tail
function.
It is normally an error for a program to attempt to get the tail of an
empty list. Moreover, a program can efficiently check whether a list is
empty or not. So, in this case, it is better to consider
tail
a partial function.
Thus, Haskell defines both tail
and head
to have
the precondition that their parameters are nonnil lists. If we call
either with a nil list, then it will terminate execution with a standard
error message.
We can generalize tail
to a
function drop'
that removes
the first n
elements of a list
as follows, (This function is called drop
in the
Prelude.)
drop' :: Int > [a] > [a]
 n <= 0 = xs
drop' n xs = []
drop' _ [] :xs) = drop' (n1) xs drop' n (_
Consider the example:
drop 2 "oxford"
$\Longrightarrow \cdots$"ford"
This function takes a different approach to the “empty list” issue
than tail
does.
Although it is illogical to take the tail
of an
empty list, dropping the first element from an empty list seems subtly
different. Given that we often use drop'
in cases where the length of
the input list is unknown, dropping the first element of an empty list
does not necessarily indicate a program error.
Suppose instead that drop'
would trigger an error when
called with an empty list. To avoid this situation, the program might
need to determine the length of the list argument. This is inefficient,
usually requiring a traversal of the entire list to count the elements.
Thus the choice for drop'
to
return a nil is also pragmatic.
The drop'
function is
tail recursive. The result list shares space with the input list.
The drop'
function
terminates when either the list argument is empty or the integer
argument is 0 or negative. The function eventually terminates because
each recursive call both shortens the list and decrements the
integer.
What is the time complexity of drop'
?
There are two base cases.
For the first leg, the function must terminate in O(max 1 n
)
steps.
For the second leg, the function must terminate within O(length xs
)
steps. So the function must terminate within O(min (max 1 n) (length xs)
)
steps.
What is the space complexity of drop'
?
This tail recursive function evaluates in constant space when optimized.
Similarly, we can generalize head'
to a function take
that
takes a number n
and a list and
returns the first n
elements of
the list.
take' :: Int > [a] > [a]
 n <= 0 = []
take' n _ = []
take' _ [] :xs) = x : take' (n1) xs take' n (x
Consider the following questions for this function?
What is returned when the list argument is nil?
Does evaluation of this function terminate?
Does the result share data with the input?
Is the function tail recursive?
What are its time and space complexities?
Consider the example:
take 2 "oxford"
$\Longrightarrow \cdots$"ox"
This chapter (13) examined programming with the list data type using firstorder polymorphic functions. Chapter 14 continues the discussion of list programming, introducing infix operations and more examples.
The Haskell module for this chapter is in ListProg.hs
.
Answer the following questions for the take'
function defined in this
chapter:
Write a Haskell function maxlist
to compute the maximum value
in a nonempty list of integers. Generalize the function by making it
polymorphic, accepting a value from any ordered type.
Write a Haskell function adjpairs
that takes a list and returns
the list of all pairs of adjacent elements. For example, adjpairs [2,1,11,4]
returns [(2,1), (1,11), (11,4)]
.
Write a Haskell function mean
that takes a list of integers and
returns the mean (i.e., average) value for the list.
Write the following Haskell functions using tail recursion:
sum''
with same
functionality as sum'
product''
with
the same functionality as product'
In Summer 2016, I adapted and revised much of this work from previous work:
Chapter 5 of my Notes on Functional Programming with Haskell [42], which is influenced by Bird [13–15] and Wentworth [178]
My notes on Functional Data Structures (Scala) [50], which are based, in part, on chapter 3 of the book Functional Programming in Scala [29] and its associated materials [30,31]
In 2017, I continued to develop this work as Chapter 4, List Programming, of my 2017 Haskellbased programming languages textbook.
In Summer 2018, I divided the previous List Programming chapter into two chapters in the 2018 version of the textbook, now titled Exploring Languages with Interpreters and Functional Programming. Previous sections 4.14.4 became the basis for new Chapter 13 (this chapter), List Programming, and previous sections 4.54.8 became the basis for Chapter 14, Infix Operators and List Programming Examples. I moved the discussion of “kinds of polymorphism” to new Chapter 5 and “local definitions” to new Chapter 9.
I retired from the fulltime faculty in May 2019. As one of my postretirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional 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.
I maintain this chapter 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.
Type class (Eq
, Ord
, context
predicate), lists (polymorphic, immutable, persistent, data sharing,
empty/nil, nonempty), string, list and string operations (cons, head,
tail, pattern matching, wildcard pattern, length), inductive
definitions, operator binding, syntactic sugar, type synonym, type
variable, type signature, follow the types to implementations, let the
form of the data guide the form of the algorithm, associativity,
identity element, zero element, termination, time and space complexity,
adjacency,
This chapter introduces Haskell infix operations and continues to develop techniques for firstorder polymorphic functions to process lists.
The goals of the chapter are to:
introduce Haskell syntax and semantics for infix operations
examine correct Haskell functional programs consisting of firstorder polymorphic functions that solve problems by processing lists and strings
explore methods for developing Haskell listprocessing programs that terminate and are efficient and elegant.
The Haskell module for this chapter is in ListProgExamples.hs
.
In Haskell, a binary operation is a function of type t1 > t2 > t3
for some types t1
, t2
, and t3
.
We usually prefer to use infix syntax rather than prefix syntax to express the application of a binary operation. Infix operators usually make expressions easier to read; they also make statement of mathematical properties more convenient.
Often we use several infix operators in an expression. To ensure that
the expression is not ambiguous (i.e., the operations are done in the
desired order), we must either use parentheses to give the order
explicitly (e.g., ((y * (z+2)) + x)
)
or use syntactic conventions to give the order implicitly.
Typically the application order for adjacent operators of different
kinds is determined by the relative precedence of the
operators. For example, the multiplication (*
) operation
has a higher precedence (i.e., binding power) than addition (+
), so, in the
absence of parentheses, a multiplication will be done before an adjacent
addition. That is, x + y * z
is taken as equivalent to (x + (y * z))
.
In addition, the application order for adjacent operators of the same
binding power is determined by a binding (or
association) order. For example, the addition (+
) and
subtraction 
operations
have the same precedence. By convention, they bind more strongly to the
left in arithmetic expressions. That is, x + y  z
is taken as equivalent ((x + y)  z)
.
By convention, operators such as exponentiation (denoted by ^
) and cons
bind more strongly to the right. Some other operations (e.g.,
division and the relational comparison operators) have no default
binding order—they are said to have free binding.
Accordingly, Haskell provides the statements infix
, infixl
, and
infixr
for declaring a symbol to be an infix operator with free, left, and
right binding, respectively. The first argument of these statements give
the precedence level as an integer in the range 0 to 9, with 9 being the
strongest binding. Normal function application has a precedence of
10.
The operator precedence table for a few of the common operations from
the Prelude is shown below. We introduce the ++
operator in
the next subsection.
infixr 8 ^  exponentiation
infixl 7 *  multiplication
7 /  division
infix infixl 6 +,   addition, subtraction
infixr 5 :  cons
4 ==, /=, <, <=, >=, >  relational comparisons
infix infixr 3 &&  Boolean AND
infixr 2   Boolean OR
++
Suppose we want a function that takes two lists and returns their
concatenation, that is, appends the second list after the
first. This function is a binary operation on lists much like +
is a binary
operation on integers.
Further suppose we want to introduce the infix operator symbol ++
for the
append function. Since we want to evaluate lists lazily from their
heads, we choose right binding for both cons and ++
. Since
append is, in a sense, an extension of cons (:
), we give
them the same precedence:
infixr 5 ++
Consider the definition of the append function. We must define the
++
operation in terms of application of already defined list operations and
recursive applications of itself. The only applicable simpler operation
is cons.
As with previous functions, we follow the type to the implementation—let the form of the data guide the form of the algorithm.
The cons operator takes an element as its left operand and a list as its right operand and returns a new list with the left operand as the head and the right operand as the tail.
Similarly, ++
must take a
list as its left operand and a list as its right operand and return a
new list with the left operand as the initial segment and the right
operand as the final segment.
Given the definition of cons, it seems reasonable that an algorithm
for ++
must consider the structure of its left operand. Thus we consider the
cases for nil and nonnil left operands.
If the left operand is nil, then the function can just return the right operand.
If the left operand is a cons (that is, nonnil), then the result consists of the left operand’s head followed by the append of the left operand’s tail to the right operand.
In following the type to the implementation, we use the form of the
left operand in a pattern match. We define ++
as
follows:
infixr 5 ++
(++) :: [a] > [a] > [a]
++ xs = xs  nil left operand
[] :xs) ++ ys = x:(xs ++ ys)  nonnil left operand (x
Above we use infix patterns on the lefthand sides of the defining equations.
For the recursive application of ++
, the length
of the left operand decreases by one. Hence the left operand of a ++
application
eventually becomes nil, allowing the evaluation to terminate.
Consider the evaluation of the expression [1,2,3] ++ [3,2,1]
.
[1,2,3] ++ [3,2,1]
$\Longrightarrow$
1:([2,3] ++ [3,2,1])
$\Longrightarrow$
1:(2:([3] ++ [3,2,1]))
$\Longrightarrow$
1:(2:(3:([] ++ [3,2,1])))
$\Longrightarrow$
1:(2:(3:[3,2,1]))
$=$
[1,2,3,3,2,1]
The number of steps needed to evaluate xs ++ ys
is
proportional to the length of xs
, the left operand. That is, the
time complexity is O(n
), where n
is the length
xs
.
Moreover, xs ++ ys
only
needs to copy the list xs
. The
list ys
is shared between the
second operand and the result. If we did a similar function to append
two (mutable) arrays, we would need to copy both input arrays to create
the output array. Thus, in this case, a linked list is more efficient
than arrays!
Consider the following questions:
What is the precondition of xs ++ ys
?
Is ++
tail
recursive?
What is the space complexity of ++
?
The append operation has a number of useful algebraic properties, for example, associativity and an identity element.
Associativity of ++
: For any
finite lists xs
, ys
, and zs
, xs ++ (ys ++ zs) == (xs ++ ys) ++ zs
.
Identity for ++
: For any
finite list xs
, [] ++ xs = xs = xs ++ []
.
We will prove these and other properties in Chapter 25.
Mathematically, the list data type and the binary operation ++
form a kind
of abstract algebra called a monoid. Function ++
is
closed (i.e., it takes two lists and gives a list back), is
associative, and has an identity element.
Similarly, we can state properties of combinations of functions. We can prove these using techniques we study in Chapter 25. For example, consider the functions defined above in this chapter.
For all finite lists xs
,
we have the following distribution properties:
++ ys) = sum' xs + sum' ys
sum' (xs ++ ys) = product' xs * product' ys
product' (xs ++ ys) = length' xs + length' ys length' (xs
For all natural numbers n
and finite lists xs
,
take n xs ++ drop n xs = xs
!!
As another example of an infix operation, consider the list selection
operator !!
. The
expression xs!!n
selects
element n
of list xs
where the head is in position 0. It
is defined in the Prelude similar to the way !!
is defined
below:
infixl 9 !!
(!!) :: [a] > Int > a
!! n  n < 0 = error "!! negative index"
xs !! _ = error "!! index too large"
[] :_) !! 0 = x
(x:xs) !! n = xs !! (n1) (_
Consider the following questions concerning the element selection operator: