Introduction

Welcome to SLP-SCHEME, the Scheme Language Processor for Emulator.ca Systems.

In the late 1970s, at the MIT Artificial Intelligence Laboratory, Guy Steele and Gerald Sussman created something remarkable. While other language designers were adding features, they were asking a different question: What is the smallest set of ideas that can express any computation? Their answer was Scheme - a language so elegant that its entire specification fits in under fifty pages.

Until now, exploring Scheme meant gaining access to expensive university minicomputers or finding a department willing to share terminal time. The ideas that excited researchers at MIT, Stanford, and Carnegie Mellon remained locked behind institutional walls.

Your home computer has just become a gateway to that world.

SLP-SCHEME brings genuine Scheme to your EC-TTY terminal at 300 baud. This interpreter provides lexical scoping, first-class procedures, and core Scheme forms. The same concepts that power artificial intelligence research and advanced computer science education are now available through a local phone call.

What makes Scheme distinctive is its commitment to simplicity. Where other languages accumulate features and exceptions, Scheme distills programming to its essence. Functions are values that can be stored, passed, and returned like any other data. Recursion replaces iteration as the primary means of repetition. A handful of primitive operations combine to express any computable idea. Once you understand these principles, you understand the foundations of computation itself.

Whether you are learning to think recursively, preparing for university computer science courses, exploring artificial intelligence concepts, or simply enjoying the aesthetic pleasure of well-crafted code, SLP-SCHEME welcomes you to the elegance of functional programming.

This implementation provides:

• Expression-oriented evaluation with a live REPL
• Lexical scoping with first-class procedures
• Numbers, booleans, characters, strings, symbols, pairs, lists, and vectors
• Core special forms: quote, if, cond, case, and, or, begin, lambda, define, set!, let (including named let), let*, letrec, do
• Proper tail recursion via a trampoline-based evaluator (R5RS-style)
• Immutable cons cells with list-processing primitives

Quick Start

Connect to SLP-SCHEME by dialing 555-0320. Once connected, try these expressions to get started:

scheme> (+ 2 3)
5
scheme> (* 6 7)
42
scheme> (define radius 5)
radius
scheme> (* 3 radius radius)
75

Now define a simple function and use it:

scheme> (define (square x) (* x x))
square
scheme> (square 5)
25
scheme> (square (square 3))
81

Create and manipulate a list:

scheme> (define nums (list 1 2 3 4 5))
nums
scheme> (car nums)
1
scheme> (cdr nums)
(2 3 4 5)

You are now ready to explore. The sections below explain each concept in detail.

Getting Connected

To access the SLP-SCHEME interpreter, configure your modem for dial-out and issue the following command:

ATDT555-0320

Upon successful connection, you will see the SLP-SCHEME banner and the scheme> prompt:

ATDT555-0320
CONNECT 1200

R5RS Scheme Subset

Type expressions to evaluate.

scheme> _

The REPL

The Read-Eval-Print Loop evaluates each complete expression and prints the result. Definitions persist for the duration of your session.

scheme> (+ 2 2)
4
scheme> (define radius 10)
radius
scheme> (* 3 radius radius)
300
scheme> (define (area r)
         (* 3 r r))
area
scheme> (area 7)
147

Editing and Interrupts

Use your terminal's backspace for inline editing.

Core Forms

SLP-SCHEME supports the following core special forms:

Data Types

Literal Types

Booleans

The values #t (true) and #f (false) represent logical truth. In conditional expressions, only #f is considered false - all other values, including 0 and the empty list, are true.

scheme> (if #t 1 0)
1
scheme> (if 0 100 200)
100

Numbers

SLP-SCHEME supports exact integers with standard arithmetic:

scheme> (+ 10 20 30)
60
scheme> (- 100 25)
75
scheme> (* 3 4 5)
60
scheme> (/ 100 4)
25

Comparison operators return booleans:

scheme> (< 5 10)
#t
scheme> (= 7 7)
#t
scheme> (>= 3 5)
#f

Lists and Pairs

Pairs and lists are the heart of Scheme - and indeed, of all Lisp-family languages. The idea is deceptively simple: a pair holds exactly two values, accessed with car (the first element) and cdr (the second). These strange names come from the IBM 704 computer where Lisp was born: "Contents of Address Register" and "Contents of Decrement Register." The names stuck.

Lists are just chains of pairs, where each pair's second element points to the next pair, ending with the empty list (). This simple structure can represent any data: lists of numbers, lists of symbols, lists of lists - even the Scheme programs themselves are lists! This property, called homoiconicity, enables powerful metaprogramming techniques.

Building Lists

scheme> (cons 1 2)
(1 . 2)
scheme> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)
scheme> (list 1 2 3 4)
(1 2 3 4)

