How to Design Programs, Second Edition | Hacker News Reader

How to Design Programs, Second Edition

ccs.neu.edu

213 pointstosh40 comments

The approach in this book is incredibly important and deserves far wider awareness than it has had so far.

Unfortunately the book itself is less than ideal for working through directly, it would benefit greatly from the polish of professional editing.

However, Gregor Kiczales of University of British Columbia has a absolutely top notch class he teaches based on the book. It's available free on EdX: https://www.edx.org/course/how-code-simple-data-ubcx-htc1x Don't be put off like I was at first by the mass-market title ("How to Code").

Where did you find trouble in working through it? I think the design recipe was insufficiently explained, which was fixed in Kiczales' course, but I found it too slow paced and without challenging exercises. The tight integration with the Racket manual is the book's greatest strength IMHO. That and the Bob Ross-like style.

Thank you for the pointer to Gregor Kiczales's EdX course. I am a few modules into this course and find it valuable.

As context, here's an early paper describing the motivation behind the first edition, and why it chose a different approach from the famous Structure and Interpretation of Computer Programs:

Felleisen, M., Findler, R. B., Flatt, M., & Krishnamurthi, S. (2004). The structure and interpretation of the computer science curriculum. Journal of Functional Programming, 14(4), 365–378.

http://www.ccs.neu.edu/racket/pubs/jfp2004-fffk.pdf

A key paragraph:

> Over the past few years, we have developed an alternative approach to teaching the first course. We have translated the approach into a new text book, and we believe that it addresses SICP’s failings along four dimensions. First, the book discusses explicitly how programs should be constructed. Second, to tame the complexity of programming, it defines a series of teaching languages based on Scheme that represent five distinct knowledge levels through which students pass during their first course. The levels correspond to the complexity of data definitions that the program design guidelines use. Third, the book uses exercises to reinforce the explicit guidelines on program design; few, if any, exercises are designed for the sake of domain knowledge. Finally, the book uses more accessible forms of domain knowledge than SICP.

> First, the book discusses explicitly how programs should be constructed.

But is it right to assume and teach that there is only one way to do it? Aren't we continuously finding out new ways of constructing programs, and isn't it useful and fun to figure out new patterns while constructing new programs?

Wirth said that program is a combination of data structures and algorithms in 1976, there were no _really_ new ways of constructing programs ever since.

HtDP teaches exactly that: proper construction of abstractions, small functions that operate over these abstractions and how to combine everything into a useful software.

So software engineering techniques such as React and Redux were already known back in 1976?

(Just an example)

Redux for sure. Smalltalk had message based system like Redux has (with the difference that in smalltalk this system was object oriented). But functional programming also existed in 1976.

Previous discussion on HN - 3 years ago (1) and even earlier (2).

(1) https://news.ycombinator.com/item?id=8778569

(2) https://news.ycombinator.com/item?id=2958108

And yet I still haven't worked through the text...

Has there been a significant update to HTDP? Or is this just being posted because HTDP is good? The second edition has existed in some form for a while now. Anyhow, the PLT/Racket folks are doing great work!

Is there a PDF or epub version of this?

Seconded. I might add this to my library next to code complete and clean code.

I really wish there was.

If only there existed a way to "print" web pages to PDF files...

Yes please.

If this was in PDF, I could save it on my tablet for offline reading during my upcoming holiday.

Now, I'll probably just bookmark it and forget about it.

I made a quick PDF conversion, formatting its not great but its readable: https://www.dropbox.com/s/bxqlrprz7ys3mc6/How%20to%20Design%...

(Thanks where is due: to generate it I used ziptabs-extension + easypdfcloud.com + combinepdf.com)

The current version of the web site has 9 parts. It took me about 4 minutes to create a PDF of each part.

Mozilla FF has File->Print as PDF

Has anyone read both SICP and HtDP and can recommend one above the other?

Edit: Nevermind, found a similar question in one of the previous discussions: https://news.ycombinator.com/item?id=2958248

This inspired me to program a Haiku:

Grasping for authority

A page turns

Close tab

Can you explain what you mean by this?

I'm interpreting it like: this book is acting more important than it is, you turned a single page, and then closed the tab because you thought it wasn't worth reading.

I also wasn't very impressed with it, but that could be because I already can code and this book focuses more on beginners than SICP. SICP starts off easy and gets hard fast...at least to me. I could've definitely missed some things in HTDP though as I didn't work it through from A-Z as I should have.

If you read other lispy books around the SICP era, they describe the issue with it: it's for math-loving engineering students. There were a few books that tried to focus on problem solving with computers without having to talk about irrational numbers.

HtDP does this very well. It helps structuring the information and the functions around it so you can solve your questions cleanly. Compared to most programming books around that are either too tied to a language or too focus on known algorithms I found it quite great.

That makes sense

Spot on! Also, the suggestion of human language as a program, even across cultures, and therefore humans as computers and a viable platform for programming, runs largely in the face of the tradition from which this tome comes. The expression of a possibly ill-conceived program, written for purpose, then thrown away, nominally as a means to program others, at a minimum achieves communication .. not with the computer but with humans. Multicontextual shift there, but same philosophical plane. It's sort of an art project. You know, curiosity. The thing that got us all in to this computational mess. Why grow up? It's the weekend after all, and there are dimensions of programming far more exciting than optimizing analytical formality. :)

A smug dismissal

From the peanut gallery

The fields lie fallow

What is a haiku?

I'm not sure this qualifies

Maybe

Interesting that they put Strings under fixed size data, and then start the arbitrarily large data section with Lists ...

Images are also considered "fixed size data" in the textbook. I think this is for pedagogical reasons, the sort of simplifying-lie-that-is-cleared-up-later that is common in science education. In the first section, students are encouraged to think of strings and images as atomic data to be processed all at once using built-in functions, but in the "arbitrarily large data" section, the authors give you tools for converting images and strings to lists (of characters and pixel values).

