Lispkit Lisp
Encyclopedia
Lispkit Lisp is a lexically scoped, purely functional
subset of Lisp
("Pure Lisp") developed as a testbed for functional programming
concepts. It was first used for early experimentation with lazy evaluation
. An SECD machine
-based implementation written in an ALGOL
variant was published by the developer Peter Henderson in 1980. The compiler
and virtual machine
are highly portable
and as a result have been implemented on many machines.
atom: given an expression returns True if its value is atomic; False if not.
add: given two expressions returns the sum of their numeric values.
car: given an expression whose value is a pair, returns the pair's first value.
cdr: given an expression whose value is a pair, returns the pair's second value.
cons: given two expressions returns a value pair consisting of their values.
div: given two expressions returns the dividend of their numeric values.
eq: given two expressions returns True if their values are equal; False if not.
if: given three expressions returns the value of the second if the value of the first is True, otherwise returns the value of the third.
lambda: given an expression, returns that expression as an evaluable value.
let: given a list of named expressions, returns that list as a single evaluable value.
letrec: given a list of named expressions, returns that list as a single evaluable value.
leq: given two expressions, returns True if the value of the first is numerically less than or equal to the value of the second; False if not.
mod (or rem): given two expressions, returns the modulus (also known as the remainder) of their numeric values.
mul: given two expressions, returns the product of their numeric values.
quote: given an expression, returns that expression as a value.
sub: given two expressions, returns the difference of their numeric values.
The functions, lambda, let, and letrec, are similar but have subtle differences in the way that they treat named variables which make them useful in different ways. lambda defines and returns a function, let binds expressions to variable names, and letrec is essentially similar to let except it allows for the definition of recursive
functions.
Purely functional
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
subset of Lisp
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
("Pure Lisp") developed as a testbed for functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
concepts. It was first used for early experimentation with lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
. An SECD machine
SECD machine
The SECD machine is a highly influential virtual machine and abstract machine intended as a target for functional programming language compilers. The letters stand for Stack, Environment, Code, Dump, the internal registers of the machine...
-based implementation written in an ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
variant was published by the developer Peter Henderson in 1980. The compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
and virtual machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
are highly portable
Porting
In computer science, porting is the process of adapting software so that an executable program can be created for a computing environment that is different from the one for which it was originally designed...
and as a result have been implemented on many machines.
Base language
The base language provides the following functions only but extensions are discussed in Henderson's book for the explicit support of lazy evaluation and non-deterministic programming.atom: given an expression returns True if its value is atomic; False if not.
add: given two expressions returns the sum of their numeric values.
car: given an expression whose value is a pair, returns the pair's first value.
cdr: given an expression whose value is a pair, returns the pair's second value.
cons: given two expressions returns a value pair consisting of their values.
div: given two expressions returns the dividend of their numeric values.
eq: given two expressions returns True if their values are equal; False if not.
if: given three expressions returns the value of the second if the value of the first is True, otherwise returns the value of the third.
lambda: given an expression, returns that expression as an evaluable value.
let: given a list of named expressions, returns that list as a single evaluable value.
letrec: given a list of named expressions, returns that list as a single evaluable value.
leq: given two expressions, returns True if the value of the first is numerically less than or equal to the value of the second; False if not.
mod (or rem): given two expressions, returns the modulus (also known as the remainder) of their numeric values.
mul: given two expressions, returns the product of their numeric values.
quote: given an expression, returns that expression as a value.
sub: given two expressions, returns the difference of their numeric values.
The functions, lambda, let, and letrec, are similar but have subtle differences in the way that they treat named variables which make them useful in different ways. lambda defines and returns a function, let binds expressions to variable names, and letrec is essentially similar to let except it allows for the definition of recursive
Recursion (computer science)
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
functions.
Further reading
- Peter Henderson, Geraint A. Jones, and Simon B. Jones, "The LispKit Manual" (ISBN 0-902928-18-X)
External links
- LispKit
- [ftp://ftp.comlab.ox.ac.uk/pub/Packages/LispKit/ Implementation of Lispkit]
- GNU Pascal LispKit port
- Archive of old LispKit LISP code and files, plus C implementation of SECD machine
- Paper about a LispKit LISP implementation in Java