TIL: The most powerful one-line program in the world

TIL: The most powerful one-line program in the world

Well, the most powerful I’ve found so far, anyway.

Given my current obsession with Lisp you might reasonably expect it to be in that language. But it isn’t: it’s in APL, and it performs one complete generation of Conway’ Game of Life in one line of code:

  Life←{↑↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

…and does so inexplicably to anyone who doesn’t know APL, obviously, but the basic algorithm is simple:

  1. Take an array with 1 in each occupied cell and 0 elsewhere
  2. Build four new arrays by exchanging each element with its neighbour up, down, left, and right
  3. Sum these arrays, which places the number of neighbours into each cell
  4. Cut-off these values to be 1 if the cell has a value of 3 or 4, and 0 otherwise
  5. Re-format the arrays back into the starting configuration

I checked it out using GNU APL and it works fine.

I discovered this gem by accident, actually implemented in APL in Forth where someone has developed APL as an embedded DSL within Forth (another language with which I have history). After a bit of digging I found a similar APL in Lisp, April, which clearly needs exploring.

In many ways APL and Lisp are parallel tracks within programming language evolution, taking a single data structure (lists or arrays) and providing powerful ways to manipulate them. Lisp of course has been extended with other data structures, including arrays, which makes the fusion of array- and list-based programming rather attractive.

I can’t help asking myself what would have happened if APL hadn’t fallen by the wayside. (I think this was inevitable, incidentally, once the syntax became fixed: any language that requires its own character set was always going to struggle.) We now have huge applications for array processing, from graphics to machine learning, and GPUs are from one perspective just APL accelerator co-processors. The ideas are still massively relevant.

Notes on Complexity: A Scientific Theory of Connection, Consciousness, and Being

Neil Theise (2023)

I’d heard a lot about this book, and expected a lot from it. Theise isn’t the first writer get lost in quantum weirdness, and he won’t be the last.

The first half is a tour of complexity science, focusing on where the boundaries of complex systems lie: the “quenched disorder” threshold between static order and complete disorder, and the existence of emergent phase changes in systems constructed from lots of simple interactions. Lovelock’s “daisyworld” is a great example of this, and Theise is very strong on assigning credit where it is due (Lynn Margulis’ contributions are often overlooked). It’s an approach that could be taken a lot further.

But then it all goes wrong, lost in the mazes of quantum theory and its superficial compatibilities with various kinds of mysticism. But there are lots of different mystic systems, and choosing to focus on three that have been selected for their similarities with a naive interpretation of quantum mechanics tells us precisely nothing about reality: there are plenty of others that are entirely incompatible (including most mainstream religions), which suggests it’s at least possible for mysticism and science to coincide by chance. And it’s a category error to then try to reason back from the mystic to the scientific in an attemot to “explain” complexity.

This absolutely isn’t what it claims to be – a scientific theory of consciousness and connectedness – because it commits the fundamental error of being selective with the data. Just because we can’t (yet) explain quantum entanglement and decoherence doesn’t mean that panpsychism has anything to tell us about reality. This sort of “reconciliation” of science (“western”) and mysticism (“eastern”) isn’t new, isn’t informative, and (to my mind) does both a disservice.

1/5. Finished Wednesday 17 July, 2024.

(Originally published on Goodreads.)

A New Kind Of Science

Stephen Wolfram (1997)

I have very mixed feelings about this book. On the one hand it’s a triumph of computational experimental technique, taking an idea that was well-known (cellular automata) and subjecting it to rigorous exploration. This uncovers a lot of new science, not least showing that complex systems can arise from even the simplest set of rules, but also that this complexity falls into classes that show graded complexity depending purely on the fine structure of the initial conditions. That’s a massively important discovery.

On the other hand…. It’s hard to describe this as a “new kind” of science. “New science,” yes, but not indicative of a new paradigm or way of doing science, other than by emphasising the structured use of simulation. Wolfram completely over-sells what he’s achieved, making claims he can’t substantiate to aggrandise his own contributions. And that’s a shame, not least because it’s so unnecessary: Wolfram has made some important discoveries, both here and to several other branches of physics and computer science, as well as popularising computational methods and tools. It’s tragic that he doesn’t seem to be able to appreciate himself as being sufficient.

The book is also quite terribly written, being almost half-composed of footnotes, meaning a reader is constantly skipping forwards and back: difficult in print, and I suspect impossible in a digital edition unless it’s been very carefully hyperlinked. And the footnotes are often important! – indeed, they often provide evidence to back-up a claim in the main text that’s entirely unsupportable from what’s been presented. So it can be seen as both excessively long and insufficiently detailed, which is quite an achievement.

3/5. Finished Sunday 7 July, 2024.

(Originally published on Goodreads.)

Shikasta: Canopus Dans Argos: Archives

Doris Lessing (1979)

Why is modern civilisation so self-destructive and complicated? The answer from this alternative history is that a previously time of happiness and long lives was subverted by a change in the universal forces to induce the current malaise.

I did enjoy this book, but it does live up to its sub-title: Personal, psychological, historical documents relating to visit by Johor (George Sherban) Emissary (Grade 9) 87th of the Period of the Last Days. It’s told in a very disjointed form using purported reports and other documents, much of the time from the diary of a young girl who doesn’t really know what’s going on, and so can’t really advance the plot very effectively. That makes it hard work, even though the writing and the overall premise are excellent.

2/5. Finished Sunday 7 July, 2024.

(Originally published on Goodreads.)

Let over Lambda

Let over Lambda

nil

Doug Hoyte. Let over Lambda. HCSW and Hoytech. ISBN 978-1-4357-1275-1. 2008.

A gloriously opinionated (in the best way) take on Lisp macro programming. The author treats Lisp – one of the first languages – as the ultimate, final language to which all others can (and should) be translated, since they’re simply special cases of Lisp forms. And he makes a surprisingly compelling case.

The material builds extensively on On Lisp, re-presenting the idea of anaphoric macros (those that bind lexical variables for use in their bodies) and extending them with pandoric macros that allow introspection into an otherwise closed lexical environment. A lot of these examples feel contrived as presented, but the techniques are anything but: powerful ways to build abstractions.

The finale is the implementation of Forth in Lisp, and then a reflection to allow Forth programs to define Lisp functions – converting a (transparent) threaded-interpreted structure into an (opaque) code block. It’s a slightly non-standard Forth, but it’s true to the basics and exposes issues like the implementations of interpretation, compilation, and tail recursion really well. It’s only another step to explore Lisp implemented in Forth through the medium of macro programming, which deserves a book itself.