Языки программирования, базовый курс.



Исполняемый код и данные

—Материя это объективная реальность,
данная нам в ощущениях

—Кем данная ?

От внешнего вида программ перейдем к их функционированию. И тут же обнаружим одно важное разделение - на программный код и данные. Обычно предполагается, что существует некое описание вычислительных или иных алгоритмических действий, отдельное от тех данных, над которыми эти действия выполняются. Надо сказать, что такое разделение существует не во всех языках. Иногда явного различия между данными и алгоритмом нет, и программист сам определяет, что считать данными, а что программой. Очевидно, что в таких языках возможна обработка программы как данных, и даже модификация выполняемого кода в процессе выполнения. Разумеется, почти в любом языке программирования можно открыть файл, в котором находится текст программы, и что-то с ним делать, но здесь речь идет именно об использовании данных самой программы как исполняемого кода и наоборот. Если бы язык Pascal давал нам такую возможность, мы бы могли писать что-то вроде:

var p,s: string;
a:integer;
begin
  readln(s);
  p:=’a:=2*’ +s;
  execute(p);
  writeln(a);
end.

При вводе строки ‘2+2’ программа печатала бы нам число 6. Понятно, что такая возможность дает нам больше возможностей для ошибок, чем реальной пользы. Поэтому смешивать программы и данные обычно позволяется только в языках с очень простым синтаксисом, где вероятность ошибки существенно ниже.

С точки зрения компьютера, который в конечном итоге выполняет программу, ситуация тоже двойственная. Известно как минимум две основных архитектуры компьютеров, так называемые гарвардская и фон-Неймановская. Вторая из них, наиболее распространенная в настоящее время, предполагает, что данные и выполняемый код находятся в одной и той же памяти, и физической разницы между ними нет. Когда программа загружается с диска в обычном компьютере, она, как и любой другой файл, рассматривается как данные для помещения в память. После загрузки программы она начинает выполняться, и тут эти данные становятся программой. Гарвардская архитектура, напротив, разделяет программу и данные физически, помещая их в разные “хранилища”. Выполнить данные как программу процессор не может, хотя обычно возможность считать программу у него есть. По такому принципу устроено большинство микроконтроллеров, которые встраивают в различные бытовые приборы, автомобили и другие устройства.

Но и во многих реализациях фон-Неймановской архитектуры возможность исполнения данных как кода стараются исключить, или по крайней мере, осложнить. Если этого не сделать, то написание вирусов и взлом программ становятся намного более простыми задачами. Например, в операционной системе MS-DOS различия между программами и данными не было, в Windows NT и Linux оно есть, а в Windows Vista даже предпринимаются специальные меры, чтобы осложнить исполнение данных как кода в обход запретов.

Прослеживается также некоторое влияние архитектуры компьютеров на языки программирования (подробнее см. ниже, в разделе компиляция и интерпретация). Например, язык С проектировался для компьютера с фон-Неймановской архитектурой, и в результате реализация его для компьютеров гарвардского типа представляет определенные сложности.

Правильность программ

Возможно ли определить, что программа содержит ошибки ?

Можно ли доказать правильность программы ? И какова роль языков в этом процессе ?

Прежде всего в этом вопросе мы сталкиваемся со сложностями в постановке вопроса. Допустим, наша программа должна посчитать квадратный корень из введенного числа на множестве вещественных чисел. Соответственно, для отрицательных чисел правильного ответа не существует. Если вместо числа ввести, например, фразу “Здесь был Вася”, то никакой разумный ответ тоже получить не удастся. Слишком большие числа тоже не удается представить в машинном выражении. Многие языки явно ограничивают «самое большое число» величиной 232, 264 или другим. Назовем положительные числа, представимые в данном языке, “корректными исходными данными” для нашего примера. Таким образом, возможно несколько различных определений того, что такое правильно работающая программа.

1. Это программа, которая не зависает и выдает требуемый результат для определенного набора входных данных. Например, чисел 4, 5 и 234.

2. Это программа, которая не зависает и выдает требуемый результат для любых корректных входных данных.

3. Это программа, которая не зависает и выдает требуемый результат для любых корректных входных данных и выдает сообщение об ошибке при некоторых некорректных входных данных.

4. Это программа, которая не зависает при вообще любых входных данных, выдает требуемый результат для любых корректных входных данных, и выдает сообщение об ошибке в случае любых некорректных входных данных.

Очевидно, что в случае 1 можно провести полное тестирование программы при всех оговоренных входных данных, а в случае 3 - при всех оговоренных некорректных данных и надеяться на то, что утверждения 2 и 4 соответственно тоже окажутся верными, то есть программа, правильно вычисляющая квадратный корень из 4, 5 и 234 окажется способной вычислить его и для 567, 789 и вообще для всех положительных чисел. Но тестирование программы при всех вообще возможных входных данных для достаточно серьезной программы невозможно (в приведенном примере это можно сделать).

Что же делать ? Можно попробовать доказать правильность программы примерно так же, как в математике доказывают теоремы. При том, что доказательство правильности отдельных небольших участков программы, как правило, тривиально, доказательство правильности больших алгоритмов может быть очень сложным. Хотелось бы заставить сам компьютер проделывать такие доказательства (вспомним о возможности рассматривать программу как данные). Но для этого нужно уметь формально доказывать правильность любых алгоритмов. К сожалению, в общем случае это невозможно. И это можно доказать.

Доказательство

Для того, чтобы доказать правильность алгоритма нужно, в соответствии с приведенными выше определениями правильности, доказать, что алгоритм вообще когда-либо завершится. Зацикливание программы вряд ли соответствует нашему представлению о правильности. Таким образом, нам в любом случае понадобится функция, назовем ее isfinite() такая, что если ей в качестве аргумента дать любую (правильную и законченную) программу на данном языке (например, в виде строки символов), то результат будет true если эта программа успешно завершается через какое-то, пусть даже очень большое, время, и false если данная программа зацикливается. Например (на языке Pascal), isfinite(‘begin writeln(3); end.’) даст нам true, а isfinite(‘begin while 1=1 do; end.’) выдаст false. Заметим, что почти на всех языках программирования можно так или иначе зациклить программу.

Представим себе, что у нас есть эта функция, и напишем следующую несложную программу:

var p:string;
begin
  if isfinite(p) then  
    while 1=1 do; (* зацикливаем программу *)
end.

Что будет, если в качестве значения p в данной программе у нас окажется сама эта программа ? Если функция isfinite() решит, что эта программа не зацикливается, то эта программа зациклится, и наоборот. Из полученного противоречия можно сделать единственный вывод, что функция isfinite() в общем виде невозможна. А значит, и невозможно автоматически доказать правильность какой угодно программы. Здесь важно заметить, что во многих частных случаях такое доказательство возможно. Таким образом, написать программу, проверяющую правильность других программ можно, но правильность самой этой доказывающей программы будет соответствовать лишь первому из наших определений правильности.

Компиляция и интерпретация

Откуда вообще появились языки программирования ?

На самых первых компьютерах не было никаких языков. Не было также и клавиатур, дисплеев, и других удобств. Программы писали прямо в машинном коде и вводили в компьютер в двоичном коде с помощью переключателей. Одно положение переключателя означало 1, второе 0. Писать программы таким способом было крайне неудобно. Проблему переключателей решили довольно просто, приспособив к компьютеру уже имевшиеся устройства чтения перфокарт, а также электрическую пишущую машинку. Но осталась еще одна проблема - проблема адресов.

Предположим, у нас есть гипотетический компьютер, “понимающий” следующую систему команд. Каждая команда состоит из трех чисел. Первое - код команды, два другие - адреса в памяти. Команды у нас будут такие: 25 - сложение, 35 - вычитание.

Тогда команда 25 10 100 означает “прибавить к содержимому ячейки памяти с адресом 10 содержимое ячейки памяти с адресом 100”. Примерно так устроены все процессоры, но коды команд и способы кодирования, естественно, различаются. При написании программы в машинных кодах программист должен был где-то для себя составить табличку, в которой записать, что по адресу 10 у него хранится, например, высота орбиты спутника, а по адресу 100 - вычисленная коррекция орбиты. Нечто подобное до сих пор делают, например, в программируемых калькуляторах или электронных таблицах, где у каждой ячейки есть номер строки и столбца, а смысл лежащего там числа известен только тому, кто работает с этой таблицей.

