A thought just occurred to me: can static analysis be used to predict when
lists are or aren't cdr coded and eliminate the expensive instruction
sequences to support run-time decisions?
Suppose one adopted an SBA framework and had two types NON-CDR-CODED-PAIR and
CDR-CODED-PAIR. And suppose all of the primitives like CAR, CDR, CONS, etc.
could take both types as arguments. And suppose that some primitives, like
CONS, returned NON-CDR-CODED-PAIRs, and others, like MAP, returned
CDR-CODED-PAIRS. And suppose that you had the following inference rule:
(SET-CDR! x:a y:b)
CDR-CODED-PAIR(c, d) in a
-----------------------------
NON-CDR-CODED-PAIR(c, b) in a
for obvious reasons. And suppose that you promoted all union types that
contained both CDR-CODED-PAIRs and NON-CDR-CODED-PAIRs to contain only
CDR-CODED-PAIRs. Then you would have *no* run-time decisions to make about
cdr coding and could in-line appropriate implementations of primitives like
CAR and CDR based upon the known argument type.
This is just a thought. I haven't fully thought it through yet. Has anybody
done anything like this?
Jeff (home page http://www.cs.toronto.edu/~qobi)
From: Joe Keane
Subject: Re: static analysis and CDR coding?
Date:
Message-ID: <jgkDHnvsD.Aor@netcom.com>
(defun icky-cons (&rest l) (replacd l (cadr l)))
--
Joe Keane, amateur mathematician