Scheme

Monday, 7/26

Announcements

  • Homework 8 due Monday (today)
  • Project 3 due Tuesday, 7/28
    • Office hours this Monday, 1 - 7 in Wozniak Lounge
    • Office hours this Tuesday, 1 - 4 in Wozniak Lounge
  • Lab makeup for lab 7 to lab 10, due Thursday 7/30
  • Lab 11 and Lab 12 due Saturday, 8/1
  • Maps composition revision due Monday, 8/3
    • Re-submit project 2 through OK to earn back points on maps composition
    • You can email your grader if you need clarification on their comments

Announcements (continued)

  • Midterm 2 is Thursday, 7/30
    • Midterm 2 information page
    • More free response as opposed to fill-in-the-blank on the midterm
    • CSM review session Tuesday, 5 - 8 in Wozniak Lounge
  • One-on-one tutoring
    • Form will be released at the end of every week
    • If you want to meet with the same tutor every week, mention it in the comments
  • Slower-paced section starting tomorrow (Tuesday)
    • Yulin's 2:30 - 4 discussion in 3113 Etcheverry
  • Second 61A Potluck on Friday, 7/31 from 5 - 8!
    • Bring board games and food!
    • 1v1 Albert in Super Smash Bros.

Review of Iterators: Iterables

  • Iterable: the object that represents sequential data
  • Iterables must have an __iter__ method

>>> iterable = range(3)

ranges are iterables!

class range:

...

def __iter__(self):

...

Iterable

0, 1, 2, 3, ...

range(3)

Review of Iterators: Iterators

>>> iterable.__iter__()

<range_iterator object at ...>

>>> iter(iterable)

<range_iterator object at ...>

>>> iterable = range(3)

  • __iter__ must return an iterator
  • Iterator: the object that actually computes the sequential data

class range:

...

def __iter__(self):

...

Iterable

class range_iterator:

...

Iterator

Review of Iterators: __next__

>>> iterator = iter(iterable)

>>> next(iterator)

0

>>> next(iterator)

1

>>> iterable = range(3)

  • Iterators must have:
    • __next__ method: returns the next element
    • __iter__ method: must return self for iterators

class range:

...

def __iter__(self):

...

Iterable

class range_iterator:

...

def __next__(self):

...

def __init__(self):

...

Iterator

Review of Iterators: StopIteration

  • __next__ computes the next element
    • next(iterator) is equivalent to
    • iterator.__next__()
  • If there are no more elements, raise StopIteration
    • Denotes the end of the sequence

>>> iterator = iter(iterable)

>>> next(iterator)

0

>>> next(iterator)

1

>>> next(iterator)

2

>>> next(iterator)

Traceback (most recent call last):

...

StopIteration

>>> iterable = range(3)

Review of Iterators: Comparison

__iter__: returns an iterator

Iterable

Iterator

__iter__: returns self

__next__: returns next element

represents sequential data

computes sequential data

class range:

...

def __iter__(self):

...

Iterable

class range_iterator:

...

def __next__(self):

...

def __init__(self):

...

Iterator

Review of Iterators: Implementing iterables and iterators

class range:

def __init__(self, stop):

self.stop = stop

def __iter__(self):

return range_iterator(self.stop)

class range_iterator:

def __init__(self, stop):

self.stop = stop

self.curr = 0

def __iter__(self):

return self

def __next__(self):

if self.curr >= self.stop:

raise StopIteration

elem = self.curr

self.curr += 1

return elem

Iterable

Iterator

(demo)

Review of Iterators: Lazy evaluation

class range:

def __init__(self, stop):

self.stop = stop

def __iter__(self):

return range_iterator(self.stop)

Iterable

  • Notice the range class does not store all of the elements
  • The range_iterator computes the next element on demand
  • Iterators allow for lazy evaluation of elements

Review of Iterators: for loops

seq = range(5)

for elem in seq:

print(elem * elem)

seq = range(5)

iterator = iter(seq)

try:

while True:

elem = next(iterator)

print(elem * elem)

except StopIteration:

pass

Python's way of saying "do nothing"

Equivalent

for loops are syntactic sugar: not necessary, but make programming a lot easier!

Review of Iterators: Generator functions

  • Generator function: a function that uses a yield statement
  • Generator functions return a generator object (a type of iterator)
    • Calling the generator function doesn't execute the body of the function
  • Calling next on the generator object executes code until first yield statement
    • Calling next resumes at stopping point

def naturals():

i = 1

while True:

yield i

i += 1

>>> naturals()

<generator object ...>

>>> iterator = naturals()

>>> next(iterator)

1

>>> next(iterator)

2

