6.001/Recitation 1

Rob Speer

Recitation for February 8, 2006.

Contents 1 Problem to ponder 2 Important stuff 3 What is Scheme? 4 Scheme syntax 4.1 Atomic expressions 4.2 Names 4.3 Combinations 5 The substitution model 5.1 Special forms 6 Practice 7 Recursion

Problem to ponder

I'll give you one of these in a bunch of recitations. Think about it if you get bored.

Today's problem: Make an infinite loop without using define.

Important stuff

Problem sets

Due online every Tuesday.

Lecture problems

Look like problem set problems, but they're easier and due sooner. Some are due on Friday.

Projects

Due every 2 or 3 weeks. Programmed in your own DrScheme and turned in through the tutor.

Project 0 is due Friday.

Remember that the web site has lots of resources for assistance on it. There are hordes of people who are even more panicked than you.

What is Scheme?

• Based on LISP, but smaller
• Functional
  • but not purely functional
• Good at representing:
  • Linked lists
  • Higher-order procedures
  • Itself
• Many competing implementations

Scheme syntax

Scheme code is made of these things:

Atomic expressions

Also called self-evaluating expressions. Numbers and strings are some of these.

Names

Names (you might know them as "variables", but they won't be varying very much for a while) can be assigned to other expressions.

(define answer 42)
(define s "I am a rather long string")

Combinations

• Always surrounded by parentheses
• Every parenthesis is meaningful
• Prefix notation

(+ 1 2)
(* 3 (+ 1 2))
(/ (* 2 6) (+ 3 1))

The substitution model

A model for how Scheme code evaluates to a result. It's wrong. But so is the Bohr model of the atom, and we still teach that.

• Replace symbols by substituting in their definition.
• Replace primitives with their result.
• Replace lambdas by substituting the formal arguments.
• Repeat until you get an answer.

Special forms

• You'll be using special forms to define things.
• λ creates functions.
  • Alt-\ types a lambda in MzScheme. The word lambda suffices, too.
• define creates names.
• Frequently you use both, because you want functions to have names.
• Syntactic sugar hides a lambda inside of a define.

Practice

What is the value of the last expression below?

   (define double-oh-one +)
   (define is 1)
   (define fun 2)
   (double-oh-one is fun)    

Evaluate each of the following expressions in order (building on previous ones if necessary). If evaluation results in an error, simply write "error".

    4

    5.5

    4.2e1

    (+ 1 2)

    (7)

    (* (+ 7 8) (   -  5 6))

    (define one 1)

    (define two (+ 1 one))

    (define five 3)

    (+ five two)

    (define biggie-size *)

    (define hamburger 1)

    (biggie-size hamburger five)

    (= 7 (+ 3 4))

    (= #t #f)

    ((+ 5 6))

    biggie-size

Recursion

• Recursion is the only way to loop.
• Tail recursion makes recursion efficient.
• Recursive vs. iterative procedures
• Let's get the damn factorial function out of the way and never speak of it again.