В информатике , строгость анализ относится к любому алгоритму , используемый , чтобы доказать , что функция в нестрогом функциональном программировании языка строга в одном или несколько из своих аргументов. Эта информация полезна для компиляторов, потому что строгие функции могут быть скомпилированы более эффективно. Таким образом, если во время компиляции доказано, что функция является строгой (с использованием анализа строгости), ее можно скомпилировать для использования более эффективного соглашения о вызовах без изменения значения включающей программы.
Обратите внимание, что функция f
считается расходящейся, если она возвращает: с точки f
зрения эксплуатации, это означало бы, что это либо вызывает ненормальное завершение включающей программы (например, сбой с сообщением об ошибке), либо бесконечный цикл. Понятие «дивергенция» имеет важное значение, потому что строгая функция - это функция, которая всегда расходится, когда дан аргумент, который расходится, тогда как ленивая (или нестрогая) функция - это функция, которая может или не может расходиться, когда ей дан такой аргумент. Анализ строгости пытается определить «свойства дивергенции» функций, которые, таким образом, идентифицируют некоторые функции, которые являются строгими.
Подходы к анализу строгости
Прямая абстрактная интерпретация
Анализ строгости можно охарактеризовать как прямую абстрактную интерпретацию, которая аппроксимирует каждую функцию в программе функцией, которая отображает свойства дивергенции аргументов на свойства дивергенции результатов. В классическом подходе, впервые предложенном Аланом Майкрофтом , абстрактная интерпретация использовала двухточечную область с 0, обозначающим множестворассматривается как подмножество аргумента или возвращаемого типа, а 1 обозначает все значения в типе. [1]
Анализ спроса
Glasgow Haskell Compiler (GHC) использует обратную абстрактную интерпретацию , известную как анализ спроса , чтобы выполнить строгость анализа, а также другие анализы программы. При анализе спроса каждая функция моделируется функцией от требований значения к результату до требований значения к аргументам. Функция является строгой в аргументе, если требование ее результата приводит к спросу на этот аргумент. [2]
Прогнозный анализ строгости
Анализ строгости на основе проекций, представленный Филипом Уодлером и Р. Дж. М. Хьюзом , использует проекции строгости для моделирования более тонких форм строгости, таких как строгость в аргументе списка. (Напротив, анализ спроса GHC может моделировать строгость только в пределах типов продуктов , то есть типов данных, которые имеют только один конструктор .) Функция считается строгим, если , где - это проекция, которая оценивает свой аргумент списка. [3]
В 1980-е годы было проведено большое количество исследований по анализу строгости.
Рекомендации
- ^ Майкрофт, Алан (1980). «Теория и практика преобразования вызова по потребности в вызов по значению». Конспект лекций по информатике: Учеб. 4-й международный Symp. по программированию, Vol. 83 . Springer-Verlag.
- ^ «Комментарий GHC: анализатор спроса в GHC» . Проверено 12 февраля 2014 .
- ^ Wadler, P .; Р. Дж. М. Хьюз (1987). «Прогнозы для анализа строгости». Функциональное программирование и компьютерная архитектура; Воронежская 274 . Springer-Verlag.