The Little Schemer, Chapter 8

I’ve been working through The Little Schemer, by Daniel P. Friedman and Matthias Felleisen. I’m up to Chapter 8 now.

Justin has been through the book and posted about it on his old blog. His post for Chapter 8 is here. He made a video about his work on Chapter 8, which is here.

I haven’t posted my work on The Little Schemer anywhere. But I’ll post some comments and questions about Chapter 8 in this thread.

Two things I noticed so far when I watched Justin’s video:

  1. Justin does more testing than I do. Maybe I should do more.
  2. When Justin is confused about something, he stays calm, whereas I sometimes start to feel frustrated. He has confidence that he can make progress in figuring the thing out. I sometimes don’t think I can make any progress–I either get it after reading it through a few times or I will never get it. I don’t want to think that way.

Question:

In Justin’s video, starting around 11:00, the question in the book (p. 127) is “Can you say what (lambda (a l) …) is?” Justin says “lambda returns a function that takes the arguments a and l”. I would have said “(lambda (a l) …) is a function”. Are both true? I don’t get how lambda returns a function. Is that the same as saying that having lambda at the beginning of (lambda ….) indicates that the whole thing is a function?

[code formatting added by me to the quotations]

The mindfulness meditation stuff can help with getting upset overall.

There’s also some generic stuff that applies to coding too. Like I think some generic issues people have when learning things are:

  1. Not having a reasonable expectation regarding the amount of work that can be expected (and feeling dumb when they have to do a lot of work).
  2. Not knowing how to break a problem down into small components.
  3. Underestimating the extent to which a large problem can be approached in small chunks, by e.g. working on small portions of it, writing analyses of what you do know, working on related skills, and so on.

But anyways this is all stuff that’s solvable.

FWIW i still get upset sometimes. Though not for very long, at least about this stuff. I mentioned an example here that was very recent:

A real programmer should feel free to jump in and tell me I’m wrong cuz I’m a newb and basing this off like one book.

I think that we say that a lambda returns a procedure, and that procedure is considered an anonymous procedure or unnamed procedure.

Here’s what happens when I run

(lambda (x) (* x x))

in DrRacket:

image

This is typical output if you just call a procedure without parentheses, btw. You’re evaluating the value of the procedure name but not invoking it. See e.g. list

image

But now consider:

((lambda (x) (* x x)) 2)

image

Now we’re taking that procedure returned by the lambda and actually giving it an argument. So this is kinda more like a procedure invocation

Simply Scheme has a whole chapter on lambda you might wanna revisit:

https://people.eecs.berkeley.edu/~bh/ssch9/lambda.html

I wouldn’t say that lambda returns a procedure, but I haven’t done much lisp. My intuition is to say that it defines an anonymous function. That said, this sort of thing can be language specific. (note: I think procedure = function in this case, but IDK maybe lisp/scheme uses the terms to mean diff stuff)

Lambda is the name of a special form that generates procedures. It takes some information about the function you want to create as arguments and it returns the procedure.

The first argument to every is, in effect, the same procedure as the one we called add-three earlier, but now we can use it without giving it a name. (Don’t make the mistake of thinking that lambda is the argument to every . The argument is the procedure returned by lambda.)

From: Simply Scheme: Introducing Computer Science ch 9: Lambda

So it seems fine to say that the function is returned by lambda. It sounds odd to me, tho, b/c I wouldn’t use that term for anon functions in other languages. Generated sounds better. That said, I think most programmers wouldn’t have trouble following along if you were explaining something and talked about lambda returning a function (there’s excess capacity in the term).

Lambda both creates and returns a procedure (aka function, same thing). The created procedure is the return value of the lambda call. (Source: I took SICP from Brian Harvey, author of Simply Scheme, and was his TA twice.)

2 Likes

Okay. So lambda both creates and returns a procedure.

Can I say that (lambda (x) (* x x)) (the whole thing, not just the word lambda) is a procedure? Or is that bad wording?

Yes, tho IDK if that’s technically correct. Either way I don’t think it’s a bottleneck.

Since the procedure is anonymous, it’s hard to talk about it otherwise. If we were sitting at a computer together looking at a page of source code, and I asked “which procedure?”, then a reasonable answer would be for you to select the whole thing and say “this one”.

