How does Lisp allow you to override the language itself?

Question

I heard that Lisp allows you to redefine the language itself, and I tried to explore it, but there is no clear explanation anywhere. Does anyone have a simple example?

Answer 1

Lisp users refer to Lisp as a programmable programming language . It is used for symbolic calculations - calculations with symbols.

Macros are just one way to use the paradigm of symbolic computing. The wider vision is that Lisp provides simple ways to describe symbolic expressions: mathematical terms, logical expressions, iterative statements, rules, descriptions of constraints, and much more. Macros (transformations of the original Lisp forms) are just one application of symbolic computing.

There are some aspects of this: if you ask about the "redefinition" of the language, then a strict redefinition will mean overriding any existing linguistic mechanism (syntax, semantics, pragmatics). But there is also an extension, implementation, removal of language functions.

There have been many attempts in the Lisp tradition to provide these functions. The Lisp dialog and a specific implementation can only offer a subset of them.

Several ways to override / modify / extend the functionality provided by the main implementations of Common Lisp:

• s-expression syntax . The syntax of s-expressions is not fixed. The reader (READ function) uses the so-called reading tables to indicate the functions that will be performed when reading the character. You can modify and create reading tables. This allows you, for example, to change the syntax of lists, characters, or other data objects. You can also introduce new syntax for new or existing data types (for example, hash tables). It is also possible to completely replace the s-expression syntax and use a different parsing engine. If the new parser returns Lisp forms, no changes are required for the interpreter or compiler. A typical example is a read macro that can read infix expressions. Inside such a read macro, infix expressions and precedence rules for operators are used. Reading macros are different from regular macros: reading macros is done at the character level of Lisp syntax.

• replacement of functions . Top-level functions are tied to characters. User can change this binding. Most implementations have a mechanism that allows this even for many built-in functions. If you want to provide an alternative to the built-in ROOM function, you can replace its definition. Some implementations will result in an error, and then offer an option to continue the change. Sometimes you need to unlock the package. This means that functions can generally be replaced with new definitions. There are limitations to this. First, the compiler can embed functions in code. To see the effect, you need to recompile the code that uses the modified code.

• recommendations . Often you want to add some kind of behavior to functions. This is called "counseling" in the Lisp world. Many common Lisp implementations will provide such a facility.

• custom packages . Packages group characters in namespaces. The COMMON-LISP package is home to all characters that are part of the ANSI Common Lisp standard. A programmer can create new packages and import existing characters. Thus, you can use the EXTENDED-COMMON-LISP package in your programs, which provides more or more features. Just by adding (IN-PACKAGE "EXTENDED-COMMON-LISP"), you can start development using your extended version of Common Lisp. Depending on the namespace used, the Lisp dialect that you use may look slightly or even radically different. There are several Lisp dialects in Genera on the Lisp machine: ZetaLisp, CLtL1, ANSI Common Lisp, and Symbolics Common Lisp.

• CLOS and dynamic objects. Generic Lisp Object System comes with a built-in input. The Meta-Object protocol extends these capabilities. CLOS itself can be extended / redefined in CLOS. You need another inheritance. Write a method. You need different ways to store instances. Write a method. Slots should have more information. Provide a class for this. CLOS itself is designed in such a way that it is able to implement a whole "region" of various object-oriented programming languages. Typical examples are adding things like prototypes, integrating with other people's object systems (like Objective-C), adding resilience, ...

• Lisp forms , Interpretation of Lisp forms can be overridden by macros. A macro can analyze the source code that it contains and modify it. There are various ways to control the transformation process. Complex macros use a code walker that understands the syntax of Lisp forms and can apply transformations. Macros can be trivial, but can also be very complex, like LOOP or ITERATE macros. Other typical examples are macros for embedded SQL and embedded HTML generation. Macros can also be used to move computations to compile time. Since the compiler itself is a Lisp program, arbitrary computation can be performed at compile time. For example, a Lisp macro could calculate an optimized version of a formula if certain parameters are known at compile time.

• Symbols Generic Lisp contains character macros. Character macros allow you to change the meaning of characters in the source code. A typical example is the following: (with slots (foo) bar (+ foo 17)) Here, the FOO symbol in the source enclosed with WITH-SLOTS will be replaced by a call (the value string of the word "foo").

• optimization , with the so-called compiler macros, you can provide more efficient versions of some functions. The compiler will use these compiler macros. This is an effective way for the user to optimize programs.

• Handling conditions - handle conditions that arise due to the use of a programming language in a certain way. Generic Lisp provides an advanced way to handle errors. A condition system can also be used to redefine language functions. For example, you can handle errors of the undefined function using autorun autoloading mechanism. Instead of sending it to the debugger, when the undefined function is visible to Lisp, the error handler may try to autoload the function and repeat the operation after loading the necessary code.

