### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# COMPILER CONSTRUCTION CSCE 531

GPA 3.61

### View Full Document

## 56

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 13 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 531 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 56 views. For similar materials see /class/229585/csce-531-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for COMPILER CONSTRUCTION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

The Roots of Lisp PAUL GRAHAM Draft January 8 2002 In 1960 John McCarthy published a remarkable paper in which he did for pro gramming something like what Euclid did for geome 3 He showed how given a handful of simple operators and a notation for functions you can build a whole programming language He called this language Lisp for List Process in because one of his key ideas was to use a simple data structure called a his for both code and data It s worth understanding what McCarthy discovered not just as a landmark in the history of computers but as a model for what programming is tending to become in our own time It seems to me that there have been two really clean consistent models of programming so far the C model and the Lisp model These two seem points of high ground with swampy lowlands between them As computers have grown more powerful the new languages being developed have been moving steadily toward the Lisp model A popular recipe for new programming languages in the past 20 years has been to take the C model of computing and add to it piecemeal parts taken from the Lisp model like runtime typing and garbage collection In this article I m going to try to explain in the simplest possible terms what McCarthy discovered The point is not just to learn about an interest ing theoretical result someone gured out forty years ago but to show where languages are heading The unusual thing about Lispquot in fact the de ning quality of Lisp39 quot that it can be written in itself To understand what 7 Carthy meant by this were going to retrace his steps with his mathematica notation translated into running Common Lisp code 1 Seven Primitive Operators To start with we de ne an cazprc vim An expression is either an atam which is a sequence of letters e g foo or a list of zero or more expressions separated by whitespace and enclosed by parentheses Here are some expressions foo 0 foo foo bar a b c d The last expression is a list of four elements the third of which is itself a list of one element Recumive Junctions of ymlmlic prmssions and Their Computation by M achine Part Iquot Communications of the ACM 34 April 1960 pp 184 190 In arithmetic the exprec ion 1 1 has the value 2 Valid Lisp expressions also have values If an expression lds a value v we say that returns Our next step is to de ne what kinds of expressions there can be and what value each kind returns If an expression is a list we call the rst element the Operator and the remaining elements the arguments We are going to de ne seven primitive in the sense of axioms operators quote atom eq car cdr cons and cond 1 quote 2 returns ax For readability we will abbreviate quote 2 as x gt quote a a gt a a gt quote a b c a b c N atom 2 returns the atom t if the value of a is an atom or the empty list Otherwise it returns In Lisp we conventionally use the atom t to represent truth and the empty list to represent falsity gt atom a t gt atom a b c gt atom 1 Now that we have an operator whose argument is evaluated we can show what quote is for By quoting a list we protect it from evaluation An unquoted list given as an argument to an operator like atom is treated as code gt atom atom a 1 whereas a quoted list is treated as mere list in this case a list of two elements gt atom atom a This corresponds to the way we use quotes in English Cambridge is a town in Ivlassachusetts that contains about 90000 people Cambridge is a word that contains nine letters rquot m 03 J Quote may seem a hit of a foreign concept because few other languages have anything like it It s closely tied to one of the most distinctive features of Lisp code and data are made out of the same data structures and the quote operator is the way we distinguish between them eq x y returns 1 if the values of a and y are the same atom or both the empty list and otherwise gt eq a a t gt eq a b gt eq 0 0 1 car x expects the value of a to he a list and returns its rst element gt car a b c a cdr x expects the value of a to he a list the rst element and returns everything after gt cdr a b c b c cons as y expects the value of y to he a list and returns a list containing the value of a followed by the elements of the value of gt cons a b c a cons b cons c gt car cons a b C a gt cdr cons a b C b c cond m 2 p7 2733 is evaluated as follows The p expressions are evaluated in order until one returns 1 When one is found the value of the corresponding 0 expression is returned as the value of the whole cond expression gt cond eq a b first atom a second second In ve of our seven primitive operators the arguments are 39 evaluated when an expression beginning with that operator is evaluated2 V will call an operator of that type a functi m 2 Denoting Functions Next we de ne a notation for de bing functions A function is expressed as lambda p1 p 6 where p p are atonls called pamm 7 m5 and is an expression An expression whose rst element is such an expression 1ambda p1 H107 a up is called a functi m call and its value is computed as follows Each expression a is evaluated Then is evaluated During the evaluation of the value of any occurrence of one of the p is the value of the corresponding a in the most recent function call gt 1ambda x cons x b a a b gt 1ambda x y cons x cdr y 1 Z a b c z b c If an expression has as its rst element an atom f that is not one of the primitive operators f a no and the value of f is a function lambda p1 p f then the value of the expression is the value of 1ambda p1 mp a man In other words parameters can be used as operators in expressions as well as arguments gt 1ambda f f b c 1ambda x cons a x a b c There is another notation for functions that enables the function to refer to itself thereby giving us a convenient way to de ne recursive functions The 2 prre 39 HIS beginning with the other two operators quote and send are evaluated dil lerently hen a quo e expression is evaluatet its argument is not evaluated but 39 quot n y returned as the value of the whole quote expre x on And in a valid send expression only an shaped path of sulexpressions will be evaluated ogic y we dont need to define a new notation for this We could define recursive fur ilt our existing notation using a function on functions called the Y combinator It may he that McCarthy did not know about the Y combinator when he wrote his paper in any case label notation is more readable notation label f lambda p1 H107 3 denotes a function that behaves like lambda p1 m 6 with the additional property that an occurrence of f within will evaluate to the label expression as if f were a parameter of the function Suppose we want to de ne a function subst r y 2 which takes an ex pression 1r an atom y and a list 2 and returns a list like 2 but with each instance of y at any depth of nesting in 2 replaced by r gt subs1 m b a b a b c d a m a m c d We can denote this function as label subs1 lambda x y z cond a1om z cond eq 2 y x 1 2 1 cons subs1 x y car 2 subs1 x y cdr z We will abbreviate f label f lambda p1 H107 6 as defun f m H107 f so defun subs1 x y z cond a1om z cond eq 2 y x 1 2 1 cons subs1 x y car 2 subs1 x y cdr z Incidentally we see here how to get a default clause in a cond expression A clause whose rst element is 1 will always succeed So cond r y 1 2 is equivalent to what we might write in a language with syntax as if r then y else 2 3 Some Functions Now that we have a way of expressing functions we de ne some new ones in terms of our seven primitive operators First it will be convenient to introduce some abbreviations for common patterns We will use czrr where r is a sequence o as or ds as an or the cor amp o car and cdr So for example cadr f is an abbreviation for car cdr 3 which returns the second element of 2 gt cadr a b c d e c gt caddr a b c d e e gt cdar a b c d e b Also we will use list 3 670 for cons 3 cons 3n gt cons a cons b cons c Now we de ne some new functions I ve changed the names of these functions b adding periods at the end This distinguishes primitive functions from those de ned in terms of them and also avoids clashes with existing Common Lisp functions 1 null r tests whether its argument is the empty list defun null K eq X 0 gt null a 0 gt null t 2 and r y returns t if both its arguments do and otherwise defun and X y cond X cond y t t 0 1 0 gt and atom a eq a a t gt and atom a eq a 13 lt 3 not gr returns t if its argument returns and if its argument returns t rquot 5 Us defun not x cond X 0 1 t gt not eq a a 0 gt not eq a 13 t append r y takes two lists and returns their concatenation defun append X y cond null x y 1 cons car x append cdr x y gt append a b c 1 0 c 1 pair r y takes two lists of the same length and returns a list of two elernent lists containing successive pairs of an element from each defun pair x cond and null x null y 0 and not atom 30 not atom y cons list car x car y pair cdr X cdr y gt pair x y z a b C X a y b 2 c assoc r y takes an atom 1139 and a list y of the form Created by pair and returns the second element of the rst list in y whose rst element is r defun assoc x y cond eq caar y x cadar y 1 assoc x cdr y gt assoc X X a y b a gt assoc x x new x a y b new 4 The Surprise So we can de ne functions that concatenate lists substitute one expression for another etc An elegant notation perhaps but so What Now comes the surprise We can also it turns out write a function that acts as an interpreter for our language a function that takes as an argument any Lisp expression and returns its value Here it is defun eval e a cond atom e assoc e a atom car e cond eq car e quote cadr e eq car e atom atom eval cadr e a eq car e eq eq eval cadr e a eval caddr e a eq car e car car eval cadr e a eq car e cdr cdr eval cadr e a eq car e cons cons eval cadr e a eval caddr e a eq car e cond evcon cdr e a t eval cons assoc car e a cdr e a eq caar e 1abe1 eval cons caddar e cdr e cons list cadar e car e a eq caar e 1ambda eval caddar e append pair cadar e evlis cdr e a a defun evcon c a cond eval caar c a eval cadar c a t evcon cdr c a defun evlis m a cond null m t cons eval car m a evlis cdr m a The de nition of eval is longer than any of the others we ve seen before Let s consider how each part works The function takes two arguments e the expression to be evaluated and a a list representing the values that atoms have been given by appearing as parameters in function calls This list is called the cmwimmrwm and it is of the form created by pair It was in order to build and search these lists that we wrote pair and assoc The spine of eval is a cond expression with four clauses How we evaluate an expression depends on what kind it is The rst clause handles atoms If e is an atom we look up its value in the environment gt eval X X a y b a The second clause of eval is another cond for handling expressions of the form a where a is an atom These include all the uses of the primitive operators and there is a clause for each one gt eval eq a a t gt eval cons x b c X a y b a b c All of these except quote call eval to nd the value of the arguments The last two clauses are more complicated To evaluate a cond expression we call a subsidiary function called evcon which works its way through the clauses recursively looking for one in which the rst element returns 1 When it nds such a clause it returns the value of the second element gt eval cond atom x atom 1 list X a b list The nal part of the second clause of eval handles calls to functions that have been passed as parameters It works by replacing the atom with its value which ought to be a lambda or label expression and evaluating the resulting expression So eval f b c f lambda x cons a x turns into eval lambda x cons a x b c f lambda x cons a x which returns a b c The last two clauses in eval handle function calls in which the rst ele ment is an actual lambda or label expression A label expression is evaluated by pushing a list of the function name and the function itself onto the environ ment and then calling eval on an expression with the inner lambda expression substituted for the label expression That is eval label firstatom lambda x cond a1om x x 1 firstatom car x y y a b c d becomes eval lambda x cond a1om x x 1 firstatom car 10 y firstatom label firstatom lambda x cond a1om x x 1 firstatom car x y lt8 b C d which eventually returns a Finally an expression of the form lambda p1 p f a an is eval uated by rst calling evlis to get a list of values v1 v of the arguments a an and then evaluating with m m m U appended to the front of the environment So eval lambda x y cons x cdr y a b C 1 0 becomes eval cons x cdr y X a y b c d which eventually returns a c d 5 Aftermath Now that we understand how eval works let s step back and consider what it means What we have here is a remarkably elegant model of computation Using just quote atom eq car cdr cons and cond we can de ne a function eval that actually implements our language and then using that we can de ne any additional function we want There were already models of computation of course rrrr most notably the Turing Machine But Turing Machine programs are not very edifying to read If you want a language for describing algorithms you might want something more abstract and that was one of McCarthy s aims in de ning Lisp 10 The language he de ned in 1960 was mis ing a lot It has no side effec no sequential execution which is useful only with side effects anyway no practical nurnbersf and dynamic scope But these limitations can be remedied with surprisingly little additional code Steele and Sussman show how to do it in a famous paper called quot The Art of the Interpreter If you understand VlcCarthy eval you understand more than just a stage in the history of languages These ideas are still the semant re of Lisp today So studying r cCarthy s original paper shows us in a sense what Lisp really is It s not something that McCarthy designed so much as something he discovered It s not intrinsically a language for Al or for rapid prototyping or any other task at that level It s what you get or one thing you get when you try to axiomatize computation Over time the median language meaning the language used by the median programmer has grown cons tently closer to Lisp So by understanding eval you re understanding what will probably be the main model of computation well into the future 4t is possible to do arithmetic in McCarthy s 1960 isp by using eg a list of 1 atoms to eseiit the number my ltmi Steele Jr and Gerald Jay Sussmaii quotThe Art of the Interpreter or the Modularity Complex Part sro One and 39i woquot M 39i Al ab Memo 433 M ay 1978 Notes In translating McCarthy s notation into running code I tried to change as little as possible I was tempted to make the code easier to read but I wanted to keep the avor of the original In McCarthy s paper falsity is represented by f not the empty list I used to represent falsity so that the examples would work in Common Lisp T ie code nowhere depends on falsity happening also to be the empty list nothing is ever consed onto the result returned by a predicate I skipped building lists out of dotted pairs because you don t need them to understand eval I also skipped mentioning apply though it was apply a very early form of it whose main purpose was to quote arguments that McCarthy called the universal function in 1960 eval was then just a subroutine that apply called to do all the work I de ned list and the ccvrs as abbreviations because that s how r IcCarthy did it In fact the ccvrs could all have been de ned as ordinary functions So could list if we modi ed eval as we easily could to let functions take any number of arguments McCarthy s paper only had ve primitive operators He used cond and quote but may have thought of them as part of his metalanguage He likewise didn t de ne the logical operators and and not but this is less of a problem because adequate versions can be de ned as functions In the de nition of eval we called other functions like pair and assoc but any call to one of the functions we de ned in terms of the primitive operators could be replaced by a call to eval That is assoc car e a could have been written as eval 1abel assoc lambda x y cond eq caar y x cadar y t assoc x cdr y car e a cons list e e cons list a a a There was a small bug in IVIcCartl eval Line 16 was equivalent to evlis cdr e a instead of just cdr e which caused the arguments in a call to a named function to be evaluated tw ce This suggests that this de s ription of eval had not yet been implemented in IBM 704 machine language when the paper was submitted It also shows how hard it is to be sure of the correctness of any length of program without try ng to run it I encountered one other problem in VIcC39 code After giving the def inition of eval he goes on to give some examples of higher order functions functions that take other functions as arguments He de nes maplist ii 12 label maplist lambda x f cond null x 0 1 cons f x maplist cdr x f then uses it to write a simple function diff for symbolic differentiation But diff passes maplist a function that uses it as a parameter and the reference to it is captured by the parameter it within maplist l It s an eloquent testimony to the dangers of dynamic scope that even the very rst example of higher order Lisp functions was broken because of it It may be that McCarthy was not fully aware of the implications of dynamic scope pe remained in Lisp implementations for a surprising y long time sman and Steele developed Scheme in 19 Lexical scope does not complicate the de nition of eval very much but it may make compilers harder to write 1 day Lisp pro ammeis would use mapcar instead of maplist hero This example lear up one myste v V why maplist is in Common L p at allv t was the original mapping ttioiL and mapcar a later addition hint

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.