Slides

S1: Chapter 3: New domains, Organizing Programs

Administrative Announcements for Week 4
- Errata on Homework 2
- Any questions on HW#2?
Topics for Week 4
- 3.1 Domain of Text: characters, strings
- 3.2 Domain of Input/Output, Side-effects
Reading
- Chapter 3
- Appendix B.5.4 begin
  - B.6.6 characters, B.6.7 strings, B.6.11 input, output
- Recommended Ex.: 3.1, 4, 6, 9, 11, 14...18, 24, 25

S2: 3.1 Text Processing

3.1.1 Domain of characters
- Set of Values = #\\a, #\\z, #\\A, #\\W, #\\4, #\\space, #\\newline, ...
Predicate functions
(char? obj) ; return #t is obj is a character, #f otherwise
(char-alphabetic? obj)
(char-numeric? obj)
; char-whitespace?, char-upper-case? char-lower-case?
Social Security for Character: Unique Numeric Code
(char- > integer char) ; returns numeric code for char
(integer- > char num) ; inverse function
Q? What should (char < ? #\\a #\\1), (char < ? #\\a #\\B) be ?
Numeric code comparison
; char=?, char < ?, char > =?, ...
Case-insensitive comparison
char-ci=?, char-ci < ?, char > =?, ...

S3: 3.1.2 Domain of Strings

String = an ordered sequence of characters
- e.g. "fIvE", "abc123", "", "cat's cradle"
- 0th character in "fIve" is #\\f, 1st #\\I, 2nd #\\v, 3rd #\\E
- (string-ref "fIvE" 1); returns #\\I,
- Predicate (string? "five") = #t,
Procedures on String Domain/Range
(string-append "abc" "123") ; yields "abc123"
(string-length "abc" ) ; yields 3
(substring "eggplant" 0 3 ) ; yields "egg"
(string #\\f #\\I #\\v #\\E) ; yields "fIvE"
Comparison Predicates
Numeric Code based: string=?, string < ?, ...
Case-insensitive: string-ci=?, string < -ci?, ...
Exercises
1. Determine domains for #t, #\\t, "t", t
2. Which string-comparison is used by textbook index ?
3. Evaluate (string-ref "abc" 2), (string-ref "abc" 0)
4. Evaluate (string=? "a" "A"), (string-ci=? "a" "A")
5. Evaluate (string-length (string-append "abc" "") )
6. (string-append (substring "clay bricks" 5 9) "-a")

S4: 3.1.3-4 : Playing with Strings

3.1.3 Encryption of messages - Caeser codes
- "a big Secret" = > "e fmk Wigvix",
Palindromes: "level", "Madam, I'm Adam",
- Q? Write predicate (palindrome? str)
Trace of Strategy - Divide and Conquor
; Test case with "level"
(palindrome? "level")
> (palindrome? "eve")
> > (palindrome? "v")
#t
SpaceN%1
; Test case with "label"
(palindrome? "label")
> (palindrome? "abe")
#f
SpaceN%1
; Test case with "noon"
(palindrome? "noon")
> (palindrome? "oo")
> > (palindrome? "")
#t

S5: 3.1.4 : Palindromes

Design
- Base Case: strings of length 1 = > answer = ...
- Recursive Case:
  - If first and last characters don't match then ....
  - else .............
    (define (palindrome? str)
    (if ( < = (string-length str) 1)
    #t
    (if (char=? (first-char str) (last-char str))
    (palindrome? (all-but-first-N-last-char str))
    #f )))
    (define (first-char str) (string-ref str 0))
    (define (last-char str) (string-ref str (last-index str)))
    (define (last-index str) (- (string-length str) 1))
    (define (all-but-first-N-last-char str)
    (substring str 1 (- (last-index str) 1) ))
- Q? Test it w/ "Noon", "level", "Madam, I'm Adam".
- Q? Is palindrome? tail-recursive?
- Q? Implement palindrome? without using "substring" procedure.

S6: 3.1.4 : More Exercises on String Manipulation

Q? Implement functions for
- (i) Converting a string to upper case
- (ii) Counting the number of vowels in a string
- (iii) Determine if a string has all five vowels
- (iv) Determine words in the dictionary with all five vowels
Steps
- (i) Identify parameters
- (ii) Identify base cases
- (iii) Identify recursive cases
- (iv) Identify problem decomposition

S7: 3.2 : Input/Output and Graphics

Motivation
- Communication with Outside world
- World = people, other computers / devices
  - keyboard, mouse, monitor, network, disk, tape, ...
- Communication = listen ; compute ; talk
  - listen = input, reading, ...
  - talk = output, reading, ...
- Medium: number, boolean, text, graphics, audio, video, ...
Scope of Discussion in 3.2
- Focus on standard input and standard output
  - Default standard input = keyboard
  - Default standard output = monitor
- Will not discuss files, streams, etc.
Side-effects in I/O procedures
- I/O procedures have state
- Parameters do not tell the complete story
- Effect of an I/O procedures = f(state of keyboard, monitor,...)

S8: 3.2.1 : Reading

Procedure read - inputs a value from standard input
- Can read a number, a boolean, a character, a string etc.
  ; Assume we type in the following on standard input
  ; 1 2 3 4 5 #\\newline
  ; Following is typed into Scheme interpreter
  (read) ; returns 1 after reading it
  (define x (read) ) ; sets x to 2
  x ; returns 2
  (+ x (read)) ; returns 5, which is (+ 2 3)
  (- (read) (read)) : Q? What will it return?
Issue of side-effect
Result of (read) is dependent on previous (read)
Makes it hard to understand, analyze and debug a program
Output may change from an execution to another
with the same input
Revisit (- (read) (read))
Recall functions may evaluate their argument in any order
Result is either (- 4 5) or (- 5 4)
non-deterministic!

S9: 3.2.2 : Output to Standard Output (e.g. Monitor)

Reading: Appendix B.6.11.3 (pp. 771)
Procedures: display, newline, format
(display scheme-form) ; returns # < void >
(newline) ; returns # < void >
(format #t format-string scheme-form scheme-form ...)
Examples
;; assume x = 2, y =3, name = "Mary"
(display name) ; Mary
(display x) ; 2
(format "x = ~a, name = ~a", x, name) ; x = 2, name = Mary
; placeholder ~a: convert corresponding scheme-form to
(+ y (display x)) ; Q? What is the value?
Return values for output routines
Procedures return # < void > and change standard output
(+ 3 # < void > ) = > error , # < void > outside domain of +
(+ y (display x)) ; Puts 2 and error message on standard output
Side effect can create surprises
(foo (display x) (display y)) ;; ?order of display

S10: 3.2 : Playing with Input/Output

Ex. Trace the call (f) assuming the standard input has
- 0 20 200 2000
- Q? How many droids are created?
- Q? What strings are sent to standard input?
- Q? What value is returned by (f)?
A sample implementation
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (f)
(display "Enter an input value or #f to end: ")
(g (read)) )
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (g x)
(if (boolean? x)
x
(if (and (number? x) ( > x 1950))
x
(begin (display "Invalid input. Enter a positive number: ")
(f) ) )))

S11: 3.2 : Playing with Input/Output

Ex. Read a sequence of ten numbers from standard input
- and print the sum.
- Design: Q? Is repetition / recursion needed?
- Is a helper function needed?
- How many parameters are needed?
- What are base cases?
- What are recursive cases?
- What is recursive decomposition?
A sample implementation
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (sum-of-ten-numbers) (sum-of-numbers 10 0) )
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (sum-of-numbers how-many sum)
(if ( < = how-many 0)
0
(sum-of-numbers (- how-many 1) (+ sum (read)) )))
Ex. Read a sequence of positive numbers from standard input
and print the sum. The series is terminated by #f

S12: Chapter 3: New domains, Organizing Programs

Administrative Announcements for Week 5
- Mid-quarter on Friday (Feb. 7th)
- Make-up before the exam.
  - Th. 1-2pm, Catherine's office hours
  - Call Catherine and Cecil to ensure smooth management.
- Q? How was the practice exam.?
Topics for Week 5
- 3.3 Domain of functions, i.e. Procedures as Arguments
- 3.4 Program Organization: let, let*, module
Reading
- Chapter 3
- Appendix B.5.8.2 let, B.5.10 module, B.6.10 procedures
Recommended Ex.: 3.1, 4, 6, 9, 11, 14...18, 24, 25

S13: 3.4 : Program Organization: let, module

Special Form let
- Motivation: Save (read) in local variable
  - for multiple use.
- Ex. Read a sequence of positive numbers from standard input
- and print the sum. The series is terminated by #f
- Psuedo code
  ;1. Read a scheme form from standard input - (read)
  ;2. If scheme-form is #f, return result
  ;3. If it is a number, add it to the sum of remaining numbers
Q? How can Steps 2 and 3 refers to the value read?
Note repeating (read) in Step 2 reads a new number!
;;let "let" rescue you!
(define (sum-of-numbers)
(let (x (read))
(if (number? x)
(+ x sum-of-numbers)
0 )))
Special form "let" allows creation of local names!

S14: 3.4.1 Special Form "let"

Syntax: ( let list-of-name-value-pairs body-scheme-form )
(let ( (x 4) (y 7) )
(if ( < x y) (+ x y) (- x y)) )
Formal Semantics
"let" is implemented by lambda
( (lambda(x y)
(if ( < x y) (+ x y) (- x y)) )
4 7)
So What?, i.e. What can surprise us?
Scope of names is local, i.e. body of let
No order of evaluation for Name-Value pairs
No recursive values allowed in name-value pair
Special forms let*, and letrec help in last two cases!

S15: 3.4.1 : Common Errors with "let"

Q? Evaluate the last expression in following :
;;assuming standard input has 1 2 3 4 5 6 7 8
;;;; form1 ;;;
(let ( (x 2) )
(+ x 3) )
;;;; form2 ;;;
(let ( (x 2) (y (+ x 3)) )
y )
;;;; form3 ;;;
(let ( (x (read)) (y (read)) )
( - x y) )
;;;; form4 ;;;
(let ( (x (read)) )
( - x (read) ) )
;;;; form5 ;;;
(let ( (x (read)) ) #t )
x
;;;; form6 ;;;
(let ( (fact (lambda(n)
(if ( < n 1) 1 (* n (fact (- n 1)))) )) )
(fact 1) )
Q? Where can let* and letrec help?

S16: 3.4.2 : Special Form "module"

Motivation
- Program organization, e.g. subroutine-library
- Abstract data types: separate interface from implementation
- Control effect of changes
Syntax: (module mname (export name-list) list-of-definitions)
Semantics: Scoping
- Only exported names accessible OUTside module
- Other helper procedures are available inside module
Example
(module location
(export make-location location-x location-y)
(define MAX-x 1000 )
(define (make-location x y) (+ (* MAX-x x) y) )
(define (location-x c) (quotient c MAX-x) )
(define (location-y c) (remainder c MAX-x) )
)
Max-x ;; return error: undefined variable Max-x
(make-location 5 5) ;; returns 5005
Changing MAX-x does not affect code outside module location!

S17: 3.4.3 : Abstract Data Types (ADT) and "module"

Why are ADTs interesting?
- ADT are like the Integrated Circuits for software
- Reusing ADTs can simplify writing programs
- We learn Specific ADTS in Csci 3317, Csci 3321
Definitions
- Interface: What services are provided by a system?
- Implementation: How are services supported inside a system?
- Data Abstraction - Specify interface to data via procedure,
  - but don't reveal the implementation choice.
- ADT- A data type specified by an interface
  - Ex. location
- 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 location ADT.

S18: 3.3 : Why Pass procedures as Arguments

Motivation: Higher level procedures
- Consider the procedures for summing following series
  - f1(n) = 1 + 2 + 3 + ... + n
  - f2(n) = 1*1 + 2*2 ... + n*n
  - f3(n) = 1*1*1 + 2*2*2 + ... + n*n*n
  - f4(n) = f(1) + f(2) + ... + f(n)
    (define (f1 n)
    (if ( < = n 1)
    1
    (+ n (f1 (sub1 n)))))
    (define (f2 n)
    (if ( < = n 1)
    1
    (+ (* n n) (f2 (sub1 n)))))
    ...
    (define (f4 n)
    (if ( < = n 1)
    1
    (+ (f n) (f4 (sub1 n)))))
- Common Pattern in f1, f2, ..., f4
- Only difference is the (f n) part in the last line
- If "f" were a parameter, Can the f1...f4 be unified?

S19: 3.3 : Domain of Procedures

Unified function with procedure valued parameter
(define (sum f n)
(if ( < = n 1)
1
(+ (f n) (sum f (sub1 n)))))
(sum (lambda(x) x) n) ;;; simulates f1.
Q? Write forms to simulate f2, f3, f4 using sum.
Q? Generalize cube-root procedure to f-root procedure to solve
f(x) = 0, i.e. find x = a, s.t. f(a) = 0.
(define (cube-root-solve a x0 x1)
(if ( < (- x1 x0) epsilon)
(mid-point x0 x1)
(if ( > (cube (mid-point x0 x1)) a)
(cube-root-solve a x0 (mid-point x0 x1))
(cube-root-solve a (mid-point x0 x1) x1))))
(define (cube-root a) (cube-root-solve a 1 a))
(define (cube a) (* a (* a a)))
(define (mid-point p q) (/ (+ p q) 2)
(define epsilon 0.0001 )

S20: 3.3 : Returning Procedures

Motivation: The infamous "compose"
- Composition of two function produce a new function
- Example Let H be sqr * cube
  H(5) = sqr * cube (2) = sqr(cube(2)) = sqr(8) = 64
Characterizing "Compose"
- Domain = pairs of functions, e.g. < sqr, cube >
- Range = functions, e.g. H
Scheme allows representation of "Compose" as procedure
- Arguments: function f, function g
- Returns: (lambda(x) (f (g x)))
  (define (compose f g)
  (lambda(x) (f (g x))) )
Testing "compose"
(define (sqr x) (* x x ))
(define (cube x) (* x (* x x)))
(define h (compose f g))
(h 2)
((compose f g) 2)
((compose (lambda(x)(* x x )) (lambda(x)(* x (* x x)))) 2)

S21: 3.3 : Input/Output from Files

Syntax: same as passing numbers as parameters
Semantics: same as passing numbers as parameters
- assuming the passed procedure has no free variable.
- Procedures are first-class citizens in Scheme
- i.e. use procedures in the same way as we use number
- Value for variables
- pass as parameter
- return as result
- No arbitrary restrictions
  - e.g. Some language restrict passing procedures as parameters
  - Others restrict returning procedures as result

S22: 3.3 : Returning Procedures as Results

Ex. Write a procedure F, which takes an argument K
- and returns another procedure G.
- G takes another argument x and computes (power x K).
  (define (F K)
  (lambda(x) (power x K)))
  (define sqr (F 2))
  (define cube (F 3))
  (define (power x K)
  (if (= K 0)
  1
  (* x (power x (- K 1))) ))
- Semantics is complex.
- How is K remembered?
- Revsit in Chapter 5

S23: 3.3 : Passing Procedures as Arguments

Reading files:
- (with-input-from-file "filename" conversion-procedure)
- conversion-procedure has no arguments
  (define (scale-down-by-500) (lambda(x) (/x 500)) )
  (with-input-from-file "plot.dat" scale-down-by-500)
  ;; reads a number x from plot.data
  ;; and returns x/500
Writing to files
(with-output-to-file "filename" conversion-procedure)
(with-output-to-file "myfile.dat" (display "Hello123") )
;; Create a file name myfile.dat containing Hello123