```Scheme for Rubyists
Scheme History


Authors: Guy Steele and Gerald Sussman
Structure and Interpretation of Computer
Programs (SICP) by Abelson & Sussman

http://mitpress.mit.edu/sicp/

http://www.archive.org/details.php?identifier=mit_ocw_sicp
Scheme in Real Life

GIMP (Script-Fu)

Guile (official extension language of GNU)

Lily Pond (sheet music engraving)
Scheme is a Lisp dialect

LISP ==> “LISt Processing language”
Scheme is a Lisp dialect


LISP ==> “LISt Processing language”
LISP ==>
Lots of Irritating Superfluous Parentheses
Lisp


Family of languages:

Common Lisp

Scheme

Emacs Lisp

Clojure

Arc
First incarnation by John McCarthy, 1958

older than COBOL (!)
Lisp vs. the World

Prefix notation
(+ x y)
(< x y)
(eq? x y)
Lisp vs. the World

No operator precedence rules
(mandatory parentheses eliminate the need)
(sqrt (+ (/ (* 3 4) 2) 3))
Lisp vs. the World

No operator precedence rules
(mandatory parentheses eliminate the need)
(sqrt (+ (/ (* 3 4) 2) 3))
==> 3
Lisp vs. the World

Functions are first-class objects, so we can:

Assign them to variables

Pass them as parameters to other functions

Return them from other functions
Lisp vs. the World
Example of 1st-class function use in Scheme
(Scheme's map =~ Ruby's map or collect)
(define square
(lambda (x) (* x x)))
(map square
(list 1 2 3 4 5 6 7 8 9))
Lisp vs. the World
Example of 1st-class function use in Scheme
(Scheme's map =~ Ruby's map or collect)
(define square
(lambda (x) (* x x)))
(map square
(list 1 2 3 4 5 6 7 8 9))
==> (1 4 9 16 25 36 49 64 81)
Lisp vs. the World

Linked lists are built in; based on pairs
“a”
1
#\b
(empty list)
2

4
Scheme representation:
(1 2 “a” 4 #\b)
Scheme vs. Other Lisps

Optimized tail recursion


Tail-recursive procedures are replaced by
iterative version in compilation


“Normal” looping constructs are not used
Why?
Even for mutually recursive procedures
Scheme vs. Other Lisps

Optimized tail recursion


Tail-recursive procedures are replaced by
iterative version in compilation


“Normal” looping constructs are not used
Why? So we don't blow the stack
Even for mutually recursive procedures
Mutual Tail Recursion
(define even?
(lambda (x)
(if (= x 0)
#t
(odd? (- x 1)))))
(define odd?
(lambda (x)
(if (= x 0)
#f
(even? (- x 1)))))
Why use recursion?

Some problems are more cleanly solved
Why use recursion?

Some problems are more cleanly solved

Especially in mathematics
{
1 if n==0 or n==1
factorial(n) =
n * factorial(n-1)
Why use recursion?
(define factorial
(lambda (n)
(cond ((or (= n 1) (= n 0)) 1)
(else (* n (factorial (- n 1)))))))

Nearly identical to math definition

Any problems?
Why use recursion?
(define factorial
(lambda (n)
(cond ((or (= n 1) (= n 0)) 1)
(else (* n (factorial (- n 1)))))))

Nearly identical to math definition

Any problems? not tail-recursive
Why use recursion?
(define factorial
(lambda (n)
(define factorial2
(lambda (n acc)
(cond ((or (= n 1) (= n 0)) acc)
(else
acc))))))
(factorial2 (- n 1) (* n
(factorial2 n 1)))

Now we're tail-recursive
Why use recursion?
(define factorial
(lambda (n)
(define factorial2
(lambda (n acc)
(cond ((or (= n 1) (= n 0)) acc)
(else
acc))))))
(factorial2 (- n 1) (* n
(factorial2 n 1)))
it depends

Now we're tail-recursive
A Tale of Two Factorial Solutions
Non-tail-recursive
Tail-recursive
(factorial 5)
(factorial 5)
(* 5 (factorial 4))
(factorial2 5 1)
(* 5 (* 4 (factorial 3)))
(factorial2 4 5)
(* 5 (* 4 (* 3 (factorial 2))))
(factorial2 3 20)
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(factorial2 2 60)
(* 5 (* 4 (* 3 (* 2 1))))
(factorial2 1 120)
(* 5 (* 4 (* 3 2)))
120
(* 5 (* 4 6))
(* 5 (24))
120
Scheme vs. Other Lisps

Scheme has a minimal set of standard features
Common Lisp has lots of built-in libraries

One namespace :(

Continuations


Representation of the state of execution
(think goto on steroids)
Also available in Ruby (callcc)
Prefix Notation
(+ 2 7)
=> 9
(* 2/3 5/8)
=> 5/12
(/ 1.0 3)
=> .333333333333
(= 2 (+ 0 3))
=> #f
(not (= (> 2 (+ 6 1)) #t))
=> #t
Defining Procedures
(lambda (x y)
(+ x y)))
(define truthy?
(lambda (x)
(not (= #f x))))
(define (truthy? x)
(not (= #f x)))
Quoting
(1 2 3)
;The object 1 is not applicable.
(quote (1 2 3))
==> (1 2 3)
'(1 2 3)
==> (1 2 3)
'testing
Applying Procedures
=> 24
(truthy? '(1 2 4))
=> #t
(truthy? #f)
=> #f
(truthy? 78)
=> #t
Parsing Lists
(car '(1 2 3))
==> 1
(cdr '(1 2 3))
==> (2 3)
Building Lists
(cons 1 2)
==> (1 . 2)
1
2
(cons 1 (cons 2 '()))
==> (1 2)
1
2
(empty list)
Building Lists
Will this work the way we expect?
(cons '(1 2 3) '(4 5 6))
Building Lists
Will this work the way we expect?
(cons '(1 2 3) '(4 5 6))
==> ((1 2 3) 4 5 6)
Building Lists
(cons 1 (cons 2 (cons 3 '(4 5 6))))
Building Lists
(cons 1 (cons 2 (cons 3 '(4 5 6))))
==> (1 2 3 4 5 6)
Yes, but this way sucks
Building Lists
The simpler solution:
(append '(1 2 3) '(4 5 6))
==> (1 2 3 4 5 6)
Functional Programming

The result depends only on the input(s)

No side effects

Easy to run in parallel
Scheme's functional-ness

Scheme encourages functional programming

But it doesn't require it (not purely functional)
(define x '(1 2 3))
x ==> (1 2 3)
(set-car! x 'stupid-symbol)
x ==> (stupid-symbol 2 3)
(set-cdr! x '(#t #f))
x ==> (stupid-symbol #t #f)
Getting Started with Scheme



MIT-Scheme: http://www.gnu.org/software/mit-scheme/

Emacs (indentation help)
http://www.aquamacs.org

Textmate Bundle
http://svn.textmate.org/trunk/Bundles/Scheme.tmbundle
Anything else we might want?
Anything else we might want?
Test Manager: xUnit for Scheme


http://web.mit.edu/~axch/www/index.html

Documentation:
http://web.mit.edu/~axch/www/testing.html
Test Manager Example
(define-each-test
(assert-equal 2 (factorial 2))
(assert-equal 6 (factorial 3))
(assert-equal 24 (factorial 4)))
(run-registered-tests)
Happy Happy Joy Joy
```