ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Встраивание нового понятия в определение синтаксиса ЯП Новая конструкция Пояснение Пример selector ={"[" expression "]"}. Индексирование доступа к элементу вектора [ind] factor = ident selector Доступ к элементу вектора X [ind] assignment = ident selector ":=" expression Присваивание элементу вектора X [ind] := 6 ArrayType = "ARRAY" expression "OF" type Вектор как тип данных ARRAY 10 OF integer type = ident | ArrayType Типы данных: целое или вектор integer FPSection = ["VAR"] IdentList ":" type Раздел параметров процедуры, возможно изменяемых VAR x,y : integer FormalParameters = "(" [FPSection {";" FPSection}] ")" Список формальных параметров процедуры (a,b: integer ; VAR x,y : integer) declarations = ["CONST" {ident "=" expression ";"}] ["TYPE" {ident "=" type ";"}] ["VAR" {IdentList ":" type ";"}] Объявления констант, типов данных и переменных CONST id = 2+3; TYPE arr10 = ARRAY 10 OF integer; VAR a1,a2,a3 : intger; xx,yy : arr10 ; 44 Дальнейшее расширение ЯП может быть сведено к подключению ТД и присоединению ВС методом раскрутки. ЯП с общей АМ семантически равномощны, на их основе достижима сравнимая эффективность процессов вычислений. Трудоѐмкость реализации АМ с помощью конкретной машины можно оценить на основе материала по низкоуровневому программированию, а также при сравнении АМ с Пи-кодом и RISK-машиной, предложенными Н. Виртом при разработке учебных языков Pascal и Oberon, и учебными машинами MIX и MMIX, описанными Д. Кнутом. Семантический спуск от полного ЯП к его БС характеризуется снижением трудоѐмкости реализации ядра ЯП и его АМ, сопровождаемое увеличением трудоѐмкости применения частичной реализации ЯП. Трудоѐмкость применения можно оценивать числом понятий, возникающих при программировании сверх тех, что присущи решению типовых задач. Цели раскрутки: – снижение трудоѐмкости начального этапа программирования; – увеличение потенциала СП, т.е. числа типовых задач, решение которых обладает приемлемой для практики трудоѐмкостью. Исследование разных схем частичных, смешанных, «ленивых» вычислений и метакомпиляции приводит к выводу о целесообразности совмещения таких схем в рамках общей СП с целью использования их преимуществ на разных уровнях изученности решаемых задач. Частичные вычисления допускают прогон программы при неполном комплекте входных данных. В результате выполняются те операции, для которых имеются данные. Одновременно строится остаточная программа, которую можно выполнить с недостающими данными и получить итоговый результат, такой, как если бы все данные были заданы изначально. Смешанные вычисления допускают произвольную разметку программы на выполнимые и задержанные действия. Выполняются маршруты, которым задержанные действия не препятствуют и выводится остаточная программа, которая может быть выполнена после снятия блокировки с задержанных действий. «Ленивые» вычисления выполняются в зависимости от необходимости операций для получения результата с запоминанием промежуточных значений выражений для экономии повторных вычислений. Метакомпиляция обрабатывает программу совместно с комплектом типовых данных. 45 Система программирования может содержать пару «интерпретатор – компилятор». На практике достоинства интерпретации проявляются при отладке программ, а преимущества компиляции – при эксплуатации готового программного продукта. Более подробное обсуждение этой темы заслуживает отдельного разговора. Теория программирования утверждает, что определение компилятора может быть выведено из определения интерпретатора методами смешанных вычислений. Компилятор по такой методике получается как остаточная программа при смешанном вычислении интерпретатора. 2.3. Структуры данных Кроме распределения памяти при компиляции различимы дисциплины, обеспечивающие эффективность работы с памятью в процессе исполнения программ: – new – delete – динамические запросы к системе памяти типа «куча»; – компактизация – уплотнение пространства с целью размещения крупных целостных объектов; – «близнецы» – метод укрупнения памяти и профилактики еѐ чрезмерной фрагментации при распределении на разно объемные блоки; – стек – дисциплина доступа FILO; – Setl – более 17-ти разных СД, динамически выбираемых СП для представления множеств в зависимости от характера их обработки и наличия свободной памяти. Типичная реализация структур данных во многих системах программирования: – векторы с паспортом, хранящим при компиляции сведения о размерах и типе элементов, не доступны при исполнении программы; – запись или структура, обеспечивающая доступ к заданному перечню разносортных элементов по статически определѐнным ключам; – объединение заданного перечня разных ТД, размещаемых в разное время по определѐнному адресу; – множество небольшого числа перечислимых элементов, обработки которых не выводит за пределы машинных команд над битовыми кодами; – стек, допускающий две дисциплины доступа, – FILO и вектор. 46 В машине списки хранятся не как последовательности символов, а как структурные формы, построенные из машинных слов как частей деревьев, подобно записям в Паскале при реализации односвязных списков. – размер и даже число выражений, с которыми программа будет иметь дело, можно не предсказывать. Кроме того, можно не организовать для размещения выражений блоки памяти фиксированной длины; – ячейки можно переносить в список свободной памяти, как только исчезнет необходимость в них. Даже возврат одной ячейки в список может быть полезен, но если данные хранятся линейно, то организовать использование лишнего или освободившегося пространства из блоков ячеек трудно; – выражения, являющиеся продолжением нескольких выражений, могут быть предоставлены однократно. В любой момент времени только часть памяти, отведенной для списков, действительно используется для хранения полезных данных. Остальные ячейки организованы в простой список, называемый списком свободной памяти. Самым интересным, можно сказать, революционным, механизмом работы с памятью в языке Lisp, стала автоматизация повторного использования памяти - «сборка мусора». С начала 1960-х годов методам такой работы посвящены многочисленные исследования, которые продолжаются до наших дней и сильно активизировались в связи с включением похожего механизма в реализацию языка Java. Общая идея всех таких методов достаточно проста: – пока памяти хватает, о ней можно не беспокоиться и располагать новые данные в новых блоках памяти; – если свободной памяти вдруг не оказалось, то надо выполнить «сборку мусора», в процессе которой, возможно, найдутся ставшие бесполезными для программы блоки; – если память нашлась, ее снова можно тратить. Специальная программа «Сборщик мусора» выполняет анализ достижимости всех блоков памяти простой пометкой узлов, видимых из конечного числа рабочих регистров системы программирования. К таким регистрам относятся промежуточные результаты вычислений, активная часть стека, ассоциативный список, таблица атомов и др. После пометки все непомеченные узлы объединяются в список свободной памяти, передающий их для повторного использования новым вызовам функции CONS. Такая автоматизация не лишена недостатков. 47 Ряд неприятных следствий: непредсказуемые длинноты (время работы) при поиске очередной порции ячеек и «перегрев системы», если такие порции слишком малы для продолжения счета. По мере роста производительности оборудования разработаны простые и не столь обременительные алгоритмы повторного использования памяти на базе параллельных процессов и профилактического копирования активных структур данных в дополнительные блоки памяти. Такие методы не требуют сложной разметки и анализа достижимости. Кроме того, почти исключается необходимость присваиваний. Они в программах заменяются именованием. Память обычно распределена по блокам, содержащим ряд слов, образующих структуры данных. Физический объем памяти, логическая длина данных и состав информации, полезной для продолжения вычислений, могут существенно различаться. Минимизацию потерь в результативности работы с памятью дает динамическая обработка бинарных деревьев – нет простоев из-за незаполнености части полей. Каждый узел такого дерева имеет небольшой объем, достаточный для хранения двух типизированных указателей (CAR и CDR, левый и правый). Типизация указателей нужна для оперативного динамического контроля соответствия данных и операций по их обработке. NIL, атомы, списки, числа, строки – все это реализационно различимые типы данных. Утверждение о бестиповости языка Lisp устарело и в наши дни заменилось признанием полноты типового контроля в динамике исполнения программ. Ранее бестиповостью называлось отсутствие статического связывания в тексте программы имен переменных с типами их значений. Для компиляции приходится дополнять Lisp-программы сведениями о типах значений свободных переменных, но далеко не каждая программа доживает до компиляции. Существуют реализации, поддерживающие автоматический вывод типов данных. Языку Lisp свойственна функциональная классификация значимых типов данных, т.е. именно реализационно различимых. Эффективность приведенного выше определения интерпретатора с использованием ассоциативного списка существенно зависит от числа различимых атомов в программе. Такая зависимость обычно смягчается механизмом функций расстановки (хэш-функций), обеспечивающим доступ к информации по ключу. В качестве ключа используется имя атома. Число свойств атома не ограничено. Свойства бывают встроенные, системные или вводимые программистом. Значения атомов, адреса встроенных операций, определяющие выражения функций – примеры встроенных свойств. 48 Обычно с машиной связывается представление о блоках информации фиксированного объема, таких как слова, байты, регистры. Функциональное программирование и ООП нацелены на более крупные построения – структуры данных не ограниченной заранее длины. Такие структуры достаточно эффективно реализуются посредством специального стека, приспособленного к обработке произвольного числа компонентов текущего уровня иерархической структуры данных. От обычного стека он отличается выделением указателя на конец текущего уровня. В результате стек хранит ссылки на границы уровней, что обеспечивает возможность возврата на любой нужный уровень, в частности, восстановления процесса обработки в случае неожиданных ситуаций. Значительный резерв производительности функциональных программ дают деструктивные функции, являющиеся формальными аналогами чистых функций, но при выполнении сопровождаемые побочными эффектами. Такой подход позволяет при необходимости повышать эффективность программ, отлаженных в стиле без использования присваиваний, простым привлечением деструктивных аналогов функций под ответственность программиста, точно знающего границы допустимых изменений хранимых данных. Непосредственная польза от сопоставления графического вида с представлением списков в памяти поясняется при рассмотрении функций, работающих со списками, на следующем примере: Диаграмма Пояснение При создании структур многократные вхождения одинаковых данных получают независимое расположение в памяти. Рис. 2. Пример ((M . N) X (M . N)) Возможное для списков использование общих фрагментов ((M . N) X (M . N)) может быть представлено графически. 49 Диаграмма Пояснение Слияние многократных вхождений одинаковых данных. Рис. 3. Графическое представление эффективного размещения данных Непосредственное текстовое представление в точности такой структуры невозможно, но ее можно построить с помощью одного из выражений: (LET ((a '(M . N))) (SETQ b (LIST a 'X a)) ) ((LAMBDA (a) (LIST a 'X a) )'(M . N)) 2.4. Реализационная прагматика При классификации ЯСП ключевое значение имеет семантика, но для уяснения преимуществ ПП, поддерживаемой ЯП, требуется понимание реализационной прагматики (РП), которая может быть не представлена в определении или стандарте ЯП, но подразумеваться традиционно. Реализационная прагматика, затрагивая все уровни определения ЯП, в основном представляет решения в области конкретной организации работы с памятью, уточняющей решения и принципы, провозглашенные в определении АМ. В первую очередь это относится к вопросам защиты областей памяти и их конечности, т.е. реагирования на дефицит памяти. Реализационная прагматика, поддерживающая разные ЯП: ФП – списки, мусорщик, списки свойств атома; ИП – побочные эффекты, векторы, ТД (переменная-значение); ЛП – разностные списки, последовательный перебор, откатка; ООП – ссылки, виртуальные и абстрактные методы и классы, множественное наследование. ЯП с общей РП реализационно равнозначны, они сравнимы по трудоѐмкости реализации СП. 50 Выводы 1. Поддержка ПП при определении ЯП и реализации СП выражается в реализации средств организации вычислений, механизмов обработки параметров и использования СД и их размещения в памяти, методов контроля за вычислениями и управления ходом вычислений. Успех применения ПП зависит от того, в какой мере используемые ЯСП поддерживают выбранную парадигму. 2. Лексически близкие и синтаксически подобные ЯП могут иметь существенные различия на уровне семантики и реализационной прагматики. 3. Диалекты ЯП часто бывают реализационно равнозначны, возможно семантически эквиваленты и равномощны, но различимы по эксплуатационной прагматике, лексике и синтаксису: – учебные концентры для ознакомления с основными идеями; – практичные подъязыки для программирования решений типовых задач; – проблемно-ориентированные вариации для расширения сферы применения; – полные языки для исследования и выбора улучшений. Т а б л и ц а 1 0 Список понятий ЯП, различаемых операционной семантикой, определяемыми для сравнения Понятие Пояснение Атом/Скаляр/Литерал Атомы и скаляры могут быть разных категорий или типов, различаемых динамически или декларативно. Структура данных Возможны ограничения на характер элементов структуры, их число и динамику их изменений. Переменная Может быть инициирована до вычислений, ограничена предписанным типом данных, заданным статически или выводимым по программе. Значение Разные типы значений связаны с различными операциями их обработки и синтаксическими позициями в тексте программы, допускающими или требующими их вхождение. Выражение Форма, результат которой может быть вычислен и использован как параметр в других формах. Действие/Операция Встроенная команда или подпрограмма, рассматриваемая как элементарная база при организации вычислений. 51 Условие/Логика Концепция истинностных значений может требовать как специального типа данных, так и рассматриваться как нагрузка обычных значений (0, NIL). Функция 6 Возможно параметризованный фрагмент программы, представляющий укрупнѐнную единицу, используемую наравне с операциями при организации вычислений. Аргумент Фактический параметр используемой функции. Вызов функции Форма, используемая для исполнения функции при заданных параметрах. Определение функции Форма, представляющая фрагмент программы, предназначенный для использования в качестве функции. Идентификатор/Имя Уникальная форма, создаваемая как синоним многократно используемого элемента данных. При неформальной характеристике стиля программирования отмечаются различия в акцентах при ответе на следующие вопросы: 1. В чем заключается основной метод обработки программы при отладке? 2. Что показывает результативную активность программы? 3. Когда принимается решение о продолжении незавершѐнных вычислений? 4. В каких пределах планируется функционирование участков повторяемости? 5. Каким способом гарантирована корректность сложной информационной обработки? Варианты ответов: 1. Основные методы обработки программы при отладке: – интерпретация текста программы, приводящая к результату еѐ выполнения; – интерпретация структуры программы, приводящая к результату еѐ выполнения; – компиляция текста программы, приводящая к коду программы, выполнение которого дает результат; – сборка кода программы из готовых типовых компонентов; – редактирование заранее подготовленных шаблонов; – генерация кода по верифицированной спецификации цели программы. 6 Операторы управления, процедуры, макросы и т. п. рассматриваются как отдельные категории функций – укрупнение действий. 52 2. Результативную активность программы показывает: – изменение состояния отдельных элементов памяти; – вычисление значения выражения; – протокол обмена данными между программой и пользователем; – изображение хода вычислений в виде диаграммы. 3. Решение о продолжении незавершѐнных вычислений принимается на основе: – наблюдения за обработкой прерываний; – получения диагностических сообщений; – анализа результатов повторного прогона программы; – подготовки обработчиков прерываний. 4. Функционирование участков повторяемости планируется: – пока имеется свободная память; – когда задано максимальное число повторений тела цикла или функции; – если известна временная граница для выполнения любой команды, включая вызов процедуры. 5. Корректность сложной информационной обработки гарантируют следующие механизмы: – статическая проверка соответствия типа данных переменных и операций; – защитные условия и инварианты циклов; – динамический контроль типов значений и допустимости операций; – верификация программ на моделях; – конструирование программ, корректных по построению. Описание концептуального языка или ядра ЯП, приспособленное для его сравнения с другими языками, содержит следующие части: – список общих понятий показывает уровень сопоставимости сравниваемых ЯП; – АС позволяет оценить глубину проработки используемых понятий; – АМ показывает масштаб переносимости СП; – РП дает оценку трудоѐмкости реализации СП; – схема интерпретации или компиляции ЯП – даѐт показатель организованности процесса вычислений; 53 – примеры программ решения типовых задач для иллюстрации концепции ЯП позволяют продемонстрировать парадигматические вариации в решении типовых задач. Кроме того, эксплуатационная прагматика представляет экспертную оценку требований к условиям применения ЯСП и критериев успешности результата программирования, что дает основания для рекомендаций по выбору ЯП, поддерживающего требуемую ПП. 2.5. Определитель парадигм Первые языки программирования обладали машинной ориентированностью и поддерживали принципиально важную, но небольшую по длительности и трудозатратам часть ЖЦП – от 2-х до 5 %, заключающуюся в кодировании готовых алгоритмов в терминах автоматов. Появление ЯВУ расширило языковое покрытие ЖЦП примерно до 10 % для хорошо поставленных задач, имеющих алгоритмы решения над типовыми структурами данных, причѐм алгоритмы приспособлены для нисходящих методик программирования. Парадигма функционального программирования посягнула на ЖЦП для задач с исследовательским компонентом и расширила его языковое покрытие до 50 % благодаря механизмам хранения и накопления информации о свойствах информационных объектов, полезной при отладке и модификации программ, составленных из небольших универсальных компонент, допускающих как нисходящую, так и восходящую методику разработки. Логическое программирование распространило эти механизмы на не вполне определенные постановки задач, что дало языковую поддержку предварительному сбору фактического материала, созданию демонстрационных версий, пробному прототипированию, отчасти тестированию и довело общее языковое покрытие ЖЦП почти до 60 % при восходящей методике разработки. Появление объектно-ориентированного программирования смягчило итеративность ЖЦП для задач, связанных с развивающимися областями приложения, что довело языковое покрытие примерно до 80 %. Определитель парадигмы языка программирования содержит следующие процедуры: – разложение языка на фрагменты по уровням/концентрам и слоям с целью выделения базовых средств языка и его реализационного ядра – семантический базис; 54 – декомпозиция семантического базиса языка на основные семантические системы с минимизацией их сложности и, возможно, их описание относительно концептуальных языков; – определение АМ языка и интерпретатора, формально достаточного для построения расширений, эквивалентных исходному языку – нормализованное определение; – сравнение полученного определения с описаниями известных парадигм и концептуальных языков; – сбоснование выводов относительно парадигмы исследуемого языка; – фразеологический словарь ПП, используемый при определении ЯП; – определение уровня языка и его ниши в жизненном цикле программ и деятельности программистов (цели и задачи), базовых языков, использованных при его создании и реализации, как основы для рекомендаций по выбору и применению ЯП и его СП. Примеры представления результатов парадигматического анализа языков программирования можно выразить в табличной форме. Т а б л и ц а 1 1 |