Задача 13.1. Представьте в виде выражения на языке Haskell программу быстрого возведения в степень. Проверьте, что программа действительно работает, задав в качестве примера исходные данные для вычисления 2 в степени 10.
Решение. Программа быстрого возведения в степень на простом императивном языке, представленном в гл. 13, может выглядеть следующим образом (переменные аир содержат исходные данные — основание и показатель степени, переменная z будет содержать результат): z = 1;
while (р > 0) {.
if'(р % 2 == 1) {.
z = z * а; р = р-1;
} else {
а = а*а;р = р/2;
}.
}.
В представлении в виде значения типа Statement эта программа будет выглядеть следующим образом: power = Sequence [.
Assignment «z» (Const 1),.
Loop (Binary (Variable «p») «>» (Const 0)).
- (Select (Binary (Binary (Variable «p») «%» (Const 2)) «==»
- (Const 1))
- (Sequence [
Assignment «z» (Binary (Variable «z») «*» .
(Variable «a»))/.
Assignment «p» (Binary (Variable «p»).
Assignment «a» (Binary (Variable «a») «*» .
(Variable «a»)),.
Assignment «p» (Binary (Variable «p») «/» .
(Const 2))]))].
Теперь можно собрать все определения типов данных и функций интерпретации программ, представленных в гл. 13, в единую программу, описать начальный контекст переменных и запустить интерпретатор. Результат работы интерпретатора показан ниже:
" interpret power [(«a», Const 2), («р», Const 10), («z», Const 0)] [(«p», 0), («z», 1024), («a», 256)].
В переменной z получен правильный результат.
Задачи для самостоятельного решения
Задача 13.2. Представьте в виде выражения на языке Haskell программу проверки заданного натурального числа на простоту. Результатом должно быть значение 1, если исходное число простое, и 0, если нс простое. Проверьте, что программа действительно работает, задав в качестве исходных значений числа 13, 25, 103.
Задача 13.3. Введите в простой императивный язык программирования понятие списка целых значений. Добавьте в список примитивных операций операции по созданию, изменению и анализу списков. Как скажутся эти изменения на функции интерпретации?
Задача 13.4. Напишите функцию, которая выдает список всех переменных программы, которым в программе делаются присваивания, но которые не используются ни в одном из выражений в программе.
Задача 13.5. Напишите функцию, которая выводит программу в виде, удобном для чтения (то есть когда присваивания имеют вид v = е;, оператор выбора имеет вид if (condition) operator; else operator;
И Т.Д.).
