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.
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. This means that 0 is not false.
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,
def statements. However, all special forms in Scheme evaluate to a value.
We'll learn more about special forms later in the discussion.
scm> (define a 1)
scm> (define b a)
scm> (define c 'a)
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
+ to get the built-in addition procedure. Then we evaluate
the two operands
2 to get their corresponding atomic
values. Finally, we apply the addition procedure to the values
2 to get the return value
Operators may be symbols, such as
*, 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:
What would Scheme display? As a reminder, the built-in
quotient function performs floor division.
scm> (define a (+ 1 2))
scm> (define b (- (+ (* 3 3) 2) 1))
scm> (+ a b)
scm> (= (modulo b a) (quotient 5 3))
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 looks like this:
(if <predicate> <if-true> [if-false])
<if-true> are required expressions and
[if-false] is optional.
The rules for evaluation are as follows:
<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
scm> (if (< 4 5) 1 2) 1 scm> (if #f (/ 1 0) 42) 42
Like Python, Scheme also has the boolean operators
special forms because they are short-circuiting operators.
andtakes 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
#tif there are no operands)
oralso 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
#fif there are no operands)
nottakes in a single operand, evaluates it, and returns its opposite truthiness value. Note that
notis 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
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.
(define square (lambda (x) (* x x))) creates a lambda
procedure that squares its argument and assigns that procedure to the name
The second version of the
define special form is a shorthand for this
(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
Write a function that returns the factorial of a number.Your Answer Run in 61A Code
(define (factorial x)(if (< x 2) 1 (* x (factorial (- x 1)))))
Q2: (Tutorial) Fibonacci
Write a function that returns the
n-th Fibonacci number.
(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,
- 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
restis not a pair or
nilit 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
procedure or the
quote special form:
listprocedure takes in an arbitrary amount of arguments. Because it is a procedure, all operands are evaluated when
listis called. A list is constructed with the values of these operands and is returned.
quotespecial 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.
==in Python for comparing two non-pairs (numbers, booleans, etc.). Otherwise,
eqv?behaves like the Python
equal?compares pairs by determining if their
equal?(that is, they have the same contents). Otherwise,
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
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.
(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?
(define x (+ 1 2 3))
(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))
(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)).
(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
(define (insert element lst index)(if (= index 0) (cons element lst) (cons (car lst) (insert element (cdr lst) (- index 1)))))