В первых языках программирования этому предмету не уделялось достаточно большое внимание. Считалось, что компьютеры нужны прежде всего для вычислений, а строкам отводилась скромная роль оформления результата при печати. В языке Fortran первой версии строки выглядели совсем непривычно:
Fortran:
100 FORMAT (11HHELLO WORLD)Странная конструкция 11HHELLO WORLD означает следующее: строковая (первое Н) константа длиной 11 символов с текстом HELLO WORLD.
Таким образом, программисту приходилось каждый раз вручную считать количество символов в строке. Если оно не совпадало с имеющимся, компилятор, пересчитав фактически имеющиеся символы, выдавал ошибку. Естественно было переложить обязанность подсчета символов на компилятор. Первая идея состояла в том, чтобы заключать строковую константу в кавычки:
Pascal
s := 'Hello world';C++
s = "Hello world";При этом естественным образом возникала проблема: как быть, если в строке должна появиться кавычка? Первое решение этого вопроса было не совсем изящным, но работающим
C++
s = "I will say \"Hello, world\"";Обратная косая черта, поставленная перед кавычкой, как бы экранирует ее, превращая в обычный символ. Читается это плохо, приводит к ошибкам, поэтому в некоторых языках ввели два разных символа для ограничения строк.
PHP
$s1 = "I will say 'Hello, world'";
$s2 = 'I will not say "Hello, world"';Так уже лучше, но что, если в строке должны встретиться и одинарные и двойные кавычки? Решение, предложенное в языке Python — использование тройных кавычек:
Python
s = """I'll say "Hello, world" """Все, вроде бы, хорошо, но обратите внимание на пробел в конце строки. Если его не будет, компилятор выдаст ошибку, потому что увидит четыре кавычки подряд. И, все-таки, что, если в строке должны появиться три кавычки подряд? Решение называется heredoc, оно появилось впервые в языке командной оболочки Unix, после было перенесено в язык Perl и другие языки. Выглядит оно так:
Perl
$s = <<END;
I will say anything ' '' """, ", ""
Yes, anything at all.
Except for
ENDИдея состоит в том, что в первой строке между << и ; записывается произвольная строка (в данном случае это END), которая не должна встречаться в том тексте, который нам нужно поместить в строковую константу, конец которой определяется этим же сочетанием символов. айти строку, которой нет внутри нашей константы всегда возможно. В языке Lua это делается несколько изящнее:
Lua
s = [===[Any text]===]Ограничивающие строку конструкции формируются из двойных квадратных скобок и знаков = между ними в
произвольном количестве (в том числе и нулевом). Такой код читается легче, чем обычный heredoc.
Раз уж мы научились формировать строковые константы, давайте посмотрим, что можно со строками делать. Первая операция называется конкатенация, или сцепление строк, и встречается почти во всех языках, где есть строки. В Javascript, например, она обозначается, как и сложение, знаком +
Javascript:
a = 'Hello';
b = a + ' world';В некоторых языках для сцепления строк используется специально выделенный знак операции. В PHP это точка, в Lua две точки подряд (a..b). У каждого из способов есть определенные преимущества и недостатки. Если это знак +, то, с одной стороны, программисту не нужно запоминать еще один знак операции (о котором, в отличие от математических символов, договориться не удалось), а с другой, если в выражении смешиваются числовые и символьные данные, результат может быть не тот, который ожидается.
Javascript:
a = 'Number';
b = 3;
c = a + b; // Number3
d = b + a; // 3Number
e = a + 3 + b; // Number33
f = 3 + b + a; // 6NumberПоведение программы в случае использования специального оператора сцепления строк более предсказуемо, даже если аргументами являются числа, этот оператор предполагает, что они будут представлены в виде строк или будет выдана ошибка.
Это, кстати, еще две операции со строками — представление числа в виде строки и превращение
строки в число. Разница между этими операциями в том, что если первая возможна всегда, то при
выполнении второй могут возникнуть ошибки, которые придется как-то обрабатывать.
Самый простой и одновременно неудобный способ используется в языке C. Функция atoi возвращает
число, соответствующее переданной строке, но если интерпретировать строку как число не удалось,
поведение ее не определено. Обычно функция возвращает 0. Таким образом, отличить ошибку от
строки "0" невозможно.
Сортировка по алфавиту является одной из типовых задач, так что операции «равно», «меньше» и «больше» для строк были бы полезны. Другое дело, что две последние операции в случае текстов на естественных языках представляют собой сложную и иногда неразрешимую задачу, поскольку в разных языках одни и те же буквы (их числовые представления) могут находиться на разных местах в алфавите.
Точное сравнение в смысле совпадения битовых представлений строк намного проще, если, конечно, для представления символов не используется Unicode.
Кроме полного сравнения строк есть еще так называемые регулярные выражения, или сравнения строки с образцом, тоже заданным в виде строки специального вида. И в некоторых языках регулярные выражения встроены в синтаксис.
$x = 'a';
if ($x =~ m/[abc]/){
print "yes"
}Регулярное выражение /[abc]/ сопоставляется со строкой, состоящей из одного символа, который может быть 'a', 'b' или 'c'. Для того, чтобы задать это выражение в программе, используются специальные ограничители / / вместо кавычек.
В целом к строкам в языке есть три различных подхода. Первый применяется, например, в языке C, где
строки это просто массивы символов. Второй состоит в создании специального типа данных, как это
сделано в языках Pascal и Java. Третий способ используется в языках с развитыми объектно-ориентированными
возможностями. В языке C++ строка string это с точки зрения языка обычный объект со всей
необходимой функциональностью. При этом ничто не мешает создать свой собственный класс объектов,
которые будут обеспечивать тот же (или другой) набор операций.
На нижнем уровне используется два основных способа представления строк. Это "строка со счетчиком" и "строка с нулем на конце". В первом случае выделяется память под символы строки и дополнительно под целое число, в котором хранится количество символов. Это число находится в памяти непосредственно перед символами строки, так что имея адрес этой структуры, можно сразу же получить длину строки.
Во втором случае символ со значением 0 используется для обозначения конца строки. Оба способа имеют свои недостатки. В случае строки со счетчиком необходимо при разработке языка или компилятора принять решение о том, какой максимальной длины может быть строка. В случае строки с финальным нулем проблемы возникают уже при выполнении программы. Дело в том, что определить длину строки можно только просмотрев ее всю и найдя тот самый конечный 0. При этом алгоритм операции сцепления строк состоит в выяснении длины строк-операндов, выделении памяти под результат и копирования строк в эту память.
Из-за того, что выделение памяти это обычно довольно долгая процедура, в некоторых стандартных библиотеках языков программирования делают специальную конструкцию для быстрого сцепления множества строк.
StringBuilder b = new StringBuilder();
for (int i = 0; i < 10000; ++i){
b.Append("something"); // добавляем много строк
}
string s = b.ToString();Объект StringBuilder не сцепляет строки и не выделяет память при добавлении новых строк. Он просто запоминает указатели на эти строки и суммирует их длины. Только при вызове ToString происходит фактическое создание строки-результата.
Строки - наиболее универсальный тип данных. Поскольку в большинстве языков программирования программа это строка символов, то все, с чем умеет работать язык программирования, представимо в виде строки символов. Неудивительно, что во многих языках программирования строки - основной, а иногда и единственный тип данных. Пионером тут выступил в 1962 году язык Snobol (StriNg Oriented and symBOlic Language), в котором исходно был всего один тип данных. Впоследствии, в версии Snobol4 добавили и другие. Сам по себе язык Snobol особой популярностью не пользовался, в основном из-за очень непривычного синтаксиса, но оказал влияние как на регулярные выражения, так и на логические языки. Последнее может показаться странным, но алгоритм сравнения строки с образцом в языке Snobol в основном совпадает с алгоритмом логического вывода в языке Prolog.
Универсальность строк как способа представления данных также используется при организации взаимодействия
между программами и в различных системах ввода-вывода и хранения данных. Если заранее неизвестно, на какой
машине будут записываться или считываться данные, и по каким-то причинам возможна несовместимость
между представлением данных на разных машинах, можно попробовать представить данные в виде строк.
Здесь тоже возможны проблемы, например, из-за того, что в зависимости от системных настроек число
"сто тысяч и две десятых" может быть представлено как 100000.2, как 100,000.2 или как 100000,2.
Обычно ввод-вывод — наименее удовлетворительная часть языка. возможно, потому,
что здесь разработчик не может полностью игнорировать реальный мир.
Д.Баррон
Идеология ввода-вывода, как и идеология языка программирования, может определяться железом или моделью системы ввода-вывода. С некоторых пор большинство операционных систем используют примерно одинаковые модели воода-вывода, а именно производные от той модели, которая когда-то сложилась в системе UNIX. В этой модели есть два основных вида "объектов внешнего мира" - файлы и потоковые устройства. Однако, в более древних операционных системах ввод-вывод был устроен иначе, например, система могла выделять пользователю фиксированный участок жесткого диска с адресами, заданными в виде чисел. На этом участке программист должен был организовываать свои файлы.
В ранних языках программирования ввод-вывод пытались оформить в виде операторов языка, однако, скоро стало ясно, что возможности операционных систем меняются, и существующие возможности ввода-вывода перестают им соответствовать.
Современный подход к системе ввода-вывода языка состоит в том, чтобы не делать ее вообще, а возложить эти функции на какую-то библиотеку. Некоторая ирония, возможно, есть в том, что возможности ввода-вывода у современных ОС примерно одинаковые.
Тем не менее, функции ввода-вывода обычно входят в описание стандарта языка.
Форматный или строковый вывод составляет большую часть всего ввода-вывода. Идея состоит в том, чтобы преобразовать любое выводимое значение в строку, которая потом выводится на экран или записывается в файл.
Наибольшее разнообразие подходов тут обнаруживается в деле преобразования
чисел в строки. Для этого обычно применяется строковое же заклинание под
названием "спецификация формата". Она может быть выражена количеством знаков,
отводимых под целую и дробную части вещественного числа, например,
F10.2 (FORTRAN) или %10.2f (C). Это также может быть шаблон,
#####.## как в языке Basic. C-шный способ форматирования чисел получил
широкое распространение и используется, например, в языке Python
print("%10.3f"% (123.456))
напечатает " 123.456" - строку длиной 10 символов, из которых 3 будут отведены на дробную часть числа. Все эти форматы были придуманы много лет назад в языке Fortran и в основном рассчитаны на то, чтобы красиво вывести числа в колонки одинаковой ширины на бумагу или экран. При этом использовались принтеры или терминалы, у которых все буквы были тоже одинаковой ширины. В наше время такие устройства используются очень редко. Как правило, нужно форматировать текст в соответствии с используемым шрифтом, а эта функциональность зависит от операционной системы, экрана и много чего еще. Ее невозможно уместить в одну функцию и одну спецификацию формата для каждого числа.
Двоичный вывод это запись в файл данных в том виде, в котором они хранятся в памяти. Результат такого вывода зависит от представления чисел в машине и данные, записанные таким образом, могут быть не переносимы на другую машину. Дело в том, что в разных процессорах целые числа, занимающие больше одного байта, могут храниться в памяти по-разному. Различают два основных способа записи таких чисел: big-endian и little-endian.
Предположим, у нас есть число 22222, и оно занимет два байта памяти. 22222 = 86*256+206, так что в одном байте будет храниться число 86, а в другом число 206. В памяти эти числа будут располагаться по соседним адресам: в случае big-endian сначала 206, потом 86, а в случае little-endian сначала 86, потом 206. Если мы запишем число 22222 на машине с одним порядком байт, а прочитаем на машине с другим порядком, то получим 52822.
Двоичный вывод обычно используется для хранения временных или локальных данных, а также в случае необходимости обеспечить совместимость с каким-то оборудованием, например, принтером.
Кроме простой возможности записывать байты в файл, многие системные библиотеки языков программирования предоставляют возможность так называемой сериализации, или систематического, связанного с языком и реализацией, способа записать на диск данные с возможностью их последующего восстановления.
Эта возможность восстановить объекты языка такими, какими они были перед записью - как раз то, что не гарантирует простая двоичная запись. Объект может содержать в своем составе адреса памяти, служебные данные и что-то еще, что может изменяться при каждом запуске программы. Фактически, из двоичной записи можно непосредственно востанавливать только очень простые данные: числа, массивы чисел и структуры, в которых есть те же числа, массивы и структуры. Сериализация гарантирует, что более сложные сущности, такие как списки, последовательности или словари, тоже будут корректно восстановлены из записи.
Сериализация - процесс, непрозрачный для программиста, последовательность байт, записанная на диск, может изменяться при изменении версий языка или в зависимости от особенностей машины, на которой она производится. Единственная базовая возможность сериализации это сохранение данных в файле и восстановление данных той же программой. В конкретных реализациях в библиотеках разных языков программирования возможны какие-то дополнительные удобства вроде гарантии восстановления данных независимо от версии или особенностей машины.
Язык XML, не являющийся языком программирования, представляет собой противоположность сериализации, хотя сериализация в XML тоже бывает. Основная идея XML - создать обобщенный формат хранения любых данных, причем запись этих данных должна быть понятна для человека. Пример:
<letter>
<to>Alex</to>
<from>Justas</from>
<heading>Bug in your code</heading>
<body>Please fix it.</body>
</letter>Смысл этой записи более или менее понятен, даже если не знать, какая программа должна работать с
такими данными. Объект letter содержит в своем составе поля to, from, header и body.
На практике чаще используют другую возможность XML - атрибуты.
<letter to="Alex" from="Justas" heading = "Bug in your code">
Please fix it.
</letter>Сам по себе стандарт XML накладывает очень мало ограничений на данные и совсем никак не регулирует способы представления объектов языков программирования. "Правильный" XML должен начинаться со специальной строки вида
<?xml version="1.0" encoding="UTF-8"?>и остальная часть файла должна содержать ровно один раздел верхнего уровня:
Нельзя
<?xml version="1.0" encoding="UTF-8"?>
<letter> ... </letter>
<letter> ... </letter>
<letter> ... </letter>
<letter> ... </letter>Можно
<?xml version="1.0" encoding="UTF-8"?>
<letters>
<letter> ... </letter>
<letter> ... </letter>
<letter> ... </letter>
<letter> ... </letter>
</letters> Остается один вопрос: а что вообще может быть внутри letter? Какие поля там обязательны,
какие можно пропустить, а каких там не должно быть вообще. Для решения этой задачи применяются
две основные технологии, которые называются DTD и XML Schema. Это тоже такие языки (XML Schema
построена на основе XML), с помощью которых можно описать структуру файла XML.
Главные достоинства XML состоят в том, что он относительно легко может быть понят человеком, а также что для него написано великое множество разнообразных программ и библиотек. Кроме того, это стандарт, поддерживаемый организацией W3C, и любую программу можно проверить на соответствие этому стандарту.
В отличие от XML, формат под названием JSON скорее является стандартом de facto, то есть большинство
реализаций этого формата вам (почти) ничего не гарантируют. Возникновение этого формата связано
с особенностью языка Javascript, в системной библиотеке которого есть функция eval, вычисляющая
значение своего аргумента, заданного в виде программы на Javascript. JSON в базовом варианте это просто запись
данных на языке Javascript:
[
{
from:"Alex",
to:"Justas",
heading:"Bug report"
},
{
from:"Justas",
to:"Alex",
heading:"Re:Bug report"
}
]В JSON есть числа, строки, массивы и объекты, и в Javascript для чтения JSON требуется ровно одна строка кода:
eval('v='+json);Недостаток такого, слишком прямолинейного, подхода в том, что вместо данных в строке может быть вообще что угодно, в том числе и вредоносный код. Поэтому в реализации Javascript были добавлены функции для работы с JSON, которые хоть что-то проверяют. Это также привело к введению некоторых ограничений на формат, например, приведенный выше JSON такими функциями прочитан не будет, им надо, чтобы имена полей также были заключены в кавычки:
[
{
"from":"Alex",
"to":"Justas",
"heading":"Bug report"
},
{
"from":"Justas",
"to":"Alex",
"heading":"Re:Bug report"
}
]JSON - более компактный формат, чем XML, в нем есть типы данных, и нет той неоднозначности, которая изначально была заложена в XML. Библиотеки для работы с JSON написаны почти для всех современных языков программирования.
Базы данных дают возможность хранить большие объемы данных при сохранении независимости от системы. Для этого все операции по записи и чтению данных выносятся в отдельный процесс, а между ним и программой вводится промежуточный язык, называемый языком запросов, на котором происходит общение между программой и базой данных. Программа формирует запрос на таком языке и отправляет его программе - серверу базы данных, сервер обрабатывает запрос и возвращает результат.
В этом подходе имеется очень много достоинств. Сервер базы данных можно вынести на отдельный компьютер и тем повысить производительность. Сервер обычно умеет обслуживать сразу много программ - клиентов. Типичный сценарий работы в такой архитектуре состоит в том, что программы-клиенты часто запрашивают примерно одни и те же данные, и сервер может держать эти данные в оперативной памяти, ускоряя обслуживание.
Но есть и недостатки. Главный из них - наличие специального языка, на котором программа общается с сервером. Проблема тут не в том, что программист должен знать уже минимум два языка, и даже не в том, что ему приходится писать на двух языках одновременно, а в том, что предложения на языке запросов должны автоматически генерироваться программой. Например, мы хотим узнать число сотрудников с зарплатой более 100000 денежных единиц. Для этого мы пишем следующий запрос:
select count(*) from employee where salary > 100000Теперь попробуем сформулировать более общий вопрос: найти число сотрудников с зарплатой более N денежных единиц. Для этого нам придется сконструировать запрос в нашей программе:
n = 100100
s = "select count(*) from employee where salary > " + str(n)О наличии ошибки в сгенерированной строке запрса мы узнаем, только отправив запрос на сервер, или, возможно, не узнаем никогда. Если, например, вместо числа 100100 в переменную n каким-то образом попадет строка
"0; drop table employee;"
то при неправильной организации базы данных все данные о сотрудниках будут уничтожены. Этот подход называется SQL injection, и является одним из основных инструментов хакеров. Сложности с созданием запросов и опасности для инфраструктуры привели к тому, что в большинстве библиотек для работы с базами данных используются специальные средства для "правильного" создания запросов. При этом проверяется все, что возможно, но SQL injection искоренить не удалось.
Другой способ организации баз данных называется No SQL, и он предполагает написание запросов на том же языке,
на котором пишется основная программа.
db.employee.find(
{"salary": {"$gt": 100000}}
)Здесь, как можно видеть, тоже есть некий своеобразный язык запросов. Он полностью интегрирован в Python, это хорошо с точки зрения надежности кода, но плохо потому, что на другом языке программирования это же запрос может выглядеть не совсем узнаваемо. Вот тот же запрос на Java:
findIterable = collection.find(gt("salary", 100000));У баз данных, построенных по принципу No SQL есть еще много разных достоинств и недостатков, но они не имеют
отношения к языкам программирования.
При вычислении выражений основной аварийными ситуациями могут быть деление на 0, извлечение корня из отрицательного числа и подобные проблемы. Их не так много, и их всегда можно предусмотреть, проверяя аргументы функций. Но в случае ввода-вывода аварийные ситуации бывают намного более сложными. Предположим, программа пытается прочитать файл на диске. При этом нужно рассматривать следующие возможности: файл отсутствует, диск поврежден и файл не читается, у программы нет прав доступа к файлу, файл занят другим процессом, достигнут конец файла, итд. Реакция программы на такие ошибки должна быть различной.
Заранее проверить все возможности было бы слишком сложно. Кроме того, при взаимодействии с окружающим миром ситуация может меняться, и проверка сделанная сейчас может быть недействительна уже через секунду. Ошибки ввода вывода (как и любые ошибки программы) надо обрабатывать. Для этого придумали несколько основных методов.
`err = fread(b,size,n,F);`
в случае ошибки или конца файла функция чтения возвращает 0. Получив такой ответ, можно вызвать функцию (ferror) чтобы узнать точнее о том, какая ошибка произошла.
В некоторых языках (стандартных библиотеках) есть специальная переменная или функция, значение которой нужно проверять после каждой операции.
Недостатки такого способа очевидны: программа превращается в набор if-ов, проверяющих
всевозможные варианты ошибок.
if файл открылся:
if данные прочитаны:
...
закрыть файл
else:
# что делать, если файл открыт, а данные не читаются
закрыть файл
else:
# файл не открылся
В той части программы, где все идет хорошо, логика обычно бывает простая, но исследование вопроса о том, что надо делать в случае ошибки, во-первых, сложно, во-вторых зависит от того состояния, в которое программа пришла, сделав безуспешную попытку открыть файл.
Уже в языке Fortran его создатели подумали о необходимости обрабатывать ошибки ввода-вывода. Для этого они, наряду с проверкой значения, использовали вариацию на тему GOTO.
Оператор
READ(5,100,END=30,ERR=40)
пробует читать данные, и производит безусловный переход (GOTO) на метку 30 в случае, если произошла попытка читать данные за концом файла и на метку 40, если произошла какая-то еще ошибка.
Подобный подход был использован в языке Basic, но не во всех его диалектах можно было указывать тип ошибки. Обычно предлагалось писать что-то вроде
ON ERROR GOTO 230
После выполнения такой строки возникновение любой исключительной ситуации приводило к передаче управления на строку 230, а там уже надо было разбираться, что именно произошло. Отдельный вопрос, касающийся такого способа обработки ошибок, состоит в том, что должна делать программа, если после перехода вследствие ошибки произойдет еще одна программная ошибка.
Этот способ похож на предыдущий, только вместо GOTO происходит вызов подпрограммы. Это решение лучше
в том смысле, что происходит локализация обработки ошибок, одна и та же подпрограмма может обрабатывать
ошибки, возникающие в разных местах основной программы, и возможна более детальная раскладка ошибок
по обработчикам. Например, в библиотеке jQuery, написанной на Javascript, можно задать обработчики
для успешного и для неуспешного выполнения запроса:
$.ajax({
url: "test.html",
success: function1,
error: function2
});Функция function2 будет вызвана при возникновении любой ошибки. Однако, можно сделать индивидуальные обработчики для различных ошибочных ситуаций:
$.ajax({
url: "test.html",
success: function1,
statusCode: {
404: function3,
500: function4
}
});Эта функция должна определить, можно ли выполнить операцию безопасно. В некоторых API есть возможность проверить, не возникнет ли ошибка при выполнении какой-либо операции.
if (can_write(f,s))
write(f,s);
else
// обрабатываем ошибкуПреимущество такого способа обработки ошибок в том, что, во-первых, код обработки ошибки упрощается, и во-вторых, при отрицательном ответе от проверяющей функции вся система находится (по крайней мере должна находиться) в предсказуемом состоянии, а именно в том, в каком она находилась до проверки. Это следует из общей идеи об отсутствии побочных эффектов у функций. Однако, иногда создатели операционных систем экономят на количестве вызовов и делают одну и ту же процедуру для проверки и для самой операции.
Все эти методы обладают одним общим основным недостатком: они сигнализируют о том, что что-то не так, но не предполагают никаких методик написания программы, которая может работать в условиях возникновения ошибок. Если в результате ошибки ввода-вывода произошел переход к какому-то месту программы, то что должен делать программист? Допустим, все это происходит внутри какой-то функции. Тогда можно, например, вернуть код ошибки. То есть превратить первый способ во второй.
Хорошо бы обработку ошибок сделать более предсказуемым действием. Для этого придуман
try
{
read(...);
}
catch(Exception e)
{
// что делаем в случае ошибки
}или
file = open(...);
try
{
read(file,...);
}
finally
{
close(file);
}В случае возникновения ошибки при выполнении read в первом фрагменте управление будет передано ветке
catch, во втором фрагменте - ветке finally. Часть finally будет выполнена как в случае ошибки,
так и в случае нормального завершения операций.
У этого способа есть множество преимуществ. Во-первых, логика обработки ошибок всегда одна и та же. Во-вторых, начиная обрабатывать ошибку, программист уже имеет о ней дополнительную информацию, и в некоторых языках можно для каждой из возможных ошибок писать свой catch. И в третьих, легко передать информацию об ошибке на верхний уровень.
Представим себе типичную ситуацию: программа читает файл с какими-то сложными структурированными данными. При этом есть какая-то процедура нижнего уровня, которая просто читает байты, что-то с ними делает и передает прочитанное вызвавшей ее процедуре. У процедуры нижнего уровня нет никакой информации о том, что именно программа делает в данный момент и она не может принять решение о том, можно ли проигнорировать неправильно прочитанные данные, или можно ли их исправить или надо сообщить об ошибке пользователю.
Технология обработки исключений состоит в том, что если исключительная ситуация не обработана при помощи try-catch или try-finally на каком-то уровне вложенности вызовов процедур, то выполнение прекращается и исключение передается на более высокий уровень.
В языке Java разработчики пошли еще дальше и обязывают программиста описать в явном виде, собирается он обрабатывать ошибку или передавать ее дальше.
public int myDivide(int a,int b) throws ArithmeticException
{
return a/b; // возможно возникновение ошибки
}
public int callMyDivide1(){ // ошибка компиляции
system.out(myDivide(2,0));
}
public int callMyDivide2 throws ArithmeticException() { // так можно, передаем исключение выше
system.out(myDivide(2,0));
}
public int callMyDivide1(){ // так тоже можно, обрабатываем ошибку сами
try{
System.out.println(myDivide(2,0));
}
catch (ArithmeticException e) {
System.out.println("ошибка вышла");
}
}Недостаток такого подхода в том, что обработка исключительных ситуаций делегируется вызывающей программе, которая в общем случае может и не знать о проблемах, локальных для вызываемой процедуры. Например, в рассмотренном случае процедуры высокого уровня, читающей структурированные данные и процедуры нижнего уровня, читающей байты, последняя может столкнуться с проблемами самого разного вида, например, со сбоем на диске, и если информация об исключительной ситуации передается наверх, процедура высокого уровня должна уметь обрабатывать все множество низкоуровневых ошибок. Для этого случая предусматривается оператор throw, который позволяет повторить обработку исключения на верхнем уровне. Например:
try
{
read_bytes(...);
}
catch(Exception e)
{
if(...) // мы можем обработать исключение здесь
process_exception(); // обработать его
else
throw(e);
}Оператор throw можно также использовать для создания собственных типов исключительных ситуаций. Обычно в языке
либо предусматривают объектный тип Exception, который можно расширять путем наследования, либо, как это сделано
в C++, допускают throw с любым типом аргумента.
Если язык программирования, на котором пишется такая обработка ошибок, относится к R-типу, можно просто возвращать из функции, осуществляющей ввод-вывод, какое-то нужное значение, в случае успеха и значение другого типа в случае ошибки. Например:
function myDivide(a, b)
{
if(b == 0)
return "Ошибка: деление на 0";
else
return a/b;
}
$a = myDivide(3,0);
if(is_string($a))
print($a);
// или просто
print( myDivide(4,0));Для удобства и единообразия можно сделать объектную "обертку" для возвращаемого значения и даже организовать автоматическое преобразование этой обертки к нужному типу. Здесь тоже работает принцип "реши проблему сам, если можешь или передай ее на верхний уровень"
Все, начинающие изучать параллельное программирование, думают, что они его понимают.
Потом они сталкиваются с ситуациями, которые, как они полагали, в принципе не могут возникнуть, и в итоге приходят к пониманию
того факта, что они никогда не понимали, с чем имеют дело
Herb Sutter
Как мы уже говорили, некоторые участки программ могут выполняться параллельно. Возможность одновременного выполнения нескольких программ появилась довольно давно, и появилась она в связи с тем, что значительную часть времени обычной вычислительной программы занимает ввод-вывод. Пока результат распечатывается или записывается на диск, процессор может считать что-то еще, а процессорное время стоило дорого. Поэтому были придуманы операционные системы, способные выполнять несколько программ одновременно. После появления компьютеров с несколькими процессорами появилась и другая задача: разделить программу на участки, которые могли бы выполняться одновременно на нескольких процессорах. В ходе решения этих задач было придумано несколько концепций параллельной обработки данных.
Это амый простой, но одновременно неочевидный по синтаксису способ организации параллельных вычислений. Подпрограммы просто передают друг другу управление в определенных точках.
co = coroutine.create(function ()
for i=1,10 do
print("co", i)
coroutine.yield()
end
end)
coroutine.resume(co)Это похоже на генераторы, которые мы уже рассматривали раньше, но с одним отличием: сопрограммы умеют передавать друг другу данные. При этом параллельного выполнения кода нет.
Сопрограммы используются в основном в сценариях последовательной обработки данных - "конвейерах". Представим себе две процедуры, первая из которых читает файл с данными и отбирает некоторые из них, а вторая производит какую-то обработку данных. В зависимости от алгоритмов отбора и обработки взаимодействие между этими процедурами может быть довольно сложным, и не всегда понятно, какая из процедур должна вызывать другую. Сопрограммы решают эту задачу довольно простым способом: "главной" процедуры нет, и процедура чтения передает (yield) полученные данные второй подпрограмме.
Важным свойством сопрограмм является то, что у них не существует проблемы одновременного доступа к каким-то переменным или другим ресурсам; в каждый момент времени выполняется одна какая-то процедура, которая не может быть прервана в произвольный момент времени.
Теперь поговорим о действительно параллельных программах. Первый случай, в котором требуется выполнять какой-то код если не параллельно, то по крайней мере асинхронно, это ввод-вывод. Выполнение программы может продолжаться во время ожидания завершения какой-то операции
PL/1
GET LIST EVENT(Z) A,B,C
...
WAIT(Z)
Команда чтения переменных GET LIST создает некую сущность под названием event, причем выполнение программы продолжается без ожидания завершения ввода-вывода. Дальше програма может делать что-то еще, не связанное с переменными A,B и C, которые должна прочитать команда GET LIST, а потом подождать (WAIT) завершения чтения. Заметим, что единственной связью между GET LIST и WAIT является переменная Z. Здесь уже возникает проблема, связанная с тем, что между GET LIST и WAIT присваивать что-то переменным A,B и C или использовать их значения было бы некорректно. Конечно, хотелось бы, чтобы компилятор мог это отследить и хотя бы предупредить программиста. Однако, наличие в языке условных операторов и GOTO делают эту задачу принципиально невыполнимой.
В современных языках такая фукциональность реализуется при помощи процедур.
jQuery.get( "test.html", function( data ) {
// делаем что-то с данными
});Процедуре jQuery.get передается адрес в сети, по которому надо обратиться, и функция, которую нужно вызвать, когда чтение завершится.
В этом случае функция обработки может выполняться как параллельно с какой-то другой процедурой, так и вызываться подобно сопрограмме. Во втором случае должна быть какая-то очередь выполнения, в которую ставится функции, соответствующие завершившимся действиям ввода-вывода.
В некоторых языках параллельные участки программ можно объявлять в явном виде. Среди современных языков такая возможность есть в Chapel
writeln("2: ### The cobegin statement ###");
cobegin {
writeln("2: output from spawned task 1");
writeln("2: output from spawned task 2");
}Все операторы блока cobegin (в данном случае это вызовы функций) будут выполнены параллельно.
В языках C++ и Fortran возможность параллельного выполнения была введена независимо от спецификации
языка, при помощи указаний компилятору.
int main(int argc, char **argv)
{
int a[100000];
#pragma omp parallel for
for (int i = 0; i < 100000; i++) {
a[i] = 2 * i;
}
return 0;
}Здесь #pragma omp parallel for означает указание компилятору распараллелить выполнение дальнейшего кода.
Это указание относится не к языку C++, а к надстройке под названием OpenMP, которая использует
тот факт, что в большинстве императивных языков применяются одни и те же конструкции (for, while, if), и
параллельное выполнение кода можно организовать одним и тем же набором директив.
Самый простой и слабо зависящий от языка способ распараллелить процессы это запускать их в явном виде с помощью процедуры стандартной библиотеки. Процедура fork в языке C создает копию существующего процесса.
pid_t pID = fork(); // создает копию данного процесса
// выполнение копии и оригинала продолжаются
// с одного и того же места, но результат
// функции fork у них разный.
if (pID == 0) // кто я?
{
// Я - дочерний процесс.
// Делаем что-то полезное
// и завершаем программу
exit(0);
}
else if (pID > 0)
{
// Я - родительский процесс.
// pID — идентификатор дочернего процесса
waitpid(pID); // ждать завершения процесса.
}
else
{
// ошибка
exit(1);
}Процедура fork не имеет отношения к языку C, а является частью интерфейса операционной системы UNIX. Использовать этот интерфейс может программа на любом языке программирования.
В современных операционных системах есть как минимум 2 класса процессов. Первый класс это то, что обычно называют программами, то есть процессы операционной системы. Второй - процессы внутри процесса или потоками выполнения. Отличие между этими классами в том, что процессы ОС изолированы друг от друга (мы на это надеемся), и у каждого такого процесса есть своя область памяти, в которой он работает. В отличие от них, все потоки одного процесса имеют общую область памяти и вследствие этого нужны некоторые особые меры по предотвращению конфликтов.
Запуск потоков в Java производится путем создания класса, производного от специального класса Thread:
public class MyThread extends Thread
{
private int tn; // номер потока
public MyThread(int n) // конструктор
{
System.out.println("Создаем поток "+n);
this.tn = n;
}
@Override
public void run() // то, что должно выполняться параллельно
{
System.out.println("Я поток " + this.tn);
}
}Использовать этот класс можно так:
MyThread t1 = new MyThread(1);
MyThread t2 = new MyThread(2);
MyThread t3 = new MyThread(3);
t1.start();
t2.start();
t3.start();Метод start класса Thread создает параллельный поток выполнения и вызывает в этом потоке
метод run, переопределенный в нашем классе MyThread.
Если несколько потоков одновременно пишут или читают одну и ту же область памяти, то возможна ситуация, когда какой-то поток запишет в эту память одно число, а прочитает другое, потому что другой поток уже успел записать туда что-то свое.
Для решения этой проблемы существует много разных способов, мы рассмотрим один, который называется mutex (от mutual exclusion). Этот способ хорош прежде всего тем, что не связан ни с ООП ни с особенностями языка. Mutex это такой совершенно непрозрачный объект, он не предоставляет никаких данных. Особенности его реализации скрыты от программиста. С этим объектом можно сделать две вещи - захватить и отпустить. При этом система, реализующая многопоточность, гарантирует, что невозможно захватить mutex дважды. Код, использующий mutex, выглядит примерно так:
mutex m;
m.lock();
// делаем что нам надо с общей памятью, другие такие же
// функции будут ждать, пока mutex не освободится.
m.unlock();Недостаток mutex в том, что он не гарантирует недоступность общей памяти для всех возможных потоков выполнения, он вообще никак не взаимодействует с общей памятью и "не знает" о ней. Поэтому если какой-то поток не содержит вызова m.lock(), то он может вызвать ту самую проблему, для решения которой используется mutex.
Другая проблема состоит в том, что если mutex занят, то вызов lock() приведет к блокированию потока выполнения до тех пор, пока mutex не освободится. Например, такая программа может выполниться, а может и зависнуть:
mutex m;
cout << "ready" << endl;
m.lock();
cout << "set" << endl;
m.lock();
cout << "go" << endl;
m.unlock();
m.unlock();Для таких ситуаций предусматривается вызов try_lock, который пытается захватить mutex и возвращает true в случае если это удалось сделать.
В языке Python используются те же самые mutex-ы, но с другими именами методов:
mutex = Lock()
mutex.acquire();
# ....
mutex.release();В функциональных языках программирования общая память потоков может отсутствовать, поэтому параллельное выполнение потоков выглядит намного проще. Например, в языке Alice можно написать:
val n = spawn factorial 35
и функция factorial выполнится параллельно с основным потоком выполнения. Завершения ее вычисления
можно в явном виде подождать, написав
await (spawn factorial 30)
(В этом языке программирования скобки для параметров функций писать не нужно, они используются лишь для задания
порядка вычислений. Без скобок запись await spawn factorial 30 означала бы вызов await с параметрами spawn, factorial и 30)
Компиляция это процесс, который обычно делят на две фазы: лексический анализ и синтаксический анализ. Если в нашем языке программирования есть ключевые слова, то не имеет смысла исследовать, из каких символов они состоят. Но можно пойти еще немного дальше. Посмотрим на оператор
a = b + 2;
Когда мы проверяем правильность синтаксиса, нам не очень важно, как именно поименованы переменные и какое конкретно число прибавляется к b (лишь бы оно было правильно написано). Поэтому вполне разумно провести предварительный этап, на котором удалить комментарии и выделить те элементы, смысл которых понятен. Это обычно числа, ключевые слова, операторы. После лексического анализа наш опреатор примет примерно такой вид:
<идентификатор> = <идентификатор> + <число>
В угловых скобках здесь записаны некие категории языка, а одиночные символы оставлены "как есть". Следующая стадия анализа программы - синтаксический анализ - состоит в том, что компилятор делает более глобальные обобщения на основе каких-то правил. Например, рассматриваемый нами оператор компилятор сначала сведет к виду
<идентификатор> = <выражение>
А потом отнесет к категории операторов присваивания. Одновременно строится так называемое дерево разбора, или AST (abstract syntax tree), которое отражает структуру программы. Например, фрагмент программы
a = 0;
while (a < 5){
if(a == 3) print("3");
a = a + 1;
}будет представлен примерно так:
программа
оператор присваивания
переменная(a)
выражение
число(0)
оператор цикла
условие
выражение
знак операции(<)
выражение
переменная(a)
выражение
число(5)
тело_цикла
оператор if
условие
выражение
знак операции(==)
выражение
переменная(a)
выражение
число(3)
часть then
вызов функции (print)
аргументы
строка("3")
оператор присваивания
переменная(a)
выражение
знак операции("+")
выражение
переменная("a")
выражение
число(1)
Читать это следует примерно так: программа состоит из оператора присваивания и оператора цикла. Оператор присваивания состоит из... и так далее.
По такому описанию уже не так сложно сгенерировать код. Для этого используется процесс, обычно состоящий из нескольких стадий, в том числе это могут быть оптимизация, генерация промежуточного кода, оптимизация промежуточного кода, генерация кода для конкретного процессора, итп.
Форма Бэкуса - Наура придумана для описания языка Algol в 1958 году. Она состоит из правил, которые в свою очередь состоят из следующих элементов:
- классы или нетерминальные символы. Это любые слова или наборы слов, заключенные в угловые скобки.
- символы языка или терминальные символы. Это слова языка, заключенные в кавычки (иногда кавычки опускают)
- операция ::= (читается "определяется как"), слева стоит нетерминальный символ, справа выражение
- операция выбора | - описывает возможность выбора одного из вариантов
- квадратные скобки [] - заключенное в них выражение может отсутствовать.
- в конце правила ставится точка.
Например, возможно такое определение:
<арифметическая операция> ::= "+" | "-" | "*" | "/".
вот описание оператора if языка Pascal:
<условный оператор if> ::= "IF" <булево выражение> "THEN" <оператор> [ "ELSE" <оператор>]. <булево выражение> ::= "NOT" <булево выражение> | "(" <булево выражение> ")" | <булево выражение> <логическая операция> <булево выражение> | <выражение> <операция сравнения> <выражение>. <логическая операция> ::= "OR" | "AND". <выражение> ::= "(" <выражение> ")" | <переменная> | <строка> | <число>. <операция сравнения> ::= "=" | "<" | ">".
Надо заметить, что БНФ языка могут соответствовать неправильные программы, например, фрагмент
IF 3 < 'klm' and 2 > 'abc' THENсоответствует приведенному тут описанию оператора IF. Также мы ничего не сказали про то, что такое <строка> и <число>. Можно привести формальные определения в рамках БНФ, например
<число> ::= <цифра> | <цифра> <число>. <цифра> ::= "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|"0". <строка> ::= "'" [<последовательность символов>] "'". <последовательность символов> ::= <символ> | <символ> <последовательность символов>
Как видно, определения могут быть рекурсивными. Однако, для формального определения нетерминала <символ> нам понадобится перечислить все возможные символы, которые могут появиться в строке.
При описании синтаксиса языков программирования часто используются следующие конструкции: одно или более повторений элемента и ноль или более повторений элемента. Например, аргументы функции это ноль или более описаний аргументов:
<описание функции> ::= <идентификатор> '(' <список аргументов> ')'. <список аргументов> ::= [<идентификатор>] | <идентификатор> <список аргументов>.
Эти конструкции часто включают в форму БНФ как расширения.
Первым языком, синтаксис которого был описан при помощи БНФ, был Algol. Возникает естественный вопрос: любой ли язык можно описать таким образом? Для ответа на этот вопрос была разработана теория формальных грамматик и классификация грамматик.
Формальная грамматика состоит из множества терминальных символов (слов языка), множества нетерминальных символов ("понятий"), и набора правил вида
левая часть -> правая часть
где левая и правая части состоят из каких-то терминальных и нетерминальных символов. Терминальные символы мы будем обозначать строчными буквами, а нетерминальные - заглавными. Также один из нетерминальных символов объявляется начальным, обозначим его S.
Синтез текста происходит путем замены левой части на правую, а анализ текста состоит в подборе подходящих правых частей и поиске пути, по которому мог бы происходить синтез данного текста. Синтез заканчивается, когда в тексте не остается нетерминальных символов, а анализ - либо когда по цепочке правил удалось дойти до начального символа, либо когда удалось доказать, что данный текст при помощи данного набора правил сгенерировать невозможно.
Обычно это демонстрируют на специальных примерах. Рассмотрим грамматику:
S -> L L -> E L -> EcL E -> a E -> b
Возможно ли при помощи этого набора правил произвести строку asdf? Конечно, нет, в грамматике
нет терминальных символов s,d и f. А строку acbca? Попробуем:
S -> L -> EcL -> acL -> acEcL -> acbcL -> acbcE -> acbca
Получилось. А можно ли вывести строку acbcaс? Нет, нельзя, но доказательство этого будет чуть
более сложным, чем для строки asdf. Заметим, что получившаяся у нас грамматика похожа на описание
каких-то элементов, разделенных запятыми, в качестве которых здесь выступает терминальный символ c.
Для более сложных грамматик анализ текста производится автоматически, специальными программами, которые, в свою очередь, тоже создаются автоматически из описаний грамматик.
Формальные грамматики можно разделить на четыре типа. Для отнесения грамматики к тому и ли иному типу необходимо соответствие всех её правил некоторым схемам.
Тип 0 — неограниченные
Непустая последовательность символов любого вида преобразуется в другую последовательность символов без каки-либо ограничений. Практического применения в силу своей сложности такие грамматики не имеют.
Тип 1 — контекстно-зависимые
Это грамматики, у которых в левой части всех правил есть хотя бы один нетерминальный символ. Приведем пример
контекстно-зависимой грамматики, описывающей язык, все тексты которого состоят из нескольких символов a, за
которыми следуют столько же b и потом столько же символов c. Примеры текстов: aabbcc, abc, aaabbbccc, и тд.
S -> A A -> aABC A -> aBC CB -> BC aB -> ab bB -> bb bC -> bc cC -> cc
Рассмотрим вывод первой из строк, приведенных в качестве примера:
S -> A -> aABC -> aaBCBC -> aaBBCC -> aabBcc -> aabbCC -> aabbcC -> aabbcc
Тип 2 — контекстно-свободные
Это грамматики, у которых левые части всех правил состоят из какого-нибудь нетерминального символа. Такие грамматики находят самое широкое применение в языках программирования ввиду того, что они простые, легко поддаются анализу и для них созданы различные средства автоматической генерации синтаксических анализаторов.
Однако, не все языки можно описать при помощи грамматик типа 2. Например, язык, который мы описали выше при
помощи грамматики типа 1, описать грамматикой типа 2 не получится. Это не самая большая проблема при создании
компиляторов, потому что, если бы нам, например, действительно зачем-то понадобился язык со строками из одинакового
количества символов a b и c, мы могли бы описать более простой язык, в текстах которого могут быть
произвольные ненулевые количества a b и c (например, aabbbbc была бы текстом такого языка), а потом
просто посчитать количества символов a b и c, и в случае их несовпадения выдать сообщение об ошибке.
Среди грамматик типа 2 есть несколько подклассов, среди которых наиболее важными для построения компиляторов являются LL(k) и LR(k).
Грамматика LL(k) это такая грамматика, в которой решение о том, какое именно правило верхнего уровня должно быть применено
для дальнейшего вывода, всегда может быть принято после просмотра не более чем k следующих терминальных
символов. Например, в языке Pascal, последовательно читая программу, мы видим один из нескольких терминальных
символов: var означает, что дальше будет описание переменной, procedure означает, что дальше будет процедура,
type означает, что дальше будет описание типа, и т.д. Число, ключевое слово for и многое другое не могут
появиться там, где мы ожидаем увидеть слова procedure или var. Pascal - типичный язык, который можно описать
грамматикой LL(1). Разбор программы происходит по принципу сверху вниз, поскольку на основании просмотренного символа
можно из всей грамматики выделить набор правил, применимых в данной ситуации.
Алгоритм разбора LR(k) на основании просмотра не более чем k следующих терминальных символов может принять решение о том, какое именно правило нижнего уровня здесь подходит. Например, в языке C при разборе строки
static int x()
мы не знаем, о чем вообще идет речь, до тех пор, пока не увидим открывающую скобку. До тех пор это может быть описание переменной, а может быть и описание функции. Но после того, как появилась скобка, мы знаем, что это функция, и можем однозначно применить соответствующее правило.
Подкласс грамматик, которые могут быть разобраны при помощи алгоритма LR(k) включает в себя все грамматики LL(1), но сам этот алгоритм работает немного медленнее, чем алгоритм разбора LL(k).
Большинство программ для автоматической генерации синтаксических аналозаторов (yacc, antlr и др.) используют один из этих
алгоритмов.
Тип 3 — регулярные
Эти грамматики делятся на два эквивалентных класса, у которых все правила имеют вид:
- A -> Bc
- A -> cB
где с - терминальный символ, а A и B - нетерминальные. Языки с грамматиками типа 3 могут быть интерпретированы с помощью регулярных выражений. Отсюда следует ответ на часто незадаваемый вопрос о том, можно ли проанализировать HTML (а также C или Python) при помощи регулярных выражений. Поначалу многим кажется, что это вполне возможно, учитывая мощь аппарата регулярных выражений, но теория говорит об обратном.
Зная теорию формальных грамматик, вы, например, никогда не сделаете такой ошибки: часто в программах требуются конфигурационные
файлы. Часто для этих файлов придумывают свой собственный формат. И, глядя на сложные конфиги таких программ как Apache или
Nginx, люди придумывают слишком сложный формат, который в общем случае не поддается интерпретации с помощью регулярных выражений.