Discussion 10: Scheme, Scheme Lists

This is an online worksheet that you can work on during discussions and tutorials. Your work is not graded and you do not need to submit anything.

Discussion 10 Vitamin

To encourage everyone to watch or attend discussion orientation, we have created small discussion vitamins. If you complete 5 of the 6 vitamins, you can earn one point of extra credit added to your final grade in the course. Please answer all of the questions in this form by Thursday at 11:59 PM.

Introduction

In the next part of the course, we will be working with the Scheme programming language. In addition to learning how to write Scheme programs, we will eventually write a Scheme interpreter in Project 4!

Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.

Primitives and Defining Variables

Scheme has a set of atomic primitive expressions. Atomic means that these expressions cannot be divided up.

scm> 123
123
scm> #t
True
scm> #f
False

Unlike in Python, the only primitive in Scheme that is a false value is #f and its equivalents, false and False. This means that 0 is not false.

The define special form defines variables and procedures by binding a value to a variable, just like the assignment statement in Python. When a variable is defined, the define special form returns a symbol of its name. A procedure is what we call a function in Scheme.

The syntax to define a variable and procedure are:

  • (define <variable name> <value>)
  • (define (<function name> <parameters>) <function body>))

Special forms are types of expressions with unique evaluation rules that can do a variety of things. Often times, speical forms are analagous to statements in Python, such as assignment statements, if statements, and def statements. However, all special forms in Scheme evaluate to a value. We'll learn more about special forms later in the discussion.

Questions

