r7 - 25 Sep 2004 - 18:47:00 - AnatolyARessinYou are here: TWiki >  XSG Web > WhatIsFairness

Что такое справедливость?

В принципе понятие справедливости применимо и к детерминированым языкам, но в случае недетерминизма его определение значительно нагляднее. Справедливость означает, что интерпретатор перебирает возможые варианты (возникшие из-за недетерминизма) в ширину, то есть если рассмотрение какого-то варианта происходит бесконечно долго, то это не мешает завершиться вариантам, которые требуют конечного времени вычисления. Скажем, Пролог справедливостью не обладает, например:

P(a,b) :- P(a,b)
Q(a,a).
R(a,b) :- P(a,b).
R(a,b) :- Q(a,b).

R(X,y)?

Функция r(a) задаваемая предикатом r(a) = b <=> R(a,b) недетерминирована, она может равняться и p(a) и q(a). Вычисление функции p(a) занимает бесконечное время, и из-за несправедливости Пролога интерпретатор все свое время тратит на нее, в то время как функция q(a) вычисляется за один шаг. В отличие от Пролога, интерпретатор XSG на аналогичной программе будет рассматривать эти два варианта одновременно и придет к одному из ответов за конечное время.

На самом деле понятие справедливости несколько сложнее, потому что варианты возникают не только из-за недетерминизма, но и при решении системы "уравнений" (см. Равенство). Справедливый интерпретатор должен уделять время всем уравнениям системы. Например:

Child(A,B).
Child(B,C).
Descedant1(x,y) :- Child(z,y), Descedant1(x,z).
Descedant1(x,y) :- Child(x,y).
Descedant2(x,y) :- Descedant2(x,z), Child(z,y).
Descedant2(x,y) :- Child(x,y).

Descedant1(x,y)?
Descedant2(x,y)?

Предикаты Descedant1 и Descedant2 выражают по сути одно и то же, но из-за отсутствия справедливости в Прологе определение Descedant2 следует признать неверным -- его интерпретация зацикливается. Дело в том, что при решении системы { Descedant2(x,z), Child(z,y) } интерпретатор пролога тратит все свое время на первое "уравнение", не принимая во внимание наличие второго. Аналогичные программы на XSG обе являются правильными, то есть за конечное время находят все правильные ответы.

-- Andrei Mishchenko - 24 Mar 2004

А не лучше ли называть это БЕСПРИСТРАСТНОСТЬЮ ?

-- BeV? - 22 Jul 2004

Несправедливость Пролога заключается в его обходе дерева решений вглубину, который с одной стороны позволяет сэкономить память, с другой стороны - может приводить к бесконечному "проваливанию" в неверную ветку. А здесь [в XSG], насколько я понимаю, под справедливостью на техническом уровне предполагается обход вширину (или какой-нибудь более навёрнутый подход, гарантирующий перечисление всех узлов поиска). Так? В этом смысле "осправедливленной" может наверное считаться оригинальная версия логического движка Пролога - Andorra.

-- AnatolyARessin - 20 Sep 2004

Да. Справедливость означает, что любой интерпретатор языка обязан выдать каждый ответ.

В языке еще одно понятие - ленивость. В случае языков типа Haskell, справедливость и ленивость почти одно и тоже. В XSG это не так: справедливость - это ограничение на построение всего дерева перебора/вычисления, а ленивость - ограничение на каждый путь в дереве: т.е. каждый отдельно взятый путь вычислений должен быть ленивым ("не считать лишнего").

-- Yuri Klimov - 20 Sep 2004

Разделение ленивости и справедливости в XSG очевидно возникает из-за его двойственной природы (ФП+ЛП). Хотя для того, чтобы говорить что-то о свойствах этих понятий, хотелось бы взглянуть на формальную семантику самого языка (операционную, денотационную или любую другую). В каком виде она существует сейчас? Естественно, реализацию на Хаскелле, при желании можно выдать за детальную денотационную семантику, но хотелось бы что-то более прозрачного и мальенького - такого, как лямбда-исчисление. Со свойствами и теоремами, аналогичными нормальному порядку редукций, всякими там Чёрчами-Россерами и т.п. (Кстати это касается и TSG)

Чую, что рефальщики меня отшлют к нормальным алгорифмам, но... чем чёрт не шутит, как говорится.

PS: Я бы, если честно, предпочёл операционную семантику, ибо использую ASF+SDF (но здесь это, очевидно, не в моде wink Вот. smile

-- AnatolyARessin - 25 Sep 2004

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r7 < r6 < r5 < r4 < r3 | More topic actions
 
Powered by TWiki

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback