1 of 17

Lecture 19: Scheme I

Catherine Han & Matthew Jeng

07/24/2017

2 of 17

Interpreters

Goals for the week:

  • Getting a new language (Scheme) under your belt!
  • Figuring out how interpreters work
    • Applying these concepts through Scheme

Introduction

Data

Mutability

Objects

Interpreters

Paradigms

Applications

Functions

3 of 17

Scheme

4 of 17

What is Scheme?

  • Dialect of Lisp
    • “The greatest single programming language ever designed”

- Alan Kay (co-creator of OOP) on Lisp

  • Known for how powerful it can be with such “simple” syntax, meaning it is known for its ridiculous amount of parentheses!
    • “Lots of Irritating Single Parentheses”

​

5 of 17

Scheme Basics

  • Scheme primitive expressions:
    • Include numbers, booleans, symbols, strings, etc.
  • Scheme call expressions:
    • Combinations of expressions
    • Consist of an operator followed by zero or more operands, and don’t forget the parentheses!

scm> (+ 1 2)

3

scm> (quotient (+ 5 5) (- 4 1))

3

scm> (+ (* 2 8)

(* 3

(+ (+ 1 2)

(+ 3 8))))

58

>>> 1 + 2

3

>>> (5 + 5) // (4 - 1)

3

>>> (2 * 8) + (3 * ((1 + 2) + (3 + 8)))

58

6 of 17

Special Forms

Not your average Scheme expression

An expression that follows special evaluation rules; they are evaluated differently from call expressions

Include: assignment expressions, quoting, lambda expressions, conditionals

7 of 17

Assignment Expressions

  • Expressions vs. Statements
    • In Python, we had statements
  • Scheme symbols are analogous to what we called names in Python
    • (define <symbol> <expression>)
    • Evaluates <expression> to a value, then binds that value to <symbol>
    • define expressions evaluate to the symbol (binding is simply a side effect)

scm> (define kevin 61)

kevin

scm> kevin

61

scm> (define stan (+ kevin 1956))

stan

scm> stan

2017

>>> kevin = 61

>>> kevin

61

>>> stan = kevin + 1956

>>> stan

2017

8 of 17

Symbols and the Quote Expression

  • Symbols are analogous to names in Python
    • So what’s the difference?
  • *:･✧Magical ✧･:* combination of strings and names
  • Can access the symbol itself and not their bound value by using the next special form, quote
    • Used to modify or prevent the evaluation of objects

​

scm> (define life 42)

life

scm> life

42

​

scm> (quote life)

life

scm> ‘life ; shorthand for (quote life)

life

9 of 17

Lambda Expressions

  • (2) More commonly, we can bind the lambda expression to a symbol

​

  • lambda expressions evaluate to anonymous procedures
    • (lambda (<formal-parameters>) <body>)
  • What can we do with a lambda expression in Scheme?
  • (1) We can use it directly as the operator of a call expression
    • This is so common, that there’s a second, shorthand, way to do this!
    • (define (<symbol> <formal-parameters>) <body>)

scm> ((lambda (x) (* x x)) 4)

​

Operand

Operator

scm> (define square (lambda (x) (* x x)))

square

​

scm> (define (square x) (* x x))

square

​

…………………………………………………………………

scm> (square 4)

16

16

​

10 of 17

Conditions and Booleans

  • There are two kinds of conditional expressions
    • (if <predicate> <consequent> <alternative>)
      • <predicate> evaluates to a true/false value. If true, <consequent> executes. Otherwise, <alternative>.
    • If we wanted to chain multiple conditionals together (similar to if-elif-else in Python), we could use the cond expression

​

  • Boolean expressions (and <e1> <e2> ...), (or <e1> <e2> ...) short-circuit just like how Python boolean expressions short-circuit
  • In Scheme, only #f (and false and False) are false values!

scm> (cond ((= 3 4) 4)

((= 3 3) 0)

(else 'burp))

0

(demo)

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

false

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

true

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

5

11 of 17

Pairs and Lists

Scheme data structures

• The pair is the basic compound value in Scheme

• Lists in Scheme are created using pairs; they’re linked lists

12 of 17

Pairs and Lists

  • Pairs are created using the cons expression in Scheme
  • car selects the first element in a pair
  • cdr selects the second element in a pair

​

scm> (define x (cons 1 3))

x

scm> x

(1 . 3)

scm> (car x)

1

scm> (cdr x)

3

13 of 17

Pairs and Lists

  • The only type of sequence in Scheme is the linked list
    • We can create these with pairs using multiple cons expressions
  • nil represents the empty list

​

  • Can also use the list expression as a shorthand way of creating linked lists

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

x

scm> x

(1 2 3)

scm> (car x)

1

scm> (cdr x)

(2 3)

​

scm> y

(1 2 3)

scm> (car y)

1

scm> (cdr y)

(2 3)

​

scm> z

(1 2 3)

scm> (car z)

1

scm> (cdr z)

(2 3)

​

scm> (define z ‘(1 2 3)) ; shortest-hand

z

scm> (define y (list 1 2 3)) ; shorthand

y

(demo)

14 of 17

Coding Tips

  • A good way to approach writing Scheme procedures is to think about it/write it out in Python first using linked lists and recursion
    • Basic versions of Scheme don’t have iteration
  • Usually pretty easy to translate to Scheme if you write it out in Python first
  • Indentations/new lines don’t matter in terms of execution
    • Use them to help organize your code!
  • Check your parentheses!!

​

15 of 17

Example

  • Let’s implement a procedure (map fn lst) which takes in a one-argument procedure fn, and returns a (linked) list with fn applied to each element of lst

(define (map fn lst)

(if (null? lst)

nil

(cons (fn (car lst)) (map fn (cdr lst)))))

(demo)

16 of 17

Example

  • We can create a tree abstraction like we did in Python:
  • Let’s write a procedure (square-tree t) that takes in a tree t and returns a tree with all its values squared
    • Let’s use the tree abstraction, square, and map!

(define (tree root branches)

(cons root branches))

​

(define (root tree) (car tree))

​

(define (branches tree) (cdr tree))

​

(define (leaf? tree) (null? (branches tree)))

(demo)

(define (square-tree t)

(tree (square (root t))

(if (leaf? t)

nil

(map square-tree (branches t)))))

17 of 17

Summary

  • We learned a new language today! Being able to pick up languages quickly is an important skill for good programmers.
  • Don’t be overwhelmed though!
    • If you’re stuck, try thinking of the Python analog and working from there
  • Scheme is a simpler, but still powerful, language
    • Everything in Scheme is an expression
    • Recursion
  • “How do I get better at Scheme?”
    • Practice
    • Practice
    • Practice