Programming languages teach you not to want what they cannot provide

Paul Graham

A presentation on what makes a programming language powerful with aim to make Python programmers see colors they have never seen before, motivating them to go beyond Python - which will soon be highly relevant with the advent of Mojo. We will look at some of the expressive limitations of Python, and how this is mitigated in other languages. We aim to demonstrate macros / meta-programming, meaning code that writes code. We hope to pique the interest of the reader to venture further to widen their horizons. Warning:

1. This is not a talk on Mojo, but rather on features Mojo will/aught to have.
2. There will be Lisp… but we will not teach it, only preach it.

Computer languages differ not so much in what they make possible, but in what they make easy.

Larry Wall

Exclusively using the same programming language, such as Python, risk calcifying the way we think of how to solve a programming problem.

There are several restrictions in Python that irks me:

• Python programming is an exercise in writing as little actual Python code as possible, and instead rely on external modules written in C/C++/Fortran, to combat how slow it is. One could argue this is “Feature not a bug”, as Python is the glue to wield the power of modules.
• Lacking in expressive power, can not abstract syntactic patterns (metaprogramming).

• Python keeps breaking backwards compatibility, leading in to versioning hell, as new versions of packages and the language itself breaks working code.

  

  Figure 2: xkcd.com/1987

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.

Paul Graham - The Roots of Lisp

Languages fall along a continuum of abstractness, from the most powerful all the way down to machine languages, which themselves vary in power.

Paul Graham - Beating the Averages

Not all programming languages are created equal, but fall on a “power continuum” of how expressive they are.

• A programmer recognizes which languages are “below” his language: “That language doesn’t even have feature X”
• When same programmer looks “up” the power continuum, he does not realize he is looking up, instead he sees known features plus “strange bits”: “I’ve never needed to use that”.

  BASIC

  “why would I ever need recursion?”

  C

  “Why would I ever need objects?”

  C++

  “Why would I ever need macros?”

Learning new languages higher in the continuum, helps to become a better programmer in general, as one can clearly see what is lacking in the lower languages.

The language “highest” in the spectrum is generally considered to be Lisp. It is the language that all other useful languages converge towards.

despite the flowery phrase that “all the programming languages converge to lisp”, it is factually accurate that all programming languages have been copying lisp since its inception, and we have every reason to believe will continue to do so going into the future.

quora

If you look at these languages in order, Java, Perl, Python, you notice an interesting pattern. At least, you notice this pattern if you are a Lisp hacker. Each one is progressively more like Lisp. … It’s 2002, and programming languages have almost caught up with 1958.

Paul Graham - Revenge of the Nerds

JavaScript

“JavaScript is Lisp in C’s clothing” (takes closures, scoping, high-order functions, and lambdas from Scheme)

C++

Now has lambda & tries to duplicate Lisp macros with constexpr (eval function at compile time) & consteval

Julia

Has a Lisp inspired macro system

Rust

Heavily inspired by Lisp’s (Scheme’s) hygienic macro system

Zig

C/C++ replacement language. Tries to mimic Lisp’s macro system

Nim

“As fast as C, as expressive as Python, as extensible as Lisp.”

Python

Lisp (Scheme) macro system considered for Python PEP638

Mojo

Superset of Python, for AI/machine learning, x 30k speed up

I’ve done a lot of work in both Python with Scipy/Numpy, and Julia. Python is painfully inexpressive in comparison. Not only this, but Julia has excellent type inference. Combined with the JIT, this makes it very fast. Inner numerical loops can be nearly as fast as C/Fortran.

Expanding on the macro system, this has allowed things like libraries that give easy support for GPU programming, fast automatic differentiation, seamless Python interop, etc.

Hacker News

We have previously spoken of the convergence towards Lisp. Some of the features of Lisp, are:

• First interpreted language (can be Interpreted step by step, rather than compiled)
• Conditionals (IF -statements)
• Functions as first class citizens (more on this later)
• Lambda functions (C++11, Python)
• Recursion (more on this and tail recursion later)
• Garbage collection
• Mix-ins (Fun fact: terminology from Ice Cream shop, see p. 457 PAIP)
• Dynamic typing (all variables are pointers to values, values have type, not variables)
• REPL e.g. other languages executes out of process via system shell
• Map / filter / apply / reduce

Mojo (same creator as LLVM and Swift) combines the usability of Python with the performance of C, unlocking unparalleled programmability of AI hardware and extensibility of AI models.

