Lab 1: Introduction to Scheme

This lab is due at the beginning of your next lab period.
It should be submitted as "lab01" and contain a single file called
"`lab.scm`

". See the "submit" link on the left menu 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.

At the command prompt simply type "`drscheme &`

" and
you should see the interpreter/code-entry split window open
up.
**[Note:** You have to choose a "language" before you start
doing anything. Under the menu: *Languagues → Choose
Language* choose *Module*. You will also have to
have `#lang scheme`

at the top of any program, which
Dr. Scheme will now insert for you.**]**

The lower pane is the interpreter. You can enter a scheme
expression like `(+ 3 4)`

at the prompt and the
`return`

key will cause the interpreter to
evaluate the expression - *provided the cursor is at the
end of the line*. You can get the cursor to the end
of the line instantly by pressing *end*.

The upper pane is the definitions window. This is where you
put things you want to keep and eventually submit.
You should start by saving this window with the proper name for
submission later. **Click on the "submit" link on the menu right
now and learn how this is done.**

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))`

.

Scheme has built-in 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`

.

Scheme also has many built-in 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.

Section
3.1
of the R6 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 (BigInts, you'll
hear people say), as can both the numerator and denominator of a rational
number.
Scheme also has built-in 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 built-in functions `inexact->exact`

and
`exact->inexact`

are sometimes useful to convert between
the different types without changing the numerical value.

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.

The above functions that make sense for inexacts are defined for inexacts, and additionally you have others like:

sin cos tan sqrtwhich ought to be self explanatory.

- Write 4.7*(34.453 - 47.728) + 3.7 as a scheme expression, and find its value.
- 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. Write an expression 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. Do you notice something strange going on here?
- Write a scheme expression that evaluates 2*x^3 - x^2 + 3*x - 5 at x = 2.451.

You may have noticed that the last of the previous problem was a bit of a pain, because you had to write 2.451 over and over. Just be glad it wasn't 34.98789798723! We could avoid this by defining 2.451 once, assigning it an easy-to-type name, and then evaluating the expression using that name.

So how do we do that? Well, the above would be:

> (define x 2.451) > (+ (* 2 x x x) (* -1 x x) (* 3 x) -5) 25.793878702The

`define`

statement binds a name (here it's 'x') to a
constant value (2.451).
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 2*x^3 - x^2 + 3*x - 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) 25.793878702This is actually a bit of a shortcut for a function definition, as we'll discuss later. Clearly, you're

`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 `my-ave`

might be defined like this:
Hopefully the three components are clear.(define (my-ave x y) (/ (+ x y) 2.0))

- Create a global constant called "root2" that stores the square root of 2. Then use a predicate function call to confirm that this value is inexact.
- Write functions
`to-celsius`

and`to-fahrenheit`

that convert back and forth from Celsius to Fahrenheit. Recall: T_C = 5/9(T_F - 32) - Define a scheme function called
`test-trig`

for sin(x)^2 + x*cos(x).

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 (my-abs 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 non-numeric objects the
`equal?`

predicate is what you want to use for comparison
(it also works on numbers).

- Define a function called
`signed-inc`

, which returns 1 plus its argument if the argument is non-negative, and -1 plus its argument if the argument is negative. - Define a function
`signed-inc-better`

which works like`signed-inc`

, 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 whats-your-sign
that returns 1,0,-1 according to the sign of a number, you
miught use `cond`

as follows:

(define (whats-your-sign 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.

By the way, did you notice the square brackets (`[`

and `]`

) that showed up in the cond expression? Those are just
there for readability. We could have used regular parentheses, but in cond
statements it's conventional to surround each condition-result pair with
square brackets. What you do is up to you - as long as they match, the
interpreter won't complain.

- Define a function
`middle-better`

which has the same behavior as`middle`

but uses cond's and boolean logical operations instead of if's.

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 `sum-range`

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 (sum-range i j) (if (= i j) i (+ i (sum-range (+ i 1) j))))Recursion is nothing new for you folks, you'll just use a lot more of it in Scheme.

- Define a
`factorial`

function. Try taking the factorial of 111. What do you notice about the result. Do you think the straightfoward C++ implementation could've given you this result? - I want to compute compound interest. Write a function
`accrue`

that takes a balance, an annual interest rate, and a number of years and returns the balance at the end of that time period asuming 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 bottom-up solution to this would probably involve writing a`(compound-month B r)`

function, that just does one month of compounding, testing it, and then moving on. Next, write an`accrue-months`

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 your`accrue`

function. - Write a function
`fib`

to compute Fibonocci numbers. Recall, fib(0) and fib(1) are both 1. All the rest are defined by the rule fib(n) = fib(n-1) + fib(n-2).

`cons`

is a built-in 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 built-in 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 `cons?`

to determine if something is a cons-ed pair:

> (define something (cons (cons 5 2) 3)) > (cons? something) #t > (cdr something) 3 > (cons? (car something)) #t > (cons? (car (car something))) #f

Using cons in this way produces what are called 'dotted pairs', and they
are printed by Dr. Scheme 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.

- Write a function
`split-inches`

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`(split-inches 73)`

should produce`(cons 6 1)`

(which will be displayed in Dr. Scheme as`(6 . 1)`

). - Write a predicate function
`shorter?`

which takes two feet-inches dotted pairs, as returned by the`split-inches`

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.