CS115

studied byStudied by 1 person
0.0(0)
learn
LearnA personalized and smart learning plan
exam
Practice TestTake a test on your terms and definitions
spaced repetition
Spaced RepetitionScientifically backed study method
heart puzzle
Matching GameHow quick can you match all your cards?
flashcards
FlashcardsStudy terms and definitions

1 / 66

encourage image

There's no tags or description

Looks like no one added any tags here yet for you.

67 Terms

1

Identifier

  • Name of the function (name of constants)

<ul><li><p>Name of the function (name of constants) </p></li></ul><p></p>
New cards
2

Parameter

knowt flashcard image
New cards
3

Argument

  • Expression producing a value passed to the function

New cards
4

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]

<ul><li><p>Identifiers that are permanently bound to values</p></li><li><p>Memorable name associated with a value</p></li><li><p>Constants are replaced one at a time (<em>small-sub rule) [define price1 1.75]</em></p></li><li><p><em>(user-defined → big-sub → put all at once) [total-cost 4 6]</em></p></li></ul><p></p>
New cards
5

Function Definition Grammar

  • Built-in

  • User-defined

<ul><li><p>Built-in </p></li><li><p>User-defined </p></li></ul><p></p>
New cards
6

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

<ul><li><p><strong>Binding occurrence: </strong>Where the identifier comes into being</p></li><li><p><strong>Bound occurrences: </strong>Locations that refer back to a given binding occurrence</p></li></ul><p><strong>Scope: </strong>An identifier is the region of a program where the identifier binding occurrence is in effect</p><ul><li><p><span>Portion of the program code where a use of that name is tied back to the given definition</span></p></li></ul><p><strong><mark data-color="#fec6c6" style="background-color: #fec6c6; color: inherit"><u>Global scope:</u></mark></strong> Constants and functions introduced using define</p><p><strong><mark data-color="#ffcbcb" style="background-color: #ffcbcb; color: inherit"><u>Function scope:</u></mark></strong> Parameter names and body of function definition</p>
New cards
7

Semantic Model

  • Method for determining the legal meaning of a program

New cards
8

Substitution

  • Replace expression in a program with something slightly similar

  • The program gets closer to being solved

New cards
9

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

New cards
10

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

New cards
11

Tracing

  • Simplify it repeatedly until final value is obtained or encounter an error

New cards
12

Floating-Point

Inexact numbers (15-digits) (#i )

  • Numbers with decimal (to show how precise they are)

New cards
13

Run-Time error

Evaluating an expression

25/0 cannot work

New cards
14

Define

  • User-defined

  • equivalent to the equal sign (=)

New cards
15

Helper function

Using an already defined function in place of another functions body

New cards
16

Ellipsis

(define (id1 id2 ... idk) exp)

  • Inner parentheses in the function definition contain a sequence of identifiers of unknown length (…)

New cards
17

Boolean

[=, <=, >]

  • Consume numbers and produce booleans

New cards
18

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 ?

New cards
19

Boolean Algebra

knowt flashcard image
New cards
20

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…)

New cards
21

Boolean Function Examples

knowt flashcard image
New cards
22

Forbidden Boolean Operation

  • Don’t put ‘=’ on booleans

  • boolean=?

New cards
23

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!

New cards
24

Substitution Rules for Boolean Operations

knowt flashcard image
New cards
25

Conditional Evaluation

knowt flashcard image
New cards
26

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

<ul><li><p>Questions must evaluate to Booleans </p></li><li><p>Evaluate questions in order; when a question evaluates to true, evaluate the corresponding answer and stop </p></li><li><p>Final question can optionally be else, which always succeeds</p></li></ul><p></p>
New cards
27

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

<ul><li><p>A cond expression can appear anywhere in a Racket program that any other expression is permitted. </p></li><li><p>This feature of a programming language is called orthogonality</p></li></ul><p></p>
New cards
28

Simplifying Conditional Code

knowt flashcard image
New cards
29

Short-circuiting

  • Terminate a computation early if additional work won't change the result.

