Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

набросок, ч. 1

(может заинтересовать только программистов, и то мало кого)

Я хочу написать небольшой игрушечный интерпретатор Схемы на C. Но уже месяц прокрастинирую, не написав не строчки. Буду мотивировать себя описанием процесса здесь. Объяснять самому себе, почему я хочу это сделать так, а не иначе, и писать код одновременно с этим. В несколько заходов с продолжениями. Например, в восемь припадков.

FAQs:
- зачем?
- У меня чешется Гондурас. Я давно не писал ничего для души. Хочу увидеть, что будет тривиально, а что не очень. Практической пользы никакой нет.

- почему Scheme?
- простой компактный язык, но с closures, lexical scope & garbage collection. Очень мало синтаксиса, не надо ебаться с парсингом. Суть языка представляю, но никогда на нем не писал; любопытно, как это 'представляю' пройдет проверку опытом.

- почему на C? почему интерпретатор?
- Так захотелось. Любопытно сделать это относительно быстрым, сохраняя простоту кода. Давно не писал на чистом C.

- такие уже есть?
- Да, куча, и на разных языках, и на C тоже. Я видел, внимательно исходники не читал, и сейчас специально не буду. Не надо мне присылать на них ссылки, писать, какая это идиотская затея, и всячески демонстрировать размер собственного члена. Не-пенисомерным комментариям всегда рад.

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

------------------приступаем к делу--------------------------------

Код стараюсь писать одновременно с записью.

Спецификация компактного стандарта Схемы лежит на http://www.schemers.org/Documents/Standards/R5RS/.

Поскольку я пишу не полновесную схему, назову ее "набросок", sketch.

Основной принцип: как можно более простой код. На втором месте, но намного
менее важно: performance.

------------------припадок первый----------------------------------

------------------tutorial----------------------------------------

Схема - очень простой язык. Основная единица работы - значение (value), значение
может передаваться в функцию, возвращаться из функции, впихиваться в переменную.
Типы значений: несколько примитивных: числа-строки итд., и главный составной тип: список.
Примеры значений (точнее, строк, которые станут этими значениями, если их прочитает парсер Схемы):

3 - целое число
3.5 - действительное число
#t - boolean true
#\A - знак большая латинская A (character; по-русски обычно 'символ', но это слово занято ниже)
"foobar" - строка
foobar - символ (symbol); как строка, но не совсем. Используется для имен функций, переменных идр.

(3 "foo" 4.5) - список из трех значений. значения разделяются пробелами или вообще говоря whitespace.

