Lab 1: Introduction to Scheme

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, 29 August. It should be submitted as "413 lab 01", 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.

# Firing up the IDE

Before beginning, run the following command in a terminal window on your Linux lab machine:

/courses/roche/413/setup

The language we are learning is called Scheme. But the interpreter for the language is called "Dr. Racket". (It used to be called Dr. Scheme, but then they mucked with the language so much that they changed the name of the programming language to Racket, and so here we are. But don't worry, we will learn Scheme still.)

At the command prompt simply type "drracket &" and you should see the interpreter/code-entry split window open up.

There are many "dialects" of the Scheme language. The one we are using for this class is called "R5RS". If you ran the script above before starting DrRacket, this language should already be selected 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. Why not go to the submit page right now and learn how this is done?

# Scheme lab formatting

Comments in Scheme start with a semicolon. The convention is to use a single semicolon for minor comments, two semicolons to document functions and the like, three semicolons to indicate sections of your code, and so on. You should start off your file (top window) with a few lines like

;;; SI 413 Lab 1
;;; MIDN Johnson and MIDN Johnson

This lab (and all the labs to follow) is organized into numbered "exercises". You should indicate - in comments - 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 auto-tested, be sure to use the exact names that are specified in the lab. Spelling counts!

As for formatting, one of the best reasons to use this IDE is that it will automatically indent your code for you. If it gets screwed up, you can always hit Ctl-I to reindent everything and make it all pretty. The only thing you really have to worry about is when to insert newlines. This is somewhat a matter of taste, but to make Scheme code readable it's usually better to err on the side of keeping your lines short and simple. This makes the nesting of all those parentheses easier for human eyes to process. Do it or receive stylistic judgment!

# 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)).

## Booleans and Predicates

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.

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 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.

## 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 ints 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 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.

## Integer functions

All the below functions return integer values, when given integer arguments.

+            -             *
quotient     remainder     modulo
max          min           abs
gcd          lcm           expt

Notice that division isn't there. Division sometimes returns a rational value, when given exact integer arguments.

## 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  round

which ought to be self explanatory.

## Exercises

1. Write 4.7*(34.453 - 47.728) + 3.7 as a scheme expression, and find its value.
2. 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. You should notice something strange going on here. Make a comment in your code about it.
3. Write a scheme expression that evaluates the polynomial $2x^3 - x^2 + 3x - 5$ at $$x = 2.451$$.

# Definitions

## Global constants

You may have noticed that the last of the previous problems 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 might be:

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

The define statement binds a name (here it's 'x') to a constant value (2.451).

## 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 my-ave might be defined like this:
(define (my-ave x y)
(/ (+ x y)
2.0))
Hopefully the three components are clear.

## Exercises

1. Create a global constant called "root2" that stores the square root of 2. While you're at it, go back up to exercises 1-3 and define them as global constants called "ex1", "ex2", and "ex3", respectively.
2. Write functions to-celsius and to-fahrenheit that convert back and forth from Celsius to Fahrenheit. Recall: $T_C = \frac{5}{9}(T_F - 32)$
3. Define a scheme function called (test-trig x) that computes $$(\sin x)^2 + x \cos x$$.

# 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 (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).

## Exercises

1. 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.
2. Define a function signed-inc-better which works like signed-inc, but returns its argument unchanged if the argument is 0.
3. 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 might 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.

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 (whats-your-sign x)
(cond ((< x 0) -1)
((> x 0) 1)
(else 0)
))

## Exercises

1. Define a function middle-better which has the same behavior as middle but uses cond's and boolean logical operations instead of if's.

# 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 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.

## Exercises

1. 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.
2. 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 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.
3. Write a function fib to compute Fibonacci numbers. For the purposes of this class, fib(1) and fib(2) are both 1 equal to 1, and all the rest are defined by the rule fib(n) = fib(n-1) + fib(n-2).

# Scheme glue: cons

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 consed 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 the IDEA 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

1. 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 the IDE as (6 . 1)).
2. 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.