(Note: since Racket supports exact bignums, in a sense numbers are not atomic either! Only Booleans ;-)

In a functional language (like Scheme) strings are immutable, so they are fixed size.

> In a functional language (like Scheme) strings are immutable, so they are fixed size.

Strings are mutable in standard Scheme (unlike, say, Java):

    #;1> (let ((string (string-copy "foo")))
           (string-set! string 0 #\b)
           string)
    "boo"

They're still a fixed length (as they are in virtually every language) because the only way to add onto them is to allocate a new string and copy everything over (this might be hidden behind a method, and you can avoid actually doing this every time by initially allocating more space than you need and using a fill pointer, but they're still fundamentally a fixed length). For example, the 4th edition of the Scheme Programming Language[0] gives this example definition of string-append:

    (define string-append
      (lambda args
        (let f ([ls args] [n 0])
          (if (null? ls)
              (make-string n)
              (let* ([s1 (car ls)]
                     [m (string-length s1)]
                     [s2 (f (cdr ls) (+ n m))])
                (do ([i 0 (+ i 1)] [j n (+ j 1)])
                    ((= i m) s2)
                  (string-set! s2 j (string-ref s1 i))))))))

Even in a language that helpfully assigned the result of this function to the first argument under the covers, this is more or less what you fundamentally have to do, as long as strings are represented by arrays (in Haskell, strings are linked lists, so this doesn't apply).

0: http://www.scheme.com/tspl4/objects.html#./objects:h8

In a functional language lists are immutable, too.

Why is this surprising? Linked lists are easily extendable, whereas strings are fixed size...

Strings are usually represented as arrays (Haskell represents them as linked lists; it's the only exception I can think of offhand), which are a fixed length. To append to an array, you need to allocate a larger one and copy everything over. You can avoid that copying for a lot of appends by allocating more space than you need and using a fill pointer, and the realloc might be hidden away in a method, but it is still fundamentally a fixed-length data structure.

Linked lists are not a fixed lenth. To add an element to a linked list, you allocate a new cons, point its car to the new element, and point its cdr to the old list. There is no "and then allocate a new, larger fixed-length list, copy everything over, and delete the old one" step.

That's all language-agnostic, but in Scheme specifically, the interface it provides for strings does not simulate arbitrary length, either. The only way to add onto strings is using string-append, which returns a newly allocated string.

Has anybody went through this book? Is it worth it for an experienced programmer to complete this book?

The first edition is one of the few books that actually teaches how to solve problems well using programming. Absolutely worth it.

It's probably me, but as an experienced programmer, I found the first edition to be numbingly boring. I couldn't stay with it and eventually gave it away.

My daughter's first class in programming used this book. She really liked the class and still has a fondness for Scheme, although her subsequent programming classes have used Java.

I took a look at the online second edition (and I happen to have a hard copy of the first edition in my library). I like the book and believe that it is one of the best books I've seen for teaching a beginner to program. The subjects covered are non-trivial, but the book gets the students there in a well paced presentation. The book emphasizes the importance of breaking down problems into well defined parts, defining the interfaces, and implementing each part as a function that satisfies the desired contract.

If you are an experienced programmer, I believe that your time would be better spent on a book that is less oriented around teaching the basic steps that you already know. Books that I can recommend to experienced programmers interested in advanced subjects in programming:

1) Structure and Interpretation of Computer Programs, 2ed., by Harold Abelson, Gerald Jay Sussman, Julie Sussman. This book will teach you how to program in Scheme, and you will learn much more than just the syntax. I would consider this to be a very demanding book for a complete beginner. Available online: https://mitpress.mit.edu/sicp/full-text/book/book.html

2) The Science of Programming (1981), by David Gries. This book and the smaller, but equally difficult monograph The Discipline of Programming (1976), by Dijkstra are great books but too hard and mathematical for many readers. They focus on verifying the correctness of programs and introduce a formalism that shows how the logical effects of each program statement can be combined to prove that the program satisfies its specification. There are practical limitations not addressed by these early expositions on program correctness, but the techniques covered can be applied by hand and I've often used them on especially troubling passages of code that I wanted to make sure were correct. If you are up for it these books will introduce new ways of thinking about your code. I'd advise taking a peek at the books before buying to make sure it will be worth the investment; it definitely was for me.

3) Learn You a Haskell for Great Good!, by Miran Lipovaca. Like learning Scheme, learning Haskell will teach you about a new way of thinking about programming. This is a nice introduction to the language. Even though I'm still trying to learn Haskell, this book was my favorite of all my books on Haskell (I've got all of the ones written in English). Learn Haskell to understand where researchers are exploring the possible futures of programming. This book is also available online: http://learnyouahaskell.com

4) Algorithms + Data Structures = Programs (1976), by Niklaus Wirth. This book is far easier on the reader than the ones I've listed above; I've included this book because it is just a fun read for any programmer. It's old and uses Pascal, but it still a great book on programming that introduces a number of algorithms and data structures. It's available used for reasonable prices: https://www.amazon.com/Algorithms-Structures-Prentice-Hall-A.... For a more advanced introduction to data structures I suggest MIT's Open Courseware videos taught by Professor Erik Demaine, https://ocw.mit.edu/courses/electrical-engineering-and-compu...

Reading through this book as an experienced programmer is worth it, but for different reasons. As an experienced programmer, you're probably called upon to bring new people up to speed. They might not need to be taught at the level HTDP assumes, but they need to be taught, and the people who wrote HTDP put a great deal of thought into how to teach people. That's what you can learn from HTDP, if you pay attention.

Reply on news.ycombinator.com