Prolog #4.2

… Так, унифицируя первый аргумент запроса с первым параметром [H|Tail] в голове правила, мы “разделяем” список на голову и хвост. Хвост списка затем становится первым аргументом рекурсивного вызова. Это пример использования | способом, похожим на head и tail в Hugs. Давайте выясним, что произойдет если мы проследим за вызовами. Для начала, вы должны ввести в “консоли” Prolog “trace.”, для того, чтобы включить возможности трассировки. После того, как вы это сделали, каждый запрос, который вы сделаете (включая те, о которых вы думаете, как о командах) будут протрасированы. Введите запрос (первая строка, ниже) и нажмите enter. Следующая таблица – это аннотированная версия того, что должно появиться на экране (примерно) (оставляю без перевода, все довольно очевидно)

В комментариях справа мы выделяем подстановки, которые следует запомнить. На первом шаге, в качестве результата унификации первоначального запроса с головой второго правила append, переменная Result унифицируется с [a|NewTail], где NewTail – это переменная, которая еще не имеет значения. На втором шаге, где происходит первый рекурсивный вызов, NewTail унифицируется с [b|NewTail]. Запомните, что каждый раз, когда используется правило, переменные рассматриваются как новые сущности, без предыдущих значений. По этой причине, суффикс 1 в переменной  NewTail1 показывает, что это другая, отличная от NewTail переменная.

Когда вычисления достигают шага 4, первый аргумент становится пустым списком. Этот запрос унифицируется с первым правилом append, и, в процессе этого шага, NewTail2 унифицируется со списком [d, e]. На данный момент, вычисления завершается, и мы разматываем рекурсию. Однако, в процессе этого разматывания, мы обратно подставляем подстановки любых переменных, которые были инстанциированы (которым были присвоены значения) в ходе рекурсии. Вот как финальный результат append конструируется. В частности, при возврате с рекурсивного вызова в шаге 3, мы обратно передаем подстановку NewTail2 внутри [c|NewTail2]. Результат – список [c, d, e]. Этот список становится значением, сохраняемым в переменной NewTail1. Далее, мы передаем значение NewTail1 в вызове [b|NewTail1]. Т.к мы на прошлом шаге вычислили, что NewTail1 – это [c, d, e], текущая обратная подстановка выводит список [b, c, d, e], который будет сохранен в NewTail. Наконец, в последнем возврате, значение NewTail обратно подставляется в вызове [a|NewTail], что приводит к списку [a, b, c, d, e]. Вот как получается ответ, сохраняемый в переменной Result. Обратные подстановки показывают, как происходит передача значений между рекурсивными вызовами, и как | используется в качестве конструктора списков, для того, чтобы объединять элементы в список.

Вот и подошла к концу глава про списки. Будет еще с заданиями подраздел. Перевод немного кривоват, но вдохновение куда-то ушло. Надеюсь придет. =)