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.
Announcement
• comprehensive assignment Scheme is posted is due on April 8th. Accepted late with penalty till April 10th. TA: Saeed
• Scheme quiz 1 is posted. Due on March 31.
• Comprehensive assign 1 mark will be released today after class. If you have a concern, please contact TA. If issues is not fully resolved, please contact me.
Announcement
• comprehensive assignment Prolog is due on April 8th. Accepted late with penalty till April 10th. TA: Ahmed
• Prolog assignment is posted. Due on March 30th , Accepted late till April 1st. TA: Alim and Emmanuel
• Scheme assignment is posted, Due on April 9, TA: Manorama
Announcement
•Thursday March 25th (4:00 – 5:20 pm) live Tutorial session for
•Prolog Assignment •Go Exam questions
•Thursday April 1 (4:00 – 5:20 pm) live Tutorial session for TBA.
•Quiz: TA Kamrooz
Functional Programming in Scheme
• Equivalencypredicates • Lists
• Listoperations
• TailRecursions
Simple Predicate Functions
• Thepredicatesymbol?indicatesabooleanfunction returning #t or #f.
• (symbol? x) true if x is a symbol
• (number? x) true if x is a number
• (eq? x y) true if x and y have internally the same
representation (think of it as same pointer value) •(equal?xy)true ifxandyareidenticalobjects
(not necessarily atomic but same structure and content)
• (null? x) true if x is the empty lists () •(pair? x)true if x is a list or pair
• (procedure? x) true if x is a function •(list? x)true if x is a list
Equality Test eq?
• eq?comparesinternalrepresentations – addresses (pointer values)
– Cannot be used to reliably compare
• numbers • characters
(define hello “bonjour”)
(eq? hello hello)
(eq? “bonjour” “bonjour”)
4.1 Equality
Equality Test eqv?
• eqv?issimilartoeq?
– But can be used for characters and numbers
• Characters and numbers are compared by their
– Can not be used to compare lists, strings or functions
(eqv? 1 1)
(eqv? 2 (+ 1 1)) #t
(eqv? 1 1.0)
Equality Test equal?
• equal?comparesthestructureandcontents
– works for lists, strings and functions
(equal? ‘(a 1 2) ‘(a 1 2)) => #t
(equal? “bonjour” “bonjour”) => #t
(equal? (list 1 2) ‘(1 2)) => #t
(equal? ‘a ‘a)
(equal? 2 2) => #t
Control Structures
• ControlstructuresinSchemearesimple.Thereareno loops. There are only functions, conditional expressions, and the sequence (a concession to programmers used to imperative languages).
• Sequencesstartwithbegin
(begin (display ‘okay) (display ‘(great)))
=> okay(great)
• Thevaluereturnedby(begin…)isthevalueofthelast expression.
List Representation
• Internallyalistconsistsoftwopointers
– The first of these pointers gives the address of the atom or the corresponding list.
– The second pointer gives the address of the next cell.
(a ((b c) d) e)
List Construction: (cons obj1 obj2)
• Thefirstparameterofconsisanobjectwhichisthe beginning of the list. The second parameter is an object which is the tail of the list.
– Essentially two pointers in so-called cons cells • Internallyanewmemorycelliscreated
– The first points to the first object passed as parameter
– The second pointer points to the second object
(cons `a `(b c)) => (a b c)
(cons `(a b) `(b c)) => ((a b) b c)
• Consisthepairconstructor
• TheuseofpointinginSchemepairsisnot recommended
(dotted pairs are not lists!)
(cons `a `b) => (a . b)
Constructing lists
Any nonempty list is constructed from an item and a smaller list using cons.
In constructing a list step by step, the first step will always be consing an item onto an empty list.
(cons ’blue empty)
(cons ’red (cons ’blue empty))
(cons (sqr 2) empty)
(cons (cons 3 (cons true empty)) (cons (make-posn 1 3) empty))
Nested boxes visualization
(cons ’blue (cons true empty))
first ‘blue
first true
rest empty
(cons 1 (cons ’blue (cons true empty)))
first ‘blue
first true
rest empty
Box-and-pointer visualization
(cons ’blue (cons true empty))
(cons 1 (cons ’blue (cons true empty)))
CAR and CDR
• CARstandforContentoftheAddressRegister
(car ‘(a b c))
(car ‘((a b) b c)) => (a b)
• CDRstandforContentoftheDecrementRegister
(cdr ‘(a b c))
(cdr ‘((a b) b c)) => (b c)
(cdr ‘(a (b c))) => ((b c))
Nesting List Expressions
(cdr (car (cdr ‘(a (b c d) e)))) => (c d)
can be written as cdr car cdr = cd a dr = cdadr – works up to four combinations
(cdadr ‘(a (b c d) e)) => (c d)
(cons (car ‘(a b c)) (cdr ‘(a b c))) => (a b c)
4.10 Pairs and Lists
Recursive Concatenation of Two Lists
(define (append-list L1 L2) (if (null? L1)
(cons (car L1) (append-list (cdr L1) L2)))) => append-list
(append-list ‘(a b) ‘(c d))
=> (a b c d)
• Note:Thereisapre-definedfunctionappendaswell.
Recursive Inverting of a List
(define (invert-list L) (if (null? L)
(append-list (invert-list (cdr L))
=> invert-list
(list (car L)))))
(invert-list ‘(a b c d)) => (d c b a)
Recursive List Membership
• Find the member in the list and return a list with this member as the car of a list.
(define (member-list a L)
(cond ((null? L) ‘())
((equal? a (car L)) L)
(#t (member-list a (cdr L)))))
(member-list ‘a ‘(a b c)) => (a b c)
(member-list ‘b ‘(a b c)) => (b c)
(member-list ‘d ‘(a b c)) => ()
Recursive Size (Length) of a List
(define (length-list L) (if (null? L)
0(+ 1 (length-list (cdr L))))) => length-list
(length-list ‘(a b c)) => 3
Another Recursive List Example
• Functionthatfindsifanelementinthelisthasa neighbour which is the same as itself
(define (same-neighbours? L)
((null? L) #f)
((null? (cdr L)) #f)
((equal? (car L)(cadr L)) #t)
(same-neighbours? (cdr L)))))
=> same-neighbours?
(same-neighbours? ‘(1 2 3 3 5))
Predicate Function for Number-only Lists
(define (number-list? x )
((not ( list? x )) #f)
((null? x ) #t)
((not (number? (car x))) #f) (else (number-list? (cdr x )))))
=> number-list
(number-list? ‘(1 2 3 4))
(number-list? ‘(1 2 3 bad 4)) => #f
Equivalence of Two Lists?
(define (eqExpr? x y) (cond
((symbol?x) (eq?xy)) ((number?x) (eqv?xy)) ; x is a list:
((null? x) (null? y))
; x is a non-empty list ((null? y) #f)
((eqExpr? (car x) (car y))
(eqExpr? (cdr x) (cdr y))) ; recurse on car and cdr (else #f)))
(eqExpr? ‘(1 2 3 4) ‘(1 2 3 4)) => #t
(eqExpr? ‘(1 2 3 4) ‘(1 2 ‘(3 4))) => #f
Removing Duplicates from a List
(define (repeated-elements L) (if (list? L)
(do-repeated-elements L) ‘list-error))
(define (do-repeated-elements L) (cond
((null? L) ‘())
((member (car L) (cdr L))
(do-repeated-elements (cdr L))) (else (cons (car L)
(do-repeated-elements (cdr L)))) ))
(repeated-elements ‘(1 2 3 2 2)) => (1 3 2)
Stack – Basic Definition
(define (empty? stack)
(null? stack))
(define (push e stack)
(cons e stack))
(define (pop stack) (if (empty? stack)
(cdr stack)))
(define (top stack)
(if (empty? stack)
(car stack)))
(empty? ‘())
(push 5 ‘(2 3 4)) => (5 2 3 4) (top ‘(2 3 4)) => 2
(pop ‘(2 3 4)) => (3 4)
Minimal Element in a List
(define (min-list x) (if (null? x)
x(min-list-aux (car x)(cdr x))))
(define (min-list-aux e l)
((null? l) e) ((> e (car l))
(min-list-aux (car l)(cdr l))) (else (min-list-aux e (cdr l)))))
(min-list ‘(4 8 9 2 8))
List Minimum Using Local Variables
(define (min-list-aux e l)
(if (null? l) e
(let ((v1 (car l))
(v2 (cdr l))) (if
(> e v1) (min-list-aux v1 v2)
(min-list-aux e v2)
Other Example of Using Local Scope
• Functionquadrupleusingdoublewithlocalscope
(define (quadruple x)
(let ((double (lambda (x) (+ x x))))
(double (double x))
(quadruple 8)
(double 8)
=> ;Unbound variable: double
Traversal Applying a Function
• Acceptfunctionasanargument
– cdr to move to the end of the list
– cons to add the changed element at the beginning
(define (apply-list fct L) (if (null? L)
(cons (fct (car L))
(apply-list fct (cdr L)))))
(apply-list (lambda(x) (+ x 4)) ‘(1 2 3 4)) => (5 6 7 8)
Adding a Prefix to the Elements of a List
• Turneachelementofalistintoapair(usingcons) attaching the prefix parameter
(define (prefix-list p L)
(apply-list
(lambda(e) (cons p e)) L))
(prefix-list 2 ‘(1 2 3)) => ((2 . 1)(2 . 2)(2 . 3))
Generating Combinations
• In combinations order does not matter
– Aside: append concatenates the input lists
(define (combine dim set)
((= dim 0) ‘(())) ((null? set) ‘()) (else
(append (prefix-list (car set)
(combine (- dim 1) (cdr set)))
(combine dim (cdr set))))))
(combine 2 ‘(1 2 3))
=> ((1 2) (1 3) (2 3))
Reduction of a List to a Value
• Applyafunctiontoallelementsandreturntheresult – F0 is the value of the reduction for the empty list
(define (reduce F F0 L)
(if (null? L)
(F (car L)
(reduce F F0 (cdr L)))
(reduce * 1 ‘(1 2 3 4)) => 24
Loops as Recursions
• LoopingNtimes
(define (loop P N)
(cond ((zero? N) ‘())
(#T (display P) (loop P (- N 1)))))
• Loopoverrange
(define (loop2 P inf sup)
(cond ((> inf sup) ‘())
(#T (display P) (loop2 P (+ inf 1) sup))))
– NOTE: These functions have a tail recursion (tail recursion)
which is easier to optimize by a compiler
Traversal using a Tail Recursion
• Anyrecursivefunctioncanbeintheformoftailrecursion using an accumulator (variables) for intermediate results (define (apply-list2 fct L Lacc)
(if (null? L) Lacc
(apply-list2 fct (cdr L)
(append Lacc (list (fct (car L))))
(define (apply-list fct L)
(apply-list2 fct L ‘()))
(apply-list abs ‘(-3 -2.1 2 3.4)) => (3 2.1 2 3.4)
Factorial Example
(define (factorial n) (if (<= n 0)
(* n (factorial (- n 1))) ) )
• To turn this into a tail recursion, the function needs to return the result of the recursive call without changes (define (factorial n) (factorialb n 1))
(define (factorialb n answer) (if (<= n 0)
(factorialb (- n 1) (* n answer))))
Map Procedure
• Mapappliesafunctiontoeveryelementofalist.Itcan be more convenient than an explicit loop
(map abs ‘(1 -2 3 -4 5 -6)) (1 2 3 4 5 6 )
• Definealambdainthesameline
– function taking two arguments
– supply two lists
(map (lambda (x y) (* x y)) ‘(1 2 3 4) ‘(8 7 6 5))
(8 14 18 20)
• Equivalencypredicates • Lists
• Listoperations
– concatenate, inverse, membership, length, list neighbours, number-only predicate, list equivalence, duplicate removal, list as a stack, minimum, functions using local scope, applying a function to list elements, adding a prefix, combination, reduction of a list
• TailRecursions – Loops
– Factorials
– Map Procedure
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com