При необходимости изменить программу приходилось вручную выискивать все команды, ссылающиеся на измененные адреса и корректировать их. Работа кодировщика состояла в поиске в таблицах кодов команд и адресов, и в ручном вводе их в компьютер. Эту занудную работу, в ходе которой происходило множество ошибок, переложили на компьютер. Программисты стали обозначать команды легко запоминающимися сокращениями, а адреса так и вообще произвольными идентификаторами, соответствие которых реальным адресам устанавливала уже специальная программа - ассемблер. Приведенная выше команда на языке ассемблера выглядела так:

ADD Altitude,Correction

Последующее развитие систем программирования и дальше шло по пути сокращения количества рутинной работы и перекладывания на компьютер тех задач, которые вызывали наибольшее число ошибок.

Традиционно принято различать компиляторы и интерпретаторы языков.

Определения их такие:

Компилятор преобразует текст программы в эквивалентный машинный код, который потом исполняется уже без участия программы-компилятора.

Интерпретатор, наоборот, считывает исходный текст программы и исполняет его безо всякого преобразования путем программного моделирования.

Однако, в современном мире программ все намного сложнее, и простое разделения на компиляторы и интерпретаторы не отражает все многообразие возможностей. По существу, в мире осталось очень мало программ, которые в полном смысле можно было бы назвать интерпретаторами. Обычно используются некоторые смешанные технологии, которые с точки зрения приведенного тут классического определения можно назвать и так и этак. К счастью, для анализа языков программирования это не очень важно. Вместо классификации программ, реализующих языки, мы займемся классификацией самих языков. Среди конструкций языка в этом смысле можно выделить три основных класса:

1. Машинно-зависимые, или элементы, определяемые машиной. При создании таких языков имеется в виду их реализация на какой-то конкретной машине. При этом в язык вводятся элементы, облегчающие такую реализацию, или же элементы, непосредственно подсказанные особенностями того железа, с которым предполагается работать.

Например, 32-битные целые числа и 8-битные байты стали фактическим стандартом, хотя не так давно в мире PC-совместимых компьютеров целые числа были в основном 16-битными. Для современных языков это не имеет особого значения, но, тем не менее, целые часто продолжают делать 32-битными.

Другим примером может служить FORTRAN, в котором есть некоторые крайне неудобные для програмиста, но “удобные” для машины конструкции.

Например, машина IBM 704, для которой впервые был реализован Fortran, могла считывать только 72 символа с перфокарты, емкость которой составляла 80 символов. Байт там был шестибитный, и в 36-битное машинное слово можно было упаковать 6 символов. Отсюда пошли 6-символьные идентификаторы в языке Fortran. Так что машинные особенности могут оказывать влияние не только на выполнение программ, но даже на внешний их вид.

Когда компьютеры были большими, а память и быстродействие их - маленькими, было естественно осложнить жизнь программисту и упростить - машине. Интересно, что компиляторы первых языков программирования были намного сложнее современных, а введение машинно-зависимых элементов в языки не дало в целом сколь-нибудь заметного положительного эффекта. В современных языках конструкций, подсказанных устройством железа, становится все меньше. Однако пережитки “железячной” эпохи еще остаются в некоторых языках программирования. В языке С неявно предполагается, что символ занимает 1 байт, и может быть преобразован к типу “целое число”, который немного больше по диапазону допустимых значений. Это неверно как с точки зрения современных требований к представлению естественных языков (256 символов достаточно для русского языка, но уже маловато для китайского), так и с точки зрения современных компьютеров, в которых уже идет переход от 32-битного к 64-битному представлению целых чисел. Однако в С символы остаются однобайтными, а при преобразовании к целому числу 7 байт оказываются просто лишними. Языки с большим количеством машинно-зависимых элементов часто называют “языками низкого уровня”.

2. Элементы, отображаемые на машину. Некоторые языковые конструкции рассчитаны на совершенно определенные способы реализации их в “железе”. Это не значит, что их нельзя реализовать как-то иначе, но авторы языков часто имеют в виду конкретные варианты перевода на машинный язык.

Примером отображения на машинный код может служить оператор “арифметический IF” в Fortran.

	IF a-b, 1,5,8

Эта конструкция означает: если a-b меньше 0, то перейти на метку 1, если равно 0, то на метку 5, а если больше - то на метку 8. Хороший и надежный способ запутать программу.

В компьютере IBM-360 имелась команда, по смыслу обратная этому оператору.

	BC M, LABEL

