Beginner's Guide to Scheme

Introduction to Scheme #

What is Scheme? #

Scheme is a dialect of the Lisp family of programming languages. It’s known for its elegant simplicity and powerful expressiveness, achieved through a minimalist core syntax and a focus on functional programming paradigms. Scheme’s core features include a simple but consistent syntax based on s-expressions (symbolic expressions), first-class functions (functions treated as data), and lexical scoping (variable visibility determined by their position in the code). This simplicity makes it an ideal language for learning fundamental programming concepts and for exploring advanced topics like metaprogramming and language design.

Why learn Scheme? #

Learning Scheme offers several benefits for developers:

• Enhanced understanding of programming fundamentals: Scheme’s minimalist design forces you to confront core programming concepts directly, leading to a deeper understanding of how programming languages work.
• Improved functional programming skills: Scheme encourages a functional programming style, which can lead to more concise, robust, and maintainable code. This style translates well to other languages.
• Increased problem-solving abilities: Scheme’s expressive power and ability to easily manipulate code as data facilitate creative and efficient solutions to complex problems.
• Foundation for further language learning: The experience of learning Scheme can significantly ease the learning curve for other languages, especially those in the Lisp family or languages with functional features.
• Appreciation of language design: Scheme’s elegance and simplicity provide insights into the principles of language design and implementation.

Setting up your environment #

To begin programming in Scheme, you need to install a Scheme implementation. The process generally involves downloading an installer or pre-built binary for your operating system (Windows, macOS, Linux) from the chosen implementation’s website. Installation usually involves extracting files and potentially adding the implementation’s binary directory to your system’s PATH environment variable so that you can access the Scheme interpreter from your terminal or command prompt.

Choosing an implementation (MIT-Scheme, Guile, etc.) #

Several excellent Scheme implementations are available. Some popular choices include:

• MIT-Scheme: A mature and widely used implementation, known for its stability and extensive documentation.
• Guile: An extensible Scheme implementation often embedded in other applications. It’s known for its powerful extension mechanisms and integration capabilities.
• Racket: A modern Scheme implementation with a focus on extensibility and a rich ecosystem of packages. It’s particularly well-suited for educational purposes and building large applications.
• Chez Scheme: A high-performance Scheme implementation often used for computationally intensive tasks.

The best implementation for you depends on your needs and preferences. For beginners, MIT-Scheme or Racket are often recommended due to their extensive documentation and supportive communities.

REPL: Read-Eval-Print Loop #

The REPL (Read-Eval-Print Loop) is the primary way you’ll interact with a Scheme interpreter. The REPL follows a simple cycle:

1. Read: The REPL reads your input, typically a Scheme expression.
2. Eval: The interpreter evaluates the expression, computing its value.
3. Print: The interpreter prints the result of the evaluation.
4. Loop: The REPL repeats this cycle, allowing for interactive experimentation and program development.

This interactive nature of the REPL makes it an invaluable tool for learning and debugging Scheme code. You can test small snippets of code, observe their behavior, and iteratively refine your programs. Most Scheme implementations provide a REPL interface either directly through a terminal window or through a graphical development environment.

Basic Syntax and Data Types #

S-expressions #

Scheme’s syntax is based on s-expressions (symbolic expressions). An s-expression is either an atom or a list. Atoms are indivisible data elements such as numbers, symbols, booleans, characters, and strings. Lists are sequences of s-expressions enclosed in parentheses (). The simplest list is the empty list, denoted by (). A non-empty list is written as (element1 element2 element3 ...) where each element is itself an s-expression. This uniform syntax for both data and code is a defining characteristic of Lisp and Scheme. For example, (+ 1 2) is an s-expression representing the addition of 1 and 2; here + is a symbol representing the addition function, and 1 and 2 are numbers.

Numbers #

Scheme supports various numeric types, including integers (1, -5, 0), floating-point numbers (3.14, -2.5), and sometimes others depending on the implementation. Numeric operations are performed using standard infix notation (e.g., +, -, *, /) but are represented as s-expressions where the operator is the first element. For example (+ 1 2) adds 1 and 2.

Booleans #

Scheme uses the symbols #t (true) and #f (false) to represent boolean values. Many Scheme procedures return #t or #f to indicate success or failure, or to represent truth values in conditional expressions.

Symbols #

Symbols are names used to represent variables, function names, and other identifiers. They consist of one or more characters, typically starting with a letter or other non-numeric character. For example, my-variable, counter, and function-name are all valid symbols. Symbols are case-sensitive.