Among the future languages that might be of special interest, is Mojo that is a super-set of Python (as C++ is unto C, or TypeScript is to JavaScript). Thus, the user can write in usual Python syntax, and import Python modules, or scale all the way down to the metal.

It boast of 30,000 x speed up.

File extension: .mojo (or alternatively “fire emoticon”).

It is supposed to support metaprogramming, inspired by Lisp.

Consider development of several popular languages:

• Python 1 -> Python 2 -> Python 3, or
• Fortran 77 -> Fortran 90 -> Fortran 2023, or
• C -> C++,

Each move risk incurring breaking changes, marking a considerable shift, requiring large effort and collaboration from language developers.

Programming languages should be designed not by piling feature on top of feature, but by removing the restrictions and limitations that make additional features seem necessary

R7RS.pdf, (2013)

• New functionality added to the language by the user should be indistinguishable from functionality added by the language designers.
• Many users would add new functionality, experiment, according to each persons need.
• This is what macros in Lisp provide.

We can view programming language as a language of words. If new words defined by the users look like primitives, and if all primitives look like words defined by the users, then a new language would grow dynamically, based on the users experimentation and needs, that is larger, without any seams. Many users would implemented new language features, and share their experimentation, growing the language fast. Such is the possibility in Lisp.

Guy Steele, “Growing a Language” (21:00-)

A Lisp programmer who notices a common pattern in their code can write a macro to give themselves a source-level abstraction of that pattern

Peter Seibel - PCL (chapter 7)

Consider a Java programmer that notice a pattern in their code, e.g. the “enhanced” for-loop of Java 1.5 added an (JSR-201 2002-2004):

1. Programmer detects pattern.
2. Convince Sun Microsystems to add source-level abstraction of pattern.
3. Sun has to publish a JSR & convene industry-wide “expert group”
4. Compiler writers need to update compiler to support new feature
5. Programmers probably not allowed to use new feature for along while (break backwards compatibility with older versions)

So an annoyance that Common Lisp programmers can resolve for themselves within five minutes plagues Java programmers for years.

Peter Seibel - PCL (chapter 7)

On a related note, the now classic article “worse is better”, by Richard P. Gabriel, argues striving for perfection (the “MIT/Lisp”-way) can hamper development, compared to just getting the ball rolling, to quickly fill a niche (“New Jersey/C”-way), and by so doing, growing the user base and number of contributors who can iteratively improve the project, to become “less worse” over time.

To work towards how s program can modify itself, we shall first consider how code gets evaluated and executed. Compilers translate high level source code to low level machine code, specific for the hardware.

By compiling the source code it is translated by a compiler to (binary) machine instructions that are loaded into memory. This is then executed on the processor. The compiler is specific for the hardware.

+------+     +----------+    +---+-----+
| src  +---->| Compiler +--->| Machine |
| code |     |          |    | code    |
+------+     +----------+    +---+-----+
                                 |
                                 |
+-------+    +----------+        |
|  CPU  |    |  Memory  |        |
|       |    |          |        |
|       |<---|          | <------+
|       |    |          |
|       |    |          |
+-------+    |          |
             +----------+

This is typically what happens when we compile C, C++, Fortran, or Lisp code.

Python is both an interpreted and compiled language. That means we are not loading compiled Python machine code to memory directly, but rather the Python binary itself. This Python interpreter consists of two components: Python Virtual Machine (PVM), and a compiler. Code is compiled to (binary) byte code (not machine code), that is then interpreted by the PVM, that runs it.

         +-------------+
         |   Memory    |
         |+-----------+|
         ||Python     ||
         ||Interpreter||
         ||+---------+||
+------->|||   PVM   |||
|        ||+---------+||
|        ||+---------+||       +------+
|  +-----+|| Compiler|||<------+ src  |
|  |     ||+---------+||       | code |
|  |     |+-----------+|       +------+
|  |     |             |
|  +---->|  Byte code  |
|        +------+------+
|               |
+---------------+

We don’t reason about our code in concepts of the characters or text of the source code, but rather by the abstract meaning that defines the operations. This is also how the code execution operates.

In order to go from written source code (text) to a program that is executing the instructions on the CPU, the code has to be parsed, broken down to a hierarchical structure that the compiler can analyze, optimize and execute it.

LISP is worth learning for a different reason — the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.

Eric Raymond - How to become a hacker

