Foundations of Computer Science
Fall 2007

For next time:

1) order the book (see my email)

2) read Louden, Programming Languages, Chapter 1, 
   Sections 1.1 through 1.3

3) install Dr. Scheme in the environment of your choice

4) (maybe) work on Scheme exercises I will distribute


What is this class about?
-------------------------

Programming paradigms

1) functional programming in Scheme

2) logic programming in Prolog


Automata

1) regular expressions and finite automata

2) context-free grammars and pushdown automata


Theory of computation

1) Turing machine

2) decidability


Complexity

1) analysis of algorithms

2) P and NP


Algorithms and data structures

0) review of linear data structures

1) trees


Language translation

1) parsing

2) tree representation of expressions

3) code generation?


Skills

1) polyparadigmatic thinking

2) practical language design and translation

3) algorithmic thinking

4) proof design

5) theory appreciation



Questions
---------

1) favorite topics?  more of this/less of that?

2) environment choices -- choose a standard?  agree to disagree?

3) language preferences?

4) how much programming project?  how much paper and pencil?

5) tolerance/need for open-ended project?



Introduction to Scheme
----------------------

1) install Dr. Scheme

2) select Choose language and select "Advanced student"

   We will start with a small language, gradually add features

   Scheme as a practical programming language 

      vs.

   Scheme as a means of demonstrating the power of
   lambda calculus + list processing


Scheme syntax
-------------

[Note: this presentation follows Abelson and Sussman, 
Structure and Interpretation of Computer Programs]

Numbers are primitive expressions.

Standard arithmetic operators are built in: +-*/

Applying operators to operands looks like this:

(+ 1 2)

The parentheses are not decorative; they are the "apply" operator.

+ 1 2 

is just a sequence of three values.

This placement of the operator is called prefix, as
opposed to infix and postfix.

Do you know languages/contexts that use infix?  postfix?







What are the pros and cons of each?








This is a small example of a kind of discussion I want us to have:

1) map out the space of possible designs by exploring endpoints

2) understand tradeoffs in the space.


Compound expressions
--------------------

An advantage of Scheme syntax is that the meaning of an
expression is unambiguous.

In "normal" notation, what does  1 + 2 * 3 mean?

What are the two possibilities?

How do you represent the possibilities?

How do you know which one is right?

Draw a tree that represents this compound expression:

(* (+ 2 (* 4 6))
   (+ 3 5 7))








Evaluating expressions
----------------------

1) an expression can be a sequence of digits

   value = numeric value of the digits (intepreted in base 10)

2) an expression can be an operator

   value = the procedure represented by the operator

3) an expression can be a sequence of expressions in parentheses

   value = value of the first expression applies to the sequence
           of values of the other expressions

These rules imply a partial order of evaluation.



Variable binding
----------------

define is an operator that creates a binding between a name and
a value

(define pi 3.1415926535897931)

Now the expression

pi

has the value 3.1415926535897931

This is not the same as an assignment statement in an imperative
language, because you cannot rebind a name.

An environment is a set of bindings.


Procedures
----------

A procedure is an object* that represents a function.

   [*LISP/Scheme programmers probably wouldn't call it that.]

There are two ways to create a procedure.  One is the lambda operator

(lambda (x) (+ x 1))

The value of this expression is an object that represents the
function SUCCESSOR.

(lambda (y) (+ y 1))

The value of this expression is an object that _also_ represents the
function SUCCESSOR.

So these two procedures are equivalent.


You can bind a name to a procedure.

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


But this sort of thing happens so often that there is 
a simplified syntax, also known as 'syntactic sugar':

(define (square2 x) 
  (* x x))


If you are used to languages with a return statement, this
might seem odd.  All procedures contains a single expression;
the 'return value' is the value of that expression.

Write a procedure, sum-of-squares, that takes two arguments
and uses 'square to compute their sum of squares.