Simply Scheme

Table of Contents

A place for me to record my thoughts, workings, and solutions while going through the Simply Scheme book.

Introduction: Functions

Showing Scheme

The first thing I had to do was get setup with the necessary dependecy files. On my system I am putting them in the directory progs-from-book, which you will see me load in the below code snippets.

Talking to scheme

I will be talking to scheme through code snippets within these emacs files. Let’s see how this looks:

(load "progs-from-book/simply.scm")
(word 'comp 'uter)
computer

Working through the examples

  • Example: Acronyms

    Our first program will simply take in a phrase and return the Acronym for that phrase, consisting of the first letter of each word.

    (load "progs-from-book/simply.scm")
    (define (acronym phrase)
      (accumulate word (every first phrase)))
    
    (acronym '(american civil liberties union))
    
    aclu
    

    Now let’s go through what each of those functions do, in order to better understand what’s going on. The first command is one that is loaded in by the file provided by the book. As we can see, it returns the first character of the passed in string.

    (load "progs-from-book/simply.scm")
    (first 'american)
    
    a
    

    Now we can use the every function in order to run the first function against each of the passed in strings. This gives us a list of results.

    (load "progs-from-book/simply.scm")
    (every first '(american civil liberties union))
    
    a c l u

    And finally we can use the accumulate function to turn that list back into a string.

    (load "progs-from-book/simply.scm")
    (accumulate word '(a c l u))
    
    aclu
    

    In the real world, we would expect that certain words would be excluded from acronyms. Let’s give it a shot:

    (load "progs-from-book/simply.scm")
    
    (define (acronym phrase)
      (accumulate word (every first phrase)))
    
    (acronym '(united states of america))
    
    usoa
    

    Uh oh. Looks like we’re not excluding common filler words. Let’s fix that.

    (load "progs-from-book/simply.scm")
    
    (define (acronym phrase)
      (accumulate word (every first (keep real-word? phrase))))
    
    (define (real-word? wd)
      (not (member? wd '(a the an in of and for to with))))
    
    (acronym '(united states of america))
    
    usa
    

    See? There we go. What we did there is define a function called real-world? that takes in a string, matches it against a list of strings, and returns true (#T) or false (#F) depending on whether the passed in string exists in the list. By passing this in to the keep function we are able to exclude certain filler words.

  • Example: Pig Latin

    The next example that is given in chapter one is to make a pig latin function. Basically, take a word. If the first letter is a vowel, just add “ay” to the end. If the first letter is not a vowel, then move letters to the end until you reacha vowel, then add “ay”.

    It’s defined as follows:

    (load "progs-from-book/simply.scm")
    
    (define (pigl wd)
      (if (member? (first wd) 'aeiou)
          (word wd 'ay)
          (pigl (word (butfirst wd) (first wd)))))
    
    (pigl 'spaghetti)
    
    aghettispay
    

    A fuller example can be seen here:

    (load "progs-from-book/simply.scm")
    
    (define (pigl wd)
      (if (member? (first wd) 'aeiou)
          (word wd 'ay)
          (pigl (word (butfirst wd) (first wd)))))
    
    (every pigl '(the ballad of john and yoko))
    
    ethay alladbay ofay ohnjay anday okoyay
  • Example: Ice Cream Choices

    Let’s see… They give a scheme program without really telling what it does. Let’s see if I can figure it out before running it…

    My guess: Well, it seems to take in three arrays. Then it takes every item in every array and combines them. So if my arrays were as follows: [small, large]., [red, blue], [dog, cat] then I would get the following:

    • small red dog
    • small red cat
    • small blue dog
    • small blue cat
    • large red dog
    • large red cat
    • large blue dog
    • large blue cat

    Let’s run it with this example and see:

    (load "progs-from-book/simply.scm")
    
    (define (choices menu)
      (if (null? menu)
          '(())
          (let ((smaller (choices (cdr menu))))
            (reduce append
                (map (lambda (item) (prepend-every item smaller))
                     (car menu))))))
    
    (define (prepend-every item lst)
      (map (lambda (choice) (se item choice)) lst))
    
    (choices '((small large)
               (red blue)
               (dog cat)))
    
    small red dog
    small red cat
    small blue dog
    small blue cat
    large red dog
    large red cat
    large blue dog
    large blue cat

    I feel like there has to be an easier way to do that. But I could be wrong. Maybe I’ll revisit this later on.

  • Example: Combinations from a set

    Including this just for posterity

    (load "progs-from-book/simply.scm")
    
    (define (prepend-every item lst)
      (map (lambda (choice) (se item choice)) lst))
    
    (define (combinations size set)
      (cond ((= size 0) '(()))
            ((empty? set) '())
            (else (append (prepend-every (first set)
                                         (combinations (- size 1)
                                                       (butfirst set)))
                          (combinations size (butfirst set))))))
    
    (combinations 3 '(a b c d e))
    
    a b c
    a b d
    a b e
    a c d
    a c e
    a d e
    b c d
    b c e
    b d e
    c d e
  • Examples: factorial
    (load "progs-from-book/simply.scm")
    
    (define (factorial n)
      (if (= n 0)
          1
          (* n (factorial (- n 1)))))
    
    (factorial 1000)
    
    402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    

Functions

Nothing to really note, just introducing functional programming.

Composition of Functions

Let’s learn about how to compose functions together.

Expressions

Scheme treats everything that is typed into it as an expression. The expression can be a single value, like 26 or something more complicated in parenthesis, such as (+ 14 7). The first kind of an expression is called an atom (or atomic expression), while the second kind is called a compound expression because it’s made out of the smaller expressions +, 14, 7. The metaphor is from chemistry, where atoms of single element can be combined with other to form chemical compounds. We can call the expressions within the compund expression its subexpressions.

These compound expressions are how we tell Scheme to “do” a thing. The idea is so important that we have made many names for this, like “calling” a procedure, “invoking” a procedure, “applying” a procedure, etc. These all mean the same thing.

This is different from most other languages, which have different kinds of expressions like a “print statement” or an “assignment statement”. In Scheme, everything is done by calling procedures, which means that everything we want to do is a compound expression.

Now, because a compund expression contains expressions, it can be hard to understand expressions without understanding expressions. The way we break the cycle is by continuing down the stack of expressions until we hit the atomic expressions.

An example is addition. Once you understand that numbers are themselves without referencing something else, it becomes very easy to see how addition works, and doesn’t need another function. Then, you can add in more calls using the addition operator, and it still makes sense. For example, once you understand what this means:

(+ 1 2)
3

Then it becomes trivial to understand this:

(+ (+ 1 2) (+ 3 4))
10

Little people

A basic description of how functions and instructions work inside a computer using people as functions.

Pitfalls

People can run into the following problems:

  • Thinking that expressions are evaluated left to right
  • Thinging that scheme cares about whitespace
  • Not matching up parenthesis

Boring Exercises

  • Exercise 3.1

    Translate the arithmetic expressions (3+4)×5 and 3+(4×5) into Scheme expressions, and into plumbing diagrams.

    (+ 3 (* 4 5))
    
    23
    
    (* 5 (+ 3 4))
    
    35
    
  • Exercise 3.2
    • 3
    • 4
    • 10
  • Exercise 3.3
  • Exercise 3.4
    • Tom (-) takes in 4 & 7 and hands -3 to Bob
    • Deb (-) takes in 3 & 5 and hands -2 to Dave
    • Bob (*) takes in 3 & -3 and hands -9 to Jill
    • Dave (-) takes in 8 & -2 and hands 10 to Jill
    • Jill (+) takes in 10 & -9 and returns 1
  • Exercuse 3.5

    Evaluate each of the following expressions using the result replacement technique:

    (sqrt (+ 6 (* 5 2))) = (sqrt (+ 6 10)) = (sqrt 16) = 4

    (+ (+ (+ 1 2) 3) 4) = (+ (+ 3 3) 4) = (+ 6 4) = 10

  • Exercise 3.6

    Not drawing a diagram.

  • Exercise 3.7

    What value is returned by (/ 1 3) in your version of Scheme? (Some Schemes return a decimal fraction like 0.33333, while others have exact fractional values like 1/3 built in.)

    (/ 1 3)
    
    1/3
    

    Looks like I have actual fractional values, which is good. MIT Scheme for the win.

  • Exercise 3.8

    Not doing

  • Exercise 3.9

    The expression (+ 8 2) has the value 10. It is a compound expression made up of three atoms. For this problem, write five other Scheme expressions whose values are also the number ten:

    • An atom
      • (10)
    • Another compound expression made up of three atoms
      • (- 13 3)
    • A compound expression made up of four atoms
      • (+ 5 3 2)
    • A compound expression made up of an atom and two compound subexpressions
      • (+ (+ 1 2) (+ 3 4))
    • Any other kind of expression
      • (+ 10)

Defining Your Own Procedures

Every scheme program consists of one or more procedures. We can define our own procedures like this:

(define (square x)
  (* x x))
#<unspecified>

This is the definition of a procedure called square. Square takes one argument, a number, and it returns the square of that number. Once you have defined square, you can use it just the same way as you use primitive procedures:

(define (square x)
  (* x x))

(square 7)
49

The procedure definition has four parts:

  • The word define means that we are about to define something
  • Then the name that we want to give the procedure
  • Then the names for it’s arguments
  • Finally the body which is the actual expression of the procedure

Special Forms

The word define used up above is a special form, or an exception to the evaluation rule mentioned previously. None of the subexpressions passed into define are evaluated. In fact, the way that special forms are built into scheme, there isn’t even a define procedure to understand.

But that matters not. The rest of the book will refer to invoking define, what’s returned by define, etc. We just need to know that it is a special form, or what most languages would call a keyword.

Functions and Procedures

Throughout the book, reference is made to functions. For our purpose, a function is a mapping from some input arguments to an output value. A process is the specific implementation of that value. For example, let’s take two procedures like so:

  • f(x) = 3x+12
  • g(x) = 3(x+4)

These are clearly two different procudures with different implementations. But, calling f(8) and g(8) both equal 36. So you could say that f(8) and g(8) are equivalent functions because they both take in 8 and return 36. The function is just the association between the starting value(s) and the resulting value, no matter how that result is computed.

We’ll say “the procedure f” when we want to discuss the operations we’re telling Scheme to carry out. We’ll say “the function represented by f” when our attention is focused on the value returned, rather than on the mechanism. (But we’ll often abbreviate that lengthy second phrase with “the function f” unless the context is especially confusing.)

Argument Names versus Argument Values

The name for the name of an argument is a formal parameter. In our square example, x is the formal parameter. The technical term for the actual value of the argument is the actual argument.

Procedure as Generalization

When faced with multiple versions of the same problem, it makes sense to generalize them by defining a procedure. The sqaure procedure is the perfect example of that. By generalizing the process, we can then focus on thinking about the problem itself, rather than the implementation of the solution.

This naming process is more important than it sounds, because once we have a name for some idea, we can use that idea without thinking about its pieces.

Composability

Any procedure that we define is essentially the same as the ones that are defined by default in Scheme, such as +. This means that we can compose together any set of procedures, because the result of any procedure can be passed into any other procedure as an argument.

The Substitution Model

Brief description that boils down to stating that scheme copies the body of a procedure when it is called. So when we call (square 5), scheme actually creates a copy of the body of the procedure (* x x) which would be (* 5 5), then computes the body, then returns the result.

Pitfalls

  • Don’t forget that a function can have only one return value
  • A very common pitfall in Scheme comes from choosing the name of a procedure as a parameter

Exercises

Skipping the boring ones

  • Each of the following procedure definitions has an error of some kind. Say what’s wrong and why, and fix it:
    ; These are the wrong ones
    (define (sphere-volume r)
      (* (/ 4 3) 3.141592654)
      (* r r r))
    
    (define (next x)
      (x + 1))
    
    (define (square)
      (* x x))
    
    (define (triangle-area triangle)
      (* 0.5 base height))
    
    (define (sum-of-squares (square x) (square y))
      (+ (square x) (square y)))
    
    ; These are the right ones
    (define (sphere-volume r)
      (* (/ 4 3) 3.141592654 (* r r r)))
    
    (define (next x)
      (+ x 1))
    
    (define (square x)
      (* x x))
    
    (define (triangle-area base height)
      (* 0.5 base height))
    
    (define (sum-of-squares x y)
      (+ (square x) (square y)))
    
    #<unspecified>
    
  • Write a procedure to convert a temperature from Fahrenheit to Celsius, and another to convert in the other direction.

    The two formulas are F=9⁄5C+32 and C=5⁄9(F-32).

    (define (fahrenheit-to-celsius f)
      (/ 5 (* 9 (- f 32))))
    
    (define (celsius-to-fahrenheit c)
      (/ 5 (+ (* 5 c) 32)))
    
    #<unspecified>
    
  • Define a procedure fourth that computes the fourth power of its argument.

    Do this two ways, first using the multiplication function, and then using square and not (directly) using multiplication.

    (define (fourth x)
      (* x x x x))
    
    (fourth 2)
    
    16
    
    (define (square x)
      (* x x))
    
    (define (fourth x)
      (square (square x)))
    
    (fourth 2)
    
    16
    
  • Write a procedure that computes the absolute value of its argument by finding the square root of the square of the argument.
    (define (square x)
      (* x x))
    
    (define (absolute-value x)
      (sqrt (square x)))
    
    (absolute-value -5)
    
    5
    
  • Write a procedure scientific that takes two arguments, a number and an exponent of 10, and returns the corresponding value

    “Scientific notation” is a way to represent very small or very large numbers by combining a medium-sized number with a power of 10. For example, 5×107 represents the number 50000000, while 3.26×10-9 represents 0.00000000326 in scientific notation.

    > (scientific 7 3) 7000

    > (scientific 42 -5) 0.00042

    (define (scientific a b)
      (* a (expt 10 b)))
    
    (scientific 7 3)
    
    7000
    
    (define (scientific a b)
      (* a (expt 10 b)))
    
    (scientific 42 -5)
    
    21/50000
    

    Some versions of Scheme represent fractions in a/b form, and some use scientific notation, so you might see 21/50000 or 4.2E-4 as the result of the last example instead of 0.00042, but these are the same value.

    (A harder problem for hotshots: Can you write procedures that go in the other direction? So you’d have

    > (sci-coefficient 7000) 7

    > (sci-exponent 7000) 3 You might find the primitive procedures log and floor helpful.)

    ;; not sure on this one
    (define (sci-coefficient x)
      (/ x 10))
    
     (sci-coefficient 7000)
    
    700
    
    (define logB
             (lambda (x B)
               (/ (log x) (log B))))
    
    (define (sci-exponent x)
      (floor (logB x 10)))
    
     (sci-exponent 7000)
    
    3.0
    
  • Define a procedure discount that takes two arguments: an item’s initial price and a percentage discount. It should return the new price:
    (define (discount price discount)
      (- price (* price (/ discount 100))))
    
    (discount 29.90 50)
    
    14.95
    
  • Write a procedure to compute the tip you should leave at a restaurant.

    It should take the total bill as its argument and return the amount of the tip. It should tip by 15%, but it should know to round up so that the total amount of money you leave (tip plus original bill) is a whole number of dollars. (Use the ceiling procedure to round up.)

    (define (discount a b)
      (- a (* a (/ b 100))))
    
    (define (tip x)
       (discount x 85))
    
    (tip 7.54)
    
    1.1310000000000002
    

Author: Doug Skinner

Email: me@doug-skinner.com

Created: 2022-01-11 Tue 08:52