@node Дешёвые пары
@subsection Дешёвые пары
Однако существует ещё одна проблема с которой придётся столкнуться.
Большинство куч в Скимах содержат пар больше чем других типов объектов.
Джонатан Рис однажды сказал, что куча состоит из пар на 45% в его реализации
Скимы, Scheme 48.Однако наше представление требует три @code{SCM} слова на одну пару ---
одно под слово, и ещё два под @sc{car} и @sc{cdr}. А есть ли какой нибудь способ представить
пару используя только два слова?
Давайте точнее определим чего мы хотим. Допустим, мы утверждаем следущее:
@itemize @bullet
@item
Если последние три бита значения @code{SCM} представляют собой нули -- @code{#b000}, тогда
это указатель, как всё и было ранее.
@item
Если последние три бита таковы: @code{#b001}, то верхние биты представляют целое число.
Это немного более строго чем раньше.
@item
Если последние три бита это @code{#b010}, то его значение, за
исключением трёх последних битов, содержит адрес пары.
@end itemize
Посмотрим на новый С код:
@example
enum type @{ string, vector, ... @};
typedef struct value *SCM;
struct value @{
enum type type;
union @{
struct @{ int length; char *elts; @} string;
struct @{ int length; SCM *elts; @} vector;
...
@} value;
@};
struct pair @{
SCM car, cdr;
@};
#define POINTER_P(x) (((int) (x) & 7) == 0)
#define INTEGER_P(x) (((int) (x) & 7) == 1)
#define GET_INTEGER(x) ((int) (x) >> 3)
#define MAKE_INTEGER(x) ((SCM) (((x) << 3) | 1))