Какие кодаты, управление потоком и логика учат нас в программировании
9 июля 2025 г.Таблица ссылок
Введение
Перевод на последовательное исчисление
2.1 Арифметические выражения
2.2 Пусть привязки
2.3 Определения верхнего уровня
2.4 Алгебраические данные и типы кодов
2.5 первоклассные функции
2.6 Операторы управления
Оценка в контексте
3.1 Контексты оценки для развлечения
3.2 Сосредоточение внимания на оценке в сердечнике
Правила печати
4.1 Правила печати для развлечения
4.2 Правила печати для Core
4.3 Тип. Звукость
Понимание
5.1 Контексты оценки являются первым классом
5.2 Данные двойные до кодата
5.3 LET-связы
5.4 Трансформация случая
5.5 Прямой и косвенный потребители
5.6 Позвоните в запас, вызовов и eta-laws
5.7 Линейная логика и двойственность исключений
Связанная работа
Заключение, заявление о доступности данных и подтверждение
A. Взаимосвязь с последовательным исчислением
B. Правила набора развлечений
C. Оперативная семантика лейбла/goto
Ссылки
6 Связанная работа
Центральные идеи Calculi, которые мы представили в этой жемчужине, не являются новыми: 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus уже более 20 лет. Мы выбрали вариант этого исчисления, который можно использовать в качестве отправной точки для изучения всех вариантов, которые были описаны в литературе. Таким образом, этот раздел «Связанный работа» предназначен для предоставления предложений для дальнейшего чтения и возможности глубже погрузиться в конкретные темы, на которые мы только затронули.
6.1 Последовательное исчисление
Основой нашего языкового ядра является термин -система назначения для последовательного исчисления, альтернативная логическая система естественного вычета. Последовательное исчисление было первоначально введено Дженценом в статьях Gentzen [1935a, B, 1969]. Для более тщательного введения в последовательное исчисление как логическую систему мы можем рекомендовать книги Негри и фон Платона [2001] и Троэльстра и Швихтенберг [2000], которые вводят последовательное исчисление и показывают, как он отличается от естественных систем дедукции, которые чаще проводятся.
6.2.
Первоначальная статья, в которой вводили 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus в качестве системы назначения термина для последовательного исчисления, была Curien и Herbelin [2000]. Прежде чем перечислить некоторые другие статьи, мы должны предоставить их следующим замечанием о нотации:
Причины этого расхождения легко объясняются. Обозначения Curien и Herbelin [2000] с его двумя контекстами γ и Δ идеально иллюстрирует соответствие с последовательным исчислением, которое работает с последовательностями γ Δ, которые содержат несколько формул на левой и правой стороне турчатки. Это близкое соответствие с последовательным исчислением для нас менее важна. Мы обнаружили, что разделение контекста таким образом часто затрудняет записывать правила в их полной общности, когда мы расширяем язык с другими функциями. Особенности, которые вводят зависимость более поздних связей от более ранних связей в контексте типирования, например, когда мы добавляем параметрический полиморфизм, не вписывайтесь в формат Curien и Herbelin [2000].
С этими замечаниями мы можем порекомендовать статьи Zeilberger [2008], Downen и Ariola [2014, 2018b, 2020], Munch-Maccagnoni [2009] и Spiwack [2014], которые были очень полезны для нас, когда мы узнали о 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus.
6.3 Типы кода
Типы кодов были первоначально изобретены Хагино [1989]. Они имели наибольший успех в таких помощниках, как AGDA, где они помогают обойти определенные технические проблемы, которые возникают, когда мы пытаемся моделировать коиндинические типы. Соответствие Copattern как способ создания производителей типов кодат был популяризирован Abel et al. [2013], хотя основная идея концепции была вокруг этого, см., Например, [Zeilberger 2008]. Но, вероятно, лучшая отправная точка, чтобы узнать больше о типах кодат, - это статья, написанная Downen et al. [2019].
6.4 Операторы управления и классическая логика
Конструкция метки/goto, которую мы используем в веселье, является примером управляющего оператора, из которого оператор Landin J [Felleisen 1987; Landin 1965; Thielecke 1998], вероятно, самый старый. Их перевод в ядро использует 𝜇-абидракции, которые также являются формой оператора управления, который первоначально был представлен Parigot [1992], прежде чем он стал частью 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus of Curien и Herbelin [2000]. Операторы управления имеют важную связь с классической логикой через изоморфизм карри-ховарда. Эти отношения были обнаружены Гриффином [1989]; Более тщательное введение можно найти в Sørensen и Urzyczyn [2006].
6.5 Различные заказы на оценку
Мы уже говорили о стратегиях оценки по значению и вызову, и о том, как их различие можно объяснить различными вариантами того, как следует оценить критическую пару. Эта двойственность между вызовом и вызовом уже наблюдалась Филински [1989] и была более подробно изучена Wadler [2003, 2005]. Мы также видели в разделе 5.6, как 𝜂-уменьшение работает только с типами данных в вызове и с типами кодатов в вызове. Поэтому многие люди приходят к выводу, что выбор порядка оценки, возможно, не должен быть глобальным решением, но вместо этого должно зависеть от типа. Этот подход требует отслеживания полярности типов и обеспечения дополнительных сменных соединений, которые помогают посреднивать различные ордена на оценку; Статья Даунена и Ариолы [2018a] является хорошей входной точкой для выполнения таких вопросов, которые подробно обсуждаются в [Zeilberger 2009] и [Munch-Maccagnoni 2013]. Хорошо известным примером смешивания заказов на оценку является парадигма вызовой за тонульную стоимость [Levy 1999], которая различает типы значений и типы вычислений, а также подчинены как по значению, так и по вызову.
7 Заключение
В этой функциональной жемчужине мы представили 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus в том, как мы знакомимся с нашими коллегами и студентами на доске; Скомпилируем небольшие примеры функциональных программ.
Мы думаем, что это лучший способ представить энтузиастов на языке программирования и авторов компиляторов в 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus, поскольку он не требует предварительного знания последовательного исчисления. Мы также показали, почему мы взволнованы этим исчислением, приведя примеры того, как оно позволяет нам выражать такие аспекты, как строгая и ленивая оценка или оптимизации компилятора, такие как случай, как уделяется чрезвычайно ясным способом. Мы хотим поделиться нашим энтузиазмом по поводу последовательного исчисления и языков, построенных на нем с большим количеством людей, и с этой жемчужиной мы надеемся, что другие начнут писать свои собственные маленькие компиляторы в последовательное исчисление и изучить интересные возможности, которые он предлагает.
Оператор доступности данных
Эта статья сопровождается реализацией в Хаскелле. После принятия и публикации этой статьи реализация будет доступна навсегда с использованием Zenodo.
Благодарности
Мы хотели бы поблагодарить анонимных рецензентов и Пола Даунена за их отзывы, которые очень помогли нам улучшить финальную презентацию статьи.
Авторы:
(1) Дэвид Биндер, Университет Тюбингена, Германия;
(2) Марко Цшенке, Университет Тюбингена, Германия;
(3) Мариус Мюллер, Университет Тюбингена, Германия;
(4) Клаус Остерманн, Университет Тюбингена, Германия.
Эта статья есть
Оригинал