Что, если языки программирования могли бы думать заранее?
7 июля 2025 г.Авторы:
(1) Дэвид Биндер, Университет Тюбингена, Германия;
(2) Марко Цшенке, Университет Тюбингена, Германия;
(3) Мариус Мюллер, Университет Тюбингена, Германия;
(4) Клаус Остерманн, Университет Тюбингена, Германия.
Таблица ссылок
Введение
Перевод на последовательное исчисление
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
Ссылки
1 Введение
Предположим, вы только что реализовали свой собственный небольшой функциональный язык. Чтобы проверить его, вы записываете следующую функцию, которая умножает все числа, содержащиеся в списке:
def mult (𝑙) ≔ случай 𝑙 {nil ⇒ 1, минусы (𝑥, 𝑥𝑠) ⇒ 𝑥 ∗ mult (𝑥𝑠)}
Что вас беспокоит в этой реализации, так это то, что вы знаете очевидную оптимизацию: функция должна непосредственно возвращать ноль, если она столкнется с нулем в списке. Есть много способов достичь этого, но вы решите расширить свой язык с помощью маркированных выражений и инструкции GOTO. Это позволяет написать оптимизированную версию:
def Mult (𝑙) ≔ Метка 𝛼 {mult ’(𝑙; 𝛼)}
def mult ’(𝑙; 𝛼) ≔ случай 𝑙 {nil ⇒ 1, ins (𝑥, 𝑥𝑠) ⇒ ifz (𝑥, goto (0; 𝛼), 𝑥 ∗ mult’ (𝑥𝑠; 𝛼))}
Вот как вы читаете этот фрагмент: кроме аргумента списка 𝑙, определение def mult (𝑙; 𝛼) ≔. Полем Полем принимает аргумент 𝛼, который указывает, как вычисление должно продолжаться после вычисления результата умножения (мы снова используем; для разделения этих двух видов аргументов). Полученная функция Mult ’принимает аргумент списка 𝑙 и два аргумента 𝛼 и 𝛽; Аргумент 𝛽 указывает, куда должна вернуться функция при нормальном рекурсивном вызове, в то время как 𝛼 указывает точку возврата короткого замыкания вычислений. В теле мульти мы используем ⟨𝑙 | case {nil ⇒. Полем Полем , Минусы (𝑥, 𝑥𝑠) ⇒. Полем .}⟩ Для выполнения дела в списке 𝑙. Если список ноль, то мы используем ⟨1 | 𝛽⟩ вернуть 1 к 𝛽, что является возвратом для обычного рекурсивного вызова. Если в списке есть форма формы (𝑥, 𝑥𝑠), а 𝑥 равна нулю, мы возвращаемся с ⟨0 | 𝛼⟩, где 𝛼 является возвратной точкой, которая короткая замыкает вычисление. Если 𝑥 не равен нулю, то мы должны выполнить рекурсивный вызов Mult ’(𝑥𝑠; 𝛼, 𝜇𝑧. ˜ ∗ (𝑥, 𝑧; 𝛽)), где мы используем 𝜇𝑧. ˜ ∗ (𝑥, 𝑧; 𝛽), чтобы связать результат рекурсивного вызова с переменной 𝑧, прежде чем умножить ее на 𝑥 и вернуть к 𝛽. Не будьте обескуражены, если это выглядит сложным в данный момент; Основная часть этой статьи будет охватывать все более подробно.
То, что вы только что видели, были впервые представлены Curien и Herbelin [2000] как решение давнего открытого вопроса: как должен выглядеть язык термина для последовательного исчисления? Последовательное исчисление является одним из двух влиятельных доказательств, представленных Gentzen [1935a, b] в одной статье, другой исчисление является естественным вычетом. Термин «Язык для естественного вычета» - это обычное исчисление Lambda, но было трудно найти хороший язык для последовательного исчисления. После того, как он был обнаружен, 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus был предложен в качестве лучшей основы для промежуточных языков компилятора, например, Downen et al. [2016]. Несмотря на это, большинство языковых дизайнеров и писателей компиляторов по -прежнему не знакомы с этим. Это ситуация, которую мы надеемся исправить с помощью этой жемчужины.
Мы часто обсуждаем идеи, которые включают в себя 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus со студентами и коллегами и поэтому должны представить их с его центральными идеями. Но мы обычно не можем мотивировать 𝜆𝜇𝜇-калькулус в качестве системы назначения термина для последовательного исчисления, поскольку большинство из них не знакомы с ним. Вместо этого мы объясняем 𝜆𝜇𝜇 𝜆𝜇𝜇-калькулус на доске, собирая в нее небольшие функциональные программы. Такое введение, к сожалению, все еще отсутствует в опубликованной литературе; Большинство существующих презентаций либо предполагают знание последовательного исчисления, либо иным образом тратят много места, представляя его в первую очередь. Мы считаем, что если можно понять исчисление лямбда без сначала изучения естественных доказательств вычета, то следует также иметь возможность понять 𝜆𝜇𝜇 𝜆𝜇𝜇-калькулус, не зная последовательного исчисления [1].
Почему мы взволнованы 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus, и почему мы думаем, что больше людей должны познакомиться с его центральными идеями и концепциями? Основной особенностью, которая отличает исчисление 𝜆𝜇𝜇 𝜆𝜇𝜇- от исчисления Lambda, является его первоклассное лечение контекстов оценки. Контекст оценки - это оставшаяся часть программы, которая работает после текущей субэкспрессии, которую мы сосредоточены на оценке отделок.
Это становится более ясным с примером: когда мы хотим оценить выражение (2 + 3) ∗ 5, мы сначала должны сосредоточиться на субэкспрессии 2 + 3 и оценить его до его результата 5. Остальная часть программы, которая будет работать после того, как мы закончили оценку, может быть представлена с помощью контекста оценки □ ∗ 5. 𝜆𝜇𝜇 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus Мы можем связывать такие контексты оценки с ковариами. Кроме того, 𝜇-оператор обеспечивает прямой доступ к контексту оценки, в котором выражение в настоящее время оценивается. Наличие такого прямого доступа к контексту оценки не всегда необходимо для программиста, который хочет написать приложение, но часто важно для исполнителей компилятора, которые пишут оптимизации, чтобы программы работали быстрее. Одно решение, которое писатели компилятора используют для представления контекстов оценки в исчислении Lambda, называется стилем продолжения. В стиле продолжения передачи контекста оценки, такого как □ ∗ 5, представлен как функция 𝜆𝑥.𝑥 ∗ 5. Это решение работает, но полученные типы, которые используются для печати программы в этом стиле, возможно, трудно понять. Возможность легко осматривать эти типы может быть очень ценной, особенно для промежуточных представлений, где термины имеют тенденцию выглядеть сложными. Обещание 𝜆𝜇𝜇 𝜆𝜇𝜇-калькулуса состоит в том, чтобы обеспечить выразительную силу программ в стиле продолжения, без необходимости иметь дело с акробатикой типа, которые обычно связаны с ним.
Остальная часть этой статьи структурирована следующим образом:
• В разделе 2 мы вводим развлечение на поверхности и показываем, как мы можем перевести его в ярко-ядр на основе последовательности. Язык поверхности является в основном ориентированным на выражение языка функционального программирования, но мы добавили некоторые функции, такие как типы кодат и операторы управления, чьи переводы дают важную информацию о том, как работает 𝜆𝜇𝜇-калькулус. В этом разделе мы также сравниваем, как Redexes оцениваются на обоих языках.
• В разделе 3 мы обсуждаем статическую и динамическую фокусировку, которые являются двумя тесно связанными методами для подъема подэккранов, которые не являются значениями в положение, где их можно оценить.
• Раздел 4 представляет правила печати для развлечения и ядра и доказывает стандартные результаты о наборе и оценке.
• Мы показываем, почему мы взволнованы 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus в разделе 5. Мы представляем различные концепции языка программирования, которые становятся намного ясными, когда мы представляем их в 𝜆𝜇𝜇 𝜆𝜇𝜇-calculus: мы показываем, что связывания с помощью let точно двойные для управления операторами, что данные и типы кодатов являются двумя идеальными двойными способами определения типов, и что преобразование в области ток-козы-это больше, чем то. Эти идеи не являются новыми для кого-то, кто знаком с 𝜆𝜇𝜇-calculus, но еще не так широко известен, как и должен.
• Наконец, в разделе 6 мы обсуждаем связанную работу и предоставляем указатели для дальнейшего чтения. Мы завершаем в разделе 7.
Эта статья сопровождается реализацией Haskell, которая также предоставляем в качестве интерактивного веб -сайта (см. Рисунок 1). Вы можете запустить примеры, представленные в этой статье в онлайн -оценщике.
Эта статья есть
[1] Для заинтересованного читателя мы показываем в Приложении A, как подключены последовательное исчисление и 𝜆𝜇𝜇 𝜆𝜇𝜇-калькулус.
Оригинал