# 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

..

-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

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