lisp + c/c++

Есть до жопы и больше ембедаббельных Лиспов и Схем (включая даже common lisp, например ecl). Есть мощный FFI, если хочется наоборот, C дёргать из Лиспа.

И как из этого ECL использовать из C++ какое-нибудь хитроумное Lisp-дерево (например результат парсинга чего-то)?

Предоставить из C++ набор функций, формирующих удобное для C++ представление дерева, и их дёргать из Лиспа, обходя Лисповое дерево. Это в общем случае гораздо удобнее, чем читать Лисповские списки из языка, для этого дела ни хрена не предназначенного.

Я такой техникой неоднократно пользовался и с Си, и с Java (в сочетании с SISC), и с .NET (с F# и с Bigloo).

Ясно, то есть в другую сторону... Спасибо.

Кстати, задумайся, а надо ли это тебе - передавать сложную структуру в C++. Может, лучше и всю нагрузку по её обработке переложить на Лисп?

С++ быстрее.

На самом деле у меня вопрос почти чисто теоретический - сейчас у нас вся эта куча с DSLами, питоном, бустом и C++, шеф бредит переделкой DSLов в XML и мечтает о sexpr'ах, при этом сам же говоря что это вероятно никогда не случится (потому что lisp хакеров не найдешь и тратата), так что если у нас что-то в эту сторону и двинется то вместо нагромождения собственных DSL у нас будет нагромождение 20-гигабайтных XML.. Вобщем проще забить.

Мне было интересно как бы это надо было делать если бы from scratch. Так или иначе на вопрос относительно необходимости передачи данных в C++ ответ в скорости некоторых операций над этими данными.

> С++ быстрее.

Нет. Только не в обработке деревянных структур.

> Мне было интересно как бы это надо было делать если бы from scratch.

Мало данных. Не ясно, что сами DSL делают (и как реализованны). Если интерпретатором на C++, то это конечно же в корне неверный подход.

> Так или иначе на вопрос относительно необходимости передачи данных в C++ ответ в скорости некоторых операций над этими данными.

Зачем их передавать в виде сложных структур? C++ эти структуры будет разбирать долго и уныло. Наверняка есть более низкоуровневый, атомарный набор операций, которые можно уже дёргать из Лиспа, а реализовывать на C++.

> Нет. Только не в обработке деревянных структур.
Хм ну а как же всякий хитроумный обход огромных деревьев (графов), рекурсия vs итерация и прочая?

> Мало данных. Не ясно, что сами DSL делают (и как реализованны). Если интерпретатором на C++, то это конечно же в корне неверный подход.
Парсинг и его правила. Трансфер деревьев и его правила. Это автоматический переводчик вроде PROMPT. DSLы реализованы интерпретатором на С++/пистоне (все это вместе склеено boost::python). Большая куча г^W.. разных вещей.

> Зачем их передавать в виде сложных структур? C++ эти структуры будет разбирать долго и уныло. Наверняка есть более низкоуровневый, атомарный набор операций, которые можно уже дёргать из Лиспа, а реализовывать на C++.
Я при всей этой песне вообще CToolbar-кодер - но мне интересен сам подход.

> Хм ну а как же всякий хитроумный обход огромных деревьев (графов), рекурсия vs итерация и прочая?

А так, что на C++ это эффективно реализовать гораздо сложнее, чем на Лиспе.

> Парсинг и его правила.

И какие тут на фиг структуры? C++ получит свои таблицы переходов в виде массивов, и пусть себе радуется.

> Трансфер деревьев и его правила

C++ тут абсолютно неуместен.

> Это автоматический переводчик вроде PROMPT

Я то думал математика какая... На фига вообще C++ в таких вещах?!? Преимуществ в производительности он не даст.

> DSLы реализованы интерпретатором на С++/пистоне (все это вместе склеено boost::python).

Ясно... Кошерное решение на Лиспе - компиляция DSL в Лисп (и следом уже на халяву в native). Метапрограммирование рулит.

>> Хм ну а как же всякий хитроумный обход огромных деревьев (графов),
>> рекурсия vs итерация и прочая?
> А так, что на C++ это эффективно реализовать гораздо сложнее, чем на
> Лиспе.
Обход огромных графов/деревьев? Я не спорю, я просто не знаю.

>> Парсинг и его правила.
> И какие тут на фиг структуры? C++ получит свои таблицы переходов в
> виде массивов, и пусть себе радуется.
Нет там никаких таблиц переходов это тебе не SLR. Грамматика то неоднозначная. В результате этого парсинга получаем дерево в стиле NP-VP и прочая лингвистическая радость. Это дерево и есть выход парсера. Правила парсера в DSL производят над этим деревом различные операции типо "Если то и тамто то пойди туда и туда и вот эти вот узлы склей в один а атрибутом SYNT_MY_BIG_ASS* установи флаг FOR_NOBODY_TO_FIND_OUT_WHAT_IT_DOES. С++ читает эти правила и выполняет то что в них сказано. Правила написано в DSL чтобы лингвист не зная особо програмирования мог что-то в них писать (это не статистический переводчик). C++ использован для скорости выполнения этих самых операций.

>> Трансфер деревьев и его правила
> C++ тут абсолютно неуместен.
Тут все выглядит похоже как в случае с парсингом - правила говорят что-то в стиле "если в дереве по VP идет NP и у NP атрибут WHATEVER то тогда обойди дерево слева направо и станцуй польку", польку танцует C++ (чтобы быстрее (с)).

>> Это автоматический переводчик вроде PROMPT
> Я то думал математика какая... На фига вообще C++ в таких вещах?!?
> Преимуществ в производительности он не даст.
Чтобы переколбашивая огромные деревья и графы (всякие трансдусеры и прочая) какой-нибудь питон не возился 10 лет.

>> DSLы реализованы интерпретатором на С++/пистоне (все это вместе
>> склеено boost::python).
> Ясно... Кошерное решение на Лиспе - компиляция DSL в Лисп (и следом
> уже на халяву в native). Метапрограммирование рулит.
Ну вот это мечта. В реальности все так как есть... Было интересно как мечта могла бы (должна бы) выглядеть.

>> Это автоматический переводчик вроде PROMPT
> Я то думал математика какая... На фига вообще C++ в таких вещах?!?
> Преимуществ в производительности он не даст.
Кстати в рамках анекдота - "наша конкуренция" (мы все - нишевые нерусские фирмы, так что неважно кто), говорят, свой шыт, который делает тоже самое, переписала из Prolog в C++, потому что медленно. ;) Но это так - ОБС и анекдот, который слышал краем уха.

> Обход огромных графов/деревьев? Я не спорю, я просто не знаю.

Именно. Это то, для чего Лисп собственно и предназначен.

> Грамматика то неоднозначная. В результате этого парсинга получаем дерево в стиле NP-VP и прочая лингвистическая радость.

GLR почто не используете тогда?

> С++ читает эти правила и выполняет то что в них сказано. Правила написано в DSL чтобы лингвист не зная особо програмирования мог что-то в них писать (это не статистический переводчик). C++ использован для скорости выполнения этих самых операций.

Да, довольно нелепое решение. Не проще ли эти правила писать на компилируемом языке? Уж всяко производительность выше будет, чем у интерпретатора на C++.

> правила говорят что-то в стиле "если в дереве по VP идет NP и у NP атрибут WHATEVER то тогда обойди дерево слева направо и станцуй польку", польку танцует C++ (чтобы быстрее (с)).

Та же хрень - C++ абсолютно неуместен. Интерпретатор тут неизбежно проиграет компилятору.

> Чтобы переколбашивая огромные деревья и графы (всякие трансдусеры и прочая) какой-нибудь питон не возился 10 лет.

То питон, а то Лисп. Несопоставимо.

> Было интересно как мечта могла бы (должна бы) выглядеть.

Попробуй так реализовать один из этих DSL, измерь производительность и напугай шефа.

> говорят, свой шыт, который делает тоже самое, переписала из Prolog в C++, потому что медленно. ;)

Нда-с, дурачьё. Учитывая, что Prolog тривиально компилируется в Си, с кучей хитрых оптимизаций...

> GLR почто не используете тогда?
У нас самописный chart parser. Почему - не спрашивай, не знаю. Это очень старый проект - еще с 90ых годов к которому дописываются все более следующие костыли. Я в основном по клиентским программам и багам.

> Не проще ли эти правила писать на компилируемом языке?
Идея в этих DSLах - возможность взять на работу лингвиста который не сильно шарит в программировании но знает всякие NP/VP. Такой лингвист пишет в декларативном стиле правила - следом C++ код их выполняет. Т.е. DSL это не совсем компилируемый/интерпретируемый язык в нашем случае вообще. Это просто набор действий написанных на каком-то диалекте. Питоно/С++ их читает и выполняет.

Идея приближающая мечту - взять один из этих DSL и переписать его в sexpr'ах.

> Та же хрень - C++ абсолютно неуместен. Интерпретатор тут неизбежно
> проиграет компилятору.
Дело не в интерпретаторе/компиляторе IMHO. Подумай об этих DSL как просто о конфигах процесса переколбашивания деревьев/графов.

> То питон, а то Лисп. Несопоставимо.
Хорошо знать.

> Попробуй так реализовать один из этих DSL, измерь производительность
> и напугай шефа.
Шеф бредит идеей переписания одного из DSL сначала в XML. Мне уже становится нехорошо.. Поэтому вопрос и был скорее теоретический.

ECL, по-моему, навсегда мёртв.

В любой реализации лиспа (CL) есть своё ffi (foreign function interface). Для Вашей цели (именно как встраиваемый язык) лучше бы подошёл Guile, его доку и читайте. Он, кстати, LGPL. Обычно ffi позволяет вызывать С из лиспа и обратно. Лисп может быть собран как разделяемая библиотека. Также можно использовать IPC.

Чтобы лисп увидел заголовочник от C(++), есть механизированные средства, например, http://www.lispworks.com/documentation/lw51/FLI/html/fli.htm
и там смотрим "The Foreign parser".

Не знаю, есть ли что-то подобное в SBCL, думаю, что есть (а SBCL - это самая модная на сегодня реализация Common Lisp).

Также есть универсальное средство SWIG, www.swig.org, которое годится не только для лиспа и позволяет увидеть С++ классы из лиспа (и не только из лиспа).

Рекомендуется пользоваться кросс-платформенными средствами FFI, т.к. ffi не стандартизован и сильно отличается между реализациями. См. лисповые сайты и найдёте (даже несколько вариантов). Я в своё время делал для лиспворкса свою версию swig на базе биндингов swig к scheme.

В целом, я согласен, что работать с деревьями на С/С++ будет относительно неудобно, хотя можно сделать кое-какие костыли с помощью макропроцессора и всё тогда будет выглядеть примерно вот так:

LISP_VAR(x, L( DEFUN _ FOO _ L(X _ Y) _ L(CONS _ X _ Y))))

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

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

Но, касаемо скорости. На сегодня быстрый и "модный" лисп - это SBCL. Вот здесь есть бенчмарки (это игра, каждый пишет так хорошо для своего языка, как может).

Сравнивая лисп с питоном, получаем, что питон, в общем-то отдыхает по сравнению с лиспом.
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=all&lang=...

Касаемо выделения памяти - у лиспа такой размер рантайма, что он превосходит память, выделяемую под задачу, но в приложении, которое работает долго, это неважно. Это важно для программ типа grep :)

Скорее всего, если переписать Ваше приложение в стиле Python/C++ на чистый SBCL, то оно станет работать быстрее. Кроме того, есть ещё вот такой бенчмарк,

http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=sumcol&la...

