Lambda the Ultimate

inactiveTopic Structure and Interpretation of Computer Science Curriculum
started 9/2/2002; 4:25:20 AM - last post 10/13/2002; 6:11:00 AM
Ehud Lamm - Structure and Interpretation of Computer Science Curriculum  blueArrow
9/2/2002; 4:25:20 AM (reads: 1901, responses: 9)
Structure and Interpretation of Computer Science Curriculum
Matthias Felleisen, Robert B. Findler, Matthew Flatt, and Shriram Krishnamurthi. The Structure and Interpretation of the Computer Science Curriculum. Functional and Declarative Programming in Education (FDPE2002). October 2002

The authors of HTDP explain why they prefer it over the venerable SICP.

Along the way they explain the choice of Scheme, and the pedagogic ideas behind the design of DrScheme.

Designing a first course in CS is very hard, and I find the work done on HTDP adimarble. Alas, reading this I find myself preferring the choices leading to SICP.

I think that a first course should not be about program design (which tends to foucs on things like programming-in-the-large, and reuse), but rather about computational models (e.g., nondeterminism and laziness). In this way the first course introduces the field of computer science, which deals with many issues beside programming and program design.

Designing an introductory course is about making choices, and though I would have made different choices, I find both this paper and the approach it argues well worth considering.

(PostScript version of the paper is available)
Posted to teaching/learning by Ehud Lamm on 9/2/02; 4:27:06 AM

