gistfile1.txt

Ребята, тут такая история.
У меня улучшился (я на это надеюсь) io.
И вот в каком смысле.

Из соображений производительности внутреннее представление конструкторов было выбрано таким:
+--------+------+------+-----+------+
| header | arg1 | arg2 | ... | argN |
+--------+------+------+-----+------+

где header имеет вид
+---+-----+-------+
| N | tag | color |
+---+-----+-------+
64  18    2       0 (bit)

Все поля ячейки, таким образом, занимают одно машинное слово.

Тонкость тут в поле tag. На него выделено 16 бит, можно больше, потому что на N (размер объекта)
вряд ли нужно больше четырёх бит. Да и цвет можно урезать до одного бита. То есть, на тег можно было,
не увеличивая размер заголовка до двух машинных слов, выделить до 59 бит (на 64-битной платформе).
Так или иначе, полноценный указатель на строку с именем конструктора туда не влезет, а тег должен
делать именно это - однозначно указывать на то, какой именно конструктор вся ячейка представляет:
S, Z, Cons, Nil или какой ещё. Использовать указатели на строки нецелесообразно ещё и потому, что со
строками для диспетчеризации вызовов g-функций пришлось бы использовать последовательность
(или бинарное дерево) строковых сравнений, или поиск в хеш-таблице или что-нибудь ещё столь же
небыстрое. Тег же - просто номер, который присвоен некоторому конструктору, который был известен
компилятору во время компиляции. Причём номера присваиваются конструкторам, попадающимся в программе
последовательно, 0, 1, 2, ... Потому для диспетчеризации g-вызовов можно использовать обычный switch,
который компилятором C преобразуется в косвенный переход по табличке указателей, что происходит
довольно быстро.

Ключевой момент здесь в том, что при компиляции программы теги можно назначить только тем конструкторам,
которые в неё хоть как-нибудь входят. Потому в текущей реализации ни одна из следующих программ не будет
работать, как хотелось бы.

Примеры.

#1
--------------------
.
x
--------------------

Хотелось бы, чтобы такая программа запрашивала x ("x = "), считывала любое валидное значение
(например, Cons(CH, Cons(Ce, Cons(Cl, Cons(Cl, Cons(Co, Nil)))))) и выводила его же на печать.
На деле на любой ввод программа не уйдёт дальше парсера значений, потому что тот ругнётся на
то, что вы пытаетесь использовать неизвестное ему имя конструктора. Потому что список известных
такой программе конструкторов, разумеется, пуст.

#2
--------------------
decrement(S(x)) = x
.
decrement(x)
--------------------

Было бы здорово, если бы работа такой программы выглядела так:
x = S(Z)
Z
или даже так:
x = Z
SLL Fatal Error: Inexhaustive pattern matching

В действительности, ввиду той же проблемы, вы увидите только ругательство на непонятный конструктор Z.


#3
------------------------------
len(Nil) = Z
len(Cons(hd, tl)) = S(len(tl))
.
len(list)
------------------------------

Видимо, вы уже понимаете, чего я хочу:
list = Cons(CH, Cons(Ce, Cons(Cl, Cons(Cl, Cons(Co, Nil))))))
S(S(S(S(S(Z)))))

Если первый пример может показаться ненужным или вырожденным, второй - неполным ("сами виноваты -
определяйте функции нормально"), то пример со списком, на мой взгляд, наиболее показательный.
Действительно, длина списка имеет смысл вне зависимости от того, что именно он содержит. Если хотите,
это элементарный полиморфизм операций, без которого довольно грустно жить. Причина, по которой
в текущей реализации это не будет работать так в том, что компилятор в список известных конструкторов
поместит S, Z, Cons и Nil, но не CH, Ce, ...


Проблема решена в текущей ветке io и все три примера работают в ней так, как хотелось бы.


Решение целиком локализовано в пределах кода, ответственного за ввод-вывод, потому и лежит оно в ветке
io. Действительно, без ввода-вывода её не может быть. Потому что если вы задаёте начальные данные
прямо в программе, все используемые в нём конструкторы становятся видны уже на стадии компиляции.
Отсюда несколько наблюдений:
1. Иметь дело с неизвестными на стадии компиляции (далее - "внешними") именами конструкторов приходится
только парсеру и принтеру значений в составе рантайма.
2. Если по одному из таких значений во время выполнения осуществляется паттерн-матчинг,
то это однозначно ошибка времени выполнения ("Inexhaustive pattern matching"), так как раз конструктор
внешний, он не появляется ни в одном паттерне в программе, тем более в паттерне той функции, которая с
ним столкнулась.
3. С точки зрения сборки мусора и управления памятью вообще ячейка, "подписанная" неведомым конструктором
ничем не отличается от любой другой.

Потому парсер значений теперь поступает так: встретив имя конструктора, не входящее в список известных,
 он сохраняет его где-то, в качестве тега пишет константу SllExternalCtrId (= 0xFFFF), обеспечивая
"Inexhaustive pattern matching" при попытке сматчить такой конструктор, аллоцирует такой объект в
куче для объектов размером на единицу больше, чем у него фактически есть аргументов (но в заголовок
 записывает правильное, неувеличенное значение), и пишет указатель на сохранённое имя конструктора в
последнее слово объекта:
+--------+------+------+-----+------+------------------+
| header | arg1 | arg2 | ... | argN | ctr name pointer |
+--------+------+------+-----+------+------------------+

Стадия sweep сборки мусора в заголовке смотрит только на цвет, ей всё равно, что записано в полях
объекта, всё равно, что объект размера N лежит в куче для объектов размера N + 1. Стадия mark смотрит
на цвет и размер и обоходит поля с arg1 по argN и тоже не замечает подвоха.

Принтер значений, обнаружив в качестве тега SllExternalCtrId, печатает строку, доступную по ctr name
pointer. В противном случае использует тег как индекс в списке (массиве) известных конструкторов и
оттуда берёт подходящее имя, как и раньше.


Остаётся придумать, а куда и как, собственно, сохранять внешние имена конструкторов.
Под каждое такое имя аллоцировать память не очень хорошо. Представьте, что в примере #3 на вход подаётся
очень длинный список, все элементы которого - NullaryConstructorWithVeryLongName. При таком подходе
такая длинная строка будет раскопирована по памяти столько раз, сколько она встречается во входе и
вообще основной расход памяти придётся именно на это. А ведь ясно, что её можно было зааллоцировать 
только раз и потом во все ячейки списка помещать на неё указатель.

Но чтобы понять, что строка уже была зааллоцирована, нужен ассоциативный массив, реализующий
АТД "множество". В качестве такого, так как мы транслируем программу на C и рантайм до сих пор был на
чистом C, была реализована простенькая хеш-таблица с открытым ключом, расширяющаяся (мультипликативно)
при необходимости.


Вот, собтвенно, это и надо заревьюить: https://github.com/ramntry/SLL/compare/io

Если есть вопросы - задавайте.