Practical example of Lisp's flexibility? [clos

问题:

Someone is trying to sell Lisp to me, as a super powerful language that can do everything ever, and then some.

Is there a practical code example of Lisp's power?
(Preferably alongside equivalent logic coded in a regular language.)

回答1:

I like macros.

Here's code to stuff away attributes for people from LDAP. I just happened to have that code lying around and fiigured it'd be useful for others.

Some people are confused over a supposed runtime penalty of macros, so I've added an attempt at clarifying things at the end.

In The Beginning, There Was Duplication

(defun ldap-users ()
  (let ((people (make-hash-table :test 'equal)))
    (ldap:dosearch (ent (ldap:search *ldap* "(&(telephonenumber=*) (cn=*))"))
                   (let ((mail  (car (ldap:attr-value ent 'mail)))
                         (uid   (car (ldap:attr-value ent 'uid)))
                         (name  (car (ldap:attr-value ent 'cn)))
                         (phonenumber (car (ldap:attr-value ent 'telephonenumber))))
                      (setf (gethash uid people)
                            (list mail name phonenumber))))
    people))

You can think of a "let binding" as a local variable, that disappears outside the LET form. Notice the form of the bindings -- they are very similar, differing only in the attribute of the LDAP entity and the name ("local variable") to bind the value to. Useful, but a bit verbose and contains duplication.

On the Quest for Beauty

Now, wouldn't it be nice if we didn't have to have all that duplication? A common idiom is is WITH-... macros, that binds values based on an expression that you can grab the values from. Let's introduce our own macro that works like that, WITH-LDAP-ATTRS, and replace it in our original code.

(defun ldap-users ()
  (let ((people (make-hash-table :test 'equal))) ; equal so strings compare equal!
    (ldap:dosearch (ent (ldap:search *ldap* "(&(telephonenumber=*) (cn=*))"))
                   (with-ldap-attrs (mail uid name phonenumber) ent
                       (setf (gethash uid people)
                             (list mail name phonenumber))))
    people))

Did you see how a bunch of lines suddenly disappeared, and was replaced with just one single line? How to do this? Using macros, of course -- code that writes code! Macros in Lisp is a totally different animal than the ones you can find in C/C++ through the use of the pre-processor: here, you can run real Lisp code (not the #define fluff in cpp) that generates Lisp code, before the other code is compiled. Macros can use any real Lisp code, i.e., ordinary functions. Essentially no limits.

Getting Rid of Ugly

So, let's see how this was done. To replace one attribute, we define a function.

(defun ldap-attr (entity attr)
  `(,attr (car (ldap:attr-value ,entity ',attr))))

The backquote syntax looks a bit hairy, but what it does is easy. When you call LDAP-ATTRS, it'll spit out a list that contains the value of attr (that's the comma), followed by car ("first element in the list" (cons pair, actually), and there is in fact a function called first you can use, too), which receives the first value in the list returned by ldap:attr-value. Because this isn't code we want to run when we compile the code (getting the attribute values is what we want to do when we run the program), we don't add a comma before the call.

Anyway. Moving along, to the rest of the macro.

(defmacro with-ldap-attrs (attrs ent &rest body)
  `(let ,(loop for attr in attrs
         collecting `,(ldap-attr ent attr))
     ,@body)) 

The ,@-syntax is to put the contents of a list somewhere, instead of the actual list.

Result

You can easily verify that this will give you the right thing. Macros are often written this way: you start off with code you want to make simpler (the output), what you want to write instead (the input), and then you start molding the macro until your input gives the correct output. The function macroexpand-1 will tell you if your macro is correct:

(macroexpand-1 '(with-ldap-attrs (mail phonenumber) ent
                  (format t "~a with ~a" mail phonenumber)))

evaluates to

(let ((mail (car (trivial-ldap:attr-value ent 'mail)))
      (phonenumber (car (trivial-ldap:attr-value ent 'phonenumber))))
  (format t "~a with ~a" mail phonenumber))

If you compare the LET-bindings of the expanded macro with the code in the beginning, you'll find that it is in the same form!

Compile-time vs Runtime: Macros vs Functions

A macro is code that is run at compile-time, with the added twist that they can call any ordinary function or macro as they please! It's not much more than a fancy filter, taking some arguments, applying some transformations and then feeding the compiler the resulting s-exps.

Basically, it lets you write your code in verbs that can be found in the problem domain, instead of low-level primitives from the language! As a silly example, consider the following (if when wasn't already a built-in)::

(defmacro my-when (test &rest body)
  `(if ,test 
     (progn ,@body)))

if is a built-in primitive that will only let you execute one form in the branches, and if you want to have more than one, well, you need to use progn::

;; one form
(if (numberp 1)
  (print "yay, a number"))

;; two forms
(if (numberp 1)
  (progn
    (assert-world-is-sane t)
    (print "phew!"))))

With our new friend, my-when, we could both a) use the more appropriate verb if we don't have a false branch, and b) add an implicit sequencing operator, i.e. progn::

(my-when (numberp 1)
  (assert-world-is-sane t)
  (print "phew!"))

The compiled code will never contain my-when, though, because in the first pass, all macros are expanded so there is no runtime penalty involved!

Lisp> (macroexpand-1 '(my-when (numberp 1)
                        (print "yay!")))

(if (numberp 1)
  (progn (print "yay!")))

Note that macroexpand-1 only does one level of expansions; it's possible (most likely, in fact!) that the expansion continues further down. However, eventually you'll hit the compiler-specific implementation details which are often not very interesting. But continuing expanding the result will eventually either get you more details, or just your input s-exp back.

Hope that clarifies things. Macros is a powerful tool, and one of the features in Lisp I like.

回答2:

The best example I can think of that is widely available is the book by Paul Graham, On Lisp. The full PDF can be downloaded from the link I just gave. You could also try Practical Common Lisp (also fully available on the web).

I have a lot of unpractical examples. I once wrote a program in about 40 lines of lisp which could parse itself, treat its source as a lisp list, do a tree traversal of the list and build an expression that evaluated to WALDO if the waldo identifier existed in the source or evaluate to nil if waldo was not present. The returned expression was constructed by adding calls to car/cdr to the original source that was parsed. I have no idea how to do this in other languages in 40 lines of code. Perhaps perl can do it in even fewer lines.

回答3:

You may find this article helpful: http://www.defmacro.org/ramblings/lisp.html

That said, it's very, very hard to give short, practical examples of Lisp's power because it really shines only in non-trivial code. When your project grows to a certain size, you will appreciate Lisp's abstraction facilities and be glad that you've been using them. Reasonably short code samples, on the other hand, will never give you a satisfying demonstration of what makes Lisp great because other languages' predefined abbreviations will look more attractive in small examples than Lisp's flexibility in managing domain-specific abstractions.

回答4:

Actually, a good practical example is the Lisp LOOP Macro.

http://www.ai.sri.com/pkarp/loop.html

The LOOP macro is simply that -- a Lisp macro. Yet it basically defines a mini looping DSL (Domain Specific Language).

When you browse through that little tutorial, you can see (even as a novice) that it's difficult to know what part of the code is part of the Loop macro, and which is "normal" Lisp.

And that's one of the key components of Lisps expressiveness, that the new code really can't be distinguished from the system.

While in, say, Java, you may not (at a glance) be able to know what part of a program comes from the standard Java library versus your own code, or even a 3rd party library, you DO know what part of the code is the Java language rather than simply method calls on classes. Granted, it's ALL the "Java language", but as programmer, you are limited to only expressing your application as a combination of classes and methods (and now, annotations). Whereas in Lisp, literally everything is up for grabs.

Consider the Common SQL interface to connect Common Lisp to SQL. Here, http://clsql.b9.com/manual/loop-tuples.html, they show how the CL Loop macro is extended to make the SQL binding a "first class citizen".

You can also observe constructs such as "[select [first-name] [last-name] :from [employee] :order-by [last-name]]". This is part of the CL-SQL package and implemented as a "reader macro".

See, in Lisp, not only can you make macros to create new constructs, like data structures, control structures, etc. But you can even change the syntax of the language through a reader macro. Here, they're using a reader macro (in the case, the '[' symbol) to drop in to a SQL mode to make SQL work like embedded SQL, rather than as just raw strings like in many other languages.

As application developers, our task is to convert our processes and constructs in to a form that the processor can understand. That means we, inevitably, have to "talk down" to the computer language, since it "doesn't understand" us.

Common Lisp is one of the few environments where we can not only build our application from the top down, but where we can lift the language and environment up to meet us half way. We can code at both ends.

Mind, as elegant as this can be, it's no panacea. Obviously there are other factors that influence language and environment choice. But it's certainly worth learning and playing with. I think learning Lisp is a great way to advance your programming, even in other languages.

回答5:

I like Common Lisp Object System (CLOS) and multimethods.

Most, if not all, object-oriented programming languages have the basic notions of classes and methods. The following snippet in Python defines the classes PeelingTool and Vegetable (something similar to the Visitor pattern):

class PeelingTool:
    """I'm used to peel things. Mostly fruit, but anything peelable goes."""
    def peel(self, veggie):
        veggie.get_peeled(self)

class Veggie:
    """I'm a defenseless Veggie. I obey the get_peeled protocol
    used by the PeelingTool"""
    def get_peeled(self, tool):
        pass

class FingerTool(PeelingTool):
  ...

class KnifeTool(PeelingTool):
  ...

class Banana(Veggie):
    def get_peeled(self, tool):
        if type(tool) == FingerTool:
            self.hold_and_peel(tool)
        elif type(tool) == KnifeTool:
            self.cut_in_half(tool)

You put the peel method in the PeelingTool and have the Banana accept it. But, it must belong to the PeelingTool class, so it can only be used if you have an instance of the PeelingTool class.

The Common Lisp Object System version:

(defclass peeling-tool () ())
(defclass knife-tool (peeling-tool) ())
(defclass finger-tool (peeling-tool) ())

(defclass veggie () ())
(defclass banana (veggie) ())

(defgeneric peel (veggie tool)
  (:documentation "I peel veggies, or actually anything that wants to be peeled"))

;; It might be possible to peel any object using any tool,
;; but I have no idea how. Left as an exercise for the reader
(defmethod peel (veggie tool)
   ...)

;; Bananas are easy to peel with our fingers!
(defmethod peel ((veggie banana) (tool finger-tool))
  (with-hands (left-hand right-hand) *me*
    (hold-object left-hand banana)
    (peel-with-fingers right-hand tool banana)))

;; Slightly different using a knife
(defmethod peel ((veggie banana) (tool knife-tool))
  (with-hands (left-hand right-hand) *me*
    (hold-object left-hand banana)
    (cut-in-half tool banana)))

Anything can be written in any language that's Turing complete; the difference between the languages is how many hoops you have to jump through to get the equivalent result.

A powerful languages like Common Lisp, with functionality such as macros and the CLOS, allows you to achieve results fast and easy without jumping through so many hoops that you either settle for a subpar solution, or find yourself becoming a kangaroo.

回答6:

There are plenty of killer features in Lisp, but macros is one I love particularily, because there's not really a barrier anymore between what the language defines and what I define. For example, Common Lisp doesn't have a while construct. I once implemented it in my head, while walking. It's straightforward and clean:

(defmacro while (condition &body body)
  `(if ,condition
       (progn
         ,@body
         (do nil ((not ,condition))
           ,@body))))

Et voilà! You just extended the Common Lisp language with a new fundamental construct. You can now do:

(let ((foo 5))
  (while (not (zerop (decf foo)))
    (format t "still not zero: ~a~%" foo)))

Which would print:

still not zero: 4
still not zero: 3
still not zero: 2
still not zero: 1

Doing that in any non-Lisp language is left as an exercise for the reader...

回答7:

I found this article quite interesting:

Programming Language Comparison: Lisp vs C++

The author of the article, Brandon Corfman, writes about a study that compares solutions in Java, C++ and Lisp to a programming problem, and then writes his own solution in C++. The benchmark solution is Peter Norvig's 45 lines of Lisp (written in 2 hours).

Corfman finds that it is difficult to reduce his solution to less than 142 lines of C++/STL. His analysis of why, is an interesting read.

回答8:

The thing that I like most about Lisp (and Smalltalk) systems, is that they feel alive. You can easily probe & modify Lisp systems while they are running.

If this sounds mysterious, start Emacs, and type some Lisp code. Type C-M-x and voilà! You just changed Emacs from within Emacs. You can go on and redefine all Emacs functions while it is running.

Another thing is that the code = list equivalence make the frontier between code and data very thin. And thanks to macros, it is very easy to extend the language and make quick DSLs.

For instance, it is possible to code a basic HTML builder with which the code is very close to the produced HTML output:

(html
  (head
    (title "The Title"))
  (body
    (h1 "The Headline" :class "headline")
    (p "Some text here" :id "content")))

=>

<html>
  <head>
    <title>The title</title>
  </head>
  <body>
    <h1 class="headline">The Headline</h1>
    <p id="contents">Some text here</p>
  </body>
</html>

In the Lisp code, auto indentation make the code look like the output, except there aren't any closing tags.

回答9:

I like this macro example from http://common-lisp.net/cgi-bin/viewcvs.cgi/cl-selenium/?root=cl-selenium It's a Common Lisp binding to Selenium (a web browser test framework), but instead of mapping every method, it reads Selenium's own API definition XML document at compile time and generates the mapping code using macros. You can see the generated API here: common-lisp.net/project/cl-selenium/api/selenium-package/index.html

This is essentially driving macros with external data, which happens to be an XML document in this case, but could have been as complex is reading from a database or network. This is the power of having the entire Lisp environment available to you at compile time.

回答10:

See how you can extend Common Lisp with XML templating: cl-quasi-quote XML example, project page,

(babel:octets-to-string
 (with-output-to-sequence (*html-stream*)
   <div (constantAttribute 42
         someJavaScript `js-inline(print (+ 40 2))
         runtimeAttribute ,(concatenate 'string "&foo" "&bar"))
     <someRandomElement
       <someOther>>>))

 =>

 "<div constantAttribute=\"42\"
       someJavaScript=\"javascript: print((40 + 2))\"
       runtimeAttribute=\"&amp;foo&amp;bar\">
    <someRandomElement>
      <someOther/>
    </someRandomElement>
  </div>"

This is basically the same thing as Lisp's backtick reader (which is for list quasi quoting), but it also works for various other things like XML (installed on a special <> syntax), JavaScript (installed on `js-inline), etc.

To make it clear, this is implemented in a user library! And it compiles the static XML, JavaScript, etc. parts into UTF-8 encoded literal byte arrays that are ready to be written to the network stream. With a simple , (comma) you can get back to lisp and interleave runtime generated data into the literal byte arrays.

This is not for the faint of heart, but this is what the library compiles the above into:

(progn
 (write-sequence
  #(60 100 105 118 32 99 111 110 115 116 97 110 116 65 116 116 114 105 98
    117 116 101 61 34 52 50 34 32 115 111 109 101 74 97 118 97 83 99 114
    105 112 116 61 34 106 97 118 97 115 99 114 105 112 116 58 32 112 114
    105 110 116 40 40 52 48 32 43 32 50 41 41 34 32 114 117 110 116 105
    109 101 65 116 116 114 105 98 117 116 101 61 34)
  *html-stream*)
 (write-quasi-quoted-binary
  (let ((*transformation*
          #<quasi-quoted-string-to-quasi-quoted-binary {1006321441}>))
    (transform-quasi-quoted-string-to-quasi-quoted-binary
      (let ((*transformation*
               #<quasi-quoted-xml-to-quasi-quoted-string {1006326E51}>))
        (locally
            (declare (sb-ext:muffle-conditions sb-ext:compiler-note))
         (let ((it (concatenate 'string "runtime calculated: " "&foo" "&bar")))
           (if it
               (transform-quasi-quoted-xml-to-quasi-quoted-string/attribute-value it)
               nil))))))
  *html-stream*)
 (write-sequence
  #(34 62 10 32 32 60 115 111 109 101 82 97 110 100 111 109 69 108 101 109
    101 110 116 62 10 32 32 32 32 60 115 111 109 101 79 116 104 101 114 47
    62 10 32 32 60 47 115 111 109 101 82 97 110 100 111 109 69 108 101 109
    101 110 116 62 10 60 47 100 105 118 62 10)
  *html-stream*)
 +void+)

For reference, the two big byte vectors in the above look like this when converted to string:

"<div constantAttribute=\"42\"
      someJavaScript=\"javascript: print((40 + 2))\"
      runtimeAttribute=\""

And the second one:

"\">
 <someRandomElement>
    <someOther/>
  </someRandomElement>
</div>"

And it combines well with other Lisp structures like macros and functions. now, compare this to JSPs...

回答11:

I was an AI student at MIT in the 1970s. Like every other student, I thought language was paramount. Nevertheless, Lisp was the primary language. These are some things I still think it is pretty good for:

• Symbolic math. It is easy and instructive to write symbolic differentiation of an expression, and algebraic simplification. I still do those, even though I do them in C-whatever.

• Theorem proving. Every now & then I go on a temporary AI binge, like trying to prove that insertion sort is correct. For that I need to do symbolic manipulation, and I usually fall back on Lisp.

• Little domain-specific-languages. I know Lisp isn't really practical, but if I want to try out a little DSL without having to get all wrapped up in parsing, etc., Lisp macros make it easy.

• Little play algorithms like minimax game tree search can be done in like three lines.

• Want to try lambda calculus? It's easy in Lisp.

Mainly what Lisp does for me is mental exercise. Then I can carry that over into more practical languages.

P.S. Speaking of lambda calculus, what also started in the 1970s, in that same AI millieu, was that OO started invading everybody's brain, and somehow, interest in what it is seems to have crowded out much interest in what it is good for. I.e. work on machine learning, natural language, vision, problem solving, all sort of went to the back of the room while classes, messages, types, polymorphism, etc. went to the front.

回答12:

One thing I like is the fact that I can upgrade code "run-time" without losing application state. It's a thing only useful in some cases, but when it is useful, having it already there (or, for only a minimal cost during development) is MUCH cheaper than having to implement it from scratch. Especially since this comes at "no to almost no" cost.

回答13:

Have you taken a look at this explanation of why macros are powerful and flexible? No examples in other languages though, sorry, but it might sell you on macros.

回答14:

@Mark,

While there is some truth to what you are saying, I believe it is not always as straight forward.

Programmers and people in general don't always take the time to evaluate all the possibilities and decide to switch languages. Often It's the managers that decide, or the schools that teach the first languages ... and programmers never have the need to invest enough amount of time to get to a certain level were they can decide this language saves me more time than that language.

Plus you have to admit that languages that have the backing of huge commercial entities such as Microsoft or Sun will always have an advantage in the market compared to languages without such backing.

In order to answer the original question, Paul Graham tries to give an example here even though I admit it is not necessarily as practical as I would like :-)

回答15:

One specific thing that impressed me is the ability to write your own object-oriented programming extension, if you happen not to like the included CLOS.

One of them is in Garnet, and one in Paul Graham's On Lisp.

There's also a package called Screamer that allows nondeterministic programming (which I haven't evaluated).

Any language that allows you to change it to support different programming paradigms has to be flexible.

回答16:

You might find this post by Eric Normand helpful. He describes how as a codebase grows, Lisp helps by letting you build the language up to your application. While this often takes extra effort early on, it gives you a big advantage later.

回答17:

The simple fact that it's a multi-paradigm language makes it very very flexible.

回答18:

John Ousterhout made this interesting observation regarding Lisp in 1994:

Language designers love to argue about why this language or that language must be better or worse a priori, but none of these arguments really matter a lot. Ultimately all language issues get settled when users vote with their feet.

If [a language] makes people more productive then they will use it; when some other language comes along that is better (or if it is here already), then people will switch to that language. This is The Law, and it is good. The Law says to me that Scheme (or any other Lisp dialect) is probably not the "right" language: too many people have voted with their feet over the last 30 years.

http://www.vanderburg.org/OldPages/Tcl/war/0009.html