CSSE 304 Day 15
Aggregate datatypes define-datatype
Parsing lambda-calculus expressions Lambda-calculus and combinators
Prelude:Creating Wicked Students
• Thisisatitleofa2018bookbyPaulHanstedtthatthe Faculty Book Clubs on campus discussed Winter 2018-19.
• FromPage41:
– If we want to create students who can go off on their own and respond thoughtfully to wicked problems, the best way to do that is to give them wicked problems over and over and over again and ask students to solve them.
– Of course we need to be in the room part of the time. We need to make sure they have the resources needed to solve them, to occasionally ask questions that will get them thinking in a different direction, or to give them tips when they’re just plain stuck and their frustration is overriding their ability to think clearly.
1
Arrays
Records (a.k.a. structs)
Union Types
Union types in Scheme via define-datatype
AGGREGATE DATATYPES
Aggregate data types (arrays)
• An aggregate type can contain values of (possibly) other types
• aggregate type example: array – Allocated consecutively
– Elements accessed by position
• In many languages (not Scheme vectors), an array must be homogeneous
– All elements of the array must be of the same type
– Is that true in Java?
• Elements are accessed by position
2
Aggregate data types (records)
• Another aggregate type is the record type. This allows heterogeneous types for the elements, which are called fields
– Fields are accessed by name.
• In C, record types are called structs
• In Java, we create a new record type by declaring a ___________
• The R6RS standard has define-record-type.
• We will instead use define-datatype, as in EoPL
Aggregate types (unions) • Anotheraggregatetype:union
– An element of a union type contains one type chosen from among several specified types (variants)
– Usually those variants are record types
– Typically, a union type includes a tag field that indicates which variant a particular datum belongs to.
• Thisiscalledadiscriminateduniontype.
• Cuniontypesarecalled__________.
• Pascal union types are called variant records
• InJava,weimplementtheunionideavia__________
http://en.wikipedia.org/wiki/Union_(computer_science)
Primarily a description of unions in C
3
DEFINING VARIANT RECORD DATATYPES IN SCHEME
define-datatype
• define-datatype is a way of adding variant record types to Scheme
• Provided by the authors of EoPL
• Implemented as a syntactic extension
(using define-syntax).
• Instructions for getting set up to use define- datatype:
– Next slide.
4
Use define-datatype in your code
• Putchez‐init.ss(linkedfromtoday’s resources on schedule page) in the same folder as your code.
• Begin your code with (load “chez‐init.ss”)
• When you upload to the PLC server, you do not need to upload the chez‐init.ss file.
– The server loads that file automatically before it runs your code, and it ignores your
(load “chez‐init.ss”) code.
Use a bintree datatype object
(define-datatype bintree bintree? [leaf-node
(datum number?)]
[interior-node
(key symbol?)
(left bintree?)
(right bintree?)])
>(define leaf-sum
(lambda (tree)
cases is new syntax, defined in chez-init.ss (it is not the same as case)
(cases bintree tree
[leaf-node (datum) datum]
[interior-node (key left right)
(+ (leaf-sum left)
(leaf-sum right))])))
5
Parse: From list to bintree
Parsing the list form of a binary tree
(define t2 (list->bintree
‘(a(b12)(c(d 34)5)))) >(define list->bintree
(lambda (t)
(cond
[(number? t)
(leaf-node t)]
[(symbol? (car t))
(interior-node
(car t)
(list->bintree (cadr t))
(list->bintree (caddr t)))]
Given the list representation of a binary tree, produce a bintree datatype structure
[else (eopl:error ‘list->bintree
“improper data format”)]))
define-datatype automatically makes a constructor for each variant
define-datatype example
Inorder traversal of interior nodes of a binary tree
>(define inorder (lambda (tree)
(cases bintree tree ; let’s write it
(define-datatype bintree bintree?
[leaf-node
(datum number?)]
[interior-node
(key symbol?)
(left bintree?)
(right bintree?)])
6
s-list datatype (for A11a)
(define-datatype symbol-exp symbol-exp?
[symbol-symbol-exp
(data symbol?)]
[s-list-symbol-exp
(data s-list?)])
(define-datatype s-list s-list?
[an-s-list
What does the type of list-of have to be?
(data (list-of symbol-exp?))])
(define list-of ; defined in chez-init.ss
(lambda (pred)
(lambda (val)
(or (null? val)
(and (pair? val)
(pred (car val))
((list-of pred) (cdr val)))))))
“I doubt that we’ll get through this part today,” Tom schemed parenthetically.
A DATATYPE
FOR PROGRAM CODE
7
Programs as data
• A program in any language really is data – to be interpreted by …
• Scheme makes the relationship more explicit.
– Same syntax for programs and data
– eval (which you are not allowed to use in your interpreter )
Interpreter project solution – not!
(let loop ()
(display “‐‐>”)
(let* ([exp (read)]
[val (eval exp)])
(pretty‐print val)
(loop)))
datatype for λ-calculus expressions
(define-datatype expression
expression?
[var-exp
(id symbol?)]
[lambda-exp
(id symbol?)
(body expression?)]
[app-exp
(rator expression?)
(rand expression?)])
Let’s add set!,
multiple rands. You’ll add others in A11b
I use slightly different names than the textbook, to be consistent with the homework documents and files.
You will enhance this type to include other expressions (such as multi-arg, multi-body lambda, if, etc)
8
concrete syntax
parser
(app-exp
(lambda-exp
(x) ((if-exp
(var-exp x)
(var-exp y)
(var-exp z))
(var-exp x))
((app-exp
(lambda-exp
(y e)
((app-exp
(var-exp +)
Two parens because a lambda can have more than one body
concrete vs. abstract syntax
(parse-exp
‘((lambda (x)
(if x y z) x)
((lambda (y e)
(+ e 3))
2)))
abstract syntax
((var-exp e)
(lit-exp 3)))))
((lit-exp 2)))))
Parse lambda-calculus Expressions
I.e., translate concrete syntax to abstract syntax
(define parse-exp
(lambda (datum)
(cond
[(symbol? datum) (var-exp datum)] [(pair? datum)
(cond
[(eqv? (car datum) ‘lambda)
(lambda-exp (caadr datum)
(parse-exp (caddr datum)))]
[else
(app-exp (parse-exp (car datum))
(parse-exp (cadr datum)))])] [else (eopl:error ‘parse-exp
“Invalid concrete syntax ~s” datum)])))
You will add several other cases (if, etc.)
Let’s add set!,
You’ll add others in A11b
9
Using Parsed Lambda-Calculus Expressions
(define unparse-exp
(lambda (exp)
(cases expression exp
[var-exp (id) id]
[lambda-exp (id body)
(list ‘lambda (list id)
(unparse-exp body))]
[app-exp (rator rand)
(list (unparse-exp rator)
(unparse-exp rand)
)])))
Note that
unparse-exp
is simpler than parse-exp. Why?
About the parse problem in A11
• Add additional features to the parseable language – and modify the code for the basic features
• Add error checking.
– Important: To report an error:
(eopl:error ‘parse-exp “bad let*: ~s” exp)
• Figuring out all of the possible errors to check for is a major part of this assignment.
– Be sure to plan time for it.
In order for the grading program to recognize your error reports, you must use ‘parse-exp as the first argument to eopl:error
10
How I will test your parse
program
1. Test some cases that should return an error
to make sure that your code actually detects the error (and reports it according to the previous slide)
2. Test-cases that call
(unparse-exp (parse-exp ‘some-legal-expression))
a. to see if you return the original expression
3. If you get zero points from the PLC server on either 1 or 2, you will also earn zero on the other part .
occurs-free? for parsed expressions
(define occurs-free?
(lambda (var exp)
(cases expression exp
[var-exp (id) (eqv? id var)]
[lambda-exp (id body)
(and (not (eqv? id var))
(occurs-free? var body))]
[app-exp (rator rand)
(or (occurs-free? var rator)
)))
(occurs-free? var rand))]
11
Day 16 Prelude
Tom Swifties (most from Wikipedia):
“Who left the toilet seat down?” Tom asked peevishly.
“I’ll never again put my arm in a lion’s mouth,” Tom said off-handedly.
“Can I go looking for the Holy Grail again?” Tom requested.
“I unclogged the drain with a vacuum cleaner,” Tom said succinctly.
“We just struck oil!” Tom gushed.
“They had to amputate them both at the ankles,” Tom said defeatedly.
“Who discovered radium?” asked Marie curiously.
“Hurry up and get to the back of the ship,” Tom said sternly.
“Who put the moss in the bog again?” asked Tom repeatedly.
“A word that contains all five English vowels plus y? And I suppose you want them to appear in alphabetical order!?” said Tom facetiously.
“The robber is coming down the stairs”, Tom said condescendingly. “Nnnn”, Tom murmured forensically.
A brief look at …
LAMBDA-CALCULUS AND COMBINATORS
12
Computation in lambda calculus
• Number representation
0 := λ f x. x 1 := λ f x. f x
2 := λ f x. f (f x) 3 := λ f x. f (f (f x))
• Operations
– SUCC:=λnfx.f(nfx)
– PLUS:=λmnfx.nf(mfx)
– MULT:=λmn.m(PLUSn)0
– AND := λ p q. p q p
– OR := λ p q. p p q
– NOT := λ p a b. p b a
– IFTHENELSE := λ p a b. p a b
Key ideas:
• beta reduction
• alpha conversion • eta reduction
http://en.wikipedia.org/wiki
/Lambda_calculus#Arithme tic_in_lambda_calculus
http://safalra.com/science/la mbda-calculus/integer- arithmetic/
λ-calculus and Turing completeness
• The untyped lambda-calculus is Turing complete (meaning that we can compute anything with it that we can compute with any other accepted formal model of computation)
• http://en.wikipedia.org/wiki/Turing_complete ness
• This article may also be helpful:
• http://en.wikipedia.org/wiki/Lambda_calculus
13
COMBINATORS
Expressions with no free variables …
• … are called combinators
(lambda (f g)
(lambda (x)
(f (g x))))
• A famous combinator, Y, is the “recursion maker”.
What is a good name for this combinator?
14
http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html
http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
THE Y-COMBINATOR
Y-combinator (“recursion maker”)
(define Y
(lambda (f)
((lambda (x)
(f (lambda (t)
((x x) t))))
(lambda (x)
(f (lambda (t)
((x x) t)))))))
Note that while Y is unusual,
there is nothing that looks recursive about it.
15
Y-combinator can be applied to …
(define H
(lambda (g)
(lambda (n)
(if (zero? n)
1(* n (g (- n 1))))))) (for example)
Note that there is nothing recursive about H. We simply pass in g and possibly call it.
But …
> ((Y H) 5)
120
Note: This is the “applicative-order Y- combinator” which works in Scheme.
In the pure lambda-calculus, in which parameters are passed “by name”.
the Y-combinator is slightly simpler.
Y-combinator generates “recursion” without using define or other naming
mechanisms
16