Spur – RISC IV: The Lisp Multiprocessor Workstation
thechipletter.substack.com
thechipletter.substack.com
I thought it was pretty widely accepted in the programming language community that Lisp has had a massive influence on the development of programming languages in general. I know it's not the only game in town, as it were, and that there's been lots of other interesting developments, but still. To imply that it hasn't been "relevant" seems like an uninformed comment to me.
Lisp is by no means the final word on programming languages, but its flexibility from its S-expression syntax to macros to its metaobject protocol makes it easier to bend the language to fit the problem rather than the usual approach of making the problem fit the implementation language, and this flexibility remains an enduring trait that continues to attract people.
Remember when it was highly controversial for Java (and then C++) to get lambda expressions and many treated us as egg-headed academic nerds for wanting those things?
I sure do.
Lisp syntax is nice to work with irrespective of everything else, which was quite a discovery, which came as a surprise. The Lisp project itself didn't expect it; Lisp was supposed to be programmed in M-expressions. Furthermore, there was a second generation project, Lisp 2, that provided an Algol-like syntax over top of the Lisp internals.
Because syntax matters, M-expressions and Algol syntax for Lisp fell by the wayside. Other subsequent attempts also faced very limited success.
Mathematica is the M-expression language. It's actually very expressive and has nice tricks like multimedia literals and the ability to do some fancy almost-tex rendering in expression, but deep down it's all sexps and lists and symbolic manipulation thereof (and an FFI).
(I think they tried to rebrand the language a couple of years back as "Wolfram", lol.)
This is an example of an M-Expression in the original definition of Lisp:
[eq[third[(A B C (D . E))];C]→cons[D;cdr[((A 1 2 3) B C)]; T→car[x]]
(COND ((EQ (THIRD (QUOTE (A B C (D . E)))) (QUOTE C))
(CONS (QUOTE D) (CDR (QUOTE ((A 1 2 3) B C)))))
(T (CAR X)))
(D B C)> astonishingly similar semantics
The "Wolfram language" has at its core a rewrite rule systems. Expressions are being rewritten by applying transformations to it. Lisp does not use anything like that. Lisp has an evaluator mechanism, based on fixed evaluation rules (+ macro transformations, which are again Lisp functions).
As a result, code in the Wolfram language is difficult to (fully) compile. Good and extensive Lisp compilers exist since the early 60s. Current examples of complete compilers are SBCL for Lisp and Chez Scheme for Scheme.
The Wolfram language also has no formal spec (compare to something like Scheme) and the language itself is not open sourced, including its main implementation. It's basically defined by its main implementation, while its proprietary language documentation looks like written in a such way to prevent implementations of the language.
I can't argue with any of your points, but I'd like to mention that Mathematica's internal compiler is pretty capable and if you do something like Plot[f, xs] it will automatically try to compile f before evaluating it at all the points.
> internal compiler is pretty capable
Depends, when reading the documentation, one gets the impression that their compiler is very limited.
Maybe you could explain that one for the benefit of myself and the other mortals.
Here follows an excerpt from a paper "Some History of Functional Programming Languages" by D. A. Turner. It talks about LISP, as invent/discovered by John McCarthy:
https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf
-----
Something called “Pure LISP” never existed — McCarthy (1978) records that LISP had assignment and goto before it had conditional expressions and recursion — it started as a version of FORTRAN I to which these latter were added. LISP 1.5 programmers made frequent use of setq which updates a variable and rplaca, rplacd which update the fields of a CONS cell.
LISP was not based on the lambda calculus, despite using the word “LAMBDA” to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions.
The M-language was first order, as already noted, but you could pass a function as a parameter by quotation, i.e. as the S-expression which encodes it. Unfortunately, this gives the wrong binding rules for free variables (dynamic instead of lexicographic).
If a function has a free variable, e.g y in
f = λx.x + y
McCarthy (1978) reports that this problem (wrong binding for free variables) showed up very early in a program of James Slagle. At first McCarthy assumed it was a bug and expected it to be fixed, but it actually springs from something fundamental — that meta-programming is not the same as higher order programming. Various devices were invented to get round this FUNARG problem, as it became known.
Not until SCHEME (Sussman 1975) did versions of LISP with default static binding appear. Today all versions of LISP are lambda calculus based.
-----
"Today all versions of LISP are lambda calculus based.", except where they are not, like evaluation rules, dynamic binding, data types, etc.
What we have now in most Lisps since the mid 80s is lexical binding and closures, but not exclusively. Scheme earlier called dynamic bound variables "fluids". CL has it, for example by default for global variables.
- The original Lisp was based on mutable singly linked lists. Lambda calculus has no lists, except for Church-encoded ones (just like lambda calculus only has Church encoded booleans and numbers). It also doesn't have mutability.
- Later, Common Lisp (which was a unification of the Lisp variants that had descended from Lisp 1.5) also grew an object system, and it was implemented using dynamic scoping and dynamic typing. That stuff definitely has nothing to do with lambda calculus.
If you want an implementation of the lambda calculus, you could try Haskell 98 or Standard ML. Those are based on System F [0], a kind of typed lambda calculus.
While Lambda calculus only has 1 argument functions, you can use those to encode lists [1] and numbers in many ways, including unary, binary, and ternary [2].
[1] https://en.wikipedia.org/wiki/Church_encoding#List_encodings
[2] https://bruijn.marvinborner.de/std/Number_Ternary.bruijn.htm...
Which is why it's strange for trealira to single out Church encoded booleans and numbers.
Coming back to that argument after a day, though, it admittedly seems like a weak argument; after all, Standard ML supports mutability and linked lists natively as well, and I gave that as an example of typed lambda calculus. Maybe a better argument is that it's dynamically typed, whereas I don't think there are dynamically typed formations of lambda calculus.
This is the system that comes to mind for me when I think of "lambda calculus" because it is the one that was most important in the history of computability and logic, it can express the same computable functions as Turing machines. System F is not Turing complete.
1. Lambda calculus has only function terms. Lisp has many types: symbols, strings, conses, vectors, characters, integers, floating-point numbers, ...
2. Lambda calculus has no list processing.
3. Lambda calculus has no quote operator to operate on pieces of its own syntax as data. There is no straightforward way to write a meta-circular interpreter for lambda calculus in lambda calculus. (There are papers about it if you want to see how hard this is.) Lisp evaluation defined in Lisp before it was even implemented, in a small number of definitions.
4. Lambda calculus has no functions with optional arguments, or variadic functions. Only functions of one argument, which is required (using currying to simulate more arguments).
5. Lambda calculus has no dynamic control transfers: throw/catch, restarts; no object system; no interactivity.
6. Lambda calculus has no symbols and no named entities: no global function environment. No dynamic/global variables. No mutable variables. No "goto" analogous to Common Lisp tagbody/go.
tromp is the local expert around here and may have something more enlightening to say.
Disagree. Some people find it tolerable for the sake of lisp advantages (mainly macros). Very few find it outright preferable. The existence and popularity of reader macros is proof of this.
> Because syntax matters, M-expressions and Algol syntax for Lisp fell by the wayside.
Because they were bad syntax. And because syntax isn't the only thing that matters. A good syntax that didn't compromise the ease of writing macros would win out, if such a thing were possible.
In Lisp circles, I would say that the majority of the people find Lisp syntax preferable. Opinions similar "I'm only tolerating this to get to the macros" are hardly ever heard. The opinion, "I wish this non-Lisp language I have to work with were written in S-expressions" is often heard.
Lisp syntax is uniform, consistent, easily formatted in different levels of line breaking, easily manipulated by text editors.
There is no ambiguity due to associativity of precedence. You never wonder which expressions belong to which operator.
I got hooked on Lisp before Lisp macros became a meme; I liked working with it before learning about macros.
Lisp-syntax front ends for non-Lisp languages prove that there are communities of people who prefer that syntax. E.g. Hy or Hissp for Python, Fennel for Lua and such.
Lisps have a considerable amount of notation in addition to the parentheses. Not everything in the written source code is denoted by an open parenthesis and symbol. That's a strawman view of Lisp syntax. However, the notations are token notations that play along with the rest of the syntax.
Not all languages in the Lisp family or Lisp-likes have reader macros. Scheme doesn't have them, except the descendant Racket dialect which has the #lang thing. The Lisp-like functional language Clojure doesn't have reader macros, yet is quite popular.
In TXR Lisp, I intentionally didn't provide reader macros.
Reader macros are not heavily used in Common Lisp. Not all uses of reader macros in Common Lisp programs and libraries are for the purpose of deviating from the concepts of Lisp syntax.
Reader macros have disadvantages:
- the Lisp printer doesn't know about the syntax and doesn't use it.
- external code tooling doesn't know about reader macros: everything from syntax coloring to identifier cross-referencing and whatnot. That makes reader macros disruptive.
- reader macros can clash. (In the Common Lisp FOSS landscape, there is now a "named readtables" module for disciplined use of multiple custom syntaxes).
print (x);
(print x)
if (cond) {
do_a();
} else {
do_b();
}
(if cond
do_a
do_b)
"Implementing Lambda Expressions in Java with Brian Goetz"
https://www.youtube.com/watch?v=Uns1dm3Laq4
C++ lambdas follow the functor class model, and they also capture the environment, the only difference is that we get to say what we want captured.
Numpy 2.0 came out two days ago and it's chaos in the whole AI ecosystem. I'm not sure how much money we're wasting on that but I wouldn't be surprised if it's on the order of a billion dollars - suppose there are 50,000 people getting paid on the order of $1,000 per day each spending the two week dealing with fires over the next year: $500,000,000
It is possible to build binaries against NumPy 2.0 that will work at runtime with both NumPy 2.0 and 1.x. See NumPy 2.0-specific advice for more details."
https://numpy.org/devdocs/dev/depending_on_numpy.html#numpy-...
They bumped the major number. That's fair play. There has always been a lot of slouching wrt versions in python. That's not numpy's fault. Too bad they're getting the black eye for it. They could have avoided it by making a new dependency name ("numpy2"), but that sets a shameful precedent, so I give them credit for not copping out.
I viscerally understand how companies can get stuck and unable to change their products significantly because their installed base will revolt. It's a tough situation.
Well, if that's how you're going to behave, foregoing entirely obvious and solved engineering problems, you get to glue all the pieces back together when reality asserts itself. I don't imagine for one minute numpy folks didn't know what this would look like, and they did it anyway. Good on them. Breaking changes are necessary. That's unqualified. Necessary. If you can't afford a big blowup in your work then manage your work.
The Tree of Elegance needs to be refreshed with the blood of both users and programers. Or something like that.
We'd not get very far is the Linux Kernel made breaking ABI changes every year.
We need to use a lock file really, but `pip` doesn't support that - you need to use a better package installed like `uv` to get this standard feature.
You are talking about the tagged add and subtract instructions, TADDcc/TSUBcc, and their trapping versions TADDccTV/TSUBccTV.
> Using that on top of some kind of Unix is shall we say problematic (in same way that x86 BOUNDS is mostly useless), together with few other “fast conditional trap” instructions in SPARC ISA, but it is there.
I've never tried using it, but why is it "problematic" on Unix? From what I understand, both on Solaris SPARC and Linux SPARC, the kernel translates the tag-overflow exception into a SIGEMT signal with si_code=EMT_TAGOVF, so you can catch the tag-overflow exception by installing a SIGEMT handler. On Linux SPARC, I think SIGEMT is only used for tag-overflow, whereas on Solaris it also is triggered by CPU performance counter overflow (EMT_CPCOVF)
I think TADDccTV/TSUBccTV are problematic in the sense that they are officially deprecated, and only supported for 32-bit overflow, not 64-bit overflow. The docs say to use BPVS instead (so branch on overflow flag instead of trapping an overflow exception)
All that said, this all has very fading relevance now, given how moribund SPARC is. Oracle has no plans to introduce any further SPARC CPUs, the SPARC CPUs they currently sell were released 7 years ago, and I expect they'll stop selling them sooner or later. Fujitsu has announced they'll end SPARC server sales in 2029, which is only 5 years away now, and although they were at one point talking about one last CPU after the current M12 generation, I doubt that's still happening.
OTOH, my view is somewhat LISP-centric and just implementing + by passing the arguments to taddcctv would be problematic, in the Smalltalk world, implementing SmallInteger>>#+ like that makes sense.
https://en.wikipedia.org/wiki/Intel_iAPX_432
It was a commercial failure.
The iAPX 432 programming model is a stack machine with no visible general-purpose registers. It supports object-oriented programming, garbage collection and multitasking as well as more conventional memory management directly in hardware and microcode. Direct support for various data structures is also intended to allow modern operating systems to be implemented using far less program code than for ordinary processors.
https://www.youtube.com/watch?v=DIccm7H3OA0
I'm so glad we have these sorts of things archived!
Hmm, looks like https://www.softwarepreservation.org/projects hasn't been submitted to HN in some years.
[0] Parallel Lisps / SPUR Lisp https://www.softwarepreservation.org/projects/LISP/parallel#... [1] SPUR Lisp: Design and Implementation https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-373... [2] Features for Multiprocessing in SPUR Lisp http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-406.... [3] Implementation of Multiprocessing SPUR Lisp http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-459....
Design Decisions in SPUR: https://pages.cs.wisc.edu/~markhill/papers/computer86_spur.p...
SPUR: A VLSI Multiprocessor Workstation: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/CSD-86-273...
Multiprocessing extensions in Spur Lisp: https://ieeexplore.ieee.org/document/31651
Apart from CHERI extensions, and a few research papers on hardware-accelerated garbage collection (which I find super cool, and wonder why it isn't getting into actual production, given e.g. how stable Java GC is and how many huge companies use Java. Or maybe offloading it to an FPGA? The same way we have GPUs and TPUs for certain classes of computation?).
The article doesn't really mention transputers, which were existent at the time and were remarkably similar in vision, with parallel multiprocessing, hardware network links, the Occam language, a ground-up Helios OS, and custom graphics card (Blossom, which would lead to the VGA standard).
Having a 3-element hardware stack somewhat restricts the use of languages on it - I imagine that Occam is similar to Forth in operation?
Therefore
Forth -> Forthic
Forth -> Forsemen
(The less gendered "Fordlander" is also acceptable)
Forthsider, from the Firth of Forth?
Apart from Occam, there where C, C++ and Fortran compilers. Targeting the transputer is not more difficult than any other stack machine (like the JVM, the .Net CLR, CPython or Pascal p-code).
The weird/interesting thing about the transputer is that it is also an operating system: two task queues (high/low priority), preemptive scheduling and communication through channels (that can be one of the 4 serial ports or memory based).
Once it's truly dead pushing more features into silicon will the be only way we can get speedups and this will become a major research area again.
There is also hardware acceleration for many audio and video codecs. "GC as a codec" doesn't strike me as something crazy: both are upgraded from time to time, but both are stable enough that hardware implementations are relevant over several years. Android phones would certainly benefit from it!
Accelerating a particular language runtime is a different story.
TBH people don't seem to have a problem generally with "throwing cycles away" and adopting languages like Python which have a pretty slow execution story. There's clearly not much of an economic advantage in optimization for processor throughput, otherwise more stuff would be getting [re]written in systems languages like C/C++/Rust/Zig etc, which would be a lot cheaper than developing custom hardware.
And frankly most of the stuff that gets funding and people seem to get excited about in our industry right now... doesn't need much CPU. It's mostly just glue languages waiting on I/O. Apart from the ML/LLM hype right now, which relies heavily on... GPUs.
I have a book here somewhere on the Linn Rekursiv hardware. Custom OO system in hardware in the 80s. Up there with Lisp machines as exotic and interesting "paths not taken".
[0] https://www.ibm.com/support/pages/pause-less-garbage-collect...
[1] https://www.oracle.com/a/ocom/docs/sparc-t8-m8-server-archit...
You'll still find people making the case that we have continued to specialize computer hardware for a specific language, that language being C. They kind of have a point. I see it as more symbiotic than that: C caught on in large part because its abstract machine was a good fit for real hardware†, and that real hardware is the way it is because it's a Pareto-optimal way to do computation.
Fact is that most languages don't have a semantics which could be accelerated much in hardware. Take Java for an example: it's possible to implement the JVM as a chip, but then you have a stack machine, and you can't JIT it onto a register architecture.
What we do now is make the chip as fast as we can at doing the basic things a computer needs to do, and only that (this is the essence of RISC). That offloads making programs fast to compilers, which can do a better job of it if the instructions they're working with are very basic, and have a (reasonably) predictable duration and behavior. Itanium was the last serious attempt to disprove that thesis, and also failed rather spectacularly. The Mill is the latest contender, and well, I wish them luck.
That may not be the final word though, people should keep trying the "language on a chip" approach, and some still are. I have a hunch that Erlang semantics might be a good target for hardware-specific acceleration, there should be some degrees of freedom available from knowing that data is only shared between processes via a strict ABI. And just because implementing garbage collectors in hardware didn't really pay off in the 1980s doesn't mean that it's physically impossible to have a win with that approach. I'm just sketching out why you don't see that kind of thing much these days.
† C has been described as a "portable assembly language" and that has become steadily less true. That would be a stronger reading of my statement than I intended.
I don’t think they’d describe CUDA. Something more APL-like, I’d imagine.
EDIT: Maybe … https://dl.acm.org/doi/pdf/10.1145/319838.319870
"hardware" in quotes. A bunch of the machines had no/little language specific hardware. For example an Xerox Interlisp-D machine was the same hardware like the Smalltalk or Mesa system. The microcode was different. The microcode provided the instruction set and then the machine would boot either into the corresponding operating systems for Interlisp, Smalltalk or Mesa. https://en.wikipedia.org/wiki/Xerox_Star
Similar for the MIT CADR and some others, it was also a microprogrammed 32bit CPU.
Symbolics' CPU were also microprogrammed, but they added hardware features to it.
The SPUR (which is a RISC chip) mentioned is a more generic design, but with support for languages features for Lisp. There were other chips in the making at that time, like the Symbolics Sunstone CPU, which was also a RISC design for Lisp, but which also did not reach the market.
> Take Java for an example: it's possible to implement the JVM as a chip, but then you have a stack machine, and you can't JIT it onto a register architecture.
One could do that, but it would be a more complex chip.
For Lisp CPUS "fast" for benchmarks was also not that much a goal. Goals oftenwere "fast" execution of a Lisp operating system (written in a dynamically typed and garbage collected language), support for large address spaces, support for Lisp data types&data representation, generic operations (like generic arithmetic operations) and compact machine code.
(let* ((x '(a b c))
(y (cdr x))
(z (copy-list (cdr x))))
(format t "y=~A, z=~A~%" y z)
(setf (nth 1 x) 'w)
(format t "y=~A, z=~A~%" y z))
y=(B C), z=(B C)
y=(W C), z=(B C)
To make a mutable list, you could write (list a b c).
If I replace ‘(a b c) in my example with (list ‘a ‘b ‘c) I got the same results.
Yeah, your core point was right, just thought to let you know about that bit of undefined behavior.
I recall seeing either on IRC or reddit someone asking about why their code wasn't working as expected, and it lead back to needing to understand that the string literal in their code was getting updated - so likely similar to the UB in C that you mentioned. Until seeing that post, I wasn't really aware of that potential issue with literals, so I think it's good to point these things out. Recently, I saw it was mentioned in "Successful Lisp"; it might be mentioned in other books I've read, but maybe I just didn't pick up on it.
That’s comparing apples with oranges. The POWER4 had two cores on a single die (https://en.wikipedia.org/wiki/POWER4) while in this system (FTA) “a processor would consist of three custom VLSI designs and around two hundred other chips”
Multiprocessing systems are much older, for example C.mmp (https://dl.acm.org/doi/10.1145/1480083.1480098, https://en.wikipedia.org/wiki/C.mmp) from 1971 (possibly also a bit of apples and oranges, but if so, IMO less so than in this article)