Simply Scheme Chapter 10 – Tic Tac Toe

Note: References to “the computer” or “the player” are interchangeable and refer to whatever side the ttt procedure will act on behalf of. References to a “mark” are references to an x or o, which I think of as marks that a player makes on a tic-tac-toe board.

For this chapter we’re loading ttt.scm. It’s a Tic-Tac-Toe program that takes the following arguments: the current game board state (in the form of a word like '__o_xox_x, where each character corresponds to a position on the game board) and whether the computer is playing x or o.

For this chapter I quoted heavily and made comments on the quoted material as I went along.

Here’s how the board locations are numbered:

When referring to “triples” like 1-5-9 below, I’m using this numbering of the spaces.

Here’s the board state that '__o_xox_x corresponds to:

Strategy

The focus of the chapter is on strategy. Tic-tac-toe is a fairly simple game strategically – perfect play is easily doable. The book lays out the following first draft implementation of strategy:

This lacks a bunch of detail like arguments, and is more in the vein of a pseudo-code roadmap for what we want to do.

Triples

You win tic-tac-toe by getting three of the same value (x’s or o’s) in a row, so these triples (1-5-9, 3-5-7, 1-2-3, 4-5-6, 7-8-9, 1-4-7, 2-5-8, 3-6-9) are key.

So we want to a list of triples and the current board position and put that information together somehow so that we can determine what the next move should be.

Our program will start with this sentence of all the winning combinations:

and a position word such as _xo_x_o__; it will return a sentence of triples such as

All that’s necessary is to replace some of the numbers with xs and os. This kind of word-by-word translation in a sentence is a good job for every.

substitute-triple, which we haven’t written yet, will take 3 digits from our list of triples and make the appropriate substitutions with the information from position. (Note that substitute-triple isn’t currently being passed position as an argument).

substitute-triple will have a procedure called substitute-letter which does the actual substitution of the letters:

We want triples to be words, not sentences like (2 x 8), so substitute-triple should return words:

(This process of iterating on a program to get it closer to what we want to do is fun).

Substitute-letter knows that letter number 3 of the word that represents the board corresponds to the contents of square 3 of the board.

Hmm not currently sure how it knows that.

This means that it can just call item with the given square number and the board to find out what’s in that square. If it’s empty, we return the square number itself; otherwise we return the contents of the square.

Whoops! Do you see the problem?

This is the same issue I was worrying about earlier.

Using Every with Two-Argument Procedures

Our procedure only takes one argument, square, but it needs to know the position so it can find out what’s in the given square. So here’s the real substitute-letter:

Now substitute-letter can do its job, since it has access to the position. But we’ll have to modify substitute-triple to invoke substitute-letter with two arguments.

Right. This is the thing I was wondering about earlier. Since substitute-triple calls substitute-letter, we’ve got to give substitute-triple access to position. Are we gonna use a lambda or let or something perhaps?

This is a little tricky. Let’s look again at the way we’re using substitute-letter inside substitute-triple:

By giving substitute-letter another argument, we have made this formerly correct procedure incorrect. The first argument to every must be a function of one argument, not two. This is exactly the kind of situation in which lambda can help us: We have a function of two arguments, and we need a function of one argument that does the same thing, but with one of the arguments fixed.

πŸ€” I’m not 100% sure I follow this part. Is substitute-letter only a function of one argument in the lambda below? It seems like it’s still taking two arguments.

The procedure returned by

does exactly the right thing; it takes a square as its argument and returns the contents of the position at that square.
Here’s the final version of substitute-triple:

Ok so summing up in my own words so far:

substitute-letter takes a square and state of the game (called position). It uses item plus the number of the square to determine whether a particular square is empty (which is represented by an underscore character _.) If the square is empty, the number of the square is returned (so in the example with the arguments 456 '_xo_x_o__), as the 4 square is empty, 4X6 is returned.) If the square is not empty, the x or o value of the square is returned.

substitute-triple applies substitute-letter to each square in a triple and then accumulates the result in a word. The lambda returns a procedure that runs the substitute-letter procedure on a particular square. The every procedure applies these lambda procedures to each digit of a particular combination (such as “456”), and returns the result in sentence form, and then the sentence results are accumulated into words.

We’ve fixed the substitute-letter problem by giving substitute-triple an extra argument, so we’re going to have to go through the same process with find-triples. Here’s the right version:

It’s the same trick. Substitute-triple is a procedure of two arguments. We use lambda to transform it into a procedure of one argument for use with every.

Thinking about this issue some more…position is fixed but comb varies. Like the every will provide the lambda here with 123 as the comb and 456 and so on. And the lambda only has one formal parameter defined. I’m not sure which of those is the critical decisive factor in terms of what lets us say that the lambda is now a one-argument function but I can maybe see the idea a bit.

Wait…I was looking at how the unnamed procedure is defined (in terms of another procedure) and looking at the number of arguments the procedure inside the lambda took, rather than thinking about what arguments the lambda was taking (namely, the one parameter defined for each lambda)

We’ve now finished find-triples, one of the most important procedures in the game.

Can the Computer Win on This Move?

Finally, the computer can win if it owns any of the triples:

the not (empty? part causes the procedure to return true if there are any triples the computer “owns”.

If So, in Which Square?

Suppose i-can-win? returns #t. We then have to find the particular square that will win the game for us. This will involve a repetition of some of the same work we’ve already done:

This would keep the number from a triple that can be won on the next move. Since the number represents the fact that a square is not occupied by an x or o, then that number represents the square where a winning move can be made.

We again use keep to find the triples with two of the computer’s letter, but this time we extract the number from the first such winning triple.

Right.

We’d like to avoid this inefficiency. As it turns out, generations of Lisp programmers have been in just this bind in the past, and so they’ve invented a kludge to get around it.
Remember we told you that everything other than #f counts as true? We’ll take advantage of that by having a single procedure that returns the number of a winning square if one is available, or #f otherwise.

Ok that makes sense as a solution.

In Chapter 6 we called such a procedure a “semipredicate.” The kludgy part is that cond accepts a clause containing a single expression instead of the usual two expressions; if the expression has any true value, then cond returns that value. So we can say

where each cond clause invokes a semipredicate.

I was unclear on this point so I wound up trying to explain it at length.

So normally a cond expression looks something like this

in this we see two distinct expressions – for example, (equal? letter 'i) and 1. The second expression is returned if the condition in the first expression is met.

However, earlier, in chapter 6, the book authors did give us the following warning:

Don’t get into bad habits of thinking about the appearance of cond clauses in terms of “two parentheses in a row.” That’s often the case, but not always. For example, here is a procedure that translates Scheme true or false values (#t and #f) into more human-readable words true and false.

The meaning of (value 'true) is basically “If value is #t, return 'true.” Because Scheme defaults to treating stuff as true unless it’s false, then if value has any non-false value, truefalse will return #t. And this is accomplished inside a single set of parentheses. However, even with truefalse, there is still a separation between the thing being evaluated and the thing being returned. In other words, value is the thing that is getting evaluated for its truth value, and 'true is the thing being returned if the evaluation of value is #t.

With the proposed changes to our tic-tac-toe program, (i-can-win? triples me) will return a single value that will 1) provide the truth value that is evaluated as true or false for the purposes of the cond expression and 2) provide additional information (besides merely being true or false) when returning a true value (namely, it will return the number of the square that provides the winning move).

We then modify i-can-win? to have the desired behavior:

my-pair? takes a triple and the computer’s mark (x or o) as arguments and then determines whether a triple has 2 appearances of the computer’s marks and 0 appearances of the opponent’s marks.

i-can-win? takes the existing set of triples (based on the current game state) and the computer’s mark as arguments and then invokes choose-win. The list of all triples is filtered by the operation of a lambda function in conjunction with keep. The lambda determines whether a particular triple is “owned” by the computer using my-pair?. If a triple is “owned” by the computer, then that satisfied the my-pair predicate and it is kept and passed to choose-win.

choose-win takes a list of winning triples as arguments. If the list is empty, it returns #f. Otherwise, it keeps and returns the number that is present in the first winning triple.

Second Verse, Same as the First

Now it’s time to deal with the second possible strategy case: The computer can’t win on this move, but the opponent can win unless we block a triple right now.
(What if the computer and the opponent both have immediate winning triples? In that case, we’ve already noticed the computer’s win, and by winning the game we avoid having to think about blocking the opponent.)
Once again, we have to go through the complicated business of finding triples that have two of the opponent’s letter and none of the computer’s letter-but it’s already done!

Is that amazing or what?

the opponent procedure returns the other mark (x or o) from whatever the computer’s mark is, and a lot of our work can work fine with either side so that saves us a lot of work.

Finding the Pivots

Pivots should return a sentence containing the pivot numbers. Here’s the plan. We’ll start with the triples:

We keep the ones that have an x and two numbers:

Right, these are our candidates for potentially finding pivots. And we already dealt with the 2 x’s case earlier with i-can-win?.

We mash these into one huge word:

We sort the digits from this word into nine “buckets,” one for each digit:

We see that there are no ones or twos, one three, two fours, and so on. Now we can easily see that four and seven are the pivot squares.

Right. The repeated appearance of a number in triples where our mark appearances once indicates a pivot.

Let’s write the procedures to carry out that plan. Pivots has to find all the triples with one computer-owned square and two free squares, and then it has to extract the square numbers that appear in more than one triple.

My-single? is just like my-pair? except that it looks for one appearance of the letter instead of two.

Makes sense. And then the lambda in pivots checks if a particular triple is returns true for my-single?, and a list of triples that meet that criteria is returned to repeated-numbers for further processing.

Repeated-numbers takes a sentence of triples as its argument and has to return a sentence of all the numbers that appear in more than one triple.

We’re going to read this procedure inside-out, starting with the accumulate and working outward.
Why is it okay to accumulate word the sentence? Suppose that a number appears in two triples. All we need to know is that number, not the particular triples through which we found it.

Right that makes sense.

Therefore, instead of writing a program to look through several triples separately, we can just as well combine the triples into one long word, keep only the digits of that word, and simply look for the ones that appear more than once.

We now have one long word, and we’re looking for repeated digits. Since this is a hard problem, let’s start with the subproblem of finding all the copies of a particular digit.

Seems like maybe you could use appearances somehow perhaps?

Ok so what this appears to do is check the word with the digits for the presence of a desired digit. Specifically, the lambda checks to see if a digit is in the digit-word is equaled to the desired digit. If so, it returns all instances of that digit.

Now we want a sentence where the first word is all the 1s, the second word is all the 2s, etc. We could do it like this:

that looks inelegant!

but that wouldn’t be taking advantage of the power of computers to do that sort of repetitious work for us. Instead, we’ll use every:

So this program has a lambda which takes a digit and number-word and returns the digit the same number of times it appears in number-word. number-word is an argument from sort-digits and the digit is provided by the Β '(1 2 3 4 5 6 7 8 9)Β  sentence. every applies the lambda to every digit of the Β '(1 2 3 4 5 6 7 8 9) sentence and returns a sentence with all the copies of the extracted digits.

Sort-digits takes a word full of numbers and returns a sentence whose first word is all the ones, second word is all the twos, etc.[2]

what’s with the 5 ""‘s? I thought maybe it was related to the x‘s but there are only 3 of those.

Let’s look at repeated-numbers again:

So repeated-numbers takes a sentence of triples. It has to return a sentence of all the numbers that appear in more than one triple.

sort-digits accumulates a word from the triples and then sorts the numbers and groups instances of the same number that appear more than once together as words within a sentence.

The keep (lambda (wd)... bit keeps all the words within the sentence created by sort-digits that appear at least twice (which indicates a pivot)

Then every-first returns only the first digit of each pivot-word.

This concludes the explanation of pivots. Remember that i-can-fork? chooses the first pivot, if any, as the computer’s move.

Taking the Offensive

Here’s the final version of ttt-choose with all the clauses shown:

You already know about the first three possibilities.
Just as the second possibility was the “mirror image” of the first (blocking an opponent’s move of the same sort the computer just attempted), it would make sense for the fourth possibility to be blocking the creation of a fork by the opponent. That would be easy to do:

Unfortunately, although the programming works, the strategy doesn’t. Maybe the opponent has two potential forks;

πŸ€” What would two potential forks look like?

we can block only one of them. (Why isn’t that a concern when blocking the opponent’s wins? It is a concern, but if we’ve allowed the situation to reach the point where there are two ways the opponent can win on the next move, it’s too late to do anything about it.)
Instead, our strategy is to go on the offensive. If we can get two in a row on this move, then our opponent will be forced to block on the next move, instead of making a fork. However, we want to make sure that we don’t accidentally force the opponent into making a fork.

Ok, so there are two steps: get two in row, but make sure that doing so doesn’t force the opponent into making a fork. If you get two in a row, and then the opponent blocks you with a move that makes a fork, then that’s a kinda pyrrhic victory. The opponent will block you so you won’t win, and then you won’t be able to stop the opponent from winning. So you can’t just look at the game next moves from your point of view but need to look at them from the opponent’s point of view.

Let’s look at this board position again, but from o‘s point of view:

The board position here is ‘xo__x___o

X‘s pivots are 4 and 7, as we discussed earlier; o couldn’t take both those squares. Instead, look at the triples 369 and 789, both of which are singles that belong to o. So o should move in one of the squares 3, 6, 7, or 8, forcing x to block instead of setting up the fork. But o shouldn’t move in square 8, like this:

because that would force x to block in square 7, setting up a fork!

So o wants to make sure that a move doesn’t put x in an i-can-fork? position.

The structure of the algorithm is much like that of the other strategy possibilities. We use keep to find the appropriate triples, take the first such triple if any, and then decide which of the two empty squares in that triple to move into.

getting a little overwhelmed by all the procedures so I’m making trees to help me understand them.

For the board state 'xo__x___oΒ  mentioned above, for the following input:

the value returned is 7 (note that I used find-triples so I could test this part of the procedure separately.)

Best-move does the same job as first-if-any, which we saw earlier, except that it also invokes best-square on the first triple if there is one.
Since we’ve already chosen the relevant triples before we get to best-move, you may be wondering why it needs all the triples as an additional argument. The answer is that best-square is going to look at the board position from the opponent’s point of view to look for forks.

Right okay. The triples that are relevant from our side’s perspective don’t address the issue of what potential moves the other player might make.

We keep the two numbers of the triple that we’ve already selected. We also select the opponent’s possible pivots from among all the triples. If one of our two possible moves is a potential pivot for the opponent, that’s the one we should move into, to block the fork.

Right okay, and that’s what Β (if (member? (first pair) opponent-pivots) is doing – checking the two numbers of our triple against the opponent’s pivots.

Otherwise, we arbitrarily pick the second (last) free square.

What if both of the candidate squares are pivots for the opponent? In that case, we’ve picked a bad triple; moving in either square will make us lose. As it turns out, this can occur only in a situation like the following:

If we chose the triple 3o7, then either move will force the opponent to set up a fork, so that we lose two moves later. Luckily, though, we can instead choose a triple like 2o8. We can move in either of those squares and the game will end up a tie.
In principle, we should analyze a candidate triple to see if both free squares create forks for the opponent. But since we happen to know that this situation arises only on the diagonals, we can be lazier. We just list the diagonals last in the procedure find-triples. Since we take the first available triple, this ensures that we won’t take a diagonal if there are any other choices.

Ah that’s clever.

Exercises

❌ Exercise 10.1

The ttt procedure assumes that nobody has won the game yet. What happens if you invoke ttt with a board position in which some player has already won? Try to figure it out by looking through the program before you run it.

So I think looking through the main cond in ttt-choose is a reasonable way to organize my answer to this:

i-can-win?‘s helper procedure my-pair? looks for triples where the number of appearances of the computer’s marks is exactly 2. So I don’t think i-can-win would “catch” a winning board position.

i-can-fork?‘s helper procedure my-single? triples with 1 appearance of the opponent’s marks, so likewise it won’t “catch” the 3 case.

i-can-advance? also relies on my-single?, so the same logic applies.

So I think maybe ttt-choose would default to using best-free-square. I’m low-confidence on this though.

UPDATE: I tried playing with it some and it seemed to just recommend that I make moves without acknowledging that victory had occurred. By the way, I realized that depending on the game board, the program might actually find triples that meet the criteria of the strategy other than the “winning” triple. So basically my updated guess is that the program would analyze the game state as normal without taking into account the fact that there was a winner.

SECOND UPDATE: I missed the fact mentioned by AnneB that the program will return an error if there are no empty square

A complete tic-tac-toe program would need to stop when one of the two players wins. Write a predicate already-won? that takes a board position and a letter (x or o) as its arguments and returns #t if that player has already won.

I used modifications of existing stuff in ttt and built on top of the existing program some. So note, this is intended to be run as an addition to the ttt program. It particular relies on find-triples, substitute-triple, and substitute-letter and can be run just with those parts.

already-won? invokes i-have-won and generates the triples using find-triples.

i-have-won invokes choose-winner and uses my-win? to filter the triples for winning triples.

my-win? looks for triples where there are 3 appearances of the computer’s mark. There’s no checking for the opponent’s mark, because if there are actually 3 of the computer’s mark then you know the opponent’s mark number is 0.

return-true-if-winner returns #true if there are any winning triples (meaning triples where we’ve already won).

This program appears to work:

Ok so solves the problem but is wildly overcomplicated. Here’s buntine’s effort for comparison:

So this checks whether a word consisting of the letter three times is a member of the list of triples generated by (find-triples position). Very easy!

Here’s AnneB’s:

I’m going to go through Anne’s procedure and then compare my procedure and Anne’s procedure.

Anne’s procedure works as follows:
The lambda checks whether a particular triple is equal to three instances of the computer’s mark me. This would indicate a winning triple. keep tests each triple generated by find-triples for whether it is true for (equal? (word me me me), and if the list of triples generated by keep is not empty? (indicating that there is at least one winning triple) then the whole procedure returns as true.

my my-win? procedure somewhat parallels the functionality of Anne’s (equal? (word me me me) in that the point is to check for three instances of the me letter.

My return-true-if-winner somewhat parallels the (not (empty? part of Anne’s procedure, although Anne returns the truth values directly using not rather than needing to use an if statement.

My i-have-won procedure parallels the part of Anne’s procedure starting at the keep. This seems like the part of my procedure that would be easiest to turn into something more elegant.

βœ…βŒ Exercise 10.2

The program also doesn’t notice when the game has ended in a tie, that is, when all nine squares are already filled. What happens now if you ask it to move in this situation?

❌ (forgot to answer this part of the question at first): You get an error.

Write a procedure tie-game? that returns #t in this case.

Here’s one solution (which makes use of the opponent procedure from ttt, although you could also just specify x and o)

It checks if the number of appearances of the computer’s letter and the opponent’s letter total to 9.

Here’s another solution (from buntine), which doesn’t make use of letter:

AnneB’s solution, which actually incorporates an already-won? check, is better:

Exercise 10.3

A real human playing tic-tac-toe would look at a board like this:

and notice that it’s a tie, rather than moving in square 9. Modify tie-game? from Exercise 10.2 to notice this situation and return #t.

Ok. A situation like the above always involves the following two things:

  1. There is exactly one space free
  2. The triples involving that space (in the above, 1-4-9, 3-6-9, and 7-8-9) have one x and one o respectively (so that neither side can actually win). If there was only one space free but one of the triples with that space had 2 appearances of the same letter, then that would mean we had a potentially winning move on our hands and not a tie.

So let’s think about this in terms of tie-game?. We want tie-game? to notice that there’s only one free space left. We also want it to notice that nobody can win by occupying that free space. So those are two separate requirements for tie-game?. The one free space one seems easiest, so we’ll start with that one:

One way to approach this problem is to create and compare filtered lists of triples. We can use one function, free-space-is-present?, to generate a list of all the triples in which the free space is present. We can use another function, triple-is-tie?, to generate a list of all the triples which fit the criteria for being a tie. If the board situation is truly one where a tie is inevitable, then the number of triples fitting both criteria should be identical. If one or another of the lists weren’t identical, that might indicate e.g. that there was a triple which included the free space and which did not fit the criteria for a tie (in other words, a potentially winning move).

We can say that a particular triple indicates a tie when all of the following conditions are met:

  1. We know there is only one free space left in the board
  2. A triple generated by find-triples has a number value and not just x’s or o’s (this indicates that that particular triple has the free space), and
  3. A triple generated by find-triples has no more than one appearance of the computer’s mark (if it had 2, that would indicate a potentially winning move that the computer could make. If there’s only one free space left, then the opponent’s number of marks in a triple with the free space doesn’t matter)

A triple meeting 2 and 3 while 1 is true means that the free space in the triple can no longer be used to win by either side.

Since I want to ensure that 1 is true, I restructure (equal? (appearances '_ position) 1)) within an if. If (equal? (appearances '_ position) 1)), then the other stuff will be analyzed (and possibly return true or false). Otherwise the procedure will return false.

I also want to still cover the case where all there are no free spaces.

So I nest my more complex analysis as the alternative within an if statement that first checks whether 0 spaces are free:

After doing the problems above, I refactored my program as follows and added testing for already-won?:

Here are some tests I ran:

For the first four tests, both versions produce the same result. For the final two tests, only the newer version produces the correct output. For the fifth test, I think that the new version of the procedure finds that the 1-5-9 triple has won and so (not (already-won? position letter)) correctly fails. For the sixth test, I think that the newer verison of the procedure correctly finds that the (not (already-won? position (opponent letter))) test fails due to x having won with triple 3-5-7.

(Can you improve the program’s ability to recognize ties even further? What about boards with two free squares?)

Let’s look at a scenario where there’s a tie. Assume the following board state, and o is going to move next:
‘xoxoox_x_ ‘o
xox
oox
_x_

o has no winning moves and can block x from winning by placing a square at 9. So this game has already deadlocked and should return true.

Here’s another case:
‘_oxxxoox_ ‘o

_ox
xxo
ox_

x can’t win if o moves in any of the remaining free spaces. o can’t win either.

One thing we haven’t done is figure out a way to update position based on a move, which I think would be essential for implementing this approach. So let’s try seeing if we can do that.

We want a procedure that can take a board position and player’s mark, figure out what move to make, and then update position.

So basically it would run ttt, take the value from that, and update the position based on the value. Whatever player’s mark was, it would replace that value in position.

Here’s my solution to this problem:

I am borrowing heavily from the structure of the sort-digits procedure here. My procedure has a lambda which checks if a digit from a list of 1 through 9 is equal to the square returned by calling ttt on the current board state and with the player’s mark (x or o). If so, the player’s mark is returned. If not, a character representing the current board state (x, o, or _ indicating empty) is returned. every does this for 9 digits, representing 9 squares of the board, and returns a sentence. This sentence is then accumulated into a word in order to be in the original form of position.

I realized when I was working on this problem that my previous iteration of tie-game had an issue. For the two cases of facing a tie game two moves out that I mentioned above, 'xoxoox_x_ 'o and '_oxxxoox_ 'o respectively, my current tie-game? procedure returns #t. I want it to return #t ultimately after I make certain adjustments to handle the two-spaces-out case, but it shouldn’t be returning #t yet. So let’s see if we can fix that before we add further layers of complexity.

I’ve added (and (equal? (appearances '_ position) 1) and that flips my two new test cases to false, as desired.

I’m also wondering if there is some way to simplify the program here along the lines I figured out already when trying to have the program handle two free spaces.

Oh. So if there is one free space, and the player can’t win, and the opponent has not already won, then that’s a tie. We’re already always checking for whether the opponent has already won, because we want to know whether either player has won regardless of whether there’s 4 free moves left or 0. So I think in the case where there is one free space left, we just need to check for whether the player will have already won after making the best move!

Ok, now we’ve got the 0 and 1 free space cases handled more elegantly!

Now to go to two spaces. Wait, first, I think since we’re handling more cases, we might want to go to a cond expression. Let me translate what I have into that first.

Let’s think about this. So if someone’s already won, that’s always going to be a not-tie situation, so that can go first, and we want to return false for tie-game? in that case.

Next, I think we want to test the two free spaces case. My intuition is that if the program can see that the game is a tie two spaces out, we don’t need to worry about testing the one free space case. The one free space case is like a subset of the two free spaces case. So we can just stop there and return false.

So one way to think of the two free spaces case is in terms of the following questions:
1. Can the player win?
2. Supposing that the player makes the best move regardless of whether they can win or not, can the opponent win?

So what you’d want to do to check for a tie-game two spaces out is to first see if the player can win, which is something we can already ask using our existing tools. Then look at the game from the opponent’s perspective but with the assumption that the player has made the best possible move in their next move, and then ask if the opponent can win. If the player can win, or the opponent can win, then the game is not tied, and this part of the procedure should return #f.

A thought occurs to me. Since we have something that can “look ahead” and judge ties with two free spaces, do we need to address 1 free space case specifically?

Another way of asking this question: are ties with one free space left a perfect subset of ties with two free spaces left?

I think one free space ties are not a perfect subset of two-space ties, and so we do need to test the 1 free space case separately. Why? Because one of the assumptions we make for the player’s move when testing whether there is a tie two free spaces out is that they make the best possible move. However, it is possible that the player fails to make the best possible move, and that that creates a tie-game situation due to the error of the player. So I think we want to test for that possibility.

I also realized a better way to test for this case. Just ask: is it true that the number of free spaces is equal to 1 and that player can win? If so, that’s not a tie-game, so return false. Since we’ve already asked if opponent has already won, we just need to know whether player 1 can win.

After glancing at buntine’s answer, I added a let statement to clean things up a bit:

I also noticed that neither buntine nor AnneB specified which player was making the next move for their versions of tie-game. I’m not quite sure if I made a mistake in doing so/if that was unnecessary to do on my part.

In the way I’ve currently structured the program, except for the check for whether either side has already won, the information about who the next player to move is going to be seemed necessary. But then I read Anne’s solution a bit and realized that if there’s two spaces left and only two possible moves in each space, that’s only two possibilities to check.

Here’s a modification dropping the use of me for the already-won? case:

Exercise 10.4

Here are some possible changes to the rules of tic-tac-toe:

What if you could win a game by having three squares forming an L shape in a corner, such as squares 1, 2, and 4?

Answer the following questions for each of these modifications separately:
What would happen if we tried to implement the change merely by changing the quoted sentence of potential winning combinations in find-triples?
Would the program successfully follow the rules as modified?

I ran some tests and it appears to. I made the following modification find-triples:

and ran the following tests:

(the comments in semi-colons represent a graphical depiction of the tic-tac-toe board state, since it’s easier for me to understand the board state that way).

I guess based on the program design this makes sense. find-triples is generated earlier on and then those triples are fed by ttt into the strategy procedure ttt-choose. So the triples list “flows down” into every portion of the program. So because the triples list is the reference point for whether a pair is winning, changing it can allow the program to adapt to different rules, at least if the rule change still involves a triple. The idea of trying to get a particular set of three values in order to win is hardcoded into the math of procedures like my-pair?. So this particular change works, but if you wanted to move to a system where you need like, an L shape to win (like 1-2-3-4, for example) then I don’t think the existing program would be able to handle that. You’d need to make more changes to handle that case.

Going into more detail: suppose you have something like the following board state:

Under the normal rules of tic-tac-toe, if you were o and making the next move here, you’d want to occupy square 8 in order to block x from winning and also to build a potential 2-5-8 triple. And indeed, the normal tic-tac-toe program returns 8 for this.

But with a “corners win” modification, you want to return 6 in order to win. And with the modification above, the procedure my-pair? will see that 2-3-6 is a potentially winning triple, and then return 6 according, which it does.

What if the diagonals didn’t win?

What would happen if we tried to implement the change merely by changing the quoted sentence of potential winning combinations in find-triples?
Would the program successfully follow the rules as modified?

I think this change would work based on the reasoning above.

The change would be reflected in the following code, which has removed the diagonal triples:

So for the following board state:

I would expect the unaltered ttt program to return a 9 (in order to win) and the modified program to return a 4 or an 7 (to try to build a 1-4-7 triple)

Both programs performed as expected.

What if you could win by having four squares in a corner, such as 1, 2, 4, and 5?

What would happen if we tried to implement the change merely by changing the quoted sentence of potential winning combinations in find-triples?
Would the program successfully follow the rules as modified?

I would expect this change to fail if implemented by editing find-triples, for the reason stated above. To recap, the idea of trying to get a particular set of three values in order to win is hardcoded into the math of procedures like my-pair?. So if you wanted to move to a system where you need like, an L shape to win (like 1-2-3-4, for example) then I don’t think the existing program would be able to handle that just by modifying find-triples. You’d need to make more substantial changes.

I changed the code as follows to test this:

Now consider the following board state:

I’d expect the standard ttt program to attempt to block the computer from winning at 9. I’d expect the modified procedure to do the same.

My prediction was correct.

Exercise 10.5

Modify ttt to play chess.

Sounds hard, especially since I don’t know anything about chess. I’m going to skip this one for now.

Trees

After reviewing her work on this chapter, I tried making some trees like AnneB did, to see the overall structure of the whole program.

Initially I thought the more detailed tree AnneB made looked overwhelming, but then I realized that I’d already some of the work in terms of describing what each part of the program did. Filling in the gaps and elaborating was a significant amount of additional work though.

Making the more detailed tree had a concrete benefit for me: I did not actually understand in detail the operation of opponent-can-win? or the various subprocedures within pivots or i-can-advance? previously. I had a sort of vague idea but making the tree gave me a more solid appreciation. I mention this as a reminder to myself of the value of making the tree, since I seem to still be somewhat skeptical and do such things in an inconsistent manner.

Things to Improve

Some of it is stuff I’ve mentioned before:

  1. Use trees more (like, I could have made a tree of the whole program).
  2. Do more thorough testing.
  3. Integrate past solutions into future steps (like Anne did with integrating already-won? into tie-game).
  4. (specific to this chapter) A failure to represent the tic-tac-toe board pictorially caused me some confusion about the board game state when coming up with tests. I fixed this as I went along.

Not sure if I’m overreaching or just failing to consistently apply best practices or something, but I found this chapter pretty difficult to work through. Possibly my standards are still not high enough in some way. I think part of the difficulty may have been that I’d worked through a lot of the material for the previous chapters in the past, but I might have skipped over most of this chapter previously, so it was kind of like totally new material. Since the next chapter looks to be stuff I’ve worked through before, I think I should go through it with some sort of checklist in order to use those (hopefully relatively easier problems) as an opportunity to work on developing some skills. Here are some things I’m thinking of having on my checklist:

  1. Make trees of procedures.
  2. Describe what each part of a procedure does in detail. Domain, range, big picture role, detailed steps.
  3. Figure out tests, including tests that try to go at least a bit beyond the scope of what the text says and make sense in terms of input someone might give an actual program (like – can the program handle erroneous input?)
  4. Ensure that I represent important information to myself in a way that’s easy for me to check for errors and issues (this came up with my initial failure in Chapter 10 to represent my tic-tac-toe test cases pictorially, which wasted some time)
  5. Integrate past solutions to problems into future steps in order to make procedures I write more robust/able to handle more cases (instead of treating each procedure as its own thing).
  6. Consider whether parameter names are reasonable.
  7. Consider whether there is redundant or unnecessary functionality. Consider especially whether if statements are needed.
  8. Carefully check each line of a program for parentheses issues when I’m done writing.
  9. Don’t rush to artificial deadlines. Focus on mastery not speed.

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:

Simply Scheme Chapter 8 – Higher Order Functions

A function that takes another function as one of its arguments is called a higher-order function. This chapter discusses several such functions.

Every

every is a function that lets us take a function as an argument and apply it to every word in a sentence or every letter in a word, regardless of the length of the sentence or word.

E.g. this gives you the first letter of every word in a sentence:

every is taking first as an argument, not invoking it.
every always returns a sentence.

Keep

keep takes a predicate and sentence as arguments and returns the words for which the predicate is true. If given a word instead of a sentence, it returns the letters (in word form) for which the predicate is true.

Accumulate

accumulate takes a procedure and sentence as arguments, applies that procedure to two elements of the sentence and gets a result. It then takes that result and applies the procedure to that result and the next element in the sentence, and keeps going until it’s combined everything together.

accumulate can also take a word as an argument instead of a sentence, treating the letters as elements.

Combining Higher Order Functions

You can combine higher order functions e.g.:

The keep number? takes the argument sent and returns a new sentence where number? is true for each element. Then that sentence gets passed to accumulate +. So the keep number? essentially acts as a filter for non-numbers, keeping them out of accumulate +‘s way and insuring that the sentence argument for accumulate + only has numbers to deal with.

Repeated

the repeated procedure returns a procedure that invokes the original procedure repeatedly. E.g.

(repeated bf 3) returns a procedure that does (bf (bf (bf))) on some input. If you don’t give it an input then Scheme just tells you that you have a procedure:

Shorter Notes

Scheme’s treatment of sentences as first-class data and functions as first-class lets us generalize ideas like “apply this function to every word of a sentence.

keep always returns a function of the same type as its second argument.

every always returns a sentence. If you want a word for every, you can accumulate word the sentence that every returns.

every expects a function of just one argument as its first argument. if you give it a function like quotient that expects two arguments, you’ll get an error message about not having enough arguments

Trying (every (quotient 6) '(1 2 3)) doesn’t help. Scheme tries to evaluate quotient 6 and throws an error.

This doesn’t work either: (every (+ 3) '(1 2 3))

(+ 3) returns 3. every wants a procedure as its first argument, and the number 3 isn’t a procedure:

accumulate can accept an empty sentence or word for +, *, word, and sentence.

Boring Exercises

What does Scheme return as the value of each of the following expressions? Figure it out for yourself before you try it on the computer.

βœ…βŒ Exercise 8.1

(every last '(algebra purple spaghetti tomato gnu))

I predicted: '(aeiou)
❌ Woops. It should be (a e i o u)

(keep number? '(one two three four))

I predicted ().
βœ…I was correct.

(accumulate * '(6 7 13 0 9 42 17))

I predicted 0.
βœ… I was correct.

(member? 'h (keep vowel? '(t h r o a t)))

I predicted false. keep vowel? returns a sentence of (o a) and ‘h is not a member of that sentence.

βœ… I was correct.

(every square (keep even? ‘(87 4 7 12 0 5)))

I predicted '(16 144 0).

βœ… I was correct.

(accumulate word (keep vowel? (every first ‘(and i love her))))

I predicted 'ai.
βœ… I was correct.

((repeated square 0) 25)

I was not sure about this one so I just tried it.

It just returns 25. I guess repeated gets called 0 times? So you just return the value of the number. It’s interesting though … if you call (repeated square 0) you do get a procedure back. I wonder what the procedure is exactly.

(every (repeated bl 2) ‘(good day sunshine))

I predicted '(go d sunshi).

βœ… I was correct.

βœ… Exercise 8.2

Fill in the blanks in the following Scheme interactions:

βœ… answer:


Forgot to include this one initially, didn’t see it until I saw Anne’s answer:


βœ… answer:


βœ… answer:


βœ… answer:


βœ… answer:


βœ… answer:

βœ…βŒ Exercise 8.3

Describe each of the following functions in English. Make sure to include a description of the domain and range of each function. Be as precise as possible; for example, “the argument must be a function of one numeric argument” is better than “the argument must be a function.”

❌ (wrong) f takes a word or sentence consisting entirely of numbers as an argument.

If provided a word as the second argument, it will return the subset of the word that consists of even numbers.

If provided a sentence as the second argument, it will return the subset of words in the sentence that consist of even numbers.

f‘s domain is words or sentences made entirely of numbers.

Its range is a word or sentence that consists entirely of even numbers.

βœ… (FIXED) The domain is non-negative integers (by themselves) or integers (including negative integers) in a sentence. Its range is non-negative even integers (by themselves) or even integers (including negative integers) in a sentence.


g takes a function that operates on one word. it applies that function to every element of the sentence (blue jay way) and returns a sentence with the result. e.g.:

❌ (WRONG) g‘s domain is functions that accept one word-arguments, and its range is a sentence that is some transformation of (blue jay way).

βœ… (CORRECTION) AnneB pointed out that you can actually get any output using g if you define a function that is always true and returns the sentence you want:

So the range is all sentences.


h takes a procedure c and calls it twice on an argument d.

For this procedure to work, the procedure used as the argument has to accept what it returns as input. So for example, even? would not work as a procedure because that returns booleans but does not accept them. butfirst, by contrast, both returns and accepts sentences, so that could work.

h can accept procedures that operate on numbers. for example:

So the domain for the procedure part (c) is a procedure that returns and can accept the same data type. There appear to be no restrictions on the domain in terms of the data part (d). I could not think of any restrictions on the range either.


i takes a number or sentence consisting of numbers and divides the total of the numbers by the number of numbers in the sentence (in other words, it finds the average)

❌ (WRONG)i‘s domain is a number or sentence consisting of numbers.
i‘s range is numbers.

βœ… (FIXED) The domain is limited to positive integers or 0, or sentences with any numbers (including complex numbers and weird stuff like that). No empty words/sentences though (you get a division by 0 error)


accumulate takes a procedure that combines two arguments as its first argument, and a word or sentence as its second arguments, and goes through and combines the elements in the second argument until it runs out.

accumulate returns a combined value depending on the procedure provided to it.

for word, it takes a sentence and returns a combined word.
for se,
for +, it takes as sentence of numbers and returns the sum of those numbers.
for -, it seems to work a differently than you might expect. Consider (accumulate - '(10 25 43 69 1 2)). You might expect this procedure to subtract 25 from 10, getting -15, and then subtract 43 from -15, getting -58, and so on until arriving at a value of -130.

but

Why -42?

I think how the functions work (paralleling an example from the text) is something like this:

for accumulating a word, the order does not matter:

but for accumulating subtraction the order matters a lot.

Accumulate has a complicated domain and I’m not sure how to describe it comprehensively. Depending on the procedure provided, accumulate’s domain can include a word or sentence or number. For +, *, word, and sentence, accumulate can accept empty arguments.

Its range includes numbers, words or sentences.

AnneB says:

accumulate takes two arguments, a procedure and a word or sentence. The domain of accumulate is all sets of a procedure and a word or sentence that fit at least one of the following:

  1. A procedure that can accept two letters (words of length one) or two words (whichever it is paired with) and returns something that it will accept as an argument, along with a word or sentence that is at least 2 in length.
  2. Any procedure, along with a word or sentence of length 1.
  3. The procedures +, *, word, or sentence, along with an empty word or an empty sentence.

I’m not sure 2 is correct. Certain procedures don’t take certain inputs (like even? doesn’t take words) and will give error if you try to use them.
1 and 3 seem correct. More AnneB:

accumulate calls the procedure with the first two elements of the given word or sentence, then calls it again with that result and the third element, and continues until it has used all the elements of the given word or sentence. If the given word or sentence has only one element, accumulate returns that word or sentence. If the given word or sentence is empty, accumulate returns the identity element of the given procedure.

I agree.


sqrt takes a number and returns the square root of that number.
sqrt‘s domain is numbers and its range is a real or imaginary number.

This may be wrong re: range. I think maybe I meant complex numbers and not imaginary numbers. Anne wrote a lot of stuff about it:

The domain of sqrt is at least all real numbers. The version of Scheme I’m using does accept negative numbers. For instance:

> (sqrt -1)
0+1i

I can’t figure out if there’s a way to input complex numbers like β€œ2+3i” into this version of Scheme.

If you enter them as number + i, it works:

Just 4i by itself won’t work though. It’s detecting only the specific number+i format, at least for me.

If there is, then the domain might include them too.

Ya it seems to include complex numbers.

I found this:

Mathematically, numbers may be arranged into a tower of subtypes in which each level is a subset of the level above it:
number
complex
real
rational
integer
For example, 3 is an integer. Therefore 3 is also a rational, a real, and a complex. The same is true of the Scheme numbers that model 3. For Scheme numbers, these types are defined by the predicates number?, complex?, real?, rational?, and integer?.

The sqrt procedure returns the principal square root of the number. This place explains what that is:

procedure: sqrt z
Returns the principal square root of z. The result will have either positive real part, or zero real part and non-negative imaginary part.

So if the domain of sqrt is the real numbers, then the range is the non-negative real numbers plus the complex numbers with a zero real part and non-negative imaginary part. If the domain of sqrt is the complex numbers, I’m not sure what the range is, but it might be all complex numbers with a positive real part or a zero real part and a non-negative imaginary part. If the domain of sqrt is all numbers, then I don’t know what the range is.

Seems fair to say sqrt‘s domain is complex numbers and range is complex numbers with a positive real part or a zero real part and a non-negative imaginary part.


repeated takes a procedure and a number and returns a procedure which consists of the procedure it was provided invoked a number of times equal to the number it was provided. e.g.:
((repeated bf 3)'(potato cheese ninja puff hat))
returns '(puff hat).

repeated‘s domain is a procedure and positive integer or 0, and its range includes many procedures. If the number provided to repeated is greater than 1, the procedure has to be able to take the value it returns as an input. For example, ((repeated even? 1) 2) works because even? is only getting invoked one time. OTOH, ((repeated even? 2) 2) does not work because the first invocation of even? returns a boolean, and even? returns but does not take booleans.

Forgot to discuss giving 0 as the second argument. If you use 0 as the number of times to invoke the procedure, then you just get the word or sentence returned back:

AnneB says:

repeated takes two arguments, a procedure and a number. The domain of repeated is all sets of procedures and whole numbers where the range of the procedure is a subset of the domain of the procedure (it doesn’t have to be a proper subset),

I think maybe “all sets of procedures and whole numbers where the range of the procedure is a subset of the domain of the procedure” is trying to get at a similar point as I was trying to get at with “If the number provided to repeated is greater than 1, the procedure has to be able to take the value it returns as an input.” The range has to be a subset of the domain so that the procedure can be called repeatedly in cases where you invoke the procedure > 1 times.

or the number is 0 or 1 and the procedure is any procedure. The range of repeated is the union of all the ranges of such procedures.

I think maybe I follow the part re: “union” but I’m not really sure. I think maybe it means that the range of repeated is the range of all the procedures previously described combined.


(repeated sqrt 3) takes a number and finds its square root 3 times. For example, (repeated sqrt 3) applied to 256 returns 2. (The square root of 256 is 16, the square root of 16 is 4, the square root of 4 is 2).

Seems like this would be the same as square root: domain is complex numbers and range is complex numbers with a positive real part or a zero real part and a non-negative imaginary part.


(repeated even? 2) returns a procedure which applies even? to a number, and then applies even? to the result of the first application of even?.

So in other words, it does something like:

(even? (even? 2))

If it was just even? once, then the domain would be a number and the range would be a boolean. With this function, however, things are different.

even? doesn’t accept booleans, which is all that even? can produce. You get an error message with this function regardless of the input.

So I think this function doesn’t have a domain or range. It’s like a broken procedure.


(repeated first 2) returns a procedure which takes takes first of some argument twice. So it does something like (first (first '(potato tomato))).

Invoking first twice on a sentence first returns the first word of that sentence and then returns the first letter of the first word.

Invoking first twice on a word returns the first letter of that word. It doesn’t matter how many times you invoke first on a word repeatedly – you keeping getting the first letter

So (repeated first 2) has the interesting property that it returns either the first letter of a word (or first character of a number) or the first letter of the first word of a sentence. For words and unnested sentences, it has the same output (a word consisting of a single letter).

If a sentence is nested one level, like '((potato tomato)), it will return the first word of the sentence (potato in my example).

If a sentence is nested two levels, like '(((potato tomato))), the function will return the entire sentence. If there are multiple nested sentences, it will return the first sentence.

There are invalid inputs to (repeated first 2). These include the empty sentence'() and empty word "".

❌ (wrong) The domain of (repeated first 2) is any non-empty word or sentence, and the range is either the first letter of a word or the first sentence within a nested sentence. Putting it more generally, we could say the range is the first element within a word or sentence (and keep in mind that with nesting the “first element” could be a whole nested sentence).

βœ… (fixed). The domain of (repeated first 2) is any non-empty word or sentence. The range may likewise be non-empty words or sentences but I’m not sure.


(repeated (repeated bf 3) 2) results in butfirst being invoked 6 times.

the (repeated bf 3) returns a procedure that invokes butfirst 3 times. then the left-most repeated returns a procedure which invokes the (repeated bf 3) procedure twice on some input, resulting in 6 invocations.

We can see this in the following examples.

I defined the following function:

butfirst 6 times on the input sentence returns the 7th value, grape.

butfirst 6 times on the input returns a word starting at the 7th letter.

inputs to the function need to at least contain 6 values (in that case returning an empty list or sentence). If they have 5 or fewer values, an error will result.

So the domain of the function is any word or sentence with greater than 5 elements. The range is a word or sentence.


Real Exercises

βœ… Exercise 8.4

Write a procedure choose-beatles that takes a predicate function as its argument and returns a sentence of just those Beatles (John, Paul, George, and Ringo) that satisfy the predicate. For example:

ANSWER:

βœ… Exercise 8.5

Write a procedure transform-beatles that takes a procedure as an argument, applies it to each of the Beatles, and returns the results in a sentence:

Answer:

βœ… Exercise 8.6

When you’re talking to someone over a noisy radio connection, you sometimes have to spell out a word in order to get the other person to understand it. But names of letters aren’t that easy to understand either, so there’s a standard code in which each letter is represented by a particular word that starts with the letter. For example, instead of “B” you say “bravo.”
Write a procedure words that takes a word as its argument and returns a sentence of the names of the letters in the word:**

(You may make up your own names for the letters or look up the standard ones if you want.)
Hint: Start by writing a helper procedure that figures out the name for a single letter.

Answer:

βœ… Exercise 8.7

Write a procedure letter-count that takes a sentence as its argument and returns the total number of letters in the sentence:

Answer:

βœ… Exercise 8.8

Write an exaggerate procedure which exaggerates sentences:

It should double all the numbers in the sentence, and it should replace “good” with “great,” “bad” with “terrible,” and anything else you can think of.

Answer:

βœ… Exercise 8.9

What procedure can you use as the first argument to every so that for any sentence used as the second argument, every returns that sentence?

sentence seems to work, though for nested sentences it doesn’t return the nesting.

AnneB noticed a couple of other things that work – word and a function that just returns the same input:

What procedure can you use as the first argument to keep so that for any sentence used as the second argument, keep returns that sentence?

word? seems to work for this, assuming no nesting. It works for the empty sentence too.

What procedure can you use as the first argument to accumulate so that for any sentence used as the second argument, accumulate returns that sentence?

sentence works, including for nesting.

βœ… Exercise 8.10

Write a predicate true-for-all? that takes two arguments, a predicate procedure and a sentence. It should return #t if the predicate argument returns true for every word in the sentence.

Answer:

βœ… Exercise 8.11

Write a GPA procedure. It should take a sentence of grades as its argument and return the corresponding grade point average:

Hint: write a helper procedure base-grade that takes a grade as argument and returns 0, 1, 2, 3, or 4, and another helper procedure grade-modifier that returns βˆ’.33, 0, or .33, depending on whether the grade has a minus, a plus, or neither.*

Answer:

Thought the slight implementation difference between my version and AnneB’s was interesting. AnneB added the modifiers up separately in the gpa part of the procedure while I added the modifier directly to the grade in base-grade using the grade-modifier helper procedure. I think maybe Anne’s organization is a bit more logical cuz it keeps the base grade and modifier separate until the final step.

βœ… Exercise 8.12

When you teach a class, people will get distracted if you say “um” too many times. Write a count-ums that counts the number of times “um” appears in a sentence:

answer:

βœ… Exercise 8.13

Write a procedure phone-unspell that takes a spelled version of a phone number, such as POPCORN, and returns the real phone number, in this case 7672676. You will need to write a helper procedure that uses an 8-way cond expression to translate a single letter into a digit.

βœ… Exercise 8.14

Write the procedure subword that takes three arguments: a word, a starting position number, and an ending position number. It should return the subword containing only the letters between the specified positions:

Answer:

Self-analysis

I should think more carefully about handling erroneous inputs with else clauses and that kind of thing.

For figuring out domain and range of a function, I should pay attention to integer versus decimal, negative numbers etc. Also try to break down the different parts of a procedure’s domain somewhat more systematically and formally (as best as I can anyways).