From the Mind of Trevor Stone

It's October, which means I'm now allowing myself to start scheming about Advent of Code 2024. The last four years I've taken it as an opportunity to learn a new language. This year for some reason I'm inspired to learn a stack-oriented language, so I've been playing with PostScript. The world has generally moved on from PostScript: it gave birth to the wildly-popular PDF format without quite as much "Anything goes in this Turing-complete document presentation language," and even the latest version of macOS Preview.app can't read PostScript files. But if you set aside the fact that a majority of the language builtins are designed for using graphics, text, fonts, and printer hardware, it's a pretty slick language. You've basically got two things available: a stack of data and operands and a stack of dictionaries for dynamic name lookup. Both the programmer and the computer use basically the same model for evaluating code: read a token; if it's data then push it on the stack, if it's executable then run it, reading from the operator stack and writing to the same stack.

Programming language tutorials, particularly for functional languages, have a strong affinity for calculating the n'th Fibonacci number, but let's generate the whole sequence by just calling the same "function" over and over again (== is "print the source representation of the object on top of the stack and GS> is the Ghostscript prompt):

GS> /fib { 2 copy add } bind def
GS> [ 1 1 fib fib fib fib ] ==
[1 1 2 3 5 8]
GS> [ 1 1 15 { fib } repeat ] ==
[1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597]

Stack-based languages can have pretty simple syntax rules. That [ ] array syntax isn't "parse elements between the brackets as an array." Instead, the [ operator pushes a mark onto the stack and the ] operator builds an array with all the items on the stack until the first mark. Everything between the brackets is just normal PostScript code being executed on the stack. The following code builds an array of increasingly nested empty arrays by copying the whole array so far:

GS> [ 5 { counttomark [ exch 1 add copy pop ] } repeat ] ==
[[] [[]] [[] [[]]] [[] [[]] [[] [[]]]] [[] [[]] [[] [[]]] [[] [[]] [[] [[]]]]]]
% Or if you prefer some non-empty values to help read
GS> [ 42 5 { counttomark [ exch 1 add copy pop ] } repeat ] ==
[42 [42] [42 [42]] [42 [42] [42 [42]]] [42 [42] [42 [42]] [42 [42] [42 [42]]]] [42 [42] [42 [42]] [42 [42] [42 [42]]] [42 [42] [42 [42]] [42 [42] [42 [42]]]]]]

I've heard that some functional programming devotees might think of the non-negative numbers as a sequence of nested empty lists…

In PostScript, procedures are just arrays with the executable bit set, and you can construct and manipulate them as arrays. {} is syntax for an executable array, [] is syntax for a regular array, and cvx converts its operand to executable:

GS> { (hello world\n) print } exec
hello world
GS> % same thing:
[(hello world\n) (print) cvx] cvx exec
hello world

Since a procedure is just a mutable array of things to do, you can replace things in that array. Here's a self-modifying procedure that increments the first value inside itself, similar to a static int in a function in C:

GS> /selfmod { 1 (caller #) print == currentdict /selfmod get dup 0 get 1 add 0 exch put } bind def
GS> selfmod
caller #1
GS> selfmod
caller #2
GS> selfmod
caller #3

Page 115 of Thinking in PostScript defines a procedure by name including some initialization code; it then redefines itself without the initialization code the first time it's run. (The fact that the book is PDF file instead of a PostScript one says something indicative about the status of PostScript in the modern world.)

While PostScript has a couple hundred operators that are part of the language, a lot of those are for doing things like drawing on the page and selecting fonts. The parts of the "standard library" for working with strings and arrays is pretty spartan: even concatstrings is a Ghostscript addition, and I think people copy/pasted their own concatenation function all over the place for years. Since my Advent of Code interests don't include "Let's re-implement parsing a variable-width text file into fixed-size mutable strings each night," I've been getting some practice with the language by writing some core library functions that I'm certain will be used frequently.

I was about to work on the functional programming standbys like map and reduce, but I realized that with arrays constructed by "run all the code between brackets, then move everything from the stack between those brackets into an array" that having a separate function for map would just be extra noise and the basic iteration operator does the trick. Here's the PostScript equivalent of myarray.map { x -> x + 1 } and mydict.mapValues { i -> x * x }.

% Add 1 to each element of an array:
[ myarray { 1 add } forall ]
% Create a dictionary with the same keys as mydict, but square the values:
<< mydict { dup mul } forall >>

reduce (or fold depending on your dialect) is similarly straightforward if you supply with the accumulator rather than using the first array value. Here's myarray.reduce(0) { x, acc -> x + acc } (sum) and an implementation of myarray.all { x -> x % 2 == 0 } (are all items are even?).

0 myarray { add } forall
true myarray { 2 mod 0 eq and } forall

None of these need special handling for empty collections. They also work to iterate through bytes of a string (though there doesn't seem to be a short way to construct a string from an array of bytes). The all implementation can become an any by switching true to false and and to or. all becomes none by adding not before and. Short-circuiting can be added with dup { exit } if after the and/or.