Каково текущее состояние параллельных или параллельных программ в изоморфизме Карри-Ховарда?

В « Доказательствах и типах» Жирара мы можем прочитать:

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

Доказательства и типы , JY Girard (стр. 28)

Но мы также можем прочитать (о линейной логике), что

С точки зрения информатики, он дает новый подход к вопросам лени, побочных эффектов и распределения памяти [GirLaf, Laf87, Laf88] с многообещающими приложениями к параллелизму.

Доказательства и типы , JY Жирар (Страница 149, написанный Ивом Лафоном)

Как параллельные программы связаны с изоморфизмом Карри-Ховарда? Каковы нынешние мысли об этом?

Параллельная Логическая структура является одной интересной областью , включая его потомок, как Linear Meld и LolliMon . Это основано на интуиционистской линейной логике.

Классическая линейная логика имеет связи с Линейной химической абстрактной машиной (CHAM), как описано, например, в исчислении для сетей взаимодействия на основе линейной химической абстрактной машины, которое явно описывает результат как результат типа Карри-Ховарда.

Тезис Александра Саммерса « Исчисление терминов Карри-Говарда для классической логики в стиле Генцена», который я не читал, похоже, направлен непосредственно на проблему обеспечения соответствия Карри-Ховарда для исчислений в стиле Генцена. В -исчисления по Кюрьену и Herbelin , введенных в дуальности вычислений является семенной работой в этом духе (нелинейного) лямбда - исчисления , соответствующий классическую логику.$\lambda\mu$

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

(Как примечание педантизма, большинство из них сосредоточено на параллелизме , а не параллелизме как таковом.)

Для параллелизма в целом существует очень активная линия исследований, которую я попытался обобщить в этом ответе: https://cs.stackexchange.com/a/102711/98901

Я добавляю здесь комментарий о параллелизме ниже.

Avron [1996] ввел понятие гиперсеквентов , то есть наборов секвенций в суждениях.

В [Kokke et al., 2019] мы показали, что консервативное расширение линейной логики с гиперсеквентами можно использовать для ввода параллелизма в исчислениях процессов. По сути, если у вас есть два независимых доказательства в линейной логике гипервариабельных и соответственно, то вы можете вывести , гдеявляется оператором для составления гиперсеквентов. Следуя интерпретации Абрамского «Доказательства как процессы» [Abramsky, 1996] , мы получаем правило типизации для параллелизма: скажем, что у вас есть два независимых процесса и типизированных и$\mathcal{G}$$\mathcal{H}$$\mathcal{G} | \mathcal{H}$$|$P Q G H P | Q P Q G | ЧАС$P$$Q$$\mathcal G$$\mathcal H$соответственно; тогда параллельная композиция (с независимыми от и ) типизируется .$P|Q$$P$$Q$$\mathcal G | \mathcal H$

Мы только начали царапать поверхность семантической интерпретации этого, но это параллелизм довольно очевиден: семантика параллельной композиции позволяет видеть одновременные действия от обоих процессов, и в статье есть теорема о том, что ни один из два процесса должны ждать, пока другой выполнит хотя бы какое-то действие (теорема готовности). Расширение более чем на два действия одновременно кажется простым. (Печатание уже учитывает это, но семантика в этой статье не в полной мере использует это.)