Lab 1:

Functional Programming

“In order to understand recursion, one must first understand recursion.”

In this lab we will dive into functional programming and recursion. In short, recursion is idea of having a procedure solve some big problem by making it a little bit smaller somehow and then calling itself. When it calls itself, it makes the problem smaller yet again. This continues until the problem is small enough to be trivially solved. Recursion can be hard to get used to if you have never used it before. Some things to remember when programming recursively are:

  1. Remember to have a base case. Your recursion should reach a point where it no longer needs to call itself to get an answer. At some point the problem should be trivial enough to just output an answer.
  2. Always make your problem smaller. Whenever you make a recursive call make sure your arguments are smaller than what they were to begin with. If they aren't then you can get yourself into some nasty infinite loops.
  3. Lastly trust the recursion! Don't overthink the problem. If your recursion makes sense and you've followed hints 1 and 2 you probably have working code. You don't always need to trace through the recursion to make sure your procedure works as you expect it to.

If this seems weird to you, take a look at the previous lab, Recursion and Scheme


finish this during section

Exercise 1.


Modify the following procedure so that it correctly handles cases like (plural 'boy). It may help to define vowel?.

Exercise 2.

Max Sum of Squares

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers

Exercise 3.

Duplicates Removed

Write a procedure dupls-removed that, given a sentence as input, returns the result of removing duplicate words from the sentence.

Exercise 4.

Pig Latin

Write a procedure pigl that takes a word as an argument and returns that word in pig latin. Here are the rules for pig latin:

  1. If the input word starts with a vowel then we append "ay" to the input.
  2. If the input word starts with a consonant then we move all the starting consonants to the end of the word and then append "ay" to the end.

Here are some examples:

(pigl 'hello) ; ellohay
(pigl 'open) ; openay
(pigl 'scheme) ; emeschay

Exercise 5.


Write a procedure count-word that takes a sentence and a word as arguments and outputs the number of occurences of the input word in the sentence.


do this in section if possible; finish the rest at home

People who know Scheme: Don't use the CS 3 higher-order procedures such as every in these problems; use recursion.

Exercise 6.

The Return of new-if

Explain what would happen if you used new-if (from Lab 0) instead of if in the pigl procedure.

Exercise 7.


Write a procedure squares that takes a sentence of numbers as its argument and returns a sentence of the squares of the numbers.

Exercise 8.


Write a procedure switch that takes a sentence as its argument and returns a sentence in which every instance of the words I or me is replaced by you, while every instance of you is replaced by me except at the beginning of the sentence, where it's replaced by I. (Don't worry about capitalization of letters.)

Exercise 9.


Write a predicate ordered? that takes a sentence of numbers as its argument and returns a true value if the numbers are in ascending order, or a false value otherwise.

Exercise 10.


Write a procedure ends-e that takes a sentence as its argument and returns a sentence containing only those words of the argument whose last letter is E.

Exercise 11.

Most versions of Lisp provide and and or procedures like the ones we've seen.In principle there is no reason why these can't be ordinary procedures, but some versions of Lisp make them special forms. Suppose, for example, we evaluate (or (= x 0) (= y 0) (= z 0)) If or is an ordinary procedure, all three argument expressions will be evaluated before or is invoked. But if the variable x has the value 0, we know that the entire expression has to be true regardless of the values of y and z. A Lisp interpreter in which or is a special form can evaluate the arguments one by one until either a true one is found or it runs out of arguments.

Your mission is to devise a test that will tell you whether Scheme's and and or are special forms or ordinary functions. This is a somewhat tricky problem, but it'll get you thinking about the evaluation process more deeply than you otherwise might. Why might it be advantageous for an interpreter to treat or as a special form and evaluate its arguments one at a time? Can you think of reasons why it might be advantageous to treat or as an ordinary function?

Exercise 12.

Do the following reading: