Корректность компилятора - Compiler correctness

В вычисление, корректность компилятора это раздел информатики, который пытается показать, что компилятор ведет себя в соответствии со своим спецификация языка.[нужна цитата ] Методы включают разработку компилятора с использованием формальные методы и использование строгого тестирования (часто называемого проверкой компилятора) на существующем компиляторе.

Формальная проверка

Два основных формальная проверка подходы к установлению корректности компиляции - это подтверждение корректности компилятора для всех входных данных и подтверждение корректности компиляции конкретной программы (проверка перевода).

Корректность компилятора для всех входных программ

Проверка компилятора формальными методами включает длинную цепочку формальных, дедуктивная логика.[1] Однако, поскольку инструмент для поиска доказательства (средство доказательства теорем ) реализован программно и является сложным, с большой вероятностью будет содержать ошибки. Один из подходов заключался в использовании инструмента для проверки доказательства ( корректор ), который, поскольку он намного проще, чем средство поиска, с меньшей вероятностью будет содержать ошибки.

Ярким примером такого подхода является CompCert, который является формально проверенным оптимизирующим компилятором большого подмножества C99.[2][3][4]

Другой проверенный компилятор был разработан в проекте CakeML,[5]что устанавливает правильность существенного подмножества Стандартный ML язык программирования с использованием HOL (помощник проверки).

Другой подход к получению формально корректного компилятора - использование генерации компилятора, ориентированной на семантику.[6]

Проверка перевода: корректность компилятора для данной программы

В отличие от попытки доказать, что компилятор подходит для проверки перевода всех допустимых программ ввода[7]стремится автоматически установить, что данная программа ввода скомпилирована правильно. Доказательство правильной компиляции данной программы потенциально проще, чем доказательство правильности компилятора для всех программ, но все же требует символических рассуждений, потому что фиксированная программа может по-прежнему работать с произвольно большими входными данными и выполняться в течение сколь угодно долгого времени. Проверка перевода может повторно использовать существующую реализацию компилятора, генерируя для данной компиляции доказательство того, что компиляция была правильной. Проверка перевода может использоваться даже с компилятором, который иногда генерирует неправильный код, если этот неправильный код не проявляется для данная программа. В зависимости от входной программы проверка перевода может завершиться ошибкой (из-за того, что сгенерированный код неверен или метод проверки перевода слишком слаб, чтобы показать правильность). Однако, если проверка перевода прошла успешно, программа компилятора гарантированно верна для всех входных данных.

Тестирование

Тестирование представляет собой значительную часть усилий по доставке компилятора, но в стандартной литературе освещается сравнительно мало. Издание 1986 г. Ахо, Сетхи и Ульман есть одностраничный раздел о тестировании компилятора без именованных примеров.[8] В издании 2006 года отсутствует раздел о тестировании, но подчеркивается его важность: «Оптимизация компиляторов настолько сложна, что мы осмеливаемся сказать, что ни один оптимизирующий компилятор не является полностью безошибочным! Таким образом, самая важная цель при написании компилятора - сделать его правильным ».[9]Fraser & Hanson 1995 содержит краткий раздел о регрессионное тестирование; исходный код доступен.[10]Bailey & Davidson 2003 покрывает тестирование вызовов процедур[11]Ряд статей подтверждают, что во многих выпущенных компиляторах есть серьезные ошибки корректности кода.[12]Sheridan 2007, вероятно, самая последняя статья в журнале по общему тестированию компиляторов.[13] Для большинства целей наибольший объем доступной информации о тестировании компилятора - это Fortran[14] и Кобол[15] комплекты для проверки.

Дальнейшие распространенные методы тестирования компиляторов: расплывание[16] (который генерирует случайные программы, чтобы попытаться найти ошибки в компиляторе) и сокращение тестового примера (который пытается свести к минимуму найденный тестовый пример, чтобы его было легче понять).[17]

Смотрите также

Рекомендации

  1. ^ Де Милло, Р. А .; Lipton, R.J .; Перлис, А. Дж. (1979). «Социальные процессы и доказательства теорем и программ». Коммуникации ACM. 22 (5): 271–280. Дои:10.1145/359104.359106.
  2. ^ Лерой, X. (2006). «Формальная сертификация серверной части компилятора или: программирование компилятора с помощью Proof Assistant». Уведомления ACM SIGPLAN. 41: 42–54. Дои:10.1145/1111320.1111042.
  3. ^ Лерой, Ксавье (2009-12-01). «Формально проверенный серверный компонент компилятора». Журнал автоматизированных рассуждений. 43 (4): 363–446. arXiv:0902.2137. Дои:10.1007 / s10817-009-9155-4. ISSN  0168-7433.
  4. ^ "CompCert - компилятор CompCert C". compcert.inria.fr. Получено 2017-07-21.
  5. ^ «CakeML: проверенная реализация машинного обучения».
  6. ^ Стефан Диль, Генерация компиляторов и абстрактных машин, ориентированная на естественную семантику, Формальные аспекты вычислений, Vol. 12 (2), Springer Verlag, 2000. Дои:10.1007 / PL00003929
  7. ^ Пнуэли, Амир; Сигель, Майкл; Зингерман, Эли. Проверка перевода. Инструменты и алгоритмы для построения и анализа систем, 4-я Международная конференция, TACAS '98.
  8. ^ Компиляторы: принципы, методы и инструменты, инфра 1986, стр. 731.
  9. ^ там же, 2006, стр. 16.
  10. ^ Кристофер Фрейзер; Дэвид Хэнсон (1995). Компилятор C с возможностью перенастройки: разработка и реализация. Бенджамин / Каммингс Паблишинг. ISBN  978-0-8053-1670-4., стр. 531–3.
  11. ^ Марк У. Бейли; Джек В. Дэвидсон (2003). «Автоматическое обнаружение и диагностика ошибок в сгенерированном коде для вызова процедур» (PDF). IEEE Transactions по разработке программного обеспечения. 29 (11): 1031–1042. CiteSeerX  10.1.1.15.4829. Дои:10.1109 / це.2003.1245304. Архивировано из оригинал (PDF) на 2003-04-28. Получено 2009-03-24., п. 1040.
  12. ^ Например., Кристиан Линдиг (2005). «Случайное тестирование соглашений о вызовах C» (PDF). Материалы шестого международного семинара по автоматизированной отладке.. ACM. ISBN  1-59593-050-7. Архивировано из оригинал (PDF) на 2011-07-11. Получено 2009-03-24., иЭрик Эйде; Джон Регер (2008). "Volatiles неправильно скомпилированы, и что с этим делать" (PDF). Материалы 7-й международной конференции ACM по встраиваемому ПО. ACM. ISBN  978-1-60558-468-3. Получено 2009-03-24.
  13. ^ Флэш Шеридан (2007). «Практическое тестирование компилятора C99 с использованием сравнения выходных данных» (PDF). Программное обеспечение: практика и опыт. 37 (14): 1475–1488. Дои:10.1002 / spe.812. Получено 2009-03-24. Библиография на http://pobox.com/~flash/compiler_testing_bibliography.html. Получено 2009-03-13. Отсутствует или пусто | название = (помощь).
  14. ^ "Источник пакета проверки Fortran". Получено 2011-09-01.
  15. ^ «Пакет проверки Source of Cobol». Получено 2011-09-01.
  16. ^ Чен, Ян; Groce, Алекс; Чжан, Чаоцян; Вонг, Вен-Кин; Папоротник, Сяоли; Эйде, Эрик; Регер, Джон (2013). Укрощение фаззеров компилятора. Материалы 34-й конференции ACM SIGPLAN по проектированию и реализации языков программирования. PLDI '13. Нью-Йорк, Нью-Йорк, США: ACM. С. 197–208. CiteSeerX  10.1.1.308.5541. Дои:10.1145/2491956.2462173. ISBN  9781450320146.
  17. ^ Регер, Джон; Чен, Ян; Cuoq, Паскаль; Эйде, Эрик; Эллисон, Чаки; Ян, Сюэцзюнь (2012). Сокращение тестовых примеров для ошибок компилятора C. Материалы 33-й конференции ACM SIGPLAN по проектированию и реализации языков программирования. PLDI '12. Нью-Йорк, Нью-Йорк, США: ACM. С. 335–346. Дои:10.1145/2254064.2254104. ISBN  9781450312059.