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

Введение

Жизнь такова, какова она есть, и более никакова.

Одному моему знакомому физику-теоретику попался в руки журнал по электронике. Он внимательно его изучил и сказал, что сильно удивлен. «Они излагают материал так, как если бы все их схемы и технические решения существовали сами по себе, а не являлись изобретением других таких же инженеров» - сказал он. И действительно, многие совершенно искусственные вещи появляются в школьном курсе как данность. Предполагается их изучение и запоминание, но не выяснение вопроса «а почему, собственно, оно было сделано именно так, а не иначе». И слишком часто такое происходит с языками программирования. Хотя именно тут ответы на вопросы лежат на поверхности. Ведь интенсивная разработка языков программирования началась всего лишь около 30 лет назад, и все статьи и книги, посвященные предмету, сохранились. Цель данного текста — заполнить образовавшуюся пустоту и рассказать о том, во-первых, как появлялись и эволюционировали языки программирования, а во-вторых, показать общие принципы их построения. Для успешного освоения курса нужно знать хотя бы один язык программирования. Большинство примеров даны на C или Pascal, причем, в большинстве случаев, без какого-либо предпочтения тому или другому языку.

Эта книга написана под сильным влиянием предыдущей работы на эту тему - книги Дэвида Баррона «Введение в языки программирования», вышедшей в издательстве МИР в 1980 году. Для своего времени книга была необычная, яркая и запоминающаяся, прежде всего легкостью изложения, а также взглядом на проблемы сверху, с высоты птичьего полета. К сожалению, в наши дни эта замечательная книжка безнадежно устарела. Многие языки, которые сравнивает автор, сейчас остались только в виртуальных музеях.

Из книги Баррона я позаимствовал общую структуру изложения и манеру ставить эпиграфы перед каждой главой.

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

Языки и программы

Не всегда причиной плохого управления
является отсутствие командного голоса.
(из руководства)

Начнем с простого. Зачем нам вообще нужны компьютеры, а стало быть, и языки программирования ?

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

Изменение среды

Пусть у нас есть три переменные, a, b и c. Пусть у нас есть программа, после выполнения которой значение переменной c станет равным сумме переменных a и b. То есть если до выполнения программы a равно 3, b равно 5 и c равно 0, то после выполнения программы c должно стать равным 8. Вот эта программа :

на С

c = a+b;

на Pascal

c := a+b;

Таким образом, если до начала выполнения среда исполнения нашей программы выглядела как 3,5,0 то после успешного завершения программы она должна стать 3,5,8.Тот же подход можно обобщить на любые другие, более сложные ситуации. Останется только один вопрос: что считать «средой» ? Всё, что программа может менять. Память компьютера, файлы данных, рисунки на экране... Все это выглядит достаточно примитивно, но это всего лишь модель. Концептуальные модели и должны быть простыми. Итак: есть некое начальное состояние системы, мы запускаем программу и получаем конечное состояние системы, вот, собственно и всё. Для примера напишем чуть более сложную программу:

на С

if (b > 0)
 c = a+b;
else
 c = a-b;

на Pascal

if b > 0 then
 c := a+b;
else
 c := a-b;

Вычисление функции.

Другая абстракция, служащая для представления работы программ — вычисление функций. Функция это некое правило, по которому элементам одного множества ставятся в соответствие элементы другого множества. Приведем пример. Пусть нам нужна функция, ставящая в соответствие паре чисел a и b их сумму. Результат вычисления надо как-то запомнить или обозначить. Обозначим его c

на С

c = a+b;

на Pascal

c := a+b;

Эти две программы совпадают с предыдущими. Попробуем написать в функциональном варианте нашу более сложную программу:

на С

c = if(b > 0, a+b, a-b);

на Pascal

c := if(b > 0, a+b, a-b);

