Scheme

Dialect of programming language Lisp

Scheme is one of the two most popular Lisp dialects. It follows minimalist philosophy, so it provides a small core language and a powerful toolkit for expanding the language.

Scheme was developed by Guy L. Steele and Gerald Jay Sussman in 1975 and presented to the programming community in a series of articles, so called Lambda Papers, during the next five years. Scheme is standardized in IEEE Standard for the Scheme Programming Language (1995), and in a series of de facto standards called the Revised n Report on the Algorithmic Language Scheme (RnRS):

  • Scheme, 1975 : Sussman, Steele
  • R1RS, 1978 : Steele, Sussman
  • R2RS, 1985: Clinger
  • R3RS, 1986: Clinger, Rees
  • R4RS, 1991: Clinger, Rees
  • R5RS, 1998: Kelsey et al.
  • R6RS, 2007: Sperber et al.
  • R7RS, 201x: in 2009 Scheme Steering Committee which supervises the standardization process announced the intention to break the dialect in two parts, Small and Large. Small will follow minimalistic traditions, while Large will be a modern evolved language while staying a proper superset of Small.

Main Scheme features (differences from other Lisp dialects):

  • minimalism based on lambda-calculus: it is used to derive a huge part of language syntax (11 constructs of 23) from other, simpler ones.
  • static lexical scope: variable name refers to the most local context possible.
  • blocks are implemented with three constructs: let, let* and letrec.
  • “proper” tail recursion allows to write loops in idiomatic recursive form, and optimizes them so that unlimited quantity of tail calls can be supported.
  • continuations (abstract representations of program state) are first-class objects (procedure call-with-current-continuation).
  • procedures and variables have a common namespace.

Scheme logo
Scheme logo

Links:

Examples:

Fibonacci numbers:

Example for versions JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

This example uses recursive definition of Fibonacci numbers. 

(define (fibonacci x)
  (if (< x 2)
    x
    (+ (fibonacci (- x 1)) (fibonacci (- x 2)))))

(do ((i 1 (+ i 1)))
  ((> i 16))
    (display (string-append (number->string (fibonacci i)) ", ")))
(display "...")
(newline)

Factorial:

Example for versions JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

This example uses tail-recursive factorial calculation. Note that GNU Guile and MIT/GNU Scheme print correct result, while JScheme has values of factorial starting with 13! wrong due to overflow. 

(define (factorial x)
  (if (< x 2)
    1
    (* x (factorial (- x 1)))))

(do ((i 0 (+ i 1)))
  ((> i 16))
    (display (string-append (number->string i) "! = "))
    (display (number->string (factorial i)))
    (newline))

Hello, World!:

Example for versions JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

Printing a message is a side effect of this command. Depending on the chosen implementation, the command will return either the message printed, or Unspecified return value. 

(write "Hello, World!")

Quadratic equation:

Example for versions guile 1.8.5

begin is used to execute several commands in row. 

(define A (read))
(define B (read))
(define C (read))
(define D (- (* B B) (* 4 A C)))
(if (= A 0)
  (display "Not a quadratic equation.")
  (begin
   (define k1 (/ B -2 A))
   (define k2 (/ (sqrt (abs D)) 2 A))
   (if (= D 0)
    (begin (display "x = ") (display k1))
    (if (> D 0)
      (begin (display "x1 = ") (display (+ k1 k2)) (newline) (display "x2 = ") (display (- k1 k2)))
      (begin (display "x1 = (") (display k1) (display ", ") (display k2) (display ")") (newline)
             (display "x2 = (") (display k1) (display ", ") (display (- k2)) (display ")"))))))

CamelCase:

Example for versions guile 1.8.5

This program shows how to use regular expressions from regex module. First two commands load the necessary modules. The third one reads a line from input stream using read-line command (rdelim module) — unlike plain read, it consumes characters till the end of line, not till the first whitespace — and converts it to lowercase.

The fourth command finds all matches for a regexp which describes a sequence of lowercase letters. Then it replaces each match with a return of a certain function applied to it (bound using lambda). In this case the function is string-titlecase which converts the first character of the string to uppercase.

Finally, the fifth command removes all non-letter characters from the string. 

(use-modules (ice-9 regex))
(use-modules (ice-9 rdelim))
(define text (string-downcase (read-line)))
(define text (regexp-substitute/global #f "[a-z]+"  text 'pre (lambda (m) (string-titlecase (match:substring m))) 'post))
(define text (regexp-substitute/global #f "[^a-zA-Z]+"  text 'pre 'post))
(display text)