Lisp because the Maxwell’s equations of software program
On my first day of physics graduate college, the professor in my class on electromagnetism started by stepping to the board, and wordlessly writing 4 equations:
He stepped again, rotated, and stated one thing like [1]: “These are Maxwell’s equations. Simply 4 compact equations. With a bit of work it’s straightforward to know the essential components of the equations – what all of the symbols imply, how we are able to compute all of the related portions, and so forth. However whereas it’s straightforward to know the weather of the equations, understanding all their penalties is one other matter. Inside these equations is all of electromagnetism – all the things from antennas to motors to circuits. When you assume you perceive the results of those 4 equations, then you could go away the room now, and you may come again and ace the examination on the finish of semester.”
Alan Kay has famously described Lisp because the “Maxwell’s equations of software program”. He describes the revelation he skilled when, as a graduate scholar, he was learning the LISP 1.5 Programmer’s Manual and realized that “the half web page of code on the underside of web page 13… was Lisp in itself. These have been “Maxwell’s Equations of Software program!” That is the entire world of programming in a couple of traces that I can put my hand over.”
Right here’s the half web page of code that Kay noticed in that guide:
What we’re going to do on this essay is perceive what that half web page of code means, and what it implies that Lisp is the Maxwell’s equations of software program. Nevertheless, we gained’t actually work by way of the half web page of code above. As an alternative, we’ll do one thing rather more informative: we’ll create a contemporary, absolutely executable equal of the code above. Moreover, to make this essay accessible, I gained’t assume that Lisp. As an alternative, I’ll train you the essential components of Lisp.
That maybe sounds over-ambitious, however the excellent news is that it’s straightforward to be taught the essential components of Lisp. Offered you will have a bit of facility with laptop programming and luxury with arithmetic, you may learn the way Lisp works in only a few minutes. Frankly, it’s a lot simpler than understanding the weather of Maxwell’s equations! And so I’ll begin by explaining a subset of the Lisp programming language, and getting you to put in writing some Lisp code.
However I gained’t cease with simply exhibiting you the right way to write some Lisp. As soon as we’ve performed that we’re going to put in writing an interpreter for Lisp code. Particularly, we’ll create a interpreter based mostly on a beautiful Lisp interpreter written by Peter Norvig, which accommodates simply 90 traces of Python code. Our interpreter will probably be a bit of extra advanced, due largely to the addition of some conveniences absent from Norvig’s interpreter. The code remains to be easy and straightforward to know, supplied you’re snug studying Python code. As we’ll see, the good thing about writing the interpreter is not only that it provides us a operating interpreter (though that’s no small factor). It’s that writing an interpreter additionally deepens our understanding of Lisp. It does that by taking what would in any other case be some quite summary ideas in our description of Lisp, and giving them concrete, tangible representations when it comes to Python code and knowledge buildings. By making concrete what was previously summary, the code for our Lisp interpreter provides us a brand new manner of understanding how Lisp works.
With our Python Lisp interpreter up and operating, we’ll then write a contemporary equal to the code on the underside of web page 13 of the LISP 1.5 Programmer’s Guide. However whereas our code will probably be basically the identical because the code from web page 13, it is going to have the appreciable benefit that it’s additionally executable. We are able to, if we want, play with the code, modify it, and enhance it. In different phrases, it’s a residing model of the Maxwell’s equations of software program! Moreover, with our new understanding it turns into a simple and enjoyable train to know all the small print on web page 13 of the LISP Guide.
This second a part of the essay is predicated totally on two sources: the primary chapter of the LISP 1.5 Guide, in fact, but in addition an essay by Paul Graham (postscript) during which he explains a number of the early concepts behind Lisp. By the way, “LISP” is the capitalization used within the LISP Guide, however in any other case I’ll use the fashionable capitalization conference, and write “Lisp”.
The good Norwegian mathematician Niels Henrik Abel was as soon as requested how he had turn into so good at arithmetic. He replied that it was “by studying the masters, not their pupils”. The present essay is motivated by Abel’s admonishment. As a programmer, I’m a newbie (and nearly utterly new to Lisp), and so this essay is a manner for me to work intimately by way of concepts from masters equivalent to Alan Kay, Peter Norvig, and Paul Graham. In fact, if one takes Abel at his phrase, then it is best to cease studying this essay, and as a substitute go examine the works of Kay, Norvig, Graham, and the like! I actually suggest taking the time to check their work, and on the finish of the essay I make some suggestions for additional studying. Nevertheless, I hope that this essay has a definite sufficient viewpoint to be of curiosity in its personal proper. Above all, I hope the essay makes fascinated with Lisp (and programming) enjoyable, and that it raises some attention-grabbing elementary questions. In fact, as a newbie, the essay might comprise some misunderstandings or errors (maybe vital ones), and I’d welcome corrections, pointers, and dialogue.
Some components of Lisp
On this and the following two sections we’ll be taught the essential components of Lisp – sufficient to develop our personal executable model of what Alan Kay noticed on web page 13 of the LISP Guide. We’ll name the dialect of Lisp we develop “tiddly Lisp”, or simply tiddlylisp for brief. Tiddlylisp is predicated on a subset of the programming language Scheme, which is without doubt one of the hottest fashionable dialects of Lisp.
Whereas I can present you a bunch of examples of Lisp, you’ll be taught rather more when you sort within the examples your self, after which mess around with them, modifying them and attempting your personal concepts. So I would like you to obtain the file tiddlylisp.py to your native machine. Alternately, when you’re utilizing git, you may simply clone all the code repository related to this essay. The file tiddlylisp.py is the Lisp interpreter whose design and code we’ll work by way of later within the essay. On Linux and Mac you can begin the tiddlylisp interpreter by typing python tiddlylisp.py from the command line. You must see a immediate:
tiddlylisp>
That’s the place you’re going to sort within the code from the examples – it’s an interactive Lisp interpreter. You may exit the interpreter at any time by hitting Ctrl-C. Word that the interpreter isn’t terribly full – as we’ll see, it’s solely 153 traces! – and a method it’s incomplete is that the error messages aren’t very informative. Don’t spend a variety of time worrying concerning the errors, simply strive once more.
When you’re on Home windows, and don’t have already got Python put in, you’ll must download it (I recommend Python 2.7 for this code), earlier than beginning the interpreter by operating python tiddlylisp.py. Word that I’ve solely examined the interpreter on Ubuntu Linux, not on Home windows or the Mac.
As our first instance, sort the next code into the tiddlylisp interpreter:
tiddlylisp> (+ 2 3) 5
Within the expression you typed in, + is a built-in process, which represents the addition operation. It’s being utilized to 2 arguments, on this case the numbers 2 and 3. The interpreter evaluates the results of making use of + to 2 and 3, i.e., of including 2 and 3 collectively, returning the worth 5, which it then prints.
That first instance was very simple, nevertheless it accommodates lots of the ideas we have to perceive Lisp: expressions, procedures, arguments, analysis, returning a worth, and printing. We’ll see many extra illustrations of those concepts under.
Right here’s a second instance, illustrating one other built-in process, this time the multiplication process, *:
tiddlylisp> (* 3 4) 12
It’s the identical fundamental story: * is a built-in process, this time representing multiplication, and is right here being utilized to the numbers 3 and 4. The interpreter evaluates the expression, and prints the worth returned, which is 12.
One probably complicated factor concerning the first two examples is that I’ve referred to as + and * “procedures”, but in lots of programming languages procedures don’t return a worth, solely capabilities do. I’m utilizing this terminology as a result of it’s the usual terminology within the programming language Scheme, which is the dialect of Lisp that tiddlylisp is predicated on. In reality, in some fashionable dialects of Lisp – equivalent to Frequent Lisp – operations equivalent to + and * can be referred to as “capabilities”. However we’ll follow Scheme’s useage, and speak solely of procedures.
One other instance, illustrating a barely totally different sort of process:
tiddlylisp> (Right here, the built-in process represents the comparability operator. And so tiddlylisp prints the results of evaluating an expression which compares the constants 10 and 20. The result's True, since 10 is lower than 20. In contrast, we've got
tiddlylisp> (since 17 is just not lower than 12.
Many Lisp newcomers are initially confused by this fashion of writing fundamental numerical operations. We're so conversant in expressions equivalent to 2 + 3 that the modified order in (+ 2 3) seems unusual and unfamiliar. And but our desire for the infix notation 2 + 3 over the prefix notation (+ 2 3) is extra a historic accident than a consequence of something elementary about arithmetic. Sadly, this has the consequence that some folks again away from Lisp, just because they dislike pondering on this unfamiliar manner.
On this essay we can't get deep sufficient into Lisp to see in a variety of concrete element why the prefix notation is a good suggestion. Nevertheless, we are going to get one trace: our tiddlylisp interpreter will probably be a lot less complicated for utilizing the identical (prefix) model for all procedures. When you actually strongly dislike the prefix notation, then I problem you to rewrite tiddlylisp in order that it makes use of infix notation for some operations, and prefix notation for others. What you may discover is that the interpreter turns into fairly a bit extra advanced. And so there's a sense during which utilizing the identical prefix model in all places makes Lisp less complicated.
One other helpful factor Lisp permits us to do is to nest expressions:
tiddlylisp> (To compute the worth of this expression, tiddlylisp evaluates the nested expressions, returning 209 from (* 11 19), and 207 from (* 9 23). The output from the outer expression is then simply the results of evaluating (, which in fact is False.
We are able to use tiddlylisp to outline variables:
tiddlylisp> (outline x 3) tiddlylisp> (* x 2) 6outline is used to outline new variables; we are able to additionally assign a worth to a variable which has beforehand been outlined:
tiddlylisp> (set! x 4) tiddlylisp> x 4One query you will have right here is concerning the barely uncommon syntax: set!. You would possibly ponder whether the exclamation mark means one thing particular - possibly set! is a few sort of hybrid process or one thing. Truly, there isn't any such complexity: set! is only a single key phrase, identical to outline, nothing particular about it in any respect. It is simply that tiddlylisp permits exclamation marks in key phrase names. So there's nothing particular occurring indicated by the exclamation mark.
A deeper query is why we do not merely eleminate outline, and make it so set! checks whether or not a variable has been outlined already, and if not, does so. I will clarify a bit of bit later why we do not do that; for now, it is best to simply be aware the excellence.
We are able to use outline to outline new procedures in a manner much like how we use it to outline variables. Here is an instance exhibiting the right way to outline a process named sq.. I will unpack what is going on on under, however first, this is the code,
tiddlylisp> (outline sq. (lambda (x) (* x x))) tiddlylisp> (sq. 7) 49Ignore the primary of the traces above for now. You may see from the second line what the process sq. does: it takes a single quantity as enter, and returns the sq. of the quantity.
What concerning the first line of code above? We already know sufficient to guess fairly a bit about how this line works: a process named sq. is being outlined, and is assigned the worth of the expression (lambda (x) (* x x)), no matter that worth may be. What's new, and what we have to perceive, is what the worth of the expression (lambda (x) (* x x)) is. To know this, let's break the expression into three items: lambda, (x), and (* x x). We'll perceive the three items individually, after which put them again collectively.
The primary piece of the expression - the lambda - merely tells the tiddlylisp interpreter that this expression is defining a process. I need to admit that after I first encountered the lambda notation I discovered this beautiful complicated [2] - I believed that lambda have to be a variable, or an argument, or one thing like that. However no, it is only a massive fats pink flag to the tiddlylisp interpreter saying "Hey, this can be a process definition". That is all lambda is.
The second a part of the expression - the (x) - tells tiddlylisp that this can be a process with a single argument, and that we will use the non permanent identify x for that argument, for the needs of defining the process. If the process definition had began as a substitute with (lambda (x y) ...) that may have meant that the process had two arguments, briefly labelled x and y for the needs of defining the process.
The third a part of the expression - the (* x x) - is the meat of the process definition. It is what we consider and return when the process is named, with the precise values for the arguments of the process substituted rather than x.
Taking all of it collectively, then, the worth of the expresion (lambda (x) (* x x)) is only a process with a single enter, and returning the sq. of that enter. This process is nameless, i.e., it would not have a reputation. However we may give it a reputation through the use of outline, and so the road
tiddlylisp> (outline sq. (lambda (x) (* x x)))tells tiddlylisp to outline one thing referred to as sq., whose worth is a process (due to the lambda) with a single argument (due to the (x)), and what that process returns is the sq. of its argument (due to the (* x x)).
An essential level concerning the variables utilized in defining procedures is that they are dummy variables. Suppose we wished to outline a process space which might return the realm of a triangle, with arguments the bottom of the triangle and the peak. We might do that utilizing the next process definition:
tiddlylisp> (outline space (lambda (b h) (* 0.5 (* b h)))) tiddlylisp> (space 3 5) 7.5However what would have occurred if we would earlier outlined a variable h, e.g.:
tiddlylisp> (outline h 11) tiddlylisp> (outline space (lambda (b h) (* 0.5 (* b h))))It most likely will not shock you to be taught that contained in the process definition, i.e., instantly after the lambda (b h), the h is handled as a dummy variable, and is totally totally different from the h outdoors the process definition. It has what's referred to as a unique scope. And so we are able to proceed the above with the next
tiddlylisp> (space 3 h) 16.5that's, the realm is simply 0.5 occasions 3 occasions the worth of h set earlier, outdoors the process definition. At that time the worth of h was 11, and so (space 3 h) returns 16.5.
There is a variation on the above that you simply would possibly marvel about, which is what occurs if you use variables outlined outdoors a process inside that process definition? As an illustration, suppose we've got:
tiddlylisp> (outline x 3) tiddlylisp> (outline foo (lambda (y) (* x y)))What occurs now if we consider foo? Nicely, tiddlylisp does the wise factor, and interprets x because it was outlined outdoors the process definition, so we've got:
tiddlylisp> (foo 4) 12What occurs to our process if we subsequent change the worth of x? In reality, this adjustments foo:
tiddlylisp> (set! x 5) tiddlylisp> (foo 4) 20In different phrases, within the process definition lambda (y) (* x y) the x actually does confer with the variable x, and to not the actual worth x may need at any given cut-off date.
Let's dig down a bit extra into how tiddlylisp handles scope and dummy variables. Let us take a look at what occurs after we outline a variable:
tiddlylisp> (outline x 5) tiddlylisp> x 5The best way the interpreter handles this internally is that it maintains what's referred to as an atmosphere: a dictionary whose keys are the variable names, and whose values are the corresponding variable values. So what the interpeter does when it sees the primary line above is add a brand new key to the atmosphere, "x", with worth 5. When the interpreter sees the second line, it consults the atmosphere, seems up the important thing x, and returns the corresponding worth. You may, when you like, consider the atmosphere because the interpreter's reminiscence or knowledge retailer, during which it shops all the small print of the variables outlined thus far.
All that is fairly easy. We are able to go alongside defining and altering variables, and the interpreter simply retains consulting and modifying the atmosphere as vital. However if you outline a brand new process utilizing lambda the interpreter treats the variables used within the definition barely otherwise. Let us take a look at an instance:
tiddlylisp> (outline h 5) tiddlylisp> (outline space (lambda (b) (* b h))) tiddlylisp> (space 2) 10What I wish to consider right here is the process definition (lambda (b) (* b h)). Up up to now the interpreter had been chugging alongside, modifying its atmosphere as applicable. What occurs when it sees the (lambda ...), although, is that the interpreter creates a brand new atmosphere, an atmosphere referred to as an inside atmosphere, as distinguished from the outer atmosphere, which is what the interpreter has been working in till it reached the (lambda ...) assertion. The inside atmosphere is a brand new dictionary, whose keys initially are simply the arguments to the process - on this case a single key, b - and whose values will probably be provided when the process is named.
To recap, what the interpreter does when it sees (lambda (b) (* b h)) is create a brand new inside atmosphere, with a key b whose worth will probably be set when the process is named. When evaluating the expression (* b h) (which defines the consequence returned from the process) what the interpreter does is first seek the advice of the inside atmosphere, the place it finds the important thing b, however not the important thing h. When it fails to seek out h, it seems as a substitute for h within the outer atmosphere, the place the important thing h has certainly been outlined, and retrieves the suitable worth.
I've described a easy instance exhibiting how environments work, however tiddlylisp additionally permits us to have process definitions nested inside process definitions, nested inside process definitions (and so forth). To cope with this, the top-level tiddlylisp interpreter operates inside a international atmosphere, and every process definition creates a brand new inside atmosphere, maybe nested inside a beforehand created inside atmosphere, if that is applicable.
If all this discuss inside and outer environments has left you confused, concern not. At this stage it actually is essential to have gotten the gist of how environments work, however you should not fear if the small print nonetheless appear elusive. In my view, one of the simplest ways to know these particulars is just not by way of summary dialogue, however as a substitute by wanting on the working code for tiddlylisp. We'll get to that shortly, however for now can transfer onwards armed with a common impression of how environments work.
The process definitions I've described to date consider and return the worth from only a single expression. We are able to use such expressions to realize suprisingly advanced issues, due to the flexibility to nest expressions. Nonetheless, it might be handy to have a manner of chaining collectively expressions that does not contain nesting. A manner of doing that is to make use of the start key phrase. start is particularly useful in defining advanced procedures, and so I will give an instance in that context:
tiddlylisp> (outline space (lambda (r) (start (outline pi 3.14) (* pi (* r r)))))This line is defining a process referred to as space, with a single argument r, and the place the worth of (space r) is simply the worth of the expression
(start (outline pi 3.14) (* pi (* r r)))with the suitable worth for r substituted. The best way tiddlylisp evaluates the start expression above is that it evaluates all of the separate sub-expressions, consecutively within the order they seem, after which returns the worth of the closing sub-expression, on this case the sub-expression (* pi (* r r)). So, for instance, we get
tiddlylisp> (space 3) 28.26which is simply the realm of a circle with radius 3.
Now, in a easy instance equivalent to this you would possibly argue that it makes extra sense to keep away from defining pi, and simply put 3.14 straight into the later expression. Nevertheless, doing so will make the intent of the code much less clear, and I belief you'll find it straightforward to think about extra advanced instances the place it makes much more sense to make use of multi-part start expressions. That is particularly the case since it's permissible to separate Lisp expressions over a number of traces, so the above process definition might have been written:
(outline space (lambda (r) (start (outline pi 3.14) (* pi (* r r)))))Now, I ought to point out that when you enter the above into the tiddlylisp interpreter, you may get errors. It's because the tiddlylisp interpreter is so stripped down that it would not permit multi-line inputs. Nevertheless, tiddlylisp will will let you load multi-line expressions from a file - strive saving the above three traces in a file named space.tl, after which operating that file with python tiddlylisp.py space.tl. Tiddlylisp will execute the code, defining the space process, after which go away you within the interpreter, the place you may sort issues like:
tiddlylisp> (space 3) 28.26A second benefit of utilizing start within the above code is that the variable pi is barely outlined within the inside atmosphere related to the lambda expression. If, for some purpose, you wish to outline pi otherwise outdoors that scope, you are able to do so, and it will not be affected by the definition of space. Think about, for instance, the next sequence of expressions:
tiddlylisp> (outline pi 3) tiddlylisp> pi 3 tiddlylisp> (outline space (lambda (r) (start (outline pi 3.14) (* pi (* r r))))) tiddlylisp> (space 1) 3.14 tiddlylisp> pi 3In different phrases, the worth of the ultimate pi is returned from the outer (international) atmosphere, not the inside atmosphere created throughout the definition of the process space.
Earlier, we mentioned outline and set!, and questioned whether or not there was actually any important distinction. Think about now the next instance, the place we modify space through the use of set! as a substitute of outline:
tiddlylisp> (outline pi 3) tiddlylisp> pi 3 tiddlylisp> (outline space (lambda (r) (start (set! pi 3.14) (* pi (* r r))))) tiddlylisp> (space 1) 3.14 tiddlylisp> pi 3.14As you may see by evaluating the ultimate line of this instance to our earlier instance, there actually is a big distinction between outline and set!. Particularly, after we outline space on this instance, what set! does is test to see whether or not the inside atmosphere accommodates a variable named pi. Because it would not, it checks the outer atmosphere, the place it does discover such a variable, and that is what set! updates. If we would used outline as a substitute it might have created a very new variable named pi within the inside atmosphere, whereas leaving pi within the outer atmosphere untouched, so the ultimate line would have returned 3 as a substitute. So having each outline and set! provides us fairly a little bit of flexibility and management over which atmosphere is getting used, on the expense of a complication in syntax.
As our closing piece of Lisp earlier than placing what we have learnt collectively to assemble a nontrivial instance, tiddlylisp features a key phrase if that can be utilized to check situations, and conditionally return the worth of various expressions. Here is an instance exhibiting the usage of if to judge absolutely the worth of a variable:
tiddlylisp> (outline x -2) tiddlylisp> (if (> x 0) x (- 0 x)) 2We are able to use the identical concept to outline a process abs which returns absolutely the worth of a quantity:
tiddlylisp> (outline abs (lambda (x) (if (> x 0) x (- 0 x)))) tiddlylisp> (abs -2) 2The final type for if expressions is (if cond consequence alt), the place we consider the expression cond, and if the worth is True, return the worth of consequence, in any other case return the worth of alt. Word that within the expression (if cond consequence alt), the cond, consequence and alt in fact should not be learn actually. Quite, they're placeholders for different expressions, as we noticed within the absolute worth instance above. By way of the rest of this essay I'll use use italics to point such placeholder expressions.
Let me conclude this part by briefly introducing two essential Lisp ideas. The primary is the idea of a particular type. On this part we mentioned a number of built-in procedures, equivalent to + and *, and in addition some user-defined procedures. Calls to such procedures at all times have the shape (proc exp1 exp2...), the place proc is the process identify, and the opposite arguments are expressions. Such expressions are evaluated by evaluating every particular person expression exp1, exp2..., after which passing these values to the process. Nevertheless, not all Lisp expressions are process calls. Think about the expression (outline pi 3.14). This is not evaluated by calling some process outline with arguments given by the worth of pi and the worth of 3.14. It could actually't be evaluated this fashion as a result of pi would not have a worth but! So outline is not a process. As an alternative, outline is an instance of what's referred to as a particular type. Different examples of particular types embody lambda, start, and if, and some extra which we'll meet later. Like outline, none of those is a process, however as a substitute every particular types has its personal particular rule for analysis.
The second idea I wish to briefly introduce is that of a listing. The checklist is without doubt one of the fundamental knowledge buildings utilized in Lisp, and even provides the language its identify - Lisp is brief for "checklist processing". In reality, many of the Lisp expressions we have seen so far are lists: an expression equivalent to (abs 2) is a two-element checklist, with components abs and 2, delimited by areas and parentheses. A extra advanced expression equivalent to (outline abs (lambda (x) (if (> x 0) x (- 0 x)))) can be a listing, on this case with the primary two components being outline and abs. The third aspect, (lambda (x) (if (> x 0) x (- 0 x))), is a sublist which in flip has sublists (and subsublists) of its personal. Later we'll see the right way to use Lisp to do manipulations with such lists.
A nontrivial instance: sq. roots utilizing solely elementary arithmetic
Let's put collectively the concepts above to do one thing nontrivial. We'll write a brief tiddlylisp program to compute sq. roots, utilizing solely the elementary arithmetical operations (addition, subtraction, multiplication, and division). The concept behind this system is to make use of Newton's method. Though Newton's methodology is attention-grabbing in its personal proper, I am not together with this instance due to its algorithmic class. As an alternative, I am together with it as a easy and delightful instance of a Lisp program. The instance comes from Abelson and Sussman's ebook on the Structure and Interpretation of Computer Programs.
Here is how Newton's methodology for computing sq. roots works. Suppose we've got a (optimistic) quantity x whose sq. root we want to compute. Then we begin by making a guess on the sq. root, guess. We will begin by arbitrarily selecting 1.0 as our preliminary worth for guess; in precept, any optimistic quantity will do. In response to Newton's methodology, we'll get an improved guess by computing (guess+x/guess)/2, i.e., by taking the common of guess and x/guess. If we repeat this averaging course of sufficient occasions, we'll converge to a very good estimate of the sq. root.
Let's specific these concepts in Lisp code. We'll do it from the highest down, beginning at a excessive stage, and progressively filling within the particulars of all of the procedures we'd like. We begin on the absolute prime stage,
(outline sqrt (lambda (x) (sqrt-iter 1.0 x)))Right here, (sqrt-iter guess x) is the worth of a to-be-defined process sqrt-iter that takes a guess guess on the sq. root of x, and retains bettering that guess again and again till it is a ok estimate of the sq. root. As I discussed above, we begin by arbitrarily selecting guess = 1.0.
The core of the algorithm is the definition of sqrt-iter:
(outline sqrt-iter (lambda (guess x) (if (good-enough? guess x) guess (sqrt-iter (enhance guess x) x))))What sqrt-iter does is takes the guess and checks to see whether or not it is but a good-enough? approximation to the sq. root of x, in a way to be made exact under. Whether it is, then sqrt-iter is finished, and returns guess, in any other case it applies sqrt-iter to the improved guess (enhance guess x) provided by making use of Newton's methodology.
By the way, the best way I've written sqrt-iter above it is one other instance of a multi-line tiddlylisp expression, and so it is not potential to enter within the tiddlylisp interpreter. Nevertheless, you may enter it as a part of a file, sqrt.tl, together with the definition of sqrt, and different procedures which we'll outline under. We'll later use tiddlylisp to execute the file sqrt.tl.
To fill out the small print of the above, we have to perceive how good-enough? and enhance work. Let's begin with good-enough?, which merely checks whether or not absolutely the worth of the sq. of guess is inside 0.00001 of x:
(outline good-enough? (lambda (guess x) (Right here, we've got outlined absolutely the worth process abs and the squaring process sq. as:
(outline abs (lambda (x) (if (That is all of the code we'd like for good-enough?. For enhance we merely implement Newton's methodology,
(outline enhance (lambda (guess x) (common guess (/ x guess))))the place common is outlined within the apparent manner:
(outline common (lambda (x y) (* 0.5 (+ x y))))We are able to write out the entire program as follows:
(outline common (lambda (x y) (* 0.5 (+ x y)))) (outline enhance (lambda (guess x) (common guess (/ x guess)))) (outline sq. (lambda (x) (* x x))) (outline abs (lambda (x) (if (Save these traces to the file sqrt.tl, after which run it utilizing python tiddlylisp.py sqrt.tl. Tiddlylisp will execute the code, defining all of the above procedures, after which go away you in an interpreter, the place you may sort:
tiddlylisp> (sqrt 2.0) 1.41421568627That is, certainly, a fairly good approximation to the true sq. root: 1.4142135....
In writing out the general program sqrt.tl, I've reversed the order of the traces, in comparison with my preliminary clarification. The explanation I've performed that is price discussing. You see, this system sqrt.tl was really the primary piece of Lisp code I ever labored although intimately. The pure solution to assume by way of the issue of computing sq. roots with Newton's methodology is within the order I defined, working in a top-down trend, ranging from the broad downside, and progressively breaking our assault on that downside down into components. However the first time I wrote the code out I assumed that I wanted to clarify these concepts to Lisp in a bottom-up trend, defining procedures like common earlier than enhance and so forth, in order that process definitions solely embody beforehand outlined procedures. That meant reversing the order of the code, as I've proven above.
Taking this strategy bugged me. It would not appear to be essentially the most pure manner to consider implementing Newton's methodology. At the least for this downside a top-down strategy appears extra pure, and when you have been simply doing exploratory programming you'd begin by defining sqrt, then sqrt-iter, and so forth. As an experiment, I made a decision to reverse the order of the progam, so it displays the pure "pondering order":
(outline sqrt (lambda (x) (sqrt-iter 1.0 x))) (outline sqrt-iter (lambda (guess x) (if (good-enough? guess x) guess (sqrt-iter (enhance guess x) x)))) (outline good-enough? (lambda (guess x) (Considerably to my shock, this ran simply positive ! (Truly, my code was barely totally different, since I used to be utilizing Frequent Lisp at that time, not tiddlylisp, however tiddlylisp works as nicely.) It is apparently okay to outline a process when it comes to another process which is not outlined till later. Now, upon shut examination of the code for tiddlylisp it seems that this makes good sense. Nevertheless it got here as a shock to me. Later, after we study the code for tiddlylisp, I will set an issue asking you to clarify why it is okay to re-order the code above.
I feel this program for the sq. root is a really lovely program. In fact, in most programming languages the sq. root is inbuilt, and so it is not precisely notable to have a chic program for it! Certainly, the sq. root is inbuilt to most model of Lisp, and it is trivially potential so as to add the sq. root to tiddlylisp. However what I like concerning the above is that it is such a easy and pure expression of Newton's methodology. As Peter Deutsch has said, Lisp applications come near being "executable arithmetic".
Issues for the creator
- As a common level about programming language design it appears like it might usually be useful to have the ability to outline procedures in phrases of different procedures which haven’t but been outlined. Which languages make this potential, and which don’t? What benefits does it convey for a programming language to have the ability to do that? Are there any disadvantages?
A couple of extra components of Lisp
I started my introduction to Lisp by specializing in elementary arithmetical operations, and the right way to put them collectively. I did that so I might provide you with a concrete instance of Lisp in motion – the sq. root instance within the final part – which is an efficient manner of getting a really feel for a way Lisp works. But when we will perceive Lisp as “the Maxwell’s equations of software program” then we additionally want to know extra about how Lisp offers with expressions and with lists. I will describe these operations on this part.
Earlier than I describe these operations, I wish to talk about a distinction that I have never drawn a lot consideration to till now. That is the excellence between an expression equivalent to (+ 1 2) and the worth of that expression, which on this case is 3. Once we feed a (legitimate) tiddlylisp expression to the tiddlylisp interpreter, it evaluates the expression, and returns its worth.
After I was first studying Lisp I might usually get myself in bother as a result of I didn’t hold myself clear on the excellence between an expression and its worth. Let me provide you with an instance of the type of confusion I might get myself into. There’s a built-in Lisp process referred to as atom?, outlined in order that (atom? exp) returns True if the worth of the expression exp is atomic – a quantity, for instance, or something which is not a listing – and returns False in any other case. (Word that exp is a placeholder expression, as we mentioned earlier, and should not be learn actually because the identifier exp.) Now, I might have a look at an instance like (atom? 5) and haven’t any bother determining that it evaluated to True. However the place I might get into bother is with an expression like (atom? (+ 1 2)). I might have a look at it and assume it should return False, as a result of the expression (+ 1 2) is just not atomic, it is a checklist. Sadly, whereas it is true that the expression (+ 1 2) is just not atomic, it is irrelevant, as a result of the worth of (atom? exp) is set by whether or not the worth of exp is atomic – which it’s, because the worth of (+ 1 2)) is 3. You may be a a lot happier Lisper when you at all times hold very clear on the excellence between expressions and the worth of expressions.
Now, in fact, this distinction between expressions and their values seems in most different programming languages. For that reason, I felt silly after I understood what was making my confusion. However what makes it really easy to make this sort of mistake is that in Lisp each expressions and the worth of these expressions will be lists. And that is why after I write one thing like (atom? (+ 1 2)) there’s an actual query: is atom? checking whether or not the expression (+ 1 2) is atomic (no, it is not, it is a checklist), or whether or not the worth of the expression – 3 – is atomic (sure, it’s). So it’s essential to be fairly cautious to maintain clear on which is supposed. To assist with this, I will be fairly pedantic concerning the distinction in what follows, writing out “the worth of exp” explicitly, to tell apart the worth from the expression itself. Word, nonetheless, that it is fairly frequent for folks to be much less pedantic and extra casual, in order that one thing like (+ x 2) could be described as “including the variable x to the variable y“, not the extra express “including the worth of the variable x to the worth of the variable y.”
Alright, with that admonishment out of the best way, let’s flip our consideration to defining the ultimate set of elementary operations we’ll want in tiddlylisp.
Returning an expression as a worth: (quote exp) returns the expression exp as its worth, with out evaluating exp. That is most clearly demonstrated by an instance,
tiddlylisp> (quote (+ 1 2)) (+ 1 2)
versus the worth of (+ 1 2), which in fact is 3. One other instance, simply to strengthen the purpose that quote returns an expression actually, with out evaluating it,
tiddlylisp> (outline x 3) tiddlylisp> (quote x) x
not the worth of x, which in fact is 3. Word additionally that quoting would not consider nested subexpressions, e.g.,
tiddlylisp> (quote ((+ 1 2) 3)) ((+ 1 2) 3)
quote can be used to return lists which are not legitimate Lisp expressions in any respect, e.g.,
tiddlylisp> (quote (1 2 3)) (1 2 3)
It is price emphasizing that (1 2 3) is not a legitimate Lisp expression, since 1 is neither a process nor a particular type – when you enter (1 2 3) into the tiddlylisp interpreter, it is going to give an error. However what quote lets us do is use the checklist (1 2 3) as knowledge. For instance, we might use it to retailer the (1 2 3) in a variable,
tiddlylisp> (outline x (quote (1 2 3))) tiddlylisp> x (1 2 3)
On this manner, quote lets us work with lists as knowledge buildings.
Why does Lisp have quote? Most different laptop programming languages haven’t got something prefer it. The explanation Lisp has it’s as a result of Lisp means that you can deal with code as knowledge, and knowledge as code. So, for instance, an object equivalent to (+ 1 2) will be handled as code, i.e., as a Lisp expression to be evaluated, which is what we have been doing up till the present dialogue. However (+1 2) also can probably be handled as knowledge, i.e., as a listing of three objects. This capacity to deal with code and knowledge on the identical footing is a superb factor, as a result of it means you may write applications to control applications. Nevertheless it additionally creates an issue, which is that we’d like to have the ability to distinguish when an expression must be handled as knowledge, and when it must be handled as code. quote is a manner of distinguishing between the 2. It is much like the best way most languages use escape characters to cope with particular strings equivalent to “. quote is a manner of claiming “Hey, what follows must be handled as knowledge, not evaluated as Lisp code”. And so quote lets us escape Lisp code, so we are able to take an expression equivalent to (+ 1 2) and switch it into knowledge: (quote (+ 1 2). On this manner, quote permits us to outline Lisp expressions whose values are arbitrary Lisp expressions.
Up till now we have been targeted on utilizing Lisp to do easy arithmetic operations, and consequently we have not wanted quote. However after we get to Lisp-as-Maxwell’s-equations we will be more and more targeted on utilizing Lisp to control Lisp code, and consequently we’ll be making frequent use of quote. For that reason it is useful to introduce shorthand for quote. In most Lisps, the traditional shorthand is to make use of 'exp to indicate (quote exp), i.e. if exp is a few Lisp expression, then the worth of 'exp is simply the expression exp itself. Sadly, utilizing the shorthand 'exp sophisticated the parsing within the tiddlylisp interpreter greater than I wished. So I made a decision to as a substitute use a unique (and, I emphasize, unconventional) shorthand for (quote exp), particularly (q exp). So our examples of quote above will be shortened to,
tiddlylisp> (q (+ 1 2)) (+ 1 2) tiddlylisp> (outline x 3) tiddlylisp> (q x) x tiddlylisp> (q ((+ 1 2) 3)) ((+ 1 2) 3)
Testing whether or not the worth of an expression is atomic: As I famous above, (atom? exp) returns True if the worth of the expression exp is atomic, and in any other case returns False. We have already mentioned the next instance,
tiddlylisp> (atom? (+ 1 2)) True
nevertheless it’s illuminating to see it in tandem with the next instance, which illustrates additionally the usage of quote,
tiddlylisp> (atom? (q (+ 1 2))) False
As above, the primary instance returns True as a result of whereas (+ 1 2) is just not atomic, its worth, 3, is. However the second instance returns False as a result of the worth of (q (+ 1 2)) is simply (+ 1 2), which is a listing, and thus not atomic.
By the best way, I ought to point out that atom? is just not a built-in process within the dialect of Lisp that tiddlylisp based mostly on, Scheme. I’ve constructed atom? into tiddlylisp as a result of, as we’ll see, the analogous operation is used many occasions within the code on web page 13 of the LISP 1.5 Programmer’s Guide. In fact, an atom? process is definitely outlined in Scheme, however for the needs of understanding the code on web page 13 it appeared most direct to easily embody atom? as a built-in in tiddlylisp.
Testing whether or not two expressions each consider to the identical atom (or the empty checklist): (eq? exp1 exp2) returns True if the values of exp1 and exp2 are each the identical atom, or each the empty checklist, (). (eq? exp1 exp2) returns False in any other case. Word that if exp1 and exp2 have the identical worth, however will not be atomic or the empty checklist, then (eq? exp1 exp2) returns False. For instance,
tiddlylisp> (eq? 2 (+ 1 1)) True tiddlylisp> (eq? 3 (+ 1 1)) False tiddlylisp> (eq? (q (1 2)) (q (1 2))) False
As for atom? my clarification of eq? is just not fairly the identical as in commonplace Scheme, however as a substitute extra carefully matches the perform eq outlined within the LISP 1.5 Programmer’s Guide.
Getting the primary merchandise of a listing: (automotive exp) returns the primary aspect of the worth of exp, supplied the worth of exp is a listing. In any other case (automotive exp) is undefined. For instance,
tiddlylisp> (automotive (q (+ 2 3))) + tiddlylisp> (automotive (+ 2 3))
The primary of those two behaves as anticipated: the worth of (q (+ 2 3) is simply the checklist (+ 2 3), and so automotive returns the primary aspect, which is +. Within the second, although, automotive is just not outlined, and tiddlylisp returns an error message, which I’ve elided. The explanation it returns an error message is as a result of the worth of (+ 2 3) is 5, which isn’t a listing, and so automotive is undefined. In an analogous manner, suppose we strive
tiddlylisp> (automotive (1 2 3))
Once more, we get an error message. The reason being that automotive is being utilized to the worth of (1 2 3), thought of as a Lisp expression. And, in fact, that worth is undefined, since 1 is neither a process nor a particular type. The best solution to do the above is to quote the checklist first,
tiddlylisp> (automotive (q (1 2 3))) 1
As soon as once more, we see how quote is used to make it clear to tiddlylisp that we’re coping with knowledge, not code to be evaluated.
Getting the remainder of a listing: (cdr exp) returns a listing containing all however the first aspect of the worth of exp. In fact, the worth of exp have to be a listing, in any other case (cdr exp) is undefined. For instance,
tiddlylisp> (cdr (q (1 2 3))) (2 3)
In response to Wikipedia the names automotive and cdr have their origin in some fairly esoteric info concerning the early implementations of Lisp. The main points do not a lot matter right here – automotive stands for “contents of handle a part of register”, whereas cdr stands for “contents of decrement a part of register” – I simply wished to make the purpose that you could possibly moderately be questioning “The place on Earth did these names come from?!” A mnemonic I discover helpful in distinguishing the 2 is to deal with the distinction between the names of the 2 procedures, which in fact is simply the center letter – a or d – and to remember that a comes earlier than d within the alphabet, simply as automotive extracts the aspect of a listing that comes earlier than the rest of the checklist, as given to us by cdr. Your style in mnemonics might fluctuate – when you do not like mine, it is nonetheless price taking a minute or two to provide you with some trick for remembering and distinguishing automotive and cdr. In fact, after a bit of follow you get used to them, and you will not want the mnemonic any extra, however at first it is useful.
Appending an merchandise at the beginning of a listing: Offered the worth of exp2 is a listing, then (cons exp1 exp2) returns a listing containing the worth of exp1 as its first aspect, adopted by all the weather of the worth of exp2. For instance,
tiddlylisp> (cons 1 (q (2 3))) (1 2 3)
Testing whether or not an expression evaluates to the empty checklist: (null? exp) returns True if exp evaluates to the empty checklist, (), and in any other case returns False. For instance,
tiddlylisp> (null? (cdr (q (1)))) True
since (cdr (q (1))) returns the empty checklist.
Conditionals: (cond (p1 e1)...(pn en)): This begins by evaluating the expression p1. If p1 evaluates to True, then consider the expression e1, and return that worth. If not, consider p2, and whether it is True, return the worth of e2, and so forth. If not one of the pj evaluates to True, then the (cond ...) expression is undefined.
That is all of the Lisp we will want to put in writing our model of Lisp-as-Maxwell’s-equations, i.e., our model of the code on web page 13 of the LISP Guide! In reality, as we’ll see shortly, it is greater than we’d like – I included a couple of further options in order that we might work by way of examples like sqrt, and in addition merely for enjoyable, to make tiddlylisp a richer and extra attention-grabbing language to play with. In fact, what I’ve described is merely a subset (with some variations) of our chosen dialect of Lisp (Scheme), and there are essential lacking concepts. To be taught extra about Lisp or Scheme, please seek the advice of the strategies for additional studying on the finish of this essay.
An interpreter for Lisp
Now that we have labored by way of the essential components of Lisp, let’s write a easy Lisp interpreter, utilizing Python. The interpreter we’ll write is predicated on Peter Norvig‘s lispy interpreter, and I extremely suggest you learn by way of his explanation. I’ve given this system we’ll talk about a separate identify – tiddlylisp – in order to make it straightforward to confer with individually from Norvig’s interpreter, however please remember that many of the code we’re discussing is Norvig’s. Nevertheless, we will study the code from a unique angle than Norvig: we will take a bit extra of a bottom-up laptop’s-eye view, taking a look at how the code executes.
We’ll have a look at the code piece by piece, earlier than placing all of it collectively. Let’s begin with the interactive interpreter, which is run if you begin up. We implement this with a Python process referred to as repl, that means to read some enter, evaluate the expression, print the results of the analysis, after which loop again to the start. That is additionally know because the read-eval-print loop, or REPL. Here is the repl process, along with a process for dealing with errors once they happen:
import traceback
def repl(immediate="tiddlylisp> "):
"A prompt-read-eval-print loop."
whereas True:
strive:
val = eval(parse(raw_input(immediate)))
if val is just not None: print to_string(val)
besides KeyboardInterrupt:
print "nExiting tiddlylispn"
sys.exit()
besides:
handle_error()
def handle_error():
"""
Easy error dealing with for each the repl and cargo.
"""
print "An error occurred. Here is the Python stack hint:n"
traceback.print_exc()
The core of repl is within the strive clause, and we’ll get to how that works shortly. Earlier than we have a look at that, be aware that if the person presses Ctrl-C, it raises the KeyboardInterrupt exception, which causes this system to exit. If an error happens throughout the strive block — say, resulting from a syntax error within the Lisp expression being parsed, or resulting from a bug in tiddlylisp itself – then another exception will probably be raised. Tiddlylisp would not deal very nicely with errors – it merely pronounces that an error has occurred, and prints the Python stack hint, which can provide you with a couple of hints about what’s gone mistaken, however which is clearly a great distance wanting actually informative error dealing with! After printing the stack hint, tiddlylisp merely returns to the immediate. Such a error dealing with might simply be improved, however we’re not going to speculate any effort on this path.
Let us take a look at the strive clause. It begins by taking enter on the immediate, after which passing it to the perform parse, which converts the string entered by the person into an inner illustration, i.e., a knowledge construction that is extra handy for our Python program to work with than a string. Here is an instance which exhibits the way it works:
parse("(* (+ 7 12) (- 8 6))") = ["*", ["+", 7, 12], ["-", 8, 6]]
In different phrases, nested Lisp lists turn into Python sublists, and issues like procedures and numbers turn into components in a Python checklist.
We’ll look shortly at how parse is carried out. For now, let’s end understanding how repl works. The output of parse is handed to the perform eval, which evaluates the interior illustration of the expression entered by the person. Offered no error happens, the result’s returned in val. Nevertheless, val is within the format of the interior illustration, and so we have to convert it from that inner illustration again right into a printable Lisp expression, utilizing to_string.
At this level, we have got three capabilities to know the small print of: parse, eval and to_string. I will clarify them out of order, beginning with parse and to_string, since they’re extraordinarily related. Then we’ll get to eval.
Alright, let’s perceive how parse works. With out additional ado, this is the code; for the reason, see under:
Image = str
def parse(s):
"Parse a Lisp expression from a string."
return read_from(tokenize(s))
def tokenize(s):
"Convert a string into a listing of tokens."
return s.exchange('(',' ( ').exchange(')',' ) ').cut up()
def read_from(tokens):
"Learn an expression from a sequence of tokens."
if len(tokens) == 0:
elevate SyntaxError('sudden EOF whereas studying')
token = tokens.pop(0)
if '(' == token:
L = []
whereas tokens[0] != ')':
L.append(read_from(tokens))
tokens.pop(0) # pop off ')'
return L
elif ')' == token:
elevate SyntaxError('sudden )')
else:
return atom(token)
def atom(token):
"Numbers turn into numbers; each different token is a logo."
strive: return int(token)
besides ValueError:
strive: return float(token)
besides ValueError:
return Image(token)
The parsing is straightforward to know. tokenize first inserts areas on both facet of any parentheses, after which splits the string round areas, returning a listing of tokens, i.e., the non-space substrings. read_from takes that checklist and removes the parentheses, as a substitute nesting sublists as indicated by the unique parenthesis construction. And, lastly, atom turns tokens into Python ints, floats or Images (strings, by definition), as applicable.
That is all there’s to parse. If tiddlylisp have been a bit of extra highly effective then parse would should be extra advanced. For instance, if we allowed strings as first-class objects within the language, then it might not work to tokenize by splitting round areas, since that may threat splitting a string into separate tokens. That is the type of factor that’d be enjoyable to incorporate in an prolonged model of tiddlylisp (and I’ve included it as an issue later on this part), however which we do not want in a primary model.
Let’s look now at how to_string works. It is a lot less complicated, rapidly undoing the steps taken in parsing:
isa = isinstance
def to_string(exp):
"Convert a Python object again right into a Lisp-readable string."
if not isa(exp, checklist):
return str(exp)
else:
return '('+' '.be a part of(map(to_string, exp))+')'
In different phrases, if the interior illustration of the expression is just not a listing, then return an applicable stringified model (this takes care of the truth that we might have ints, floats and, as we will see, Booleans within the inner illustration). If it’s a checklist, then return no matter we get by making use of to_string to all the weather of that checklist, with applicable delimiting by whitespace and parentheses.
At this level, the primary factor we have to full tiddlylisp is the eval perform. Truly, that is not fairly true: as we mentioned earlier, tiddlylisp additionally retains observe of a worldwide atmosphere (and presumably a number of inside environments), to retailer variable and process names, and their values. eval goes to make heavy use of the environments, and so it helps to look first at how environments are outlined. They’re fairly easy: an atmosphere has a bunch of keys, representing the names of the variables and procedures in that atmosphere, and corresponding values for these keys, that are simply the values for the variables or procedures. An atmosphere additionally retains observe of its outer atmosphere, with the caveat that the worldwide atmosphere has an outer atmosphere set to Python’s None. Such environments are simply carried out as a subclass of Python dictionaries:
class Env(dict):
"An atmosphere: a dict of {'var':val} pairs, with an outer Env."
def __init__(self, params=(), args=(), outer=None):
self.replace(zip(params, args))
self.outer = outer
def discover(self, var):
"Discover the innermost Env the place var seems."
return self if var in self else self.outer.discover(var)
As you may see, the one modifications of the dictionary class are that: (1) an atmosphere additionally retains observe of its personal outer atmosphere; and (2) an atmosphere can decide whether or not a variable or process identify seems in its checklist of keys, and if it would not, then it seems to see if it is in its outer atmosphere. In consequence, the discover methodology returns the innermost atmosphere the place the variable or process identify seems.
Word, by the way, that the atmosphere would not distinguish between variable and process names. Certainly, as we’ll see, tiddlylisp treats user-defined procedures and variables in the identical manner: a process is a variable which simply occurs to take the worth of a lambda expression as its worth.
Tiddlylisp begins off working in a specific international atmosphere, and this too have to be outlined by our program. We’ll do that by creating an occasion of the category Env, and calling a perform so as to add some built-in process definitions and variables:
def add_globals(env):
"Add some built-in procedures and variables to the atmosphere."
import operator
env.replace(
{'+': operator.add,
'-': operator.sub,
'*': operator.mul,
'/': operator.div,
'>': operator.gt,
'=': operator.ge,
'
By the way, in tiddlylisp's model of add_globals I made a decision to strip out lots of the built-in procedures which Norvig contains in lispy's international atmosphere - it is instructive to have a look at Norvig's code for add_globals to see simply how straightforward it's so as to add extra built-in procedures to tiddlylisp. If you wish to do some exploratory programming with tiddlylisp then it is best to most likely copy a few of Norvig's extra built-in procedures (and maybe add a few of your personal). For us, although, the above procedures are sufficient.
One notable function of the worldwide atmosphere is the variables named True and False, which consider to Python's Boolean True and False, respectively. This is not commonplace in Scheme (or most different Lisps), however I've performed it as a result of it ensures that we are able to use the strings True and False, and get the suitable inner illustration.
With the worldwide atmosphere arrange, we are able to now perceive how eval works. The code is very simple, merely enumerating the various kinds of expressions we may be evaluating, and studying from or modifying the atmosphere, as applicable. It is price studying (and rereading) the code intimately, till you perceive precisely how eval works. I even have a couple of feedback on the finish. Here is the code:
isa = isinstance
def eval(x, env=global_env):
"Consider an expression in an atmosphere."
if isa(x, Image): # variable reference
return env.discover(x)[x]
elif not isa(x, checklist): # fixed literal
return x
elif x[0] == 'quote' or x[0] == 'q': # (quote exp), or (q exp)
(_, exp) = x
return exp
elif x[0] == 'atom?': # (atom? exp)
(_, exp) = x
return not isa(eval(exp, env), checklist)
elif x[0] == 'eq?': # (eq? exp1 exp2)
(_, exp1, exp2) = x
v1, v2 = eval(exp1, env), eval(exp2, env)
return (not isa(v1, checklist)) and (v1 == v2)
elif x[0] == 'automotive': # (automotive exp)
(_, exp) = x
return eval(exp, env)[0]
elif x[0] == 'cdr': # (cdr exp)
(_, exp) = x
return eval(exp, env)[1:]
elif x[0] == 'cons': # (cons exp1 exp2)
(_, exp1, exp2) = x
return [eval(exp1, env)]+eval(exp2,env)
elif x[0] == 'cond': # (cond (p1 e1) ... (pn en))
for (p, e) in x[1:]:
if eval(p, env):
return eval(e, env)
elif x[0] == 'null?': # (null? exp)
(_, exp) = x
return eval(exp,env) == []
elif x[0] == 'if': # (if check conseq alt)
(_, check, conseq, alt) = x
return eval((conseq if eval(check, env) else alt), env)
elif x[0] == 'set!': # (set! var exp)
(_, var, exp) = x
env.discover(var)[var] = eval(exp, env)
elif x[0] == 'outline': # (outline var exp)
(_, var, exp) = x
env[var] = eval(exp, env)
elif x[0] == 'lambda': # (lambda (var*) exp)
(_, vars, exp) = x
return lambda *args: eval(exp, Env(vars, args, env))
elif x[0] == 'start': # (start exp*)
for exp in x[1:]:
val = eval(exp, env)
return val
else: # (proc exp*)
exps = [eval(exp, env) for exp in x]
proc = exps.pop(0)
return proc(*exps)
Largely that is self-explanatory. However permit me to attract your consideration to how Norvig offers with nameless process definitions utilizing lambda. After I first examined his code I questioned how he'd address this, and anticipated it might be fairly advanced. However as you may see, this can be very easy: lambda expressions consider to the suitable nameless Python perform, with a brand new atmosphere modified by the addition of the suitable variable keys, and their values. Stunning!
Tiddlylisp is basically full at this level. It is handy to complete off this system by offering two methods of operating tiddlylisp: both in an interactive interpreter mode, i.e., the REPL, or by loading a tiddlylisp program saved in a separate file. To begin the REPL, we'll merely run python tiddlylisp.py. To load and execute a file, we'll run python tiddlylisp.py filename. After execution, we would prefer to be dropped into the REPL so we are able to examine outcomes and do additional experiments. The principle complication in doing that is the necessity to load tiddlylisp code which is cut up over a number of traces. We do that by merging traces till the variety of opening and shutting parentheses match. Here is the code - it is best to start out on the backside, with the code instantly after if __name__ == "__main__":
import sys
def load(filename):
"""
Load the tiddlylisp program in filename, execute it, and begin the
repl. If an error happens, execution stops, and we're left within the
repl. Word that load copes with multi-line tiddlylisp code by
merging traces till the variety of opening and shutting parentheses
match.
"""
print "Loading and executing
f = open(filename, "r")
program = f.readlines()
f.shut()
rps = running_paren_sums(program)
full_line = ""
for (paren_sum, program_line) in zip(rps, program):
program_line = program_line.strip()
full_line += program_line+" "
if paren_sum == 0 and full_line.strip() != "":
strive:
val = eval(parse(full_line))
if val is just not None: print to_string(val)
besides:
handle_error()
print "nThe line during which the error occurred:n
break
full_line = ""
repl()
def running_paren_sums(program):
"""
Map the traces within the checklist program to a listing whose entries comprise
a operating sum of the per-line distinction between the variety of '('
parentheses and the variety of ')' parentheses.
"""
count_open_parens = lambda line: line.rely("(")-line.rely(")")
paren_counts = map(count_open_parens, program)
rps = []
whole = 0
for paren_count in paren_counts:
whole += paren_count
rps.append(whole)
return rps
if __name__ == "__main__":
if len(sys.argv) > 1:
load(sys.argv[1])
else:
repl()
That completes the code for tiddlylisp! A grand whole of 153 traces of non-comment, non-whitespace code. Right here all of it is, in a single massive block (commented and barely reordered), so you may see how the items match collectively:
#### tiddlylisp.py
#
# Based mostly on Peter Norvig's lispy (http://norvig.com/lispy.html),
# copyright by Peter Norvig, 2010.
#
# Diversifications by Michael Nielsen. See
# https://michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/
import sys
import traceback
#### Image, Env courses
Image = str
class Env(dict):
"An atmosphere: a dict of {'var':val} pairs, with an outer Env."
def __init__(self, params=(), args=(), outer=None):
self.replace(zip(params, args))
self.outer = outer
def discover(self, var):
"Discover the innermost Env the place var seems."
return self if var in self else self.outer.discover(var)
def add_globals(env):
"Add some built-in procedures and variables to the atmosphere."
import operator
env.replace(
{'+': operator.add,
'-': operator.sub,
'*': operator.mul,
'/': operator.div,
'>': operator.gt,
'=': operator.ge,
' "):
"A prompt-read-eval-print loop."
whereas True:
strive:
val = eval(parse(raw_input(immediate)))
if val is just not None: print to_string(val)
besides KeyboardInterrupt:
print "nExiting tiddlylispn"
sys.exit()
besides:
handle_error()
#### error dealing with
def handle_error():
"""
Easy error dealing with for each the repl and cargo.
"""
print "An error occurred. Here is the Python stack hint:n"
traceback.print_exc()
#### on startup from the command line
if __name__ == "__main__":
if len(sys.argv) > 1:
load(sys.argv[1])
else:
repl()
Issues
- Modify tiddlylisp in order that the + process will be utilized to any variety of arguments, e.g., in order that (+ 1 2 3) evaluates to 6.
- Earlier we carried out a sq. root process in tiddlylisp. Are you able to add it on to tiddlylisp, utilizing the Python math module’s sqrt perform?
- In our earlier implementation of the sqrt process we mentioned the ordering of the traces of code, and whether or not it is okay to outline a process when it comes to another yet-to-be-defined process. Study the code for tiddlylisp, and clarify why it is okay for a process equivalent to sqrt to be outlined when it comes to a process equivalent to sqrt-iter which is not outlined till later. Strive doing the identical factor with variables, e.g., strive operating (outline x y) adopted by (outline y 1). Does this work? In that case, why? If not, why not?
- Modify tiddlylisp in order that when utilized to 1 argument the - process merely negates it, e.g., (- 2) returns -2, whereas - nonetheless computes variations when utilized to two arguments.
- Is it potential to put in writing a pure tiddlylisp process minus so that (minus x) returns -x, whereas (minus x y) returns x-y?
- Within the dialogue the place we launched cond I acknowledged that (cond (p1 e1)...(pn en)) is undefined when not one of the expressions p1…pn consider to True. What does Tiddlylisp return on this case? Are you able to consider a greater manner of coping with this example?
- Are you able to add help for strings to tiddlylisp?
After I first examined Norvig’s code for lispy, I used to be shocked by simply how a lot I discovered from his code. In fact, I anticipated to be taught fairly a bit – I’m only a newbie at Lisp – however what I discovered significantly exceeded my expectations. Why would possibly writing an interpreter deepen our understanding of a programming language? I feel the reply has to do with how we perceive abstractions. Think about the best way I first defined the idea of Lisp environments, early on this essay: I gave a common dialogue of the idea, after which associated it to a number of of the examples we have been working by way of. That is the same old manner we address abstractions when studying (or instructing) a language: we make these abstractions concrete by working by way of code examples that illustrates the results of these abstractions. The issue is that though I can present you examples, the abstraction itself stays ephemeral.
Writing an interpreter is a manner of constructing a programming language’s abstractions concrete. I can present you 1,000,000 examples illustrating penalties of the Lisp atmosphere, however none can have fairly the identical concrete flavour because the code for our Python Lisp interpreter. That code exhibits explicitly how the atmosphere will be represented as a knowledge construction, how it’s manipulated by instructions equivalent to outline, and so forth. And so writing an interpreter is a manner of reifying abstractions within the programming language being interpreted.
Issues
- I gave the instance of the atmosphere as a Lisp abstraction which is made extra concrete if you perceive the code for the interpreter. One other instance of an abstraction is errors in code. Are you able to enhance tiddlylisp’s error dealing with in order that we get one thing extra informative than a Python stack hint when one thing goes mistaken? One suggestion for a way to do that is to determine two (or extra) courses of error that will happen in tiddlylisp applications, and to modify the interpreter so it catches and gracefully handles these error courses, printing informative error messages.
On Peter Norvig’s webpage describing his interpreter, a couple of commenters take him to process for writing his interpreter in Python. Here is an example to provide the flavour of those feedback:
This code seems very good, however i believe that implementing a Lisp Interpreter in Python is a few type of dishonest. Python is a high-level language, so that you get very a lot at no cost.
Norvig replies:
You might be proper — we’re counting on many options of Python: name stack, knowledge varieties, rubbish assortment, and so on. The subsequent step can be to point out a compiler to some form of meeting language. I feel both the Java JVM or the Python byte code can be good targets. We would additionally want a runtime system with GC. I present the compiler in my PAIP [Paradigms of Artificial Intelligence] book.
The commenter and Norvig are proper, in some sense. However there’s additionally a way during which the Python interpreter achieves one thing that may not be achieved by a program that compiled Lisp to the Java JVM, or to assembler, or another goal nearer to the naked metallic. That is due to all programming languages, Python is without doubt one of the closest to an abnormal human language. And so writing a Lisp interpreter in Python is an exceptionally clear manner of explaining how Lisp works to a human who would not but perceive the core ideas of Lisp. Insofar as I can guess at Norvig’s intention, I consider the code for his interpreter is primarily supposed to be learn by people, and the truth that it can be learn by a pc is a design constraint, not the elemental objective [3].
It appears to me that the type of remark above arises as a result of there are actually three pure variations on the query “Methods to clarify Lisp?”. All three variations are attention-grabbing, and value answering; all three have totally different solutions. The primary variation is the right way to clarify Lisp to an individual who would not but know Lisp. As I’ve simply argued, a very good reply to this query is to work by way of some examples, after which to put in writing a easy Python interpreter. The second variation is the right way to clarify Lisp to a machine. That is the query the commenter on Norvig’s weblog is asking, and to reply that query nothing beats writing a Lisp interpreter (or compiler) that works near the naked metallic, say in assembler, requiring you to deal explicitly with reminiscence allocation, rubbish assortment, and so forth.
However there’s additionally a 3rd variation on the query. And that is how greatest to clarify Lisp to somebody who already understands the core ideas of Lisp. That sounds paradoxical: would not such an individual, by definition, already perceive Lisp? Nevertheless it’s not paradoxical in any respect. Think about the next expertise which many individuals have when studying (or instructing) arithmetic. The easiest way to clarify a mathematical concept to somebody new to the concept is utilizing their outdated language and their outdated manner of wanting on the world. That is like explaining Lisp by writing a Python interpreter. However as soon as the individual has grasped a transformative new mathematical concept, they will usually deepen their understanding by re-examining that concept inside their new manner of wanting on the world. That re-examination can assist crystallize a deeper understanding. In an analogous manner, whereas writing a Lisp interpreter in Python could also be a great way of explaining Lisp to an individual who would not but perceive Lisp, somebody who grasps the core concepts of Lisp might discover the Python interpreter a bit of clunky. How ought to we clarify Lisp inside the framework of Lisp itself? One reply to that query is to make use of Lisp to put in writing a Lisp interpreter. It is to that process that we now flip.
Lisp in Lisp
How ought to we write a Lisp interpreter in Lisp? Let’s assume again to what Alan Kay noticed on the backside of web page 13 of the LISP Guide:
Though it is written in a unique notation than we have used, that is Lisp code. In reality, it is the core of a Lisp interpreter written in Lisp: the process evalquote takes a Lisp expression as enter, after which returns the worth of that expression. On this part we will use tiddlylisp to put in writing an analogue to evalquote (we’ll change the identify to eval). In fact, such a process is just not actually a full interpreter – we can’t have a read-eval-print loop, for one factor – nevertheless it’s not troublesome to increase our code to a full interpreter (it requires a couple of additions to tiddlylisp, too). For that reason, in what follows I will confer with our eval process as an “interpreter”, despite the fact that it is extra correct to say that it is the core of an interpreter. I have never made the extension to a full interpreter right here, partly as a result of I do not wish to lengthen an already lengthy essay, however largely as a result of I wish to stick with the theme of the “Maxwell’s equations of software program”. For a similar causes, I’ve additionally restricted our eval to decoding solely a subset of tiddlylisp, omitting the arithmetical operations and concentrating as a substitute on procedures for manipulating lists.
My therapy on this part is predicated on a stupendous essay (postscript) by Paul Graham, during which he explains what the unique designer of Lisp, John McCarthy, was as much as in the paper the place he launched Lisp. In his essay, Graham writes a totally executable Lisp interpreter in one of many fashionable dialects of Lisp, Frequent Lisp, and I’ve based mostly a lot of my code on Graham’s. Maybe the primary distinction in my therapy is that whereas Graham’s eval is written to be run underneath Frequent Lisp, our eval is executable in tiddlylisp, an interpreter for Lisp that we have written ourselves (with a number of assist from Peter Norvig!) So despite the fact that the code could be very related, the angle is sort of diferent, and I feel we acquire one thing from this totally different perspective.
The code we’ll write is longer than what you see on web page 13 of the LISP Guide. The reason being that the code on web page 13 was not really self-contained, however made use of a number of procedures outlined earlier within the LISP Guide, and we have to embody these procedures. The ultimate consequence remains to be solely a bit of over a web page of code. Let’s begin by defining a couple of of these helper procedures.
(not exp) returns True if the expression exp evaluates to False, and in any other case returns False. For instance,
tiddlylisp> (not (atom? (q (1 2)))) True tiddlylisp> (not (eq? 1 (- 2 1))) False
Here is the tiddlylisp code for not:
(outline not (lambda (x) (if x False True)))
(append exp1 exp2) takes expressions exp1 and exp2 each of whose values are lists, and returns the checklist fashioned by concatenating these lists. For instance,
tiddlylisp> (append (q (1 2 3)) (q (4 5))) (1 2 3 4 5)
Here is the tiddlylisp code for append:
(outline append (lambda (x y) (if (null? x) y (cons (automotive x) (append (cdr x) y)))))
(pair exp1 exp2) returns a two-element checklist whose components are the worth of exp1 and the worth of exp2:
tiddlylisp> (pair 1 2) (1 2) tiddlylisp> (pair (+ 1 2) 1) (3 1)
Here is the tiddlylisp code for pair:
(outline pair (lambda (x y) (cons x (cons y (q ()) ))))
Word that my use of pair is considerably unconventional – the extra common strategy in Lisp is to make use of (checklist exp1 exp2 exp3…) to assemble a listing whose values are simply the values of the respective expressions. The explanation I have never performed it is because tiddlylisp would not permit us to outline Lisp procedures with a variable variety of arguments. Word additionally that the process pair that I’ve outlined shouldn’t be confused with one among Scheme’s commonplace procedures, pair?, which has a unique objective, and which we can’t use within the present essay.
Issues
- Are you able to modify tiddlylisp in order that (checklist exp1 exp2 exp3…) does certainly return a listing whose values are simply the values of the respective expressions?
I will now introduce a category of helper procedures that are concatenations of two or extra purposes of automotive or cdr. An instance is the process cdar, which applies automotive first, adopted by cdr, that’s, (cdar exp) has the identical worth as (cdr (automotive exp)). The notation cdar is a mnemonic, whose key components are the center two letters, d and a, indicating that cdar is what you get if you apply (in reverse order) cdr and automotive. You would possibly marvel why it is reverse order – the reply is that reverse order corresponds to the visible syntactic order, that’s, the order from left-to-right that the procedures seem within the expression (cdr (automotive exp)).
As one other instance, the process caar is outlined in order that (caar exp) has the identical worth as (automotive (automotive exp)). In our eval it will be useful to make use of a number of such procedures:
(outline caar (lambda (x) (automotive (automotive x)))) (outline cadr (lambda (x) (automotive (cdr x)))) (outline cadar (lambda (x) (cadr (automotive x)))) (outline caddr (lambda (x) (cadr (cdr x)))) (outline caddar (lambda (x) (caddr (automotive x))))
Our subsequent helper process is named pairlis. (pairlis exp1 exp2) takes expressions exp1 and exp2 whose values are lists of the identical size, and returns a listing which is fashioned by pairing the values of corresponding components. For instance,
tiddlylisp> (pairlis (q (1 2 3)) (q (4 5 6))) ((1 4) (2 5) (3 6))
Here is the tiddlylisp code for pairlis:
(outline pairlis
(lambda (x y)
(if (null? x)
(q ())
(cons (pair (automotive x) (automotive y)) (pairlis (cdr x) (cdr y))))))
We’ll name a listing of pairs equivalent to that produced by pairlis an affiliation checklist. It will get this identify from our closing helper process, the assoc process, which takes an affiliation checklist and treats it as a lookup dictionary. The best solution to clarify what this implies is thru an instance,
tiddlylisp> (outline a (pairlis (q (1 2 3)) (q (4 5 6)))) tiddlylisp> a ((1 4) (2 5) (3 6)) tiddlylisp> (assoc 2 a) 5
In different phrases, assoc seems for the important thing 2 as the primary entry in one of many pairs within the checklist which is the worth of a. As soon as it finds such a pair, it returns the second aspect within the pair.
Acknowledged extra abstractly, suppose the expression exp1 has a worth which seems as the primary entry in one of many pairs within the affiliation checklist which is the worth of exp2. Then (assoc exp1 exp2) returns the second entry of that pair.
In any case that clarification, the code for assoc is very simple, less complicated even than pairlis:
(outline assoc (lambda (x y) (if (eq? (caar y) x) (cadar y) (assoc x (cdr y)))))
I will not clarify how assoc works, however when you’re on the lookout for a very good train in making use of caar and related procedures, then it is price spending a while to rigorously perceive how assoc works.
With all these helper procedures in place, we are able to now write our equal to the code on web page 13 of the LISP Guide. This contains each the core process, eval, along with a few further helper procedures, evcon and evlis. Here is the code:
(outline eval
(lambda (e a)
(cond
((atom? e) (assoc e a))
((atom? (automotive e))
(cond
((eq? (automotive e) (q automotive)) (automotive (eval (cadr e) a)))
((eq? (automotive e) (q cdr)) (cdr (eval (cadr e) a)))
((eq? (automotive e) (q cons)) (cons (eval (cadr e) a) (eval (caddr e) a)))
((eq? (automotive e) (q atom?)) (atom? (eval (cadr e) a)))
((eq? (automotive e) (q eq?)) (eq? (eval (cadr e) a) (eval (caddr e) a)))
((eq? (automotive e) (q quote)) (cadr e))
((eq? (automotive e) (q q)) (cadr e))
((eq? (automotive e) (q cond)) (evcon (cdr e) a))
(True (eval (cons (assoc (automotive e) a) (cdr e)) a))))
((eq? (caar e) (q lambda))
(eval (caddar e) (append (pairlis (cadar e) (evlis (cdr e) a)) a))))))
(outline evcon
(lambda (c a)
(cond ((eval (caar c) a) (eval (cadar c) a))
(True (evcon (cdr c) a)))))
(outline evlis
(lambda (m a)
(cond ((null? m) (q ()))
(True (cons (eval (automotive m) a) (evlis (cdr m) a))))))
Earlier than we study how eval works, I wish to provide you with some examples of eval in motion. If you need, you may observe together with the examples by first loading this system defining eval into tiddlylisp (the total supply is under), after which typing the examples into the interpreter.
To know the right way to use eval in examples, we should be clear concerning the that means of its arguments. e is a Lisp expression whose worth is the Lisp expression that we wish to consider with eval. And a is a Lisp expression whose worth is an affiliation checklist, representing the atmosphere. Particularly, the primary aspect of every pair in a is the identify of a variable or process, and the second aspect is the worth of that variable or process. I will usually confer with a simply because the atmosphere.
Suppose, for instance, that we wished to make use of eval to judge the expression (automotive (q (1 2))). We’ll assume that we’re evaluating it within the empty atmosphere, that’s, no variables or further procedures have been outlined. Then we would must go eval expressions with values (automotive (q (1 2))) and (). We are able to do that by quoting these values:
tiddlylisp> (eval (q (automotive (q (1 2)))) (q ())) 1
As you may see, we get the fitting consequence: 1.
I defined intimately the right way to construct up the expression (eval (q (automotive...) evaluated above. But when we hadn’t gone by way of that clarification, then the expression would have appeared fairly of sophisticated, with a number of quoting occurring. The reason being that eval is evaluating an expression which is itself the worth of one other expression. With a lot analysis occurring it is no marvel there’s many q‘s floating round! However after working rigorously by way of a couple of examples all of it turns into clear.
Here is an instance exhibiting the right way to use variables within the atmosphere:
tiddlylisp> (eval (q (cdr x)) (q ((x (1 2 3))))) (2 3)
Unpacking the quoting, we see that it is evaluating the expression (cdr x) in an atmosphere with a variable x whose worth is (1 2 3). The result’s, in fact, (2 3).
Here is an instance exhibiting the right way to use a process which has been outlined within the atmosphere:
tiddlylisp> (eval (q (cddr (q (1 2 3 4 5)))) (q ((cddr (lambda (x) (cdr (cdr x))))))) (3 4 5)
In different phrases, the atmosphere shops a process cddr whose worth is (lambda (x) (cdr (cdr x))), and eval returns the results of making use of cddr to an expression whose worth is (1 2 3 4 5). In fact, that is simply (3 4 5).
We are able to additionally use eval to outline and consider an nameless process, on this case one which has the identical impact as cadr:
tiddlylisp> (eval (q ((lambda (x) (automotive (cdr x))) (q (1 2 3 4)))) (q ())) 2
A major downside of eval is that it has a fairly restricted Lisp vocabulary. You may see this by operating:
tiddlylisp> (eval (q (eq? 1 1)) (q (())))
The primary line seems like completely legitimate Lisp – in truth, it’s completely legitimate Lisp. The issue is that eval would not acknowledge 1 – on the stage of sophistication we’re working it actually solely understands lists, variables, and procedures. So what it tries to do is deal with 1 as a variable or process to search for within the atmosphere, a. However 1 is not within the atmosphere, which is why there’s an error message.
Fixing this downside by modifying eval is not terribly troublesome [4]. Nevertheless, to remain near the LISP Guide, I will go away this as is. A kludge to get round this situation is so as to add 1 as a key within the atmosphere. For instance, we are able to use:
tiddlylisp> (eval (q (eq? 1 1)) (q ((1 1)))) True tiddlylisp> (eval (q (eq? 1 2)) (q ((1 1) (2 2)))) False
That is precisely as anticipated. We did not see this downside in our earlier examples of eval, just because they concerned checklist manipulations which did not require us to judge numbers equivalent to 1. By the way, this is an amusing variation on the above kludge:
tiddlylisp> (eval (q (eq? 1 2)) (q ((1 1) (2 1)))) True
In different phrases, if we inform our interpreter emphatically sufficient that 1 = 2 then it is going to begin to consider it!
Simply to place eval by way of its paces, let’s add a bundle of checks of fundamental performance. It is not an exhaustive check suite, however not less than checks that the essential procedures are working as we anticipate. You need not learn by way of the next check code in exhaustive element, though it is best to learn not less than the primary few traces, to get a sense for what is going on on. Word that in a couple of of the traces we have to add one thing like 1 or 2 to the atmosphere, so that eval be capable to consider it, as occurred within the instance simply above.
(outline assert-equal (lambda (x y) (= x y))) (outline assert-not-equal (lambda (x y) (not (assert-equal x y)))) (assert-equal (eval (q x) (q ((x test-value)))) (q test-value)) (assert-equal (eval (q y) (q ((y (1 2 3))))) (q (1 2 3))) (assert-not-equal (eval (q z) (q ((z ((1) 2 3))))) (q (1 2 3))) (assert-equal (eval (q (quote 7)) (q ())) (q 7)) (assert-equal (eval (q (atom? (q (1 2)))) (q ())) False) (assert-equal (eval (q (eq? 1 1)) (q ((1 1)))) True) (assert-equal (eval (q (eq? 1 2)) (q ((1 1) (2 2)))) False) (assert-equal (eval (q (eq? 1 1)) (q ((1 1)))) True) (assert-equal (eval (q (automotive (q (3 2)))) (q ())) (q 3)) (assert-equal (eval (q (cdr (q (1 2 3)))) (q ())) (q (2 3))) (assert-not-equal (eval (q (cdr (q (1 (2 3) 4)))) (q ())) (q (2 3 4))) (assert-equal (eval (q (cons 1 (q (2 3)))) (q ((1 1)(2 2)(3 3)))) (q (1 2 3))) (assert-equal (eval (q (cond ((atom? x) (q x-atomic)) ((atom? y) (q y-atomic)) ((q True) (q nonatomic)))) (q ((x 1)(y (3 4))))) (q x-atomic)) (assert-equal (eval (q (cond ((atom? x) (q x-atomic)) ((atom? y) (q y-atomic)) ((q True) (q nonatomic)))) (q ((x (1 2))(y 3)))) (q y-atomic)) (assert-equal (eval (q (cond ((atom? x) (q x-atomic)) ((atom? y) (q y-atomic)) ((q True) (q nonatomic)))) (q ((x (1 2))(y (3 4))))) (q nonatomic)) (assert-equal (eval (q ((lambda (x) (automotive (cdr x))) (q (1 2 3 4)))) (q ())) 2)
In tiddlylisp, maybe the simplest manner to make use of this check code is to append it on the backside of the file the place we outline eval. Then, after we load that file into reminiscence, the checks run robotically. If all the things is working correctly, then all of the checks ought to consider to True.
How does eval work? Wanting again on the code, we see that it is only a massive cond assertion, whose worth is set by which of assorted situations consider to True. The cond assertion begins off:
(cond
((atom? e) (assoc e a))
...
To know what this accomplishes, it’s useful to keep in mind that what we’re most inquisitive about is the worth of e, not e itself. Let’s use e' to indicate the worth of e, i.e., e' is the Lisp expression that we really wish to consider utilizing eval. Then what the situation above does is test whether or not e' is atomic, and in that case it returns the worth of the corresponding variable or process within the atmosphere, precisely as we would anticipate.
Let us take a look at the following line within the massive outer conditional assertion:
((atom? (automotive e))
At this stage, we all know that e' is not atomic, since we already checked for that, and so e' have to be a listing. This line checks to see whether or not the primary aspect of e' is itself an atom. Whether it is, then there are a number of potentialities: it could possibly be a particular type, equivalent to quote, or a built-in process, equivalent to automotive, or else a process that is outlined within the atmosphere. To test which of those potentialities is the case, we consider one other (nested) conditional assertion. This simply checks off the totally different instances, as an example the primary line of the nested conditional checks to see if we’re making use of the process automotive, and in that case proceeds appropriately,
((eq? (automotive e) (q automotive)) (automotive (eval (cadr e) a)))
In different phrases, if the primary image in e' is automotive, then extract no matter expression is being handed to automotive, utilizing (cadr e), then consider that expression utilizing (eval (cadr e) a), and at last extract the primary aspect, utilizing (automotive (eval...)). That is precisely what we would anticipate automotive to do. A lot of the remainder of this nested conditional assertion works alongside related traces, as you may test your self. The ultimate line is attention-grabbing, and deserves remark:
(True (eval (cons (assoc (automotive e) a) (cdr e)) a))))
This line is evaluated when the expression e' doesn’t begin with a particular type or built-in process, however as a substitute begins with the identify of a process outlined within the atmosphere. To know what’s returned, be aware that (automotive e) retrieves the identify of the process, so (assoc (automotive e) a) can retrieve the process from the atmosphere, after which (cons (assoc (automotive e) a) (cdr e)) appends the arguments to the process. The entire thing is then evaluated. It is all fairly easy and chic!
Shifting again into the outer cond assertion, the ultimate situation is as follows:
((eq? (caar e) (q lambda)) (eval (caddar e) (append (pairlis (cadar e) (evlis (cdr e) a)) a))))))
This happens when evaluating a quoted expression of the shape ((lambda (x…|) exp). The primary line merely checks that we’re, certainly, seeing a lambda expression. The caddar e extracts the expression exp from the physique of the lambda expression. We consider this within the context of an atmosphere which has modified by appending some new variable names (extracted with cadar e), utilizing pairlis to pair them with their values, that are evaluated utilizing evlis (which you’ll be able to work by way of your self). As soon as once more, it is all fairly easy and neat – a reality which speaks to the marvellous class of the design introduced within the LISP Guide (and, finally, resulting from John McCarthy).
It will not have escaped your consideration that our Lisp eval is similar to the eval we wrote earlier in Python. Tiddlylisp is considerably totally different to the dialect of Lisp our eval interprets, however the implementation is recognizably related. It’s a matter of style, however I feel the Lisp implementation is extra elegant. It is true that the Lisp code is superficially a bit of extra advanced – it depends extra on ideas outdoors our on a regular basis expertise, such because the procedures caar, cadar, and so forth. Nevertheless it makes up for that by possessing a larger conceptual economic system, in that we’re utilizing ideas equivalent to automotive, cdr and cond to put in writing an interpreter which understands these exact same ideas.
Here is the total code for our Lisp interpreter in tiddlylisp. You must append the check code given above, and reserve it all as a single file, eval.tl.
(outline caar (lambda (x) (automotive (automotive x))))
(outline cadr (lambda (x) (automotive (cdr x))))
(outline cadar (lambda (x) (cadr (automotive x))))
(outline caddr (lambda (x) (cadr (cdr x))))
(outline caddar (lambda (x) (caddr (automotive x))))
(outline not (lambda (x) (if x False True)))
(outline append (lambda (x y)
(if (null? x) y (cons (automotive x) (append (cdr x) y)))))
(outline pair (lambda (x y) (cons x (cons y (q ()) ))))
(outline pairlis
(lambda (x y)
(if (null? x)
(q ())
(cons (pair (automotive x) (automotive y)) (pairlis (cdr x) (cdr y))))))
(outline assoc (lambda (x y)
(if (eq? (caar y) x) (cadar y) (assoc x (cdr y)))))
(outline eval
(lambda (e a)
(cond
((atom? e) (assoc e a))
((atom? (automotive e))
(cond
((eq? (automotive e) (q automotive)) (automotive (eval (cadr e) a)))
((eq? (automotive e) (q cdr)) (cdr (eval (cadr e) a)))
((eq? (automotive e) (q cons)) (cons (eval (cadr e) a) (eval (caddr e) a)))
((eq? (automotive e) (q atom?)) (atom? (eval (cadr e) a)))
((eq? (automotive e) (q eq?)) (eq? (eval (cadr e) a) (eval (caddr e) a)))
((eq? (automotive e) (q quote)) (cadr e))
((eq? (automotive e) (q q)) (cadr e))
((eq? (automotive e) (q cond)) (evcon (cdr e) a))
(True (eval (cons (assoc (automotive e) a) (cdr e)) a))))
((eq? (caar e) (q lambda))
(eval (caddar e) (append (pairlis (cadar e) (evlis (cdr e) a)) a))))))
(outline evcon
(lambda (c a)
(cond ((eval (caar c) a) (eval (cadar c) a))
(True (evcon (cdr c) a)))))
(outline evlis
(lambda (m a)
(cond ((null? m) (q ()))
(True (cons (eval (automotive m) a) (evlis (cdr m) a))))))
It is instructive to match our eval to what Kay noticed on web page 13 of the LISP 1.5 Programmer’s Guide:
Clearly, what we have written is longer than that half-page! Nevertheless, as I discussed earlier, that half-page omitted the code for helper procedures equivalent to caar, append, and so forth, which have been outlined earlier within the LISP Guide. A extra direct comparability is to our code for the eval, evcon and evlis procedures.
When you examine our code to the LISP Guide, a couple of variations leap out. The obvious is that the LISP Guide’s evalquote, apply and eval have all been mixed into one process. This can be a type of group I adopted from Paul Graham’s eval, and it makes it a lot simpler to see what’s going on, within the outer cond. Particularly, the outer cond has a quite simple construction: (1) if the expression we’re tring to judge is an atom, return its worth; in any other case (2) the expression have to be a listing, so test to see if the primary aspect is an atom, during which case it have to be a particular type or process, and must be evaluated appropriately (that is the inside cond); and in any other case (3) we have to be coping with a lambda expression.
Situation (3) is attention-grabbing. With the syntax we’re utilizing, the situation in step (3) might merely be expressed as True, not (eq? (caar e) (q lambda), because it’s the one remaining risk. This may, in some sense, simplify (and pace up) the code. Nevertheless, it might additionally make it more durable to know the intent of the code.
One thing that you could be be aware was current within the LISP Guide however which is lacking from our eval is the particular type label. label was used within the LISP Guide to present names to procedures, and in order that process definitions might refer recursively to themselves. It is solely a few traces so as to add again in, however I have never performed so. If you would like, it is a enjoyable problem so as to add this performance again in, and so I’ve given this as an issue under.
Issues
- How might you add a facility to eval in order that process definitions can confer with themselves? When you’re having bother with this downside, you may get a touch by wanting on the code from web page 13 of the LISP Guide. A whole resolution to the issue could also be discovered in Paul Graham’s essay about the roots of Lisp.
This can be a good little interpreter. Nevertheless, it has many limitations, even when in comparison with tiddlylisp. It could actually’t do fundamental arithmetic, would not address integers, a lot much less extra sophisticated knowledge varieties, it would not actually have a manner of outlineing variables (in any case, it would not return a modified atmosphere). Nonetheless, it already accommodates lots of the core ideas of Lisp, and it truly is an executable counterpart to what Alan Kay noticed on web page 13 of the LISP 1.5 Guide.
What can we be taught from this interpreter for Lisp in Lisp? As an mental train, it is cute, however past that, so what? Let’s take into consideration the analogous query for Python, i.e., writing a Python perform that may return the worth of Python expressions. In some sense, fixing this downside is a trivial one-liner, since Python has a built-in perform referred to as eval that’s able to evaluating Python expressions.
What if, nonetheless, we eradicated eval (and related capabilities) from Python? What then? Nicely, a Python model of eval can be rather more sophisticated than our Lisp eval. Python is way much less common language than Lisp, and this makes it rather more sophisticated for it to cope with Python code. In contrast, Lisp has an very simple syntax, and is designed to control its personal code as knowledge. That is all mirrored within the simplicity of the interpreter above.
Past this, the code for eval is a stupendous expression of the core concepts of Lisp, written in Lisp. It is true that our eval implements a really incomplete model of Lisp, however with just a bit elaboration we are able to add help for arithmetic, extra superior management buildings, and so forth – all the things wanted to make this an basically full fundamental Lisp. And so we’d like solely a bit of poetic license to say that, simply as with Maxwell’s equations and electromagnetism, there’s a sense during which when you can have a look at this compact little program and perceive all its penalties, then you definitely perceive all that Lisp can do. And since Lisp is common, that implies that inside these few traces of code is all a pc can do – all the things from Area Invaders to laptop fashions of local weather to the Google search engine. In that sense this elegant little program actually is the Maxwell’s equations of software program.
Issues
- Define a proof that (eval (q (exp)) a) returns the worth of exp within the atmosphere a for all expressions exp and environments a if and provided that the underlying Lisp interpreter is right. This little theorem will be thought of a proper manner of stating that eval accommodates all of Lisp. The explanation I ask for a top level view proof solely is that numerous components within the assertion aren’t outlined in addition to they should be to make this a rigorous consequence; nonetheless, a compelling define proof is potential.
- Prolong the code given for eval as a way to implement a full read-eval-print loop. This can require you to increase tiddlylisp in order that it may possibly address enter and output, and (maybe) some form of looping.
- Having labored by way of eval.tl, it ought to now be straightforward to work by way of the primary chapter of the LISP 1.5 Programmer’s Guide. Download the LISP manual and work by way of the primary chapter, together with the code on web page 13.
Issues for the creator
- Is it potential to change the above Lisp-in-Lisp in order that it interprets all of tiddlylisp? Word that this may require modification of tiddlylisp.
Acknowledgements
Due to Jen Dodd for a lot of useful discussions.
Footnote
[1] I am paraphrasing, since this was 17 years in the past, however I consider I’ve reported the essence of the feedback appropriately. I’ve taken one liberty, which is in supplying my very own set of examples (antennas, motors, and circuits), since I do not recall the examples he gave. By the way, his feedback comprise a typical error that took me a number of years to kind out in my very own pondering: Maxwell’s equations really do not utterly specify electromagnetism. For that, it’s essential to increase them with one further equation, the Lorentz force law. It’s, maybe, unfair to characterize this as an error, since it is a frequent useage to equate Maxwell’s equations with electromagnetism, and I’ve little question my professor was conscious of the nuance. Nonetheless, whereas the useage is frequent, it is not right, and you actually do want the Lorentz pressure legislation as nicely. This nuance creates a slight quandary for me on this essay. Because the title of the essay suggests, it explores a well-known comment made by Alan Kay about what he referred to as “the Maxwell’s equations of software program”, and I presume that in making this comment Kay was following the frequent useage of equating the results of Maxwell’s equations with the entire of electromagnetism. My quandary is that this: on the one hand I do not want to perpetuate this useage; however I feel Kay’s formulation is stimulating and chic. So I will undertake the identical useage, however with the admonishment that it is best to learn “Maxwell’s equations” as synonomous with “Maxwell’s equations plus the Lorentz pressure legislation”. That set of 5 equations actually does specify the entire of (classical) electromagnetism. [2] I first encountered lambda in Python, not Lisp, however I consider I might have been perplexed for a similar purpose even when I might first encountered it in Lisp. [3] With a hat tip to Abelson and Sussman, who famously wrote “applications have to be written for folks to learn, and solely by the way for machines to execute”. [4] The best options I can consider are: (1) to present eval the flexibility to find out when some key is just not within the atmosphere; or (2) to present eval the flexibility to acknowledge numbers. Each approaches appear to additionally require making some modifications to tiddlylisp.Additional studying
A lot of Alan Kay’s writing could also be discovered on the web site of the Viewpoints Research Institute. I additionally suggest shopping his list of recommended reading.
Lisp enjoys a plethora of insightful and fantastically written books and essays, lots of them freely obtainable on-line. This essay is, in fact, based mostly principally on Peter Norvig’s essay on his basic Lisp interpreter, lispy. I’ve additionally drawn a couple of concepts from a followup essay of Norvig’s which describes a more sophisticated Lisp interpreter. Each essays (and the accompanying code) are marvellously elegant, and nicely price working by way of. Norvig’s other works are additionally price your time. The primary three chapters of Norvig’s ebook Paradigms of Artificial Intelligence Programming are a superb introduction to Frequent Lisp.
The opposite principal inspiration for the present essay is Paul Graham’s essay The Roots of Lisp (postscript file), the place he explains John McCarthy’s early concepts about Lisp. My essay could also be seen as an try and remix the concepts in Norvig’s and Graham’s essays, in an try to higher perceive Alan Kay’s comment about Lisp-as-Maxwell’s-Equations. I additionally suggest Graham’s ebook “On Lisp”, which accommodates a superb dialogue of Lisp macros and plenty of different topics. The ebook appears to be out of print, however due to Graham and the writer Prentice Corridor the textual content of all the ebook is freely available online. Word that I’m nonetheless working by way of “On Lisp”, I’ve not but learn it to completion. The identical is true of the books I point out under, by Seibel, and by Abelson and Sussmann.
Though “On Lisp” is a marvellous ebook, it is not written for folks new to Lisp. To realize familiarity, I recommend working by way of the primary three chapters of Norvig’s ebook, talked about above. If that is not obtainable, then it is best to check out Peter Seibel‘s ebook Practical Common Lisp. It is freely obtainable on the hyperlink, and offers an simply readable introduction to Frequent Lisp.
Lastly, I need to suggest the great ebook by Abelson and Sussman on the Structure and Interpretation of Computer Programs. Amongst different issues, it is an introduction to the Scheme dialect of Lisp, nevertheless it’s about rather more than that; it is about how to consider programming. It is a well-known ebook, however for a very long time I prevented taking a look at it, as a result of I might in some way picked up the impression that it was a bit of dry. I began studying, and located this impression was utterly false: I used to be completely gripped. A lot of “On Lisp” and “Paradigms of Synthetic Intelligence Programming” even have this high quality. Abelson and Sussmann’s ebook is freely available online.
Excited by extra? Please subscribe to this blog, or follow me on Twitter. You may additionally get pleasure from studying my new ebook about open science, Reinventing Discovery.