Review of Iterators: range as a generator function

>>> iterator = iter(iterable)

>>> next(iterator)

0

>>> next(iterator)

1

>>> next(iterator)

2

>>> next(iterator)

StopIteration

>>> iterable = range(3)

def range(stop):

curr = 0

while curr < stop:

yield curr

curr += 1

class range:

def __init__(self, stop):

self.stop = stop

def __iter__(self):

return range_iterator(self.stop)

class range_iterator:

def __init__(self, stop):

self.stop = stop

self.curr = 0

def __iter__(self):

return self

def __next__(self):

if self.curr >= self.stop:

raise StopIteration

elem = self.curr

self.curr += 1

return elem

Review of Iterators: Recursion with generator functions

def naturals():

i = 1

while True:

yield i

i += 1

Iterative

def naturals():

yield 1

for i in naturals():

yield i + 1

Recursive

>>> naturals()

>>> iterator = naturals()

naturals(): 1

1

>>> next(iterator)

2

>>> next(iterator)

naturals():

2

1

naturals():

1

2

3

>>> next(iterator)

3

naturals():

1

2

3

4

>>> next(iterator)

4

This should help with make_s on Homework 8...

Scheme

  • Scheme
    • Primitives and call expressions
  • Special forms
    • Defining variables
    • Conditionals
    • Functions
    • Let
  • Pairs and lists
    • cons, car, and cdr
    • Manipulating lists

Interpretation

Functions

Describing computations

Data

Storing information

State

Changing information over time

Interpretation

Evaluating programs

  • Interpretation
    • Python is an interpreter
    • Project 4: build a Scheme interpreter
    • First, we have to learn Scheme!

Scheme: Learning another language!

  • Scheme is a dialect of Lisp
    • One of the oldest languages still in use today! (1958)
  • Lisp and its variants (including Scheme) are known for
    • Simple but powerful syntax
    • Lots of parentheses

https://xkcd.com/297/

Scheme

  • Scheme is an interpreted language
    • Like Python
  • CS 61A uses a custom Scheme interpreter
    • Slightly different from other versions of Scheme

~$ python3 scheme

Welcome to the CS 61A Scheme interpreter v1.0.4

scm>

Scheme

  • Scheme
    • Primitives and call expressions
  • Special forms
    • Defining variables
    • Conditionals
    • Functions
  • Pairs and lists
    • cons, car, and cdr
    • Manipulating lists

Primitives

scm> 5

5

scm> 3.14

3.14

scm> True

True

scm> #t

True

scm> False

False

scm> #f

False

>>> 5

5

>>> 3.14

3.14

>>> True

True

>>> False

False

Python

Scheme

Call expressions

>>> mul(5, 4)

20

>>> 5 + 4 + 3 + 2 + 1

15

scm> (* 5 4)

20

scm> (+ 5 4 3 2 1)

15

Python

Scheme

( + 5 4 )

operator

operand

operand

  • Evaluate operator and operands, left to right
  • Apply operator value on operand values

Call expressions: built-in functions

>>> 6 - 2

4

>>> 5 % 3

2

>>> 5 == 4

False

>>> 5 != 4

True

>>> 5 > 4

True

scm> (- 6 2)

4

scm> (modulo 5 3)

2

scm> (= 5 4)

False

scm> (not (= 5 4))

True

scm> (> 5 4)

True

Python

Scheme

infix notation

prefix notation

Defining variables

>>> x = 5

>>> y = x + 3

>>> x * y

40

scm> (define x 5)

x

scm> (define y (+ x 3))

y

scm> (* x y)

40

Python

Scheme

Symbols

scm> (define a 5)

a

scm> 'a

a

scm> 'hello-world

hello-world

  • Symbol: treated literally by the interpreter
    • Not a string
  • Denoted with a single quote

Scheme

  • Scheme
    • Primitives and call expressions
  • Special forms
    • Defining variables
    • Conditionals
    • Functions
  • Pairs and lists
    • cons, car, and cdr
    • Manipulating lists

Special forms: defining variables

  • Special form: an expression that does not follow the normal evaluation procedure
  • Example:
    • define statement looks like a call expression
    • but we don't evaluate the first "operand", the variable name

( define x (+ 4 5) )

  • Evaluate operator and operands, left to right
  • Apply operator value on operand values

Not evaluated

Special forms: boolean operators

>>> True and False

False

>>> False and 1 / 0 and 5

False

scm> (and True False)

False

scm> (and False (/ 1 0) 5)

False

>>> True or False

True

>>> True or 1 / 0 or 5

True

scm> (or True False)

True

scm> (or True (/ 1 0) 5)

