Надъязыковый подход к изучению языков программирования
5 причин необходимости изучения концепций языков программирования
Больше возможности для выражения идей
Более обоснованный выбор подходящего языка
Повышение способности к изучению новых языков
Углубление понимания важности реализации
Повышение способности к разработке новых языков
Области применения программирования
Научные приложения
Коммерческие приложения
Искусственный интеллект
Системное программирование
Языки подготовки сценариев
Специализированные языки программирования
Категории языков программирования
Императивные
Декларативные
Объектно-ориентированные
История развития языков программирования
40гг. – первые цифровые компьютеры – программирование путем коммутации проводов.
программирование на машинном языке
появление ассемблеров – машинные команды получают мнемонические имена (LOAD, STORE, ADD, …)
конец 50х – создание первого компилятора для языка FORTRAN (FORmula TRANslator – транслятор формул)
n более удобное средство для написания формул, чем ассемблер
n переносимость кода
Исторические требования к ЯП
Архитектура языков программирования должна быть максимально приближена к архитектуре компьютеров для наиболее эффективного использования его ресурсов.
Компьютер состоит из процессора и памяти – значит программа должна состоять из последовательности инструкций, выполняемых процессором и модифицирующих память.
Парадигма языка программирования
Компьютер представляется в виде туповатого исполнителя, тем не менее поддающегося обучению.
Исполнитель может исполнять некоторые простейшие команды.
Обучение происходит путем формирования процедур из команд и использования их в дальнейшем вместо повторения последовательности команд.
Программа описывает процесс последовательного, пошагового решения задачи.
Наклонения предложений в грамматике
изъявительное (повествовательные)
вопросительное
повелительное (императивное)
Исторически первыми сформировались императивные
(директивные, процедурные) языки программирования
Программирование в повествовательном наклонении
Стиль программирования, в котором программа представляется в как совокупность утверждений получил название декларативный.
Программа на императивном языке программирования предписывает, как достичь требуемую цель; декларативная программа заявляет (декларирует), что должно быть достигнуто в качестве цели.
Предположим, требуется пройти в городе из пункта А в пункт Б.
Декларативная программа - это план города, в котором указаны оба пункта, плюс правила уличного движения. Руководствуясь этими правилами и планом города, курьер сам найдет путь от пункта А к пункту Б.
Императивная программа - это список команд примерно такого рода: от пункта А по ул. Садовой на север до площади Славы, оттуда по ул. Пушкина два квартала, потом повернуть направо и идти до Театрального переулка, по этому переулку налево по правой стороне до дома 20, который и есть пункт Б.
Характеристики и свойства языков программирования
Характеристики
n Мощность
n Уровень
n Концептуальная целостность
Экономия понятий
Ортогональность понятий
Единообразие понятий
Универсальные и специализированные языки
Свойства
n Надежность
n Удобочитаемость
n Полнота
n Гибкость
n Простота
n Мобильность
n Эффективность
Характеристики, свойства и требования
Методы реализации
Компиляция
Интерпретация
Смешанные системы реализации
Этапы разработки программ
Технический взгляд
n Определение требований
n Проектирование
n Кодирование
n Тестирование
n Отладка
n Документирование
Психологические этапы
n Смятение
n Понимание сути
n Понимание способа реализации
n Реализация основной функции
n Реализация всех функций
n Подготовка к отчуждению
n Подготовка документации
Основные понятия ЯП
Базовые определения
Объекты данных
Типы данных
Выражения и операторы
Блоки и подпрограммы
Абстрактные типы данных
Дополнительные возможности
Базовые определения
Язык программирования – множество текстов (последовательностей символов) некоторого алфавита, удовлетворяющих правилам синтаксиса и задающих порядок вычисления в соответствии с правилами семантики.
Алфавит ЯП – набор символов, включающий буквы, цифры и специальные знаки (пунктуации, операций и т. д.).
Синтаксис ЯП – совокупность правил записи, которым должна удовлетворять любая программа.
Семантика ЯП – правила, определяющие, какие операции и в какой последовательности должна выполнить ЭВМ, работая по программе.
Состав языков программирования
Базовые определения
lЯзык программирования – множество текстов (последовательностей символов) некоторого алфавита, удовлетворяющих правилам синтаксиса и задающих порядок вычисления в соответствии с правилами семантики.
lАлфавит ЯП – набор символов, включающий буквы, цифры и специальные знаки (пунктуации, операций и т. д.).
lСинтаксис ЯП – совокупность правил записи, которым должна удовлетворять любая программа.
lСемантика ЯП – правила, определяющие, какие операции и в какой последовательности должна выполнить ЭВМ, работая по программе.
Семантика ЯП
Семантика ЯП задается определением средств описания данных и действий.
Типы данных
lРанние языки
nВспомогательный прием для облегчения работы компилятора
lСовременные языки
nВыражение задачи с большей ясностью
nОбеспечение высокой надежности
Типичные классы ошибок
lОбъектам данных могут присваиваться логически некорректные значения
lК объекту данных может быть применена логически некорректная операция
Типы данных
lПростые
nЦелые
nДействительные
nСимвольные
nЛогические
lСтруктурные
nМассивы
nЗаписи
nОбъединения
Пример описания переменных и записи операция над данными различных типов
I: integer := 1;
С: character := '1';
В: boolean := true;
1+1
1<=2
С > 'А‘
В and false
В or true
Пример использования массива и записи
A: array (1..5) of integer;
R: record
I: integer;
C: character;
B: boolean;
end record;
U: union
integer;
character;
boolean;
end union;
lA(4) – обращение к 4-му элементу массива А
lR. В – обращение к переменной B записи R
lU := ‘A’ присваивание переменной U символьного значения
Массив
Запись
Объединение
Требования к средствам описания действий
lДолжны быть надежны (минимум ошибок при написании программы)
lСмысл должен быть очевиден и однозначен (чтобы можно было легко понять общую структуру программы)
lДолжны обеспечивать достаточную гибкость (чтобы программист мог выразить свой алгоритм просто и эффективно)
Требования противоречивы – при разработке языков пытаются достичь компромисса
Выражение и присваивание
lВиражение — это формула для вычисления значения некоторого типа. В общем случае выражение представляет собой один или несколько операндов, разделенных знаками операций
lОператор присваивания “:=“ Слева от знака оператора указывается тот объект данных, которому в качестве значения присваивается значение стоящего справа выражения
I, J: integer;
PI: constant real := 3.;
В: boolean;
A: array (1..5) of real;
R: record
K: integer;
D: character;
end record;
I:=I+J*2;
J:=3*(I-J)+R. K;
B:=B and (A(3)<PI) and (R. D=‘A’);
A(5):=PI**2+A(5);
Операторы управления
lОператор «if» - условное выполнение операторов.
Проверяет некоторое условие и в зависимости от истинности или ложности его выполняет те или иные операторы.
lОператор «while» - циклическое выполнение операторов.
Выполняет заданные операторы до тех пор, пока истинно заданное условие, причем условие проверяется перед выполнением операторов.
Подсчет суммы положительных элементов массива
A: array (1..100) of integer;
SUM: integer;
I: integer;
SUM:=0;
while I<= 100 do
if A(I)>0 then
SUM:=SUM+A(I);
end if;
J:=I+1;
end do;
Необходимость структурирования программы
lВыделение логических единиц
lОсвобождение памяти от ненужных переменных
lУправление областью видимости имен
lПриближение места описания переменных к месту использования
lПовторное использование кода
Решение проблем – введение в язык понятий блока и подпрограммы
Блок
lПрограммная единица состоящая из:
nописания всех локальных (или внутренних) объектов данных и
глобальных (или внешних) объектов данных
nописания действий, которые должен выполнить блок
block
TEMP: integer;
use I, J: in out integer;
begin
TEMP:=I;
I:=J;
J:=TEMP;
end block;
Процедуры
lПроцедура – описание действий, которые необходимо выполнить в какой-то момент выполнения программы
lДля выполнения действий, описанных в процедуре используется вызов процедуры
block
I, J: integer;
procedure ПЕРЕСТАВИТЬ is
TEMP: integer;
begin
TEMP:=I;
I:=J;
J:=TEMP;
end procedure;
begin
I:=l;
J:=2;
ПЕРЕСТАВИТЬ;
ПЕРЕСТАВИТЬ;
end block;
Использование процедур с параметрами
lПараметры процедуры – специальная конструкция языка, позволяющая указывать переменные, которые должны обрабатываться в функции
block
I, J,K: integer;
procedure ПЕРЕСТАВИТЬ
(М,N: in out integer)is
TEMP: integer;
begin;
TEMP:=M;M=N;N:=TEMP;
end procedure;
begin
I:=1; J:=2; K:=3;
ПЕРЕСТАВИТЬ(I,J); //2,1,3
ПЕРЕСТАВИТЬ(J, К); //2,3,1 ПЕРЕСТАВИТЬ(К,I); //1,3,2
end block;
Функции
Функция — это специальная форма процедуры, предназначенная для вычисления одного значения.
block
I, J,K: integer;
МАХ2: integer;
function MAX
(PAR1,PAR2: in integer)
return(REZ:out, integer) is
begin
if PAR1 > PAR2 then
REZ:=PAR1;
else
REZ:=PAR2;
end if;
end function;
begin
…
MAX2 := 2*MAX(K, MAX(I, J));
…
end block;
Пакеты
lПакет – средство языка программирования для представления совокупности логически связанных вычислительных ресурсов
lПакеты могут объединять как подпрограммы, так и объекты данных и даже типы данных.
Абстрактные типы данных
lАбстрактный тип данных представляет собой описание множества значений и набора операций, с помощью которых (и только с их помощью) можно обрабатывать эти значения.
Дополнительные возможности
lОбработка файлов
lОбработка исключений
lПараллельная обработка
lМакрообработка
.
Типизация языков программирования
Основные вопросы
lПонятие типа
lОпределение типа
lСпособы контроля типов
lВиды и уровни типизации
lЭквивалентность типов
lПоколения языков программирования
Понятие типа
lПервоначально:
nТип предназначался для выбора компилятором наиболее эффективное представление для объекта.
nС машинной точки зрения тип объекта — это форма представления его значений в памяти и определяемый этой формой способ доступа.
lСовременные языки:
nЭффективность реализации как функция механизма типов отодвинута на второй план.
nБольшее значение:
lвозможность выбирать естественные структуры данных
lделать программу более понятной
lменее подверженной ошибкам
lлегче проверяемой (в т. ч. компилятором) и исправляемой
Предшествующие определения типа
lКак множество значений, которые могут принимать объекты данного типа.
nНедостаточно точно – не дает однозначного пути для построения типов
lаггауof integer и
larrayof integer (различны или нет?)
lМножество значений и набор операций, выполняемых над этими значениями и обладающих некоторыми свойствами.
nНе решается проблема однозначности:
lРазличны или нет типы двух списков, если их определения налагают разные ограничения на максимальное число элементов?
Определение типа
lТип данных - множество с операциями (алгебра), учитывающая следующее:
nесли дан новый тип, то можно описывать и инициализировать переменные этого типа;
nесли дана переменная некоторого типа, то можно определить и изменить ее текущее значение;
nесли даны два значения определенного типа, то можно сравнить их, по крайней мере на равенство или неравенство;
nописание типа дает некоторую интерпретацию определяемым синтаксисом языка символам, которые вводятся для обозначения констант.
lЕсли два типа отличаются по любым из перечисленных факторов, то такие типы считаются разными
Запись определения нового типа
type имя_типа is описание_типа;
Контроль типов
lКонтроль типов - определение типов выражений и их согласованности с типами, которые требуются по правилам языка в данном контексте программы
n(например, согласованности типов аргументов и параметров процедур)
Синтаксически правильная программа
lПрограмма называется синтаксически правильной, если она удовлетворяет правилам синтаксиса языка, т. е. не содержит синтаксических ошибок.
lОпределение синтаксической правильности программ производится на этапе компиляции.
lОбозначим множество программ этого класса через Ls.
Типово-правильная программа
lПрограмма называется типово-правильной, если она удовлетворяет правилам типизации языка.
lПравила типизации
nприписывание типов переменным и константам,
nопределение типов выражений по типам их частей
nсогласование типов частей языковых конструкций (например, операторов присваивания)
n…
lОпределение типовой правильности программ также производится на этапе компиляции.
lОбозначим множество программ этого класса через Lt
lLt – подмножество Ls.
lЕсли Lt не определено – язык не типизированный, иначе – типизированный.
Типовые ошибки
lПрограмма называется программой без типовой ошибки, если при ее выполнении не возникает типовой ошибки
nОбозначим множество программ этого класса через Le.
nLe входит в Lt
lПрограмма называется программой с выловленными типовыми ошибками, если все возникающие при ее выполнении типовые ошибки обнаруживаются при контроле типов.
nОбозначим множество программ этого класса через Ld.
lLd Í Lt \ Le
Классификация языков по способу контроля типов
lЕсли Lt = Le , т. е. типово-правильные программы не могут содержать типовых ошибок, то язык называется языком с полным статическим контролем типов.
lЕсли Ls=Lt, т. е. правила типизации языка очень слабые или их нет совсем (все синтаксически правильные программы являются типово-правильными), и, следовательно, вся работа по контролю типов производится во время выполнения программ, то язык называется языком с динамическим контролем типов.
lЕсли при этом Ld = Lt \ Le, т. е. все типовые ошибки обнаруживаются при динамическом контроле типов, то язык называется языком с полным динамическим контролем типов.
lЕсли Le Ì Lt Ì Ls, т. е. не все синтаксически правильные программы являются типово-правильными и типово-правильные программы могут содержать типовые ошибки, то язык называется языком со смешанным контролем типов.
lЕсли при этом Ld = Lt \ Le, то язык называется языком с полным смешанным контролем типов.
Классификация ЯП по способу определения семантики языковых конструкций
lЕсли семантика каждой языковой конструкции (например, операций) определяется по тексту программы, а не во время ее выполнения, т. е. статически, язык называется статически типизированным, в противном случае — динамически типизированным.
lСтатически типизированные языки:
nслабо типизированный, если информация о типе используется только для обеспечения корректности программы на машинном уровне;
nсильно типизированный, если осуществляется полный контроль типов (статический, динамический или смешанный);
nзащитно типизированный, если программы, содержащие конструкции с возможными типовыми ошибками, считаются недопустимыми, даже если эти ошибки никогда не могут возникнуть.
Проблемы слабо типизированных языков
lОперация, которая может восприниматься машиной как корректная, может быть некорректной на абстрактном уровне программы
С: character;
С:=4;
С:=‘4’;
lНеявное преобразование типов может привести к непредсказуемым результатам
X, Y: real;
I, J,K: integer;
K:=X-J;
lИз-за использования неявного преобразования типов программа может иметь законную но не очевидную интерпретацию
1<2<3 – истина и 3<2<1 – истина
Сильно типизированные языки
Используется операция явного преобразования типа
X: real;
I: integer;
В: boolean;
С: character;
Х:=rеаl(I);
C:=character(10);
Эквивалентность типов
lТребования к реализации
nинтуитивная привлекательность
nлегкость реализации
nэффективность выполнения
lЭквивалентность по структуре (структурная эквивалентность) – совпадают описания типов
lЭквивалентность по имени (именная эквивалентность) – типы с разными именами считаются разными
type TAБЛ1 is array (1..10) of integer;
type ТАБЛ2 is array (1..10) of integer;
X: array(lof integer;
Y: ТАБЛ1;
Z: ТАБЛ2;
lВ случае эквивалентности по структуре типы переменных X, Y, Z будут считаться одинаковыми, а в случае эквивалентности по имени — различными
Преимущества эквивалентности типов по имени
lСильно упрощается распознавание эквивалентности типов по имени
lЗапрещение взаимодействия различных типов, даже если они имеют одинаковую структуру.
Поколения языков
lКонкретная система типов представляет собой компромисс между эффективностями реализации и контроля типов.
lПервое поколение - языки с минимальными возможностями типизации
nПредоставляют лишь средства для описания переменных простых типов и массивов; никаких новых типов вводить нельзя.
nФортран, Алгол-60.
lВторое поколение – языки, предоставляющие программисту основные конструкторы типов: массивы, записи, объединения
nПЛ/1, Алгол-68, Паскаль, С
nТип рассматривается как множество значений, получаемых из базисных множеств с помощью конструкторов.
nВсе операции над типами данных предопределенные — определяемые языком, а не программистом.
nНовые типы могут получать имена, но с ними нельзя связывать новых, специально вводимых операций.
lТретье поколение – языки, предоставляющие программисту средства определения абстрактных типов данных
nС++, C#, Java
nТипы понимаются как множества с операциями.
Простые типы данных
Простые типы данных
Объекты простых типов не имеют внутренней структуры, они могут содержать лишь одно неделимое значение.
Числовые типы
lЦелые числа – бесконечное множество дискретных значений.
lДействительные числа - неограниченный континуум значений
Целые типы
l Описание типа имеет вид
ntype имя_типа is integer range нижняя_граница..верхняя_граница;
lПеременные такого типа могут принимать любые целые значения в указанном диапазоне
lУказание диапазона позволяет:
nповысить надежность и удобочитаемость
nвыбрать компилятору наиболее эффективный способ представления значений
Эффективность реализации
lУказание диапазона позволяет строить мобильные программы, сохраняя эффективность их реализации.
lЖелание отказаться от указания диапазона сталкивается со сложностью реализации.
type BIG_INT is integer
range -..,
INT is integer range -32768..32767,
SMALLINT is integer range -128..127;
Атрибуты целого типа
lАтрибуты типа – конструкция языка, позволяющая получить информацию о свойствах типа
lимя_типа'FIRST
lимя_типа'LAST
или
lимя_переменной'FIRST
lимя_переменной'LAST
Операции над переменными целых типов
lсложение (+)
lвычитание (-)
lумножение (*)
lделение (/)
lостаток от деления (mod)
lвозведение в степень (**)
lсравнение на равенство (=)
lсравнение на неравенство (/=)
lсравнение на меньше (<)
lсравнение на меньше или равно (<=)
lсравнение на больше (>)
lсравнение на больше или равно (>=)
lунарный плюс (+)
lунарный минус (-)
lабсолютное значение (abs)
Деление и остаток от деления
lРезультат операции деления всегда целый
lОкругление производится в сторону нуля как для положительных, так и для отрицательных значений
lОстаток от деления
X mod У = Х-(Х/У)*У
Действительные типы
lОписание имеет вид
ntype имя_типа is real range нижняя_граница..верхняя_граница digits количество значащих цифр;
nили
ntype имя_типа is real
range нижняя_граница..верхняя_граница delta абсолютная_точность;
lВ случае если диапазон не указан предполагается, что значения лежат в некотором предопределенном диапазоне, зависящем от конкретной реализации
lПеременные могут принимать любые действительные значения в указанном диапазоне, которые будут храниться либо с указанным количеством значащих цифр — плавающие типы, либо с указанной абсолютной точностью — фиксированные типы.
type
FLOAT is real range -7.2E75..7.2E75
digits 6,
FIXED is real range -2.0..2.0 delta 0.01;
Атрибуты действительных типов
lвместо имени типа можно указывать имя переменной
lимя_типа' FIRST — нижняя граница значений
имя_типа' LAST — верхняя граница значений
lимя_типа' DIGITS — количество цифр мантиссы
lимя_типа' EPSILON — абсолютное значение разности между 1.0 и ближайшим к 1.0 большим его числом данного типа
lимя_типа' SMALL — значение минимального положительного числа
lимя_типа' LARGE — значение максимального положительного числа
lимя_типа' DELTA — абсолютная точность
Запись констант
lзапись с точкой:
n10.4
n-0.
lзапись с порядком:
n104Е-1
n-145Е-12
lзапись с точкой и порядком:
n1.04Е1
n-1.45Е-10
Операции над переменными действительных типов
lсложение (+)
lвычитание (-)
lумножение (*)
lделение (/)
lвозведение в степень (**)
lсравнение на равенство (=)
lсравнение на неравенство (/=)
lсравнение на меньше (<)
lсравнение на меньше или равно (<=)
lсравнение на больше (>)
lсравнение на больше или равно (>=)
lунарный плюс (+)
lунарный минус (-)
lабсолютное значение (abs)
Особенности округления
lПри вычислении выражения с действительными числами с конечной точностью представления возникают погрешности, которые могут оказать существенное влияние на получаемые результаты
lСледует сравнивать действительные числа лишь на приближенное равенство и неравенство, например
if abs(X-Y)<0.00001*abs(X) then...
Уменьшение погрешностей вычислений
· складывать наименьшие члены сумм первыми;
· определять все положительные и отрицательные слагаемые и складывать их поочередно;
· избегать вычитания двух почти равных чисел; если это все же необходимо, производить вычитание до умножения или деления (т. е. лучше записать А*(В-С), чем А*В-А*С);
· избегать показателей степени в форме действительных чисел, так как в этом случае степень вычисляется через log и ехр; напротив, G**2 (если такая операция допускается) вычисляется как G*G;
· использовать операцию извлечения квадратного корня sqrt (если она есть) вместо G**0.5, так как sqrt обычно вычисляется точнее;
· использовать в процессе вычисления максимально возможную точность, если это необходимо;
· уменьшать число операций;
· избегать цепочек операций, в которых используются неточные значения;
Перечислимые типы
lОписание типа имеет вид:
ntype имя-типа is
(значение1, значение2, ... );
ntype АЛФАВИТ is (БУКВЫ, ЦИФРЫ, СПЕЦ_СИMB);
ntype ДНИ_НЕДЕЛИ is (ПН, ВТ, СР, ЧТ, ПТ, СБ, ВС);
lПеременная такого типа может принимать значения только из списка в описании типа.
Операции над переменными перечислимых типов
lВсегда определены
nсравнение на равенство (=)
nсравнение на неравенство (/=)
lОпределены в некоторых языках
nсравнение на меньше (<)
nсравнение на меньше или равно (<=)
nсравнение на больше (>)
nсравнение на больше или равно (>=)
Атрибуты перечислимых типов
lвместо имени типа можно указывать имя переменной
lимя_типа' POS — функция с одним параметром перечислимого типа, значением которой является порядковый номер значения параметра
lимя_типа' VAL — функция с одним параметром любого целого типа, значением которой является значение перечислимого типа, чьим порядковым номером является значение параметра
lимя_типа' FIRST — минимальное значение указанного типа имя_типа' LAST — максимальное значение указанного типа имя_типа' SUCC — функция с одним параметром перечислимого типа, значением которой является следующее по порядку значение этого перечислимого типа
lимя_типа' PRED — функция с одним параметром перечислимого типа, значением которой является предыдущее по порядку значение этого перечислимого типа
Логический тип
lОписание типа имеет вид:
ntype boolean is (false, true);
lОперации
nсравнение на равенство (=)
nсравнение на неравенство (/=)
nлогическое дополнение (not)
nлогическое И (and)
nлогическое ИЛИ (or)
Подтипы
lПодтипы используются для ограничения множества значений типа
lНапример:
type ДНИ_НЕДЕЛИ is (ПН, ВТ, СР, ЧТ, ПТ, СБ, ВС);
subtype РАБОЧИЕ ДНИ is ДНИ_НЕДЕЛИ range ПН. . ПТ;
X: РАБОЧИЕ ДНИ;
lОбъекты типа РАБОЧИЕ_ДНИ могут свободно смешиваться с объектами типа ДНИ_НЕДЕЛИ, не требуя явного применения преобразования типа
Анонимные типы
lЕсли нет необходимости вводить имя нового типа (будут описаны лишь один или два объекта этого типа) можно записать определение типа в том месте, где требуется имя типа.
lНапример:
type КЛЮЧ is (ВКЛ,ВЫКЛ);
P,Q: КЛЮЧ;
можно описать, используя механизм анонимных типов:
P.Q: (ВКЛ. ВЫКЛ);
Эквивалентность анонимных типов
lПеременные P и Q имеют один тип
P.Q: (ВКЛ. ВЫКЛ);
lПеременные P и Q имеют различные типы
Р: (ВКЛ. ВЫКЛ);
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
