Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

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

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

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

У наброска появилась страница, на которой можно смотреть на весь код, как на текущее состояние, так и
на прошлые припадки (теги fit-1, fit-2 итд.).

-----<<<<<< предыдущая часть, там контекст и начало работы---

План работы (возможно, изменится): к концу этого припадка я хочу иметь возможность сказать (+ 3 5) и (car '(1 2)) и (set! y 13) и (+ y 22). Часть кода, который это воплотит, будет впоследствии переписана заново для поддержки лексической видимости и хвостовой рекурсии, которой сейчас еще не будет. Тот код, который предназначен на выброс, я напишу как можно проще и быстрее.

----------------------tutorial----------------------
Идентификаторы, т.е. имена переменных и функций, в Схеме называются символы. Символы указывают на значения в результате процесса, который называется binding и подробнее будет описан позже. Пока что тривиальный пример: (define y 4) определяет новую переменную y и присваивает ей значение 4. Если бы в Схеме, как в некоторых функциональных языках, были неизменяемые значения (immutable values), то больше ничего и не надо было говорить, но это не так. В Схеме на самом деле переменная связана не с значением, а с "ячейкой" (location), в которой это значение сидит, и можно его изменить. Если я выполню (set! y 5), то теперь значение y будет 5. Если напишу (set! y "214"), то y станет строкой, и так далее.

Результат выполнения символа - его значение. Поэтому, например, (+ y 10) дает результат 14, если y было со значением 4. Как я объяснил в прошлый раз: выполняются все значения в списке, первое из них принимается за функцию, которую надо вызвать, остальные - за ее аргументы, функция вызывается и то, что она возвращает, есть результат выполнения списка. В данном примере 10 выполняется в 10, y выполняется в 4, символ + выполняется в встроенную функцию сложения, она получает 10 и 4 и возвращает 14.

В прошлый раз я сказал, что аргументы всегда выполняются до вызова функции. Но это была ложь, или точнее недосказание, потому что когда выполняется список типа (foo bar1 bar2 bar3), символ foo необязательно выполняется в функцию. Ведь если бы это было так, как бы могло работать (set! y 5) выше? еще до вызова "функции" set! y заменилось бы на свое значение 4, и set! получила бы 4 и 5, и не смогла бы изменить y. То, что происходит на самом деле это вот что: set! это не функция, а пример 'специальной формы', встроенной в язык. Когда Схема распознает, что первое значение в списке - символ, указывающий на специальную форму, а не просто функцию, то она не выполняет остальные аргументы y и 4, а передает их как есть, без выполнения, и форма каким-то специальным образом что-то с ними делает. Например, set! дает переменной y новое значение, а (define y 4), показанное выше - тоже специальная форма - определяет новую переменную.

Еще один пример 'специальной формы' - "if": если я напишу (if x1 x2 x3), то это значит: "если x1 выполняется в истинное значение, то выполни x2 и верни его значение, иначе выполни x3 и верни его значение". Т.е. если x1 верно, я вообще хочу не выполнять x3, но если бы if была обычной функцией, это было бы невозможно.

Схема позволяет программисту создать свои новые варианты 'специальных форм', кроме встроенных в язык, таких как set!, define и if. Такие новые специальные формы называются 'макросы', о них позже.

Кроме того, что список является основным способом вызвать функцию в Схеме, он также является главной структурой данных в Схеме. Если у нас есть (foo 1 2 3), то выполнение этого списка вызовет функцию foo. А что если я просто хочу список (1 2 3) из трех чисел, чтобы работать с ним, как с данными? Ну например передать его функции car, чтобы она вернула первый элемент: 1. Если я напишу (car (1 2 3)), то будет ошибка: Схема попытается выполнить аргумент функции car, т.е. список (1 2 3), но 1 - не символ, не идентификатор функции. Как мне сказать Схеме, что я не хочу выполнять этот список, а просто хочу его передать?

Для этого придумали специальную форму quote: если я напишу (quote (1 2 3)), то результатом выполнения этого списка будет (1 2 3). Ошибки не будет, потому что quote - не обычная функция, а специальная форма, и не обязана выполнить свой аргумент (1 2 3), а может делать с ним что хочет. Она его просто возвращает. Так что мне надо написать:
(car (quote (1 2 3))), и это даст нужный результат: 1. Но так каждый раз писать очень неудобно, и поэтому придумали сокращение: вместо (quote (1 2 3)) можно написать '(1 2 3). Символ апострофа заменяет вызов quote; по сути дела он абсолютно идентичен этому вызову, и просто является синтаксическим сокращением для программиста. Но это действительно удобно: (car '(1 2 3)) написать легко. Так что каждый раз, как вы видите ' перед каким-то значением в Схеме, это означает: "процитируй" это значение, т.е. дай в качестве результата именно его, не пытаясь его выполнить.
Чаще всего это будет стоять перед списками. Еще один пример, когда удобно - перед символом. Значение foo при попытке выполнения пытается посмотреть, что записано в переменной foo, и вернуть это; а 'foo просто возвращает символ foo, как значение (переменной такой может и не быть вообще).

----------------------braindump---------------------------
[не связано напрямую с кодом, к-й я сейчас буду писать, но эти размышления вызваны им]

На данный момент я не очень понимаю, нужен ли мне еще один layer of indirection между переменными и значениями. Что-то я запутался тут. Значит так. У меня будет один layer of indirection - собственно bindings. Это понятно. Пусть у меня есть переменная y, и предположим для простоты, что она в top-level environment, ничем не скрыта итд. Тогда есть binding y->i, где i некий индекс, и в cells[i] лежит значение. Так я думал до сих пор, что будет. Используя язык стандарта R5RS, i это "location", а cells[i] "value".

Теперь предположим, что в cells[i] лежит 4, а я делаю (set! y "123"). Я не могу, конечно, взять и записать "123" в cells[i], где было до этого 4, потому что "123" занимает больше клеток, и они уже заняты другими значениями. Я предполагал до сих пор, что я сделаю следующее: создам новое значение "123" по какому-то адресу j, и изменю binding y->i на y->j. Строго говоря, это меняет значение "location". Но мне казалось, что это не мешает ничему. Теперь я как-то не уверен: что если какие-то eq? equal? итд. ожидают чего-то другого? В принципе я могу сделать по-другому. Я могу сделать так, чтобы y->k, где k это клетка нового типа T_PTR, указывающая на i - т.е. еще один layer of indirection. Теперь, если я делаю (set! y "123"), я меняю k->i на k->j, а binding y->k остается без изменений - "location" сохраняется. Но правильно ли будет так сделать?

У меня это как-то переплелось с путаницей насчет того, как собственно передаются аргументы функциям - по значению или по ссылке (by value or by reference). Ведь если по значению, то получается, что вызов (some-string-function string) всегда создаст новую копию string, чтобы ее передать, а если строки длинные, выходит, что работа с ними очень неэффективная. И зачем тогда нужна стандартная функция (string-set! str ind char), которая меняет строку str по индексу ind на знак char? Если я сделаю string-set! внутри функции foo, получившей str в виде аргумента, изменится ли то, что передал вызвавший foo, в его собственной строке, к-ю он передал для str?

Меня на самом деле смущает то, что я не могу найти ответ на эти вопросы в спецификации R5RS. Мне как-то очень нравилась ее краткость, а теперь что-то разонравилась. Или она специально оставляет это несказанным? OK, нашел одно упоминание в первой главе: "Arguments to Scheme procedures are always passed by value", но как-то это очень нелогично выглядит в свете существования мутирующих string-set! и set-car!. OK, устанавливаю plt-scheme, чтобы запустить его REPL и попробовать. Понадеюсь на то, что он хорошо воплощает R5RS.

Ага. Работа с plt-r5rs многое прояснила. Передача аргументов действительно по ссылке, а не по значению, совершенно точно в случае строк и пар (для остального это наверное не очень важно). Если определить функцию foo которая делает string-set! своему аргументу, и вызвать эту функцию (foo y), то значение y меняется. То же самое, если foo делает set-car! своему аргументу. А вот если foo делает set! своему аргументу, то на исходное значение это никак не влияет. То же самое происходит, если вместо функции просто сделать (define z y), и менять z: если с помощью set!, то y не меняется, если с помощью set-car!, string-set!, то меняется. Черт побери, почему в спеке нельзя было нормально это объяснить? Ведь я три раза его просмотрел именно в поисках этой информации.

