Здравствуйте, Аноним, Вы писали:
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
Мой вывод из всего этого таков: лисп остановился в развитии вместе с его пользователями. Вместо поиска путей конструктивных ограничений (Haskell, Agda2), его пользователи продолжают использовать его гибкость. Любые попытки внести такие ограничения в Лисп даже в виде расширений не используются в реальной работе, они используются только в рекламных целях и в целях поддержания огня священных войн.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[22]: Как написать виртуальную машину на LISP
От:
Аноним
Дата:
13.08.09 10:58
Оценка:
Здравствуйте, 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.
Re[20]: Как написать виртуальную машину на LISP
От:
Аноним
Дата:
13.08.09 11:22
Оценка:
Здравствуйте, 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@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ей, которые лисперы пользователям дают. И не по той причине, что пользователи любят садомазо, а чтоб им, пользователям, по ручкам шаловливым вовремя настучать, даже если им это и не понравится.
Я не понимаю, зачем скатываться в "любят садомазо" на третьем или даже втором ответе.
Тем не менее, я продолжу.
Я считаю себя пользователем своих же творений.
Как только я написал функцию, я намерен её использовать.
Поскольку я признаю за собой право на ошибку и признаю за собой ответственность за ошибки в программе в целом, мне удобно, когда я сразу получаю по рукам. Даже если мне это и не нравится (вот сейчас с типами воюю).
Почему лисперы не считают себя пользователями своих же функций? Или считают? Если считают, то почему они не ограничивают себя, как других пользователей?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[22]: Как написать виртуальную машину на LISP
От:
Аноним
Дата:
13.08.09 12:32
Оценка:
Здравствуйте, 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. Сравнивать с Хаскелем куда круче.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, thesz, Вы писали:
T>>Первый лиспер из множества участвовавших в обсуждениях с моим участием, что использует в своей работе систему типов. А> Ну так я и Haskell использую, где-то треть кода пишется на нём.
Это же кардинально меняет дело!
T>>>>Мой вывод из всего этого таков: лисп остановился в развитии вместе с его пользователями. А>>> Пользователи Лиспа не считают это направление "развитием". Есть более полезные для практики направления, куда стоит развиваться. T>>Например? А> Техники реализации DSLей с хитрой семантикой. В которую может входить и сложная система типов. А может и не входить.
А по какой причине сложная система типов может не входить в реализацию DSL с хитрой семантикой?
Может ли в реализацию DSL с хитрой семантикой входить простая система типов?
T>>Я не понимаю, зачем скатываться в "любят садомазо" на третьем или даже втором ответе. А> Сравнение типизации с bondage&discipline — давнее и устоявшееся. Лично я ничего в этом обидного не вижу. Лупть по рукам надо всех, в том числе и меня самого. При определённых обстоятельствах, конечно же.
T>>Поскольку я признаю за собой право на ошибку и признаю за собой ответственность за ошибки в программе в целом, мне удобно, когда я сразу получаю по рукам. Даже если мне это и не нравится (вот сейчас с типами воюю). А> Это всё прекрасно. Но, к сожалению, весьма плохо влияет на производительность труда.
Можно пример?
T>>Почему лисперы не считают себя пользователями своих же функций? Или считают? Если считают, то почему они не ограничивают себя, как других пользователей? А> Ограничивают себя там, где вероятность ошибки велика, и оставляют себе свободу действий (и возможность быстрой разработки) там, где ошибка не страшна.
Вот "возможность быстрой разработки" меня смущает.
Поэтому я снова попрошу пример.
A>А пользователя, который не знает хорошо всех внутренностей системы, ограничивают везде, где только можно.
Если честно, то лично я не знаю особенностей работы системы практически никогда. Только моего узкого кусочка, что сейчас находится в разработке.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
2 замечания: ты измеряешь полное время компиляции + время выполнения. И всё это в цикле. Гораздо интереснее один раз откомпилировать (и померять время), а потом выполнить (и измерить отдельно).
И второе: в компиляционном варианте метод `vmc-arith-op` выглядит так:
Здравствуйте, 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.
Здравствуйте, 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-битных. Ну знатоки, подскажите ключи компиляции для оптимизации.
Здравствуйте, D. Mon, Вы писали:
DM>По gcc не знаток, но как минимум ключик -O2 стоит написать. Или можно попробовать -O3, вроде активный инлайнинг именно там включается.
Здравствуйте, Аноним, Вы писали:
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? Разворачиванием словарей классов, например.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)