ACNews #71 03 августа 2018

Новости языка Listh - плюсы и минусы хранения в списках против хранения в куче.

                      Новости языка Listh
                        by Alone Coder

Я долго взвешивал, нужны ли с самого начала дополнительные
структуры данных, кроме списков, которые казались
расточительными по памяти. Решил записать плююсы и минусы
хранения в списках против хранения в куче:

- запись в куче можно индексировать (будет массив), а список
нельзя.
? first fit куча (очень медленная) заполняется на 85%, то есть
для строк она выгоднее в 3.4 раза (но зато мы можем в списке
хранить 16-битные строки), а для программ в 1.7 раза, чем
список. buddy куча (среднемедленная) заполняется на 75%, то есть
для строк она выгоднее в 3 раза (но зато мы можем в списке
хранить 16-битные строки), а для программ в 1.5 раза, чем
список. но эти числа для блоков 10-100 байт, а куча теряет много
памяти на маленьких записях (ей нужно лишних 8 байт на запись).
4 элемента подряд (16 байт в куче, 16 байт в списке) или строку
из 3 букв (12 байт в куче, 12 байт в списке, т.к. не нужен )
выгоднее хранить в списке!
+ список выделяет и освобождает память за O(1), практически
мгновенно.
+ список не имеет ограничений на длину выделяемого фрагмента, он
выделится всегда, если есть свободная память. можно даже 100
килобайт одним списком.
+ реализация списка на куче даст проигрыш в 3 раза (12 байт на
элемент против 4).
+ реализация бинарного дерева на куче: 12 байт на узел
(используя NIL), на списке: 4 байта на узел (используя NIL) -
считаем, что листы хранятся отдельно, на них только указываем,
иначе зависит от размера листа.
+ список можно увеличивать и уменьшать, а элемент кучи нельзя.

То есть не всё так плохо, единственная реальная проблема - как
реализовать массив на списках.

а) перебором списка - O(i). 
б) сделать поверх списка список чётных элементов, поверх того 
тоже и т.д. - O(log(n)). 
в) добавить выделяемые блоки по 256 байт в качестве элементов 
списка? (хранить указатели на них и иметь операции 
индексирования.) память для списков можно сделать на этих 
блоках, их даже можно освобождать обратно (если иметь счётчик в 
каждом). для этого список свободных можно сделать двусвязным, 
тогда можно будет выключать пустые элементы блока и отдать 256 
байт. 
г) добавить ещё кучу? как делить память между списком и кучей? 
д) просто работать в памяти через POKE и PEEK. 

Я выбрал последний вариант, но заложил в будущем возможность
использовать 256-байтные блоки (для этого понадобилось сделать
список свободных элементов двусвязным, чтобы можно было
ликвидировать элементы в 256-байтном блоке, когда тот
освободится).

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

- интерпретатор
- арифметика (T, NIL, +, -...)
- работа со списками (VALUE, NEXT, FORM...)
- работа со стеком (DUP, DUP2(повторить 2 элемента), DROP, SWAP,
OVER(повторить 2-й элемент), ROT(вынуть 3-й элемент)...)
- работа с памятью (NEW, DEL...)
- работа с переменными (NEWVAR, FINDVAR, =>, DEF, DEFUN,
EVAL...)
- работа с терминалом (ttypeek, ttyget (изначально работает из
памяти, потом сработает патч, чтобы переключился на клавиатуру),
ttyput...)
- расшифровка и исполнение лиспотекста из терминала.

Остальное можно написать на самом Listh или постепенно добавлять
ассемблерные обработчики.
Можно редактор (расшифровку и исполнение команд) написать на
самом Listh. Сначала я так и сделал, планируя набрать эти
Listh-функции прямо в ассемблерном тексте (в виде
последовательности dw:dw), но для этого нужно сразу реализовать
структуры программы (IF, WHILE...). Поэтому я просто вручную
скомпилировал нужные процедуры на ассемблер, а по мере
надобности писал новые прямо на ассемблере.

Все лиспосписки (введённая команда, VarList, Prog) сделаны
выводимыми. Для этого у них в начале лежит адрес LispList, в
середине указатели на термы содержимого, а в конце указатель на
терм EndLisp. Термы - тоже списки, в первом элементе у них адрес
обработчика, во втором значение, а далее имя по одному символу
(это относится и к числам - ведь их можно записать по-разному, а
показывать надо именно в том виде, как ввели). Функция печати
лиспосписков ttyputlist рекурсивно выводит все термы, у которых
в первом элементе лежит адрес LispList (он не выводится, как и
последний элемент). Эта функция может печатать и отдельный терм
(у него первый элемент отличается от LispList). Голые списки
чисел эта функция печатать не может, можно написать отдельную
функцию для этого.

