Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

набросок, припадок четвертый, ч. 2

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

(продолжение этой записи)

-----------------------------------coding--------------------

Мне нужна хэш-таблица для каждой среды. Поправка: на самом деле мне нужна структура, которая умеет две вещи. Вернуть номер символа; нумерация начинается с 1, если символ не найден, он автоматически добавляется с новым номером и номер возвращается. И вернуть наибольший номер до сих пор - чтобы знать, сколько места отвести для среды. Я воспользуюсь для этого все той же хэш-таблицей из C++ в symbols.cc. Я был уверен, что в этом припадке полностью от нее избавлюсь, но вышло по-другому. Тем не менее, я спрячу всю C++-ность, сделаю интерфейс очень C-шным:

void *new_symbol_table(); void delete_symbol_table(void *table); uint32_t new_symbol(void *table, const char *name, int len); uint32_t num_symbols(void *table);
Вот новая структура в symbols.cc, и для примера самая сложная из этих четырех функций:
struct symbol_table { uint32_t next; tr1::unordered_map<string, uint32_t> table; }; uint32_t new_symbol(void *table, const char *name, int len) { string str = sym_name(name, len); symbol_table *st = (symbol_table *)table; if (st->table.find(str) != st->table.end()) return st->table[str]; st->table[str] = st->next++; return st->next-1; }
Среда должна хранить N слотов для индексов значений, а также ссылку на предыдущую среду. Больше, кажется, она ничего не должна хранить (я сначала думал, что должна что-то типа количества аргументов функции итд., но все это можно держать в T_FUNC, который у нас наготове, когда функция вызывается). Значит, среда может быть просто вектором размером N+1. Я даже не думаю, что нужно для нее заводить новый тип T_ENV. Пусть просто первый элемент вектора, номер 0, будет всегда ссылкой на предыдущую среду. А начиная с элементов номер 1 и далее будут слоты для переменных. Для этого пусть у нас код в symbols.cc начинает нумерацию слотов с 1, а не с 0. Нам пригодится вспомогательная функция для создания пустого вектора данной величины; заодно существующий код создания вектора (на данный момент в read_vector() и встроенной list->vector) может начать ее использовать.
uint32_t make_vector(uint32_t size, int zero_it) { uint32_t len = (size+1)/2; /* num of extra cells required */ CHECK_CELLS(len+1); uint32_t index = next_cell; uint64_t value = T_VECT | (uint64_t)len << 16 | (uint64_t)(size) << 32; cells[next_cell++] = value; if (zero_it) memset(VECTOR_START(index), 0, size*sizeof(uint32_t)); next_cell += len; return index; } uint32_t make_env(uint32_t size, uint32_t prev) { uint32_t env = make_vector(size+1, 1); *VECTOR_START(env) = prev; return env; }
Мне нужен новый тип данных для "ссылок на переменные". Он вполне умещается в одну клетку, хранит два числа: номер слота и "сколько уровней вверх". Считывать его никогда не надо, так что в read_value() не надо ничего добавлять, только в dump_value().
#define T_VAR 9 /* reference to a lexical variable */ #define VAR_FRAME(i) (uint32_t)((cells[i] >> 32) & 0xFFFF) #define VAR_SLOT(i) (uint32_t)((cells[i] >> 32) >> 16) uint32_t store_var(uint32_t slot, uint32_t frame) { uint64_t value = T_VAR; CHECK_CELLS(1); uint32_t index = next_cell; cells[next_cell++] = value | ((uint64_t)frame << 32) | (uint64_t)slot << 48; return index; } ....in dump_value()... case T_VAR: printf("#<var:%u,%u>", VAR_SLOT(index), VAR_FRAME(index)); break;
Кажется, можно писать prepare(). Как и eval(), она получает и возвращает значение, и рекурсивно вызывает себя. Когда она работает над списком, то не стесняется менять его содержимое - я предполагаю, что это просто исходный код, прочитанный с помощью read_value(), никому больше не нужный. Только с символами и списками надо что-то делать, во всех остальных случаях возвращаемся сразу - вот скелет функции, и как мы будем ее вызывать:
uint32_t prepare(uint32_t index) { switch(TYPE(index)) { case T_SYM: break; case T_PAIR: break; default: break; } return index; } ... in main() ... int can_read = read_value(&str, &index, 0); if (can_read) { uint32_t prepared = prepare(index); if (prepared) { uint32_t res = eval(prepared); if (res) { dump_value(res, 0); printf("\n"); } else printf("eval failed.\n"); } else printf("prepare failed.\n"); } else printf("failed reading at: %s\n", str);

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

