Discussion 10: Scheme, Scheme Lists
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)
scm> a
scm> (define b a)
scm> b
scm> (define c 'a)
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:
- Evaluate the operator to get a procedure.
- Evaluate each of the operands from left to right.
- 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))
scm> a
scm> (define b (- (+ (* 3 3) 2) 1))
scm> (+ a b)
scm> (= (modulo b a) (quotient 5 3))
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:
- Evaluate
<predicate>
. - 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 thatnot
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))
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.
Run in 61A CodeQ2: (Tutorial) Fibonacci
Write a function that returns the n
-th Fibonacci number.
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, ifrest
is not a pair ornil
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 whenlist
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 Pythonis
operator.equal?
compares pairs by determining if theircar
s areequal?
and theircdr
s areequal?
(that is, they have the same contents). Otherwise,equal?
behaves likeeqv?
.
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.
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))
Write an expression that selects the value 3 from the list below.
(define s '(5 4 (1 2) 3 7))
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)
).
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.
Run in 61A Code