Saturday, August 5, 2023

Off-sides Penalty

Many years ago I was under the delusion that if Lisp were more “normal looking” it would be adopted more readily. I thought that maybe inferring the block structure from the indentation (the “off-sides rule”) would make Lisp easier to read. It does, sort of. It seems to make smaller functions easier to read, but it seems to make it harder to read large functions — it's too easy to forget how far you are indented if there is a lot of vertical distance.

I was feeling pretty good about this idea until I tried to write a macro. A macro’s implementation function has block structure, but so does the macro’s replacement text. It becomes ambiguous whether the indentation is indicating block boundaries in the macro body or in it’s expansion.

A decent macro needs a templating system. Lisp has backquote (aka quasiquote). But notice that unquoting comes in both a splicing and non-splicing form. A macro that used the off-sides rule would need templating that also had indenting and non-indenting unquoting forms. Trying to figure out the right combination of unquoting would be a nightmare.

The off-sides rule doesn’t work for macros that have non-standard indentation. Consider if you wanted to write a macro similar to unwind-protect or try…finally. Or if you want to have a macro that expands into just the finally clause.

It became clear to me that there were going to be no simple rules. It would be hard to design, hard to understand, and hard to use. Even if you find parenthesis annoying, they are relatively simple to understand and simple to use, even in complicated situations. This isn’t to say that you couldn’t cobble together a macro system that used the off-sides rule, it would just be much more complicated and klunkier than Lisp’s.

Wednesday, July 26, 2023

The Garden Path

Follow me along this garden path (based on true events).

We have a nifty program and we want it to be flexible, so it has a config file. We make up some sort of syntax that indicates key/value pairs. Maybe we’re hipsters and use YAML. Life is good.

But we find that we to configure something dynamically, say based on the value of an environment variable. So we add some escape syntax to the config file to indicate that a value is a variable rather than a literal. But sometimes the string needs a little work done to it, so we add some string manipulation features to the escape syntax.

And when we deploy the program, we find that we’ve want to conditionalize part of the configuration based on the deployment, so we add a conditional syntax to our config language. But conditionals are predicated on boolean values, so we add booleans to our config syntax. Or maybe we make strings do double duty. Of course we need the basic boolean operators, too.

But there’s a lot of duplication across our configurations, so we add the ability to indirectly refer to other config files. That helps to some extent, but there’s a lot of stuff that is almost duplicated, except for a little variation. So we add a way to make a configuration template. Templating needs variables and quoting, so we invent a syntax for those as well.

We’re building a computer language by accident, and without a clear plan it is going to go poorly. Are there data types (aside from strings)? Is there a coherent type system? Are the variables lexically scoped? Is it call-by-name or call-by-value? Is it recursive? Does it have first class (or even second class) procedures? Did we get nested escaping right? How about quoted nested escaping? And good grief our config language is in YAML!

If we had some forethought, we would have realized that we were designing a language and we would have put the effort into making it a good one. If we’re lazy, we’d just pick an existing good language. Like Lisp.

Saturday, July 8, 2023

Playing with AI

Write a polemic about how omitting conditional expressions from a language is lazy and stupid.

Conditional expressions are a fundamental feature of any programming language that claims to be expressive, concise and elegant. They allow programmers to write complex logic in a single line, without the need for verbose and repetitive if-else statements. They also enable functional programming paradigms, such as pattern matching and recursion, that are essential for solving many problems efficiently and elegantly.
Omitting conditional expressions from a language is a sign of laziness and stupidity on the part of the language designers. It shows that they do not care about the needs and preferences of their users, who have to write more code, introduce more bugs, and suffer more frustration. It also shows that they do not understand the principles and benefits of functional programming, which have been proven by decades of research and practice. They are stuck in an imperative mindset, where everything has to be done with side effects and mutations.
A language without conditional expressions is a crippled language, that forces programmers to use hacks and workarounds to achieve what should be simple and natural. It is a language that discourages creativity, elegance and readability. It is a language that should be avoided by anyone who values their time, sanity and reputation.
Some examples of programming languages that don’t have conditional expressions are:
  • CoffeeScript
  • Go
  • Pascal
  • Rust

