CprS376 Schedule
CprS376 Class 1
CprS376 Class 3

Scheme Programming Primer

Class 2 - Section 1.1



Contents

Getting Started

Reading through the following transcript should give you a quick introduction to the interactive nature of Scheme programming and a number of the most fundamental and useful scheme programmming constructs. Note that this transcript was prepared using a different scheme interpreter, so you may see slight variations when using Petite Chez Scheme.

;; basic-Scheme.ss

;; TOPICS:  elementary data types: integers, Boolean constants, 
;;                                 symbols, lists
;;          control: if and cond
;;          naming things: define
;;          creating procedures: lambda


;; = = = = = DATA TYPES = = = = =

; = = = = = numbers and arithmetic = = = = =

>>> (+ 5 6)
11
>>> (+ 5.2 6.9)
12.100000000000001
>>> (* 2 3 4)
24


; = = = = = Boolean constants = = = = =

; NOTE: Boolean values #f = false, #t = true

>>> (Boolean? #f)
#t
>>> (Boolean? #t)
#t
>>> (Boolean? 17)
#f


; = = = = = symbols = = = = =

>>> 'x
x
>>> 'chris
chris
>>> 'hot-dogs-and-mustard
hot-dogs-and-mustard


; = = = = = lists = = = = =

; list will make a list of its arguments
>>> (list 'a 'b 'c)
(a b c)
>>> (list 'a 'b 'c '(1 2 3 4))
(a b c (1 2 3 4))

; car selects the first element of a list
>>> (car '(a b c))
a

; cdr selects all but the first element of a list
>>> (cdr '(a b c))
(b c)

; cons is a "constructor"
>>> (cons 'x '(a b c))
(x a b c)

; shorthand for chains of car's and cdr's
>>> (car (cdr '(a b c d)))
b
>>> (cadr '(a b c d))
b
>>> (car (cdr (cdr '(a b c d))))
c
>>> (caddr '(a b c d))
c

; what should X be?
>>> (cXr '(a b (c y) d))
y

; solution
>>> (cddr '(a b (c y) d))
((c y) d)
>>> (caddr '(a b (c y) d))
((c y) d)
>>> (caddr '(a b (c y) d))
(c y)
>>> (cadr (caddr '(a b (c y) d)))
y
>>> (cdr (caddr '(a b (c y) d)))
(y)

; append glues two lists together
>>> (append '(a b c) '(x y z))
(a b c x y z)

; = = = = = data types and predicates to test them = = = = =

>>> (number? 9)
#t
>>> (number? 'a)
#f
>>> (Boolean? #t)
#t
>>> (symbol? 'jane)
#t
>>> (symbol? 84)
#f
>>> (symbol? '(a b c d e))
#f


; = = = = = CONTROL STRUCTURES = = = = =

;; if

; syntax for if:  (if 
                      
                      )

>>> (if (symbol? 'kitty)
        'SYMBOL
        'something-else)
symbol
>>> (if (symbol? 678)
        'SYMBOL
        'something-else)
something-else

>>> (if #f 1 2)
2
>>> (if #t 1 2)
1

; #f and '() are the ONLY two values considered to be false
>>> (if '() 1 2)
2
>>> (if 1 2 3)
2

;; if can be used to channel the flow of control
>>> (if (> 5 0)
        'yes
        'no)
yes

;; cond

; syntax for cond:
    (cond ()
          ()
                ...
          (else ()))
    
     ::= ( )
                           
>>> (cond ((symbol? 'chris) 'symbol)
          ((number? 'chris) 'number)
          (else 'something-else))
symbol
>>> (cond ((symbol? 23) 'symbol)
          ((number? 23) 'number)
          (else 'something-else))
number
>>> (cond ((symbol? '(a b c d)) 'symbol)
          ((number? '(a b c d)) 'number)
          (else 'something-else))
something-else


; = = = = = DEFINE = = = = =

; define is used to assign values to symbols
; think of define as entering symbol/value pairs into a symbol table

;;   SYMBOL TABLE
;;    var    val
;;     x      3
;;     y     15
;;    lst  (a b c)


>>> (define x 3)
x
>>> x
3
>>> (define y 15)
y
>>> y
15
>>> (define lst '(a b c))
lst
>>> lst
(a b c)

; one can change the values of variables

>>> (define chris '(chris parrish))
chris
>>> chris
(chris parrish)
>>> (define chris 47)
chris
>>> chris
47

; = = = = = PROCEDURES = = = = =

;; one of the great strengths of Scheme is the ease
;; with which procedures can be created

;; the special form lambda creates procedures

>>> (lambda (obj)
      (if (symbol? obj)
          'SYMBOL
          'something-else))
#

>>> (lambda (obj)
      (cond ((symbol? obj) 'symbol)
            ((number? obj) 'number)
            (else 'something-else)))
#

;; to be able to employ these procedures in our calculations, 
;; we use define to give them names

>>> (define classify
      (lambda (obj)
        (cond ((symbol? obj) 'symbol)
              ((number? obj) 'number)
              (else 'something-else))))
classify
>>> (classify 23)
number
>>> (classify 'chris)
symbol
>>> (classify '(1 2 3 4))
something-else
; the quote mark inhibits evaluation
>>> (classify classify)
something-else
>>> (classify 'classify)
symbol

; there is even a predicate which can tell
; if a Scheme object is a procedure

>>> (procedure? classify)
#t
>>> (procedure? cons)
#t
>>> (procedure? +)
#t
>>> (procedure? '+)
#f

;; = = = = = LIST? = = = = =

; note that we have not said anything about a predicate called list?
; that is because it is not built into Scheme. We must write it ourselves.

; null? returns #t if its argument is the empty list
; otherwise it returns #f

>>> (null? '())
#t
>>> (null? '(here there))
#f

; pair? returns #t if its argument is a non-empty list

>>> (pair? '())
#f
>>> (pair? '(a b))
#t
>>> (pair? 'chris)
#f

; these two predicates together can tell if an object is a list

>>> (define list?
      (lambda (obj)
        (cond ((null? obj) #t)
              ((pair? obj) #t)
              (else #f))))
list?
>>> list?
#
>>> (list? '())
#t
>>> (list? '(a b c))
#t
>>> (list? 234)
#f

;; = = = = = OR = = = = =

;; the above definition of list? is perfectly satisfactory
;; but a rather more elegant definition is possible
;; using the special form or

>>> (define list?
      (lambda (obj)
        (or (null? obj)
            (pair? obj))))
list?
>>> (list? '())
#t
>>> (list? '(a b c))
#t

;;; exercises from chap 1

>>> (cons 'two '())
(two)
>>> (cons 'one (cons 'two '()))
(one two)
>>> (cons 'one (cons 'two (cons 'three (cons 'four '()))))
(one two three four)

Notions of Equivalence in Scheme

Most scheme programming constructs seem quite straightforward, but there are certain subtleties involved in scheme's notions of equivalence and equality.


;; equivalence.ss


;; = = = = =  FLAVORS OF EQUALITY = = = = =

;; for numbers

>>> (= 45 (+ 40 5))
#t

;; for symbols

>>> (eq? 'a (car '(a b c)))
#t

;; for numbers, symbols, booleans

>>> (eqv? #f (= 2 3))
#t

;; for all of the above, and lists as well

>>> (equal? (< 2 1) (= 3 4))
#t
>>> (equal? '(a b c d) '(a b c 3))
#f


; = = = = = SUMMARY OF EQUIVALENCE = = = = =

; the operators: =, eq?, eqv?, equal?

;   = tests sameness of numbers 

;   eq? tests sameness of symbols 
;        note: each application of cons constructs a new cell
;                 (eq? (cons 1 2) (cons 1 2)) returns #f!

;   eqv? tests sameness of numbers, symbols and booleans
;         (as well as vectors, strings, and chars)

;   equal? is a universal test for sameness 
;          (tests all of the above and lists as well)
;          note: (equal? (cons 1 2) (cons 1 2)) returns #t!

;   the difference is mainly one of efficiency
;          use the predicate designed for the task at hand

SICP Source Code

Programming Exercises

We will begin to work on the following exercises from chapter 1 in class today: 5, 9, 10, 12,15, 17, 18, 29, 30, 31, 32, 34, 35, 36, 37.