Можно ли вычислить, равны ли две функции экстенсионально?

9

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

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

Стоит ли смотреть на денотационную семантику или она не связана?

Я заинтересован в указателях для исследований в этой области и в различных терминах, используемых для описания предмета, которые могут помочь в моем поиске литературы.

Маттис Стин
источник

Ответы:

8

Да. Если вы можете проверить, что они одинаковы, то и компьютер тоже.

Вот краткая спецификация для целочисленной сортировки в Coq:

Inductive natlist : Type :=
| nil : natlist
| cons : nat → natlist → natlist.

Fixpoint is_sorted (l : natlist ) : bool :=
    match l with
    |  nil => true
    |  (cons x nil) => true
    |  (cons x (cons y r)) => if x <= y then is_sorted (cons y r) else false
    end.

...

Theorem sort_spec : forall l, is_sorted (sort_list l).

Спецификация может быть непосредственно закодирована в объявлении сортировки с использованием зависимых типов.

Для этой конкретной проблемы Джон Дарлингтон продемонстрировал в 70-х годах, что 6 семейств алгоритмов сортировки могут быть получены путем механического преобразования спецификации сортировки в реализацию; Я полагаю, что это идет под названием "основанный на семантике программный вывод".

В мире разработки программного обеспечения поиск экстенсивно эквивалентных функций известен как «семантическое обнаружение клонов».

Дейв Кларк также дал хороший ответ на этот вопрос в CS StackExchange: /cs/2059/how-do-you-check-if-two-algorithms-return-the-same-result -для-любой-вход

Все это подпадает под зонтики формальных методов и языков программирования . Денотационная семантика - это один класс методов для моделирования семантики, но они потеряли популярность из-за сложности использования по сравнению с операционной семантикой.

Джеймс Коппел
источник
Спасибо за ответ! Это именно то, что я искал.
Маттис Стин
4
Я категорически не согласен с утверждением о том, что денотационная семантика «вышла из-под контроля». Это во многом зависит от того, кого вы спрашиваете.
Андрей Бауэр
5

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

Проверка может происходить во многих формах, например, в теории множеств ZFC, используя операционную семантику. Однако это было бы больно. Если существует денотационная семантика, их также можно использовать, но хорошая денотационная семантика существует только для нескольких языков. Обычно используют программную логику, например логику Хоара , для демонстрации равенства расширений программ. Для этого логика Hoare для языков с функциями обычно требует аксиомы, гласящей, чтоезнак равногИксα,е(Икс)знак равног(Икс), при условии, что е а также г являются функциями типа αβ (детали аксиомы variy с деталями выбранного подхода к логике Хоара).

Мартин Бергер
источник
Спасибо за ответ. Я буду смотреть на логику Хоара. Трудно ли определить денотационную семантику по сравнению с логикой Хоара или она просто менее подходит для большинства языков? Является ли экстенсиональное равенство неразрешимым вообще из-за проблемы остановки? Тогда, если функции должны были бы всегда останавливаться, как в целом функциональных языках, разве это не было бы решаемо вообще? Или есть другие причины для неразрешимости вообще?
Маттис Стин
@ Matthijs Steen: Кажется, трудно найти хорошую денотационную семантику для языков программирования с интересными функциями. Логика Hoare, напротив, расцвела в последнее десятилетие, и мы можем построить ее практически для любого языка программирования сейчас. Равенство экстентов неразрешимо, потому что (немного упрощая), в противном случае вы можете проверить, является ли произвольная программап контекстуально эквивалентно 0всегда завершающая программа, которая является вариантом проблемы остановки. Если вы добавите достаточное количество условий конечности в язык, вы в конечном итоге получите что-то, что ... (продолжение)
Мартин Бергер,
... имеет разрешимое контекстное равенство. Но обратите внимание, что Р. Лоудер показал, что даже конечный PCF обладает неразрешимой контекстуальной эквивалентностью.
Мартин Бергер
-2

Быстрый ответ (я признаю, что я не тратил много времени ...) Теорема Райса говорит, что для любого нетривиального вопроса неразрешимо сказать, будет ли функция, вычисляемая программой, иметь свойство или нет. Поэтому вопрос здесь неразрешим

обычный парень
источник
1
Разве в нем не говорится, что «... для любого нетривиального свойства частичных функций ...», поэтому оно не может быть разрешимым для полных функций?
Маттис Стин