здесь if - функция, возвращающая значение второго аргумента, если первый истина, и значение третьего, если первый - ложь. Существенно то, что нигде в определении функции не говорится, что множества, на которых она определена, должны быть числами. В вышеприведенном примере мы вычисляем функцию от двух чисел, но вместо чисел мы можем использовать строки, символы и вообще что угодно. Результатом работы программы в данном случае считается результат вычисления функции. У всех функций имеется область определения, но обычно функции рассматривают на каком-то подмножестве области определения - том, которое нас интересует в постановке задачи. Здесь проявляется основная разница между подходами (и языками, на них основанными): в случае изменения среды результатом работы программы можно считать произвольный набор переменных (файлов, пикселей экрана итп), например, никто не мешает написать программу, вычисляющую сумму и разность двух чисел. Результатом функции по определению является единственное значение, поэтому в случае функционального подхода наша функция будет возвращать единую сущность - пару чисел. Заметим, что ничего необычного в понятии "пара чисел" нет, мы уже использовали такой объект в качестве аргумента нашей первой функции. Как именно эти числа будут «упакованы» в результат - другой вопрос.

В соответствии с этими двумя абстракциями можно дать два определения очень важного понятия: эквивалентности программ. В терминах изменения среды две программы считаются эквивалентными, если они изменяют среду одинаковым образом. Вопрос только в том, что именно мы рассматриваем в качестве среды. Так, если нас интересуют знчения только a, b и c, то программы

c = a+b;

и

t = a+b;
c = t;

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

c = a+b;

и

z := q+p;

тоже эквивалентны, хотя написаны на разных языках и используют разные имена переменных.

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

Программа как модель.

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

Немного истории

Первым полноценным языком программирования был Fortran, придуманный в 1954 году, и впервые реализованный в 1957-м. Годом позже появились Algol и Lisp. Удивительным фактом является то, что большинство особенностей языка Fortran в наше время считаются устаревшими, но, в отличие от него, Algol был вполне современным языком. Достаточно сказать, что популярные в наше время языки Pascal и C сделаны на основе языка Algol путем добавления некоторых полезных усовершенствований. Сам язык Algol в начале XXI века не используется вообще, а вот Lisp прожил полвека вообще без каких-либо изменений. Любопытно также, что развитие искусственных языков програмирования шло тем же путем, что и развитие естественных: от сложного к простому. Так же, как из русского языка исчезли несколько букв, как минимум один падеж и двойственное число, из языков программирования исчезали слишком сложные особенности. Современные языки, как правило, проще старых. Некоторые устаревшие особенности языков мы будем специально рассматривать.

Роль языка программирования

- Сколькими языками владеете ?
- Двумями: русским и командным.

Часто спрашивают, какой язык должен прежде всего знать программист. Ответ на этот вопрос не меняется с тех пор, как придумали программирование: свой родной язык. Русский, английский, испанский… Давайте попробуем понять, что это так. Посмотрим, как происходит процесс создания программы. Сначала необходима постановка задачи. То есть понимание того, что именно программа должна делать и зачем она нужна. С точки зрения нашей абстракции исполнения мы должны сказать, какие начальные состояния нас интересуют, и какие конечные состояния мы хотим получить. Например, на входе — последовательность покупок в универсальном магазине, а на выходе — месячный отчет о продажах. На входе — текст, на выходе — список орфографических ошибок в этом тексте. И так далее.

Второй этап - придумывание алгоритма (или использование уже известного). Часто этот этап не отделяют от третьего - кодирования. Разница между вторым и третьим этапами состоит в том, что алгоритм, как правило, не имеет отношения к языку программирования. Алгоритм можно описать словами, картинкой или как угодно еще.

DECSS
Эта история началась 20 января 2000 года, когда судья Южного Округа Нью-Йорка вынес решение, запрещающее распространять код программы, способной декодировать защиту DVD дисков. Международное сообщество программистов отреагировало на этот запрет своеобразным видом протеста. Раз запрещено публиковать текст программы, решили они, но есть статья Конституции, гарантирующая свободу слова, то можно создать некое представление алгоритма, которое само не являлось бы программой, но по которому можно было бы легко восстановить текст запрещенной программы. Таким образом впервые в истории был проведен эксперимент по описанию алгоритма наибольшим возможным числом способов. Было создано несколько десятков различных способов представления алгоритма decss. В том числе: изложение в виде текста на английском языке, математических формул, чтения текста программы вслух, электронной схемы, рисунков, фильма и даже в виде хайку.

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

