CSSE 304 Day 9
Exam preview
“OOP” in Scheme?
Preview of an A8 problem Miscellaneous examples and exercises
Exam 1: Tuesday, Sept 24 7:00-9:30 PM G 308, 310, 315, 317
Exam Resources allowed:
Written part: writing implement (pencil or pen).
Computer part: TSPL, CSUG, EoPL, EOPL-1, course web pages, an editor and a Scheme interpreter on your laptop, notes/code that you write before the exam, no other sources (such as code from previous terms or other students).
No other electronic devices, headphones, ear buds (unless you bring me a written accommodation).
Exam material: through Day 9 class and A8 plus reading assignments through day 9. If you are allowed extra time, please tell me today.
List of built-in procedures and syntax to know for written part of the exam is linked from Day 12 of schedule page (and on the next slide).
Also some old exams are linked from Day 12.
1
Procedures & syntax: written part of exam
Did I miss any?
2
BST? solution
group-by-n solution
3
http://community.schemewiki.org/?object-oriented-programming
Constructing objects “fields”
“methods”
method arguments
HOW MIGHT WE DO OOP IN SCHEME, USING ONLY THINGS THAT WE HAVE SEEN SO FAR?
“OO Programming” in Scheme
We need to find a way to encapsulate “fields” and “methods”, so that fields can only be accessed/changed by using the methods.
We can represent an object by a _____.
“Fields” are persistent local variables.
A “method name” is the first argument to the “object” procedure
“method arguments” are the other arguments to the procedure.
4
> (define s1 (make-stack))
> (define s2 (make-stack))
> (s1 ‘push ‘a)
> (s2 ‘push (s1 ‘pop)) > (s1 ’empty?)
#t
> (s2 ‘pop)
a
> (s2 ‘pop)
z
> (s2 ‘pop)
Exception in car: () is not a pair
>
> (s2 ‘push ‘z)
> (s1 ‘push ‘b)
> (s1 ‘pop) b
(s1 ’empty?)
#f
Transcript for the use of the stack “class”
A better error message would be a nice improvement here
Encapsulation: Creating “objects” in a mostly functional language
The car of the stk list contains the top of the stack
What is the
This code
problem with
contains a
this code?
subtle error.
Can you see
How to fix it?
what it is?
5
Encapsulation: Creating “objects” in a mostly functional language
Reverse these two code lines
The car of the stk list contains the top of the stack
What is the
This code
problem with
contains a
this code?
subtle error.
Can you see
How to fix it?
what it is?
HW 8 Preview
You will implement another class, slist‐leaf‐ iterator. Your procedure, given an s-list s, will make an iterator “object” that iterates s.
An easy way to implement this? Good idea?
6
HW 8 Preview
You will use this stack “class” implementation as a helper procedure in your implementation of another class, slist‐ leaf‐iterator. Your procedure, make‐slist‐leaf‐ iterator, given an s-list s, will make an iterator “object” for s.
Why is the “easy” approach from the last slide inefficient? Think of an slist with tens of thousands of symbols.
In the HW problem, your iterator procedures are not allowed to traverse more of the tree than is required for the ‘next calls that actually happen.
That’s where a stack object comes in.
Can be similar to the preorder iterator in Weiss*, Chapter 18.
* Data Structures and Problem Solving Using Java
But the code will be simpler than Weiss’s because Scheme notation is simpler.
Interlude
7
COMPOSE AND CASE-LAMBDA
Compose With Any
Number of Arguments
compose, which creates the composition
of any number of one-argument procedures.
> (define caddddddr
(compose car cdr cdr cdr cdr cdr cdr))
> (define id (compose))
> (caddddddr ‘(1 2 3 4 5 6 7 8))
7
> (id ‘(a b c))
(a b c)
8
Simple compose Solution
(define compose
(lambda fn-list
(lambda (x)
(if (null? fn-list)
x
((car fn-list)
((apply compose (cdr fn-list))
x))))))
Another way of defining variable-arity procedures (by example)
CASE-LAMBDA
9
Scheme’s case-lambda
A simpler way to define a procedure that takes a variable number of arguments:
(define fact
(case-lambda
[(n) (fact n 1)]
[(n acc) (if (zero? n)
acc
(fact (- n 1)
(* n acc)))]))
Another case-lambda example
(define substring1
(case-lambda
[(s)
(substring1 s 0)]
[(s start)
(substring s
start
(string-length s))]
[(s start end)
(substring s start end)]))
10
compose 2-3 using case-lambda
(define compose ; two or three arg version (case-lambda ; of compose from A6
[(f g) (lambda (x) (f (g x)))]
[(f g h) (lambda (x) (f (g (h x))))]))
Try it:
> ((compose car cdr cdr) ‘(1 2 3 4))
3
> ((compose car cdr cdr cdr) ‘(1 2 3 4))
Error: incorrect number of arguments to #
Type (debug) to enter the debugger.
compose using case- lambda
Full version of compose
takes any number of arguments
(define compose
(case-lambda
[() (lambda (x) x)]
[(first . rest)
(lambda (x)
(first ((apply compose rest) x)))]))
11
compose using case- lambda
Full version of compose
(takes any number of
arguments):
(define compose
(case-lambda
[() (lambda (x) x)]
[(first . rest)
(lambda (x)
(first ((apply compose rest) x)))]))
To slightly increase the efficiency, we can add a new case. Place it between the current first and second cases.
[(single-arg) single-arg]
Two Approaches to
compose
(define compose1 1st version (case-lambda
[() (lambda (x) x)]
[(first . rest)
(let ([composed-fns (apply compose1 rest)]) (lambda (x)
(first (composed-fns x))))]))
Compared to
(define compose2 2nd version (case-lambda
[() (lambda (x) x)]
[(first . rest)
(lambda (x)
(first ((apply compose2 rest) x)))]))
Can you determine which one is better and why?
12
Experiment with 2nd compose
> (trace compose2)
(compose2)
> (define cadddr (compose2 car cdr cddr)) |(compose2 #
|#
|(compose2 #
|#
|#
What is the problem here?
(define compose2
(case-lambda
[() (lambda (x) x)]
[(first . rest)
(lambda (x)
(first ((apply compose2 rest)
x)))]))
Experiment with the 1st compose
> (trace compose1)
(compose1)
> (define cadddr (compose1 car cdr cddr)) |(compose1 #
| (compose1 #
| |(compose1 #
| | #
4
Why is
this better?
(define compose1
(case-lambda
[() (lambda (x) x)]
[(first . rest)
(let ([composed-fns
(apply compose1 rest)])
(lambda (x)
(first (composed-fns x))))]))
13