This isn't bad, but I wanted more vitriol. I asked and I got a screed that could have come out of comp.lang.functional Unfortunately, it thought better of it and erased its own output before I could snapshot it.

Wednesday, June 28, 2023

Fails Static Type Check, but Runs Anyway

Here’s a function that fails a static type check, but has no runtime type error:

(defun foo ()
  (sqrt (if (static-type-check? #’foo)

I suspect most people that favor static types will argue that this sort of program doesn’t count for some reason or other. I think this is more an example (albeit contrived) of the limitations of static type checking.

Tuesday, June 27, 2023

Tail recursion in REBOL

Many years ago I worked on a language called REBOL. REBOL was notable in that it used a variation of Polish notation. Function names came first, followed by the arguments in left to right order. Parentheses were generally not needed as the subexpression boundaries could be deduced from the arguments. It’s a bit complicated to explain, but pretty easy to code up.

An interpreter environment will be a lists of frames, and each frame is an association list of variable bindings.

(defun lookup (environment symbol)
  (cond ((consp environment)
         (let ((probe (assoc symbol (car environment))))
           (if probe
               (cdr probe)
               (lookup (cdr environment) symbol))))
        ((null environment) (error "Unbound variable."))
        (t (error "Bogus environment."))))

(defun extend-environment (environment formals values)
  (cons (map ’list #’cons formals values) environment))

define mutates the topmost frame of the environment.

(defun environment-define! (environment symbol value)
  (cond ((consp environment)
         (let ((probe (assoc symbol (car environment))))
           (if probe
               (setf (cdr probe) value)
               (setf (car environment) (acons symbol value (car environment))))))
        ((null environment) (error "No environment."))
        (t (error "Bogus environment."))))

We’ll use Lisp procedures to represent REBOL primitives. The initial environment will have a few built-in primitives:

(defun initial-environment ()
   (list #’+

A closure is a three-tuple

(defclass closure ()
  ((arguments :initarg :arguments :reader closure-arguments)
   (body :initarg :body :reader closure-body)
   (environment :initarg :environment :reader closure-environment)))

An applicable object is either a function or a closure.

(deftype applicable () ’(or closure function))

We need to know how many arguments a function takes. We keep a table of the argument count for the primitives

(defparameter +primitive-arity-table+ (make-hash-table :test #’eq))

(eval-when (:load-toplevel :execute)
  (setf (gethash #’* +primitive-arity-table+) 2)
  (setf (gethash #’< +primitive-arity-table+) 2)
  (setf (gethash #’+ +primitive-arity-table+) 2)
  (setf (gethash #’- +primitive-arity-table+) 2)
  (setf (gethash #’1- +primitive-arity-table+) 1)
  (setf (gethash #’print +primitive-arity-table+) 1)
  (setf (gethash #’zerop +primitive-arity-table+) 1)

(defun arity (applicable)
  (etypecase applicable
    (closure (length (closure-arguments applicable)))
    (function (or (gethash applicable +primitive-arity-table+)
                  (error "Unrecognized function.")))))

REBOL-EVAL-ONE takes a list of REBOL expressions and returns two values: the value of the leftmost expression in the list, and the list of remaining expressions.

(defun rebol-eval-one (expr-list environment)
  (if (null expr-list)
      (values nil nil)
      (let ((head (car expr-list)))
        (etypecase head

          ((or number string) (values head (cdr expr-list)))

           (case head

              (let ((name (cadr expr-list)))
                (multiple-value-bind (value tail) (rebol-eval-one (cddr expr-list) environment)
                  (environment-define! environment name value)
                  (values name tail))))

              (multiple-value-bind (pred tail) (rebol-eval-one (cdr expr-list) environment)
                (values (rebol-eval-sequence (if (null pred)
                                                 (cadr tail)
                                                 (car tail))
                        (cddr tail))))

                 (values (make-instance ’closure
                          :arguments (cadr expr-list)
                          :body (caddr expr-list)
                          :environment environment)
                  (cdddr expr-list)))

              (let ((value (lookup environment head)))
                (if (typep value ’applicable)
                    (rebol-eval-application value (cdr expr-list) environment)
                    (values value (cdr expr-list)))))))))))

If the leftmost symbol evaluates to something applicable, we find out how many arguments are needed, gobble them up, and apply the applicable:

(defun rebol-eval-n (n expr-list environment)
  (if (zerop n)
      (values nil expr-list)
      (multiple-value-bind (value expr-list*) (rebol-eval-one expr-list environment)
        (multiple-value-bind (values* expr-list**) (rebol-eval-n (1- n) expr-list* environment)
          (values (cons value values*) expr-list**)))))

(defun rebol-eval-application (function expr-list environment)
  (multiple-value-bind (arglist expr-list*) (rebol-eval-n (arity function) expr-list environment)
    (values (rebol-apply function arglist) expr-list*)))

(defun rebol-apply (applicable arglist)
  (etypecase applicable
    (closure  (rebol-eval-sequence (closure-body applicable)
                                   (extend-environment (closure-environment applicable)
                                                       (closure-arguments applicable)
    (function (apply applicable arglist))))

Evaluating a sequence is simply calling rebol-eval-one over and over until you run out of expressions:

(defun rebol-eval-sequence (expr-list environment)
  (multiple-value-bind (value expr-list*) (rebol-eval-one expr-list environment)
    (if (null expr-list*)
        (rebol-eval-sequence expr-list* environment))))

Let’s try it:

(defun testit ()
     define fib
       lambda (x)                         
        (if lessp x 2
            (add fib sub1 x
                 fib sub x 2))

     define fact
       lambda (x)
       (if zerop x
           (mult x fact sub1 x))

     define fact-iter
       lambda (x answer)
       (if zerop x
           (fact-iter sub1 x mult answer x))

     print fib 7
     print fact 6
     print fact-iter 7 1

CL-USER> (testit)


This little interpreter illustrates how basic REBOL evaluation works. But this interpreter doesn’t support iteration. There are no iteration special forms and tail calls are not “safe for space”. Any iteration will run out of stack for a large enough number of repetition.

We have a few options:

  • choose a handful of iteration specail forms like do, repeat, loop, for, while, until etc.
  • invent some sort of iterators
  • make the interpreter tail recursive (safe-for-space).
It seems a no brainer. Making the interpreter tail recursive doesn’t preclude the other two,. In fact, it makes them easier to implement.

To effectively support continuation passing style, you need tail recursion. This alone is a pretty compelling reason to support it.

But it turns out that this is easier said than done. Are you a cruel TA? Give your students this interpreter and ask them to make it tail recursive. The problem is that key recursive calls in the interpreter are not in tail position. These are easy to identify, but you’ll find that fixing them is like flattening a lump in a carpet. You’ll fix tail recursion in one place only to find your solution breaks tail recursion elsewhere.

If our interpreter is written in continuation passing style, it will be syntactically tail recursive, but it won’t be “safe for space” unless the appropriate continuations are η-reduced. If we look at the continuation passing style version of rebol-eval-sequence we’ll see a problem:

(defun rebol-eval-sequence-cps (expr-list environment cont)
  (rebol-eval-one-cps expr-list environment
    (lambda (value expr-list*)
      (if (null expr-list*)
          (funcall cont value)
          (rebol-eval-sequence-cps expr-list* environment cont)))))

We cannot η-reduce the continuation. We cannot make this “safe for space”.

But the continuation contains a conditional, and one arm of the conditional simply invokes the containing continuation, so we can η-convert this if we unwrap the conditional. We’ll do this by passing two continuations to rebol-eval-one-cps as follows

(defun rebol-eval-sequence-cps (expr-list environment cont)
  (rebol-eval-one-cps expr-list environment
     ;; first continuation
     (lambda (value expr-list*)
       (rebol-eval-sequence-cps expr-list* environment cont))
     ;; second continuation, eta converted
rebol-eval-one-cps will call the first continuation if there are any remaining expressions, and it will call the second continuation if it is evaluating the final expression.

This intepreter, with the dual continuations to rebol-eval-one-cps, is safe for space, and it will interpret tail recursive functions without consuming unbounded stack or heap.

But we still have a bit of an implementation problem. We’re allocating an extra continuation per function call. This doesn’t break tail recursion because we discard one of the continuations almost immediately. Our continuations are not allocated and deallocated in strict stack order anymore. We cannot easily convert ths back into a stack machine implementation.

To solve this problem, I rewrote the interpreter using Henry Baker’s Cheney on the M.T.A technique where the interpreter functions were a set of C functions that tail called each other and never returned. The stack would grow until it overflowed and then we’d garbage collect it and reset it. The return addresses pushed by the C function calls were ignored. Instead, continuation structs were stack allocated. These contained function pointers to the continuation. Essentially, we would pass two retun addresses on the stack, each in its own struct. Once the interpreter figured out which continuation to invoke, it would invoke the function pointer in the struct and pass a pointer to the struct as an argument. Thus the continuation struct would act as a closure.

This technique is pretty portable and not too bad to implement, but writing continuation passing style code in portable C is tedious. Even with macros to help, there is a lot of pointer juggling.

One seredipitous advatage of an implementation like this is that first-class continuations are essentially free. Now I’m not wedded to the idea of first-class continuations, but they make it much easier to implement error handling and advanced flow control, so if you get them for free, in they go.

With it’s Polish notation, tail recursion, and first-class continuations, REBOL was described as an unholy cross between TCL and Scheme. “The result of Outsterhout and Sussman meeting in a dark alley.”

Current versions of REBOL use a simplified interpreter that does not support tail recursion or first-class continuations.

Thursday, June 8, 2023

Lisp Essential, But Not Required

Here’s a weird little success story involving Lisp. The code doesn’t rely on anything specific to Lisp. It could be rewritten in any language. Yet it wouldn’t have been written in the first place if it weren’t for Lisp.

I like to keep a Lisp REPL open in my Emacs for tinkering around with programming ideas. It only takes a moment to hook up a REST API or scrape some subprocess output, so I have a library of primitives that can talk to our internal build tools and other auxiliary tools such as GitHub or CircleCI. This comes in handy for random ad hoc scripting.

I found out that CircleCI is written in Clojure, and if you connect to your local CircleCI server, you can start a REPL and run queries on the internal CircleCI database. Naturally, I hooked up my local REPL to the Clojure REPL so I could send expressions over to be evaluated. We had multiple CircleCI servers running, so I could use my local Lisp to coordinate activity between the several CircleCI REPLs.

Then a need arose to transfer projects from one CircleCI server to another. My library had all the core capabilities, so I soon had a script for transferring projects. But after transferring a project, we had to fix up the branch protection in GitHub. The GitHub primitives came in handy. Of course our internal systems had to be informed that the project moved, but I had scripting primitives for that system as well.

More requirements arose: package the tool into a docker image, deploy it as a microservice, launch it as a kubernetes batch job, etc. At each point, the existing body of code was 90% of the solution, so it only required small changes to the code to handle the new requirements. As of now, the CircleCI migration tool is deployed as a service used by dozens of our engineers.

Now Lisp isn’t directly necessary for this project. It could easily (for some definitions of easy) be rewritten in another language. But the initial idea of connecting to a Clojure REPL from another Lisp is an obvious thing to try out and only takes moments to code up. If I were coding in another language, I could connect to the REPL, but then I’d have to translate between my other language and Lisp. It’s not an obvious thing to try out and would take a long time to code up. So while this project could be written in another language, it never would have been. And Lisp’s flexibility meant that there was never a reason for a rewrite, even as the requirements were changing.

Tuesday, May 30, 2023

Raymarching in Lisp

It turns out there’s a nice functional variation of raytracing called raymarching. The algorithms involved are simple and elegant. The learning curve is shallow and you can generate great looking images without hairy trig or linear algebra.

We’ll follow the example of Georges Seurat and simply compute the color independently for each of myriads of pixels. This is efficiently done in parallel in real time on a GPU, but then you have to use shader language and I want to use Lisp. It is insanely inefficient to do this serially on the CPU in Lisp, but still fast enough to render an image in a couple of seconds.

Imagine you have some scene you want to render. There is a volume of 3-dimensional space the scene occupies. Now imagine we know for every point in 3-dimensional space how far away that point is from the nearest surface. This is a scalar value that can be assigned to any point. It is zero for every point that lies on a surface, positive for points above surfaces, and negative for points below. This is the SDF (Signed Distance Field). The SDF is all we need to know to generate a raytraced image of the scene.

We’ll use the SDF to feel our way through the scene. We’ll start at the tip of the ray we’re tracing. We don’t know where the surface is, but if we consult the SDF, we can determine a distance we can safely extend the ray without hitting any surface. From this new point, we can recur, again stepping along no further than the SDF at this new location permits. One of two things will happen: we either step forever or we converge on a surface.

(defun raymarch (sdf origin direction)
  (let iter ((distance 0)
             (count 0))
    (let* ((position (+ origin (* direction distance)))
           (free-path (funcall sdf position)))
      (if (< free-path +min-distance+)
          position  ;; a hit, a very palpable hit
          (unless (or (> count +max-raymarch-iterations+)
                      (> free-path +max-distance+))
            (iter (+ distance free-path) (+ count 1)))))))

To convert an SDF to a Seurat function, we trace an imaginary ray from our eye, through the screen, and into the scene. The ray origin is at your eye, and we’ll say that is about 3 units in front of the window. The ray will travel 3 units to the screen and hit the window at point (i,j), so the ray direction is (normalize (vector i j 3)). We march along the ray to find if we hit a surface. If we did, we compute the amount of light the camera sees using the Lambert shading model.

(defun sdf->seurat (sdf)
  (let ((eye-position (vector 0 0 -4))
        (light-direction (normalize (vector 20 40 -30))))
    (lambda (i j)
      (let* ((ray-direction (normalize (vector i j 3)))
             (hit (raymarch sdf eye-position ray-direction)))
        (if hit
            (* #(0 1 0) (lambert sdf hit light-direction))
            (vector 0 0 0))))))

Lambert shading is proportional to the angle between the surface and the light falling on it, so we take the dot product of the light direction with the normal to the surface at the point the light hits it. If we know the SDF, we can approximate the normal vector at a point by probing the SDF nearby the point and seeing how it changes.

(defun lambert (sdf hit light-direction)
  (dot (pseudonormal sdf hit) light-direction))

(defun pseudonormal (sdf position)
  (let ((o (funcall sdf position))
        (dsdx (funcall sdf (+ #(0.001 0 0) position)))
        (dsdy (funcall sdf (+ #(0 0.001 0) position)))
        (dsdz (funcall sdf (+ #(0 0 0.001) position))))
      (normalize (vector (- dsdx o) (- dsdy o) (- dsdz o)))))

These are all you need to generate good looking 3-d images from a SDF. Now the SDFs for primitive geometric shapes are pretty simple. Here is the SDF for a sphere.

(defun sdf-sphere (position radius)
  (lambda (vector)
    (- (length (- vector position)) radius)))

and the SDF for the ground plane

(defun sdf-ground (h)
  (lambda (vector)
    (+ (svref vector 1) h)))

Given the SDF for two objects, you can use higher order functions to compose them into a scene. Taking the minimum of two SDFs will give you the union of the shapes. Taking the maximum will give you the intersection of two shapes. Other higher order functions on SDFs can blend two SDFs. This has the effect of morphing the shapes together in the image.

I like this approach to raytracing because the arthimetic is straightforward and obvious. You only need the simplest of vector arithmetic, and you don’t need linear algebra or matrix math to get started (although you’ll want project matrixes later on when you want to move your camera around). I’m more comfortable with recursive functions than 3x3 matrices.

This approach to raytracing is best done on a graphics card. These algorithms are pretty straightforward to code up in shader language, but shader language is fairly primitive and doesn’t have higher order functions or closures. Code written in shader language has to be converted to not use closures and HOFs.