Lecture: 2
Date: Jan 9, 2008

Continue with accumulators
New notations for Data definitions

=====

Administrative notes:

Good news, bad news (you decide which is which)
- no quizzes in class
- no laptops in class

We're using v372, so you should too.

My office hours: W 3-5 (right after class).

If you fail a quiz, talk to your TA to figure out what to do about
it. If you don't, you get a ZERO on that week's homework.

Lab quizzes are based on the portfolio problems for that week.  Make
sure you can do them all by Sunday, and if you are having trouble,
bring it up in class on Monday and we'll work through it so that you
are prepared by Tuesday.

Books are available from Reprographics (http://nerepro.com/), which is
supposedly behind the bookstore.

=====

We know that foldl and foldr fold a list together in different
orders. When we have a commutative operator (like + on integers), we
can choose either.  But let's look at a remaining difference between
structural recursion and accumulators:

Here is sum, written using structural recursion.  Almost all of this
code comes for free from the design recipe.

;; sum : [Listof Number] -> Number
;; Purpose: to sum the given list of numbers.
(define (sum lon)
  (cond [(empty? lon) 0]
        [(cons? lon) (+ (first lon)
                        (sum (rest lon)))]))

Here is sum-acc, sum written using an accumulator.

;; sum : [Listof Number] -> Number
;; Purpose: to sum the given list of numbers.
(define (sum-acc lon n)
  (cond [(empty? lon) n]
        [(cons? lon) (sum-acc (rest lon)
                              (+ (first lon) n))]))

Note that (sum-acc ls n) = (+ n (sum ls)).

Let's step through the evaluation of both to compare the differences.

(sum '(1 2 3))
(+ 1 (sum '(2 3)))
|    (+ 2 (sum '(3)))
|    |    (+ 3 (sum '()))
|    |    |    0
|    |    3
|    5
6

Notice that (sum (cons 1 lon)) = (+ 1 (sum lon)), but we cannot
perform the addition (+ 1 ?) until we finish computing (sum lon).  The
evaluator (DrScheme) must /remember/ to add 1 to the result of
computing the recursive call.

So if we have a list with 10,000 elements, 10,000 additions operations
stack up before we can actually start doing them.  (Think about how
/wide/ the trace of this computation will be).

(sum-acc '(1 2 3) 0)
(sum-acc '(2 3) (+ 1 0))
(sum-acc '(2 3) 1)
(sum-acc '(3) (+ 2 1))
(sum-acc '(3) 3)
(sum-acc '() (+ 3 3))
(sum-acc '() 6)
6

Notice that here we perform the addition as we go and the result of
the recursive call is the result of the overall computation; we don't
need to remember to do anything to the result of the recursive call.
Nothing stacks up; the width of the trace stays fixed.

So not only do foldr/structural recursion and foldl/accumulators have
different orderings, but they have different space consumption.

Try these and other examples out in the stepper see the differences.

[Also recall that accumulators are motivated by computations that need
to remember stuff about previous computations... they can use the
accumulator to remember, whereas structural recursive computations
have to re-compute.]

There will be more on loops and accumulators in the homework.


=====

Let's return to our data definitions from last class (and lab):

;; An Ad is a (make-ad String Number Number).
(define-struct ad (name minutes profit))

;; An RS (Radio Show) is a (make-rs String Number Ad).
(define-struct rs (name minutes ad))

[I've simplified things a bit-- a show has a single ad, not a list of
ads.]

There is a lot of information in this data definition.  For example,
we can write already write templates for any function that consumes an
Ad or an RS.

(define (rs-template an-rs)
  (rs-name a-show)    ;; ? String
  (rs-minutes a-show) ;; ? Number
  (rs-ad a-show) ...) ;; ? Ad

Q: From a data definition, what do we know?
A: 1) Number of fields
   2) Type of fields (kind of data in fields)
   3) Names of fields, name of structure.

We're going to look at TWO new notations for writing down this
information.

The first is graphical:

+----------------+
|       Ad       |
+----------------+
| String name    |
| Number minutes |
| Number profit  |
+----------------+

We draw a box, the name of the class of data goes in the top.  Below
we list the type and name of each field.

Q: What does the graphical notation for RS look like?

+----------------+
|       RS       |
+----------------+
| String name    |
| Number minutes |
| Ad ad          |
+----------------+

Notice that the last line refers to Ad.  We draw a "containment arrow"
that goes FROM RS's ad field TO the Ad box [I may have had this
backwards in class].

+----------------+
|       RS       |
+----------------+
| String name    |
| Number minutes |
| Ad ad          |--+
+----------------+  |
                    |
+----------------+  |
|       Ad       |<-+
+----------------+
| String name    |
| Number minutes |
| Number profit  |
+----------------+

Now let's look at yet another notation: Java

(the theme of today's class is how to write the same thing over and
over again)

class Ad {
  String name;
  int minutes;    Q: What does "int" mean?
...               A: Integer
}                 Q: What is an integer?
                  A: Whole number

In Scheme, a number is a number is a number.  2/3 is an exact rational
number, we can do things like add 2/3 to 1, etc.

Java (and most other programming languages) do not have a "Number"
type, but rather they have several distinct kinds of numbers, like
integers, inexact numbers, ... (we'll see others later).

Moving on:

class Ad {
  String name;
  int minutes;
  int profit;

  ...
}

This is a "class" with 3 fields (just like our Scheme
structure). define-struct automagically made a constructor for us
(make-ad, made-rs).  Java doesn't do this, so have to write the
constructor ourselves:

class Ad {
  String name;
  int minutes;
  int profit;

  // Constructor
  Ad(String name, int minutes, int profit) {
    this.name = name;
    this.minutes = minutes;
    this.profit = profit;
  }
}

You can make a line comment with "//" in Java, analogous to ";;".
You can make a block comment with "/* ... */", analogous to "#| ... |#".

Notice that we no longer have parenthesis littered everywhere, however
we have to learn (by rote, unfortunately) the syntax (grammatical
rules) for Java--- where do you put a curly brace, where do you put a
parenthesis, what are the precedence rules, etc.

The above is the (verbose) Java equivalent to the (succint) Scheme
data definition:

;; An Ad is a (make-ad String Number Number).
(define-struct ad (name minutes profit))

Q: Write the Java equivalent of the RS data definition.

Q: from audience: What does "this" mean?
A: Just as in Scheme we make a distinction between "a structure
definition" and "an instance of that structure", we make a distinction
in Java between "a class definition" and "an instance of that class".

So "this.name = name;" means roughly, when the constructor is called,
a new instance of Ad will be created, and "this" instances name field
will be whatever was given as a name (the first argument to the
constructor).

Notice how we say the same thing several times.

Q: Could you write a Scheme program that took in a data definition and
produced the Java code that defined that class of data?
A: Yes.  Easily.

Now that we have data definitions, let's make some example data.

Java is class-based, programs consist of sequences of classes, so we
need an "example" class that will use our data definitions:

class Example {
  // An Exampe has no fields, so this area is left intentionally blank.

  // Constructor
  Example () { }
  // This constructor takes no arguments, since there are no fields.

  // Example data go here:

  // Instead of:
  // (define ipod (make-ad "ipod" 2 100))

  // We write:
  Ad ipod = new Ad("ipod", 2, 100);

  // Instead of:
  // (define news (make-show "news" 60 ipod))

  // You write:
  // ?
}


Notice how we say "Type name = Constructor(Arg1, Arg2, ..., ArgN);"

Q: What kinds of data have we seen so far?
A:

   - Strings : Predefined class (it's fancy: handles unicode, knows
     that 'ch' comes after 'h' when you're speaking a Slavic language,
     for example).

   - int : Built-in primitive (not a class, that's why it's lowercase).
     Other built-in primitives:
     * float
     * double
     * long
     * short
     * char - 'x', 'y', ...
     * boolean - true, false
     * ...

float and double represent inexact numbers.  "float" comes from
"floating point number"-- a number is represented with a fixed number
of bits, the radix point (aka decimal point if we're talking base ten)
moves ("floats") around as we compute.  A "double" ("double precision
floating point number") is twice as "wide": it uses twice as many bits
to represent numbers with greater precision.

long and short, like int, are exact integer numbers.  We more or less
ignore them.

   - User-defined classes (like Ad, RS, etc.)

Q: What other kinds of data did we see in 211?
A: A bunch.

Q: What other kinds of data did we see in 211 when we wanted data that
was "one of" some collection of other classes of data?
A: Unions

Let see how to do unions.

A Shape is one of ?:
- Circle
- Square
- Triangle
- Rhombus
- ...

Q: Is this is a complete data definition?
A: No, we need data definitions for each variant in our union.

;; A Circle is a ? (make-circle Number String Symbol)
(define-struct circle (size color mode))

;; A Square is a ? (make-square Number String Symbol)
(define-struct square (size color mode))

Draw diagrams for these data definitions.

+--------+  +--------+
| Circle |  | Square |   ... (triangle, etc).
+--------+  +--------+
|  ...   |  |  ...   |

How do we represent, graphically that these are variants of a Shape?
Using an "inheritance arrow" (it has a hollow arrow head), that goes
FROM the variant TO the union, which is a box with no fields:

     +----------+
     |  IShape  |
     +----------+
      / \    / \
      ---    ---  
       |      |
+--------+  +--------+
| Circle |  | Square |   ... (triangle, etc).
+--------+  +--------+
|  ...   |  |  ...   |


In Scheme, a union is represent only in the comments of a
program. Variants of a union are recognized using cond.  In Java, the
union becomes a part of the program and is represented an "interface":

interface IShape {}

Notice that this uses the "interface" keyword instead of "class" and
the body of an interface, for now, is always empty.

As a convention, we use the prefix "I" for interface names.

Every class that wants to be a variant of a union must say so using
the "implements" keyword.  For example:

class Circle implements IShape {
   // ... usual stuff goes here ...
}

Now, how can we make a shape?

IShape sq1 = Sq(5,"blue","solid");

Q: Where do you put the above?
A: In the examples class.

The diagrams we have seen are a slight adaptation of UML diagrams, a
tool professional programmers use all the time.


Quick digression in the last 5 minutes of class:

Let's return to the earlier question about a program that would
produce Java code from a data definition.

;; A StructDefn is a (make-struct-defn Symbol [Listof Field])
(define-struct struct-defn (name fields))

;; A Field is a (make-field Symbol Symbol)
(define-struct (name type))

Now, develop the program struct-defn->java : StructDefn -> String.