Язык определяет способ мышления.

Согласно гипотезе лингвистической относительности, иначе называемой «гипотеза Сепира-Уорфа», люди, говорящие на разных языках, по-разному воспринимают мир и по-разному мыслят. Неизвестно, верна ли эта гипотеза в отношении естественных языков, но для языков программирования в этом утверждении имеется большая доля истины. Анализируя алгоритмы, которые используют программисты на Java, Pascal или C, легко заметить сходство приемов и методов. Дело в том, что, несмотря на изобилие способов представления алгоритмов, программисты обычно используют для создания алгоритма тот же язык программирования, на котором пишут программу, и придумывают алгоритм, исходя из возможностей этого языка.

Почему это так ? Давайте рассмотрим простой пример. Пусть нам нужно найти, сколькими различными способами можно расставить N предметов (N может находиться в диапазоне от 13 до 20), причем предмет номер 0 должен находиться на 10-м месте справа. Можно придумать простой алгоритм: создаем полный список всех возможных перестановок, просматриваем его и считаем только те, которые удовлетворяют условию. Проблема в том, что, во-первых, при N=20 этот алгоритм потребует примерно два миллиона терабайт памяти, а во-вторых, будет выполняться более 2000 лет, хотя алгоритм этот формально правильный.

Можно заметить, что решение задачи - это просто (N-1)! и посчитать это число, при N=20 равное 121645100408832000. Тут возникает другая проблема: это число не влезает в 32 разряда (но влезает в 64). Следовательно, решение задачи сведется либо к созданию подпрограмм для работы с 64-битными целыми числами, либо к к созданию библиотеки для работы с числами произвольной разрядности. Однако, в некоторых языках возможность работы с такими числами входит в стандартные спецификации, так что задача сводится к написанию подпрограммы вычисления факториала числа.

Такая двойственность алгоритма (с одной стороны независимость от языка, а с другой - тесная связь с языком) объясняется достаточно просто. Многие языки программирования схожи между собой. Соответственно, алгоритмы, придуманные для одного языка, легко (или не очень легко) переносятся на другой. О сходстве языков мы будем много говорить в течение всего этого курса, а сейчас обратим внимание на различия. Анализ различий позволяет нам построить классификацию или как-то систематизировать предмет изучения. Рассмотрим характеристики языков программирования.

Субъективные характеристики языков программирования

Для начала рассмотрим те характеристики языков программирования, которые не связаны с какими-то формальными особенностями этих языков. К числу субъективных характеристик языка относятся мощность, простота, красота (элегантность). Рассмотрим примеры.

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

PHP:

// данные
$s = 'Cats do not like dogs';
$a = array('cats','dogs','bats');

// программа

echo count(array_intersect(array_map("strtolower",explode(' ',$s)),$a));

C:

#include <stdio.h>
#include <string.h>

/* данные */
char s[] = "Cats do not like dogs";
char *a[]= {"cats","dogs","bats"};

/* программа */

int main()
{

   int count=0,i;   char *position;
   char word[10];
   position = s;
   while (1)
   {
      i=0;
      while(*position != ' ' && *position) 
	    word[i++] = 32 | *position++; 
	  word[i]= 0;
      for (i=0;i<sizeof(a)/sizeof(char*);i++)
        if(strcmp(a[i],word)== 0) 
		  count++;
      while(*position == ' ') 
	    ++ position ;
      if(!*position) 
	    break;
   }
   printf("%d",count);

}


Простота языка обычно определяется так называемым принципом Оккама: не следует умножать число сущностей сверх необходимости.

Ниже приводятся 3 варианта программы, печатающей приветствие «Hello World» - на языках BASIC, Java и COBOL. По внешнему виду программ легко понять, какой из этих языков проще.


BASIC