Она выполняла переход на метку LABEL если некое значение, полученное в результате предыдущих расчетов, было больше, равно или меньше нуля, если в M 2й, 3й и 4й биты соответственно были равны 1, причем можно было задавать сразу несколько условий перехода. Таким образом,

	IF a-b, 1,5,8

транслировалось в

	BC 4, LABEL1 ; если меньше 0, перейти на LABEL1
	BC 8, LABEL5 ; если равно 0, перейти на LABEL5
	BC 2, LABEL8 ; если больше 0, перейти на LABEL5

а вот часто встречающийся случай перехода если значение меньше или равно 0

	IF a-b, 5,5,8

удачно транслировался как

	BC 4+8, LABEL5
	BC 2, LABEL8

Вызовы подпрограмм в современных языках программирования C и Pascal продуманы так, чтобы легко отображаться на современные машины в которых есть программно-доступный стек возвратов. В тех редких случаях, когда такого стека нет, например, для микроконтроллера AT90S1200, обычный компилятор C не реализован. С другой стороны, способ вызова подпрограмм, принятый в языке Pascal, был реализован в процессорах Intel. Таким образом, отображаемые на машину элементы языка иногда способствуют развитию «железа». Разработчики процессоров вводят в свои процессоры новые команды, еще более упрощающие реализацию таких элементов.

3. Машинно-независимые, или элементы, определяющие виртуальную машину не предусматривают какой-то простой реализации в компьютере. Фактически, такие элементы требуют определенного объема программного моделирования, создания виртуальной машины, которая уже позволяет реализовать эти особенности. Примером могут служить строки в Паскале. Конструкция

var a,b,c: string;
...
a:=b+c;

простого выражения в кодах процессора не имеет, и приблизительно переводится в следующий алгоритм:

выяснить длину b и c
сложить полученные числа
выделить область памяти длиной, равной полученному результату сложения
скопировать туда сначала содержимое строки b, потом содержимое строки c
сделать так, чтобы полученная строка была доступна под именем a.

Надо заметить, что процесс выделения памяти тоже никак не укладывается в одну-две процессорных команды.

4. Неисполняемые элементы. Они непосредственно не вызывают порождение какого-то машинного кода, но нужны для решения задач, которые сам же язык и ставит перед программистом. Например, в языке С++ не допускается непосредственное присваивание переменной, объявленной как int значения типа “указатель”. Однако, написав так называемое “приведение типа” это можно сделать.

	char *v;
	int i = (int) v;

с точки зрения процессора заклинание (int) тут вообще ничего не делает. И int и указатель внутри многих (не всех!) компьютеров представляются совершенно одинаково. Но для програмиста на С такая запись это знак “Внимание! Тут происходит нечто, не совсем обычное”. В некторых языках имеются также чисто декоративные элементы, ни на что не влияющие вообще. Так, например,в языке Pascal есть конструкция program, которая ставится в начало программы и ничего там не делает. В большинстве реализаций Паскаля ее можно просто не писать.

5. Так называемый “syntax sugar”. Это сложнопереводимое высказывание означает возможость записать какое-то часто встречающееся сочетание операторов иным способом, проще и нагляднее. Например, в С++ можно вместо

int i; 
for (i=1;…

написать

for (int i=1; …

Syntax sugar часто встречается в современных языках, поскольку облегчает жизнь и красиво смотрится.

Такое разделение по отношению элементов языков к исполняющему компьютеру весьма условно, на самом деле не существует четких границ между этими классами. Тем не менее, это деление является важным для понимания языков, поскольку обычно люди путают особенности языка с особенностями конкретной его реализации в виде компилятора или интерпретатора. Не существует “компилируемых” или “интерпретируемых” языков, существуют реализации в виде компилятора или интерпретатора. Язык, содержащий большое количество элементов, требующих программного моделирования, скорее всего окажется интерпретатором, и наоборот. Существуют и исключения, например, в силу совершенно непонятных причин язык BASIC, в своем исходном варианте вообще не содержащий конструкций, требующих программного моделирования, чаще всего бывает интерпретатором и именно в таком виде был создан.

Совсем просто это деление на классы можно изобразить в виде лозунгов, под которыми могли бы быть созданы те или иные возможности языка.

  1. “Зачем что-то изобретать ? У меня тут есть машина. То, что она умеет, я и включу в язык”.
  2. “Я придумал ловкий способ реализовать эту возможность. Люди с компьютерами других типов получат массу проблем, но это будут не мои проблемы”
  3. “То, что я тут придумал, выглядит красиво, и какая разница, во что это обойдется. Компьютеры нынче дешевы”.
  4. “Это мой собственный язык, и писать вы будете как я скажу”
  5. “Программисты будут мне благодарны за это маленькое упрощение их труда”

Разнообразие языков программирования

Животные делятся на:
а) принадлежащих Императору,
б) набальзамированных,
в) прирученных,
г) молочных поросят,
д) сирен,
е) сказочных,
ж) бродячих собак,
з) включённых в эту классификацию,
и) бегающих как сумасшедшие,
к) бесчисленных,
л) нарисованных тончайшей кистью из верблюжьей шерсти,
м) прочих,
н) разбивших цветочную вазу,
о) похожих издали на мух.
Х.Борхес

