Class Notes (838,386)
Canada (510,872)
CS 135 (34)

CS135 - September 9-November 28, 2013

42 Pages
Unlock Document

Computer Science
CS 135
Sandy Graham

⇚ Return to University Notes index CS135 Designing Functional Programs Instructor: Name: Sandra (Sandy) Graham Email: [email protected] Office hours: Tuesdays in MC 2062/2063, Thursdays in MC 4065, 1:15-2:15 PM ISA = instructional support assistant Drop by the Tutorial Center (MC 4065) during the scheduled hours for assistance, no appointments needed. i-clicker Do this before every class: 1. Hold On/Off until power button blinks. 2. There is an i-clicker sticker on the wall, says DA. Press D and then A. 3. The Vote Status light should flash green. Programming Language Design Two important branches of language design: Imperative: frequent changes to data - Java, C++ Functional: computation of new values rather than changing old ones - LISP, ML, Haskell, Erlang, F# - closely connected to math, easier to reason about/design programs Scheme Member of the LISP family of languages. Usually no side effects - operations do not affect other ones Functional language Basic Scheme forms: ;; block comment 6 ; atom numberent "abc" ; atom string Stylistically, single line comments should use two semicolons; however, this is not required by the syntax. Primary aspects of course: Design Abstraction Refinement of old ideas Syntax, expressiveness, semantics Communication with human and computer Functions In math, functions generalize similar expressions: f(x) = x^2+4*x+2 g(x,y) = x+y Function consist of: Function name Parameters Algebraic expression of parameters Application of function: f(3) g(5,6) Application supplies arguments (the values) that correspond to the parameters. In math, application is evaluated by substitution: f(g(5,6)) = f(5+6) = f(11) = 11^2+4*11+2 = 167 Evaluation can be done in any order: g(g(1,3),f(2)) = g(1+3,f(2)) or g(1,3) + f(2) The Scheme interpreter (program that evaluates Scheme code) uses a left to right, depth-first evaluation order - inside-out, left to right. Math is written in infix notation - the operator is placed between its operands. There are also notations known as prefix and postfix notation - operator before operands, and operator after operands, respectively. Scheme uses prefix notation. Prefix notation needs no order of operations because there is no ambiguity. Convert infix to prefix: (6-4)/(5+7) What is the last operator to be applied? / (6-4) (5+7) Repeat process. / - 6 4 + 5 7 This is valid prefix notation, but not valid Scheme. Since in Scheme arbitrary numbers of operands are supported, we need to add brackets to make it explicit. (/ (- 6 4) (+ 5 7)) Conversion is done by moving the last operator to be applied to the beginning of the subexpression until no infix operators remain. Operand order remains the same. Prefix Notation If we treat infix operators as functions, we don't need to use parentheses to specify order of operations: 3 - 2 ;infix notation -(3, 2) ;prefix notation Convert to prefix notation: (((3+8)-(7+9))/12) ;infix notation / ((3+8)-(7+9)) 12 / - (3+8) (7+9) 12 / - + 3 8 + 7 9 12 ;prefix expression (/ (- (+ 3 8) (+ 7 9) 12)) ;scheme code Scheme code needs the brackets in order to support arbitrary numbers of parameters. DrRacket Racket (Scheme) development environment. DrRacket has interactions and definitions panes. Definitions are persistent and are saved on permanent storage. Interactions are realtime and users interact with programs here, but are not saved. The interactions pane is a REPL (read-eval-print-loop), a way to write some code, execute it, and get results immediately. Integers in Scheme are unbounded - they can be arbitrarily large without fear of overflows. Rational numbers in Scheme are represented and computed exactly, without any loss in precision. Scheme tries to use exact numbers whenever possible. When an exact value is not possible, such as with irrational numbers, they are marked as inexact. Inexact values taint all computations it is used in with inexactness. (sqrt 2) evaluates to #i1.414213562370951 ; #iX represents a literal inexact value (expt 2 100) evaluates to 1267650600228229401496703205376 ;exact (/ -5 12) evaluates to $-\frac{5}{12}$ ;exact #i1.23 ;inexact 1.2e12 ;exact 1.234567 ;exact 12345 ;exact Common errors: Mismatched brackets: (+ 1 2 Infix operators(1 + 2) Runtime errors: (/ 3 (- 2 2)) (division by 0) The stepper tool is useful for tracing execution one step at a time. Scheme is a dynamically typed language - types do not need to be declared. Contracts are not enforced by the language since they are just comments. However, we can explicitly check for types to catch errors. This contrasts with statically typed languages such as Java, where the type is associated with identifiers and only certain values are allowed to be stored in them. Types are associated with values, but not with identifiers such as parameters or constants. Definitions Defining functions in math: f(x) = x 2 This follows the general pattern name(formal_parameters) = body In Scheme, this is writt(define (name formal_parameters) body) . For example: (define (sum x y) (+ x y)) is equivalent to sum(x,y) = x + y This is called with something like the following: (sum 5 6) ; 5 and 6 are the arguments define is a special form. It looks like a Scheme function, but its arguments are not necessarily evaluated, and this form may do something special normal functions cannot.define binds a name to an expression. A definition can only be defined oncedefine cannot be used twice on the same identifier. However, redefinition is possible in the full Scheme language. All operators in scheme are actually just functi+n,-,sqrt are predefined in the environment when the program starts. This means that they can be redefined, too. Evaluate (* (- 6 4) (+ 3 2)) : (* (- 6 4) (+ 3 2)) (* 2 (+ 3 2)) (* 2 5) 10 On paper: (* (- 6 4) (+ 3 2)) ▯ (* 2 (+ 3 2)) ▯ (* 2 5) ▯ 10 Functions are applied via substitution, as in math. There is only one solution to every possible expression - there is no ambiguity. Functions can only return one value. Constants Constants do not accept parameters, and simply have a constant value: (define pi 3.1415926535) (define density (/ mass volume)) Orders of definitions are not important at this point. Definitions can be done in any order. Constants are a special case of definitions. Constants are only evaluated once, and are not evaluated again upon substitution. Scope Inner scopes override outer scopes: (define x 3) (define (f x) (* x x)) (f 4) ; in the body of f, x is 4, since the parameter is in the inner scope and overrides x=3 in the outer scope Every function has its own scope. Scopes are environments where bindings exist. 17/9/13 Constants have various advantages: Gives meaningful names to magic numbers. Reduces typing and errors if values need to be changed. Makes programs easier to understand. Constants are sometimes called variables, but are generally not changed. Unevaluated code is highlighted in black. Tests try to evaluate all possible code paths and all the highlighting should disappear. Scheme programs are sequences of definitions and expressions. Expressions are evaluated using substitution to produce values. Expressions may use special forms sucdefine, which may not necessarily behave in the same way as normal expressions. The Design Recipe Programs are acts of communication: between person and computer, between person and same person in the future, and between person and others. ; comments start with a semicoolon and go on until the end of the line Block comments are comments that generally go on for multiple lines. These are, by convention, written with two semicolons: ;; block comments ;; generally apepar at the beginning of files ;; and before functions Every function must follow the design recipe - a development process that leaves behind a written explanation of development. Design recipes result in robust and reliable functions that are easy to understand. The five parts of the design recipe are, in order of submission: Contract: information for the user - function signature - argument types and descriptions, return types and descriptions. Purpose: description of what the function is designed to compute - what it produces or returns. Examples: clarification of the general use of the function and what usage of it looks like. Should represent each part of the data definition. Definition: The Scheme header and body of the function. Tests: a representative set of inputs and expected outputs showing that the function works - expected outputs must be calculated by hand or some other source. Examples are similar to tests, but tests generally only show the function works while examples show people how to use it. There are usually more tests than examples. Recommended order of execution: Write contract. Write purpose. Write examples. Write definition body. Write tests. Write a function that sums the squres of two numbers: Contract: ;; sum-of-squares: Num Num -> Num Purpose: ;; Purpose: produces the sum of squares of arg1 and arg24 Examples: ;; Examples: (check-expect (sum-of-squares 3 4) 25) (check-expect (sum-of-squares 0 2.5) 6.25) Body: (define (sum-of-squares arg1 arg2) (+ (sqr arg1) (sqr arg2))) Tests: (check-expect (sum-of-squares -1 2) 5) (check-expect (sum-of-squares 0.01 1000) 1000000.0001) (check-expect (sum-of-squares 50 -28) 3284) (check-expect (sum-of-squares 1/25 65) 4225.0016) Types used in contract (case sensitive): Num: any Scheme numeric value Int: any integers Nat: natural numbers Boolean: Boolean value Symbol: symbolic value String: string value Char: character value Any: any type of value Tests should be written after the code body. They should be small and focused with a clear purpose. (check-expect (+ 1 2) 3) ; checks that a value is exactly equal to another (check-within (sqrt 2) 1.414 0.001) ; checks that a value is equal to another within a tolerance (check-error (/ 1 0) "/: division by zero") ;checks that a certain error occurs These are special forms and are evaluated at the end. A summary of the test results are shown in the interactions window. Write a function that rounds to a given number of decimal places: ;; round-to: Num Int -> Num ;; Purpose: produces the value given rounded to a given number of decimal places ;; Examples: (check-expect (round-to 1.25 1) 1.2) (check-expect (round-to 23.45 -1) 20) (define (round-to value decimal-places) (/ (round (* value (expt 10 decimal-places))) (expt 10 decimal-places))) ;; Tests (check-expect (round-to 1.25 1) 1.2) ; round down towards even number (check-expect (round-to 1.35 1) 1.4) ; round up towards even number (check-expect (round-to 12.3 5) 12.3) ; fewer decimal places than requested (check-expect (round-to 12 0) 12) ; boundary condition We can put ... as a placeholder for the function body before actually writing the body. If the contract is violated, the result may be undefined. For ex(round-to 3 0.5) . Starting with the Intermediate Student teaching language, helper functions that supplement a wrapper function need only a contract and purpose if the wrapper function obeys all of the following: One line of code in the body. Includes a function application of the helper function with modified or additional parameters. Mutually recursive functions, should be directly adjacent. They only need one set of examples and tests for all of them, but each one still neesd a contract and purpose. The tests for the wrapper function, however, must fully test the helper function as well. Templates are useful, but are not required to unless specifically requested to, or for custom data types. See "Generative Recursion and the Design Recipe" for more concerns when using the design recipe with generative recursion. 19/9/13 Boolean Values Scheme represents Boolean values with the liter#ts and #f (true and false are also usable in the Scheme teaching languages), representing true and false respectively. The equality functio(= x y) ((= Num Num) -> Boolean ) tests whether two numbers are equal and results in a boolean value. (< x y) and (>= x y) behave similarly. Predicates are expressions that result in Boolean values. They are, by convention, given names that end with a question mark. For example, (even? x) is clearly a predicate. The most common Boolean operators are (and x y ...) , (or x y ...) , and(not x) . They represenx ∧ y x ∨ y , and¬x , respectively. Scheme has no inequality (not-equals) operator. However, it can be implemented as foll(not (= x y)) . Scheme uses short circuit evaluation. and and or, if the result of the expression is known before the evaluation is complete, the rest is not evaluated: Ifor has a true argument, it knows that the result must be true regardless of other argum(or #t (/ 1 0)) will not give an error, since the division is never evaluated. Ifand has a false argument, it knows that the result must be false regardless of other argu(and #f (/ 1 0)) will not give an error, since the division is never evaluated. This is made possible band and or being special forms. Many types have an equality predicate, lsymbol=? and string=? , which should be used whenever possible. However, if the types of the operands are not known befrehand,(equal? x y ...) can be used to check that they are compatible types and that they have the same value. This does not work with inexact numbers. Strings Strings are denoted by double quotes"CS135" ,"abc" ,"". The length of a string is determined w(string-length x) . We determine if a value is a string with the predicate function (string? x) . We concatenate strings usin(string-append x y ...) String comparisons are done based on ASCII values. Symbols Symbols are denoted by a single quote'symbol . A symbol represents a particular idea. They are used to define a finite set of values, each one with a name. Symbols can only be compared, not manipulated like with strings. Write a predicate function that checks if the input is a valid multiple choice answer: ;; valid-choice: Any -> Boolean ;; Purpose: produces true when the answer is one of "A", "B", "C", "D", false otherwise. ;; Examples: (check-expect (valid-choice? 123) #f) (check-expect (valid-choice? "C") #t) (define (valid-choice? value) (and (string? value) (or (string=? value "A") (string=? value "B") (string=? value "C") (string=? value "D")))) ;; Tests (check-expect (valid-choice? "A") true) (check-expect (valid-choice? "B") true) (check-expect (valid-choice? "C") true) (check-expect (valid-choice? "D") true) (check-expect (valid-choice? "potato") false) (check-expect (valid-choice? 123) false) Conditional Expressions The special forcondis used to write conditionaal expressions in Scheme. Each argument is a question/answer pair, where the question is a boolean expression: (cond [(< x 0) (- x)] [(>= x 0) x]) The above results in the absolute vax.e of Square brackets are used by convention. Square brackets are equivalent to parentheses in the teaching languages. cond evaluates the question in each pair from top to bottom. As soon as one is true, its associated answer is evaluated and returned. If no pair matches, a runtime error is generated. The last pair can use the queelseto always match: (cond [(= 1 2) 3] [(= 4 5) 6] [else 7]) Write a program that converts a numeric grade to a letter grade: (define (convert-grade percentage advanced?) (string-append (cond [(>= percentage 80) "A"] [(>= percentage 70) "B"] [(>= percentage 60) "C"] [(>= percentage 50) "D"] [else "F"]) (cond [advanced? "+"] [else ""]))) When testingcond statements, test values on boundaries, and test values for each case. A statement with 4 cases might need 7 tests. 24/9/13 Simplifying Conditionals If a question is asked, we know that all the questions before it are false. For example, we can simplify the following: (cond [(< grade 50) 'fail] [(and (< grade 60) (>= 50)) 'poor] [(>= grade 60) 'acceptable]) Into the following: (cond [(< grade 50) 'fail] [(< grade 60) 'poor] [else 'acceptable]) For conditional expressions, each question and answer should have one corresponding tests. The tests should be simple and directly test a particular answer. More tests are appropriate at boundary points as well. In the above case, good test values would be 40, 50, 55, 60, and 70. Every way each argument could be false needs to be false, and each one needs a test. Some tests are based on the problem description - these are black-box tests. They are not based on anything in the code, such as implementation details. Some tests are based on the code itself - these are white-box tests. They may check things like specific conditionals or boolean expressions. Both types of testing are important. Helper functions generalize similar expressions, and help avoid overly complex expressions. Helper functions should use meaningful names and must follow the design recipe. Syntax/Semantics Syntax is the way we're allowed to say things. Semantics is the meaning of what we say. Ambiguity is the property of sentence having multiple meanings. Scheme programs must have correct syntax, meaningful semantics, and be unambiguous. Syntax Grammars enforce syntax and avoid ambiguity. For example, an English sentence might be described as follows: = The grammar is the syntactic model of the Scheme language. Semantics A semantic model provides a way to predict the result of running any program. Ellipses...) can represent omissions, indicate patterns, and more. Pattern ellipses often represent multiple arguments or parameters. A semantic model for Scheme is based on substitution, where we step through the program one substitution at a time: 1. Find the leftmost (from beginning) expression that can have a rule applied to it. A rule can only be applied if the expression depends only on simple values. Otherwise, the non-simple values need to be simplified first. 2. Rewrite it according to the substitution rules: Built-in function applications become their values. (f ...) => (result of evaluating f(...)) User defined function applications become their bodies, with arguments inserted. when (define (f ...) e) occurs to the l(f ...) => (e with substitution of parameters for arguments) Constants become their values. when (define x ...) occurs to the lxf=> ... Conditional expressions become an answer if a question is true, or lose a question/answer pair otherwise. (cond [true e]) => e (cond [false e] ...) => (cond ...) (cond [else e]) => e And and or become short circuiting arguments, and lose non-short-circuiting arguments. (and false ...)=> false (and true ...)=> (and ...) (and) => true (or true ...)=> true (or false ...)=> (or ...) (or) => false Structure constructors stay as-is, though arguments are simplified. (make-posn ...)=> (make-posn ...) (make-posn 8 1)=> (make-posn 8 1) Structure selectors become the value of its corresponding field. (posn-x (make-posn 4 2))=> 4 Structure predicates become a boolean representing whether the argument is an instance of the structure. (posn? (make-posn 1 2))=> true (posn? 5)=> false Lists stay as-is, though arguments are simplified. (cons 1 (cons 2 empty))=> (cons 1 (cons 2 empty)) (list 1 2 3 4 5)=> (list 1 2 3 4 5)in "Beginner Student with List Abbreviations" and above. Local definitions are renamed, rebound, and hoisted. See "Local Definitions and Lexical Scope" for more details. (local [(define x ...) ...] ...)=> (define (new name for x) ...) (body of local with x substituted with the new name for x) (local [(define (f ...) ...) ...] ...)=> (define ((new name for f) ...) ...) (body of local with f substituted with the new name for f) Anonymous functions become their bodies, with arguments inserted. ((lambda (x) (* x 2)) 5)=> (* 5 2) 3. This is one evaluation step. Return to step 1 until the entire expression is in the simplest possible form, or results in an error. Note that constant and function definitions are already in their simplest form. These rules may differ from those in DrRacket's stepper feature. Evaluating a program by stepping through is called tracing. In more complex programs, condensed traces are used - traces that can skip multiple steps to show only important parts. Trace(term (- 3 1) (+ 1 2)) given(define (term x y) (* x (sqr y)): (term (- 3 1) (+ 1 2)) => (term 2 (+ 1 2)) => (term 2 3) => (* 2 (sqr 3)) => (* 2 9) => 18 => (simplest form) Trace(cond [( > 3 4) x]): (cond [( > 3 4) x]) => (cond [false x]) => (cond) => (error: no questions answered) Templates The form of a program should mirror the form of the data. A template is a general outline of code that consumes some type of data, that we can fill in to create a program. Templates must appear after data definitions and before function definitions. We start by making the template of a function, and then flesh out the template to create the finished function. For every form of data, we create a template and use it to write functions that work with that type of data. Templates should be commented out in Scheme code due to issues with MarkUs. For example, a template for a list of a datatXpmight appear as follows: ;; my-listof-x-fn: (listof X) -> Any ;; (define (my-listof-x-fn lox) ;; (cond ;; [(empty? lox) ...] ;; [else (... (first lox) ... ;; (my-listof-x-fn (rest lox)) ...)])) The template must always produce Any since we don't know what type of data it will give. Templates only require the contract, but functions written using a template still require the full design recipe. Structures Structures are a bundling of several values into one. They are complex values. They work only with finite sets of values, and have a fixed size and field count. For example, a structure might represent a product in an online store. It would store, for example, the name (String), product ID (Nat), price (Num), and availability (Boolean). The two parts of a structure definition is the code and the data definition: ;; this is the code part (define-struct product (name product-id price availability)) ;; this is the data definition part ;; A Product = (make-product String Nat Num Boolean) ; use CamelCase in data definitions define-struct is a special form that defines a structure and a set of corresponding helper functions. Here, Racket has made a number of functions automatically: make-product - the constructor creates an instance of the struture, and is nmake-{x} , where{x} is the structure name. product-name ,product-product-id ,product-price ,product-availability - the selector functions obtain a particular field in the structure, and are name{x}-{y} , where {x} is the structure name and{y} is a field name. product? - the type predicate checks if a particular value is an instance of the structure, and ar{x}?, where {x} is the structure name. We can now work with this structure: (define item (make-product "Television" 412 899.99 false)) (product? item) => true (product-name item) => "Television" Structures are immutable - they cannot be changed. Once created, they remain the same. Structures can contain structures. In contracts, product structures can now be referencedProduct . For example:fake-product: String Boolean -> Product . In the Scheme teaching languages, thePosn structure is defined, and is designed to represent a 2D coordinate. ;; distance: Posn Posn -> Num ;; Purpose: productes the Euclidean distance between `p1` and `p2` ;; Examples: (check-expect (distance (make-posn 1 1) (make-posn 4 5)) 5) (define (distance p1 p2) (sqrt (+ (sqr (- (posn-x p2) (posn-x p1))) (sqr (- (posn-y p2) (posn-y p1)))))) In code, the structure name is lowercase. In contracts, data definitions, and a few other places, the name is written in CamelCase - each word is capitalized, and dashes are removed. Templates The template is written right after the data definition. A template for a function that consumes a structure selects every field in the structure, even if the function itself doesn't use all of them. When we want to write a function, we write it based on the template: ;; product-fn: Product -> Any (define (product-fn prod) (... (product-name prod) ... ... (product-id prod) ... ... (product-price prod) ... ... (product-availability prod))) We use Any since we don't know what it returns yet. This needs to be reviewed later when actually writing the function. We then fill in the placehol..., to create the finished function: (define (change-price prod price) (make-product (product-name prod) (product-id prod) price (product-availability prod))) 1/10/13 For each new structure type, we need: data analysis: looking at the problem, we need to determine if there is a need for compound data type. data definition: describe the compound data type - what each field is, what they are used for. template: describe the basic structure of functions that consume this type, after the data definition. In contracts, we can use atomic data types as well as data definition names (capitalized). It is best to define constants for tests and examples to represent structures, in order to shorten the code. Data definitions Unions (define-struct movieinfo (name director)) ;; A MovieInfo = (make-movieinfo String String) (define-struct mp3info (title length)) ;; An Mp3Info = (make-mp3info String Num) ;; THIS IS A UNION TYPE ;; A MultimediaInfo is one of: ;; * a MovieInfo ;; * an Mp3Info ;; THIS IS THE TEMPLATE FOR A FUNCTION THAT CONSUMES THE UNION TYPE ;; my-multimediainfo-fn: MultimediaInfo -> Any (define (my-multimediainfo-fn info) (cond [(movieinfo? info) (... (movieinfo-name info) ... ... (movieinfo-director info) ...)] [(mp3info? info) (... (mp3info-title info) ... ... (mp3info-length info) ...)])) Now when we write a function, we use the template as a basis: ;; multimediainfo-identifier: MultimediaInfo -> String ;; WE CAN ALSO WRITE THE CONTRACT AS ;; multimediainfo-identifier: (union MovieInfo Mp3Info) -> String (define (multimediainfo-identifier info) (cond [(movieinfo? info) (movieinfo-name info)] [(mp3info? info) (mp3info-title info)])) In the above code, the union data MultimediaInfo (also known a(union MovieInfo Mp3Info) ) represents eitheMovieInfo or anMp3Info . Data definitions do not necessarily need to correspond to any structures in the code: ;; A Nat is an integer greater than or equal to zero Above we defined the natural number, but there is no data type in Scheme that corresponds to this. It is intended for the human readers. Error Checking (define (safe-make-posn x y) (cond [(and (number? x) (number? y)) (make-posn x y)] [else (error "numerical arguments required")])) ;; Tests (check-expect (safe-make-posn 2 3) (make-posn 2 3)) (check-error (safe-make-posn 2 'abc) "numerical arguments required") We generally assume inputs are valid unless explicitly required to do error checking. Lists A recursive definition defines something in terms of itself. A list is a compound data type. It is a recursively defined. They are known as "cons" types. A list of 5 numbers is a number followed by a list of 4 numbers. A list of 4 numbers is a number followed by a list of 3 numbers. A list of 3 numbers is a number followed by a list of 2 numbers. A list of 2 numbers is a number followed by a list of 1 numbers. A list of 1 numbers is a number followed by a list of 0 numbers. A list of 0 numbers is the base case and handled specially. Lists in Scheme are similar to singly linked lists. We have access only to the first element and the rest of the list. Basic list constructs empty - list of 0 elements. (cons element rest) (construct) - creates a list value followed byrest . (first list) - obtains the first element of non-empty llist. (rest list) - obtains the (possibly empty) list of all the elements of non-emplisti, excluding the first. (empty? list) - determines whether listlist is empty. (cons? value) - determines whether value value is a cons type (except fempty). (member? element list) - determines whether element is contained inlist. (length list) - obtains the number of elements inlist. List operations (cons 'a (cons 'b (cons 'c empty))) This is a list'a, 'b, and'c , in that order. To append lists, we cannot us(cons list1 list2) . This would simply create a list with the first elemenlist1n, and the rest being list2 . For list appending, we can use the built-in fuappend . 3/10/13 A list is one of: empty - the empty list. (cons element list) - a recursive list definition. Data Definitions and Templates For each new list type, we need: data analysis: looking at the problem, we need to determine if there is a need for a recursive data type. data definition: describe the recursive data type - what each element is, what the base cases are. template: describe the basic structure of functions that consume this type, after the data definition. The template is written right after the data definition. It is based on the data definition and so appears gcondalexpression with one qeustion/answer pair for each possibility. Self-referential data definition clauses lead to recursion in the template, while base cases do not. Example of a list of strings: ;; A ListOfStrings is either ;; * empty or ;; * (cons String ListOfStrings) ;; Template for ListOfStrings ;; my-los-fn: ListOfStrings -> Any (define (my-los-fn los) (cond [(empty? los) ...] ; base case [else (... (first los) ... ... (my-los-fn (rest los) ...))])) We can write ListOfStrings (or alternativel(listof String) ) in data definitions. (listof X) notation is shorter and does not require any other definitions. HeXerepresents any type, even a list or structure. The implicit template when using(listof X) is as follows: ;; my-listof-X-fn: (listof X) -> Any (define (my-listof-X-fn lst) (cond [(empty? lst) ...] [else (... (first lst) ... (my-listof-X-fn (rest lst)) ...)])) Sometimes we need non-empty lists. A data definition could be written(ne-listof X) , or using a definition like the following: ;; A NeListOfStrings is either ;; * (cons String empty) or ;; * (cons String NeListOfStrings) ;; Template for NeListOfStrings ;; my-nelos-fn: NeListOfStrings -> Any (define (my-nelos-fn nelos) (cond [(empty? (rest nelos)) ; base case (... (first nelos) ...)] [else (... (first nelos) ... ... (my-los-fn (rest nelos) ...))])) Function that makes an acronym from a list of strings: ;; make-acronym: ListOfStrings -> String ;; Purpose: produces an acronym formed by the first letter of each of the elements of `strings`. ;; Examples: (check-expect (make-acronym (cons "Kentucky" (cons "Fried" (cons "Chicken" empty)))) "KFC") (define (make-acronym strings) (cond [(empty? strings) ""] [else (string-append (substring (first strings) 0 1) (make-acronym (rest strings)))])) Recursion Recursive definitions should have a base case. This allows the recursion to eventually terminate. It should also always be possible to get closer to the base case upon each step. It may not have to happen for every call, but it must eventually reach the base case. If either of these are not true, it may result in infinite recursion, when the function calls itself indefinitely. Structural recursion, as opposed to generative recursion, is recursion guided by the data definition - the form of the code matches the form of the data definition. In other words, our functions should follow the template closely and work with the first element of the list and recurse only with the rest of the list. Pure structural recursion requires that at every call of the recursive function, all parameters are either unchanged or one step closer to the base case. The parameters should be driving the recursion, while everything else stays unchanged. Mutual recursion is recursion involving two or more functions that call each other recursively. It occurs when we have data definitions that refer to each other. Care must be taken to ensure that the base case is eventually reached. Data definitions can be mutually recursive: A NestedThing is one of: * empty * (listof OtherThing) A OtherThing is one of: * Symbol * (list Symbol NestedThing) Condensed Traces A condensed trace is a way of writing traces that skips the excessive detail that would result from a full trace. Here, we skip steps to show only the most important information. It is always important to specify whether a trace is condensed or full. For example, we might do a condensed trace of a function as follows: (make-acronym (cons "Kentucky" (cons "Fried" (cons "Chicken" empty)))) => (string-append "K" (make-acronym (cons "Fried" (cons "Chicken" empty)))) => (string-append "K" (string-append "F" (make-acronym (cons "Chicken" empty)))) => (string-append "K" (string-append "F" (string-append "C" (make-acronym empty)))) => (string-append "K" (string-append "F" (string-append "C" ""))) => "KFC" This better shows the way the application of the recursive function leads to the application of that function to a smaller list, until the base case is reached. There aren't strict rules for condensed traces, since everyone might have a different idea of what is an important step. It is possible to condense more or less depending on whether it makes the trace more clear. 8/10/13 Strings are used to represent text. In Scheme, strings are actually sequences of characters. (string->list "abc ") -> (cons #\a (cons #\b (cons #\c (cons #\space empty)))) (list->string (cons #\a (cons #\b (cons #\c (cons #\space empty))))) -> "abc " Characters are denoted #\a, wherea represents the character value - in this case, a lowercase A. ;; replace-space: String -> String ;; Purpose: produces a copy of `str` where all spaces are replaced by underscores. ;; Examples: (check-expect (replace-space "") "") (check-expect (replace-space "CS 135") "CS_135") ;; THIS IS A WRAPPER FUNCTION; IT MAINLY CALLS ANOTHER FUNCTION TO DO THE ACTUAL WORK (define (replace-space str) (list->string (replace-space-list (string->list str)))) ;; Tests: ;; NOT INCLUDED FOR BREVITY ;; replace-space-list: (listof Char) -> (listof Char) ;; Purpose: produces a copy of `loc` where all #\space is replaced by #\_ ;; Examples: (check-expect (replace-space-list empty) "") (check-expect (replace-space (cons #\C (cons #\S (cons #\space (cons #\1 (cons #\3 (cons #\5 empty))))))) (cons #\C (cons #\S (cons #\_ (cons #\1 (cons #\3 (cons #\5 empty))))))) (define (replace-space-list loc) (cond [(empty? loc) empty] [else (cons (cond [(char=? (first loc) #\space) #\_] [else (first loc)]) (replace-space-list (rest loc)))])) ;; Tests: ;; NOT INCLUDED FOR BREVITY Nested Templates Template for a Polygon: ;; A Polygon is one of: ;; * empty ;; * (cons Posn Polygon) (define (my-polygon-fn poly) (cond [(empty? poly) ...] [else (... (first poly) ... ... (my-polygon-fn (rest poly)) ...)])) However, we know that (first poly) is a Posn. So we should refer to its template: (define (my-polygon-fn poly) (cond [(empty? poly) ...] [else (... (my-posn-fn (first poly)) ... ... (my-polygon-fn (rest poly)) ...)])) (define (my-posn-fn p) (... (posn-x p) ... ... (posn-y p) ...)) Alternatively, it is possible to combine the two templates: (define (my-polygon-fn poly) (cond [(empty? poly) ...] [else (... (... (posn-x p) ... ... (posn-y p) ...) ... ... (my-polygon-fn (rest poly)) ...)])) A data definition for Nat: ;; A Nat is one of: ;; * 0 ;; * (add1 Nat) ;; NATURAL NUMBERS START AT 0 IN COMPUTER SCIENCE AND LOGIC ;; TEMPLATE FOR NATURAL NUMBERS (define (my-nat-fn n) (cond [(<= n 0) ...] ; WE USE <= HERE INSTEAD OF zero? IN ORDER TO CATCH NEGATIVE OR FRACTIONAL INPUTS. THIS IS DEFENSIVE PROGRAMMING [else (... (my-nat-fn (sub1 n)) ...)])) ;; WE USE THE INVERSE OF THE `add1` FUNCTION TO GET THE NUMBER `x` SUCH THAT `(add1 x)` IS `n` A natural number like 5 would therefore be representable as somethin(add1 (add1 (add1 (add1 (add1 0))))) . This is similar to the recursive formulation of a list. Since in each call we need to get closer to the base case, we need to invert the funsub1nto get closer to the base case. This isn't the usual way we'd think of numbers, but writing it in the form of a data definition allows us to make good templates that consume this type of data. Countdown example: ;; countdown-to: Int Int -> (listof Int) ;; Purpose: produces a list of integers from `start` to `end` ;; Examples: ;; NOT INCLUDED FOR BREVITY (define (countdown-to start end) (cond [(<= start end) (cons end empty)] [else (cons start (countdown-to (sub1 start) end))])) 10/10/13 We can denote subsets of certain sets using subscript notation: Natural numbers:Z≥0 Negative integerZ: <0 Real numbers greater than 10R>100 In data definitions, we can represent this as follows: ;; ascii->listofchar: Nat[<256] Nat[<256] -> (listof Char) Here,Nat[<256] is equivalent N<256, or natural numbers less than 256. Other possible uses of the square braket notation are Int[>=20] ,String[0] -> Boolean ;; Purpose: produces true if `n` is prime and false otherwise ;; Examples: (check-expect (prime? 1) false) (check-expect (prime? 2) true) (check-expect (prime? 4) false) (define (prime? n) (not (or (= n 1) (has-factors? 2 n)))) ;; Tests: ;; OMITTED FOR BREVITY ;; has-factors?: Nat[>1] Nat[>0] -> Boolean ;; Purpose: produces true if any numbers between `factor` and one less than `n` divide `n`, and false otherwise ;; Examples: ;; OMITTED FOR BREVITY (define (has-factors? factor n) (cond [(>= factor n) #f] [(zero? (remainder n factor)) #t] [else (has-factors? (add1 factor) n)])) ;; Tests: ;; OMITTED FOR BREVITY Consider a basic list sorting function template: (define (sort list) (cond [(empty? list) ...] [else (... (first list) ... (sort (rest list)) ...)])) Now we need to do something with the first element of the list and the (assumed sorted) rest of the list. Whainsert,n do is use a helper function that inserts an element into a list in sorted order: (define (sort list) (cond [(empty? list) empty] [else (insert (first list) (sort (rest list)))])) We simply need to assume that when we calsort , we will get a sorted list, aninsert will correctly insert the element in sorted order. We start with a template for the insertion function: ;; insert: Any (listof Any) -> (listof Any) (define (insert element list) (cond [(empty? list) ...] [else (... (first list) ... (insert element (rest list)) ...)])) We can assume the list is in sorted order since it will only ever be called on tsort. So we just need to put it at the beginning if it's already in the proper place, or recurse to put it in the correct place in the rest of the list: ;; insert: Num (listof Num) -> (listof Num) ;; Purpose: produces a list equal to `list` except with `element` inserted in sorted order ;; Examples: (check-expect (insert 1 (list 2 3)) (list 1 2 3)) (check-expect (insert 2 (list 1 3)) (list 1 2 3)) (define (insert element list) (cond [(empty? list) (cons element empty)] [(<= element (first list)) (cons element list)] [else (cons (first list) (insert element (rest list)))])) ;; Tests: (check-expect (insert 1 (list 2 3)) (list 1 2 3)) (check-expect (insert 2 (list 1 3)) (list 1 2 3)) (check-expect (insert 2 empty) (list 2)) Together, this forms a sorting function based on the insertion sort algorithm. List Abbreviations Lists can be written in a few ways. All of the following are equivalent: (cons 3 (cons (cons 'a (cons 'b empty)) (cons "test" (cons #\a empty)))) (list 3 (list 'a 'b) "test" #\a) '(3 (a b) "test" #\a) - only available starting in "Beginning Student with List Abbreviations". In the quoted part, only symbols, numbers, strings, and lists are allowed. No quotes are used inside the outer '()cis the same aempty . We use list for lists of fixed size, where the length of the list is known beforehand. Wconsifor constructing a list of variable length. In data definitions, we can use notation(list String Num) to represent a list with the first element being a string, and the second a number. We can simulate structures with lists - each element could hold a field, and the list itself would be a collection of fields, just like a structure. This could be useful for things like type unions, where instead of writing very similar code for two different types of structures, we simply use lists for both and assume the needed fields are at the same place in both types of lists. Beginning Student with List Abbreviations also has extra functions for working with lists: (second list) is equivalent t(first (rest list)) . It obtains the second element of a list. (third list) is equivalent t(first (rest (rest list))) . It obtains the third element of a lsit. ... (eighth list) is equivalent t(first (rest (rest (rest (rest (rest (rest (rest list)))))))) . It obtains the eighth element of a list. 15/10/13 Dictionaries Dictionaries are abstract data types (not a primitive type, but a commonly used pattern). They are associations of keys with values. A telephone directory is a dictionary - the names are the key, which we use to look up phone numbers, which are the values. Keys must be unique in a dictionary - there can be no duplicates. However, values do not need to be unique. The most important operations on dictionaries are: Lookup - given a key, produce the value associated with it. Add - add a new key and its associated value. Remove - given a key remove it and the value associated with it. The actual implementation of the dictionary is dependent on what we want from it. For example, some implementations might have faster lookup but slower add and remove. Association Lists This is simply a list of key/value pairs: ;; An AL is one of: * empty * (cons (list Num String) AL) ;; Template for AL: ;; my-al-fn: AL -> Any (define (my-al-fn al) (cond [(empty? al) ...] [else (... (first (first al)) ... ... (second (first al)) ... ... (my-al-fn (rest al)) ...)])) ;; OR USE (listof (list Num String)) Now we can implement a few operations on this data type: ;; al-lookup: AL Num -> (union String false) ;; Purpose: produces the value associated with `key` in `al` if it exists, and false otherwise ;; Examples: ;; OMITTED FOR BREVITY (define (al-lookup al key) (cond [(empty? al) false] ; false represents the element not being found [(= key (first (first al))) (second (first al))] [else (al-lookup (rest al) key))])) ;; Tests: ;; OMITTED FOR BREVITY ;; al-remove: AL Num -> AL ;; Purpose: produces an AL equal to `al` without the key `key` ;; Examples: ;; OMITTED FOR BREVITY (define (al-remove al key) (cond [(empty? al) empty] [(= key (first (first al))) (al-remove (rest al) key)] [else (cons (first al) (al-remove (rest al) key))])) ;; Tests: ;; OMITTED FOR BREVITY Processing Multiple Lists Processing one list Consider an appending function: ;; my-append: (listof Any) (listof Any) -> (listof Any) (define (my-append list1 list2) (cond [(empty? list1) list2] [else (cons (first list1) (my-append (rest list1) list2))])) This uses only structural recursilist2 does not change between calls. Note that the run time of this function depends on the lenglist1 . Ilist1 is very large, the function may need a significant amount of time to run. Processing in lockstep If both lists are of the same length, we can assume that the first list will be empty if and only if the second is. Consider a dot product function: ;; dot-product: (listof Num) (listof Num) -> Num (define (dot-product vec1 vec2) (cond [(empty? vec1) 0] [else (+ (* (first list1) (first list2)) (dot-product (rest vec1) (rest vec2)))])) Processing at different rates There are four possible cases to consider if the two lists are of differing lengths. Both are empty. The first is empty, but the second isn't. The second is empty, but the first isn't. Both are non-empty. This is reflected in the template: ;; my-double-list-fn: (listof Any) (listof Any) -> Any (define (my-double-list-fn list1 list2) (cond [(and (empty? list1) (empty? list2)) ...] [(and (empty? list1) (cons? list2)) ...] [(and (cons? list1) (empty? list2)) ...] [else ...])) Consider an element count test function: ;; minimum-occurrences?: (listof Any) Any Nat -> Boolean ;; Purpose: produces true if `value` appears in `list` at least `count` times, and false otherwise ;; Examples: ;; OMITTED FOR BREVITY (define (minimum-occurrences? list value count) (cond [(<= count 0) true] [(empty? list) false] [(equal? value (first list)) (minimum-occurrences? (rest list) (sub1 count))] [else (minimum-occurrences? (rest list) count)])) ;; Tests: ;; OMITTED FOR BREVITY Consider a list comparison function: ;; list=?: (listof Any) (listof Any) -> Boolean ;; Purpose: produces true if `list1` and `list2` are equal, and false otherwise ;; Examples: ;; OMITTED FOR BREVITY (define (list=? list1 list2) (cond [(and (empty? list1) (empty? list2)) #t] [else (and (cons? list1) (cons? list2) (equal? (first list1) (first list2)) (list=? (rest list1) (rest list2)))])) ;; Tests: ;; OMITTED FOR BREVITY 17/10/13 Types of Recursion Pure structural recursion Structural recursion is based on a recursive data definition - it is driven by and follows the form of the data definition. On each call, all parameters must be either unchanged, or one step closer to a base case according to the data definition. However this can have disadvantages. Consider a function finding the maximum element of a list, written in pure structural recursion style: ;; list-max: (ne-listof Num) -> Num (define (list-max list) (cond [(empty? (rest list)) (first list)] [(>= (first list) (list-max (rest list))) (first list)] [else (list-max (rest list))])) In the worst case - a strictly increasing list - the function will call itself twice for each step, which means it takes exponential time based on the length of the list. Accumulative recursion/Structural recursion with an accumulator This is similar to pure structural recursion, but it can also have parameters with partial answers. Consider a function finding the maximum element of a list, written in accumulative recursion style: ;; list-max-helper: (listof Num) Num -> Num (define (list-max-helper list partial-max) (cond [(empty? list) partial-max] [(>= (first list) partial-max) (list-max-helper (rest list) (first list))] [else (list-max-helper (rest list) partial-max)])) ;; list-max: (ne-listof Num) -> Num (define (list-max list) (list-max-helper (rest list) (first list))) Here, we recurse at most once per call. The extra parameter allows us to move extra data downwards through the calls so we don't need to restructure it to move data upwards only. We can use as many extra parameters as needed. The key is that we make extra data available to the callee. Generally, the accumulatively recursive function needs a wrapper function to start it off with initial values for the extra parameters. Consider a function that reverses a list: ;; list-reverse: (listof Any) -> (listof Any) (define (list-reverse list current) (cond [(empty? list) current] [else (list-reverse (rest list) (cons (first list) current))])) Note thatreverse is actually a built-in function that has teh same functionality, though it doesn't require the second parameter. We use the function as follows: (list-reverse '(a b c) empty) -> '(c b a) Generative/general recursion Generative/general recursion allows us to get closer to a base case in any way we want - we can calculate the parameters freely. If there is even just one generated parameter, it is generative recursion. Consider the GCD form > 0 : gcd(n,0) = n gcd(n,m) = gcd(m,n mod m) We do not have a data definition. Here, we use generative recursion to create a function to compute the GCD of two numbers: (define (gcd n m) (cond [(zero? m) n] [else (gcd m (remainder n m))])) This is written in generatively recursive style because the arguments are generated by computaniandonm. Generative recursion is easier to get wrong, harder to debug, and harder to reason about. 22/10/13 Trees A tree is an abtract data type, like a dictionary. It is a recursive data structure made up of nodes: internal nodes refer to one or more other nodes. leaf nodes do not refer to any other nodes. Nodes can also store their own value. This value is known as a label. ;; A Tree is one of: ;; * (Leaf-constructor Value) ;; * (Node-constructor Tree Tree) Every node is also a tree in itself. If we look at a node and its descendents as a tree, we call it a subtree in this context. For example, we can represent arithmetic expressions as trees. C(4 + 1) ∗ (7 − (6/2)) : ∗ + 4 1 − 7 / 6 2 If node A refers to node B, and node B refers to node C, and so on, until node Z, then nodes B to Z are descendents of A, and nodes A to Y are ancestors of Z. A node is its own ancestor and descendent. If node A refers to node B, A is the parent/direct ancestor of B, and B is the child/direct descendent of A. If two nodes have the same parent, then they are siblings. Additional constraints for trees are: A node cannot have a descendent that is its ancestor. A node can have only one parent. The very top node is known as the root node. Trees have various classifying properties: Number of children each internal node has: two or less (binary tree), exactly two (variant of binary tree), or even any amount (general tree). Whether all nodes have labels, or just leaf nodes. Whether the order of children of an internal node matters. Actual structure of the tree in the implementation. So for the binary arithmetic expression above: Each internal node has exactly two children. Leaf nodes have number labels, and internal nodes have symbol labels The order of children is significant. We can use the following data definition for a binary arithmetic expression tree: (define-struct bae (operation arg1 arg2)) ;; A BinExp is one of: ;; * Num ;; * (make-bae Symbol BinExp BinExp) So the expression above would be representable(make-bae '* (make-bae '+ 4 1) (make-bae '- 7 (make-bae '/ 6 2))) . Now we can write a template for this: ;; binexp-fn: BinExp -> Any (define (binexp-fn tree) (cond [(number? tree) ...] [(bae? tree) (... (bae-operation tree) ... (bae-arg1 tree) ... (bae-arg2 tree) ...)])) Since we know tha(bae-arg1 tree) and (bae-arg2 tree) are both of type BinExp, we can apply the BinExp processing function on it: ;; binexp-fn: BinExp -> Any (define (binexp-fn tree) (cond [(number? tree) ...] [(bae? tree) (... (bae-operation tree) ... (binexp-fn (bae-arg1 tree)) ... (binexp-fn (bae-arg2 tree)) ...)])) Now we can make functions consuming BinExp values, such as an evaluator: (define (eval ex) (cond [(number? ex) ex] [(bae? ex) (cond [(symbol=? (bae-operation ex) '*) (* (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))] [(symbol=? (bae-operation ex) '+) (+ (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))] [(symbol=? (bae-operation ex) '/) (/ (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))] [(symbol=? (bae-operation ex) '-) (- (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))]))) Traversal Traversal simply means going through every node of a tree. There are two broad types of traversal: breadth-first traversal deals with one nesting level at a time - it deals with all of an interna node's children before dealing with their children. depth-first traversal deals with one path at a time - it deals with a node, its children, and so on, until the entire node is processed, before moving on to the next child. Depth-first traversal is quite natural to implement recursively. As a result, it is used quite often in this course. We can represent traversal as a flat list of the nodes in the tree, in the order that they were traversed. When we do traversal, there is also a question of the order in which we deal with children of an internal node and the node itself. For example, we can process the t(+ 1 2) in the following ways: 1. process the+, the1 and 2 - this is called pre-order traversal. The result'+ 1 2 .e 2. process1 , the+, and then2- this is called in-order traversal. The result 1 '+ 2.e 3. process1 ,2, and the+ - this is called post-order traversal. The result 1 2 '+.e We can implement pre-order traversal pretty simply: traverse-binexp: BinExp -> (listof (union Symbol Num)) (define (traverse-binexp tree) (cond [(number? tree) (list tree)] ; leaf node [(bae? tree) (append (bae-operation tree) (traverse-binexp (bae-arg1 tree)) (traverse-binexp (bae-arg2 tree)))])) In a similar way, in-order and post-order traversal can be done by switching the order of thappend.ents to 24/10/13 Binary Search Dictionaries were previously implemented using an association list of two-element lists. However, this had the problem that it could potentially require us to search through thte entire list to lookup a value. We could instead put the key-value pairs into a binary tree: (define-struct node (key val left right)) ;; A binary tree (BT) is one of: ;; * empty ;; * (make-node Num String BT BT) Here, if a node hempty as its left and right branches, it is a leaf node. Otherwise, it refers to other values and is an internal node. Template for a binary tree: ;; my-bt-fn: BT -> Any (define (my-bt-fn tree) (cond [(empty? tree) ...] [else (... (node-key tree) ... (node-val tree) ... (my-bt-fn (node-left tree)) ... (my-bt-fn (node-right tree)) ...)])) Consider a function that counts the number of nodes equal to a certain value in a tree: ;; count-bt-equal: BT Any -> Any ;; Purpose: returns the number of nodes in `tree` equal to `value` ;; Examples: ;; OMITTED FOR BREVITY (define (count-bt-equal tree value) (cond [(empty? tree) ...] [else (+ (cond [(equal? (node-val tree) value) 1] [else 0]) (count-bt-equal (node-left tree)) (count-bt-equal (node-right tree)))])) ;; Tests: ;; OMITTED FOR BREVITY We can search through this type of tree pretty easily - if not found or empty, search through the left and right subtrees recursively. However, this is no more efficient than an association list - we could still potentially search through the whole thing in order to lookup a value. Draw the tree(make-node 5 'a (make-node 1 'b empty empty) (make-node 6 'c empty (make-node 14 'd empty empty))) : 5 / \ 1 6 \ 14 We do no
More Less

Related notes for CS 135

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.