Набрали: Валентин Буров, Илья Тюрин
| Вид материала | Лекция |
- Идз №5 Индивидуальные задания из задачника Тюрин Ю. И., Ларионов В. В., Чернов, 268.29kb.
- Тюрин Сергей Борисович учебно-методический комплекс, 387.27kb.
- Тюрин Сергей Борисович учебно-методический комплекс, 459.22kb.
- Тюрин Сергей Борисович учебно-методический комплекс, 369.3kb.
- Федеральное агентство по образованию (Рособразование) Архангельский государственный, 359.58kb.
- В. Ю. Буров, Н. А. Кручинина малое предпринимательство в забайкальском крае (современное, 2671.76kb.
- Зарипов Рашид Рафкатович Проверил: Нижний Тагил 2004 г задача, 96.68kb.
- Русская литература. Электронный учебник, 348kb.
- А. М. Тюрин Аннотация: Изменения тенденций эволюции языка новгородских берестяных грамот,, 370.04kb.
- Петрик Валентин Михайлович, 487.68kb.
Текст лекций записал: Валентин Буров.
Набрали: Валентин Буров, Илья Тюрин.
Языки Программирования.
Лекция 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).
Виртуальная машина – некоторый абстрактный интерпретатор языка программирования. Виртуальная машина, как правило, реализуется следующим образом. Вводится некоторое промежуточное представление (байт-код), и определяются правила перевода программы в байт-код, а также определяются правила интерпретации байт-кода.
Есть еще один способ реализации виртуальной машины. В 60-е годы предпринимались попытки преодоления семантического разрыва между архитектурой компьютера и языком программирования, с помощью аппаратной реализации языков программирования. Было реализовано два очень интересных проекта – это машина Symbol, внутренним языком которой был Алгол-60, и машина МИР. МИР (Машина Инженерных Расчетов) была создана в Советском Союзе (на Украине), внутренним языком этой машины был язык Аналитик, который представлял собой некоторое слегка суженое расширение языка Алгол-60. Причем некоторые возможности этой машины потрясают до сих пор (в язык были встроены средства дифференцирования и интегрирования). Однако такой подход в мире не пошел, и сейчас популярность за подходом, основанном на байт-коде.
^
Часть I. Традиционные Языки Программирования
К традиционным языкам программирования относятся такие языки, как Паскаль, Си, Алгол-60, Java, Фортран, и др. Это те языки, которые основаны на Фон-неймановской модели (с учетом ее развития) поведения программы. Есть программа, есть данные (которые хранятся отдельно от программы), объектами данных являются переменные и константы. Все языки программирования, основанные на такой модели, с нашей точки зрения являются традиционными.
Поскольку традиционные языки программирования построены на понятии переменной, то основной операцией в традиционных языках программирования, является операция присваивания. Поэтому все традиционные языки программирования несколько похожи друг на друга.
Традиционные языки программирования отличаются методом классификации объектов данных, средствами изменения операций над данными, а также способами группировки операторов друг с другом (управляющие структуры).