Пусть за меня список символьных таблиц хранит symbols.cc; я только буду говорить ему иногда: добавь новую таблицу, или удали последнюю - когда начинаю/кончаю работать с лямбдой. Мне нужны две операции: найти символ поиском изнутри/снаружи, и вернуть его номер в таблице и номер самой таблицы; и добавить символ в самую новую таблицу. Да, и еще вернуть размер самой новой таблицы. Как-то так (интерфейс, структуры и одна функция для примера):
int find_symbol(const char *name, int len, uint32_t *slot, uint32_t *frame); void add_symbol(const char *name, int len, uint32_t *slot, uint32_t *frame); void add_symbol_table(); void delete_symbol_table(); uint32_t latest_table_size(); struct symbol_table { uint32_t next; tr1::unordered_map<string, uint32_t> table; }; list<symbol_table> tables; int find_symbol(const char *name, int len, uint32_t *slot, uint32_t *frame) { string str = sym_name(name, len); int pos = 0; for (list<symbol_table>::iterator it = tables.begin(); it != tables.end(); ++it, ++pos) { if (it->table.find(str) != it->table.end()) { *slot = it->table[str]; *frame = pos; return 1; } } return 0; }
Теперь ясно, что делать в prepare(), когда мы видим символ:
switch(TYPE(index)) { case T_SYM: res = find_symbol(STR_START(index), STR_LEN(index), &slot, &frame); if (res) { uint32_t var = store_var(slot, frame); return var; } else { printf("Undefined variable: "); dump_value(index, 0); return 0; } break;
Когда мы видим список, то меня интересуют на данный момент следующие три специальных случая: define, lambda и quote. Если мы не видим ни одного из этих специальных случаев, то мы просто рекурсивно проходимся по всем членам списка, включая "функцию" (которая может быть и специальной формой вроде set! или if, нам это не мешает тут).

В случае quote мы просто игнорируем то, что дальше - ничего заменять там не надо, в остальном eval() разберется. Позже надо будет добавить что-то посложнее для поддержки так называемого quasi-quoting, но пока не надо.

Когда мы видим lambda, то добавляем новую таблицу символов; создаем T_FUNC; добавляем все имена аргументов в таблицу символов; проходимся рекурсивно по телу; дописываем в T_FUNC количество слотов в новой таблице, удаляем ее и возвращаемся; кажется, так. Тут надо объяснить, почему не взять это количество слотов просто как число аргументов, зачем вообще нужна эта latest_table_size(). Во-первых, я хочу оставить возможность все-таки переменные let сотоварищи хранить в окружающей лямбде, а не отдельную среду делать. На всякий случай. Но главное - стандарт заставляет меня это сделать для вызовов define внутри тела функции. Такие вызовы считаются принадлежащими всей функции, и их переменные имеют видимость во всей функции:
(lambda (a b) (define x (+ y a)) (define y 4) (...) )

Определение x может уже пользоваться y, хотя определения y еще нет. Значит, мне так или иначе надо уметь добавлять новые слоты уже после того, как я прошелся по списку аргументов.

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

Для того, чтобы сделать эту поддержку отложенных define, prepare() получает дополнительный аргумент uint32_t *deferred_define. Если он NULL, то ничего специального для тела define делать не надо, а просто идти по нему рекурсивно. Если это работающий указатель, то в него запишем индекс тела define, а проходить его не будем. Вспомогательная функция для лямбды будет с помощью этого собирать ссылки на отложенные define у своих рекурсивных вызовов.
case T_PAIR: func = CAR(index); args = CDR(index); if (!LIST_LIKE(args)) { printf("A dot pair but not a list in prepare()\n"); return 0; }; if (TYPE(func) == T_SYM) { if (IS_SYMBOL(func, "quote")) return index; if (IS_SYMBOL(func, "define")) { if (!check_list(args, 2, 1)) die("bad define/set! syntax"); sym = CAR(args); if (TYPE(sym) != T_SYM) die("bad define syntax in prepare"); add_symbol(STR_START(sym), STR_LEN(sym), &slot, &frame); uint32_t var = store_var(slot, frame); /* replace the symbol with the variable */ SET_CAR(args, var); if (deferred_define) { *deferred_define = CDR(args); /* (val) not val, deliberately. */ return 1; } else { if (prepare_list(CDR(args)) == 0) return 0; else return index; } } if (IS_SYMBOL(func, "lambda")) { /* Easier to add/delete symbol tables here than chase exit points in prepare_lambda(). */ add_symbol_table(); uint32_t res = prepare_lambda(args); delete_symbol_table(); return res; } } /* The usual case: resolve the list recursively. */ return prepare_list(index); break;
Две вспомогательных функции: prepare_list() и prepare_lambda(). Первая тривиальная, просто проходится по списку и рекурсивно вызывает prepare(). Единственное, ради чего стоило выделять ее в отдельную функцию - то, что если prepare() возвращает что-то изменившееся, то она это подставляет прямо в список, который обрабатывает. См. строчку с SET_CAR в ее коде. prepare_lambda() - самая сложная из новых функций, "мясо" новой функциональности prepare(). Вот ее скелет:
uint32_t prepare_lambda(uint32_t args) { ... /* Basic argument correctness. */ ... /* Walk the argument list and create slots. TODO: check uniqueness */ int args_number = length_list(args_list); while(args_list != C_EMPTY) { uint32_t sym = CAR(args_list); if (TYPE(sym) != T_SYM) die ("not a symbol in lambda arg list"); add_symbol(STR_START(sym), STR_LEN(sym), &slot, &frame); args_list = CDR(args_list); } /* Go over the body and walk it recursively, deferring defines. */ uint32_t body = CDR(args); while (body != C_EMPTY) { uint32_t statement = CAR(body); defines[defines_curr] = 0; uint32_t res = prepare(statement, &defines[defines_curr]); ... } /* Go over deferred define bodies, if any. */ ... /* Create a T_FUNC, record the number of slots. */ CHECK_CELLS(2); uint32_t index = next_cell; uint64_t value = T_FUNC; uint32_t count_vars = latest_table_size(); value |= (uint64_t)count_vars << 32; value |= (uint64_t)args_number << 48; cells[next_cell++] = value; // Higher 32-bit will be an env pointer in closures. */ cells[next_cell++] = (uint64_t)CDR(args); return index; }
Тут надо было решить, как представлять T_FUNC. У нас теперь есть три шага в процессе обработки лямбды. Во-первых, prepare_lambda(), главная задача которой - заменить символы в теле функции на "ссылки на переменные" T_VAR. Во-вторых, еще не написанный код в eval(), который собственно "выполняет" лямбду и создает на ее основе новое замыкание, привязанное к текущей среде. В-третьих, код выполнения такого замыкания, тоже не написанный, который создает новую среду, инициализирует аргументы, и выполняет тело. "Интерфейс" между этими тремя шагами мы можем организовать на наше усмотрение. Важно, чтобы от первого шага ко второму передавалась такая информация, как число слотов и аргументов функции (это не одно и то же, т.к. define внутри функции создает новые слоты, отличные от ее аргументов). И от второго к третьему - то же самое плюс ссылка на предыдущую среду.

Можно было оставить текст функции почти как есть после prepare_lambda, т.е. оставить список, начинающийся с символа "lambda" итд. - только вместо списка аргументов подставить нужную информацию о числе слотов и аргументов, и обработать тело. А уже во время "выполнения" lambda создать T_FUNC. Я решил сделать по-другому: значение T_FUNC может означать как и приготовленную "лямбду", которую еще не выполнили и не создали замыкание, так и созданное замыкание. Вторая клетка этого значения содержит ссылку на тело функции и ссылку на предыдущую среду; если эта последняя ноль, то это еще не замыкание, а только "приготовленная лямбда". Ее и создает код в конце prepare_lambda() выше.

Вот как выглядят результаты prepare() - я изменил главный цикл, чтобы он вызывал только prepare(), без eval(), и добавил нетривиальную распечатку функции в dump_value() - на данный момент. Наверняка еще есть какие-то баги, но основная функциональность, кажется, работает:
> sketch 59 cells> (define top-level 6) prepared: (define #<var:28,0> 6) 72 cells> (lambda () 5) prepared: *func:0 vars, 0 args, body:(5)* 83 cells> (lambda (arg1) arg1) prepared: *func:1 vars, 1 args, body:(#<var:1,0>)* 100 cells> (lambda (arg1 arg2) (define in-func 15)) prepared: *func:3 vars, 2 args, body:((define #<var:3,0> 15))* 130 cells> (lambda (arg1 arg2) (define in-func 15) '(arg1 in-func)) prepared: *func:3 vars, 2 args, body:((define #<var:3,0> 15) (quote (arg1 in-func)))* 176 cells> (lambda (arg1 arg2) (define in-func 15) (list arg1 in-func)) prepared: *func:3 vars, 2 args, body:((define #<var:3,0> 15) (#<var:15,1> #<var:1,0> #<var:3,0>))*
Причина, по которой нормально обработался символ list в последней строке - то, что я добавил в регистрацию встроенных функций один вызов add_symbol(), ничего по сути не меняя; т.е. они есть в новой символьной таблице высшего уровня, но настоящей "глобальной среды" еще нет.

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

Во-первых, есть неприятная сложность с специальными формами типа set! и if - т.е. не quote,define,lambda, которыми я теперь занимаюсь в prepare(), а всеми остальными. Дело в том, что в отличие от встроенных функций их нет в символьной таблице, и поэтому код рекурсивного обхода списка в prepare() не находит их и возвращает ошибку - он думает, что они неопределенные функции. Я мог бы добавить их как псевдо-встроенные функции, только чтобы prepare() сработала - но как мне это поможет, если prepare заменит 'set!' на #<var:15,0>? Я ведь все равно пока что хочу эти специальные формы специально обрабатывать в eval(), а для этого мне надо их там распознать. Я не хочу передавать их исполнение встроенным функциям, даже если обозначить специально, что они не должны вычислять свои аргументы - потому что я опасаюсь, что это помешает мне сделать хвостовую рекурсию.

На данный момент я не вижу иного выхода, чем специально проверить их имена в prepare() и тогда проходить рекурсивно только по их аргументам. Это уродливо и громоздко, потому что и prepare() и eval() смотрят теперь специально на все эти имена: не только define/quote, но и остальные. Но пока я не вижу, как это лучше сделать. Надеюсь, что когда будет хвостовая рекурсия и макросы, это все можно будет упростить.
/* Special forms that don't exist in the symbol table. TODO: simplify. */ if (IS_SYMBOL(func, "set!") || IS_SYMBOL(func, "if")) { /* only walk the args */ uint32_t res = prepare_list(args); if (res == 0) return 0; return index; }
Еще я заметил, что у меня есть баг в обработке define: если я попробую определить переменную, которая уже есть, это создает новую. На самом деле это должно создавать новую, только если в текущей символьной таблице нет уже такой. (define a 3)(define a 4) должно создать один слот, а не два - неважно, на глобальном уровне или внутри функции. Для этого мой интерфейс с символами не заточен, и нужна другая функция find... хотя нет, почему же? Просто пусть add_symbol(), которая всегда добавляет в текущую таблицу, не добавляет, если там уже это есть. Это оказалось простой поправкой.

Во-вторых, надо создать глобальную среду и зарегистрировать в ней все встроенные функции. Глобальная среда отличается от любой другой тем, что она продолжает расти - во время ее создания ее размер неизвестен. Я отведу для нее 10 тысяч слотов, этого должно надолго хватить, и пусть программа умрет, если станет больше - но в будущем нужно будет придумать, как ее можно в таком случае расширить.
...in common.h.... extern uint32_t toplevel_env; ...in sketch.c... uint32_t toplevel_env = 0; void store_env(uint32_t env, uint32_t slot, uint32_t value) { if (slot > VECTOR_LEN(env)) { /* TODO: do something smart for the toplevel environment */ die("environment out of range"); } VECTOR_START(env)[slot] = value; } ... in main()... toplevel_env = make_env(10000, 1); ... in builtins.c, register_builtin().... set_symbol(name, strlen(name), index); uint32_t slot, frame; add_symbol(name, strlen(name), &slot, &frame); store_env(toplevel_env, slot, index);
OK, теперь, кажется, можно менять eval().

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

eval() теперь не ожидает увидеть символ: все символы должны были быть разрешены в ссылки на переменные в prepare() (исключения - имена специальных форм и все, что спрятано за quote). Зато ей нужно уметь разбираться с T_VAR:
case T_SYM: printf("eval: should not get a naked symbol"); return 0; case T_VAR: slot = VAR_SLOT(index); frame = VAR_FRAME(index); while (frame > 0) { if (env == 0) die("bad frame or env in eval"); env = VECTOR_START(env)[0]; frame--; } if (env == 0) die("bad frame or env in eval"); return VECTOR_START(env)[slot];


if и quote продолжают работать точно так же, как раньше. define и set! становятся полными близнецами, потому что работу define по определению нового символа теперь делает prepare(). Код обработки "lambda" полностью удаляется, eval() никогда не должен видеть определение lambda. Создание функции-замыкания, или иными словами выполнение "lambda", а также вызов функции, теперь происходит, когда первым элементом списка оказывается T_FUNC; эти случаи различаются по тому, "прикреплен" этот T_FUNC к какой-то среде или нет.

Нет, поправка (после долгой отладки): я перепутал. Выполнение "lambda" - это случай, когда eval получает чистый T_FUNC, не в списке. А выполнение функции - когда T_FUNC первый элемент в списке. Уф.
case T_FUNC: /* Executing a lambda form. */ ... some error-checking... /* Copy the T_FUNC and set its environment. */ CHECK_CELLS(2); uint32_t new_index = next_cell; cells[next_cell++] = cells[index]; cells[next_cell++] = cells[index+1]; SET_CAR(new_index, env); return new_index;


Новый код вызова функции:
/* evaluate arguments and call the function */ uint32_t num_args; if (!eval_args(args, env, arg_array, &num_args)) return 0; if (cells[val] & BLTIN_MASK) { /* builtin function */ ... skipped ... } else { /* lambda function */ uint32_t body = FUNC_BODY(val); if (num_args != FUNC_ARGCOUNT(val)) { printf("eval: number of args mismatch.\n"); return 0; } /* Create a new environment, tied to the one stored in T_FUNC. */ /* If we did our job right, zero_it in the call to make_env() is not necessary. */ uint32_t new_env = make_env(FUNC_VARCOUNT(val), 0); VECTOR_START(new_env)[0] = FUNC_ENV(val); for (uint32_t i = 0; i < num_args; i++) { store_env(new_env, i+1, arg_array[i]); } uint32_t retval = C_UNSPEC; while (body != C_EMPTY) { retval = eval(CAR(body), new_env); if (retval == 0) return 0; body = CDR(body); } return retval; }
Все. Наверняка тут еще остались баги, но на сегодня более чем хватит. Осталось проверить, что все это как-то работает.

Поскольку меня достало вводить все в одну строку, я делаю небольшой рефакторинг ридера read_value() и главной функции main(). Пусть read_value() возвращает не только 1/0, но еще -1 в том случае, если строка кончилась, но если бы она продолжилась, то функция могла бы продолжать читать. Например, если read_value() встречает что-то, что никак не может понять, пусть возвращает 0, как и раньше; но если встречает конец строки в середине списка, пусть возвращает -1. Тогда main() пытается прочитать еще одну строку, добавляет ее к буферу, и заново пытается прочесть весь буфер (это немного неэффективно, но полагаю, что на практике окажется несущественно...

Хотя нет. Я уже написал весь этот код и отладил, но передумал. Это безумие - читать функцию из 20 строк так: сначала одну, потом две, потом три итд., и каждый раз создавать все промежуточные объекты в ридере. Надо это сделать полегче. Пусть будет функция in_flight(), которая тупо считает скобки, учитывает кавычки, и говорит, находимся ли мы внутри списка.
/* 1 if we seem to be inside a list, based on parens parity */ int in_flight(char *str) { int paren_level = 0; int in_string = 0; while (*str) { if (*str == '(' && !in_string) paren_level++; if (*str == ')' && !in_string) { if (paren_level == 0) return 0; else paren_level --; } if (*str == '#' && *(str+1) == '\\' && !in_string) str+=2; if (*str == '\\' && in_string) str++; if (*str == '"') in_string = !in_string; str++; } return (paren_level > 0 || in_string); }

Попробую написать рекурсивный факториал, использующий локальную переменную:
$ ./sketch 5061 cells> (define fact (lambda (n) ... (define prev (fact (+ n -1))) ... (* prev n) ... )) 5136 cells> (fact 3) Segmentation fault

Отлично! :)

... Проверка в дебаггере показывает, что переполняется стек. Ха, я же забыл остановить его остановить на нуле! Вот он и побежал...

OK, исправим это так:
5421 cells> (define fact (lambda (n) ... (define prev (if (eqv? n 1) 1 (fact (+ n -1)))) ... (* n prev) ... )) 5520 cells> (fact 3) 6 5574 cells> (fact 10) 3628800

Работает! Теперь проверю работу замыканий на примере функции count-maker выше. Поскольку у меня нет поддержки let, ее текст будет выглядеть довольно извращенным. Вместо (let ((x 0)) smth) у меня будет ((lambda (x) smth) 0), и в итоге получатся три вложенные лямбды.
5138 cells> (define count-maker (lambda () ... ((lambda(n) ... (lambda () (set! n (+ n 1)) n)) 0) ... )) 5234 cells> (define c1 (count-maker)) 5259 cells> (c1) 1 5271 cells> (c1) 2 5283 cells> (c1) 3 5295 cells> (define c2 (count-maker)) 5320 cells> (c2) 1 5332 cells> (c1) 4 5344 cells> (c2) 2

Работает!

Напоследок я удаляю ненужные теперь функции для работы с старой глобальной таблицей символов get_symbol() и set_symbol(). Если я все правильно сделал, их теперь никто не вызывает, и действительно, их удаление проходит незамеченным для остального кода.

Размер проекта: 1240 строк.
------------------------послесловие------------------------
Код проекта (меняется по мере развития)

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

Я пока не решил, чем будет заниматься следующий припадок. Возможно, поддержкой хвостовой рекурсии, а возможно, поддержкой let, do, cond, case и других специальных форм, которые я до сих пор игнорировал. Постараюсь также добавить еще встроенных функций, и хотя бы один числовой тип - действительные числа с плавающей точкой, думаю.
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.
  • 9 comments