How to Design Programs

Last updated

How to Design Programs
How to Design Programs (front cover).jpg
Author Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi
CountryUnited States
Subject Computer programming
Genre Textbook
Publisher MIT Press
Publication date
February 12, 2001
Media typeprint
Pages720
ISBN 0-262-06218-6
LC Class QA76.6 .H697 2001
Website htdp.org

How to Design Programs (HtDP) is a textbook by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi on the systematic design of computer programs. MIT Press published the first edition in 2001, and the second edition in 2018, which is freely available online and in print. The book introduces the concept of a design recipe, a six-step process for creating programs from a problem statement. While the book was originally used along with the education project TeachScheme! (renamed ProgramByDesign), it has been adopted at many colleges and universities for teaching program design principles.

Contents

According to HtDP, the design process starts with a careful analysis of a problem statement with the goal of extracting a rigorous description of the kinds of data that the desired program consumes and produces. The structure of these data descriptions determines the organization of the program.

Then, the book carefully introduces data forms of progressively growing complexity. It starts with data of atomic forms and then progresses to compound forms, including data that can be arbitrarily large. For each kind of data definition, the book explains how to organize the program in principle, thus enabling a programmer who encounters a new form of data to still construct a program systematically.

Like Structure and Interpretation of Computer Programs (SICP), HtDP relies on a variant of the programming language Scheme. It includes its own programming integrated development environment (IDE), named DrRacket, which provides a series of programming languages. The first language supports only functions, atomic data, and simple structures. Each language adds expressive power to the prior one. Except for the largest teaching language, all languages for HtDP are functional programming languages.

Pedagogical basis

In the 2004 paper, The Structure and Interpretation of the Computer Science Curriculum, [1] the same authors compared and contrasted the pedagogical focus of How to Design Programs (HtDP) with that of Structure and Interpretation of Computer Programs (SICP). In the 14-page paper, the authors distinguish the pedagogic focus of HtDP from that of SICP, and show how HtDP was designed as a textbook to address some problems that some students and teachers had with SICP.

The paper introduces the pedagogical landscape surrounding the publication of SICP. The paper starts with a history and critique of SICP, followed by a description of the goal of the computing curriculum. It then describes the principles of teaching behind HtDP; in particular, the difference between implicit vs. explicit teaching of design principles. It then continues on to describe the role of Scheme and the importance of an ideal programming environment, and concludes with an extensive evaluation of content and student/faculty reaction to experience with SICP vs. HtDP.

One of the major focuses of the paper is the emphasis on the difference in required domain knowledge between SICP and HtDP. A chart in the paper compares major exercises in SICP and HtDP, and the related text describes how the exercises in the former require considerably more sophisticated domain knowledge than those of HtDP. The paper continues on to explain why this difference in required domain knowledge has resulted in certain students having confused domain knowledge with program design knowledge.

The paper claims the following four major efforts that the authors of HtDP have made to address perceived issues with SICP:

  1. HtDP addresses explicitly, rather than implicitly, how programs should be constructed.
  2. To make programming easier, the book guides students through five different knowledge levels corresponding to data definition levels of complexity.
  3. The book's exercises focus on program design guidelines, rather than domain knowledge.
  4. The book assumes less domain knowledge than that of SICP.

The paper then distinguishes between structural recursion, where the related data definition happens to be self-referential, requiring usually a straightforward design process, and generative recursion, where new problem data is generated in the middle of the problem-solving process and the problem solving method is re-used, often requiring ad hoc mathematical insight, and stresses how this distinction makes their approach scalable to the object-oriented (OO) world.

Finally, the paper concludes with a description of responses from various faculty and students after having used HtDP in the classroom.

Related Research Articles

In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.

<span class="mw-page-title-main">Lisp (programming language)</span> Programming language family

Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1960, Lisp is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket and Clojure.

<span class="mw-page-title-main">Scheme (programming language)</span> Dialect of Lisp

Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT AI Lab and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It was the first dialect of Lisp to choose lexical scope and the first to require implementations to perform tail-call optimization, giving stronger support for functional programming and associated techniques such as recursive algorithms. It was also one of the first programming languages to support first-class continuations. It had a significant influence on the effort that led to the development of Common Lisp.

Iteration is the repetition of a process in order to generate a sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration.

<i>Structure and Interpretation of Computer Programs</i> Computer science textbook

Structure and Interpretation of Computer Programs (SICP) is a computer science textbook by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman with Julie Sussman. It is known as the "Wizard Book" in hacker culture. It teaches fundamental principles of computer programming, including recursion, abstraction, modularity, and programming language design and implementation.

<span class="mw-page-title-main">Gerald Jay Sussman</span> American computer scientist

Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. He has been involved in artificial intelligence (AI) research at MIT since 1964. His research has centered on understanding the problem-solving strategies used by scientists and engineers, with the goals of automating parts of the process and formalizing it to provide more effective methods of science and engineering education. Sussman has also worked in computer languages, in computer architecture and in Very Large Scale Integration (VLSI) design.

<span class="mw-page-title-main">Tutorial</span> Type of educational intervention

A tutorial, in education, is a method of transferring knowledge and may be used as a part of a learning process. More interactive and specific than a book or a lecture, a tutorial seeks to teach by example and supply the information to complete a certain task.

A modeling language is any artificial language that can be used to express information or knowledge or systems in a structure that is defined by a consistent set of rules. The rules are used for interpretation of the meaning of components in the structure Programing language.

<span class="mw-page-title-main">Constructivism (philosophy of education)</span> Philosophical viewpoint about the nature of knowledge; theory of knowledge

