CS61A: Lecture 25

Lecture - The Scheme Programming Language

• 2 Reasons
  • Concepts in Python transfers into another programing language
  • Build an interpreter for Scheme
    • A program that runs other programs
• Scheme as a language
  • There are only expressions in the language.
  • Each expression is related to a value.
  • Expressions are evaluated in an environment (which gives symbols meaning) to produce a value.
    • Local frame: “the course instructor” has a specific meaning for a particular course.
    • Global frame: “multiply” is an operation that everyone knows about.
    • Local before Dlobal: in a particular context, “multiply” can mean something different.
• Scheme programs consist of expressions, which can be:
  • Self-evaluating expressions: 2, 3.3, true
  • Symbols: +, -, quotient, not
  • Call expressions: (quotient 10 2), (f x)
  • Special forms: (if a b c) (let ((x 2)) (= x 1))
• These expressions are either primaitive or combinations.
• True and false values in scheme: #t or #f

The minus and division operator (-)

• different behaviors based on number of parameters
  • No parameters: Errors
  • One parameter: Minus would get the negative of the value, division would return 1 over the value.
  • Many parameters: Minus would subtract multiple values in a row from the first value, same with division.
• Integer division is quotient
• Decimal division is /

Defining Functions/Prodecures

• There are no return keywords in scheme. In scheme, the value of a call expression is the value of the last body.
• Instead of multiple return statements, Scheme uses nested conditional expressions.
  • if and cond evaluate to values themselves.
• If and cond can also skip evaluating conditions. It will only evaluate a condition if we reach that point.
• In scheme, only false is the false value, everything else is true.
• The Nonetype in scheme is just undefined.
• The value of a define expression is the name of the procedure we define
• We may mimic if-elif-else behavior with nested ifs

(if (condition) (return value) (if (condition2) (return value true) (return value false)))

Special forms

• Some Scheme combinations are not call expressions because they are special forms

scm> (define (f x) (print x) False)
scm> (and (f 3) (f 4))
3
#4

• Scheme has no for/while statements, so recursion is required to iterate.
  • Ex: summiong first n values

(define (sum-first-n n)
    (define (f k total)
        (if (> k n)
            total
            (f (+ k 1) (+ total k))
        )
    )
    (f 1 0)
)

• We may create while and for loops in scheme but that requires another special form, which requires a macro.

Lambda Expressions

• Lambda expressions evaluate to anonymous procedures
  • (lambda (arguments) (return value))

Cond & Begin

• Cond behaves like an if-elif-else statement

(print
    (cond
        ((> x 10) 'big)
        ((> x 5) 'medium)
        (else 'small)
    )
)

• begin allows us to combine multiple expressions into one expression

Examples

• Write a-plus-abs-b that adds a+abs(b)

(define (a-plus-abs-b a b)
    ((if (> 0 b) - +) a b)
)