LispMe Semantics

General

Scheme (and thus LispMe) has following general characteristics:

Lexical binding

Each use of a a variable name refers to a lexically enclosing binding of that variable. This means that by inspecting just the source text of a LispMe program you can determine the binding of the variable. This is in contrast to dynamic binding, where free variables in an expression are resolved according to the dynamic call chain and unwanted bindings may occur due to name clashes.

Languages sharing this trait	Languages not sharing this trait
C, Pascal, Common Lisp, SML, Python 2.0	Older Lisps, APL

Call by value

When evaluating a procedure call, all sub-expressions (including the procedure to be called itself) are evaluated before the procedure is entered. This is also called applicative order evaluation, in contrast to normal order evaluation or call by name, where the procedure decides, when and which of its arguments are evaluated. By using explicit delay and force, you can have some characteristics of normal order evaluation.

Languages sharing this trait	Languages not sharing this trait
C, Pascal, Common Lisp, SML, Python	Haskell

Tail recursion

The Scheme standard requires, that calling a procedure as the last action in a procedure (i.e. returning the called procedure's value as its own result) does not consume stack space. LispMe fullfills this requirement. That means that there need not be a special construct for iteration, as all loops can be expressed as tail-recursive procedure calls.

Languages sharing this trait	Languages not sharing this trait
Normally not defined in the language definition, but elimination of tail-calls to the current procedure is a common optimization in modern compilers.	all others

Latent typing

In LispMe, types are not associated with variables, but with values. This means, you don't have to declare variables, as a single variable may be bound to values of different types during an evaluation. All primitive procedures check the types of their operands at runtime. This is also called dynamic or weak typing.

Languages sharing this trait	Languages not sharing this trait
other Lisps, Smalltalk, APL, Python	C, Pascal, SML, Haskell

First classness

All values including closures, continuations and promises can be used without arbitrary restrictions, i.e. they can be

arguments to procedures
returned by procedures
stored in variables

Languages sharing this trait	Languages not sharing this trait
Common Lisp, Smalltalk, SML, Haskell, Python	C, Pascal, APL

Unlimited extent

All objects created in LispMe have unlimited lifetime (extent) For example, it's possible to refer to the parameters of a procedure, even when the procedure already has returned. LispMe objects are never explicitly destroyed, but there's a mechanism called garbage collection, which may reclaim memory used by objects which provable can't affect an evaluation.

Languages sharing this trait	Languages not sharing this trait
Common Lisp, Smalltalk, SML, Haskell, APL, Python	C, Pascal

Explicit continuations

A continuation represents the future of a computation. At each stage in a evaluation there's a value being computed and a continuation going to do something with this value. Normally these continuations work behind the scenes and programmers don't think much about them. LispMe allows continuations to be captured into a continuation object, which may be stored and called many times and always returns to the same place. Continuations are a powerful control mechanism and can be used to implement non-local returns, exception handling, backtracking, or coroutines.

Languages sharing this trait	Languages not sharing this trait
none	all others

Metalinguistic facilities

LispMe data and programs have similar forms (nested lists). So you can construct a list at runtime and let LispMe interpret it as code by using the function eval.

Languages sharing this trait	Languages not sharing this trait
Other Lisps, Smalltalk, Haskell (experimental)	C, Pascal, SML, Haskell 98

Environment and evaluation

Identifiers

Identifiers (Syntax) have three uses in LispMe:

They can stand for themselves representing whatever the user imagines. This is similar to Pascal/C enumeration types.
They can name variables. A variable name denotes a location in memory where a value is stored. This is called binding. A set of bindings is called an environment.
They can name special forms. Special forms are LispMe expressions which are evaluated in a different way than ordinary names. There's a set of built-in special forms in LispMe, but you can define your own, too, by using macros.

Lexical environment

For each place where an identifier is bound in LispMe, there's a region in the source text where this binding is visible. This region (called scope) is determined solely by the nesting of syntactic structures building the source text. There are some special forms that introduce new bindings. The lexical environment can be visualized as a sequence of frames, where each frame binds some variables. Entering a binding construct extends the current environment by one frame containing the bindings of the variables mentioned in this construct and leaving it restores the old environment in effect before.

A single variable name may be bound in many different frames, but using this name refers to the innermost frame in which the variable is bound (this means the nearest lexical binding form).

When a procedure (or lexical closure) is created by a lambda expression, the environment now in effect is stored together with the procedure's object code to enable the procedure to access the bindings in effect at its creation time.

This applies all to Scheme, too, but LispMe also handles loading memos this way. Initially, the global environment (you can view the variables in the global environment via the names button) contains only some variables (primitive procedures are handled differently, see below). Loading a memo or entering a define expression into the input field creates a new frame in the global environment containing the bindings just created. This frame shadows older bindings of variables with the same name, just like described above. You can remove the last frame of bindings with the pop button. This ensures proper lexical name resolution, but has one disadvantage: You can't refer to names not yet defined. Either the name has to be defined in a memo (or definition) loaded before, or it must be defined in the same memo the referring name is defined, thus allowing mutual recursive definitions.

To facilitate re-definitions of a name (e.g., by evaluating define expressions repeatedly) without having to pop the last definition, LispMe provides an option to rewrite any definition to the corresponding set! if the name being defined already exists. So instead of extending the top-level environment with each definition, the value will just be re-bound.

The read-eval-print loop

A LispMe program is in fact an expression you enter in the input field, which is compiled and immediately evaluated by pressing the eval button using the bindings in the global environment (viewable with the names button). Evaluation computes a value as described in the following sections, which is finally printed in the output field. Furthermore, an evaluation may cause side effects (modify a previously bound variable, output some text, or draw graphics).

Expressions

The semantics of LispMe expressions defined by this grammar is described here.

Literals

Literals are expressions, which evaluate to themselves and don't cause side effects. This means, that the printed representation of a literal is the same as written in a LispMe expression. Self-evaluating expressions include numbers, chars and strings and the special values #t, #f, and #n.

The special form quote returns its argument without evaluating it.

Variables

An expression which is just an identifier is a reference to a variable. The value in the innermost environment frame binding this identifier is returned.

Procedure applications

To evaluate an application, all sub-expressions are evaluated recursively. The first sub-expression must evaluate to a procedure object, i.e. it is a

primitive procedure
lexical closure created by lambda
continuation created by call/cc

Starting with version 3.0, primitive operations are handled as specified in R⁵RS, so all these applications are supported now:

passing a builtin procedure: (map sin '(0 1 2))
using a builtin name as a parameter: (lambda (event) ...)
redefining a builtin name: (let ((+ *)) (+ 1 2 3 4))

The only thing still disallowed is set!-ing a builtin procedure to another value (which is devellish practice anyway :-). However, you can define a builtin name to anything you like, the new binding shadows the builtin value as required by the standard.

Special forms

Special forms provide features not possible with procedure calls:

Avoiding evaluation

See define, delay, quasiquote, and quote, and set!.

Binding

The binding forms lambda, let, and letrec extend the current environment by a new frame.

Control

and, begin, case, cond, if, and or provide decisions and sequential evaluation.

Macros

LispMe does not support the pattern matching macro system of R⁵RS (using define-syntax etc.) but uses the more simplistic model of PC Scheme, which binds symbols to expansion procedures, which are called with the expression to be expanded and should return a simpler expression, which in turn is compiled.

To define a macro, use the macro special form, which associates a symbol with a procedure that takes exactly one parameter. When the compiler encounters an expression beginning with that symbol, the associated procedure is called with the entire expression as its parameter. The expansion procedure should now build a new expression from its parameter. The returned expression is then compiled (and may include further macros, which are expanded accordingly, but only to a limited number, see here for details.