程序代写代做代考 data structure Java interpreter CSSE 304 Day 9

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

Related Posts