John Harrison - Введение в функциональное программирование (1108517), страница 3
Текст из файла (страница 3)
Но мынадеемся, что изучая материал, приведённый далее, читатель получит представлениео том, какое разнообразие задач можно решить, программируя в функциональномстиле.Имеративный стиль программирования не является нерушимой догмой.Многие свойства императивных языков программирования развились в процессеабстрагирования от типового компьютерного оборудования, от машинного кодак ассемблерам, затем к макроассемблерам, языку FORTRAN и так далее. Нетоснований утверждать, что такие языки представляют собой наиболее удобныйспособ взаимодействия человека и машины.
В самом деле, последнее слово вразвитии компьютерных архитектур еще не сказано, и компьютеры должны служитьнашим нуждам, а не наоборот. Вероятно, что правильный подход не в том, чтобыначать с оборудования и продвигаться вверх, а наоборот – начать работу с языкапрограммирования, как средства для описания алгоритмов, и затем двигатьсявниз к оборудованию (Dijkstra 1976). В действительности, данная тенденция можетбыть обнаружена и в традиционных языках программирования. Даже FORTRANпозволяет записывать арифметические выражения обычным способом. Программистне обеспокоен задачей линеаризации вычисления подвыражений и выделения памятидля хранения промежуточных результатов.Из этих соображений можно сделать вывод, что идея разработки языковпрограммирования, сильно отличающихся от традиционных, императивных языков,является вполне законной.
Однако, для того, чтобы показать, что мы не простопредлагаем изменения ради изменений, мы должны сказать несколько слов отом, почему мы могли бы предпочесть функциональные языки программированияимперативным.Возможно, главной причиной является то, что программы на функциональныхязыках более точно соответствуют математическим объектам, и их свойства легчедоказывать. Для того, чтобы показать, что программа означает, мы можем связатьабстрактный математический смысл с программой или оператором — это цельденотационной семантики (семантика = значение, смысл).
В императивных языкахэто должно делаться скорее побочным способом, из-за неявной зависимости отсостояния. Для простых императивных языков можно связать оператор с функциейΣ → Σ, где Σ – множество допустимых состояний. Таким образом, оператор получаетнекоторое состояние и порождает другое. Однако, не каждый оператор всегдазавершает свою работу (например, while true do x := x), так что эта функция,вообще говоря, является частичной. Иногда более предпочтительными являютсяальтернативные средства формализации семантики, например, преобразователипредикатов (Dijkstra 1976).
Но если мы добавим возможности, которые могут31.1. Достоинства функционального программированияГлава 1. Введениесложным образом изменить последовательность выполнения операторов, например,goto, или конструкции break и continue языка C, то даже такие решения перестанутработать, поскольку один оператор может привести к пропуску выполнения другихоператоров, следующих за ним в тексте программы.
Вместо этого обычно используютболее сложные семантики, основанные на продолжениях (continuations).В противоположность сказанному выше, функциональные программы, по словамХенсона Henson (1987), «носят свою семантику с собой».3 Мы можем показать это напримере ML. Основные типы напрямую могут рассматриваться как математическиеобъекты. Используя стандартную запись [[X]] для «семантики X», мы можем сказать,например, что [[int]] = Z. Например, функция ML fact, определённая выражением:l e t rec f a c t n =i f n = 0 then 1else n ∗ f a c t (n − 1 ) ; ;имеет один аргумент типа int, и возвращает значение типа int, так что она простоявляется связанной с абстрактной частичной функцией Z → Z:([[fact]](n) =n! if n ≥ 0⊥ otherwise(Здесь ⊥ обозначает неопределённость, поскольку для отрицательных аргументовпрограмма не сможет завершиться).
Однако этот способ простой интерпретации неработает для не-функциональных программ, поскольку, так называемые «функции»могут не быть функциями в математическом смысле. Например, в стандартнойбиблиотеке языка C есть функция rand(), которая возвращает различныепсевдослучайные значения при последовательных вызовах. Это может быть сделанос помощью локальных статических переменных, используемых для храненияпредыдущих результатов, например, так:intrand ( void ) {s t a t i c int n = 0 ;return n = 2147001325 ∗ n + 7 1 5 1 3 6 3 0 5 ;}Таким образом, мы можем рассматривать отказ от переменных и присваивания,как следующий шаг после отказа от goto, поскольку каждый следующий шаг делаетсемантику проще.
Более простая семантика делает доказательство свойств программболее ясным. Это даёт нам больше возможностей для доказательства корректностипрограмм и преобразований, используемых для их оптимизации.У функциональных языков есть и другое потенциальное преимущество.Поскольку вычисление выражений не имеет побочных эффектов для любыхсостояний, то отдельные подвыражения могут вычисляться в произвольном порядке,не влияя друг на друга.
Это означает, что функциональные программы хорошоподдаются распараллеливанию, т.е., компьютер может автоматически вычислятьразличные подвыражения на разных процессорах. В то же время, императивныепрограммы часто задают жёсткий порядок вычислений, так что даже ограниченное3Дополнительно: денотационную семантику можно рассматривать как попытку превратитьимперативные языки в функциональные, путём явного объявления состояний.4Глава 1. Введение1.2. Планперемешивание инструкций в современных процессорах с конвейерной обработкойведёт к сложностям и возникновению технических проблем.На самом деле, ML не является чисто функциональным языкомпрограммирования; в нём есть переменные и присваивания, если потребуется.Большую часть времени мы будем делать нашу работу, оставаясь в рамкахчисто функционального подмножества языка. Но даже если мы и воспользуемсяприсваиваниями, потеряв некоторые из ранее перечисленных достоинств, останетсяв силе большая гибкость в работе с функциями, свойственная языкам, подобнымML.
Программы часто могут быть выражены очень кратко и элегантно при помощифункций высшего порядка (функций, которые оперируют другими функциями).4Код может быть более общим, поскольку он может быть параметризован другимифункциями. Например, программа, которая складывает список чисел, и программа,которая умножает список чисел, могут рассматриваться как экземпляры одной итой же программы, которая параметризуется арифметической операцией над паройчисел и единичным элементом. В первом случае это будут + и 0, а во втором – ∗ и1.5 В заключение, функции могут использоваться для представления бесконечныхнаборов данных удобным способом, например, мы позже покажем как использоватьфункции для выполнения вычислений с вещественными числами, в отличие отиспользования приближений в виде чисел с плавающей запятой.В то же время, функциональные программы не лишены собственных проблем.Поскольку функциональные программы менее ориентированы на выполнение наконечном оборудовании, может быть тяжело вычислить точное использованиересурсов, таких как время и память.
Ввод-вывод также непросто ввести вфункциональную модель, хотя существуют остроумные способы, основанные набесконечных последовательностях.Читатели данной книги должны сами сделать заключение о достоинствахфункционального стиля. Мы не хотим навязывать никакую идеологию, а лишьхотим показать, что существуют разные подходы к программированию, ичто в соответствующих ситуациях функциональное программирование можетиметь значительные достоинства.
Большинство наших примеров выбрано изобластей, которые могут быть определены как «символьные вычисления». Мыверим, что функциональные программы успешно работают в таких приложениях.Однако, как всегда, человек должен использовать наиболее подходящие дляработы инструменты. Возможно, что императивное, объектно-ориентированное илилогическое программирование лучше подходят для определённых задач.1.2ПланДля тех, кто использовал императивное программирование, переход кфункциональному будет неизбежно тяжёл, независимо от используемого подхода.Хотя есть люди, которые сразу хотят перейти непосредственно к программированию,4Элегантность субъективна, а краткость — не самоцель. Функциональные языки, а также другиеязыки, такие как APL, часто создают соблазн создания очень короткого, хитроумного кода, которыйэлегантен для знатоков, но непонятен для остальных.5Это напоминает абстракции, введенные в чистой математике; например, аддитивные имультипликативные структуры над числами являются частными случаями абстрактного понятия«моноид».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
