3. Запись алгоритмов в «каноническом» виде
. К оглавлению . Показать весь текст .
Мы увидели, что на самом деле «окончательный» текст программы (после его «компиляции» с «языка среднего уровня» - который использует композиции и приоритеты операций в строках программы, например) мы получили такой программный текст, где каждая строка содержит не больше 2 операций. И самый сложный случай, когда:
1. Есть операция присваивания, и есть та функция, которая даёт значение для этого присваивания. Притом данная функция – одна из «базовых» (из ограниченного набора), без всяких «композиций» нескольких операций.
Второй по сложности случай:
2. Оператор goto – который тоже аналог операции присваивания – только присваивания нужного адреса той «переменной», которая указывает на точку исполнения программы. А после оператора goto расположена или переменная, или константа, которая содержит метку, обозначающую нужный адрес.
И последние, самые простые случаи:
3. Оператор метки – который в процессе работы просто пропускается, не вызывая никаких изменений в какой-либо переменной или месте исполнения программы, кроме перехода к исполнению следующей за данной меткой операции в программе. И последний простой случай – оператор остановки «.».
Перечислим все варианты строк программы (с указанием конкретных операторов), которые могут быть в тексте нашей программы в «откомпилированном» виде. Будем считать, что программный текст, составленный по нижеследующим правилам записан в «каноническом» виде.
В конце каждой строки такого «канонического» текста всегда стоит точка с запятой и перевод строки.
Кстати, термин «строка» дальше в статье используется не в смысле теории строк, а в смысле «части текста, разделенные между собой символами перевода строки, и включающие в себя символ перевода строки в конце каждой строки». Понятно, что в смысле теории строк мы считаем программный текст – строкой, но далее в статье мы будем называть его «текст».
Итак, после уточнения толкования тут терминов «текст» и «строка» перечислим те варианты строк, из которых состоит наш программный текст в каноническом виде:
1. метка (эта «команда» служит для перехода к ней, но сама не исполняется) – строка символов в квадратных скобках, например [next_1], сама строка символов составляется по таким же правилам, как названия переменных;
2. goto – пробел используется как разделитель с именем переменной, например goto x;
3. Оператор «.» (точка) – остановка – при этом в программе в «каноническом» виде оператор перед оператором «.» заканчивается точкой с запятой и переводом строки, и после оператора «.» стоит точка с запятой и перевод строки, например:
Return=x;
.;
Далее – оператор присваивания с разными правыми частями, от которых поступают данные для присваивания. Условимся, что пробелы между левой и правой частями присваивания не используются, а внутри функций – используются для разделения аргументов вместе с запятыми, типа x_1(0)=str(x_2, i, j).
Кстати, такая запись c обозначением x_1(0) в «каноническом виде» аналогична записи x_1=str(x_2, i, j) в «не каноническом» виде. Договорённость о 2 разных обозначениях левой стороны присваивания сформулирована в конце 1-го раздела. В п.6 будет напоминание о том, как меняется механизм присваивания в зависимости от значения, которое есть (или если ничего нет) в данных скобках.
В скобках при переменной в левой части присваивания может находиться либо зарезервированная константа, либо переменная, либо вообще ничего. Но данные скобки должны быть в любом случае при записи присваивания в каноническом виде. Тонкий момент про зарезервированные константы и про 0 (Ноль) в левой части присваивания тоже будет рассмотрен после пункта 8. Сейчас лишь отмечу, что 0 (Ноль) тут без кавычек, потому что это – зарезервированная константа.
А правые части присваивания могут быть следующие при канонической записи:
4. Функция Chr(…) – с одной переменной (числом) или зарезервированной константой (которая является числом к тому же) в качестве аргумента – работает так, как это описано в теории строк в предыдущей статье;
5. Функция str(…) – c тремя переменными/зарезервированными константами в качестве аргументов (2 из которых - числа) – работает так, как это описано в теории строк в предыдущей статье;
6. «Функция» Assign(…) – значение другой переменной/зарезервированной константы для присваивания – самый простой случай присваивания одной переменной значения другой переменной (или зарезервированной константы). То есть, если в неканоническом виде мы пишем
a=b;
то в «каноническом» виде это же самое будет записано для единообразия так:
a(0)=Assign(b);
Но тут есть очень важный способ применения «функции» Assign, выполняющий роль конкатенации:
a()=Assign(b);
Это приводит к тому же результату, к которому в «не каноническом» виде ведёт операция:
a =a ⋅ b;
То есть, операция в «не каноническом» виде:
a = b ⋅ c;
Сводится к таким двум операциям в «каноническом» виде:
a(0)=b;
a()=Assign(c);
Если же значение у переменной в скобках больше 0, то для случая (например):
a(i)= Assign(b);
Переменная a изменится только с i-го символа по i+len(b)-1 символ включительно. На их местах окажутся все символы значения переменной b c 1-го символа по len(b)-й символ соответственно.
Но есть исключение из данного правила для a(i): если i > len(a), то результат работы разбираемого варианта присваивания (a(i)= Assign(b);) не будет отличаться от предыдущего варианта присваивания в данном пункте:
a()= Assign(b);
Примеры были приведены в конце 1-го раздела.
7. Функция Comp(…) – c двумя переменными/зарезервированными константами в качестве аргументов – работает так, как это описано в теории строк в предыдущей статье;
8. «Функция» Const(…) – константа, значение которой присваивается переменной в левой части присваивания только двумя способами:
8.1. Значение из Const(…) присваивается «целой» переменной, например, случай пустой строки:
x_1(0)=Const();
Пример присваивания не пустой строки:
a(0)=Const(To be, or not to be, );
8.2. Значение из Const(…) дописывается в конец переменной, например:
a()=Const(that is the question:);
Оставшийся метод присваивания не используется с конструкцией Const(…). Например, конструкция:
a(i)=Const(…);
не используется, если i ≠ 0.
При помощи конструкции Const(…) можно представлять любые строки, кроме строк с символом перевода строки ChrEnter, что будет разобрано чуть ниже.
Всё остальное сводится к этим 8 случаям.
При желании можно добавить к функциям в правой части оператора присваивания ещё и функцию len(), а можно просто написать (под)программу, вычисляющую, чему равна длина строки. Поэтому функцию len() рассматривать как одну из базовых для алгоритмов не будем. Так же, как увеличение на единицу и прочие арифметические операции – все они могут быть рассчитаны при помощи (под)программ, составленных из базовых функций.
Заметим, что в качестве аргументов функций мы не используем константы помимо зарезервированных (кроме пункта 8) – это для сокращения числа вариантов. Всегда можно присвоить константу некоторой переменной и работать с данной переменной вместо константы.
Что же касается зарезервированных констант, то это только 2 константы для обозначения 2 символов: 0 (Ноль) и символ перевода строки ChrEnter.
Имя зарезервированной константы 0 (Ноль) совпадает с её значением. В таком совпадении нет ничего удивительного, потому что и для переменной такое возможно:
x = «x»; - в неканонической записи,
x=Const(x); - в канонической записи.
Исключительным в зарезервированной константе 0 (Ноль) является только то, что это название (а это именно название – как у нас есть названия переменных) начинается на цифру. Ведь название 0 (Ноль) из одной цифры и состоит. И это единственное исключение из правил составления имён. Потому что в общем случае имена не могут начинаться на цифру, не могут содержать в себе ни скобки, ни знаки операций, ни знаки пунктуации, ни пробелы и т.п.
Зарезервированную константу 0 (Ноль) мы ввели для удобства – потому что у нас есть важный случай переменной со скобками в левой части присваивания (a(0), например), потому что от этого символа начинается построение (под)программ для арифметических действий и т.д. и т.п.
Теперь – про зарезервированную константу ChrEnter. Рассмотрим конструкцию:
Const(Значение константы);
Такая конструкция представляет собой строку «Значение константы». В «обычном» (не «каноническом») программном тексте мы используем кавычки, чтобы обозначить готовые строки (константы, а не переменные). Но условимся, что и в «обычном» программном тексте можно применять конструкцию Const(), если она заканчивается переводом строки ChrEnter после своей закрывающей скобки и точки с запятой. Вот комбинация этих трёх символов:
);
включая перевод строки ChrEnter, и служат признаком окончания (до этих трёх символов, не включая их) строки-константы. Условимся, что внутри строки-константы не может находится символ перевода строки ChrEnter. Все остальные символы (даже не графические!) могут содержаться внутри строки-константы, включая комбинацию символов «);», например:
Const(Значение константы с такими :-);-) смайликами);
Никакой неоднозначности не возникает, потому что до признака окончания строки-константы в конструкции Const(…) у смайликов тут не хватает символа перевода строки ChrEnter.
Чтобы включить ChrEnter внутрь строки, придётся (для программы в «каноническом виде») использовать конкатенацию с зарезервированной константой ChrEnter. Например:
a(0)=Const(To be, or not to be, that is the question:);
a()=Assign(ChrEnter);
a(0)=Const(Whether ’tis nobler in the mind to suffer);
Конечно, тут мы рассмотрели случай, когда все символы, кроме ChrEnter, имеют графическое выражение. А в принципе внутри конструкции Const(…) могут оказаться и нечитаемые символы, которые при помещении в редактор или браузер переместят следующий символ вверх или влево.
Но «канонический вид» введён не для «разглядывания» программного текста, а для его исполнения и работы с программой как со строкой. А как последовательность символов – программный текст в каноническом виде остаётся строкой и имеет все свойства строк.
Да, есть специальный символ перевода строки ChrEnter, но мы выделяем его не потому, что он «невидимый», в силу чего не имеет графического выражения «чёрным по белому», а потому, что он один из признаков окончания строки программы и, в частности, окончания «функции» Const();
В то же время, в процессе написания программы – когда она имеет «не канонический» вид – некоторые символы невозможно просто так набрать на клавиатуре и увидеть на экране, например. Но ничто не мешает использовать в «не каноническом» виде универсальные методы для записи любого символа «удобным» образом.
Например, в «не каноническом» виде у нас будет присваивание:
x_1 = Chr(«65») ⋅ Chr(«92») ⋅ Chr(«14») ⋅ Chr(«79») ⋅ Chr(«82») ⋅ Chr(«25») ⋅ Chr(«14») ⋅ Chr(«92») ⋅ Chr(«95») ⋅ Chr(«14») ⋅ Chr(«91») ⋅ Chr(«92») ⋅ Chr(«97») ⋅ Chr(«14») ⋅ Chr(«97») ⋅ Chr(«92») ⋅ Chr(«14») ⋅ Chr(«79») ⋅ Chr(«82») ⋅ Chr(«25»);
В этом присваивании мы использовали функцию Chr() с такими аргументами, которые не являются ни переменными, ни зарезервированными константами. Но при «компиляции» такого присваивания – если ни один Chr() в нём не порождает символ перевода строки – превратится в следующее (например) присваивание в каноническом виде
x_1(0)=Const(To be, or not to be,);
Хотя, если «компиляция» не оптимизирована, то «откомпилированное» присваивание из неканонического вида превратится в последовательность примерно таких присваиваний в каноническом виде:
x_1(0)=Const(T);
x_1()=Const(o);
x_1()=Const( );
…
Но и такая последовательность действительно соответствует тому, как работает компьютер с тем, что было изначально записано как «цепочка» конкатенаций в «не каноническом» виде.
Поэтому, если в «не каноническом» виде переменной x_1 присвоена некоторая строка без обращения к переменным в правой части присваивания, то точно такое же присваивание переменной x_1 – без обращения к переменным в правых частях присваивания – можно сделать с использованием конструкций Const(…) и Assign(…) в «каноническом» виде.
Как отмечалось чуть выше – среди приведённых «базовых» функций для работы алгоритмов – нет арифметических операций. И с точки зрения соответствия теории строк, таких операций тоже не могло быть – так как аксиомы арифметики ничего не говорят об алгоритмах вычисления арифметических операций с числами в позиционном представлении, что было разобрано ещё в разделе «1. Недостаточность арифметики для целей теории алгоритмов» первой статьи. Впрочем, аксиомы арифметики дают в теории строк «исходную константу» – 0 (Ноль), на основе которой доступны все остальные строки – через функцию Chr и другие строковые функции, которые используют ещё и функцию следования (увеличения числа на 1).
Тут не следует путать теорию строк и базовые функции для работы алгоритмов. У них совершенно одинаковый вид для удобства доказательства «представимости» алгоритмов в теории, но в то же время алгоритмы не нуждаются в том, чтобы «получать доступ» к строкам через 0 (Ноль). Алгоритмы сразу имеют дело с готовым набором символов и цифр, а мы лишь «подстраиваем» нашу теории под данный набор, добавляя аксиому (или гипотезу) о том, чему именно равны следующие константы нашей теории строк:
l_NumBeg, l_NumLim, l_ChrLim.
А кроме того, надо добавить аксиому (или гипотезу) о том, чему равно ChrEnter.
В заключение этого раздела сделаем одно очень принципиальное (для будущего применения) замечание:
Между программой, работающей отдельно, и той же программой, но оформленной в качестве подпрограммы внутри другой программы – нет разницы с точки зрения того результата, который возвращает данная (под)программа – ни тогда, когда она работает самостоятельно, ни тогда, когда она работает в качестве подпрограммы.
Тонкий момент – для будущей теории программ – это формализация критериев эквивалентности работы программ и всех «равных» ей вариантов подпрограмм. Перечислим 2 (из множества имеющихся) достаточных условия для подобной эквивалентности:
1. Нет никакой разницы, как названы переменные и аргументы (под)программы, если путём их переименований можно получить другую (под)программу без сокращения исходного количества независимых переменных и аргументов;
2. Можно считать, что нет никакой разницы между временем работы (под)программ, если имеется переход между ними при помощи пункта 1,
Нам в дальнейшем потребуется пункт 2, особенно тот факт, что значения переменных и аргументов подпрограмма может иметь сразу внутри тех переменных, которые используются в той программе, которая содержит данную подпрограмму. Выше уже отмечалось, что строить подпрограммы с использованием стека совсем не обязательно. И ничто не мешает отсчитывать время работы подпрограммы с момента исполнения первого оператора в ней – не формируя никакого стека с «передаваемыми аргументами» для этого. Как обычная программа имеет все необходимые данные уже в момент начала своей работы – так же и будучи оформленной в качестве подпрограммы, она может иметь точно то же самое – с точностью до переименований своих аргументов и переменных.
По поводу начала пункта 2 «можно считать» - нужны некоторые пояснения. Если программа записана как строка, то доступ к разным её частям, включая подпрограммы, может требовать различного времени. Но для исполнения подпрограммы можно присвоить её в другую «программную переменную», в которой подпрограмма будет расположена с 1-го символа и этим добиться стандартных условий её работы. А время на «копирование» или обращение к подпрограмме, равно как и возврат к исполнению основной программы, можно считать относящимся к времени работы основной программы, а не временем работы подпрограммы, к которой происходит обращение из основной программы.
Из сказанного мы делаем ещё один вывод:
3. Инициализация используемых в (под)программе переменных и передача в (под)программу значений аргументов, необходимых для работы данной (под)программы – не являются частью работы (под)программы и на них (под)программа не тратит никакого времени своей работs. Точно так же и время возврата из подпрограммы к дальнейшему исполнению основной программы будем считать частью работы и частью времени работы основной программы.
Сделанный в предыдущем абзаце вывод чрезвычайно важен для оценки времени работы алгоритмов проверки NP-языков, например. Потому что «на вход» алгоритму проверки подаётся проверяемое слово и сертификат. Притом время работы программы определяется размером слова – в то время как размер сертификата может быть сколь угодно велик. Но та часть сертификата, которые алгоритм проверки не использовал в своей работе – никак не влияют на время работы алгоритма.
И, кстати, подпрограммы внутри программы проверки точно так же могут использовать лишь часть данных из аргумента «сертификат» – никак не увеличивая время своей работы из-за той части сертификата, которая не была использована в их работе.
4. Блок инициализации:
Будем считать, что в программе, записанной в каноническом виде, есть такой блок операций в начале программы, который состоит только из операций присваивания, в правых частях которых стоят либо Assign() с одной из зарезервированных констант в качестве аргумента, либо «функция» Const() с произвольными константами (включая и пустую строку). И все переменные, которые используются в программе, получают в этом «блоке инициализации» свои «начальные значения» - хотя бы пустую строку.
Все аргументы, которые передаются в программу (если таковые есть) также получают свои значения в этом «блоке инициализации».
Все переменные, которые стоят в левой части присваивания, сопровождаются скобками. И в блоке инициализации эти скобки должны быть либо пустые, либо в них должен быть 0 (Ноль). То есть, каждое присваивание в блоке инициализации представляет собой один из 2-х вариантов:
а. Либо значения присваивания дописывается в конец (конкатенации справа) к прежнему значению переменной (случай пустых скобок при переменной слева от знака присваивания).
б. Либо значение присваивания заменяет собой прежнее значение переменной (случай, когда в скобках при переменной слева от знака присваивания находится 0 - ноль).
Очевидно, что любую программу можно переписать таким образом, чтобы заменить константы (кроме зарезервированных) в «середине» программы на переменные, содержащие эти константы в качестве своих значений. А сами эти значения присвоить в блоке инициализации.
А перечисленные операции присваивания позволяют присвоить любой переменной любую строку. Например, если в «не каноническом» виде присваивание имеет такой вид:
x_1 = «Буря мглою небо кроет,» ⋅ ChrEnter ⋅ «Вихри снежные крутя,»;
То в каноническом виде в блоке инициализации вид будет такой (например):
x_1(0)=Const(Буря мглою небо кроет,);
x_1()=Assign(ChrEnter);
x_1()=Const(Вихри снежные крутя,);
Будем считать, что программа не исполняет блок инициализации – это те данные, которые есть изначально, ещё до начала работы программы. Есть изначально так же, как есть сам текст программы.
Блок инициализации лишь декларирует то, какие данные имеются (должны быть) в момент начала работы программы. А сама работа программы (первый шаг) начинается с той строки в программе, которая первой нарушает правила для блока инициализации.
Заметим, что 8-ой пункт описания строк программы в каноническом виде, применяется только в блоке инициализации и поэтому «функция» Const() никак не влияет на время работы программы.
