Кстати! Русские авторы с отсылками к русским авторам, на русской конференции... на английском языке. А на русском того же самого нет? Моё гугл-фу оказалось бессильно, нашёл только другие работы их же.
Статья интересная, но возможно, что я понял её неправильно. Суперкомпиляция позволяет рожать и применять теоремы равенства, это всё хорошо... но когда компилятор должен остановиться и начать уже компилировать, а не исследовать код?
Для популярной (например, стандартной) библиотеки автоматический вывод и создание ёмкого (а то и исчерпывающего) каталога правил переписывания - дело полезное. Делается единожды. Ещё и библиотеку можно построить так, чтобы упростить жизнь анализатору кода.
А в конкретной программе, да ещё и оснащённой всякими ловушками ("а давайте mk сделаем на последовательности Коллаца")?
Потому и задал свой наивный, но частично риторический вопрос.
Там рассматриваются программы с ловушками, почему у phase ordering problem нет решения, и многое другое. Автор с этими ловушками намучился достаточно, когда над Blitz++ работал. Душеспасительное чтение, право слово.
Что же до английского языка, то автор Илья Ключников осел в facebook, языками занимается (по-моему, неправильно). Статьи на английском ему для этого нужны были.
Касательно же суперкомпиляции, то она, в её изводе под названием "дистилляция" способна, в принципе, улучшить квадратичный алгоритм до линейного, Глядишь, и Коллаца решит. ;)
Если у нас есть каталог равенств программы (включая равенство вычислений их результату), то структурное равенство (стандартный вариант deriving) будет тривиально O(1). Но это всё равно требует нормализации программы, чтобы mk n было равно mk (n+1-1). А оптимизация и есть нормализация, в некотором смысле.
Вот, пойду читать диссертацию Клиффорда Клика, начинается она весело, авось не усну :)
Просто, когда какая-то тема обозначена коротким мазком, sapienti sat, то вот те, кто не sapienti, - я, например, - оказываются очень даже не sat, но заинтригованы.
https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_guide/rewrite-rules.html
https://github.com/ghc/ghc/blob/182df90e4d1f652c3d078294921805b9b982671b/libraries/base/Data/OldList.hs#L776
https://github.com/ghc/ghc/blob/182df90e4d1f652c3d078294921805b9b982671b/libraries/base/Data/Maybe.hs#L296
https://github.com/haskell/vector/blob/e0c391c70c57ac1c4b6dd8260c9a5502acaae15e/vector/src/Data/Vector/Generic.hs#L271
И вы прочтите статью-то. Она интересная!
Reply
Статью-то я прочёл.
Кстати! Русские авторы с отсылками к русским авторам, на русской конференции... на английском языке. А на русском того же самого нет? Моё гугл-фу оказалось бессильно, нашёл только другие работы их же.
Статья интересная, но возможно, что я понял её неправильно. Суперкомпиляция позволяет рожать и применять теоремы равенства, это всё хорошо... но когда компилятор должен остановиться и начать уже компилировать, а не исследовать код?
Для популярной (например, стандартной) библиотеки автоматический вывод и создание ёмкого (а то и исчерпывающего) каталога правил переписывания - дело полезное. Делается единожды. Ещё и библиотеку можно построить так, чтобы упростить жизнь анализатору кода.
А в конкретной программе, да ещё и оснащённой всякими ловушками ("а давайте mk сделаем на последовательности Коллаца")?
Потому и задал свой наивный, но частично риторический вопрос.
Reply
У автора Blitz++ есть диссертация про компиляторы: https://www.researchgate.net/publication/2869498_Active_Libraries_and_Universal_Languages (но лучше на citeseer поискать)
Там рассматриваются программы с ловушками, почему у phase ordering problem нет решения, и многое другое. Автор с этими ловушками намучился достаточно, когда над Blitz++ работал. Душеспасительное чтение, право слово.
Кодогенератор ghc работает в схожем ключе, по этой схеме: https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf
Что же до английского языка, то автор Илья Ключников осел в facebook, языками занимается (по-моему, неправильно). Статьи на английском ему для этого нужны были.
Касательно же суперкомпиляции, то она, в её изводе под названием "дистилляция" способна, в принципе, улучшить квадратичный алгоритм до линейного, Глядишь, и Коллаца решит. ;)
Если у нас есть каталог равенств программы (включая равенство вычислений их результату), то структурное равенство (стандартный вариант deriving) будет тривиально O(1). Но это всё равно требует нормализации программы, чтобы mk n было равно mk (n+1-1). А оптимизация и есть нормализация, в некотором смысле.
Reply
Ну прям неинтересно.
Вот, пойду читать диссертацию Клиффорда Клика, начинается она весело, авось не усну :)
Просто, когда какая-то тема обозначена коротким мазком, sapienti sat, то вот те, кто не sapienti, - я, например, - оказываются очень даже не sat, но заинтригованы.
Reply
Leave a comment