Transcript CMPUT 301: Lecture 02 Basic Concepts

CMPUT 301: Lecture 02
Basic concepts of Design and
Implementations
Lecturer: Martin Jagersand
Department of Computing Science
University of Alberta
Notes based on previous courses by
Ken Wong, Eleni Stroulia
Zach Dodds, Martin Jagersand
Goals today:
• Concepts and stages in the program designs
and implementation process.
• How and why Object Oriented design and
Programming evolved and where it fits in
the greater picture of SwEng paradigms.
• Some practical OO concepts and examples.
2
Design strategies overview:
• Previous courses: learned pragmatics of
programming and principles of algorithms
• This course: Focus on whole project design.
• Important concepts:
– abstraction
(simplifying to its essentials the description of a
real-world entity)
– separation
(treating “what” and “how” aspects
independently)
3
Abstraction
• Examples:sales person, medical patient, etc.
4
Abstraction
• Design strategy 1:
– focus on the essential aspects of an entity or
concept
– ignore or conceal non-essentials
– map real-world entities to software objects
• Abstraction =
– a named collection of attributes (data) and
behavior (actions, methods) relevant to
modeling a given entity for some particular
purpose
5
Separation
• Design strategy 2:
– separate “what” is to be done from “how” it is
done
– separate design issues from implementation
details
– separate externally “visible” behavior
(interfaces) from hidden, internal mechanisms
(implementations)
6
Interchangeable Implementations
7
Interchangeable Implementations
8
Separation
• Separation of concerns:
–
–
–
–
interfaces reveal assumptions
implementations hide changeable details
interface == contract
avoid ripple effects
9
Design concepts vs.
programming languages
• Note that design concepts (e.g. abstraction,
separation …) are independent of
programming languages
• But one or several programming language
may support or impose certain concepts.
Example: Separation:
– .h files in c
– Definition modules in modula 2,3
– Interfaces in java
10
Programming languages
• Programming paradigms and languages are
between (and link) human concepts and
ideas to machine implementations
• Have changed during time (more so than
either ideas or machines)
Prog.
Lang.
Computer
Human ideas
11
Evolution of programming languages
•
•
•
•
•
Machine lang
Imperative (Fortran, c, Pascal…)
Functional (lisp, ML, Haskell…)
Logical (prolog, alf…)
Object Oriented (Smalltalk, c++, java)
12
Design Strategies vs.
programming languages
• Note again that design strategy (e.g.
abstraction, separation …) are independent
of programming languages.
• Also: The same project can be implemented
using different strategies (and languages)
13
Example: Higher order functions
• Concept from functional design paradigms
and mathematics
• Q=f g
• Implementation in imperative and OO
languages and comments.
(blackboard)
14
Example: XVision
• Provides visual tracking (rmember interaction
video in last lecture)
• 10+ years effort several people, several univ
• Several implementations, same functionality
• Xvision 1-1.3 (Upenn, Yale): c, c++, Imperative
• fVision (Yale): Haskell, greencard, c
• XVision2 (JHU): c++
(Written using some fvision design strat)
15
Xvision application: face tracking
16
Xvision 1-1.3 (Upenn, Yale): c, c++,
Imperative
• Written by “hackers”
• Neat tricks speed up, but shortcut across
abstractions
• Good to provide specified functionality,
• but hard to port
• Hard to extend
17
fVision (Yale): Haskell, greencard, c
Example program:
trackMouth v = bestSSD mouthIms (newsrcI v (sizeof mouthIms))
trackLEye v = bestSSD leyeIms (newsrcI v (sizeof leyeIms))
trackREye v = bestSSD reyeIms (newsrcI v (sizeof reyeIms))
trackEyes v = composite2 (split, join) (trackLEye v) (trackREye v)
where
split = segToOrientedPts
--- some geometry
join = orientedPtsToSeg
--- some more geometry
trackClown v = composite2 concat2 (trackEyes v) (trackMouth v)
18
fVision (Yale): Haskell, greencard, c
• Uses dataflow model, higher order
functions
• Much easier to script new behaviours
• Easier to express geometry
• More compact code
• Haskell code about speed: about ¼ of c
19
XVision2 (JHU): c++
•
•
•
•
See it in our lab, use in c306, learn in c610!
Designed first, then implemented
Extensible, portable
Some loss of “neat” speadups due to
separation and hiding
• Speed: ¼ - 1/7 of original c version.
20
Next time:
• Object oriented design strategies
21