November 7, 2010

uri-template, Eager Future и Руби, и ещё немного бреда о Лисповой операционной системе

Выставил uri-template и Eager Future на github:

https://github.com/vsedach/uri-template
https://github.com/vsedach/Eager-Future

uri-template теперь использует named-readtables, которое дает возможность использовать readtables и reader macros аналогично packages. Рекоммендую named-readtables всем кто использует read-macros, и даже всем кто их не использует из за readtable-case :invert (самый перспективный метод иметь регистры типа верблюжих в символах).

План перевести uri-template на LLGPL (была лицензированной под BSD), а Eager Future переписать как совершенно новый проект с довольно уникальными свойствами среди конкурентных библиотек (тоже под LLGPL, но сначала надо додуматся как перебороть SBCL, там что-то вроде бага со слабыми ссылками - подробности (англ)).

Джастин Грант показал как можно реализовать компилятор с Ruby на Лисп (англ). Я наконец сошел с ума и тоже хочу сделать компилятор на Лисп, только из C. Зачем? Что бы взять NetBSD, скомпилировать его драйвера на Лисп, и получить Лисповую операционную систему (я же сказал я сошел с ума). Подробности на Hacker News (англ). Проект вот здесь, для начало взял Zeta-C, C компилятор для Лисп-машин, но уже видно что почти всё придётся переписывать. Для начала, может кто нибудь знает, существует ли рабочий Лисповый парсер C (в Zeta-C противная дрянь генерирована yacc-ом времен СССР и переведенная в Zetalisp)?

19 comments:

freiksenet said...

Автор cl-yacc упоминал что парсил им superset of C, может у него чтото есть.

Yakov Zaytsev said...

> Что бы взять NetBSD, скомпилировать его драйвера на Лисп, и получить Лисповую операционную систему

крэзи конечно
я б сделал лучше примочку чтоб драйвера на lisp писать можно было для начала. для линукс для начала напр ;-)
т.е. lisp машина на ядре linux скажем более реалистична :-D

Dmitriy Budashny said...

Но ведь драйвера это ещё не вся операционная система. К чему эти драйвера собираетесь прикручивать?

Anonymous said...

> План перевести uri-template на LLGPL (была лицензированной под BSD)

Лучше не нужно. GNU лицензии есть зло для Lisp`а и его продвижения.

--
Артем

quasimoto said...

У NetBSD конечно много дров, но лучше уж тогда брать DragonFlyBSD (шутка :)). А вообще, на данный момент роскошь запустится на голом железе уже не так много значит (взять тот же Inferno - как он был на обочине истории, так и есть, при том что может работать как в режиме "железном", так и хостится под другими ОСами). Гораздо важнее сами VM с их свойствами - JVM вполне себе ОС, а LLVM вполне себе окружение. В этом смысле правильнее было бы развивать модульность и разные продвинутые фичи в SBCL, чем воскрешать повисшие в воздухе остатки Symbolics/Genera/Etc. К примеру - существует на данный момент ассемблер на CL который может быть использован в прктических целях? Да, у автора Movitz, но - не очень хорошо пашет и только для x86. А вот ассамблер в SBCL, будучи выделен в отдельный модуль (относительно не сложно), автоматически оказывается вполне себе консистентным ассамблером под чуть ли не десять архитектур :) И вот так во многих других аспектах (что касается SBCL) - виртуальные операторы фактически заменяют собой примитивы трансляции в си, например, то что в си `+', то в SBCL - VOP; пакет SB-VM содержит кое-какие описания тех архитектур (именно в "железном" смысле), на которых работает VM и т.д.

Кстати, а зачем LLGPL? Зачем лицензировать код, который итак в PD (вот SBCL - тоже большей частью в PD)?

Vladimir Sedach said...

@freiksenet

Ура! Спасибо за ссылку, все нашел: http://www.pps.jussieu.fr/~jch/software/repos/cpc/

@Yakov Zaytsev

Проблема то что на базовом уровне все равно остается C, а это значит обязательный раздел kernel и user и виртуальная память. Когда все на Лисповом рантайме с проверками, все намного проще, быстрее и также есть возможность делать очень крутые вещи с аллокатором и мусорщиком.

Насчет Linuxа конкретно, там код просто говно по сравнению с NetBSD. Его вообще скомпилировать без GCC невозможно, и организация в большей части отсутствует.

@Dmitriy Budashny

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

@quasimoto

SBCL хороший пример, но его VOPs слишком связаны с его C-ишным рантаймом и нужды в операционной системе. Помимо самих VOPs для системного Лиспа будет нужен еще ограничиный диалект Лиспа для системного программирования и бутстраппинга. Такие диалекты были в T и Portable Standard Lisp. Я думаю будет перспективно использовать первую половину SBCL (компиляция Common Лиспа в IR) над специально продуманными VOPs и системным диалектом Лиспа.

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

quasimoto said...

> SBCL хороший пример, но его VOPs слишком связаны с его C-ишным рантаймом и нужды в операционной системе.

Не совсем так. Конкретно - в sbcl/src/compiler/assem.lisp определяется структура segment которая держит вместе с прочими слотами бинарный буфер (слот buffer) в которые происходит emit этих самых raw байтов которые соответсвуют ассемблерным мнемоникам. Далее - структура instruction которая содержит слот emitter, это функция которая в бинарный буфер сегмента пишет машкод. И в конце этого файла - мкрос define-instruction который из некоторого декларативного описания инструкции создаёт функцию эммитер, структуру instruction и помещает её *assem-instructions*.

И для каждой из семи архетектур есть файл sbcl/src/compiler/${ARCH}/insts.lisp который определяет весь набор инструкций (трансферных мнемоник и производных) для архитектуры.

Т.е. я хочу сказать что эта часть SBCL очень портируема и почти независима - просто структура с бинарным буфером и набор макросов для определения инструкций (функций которые мишут машинный код). А дальше - бакэнды в которых эти макросы используются для определенрия всех инструкций. И нужно добавить, что в compiler/generic лежит некоторое описание того чем является IBM PC с точки зрения плоской памяти (байты, например, октеты и т.д.), а в compiler/${ARCH} с точки зрения архитектуры CPU (регистры и т.п.).

Что касается VOP-ов - я так подробно не разбирался, но у меня создалось впечатление что это DSL следующего уровня уже над инструкциями (vop.lisp, meta-vmdef.lisp), хотя уже есть гораздо больше зависимостей и привязок к VM и IR2 представлению.

> Помимо самих VOPs для системного Лиспа будет нужен еще ограничиный диалект Лиспа для системного программирования и бутстраппинга.

Как недавно заметил dmitry_vk, си это DSL к плоской памяти (и инструкциям процессора, добавлю). Это его путь к управлению *машиной* и построению абстракций (такие сейчас машины). В этом смысле транслировать C -> CL это неправильно в смысле того, что CL имеет GC, CL это более абстрактный язык, мало завязанный на модель мультипроцессоры+плоская-разделяемая-память. Так что да, нужен субдиалект, системный. И я вижу, что распарсить си в некий лисп - не проблема (cl-yacc действительно выглядит лучше, чем тот ужас в Zeta-C ;). А вот что дальше делать с этим AST - во что транслировать? И SBCL с его ассемблером и VOP-ами выглядит лучшим бакендом. Т.е. что-то вроде LLVM - LLVM используется как платформа для разных языков. SBCL пока платформа только для Common Lisp (чтобы определить точно, что за язык), но вполне может служить платформой для языков с другими свойствами (си-стемных, например).

----

> LLGPL очень приемлимая лицензия.

Ну в принципе да. Как говорил один из апологетов опес-сорса - "в идеальном мире BSD/Public Domain были бы лучшими выразителями идеалов открытого кода, но в нынешнем мире - таковы GPL-подобные лицензии." Хотя мне всегда кажется что по-настоящему крутые вещи должны сразу делаться в PD (как в том же CMUCL - это было сразу, а не как в Zeta-C - открыли и слили, когда уже самим это совсем не нужно :)).

Yakov Zaytsev said...

> Когда все на Лисповом рантайме с проверками, все намного проще, быстрее и также есть возможность делать очень крутые вещи с аллокатором и мусорщиком.

можно раскрыть для особо одареных.
все-таки чем плохо если лисп-рантайм сидит в ядре *BSD и все сисколы и апи в нем foreign functions? это ж все равно завуалировать можно.
да, линукс говно, но широкораспространенное.

Vladimir Sedach said...

А что если в ядре ошибка? Или захотелось что-то поменять? И кто будет кому память распределять и как?

Ведь если даже попытатся всё сделать тупо через сисколы как ffi, они же все сделаны под userspace, в самом ядре распределение памяти, процессы/треды и даже стек работают совсем по другому и с большими ограничениями.