True

( and False (/ 1 0) 5 )

Python

Scheme

Short-circuits: stops evaluation here

Special forms: if statements

>>> x = 0

>>> if x == 5:

... 1 / 0

... else:

... x - 42

-42

scm> (define x 0)

x

scm> (if (= x 5)

(/ 1 0)

(- x 42))

-42

>>> if x > 0:

... 3

scm> (if (> x 0)

(+ x 3))

okay

( if (= x 0) (+ x 3) (- x 42) )

Python

Scheme

Only one clause is evaluated

Similar to None

Special forms: cond statements

>>> x = 0

>>> if x == 5:

... 1 / 0

... elif x < 5:

... x + 2

... else:

... x - 42

2

scm> (define x 0)

x

scm> (cond ((= x 5) (/ 1 0))

((< x 5) (+ x 2))

(else (- x 42)))

2

( cond ((= x 5) (/ 1 0)) ((< x 5) ( + x 2)))

Python

Scheme

Pairs of condition and return value

Special forms: lambda statements

>>> lambda x, y: x + y

<function <lambda> ...>

>>> neg = lambda x: -x

>>> neg(4)

-4

>>> (lambda x: -x)(4)

-4

scm> (lambda (x y) (+ x y))

(lambda (x y) (+ x y))

scm> (define neg

(lambda (x) (- x))

neg

scm> (neg 4)

-4

scm> ((lambda (x) (- x)) 4)

-4

( lambda (x y) (+ x y) )

Python

Scheme

parameters

return value

Special forms: defining functions

scm> (define (mul x y)

(* x y))

mul

scm> (define (square x)

(mul x x))

square

scm> (square 4)

16

>>> def mul(x, y):

... return x * y

>>> def square(x):

... return mul(x, x)

>>> square(4)

16

( define (mul x y) (* x y) )

Python

Scheme

name

return value

parameters

Scheme

  • Scheme
    • Primitives and call expressions
  • Special forms
    • Defining variables
    • Conditionals
    • Functions
  • Pairs and lists
    • cons, car, and cdr
    • Manipulating lists

Pairs and lists

  • In the 1950s, computer scientists used confusing names
    • cons: creates a pair
    • car: returns first element of a pair
    • cdr: returns second element of a pair
    • nil: the empty list

scm> (define x (cons 1 3))

x

scm> (car x)

1

scm> (cdr x)

3

scm> nil

()

Pairs and lists

  • Creating lists from pairs
    • A Scheme list is a pair where the second element is also a Scheme list or the empty list

scm> (cons 1 (cons 2 (cons 3 nil)))

(1 2 3)

scm> (define x (cons 4 (cons 3 nil)))

x

scm> (car x)

4

scm> (cdr x)

(3)

scm> (cons 3 nil)

(3)

(cdr x) is a list containing 3

Scheme list?

Linked list!

'I'

'linked'

'lists!'

'hate'

Pairs and lists

scm> (cons 1 2)

(1 . 2)

scm> (cons 1 (cons 2 nil))

(1 2)

  • Pairs whose second elements are not Scheme lists are called malformed lists

dot denotes malformed list

1

2

(cons 1 2)

1

2

(cons 1 (cons 2 nil))

Quoting pairs and lists

scm> (cons 1 (cons 2 nil))

(1 2)

scm> '(1 2)

(1 2)

scm> (define x '(1 2 3 4 5 6))

scm> (car x)

1

scm> (cdr x)

(2 3 4 5 6)

scm> (car (cdr x))

2

scm> (cons 1 2)

(1 . 2)

scm> '(1 . 2)

(1 . 2)

  • Use single quote to quickly create lists and pairs
    • Symbol: expression that follows the quote is treated literally

Scheme

  • Scheme
    • Primitives and call expressions
  • Special forms
    • Defining variables
    • Conditionals
    • Functions
  • Pairs and lists
    • cons, car, and cdr
    • Manipulating lists

Manipulating lists

  • Implement (map fn lst):
    • fn is a one argument function
    • lst is a well-formed Scheme list
  • Return a new list that contains elements of lst with fn applied each element

(define (map fn lst)

Manipulating lists

  • How would you implement map in Python? (using linked lists)
    • Use recursion!

def map(fn, lst):

if lst is Link.empty:

return Link.empty

return Link(fn(lst.first),

map(fn, lst.rest))

  • Translate into Scheme

(define (map fn lst)

(if (null? lst)

nil

(cons (fn (car lst))

(map fn (cdr lst)))))

  • Why can't we use iteration?
    • Basic versions of Scheme don't have iteration
    • Must use recursion!
21-Scheme - Google Slides