Should I replace
Topics/tags: CSC 151, functional programming, Racket, teaching, technical
As you may recall from a recent musing, I’d been working on a reading on higher-order procedures intended for the new version of CSC 151. Higher-order procedures are procedures that take other procedures as input, produce procedures as output, or both. They are a core aspect of functional programming and also one of the things that distinguish Grinnell’s CSC 151 from other introductory CS courses . While reflecting on that issue, I’d put the reading aside for a bit after writing that musing. I’ve come back to it recently.
The second major question I had in approaching higher-order procedures from a new perspective was how to deal with what we call
sectioning. Sectioning is an approach in which you take an extant procedure and fill in one or more of its parameters with constants. For example, to create a one-parameter procedure that subtracts 2 from its parameter, you section the two-parameter subtraction operation using the value 2 for the second (or
(define left-section (lambda (proc left) (lambda (right) (proc left right)))) (define right-section (lambda (proc right) (lambda (left) (proc left right))))
In both cases, we’ve defined a procedure (
lambda) of two parameters (
proc and either
right) that returns another procedure (the second
lambda) that takes another parameter and applies
proc appropriately. With those defined, we might define
sub2 as follows.
(define sub2 (right-section - 2))
Why would we ever teach students to program this way? In part, because it’s an important way of thinking about programming and about the use of functions. In part, because it permits some more concise and efficient ways of approaching the world. For example, functional programmers, when asked to subtract 2 from each element of a list, are likely to write an expression like the following (using the more concise
(map (r-s - 2) lst)
I appreciate higher-order programming enough that, when I worked with a team to design the new media-computation version of CSC 151, I looked for ways to move higher-order concepts earlier in the course. Certainly, what we called the
functional model of image making (
an image is a function from (x,y) position to color) is one example.
At some point, I was inspired to think about more general versions of these operations, ones that supported procedures of more than two parameters. I don’t recall all the issues that led me to consider the issue, but I know that a draft of John Stone’s Algorithms for Functional Programming was one key factor.
And so I sat down to write the general
section in Racket. At some point, I realized that Sebastian Egner had described something similar in SRFI 26 . Egner called has procedure
cut, rather than
section, but it does more or less the same thing. He uses a symbol,
<>, that he calls
slot (and we call
diamond) for missing parameter. Using our variant of this notation, one might define
sub2 as follows.
(define sub2 (section - <> 2))
I think that’s the important history: We started with
right-section and, at some point, we added the general
section. That brings us to these past few weeks, when I was working on the reading on higher-order procedures for the new course. I’d generally introduced sectioning and composition in the context of another higher order procedure, such as
image-variant in the media-computation version and
map in the data-science version. This time, I’m trying to introduce them as just another basic way to write procedures.
One thing I realized as I was writing new text is that many students get confused that the procedure in section appears in an odd position. They’re used to the procedure appearing immediately after an open parenthesis. So I’ve been thinking about an alternative, which I call
partial expressions and denote
Px. Here’s how we’d define
sub2 with that model.
(define sub2 (Px (- __ 2)))
As you might be able to tell, I’ve also replaced the diamond with a different symbol,
__. I made that choice after talking with a colleague; we both agreed it made the
missing piece seem a bit clearer. But is this form better than
section? I’m not sure. I’m not thrilled with the name
Px as an alternative to
section. I tried
partial, but I didn’t like that much, either. I couldn’t think of a good symbol like the
o I use for composition. I’m also not as happy as I thought I’d be about the form. I’m wondering whether students will find it clearer. But I still have a few months to think about the issue.
There’s another possible advantage of this model; students can put the parameter" marker within a nested operation, which wasn’t as natural in the cut model. For example, we can write a procedure that counts the number of words in a string as follows.
(define num-words (Px (length (string-split __ " "))))
Is that better than the lambda equivalent?
(define num-words (lambda (str) (length (string-split str " "))))
The partial version is certainly shorter. But this example makes me realize that it’s less clear that
Px is taking a procedure as one of its parameters. On the other hand, a colleague has suggested that students are often confused why the diamonds can only appear at the top level of a section. So maybe this is a better approach.
 The CS education literature is filled with debates about
objects early and
objects late. I always say that we’re a
hop early curriculum. Now I realize that I could add,
which allows our students to get a jump on important concepts.
 I can trace it back to the first time I taught CSC 151, in Fall 2000. That reading lives on at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Readings/hop.html.
 We still cover them in current versions, just in a different context. There are early readings on using higher-order procedures and then a later reading on writing higher-order procedures. The details appear there.
 SRFI stands for something like
Scheme Request for Implementation. The SRFIs represent suggested extensions to Scheme.
 There’s some other history that’s less important. I’ll leave that for another musing.
 I also have two months to talk to colleagues and upper-level students about it. I wonder what they’ll say.
 Unfortunately, I have a bunch of other stuff to think about, too.
Version 1.0 of 2018-11-21.