M
для них тоже аот есть
Так а почему не используется?
Size: a a a
2020 February 26
E
я вообще никаким образом не пересекаюсь с ними и не интересуюсь, знаю что там много людей и они очень активно работают)
E
У меня такой вопрос. Связан с компиляторами, так что, думаю, по теме.
Вот есть формальные грамматики, в них есть терминалы и нетерминалы. Там через правила задаются преобразования изначального нетерминала.
А что если всё что у нас имеется - это терминалы и правила их преобразования? Как это называется?
Пример, собственно ради которого я и спрашиваю - это преобразование математических выражений. Вот есть у нас формула, или можно сказать "двустороннее правило": sin(2*x) <-> 2*sin(x)*cos(x), мы по этим формулам делаем допустимые преобразования из одного вида в другой, приходя к результату.
Просто интересно как такое может называться и насколько это исследовали. Может есть уже какие-то математические и программистские правила для описания подобных преобразований (ну как с формальными грамматиками).
Вот есть формальные грамматики, в них есть терминалы и нетерминалы. Там через правила задаются преобразования изначального нетерминала.
А что если всё что у нас имеется - это терминалы и правила их преобразования? Как это называется?
Пример, собственно ради которого я и спрашиваю - это преобразование математических выражений. Вот есть у нас формула, или можно сказать "двустороннее правило": sin(2*x) <-> 2*sin(x)*cos(x), мы по этим формулам делаем допустимые преобразования из одного вида в другой, приходя к результату.
Просто интересно как такое может называться и насколько это исследовали. Может есть уже какие-то математические и программистские правила для описания подобных преобразований (ну как с формальными грамматиками).
прочитал это полотно и не понял сути вопроса
E
это про банальные пипхолы?
LW
У меня такой вопрос. Связан с компиляторами, так что, думаю, по теме.
Вот есть формальные грамматики, в них есть терминалы и нетерминалы. Там через правила задаются преобразования изначального нетерминала.
А что если всё что у нас имеется - это терминалы и правила их преобразования? Как это называется?
Пример, собственно ради которого я и спрашиваю - это преобразование математических выражений. Вот есть у нас формула, или можно сказать "двустороннее правило": sin(2*x) <-> 2*sin(x)*cos(x), мы по этим формулам делаем допустимые преобразования из одного вида в другой, приходя к результату.
Просто интересно как такое может называться и насколько это исследовали. Может есть уже какие-то математические и программистские правила для описания подобных преобразований (ну как с формальными грамматиками).
Вот есть формальные грамматики, в них есть терминалы и нетерминалы. Там через правила задаются преобразования изначального нетерминала.
А что если всё что у нас имеется - это терминалы и правила их преобразования? Как это называется?
Пример, собственно ради которого я и спрашиваю - это преобразование математических выражений. Вот есть у нас формула, или можно сказать "двустороннее правило": sin(2*x) <-> 2*sin(x)*cos(x), мы по этим формулам делаем допустимые преобразования из одного вида в другой, приходя к результату.
Просто интересно как такое может называться и насколько это исследовали. Может есть уже какие-то математические и программистские правила для описания подобных преобразований (ну как с формальными грамматиками).
2*x это уже нечто, что описывается нетерминалом
E
sin(2*x) <-> 2*sin(x)*cos(x)
можно добавить в гцц одним движением. вопрос: нужно ли
можно добавить в гцц одним движением. вопрос: нужно ли
E
и ответ: ненужно
AK
и ответ: ненужно
Скорее всего речь была не про оптимизацию
E
хотя т.е. в теории sin(2*x) можно разложить чтобы поискать CSE на компоненты
AK
А просто про преобразование выражений
LW
и ответ: ненужно
Mathematica и другие подобные программы делают это постоянно.
E
Mathematica и другие подобные программы делают это постоянно.
пусть они и дальше этим занимаются 😊
SM
У меня такой вопрос. Связан с компиляторами, так что, думаю, по теме.
Вот есть формальные грамматики, в них есть терминалы и нетерминалы. Там через правила задаются преобразования изначального нетерминала.
А что если всё что у нас имеется - это терминалы и правила их преобразования? Как это называется?
Пример, собственно ради которого я и спрашиваю - это преобразование математических выражений. Вот есть у нас формула, или можно сказать "двустороннее правило": sin(2*x) <-> 2*sin(x)*cos(x), мы по этим формулам делаем допустимые преобразования из одного вида в другой, приходя к результату.
Просто интересно как такое может называться и насколько это исследовали. Может есть уже какие-то математические и программистские правила для описания подобных преобразований (ну как с формальными грамматиками).
Вот есть формальные грамматики, в них есть терминалы и нетерминалы. Там через правила задаются преобразования изначального нетерминала.
А что если всё что у нас имеется - это терминалы и правила их преобразования? Как это называется?
Пример, собственно ради которого я и спрашиваю - это преобразование математических выражений. Вот есть у нас формула, или можно сказать "двустороннее правило": sin(2*x) <-> 2*sin(x)*cos(x), мы по этим формулам делаем допустимые преобразования из одного вида в другой, приходя к результату.
Просто интересно как такое может называться и насколько это исследовали. Может есть уже какие-то математические и программистские правила для описания подобных преобразований (ну как с формальными грамматиками).
в общем виде, это просто система переписывания? но они канонически недетерминистичны, что вряд ли на практике встречается. Пригодилась бы информация о том по какому правилу такие преобразования происходят
PS
в общем виде, это просто система переписывания? но они канонически недетерминистичны, что вряд ли на практике встречается. Пригодилась бы информация о том по какому правилу такие преобразования происходят
Тут действительно напрашиваются системы переписывания. И еще вопрос — какую из них считать за канон ;)
Короче говоря, гуглить полезно по "term rewriting" и "equational language".
Короче говоря, гуглить полезно по "term rewriting" и "equational language".
M
sin(2*x) <-> 2*sin(x)*cos(x) и прочие сложные штуки в качестве пипхолов действительно не нужны. Для этого есть супероптимизиаторы такие как souper. Они сделают все намного лучше, а главное ты явно будеш контроллировать пайплайн и решать а надо ли тебе это вообще
PS
MaxGraey
sin(2*x) <-> 2*sin(x)*cos(x) и прочие сложные штуки в качестве пипхолов действительно не нужны. Для этого есть супероптимизиаторы такие как souper. Они сделают все намного лучше, а главное ты явно будеш контроллировать пайплайн и решать а надо ли тебе это вообще
Для сложных штук нужны, все-таки, предметно-ориентированные наборы правил. А souper не масштабируется и сложному его научить тоже сложно :)
M
Для сложных штук нужны, все-таки, предметно-ориентированные наборы правил. А souper не масштабируется и сложному его научить тоже сложно :)
Что значит не масштабируется?
M
Ему как бы и не нужны вереницы DSL правил, он их сам выводит
PS
MaxGraey
Что значит не масштабируется?
Это означает, что сама по себе задача, с которой имеет дело решатель — NP-полная. А алгоритмы для таких задач не масштабируются в общем случае. И еще отдельный вопрос — как представить в SMT-решателе тригонометрию :)
FO
Это означает, что сама по себе задача, с которой имеет дело решатель — NP-полная. А алгоритмы для таких задач не масштабируются в общем случае. И еще отдельный вопрос — как представить в SMT-решателе тригонометрию :)
как экспоненты, разумеется