Продолжим анализ различных характеристик языков программирования. Языки бывают:

Универсальные и специализированные.

К универсальным языкам в самом общем смысле относятся такие, на которых теоретически можно написать что угодно. Разумеется, не учитывая особенности реализации, из-за которых, например, операционная система, написанная на PHP, будет работать чересчур медленно (и требовать еще одну операционную систему для работы) . Примером универсального языка может служить С (или С++). К специализированным языки, созданные для какой-то конкретной цели, либо языки, созданные с определенной целью. Зачастую специализированные языки не позволяют реализовать какой-то класс алгоритмов. В качестве пример специализированного языка можно привести язык запросов к базам данных SQL.

Интерактивные и неинтерактивные.

Некоторые языки специально приспособлены для работы в режиме “калькулятора” - вводим строку, получаем результат. Одним из первых интерактивных языков был BASIC. Из более современных можно отметить язык системы Matlab, функциональный язык Q и другие. К неинтерактивным можно отнести C, Pascal, Haskell (язык, очень похожий на Q).

Императивные и функциональные

Императивными называются те языки, к которым мы больше всего привыкли. Программа в них состоит из набора команд, “приказывающих” некоторому исполнителю произвести ту или иную последовательность действий. Pascal, С, BASIC - это все императивные языки. Помните, мы говорили о двух парадигмах програмирования? Императивные языки олицетворяют первую из них - преобразование среды.

read (a);
read (b);
c := a+b;

Программа на императивном языке, означающая: прочесть число, назвать его a, прочесть второе число, назвать его b, сложить а и b, результат назвать c.

Естественно было бы видеть языки, основанные на второй парадигме. И такие языки есть. Они носят название функциональных. В таких языках выполнение любой программы равносильно вычислению значения функции. Если в императивных языках последовательность вычислений строго задана, и ее задание является основной обязанностью программиста, то в функциональных выбор последовательности вычислений остается за компьютером, хотя у программиста остается возможность в некоторых случаях указать ее в яном виде. Иначе говоря, целью программирования в функциональных языках является указание того, что должно быть вычислено, то в императивных программист определяет в основном, как оно должно быть сделано. Примером функционального языка может служить язык LISP.

set (result, multiply (read(), read() ) )

Это программа на несуществующем функциональном языке, означающая: назвать именем result произведение первого прочитанного числа и второго прочитанного числа.

Здесь функция set означает присваивание, функция multiply – умножение, а функция read считывает значение. Вся программа записана в виде одного выражения.

Очевидно, что это та же самая программа, хотя надобность в промежуточных a и b отпала. Важно отметить наличие так называемого “побочного эффекта” функции, который в данном случае заключается в чтении чисел. Если в императивном языке чтение числа происходит в момент исполнения команды, то в функциональном есть только описание способа вычисления функции. Допустим, в качестве первого числа ввели 0. Наша система может быть настолько”умной”, что сообразит, что читать второе число в общем-то и не нужно, результат все равно будет 0. Вопрос - может ли система не читать второе число ? Ответ на этот вопрос неоднозначен. Если за компьютером сидит человек, и программа ведет с ним примерно такой диалог:

Введите два числа, а я посчитаю их произведение.
>2
>3
Произведение равно 6.

Введите два числа, а я посчитаю их произведение.
>0
Второе число вводить не нужно, произведение равно 0