(3 "foo" (4 #t) 5) - список с вложенным списком

Любое значение можно выполнить, и тогда получается другое значение. Для примитивных типов это ничего не значит, они "выполняются" сами в себя. Если выполнить значение 3.5, получится 3.5. Главное, для чего нужно выполнение - для списков. Чтобы "выполнить" список, первое значение в нем считается именем функции, все остальные значения - аргументами, функция вызывается с этими аргументами, и то, что она возвращает - это результат выполнения:

(+ 3 5.5) - список из трех значений: символ +, числа 3 и 5.5. Символ + неким способом, о котором позже, связан с встроенной функцией сложения. Теперь если выполнить значение (+ 3 5.5), то вызовется встроенная функция с аргументами 3 и 5.5, и вернет 8.5, поэтому это результат выполнения.

(foo 4 (* 2 5) ) список из трех значений, одно из которых само список. Когда этот список выполняется, сначала выполняются каждый из его аргументов: 4 дает само себя, а (* 2 5) дает 10, и потом вызывается какая-то функция foo, которая определена в другом месте, с аргументами 4 и 10. То, что она возвращает, и есть результат.

Программа на Схеме - набор значений. Запустить программу на Схеме значит прочитать эти значения и выполнить их одно за другим. Некоторые из этих значений запускают встроенные функции, которые определяют другие функции, например foo. Потом другие значения могут вызывать foo. Поэтому то, что на C совсем разные вещи с точки зрения синтаксиса: "2+4" и "int foo(int a) { return a+5 };", в Схеме одинаковые по сути вещи, значения: (+ 2 4), (define (foo a) (+ a 5))

На самом деле я соврал насчет списка, это не фундаментальный тип, а фикция, чтобы удобно было записывать. Списки составляются из пар, где пара - фундаментальный тип, значение, которое хранит два других значения (любого типа). Пары можно записать с помощью синтаксиса ( . ):

(3 . "abc") значение-пара, первое значение в паре 3, второе "abc". Традиционно первое называют car, второе cdr, и так называются встроенные функции, которые достают первое/второе значение из пары.

Списки строятся из вложенных пар: список есть пара, в которой первое значение - первый элемент списка, а второе значение - новая пара, в которой первое значение - второй элемент списка, а второе значение - новая пара...

(3 4 "abc") то же, что

(3 . (4 . ("abc" . () ) ) )

Здесь () - специальный объект "пустой список", который заканчивает вложенную иерархию пар.

----------------------------end tutorial-------------(если что-то очень непонятно, можно спросить)-------------

----------------------------braindump--------------------------------

Нужно как-то хранить значения и следить за ними. В самом языке нет управления памятью, интерпретатор должен следить за тем, какие значения более не нужны, и убирать их. Разные значения могут требовать разного кол-ва памяти (целое число и длинная строка). Фундаментальный вопрос: как представить пару, внутри которой хранятся два других значения. Видимо, концептуально проще относиться к ней как к паре пойнтеров, а не напр. вкладывать значения в значения; напр. потому, что иначе придется отдельно хранить за жизнью и востребованностью значений внутри значений.

Если делать отдельный malloc() для каждого значения, то во-первых много крохотных объектов, во-вторых все равно где-то надо следить за ними за всеми, чтобы потом собрать мусор. Проще, и согласуется с принципом "как можно меньше кода": пусть будет фиксированная клетка для каждого значения. Но значение может требовать больше памяти, чем есть в клетке. Тогда дадим такому значению несколько клеток. Все клетки могут лежать в одном массиве, который предоставляет всю память для Схемы.

Мы хотим писать на чистом C, но ориентироваться на 64-битные архитектуры, потому что сейчас 2010-й год. (конечно, код будет работать без всяких проблем и под 32-битной системой). Поэтому я собираюсь активно использовать фиксированные типы данных: uint32_t и uint64_t вместо int итп. Размер клетки будет фиксированный, но какой? 32-битная клетка кажется слишком маленькой: в ней нужно оставить место для кучи битовых полей, определяющих статус, тип итд., и тогда в оставшиеся биты даже большое целое число не вместишь. Возьмем 64-битную клетку и заплатим за это памятью, когда мы не пользуемся всеми этими 8 байтами.

Получается что-то вроде: uint64_t cells[]. Любое значение определяется некоей клеткой cells[i], в которой несколько битов рассказывают, что это за тип, итп. Кроме того, в cells[i] отведено место сказать, сколько следующих за i клеток являются все еще частью этого значения. Как именно эти следующие клетки используются, зависит от типа.

Сколько бит отвести под поле кол-ва следующих клеток? Строка длиной в X байт требует ~X/8 клеток. Восьмибитное после слишком маленькое, 16-битное поле даст строки размером максимум в пол-мегабайта, скажем, что нам этого достаточно. Логично еще 16 бит отвести под всякие флаги и тип клетки, с запасом, и тогда оставшиеся 32 бита - для "immediate value", т.е. туда влезет 32-битное целое число или знак или крохотная строка, но не действительное число и не пара.

Чтобы передать пару, надо две "ссылки"; если это настоящие ссылки, то под 64-битной архитектурой это еще две клетки. Наверное, лучше использовать индекс клетки, i; если ограничить его 32 битами, тогда пара влезает в одну дополнительную клетку. Это ограничение означает максимум в 2^32 клеток, т.е. 32GB памяти под Схему - более чем достаточно.

Есть соблазн это соптимизировать. Пар очень много, поэтому желательно, чтобы пара занимала вообще только одну клетку. Может, для клеток-пар отвести всего несколько битов для флажков, и скажем 60 бит для двух ссылок-индексов, с максимумом 2^30? Пока воздержусь от этого соблазна, чтобы код был попроще.

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

uint32_t next_cell скажет нам индекс следующей свободной клетки. Когда нужна клетка, ставим ее туда и увеличиваем. Это проще, чем хранить список свободных мест и менеджить его. Когда массив кончается, врубаем сборщик мусора и уплотняем все.
#define MAX_CELLS 1000000 uint64_t cells[MAX_CELLS]; uint32_t next_cell = 0; #define CHECK_CELLS(i) do { if (next_cell + i >= MAX_CELLS) \ die("out of cells"); } while(0); // 4 lowest-order bits for the type #define TYPE 0xF #define T_NONE 0 /* this cell is unused */ #define T_INT32 1 /* immediate 32-bit value */ #define T_PAIR 2 /* pair, uses next cell */ #define T_STR 3 /* string */ #define T_EMPTY 4 /* empty list, a special value */ #define T_BOOL 5 /* boolean */


Попробуем прочитать значение из какой-то строки и сохранить его в памяти. Поскольку значение может включать в себя вложенные списки, т.е. вложенные пары, главная функция будет рекурсивной (для простоты, опять-таки). Она возвращает true/false, продвигает указатель на входную строку, и возвращает индекс клетки, где начинается созданное значение (необязательно next_cell-1: есть значения, которые занимают много клеток). Для максимальной простоты этой первой версии будем читать только целые числа, списки, строки без escaping'а внутри, и символы.

int read_value(char **pstr, uint32_t *pindex) { char *str = *pstr, *p; int num, count; uint64_t value; uint32_t index = next_cell; while(isspace(*str)) ++str; if (sscanf(str, "%d%n", &num, &count) >= 1) { str += count; value = T_INT32 | ((uint64_t)num << 32); CHECK_CELLS(1) cells[next_cell++] = value; *pindex = index; *pstr = str; return 1; } if (*str == '"') { char *end = ++str; while(*end && *end != '"') ++end; if (*end == '\0') return 0; // TODO: actually pack bytes into the cells rather than 1 per cell CHECK_CELLS(end-str); value = T_STR | (uint64_t)(end - str) << 16; cells[next_cell++] = value; for (p = str; p < end; p++) cells[next_cell++] = *p; *pindex = index; *pstr = end+1; return 1; }

Главный случай - это чтение списка. Сначала проверяем, что это не (). Потом читаем первое значение. Потом на всякий случай проверим, не закончился ли список на одном значении - тогда это и не список на самом деле. Предположим, нет.

Теперь нам надо решить, воплощать синтаксис (а . б) или плюнуть пока. Скажем, что пусть будет. Значит, либо мы видим . и второе значение и ). Либо, если мы не видим ., то как нам справиться с остальными элементами списка (v1 v2 v3 ...)? Если мы в цикле будем вызывать read_value, пока не дойдем до закрывающей скобки, то нужно будет вставлять еще раз код создания пары, плюс отдельно проверять случай (v1 v2 v3 . v4).

Лучше сделать вид, что после (v1 мы якобы открыли новый список и уже прочитали его первую скобку; пусть read_value сделает за нас все остальное. Для этого надо добавить ей аргумент, который обычно будет false, кроме этого случая:

#define SKIP_WS(str) do { while(isspace(*str)) ++str; } while(0) int read_value(char **pstr, uint32_t *pindex, int implicit_paren) { [...] if (implicit_paren || *str == '(') { if (!implicit_paren) ++str; SKIP_WS(str); /* allows ( ) as the empty list, why not I guess */ if (*str == ')') { [store T_EMPTY and return 1] } uint32_t index1; int res = read_value(&str, &index1, 0); if (!res) return 0; SKIP_WS(str); if (*str == ')') { /* just one value in the list */ *pstr = str+1; *pindex = index1; return 1; }

Пришла пора читать либо . и второе значение пары, либо остаток списка:
int dot_pair = 0; if (*str == '.' && isspace(*(str+1))) { dot_pair = 1; str++; } uint32_t index2; res = read_value(&str, &index2, !dot_pair); if (!res) return 0; [store the pair, second cell is (index1 << 32) | index 2 and return 1]

Один и тот же рекурсивный вызов работает и для пары, и для списка.

Однако проверка показывает, что в этом коде есть целых два бага. Во-первых, это только кажется, что кроме аргумента !dot_pair, случаи (1 2) и (1 . 2) должны работать аналогично. На самом деле рекурсивный вызов в (1 . 2) должен прочитать только значение '2', а наличие закрывающей скобки мы не проверили. Это первый баг. Во-вторых, (1 2) должен как раз красиво сам хватать закрывающую скобку, потому что "2" и ")" читаются в вложенных рекурсивных вызовах с implicit_paren==1, так что ")" как раз попадает на проверку пустого списка, и мы получаем (1 . (2 . () ) ), как и хотели. Но это не работает, потому что при чтении "2)" с implicit_paren==1 код считает, что он считывает (2) и попадает на случай одиночного списка. Нужно этот случай запереть, когда implicit_paren==1.

Исправляю другие мелкие баги. Кроме того, добавляю код для чтения символов, который здесь не привожу, он очень похож на строки. Символ пробуем прочитать, только если все остальное не удалось. Символы могут выглядеть странно, например, начинаться с ? или целиком быть "+". В спецификации есть грамматика, я беру из нее нужные несколько строк и делаю из них #define'ы для проверки этих случаев.

Есть еще одна тонкость, которую не упомянул. Код построен так, что read_value() может вернуть false, но внести при этом всякие новые клетки - это в случае, если она не сразу сдается, а некоторые вложенные вызовы срабатывают. Можно было бы запоминать значение next_cell и делать rollback; я решил этого не делать сознательно, чтобы код был проще. Эти клетки никому не мешают, и следующая уборка мусора их уберет.

Пора заканчивать этот припадок, но даже самую первую и примитивную версию кода не стоит оставлять без REPLа. REPL - это read-eval-print loop, традиционный способ в ЛИСПовых языках общаться с системой, вводя в нее значения, которые она немедленно интерпретирует. Иными словами, командная строка. Посколько у нас "eval" еще никакого нет, сделаем просто цикл, который читает с стандартного ввода строку, пытается ее понять с помощью read_value(), и если удается, канонически распечатывает. Код распечатки длинный, но простой, опускаю его, а main() выглядит так:
int main(int argc, char **argv) { char buf[512]; while(1) { printf("%d cells> ", next_cell); if (fgets(buf, 512, stdin) == 0) die("fgets() failed"); char *str = buf; uint32_t index; int res = read_value(&str, &index, 0); if (res) { dump_value(index); printf("\n"); } else printf("failed at: %s\n", str); } return 0; }


-------------------------------конец первого припадка------------------------------

Ведь код до сих пор, файл sketch.c. 200 строк, я думал, что будет меньше.
Tags: набросок
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 80 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →