CSSE 304 Day 14
More define-syntax examples Re-introduction to datatypes Standard aggregate datatypes define-datatype
(Parsing lambda-calculus expressions)
lexical address hint
(lexical-address
‘((lambda (x y)
(((lambda (z)
(lambda (w y)
(+ x z w y)))
(list w x y z))
(+ x y z)))
(y z)))
Recursive helper should take an additional argument, a “lexical environment”
1
Live coding time
• my-let • my-if
• ++
• ++-post • my-and • for loop
Definition
Basic and derived operations
Example: Non-negative integers Implementation strategies
Standard Datatypes – arrays and records Variant records
EoPL’s Scheme define-datatype Parsing lambda-calculus expressions
DATATYPES
2
data • interpretation
• bits
datatype
• What is an (abstract) data type?
– Interface (how the user sees it)
– Representation (data structure used)
– Implementation (provide the interface based on the representation)
• In EoPL notation, x means “the current representation of x”.
• Representative example: non-negative integers. n means the representation of the integer n.
3
Interface for “non-negative integer” datatype
• (zero) = 0
• (iszero? n ) = #t if n is the representation of zero,
#f otherwise.
• (succ n) = n+1 (n0)
• (pred n+1) = n (n0)
These operations define the datatype.
Other operations can be derived from them.
Derived op example (representation-independent code):
(define add
(lambda (m n)
(if (iszero? n)
m
Next we will look at some implementations of this ADT.
(add (succ m) (pred n)))))
Representation 1: Unary representation of non-negative integers
• 0 =() ;theemptylist • n+1=(cons #t n)
• Define the integer operations. – zero iszero? succ pred
• There is a (slightly) more efficient implementation of add (than the one from the last slide) if we base it on this representation instead of the ADT.
– Can you see what it is?
– That implementation is representation-dependent.
(zero) = 0
(iszero? n ) = #t if n is the
representation of zero, #f otherwise.
(succ n) = n+1 (n0) (pred n+1) = n (n0)
4
Other representations of non- negative integers
• There are several online only slides that present other possible representations of non-negative integers.
• The main point is that for any ADT specification, there can be many different representations/implementations.
Representation 2: Another representation of non-negative integers
• Representeachnumberbyabinarystring
Base Cases: 0 = “0” 1 = “1”
Other case: If n>0, there are unique integers q and r such that r is 0 or 1, and n = 2*q + r
Then n is the string concatenation of q with r .
• Example 13 = “1101”
• succandpredaremorecomplexthanintheunary representation ( easier if bits in number are reversed)
• but add is faster than in the unary representation! Can you write it?
5
Representation 3: Another representation of non-negative integers
• RepresenteachnumberbythecorrespondingScheme integer
0 = 0
iszero? = zero?
succ = (lambda (x) (+ x 1)) pred = (lambda (x) (- x 1))
• Amoreefficient(representation-dependent) implementation of add
(define add +)
Representation 4: Another representation of non-negative integers
Represent numbers by lambda calculus expressions:
0 = (lambda (x) (lambda (y) y))
1 = (lambda (x) (lambda (y)(x y)))
2 = (lambda (x) (lambda (y)(x (x y)))) 3 = (lambda (x) (lambda (y)(x (x (x y)))))
succ = (lambda (x) (lambda (y) (lambda (z) (y ((x y) z)))))
We will skip the details of how this works.
isZero? = (lambda (k) (k ((true false) true))
where true is (lambda (x) (lambda (y) x))
and false is (lambda (x) (lambda (y) y)) . We will not look at the details of this today.
6
Representations 5 and 6: Two more representations of non-negative integers
• Bignums
• Diff-trees
• See Pages 34-35 of EoPL . and
• In the past I have assigned programming problems related to these.
Not required this term, but in case you are interested, there is a link to the old assignment on the schedule page.
Interlude
• From rec.humor.funny (circa 1995):
• We were discussing how to pronounce certain
computer names.
• Is “Linux” pronounced “Lin-ucks” or “Lie-nucks”?
• And is the editor “vi” called “veye” or “Vee-Eye”?
• So we tapped them into our friendly Mac, and asked its verdict on pronunciation:
• “Linux” is pronounced “Lin-uks”.
• “vi” is pronounced “Six”.
7