[Agda] Erasable vs. irrelevant, and red black trees again

Alan Jeffrey ajeffrey at bell-labs.com
Fri Jan 20 16:14:52 CET 2012


On 01/19/2012 10:52 PM, jleivent at comcast.net wrote:
> Would the black-level terms have been erasable by the compiler had I used normal naturals?

This depends on the back end, as Agda's IL doesn't handle much in the 
way of optimization.

The JS back end does some very simplistic analysis of "singleton types", 
types with at most one closed inhabitant. These are zero-field records, 
zero-constructor datatypes, datatypes with one zero-argument 
constructor, functions to singleton types, and Set. Many expressions of 
singleton type are erased, and replaced by the singleton.

So in this case, all the uses of naturals in red-black tree types would 
be erased, but rather annoyingly there's no dead-code analysis, so the 
natural expressions would still be there. Moreover, I'd expect that in 
most cases the dead-code analysis would have to be a whole-program 
analysis, so can't be performed by the Agda compiler (it would need to 
be done by the JS JIT compiler).

A.


More information about the Agda mailing list