набросок, припадок третий

avva — 19.07.2010 (интересно будет только программистам)

Продолжение наброска.

Я пометил все записи про набросок тагом 'набросок', и буду впредь так делать.
Весь код, как и раньше, выкладывается на github/avorobey/sketch.

Спасибо всем, кто в прошлый раз указал на баги, критиковал прозу, и вообще высказывал свои мысли о проекте.

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

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

------------------------------------tutorial------------------------------------------------
Секции tutorial всегда предполагают, что вы читали и поняли эти секции из предыдущих припадков.

В Схеме есть отдельный тип булевых значений, как bool в C++ или boolean в Джаве. С помощью этих значений удобно организовывать условные вычисления, т.е. "if" сотоварищи. Есть только два возможных булевых значения: истина и ложь, и они обозначаются символичестки #t и #f. В таком виде их можно использовать в тексте программы итд. Функции, которые сравнивают что-то с чем-то, или проверяют истинность чего-то, обычно возвращают #t и #f, и их называют предикатами. Так просто принято их называть, с точки зрения Схемы в этих функциях нет ничего особенного; поскольку в Схеме нет статической проверки типов, любая функция может возвращать значение любого типа, равно как и любая переменная может содержать значение любого типа.

Предикатам принято давать имена, заканчивающиеся на вопросительный знак; так, eqv? проверяет, одинаковые два объекта передали этой функции или нет. boolean? проверяет, передали ему значение булевого типа, #t/#f, или что-то другое. Есть несколько удобных исключений из этого правила вопросительного знака, например '=', '<' итд. проверяют равенство или отношения порядка между числами. Опять-таки, то, что в других языках требует специальной синтаксической поддержки (например, отдельных операторов ==, < итд. в C/C++), в Схеме делается с помощью все тех же значений, и функций, вызываемых с помощью списков. (= x y) вернет #t если в переменных x и y записаны одинаковые числа, #f во всех других случаях. И так далее.

Когда надо проверить что-то на истинность, например, условие для 'if', то истинным считается не только #t, но и вообще любое значение, кроме #f. Только #f считается ложным. Это бывает удобно, хотя - как и в C, где тоже принято такое правило - злоупотреблять этим тоже не стоит, потому что может получиться малопонятный код.

'if' принимает аргумент, который считается условием, а потом еще один, который соответствует 'then', т.е. что делать, если условие верно. И можно также передать еще один, который соответствует 'esle', а можно не передавать. (if (= 3 3) "foo") вернет "foo". (if (= 3 4) "foo" "bar") вернет "bar". (if (= 3 4) "foo") вернет неопределенный результат.

Поскольку при вызове обычных функций сначала выполняются все их аргументы, а потом уже вызывается функция, 'if' не может быть обычной функцией. Ведь если мы например написали (if condition (func1 arg1) (func2 arg2)), то если condition верно, мы вообще не хотим, чтобы (func2 arg2) вызывалось - иначе какое же это условное вычисление. Поэтому 'if' - специальная форма, а не обычная функция. Есть еще специальные формы (или, точнее, макросы, но о разнице между ними разговор будет позже, пока можно считать их специальными формами) работающие с булевыми значениями и помогающие организовать логику внутри функций. "case" похож по своей функциональности на switch в C, "cond" - более общий его вариант. "and" и "or" соответствуют булевым операторам && и || в C, и как они, вычисляются "лениво": при выполнении (or cond1 cond2), если cond1 окажется истинным, то cond2 и не будет даже выполнено. Эта "ленивость" требует от них быть специальными формами, а не функциями.

Векторы. Векторы в Схеме соответствуют массивам в C. Как должно быть ясно из определения списка, список в Схеме похож на "связанный список", а не на "массив", в терминологии базисных структур данных: в списке легко двигаться от начала вперед до конца, но невозможно мгновенно попасть на элемент номер k, надо сначала перебрать первые k-1. В Схеме очень многое из того, что обычно программист на C сделает с помощью массива, делается через списки - это оказывается очень удобным и интуитивным. Но иногда все же необходим быстрый доступ к любому элементу, и тогда можно использовать векторы. Несмотря на то, что доступ к каждому элементу быстрый, каждый элемент все равно может хранить в себе значение любого типа (в отличие от массивов в C). Техническое слово для массивов такого рода - "гетерогенные", heterogeneous. Векторы можно записать в тексте программы вот так: '#(1 2 "foo" (3 4)) (апостроф вначале необходим, чтобы система не попыталась их выполнить, как и в случае списка), и есть разнообразные встроенные функции для доступа к их элементам.

