И.Г. Головин, И.А. Волкова - Языки и методы программирования (1160773), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Подробнее язык Лисп15рассматривается в подразд. 11.2. Здесь сделаем только несколько за­мечаний, необходимых для понимания примера.Лисп-выражение — это атом либо список. Атом — это либо сим­вол (идентификатор), либо число. Список — это последовательностьчленов списка, разделенных пробелами, заключенная в круглые скоб­ки. Член списка — это либо атом, либо список. Есть специальныйатом — nil, который представляет собой пустой список. Поэтомуего другое обозначение ().

Это единственный атом, который одно­временно является и списком. Нетрудно увидеть, что примеры вызоваи определения функции сами представляют собой списки. Иначеговоря, Лисп-программы не только обрабатывают списки, но и самипредставляют собой списки. Следовательно, функция read не зани­мается политерным вводом (как в императивных языках программи­рования), а читает и строит Лисп-объекты (атомы и списки). Поэтомунемного переформулируем задачу для решения ее на языке Лисп вфункциональном стиле.

Пусть на входе имеется список слов (сим­волов). Требуется выдать этот список в обратном порядке. Заметим,что формулировка задачи не упростилась, а наоборот, усложнилась.Однако это не усложнит ее решение на Лиспе.Поскольку функция read сразу вводит весь список, то необходимонаписать функцию обращения списка. И такая функция в Лиспе име­ется, она называется reverse.

Тогда решение выглядит тривиально(print — это функция вывода в стандартный канал):(print (reverse (read)))Однако чтобы почувствовать специфику функционального про­граммирования, напишем свой вариант функции reverse:(defun rev(x)(if (null x)nil(append (rev (cdr x)) (cons (car x) nil) )))Поясним решение.

Заметим, что список — это рекурсивная струк­тура, поэтому и обработка списков тоже рекурсивная по своей при­роде. Обращение пустого списка — это пустой список, если же списокне пустой, то он состоит из первого элемента списка (функция Лиспа(саг х) возвращает первый элемент списка х) и хвоста, которыйтоже является списком (функция Лиспа (cdr х) возвращает хвостсписка х).

Обращение такого списка — это список, который состоитиз двух списков: первый список представляет собой обращение хвоста( (rev (cdr х) ) ), а второй список состоит из одного элемента —головых (с а г х ) .Однако первый элемент списка — это необязательно список,поэтому из него следует сделать одноэлементный список с помощью16функции Лиспа (cons а Ь) .В результате работы этой функцииформируется список с головой а и хвостом Ь.

Таким образом, (cons(саг х) n i l ) и есть требуемый одноэлементный список.Ф у н к ц и я append в языке Лисп служит для конкатенации списков,а предикат ( n u ll х) проверяет список х на пустоту.Специальная функция i f Лиспа вычисляет свой первый аргу­мент ( ( n u ll х ) ), и если он истинный, то возвращает вычисленныйвторой аргумент ( n il) , а в противном случае возвращает вычислен­ный третий аргумент ( (append (re v (cd r х) ) (cons (c a r x)n i l ) )).Заметим, что в приведенной программе отсутствуют присваи­вания и циклы. В ней только вызовы функций (и один из них ре­курсивный). Это отличительный признак чисто функциональныхпрограмм. Также отметим еще два момента.

Во-первых, это совсемне лучший способ реализации функции re v e rs e . Во-вторых, рекур­сивный способ обращения списка (или массива) можно реализоватьна любом императивном языке, в котором допускаются рекурсивныевызовы функций.Следовательно, можно программировать в функциональном сти­ле и на ИЯП. Правда, делать это на императивных языках труднее,чем на языках типа Лисп, явно поддерживающих функциональныйстиль.1.3. Схема рассмотрения языковпрограммированияКонструкции языков программирования будем рассматривать последующей схеме (подробнее см. в [18]): базис, средства развития исредства защиты.Базис — это понятия и конструкции, встроенные в язык про­граммирования, иначе говоря, это то, что «понимает» транслятор.Базис подразделяется на скалярный и структурный.В скалярный базис входят элементарные (неделимые) типы дан­ных и элементарные операции. Тип данных i n t e g e r с машиннойточки зрения имеет некоторую структуру, представляющую собойпоследовательность либо битов, либо байтов.

Однако в большинствеЯП целый тип представляет собой именно скалярную величину иотносится к скалярному базису.К структурному базису относятся встроенные в язык конструкции,которые имеют внутреннюю структуру, т.е. включают в себя другиеконструкции языка. В структурный базис императивных языковвходят составные типы, например массивы и записи (структуры),большинство операторов языка (за исключением совершенно три­виальных типа b re a k или c o n tin u e в С).17Базисы императивных языков программирования похожи другна друга.

И то, что появляются новые языки, а старые продолжаютжить, обусловлено различиями не в базисе, а в средствах развитияи защиты.Средства развития — это аппарат, позволяющий добавлять впрограммы новые понятия (абстракции), которых не было в базисе.Уже в самом первом языке программирования Фортране появилосьтакое средство развития, как подпрограмма. Основное требование ксредствам развития — возможность определять новые типы данных.В идеале новые типы почти не должны отличаться от базисных типов.Самыми мощными средствами развития из тех, которые мы будемрассматривать, являются классы.Однако только одного аппарата развития недостаточно. Напри­мер, мало иметь средства создания новых типов данных. Необходимоопределять их таким образом, чтобы соответствующие абстракцииможно было легко употреблять, а также контролировать их цельностьи корректность поведения.

Именно этим занимаются средства за­щиты в языках программирования. К средствам защиты относятся,например, средства обработки исключительных ситуаций, механизмабстракции данных и др. Современные языки программированияотличаются от более ранних языков прежде всего тем, что у первыхзначительно усилены именно средства защиты.Глава 2ИСТОРИЧЕСКИЙ ОЧЕРК РАЗВИТИЯ ЯЗЫКОВПРОГРАММИРОВАНИЯМожно условно выделить три периода развития языков програм­мирования:• период зарождения (1950 — начало 1960 гг.);• период бурного роста (1960—1980 гг.);• эволюционный период (1980 гг. и по настоящее время).Период зарожденияПервым языком программирования в современном смысле этогослова стал язык Фортран, разработанный в 1954 — 1957 гг. в IBMпод руководством Джона Бэкуса.

Фортран (Fortran) — это транс­лятор формул (Formulae Translator). Авторы языка поставили цельюсоздание инструмента, который позволил бы ученым и инженерамиспользовать близкую им нотацию, а не машинный код для созданияпрограмм. Фортран — пример языка, создатели которого достиглитех целей, которых добивались. Несмотря на то что с современнойточки зрения Фортран подвергается справедливой критике, он явля­ется одним из самых успешных языков программирования. На этомязыке активно программируют до сих пор.Определим языковую нишу как совокупность проблемных об­ластей, для работы в которых предназначен данный язык програм­мирования. Одна из главных причин успеха Фортрана состоит втом, что он первым занял нишу языка научно-технических расчетов(НТР) для разнообразных математических и физических моделей,использующих интегральное и дифференциальное исчисления, раз­ностные методы.

Фортран позволил ученым (математикам, физиками др.) самостоятельно разрабатывать программы для своих целей.Огромным достоинством Фортрана явилась его доступность наосновных машинных архитектурах. В результате программистскаябаза существенно увеличилась. Фортран показал, что язык высокогоуровня помогает привлечь к программированию большее количествоприкладных специалистов. Компьютер становится более полезным.Фортран продемонстрировал, что язык программирования высоко­19го уровня позволяет обеспечить мобильность (или переносимость)программ и знаний.Существует два аспекта мобильности, обеспечиваемой исполь­зованием языков программирования: мобильность программногообеспечения и мобильность знаний. До появления Фортрана про­грамма, написанная на одном машинном языке, не могла выполнять­ся на машине другой архитектуры из-за несовместимости на уровнедвоичных кодов.

После появления Фортрана были разработанымиллионы строк программного кода, которые могли выполняться намашинах разной архитектуры, хотя до сих пор обеспечение полноймобильности программного обеспечения не достигнуто. Чем болеесложной является задача, тем труднее перенести ее с одной машинына другую.Однако более важным аспектом является мобильность знаний. Допоявления Фортрана при появлении новой или просто другой моделикомпьютера приходилось изучать новую систему команд, привыкатьк новой управляющей программе (операционных систем тогда небыло), переписывать все программы на новом машинном языке.После появления Фортрана при переходе с одной машины на другуюнеобходимость переучиваться и переписывать программы отпала, чтопозволило специалистам сосредотачиваться на проблемной области,а не на изучении новых инструментов.Фортран по многим причинам непригоден для индустриальногопрограммирования, однако в области высокопроизводительных вы­числений он является ведущим языком.

В настоящее время суще­ствует несколько версий Фортрана, самые популярные из которыхФортран 77 и Фортран 90.Успех Фортрана дал толчок к появлению новых языков. В 1960 г.появился Алгол 60. Этот язык оказал огромное концептуальноевлияние на последующие языки. Так, например, цикл for совре­менных языков унаследован из Алгола. В Алголе впервые появиласьрекурсия, а также понятия стека и вложенных областей види­мости. Алгол был разработан группой ученых как язык описанияалгоритмов — ALGOrithmic Language.

Характеристики

Список файлов книги