Programming Paradigms
• Course overview
•Introduction to programming paradigms
Copyright By PowCoder代写 加微信 powcoder
• Review: The object-oriented
paradigm in Java •Imperative and concurrent
programming paradigm: Go. • Logic paradigm: Prolog.
• Functional paradigm: Scheme.
Acknowledgment
The slides posted through the term are based of the slides offered by:
Prof. Jochen Lang
Demo code: https://www.site.uottawa.ca/~jl ang/CSI2120/demoCode.html
Scheme: Functional Programming
• Input/OutputinScheme • Settingvaribleswithset! • Loopingwithdo
Input/Output
• display–printstothescreen(REPLbuffer) – (display “hello world”)
– hello world
• read–functionthatreturnskeyboardentries
– 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–forformattedoutput
Example: Number Entry
• Functionthatreadsnumbers,testsforanumberuntilone 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
Example: Using the Input
• Afunctionthatreadsanumberandcallsthefunctionsqrt and prints the output.
(define (find-sqrt)
(let ((n (ask-number)))
(display “The sqrt of “) (display n)
(display ” is “) (display (sqrt n)) (newline)))
=> find-sqrt
(find-sqrt)
Enter a number: type 5
prints The sqrt of 5 is 2.23606797749979
Reading a File into a List
• Filei/oworksasexpected
– 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) (begin
; check for eof
(close-input-port p)
(cons x (f (read p))))))
File I/O Inside a Top-level Define
• Functionthatopensafileandappliesaprocedureto 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)
– Note that procedure is applied to the path • must read in supplied procedure proc
Example: Output to File with a Top- level Define
• Writetofilefilenameandtheoutputfromthefunction proc
(define proc-out-file (lambda (filename proc)
(let ((p (open-output-file filename))) (let ((v (proc p)))
(close-output-port p)
– proc-out-file only opens and closes file • must write in supplied procedure proc
Printing a List to File
• Callproc-out-filewithafunctionthatrecursivelygoesover 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))))))))
Reminder: The function set!
• Thefunctionset!allowsustoassignavaluetoa variable
(set! a-num (+ 3 4))
(set! a-num (+ 1 a-num))
• NotethatinSchemefunctionswhichmodifytheir arguments are given names that end with an exclamation mark !
Example: Encapsulated set
(define light-switch (let ((lit #f)) (lambda () (set! lit (not lit))
(if lit ‘on ‘off))))
• Thevariablelit isonlyaccessiblewithinthedefine • Itisakindofastaticvariableinsideafunction
Stack – Using Variables
(define a-stack ‘())
(define (empty?)
(null? a-stack))
(define (push e)
(set! a-stack
(cons e a-stack))
a-stack ))
(define (pop)
(if (empty?)
(set! a-stack
(cdr a-stack))
a-stack)))
(define (top)
(if (empty?)
(car a-stack)))
Using a Stack
(define a-stack ())
Iteration: do
• (do((varinitupdate)…)(testresultIfTrue…)exprIfTe stFalse …)
(define fibonacci
(lambda (n)
(if (= n 0)
0(do((in(-i1)) ;i=1,–i (a1 1 (+ a1 a2)) ; a1=1, a1+=a2 (a2 0 a1)) ; a2=0, a2=a1
((= i 1) a1)))))
(fibonacci 6) => 8
Vectors in Scheme
• VectorsinSchemeareheterogeneousstructuresthatallow access to the various elements using an index.
– requires less memory than lists
– elements access is constant time • Basiccommands
– 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(2222)”Anna”)
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)
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)
Converting a List into a Vector
• Schemefunctionsforvectorandlistconversions
(list->vector ‘(1 2 3 4))
(vector->list (list->vector ‘(1 2 3 4)))
• Ourownfunction
(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 ‘#(a b c))
=> (a b c)
(let ((v ‘#(1 2 3 4 5)))
(apply * (vec->li v))) => 120
Sorting Vectors and Lists
• SortingfunctionsavailableinScheme – 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
• Thepredicatetestmusthavethegeneralform (and (test x y) (test y x))
• Examples
(sort ‘(342125)<) => (122345) (sort ‘(0.5 1.2 1.1) >) => (1.2 1.1 .5)
List Functions Needed for Merge- Sorting
• Recursivealgorithm – Split list into two
– until only one element
– merge lists on the way up maintaining the order • OurImplementationwillusehelperfunction
– 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
Extracting a Sub-list from a List
• Extractingarangefromalistwithanadditionaloffset (define (sub L start stop ctr)
((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)
Split a List into Two
• Splitalistintotwousingsub-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 ‘(a b c d e f g h))
=> ((a b c d) (e f g h))
Merging Two Lists
• Merginginorderassumingtheinputissorted
(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)
Merge-Sort Main Routine
• Assemblethesub-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)
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 '(74218610)) => (1 2 4 6 7 8 10)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com