?

Log in

No account? Create an account

Previous Entry Share Next Entry
Higher-order vs. first -order
medved
avlasov wrote in dot15926
Маленький пост на тему в чем разница между first-order и higher-order.

Строго говоря, higher-order - это когда параметрами предикатов (и функций) могут быть другие предикаты (и функции), а first-order - когда не могут.

Но это определение не совсем интуитивное. Рассмотрим подробнее на примере.

Допустим у нас есть пара запись вроде
PossibleIndividual(myInstance)
ClassificationTemplate(myInstance, MyClass)

В рамках FOL, myInstance и MyClass - это переменные, а ClassificationTemplate и PossibleIndividual - это предикаты.
Обе эти записи задают, что myInstance есть инстанс каких-то классов. Но существенная для FOL разница состоит в том, что в первом случае класс задан предикатом, а во втором - переменной. Т.е. в первом случае у нас стандартный класс, а во втором - "пользовательский".

И синтаксически запись разная. Но семантически, они означают (почти что) одно и то же - задают факт классификации. Разница лишь в том, что в первом случае класс стандартный, а во втором определенный пользователем. Поэтому может возникнуть желание и синтаксис использовать в обоих случаях одинаковый, например иметь возможность записать
ClassificationTemplate(myInstance, PossibleIndividual)
и
MyClass(myInstance)

К сожалению, в рамках FOL мы не можем произвольно смешивать два таких вида синтаксиса, ибо в этом случае оказывается, что MyClass и PossibleIndividual выступают в роли предикатов, но мы их передаем в качестве параметров ClassificationTemplate. Таким образом, ClassificationTemplate становится предикатом второго порядка, а они в рамках FOL запрещены.

Замечу что понятия типа class_of_class все равно можно в таких записях выражать, просто это менее удобно синтаксически (ну и на уровне семантики тоже есть некоторые ограничения).

Второпорядковые записи как синтаксический сахар

Сие противоречие можно разрешить, если ввести явную или неявную трансляцию таких высокопорядковых выражений в перво-порядковые.

Например, можно использовать префикс #, который будет означать что предикат нужно считать переменной.
Таким образом можно сделать две записи
PossibleIndividual(myInstance)
ClassificationTemplate(myInstance, #PossibleIndividual)

В данном случае, PossibleIndividual и #PossibleIndividual - символы разные, и конфликта не возникает.
Однако, с точки зрения логики, связи между ними никакой нет - она есть только в мозгу человека. Поэтому такую связь нужно добавить.

Например, компилятор, как только встретит использование #PossibleIndividual неявно добавляет правило:
all x ClassificationTemplate(x, #PossibleIndividual) <-> PossibleIndividual(x)

Либо же тупо конвертит ClassificationTemplate(myInstance, #PossibleIndividual) в PossibleIndividual(myInstance).

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