Что мы знаем о достоверно правильных программах?

37

Постоянно растущая сложность компьютерных программ и все более важное положение, которое компьютеры занимают в нашем обществе, заставляют меня задуматься, почему мы до сих пор не используем все вместе языки программирования, на которых вам необходимо предоставить формальное доказательство правильности работы вашего кода.

Я считаю, что этот термин является «сертифицирующим компилятором» (я нашел его здесь ): компилятором, компилирующим язык программирования, на котором нужно не только писать код, но также указывать спецификацию кода и доказывать, что код придерживается спецификация (или используйте для этого автоматический прувер).

При поиске в интернете я обнаружил только проекты, которые используют очень простой язык программирования или неудачные проекты, которые пытаются адаптировать современные языки программирования. Это приводит меня к моему вопросу:

Существуют ли сертифицирующие компиляторы, реализующие полноценный язык программирования, или это очень сложно / теоретически невозможно?

Кроме того, я еще не видел ни одного класса сложности, включающего доказуемые программы, такие как «класс всех языков, разрешимых машиной Тьюринга, для которых существует доказательство того, что эта машина Тьюринга останавливается», который я назову ProvableR , как аналог R , множество рекурсивных языков.

Я вижу преимущества изучения такого класса сложности: например, для ProvableR проблема разрешима (я даже предполагаю, что определенное очевидным образом, будет самым большим классом языков, для которого он разрешима). Кроме того, я сомневаюсь, что мы исключили бы любые практически полезные программы: кто будет использовать программу, если вы не можете доказать, что она заканчивается?ProvableRE

Итак, мой второй вопрос:

Что мы знаем о классах сложности, которые требуют, чтобы их языки содержали определенные свойства?

Алекс тен Бринк
источник
1
Компилятор может перечислить все возможные доказательства длины i, позволяя переходить от 1 к бесконечности, пока не найдет доказательство остановки программы. Если мы требуем, чтобы ввод для компилятора был остановлен, то компилятор всегда найдет это доказательство. Так как проблема остановки неразрешима, мы должны заключить, что есть программы, которые останавливают, но никаких доказательств этому нет. Важным моментом является то, что программы не могут выяснить, существует ли доказательство, а не то, что они не могут найти доказательство, если оно существует.
Алекс тен Бринк
3
Я думаю, что вы должны разделить их. Это разные вопросы с разными ответами.
Марк Рейтблатт
4
По первому вопросу влиятельная статья - «Социальные процессы и доказательства теорем и программ», portal.acm.org/citation.cfm?id=359106
Колин Маккуиллан,
1
Проверка программы неразрешима. Итак, одна проблема состоит в том, чтобы сказать, что является хорошим решением. См. Cstheory.stackexchange.com/questions/4016/…
Раду ГРИГОР
2
@Colin: эта статья заслуживает прочтения из-за анализа доказательств, но ее прогнозы были сфальсифицированы. Сегодня у нас есть достоверно правильные компиляторы, ядра операционных систем, сборщики мусора и базы данных, которые, по их прогнозам, невозможны. Уловка, чтобы уклониться от их критики, состояла в том, чтобы избежать человеческой проверки деталей низкоуровневых формальных доказательств, но использовать машинную проверку доказательств и использовать людей для проверки проверки. Отношение Ноама к теории типов - это то, где находится современное состояние, в котором императивные программы остаются в некотором роде, поскольку теория типов функционирует.
Нил Кришнасвами

Ответы:

28

«Сертифицирующий компилятор» обычно означает что-то немного другое: это означает, что у вас есть компилятор, который может доказать, что машинный код, который он испускает, правильно реализует семантику высокого уровня. То есть это доказательство отсутствия ошибок компилятора. Программы, которые люди дают компилятору, могут все еще быть неправильными, но компилятор сгенерирует правильную версию машинного кода неправильной программы. Самым большим успехом в этом направлении является проверенный компилятором CompCert , который является компилятором для большого подмножества C.