Пока со всем этим разберешся было бы намного проще сделать свое ядро (ведь всё что нужно для лисповского ядра это аллокатор и стеки - на базе этого можно сделать мусорщик и нити) и подогнать BSDшные драйвера как простые библиотеки.

А в Линуксе ещё хуже. Во первых Линус назовет тебя дураком (такое по настоящему было с Schemix), а потом решит сделать капитальный рефакторинг внутренностей ядра и всё придется делать по новому.

Anton Vodonosov said...

А я вот не понял, кроде других вещей, почему нужно перекомпилировать эти драйвера каким-то другим компилятором? Это же все равно компилятор языка С?

Что значик компилятор из С на Лисп? Почему нельзя подключать к лисповому ядру драйвера скомпилированные обычным сисшным компилятором?

Vladimir Sedach said...

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

Все недостатки Лиспа под Сишным ядром остаются, только получается в два раза больше работы!

Anton Vodonosov said...

Хорошо, теперь понимаю.

Сомнение: свойства рантайма зависят от языка. Возможно ли сделать лисповый рантайм который будет удовлетворять требованиям С?

Операции типа: void *p = malloc(100*sizeof(SomeStruct)); SomeStruct *ss = (SomeStrcuct*)p; ss.a = 1; ss++; ss.a = 2;

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

love5an said...

>quasimoto
>си это DSL к плоской памяти (и инструкциям процессора, добавлю). Это его путь к управлению *машиной* и построению абстракций (такие сейчас машины).

Да нет, "такими" машины были когда Си создавался и претерпевал основное развитие.
А возможности сегодняших машин, с векторными инструкциями, несколькими ядрами, и прочим, он совершенно не отображает.
Си тупо устарел.

gavenkoa said...

@love5an
> Си тупо устарел.

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

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

Модель вычислительной машины фон Неймана портят необходимые средства защиты памяти (больше касается кода ядра) и многопоточность (в основном прикладной код).

Маркет Лисп процессоров помер в 80-ых, потому натягивать Лисп на PC актуально лишь в качестве хобби.

Высокоуровневые распределенные вычисления, абстрагированые от hadrware, более удачная ниша для Lisp.

Vladimir Sedach said...

"Архитектура процессоров общего назначения заложена фон Нейманом и стандарт Си в точности ложится в эту архитектуру."

Правильно. Виртуальная память, кэщ инструкций, NUMA, scratchpad RAM и многопроцессорность не существуют и Си есть зеркальное отражение архитектуры компютера.

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

Кроме плоской памяти, стека, модель вызова, расположение и формат кода в памяти, метод распределение памяти динамически, метод распределение памяти статически.

"Маркет Лисп процессоров помер в 80-ых, потому натягивать Лисп на PC актуально лишь в качестве хобби."

Что общего имеет PC с Лисп процессорами? И в чём недостатки существующих Лисп компиляторов которые делают их подходы компилирования не пригодным для системного программирования?

gavenkoa said...

@Vladimir Sedach
> "Архитектура процессоров общего
> назначения заложена фон Нейманом
> и стандарт Си в точности ложится
> в эту архитектуру."

> Правильно. Виртуальная память,
> кэщ инструкций, NUMA, scratchpad
> RAM и многопроцессорность не
> существуют и Си есть зеркальное
> отражение архитектуры компютера.

Многоядерность, многопоточность, разделение ресурсов процесами не входит в стандарт Си, POSIX помогает немного в этом. В интервью Дейкстра высказывался что исследования в compter scince в 200x будут направлены как раз в этом направлении, т.к. производители практически исчерпали технические приемы делать cpu быстрее, теперь делают дешевле и побольше копий ядра.

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

Виртуальную память я думаю неуместно приводить в пример, она решает множество проблем, при этом __прозрачно__ - она есть, но ее никто не "видит". Тем более в 64-битную эру дешевой памяти об этом можно не переживать.

Приведу пример когда на Си все же можно провести "тюнинг" в условиях паралельности (решение задачи о хамелионах из shootout.alioth.debian.org): http://software.intel.com/ru-ru/blogs/2009/09/15/2002127/

> Кроме плоской памяти, стека,
> модель вызова, расположение и
> формат кода в памяти, метод
calling convention не слишком при чем. Скорее всего 32-битная Windows виновница того что об этом еще помнят )) В 64-битной Windows это учли.

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

> распределение памяти
> динамически, метод распределение
> памяти статически.

OK, на производительность это влияет. OCaml имеет умный алокатор и на задачах, требующих много выделения/освобождения памяти, оставляет далеко позади C/C++.

