This is the archived website of SI 413 from the Fall 2013 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
This lab is due at 2359 on Thursday, 5 September. It should be submitted as "413 lab 02", with the files named properly according to the submit script. See the submit page for details. You are highly encouraged to submit whatever you have done by the end of this lab. Remember that duplicate submissions are fine; I will just grade the latest one when the time comes.
A major theme of this class is understanding careful specifications, and a consequence is that, for the programming parts at least, you should be able to know the quality of your solution before submitting it. To this end, you will be given the time and the credit for carefully testing your code. Remember that the purpose of testing is to find bugs in code. Therefore a good test is one that fails a piece of code. Don't feel bad about this; that's the point of testing! Easy tests might make you feel good, but are useless. Careful testing helps you find bugs before they cause problems.
Starting with this lab, you will write and submit (unit) tests with each of your labs. The full details of how these tests are submitted is outlined on the submit page, but here is a general overview.
You will write and submit at least one test for each of the exercises below.
Each test case must be in a separate file, and each one is in two parts:
First, there is a single Scheme expression
(possibly following some definitions) that will be evaluated in the
context of the file that's being tested. Then you have another
Scheme expression for the "expected" result. These are separated by
a single line that contains just a semicolon
For example, to test the
to-celcius function from
Lab 1, the following file would work:
(to-celcius 77) ; 25
Notice that the tests don't have to be long or complicated!
You write each of these tests into a different file, and put
all those files in the
tests subdirectory of your
Important tip: You need to be careful when testing
functions that return inexact numbers, that you account for round-off
errors in the calculation. The easiest way to do this is to use the
round function; for example, the public test for
the first exercise below looks like:
(round (* (to-usdollar 500 'yen) 100)) ; 509.0
An easy script is provided to test your solution against the tests you have written. If you have set up your environment properly, you can run the command
schemetest your_file.scm test1.scm test2.scm ...to test the Scheme program
your_file.scmagainst those test files. In fact, this is the same script I run to do the sanity tests and ultimately to grade your work!
There is also a collection of "public tests" (basically corresponding to the examples in the text of the lab) that I have written for you. There is another script provided to test your submission against all your tests as well as all the public tests. If you pass all these tests, you can feel reasonably confident that you have understood the basic intent of all the exercises and named your functions correctly. This "sanity check" against your tests and the public tests is also automatically run every time you submit.
After the deadline, I will test your code and I will test your tests! First, your tests are run against a correct sample solution, and against a very incorrect anti-solution. You will lose credit for any tests you write which my (correct) solution fails, or which my (incorrect) anti-solution passes. These bad tests are also discarded for the next round, in which your code is tested with everyone else's "good tests". Here, you will receive credit for other students' tests that you pass, as well as your tests that other students' code fails. So you will be rewarded for writing difficult tests, and for passing the difficult tests that everyone else writes!
My hope is that taking the time to do this testing makes you more confident in your own code, and encourages you to think carefully about what mistakes you might make before you make them. I would love to hear any feedback you have about the testing process in our labs.
Recall that a symbol is just a quoted identifier, such as
We can use the function
symbol? to find out whether
something is a symbol, and
eqv? to compare two
1 US dollar = 0.76 Euros (euro) 1 US dollar = 98.18 Japanese Yen (yen) 1 US Dollar = 1109.85 South Korean Won (won)
(to-usdollar amt cur)that takes an amount of money
amtin some foreign currency
curand returns that amount in US dollars. The parameter
curwill be one of the symbols
(to-usdollar 500 'yen)produces 500/98.18, which comes out to
(from-usdollar amt cur)that does the opposite: takes an amount in US Dollars and converts it to the named currency.
(convert amt fromCur toCur)that takes an amount in currency
fromCurand converts it to currency
toCur. Use your functions from parts 1 and 2 and life will be easy!
Recall "big 4" of list processing:
'(): the name for an empty list.
(cons a L): Take an item
aand a list
Land return the new list with
ainserted in the front of
(car L): Returns the first item in
(cdr L): Returns the list containing all the items in
Lafter the first item.
If you're faced with nested lists, you sometimes need cars of
cdrs, and cdrs of cars, and so forth. The shortcut for
a bunch of these in a row is
X is either
There are two more extremely useful shortcuts:
list: Takes an arbitrary number of items and makes a single list containing them.
append: Takes an arbitrary number of lists and makes a single list containing all their items.
Make sure you understand the difference between these two!
In class we looked at the general pattern for a recursive function
on a list. When that function is also producing a list, it extends
the pattern by (usually) returning
'() in the base case, and
(usually) returning a
cons in the general case. For example,
here is a simple recursive function that multiplies every number in a list
; alon must be a list of numbers. (define (mulby2 alon) (if (null? alon) '() (cons (* 2 (car alon)) (mulby2 (cdr alon)))))
See what's happening? Make sure you can identify the base case condition, the base case return value, and the recursive call. Notice what gets multiplied by 2, and where it happens. If it's confusing, now is the time to ask your able and handsome instructor!
squaresthat takes integers i and j and returns list of the squares i^2, (i+1)^2, ..., (j-1)^2, j^2.
> (squares 2 12) (4 9 16 25 36 49 64 81 100 121 144)
In class we saw that there is a built-in Scheme function
which returns the length of a list. Using this, we could write a function
longer? to test whether the first list is longer than the second:
; L1 and L2 must both be lists (define (longer? L1 L2) (> (length L1) (length L2)))
Now I want you to write your own version of
doesn't use length calculation as a subroutine. Instead, you will have to
recursively process both
at the same time until one of them is empty.
(I really mean it - no length, even if you write it yourself! I will test you code using an infinite list as one of the arguments. Yes, those exist in Scheme. Look up "immutable cyclic data" in the manual if you're really really curious.)
sum-cashthat returns the value in US dollars of a collection of amounts of different currencies (same currencies as above). The amounts will be given in a list L, such that each element of L is itself a list, whose first element is an amount and whose second element is a currency name. So, for example,
'((12.20 usd) (340 yen) (850 won))as an argument to
sum-cashwould mean adding 12.20 dollars, 340 yen and 850 won, and giving the total in dollars. Here's an example:
> (sum-cash '((12.20 usd) (340 yen) (850 won))) 16.4289...
std-devthat takes a list of numbers and returns their standard deviation. (Recall: std dev of x1, x2, ..., xn is
__________________________________________ / /(x1 - u)^2 + (x2 - u)^2 + ... + (xn - u)^2 / ------------------------------------------ \/ n - 1... where u is the average of x1, x2, ..., xn. When you write this function, use top-down design. In scheme this means writing the
std-devfunction using functions you wish were already defined, then going back and defining them later. It can be useful to quote these function calls before you implement them, so you can even do top-down testing!
> (std-dev '(34 18 25 23 29 11 28 24 27 29)) 6.460134157533676
uniquefythat takes a list of numbers, and returns a list with all the distinct numbers in the original, i.e., with all the duplicate numbers removed. For example:
> (uniquefy '(1 2 4 1 2 2 3 15)) (1 2 4 3 15)At the very least, you will probably want to also define at least one nice helper function. Try thinking about the efficiency of your function. Could you make it faster?
let construct in Scheme allows you to give a
name to a common subexpression. For example, consider the
33 * (501 - 33) --------------------- 1 - (33 * (501 - 33))
The natural way to code this in Scheme is probably
(/ (- (* 33 501) 33) (- 1 (- (* 33 501) 33)))
But you could say "let a = 33 * (501 - 33), and return a / (1 - a)".
let allows you to do:
(let ((a (- (* 32 501) 33))) (/ a (- 1 a)))
let is the Scheme way of getting local
variable functionality. What you've got is the
let keyword, followed by a list of
variable-name/value pairs, followed by an expression
(presumably using the new names) that provides the value of
let expression. For example, the following code
12 as a result:
(let ((a 2) (b 4) (c 6)) (+ a b c))
There is power in using
let in functions. Suppose I want to define a function called
shifted-cube, which computes (x + 1)^3 for a
(define (shifted-cube x) (let ((a (+ x 1))) (* a a a)))
(shifted-cube 2) produces the value
test-sinthat computes 1/((sin x)^2 + 1) + sqrt((sin x)^2 + 1) - ((sin x)^2 + 1)^2
distthat computes the difference (in inches) between two lengths (given in feet and inches). Example:
> (dist 3 7 2 11) ;;; difference between 3'7'' and 2'11'' 8Write this function using a
letexpression to create values
L2for the lengths in inches of the input feet-and-inches lengths.
As you have perhaps noticed, you never actually tell scheme
what the type of a function parameter is. Thus, if I
define some function
(f x y), there's nothing to stop me from
calling it like this:
(f sqrt 4). In other words, there's
nothing to stop me from passing f a function as one of its
arguments. This is something very special about functional programming
languages: functions can be used like any other kind of data.
Take a moment to allow this to sink in.
Now check out this example.
f uses its first argument,
x, as a function. So
x should be a function!
> (define (f x y) (* y (x y))) > (f sqrt 4) 8
What happened here? Well since
the evaluation produces
(* 4 (sqrt 4)) which is 8. So f is the
function x to argument y and then multiply by y" function.
to functions like this is very powerful. This is part of what
we mean when we say that "functions are first class objects"
in a functional language.
(fd-at g n)that takes a function
gand a value
nand returns the finite difference of g at n. For example:
> (define (f x) (* x x)) > (fd-at f 3) 7
is a really useful function that takes functions as arguments.
(map f L) applies the function
to each element of the list
and puts the results together in a new list. For example:
> (map abs '(-4 12 -3 -8 11 0)) (4 12 3 8 11 0)
If you have a function with k arguments, then you give
lists, and it will take the first argument from list1, the
second from list2, etc.
> (map * '(2 3 4) '(6 5 4)) (12 15 16)
Another useful function of this type is
(apply f L)
calls the function
f with arguments the elements of
are some examples:
> (apply max '(4 6 2)) ; same as (max 4 6 2) 6 > (apply - '(3 7)) ; same as (- 3 7) -4
apply can be very interesting.
> (define (sqr x) (* x x)) > (map sqr '(1 2 3 4 5 6 7 8 9 10)) (1 4 9 16 25 36 49 64 81 100) > (apply + (map sqr '(1 2 3 4 5 6 7 8 9 10))) 385
Yet another useful function-that-takes-a-function is
(filter f? L) applies the predicate function
f? to each element in the list
L, and returns the
list containing only the elements for which the predicate returns true.
> (filter number? '(a b 2 #t + 4)) (2 4)
filter function is not built-in to
the version of Scheme that we are using. So you will have to copy and
paste the function into your code:
(define (filter pred? L) (cond ((null? L) '()) ((pred? (car L)) (cons (car L) (filter pred? (cdr L)))) (else (filter pred? (cdr L)))))
For these, you will probably want to use this helper function. Just copy its definition into your code.
; Returns a list containing integers a, a+1, ..., b. (define (range a b) (if (> a b) '() (cons a (range (+ a 1) b))))
sqrt-prodthat takes a number
nand computes the product of the square roots of the integers from 1 up to n. For example:
> (sqrt-prod 10) 1904.94...
special-numsthat takes an integer
nand computes a list of all integers between 1 and n that are both divisible by 3 and are perfect squares. For example:
> (special-nums 100) (9 36 81)Hint: you should make some helper functions that are predicates.
(define P1 '((3 5) (9 2) (11 6) (8 8) (4 6)))P1 represents a polygon whose vertex coordinates are given by the pairs in P1. Write a function
(translate p d)that takes a polygon (in the sense of P1, i.e., a list of coordinate pairs) and an offset d (represented by a pair, the x offset and the y offset) and translates the given polygon by the given offset.
> (define P1 '((3 5) (9 2) (11 6) (8 8) (4 6))) > (translate P1 '(1 2)) ((4 7) (10 4) (12 8) (9 10) (5 8)) >Depending on your approach, the following function might be useful to you:
;Creates a list of k copies of x (define (repeat x k) (if (= k 0) '() (cons x (repeat x (- k 1)))))For full credit, your function should also work in higher dimensions. By this I mean, if each point has x, y, and z coordinates, for example, everything should still work, by providing a list of 3 offsets to the