globalf5-240972240972 (850810), страница 33
Текст из файла (страница 33)
Таким образом, выделено четыре типа переходов:индуктивное и дедуктивное развитие, конкретизация и выравнивание.Эта классификация сопоставима с классификацией трансформацийпрограмм в теории смешанных вычислений, предложеннойА.П.Ершовым [9].Макетирование функцийПри разработке больших программ, особенно по нисходящей методике,необходимость в тестировании и отладке возникает отчасти раньше, чемподготовлен текст программы.
Макет программы — это некоторыйпредварительный ее текст, допускающий уточнение — доопределение .Простейший макет может быть создан из небольшой коллекции тестов,иллюстрирующих поведение программы в наиболее важных точках.Выбор таких точек — необходимая работа, результаты которой227Л.В. ГородняяОсновы функционального программированиямногократно используются на всех фазах жизненного цикла программы:при конструировании алгоритмов, автономном тестированиикомпонентовпрограммы,комплекснойотладкепрограммы,демонстрации программы всем заинтересованным лицам, при ееэксплуатации и развитии.
Функционирование простых макетовособенно легко реализуется в языках, обладающих унификациейструктур данных и функциональных объектов, таких как LISP и SETL.Подобный механизм определения функций с помощью коллекциифактов и ряда шаблонов характерен для декларативных языковпрограммирования – Prolog, ML, Haskell.SETL — язык сверхвысокого уровня, представляет собой попыткуактивного использования теоретико-множественных понятий впрактике программирования [12].Согласно концепции этого языка, понятие "функция" обладаетдвойственной природой.
Функция может быть представлена валгоритмическом стиле — определением процедуры, выполнениекоторой сопоставляет результат допустимому аргументу. Но столь жеправомерно представление функции в виде графика, отображающегоаргументы в результаты. Оба представления могут существоватьодновременно — это всего лишь две реализации одной функции.Графическое понимание функции включает в себя и табличнуюреализацию подобно математическим таблицам Брадиса. Кроме тогографик функции не обязан быть линией — это может быть фигурапроизвольныхочертаний.Следовательно,аргументуможетсоответствовать множество результатов, лежащих на пересечениивертикали с этой фигурой — графиком функции. При такой трактовкенет ничего удивительного в постепенном накоплении или построенииграфика функции. Можно задать небольшое множество точек графика, апотом постепенно его пополнять.
По замыслу Дж.Шварца, автора языкаSETL, такая методика может выполнять роль оптимизации особосложных вычислений.Более формальный макет может быть построен из спецификацийфункций в виде типовых выражений, задающих описание типоваргументов и результатов. Такой макет может работать как "заглушка" длянереализованных компонентов. Вместо них может работатьуниверсальная функция, проверяющая соответствие фактических228Л.В.
ГородняяОсновы функционального программированияаргументов предписанному типу данных и вырабатывающая в качестверезультата произвольное данное, соответствующее описаниюрезультата. Этот механизм будет более эффективен в паре с простыммакетом из тестов, если результат выбирать из коллекции тестов.Мемо-функции и тестированиеНе менее ценные следствия из унификации структурных значений ифункциональных объектов дает накопительный, кумулятивный эффектряда сеансов обработки рекурсивных программ, содержащих общиекомпоненты. Допустимость совместного хранения функциональныхопределений и тестов для их проверки в общей структуре, например всписке свойств атома, именующего функцию, позволяет строитьтехнологические макеты с множественными определениями,коллекциями тестов и спецификаций, а также с документацией.
Такиемакеты пригодны для поддержки полного жизненного циклапрограммы. Они позволяют организовывать оперативное сравнениерезультатов при обновлении системы функций. На такой основевозможно автоматическое тестирование программ. С практическойточки зрения технологические макеты — универсальный инструментдинамической оптимизации прикладных систем.Представим, что вычисление каждой рекурсивной функциисопровождается сохранением пары "аргумент, результат". После этогоможно запустить в дело слегка измененное правило интерпретациифункций. Изменение заключается в следующем: прежде чем применятьфункцию к фактическому аргументу, выполняется проверка, нет ли дляэтого аргумента уже вычисленного результата. Готовый результат и естьрезультат функции, а в противном случае все работает как обычно.Механизм сохранения насчитанных результатов функций назван "мемофункции" [4].
Естественно, основанием для его применения являетсядостаточная сложность и частота обработки. Примечательнаяособенность данного метода — любая сложность очень частыхвычислений стремится со временем к линейной.229Л.В. ГородняяОсновы функционального программированияПарадигмы программированияВ данной лекции подводится итог изучению основ ФП и особенностейего применения. Анализируются наиболее очевидные закономерностиприменения языков программирования, отражающие расширениекласса решаемых задач, прогресс элементной базы и рост квалификациипрограммистов.
Рассматриваются ключевые моменты развитияпарадигм программирования и анализируются закономерности впроцессе реализационного освоения новых областей обработкиинформации. Приведен небольшой обзор парадигм программирования.Для желающих поэкспериментировать дана справка о реализационныхособенностях GNU Clisp [6, 7].Парадигмы программированияИтоги и выводыСогласно рекомендациям специалистов по обучению информатике,функциональное программирование (ФП) входит в число основныхподходов к изучению программирования в университетах (наряду салгоритмическим , императивным , аппаратным, объектным и обзорноознакомительным). В целом средства и методы ФП образуют два слоя.Глубинный слой — локальное программирование строгих функций ,безотходных структур данных, обратимых контекстов, регулярныхотображений, корректных функций высших порядков, универсальныхфункций и средств управления вычислениями.
Внешний слой —функциональное моделирование широкогоспектрапарадигмпрограммирования,обеспечивающеепроизводственноепрограммирование прототипами, дающее подход к оценкефункциональности информационных систем и их компонентов.Глубинный слой дает концептуальную основу для применения иопределения функций во всей полноте этого понятия, для его развитияи выбора реализационных решений при разработке систем ФП, включаяпривлечение стандартной программотехники и деструктивныхфункций. Внешний слой открывает перспективы повышения уровняиспользуемых конструкций на базе моделирования основныхмеханизмовсистемного,низкоуровневого,оптимизационного,230Л.В.
ГородняяОсновы функционального программированиялогического, высокопроизводительного, ООП и других подходов кразработке программ. Такие подходы расширяют понятие "функция",варьируютправилапримененияиреализациифункций,конкретизируют расширения и специализацию систем ФП.Фактически термин "функциональное программирование" используетсяпри объединении в систему методов решения классов задач,обладающих исследовательскими аспектами, что влечет за собойнеобходимость развития полученных решений . Система предполагаетобщую логику уточнения решаемых задач и формализацию обобщенныхрешений на основе специально выбранных базовых конструкций.1. Базовые конструкции определяются как строгие функции .2.
Общая логика развития задачи сводится к процессу раскруткиполного решения как набора шагов по расширению наборафункций и повышению их потенциала использованиемотображений , что обеспечивается надежными средствами языкафункциональногопрограммирования(ЯФП)ибыстроотлаживается на базе систем ФП (СФП), приспособленных кинтерпретации программ.3. При необходимости выполняются формальные преобразованияпрограмм , (например, компиляция), обеспечивающие улучшениеэксплуатационных характеристик, связанных с процессамиисполнения программ.4. Важный критерий качества ФП — полнота системы функций иуниверсальностьопределений,дающаявозможностьсинтаксически управляемой обработки данных с помощьюфункций высших порядков (ФВП), что существенно повышаетнадежность программирования.5.
Разработка ИС средствами ФВП успешно выполняет рольпрототипа для реализации другими, более распространеннымисредствами.Оттолкнувшись от интуитивного представления о понятии "функция",мы для начала ограничились однозначными функциями , но разрешилипредельно широкое толкование понятия "значение", включающеепонятие "структура данных".1. Ориентируясь на рекурсивные определения функций , мы ввели231Л.В.
Городняя2.3.4.5.Основы функционального программированиянесложную схему, достаточно удобную для построения формул,задающих функциональные определения. При этом отмеченокачественное различие между элементарными функциями,задаваемыми неформально вне метаязыка, и остальнымифункциями, определяемыми формулами языка, использующимиобозначения элементарных функций. В качестве примерарассмотрен элементарный Лисп .Затем было конкретизировано основное множество значенийфункций как множество списков и атомов, на котором определеныалгебра и логика, достаточные для обработки и анализа такихзначений.
Представления функций отображены в это множество иопределена универсальная функция , по списочномупредставлению функции и ее аргументов строящая результат.Рассмотрены примеры структур данных, полезных приреализации списков, интерпретируемых как функции (стеки,пары, блоки, односвязные списки, расстановочные таблицы идр.).Изучено расширение функционального языка, достаточное дляимперативно- процедурного стиля программирования, чтообеспечивает помимо нисходящей методики разработки программи восходящую, более естественную для несложных задач.Определена абстрактная машина, содержащая реализациюэлементарных функций языка и поддерживающая интерпретациюфункционального языка, и проанализирован компилятор сабстрактногосинтаксисафункциональногоязыкапрограммирования на языково-ориентированную абстрактнуюмашину.Таким образом, завершена нисходящая линия определения языкафункционального программирования, позволяющая во всех деталяхпредставлять один возможный процесс применения функций на уровнеинтуитивных понятий, структур данных и машинного кода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
