This guide is for anyone teaching COMP 50 at Tufts. If you are helping students, please follow the guidelines below.
I owe an immense debt to Matthias Felleisen—almost all of the questions are his.
We don’t provide answers. Instead, we ask questions. We ask questions that are timeless and apply to many problems. Eventually, through force of repetition, the students learn to ask themselves the questions. At that point they can succeed even when we are not in the room.
Good programmers proceed systematically. That’s what we’re here to teach.
A useful program is never finished. It is only modified by your successors.
A program that merely works is useless. You have created something useful only when you can articulate how it was created and in response to what problem.
Our students must not only be able to do but must be able to articulate explicitly what it is that they do.
If you can’t articulate what you’re doing, you can’t learn to do it better.
Any programming language is an impediment to learning. We use the Beginning Student Language because it is less of an impediment than all the others. Why does the programming language matter?
Novice programmers know just enough syntax to harm themselves.
Novices in all fields make mistakes.
The primary role of the programming language is to mitigate the consequences of mistakes. Thus, if a student complains that things would be easier if only the had objects, or Python, or copy constructors, or some other fashionable programming-language feature, we must remind them that expressive power is beside the point. The points are clarity and safety—first, the language shall do minimum harm.
There is a distinction between designing programs and designing functions. In the first edition this distinction is not entirely clear. Here’s a sketch of how to design programs:
Create a plan (which might spawn a wish list)
Build the bricks needed to implement the plan (by designing functions)
Compose the bricks to create the solution that was planned
(Key step: identify the data used to communicate between “bricks”)
Repeat and refine
The key aspect of the design recipe is the six-step process:
Analysis, data definitions, data examples
Signature, purpose statement, and header
Functional examples (containing calls to the function being designed)
Code template(s) for the function body
Code
Tests
(For generative recursion only) termination
We work with inductive data. This means any value that can be built in finitely many steps. From simpler to more complex, inductive data include
Atomic data (“baked in”; we don’t know how it’s made)
Intervals
Enumerations
Structures (aka product types or Cartesian products)
Unions (aka sum types or “mixed data”)
Self-referential data descriptions (aka recursive data)
Mutually referential data descriptions
Each class of data comes with its own analysis, and each class determines a particular function template. If you’re going to learn to solve problems like a computer scientist, as opposed to a domain expert, you have to move beyond atomic data.
Tufts culture is to be helpful. Our students want answers, and they think answers are helpful. Even better, the students reward us for answers. They smile at us, they are friendly, and they like us. Sadly, we’re not here to be liked—we’re here to help students learn. In particular, we’re here to help students master the design process. (Luckily, as you will know if you have taken COMP 40 or COMP 105, if we help the students learn a lot of good stuff, then when it’s over, they like us a lot. Successful students have used the design process in all sorts of situations—even to create poetry!)
Helping students learn means avoiding answers. Although providing answers gives everyone pleasure in the short term, we must deny ourselves these pleasures and instead ply the students with questions. Exercise constant vigilance!
Systematic, step-by-step design is not fun until you start to master it. When they’re beginning, our students will be tempted to skip steps. To help our students resist temptation, we insist on seeing all the steps of the design recipe in order. We don’t help with step N + 1 until we have seen a reasonable attempt at step N.
Questions germane to the Bargain and the practice of being a successful student at Tufts:
How is your deliberate practice going?
At what time of day do you have your brief, daily sessions of deliberate practice, and how long do they last?
How are things going with your study group?
What times are you spending in Halligan with other students, and how is that working?
How much sleep are you getting?
These questions are based on some common mistakes or other unproductive behavior I have witnessed over the years.
Has DrRacket hit you with an error message?
Have you made the error window big enough so that you can read the whole message at once?
Can you explain to me in your own words what the error message means?
When was the last time you clicked Check Syntax or Run?
Can you show me how to find the documentation of the Racket function you are using?
What is the most challenging and creative part of our work as designers? Seeing data in the world and coming up with a precise description and definition of how the data will be represented in the computer. Many of our students may struggle here, and it may be difficult to get them to focus. But understanding the data is the key to everything that follows.
Questions to ask about data:
Can you describe the data that goes into this function?
Can you describe the data that comes out of this function?
Can you describe the data you see in the problem (or in the world)?
What constitutes a data definition? If you can build data, you have a definition.
What are the three ways of defining data?1
Which of the three ways of defining data is used here?
If the student has a definition by parts, does each part have a definition?
If the student has a definition by choice, does each choice have a definition?
If the student has atomic data, do you need to define intervals or enumerations?
Can you use your data definition to generate examples?
Will DrRacket swallow those examples?
Can you make an example corresponding to each clause of your data definition?
The purpose statement, signature,2 and function header all work together:
The signature says what kind of data come in and go out.
The header gives names to the data that come in.
The purpose statement precisely and comprehensively says how the data that go out (the results of calling the function) are determined by the data that come in (the actual parameters).
Some questions:
Can you say in your own words what this function computes?
What comes in? What goes out? Do you have enough inputs to achieve your purpose?
What kinds of data (structures, variants, atomic) can go into a function?
What kinds of data (structures, variants, atomic) can come out of a function?
Using this purpose statement and signature, could someone else make good examples based on them?
About this signature: where do you define each class of data that is mentioned in the domain or in the range of the signature?
Are all the inputs and the output involved in the purpose statement?
Does your purpose statement avoid saying how the computation is accomplished?
It’s so tempting to skip this step.
Can you give me an example?
Can you show me a table of inputs and outputs? (This is the table with entries “what I have”, “what I want”, and “what else I have or know”. It’s OK for some entries to include “I don’t know” or simply “??”.)
Do you have an example for each variant (or each combination of variants) in your input data? (A variant might arise from a clause in a data definition or possibly from an analysis of an interval.)
(If intervals are involved) Do you have an example from inside each interval? From outside each interval? From the boundaries of each interval?
Can you write this example using check-expect or check-within?
Once we have a signature and all the data definitions, creating the function template should be completely mechanical.3 But there are a lot of details to manage, and we should expect students to need help.
Are there numeric intervals involved that have to be broken down by cases?
Does the data definition use clauses?
How many clauses are in the data definition?
How do you distinguish the various kinds of data? (With what predicates or conditions?)
Do any of the clauses contain structures?
(Where structures are involved) Have you used selectors for each structure (composite data)?
Do any pieces refer to other data definitions (of yours)? (N.B. Composing solutions that involve multiple data definitions is a key skill in enabling the student’s successor to take over the code.)
This is another step that requires some creativity, but it is more of the puzzle-solving variety. Coding obviously builds on the function template, but it is also helpful to use the tables of examples from step 3, and the whole effort must be guided by signatures and purpose statements from step 2.
What are the easy cases? (In general, easy cases involve no selectors and no recursion.)
Can you make an example of each easy case?
Can you create a partial implementation using Racket’s ... expression?
Can you interact with the partial implementation? Can you write test cases?
In the non-easy cases, can you explain each expression? (If not, go back to functional examples)
Can you extend your table of examples with the values of the expressions that appear in your function? (This technique is very powerful. Don’t underestimate it.)
Can you extend your table of examples with the value(s) you are trying to compute?
Using the table of examples, Can you combine the values of the expressions in a way that computes the result you want? (This is the key puzzle-solving aspect of coding.)
If a student is stuck at this step, encourage him or her just to try something out. The computer is fast, and if the student has guessed wrong, the test cases will fail quickly.
Is the combination of these values super-simple, or does it warrant the addition of a function to your wish list?
Our students should use check-expect and check-within early and often.
Has each of your examples been turned into a test case?
Do the test cases pass?
Does DrRacket show any code in red on black, meaning that it has not been exercised by any of the test cases?
Questions to ask when tests don’t pass:
Are the tests right or wrong?
Can big tests be split into multiple smaller tests?
Can a failure of a test case for a big function be “pushed out” to create a failing test case for a smaller function?
Can you develop a failing test case that is small enough, of a small enough function, that it will profit you to use the Stepper?
Applies only to generative recursion. Coming later.
Atomic data, definition by parts (structure), and definition by choice (variants). There is a fourth: definition by self-reference.↩
In the first edition, a signature is (mistakenly) called a “contract.”↩
If you like math, data definitions and function templates are related by a homomorphism. Actually even if you don’t like math, they are still related by a homomorphism.↩