Michael Vanier - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/2/2002; 8:49:36 PM (reads: 1179, responses: 1)
It's an interesting article that makes several good points. I particularly like the distinction between structural and generative recursion. The program design recipes are also nice. However, I think I agree with you that the point of SICP is to present a solid conceptual understanding of what is going on when a program executes, as opposed to simply how to write a program. As the paper's authors mention, SICP tends to teach the latter by example and assume you can pick it up by osmosis. Of course, the brightest students (like the people who read LtU) can do that, but for the rest HtDP is probably better. Still, I've read quite a bit of HtDP and find the pace pretty glacially slow. Maybe that reflects my experience. Also, I felt that the authors didn't say enough about what makes SICP a good book, instead only focusing on its flaws as they perceive them. Finally, although I agree with them that the pseudo-OO system presented in SICP is not really a good foundation for real OO languages (for one thing, it doesn't deal with inheritance), I doubt that the HtDP approach is much better. That's not a criticism, because that isn't the focus of HtDP either; I just don't see that the HtDP approach is really superior in that regard.

Ehud Lamm - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/3/2002; 3:15:53 AM (reads: 1221, responses: 0)
Note that I don't think SICP is perfect, and I find many of the arguments raised by Felleisen et al. to be convincing, specifically the distinction between implicit and explicit learning.

I also agree that some of the examples are perhaps too much physics-oriented for CS students. I think some other examples could have been more CS-like (of the top of my head, some algorithm classes that can be parameterized, like tree traversal, dfs vs. bfs). But finding the right examples is just so very hard.

I like examples that are difficult enough to make the students feel they are learning important new tools (and domain knowledge!) Most CS text books fail to achieve this goal, while SICP comes fairly close.

I like the distinction between structural and generative recursion in HTDP, too.

I think Evans tried to achieve some of the goals I emphasize. I am not sure how well it went it practice, though.

Noel Welsh - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/3/2002; 3:57:04 AM (reads: 1145, responses: 1)
I agree with many of the points made in the paper. In my experience as a student people aren't motivated by stuff like integration and differentiation. However they'll spend hours tweaking their GUIs to look nice (doesn't everyone want to implement the drawing language in SICP?)

I too found HtDP glacially slow and loved SICP, but then I came to SICP rather than it being forced upon me, and I already had many years programming experience (including a touch of Scheme).

Drawing a 3-D maze (in the style of the original Wizardy and Bard's Tale) is an excellent example of a fun and easy recursive problem. If I'd know about recursion when I was 13 the characters in my little 3-D wouldn't have suffered from tunnel vision! The 'physics' is trivial when you only allow 90-degree turns but the structure of the drawing algorithm is still reasonably complex. And the results are way cool!

Ehud Lamm - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/3/2002; 4:05:42 AM (reads: 1194, responses: 0)
Any learning that is forced upon you is bad. That's why people should learn when and where they want (I am writing this on a university computer ).

Point is, the first course is lioke boot camp -- it has to make you realize that what you like to play around with at home is not necessarily the same as what CS is about.

I claim that you can do this, and still make the course interesting and exciting. But I am known to be an uncurable optimist...

Michael Vanier - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/3/2002; 10:36:39 AM (reads: 1125, responses: 2)
I think we're all in violent agreement here ;-) I also came to SICP after many years of programming experience, including a bit of lisp. That seems to be typical of those who love SICP. I wonder whether teaching SICP to rank beginners (as we do here at Caltech and also at MIT and Berkeley) is giving them too much, too soon. Certainly a lot of the students seem overwhelmed by all the new concepts thrown at them (not to mention being forced to completely abandon everything they thought they knew about programming). Forcing students to think in a new way is good, but overdoing it can have the unintended effect of turning off students that otherwise could become good programmers and/or CS researchers.

Ehud Lamm - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/3/2002; 11:19:24 AM (reads: 1171, responses: 1)
overdoing it can have the unintended effect of turning off students that otherwise could become good programmers and/or CS researchers.

This is obviously true. But the reverse can also happen: students are sure they understand concepts they really don't, and it becomes an up hill battle to teach them the correct version.

It is easier with theory - since most students don't have prior exposure; but with programming it can be a real pain.

Ehud Lamm - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/3/2002; 12:28:04 PM (reads: 1208, responses: 0)
To clarify (now that ER is over...), what I meant is that when CS1 courses teach half baked ideas, they make the rest of the program that much harder to teach.

Teach programming languages I see quite a few students that are sure they know what a stack is and how it is different than the heap -- when in fact they don't have a clue. But someone told them something about these, when they learned about procedure calls in CS1.

Another tragic example, was an instructor that told her students not to use recursion ever "I worked 10 years in industry, and not once have I seen recursion used." If this is the result of teaching recursion in CS1, it'd be better to drop it.

(Note: None of the above is directed at HTDP; I am talking about CS1 general. HTDP is among the better options)

jon fernquest - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
9/4/2002; 2:34:38 AM (reads: 1098, responses: 0)
I don't see the authors' objection that SICP focuses on domain knowledge too much a valid objection, at least nowadays.

As margins on hardware and software fall, all that computer companies have left is *consulting services* and *domain knowledge* is what makes consultants and consulting organizations valuable. To make students ready for this they should be thrown some rich, realistic, and challenging *problems from specific domains*, like the classics in SICP and PAIP...or...

The telecommunications domain which has several DSL's and even conferences devoted to it, comes to mind as a good new source of new domain problems to replace the toy problems, examples, and games that textbooks traditionally rely on

Furthermore, consulting is a niche through which non-mainstream languages (Haskell, Scheme, DSL's) and their features can slip into the mainstream. An expert recommending a language for a specialized purpose (see Little Languages, Little Maintenance ), is going to have more chance than someone advocating the language for everyday use in some major bastion of conservatism like data processing or systems programming.

Capturing domain knowledge is the best reason I can see to use DSL's.

The norm is for a consulting organization to be valuable because of its human capital, i.e. the knowledge resides in its employees' heads not the organization itself.

I've seen consulting organizations (tech support departments also) try to capture domain knowledge by setting up *knowledge bases*, but these just grow and grow and grow old, messy, irrelevant, and finally die, *mere recording is not enough*, the domain knowledge must reside in *a tool that is continuously being used to solve problems in the domain*: A Domain Specific Language. Users will adapt the tool to its changing context of use.

(Whoops. I seemed to have veered from the subject. Sorry. :)

HTDP and SICP seem more like complements than substitutes to me, I love HTDP's recipe-cookbook detailed descriptions of how to write programs.

I think many older people enjoy SICP because they've already seen these concepts described in all their full blown complexity.

Possible Enhancements:


Build Scheme DSL's with modular monadic action semantics.

Build interpreters from standard language modules first, then use partial evaluation to derive compilers.

Combine and reuse language features from different programming paradigms in these interpreters. This should break students fixation on syntax.

Embed Scheme in Java using Java syntax to disorient the students a little bit and get them to ask some hard meta-questions like: "What is Java?" and "What is Scheme?" Felleissen's book and Wadler's Featherweight Java provide good hints on how to do this. Make Scheme relevant to current employment market by calling it an "advanced Java feature."

Add language features to Scheme like strong typing, lazy evaluation, and parametric polymorphism in a modular fashion.

(Sch(eme)+(H)askell = Schaskell


Code smells --> refactoring

Unit testing + refactoring = meaning preserving program transformations

Refactoring as a form of program understanding, simplification, elimination of redundancy, and readability.

Two student team projects using extreme programming.

Ehud Lamm - Re: Structure and Interpretation of Computer Science Curriculum  blueArrow
10/13/2002; 6:11:00 AM (reads: 837, responses: 0)
PPT slides from thetalk are now available.