Equality, Imperative programming
A comparison of define, set!, and set-struct-field!:
So let's make some sample structures:
(define-struct person (birthyear haircolor annoying activity))
(define mary-kate-olsen (make-person 1986 'blonde true 'smiling))
(define ashley-olsen (make-person 1986 'blonde true 'smiling))
(define michelle-tanner1 mary-kate-olsen)
(define michelle-tanner2 ashley-olsen)
You'll see why we're using the ultra-annoying Olsen twins as an example.
(Heh, heh. Evil grin.)
In case you don't know, they are the child stars who each played
Michelle Tanner in an inanely stupid TV show "Full House".
Clearly, your expectations are that
Q: What does the following do? First, step through the evaluation in your head, then confirm it with DrScheme.
(define (kill-person! person)
(set-person-activity! person 'dead)
(set-person-annoying! person false))
(kill-person! ashley-olsen)
(person-activity michelle-tanner2) = ?
(person-activity mary-kate-olsen) = ?
eq? tests whether two things are really the same thing, while equal? tests whether they look alike. Q:
(eq? mary-kate-olsen michelle-tanner1) = ?
(eq? mary-kate-olsen ashley-olsen) = ?
(equal? mary-kate-olsen michelle-tanner1) = ?
(equal? mary-kate-olsen ashley-olsen) = ?
Cons-cells are just predefined kinds of structures, using a naming convention doesn't quite correspond to user-defined structures. They use the special forms set-car! and set-cdr!. (car and cdr are the traditional names for first and rest, respectively. However, the implementors of DrScheme forgot to define the names set-first! and set-rest!.) Remember that while each cons-cell is a structure, a list is a bunch of cons-cells.
To do: Figure out what the following examples should do. Confirm your answers using DrScheme.
(define list1 (list 1 3 5 7))
(define list2 list1)
(define list3 (cdr list1))
(eq? list1 list2) = ?
(equal? list1 list2) = ?
(eq? list1 (cons 1 list3)) = ?
(equal? list1 (cons 1 list3)) = ?
(set-car! list1 10) ; the car/first should be a list element
list1 = ?
list2 = ?
list3 = ?
(eq? list1 list2) = ?
(equal? list1 list2) = ?
(eq? list1 (cons 10 list3)) = ?
(equal? list1 (cons 10 list3)) = ?
(set-cdr! (cdr list1) (list 2 4)) ; the cdr/rest should be a list
list1 = ?
list2 = ?
list3 = ?
(eq? list1 list2) = ?
(equal? list1 list2) = ?
(eq? list1 (cons 10 list3)) = ?
(equal? list1 (cons 10 list3)) = ?
(define alist (list 1 3 5 7))
(set-cdr! (cdr alist) alist)
alist = ?
(cdr alist) = ?
Note: The shared output you'll see in the last example is basically the same as local.
To do: Figure out what the following examples should do. Confirm your answers using DrScheme.
(define list1 (list 1 2))
(define list2 (list 1 2))
(eq? list1 list2) = ?
(equal? list1 list2) = ?
(set! list1 list2)
(eq? list1 list2) = ?
(equal? list1 list2) = ?
(set! list1 (list 1 2))
(eq? list1 list2) = ?
(equal? list1 list2) = ?
(define num1 12)
(define num2 12)
(eq? num1 num2) = ?
(equal? num1 num2) = ?
(set! num1 num2)
(eq? num1 num2) = ?
(equal? num1 num2) = ?
(set! num1 12)
(eq? num1 num2) = ?
(equal? num1 num2) = ?
For the curious...
What if we use a really big number like
12000000000000000000 instead of 12?
In reality, eq? tests equality of simple non-compound values, such as numbers and symbols and also references, which are now considered values.
A reference is really just the same thing as a location, pointer, or memory address. These latter terms have more low-level connotations, dependent on the machine model (which we'll describe later in this course).
Scheme, Java, and other languages use references a lot, but hide them from the programmer. Much of the problem of writing Scheme-like functions in languages such as C is that, in those languages, the programmer is expected to deal with references explicitly.
This course has dealt primarily with a style of programming known as functional programming, or to also include the previous couple weeks, mostly-functional programming. Another style is imperative programming, which focuses primarily on side-effects (e.g., set! and set-struct-field!), rather than passing arguments. Here, we will begin to see the relation between the two.
We start with a simple structurally recursive program:
(define (sum-list alon)
(cond [(empty? alon) 0]
[(cons? alon) (+ (first alon) (sum-list (rest alon)))]))
We can then obtain the accumulator version:
(define (sum-list alon)
(local [(define (sum-list-acc the-lon accum)
(cond [(empty? the-lon) accum]
[(cons? the-lon) (sum-list-acc (rest the-lon)
(+ (first the-lon)
accum))]))]
(sum-list-acc alon 0)))
As you've seen, sometimes this step is difficult.
We'll rewrite this to avoid passing arguments in the helper function and, instead, change only local variables. This is a straightforward syntactic translation:
(define (sum-list alon)
(local [(define accum 0)
(define the-lon alon)
(define (sum-list!)
(cond [(empty? the-lon) accum]
[(cons? the-lon) (begin
(set! accum
(+ (first the-lon) accum))
(set! the-lon
(rest the-lon))
(sum-list!))]))]
(sum-list!)))
Q: Does the order of the two set!s matter? Why or why not?
Lastly, we can rewrite this as a loop, here using one of Scheme's looping constructs. This is a straightforward syntactic translation:
(define (sum-list alon)
(local [(define accum 0)]
(loop-until alon
empty?
rest
(lambda (the-lon)
(set! accum (+ (first the-lon) accum))))
accum))
To do: Play around with loop-until. It takes four arguments: a starting value to loop on, a test for what value(s) to stop on, a function to get the next loop value from the current one, and a function to evaluate on each loop iteration.
Most programming languages have a construct similar to this, except with a test for what value(s) to continue looping (i.e., the opposite of what's used here). It is typically called a while loop.
Which is best?
To do: Write imperative versions of