Суперкомпилируем суперагентов
Александр Корлюков
Начнем с детской задачки.
Задача 1. Летит стая гусей, а навстречу ей - один гусь. Один гусь и говорит "Здравствуйте, сто гусей !". На что вожак отвечает :
- нас не 100 гусей. Вот если взять всех нас, до еще столько, да еще пол-столько, да еще четверть столько, до еще тебя гуся, то получится ровно сто гусей.
Спрашивается, сколько гусей в стае ?
Школьник младших классов просто подберет ответ - 36 гусей. Знакомые с алгеброй обозначат количество гусей через x, составят уранение и получат ответ.
Здесь мы предлагаем использовать суперкомпилятор (A Nemytykh, V.Turchin. The supercompiler SCP4 in language refal-5, http://botik.ru/pub/local/scp/refal5/refal5.html ) для организации процесса компьютерных решенияй этой и еще нескольких задач.
Суперкомпилятор производит глубокий анализ заданной программы на языке программирования рефал-5 (V.F. Turchin. "Refal-5, Programming Guide & Reference Manual.", New England Publishing Co., 1989, electronic version: http://www.botik.ru/pub/local/scp/refal5/ ,2000.) и строит, если это возможно, более оптимальную программу. Оптимизация возможна, если часть исходных данных обрабатываемой программы фиксирована. Такое всегда происходит с интерпретирующими программами.
Примеры успешного применения суперкомпилятора можно посмотреть на сайте (Корлюков А.В. Пособие по суперкомпиляции http://www.refal.net/supercom.htm ,1999) Экзотическим применением суперкомпилятора является получение математических формул.
Будем решать задачу про гусей при помощи суперкомпилятора. Пишем программу, которая по количеству гусей, определяет, подходит ли это количество под вопрос в задаче или не подходит.
$ENTRY Go {
e.1 = <Eq (<A e.1>) (<G100 >)>;
}
A {
e.1 = <G e.1>
<G e.1>
<G12 e.1>
<G14 e.1>
'g';
}
G {
e.1 = e.1;
}
G12 {
= ;
'gg' e.1 = 'g' <G12 e.1>;
}
G14 {
= ;
'gggg' e.1 = 'g' <G14 e.1>;
}
Eq {
( ) ( ) = T;
('g' e.1) ('g' e.2) = <Eq (e.1) (e.2)>;
(e.1) (e.2) = F;
}
G100 {
=
'gggggggggggggggggggggggggggggggggggggggggggggggggg'
'gggggggggggggggggggggggggggggggggggggggggggggggggg' ;
}
Программа на языке рефал-5 состоит из набора функций, в нашем случае это Go, A, G, G12, G14, Eq, G100. Каждая функция состоит из предложений, отделяемых друг от друга символом ";". Каждое предложение состоит из левой и правой частей - они отделяются символом "=". В левой части описывается образец, в правой - результат замены. При описании образцов и результатов замен используются переменные выражения, например, e.1 , e.2 , переменные символа - s.a , s.b , а также конкретные символы, которые заключаются в кавычки. При задании структуры выражений можно использовать структурные скобки в обычном понимании.
Функция A получает в качестве аргумента неизвестное количество гусей и строит, обращаясь к функциям G, G12, G14 то количество гусей, о котором сказано в условии задачи. Функция G100 с пустым аргументом строит 100 гусей, а функция Eq сравнивает оба количества гусей, выдавая в качестве результата замены T (истина) или F (ложь) при равенстве или неравенстве.
Суперкомпилируем эту программу, получаем
$ENTRY Go {
'gggggggggggggggggggggggggggggggggggggggg' e.41 = F ;
'gggggggggggggggggggggggggggggggggggg' = T ;
'gggggggggggggggggggggggggggggggg' = F ;
'gggggggggggggggggggggggggggg' = F ;
'gggggggggggggggggggggggg' = F ;
'gggggggggggggggggggg' = F ;
'gggggggggggggggg' = F ;
'gggggggggggg' = F ;
'gggggggg' = F ;
'gggg' = F ;
= F ;
}
Если 36 гусей, то истина, иначе - ложь. Представляет интерес первое предложение - мы не только нашли ответ, но и доказали, что других решений нет.
Если теперь убираем в функции Eq третье предложение, то получаем
$ENTRY Go {
'gggggggggggggggggggggggggggggggggggg' = T ;
}
Задача 2. Шеф разведки, где служит Агент007, в целях полной конспирации и надежности придумал схему взаимной слежки своих агентов.
Агент001 следит за тем агентом, который следит за Агентом002.
Агент002 следит за тем агентом, который следит за Агентом003.
Агент003 следит за тем агентом, который следит за Агентом004.
Агент004 следит за тем агентом, который следит за Агентом005.
Агент005 следит за тем агентом, который следит за Агентом006.
Агент006 следит за тем агентом, который следит за Агентом007.
Агент007 следит за тем агентом, который следит за Агентом001.
Все шло нормально, пока на службу не пришел Агент008. Никак у шефа не получается составить подобную схему взаимной слежки для восьми агентов.
Задача (а). Какая схема взаимной слежки была сначала (за кем следит каждый агент)?
Задача (б). Почему при 8 агентах у шефа ничего не получается ?
Решение с помощью суперкомпилятора.
Возьмем программу из первого параграфа "Подстановки. Подстановочные шифры" Пособия по суперкомпиляции.
Perm {
(e.perm) s.a e.string = <PermS s.a e.perm> <Perm (e.perm) e.string>;
(e.perm) = ;
}
PermS {
s.a (s.a s.b) e.2 = s.b;
s.a (s.c s.b) e.2 = <PermS s.a e.2>;
* s.a = s.a;
}
Eq {
(s.a e.1) (s.a e.2) = <Eq (e.1) (e.2)>;
( ) ( ) = T;
* (e.1) (e.2) = F;
}
Программа осуществляет шифрование текста e.string в соответствии с заданным шифром e.perm
Взаимная слежка агентов - это как бы шифрование, запишем неизвестную слежку в виде
( ("001" s.1) ("002" s.2) ("003" s.3) ("004" s.4)
("005" s.5) ("006" s.6) ("007" s.7) )
Агент001 следит за неизвестным агентом s.1 и так далее.
По условию задачи, если мы дважды произведем это шифрование (дважды - это сначала один раз, затем еще раз), то это все равно, что один раз применить "последовательный" шифр
("001" "002") ("002" "003") ("003" "004") ("004" "005")
("005" "006") ("006" "007") ("007" "001")
Теперь по условию задачи составляем задание на суперкомпиляции (двойное применение неизвестного шифра равняется известному шифру)
<Eq
( <Perm ( ("001" s.1) ("002" s.2) ("003" s.3) ("004" s.4)
("005" s.5) ("006" s.6) ("007" s.7) )
<Perm ( ("001" s.1) ("002" s.2) ("003" s.3) ("004" s.4)
("005" s.5) ("006" s.6) ("007" s.7) )
"001" "002" "003" "004" "005" "006" "007" > >
)
( <Perm ( ("001" "002") ("002" "003") ("003" "004") ("004" "005")
("005" "006") ("006" "007") ("007" "001") )
"001" "002" "003" "004" "005" "006" "007" >
)
>;
Подчеркнем, что мы здесь ничего не программируем, записываю условие задачи - и только. Полученное никак не годится для каких-либо осмысленных пусков на счет при обычном, без использования суперкомпилятора, программировании.
Действительно, сейчас имеется предикат, принимающий значение истина на ответе к задаче, и ложь (отождествление невозможно) - на не ответе. Если я знаю ответ, то могу пустить программу на счет и получу на экране истину, если не знаю ответа, то тоже могу пустить программу на счет и получить на экране ложь (скорее всего).
После суперкомпилиляции получаем следующую программу
Agent0071 {
"005" "006" "007" "001" "002" "003" "004" = T ;
}
Теперь записываем ответ
Агент001 следит за Агентом005.
Агент002 следит за Агентом006
Агент003 следит за Агентом007
Агент004 следит за Агентом001
Агент005 следит за Агентом002
Агент006 следит за Агентом003
Агент007 следит за Агентом004
Задача (а) решена, переходим к решению задачи для 8 агентов. Составляем аналогичное задание на суперкомпиляцию, суперкомпилируем и получаем сообщение, что решений нет.
Приведем алгебраическое решение, которое будет понятно студентам второго курса университета..
Запишем искомую схему взаимной слежки в виде подстановки а на 8 символах. По условию задачи a^2 = ( 1 2 3 4 5 6 7 8 ) - запись подстановки в виде одного цикла.
Квадрат любой подстановки является четной подстановкой, а подстановка, которая получилась - ( 1 2 3 4 5 6 7 8 ) - нечетная. Противоречие показывает невозможность решения второй задачи.
В случае первой задачи имеем a^2 = ( 1 2 3 4 5 6 7 ) = b.
Подстановка b обладает свойством b^7 = e - тождественная подстановка, а значит,
b^8 = b, при этом b = a^2, поэтому можно взять a = b^4 = ( 1 5 2 6 3 7 4 ).
Если относить эту задачу к обычным переборным, то давайте попробуем организовать такой перебор на каком-либо другом из известных языков программирования ! Семь вложенных друг в друга циклов, которые потом надо будет изменять на восемь циклов, или упорядочить лексикографически варианты.
Задача 3. Найдите такое 10-значное число, в котором первая слева цифра равняется количеству нулей в этом числе, вторая цифра равняется количеству единиц в этом числе, и так далее, десятая цифра равняется количеству девяток в этом числе.
Например, подходит число 6 210 001 000 . Действительно, в нем 6 нулей, 2 единицы, 1 двойка, 1 шестерка, и других цифр нет.
Задача обобщается для чисел произвольной разрядности.
Приведем ответ в этой задаче, который достаточно любопытен.
Для 2-значных чисел - решений нет,
Для 3-значных чисел - решений нет,
Для 4-значных чисел - два решения - 1210 и 2020,
Для 5-значных чисел - одно решение - 21200,
Для 6-значных чисел - решений нет,
Для 7-значных чисел - одно решение - 3211000,
Для n-значных чисел, n>7- одно решение -
n-4 , 2 , 1 , 0 , ... , 0 , 1 , 0 , 0 , 0 .
Решаем задачу при помощи суперкомпилятора.
Число представляем в виде последовательности скобок по одной для каждой цифры. Цифры записываем в унарной системе счисления (нуль - пустое выражение).
Программа, проверяющая, является ли входное число ответом, следующая -
$ENTRY RecNumb {
e.1 = <RecEnd <Rec ( ) <Fltr ( ) e.1>>>;
}
Rec {
(e.1) = e.1;
(e.1) (e.2) e.3 = <Rec1 (e.2) <Rec (e.1 (e.2)) e.3> >;
}
RecEnd {
( ) e.2 = <RecEnd e.2>;
= T;
}
Rec1 {
( ) ('1' e.2) e.3 = (e.2) e.3;
('1' e.1) (e.2) e.3 = (e.2) <Rec1 (e.1) e.3>;
}
Задание на суперкомпиляцию для фиксированного количества цифр задается последовательностью скобок, например, для 5-значных чисел
<RecNumb (e.1) (e.2) (e.3) (e.4) (e.5) > ;
Схема математического решения. Пусть a0 , a1 , ... , an - цифры искомого n+1-значного числа. Подсчет количества цифр (=n+1) различными способами (от перестановки мест слагаемых сумма не меняется) дает два соотношения
a0 + a1 + ... + an = n+1
0*a0 + 1*a1 + 2*a2 + ... + n*an = n+1
Т.е., сумма цифр равняется значности числа, и сумма с коэффициентами тоже равняется значности числа.
Далее идет какой-то перебор возникающих вариантов с учетом большого количества нулей.
Задача 4. Вычисление последовательности Фибоначчи матричным способом. Последовательность Фибоначчи F(k) определяется правилами F(1) = 1, F(2) = 1, F(k+2) = F(k) + F(k+1)
В этой задаче каждая последующая пара элементов последовательности Фибоначчи вычисляется через предыдущую пару путем умножения на матрицу
A = ( 0 1 )
( 1 1 )
(как на практических занятиях по алгебре на втором курсе университета). В результате получается что-то похожее на геометрическую прогрессию - произвольная пара элементов выражается через первую пару
( F(k) , F(k+1) ) = ( F(0) , F(1) ) * A^k
Для возведения матрицы в произвольную степень существуют свои способы. Это является примеров применения матриц к рекуррентным последовательностям, таким способом можно выводить формулы для общих членов последовательностей. Начальные значения могут быть любыми (и любое количество), матрица может быть любого размера (т.е. последующий элемент может выражаться через три или четыре и т.д. предыдущих элементов, не обязательно сумма). Таким образом происходит разделение начальных значений рекуррентной последовательности (они в начальном векторе) и закона образования последовательности (он в матрице).
Суперкомпилируется программа, в которой имеются функция вычисления скалярного произведения любых векторов, функция умножения матрицы на вектор, причем матрица представлена по строкам, а для умножения нужны столбцы. Обращаем внимание, что при обращении вычисляются два последовательных элемента последовательности Фибоначчи, хотя реально нужен лишь один элемент, второй уже имеется. Суперкомпилятор благополучно разбирается, что вычисленное совпадает с имеющимся. Все умножения на 0 и на 1 упрощаются, сумма с 0 - тоже.
Приводим программу
$ENTRY Fibonacci {
e.begin (e.k) (e.k1) = e.begin (e.k)
<MulVM ((e.k) (e.k1)) (<MatrixA >)>;
}
* Определение матрицы A
MatrixA {
= ( (0) (1) )
( (1) (1) );
}
* Умножение вектора на матрицу
MulVM {
(e.vector) ( ) = ;
(e.vector) (e.matrix) = <MulVV (e.vector) (<Mfirst e.matrix>)>
<MulVM (e.vector) (<Mlast e.matrix>)>;
}
Mfirst {
= ;
((e.1) e.2) e.3 = (e.1) <Mfirst e.3>;
}
Mlast {
= ;
((e.1) ) e.3 = <Mlast e.3>;
((e.1) e.2) e.3 = (e.2) <Mlast e.3>;
}
* Умножениевектора на вектор (скалярное произведение)
MulVV {
(e.v1) (e.v2) = <MulVV1 (0) (e.v1) (e.v2)>;
}
MulVV1 {
(e.rez) ( ) ( ) = (e.rez);
(e.rez) ((e.1) e.2) ((e.3) e.4) = <MulVV1
(<Add (e.rez) <Mul (e.1) e.3>>)
(e.2) (e.4)>;
}
В результате суперкомпиляции получаем
$ENTRY Fibonacci {
e.41 (e.102) (e.101) = e.41 (e.102) (e.101) (<Add (e.102) e.101>) ;
}
Задача 5. Получить автоматически компилятор машины Тьюринга в язык рефал-5.
В теоpии алгоpитмов в качестве точного математического эквивалента для общего интуитивного пpедставления об алгоpитме используется понятие машины Тьюpинга .
Пpогpамма для машины Тьюpинга состоит из последовательности инстpукций. Каждая инстpукция имеет вид
CurrentState CurrentSymbol NextSymbol NextState Move
где
CurrentState - текущее внутpеннее состояние,
CurrentSymbol - обозpеваемый символ,
NextSymbol - символ, котоpый пишется в обозpеваемую ячейку,
NextState - последующее внутpеннее состояние.
Move - напpавление сдвига головки ('L' или 'R' ), 'L' означает сдвиг головки влево, 'R' - сдвиг головки впpаво на одну ячейку.
Пpедполагается, что в обе стоpоны от введенной последовательности символов находится бесконечное количество символов пpобел (пробел будем обозначать символом "b").
Hачальное внутpеннее состояние - "A", конечное внутреннее состояние - "Z".
Работа машины Тьюpинга состоит из последовательности шагов. Hа каждом шаге пpоисходят следующие действия:
1. Если текущее внутpеннее состояние "Z", то пpоисходит остановка pаботы пpогpаммы.
2. По текущему внутpеннему состоянию CurrentState и обозpеваемому символу CurrentSymbol ищется инстpукция с левой частью CurrentState CurrentSymbol .
3. Если такой инстpукции нет, то пpоисходит остановка pаботы с аваpийным сообщением "Hет инстpукции с левой частью CurrentState CurrentSymbol".
4. В найденной инстpукции pассматpивается пpавая часть, т.е. значения NextSymbol NextState Move.
5. Символ NextSymbol пишется в обозpеваемую ячейку.
6. Головка сдвигается впpаво или влево на одну ячейку в соответствии с символом Move.
6. Машина пеpеходит в новое внутpеннее состояние NextState.
7. Hа этом выполнение шага заканчивается. Машина Тьюpинга пеpеходит к выполнению следующего шага.
Рассмотрим пример программы для машины Тьюринга - удвоение количества единиц на ленте с заменой их на двойки. Если, к примеру, на ленте в начале находится 10 единиц, то в конце будет находиться 20 двоек.
CurrentState CurrentSymbol NextSymbol NextState Move
A b . Z R
A 2 2 A R
A 1 2 B L
B 2 2 B L
B b 2 A R
|
Ниже приведено преобразование двух единиц в четыре двойки (под обозреваемым символом написано текущее внутреннее состояние машины Тьюринга).
b b b 1 1 b b
A
b b b 2 1 b b
B
b b 2 2 1 b b
A
b b 2 2 1 b b
A
b b 2 2 2 b b
B
b b 2 2 2 b b
B
b b 2 2 2 b b
B
b 2 2 2 2 b b
A
b 2 2 2 2 b b
A
b 2 2 2 2 b b
A
b 2 2 2 2 b b
A
b 2 2 2 2 . b
Z
Рассмотрим суперкомпиляцию интерпретатора машины Тьюринга, который написан на рефале.
Интерпретатор выглядит так
$ENTRY Go {
(s.symbol) (e.tape ) = <Turing ( ('Ab.ZR')
('A22AR')
('A12BL')
('B22BL')
('Bb2AR') )
('A') ( ) (s.symbol) (e.tape ) >;
}
Turing {
(e.instr) ('Z') (e.left) (s.symbol) (e.right) =
(e.left) (s.symbol) (e.right) ;
(e.instr) (s.q) (e.left) (s.symbol) (e.right) =
<Turing (e.instr) <Turing1
<Search (s.q s.symbol) (e.instr)>
(e.left) (s.symbol) (e.right)> >;
}
Turing1 {
(s.c s.r 'L') (e.left s.a) (s.symbol) (e.right) =
(s.r) (e.left) (s.a) (s.c e.right) ;
(s.c s.r 'R') (e.left) (s.symbol) (s.a e.right) =
(s.r) (e.left s.c) (s.a) (e.right) ;
}
Search {
(s.q s.b) ((s.q s.b s.NextSymbol s.NextState s.Move) e.instr) =
(s.NextSymbol s.NextState s.Move);
(s.q s.b) ((e.1) e.2) = <Search (s.q s.b) (e.2)>;
}
|
После суперкомпиляции получаем программу
$ENTRY Go {
(s.102 ) (e.103 ) = <F20 s.102 (e.103 )> ;
}
F41 {
(e.109 ) (e.111 s.124 ) '2' = <F41 ('2' e.109 ) (e.111 ) s.124 > ;
(s.128 e.109 ) (e.111 ) 'b' = <F20 s.128 (e.109 ) e.111 '22' > ;
}
F20 {
'b' (s.112 e.109 ) e.111 = (e.111 '.' ) (s.112 ) (e.109 ) ;
'2' (s.116 e.109 ) e.111 = <F20 s.116 (e.109 ) e.111 '2' > ;
'1' (e.109 ) e.111 s.123 = <F41 (e.109 ) (e.111 ) s.123 > ;
}
|
Здесь все прекрасно видно. Функция F20 соответствует внутреннему состоянию "A" , функция F41 соответствует внутреннему состоянию "B". Каждое предложение соответствует одной инструкции программы для машины Тьюринга. Количество рефал-шагов равняется количеству шагов машины Тьюринга.
Выходом суперкомпилятора является оптимальная программа на рефале, то есть произошла компиляция программы для машины Тьюринга в рефал-программу .
Для получения коэффициентов ускорения выполнения мы подготовили пример из 256 единиц.
Выполнение рефал-программы состоит из последовательности элементарных действий, называемых шагами
До суперкомпиляции количество рефал-шагов равняется 656 908, время - 8.950 секунды, после суперкомпиляции количество рефал-шагов равняется 131 082, время - 1.050 секунды. Таким образом, мы имеем ускорение по шагам Kstep = 5.011, ускорение по времени Ktime = 8.524.
Все примеры выполнялись на машине Pentium200, операционная система Windows98, использовалась версия языка рефал - рефал-5