Cтраница 1
Рекурсивное состояние соответствует непустому списку, длина которого равна длине его хвоста, увеличенной на единицу. [1]
В рекурсивном состоянии мы начинаем строить выходной список с помощью прогрессирующей подстановки, констатируя, что Н, голова первого входного списка, должна быть первым элементом выходного списка. [2]
В рекурсивном состоянии выходной список строится с помощью прогрессирующей подстановки. [3]
В этих тестах косвенно проверяется и второе базовое состояние, так как рекурсивные состояния сокращают входной аргумент до пустого списка. [4]
Главное, чему может научить данный пример, - это правильное размещение предиката отсечения в утверждениях для рекурсивных состояний. В первом и четвертом утверждениях отсечение находится на первом месте тела утверждения, потому что состояние идентифицируется образцом в заголовке утверждения. Таким же образом состояние идентифицируется и во втором утверждении, но здесь отсечение не обязательно, так как состояние пустого списка исключает три последующих состояния. Его использование просто увеличивает эффективность. Если состояние идентифицируется подцелью, как это наблюдается в третьем утверждении, отсечение размещается непосредственно за этой подцелью. Альтернативы возврата не отбрасываются при выявлении каждого состояния, но как только состояние будет распознано, другие состояния станут недостижимыми. [5]
Альтернативные подстановки не могут быть получены в силу того, что отсечение, введенное в утверждение для базового состояния, блокирует механизм возврата, который, если бы отсечения не было, мог бы создавать альтернативы через рекурсивные состояния. Такое ограничение может считаться вполне приемлемым, если мы уверены в том, что данный предикат будет использоваться только для проверки принадлежности элемента списку. [6]
Однако эта программа не сможет завершить свою работу, если цель должна дать отказ. Виновником выступает утверждение для рекурсивного состояния - оно является леворекурсивным. Это означает, что рекурсивный вызов находится в начале его тела. Для тех целей, которые должны получить отказ, рекурсивная подцель после того, как будут просмотрены все звания, должна будет получить ту же форму, что и ее родительская цель. При этом она не приблизится к базовому состоянию. Полным решением данной проблемы служит перестановка как утверждений, так и подцелей в теле рекурсивного утверждения. [7]
Для примера рассмотрим, как можно протестировать процедуру для предиката сжать / 4, данную в подразд. Для этой процедуры было выделено три рекурсивных состояния. Рисунок 9.1 демонстрирует тестовые - данные для каждого из них. [8]
Мы должны исследовать и то, каким образом в утверждениях для каждого из рассмотренных состояний выражаются требования к их обработке. Особенно следует обратить внимание на то, как в утверждениях для рекурсивных состояний формулируются аргументы рекурсивных вызовов из аргументов, находящихся в заголовках этих утверждений. Следует также убедиться в том, что при каждом вызове мы приближаемся к базовому состоянию. [9]
Рекурсивная процедура должна обладать утверждениями по крайней мере для одного базового и одного рекурсивного состояния. [10]
Первое, что нужно сделать при процедурном исследовании выполнения корректной в декларативном смысле процедуры, - это определить, наверняка ли вызов приведет к ее завершению. При использовании метода анализа состояний Вы не столкнетесь с проблемой зацикливания процесса, если поместите утверждения для базовых состояний перед рекурсивными утверждениями, а также если убедитесь, что рекурсивные состояния приближают процесс к базовому состоянию. Для примера рассмотрим процедуру для предиката младше по званию / 2, альтернативную той, что была дана в разд. [11]