OK, кажется, я распутал себя. Surprise surprise! мой первоначальный подход был верен. Пусть (set! y "123") меняет binding y->i на y->j, это правильно; если другая переменная z тоже указывала на cells[i], в результате (define z y) или передачи y функции с аргументом z, то значение z не изменится, и это правильно. С другой стороны, string-set! и set-car! не меняют y->i, а идут внутрь значения cells[i] и шуруют в нем; если z тоже указывала на cells[i], она получает изменения. И это тоже правильно, если верить plt-scheme - в стандарте я не могу это найти. Функции при этом могут все свои аргументы получать by reference в том смысле, что они получают индекс клетки i, и вставляют его в свои bindings. Дополнительный layer of indirection, кажется, не нужен вообще. Если я где-то неправ и вы это понимаете, поправьте меня.

-------------------code--------------------------
Меж тем пока что я хочу по-простому одну глобальную таблицу bindings, от символа к значению (к индексу значения). Потом я все это переделаю для поддержки lexical scope и closures, поэтому мне нужно что-то невыносимо тривиально и простое, чтоб не жалко было выкинуть. Возьму-ка я hash_map<string, uint32_t> из C++; вообще-то я хочу весь проект написать на C, но это временно.
[file symbols.cc] extern "C" uint32_t get_symbol(const char *name, int len); extern "C" void set_symbol(const char *name, int len, uint32_t val);
hash_map, говорите? Нет, прощай, дорогой hash_map, вперед, к светлым новым стандартам C++0x!
#include <tr1/unordered_map> tr1::unordered_map<string, uint32_t> table;
Я передаю этим функциям имя символа в виде указателя+длины, потому что так оно у меня хранится в памяти, без заканчивающего нуля. Надо как-то создать C++-ную строку из этого. К сожалению, у string нет подходящего конструктора, зато есть оператор присваивания. Вот вспомогательная функция и set_symbol:
string sym_name(const char* name, int len) { string str; str.assign(name, len); return str; } void set_symbol(const char *name, int len, uint32_t val) { table[sym_name(name, len)] = val; }
Гм, а как, интересно, get_symbol() сообщит мне, что не нашла символ? Есть два простых варианта: либо специальное значение 0, либо пусть вернет boolean, и дополнительный аргумент-указатель, куда посадить само значение. Однако у меня индекс 0 не специальный, он используется в cells[]! Требование простоты кода важнее: пусть get_symbol() возвращает 0, а первую клетку мы для такого случая зарезервируем; может, еще где пригодится:
uint64_t cells[MAX_CELLS]; /* start from 1, as index 0 is reserved for errors or invalid values */ uint32_t next_cell = 1;
OK, теперь пора разобраться с именами символов, которые мы будем передавать get_symbol(). В прошлый раз я их запихал по одному знаку в клетку, надо сжать. Ой, внезапно до меня доходит очевидное: ведь если строка/символ сидят по адресу cells[i], то их байты можно просто писать начиная с cells[i+1] как обычные байты, не надо никакого сложного кодирования (я во время прошлого припадка представлял себе отчего-то, что надо будет в цикле сдвигать на 0, 8, 16, 24, ... бит и вставлять в нужное место очередной клетки). Ха, функция pack_string() сильно упрощается. Остается решить вот что: в самой первой клетке строки/символа cells[i] есть неиспользованные верхние 32 бита, втискивать ли туда тоже начало строки? Кажется, мы благополучно приземлились на дилемму little endian/big endian: если архитектура little endian, то эти верхние 32 бита будут сразу перед следующей клеткой, и все просто; если big endian, то разрыв. Варианты: а) предположить little-endian и задокументировать это, все равно "почти все такие"; б) в случае big-endian хранить все флаги, тип итп. в /верхних/ 32 битах, а не нижних, создать набор макросов, к-й это скрывает; такое веселое вполне извращение! но в) все это слишком сложно, пожертвуем этими 32 битами и начнем со следующей клетки. Выбираю в).
#define SYMBOL_NAME(i) (char *)(cells+i+1) #define SYMBOL_LEN(i) ((cells[i] & 0xFFFFFFFF) >> 16) /* helper func to store a string into cells */ uint32_t pack_string(char *str, char *end, int type) { uint32_t len = (end-str+7)/8; CHECK_CELLS(len); uint32_t index = next_cell; uint64_t value = type | (uint64_t)len << 16; cells[next_cell++] = value; strncpy(SYMBOL_NAME(index), str, end-str); return index; }
Стоп, проблема: мне-то надо знать длину строки в байтах, а это сохраняет только в клетках! a) Варианты: a) можно в битах 31-15 вместо len хранить end-str, т.е. длину в байтах; это будет отличать строку/символ от других типов, и во время сборки мусора надо будет об этом не забыть. Еще это снижает максимальную длину строки до 64k, в то время как я рассчитывал на 512k. б) можно отдельно в битах 47-32 записать длину в байтах, благо я похерил планы использовать верхние 32 бита для чего-то стоящего в этих типах. Выбираю б). Соответственно меняю
#define SYMBOL_LEN(i) (cells[i] >> 32) ... uint64_t value = type | (uint64_t)len << 16 | (uint64_t)(end-str) << 32;
Кроме того, меняю соответствующий код в dump_value(). Запуск и проверка обнаруживают, что я забыл сделать "next_cell+=len" в функции выше; хорошо, что я в REPLе вставил распечатку текущего кол-ва клеток в подсказке командной строки.

OK, что дальше. Кажется, пришла пора писать функцию выполнения eval()! Мой первый eval() будет очень примитивный (улавливается закономерность?), потом я его переделаю. Списки он будет выполнять, вызывая себя рекурсивно; это очень просто написать, но не поддерживает хвостовую рекурсию, обязательную в Схеме. Что это такое и как ее поддержать, обсудим позже. Специальные формы define и set! будут специальными случаями в коде eval(), а вот встроенные функции типа + и car я хочу сделать уже общим способом.

eval() принимает индекс значения для выполнения и возвращает индекс результата. Вот начало функции, показывающее, что делать для примитивных значений, для списка, и специальный случай "define" внутри списка.
uint32_t eval(uint32_t index) { uint32_t sym, val, car, cdr; switch(TYPE(index)) { case T_EMPTY: case T_INT32: case T_BOOL: case T_STR: return index; case T_SYM: val = get_symbol(SYMBOL_NAME(index), SYMBOL_LEN(index)); if (val == 0) die("undefined symbol"); return val; case T_PAIR: car = CAR(index); cdr = CDR(index); if (TYPE(car) != T_SYM) die("car of eval'd pair is not a symbol"); if (TYPE(cdr) != T_PAIR) die("cdr of eval'd pair is not a pair"); if (strncmp(SYMBOL_NAME(car), "define", 6) == 0) { /* the only allowed syntax here is (define symbol value) */ sym = CAR(cdr); if (TYPE(sym) != T_SYM) die ("define followed by non-symbol"); if (TYPE(CDR(cdr)) != T_PAIR) die ("define symbol . smth"); val = CAR(CDR(cdr)); if (TYPE(CDR(CDR(cdr))) != T_EMPTY) die ("define symbol smth ???"); set_symbol(SYMBOL_NAME(sym), SYMBOL_LEN(sym), val); return val; /* TODO: actually undefined */ } break;
Случай set! почти идентичен этому, только проверяет, что символ уже существует; собственно, сделаю для них один код. Форма "quote" тоже очень простая - проверяет, что ей передали ровно одно значение, и возвращает его.

Пока хватит специальных форм, займемся функциями. Для функций мы заведем новый вид значения T_FUNC. Что он должен хранить - отдельный интересный вопрос. Если это функция, определенная программистом - то список параметров и собственно тело функции, т.е. два значения (тело функции - просто очередное значение). Кроме того, для поддержки замыканий (closures) надо будет еще добавить... но как именно это устроить, я еще не решил окончательно. Ну а если функция встроенная? Это отдельный тип T_BLTIN или тот же T_FUNC но с дополнительным флажком, который говорит "я встроенная функция"? Мне кажется, лучше с флажком, бит у нас еще много.
#define T_FUNC 7 /* function, a.k.a. closure */ #define BLTIN_MASK 16
Договоримся, что встроенные функции используют одну дополнительную клетку, в которой по-простому лежит указатель на C-функцию. Эта функция принимает и возвращает uint32_t, индексы значений, используя 0 для того, чтобы вернуть ошибку.

Встроенные функции регистрируют себя с помощью register_builtin():
typedef uint32_t (*builtin_t)(uint32_t); void register_builtin(char *name, builtin_t func) { CHECK_CELLS(2); uint64_t value = T_FUNC | BLTIN_MASK; uint32_t index = next_cell; cells[next_cell++] = value; cells[next_cell++] = (uint64_t)func; set_symbol(name, strlen(name), index); }
Для начала нам хватит car, cdr, и функция регистрации всех встроенных, которую вызовем из main(). Плюс кусочек кода в dump_value(), печатающий лаконичное *func* при встрече с функцией.

Встроенные функции вскоре переедут в свой собственный файл, подозреваю.
uint32_t car(uint32_t index) { if (TYPE(index) != T_PAIR) return 0; return CAR(index); } uint32_t cdr(uint32_t index) { if (TYPE(index) != T_PAIR) return 0; return CDR(index); } void register_builtins(void) { register_builtin("car", car); register_builtin("cdr", cdr); }
Возвращаемся в eval(). Предположим, мы посмотрели, на что ссылается символ, и увидели, что это функция, и даже встроенная, потому что другие мы запускать не умеем. Теперь нам надо выполнить все-все-все аргументы, которые нам даны в виде списка, и построить новый список - их значений. Как это сделать? Обойдемся без рекурсии и постулируем какой-то разумный предел - скажем, максимум 256 аргументов в одном вызове звучит нормально? Пусть одна вспомогательная функция пройдется по всем аргументам, выполнит их, и заполнит временный массив (индексов) значений, а потом с помощью другой вспомогательной функции make_pair() мы сделаем из него список.
/* special forms end here. Now check if it's a function. */ val = get_symbol(SYMBOL_NAME(car), SYMBOL_LEN(car)); if (val == 0) die("undefined symbol as func name"); if (TYPE(val) != T_FUNC) die("first element in list not a function"); if (cells[val] & BLTIN_MASK == 0) die("can only call builtins for now"); uint32_t args[MAX_ARGS]; uint32_t num_args; if (!eval_args(cdr, args, &num_args)) return 0; uint32_t list = make_list(args, num_args); builtin_t func = (builtin_t)cells[val+1]; /* well, there you go */ return func(list);
Опускаю код eval_args() и make_list() тут, см. исходники.

Проверка этого кода показывает, что в car() и cdr() выше есть баг, хоть они и кажутся очень простыми. Дело в том, что они получают напр. не (1 2 3), если вызвать (car (quote (1 2 3)), а ((1 2 3)), потому что они получают список всех своих аргументов: в данном случае аргумент один, но список все равно есть. Вот например код исправленной car:
uint32_t car(uint32_t index) { /* check that we have just one argument (the list is of size 1) */ if (TYPE(index) != T_PAIR || TYPE(CDR(index)) != T_EMPTY) return 0; /* pass to this argument - first CAR - and return its first element */ return CAR(CAR(index)); }
Заодно добавляю встроенную функцию +, которая работает только с 32-битными числами. Она умеет суммировать сколько угодно аргументов. Ее отлаживание обнаруживает баг в коде прошлого припадка, читающем специальные идентификаторы +,-,... . Исправляю.

Последнее, что хочется успеть сегодня - синтаксис '(1 2 3) вместо (quote (1 2 3)). Это просто. В случае, когда мы видим апостроф, мы просто читаем следующее значение, и руками составляем его в список вместе с символом quote. Вот код нового куска в read_value() (кроме этого, был небольшой рефакторинг make_list(), чтобы он сам () в конце добавлял для простоты):
if (*str == '\'') { str++; uint32_t indices[2]; int res = read_value(&str, &indices[1], 0); if (!res) return 0; char *quote = "quote"; indices[0] = pack_string(quote, quote+5, T_SYM); *pindex = make_list(indices, 2); *pstr = str; return 1; }


Проверка всего, что понаписано!
$ ./sketch 7 cells> (+ 3 5) 8 24 cells> (+ 3 10 -14) -1 46 cells> (car (quote (1 2 3))) 1 73 cells> (car '("foo" "bar")) "foo" 99 cells> (cdr '(1 2 3)) (2 3) 126 cells> (define foo 14) 14 138 cells> (+ foo -14) 0 156 cells> (set! foo 20) 20 168 cells> (+ foo -14) 6 186 cells> (set! foo "foofoofoo") "foofoofoo" 200 cells> (+ foo -14) eval failed. 217 cells>

На сегодня все. Проект вырос до 420 строк кода.
------------------------------конец второго припадка----------------------------------

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

код второго припадка (зафиксирован)
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.
  • 47 comments