Здравствуйте, Аноним, Вы писали:

DM>>Из этого примера смысл ast:visit в МЛ ускользает — чем плох обычный рекурсивный обход дерева?

А> Тем, что надо не забыть рекурсивно обойти все-все ссылки. А при преобразовании ast -> ast забыть это очень легко, типизация тут ничем не поможет.

А часто ли тип результата трансформации дерева совпадает с исходным? В моей практике — нечасто. Поэтому проверка типов просто не даст забыть преобразовать какой-нибудь случай.

Причем во многих случаях вполне сгодятся map и fold из tywith:

The following type definition:

  type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree
    with map, fold

Will generate functions with the following signatures:

  val map_tree : ('a -> 'b) -> 'a tree -> 'b tree
  val fold_tree : ('a -> 'b) -> ('b -> 'b -> 'b) -> 'a tree -> 'b

В них уже можно подставлять конкретные функции преобразования частей.

DM>> В нем гораздо больше свободы действий

А> Не больше. Явный обход дерева — это частный случай.

Не очевидно. Но я просто не знаю всех возможностей ast:visit.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, thesz, Вы писали:

TBG>>>А как сам где-то в этой теме говоришь: "Ценность этого действа сильно преувеличена".

T>>Я говорю, что ценность метапрограммирования преувеличена.

А> Qi — по сути, расширение Лиспа. Да и Axiom тоже. И в Qi, и в Qi II, и в Axiom зависимые типы присутствуют.

Я, как-то, спровоцировал войну в ru_lisp в ЖЖ.

Узнал много нового, например, что пользователю Qi удалось доказать, что 42 имеет тип "строка". Плюс, как выяснилось, никто из пользователей Lisp, присутствующих в ru_lisp, не использует Qi в своей работе.

Если хочется опровергнуть, то я бы попросил написать аналог кода для safeHead

Автор: thesz
Дата: 12.08.09

.

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

Здравствуйте, D. Mon, Вы писали:

DM>А часто ли тип результата трансформации дерева совпадает с исходным?

Очень часто. Большая часть преобразований именно такие.

DM> В моей практике — нечасто.

Часто компиляторы пишешь?

DM> Поэтому проверка типов просто не даст забыть преобразовать какой-нибудь случай.

Даже если и так — разве не напрягает все эти случаи расписывать, да ещё и везде менять код при изменении определения типа?

DM>В них уже можно подставлять конкретные функции преобразования частей.

И получается тормозятина. ast:visit не будет вообще переписывать те части дерева, которые не могут заведомо содержать изменяемые узлы. fold пройдётся по всему дереву целиком.

И для описанного случая (переименование переменных с lexical scoping) никакой fold не годится, поскольку тут нужно тащить контекст.

DM> Не очевидно. Но я просто не знаю всех возможностей ast:visit.

Посмотри на примеры, там всё довольно таки прозрачно. Наиболее полезная хитрая фича — else-deep. А при отключении стратегии DEEP это будет ровно то же самое, что просто рекурсивный обход дерева. Да, ещё конструкторы там есть удобные, в ML так сделать нельзя — см. макру ast:mknode.

Здравствуйте, D. Mon, Вы писали:

DM> Зачем? Можно так с ним сравнить. Насколько сейчас отличается скорость твоего решения от данного интерпретатора?

Потому что сейчас вариант на С тормознее компилируемого варианта Lisp.

Здравствуйте, thesz, Вы писали:

А>> Qi — по сути, расширение Лиспа. Да и Axiom тоже. И в Qi, и в Qi II, и в Axiom зависимые типы присутствуют.

T>Я, как-то, спровоцировал войну в ru_lisp в ЖЖ.

Ну в войнах то тролли участвуют. Всем остальным до них дела нет.

T>Узнал много нового, например, что пользователю Qi удалось доказать, что 42 имеет тип "строка". Плюс, как выяснилось, никто из пользователей Lisp, присутствующих в ru_lisp, не использует Qi в своей работе.

Я Axiom использую.

T>Мой вывод из всего этого таков: лисп остановился в развитии вместе с его пользователями.

Пользователи Лиспа не считают это направление "развитием". Есть более полезные для практики направления, куда стоит развиваться.

T> Вместо поиска путей конструктивных ограничений (Haskell, Agda2), его пользователи продолжают использовать его гибкость.

Ну не любят лисперы bondage&discipline. Не для всех это извращение, только немногие получают от этого удовольствие, большинству же и смотреть то противно, не то что участвовать.

T> Любые попытки внести такие ограничения в Лисп даже в виде расширений не используются в реальной работе,

Конечно, зачем лисперам то эти ограничения? Они используются в реальной работе тех самых DSLей, которые лисперы пользователям дают. И не по той причине, что пользователи любят садомазо, а чтоб им, пользователям, по ручкам шаловливым вовремя настучать, даже если им это и не понравится.

Здравствуйте, Turtle.BAZON.Group, Вы писали:

TBG>Потому что сейчас вариант на С тормознее компилируемого варианта Lisp.

Немножко ошибся. Забыл, что на другом компьютере считал. Итак:

C++ 26 сек
Lisp (compiled) 37 сек
Lisp (interpreted) 64 сек

Но это ещё без оптимизаций — без деклараций типов и тому подобного.

turtle@turtle:~/scm-controlled/turtle/icfpcontest/icfpcontest-2009/speedcon$ time ./a.out ../task/bin1.obf 1001
267 frames loaded

real    0m25.736s
user    0m24.454s
sys     0m0.044s

* (time (bazon-icfpc-2009:start-vmc "../task/bin1.obf" 1001 :max-steps 1000000))

Evaluation took:
  37.156 seconds of real time
  36.886305 seconds of total run time (36.782299 user, 0.104006 system)
  [ Run times consist of 1.332 seconds GC time, and 35.555 seconds non-GC time. ]
  99.27% CPU
  924 lambdas converted
  66,877,744,221 processor cycles
  2,678,521,056 bytes consed

* (time (bazon-icfpc-2009:start-vmi "../task/bin1.obf" 1001 :max-steps 1000000))

Evaluation took:
  63.763 seconds of real time
  55.631477 seconds of total run time (55.543471 user, 0.088006 system)
  [ Run times consist of 1.048 seconds GC time, and 54.584 seconds non-GC time. ]
  87.25% CPU
  114,767,574,723 processor cycles
  2,656,352,744 bytes consed

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, thesz, Вы писали:

А>>> Qi — по сути, расширение Лиспа. Да и Axiom тоже. И в Qi, и в Qi II, и в Axiom зависимые типы присутствуют.
T>>Я, как-то, спровоцировал войну в ru_lisp в ЖЖ.
А> Ну в войнах то тролли участвуют. Всем остальным до них дела нет.

Вот ты себя к кому относишь, к троллям, или ко всем остальным?

T>>Узнал много нового, например, что пользователю Qi удалось доказать, что 42 имеет тип "строка". Плюс, как выяснилось, никто из пользователей Lisp, присутствующих в ru_lisp, не использует Qi в своей работе.
А> Я Axiom использую.

Ура!

Первый лиспер из множества участвовавших в обсуждениях с моим участием, что использует в своей работе систему типов.

T>>Мой вывод из всего этого таков: лисп остановился в развитии вместе с его пользователями.
А> Пользователи Лиспа не считают это направление "развитием". Есть более полезные для практики направления, куда стоит развиваться.

Например?

T>> Любые попытки внести такие ограничения в Лисп даже в виде расширений не используются в реальной работе,
А> Конечно, зачем лисперам то эти ограничения? Они используются в реальной работе тех самых DSLей, которые лисперы пользователям дают. И не по той причине, что пользователи любят садомазо, а чтоб им, пользователям, по ручкам шаловливым вовремя настучать, даже если им это и не понравится.

Я не понимаю, зачем скатываться в "любят садомазо" на третьем или даже втором ответе.

Тем не менее, я продолжу.

Я считаю себя пользователем своих же творений.

Как только я написал функцию, я намерен её использовать.

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

Почему лисперы не считают себя пользователями своих же функций? Или считают? Если считают, то почему они не ограничивают себя, как других пользователей?

Здравствуйте, thesz, Вы писали:

T>Первый лиспер из множества участвовавших в обсуждениях с моим участием, что использует в своей работе систему типов.

Ну так я и Haskell использую, где-то треть кода пишется на нём.

T>>>Мой вывод из всего этого таков: лисп остановился в развитии вместе с его пользователями.
А>> Пользователи Лиспа не считают это направление "развитием". Есть более полезные для практики направления, куда стоит развиваться.

T>Например?

Техники реализации DSLей с хитрой семантикой. В которую может входить и сложная система типов. А может и не входить.

T>Я не понимаю, зачем скатываться в "любят садомазо" на третьем или даже втором ответе.

Сравнение типизации с bondage&discipline — давнее и устоявшееся. Лично я ничего в этом обидного не вижу. Лупть по рукам надо всех, в том числе и меня самого. При определённых обстоятельствах, конечно же.

T>Поскольку я признаю за собой право на ошибку и признаю за собой ответственность за ошибки в программе в целом, мне удобно, когда я сразу получаю по рукам. Даже если мне это и не нравится (вот сейчас с типами воюю).

Это всё прекрасно. Но, к сожалению, весьма плохо влияет на производительность труда.

T>Почему лисперы не считают себя пользователями своих же функций? Или считают? Если считают, то почему они не ограничивают себя, как других пользователей?

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

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, D. Mon, Вы писали:

А> Тем, что надо не забыть рекурсивно обойти все-все ссылки. А при преобразовании ast -> ast забыть это очень легко, типизация тут ничем не поможет.

А вот при преобразовании AST (Where ::: Let ::: a) -> AST a (лямбда-лифтинг, убирающий where и let) типизация очень помогает.

Чьё отсутствие меня и бесило, когда я занимался компиляторами на "профессиональной" основе и пользовался библиотекой на C++.

А> Допустим, такая задача — есть AST довольно сложного языка, в котором, кроме всего прочего, есть конструкции let id = expr in expr и function (args) = expr;
А> Надо написать преобразование этого AST, такое, что каждое локально введённое имя будет заменяться на сгенерённый уникальный идентификатор.
А> В варианте со всякими там ML придётся писать рекурсивный обход всего дерева, не забывая ни одного пути, на котором может втретиться значение типа expr.

http://www.cs.vu.nl/boilerplate/

A>И в каждом рекурсивном вызове тащить за собой ещё и окружение (таблицу переменования переменных).

Для чего есть SYB поверх монад.

A>Очень многословно выходит.

Не так уж и многословно.

A>В варианте с ast:visit это будет несколько строчек, где из всего AST будут упомянуты только изменяемые узлы. Всё остальное будет сгенерено автоматически.

Как и в варианте с SYB.

А> И такого типа простые преобразования деревьев в компиляторах очень типичны. Редко когда надо обойти всё дерево, чаще за один проход выполняется какое-то одно простое преобразование.

Преобразующее одну из сторон AST. Какую именно, хорошо бы отмечать типом.

Кстати, не рекомендую сравнивать с ML. Сравнивать с Хаскелем куда круче.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, thesz, Вы писали:

T>>Первый лиспер из множества участвовавших в обсуждениях с моим участием, что использует в своей работе систему типов.
А> Ну так я и Haskell использую, где-то треть кода пишется на нём.

Это же кардинально меняет дело!

T>>>>Мой вывод из всего этого таков: лисп остановился в развитии вместе с его пользователями.
А>>> Пользователи Лиспа не считают это направление "развитием". Есть более полезные для практики направления, куда стоит развиваться.
T>>Например?
А> Техники реализации DSLей с хитрой семантикой. В которую может входить и сложная система типов. А может и не входить.

А по какой причине сложная система типов может не входить в реализацию DSL с хитрой семантикой?

Может ли в реализацию DSL с хитрой семантикой входить простая система типов?

T>>Я не понимаю, зачем скатываться в "любят садомазо" на третьем или даже втором ответе.
А> Сравнение типизации с bondage&discipline — давнее и устоявшееся. Лично я ничего в этом обидного не вижу. Лупть по рукам надо всех, в том числе и меня самого. При определённых обстоятельствах, конечно же.

T>>Поскольку я признаю за собой право на ошибку и признаю за собой ответственность за ошибки в программе в целом, мне удобно, когда я сразу получаю по рукам. Даже если мне это и не нравится (вот сейчас с типами воюю).
А> Это всё прекрасно. Но, к сожалению, весьма плохо влияет на производительность труда.

Можно пример?

T>>Почему лисперы не считают себя пользователями своих же функций? Или считают? Если считают, то почему они не ограничивают себя, как других пользователей?
А> Ограничивают себя там, где вероятность ошибки велика, и оставляют себе свободу действий (и возможность быстрой разработки) там, где ошибка не страшна.

Вот "возможность быстрой разработки" меня смущает.

Поэтому я снова попрошу пример.

A>А пользователя, который не знает хорошо всех внутренностей системы, ограничивают везде, где только можно.

Если честно, то лично я не знаю особенностей работы системы практически никогда. Только моего узкого кусочка, что сейчас находится в разработке.

Здравствуйте, Turtle.BAZON.Group, Вы писали:

TBG>C++ 26 сек
TBG>Lisp (compiled) 37 сек
TBG>Lisp (interpreted) 64 сек

2 замечания: ты измеряешь полное время компиляции + время выполнения. И всё это в цикле. Гораздо интереснее один раз откомпилировать (и померять время), а потом выполнить (и измерить отдельно).

И второе: в компиляционном варианте метод `vmc-arith-op` выглядит так:

(defun vmc-arith-op (ip data-memory arith-f r1 r2)
  `(setf (aref ,data-memory ,ip)
         (funcall ,arith-f
                  (aref ,data-memory ,r1)
                  (aref ,data-memory ,r2))))

Имхо, лучше вместо непрямого вызова через "funcall" сразу "инлайнить" вызов нужной арифметической операции.
Что-то навроде:

(defun vmc-arith-op (ip data-memory arith-f r1 r2)
  `(setf (aref ,data-memory ,ip)
         (,arith-f
                  (aref ,data-memory ,r1)
                  (aref ,data-memory ,r2))))

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

Здравствуйте, Turtle.BAZON.Group, Вы писали:

TBG>Немножко ошибся. Забыл, что на другом компьютере считал. Итак:

TBG>C++ 26 сек
TBG>Lisp (compiled) 37 сек
TBG>Lisp (interpreted) 64 сек

На какой машине это запускалось и чем и как компилялся С++ вариант?
У меня он отрабатывает за 4,6 секунды. Ноутбук с Core 2 Duo 2.0 GHz, Windows Vista, Intel Compiler 7.1.

Неужто твоя машина в 5 раз медленнее?

DM>На какой машине это запускалось и чем и как компилялся С++ вариант?
DM>У меня он отрабатывает за 4,6 секунды.

Поправка: если тот же исходник компилю MSVC 6, то 3,75 секунды.

Здравствуйте, D. Mon, Вы писали:

TBG>>C++ 26 сек
TBG>>Lisp (compiled) 37 сек
TBG>>Lisp (interpreted) 64 сек

DM>На какой машине это запускалось и чем и как компилялся С++ вариант?
DM>У меня он отрабатывает за 4,6 секунды. Ноутбук с Core 2 Duo 2.0 GHz, Windows Vista, Intel Compiler 7.1.

DM>Неужто твоя машина в 5 раз медленнее?

Вот таким образом:

g++ -std=c++0x vm.cpp

Машина 1.2 ГГц где-то два ядра. 32-битных. Ну знатоки, подскажите ключи компиляции для оптимизации.

Здравствуйте, Turtle.BAZON.Group, Вы писали:

TBG>Машина 1.2 ГГц где-то два ядра. 32-битных. Ну знатоки, подскажите ключи компиляции для оптимизации.

По gcc не знаток, но как минимум ключик -O2 стоит написать. Или можно попробовать -O3, вроде активный инлайнинг именно там включается.

Здравствуйте, D. Mon, Вы писали:

DM>По gcc не знаток, но как минимум ключик -O2 стоит написать. Или можно попробовать -O3, вроде активный инлайнинг именно там включается.

В корку падает.

Здравствуйте, Turtle.BAZON.Group, Вы писали:

TBG>В корку падает.

Кто и когда?

Здравствуйте, Аноним, Вы писали:

T>>Здесь присутствуют два бывших Лисповика, vshabanov и lomeo, оба покинули его и из-за невозможности нормального сравнения с образцом в том числе.
А> Интересно было бы послушать, чего именно им не хватило.

Ну, я не "лисповик", а schemer, CL баловался постольку-поскольку.

Если кратко — не хватало статической типизации. Субъективно — на Haskell, с которым я тогда был знаком меньше, разработка была быстрее.

Большинство из того, что мне нравилось в scheme, есть или не нужно (решаются схожие задачи по другому) в Haskell. В том числе и макросы. Это не к вопросу о Тьюринг-полноте, разумеется, а к вопросу об удобстве.

О Qi знаю. Не понимаю зачем он. По моему, сила лиспа в динамике в том числе.

P.S. Scheme мне очень нравится и я до сих пор иногда (правда, всё реже) её использую.

Здравствуйте, thesz, Вы писали:

A>>В варианте с ast:visit это будет несколько строчек, где из всего AST будут упомянуты только изменяемые узлы. Всё остальное будет сгенерено автоматически.

T>Как и в варианте с SYB.

Тут такой прикол — в ast:visit, насколько я понял, будет сгенерен эффективный код доступа к полю структуры, а в SYB — нет (cast-ы будут), разве что на TH его переписать.

Здравствуйте, lomeo, Вы писали:

L>Здравствуйте, thesz, Вы писали:

A>>>В варианте с ast:visit это будет несколько строчек, где из всего AST будут упомянуты только изменяемые узлы. Всё остальное будет сгенерено автоматически.
T>>Как и в варианте с SYB.
L>Тут такой прикол — в ast:visit, насколько я понял, будет сгенерен эффективный код доступа к полю структуры, а в SYB — нет (cast-ы будут), разве что на TH его переписать.

И это никак не лечится путём переписывания и оптимизаций?..

Можно, вообще, представить алгоритм, который оптимизирует SYB код до кода ast:visit? Разворачиванием словарей классов, например.