Simply Scheme Chapter 9 – Lambda

Lambda

lambda lets us generate procedures without having to give them a name. This can lead to nicer program organization compared with the alternatives (such as making a helper function):

Another example, which uses lambda to provide a procedure to the higher order function accumulate:

I think this is going through the words of 'wild honey pie one by one. If the first word is greater than the second word, it returns the first word. Otherwise, it returns the second word. Since it’s only returning one value each time and not actually combining anything, you only wind up with one word in the end.

Define & Let

define actually gives a name to values. lambda creates procedures. (define (square x) (* x x)) is short for (define square (lambda (x) (* x x))).

In this example, the job of lambda is to create a procedure that multiplies its argument by itself; the job of define is to name that procedure square.

In something like (* x x), the * has to be substituted just like the x does. But for * there’s a global definition that’s been predefined by define.

Just as the notation to define a procedure with parentheses around its name is an abbreviation for a define and a lambda, the let notation is an abbreviation for a lambda and an invocation.

When to Name Functions

Use names for procedures when you can give a meaningful name that will help clarify the program.

Use names for stuff that you’ll use often.

Shorter Notes

Don’t use the same formal parameter for both a procedure and a procedure inside a procedure.

Boring Exercises

✅❌ Exercise 9.1

What will Scheme print? Figure it out yourself before you try it on the computer.

I predicted that this would return a procedure which takes a value, multiplies it by 3, and adds 4.

❌ I was correct in my description but a bit non-responsive to the question. I should have said “it will print something indicating that scheme is returning a procedure”.

---

✅ I correctly predicted that this would print 34.

---

✅ I correctly predicted that this would print'(yan etim ta lal). The lambda will create a word that starts with the last character of each word and then combines that with all but the last characters of each word, and then every will return a sentence full of such words (one for each word in the sentence).

---

This seems to have too many arguments for the lambda. I predict an error message about too many arguments.

✅ Yup.

✅ Exercise 9.2

Rewrite the following definitions so as to make the implicit lambda explicit.

rewrite:

---

Rewrite:

✅ Exercise 9.3

What does this procedure do?

The lambda defines two formal parameters, x and y. The lambda always returns y. accumulate typically operates by applying a procedure to two variables that combines them in some way. There is no combining going on here, however. So the ultimate result, I think, will be that what gets returned is the last word of a sentence.

✅ Yup. It also returns the last letter of a word.

Real Exercises

✅ Exercise 9.4

The following program doesn’t work. Why not? Fix it.

It’s supposed to work like this:

What we want in the spot where describe is is something that returns a procedure that can take the input sent and apply it to the '(pete roger john keith)) sentence.

The describe program seems to assume it can take sent as an argument, but sent is never provided to describe.

We can make this work with lambda

---

In each of the following exercises, write the procedure in terms of lambda and higher-order functions. Do not use named helper procedures. If you’ve read Part IV, don’t use recursion, either.

---

✅ Exercise 9.5

Write prepend-every:

Answer:

✅ Exercise 9.6 – Note about lambda and program structure

Write a procedure sentence-version that takes a function f as its argument and returns a function g. f should take a single word as argument. g should take a sentence as argument and return the sentence formed by applying f to each word of that argument.

Answer:

NOTE: My answer works but is unnecessarily complicated. I recreated some of the functionality of every unnecessarily. every can already apply a function to each word of a sentence. AnneB’s version is more elegant:

This problem illustrates an important distinction in the text:

For example, here is a procedure to keep the words of a sentence that contain the letter h. The domain of the function is sentences, and its range is also sentences. (That is, it takes a sentence as argument and returns a sentence as its value.)

By contrast, here is a function of a letter that returns a procedure to keep words containing that letter.

The procedure keeper has letters as its domain and procedures as its range. The procedure returned by keeper has sentences as its domain and as its range, just as keep-h does.

In keep-h, the lambda returns a procedure which looks to see if h is part of a word, but that procedure is returned to the keep and is used directly on the input to keep-h. The lambda isn’t the highest level thing in the procedure, so the procedure it returns is used by the higher-order function keep.

