Should I replace section
with partial
?
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 [1]. 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 right
) parameter.
In early versions of the course [2,3], we taught students about
left-section
and right-section
, which can be defined as follows.
(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 left
or 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 r-s
for right-section
).
(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 [4]. 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 left-section
and 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.
Fortunately, as I said, I have another two months to think about all of this [6,7].
[1] 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
.
[2] 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.
[3] 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.
[4] SRFI stands for something like Scheme Request for Implementation
.
The SRFIs represent suggested extensions to Scheme.
[5] There’s some other history that’s less important. I’ll leave that for another musing.
[6] I also have two months to talk to colleagues and upper-level students about it. I wonder what they’ll say.
[7] Unfortunately, I have a bunch of other stuff to think about, too.
Version 1.0 of 2018-11-21.