Looks like no one added any tags here yet for you.
Identifier
Name of the function (name of constants)
Parameter
Argument
Expression producing a value passed to the function
Constants
Identifiers that are permanently bound to values
Memorable name associated with a value
Constants are replaced one at a time (small-sub rule) [define price1 1.75]
(user-defined → big-sub → put all at once) [total-cost 4 6]
Function Definition Grammar
Built-in
User-defined
Scope
Binding occurrence: Where the identifier comes into being
Bound occurrences: Locations that refer back to a given binding occurrence
Scope: An identifier is the region of a program where the identifier binding occurrence is in effect
Portion of the program code where a use of that name is tied back to the given definition
Global scope: Constants and functions introduced using define
Function scope: Parameter names and body of function definition
Semantic Model
Method for determining the legal meaning of a program
Substitution
Replace expression in a program with something slightly similar
The program gets closer to being solved
Simplifying Built-In Functions
How do we simplify an expression like this one?
(+ 5 7 8)
The + function is built in
The best we can do with a built-in function is to write down the answer in one step: 20
We call this the as-if-by-magic rule
Simplifying User-Defined Functions
With a user-defined function, we have a lot more information: the function body
(define (f x) (- (- (sqr x) x) 1))
(f 13)
We replace the application by the body of the function, in which every occurrence of a parameter name is replaced by its corresponding argument value.
This is the big-sub rule
Tracing
Simplify it repeatedly until final value is obtained or encounter an error
Floating-Point
Inexact numbers (15-digits) (#i )
Numbers with decimal (to show how precise they are)
Run-Time error
Evaluating an expression
25/0 cannot work
Define
User-defined
equivalent to the equal sign (=)
Helper function
Using an already defined function in place of another functions body
Ellipsis
(define (id1 id2 ... idk) exp)
Inner parentheses in the function definition contain a sequence of identifiers of unknown length (…)
Boolean
[=, <=, >]
Consume numbers and produce booleans
Predicate
Consume numbers and determine if it has a given property [even? odd? positive? negative?
Type Predicate: Consumes value and if it belongs to a certain type [number? integer? boolean?]
ALWAYS GIVE PREDICATES NAME ENDING IN ?
Boolean Algebra
Boolean Operations
• (and exp1 … expk) produces true if all of the expi evaluate to true, and false otherwise
• (or exp1 … expk) produces true if any of the expi evaluates to true, and false otherwise
• (not exp) produces false if exp evaluates to true, and true if exp evaluates to false.
(see notes…)
Boolean Function Examples
Forbidden Boolean Operation
Don’t put ‘=’ on booleans
boolean=?
Semantics of Boolean Operations
• The not operation is just a regular built-in function: it consumes a Boolean value and produces its logical complement.
• But ‘and’ and ‘or’ have special powers: they stop processing as soon as the answer is certain:
20 (or (= x 0) (> (/ 1 x) 10))
(and (positive? x) (< (sqrt x) 5))
• This power is called short-circuiting. Because of short-circuiting, ‘and’ and ‘or’ or can't be functions—they need special-purpose substitution rules!
Substitution Rules for Boolean Operations
Conditional Evaluation
Grammar of cond
Questions must evaluate to Booleans
Evaluate questions in order; when a question evaluates to true, evaluate the corresponding answer and stop
Final question can optionally be else, which always succeeds
Semantics of cond
A cond expression can appear anywhere in a Racket program that any other expression is permitted.
This feature of a programming language is called orthogonality
Simplifying Conditional Code
Short-circuiting
Terminate a computation early if additional work won't change the result.
Orthogonality
Aspect of the design of programming languages that helps keep them simple and understandable
String Functions
A string is a block of text, i.e., a sequence of characters
A string literal can be written by enclosing text in double quotes
string?: type predicate for strings
string=?: consumes two strings, produces a boolean indicating whether they have the same characters
string-length: consumes a single string, produces the number of characters in the string
string-append: consumes any number of strings, and produces a single new string in which all the characters of the consumed strings are glued together
string Indices: Assign consecutive indices to the characters in a string, starting from zero: [0 1]
Escaped Characters
Some special characters must be preceded by a backslash character (\) so that they don't confuse Racket
Inside a string, write \" for a double quote and \\ for a backslash. Each is still a single character
Substrings
(substring s a b): produce a new string consisting of the characters of string s from index a up to, but not including, index b
We require 0 ≤ a ≤ b ≤ (string-length s) 11
(substring s a): a convenient shorthand for (substring s a (string-length s)), i.e., the substring from index a to the end of the string
Symbols
A symbol is an identifier preceded by a single quotation mark; label information, define sets of categories
symbol?: type predicate for symbols
symbol=?: consumes two symbols, produces a boolean indicating whether they're the same
Symbols are multiple choice, strings are short answer
Symbols are atomic, strings are compounds
Symbol Example: Numbers with Infinity
Generalized Equality
The built-in function equal? consumes two values of any types and checks if they're equal
Comments
(;) Ignore current line
(;;) Ignore full-line comment
Purpose
Multi-line comment
Starts with the function name
“produces..”
Explains what the function does (NOT HOW IT DOES IT)
Mentions all parameter names
Contract
Comments that describe the domain and range of the function
Domain and range are sets
Examples:
;; sum-of-squares: Num Num -> Num
;; string-length: Str -> Nat
;; symbol=?: Sym Sym -> Bool
When needed, we add an optional requires clause under the contract, where we put any additional constraints on domain types:
;; Requires: 2 <= x < 19
;; Requires: s is not the empty string
;; Requires: a >= b
Examples
Show reader what your code might look like
Force you to think the problem through by solving cases by hand
Shows the function produces the right answer
Header + Definition
Define the portion of the function
Add extra ellipsis (…)
(define (sum-of-squares p1 p2)
...)
Tests
Additional check-expect to verify the function produces the right answers
;; Tests:
(check-expect (sum-of-squares -1 -2) 5)
(check-expect (sum-of-squares 0 2.5) 6.25)
(check-expect (sum-of-squares -10 2.5) 106.25)
Check-expect
(check-expect test-expression expected-result)
Consumes 2 expressions and evaluates it
Black-Box Testing
Tests that don’t depend on how the function works (incorrect answers)
White-Box Testing
Derived from the function definition (correct answers)
Fine-Grained Coverage
Must check all ways of testing
(define (charming? x)
(and (>= x 5) (<= x 17) (not (= x 13))))
Testing Breakpoints
Breakpoint: Where the function changes
Testing Inexact Numbers
We never check inexact numbers for equality:
> (equal? (sqr (sqrt 5)) 5)
false
• By extension, we're not allowed to use check-expect with inexact numbers
• check-within: includes a third argument: a numeric tolerance
> (check-within (sqr (sqrt 5)) 5 0.0001)
The test passed!
Final Design Recipe With HELPER FUNCTION
List length
Have a lost with (n) things in it
Add one more to obtain a new list (n+1)
A way to describe a list with nothing in it (empty)
Way to add one new thing into the existing list
The empty list
Nothing in it
Use it as a starting point
> empty
Kinda like ‘true’: a special defined value that means only itself
> (empty? empty)
true
“Consing” a list
The empty list is a list
Given an existing list, you can build a new list that has one more item added at the beginning
cons “construct” = produces a new list
Consume two arguments
Any type at all
Must be a list
Cons Cell
cons function produces a special value of a new type
Verify by its predicate, cons?
> (cons? empty) ;; the empty list isn't a cons
false
List
> (list? empty)
true
> (list? lst2)
true
> (list? "I'm a list")
false
First & Rest
(first (cons v lst)) ⇒ v
(rest (cons v lst)) ⇒ lst
> (first suits)
'spades
> (rest suits)
(cons 'hearts (cons 'diamonds (cons 'clubs empty)))
CANNOT USE FIRST OR REST ON AN EMPTY
> (first empty)
first: expects a non-empty list; given: empty
> (rest empty)
rest: expects a non-empty list; given: empty
Visualization using nested boxes
Visualization using boxes and arrows
box-and-pointer visualization
sum-list
consumes a list of numbers (lon) and produces the sum
Data-Defintion
A type is a group of values
Create new types if Racket doesn’t have the one you need
Name the new type and use it like any standard type
A data definition introduces a new type, here called ExtNum
ExtNum
can be either a Num
or a Sym
This type is like a union of Num
and Sym
(i.e., it can be one or the other)
We use a bulleted list to show its possible values
More Data-Definition
Folding Idioms
‘folding’ the contents of the list into a single value
Mapping Idiom
Produces a new list of the same length (can also negate)
Filtering Idioms
Creating a new list with given requirements (sublist)
Auxiliary Parameters
string literal
(i.e., a string value in its final form)
Wrapper Function
A simple, non-recursive function that initiates a large computation, often preparing data for recursive processing and polishing up the result
Homogeneous list
A list whose elements are all of a given type