This is the same argument you tend to hear for learning Latin. It won’t get you a job, except perhaps as a classics professor, but it will improve your mind, and make you a better writer in languages you do want to use, like English.

Paul Graham - Beating the Averages

The main benefits of Lisp is the experience of using it. We have (perhaps cheekily) argued that all programming languages converge towards Lisp, being the “highest” language in the spectrum of power and expressiveness. Thus, from learning Lisp, we can not only glean insights into the future of programming, but it will also enable feats not possible in any other languages.

Due to its expressive power, one can abstract more with fewer lines of code, leading to significant faster development time. The following is some user testimonies:

Lisp, upon its discovery in 1958, embodies 9 main ideas, outlined in What made Lisp different, that made it the defacto language for AI programming in USA up until the 1990s, (although Europe and Japan also used Prolog, as noted by Norvig/PAIP). Lisp has strong merits as a fundamental programming language:

In Lisp, the code itself is represented as lists, which is the fundamental data structure. It is argued that it is better to have 100 functions operate on one data structure than 10 functions on 10 data structures (although lisp has vectors, hash tables, associated lists (what Python calls “dictionaries”), and other data structures as well).

Lisp was the first language to introduce recursion. Furthermore, Scheme is guaranteed to be tail recursive, meaning it needs no looping constructs (“for, do, while”), like Pascal, C/C++, etc. where recursive function calls will grow memory consumption with number of calls, even if the process is iterative, thus the need for a special looping construct. Scheme does not have this defect, as is demonstrated in the following.

Programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status, supporting all operations generally available to the language:

• can be named by variables
• can be passed as arguments to functions
• can be returned as result of functions
• may be included in data structures.

Lisp syntax is connected to its expressive power. Since Lisp’s syntax is uniform:

(<operator> <arg1> <arg2> ... <argn>)

it will, as we shall see, allow macros to operate on everything, without having to write an AST-manipulating program (like OCaml’s PPX). Paul Graham notes in Beating the Averages that:

is not so much that Lisp has a strange syntax as that Lisp has no syntax You write programs in the parse trees that get generated within the compiler when other languages are parsed

or in full:

Lisp code is made out of Lisp data objects. And not in the trivial sense that the source files contain characters, and strings are one of the data types supported by the language. Lisp code, after it’s read by the parser, is made of data structures that you can traverse.

If you understand how compilers work, what’s really going on is not so much that Lisp has a strange syntax as that Lisp has no syntax. You write programs in the parse trees that get generated within the compiler when other languages are parsed. But these parse trees are fully accessible to your programs. You can write programs that manipulate them. In Lisp, these programs are called macros. They are programs that write programs.

src

• Why is pgloader so much faster? pgloader, for loading data into PostgreSQL is 30x faster when re-written from Python to Common Lisp.
• How to make Lisp go faster than C​, (pdf, Didier Verna, 2006).

CL-PPCRE, a regular expression library, written in Common Lisp, runs faster than Perl’s regular expression engine on some benchmarks, even though Perl’s engine is written in highly tuned C

The Machine that builds itself

Compiler macros can transform function calls into more efficient code at runtime, and a mandatory disassembler which enables programmers to fine-tune time-critical functions until the compiled code matches their expectations.

The Machine that builds itself

Languages must evolve or die.

• Python evolves through major & minor versions: 1 -> 2 -> 3.0 -> 3.1 …
• C++ evolves through updated standards C++11 -> C++14 -> C++17
• Lisp evolves by dialects, forming a family of Lisp languages/dialects.

Where Python only has one (main standard) implementation (CPython), each Lisp dialect typically have many different implementations (both interpreters and compilers), similarly to how C++ has many different compilers (gcc, clang/LLVM, intel, mvcc, Borland).

As noted in PAIP: programming languages come and go as new styles of programming are invented, Lisp just incorporates new styles as macros (e.g. For-loop, CLOS), possible since programs are just simple data structure (list).

Overall, the evolution of Lisp has been guided more by institutional rivalry, one-upsmanship, and the glee born of technical cleverness that is characteristic of the \hacker culture“ than by sober assessments of technical requirements. Nevertheless this process has eventually produced both an industrial- strength programming language, messy but powerful, and a technically pure dialect, small but powerful, that is suitable for use by programming-language theoreticians.

Evolution of Lisp

“We were after the C++ programmers. We managed to drag a lot of them about halfway to Lisp.”

