The K i l o L I S P M a n u a l By Nils M Holm, 2019 0 Quick Summary For the impatient LISP user: Kilo LISP is a purely symbolic, lexically scoped LISP system with tail call elimination, macros, and image files. The only data types are the atom (symbol) and the pair/list. full is true and EMPTY is false. The following special forms exist: Core: APPLY IF FILL LAMBDA PROG QUOTE SETQ Derived: LET LABELS COND AND OR QQUOTE LOOP The following functions are predefined: Primitive: ATOM CAR CDR CONS EQ EOFP ERROR RC GENSYM LOAD PRIN PRIN1 PRINT READ SETCAR SETCDR SUSPEND Derived: ASSOC CAAR ... CDDDR CONC EQUAL LIST MAP MEMB NOT NCONC NRECONC NREVER SPACE RECONC REVER The following syntactic sugar exists: 'x is (quote x) @x is (qquote x) ,x is (unquote x) ,@x is (splice x) #xyz is (quote (x y z)) % is the EOT 1 S-Expressions A Symbol is any combination of these characters: a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 0 - Other characters can be included by prefixing them with a /. An Atom is either a symbol or EMPTY. A Pair is an ordered pair of two S-expressions: (car-part . cdr-part) The spaces before and after the dot are optional, i.e. (a . b) = (a.b) A pair may contain other pairs: ((a . b) . c) (a . (b . c)) ((a . b) . (c . d)) An S-Expression is either an atom or a pair. A nested pair of the form (a . (b . c)) may be written as (a b . c) and (a . empty) may be written as (a) The rules apply inductively, so (a . (b . (c . empty))) = (a b c) 1.1 Lists A list is an S-expression that is either EMPTY or a pair whose cdr part is a list: List = EMPTY or (S-expression . List) These are Lists: empty (foo) (foo bar baz) ((a . b) foo (nested list)) A list whose innermost/rightmost cdr part is a symbol is called a Dotted List. These are dotted lists: (a b . c) ((foo bar) . baz) The pair is a two-element dotted list. Lists of single-character symbols may be abbreviated as follows: (quote (a b c)) = #abc Abbreviated lists are self-quoting. See QUOTE. An Association List (or Alist) is a list of pairs (associations), where the car part of each association is called the Key and the cdr part the value of the association: (( . ) ... ( . )) See ASSOC for details. 1.2 Comments A comment may be inserted anywhere (even inside of a form, but not inside of an atom) by including a semicolon (;). Comments extend to the end of the current line. Example: (setq foo ; this is a comment (quote bar)) 1.3 Unreadable Forms A form that contains characters other than those listed in the previous sections are unreadable, i.e. they cannot be read by the LISP parser. Unreadable forms are sometimes output by the system to represent data that have no unambiguous textual representation. 2 Expressions An Expression is an S-expression with a meaning. x => y denotes that x evaluates to y; y is the Value of x. undefined denotes an undefined value. There are four kinds of expressions: Variables Lambda Abstraction Function Application Special Forms Strictly speaking, lambda abstraction is also a special form, but it will be explained separately. 2.1 Variables A Variable is a symbol that is bound to a Location. A location is a container that contains a value. Variables evaluate to the value that is stored in their location: Variable => Value References to unbound symbols (symbols that are not bound to any location) are undefined: unbound-symbol => undefined The term "a variable V is bound to the value X" is short for "a variable V is bound to a location holding the value X". A Constant is a variable that is bound to its own name: constant => constant For instance, the canonical "true" value, t, is a constant: full => full Variables are created by the SETQ special form or by lambda abstraction. 2.2 Lambda Abstraction (Lambda ) is a Lambda Abstraction. Its value is a Function. Names enclosed in angle brackets are Meta-Syntactic Variables. They are not part of LISP, but describe parts of special forms. They may represent single expressions or sequences of expressions. is a list of variables (a.k.a. Formal Arguments) of that function and is the Term or Body of that function. may be - a variable - a list of variables - a dotted list of variables must be at least one expression. Examples: (lambda (x) x) (lambda (f x y) (f (f x) (f y))) (lambda () (print (quote hello/ world))) (lambda x (f x) x) The variables of a function are created by the function by binding their names to locations containing the (actual) arguments of the function. This happens when the function is being applied to some arguments. 2.3 Function Application A variable X is Bound in an expression E, if - E is a lambda function AND - X is a variable of E Examples: X is bound in (lambda (x) (f x)) F is not bound in (lambda (x) (f x)) When a variable X is not bound in an expression E, X is Free in E; X is a free variable of E. A function is Applied to (Actual) Arguments using the syntax (function argument ...) The following steps are involved in the application: (1) each expression in the application is evaluated (2) a location is created for each variable of the function (3) each argument is stored in the corresponding location (4) the body of the function is evaluated (5) the value of the body is returned Because of (1), functions may be bound to variables. In step (1), a variable bound to a function will be replaced by that function. Variables are associated with arguments by position, i.e. the first argument is stored in the first variable, etc. For instance: ((lambda (x y) (cons x y)) (quote 1) (quote 2)) ; evaluate arguments: ; (quote 1) => 1, (quote 2) => 2 ((lambda (x y) (cons x y)) 1 2) ; create variables and store 1 in X and 2 in Y, ; giving the body (cons 1 2) ; evaluate the body, giving the value (1 . 2) 2.4 Optional Arguments When the list of formal arguments is a proper (EMPTY-terminated) list, there has to be exactly one argument per variable: ((lambda (x) x)) => undefined ((lambda (x) x) 'a) => A ((lambda (x) x) 'a 'b)) => undefined When the argument list of a function is a dotted list, the variables before the dot bind like fixed arguments, above, and the variable after the dot binds to a list containing any excess arguments that may be passed to the function: ((lambda (x . y) y)) => undefined ((lambda (x . y) y) 'a) => empty ((lambda (x . y) y) 'a 'b)) => (b) ((lambda (x . y) y) 'a 'b 'c)) => (b c) ... When there are no fixed arguments, the formal argument list is replaced with a single variable that binds to a list of all arguments: ((lambda x x)) => empty ((lambda x x) 'a) => (a) ((lambda x x) 'a 'b)) => (a b) ... 3 Special Forms A Special Form is an expression of the form ( ...) The syntax is the same as in function application, but there are some differences: When a syntactic Keyword is found in the first slot of a list, neither the keyword nor any s will be evaluated. The s will then be processed by the LISP system according to the semantics of the individual special form. These semantics may involve the evaluation of some of the s. A Keyword is sometimes also called a Special Operator. The special operators of the Kilo LISP language are APPLY IF FILL LAMBDA PROG QUOTE SETQ 3.1 (LAMBDA EXPR1 EXPR2 ...) => FUN Create a new function with the formal arguments and the body (PROG EXPR1 EXPR2 ...). The PROG special form is implied, i.e. (lambda (x) a b c) will be interpreted as (lambda (x) (prog a b c)) may be a list, a dotted list, or a single variable. See Function Application, above. Examples: (lambda (x) x) ; identity function (lambda (x) (car (cdr x))) ; CADR function (lambda x x) ; LIST function 3.2 (APPLY FUN LIST) => EXPR Apply FUN to the given LIST of arguments and return the value delivered by the function. Basically, APPLY does X = (cons fun list) and then evaluates X, but *without* evaluating the arguments in LIST again. FUN may be a built-in function, or a lambda function, but not a special operator (like APPLY itself). Example: (apply cons '(1 2)) => (1 . 2) 3.3 (QUOTE EXPR) => EXPR Return EXPR unevaluated. The form 'x is an abbreviation for (quote x). Examples: (quote foo) => foo (quote (car x)) => (car x) '(foo bar) => (foo bar) 3.4 (IF EXPR1 EXPR2 EXPR3) => EXPR Evaluate EXPR1. When its value is not EMPTY, evaluate EXPR2 and otherwise evaluate EXPR3. Return the value of the expression evaluated last. EXPR1 is called the Predicate of the form. Examples: (if full 'yes 'no) => yes (if empty 'yes 'no) => no (if (atom 'x) 'a 'b) => a 3.5 (FILL EXPR1 EXPR2) => EXPR Evaluate EXPR1. When its value is not EMPTY, return EXPR1. Otherwise evaluate and return EXPR2. In either case EXPR1 is only evaluated once. Examples: (fill 'foo 'bar) => foo (fill empty 'bar) => bar 3.6 (SETQ EXPR) => Evaluate EXPR and store its value in the location bound to the variable . Return . When is not bound to any location, a fresh location will be created and will be bound to it. Example: (setq foo 'bar) => foo foo => bar 3.7 (PROG EXPR ...) => EXPR Evaluate all given expressions from the left to the right and return the value of the rightmost expression. The special form (prog) evaluates to EMPTY. Examples: (prog '1 '2 '3) => 3 (prog (print 'foo) ; print foo, then print bar (print 'bar)) => bar 4 Derived Special Forms A Derived Special Form is a special form that is being transformed by the LISP system to an expression that uses only function application and the (primitive) special forms listed in the previous chapter. A function transforming a derived special form to a primitive expression is called a Macro. A macro is defined using the SETQ, MACRO, and LAMBDA special forms: (setq (macro (lambda ...))) The transformation of a derived special form is called Macro Expansion. It is part of the evaluation process and happens after reading but before interpreting an expression. The transformation is performed by passing the arguments of the derived special form to the macro and then replacing the derived special form by the result of the macro. The result of macro expansion can contain more derived special forms, which will also be expanded. Examples: (setq kwote (macro (lambda (x) (list 'quote x)))) This macro will expand the derived special form (kwote foo) to the expression (quote foo), no matter what FOO is. The result of the form is FOO. (setq listq (macro (lambda x (if (eq empty x) empty (list 'cons (list 'quote (car x)) (cons 'listq (cdr x))))))) This macro will expand the derived special form (listq a b c) to (cons (quote a) (listq b c)) then to (cons (quote a) (cons (quote b) (listq c))) then to (cons (quote a) (cons (quote b) (cons (quote c) (listq)))) and then to (cons (quote a) (cons (quote b) (cons (quote c) empty))) which no longer contains any derived special forms. The last expression in the process is then interpreted, giving the result (a b c). The LISTQ macro can be implemented more comprehensibly using quasiquotation -- see QQUOTE at the end of this chapter. 4.1 (GENSYM) => SYMBOL Generate a unique symbol name. Rationale: When derived special forms expand to expressions containing local variables, these variables should be named using GENSYM. Otherwise name capturing can occur, as the following example illustrates: (setq swap (macro (lambda (x y) @(let ((L ,x)) (setq ,x ,y) (setq ,y L))))) It is supposed to swap the values of X and Y, but the local name L is captured when expanding (swap L M), which does nothing: (let ((L L)) (setq L M) (setq M L)) (It creates a local L and initializes it with the outer L, then sets the local L to M and then M to the local L.) The proper way to implement the SWAP macro would be: (setq swap (macro (lambda (x y) (let ((g (gensym))) @(let ((,g ,x)) (setq ,x ,y) (setq ,y ,g)))))) Example: (list (gensym) (gensym) (gensym)) => (G1 G2 G3) 4.2 (LET ) => EXPR has the form (( EXPR1) ... ( EXPRn)) and is an implied PROG form. Create the variables through , then evaluate the expressions in no specific order and bind their values to the corresponding variables. Finally evaluate and return its value. Examples: (let ((a '1) (b '2)) (cons a b)) => (1 . 2) (let ((a 'foo)) '1 '2 a) => foo (let ((a '1)) (let ((a (cons a '2))) a)) => (1 . 2) 4.3 (LABELS ) => EXPR has the form (( EXPR1) ... ( EXPRn)) and is an implied PROG form. Create the variables through and then evaluate the expressions, from left to right, and store their values in the associated variables. Evaluate and return its value. When the EXPRs are lambda special forms, then each EXPR may refer to each VAR, thereby allowing to create mutually recursive functions. In addition, each EXPRi can refer to any , without any further restrictions, as long as J full (labels ((complement (lambda (p) (lambda (x) (eq empty (p x))))) (pair (complement atom))) (pair '(1 . 2))) => full 4.4 (AND EXPR ...) => EXPR Evaluate the given expressions, from left to right, until one expression evaluates to EMPTY. In this case return EMPTY. When none of the EXPRs evaluates to EMPTY, return the value of the last expression. When no arguments are given, return T. This special form implements the short-circuit logical AND. Examples: (and) => full (and '1 '2 '3) => 3 (and empty 'foo) => empty 4.5 (OR EXPR ...) => EXPR Evaluate the given expressions, from left to right, until one expression evaluates to a value other than EMPTY. In this case return the value. When none of the EXPRs evaluates to non-EMPTY, return EMPTY. When no arguments are given, return EMPTY. This special form implements the short-circuit logical OR. Examples: (or) => empty (or '1 '2 '3) => 1 (or empty 'foo) => foo (or empty empty) => empty 4.6 (COND ...) => EXPR Each has any of these forms: (EXPR1 EXPR2 ...) (EXPR1) (ELSE EXPR2 ...) COND proceeds as follows: The predicate EXPR1 of the first clause is evaluated. When its value is not EMPTY, there are two cases to distinguish: (1) When the clause contains multiple expressions, the expressions EXPR2 ... will be evaluated from the left to the right and the value of the last expression will be returned. No other clauses will be examined. (2) When the clause contains only the predicate EXPR1, the value of the predicate will be returned. No other clauses will be examined. When the predicate of the first clause is EMPTY, the predicate of the next clause will be evaluated. Evaluation of COND ends when either a clause with a true predicate is found or no clauses are left to evaluate. When there are no clauses left to evaluate, EMPTY is returned. When a clause has a predicate of the form ELSE, then the predicate will be assumed to be true *and* the clause must be the last clause in the COND form. Examples: (cond (full 'first) (full 'second)) => first (cond (empty 'a) (empty 'b) (full 'c)) => c (cond (empty 'a) (else 'b)) => b (cond (empty 'foo)) => empty (cond) => empty 4.7 (LOOP ) => EXPR has the form (( EXPR1) ... ( EXPRn)) and is an implied PROG form. is a variable that will be bound to the function (lambda ( ... ) ) and this function will then be applied to the arguments EXPR1 through EXPRn. Hence applying to new arguments inside of will re-enter the loop with new values bound to the given variables. Examples: ; print (3 2 1), (2 1), (1) (loop next ((a '(3 2 1))) (cond ((eq empty a)) (else (prin a) (next (cdr a))))) => full ; infinite loop (loop next () (next)) 4.8 (QQUOTE