Lambda the Ultimate

I am curious to hear more about your experience teaching semantics the first year. My students have enough trouble learning programming, which is already quite a precise discipline (the rigors of syntax and algorithmic thinking: telling the computer exactly what it should do!). During the first year I find it is enough to give them precise, natural-language definitions of certain concepts (scoping, encapsulation, assignment, and so forth). This helps them to understand programming. But I don't give a semantics formalism as such.

I have an easier time of it than you, since HtDP uses small subsets of Scheme (with some added constructs, e.g. structures) as a precursor to Java (a second-term course). This offers three advantages: first, simplicity; second, a purely functional world until week 10; third, reduction semantics (meaning you don't have to go outside the language to specify the meaning of a program).

To this, I personally can add a fourth advantage: my students are entering a Faculty of Mathematics based on their performance in high-school math. So not only do the semantics nicely parallel the notion of substitution with which they are familiar from algebra, but they are good at it.

At three points (corresponding to Beginning Student with List Abbreviations, Intermediate Student with lambda, and Advanced Student in the HtDP language hierarchy) I make available summaries of the syntax and semantics to date, and each one fits onto two typeset pages in 12pt type. Furthermore, the rules are pretty intuitive, for the most part.

I also sprinkle "traces" using the semantics throughout; complete ones at the beginning, but then "condensed" ones later on, though I try to condense in such a way that it's evident what is omitted (usually conditionals, multi-argument special forms such as "and", and applications of accessors for structures and lists).

Back when Pascal and Fortran were the teaching languages, students used to trace programs using tables: at line 10, here are the values of all the variables. There is very little of that now. The best students (e.g. everyone reading this comment) don't need that; they understand the abstractions. The rest of the students don't quite know where to turn when their intuitive notions of what their program does clash with the only real source of "meaning" they have, namely running the program. I am fortunate in that I can be a little more rigourous about semantics than someone teaching Java or C++ as a first language. But I believe going further down this road than most current practice is the key to restoring some effectiveness to first courses.

My course home page is here if you wish to look at my materials. The course follows HtDP fairly closely, with perhaps a bit more rigour. --PR

I am a bit confused by your message; let me explain why.

This offers three advantages: first, simplicity;

I don't understand; my approach is quite simple too.

second, a purely functional world until week 10;

I don't consider this an advantage, on the contrary. I try to give my students exposure to more than functional programming, such as state, object-oriented principles (encapsulation, polymorphism, inheritance), abstract data types, exceptions, and dataflow concurrency. It is nice to start with functional programming but there are many useful concepts outside of it that students should see. There is absolutely nothing wrong with state, on the contrary it is an essential concept that is needed to achieve modularity in programs.

third, reduction semantics (meaning you don't have to go outside the language to specify the meaning of a program).

Again, I don't consider this an advantage. Defining something in terms of itself can be very confusing to students. I think it is much better to define something in terms of something else. If you have a kernel language, then you can define a rich language in terms of the kernel language. But the kernel language itself should be defined in terms of something else: something the students already understand like simple mathematics. In my experience, new concepts should always be grounded in existing concepts.

a fourth advantage: my students are entering a Faculty of Mathematics based on their performance in high-school math.

Computer programming is not the same subject as mathematics. I think that the two fields are quite different, and one should not needlessly mathematize computer programming. From the viewpoint of computer programming, mathematics is just a tool.

I agree completely that you need rigor, but one doesn't need a lot of mathematical baggage to be rigorous. I do think I understand your point though: teachers who don't mathematize much tend not to be rigorous. It's a lot of effort to be rigorous without overmathematizing (pardon the neologism), but it's not impossible.

I am a bit confused by your message

And I am by yours! You suggested that programming in first year was hard enough without introducing semantics; I was pointing out why our situations were different. I was not claiming that what I am doing in first year is in any way a replacement for what you are doing in second year. So when you say I try to give my students exposure to more than functional programming, such as state, object-oriented principles (encapsulation, polymorphism, inheritance), abstract data types, exceptions, and dataflow concurrency you are comparing an introductory programming course for those who may lack prior computing experience to a second-year concepts course.

So let me back up and state my premise again, perhaps more clearly this time. I think that a certain amount of semantics in first year is possible and in fact can help students in understanding the art of programming, and prepare them for further study in a course such as you are teaching. But I think that Scheme-then-Java is preferable to Java-first.

I agree with your points about kernel languages and richer languages, except where a first course is concerned. I don't think the students' understanding of mathematics, even my incoming Math majors, is sufficiently strong on which to base semantics in a first course, though I am willing to be convinced otherwise. (They are weak on set theory, for example, until they get through their first university math course which they take concurrently with my course.) Saying "we rewrite programs according to these rules until we get down to a sequence of values" is pretty simple, and every intermediate step is itself a legal program. It is particularly valuable when introducing recursion.

As for "needlessly mathematizing", I don't think I am doing that, though again if anyone can point out specifics in my materials, I will correct this. But if students have math skills -- in particular, if they understand elementary algebra -- then these can be put to good use by giving them semantics whose manipulations resemble what they are familiar with. I can't think of anything else approaching a formal system that they understand at a similar level when they enter university. --PR

I agree with everything you say. I think that I misunderstood the context of your earlier message. Some semantics in the first year is beneficial, if it is well integrated and unobtrusive.

I think that the ultimate solution will be that the basic concepts of programming have to be taught correctly in high school. Whatever happened to the Logo project of Seymour Papert from the 1980s? The book 'Mindstorms' that documents his experience is still worth reading today. It seems that computer science education in high school has regressed since then.

But in the meanwhile, university courses have to be able to correct the students' bad beginnings and fill in the gaps. It seems that this can be done in either the first year (see the work of Matthias Felleisen and his colleagues and the book HTDP) or the second year (this is my experience).

I second that. His later work isn't all that exciting, but this book, and the Logo experience in general is worth exploring. (Disclosure: My first programming language was Logo...)

Second, if you want to use this technique, choose an applicative language, with little compile time checking (i.e., static semantics, which aren't going to be explained by the reduction relation).

they pooh-pooh me, saying that by far the major problem is that the students can't solve algorithms.

I can imagine ways of testing this statement, for example, you could have a knowledgeable programmer "translate" for the students or you could have one student write down an algorithm in natural language and give it to a second student to perform, the second student not knowing what the ultimate goal is, and other ideas like this with varying levels of subjective/uncontrollable elements that take out the "translation" aspect. Also, when an instructor writes some code on a chalkboard and explains how it performs the algorithm, how well do the students follow along, at least as far as understanding how the algorithm accomplishes the task if not how the code corresponds to the algorithm?

I have no idea if any studies along this line have been carried out. That said, while it would be ridiculous to think that the translation has no overhead (if it didn't you wouldn't even need to learn a new language, you would immediately be able to code in it, in fact the speed in which new programming languages can be picked up can be used to support the following), my personal anecdotal evidence not as an educator is that your colleagues are mostly right, for example, I've seen students have difficulty understanding what is going on in box-and-pointer diagrams and these have almost zero "translation" overhead.

All this said, it might still be useful. Any aspect that can be made simpler is certainly helpful so that more time can be spent on algorithms rather than the proper semicolon placement.

Perhaps you're somewhat missing my point. Who cares about semi-colon placement. I'm talking about mapping the subjects, objects, adverbs, adjectives, and verbs, and phrases or clauses that play these roles, to corresponding program statements. For instance, in the example I gave you, here are two possible answers, at different levels of explicitness or complexity, in C# syntax:

Simple version: person::location1.getPersonName(“with big mouth”).eat(“fish”, "with alacrity”, "not too quickly")

More complex version: person::location1.getPersonName(“with big mouth”).eat(food::fish.getFishName(), "with alacrity”, person::location1. getPersonName(“with big mouth”).setEatSpeed("not too quickly"))

Role assignment in, for example, the more complex version (simple version should be obvious from this):

- Subject: person::location1.getPersonName(“with big mouth”)
- Verb: eat
- Object: food::fish.getFishName()
- Adverb #1: ”with alacrity”
- Adverb#2: person::location1.getPersonName(“with big mouth”).setEatSpeed("not too quickly"))

The point is also, in my opinion, to generate interest in programming, by making the student see the similarities in computer and human speech. At the same time, they start to understand the semantics.

By the way, check this page on my website, in case you think I'm not interested in algorithms: http://www.searchhelpcenter.com/search-discussion-article-thesaurus-relationships.html

I am going to add some important things to the scheme of object role relations as described on that page, namely, system relations, such as higher level plans and relations that guide sequences of events. That makes a better bridge between the object and system levels of mental templates, and also enables me to explain the connection to my previous works on systems.

Perhaps you're somewhat missing my point. Who cares about semi-colon placement.

I think you are misinterpreting what I wrote. My last sentence was exactly along the lines of "who cares about semi-colon placement". My point was that in my, admittedly small, experience complete beginners spend a lot of time on trivial syntactic elements whose mastering adds nothing to ones ability to program. However, I'll agree with you about somewhat missing your point. When you say:

I'm talking about mapping the subjects, objects, adverbs, adjectives, and verbs, and phrases or clauses that play these roles, to corresponding program statements.

my response is "To what end?" While I expect programmers to see the Subject-Verb-Object nature of OO and to be able to use that, I don't see what you are doing much differently from normal OO education and/or what you hope to gain by it.

The point is also, in my opinion, to generate interest in programming, by making the student see the similarities in computer and human speech.

<don't take too seriously>Yes, connecting programming with grammar, a part of language proficiency many students find exciting.</don't take too seriously>

in case you think I'm not interested in algorithms

What did I say that gave you that idea? I did not think your ideas were particularly aimed at "algorithms", rather more at understanding of the basics of the languages particularly OO ones and at modelling(-esque) relationships. If I'm mistaken then since we are talking about students and beginning students, how would this be applied in the teaching of a sort, say? (bubble sort, insertion sort, quicksort, or whichever you prefer)

Finally, you mentioned you teach. Have you applied these ideas in your classrooms? How have they come across? How did you present them? Did it seem to make a difference? How well did the students do in later programming classes? And so forth.

By the way, in reading all the posts in this section of the blog, I keep wondering what exactly people mean by "semantics." I think semantics refers to meaning in relation to a particular domain, but it can also mean that the programmer is using a non-abstract vocabulary. Are you talking about the vocabulary of a particular programming language, and/or are you talking about applying the program logic to a particular domain? As I see it, these are two separate, albeit interrelated and somewhat overlapping ideas.

Syntax, as I understand it, refers to rules that a orthogonal to any particular vocabulary, although the syntactical rules themselves have to be stated in a particular vocabulary (in a semantic fashion). While the idea of syntax is usually applied to language, I imagine that it can also apply to the abstract (mathematical/logical) structure of, say, an algorithm. Do you agree.

Then there is the word "grammar." I'm not quite sure of how it differs in meaning from the word "syntax." Does it refer to certain aspects of syntax, or does it have a broader meaning than syntax? Or, do the words largely overlap in meaning, although there are some unique, non-overlapping differences.