Too much exercise

I've spent the past few days thinking about how to answer the exercises in my previous post. I think I finally came up with a good analogy. (Bear with me.)

These days, it is not uncommon to run programs on virtual hardware. Programs like VMWare or Virtual Box provide nearly undetectable emulation of an x86 PC. In fact, modern x86 CPUs actually emulate the x86 instruction set through hardware accelerated interpretation or jit compiling. Although it can be tricky to emulate the entire body of computer hardware and peripherals that might go into a PC, it is straightforward to emulate the bare bones PC hardware with close to perfect fidelity, even down to the CPUID.

So could one write a portable x86 program — one that can run without modification on a real PC with real hardware or on a real PC with virtual hardware (like a Transmeta CPU) or on completely virtual hardware — that can reliably and predictably detect whether it is being “run directly” or “just being emulated”? The entire raison d'être of virtualization rests on the fact that, given enough effort, you can fool all of the programs all of the time. (Bugs notwithstanding.)

So let's reconsider Exercise 1:  Write a program that returns 1 if run on any tail-recursive implementation of a language, but returns 0 if run on any non tail-recursive implementation of that same language.

Restate this as: Write a portable x86 program — one that can run without modification on a real PC with real hardware or on a real PC with virtual hardware (like a Transmeta CPU) or on completely virtual hardware — that can NOT ONLY reliably and predictably detect whether it is being “run directly” or “just being emulated”, BUT FURTHERMORE can reliably and predictably detect whether the underlying execution mechanism is “recursive” or “iterative”?

I assert that this question is barely worth thinking about (unless you work at VMWare) and that the answer could hardly be anything but “No.”

Exercise 1a (extra credit):  Write a program that crashes or doesn't return if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.

If a program cannot detect whether or not it is being emulated, perhaps it can “half” detect. If it could reliably crash the emulator, then you could at least demonstrate that some sort of emulation is being done even if you couldn't perform a conditional branch in this situation. Suppose the program were being emulated. Suppose further that the emulator is recursive (for whatever reason). One could, in theory, crash the emulator via a stack overflow or out-of-memory error (maybe that emulator is recursive, but it uses heap-allocated stack frames). Alas, this isn't what we asked for. We are looking for a program that can reliably crash an iterative emulator. We're out of luck.

Exercise 1b, essay (extra extra credit): Discuss the implications of your answers to exercises 1 and 1a to the semantics of the programs (woah, my apologies, programs don't have semantics, languages do. Pretend I wrote “languages”). In particular, briefly outline what changes to the various semantic models — denotational, operational, and/or axiomatic — take place upon introducing tail recursion.

The implication is this: the semantics of a programming language are logically independent of the implementation of the language. (If they were not, virtual machines would be impossible.)

Exercise 2: What trivial change can Louis make to his code for smaller that will disable tail recursion?

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (let ((answer
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate))))
        answer)))

There is no need for a flag to enable or disable tail recursion. Tail recursion only “works” when the caller does nothing to the return value but immediately return it itself. A LET expression is syntactic sugar:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      ((lambda (answer) answer)
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate)))))

You can now see that the value of the conditional expression is not immediately returned, but rather passed as an argument to a (rather trivial) lambda expression. (Yes, a smart compiler could notice that the lambda expression is simply the identity function in this case. If that is a problem, simply make sure that the function you use to disable the tail recursion is late-bound so that the compiler cannot prove that it can be elided.)

Exercise 3: What trivial change can Louis make to his code for smaller that will enable tail recursion on all but the initial call to smaller?

(define (smallest list predicate)
  ;; Returns the smallest element of list.

  (define (smallest list predicate)
    (if (null? list)
        #f
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate))))
  (let ((answer (smallest list predicate)))
    answer))

Again, we don't need special flags to have fine control over tail recursion.

Exercise 4: Implement disable-tail-recursion as a macro.

;;; For example:
(define-syntax disable-tail-recursion
  (syntax-rules ()
    ((disable-tail-recursion form)
     (let ((answer form)) answer))))

You could be more sophisticated and invoke a late-bound function, but this is, frankly, overkill. You hardly need macros, special forms, flags, decorations, etc. to control tail recursion. This is especially true if all you want is a pretty stack trace for debugging. Tail recursion is as easy to turn on and off as a printf.