• Guy Steele, co-author of the Java spec

Paul Graham - Revenge of the Nerds

Key points of Common Lisp:

• Industrial
• Unification of many previous Lisp dialects (MacLisp and it’s successors).
• Standard Lisp dialect for large scale software projects
• Large & comprehensive (700 functions), advanced,

ANSI Common Lisp is a language specification, of which there are many implementations. Some popular:

• SBCL (Steel Bank Common Lisp), fork from CMUCL, fast, popular, well maintained & developed.
• Allegro Common Lisp
• LispWorks
• Clasp (LLVM, seamlessly interoperates with C++)
• CMUCL
• GNU Common Lisp (not fully ANSI), used by mathematical tools like Maxima & AXIOM.

(Most popular IDE for CL is Emacs, e.g. see this for minimal setup, or Lem, which is written in Common Lisp).

Scheme has an outsized importance in the world of programming languages compared to its actual use in industry, because it has so often pioneered features that later broke into the mainstream.

http://dpk.io/r7rswtf

Key points of Scheme:

• Academic,
• Minimal & clean
• For teaching and research & experimentation with programming language design
• Used in SICP
• Developed by committee releasing implementation standards “R^nRS” (“Revised n Report on the Algorithmic Language Scheme” ).

Some notable implementations:

• Racket, user friendly, comes with its own IDE (DrRacket)
• Chez Scheme (fastest),
• GNU Guile, preferred extension language for the GNU Project
• Chicken, compiles to C, portable, extensible
• Gambit, compiles to C, “unique blend of speed, portability and power”
• Chibi, minimal, for extension
• Kawa, runs on JVM,
• MIT/GNU Scheme, by Guy Steele & Gerald Jay Sussman

Let me repeat here what a radical decision it was to go and build a Scheme. The only Scheme implementation that had ever been built at this point was the research prototype Steele had done for his Masters. All serious Lisps in production use at that time were dynamically scoped. No one who hadn’t carefully read the Rabbit thesis believed lexical scope would fly; even the few people who had read it were taking a bit of a leap of faith that this was going to work in serious production use – the difference between theory & practice is, uh, larger in practice than in theory.

Olin Shivers: History of T

For some implementation benchmarks, see:

• Benchmarks
• Coverage

Interestingly, the statistical programming language R, is written on top of Scheme, and makes use directly from Lisp to use macros for creating Domain Specific Language (DSL) e.g. for ggplot2, dplyr and plyr.

As a side-note: this blog post talks about different implementations of Scheme, and its use for games programming, and on embedding:

S7 is an example of an embeddable Scheme. Guile is also used for extending C programs, though typically that involves dynamically linking to libguile rather than embedding the interpreter into the program’s executable. Fennel takes a different approach, recognizing that there are many existing applications that are already extensible through Lua, and provides a lispy language that compiles to Lua. …. The initial vision for Guile was to Emacsify other programs by adding a Scheme interpreter to them. These days, the best practice is to write your program in Scheme to begin with. Common Lisp is probably the best example, though. Implementations like SBCL have good C FFIs and can compile efficient native executables, minimizing the desire to use some C for performance reasons.

• Modern, compared to other Lisps (e.g. case sensitive, Lisp-1)
• Runs on JVM
• ClojureScript - compiles Clojure to JavaScript

For more, see:

• clojure-by-example - online documentation
• clojure for the brave and true - book
• Maria, a coding environment for beginners - tutorial

• elisp (aka Emacs Lisp) - Scripting language for GNU Emacs (and XEmacs)

• uLisp - Lisp for microcontrollers

  Lisp for Arduino, Adafruit M0/M4, Micro:bit, ESP8266/32, RISC-V, and Teensy 4.x boards.

• PetaLisp - for extreme parallelization / high performance computing

  Attempt to generate high performance code for parallel computers by JIT-compiling array definitions. It is not a full blown programming language, but rather a carefully crafted extension of Common Lisp that allows for extreme optimization and parallelization.

• PicoLisp (docs) - (1 MB) Focus on data, rather than code. Three data structures (nubmer, symbol, cons), all implemented as the internal single data type “cell”.

  In programming, the ultimate purpose is to manipulate data, not functions. Code and data are equivalent in Lisp, so you get the function manipulations for free anyway, but the focus should be on data.

• Hy / Hylang (embedded in Python as alternate syntax for Python)

  Compared to Python, Hy offers a variety of extra features, generalizations, and syntactic simplifications, as would be expected of a Lisp.