I think that’s okay. I’ve also loosely referred to like, “the lambda” when talking about what the procedure returned by a lambda does (e.g. “the lambda here squares the argument it’s given”, something like that). So I kinda use lambda like a name sometimes, informally. I think that technically the lambda creates/returns an unnamed procedure that does whatever operation like squaring an argument, but it’s hard to be super technically precise all the time (though might be worth trying to be that precise some, especially if things are fuzzy)

New question:

Did the authors make an error in their insertL-f procedure (and similarly in insertR-f)?

insertL-f inserts new to the left of the first thing in l that passes the test? with old:

(define insertL-f
  (lambda (test?)
    (lambda (new old l)
      (cond ((null? l) (quote ()))
            ((test? (car l) old) (cons new (cons old (cdr l))))
            (else (cons (car l) ((insertL-f test?) new old (cdr l))))))))

Their examples have test? being eq? or some other version of equality. In that case, their procedure works.

But if test? is something like “is the element of length old?”, then it doesn’t work. On the next-to-last line, instead of old, they should have (car l), right?

Or am I misunderstanding?

This is fine.

The term lambda comes from lambda calculus. Lambda calculus is an area of maths about particular ways of writing (like \lambda x.*xx) and reducing functions – and those methods are foundational to lisps and other functional languages (like Haskell). From the linked wiki page:

A valid lambda calculus expression is called a “lambda term”.

So basically I think calling the lambda expression (i.e., the full function) a lambda is fine. If you wanted to be more explicit you could say “lambda expression” or “lambda function”.

I wanted to mention all that b/c the general concept of (and words used for) a lambda expression overlaps with scheme’s lambda special form. In other languages the word lambda isn’t a reserved keyword, but you can still write lambda functions, and you could still call them lambdas. e.g., these two expressions do the same thing (the first in scheme, the second in haskell, and third as a lambda expression): (lambda (x) (* x x)) and \x -> x * x and \lambda x.*xx.

Yeah, there are lots of things that programmers skip over or shortcut in this way – it’s not a big deal mostly. An example is how ppl talk about a function’s arguments and parameters – usually ppl treat those terms as interchangeable. I think technically “arguments” are the values that get passed in to a function call, and “parameters” are the input variables that a function takes. e.g.: (in python)

# declare a function `f` with a single parameter: `x`
def f(x):
  return x*x

def main():
  # call `f` with the argument `3`
  return f(3)

I prefer to get this kind of thing right, especially while I’m a beginner, because it helps me understand better. I’ve been using “argument” wrong and I’ll try to fix that going forward.

off-topic but i wonder how easy it would be to turn on good syntax highlighting + line numbers for discourse. it was pretty easy to do for my blog

1 Like

I’m not quite following. You think instead of…

(cons new (cons old (cdr l))))

…it should be…

(cons new (cons (car l) (cdr l))))

…do I have that right? I’m not sure I see why. Can you try putting in code the case for which you think their approach wouldn’t work?

I should have thought to give an example. Here’s one:

(define divisible-by?
  (lambda (x y)
    (integer? (/ x y))))

> ((insertL-f divisible-by?) 0 2 '(3 4 5 6))
'(3 0 2 5 6)

The program is meant to insert a 0 before the first thing in the list that’s divisible by 2. It did that, but it also changed the thing that’s divisible by 2 to a 2 because old is 2. car l at that point would be 4. Does this make sense?

More importantly, I should have thought to try out some examples on my own. I was just going by reading the code. I should be trying things out more.

i think the insert procedures had in mind the context that you were trying to insert a new value on the basis of whether a particular element in the list that was pre-existing - the old value - passed a test.

i am looking at your example. it seems like, if we follow the substitution model, the formal parameters within the lambdas of insertL-f would be misnamed. e.g. 2 would be substituted in for old. But 2 is not actually a value that appears in the list l.

if the parameters appear misnamed for a particular use-case, that seems like a sign that maybe we are trying to get the procedure to do stuff that was not within the anticipated scope of the procedure as it was designed

Good point that the parameters seem to be misnamed for how I’m thinking about it, so maybe they’re not intending what I have in mind.

The only way I can make sense of their procedure is if they meant test? to always be a test for equality. Depending on what kind of things you wanted to know the equality of, you’d use a different procedure for testing that equality.

This seems limiting to me, but it makes their procedure okay, and they never talked about any other kind of test. So I think you’re right that that’s what they intended.