Propositional Calculus - College of Computing & Informatics

Propositional Calculus - College of Computing & Informatics

Introduction to Functional Programming in Racket CS 270 Math Foundations of CS Jeremy Johnson 1 Objective To introduce functional programming in racket Programs are functions and their semantics involve function application. Programs may also produce function by returning functions as values. In pure functional programming, this is it, there are no variables, side effects, nor loops. This simplifies semantics but does not reduce computational power.

We will investigate the style of programming this implies and how to model the semantics of such programs. 2 Outline 1. Syntax and semantics 2. Functional programming 1. Programs are functions for every input there is a unique output (referential transparency) 2. No variables no assignment and no loops 3. Use recursion for iteration 4. Functions are first class objects 1.

Pass as arguments and return as values 3. Racket language and Dr. Racket IDE 3 A Pure Functional Language x1 = y1,,xn=yn f(x1,,xn) = f(y1,,yn) No side-effects, no assignments, no state, no loops Use recursion instead of iteration Still Turing complete Makes reasoning about programs easier 4

C++ Function with Side-Effects #include using namespace std; % g++ count.c int cc() % ./a.out { static int x = 0; return ++x; cc() = 1

cc() = 2 cc() = 3 } int main() { cout << "cc() = " << cc() << endl; cout << "cc() = " << cc() << endl; cout << "cc() = " << cc() << endl; } 5 Syntax Programs and data are lists delimited by (

and ) or [ and ] and separated by space S expressions (E1 En) Special forms Self evaluating: numbers, Booleans, strings, (quote expr) (if test-expr then-expr else-expr) (cond ([P1 E1] [Pt Et]))

