Языки программирования. Практический сравнительный анализ
1. КОНЦЕПТУАЛЬНАЯ СХЕМА ЯЗЫКА ПРОГРАММИРОВАНИЯ.
1.1. Что такое язык программирования
Естественно начать с характеристики изучаемого предмета. Но коротко охарактеризовать, что именно будем изучать, с какой целью и как, не просто (скоро станет понятно, почему). Конечно, нас будут интересовать "языки программирования" (ЯП). На сколь точно эти слова определяют сферу наших интересов? Одни скажут, что язык машин Тьюринга или алгоритмов Маркова - это ЯП, другие не согласятся с этим категорически. Одни признают язык управления заданиями в ОС ЕС языком программирования, другие приведут доводы против.
Такая ситуация на первый взгляд неприятна - собираемся изучать неизвестно что. Сделаем вывод, что нужно определить объем понятия "язык программирования" (его экстенсионал, т.е. множество обьектов, охватываемых этим понятием, множество его частных случаев).
Чтобы создать себе первую точку опоры, пойдем по простейшему пути - явно перечислим те конкретные языки, которые нас заведомо интересуют (их мы уверенно считаем "языками программирования"). Это Фортран, Паскаль, Бейсик, Лисп, Апл, Форт, Рефал, Ада. Однако вряд ли стало намного легче. Хочется иметь возможность на основе определения предсказывать новые частные случаи, в определении не перечисленные. Такое определение должно опираться на существенные свойства выбираемых для изучения языков - оно должно быть интенсиональным. Дадим одно из возможных интенсиональных определений ЯП.
Язык программирования - это инструмент для планирования поведения исполнителя.
Однако остаются основания для неудовольствия. Во-первых, известные нам языки программирования (Фортран, Алгол, Бейсик) служат не только для планирования поведения (машин), но и для обмена программами между людьми. Такая важнейшая функция существенно влияет на их устройство и принципы создания (хотя она все-же вторична - можно показать, что люди должны понимать и читать программы, даже не имея никаких намерений ими обмениваться; просто иначе достаточно крупной программы не создать).
Эту функцию языка никак нельзя игнорировать при изучении ЯП.
Во-вторых, в нашем определении каждое слово нуждается в уточнении. Являются ли "инструментами для планирования поведения исполнителя" должностная инструкция, письменный стол, переговорное устройство, правила уличного движения, русский язык?
Но кое-чего мы добились - можем привести примеры ЯП, с которыми все согласны, и указать объекты, заведомо не являющиеся ЯП в соответствии с нашим определением (также рассчитывая на общее согласие) - левая тумба письменного стола, стойка питания БЭСМ-6, рубанок, автомобиль.
1.2. Метауровень
Взглянем на наши действия с позиции стороннего наблюдателя, отвлечемся (абстрагируемся) от своей роли соответственно автора и читателей на только что законченном начальном отрезке работы. Поднимемся, как говорят, на метауровень, с тем чтобы обозревать начальный отрезок (исходный уровень) в целом. Чем мы занимались?
Во-первых, приступили к изучению ЯП. Во-вторых, попытались добиться взаимопонимания (согласованного понимания) в вопросе о том, что такое ЯП. В-третьих, начали применять для достижения взаимопонимания метод последовательных уточнений.
Чего мы добилмсь и что осталось неясным? Стало яснее, что будем изучать. Почувствовали, что добиться взаимопонимания (даже по поводу привычных понятий) очень непросто. Осталось неясным , в частности, с какой позиции и с какой целью мы намерены изучать ЯП.
Постараемся в первом приближении устранить возможные неясности. Однако заниматься последовательными уточнениями многих важных понятий мы будем на протяжении всей нашей работы - ведь она не формальная, а содержательная, нас интересуют реально существующие, возникающие на наших глазах и развивающиеся объекты - живые языки программирования. Поэтому-то и невозможно дать исчерпывающего описания ЯП как понятия (это понятие живет вместе с нами).
Начнем с более внимательного рассмотрения преград, обычно возникающих на пути к взаимопониманию.
1.3. Модель передачи сообщения
Естественно, и результаты у них будут разные. Это семантическое недоразумение.
Наконец, автору трудно иногда представить себе, какую интерпретацию может придать его сообщению адресат, если у них сильно различаются представление о мире или решаемые задачи.
Например, сообщение лектора о предстоящем коллоквиуме может быть воспринято студентами как призыв не посещать малоинформативные лекции, чтобы иметь время для работы с книгами. Это уже прагматическое недоразумение.
Нетрудно привести и другие примеры синтаксических, семантических и прагматических недоразумений при попытке достичь взаимопонимания.
1.5. При чем здесь взаимопонимание
Почему же в самом начале речь пошла о взаимопонимании и о стоящих на пути к нему преградах? В основном, по двум причинам.
Во-первых, ЯП - это инструмент для достижения взаимопонимания (безопаснее "взаимопонимания") с компьютерами и между людьми по поводу управления компьютерами. Поэтому в принципах построения, структуре, понятиях и конструктах ЯП находит свое отражение и сущность общей проблемы взаимопонимания, и взгляды их творцов на эту проблему, и конкретные методы ее решения.
Во-вторых, способ, которым люди преодолевают преграды на пути к взаимопониманию, содержит некоторые существенные элементы, остающиеся важными и при общении с компьютерами (в частности, при создании и использовании ЯП).
1.6. Как достигают взаимопонимания
Особенно бояться синтаксических недоразумений не стоит. Они касаются отдельных неудачных фраз и легко устраняются немедленным вопросом (устным или письменным). В ЯП это тоже не проблема - таких недоразумений там просто не бывает. Дело в том, что создатели ЯП руководствуются принципом однозначности - язык программирования должен быть синтаксически однозначным (т.е. всякий правильный текст на ЯП должен иметь единственную допустимую структуру).
Замечание 1. Итак, сформулирован один из принципов построения ЯП, отличающих их, скажем, от языков естественных. Такого рода общие принципы и концепции нас и дальше будут интересовать в первую очередь.
Конец замечания.
Семантические недоразумения опаснее. Если, скажем, слово "язык" будет ассоциироваться с кулинарным субпродуктом, ставшим весьма редким гостем прилавка, то недоразумение может не ограничиться пределами одной фразы. Большой язык, свежий язык, красный язык, зеленый и голубой язык - все это может касаться и говяжьего языка и ЯП (в конкурсе языковых проектов, ставшем одним из этапов создания языка Ада, языки-конкуренты получили условные "цветные" наименования; победил "зеленый" язык).
Метод борьбы с семантическими недоразумениями при человеческом общении известен - нужно выделять важные понятия, давать им четкие определения, приводить характерные примеры. Это со стороны говорящего. Слушатели должны, в свою очередь, стараться уловить оставшиеся существенные неясности, приводить контрпримеры (объектов, соответствующих определениям, но повидимому не имевшихся в виду говорящим, и объектов, не соответствующих определениям, но, скорее всего, имевшихся в виду). Этот же метод точных определений широко используется в ЯП (вспомните определения процедур и функций в Алголе и Фортране, а также типов в Паскале), а примеры и контрпримеры применяются, как известно, при отладке программ.
1.7. Отступление об абстракции-конкретизации. Понятие модели
Добиваясь взаимопонимания, мы активно пользуемся аппаратом абстракции-конкретизации (обобщения-специализации).
Создавая понятие, отвлекаемся (абстрагируемся) от несущественных свойств тех конкретных объектов, на основе знания которых понятие создается, и фиксируем в понятии лишь свойства существенные, важные с точки зрения задачи, решаемой с применением этого понятия. Так, в понятии "часы" мы обычно фиксируем лишь свойство быть "устройством, показывающим время" и абстрагируемся от формы, структуры, цвета, материала, изготовителя и других атрибутов конкретных часов.
Приводя пример, мы конкретизируем (абстрактное) понятие, "снабжая" его второстепенными с точки зрения его сущности, но важными в конкретной ситуации деталями.
Так, конкретное выполнение процедуры происходит при конкретных значениях ее параметров; конкретный пример ЯП - скажем, Фортран - имеет конкретный синтаксис и конкретную семантику.
Мои часы большие, круглые, позолоченные, с тремя стрелками, марки "Восток", на 17 камнях. Все это немного говорит об их качестве в роли "устройства, показывающего время", но конкретное устройство всегда обладает подобными "лишними" с точки зрения его роли свойствами. Их существование лишь подчеркивает тот факт, что (абстрактное) понятие никогда не исчерпывает конкретного объекта - оно всегда отражает лишь некоторую точку зрения на этот объект, служит компонентой его модели, оказавшейся удобной для решения определенной задачи. В другой ситуации, при решении другой задачи, этот же конкретный объект может играть другую роль. Тогда и точка зрения на него может быть другой, и может потребоваться совсем другая модель того же самого объекта.
На "устройство, показывающее время", в известных условиях можно предпочесть смотреть как на "украшение" и с этой точки зрения (в этой его роли) важнее станут форма, цвет, размер, фирма, чем даже способность правильно показывать время. На процедуру можно смотреть как на "объект, расходующий машинные ресурсы". При такой ее роли совершенно неважно, каков смысл выполняемых в ней действий. На ЯП иногда приходится смотреть как на объект стандартизации, и тогда важно не столько то, каковы особенности его семантики и синтаксиса, сколько то, найдется ли достаточно много заинтересованных в его стандартизации людей и организаций.
Непроизвольная, а иногда и намеренная, но не подчеркнутая явно смена точки зрения, переход по существу к другой модели объекта мешает взаимопониманию, служит источником прагматических недоразумений. Вы говорите, что часы "плохие", потому что некрасивые, а я говорю "хорошие", так как отлично работают.
Способность без затруднений переходить от одной модели к другой, четко фиксировать и легко изменять уровень рассмотрения, а также угол зрения, отмечается обычно как важнейшее профессиональное качество программиста.
1.8. Синтактика, семантика, прагматика
Устранять прагматические недоразумения бывает особенно сложно, когда они связаны не только с различием точек зрения, но и целевых установок. Если правильно разложить фразу на составляющие может помочь согласование с контекстом, а правильно понять смысл слова или фразы может помочь знание их назначения (роли), то восстановить эту роль, догадаться о ней, если об этом не сказано явно, очень тяжело. Слишком велика неопределенность, свобода выбора.
Представим себе положение человека, которому излагается последовательность определений и не говорится, зачем они вводятся, для решения каких задач предназначены. Это хорошо знакомая всем ситуация - есть такой стиль изложения математических результатов. Слушатель (читатель) при этом лишен всякой опоры для контроля, кроме поиска чисто логических противоречий. Пока он не понял, зачем все это нужно, он готов пропустить любую содержательную ошибку. А попробуйте понять смысл программы, если неизвестно, для чего она написана!
Вывод очевиден - для достижения взаимопонимания необходимо, чтобы отправитель и адресат, во-первых, пользовались одинаковыми правилами разложения сообщения на составляющие (изучением таких правил занимается синтактика); во-вторых, согласованными правилами сопоставления сообщению смысла (такими правилами занимается семантика); и, в-третьих, имели согласованные целевые установки (это предмет прагматики).
Ролью всех перечисленных аспектов для создания и использования языков программирования мы еще займемся, а сейчас уместно поговорить об основной цели изложения (для согласования наших целевых установок).
1.9. Основная цель изложения
Мы намерены изложить основные принципы оценки, создания и использования современных ЯП. Это очень нужная, плодотворная и увлекательная, но далеко еще не устоявшаяся, быстро развивающаяся область. Поэтому нет возможности опираться на освященный традицией опыт предшественников, а также стабильные программы и учебники (как это бывает, скажем, при изучении математического анализа или дифференциальных уравнений).
Приходится рисковать и экспериментировать.
Итак, о нашей основной цели. Она состоит в том, чтобы постараться правильно ориентировать читателя в области ЯП, помочь ему осознать навыки и опыт, приобретенные при самостоятельной работе с конкретными ЯП.
Но не слишком ли опасна идея "правильно ориентировать? Ведь если, скажем, представления о профессиональных запросах читателя или о тенденциях развития ЯП окажутся ошибочными, то скорее всего "правильная" ориентация на самом деле окажется дезориентацией. Не лучше ли ограничиться изложением бесспорных положений из области ЯП - уж они-то понадобятся наверняка!?
К сожалению или к счастью, альтернативы у нас по сути нет. Абсолютно бесспорные положения касаются, как правило, лишь конкретных ЯП. Например, "Один из операторов в языке Алгол 60 - оператор присваивания. Устроен он так-то. Служит для того-то". В хорошо известном учебнике программирования это положение обобщено. Сказано так:"Фундаментальным действием в любом алгоритмическом языке является присваивание, которое изменяет значение некоторой переменной". И это уже неверно! Сейчас много внимания уделяется так называемому функциональному программированию, аппликативным ЯП, где присваивание не только не "фундаментальное" действие, но его вообще нет!
Значит, в области ЯП нет достаточно общих бесспорных положений? В некотором смысле есть. Чаще не столь бесспорных, сколь заслуживающих изучения. Правда, их общность - несколько другого характера. Примером может служить упоминавшийся принцип однозначности. Да и приведенная фраза из учебника - вполне бесспорное положение, если считать, что она характеризует определенный класс ЯП, в который не попадает, скажем, язык Лисп - один из самых "заслуженных", распространенных и в то же время перспективных. Итак, даже если ограничиться лишь относительно бесспорными положениями, их все равно нужно отбирать с определенных позиций, с определенной целью. Естественная цель - стремиться принести читателю максимальную пользу.
Опять мы приходим к "угадыванию" будущих потребностей.
1.10. Зачем могут понадобиться знания о ЯП
Во-первых, каждая программа должна общаться (обмениваться информацией) с внешним миром. Соглашения, определяющие способ общения - это язык, так что понимание принципов построения языков - необходимый компонент грамотного программирования. Исключительно важный компонент, как мы еще не раз увидим, потому что непосредственно связан с внешним эффектом программы, со способом ее использования. При разработке внешнего сопряжения своей программы программист обязан проявить истинный профессионализм, представляя пользователю максимум услуг при минимуме затрат. Особенно это важно при создании пакетов прикладных программ, инструментальных систем, вообще любых программных изделий, предназначенных для эксплуатации без участия автора.
Во-вторых, каждый язык - это своя философия, свой взгляд на деятельность программиста, отражение определенной технологии программирования. Даже представлений об Алголе, Фортране и Бейсике достаточно, чтобы почувствовать, что имеется в виду.
Скажем, творцы Алгола (выдающиеся представители международного сообщества ученых в области информатики под руководством Петера Наура) с естественным для них академизмом придавали относительно много значения строгости определения и изяществу языковых конструктов. Считалось, что самое важное в работе программиста - сформулировать алгоритм (и, возможно, опубликовать его). Переписать программу в расчете на конкретные устройства ввода-вывода считалось не заслуживающей особого внимания технической деятельностью. Не привлек должного внимания авторов языка и такой "технический" аспект программистской деятельности, как компоновка программ из модулей.
Творцы Фортрана (сотрудники фирмы ИБМ во главе с Джоном Бэкусом) в значительной степени пренебрегли строгостью и изяществом и со свойственным им в ту пору (1954-57гг.) прагматизмом уже в первых версиях языка уделили особое внимание вводу-выводу и модульности.
Но ни Фортран, ни Алгол не рассчитаны на работу в диалоговом режиме. В отличии, как вам известно, от Бейсика (созданного в Дартмундском колледже первоначально для обучения студентов).
Таким образом, изучение ЯП дает знание и понимание разнообразных подходов к программированию. Это полезно при любой программистской деятельности.
В-третьих, понимание общих принципов и концепций, определяющих строение и применение ЯП, позволяет легче и глубже освоить конкретный язык - основной профессиональный инструмент программиста.
В-четвертых, и это хотелось бы подчеркнуть особо, понятия и тенденции в области ЯП с некоторым запаздыванием (в целом полезным), довольно точно отражают понятия и тенденции собственно программирования как науки (и области человеческой деятельности). В этом смысле мы повторяем и закрепляем основные принципы и понятия программирования, но с несколько иной точки зрения.
Все, о чем было сказано до сих пор, касалось интересов потенциального пользователя ЯП. Но читатель может оказаться и руководителем коллектива, которому требуется оценивать и выбирать язык для выполнения конкретного проекта (учитывать, скажем, затраты на освоение этого языка или на обмен написанными на нем программными изделиями).
Если же он станет творцом языка, создателем транслятора или руководства для пользователей, то ему понадобятся столь разнообразные знания о ЯП, что их придется извлекать целеустремленным изучением специальной литературы. Можно надеяться дать лишь первоначальный импульс в нужном направлении.
Конечно, предсказать, для чего именно понадобятся приобретенные знания - сложно. Могут напрямую и вовсе не понадобиться. Но наверняка пригодится приобретенная обсуждениями, размышлениями и упражнениями культура работы со сложными объектами при решении сложных задач. В нашем случае - это такие задачи, как ОЦЕНКА, ИСПОЛЬЗОВАНИЕ, РАЗРАБОТКА И РЕАЛИЗАЦИЯ языков программирования.
Было бы неправильно ставить нашей целью научить свободному владению конкретными языками, пусть даже такими привлекательными или перспективными, как Бейсик, Паскаль или Ада.
Для этого служат специальные учебники, упражнения и, главное, практика.
Наша задача - познакомить с важнейшими понятиями и концепциями, помогающими оценивать, использовать, реализовывать и разрабатывать ЯП, дать представление о направлениях и проблемах их развития. Поэтому займемся, в основном, изучением моделей языков программирования и основных принципов их оценки, использования, реализации и разработки. Наиболее важные по тем или иным причинам языки или их конструкты иногда будут рассматриваться довольно подробно, но прежде всего лишь как примеры, иллюстрирующие более общие положения.
Например, будет важно понимать, что с каждым ЯП связан эталонный (абстрактный) исполнитель, в котором в свою очередь определены данные, операции, связывание, именование, аппарат прогнозирования и контроля, возможно исключений, синхронизации И защиты. Важно понимать перечисленные термины, понимать назначение соотвествующих языковых конструктов и уметь ими пользоваться при решении практических задач. Но не очень важно помнить наизусть все связанные с ними тонкости в конкретных языках. Последнее может оказаться важным лишь тогда, когда тонкости иллюстрируют ключевые концепции рассматриваемого ЯП. Например, жесткие правила выбора обозначений в Бейсике непосредственно связаны с его ориентацией на относительно небольшие программы и простоту реализации.
1.11. Пять основных позиций при рассмотрении ЯП
Итак, будем считать, что целевые установки согласованы в достаточной степени, чтобы сделать следующий шаг - приступить к систематическому изучению нашего предмета.
И сразу вопрос - с чего начать? Легко сказать "систематическому". Но ведь системы бывают разные. Часто начинают "снизу" - с основных конструктов, встречающихся почти во всех существующих ЯП. Тогда мы сразу погружаемся в мир переменных, констант, параметров, процедур, циклов и т.п. Такой путь привлекателен хотя бы тем, что им сравнительно легко пойти. Но на этом пути за деревьями обычно не видно леса, не удается увидеть язык "в целом", построить его адекватную модель.
Это резко увеличивает число объектов, с которыми приходится иметь дело при создании программ. Отсюда повышение сложности программирования, увеличение размера программ, понижение их надежности и робастности.
Второй источник сложности, в отличие от первого, есть надежда победить (или хотя бы существенно ослабить) за счет развития методов представления в компьютерах знаний о реальном мире и эффективном учете этих знаний при создании и исполнении программ.
1.16. Два основных средства борьбы со сложностью
Рассмотренные источники сложности оказывают определяющее влияние на теорию и практику в области ЯП. Важнейшим средством борьбы с первым из них служит аппарат абстракции-конкретизации. Он обеспечивает базу для проблемной ориентации языковых выразительных средств.
Например, в Фортране характерным средством абстракции служит подпрограмма, а соответствующим средством конкретизации - обращение к ней с фактическими параметрами. Важнейшим средством борьбы со вторым источником сложности служит аппарат прогнозирования-контроля. Он обеспечивает базу для повышения надежности и робастности программ.
Например, в Фортране характерным средством прогнозирования служит объявление типа, соответствующий контроль предусмотрен семантикой языка, но средств управления таким контролем в языке нет.
Упражнение. Приведите известные вам примеры средств абстракции-конкретизации и прогнозирования-контроля. Постарайтесь подобрать симметричные, взаимнодополнительные средства. Убедитесь, что в известных вам ЯП эта дополнительность обеспечена не всегда.
Теперь мы в состоянии сформулировать следующий основной критерий качества ЯП (как инструмента для планирования поведения исполнителя): язык тем лучше, чем более он способствует СНИЖЕНИЮ СЛОЖНОСТИ производства программных услуг.
Удовлетворимся временно этим результатом разработки технологической позиции и уделим теперь немного внимания семиотической позиции.
1.17. Язык программирования как знаковая система
Продолжим уточнение понятия "язык программирования".
Наше новое интенсиональное определение таково:
Язык программирования - это знаковая система для планирования поведения компьютеров.
Итак, не любой "инструмент", а "знаковая система" и не для планирования произвольных "исполнителей", а только из класса ЭВМ (или "компьютеров"). К ограничению класса исполнителей в этом определении мы подготовились заранее, а вот о знаковых системах еще подробно не говорили.
Знаковая система - это совокупность соглашений (явных или неявных), определяющих класс знаковых ситуаций.
Понятие знаковой ситуации в семиотике относят к первичным понятиям, представление о которых создают с помощью примеров, а не явных определений. Необходимые компоненты знаковой ситуации - знак и денотат. Говорят, что знак обозначает денотат (знак называют также обозначением или именем, а денотат - обозначаемым или значением). Так, в модели передачи сообщения само сообщение служит знаком, его смысл - денотатом.
Вот еще знаковые ситуации (первым укажем знак, вторым - денотат): буква и соответствующий звук, дорожный знак ("кирпич") и соответствующее ограничение ("въезд запрещен"), слово и соответствующее ему понятие. Каждый без затруднений пополнит этот список.
Когла класс знаковых ситуаций определяется совокупностью соглашений (правил), устанавливающих закономерную связь между структурой знака и его денотатом, говорят, что эти соглашения образуют знаковую систему (или язык). При этом правила, определяющие структуру допустимых знаков, называются синтаксисом языка, а правила, определяющие соответствующие допустимым знакам денотаты, называются семантикой языка. (Науку о синтаксисах языков называют синтактикой, а слово "семантика" используется как для обозначения конкретных правил некоторого языка, так и для обозначения общей науки о таких правилах).
Одним из примеров знаковой системы служит позиционная система счисления (скажем, десятичная). Правила, определяющие перечень допустимых цифр и их допустимое расположение (скажем, справа налево без разделителей) - это синтаксис.
Правила вычисления обозначаемого числа - семантика. При этом запись числа в позиционной системе - знак, а само обозначаемое число - денотат. Известные вам ЯП - также знаковые системы.
Упражнение. Приведите пример синтаксического и семантического правила из таких знаковых систем, как Фортран, Бейсик, Ассемблер.
В общем случае в ЯП знаки - это элементы программ (в том числе полные программы), а денотаты - элементы и свойства поведения исполнителя (атрибуты его поведения), в частности, данные, операции, управление, их структура, их связи и атрибуты. Например, знаку, составленному из шести букв "arctan" (элементу программы на Фортране), использованному в этой программе в подходящем контексте, соответствует в качестве денотата такой элемент поведения исполнителя, как операция вычисления арктангенса.
Знаку, составленному из пяти букв "begin" (элементу программы на Алголе) в одном контексте в качестве денотата может соответствовать такой элемент поведения, как вход в блок, а в другом - переменная вещественного типа, в третьем - массив целого типа.
Упражнение. Выпишите подходящие контексты.
Итак, знаковая система - это правила образования знаков (синтаксис) и согласованные с ними правила образования денотатов (семантика). Подчеркнем, что правила использования денотатов для целей, выходящих за рамки семантики (т.е. прагматика) обычно не включаются в знаковую систему. Например, в Фортране нет каких-либо правил, ограничивающих применение соответствующих вычислительных процессов для неблаговидных целей.
Теперь уточненное определение ЯП как знаковой системы для планирования поведения компьютеров должно быть полностью понятным.
1.18. Разновидности программирования
Чтобы создать себе более удобную основу для формирования оценок, принципов и требований, примем соглашения, сужающие область наших рассмотрений.
Во-первых, программировать можно с различной целью. Скажем, для развлечения и обучения (игровое программирование); для отработки идей, приемов, инструментов, методов, критериев, моделей (экспериментальное программирование, его характерное свойство - созданная программа не предназначена для применения без участия автора, т.е.
результат такого программирования неотчуждаем).
В дальнейшем будем рассматривать только индустриальное программирование, цель которого - создание программных изделий (программных продуктов) на заказ или на продажу. Характерное свойство - отчуждаемость результата.
Во-вторых, может быть различным характер использования заготовок программ. По этому критерию различают по крайней мере три разновидности программирования:
сборочное - программа составляется из заранее заготовленных модулей (так обычно сейчас работают пакеты прикладных программ);
конкретизирующее - программа получается в результате преобразования универсальных модулей-заготовок (в результате специализации) в расчете на конкретные условия применения; цель специализации - повышение эффективности (снижение ресурсоемкости) универсальной программы;
синтезирующее - роль заготовок относительно невелика.
В дальнейшем нас, как правило, будет интересовать лишь синтезирующее индустриальное программирование.
В-третьих, стадии жизненного цикла программного изделия предъявляют различные, иногда противоречивые, требования к ЯП. Выделим стадии проектирования, эксплуатации и сопровождения. В первую очередь будем интересоваться стадией проектирования изделия, так как на ней в той или иной форме следует учитывать и требования всех остальных стадий жизненного цикла.
Можно надеяться, что вдумчивый читатель сможет применить полученные навыки анализа ЯП и при иных исходных соглашениях.
1.19. Понятие о базовом языке
Выделенные нами два источника сложности в программировании полезно трактовать как два различных аспекта единого источника - рассогласования моделей проблемной области (области услуг, задач, операций, сокращенно - ПО) у пользователей и исполнителей.
При таком взгляде создаваемая программа выступает как средство согласования этих моделей. Чем ближе исходные модели, тем проще программа. При идеальном исходном согласовании программа вырождается в прямое указание на одну из заранее заготовленных услуг (например, "распечатать файл", "взять производную", "выдать железнодорожный билет").
Но мы уже говорили об исключительном разнообразии моделей даже одного-единственного объекта, рассматриваемого с различных точек зрения. Поэтому невозможно построить исполнитель, непосредственно пригодный для выполнения любой услуги. Однако можно ориентировать его на фиксированный класс услуг. Для управления такими специализированными исполнителями строятся проблемно-ориентированные языки программирования (ПОЯ). В качестве хорошо известного примера годится, скажем, язык управления заданиями в операционной системе.
Итак, ПОЯ опирается на определенную модель соответствующей ПО (иногда говорят, что эта модель встроена в такой язык; точнее говоря, ПОЯ - это знаковая система, для которой модель соответствующей ПО служит областью денотатов).
Мы установили, что безнадежно строить язык с моделями, заготовленными "на все случаи жизни". Однако можно попытаться построить язык, на базе которого будет удобно (относительно несложно, с приемлемыми затратами) строить модели весьма разнообразных ПО. Такой язык называют базовым языком программирования.
Обычная схема применения базового языка в определенной ПО состоит из двух этапов. На первом (инструментальном) создается модель ПО и соотвествующий ПОЯ (их создают с помощью базового языка программисты-конструкторы). На втором (функциональном) этапе программисты-пользователи решают прикладные задачи, пользуясь созданным ПОЯ.
Итак, базовый ЯП - это по существу ПОЯ, предназначенный для построения моделей других ПО и соответствующих ПОЯ. Нас будут интересовать в первую очередь именно базовые языки, в особенности базовые языки индустриального программирования.
1.20. Концептуальная схема рассмотрения ЯП
Завершая подготовку к систематическому изучению ряда моделей ЯП, зафиксируем единую схему их рассмотрения. Эта схема поможет сопоставить и оценить различные ЯП прежде всего с точки зрения их пригодности служить базовым языком индустриального программирования.
Если бы нас интересовала, скажем, оценка языков с точки зрения легкости их усвоения начинающими программистами, мы предложили бы, конечно, другую схему их рассмотрения, начав с выявления основных идей и проблем обучения, наиболее подходящих средств решения этих проблем и т.д., подобно нашему пути к базовому языку.
Тем самым, предлагаемую ниже схему нужно воспринимать и как демонстрацию существенного элемента систематического метода сравнительной оценки языков. (Конечно, наша учебная схема намного проще той, которую следовало бы строить при практическом решении вопроса о пригодности конкретного языка служить базовым языком индустриального программирования.)
Главное назначение базового языка - строить модели ПО с тем, чтобы уменьшить сложность программирования в них. В качестве основных средств понижения сложности мы выделили абстракцию-конкретизацию и прогнозирование-контроль.
Первый будем кратко называть аппаратом развития (так как по существу он служит для построения над исходным языком новой знаковой системы, денотатами в которой выступают введенные абстракции и их конкретизации).
Второй будем называть также аппаратом защиты (так как он используется, в частности, для защиты построенных абстракций от разрушения).
Исключительная технологическая роль названных средств дает основание уделить им особое внимание в предлагаемой ниже единой концептуальной схеме рассмотрения ЯП.
Опишем первую версию единой схемы. При необходимости она будет корректироваться и уточняться.
В каждом ЯП нас будет интересовать пять аспектов: базис, развитие, защита, исполнитель, архитектура. Охарактеризуем каждый из этих аспектов.
Базис ЯП - это, во-первых, так называемая скалярная сигнатура (т.е. элементарные типы данных и элементарные операции) и, во-вторых, структурная сигнатура (т.е. допустимые структуры данных и операций; другими словами, структуры памяти и управляющие структуры).
Об аппарате развития языка (абстракции-конкретизации) уже сказано. Добавим лишь, что будем различать развитие вверх - аппарат определения и использования новых абстракций, и развитие вниз - уточнение и переопределение компонент базиса.
Об аппарате защиты также сказано. Имеется в виду прогнозирование (объявление) свойств поведения объектов (принадлежности к определенному типу, указание области действия, указание ограничений на допустимые значения в определенных контекстах) и контроль за соблюдением ограничений (в частности, управление реакцией на нарушение объявленного поведения).
Характеризуя исполнитель, будем говорить об основных его ресурсах, позволяющих хранить и выполнять программы (не о типах данных и операций, как в базисе, а о конкретных индивидуальных устройствах: разновидностях памяти, процессоров, обмена с внешней средой и т.п.).
Наиболее "капризный" из выделенных аспектов - "архитектура". Здесь критерии весьма расплывчаты. Тем не менее постараемся оценивать общее строение языка с точки зрения таких архитектурных понятий, как концептуальная целостность (возможность предсказать одни решения авторов языка по другим, т.е. увязанность, согласованность решений), модульность, ортогональность (возможность свободно комбинировать небольшое число относительно независимых фундаментальных понятий) и другим, знакомство с которыми нам еще предстоит.
В заключение подчеркнем, что пока в нашей схеме - только внутренние аспекты ЯП как знаковой системы. Совершенно не затронуты такие важнейшие для выбора и оценки языка аспекты, как распространенность на различных типах компьютеров, наличие высококачественных реализаций, уровень их совместимости и т.п.
Следующий раздел начнем с применения нашей схемы к трем моделям ЯП - модели Неймана, модифицированной модели Маркова и модели Бэкуса.
2. ТРИ МОДЕЛИ ЯЗЫКА
Стремясь дать представление о разнообразии подходов к практическому программированию и одновременно подтвердить дееспособность концептуальной схемы, применим ее к трем конкретным моделям ЯП. Первая модель отражает свойства первых ЭВМ, вторая восходит к нормальным алгоритмам Маркова. Вместе с тем это модели вполне реальных языков практического программирования. Третья модель, с одной стороны, опирается на такую почтенную форму планирования, как алгебраическая формула (выражение), а с другой стороны, ориентирует на такие современные области исследований и разработок, как функциональное программирование и алгебра программ.
2.1. Модель фон-Неймана (модель Н)
Рассмотрим модель, отражающую свойства первых ЭВМ - модель весьма примитивную, но способную послужить для нас своеобразным "началом координат", создать исходную точку отсчета.
2.1.1. Базис.
Два скалярных типа данных: адреса и значения. Конечный набор базисных скалярных операций (система команд): присваивание, условные операции, останов и другие. Единственная структура данных - кортеж ячеек (т.е. пар адрес -> значение) с линейно упорядоченными адресами (память). Никакой явной структуры операций - каждая операция сама определяет своего преемника. Есть выделенная ячейка C (регистр команд), в которой хранится адрес подлежащей выполнению команды.
2.1.2. Развитие
Никаких выделенных явно средств развития - все они скрыты в универсальности набора операций, среди которых ключевую роль играет оператор присваивания ячейке нового значения и зависимость выбора преемника от состояния памяти. Любое развитие возможно только путем явного моделирования новых операций за счет универсальности системы команд. Что такое значение - не уточняем. Достаточно считать, что это целые и строки литер (для выделенных ячеек ввода-вывода).
2.1.3. Защита
Полностью отсутствует.
2.1.4. Исполнитель
Память - базисная структура данных (кортеж ячеек), процессор - устройство, последовательно выполняющее указанные (в С) операции, поведение - последовательность состояний памяти, план (программа) - исходное состояние (или его выделенная часть), результат - заключительное состояние (если оно есть; при этом содержательно результатом обычно служит лишь выделенная часть заключительного состояния).
Указанные "части" для каждой программы свои. Так что в общем случае программа формально не отличается от исходных данных и результатов - одни и те же ячейки исполнитель может интерпретировать либо как содержащие команды, либо как содержащие данные. Все дело в том, в какой роли адреса ячеек используются в исполняемых командах.
2.1.5. Знаки и денотаты в модели Н
Сведения о базисе можно выразить с помощью следующих обозначений.
Пусть А - тип данных "адрес" (т.е. множество адресов в модели Н), V - тип данных "значение" (т.е.
множество содержимых ячеек с адресами из А). Тогда конкретное состояние памяти можно представить функцией s типа
S:A->V
т.е. конкретным отображением адресов в значения.
Тип функции "состояние" выражает первый принцип фон-Неймана - принцип произвольного доступа к памяти (в конкретном состоянии s из S равнодоступны все ячейки).
Операции (операторы) в модели фон-Неймана - это объекты типа
St:S->S.
Кроме того, модель фон-Неймана характеризуется функцией декодирования операций (частично-определенной)
d:V->Com,
где Com - команды т.е. операции, встроенные (элементарные) в Н.
В этих обозначениях второй принцип фон-Неймана - принцип хранимой программы отражается формулой
(А с из Com)(E v из V):d(v) = с ,
где A обозначает "для всех", а E - "существует". Т.е. всякую команду можно записать в память (найдется способ ее закодировать).
[Фактически здесь использованы элементы некоторого языка для описания семантики ЯП - семантического метаязыка. Язык для описания синтаксиса ЯП знаком из курса программирования. Таким синтаксическим метаязыком служит, например, БНФ (форма Бэкуса-Наура).]
2.1.6. Основное семантическое соотношение в модели Н.
(денотационная семантика)
Каков же денотат программы s в модели Н? Другими словами, какова та функция, которую реализует (обозначает) программа s?
Рассмотрим функцию r типа St
r:S->S
которая обозначает результат выполнения программы s, т.е. r(s) - это состояние s1, в котором выполняется операция остановки ("stop"). Оно не всегда достигается, т.е. функция r - частично-определенная - ведь, во-первых, не всякое состояние может служить программой и, во-вторых, не всякая программа завершает работу.
Другими словами, если C - регистр команды, то
d(s1(s1(C))) = stop.
(такому семантическому соотношению удовлетворяет заключительное состояние s1).
Обозначим через k=d*s*s композицию функций d,s,s.
Тогда основное семантическое соотношение, определяющее денотат r(s) программы s в модели Н, записывается так:
r(s)=если k(С)=stop, то s, иначе r(k(C)(s)).
Другими словами, нужно выполнить над состоянием s операцию, получающуюся декодированием содержимого ячейки с адресом, взятым из C, и вычислить функцию r от полученного нового состояния, пока не окажется, что нужно выполнить операцию stop.
Что можно извлечь из формулы для r?
Во-первых, то, что один шаг выполнения программы требует, в общем случае, трех обращений к памяти (в нашей модели регистр команд - в основной памяти), ведь переход к новому состоянию описывается как d(s(s(С)))(s).
Во-вторых, становится очевиднее, что средства развития в модели Н не выделены - денотат программы разлагается лишь на очень мелкие части - денотаты отдельных команд (выраженные, кстати, функцией k). Отсутствуют средства для явного обозначения композиций функции k, т.е. для явного укрупнения денотатов.
Пусть P = {p} - множество программ, R = {r} - множество функций типа S->S. Функциональной или "денотационной" семантикой программ называют функцию типа P->R, отображающую программу (т.е. исходное состояние p) в соответствующую ей функцию (оператор) r, удовлетворящую основному семантическому соотношению.
Название "денотационная" возникло исторически. Всякая семантика денотационная в том смысле, что сопоставляет знаку (программе) некоторый ее денотат (смысл).
Обратите внимание, сколь концептуально сложной оказалась знаковая система Н. Во всяком случае, нам потребовались так называемые функции высших порядков (т.е. функции, среди аргументов и (или) результатов которых встречаются снова функции). Действительно, посмотрите на перечень примененных функций:
s: A --> V
St: S --> S
d: V --> Com
r: S --> S
sem: P --> R
очевидно, что операция - функция высшего порядка, отображающая состояния (функции из адресов в значения); декодирующая функция - также высшего порядка; семантическая функция - также высшего порядка по отношению к функциям p и r (первая из них отображает адреса в значения, вторая - исходное состояние в заключительное).
2.1.7. Архитектура
Архитектура модели Н сильно зависит от конкретного набора команд. Может быть весьма изящной, как, например, архитектура команд машин серии ЕС или Сетуни.
Примеры программ в модели Н в достаточном числе содержатся в любом учебнике по программированию.
2.2. Модифицированная модель Маркова (модель М)
Модель Н возникла как обобщение такого поведения, когда после предыдущего действия ясно, какое должно быть следующим (команда сама устанавливает следующую). Такое поведение типично для рутинных вычислений, на автоматизацию которых ориентировались первые компьютеры (они были предназначены, как известно, для расчетов, связанных с созданием атомной бомбы).
Расчеты такого рода характеризуются данными относительно простой структуры - программы имеют дело с числами. Вся сложность поведения исполнителя определяется сложностью плана (т.е. числом и связями указанных в нем действий). Управление последовательностью действий зависит от сравнения простых данных. Еще Джон фон-Нейман хорошо понимал, что для других классов применений могут потребоваться компьютеры, характеризующиеся другим типом поведения.
2.2.1. Перевод в польскую инверсную запись (ПОЛИЗ)
Рассмотрим, например, задачу перевода арифметической формулы в постфиксную форму. Другими словами, исходными данными для нашей программы должны быть обычные арифметические формулы, а в результате нужно получить их запись в ПОЛИЗе. Например,
(a+b)*(c+d) --> ab + cd + *.
Мы уже говорили о том, что данные ко всякой программе записываются на некотором языке (являются знаками в некоторой знаковой системе). Чтобы их обработать, нужно воспользоваться правилами построения знаков в этой системе (синтаксисом языка) для распознавания структуры знака, затем воспользоваться семантикой знаковой системы, чтобы связать со структурой знака его смысл (денотат) и обработать данное в соответствии с его смыслом.
Пусть синтаксис языка формул, которые мы хотим обрабатывать, задают следующие правила БНФ:
Числа и переменные точно определять не будем, оставляя представление о них на интуитивном уровне (23 и 305 - числа, x, y, a, b, АЛЬФА - переменные).
Тогда 23 - формула (первичная, произведение, сумма), a+b*23 - также формула (сумма), (a+b)*23 - также формула (произведение); (a+*b) - не формула.
Семантика формул - общепринятая. Смыслом (денотатом) формулы будем считать число, получающееся из чисел, входящих в формулу, применением указанных операций в общепринятом порядке. Задача состоит в том, чтобы получить перевод в ПОЛИЗ, сохраняющий денотат (т.е. в данном случае - над теми же числами нужно выполнить те же операции и в том же порядке).
Другими словами, было бы идеально, если бы вся программа записывалась фразой примерно такого вида:
перевод(<формула1><операция><формула2>) =
перевод(<формула1>)
перевод(<формула2>)
<операция>
Можно заметить, что перевод текста с языка формул четко распадается на действия двух сортов - на распознавание компонент структуры исходной формулы и на компоновку ее образа в ПОЛИЗЕ из результатов перевода выделенных компонент. Когда действия этих сортов переплетены некоторым нерегулярным способом, то планировать, понимать, выполнять и проверять сложно. Чтобы уменьшить сложность, полезно выделить две ключевых абстракции (два понятия): анализ исходной структуры и синтез результирующей структуры, и предложить знаковую систему для их взаимосвязанной конкретизации в рамках единой программы.
Тут уместно вспомнить язык нормальных алгоритмов Маркова (для единообразия назовем этот язык моделью Маркова).
Охарактеризуем эту модель с точки зрения нашей концептуальной схемы.
Базис: единственный скалярный тип данных - литера; единственная базисная операция - поиск-подстановка; единственная структура данных - строка (текст); единственная структура операций - цикл по подстановкам.
Развитие: Явных средств нет. Только моделированием.
Дальнейший анализ модели можно предложить в качестве упражнения.
В модели Маркова анализ структуры встроен в исполнитель и управляется левой частью подстановки. Синтез структуры отделен от анализа - он управляется правой частью подстановки. Исполнитель распознает тривиальную структуру (слово), указанную слева, и заменяет ее столь же тривиальной структурой (словом), указанной справа.
С точки зрения нашей задачи эта модель недостаточно развита. Дело в том, что вид распознаваемых структур слишком тривиален. Хотелсь бы приблизить средства описания вида структур, скажем, к БНФ. Шаги в нужном направлении сделаны в языке, созданном в ИПМ АН СССР в 1966-68 г.г. и получившем название "рефал" (рекурсивных функций алгоритмический язык). В его основу положены следующие три модификации модели Маркова.
2.2.2. Три основные модификации модели Маркова (введение в рефал)
Мы изложим модель М языка программирования, особенно интересного с точки зрения нашей концептуальной схемы потому, что он был задуман и реально используется как средство для эффективного определения других языков (другими словами, в него заложены достаточно мощные средства развития).
Первая модификация состоит в том, что в качестве (по-прежнему единственной) базисной структуры данных вместо произвольной строки (слова) используется так называемое "выражение" - строка, сбалансированная по скобкам.
Вторая модификация касается подстановки. Ее левая часть должна быть так называемым функциональным термом с возможными переменными. Правая часть должна быть выражением, в котором можно использовать переменные из левой части подстановки (и только их).
Третья модификация касается поиска применимой подстановки.
В отличие от модели Маркова, где заранее не фиксируется заменяемая часть обрабатываемого слова, в рефале заменяемая часть обрабатываемого выражения фиксируется перед поиском применимой подстановки - это всегда так называемый ведущий функциональный терм. Применимой считается подстановка с минимальным номером, левая часть которой согласуется с ведущим термом. Другими словами, применима такая подстановка, в левой части которой указан общий вид структуры (образец), частным случаем которой оказался ведущий терм.
Займемся теперь каждой из модификаций подробнее. Нам нужно уточнить смысл слов "выражение", "ведущий функциональный терм", "переменная" и "согласуется".
2.2.2.1. Строение выражений; поле зрения
Выделено три типа скобок - так называемые символьные (открывающая ` и закрывающая ' кавычки), структурные (обычные круглые скобки) и функциональные (мы будем использовать фигурные скобки "{" и "}" ).
Выражением называется всякая последовательность литер, сбалансированная по всем трем типам скобок; термом - выражение в скобках либо совсем без скобок; символом - отдельная литера либо последовательность литер в символьных скобках.
Например,
(a+b) - выражение - структурный терм;
{a+b (c `АЛЬФА')} - выражение - функциональный терм;
`АЛЬФА' - символ, терм, выражение;
}ab{ - не выражение.
По существу, выражение - это линейное представление дерева - структура этого вида часто используются в программировании именно потому, что наглядно воплощает идею иерархии, частичного порядка, пошаговой (последовательной) декомпозиции.
Дерево - это ориентированный граф (орграф) без циклов, в котором выделена вершина, называемая корнем дерева, и в каждую вершину, кроме корня, входит ровно одна дуга, причем из корня доступны все вершины. В дереве легко вводятся уровни иерархии (по длине пути из корня).
Так, выражение {a+b(c `АЛЬФА' )} может быть представлено деревом вида
{ } 0-уровень
/ \
a + b ( ) 1-уровень
/ \
c ` ' 2-уровень
/ \
А Л Ь Ф А 3-уровень
Рис. 2.1
Ведущим (функциональным) термом называется самый левый функциональный терм, не содержащий других функциональных термов. В примерах ниже ведущие термы выделены.
(a+b{c+d}); { АЛЬФА (a*b)}{cd}x10
(100 DO 3 {I={1}(,3)}).
Таким образом, мы полностью описали допустимую структуру поля зрения рефал-исполнителя (рефал-машины). В этом поле помещается обрабатываемый объект, который может быть только выражением. В качестве очередной заменяемой части всегда выбирается ведущий терм. Если такового нет, то считается, что делать исполнителю нечего, и он останавливается.
Выражение, оставшееся в поле зрения, считается результатом выполнения программы, находящейся в поле определений исполнителя.
[В авторской терминологии это поле называется "поле памяти". Так говорить нам неудобно. В модели Н и программа, и данные находились в памяти. Естественно считать, что поле зрения рефал-машины - также часть памяти. Термин "поле определений" лучше отражает суть дела.]
2.2.2.2. Поле определений; рефал-предложения
[Мы изучаем модели ЯП. Поэтому будем позволять себе "вариации на тему" рассматриваемого языка-прототипа, когда такие вариации упрощают рассмотрение. Следовательно, сведения о конкретном языке не следует воспринимать как руководство по программированию на нем.
Например, говоря о рефал-предложениях, мы не будем строго следовать их авторской трактовке.]
В нормальном алгоритме Маркова средства описания правил анализа и синтеза бедны - можно лишь явно выписывать заменяемое и заменяющее подслова (левую и правую части марковской формулы соответственно).
Основная идея обобщения марковской формулы состоит в том, чтобы за счет введения локальных переменных наглядно изображать одной (обобщенной) формулой сразу целый класс подстановок (применимых к функциональным термам определенной структуры).
Ключевыми понятиями при этом служат интерпретация переменных и согласование (терма с обобщенной подстановкой при определенной интерпретации ее переменных).
Интерпретация переменных - это функция типа I:N->V, где N - множество обозначений переменных, V - множество их допустимых значений.
[Интерпретация напоминает состояние в модели Н. Только вместо адресов - обозначения переменных. Это по сути одно и то же. Но называем мы их по-разному, так как они играют разные роли. Состояние в модели Н - глобальный объект, сохраняющийся между последовательными операциями, а интерпретация в модели М - локальный объект, действующий внутри операции подстановки.]
При конкретной интерпретации переменных обобщенная подстановка (в рефале ее называют предложением или рефал-предложением) изображает конкретную марковскую формулу подстановки.
Например, предложение
{10 e 00 s 1} -> s 101 e
где е и s - (локальные) переменные, при интерпретации
i1={e->00, s->11}
(здесь фигурные скобки - обозначение множества пар, составляющих интерпретацию) изображает марковскую формулу
{100000111}-->1110100 ,
а при интерпретации
i2={e->ABC,s->D}
- изображает марковскую формулу
{10ABC00D1}-->D101ABC.
Соответственно левая часть предложения изображает левую часть марковской формулы, а правая часть предложения - правую часть формулы.
Согласование - это тройка (t,i,s), где t - ведущий терм, s - предложение и i - интерпретация, при которой левая часть s изображает t.
Итак, за счет различных интерпретаций переменных одна обобщенная марковская подстановка (предложение) способна изображать целый класс марковских подстановок (что и требовалось).
Однако этот класс не должен быть слишком широким - ведь каждое предложение должно быть приспособлено для (наглядного) изображения вполне определенного содержательного преобразования поля зрения. Поэтому следует принять меры к тому, чтобы ,во-первых, изображаемые подстановки не нарушали структуру поля зрения, и ,во-вторых, чтобы можно было управлять допустимыми значениями переменных (другими словами, управлять их типом).
Наконец, в-третьих, необходимо установить такие правила согласования предложения с ведущим термом, чтобы анализ и синтез были однозначными. Другими словами, правила согласования должны обеспечивать единственность подразумеваемой программистом согласующей интерпретации (при фиксированном поле зрения).
Первое и второе достигаеттся за счет ограничений на класс допустимых интерпретаций, третье - за счет ограничений на класс допустимых согласований.
Именно, допустимые интерпретации должны удовлетворять двум условиям.
2.2.2.2.1. Значения переменных, а также обе части изображаемой подстановки должны быть выражениями.
Так что М-преобразования не выводят за класс выражений.
2.2.2.2.2. Значение переменной должно соответствовать так называемому спецификатору, который указывается непосредственно после обозначения переменной и отделяеется двоеточием ":".
[Понятие спецификатора связано с еще одним (в некотором смысле ортогональным) направлением обобщения марковской формулы подстановки. Это направление мы оставим открытым и будем использовать пока только очень простые спецификаторы. Именно, в качестве спецификатора можно написать "символ" или "терм" (это значит, что значениями переменной могут быть только символы (только термы)) или в круглых скобках можно явно перечислить допустимые значения переменной.
Например, s:символ - переменная, значениями которой могут быть только символы, t:терм - только термы, s:(+I-) - значениями s могут быть только литеры "+" или "-". ]
Ограничения на согласования состоят в том, что допустимыми считаются только так называемые ориентированные согласования. Они бывают левыми или правыми.
2.2.2.2.3. Определение ориентированного согласования
Определим левое (левоориентированное) согласование. Правое определяется по симметричным правилам.
Будем называть переменную y1 в функциональном терме левой для переменной y2, если самое левое вхождение y1 расположено левее самого левого вхождения переменной y2.
Будем говорить, что согласование (t,i',s) короче согласования (t,i,s), если в t найдется переменная y1, для которой i'(y1) короче i(y1), причем для любой переменной z, левой для y1 в терме t, i'(z) совпадает с i(z).
Согласование (t,i,s) называется левым, если оно самое короткое из возможных согласований t и s.
Таким образом, основная идея левого согласования - левые переменные при поиске согласующей интерпретации удлиняются в последнюю очередь.
Конец определения.
По умолчанию предполагается, что допустимы только левые согласования. Допустимость только правых согласований указывается буквой R после закрывающей функциональной скобки в левой части предложения.
Например, предложение
{e1+e2}-->{e1}{e2}+
согласуется с термом {a+b+c+d} за счет интерпретации
{e1-->a, e2-->b+c+d}
и изображает формулу подстановки
{a+b+c+d} --> {a}{b+c+d}+ ,
а предложение
{e1+e2}R --> {e1}{e2}+
согласуется с тем же термом за счет интерпретации
{e1-->a+b+c, e2-->d}
и изображает формулу подстановки
{a+b+c+d} -> {a+b+c}{d}+.
В рефале принимаются меры к тому, чтобы всегда можно было отличить переменные от постоянных частей предложения. Если есть опасность спутать переменную и постоянную, то постоянную будем выделять.
Подводя итог, можно сказать, что идея подстановки работает в рефале три раза.
Во-первых, интерпретация i определяет подстановку значений переменных вместо их обозначений.
Во-вторых, тем самым она определяет соответствие обобщенной и конкретной марковских подстановок (т.е. "подстановку" конкретной подстановки вместо обобщенной).
Наконец, в-третьих, правая часть этой конкретной подстановки заменяет ведущий терм.
При этом подбор согласующей интерпретации есть, по существу, анализ ведущего терма, а порождение конкретной правой части подстановки при найденной интерпретации - синтез заменяющего выражения (в правой части всегда должно быть правильное выражение - это еще одно требование рефала).
В этом смысле левая часть предложения служит образцом структуры ведущего терма (терм и предложение согласуются, если структура терма соответствует образцу), а правая - образцом для синтезируемого заменяющего выражения.
Упражнение. Покажите, что если ведущий терм согласуется с некоторым предложением, то соответствующее согласование единственно.
Подсказка. Оно либо левое, либо правое.
2.2.3. Исполнитель (рефал-машина)
Теперь легко объяснить, как действует исполнитель, имея в поле зрения обрабатываемое выражение, а в поле определений - программу (т.е. кортеж предложений). Он выполняет следующий цикл.
Во-первых, выделяет ведущий терм. Если такового нет, останавливается. Выражение в поле зрения считается результатом.
Во-вторых, ищет первое по порядку предложение, которое согласуется с ведущим термом. Соответствующее согласование всегда единственно. Значит, единственна и изображаемая при соответствующей интерпретации переменных марковская подстановка. Она и применяется к ведущему терму. И цикл начинается сначала с обновленным полем зрения.
Если нет согласующихся с ведущим термом предложений, то исполнитель останавливается с диагностикой "согласование невозможно".
2.2.4. Программирование "в стиле рефала"
Задачу перевода в ПОЛИЗ (с учетом старшинства операций) решает следующая программа.
{e1+e2}R -> {e1}{e2}+
{e1*e2}R -> {e1}{e2}*
{(e)} -> {e}
{e} -> e
Упражнение 1. Доказать, что это правильная программа.
[Обратите внимание: действиями исполнителя полностью управляет структура обрабатываемых данных.] .
Упражнение 2. Можно ли эту программу написать короче? Например, так:
{e1 s:(+I*) e2}R -> {e1}{e2}S
{(e)} -> {e}
{e} -> e
Упражнение 3. Можно ли здесь отказаться от правого согласования?
Задача. Напишите на рефале программу аналитического дифференцирования многочленов по переменной "x".
2.2.5. Основное семантическое соотношение в модели М
Рассмотрим функцию sem, реализуемую рефал-программой p. Ее тип, очевидно
sem:P x E -> E
где Р - программы, Е - выражения.
[ Уже тип функции sem указывает на принципиалъное отличие от модели Н - программа не меняется. В модели Н программа - часть (изменяемого) состояния.]
Пусть ft - функция, выделяющая в выражении ведущий функциональный терм, l и r - функции, выделяющие соответственно левую и правую части выражения, оставшиеся после удаления ведущего терма. Конкатекацию (соединение) строк литер будем обозначать точкой ".". Удобно считать, что если ведущего терма в выражении е нет, то ft = <>, r(e) = e, где <> обозначает пустое слово. Все эти три функции типа E -> W, где W - тип "слов" (произвольных последовательностей литер), так как результаты могут и не быть выражениями.
Пусть, далее step - функция типа
Р х Т' -> E ,
где Т' = Т U {<>}. Эта функция реализуется одним шагом работы рефал-машины - функция step отображает пару
(программа, ведущий терм или пусто)
в выражение, получающееся из этого терма применением соответствующей марковской подстановки. Функция step, естественно, частичная - она не определена, если согласование с p невозможно; step(p,<>) = <> по определению.
Учтем, что p не меняется и вся зависимость sem от p скрыта в функции step. Поэтому позволим себе для краткости явно не указывать p среди аргументов функций sem и step. Тогда можно выписать следующее соотношение для sem:
sem(e) = sem(l(e).step(ft(e)).r(e))
Если обозначить l(e), r(e) и ft(e) соответственно через l, r и f, то получим более выразительное соотношение:
(a) sem(l.ft.r) = sem(l.step(ft).r)
Покажем, что на самом деле справедливо следующее основное соотношение
(b) sem(l.ft.r) = sem(l.sem(ft).r)
Действительно, если step(ft) не содержит функциональных термов, то
sem(ft) = step(ft)
и (b) cледует из (a).
Если же step (ft) содержит функциональные термы, то так как l таких термов не содержит, все функциональные термы из step(ft) будут заменены раньше, чем изменится l или r. Но последовательные замены термов в step(ft) - это и есть вычисление sem(ft).
Если такое вычисление завершается и между l и r не остается функциональных термов, то вычисление sem от исходного выражения будет нормально продолжено с выражения l.sem(ft).r.
Если же sem(ft) вычислить не удается из-за отсутствия согласования, то на этом же месте окажется невозможным согласование и для исходного выражения. Тем самым равенство доказано.
В соотношении (b) зафиксированы следующие свойства семантики рефала.
Во-первых, результат применения программы к ведущему терму не зависит от его контекста, а значит, и от истории применения программы к исходному выражению.
Во-вторых, "область изменения" в выражении e до полного вычисления его ведущего терма ограничена этим термом.
В-третьих, если l и r не содержат функциональных скобок, они никогда не могут быть изменени.
Аналогичными рассуждениями можно обобщить соотношение (a). Обозначим через ft1,...,ftn последовательные терминальные функциональные термы в e (т.е. не содержащие других функциональных термов), а через r0,...,rn - слова , не содержащие функциональных термов и такие, что
Упражнение. Докажите справедливость этого соотношения.
Не забудьте, что участок r0.sem(ft1).,...,.sem(ftn).rn может содержать функциональные термы.
Отметим также очевидное соотношение
sem(sem(e)) = sem(e).
Таким образом, обработка в модели М обладает четкой иерархической структурой. Другими словами, выполнение программы p над выражением e можно представлять себе как "вычисление" этого выражения, начиная с любого из "терминальных функциональных поддеревьев" соответствующего дерева.
2.2.6. Пример вычисления в модели М
Сопоставим вычисление по школьным правилам выражения (10+2)*(3+5) с обработкой в модели М выражения {10+2} {3+5}* по программе перевода в ПОЛИЗ. Изобразим последовательно получаемые деревья, соответствующие обрабатываемым выражениям (слева - для школьной арифметики, справа - для рефала).
Шаг 1 (исходные деревья).
* . . *
/ \ / \
/ \ / \
10+2 3+5 {10+2} {3+5}
Рис. 2.2
Деревья явно похожи (вершины изображают операции, дуги - отсылки к тем операндам, которые еще следует вычислить).
Шаг 2 (применение одной из операций, для которых готовы операнды).
12 * . . . + . *
I / I \
I / I \
3+5 {10} {2} {3+5}
Рис. 2.3
Видно, что дерево справа "отстает" от дерева слева. Сказывается различие результатов функций step и sem. Последим за правым деревом до завершения вычисления функции sem({10+2}).
Шаг 2.1.
10 . + . *
/ \
{2} {3+5}
Рис.2.4
Шаг 2.2.
10 2 + . *
\
{3+5}
Рис. 2.5
Вот теперь деревья снова похожи!
Слово "вычисление" означает здесь процесс, вполне аналогичный вычислению значения обычного школьного алгебраического выражения после подстановки вместо переменных их значений. Однако, аналогия касается не типа допустимых значений (в школьной алгебре - числа, а здесь - сбалансированные по скобкам тексты), а способа планирования обработки (способа программирования).
И в школьной алгебре, и в рефале план обработки в определенном смысле содержится в обрабатываемом (вычисляемом) выражении. Роль исполнителя состоит в том, чтобы выполнять указанные операции над допустимыми операндами, подставляя результат операций в обрабатываемое выражение на место вычисленного терма.
[Существенные отличия состоят в том, что, во-первых, школьные операции считаются заранее известными, предопределенными, а смысл единственной рефал-операции step задается полем определений; во-вторых, результат школьных операций - всегда "окончательный" (новых операций в нем не содержится - это число), а результат операции step - в общем случае "промежуточный" - им может оказаться выражение с новыми функциональными термами. Заметим, что второе отличие исчезает, если от функции step перейти к функции sem - ее результат всегда "окончательный", ведь (sem(sem(e)) = sem(e)).].
Шаг 3.
12*8 10 2 + . . + *
/ \
{3} {5}
Рис. 2.6
Шаг 3.1.
10 2 + 3 . + *
\
{5}
Рис. 2.7
Шаг 3.2.
10 2 + 3 5 + *
Рис. 2.8
Шаг 4.
96 10 2 + 3 5 + *
(нет функциональных термов)
Рис. 2.9
Итак, мы убедились, что вычисления в рефале очень похожи на вычисления обычных арифметических формул.
2.2.7. Несколько замечаний
2.2.7.1. Вычисления по формулам очень поучительны для программистов. Из этого древнейшего способа планирования вычислений можно извлечь много полезных идей.
Во-первых, это четкая структура вычислений - она, как мы видели, древовидная.
Во-вторых, операнды рядом с операциями (их не нужно доставать из общей памяти).
В-третьих, результат не зависит от допустимого изменения порядка действий - (с сохранением иерархии в соответствии с деревом выражения). Отсюда - путь к параллельному вычислению, если позволяют вычислительные ресурсы (когда есть несколько процессоров).
В-четвертых, принцип синхронизации таких вычислений прост - всякая операция должна ждать завершения вычислений своих операндов, и только этого события она должна ждать (ничто другое на ее выполнение не влияет).
На этом принципе основаны так называемые конвейерные вычисления и вычисления "управляемые потоком данных" (data flow).
В-пятых, результаты операций никуда не нужно посылать - они нужны там, где получены.
Наконец, отметим еще одну идею, в последние годы привлекающую внимание исследователей, стремящихся сделать программирование надежным, доказательным, систематическим. Речь идет о том, что над школьными формулами можно выполнять систематические преобразования (упрощать, приводить подобные члены, явно выражать неизвестные в соотношениях и т.п.). Есть надежда определить практичную алгебру преобразований и над хорошо организованными программами. Это позволит систематически выводить программы, проверять их свойства, оптимизировать и т.п.
2.2.7.2. Обратите внимание: значение функции sem не зависит от порядка вычисления терминальных функциональных термов. А в нашем исходном определении модели М требовалось, чтобы всегда выбирался самый левый из всех таких термов. При отсутствии взаимного влияния непересекающихся термов такое требование несущественно. [В реальном рефале указанное влияние возможно.]
2.2.8. Аппликативное программирование
Модель М относится к широкому классу так называемых аппликативных моделей вычислений. Это название (от слова apply - применять) связано с тем, что в некотором смысле единственной операцией в таких моделях оказывается операция применения функции к ее аргументу, причем единственной формой влияния одного применения на другое служит связь по результатам (суперпозиция функций). В частности, функции не имеют побочного эффекта.
[Напомним, что побочным эффектом функции называется ее влияние на глобальные объекты, не являющиеся аргументами; в модели М переменные локальны в предложениях, а отсутствие побочного эффекта на поле зрения мы уже обсуждали.]
Аппликативные модели привлекательны тем, что сохраняют многие полезные свойства вычислений по формулам. Самое важное из них - простая и ясная структура программы, четко отражающая требования к порядку вычислений и связям компонент.
Вместе с тем по своей алгоритмической мощности аппликативные модели не уступают другим моделям вычислений.
Задача. Доказать, что модель М алгоритмически полна, т.е. для всякого нормального алгоритма А найдется эквивалентная ему рефал-программа (допускается заменять алфавит, в котором работает А).
Однако, пока наша модель М бедна в том отношении, что ко всем термам применяется одна и та же функции step. Это плохо и потому, что программу трудно понимать (особенно, если она длинная) и потому, что она будет медленно работать, если каждый раз просматривать все предложения поля определений.
К счастью, модель М легко приспособить к более гибкому стилю аппликативного программирования.
2.2.9. Структуризация поля определений; рефал-функции
Допустим, что имеется неограниченный набор различных пар функциональных скобок (как это можно обеспечить?). Будем группировать предложения, записывая подряд друг за другом такие предложения, левая часть которых заключена в одинаковые функциональные скобки.
Тогда ведущий терм будет однозначно указывать на соответствующую группу предложений (в ней и только в ней достаточно искать согласование).
В этом случае функция step распадается на отдельные функции, а программа - на определения этих функций (за что соответствующее поле, где помещается рефал-программа, мы и назвали полем определений).
Достаточно различать только левые функциональные скобки (почему?).
Будем считать левой функциональной скобкой название (идентификатор) функции вместе с непосредственно следующей за ним открывающей фигурной скобкой.
Например, программу перевода в ПОЛИЗ запишем так:
перевод {e1+e2}R -> перевод {e1} перевод {e2} +
перевод {e1*e2}R -> перевод {e1} перевод {e2} *
перевод {(e)} -> перевод {e}
перевод {e} -> e.
Такую совокупность подстановок естественно считать определением рефал-функции "перевод". Его удобно использовать в большой программе среди других подобных определений.
Поле зрения с исходными данными для перевода может выглядеть при этом так:
перевод {(a+b) * (c+d)}
Как видим, и запись самой программы в модели М, и обращение к ней весьма напоминает то, что мы выбрали в качестве идеала в самом начале разговора об анализе и синтезе. [Недостаточна, правда, выразительная сила применяемых в нашей модели образцов. Поэтому приходится писать подробнее, чем в БНФ].
До сих пор мы смотрели на поле определений как на определение одной функции. Это была либо функция step, если результат считался полученным после одного применения подстановки, либо (в общем случае рекурсивная) функция sem, если результатом признавалось только выражение без функциональных термов.
Когда поле определений разбито на группы подстановок с одинаковыми левыми функциональными скобками, каждую такую группу естественно считать определением отдельной функции. С точки зрения одного шага рефал-машины - это функция, представляющая собой сужение функции step на ведущие термы с конкретной функциональной скобкой. С технологической точки зрения (с точки зрения программиста) - это (рекурсивная) рефал-функция, представляющая собой сужение функции sem на те же термы.
Замечание. Применение рефал-функций предполагает уже некоторый элемент прогнозирования со стороны программиста и контроля со стороны рефал-машины, отсутствовавший в исходной модели.
Именно, употребляя конкретную функциональную скобку в правой части предложения, программист прогнозирует, что при определенном поведении исполнителя (если будет выбрано именно это предложение) потребуется определение соответствующей функции.
Рефал-машина, со своей стороны, получает возможность просмотреть поле определений и проверить, что в нем присутствуют определения всех использованных рефал-функций. Другими словами, становится возможным статический контроль программ (т.е. контроль программ до их выполнения, без учета исходных данных).
Конец замечания.
Итак, мы можем определять в программе столько (рекурсивных) функций, сколько нужно.
Вот, например, как выглядит программа аналитического дифференцирования, в которой используется частная производная по x и частная производная по y.
Dx{e1+e2}R -> Dx{e1} + Dx{e2}
Dx{e1*e2}R -> e1*(Dx{e2}) + e2*{Dx{e1})
Dx{(e)} -> Dx{e}
Dx{`x'} -> 1
Dx{s: символ} -> 0
Dy{e1+e2}R -> Dy{e1} + Dy{e2}
. . . . . .
. . . . . .
Dy{`y'} -> 1
Dy{s: символ} -> 0
Задача. Можно ли объединить эти функции? Как это сделать?
2.2.10. Функциональное программирование
В соответствии с определением А.П.Ершова функциональное программирование - это способ составления программ, в которых единственным действием является вызов (применение) функции, единственным способом расчленения программ на части - введение имени для функции и задание для него выражения, вычисляющего значение этой функции, единственным правилом композиции (структурой операций) служит суперпозиция функций.
Ясно, что модель М с учетом последней "функциональной" модификации позволяет программировать в строго функциональном стиле. Другими словами - это одна из моделей функционального программирования.
[Таким образом, одно из отличий "функционального" программирования от "аппликативного" - возможность явно определять (в общем случае рекурсивные) функции].
Дополнительные примеры программирования в "функциональном стиле" мы приведем чуть позже, а пока завершим введение в рефал кратким обзором "функциональной" модели М с точки зрения нашей концептуальной схемы.
2.2.11. Модель М с точки зрения концептуальной схемы
Базис: скалярные данные - только литеры, скалярные операции - только обобщенная поиск-подстановка. Структурные данные - только выражения (есть подтипы: символ и терм), структурные операции - встроенный цикл, легко приводящий к комбинациям функций.
[Говорят, что функции комбинируются горизонтально, если их результаты являются непосредственными составляющими одного функционального терма.
Говорят, что функции комбинируются вертикально, если одна из них не может быть вычислена до завершения вычисления другой. В такой комбинации первая называется внещней, а вторая - внутренней.
В модели М применяется и горизонтальная, и вертикальная комбинация функций. Горизонтальная комбинация называется также конструкцией, а вертикальная, при которой результат внутренней служит полным аргументом внешней - композицией. Произвольная комбинация - суперпозицией.]
Развитие: вверх - только функции типа Е -> Е (однако за счет структурированности выражений это весьма мощное средство развития (как будет показано)); вниз - средств нет.
Защита: в базисе средств нет.
2.2.12. Модель М и Лисп
Можно показать, что модель М отражает не только свойства такого реального языка, как рефал, но и свойства еще одного заслуженного языка, языка Лисп, созданного Джоном Маккарти в 1960 году и с тех пор прочно удерживающего позиции одного из самых распространенных ЯП (особенно в качестве инструментального языка в области искусственного интеллекта). В последние годы интерес к нему усилился еще и как к первому реальному языку функционального программирования.
Единственной базисной структурой данных в Лиспе служит список (так называемое S-выражение). Оно естественно представимо в модели М выражением в круглых скобках. Элементарные селекторы и конструкторы Лиспа (предопределенные функции, позволяющие выбирать из списков компоненты и строить новые списки из заготовок) легко программируются в модели М.
[Приведем упрощенные определения рефал-функций, способных играть роль селекторов и конструкторов. Для краткости всюду ниже будем считать, что с обозначениями рефал-переменных, начинающихся с буквы s и t, связаны соответственно спецификаторы "символ" и "терм" (так и делается в реальном рефале)].
Выбор головы (первого элемента) списка:
первый {(t e)} -> t.
Выбор хвоста списка:
хвост {(t e)} -> (e).
Конструирование (создание) списка:
создать {e} -> (e).
Соединение списков:
соединить {(e1)(e2)} -> (e1 e2).
Подобным образом программируются и другие функции, аналогичные примитивам Лиспа.
Упражнение. Возьмите руководство по языку Лисп и аккуратно выпишите рефал-определения примитивов (базисных функций) Лиспа.
Учтите все их тонкости. Рассмотрите отличия функций первый, хвост и создать от функций car, cdr и cons Лиспа.
Обратите внимание: по существу мы продемонстрировали способность модели М к развитию - довольно легко определить в модели М новый язык, аналогичный Лиспу.
2.3. Критерий концептуальной ясности и функции высших порядков
Предыдущий раздел мы закончили программированием в модели М базисных примитивов языка Лисп - использовали средства развития модели М.
Напомним, что с точки зрения нашей концептуальной схемы способность к развитию - одно из важнейших свойств модели.
Продолжая рассматривать модели ЯП с технологической позиции, продемонстрируем технологическую потребность в функциях высших порядков (т.е. функциях, аргументами и (или) результатами которых служат функции). Затем мы, во-первых, покажем, как их можно ввести в модели М, и, во-вторых, рассмотрим модель Бэкуса (модель Б), в которой функции высших порядков играют ключевую роль (введены в базис).
Напомним, что к модели М мы пришли от идеи разделения анализа и синтеза в обработке данных. И получили мощные средства развития, как только ввели удобную базисную структуру данных (выражение), локализовали область воздействия на эту структуру (ведущий терм) и упростили отбор возможных воздействий (ввели рефал-функции).
Теперь у нас в руках аппарат, который можно развивать в различных направлениях и (или) использовать в различных целях.
[Например, в реальном рефале введены операции, позволяющие изменить поле определений в процессе исполнения программы. Это так называемые операции "закапывания" и "выкапывания" определений по принципу магазина. При таком развитии получается стиль программирования, более близкий к традиционному, с присваиванием глобальным переменным и взаимным влиянием непересекающихся термов. Нас больше интересует развитие в функциональном стиле.]
Воспользуемся аппаратом развития, чтобы показать богатейшие возможности функционального программирования с точки зрения достижения концептуальной ясности программ.
Идеалом будет служить такая программа, в которой в некотором смысле нет ничего лишнего. Другими словами этот критерий концептуальной ясности можно выразить так - структура функции, реализуемой программой, совпадает со структурой программы.
[Однако при этом функция "состоит" из соответствий, а программа - из операций.]
Важнейшая абстракция, способствующая приближению к намеченному идеалу - функция высшего порядка (или, как мы ее назовем, следуя Бэкусу, форма). Ближайшая задача - показать это на достаточно убедительных примерах.
Замечание. Важно понимать, что хотя модель М, конечно, алгоритмически полна, она (как и любая другая модель) не универсальна в том смысле, что в ней не всегда легко вводить любые абстракции. Однако формы в ней вводить довольно легко.
Конец замечания.
2.3.1. Зачем нужны функции высших порядков
Они возникают совершенно естественно. Классический пример - программа интегрирования (вычисления определенного интеграла). Она реализует некоторую форму, аргументом которой служит подынтегральная функция, а результатом - число. Программа аналитического дифференциирования реализует форму, аргументом которой служит некоторая функция (заданная, скажем, многочленом), а результатом - ее производная, т.е. снова функция.
Любая из рассмотренных нами функций, выражающих денотационную семантику модели Н или М, получается, как мы видели, определенной комбинацией исходных функций, соответствующих базисным конструкциям. Если изменить эти исходные функции, не меняя зафиксированной нами формы, представленной их комбинацией, то получим другую семантику модели.
Так, если в модели Н изменить семантику операций - изменится семантика программы. В модели М также можно варьировать, скажем, правила согласования или подстановки без всякого изменения денотационных соотношений - они-то и фиксируют вполне определенную форму, отображающую пару (step,p) в sem.
2.3.2. Замечания о функциях высших порядков
2.3.2.1. Чтобы говорить точно, напомним, что рассматриваем мы функции только типа
E -> Е.
В частности, это означает, что все они формально имеют один аргумент. Фактически может быть столько аргументов, сколько нужно - ведь аргументами можно всегда считать последовательные термы выражения. Отдельные аргументы можно всегда заключить в круглые скобки.
Однако чтобы не загромождать примеры, договоримся, что отделение аргументов пробелами эквивалентно заключению в скобки. Другими словами, будем в значительной степени абстрагироваться от "проблемы круглых скобок", концентрируя внимание на принципиальных моментах (хорошо понимая, что в практическом программировании от этой проблемы никуда не деться - в Лиспе, например, она одна из самых неприятных).
2.3.2.2. Как только мы сказали, что имеем дело с функциями
Е -> Е
сразу возникает вопрос, как же быть с формами. У них-то аргументы - функции, а не выражения. Ответ состоит в том, что и аргументы, и результаты форм всегда будут представлены некоторыми выражениями (например, символами - названиями функций).
2.3.2.3. Примем стиль изложения, при котором смысл вводимых программистских абстракций будем объяснять с помощью определений в модели М. Иногда это может показаться трудным для восприятия. Однако зато мы, во-первых, постоянно упражняемся в программировании в модели М; во-вторых, немедленно демонстрируем конкретизацию вводимой абстракции - а именно ее реализацию в известной модели.
[Такой стиль можно назвать проекционным - вместе с новым понятием излагается его проекция (перевод) на уже известный инструментальный язык. В нашем случае основу этого языка предоставит модель М.]
2.3.2.4. Первая из форм, которую следовало бы рассмотреть - это, конечно, аппликация (которую обозначим двоеточием ":"). Она применяет указанную в ее аргументе функцию (возможно, форму) к остальным компонентам аргумента. Можно было бы определить аппликацию в общем виде, однако нам удобнее считать, что определение рефал-функции ":" формируется постепенно.
А именно, группа предложений со специальной функциональной скобкой вида ":{" пополняется новыми предложениями по мере введения новых форм.
Таким способом (за счет возможностей рефальских образцов) можно определять новые формы (и обычные функции), не требуя, чтобы обращение к ним было обязательно префиксным (т.е. чтобы название функции предшествовало аргументам). Префиксный способ требует слишком много скобок, поэтому его желательно избегать, когда функция (форма) обладает, скажем, свойством ассоциативности.
Упражнение. Покажите, как можно вводить инфиксные функции.
Подсказка. Вспомните о переводе в ПОЛИЗ.
Пока будем считать, что в группе аппликации лишь два предложения
:{(f) e} -> :{f e}
(anл)
:{s_f e} -> s_f{ e }
где f - переменная, обозначающая вызов некоторой формы, а s_f - переменная, обозначающая название применяемой рефал-функции.
Первое предложение снимает скобки, ограничивающие вызов формы (они могли остаться после вычисления значения ее результата, если он был задан инфиксным выражением), а второе выписывает функциональный терм, который служит вызовом применяемой функции.
Подразумевается, что определения применяемых функций в рефал-программе имеются. Предложения (апл) будут оставаться последними в группе аппликации. Новые будем добавлять в ее начало (чтобы сначала действовали формы, а лишь затем их результаты - обычные функции).
2.3.3. Примеры структурирующих форм
Намеченный идеал концептуальной ясности наводит на мысль, что наиболее важными могут оказаться формы, помогающие рационально структурировать программу - выражать ее смысл (реализуемую функцию) простой и понятной комбинацией других функций. Рассмотрим несколько таких структурирующих форм.
Первая из них - композиция (ее часто обозначают звездочкой "*"). Применить результат композиции двух функций f и g - значит применить функцию f к результату применения g. "Применить" - это значит использовать аппликацию.
В модели М определение композиции выглядит так:
:{(f*g)e} -> :{(f) :{(g) e}}.
Точнее говоря, чтобы это предложение заработало как определение новой формы (а именно композиции), им следует пополнить группу (апл).
Вторая полезная форма - "общая аппликация" (применение указанной в аргументе функции ко всем непосредственным составляющим обрабатываемого выражения). Обозначим ее через "А" по аналогии с квантором всеобщности. Для ее определения через аппликацию в группу (апл) следует добавить два рефал-предложения
:{(Аf)t e} -> :{(f)t} :{(Аf)e}
:{(Аf) } -> <> .
Итак, указанная выражением f функция применяется к компонентам обрабатываемого выражения. Получается выражение, составленное из результатов всех применений.
Вопрос. Зачем понадобилось второе предложение?
Третья структурирующая форма - конструкция (ее обозначим запятой ","). Применить результат конструкции двух функций f и g к выражению e - значит получить конкатенацию выражений f(e) и g{e}.
Определить конструкцию в модели М можно так.
:{(f,g) e} -> :{(f)e} :{(g)e} .
Еще один пример формы - редукция, которую обозначим через "/". Название, идея и обозначение восходят к Айверсону, автору языка Апл - одного из самых распространенных диалоговых языков. Своей исключительной лаконичностью этот язык в значительной степени обязан функциям высших порядков.
:{(/f) t1 t2 e} -> :{(f) t1 :{(/f) t2 e}}.
:{(/f) t} -> t.
Идея редукции в том, что бинарная операция f (двухместная функция) последовательно применяется, начиная с конца выражения вида (t1 t2 e) - т.е. выражения, в котором не меньше двух составляющих. Название этой формы подчеркивает, что обрабатываемое выражение сворачивается к одному терму (редуцируется) за счет последовательного "сьедания" пар компонент выражения, начиная с его конца.
Например, с помощью редукции можно определить функцию "сумма".
сумма{e} -> :{(/+) e} .
Тогда если считать, что бинарная операция "+" предопределена и ее можно использовать префиксным способом, получим
сумма{10 20 30} = :{(/+) 10 20 30} =
= :{+10 :{(/+) 20 30}} =
= :{+10 :{+20 :{(/+) 30}}} =
= :{+10 :{+20 30}} = :{+10 50} = 60 .
Обратите внимание, сколь прост и привычен вид программы-формулы
сумма{10 20 30} = 60.
Итак, мы определили конструкцию, общую аппликацию, композицию, редукцию, В том же стиле с помощью аппликации можно определить и другие полезные формы.
Если программировать с использованием таких форм (и некоторых других), то по существу мы будем работать в модели БЭКУСА (модели Б). И снова развитие рефала новыми функциями дает новый язык - язык Бэкуса.
Отличительная черта модели Бэкуса - "фундаментализация" идеи функциональных форм. В частности, четыре названные выше формы считаются примитивными (предопределенными, т.е. определенными средствами, выходящими за рамки модели). Аналогичная идея - одна из основных в языке Апл Айверсона. Однако Айверсону, в отличие от Бэкуса, не удалось ее фундаментализировать (выделить как важнейшую, как основу целого направления в программировании).
2.3.4. Еще несколько функций над выражениями
Определим в модели М еще несколько функций, полезных для работы с выражениями.
реверс{t e} -> реверс{e} t .
реверс{ } -> <>.
Эта функция преобразует выражение вида t1 ... tn в выражение вида tn ... t1, где ti - термы.
Следующая функция - транспонирование (для краткости будем обозначать ее "транс"). По сути дела это обычное транспонирование матриц. Ее действие представим таблицей примеров.
Вопрос. Для чего понадобилось вводить функции дл-хвосты и кор-хвосты?
Подсказка. Мы хотим транспонировать только матрицы.
2.3.5. Пример программы в стиле Бэкуса
Теперь можно написать программу, выражающую в некотором смысле "идеал" программирования в стиле Бэкуса. Точнее, мы напишем программу-формулу, вычисляющую скалярное произведение двух векторов. Будем действовать методом пошаговой детализации.
Допустим, что предопределены функции "сложить" (+) и "умножить" (x). Представим подлежащие перемножению векторы выражением вида (e1)(e2), где e1 - первый вектор, e2 - второй.
Исходная пара векторов представляет собой матрицу с двумя строками e1 и e2.
Вспомним определение скалярного произведения - это
Сумма всех произведений
(d) попарно соответствующих компонент
подлежащих перемножению векторов.
Прочитаем это определение "с конца". Нужно, во-первых, получить попарно компоненты векторов e1 и e2, во-вторых, получить все произведения этих пар, в-третьих, получить сумму (сложить) все эти произведения.
Итак, план (программа) наших действий состоит из трех последовательных шагов, причем результат предыдущего шага непосредственно используется последующим шагом.
Следовательно, наша программа представляет собой композицию функций
f3 * f2 * f1
Какие же это функции?
Функция f1 определяет то, что нужно сделать "во-первых". Если даны два вектора, скажем,
(b1) (10 20 30) (3 2 1)
то нужно получить их компоненты попарно.
(b2) (10 3) (20 2) (30 1)
С этим мы уже встречались, так работает функция "транс". Значит, естественно положить f1 = транс.
Функция f2 определяет то, что нужно сделать "во-вторых". Нужно получить все произведения пар. В нашем примере - это выражение
(b3) 30 40 30
Такое выражение получится, если функцию "умножить" применить к каждому подвыражению выражения (b2). С подобным мы тоже встречались - так работает общая аппликация "А" с аргументом "умножить" (x).
Значит, естественно положить f2 = (Аx).
Наконец, f3 определяет, что нужно сделать "в-третьих". Нужно получить общую сумму всех компонент (b3), т.е.
(b4) 100
Такое выражение получится, если к (b3) применить форму "редукция", с аргументом "сложить" (+). Значит, естественно положить
f3 = (/ +).
Итак, можно выписать нашу программу-формулу полностью:
(/+) * (Аx) * транс .
Эта формула описывает именно ту функцию, которая решает нашу задачу, т.е. вычисляет скалярное произведение.
Использовать ее можно, как и раньше, двумя способами - либо непосредственно применять к обрабатываемому выражению:
:{((/+)*(Аx)*транс) (10 20 30) (3 2 1)} = 100 ,
либо ввести для нее название, скажем, IP
IP{e} -> :{((/+)*(Аx)*транс) e} .
и использовать как обычную рефал-функцию:
IP{(10 20 30) (3 2 1)} = 100 .
Как видим, наша программа полностью соответствует определению скалярного произведения - все слова в этом определении использованы и ничего лишнего не понадобилось вводить (мы записали программу, не использовав ни одного лишнего понятия).
Намеченный идеал концептуальной ясности для данной программы достигнут. Для других программ вопрос открыт, но направление должно чувствоваться. С другой стороны, мы показали, как средства развития в модели М, позволяя вводить адекватные понятия (абстракции), помогают бороться со сложностью создания программ.
Задача. Можно ли аналогичные средства ввести в Алголе-60, Фортране, Бейсике? Дайте обоснованный ответ.
2.3.6. Сравнение с программой на Алголе 60
Рассмотрим фрагмент программы на Алголе 60:
c := 0;
(ap) for i:=1 step 1 until n do
c := c + a[i] x b[i];
Такой фрагмент вычисляет скалярное произведение двух векторов a и b.
Попытаемся сопоставить его с определением скалярного произведения (d).
Во-первых, сразу видно, что естественная композиция функций в программе (ap) не отражена. Пришлось заменить ее последовательными действиями с компонентами векторов.
Во-вторых, пришлось ввести пять названий c,i,n,a,b, никак не фигурирующих в исходной постановке задачи. Причем, если по отношению к a,b и с еще можно сказать, что это обозначения исходных данных и результата, то что такое i и зачем понадобилось n?
Ответ таков, что на Алголе со структурами-массивами по-другому работать нельзя. Мы работали с выражением в модели М как с целостным объектом, а в Алголе 60 над массивами возможны лишь "мелкие" поэлементные операции (для этого понадобилась переменная i). К тому же нельзя узнать размер массива, необходимо явно указывать этот размер (n).
В-третьих, мы уже говорили о возможности распараллелить работу по функциональной программе-формуле. А как это сделать в программе (ap)? Опять сравнение не в пользу Алгола.
Задача. Найдите аргументы в пользу Алгола.
Замечание. Программа скалярного произведения в модели Б - это формула, операциями в которой служат формы, а операндами - основные скалярные функции (+, x) и некоторые другие (транс). В этой связи интересно напомнить, что Джон Бэкус - "отец" Фортрана, который тоже начинался как Formula Translation (и "испортился" под натиском "эффективности"). Так что Джон Бэкус пронес идею "формульного" программирования через многие годы, от своего первого знаменитого Фортрана до теперь уже также знаменитого "функционального стиля". Излагая модель Б, мы пользуемся лекцией, прочитанной Джоном Бэкусом по случаю вручения ему премии Тьюринга за выдающийся вклад в информатику [3].
Мы показали, как функции высших порядков помогают писать концептуально ясные программы. В дальнейшем нам предстоит заняться моделью Б подробнее. Основная цель - познакомить с алгеброй программ, разработанной в этой модели, и с применением алгебры для доказательного программирования.
2.4. Модель Бэкуса
Мы показали, как функции высших порядков помогают писать концептуально ясные программы. Теперь займемся моделью Б подробнее. Основная цель - познакомить с разработанной в этой модели алгеброй программ и с ее применением для доказательства эквивалентности программ. Чтобы законы в этой алгебре были относительно простыми, нам понадобится, во-первых, ограничить класс обрабатываемых объектов - считать объектами не произвольные выражения, а только М-термы (т.е. термы в смысле модели М); во-вторых, так подправить определения форм, чтобы их применение всегда давало объекты. Наконец, придется ввести функции, позволяющие раскрывать и создавать термы.
Для выразительности и краткости при наших определениях будем пользоваться общематематической символикой.
Однако все нужные объекты, функции и формы можно без принципиальных трудностей ввести и средствами модели М.
2.4.1. Модель Бэкуса с точки зрения концептуальной схемы
Имея опыт работы со структуризованными объектами (выражениями), формами и рекурсивными определениями (который мы приобрели, работая в модели М) можно с самого начала рассматривать модель Бэкуса (модель Б) по нашей концептуальной схеме. Чтобы не загромождать изложение, не будем постоянно подчеркивать различие между знаками в языке Б (модели Б) и их денотатами, надеясь, что из контекста всегда будет ясно, о чем идет речь. Например, будем называть формой как функцию высшего порядка (денотат), так и представляющее ее выражение (знак). Соответственно примитивной функцией будем называть как ее идентификатор (знак), так и обозначаемое этим идентификатором отображение из объектов в объекты (денотат).
Базис. В модели два скалярных типа - атомы и примитивные функции. Первые служат для конструирования объектов, вторые - для конструирования функций. Объекты и формы - это два структурных типа. Имеется единственная операция - аппликация.
Развитие. Единственным средством развития служит возможность пополнять набор D определений функций. Делается это с помощью фиксированного набора форм и примитивных функций. Определения могут быть рекурсивными.
2.4.2. Объекты
Объект - это либо атом, либо кортеж (последовательность) вида
< X1, ... , Xn >
где Xi - либо объект, либо специальный знак > - "неопределено".
Таким образом, выбор фмксированного множества А атомов полностью определяет множество всех объектов О.
Будем считать, что в А входят (т.е. служат атомами) идентификаторы, числа и некоторые специальные знаки (T,F и т.п.). Выделен специальный атом <> - это единственный объект, который считается одновременно и атомом, и (пустым) кортежем.
Замечание. Аналогично спискам Лиспа нетрудно предствить Б-объекты М-выражениями, введя подходящие обозначения для специальных объектов и заключая последовательности объектов в круглые скобки.
Это же относится и к последующему неформальному изложению модели Б (хороший источник полезных упражнений по представлению Б-понятий М-понятиями).
Конец замечания.
Все объекты, содержащие > в качестве элемента, считаются по определению равными > (т.е. знаки различны, а денотаты - равны). Будем считать, что все такие объекты до применения к ним каких бы то ни было операций заменяются "каноническим" представлением ">".