Posts tagged lisp

Yet another description of macroexpansion in Common Lisp. There is nothing particuarly new here and it partly duplicates some previous articles: I just wanted to rescue the text.

Here’s a simple example of dealing with a naturally circular function definition.

Common Lisp is, I think, a remarkably pleasant language, despite what some people like to say. Here are two small deficiencies, both of which are understandable in terms of the history of CL, and both of which ultimately hurt naïve programmers working in CL.

It seems that my article about the existence in the Lisp community of rather noisy people who seem to enjoy complaining rather than fixing things has atracted some interest. Some things in it were unclear, and some other things seem to have been misinterpreted: here are some corrections and clarifications.

Someone asked about better Lisp IDEs on reddit. Such things would obviously be desirable. But the comments are entirely full the usual sad endless droning from people who need there always to be something preventing them from doing what they pretend to want to do, and are happy to invent such barriers where none really exist. comp.lang.lisp lives on in spirit if not in fact.

[The rest of this article is a lot ruder than the above and I’ve intentionally censored it from the various feeds. See also corrections and clarifications.]

People learning Lisp often try to learn how to write macros by taking an existing function they have written and turning it into a macro. This is a mistake: macros and functions serve different purposes and it is almost never useful to turn functions into macros, or macros into functions.

People sometimes ask which is the best Lisp dialect? That’s a category error, and here’s why.

Or: things you do to distract yourself from watching an attempted fascist coup.

The U combinator allows you to define recursive functions and I think it is simpler to understand than the Y combinator.

It’s not obvious how things like letrec get defined in Scheme, without using secret assignment. In fact I think they are defined using secret assignment:

(letrec ([f (λ (...) ... (f ...) ...)])
  ...)

turns into

(let ([f ...])
  (set! f (λ (...) ... (f ...) ...))
  ...)

But it’s interesting to see how you can define recursive functions without relying on assignment, including mutually-recursive collections of functions. One way is using the U combinator.

I suspect that there is lots of information about this out there, but it’s seriously hard to search for anything which looks like ’*-combinator’ now (even now I am starting a set of companies called ‘integration by parts’, ‘the quotient rule’ &c).

You can famously do this with the Y combinator, but I didn’t want to do that because Y is something I find I can understand for a few hours at a time and then I have to work it all out again. But it turns out that you can use something much simpler: the U combinator. It seems to be even harder to search for this than Y, but here is a quote about it:

In the theory of programming languages, the U combinator, \(U\), is the mathematical function that applies its argument to its argument; that is \(U(f) = f(f)\), or equivalently, \(U = \lambda f \cdot f(f)\).

Self-application permits the simulation of recursion in the λ-calculus, which means that the U combinator enables universal computation. (The U combinator is actually more primitive than the more well-known fixed-point Y combinator.)

The expression \(U(U)\) is the smallest non-terminating program.

(Text mildly edited from here, which unfortunately is not a site all about the U combinator other than this quote.)

Prerequisites

All of the following code samples are in Racket. The macros are certainly Racket-specific and some of the other code probably is as well. To make the macros work you will need syntax-parse via:

(require (for-syntax syntax/parse))

However note that my use of syntax-parse is naïve in the extreme: I’m really just an unfrozen CL caveman pretending to understand Racket’s macro system.

Also note I have not ruthlessly turned everything into λ: Rather than ((λ (...) ...) ...) there is (let ([... ...] ...) ...) in this code; there is use of multiple values including let-values; there is (define (f ...) ...) rather than (define f (λ (...) ...)) and so on.

Two versions of U

The first version of U is the obvious one:

(define (U f)
  (f f))

But this will run into some problems with an applicative-order language, which Racket is by default. To avoid that we can make the assumption that (f f) is going to be a function, and wrap that form in another function to delay its evaluation until it’s needed: this is the standard trick that you have to do for Y in an applicative-order language as well. I’m only going to use the applicative-order U when I have to, so I’ll give it a different name:

(define (U/ao f)
  (λ args (apply (f f) args)))

Note also that I’m allowing more than one argument rather than doing the pure-λ-calculus thing.

Using U to construct a recursive functions

To do this we do a similar trick that you do with Y: write a function which, if given a function as argument which deals with the recursive cases, will return a recursive function. And obviously I’ll use the Fibonacci function as the canonical recursive function.

So, consider this thing:

(define fibber
  (λ (f)
    (λ (n)
      (if (<= n 2)
          1
          (+ ((U f) (- n 1))
             ((U f) (- n 2)))))))

This is a function which, given another function, U of which computes smaller Fibonacci numbers, will return a function which will compute the Fibonacci number for n.

In other words, U of this function is the Fibonacci function!

And we can test this:

> (define fibonacci (U fibber))
> (fibonacci 10)
55

So that’s very nice.

Wrapping U in a macro

So, to hide all this the first thing to do is to remove the explicit calls to U in the recursion. We can lift them out of the inner function completely:

(define fibber/broken
  (λ (f)
    (let ([fib (U f)])
      (λ (n)
        (if (<= n 2)
            1
            (+ (fib (- n 1))
               (fib (- n 2))))))))

Don’t try to compute U of this: it will recurse endlessly because (U fibber/broken) -> (fibber/broken fibber/broken) and this involves computing (U fibber/broken), and we’re doomed.

Instead we can use U/ao:

(define fibber
  (λ (f)
    (let ([fib (U/ao f)])
      (λ (n)
        (if (<= n 2)
            1
            (+ (fib (- n 1))
               (fib (- n 2))))))))

And this is all fine ((U fibber) 10) is 55 (and terminates!).

Purists can then turn let into λ in the usual way:

(define fibber
  (λ (f)
    ((λ (fib)
       (λ (n)
         (if (<= n 2)
             1
             (+ (fib (- n 1))
                (fib (- n 2))))))
     (U/ao f))))

And this is really all you need to be able to write the macro:

(define-syntax (with-recursive-binding stx)
  (syntax-parse stx
    [(_ (name:id value:expr) form ...+)
     #'(let ([name (U (λ (f)
                        (let ([name (U/ao f)])
                          value)))])
         form ...)]))

Or, for the pure of heart:

(define-syntax (with-recursive-binding stx)
  (syntax-parse stx
    [(_ (name:id value:expr) form ...+)
     #'((λ (name)
          form ...)
        (U (λ (f)
             ((λ (name)
                value)
              (U/ao f)))))]))

And this works fine:

(with-recursive-binding (fib (λ (n)
                               (if (<= n 2)
                                   1
                                   (+ (fib (- n 1))
                                      (fib (- n 2))))))
  (fib 10))

A caveat on bindings

One fairly obvious thing here is that there are two bindings constructed by this macro: the outer one, and an inner one of the same name. And these are not bound to the same function in the sense of eq?:

(with-recursive-binding (ts (λ (it)
                              (eq? ts it)))
  (ts ts))

is #f. This matters only in a language where bindings can be mutated: a language with assignment in other words. Both the outer and inner bindings, unless they have been mutated, are to functions which are identical as functions: they compute the same values for all values of their arguments. In fact, it’s hard to see what purpose eq? would serve in a language without assignment.

This caveat will apply below as well.

Two versions of U for many functions

The obvious generalization of U, U*, to many functions is that \(U^*(f_1, \ldots, f_n)\) is the tuple \((f_1(f_1, \ldots, f_n), f_2(f_1, \ldots, f_n), \ldots)\). And a nice way of expressing that in Racket is to use multiple values:

(define (U* . fs)
  (apply values (map (λ (f)
                       (apply f fs))
                     fs)))

And we need the applicative-order one as well:

(define (U*/ao . fs)
  (apply values (map (λ (f)
                       (λ args (apply (apply f fs) args)))
                     fs)))

Note that U* is a true generalization of U: (U f) and (U* f) are the same.

Using U* to construct mutually-recursive functions

I’ll work with a trivial pair of functions:

• an object is a numeric tree if it is a cons and its car and cdr are numeric objects;
• an objct is a numeric object if it is a number, or if it is a numeric tree.

So we can define ‘maker’ functions (with an ’-er’ convention: a function which makes an x is an xer, or, if x has hyphens in it, an x-er) which will make suitable functions:

(define numeric-tree-er
  (λ (nter noer)
    (λ (o)
      (let-values ([(nt? no?) (U* nter noer)])
        (and (cons? o)
             (no? (car o))
             (no? (cdr o)))))))

(define numeric-object-er
  (λ (nter noer)
    (λ (o)
      (let-values ([(nt? no?) (U* nter noer)])
        (cond
          [(number? o) #t]
          [(cons? o) (nt? o)]
          [else #f])))))

Note that for both of these I’ve raised the call to U* a little, simply to make the call to the appropriate value of U* less opaque.

And this works:

(define-values (numeric-tree? numeric-object?)
  (U* numeric-tree-er numeric-object-er))

And now:

> (numeric-tree? 1)
#f
> (numeric-object? 1)
#t
> (numeric-tree? '(1 . 2))
#t
> (numeric-tree? '(1 2 . (3 4)))
#f

Wrapping U* in a macro

The same problem as previously happens when we raise the inner call to U* with the same result: we need to use U*/ao. In addition the macro becomes significantly more hairy and I’m moderately surprised that I got it right so easily. It’s not conceptually hard: it’s just not obvious to me that the pattern-matching works.

(define-syntax (with-recursive-bindings stx)
  (syntax-parse stx
    [(_ ((name:id value:expr) ...) form ...+)
     #:fail-when (check-duplicate-identifier (syntax->list #'(name ...)))
     "duplicate variable name"
     (with-syntax ([(argname ...) (generate-temporaries #'(name ...))])
       #'(let-values
             ([(name ...) (U* (λ (argname ...)
                                (let-values ([(name ...)
                                              (U*/ao argname ...)])
                                  value)) ...)])
           form ...))]))

And now, in a shower of sparks, we can write:

(with-recursive-bindings ((numeric-tree?
                           (λ (o)
                             (and (cons? o)
                                  (numeric-object? (car o))
                                  (numeric-object? (cdr o)))))
                          (numeric-object?
                           (λ (o)
                             (cond [(number? o) #t]
                                   [(cons? o) (numeric-tree? o)]
                                   [else #f]))))
  (numeric-tree? '(1 2 3 (4 (5 . 6) . 7) . 8)))

and get #t.

As I said, I am sure there are well-known better ways to do this, but I thought this was interesting enough not to lose. This originated as an answer to this Stack Overflow question.

An attempt to describe three well-known function calling conventions in terms of bindings.