CS 135 Midterm 1 Notes

Programming language design

**Imperative: **based on frequent changes to data (eg Java, C++, Turing)

**Functional:** based on the computation of new values rather than the transformation of old ones (eg Scheme, Excel formulas, LISP)

Scheme

-functional, minimal, small toolbox, **interactive emulator**, **racket: a dialect of Scheme**, 1975

Functions

** Parameters: **the variables in the function definition (eg g(x,y) = x + y)

**Arguments: **supplied when **application **of the function occurs for the parameters (eg g(1,3))

**Evaluating: **the arguments yield its values by **substitution**

–**Left to right**

** -BEDMAS **and **Obey parentheses**

Scheme: (6 – 4)(3 + 2) becomes (* (6 – 4) (+ 3 2))

**DrRacket: **Interactions and Definitions Window

Interactions window: **Read-Evaluate-Print-Loop (REPL)**

Some Built-in Scheme functions

(expt A B) – computes A^B

(sqr A) – computes A^2

(quotient A B) – computes A/B but truncates the decimal places

(remainder A B) – computes A%B, same with (modulo A B)

(substring string A B) – takes the string from index A to index B-1

**-Scheme Integers **are unbounded

**-Rational numbers **are represented exactly (ie 1/3)

**-Irrational numbers** are flagged as being **inexact**

(sqrt 2) -> #i1.414142…

General definition of functions

**Defining Function:** (define (<name> <parameters1> .. <parametern>) <body expression>)

** Calling Function: **(<name> <parameters1> … <parametern>)

–**define** is a **special form: **looks like a Scheme function, but not all of its arguments are evaluated

-It **binds** a name to an expression

-Consists of single “body” expression

Evaluating Scheme Functions

-we use the ‘yields’ symbol “=>” to show evaluating built-in and user defined functions

(* (- 6 4) (+ 3 2)) => (* 2 (+ 3 2)) => (* 2 5) => 10

** –**Each function’s parameter name has meaning only within the body of the function

Defining Constants

(define <name> <value or calculation>)

-Can give meaningful names

-Reduce typing errors

-Easier to understand

-Can be used in any expression

-Sometimes called variables, but values cannot be changed

DrRacket’s Definition Window

-Can accumulate definitions and expressions

-Run program loads it into interactions window

-Save/Restore definitions window

–**Stepper** tool to evaluate expressions step by step

**–**A Scheme program is a sequence of definitions and expressions

-Expressions are evaluated, using substitution, to produce values

-Expressions may use **special forms** (looks like functions but do not evaluate all arguments)

——– End of Module 1 ——–

Programs are acts of communication between you and yourself, computer, and others

Programs should be **compatible, composable, correct, durable, efficient, extensible, flexible, maintainable, portable, readable, reliable, reusable, scalable, usable, and useful**

**Design Recipe **(in the order of execution)

** Purpose: **describes what the function is to complete

-should mention what the parameter variables would be used for, especially for mathematical formulas

**Examples: **Illustrates the use of the function

** Definition Header & Contract**: Describe what type of arguments the function consumes and what type it produces. And opens the calling of the function

– Types used: Num, Int, Nat (includes 0), Any, Symbol, String

**Definition Body: **what the function actually does

** Tests: **representative set of inputs and expected results

-Should test boundary values in cond statements

-Handle complexities and unusual values

-Should be **small and direct**

-Figure out tests by hand

-Saved and evaluated at the very end

-Use check-expect function

-Use check-within for inexact values

(check-within (sqrt 2) 1.4 0.1)

Boolean-valued functions

- A function which tests whether two numbers x and y are equal has two possible Boolean values: true or false
- Scheme has built-in comparison functions (=), (<), (>), (<=), (>=), (symbol=?)

-Scheme has complex comparisons like AND, OR, NOT functions also

-AND, OR may have 2+ arguments

-Special form AND has value true exactly when all of its arguments have value true

-Special form OR has value true exactly when at-least one of its arguments has value true

-Function NOT has value true exactly when its one argument has value false

Predicates

-A function that produces a boolean result

-Built-in even?, negative?, zero?

Symbolic Data

-Symbols can have meaning to us, but not Scheme

-Defined with an apostrophe: ie ‘blue

-symbol=? function is used to compare symbols

**Strings**: have compound data with spaces and more built-in functions

-more efficient to compare 2 symbols than strings

-string-append, string-length, string<?

-Symbols are small fixed labels where as strings are more indeterminate or when computation is needed

Equality Testing

= is for numbers

symbol=? is for symbols

equal? can be used to test all kinds if types, except inexact values

-Do not use equal? all the time, its slow and gives additional info to the readers and catch errors

**Conditional Expressions **

-cond is a **special form**

-each argument has a question/answer pair, question is a boolean expression

(cond

[(question1) (answer1)]

..

[(questionk) (answerk)]

[else (answer)])

-evaluates in order and as soon as one evaluates to true, the whole expression becomes the answer to that evaluation.

-Only 1 true per cond statement

-AND OR can help simplify complex cond functions

-Knowing if all previous questions evaluated to false can tell us the value doesn’t fit the previous criteria

Tests for conditional expressions

-one test for each possible answer in the expression

-simple, direct, aimed to test that answer

-test boundary points and intervals as well

-Test AND and OR with each argument false/true

**Black-box tests**: tests like examples that are not based on the details of the code

**White-box tests: **tests that are based on the details of code (eg to test specific answers)

Helper functions:

-many smaller functions can collectively help accomplish a larger task

-code you feel is repeated several times should be placed in helper function

——– End of Module 2 ——-

Syntax and semantics

** –**Scheme has few constructs, so model description is short

-No diagrams, vague description is needed to model a program

**Spelling Rules**

-Identifiers are names of constants, parameters, and user-defined function

-Letters, numbers, underscores and other punctuation marks

-Must contain 1 non-number, no spaces or any bracket, colon, or quotes

-Symbols start with an apostrophe

**Grammar**

<def> = (define (<var> <var> … <var>) <exp>)

Semantics

A method of predicting the result of a program without running the program

**Tracing: **doing a step-by-step reduction according to these rules

**Ellipsis: **(…) used to indicate a pattern

Application of built-in functions

-We substitute and then evaluate the function

**Application of user-defined functions**

-We take the body of the function and replace the vales

-We substitute the expression if the argument is not a value

-We simplify the expression in arguments

-Then we define the function with variables in place

-And substitute into the expression of the function

(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

For constants, we have id => val where (define id val) occurs to the left

**Cond**

(cond [false exp] … ) => (cond…)

(cond [true exp] … ) => exp

(cond [else exp]) => exp

**Errors: **A **syntax error** occurs when a sentence cannot be interpreted

A **runtime error** occurs when an expression cannot be reduced to a value by application of our evaluation rules.

Eg. (cond [(> 3 4) x]) <- all conditions result to false, no else statement

**Simplification of AND and OR**

(and false …) => false

(and true …) => (and …)

(and) => true

(or true…) => true

(or false …) => (or …)

(or) => false

Summary of Substitution Rules

- Apply functions only when all arguments are values
- When given a choice, evaluate the leftmost expression first
- (f v1 … vn) => v when f is built-in
- (f v2 … vn) => exp’ when (define (f x1 … xn) exp) occurs to the left
- id => val when (define id val) occurs to the left
- (cond [false exp]) => (cond …)
- (cond [true exp]) => exp
- (cond [else exp] => exp
- (and false …) => false
- (and true…) => (and …)
- (and) => true
- (or true …) => true
- (or false …) => (or …)
- (or) => false