• hissp Scheme like & minimalist, full access to Python’s 3.8+ ecosystem

  It’s Python with a Lissp.

• Arc - (By Paul Graham) runs Hacker News web forum.
• Franz Lisp - Very popular in 70s & 80s. Name is pun on “Franz Liszt”. Discontinued.
• Fennel Lisp that compiles to Lua.

Metaprogramming was especially popular in the field of Artificial Intelligence, during 1970s & 80s, using Lisp. Since the language is itself a first-class data type, this makes it the quintessential language for metaprogramming. Wikipedia calls this homoiconicity, though that definition is a misnomer. Better to say: in Lisp the external and internal representation of the language (on which the virtual machine operates) is the same (or very close).

For comparison, Python is not homoiconic, as the external representation is the text file, and the internal is the bytecode on which the interpreter operates, while in Lisp both representations are s-expressions (at least in theory, in practice, it depends on implementation details). Likewise, C is not/less homoiconic, as the external representation is the program text, and the internal is machine code.

Although many languages do offer possibility for metaprogramming, or manipulating the Abstract Syntax Tree, we shall see that this is strongly dissuaded in all but a few languages.

Update [2024-07-15 Mon], A blog post demonstrating Lisp using Python: Homoiconic Python - McCarthy’s Lisp in Python lists

Most Python programmers rarely, if ever, have to think about metaclasses.

• realpython.com

Python provides metaclasses, which is a form of meta programming, that can dynamically re-program classes, through access to a dict of methods and attributes of the class. However, unless you know what you are doing, you are dissuade from using it. Example of its use case is e.g. how sklearn transformer can enforce that each inheriting class implements a fit() and transform() function).

Use cases (src):

• Check that class was defined correctly.
• Check that every module in our framework follows naming convention for methods/attributes.
• Raise errors during module import.
• Each time a base class is subclassed, we can run a specific code using metaclass.
• We often use special methods and metaclasses to change the way Python objects work. We can even extend Python syntax by creating our own domain-specific language (DSL) using the abstract syntax tree (AST).

Technically, one could construct string of valid Python code, and use eval:

x = 1
y = eval('x + 1')  # -> y = 2

# typical use:
eval(input())

