CS135

What is Computation?

Have instructions that the computer has to complete

Imperative Design

Based on frequent changes to data

e.x, Java, C++, Python

Functional Design

Computation of new vales rather than the transformation of old ones

e.x, Excel formula, XSLT, LISP

Syntax

How things are supposed to be said

e.x, “?is This Sentence syntactically correct”

Semantics

What the actual meaning is

e.x, “Trombones fly hungrily”

Ambiguity

Valid programs have exactly one meaning

e.x, “Sally was given a book by Joce”

Values

Numbers or mathematical objects (5, 4/9, pi)

Expression

Combine values with operators and functions

E.x, (5+2)

Functions

Generalize similar expressions

E.x, f(x)= x²+4x+2

Different components of a function

1. Name of function (g)

2. Parameters (x y)

3. Algebraic expression using parameters

Arguments

Supplies arguments for parameters

Infix

(+, -, et.c)

E.x, 3-2 = (- 3 2)

(6-4) / (5+7) = / ((- 6 4) (+ 5 7))

Yield Symbol

Each step is indicated using “Yield Symbol”

Ellipses

Use ellipses to show a pattern

(f v1 v2 v3) = V

Defining Functions

“Binds name to body”

(define(g x y) (+ x y))

Syntax Error

Reading an expression

Run-Time error

Evaluating an expression

25/0 cannot work

Substitution Rule

Identifiers

Functions named by identifiers (e.x, x-ray)

Observations

Parameter order matters

(define (g x y) (- x y)

DOES NOT =

(define (g y x) (- x y)

Constants

k=3, p=k²

(define k 3)

(define p (sqr k)) = ‘p’ gets bound to the new value

• Are used in any expression (body of a function)

• Don’t repeat a definition once its expression has been reduced to a value

Comments

;

;; Comments which use whole line

(+ 6 7) ; Comment after code (use one semi-colon

Block Comments

#|

(define (function-to-temporarily-remove x y)

(+ x y))

|#

Helper Function

Help implement another function

• Helper used to define constants must be defined before

  - (define c (distance 1 1 3 9))

Check-expert

Form that we use to test function

(check-expert expr-test expr-expected)

• expr-test = function application we are testing

• expr-expected = expected result “correct answer”

Scope

Global & Function

• The Scope of an identifier is where it has effect (in program)

  1. Smallest enclosing scope has priority

  2. Duplicate identifiers within the same scope will cause an error

(define f 3)

(define (fx)(sqr x))

*ERROR - WAS ALREADY DEFINED

Booleans

(< x 5)

T or F value

<, >, >=, <=, = [each produces a value]

• Abbreviated Bool

Predicates

Function that produces a bool is a ‘predicate’

• Usually has a ‘?’ at the end

• (can-vote? age)

Combining Predicates

and, or, not all consume and produce Bool values

Substitution Rules (and)

(and false …) = false

(and true) = (and …)

(and) = true

Substitution Rules (or)

(or true …) = true

(or false …) = (or …)

(or) = false

Conditional expressions

Expressions should take one value under certain conditions (cond)

• Question is Boolean

• Answer is a possible value of the conditional expression

Short-Circuit Evaluation

Evaluates as many arguments of (and) & (or) that is necessary to find final result

else

If none of the conditions were satisfied, then we do something else

Nested Conditions

Nests one conditional expression inside another

Flattening Nested Conditions

Flats the condition to make it easier to read than nested

• No cond with another cond inside (see notes for example)

[else (cond… *THIS HAS TO BE FLATTEND

Bounding Conditions

• Cut off between passing and failing

Intervals for testing

RULES OF SUBSITIUTION