Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Новости языка 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 байт в списке, т.к. не нужен \0)
- выгоднее хранить в списке!
- + список выделяет и освобождает память за 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)=1A4C ("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
- - комментарии, ввод слова должен поддерживать пробелы в
- комментариях
- - эскейп-коды в строковых константах
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement