Существуют ли какие-либо доказуемые языки в реальном мире? (scala?)

Ответ 1

Да, существуют языки, предназначенные для написания доказуемо правильного программного обеспечения. Некоторые из них даже используются в промышленности. Spark Ada, вероятно, самый яркий пример. Я поговорил с несколькими людьми в Praxis Critical Systems Limited, который использовал его для кода, работающего на Boings (для мониторинга двигателя), и это кажется довольно приятным. (Вот отличный резюме/описание языка.) Этот язык и сопроводительная система доказательств используют второй метод, описанный ниже. Он даже не поддерживает динамическое распределение памяти!

Мое впечатление и опыт в том, что существует два метода написания правильного программного обеспечения:

• Техника 1: Напишите программное обеспечение на удобном вам языке (например, C, С++ или Java). Примите официальную спецификацию такого языка и убедитесь, что ваша программа верна.

  Если ваша амбиция должна быть на 100% правильной (что чаще всего является требованием в автомобильной/аэрокосмической промышленности), вы будете тратить мало времени на программирование и больше времени.

• Техника 2: Напишите программное обеспечение на немного более неудобном языке (например, подмножество Ada или модифицированная версия OCaml) и напишите корректность на этом пути. Здесь программирование и доказательство идут рука об руку. Программирование в Coq даже приравнивает их полностью! (См. Карри-Говардская переписка)

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

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

Вот еще несколько примеров формальных подходов. Если это "реальный мир" или нет, зависит от того, кого вы спрашиваете: -)

• Доказательство теоремы Coq: Программирование с Coq (метод 2)
• ESC/Java (техника 1, ни звук, ни завершение, хотя)
• SpeС# (техника 1, ни звук, ни завершение, хотя)
• Почему /Krakatoa (метод 2, основанный на Java)

Я знаю только один "доказуемо правильный" язык веб-приложений: UR. Ur-программе, которая "проходит через компилятор", гарантируется не:

• Страдают от любых атак с использованием кода.
• Возврат недействительного HTML
• Содержит мертвые ссылки внутри приложения
• Имеются несоответствия между формами HTML и полями, ожидаемыми их обработчиками.
• Включить код на стороне клиента, который делает неверные предположения об услугах "AJAX", которые предоставляет удаленный веб-сервер.
• Попытка недопустимых запросов SQL
• Использовать неправильное маршалинг или размаширование при взаимодействии с базами данных SQL или между браузерами и веб-серверами.

Ответ 2

Чтобы ответить на этот вопрос, вам действительно нужно определить, что вы подразумеваете под "доказуемым". Как отметил Рики, любой язык с системой типов - это язык со встроенной системой доказательств, которая запускается каждый раз, когда вы скомпилируете свою программу. Эти системы доказательств почти всегда печально импотентны; отвечая на вопросы типа String vs Int и избегая таких вопросов, как "отсортирован ли список"? — но они представляют собой системы доказательств.

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

Даже для доказательства чего-то простого, как правильность алгоритма сортировки, требуется сравнительно сложная система доказательств. (обратите внимание: поскольку мы уже установили, что системы типа являются встроенной в язык системой доказательств, я буду говорить о вещах с точки зрения теории типов, а не размахивать руками еще более энергично). Я абсолютно уверен, что полное доказательство корректности сортировки списка потребует определенной формы зависимых типов, иначе вы не сможете ссылаться на относительные значения на уровне типа. Это немедленно начинает врываться в сферы теории типов, которые, как было показано, неразрешимы. Таким образом, хотя вы можете доказать правильность алгоритма сортировки списка, единственным способом сделать это будет использование системы, которая также позволит вам выражать доказательства, которые она не может проверить. Лично я нахожу это очень обескураживающим.

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

Со всем этим стоит отметить, что система типа Scala (например, Haskell's) - это Turing Complete, что означает, что вы теоретически можете использовать ее для доказательства любого разрешимого свойства вашего кода при условии, что вы написали ваш код таким образом, что он поддается таким доказательствам. Haskell почти наверняка является лучшим языком для этого, чем Java (так как программирование на уровне языка в Haskell аналогично Prolog, а программирование на уровне типа в Scala больше похоже на SML). Я не советую вам использовать системы типа Scala или типа Haskell (формальные доказательства алгоритмической корректности), но вариант теоретически доступен.

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

Ответ 3

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

Для доказательства того, что работает целая программа, да, вы выходите за пределы обычных языков, где математика и программирование встречаются друг с другом, пожимают друг другу руки, а затем переходят к разговорам с использованием греческих символов о том, как программисты не могут справиться с греческими символы. Что касается Σ этого в любом случае.

Ответ 4

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

• Есть хорошо понятые языки с возможностью быть доказанными в использовании сегодня; Lisp через ACL2 является одним, и, конечно, схема также имеет хорошо понятое формальное определение.

• ряд систем пытался использовать чистые функциональные языки или почти чистые, такие как Haskell. В Haskell существует довольно много формальных методов.

• Возвращаясь на 20 + лет, существовала недолговечная вещь для использования ручного доказательства формального языка, который затем строго переводился на скомпилированный язык. Некоторыми примерами были IBM Software Cleanroom, ACL, Gypsy и Rose из Computational Logic, John McHugh и моя работа над надежной компиляцией C и моей собственной работой по ручному тестированию для системного программирования C. Все это привлекло некоторое внимание, но никто из них не преуспел в этом.

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

Ответ 5

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

Это интересно читать, если вас интересуют языки функционального программирования и чистые языки функционального программирования.

Ответ 6

Использование таких доказуемых языков в реальном мире было бы невероятно трудным для написания и понимания afterwoods. бизнес-мир нуждается в рабочем программном обеспечении, быстро.

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

Ответ 7

Я участвую в двух доказуемых языках. Во-первых, это язык, поддерживаемый Perfect Developer, системой для указания sotfware, ее уточнения и генерации кода. Он использовался для некоторых крупных систем, включая сам PD, и преподавался в ряде университетов. Второй доказуемый язык, с которым я связан, является доказуемым подмножеством MISRA-C, более подробно см. C/С++ Verification Blog.

Ответ 8

Scala должен быть "реальным миром", поэтому не было сделано никаких усилий, чтобы сделать его доказуемым. Что вы можете сделать в Scala, это создать функциональный код. Функциональный код намного проще тестировать, что является ИМХО хорошим компромиссом между "реальным миром" и доказуемостью.

EDIT ===== Убрали мои неправильные идеи о том, что ML "доказуемо".

Ответ 9

Ознакомьтесь с Omega.

Это Введение содержит относительно безболезненной реализации AVL деревьев с включенным правильность доказательства.

Ответ 10

Мое (противоречивое) определение "реального мира" в контексте доказуемо-правильного кода:

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

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

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

Ответ 11

Как насчет Idris и Agda? Достаточно ли реального мира?

В качестве примера для реальной жизни существует проект, целью которого является предоставление проверенной библиотеки HTTP REST, написанной в Agda, называемой Lemmachine: https://github.com/larrytheliquid/Lemmachine