Привет,

Тут так получилось, что пишем второе поколение языка для управления маленькими устройствами — соответственно, есть шанс что-нибудь сделать по-человечески. VM — обычная форт-vm, два стека, немного кучи. Пока сделал управление памятью и mark'n'sweep gc. Кучи мало — 2K — 8K, выделяется чанками, чанк — это последовательность байт с 2-байтовым заголовком и признаком того, занят он или нет (ну еще два бита для GC который работает по алгоритму Дийкстры).

Основной структурой данных видится список, причем, сохраненный в виде вектора — оверхед от нормальных списков тут слишком велик). Списки (и вообще любые данные) — хочется сделать иммутабельными; но вот терзают смутные сомнения — не обернется ли это очень большим количеством копирований и частыми запусками GC (а он очень недешев, т.к. консервативный — т.к. нет способа отличить указатель от произвольного слова)?

Для примера — операция head: Кладет на стек голову списка, при этом мы получаем (1) — слово на стеке, (2) исходный список (3) новый список, который получается копированием старого. Итого, для тупой реализации и типичного алгоритма разбора, скажем, 80-байтной строки NMEA нам потребуется что-то 3400 байт и 80 операций копирования памяти, почти вся (или вся) наша память.

Вопрос — как это делается (как бы вы сделали) вообще в языках с иммутабельными данными? Например, для операций "голова" и "хвост". Пока то, что я вижу — это считать списком пару (размер, указатель на данные) — тогда head создает новую структуру, где (размер, начало) == (размер_исходный-1, начало+1). Тогда при таком-же разборе мы потратим где-то 480 байт, что как-то где-то сносно, но при этом заголовок каждого списка получается 6 байт вместо исходных двух.

Второй вопрос — какой бы выбрать базис операций для работы с памятью. Видится два подхода — первый ограничиться исключительно операциями над списками head, tail, (, ++, nth, length (что еще) — этого же набора вроде хватает и для организации туплов (ну может добавить операцию произвольного чтения — байта или слова по заданному смещению) — или взять стандартный набор — @ (at), !(to) — произвольное чтение/запись по смещению (чего не хочется, если честно — все равно всю работу со списками выносить в нативный код, так что зачем давать скрипту возможность нагадить в кучу и сломать управление памятью)

Кстати, заодно принимаются мысли по другой организации хипа — если есть мысли, как сделать распределение памяти с меньшим оверхедом. И по gc тоже принимаются. Предпосылки — машина 16-битная, физически RAM — 2K — 10K (не менее 1K уйдет на системные нужды — стеки, io буферы, структуры ОС);