(lambda (p1 pn) E1 Et) (define name E) 6 (let ([b1 v1] [bt vt] E) Semantics To evaluate (E1 E2 ... En), recursively evaluate E1, E2,...,En - E1 should evaluate to a function - and then apply the function value of E1 to the arguments given by the values of E2,...,En. In the base case, there are self evaluating expressions (e.g. numbers and symbols). In addition, various special forms such as quote and if must be handled separately. 7

Read-Eval-Print-Loop (REPL) Dr. Racket IDE (racket-lang.org) Definition Window Click Run to load and run definitions Interaction Window Enter expressions at the prompt (REPL) 8 Example Evaluation

2 => 2 (/ 4 6) => + => # (+ 2 (* 3 4)) => (+ 2 12) => 14 (max 1 2 3) => 3 (1 2 3) => error

(list 1 2 3) => (1 2 3) (list 1 (2 3) 4) => error (list 1 (list 2 3) 4) => (1 (2 3) 4) Booleans and Predicates Boolean constants: #t and #f (= 2 3) => #f (or (= 2 3) (not (= 2 3))) => #t (and #t #t #t) => #t Predicates are Boolean functions

Convention is name? (equal? 2 3) => #f (eq? 2 3) => #f (number? 2) => #t (boolean? (and #t #f)) => #t Conditional (if test-expr then-expr else-expr) Evaluate test-expr if not #f evaluate and return then-expr else evaluate and return else-expr

(if (< 2 3) 0 1) => 0 (if (< 3 2) 0 1) => 1 (if (= 3 (+ 2 1)) 0 1) => 0 (if (or (= 2 3) (= 3 3)) (+2 3) (+ 3 3)) => 5 Conditional (cond [test-expr1 then-body1] [test-exprn then-bodyn] [else then-body]) Evaluate test-expr1 if #f then goto next

case otherwise return then-body1. The else case always returns then-body (cond [(= 2 3) 2] [(= 3 4) 3] [else 4]) => 4 List Processing Functions

(null? ()) => #t (null? (1 2 3)) => #f (car (1 2 3)) => 1 ;same as (first (1 2 3)) (cdr (1 2 3)) => (2 3) ;same as (rest (1 2 3)) (cons 1 ()) => (1) (cons 1 (2 3)) => (1 2 3) (cons 1 (cons 2 (cons 3 '()))) => (1 2 3) (cons (cons 1 ()) (2 3)) => ((1) 2 3) Lambda Expressions (lambda (parameters) body) Evaluates to a function When applied the actual arguments are

substituted for the formal parameters into the body which is then evaluated and returned (lambda (x) (* x x)) => # ((lambda (x) (* x x)) 2) => 4 (define sqr (lambda (x) (* x x))) (define (sqr x) (* x x)) ;shorthand for above (sqr 2) => 4

Recursion In a functional language there are no side effects, hence no assignment and no loops. All control must be done through recursion (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) (fact 3) => 6 (define (ones n) (if (= n 0) '() (cons 1 (ones (- n 1))))) (ones 3) => (1 1 1) Trace Recursion (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) (fact 0) = 1

(fact 3) = (* 3 (fact 2)) = (* 3 (* 2 (fact 1))) = (* 3 (* 2 (* 1 (fact 0)))) = (* 3 (* 2 (* 1 1))) = 6 When n=0 [base case] no recursion When n>0 [recursive case] recursion occurs Recursion (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) Similar to mathematical definition define what to compute Declarative programming states what to compute rather than how to compute it Tail Recursion

A tail recursive function is a function where the recursive call is the last operation. Such procedures can easily be converted to loops. (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) (define (factt n sofar) (if (= n 0) sofar (factt (- n 1) (* n sofar))))) (fact n) = (factt n 1) Tail Recursion An equivalent loop can be constructed, which updates the arguments each iteration of the loop. for (;;){

if (n == 0) return sofar; else { t1 = n - 1; t2 = sofar * n; n = t1; sofar = t2; } } Testing Test cases give examples of what a function should compute if implemented properly. They can be used for debugging.

(fact 3) = 6 (fact 2) = 2 (fact 1) = 1 (fact 0) = 1 Unit Testing in Racket (require rackunit) (require rackunit/text-ui) (define-test-suite fact-suite (check-equal? (fact 0) 1) (check-equal? (fact 1) 1) (check-equal? (fact 2) 2) (check-equal? (fact 3) 6)

) (run-tests fact-suite 'verbose) 4 success(es) 0 failure(s) 0 error(s) 4 test(s) run 0 Higher Order Functions sort: (sort '(4 3 2 1) <) => (1 2 3 4) (sort '("one" "two" "three" "four") string '("four" "one" "three" "two") map: (map sqr '(1 2 3 4)) => (1 4 9 16) 22

Higher Order Functions filter: (filter odd? '(1 2 3 4 5)) => (1 3 5) (filter even? (1 2 3 4 5)) => (2 4) fold:

(foldr cons '() '(1 2 3 4)) => (1 2 3 4) (foldr list '() '(1 2 3 4)) => '(1 (2 (3 (4 ())))) (foldr + 0 '(1 2 3 4)) => 10 (foldl cons () (1 2 3 4)) => (4 3 2 1) (foldl list '() '(1 2 3 4)) => '(4 (3 (2 (1 ())))) (foldl * 1 (1 2 3 4)) => 24 23 Functions that Return Functions Make-adder (define (make-adder x) (lambda (y) (+ x y))) (define add1 (make-adder 1)) (add1 3) => 4

(define (make-multiplier x) (lambda (y) (* x y))) (define double (make-multiplier 2)) (double 3) => 6 24 Function Composition (define (compose f g) (lambda (x) (f (g x)))) (define add2 (compose add1 add1)) (add2 3) => 5

(define getsecond (compose first rest)) (getsecond (1 2 3 4 5)) => 2 25 Currying (define (curry f a) (lambda (b) (f a b))) (define add1 (curry + 1)) (add1 3) => 4 (define double (curry * 2)) (doulble 3) => 6

26

Recently Viewed Presentations

  • Windows Forensics - University of Washington

    Windows Forensics - University of Washington

    Windows Forensics 10 Apr 2007 TCSS431: Network Security Stephen Rondeau Institute of Technology Lab Administrator Agenda Forensics Background Operating Systems Review Select Windows Features Vectors and Payloads Forensics Process Forensics Tools Demonstration Forensics Background Inspection of computer system for evidence...
  • Montage: Architecture and Applications of an Astronomical ...

    Montage: Architecture and Applications of an Astronomical ...

    Sample Results Page Design Drivers for Mosaic Service Cluster housed at IRSA/IPAC Rapid response and high throughput Pathfinder for projects such as LSST Design Goals Inexpensive, commodity hardware Highly fault-tolerant Scaleable, extensible and distributable Portable, open source software Modular software...
  • The Book of Acts - Workers Together With Him

    The Book of Acts - Workers Together With Him

    Philippians 1:1-2. 1 Paul and Timotheus, the servants of Jesus Christ, to all the saints in Christ Jesus which are at Philippi, with the bishops and deacons: 2 Grace . be . unto you, and peace, from God our Father,...
  • Relating Fractions to Division - Effingham County Schools ...

    Relating Fractions to Division - Effingham County Schools ...

    Schimmel Relating Fractions to Division MCC5.NF.3 - Interpret a fraction as a division of the numerator by the denominator (a/b = a ÷ b). Solve word problems involving division of whole numbers leading to answers in the form of fractions...
  • Protocoale De Reţea - Ura

    Protocoale De Reţea - Ura

    NetBIOS / NetBEUI - dezvoltat iniţial de IBM şi preluat de Microsoft, utilizat în SO predecesoare lui Windows NT 4.0 (W 95, W 98) - protocol foarte eficient, rapid şi uşor de instalat, dar nerutabil utilizare limitată
  • Persuasion Techniques

    Persuasion Techniques

    Loaded Wordsand Pictures. Using words and pictures that appeal to the emotions, rather than using facts.
  • Organic Chemistry - NZ Science Class Online

    Organic Chemistry - NZ Science Class Online

    Non reactivity of alkanes (in relation to acids, alkalis, metals, water, because they are non-polar molecules).. Low melting and boiling points - intermolecular forces are weak van der Waal forces. Odour - hydrocarbons are volatile because they have weak intermolecular...
  • Chapter 5 The Psychoanalytic Approach: The Neo-Freudians Alfred

    Chapter 5 The Psychoanalytic Approach: The Neo-Freudians Alfred

    He met Anna Freud and her colleagues, acquired a Montessori teaching credential, and learned about the psychoanalytic approach. He fled the Nazis in 1933 and moved to the United States, where he published on ego psychology and proposed a psycho-social...