• Special Variables - Inserts binding variables into existing code. Many Lisp dialects, such as Common Lisp, provide special / dynamic variables. Their value is viewed at runtime on the stack. This allows you to include code to add variable bindings that affect existing code without changing it. A typical example is a variable of type * standard-output *. You can rebuild a variable, and all output using this variable during the dynamic region of the new binding will move in a new direction. Richard Stallman argued that it was very important for him that he was installed by default in Emacs Lisp (although Stallman knew about lexical binding in Scheme and Common Lisp).

Lisp has these and other features, as it is used to implement many different languages ​​and programming paradigms. A typical example is a built-in implementation of a logical language, such as Prolog. Lisp allows you to describe Prolog terms with s-expressions and with a special compiler, Prolog terms can be compiled into Lisp code. Sometimes the usual Prolog syntax is required, then the parser will parse the typical Prolog terms in Lisp forms, which will then be compiled. Other examples for embedded languages ​​are rule-based languages, mathematical expressions, SQL terms, Lisp inline assembler, HTML, XML, and many others.

Answer 2

I am going to connect to the fact that Scheme is different from Common Lisp when it comes to defining a new syntax. It allows you to define templates using define-syntax , which apply to the source code wherever they are used. They look exactly like functions, only they run at compile time and transform the AST.

Here is an example of how let can be defined in terms of lambda . The string with let is the pattern to be matched, and the string with lambda is the resulting code pattern.

 (define-syntax let (syntax-rules () [(let ([var expr] ...) body1 body2 ...) ((lambda (var ...) body1 body2 ...) expr ...)])) 

Note that this is NOTHING like text substitution. You can really override lambda , and the above definition for let will still work because it uses the lambda definition in the environment where let was defined. In fact, it is powerful as macros, but pure as functions.

Answer 3

Macros are a common reason for this. The idea is that since the code is just a data structure (more or less a tree), you can write programs to create this data structure. Thus, everything you know about writing programs that generate and manage data structures adds code explicitly to your ability.

Macros are not a complete redefinition of the language, at least as far as I know (I'm actually Schemer, I could be wrong), because there is a limitation. A macro can only take one subtree of your code and generate one subtree to replace it. Therefore, you cannot write macros that transform the entire program as cool as it would be.

However, macros, as they stand, can still do many things - definitely more than any other language will allow you to do. And if you use static compilation, it would not be difficult at all to convert the whole program, so the restriction will be of lesser importance.

Answer 4

The reference to “structure and interpretation of computer programs” in chapter 4-5 is what I was missing from the answers ( link ).

These chapters will help you create a Lisp evaluator in Lisp. I like reading because it not only shows how to redefine Lisp in a new evaluator, but also lets you know the characteristics of the Lisp programming language.

Answer 5

This answer specifically refers to Common Lisp (CL hereinafter), although parts of the answer may be applicable to other languages ​​of the Lisp family.

Since CL uses S-expressions and (basically) looks like a sequence of function applications, there is no obvious difference between inline and user-defined codes. The main difference is that "things provided by the language" are available in a specific package in the encoding environment.

With a little attention, it’s easy to replace the code and use them.

Now the "normal" reader (the part that reads the source code and turns it into internal notation) expects the source code to be in a specific format (in S-expression brackets), but since the reader is controlled by something called "read-tables" , and they can be created and modified by the developer, it is also possible to change the way you view the source code.

These two things should at least provide some justification for why Common Lisp can be considered a reprogrammable programming language. I do not have a simple example, but I have a partial implementation of the translation of Common Lisp into Swedish (created April 1, a few years ago).

Answer 6

From the outside, looking at ...

I always thought that it was because Lisp provided in its power such basic atomic logic operators that any logical process can be built (and was built and presented as a set of tools and add-ons) from the main components.

It is not so much that he can redefine himself, because his basic definition is so pliable that it can take any form and that it is not assumed / assumed in the structure that it is not assumed in the form.

As a metaphor, if you have only organic compounds, you do organic chemistry, if you have only metal oxides, you do metallurgy, but if you have only elements, you can do everything except your additional initial steps ... from which others have already done for you ....

I think.....

Answer 7

Cool example at http://www.cs.colorado.edu/~ralex/papers/PDF/X-expressions.pdf

Reading macros

define X-expressions for coexistence with S-expressions, for example,

 ? (cx <circle cx="62" cy="135" r="20"/>) 62 

plain vanilla Common Lisp at http://www.AgentSheets.com/lisp/XMLisp/XMLisp.lisp ...

 (eval-when (:compile-toplevel :load-toplevel :execute) (when (and (not (boundp '*Non-XMLISP-Readtable*)) (get-macro-character #\<)) (warn "~%XMLisp: The current *readtable* already contains a #/< reader function: ~A" (get-macro-character #\<)))) 

... of course, the XML parser is not so simple, but it can be connected to a Lisp reader.