#prog #article
Не смотря на то, что исторически property-based testing применялось для тестирования чистых функций, технически ничто не мешает тестировать и функции с некоторыми побочными эффектами. Тем не менее, при переносе этого подхода на компиляторы возникает очевидная проблема: все сколько-нибудь полезные программы обладают побочными эффектами, и языки далеко не всегда определяют порядок вычислений достаточно точно, чтобы предсказать вывод обладающей побочными эффектами фрагмента программы исключительно по исходному коду. Одним из таких языков является OCaml: среди его реализаций есть как те, которые вычисляют порядок аргументов слева направо, так и те, которые вычисляют справа налево. Это делает генерацию исходных программ с целью тестирования несколько затруднительной, поскольку вывод даже корректно скомпилированной программы может зависеть от реализации.
В статье
Effect-Driven QickChecking of Compilers авторы решили эту проблему, спроектировав генератор, который создаёт лишь программы, вывод которых не зависит от порядка вычислений. Сделали они это путём введения рудиментарной системы эффектов (попутно доказав её корректность) и архитектуры генератора, позволяющей на ранних этапах генерации отбрасывать альтернативы, которые бы привели к зависимости от конкретного порядка вычислений. Вместе с генератором они также спроектировали минификатор, позволяющий минифицировать программы с сохранением полезного свойства независимости (впрочем, это получилось скорее автоматически ввиду того, что это свойство было закодировано в эффектах, а элементарные операции минификации сохраняли тип).
Генератор получился достаточно ограниченным. Он генерирует только весьма узкое подмножество всех программ (в частности, никакого полиморфизма, ни по типам, не по эффектам), и, в частности, генерирует только программы, которые гарантированно завершаются. Вдобавок, введённая система эффектов отслеживает исключительно сам факт наличия побочного эффекта, но не его конкретную разновидность. Тем не менее, даже такое ограниченный инструмент оказался полезным на практике. Используя реализацию QuickCheck для OCaml для свойства "для любой программы, сгенерированной генератором, вывод этой программы при использовании двух разных компиляторов одинаков", авторы смогли обнаружить четыре новых бага, а также найти два уже ранее известных.
P. S.: единственное, что меня смущает — это лемма об ослаблении контекста типизации в разделе, в котором доказывается корректность системы типов с эффектами:
If
∆;Γ,(x : τ′),Γ′ ⊢ e : τ & φ and τ′′ ⊑ τ′
then
∆;Γ,(x : τ′′),Γ′ ⊢ e : τ & φ
или, если словами, произвольный тип внутри контекста типизации можно заменить на тип с более слабым эффектом. Лично мне это не кажется очевидным от слова совсем.