Accessing Elements

scheme> (define nums (list 10 20 30 40))
nums
scheme> (car nums)
10
scheme> (cdr nums)
(20 30 40)
scheme> (car (cdr nums))
20
scheme> (car (cdr (cdr nums)))
30

List Predicates

scheme> (null? '())
#t
scheme> (null? (list 1))
#f
scheme> (pair? (cons 1 2))
#t

Procedures and Lambda

Here is where Scheme reveals its true power. Procedures are created with lambda and are first-class values - they can be stored in variables, passed as arguments, and returned from other procedures, just like numbers or lists.

This might seem like a technical distinction, but it changes everything. In BASIC, you can pass a number to a subroutine. In Scheme, you can pass a procedure to another procedure. Your programs can write programs. Functions can manufacture other functions. This is the key to Scheme's expressiveness - and the foundation of techniques used in artificial intelligence research.

Defining Procedures

The long form uses lambda explicitly:

scheme> (define square (lambda (x) (* x x)))
square
scheme> (square 9)
81

The short form is syntactic sugar:

scheme> (define (cube x) (* x x x))
cube
scheme> (cube 4)
64

Procedures as Values

Procedures can be passed to other procedures:

scheme> (define (apply-twice f x) (f (f x)))
apply-twice
scheme> (apply-twice square 2)
16
scheme> (apply-twice cube 2)
512

Understanding Recursion

If you come from BASIC or FORTRAN, you are accustomed to loops: FOR, WHILE, REPEAT. Scheme has none of these. Instead, it has something more fundamental: recursion.

A recursive procedure calls itself with modified arguments until reaching a base case. This might sound like a limitation, but it is actually a liberation. Recursion is more powerful than iteration - any loop can be written as recursion, but not all recursion can be easily expressed as a loop. And once you learn to think recursively, you will find it is often the most natural way to express a solution.

Simple Recursion

Consider computing the factorial of n (n! = n * (n-1) * ... * 1):

scheme> (define (factorial n)
         (if (<= n 1)
             1
             (* n (factorial (- n 1)))))
factorial
scheme> (factorial 5)
120
scheme> (factorial 10)
3628800

This works as follows:

• (factorial 5) computes 5 * (factorial 4)
• (factorial 4) computes 4 * (factorial 3)
• ...and so on until...
• (factorial 1) returns 1 (base case)
• The multiplications complete: 1 * 2 * 3 * 4 * 5 = 120

List Recursion

Processing a list recursively follows a pattern: handle the empty list (base case), otherwise process the first element and recurse on the rest.

scheme> (define (list-length lst)
         (if (null? lst)
             0
             (+ 1 (list-length (cdr lst)))))
list-length
scheme> (list-length (list 1 2 3 4 5))
5

Sum all elements of a list:

scheme> (define (sum-list lst)
         (if (null? lst)
             0
             (+ (car lst) (sum-list (cdr lst)))))
sum-list
scheme> (sum-list (list 10 20 30))
60

Recursion Patterns

SLP-SCHEME implements proper tail-call optimization (R5RS-style) via a trampoline evaluator. Tail calls — including in if, cond, case, begin, and/or, lambda bodies, and named let — iterate without growing the host stack, so deep tail recursion is safe.

Non-tail recursion (calls that wrap their result in another expression, e.g. (+ 1 (f (- n 1)))) still consumes stack space and is bounded by max_recursion_depth (default 1000). Prefer the accumulator pattern for unbounded loops:

;; Accumulator pattern - this loop is iterative under proper tail calls
(define (sum-to n acc)
  (if (= n 0)
      acc
      (sum-to (- n 1) (+ acc n))))

scheme> (define (sum n acc)
         (if (= n 0)
             acc
             (sum (- n 1) (+ acc n))))
sum
scheme> (sum 50 0)
1275
scheme> (sum 100000 0)        ; deep tail recursion is safe
5000050000

The accumulator acc carries the running total. Because the recursive call is in tail position, the trampoline reuses the call frame instead of growing the stack.

Conditionals

The if Form

(if test consequent alternative) evaluates the test. If true, the consequent is evaluated; otherwise, the alternative.

scheme> (if (> 5 3) 1 0)
1
scheme> (define (abs x) (if (< x 0) (- 0 x) x))
abs
scheme> (abs -7)
7

Multi-way Conditionals

cond evaluates a sequence of test/expression clauses, returning the value of the first matching clause. Use else for the default branch:

scheme> (define (sign x)
         (cond ((< x 0) -1)
               ((> x 0) 1)
               (else 0)))
sign
scheme> (sign -5)
-1
scheme> (sign 10)
1
scheme> (sign 0)
0

case dispatches on a key value against literal datum lists:

scheme> (define (day-type d)
         (case d
           ((mon tue wed thu fri) 'weekday)
           ((sat sun) 'weekend)
           (else 'unknown)))
day-type
scheme> (day-type 'wed)
weekday

Logical Operations

and returns the last value if all expressions are truthy, or #f on the first false. or returns the first truthy value, or #f if all are false. Both short-circuit and place their last expression in tail position:

scheme> (and 1 2 3)
3
scheme> (and 1 #f 3)
#f
scheme> (or #f #f 42)
42
scheme> (or #f #f #f)
#f

Local Bindings

let

let introduces local variables that exist only within its body. All bindings are evaluated in the outer environment before any are bound:

scheme> (let ((x 10)
              (y 20))
         (+ x y))
30
scheme> (let ((a 3)
              (b 4))
         (+ (* a a) (* b b)))
25

let*, letrec, and named let

let* binds sequentially: each binding can reference earlier ones in the same form.

scheme> (let* ((x 5)
               (y (* x 2))
               (z (+ x y)))
         z)
15

letrec allows the binding expressions to refer to each other (and to themselves), which is how mutually recursive local procedures are written.

scheme> (letrec ((even? (lambda (n) (if (= n 0) #t (odd?  (- n 1)))))
                 (odd?  (lambda (n) (if (= n 0) #f (even? (- n 1))))))
          (even? 1000))
#t

Named let is sugar for a letrec plus an immediate call — the canonical way to write a tight loop:

scheme> (let loop ((n 100000) (acc 0))
         (if (= n 0)
             acc
             (loop (- n 1) (+ acc n))))
5000050000

For mutually recursive functions, define them at the top level with define.

I/O Procedures

SLP-SCHEME provides basic output procedures:

scheme> (display 42)
42
scheme> (newline)

scheme> (define (println x) (display x) (newline))
println
scheme> (println 100)
100
scheme> (println (list 1 2 3))
(1 2 3)

To disconnect from the service, use the standard modem hangup sequence (ATH) or close your terminal connection.

Interactive REPL

Experiment with Scheme directly in this manual using the interactive REPL:

(+ 2 3)

Practical Examples

Fibonacci Numbers

scheme> (define (fib n)
         (if (< n 2)
             n
             (+ (fib (- n 1)) (fib (- n 2)))))
fib
scheme> (fib 10)
55
scheme> (fib 15)
610

Reversing a List

scheme> (define (reverse-list lst)
         (define (rev-helper lst acc)
           (if (null? lst)
               acc
               (rev-helper (cdr lst) (cons (car lst) acc))))
         (rev-helper lst '()))
reverse-list
scheme> (reverse-list (list 1 2 3 4 5))
(5 4 3 2 1)

Map (Apply Function to Each Element)

scheme> (define (map f lst)
         (if (null? lst)
             '()
             (cons (f (car lst)) (map f (cdr lst)))))
map
scheme> (map square (list 1 2 3 4 5))
(1 4 9 16 25)

Appendix A: Quick Reference Card

╔══════════════════════════════════════════════════════════════════════════╗
║  SLP-SCHEME v0.7 - QUICK REFERENCE                   Emulator.ca Systems ║
╠══════════════════════════════════════════════════════════════════════════╣
║                                                                          ║
║  ARITHMETIC:      (+ a b ...)        (- a b)         (* a b ...)         ║
║                   (/ a b)            (= a b)         (< a b)  (> a b)    ║
║                   (<= a b)           (>= a b)                            ║
║                                                                          ║
║  LISTS:           (cons a b)         Build a pair                        ║
║                   (car lst)          First element                       ║
║                   (cdr lst)          Rest of list                        ║
║                   (list a b ...)     Build a list                        ║
║                   (null? lst)        Test for empty                      ║
║                   (pair? x)          Test for pair                       ║
║                                                                          ║
║  PREDICATES:      (number? x)        (boolean? x)    (symbol? x)         ║
║                   (eq? a b)          Identity test                       ║
║                                                                          ║
║  DEFINE:          (define name value)                                    ║
║                   (define (name args) body)                              ║
║                                                                          ║
║  LAMBDA:          (lambda (args) body)                                   ║
║                                                                          ║
║  SPECIAL FORMS:   (quote expr) / 'expr    Prevent evaluation             ║
║                   (if test then else)     Conditional                    ║
║                   (cond (test expr...) ... (else expr...))               ║
║                   (case key (datums expr) ... (else expr))               ║
║                   (and expr ...)          Short-circuit AND              ║
║                   (or  expr ...)          Short-circuit OR               ║
║                   (begin expr ...)        Sequence expressions           ║
║                   (set! var value)        Mutate binding                 ║
║                   (let     ((v e)...) body)   Parallel bindings          ║
║                   (let*    ((v e)...) body)   Sequential bindings        ║
║                   (letrec  ((v e)...) body)   Recursive bindings         ║
║                   (let name ((v e)...) body)  Named let / loop           ║
║                   (do      ((v i s)...) (test) body)                     ║
║                                                                          ║
║  OUTPUT:          (display expr)     (newline)                           ║
║                                                                          ║
║  STRINGS / CHARS: "literal"  #\a  (string-length s)  (string-ref s i)    ║
║                                                                          ║
║  TAIL CALLS:      Properly optimized; deep tail recursion is safe.       ║
║                                                                          ║
║  DIAL: ATDT555-0320                                                      ║
╚══════════════════════════════════════════════════════════════════════════╝

Appendix B: Troubleshooting

Problem: "Unexpected end of input" Your parentheses are unbalanced. Count opening and closing parentheses - they must match. The REPL will wait for more input if a closing paren is missing.

Problem: "Unbound variable" You referenced a name that has not been defined. Check spelling and ensure the define was evaluated in the current session.

Problem: Recursion causes disconnect Tail recursion is properly optimized, so loops written in tail-call style (e.g. accumulator pattern, named let) are safe at any depth. Non-tail recursion — calls whose result is consumed by another expression, like (+ 1 (f (- n 1))) — still consumes one host stack frame per level and is capped at max_recursion_depth (default 1000). Rewrite such functions with an accumulator if you need to go deeper.

Problem: "Invalid syntax" Special forms have specific syntax requirements. define requires a name and value. if requires exactly three parts (test, consequent, alternative). lambda requires a parameter list.

Problem: Output appears on same line Use (newline) after (display ...) to move to the next line. Display does not automatically add line breaks.

Appendix C: Glossary

Accumulator - A parameter that carries a running result through recursive calls, enabling tail recursion.

Base case - The condition that terminates recursion. Without a base case, recursion continues forever.

Car - The first element of a pair. Named after "Contents of Address Register" from the IBM 704.

Cdr - The second element of a pair. Named after "Contents of Decrement Register" from the IBM 704.

Cons - Construct a pair from two values. The fundamental building block of lists.

Lambda - The form that creates a procedure. Named after lambda calculus.

REPL - Read-Eval-Print Loop. The interactive mode where you enter expressions and see results.

R5RS - Revised^5 Report on the Algorithmic Language Scheme (1998). The standard that SLP-SCHEME draws from (implementing a subset, with proper tail recursion).

Tail recursion - A recursive call that is the last operation in a procedure. SLP-SCHEME implements proper tail-call optimization via a trampoline evaluator, so tail-recursive loops run in constant stack space.

Further Exploration

You have learned the fundamentals of Scheme - expressions, procedures, recursion, and list processing. These concepts form the foundation of functional programming, but there is much more to explore.

Recommended Next Steps

Practice Recursion: The best way to internalize recursive thinking is to solve problems. Try writing procedures to:

• Find the maximum element in a list
• Remove duplicate elements from a list
• Flatten a nested list structure
• Compute the nth prime number

Read the Classics: The concepts in SLP-SCHEME are drawn from Structure and Interpretation of Computer Programs by Abelson and Sussman, used in MIT's introductory computer science course. If you can find a copy, it will transform how you think about programming.

Explore Higher-Order Functions: You have seen map. Try implementing filter (select elements matching a predicate) and reduce (combine list elements into a single value). These three operations are surprisingly powerful when combined.

Build Something: A small project cements understanding better than any tutorial. Consider:

• A simple calculator that parses arithmetic expressions
• A procedure that plays a guessing game
• Functions to manipulate sets represented as lists

Related Services

• SLP-BASIC (555-0300) - The BASIC interpreter for Emulator.ca Systems
• SLP-FORTH (555-0400) - Explore stack-based programming
• SLP-PROLOG (555-0730) - Logic programming and AI concepts

Scheme rewards persistence. The concepts that seem foreign at first will become second nature with practice. Soon you will find yourself thinking in recursion, seeing lists everywhere, and appreciating the beauty of a language that trusts the programmer with simple, powerful tools.

"Programs must be written for people to read, and only incidentally for machines to execute." — Abelson and Sussman

SLP-SCHEME v0.7 - Emulator.ca Systems

Document Revision 0.7