В процессе реализации пройдены следующие майлстоуны:

+ работа с памятью (NEW, DEL), проверяем трассировкой
+ печать числа ttyputnum, проверяем вызовом из асма
+ печать строки ttyputstr, проверяем вызовом из асма
+ чтение вложенного лиспосписка (из известных элементов),
проверяем работу strcmp асмовставками, проверяем, как легло в
память (READTERM (READTERM) READTERM)
+ печать вложенного лиспосписка, проверяем, что он соответствует
введённому (READTERM (VarList () readlist) READTERM)
+ интерпретация лиспосписка (VarList ttyputlist) - печать списка
переменных, проверяем его
+ интерпретация лиспосписка (T T + T ttyputnum ttyputnum)
+ интерпретация вложенного лиспосписка (T - (T + T) DUP
ttyputnum NOT ttyputnum)
+ чтение чисел (с автоматическим созданием константы, если такой
ещё нет), проверяем на (13 + 13 ttyputnum VarList ttyputlist)
+ чтение строк (с автоматическим созданием константы, если такой
ещё нет), проверяем на ("abc" ttyputstr VarList ttyputlist)
+ показ свободной памяти (FreeMem ttyputnum)=1AЧC ("abc"
ttyputstr VarList ttyputlist FreeMem ttyputnum)=1984
+ чистить найденное слово или ошибочное слово при вводе (чтобы
не забивать память) (FreeMem ttyputnum)=1A44 ("abc" ttyputstr
VarList ttyputlist FreeMem ttyputnum)=19E4
+ команда определения переменной (с занесением в исходник, в
скобках начальное значение) (DEF "newvar" (15) VarList
ttyputlist) или (DEF "newvar" (15 + 11) VarList ttyputlist)
+ печать исходника (список введённых команд-определений - в
порядке их ввода) (DEF "newvar" (15) VarList ttyputlist Prog
ttyputlist)
+ выполнение нескольких введённых строк (DEF "newvar" (15)
VarList ttyputlist Prog ttyputlist FreeMem ttyputnum)(newvar
ttyputnum)
+ команда определения функции (с занесением в исходник) (DEF
"newvar" (15) DEFUN "newfun" (VarList ttyputlist Prog
ttyputlist) FreeMem ttyputnum)(newvar ttyputnum newfun)
+ команда QUOTE (QUOTE (VarList ttyputlist Prog ttyputlist) DUP
ttyputlist EVAL FreeMem ttyputnum)
+ при переопределении функции класть ссылку на неё не в начало,
а в конец исходника, чтобы было всегда позже объявления
используемых в ней переменных
+ команда копирования списка (QUOTE (VarList ttyputlist) FreeMem
ttyputnum copylist FreeMem ttyputnum DUP ttyputlist dellist
FreeMem ttyputnum)
+ команда удаления дерева (т.е. LispList со входящими LispList):
(QUOTE (VarList (13) ttyputlist) FreeMem ttyputnum DUP
ttyputlist deltree FreeMem ttyputnum)
+ команда копирования дерева (т.е. LispList со входящими
LispList): (QUOTE (VarList (13) ttyputlist) FreeMem ttyputnum
copytree FreeMem ttyputnum DUP ttyputlist deltree FreeMem
ttyputnum)
+ ручной ввод (только в скобках, после закрывающей скобки ввести
Enter), с эхом, при вводе неизвестного идентификатора сразу
пишется ошибка, а в список попадает NIL
+ печать свободной памяти до ввода, после ввода и после
исполнения команды
+ чтение символов (с автоматическим созданием константы, если
такой ещё нет, пробел или кавычку нельзя), проверяем на ('A'
ttyputnum VarList ttyputlist)
+ отрицательные числовые константы
+ очистка введённой команды (предварительно все новые слова из
введённой команды копируются в VarList, а при DEF/DEFUN
определения копируются в Prog)

В планах:

- команда удаления переменной/константы/функции из Prog и
VarList (с проверкой использования?)
- команда вывода исходника в файл (без внешних скобок, так что
получится набор сравнительно коротких команд)
- команда ввода исходников из файла
- команда THEN (...) ELSE (...)
- команда REPEAT (...) //UNTIL T
- комментарии, ввод слова должен поддерживать пробелы в
комментариях
- эскейп-коды в строковых константах