Данный текст является предварительной версией книги, предназначенной для чтения специалистами и распространяется по лицензии (CC BY-NC-ND 4.0)
https://creativecommons.org/licenses/by-nc-nd/4.0/deed.ru
В финальной версии книги часть лицензии ND, запрещающая создавать производные тексты, будет снята.
Меня дважды спрашивали: «Скажите, мистер Бэббидж, что случится, если вы введете в машину неверные цифры? Cможем ли мы получить правильный ответ?» Я не могу себе даже представить какая путаница в голове может привести к подобному вопросу. Чарльз Бэббидж
При изучении программирования возникает много проблем. Одна из них связана с тем, что мы изучаем язык, и, естественно, пытаемся провести параллели с уже известными нам языками - английским, немецким... Изучая английский, мы не спрашиваем, почему в нем нет падежей или почему эти глаголы неправильные, а не вон те, хотя лингвисты знают ответы и на эти вопросы. В отличие от естественных языков, языки программирования появились недавно, всего лишь около 60 лет назад, все статьи и книги, посвященные предмету, сохранились, и восстановить последовательность появления в языках программирования, например, объектов или генераторов, не составляет особенного труда.
Конечно, сказанное не относится только к программированию. Многие придуманные людьми вещи появляются в школьном курсе как данность. Предполагается их изучение и запоминание, но не выяснение вопроса «а почему, собственно, оно было сделано именно так, а не иначе».
Цель данного текста — заполнить образовавшуюся пустоту и, во-первых, рассказать о том, как появлялись и
эволюционировали языки программирования, а во-вторых, показать
общие принципы их построения. Для успешного освоения курса нужно знать хотя бы один язык программирования.
Большинство примеров даны на C, Pascal или Python, причем, в большинстве случаев, без какого-либо предпочтения
тому или другому языку.
Этот текст написан под сильным влиянием предыдущей работы на эту тему - книги Дэвида Баррона «Введение в языки программирования», перевод которой вышел в издательстве МИР в 1980 году. Для своего времени книга была необычная, яркая и запоминающаяся, прежде всего легкостью изложения, а также взглядом на проблемы сверху, с высоты птичьего полета. К сожалению, в наши дни эта замечательная книжка безнадежно устарела. Многие языки, которые сравнивает автор, сейчас остались только в виртуальных музеях. Из книги Баррона я позаимствовал общую структуру изложения и манеру ставить эпиграфы. Некоторые явно устаревшие языки, вроде Fortran будут, тем не менее, подробно разобраны, поскольку разбор ошибок, допущенных при их конструировании, может быть полезным для последующих поколений изобретателей языков.
Первым полноценным языком программирования был Fortran, придуманный в 1954 году, и впервые реализованный в 1957-м. Годом позже появились Algol и Lisp. Удивительно, что большинство особенностей языка Fortran образца 1954 года в наше время считаются устаревшими, но, в отличие от него, Algol был вполне современным языком. Достаточно сказать, что популярные в наше время языки Pascal и C (а также Java, PHP и C#) сделаны на основе языка Algol путем добавления некоторых усовершенствований. А вот следующий по счету язык Cobol был опять снабжен невероятным количеством особенностей, которые не пригодились в дальнейшем.
Сам язык Algol в начале XXI века не используется вообще, а вот Lisp прожил полвека почти без изменений. Любопытно также, что развитие искусственных языков програмирования шло тем же путем, что и развитие естественных: от сложного к простому. Так же, как из русского языка исчезли несколько букв, пара падежей и двойственное число, из языков программирования исчезали слишком сложные особенности. Современные языки, как правило, проще старых (C++ можно считать исключением). Некоторые устаревшие особенности языков мы будем специально рассматривать.
Внутри компьютера естественные языки выглядят неестественно
Алан Перлис
Посмотрим, как происходит процесс создания программы. Сначала необходима постановка задачи. То есть понимание того, что именно программа должна делать и зачем она нужна. С точки зрения нашей абстракции исполнения мы должны сказать, какие начальные состояния нас интересуют и какие конечные состояния мы хотим получить. Например, на входе — последовательность покупок в универсальном магазине, а на выходе — месячный отчет о продажах. На входе — текст, на выходе — список орфографических ошибок в этом тексте. И так далее.
Второй этап - придумывание алгоритма (или реализация уже известного). Часто этот этап не отделяют от третьего - кодирования. Разница между вторым и третьим этапами состоит в том, что алгоритм, может не иметь отношения к языку программирования. Алгоритм можно описать словами, картинкой или как угодно еще.
20 января 2000 года судья Южного Округа Нью-Йорка вынес решение, запрещающее распространять код программы, способной декодировать защиту DVD дисков. Программистское сообщество программистов отреагировало на этот запрет своеобразным видом протеста. Пусть запрещено публиковать текст программы, решили они, но есть статья Конституции, гарантирующая свободу слова. А значит, можно создать некое представление алгоритма, которое само не являлось бы программой, но по которому можно было бы легко восстановить текст запрещенной программы. Таким образом впервые в истории был проведен эксперимент по описанию алгоритма наибольшим возможным числом способов без использования языка программирования. Было создано несколько десятков различных способов представления алгоритма decss. В том числе: изложение в виде текста на английском языке, математических формул, чтения текста программы вслух, электронной схемы, рисунков, фильма и даже в виде хокку.
Согласно гипотезе лингвистической относительности, иначе называемой «гипотеза Сепира-Уорфа», люди, говорящие на разных языках, по-разному воспринимают мир и по-разному мыслят. Неизвестно, верна ли эта гипотеза в отношении естественных языков, но для языков программирования в этом утверждении имеется большая доля истины.
Анализируя алгоритмы, которые используют программисты на Java, Pascal или C, легко заметить сходство приемов и методов. Дело в том, что, несмотря на изобилие способов представления алгоритмов, программисты обычно используют для придумывания алгоритма тот же язык программирования, на котором пишут программу, и сочиняют алгоритм, исходя из возможностей этого языка. Иначе говоря, они думают на языке программирования.
Такая двойственность алгоритма (с одной стороны независимость от языка, а с другой - тесная связь с языком) объясняется достаточно просто. Многие языки программирования схожи между собой. Соответственно, алгоритмы, придуманные для одного языка, легко (или не очень легко) переносятся на другой. Поэтому можно говорить о представлении алгоритмов на некотором «обобщенном» языке программирования, существующем в воображении программиста, но при этом особенности языка учитываются при поиске оптимальных решений. О сходстве языков мы будем много говорить в течение всего этого курса, а сейчас обратим внимание на различия. Анализ различий позволяет нам построить классификацию или как-то систематизировать предмет изучения.
Рассмотрим характеристики языков программирования.
Для начала рассмотрим те характеристики языков программирования, которые не связаны с какими-то формальными особенностями этих языков. К числу субъективных характеристик языка относятся мощность, простота, красота (элегантность). Рассмотрим примеры.
Мощность языка — это возможность не слишком сложными конструкциями решать достаточно сложные задачи.
Простота языка обычно определяется так называемым принципом Оккама: не следует умножать число сущностей сверх необходимости.
Красота языка обычно понимается как соответствие формы содержанию и как элегантность решения тех или иных проблем проектирования языка. Любой искусственный язык это своего рода «игра ума», и некоторые языки с этой точки зрения действительно выглядят красиво. Существуют языки, у которых красота — одно из наиболее существенных достоинств. Таковы, например, Forth, Haskell и Prolog.
Язык Forth замечателен тем, что в нем любая конструкция может быть выражена через другие. Программист может создать свой
собственный IF, свой собственный WHILE и так далее. Языки Haskell и Prolog построены на базе строгих математических теорий.
Говорят, что по одежке встречают. Внешняя форма языка - первое, с чем приходится сталкиваться при его изучении. К общим элементам внешней формы языков относятся следующие элементы:
Пробелы и разбивка. Почти все современные языки допускают свободное размещение текста программы - вставку произвольного числа пробелов в тех местах, где допустим хотя бы один пробел, а также перенос строки на тех местах, где допустимы пробелы. Однако так было не всегда. Ранние языки, такие как FORTRAN, требовали от программиста совершенно определенного размещения текста программы на странице. А именно, в случае FORTRAN IV, первые 6 позиций строки должны были быть пробелами или содержать метку программы. Если в них появлялась буква С, то это означало комментарий.
C Это комментарий
C Это тоже комментарий
C На следующей строке находится оператор присваивания
X = 10
C А следующая строка - ошибка, так писать нельзя
X = 10
C А на следующей строке находится метка и оператор
10 CONTINUE
C Эта строка тоже ошибка, перед C не должно быть пробела
C А в конце программы обязательно должен стоять END
ENDИнтересно, что в Fortran пробелы играют важнейшую роль в шести первых позициях каждой строки, но дальше они полностью игнорируются.
Из современных языков форматирование интенсивно используется в языке Python, где оно играет ту же роль,что и фигурные скобки в языке C или begin ... end в Паскале.
if x < 0:
x = 0
print ('Было слишком мало, теперь ноль')
elif x == 0:
print ('Ноль')
elif x == 1:
print ('Один')
else:
print ('Много')Зарезервированные слова. Большинство языков содержат так называемые ключевые слова, имеющие некое предопределенное значение в данном языке.
Примером могут служить слова for, while и if, являющиеся ключевыми в очень многих языках. Существуют два основных подхода к ключевым словам.
Согласно первому из них, ключевые слова не могут использоваться в программе ни в каком другом значении. Невозможно сделать переменную с
именем for, или функцию с именем if. Второй подход состоит в дозволении подобных названий, и выяснении смысла происходящего из контекста.
В некоторых языках используются оба подхода: часть ключевых слов «абсолютны», а часть программист может использовать по своему усмотрению.
Начиная с языка Algol-60, созданного в 1960 году, ключевые слова, такие как for и if, считаются чем-то неделимым, не поддающимся разбиению на отдельные
символы. В некотором смысле до логического предела эту идею довели создатели компьютера Спектрум, в языке Basic которого ключевые слова и были
отдельными символами. То есть при выводе на экран символа с кодом 235 отображалось слово FOR, а символ с кодом 250 соответствовал IF.
Напротив, строки символов обычно рассматривают как изначально состоящие из отдельных символов. Так, операция поиска и замены имеет смысл для строк,
но не для ключевых слов языка.
В некоторых языках программирования, например, в Prolog и Erlang имеется нечто среднее между символами языка и строками. Это нечто называется атомы,
и это что-то вроде неделимых, то есть не состоящих из отдельных символов строк, которые определяет сам программист.
Комментарии. Уже в самых первых языках программирования появилась возможность вставлять в программу произвольный текст на естественном языке. Обычно используют два вида комментариев: блочные и строчные. Комментарии первого вида начинаются с определенного символа или сочетания символов, и продолжаются до другого предписанного сочетания символов. Основная проблема, которая возникает здесь, это так называемые вложенные комментарии.
int i;
/* это комментарий
/* а это вложенный комментарий */
является ли этот текст комментарием? */Если комментарий определяется как «текст, начинающийся с /* и заканчивающийся */», то третья строка приведенного примера не
считается комментарием. Если же комментарий это «текст, заключенный в скобки вида /* */», то третья строка - комментарий.
Разные языки по-разному решают эту проблему. Второй вид комментариев проще - они начинаются с предопределенного «заклинания» и
продолжаются до конца строки. В языке C++ и производных от него это сочетание //, встречаются также # и --.
Набор символов. Чаще всего в языках программирования используют символы латинского алфавита и знаки препинания. Используемый в
программировании набор символов, как правило, определяется стандартной клавиатурой, но с другой стороны, символы, находящиеся на
стандартной клавиатуре, отчасти определяются часто используемыми языками программирования.
Часто ли в обычных текстах встречаются фигурные скобки { и }? А в языке С они используются очень часто. До повсеместного
распространения языка С на стандартной клавиатуре таких символов не было. В ранних стандартах этого языка даже были специальные
сочетания общеупотребительных символов, которыми можно было заменять фигурные скобки.
Иногда изобретатели языков программирования выдумывают свои собственные символы. Таких много в языке ALGOL, а малоизвестный ныне язык APL в основном из них и состоит. Недостаток такого подхода очевиден - кроме самого языка, программисту приходится изучать еще и символы. (Это одна из проблем, возникающих при изучении некоторых естественных языков, например, японского или грузинского) Наверное, не все с ходу смогут это сделать. В заключение о наборе символов можно еще сказать, что в некоторых языках существует различие между прописными и строчными буквами, а в некоторых нет. В пользу и того и другого подходов есть аргументы, но в целом это дело вкуса и привычки.
Как правило, комментарии служат (вы, наверное, догадались) для комментирования программы. Однако, в некоторых случаях в язык вводят специальные виды
комментариев. Например, в языке Java комментарии, начинающиеся с /** используются для автоматического создания документации к программе.
/**
* Эта программа нажимает на кнопку.
* <p>
* Если у вас есть кнопка, ее можно нажать
* вызвав эту процедуру
* </p>
* И еще какое-то длинное объяснение того, что тут
* происходит.
*
* @param btn это описание параметров
* @return а это описание возвращаемого значения
*/
public int pushButton (Button btn) {
...
}То же самое есть в языке Python
def pushButton(button):
""" Это документация к функции pushButton
которая нажмет на кнопку, если это
зачем-то нам понадобится
"""
...В отличие от Java, в программе на Python такие описания доступны даже во время выполнения программы. Формально в Python это не совсем комментарий, однако, эти строки никак не влияют на выполнение документируемой функции.
Еще один способ нетрадиционного использования комментариев состоит в том, чтобы давать указания компилятору. Например, в языке Python при помощи следующего причудливого комментария:
# -*- coding: utf-8 -*-можно сообщить, что программа написана в кодировке utf-8
В языках C и Haskell тоже используются комментарии специального вида. Например, если программа на Haskell сгенерирована автоматически из какого-то исходника, и мы хотим видеть в отладчике не сгенерированную программу на Haskell, а исходник, нужно использовать такие комментарии:
{-# LINE 42 "source.program" #-}Часто задают вопрос: почему основу большинства языков программирования составляют слова, заимствованные из английского языка? Нельзя ли сделать язык программирования на основе русского или суахили? Можно, но возникает целый набор неожиданных проблем. В английском языке нет родов и падежей, простая структура фразы и не очень развитая грамматика. Все это позволяет легко конструировать искусственные фразы стандартного вида. Как на русский язык перевести оператор
for i=1 to N do
"Для i равного 1 до N делать"... "делай"? "повторять"? "повтори"? Фразы языков программирования выглядят не слишком красиво
на естественном языке, но все уже привыкли. Мы также привыкли обозначать математические функции латинскими словами, мы пишем
sin x, а не син x. Большая часть литературы по языкам программирования выходит на английском, так что создатели языков
английский обычно знают.
И, кроме того, у этой проблемы есть простое и элегантное решение: сделать язык программирования вообще без заимствованных из естественного языка слов. Такие языки есть, например, APL, но они тоже не пользуются особой популярностью.
Метапрограммы это такие программы, которые рассматривают самих себя и другие программы как данные.
Андерс Хейлсберг, создатель Delphi и C#
От внешнего вида программ перейдем к их функционированию. И тут же обнаружим одно важное разделение, а именно на программный код и данные. Обычно предполагается, что существует некое описание вычислительных или иных алгоритмических действий, отдельное от тех данных, над которыми эти действия выполняются. Надо сказать, что такое разделение существует не во всех языках. Иногда явного различия между данными и алгоритмом нет, и программист сам определяет, что считать данными, а что программой. Очевидно, что в таких языках возможна обработка программы как данных, и даже модификация выполняемого кода в процессе выполнения. Разумеется, почти в любом языке программирования можно открыть файл, в котором находится текст программы, и что-то с ним делать, но здесь речь идет именно об использовании данных самой программы в качестве исполняемого кода и наоборот.
Если бы язык Pascal давал нам такую возможность, мы бы могли писать что-то вроде:
var p,s: string; a:integer;
begin
readln(s);
p:='a:=2*' +s;
execute(p);
writeln(a);
end.При вводе строки ‘2’ программа печатала бы нам число 4. Понятно, что такая возможность дает нам больше возможностей для ошибок, чем реальной пользы. Поэтому смешивать программы и данные обычно позволяется только в языках с очень простым синтаксисом, где вероятность ошибки существенно ниже. Однако, есть исключения, и одно из них - Javascript, который сегодня является одним из самых распространенных языков.
Тестировщик заходит в бар и заказывает:
кружку пива, 2 кружки пива, 0 кружек пива, 999999999 кружек пива, –1 кружку пива, qwertyuip кружек пива.
Первый реальный клиент заходит в бар и спрашивает, где туалет. Бар взрывается.
Анекдот
Возможно ли определить, что программа содержит ошибки? Можно ли доказать правильность программы? И какова роль языков в этом процессе?
И самый интересный вопрос: раз уж возможно рассматривать текст программы как данные для какой-то другой программы, возможно ли написать такую программу, которая будет проверять правильность других программ? И сможет ли она заодно проверить правильность себя самой?
Тут мы прежде всего сталкиваемся со сложностями в постановке вопроса. Допустим, наша программа должна посчитать квадратный корень из некоторого числа, введенного с клавиатуры. Для отрицательных чисел правильного ответа не существует, и суть ошибки нам понятна. Если вместо числа ввести, например, фразу «Здесь был Вася», то никакой разумный ответ тоже получить не удастся. Слишком большие числа не удастся представить в машинном выражении, многие языки ограничивают «самое большое число». Назовем положительные числа, представимые в данном языке, «корректными исходными данными» для нашего примера. Таким образом, возможно несколько различных определений того, что такое правильно работающая программа.
1. Это программа, которая не зацикливается и выдает требуемый результат для определенного набора корректных входных данных. Например, чисел 4, 5 и 234.
2. Это программа, которая не зацикливается и выдает требуемый результат для любых корректных входных данных.
3. Это программа, которая не зацикливается и выдает требуемый результат для любых корректных входных данных и выдает сообщение об ошибке при некоторых некорректных входных данных.
4. Это программа, которая не зацикливается при вообще любых входных данных, выдает требуемый результат для любых корректных входных данных, и выдает сообщение об ошибке в случае любых некорректных входных данных.
Очевидно, что в случае 1 можно провести полное тестирование программы при всех оговоренных входных данных, а в случае 3 - при всех оговоренных некорректных данных и надеяться на то, что утверждения 2 и 4 соответственно тоже окажутся верными, то есть программа, правильно вычисляющая квадратный корень из 4, 5 и 234 окажется способной вычислить его и для 567, 789 и вообще для всех положительных чисел. Но тестирование программы при всех вообще возможных входных данных для достаточно серьезной программы обычно невозможно.
Что же делать? Можно попробовать доказать правильность программы примерно так же, как в математике доказывают теоремы. При том, что доказательство правильности отдельных небольших участков программы, как правило, тривиально, доказательство правильности больших алгоритмов может быть очень сложным. Хотелось бы заставить сам компьютер проделывать такие доказательства (вспомним о возможности рассматривать программу как данные). Но для этого нужно уметь формально доказывать правильность любых алгоритмов. К сожалению, в общем лучае это невозможно. И это можно доказать.
Для того, чтобы доказать правильность алгоритма нужно, в соответствии с приведенными выше определениями правильности, доказать, что алгоритм вообще когда-либо завершится.
Зацикливание программы вряд ли соответствует нашему представлению о правильности. Таким образом, нам в любом случае понадобится функция, назовем ее isfinite(), такая, что если
ей в качестве аргумента дать имя файла с корректной программой на данном языке, то результат будет true если эта программа успешно
завершается через какое-то, пусть даже очень большое, время, и false если данная программа зацикливается.
Заметим, что почти на всех языках программирования можно так или иначе зациклить программу.
Представим себе, что у нас есть эта функция, и напишем следующую несложную программу:
begin
if isfinite('test.pas') then
while 1=1 do; (* зацикливаем программу *)
else
writeln('OK'); (* нормальное завершение *)
end.Что будет, если в файле test.pas у нас окажется сама эта программа? Если функция isfinite() решит, что эта программа не зацикливается, то эта программа зациклится, и наоборот. Из полученного противоречия можно сделать вывод, что функция isfinite() невозможна. А значит, и невозможно доказать в общем случае правильность какой угодно программы. Здесь важно заметить, что во многих частных случаях такое доказательство, тем не менее, возможно. Таким образом, написать программу, проверяющую правильность других программ можно, но правильность самой этой доказывающей программы будет соответствовать лишь первому из наших определений правильности.
Этот вывод о невозможности выяснить, зацикливается ли произвольная программа, носит название «проблема остановки» и в теории алгоритмов доказывается несколько более
формально. Но на этом проблемы не заканчиваются. Теорема Райса утверждает то же самое относительно любого нетривиального свойства алгоритмов. Нетривиальным тут называется
такое свойство, которым некоторые алгоритмы обладают, а некоторые нет. Разумеется, это касается неких идеализированных алгоритмов, в нашем подходе к программам как к строкам
текста никто не мешает выяснить, например, содержит ли данная программа оператор if или переменную с именем X. Но такие свойства не считаются свойствами алгоритмов.
Низкоуровневый язык — это когда требуется внимание к вещам, которые никак не связаны с программами на этом языке.
Алан Перлис
Компьютер представляет собой устройство, способное выполнять команды, записанные в память. Команды выполняются над каким-то данными, которые тоже лежат в памяти. Память компьютера можно представить себе как набор полок, на каждой из которых может лежать число, причем число в определенном диапазоне. У каждой такой полки есть номер, то есть еще одно число, по которому можно получить хранимое на полке число или положить туда другое, заменив им имеющееся. Обычно на одной такой полке можно хранить число в диапазоне от 0 до 255 (один байт). Число 326 оказывается слишком большим и не влезает на одну полку. Однако, его можно представить в виде 256+70 и уместить в два байта со значениями 1 и 70.
Команды процессора это элементарные операции, доступные программисту. Например, сложение, вычитание, помещение числа в память или извлечение его из памяти. Команды никак не отличаются от данных, это такие же числа, и прочитав содержимое какой-либо памяти, мы никаким способом не сможем отличить команды от данных. Например, последовательность байт 102, 131, 192, 2 может означать команду для процессора x86 «прибавить 2 к содержимому регистра ax", а может означать число 1719910402, а может означать и 4 числа 102, 131, 192, 2. Интерпретация зависит от того, как программа (а не процессор) использует эти данные. В некоторых процессорах память, в которой лежат команды отделена от памяти, в которой хранятся данные, но это не меняет ситуацию - программа и данные это просто числа, хранящиеся в памяти в соответствии с описанными правилами. Проводились эксперименты по созданию процессоров, различающих типы данных, но на сегодняшний день такие процессоры не получили распространения.
Откуда вообще появились языки программирования? На самых первых компьютерах не было никаких языков. Не было также и клавиатур, дисплеев, и других удобств. Программы писали прямо в машинном коде и вводили в компьютер в двоичном коде с помощью переключателей. Одно положение переключателя означало 1, второе 0. Писать программы таким способом было крайне неудобно. Проблему переключателей решили довольно просто, приспособив к компьютеру уже имевшиеся устройства чтения перфокарт, а также электрическую пишущую машинку. Но осталась еще проблема адресов.
Предположим, у нас есть гипотетический компьютер, «понимающий» следующую систему команд: каждая команда состоит из трех чисел. Первое из них - код команды, два другие - адреса в памяти. Команды у нас будут такие: 25 - сложение, 35 - вычитание.
Тогда команда 25 10 100 означает «прибавить к содержимому ячейки памяти с адресом (номером) 10 содержимое ячейки памяти с адресом 100». Примерно так устроены команды у всех реально существующих процессоров, но коды команд и способы кодирования, естественно, различаются. При написании программы в машинных кодах программист должен был где-то для себя составить табличку, в которой записать, что по адресу 10 у него хранится, например, высота орбиты спутника, а по адресу 100 - вычисленная коррекция орбиты. Нечто подобное до сих пор делают, например, в программируемых калькуляторах или электронных таблицах, где у каждой ячейки есть номер строки и столбца, а смысл лежащего там числа известен только тому, кто работает с этой таблицей. Другая таблица, которой все время приходилось пользоваться, была таблица кодов команд, в которой было написано, что делает та или иная команда.
При необходимости изменить программу приходилось вручную выискивать все команды, ссылающиеся на измененные адреса и корректировать их. Работа кодировщика состояла в поиске в таблицах кодов команд и адресов, и в ручном вводе их в компьютер. Эту занудную работу, в ходе которой происходило множество ошибок, переложили на компьютер. Программисты стали обозначать команды легко запоминающимися сокращениями, а адреса так и вообще произвольными идентификаторами, соответствие которых реальным адресам устанавливала уже специальная программа - ассемблер. Приведенная выше команда на языке ассемблера выглядела так:
ADD Height,CorrectionНесложная программа могла заменить ADD на 25, а для переменных Height и Correction выделить реальные алреса памяти, то есть составить таблицу, в которой символическим именам были бы сопоставлены числа. Таким образом был создан первый протоязык программирования - ассемблер.
Последующее развитие систем программирования и дальше шло по пути сокращения количества рутинной работы и перекладывания на компьютер тех задач, которые вызывали наибольшее число ошибок. Традиционно принято различать компиляторы и интерпретаторы языков. Определения их такие:
Компилятор преобразует текст программы в эквивалентный машинный код, который потом исполняется уже без участия программы-компилятора.
Интерпретатор, наоборот, считывает исходный текст программы и исполняет его безо всякого преобразования путем программного моделирования.
Однако, в современном мире программ все намного сложнее, и простое разделения на компиляторы и интерпретаторы не отражает все многообразие возможностей. По существу, в мире осталось очень мало программ, которые в полном смысле можно было бы назвать интерпретаторами. Обычно используются некоторые смешанные технологии, которые с точки зрения приведенного тут классического определения можно назвать и так и этак. К счастью, для анализа языков программирования это не очень важно. Вместо классификации программ, реализующих языки, мы займемся классификацией самих языков. Среди конструкций языка в этом смысле можно выделить три основных класса:
При включении в язык таких элементов имеется в виду их реализация на какой-то конкретной машине. Под словом "машина" здесь и далее понимается определенная архитектура компьютера, набор команд и связанных со всем этим особенностей. Например, можно говорить о машинах IBM360, машинах I32, AMD64 итд. Название это используется по аналогии с термином "машина Тьюринга".
Машинно-зависимые элементы это элементы, непосредственно подсказанные особенностями той машины, с которой предполагается работать. Например, 32-битные целые числа и 8-битные байты стали фактическим стандартом, хотя не во всех компьютерах байт (единица адресации памяти) состоит из 8 бит. Были машины с 6-битными и 9-битными байтами. Размер в 8 бит был принят в качестве стандарта только в 1993 году. Для современных языков это не имеет особого значения, но, тем не менее, целые часто продолжают делать 32-битными. Или 64-битными.
Другим примером может служить Fortran, в котором есть некоторые крайне неудобные для програмиста, но «удобные» для машины конструкции. Например, машина IBM 704, для которой впервые был реализован Fortran, могла считывать только 72 символа с перфокарты, емкость которой составляла 80 символов. Байт там был шестибитный, и в 36-битное машинное слово можно было упаковать 6 символов. Отсюда пошли 6-символьные идентификаторы в языке Fortran. Так что машинные особенности могут оказывать влияние не только на выполнение программ, но даже на внешний их вид.
Когда компьютеры были большими, а память и быстродействие их - маленькими, было естественно осложнить жизнь программисту и упростить - машине. Интересно, что компиляторы первых языков программирования были намного сложнее современных, а введение машинно-зависимых элементов в языки не дало в целом сколь-нибудь заметного положительного эффекта. В современных языках конструкций, подсказанных устройством железа, становится все меньше. Однако пережитки «железячной» эпохи еще остаются в некоторых языках программирования. В языке С неявно предполагается, что символ занимает 1 байт, и может быть преобразован к типу «целое число», у которого диапазон допустимых значений более широкий. Это плохое решение как с точки зрения современных требований к представлению естественных языков (256 символов достаточно для русского языка, но уже маловато для китайского), так и с точки зрения современных компьютеров, в которых уже идет переход от 32-битного к 64-битному представлению целых чисел. Однако в С символы остаются однобайтными, а при преобразовании к целому числу 7 байт оказываются просто лишними. Языки с большим количеством машинно-зависимых элементов часто называют «языками низкого уровня».
Некоторые языковые конструкции рассчитаны на определенные способы их реализации. Это не значит, что их нельзя реализовать как-то иначе, но авторы языков часто имеют в виду конкретные варианты перевода на машинный язык. Вызовы подпрограмм в современных языках программирования C и Pascal продуманы так, чтобы упростить их реализацию на современные машинах, в которых есть программно-доступный стек возвратов. В тех редких случаях, когда такого стека нет, например, для микроконтроллера AT90S1200, обычный компилятор C не реализован. С другой стороны, способ вызова подпрограмм, принятый в языке Pascal, был реализован в процессорах Intel. Таким образом, отображаемые на машину элементы языка иногда способствуют развитию аппаратного обеспечения. Разработчики процессоров вводят в свои процессоры новые команды, еще более упрощающие реализацию таких элементов.
Это те элементы, которые не предусматривают какой-то очевидной и простой реализации в компьютере. Такие элементы требуют определенного объема программного моделирования или создания виртуальной машины, которая уже позволяет реализовать эти особенности. Примером могут служить строки в Паскале. Конструкция
var a,b,c: string;
b := 'Hello ';
c := 'World!';
a := b+c;простого выражения в кодах процессора не имеет, и приблизительно переводится в следующий алгоритм:
- выяснить длину b и c
- сложить полученные числа
- выделить область памяти с длиной, равной полученному результату сложения
- скопировать туда сначала содержимое строки b, потом содержимое строки c
- сделать так, чтобы полученная строка была доступна под именем a.
Надо заметить, что процесс выделения памяти тоже никак не укладывается в одну-две процессорных команды.
Это те части программы, которые непосредственно не вызывают порождение какого-то машинного кода, но нужны для решения задач, которые сам же язык и ставит перед программистом. Например, в языке С++ не допускается непосредственное присваивание переменной, объявленной как целое число (int) значения адреса памяти. Однако, написав так называемое "приведение типа", это можно сделать.
char *v;
int i = (int) v;С точки зрения процессора заклинание (int) тут вообще ничего не делает. И int и адрес внутри многих (не всех!) компьютеров представляются совершенно одинаково. Но для програмиста на С такая запись это знак «Внимание! Тут происходит нечто не совсем обычное". В некторых языках имеются также чисто декоративные элементы, ни на что не влияющие вообще. Так, например,в языке Pascal есть конструкция program, которая ставится в начало программы и ничего там не делает. В большинстве реализаций Паскаля ее можно просто не писать.
Это сложнопереводимое высказывание означает возможость записать какое-то часто встречающееся сочетание операторов иным способом, проще и нагляднее. Например, в С++ можно вместо
int i;
for (i=1;…написать
for (int i=1; …Syntax sugar часто встречается в современных языках, поскольку облегчает жизнь и красиво смотрится, но не только. Реализация объектно-ориентированного программирования (ООП) в языке Lua представляет собой разновидность syntax sugar.
Разделение элементов языков на машинно-зависимые, машинно-независимые и прочие весьма условно, не существует четких границ между этими классами. Тем не менее, это деление является важным для понимания языков, поскольку обычно люди путают особенности языка с особенностями конкретной его реализации в виде компилятора или интерпретатора. Правильнее говорить не о «компилируемых» или «интерпретируемых» языках, а о реализациях в виде компилятора или интерпретатора. Язык, содержащий большое количество элементов, требующих программного моделирования, скорее всего, окажется интерпретатором, и наоборот. Существуют и исключения, например, в силу совершенно непонятных причин язык BASIC, в своем исходном варианте почти не содержащий конструкций, требующих программного моделирования, чаще всего бывает интерпретатором и именно в таком виде был создан.
Совсем просто это деление на классы можно изобразить в виде лозунгов, под которыми могли бы быть созданы те или иные возможности языка.
- «Зачем что-то изобретать? У меня тут есть машина. То, что она умеет, я и включу в язык»
- «Я придумал ловкий способ реализовать эту возможность. Люди с компьютерами других типов получат массу проблем, но это будут не мои проблемы»
- «То, что я тут придумал, выглядит красиво и удобно, и какая разница, во что это обойдется. Компьютеры нынче дешевы»
- «Извините, так надо в силу логики языка»
- «Программисты будут мне благодарны за это маленькое упрощение их труда. Кроме того, это красиво»
Продолжим анализ различных характеристик языков программирования. Языки бывают:
К универсальным языкам в самом общем смысле относятся такие, на которых теоретически можно написать что угодно. Разумеется, не учитывая особенности реализации, из-за которых, например, операционная система, написанная на PHP, будет работать чересчур медленно (и требовать еще одну операционную систему для работы). Примером универсального языка может служить С (или С++). К специализированным языки, созданные для какой-то конкретной цели, либо языки, созданные с определенной целью. Зачастую специализированные языки не позволяют реализовать какой-то специфический класс алгоритмов. В качестве специализированного языка можно указать язык запросов к базам данных SQL.
Некоторые языки специально приспособлены для работы в режиме «калькулятора» - вводим строку, получаем результат. Одним из первых интерактивных языков был BASIC. Из более современных можно отметить Python, язык системы Matlab и другие. К неинтерактивным можно отнести C, С++, Pascal. В литературе режим непосредственного исполнения введенных команд обозначают сокращением REPL (Read-Evaluate-Print Loop), цикл чтения-вычисления-печати результата.
Императивными называются те языки, к которым мы больше всего привыкли. Программа в них состоит из набора команд, «приказывающих» некоторому исполнителю произвести ту или иную последовательность действий. Pascal, С, BASIC - это все императивные языки.
read (a);
read (b);
c := a*b;
print(c);Перед вами программа на императивном языке, означающая: прочесть число, назвать его a, прочесть второе число, назвать его b, перемножить а и b, результат назвать c. Во всех императивных языках эксплуатируется одна важная идея - изменяемое состояние. Когда программа читает переменную a, ее состояние меняется. Когда программа присваивает переменной c значение суммы a и b, состояние переменной c меняется. В очень общем виде смысл алгоритма на императивном языке - привести нечто, что может иметь некий набор состояний из некоторого начального состояни в желаемое состояние. Это могут быть переменные в программе, файлы данных или внешние управляемые программой устройства.
В функциональных языках выполнение любой программы равносильно вычислению значения функции. Примерами функциональных языков могут служить языки LISP и Scheme.
(write (* (string->number (read-line))
(string->number (read-line))
))Это программа на языке Scheme, означающая: напечатать произведение двух чисел, каждое из которых получено преобразованием строки, прочитанной из стандартного ввода, в число. Это та же самая программа, хотя надобность в промежуточных переменных a,b и c отпала. Важно отметить наличие так называемого «побочного эффекта» функций, который в данном случае заключается в чтении и печати чисел. Если в императивном языке чтение числа происходит в момент исполнения команды, то в функциональном есть только описание способа вычисления функции.
Главной особенностью функциональных языков является то, что в них обычно стараются избегать главного свойства языков императивных: изменяемого состояния. В приведенном примере
переменных нет вообще, но если они есть, их обычно делают неизменяемыми. Если в императивных языках переменные это «полки", на которые можно положить значения, то в
функциональных языках переменные это в полном смысле слова имена для функций или значений. Эта парадигма ближе к естественному пониманию вещей, если вашу собаку зовут Рекс,
вы обычно не склонны его менять и тем более не рассматриваете это имя как способ хранения разнообразных собак. Запись X=X+1 во многих функциональных языках (там, где вообще
возможна такая запись) не имеет смысла, X не может быть равен X+1. Тем не менее, в функциональные языки часто вводят императивные элементы, просто потому, что идея
изменяемого состояния пришла к нам из аппаратных особенностей компьютеров, и представляется программистам вполне естественной.
Посмотрим еще раз на приведенную выше программу. Допустим, в качестве первого числа ввели 0. Наша система может быть настолько «умной», что сообразит, что читать второе число в общем-то и не нужно, результат все равно будет 0. Вопрос - может ли система не читать второе число? Ответ на этот вопрос неоднозначен. Эта неоднозначность присутствует во всех функциональных языках программирования, и везде она как-то решается.
Один из очевидных способов решения - выделить отдельный класс функций, пропускать вычисление которых нельзя. Тогда в случае, если первое число 0, второе число будет все равно прочитано, хотя умножение может и не производиться.
Объектно-ориентированные языки могут основываться как на императивных, так и на функциональных, или на тех и других сразу. Они используют некую концепцию программирования, которую мы будем разбирать отдельно в посвященной этому главе. Пока что приведем примеры. Java, SmallTalk, ECMAScript - объектно-ориентированные языки.
К логическим языкам относятся те, которые используют в качестве основы ту или иную систему формальной логики. Одна из таких систем называется «дизъюнкты Хорна», в ней используются выражения вида
u <= (p AND q AND t AND ... AND z)
что надо понимать как «для того, чтобы было истинно u, необходимо, чтобы были истинны p,q, ... z». Внешне эта запись похожа на присваивание в обычных языках. Вот пример программы на Прологе :
father('pete', 'paul').
father('john', 'jim').
father('paul', 'andrew').
grandfather(C, GF) :- father(C, F) and father(F, GF).Первые 3 предложения определяют так называемые «факты», то есть утверждения, не зависящие от других. Четвертая строка определяет условное утверждение: GF является дедом C, если существует некто F, являющийся одновременно сыном GF и отцом С. С точки зрения Пролога это утверждение выглядит так: чтобы доказать, что grandfather(C, GF) истинно при некоторых значениях переменных (и одновременно найти, при каких именно C и GF), нужно сначала найти утверждение father(C, F), присвоить переменным C и F конкретные значения, в данном случае 'pete' и 'paul', а потом попробовать найти утверждение father(F, GF), используя уже найденное значение переменной F. Если не получится, то пробовать другие варианты. В этом примере условиям предиката grandfather удовлетворяют первый и третий факты. В результате выполнения программы С получается равным 'pete', а GF равным 'andrew'.
Несмотря на то, что такие языки предназначены для решения логических задач, они почти все относятся к универсальным языкам, и годятся для написания каких угодно программ. Смысл существования этих языков отчасти заключается еще и в том, что логические системы, на которых эти языки построены, являются хорошо известными и тщательно разработанными разделами математики. Кроме того, логические языки программирования требуют от программиста особенного стиля мышления, в ряде случаев весьма полезного. Первым логическим языком был Prolog, и большинство существующих сейчас логических языков (Alice, Goedel) основаны на нем.
Отдельную группу языков составляют основанные на понятии rewriting. Парадоксально, но для этого слова в Википедии не нашлось русского эквивалента, хотя один из языков этой группы, Рефал, был разработан в нашей стране. Смысл понятия rewriting очень простой. Это всего лишь обобщение идеи поиска и замены, используемых в любом текстовом редакторе.
Рассмотрим следующую простую задачу. Вы хотите задать функцию, которая определяет для любой заданной строки символов, является ли она палиндромом. Попробуем определить это формально:
-
Пустая строка является палиндромом.
-
Строка из одного символа является палиндромом.
-
Если строка начинается и оканчивается одним и тем же символом, то она является палиндромом тогда и только тогда, когда строка, полученная из нее путем удаления начального и конечного символов, является палиндромом.
-
Если не выполнено ни одно из вышеприведенных условий, строка палиндромом не является.
Обычно функциональные, логические и rewriting языки объединяют в одну группу под названием декларативных, намекая на то, что все они не задают последовательности вычислений, а декларируют некоторые факты или утверждения, ведущие к достижению цели.
Реляционные языки программирования основаны на специально придуманной системе, которая называется реляционной алгеброй, или алгеброй отношений. Смысл, опять же, в том, чтобы «подложить» под язык стройную математическую теорию. К реляционным языкам относятся SQL и Prolog.
Языки запросов относятся к специализированным языкам и предназначены для извлечения информации из баз данных.
Некоторые языки программирования создавались с совсем иной целью, нежели все остальные. По крайней мере, никто из их создателей не предполагал, что на них всерьез будут писать программы. Создание эзотерических языков программирования - это игра ума, сродни сочинению стихов, каждое слово которых начинается с буквы Ч, или изобретению машин, разбивающих яйцо наиболее сложным способом. Иногда эзотерические языки программирования создают как пародию на существующие. Таков, например, язык INTERCAL, в котором вместо команды GOTO используется конструкция COMEFROM, которая пишется в том месте, куда происходит переход.
Многие эзотерические языки программирования были придуманы с целью создать язык, писать программы на котором будет максимально сложно. Причем написать какую угодно программу должно быть просто, а вот написать программу, делающую нечто конкретное - практически невозможно. На сегодняшний день эту цель можно считать достигнутой. На языке Malbolge написано всего несколько программ, и ни одну из них не написал человек. Все они созданы автоматически, методом перебора. Такие языки нужны во-первых, затем, чтобы эта область на становилась слишком уж скучно-академической, а во-вторых как полезное упражнение в той или иной области теории языков.
Здесь можно остановиться и задать вопрос: а зачем вообще нужны разные языки? Если они все одинаковы, то почему бы всем не выучить какой-то один? Если они все разные, то почему не выбрать лучший?
Ответом могут служить следующие цитаты, приведенные в книге Д.Баррона:
«программист, знающий один язык программирования, не знает ни одного»
«если становиться программистом, то программистом хорошим. Такого программиста отличает только постоянное желание стать еще лучшим программистом, а единственный путь для этого — стремиться овладеть несколькими языками, стать хорошим лингвистом в программировании. Несомненный вред наносят те довольно хорошие программисты, которые полагают, что язык, которым они пользуются, во всех смыслах является наилучшим»
«до тех пор, пока мы не избавимся от последнего пользователя только-С или только-Паскаля, для остальных нет шансов достигнуть профессионального уровня.»
Язык программирования представляет ценность сам по себе, как произведение человеческого разума и изобретательности. Спрашивать, какой язык нужно изучить, чтобы уметь программировать – все равно, что спрашивать, какую книгу прочесть, чтобы знать литературу. Языки программирования во многом напоминают естественные, и полиглот всегда имеет преимущество в понимании языка. Попыток прекратить размножение языков программирования и создать «идеальный» язык предпринималось много, но все они оказались неудачными.
Очень часто эти вещи вызывают путаницу. Говоря, что такой-то язык «медленный", а другой «быстрый» или что один язык «позволяет делать то-то», а другой «не позволяет», люди смешивают в одну кучу собственно языки программирования, их конкретные реализации и библиотеки.
В большинстве языков программирования проводится различие между собственно элементами языка, такими как операторы, ключевые слова и т.п., и функциями, которые могут быть реализованы так или иначе, и вызываются неким единообразным способом. В некоторых языках, например, в Forth, такого различия нет. Кроме того, библиотеки функций делятся на те, которые описаны в стандарте языка или другом подобном документе, и те, которые написаны на этом языке другими людьми, не имеющими отношения к созданию и развитию данного языка. Популярность языка Python, а в не очень далеком прошлом и языка Delphi, не в последнюю очередь обусловлена наличием огромного числа сторонних библиотек, среди которых есть очень качественные, например, numpy или scipy.
Вопрос различий между реализациями сейчас стоит не так остро, как раньше, потому что у подавляющего большинства языков программирования есть реализации с открытым кодом, и их можно считать основными. Тем не менее, отличия производительности между разными реализациями языка могут быть очень существенными, хотя это не всегда можно считать характеристиками самого языка. Иначе говоря, язык не виноват, что для него написали компилятор, выдающий медленный и неэффективный код, но для некоторых языков код всегда будет более медленным, чем для других.
Ответа на вопрос «какой язык программирования самый быстрый» не существует. В Интернете уже много лет проводится игра под названием «The Computer Language Benchmarks Game». В ней участники пытаются создать наиболее эффективные реализации различных алгоритмов на разных языках программирования. Под эффективностью понимаются как скорость выполнения программы, так и необходимый для ее работы объем памяти. Результаты многолетнего труда соревнующихся именно такие: «самый эффективный язык» невозможно определить однозначно.
Например, пусть компилятор языка A выдает код, который для некоторого алгоритма выполняется вдвое быстрее, чем код для такого же алгоритма, записанного на языке B. Но в то же время язык B позволяет легко распараллелить аэтот алгоритм и выполнить его на 4 процессорных ядрах одновременно, а язык A не позволяет сделать это просто и эффективно. Но это не значит, что на языке A нельзя написать более эффективную многоядерную реализацию алгоритма, просто это сделать сложнее. И тем более это не значит, что у данного алгоритма нет еще более эффективной реализации, про которую мы не знаем.
В области компьютерной лингвистики на русском языке до сих пор нет окончательно устоявшейся терминологии, и многие важные термины переводят с английского, используя калькирование, что дополнительно все запутывает. Например, термин Duck typing, о котором мы будем говорить в разделе про ООП, вызывает в памяти рядового американца ассоциации с сенатором Маккарти, "охотой на ведьм" и вообще понятно, о чем идет речь. Русскому программисту надо специально растолковать, что вот был такой печально знаменитый Маккарти, и тогда станет ясно, почему оно так называется. А если термин еще и перевести, получится "Утиная типизация" - довольно уродливый термин и совершенно непонятный. Ну правда, не начинать же каждую лекцию про ООП с рассказа об истории послевоенных США.
В этом тексте используются английские термины там, где не находится подходящих русских эквивалентов.
Напишите программу, которая печатает свой собственный код. При этом программа не должна производить никакой ввод, не должна читать
файлы, и не должна использовать какие-то особенности реализации или операционной системы. Такая программа называется куайн, в честь
философа и лингвиста У. Куайна. Небольшая подсказка: мы можем написать программу, которая печатает "Hello, world". Далее мы можем
написать программу, которая печатает print("Hello, world"). Дальше надо всего лишь понять, как остановиться. Как это сделать, покажет
еще одна подсказка. Решите логическую задачу:
Некий ученый, назовем его Смит, написал статью, которая потом была переведена и опубликована в японском журнале. Смит не знает японского. В конце статьи на японском были добвлены следующие примечания:
- Я благодарен моему коллеге профессору Тамура за перевод данной статьи.
- Я благодарен профессору Тамура за перевод вышеприведенного примечания.
- Я благодарен профессору Тамура за перевод вышеприведенного примечания.
Почему благодарностей именно столько, сколько их есть, и как Смиту удалось избежать бесконечного повторения примечаний?
Изучите какой-нибудь ассемблер и какой-нибудь эзотерический язык программирования.
Попробуйте представить себе, как мог бы выглядеть язык программирования:
- с нестандартным набором символов
- со словами не из английского языка (а, например, эльфийского)
- вообще без слов (Scratch не подойдет, там программа набирается из табличек со словами, а надо, чтобы слов не было вовсе)
- без присваиваний и без оператора цикла