Стиль програмування

В цьому розділі ми дамо рекомендації для написання елегантних і ефективних програм на Пролозі.

Для виміру ефективності програми традиційно використовують два параметри: пам`ять і час. В Пролозі на покращання цих оцінок значною мірою впливає відміна хвостової рекурсії.

Розглянемо відомий нам предикат member:

member (X, [X|_]).

member (X,[_|Y]): member (X,Y)

Ітеративна операція перевірки або генерації елементів потрібного списку проводиться рекурсивним чином, тому стекова пам`ять (а відповідно і час виконання) повністю залежить від рекурсії. Припустимо, що предикат demopredописується так:

demopred (X,Y): - ... , member (A,B), test (A), ...

При активізації member спочатку система повинна запам`ятати, що після успішного виконання member керування потрібно передати предикату test. Тому, адреса test повинна бути збережена в стеці. Для кожного рекурсивного звертання до member система запам`ятовує адресу, до якої повинен повернутись предикат memberпісля успішного завертання цього предикату. Враховуючи, що міжmember (X,[_,Y]):- і рекурсивним зверненням member(X,Y) не має точок повернення до попереднього стану, не має необхідності зберігати адресу member в стеці декілька разів. Достатньо запам`ятати, що після успішного завершення предикату member керування повинно бути передане предикату test. Це і буде відміною хвостової рекурсії. Там, де система не може відмінити рекурсію, програміст може зробити це сам, використовуючи наступні правила.

Правило1. Краще використовувати більше змінних, ніж предикатів.

Це правило знаходиться часто в прямому конфлікті з наглядністю програми. В багатьох випадках декларативний стиль Прологу приводить до гіршого коду в порівнянні з процедурними мовами. Наприклад, якщо ви пишете предикат, для перестановки елементів списку, тоді такий фрагмент коду, як:

reverse(X,Y):- reverse1([],X,Y). /*More efficient*/

reverse1(Y, [], X).

reverse1(X1, [U | X2], Y):- reverse1([U|X1],X2,Y).

пред'являє менше вимог до стеку, ніж використання додатково предикату append:

reverse([],[]).

reverse([U | X], Y):- reverse(X,Y1), append(Y1,[U],Y).

append([],Y,Y).

append([U|X],Y,[U|Z]):-append(X,Y,Z).

Правило 2. При впорядкуванні підцілей в правилі, першими розміщуйте підцілі з найбільш зв'язаними змінними.

Наприклад ви пишете предикат для вирішення системи рівнянь

ìХ + 1 = 4

í

îХ + Y = 5

використовуючи метод "генеруй_ і_перевіряй":

solve(X,Y):- /*кращій варіант*/

Num(X), plus(X, 1, 4),

Num(Y), plus(X, Y, 5).

Тоді він буде кращим за наступний фрагмент :

solve(X,Y):- /*гірший варіант*/

Num(X), num(Y),

Наши рекомендации