Lab 1: Scheme expressions and functions
This lab is due at 2359 on Wednesday, 30 August. It should be submitted to the course SI413 as Lab01, with the files named properly according to the lab instructions. See the submit page for details. You are highly encouraged to submit whatever you have done by the end of this lab time. Remember that you must thoroughly test your code; the tests that are visible before the deadline are only there to make sure you are using the right names and input/output formats.
1 Starter Code
2 Initial setup
2.1 Gitlab
Start by following the initial GitLab setup instructions if you haven't already. Note, you need to run the setup script once on a lab machine, and then again on your laptop or any other place you want to get work done.
Next, you will make a new repo for the next few weeks' labs, on Scheme programming, by running:
roche@ubuntu$
413repo scheme
One lab partner should run this command first, which will create the initiial repository and add your lab partner as a "maintainer". Then the second lab partner can run the same command (or you can run it again yourself on a different computer), and it should connect up with the existing repository so you can collaborate.
Once this is complete, you should have a directory called scheme
with
a file inside called lab01.scm
. That will be your starting point for this lab.
2.2 DrRacket
We will be doing our Scheme programming using the DrRacket IDE. Check the instructions here for installation.
Basically, you should run this command before you get started (even on the lab machine where DrRacket is already installed):
curl k L 'https://faculty.cs.usna.edu/~roche/413/getracket.sh'  bash
You should now be able to run DrRacket from the applications menu, or by
running the command drracket
from a terminal or the run window (AltF2).
When DrRacket opens, check that the setup worked by seeing that it says "Swindle" in the bottomleft of the window. Now close DrRacket (we will reopen with the correct filename next).
2.3 Starting on the lab
Do this now:
 Open a terminal and go to your repo folder, probably
~/si413/scheme/lab01
. 
There should be a file
lab01.scm
already started for you.  Open that file in DrRacket by running the command
roche@ubuntu$
drracket lab01.scm &

Start by editing your file so it looks like this (using your own name of course):
The semicolon is used to start a comment line in Scheme, like;;; SI 413 Lab 1 ;;; MIDN Your Name and MIDN Your Lab Partner's Name (define myfirstvar 22)
//
in C++ or Java. You should of course get in the habit of putting your name in comments of any piece of code you work on!
The next line, as you can probably guess, is Scheme code to create a variable calledmyfirstvar
and give it the value of22
 Run your code by hitting CtrlR (or click the Run button).
 The top part of the IDE is called the definitions window. This is the code that will be saved and eventually submitted.
 The bottom half of the DrRacket window is called the interactions window. Here you can call the functions and things that you have defined in the definitions window above. But the interactions window is not saved! Every time you click "Run", it will get cleared out.
