01: Introduction to Scheme Programming

This article is a part of a series where I go through teachyourselfcs. If you would like to start at the beginning start here.

INTRO

I will be following the Summer 2010 Calendar so each week will consist of 4 lectures and 2 labs.

LECTURES

L01

Mathmatical Operations

Class starts by going over some sytax for Scheme. Most languages do simple operations the same way we learned in grade school (infix notation):
2 + 2 + 3
Scheme uses a different syntax where the operator is always on the left (prefix notation) and you can add as many numbers as you would like:
(+ 2 2 3)
Now lets say we want to do something like:
2 + 2 + 3 - 4
In Scheme you can simply nest operators:
(- (+ 2 2 3) 4)

When you first see this it looks way more complicated, but what is happening under the hood makes it a lot clearer.
Scheme takes the arguments and then computes the expressions of the arguments until it gets down to a primitive value. (+ 2 2 3) is a expression and not a primitive value, so it calls (+ 2 2 3). The left argument of the - is now 7 and both arguments are primitive values, meaning it can calculate the - to get 3.

Define

define is an interesting keyword. It can be used to create functions:

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

The syntax is very different from other languages, but try to think of define as a function itself.

Define’s first parameter takes in a symbol (square) as it’s first argument that will be the name of the procedure. The rest of the parameters are parameters for the body in this case x.

The second parameter that define takes in is the body that the procedure will call (* x x).

Define can also be used to store constants:
(define pi 3.14159)

This is the same thing as above but used in a different way. Since 3.14159 is a primitive no expression needs to be evaluated for the second parameter.

Conditionals

Here is the first example of a program we see in class:

(define (plural wd)
	(if (equal? (last wd) 'y)
	(word (bl wd) 'ies)
	(word wd 's)))

As you’ve probably already guessed, if is a function.

The first parameter is the test case for example if we input fly (equal? (last wd) 'y) would be true, because fly ends in y.

The third parameter if takes in is the expression if the test case is true.

The third parameter if takes in is the expression if the test case is false.

Also worth noting that names that return a boolean add a ? to the end to show that the primitive returned is true or false. Like how equal is equal? in the code block above.

L02

Recursion

(define (pigl wd)
	(if (pl-done? wd)
		(word wd 'ay)
		(pigl (word (bf wd) (first wd)))))

(define (pl-done? wd)
	(vowel? (first wd)))

(define (vowel? letter)
	(member? letter '(a e i o u)))

Recursion is when a procedures calls the same procedure that it is writing. Without a test case this will go on infinitely, but a recursive function continues to do the body of the procedure until it is told to end.

Notice in the above example from lecture the function calls pigl until pl-done is equal to true.

Lets say pigl gets called with scheme. The conditional checks pl-done which checks the first letter in the word to see if it is a vowel. Since pl-done is false because s isn’t a vowel it calls pigl again with the argument chemes. This is because word takes the arguments cheme and s and adds them together. pigl gets called repeatedly until it is called with a vowel as the first letter. When the first letter is a vowel the expression (word wd 'ay) is ran and the result is a primitive which means the procedure stops.

Abstraction

Big Picture:

Application                   (highest)
------------------------------
High level language (Scheme)
------------------------------
low level language  ( C )
------------------------------
machine language/ architecture
------------------------------
logic gates
------------------------------
transistors
------------------------------
quantum physics                 (lowest)
------------------------------

Abstraction is the layering of pieces on top of eachother. Little pieces are put together to form a layer that can be referenced as a whole.

Functional Programming

With the introduction of multi-core processers, parallelism has helped functional programming make a comeback. If everything is a function you won’t run into race conditions created by dependencies.

Function vs. Procedure

Two functions are the same if they give the same output with given inputs.

A procedure is a sequence of steps for computing a function.

Therefore 2x + 6 and 2(x + 3) are the same function but different procedures.

Cond

(define (buzz n)
    (cond ((equal? (remainder n 7) 0) 'buzz)
    ((member? 7 n) 'buzz)
    (else n)))

cond allows for multiple test cases, and will return the first clause that is true.

Lets try 14. Since 14 / 7 has a remainder of 0 the first clause is met and returns buzz.

Now Lets try 17. The first clause is not met, and therefore goes onto the next clause. 17 does have a 7 inside of it so buzz is returned.

Now lets try 15. The remainder is 1 so the first clause is not met, and 15 does not have a 7 inside of it so the catch all else keyword returns the number 15.

Important to note:
If a cond does not have an else statement it will return unspecified, which can be different depending on interpreted, so always have an else statement.

Applicative Order vs Normal Order

(def (f a b) (+ (g a) b))
(def (g x) (* 3 x))

(f (+ 2 3) (- 15 6))

Applicative Order:
evaluates the sub expressions until they are primitive values, then passes the primitive results back up to the parent function.
(f (+ 2 3) (- 15 6))
2 + 3 and 15 - 6 will be evaluated before the outside f is evaluated. Then f will be called with (f 5 9).
Normal Order:
evaluates the outsides first, but instead of passing primitive values it passes the expressions.
(f (+ 2 3) (- 15 6)) turns into (+ (g (+ 2 3)) (- 15 6))
Now f is done and the next expression can be evaluated.

Possible Problem:

(def (zero z) (- x x))

applicative

(zero (random 10)) --->
(random 10) ==> 8
(zero 8) --->
(- 8 8) ==> 0
0

normal

(zero (random 10)) --->
(+ (random 10) (random 10)) ==>
    (random 10) ==> 8
    (random 10) ==> 1
(- 8 1) ==> 7
7

Since the (random 10) is split into 2 different function alls in normal order you get different results.

L03

Data vs Procedures

Data is like a noun. Procedures are like verbs.

Capitalization does not matter in scheme. Able to take in functions as arguments. se is the function for creating sentences.

Lambda

The thing that makes a function. A thing that creates and can call a function without having to be named.

PRED: short for predicate, predicate is a function whose range is a boolean (true or false). Every procedure has a lambda hidden inside of it.

L04

Using lambdas for control using procedures as data. Keep decides whether to keep data or not.

first class datatype

Rule of Thumb:
They can be stored as a variable.
They can be stored inside a data type like a list.
You can return function to make other functions.
(let bindings body) Binding is a name: value expression.
Bindings can’t reference eachother during declaration because of applicative order.
let* allows you to reference other bindings during declaration by nesting the lets.
Want to keep as many variables local as possible.

LABS

Lab 1A

The first problem for the lab was to modify the plural program to handle a word ending in y, but has a vowel in front of it (boy).

(define (plural wd)
	(if (equal? (last wd) 'y)
		(if (vowel? (last (bl wd)))
		(word wd 's)
		(word (bl wd) 'ies))
	(word wd 's)))

(define (vowel? letter)
	(member? letter '(a e i o u)))

I handled this by adding a conditional that checks for the second to last letter.

The second assgnment was:

Define a procedure that takes three numbers as arguments and returns the sum of
the squares of the two larger numbers.

My Solution:

(define (twoLargerSums a b c)
    (if (>= a b)
        (if (>= b c)
            (+ (square a) (square b))
            (+ (square a) (square c)))
        (if (>= a c)
            (+ (square a) (square b))
            (+ (square b) (square c))))
)

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

Lab 1B

Solution for #3 on lab:

(define (substitute sent old new)
    (if (equal? sent '())
        '()
        (se (replace (first sent) old new) (substitute (bf sent) old new))))

(define (replace wd old new)
    (if (equal? wd old)
        new
        wd)
)

Note to self, don’t copy and paste function calls to check if your code is right because there might be special characters in there :P.

The replace function here takes in the current word and checks to see if the word should be replaced, then it returns what the word should be. Substitute is a recursive function that iterates the sentence and returns the sentence with the replacements.

READINGS

1.1 The Elements of Programming

The section starts off saying that there are 3 mechanisms that languages utilize to simplify complex ideas:
primitive expressions: simplest entities within a language.

means of combination: The ability to combine simple entities.

means of abstraction: The ability to name and manipulate combined elements.

Breaking down a compound expression:
combination: (+ 137 349)
operator: +
operands: 137 349

The interpreter runs in a “read-eval-print” loop. That is why it is not necessary to print stuff out like in other languages.

Environment: The name-object pairs the interpreter keeps in memory.

Compound Procedures can be used to build on top of other Compound Procedures:

(define (sum-of-squares x y)
(+ (square x) (square y))

Compound Procedure: procedure that you make out of other procedures.

Primitive Procedure: procedure built into the language ex: +

Both are used exactly the same.

When writing programs it is important to write modular code that doesn’t care how the other things are computed, only what is computed. This is known as a Black-Box abstraction.

Lisp allows for block structure so you can nest a define in another define, and only the parent will have access to the nested define.
Lisp also allows the sub define functions to have access to parameters in the parents scope. This is called lexical scoping.

1.2 Procedures and the processes they generate

Linear Recursion vs linear interative

Recursive calls itself, interative uses a helper iterator function to loop through the possibilities.

Tail-recursive: an iterative process in constant space.

Tree-recursive: think fibonacci where it uses recursion multiple times. Tree recursive procedures are easy to identify, but not very efficient. It is possible one day a “smart compiler” could find these procedures and make them efficient.

1.3 Formulating Abstractions with Higher Order Procedures

Sigma Notation: The sum of numbers between A and B. This can be abstracted to create a procedure that handles all needs for doing a procedure to calculate a sum.

Arguments for a Summation function:

Term: Procedure for the sum.
a: start point
b: end point
next: The increment function ex: + 1 + 2 + 3

You can use binary search like logic to find points within a function. By splitting the length repeatedly then checking accuracy you can continually get closer to the point you are looking for in the function. The calculated runtime for these functions are:

L = length of the functions start to end points
T = tolerance, the distance from the given point that will return a result
runtime:
log(L/T)

Think of L/T as the possibilties between the two points.