набросок, ч. 2
Jul. 15th, 2010 08:46 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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, но это временно.
OK, что дальше. Кажется, пришла пора писать функцию выполнения eval()! Мой первый eval() будет очень примитивный (улавливается закономерность?), потом я его переделаю. Списки он будет выполнять, вызывая себя рекурсивно; это очень просто написать, но не поддерживает хвостовую рекурсию, обязательную в Схеме. Что это такое и как ее поддержать, обсудим позже. Специальные формы define и set! будут специальными случаями в коде eval(), а вот встроенные функции типа + и car я хочу сделать уже общим способом.
eval() принимает индекс значения для выполнения и возвращает индекс результата. Вот начало функции, показывающее, что делать для примитивных значений, для списка, и специальный случай "define" внутри списка.
Пока хватит специальных форм, займемся функциями. Для функций мы заведем новый вид значения T_FUNC. Что он должен хранить - отдельный интересный вопрос. Если это функция, определенная программистом - то список параметров и собственно тело функции, т.е. два значения (тело функции - просто очередное значение). Кроме того, для поддержки замыканий (closures) надо будет еще добавить... но как именно это устроить, я еще не решил окончательно. Ну а если функция встроенная? Это отдельный тип T_BLTIN или тот же T_FUNC но с дополнительным флажком, который говорит "я встроенная функция"? Мне кажется, лучше с флажком, бит у нас еще много.
Встроенные функции регистрируют себя с помощью register_builtin():
Встроенные функции вскоре переедут в свой собственный файл, подозреваю.
Проверка этого кода показывает, что в car() и cdr() выше есть баг, хоть они и кажутся очень простыми. Дело в том, что они получают напр. не (1 2 3), если вызвать (car (quote (1 2 3)), а ((1 2 3)), потому что они получают список всех своих аргументов: в данном случае аргумент один, но список все равно есть. Вот например код исправленной car:
Последнее, что хочется успеть сегодня - синтаксис '(1 2 3) вместо (quote (1 2 3)). Это просто. В случае, когда мы видим апостроф, мы просто читаем следующее значение, и руками составляем его в список вместе с символом quote. Вот код нового куска в read_value() (кроме этого, был небольшой рефакторинг make_list(), чтобы он сам () в конце добавлял для простоты):
Проверка всего, что понаписано!
На сегодня все. Проект вырос до 420 строк кода.
------------------------------конец второго припадка----------------------------------
Код проекта (главная линия, меняется)
код второго припадка (зафиксирован)
Продолжение наброска.
У наброска появилась страница, на которой можно смотреть на весь код, как на текущее состояние, так и
на прошлые припадки (теги 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);
#include <tr1/unordered_map>
tr1::unordered_map<string, uint32_t> table;
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;
}
uint64_t cells[MAX_CELLS];
/* start from 1, as index 0 is reserved for errors or invalid values */
uint32_t next_cell = 1;
#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;
}
#define SYMBOL_LEN(i) (cells[i] >> 32)
...
uint64_t value = type | (uint64_t)len << 16 | (uint64_t)(end-str) << 32;
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;
Пока хватит специальных форм, займемся функциями. Для функций мы заведем новый вид значения T_FUNC. Что он должен хранить - отдельный интересный вопрос. Если это функция, определенная программистом - то список параметров и собственно тело функции, т.е. два значения (тело функции - просто очередное значение). Кроме того, для поддержки замыканий (closures) надо будет еще добавить... но как именно это устроить, я еще не решил окончательно. Ну а если функция встроенная? Это отдельный тип T_BLTIN или тот же T_FUNC но с дополнительным флажком, который говорит "я встроенная функция"? Мне кажется, лучше с флажком, бит у нас еще много.
#define T_FUNC 7 /* function, a.k.a. closure */
#define BLTIN_MASK 16
Встроенные функции регистрируют себя с помощью 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);
}
Встроенные функции вскоре переедут в свой собственный файл, подозреваю.
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);
}
/* 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);
Проверка этого кода показывает, что в 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));
}
Последнее, что хочется успеть сегодня - синтаксис '(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 строк кода.
------------------------------конец второго припадка----------------------------------
Код проекта (главная линия, меняется)
код второго припадка (зафиксирован)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-07-15 08:24 am (UTC)И пометкой spec-form? В корне верно. Интересно, в Схеме можно сделать
(define my-define define) ?