OTOH with keeper, the lambda is the highest level thing in the keeper. It’d be the root of a tree of the function. So the lambda has nothing within the program to return a procedure to. Therefore, the overall procedure returns a procedure.

✅ Exercise 9.7

Write a procedure called letterwords that takes as its arguments a letter and a sentence. It returns a sentence containing only those words from the argument sentence that contain the argument letter:

Answer:

The lambda returns a predicate procedure which checks if the value for letter is present in a word. If this is so, the lambda procedure returns true; otherwise, it returns false. keep applies the procedure returned by lambda to each of the words in the sent, and keeps the ones for which the value of the lambda procedure is true.

NOTE: again, my program is a bit inelegant. The if is unnecessary. keep can work just fine with a lambda procedure that checks if letter is a member of a word in a more straightforward way. AnneB’s version:

Since the (member? letter w) returns true or false, it’s an appropriate predicate for keep without needing to toss an if statement in there.

✅🤔 Exercise 9.8

Suppose we’re writing a program to play hangman. In this game one player has to guess a secret word chosen by the other player, one letter at a time. You’re going to write just one small part of this program: a procedure that takes as arguments the secret word and the letters guessed so far, returning the word in which the guessing progress is displayed by including all the guessed letters along with underscores for the not-yet-guessed ones:

Hint: You’ll find it helpful to use the following procedure that determines how to display a single letter:

This question is ambiguous. I initially thought they wanted us to use the hang-letter procedure directly. I based this on the statement:

You’ll find it helpful to use the following procedure that determines how to display a single letter:

They said use, not “look at” or “draw inspiration from” or something like that.

OTOH, after exercise 9.4 there is the following instruction:

In each of the following exercises, write the procedure in terms of lambda and higher-order functions. Do not use named helper procedures. If you’ve read Part IV, don’t use recursion, either.

I read this as applying to all the remaining exercises, since it says “each”. I read 9.8 as being an exception to that instruction (it’s like how in law, a more specific rule in a subset of X tends to control versus a more general rule at a higher level of X, unless there’s something that says “this rule trumps other stuff”.)

So anyways I read what we were supposed to do one way. buntine appears to agree with my reading. So I solved it my way, but then started to read AnneB’s answer in which she took the helper procedure as more of a hint for making a procedure with no helper procedures. At that point I stopped reading AnneB’s answer to try to figure something similar to her approach by myself.

An issue with my initial solution (before reading AnneB’s stuff) is that I didn’t return the correct thing …. I wanted a word and not a sentence.

Initial Answer:

Corrected initial answer:

Description: the lambda procedure returns a letter if the letter matches a word containing the existing guesses, and returns an underscore if the letter does not match the guesses. every applies the lambda procedure to each letter of a word and returns the results as a sentence.

Okay so let’s try rewriting the procedure without a separate hang-letter.

This version has a lambda that checks if a letter is a member of the list of existing guesses. If so, it returns that letter. Otherwise, it returns an underscore. every applies this lambda procedure to each letter in the list of existing guesses and returns a sentence. accumulate word takes this sentence and transforms it into a word.

I checked and my second version is basically the same as AnneB’s aside from the fact that mine returns a word.

✅ Exercise 9.9

Write a procedure common-words that takes two sentences as arguments and returns a sentence containing only those words that appear both in the first sentence and in the second sentence.

The lambda checks a word in sent1 and sees if it’s a member of sent2. keep applies this lambda procedure to each word in sent1, so that each word in sent1 is checked for its membership in sent2, and words that return true as members are kept and returned by common-words.

✅ Exercise 9.10

In Chapter 2 we used a function called appearances that returns the number of times its first argument appears as a member of its second argument. Implement appearances.

Answer:

I checked to make sure that the values returned were the same as the version of appearances I’d played around with earlier:

AnneB’s version is more elegant since she used count and keep whereas I used accumulate and returning number values:

✅ Exercise 9.11

Write a procedure unabbrev that takes two sentences as arguments. It should return a sentence that’s the same as the first sentence, except that any numbers in the original sentence should be replaced with words from the second sentence. A number 2 in the first sentence should be replaced with the second word of the second sentence, a 6 with the sixth word, and so on.

