User guide

10.3. COMPACTION OF SIAL 185
10.3 Compaction of Sial
In order to transmit program to a device such as a mobile phone or s pac e probe over a
slow connection it is useful to have a compact representation of the code. Sial is b ot h
target machine independent and can b e compacted with ease. This section gives a brief
overview of an experimental compaction technique that seems to performs well.
Since the types of operands and their number depend only on the Sial operator,
an Sial stream can be split into several streams of which the main one is the stream
of Sial operators. Others are streams holding global variable numbers, local variable
offsets, program label numbers, data l abels, i nteger constants, character codes and a
some others. These streams can be separately compressed taking advantage of the
special properties of each. Some ideas are given bel ow.
Local variable offsets have a very skew distribution and so are susceptible to Huff-
man (or possibly arithmeti c ) coding after some preprocessing to deal with large values
and the implementation of a mechanism to take advantage of the observation that, if
an offset is used onc e , the same offset i s likely to be used agai n in the near future. This
might suggest the use of move-to-front buffering.
Program labels h ave t he property t hat, in any section, they are each only set
once using a LAB or ENTRY statement. If they are systematically renumbered so that
successive label setting statements take successive label numbe r s, there is no need for
these statements to take a label argument. The remaining labels in the stream are
typically nearly monotonic the compaction algorithm can take advantage of this.
The operation code str e am often contains repeated patterns that are susceptible to
the conventional techniques used to compre ss text, and the same applies to the stream
of characters. It might be worth separating out the integers re pr e se nting the character
string lengths from other integers and place them either in a stream of their own or
insert them into the stream of characters.
Some preliminary experiments on Sial compression can be found in the directory
bcplprogs/sial in th e standard BCPL distribution.