Slides

S1: Overview

Introductions Instructor, TAs, Audience
Administrative Issues
- Topics, Textbooks, Reference Material
- Policies and course secrets, Schedule
Week 1 - Outline
- 1.1 Csci 3316 in context of Computer Science
- Appendix B, 1.2 Scheme syntax
- 1.3 Procedures and Definitions
- 1.4 Decisions
- 1.5 Scheme Semantics (The rules)
Reading
- Review Calculus I
- Chapter 1: Basic Scheme
- Appendix B.1, B.2, B.3, B.5.3
Recommended Ex.: 1.12-15, 17-19, 23, 27, 30, 34, 35

S2: Introductions, Administrative Issues

Introductions
- Instructor: Shashi
- TAs : Andrew, Catherine, Zheng and Cecil
- Audience: meet your neighbor, form study group
Administrative Issues
- Topics, Textbooks, Reference Material
  - Practice makes perfect - use exercises!
- Policies on Examinations and Homeworks
  - Must submit all homeworks!!
- Policy on Cheating and Collaboration
  - work together, but no verbatim copies!
- Course secrets
Schedule
- Note: QUIZ on Friday - review Calculus I
- Note due dates, plan your quarter!

S3: Csci 3316 in context of Computer Science

Q? Identify applications of computers in medicine, business,
- science, engineering, entertainment, government, law, ...
- Computer Science = life-blood of modern society
- Medicine - Pacemaker, CAT-scan, patient-records, ...
- Business - ATMs, credit-card, OLTP, ...
- Science - Space flight control, Genome mapping, ...
- Engineering - Car Design, CNC machines, ...
- Entertainment - Movies (Jurassic Park), VR Games
- Law - researching precedent
- Government - Environmental, defense, crime prevention

S4: Csci 3316 in context of Computer Science

Life Cycle of computer systems
- analysis
- requirement specification
- system design
- implementation
- quality control, testing
- operation, maintenance
Q? Where does computer programming fit in the life cycle?
Why study Scheme programming language?
- Simple unambiguous syntax, robust, interpreted this incremental
- Yet powerful
Scheme = best first programming language ?

S5: Scheme Syntax & Semantics

Syntax Vs. Semantics
- Syntax = structure related, e.g. Grammar
  - Ex.: Sentence = Noun-Phrase + Verb Phrase
- Semantics relates to meaning
Ex. Let S = Colorless green ideas sleep furiously.
- Q? Does S conform to syntax rules of English?
- Q? Is S semantically correct (meaningful)?
Syntax of Scheme forms (programs)
- Atomic forms: 2, 3.402, #t, "aString", aVariableName
- Compound forms, e.g.
  (+ 1 2), (define x 3), (if x y (+ y 2)), ...
  - pre-fix notation
- Semantics
- Evaluation rules for different scheme forms
- procedure calls Vs. special forms

S6: 1.1 Syntax: Prefix Notation

Unambiguous, obviates the need of precedence rule !
- Consider infix 1 + 2 * 3.
  - Q? Is it infix: (1 + 2) * 3 OR 1 + (2 * 3)
  - Ambiguity from optional parenthesis, precedence rules
- Prefix: (* (+ 1 2) 3), (+ 1 (* 2 3))
- No ambiguity
- No optional parenthesis
:) No precedence rules to remember in Scheme!
:) Uniform syntax for all forms
Ex. 1-13, 1-14, 1-15 (pp. 20)

S7: Common Errors with Scheme Syntax

See 1.1, Appendix B.1-3
Parenthesis are special, and NOT optional
- Ex. (+ 2 3) evaluates to 5
  - but (+ (2) 3) is an error
  - because (2) tries to find operator 2, not number 2!
- Names are case insensitive
- foo, FOO and FoO refer to the same object
Semicolon (;) start a comment till end of line
Whitespace are delimiters except within strings
Reserved keywords should not be used as Identifiers
- Chapter 1: lambda, define, if, and, or
- Chapter 2-5: begin, case, cond, delay, do, else,
  - let, let*, letrec, quote, set!, unquote, ...

S8: Semantics: 1.2.1, 1.5 The Rules

Special Forms = (keyword argument1 argument2 ...)
(define x 3), (if ( > x 0) (f x) (g x)), ...
- Special form controls evaluation of arguments.
- Ex. (if condition form1 form2)
  - evaluates either form1 or form2 but not both!