Сам компилятор Compcert - это программа с проверкой корректности (выполненная в Coq), которая гарантирует, что, если он генерирует код для программы, он будет корректным (по отношению к операционной семантике сборки и C, используемой разработчиками CompCert). Усилие для машинной проверки этих вещей довольно большое; обычно доказательство правильности будет в диапазоне от 1x до 100x размера программы, которую вы проверяете. Написание машинно-проверенных программ и доказательств - это новый навык, который вы должны освоить - это не математика или программирование, как обычно, хотя это зависит от умения хорошо выполнять обе задачи. Такое ощущение, что вы начинаете с нуля, словно снова начинающий программист.

Однако для этого нет особых теоретических барьеров. Единственная вещь в этом направлении - теорема Блюма о размере, что для любого языка, в котором все программы являются общими, вы можете найти программу на общем рекурсивном языке, который будет по крайней мере экспоненциально больше при программировании на общем языке. Способ понять этот результат состоит в том, что тотальный язык кодирует не только программу, но и доказательство завершения. Таким образом, вы можете иметь короткие программы с длительными доказательствами завершения. Однако на практике это не имеет значения, поскольку мы собираемся писать программы только с управляемыми доказательствами завершения.

РЕДАКТИРОВАТЬ: Dai Le попросил немного проработать последний пункт.

Это в основном прагматическое утверждение, основанное на том факте, что, если вы можете понять, почему программа работает, то маловероятно, что причина заключается в каких-то огромных неизменных миллионах страниц. (Самые длинные инварианты, которые я использовал, занимают несколько страниц, и они заставляют рецензентов ворчать! Понятно, что и так, поскольку инвариант - причина, по которой программа работает без всего повествования, которое помогает людям понять его.)

Но есть и некоторые теоретические причины. По сути, мы не знаем очень многих способов систематического изобретения программ, доказательства правильности которых очень длинные. Основной метод состоит в том, чтобы (1) взять логику, в которой вы доказываете правильность, (2) найти свойство, которое не может быть прямо выражено в этой логике (доказательства непротиворечивости являются типичным источником), и (3) найти программу, Доказательство правильности опирается на семейство явных следствий невыразимого свойства. Поскольку (2) невыразимо, это означает, что доказательство каждого выраженного следствия должно быть сделано независимо, что позволяет увеличить размер доказательства корректности. В качестве простого примера обратите внимание, что в логике первого порядка с родительским отношением вы не можете выразить отношение предка.kk) выразимо, для каждого фиксированного . Таким образом, предоставляя программе, которая использует некоторое свойство предка до некоторой глубины (скажем, 100), вы можете заставить доказательство корректности в FOL содержать доказательства этих свойств в сто раз.k

Сложный взгляд на этот предмет называется «обратной математикой» и является изучением аксиом, необходимых для доказательства данных теорем. Я не знаю много об этом, но если вы отправите вопрос о его применении в CS, и я уверен, что по крайней мере Тимоти Чоу и, возможно, несколько других людей, смогут рассказать вам интересные вещи.

Нил Кришнасвами
источник
1
Не могли бы вы развить этот пункт «мы только собираемся писать программы с управляемыми доказательствами завершения»?
Дай Ле
Спасибо за ваш обновленный ответ! Ваш ответ действительно открывает мою перспективу. На самом деле я сам тоже немного работаю над «обратной математикой», но я не осознавал связи, которую вы упомянули. Еще раз спасибо!
Дай Ле
1
Смысл вашей правки связан с тем, что у нас практически нет кандидатов на тавтологии, которые требуют длинных доказательств в естественных системах доказательств (как, скажем, Фреге). Частично это объясняется тем, что тавтология, в которой мы знаем тавтологию, единственна только потому, что мы имели в виду доказательство, которое обязательно было не таким длинным!
Джошуа Грохов
22

Я думаю, что ответ на первый вопрос заключается в том, что обычно слишком много работы с текущими инструментами. Чтобы почувствовать, я предлагаю попробовать доказать правильность Bubble Sort в Coq (или, если вы предпочитаете немного больше испытаний, используйте Quick Sort). Я не думаю, что разумно ожидать, что программисты будут писать проверенные программы, пока доказательство правильности таких базовых алгоритмов так сложно и отнимает много времени.

Этот вопрос похож на вопрос, почему математики не пишут формальные доказательства, проверяемые средствами проверки? Написание программы с формальным доказательством правильности означает доказательство математической теоремы о написанном коде, и ответ на этот вопрос также относится к вашему вопросу.