10 PRINT "Hello
World!"

JAVA

public class HelloWorld {
  public static void main(String[] args) {
    System.out.println("Hello, world!");
  }
}

COBOL

*****************************

IDENTIFICATION DIVISION.

PROGRAM-ID.
HELLO.
ENVIRONMENT DIVISION.
DATA DIVISION.
PROCEDURE DIVISION.
MAIN SECTION.
DISPLAY "Hello World!"
STOP RUN.
****************************

Красота языка обычно понимается как соответствие формы содержанию и как элегантность решения тех или иных проблем проектирования языка. Любой искусственный язык это своего рода «игра ума», и некоторые языки с этой точки зрения действительно выглядят красиво. Существуют языки, у которых красота — одно из наиболее существенных достоинств. Таковы, например, FORTH, Q и Prolog.

Язык FORTH замечателен тем, что в нем любая конструкция может быть выражена через другие. Программист может создать свой собственный IF, свой собственный WHILE и так далее. Язык Q выделяется краткостью конструкций. Вот, например, программа на Q, вычисляющая производную арифметического выражения (попробуйте это сделать на С):

diff X X	= 1;
diff X (U+V)	= diff X U + diff X V;
diff X (U*V)	= U*diff X V + V*diff X U;
diff X Y	= 0 otherwise;

Внешняя форма

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

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

C Это комментарий
C Это тоже комментарий
С на следующей строке находится метка и оператор
 10   CONTINUE
C А следующая строка - ошибка, оператор начинается не с 6й позиции
  X = 10
 C Это тоже ошибка, перед C не должно быть пробела

Интересно, что в Fortran пробелы играют важнейшую роль в шести первых позициях каждой строки, но дальше они полностью игнорируются.

Из современных языков форматирование интенсивно используется в языке Python, где оно играет ту же роль,что и фигурные скобки в языке C или begin ... end в Паскале.

if x < 0:
   x = 0
   print 'Negative changed to zero'
elif x == 0:
   print 'Zero'
elif x == 1:
   print 'Single'
else:
   print 'More'

Зарезервированные слова . Большинство языков содержат так называемые ключевые слова, имеющие некое предопределенное значение в данном языке. Примером могут служить слова for, while и if, являющиеся ключевыми в очень многих языках. Существуют два основных подхода к ключевым словам. Согласно первому из них, ключевые слова не могут использоваться в программе ни в каком другом значении. Невозможно сделать переменную с именем for, или функцию с именем if. Второй подход состоит в дозволении подобных названий, и выяснении смысла происходящего из контекста. В некоторых языках используются оба подхода: часть ключевых слов «абсолютны», а часть программист может использовать по своему усмотрению.

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

int i; 
/* это комментарий  
/* а это вложенный комментарий */
   является ли этот текст комментарием ? */

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

Набор символов. Чаще всего в языках программирования используют символы латинского алфавита и знаки препинания. Используемый в программировании набор символов, как правило, определяется стандартной клавиатурой, но с другой стороны, символы, находящиеся на стандартной клавиатуре, отчасти определяются часто используемыми языками программирования. Часто ли в обычных текстах встречаются фигурные скобки { и }? А в языке С они используются очень часто. До повсеместного распространения языка С на стандартной клавиатуре таких символов не было. В ранних стандартах этого языка даже были специальные сочетания общеупотребительных символов, которыми можно было заменять фигурные скобки. Иногда изобретатели языков программирования выдумывают свои собственные символы. Таких много в языке ALGOL, а малоизвестный ныне язык APL в основном из них и состоит. Недостаток такого подхода очевиден - кроме самого языка, программисту приходится изучать еще и символы. (Это одна из проблем, возникающих при изучении некоторых естественных языков, например, японского или грузинского) Наверное, не все с ходу смогут это сделать. В заключение о наборе символов можно еще сказать, что в некоторых языках существует различие между прописными и строчными буквами, а в некоторых нет. В пользу и того и другого подходов есть аргументы, но в целом это дело вкуса и привычки.

Задания

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