Constructivism is a theory in education which posits that individuals or learners do not acquire knowledge and understanding by passively perceiving it within a direct process of knowledge transmission, rather they construct new understandings and knowledge through experience and social discourse, integrating new information with what they already know. For children, this includes knowledge gained prior to entering school. It is associated with various philosophical positions, particularly in epistemology as well as ontology, politics, and ethics. The origin of the theory is also linked to Swiss developmental psychologist Jean Piaget's theory of cognitive development.

In the state of Victoria, Australia, the Victorian Essential Learning Standards(VELS) is the curriculum framework for Preparatory to Year 10 school levels, which replaced the Curriculum and Standards Framework II (CSF 2) in 2006. Students starting Year 11 normally proceed to complete the Victorian Certificate of Education (VCE), but other education options are available. VELS was superseded by the Australian Curriculum AusVELS in 2013.

Editing technology is the use of technology tools in general content areas in education in order to allow students to apply computer and technology skills to learning and problem-solving. Generally speaking, the curriculum drives the use of technology and not vice versa. Technology integration is defined as the use of technology to enhance and support the educational environment. Technology integration in the classroom can also support classroom instruction by creating opportunities for students to complete assignments on the computer rather than with normal pencil and paper. In a larger sense, technology integration can also refer to the use of an integration platform and application programming interface (API) in the management of a school, to integrate disparate SaaS applications, databases, and programs used by an educational institution so that their data can be shared in real-time across all systems on campus, thus supporting students' education by improving data quality and access for faculty and staff.

"Curriculum integration with the use of technology involves the infusion of technology as a tool to enhance the learning in a content area or multidisciplinary setting... Effective integration of technology is achieved when students are able to select technology tools to help them obtain information in a timely manner, analyze and synthesize the information, and present it professionally to an authentic audience. The technology should become an integral part of how the classroom functions—as accessible as all other classroom tools. The focus in each lesson or unit is the curriculum outcome, not the technology."

<span class="mw-page-title-main">Racket (programming language)</span> Lisp dialect

Racket is a general-purpose, multi-paradigm programming language and a multi-platform distribution that includes the Racket language, compiler, large standard library, IDE, development tools, and a set of additional languages including Typed Racket, Swindle, FrTime, Lazy Racket, R5RS & R6RS Scheme, Scribble, Datalog, Racklog, Algol 60 and several teaching languages.

The ProgramByDesign project is an outreach effort of the PLT research group. The goal is to train college faculty, high school teachers, and possibly even middle school teachers, in programming and computing.

An intelligent tutoring system (ITS) is a computer system that aims to provide immediate and customized instruction or feedback to learners, usually without requiring intervention from a human teacher. ITSs have the common goal of enabling learning in a meaningful and effective manner by using a variety of computing technologies. There are many examples of ITSs being used in both formal education and professional settings in which they have demonstrated their capabilities and limitations. There is a close relationship between intelligent tutoring, cognitive learning theories and design; and there is ongoing research to improve the effectiveness of ITS. An ITS typically aims to replicate the demonstrated benefits of one-to-one, personalized tutoring, in contexts where students would otherwise have access to one-to-many instruction from a single teacher, or no teacher at all. ITSs are often designed with the goal of providing access to high quality education to each and every student.

<span class="mw-page-title-main">Recursion (computer science)</span> Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

<span class="mw-page-title-main">Composition studies</span>

Composition studies is the professional field of writing, research, and instruction, focusing especially on writing at the college level in the United States.

<i>Essentials of Programming Languages</i>

Essentials of Programming Languages (EOPL) is a textbook on programming languages by Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes.

Self access language learning centers are educational facilities designed for student learning that is at least partially, if not fully self-directed. Students have access to resources ranging from photocopied exercises with answer keys to computer software for language learning. These centers are an outgrowth of a style of learning that can go by several names: learner-centered approach, learner autonomy or self-directed learning. These centers exist primarily in Asia, Europe and North America. Use of such facilities and the pedagogical theory they are based upon has its advantages and disadvantages. Proper use can result in a feeling of empowerment and better learning outcomes, but getting to the point where students and teachers can exploit them effectively can be problematic. For this reason, the structure of established self access centers varies from completely student-directed work with classroom immersion to programs that provide primarily tutor or instructor guidance for student work•

Bootstrap is based at Brown University (USA), and builds on the research and development done there. Bootstrap curriculum consists of 4 research-based curricular computer science modules for grades 6-12. The 4 modules are Bootstrap:Algebra, Bootstrap:Reactive, Bootstrap:Data Science, and Bootstrap:Physics. Bootstrap materials reinforce core concepts from mainstream subjects like Math, Physics and more, enabling non-CS teachers to adopt the introductory materials while delivering rigorous and engaging computing content drawn from Computer Science classes at universities like Brown, WPI, and Northeastern.

<i>Structure and Interpretation of Computer Programs, JavaScript Edition</i>

Structure and Interpretation of Computer Programs, JavaScript Edition is an adaptation of the computer science textbook Structure and Interpretation of Computer Programs (SICP). It teaches fundamental principles of computer programming, including recursion, abstraction, modularity, and programming language design and implementation. While the original version of SICP uses the programming language Scheme, this edition uses the programming language JavaScript.

References

  1. The Structure and Interpretation of the Computer Science Curriculum. Journal of Functional Programming, Volume 14, Issue 4 (July 2004) Pages: 365 - 378 (PDF), NEU, 2004, archived (PDF) from the original on May 11, 2008 a paper in which the authors compare and contrast HtDP with SICP.