> "Маркет Лисп процессоров помер в
> 80-ых, потому натягивать Лисп на
> PC актуально лишь в качестве
> хобби."

> Что общего имеет PC с Лисп
> процессорами? И в чём недостатки
> существующих Лисп компиляторов
> которые делают их подходы
> компилирования не пригодным для
> системного программирования?

Это сарказм, в Лисп компиляторах я профан ))

Vladimir Sedach said...

"В интервью Дейкстра высказывался что исследования в compter scince в 200x будут направлены как раз в этом направлении, т.к. производители практически исчерпали технические приемы делать cpu быстрее, теперь делают дешевле и побольше копий ядра."

Если взять Лисп, APL и функциональное программирование, то все перспективные технологии кроме software transactional memory уже были реализованны к началу 90х (насчет Лиспа, это включает *Lisp (Starlisp), Multilisp, actors (ACT-1, ABCL), Paralations, NESL).

В основном прогресс в многопроцессорности в 90х и 200х был в математических моделях консистентности и в железе (compare and swap, cache coherency).

"Виртуальную память я думаю неуместно приводить в пример, она решает множество проблем, при этом __дерьмово__"

I fixed it for you.

Какие проблемы пытаются решать с помощю виртуальной памяти?

В первой категории изоляция процессов и защита от хакеров. Это делается проще и надежнее с помощю проверки типов (куда виртуальную память уже стали протаскивать начиная с NX bit).

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

В результате получается куча фрагментации и неиспользуемой памяти (relocating мусорщик тривиально справляется с этой проблемой если знает настоящеё распределение памяти).

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

64-битные системы как раз имеют больший недостаток когда используются с виртуальной памятю чем 32-битные. Адресов намного больше (да и каждый адресс занимает в два раза больше байтов) а что делать с размерами страниц? 4kb не актуально - таблица страниц будет занимать слишком много памяти. А 2mb и более значит куча неиспользуемой памяти, и очень низкое ограничение на количество нить в системе (ведь стэк-то распределается нитям по страницам).

Кстати о таблице страниц и многопроцессорности, ведь таблица тоже имеет свою кэщ на каждом процессоре (translation lookaside buffer), и её надо синхронизировать также как и L2 кэщ.

Всё что делает виртуальная память делается проще и эффективнее с помощю проверки типов и мусорщика.

"Формат кода в памити - я не в курсе как оптимиризующие компиляторы работают."

Не столько формат а вопрос где он находится (data/code segments).

gavenkoa said...

Прежде спасибо за дискусию на гране моей некомпетентности ))

> Если взять Лисп, APL и
> функциональное программирование,
> то все перспективные технологии
> уже были реализованны к началу 90х

Несомненно за ФП будущее.

Человек задает цель, а ЭВМ ищет решение или человек работает с категориями предметной области, а не машинными инструкциями.

> В первой категории изоляция
> процессов. Это делается проще и
> надежнее с помощю проверки типов
Изоляция процесов, пользователей, прав доступа, виртуальных машин - большая часть выполняется аппаратно. Чем тут проверка типов может помочь - не знаю.

Вот для исходного тескта программы наличие типов облегчает доказательство корректности программы (по различным критериям, например отсутствие переполнения буфера) и в случае наличия доказательства корректности компилятора/интерпретатора мы получаем надежную программу.

Си на типы плюет - потому много трудно улавиливаемых проблем.

> с помощю проверки типов (куда
> виртуальную память уже стали
> протаскивать начиная с NX bit).

Последнюю моду запускать процесы в виртулаьных контейнерах (или другое - ARM TrustZone® technology) уже не отнести к проверке типов.

NX - прежде всего дешевая защита от атаки переполнения буфера.

> свопинг
Не стоит рассматривать, кому надо - тот обеспечит нужним числом GiB RAM свой сервер.

Хотя во времена System/370 именно для этого и реализовали вирт. пам.

> Всё что делает виртуальная
> память делается проще и
> эффективнее с помощю проверки
> типов и мусорщика.
Остается чуство что чет не так, но с реализацией виртуальной памяти ни для одной из архитектур не знаком ))

quasimoto said...

Вот ещё довольно интересный пример на тему разбора и компиляции Си:

http://piumarta.com/S3-2010/com-paper.pdf
http://piumarta.com/S3-2010/com-example.tar.gz

там PEG грамматики, какой-то диалект лиспа как промежуточное представление, возможен bootstrap.