CSI2120 Programming Paradigms Jochen Lang
jlang@uottawa.ca
Faculté de génie | Faculty of Engineering
Jochen Lang, EECS jlang@uOttawa.ca
Scheme: Functional Programming
• Input/Output in Scheme
• Vectors in Scheme
• Looping with do • Sorting
Jochen Lang, EECS jlang@uOttawa.ca
Input/Output
• display – prints to the screen (REPL buffer) – (display “hello world”)
– hello world
• read – function that returns keyboard entries
– Reads a line from the REPL buffer and returns; nothing printed, e.g.:
(read) type 234 return
– Combine with display
(display (read)) type “hello world“ return prints hello world
• newline – for formatted output
Jochen Lang, EECS jlang@uOttawa.ca
Example: Number Entry
• Function that reads numbers, tests for a number until one is received.
(define (ask-number)
(display “Enter a number: “)
(let ((n (read)))
(if (number? n) n (ask-number))))
=> ask-number
(ask-number)
Enter a number: type “Hello” Enter a number: type Hello Enter a number: type (+ 3 54) Enter a number: type 2
prints 2
Jochen Lang, EECS jlang@uOttawa.ca
Reading a File into a List
• File i/o works as expected
– File streams are called ports
– Different flavours of file commands, here: open- input-file (others include open-input-output-file and open-output-file), close-input-port
(let ((p (open-input-file “short.scm”)))
(let f ((x (read p))) ; reading from file
(if (eof-object? x) ; check for eof
(begin
(close-input-port p)
‘())
(cons x (f (read p))))))
Jochen Lang, EECS jlang@uOttawa.ca
File I/O Inside a Top-level Define
• Function that opens a file and applies a procedure to every token read.
– Two arguments filename and proc
(define proc-in-file
(lambda (filename proc)
(let ((p (open-input-file filename)))
(let ((v (proc p)))
(close-input-port p)
v))))
– Note that procedure is applied to the path • must read in supplied procedure proc
Jochen Lang, EECS jlang@uOttawa.ca
Example: Output to File with a Top- level Define
• Write to file filename and the output from the function proc
(define proc-out-file
(lambda (filename proc)
(let ((p (open-output-file filename)))
(let ((v (proc p)))
(close-output-port p)
v))))
– proc-out-file only opens and closes file
• must write in supplied procedure proc
Jochen Lang, EECS jlang@uOttawa.ca
Printing a List to File
• Call proc-out-file with a function that recursively goes over the list
– Define a lambda to pass to proc-out-file
– Here the lambda makes use of a named let expression
(proc-out-file “list.out”
(lambda (p)
(let ((list-to-be-printed ‘(1 2 3 4)))
(let f ((l list-to-be-printed))
(if (not (null? l))
(begin
(write (car l) p)
(newline p)
(f (cdr l))))))))
Jochen Lang, EECS jlang@uOttawa.ca
Iteration: do
• (do ((var init update) …) (test resultIfTrue …) exprIfTe stFalse …)
(define fibonacci
(lambda (n)
(if (= n 0) 0
(do ((i n (- i 1))
(a1 1 (+ a1 a2)) ; a1=1, a1+=a2
(a2 0 a1)) ; a2=0, a2=a1
((= i 1) a1)))))
(fibonacci 6)
; i=1, –i
=> 8
Jochen Lang, EECS jlang@uOttawa.ca
Vectors in Scheme
• Vectors in Scheme are heterogeneous structures that allow access to the various elements using an index.
– requires less memory than lists
– elements access is constant time
• Basic commands
– create a vector with k elements
(make-vector k )
– create with an initial value for the elements (make-vector k init )
– test if an object is a vector
(vector? obj )
– make a constant vector
‘#( element_0 … element_k-1 )
• Ex: ‘#(0 (2 2 2 2) “Anna”)
Jochen Lang, EECS jlang@uOttawa.ca
Constructors and Accessors
• Top-level define for v
(vector ‘a ‘b ‘c)
=> #(a b c)
(define v (vector 2 (+ 1 2)))
=> v
v
=> #(2 3)
(vector-ref v 0) ; index starts at 0
2
(vector-length v)
2
(vector-set! v 1 10)
=> #(2 10)
Jochen Lang, EECS jlang@uOttawa.ca
More Examples of vector-set!
(let ((v (vector ‘a ‘b ‘c ‘d ‘e)))
(vector-set! v 2 ‘x) v)
=> #(a b x d e)
(define vector-fill!
(lambda (v x)
(let ((n (vector-length v)))
(do ((i 0 (+ i 1)))
((= i n))
(vector-set! v i x)))))
=> vector-fill!
(let ((v (vector 1 2 3)))
(vector-fill! v 0) v)
=> #(0 0 0)
Jochen Lang, EECS jlang@uOttawa.ca
Converting a List into a Vector
• Scheme functions for vector and list conversions
(list->vector ‘(1 2 3 4))
(vector->list (list->vector ‘(1 2 3 4)))
• Our own function
(define vec->li
(lambda (s)
(do ((i (- (vector-length s) 1) (- i 1))
(ls ‘() (cons (vector-ref s i) ls)))
((< i 0) ls))))
=> vec-li
(vec->li ‘#(a b c))
=> (a b c)
(let ((v ‘#(1 2 3 4 5)))
(apply * (vec->li v)))
=> 120
Jochen Lang, EECS jlang@uOttawa.ca
A Vector Function Example
• Looping from beginning to end
(define vector-sum
(lambda (vec)
(let ((size (vector-length vec)))
(do ((position 0 (+ position 1))
(total 0
(+ total (vector-ref vec position))))
((= position size) total)))))
=> vector-sum
(vector-sum #( 2 5 7 3 4))
=> 21
Jochen Lang, EECS jlang@uOttawa.ca
Another Example
• This time counting down from the end to the beginning
(define vector-sum
(lambda (vec)
(do ((remaining (vector-length vec)
(- remaining 1))
(total 0 (+ total (vector-ref vec
(- remaining 1)))))
((zero? remaining) total))))
=> vector-sum
(vector-sum #( 2 5 7 3 4))
=> 21
Jochen Lang, EECS jlang@uOttawa.ca
Sorting Vectors and Lists
• Sorting functions available in Scheme
– dialect dependent
– Racket has sort (while MIT Scheme has quick-sort and merge-sort accepting a list or vector) with an order predicate (here less-than). sort only accepts lists
• The predicate test must have the general form (and (test x y) (test y x))
=> #f
• Examples
(sort ‘(342125)<)
=> (1 2 2 3 4 5)
(sort ‘(0.5 1.2 1.1) >)
=> (1.2 1.1 .5)
Jochen Lang, EECS jlang@uOttawa.ca
List Functions Needed for Merge- Sorting
• Recursive algorithm
– Split list into two
– until only one element
– merge lists on the way up maintaining the order
• Our Implementation will use helper function – split ; splitting a list into two
• sub-list ; Defined with a helper routine that extracts a sub-list
– merge-list ; merging two lists in order
Jochen Lang, EECS jlang@uOttawa.ca
Extracting a Sub-list from a List
• Extracting a range from a list with an additional offset (define (sub L start stop ctr)
(cond
((null? L) L)
((< ctr start)
(sub (cdr L) start stop (+ ctr 1)))
((> ctr stop) ‘() )
(else (cons (car L)
(sub (cdr L) start stop (+ ctr 1))))))
=> sub
(sub ‘(a b c d e f g h) 3 7 0)
=> (d e f g h)
Jochen Lang, EECS jlang@uOttawa.ca
Split a List into Two
• Split a list into two using sub-list
– two base cases, empty list and lists of 1
(define (split L)
(let ((len (length L)))
(cond ((= len 0) (list L L) )
((= len 1) (list L ‘() ))
(else (list (sub L 1 (quotient len 2) 1)
(sub L (+ (quotient len 2) 1)
len 1))))))
=> split
(split ‘(a b c d e f g h))
=> ((a b c d) (e f g h))
Jochen Lang, EECS jlang@uOttawa.ca
Merging Two Lists
• Merging in order assuming the input is sorted
(define (mergelists L M)
(cond ( (null? L) M)
((null? M) L)
((< (car L)(car M))
(cons (car L)
(mergelists (cdr L) M)))
(else (cons (car M)
(mergelists L (cdr M))))))
=> mergelists
(mergelists ‘(1 5 10) ‘(2 6 7))
=> (1 2 5 6 7 10)
Jochen Lang, EECS jlang@uOttawa.ca
Merge-Sort Main Routine
• Assemble the sub-routines
(define (mergesort L)
(cond ((null? L) ‘())
((= 1 (length L)) L)
((= 2 (length L))
(mergelists (list (car L))(cdr L)))
(else (mergelists
(mergesort (car (split L)) )
(mergesort (car (cdr (split L))))))))
=> mergesort
(mergesort ‘(3 4 2 1 8 6 10))
=> (1 2 3 4 6 8 10)
Jochen Lang, EECS jlang@uOttawa.ca
Quick Sort
(define (qsort L)
(if (or (null? L) (<= (length L) 1))
L ; no need to sort
(let loop ((left '()) (right '()) ; for
(pivot (car L)) (rest (cdr L)))
(if (null? rest)
(append (qsort left)(list pivot)(qsort right))
(if (<= (car rest) pivot)
(loop (append left (list (car rest)))
right pivot (cdr rest))
(loop left (append right (list (car rest)))
pivot (cdr rest)))))))
=> qsort
(qsort ‘(74218610)) => (1 2 4 6 7 8 10)
Jochen Lang, EECS jlang@uOttawa.ca
Scheme: Functional Programming
• Input/Output in Scheme
• Looping with do • Vectors
– basic functions
– looping forwards and backwards • Sorting
– Mergesort – Quicksort
Jochen Lang, EECS jlang@uOttawa.ca