[racket] a little macro exercise

From: David Herman (dherman at ccs.neu.edu)
Date: Sat Oct 9 22:30:19 EDT 2010

I think you may be missing a crucial point: once control hits the first passing test, there are no more conditionals; every right-hand side is compiled as a procedure that unconditionally tail-calls the next right-hand side. IINM, this is pretty much the same way `switch' is typically compiled: each case is treated as a basic block boundary, and compilers often connect up basic blocks with explicit jumps in the IR.

Now, in a Scheme compiler, it's not uncommon to do a basic analysis to determine when a named procedure is a "known local," i.e., a statically-known procedure definition whose value doesn't escape. This is the case here: each of the tempX procedures is a known local, so the tail calls between subsequent blocks (e.g., temp4 -> temp5 and temp5 -> temp7 in your first example) ought to be compilable to unconditional jumps. At which point, you're in much the same place you'd be with the IR for a `switch' in a traditional C compiler.


On Oct 9, 2010, at 5:57 PM, Neil Van Dyke wrote:

> David Herman wrote at 10/09/2010 07:46 PM:
>> I thought about the "am I falling through?" approach you've been taking, but the problem is that it keeps having to recompute the same test. In C-like languages, one of the benefits of `switch' [1] is that fall-through is expected to either be a literal "execute the next instruction in the PC" or at least a jump to a fixed address. So I prefer an approach that sets up a basic-block-like structure, like so:
> I like this way of thinking.
> Here's an expansion of Shriram's example:
> (define (cas1 v)
>   (let ([disc-v v])
>     (let/ec
>         k
>       (syntax-parameterize
>        ([break (syntax-rules () [(_ v) (k v)])])
>        (define (temp2) (case disc-v [(1) (temp4)] [else (temp3)]))
>        (define (temp3) (case disc-v [(2) (temp5)] [else (temp6)]))
>        (define (temp4) (display "1") (temp5))
>        (define (temp5) (display "2") (break 2) (temp7))
>        (define (temp6) (case disc-v [(3) (temp7)]))
>        (define (temp7) 3)
>        (temp2)))))
> That seems a little unfamiliar to me because of the linear search with multiple tests.  I instead used a single "case", on the perhaps naive assumption that that's easiest for a compiler to optimize:
> (define (cas1 v)
>   (let ((temp3 (lambda () 3)))
>     (let ((temp2 (lambda () (display "2") 2)))
>       (let ((temp1 (lambda () (display "1") (temp2))))
>         (case v
>           ((1) (temp1))
>           ((2) (temp2))
>           ((3) (temp3)))))))
> Couldn't a compiler could optimize a "case" at least as well as any syntax transformer I wrote, unless I had special knowledge about the actual runtime inputs that a static optimizer doesn't have (which I don't)?  (Examples: binary search, jump tables, branching on tags/types, dynamic optimizations.)
> I was guessing then that, if I let the compiler do what it wants with a single "case" and then went with tail calls to chain fallthrough between thunks, it doesn't get much better than that for a compiler.
> But I'm just making that up, since I don't know how smart the compiler, and modern CPUs and JITs mean that we can't just count instructions in disassembly dumps to have an easy idea what'll go on.
> -- 
> http://www.neilvandyke.org/

Posted on the users mailing list.