Знаки (characters). В C знаки хранятся в численных переменных, а в Схеме для них есть отдельный тип. Главным образом знаки нужны для того, чтобы делать что-то полезное со строками. Есть языки, в которых строки являются не примитивным типом, а просто списком знаков. В Схеме это не так, по-видимому, из соображений скорости работы; но любую строку можно перевести в список знаков и обратно функциями string->list и list->string. В тексте программы знак можно указать так: #\r (это строчная буква r), или, для некоторых знаков, которые так трудно набрать, по имени: #\space и #\newline.

Да, возвращаясь на секунду к спискам, стоит упомянуть важные встроенные функции cons и list. (cons arg1 arg2) просто-напросто создает новую пару, первый элемент которой - значение arg1, второй - значение arg2. "cons" (равно как и "car", и "cdr") называется так из исторических соображений, и смысл этих названий утерян в глубине веков. То, что в Схеме называется "пара", когда-то называли "cons cell", потому что это клетка, которую строят с помощью функции cons. Как вы помните, список в Лиспе состоит из вложенных друг в друга 'с правой стороны' (вторыми элементами) пар. Список (1 "123" #t) можно также представить, с помощью записи пары с точкой, так: (1 . ("123 . (#t . ()))). Его же можно получить, выполняя несколько раз функцию cons, так: (cons (1 (cons ("123" (cons (#t ()))))).

Функция list попросту создает список из всех своих аргументов: тот же список из предыдущего абзаца можно получить, выполнив (list 1 "123" #t). На первый взгляд может быть непонятно, зачем такая функция нужна; но если это непонятно, это как раз свидетельствует о том, что вы недостаточно хорошо понимаете, как списки и "выполнение" работают друг с другом, и стоит об этом подумать. Как мы можем получить, в результате выполнения чего-то, список (1 "123" #t)? Конечно, просто написать его в тексте программы нельзя, потому что Схема попытается выполнить сам список, т.е. вызвать функцию '1', но это не функция вовсе. Можно вызвать несколько раз cons, как в прошлом абзаце, но это долго. Можно написать '(1 "123" #t) или, что то же самое, (quote (1 "123" #t)), и это сработает и даст нам этот список. Но теперь посмотрим на другой пример: пусть у нас в переменных x и y есть какие-то значения, и мы хотим сделать из этих значений список. Тогда (x y) все еще не подходит (попытается вызвать функцию, записанную в переменной x). '(x y) тоже не подходит, потому что это даст в точности список (x y), т.е. список из *символов* x и y, а не значений *переменных* x и y. Использование quote полностью выключает выполнение того, что внутри, но это не то, что нам надо! А вот (list x y) даст именно то, что надо, потому что это не специальная форма, а обычная функция, и ее аргументы будут выполнены. Вот для таких случаев она и нужна.

Наконец, поговорим о функциях, которые определяет сам программист. До сих пор мы имели дело только с встроенными функциями, которые готовы для использования, например (car '(1 2)). Новая функция, которую вы можете написать сами, определяется с помощью специальной формы lambda (это слово используется ради его сакрального значения, сохранившегося еще с времен примитивных культур). Предположим, в C мы бы написали функцию int my_plus(int x, int y) { return x+y }. В Схеме, в отличие от C, функция не обязана иметь имя; каждая функция рождается 'анонимной' и выглядит, например, так: (lambda (x y) (+ x y)). Первым аргументом lambda является список параметров, а за ним идет тело функции - попросту значения, которые надо выполнить. В данном примере значение одно, но их может быть несколько - тогда функция возвращает результат последнего из них. Значения могут быть любые; например, я могу написать (lambda (x y) 123 "foo" (+ x y)), и это будет то же самое, потому что первые два значения тела, 123 и "foo", выполнятся сами в себя и ничего полезного не сделают, а вернет функция то, что вернет выполнение (+ x y). Понятно, что когда я вызываю эту функцию, и передаю ей какие-то два аргумента, скажем 10 и 15, то перед выполнением тела (+ x y) Схема каким-то образом "подставит" в переменную x значение 10, а в переменную y значение 15. И тогда функция вернет 25, как и надо. Как именно работает эта "подстановка" - отдельная сложная тема, к которой мы еще вернемся.

Но как, собственно, эту функцию вызвать, если у нее даже нет имени, в отличие от car, list итд.? Ну, во-первых, хоть у нее нет имени, но вот она у меня в руках, как значение - ее создала и вернула форма lambda. Поэтому я могу немедленно ее вызвать, по обычной схеме вызова через список: ((lambda (x y) (+ x y)) 10 15) вернет 25. Если вы не понимаете этот пример, вглядывайтесь в него, пока не поймете, это важно. Кроме того, мы знаем, что (define y "123"), например, определяет переменную y с значением "123"; поэтому можно написать (define my-plus (lambda (x y) (+ x y))), и теперь наша функция "сидит" в переменной my-plus. Теперь можно написать (my-plus 10 15), и это сделает то, что надо.

Вот так, собственно, и создают новые функции в Схеме. В одном из предыдущих припадков я привел пример, который выглядел по-другому: скажем, (define (my-plus x y) (+ x y)). Так действительно проще написать, если заранее знаешь, какое имя хочешь дать функции, и так обычно пишут в программах на Схеме. Но важно отдавать себе отчет, что этот способ - всего лишь сокращенный вариант, для удобства, (define my-plus (lambda (x y) (+ x y))). На самом деле то, что происходит - это лямбда, и важно это понимать, хотя бы потому, что в Схеме сплошь и рядом пользуются анонимными функциями, которые пишутся именно с lambda, и надо уметь это делать.

------------------------------------braindump------------------------------------------------
Еще до начала работы над этим припадком я починил несколько багов, некоторые по наводке комментаторов (спасибо!),
некоторые нашел сам. Один баг был смешной: в выражении типа (define y 3) я не вычислял третий аргумент, а присваивал
его в y как есть. Для такого примера это неважно, но скажем (define y (+ 3 5)) уже работает неправильно: оно должно положить в y 8, а кладет список (+ 3 5). Исправлено добавлением одной строки: val = eval(val).

Другой интересный баг был в ридере (в чтении исходников): когда ему встречалась закрывающая скобка ")", он не двигал указатель текущего знака в строке на единицу. В результате любая закрывающая скобка как бы продолжала ему попадаться неограниченное число раз, закрывала все открытые списки и заканчивала проход. Выражение типа (define y (+ 3 5)) работало правильно, а какое-нибудь (+ (+ 3 5) 10) - нет, превращалось в (+ (+ 3 5)).

Векторы. Я ничего не знал про векторы, когда начал проект, и опасался, что с моей моделью памяти их будет трудно сделать (если они могут расти). Оказалось, однако, что у них фиксированный размер, и поэтому с ними должно быть очень просто. Вектор размером n должен хранить n "ссылок" на другие значения; будем складывать их по два в следующие за основной клетки: как строки, только вместо восьми знаков на клетку тут два индекса на клетку. Как и со строками, отдельно сохраним в главной клетке, кроме длины в клетках, "настоящую" длину в элементах. Обращаться к вектору и менять значения элементов будет очень легко.

Единственное, что нетривиально - прочитать литерал вектора, т.е. запись типа #(1 2 "123" (4 5) foo), и создать из нее вектор. В отличие от списков, которые можно создавать динамически по мере чтения списка, тут придется прочитать все значения, а потом "одним махом" создать вектор. Наверное, можно было заметить до сих пор, что я стараюсь избегать malloc()-ов и менеджмента памяти, насколько это практично, но тут без этого не обойтись: я бы не хотел ставить небольшой априорный предел размеру массива. Я выделю этот код из read_value() в отдельную вспомогательную функцию read_vector(), и в ней заранее отведу место для 1000 индексов - этого хватит для практически всех реальных массивов - но все же код для тех случаев, когда массив длиннее, написать придется.

P.S. Я хочу прояснить, что код функции read_vector() - плохой код, и согласно моим же собственным принципам мне следовало написать его по-другому. Он в два или три раза длиннее, чем должен быть согласно принципу "простота кода превыше всего". Лучше было, например, пользоваться только malloc()-ом, без начального массива на стеке; или вообще не адаптировать размер, а malloc() один раз большой кусок памяти, на сто тысяч индексов, скажем, и назвать это жестким пределом. Однако мне хотелось написать так, чтобы в обычном случае обошлось без malloc()'а. У этого желания нет реального оправдания с точки зрения performance. Можно считать это капризом.

#define T_VECT 8 /* vector */ #define VECTOR_START(i) (uint32_t *)(cells+i+1) #define VECTOR_LEN(i) (cells[i] >> 32) /* helper func to read a #(...) literal vector */ int read_vector(char **pstr, uint32_t *pindex) { uint32_t initial_indices[2]; int max_index = 2, cur_index = 0; uint32_t *indices = initial_indices; int malloced = 0; char *str = *pstr; while(1) { SKIP_WS(str); if (*str == ')') break; int res = read_value(&str, &indices[cur_index], 0); if (res == 0) { if (malloced) free(indices); return 0; } cur_index++; if (cur_index >= max_index) { /* need to grow */ max_index *= 2; indices = malloced ? realloc(indices, max_index*sizeof(uint32_t)) : malloc(max_index*sizeof(uint32_t)); if (indices == 0) die("couldn't alloc memory for a vector"); if (!malloced) { memcpy(indices, initial_indices, 2*sizeof(uint32_t)); malloced = 1; } } } /* we've seen ')' and all is good. store and cleanup */ str++; /* one past the ')' */ uint32_t len = (cur_index+1)/2; /* num of extra cells required */ CHECK_CELLS(1+len); uint32_t index = next_cell; uint64_t value = T_VECT | (uint64_t)len << 16 | (uint64_t)(cur_index) << 32; cells[next_cell++] = value; memcpy(VECTOR_START(index), indices, cur_index*sizeof(uint32_t)); if(malloced) free(indices); next_cell+=len; *pindex = index; *pstr = str; return 1; }

Код в read_value() вызывает эту функцию сразу после прочтения
#(, так что она сразу начинает читать значения элементов.



Этот код заработал с первого раза, что меня приятно удивило. Но
когда я просмотрел его еще раз, зная, что мне нужно проследить, что
free() вызывается во всех путях сквозь код, я обнаружил, что забыл
написать if(malloced) free(indices); ближе к концу функции, и
добавил это. В качестве грубой проверки того, что все его части
работают, я изменил константы 1000 и *=5 на 2 и *=2, и попробовал
вручную вводить всякие векторы.



Код для показа векторов в dump_value() вполне прозрачный, и
демонстрирует стандартный выверт "сделай что-то в каждом проходе
цикла, кроме последнего":

case T_VECT: length = VECTOR_LEN(index); uint32_t *start = VECTOR_START(index); printf("#("); for (i = 0; i < length; i++) { dump_value(start[i], 0); if (i != length-1) putchar(' '); } putchar(')');

Знаки (characters). Добавить поддержку этого типа очень
легко. Надо уметь читать запись типа #\c, где c - любой
ASCII-символ, или два специальных случая "#\space" и "#\newline". Я
не стал добавлять другие имена знаков, потому что эти два - все,
что требует стандарт. Значение знака целиком умещается в одну
клетку, конечно - 8 бит, передающих сам знак, идут в верхние 32
бита клетки. Если когда-нибудь потом в набросе будет поддержка
Юникода, это можно будет сохранить - в верхние 32 бита клетки
полностью помещается расширенный Юникод-символ. Я не цитирую здесь
код чтения и показа знака, он очевиден, см. исходники. Я вначале
забыл добавил T_CHAR в eval() - знаки выполняются в самих себя, как
числа и строки - потом добавил. Кстати, T_VECT туда не надо
добавлять, т.к. вектор сам по себе не может выполниться, это
ошибка. Чтобы ввести вектор в текст программы, нужно процитировать
его апострофом.



Булевые значение. Прочитать их легко: #t и #f. Вопрос в том, как их
представить. Первоначально я отвел для них тип T_BOOL, и ясно, что
легко найти бит, чтобы передать их значение. Но я сказал себе
заранее, что когда дойду до работы с истинностью/ложностью, решу,
не стоит ли перейти к универсальным константам для них, и пришла
пора принять это решение. Суть в том, что для нескольких значений:
#t, #f и () это те, что приходят мне на ум - жаль всякий раз
создавать новую клетку для их хранения. Их невозможно изменить, и
они встречаются все время: например, () заканчивает каждый список
(второй элемент в последней паре). Не стоит ли поэтому отделить для
них несколько начальных клеток, подобно тому, как индекс 0 я
выделил для ошибки?



Но если для () используется всегда один и тот же индекс, тогда само
значение индекса может служить идентичностью (), а не его тип
T_EMPTY. Значения индексов могут сидеть в глобальных переменных
типа cell_empty, cell_true, cell_false.

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



Подумав, я решил все-таки это сделать. Мне не нужны больше T_BOOL и
T_EMPTY, но я введу вместо них T_RESV (reserved), которым будут
помечены все такие "специальные" клетки; это дает мне возможность
отвести им case T_RESV внутри разборок switch по типу, и уже внутри
этого случая смотреть на индекс. Это, наверное, чуть-чуть
медленнее, чем прямая проверка, но совершенно незначительно.



Изначально, когда я об этом думал, то хотел держать индексы
специальных значений в глобальных переменных типа cell_empty, и
регистрировать их вначале похожим на register_builtins() способом.
Но сейчас я подумал, что просто отгородить несколько первых
индексов и использовать #define EMPTY 2 итд. ничем не хуже.
Непохоже, чтобы меня это ограничило в будущем, код от этого проще и
чуть-чуть быстрее (тоже, впрочем, незначительно, т.к. значения этих
переменных все время сидели бы в кэшах процессора).

#define T_RESV 5 /* special value: bool or () */ /* special index values */ #define C_ERROR 0 #define C_UNDEFINED 1 #define C_EMPTY 2 #define C_FALSE 3 #define C_TRUE 4 /* start after all these special values */ uint32_t next_cell = 5; void init_cells(void) { cells[C_EMPTY] = cells[C_FALSE] = cells[C_TRUE] = T_RESV; }

Код, который имел дело с T_EMPTY или T_BOOL (впрочем, с
T_BOOL у меня ничего еще не было) меняется; вот пример нескольких
таких изменений, и нового кода для чтения/показа булевых
значений:

#define LIST_LIKE(i) (TYPE(i) == T_PAIR || i == C_EMPTY) /* TODO: should have a handy universal empty list value */ CHECK_CELLS(1); uint32_t empty = next_cell; cells[next_cell++] = T_EMPTY; uint32_t pair = empty C_EMPTY; /* () at first; then pairs in the loop */ void dump_value(uint32_t index, int implicit_paren) { [...] switch(TYPE(index)) { case T_RESV: if (index == C_EMPTY) printf("()"); else if (index == C_FALSE) printf("#f"); else if (index == C_TRUE) printf("#t"); else die("unknown RESV value"); break; uint32_t car(uint32_t index) { /* check that we have just one argument (the list is of size 1) */ if (TYPE(index) != T_PAIR || CDR(index) != C_EMPTY) return 0; [...]

И так далее.



Я поймал себя на том, что не добавляю очевидные и простые
встроенные функции, потому что от этого файл sketch.c еще больше
разрастется. Очевидно, пришла пора выделить встроенные функции в
отдельный файл. Я не то чтобы сильно заинтересован в строгом
API-барьере между этим новым файлом builtins.c и sketch.c - пока
что мне не помешает, если встроенные функции будут обращаться к
cells, пользоваться удобными макросами итд. Но т.к. они должны все
это теперь как-то увидеть, пришла пора заодно написать header file.
Я назову его common.h и перенесу туда большинство #define'ов,
extern'ы нескольких ключевых переменных, и прототипы полезных
функций. Кроме того, я добавил несколько удобных макросов для
использования в встроенных функциях - они проверяют количество
аргументов и инициализируют их; и удобную служебную функцию
check_list, которая проверяет, что в списке есть достаточно
элементов, и он хорошо построен. check_list, возможно, немного
перегружена фунциональностью, на что указывает длинный комментарий,
объясняющий ее поведение. Но мне не хотелось разводить это в 2-3
делающих практически то же самое функции.

(P.S. позже, когда мне понадобилось написать функцию для подсчета
длины списка, у меня был соблазн внести это тоже в check_list; но
это уже перевесило бы баланс между сложностью и полезностью, на мой
взгляд).

/* checks that index is a proper ()-terminated list with at least count elements. if strict is true, must be exactly count elements. count==0, strict==0 allows any list. () itself is a list. */ int check_list(uint32_t index, int count, int strict) { while(index != C_EMPTY) { if (TYPE(index) != T_PAIR) return 0; if (strict && count <= 0) return 0; index = CDR(index); if (count > 0) --count; } if (count > 0) return 0; else return 1; } #define ONE_ARG(name) uint32_t name; if (!check_list(args, 1, 1)) \ return 0; name = CAR(args); #define TWO_ARGS(name1, name2) uint32_t name1, name2; \ if (!check_list(args, 2, 1)) return 0; name1 = CAR(args); \ name2 = CAR(CAR(args));



Теперь писать встроенные функции легко и приятно. Я добавляю
множество легких функций из 
шестой главы стандарта.



Несколько примеров:

#define GEN_TYPE_PREDICATE(func_name, type) \ uint32_t func_name(uint32_t args) { \ ONE_ARG(name); \ if (TYPE(name) == type) return C_TRUE; \ else return C_FALSE; \ } GEN_TYPE_PREDICATE(procedure_p, T_FUNC) GEN_TYPE_PREDICATE(vector_p, T_VECT) GEN_TYPE_PREDICATE(string_p, T_STR) uint32_t null_p(uint32_t args) { ONE_ARG(index); if (index == C_EMPTY) return C_TRUE; else return C_FALSE; }





Заодно я делаю легкий рефакторинг нескольких вспомогательных
функций в sketch.c, а также разбираюсь с "unspecified value". В
Схеме некоторые вызовы функций или специальных форм не возвращают
никакого значения - или, точнее, согласно стандарту, возвращают
"unspecified value". Например, (define y 12) не возвращает ничего,
просто делает свою работу. Ясно, что в моем коде было бы очень
неудобно делать так, чтобы эти функции/формы действительно ничего
не возвращали (void с точки зрения C), это добавит кучу муторного
клея, чтобы примирять интерфейсы. Стандарт не мешает им вернуть
что-то, и в принципе незаконно пользоваться для чего либо тем, что
они возвращают. Поэтому я могу, например, решить, что всегда в
таком случае возвращается пустой список (). Или число 42. Или
вообще что угодно. Но это неудобно для отладки и понимания того,
что происходит: когда я в командной строке набираю (define y 12), я
не хочу увидеть "ответ" (), я хочу ничего просто не увидеть.
Поэтому я ввел дополнительное зарезервированное значение
C_UNDEFINED, но больше ничего с ним не делал. Теперь я ввожу его в
действие: переименовываю в C_UNSPEC, даю ему тоже (как () и
булевым) тип T_RESV, решаю дать ему выполняться в самого себя (для
этого ничего не надо менять), и при распечатке чтобы ничего не
показывал. Теперь можно продолжить с встроенными функциями, и
set-car! вместе с set-cdr! могут со спокойным сердцем согласно
стандарту вернуть C_UNSPEC. Вот, например, set-car! (фунцкия,
меняющая первый элемент данной пары на другое значение):

uint32_t set_car(uint32_t args) { TWO_ARGS(arg1, arg2); if (TYPE(arg1) != T_PAIR) return 0; uint64_t val = cells[arg1+1]; cells[arg1+1] = (val & 0xFFFFFFFF) | (uint64_t)arg2 << 32; return 1; }





Добавляю предикаты равенства eqv?, eq?, equal?. Все довольно
просто, но для equal? мне наконец надо сравнивать значения строк, а
не только символов. Оказывается логичным переименовать макросы
SYMBOL_NAME и SYMBOL_LEN в STR_START и STR_LEN, не меняя их
содержимого: строки и символы сейчас хранятся одинаково. В скором
будущем символы будут храниться по-другому, но тогда все равно
придется менять все места, к-е их сравнивают.



Добавляю функции для работы с векторами: vector-length, vector-ref
(вытащить элемент номер k из вектора). Раньше я решил не писать в
этом припадке функции перевода типов, напр. string->list и
list->string - перевод строки в список знаков и наоборот -
просто не хотелось этим заниматься. Но сейчас по прихоти решаю
написать vector->list и list->vector. Вот забавное
совпадение: для функции vector->list мне нужно что-то, что
создает список из многих элементов. У меня уже есть такая функция,
make_list в sketch.c, которая мне нужна была для eval() - чтобы из
вычисленных аргументов к функции, сидящих в локальном массиве,
создать схемный список аргументов. Оказывается, мне не надо ее
менять или обобщать, потому что вектор тоже представляет все свои
элементы в виде массива uint32_t, сидящего внутри клеток. Это очень
удобно. С кодом для list->vector тяжелее, потому что
существующий код построения вектора, в функции read_vector(),
делает это из локального массива, а не из списка. Можно было бы
абстрагировать создание вектора в отдельную функцию, умеющую читать
уже готовые значения как из массива, так и из списка, но код был бы
довольно уродливый, и я решаю этого не делать.

uint32_t vector_list(uint32_t args) { ONE_ARG(vect); if (TYPE(vect) != T_VECT) return 0; return make_list(VECTOR_START(vect), VECTOR_LEN(vect)); } uint32_t list_vector(uint32_t args) { ONE_ARG(list); int len = length_list(list); if (len == -1) return 0; uint32_t len_cells = (len+1)/2; CHECK_CELLS(1+len_cells); uint32_t index = next_cell; uint64_t value = T_VECT | (uint64_t)len_cells << 16 | (uint64_t)(len) << 32; cells[next_cell++] = value; uint32_t *elements = (uint32_t *)&cells[next_cell]; for (int i = 0; i < len; i++) { *elements++ = CAR(list); list = CDR(list); } return index; }

Существование list->vector порождает вопрос: зачем мне
нужна сложная и муторная функция read_vector(), которую я объяснил
выше (с маллоками итд.)? Может, просто прочитать вектор, как будто
это список, а потом перевести в вектор? В принципе это вполне
сработает и уменьшит количество кода строк так на 50 (!). Но этот
временный список займет чертовски много места (в четыре раза
больше, чем массив), а мне не хотелось бы так быстро сжигать память
на больших векторах. Не буду пока этого делать, но не уверен, что
это правильное решение. В будущем, когда будет работать сборщик
мусора и станет яснее, насколько часто он вызывается итд., можно
будет вернуться к этому.



Пожалуй, пока хватит встроенных функций. Можно еще много легких
добавить, но мне надоело. Кстати, одна из причин, по которым я
посвятил большинство этого припадка отшлифовке типов данных и
множеству встроенных функций, а не более "фундаментальным" и
привлекательным вещам типа поддержки лексической видимости и
замыканий - психологическая. Если все пойдет нормально и я закончу
"фундаментальные" вещи в удовлетворительном для меня виде, то надо
будет "дошлифовывать" систему, добавлять кучу встроенных функций
итд. Если во всем этом к тому времени еще даже конь не поваляется,
трудно будет себя заставить заниматься этой работой. А так -
заметная ее часть уже будет готова.



Я хочу добавить поддержку lambda, пусть даже еще без "нормальных"
схемовских переменных, все еще используя мою временную глобальную
символьную таблицу. Но до этого я добавлю специальную форму if,
потому что я подозреваю, что даже без нормальных переменных моя
lambda позволит мне написать рекурсивный факториал, а им будет
хорошо завершить этот припадок. Для рекурсивного факториала мне
нужен if.



Специальная форма (if condition X Y) или (if condition X) - у нее
есть два вида, с вариантом "иначе сделай тот-то" и без - пишется
легко и приятно рядом с другими специальными формами в eval(), типа
define и quote. Перед тем, как писать ее, я задумался о том, чтобы
перенести все специальные формы в другое место, организованно
сделав их чем-то вроде встроенных функций. Главное отличие
специальных форм от встроенных функций - в том, что для этих форм
необязательно надо выполнять их аргументы, они сами должны этот
вопрос решать. Ну так можно было бы в тип T_FUNC добавить бит,
который говорит: эту встроенную "функцию" вызывать, передавая ей
аргументы без выполнения их, она сама решит, что делать.
Специальные формы могли бы организованно регистрировать себя через
register_builtin(), как встроенные функции. eval() стала бы намного
проще.



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



Код if выглядит так:

if (IS_SYMBOL(func, "if")) { int len = length_list(args); if (!(len == 2 || len == 3)) die("bad if syntax"); val = eval(CAR(args)); /* condition */ if (val != C_FALSE) { /* only #if is false */ return eval(CAR(CDR(args))); } else { if (len == 3) return eval(CAR(CDR(CDR(args)))); else return C_UNSPEC; } }



Простую форму lambda, т.е. определение новых функций (не
встроенных), можно сделать так. Функция будет значением типа
T_FUNC, без бита BLTIN_MASK, и хранить в дополнительной клетке два
значения: список аргументов и тело фунцкии: список значений,
которые надо выполнить. Аргументы должны все быть символами. Когда
функцию вызывают со списком из N значений, код в eval() проверяет,
что размер списка аргументов тоже N, и добавляет символы из списка
аргументов в глобальную таблицу с соответствующими значениями, а
потом выполняет один за другим значения из тела.



Например, если я напишу: (define my-plus (lambda (x y) (+ x y))),
то выполнение специальной формы (lambda (x y) (+ x y)) создаст
объект T_FUNC, хранящий список аргументов (x y), и тело ((+ x y));
двойные скобки здесь - не ошибка. Когда кто-то вызывает (my-plus z
(* 3 5)), происходит следующее. Сначала выполняются аргументы z и
(*3 5); предположим, что в переменной z записано 17, и мы получаем
список параметров (17 15). Потом проверяется, что параметров
столько же, сколько формальных аргументов в (x y) - это так. Потом
в глобальную таблицу символов добавляется x->17 и y->15,
меняя предыдущие значения, записанные в этой таблице для
идентификаторов x и y, если таковые были. И, наконец, выполняются
все значения из тела, в данном случае только (+ x y), и
возвращается результат последнего, т.е. 32. Ограничения этого
примитивного способа определять функции должны тоже быть
очевидны:

переменные "внутри" функции мешаются с переменными "снаружи",
использование переменных в рекурсивных вызовах вообще не работает.
Но пока что этого достаточно.

if (IS_SYMBOL(func, "lambda")) { int len = length_list(args); if (len == -1 || len < 2) die("bad lambda syntax"); uint32_t args_list = CAR(args), body = CDR(args);

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

if (IS_SYMBOL(func, "lambda")) { int len = length_list(args); if (len == -1 || len < 2) die("bad lambda syntax"); uint32_t args_list = CAR(args); if (!check_list(args_list, 0, 0)) die ("bad lambda argument list"); /* TODO: check that args_list actually contains only symbols and they don't repeat */ uint64_t value = T_FUNC; CHECK_CELLS(1); uint32_t index = next_cell; cells[next_cell++] = value | (uint64_t)args << 32; return index; }

Вот код, тоже внутри eval(), который умеет теперь вызывать не
только встроенные функции, но и lambda-определенные. Получилось,
надо сказать, немного забавно. Когда я писал код для вызова
встроенных функций, то он сначала строил C-массив значений
аргументов, а потом специально запихивал его в новый список, с
помощью make_list(), и передавал его встроенной функции. Я это
сделал потому, что предполагал, что "обычные" функции будут такой
список использовать, и хотел, чтобы интерфейс был одинаковый. В
результате я еще и добавил макросы ONE_ARG и TWO_ARGS, чтобы
встроенные функции обратно из этого списка могли легко вытащить
главные аргументы. Но "обычным" функциям в итоге такой список ни к
чему, потому что значения аргументов прямым ходом идут в присвоение
к формальным параметрам функции, а это проще сделать в цикле по
массиву. Может быть, стоит переделать интерфейс к встроенным
функциям, чтобы они напрямую получали args_array и num_args - это
упростит некоторые из них, и немного ускорит весь процесс. Я пока
не буду это делать на всякий случай, пока у меня не готова версия
eval() с поддержкой лексической среды и хвостовой рекурсии, но
оставлю напоминание в TODO.

/* evaluate arguments and call the function */ uint32_t num_args; if (!eval_args(args, arg_array, &num_args)) return 0; if (cells[val] & BLTIN_MASK) { /* builtin function */ /* TODO: do we really need a list for builtin funcs? Reevaluate the interface to them after lexical scoping & tail calls are done. */ uint32_t list = make_list(arg_array, num_args); builtin_t func = (builtin_t)cells[val+1]; /* well, there you go */ return func(list); } else { /* lambda function */ uint32_t params_and_body = (uint32_t)(cells[val] >> 32); uint32_t params = CAR(params_and_body); if (length_list(params) != num_args) return 0; /* TODO: informative */ for (uint32_t i = 0; i < num_args; i++) { uint32_t param = CAR(params); params = CDR(params); if (TYPE(param) != T_SYM) return 0; set_symbol(STR_START(param), STR_LEN(param), arg_array[i]); } uint32_t body = CDR(params_and_body); uint32_t retval = C_UNSPEC; while (body != C_EMPTY) { retval = eval(CAR(body)); if (retval == 0) return 0; body = CDR(body); } return retval;



Ну и, наконец, вот обещанный код факториала. Поскольку я не написал
функции "минус", я отнимаю единицу путем прибавления минус
единицы.

$ ./sketch 59 cells> (define fact (lambda (n) (if (eqv? n 0) 1 (* n (fact (+ n -1)))))) *func* 131 cells> (fact 0) 1 142 cells> (fact 4) 24 209 cells> (fact 10) 3628800 360 cells>



На сегодня хватит. Проект вырос до 930 строк кода.



--------------------------------------послесловие-------------------------------------




Код
проекта (меняется по мере развития)



Код этого
припадка (зафиксирован во времени)



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