CMPSC 461 - Scheme Language

Prefix Notation

4+(5*7) → (+4(* 5 7))

3+4 → (+ 3 4)

3*4 → (*3 4)

5+(2*2) → (+5(* 2 2))

Scheme Variables

foo = 3 → (define foo 3)

(* foo 4) = 12

Scheme Expressions

(E₁ E₂ … E_k)

E₁ is the function to invoke

E₂ … E_k Function arguments

User-Defined Functions

f(x) = x² → (define (square x) (* x x))
(+ (square 2) (square 3)) = 4 + 9 = 13

f(x, y) = x + y² → (define (f x y) (+ x (* y y))
(f 3 4) = 3 + 4² = 19

Built-int Functions (take 0+ params, apply operation to all params together)

(+ 2 3 5) = 11
(* 3 2 4) = 24
(+) = 0
(*) = 1
(+ 5) = 5
(* 8) = 9

Flow Control

(define (abs x) #Foo header)

(if (< x 0) #Conditional

(-x) #Built-in function

x)) #Return

(abs -3) = 3
(abs 3) = 3

List built-in functions

(sort (list 4 6 5)) = (4 5 6)
(sort (list 5 4 3 2 1) <) = (1 2 3 4 5)
(sort (list “abc” “a” “ab”) string<?) = (“a” “ab” “abc”)

(length (list 1 2)) = (1 2)

List manipulation

(define my-list (list 1 2 3 4 5))

my-list → (1 2 3 4 5)

(car my-list) → 1

(cdr my-list) → (2 3 4 5)

General info

Dynamic Typing
Functions = Values

Anonymous Functions (Lambda Calculus)

Small foos taking any amt of args, but only have one expression; Can only use once

(define square (lambda(x) (* x x)) = (define (square x) (* x x))

Parenthesis

Reserved for function call / invocation

(+ 3 4) is okay
(+ (3) 4) is not

(lambda(x) x) is okay
(lambda (x) (x)) is not

(lambda(x) (* x x)) is okay
(lambda (x) (* (x) x)) is not

Recursive Functions

(define diverge (lambda (x) (diverge (+ x 1))))

1) define foo
2) foo arg = lambda foo
3) lambda arg = fully defined foo

Booleans

#t → True
#f → False
number? → test whether argument is a number
equal? → test if values are equal (works with & beyond numbers)
= → reserved for numbers
and, or, not → they exist as operators

(equal? 2 2) → #t

(equal? x (* 2 y)) → does x = 2 * y ?

(equal? #t #t) → #t

(and (> 7 5) (< 10 20))) → (7 > 5) and (10 < 20) → #t

If expressions

(if P E1 E2) → If P then E1. Else, E2

(define (max x y) (if (> x y) x y) → if (x>y) return x. Else return y.

DOES NOT EVALUATE BOTH BRANCHES

Multi-Case Conditionals

(cond (P1 E1)
     (Pn En)
     (else En+1))

Ex:
(cond ((>= x 90) ‘A)

     ((>= x 80) ‘B)

     ((>= x 70) ‘C)

     ((>= x 60) ‘D)

     (else ‘F)))

Higher-Order Functions

Functions that: take foos as args & return foos as results. Ex: g(f, x) = f(f(x))

(define (twice f x) (f (f x)))
(define (PlusOne x) (+ 1 x))
(twice plusOne 2)
(twice square 2)
(twice (lambda (x) (+ x 2)) 3)

Let constructus

No variable can refer to another one defined in same let
(let ((x1 E1) (x2 E2) … (xk Ek)) E)

(let ((x (+ 3 2)) (* x x))) = (* (+ 3 2) (+ 3 2))

(let ((three-sq (square 3)) (four-sq (square 4))) (+ three -sq four-sq)) =
(+ (square 3) (square 4)

Variables can refer to earlier variables
(let* ((x 2) (y x)) y) = (let ((x 2)) (let ((y x)) y)

Ei can refer to themselves or each other
letrec ((x1 E1) (x2 E2) … (xk Ek)) E)
Here, scope of x1 is E1, E2, … and Ek and