An Etude in Minimalism

2018-November-16

Scheme is a masterpiece of minimalism in programming language design. Despite being a simple language, it has amazing expressive power. Its most widely implemented standard is only 50 pages long and can be read over a weekend. This post is an attempt to find out the secret to Scheme's minimal but effective design. It is hoped that the insights gained should be applicable to system design problems in general.

Lambda the Powerful!

First-class functions are the primary means of abstraction in Scheme. A function can be passed as an argument to other functions, can be created at will and can be stored in data structures. A function can also make unbounded number of iterative calls to itself or to other functions. This is possible because Scheme implementations are required to optimize tail calls. This enable programmers to use tail recursion for expressing iteration.


;; Sum the elements in a list, utilizing tail recursion.

(define (sum-list xs sum)
  (if (null? xs)
    sum
    (sum-list (cdr xs) (+ (car xs) sum))))

(sum-list '(1 2 3 4 5) 0)
;;=> 15
      

We can redefine sum-list as a general "list reducer". The operation used to combine the elements of the list together into a single value can be passed as a functional argument:


(define (reduce xs init opr)
  (if (null? xs)
  init
  (reduce (cdr xs) (opr (car xs) init) opr)))

;; Same as sum-list
(reduce '(1 2 3 4 5) 0 +)
;;=> 15

(reduce '(1 2 3 4 5) 1 *)
;;=> 120

(define (square x) (* x x))

(reduce '(1 2 3 4 5) 1 (lambda (x y) (+ (square x) (square y))))
;;=> 28569050
      

Tail call optimization makes it unnecessary to bake-in looping constructs like for and while into the core of the language.

Lexical Scope

Scheme was one of the earliest languages to support lexical scoping of variables. This means, all variable bind to the values given to them in the context they were defined. These bindings do not change even when the expressions are evaluated in other parts of the program.

The following program demonstrates the possibilities offered by lexical scoping. It defines a function that returns another function. The returned function can refer to the variable bindings in its defining context, even when it is invoked from other contexts.


(define (make-adder base)
  (lambda (x) (+ base x)))

(define a5 (make-adder 5))
(define a10 (make-adder 10))
(a5 20)
;;=> 25
(a10 20)
;;=> 30
      

The combination of first-class functions and lexical scoping allows Scheme to express object-based programs. No special syntax or language construct is required to use this powerful paradigm.


(define (make-cat)
  (lambda (message)
    (case message
      ((say-hello) 'meow))))

(define (make-dog)
  (lambda (message)
    (case message
      ((say-hello) 'bow-wow))))

(define c (make-cat))
(c 'say-hello)
;;=> meow
(define d (make-dog))
(d 'say-hello)
;;=> bow-wow
      
(Read more about functional abstractions).

Syntactic Abstractions

It is quite impressive that a combination of a few simple concepts is enough to program in multiple paradigms. But sometimes the programs written might need a more natural syntax. For instance, programs will become shorter and easier to maintain if there is syntactic support for defining classes of objects. Instead of building in syntax for all possible paradigms, Scheme (like other Lisps) allow users to extend the language syntax by a macro system. Scheme's macro system is even more powerful because the code generated by a macro is guaranteed to be hygienic. The Scheme macro system respects the lexical scoping of the rest of the language. This is assured by special naming and scoping rules for macro expansion and avoids common programming errors that can occur in the macro systems of other programming languages. The macro system is also very expressive because it makes use of a simple pattern matching sub-language.

Let us extend Scheme to support a language for defining new classes of objects. This extension will add a new construct to the language called define-class. It takes the class name and a list of messages and message handlers as arguments. The Scheme macro expander will transform a define-class to a function definition that takes a symbolic message as argument and execute the appropriate message implementation.


(define-syntax define-class
  (syntax-rules ()
    ((define-class class-name ((message-name message-body) ...))
     (define (class-name)
       (lambda (message)
	 (case message
	   ((message-name) message-body)
	   ...
	   (else (error "invalid message" message))))))))

(define-class cat ((say-hello 'meow)))
(define-class dog ((say-hello 'bow-wow)))

(define c (cat))
(define d (dog))

(c 'say-hello)
;;=> meow
(d 'say-hello)
;;=> bow-wow
      

Exercise 1: Add attribute support for classes defined by define-class. For instance, it should be possible to assign names to the various animal objects, like - (define c (cat 'sassy)). It should also be possible to refer and update the attributes through messages, e,g:

(c 'name) ;;=> sassy
(c 'set-name 'Kitty)
(c 'name) ;;=> Kitty

Let us conclude this section with one more example. We will define a macro that will behave like the while loop found in most imperative languages. Notice how the macro compiles the loop to a tail-recursive function.


(define-syntax while
  (syntax-rules ()
    ((while condition body ...)
     (begin
       (define (loop)
	 (if condition
	     (begin
                body ...
	       (loop))))
        (loop)))))

;; Usage:
(define i 0)
(while (< i 5)
  (display "hello\n")
  (set! i (+ i 1)))
;;-> hello
     hello
     hello
     hello
     hello
      
(Read more about building syntactic abstractions in Lisp).

Control-flow Abstractions

The previous sections showed how a pragmatic language can be designed on top of only a couple of simple building blocks. First-class functions and macros can be combined together in intuitive ways to extend and adapt the language to suit almost any problem domain. But Scheme does not stop there! It also allows the programmer to get access to the control state of the program and add extensions to the language that control the way the program execution flows. It is possible to capture the current state of control flow as a function. If this function is called from another part of the program, control will go back to the point where it was captured and the program will continue executing from there.

The presence of first-class continuations means Scheme do not need built-in support for features like exceptions and coroutines. These can be added to the language as libraries.

We will conclude this post with two examples of using continuations. The first one shows the implementation of a simple coroutine mechanism.


(define continue #f)

(define (f)
  (display "f: hello\n")
  (call/cc
   (lambda (k)
     (set! continue k)
     (g)))
  (display "bye bye!\n"))

(define (g)
  (display "g: hello\n")
  (continue))

(f)
;;-> f: hello
;;-> g: hello
;;-> bye bye!
      

The continuation captured in the function f allows the function g to restart f from where it left off. This code can become the basis for a more feature-full multitasking library.

Exercise 2: Read about the Actor model of computation and write an implementation for Scheme. Look at Erlang for inspiration! You can find some guidance on actual implementation here and here.

The second example combines continuations with functions and macros to implement an exception handling mechanism. Basically, the error handlers are continuations which are made to replace the current state of program execution when an exception is raised.


(define handlers '())

(define (top-handler)
  (car handlers))

(define (pop-handlers!)
  (if (not (null? handlers))
      (set! handlers (cdr handlers))))

(define no-handlers? null?)

(define (exception msg)
  (if (no-handlers? handlers)
      (error msg)
      (let ((handler (top-handler)))
	(handler (cons 'error msg)))))

(define (prepare-handler handler)
  (pop-handlers!)
  (lambda (obj)
    (if (and (pair? obj) (eq? 'error (car obj)))
	(handler obj)
	obj)))

(define-syntax with-handler
  (syntax-rules ()
    ((with-handler handler body ...)
     ((prepare-handler handler)
      (call/cc
       (lambda (k)
	 (set! handlers (cons k handlers))
	 body
	 ...))))))


;; Example usage:
(define (f x y)
  (if (= y 0)
    (exception "cannot divide by zero")
    (/ x y)))

(with-handler
   (lambda (ex)
     (format #t "~A\n" ex))
   (display (f 10 20))
   (display " -- done!\n"))
;;-> 1/2 -- done!

(with-handler
   (lambda (ex)
     (format #t "~A\n" ex))
   (display (f 10 0))
   (display " -- done!\n"))
;;-> (error . cannot divide by zero)

Conclusion

Scheme is the Lego of the programming world. Strict, first-class functions with lexically scoped variable bindings are the primary building material here. We combine and compose them in various patterns to build abstractions of immense power. These abstractions can be constructed fast because the semantics of function definition and application is simple to understand and easy to reason about. These abstractions will normally have good performance because most Scheme implementations take special care to optimize function calls. Add hygienic macros and continuations to the toolbox and we have unlimited power at our disposal. Scheme allows us to build the right abstractions at the right level and write code in a language tailor-made for the problem at hand. Indeed Scheme is a triumph of minimalism in language design and engineering!