Стиль програмування
В цьому розділі ми дамо рекомендації для написання елегантних і ефективних програм на Пролозі.
Для виміру ефективності програми традиційно використовують два параметри: пам`ять і час. В Пролозі на покращання цих оцінок значною мірою впливає відміна хвостової рекурсії.
Розглянемо відомий нам предикат 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),