Programming Paradigms CSI2120 – Winter 2019
Jochen Lang
EECS, University of Ottawa Canada
Scheme: Functional Programming
• Input/Output in Scheme
• Setting varibles with set!
• Vectors in Scheme
• Looping with do
• Sorting
CSI2120: Programming Paradigms
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) type234return
– Combine with display
(display (read)) type “hello world“ return prints hello world
• newline – for formatted output
CSI2120: Programming Paradigms
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
CSI2120: Programming Paradigms
The function set!
• The function set! allows us to assign a value to a variable (set! a-num (+ 3 4))
(set! a-num (+ 1 a-num))
• Note that in Scheme functions which modify their arguments are given names that end with an exclamation mark !
CSI2120: Programming Paradigms
Example: Encapsulated set
(define light-switch (let ((lit #f)) (lambda ()
(set! lit (not lit))
(if lit ‘on ‘off))))
• The variable lit is only accessible within the define
• It is a kind of a static variable inside a function
CSI2120: Programming Paradigms
Iteration: do
• (do ((var init update) …) (test resultIfTrue …) exprIfTestFalse …)
(define fibonacci
(lambda (n)
(if (= n 0) 0
(fibonacci 6)
=> 8
(do((in(-i1)) ;i=1,–i (a1 1 (+ a1 a2)) ; a1=1, a1+=a2 (a2 0 a1)) ; a2=0, a2=a1
((= i 1) a1)))))
CSI2120: Programming Paradigms
Vectors in Scheme
• Vectors in Scheme are heterogeneous structures that allow access to the various elements using an index.
– requires less memory than lists
– elementsaccessisconstanttime • Basic commands
– createavectorwithkelements
(make-vector k )
– createwithaninitialvaluefortheelements (make-vector k init )
– testifanobjectisavector
(vector? obj )
– make a constant vector
‘#( element_0 … element_k-1 )
• Ex: ‘#(0 (2 2 2 2) “Anna”)
CSI2120: Programming Paradigms
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)
CSI2120: Programming Paradigms
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)
CSI2120: Programming Paradigms
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
CSI2120: Programming Paradigms
Sorting Vectors and Lists
• Sorting functions available in Scheme
– dialect dependent
– Rackethassort(whileMITSchemehasquick-sortand 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)<) => (122345) (sort ‘(0.5 1.2 1.1) >) => (1.2 1.1 .5)
CSI2120: Programming Paradigms
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
CSI2120: Programming Paradigms
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)
CSI2120: Programming Paradigms
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))
CSI2120: Programming Paradigms
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
(mergelists ‘(1 5 10) ‘(2 6 7))
=> (1 2 5 6 7 10)
CSI2120: Programming Paradigms
(mergelists L (cdr M))))))
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)
CSI2120: Programming Paradigms
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)
=> qsort
(qsort ‘(74218610)) => (1 2 4 6 7 8 10)
(loop (append left (list (car rest)))
right pivot (cdr rest))
(loop left (append right (list (car rest)))
pivot (cdr rest)))))))
CSI2120: Programming Paradigms
Scheme: Functional Programming
• Input/Output in Scheme
• Setting variables with set!
– stack with a top-level stack
• Looping with do
• Vectors
– basic functions
– looping forwards and backwards • Sorting
– Mergesort – Quicksort
CSI2120: Programming Paradigms