Tip: In the interactions window, use <Esc>P to go back up to the previous command. And be careful about hitting <Enter> in the middle of a line; use <Ctrl><Enter> to run the current command if the cursor is in the middle of the line.
2.4 Scheme lab formatting
Our labs will usually consist of a series of numbered exercises. You should (at least) indicate in comments (starting with a semicolon) where each exercise begins in your code.
Most of the exercises ask you to define a constant or a function. Since your code will be autotested, be sure to use the exact names that are specified in the lab. Spelling counts!
Like most programming languages, Scheme code is entirely unreadable without proper formatting and indentation. In DrRacket, this is really easy! You can reindent the entire file with the shortcut CtrlI. There is no excuse to turn in Scheme code that's not properly formatted.
In any case, in this class your code will be judged for readability as well as correctness. This is a programming languages class, so the language itself really does matter besides the outcome. For Scheme, try to pick up on conventions you see in the notes and on slides, keeping most of the lines short so that it's easy for a human to visually see how your code works. When in doubt, don't hesitate to ask!
3 Basic Expressions
An expression in Scheme is either an atomic object (a number,
a symbol, a string) or it is a list of expressions inside
parentheses  elements of which are separated by white space.
When a list is evaluated by the interpreter, the first element
is treated as a function, and the other elements are treated
as arguments to the function. So, instead of
sqrt(2.4)
, in Scheme we say (sqrt
2.4)
. Of course, expressions can be nested
(composition of functions), so sqrt(3.4*2.9)
is expressed in Scheme as (sqrt (* 3.4 2.9))
.
3.1 Booleans and Predicates
Scheme has builtin constants #t
and
#f
for true and false, respectively. The operations
and
, or
, and not
define
standard boolean logic as we would expect, so for instance
the expression (or (and #t #f) (not #f))
evaluates to
#t
.
Caution: in Scheme, anything that is not
#f
is considered to be true. This is actually pretty
convenient because it allows functions to return some extra information
 we know why some expression is true and not just that it
was true. So for example,
(or (not 6) 3)
returns 3
, which really
means "true" since 3 is not #f
. Get it?
Scheme also has many builtin functions that return a boolean value.
These are called predicates and by convention their names end
with a question mark. They are often used to determine the types of
objects, since Scheme variables have no declared types. For instance,
the predicate boolean?
determines whether its argument
is a boolean value (true or false), and if so returns #t
.
So (boolean? #f)
returns true, and
(boolean? 20)
returns false.
3.2 Numeric Types
Section 6.2 of the R5 Scheme language definition
describes numbers in
Scheme. Here are some high points.
There are two types of numbers in Scheme: exact and inexact.
The predicates
exact?
and inexact?
can be used to make the
distinction.
Inexact
numbers are essentially doubles, and include +inf.0
and inf.0
.
When you write a number with a decimal point,
it is automatically treated as inexact.
Exact numbers in Scheme are either integers or rational numbers.
But these aren't like the int
s you know from C++ or Java.
Integers in Scheme can be arbitrarily large ("arbitrary precision"),
as can both the numerator and denominator of a rational
number.
Scheme also has builtin complex numbers, both exact and inexact.
We'll mostly concentrate on inexact real numbers (called "floats" from
here on in) and exact integers.
Caution: The predicates integer?
,
rational?
, and real?
are also defined, and
can be useful at times. However, these correspond to the
mathematical meaning, not the underlying type. So for instance,
(integer? 5)
and (integer? 5.0)
both produce
#t
, even though 5
is a BigInt and 5.0
is a float.
The builtin functions inexact>exact
and
exact>inexact
are sometimes useful to convert between
the different types without changing the numerical value.
3.3 Integer functions
All the below functions return integer values, when given integer arguments.
+  * quotient remainder modulo max min abs gcd lcm exptNotice that division isn't there. Division sometimes returns a rational value, when given exact integer arguments.
3.4 Floating point functions
The above functions that make sense for inexacts are defined for inexacts, and additionally you have others like:
sin cos tan sqrt log exp floor ceiling roundwhich ought to be self explanatory.
3.5 Definitions of global constants
Sometimes you need to give something a name!
In Scheme, we do this using define
.
In its simplest form, you just write (define
So for example, the line
(define x 15)
creates a name x
and assigns it the value 15
.
You can put any expression in for the value, so for example
(define x (* 3 5))
would have the same outcome as the line above.
Exercises

Define a constant
ex1
and give it the value of \(4.7*(34.453  47.728) + 3.7\). But don't do any math yourself! Write that formula as a Scheme expression and make the computer do the calculation in your code. 
Functions like +, , *, max, and min that make sense for
more than two arguments (fewer than two as well!) work
just fine for more than two arguments. For example:
(+ 1 2 3)
evaluates to 6 just like you'd expect. Define a constantex2
that evaluates to the largest value of sqrt(5), sin(1) + sin(2) + sin(3), and 31/13.
Note: Remember that integer division produces rational numbers. You should notice something strange going on here. Make a comment in your code about it. 
Define a constant
ex3
that equals the evaluation of the polynomial \[2x^3  x^2 + 3x  5\] at \(x = 2.451\).
(Note, you are allowed to make extra constant definitions if you want...)  Create a global constant called "root2" that stores the square root of 2.
4 Function Definitions
But we all know that global variables, in general, are not a good idea. A nicer thing to do would be to create a function for \(2x^3  x^2 + 3x  5\) and then just call the function with argument 2.451. So how do you write a function? Well, the above would be:
(define (f x)
(+ (* 2 x x x)
(* 1 x x)
(* 3 x)
5))
(f 2.451)
This is actually a bit of a shortcut for a function definition,
as we'll discuss later. Clearly, you're defining a
new function, whose name is f
and whose parameter
names are everything else following in the parentheses (just
x
in this case), and then what follows is
an expression that is the value of the function. For a
simpler example, a function called myave
might be defined like this:
(define (myave x y)
(/ (+ x y)
2.0))
Hopefully the three components are clear.
Exercises

Write functions
tocelsius
andtofahrenheit
that convert back and forth from Celsius to Fahrenheit. Recall: \[T_C = \frac{5}{9}(T_F  32)\] 
Define a scheme function called
(testtrig x)
that computes \((\sin x)^2 + x \cos x\).
5 Control: if's and cond's
In C++ if's are statements. That means that they do not have type and they do not have value. Instead they describe a process whose side effects (output, changes in variable values, etc) embody the actual computation.
In Scheme everything is an expression, and that includes if's. An if expression has three parts: the test condition, the "then" expression and the "else" expression. The value of the if expression is either the "then" expression (when the test evaluates to true) or the "else" expression. For instance, the following expression evalutes to the absolute value of x:
(if (< x 0)
(* 1 x)
x)
You see, depending on the result of the test, we either get the value 1*x or simply x itself. We can use this to get define an absolute value function:
(define (myabs x)
(if (< x 0)
(* 1 x)
x))
although, of course, scheme already has one.
We can nest these expressions as needed.
The predicates we mentioned earlier come in handy when
writing if statements.
Numbers can also be compared with the usual: i.e <, >, ≤,
≥, =. Note: these look really weird because of Scheme's prefix
notation. It will take some time before you see right away that
(>= 5 4)
is true.
Note also: for nonnumeric objects the
equal?
predicate is what you want to use for comparison
(it also works on numbers).
Exercises

Define a function called
signedinc
, which returns 1 plus its argument if the argument is nonnegative, and 1 plus its argument if the argument is negative. 
Define a function
signedincbetter
which works likesignedinc
, but returns its argument unchanged if the argument is 0. 
Define a function
middle
that takes three numbers as argument and returns the middle of the three. E.g.(middle 4 2 3)
should evaluate to 3.
There's also a nice function cond
that's useful
when you have a bunch of distinct cases to consider. For
example, if you want to define a function whatsyoursign
that returns 1,0,1 according to the sign of a number, you
might use cond
as follows:
(define (whatsyoursign x)
(cond ((< x 0) 1)
((> x 0) 1)
((= x 0) 0)
))
So cond's arguments form a list of condition/result pairs.
The interpreter finds the first condition that is satisfied,
and the value of the cond expression is the result associated
with that condition.
The cond
function also has a special condition
called else
that can show up last to catch
anything which hasn't triggered the other conditions. So the
example above could also be written:
(define (whatsyoursign x)
(cond ((< x 0) 1)
((> x 0) 1)
(else 0)
))
Exercises

Define a function
middlebetter
which has the same behavior asmiddle
but uses cond's and boolean logical operations instead of if's.
6 Recursion!
To do anything interesting in Scheme we need recursion. The
reason is that we don't have loops! Suppose, for example, we
wanted to define a function sumrange
that would
sum all the integers in the given range. Normally we'd think
of using loops for this, but Scheme doesn't do loops! They're
contrary to the idea of referential transparency  i.e. no
side effects. Loops are all about creating side effects 
over and over and over. At any rate, we need to use recursion:
(define (sumrange i j)
(if (= i j)
i
(+ i (sumrange (+ i 1) j))))
Recursion is nothing new for you folks, you'll just use a lot
more of it in Scheme.
Exercises

Define a
factorial
function. Try taking the factorial of 111. Make a comment about why the straightforward Java implementation would not have given you this result. 
I want to compute compound interest. Write a function
(accrue B r y)
that takes a balance, an annual interest rate, and a number of years and returns the balance at the end of that time period assuming that interest is computed monthly. Recall: If the annual interest rate is r and the balance is B, then one month's compounding produces a new balance of B*(1 + r/1200) (we're assuming a value of, say, 7.5 for r means 7.5%). Hint: A nice bottomup solution to this would probably involve writing a(compoundmonth B r)
function, that just does one month of compounding, testing it, and then moving on. Next, write anaccruemonths
that would take a balance, a rate, and a number of months, and compute the balance at the end of that many months  test it! Then it should be easy to write youraccrue
function. 
Write a function
fib
to compute Fibonacci numbers. For the purposes of this class, fib(1) and fib(2) are both equal to 1, and all the rest are defined by the rule fib(n) = fib(n1) + fib(n2).
7 Scheme glue: cons
cons
is a builtin Scheme procedure that takes two objects
and combines them into one. It is the basic building block of every data
structure that we can make in Scheme. The builtin functions
car
and cdr
act as a sort of a reverse cons 
they return the first part and the second part of a
cons
ed pair, respectively.
(Why 'car' and 'cdr'? Historical reasons, of course! These were the names of parts of the registers that existed in the machine Lisp was originally implemented on.)
We can also nest cons statements inside each other, and use the
predicate pair?
to determine if something is a consed pair:
> (define something (cons (cons 5 2) 3)) > (pair? something) #t > (cdr something) 3 > (pair? (car something)) #t > (pair? (car (car something))) #f
Using cons in this way produces what are called 'dotted pairs', and they
are printed by the interpreter as (a . b)
. But one you start
nesting conses, you might notice the way they display is a bit strange.
We'll see why this in the next class.
Exercises

Write a function
splitinches
that takes an integer for a number of inches and produces a dotted pair of feet and inches, in the usual way so that the cdr of the dotted pair that gets returned is between 0 and 11. For instance(splitinches 73)
should produce(cons 6 1)
(which will be displayed in the interpreter as(6 . 1)
). 
Write a predicate function
shorter?
which takes two feetinches dotted pairs, as returned by thesplitinches
function, and returns true if the first is less than the second, in terms of total inches. Note: there are a few different ways to do this. You decide what you think is the best approach.