Lambda the Ultimate

Has there been a paper describing optimizations to arithmetic for tagged pointer representations? For instance, stealing 1-bit to distinguish pointers and integers, and using 0 as the tag value for integers, we don't need to perform any shifting for integer addition in order to normalize the integer back to its tagged representation:

-- integer i is represented as a word shifted by 1 bit:
-- word = tag(int)
tag(int) = int << 2
         = word * 2

-- int = untag(word)
untag(word) = word >> 2
            = word / 2

-- no shift needed; subtraction the same
addition = int0 + int1
         = tag( untag(word0) + untag(word0) )
         = tag( (word0 / 2) + (word1 / 2) )
         = tag( (word0 + word1) / 2)
         = 2 * (word0 + word1) / 2
         = word0 + word1

-- one right shift needed to normalize
multiplication = int0 * int1
               = tag( untag(word0) * untag(word1) )
               = tag( (word0 / 2) * (word1 / 2) )
               = tag( word0 * word1 / 4 )
               = 2 * word0 * word1 / 4
               = word0 * word1 / 2

-- one left shift needed to normalize
division = int0 / int1
         = tag( untag(word0) / untag(word1) )
         = tag( (word0 / 2) / (word1 / 2) )
         = tag(word0 / word1)
         = 2 * (word0 / word1)
etc.

Obviously these can be derived from basic arithmetic, but it's a bit tedious, so I was wondering if there was a reference describing a full set of such identities, or any more sophisticated optimizations. Perhaps a tag calculus of sorts.

Of course, care must be taken to handle overflow on the word when adding and multiplying, but I think "branch on overflow" is a fairly common instruction, and would provide for an efficient implementation to tweak the result.

Ran across a short weblog entry on Leonhard Euler, the father of functions and initiator of much in the way of number theory. The mention of Project Euler caught my eye, as I rather like projects that involve multiple PLs attacking the same sets of problems.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Project Euler has been around for almost as long as LtU but this is the first I'd heard of it. I find the questions and the competitive gaming aspect to be interesting, though I have a long way to go (level 2 out 5). Not sure there is a direct tie into PLs, but since I'm using it to learn more math and investigate the breaking points and elegance of PLs... and anything involving multiple PLs in competition and mathematics can't be too far removed... and since I haven't posted a story to LtU in a while and this happens to be my current interest... well, that will have to suffice. I'll have to admit though that many of the solutions I looked at are either too rushed (brute force), too cumbersome (indexes flying everywhere) or too terse. But that's true of most code that I run across (including my own). Still hoping for a PL that has that just right aspect - though I'm leaning to Oz these days.

_{(For those of us that are looking for walk-through/cheat guides, the Haskell wiki has the code to the first 200 problems, and I've put my Oz code for the first 50 up on the CTM wiki).}