Significance of the Study
Prolog – Logic Programming
– Based on Predicate Logic –
Working with predicates –
Computation is reasoning, initiated by a query
– Popular in natural language processing
• LISP – Functional Programming – Based on Lambda Calculus
– Working with functions
– Computation is evaluation
– Used in Artificial Intelligence –
Theory based on Lambda Calculus by Alonzo Church (1930) – l-calculus: theory of functions as formulas – Easier manipulation of functions using expressions
LISP interpreter: An interactive environment, always evaluating input
The heart of the Lisp interpreter is the “read-eval-print” loop. That is, the interpreter does the following three jobs over and over:
- read an input expression
- evaluate the expression
- print the results
This loop can be written in Lisp itself very simply:
(loop (print (eval (read)))
Of course, this doesn’t take into account error handling, multiple values, and so on, but much of what Lisp does, including some things that seem unintuitive, can be understood by reasoning about the above three step process.
The Lisp Reader
The input to the Lisp reader is a sequence of characters. The output is a Lisp expression. The job of the reader is to convert objects in character world to objects in expression world.
In character world, there are no pointers, no lists, no symbols, just characters like A, b, `, and (. That is, (A B (C D) E) is not a list, it is a sequence of parentheses, spaces, and letters. “abc” is not a string, it is a sequence of letters.
In expression world, there are no parentheses, no spaces, no quote marks, just atoms and lists. That is, (A B (C D) E) has no parentheses or spaces. It is a list of three atoms and a list. “abc” has no quote marks. It is a string with three characters.
The Common Lisp reader is quite complex (Steele has a full description), but it works roughly like this:
- If the reader sees a character with read-macro function, it calls that function, and returns whatever expression that function returns. For example, ‘ has a pre-defined read-macro function that basically says (list (quote quote) (read)). Thus, ‘abc becomes (quote abc).
- If the reader sees a “, it collects characters until it sees another “, and creates a string object with the characters found between the string quotes. Thus, the 5 characters “abc” become the 3-character string with the characters a, b, and c.
- If the reader sees a digit (0 – 9), it collects the digits that follow, and creates the number those digits represent (base 10). Thus, the three characters 123 become the single number 123.
- If the reader sees an alphabetic character, it collects characters until it sees a space or parenthesis, and then gets the symbol (using Lisp’s intern function) that has those characters (converted to upper case) as its name. Thus the three characters abc become the single unique symbol ABC.
- If the reader sees a left parenthesis, it reads more characters, turning them into expressions, using all these rules, until it sees a right parenthesis. Then it returns the list of expressions read. Thus, the 7 characters (A B C) become the 3 element list (A B C).
The Lisp Evaluator
The Lisp evaluator takes an expression and returns an expression. The expression returned is called the value of the expression evaluated. [I’ll ignore expressions that return multiple values here.]
The rules for evaluation are surprisingly simple. Graphically, it looks like this:
First, there are two rules for atoms:
- The value of a symbol is looked up in the current lexical environments. If none is found, symbol-value is called. If that fails, there’s an error (unbound variable).
- The value of any other kind of atom is the atom itself.
There are three rules for lists that start with a symbol. If they don’t work, there’s an error. The rules are:
- If the symbol names a special function, use the rules for evaluation stored with the special function.
- If the symbol has a macro function attached, apply the macro function to the rest of the list, and evaluate the result.
- If the symbol has a normal function attached, evaluate the other elements in the list, and apply the function to a list of the values returned. The value the function returns is the final value.
There is one other case for lists, but it appears rarely in modern code:
- If the list has the form ((lambda (vars) exps) args), then evaluate the arguments, and apply the lambda function to the list of results. The value the lambda returns is the final value.
Anything that can be done with a lambda can also be done with either let or destructuring-bind.
The Lisp Printer
The input to the Lisp printer is a Lisp expression. The output is a sequence of characters. The job of the printer is to convert objects in expression world to objects in character world.
The printer’s rules are pretty simple. They all involve taking an expression and printing a sequence of characters:
- If the expression is an string, print “ then the characters in the string, then another “.
- If the expression is a symbol, print the characters in the symbol’s name.
- If the expression is a number, print the digits representing that numbers (base 10).
- If the expression is a list, print a left parenthesis, then print each element in the list, with a space after each element but the last, then print a right parenthesis.
There are also rules for printing structures, special characters, and so on.
The purpose of the above rules is to make the following as true as possible:
(equal exp (read-from-string (write-to-string exp)))
Often, however, that is not what we want. For example, we probably want the string “Pick an option:” to appear on the screen as
Pick an option:
not
“Pick an option:”
The latter is correct in so far as, if Lisp read it, it would see a string, but we want people to read this message, not Lisp.
Use functions like write-string, princ, and the ~A format command to print things “for people” rather than for Lisp. However, don’t use these functions for printing debugging information. The information these functions hide for readability may be exactly what you need for debugging.
Closures
Closure-Oriented Programming
One of the conclusions that we reached was that the “object” need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele on the design of Scheme
Sometimes it’s called a closure, other times a saved lexical environment. Or, as some of us like to say, let over lambda. Whatever terminology you use, mastering this concept of a closure is the first step to becoming a professional lisp programmer. In fact, this skill is vital for the proper use of many modern programming languages, even ones that don’t explicitly contain let or lambda, such as Perl or Javascript.
Closures are one of those few curious concepts that are paradoxically difficult because they are so simple. Once a programmer becomes used to a complex solution to a problem, simple solutions to the same problem feel incomplete and uncomfortable. But, as we will soon see, closures can be a simpler, more direct solution to the problem of how to organise data and code than objects. Even more important than their simplicity, closures represent a better abstraction to use when constructing macros—the topic of this book.
The fact that we can build objects and classes with our closure primitives doesn’t mean that object systems are useless to lisp programmers. Far from it. In fact, COMMON LISP includes one of the most powerful object systems ever devised: CLOS, the COMMON LISP Object System. Although I am very impressed with the flexibility and features of CLOS, I seldom find a need to use its more advanced features1, thanks to assignable value cells and good old lambda expressions.
Environments and Extent
What Steele means by assignable value cells is an environment for storing pointers to data where the environment is subject to something called indefinite extent. This is a fancy way of saying that we can continue to refer to such an environment at any time in the future. Once we allocate this environment, it and its references are there to stay as long as we need them. Consider this C function:
#include <stdlib.h>
int *environment_with_indefinite_extent(int input) {
int *a = malloc(sizeof(int));
*a = input;
return a;
}
After we call this function and receive the pointer it returns, we can continue to refer to the allocated memory indefinitely. In C, new environments are created when invoking a function, but C programmers know to malloc() the required memory when returning it for use outside the function.
By contrast, the example below is flawed. C programmers consider a to be automatically collected when the function returns because the environment is allocated on the stack. In other words, according to lisp programmers, a is allocated with temporary extent.
int *environment_with_temporary_extent(int input) {
int a = input;
return &a;
}
The difference between C environments and lisp environments is that unless you explicitly tell lisp otherwise it always assumes you mean to use indefinite extent. In other words, lisp always assumes you mean to call malloc() as above. It can be argued that this is inherently less efficient than using temporary extent, but the benefits almost always exceed the marginal performance costs. What’s more, lisp can often determine when data can safely be allocated on the stack and will do so automatically. You can even use declarations to tell lisp to do this explicitly.
But because of lisp’s dynamic nature, it doesn’t have explicit pointer values or types like C. This can be confusing if you, as a C programmer, are used to casting pointers and values to indicate types. Lisp thinks about all this slightly differently. In lisp, a handy mantra is the following:
Variables don’t have types. Only values have types.
Still, we have to return something to hold pointers. In lisp there are many data structures that can store pointers. One of the most favoured by lisp programmers is a simple structure: the cons cell. Each cons cell holds exactly two pointers, affectionately called car and cdr. When environment-with-indefinite-extent is invoked, a cons cell will be returned with the car pointing to whatever was passed as input and the cdr pointing to nil. And, most importantly, this cons cell (and with it the pointer to input) has indefinite extent so we can continue to refer to it as long as we need to:
(defun environment-with-indefinite-extent (input)
(cons input nil))
The efficiency disadvantages of indefinite extent are approaching irrelevance as the state of the art in lisp compilation technology improves. Environments and extent are closely related to closures and more will be said about them throughout this chapter.
Lexical and Dynamic Scope
The technical term for where to consider a variable reference valid is scope. The most common type of scope in modern languages is called lexical scope. When a fragment of code is surrounded by the lexical binding of a variable, that variable is said to be in the lexical scope of the binding. The let form, which is one of the most common ways to create bindings, can introduce these lexically scoped variables:
* (let ((x 2))
x)
2
The x inside the body of the let form was accessed through lexical scope. Similarly, arguments to functions defined by lambda or defun are also lexically bound variables inside the text of the function definition. Lexical variables are variables that can only be accessed by code appearing inside the context of, for instance, the above let form. Because lexical scoping is such an intuitive way to limit the scope of access to a variable, it can appear to be the only way. Are there any other possibilities for scoping?
As useful as the combination of indefinite extent and lexical scoping turns out to be, it has until recently not been used to its fullest extent in mainstream programming languages. The first implementation was by Steve Russell for Lisp 1.5[HISTORY-OF-LISP] and was subsequently designed directly into languages like Algol-60, Scheme, and COMMON LISP. Despite this long and fruitful history, the numerous advantages of lexical scoping are only slowly being taken up by many Blubs.
Although the scoping methods provided by C-like languages are limited, C programmers need to program across different environments too. To do so, they often use an imprecisely defined scoping known as pointer scope. Pointer scope is famous for its difficulty to debug, numerous security risks, and, somewhat artificially, its efficiency. The idea behind pointer scoping is to define a domain specific language for controlling the registers and memory of a Von Neumman machine similar to most modern CPUs[PAIP-PIX], then to use this language to access and manipulate data-structures with fairly direct commands to the CPU running the program. Pointer scoping was necessary for performance reasons before decent lisp compilers were invented but is now regarded as a problem with, rather than a feature of, modern programming languages.
Even though lisp programmers seldom think in terms of pointers, the understanding of pointer scoping is very valuable in the construction of efficient lisp code.
#include <stdio.h>
void pointer_scope_test() {
int a;
scanf(“%d”, &a);
}
In the above function we use the C & operator to give the actual address in memory of our local variable a to the scanf function so it knows where to write the data it scans. Lexical scoping in lisp forbids us from implementing this directly. In lisp, we would likely pass an anonymous function to a hypothetical lisp scanf function, allowing it to set our lexical variable a even though scanf is defined outside our lexical scope:
(let (a)
(scanf “%d” (lambda (v) (setf a v))))
Lexical scope is the enabling feature for closures. In fact, closures are so related to this concept of lexical scope that they are often referred to more specifically as lexical closures to distinguish them from other types of closures. Unless otherwise noted, all closures in this book are lexical.
In addition to lexical scope, COMMON LISP provides dynamic scope. This is lisp slang for the combination of temporary extent and global scope. Dynamic scoping is a type of scoping that is unique to lisp in that it offers a very different behaviour but shares an identical syntax with lexical scope. In COMMON LISP we deliberately choose to call attention to variables accessed with dynamic scope by calling them special variables. These special variables can be defined with defvar. Some programmers follow a convention of prefixing and postfixing special variable names with asterisks, like *temp-special*. This is called the earmuff convention.
Special variable declarations look like this:
(defvar temp-special)
When defined like this, temp-special will be designated special2 but will not be initialised with a value. In this state, a special variable is said to be unbound. Only special variables can be unbound—lexical variables are always bound and thus always have values. Another way of thinking of this is that by default all symbols represent lexically unbound variables. Just as with lexical variables, we can assign a value to special variables with setq or setf. Some lisps, like Scheme, do not have dynamic scope. Others, like EuLisp[SMALL-PIECES-P46], use different syntax for accessing lexical versus special variables. But in COMMON LISP the syntax is shared. Many lispers consider this a feature. Here we assign a value to our special variable temp-special:
(setq temp-special 1)
So far, this special variable doesn’t seem that special. It seems to be just another variable, bound in some sort of global namespace. This is because we have only bound it once—its default special global binding. Special variables are most interesting when they are re-bound, or shadowed, by new environments. If we define a function that simply evaluates and returns temp-special:
(defun temp-special-returner ()
temp-special)
This function can be used to examine the value that lisp evaluates temp-special to be at the moment in time when it was called:
* (temp-special-returner)
1
This is sometimes referred to as evaluating the form in a null lexical environment. The null lexical environment obviously doesn’t contain any lexical bindings. Here the value of temp-special returned is that of its global special value, 1. But if we evaluate it in a non-null lexical environment—one that contains a binding for our special variable—the specialness of temp-special reveals itself3:
* (let ((temp-special 2))
(temp-special-returner))
2
Notice that the value 2 was returned, meaning that the temp-special value was taken from our let environment, not its global special value. If this still does not seem interesting, see how this cannot be done in most other conventional programming languages as exemplified by this piece of Blub pseudo-code:
int global_var = 0;
function whatever() {
int global_var = 1;
do_stuff_that_uses_global_var();
}
function do_stuff_that_uses_global_var() {
// global_var is 0
}
While the memory locations or register assignments for lexical bindings are known at compile-time4, special variable bindings are determined at run-time—in a sense. Thanks to a clever trick, special variables aren’t as inefficient as they seem. A special variable actually always does refer to the same location in memory. When you use let to bind a special variable, you are actually compiling in code that will store a copy of the variable, over-write the memory location with a new value, evaluate the forms in the let body, and, finally, restore the original value from the copy.
Special variables are perpetually associated with the symbol used to name them. The location in memory referred to by a special variable is called the symbol-value cell of a symbol. This is in direct contrast to lexical variables. Lexical variables are only indicated with symbols at compile-time. Because lexical variables can only be accessed from inside the lexical scope of their bindings, the compiler has no reason to even remember the symbols that were used to reference lexical variables so it will remove them from compiled code.
Although COMMON LISP does offer the invaluable feature of dynamic scope, lexical variables are the most common. Dynamic scoping used to be a defining feature of lisp but has, since COMMON LISP, been almost completely replaced by lexical scope. Since lexical scoping enables things like lexical closures (which we examine shortly), as well as more effective compiler optimisations, the superseding of dynamic scope is mostly seen as a good thing. However, the designers of COMMON LISP have left us a very transparent window into the world of dynamic scoping, now acknowledged for what it really is: special.
Let It Be Lambda
Let is a lisp special form for creating an environment with names (bindings) initialised to the results of evaluating corresponding forms. These names are available to the code inside the let body while its forms are evaluated consecutively, returning the result of the final form. Although what let does is unambiguous, how it does it is deliberately left unspecified. What let does is separated from how it does it. Somehow, let needs to provide a data structure for storing pointers to values.
Cons cells are undeniably useful for holding pointers, as we saw above, but there are numerous structures that can be used. One of the best ways to store pointers in lisp is to let lisp take care of it for you with the let form. With let you only have to name (bind) these pointers and lisp will figure out how best to store them for you. Sometimes we can help the compiler make this more efficient by giving it extra bits of information in the form of declarations:
(defun register-allocated-fixnum ()
(declare (optimize (speed 3) (safety 0)))
(let ((acc 0))
(loop for i from 1 to 100 do
(incf (the fixnum acc)
(the fixnum i)))
acc))
For example, in register-allocated-fixnum we provide some hints to the compiler that allow it to sum the integers from 1 to 100 very efficiently. When compiled, this function will allocate the data in registers, eliminating the need for pointers altogether. Even though it seems we’ve asked lisp to create an indefinite extent environment to hold acc and i, a lisp compiler will be able to optimise this function by storing the values solely in CPU registers. The result might be this machine code:
; 090CEB52: 31C9 XOR ECX, ECX
; 54: B804000000 MOV EAX, 4
; 59: EB05 JMP L1
; 5B: L0: 01C1 ADD ECX, EAX
; 5D: 83C004 ADD EAX, 4
; 60: L1: 3D90010000 CMP EAX, 400
; 65: 7EF4 JLE L0
Notice that 4 represents 1 and 400 represents 100 because fixnums are shifted by two bits in compiled code. This has to do with tagging, a way to pretend that something is a pointer but actually store data inside it. Our lisp compiler’s tagging scheme has the nice benefit that no shifting needs to occur to index word aligned memory
But if lisp determines that you might want to refer to this environment later on it will have to use something less transient than a register. A common structure for storing pointers in environments is an array. If each environment has an array and all the variable references enclosed in that environment are just references into this array, we have an efficient environment with potentially indefinite extent.
As mentioned above, let will return the evaluation of the last form in its body. This is common for many lisp special forms and macros, so common that this pattern is often referred to as an implicit progn due to the progn special form designed to do nothing but this5. Sometimes the most valuable thing to have a let form return is an anonymous function which takes advantage of the lexical environment supplied by the let form. To create these functions in lisp we use lambda.
Lambda is a simple concept that can be intimidating because of its flexibility and importance. The lambda from lisp and scheme owes its roots to Alonzo Church’s logic system but has evolved and adapted into its altogether own lisp specification. Lambda is a concise way to repeatably assign temporary names (bindings) to values for a specific lexical context and underlies lisp’s concept of a function. A lisp function is very different from the mathematical function description that Church had in mind. This is because lambda has evolved as a powerful, practical tool at the hands of generations of lispers, stretching and extending it much further than early logicians could have foreseen.
Despite the reverence lisp programmers have for lambda, there is nothing inherently special about the notation. As we will see, lambda is just one of many possible ways to express this sort of variable naming. In particular, we will see that macros allow us to customise the renaming of variables in ways that are effectively impossible in other programming languages. But after exploring this, we will return to lambda and discover that it is very close to the optimal notation for expressing such naming. This is no accident. Church, as dated and irrelevant as he might seem to our modern programming environment, really was on to something. His mathematical notation, along with its numerous enhancements in the hands of generations of lisp professionals, has evolved into a flexible, general tool6.
Lambda is so useful that, like many of lisp’s features, most modern languages are beginning to import the idea from lisp into their own systems. Some language designers feel that lambda is too lengthy, instead using fn or some other abbreviation. On the other hand, some regard lambda as a concept so fundamental that obscuring it with a lesser name is next to heresy. In this book, although we will describe and explore many variations on lambda, we happily call it lambda, just as generations of lisp programmers before us.
But what is lisp’s lambda? First off, as with all names in lisp, lambda is a symbol. We can quote it, compare it, and store it in lists. Lambda only has a special meaning when it appears as the first element of a list. When it appears there, the list is referred to as a lambda form or as a function designator. But this form is not a function. This form is a list data structure that can be converted into a function using the function special form:
* (function ‘(lambda (x) (+ 1 x)))
#<Interpreted Function>
COMMON LISP provides us a convenience shortcut for this with the #’ (sharp-quote) read macro. Instead of writing function as above, for the same effect we can take advantage of this shortcut:
* #'(lambda (x) (+ 1 x))
#<Interpreted Function>
As a further convenience feature, lambda is also defined as a macro that expands into a call to the function special form above. The COMMON LISP ANSI standard requires[ANSI-CL-ISO-COMPATIBILITY] a lambda macro defined like so:
(defmacro lambda (&whole form &rest body)
(declare (ignore body))
`#’,form)
Ignore the ignore declaration for now7. This macro is just a simple way to automatically apply the function special form to your function designators. This macro allows us to evaluate function designators to create functions because they are expanded into sharp-quoted forms:
* (lambda (x) (+ 1 x))
#<Interpreted Function>
There are few good reasons to prefix your lambda forms with #’ thanks to the lambda macro. Because this book makes no effort to support pre-ANSI COMMON LISP environments, backwards compatibility reasons are easily rejected. But what about stylistic objections? Paul Graham, in ANSI COMMON LISP[GRAHAM-ANSI-CL], considers this macro, along with its brevity benefits, a “specious sort of elegance at best”. Graham’s objection seems to be that since you still need to sharp-quote functions referenced by symbols, the system seems asymmetric. However, I believe that not sharp-quoting lambda forms is actually a stylistic improvement because it highlights the asymmetry that exists in the second namespace specification. Using sharp-quote for symbols is for referring to the second namespace, whereas functions created by lambda forms are, of course, nameless.
Without even invoking the lambda macro, we can use lambda forms as the first argument in a function call. Just like when a symbol is found in this position and lisp assumes we are referencing the symbol-function cell of the symbol, if a lambda form is found, it is assumed to represent an anonymous function:
* ((lambda (x) (+ 1 x)) 2)
But note that just as you can’t call a function to dynamically return the symbol to be used in a regular function call, you can’t call a function to return a lambda form in the function position. For both of these tasks, use either funcall or apply.
A benefit of lambda expressions that is largely foreign to functions in C and other languages is that lisp compilers can often optimise them out of existence completely. For example, although compiler-test looks like it applies an increment function to the number 2 and returns the result, a decent compiler will be smart enough to know that this function always returns the value 3 and will simply return that number directly, invoking no functions in the process. This is called lambda folding:
(defun compiler-test ()
(funcall
(lambda (x) (+ 1 x))
2))
An important efficiency observation is that a compiled lambda form is a constant form. This means that after your program is compiled, all references to that function are simply pointers to a chunk of machine code. This pointer can be returned from functions and embedded in new environments, all with no function creation overhead. The overhead was absorbed when the program was compiled. In other words, a function that returns another function will simply be a constant time pointer return function:
(defun lambda-returner ()
(lambda (x) (+ 1 x)))
This is in direct contrast to the let form, which is designed to create a new environment at run-time and as such is usually not a constant operation because of the garbage collection overhead implied by lexical closures, which are of indefinite extent.
(defun let-over-lambda-returner ()
(let ((y 1))
(lambda (x)
(incf y x))))
Every time let-over-lambda-returner is invoked, it must create a new environment, embed the constant pointer to the code represented by the lambda form into this new environment, then return the resulting closure. We can use time to see just how small this environment is:
* (progn
(compile ‘let-over-lambda-returner)
(time (let-over-lambda-returner)))
; Evaluation took:
; …
; 24 bytes consed.
;
#<Closure Over Function>
If you try to call compile on a closure, you will get an error saying you can’t compile functions defined in non-null lexical environments[CLTL2-P677]. You can’t compile closures, only the functions that create closures. When you compile a function that creates closures, the closures it creates will also be compiled[ON-LISP-P25].
The use of a let enclosing a lambda above is so important that we will spend the remainder of this chapter discussing the pattern and variations on it.
.
(lambda ()
(let ((counter 0))
(lambda () (incf counter))))
When the lambda over let over lambda is invoked, a new closure containing a counter binding will be created and returned. Remember that lambda expressions are constants: mere pointers to machine code. This expression is a simple bit of code that creates new environments to close over the inner lambda expression (which is itself a constant, compiled form), just as we were doing at the REPL.
With object systems, a piece of code that creates objects is called a class. But lambda over let over lambda is subtly different than the classes of many languages. While most languages require classes to be named, this pattern avoids naming altogether. Lambda over let over lambda forms can be called anonymous classes.
Although anonymous classes are often useful, we usually do name classes. The easiest way to give them names is to recognise that such classes are regular functions. How do we normally name functions? With the defun form, of course. After naming, the above anonymous class becomes:
(defun counter-class ()
(let ((counter 0))
(lambda () (incf counter))))
Where did the first lambda go? Defun supplies an implicit lambda around the forms in its body. When you write regular functions with defun they are still lambda forms underneath but this fact is hidden beneath the surface of the defun syntax.
BLOCK-SCANNER
(defun block-scanner (trigger-string)
(let* ((trig (coerce trigger-string ‘list))
(curr trig))
(lambda (data-string)
(let ((data (coerce data-string ‘list)))
(dolist (c data)
(if curr
(setq curr
(if (char= (car curr) c)
(cdr curr) ; next char
trig)))) ; start over
(not curr))))) ; return t if found
In order to motivate the use of closures, a realistic example is presented: block-scanner. The problem block-scanner solves is that for some forms of data transfer the data is delivered in groups (blocks) of uncertain sizes. These sizes are generally convenient for the underlying system but not for the application programmer, often being determined by things like operating system buffers, hard drive blocks, or network packets. Scanning a stream of data for a specific sequence requires more than just scanning each block as it comes in with a regular, stateless procedure. We need to keep state between the scanning of each block because it is possible that the sequence we are scanning for will be split between two (or more) blocks.
The most straightforward, natural way to implement this stored state in modern languages is with a closure. An initial sketch of a closure-based block scanner is given as block-scanner. Like all lisp development, creating closures is an iterative process. We might start off with code given in block-scanner and decide to improve its efficiency by avoiding coercion of strings to lists, or possibly improve the information gathered by counting the number of occurrences of the sequence.
Although block-scanner is an initial implementation waiting to be improved, it is still a good demonstration of the use of lambda over let over lambda. Here is a demonstration of its use, pretending to be some sort of communications tap watching out for a specific black-listed word, jihad:
* (defvar scanner
(block-scanner “jihad”))
SCANNER
* (funcall scanner “We will start “)
NIL
# (funcall scanner “the ji”)
NIL
* (funcall scanner “had tomorrow.”)
(let ((direction ‘up))
(defun toggle-counter-direction ()
(setq direction
(if (eq direction ‘up)
‘down
‘up)))
(defun counter-class ()
(let ((counter 0))
(lambda ()
(if (eq direction ‘up)
(incf counter)
(decf counter))))))
LAMBDA as a renaming operation which has more to do with the internal workings of the compiler (or the interpreter), and with a notation for indicating where quantities are referred to, than with the semantics as such of the computation to be performed by the program..
An Example: Compiling a Simple Function One of the important consequences of the view of LAMBDA and function calls presented above is that programs written in a style based on the lambda— calculus-theoretic models of higher-level constructs such as DO loops
Thus , compiler temporaries and simple user variables are treated on a completely equal basis. This idea was used in (Johnsson 75] but without any explanation of why such equal treatment is justified. Here we have some indication that there is conceptually no difference between a user variable and a compiler-generated temporary
In any case, names are eliminated at compile time, and so by run time the distinction between user names and the compiler ’s generated names has been lost. Thus, at the low level, we may view LAMBDA as a renaming operation which has more to do with the internal workings of the compiler (or the interpreter), and with a notation for indicating where quantities are referred to, than with the semantics as such of the computation to be performed by the program.
Furthermore, the ‘access depth’ of a lexical variable is equal to the number of closures which contain it, and in typical programs this depth is small (less than 5). In an optimizing conpiler for lexically scoped LISP it would not necessary to create environment structures in a standard form . Local variables could be kept in any available registers if desired. It would not necessary to interface these environment structures to the interpreter. Because the scoping would be strictly lexical, a reference to a variable in a compiled environment structure must occur in compiled code appearing within the LAMBDA that bound the variable, and so no interpreted reference could refer to such a variable. Similarly, no compiled variable reference could refer to an environment structure created by the interpreter.
This problem can be fixed in any case if the compiler outputs an appropriate map of variable locations for use by the debugger.)
Basic Issues The compiler will need to perform a large amount of global data flow and data type analysis; much of this can be based on the approach used by Wuif in the BLISS-U compiler [Wulf 75), augmented by some general flow-graph analysis scheme. (The BLISS-li flow analysis is not sufficiently general in that it only analyzes single functions, and within a function the only control constructs are conditionals, loops, and block exits.)
https://apps.dtic.mil/sti/tr/pdf/ADA034090.pdf
Conclusion:
LISP and Prolog are indeed Forerunners of Artificial Intelligence Languages. Yet, LISP has some significant differences in Complier vs Interrupters focused topics upon. And Lamda Calculus Functionality gives LISP its trademark in Logical Programming. These were the Key factors discussed in the Study.
References: