Ежедневные применения теории типов

10

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

Тамад Ланг
источник
2
Почему у чего-то должны быть приложения вне того, для чего оно было изобретено?
Рафаэль
3
Основы математики? Люди также использовали теорию типов для формализации таких вещей, как синтетическая теория предметной области, топология и т. Д. Есть также работа Криса Мартенса по использованию теоретических инструментов типов для моделирования повествовательного рассказа. Диссертация ссылка
Даниэль Гратцер
1
Можете ли вы уточнить, считается ли приложение?
Джейк
4
Я не убежден вашей предпосылкой. Предположим, что кто-то сказал: «Я хочу понять автомобильную технику, но сначала я должен знать, для чего я могу использовать автомобиль. Могут ли быть неочевидные применения автомобилей помимо транспорта?» Они получают ответы о том, что некоторые люди спят в своих машинах, а Ансель Адамс использовал его в качестве платформы для фотографирования . Что ж, это здорово, но это не помогает никому понять инженерию и может привести нашего гипотетического ученика к проектированию автомобилей с супер наклонными сиденьями и очень жесткой подвеской.
Дэвид Ричерби
3
Дело в том, что большая часть теоретической информатики (включая то, над чем я работаю) практически бесполезна, хотя математически красива. К сожалению, вы должны выбрать стороны.
Юваль Фильмус

Ответы:

10

Вы можете быть заинтересованы в работе над Ceptre , в результате исследования доктора философии из Криса Martens , который использует теорию типа для интерактивного повествования. Ниже приводится реферат диссертации :

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

В частности, мы рассматриваем нарратив со структурной точки зрения и наблюдаем, что альтернативные нарративные пути играют дополняющую роль к одновременным взаимодействующим временным рамкам. Линейная логика предоставляет инструменты представления, необходимые для исследования этой структуры, и, расширив соответствие доказательств и построение доказательств, мы находим набор вычислительных возможностей. Мы представляем три попытки реализации этих возможностей: (1) использование линейного логического программирования для создания повествований; (2) новый язык программирования для создания интерактивных рассказов, игр и симуляций; и (3) методы для определения и подтверждения свойств программы на уровне проектирования.

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

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

gasche
источник
1
Это похоже на использование линейной логики, а не теории типов как таковой .
Дэвид Ричерби
6
Линейная логика является краеугольным камнем теории типов. Эта работа во многом является частью теории типов как дисциплины (некоторые люди описывают свою работу как «теорию доказательств», когда она в равной степени относится к теории типов, хотя названия не эквивалентны, так как некоторые другие работы в «теории доказательств» будут рассматриваться как более конкретным для теории доказательств, а не центральным для теории типов).
Гаше
9

Там были интересные применения теории типов в лингвистике. См., Например, лингвистические труды Чунг-Цзе Шаня или Кристиана Реторе .

Цитируется ниже описание Rétoré в книге о категориальных грамматик:

Эта книга - современное и всестороннее введение в категориальные грамматики в логической традиции, начатой ​​работой Ламбека. Он направляет студентов и исследователей через фундаментальные результаты в этой области, предоставляя современные доказательства многих классических теорем, а также оригинальные последние достижения. Многочисленные примеры и упражнения иллюстрируют мотивацию и применение этих результатов с лингвистической, вычислительной и логической точек зрения. Исчисление Ламбека и его варианты, а также соответствующие грамматики лежат в основе этих лекционных заметок. Глава посвящена ключевой особенности этих категориальных грамматик: их очень элегантному синтаксически-семантическому интерфейсу. Кроме того, мы адаптируем к этим исчислениям линейные логические доказательственные сети, поскольку они предоставляют эффективные алгоритмы синтаксического анализа, как показано в парсере Grail.

Следующая цитата во введении главы книги « Языковые побочные эффекты» Шана :

Эта статья связывает случаи очевидной некомпозиционности в естественных языках с случаями в языках программирования. Он имеет форму песочных часов: я начинаю в § 1 с подхода к интерфейсу синтаксис-семантика, который помогает нам создавать композиционные семантические теории. Этот подход заключается в проведении аналогии между вычислительными побочными эффектами в языках программирования и тем, что я называю аналогией лингвистических побочных эффектов в естественных языках.

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

Введенный мной метаязык полезен для анализа как языков программирования, так и естественных языков. Для интуиции я рассмотрю первое использование в § 3, а затем укажу на достоинства этого лечения в § 4.

Обращаясь к естественному языку в § 5, я подробно описываю, как эта перспектива помогла Крису Баркеру и мне изучить связывание и кроссовер, а также вопросы и преимущества и превосходство. Я также использовал продолжения для изучения количественных и неопределенных областей действия, особенно в китайском языке мандарин, но здесь есть только место, чтобы наметить эти дальнейшие разработки, в §6.

gasche
источник
9

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

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

Например, некоторые инструменты автоматической проверки доказательств работают по этому принципу: они проверяют достоверность доказательства путем проверки типа определенного термина в некоторой системе типов. LF proof checker основан на этом подходе, как и HOL Light . В качестве примера приложения код для проверки корректности использовал LF для проверки доказательств безопасности ненадежного кода в памяти. Преимущество использования такого рода средства проверки правописания состоит в том, что реализация может быть очень простой, и, таким образом, мы можем получить высокую уверенность в том, что реализация является правильной. Смотри, например, следующую статью:

Основополагающие проверки с маленькими свидетелями . Динхао Ву, Эндрю В. Аппель, Аарон Стамп. PPDP 2003.

jmite
источник
Это может помочь: math.ucr.edu/home/baez/rosetta.pdf
псевдоним
Я не думаю, что это отвечает на вопрос. А как насчет реальных приложений?
Юваль Фильмус
@YuvalFilmus Определить «фактический»?
Дэвид Ричерби
1
Знаете ли вы, кто-нибудь использовал теорию типов, чтобы доказать что-то новое о проверке цепей, реальном анализе, символической логике или геометрии? Или мы просто говорим о случаях, когда кто-то использует 20 страниц теории типов, чтобы доказать что-то, что занимает три строки в элементарном учебнике?
Дэвид Ричерби
@ Дэвид Что это ответ, что в принципе вы можете использовать теорию типов, чтобы доказать вещи. Кроме того, в принципе, мы можем использовать клеточные автоматы для доказательства чего-либо, поскольку правило 110 является полным по Тьюрингу. Я думаю, что первое утверждение так же бессмысленно, как и второе.
Юваль Фильмус
7

Интересной статьей, которая объясняет приложения зависимых типов, является The Power of Pi , которая показывает, как Agda может использоваться для решения интересных задач.

Другим хорошим примером является использование зависимых типов для управления ресурсами. Хорошим примером является API управления файлами из Effects of Idris . Например, функция для чтения строки из файла имеет следующий тип

readLine  : { [FILE_IO (OpenFile Read)] } Eff String

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

Более подробную информацию о библиотеке эффектов можно найти здесь .

Еще одно приложение - это использование зависимых типов для параллелизма, как описано в следующей статье создателя Idris.

Родриго Рибейро
источник
1
Добавлены другие примеры.
Родриго Рибейро
3

как упоминалось в ответе jmite, логика / теория более высокого порядка в верификации схем / аппаратных средств / электроники существовала уже несколько десятилетий и в настоящее время настолько рутинна, что ее даже не замечают / не рассматривают так часто, как «приложение» после явно большого усилия по переносу в ~ 1990-е годы, хотя это все еще активная область исследований. Coq и его типовая логика также широко применяются, в частности, для проверки схем / аппаратного обеспечения / электроники на всем пути от логики логического элемента низкого уровня до структур / подсистем гораздо более высокого уровня / порядка. вот несколько ключевых ссылок

ВЗН
источник
1
Чтобы быть справедливым, тем не менее, наиболее актуальная проверка аппаратного обеспечения в промышленном масштабе была сделана с использованием проверки модели, технологии проверки, которая, как правило, не связана с теорией типов (хотя мосты были проведены недавно). Теория типов использовалась для построения языков описания аппаратного обеспечения (не слишком унаследованных от языков программирования), и большинство языков, которые вы предоставляете, относятся к этой категории, а некоторые из корректоров, разработанных для проверки аппаратного обеспечения (в частности, оригинальная HOL, но не самый используемый PVS) - это карри-говардские переносы теории типов.
Гаше
если у вас есть глубокие знания в области проверки аппаратного обеспечения, было бы интересно услышать больше подробностей в чате Computer Science, но подумайте / предположите, что узкие / четкие линии / обобщения трудно провести в этой области, например, между проверкой модели и теорией типов. может потребоваться очень тонкий исторический анализ, чтобы всесторонне раскрыть / собрать воедино связи между двумя разными областями с разными целями, а иногда даже за пределами возможностей экспертов в любой области в отдельности ... в целом ссылки показывают сильные связи, которые могут быть проанализированы в дальнейшем. ..
vzn