Задача предельно проста - прочитать числа из текстового файла и просуммировать их.
Вверху идут честно написанные согласно правилам варианты (требуется читать файл штатными средствами построчно).
С решает задачу за 5.25 секунд, С++ - за 8.42, SBCL - за 9.27
Внизу идут альтернативные варианты (работают корректно, но отступают от правил). В лиспе отступление от правил состояло в замене построчного чтения побайтным (хотя это должно быть медленнее).
SBCL управился с задачей за 2.5 секунды (но быстрее всех оказалась вообще Ява). С не удалось догнать SBCL, даже отступив от правил. Так что насчёт того, что C++ быстрее лиспа - вопрос открытый для дискуссий. Если SBCL может сделать С++ в 3 раза даже на задаче такого уровня, то что говорить о более сложных задачах, особенно, в тех, где нужна возможность что-то интерпретировать? А ведь SBCL умеет генерить оптимизированный нативный код на лету...

И вообще, закажите мне прототип - а там посмотрим. А то блин, сижу, денег мало, на скучную работу неохота, на интересную не взяли. Я ведь дорого не возьму - первая доза безплатно ;)

> Для Вашей цели (именно как встраиваемый язык) лучше бы подошёл Guile, его доку и читайте.

У http://grundik.livejournal.com/ впечатление от guile в бою скорее отрицательное.

> В лиспе отступление от правил состояло в замене построчного чтения побайтным (хотя это должно быть медленнее). SBCL управился с задачей за 2.5 секунды (но быстрее всех оказалась вообще Ява). С не удалось догнать SBCL, даже отступив от правил.

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

> Это очень старый проект - еще с 90ых годов к которому дописываются все более следующие костыли.

Томита свою знаменитую работу задолго до 90х накатал.

> Т.е. DSL это не совсем компилируемый/интерпретируемый язык в нашем случае вообще.

Я не об этом - DSL выгоднее компилировать, чем интерпретировать. И компилятор DSL->Lisp->Native будет гораздо эффективнее, чем DSL->C++ interpreter.

> Идея приближающая мечту - взять один из этих DSL и переписать его в sexpr'ах.

Это всего лишь синтаксис. Синтаксис роли не играет, важно то, КАК он исполняется. Семантика, то есть.

> Дело не в интерпретаторе/компиляторе IMHO. Подумай об этих DSL как просто о конфигах процесса переколбашивания деревьев/графов.

Кто-то тут говорил, что производительность важна. Создать из такого конфига специализированную, оптимизированную скомпилированную программу - гораздо лучше, чем интерпретировать этот конфиг тупым тормозным интерпретатором.

> Шеф бредит идеей переписания одного из DSL сначала в XML.

Опять же - это только синтаксис. Это ничего не изменит вообще в плане исполнения этого кода. Синтаксис может быть каким угодно, хоть и XML, это самая маленькая и неинтересная часть любого DSL.

> Если SBCL может сделать С++ в 3 раза даже на задаче такого уровня, то что говорить о более сложных задачах, особенно, в тех, где нужна возможность что-то интерпретировать? А ведь SBCL умеет генерить оптимизированный нативный код на лету...

Достаточно захотеть классов, и CLOS не даст вам почти ничего оптимизировать на машинном уровне.

> Для Вашей цели (именно как встраиваемый язык) лучше бы подошёл Guile, его доку и читайте.

Интерпретатор. В печку его.

> а сишная программа честно дёргает syscall на каждый байт (сорцы не смотрел)

Посмотрел. Сишная программа явно читает построчно, а лисповая явно побайтно (речь идёт о самой программе, а не о автоматических оптимизициях). Зачёт SBCL.

Кстати, SBCL со времён 1.0.12 подразогнали неплохо.

>Достаточно захотеть классов, и CLOS не даст вам почти ничего оптимизировать на машинном уровне.

А я их и не хочу. Пользуюсь только в крайнем случае. Мне кажется, CLOS - это несколько монстроидная вещь, надо бы что-то попроще. Хотя это - вопрос знания и культуры, а тот лисповый код, который я читал, в основном не базируется на CLOS.

Впрочем, в лиспе, безусловно, возможно сделать и более простую (и более подверженную оптимизации) систему ООП. Самое короткое расширение Scheme, добавляющее понятие класса, имеет исходник в 4кб. Я в скоё время в переписке написал за один день объектно-ориентированное расширение С то ли на m4, то ли на #define. Нет в этих классах никакой магии. Небольшое расширение языка и совершенно несложное. Некоторые манипуляции с пространством имён и добавление средств динамического выбора тела. Всё.

> А я их и не хочу. Пользуюсь только в крайнем случае. Мне кажется, CLOS - это несколько монстроидная вещь, надо бы что-то попроще. Хотя это - вопрос знания и культуры, а тот лисповый код, который я читал, в основном не базируется на CLOS.

Ну тогда спокойно можете использовать SBCL. Компилятор некоторые ляпы делает, но, в целом, выдаёт весьма достойный машинный код, тем более, для языка такого высокого уровня. Кое в чём готовый код можно с gcc'шным сравнивать.

> Впрочем, в лиспе, безусловно, возможно сделать и более простую (и более подверженную оптимизации) систему ООП. Самое короткое расширение Scheme, добавляющее понятие класса, имеет исходник в 4кб. Я в скоё время в переписке написал за один день объектно-ориентированное расширение С то ли на m4, то ли на #define. Нет в этих классах никакой магии. Небольшое расширение языка и совершенно несложное. Некоторые манипуляции с пространством имён и добавление средств динамического выбора тела. Всё.

Безусловно. CLOS просто очень мощный и гибкий.

lush.sf.net?

>Достаточно захотеть классов, и CLOS не даст вам почти ничего оптимизировать на машинном уровне.

Но и не так медленно. Например, можно замерить, как отличается вызов 
обычной (пустой) функции, вызов метода (дискриминация по одному 
объекту!) и использование etypecase. Видно, что оптимизационные 
алгоритмы на уровне библиотеки CLOS делают свое дело -- метод 
вызывается всего-лишь в два раза медленнее функции (это и в CLISP, и в
SBCL). А etypecase и того медленее. Тестик как-то Snellman вывешивал 
на c.l.l в каком-то очередном обсуждении год или полтора назад. 
Тестик синтетический конечно, и ясно, что более исчерпывающий
тест можно получить, сделав какую-нибудь разухабистую иерархию классов
с множественным наследованием и т. д. А тут нет иерархии никакой. 
Тогда можно реальные цифры получить, но и не такие оптимистичные, 
наверное. :)


(declaim (optimize speed))

(defclass a () ())
(defclass b () ())
(defclass c () ())
(defclass d () ())

(defgeneric test-generic (object)
  (:method ((object a)) 1)
  (:method ((object b)) 2)
  (:method ((object c)) 3)
  (:method ((object d)) 4))

(defun test-etypecase (object)
  (etypecase object
    (a 1)
    (b 2)
    (c 3)
    (d 4)))

(defun test-null (object)
  (declare (ignore object))
  nil)

(defun run (&optional (iterations (expt 2 22)))
  (let ((objects (list (make-instance 'd)
                       (make-instance 'a)
                       (make-instance 'b)
                       (make-instance 'c))))
    (setf (cdr (last objects)) objects)
    (time
      (dotimes (i iterations)
        (setf objects (cdr objects))
        (test-null (car objects))))
    (time
      (dotimes (i iterations)
        (setf objects (cdr objects))
        (test-generic (car objects))))
    (time
      (dotimes (i iterations)
        (setf objects (cdr objects))
        (test-etypecase (car objects))))))

s/(optimize speed)/(optimize (debug 0) (safety 0) (speed 3))

>s/(optimize speed)/(optimize (debug 0) (safety 0) (speed 3))

Это была копипаста. Так написал сам Juho Snellman -- основной контрибутор SBCL. Я очень давно просто этот примерчик скопипастил из треда, чтобы проверить у себя. Так с тех времен в хламовке и валялся. :)