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. Dave 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/ _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
