S1: Assorted Topics for Week 9 and 10
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
      • { { 3 } 4 5} is not!
    • 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 '{ '})
    • for each testcase.
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 '{ '})
    • for each testcase.
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
      • introducing new bugs
    • 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(x*x) +Bx + C = 0
  • 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
    • on each implementation.
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
    • ACM Student Chapter
  • 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
    • with all of you.
  • 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)