Lambda the Ultimate

In general, an undergrad CS course in one programming language or another will only be as effective as the rest of the relevant curriculum. If you have a course that teaches the basics of programming in Scheme but a data strcutures and algorithms course that teaches in C, you're working against yourself. I do think that using something more high level in C is necessary though, because you need to develop skills that teach you how to reason and think about a problem, and C makes this difficult.

I haven't seen it first hand myself, but with the Squeak camp at GA Tech, I imagine they focus on the decomposing problems into objects. In most Scheme courses I've seen, they focus on decomposing problems into procedures and spend a fair bit of time on recursion theory (although it's not called recursion theory, it's explored in the context of Scheme). In most C courses I've seen, problems are decomposed into functions and a fair bit of time is spent on merely getting running code.

In all of this, I'm not taking into account students who already program and thus, probably have a preference to which language they learn. I had friends at GA Tech who were in some of the Squeak classes and they didn't like it very much. They didn't see the utility of using a system they saw as slow and overly conceptually abstract. They largely thought in terms of C.

Ok, so it might not be a good choice for a first course. But as a second semester course trying to teach machine architecture, it would get my vote. Actually, a more involved course would make the students design their own single board computer and program it in assembly - at least if you were slanted towards an EE degree. :-)

I almost said Modula-2; my old university used to use that as its introductory language. They used the Metrowerks Modula-2 IDE on Macintoshes, and it was pretty nice; editor with syntax highlighting, integrated debugger, and so on. Unfortunately, Metrowerks doesn't make that product anymore, and I'm not sure if any Modula-2 textbooks are available. It's too bad. Modula-2 was like Pascal, so it was static and (as I recall) strongly typed. It shared the same Wirth style syntax, which some find more readable. The textbook we used stresssed things like encapsulation and information hiding, and the code examples used pre- and post-conditions, as well as loop invariants. So it tried to introduce good habits.

I think Python would make a good first language because you can use it as an imperative language (like C or Pascal) as well as an OO or maybe functional language. It has a large amount of freely available code for students to look at and play with.

The fact that Python is interpreted plays a large part in my choice. I think students can benefit from the instant feedback of typing something in and seeing the result, instead of spending time in an editor, then compiling, then running, then back to the editor...

And because it is interpreted, debugging is made a bit easier. Students get a (moderately readable) stack trace rather than seeing an inscrutable error message and having the program dump core.

Also, Python is runs on many platforms, and is available free of charge. So students can use their own computers for work, and be assured that the program will run the same on a professor's or TA's machine.

I don't know if Python is catching on as a teaching language, though. I've met several people who told me that their schools were switching to Java, or that they themselves were taught primarily in Java. I had heard that the Advanced Placement exams were going to move to Java, but I'm not sure if they have.