- Ex. special forms in Ch#1: and, define, if, lambda, or
- Procedure calls = (procedure argument1 argument2 ...)
- Evaluates procedure and all arguments before calling procedure.
  (+ 1 2), ((lambda(x)(+x 2)) 5), (not ( > x y))
Ch#1. procedures: +, -, *, /, < , > , =, > =, not, sqrt, zero?,
discr, find-root1, find-root2 (pp 35), ...
Q? Is it possible to write a procedure new-if
to simulate special form "if"?

S9: 1.3 Special Form "lambda"

Syntax: (lambda (variables) mapping-rule )
Semantics: Creates a procedure.
- Does not evaluate variables or mapping-rule
  (lambda (x) (+ x 3) ) ;creates a procedure,
  ( (lambda(x) (+ x 3)) 10) ;evaluates to 13
- Q? Write a lambda-form for f(x) = 10x + 4
- Recall: Function f from a set X to a set Y,
- assign each element x in X an element y in Y.
- Domain of f = set X ; Range of f = set Y
Domains relevant to Chapter 1 (see Appendix B.2, B.3)
Boolean = (#t, #f)
Numbers = real numbers (finite precision, limited range)
Procedures = set of lambda-forms
Q? Identify a couple of scheme functions on each domain.
Q? Identify domain and range of following functions:
+, < , add1, not, sqrt, zero?

S10: 1.3 Special Form "define"

Syntax : (define name value)
Semantics : Create an name initialized to value
- Evaluate value but not name
- Environment = collection of < name, value > pairs
Scheme definitions
- constant: (define a 5)
- function: (define f (lambda(x) (+ (* 10 x) 3)) )
  - or (define (f x) (+ (* 10 x) 3))
- Applications: (f 3) , (f a), or
  - ( (lambda(x) (+ (* 10 x) 3)) a )
- Compare with Calculus syntax
- Definition of constant: a = 5
- Definition of a function: f(x) = 10x + 3
- Applications: f(3) , f(a)
Ex. 1-17, 1-18 (pp. 28)

S11: 1.4 Special Form "if"

Syntax: (if condition form1 form2)
Semantics: if condition is true evaluate form1 else form2
- evaluates either form1 or form2 but not both!
- always evaluates the condition
- condition is Boolean (#t, #f)
Use in decision making
- Ex. from calculus : absolute value of a number
  - |x| = x if x > = 0, |x| = -x if x < 0.
- Ex. from post-office in calculus notation.
  - Stamp(postcard) = 40 cents if domestic?(address)
  - Stamp(postcard) = 60 cents if international?(address)
- Ex. (if ( > x 0) "x is positive" "x is negative")
- (define safe-sqrt
- (lambda(x)
- (if ( < x 0) "undefined" (sqrt x)) ) )
- Q? Create a scheme function to represent |x|
- Identify conditional, form1, form2 in

S12: 1.4 Special Forms "and", "or" & function "not"

Predicate is a function returning a Boolean value
- Ex. function zero?, > , < , > =, ...
  (define positive? (lambda(x) ( > x 0)) )
Simple predicates may need to be combined
- Ex. 1-34 (pp 44) from Post Office
- Q? How do we combine predicates?
Functions : Boolean domain - > Boolean range
- not: (not #t) = #f, (not #f) = #t
Special Forms : (Boolean X Boolean) - > Boolean
- (and #t #t) = #t; (and #t #f) = (and #f #t) = (and #f #f) = #f
  - is true if and only if both predicates are true
- (or #t #t) = (or #t #f) = (or #f #t) = #t; (or #f #f) = #f
  - is true if either predicate is true

S13: 1.4 Special Forms "and", "or"

Ex.: Identify the instance of "and", "or in (A), (B), (C)
- (A) A person may take road-test for driving license if
  - (i) the person is at least 16 years of age
  - (ii) the person has passed the written test
- (B) A student may get a passing grade in Csci 3316 if
  - (i) she submits all homeworks
  - (ii) scores at least 50 percent on final exam.
- (C) A student may register in Csci 3316 if
  - (i) he has taken Calculus I at U of M
  - (ii) he has taken equivalent course elsewhere

S14: Administrative

Waiting List Policy- Departmental List, others
Stats on Monday 1/13
Section, Capacity, Registered showed up, Waiting
1 34 31, 1 (original) + 2 (new)
2 34, 29, 4 (original) + 1 (new)
3 34, 31, 4 (original) + 3 (new)
4 34, 29, 7 (original) + 10 (new?)
5 34, 22, 6 (new)
Policy
Original wait list = > get section you are waiting for
New wait list = > find a section with room
e.g. section 5, or 1 or 2
Homework 1 - Any questions?

S15: Composing forms - procedure calls

Composing procedure-call forms
- Arithmetic: +, -, *, /, sqrt, ...
  (* b b), (* 4 (* a c)), (* b -1)
  (- a b), (- (* b b) (* 4 (* a c)) )
  (sqrt a), (sqrt ( - (* b b) (* 4 (* a c)) ) )
- Predicates and Boolean: and, or, not, > , =, < , > =, < =, zero?, ...
  ( > a 0), (zero? b), ( < a 5) ;;; assume a and b are numbers
  (not #t), (not (zero? 0))
  (and ( > a 0) ( < a 5) ), (or (zero? b) (= a 0) ),
- Mixing boolean and arithmetic procedures
  Ensure Domain Compatibility
  (zero? (+ a b)) ;;; assume a and b are numbers
  (+ (zero? a) b) ;;; ERROR: domain of +!!!
- Ex.: Evaluate following forms with a=0, b= -1, c = -2.
  ( > (+ a b) (- a b))
  ( < (zero? a) (zero? b) )
  (and ( > a b) (zero? a) )
  (not ( < a b))
  (or (not (zero? a)) (not b) )
  (+ 2 ( < b c))

S16: Composing forms - special forms if, procedure calls

(if condition form1 form2) returns either form1 or form2
- condition should be boolean
- form1, form2 can be either number or boolean or ...
  (if (zero? angle) 1 (/ (sin angle) angle) ) ;;; angle is a number
  (+ 2 (if ( > 2 3) 4 5) )
  (if ( < x 0) null (sqrt x) )
  (if (zero? a) ;;; Assume a, x are numbers
  0
  (if (zero? x) null (/ a x) ) )
Ex.: Evaluate the following assuming x = 3, y =7 , w = 0, z =0
(if ( > x 5) ( < x 10) ( > x 0) )
( > 30 (if ( > x 0) x (* x -1) ) )
(+ 30 (if x x y ) )
(if (zero? w)
0
(if (zero? z) null (/ w z) ) )
(if (zero? (+ w 1))
0
(if (zero? z) null (/ (+ 1 w) z) ) )

S17: Composing forms - User defined procedures

A special use of define, lambda
- (define procedureName (lambda (parameters) form ) )
  (* b b), (* 4 (* a c)), (- (* b b) (* 4 (* a c)) )
  (sqrt ( - (* b b) (* 4 (* a c)) ) )
  ( < x 0)
  (if ( < x 0) null (sqrt x) )
  (define sqr (lambda(b) (* b b) ) )
  (define negative? (lambda(x) ( < x 0) ) )
  (define robust_sqrt (lambda(x) (if (negative? x) null (sqrt x)) ) )
- Ex. Define following procedures to solve quadratic equations
- (discriminant a b c)
- (solution1 a b c ) ;;; computes a solution
- (robust_solution1 a b c) ;;; Check arg-for-sqrt > 0
  (define discriminant
  (lambda(a b c) ( - (* b b) (* 4 (* a c)) ) ))
  (define solution1
  (lambda(a b c)
  (/ (+ (* b -1) (discriminant a b c)) 2 ) ))
  (define robust_solution1
  (lambda(a b c)
  (if (negative? (discriminant a b c) )
  null
  (solution1 a b c) )
  ))

S18: Composition - Summary

Arithmetic/Boolean Procedure call forms
- Ensure domain compatibility,
  - i.e. inputs for each procedure of appropriate type!
- Nesting of any depth possible
Combining with special form "and", "or", "if"
- Restrict forms to be side-effect-free!
- Starters: Avoid deep nesting of "if", "and", "or"
  - e.g. use only 1 of these in a procedure-body
  - by decomposing complex tasks into simple procedures!
- Combining with special form "define", "lambda"
- Restricted to procedure definition for now!
- (define procedureName (lamdba (arguments) body) )
  - body has no define/lambda for now.