New cards
30

Orthogonality

  • Aspect of the design of programming languages that helps keep them simple and understandable

New cards
31

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]

New cards
32

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

New cards
33

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

<ul><li><p>(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 </p></li><li><p>We require 0 ≤ a ≤ b ≤ (string-length s) 11 </p></li><li><p>(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</p></li></ul><p></p>
New cards
34

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

<ul><li><p>A symbol is an identifier preceded by a single quotation mark; label information, define sets of categories </p><p></p></li><li><p><strong><u>symbol?</u>: </strong>type predicate for symbols </p></li><li><p><strong><u>symbol=?</u></strong>: consumes two symbols, produces a boolean indicating whether they're the same</p><p></p></li><li><p>Symbols are multiple choice, strings are short answer </p></li><li><p>Symbols are atomic, strings are compounds</p></li></ul><p></p>
New cards
35

Symbol Example: Numbers with Infinity

knowt flashcard image
New cards
36

Generalized Equality

  • The built-in function equal? consumes two values of any types and checks if they're equal

<ul><li><p>The built-in function equal? consumes two values of any types and checks if they're equal</p></li></ul><p></p>
New cards
37

Comments

(;) Ignore current line

(;;) Ignore full-line comment

New cards
38
<p>Purpose </p>

Purpose

  • Multi-line comment

  • Starts with the function name

  • “produces..”

  • Explains what the function does (NOT HOW IT DOES IT)

  • Mentions all parameter names

<ul><li><p>Multi-line comment </p></li><li><p>Starts with the function name </p></li><li><p>“produces..”</p></li><li><p>Explains what the function does (NOT HOW IT DOES IT)</p></li><li><p><strong>Mentions all parameter names </strong></p></li></ul><p></p>
New cards
39
<p>Contract </p>

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

<ul><li><p>Comments that describe the domain and range of the function</p></li><li><p>Domain and range are sets</p></li></ul><p>Examples:<br>;; sum-of-squares: Num Num -&gt; Num<br>;; string-length: Str -&gt; Nat<br>;; symbol=?: Sym Sym -&gt; Bool</p><p>When needed, we add an optional <strong>requires</strong> clause under the contract, where we put any additional constraints on domain types:</p><p>;; Requires: 2 &lt;= x &lt; 19<br>;; Requires: s is not the empty string<br>;; Requires: a &gt;= b</p>
New cards
40
<p>Examples</p>

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

<ul><li><p>Show reader what your code might look like </p></li><li><p>Force you to think the problem through by solving cases by hand </p></li><li><p>Shows the function produces the right answer </p></li></ul><p></p>
New cards
41

Header + Definition

  • Define the portion of the function

  • Add extra ellipsis (…)

(define (sum-of-squares p1 p2)
...)

<ul><li><p>Define the portion of the function</p></li><li><p>Add extra ellipsis (…)</p></li></ul><p>(define (sum-of-squares p1 p2)<br>         ...)</p>
New cards
42

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)

<ul><li><p>Additional check-expect to verify the function produces the right answers</p></li></ul><p>;; Tests:</p><p>(check-expect (sum-of-squares -1 -2) 5)<br>(check-expect (sum-of-squares 0 2.5) 6.25)<br>(check-expect (sum-of-squares -10 2.5) 106.25)</p>
New cards
43

Check-expect

(check-expect test-expression expected-result)

  • Consumes 2 expressions and evaluates it

New cards
44

Black-Box Testing

  • Tests that don’t depend on how the function works (incorrect answers)

New cards
45

White-Box Testing

  • Derived from the function definition (correct answers)

New cards
46

Fine-Grained Coverage

  • Must check all ways of testing

(define (charming? x)
(and (>= x 5) (<= x 17) (not (= x 13))))

New cards
47

Testing Breakpoints

Breakpoint: Where the function changes

<p><strong>Breakpoint</strong>: Where the function changes </p><p></p>
New cards
48

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!

New cards
49

Final Design Recipe With HELPER FUNCTION

knowt flashcard image
New cards
50

List length

  • Have a lost with (n) things in it

  • Add one more to obtain a new list (n+1)

  1. A way to describe a list with nothing in it (empty)

  2. Way to add one new thing into the existing list

New cards
51

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

New cards
52

“Consing” a list

  1. The empty list is a list

  2. 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

    1. Any type at all

    2. Must be a list

<ol><li><p>The empty list is a list</p></li><li><p>Given an existing list, you can build a new list that has one more item added at the beginning</p></li></ol><p>cons “construct” = produces a new list </p><ul><li><p>Consume two arguments</p><ol><li><p>Any type at all </p></li><li><p>Must be a list </p></li></ol></li></ul><p></p>
New cards
53

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

New cards
54

List

> (list? empty)
true

> (list? lst2)
true

> (list? "I'm a list")
false

New cards
55

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

New cards
56
<p>Visualization using<strong> nested boxes</strong></p>

Visualization using nested boxes

knowt flashcard image
New cards
57
<p>Visualization using<strong> boxes and arrows</strong></p>

Visualization using boxes and arrows

  • box-and-pointer visualization

<ul><li><p>box-and-pointer visualization</p></li></ul><p></p>
New cards
58

sum-list

  • consumes a list of numbers (lon) and produces the sum

<ul><li><p>consumes a list of numbers (lon) and produces the sum</p></li></ul><p></p>
New cards
59
<p>Data-Defintion </p>

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

<ul><li><p>A type is a group of values</p></li><li><p>Create new types if Racket doesn’t have the one you need</p></li><li><p>Name the new type and use it like any standard type</p></li></ul><ul><li><p>A data definition introduces a new type, here called <code>ExtNum</code></p></li><li><p><code>ExtNum</code> can be either a <code>Num</code> or a <code>Sym</code></p></li><li><p>This type is like a <strong><em>union</em></strong> of <code>Num</code> and <code>Sym</code> (i.e., it can be one or the other)</p></li><li><p>We use a bulleted list to show its possible values</p></li></ul><p></p>
New cards
60

More Data-Definition

knowt flashcard image
New cards
61

Folding Idioms

‘folding’ the contents of the list into a single value

New cards
62

Mapping Idiom

Produces a new list of the same length (can also negate)

New cards
63

Filtering Idioms

Creating a new list with given requirements (sublist)

New cards
64

Auxiliary Parameters

New cards
65

string literal

(i.e., a string value in its final form)

New cards
66

Wrapper Function

A simple, non-recursive function that initiates a large computation, often preparing data for recursive processing and polishing up the result

New cards
67

Homogeneous list

A list whose elements are all of a given type

New cards

Explore top notes

note Note
studied byStudied by 3 people
146 days ago
5.0(1)
note Note
studied byStudied by 8 people
674 days ago
5.0(1)
note Note
studied byStudied by 2599 people
305 days ago
5.0(11)
note Note
studied byStudied by 73 people
703 days ago
5.0(2)
note Note
studied byStudied by 29 people
777 days ago
5.0(3)
note Note
studied byStudied by 33 people
824 days ago
4.5(2)
note Note
studied byStudied by 20 people
730 days ago
5.0(1)
note Note
studied byStudied by 5 people
640 days ago
5.0(1)

Explore top flashcards

flashcards Flashcard (20)
studied byStudied by 9 people
759 days ago
5.0(4)
flashcards Flashcard (68)
studied byStudied by 44 people
366 days ago
5.0(1)
flashcards Flashcard (67)
studied byStudied by 3 people
735 days ago
5.0(1)
flashcards Flashcard (46)
studied byStudied by 4 people
823 days ago
5.0(1)
flashcards Flashcard (61)
studied byStudied by 5 people
399 days ago
5.0(1)
flashcards Flashcard (34)
studied byStudied by 33 people
153 days ago
5.0(1)
flashcards Flashcard (39)
studied byStudied by 2 people
89 days ago
5.0(1)
flashcards Flashcard (314)
studied byStudied by 1 person
46 minutes ago
5.0(1)
robot