This file is raw output from pdftotext and may not be ideal for distribution. If you are a maintainer for Hackipedia, please sit down when you have time and clean this text version up. Source PDF: /mnt/main/jmc-storage/docs/Languages, computer/Lisp/Lisp As An Implementation Language For Computer Algebra Systems, Yacas v1.0.55 (May 20, 2003).pdf Like all conversions the text below should be fully readable as UTF-8 unicode text. --------------------------------------------------------------- (IN PROGRESS) Lisp as an Implementation Language for Computer Algebra Systems 1 by the Yacas team Yacas version: 1.0.55 generated on May 20, 2003 Lisp is a very simple language, one suited for doing computer algebra. Almost all CAS systems today owe a lot to the ideas that came from Lisp. This is a book on the Lisp language, and its connection to Yacas. Yacas is built on top of a Lisp dialect. 1 This text is part of the Yacas software package. Copyright 2000–2002. Principal documentation authors: Ayal Zwi Pinkus, Serge Winitzki, Jitse Niesen. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts and no Back-Cover Texts. A copy of the license is included in the section entitled “GNU Free Documentation License”. Contents 1 A brief introduction to Lisp 2 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Why choose Lisp over other languages? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 A little history of Lisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 The Lisp interactive command line interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 A basic set of Lisp primitive commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6 Arbitrary precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 A few useful macros and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.8 A reality check: implementing more functions in the interpreter for efficiency . . . . . . . . . . . . . . . 7 2 Language design issues 9 2.1 Enforcing correct code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Containers and iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Packaging modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Default modules defined in the Lisp environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Error handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.6 Type systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.7 Data structures as types in Lisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.8 Typing in Yacas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Compiling Lisp code 14 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Steps for converting to source code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Parsing the expressions into an internal format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Some general rules for optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 Dealing with function calls and macro expansions when compiling Lisp expressions to syntax from other languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.6 The concept of bootstrapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.7 Strong typing as an option for generating optimized code . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Converting Yacas script code to other languages 19 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Relevant parts of the system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Naming conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.4 Functions used from the Common Lisp environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.5 The read-eval-print loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.6 Making the Yacas parser available . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.7 Compiling functions to native Lisp syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.8 The custom evaluator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.9 The system in action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5 GNU Free Documentation License 21 1 Chapter 1 A brief introduction to Lisp 1.1 Introduction At the end of the day we want to arrive at a language where we can implement an algorithm in a few lines of code, and have Yacas owes much of its current form to Lisp. A lot of ideas the compiler generate efficient code for it. from Lisp have been taken over into the Yacas interpreter. Given the strong typed Lisp we are using here, how is it This book aims to describe this connection, to show how different from using c++/Java directly? Yacas compares to other Lisp dialects (Yacas can be viewed The difference is in the syntax. Algorithms for manipulating as a dialect of Lisp), and how the Yacas interpreter is related symbolic expressions are written down much more naturally in to Lisp. a language that supports these operations natively. The code to Viewed from the top level, Yacas is just one function; Yacas perform symbolic manipulation operations can look surprisingly is called with one, or possibly two arguments, or from a different complex when written in c++ or Java. Later on, a compiler point of view, a request is made to the Yacas system. How the for the Lisp dialect developed here that will try to compile to function performs the action is implementation-dependent, but human-readable source code will be described. Although the at the top-level it can be viewed as one call. From c++ or Java, results are somewhat readable, they are a lot less readable than it might look like the original Lisp or Yacas script code they were generated from. Convenient notation aids the programmer greatly in thinking yacas.Evaluate("expression"); about a problem. It is not unusual in mathematics to devise a Or from Lisp, new notation scheme to make life easier. For example, the bra ket notation, where stands for the inproduct defined as (yacas expression environment) Integrate()a*b The environment argument is optional; it can be a global resource that doesn’t have to be passed in. has the added advantage of being able to write down projec- For instance, taking the derivative of a function could look tion operators of the form |b> a 1.3 A little history of Lisp Error, variable has no value : a Lisp is one of the older computer programming languages in Lisp dialects are usually case-insensitive (the atom a is the existence. It came from a mathematical background, lambda same as A). calculus, and is used even now. Arguably, most programming Here the atom a evaluated to itself, because it was not as- languages owe a lot to Lisp. signed. There are various sources on the internet describing the early history of Lisp. In> (setf a ’(this is a list)) Out> (this is a list ) In> a 1.4 The Lisp interactive command Out> (this is a list ) line interface Here we assigned the value (this is a list) to the variable a, and a now evaluates to that list. The system looked up the When Lisp is started, the user is generally greeted with a value bound to the variable a without re-evaluating it. prompt. The Lisp interpreter is in its read-eval-print loop; it reads in an expression typed in by the user, evaluates it, and In> ’a prints the result of evaluation to the console. Out> a The definition of an expression can be given such; In> (eval a) 1. an expression is either an atom, or a list of expressions. ERROR: function not defined : this Out> nil 2. an atom is a word, a list of characters. So, the words foo and bar could be called atoms. A list With quote we can withhold evaluating a, and with eval we is represented by writing the expressions in the list out with can re-evaluate a. Since this is not a defined function in this spaces in between them, and brackets around them. So, (foo case, an error is raised. bar) would be a list with two elements, foo and bar. Note that evaluation as defined in Lisp dialects is less suitable In Lisp, each expression can evaluate to a value (if no error for CAS systems. A CAS would return expressions unevaluated, occurred). When evaluating an atom, the atom can either be a which is what you want in a CAS. It then represents some func- ’special’ atom that evaluates to itself, or otherwise a lexical word tion which has not been specified yet. In a Lisp intepreter, it is that refers to a variable. When it is a variable, the Lisp system nice to have the interpreter raise an error, but in a CAS, where looks up its value, and returns the value the variable is bound it is data, it should not be simplified further. to, in what is called the ’environment’ the Lisp interpreter is For atoms that refer to variables that are not yet bound, the evaluating in. When a variable is not bound, an error is raised. variables should be returned unevaluated by default, and func- The noted difference with the usual Lisp dialects is that a normal tions that are called but not defined should be returned as the Lisp system raises an error when an expression tries to evaluate same function but with their arguments evaluated. evaluation a variable that is not bound to a value, whereas in a CAS, the as defined in most Lisp dialects is not suited to simplifying ex- variable is a free parameter in some expression. pressions. Later in this book an evaluator will be developed in When a list of expressions is encountered, the first element Lisp itself that is closer to a sense of ’simplification’ required for in the list is a function that should be called, and the rest of CAS. the expressions in the list are the arguments. The interpreter Sometimes the user wants to refer to a function without hav- handles the list by first evaluating the arguments (the rest of ing to define it, because transformation rules for the function can the list), and then calling the function with the evaluated argu- be given without explaining explicitly how to go about evaluat- ments as parameters to the function. There are exceptions to ing the function. Certain functions have properties, and some- this; the function quote returns its argument unevaluated. In times it is easier to work with the properties than to evaluate stead of writing (quote ), a common short-hand them explicitly. is ’, eg. the expression with a quote in front of For the rest of this book, it is assumed that the semi-colon, it. Quotes are used a lot, to tell the system that data is being ;, means that the rest of the input line up to the end of line or passed in. end of file is a human readable comment, not to be executed. 3 1.5 A basic set of Lisp primitive Assigning variables and functions commands In addition, functions and macros can be defined: 1. (setf ) - to assign a variable, Surprisingly few Lisp functions are needed to be able to imple- setf can be used. the variable argument is not evaluated ment any algorithm in Lisp. Languages are usually referred to before setf is called, but expression is. as being Turing complete if any algorithm can be implemented in them. Turing showed that a small apparatus, called a Turing 2. (defun machine, was universal in that theoretically any algorithm could ) - define a function whose name is be implemented in it. The way to show a language is Turing function-name, and a list of arguments argument-list. complete is to implement a Turing machine in that language. This function can then be called from anywhere. Its if that is done, that language can execute any algorithm, as a arguments are first evaluated, and a set of local variables Turing machine can be implemented in it, and Turing machines (listed in the argument-list argument) are reserved, and can execute any algorithm. bound to the values passed in. Note that building a Turing machine is just a theoretical exer- 3. (defmacro cise. Turing machines don’t concern themselves with efficiency. ) - does the same as defun, but with Algorithms can be run, in finite time, but it will most certainly the arguments not evaluated before evaluating the body not be the most efficient way to execute the algorithm on a real expression. Also, the expression is evaluated from computer. within the calling scope, so the expression can use Methods to make execution more efficient break down in two variables from its calling environment. A better way to steps: look at macros is as if they were copy-pasted into the place where they were called. 1. encapsulating a specific algorithm in a function call, and make define an efficient implementation of the function in The default set of functions implemented in the core of a Lisp the environment the Lisp interpreter is executing in interpreter can be divided between function-like and macro-like functions, in that when a function-like (defun) function is called, 2. writing a compiler that converts algorithms stated in Lisp its arguments are evaluated first. Examples of this are cons, code to a version that is more efficient, more close to the first and rest. hardware the program is running on When calling macro-like (defmacro) functions, however, the This section describes a minimum set of Lisp primitives arguments are not evaluated first, and the variables defined in needed for building a Turing machine, theoretically. After that, the calling environment are visible while expressions using ar- first numeric operations are introduced, before implementing a guments on the command line are evaluated. A macro can be Turing machine. Fundamentally, the language does not need to viewed as a bit of code that got pasted in to the place where it support arithmetic in order to be able to implement any algo- got called, by the interpreter (in fact, this is what a compiler rithm, as other constructs using lists can be used to represent can do). and work with numbers, but not implementing it does make the The defmacro function allows the programmer to expand the effort rather complex. language by adding functions that act as if they were defined in The following sections will describe the following minimal set the core part of the interpreter. of commands; Macros are not necessary, strictly speaking. Macros clean up the syntax of a program, in that it allows a programmer to write 1. macro-like commands quote, if, cond, setf, while, progn, more clean and brief code. For example, the expression eval, defun and defmacro. (if (equal a b) () (print a)) 2. function-like commands assoc, first, rest, cons, atom, listp, list, equal, +, integerp, - and <. could be written more concisely as In the next sections, whenever a function call is explained, (unless (equal a b) (print a)) the arguments to the function will be delimited by < and >. Arguments are evaluated unless stated otherwise. if unless were defined. But it would have to be defined as a macro, as when unless is called, the arguments should not be evaluated first. Unless can be defined as: Naming conventions (defmacro unless (predicate body) The set of primitives described in this section are meant to be (if predicate nil body) ) used as building blocks for building a final bigger system. This makes unless work, as the following interaction shows: Controlling evaluation In> (unless t (print ’SOMETHING)) To control whether evaluation is performed, the following com- Out> nil mands are available: In> (unless nil (print ’SOMETHING)) SOMETHING 1. (quote ) - as described in the introduction Out> SOMETHING above, quote takes one argument, and returns it unevalu- ated. Especially when code is generated, and does not have to be human-readable, macros are not necessary. But they are a nice 2. (eval ) - eval also takes one argument, and feature nonetheless, and have to be implemented in the inter- evaluates it when eval is called. When eval is called, its preter, it can not be faked with normal defun functionality. argument was evaluated already. Examples involving defun: 4 In> (defun foo (atom) (cons atom (list rest))) In> (cons ’a ’(b c)) Out> foo Out> (a b c ) In> (setf rest ’end) In> (list (+ 2 3) 4 3) Out> end Out> (5 4 3 ) In> (foo a) One important function is assoc: Out> (a end ) In> (foo b) 1. (assoc ) - given an association list, Out> (b end ) which is a list of (¡key¿ ¡value¿) pairs, return the first found pair for which the key matches the one given as first argu- In addition, nameless (pure) functions can be made, which ment, or return nil if it wasn’t found. work exactly as their defun/defmacro counterparts, as lambda Examples: and macro: In> (setf list ’( ("name" "Peter") ("age" 28) ) ) 1. (lambda ) - define a pure unnamed Out> list function. In> (assoc ’"name" list) 2. (macro ) - define a pure unnamed Out> ("name" "Peter" ) macro. In> (assoc ’"age" list) Out> ("age" 28 ) Examples: In> (assoc ’"something" list) Out> nil In> (setf add ’(lambda (x y) (+ x y))) Out> add In> (add 2 3) Predicates Out> 5 Common Lisp has two special atoms, t and nil. t stands for Note that pure functions, the lambda and macro expressions true, whereas nil stands for false. nil is actually usually also described here, are not strictly necessary, if we have equivalents the empty list. Typing an empty list () is the same as typing for defun and defmacro. But pure unnamed functions do allow nil: for convenient notation, without clobbering up the global name In> () space. They also allow for locally defined functions. If they are Out> nil required, they have to be part of the interpreter, since it cannot In> nil be faked with defun and defmacro. Out> nil An interesting option is to not define the operations defun In Common Lisp, nil is considered to mean false when con- and defmacro, but just setf, lambda and macro. This set is just sidered as a boolean result from a list, and anything different as powerful, and in fact allows you to create defun and defmacro from nil is considered to mean true. This is then used as an from them. We choose defun and defmacro over the route of efficient way to find items in lists. The result returned can then using setf, lambda and macro to define defun and defmacro either be a found result, or nil which means nothing was found. because lambda and macro are not strictly required to build a CAS. When implementing a more mature Lisp interpreter, it In> (rest ’(a b)) is wise to define lambda and macro, for the convenience of the Out> (b ) programmer. In> (rest ’(a)) Out> nil Creating and disseminating lists of expres- The author feels uneasy with having the nil atom overloaded as both an empty list and false when used in predicates, because sions it makes code harder take along to another language. In some Lists of expressions are used to build more elaborate structures. cases nil means an empty list, and in some cases it means false, The following commands are available for doing so: which complicates converting code, due to the fact that the To disseminate a list: code has to be examined more closely for this. Yacas has a distinct set of atoms, True and False precisely for this reason. 1. (first ) - return the first element of a list A test to see if something is an empty list is still possible, by 2. (rest ) - return the list with the first item removed. comparing the result of evaluating an expression with an empty list. Indeed, Yacas is not alone in this, Scheme (another dialect Examples, taken from an interaction with clisp: of Lisp) has different symbols for true and false, #t and #f respectively. In> (first ’(a b c)) Two predicates needed for operating on lists are then: Out> a In> (rest ’(a b c)) 1. (listp ) - listp returns t if ¡expression¿ is Out> (b c ) a list, nil otherwise. 2. atom - atom returns T if the expression To reconstruct a list: passed in is an atom (a word). 1. (cons ) - cons returns 3. (equal ¡expression-1¿ ¡expression-2¿) - returns t if the two a list that has ¡first-expression¿ as its first element, and expressions are the same, nil otherwise. Common Lisp has ¡rest-list¿ as the rest of an expression. more equality operators. They are more efficient for spe- 2. (list <...>) - return a list with the ¡...¿ arguments eval- cific types of comparisons. equal is the most generic form uated. which works on all types of input. As we are composing a minimum subset of functions to work with in this part of Example taken from an interaction with clisp: this book, we will only mention equal. 5 Note the difference in atom and listp, which was taken from The next sections after that will continue by introducing a Common Lisp. In Common Lisp predicates are supposed to be few building blocks that are needed to implement a CAS like suffixed by a ’p’, but apparently not so with atom. Yacas. Variable scoping 1.6 Arbitrary precision arithmetic 1. (let ) - Variables can be declared locally in the function being called, using Let. Before proceeding to build up a full system, we first introduce the arithmetic to the system. Arithmetic could theoretically be When setf is called, first the local variables are searched for performed by using what we already have (lists of objects, where a candidate variable to set, and after that the global variables the number of objects in the list represents the number), but it are searched. When entering a function body, a local frame of would be impractical. local variables for that function are defined, and the parameter We start with the representation of numbers. This section will variables are bound to the arguments passed in to the function. only refer to arbitrary precision integers, floating point num- let allows the programmer to declare additional local variables. bers will come later. The implementation of the Lisp dialect The following example sets up variables n and m and assigns described here is designed to be easily extended that way. them values locally. n is bound to a, and m bound to (b c). Numbers are represented as atoms, sequences of characters. In> (let ( (n ’a) (m ’(b c)) ) (cons n m)) More specifically, they can be a sequence of digits from 0 to 9 Out> (a b c ) (we will work in the decimal number system here, as that is what In> n most humans are used to). Negative integers have a minus sign ERROR: variable not defined : n in front of them. So, 1234 and -1234 are atoms representing Out> nil the integers 1234 and -1234 respectively. The most basic arithmetic operations are then addition and The expression part in the let form gets evaluated after the negating a number: local variables have been assigned. Note that evaluation of the expressions in the let form are performed in the scope where In> (+ 1 2 3) the let form is called, thus expressions in the let form can use Out> 6 local variables from its surroundings. In> (- 5) Local variables that are declared in a certain scope where the Out> -5 variable already had a value mask the older declaration of the In> (+ 2 (- 3)) variable. Out> -1 Note: the values that will be assigned to the local variables Together with a predicate to determine that something is an are evaluated before being assigned to the local variables. So the integer (integerp), and an ordering operator less than denoted expressions in the assign-list cannot refer to other variables <, other arithmetic operations like multiplication, division, ex- declared in the same assign-list. ponentiation etc. can be built. Some examples using < and integerp. Execution control In> (integerp 4) No language is complete without conditional execution and Out> t looping. In> (integerp -4) 1. (if ) - an if Out> t statement: if predicate doesn’t evaluate to nil return the In> (integerp ’a) result of evaluating the then-clause expression, otherwise Out> nil return the result of evaluating the else-clause. In> Out> (a b c ) In> (integerp ’(a b c)) 2. (while ) - this function evaluates Out> nil body until predicate returns nil (predicate is called be- In> (< 2 3) fore each iteration), and the result of the last evaluation of Out> t body is returned afterwards. In> (< 3 2) 3. (cond ( ) ... ( Out> nil )) - similar to cond in Lisp: the items are traversed one at a time, from front to end, evaluating the Note that a computer algebra system requires arbitrary pre- predicates. if one does not evaluate to nil, its body is cision arithmetic, as for certain algorithms the intermediate re- evaluated, and the result of evaluating returned. sults of a calculation can become big, even if the final result is small. So, a CAS should be able to do the following: 4. (progn ... ) - evaluate multiple ex- pressions, and return the result of evaluating the last ex- In> (+ 12345678901234567890999999999999999999 1) pression, body-n. Out> 12345678901234567891000000000000000000 This concludes the a set of functions required for building up a computer algebra system. It is not a minimal set by any means, as a following section will show; if can be defined by 1.7 A few useful macros and func- using defmacro and cond, for instance. tions The next section will first introduce arbitrary number arith- metic support. It is not strictly necessary for the interpreter to Now we are ready to create more powerful building blocks using work and be able to do anything, but it is the first concession the primitive set of functions introduced in previous sections. we will make towards efficiency, as it is rather hard to find an The routines developed here will be built from the primitive algorithm that does not need arithmetic. building blocks described before. However, an implementation 6 is free to implement these hard-coded in the core kernel for and with this we can start to print functions for boolean ex- speed. This is advisable because the constructs developed here pressions. First, let us define a not operator, which returns True will be used often, and so there is a need for efficiency. if its argument is nil: Note that the functions introduced so far are not minimal. Some can be defined in terms of others. They are defined here In> (defmacro not (a) (null a) ) because they are easy to define in an interpreter without making Out> not the interpreter much larger, but are used often, so efficiency is In> (not ’a) required. For instance, given the cond and defmacro operations, Out> nil it is possible to define an if operation: In> (not nil) Out> t In> (defmacro Newif (pred then else) Then lazy and and lazy or operations can be defined: (cond ( pred then) In> (defmacro and (a b) (if a b nil)) ( t else) Out> and ) ) In> (defmacro or (a b) (if a t b) ) Out> Newif Out> or In> (Newif (equal ’a ’b) ’c ’d) These evaluate their first argument first, and decide to eval- Out> d uate the second only if the first one does not give enough in- In> (Newif (equal ’a ’a) ’c ’d) formation to decide whether to stop. For instance, if the first Out> c argument to and returns false (eg. nil), then the result of eval- In> (if (equal ’a ’b) ’c ’d) uating the entire expression should be nil, otherwise it returns Out> d the result of evaluating the second argument. or works the In> (if (equal ’a ’a) ’c ’d) other way round: it evaluates the second argument if the result Out> c of evaluating the first argument was nil. Now let us start by building a set of new primitives using Lazy and and or operators can be used to combine predicates the ones introduced so far. We start by defining Null, which into a larger predicate, but also to guard evaluation of an ex- returns True if its argument is an empty list: pression, let it only evaluate an expression if a pre-condition is met. The unless operation could equally well have been defined In> (defun null (expr) (equal expr nil) ) by using or: Out> null In> (null ’a) In> (defmacro unless (predicate body) Out> nil (or predicate body) ) In> (null ()) Out> unless Out> t In> (unless t (print ’SOMETHING)) In> (null nil) Out> nil Out> t In> (unless nil (print ’SOMETHING)) SOMETHING With this, we can define a Length function which returns the Out> SOMETHING length of a list: In> (defun length (list) Most of these functions are convenience functions. They make (if (null list) code easier to read. Macros in effect allow you to extend the 0 language. (+ 1 (length (rest list))) ) ) Out> length 1.8 A reality check: implement- In> (length ’(a b c)) Out> 3 ing more functions in the inter- In> (length ()) preter for efficiency Out> 0 Even though new functions can be created in Lisp code rather In addition to the already defined function first, we can than the interpreter, it is not necessarily a good idea to do so. define the functions second, third, etc. to print code that is For instance, declaring additional local variables can be done easier to read: with defmacro (and in this case macro would also be neces- In> (defun second (list) (first (rest list) ) ) sary). However, it is used a lot in Lisp code, so it makes sense Out> second to write an efficient version in the interpreter itself. This section In> (defun third (list) (first (rest (rest list) ) describes a few commands that, although not strictly necessary, ) ) Out> third should be implemented in the interpreter for efficiency of exe- In> (setf lst ’(a b c)) cution. Out> lst The reasons for adding these functions fall into the following In> (first lst) categories: Out> a 1. routines that make for easy debugging (example: print). In> (second lst) Out> b 2. routines that can be implemented a lot more efficiently in In> (third lst) the interpreter than using the base Lisp commands (exam- Out> c ple: let). 7 3. routines that are already implemented in the interpreter any way (examples: second, third, null, eq). It is a pity if these were not used while they are already implemented efficiently and available. 4. commands related to user interfacing. An example is exit, which is not strictly needed, but facilitates quitting the command line version of the interpreter. These should be implemented in the code that is only used in the console version. exit makes less sense in a graphical user interface, where stopping the application is likely to be performed in different ways. exit is not strictly a function needed for CAS. The commands described here can be implemented in the interpreter, but they are not strictly necessary, or they can be implemented in Lisp code using more basic primitives. 1. (let ( ( ) ... ( ) ) ) - evaluate the values val-1 through ¡val-n¿ and declare new local variables and then assign the values to the new local variables. Note that the values are evaluated before assigning them to the variables, so the variables can not depend on each other. 8 Chapter 2 Language design issues This documentation comes with some implementation for the 3. check if there are still objects in the container little Lisp dialect introduced in this document. It is imple- A lot of algorithms working on data can get away with this se- mented in Java. This section discusses some details pertain- quential processing, performing an operation on an object, and ing to the implementation. It will discuss some features of the then moving to the next object to perform the same operation language design. on it. The classic way in Lisp has been to have a list of objects, and 2.1 Enforcing correct code have the first function return the first of the list, rest return the rest (the objects that still need processing), and when the Programmers are lazy. They will try to get as much as possible list is empty, all objects have been processed. done by typing as little as possible. This can be used as an The reason to make this abstraction is that for specific cases advantage in the design of a programming language. If the optimizations can be made in the way the container is imple- programming language makes it easy ’to do it the right way’, mented internally. For instance, in stead of a list, an array but hard ’to do it the wrong way’, the programmer might take could be used, which gives constant-time access to an element the easy route and do it right. The culmination of this is to in a container, but slow O(n) insertion time. Many more op- make it possible to do it right, but impossible to do wrong. The tions are available; objects could be obtained from a compressed language c has many examples of the opposite, where it is easy block of data, or read in sequentially from disk (for huge sets to do something wrong, but hard to do it right. The functions of objects), or a set of objects could be defined symbolically, gets and fgets are examples. like (range 1 Infinity). A routine could then be written that From the other side, exceptions in Java for instance, can not finds the first occurrence of an integer that has certain proper- be ignored. A routine has to handle it, or promise to pass off ties, for instance. One would need to have a function first and the exception to the calling environment. But then all the func- rest and null for arrays and for objects of the form (range tions calling the function must handle the exception, resulting ). in much more typing work. This is an important issue, because computers are good at This concept can be put to great use in for instance a doing a dull task, but doing it millions of times over. One option typing system, where it can be made very hard to pass an is to have a huge data set and process it. An efficient way of arbitrary-type object around, like the void * of c or c++, or walking over a sequence of data objects is then necessary. a GenericLispObjectHugeTypeDeclarator in a Lisp system, where type declarations can be enforced. In addition to this, it can be made harder to pass around wrong types by forcing 2.3 Packaging modules hand-written type-conversions. An object of a generic type can be passed in, but if it results in considerable extra effort on the Modules are essentially groups of functions and ’global’ variables behalf of the programmer to do type conversions in the code, the that can only be accessed from within that environment. It is programmer might consider declaring the object of the correct an important feature in a language that hopes to stay modular type in the first place. while the software written in it grows to a sizable number of C++ does this the other way round; the language makes separate files. it particularly easy to do automatic type conversions between Packaged environments are similar to the well-known single- types, sometimes resulting in dangerous code. ton classes from c++, which are in turn again similar to global functions and variables. The disadvantage of having things global is mainly that you can only have one instance of the 2.2 Containers and iterators global state of that module. This is not a problem for modules for which there is naturally only one instance. In the c++ standard library there is a powerful notion of con- Packaged modules are usually of this form. They can be tainers and iterators. The idea is to hide how objects are stored seen as a name space, where certain symbols are defined to in a structure, and offer a generic way to access objects in a have a meaning locally. Specific symbols from a module can be store of objects. General algorithms that work on sets of data exported to another module, thus the symbol of another module can then be defined in terms of this unified interface. The ob- becomes visible in another name space. ject that gives access to an element in a container is called an As mentioned above, modules in the Lisp dialect developed iterator. The typical things needed are: here have a very simple structure; they are essentially what is usually referred to as a class, but there will be only one instan- 1. get the first object in a container tiation of each module, and modules are not ’derived’ in any 2. get the next object in a container form from other modules. Modules can export functions (or 9 more precisely, modules can import functions from other mod- This way we have back our easy access to the functionality ules) when appropriate, but this feature should be used with of adding two integers. However, we are left with cumbersome care as this easily results in re-introducing name collisions in syntax for importing this function. For this the function import the name space of a module. was defined, which makes importing a function from another Modules have their own global variables. When a function module into a module a little bit easier: from a module is invoked, it can only see its own globals, even In> (import INTEGER + AddInt) if exported to another environment. This has the following ad- Out> t vantages: In> (AddInt 2 3) 1. It enforces modularity, by disallowing modules to modify Out> 5 globals from other modules directly. Note that for this language we chose the construct of 2. It facilitates compilation to efficient code when in an namespace because we don’t want access to global variables in object-oriented environment; the module just becomes a the module. Another option would have been to allow pass- class with methods and properties, with a one-on-one re- ing an environment, or module name to eval, as in (eval lation between the functions, global variables defined in ). This would have allowed the the module, and the properties and methods defined in the programmer to pass in any expression to the environment, effec- compiled class. tively making it possible to evaluate variables in that module. We want to actively disallow that, by only allowing function When well-thought out, packages can greatly aid in making calls to that environment. The arguments to the function call a system modular, built from small sub-modules which can be are evaluated before the function defined in the module is called, added or removed. thus they are evaluated in the calling environment. To define a module, makeenv can be used. makeenv takes two Functions supporting modularization arguments, a module name and the body to execute to define globals and functions inside it. For example, we can define a The essential functions for modularization are namespace, function bar in the module foo as follows: import, makeenv and functionp. These functions will be de- scribed in this section. In> (makeenv foo (defun bar(n m) (list ’head n m))) An environment can be built up with makeenv, and defining Out> bar the functions and global variables contained therein: In> (bar 2 3) ERROR: function not defined : bar (makeenv arithmetic Out> nil (progn In> (import foo bar bar) (defun add (n m) ...) Out> t (setf pi 3.1415926535) In> (bar 2 3) ) ) Out> (head 2 3 ) In> (namespace ’foo ’bar 2 3) An expression can then be evaluated in this environment Out> (head 2 3 ) through: The function functionp allows one to check that a function is (namespace ) defined in a package. This is useful for checking that a package The ’environment’ can be thought of as a static class, a sin- name that is passed as an argument is a valid package (has gleton, in object-oriented terms. There is only one of this type the correct functions implemented). The syntax is (functionp of object, and one instance of each property in the class, which ): is why the compiler can generate a static link to it. A function In> (functionp ’std ’+) in an environment is no more than a method in such a singleton Out> nil class. In> (functionp ’INTEGER ’+) The arithmetic operations like + are actually defined in the Out> t module INTEGER for the reference implementation of the Lisp In> (import INTEGER + +) interpreter described in this book. This means that from start Out> t up, the + operator is not directly accessible. One way to access In> (functionp ’std ’+) a function in a module is to pass the name of the module as an Out> t argument to the operator namespace: The default environment (module) the application starts in, In> (+ 2 3) the one the user can access, is the name space std. Other name ERROR: function not defined : + spaces are INTEGER, Out> nil Note that INTEGER is both the name of a name space and of a In> (namespace ’INTEGER ’+ 2 3) type. This has powerful consequences: of we define a vector to Out> 5 be a vector of integers, as some structure with VECTOR INTEGER This is obviously not the most convenient syntax. One way in it, the code to add two vectors knows that the components of to encapsulate a call to a function in a module is to define a the vector can be added by using the addition operation from the function for it: INTEGER module directly, resulting in speedier code than code that would accept the components as being of type OBJECT, and In> (defun +(a b) (namespace ’INTEGER ’+ a b)) figuring out for each component that it was an integer. Out> + The system can even go as far as checking that a parametric In> (+ 2 3) type can be made by checking that certain operations are defined Out> 5 for it, through the functionp call. 10 The bigger picture functions at any depth can throw an exception, accompanied with information on what went wrong. preEval catches the The programming language does not stands on itself. It offers exception, and shows the error. a way to execute certain algorithms, through the language of- It is defendable to use exceptions, as the problem is likely fered, but also there are interfaces to the environment (usually to be invalid input to a function, and as a result invalid input the operating system). As such, from within the programming passed in by the user, and as such an environment issue that environment, there are functions that are supported that allow the code cannot be expected to treat correctly. for operating system dependent operations, like file manipula- Exceptions halt execution immediately. The preEval catches tion and using libraries commonly found on systems. it, and the user interface can continue where it left off. This As such, the programming language also offers an interface is defendable behavior. The system is only expected to do on- to operating system functionality through modules supporting line commands typed in by the user, or fail. The story would these operations. be different if Yacas were used to control some system, and it needs to keep running after failure, but it was not designed for Static versus dynamic scoping that. Yacas is a computer algebra system, not a controlling system for a Space Shuttle. Dynamic scoping is not supported implicitly. To access a func- tion or object from an environment, the environment needs to be specified explicitly. This is important because the compiler needs to be able to determine where to find the information at 2.6 Type systems compile time. The reference to the function or variable needs to Even though the Lisp interpreter discussed so far does not sup- be hard-coded at compile time. Having to look up the symbol at port typing, when we discuss compiled Lisp typing is considered, run-time would simply be an unnecessary performance penalty. and thus the subject warrants some discussion. The Lisp interpreter described so far is untyped, meaning that everything is of one type, OBJECT. What happens in fact 2.4 Default modules defined in the is that the interpreter executes functions, and these functions Lisp environment internally do conversions. When calling an arithmetic operator like +, arguments of type OBJECT are converted to NUMBER, the All modules have access to the following functions and macros addition is performed, and the result is converted back from type by default: NUMBER to OBJECT. Untyped systems are inefficient this way. quote, if, cond, setf, while, progn, defun, defmacro, assoc, The compiled Lisp dialect that will be developed will allow eval, first, rest, cons, atom, listp, list, equal, namespace, import, for typed arguments and functions; functions can only accept makeenv, functionp. arguments of a certain type, and return a result of a specific All other commands (including arithmetic commands) can be type. The typed Lisp dialect will still allow for untyped (eg. accessed through other modules. OBJECT) arguments, for the lazy programmer (but as we shall For modules representing some type, usually there should at see later, the lazy programmer is in for a few nasty surprises: least be a type function which returns t if an object is of that slower code and more typing required, as a lot of manually coded type, nil otherwise, and a function make which makes such an type conversions will need to be made). With the simple typing object given some arguments (if applicable). system we will use, no automatic type conversions will be made. They will have to be done manually. The INTEGER module The system will consist of various packages involving oper- ations on objects. For instance, there will be a package that The INTEGER module is one of the few that should be imple- performs addition on integers and real numbers, and there will mented in the interpreter, as it is probably most efficiently im- be a package that deals with addition of vectors and matrices. plemented through some library. It supports the following com- The same will hold for for instance complex numbers. The addi- mands: tion operator in the global environment will then be responsible 1. (+ n m) - addition of integers, returns integer for dispatching an addition operator to the appropriate addition operator in the appropriate environment. For instance, there 2. (- n) - negation of an integer, returns integer can be an AddIntegers operator, and an AddComplexNumbers 3. (* n m) - multiplication of integers, returns integer operator, and the invoking addition operator can first check argument types before invoking the correct operator. This is 4. (div n m) - division of integers, returns integer q for which called data-directed programming. n = qm + r, 0 ≤ r < m Complications arise when two objects of different types are 5. (mod n m) - remainder after division of integers, returns added. When adding an integer to a real number, one cannot integer r for which n = qm + r, 0 ≤ r < m use the operators for adding integers or real numbers them- 6. (gcd n m) - greatest common divisor of two integers selves. One solution for this is to first convert the integer to a real number type, and then invoke the addition of real numbers 7. (< n m) - ’less than’ operator for integers, returns boolean operator. For numeric types, this works well. Numbers can be 8. (integerp n) - returns t if n is an integer, nil otherwise put in what is called a tower of types: integers are a sub-type of 9. (type n) - returns t if n is an integer, nil otherwise. rational numbers, which are a sub-type of real numbers, which are a sub-type of complex numbers. A number can always be moved up in the tower of types. An integer is just a special case 2.5 Error handling of a complex number, for instance. So when adding an integer to a complex number, one only needs to convert from the integer Error handling is done by using exceptions. A function preEval to complex. This can be done in steps, so for n types only n-1 is the entry point for evaluating expressions, and can be called convertors are needed; IntegerToRational, RationalToReal, from the user interface part. While performing the command, etc. 11 Typing systems are not always this simple. For example, a (defun make-complex (r i) diagonal matrix is a sub-type of the generic set of all matrices, (list ’complex r i) but some diagonal matrices are also sub-types of the unitary ma- ) trices. So a matrix can have more than one super-type. Super- (defun real-part (z) (second z)) types can have multiple sub-types too. In this case, choosing (defun imag-part (z) (third z)) the right conversion is not trivial. The choice can be based on some heuristic; when doing a specific type of operation, first Then this allows for the following interaction: try to convert the matrix to a type for which there is the most In> (setf z (make-complex 2 3)) efficient algorithm for performing that action, otherwise try an- Out> z other type. In> (real-part z) It gets worse; for polynomials, x2 − y can be a multivariate Out> 2 polynomial in (x,y) with integer coefficients, or a univariate In> (imag-part z) polynomial in x with coefficients which are univariate polyno- Out> 3 mials in y, or a univariate polynomial in y with coefficients which are univariate polynomials in x. There might be cases where the We can define a predicate to check if an object is complex as: system can not decide which type to take, and the user will have (defun complexp(z) to help the system by telling what type to take. (and (listp z)(equal ’complex (first z))) Types can be down-cast to sub-types too, if possible. This ) is sometimes necessary. Suppose one has two objects of type OBJECT, as entered by the user. The user wants to perform a And with that a simple addition operation: division operation. The system can try to drop the object to the lowest possible type, by first trying to convert to integer, (defun add (x y) and if this doesn’t work, see if the objects can be converted to (cond objects of type univariate polynomial, and otherwise multivari- ( (integerp x) (+ x y) ) ate polynomial, etc. The trick is to have a routine that accepts ( (complexp x) univariate polynomials in internal representation, performs the (make-complex operation, and returns the result of the operation in internal rep- (add (real-part x) (real-part y)) resentation. When the operation is called with generic objects (add (imag-part x) (imag-part y)) as arguments, if they can be converted to internal representa- ) ) ) ) tion for univariate polynomials first, this can be done, and the which allows for the interaction: result of the operation converted back to generic object type (a form the user could have typed in). The advantage of this is In> (add (make-complex 2 3) (make-complex 4 5)) an object is converted once, when passed to a function. The Out> (complex 6 8 ) result of consecutive function calls can then use the object in the type it is already in, without having to convert types each This is an example of data-driven programming; invoking dif- time, and the final result is converted back. This way types are ferent routines for different data types. Also note we use the add only converted twice; at the beginning and at the end. operation for the components of the complex data object. This has powerful consequences: it means that a complex object can have components of arbitrary type, as long as there is an addi- 2.7 Data structures as types in tion operation defined for it in the add function. The complex data object is in effect a parametric type: (complex Lisp ), where can be anything, integers, matrices, etc. is a type parameter for this complex data type. A nice way to work with data structures is to hide them behind Types in general aid in two ways: to check for correctness of what are called constructors and selectors. For example, sup- code, and to give information to the compiler to generate more pose we need a type for complex numbers. We could make a efficient code. This also holds for parametric types. Suppose we function make-complex, which is a constructor, and real-part have a vector object. Pseudo-code for adding the two vectors and imag-part. We don’t need to discuss the internal represen- could look like this: tation of the complex number, as all we need to know is how to make one, and how to obtain all the information there is to vector add-vectors(v1,v2) know about the object. vector result = zero-vector Interestingly, often when dealing with mathematical objects, for i from 1 to degree(v1,v2) there are properties that always need to hold for such objects. result[i] := add(v1[i],v2[i]) In the case of make-complex, real-part and imag-part, for a return result complex number z, the following should always be true: Note we use the add operation here for adding the components (equal z (make-complex (real-part z) (imag-part z)))of a vector. Suppose the add operation was then defined as: Data structures are a powerful way to abstract types away. A object add(x,y) data structure can be defined for for instance rational numbers, if (object-type(x) = integer) matrices, etc. Also cons, first and rest are such a combina- return add-integers(x,y) tion, where cons is the constructor, and first and rest are the if (object-type(x) = real) selectors. The result of evaluating (cons a b) is an object for return add-reals(x,y) which first returns a, and rest returns b. if (object-type(x) = complex) Suppose we decide to represent complex numbers as (complex return add-complex(x,y) real imag). Then the following routines are constructors and if (object-type(x) = vector) selectors: return add-vectors(x,y) 12 Now the important thing to notice is that the add function is 2.8 Typing in Yacas called from within the loop of add-vectors, and if the vectors in question contain a billion items, add gets called a billion times. Type conversions are considered to be a ’policy’ which is best However, add checks the type of the object to be added each time implemented in the final Yacas system, through some strategy it is called, and it is called from the inner loop! The add-vectors for conversion. The code that does the final symbolic manip- function can be written with the add operation inlined into it: ulation can take care of converting types, as appropriate. The implementation of the simplification algorithm that defines Ya- vector add-vectors(v1,v2) cas can contain the heuristics of type conversion. vector result = zero-vector Inlining functions as described above is automatically done on for i from 1 to degree(v1,v2) macros. However, macros are slow to execute in the interpreter, if (object-type(v1[i]) = integer) so a possible feature of a compiler could be to tell it a function result[i] = add-integers(v1[i],v2[i]) can be inlined. The variable scoping rules can still hold; the if (object-type(v1[i]) = real) body should not be allowed to access variables in its calling result[i] = add-reals(v1[i],v2[i]) environment. if (object-type(v1[i]) = complex) result[i] = add-complex(v1[i],v2[i]) if (object-type(v1[i]) = vector) result[i] = add-vectors(v1[i],v2[i]) return result However, because all the type of all the vector components can be expected to be the same, this can be improved by pulling the if statements outside of the loop, so the if statements are only performed once in stead of a billion times. This is a com- mon way to optimize code, and is often done by hand. There is no reason, however, why a computer could not do this optimiza- tion. When the add operation is inlined, if the compiler knows that the if statements will yield the same results every time, it can pull them outside of the loop, as follows: vector add-vectors(v1,v2) vector result = zero-vector if (object-type(v1[i]) = integer) for i from 1 to degree(v1,v2) result[i] = add-integers(v1[i],v2[i]) if (object-type(v1[i]) = real) for i from 1 to degree(v1,v2) result[i] = add-reals(v1[i],v2[i]) if (object-type(v1[i]) = complex) for i from 1 to degree(v1,v2) result[i] = add-complex(v1[i],v2[i]) if (object-type(v1[i]) = vector) for i from 1 to degree(v1,v2) result[i] = add-vectors(v1[i],v2[i]) return result If a compiler knows beforehand that two vectors of type vector, it can devise a special function that will only work on objects of type vector, but this is already a lot less useful. The if statements have already been pulled out of the loop, so they will not be performed a billion times for an addition of two vectors both with a billion components. Parametric types can be supported naturally. A vector could be represented as (vector ), so that (vector SMALLFLOAT (1 0 0)) would be a base unit vec- tor in a three-dimensional space, with real-valued vector com- ponents. Flexibility is not lost, the type can be EXPRESSION or OBJECT or some other generic type. But it can also be (UNIPOLY INTEGER x), eg. making the vector a vector with univariate polynomials in x over the integers as components. The above considerably speeds up the operation. The prob- lem is that it is more natural to place the if statements in the add function, so it can be used in many places, when adding complex numbers, matrices, etc. But inlining it allows the com- piler to optimize the if statements away by pulling them outside of the loop. In most cases, even if not in a loop, the compiler can optimize code away if inlined, by using typing information. 13 Chapter 3 Compiling Lisp code 3.1 Introduction be executed at compile time (macros will be expanded during compilation), global variables are set, functions defined, and This section deals with compiling Lisp code to a form that runs possibly other things done while loading a file. Compilation more efficient on a real computer. will be taken to mean creating a class that gets loaded, and a The overheads of executing Lisp are: method in this class called to perform what would usually be 1. Parsing expressions when loading in a file. This is not a performed when loading the file. big performance penalty, as it only happens at startup, and The fact that compilation is reminiscent of interpretation sug- might even be slower after compilation if more needs to be gests that the strategy pattern could be used, when the compiler loaded from disk to run a compiled version of a program. is written in the target environment. For this, the default eval- uation routine or object needs to be replaced by another, one 2. When evaluating a variable, the interpreter needs to dy- that compiles in stead of interpreting. Compiling would then namically look in a list for the value of the variable. Com- reduce to loading a file, but using a different ’interpreter’ for it. piled code can be written such that it can immediately This abstraction is further warranted by the fact that a debug- access the value. ging environment is needed, one where a programmer can step 3. When evaluating a function, looking up the function to call through code. can be expensive. The function needs to be found in some Defining a function will reduce to defining a class (in an container of functions, like a hashtable, which would run object-oriented system) with an eval or apply method. The in O(log n) time, worst-case (best case O(1), when only a method gets called with a list of arguments to perform its tasks. few functions are added). In addition, routines can be created that directly perform the 4. The overhead of building lists to be passed to a function, task with the arguments given in directly in the target pro- which then needs to decompose the arguments. gramming language. This is made easier with the Lisp dialect 5. Needless operations, like conversions from string represen- described earlier because of the constraint of a fixed number of tation to internal number representation and back. arguments. 6. Inefficient execution of code that could be done more effi- ciently in native code. An if or while statement can be 3.3 Parsing the expressions into an expected to run a lot more efficient when not interpreted. The first concern will be to convert the Lisp code to source internal format code for the target platform; when the Lisp interpreter is written The first possible step is to skip parsing at runtime, by doing in Java we want the Lisp code compiled to Java, etc. it at compile time. Even though this does not give a much The disadvantage is the compiler then needs to be around greater speed at runtime, it is a requirement if the code is to be for compilation to be able to take place. Programs thus get compiled. compiled once, and then run. The compiler is not available at A form (foo a b) could be compiled to run time. As compiled code can interact with interpreted code, the user is still free to write his own functions, but they will LispObject object = have to run interpreted. cons(recSymbol("foo"), The advantage of directly compiling to source code as input cons(recSymbol("a"), for another compiler is that it is less work. However, a little cons(recSymbol("b"),nil))); compiler could be written that takes the resulting output source code and compiles it further to some other target, dynamically at run time. Theoretically, even a byte code interpreter could This expression could be assigned at construction of the object, be written, and a compiler for it, and this could be plugged into and thus built only once like the interpreter would do. the system. Equivalently, a symbol bar would be defined as: LispObject object = recSymbol("bar"); 3.2 Steps for converting to source If nothing is known about the function foo, no further sim- code plifications can be made, as it could be a macro or a function, and thus nothing is known about whether the arguments need When compiling to source code, the first step is parsing in the to be evaluated or not. code to be compiled. The compiler will have to look very similar When foo is a macro, it can be dealt with easily by directly to an interpreter; code needs to be read in, and part of it needs to expanding the code in place. When foo is defined as 14 In> (defmacro foo (a) a) LispObject a = recSymbol("2"); Out> foo LispObject b = recSymbol("3"); LispObject object = Foo.eval(a,b); Evaluation of (foo (+ 2 3)), return object; In> (foo (+ 2 3)) If foo is guaranteed to only work with numeric values for Out> (+ 2 3 ) input, we could add another method to the foo evaluator object is the same as inlining the code with a let statement: Foo, one which takes two numeric arguments: In> (let ((a (quote (+ 2 3)))) a) LispNumber a = 2; Out> (+ 2 3 ) LispNumber b = 3; LispNumber number = Foo.evalTyped(a,b); Macros have to be expanded before an expression is evaluated, return recSymbol(number); but other than that, the compiler can read in all the code before inlining macros, to be able to inline macros that are defined The interesting option for the last optimization is that all the later on. Alternatively, the actual evaluation could be cast in intermediate values are now numbers, not lisp atoms. The ad- code that looks at runtime to discover whether a function call vantage to this is that if an expression is more complex than the is actually a macro expansion, but this is less efficient at run above example, the input arguments can be converted to num- time. bers at the beginning, and then the arithmetic operations per- In the following examples, it is assumed that there are objects formed, and only at the end are these numbers converted back of type LispObject, which can hold a general Lisp expression, to atoms (through the recSymbol function explained above). So LispNumber which can hold a number, and functions eval, cons, in this case, and recSymbol. The last, recSymbol, takes some native argu- ment like a string, and converts it to a LispObject. nil is taken (let ((a 2) (b 3)) (+ (foo a b) 5)) to be an empty list. Could be converted to: Optimizing an expression can then continue in various steps. Suppose we take the definition of the call (foo a b) above, and LispNumber a = 2; that we know that foo is a function that will be compiled. Then LispNumber b = 3; we can rewrite return recSymbol(Foo.evalTyped(a,b)+5); LispObject object = A lot of conversions to and from formats can be avoided if eval( the compiler can recognize that it is appropriate. Code of this cons(recSymbol("foo"), form would not be much slower than code written natively in cons(recSymbol("a"), the target language (actually not quite true, if you have the full cons(recSymbol("b"),nil)))); language at your disposal you might be able to do optimizations return object; by hand). If functions are defined as macros, of course the compiler can as inline them and perform additional optimizations, removing the LispObject object = need for the overhead of a call. Foo.eval( A further optimization could be a conversion to native nu- cons(eval(recSymbol("a")), meric types. If the compiler knows that the result of some com- cons(eval(recSymbol("b")),nil))); putation is an integer, and it fits in a native integer (for instance return object; a 32-bit integer), the above code could become: Here the arguments are evaluated explicitly before being return recSymbol(Foo.evalTypedNative(2,3)+5); passed to foo, and foo is hard-linked, called directly with the appropriate arguments. A next step is to optimize the eval inside these expressions, 3.4 Some general rules for opti- eg. optimizing evaluation of a and b. If a and b were local mization variables from within a let statement, or arguments to a function call in its environment, this could be optimized further. Each Optimization generally entails doing as much work doing compi- declaration of a local variable can be made a real local variable lation, and as little as possible during runtime. Looking up the in the target source code. location where a local variable is stored, looking up a function, and in a macro that gets inlined determining if an if statement (let ((a 2) (b 3)) (foo a b)) or some clause to a cond statement will always return true are things the compiler can find out and ’evaluate’ at compile time, could become so it doesn’t have to be done at runtime. The compiler can optimize code based on assumptions about LispObject a = recSymbol("2"); the input. This is why compiled languages usually have typed LispObject b = recSymbol("3"); variables. This can also be solved, for specific cases, by using LispObject object = macros. Suppose one wants to multiply two matrices, (mat-mult Foo.eval(cons(a,cons(b,nil))); a b). The elements of the matrices a and b can be anything, return object; univariate polynomials, multivariate polynomials, analytic func- This skips lookup of local variables in an environment, as the tions of one variable, complex, real. But when the compiler compiler will be able to directly take the appropriate value. knows the elements of the matrices are real-valued, some opti- In the dialect described here, we only accept a fixed number mizations can be made in the body of a macro. Alternatively, of arguments, and thus we could add a method to the Foo object if a function call required for multiplying matrix elements is which accepts two arguments, and the code would change to: defined as a function, that function can be treated as a macro, 15 and a separate function compiled from it and called from within { mat-mult, to take into account the fact that it is going to be i=i+1; passed real-valued matrix elements. Having more information { about the input gives options for optimizing the code more. This printf("%d\n",i); allows algorithms to be stated at a high-level, with the compiler pred = i ) - declares a global variable. platform, and ’bootstrap’ the rest of the code into the system declare is not needed for the untyped interpreter, just for the using the compiler. The system effectively ’ports’ itself to the typed Lisp code that will be used for conversion to c++/Java new platform, by generating efficient code for that platform. or other targets. For example, one could first start with compiling some utility The typing system is very simple; no automatic type conver- functions, then compile support for parsing Yacas expressions sion is performed. In stead, the user is expected to call con- and pattern matching, and then compile more powerful script version routines. For instance, when a function sin expects a code. float, but an integer n is passed in, the calling sequence should As a first step, a simple but fast compiler can be invoked, in- ne something like (sin (int-to-float n)), and not (sin n). voking more powerful compilers each time the system has faster Some functions, like setf, will accept different types of argu- components, resulting in faster and faster code. ments (the second argument to setf should be of the type of the variable the value is assigned to). This is a very simple typing system, but this Lisp dialect 3.7 Strong typing as an option for is not meant to be really used for programming, just a basic generating optimized code minimum set. Overloading of functions and variable number of arguments are also not supported. Until now we have only discussed an untyped Lisp system, one The following native types are supported in the basic Lisp where the system doesn’t know the types of arguments passed dialect: or variables. An untyped Lisp is in principle enough for imple- 1. OBJECT - any Lisp expression menting a CAS. However, a small addition, declaration of types for parameters and variables, has a lot of advantages. 2. INTEGER - Big (arbitrary precision) integer Take a function fact 3. FLOAT - Big (arbitrary precision) float 4. STRING - text string (should be encapsulated by double (defun fact (n) quotes when entered by the user) (if (equal n 0) 1 5. STRINGBUFFER - String, but not stored in any caches or (* n (fact (+ n -1))) hash tables. Stringbuffer is meant to be used to build up ) ) strings. 6. CHAR - Array element of a string or string buffer. This is Now, if we write this as made a base type so that parsers and tokenizers can be (defun (fact INTEGER) ( (n INTEGER) ) written in the Lisp dialect itself, and efficiently compiled (if (equal n 0) to native code. Char is represented as a string with one 1 character. (* n (fact (+ n -1))) 7. HASHTABLE - fast association of one object with another. ) ) This list will be extended. Note that this just adds extra information, about types that The compiler can also be made to accept non-typed variables, should be passed in or returned. But the addition of type infor- arguments and functions. The type of these objects should then mation greatly aids in translating (compiling) to other targets. default to OBJECT. However, this does not save the user from For example, in c++ this bit of code could look like converting to appropriate type. For instance, if the type of some expression is not explicitly set to INTEGER, and it is used BigInteger fact(BigInteger n) in addition, then a call to object-to-int is required every time { the object is treated as an integer. Next to it being a nuisance if (n==0) for the programmer, it also makes the code less efficient. return 1; The compiler is of course free to ignore types when it comes to else translation. All objects should be able to pass as type OBJECT. return n*fact(n-1); The typing system is there to ensure efficiency of the generated } code. The untyped interpreter described in the beginning of 17 this book disregards all typing information whatsoever. The compiler does however have to check that arguments passed in have a valid type. By the same token, the interpreter could be modified to han- dle the typed expressions, and just ignore the typing informa- tion. The interpreter could easily be extended to ignore the typing information given: In> (defun foo-untyped (n) (+ n 2)) Out> foo-untyped In> (defun (foo-typed INTEGER) ( (n INTEGER) ) (+ n 2) ) Out> (foo-typed INTEGER ) In> (foo-untyped 3) Out> 5 In> (foo-typed 3) Out> 5 The change from to ( ) is a trivial one. But this extra information can easily be mapped to strong typed compiled languages, which is why it is a useful step. Indeed, 100 lines of Yacas (Yacas already had an interpreter at the time of writing of this document, version 1.0.53 had an interpreter written in c++) code can render the following: (defun foo (n ) (IntegerToObject (+ (ObjectToInteger n )2 ))) to LispObject foo(LispObject n) { LispObject result ; { result = IntegerToObject(ObjectToInteger(n)+2); } return result; } and (defun (foo INTEGER ) ((n INTEGER )) (+ n 2 )) to BigInteger foo(BigInteger n) { BigInteger result ; { result = n+2; } return result; } The typing information in effect gives the compiler enough information to directly convert expressions to another syntax. The compiler thus just becomes a simple expression transformer. 18 Chapter 4 Converting Yacas script code to other languages 4.1 Introduction minimum Lisp interpreter implementation can be written for other environments. This section describes an implementation of a minimal environ- The following sections describe the implementation of the ment in Common Lisp that allows execution of code originally parts described above. written in Yacas script code. Small Lisp interpreters can easily be written in any language. Being able to directly compile the interpreter into a program 4.3 Naming conventions from for instance Common Lisp or Java allows the freedom to first print the code for the reference Yacas interpreter imple- Along with the code that is converted to Lisp code, and the code mentation, and then use it in other projects later on. to do this conversion (written in Yacas code), comes a small The main aim for Yacas is to allow for mathematically- body of utility functions written in Lisp, which are required for oriented algorithms to be written easily. Being able to com- simulating Yacas in a Lisp environment. pile that code to code that can be compiled into other syntax The functions defined that offer specific functionality for Ya- gives flexibility. This effort thus also defines tha absolute bare cas interpretation are prepended with a yacas-, in order to be minimum required for such a system. able to easily recognize their origin. Common Lisp was chosen because it is sufficiently close to Functions compiled from Yacas script have yacas-script- Yacas, Yacas resembling a Lisp interpreter internally. Yacas prepended, and -arity-n appended (where n is the arity of the already comes with a parser for Yacas script code, and can function defined). easily manipulate expressions to bring them into a form suitable The lisp code is divided into the following modules: for execution in another environment. 1. yacas.lisp - the main top-level entry code. This module Not all of Yacas will be made available, just the functional loads all other modules, and implements the top-level read- subset needed for doing CAS. Other systems have their own eval-print loop. functionality for interacting with the system (file input/output 2. match.lisp - implementation of dynamic pattern match- and such). ing. 3. yacasread.lisp - implementation of the parser. 4.2 Relevant parts of the system 4. yacaseval.lisp - implementation of the Yacas evaluation scheme. The minimum set up consists of: 5. yacasprint.lisp - implementation of the infix pretty printer. 1. A parser. Although not highly necessary, the author feels the Yacas syntax is a comfortable one. One reference im- 6. yacassupport.lisp - various other utility routines, defin- plementation can be written in the mini sub-set of Lisp ing a small API that can be called from Yacas code or the that will be used. command line. 2. A compiler for converting from Yacas script to Common Lisp evaluable expressions and functions. 4.4 Functions used from the Com- 3. Various small utility functions written in a small sub-set of Lisp, to offer functionality required for executing Ya- mon Lisp environment cas script at run time. Pattern matching functionality for The conversion to Common Lisp uses a small sub-set of what instance can be implemented easily in Lisp code itself. Common Lisp offers, or worded differently, it only needs a small 4. if necessary, a custom eval operation to alter the default subset in order to be implemented. Better optimized versions evaluation behavior. For instance, in Common Lisp, when can be made specifically for Common Lisp, but the exercise is a function or variable is not bound, the system raises an to define a minimum required set of features. error, whereas Yacas returns the expression unevaluated. The following is used from Common Lisp: Thus this project takes a minimum subset of Common Lisp to 1. the T and NIL atoms, where NIL is the empty list but also implement a minimum environment for running code originally designates ’false’ when used in a predicate. Anything other written in Yacas script. In practice this system could then than NIL is considered to represent ’true’. also be used in other Lisp dialects like Scheme or elisp, or a 2. defun, cond, equal, atom, eval, and, bound, listp, first, rest 19 4.5 The read-eval-print loop Yacas can be invoked from within the Common Lisp shell by typing (yacas). This starts the normal read-eval-print loop, parsing Yacas syntax, converting it to internal format, evalu- ating it, and lastly printing the result on screen in the same infix syntax used for input. Note that in theory both read and print can be replaced by something else, or not implemented at all (then the standard Lisp print and read can be used. The functions to perform these tasks are yacas-read, yacas-eval and yacas-print. 4.6 Making the Yacas parser avail- able The parser acts as a front-end to Yacas functionality, convert- ing infix notation more commonly used by humans for writing down mathematical expressions into an internal representation. For Lisp the representation is fixed: linked lists of atoms. 4.7 Compiling functions to native Lisp syntax The pattern matcher 4.8 The custom evaluator Part of the language lies in how expressions get evaluated, after they have been converted to internal format, taking an input expression and returning some result after performing an oper- ation on the expression commonly referred to as evaluation. There are slight differences between the way Common Lisp evaluates and the way Yacas expressions should be evaluated, necessitating a bit of code between the two. In Yacas, when a function is not defined or a variable not bound to a value, the expression in question is returned uneval- uated (actually, in the case of a function call, its arguments are evaluated). Since interpreting a Lisp program is just an algorithm, and any algorithm can be implemented in Lisp, one could write a Lisp interpreter in Lisp itself. In fact, it is very simple to do so. This section describes an example Lisp interpreter written in Lisp itself. It will be used in the end to implement an interpreter for Yacas code. The advantage of directly compiling to native code (c++/Java) is clear; one stands a chance of writing a Lisp in- terpreter in Lisp itself, and have it be as efficient as the internal interpreter itself (if the compiler is good enough). The inter- preting code just needs to be compiled by a good compiler. 4.9 The system in action Example output code generated by the com- piler 20 Chapter 5 GNU Free Documentation License Version 1.1, March 2000 The “Invariant Sections” are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, Copyright (C) 2000 Free Software Foundation, Inc. in the notice that says that the Document is released under this 59 Temple Place, Suite 330 License. Boston, MA, 02111-1307 The “Cover Texts” are certain short passages of text that are USA listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. Everyone is permitted to copy and distribute verbatim copies A “Transparent” copy of the Document means a machine- of this license document, but changing it is not allowed. readable copy, represented in a format whose specification is available to the general public, whose contents can be viewed Preamble and edited directly and straightforwardly with generic text ed- itors or (for images composed of pixels) generic paint programs The purpose of this License is to make a manual, textbook, or (for drawings) some widely available drawing editor, and that or other written document “free” in the sense of freedom: to is suitable for input to text formatters or for automatic transla- assure everyone the effective freedom to copy and redistribute tion to a variety of formats suitable for input to text formatters. it, with or without modifying it, either commercially or non- A copy made in an otherwise Transparent file format whose commercially. Secondarily, this License preserves for the author markup has been designed to thwart or discourage subsequent and publisher a way to get credit for their work, while not being modification by readers is not Transparent. A copy that is not considered responsible for modifications made by others. “Transparent” is called “Opaque”. This License is a kind of “copyleft”, which means that deriva- tive works of the document must themselves be free in the same Examples of suitable formats for Transparent copies include sense. It complements the GNU General Public License, which plain ASCII without markup, Texinfo input format, LaTeX in- is a copyleft license designed for free software. put format, SGML or XML using a publicly available DTD, and We have designed this License in order to use it for man- standard-conforming simple HTML designed for human modi- uals for free software, because free software needs free docu- fication. Opaque formats include PostScript, PDF, proprietary mentation: a free program should come with manuals providing formats that can be read and edited only by proprietary word the same freedoms that the software does. But this License is processors, SGML or XML for which the DTD and/or process- not limited to software manuals; it can be used for any textual ing tools are not generally available, and the machine-generated work, regardless of subject matter or whether it is published HTML produced by some word processors for output purposes as a printed book. We recommend this License principally for only. works whose purpose is instruction or reference. The “Title Page” means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For Applicability and Definitions works in formats which do not have any title page as such, “Title This License applies to any manual or other work that contains a Page” means the text near the most prominent appearance of notice placed by the copyright holder saying it can be distributed the work’s title, preceding the beginning of the body of the text. under the terms of this License. The “Document”, below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as “you”. Verbatim Copying A “Modified Version” of the Document means any work con- taining the Document or a portion of it, either copied verbatim, You may copy and distribute the Document in any medium, or with modifications and/or translated into another language. either commercially or noncommercially, provided that this Li- A “Secondary Section” is a named appendix or a front-matter cense, the copyright notices, and the license notice saying this section of the Document that deals exclusively with the rela- License applies to the Document are reproduced in all copies, tionship of the publishers or authors of the Document to the and that you add no other conditions whatsoever to those of Document’s overall subject (or to related matters) and contains this License. You may not use technical measures to obstruct nothing that could fall directly within that overall subject. (For or control the reading or further copying of the copies you make example, if the Document is in part a textbook of mathematics, or distribute. However, you may accept compensation in ex- a Secondary Section may not explain any mathematics.) The change for copies. If you distribute a large enough number of relationship could be a matter of historical connection with the copies you must also follow the conditions in section 3. subject or with related matters, or of legal, commercial, philo- You may also lend copies, under the same conditions stated sophical, ethical or political position regarding them. above, and you may publicly display copies. 21 Copying in Quantity Version under the terms of this License, in the form shown in the Addendum below. If you publish printed copies of the Document numbering more than 100, and the Document’s license notice requires Cover 7. Preserve in that license notice the full lists of Invariant Texts, you must enclose the copies in covers that carry, clearly Sections and required Cover Texts given in the Document’s and legibly, all these Cover Texts: Front-Cover Texts on the license notice. front cover, and Back-Cover Texts on the back cover. Both cov- 8. Include an unaltered copy of this License. ers must also clearly and legibly identify you as the publisher 9. Preserve the section entitled “History”, and its title, and of these copies. The front cover must present the full title with add to it an item stating at least the title, year, new au- all words of the title equally prominent and visible. You may thors, and publisher of the Modified Version as given on add other material on the covers in addition. Copying with the Title Page. If there is no section entitled “History” in changes limited to the covers, as long as they preserve the title the Document, create one stating the title, year, authors, of the Document and satisfy these conditions, can be treated as and publisher of the Document as given on its Title Page, verbatim copying in other respects. then add an item describing the Modified Version as stated If the required texts for either cover are too voluminous to in the previous sentence. fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto ad- 10. Preserve the network location, if any, given in the Docu- jacent pages. ment for public access to a Transparent copy of the Docu- If you publish or distribute Opaque copies of the Docu- ment, and likewise the network locations given in the Doc- ment numbering more than 100, you must either include a ument for previous versions it was based on. These may be machine-readable Transparent copy along with each Opaque placed in the “History” section. You may omit a network copy, or state in or with each Opaque copy a publicly-accessible location for a work that was published at least four years computer-network location containing a complete Transparent before the Document itself, or if the original publisher of copy of the Document, free of added material, which the gen- the version it refers to gives permission. eral network-using public has access to download anonymously 11. In any section entitled “Acknowledgements” or “Dedica- at no charge using public-standard network protocols. If you tions”, preserve the section’s title, and preserve in the sec- use the latter option, you must take reasonably prudent steps, tion all the substance and tone of each of the contributor when you begin distribution of Opaque copies in quantity, to acknowledgements and/or dedications given therein. ensure that this Transparent copy will remain thus accessible at 12. Preserve all the Invariant Sections of the Document, unal- the stated location until at least one year after the last time you tered in their text and in their titles. Section numbers or distribute an Opaque copy (directly or through your agents or the equivalent are not considered part of the section titles. retailers) of that edition to the public. 13. Delete any section entitled “Endorsements”. Such a section It is requested, but not required, that you contact the authors may not be included in the Modified Version. of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated 14. Do not retitle any existing section as “Endorsements” or version of the Document. to conflict in title with any Invariant Section. If the Modified Version includes new front-matter sections or Modifications appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option You may copy and distribute a Modified Version of the Docu- designate some or all of these sections as invariant. To do this, ment under the conditions of sections 2 and 3 above, provided add their titles to the list of Invariant Sections in the Modified that you release the Modified Version under precisely this Li- Version’s license notice. These titles must be distinct from any cense, with the Modified Version filling the role of the Docu- other section titles. ment, thus licensing distribution and modification of the Modi- You may add a section entitled “Endorsements”, provided it fied Version to whoever possesses a copy of it. In addition, you contains nothing but endorsements of your Modified Version by must do these things in the Modified Version: various parties – for example, statements of peer review or that 1. Use in the Title Page (and on the covers, if any) a title the text has been approved by an organization as the authori- distinct from that of the Document, and from those of pre- tative definition of a standard. vious versions (which should, if there were any, be listed You may add a passage of up to five words as a Front-Cover in the History section of the Document). You may use the Text, and a passage of up to 25 words as a Back-Cover Text, to same title as a previous version if the original publisher of the end of the list of Cover Texts in the Modified Version. Only that version gives permission. one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one 2. List on the Title Page, as authors, one or more persons or entity. If the Document already includes a cover text for the entities responsible for authorship of the modifications in same cover, previously added by you or by arrangement made the Modified Version, together with at least five of the prin- by the same entity you are acting on behalf of, you may not add cipal authors of the Document (all of its principal authors, another; but you may replace the old one, on explicit permission if it has less than five). from the previous publisher that added the old one. 3. State on the Title page the name of the publisher of the The author(s) and publisher(s) of the Document do not by Modified Version, as the publisher. this License give permission to use their names for publicity for 4. Preserve all the copyright notices of the Document. or to assert or imply endorsement of any Modified Version. 5. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices. Combining Documents 6. Include, immediately after the copyright notices, a license You may combine the Document with other documents released notice giving the public permission to use the Modified under this License, under the terms defined in section 4 above 22 for modified versions, provided that you include in the combina- Termination tion all of the Invariant Sections of all of the original documents, You may not copy, modify, sublicense, or distribute the Docu- unmodified, and list them all as Invariant Sections of your com- ment except as expressly provided for under this License. Any bined work in its license notice. other attempt to copy, modify, sublicense or distribute the Doc- The combined work need only contain one copy of this Li- ument is void, and will automatically terminate your rights un- cense, and multiple identical Invariant Sections may be replaced der this License. However, parties who have received copies, or with a single copy. If there are multiple Invariant Sections with rights, from you under this License will not have their licenses the same name but different contents, make the title of each terminated so long as such parties remain in full compliance. such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to Future Revisions of This License the section titles in the list of Invariant Sections in the license The Free Software Foundation may publish new, revised versions notice of the combined work. of the GNU Free Documentation License from time to time. In the combination, you must combine any sections entitled Such new versions will be similar in spirit to the present version, “History” in the various original documents, forming one sec- but may differ in detail to address new problems or concerns. tion entitled “History”; likewise combine any sections entitled See http://www.gnu.org/copyleft/. “Acknowledgements”, and any sections entitled “Dedications”. Each version of the License is given a distinguishing version You must delete all sections entitled “Endorsements.” number. If the Document specifies that a particular numbered version of this License “or any later version” applies to it, you have the option of following the terms and conditions either Collections of Documents of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If You may make a collection consisting of the Document and other the Document does not specify a version number of this License, documents released under this License, and replace the individ- you may choose any version ever published (not as a draft) by ual copies of this License in the various documents with a single the Free Software Foundation. copy that is included in the collection, provided that you fol- low the rules of this License for verbatim copying of each of the documents in all other respects. ADDENDUM: How to use this License for You may extract a single document from such a collection, your documents and distribute it individually under this License, provided you To use this License in a document you have written, include insert a copy of this License into the extracted document, and a copy of the License in the document and put the following follow this License in all other respects regarding verbatim copy- copyright and license notices just after the title page: ing of that document. Copyright (C) YEAR YOUR NAME. Permission is granted to copy, distribute and/or modify this Aggregation With Independent Works document under the terms of the GNU Free Documentation License, Version 1.1 or any later A compilation of the Document or its derivatives with other version published by the Free Software Foundation; separate and independent documents or works, in or on a volume with the Invariant Sections being LIST THEIR of a storage or distribution medium, does not as a whole count TITLES, with the Front-Cover Texts being LIST, and as a Modified Version of the Document, provided no compilation with the Back-Cover Texts being LIST. A copy of copyright is claimed for the compilation. Such a compilation is the license is included in the section entitled called an “aggregate”, and this License does not apply to the ‘‘GNU Free Documentation License’’. other self-contained works thus compiled with the Document, on account of their being thus compiled, if they are not themselves If you have no Invariant Sections, write “with no Invariant derivative works of the Document. Sections” instead of saying which ones are invariant. If you have If the Cover Text requirement of section 3 is applicable to no Front-Cover Texts, write “no Front-Cover Texts” instead of these copies of the Document, then if the Document is less “Front-Cover Texts being LIST”; likewise for Back-Cover Texts. than one quarter of the entire aggregate, the Document’s Cover If your document contains nontrivial examples of program Texts may be placed on covers that surround only the Doc- code, we recommend releasing these examples in parallel under ument within the aggregate. Otherwise they must appear on your choice of free software license, such as the GNU General covers around the whole aggregate. Public License, to permit their use in free software. Translation Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of sec- tion 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addi- tion to the original versions of these Invariant Sections. You may include a translation of this License provided that you also include the original English version of this License. In case of a disagreement between the translation and the original English version of this License, the original English version will prevail. 23