хорошо, когда это происходит в диалоге, а если числа вводятся из какого-то файла автоматически ? Эта неоднозначность присутствует во всех функциональных языках программирования, и везде она как-то решается. Один из очевидных способов решения - выделить отдельный класс функций, пропускать вычисление которых нельзя. Тогда в случае, если первое число 0, второе число будет все равно прочитано, хотя умножение может и не производиться.

Вспомним, что в C логические выражения вычисляются сокращенно, то есть в случае выражение (1 || f(x)) функция f(x) вызвана на будет. Но в C это не приводит к проблеме, потому что большая часть вычислений производится императивными операторами. Но представьте себе программу, записанную в виде одной большой функции.

Объектно-ориентированные

Объектно-ориентированные языки могут основываться как на императивных, так и на функциональных, или на тех и других сразу, а могут существовать и сами по себе. Они используют некую концепцию программирования, которую мы будем разбирать отдельно в посвященной этому главе. Пока что приведем примеры. Java, SmallTalk, ECMAScript - это все объектно-ориентированные языки.

Логические.

К логическим языкам относятся те, которые используют в качестве основы ту или иную систему формальной логики.

Одна из таких систем называется «дизъюнкты Хорна», в ней используются выражения вида

u <=(p AND q AND t AND ... AND z)

Такой текст читается как «Из p, q, t и так далее следует u», и интерпретируется «для того, чтобы было истинно 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, если существует некто М, являющийся одновременно сыном 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 очень простой. Это всего лишь поиск и замена, используемые в любом текстовом редакторе. Попробуем сделать что-то достаточно сложное, используя только поиск и замену. Рассмотрим простой набор правил:

  1. Найти в тексте «число ‘*’ число». Заменить на произведение найденных чисел.
    (Запись «число ‘*’ число» означает, что нужно найти последовательность цифр, после которой идет звездочка, после которой опять идет последовательность цифр)
  2. Найти в тексте «число ‘/’ число». Заменить на произведение найденных чисел.
  3. Найти в тексте «число ‘+’ число». Заменить на сумму найденных чисел.
  4. Найти в тексте «число ‘-’ число». Заменить на разность найденных чисел.
  5. Найти в тексте ‘(’ «число» ‘)’. Заменить на найденное число.

Применим этот набор правил к тексту “12 - 3 * (2 + 1)” несколько раз, до тех пор, пока ни одной замены сделать будет невозможно. Вот как будет меняться текст :

12 - 3 * (3) -- применили правило 3

12 - 3 * 3 -- применили правило 5, все правила пройдены, начинаем сначала

12 - 9 -- применили правило 1

3 -- применили правило 4, все правила пройдены, начинаем сначала

Больше ни одно правило не подходит, результат получен. Для создания языка на этом принципе нужно всего лишь формализовать запись правил, и придумать какие-то способы организации наборов правил, чтобы они были не все в одной куче.

Обычно функциональные, логические и rewriting языки объединяют в одну группу под названием декларативных, намекая на то, что все они не задают последовательности вычислений, а декларируют некоторые факты или утверждения, ведущие к достижению цели.

Прочие

Реляционные языки программирования основаны на специально придуманной системе, которая называется реляционной алгеброй, или алгеброй отношений. Смысл, опять же, в том, чтобы “подложить” под язык стройную математическую теорию. К реляционным языкам относятся SQL и, как ни странно, Prolog. Вообще, не стоит удивляться тому, что какие-то языки попадают не в одну категорию.

Языки запросов относятся к специализированным языкам и предназначены для извлечения информации из баз данных.

Эзотерические языки программирования

Некоторые языки программирования создавались с совсем иной целью, нежели все остальные. По крайней мере, никто из их создателей не предполагал, что на них всерьез будут писать программы. Создание эзотерических языков программирования - это игра ума, сродни сочинению стихов, каждое слово которых начинается с буквы Ч, или изобретению машин, разбивающих яйцо наиболее сложным способом.

Иногда эзотерические языки программирования создают как пародию на существующие. Таков, например, язык INTERCAL, в котором вместо команды GOTO используется инструкция COMEFROM, которая пишется в том месте, куда происходит переход.

