Scheme Semantics: Introduction | Print Statement | Declaration/Assignment Statements | Let Statement | Lambda Statement | Define Statement | If Statement
Remainder of this Paper: Scheme Introduction | Lexer | Parser | Continuations

Introduction to the Scheme Programming Language


The Scheme computer programming language is a general purpose non-pure functional programming language. Since it is a high level language, it supports operations data such as numbers, characters, strings, lists, and vectors. It is a versatile language, one that is easy to learn but difficult to master. Scheme is a dialect of Lisp, evolving from Lisp and adopting lexical scoping and block structure prior to Common Lisp's adoption of these features. A program in Scheme is a statement list followed by an expression, either of which can be null. For example, 



"hello" (string)

42 (int)

22/7 (real)

3.14159 (real)

+ (operator)

(+ 1 2) (operation)

'(a b c d) (list)
are all examples of expressions in Scheme, and are therefore valid programs. A procedure definition may look like the following. 




(define square

	(lambda (n)

		(* n n)))
Calls to the procedure would be constructed as such: 




(square 5) -> 25

(square -200) -> 40000

(square 0.5) -> 0.25

(square -1/2) -> 1/4
Data values in Scheme, or objects, are dynamically allocated in a heap when they remain until no longer needed, and then automatically deallocated, that is, Scheme has automatic garbage collection. Objects are retained indefinitely, and they objects may be passed freely to and from procedures as arguments and return values. This is in contrast to most languages in which data values are allocated and deallocated based completely where the in the code the execution is, or they are explicitly allocated and deallocated by the programmer.

Scheme keywords and variables are lexically scoped, that is, the values associated with variables are determined before program evaluation by an interpreter because of Scheme's block structure. This is an example of static scoping in programming languages.

Procedures in Scheme can appear anywhere, such as stand alone, or within an enclosing block. To support its lexical scoping, a procedure in Scheme carries with it the lexical context (environment) so as statically bind variable identifiers to their corresponding memory locations and values.

Scheme supports recursion, in which a procedure can directly or indirectly invoke itself. This approach is exceptionally useful to create loops or iterations, a very elegant and efficient approach to program development.

The remainder of this paper is divided into five sections:

Scheme Lexer (Scanner) with explanation
Scheme Yacc Parser with explanation
Scheme Semantic Structure with explanation
Special Feature: Continuations and their use in Scheme
An Example of a Scheme program