Это не означает, что не было успешных случаев проверенных программ. Я знаю, что есть группы , которые доказывают правильность таких систем, как гипервизор Microsoft . Связанный случай - проверенный компилятор C от Microsoft . Но в целом текущие инструменты требуют большой разработки (включая аспекты SE и HCI), прежде чем они станут полезными для программистов общего профиля (и математиков).

Что касается последнего абзаца ответа Нила о росте размера программы для языков с только полными функциями, то на самом деле легко доказать еще больше (если я правильно понял). Разумно ожидать, что синтаксис любого языка программирования будет ce, а набор общих вычислимых функций не является ce, поэтому для любого языка программирования, где все программы являются суммарными, существует общая вычислимая функция, которая не может быть вычислена какой-либо программой ( любого размера) на этом языке.


На второй вопрос я ответил на аналогичный вопрос в блоге Скотта некоторое время назад. В основном, если класс сложности имеет хорошую характеристику и вычислимо представим (то есть, это ce), то мы можем доказать, что некоторые представления задач в классе сложности доказуемо полны в очень слабых теориях, соответствующих классу сложности. Основная идея заключается в том, что доказуемо общие функции теории содержит все C 0 функции и задачи , которая является C 0AC0AC0-полный для класса сложности, поэтому он содержит все проблемы в классе сложности и может доказать совокупность этих программ. Связь между доказательствами и теорией сложности изучается с точки зрения сложности доказательств, если вам интересно , см. Недавнюю книгу С. А. Кука и П. Нгуена « Логические основы сложности доказательств ». ( Доступен черновой вариант с 2008 года.) Итак, основной ответ таков: для многих классов «Обеспечиваемо C = C».

В целом это не так, поскольку существуют классы семантической сложности, которые не имеют синтаксической характеристики, например, полные вычислимые функции. Если под рекурсивом вы имеете в виду полные рекурсивные функции, то эти две функции не равны, и набор вычислимых функций, которые доказуемо полны в теории, хорошо изучен в литературе по теории доказательств и называется доказуемо полными функциями теории. Например: доказуемо полные функции являются ϵ 0 -рекурсивными функциями (или эквивалентно функциями в системе Гёделя T ), доказуемо полные функции P A 2 являются функциями в системе F Жирара F , доказуемо полными функциямиPAϵ0TPA2F - примитивные рекурсивные функции, ....IΣ1

Но мне не кажется, что это много значит в контексте проверки программ, поскольку есть также программы, которые в расширенном порядке вычисляют одну и ту же функцию, но мы не можем доказать, что эти две программы вычисляют одну и ту же функцию, то есть программы в равной степени равны, но не намеренно. (Это похоже на «Утреннюю звезду» и «Вечернюю звезду».) Кроме того, легко модифицировать данную доказуемо полную программу, чтобы получить такую, которую теория не может доказать своей совокупностью.


Я думаю, что эти два вопроса связаны между собой. Цель состоит в том, чтобы получить проверенную программу. Проверенные программы означают, что программа удовлетворяет описанию, которое является математическим утверждением. Один из способов - написать программу на языке программирования, а затем доказать, что ее свойства удовлетворяют описанию, что является более распространенной практикой. Другой вариант - попытаться доказать математическое утверждение, описывающее проблему, используя ограниченные средства, а затем извлечь проверенную программу из нее. Например, если мы докажем в теории, соответствующей что для любого данного числа n существует последовательность простых чисел, произведение которых равно n , то мы можем извлечь PPnnPалгоритм факторизации из доказательства. (Существуют также исследователи, которые пытаются максимально автоматизировать первый подход, но проверка интересных нетривиальных свойств программ сложна в вычислительном отношении и не может быть полностью проверена без ложных срабатываний и негативов.)

Кава
источник
3
Хороший ответ! Вы упоминаете, что одним из способов является извлечение программ из доказательств, что можно сделать автоматически, например, в Coq. Смежной областью является извлечение доказательств , когда люди (обычно работающие в математической логике) пытаются извлечь информацию из данного доказательства. Например, в некоторых случаях возможно (автоматически) найти интуиционистское доказательство, данное классическому.
Раду GRIGore
1
@Radu: спасибо за указание, что это можно сделать автоматически в Coq. Как вы упомянули, можно также извлечь некоторую конструктивную информацию и, следовательно, программы из классических доказательств теоремы, используя доказательство майнинга для некоторых классов формул (заинтересованные люди могут проверить работы Ульриха Куленбаха для деталей). Другой возможный связанный результат заключается в том, что если a Π20 теорема доказана в , она также конструктивно доказуема в H A переводом Харви Фридмана. _PAHA
Каве
1
У Андрея Бауэра есть новый интересный пост в его блоге, в котором он доказывает интерпретацию Геделя в диалектике в Coq .
Каве
18

То, о чем вы спрашиваете в первом вопросе, иногда называют «проверяющим компилятором», и несколько лет назад Тони Хоар предложил его как грандиозную задачу для компьютерных исследований . В некоторой степени это уже существует и активно используется в таких инструментах, как средство доказательства теорем Кока , которые организуют задачу с помощью теории типов и принципа «предложения как типы» (« Карри-Ховард »).

РЕДАКТИРОВАТЬ: просто хотел добавить акцент на «в некоторой степени». Это далеко не решенная проблема, но успех Coq дает надежду, что это не несбыточная мечта.

Ноам Цайлбергер
источник
8
Я бы сказал, что создание проверенного программного обеспечения - это то, где создание простого старого программного обеспечения было в 1956 году. Уже было очевидно, что программное обеспечение будет невероятно важным, и уже были большие успехи. Тем не менее, многие люди по-прежнему упускали фундаментальные концепции (например, четкое понимание того, что такое процедуры и переменные), и расстояние от теории до практики может быть таким же коротким, как и реализация Лиспа путем программирования кода в теореме. Это НЕВЕРОЯТНО захватывающее время, чтобы работать над языками и проверкой.
Нил Кришнасвами
12

Инструмент, который проверяет правильность программы, иногда называют верификатором программы. В этом контексте «правильный» обычно означает две вещи: программа никогда не выдает определенные выходные данные (например, ошибка сегментации, исключение NullPointerException и т. Д.) И что программа согласуется со спецификацией.

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

Имея в виду эти предостережения, я рекомендую вам взглянуть на верификатор программы Spec # .

Раду ГРИГОРЕ
источник
Насколько я понимаю Spec # (и его расширение Sing #), он дает программисту возможность статически проверять утверждения, но не требует от программиста этого, равно как и не дает возможности доказывать произвольные свойства кода.
Алекс тен Бринк
Произвольные свойства могут быть закодированы как утверждения, в принципе. Я не уверен, что вы хотите, чтобы инструмент требовал. Хотите ли вы, чтобы спецификации говорили, каким должен быть выход для всех возможных входов?
Раду GRIGore
4

В общем случае невозможно создать алгоритм, который подтверждает, эквивалентен ли алгоритм спецификации. Это неофициальное доказательство:

Почти все языки программирования являются тьюрингово-полными. Поэтому любой язык, выбранный ТМ, также может быть выбран программой, написанной на этом языке.

Equivalence/TM

Equivalence/TMNonemptiness/TMEmptiness/TMEmptiness/TMEquivalence/TMEquivalence/TMтоже недопустимо. Поэтому вы можете использовать алгоритм независимо от того, являются ли две машины неэквивалентными, но вы не можете быть уверены, что они эквивалентны, или вы не дали вашему алгоритму достаточно времени.

Однако это только для общего случая. Вполне возможно, что вы можете решить, эквивалентны ли спецификации программе, решив более упрощенную версию проблемы. Например, вы можете проверить только несколько входных данных или сказать, что две программы эквивалентны с некоторой неопределенностью. Вот что такое тестирование программного обеспечения.

Что касается остальных ваших вопросов:

Примечание: эта часть была отредактирована для уточнения. Оказывается, я сделал ошибку, которую пытался избежать, извините.

TrueRTrueRR

ProvableR=TrueRProvableRTrueRTrueRProvableRAϵTrueRAAAϵProvableR

Неофициально это можно обобщить так: вы не знаете, что язык является решаемым, пока вы не доказали, что это так. Таким образом, если в формальной системе у вас есть знание о том, что язык является разрешимым, это знание также может служить доказательством этого. Следовательно, вы не можете одновременно знать, что язык является разрешимым, и это невозможно доказать, поэтому эти два утверждения являются взаимоисключающими.

RProvableRProvableRRR

@Kaveh суммирует это лучше всего: «Применимость» всегда означает доказуемость в некоторой системе / теории и не совпадает с правдой в целом.

То же самое относится и к любому другому классу сложности: чтобы определить членство, сначала нужно получить подтверждение. Вот почему я считаю, что ваш второй вопрос слишком общий, поскольку он содержит не только теорию сложности, но и теорию вычислений, в зависимости от того, какое свойство вы хотите иметь в языке.

chazisop
источник
1
RProvableRΣ30Σ10
1
Применимость всегда означает доказуемость в некоторой системе / теории и не совпадает с истиной в целом.
Каве
1
Теперь я вижу, что для того, чтобы мой вопрос был интересным, нужно поговорить о наборе останавливающих машин Тьюринга, а не о множестве разрешимых языков.
Алекс тен Бринк
1
@ Алекс Ну, тебе нужен какой-то способ говорить о языках, но их неисчислимо много. Итак, если вы хотите поговорить о языках, связанных с каким-то конечным объектом (например, доказательством), вам нужно ограничиться языками, которые можно идентифицировать с помощью конечного объекта, такого как TM.
Марк Рейтблатт
2
R
3

Следующая классическая монография изучает почти точно ваш второй вопрос:

Хартманис, Дж. Возможные вычисления и доказуемые свойства сложности , Серия региональных конференций CBMS-NSF по прикладной математике, 30. Общество по промышленной и прикладной математике (SIAM), Филадельфия, Пенсильвания, 1978.

{L(Mi)|Ti(n)T(n) is provable in F}MiTi(n)Min

T(n)nlog(n)g(n)1FTIME[T(n)]TIME[T(n)g(n)]

T(n)FTяMЕ[T(N)]TяMЕ[T(N)]

T(N)Nжурнал(N)TяMЕ[T(N)]знак равно{L(Mя)|Ф доказывает(J)[L(MJ)знак равноL(Mя)TJ(N)T(N)]}

Для космоса, однако, ситуация лучше контролируется:

s(N)NSPACE[s(n)]=FSPACE[s(n)] .

SPACE[S(n)]=FSPACE[S(n)]S(n)ns(n)SPACE[S(n)]=SPACE[s(n)]

Джошуа Грохов
источник
1

Вопрос должен быть поставлен правильно. Например, никто никогда не хочет знать, завершит ли реальная программа заданную бесконечную память и какие-то средства доступа к ней (может быть, операция по перемещению базового адреса на некоторое число). Теорема Тьюринга не имеет отношения к корректности программы в каком-либо конкретном смысле, и люди, которые ссылаются на нее как на барьер для проверки программы, путают две совершенно разные вещи. Когда инженеры / программисты говорят о корректности программы, они хотят знать о конечных свойствах. Это также в значительной степени верно для математиков, которые интересуются, доказуемо ли что-то. Письмо Годеля http://vyodaiken.com/2009/08/28/godels-lost-letter/ объясняет это в некоторых деталях.

А именно, это, очевидно, означало бы, что, несмотря на неразрешимость проблемы Entscheidungs, умственную работу математика по вопросам «да» или «нет» можно полностью заменить машиной. В конце концов, нужно было бы просто выбрать натуральное число n настолько большое, что, когда машина не дает результата, не имеет смысла больше думать о проблеме.

Вполне может оказаться невозможным исследовать огромный набор состояний программы, выполняемой на реальном компьютере, и обнаруживать плохие состояния. Нет теоретической причины, по которой это невозможно сделать. На самом деле, в этой области достигнут большой прогресс - например, см. Http://www.cs.cornell.edu/gomes/papers/SATSolvers-KR-book-draft-07.pdf (спасибо Нилу Иммерману за рассказывал мне об этом)

Другая и более сложная проблема заключается в том, чтобы точно указать, какие свойства нужно иметь программе, чтобы она была правильной.

Виктор Йодайкен
источник