compact code representation

Alaric B. Williams alaric@abwillms.demon.co.uk
Fri, 2 May 1997 18:13:06 +0000


On 30 Apr 97 at 23:43, lispos@math.gatech.edu wrote:

> NB: Could people on the list please use more meaningful subject lines,
> instead of propagating the same meaningless line when the subject
> has drifted far away the original message? Thanks.

(hangs head in guilt)
 
> >>: hbaker
> >: ABW
 
> > On 29 Apr 97 at 7:48, lispos@math.gatech.edu wrote:
> Alaric, will you correct your quoting software?

It's not cooperating. Sorry... the fields I get to put in that line
are sender's full name, sender's email address, sender's first name,
date, time, rate of inflation... :-(
 
> > My favourite approach is just to define a representation for Lisp lists
> > on disk in binary format. "source code" in ASCII form is just one way
> > of doing this. Another is to have a symbol table followed by a tagged
> > data dump,

> Yeah. That's what I've been talking about for some time, ain't it?

Yeah, WE have :-)

> Oh no! We've been talking about compact code,
> and now you're having 32-bit lengths???

Hey, whatever. Use base 128, then - top bit set means it's
the last byte of the number.

> Many LISP constructors have fixed arity; most lists are small;
> huffman-like encoding of list length may be used;
> or even a terminator-based list encoding,
> which allows for a more regular pattern if we want to further compress
> the already compact code through GZIP...

Although my experiments used GZIP, it would be far better to use properly
isolated typestreams for the Huffman stage, then followed by a symbol-level
sliding window, I think.

> > Thus, it is the full s-expr, not some compiled form, but it's compact
> > and fast to load.
> Yeah.

I guess that compression should be chosen by the system invisibly when
storing stuff locally, with an override to maximum compression when disk
space gets tight. The automatic compression choice is made for the
best tradeoff between disk read rate and CPU decompression rate :-)
 
> == Fare' -- rideau@ens.fr -- Franc,ois-Rene' Rideau -- DDa(.ng-Vu~ Ba^n ==

ABW 
--
Alaric B. Williams (alaric@abwillms.demon.co.uk)

   ---<## OpenDOS FAQ ##>---

Plain HTML: http://www.delorie.com/opendos/faq/
            http://www.deltasoft.com/faq.html

Fancy HTML: http://www.deltasoft.com/faq0000.html