Answer:

Here is AnneB’s for comparison:

I think this time my solution is more elegant, cuz I think using item to pull the appropriate word is more elegant than doing the (first ((repeated butfirst (- word1 1)) sentence2)) thing.

✅ Exercise 9.12

Write a procedure first-last whose argument will be a sentence. It should return a sentence containing only those words in the argument sentence whose first and last letters are the same:

answer:

another example of inelegance. you can just return the truth value provided by equal? to keep directly, like AnneB does:

✅ Exercise 9.13

Write a procedure compose that takes two functions f and g as arguments. It should return a new function, the composition of its input functions, which computes f(g(x)) when passed the argument x.

Answer:

✅ Exercise 9.14

Write a procedure substitute that takes three arguments, two words and a sentence. It should return a version of the sentence, but with every instance of the second word replaced with the first word:

My initial answer:

the lambda checks if a word in the sentence sent-wd is equal to the second word wd2. If so, it returns wd1, which effectively replaces wd2 with wd1. Otherwise, it returns sent-wd, which leaves the word from the sentence in place. every applies this to each word of sent and returns a sentence with the result.

✅ Exercise 9.15

Many functions are applicable only to arguments in a certain domain and result in error messages if given arguments outside that domain. For example, sqrt may require a nonnegative argument in a version of Scheme that doesn’t include complex numbers. (In any version of Scheme, sqrt will complain if its argument isn’t a number at all!) Once a program gets an error message, it’s impossible for that program to continue the computation.
Write a procedure type-check that takes as arguments a one-argument procedure f and a one-argument predicate procedure pred. Type-check should return a one-argument procedure that first applies pred to its argument; if that result is true, the procedure should return the value computed by applying f to the argument; if pred returns false, the new procedure should also return #f:

answer:

✅ Exercise 9.16

In the language APL, most arithmetic functions can be applied either to a number, with the usual result, or to a vector-the APL name for a sentence of numbers-in which case the result is a new vector in which each element is the result of applying the function to the corresponding element of the argument. For example, the function sqrt applied to 16 returns 4 as in Scheme, but sqrt can also be applied to a sentence such as (16 49) and it returns (4 7).
Write a procedure aplize that takes as its argument a one-argument procedure whose domain is numbers or words. It should return an APLized procedure that also accepts sentences:

My initial answer (which I revised):

My second attempt at an answer (to cover the word case):

This produces the desired output for apl-sqrt. i also made a procedure that appends the letter e to a single word and tested that as well. I got the expected results:

AnneB’s solution is a bit more elegant. It relies on the fact that numbers return #t to word?. Anne’s version therefore doesn’t do two separate checks for both word? and number? like my version does:

buntine’s solution is similar to Anne’s except that buntine has the if check for whether something is a sentence:

❌ Exercise 9.17

Write keep in terms of every and accumulate

I figured out a partial solutions to this one but got a bit stuck.

Normal keep returns the word 239 for the following input:

but my keep2 procedure returns '(2 3 9)

The basic way keep2 works is that the lambda takes an element and checks if the predicate procedure provided to keep is true. If so, it returns that element. If not, it returns an empty sentence. every applies this lambda procedure to each element in the input sentence. the empty sentences don’t actually appear in the final sentence produced by every.

Since I was feeling a bit stuck, I looked at an old solution of mine from a prior run through the book:

the lambda part is pretty similar to what I wrote above.

This program uses let to define the value of stuff as the big   (every (lambda (inputelem) (if (pred inputelem) inputelem '())) inputs))) statement. It then tests whether inputs is a word. If so, it runs accumulate word on stuff. So basically, stuff has produced a sentence, and then that sentence gets accumulated into a word. Alternatively, if inputs is not a word, then stuff gets returned as a sentence.

I think I partially had trouble thinking about this solution again because I don’t have a good handle on using let yet. So maybe that is something to work on.

The functional keep1 procedure having the proper range (sentences AND words) is really important. keep2 only had sentences in its range.

Here is a tree I made comparing my flawed program with my working one: