Foundations of Computer Science
Fall 2007

For today you should have:

1) done the exercises near the end of notes02 and brought a neatly
   printed hard copy of your working code.

2) prepared for a Scheme quiz

3) read Louden, Programming Languages, Chapter 1, 
   Sections 1.4 through 1.6 and prepared to answer the
   questions below

For next time you should:

1) read from Sipser and answer the questions below

2) finish off any unfinished examples from notes01 and notes02

3) start on the symbolic differentiator (below)


Reading questions
-----------------

Sipser, page xi: To the student, and pages 1-16

1) What is the central question of complexity theory?




2) Give an example of an application where a computationally hard
   problem is a good thing.




3) What's the difference between computability theory and complexity
   theory?




4) Give an example of an automaton that has a practical application.




5) After you read about Sets, do Exercise 0.2 on page 25








6) After you read about functions and relations, do Exercise 0.6 on
   page 26.




7) After you read about graphs, do Exercise 0.8 on page 26.




8) What is a tree?  What are leaves?





9) What is a language?




Data-code equivalence
---------------------

When you evaluate

> (cons 1 2)

Scheme builds a data structure (which we represent with a
box and pointer diagram) and then prints a string representation
of the data structure.

(1 . 2)

When you evaluate

> '(1 . 2)

Scheme builds some representation of this quoted expression
and the prints a string representation of the representation:

(1 . 2)

Notice that the printed output is the same in both cases.  Does
that mean that the internal representation is the same?

How can we tell?  Let's create two values:

(define e1 (cons 1 2))
(define e2 '(1 . 2))

Now, what are the operations we can perform with these values?

(null? e1)   (null? e2)      #f

(pair? e1)   (pair? e2)      #t

(car e1)     (car e2)        1

(cdr e1)     (cdr e1)        2

Those are all the operations I can think of that will work with
these values (others will produce errors).

For all intents and purposes (not, by the way "intensive purposes")
these two values are the same, and therefore, by the fundamental
principle of data abstraction:

	  They are the same.


The same is true for lists; the quoted expression '(+ 1 2) is, 
for all I&P, a list of three elements.

All function applications look like lists, and all Scheme
expressions look like function applications, and therefore

	  All Scheme expressions (code) can be treated as
	  lists (data).

This data-code equivalence is a powerful features that makes Scheme
particularly suited to language translation.

Question: what's the difference between '(+ e1 e2) and (list '+ e1 e2)?


Symbolic differentiation
------------------------

Read the redacted handout from Abelson and Sussman, Structure
and Interpretation of Computer Programs.

A note on the SICP style of presentation:

1) first you get the interface for the underlying data type

2) then you get code that builds on this interface

3) then you get an implementation of the interface

Their point is to demonstrate:

1) data abstraction (another data type could implement this
   interface), and

2) top-down programming.

I am not dogmatic about top-down programming, but I will point
out that it is only possible if you understand the problem
well enough, when you start, to design the interface.