Решил начать новую тему, чтобы обсудить интересный (я бы даже сказал, концептуальный) вопрос о формализации алгоритмических знаний. Почему в разделе про Дракон – да потому что Дракон рассматривается на этом форуме как наиболее подходящий кандидат для представления алгоритмических знаний.
Возможно, я многого не знаю в теории по этому вопросу, и надеюсь на просвещение с Вашей помощью...
Итак, рассмотрим конкретный пример: копирование данных из одной области памяти в другую. В этой простейшей задаче я, как ни странно, зашёл в тупик, пытаясь определить, в чём именно здесь будут состоять алгоритмические знания и что же такое, собственно, есть алгоритм.
Начнём, как обычно, с неформальной картинки:
Вложение:
Комментарий к файлу: Задача копирования
move_problem.PNG [ 3.34 КБ | Просмотров: 28596 ]
И ещё необходимое уточнение: размер ячейки памяти - пусть будет 2-байтовое слово для определённости (возможно, кто-то сразу захочет услышать извинения из-за «ассемблерной» постановки задачи… ну, что ж делать, задача такая… реальная задача).
Как ни парадоксально это звучит, но на этом обобщённые алгоритмические знания о сути данной задачи… заканчиваются!
Далее начинается слой алгоритмических знаний,
привязанный к конкретному исполнителю.
Вариант 1 (Borland Pascal, Delphi):Код:
var p1,p2:pointer; i:integer;
p1:=откуда; p2:=куда;
for i:=1 to N do begin
Smallint(p2^):=Smallint(p1^);
inc(Longword(p1),2); inc(Longword(p2),2);
end;
М-м… да-а… Что-то некрасиво, ненадёжно (указатели нетипизированные; а хоть бы и типизированными сделать – изменится не сильно!) и вообще какая-то странная эмуляция ассемблерного решения на Паскале… однако, вроде бы полностью соответствует сути задачи. Ну хорошо, сформулируем более чисто (алгоритмически).
Вариант 2 (Borland Pascal, Delphi):Код:
var a1,a2:array[1..N] of Smallint; i:integer;
for i:=1 to N do a2[i]:=a1[i];
Ой… Алгоритм вроде виден, но как его использовать для конкретной задачи? Как описать нужную область памяти (например, видеопамяти) в виде Паскальского массива? Ну, допустим, как-то можно извернуться (оставив за кадром, хотя это не есть хорошо) – но тогда необходимо усложнить алгоритм с учётом начальных смещений, суммируя их с индексами… Ну и т.п.
Хорошо. Каждой задаче - адекватный инструмент. Ассемблер так ассемблер. Вопрос – какой?
Вариант 3 (Asm, DEC PDP-11):Код:
mov откуда, r1
mov куда, r2
mov N, r0
1$: mov (r1)+, (r2)+
sob r0, 1$ ;Subtract One and Branch if not zero
Решение элегантное, эффективное… За счёт особенностей конкретного исполнителя, который разрешает автоинкрементную адресацию и имеет специальную команду для организации цикла.
А не взять ли другой процессор?
Вариант 4 (Asm, Infineon C167):Код:
mov r1, откуда
mov r2, куда
mov r0, N
L_1: mov [r2+], [r1]
add r1, #2
sub r0, #1
jmp cc_NZ, L_1
Вот незадача… Оба регистра-указателя процессор не позволяет инкрементировать в одной команде. Так… Ещё один процессор (догадайтесь сами, какой
):
Вариант 5 (Asm, Intel 8086):Код:
lds si, откуда
les di, куда
mov cx, N ;сколько
cld ;в каком направлении
rep movsw ;поехали!
Цикл реализуется микропрограммно, я рад безмерно… Вот только куда подевался алгоритм копирования как таковой?
Ну и, наконец, ближе к кандидату на «универсальный описатель алгоритмов» - Дракону. Что же в нём описывать? Алгоритм? И каков, на самом деле, алгоритм решения данной задачи? Вариант 2? Или 1? Ну хорошо, пусть вариант 1 – вернулись к тому, с чего начали:
Вложение:
Комментарий к файлу: алгоритм копирования на Драконе
move.PNG [ 3.07 КБ | Просмотров: 28594 ]
Ну а, что, если воспользоваться неязыковыми средствами? Например, процедурой Move(Src,Dst,Count) в Delphi? Хорошо, это правильное решение, Delphi7 содержит код этой процедуры по типу варианта 5 (ну, с учётом 32-разрядности, конечно). Причём, если позволяет количество копируемых данных, использует не movsw, а movsd, что, естественно, ещё эффективнее… затрачивая только пару команд на проверку и ветвление перед началом цикла…
А вот сейчас взял да и посмотрел, какой код делает более свежая версия - Turbo Delphi… Ой! Я ничего не понимаю… После кучи проверок на более эффективные случаи (когда можно обойтись парой простых команд копирования вместо цикла) – реализуется обычный цикл (!), причём данные в цикле копируются не напрямую, и не через регистр общего назначения, а… через стек FPU ! Может, я чего-то не понял с ходу… но комментировать больше неохота…
Кроме того, очевидно, что на все случаи жизни системных процедур не напасёшься.
Собственно, для чего меня всё это интересует? Как ни странно, для вполне практической цели – хочу к Дракон-редактору прикрутить кодогенератор… На самом деле почти без разницы, к чему прикручивать кодогенератор – к Дракону или какому текстовому ЯВУ… А вот что именно компилировать? Смотрим – даже в такой простой задаче ну никак не отделяется чистый алгоритм от того слоя, в котором можно было бы отдельно учесть особенности исполнителя (естественно, ставится задача получения не просто работающего кода, но кода оптимального. Причём оптимального кода для разных целевых платформ).
Применить шаблоны? Дык, на все случаи шаблонов не напасёшься… да и как их распознавать в общем случае? Как придумать шаблон даже для такой несложной задачи? Особенно, если учесть, что от размера ячейки памяти в этой задаче реализация кода может существенно меняться, как и его эффективность…
Использовать оптимизирующий компилятор ЯВУ? Но какой компилятор сможет оптимизировать даже «приближённый к ассемблеру» вариант 1?
Вот такие вопросы. Если они останутся риторическими, я не удивлюсь… Но должна же что-то говорить теория… Про то, что такое алгоритм и с чем его едят…