Здравствуйте, Andrei F., Вы писали:
AF>Объясните "на пальцах", на наглядных примерах?
Это (по крайней мере, один из смыслов понятия), построение семантической модели кода (потоки данных, потоки управления) без его фактического выполнения, т.е. путем анализа самого кода (скорее AST, насколько я понимаю). Применяется при оптимизациях (я хз как именно) и при статическом анализе безопасности кода (анализируются пути флуктуаций потенциально-malformed входных данных, и если они попадают на выход без изменений, либо определенным образом влияют на потоки управления, то achtung, тут скорее всего уязвимость).
VGn>>"на пальцах" — абстрактная интерпретация понятия "абстрактная интерпретация" KV>Сферического кода в вакууме?
Ну на то она и "абстрактная". А вообще я конечно имел в виду "интерпретацию" в смысле "разъяснение", который вообще-то является первоначальным общим смыслом слова без углубления в профессиональные слэнги.
Частичные вычисления позволяют сократить код путем подстановки заранее известных данных в программу. Но существует ещё более продвинутая техника, которая может оптимизировать код намного сильнее, и частичные вычисления являются её подмножеством — суперкомпиляция.
Компилятор, который математически моделирует выполнение программы, а затем использует эту модель для производства более эффективной программы называется суперкомпилятором (англ. supervising compiler).
Интересно, что авторство этого термина (и сопутствующих исследований) принадлежит нашему соотечественнику — Валентину Турчину. Он также разработал язык Рефал, демонстрирующий концепт суперкомпиляции (язык очень стар и основан на переписывании термов).
Суперкомпиляцию еще называют «абстрактной интерпретацией» программ. У Турчина это обозначается термином «прогонка» — или «driving» в англоязычных публикациях.
При прогонке компилятор строит дерево процессов программы — граф всех возможных состояний программы с ребрами-переходами между ними.
Здравствуйте, Andrei F., Вы писали:
AF>Объясните "на пальцах", на наглядных примерах?
Для наглядного примера возьмем язык выражений с таким AST:
data Expr = Add Expr Expr | Const Int | Less Expr Expr
Напишем интерпретатор таких выражений:
data Value = VBool Bool | VInt Int
eval :: Expr -> Value
eval (Const x) = VInt x
eval (Add x y) =
case (eval x, eval y) of
(VInt a, VInt b) -> VInt (a + b)
_ -> error"Runtime type error"
eval (Less x y) =
case (eval x, eval y) of
(VInt a, VInt b) -> VBool (a < b)
_ -> error"Runtime type error"
Теперь напишем проверку типов для этих выражений:
data Type = TBool | TInt
typeOf :: Expr -> Type
typeOf (Const _) = TInt
typeOf (Add x y) =
case (typeOf x, typeOf y) of
(TInt, TInt) -> TInt
_ -> error"Compile error"
typeOf (Less x y) =
case (typeOf x, typeOf y) of
(TInt, TInt) -> TBool
_ -> error"Compile error"
Функции eval и typeOf очень похожи. В то время как eval вычисляет значение выражения, typeOf вычисляет тип выражения. Типы можно рассматривать как разновидность значений, которые вычисляются во время компиляции. Кроме того, они аппроксимируют значения времени выполнения — для VInt 42, VInt 7, VInt 13 аппроксимацией будет тип TInt, для VBool True и для VBool False аппроксимацией будет TBool. Другими словами, это частично известное значение — мы знаем, к какому подмножеству будет относиться результат выполнения программы еще до запуска.
Если продолжать в том же духе, можно увидеть, что компиляция, оптимизация, статическая верификация и прочие -ации для нашего языка будут подобными интепретаторами с типом Expr -> <что-то>.
Насколько я понимаю, абстрактная интерпретация — это вышеизложенная идея с изрядной дозой матана, теории доменов Даны Скотта, жаб и червей.
Re[2]: Что такое "абстрактная интерпретация", как я ее поним
Здравствуйте, palm mute, Вы писали:
PM>Насколько я понимаю, абстрактная интерпретация — это вышеизложенная идея с изрядной дозой матана, теории доменов Даны Скотта, жаб и червей.
Про жаб и червей можно поподробнее? (Уж больно названия внезапные).
Перекуём баги на фичи!
Re[3]: Что такое "абстрактная интерпретация", как я ее поним
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, palm mute, Вы писали:
PM>>Насколько я понимаю, абстрактная интерпретация — это вышеизложенная идея с изрядной дозой матана, теории доменов Даны Скотта, жаб и червей.
К>Про жаб и червей можно поподробнее? (Уж больно названия внезапные).
Магия вуду в действии. Ингредиенты «порошка зомби»:
...
На втором месте в списке ингредиентов «порошка зомби» стоит ядовитая жаба Bufo marinus. Для получения её яда колдун держит одну ночь жабу в банке вместе с морским червём, который кусает её и заставляет вырабатывать яд. В результате каратоидные железы жабы вырабатывают большое количество активных химических веществ — буфотеин, буфо-гении и буфотоксин. Утром жабу и червя убивают, сушат на солнце и тоже растирают в порошок.
...
Re[3]: Что такое "абстрактная интерпретация", как я ее поним
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, Кодт, Вы писали:
К>>Про жаб и червей можно поподробнее? (Уж больно названия внезапные).
PM>Это недо-мем, в моей эпсилон-окрестности в ЖЖ.
Но имхо у того же metaclass это обычно жабы (Java) и змеи (Python)
Re[5]: Что такое "абстрактная интерпретация", как я ее поним
Здравствуйте, Курилка, Вы писали:
К>>>Про жаб и червей можно поподробнее? (Уж больно названия внезапные).
PM>>Это недо-мем, в моей эпсилон-окрестности в ЖЖ.
К>Но имхо у того же metaclass это обычно жабы (Java) и змеи (Python)
Там и черви, и ад, и израиль. Но это уже просто вопиющий оффтопик.
Re[4]: Что такое "абстрактная интерпретация", как я ее поним
Здравствуйте, deniok, Вы писали:
К>>Про жаб и червей можно поподробнее? (Уж больно названия внезапные). D>Магия вуду в действии. Ингредиенты «порошка зомби»:
Тюю. А я-то думал, будет продолжение линз и бананов
Перекуём баги на фичи!
Re[5]: Что такое "абстрактная интерпретация", как я ее поним
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, deniok, Вы писали:
К>>>Про жаб и червей можно поподробнее? (Уж больно названия внезапные). D>>Магия вуду в действии. Ингредиенты «порошка зомби»: К>Тюю. А я-то думал, будет продолжение линз и бананов
Поскольку термины будоражат, можно попробовать их использовать с толком в будущих построениях
Здравствуйте, Andrei F., Вы писали:
AF>Объясните "на пальцах", на наглядных примерах?
Ну ежели без программирования
Вместо "Саша вые...л Машу после бутылки Советского..." — "Гетеросексуальный половой акт в состоянии алкогольного токсикоза" — это "абстракция" определенного факта.
А вывод из этого "Пьяная баба — себе (а не то, что вы подумали) не хозяйка" — это интерпретация абстракции данного факта (плюс немножечко анализа, конечно).
Обратите внимание, интерпретация (и анализ, дада) самого факта была бы "Маша после Шампанского возле Саши — себе не хозяйка".
Собственно, абстракция — это размен точности на размер охвата.
А интерпретация — по идее должно быть "тождественное преобразование информации",
но сплошь и рядом к интерпретации примешивается еще и анализ с последующей абстракцией результатов.
В результате чего плодятся узкоприменимые закономерности, вроде приведенной выше "житейской мудрости" о пьяных женщинах.