S1: Assorted Topics for Week 9 and 10
- Topics for Lab. 14
- Reading Lists
- Data Abstraction
- Topics for Chapter 5.1-5.2
- State, Assignment, Side-effects
- Assignment operators: set!, set-car!, set-cdr!
- Outline
- Ch. 4.3.9 Reading Lists
- Ch. 3.4.2 Modules, Software Engineering Box before 3.4
- Ch. 5.1 Boxes (extension)
- Ch. 5.2 Mutating Data Structures
- Ch. 5.3 Variable that vary
- Recommended Ex.: 1..3, 7, 9 ,17, 18, 20, 21
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S2: Revisiting 4.3.9 input-output with lists
- Reading flat lists from standard input
- List Delimiters: Use { and } instead of ( and )
- Item delimiters: whitespace
- Flat list: { 1 2 4 } is a flat list
- Trace driven development for standard input = { 1 2 4 }
(read-flat-list '{ '}) which reads { and recurse
(read-flat-list '{ '}) which reads 1
(cons 1 (read-flat-list '{ '})) which reads 2
(cons 1 (cons 2 (read-flat-list '{ '}))) which reads 4
(cons 1 (cons 2 (cons 4 (read-flat-list '{ '})))) which reads }
(cons 1 (cons 2 (cons 4 '() )))
( 1 2 4 )
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S3: Reading a flat list
- Base Case : read returns '} = > list = '()
- Recursive Decomposition
- read returns '{ = > (read-flat-list '{ '})
- read returns an item = > (cons item (read-flat-list '{ '}))
;;;;;;;
(define (read-flat-list begin-sym end-sym)
(let ( (token (read)) )
(if (symbol-equal? token 'end-sym)
'()
(if (symbol-equal? token 'begin-sym)
(read-flat-list begin-sym end-sym)
(cons token (read-flat-list begin-sym end-sym))
) ) ) )
;;;;;;;
- Testcases:
- standard input = { 4 2 1 }
- standard input = { }
- standard input = { { 1 } }
- standard input = { { 2 } { 1 } }
- Q? Determine the value returned from (read-flat-list '{ '})
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S4: 4.3.9 Reading a NESTED list
- Key difference from reading flat lists
- Items can themselves be a nested list
- Multiple occurrence of '{ and '}
- Trace driven development for standard input = { 1 { 2 } 4 }
;;; want (cons 1 (cons '(2) (cons 4 nil)))
(read-nested-list '{ '}) which reads first {
(helper '{ '}) which reads 1
(cons 1 (helper '{ '})) which reads {
(cons 1 (cons (helper '{ '}) (helper '{ '}))) which reads 2
(cons 1 (cons (cons 2 (helper '{ '})) (helper '{ '}))) which reads }
(cons 1 (cons (cons 2 '()) (helper '{ '}))) which reads 4
(cons 1 (cons '(2) (cons 4 (helper '{ '})))) which reads }
(cons 1 (cons '(2) (cons 4 '() ))) which reads }
(1 (2) 4 )
- Q? Why is a helper procedure needed? (see trace)
- first { makes one recursive call, other { make two!
- Note the presence of two calls to helper in line 4
- Q? Can either call to helper read the next input?
- Q? How to ensure that the left one reads next input?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S5: 4.3.9 Reading a NESTED list
- (read-nested-list start-sym end-sym)
- reads first '{ and calls helper
- (helper-read-nested-list start-sym end-sym)
- Base Case : read returns '} = > list = '()
- Recursive Decomposition
- read returns an item = >
(cons item (helper-read-nested-list start-sym end-sym))
- read returns '{ = >
(cons (helper-read-nested-list start-sym end-sym)
(helper-read-nested-list start-sym end-sym) )
- Even better
(let ((temp (helper-read-nested-list start-sym end-sym)) )
(cons temp (helper-read-nested-list start-sym end-sym) ) )
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S6: 4.3.9 Reading a NESTED list
- The implementation
(define (helper-read-nested-list start end)
(let ( (token (read)) )
(if (symbol-equal? token '} )
'()
(if (symbol-equal? token '{ )
(let ( (tmp (helper-read-nested-list start end)))
(cons tmp (helper-read-nested-list start end)))
(cons token (helper-read-nested-list start end))
) ) ) )
(define (read-nested-list start-sym end-sym)
(let ( (token (read)) )
(if (symbol-equal? token '{ )
(helper-read-nested-list start-sym end-sym)
token )))
- Testcases:
- standard input = { 4 2 1 }
- standard input = { }
- standard input = { { { 1 } } }
- standard input = { { 2 } 3 { 1 } }
- Q? Determine the value returned from (read-flat-list '{ '})
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S7: 3.4 Data Abstraction, ADTs, Encapsulation
- Readings: Chapter 3.4, Software Engineering box (pp 137-155)
- Problem: Complexity of designing large software systems
- Software systems with 10s of millions of lines of code
- Complexity growth is quadratic in number of components
- Constant change problem: software changes continuously to
- model the changes in the application domain.
- For example, Banking - interest rate, regulations change daily
- OS/360 project in 1960s = > overran budget, schedule manyfold
- Correcting bugs introduced new bugs
- Adding new people to overdue project made it worse.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S8: Motivation for Abstractions
- 1960's Software crisis:
- Hardware is getting cheaper, more reliable and faster,
- but software still stays expensive and not so reliable.
- Can software used by banks, airlines etc. fails mysteriously?
- Analysis of the Software Crisis in 1960s
- Use of low-level machine languages
- Changing programs to fix a bug could affect the entire program
- Complex program design - high coupling between components
- Birth of Software Engineering (1968): from coding to a life-cycle
- requirements, design, implementation, validation, maintenance
- Modular design - low coupling, high cohesion VIA
- Abstraction - procecdural abstraction, data abstraction
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S9: Procedures Vs. modules
;(module plotter
; (export plotter-data-transform-mod display-plotter)
(define (plotter-data-transform-mod xform )
;;; body (see. pp. 150)
)
(define (display-plotter) ;;; body )
(define (helper xform pendown) ;;; body )
;)
;;; eqv. in procedures = > no export facility
(procedure plotter
(define (plotter-data-transform-mod xform )
;;; body (see. pp. 150)
)
(define (display-plotter) ;;; body )
(define (helper xform pendown) ;;; body )
;;; body of plotter
)
- Q? How many procedures are in the interface in each case?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S10: What needs to be abstracted?
- What needs to abstracted? What can change?
- algorithm, social context, platform : lines of code
- data format, particularly global variables
- Example: Year 2000 problem - change in format of year data
- What does abstraction provide?
- Encapsulation of ADT: View ADT as a program unit
- Information Hiding: Need to know principle
- Show interface (what), not implementation (how)
- Procedural Abstraction
- What is encapsulated? - lines of code
- Interface = procedure name, parameters, result
- Implementation = code, helper procedures, local data
- Mechanisms: procedure, module, class ...
- Data Abstraction
- What is encapsulated? - data format, helper data-items
- Interface = constructor, accessor, operations
- Implementation = global data + format, helper procedures
- Mechanisms: abstract data types, module, class, ...
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S11: Example of Procedural Abstraction: Sqaure root
- Computing roots of a quadratic equation
- A generic code
(define (root1 A B C)
(/ (+ (* -1 b)
(sqrt (- (* B B) (* 4 (* A C))) )
)
2 ))
(define (root2 A B C)
(/ (- (* -1 b)
(sqrt (- (* B B) (* 4 (* A C))) )
)
2 ))
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S12: Example of Procedural Abstraction: Sqaure root
- Reducing repeated code by procedural abstraction
(define (discr A B C)
(sqrt (- (* B B) (* 4 (* A C))) ) )
(define (root1 A B C)
(/ (+ (* -1 b) (discr A B C)) 2 ) )
(define (root1 A B C)
(/ (- (* -1 b) (discr A B C)) 2 ) )
- Change in discriminant definition = > limits changes!
(define (discr A B C)
(let ( (tmp (- (* B B) (* 4 (* A C))) ) )
(if ( > = tmp 0) (sqrt tmp) (display "error in discr") ) ))
- Q? Identify impact of introduction of error checking
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S13: Example of Data Abstraction : Time ADT
- Example of computing minutes of a call (Lab. 14)
- Without data abstraction, e.g. time ADT
;;; assume time is represented as 100* hour + minute
(define (duration start-date start-time end-date end-time)
(let ( (start-hour (quotient start-time 100))
(start-minute (remainder start-time 100))
(end-hour (quotient end-time 100))
(end-minute (remainder end-time 100)) )
(if (equal? start-date end-date)
(-(+ end-minute (* 60 end-hour))
(+ start-minute (* 60 start-hour)))
( ;; ..... )
) ) )
(define (discount-percent start-time)
(let ( (start-hour (quotient start-time 100))
(start-minute (remainder start-time 100))
(if .... ))))
- Each function using time data-type
- needs to know the format of time and date
- Changing format of time (100*hour+minutes)
- affect every routine using data of type time
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S14: Example of Time ADT
- Alternative: time Abstract Data Type
;(module time
; (export make-time get-hour get-minute)
(define (make-time hour minute) (+ minute (* 100 hour)))
(define (get-hour time) (quotient time 100))
(define (get-minute time) (remainder time 100))
;
(define (duration start-date start-time end-date end-time)
(if (= start-date end-date)
(-(+ (get-minute end-time) (* 60 (get-hour end-time) ))
(+ (get-minute start-time (* 60 (get-hour start-time)))
( ;; ..... )
(define (discount-percent start-time)
(let ( (start-hour (get-hour start-time))
(start-minute (get-minute start-time))
(if .... ))))
- ADT time hides the implementation (100*hour + minute) of time
- Reduction of code decoding format of time
- Change in implementation format of time
- does not affect procedure 'duration' or 'discount-percent'
- Year 2000 problem = > won't exit if time ADT was used!!
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S15: Example of Time ADT
- Q? Suppose we change the format of time to = (cons hour minute)
- Identify the routines to be changes in each implementation.
- Without time ADT
- duration, discount-precentage, and all routines using time datatype
- With time ADT, only the routines inside module time!
;(module time
; (export make-time get-hour get-minute)
(define (make-time hour minute) (cons hour minute))
(define (get-hour time) (car time ))
(define (get-minute time) (cdr time ))
;)
- Q? Can we include more procedures inside time ADT?
- Q? Define a date ADT with a constructor and three accessors.
- A date consists of a year, a month and a day of the month.
- Clearly document the interface and the implementation.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S16: Abstract Data Types (ADT) - Other Remarks
- Why are ADTs interesting?
- ADT are like the Integrated Circuits for software
- Reusing ADTs can simplify writing programs
- Object oriented Hype = > fancy names for ADTs
- We learn Specific ADTS in Csci 3317, Csci 3321
- Common procedures in the interface of an ADT
- constructor - creates a value of the ADT type
- accessor - extract a part of an ADT value
- Q? Identify constructors and accessors for ADTs in Lab. 14
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S17: Is module the only way to support ADTs?
- Scheme Module construct
- Collection of objects divided into export and local
- Exported names are visible outside the module
- Local may have Initialization code, own/static variables
- C++ Class construct
- Extend struct type definition to include procedures
- Has 2 kinds of parts:
- public parts are exported
- private parts are hidden
- Another implementation of ADTs in Scheme
- Use a list with procedures and data
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S18: Example of ADTs from Lab. 14
- Program to compute phone bills
- Data abstraction identifies two major ADTs:
- Call record
- attributes: phone number, date, start-time, end-time
- procedures: display, area-code, duration, discount-percent
- Customer record
- attributes: phone number, name, list-of-calls
- procedures: display, process-all-calls
- Other possible ADTs: time, call-rate, area-code, ..
- Q? Identify the private and public parts of each module.
- Q? Why is it an error for customer-record procedure
- to directly access the attributes of a call-record?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S19: Example of ADTs from Lab. 14
- Abstraction layers
- Main program -- > Customer ADT -- > Call-record ADTs
- Implementation of call-record hidden from Customer ADT
- Implementation of Customer ADT hidden from main program
- Changing implementation of an ADT does not affect others,
- Customer ADT, call-record ADT and main program
- can be developed by 3 different programmers.
- Addressing constant change problem:
- Changing the implementation of call-record module
- des not affect either main program or customer record module
- Impact of implementation changes are contained within a module
- Impact on teamwork
- Each module can be dveloped independenlty
- After interfaces have been stabilized.
- Q? What would be a procedural abstraction for Lab. 14?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S20: Overview of the Last Class
- Administrative
- Comments on Final Exam.
- Closing remarks on Csci 3316, Winter 1997
- Course Evaluation
- Return HW#, Announce address of solutions
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S21: Comments on Final Exam.
- Syllabus
- Procedural Abstraction
- procedures, recursion, tail recursion, higher level procedures
- Data Abstraction
- pairs, lists, abstract data types
- Analysis Tools
- droid model, box-pointer diagrams, tracing
- Scheme
- prefix notation, special forms vs. procedure calls
- Nature
- Primarily analysis / problem solving
- A little bit of programming and discussion
- Open textbook, open class notes
- Pace: Not a speed test!
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S22: Closing Remarks
- Top ten things to learn in Csci 3316
- How to get phone numbers of fellow students?
- Matching Lots of Irritating Single Parenthesis.
- Change is the only constant for Computer Professionals
- Computer Science >> programming
- How to write simple programs?
- RECURSION
- droid models
- higher level procedures, e.g. map
- list processing
- Computer Science = life-blood of modern society
- Medicine - Pacemaker, CAT-scan, patient-records, ...
- Science - Space flight control, Genome mapping, ...
- Entertainment - Movies (Jurassic Park), VR Games
- Law - researching precedent
- Government - Environmental, defense, crime prevention
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S23: Csci 3316 in context of Computer Science
- Life Cycle of computer systems
- analysis
- requirement specification
- system design
- implementation
- quality control, testing
- operation, maintenance
- Q? Where does computer programming fit in the life cycle?
- Why study Scheme programming language?
- Simple unambiguous syntax, robust, interpreted this incremental
- Yet powerful
- Scheme = best first programming language ?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S24: Life after Csci 3316
- Reality Check via Undergraduate Colloquium
- Neeting fellow students
- More Csci concepts using Scheme = > Csci 3317
- Data Abstraction = >
- Data Structures in Csci 3321, 3322,
- Database Management in Csci 5702, Csci 5703
- Software Engineering in Csci 5180
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)
S25: Last Slide!!!
- It was fun learning programming concepts
- See you again in a course
- and in an activity sponsored by
- Undergraduate Committee
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3316,Winter.(home)