Characters #

Characters are single characters enclosed in #\ characters. For instance, #\A, #\space, #\newline represent the uppercase letter A, a space character, and a newline character, respectively.

Strings #

Strings are sequences of characters enclosed in double quotes ". For example, "Hello, world!" is a string. Scheme provides procedures for manipulating strings, such as concatenating strings or extracting substrings.

Lists #

Lists are fundamental data structures in Scheme. They are ordered sequences of s-expressions. The empty list is (), and non-empty lists are constructed using parentheses. The cons procedure adds an element to the beginning of a list; car and cdr access the first element and the rest of the list, respectively. For example, (cons 1 '(2 3)) creates the list (1 2 3).

Pairs #

A pair is a fundamental building block of lists. It consists of two s-expressions, a car (for “contents of the address register”) and a cdr (for “contents of the decrement register”). Lists are implemented as linked lists of pairs, where the car of each pair holds an element of the list, and the cdr points to the next pair or the empty list.

Vectors #

Vectors are another type of sequence, similar to lists but with efficient random access to elements. They are created using the vector procedure. Vector elements are accessed using the vector-ref procedure and modified using the vector-set! procedure (note the ! indicating a side-effecting procedure). Vectors can contain any Scheme data type.

Fundamental Operations #

Arithmetic operations (+, -, *, /) #

Scheme provides standard arithmetic operations: +, -, *, and /. These are functions, not operators in the typical infix sense. They take one or more numeric arguments as s-expressions and return the result. For example:

(+ 1 2 3)     ; Returns 6
(- 10 5)      ; Returns 5
(* 2 4)       ; Returns 8
(/ 10 2)      ; Returns 5

Note that division (/) always returns a floating-point number, even if the operands are integers.

Comparison operations (=, <, >, <=, >=) #

Scheme provides functions for comparing numbers: =, <, >, <=, >=. These functions take two or more numeric arguments and return #t (true) if the comparison holds for all arguments, and #f (false) otherwise.

(= 1 1)       ; Returns #t
(< 2 3)       ; Returns #t
(> 5 1)       ; Returns #t
(<= 2 2)      ; Returns #t
(>= 10 10)    ; Returns #t
(= 1 2 3)     ; Returns #f (1 is not equal to 2 and 3)

Logical operations (and, or, not) #

Scheme offers standard logical operations: and, or, and not. and returns #t if all arguments are true, otherwise it returns #f. or returns #t if at least one argument is true, otherwise #f. not takes a single boolean argument and returns its negation.

(and #t #t)    ; Returns #t
(and #t #f)    ; Returns #f
(or #t #f)     ; Returns #t
(or #f #f)     ; Returns #f
(not #t)       ; Returns #f
(not #f)       ; Returns #t

Defining variables (define) #

The define special form is used to create variables. It takes a symbol (the variable name) and an expression whose value is assigned to the variable.

(define x 10)    ; Defines a variable x with the value 10
(define y (+ x 5)); Defines y as x + 5 (y will be 15)

Conditional statements (if, cond) #

• if: The if special form provides basic conditional execution. It takes three arguments: a test expression, a consequence expression (executed if the test is true), and an alternative expression (executed if the test is false).

(if (> x 5) (+ x 1) (- x 1)) ; If x > 5, add 1 to x; otherwise, subtract 1

• cond: The cond special form offers a more general conditional construct. It takes multiple clauses, each consisting of a test expression and a consequence expression. The first clause whose test evaluates to true is executed. A final else clause can be added to handle cases where no other test is true.

(cond ((> x 10) "x is greater than 10")
      ((= x 10) "x is equal to 10")
      (else "x is less than 10"))

Basic Input/Output #

The exact way to handle input/output depends on the Scheme implementation. Many provide functions such as display (to print to the console without a newline) and newline (to print a newline character). For reading input, functions like read (to read a Scheme expression from the input stream) might be used. More sophisticated I/O operations would typically involve opening and closing files and handling streams. Consult your specific Scheme implementation’s documentation for details on I/O functions. For example, in many implementations:

(display "Hello, world!")  ; Prints "Hello, world!" to the console
(newline)                  ; Moves the cursor to the next line

Functions and Procedures #

Defining functions (lambda, define) #

Scheme uses the terms “function” and “procedure” interchangeably. Functions are defined using either lambda or define.

• lambda: The lambda special form creates an anonymous function. It takes a list of parameters and a body expression.

(lambda (x y) (+ x y)) ; Creates a function that adds two numbers

This creates a function that takes two arguments, x and y, and returns their sum. The function itself is a value that can be passed to other functions or stored in a variable.

• define: The define special form can also be used to define named functions. It takes a function name (symbol), a list of parameters, and a body expression.

(define add (lambda (x y) (+ x y))) ; Defines a named function 'add'
(define (add x y) (+ x y))         ; Equivalent shorter syntax for defining functions

Both definitions create the same function, but the second syntax is more concise and commonly used.

Function application #

Function application is straightforward in Scheme. A function is applied by placing the function name (or expression evaluating to a function) followed by its arguments in parentheses.

(add 1 2)       ; Applies the 'add' function to 1 and 2, returns 3
((lambda (x) (* x x)) 5) ; Applies an anonymous function to 5, returns 25

Scope and lexical closures #

Scheme uses lexical scoping, meaning that the scope of a variable is determined by its position in the code. A variable is accessible within the function (or block of code) where it’s defined, and in any nested functions within that scope. Lexical closures are functions that “remember” their surrounding environment even after the enclosing function has finished executing.

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

(define add5 (make-adder 5)) ; add5 is a closure that remembers x=5
(add5 10)                  ; Returns 15

Here, make-adder returns a function (a closure) that “remembers” the value of x even after make-adder has finished.

Higher-order functions #

Higher-order functions are functions that take other functions as arguments or return functions as results. Scheme supports higher-order functions naturally due to its functional paradigm. Examples include map, filter, and fold (also known as reduce).

(map (lambda (x) (* x 2)) '(1 2 3)) ; Applies *2 to each element of the list, returns '(2 4 6)

Recursion #

Recursion is a powerful technique in Scheme where a function calls itself directly or indirectly. Recursive functions are commonly used to process lists or trees. A recursive function must have a base case (a condition that stops the recursion) and a recursive step (a step that calls itself with a smaller problem).

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

(factorial 5) ; Returns 120

This function calculates the factorial of a number using recursion. The base case is when n is 0, returning 1. The recursive step multiplies n by the factorial of n-1.

Working with Lists #

List manipulation functions (car, cdr, cons, append) #

Scheme provides fundamental functions for manipulating lists:

• car: Returns the first element of a list. (car '(1 2 3)) returns 1.
• cdr: Returns the rest of the list after removing the first element. (cdr '(1 2 3)) returns (2 3). If the list is empty, cdr returns the empty list.
• cons: Adds an element to the beginning of a list. (cons 0 '(1 2 3)) returns (0 1 2 3).
• append: Concatenates two or more lists. (append '(1 2) '(3 4)) returns (1 2 3 4).

Mapping over lists (map) #

The map function applies a given function to each element of a list and returns a new list containing the results.

(map (lambda (x) (* x 2)) '(1 2 3 4)) ; Doubles each element: returns '(2 4 6 8)

This example applies a lambda function (which doubles its input) to each element of the list '(1 2 3 4).

Filtering lists (filter) #

The filter function (often called filter or a similar name; the exact name may vary slightly depending on the Scheme implementation) selects elements from a list that satisfy a given predicate (a function that returns true or false). It returns a new list containing only the selected elements.

(filter even? '(1 2 3 4 5 6)) ; Selects even numbers: returns '(2 4 6)

This example uses the built-in even? predicate to select even numbers from the list.

Folding lists (foldl, foldr) #

Fold functions (also known as reduce functions) combine the elements of a list into a single value using a given accumulating function.

• foldl (left fold): Processes the list from left to right. It takes the accumulating function, an initial value, and the list as arguments.

(foldl + 0 '(1 2 3 4)) ; Sums the elements: returns 10

This example uses + as the accumulating function and 0 as the initial value. The function successively adds each element to the accumulated sum.

• foldr (right fold): Processes the list from right to left. The behavior is generally similar to foldl except for the order of processing. For most associative operations, the results are the same; however, for non-associative operations, the order can matter.

(foldr + 0 '(1 2 3 4)) ; Also sums the elements: returns 10 (same as foldl in this case)

These examples demonstrate basic list operations in Scheme. More complex list manipulations can be built by combining these functions and using recursion. Remember that the specific names of some functions (e.g., filter) might have slight variations depending on the Scheme implementation you are using. Consult your implementation’s documentation for details.

Macros and Advanced Techniques #

Introduction to macros (syntax-rules) #

Macros in Scheme are powerful tools for extending the language’s syntax. They allow you to define new language constructs by manipulating code as data before it’s evaluated. Scheme’s most common macro system is syntax-rules, a pattern-matching system that simplifies macro definition.

A syntax-rules macro is defined using a pattern-matching approach. The macro takes patterns as input and generates code as output. The patterns specify how the input code should be structured, and the output code defines what code should be generated based on those patterns.

(define-syntax-rule (my-macro x y)
  (+ x (* 2 y)))

(my-macro 1 2)  ; Expands to (+ 1 (* 2 2)), evaluates to 5

This macro my-macro takes two arguments (x and y) and expands into an expression that adds x to twice y.

Hygiene and macro expansion #

Hygiene is a crucial aspect of macro systems. It prevents unintended name collisions between variables in the macro definition and variables in the code where the macro is used. Hygienic macros ensure that the variables in the macro’s generated code are distinct from the surrounding code’s variables, preventing accidental variable shadowing or modification.

Macro expansion is the process of transforming the macro call into its equivalent code before evaluation. The Scheme interpreter (or compiler) performs macro expansion before evaluating the code. Understanding macro expansion helps in debugging and analyzing macro behavior. You can often use a Scheme implementation’s tools to inspect the expanded code to see how your macros are being translated.

Creating DSLs with macros #

Macros are particularly useful for creating domain-specific languages (DSLs) within Scheme. A DSL is a language tailored to a particular domain or problem. Macros can be used to build a more concise and expressive syntax for that domain, making the code easier to read and write.

For example, imagine creating a DSL for describing graphical user interfaces. Macros could be defined to simplify creating buttons, labels, and other UI elements. Instead of writing complex code to create a button, you could use a macro with a simpler syntax like:

(define-syntax-rule (button label action)
  (button-widget label (lambda () action)))

This macro simplifies the creation of buttons, encapsulating the details of creating the button widget. This makes the code for creating a GUI more readable and maintainable. The use of macros allows you to abstract away low-level details, creating a higher-level language specifically designed for building GUIs within the Scheme environment.

Example Programs #

Simple calculator #

This example demonstrates a simple calculator that performs addition, subtraction, multiplication, and division. It uses a cond statement to handle different operations.

(define (calculator op x y)
  (cond ((eq? op '+) (+ x y))
        ((eq? op '-) (- x y))
        ((eq? op '*) (* x y))
        ((eq? op '/) (/ x y))
        (else (display "Invalid operation") (newline))))

(calculator '+ 5 3)   ; Output: 8
(calculator '- 10 4)  ; Output: 6
(calculator '* 2 7)   ; Output: 14
(calculator '/ 15 3)  ; Output: 5
(calculator 'mod 10 3) ; Output: Invalid operation

List processing functions #

This example shows several list processing functions: finding the length of a list, summing the elements of a list, and calculating the average of the elements.

(define (list-length lst)
  (if (null? lst)
      0
      (+ 1 (list-length (cdr lst)))))

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

(define (list-average lst)
  (/ (list-sum lst) (list-length lst)))

(define my-list '(1 2 3 4 5))
(display "Length: ") (display (list-length my-list)) (newline) ; Output: Length: 5
(display "Sum: ") (display (list-sum my-list)) (newline)     ; Output: Sum: 15
(display "Average: ") (display (list-average my-list)) (newline); Output: Average: 3

Basic game implementation #

This example implements a simple number guessing game. The computer generates a random number, and the player tries to guess it.

; Requires a random number generator.  The specific function might vary by implementation.
; This example assumes a function (random-number n) exists that returns a random integer between 0 and n-1.

(define (guessing-game)
  (let ((secret-number (random-number 100))) ; Generates a number between 0 and 99
    (display "Welcome to the Number Guessing Game!\n")
    (let loop ((guess -1))
      (display "Guess a number between 0 and 99: ")
      (let ((guess (read)))
        (cond ((= guess secret-number)
               (display "Congratulations! You guessed it.\n"))
              ((< guess secret-number)
               (display "Too low! Try again.\n")
               (loop guess))
              ((> guess secret-number)
               (display "Too high! Try again.\n")
               (loop guess))
              (else (display "Invalid input.\n") (loop guess)))))))

(guessing-game)

Remember to adapt the random-number function to match your specific Scheme implementation’s random number generation capabilities. This game provides a basic framework; you could expand it to include features like limiting the number of guesses or providing hints.