Недавно Дана Скотт предложила стохастическое лямбда-исчисление, попытку ввести вероятностные элементы в (нетипизированное) лямбда-исчисление на основе семантики, называемой графовой моделью. Вы можете найти его слайды в Интернете, например, здесь и его статью в журнале прикладной логики , том. 12 (2014).
Однако, с помощью быстрого поиска в Интернете, я обнаружил аналогичное предыдущее исследование, например, для системы типов Хиндли-Милнера . Способ, которым они вводят вероятностную семантику, похож на метод Скотта (в первом они используют монады, в то время как во втором Скотт использует стиль прохождения продолжения).
Чем отличается работа Скотта от предыдущей работы с точки зрения самих теорий или их возможных применений?
Ответы:
Одна очевидная сила его подхода состоит в том, что он позволяет функциям высшего порядка (то есть лямбда-терминам) быть наблюдаемыми результатами, которые теория измерения обычно делает довольно хитрыми. (Основная проблема заключается в том, что пространства измеримых функций обычно не имеют борелевской алгебры, для которой измерима прикладная функция, иногда называемая «eval»; см. Введение к статье Борелевские структуры для функциональных пространств .) Скотт делает это, используя Кодирование Гёделя от лямбда-терминов до натуральных чисел и работа непосредственно с закодированными терминами. Одним из недостатков этого подхода может быть то, что кодирование может быть трудно расширить с помощью реальных чисел в качестве программных значений. (Изменить: это не слабость - см. Комментарий Андрея ниже.)σ
Использование CPS, по-видимому, главным образом для наложения полного порядка на вычисления, для наложения полного порядка на доступ к случайному источнику. Государственная монада должна делать то же самое.
«Случайные переменные» Скотта, похоже, совпадают с «выборочными функциями» Пакса в его операционной семантике . Техника преобразования стандартных однородных значений в значения с любым распределением более широко известна как выборка с обратным преобразованием .
Я полагаю, что есть только одно фундаментальное различие между семантикой Рамси и Скотта. Программы Рэмзи интерпретируют программы как вычисления, которые строят оценку результатов программы. Скотт предполагает существующее единообразное измерение входных данных и интерпретирует программы как преобразования этих входных данных. (Выходная мера в принципе может быть рассчитана с использованием прообразов .) Скотт аналогичен использованию случайной монады в Haskell.
В своем общем подходе семантика Скотта кажется наиболее похожей на вторую половину моей диссертации по вероятностным языкам - за исключением того, что я придерживался значений первого порядка вместо умного кодирования, использовал бесконечные деревья случайных чисел вместо потоков и интерпретировал программы как стрелочные вычисления. (Одна из стрелок вычисляет преобразование из фиксированного вероятностного пространства в выходные данные программы; другие вычисляют прообразы и приблизительные прообразы.) Глава 7 моей диссертации объясняет, почему я считаю, что интерпретировать программы как преобразования фиксированного вероятностного пространства лучше, чем интерпретировать их как вычисления что построить меру. В основном все сводится к тому, что «точки фиксации мер очень сложны, но мы хорошо понимаем точки фиксации программ».
источник