Transcript list of zoo animals

preparation
• start drscheme
• set language level to Beginner
• open in Presentations
–
–
–
–
–
length1.ss
length2.ss
icons.ss
planets0.ss
convert.ss
• add teachpack convert.ss
How to Produce the Best OO Programmers:
By Teaching Program Design
Matthias Felleisen
Rice University
Houston, Texas
Current Practice in Introductory Courses
• teach the syntax of a currently
fashionable programming language
• use Emacs or commercial PE
• show examples of code and ask
students to mimic
• discuss some algorithmic ideas (BigO)
Current Practice: Syntax and PEs
In you favorite C++ or Java programming environment:
wage_per_hour * number_of_hours = total_wage
pointer manipulation
Current Practice: Design vs Tinkering/O
• syntax: tinker until it works
• design: tinker until it works, too
• teaching standard algorithms
doesn’t replace a discipline of
design
• analyzing algorithms doesn’t say
how we should design programs
Lessons: The Trinity
• simple programming language
• programming environment for beginners
• a discipline of design: classes of data
TeachScheme!
TeachScheme! is not MIT Scheme!
• not MIT’s Scheme
• not MIT’s programming environment
• most importantly: not MIT’s non-design
– SICP fails the normal student
– SICP fails to convey the central role of design
– SICP has an outdated idea of OO programming
Part I: The Programming Language
Programming Language: Scheme
• Scheme’s notation is simple:
– (, operation, operands, )
• Scheme’s semantics is easy:
– it’s just the rules of mathematics: 1+1 = 2
• With Scheme, we can focus on ideas
Programming Language: Scheme Again
• simple syntax
• it’s a lie!
• simple semantics
• more lies!
• powerful PE
• do you believe this?
• rich language
• so where are the GUIs?
algebraic syntax
length1 returns 0, no matter what input
more algebraic syntax
an error message concerning procedures,
whatever those things are
Syntax is a Problem
• simple notational mistakes produce
strange results -- without warning
• simple notational mistakes produce
error messages beyond the students’
knowledge
• … and even in Scheme there are just
too many features
Programming Languages: Not One, Many
• language 1: first-order functional PL
– function definition and application
– conditional expression
– structure definition
• language 2: local function definitions
• language 3: functions and effects
– higher-order functions
– set! and structure mutation
– begin
Programming Languages
• arrange programming language in
pedagogic layers
• put students into a knowledgeappropriate context
• focus on design ideas relative to
this context
Part II: The Programming Environment
On to the Programming Environment
• one PE for all language levels
• the PE must allow instructors to
supplement code at all levels --even if the code does not conform
to the level
• the PE must enable interactive
exploration
DrScheme: Beginner Level
• error message due to restricted syntax
• check syntax
• pictures are values [if time]
• teachpacks
Part III: Design Recipes
Program Design for Beginners
• foster basic good habits
• the design is rational
– its steps explain the code’s structure
• the design focuses on classes of data
• the process is accessible to beginner
Design Recipes
in
to be designed
out
How do we wire the “program” to the rest of the world?
IMPERATIVE: Teach Model-View Separation
Design Recipes
• the programming environment must
support extreme separation of view
and model
• demonstrate temperature conversion
The Basic Design Recipe
• data analysis and class definition
• contract, purpose statement, header
• in-out (effect) examples
• function template
• function definition
• testing, test suite development
Design Recipes: Class Definitions
• use rigorous language, not
formalism
• naïve set theory
–
–
–
–
–
–
basic sets: numbers, chars, booleans
intervals on numbers
(labeled) products, that is, structures
(tagged) unions
self-references
vectors (much later)
Design Recipes: Class Definitions (2)
(define-struct spider (name size legs))
A spider is a structure:
(make-spider symbol number number)
Design Recipes: Class Definitions (3)
A zoo animal is either
• a spider
• an elephant
• a giraffe
• a mouse
•…
Each of these classes of animals has its own definition
Design Recipes: Class Definitions (4)
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
Let’s make examples:
• empty (by definition)
• (cons (make-spider ‘Asterix 1 6) empty)
• (cons (make-spider ‘Obelix 99 6) (cons … …))
Design Recipes: Class Definitions (5)
(define-struct child (name father mother))
A family tree is either
• ‘unknown
• (make-child symbol a-family-tree a-family-tree-2)
Many, if not most, interesting class definitions are self-referential.
Design Recipes: Templates
• a template reflects the structure of
the class definitions (for input,
mostly)
• this match helps designers, readers,
modifiers, maintainers alike
Design Recipes: Templates (2)
• is it a basic class?
• “domain knowledge”
• is it a union?
• case analysis
• is it a structure?
• extract field values
• is it self-referential?
• annotate for recursion
Design Recipes: Templates (3)
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
;; fun-for-zoo : list-of-zoo-animals -> ???
(define (fun-for-zoo a-loZA) … )
is it a union?
Design Recipes: Templates (4)
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
;; fun-for-zoo : list-of-zoo-animals -> ???
(define (fun-for-zoo a-loZA)
what are the sub-classes
(cond
[ <<condition>> <<answer>> ]
[ <<condition>> <<answer>> ]))
Design Recipes: Templates (5)
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
;; fun-for-zoo : list-of-zoo-animals -> ???
(define (fun-for-zoo a-loZA)
(cond
[ (empty? a-loZA) <<answer>> ]
[ (cons? a-loZA) <<answer>> ]))
are any of the potential
inputs structures?
Design Recipes: Templates (6)
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
;; fun-for-zoo : list-of-zoo-animals -> ???
is the class definition
(define (fun-for-zoo a-loZA)
self-referential?
(cond
[ (empty? a-loZA) … ]
[ (cons? a-loZA) … (first a-loZA) …
… (rest a-loZA) … ]))
Design Recipes: Templates (7)
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
;; fun-for-zoo : list-of-zoo-animals -> ???
(define (fun-for-zoo a-loZA)
(cond
[ (empty? a-loZA) … ]
[ (cons? a-loZA) … (first a-loZA) …
… (rest a-loZA) … ]))
Design Recipes: Defining Functions
• templates remind beginners of all
the information that is available
– which cases
– which field values, argument values
– which natural recursions are computed
• the goal of function definitions is
– to compute with the available values
– to combine the computed effects
Design Recipes: Overview
•
•
•
•
basic data, intervals of numbers
structures
unions
self-reference in class description
– several different cases [all one recipe]
• mutual references
• generative recursion
• special attributes:
– accumulators
– effects
• abstraction of designs
Design Recipes: Conclusion
• get students used to discipline from
DAY ONE
• use scripted question-and-answer game
until they realize they can do it on their
own
• works well as long as class definitions
are “standard”
Part IV: From Scheme to Java
Training OO Programmers
On to Java: What is OO Computing?
Scheme to Java: OO Computing
• focus: objects and
method invocation
• structures and
functions
• basic operations:
• basic operations:
– creation
– select field
– mutate field
–
–
–
–
creation
select field
mutate field
recognize kind
• select method via
“polymorphism”
• f(o) becomes o.f()
Scheme to Java: OO Programming
• develop class and
interface hierarchy
• develop class
definitions
• allocate code of
function to proper
subclass
• allocate code of
function to proper
cond-clause
Scheme to Java: Class Hierarchy
A list of zoo animals is either
• empty
• (cons animal a-list-of-zoo-animals)
List of zoo animals
Empty
Cons:
animal
list of zoo animals
Scheme to Java: Code Allocation
;; fun-for-zoo : list-of-zoo-animals -> ???
(define (fun-for-zoo a-loZA)
(cond
[ (empty? a-loZA)
]
[ (cons? a-loZA) … (first a-loZA) …
… (rest a-loZA) … ]))
List of zoo animals
Empty:
Cons:
animal
list of zoo animals
Scheme to Java: Ketchup & Caviar
abstract class List_Zoo_Animal {
int fun_for_list();
}
class Cons extends List_Zoo_Animal {
Zoo_Animal first;
List_Zoo_Animal rest;
int fun_for_list() {
return 1 + rest.fun_for_list();
}
}
class Empty
extends List_Zoo_Animal {
int fun_for_list() {
return 0;
}
}
Scheme to Java: Ketchup & Caviar
abstract class List_Zoo_Animal {
int fun_for_list();
}
class Cons extends List_Zoo_Animal {
Zoo_Animal first;
List_Zoo_Animal rest;
int fun_for_list() {
return 1 + rest.fun_for_list();
}
}
class Empty
extends List_Zoo_Animal {
int fun_for_list() {
return 0;
}
}
Scheme to Java
• the design recipes work step for
step for the production of OO
programs
• the differences are notational
• the differences are instructive
Why not just Java first?
• complex notation, complex mistakes
• no PE supports stratified Java
• design recipes drown in syntax
Part V: Experiences
Experiences: Rice Constraints
• life-long learners
• no trends, no fashion
• accommodate
industry long-time
• oo programming
components
• enable students to
gain industry
experience after
two semesters
• until recently:
– C++
• now more and more:
– Java, true OOP
Experiences: The Rice Experiment
second semester: OOP, classical data structures, patterns
comp sci introduction:
• TeachScheme curriculum
• good evaluation
• huge growth
• many different teachers
applied comp introduction:
• C/C++ curriculum
• weak evaluations
• little growth
•several teachers
beginners: no experience, up to three years of experience
Experiences: The Rice Experiment
• Faculty with preferences for C/C++
state that students from the Scheme
introduction perform better on
exams and projects in second
course than students from the C/C++
introduction
• Students with lots of experiences
eventually understand how much the
course adds to their basis
Experiences: Secondary Schools
• trained nearly 80 teachers/professors
• 65 deployed the curriculum, reuse it
• better basis for second courses
• much higher retention rate
– especially among females
Conclusion
• training good programmers does not
mean starting them on “currently
fashionable” tools
• provide a strong, rigorous foundation
in data-oriented, class-oriented
thinking
• then, and only then, expose to
current fashion
Conclusion
• training takes more than teaching
some syntax and good examples
• training takes
– a simple, stratified language
– an enforcing programming environment
– a rational design recipe
• Teach Scheme!
The End
Credits
•
•
•
•
Findler
Flanagan
Flatt
Krishnamurthi
•
•
•
•
Cartwright
Clements
Friedman
Steckler