Многие эзотерические языки программирования были придуманы с целью создать язык, писать программы на котором будет максимально сложно. Причем написать какую угодно программу должно быть просто, а вот написать программу, делающую нечто конкретное - практически невозможно. На сегодняшний день эту цель можно считать достигнутой. На языке Malbolge написано всего несколько программ, и ни одну из них не написал человек. Все они созданы автоматически, методом последовательного перебора. Такие языки нужны во-первых, затем, чтобы эта область на становилась слишком уж скучно-академической, а во-вторых как полезное упражнение в той или иной области теории языков.

Здесь можно остановиться и задать вопрос: а зачем вообще нужны разные языки? Если они все одинаковы, то почему бы всем не выучить какой-то один? Если они все разные, то почему не выбрать лучший?

Ответом может быть следующие цитаты.

«если становиться программистом, то программистом хорошим. Такого программиста отличает только постоянное желание стать еще лучшим программистом, а единственный путь для этого — стремиться овладеть несколькими языками, стать хорошим лингвистом в программировании. Несомненный вред наносят те программисты, которые полагают, что язык, которым они пользуются, во всех смыслах является наилучшим»

«до тех пор, пока мы не избавимся от последнего пользователя только-С или только-Паскаля, для остальных нет шансов достигнуть профессионального уровня.»

Язык програмирования представляет ценность сам по себе, как произведение человеческого разума и изобретательности. Спрашивать, какой язык нужно изучить, чтобы уметь программировать – все равно, что спрашивать, какую книгу прочесть, чтобы знать литературу. Языки программирования во многом напоминают естественные, и полиглот всегда имеет преимущество в понимании языка над одноязычным. Попыток прекратить размножение языков программирования и создать «идеальный» язык предпринималось много, но все они оказались неудачными.

Классификация языков программирования

В естественных науках основы истины должны быть подтверждены наблюдениями.
Карл Линней.

И все-таки, существует ли всеобъемлющая, универсальная классификация языков программирования ? Ответ на этот вопрос однозначный - не существует. Даже если бы такую классификацию вдруг придумают, на следующий день после придания ей хоть какого-то официального статуса, появится новый язык программирования (скорее всего эзотерический), специально созданный для того, чтобы нарушить эту классификацию. Языки программирования придумывают особенные люди, обладающие, помимо прочего, еще и чувством юмора.

И все-таки среди разнообразия языков можно выделить некие группы, собрав вместе языки, имеющие между собой нечто общее. Такая классификация будет заведомо неполной, зато она может оказаться полезной при изучении языков. Попробуем ее составить.

  1. Алгольная группа. К ней относятся языки C, Pascal, C++, MODULA, Delphi. Основные характеристики: это языки в основном L-типа, имеющие структуру вложенных блоков (статических и динамических), не имеющие встроенной сборки мусора и предполагающие в основном процедурный стиль программирования.
  2. Группа LISPа. Сюда входят все языки с LISP-подобным синтаксисом - сам LISP, Scheme, Dylan, Clojure, встроенные языки систем AutoCAD, Audacity, GIMP, Emacs. Отличает эти языки характерный синтаксис с множеством скобок и списки в качестве базовой структуры данных.
  3. Группа ML-языков. К ней относятся Haskell, F#, OCaml, Pure, Erlang и другие. Для них характерны: специфическая форма записи функций (rewriting), типизация, отложенные вычисления.
  4. Группа Java. Это наследники алгольной группы языков, испытавшие влияние других парадигм программирования. Все они достаточно похожи по возможностям, но отличаются синтаксисом и интерпретацией сложных типов. Это сама Java, C#, Python, Lua, ActionScript, JavaScript. Несколько особняком стоит язык PHP, который в его современном виде похож на языки группы Java, хотя пришел к этому совершенно другим путем. Это языки R-типа, объектно-ориентированные, с автоматической сборкой мусора, преимущественно процедурным стилем программирования.
  5. Группа Prolog. Включает несколько языков, построенных на принципах логического программирования.
  6. Стековые языки. Это, прежде всего, Forth, а также множество языков виртуальных машин. Широко применяется язык описания страниц PostScript, на его основе построен формат PDF. Стековые языки работают для нас, но мы, как правило, их не замечаем.

Задания

  1. Напишите программу, которая бы печатала собственный текст. Это значит, что программа, не используя никаких внешних данных, должна выводить текст, который бы с точностью до форматирования совпадал с исходным текстом самой программы. Из средств ввода-вывода разрешается использовать только стандартные операторы вывода
  2. Напишите интерпретатор арифметических выражений.