Перед началом: Абстракция и применение функции; Свободное и связанное вхождение; Рекурсивное синтаксическое дерево.
Замена текста может изменить смысл функции
В терме (λf.λz.(f λu.z) z) аргументом внешней функции является свободное z. Если просто вставить это имя вместо f, внешний по отношению к месту вставки λz свяжет его. Свободная ссылка превратится в параметр совсем другой функции. Получившийся текст будет выглядеть грамматически правильно, но обозначать другое выражение. Ошибка называется захватом переменной.
Абстракция λx.M связывает в M соответствующие вхождения x, кроме затенённых внутренними связываниями. Множество свободных переменных вычисляется структурно: у переменной это она сама, у применения — объединение множеств частей, у абстракции — свободные переменные тела без параметра. Перед сокращением полезно вычислить это множество у аргумента: именно такие имена нельзя неожиданно связать при его переносе.
Подстановка останавливается у подходящего связывания
Бета-правило сокращает применение (λx.M) N до M[x:=N]. При обходе M вхождение x заменяется аргументом, а другая переменная остаётся прежней. В применении обходятся обе части. В абстракции с тем же параметром x подстановка останавливается: внутренний x принадлежит новому связыванию. Заменять его было бы уже изменением другой переменной с одинаковым написанием.
У абстракции λy.P с отличным параметром нужно дополнительно проверить y относительно свободных переменных N. Если возникает риск захвата при требуемой подстановке, связанный параметр переименовывается в свежее имя. Важно переименовать только связанные с ним вхождения, сохранив внутреннее затенение. Глобальная замена всех букв y в строке не выполняет эту задачу корректно.
Альфа-переименование готовит один бета-шаг
Переименование связанного параметра без захвата называют альфа-преобразованием. Например, λz.P можно записать с новым параметром w, если w не создаёт конфликтов и соответствующие вхождения заменены согласованно. Выбор конкретного свежего написания не является частью результата вычисления: корректные варианты сравнивают с точностью до альфа-эквивалентности. Но свободные имена так переименовывать нельзя.
В нашем примере выбираем w, которого ещё нет в терме, и превращаем внутреннее связывание z в w. Внутри λu бывшее z всё ещё относится к этому внешнему связыванию, поэтому тоже станет w. После этого вставленное свободное z не попадает под λw. Подготовительное альфа-преобразование не является вторым бета-сокращением; это условие корректного выполнения одного заданного шага.
Нормальный поиск редекса и граница демонстрации
Лаборатория выбирает левый внешний бета-редекс и выполняет одно сокращение с безопасной подстановкой. Она не запускает произвольный машинный код и не обещает нормализацию каждого выражения. В λ-исчислении существуют термы с бесконечной цепочкой сокращений. Один успешный шаг показывает конкретное правило перехода, а не завершение всего вычисления или применимость выбранной стратегии к произвольному языку.
Для ручной проверки сначала отметьте связывания, затем укажите редекс, свежий параметр и оставшиеся свободные ссылки. У результата нашей задачи свободное z должно сохраниться. Проверка свободных переменных помогает обнаружить захват, но сама по себе не доказывает правильность всего дерева. Поэтому дополнительно сравнивают структуру применения и то, какие вхождения были заменены; совпадение множества имён ещё допускает неправильную перестановку частей.
Аргумент z проходит под другое связывание
Условие. Выполнить один левый внешний бета-шаг: (λf.λz.(f λu.z) z). Применения заключены в скобки; тело λu.z является аргументом внутреннего применения.
- Внешний редекс связывает f, аргумент — свободное z. Его множество свободных переменных равно {z}.
- В теле есть λz, которое захватило бы вставленное имя. Выбираем свежее w.
- Альфа-переименование даёт тело λw.(f λu.w). Параметр u остаётся прежним.
- Подставляем z вместо f: получаем λw.(z λu.w). Новое имя w может быть выбрано иначе при сохранении связываний.
Ответ. λw.(z λu.w), с точностью до переименования связанных параметров.
Проверка. Свободные переменные результата — {z}. Наивное λz.(z λu.z) замкнуто и поэтому потеряло свободный аргумент.
Где легко ошибиться. Свежесть имени проверяется по всему нужному контексту, а не только по параметру текущей функции. Красивое новое написание может уже встречаться свободно внутри тела.
Один β-шаг с защитой от захвата переменных
Учебное λ-исчисление: λx.term или \x.term, применение (term term), имена из a–z с цифрами длиной до восьми символов. До 180 токенов и 30 уровней вложенности. Делается один левый внешний β-шаг с α-переименованием при необходимости; это преобразование дерева выражения, не запуск программы.
Вопросы к этой главе
Должен ли результат буквально использовать букву w?
Нет. Подойдёт другое действительно свежее имя. Сравнение результатов должно учитывать альфа-эквивалентность, сохраняя свободные имена.
Можно заменять переменные обычным replace по строке?
Такой вызов не различает вхождения, области связывания и внутреннее затенение. Подстановка определяется по синтаксическому дереву или равноценному представлению связей.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Перед началом: Бета-сокращение; Значение в выбранной семантике; Подстановка без захвата.
Один терм допускает разные пути вычисления
Пусть I обозначает λs.s, а Ω — применение λu.(u u) к такой же абстракции. Рассмотрим (λq.(λr.(r r) I) Ω). Тело внешней функции не использует q. Стратегия, подставляющая аргумент без предварительного вычисления, сможет его отбросить и получить I. Стратегия, требующая сначала значение аргумента, застрянет не на ошибке, а на бесконечном вычислении Ω.
Малый шаг записывает одно допустимое преобразование выражения. Чтобы эта запись определяла исполнение, нужны правила выбора позиции, а не только бета-формула. Без них можно сокращать разные редексы и получать разные промежуточные цепочки. Конечный пример полезен именно тем, что показывает, какая часть терма выбирается первой и почему другой участок пока не имеет права измениться.
Call-by-value сначала получает значение аргумента
В выбранной слабой семантике call-by-value абстракция является значением. Для применения вычисляется функция, затем аргумент, и только после получения абстракции и значения разрешается подстановка. Под телом ещё не вызванной абстракции шаги не выполняются. Слово «слабая» указывает на это ограничение поиска, а не на меньшую строгость требований к корректности программы.
Для Ω один бета-шаг воспроизводит то же самое применение. Поэтому возможны шаги, но значение никогда не достигается. Если Ω требуется вычислить как аргумент внешней функции, её тело не начинает работу. Формальное отсутствие завершения отличается от отсутствия допустимого шага: застрявший терм не является значением и не может двигаться по правилам, а Ω постоянно движется к себе.
Call-by-name откладывает работу, но не обязательно разделяет её
В слабом call-by-name после получения функции-абстракции аргумент подставляется как выражение. Если параметр не используется, работа аргумента исчезает. Если параметр встречается несколько раз, его выражение может оказаться в нескольких местах и вычисляться повторно. Поэтому отложенное вычисление и запоминание результата являются разными решениями реализации. Call-by-need добавляет разделение вычисленной работы, которого в простой подстановочной модели нет.
Наш внешний q отсутствует в теле, поэтому call-by-name сразу убирает Ω. После этого два применения идентичности дают конечное значение. Обещать одинаковое число шагов для всех стратегий было бы неверно. При наличии побочных эффектов различия могут касаться не только времени, но и наблюдаемого поведения; здесь выбран чистый λ-язык, чтобы исследовать порядок и завершение без дополнительных эффектов.
Слабая стратегия и полная нормальная форма различаются
Терм λx.Ω является значением обеих выбранных слабых стратегий: тело пока не вычисляется. При поиске полной бета-нормальной формы пришлось бы сокращать и редексы под абстракцией, поэтому такое тело нельзя игнорировать. Вывод «получили функцию» относится к выбранному понятию результата. Его нельзя автоматически переименовать в утверждение, что внутри терма больше вообще нет редексов.
Для проверки трассы на каждом переходе укажите применённое правило и контекст. Если используется сокращённое имя I или Ω, сначала зафиксируйте его определение. Ограничение числа шагов в демонстрации сообщает только, что за этот бюджет значение не найдено. Доказательство бесконечности нашей Ω сильнее: после каждого шага буквально воспроизводится та же структура, поэтому конечное значение не появляется на любой последующей итерации.
Три шага вместо бесконечного аргумента
Условие. I=λs.s, Ω=(λu.(u u) λu.(u u)). Сравнить слабые стратегии для M=(λq.(λr.(r r) I) Ω).
- Call-by-name сокращает внешний редекс и получает (λr.(r r) I): параметр q в теле отсутствует.
- Следующий шаг подставляет I вместо r, получая (I I).
- Третий шаг даёт I, которое является значением слабой семантики.
- Call-by-value до внешней подстановки должен вычислить Ω. Каждый шаг Ω даёт Ω, поэтому до тела внешней функции он не доходит.
Ответ. Call-by-name достигает I за три бета-шага; call-by-value расходится на аргументе.
Проверка. В цепочке не вычислялось тело абстракции I до применения. Самовоспроизведение Ω проверяется подстановкой λu.(u u) в оба вхождения u.
Где легко ошибиться. Не путайте бесконечную цепочку допустимых шагов с ошибкой «шаг невозможен». Для анализа безопасности и завершения это разные результаты.
Вопросы к этой главе
Call-by-name всегда выполняет меньше работы?
Нет. Если параметр используется несколько раз, отложенное выражение может вычисляться повторно. Число шагов зависит от конкретного терма и модели разделения результатов.
Полученная абстракция всегда является полной нормальной формой?
В слабой семантике она уже значение, даже если внутри тела есть редексы. Полная нормальная форма требует другого условия.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Перед началом: Вариантный тип и конструктор; Рекурсивное определение; Условие в ветви сопоставления.
Допустимые значения задаёт тип
Зададим конечные деревья T=Tip|Fork(int,T,T). Ветка Fork может иметь любую целую метку и два дерева, включая пустые. Значение Fork(−2,Tip,Fork(3,Tip,Tip)) допустимо: отрицательная метка не запрещена объявлением типа. Если функция обрабатывает только внутренние узлы с положительными метками, она пропускает часть совершенно законных входов. Ошибка находится в охвате случаев, а не в построении этого дерева.
Индуктивное определение создаёт значения конечным применением конструкторов. Tip даёт базовый случай, Fork строит более сложное значение из уже построенных частей. Для нашей математической модели не предполагаются скрытые циклические ссылки или ленивые бесконечные деревья. Такие возможности потребовали бы другого рассуждения о значениях и завершении обхода. Слово «рекурсивный» само по себе не разрешает молча смешивать эти модели.
Проверяйте покрытие значений, а не только имена конструкторов
Пусть первая ветвь возвращает ноль для Tip, вторая обрабатывает Fork(n,Tip,Tip), а третья — Fork(n,l,r) только при условии n>0. Оба имени конструкторов присутствуют, но отрицательный внутренний узел не попал никуда. Guard сужает множество значений своей ветви. Отдельная обработка листового узла также не покрывает все формы Fork: дети могут быть непустыми.
Шаблоны проверяются в установленном порядке. Более общий шаблон раньше специального может сделать последний недостижимым. Ветка «всё остальное» способна скрыть проблему при добавлении нового конструктора. Для понимания исчерпываемости полезно разбить пространство значений по конструкторам, затем по вложенным формам и условиям. Результат должен покрывать каждое допустимое значение, а не только каждую строку небольшого теста.
Полный структурный обход имеет простое основание
Для суммы меток достаточно двух ветвей: score(Tip)=0 и score(Fork(n,l,r))=n+score(l)+score(r). Специальная ветвь листа не нужна: общее правило само даёт n+0+0. Знак метки не влияет на допустимость рекурсии. Отрицательные значения меняют сумму, но не структуру, по которой определяется следующий вызов.
Корректность доказывается структурной индукцией. Базовое пустое дерево содержит ноль меток. Для Fork предполагаем правильность сумм обоих поддеревьев и добавляем метку корня; это перечисляет все узлы ровно один раз. Каждый рекурсивный вызов получает строгое поддерево, поэтому на конечных значениях обход заканчивается. Здесь одна и та же структура даёт и смысл результата, и меру продвижения.
Исчерпываемость не доказывает любое поведение функции
Даже полный набор шаблонов может содержать бесконечный вызов функции на том же входе. Поэтому полнота разбора и завершение вычисления проверяются отдельно. Аналогично, возвращаемые числа могут вычисляться неверно, хотя каждая форма входа куда-то попадает. Предупреждение анализатора о неполном match полезно, но отсутствие такого предупреждения не заменяет доказательство суммы и свойств рекурсивных вызовов.
Практический контрпример выбирают именно из непокрытого множества: отрицательный узел, который не является листом. После исправления сравните результат с независимым перечислением меток. Затем рассмотрите пустое дерево и одиночный узел. Такие проверки направлены на логические границы определения, а не на случайный размер входа. Если появится новый конструктор, доказательство и шаблоны должны быть пересмотрены вместе с типом.
Законный вход без подходящей ветви
Условие. Для T=Tip|Fork(int,T,T) есть ветви Tip→0; Fork(n,Tip,Tip)→n; Fork(n,l,r) when n>0→n+score(l)+score(r). Вход Fork(−2,Tip,Fork(3,Tip,Tip)).
- Вход является Fork, поэтому первая ветвь Tip не подходит.
- Правый ребёнок не Tip, поэтому шаблон одиночного листового узла тоже не подходит.
- Условие третьей ветви −2>0 ложно. Значение допустимо, но разбор не исчерпывающий.
- Заменяем специальные ветви общим правилом Fork без guard. Получаем −2+0+(3+0+0)=1.
Ответ. Изначальный разбор пропускает вход; полный структурный score возвращает 1.
Проверка. Независимый список меток дерева — [−2,3], его сумма 1. Базовый Tip не добавляет меток.
Где легко ошибиться. Наличие имени Fork в нескольких шаблонах не означает покрытия всех Fork. Вложенный шаблон и guard ограничивают охватываемые значения.
Вопросы к этой главе
Если все конструкторы обработаны, рекурсия завершится?
Не обязательно. Вызов на том же входе может повторяться бесконечно. В нашем исправленном определении завершение обосновано переходом к строгим поддеревьям.
Почему отрицательная метка не является ошибкой типа?
Тип содержит int без дополнительного ограничения. Положительность пришлось бы выразить отдельным инвариантом или более точным представлением допустимых значений.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Перед началом: Суждение о типе; Малый шаг вычисления; Значение и замкнутый терм.
Тип результата должен переживать шаги вычисления
Выражение if ((λb:Bool.b) true) then ((λn:Int.n+3) 4) else 0 имеет тип Int в нашей мини-системе. Условие типизировано как Bool, обе ветви — как Int. После сокращения условия и выбора ветви выражение должно сохранить тот же итоговый тип. Такая трасса показывает смысл сохранения типа на конкретном примере, хотя не является доказательством для всех термов языка.
В учебной системе есть функции, Bool, математические целые Int и тотальное сложение целых. При добавлении операций к формальному ядру нужно проверить новые правила, а не автоматически перенести готовую теорему. Например, операция, которая может вызвать исключение, требует описания этого результата в семантике. Типизированность и поведение операции связаны через конкретные определения языка.
Два утверждения работают вместе
Прогресс говорит о замкнутом корректно типизированном терме: он либо уже значение, либо имеет следующий допустимый шаг. Замкнутость существенна: отдельно стоящая переменная может иметь тип в окружении, но не вычисляться без подстановки или значения этого окружения. Условие нельзя опустить только потому, что в бумажной записи рядом когда-то было объявление.
Сохранение утверждает, что допустимый шаг корректно типизированного выражения сохраняет его тип при соответствующих предпосылках. Вместе с прогрессом это позволяет продолжать рассуждение о достижимых состояниях: после первого шага снова применимы нужные условия. Доказательство обычно опирается на лемму о подстановке и свойства значений нужного типа. Таблица результатов тестов этих лемм не заменяет.
Не застрять и обязательно закончить — разные свойства
Бесконечная цепочка корректных шагов не противоречит прогрессу. Язык с общей рекурсией может допускать типизированную функцию, которая вызывает себя без завершения. Для чистого просто типизированного ядра существуют дополнительные результаты о нормализации, но они не выводятся из одного определения слов «прогресс» и «сохранение». Нужно указать точный язык и отдельное обоснование завершения.
Прикладная правильность также не следует из типа Int. Выражение может безопасно вернуть целое семь, хотя пользователь ожидал другое число из-за ошибки алгоритма. Аналогично, теорема об абстрактном языке не обещает отсутствие нехватки памяти, сбоев устройства или ошибок реализации компилятора. Каждое расширение границы требует дополнительных предпосылок и связи формальной модели с реальной системой.
Проверяйте ошибочные расширения на малом контрпримере
Если разрешить применять любое логическое значение как функцию, можно получить выражение, которое новый проверяющий типов признаёт, а старые правила выполнения не умеют сокращать. Это нарушит прогресс. Если шаг внезапно заменяет целое логическим значением, он может нарушить сохранение. Такие контрпримеры полезны при проектировании новых операций и правил приведения, прежде чем переходить к большому языку.
В собственной проверке сначала постройте вывод исходного типа, затем перечислите разрешённые шаги и тип каждого промежуточного выражения. Отдельно проверьте, что финальный результат является значением. После этого сформулируйте границу вывода: проверена конкретная трасса, а общий результат требует доказательства всех случаев правил. Такой порядок не позволяет выдать успешный запуск одного примера за готовую теорему безопасности реализации.
Один итоговый тип на всей трассе
Условие. Учебные Bool, Int и тотальное сложение. Терм: if ((λb:Bool.b) true) then ((λn:Int.n+3) 4) else 0.
- Условие имеет тип Bool; применение в then имеет тип Int; else также Int. Весь терм получает Int.
- Сокращение условия даёт if true then ((λn:Int.n+3) 4) else 0; итоговый тип остаётся Int.
- Выбирается then: ((λn:Int.n+3) 4), по-прежнему Int.
- Бета-шаг даёт 4+3, арифметический шаг — 7. Оба выражения имеют тип Int, последнее является значением.
Ответ. Трасса заканчивается значением 7 типа Int; каждый промежуточный терм также имеет итоговый тип Int.
Проверка. Замена else на false нарушила бы правило одинакового типа ветвей ещё до вычисления, хотя условие в данном запуске истинно.
Где легко ошибиться. Успешная проверка типов относится к определённым правилам языка. Она не является универсальным обещанием завершения, прикладной правильности и отсутствия любых реальных сбоев.
Вопросы к этой главе
Зачем в прогрессе требовать замкнутый терм?
Свободная переменная может иметь объявленный тип, но не иметь значения для выполнения. Теорема должна явно учитывать окружение или ограничить термы замкнутыми.
Можно доказать type soundness тестированием?
Тесты обнаруживают контрпримеры и проверяют реализацию на выбранных данных. Общее утверждение обо всех допустимых термах требует доказательства по правилам системы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Перед началом: Предусловие и постусловие; Индукция; Математические целые без переполнения.
Семь итераций ещё не доказывают общее правило
Программа начинает с i=0, s=0 и, пока i<n, выполняет s=s+3i+2, затем i=i+1. При n=7 она складывает 2,5,8,11,14,17,20 и получает 77. Но успешный запуск не объясняет результат для произвольного n. Нужно утверждение, которое связывает текущий счётчик с уже накопленной частью суммы и остаётся верным после каждой итерации.
Работаем с математическими целыми и постоянным n≥0. Это исключает скрытое переполнение машинного типа и изменение границы цикла извне. Цель — после завершения получить s=n(3n+1)/2. Если эти предпосылки поменять, доказательство придётся проверить заново. Например, отрицательное n меняет связь между отсутствием итераций и ожидаемой формулой; параллельное изменение n разрушает выбранную меру продвижения.
Инвариант описывает уже обработанный префикс
Возьмём I: 0≤i≤n и s=i(3i+1)/2. Перед первой проверкой условия i=s=0, поэтому I выполнен. Выражение справа равно сумме первых i членов последовательности 3k+2 при k от нуля до i−1. Инвариант говорит именно об обработанных членах, а не о будущей полной сумме, которую ещё предстоит получить.
На входе в тело известно I вместе с i<n. После первого присваивания s становится i(3i+1)/2+3i+2=(i+1)(3i+4)/2. Затем счётчик увеличивается, и та же формула принимает вид s=i_new(3i_new+1)/2. Условие i<n гарантирует верхнюю границу нового i. Таким образом, тело сохраняет все части I, а не только арифметическое равенство.
Выход использует и инвариант, и отрицание условия
Когда цикл заканчивается, известно i≥n. Инвариант одновременно даёт i≤n, поэтому i=n. Подстановка в равенство накопителя даёт требуемое постусловие. Одного инварианта без информации о выходе было бы недостаточно: при i=0 он верен и до вычисления всей суммы. Одного ложного условия также недостаточно, потому что оно ничего не говорит о s.
В логике Хоара такая схема обосновывает частичную корректность: если программа завершилась при выполненных предпосылках, постусловие верно. Чтобы не подменить это обещанием обязательного завершения, отдельно зададим вариант V=n−i. При истинном условии он положителен, после тела уменьшается ровно на единицу и остаётся неотрицательным. Бесконечно убывать в натуральных значениях он не может.
Порядок присваиваний входит в доказательство
Первое присваивание использует старое i. Если увеличить счётчик раньше, вместо последовательности 2,5,… начнётся 5,8,… . Текст почти тот же, но выбранный инвариант больше не сохраняется. В рассуждении по присваиванию значение правой части вычисляется в предыдущем состоянии; обозначения i_old и i_new помогают не заменить его незаметно уже обновлённой переменной.
Для собственной проверки выпишите предусловие, инициализацию, сохранение, выход и вариант завершения как разные обязанности. Слабое утверждение вроде s≥0 может сохраняться, но не вывести нужную точную сумму. Слишком сильное s=n(3n+1)/2 не выполнено вначале. Удачный инвариант достаточно точен для постусловия и одновременно верен для каждого промежуточного префикса работы, а не только для финального числа.
Накопитель для n=7
Условие. n=7; i=0; s=0. Пока i<n: сначала s=s+3i+2, затем i=i+1. Все числа математические целые.
- Инициализация даёт s=0=0·(3·0+1)/2 и 0≤i≤7.
- Общий переход переводит i(3i+1)/2 в (i+1)(3i+4)/2, затем обновляет i.
- При выходе i=7, поэтому s=7·22/2=77. Вариант 7−i убывал от 7 до 0.
- Независимо складываем 2+5+8+11+14+17+20=77. Если переставить присваивания, получится 5+8+11+14+17+20+23=98.
Ответ. Исходный цикл возвращает 77; выбранный инвариант и вариант обосновывают правильность и завершение для любого n≥0.
Проверка. Разница при перестановке равна 3n=21 для n=7. Она возникает из-за другого набора членов, а не из-за ошибки округления.
Где легко ошибиться. Частичная корректность не доказывает завершение. Для полной гарантии отдельно проверяется продвижение по хорошо основанной мере.
Вопросы к этой главе
Любое сохраняющееся утверждение годится как инвариант?
Формально оно может быть инвариантом, но должно ещё помогать вывести нужное постусловие при выходе. Утверждение true слишком слабо для точной суммы.
Почему нужен запрет переполнения?
Равенства доказаны над математическими целыми. Машинная арифметика по модулю или с исключением требует другого постусловия либо дополнительных ограничений на n.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.