На этом шаге мы рассмотрим использование аргументов в качестве переменных цикла.

Сейчас, после освоения хвостовой рекурсии, как бы вы поступили с циклическими переменными и счетчиками? Чтобы ответить на этот вопрос, мы совершим небольшое преобразование с Pascal на Пролог, предполагая, что вы знакомы с языком Pascal. Обычно результаты прямых переводов между двумя языками, как естественными, так и языками программирования, достаточно убоги. И хотя приведенный ниже пример неплох и является разумной иллюстрацией чисто процедурного программирования на Прологе, вам никогда не следует писать программы на Пролог методом слепого перевода их с другого языка. Пролог - очень мощный и выразительный язык, и правильно написанные Пролог-программы показывают иной стиль программирования и имеют совсем иные проблемы, нежели программы на других языках.

На шаге 39 мы показали вычисление факториала с помощью рекурсивной процедуры. Здесь мы используем для этого итерацию. В Pascal это выглядело бы так:

   Р:=1;
   for I:=1 to N do P:=P*I;
     FactN:=P;

Если вы знакомы с Pascal, то знаете, что := является оператором присваивания и произносится как "присвоить". Здесь 4 переменных. N - число, факториал которого будет вычисляться; FactN - результат вычисления; I - циклическая переменная, изменяемая от 1 до N; P - суммирующая переменная. Конечно, опытный программист на Pascal объединил бы FactN и Р, но для перевода на Пролог так будет удобнее.

Первый шаг в переводе на Пролог - замена for более простой формулировкой для цикла, точнее определяющей, что происходит с I на каждом шаге. Используем для этого определение while:

   Р:=1; /* Инициализация Р и I */
   I:=1;
   while I <= N do /* Задание цикла */ 
    begin
      Р:=Р*I; /* Обновление Р и I */
      I:=I+1 
    end; 
   FactN:= P;  /* Показать результат */

Программа показывает переведенный на Пролог цикл while языка Pascal.

  predicates
     factorial(integer,integer)
     factorial_aux(integer,integer,integer,integer)  
  clauses    
     factorial(N, FactN):-
        factorial_aux(N,FactN,1,1).
     factorial_aux(N,FactN,I,P):-
        I <= N,!,
        NewP=P * I,
        New1=I+1,
     factorial_aux(N,FactN,New1,NewP).
     factorial_aux(N,FactN,I,P):- 
        I > N,
        FactN=P.

Текст этой программы можно взять здесь.

Результат работы программы можно посмотреть на рис.1

Рис.1. Результат работы программы pro41_1.pro

Рассмотрим программу более детально. У предложения для предиката factorial есть только два аргумента - N и FactN. Oни являются как бы входом и выходом, если смотреть с точки зрения того, кто вычисляет факториал. Предложения для factorial_aux(N,FactN,I,P) фактически обесчивают рекурсию. Их аргументами являются четыре переменные, которые должны предаваться из одного шага в другой. Поэтому factorial просто вызывает factorial_aux, передавая ему N и FactN с начальными значениями для I и Р:

  factorial(N,FactN):-
     factorial_aux(N,FactN,1,1).

Так I и P инициализируются.

Но как factorial передает FactN, ведь у нее пока нет еще значения? Ответ заключается в том, что Пролог здесь унифицирует переменную, названную FactN в одном предложении, с переменной, названной FactN в другом предложении. Таким же образом factorial_aux передает себе FactN в качестве аргумента и рекурсивном вызове. В конечном счете последняя FactN получит значение, и после этого все другие FactN, которые унифицировались с ней, получат такое же значение. Пролог может определить из исходного кода, что FactN в действительности не используется перед вторым предложением factorial_aux, а все время передается одна и та же FactN.

Теперь о работе factorial_aux. Обычно этот предикат проверяет предложение "I меньше либо равно N" для циклического вычисления, а затем рекурсивно вызывает себя с новыми значениями для I и P. Здесь проявляется еще одна особенность Пролога. В Прологе верное для арифметики выражение

P=Р+1
совсем не является определением присвоения (как это должно быть на большинстве других языков программирования).

Замечание: Вы не можете изменить значение переменной в Прологе.

В Прологе это так же абсурдно, как и в алгебре. Вместо этого вы должны создать новую переменную и придать ей нужное значение. Например:

   NewP=Р+1

Поэтому первое предложение выглядит следующим образом:

   factorial_aux(N,FactN,I,P):-
      I <= N,!,
      NewP=P*I,
      Newl=I+1,
      factorial_aux(N,FactN,Newl,NewP).

Как и в случае cutcount2, в этом предложении отсечение будет обеспечивать оптимизацию хвостовой рекурсии, хотя оно и не является последним предложением в предикате.

В конечном счете I будет превышать N; текущие значения P и FactN унифицируются и рекурсия прекратится. Это реализуется во втором предложении, которое выполнится, когда проверка I<= N в первом предложении будет неуспешна.

   factorial_aux(N,FactN,I,P):-
      I>N,
      FactN=P.

Здесь нет необходимости делать FactN=P отдельным шагом; унификация может происходить в списке аргументов. Подстановка одинакового названия переменных требует, чтобы аргументы в этих позициях были равны. Более того, проверка I>N избыточна, т. к. обратное было проверено в первом предложении. Это дает завершающее предложение:

   factorial_aux(_,FactN,_,FactN).

На следующем шаге мы начнем рассматривать списки и рекурсию.

Предыдущий шаг Содержание Следующий шаг