I really like the MIT approach of four basic courses: 6.001, 6.002, 6.003 (can't seem to find a more recent homepage) and 6.004.

I don't know of any real CS textbooks in Python. I have two O'Reilly books, "Learning Python" and "Programming Python." Both are pretty good, but they are aimed more at experienced programmers.

You could check the Python Education SIG's mailing list archives. They have some links that might be useful; for example they have a link to the Python version of "How To Think Like A Computer Scientist."

(It would be cool to have something like SICP in Python...)

My main concern with books of this sort (I haven't seen the Python books, but I am a great fan of other O'Reilly titles) is not that they are aimed at experienced programmers, but rather that they are don't try to educate, but rather to train. The examples are usually rather limited, and concentrate on syntax; there are sually no open/challenge exercises. Theoretical foundation is not important for books of this type, so for example (to go back to the discussion we had a couple of days ago) they can show problematic uses of inheritance, without so much as explaining the relevant issues.

A more general concern is that books of this kind are not concerned with the CS curriculum as a whole. They don't follow a thoughtout approach to CS education.

By the way, HtDP tries to be much more learner-friendly than SICP, but does follow a well reasoned approach to teaching basic CS.

To put another spin on this issue, I'd like to point out that many simple programming examples used in the foundation course can introduce important concepts which are later devloped more carefully. I think this is a good way to teach. For example, students may implement a DFA in order to tokenize input (or indeed use regular expressions, if the language supports them). In later courses they will learn about formal language theory.

Alas, not many books folow this approach.

The "How To Think Like a Computer Scientist" book seems to be aimed more at high school students than college, but it might be possible to adapt it for a more advanced audience.

Thanks for the HtDP pointer.

Is it because of the C legacy of efficiency at the machine level vs. high-level expressiveness?

Does it all come back to the fact that "LISP is slow, C is fast"?

But yeah, one of the memes in this C-based culture is "LISP is slow, C is fast." Regardless of how the world really is, this is a concept mixed, mutated, and transmitted throughout C-culture.

1. Has Java in its name so students and faculty won't object.
2. Widely used in the industry.
3. Has an official standard (ECMAScript). And this standard is actually supported.
4. Supports procedural programming (this is how most Web developers use it). Allows nested function definitions and even executing code directly in the global scope.
5. Supports object-oriented programming (this is how good Web developers use it). Everything is an (extensible) object, including the basic types. Inheritance is prototype based (based on Self).
6. Supports functional programming (this is how I use it ;-). Functions are first-class citizens, implements lambda expressions and closures.
7. Garbage collection.
8. Exception handling (try/catch/finally/throw).
9. Lots of built-in types and services (regular expressions, dynamic arrays, maps).
10. Familiar syntax makes it easy to switch to/from C/C++/Java.
11. No compilation, just type and run.
12. Has a standard object-oriented, event-driven UI framework (the browser).
13. Supports XML.
14. Runs on most any platform.
15. Development tools are widely available and often free.

I was talking with a Javascript hacker a couple of weeks ago. Now this guy is not really a programmer (he is in the math department), but he sure does write nice scripts. I tried to explain the concept of information hiding, so I gave the example of stacks, that mey be implemented as arrays or as linked lists. After several confused looks I realized that my friend didn't realize that arrays are not the same as associative/dynamic arrays. I had to explicitly explain that when I say array I am talking about a consecutive area in memory, with a predefined given size.

Now this kind of confusion is not something I want a first programming language to encourage. I am not sure it is the language fault, by the way. What do you think?

Lack of good support for information hiding is one of JavaScript's problems, though not perhaps the major one. I would probably put the lack of enforced variable declaration higher on the list (though both problems can be overcome: information hiding through judicious use of closures, and variable declaration through the scripting host (probably)).

As to your friend: in JavaScript arrays are dynamic/associative. JavaScript implements objects as a collection of name/value pairs. In the case of an array the names are the indices (at least of JScript they are even converted to strings prior to indexing). As a result, JavaScript arrays can be sparse, can grow dynamically (they support push/pop) and even contain members with indices that are not numeric.

Obviously this means that internally a JavaScript array is not implemented as a consecutive block of memory, and that accessing an element has significantly more overhead. I imagine, most JavaScript users (I'm intentionally not saying programmers) don't care. In another thread you mentioned "advocates of the so called scripting languages approach". I'm not exactly sure what you mean, but to me script users often just want to get a job done (your mathematician friend) and in such cases having a single, simple collection type that does most everything you need makes life a lot simpler.

This is not to say that you can't use JavaScript to implement a linked list, or a tree or whatever. Indeed one of the Beyond samples is a linked list that supports the same set of iteration functions as the Array type and can thus be used polymorphically with it.

I personally don't think that the dynamic nature of JavaScript arrays, and their internal representation, is a hindrance for the use of this language as a teaching tool. Worst case, don't tell the students about the internal representation (at least not at first). You can even do something silly like:

and then teach push and pop using Stack.

I certainly don't think JavaScript is an ideal language (even with Beyond ;) But I do think it's a really nice language, easy to use, and implements all of the stuff you need to teach a CS course.

But teaching these distinctions is something I really want to do in CS1.

My comment was obviously a bit tongue-in-cheek, but I do think there is a valid point here. The high-level environments/languages in use today hide many of the implementation details and memory layouts of the structures they are exposing. All they guarantee (sometimes) is the O value. Do you really know how the STL deque is implemented? (I believe it varies between implementations.) I haven't seen an ECMAScript guarantee that array access is O(1), but it can very well be that way without using contiguous memory (at least in most cases).

You could probably simulate contiguous memory storage in JavaScript using a string, but that would be really weird. If this is a make-or-break requirement for you than JavaScript is not the tool you want. BTW, do Scheme, Smalltalk, Python, Ruby, etc all guarantee the memory layout of their arrays?

However, the real issue is about teaching. When you learn you should strive to understand all the factors involved.

I agree that using any VHLL is problematic in this regard; that's why an FP based course requires a complementary course about low level details. (Or teach like SICP, how to build an interpreter for a virtual machine etc.)

That's the answer then, teach JavaScript and x86 assembler (or Amiga assembler as has been previously suggested.) Your students will really love you :-)

But seriously, JavaScript is one of the least suited languages to do explicit memory manipulation (it doesn't even have standard means to control its garbage collector.) It does a very good job of insulating you from the implementation detail (which is a good thing for a scripting language.) And it is good, IMO, at expressing algorithms. For example, I intend to publish on LtU an example that contrasts imperative and functional (using Beyond) implementations of the Sieve of Eratosthenes.

Another thought that comes to mind is to use JavaScript over an environment that does provide the data structures you want. Rhino over the JVM or JScript.NET

Here is a simple implementation of a stack in JavaScript, with information hiding (only the push and pop methods are exposed):

Note also that the dynamic nature of JavaScript's arrays is nowhere used nor exposed.

Now try to explain this example to someone who hasn't seen closures...

You want a language which will enable you to give concise and clear example code in later courses. I am thinking about courses that are not directly about programming, but include example code. Examples? Executable math (e.g., MATLAB), algorithm courses etc.

If you teach students verbose languages (like Java) it is hard to give complete example programs.

Notice that there's a tension between this goal, and the goal of teaching languages that expose important implementation details (parameter passing styles, for example).

In contrast, learning C, C++ and x86 assembly on the IBM PC required the compile-edit-debug cycle which incurred a lot of wasted idle time when trying to verify how a given language feature behaves exactly.

Python brings back the joy of immediate learning I used to experience on the Apple II.

We use Haskell (more precisely Helium) here, and I can attest that it is several times easier to teach than Java, but I think there are too many ad hoc things about Haskell to make it the best beginner's language, and the DrScheme environment is still better than Helium's.

Frankly, I think Java is one of the worst choices for a teaching language. It's verbose, obscure, non-interactive and has a million idiosyncracies both in the language and the standard libraries. Also, it is too much of a medium-scale language: it's badly suited toward small- and large-scale problems. Even for relatively small programs one has to introduce design patterns to work around the lack of support for things like tuples and higher-order functions.

I think a problem is that there are so many issues related to pedagogy and human factors that dictate what is the most straight-forward means of teaching computer science. Meaning, I think that it probably depends alot upon the particular individual you are instructing.

Personally, I really enjoyed my background in digital computations and computer engineering. I believe that having an in-depth understanding from bottom to top made it easier for me to learn new languages and concepts. For me, it's easier to grasp higher level abstractions if I have some sort of understanding of the implementation (even if it's naive) behind those higher level abstractions.

On the other hand, I understand that, for some people, it's easier to begin with higher level abstractions, otherwise they establish pre-conceived notions which are difficult for them to break.

Or to begin with different low-level foundations. For instance, some people may feel comfortable beginning with a concrete, possibly physical understanding of the computer and its execution model and abstracting layer on layer away from that. Others may feel more comfortable beginning with a low-level conceptual, possibly mathematical model (or models) of computation (the Turing machine, the lambda calculus, various process calculi) and abstracting layer on layer away from that.

Just as there's more than one top-down approach, there's more than one bottom-up approach... In fact, I believe a big insight comes when you realize that the apparently one-dimensional tower of abstraction is actually a far more fluid structure. Maybe a different pedagogical question is: how do you get students to that point? How do you help them reach the level where they can step back and reflect on the process and structure of abstraction itself? Are some programming languages or systems (I'm sure someone will suggest Lisp...) inherently more suited to this? Is there, in fact, any shortcut to insight?

In the second semester, they write a lisp interpreter, and do exercises in lisp, java, and C++. They use lisp macros, C++ polymorphism, and implement Dijkstra's algorithm.

Overall, I think the general goal of the program is a great idea -- teach a concrete knowledge of the machine, before getting into the useful abstractions provided by high-level languages.

I helped someone get through the first semester of this course. Some impressions of the course:

• C's string handling is too advanced to jump right into, so they have string library functions that students use. However it is impossible to use these libraries robustly without understanding pointers. C++'s std::string might have been a better choice.
• Using assembler is a great way to teach the fact that code is really just another kind of data (a theme revisited by lisp macros in the second semester). However, the main effect of using an 8-bit vm is that students have to learn 2's complement representation, and the bitwise representation of numbers (in order to explain over- and underflow). The fact that code is data tends to get drowned in the noise.
• On the other hand, the VM technique did manage to drill home the fact that "letters" (i.e. characters) are really just numbers in some encoding (e.g. ascii). The fact that ascii digits have different numeric values than the digit they represent was surprising. i.e. '9' != 9.
• The difference between the contents of a file, and the handle to that file was not explained. In particular, the fact that a file handle remembers the current offset within the file, was a surprise to the person I was working with.
• Not enough attention was given to how to test programs. The debugger was covered, but only in lecture style, not a workshop.
• Debugging C is extremely difficult. Without help, the person I was working with would probably have become completely stumped by a few bugs, and would have gotten zero credit for those problems even though partial credit would have been deserved. I nearly became stumped myself a couple times, and had to resort to tools like purify and valgrind.
• The breadth of tasks that students cover is very impressive and probably the single strongest aspect of the course. C, assembler, data structures, algorithms, and user interface are all covered to some degree.

Which leads me to the dictum "use medium-abstraction languages for teaching."

This principle can also explain why Scheme is often a better choice than Haskell.

You could write a one line C version, but it would go against everything you'd be trying to teach. In C++ this is no longer true. This is despite the fact that the C++ is made shorter by applying several Perl-isms to the main() function.

Java certainly has its problems, not the least of which is the fact that you have to jump feet-first into the OO thing, otherwise the framework just doesn't make sense. But still, I think that in this particular context it's better than C.

Can you give a concrete example why C is better than Java as a foundation language?

2. I want students to understand the distinction between value and reference semantics.

etc.

Notice, that I don't think C is such a great choice. I think Pascal was better for teaching beginners.

At Oxford, we use Oberon as the second language we teach to our undergraduate students (the first one is Haskell). We chose it because of its cleanliness and simplicity, and because of the availability of books that emphasize clear reasoning about programs.