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

[avva]

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

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

У наброска появилась страница, на которой можно смотреть на весь код, как на текущее состояние, так и
на прошлые припадки (теги 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 строк кода.
------------------------------конец второго припадка----------------------------------

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

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

Comments

[avva.livejournal.com]

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

[gianthare.livejournal.com]

> в будущем они конечно будут символами с нормальными значениями
И пометкой spec-form? В корне верно. Интересно, в Схеме можно сделать
(define my-define define) ?