dmitgu

Category:

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() никак не влияет на время работы программы.    

Error

default userpic

Your reply will be screened

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.