Lisp in AI: self-modifying code and domain-specific levels of abstraction

Question

AI is implemented in a variety of different languages, e.g., Python, C/C++, Java, so could someone please explain to me how exactly does using Lisp allow one to perform #5 (mentioned here by Peter Norvig):

5. [Lisp allows for..] A macro system that let developers create a domain-specific level of abstraction in which to build the next level. ... today, (5) is the only remaining feature in which Lisp excels compared to other languages.

Source: https://www.quora.com/Is-it-true-that-Lisp-is-highly-used-programming-language-in-AI

I'm basically confused by what it means to create a domain-specific level of abstraction. Could someone please provide a concrete example/application of when/how this would be useful and, just in general, what it means? I tried reading http://lambda-the-ultimate.org/node/4765 but didn't really "get the big picture." However, I felt like there is some sort of magic here, in that Lisp allows you to write the kind of code that other procedural/OOP/functional languages won't let you. Then I came across this post: https://www.quora.com/Which-programming-language-is-better-for-artificial-intelligence-C-or-C++, where the top answer states:

For generic Artificial Intelligence, I would choose neither and program in LISP. A real AI would have a lot of self-modifying code (you don't think a real AI would take what its programmer wrote as The Last Word, would you?).

This got me even more intrigued, which led me to wonder:

What exactly would it mean for an AI to have "self-inspecting, self-modifying code" (source: Why is Lisp used for AI?) and, again, why/how this is useful? It sounds very cool (almost like as if the AI is self-conscious about its own operations, so to speak), and it sounds like using Lisp allows one to accomplish these kinds of things, where other languages wouldn't even dream of it (sorry if this comes off as naively jolly, I have absolutely no experience in Lisp, but am excited to get started). I read a little bit of: What are the uses of self modifying code? and immediately became interested in the prospect of specific AI applications and future frontiers of self-modifying code.

Anyway, I can definitely see the connection between having the ability to write self-modifying code, and having the ability to tailor the language atop of your specific research problem domain (which is what I assume Peter Norvig implies in his post), but I really am quite unsure in what any of this really means, and I would like to understand the nuts-and-bolts (or even just the essence), of these two aspects presented above ("domain-specific level of abstraction" and "self-inspecting, self-modifying code") in a clear way.

Answer 1

[Lisp allows for..] A macro system that let developers create a domain-specific level of abstraction in which to build the next level. ... today, (5) is the only remaining feature in which Lisp excels compared to other languages.

This might be too broad for Stack Overflow, but the concept of domain-specific abstraction is one that happens in lots of languages, it's just much easier in Common Lisp. For instance, in C, when you make a call to open(), you get back a file descriptor. It's a small integer, but if you're adhering to the domain model, you don't care that it's an integer, you care that it's a file descriptor, and that it makes sense to use it where a file descriptor is intended. It's a leaky abstraction, though, because those calls tend to signal errors by returning negative integers, so you do actually have to care about the fact that a file descriptor is an integer, so that you can reliably compare the result and figure out whether it was an error or not. In C, you can define structures, or record types, that bundle some information together. That provides a slightly higher amount of abstraction.

The idea of abstraction is that you can think about how something is supposed to be used, and what it represents, and think in terms of the domain, not in terms of the representation. All programming languages support this in some sense, but Common Lisp makes it much easier to build up language constructs that look just like the builtins of the language, and help to avoid redundant (and error-prone) boilerplate.

For instance, if you're writing a natural deduction style theorem prover, you'll need to define a bunch of inference rules and make them available a proof system. Some of those rules will be more simplistic, and won't need to know about the current proof scope. For instance, to check whether a use of conjunction elimination (from A∧B, infer A (or B)) is legal, you just need to check the forms of the premise and the conclusion. Without abstraction, you might have to write:

(defun check-conjunction-elimination (premises conclusion context)
   (declare (ignore context))
   (and (= (length premises) 1)
        (typep (first premises) 'conjunction)
        (member conclusion (conjunction-conjuncts (first premises))
                :test 'proposition=)))

(register-inference-rule "conjunction elimination" 'check-conjunction-elimination)

With the ability to define abstractions, you can write a pattern matcher that could simplify this to:

(defun check-conjunction-elimination (premises conclusion context)
   (declare (ignore context))
   (proposition-case (premises conclusion)
     (((and A B) A) t)
     (((and A B) B) t)))

(register-inference-rule "conjunction elimination" 'check-conjunction-elimination)

(Sure, some languages have pattern matching built in (Haskell, Prolog (in a sense)), but the point is that pattern matching is a procedural process, and you can implement it in any language. However, it's a code generation process, and in most languages, you'd have to do the code generation as a separate pass during compilation. With Common Lisp, it's part of the language.)

You could abstract that pattern into:

(define-simple-inference-rule "conjunction elimination" (premises conclusion)
  ((and A B) A)
  ((and A B) B)))

And you'd still be generating the original code. This kind of abstraction saves a lot of space, and it means that when someone else comes in, they don't need to know all of Common Lisp, they just need to know how to use define-simple-inference-rule. (Of course, that does add some overhead, since it's something else that they do need to know how to use.) But the idea is still there: the code corresponds to the way you talk about the domain, not the way the programming language works.

As to "self modifying code", I think it's a term that you'll hear more than you'll actually see good uses of. In the sense of macroexpansion described above, there's a kind of self-modifying code (in that the macroexpansion code knows how to "modify" or transform the code into the something else, but I don't think that's a great example). Since you have access to eval, you can modify code as an object and evaluate it, but I don't think many people really advocate for that. Being able to redefine code on the fly can be handy, but again, I think you'll see people doing that much more in the REPL than in programs.

However, being able to return closures (something which more and more languages are supporting) is a big help. For instance, trace is "sort of" self modifying. You could implement it something like this:

(defmacro trace (name)
  (let ((f (symbol-function name)))
    (setf (symbol-function name)
          (lambda (&rest args)
            (print (list* name args))
            (apply f args)))))

You'd need to do something more to support untrace, but I think the point is fairly clear; you can do things that change the behavior of functions, etc., in predictable ways, at run time. trace and logging facilities are an easy example, but if a system decided to profile some of the methods that it knows are important, it could dynamically decide to start caching some of the results, or doing other interesting things. That's a kind of "self modification" that could be quite helpful.