globalf5-240972240972 (850810), страница 4
Текст из файла (страница 4)
ГородняяОсновы функционального программированиявариантов функциональных построений.Расхожее мнение о неэффективности Лиспа столь же убедительно, скольактуальное когда-то рассуждение о бесполезности интеллигентов,некачественно собирающих колхозную картошку. Как авиация несоревнуется с автотранспортом в объеме грузоперевозок, так ифункциональное программирование несравнимо со стандартнымипарадигмами в массовости применения, но это не умаляет егодостоинств.Столь же расхожее утверждение, что функциональный стильпрограммирования на Лиспе обеспечивает ясность программ, требуетпоправки, что больше для тех кто пишет, чем для тех, кто читает.
(Пристихийно-алгоритмическом стиле программист часто не ведает, что жеделает его программа — утрата единства замысла).Многие современные языки и технологии программированияунаследовали опыт реализации и применения Лиспа и других языковсимвольной обработки. Так, например, Java берет на вооружение идеинеполной компиляции и освобождения памяти, объектноориентированное программирование реализует объекты, весьмапохожие на списки свойств атомов Лиспа, хэш-таблицы языка Perlнапоминают применение ассоциативных списков Лиспа. Pythonобрабатывает программы с нетипизированными переменными.Лисповское наследие в информатике достойно отдельногорассмотрения.
Здесь мы сконцентрируемся на ключевой идее Лиспа —сведении понятия "программа" к взаимодействию разных категорийфункций. Базирующееся на таком сведении функциональноепрограммирование можно описать в терминах любого языка, но Лиспдает этой идее достаточно полное звучание и формирует некую шкалусравнения и определения стандартных конструкций и методовпрограммирования, а также упорядочение явлений, характерных дляэкспериментальной разработки программ и поиска новых областей ихприменения.18Л.В.
ГородняяОсновы функционального программированияЭлементарный ЛиспИзучается ключевой метод функционального программирования —выбор семантического базиса для класса решаемых задач на примереорганизации информационной обработки символьными выражениямив языке Лисп. Вводятся базовые понятия, достаточные для символьногопредставления программ. Формализм рекурсивных функций и простыеалгоритмы символьной обработки привлечены для обоснования идемонстрации функционального подхода к представлению программ.Анализируются требования к полноте и эффективности их обработки. Вкачестве исторической иллюстрации полномасштабного примененияфункционального программирования для решения достаточно сложнойзадачи используется символика языка Лисп, выбранная приорганизации символьной обработки для решения задач искусственногоинтеллекта.Основы символьной обработки.
Базовые средстваФункциональный стиль программирования сложился в практикерешения задач символьной обработки данных в предположении, чтолюбая информация для компьютерной обработки может быть сведена ксимвольной. (Существование аналоговых методов принципиально непротиворечит этой гипотезе.) Слово "символ" здесь близко понятию"знак" в знаковых системах. Информация представляется символами,смысл которых может быть восстановлен по заранее известнымправилам.Методы функционального программирования основаны на формальномматематическом языке представления и преобразования формул.Поэтому можно дать точное, достаточно полное описание основфункционального программирования и специфицировать системупрограммирования для поддержки и разработки разных парадигмпрограммирования, моделируемых с помощью функциональногоподхода к организации деятельности.Такое определение будет приведено в шестой лекции, а сейчаснеобходимо освоить технические приемы символьной обработки.
Вдальнейшем будут проиллюстрированы и практические способы19Л.В. ГородняяОсновы функционального программированияприменения функционального программирования, превращающие его вудобную технологию современного программирования.Функциональное программирование отличается от большинстваподходов к программированию тремя важными принципами:1) Природа данныхВсе данные представляются в форме символьных выражений. В ЛиспеДж. Маккарти назвал их S-выражениями.
Состав S-выражений и типыих элементов не ограничиваются, что позволяет их использовать какдревообразные структуры . Это позволяет локализовывать любыеважные подвыражения. Система программирования над такимиструктурами обычно использует для их хранения всю доступнуюпамять, поэтому программист освобожден от распределения памяти подотдельные блоки данных.2) Самоописание обработки символьных выраженийВажная особенность функционального программирования состоит втом, что описание способов обработки S-выражений представляетсяпрограммами, рассматриваемыми как символьные данные.
Программыстроятся из рекурсивных функций над S-выражениями. Определения ивызовы этих функций, как и любая информация, имеют вид Sвыражений, то есть формально они могут обрабатываться как обычныеданные, получаться в процессе вычислений и преобразовываться какзначения.3) Подобие машинным языкамСистема функционального программирования допускает, что программаможетинтерпретироватьи/иликомпилироватьпрограммы,представленные в виде S-выражений. Это сближает методыфункционального программирования с методами низкоуровнегопрограммирования и отличает от традиционной методики применения20Л.В.
ГородняяОсновы функционального программированияязыков высокого уровня.Не все языки функционального программирования в полной мередопускают эту возможность, но для Лиспа она весьма характерна. Впринципе, такая возможность достижима на любом стандартном языке,но так делать не принято.Наиболее очевидные следствия из выбранных принципов:процесс разработки программ разбивается на две фазы:построение базиса и его пошаговое расширение;рассмотрение программы как реализации алгоритма естественнодополняется табличной реализацией функций, т.е.
допустимоиспользование хранимых графиков функций в виде структур изаргументов и соответствующих результатов наряду с процедурами;прозрачность ссылок обеспечена совпадением значенийодинаково выглядящих формул, вычисляемых в одинаковомконтексте;нацеленность на универсальные функции и функциональнополные системы, трудоемкость первичной реализации которыхкомпенсируется надежностью определений и простотойприменения.Функциональное программирование активно применяется длягенерации программ и выполнения динамически конструируемыхпрототипов программ, а также для систем, применяемых в областях снизкой кратностью повторения отлаженных решений (например, вучебе, проектировании, творчестве и научных исследованиях),ориентированных на оперативные изменения, уточнения, улучшения,адаптацию и т.п.ДанныеЛюбые структурыданных начинаются с элементарных значений.Следуя Лиспу, в функциональном программировании такие значенияназывают атомами или символами.
Внешне атом обычно выглядит какпоследовательность из букв и цифр, начинающаяся с буквы. В первыхреализациях Лиспа было принято ограничивать длину атома, но21Л.В. ГородняяОсновы функционального программированияограничение было не слишком жестким (30 литер). Теперьограничивают лишь число значащих литер (порядка 60), по которыматомы распознаются как различимые объекты с помощью хэш-таблицыобъектов.AATOMВотВесьмаДлинныйАтомНоЕслиНадоТоАтомМожетБытьЕщеДлинннееФ4длш139к131бОдинаково выглядящие атомы не различимы по своим свойствам, хотяпроявления этих свойств могут быть обусловлены контекстомиспользования атомов. Термин "атом" выбран по аналогии схимическими атомами.
Согласно этой аналогии атом может иметьдостаточно сложное строение, но оно не рассматривается как обычноеS-выражение. Устройство атома реализационно зависимо и лишьсоответствует некоторой спецификации, содержание которой будетрассмотрено в девятой лекции. Атом не предназначен для разбора начасти базовыми средствами языка.Более сложные данные выстраиваются из унифицированных структурданных — одинаково устроенных блоков памяти.
В Лиспе это бинарныеузлы, содержащие пары объектов произвольного вида. Каждыйбинарный узел соответствует минимальному блоку памяти,выделяемому системой программирования при организации иобработке структур данных . Выделение блока памяти и размещение внем пары данных выполняет функция CONS (от слова consolidation), аизвлечение левой и правой частей из блока выполняют функции CAR иCDR,соответственно.(Вдругих языках функциональногопрограммированияиспользуютсявекторы,кортежи,последовательности, потоки, множества, сети и другие структурыданных, обладающие достаточной гибкостью, т.е.
способностью корганизации единого доступа к любому числу элементов произвольноготипа.)CONS =>> [CAR | CDR]Бинарный узел, содержащий пару атомоврассматривается как одноэлементный список:22ATOMиNIL,Л.В. ГородняяОсновы функционального программирования(ATOM) = [ ATOM | NIL ]Если вместо атомаATOM рекурсивно подставлять произвольныеатомы, а вместо NIL — произвольные списки, затем вместо ATOM —построенные списки и так далее, то мы получим множество всехвозможных списков.
АтомNIL играет роль пустого списка ифактически эквивалентен ему. Можно сказать, что список — этозаключенная в скобки последовательность из атомов, разделенныхпробелами, или списков .ATOM(A B)(A B C D E F G H I J K L M N O P R S T U V W X Y Z)(C (A B))((A B) C)((A B) (D C))((A B)(D(C E)))Такая форма представления информации называется списочнойзаписью (list-notation). Ее основные достоинства — лаконичность,удобство набора и отсутствие "синтаксического сахара". Она достаточноотражает взаимосвязи структур данных, размещаемых в памяти, ипомогает задавать процедуры доступа к их компонентам.Любой список может быть построен из пустого списка и атомов спомощью CONS, и любая его часть может быть выделена с помощьюподходящей композиции CAR-CDR.Функция CONS строит списки из бинарных узлов, заполняя их парамиобъектов, являющихся значениями пары ее аргументов.
Первыйаргумент произвольного вида размещается в левой части бинарногоузла, а второй, являющийся списком, — в правой.Функция CAR обеспечивает доступ к первому элементу списка — его"голове", а функция CDR — к укороченному на один элемент списку —его "хвосту", т.е. к тому, что остается после удаления головы.Функция ATOM позволяет различать составные и атомарные объекты: наатомах ее значение "истина", а на структурированных объектах —23Л.В. ГородняяОсновы функционального программирования"ложь".Функция EQ выполняет проверку атомарных объектов на равенство.Различие истинностных значений в Лиспе принято отождествлять сразницей между пустым списком и остальными объектами, которымпрограммист может придать в программе некоторый другой смысл.Таким образом, значение "ложь" — это всегда NIL. (Во многих языкахпрограммирования используется 0 – 1 или идентификаторы True —False и др.)Если требуется явно изобразить истинностное значение, то дляопределенности в качестве значения "истина" используется константа —атом T (true) как стандартное представление, но роль такого значенияможет выполнить любой, отличный от пустого списка, объект.Точечная нотацияИсторически при реализации Лиспа в качестве единой базовойструктуры для конструирования S-выражений использовалась такназываемая "точечная нотация" (dot-nоtation), согласно которой левая иправая части бинарного узла равноправны и могут хранить данныелюбой природы.Бинарный узел, содержащий пару атомовпредставить в виде S-выражения вида:ATOM1 и ATOM2, можно( ATOM1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
