How to Design Programs and DrRacket
I’m currently working through “How to Design Programs, Second Edition” available for free here:
There is also associated software called DrRacket available for free here:
Now, what’s interesting is that DrRacket uses a teaching language called Scheme that is like Lisp. Now why would you use something like this instead of Python? To quote from the preface to HTDP:
“The typical course on programming teaches a “tinker until it works” approach. When it works, students exclaim “It works!” and move on. Sadly, this phrase is also the shortest lie in computing, and it has cost many people many hours of their lives. In contrast, this book focuses on habits of good programming, addressing both professional and vocational programmers.”
There is also a MOOC series based on this textbook available on edx:
Learning a language, not how to write programs
Now, Joel Spolsky has a similar view. He writes about how Java schools are churning out developers in his article “The Perils of Java Schools”:
“Heck, in 1900, Latin and Greek were required subjects in college, not because they served any purpose, but because they were sort of considered an obvious requirement for educated people. In some sense my argument is no different that the argument made by the pro-Latin people (all four of them). “[Latin] trains your mind. Trains your memory. Unraveling a Latin sentence is an excellent exercise in thought, a real intellectual puzzle, and a good introduction to logical thinking,” writes Scott Barker. But I can’t find a single university that requires Latin any more. Are pointers and recursion the Latin and Greek of Computer Science?“
He then talks about how some of these courses, as painful as they are and as seemingly irrelevant are actually good:
“These students would never survive 6.001 at MIT, or CS 323 at Yale, and frankly, that is one reason why, as an employer, a CS degree from MIT or Yale carries more weight than a CS degree from Duke, which recently went All-Java, or U. Penn, which replaced Scheme and ML with Java in trying to teach the class that nearly killed me and my friends, CSE121.”
How much do we need to know as data scientists?
Now, as data scientists do we need to be full stack developers who are totally across functional programming? Probably not! For those interested the course for 6.001 is here and the textbook is available online:
Where does HTDP fit in?
To me, DrRacket and How to Design Programs feels like a pretty good take on writing software.
In fact here’s a framework for developing programs that they work through in the book:
1) From Problem Analysis to Data Definitions
Identify the information that must be represented and how it is represented in the chosen programming language. Formulate data definitions and illustrate them with examples.
2) Signature, Purpose Statement, Header
State what kind of data the desired function consumes and produces. Formulate a concise answer to the question what the function computes. Define a stub that lives up to the signature.
3) Functional Examples
Work through examples that illustrate the function’s purpose.
4) Function Template
Translate the data definitions into an outline of the function.
5) Function Definition
Fill in the gaps in the function template. Exploit the purpose statement and the examples.
Articulate the examples as tests and ensure that the function passes all. Doing so discovers mistakes. Tests also supplement examples in that they help others read and understand the definition when the need arises—and it will arise for any serious program.
HTDP also mentions the pitfalls of learning a language and not how to write programs:
“A typical “quick programming in X” book or course fails to teach principles that transfer to the next fashion language. Worse, the language itself often distracts from the acquisition of transferable skills, at the level of both expressing solutions and dealing with programming mistakes.”
And the solution, to start with a teaching language:
“Our solution is to start with our own tailor-made teaching language, dubbed “Beginning Student Language” or BSL. The language is essentially the “foreign” language that students acquire in pre-algebra courses. It includes notation for function definitions, function applications, and conditional expressions….This language is thus so small that an error diagnosis in terms of the whole language is still accessible to readers with nothing but pre-algebra under their belt.”
Why am I bothering?
As someone who is a self-taught data scientist I feel there are gaps missing from my knowledge of CS.
So, I’m slowly making my way through the book, doing about half an hour per day. So far it has been fun! My hope is that I will be able to acquire those fundamental skills that can transfer to any learn any programming language or library in the future.
Who else is interested in this stuff?
Well, Peter Norvig is one. He wrote a book back in the day called “Paradigms of Artificial Intelligence” which implements algorithms in Common Lisp:
It turns out back in the day that Lisp was the language a lot of the early AI was implemented in. In fact John McCarthy who created Lisp also coined the term “artificial intelligence”. So, is there something about writing code in Lisp or Scheme that helps improve coding skills or thought patterns or problem solving, or all of the above? Well, I intend to find out.
Another guy who is influenced by Scheme/ Lisp is Hadley Wickham:
“To understand why R’s object systems work the way they do, I found The Structure and Interpretation of Computer Programs (SICP) by Harold Abelson and Gerald Jay Sussman, particularly helpful. It’s a concise but deep book. After reading it, I felt for the first time that I could actually design my own object-oriented system. The book was my first introduction to the generic function style of OO common in R. It helped me understand its strengths and weaknesses. SICP also talks a lot about functional programming, and how to create simple functions which become powerful when combined.”
Jumping in, how to do mean in Scheme?
It’s a simple example, but it rhymes, so that’s kind of funny!
; define our y1 and y2 vectors
(list 1 2 3 4 5 6 7 8 9 10))
We want a couple of examples to test things out. Notice the prefix function call here. It is like reading apply the function “list” to each element that follows. In the same way you can sum variables like this:
(+ 1 2 3 4 5 6 7 8 9 10)
Which gives 55, there is no ambiguity here! It’s actually a really natural thing to do even though it looks weird.
Now for our functions:
(define (sum x)
(apply + x))
Sum is really just saying apply “+” which is actually a function to each element I pass in.
(define (mean x)
(/ (sum x) (length x)))
Now, to calculate the mean we are just applying our sum function to our list and dividing by the length of the list.
So we know our sum is 55 and our length is 10, so our mean is 5.5