C has something called pre-processing macros (lines starting with #) that do text substitution (simple search & replace) before compilation. For example:

(The word “macro” in computer science, comes from assembly programming’s macro-instructions, which looks like a single instruction, but expands into a sequel of instructions.)

C++ template programming is to Lisp macros what IRS tax forms are to poetry

Christian Stafmeister (2015, Google Tech Talk)

In C++ (and Mojo) we specify the input type of the parameters, and can have functions with same name, but different implementation, depending on the input type:

// square function for integers
int square(int x){
  return x*x;
}

// square function for float precision
float square(float x){
  return x*x;
}

Template system acts as a blueprint for the compiler to generate the code for overloaded functions, for only the types we use, at read time:

// Generate code for square function for each type we need:
template<typename T>
T square(T x){
  return x*x;
}

float a = 3.0f;
float aa = square(a);         // implicit

float bb = square<float>(3);  // explicit

(As of C++20 we can simply use auto keyword, for abbreviated function template).

The syntax for templates in C++ is very limited.

(Technically, one could have metaprogramming in C++, by linking the program to libclang, and have access to the AST of clang in the program, as noted).

Other languages have some for of metaprogramming capabilities, e.g.

Julia

has eval() and quote() and symbols & expressions dump() see docs for more.

Rust

see little book of rust macros for more.

Mojo

in the works.

Ruby

Inspired by Lisp, but considered odd:

… can leave you beset with strange and foreign methods, unfamiliar syntax, and downright mystifying blocks of code. It’s true: metaprogramming is a relatively advanced topic. If you want to really dig in and leverage it on a deep level, it will take time, effort, and a different way of thinking than you’re used to.

In order to write a macro, one typically starts with:

1. Writing the code we want it to output.
2. Write how you want to call/use the macro
3. Write the macro that meets 1. & 2.

There are some simple best practice rules to follow, see PCL ch 7 (and look up gensym).

A first and simple example (from PCL, ch. 3), demonstrates how we can make a new programming language that is the reverse of Lisp. I.e. identical syntax, except read from right-to-left. First consider the function reverse that does what the name suggests, when applied on lists:

(reverse '(1 2 3 4))     ;; => (4 3 2 1)

We can now define a macro that transforms regular Lisp to Backwards Lisp (right-to-left evaluation):

(defmacro backwards (expr) (reverse expr))

Now, only post-fix Lisp forms (reversed lists) are valid expressions in our Backwards Lisp language, that requires we wrap the Backwards Lisp in the backwards macro (compare how Python wraps valid Python code with the eval expression: eval("1 + 2")):

(backwards (2 1 +)) ;; => 3

In the above, the (invalid Lisp) expression (1 2 +) is noted to be an argument to a macro (a /special form/(!)), thus it is not evaluated, instead it is passed in as un-evaluated data to the macro body that reverses it to valid regular Lisp, that can then be evaluated.

(macroexpand-1 '(backwards (2 1 +))) ;; => (+ 1 2)

NOTE: Since the compiler will generate identical code for (+ 1 2) and (backwards (1 2 +)), the efficiency of Backwards Lisp is identical to normal Lisp.

Macros allow one to define a new syntax, e.g. to use C-syntax in Common Lisp, like with-c-syntax, or lisp With white space indentation, instead of parenthesis.

The backquote / quasiquote operator is useful when writing macros for unquoting. It allows us to insert values in a quoted expression, at program definition time (rather than at run time):

(defvar a 3)
'(1 2 a)                                ; => (1 2 a)
`(1 2 ,a)                               ; => (1 2 3)

Rather than use the literal symbol a, insert value of variable a.

Another useful way to think about the backquote syntax is as a particularly concise way of writing code that generates lists. This way of thinking about it has the benefit of being pretty much exactly what’s happening under the covers – when the reader reads a backquoted expression, it translates it into code that generates the appropriate list structure. For instance, `(,a b) might be read as (list a 'b). It’s important to note that backquote is just a convenience. But it’s a big convenience.

PCL

Here we demonstrate an actual use case for macros, by developing a unit test framework (based on PCL ch 9). It will consist of expressions, testing a case, and returning a boolean: true if passed, false if failed.

We saw in Reflections on “Growing a language, that Guy Steel argued:

New functionality added to the language by the user should be indistinguishable from functionality added by the language designers.

In fact, many parts of the core Lisp language is implemented as macros themselves. This is the case with conditionals like and, or, cond, etc. If these were implemented as functions, they would not be able to “short circuit”, i.e. abort evaluating the input arguments once the inevitable return value of the expression is known.

For example, consider the code below. If (x is 3) then the arguments will be evaluated to: True, False, and thus last will be left un-evaluated.

(and (= x 3) (> -1 0) (> 2 1))

Had and been a function, each of the three argument would have been evaluated, before the final result was returned by the and function.

By using macroexpand we can see the and macro generates nested if-statements:

(macroexpand '(and 1 2 3 4))

expands to:

(if (if 1
        (if 2
            3))
    4)

worth noting: since everything in Lisp evaluates to true, except NIL (which is an alias for the empty list), and will either return NIL (if false), or return the value of the last argument if all are true. In the example above, and returns 4.

Similarly, for the cond expression in Common Lisp (like switch in C/C++) is also a recursive macro, building nested if-statements, similar to Python’s if-elif-else pattern. (For more, see PCL ch 7).

In short, where a function will do, don’t use a macro. Macros are used for things functions can not do, such as:

• When we want to treat code as data (e.g. previous example)
• When we want to control (or prevent) evaluation of input arguments, i.e. operator needs access to parameters before they are evaluated (e.g. and).
• When you need performance by avoiding runtime function calls
• When it significantly improves readability of code, by providing a simple syntax for repeated patterns. Abstraction to clarify intent, as to not have half of the code pattern in the brain.

More on this soon, in Lisp vs other languages, especially the last point above, on how abstractions help move code patterns from the brain to the code.

Note: when we have bugs or crashes from macros, the error message will be from the resulting code the macro generated, not from the macro itself.

See When to use Macros (ch 8) in On Lisp (Paul Graham) for detailed discussion.

The three big moments in a Lisp expression’s life are read-time, compile-time, and runtime. Functions are in control at runtime. Macros give us a chance to perform transformations on programs at compile-time.

Paul Graham - On Lisp, p. 224 ch 17 (Reader Macro)

There are actually several different kinds of macros. The “normal” macros transform programs at compile time. However, before that, the code is read at read time, which is where we can apply reader-macros, to transform the syntax.

Macros and read-macros see your program at different stages. Macros get hold of the program when it has already been parsed into Lisp objects by the reader, and read-macros operate on a program while it is still text. However, by invoking read on this text, a read-macro can, if it chooses, get parsed Lisp objects as well. Thus read-macros are at least as powerful as ordinary macros.

Paul Graham - On Lisp, p 225 ch 17.1

1. Read-time - Reader-macros can reprogram the syntax, before parsing, e.g.
   • Syntactic sugar: replace quotes '<expression> with (quote <expression>)
   • Replace parenthesis with space indentation: wisp (“white space lisp”)
   • C-language syntax in Lisp: with-c-syntax
2. Compile time,
   • AST/Transform - Regular macros operate on semantic structure (Lisp objects), and have access to - and can manipulate - its AST
   • Compile time - Compile macros can hook into the compile process. Usually just for optimization.
3. Run-time - Functions execute expressions.

This is one of the “killer features” of Lisp, as it allows for incredibly powerful development and debugging through the REPL.

The whole language there all the time. There is no real distinction between read-time, compile-time, and runtime. You can compile or run code while reading, read or run code while compiling, and read or compile code at runtime.

Running code at read-time lets users reprogram Lisp’s syntax; running code at compile-time is the basis of macros; compiling at runtime is the basis of Lisp’s use as an extension language in programs like Emacs; and reading at runtime enables programs to communicate using s-expressions, an idea recently reinvented as XML.

Paul Graham - What made Lisp different

Let us investigate how one might go about implementing a function that generates an accumulator function, in various languages. The task is to:

• The generating function takes a number n
• Returns a function that takes another number i
• Which returns n incremented by i

Note:

• that’s number, not integer

• that’s incremented by (increase its value), not plus (add two values).

  f(n) -> g(i) -> (n=n+i)
  

(For solutions in many languages, see Accumulator Generator. This section is a re-write of the Appendix of this article)

In ANSI Common Lisp (page 1, 1996), Paul Graham notes, that simple functions can be written in any language, and look the same. For instance, the following function that returns the sum of numbers less than =n, in Lisp:

(defun sum (n)
  (let ((s 0))
    (dotimes (i n s)
      (incf s i))))

…and in C:

int sum(int n){
  int i, s = 0;
  for(i = 0; i < n; i++)
    s += i;
  return(s);
}

To do simple computing, any language will do. However, what if you want a function that takes a number n, and returns a function that adds n to its arguments:

(defun addn (n)
  #'(lambda (x)
      (+ x n)))

Which would be called using (funcall (addn 2) 40) returning 42.

Or in Scheme

(define (foo n)
  (lambda (x) (+ x n)))

Such a function can not be written in C. At least not anonymously, it has to be named. If C supported closures, you could write a function that returns a pointer to a function, that would capture the outer value n.

As of C++ 2011 you can write this function using the then newly introduced lambda function.

[n](int arg){ return arg + n; }

Before 2011, you might be able to pull something off by defining a custom class and overloading the () operator.

The Lisp REPL is part of the development process, it is not only used for exploration and debugging. It’s fun, it’s a productive boost, and it allows to catch errors earlier, both because we try functions earlier, and because we get type warnings when we compile the file or the current function (yes, we can compile a single function).

Python VS Common Lisp, workflow and ecosystem

Demonstrate connecting to lisp process of:

• My Nyxt web browser, written in common Lisp
• My StumpWM window manager, written in Common Lisp

From my Emacs. Then implement a “hello world” function, in either image, and call it from within the Nyxt web browser, or StumpWM window manager, to demonstrate that I have added a new function to these. While they were running!

(Or for demonstration see: this video, by Gavin Freeborn).

• Clasp: Common Lisp using LLVM and C++ for Molecular Metaprogramming by Professor Christian Schafmeister, Google tech talk 2015. (How he abandoned Python, for Lisp), (vid)
• ACM OOPSLA Conference: Growing a Language - Guy Steele, 1998, (vid)
• The AST and Me - Emily Morehouse-Valcarcel, PyCon 2018 (vid)
• Jeremy Howard demo for Mojo launch. (Demonstration of matrix multiplications, and Mandelbrot computation in Mojo), (vid)
• LAMBDA Functions: Powerful And Elegant Abstractions, EuroPython 2017 (vid)

• [SICP] Structure and interpretation of computer programs - Abelson, & Sussman
• [PCL] Practical Common Lisp - Peter Seibel. (Common Lisp)
• [PAIP] Paradigms of Artificial Intelligence Programming - Peter Norvig
• ANSI Common Lisp - Paul Graham (reference book)
• On Lisp - Paul Graham (advanced)
• [htdp] How to design programs

• The Roots of Lisp - Paul Graham (2002)
• “The Machine that Builds itself: How the Strengths of Lisp Family Languages Facilitate Building Complex and Flexible Bioinformatic Models” (arXiv, 2016)
• The history of Lisp - From McCarthy’s memory, ACM SIGPLAN conference 1978
• Lambda Calculus (2013) - (Hacker news discussion), math chapter
• Defense of Lisp macros: an automotive tragedy - “Replacing Lisp’s beautiful parentheses with dozens of special tools and languages, none powerful enough to conquer the whole software landscape, leads to fragmentation and extra effort from everyone, vendors and developers alike. The automotive field is a case in point.”

• Beating the averages - Paul Graham on how using Lisp in ViaWeb gave them super powers
• Revenge of the Nerds - Paul Graham on programming languages, and convergence
• Lisp as the Maxwell’s equations of software - Exploration of Alan Kay’s analogy.
• It’s Lambdas All the Way Down - On Lisp in Lisp, and lambdas as closures defining the whole language.
• Fun with Lambda Calculus - Introduction to lambda calculus, and Y-combinator.
• From Python to Common Lisp to Julia - One mans journey from Python to Common Lisp.
• Lisping at JPL - Ron Garret
• Casting spells in Lisp - On (crazy) persons humorous guide to Common Lisp.

• Python VS Common Lisp, workflow and ecosystem - From Python to Common Lisp

  This is the article I wish I had read earlier, when I was interested in Lisp but was a bit puzzled, because the Lisp way always seemed different, and I couldn’t find many voices to explain it. The Python way may not be the most practical or effective, Common Lisp might not be a dead language

• A Road to Common Lisp - A suggestion for how to get started
• Make a Lisp - Guide to implement a Lisp

• Racket Intro - Scheme implementation, with own editor.
• The Common Lisp Cookbook - Main online Common Lisp documentation resource
• Common Lisp HyperSpec - Online Common Lisp documentation
• common-lisp.net - A gate way to Common Lisp
• Crafting Interpreters - Good resource for understanding implementation of languages.

• numcl - Numpy clone in Common Lisp
• py4cl - Call Python libraries from Common Lisp
• cl4py - Call Common Lisp libraries from Python
• awesome-cl - Big collection of Common Lisp libraries, Frameworks and tools.

An S-expression is the fundamental unit of storage in Lisp. They are used to represent both source code and data. By the original definition, an S-expression is one of two things.

An atom

does not recursively store any more s-expressions, or

a cons cell

fundamental unit of composition in lisp, points to two other S-expressions: car (head/first), and cdr (rest/tail), respectively.

S-expressions denote the printed form of lisp objects. several s-expressions can map to the same symbol, e.g. foo, FOO, or 000, 0, #x0. They are different read syntax, equivalent through their semantics of denoting the same object. Lisp programs are valid S-expressions, but not all S-expressions are valid Lisp programs. For the s-expression to be valid code, then the first element in the list is usually an operator or function, and remaining elements are input arguments.

Note that modern Lisp dialects extend the definition of “atom” to include things like numbers.

Note: modern lisp dialects adds other data storage containers, like vectors

#(1 2 3 4)

Note that the ANSI Common Lisp standard does not use the terms S-expression or symbolic expression. No such terms appear in the Glossary, only expression, which is defined like this:

expression n. 1. an object, often used to emphasize the use of the object to encode or represent information in a specialized format, such as program text. “The second expression in a let form is a list of bindings.” 2. the textual notation used to notate an object in a source file. “The expression ‘sample is equivalent to (quote sample).”

(defmacro swap (a b)
  `(let ((tmp ,a)) (setf ,a ,b) (setf ,b tmp)))

problem: (swap tmp z) expands to:

(let ((tmp tmp)) (setf tmp z) (setf tmp tmp))

solution: Calling gensym to generate variable name guaranteed to not be used in code, solves Problems e.g.

(defmacro swap (a b)
  (let ((tmp (gensym)))
  `(let ((,tmp ,a)) (setf ,a ,b) (setf ,b tmp))))