Программирование на функциональном уровне

В информатике программирование на уровне функций относится к одной из двух противоположных парадигм программирования, определенных Джоном Бэкусом в его работе над программами как математическими объектами, другая — программирование на уровне значений .

В своей лекции на Премии Тьюринга 1977 года Бэкус изложил то, что он считал необходимостью перехода к другой философии проектирования языков программирования: ^[1]

Языки программирования, похоже, находятся в беде. Каждый последующий язык включает в себя, с небольшой доработкой, все особенности своих предшественников плюс еще несколько. [...] Каждый новый язык требует новых и модных функций... но очевидным фактом является то, что лишь немногие языки делают программирование достаточно дешевым или более надежным, чтобы оправдать затраты на их создание и обучение их использованию.

Он разработал FP как первый язык программирования , специально поддерживающий стиль программирования на уровне функций.

Программа функционального уровня не содержит переменных (см. бесточечное программирование ), поскольку программные переменные , которые необходимы для определений уровня значений, не нужны в программах функционального уровня.

Введение [ править ]

При функциональном стиле программирования программа строится непосредственно из программ, заданных вначале, путем объединения их с программообразующими операциями или функционалами . Таким образом, в отличие от подхода на уровне значений, который применяет данные программы к значениям для формирования последовательности значений , кульминацией которой является желаемое значение результата, подход на уровне функций применяет операции формирования программ к данным программам для формирования последовательности программ. кульминацией программы желаемого результата.

В результате подход к программированию на функциональном уровне предлагает изучить пространство программ под операциями формирования программ с целью выявить полезные алгебраические свойства этих операций формирования программ. Функциональный подход дает возможность превратить набор программ в математическое пространство за счет выделения алгебраических свойств программообразующих операций в пространстве программ .

Еще одним потенциальным преимуществом представления на уровне функций является возможность использовать только строгие функции и, таким образом, иметь восходящую семантику , которая является самой простой из всех. Еще одним является существование определений функционального уровня, которые не являются поднятым (то есть поднятым с более низкого уровня значений на более высокий функциональный уровень) образом любого существующего уровня ценностей: эти (часто краткие) определения функционального уровня определения представляют собой более мощный стиль программирования, недоступный на уровне значений.

функциональному программированию Контраст

Когда Бэкус изучал и публиковал свой стиль программирования на функциональном уровне, его послание по большей части было понято неправильно. ^[2] как поддержка традиционных языков функционального стиля программирования вместо своего собственного FP и его преемника FL .

Бэкус называет функциональное программирование аппликативным программированием ; ^{[ нужны разъяснения ]} его программирование на функциональном уровне представляет собой особый, ограниченный тип.

Ключевое отличие от функциональных языков заключается в том, что язык Бэкуса имеет следующую иерархию типов:

атомы
функции, которые переводят атомы в атомы
Функции высшего порядка (которые он называет «функциональными формами»), которые переводят одну или две функции в функции.

...и единственный способ генерировать новые функции — это использовать одну из функциональных форм, которые фиксированы: вы не можете построить свою собственную функциональную форму (по крайней мере, не в рамках FP; вы можете в рамках FFP ( Formal FP )).

Это ограничение означает, что функции в FP представляют собой модуль (порожденный встроенными функциями) над алгеброй функциональных форм и, следовательно, алгебраически разрешимы. Например, общий вопрос о равенстве двух функций эквивалентен проблеме остановки и неразрешим, но равенство двух функций в FP — это просто равенство в алгебре, и поэтому (как предполагает Бэкус) проще.

Даже сегодня многие пользователи языков лямбда-стиля часто ошибочно интерпретируют подход Бэкуса на уровне функций как ограничительный вариант лямбда-стиля, который де-факто является стилем уровня значений. На самом деле Бэкус не согласился бы с «ограничительным» обвинением: он утверждал, что именно из -за таких ограничений могло возникнуть хорошо сформированное математическое пространство, аналогично тому, как структурное программирование ограничивает программирование ограниченной версией. всех возможностей потока управления, доступных в простых, неограниченных неструктурированных программах .

Свободный от значений стиль ФП тесно связан с эквациональной логикой декартовой замкнутой категории .

Примеры языков [ править ]

Каноническим языком программирования функционального уровня является FP . включают FL и J. Другие

См. также [ править ]

Ссылки [ править ]

^ Бэкус, Джон (1978). «Можно ли программирование освободить от стиля фон Неймана?: Функциональный стиль и его алгебра программ» (PDF) . Коммуникации АКМ . 21 (8): 613–641. дои : 10.1145/359576.359579 .
^ Худак, Пол (1989). «Концепция, эволюция и применение языков функционального программирования». Обзоры вычислительной техники ACM . 21 (3): 359–411. дои : 10.1145/72551.72554 . S2CID 207637854 .

Внешние ссылки [ править ]

Программы функционального уровня как математические объекты от Джона Бэкуса
От семантики функционального уровня к преобразованию и оптимизации программ SpringerLink см. пункты 1.2 и 1.3.
Закрытые аппликативные языки, FP и FL , в книге Джона В. Бэкуса (Публикации) или в оригинальной книге «Семантика языков программирования и закрытые аппликативные языки».
Переменные экземпляра, выход из воздержания от переменных

[1] Бэкус, Джон (1978). «Можно ли программирование освободить от стиля фон Неймана?: Функциональный стиль и его алгебра программ» (PDF) . Коммуникации АКМ . 21 (8): 613–641. дои : 10.1145/359576.359579 .

[2] Худак, Пол (1989). «Концепция, эволюция и применение языков функционального программирования». Обзоры вычислительной техники ACM . 21 (3): 359–411. дои : 10.1145/72551.72554 . S2CID 207637854 .

[1]

[2]