Writing a language in 15 minutes

Implementing Scheme using Ruby and Treetop

James Coglan

jcoglan.com

Scheme data

• Booleans: #t, #f
• Integers: 45, 0, 999
• Identifiers: foo, +, list?, string->number
• Lists: (a list of symbols)
• Procedures: (lambda (x y) (+ (/ x 2) y))

Scheme expressions

• All expressions are written as lists
• The first item in the list is a function
• The remaining items are the arguments
• (+ 3 4) == "Call function named + with arguments 3, 4"
• (* (+ 3 4) (/ 9 3)) == 21

Definitions

• (define x 12) == "assign the value 12 to x"
• (define y (* 7 3)) == "assign the value of (* 7 3) to the variable y"
• Create functions using define and lambda

(define sq (lambda (x)
             (define z (* x x))
             z))

(sq 6) ; => 36

Conditionals

• (if condition true-expr false-expr)
• Evaluate condition; if #t, evaluate and return true-expr, otherwise evaluate and return false-expr
• Ruby equivalent: cond ? true_expr : false_expr

(define abs
  (lambda (x)
    (if (< x 0)
        (- 0 x)
        x)))

Scope and recursion

• Each lambda introduces scope
• Scopes are lexically nested
• Each function can see all its local vars and any vars in enclosing scopes

(define factorial
  (lambda (x)
    (if (= x 0)
        1
        (* (factorial (- x 1))
           x))))

Closures

• Lexical scoping + first-class functions = closures
• Functions can be treated as data
• This add returns a function that remembers the value of x

(define add (lambda (x)
              (lambda (y)
                (+ x y))))

(define add3 (add 3))  ; => #<procedure>

(add3 7)    ; => 10

((add 8) 4) ; => 12

More information

• vimeo.com/jcoglan
• github.com/jcoglan/heist
• github.com/jcoglan/stickup