struct Cons {
int first;
Cons* rest;
};
Cons* makeCons( int car, Cons* cdr ) {
Cons* c = new Cons;
c->first = car;
c->rest = cdr;
return c;
}
void printList( Cons* c ) {
if (c == NULL)
cout << endl;
else {
cout << c->first << " ";
printList( c->rest );
}
}
int main() {
Cons* nums1, *nums2;
nums1 = new Cons;
nums1->first = 17;
nums1->rest = NULL;
nums2 = makeCons( 15, makeCons( 16, nums1 ) );
printList( nums2 );
}
- - - -
NOTE: our recursive idea that
A List is
- null, or
- makeCons( kar, kdr )
is not part of the language!
In fact, if a "null list" had been a structure
(maybe all lists keep track of their own length),
we'd have trouble distinguishing makeNulls from makeConss.
What is going on here?
A Cons* is a reference (signpost);
a Cons is the real structure.
(In Scheme you couldn't make this distinction;
in C you can, and you must be careful not to confuse them.)
Notice how discount actually changed the structure referred to;
compare this with a function taking an int.
Let's write allEven: Don't forget templates!
bool allEven( Cons* l ) {
if (l == NULL)
return true;
else
return (l->car % 2 == 0) && allEven( l->cdr );
}
You're not allowed to forget about program templates!
----
C structures: Under the hood
or,
The truth about splats and dots
Questions unanswered:
- how to pass two-d arrays?
- why does C make us use *, to get scheme semantics for structs?
Recall how we use structures in C to get Scheme behavior:
...(example from prev. lecture)
"ir->price" is shorthand for "(*ir).price"
What does "*" mean?
(a) In declarations:
"InvRec *x" means that *x is an InvRec, and x is a pointer-to-InvRec
(b) In executable statements:
"x" refers to the (value of the) pointer,
"*x" refers to the (value of the) int.
Pictures of memory, when you make a struct:
creating invRec, calling discount, makeInvRec.
Note that in calling "z = 0.9; discount( ir, z )",
any changes to "ir" do seem to be reflected, but changes to z aren't.
Why?
Because in JAM, when we call a function, the parameters are copied.
This is "call-by-value".
C lets you do smething Scheme didn't:
declare a structure, instead of a reference-to-structure.
(This complicates things; I suggest you only use pointers-to-structs.)
invRec ir2;
ir2->price = 99.99;
float z = 0.9;
discount2( ir2, z );
cout << ir2->price; // prints 99.99
Note that Scheme, and original C, has only call-by-value.
Because we can pass references by value, sometimes we effect changes.
This is a faux pass-by-reference; you can imagine a language
where changes to parameters are *really* modifying the calling-variable
(e.g., in discount2, modifying the second arg would change z.)
But we can also fake this, using references.
Some books call this pass-by-ref, but it's not really
(just having pass-by-ref can't
explain circular references, item in multiple lists, etc).
Uses of pass-by-ref: when you want to return multiple values w/o struct.
--------
dec.07 (mon)
Ask about: how many going to lab. How many have finals on sat,sun?
Calling functions in JAM:
Suppose you had sqrt written at 5000.
...input in register (or, agreed memory location)
... we could put the return address in a pre-designated spot
(perhaps even mem[5023], the return-instruction)
... trash some registers
... return value in a register
This could work okay (original fortran), except that...
no recursion allowed!
Need to remember a whole stack full of pending recursive calls...
use a "stack" (the adt of a scheme list).
----
apr.22 (wed.)
Vectors in C:
- vectors are represented as a poitner to the first element.
const int sz = 5;
int main() {
int data[sz];
data[2] = 17;
}
Draw memory diagrams of what happens in this.
Note that data[2] is translated to *(data+2).
While the latter is still valid C, DO NOT USE IT!
What about passing arrays?
void print( int vec[] ) {
for (int i = 0; i < sz; i++)
cout << vec[i];
cout << endl;
}
Draw memory diagrams of what happens when main calls print(data).
What if we were to assign to vec[2]?
Notice that it changes, just like when structure-references
are passed, even though we didn't use the "*" syntax at all. (an inconsistenC)
What about returning arrays?
Try:
// WRONG
int[] makeAndFillVec() {
int retVec[sz];
for (int i=0; i < sz; i++)
retVec[i] = 2*i;
return retVec;
}
int main() {
int data[];
data = makeAndFillVec();
print( data );
}
Well, first a syntax problem: "int x[]" isn't a valid
declaration; change them to "int* x" :-(
But there is a much more serious problem:
Draw memory diagrams.
When we leave makeAndFillVec, local memory goes away, can get re-used.
(Ex: data1 = makeAndFillVec(); data1[2]=17; data2 = makeAndFillVec();
You can see that data1[2] is no longer 17! data1 and data2 *happen*
to poitn to same location.)
Solution:
In makeAndFillVec, don't declare the array as a local variable
(never return address of a local variable).
Instead,
int* retVec;
retVec = new int[sz];
This way retVec (the poitner) is a local var, but the actual array
is long-lived, on the heap.
Talk about exam.
----
98.apr.25 (last day)
Exam bits:
-- If wanting to temporarily mark structures, just having
the references be local won't work. Remember, each call
to make-student creates one object. Write a function "clone" if you
want...(when a student contains references, what does cloning mean?)
-- minor: (if ... #t #f)
Where have we been?
Scheme -
define, lambda, if, zero?, 0, add1
computation as an extension of algebra
struct recursion -- mirror your input
generative recursion
accumulator recursion, loops
side-effects: set-struct-field!, set!, print, read
Assembly
Jam, C
In Jam, some opcodes are redundant. What would a minimal set be?
In fact, which is more powerful -- Scheme or JAM?
(why "car" and "cdr"?)
In 1930's, people trying to formalize "computation"
lambda calculus -- Church 1936
Turing Machine -- Turing 1936
recursive functions -- Go:del, Kleene 1936
deduction systems -- Post 1943
register machines (JAM) -- 1946
Church-Turing thesis: all notions of "computability" are the same!
Can we compute anything we like? No:
;; Loop forever.
(define (loop x)
(loop (add1 x)))
;; halt: program, input --> boolean
;; return #t if prog eventually stops given inp; #f otherwise.
;;
(define (halt prog inp) ...)
I claim we can't write this.
Proof by contradiction: Pretend we *could* write it,
and reach a contradition
(Assuming my broker wasn't lying, i have $1M in bank.)
Okay, supposing we *could* write halt in scheme. Then,
(define (twisted prog)
(if (halt prog prog)
(loop 17)
#t))
;; twisted: takes a program, and
;; loops forever if prog halts given itself as input;
;; returns if prog runs forever given itself as input.
Question: what is (twisted twisted)?
- Suppose it loops forever.
Then (by description of twisted), "twisted halts given itself as input".
- Suppose it returns:
Then (by description of twisted), "twisted loops given itself as input".
No matter what (twisted twisted) does, we have a contradiction;
our supposition that we could write "halt" must be wrong.
Where to go from here:
CS is *not* about programming. ("CS is no more about computers than
astronomy is about telescopes")
Comp212: more programming, and program design; object-oriented (java)
circuit design (elec 326); comp arch: comp/elec 320;
Compilers, OS.
networks, security.
applications: databases, graphics, ai, (robotics).
theory: comp280; comp481
(user-interfaces are usually given scant notice, yet are arguably the most
important feature of any program people will use.)
=============================================================
=============================================================
Other miscellaneous lectures, lectures fragements,
notes from previous years:
=============================================================
[ see handwritten notes matthias's last lecture; halting problem. ]
(why "car" and "cdr"?)
Why C is unsafe
- lets you walk off end of array
- can cast pointers
- pointer arithmetic lets you access memory directly !!
- too easy to erroneously return pointers to freed memory.
double sumSoFar;
int i;
double sumDataToSize() {
sumSoFar = 0;
Examples not used (lab has an example of loop-w/o-vector)
What is the sum of x^2/2! + x^4/4! + x^6/6! + ... + x^100/100!
That is, sum_i=0..100 x^i/i!
(define (cos x)
(lambda (x)
(begin
(set! sum-so-far 0)
(fori= 0 add2 (lambda (i) (> i 100))
(lambda (i) (set! sum-so-far (+ sum-so-far (/ (expt x i) (! i))))))
sum-so-far)))
(Of course, we could do this w/o set!.
Since we're going-by-two, it's not quite nat.recursion, though close.
Accumulator style also straightforward.
And we could write a fori= version which used these approaches
but still separated the control from the task-for-each-i.)
Compute the sum of a list of numbers:
(No, since we'd then want to translate lists into JAM)
(define (sum lyst)
(local [(define sum-so-far 0)
(define (find-answer)
(if (empty? lyst)
sum-so-far
(begin (set! sum-so-far (+ sum-so-far (first lyst)))
(set! lyst (rest lyst))
(find-answer)))))]
(find-answer)))
Well, actually, the imperative version would have a loop-structure,
to replace the "define find-answer" and recursive call.
<<<<
Note: there is nothing special about having destructive operations
as the body of the fori= loop; we could easily have a version which
returned a value (the index), which could get used recursively.
In fact, this would be like make-lists-fun, for generatvie recursion.
miss-and-cann:
(fori=-v.2 (list start-state)
all-legal-states-one-trip-later
contains-final-state?
(lambda (x) 'dummy))
[actually, "while" might be better for this??
(while (list start-state)
contains-final-state?
all-legal-states-one-trip-later)
]
However, we are stressing bodies that do set!, vector-set!
as an intro to imperative prog:
>>>>>
; Another exapmle: fill-vec!, using fori=.
(define (fill-vec! v n rule)
(fori= 0 n (lambda (i) (vector-set! v i (rule i)))))
; Yes, this could avoid passing in n, by using vector-length.
---------------------------------------------
opcodes; loops
Recall from the end of two lectures ago,
The JAM machine has a CPU, memory (a giant vector),
and registers R0-R9 general purpose, special register PC.
The four-stage step of JAM machine:
Repeatedly
(1) fetch the value mem[PC]
(2) increment PC
(3) decode the value as an instruction
(4) execute the instruction.
Okay, now we'll talk about some of the exact instructions.
Refer to the reference sheet.
There are a few general classes of instructions:
- arithmetic (only works on registers)
- memory (move between memory and registers)
- control (modify PC)
Let's take an example. Suppose in Scheme we have variables a,b,
and we wanted the equivalent of
(set! a (- a b))
;; a <-- a - b (Alternate notation)
For the JAM assembly version, we'll suppose that a is stored in
memory location 456, and b in location 789.
Hmmm, the only subtraction command is "Rx <-- Ry - Rz".
This means that we need to move a and b from memory into registers.
Aside:
When to count from zero instead of 1:
(My microwave, which goes for n+1 seconds)
- when counting continuous quantities:
distance after t seconds; height of a building
- from 1 with discrete quantities:
# of people in room, # of floors in a building
Note that there is sometimes conflict:
european ground floor=0. This is great in that floor-k is 10k feet above
ground (and you climb k flights);
however a building with k floors is 10(k+1) ft tall.
(Are you more interested in floors or ceilings?)
Chapter 0 of a book -- only if it contains background material.
(What if there is background stat + background econ?)
When to use quotes, in English:
My name is mud. (My band's name is hard to pronounce.)
She asked how to play kazoo; I replied quietly.
Love is a four-letter word.
What is the center of gravity?
Use of quotes:
Supresses matching a meaning(value) with the word(placeholder).
(Also: to indicate a term defn, or re-defn, or abuse/novel-use,
sarcasm, even quoting:
A cat's "thumb" is on its forearm.
When writing, look at each use, is it justified?
NOT: "thanks", the "brilliant" decision...
Names automatically considered quoted: New York.)
", when prepended to an unquoted copy of itself, becomes grammatical."
Examples of poor interface design:
- most-used/important buttons should be biggest.
(nuclear power panels w/ rows of buttons; keg handles.)
(CD player: play. Display should default to time-left.)
- course-eval web page: use colors, not numbers, and fixed column heads.
Loops: first write map-vector
The body, given i,
mar.30 JAM II: opcodes; loops
Recall from the end of two lectures ago,
The JAM machine has a CPU, memory (a giant vector),
and registers R0-R9 general purpose, special register PC.
The four-stage step of JAM machine:
Repeatedly
(1) fetch the value mem[PC]
(2) increment PC
(3) decode the value as an instruction
(4) execute the instruction.
Okay, now we'll talk about some of the exact instructions.
Refer to the reference sheet.
There are a few general classes of instructions:
- arithmetic (only works on registers)
- memory (move between memory and registers)
- control (modify PC)
Let's take an example. Suppose in Scheme we have variables a,b,
and we wanted the equivalent of
(set! a (- a b))
;; a <-- a - b (Alternate notation)
For the JAM assembly version, we'll suppose that a is stored in
memory location 456, and b in location 789.
Hmmm, the only subtraction command is "Rx <-- Ry - Rz".
This means that we need to move a and b from memory into registers.
;; R0 <-- mem[456]. A two-step process:
(ldi 1 456) ; R1 <-- 456
(ld 0 1) ; R0 <-- mem[R1]
;; R5 <-- mem[789]. The same two-step.
(ldi 6 789)
(ld 5 6)
;; Now we can subtract! Put answer in R2.
(sub 2 5 0) ; R2 <-- R5 - R0.
;; We did "a-b" (answer in R2), so now "a <-- R2",
;; i.e. "mem[456] <-- R2". Looking at the store command "st",
;; we need to have the value 456 sitting in a register. Is that so?
;; Fortuitously, yes.
(st 2 1) ; mem[R1] <-- R2.
(halt)
So this is the program. Now we need to put it into memory,
so that the JAM machines' 4-step program can get to it.
We have seven instructions; we'll place those in, say,
mem[4], mem[5], ..., mem[10].
But it turns out, memory can only hold numbers! We must
refer to the sheet for the encoding.
Consider "(ldi 1 456)". Reading of the sheet, we see that
this is encoded as "+00045619"; store this value into mem[4]
using the machine inspector.
Similarly, "ld 0 1" is encoded as "??1?1060", eg 101060.
Question: What is "(sub 2 5 0)" encoded as?
Note how you have to use the insepector to load these
numbers (instructions) into mem locations 4..10.
Then, you must set the PC to 4, and execute.
----
apr.01 Scheme to Jam to C
lab: Jam, C intro
hw: Jam loops, simple C, C loops
An Overhead slide, with the program from last time:
;;; (set! a (- a b))
;;; a <-- a - b (Alternate notation)
;; We presume a is stored in memory location 456, and b in location 789.
locat'n: Value ; Decoded ; Comment.
mem[ 4]: 45619 ; (ldi 1 456) ; R1 <-- 456 Two-step for R0<--mem[456]:
mem[ 5]: 101060 ; (ld 0 1) ; R0 <-- mem[R1]
mem[ 6]: 78969 ; (ldi 6 789) ; R6 <-- 789 Two-step for R5<--mem[789]:
mem[ 7]: 106560 ; (ld 5 6) ; R5 <-- mem[R6]
mem[ 8]: 05220 ; (sub 2 5 0) ; R2 <-- R5 - R0. Subtract; put answer in R2.
mem[ 9]: 101270 ; (st 2 1) ; mem[R1] <-- R2. R1 is still a's location.
mem[10]: 321000 ; (halt)
Note with ld, st: in "(ld 2 1)", R2 is the register which gets the value;
R1 is the register which contains the *address* of the value.
The actual values are "machine code".
THe decoded instructions are "assembly code".
It's tedious writing in machine code; much nicer to write in assembly,
and then have a program to translate it.
That's it first worked: somebody wrote an assembler, in machine code!
Thereafter, you write in assembly, and give your english-like
program text to the assembler, which translates it.
(Actually, they probably wrote it in assembler, and then hand-evaluated
to assemble their assembler into machine code.)
We'll do a similar thing in lab: You'll write in C, and then an
"compiler" will translate your C code to assembly code, which will
then be assembled into machine code.
(In drScheme, every time you hit "execute", this compiling happens.)
We will see C soon, and in lab how to do the compiling (i.e. how
to click the execute button.)
C is "high-level assembly": it allows for variable names,
for-loops, function calls.
Here is an example which involves a loop.
We want to store the values 0...49 in locations 100...149.
(define vec (make-vector 50))
(define (fill i)
(if (< i (vector-length vec))
(begin (vector-set! vec i i)
(fill (add1 i)))
(void)))
In JAM-assembly:
- Approach 1: have veci iterate 100,101,102,...149, and access mem[vec].
- Approach 2: set vec = 100; have i iterate 0,1,2,3,...,49, and store
into mem[vec + i]
We'll take approach 2; it parallels the Scheme (and C) approach.
;; We'll use memory locations 100 through 150 to store "vec".
;; First think about what placeholders we need.
;R0 i <-- 0
;R1 len <-- 50
;R2 vec <-- 100
;R3 vec + i
;R4 uno <-- 1
;R5 diff: ??
(ldi 0 0)
(ldi 1 50)
(ldi 2 100)
(ldi 4 1)
loop: (sub 5 1 0)
... ; is i < len ?
(add 3 2 0) ; R3 <-- vec + i
(st 0 3)
(add 0 0 4) ; i <-- i + 1
(jmpi loop)
done: (halt)
Now go back and fill in the skipped line: blez 5 done
Eleven instructions. Put them in memory 90..100.
It works, but only because of luck!
What if we set vec[i] to be i+1970?
Lesson: be very careful! (Some machines have two memories -- prog & data)
----
apr.03
Exercise on your own:
get rid of computing vec+i, and instead use the stx instruction.
(stx 0 2 0) ;; mem[R2+R0] <-- R0
Cf Scheme and C:
C has the contracts built-in.
Scheme, natural Recursion
(define size 50)
(define nums (build-vector size (lambda (i) 17.3)))
;; max: natNum --> float
;; Given N, find the largest entry in nums[0]..nums[N].
;; Note that since N is 0, this is always a non-empty set.
;; The natural recursion version.
;;
(define (max N)
(if (zero? N)
(vector-ref nums 0)
(local [(define max-of-rest (max (sub1 N)))
(define nth (vector-ref nums N))]
(if (> max-of-rest nth)
max-of-rest
nth))))
(max (sub1 size))
C, natural Recursion
// max, the natural-recursion version.
//
#include
const int size = 50;
double nums[size];
// max: Return the largest entry in nums[0]..nums[N].
//
double max( int N ) {
if (N==0)
return nums[0];
else {
int maxOfRest = max( N-1 );
int nth = nums[N];
if ( maxOfRest > nth )
return maxOfRest;
else
return nth;
}
}
int main() {
cout << max( size-1 );
return 0;
}
// Note: you must call a function "fill-up-nums()" to
// initialize the array.
Scheme, accumulator version
(define size 50)
(define nums (make-vector 50 17))
(define (max N max-so-far)
(if (>= N size)
max-so-far
(if (> nums[N] max-so-far)
(max (add1 N) nums[N])
(max (add1 N) max-so-far))))
(max 1 nums[0])
C, accumulator version
#include
const int size = 50;
int nums[size];
int max( int N, int maxSoFar ) {
if (N >= size)
return maxSoFar;
else if (nums[N] > maxSoFar)
return max( N+1, nums[N] );
else
return max( N+1, maxSoFar );
}
int main() {
cout << max( 1, nums[0] );
return 0;
}
Variables:
- (define x 3) int x; // declare
x = 3; // assign
// OR
int x = 3; // initialize
Compare with the tail-recursion of Scheme:
The tail-recursion changes the argument each time through.
The assembly version assigns to i each time through.
Tail-recursion can be implemented as a loop + (re)assign parameters!
Exercise:
Modify this, so that you compute the sum of
----
(define vec (make-vector 50))
(fori= 0
(lambda (i) (< i (vector-length vec)))
add1
(lambda (i) (vector-set! vec i i)))
----
const int size = 50;
int vec[] = new int[size];
int i;
for ( i = 0; i < size; i = i + 1 ) {
vec[i] = i;
}
; Using the fori= construct:
;(fori= 0
; (index-checker vec)
; add1
; (lambda (i) (vector-set! vec i i)))
apr.03 advanced Jam: stack
apr.06 implementing Jam
apr.08 exam2 review
hw e.c.:
lab: optional: arithmetic
hw: assign project
apr.13 (catchup)
apr.15 multi-dim arrays scheme, C
lab: C
apr.17 object-oriented I
apr.20 object-oriented II
lab: timing
apr.22 halting prob
apr.24 summary
Labs: arithmetic imprecision;
timing qsort, msort, isort;
optional topics: eval, program-as-data, shcme-in-scheme
max:
scheme-accum
C-accum
scheme-for
C-for
Jam-for
The Scheme-accumulator version of max
Scheme, accumulator version
;; max: int, double --> double
;; Return the largest value out of vec[i]...vec[size-1],max-so-far.
;; N.B. It is an error if vec does not have at least one element.
;;
(define (max i max-so-far)
(if (>= i size)
max-so-far
(if (< max-so-far (vector-ref vec i))
(max (add1 i) (vector-ref vec i))
(max (add1 i) max-so-far))))
(max 1 (vector-ref vec 0))
C, accumulator version
#include
const int size = 50;
int nums[size];
int max( int N, int maxSoFar ) {
if (N >= size)
return maxSoFar;
else if (nums[N] > maxSoFar)
return max( N+1, nums[N] );
else
return max( N+1, maxSoFar );
}
int main() {
cout << max( 1, nums[0] );
return 0;
}
C, for-loop version
// max-for.cc
// Compile this with "g++ -Wall max-for.cc".
#include
const int size = 50;
double vec[size];
// max
// The "for" version in C.
//
double max( int i, double maxSoFar ) {
if (i >= size) {
return maxSoFar;
}
else if (maxSoFar < vec[i]) {
return max( i+1, vec[i] );
}
else {
return max( i+1, maxSoFar );
}
// N.B. In this case, the curly-bracces were optional,
// since each if/else body had only one statement.
}
int main() {
cout << max( 1, vec[0] );
return 0;
}
;; max: . --> double
;; The Scheme fori= version.
;; Return the largest value out of vec[0]...vec[size-1]
;; N.B. It is an error if vec does not have at least one element.
;;
(define (max)
(local [(define max-so-far (vector-ref vec 0))]
(begin
(fori= 1 ; start
(lambda (i) (>= i size)) ; stop?
add1 ; next
(lambda (i) ; body!
(if (< max-so-far (vector-ref vec i))
(set! max-so-far (vector-ref vec i))
(void))))
max-so-far ; This is the 2nd stmt in the begin.
)))
// The C-for version of max.
// N.B. It is an error if vec does not have at least one element.
//
double max() {
double maxSoFar = vec[0];
int i;
for ( i = 1; i < size; i = i + 1 ) {
if (maxSoFar < vec[i]) {
maxSoFar = vec[i];
}
}
return maxSoFar;
}
----
apr.08: tail-recursion to loops in JAM.
JAM:
vec <-- 100
i
uno <-- 1
diff
msf <-- ldx vec 0
i <-- 1
diff <-- size - i
blez diff end
ldx veci vec i
diff <-- veci - msf
blez diff endfor
msf <-- veci
endFor:
i <-- i + 1
jmpi startFor
end
Notice now, how tail-recurion, in JAM, becomes
"change the arguments (stored in registers), and do a jump".
This is quick and easy.
To think about:
How would you translate function-call to JAM?
Imagine I had a subroutine that location 5000, which
took the sqrt of R0, and put the answer in R1 (trashing the
other registers). How would you call it? What would happen
at end of that routine?
Would this work for recursive functions?
--------