Текст лекций записал: Валентин Буров.

Набрали: Валентин Буров, Илья Тюрин.

Языки Программирования.

Лекция 3

Введение.

1. Определение и схема рассмотрения языков программирования.

…………………..

2. Исторический очерк развития языков программирования.

…………………..

3. Основные понятия.

На сегодняшний день стало ясно, что некоторые базовые понятия лежат в основе любого языка программирования. Мы определили понятие языка программирования, как инструмент планирования поведения исполнителя (реального или виртуального). Любой исполнитель обладает тремя свойствами, которые играют определяющую роль с точки зрения понимания того, что собой представляет программа.

1. Любой исполнитель обрабатывает какие-то данные.

2. Над данными выполняются некоторые операции.

3. Исполнитель осуществляет связывание (binding).

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

Есть также понятие объекта данных. В функциональных языках программирования объектами данных являются переменные и константы. В языке Лисп, например, объектами данных являются атомы (символы или какие-то значения) и списки.

Разница между переменными и константами состоит во времени связывания значения с объектом данных. Константа получает свое значение до начала работы программы. Такое связывание называется статическим. Связывание значения переменной с объектом данных происходит динамически, т.е. во время выполнения программы. Основное отличие между переменными и константами заключается именно во времени связи.

Что же общего между переменными и константами? В любом случае мы говорим о некотором месте расположения данных, возможно абстрактном. В языках программирования вначале переменная появилась как абстракция ассемблерного адреса. Константа может иметь какой-то конкретный адрес в сегменте данных, а может и не иметь. В этом случае она расположена непосредственно в команде (например, MOV [BX],5). Таким образом, мы можем говорить, что всегда есть некоторое место в памяти, в которой константа хранится.

В функциональных языках принципиально отсутствует понятие "место в памяти". И в этом основное отличие нетрадиционных языков от остальных. Как только в "чистый" Лисп добавился оператор SET (и SET TO), в Лиспе стало возможным программировать как на Фортране. До появления этого оператора, программирование на Лиспе было своеобразным занятием, т.к. программа состояла исключительно из вызовов функций. В Лиспе можно объединить два списка с помощью команды (CONS AB), в результате чего образуется новый список, и при этом мы ничего не можем сказать о его местоположении. Местоположение не является атрибутом данных в функциональных языках программирования. В логических языках, типа Пролога, ситуация та же самая – объектом данных служит понятие терма (и атома). Вычисление производиться в процессе отождествления термов с соответствующими значениями. Причем опять же, у термов нет конкретного местоположения в памяти.

С точки зрения объектов данных несколько различаются и традиционные языки программирования. Например, являются ли функции и процедуры объектами данных? В стандартном Паскале – нет. А вот в языках Турбо Паскаль, Модула-2, Си - процедуры и функции являются объектами данных, потому что там появляется понятие процедурного (функционального) типа данных, следовательно, можно объявлять переменные и присваивать им соответствующие значения. Правда значениями функционального типа является адрес.

В языке Лисп есть функция (EVAL S), свой единственный аргумент-список она рассматривает как функцию на Лиспе, и выполняет программу, которая записана в списке S. Какой язык программирования с этой точки зрения является более мощным – Лисп или Си? Здесь рассмотрение с точки зрения данных и операций ничего не дает, и мы должны вспомнить о связывании. В традиционных языках программирования связывание функции с переменной функционального типа происходит до начала работы программы (функция может подгружаться динамически, однако это не меняет сути дела). В Лиспе значение списка может появляться в процессе работы (например, мы можем вводить функцию с клавиатуры).

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

Что есть значения? Все знакомые нам языки программирования умеют обрабатывать, например, такое значение – 33. Вспоминается всем знакомый анекдот:

- Штурман, - приборы.

- Восемь.

- Что восемь?

- А что приборы?

33 - что это за значение? То ли это символ "Esc" в восьмеричной системе, то ли это некоторое целое число, которое представляет счетчик или еще что-нибудь, то ли это упакованное множество. Вывод: в большинстве случаев, само значение никак не характеризует содержательную роль данных. Важнейшая роль данных с точки зрения программиста – это их содержательная роль. Оказывается, что просто множество значений очень слабо характеризует данные.

Что же характеризует данные более содержательно, чем значения? Прежде всего - набор операций. В свое время, в начале 70-х годов, когда люди начали задумываться, что же есть такое основные понятия (напридумывали языков программирования, а потом стали разбираться в том, что напридумывали), возникла целая дискуссия. Например, Вирт придумал Паскаль и написал неплохой курс программирования "Систематическое программирование", в котором (не называя Паскаль Паскалем) описывал Паскаль и то, как на нем программировать, и в частности написал, что данные характеризуются, прежде всего, своим типом данных. Тип данных с точки зрения Вирта в начале 70-х – это множество значений. В 1973 году появилась статья "Типы данных – это не значения". В этой статье говорилось о том, что данные, прежде всего, характеризуются набором операций, которые можно выполнять над этими данными, ну и, конечно же (во вторую очередь), данные характеризуются множеством значений. Этот взгляд и дал миру впоследствии некоторые очень полезные идеи. Главная формула, которой стали придерживаться:

ТИП ДАННЫХ = МНОЖЕСТВО ЗНАЧЕНИЙ + НАБОР ОПЕРАЦИЙ

Рассмотрим некоторую структуру данных, которая состоит из некоторого целого значения, и некоторого массива. Чем она является с содержательной точки зрения – непонятно. Но если мы скажем, что к этой структуре применима операция POP, которая уменьшает значение INT на единицу и возвращает элемент массива с индексом INT, а также применима операция PUSH X, которая присваивает текущему элементу массива значение X, и увеличивает INT на единицу. Теперь стало ясно, что эта структура – стек. Если мы зададим набор операций несколько иначе, мы можем получить очередь. Главное, что содержательную роль структуры определяет, прежде всего, набор операций, а потом уже множество значений. Тот же стек, мы можем реализовать иначе – как структуру данных, состоящую из указателя и некоторого поля, которое характеризует положение вершины стека. То есть в данном случае представление стека другое, однако набор операций тот же самый, т.е. смысл объекта данных определяется набором операций.

Важно понять, что понятия данных и операций очень взаимосвязаны. Пусть у нас есть некоторая структура данных, для которой существует операция Length. Эта операция возвращает длину этой структуры в некоторых единицах. Возникает вопрос: есть ли где-то данные, которые называются длиной или нет. С содержательной точки зрения это совершенно не важно. Если эта операция применяется к строкам, признак конца которых ноль (null terminated string), то вычисление длины – это действительно операция, которая требует вычислений. Если эта операция применяется к строкам, первый байт которых означает длину строки, а дальше идет сама строка (как в Turbo Pascal), то здесь происходит просто взятие данных из памяти. То есть длина может быть операцией, а может быть данными, хотя это и не важно для программиста.

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

Несколько слов о понятии виртуальной машины языка. Обратимся к истории. Как достаточно точно определить язык программирования? Этот вопрос мучит человечество очень давно. Была попытка формально определить Алгол-60 (синтаксис языка – контекстно-свободный), однако семантика языка все равно определялась на естественном языке. Этот подход сейчас стал стандартным, однако, это не точное определение языка. Как же точно определить язык? В 62-ом году, была высказана точка зрения {* кем? *} о том, что язык – это то, что умеет компилировать (интерпретировать) соответствующий компилятор (интерпретатор). То есть язык полностью определяется своим транслятором. Такая точка зрения была с удовольствием раскритикована всей прогрессивной международной общественностью. Понятно почему. Есть несколько трансляторов с языка Фортран, однако есть что-то общее (а именно, язык Фортран), что позволяет говорить об одном языке, хотя его реализации отличаются.

Когда начали развиваться методы формального описания языков программирования (в 60-е годы), в Венской лаборатории фирмы IBM, был разработан язык VDL (Vienna Definition Language), который состоял из двух компонентов – абстрактный транслятор и абстрактный интерпретатор. Абстрактный транслятор переводил программу на описываемом языке программирования (PL/1) в некоторое внутреннее представление, а абстрактный интерпретатор выполнял эту программу. Из этого метода выросла целая технология программирования VDM (Vienna Development Method), которая применялась для решения прикладных задач. Идея определения языка программирования в рамках какого-то абстрактного интерпретатора оказалась очень привлекательной и полезной. Язык Паскаль получил очень широкое распространение (хотя Вирт никого не заставлял на нем программировать, кроме своих студентов), во многом благодаря появлению микрокомпьютеров, на которые Паскаль было перенести очень легко. Дело в том, что в UCSD (University California San-Diego) была разработана система программирования на Паскале (UCSD-Pascal), которая была основана на P-коде. Они разработали интерпретатор некоторого внутреннего представления Паскаль-программы. Поскольку это представление не зависело от конкретной архитектуры ЭВМ, то можно было легко перенести эту систему программирования, написав свой интерпретатор.

Аналогичный подход был применен тогда, когда в 70-х годах разрабатывался язык программирования Smalltalk. Создатели языка определили т.н. байт-код (внутреннее представление). Единственное описание языка Smalltalk на русском языке появилось в японской книге "Языки программирования и схемотехника СБИС". Дело в том, что поскольку этот байт-код достаточно прост, то почему бы не зашить его в Сверх Большую Интегральную Схему? Большая часть этой книги и описывает архитектуру процессора, который будет интерпретировать этот байт-код. Этот проект в серию не пошел, однако был разработан программный эмулятор этого процессора.

Еще одно достижение, связанное с понятием абстрактного интерпретатора – это язык Java. Язык Java изначально проектировался для того, чтобы он мог исполняться на всех компьютерах, к которым подключена Internet, независимо от их архитектуры. Воспользовались старым добрым методом. Параллельно с языком Java был разработан соответствующий байт-код, который и назвали виртуальной машиной языка (JVM).

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