scm> (define a 1)
a
scm> a
1
scm> (define b a)
b
scm> b
1
scm> (define c 'a)
c
scm> c

Call Expressions

Call expressions apply a procedure to some arguments.

(<operator> <operand1> <operand2> ...)

Call expressions in Scheme work exactly like they do in Python. To evaluate them:

  1. Evaluate the operator to get a procedure.
  2. Evaluate each of the operands from left to right.
  3. Apply the value of the operator to the evaluated operands.

For example, consider the call expression (+ 1 2). First, we evaluate the symbol + to get the built-in addition procedure. Then we evaluate the two operands 1 and 2 to get their corresponding atomic values. Finally, we apply the addition procedure to the values 1 and 2 to get the return value 3.

Operators may be symbols, such as + and *, or more complex expressions, as long as they evaluate to procedure values.

scm> (- 1 1)                 ; 1 - 1
0
scm> (/ 8 4 2)               ; 8 / 4 / 2
1
scm> (* (+ 1 2) (+ 1 2))     ; (1 + 2) * (1 + 2)
9

Some important built-in functions you'll want to know are:

  • +, -, *, /
  • =, >, >=, <, <=
  • quotient, modulo, even?, odd?, null?

Questions

What would Scheme display? As a reminder, the built-in quotient function performs floor division.

scm> (define a (+ 1 2))
a
scm> a
3
scm> (define b (- (+ (* 3 3) 2) 1))
b
scm> (+ a b)
13
scm> (= (modulo b a) (quotient 5 3))
#t

Special Forms

Special form expressions contain a special form as the operator. Special form expressions do not follow the same rules of evaluation as call expressions. Each special form has its own rules of evaluation -- that's what makes them special!

If Expression

An if expression looks like this:

(if <predicate> <if-true> [if-false])

<predicate> and <if-true> are required expressions and [if-false] is optional.

The rules for evaluation are as follows:

  1. Evaluate <predicate>.
  2. If <predicate> evaluates to a truth-y value, evaluate <if-true> and return its value. Otherwise, evaluate [if-false] if provided and return its value.

This is a special form because not all operands will be evaluated! Only one of the second and third operands is evaluated, depending on the value of the first operand.

Remember that only #f is a false-y value in Scheme; everything else is truth-y.

scm> (if (< 4 5) 1 2)
1
scm> (if #f (/ 1 0) 42)
42

Boolean operators

Like Python, Scheme also has the boolean operators and, or, and not. and and or are special forms because they are short-circuiting operators.

  • and takes in any amount of operands and evaluates these operands from left to right until one evaluates to a false-y value. It returns that first false-y value. If there are no false-y values, it returns the value of the last expression (or #t if there are no operands)
  • or also evaluates any number of operands from left to right until one evaluates to a truth-y value. It returns that first truth-y value. If there are no truth-y values, it returns the value of the last expression (or #f if there are no operands)
  • not takes in a single operand, evaluates it, and returns its opposite truthiness value. Note that not is a regular procedure and not a special form.

Important note: the only false-y value in scheme is #f. In particular, 0 is truth-y!

scm> (and 25 32)
32
scm> (or 1 (/ 1 0))    ; Short-circuits
1
scm> (not (odd? 10))
#t

Questions

What would Scheme display?

scm> (if (or #t (/ 1 0)) 1 (/ 1 0))
1
scm> ((if (< 4 3) + -) 4 100)

Lambdas and Defining Functions

All Scheme procedures are lambda procedures. One way to create a procedure is to use the lambda special form.

(lambda (<param1> <param2> ...) <body>)

This expression creates a lambda function with the given parameters and body, but does not evaluate the body. Just like in Python, the body is not evaluated until the function is called and applied to some argument values. The fact that neither operand is evaluated is what makes lambda a special form.

Another similarity to Python is that lambda expressions do not assign the returned function to any name. We can assign the value of an expression to a name with a define special form.

For example, (define square (lambda (x) (* x x))) creates a lambda procedure that squares its argument and assigns that procedure to the name square.

The second version of the define special form is a shorthand for this function definition:

(define (<name> <param1> <param2 ...>) <body>)

This expression creates a function with the given parameters and body and binds it to the given name.

scm> (define square (lambda (x) (* x x))) ; Bind the lambda function to the name square
square
scm> (define (square x) (* x x))          ; Equivalent to the line above
square
scm> square
(lambda (x) (* x x))
scm> (square 4)
16

Questions

Q1: Factorial

Write a function that returns the factorial of a number.

Your Answer
Run in 61A Code
Solution
(define (factorial x)
(if (< x 2) 1 (* x (factorial (- x 1)))))

Walkthrough video

Q2: (Tutorial) Fibonacci

Write a function that returns the n-th Fibonacci number.

Your Answer
Run in 61A Code
Solution
(define (fib n)
(if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))
)
scm> (fib 0)
0
scm> (fib 1)
1
scm> (fib 10)
55

Pairs and Lists

All lists in Scheme are linked lists. Scheme lists are composed of two element pairs. We define a list as being either

  • the empty list, nil
  • a pair whose second element is a list

As in Python, linked lists are recursive data structures. The base case is the empty list.

We use the following procedures to construct and select from lists:

  • (cons first rest) constructs a list with the given first element and rest of the list. For now, if rest is not a pair or nil it will error.
  • (car lst) gets the first item of the list
  • (cdr lst) gets the rest of the list
scm> nil
()
scm> (define lst (cons 1 (cons 2 (cons 3 nil))))
lst
scm> lst
(1 2 3)
scm> (car lst)
1
scm> (cdr lst)
(2 3)
scm> (car (cdr lst))
2
scm> (cdr (cdr (cdr lst)))
()

The rule for displaying lists is very similar to that for the Link class from earlier in the class's __str__ method. It prints out the elements in the linked list as if the list has no nested structure. The only difference is that Link.__str__ uses angle brackets <> and scheme uses parentheses ().

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

Two other common ways of creating lists is using the built-in list procedure or the quote special form:

  • The list procedure takes in an arbitrary amount of arguments. Because it is a procedure, all operands are evaluated when list is called. A list is constructed with the values of these operands and is returned.
  • The quote special form takes in a single operand. It returns this operand exactly as is, without evaluating it. Note that this special form can be used to return any value, not just a list.
scm> (define x 2)
scm> (define y 3)
scm> (list 1 x 3)
(1 2 3)
scm> (quote (1 x 3))
(1 x 3)
scm> '(1 x 3)   ; Equivalent to the previous quote expression
(1 x 3)
scm> '(+ x y)
(+ x y)

=, eqv?, equal?

  • = can only be used for comparing numbers.
  • eqv? behaves like == in Python for comparing two non-pairs (numbers, booleans, etc.). Otherwise, eqv? behaves like the Python is operator.
  • equal? compares pairs by determining if their cars are equal? and their cdrs are equal? (that is, they have the same contents). Otherwise, equal? behaves like eqv?.
scm> (define a '(1 2 3))
a
scm> (= a a)
Error
scm> (equal? a '(1 2 3))
#t
scm> (eqv? a '(1 2 3))
#f
scm> (define b a)
b
scm> (eqv? a b)
#t

Questions

Q3: List Concatenation

Write a function which takes two lists and concatenates them.

Notice that simply calling (cons a b) would not work because it will create a deep list. Do not call the builtin procedure append, since it does the same thing as list-concat should do.

Your Answer
Run in 61A Code
Solution
(define (list-concat a b)
(if (null? a) b (cons (car a) (list-concat (cdr a) b)))
)
scm> (list-concat '(1 2 3) '(2 3 4))
(1 2 3 2 3 4)

Q4: (Tutorial) Warm-up

These short questions are meant to help refresh your memory of topics covered in lecture and lab this week before tackling more challenging problems.

Describe the difference between the following two Scheme expressions. Hint: which defines a new procedure?

Expression A:

(define x (+ 1 2 3))

Expression B:

(define (x) (+ 1 2 3))
Expression A binds the name x to the value 6. Expression B defines a new procedure named x that takes in no arguments and returns 6. The key difference between these two is the parentheses around x, which contains the name of the new procedure as well as its formal parameters.

Write an expression that selects the value 3 from the list below.

(define s '(5 4 (1 2) 3 7))
(car (cdr (cdr (cdr s))))

Q5: (Tutorial) List Duplicator

Write a Scheme function that, when given a list, such as (1 2 3 4), duplicates every element in the list (i.e. (1 1 2 2 3 3 4 4)).

Your Answer
Run in 61A Code
Solution
(define (duplicate lst)
(if (null? lst) lst (cons (car lst) (cons (car lst) (duplicate (cdr lst)))))
)

Q6: (Tutorial) List Insert

Write a Scheme function that, when given an element, a list, and an index, inserts the element into the list at that index. You can assume that the index is in bounds for the list.

Your Answer
Run in 61A Code
Solution
(define (insert element lst index)
(if (= index 0) (cons element lst) (cons (car lst) (insert element (cdr lst) (- index 1))))
)