В дальнейшем я рассматриваю только чистые программы Prolog. Это означает, что я не говорю о побочных эффектах и вызовах ОС, которые оставляют логику логики делать что-то, что невозможно наблюдать из Prolog.
Существует известная абстрактная мера для времени выполнения программы Prolog: количество логических выводов. Под "абстрактным" я подразумеваю, что эта мера не зависит от какой-либо конкретной реализации и фактического конкретного оборудования. Это мера в том смысле, что она дает нам некоторую информацию о времени, которое потребуется для выполнения программы. Мы даже можем указать производительность систем Prolog в какой-то степени, указав их количество выводов на второй и второй (LIPS), и это настолько широко используется, что можно назвать его традиционной мерой производительности системы. Традиционно это число измеряется определенным эталоном, но общее понятие "количество выводов", конечно, распространяется и на другие, более сложные программы Prolog.
Однако, насколько я понимаю, эта конкретная (осмелюсь сказать: конкретная) абстрактная мера не говорит всей правды в следующем важном смысле:
Для любой заданной цели Пролога G обозначим с t (G): T & rightarrow; R - фактическое исполнение время G на данной системе Prolog на конкретном оборудовании, т.е. функцию из условий Herbrand реальный номер. Назовем меру & alpha;: T & rightarrow; R правдивый iff t (G) & approx; & alpha; (G) для всех G в том смысле, что значения отличаются на коэффициент, ограниченный константой для все цели G и все "реалистичные" типы аппаратного обеспечения (я должен оставить эту последнюю точку слегка неопределенной, но я предполагаю здесь для простоты, что одна и та же реализация Prolog выполняется примерно так же на "типичном" оборудовании. Я знаю, что на самом деле это не так, и одна и та же реализация может демонстрировать совершенно разные характеристики на разных типах аппаратного обеспечения. Если это так, ограничьте определение подмножеством аппаратных типов, где реализация выполняется "примерно" так же.)
Насколько я знаю, количество логических выводов в общем случае не является достоверной мерой фактического времени выполнения задачи Prolog в частности, поскольку время, необходимое для выполнения унификаций, не измеряется им. Можно построить случаи, когда разница между этой мерой и фактическим временем выполнения больше не ограничена константой.
Поэтому мой вопрос: существует ли правдивая абстрактная мера для времени выполнения цели Prolog? Если он вообще не существует, укажите подробное подмножество программ Prolog, где такая мера может быть определена. Например, ограничивая типы унификаций, которые могут произойти.
Этот вопрос имеет большое практическое значение, например, при использовании Prolog для реализации smart контрактов. В таких случаях вы хотите абстрактно измерить, сколько времени потребуется для запуска программы Prolog , даже если ваша программа работает на разных машинах, которые должны быть в согласии о времени, которое требуется для запуска, и тем не менее вы хотите сохранить возможность будущих улучшений для конкретной технологии внедрения. Следовательно, эта мера должна зависеть только от фактически данной программы, а не от каких-либо конкретных особенностей реализации, таких как количество ячеек памяти, к которым обращаются.
