ICS4U Grade 12 – Computer Science – Scheme

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

 

  1. Apply functions only when all arguments are values
  2. When given a choice, evaluate the leftmost expression first
  3. (f v1 … vn) => v when f is built-in
  4. (f v2 … vn) => exp’ when (define (f x1 … xn) exp) occurs to the left
  5. id => val when (define id val) occurs to the left
  6. (cond [false exp]) => (cond …)
  7. (cond [true exp]) => exp
  8. (cond [else exp] => exp
  9. (and false …) => false
  10. (and true…) => (and …)
  11. (and) => true
  12. (or true …) => true
  13. (or false …) => (or …)
  14. (or) => false