Функция программирование: Понятие функции в программировании

Содержание

Функция (программирование) — это… Что такое Функция (программирование)?

У этого термина существуют и другие значения, см. функция.

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

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

Побочный эффект

Побочным эффектом функции называется любое изменение функцией состояния программной среды, кроме возвращаемого значения: изменение значений глобальных переменных, выделение и освобождение памяти, ввод-вывод и тому подобного. Теоретически наиболее правильным является использование функций, не имеющих побочного эффекта (то есть таких, в результате вызова которых возвращается вычисленное значение, и только). В функциональной парадигме программирования любая программа представляет собой набор вложенных вызовов функций, не вызывающих побочных эффектов. Наиболее известный язык программирования, реализующий эту парадигму — Лисп. В нём любая операция, любая конструкция языка, любое выражение, кроме константы, являются вызовами функций. Наиболее полно парадигма функционального программирования реализуется в языке Хаскелл.

Функции и процедуры

В некоторых языках программирования (например, в Паскале) функции и процедуры (подпрограммы, не возвращающие значения) чётко разграничены синтаксисом языка. В других — например, в языке Си, — процедуры являются частным случаем (подмножеством) функций, возвращающими значение типа (псевдотипа^{[источник не указан 757 дней]}) void — пустое значение.

Аргументы и параметры

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

Функция без аргументов

Такая функция не требует никаких аргументов.

См. также

Ссылки

Чем отличаются понятия функции, процедуры и метода в программировании? — Хабр Q&A

D3lphi

Функция — подпрограмма, выполняющая какие-либо операции и возвращающая значение.
Процедура — подпрограмма, которая только выполняет операции, без возврата значения.
Метод — это функция или процедура, которая принадлежит классу или экземпляру класса.

как бы да, но… только на самом начальном этапе, что бы угомонить хаос в голове новичка ))

в дальнейшем, все интереснее все эти понятия контекстно зависимые, контекстом является парадигма программирования и/или конкретный язык

1 — в контексте парадигм, из данных понятий уникально одно Метод, как уже было сказано D3lphi, это нечто принадлежащее классу. класс, в свою очередь, это фундаментальное понятие ООП основанного на классах (шарм ситуации в том, что ООП бывает тоже разное ;))

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

но .. есть много языков, где понятия метод нет вообще

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

2 — из контекста языков:

понятие процедура в явном виде, чаще всего употребляют преподаватели, которые сами учились на языках типа Fortran, Pascal или родственных, и либо не имели другого опыта вообще, либо иной опыт был на много скромнее

сейчас доминируют языки, основывающиеся на Си синтаксисе, даже java и js в данном вопросе станут родственниками классического Си

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

смешение всего этого на примере C# — в этом языке, все есть объект. а любой исполняемый код это метод, и методы реализуются только функциями (в тч void функциями)

Что такое функциональное программирование

В программировании есть два больших подхода — императивное и функциональное. Они существенно отличаются логикой работы, ещё и создают путаницу в названиях. Сейчас объясним.

🤔 Функциональное — это про функции?

❌ Нет. Функциональное — это не про функции. Функции есть почти в любых языках программирования: и в функциональных, и в императивных. Отличие функционального программирования от императивного — в общем подходе.

Метафора: инструкция или книга правил

Представьте, что вы открываете кафе-столовую. Сейчас у вас там два типа сотрудников: повара и администраторы.

Для поваров вы пишете чёткие пошаговые инструкции для каждого блюда. Например:

Налить воды в кастрюлю
Поставить кастрюлю с водой на огонь
Добавить в кастрюлю с водой столько-то соли
Если нужно приготовить 10 порций, взять одну свёклу. Если нужно приготовить 20 порций, взять две свёклы.
Почистить всю свёклу, которую вы взяли
…

Повар должен следовать этим инструкциям ровно в той последовательности, в которой вы их написали. Нельзя сначала почистить свёклу, а потом взять её. Нельзя посолить кастрюлю, в которой нет воды. Порядок действий важен и определяется вами. Это пример императивного программирования. Вы повелеваете исполнителем. Можно сказать, что исполнители выполняют ваши задания.

Для администратора вы пишете не инструкцию, а как бы книгу правил:

У нас нельзя со своим. Если гости пришли со своим, то сделать им замечание такое-то.
В зале должно быть чисто. Если в зале грязно, вызвать уборщика.
Если образовалась очередь, открыть дополнительную кассу.

Это тоже команды, но исполнять их администратор будет не в этой последовательности, а в любой на своё усмотрение. Можно сказать, что задача этого человека — исполнять функции администратора, и мы описали правила, по которым эти функции исполнять. Это пример функционального программирования.

❌ Программисты, не бомбите

Конечно же, это упрощено для понимания. Вы сами попробуйте это нормально объяснить (можно прямо в комментах).

Императивное программирование

Примеры языков: C, С++, Go, Pascal, Java, Python, Ruby

Императивное программирование устроено так:

В языке есть команды, которые этот язык может выполнять. Эти команды можно собрать в подпрограммы, чтобы автоматизировать некоторые однотипные вычисления. В каком порядке записаны команды внутри подпрограммы, в том же порядке они и будут выполняться.

Есть переменные, которые могут хранить данные и изменяться во время работы программы. Переменная — это ячейка для данных. Мы можем создать переменную нужного нам типа, положить туда какое-то значение, а потом поменять его на другое.

Если подпрограмме на вход подать какое-то значение, то результат будет зависеть не только от исходных данных, но и от других переменных. Например, у нас есть функция, которая возвращает размер скидки при покупке в онлайн-магазине. Мы добавляем в корзину товар стоимостью 1000 ₽, а функция должна нам вернуть размер получившейся скидки. Но если скидка зависит от дня недели, то функция сначала проверит, какой сегодня день, потом посмотрит по таблице, какая сегодня скидка.

Получается, что в разные дни функция получает на вход 1000 ₽, но возвращает разные значения — так работает императивное программирование, когда всё зависит от других переменных.

Последовательность выполнения подпрограмм регулируется программистом. Он задаёт нужные условия, по которым движется программа. Вся логика полностью продумывается программистом — как он скажет, так и будет. Это значит, что разработчик может точно предсказать, в какой момент какой кусок кода выполнится — код получается предсказуемым, с понятной логикой работы.

Если у нас код, который считает скидку, должен вызываться только при финальном оформлении заказа, то он выполнится именно в этот момент. Он не посчитает скидку заранее и не пропустит момент оформления.

👉 Суть императивного программирования в том, что программист описывает чёткие шаги, которые должны привести код к нужной цели.

Звучит логично, и большинство программистов привыкли именно к такому поведению кода. Но функциональное программирование работает совершенно иначе.

Функциональное программирование

Примеры языков: Haskell, Lisp, Erlang, Clojure, F#

Смысл функционального программирования в том, что мы задаём не последовательность нужных нам команд, а описываем взаимодействие между ними и подпрограммами. Это похоже на то, как работают объекты в объектно-ориентированном программировании, только здесь это реализуется на уровне всей программы.

Например, в ООП нужно задать объекты и правила их взаимодействия между собой, но также можно и написать просто код, который не привязан к объектам. Он как бы стоит в стороне и влияет на работу программы в целом — отправляет одни объекты взаимодействовать с другими, обрабатывает какие-то результаты и так далее.

Функциональное программирование здесь идёт ещё дальше. В нём весь код — это правила работы с данными. Вы просто задаёте нужные правила, а код сам разбирается, как их применять.

Если мы сравним принципы функционального подхода с императивным, то единственное, что совпадёт, — и там, и там есть команды, которые язык может выполнять. Всё остальное — разное.

Команды можно собирать в подпрограммы, но их последовательность не имеет значения. Нет разницы, в каком порядке вы напишете подпрограммы — это же просто правила, а правила применяются тогда, когда нужно, а не когда про них сказали.

Переменных нет. Вернее, они есть, но не в том виде, к которому мы привыкли. В функциональном языке мы можем объявить переменную только один раз, и после этого значение переменной измениться не может. Это как константы — записали и всё, теперь можно только прочитать. Сами же промежуточные результаты хранятся в функциях — обратившись к нужной, вы всегда получите искомый результат.

Функции всегда возвращают одно и то же значение, если на вход поступают одни и те же данные. Если в прошлом примере мы отдавали в функцию сумму в 1000 ₽, а на выходе получали скидку в зависимости от дня недели, то в функциональном программировании если функция получит в качестве параметра 1000 ₽, то она всегда вернёт одну и ту же скидку независимо от других переменных.

Можно провести аналогию с математикой и синусами: синус 90 градусов всегда равен единице, в какой бы момент мы его ни посчитали или какие бы углы у нас ещё ни были в задаче. То же самое и здесь — всё предсказуемо и зависит только от входных параметров.

Последовательность выполнения подпрограмм определяет сам код и компилятор, а не программист. Каждая команда — это какое-то правило, поэтому нет разницы, когда мы запишем это правило, в начале или в конце кода. Главное, чтобы у нас это правило было, а компилятор сам разберётся, в какой момент его применять.

В русском языке всё работает точно так же: есть правила правописания и грамматики. Нам неважно, в каком порядке мы их изучили, главное — чтобы мы их вовремя применяли при написании текста или в устной речи. Например, мы можем сначала пройти правило «жи-ши», а потом правило про «не с глаголами», но применять мы их будем в том порядке, какой требуется в тексте.

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

Типы и функции / Хабр

Это третья статья в цикле «Теория категорий для программистов».

Категория типов и функций играет важную роль в программировании, так что давайте поговорим о том, что такое типы, и зачем они нам нужны.

Кому нужны типы?

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

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

Итак, вопрос в том, хотим ли мы, чтобы обезьяны были счастливы, или создавать корректные программы?
(прим. переводчика: не стоит оскорбляться, автор просто любит менее скучные метафоры, чем ГСЧ и «случайные последовательности байт», а не называет программистов обезьянами).

Обычно цель мысленного эксперимента с печатающими обезьянами — создание полного собрания сочинений Шекспира (прим. переводчика: или Война и Мир Толстого). Проверка орфографии и грамматики в цикле резко увеличит шансы на успех. Аналог проверки типов пойдет еще дальше: после того, как Ромео объявлен человеком, проверка типов убедится, что на нем не растут листья и что он не ловит фотоны своим мощным гравитационным полем.

Типы нужны для компонуемости

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

Единственный серьезный аргумент, который я слышу против строгой статической типизации: она может отвергнуть некоторые программы, которые семантически верны. На практике это случается крайне редко (прим. переводчика: во избежания срача замечу, что тут автор не учел, или несогласен, что есть много стилей, и привычный программсистом на скриптовых языках duck-typing тоже имеет право на жизнь. С другой стороны, duck-typing возможен и в строгой системе типов через templates, traits, type classes, interfaces, много есть технологий, так что мнение автора нельзя считать строго неверным.) и, в любом случае, каждый язык содержит какой-то черный ход, чтобы обойти систему типов, когда это действительно необходимо. Даже Haskell имеет unsafeCoerce. Но такие конструкции должны использоваться разумно. Персонаж Франца Кафки, Грегор Замза, нарушает систему типов, когда он превращается в гигантского жука, и мы все знаем, как это кончилось (прим. переводчика: плохо 🙂.

Другой аргумент, который я часто слышу, в том, что строгая типизация накладывает слишком много нагрузки на программиста. Я могу сочувствовать этой проблеме, так как сам написал несколько обьявлений итераторов в С++, только вот есть технология, вывод типов, которая позволяет компилятору вывести большинство типов из контекста, в котором они используются. В С++, вы можете объявить переменную auto, и компилятор выведет тип за вас.

В Haskell, за исключением редких случаев, аннотации типа являются опциональными. Программисты, как правило, все равно их используют, потому что типы могут многое рассказать о семантике кода, и обьявления типов помогают понимать ошибки компиляции. Обычная практика в Haskell — начинать проект с разработки типов. Позже, аннотации типов являются основой для реализации и становятся гарантированными компилятором комментариями.

Строгая статическая типизация часто используется в качестве предлога для нетестирования кода. Иногда вы можете услышать, как Haskell-программисты говорят: «Если код собирается, он правильный.» Конечно, нет никакой гарантии, что программа, корректная с точки зрения типов, коректна в смысле правильного результата. В результате такого отношения в ряде исследований Haskell не стал сильно опережать остальные языки по качеству кода, как можно было бы ожидать. Кажется, что в коммерческих условиях необходимость чинить баги существует только до определенного уровня качества, что в основном связано с экономикой разработки программного обеспечения и толерантности конечного пользователя, и очень слабо связано с языком программирования или методологией разработки. Лучшим критерием было бы измерить, сколько проектов отстает от графика или поставляется с сильно сниженным функционалом.

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

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

Что такое типы?

Простейшее описание типов: они представляют собой множества значений. Типу Bool (помните, конкретные типы начинаются с заглавной буквы в Haskell) соответствует множество из двух элементов: True и False. Тип Char — множество всех символов Unicode, например ‘a’ или ‘ą’.

Множества могут быть конечными или бесконечными. Тип String, который, по сути, синонимом списка Char, — пример бесконечного множества.

Когда мы обьявляем x, как Integer:

x :: Integer

мы говорим, что это элемент множества целых чисел. Integer в Haskell — бесконечное множество, и может быть использовано для арифметики любой точности. Есть и конечное множество Int, которое соответствует машинному типу, как int в C++.

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

В Set, объекты — это множества, а морфизмы (стрелки) — функции.

Set — особая категория, потому что мы можем заглянуть внутрь ее объектов и это поможет многое интуитивно понять. Например, мы знаем, что пустое множество не имеет элементов. Мы знаем, что существуют специальные множества из одного элемента. Мы знаем, что функции отображают элементы одного множества в элементы другого. Они могут отображать два элемента в один, но не один элемент в два. Мы знаем, что тождественная функция отображает каждый элемент множества в себя, и так далее. Я планирую постепенно забывать всю эту информацию и вместо этого выразить все эти понятия в чисто категорийной форме, то есть в терминах объектов и стрелок.

В идеальном мире мы могли бы просто сказать, что типы в Haskell — множества, а функции в Haskell — математические функции между ними. Существует только одна маленькая проблема: математическая функция не выполняет какой-либо код — она знает только ответ. Функция в Haskell должна ответ вычислять. Это не проблема, если ответ может быть получен за конечное число шагов, каким бы большим оно ни было. Но есть некоторые вычисления, которые включают рекурсию, и те могут никогда не завершиться. Мы не можем просто запретить незавершающиется функции в Haskell потому, что различить, завершается функция, или нет — знаменитая проблема остановки — неразрешима. Вот почему ученые-компьютерщики придумали гениальную идею, или грязный хак, в зависимости от вашей точки зрения, — расширить каждый тип специальным значением, называнным bottom (прим. переводчика: этот термин (bottom) слышится как-то по-дурацки на русском, если кто знает хороший вариант, пожалуйста, предлагайте.), которое обозначается _|_ или в Unicode ⊥. Это «значение» соответствует незавершающемуся вычислению. Так функция, объявленная как:

f :: Bool -> Bool

может вернуть True, False, или _|_; последнее значит, что функция никогда не завершается.

Интересно, что, как только вы принимаете bottom в систему типов, удобно рассматривать каждую ошибку времени исполнения за bottom, и даже позволить функции возвращать bottom явно. Последнее, как правило, осуществляется с помощью выражения undefined:

f :: Bool -> Bool
f x = undefined

Это определение проходит проверку типов потому, что undefined вычисляется в bottom, которое включено во все типы, в том числе и Bool. Можно даже написать:

f :: Bool -> Bool
f = undefined

(без x) потому, что bottom еще и член типа Bool -> Bool.

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

Из-за bottom, категория типов Haskell и функций, называется Hask, а не Set. С теоретической точки зрения, это источник нескончаемых осложнений, поэтому на данном этапе я использую мой нож мясника и завершу эти рассуждения. С прагматической точки зрения, можно игнорировать незавершающиеся функции и bottom и работать с Hask как с полноценным Set.

Зачем нам математическая модель?

Как программист, вы хорошо знакомы с синтаксисом и грамматикой языка программирования. Эти аспекты языка, как правило, формально описываются в самом начале спецификации языка. Но смысл и семантику языка гораздо труднее описать; это описание занимает намного больше страниц, редко достаточно формально, и почти никогда не полно. Отсюда никогда не заканчивающиеся дискуссии среди языковых юристов, и вся кустарная промышленность книг, посвященных толкованию тонкостей языковых стандартов.

Есть формальные средства для описания семантики языка, но из-за их сложности они в основном используются для упрощенных, академических языков, а не реальных гигантов промышленного программирования. Один из таких инструментов называется операционная семантика и описывает механику исполнения программы. Он определяет формализованный, идеализированный интерпретатор. Семантика промышленных языков, таких как C++, как правило, описывается с помощью неформального рассуждения, часто в терминах «абстрактной машины».

Проблема в том, что что о программах, использующих операционную семантику, очень трудно что-то доказать. Чтобы показать некое свойство программы вы, по сути, должны «запустить ее» через идеализированный интерпретатор.

Не важно, что программисты никогда формально не доказывают корректность. Мы всегда «думаем», что мы пишем правильные программы. Никто не сидит за клавиатурой, говоря: «О, я просто напишу несколько строк кода и посмотрю, что происходит.» (прим. переводчика: ах, если бы…) Мы считаем, что код, который мы пишем, будет выполнять определенные действия, которые произведут желаемые результаты. Мы, как правило, очень удивлены, если это не так. Это означает, что мы действительно думаем о программах, которые мы пишем, и мы, как правило, делаем это, запуская интерпретатор в наших головах. Просто, очень трудно уследить за всеми переменными. Компьютеры хороши для исполнения программ, люди — нет! Если бы мы были, нам бы не понадобились компьютеры.

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

Рассмотрим определение функции факториала в Haskell, языке, легко поддающемуся денотационной семантике:

fact n = product [1..n]

Выражение [1..n] — это список целых чисел от 1 до n. Функция product умножает все элементы списка. Точно так, как определение факториала, взятое из учебника. Сравните это с C:

int fact(int n) {
    int i;
    int result = 1;
    for (i = 2; i <= n; ++i)
        result *= i;
    return result;
}

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

fact 0 = 1
fact n = n * fact (n - 1)

Хорошо, я сразу признаю, что это был дешевый прием! Факториал имеет очевидное математическое определение. Проницательный читатель может спросить: Какова математическая модель для чтения символа с клавиатуры, или отправки пакета по сети? Долгое время это был бы неловкий вопрос, ведущий к довольно запутанным объяснениям. Казалось, денотационная семантика не подходит для значительного числа важных задач, которые необходимы для написания полезных программ, и которые могут быть легко решаемы операционной семантикой. Прорыв произошел из теории категорий. Еугенио Моджи обнаружил, что вычислительные эффекты могут быть преобразованы в монады. Это оказалось важным наблюдением, которое не только дало денотационной семантике новую жизнь и сделало чисто функциональные программы более удобными, но и дало новую информацию о традиционном программировании. Я буду говорить о монадах позже, когда мы разработаем больше категорийных инструментов.

Одним из важных преимуществ наличия математической модели для программирования является возможность выполнить формальное доказательство корректности программного обеспечения. Это может показаться не столь важным, когда вы пишете потребительский софт, но есть области программирования, где цена сбоя может быть огромной, или там, где человеческая жизнь находится под угрозой. Но даже при написании веб-приложений для системы здравоохранения, вы можете оценить ту мысль, что функции и алгоритмы из стандартной библиотеки языка Haskell идут в комплекте с доказательствами корректности.

Чистые и Грязные функции

То, что мы называем функциями в C++ или любом другом императивном языке, не то же самое, что математики называют функциями. Математическая функция — просто отображение значений в значения.

Мы можем реализовать математическую функцию на языке программирования: такая функция, имея входное значение будет рассчитать выходное значение. Функция для получения квадрата числа, вероятно, умножит входное значение само на себя. Она будет делать это при каждом вызове, и гарантированно произведет одинаковый результат каждый раз, когда она вызывается с одним и тем же аргументом. Квадрат числа не меняется с фазами Луны.

Кроме того, вычисление квадрата числа не должно иметь побочного эффекта, вроде выдачи вкусного ништячка вашей собаке. «Функция», которая это делает, не может быть легко смоделирована математической функцей.

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

Примеры типов

Как только вы решите, что типы — это множества, вы можете придумать некоторые весьма экзотические примеры. Например, какой тип соответствует пустому множеству? Нет, это не void в C++, хотя этот тип называется Void в Haskell. Это тип, который не наполнен ни одним значением. Вы можете определить функцию, которая принимает Void, но вы никогда не сможете ее вызвать. Чтобы ее вызвать, вам придется обеспечить значение типа Void, а его там просто нет. Что касается того, что эта функция может вернуть — не существует никаких ограничений. Она может возвращать любой тип (хотя этого никогда не случится, потому что она не может быть вызвана). Другими словами, это функция, которая полиморфна по возвращаемому типу. Хаскеллеры назвали ее:

absurd :: Void -> a

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

(Помните, что a — это переменная типа, которая может быть любым типом.) Это имя не случайно. Существует более глубокая интерпретация типов и функций с точки зрения логики под названием изоморфизм Карри-Говарда. Тип Void представляет неправдивость, а функция absurd — утверждение, что из ложности следует что-нибудь, как в латинской фразе «ex falso sequitur quodlibet.» (прим. переводчика: из ложности следует что угодно.)

Далее идет тип, соответствующий одноэлементному множеству. Это тип, который имеет только одно возможное значение. Это значение просто «есть». Вы могли сразу его не признать, но это void в C++. Подумайте о функциях от и в этот тип. Функция из void всегда может быть вызвана. Если это чистая функция, она всегда будет возвращать один и тот же результат. Вот пример такой функции:

int f44() { return 44; }

Вы можете подумать что эта функция принимает «ничего», но, как мы только что видели, функция, которая принимает «ничего» не может быть вызвана, потому что нет никакого значения, представляющего тип «ничего». Итак, что же эта функция принимает? Концептуально, она принимает фиктивное значение, у которого есть только единственный экземпляр, так что мы можем явно его не указывать в коде. В Haskell, однако, есть символ этого значения: пустая пара скобок (). Таким образом, из за забавного совпадения (или не совпадения?), вызов функции от void выглядит одинаково и в C++ и в Haskell. Кроме того, из-за любви Хаскеля к лаконичности, тот же символ () используется и для типа, конструктора и единственного значения, соответствующего одноэлементному множеству. Вот эта функция в Haskell:

f44 :: () -> Integer
f44 () = 44

Первая строка обьявляет, что f44 преобразует тип (), названный «единица», в тип Integer. Вторая строка определяет, что f44 с помощью паттерн-матчинга преобразует единственный конструктор для единицы, а именно () в число 44. Вы вызываете эту функцию, предоставляя значение ():

f44 ()

Обратите внимание, что каждая функция от единицы эквивалентна выбору одного элемента из целевого типа (здесь, выбирается Integer 44). На самом деле, вы можете думать о f44, как ином представлении числа 44. Это пример того, как мы можем заменить прямое упоминание элементов множества на функцию (стрелку). Функции из единицы в некий тип А находятся во взаимно-однозначном соответствии с элементами множества A.

А как насчет функций, возвращающих void, или, в Haskell, возвращающих единицу? В C++ такие функции используются для побочных эффектов, но мы знаем, что такие функции — не настоящие, в математическом смысле этого слова. Чистая функция, которая возвращает единицу, ничего не делает: она отбрасывает свой аргумент.

Математически, функция из множества А в одноэлементное множество отображает каждый элемент в единственный элемент этого множества. Для каждого А есть ровно одна такая функция. Вот она для Integer:

fInt :: Integer -> ()
fInt x = ()

Вы даете ей любое целое число, и она возвращает единицу. Следуя духу лаконичности, Haskell позволяет использовать символ подчеркивания в качестве аргумента, который отбрасывается. Таким образом, не нужно придумывать для него название. Код выше можно переписать в виде:

fInt :: Integer -> ()
fInt _ = ()

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

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

unit :: a -> ()
unit _ = ()

В C++ вы бы реализовали ее так:

template<class T>
void unit(T) {}

(прим. переводчика: дабы помочь компилятору оптимизировать ее в noop, лучше так):

template<class T>
void unit(T&&) {}

Далее в «типологии типов» набор из двух элементов. В C++ он называется bool, а в Haskell, что не удивительно, Bool. Разница в том, что в C++ bool является встроенным типом, в то время как в Haskell он может быть определен следующим образом:

data Bool = True | False

(Читать это определение стоит так: Bool может быть или True или False.) В принципе, можно было бы описать этот тип и в C++:

enum bool {
    true,
    false
};

Но C++ перечисление на самом деле целое число. Можно было бы использовать C++11 «class enum», но тогда пришлось бы уточнять значение именем класса: bool::true или bool::false, не говоря уже о необходимости включать соответствующий заголовок в каждом файле, который его использует.

Чистые функции из Bool просто выбирают два значения из целевого типа, одно, соответствующее True и другое — False.

Функции в Bool называются предикатами. Например, библиотека Data.Char в Haskell содержит много предикатов, например IsAlpha или isDigit. В C++ есть похожая библиотека <cctype>, которая обьявляет, помимо прочего, функции isalpha и isdigit, но они возвращают int, а не булевое значение. Настоящие предикаты определены в <locale> и называются ctype::is(alpha, c) и ctype::is(digit, c).

Теория категорий для программистов: предисловие
Категория: суть композиции

Типы и функции
Категории, большие и малые
Категории Клейсли

Функция (программирование) Википедия

У этого термина существуют и другие значения, см. функция.

Фу́нкция в программировании, или подпрограмма — фрагмент программного а, к которому можно обратиться из другого места программы. В большинстве случаев с функцией связывается идентификатор^[en], но многие языки допускают и безымянные функции. С именем функции неразрывно связан адрес первой инструкции (оператора), входящей в функцию, которой передаётся управление при обращении к функции. После выполнения функции управление возвращается обратно в адрес возврата — точку программы, где данная функция была вызвана.

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

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

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

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

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

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

Примеры функций[ | ]

JavaScript[

структура и интерпретация. Часть I — «Хакер»

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

Я начал программировать еще в детстве, и годам к двадцати пяти мне казалось, что я все знаю и понимаю. Объектно ориентированное программирование стало частью моего мозга, все мыслимые книги о промышленном программировании были прочитаны. Но у меня оставалось такое ощущение, будто я что-то упустил, что-то очень тонкое и необыкновенно важное. Дело в том, что, как и многих в девяностые годы, в школе меня учили программировать на Pascal (о да, слава Turbo Pascal 5.5! — Прим. ред.), потом был C и C++. В университете Fortran и потом Java, как основной инструмент на работе. Я знал Python и еще несколько языков, но все это было не то. А серьезного образования в области Computer Science у меня не было. Однажды во время перелета через Атлантику я не мог заснуть, и мне захотелось что-то почитать. Каким-то волшебным образом у меня под рукой оказалась книга про язык программирования Haskell. Мне кажется, именно тогда я понял истинный смысл выражения «красота требует жертв».

Теперь, когда меня спрашивают, как я выучил Haskell, я так и говорю: в самолете. Этот эпизод изменил мое отношение к программированию вообще. Конечно, после первого знакомства многие вещи казались мне не вполне понятными. Пришлось напрячься и изучить вопрос более тщательно. И знаешь, прошло десять лет, многие функциональные элементы стали частью промышленных языков, лямбда-функции уже есть даже в Java, вывод типов — в С++, сопоставление с образцом — в Scala. Многие думают, что это какой-то прорыв. И в этой серии статей я расскажу тебе про приемы функционального программирования, используя разные языки и их особенности.

Интернетчики часто на потеху публике составляют всякие списки и топы. Например, «список книг, которые ты должен прочесть до тех пор, пока тебе не исполнилось тридцать». Если бы передо мной стояла задача сделать список книг по программированию, которые ты должен прочесть до тех пор, пока тебе сколько-то там не исполнилось, то первое место, безусловно, досталось бы книге Абельсона и Сассмана «Структура и интерпретация компьютерных программ». Мне даже иногда кажется, что компилятор или интерпретатор любого языка должен останавливать каждого, кто не читал эту книгу.

Поэтому если и есть язык, с которого нужно начинать изучение функционального программирования, так это Lisp. Вообще, это целое семейство языков, куда входит довольно популярный сейчас язык для JVM под названием Clojure. Но в качестве первого функционального языка он не особо подходит. Для этого лучше использовать язык Scheme, который был разработан в MIT и до середины двухтысячных годов служил основным языком для обучения программированию. Хотя сейчас вводный курс с тем же названием, что упомянутая книга, был заменен на курс по Python, она все еще не потеряла своей актуальности.

Обложка знаменитой книги «Структура и интерпретация компьютерных программ»

Постараюсь кратко рассказать о языке Scheme и вообще об идее, стоящей за языками данной группы. Несмотря на то что Lisp очень старый (из всех языков высокого уровня старше только Fortran), именно в нем впервые стали доступны многие методы программирования, применяемые сейчас. Далее я буду использовать название Lisp, имея в виду конкретную реализацию — Scheme.

Синтаксис в языке Lisp, хм, слегка спорный. Дело в том, что идея, лежащая в основе синтаксиса, крайне проста и построена на основе так называемых S-выражений. Это префиксная запись, в которой привычное тебе выражение 2 + 3 записывается как (+ 2 3). Это может показаться странным, но на практике дает некоторые дополнительные возможности. Кстати, (+ 2 10 (* 3.14 2)) тоже работает :). Таким образом, вся программа — это набор списков, в которых используется префиксная нотация. В случае языка Lisp сама программа и абстрактное синтаксическое дерево — «если вы понимаете, о чем я» 😉 — по сути, ничем не отличаются. Такая запись делает синтаксический анализ программ на Lisp очень простым.
Раз уж мы говорим о языке программирования, то следует сказать о том, как определять функции в этом языке.

Тут нужно сделать небольшое отступление. Существует одна тонкость, значимость которой в современной литературе недооценена. Нужно все-таки разделять функцию в математическом смысле и функцию, как мы ее понимаем в функциональном программировании. Дело в том, что в математике функции являются декларативными объектами, а в программировании они используются для организации процесса вычислений, то есть в каком-то смысле, скорее, представляют собой императивное знание, знание, отвечающее на вопрос «как?». Именно поэтому Абельсон и Сассман в своей книге это очень тщательно разделяют и называют функции в программировании процедурами. В современной литературе по функциональному программированию это не принято. Но я все же настоятельно рекомендую разделять эти два смысла слова «функция» хотя бы у себя в голове.

Самый простой способ определить функцию — это написать следующий код. Начнем с неприлично простого:

(define (sq-roots a b c)
   (let ((D (- (* b b) (* 4 a c))))
        (if (&lt; D 0)
          (list)
          (let ((sqrtD (sqrt D)))
               (let ((x1 (/ (- (- b) sqrtD) (* 2.0 a)))
                     (x2 (/ (+ (- b) sqrtD) (* 2.0 a))))
                    (list x1 x2))))))

Да, это именно то, что ты подумал, — решение квадратного уравнения на Scheme. Но этого более чем достаточно, чтобы разглядеть все особенности синтаксиса. Здесь sq-roots — это название функции от трех формальных параметров.

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

Теперь о выражениях. В нашей функции sq-roots мы использовали конструкцию if. Вот здесь-то и начинается функциональное программирование.

Дело в том, что в отличие от императивных языков, таких как C, в функциональных языках if — это выражение, а не оператор. На практике это означает, что у него не может отсутствовать ветка else. Потому что выражение всегда должно иметь значение.

Нельзя рассказать про синтаксис, не поговорив о синтаксическом сахаре. В языках программирования синтаксическим сахаром называют конструкции, которые не являются необходимыми, а лишь облегчают чтение и переиспользование кода. Для начала приведем классический пример из языка C. Многие знают, что массивы не обязательное средство выражения, так как есть указатели. Да, действительно, массивы реализованы через указатели, и a[i] для языка C — это то же самое, что и *(a + i). Данный пример вообще довольно необычный, с ним связан забавный эффект: так как операция сложения остается коммутативной в случае указателей, то последнее выражение — это то же самое, что и *(i + a), а это может быть получено при удалении синтаксического сахара из выражения i[a]! Операция удаления синтаксического сахара в английском языке называется специальным словом desugaring.

Возвращаясь к языку Scheme, следует привести важный пример синтаксического сахара. Для определения переменных, как и в случае функций, используется ключевое слово (в Lisp и Scheme это называется специальной формой) define. К примеру, (define pi 3.14159) определяет переменную pi. Вообще говоря, точно так же можно и определять функции:

(define square (lambda (x) (* x x)))

это то же самое, что и

(define (square x) (* x x))

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

Если посмотреть на let с точки зрения лямбда-выражения, то легко заметить следующее соответствие:

(let ((x 5) (y 2)) (* x y))
(apply (lambda (x y) (* x y)) (list 5 2))

Здесь оба выражения можно считать эквивалентными, а apply просто применяет функцию к списку аргументов.

Функциональные языки бывают чистыми и нечистыми. Чистые функциональные языки сравнительно редки, к ним относятся в первую очередь Haskell и Clean. В чистых языках нет побочных эффектов. На практике это означает отсутствие присваивания и ввода-вывода в том виде, к которому мы привыкли. Это создает ряд трудностей, хотя в уже упомянутых языках это решено довольно хитроумно, и на этих языках пишут код с большим количеством ввода-вывода. Языки типа Lisp, OCaml или Scala допускают функции с побочными эффектами, и в этом смысле данные языки зачастую более практичны.

Наша задача — изучить основные приемы функционального программирования на Scheme. Поэтому мы будем писать чисто функциональный код, без использования генератора случайных чисел, ввода-вывода и функции set!, которая позволят менять значения переменных. Обо всем этом можно прочитать в книге SICP. Сейчас остановимся на самом существенном для нас.

Первое, что смущает начинающего в функциональном программировании, — это отсутствие циклов. А как же быть? Многих из нас учат, что рекурсия — это плохо. Аргументируется это тем, что рекурсия в обычных языках программирования обычно реализована неэффективно. Дело в том, что в общем случае следует различать рекурсию как технический прием, то есть вызов функции из самой себя, и рекурсию как процесс. В функциональных языках поддерживается оптимизация хвостовой рекурсии или, как иногда говорят, рекурсии с аккумулятором. Это можно проиллюстрировать на простом примере.

Пускай у нас есть две функции — succ и prev. Первая возвращает число, на 1 большее, чем аргумент, а вторая — на 1 меньшее. Теперь попробуем определить операцию сложения, причем двумя способами:

(define (add x y)
  (if (eq? y 0) x (add (succ x) (prev y))))

(define (add-1 x y)
  (if (eq? y 0) x (succ (add-1 x (prev y)))))

В чем разница между первым и вторым случаем? Дело в том, что если рассмотреть способ вычисления для первого случая по шагам, то можно увидеть следующее:

(add 3 4) =&gt;
(add 4 3) =&gt;
(add 5 2) =&gt;
(add 6 1) =&gt;
(add 7 0) =&gt;
7

Во втором случае мы будем иметь примерно следующее:

(add-1 3 4) =&gt;
(succ (add-1 3 3)) =&gt;
(succ (succ (add-1 3 2))) =&gt;
(succ (succ (succ (add-1 3 1)))) =&gt;
(succ (succ (succ (succ (add-1 3 0))))) =&gt;
(succ (succ (succ (succ 3)))) =&gt;
(succ (succ (succ 4))) =&gt;
(succ (succ 5)) =&gt;
(succ 6) =&gt;
7

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

Один из важнейших элементов функционального программирования, наряду с рекурсией, — списки. Они обеспечивают основу для сложных структур данных. Как и в других функциональных языках, списки являются односвязными по принципу голова — хвост. Для создания списка используется функция cons, а для доступа к голове и хвосту списка — функции car и cdr соответственно. Так, список (list 1 2 3) — это не что иное, как (cons 1 (cons 2 (cons 3 '()))). Здесь '() — пустой список. Таким образом, типичная функция обработки списка выглядит так:

(define (sum lst)
  (if (null? lst)
    0
    (+ (car lst) (sum (cdr lst)))))

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

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

(define (map f lst)
  (if (null? lst)
    lst
    (cons (f (car lst)) (map f (cdr lst)))))

Функция map применяет функцию f к каждому элементу списка. Как бы это странно ни выглядело, но теперь мы можем выразить функцию вычисления длины списка length через sum и map:

(define (length lst)
   (sum (map (lambda (x) 1) lst)))

Если ты вдруг сейчас решил, что все это как-то слишком просто, то давай подумаем вот над чем: как сделать реализацию списков, используя функции высших порядков?

То есть нужно реализовать функции cons, car и cdr так, чтобы они удовлетворяли следующему соотношению: для любого списка lst верно, что значение (cons (car lst) (cdr lst)) совпадает с lst. Это можно сделать следующим образом:

(define (cons x xs)
  (lambda (pick)
    (if (eq? pick 1) x xs)))

(define (car f) (f 1))

(define (cdr f) (f 2))

Как это работает? Здесь функция cons возвращает другую функцию, которая имеет один параметр и в зависимости от этого возвращает либо первый, либо второй аргументы. Легко проверить, что необходимое соотношение выполняется для этих функций.

Одна приятная особенность языка Lisp делает его необыкновенно удобным для написания программ, которые занимаются преобразованием других программ. Дело в том, что программа состоит из списков, а список — это основная структура данных в языке. Существует способ просто «закавычить» текст программы, чтобы она воспринималась как список атомов.

Атомы — это просто символьные выражения, к примеру ('hello 'world), что то же самое, что и '(hello world), или в полной форме (quote (hello world)). Несмотря на то что в большинстве диалектов Lisp есть строки, иногда можно обходиться quote. Что более важно, с помощью такого подхода можно упростить кодогенерацию и обработку программ.

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

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

Так что я лишь приведу пример кода, который бы показывал суть дела, детали оставлю читателю (который, как я надеюсь, тщательно изучит книгу «Структура и интерпретация компьютерных программ»).

(define (deriv exp var)
  (cond ((number? exp) 0)
    ((variable? exp)
     (if (same-variable? exp var) 1 0))
    ((sum? exp)
     (make-sum (deriv (addend exp) var)
               (deriv (augend exp) var)))
    ((product? exp)
     (make-sum
       (make-product (multiplier exp)
                     (deriv (multiplicand exp) var))
       (make-product (deriv (multiplier exp) var)
                     (multiplicand exp))))
    (else
     (error "unknown expression type - DERIV" exp))))

Здесь функция deriv представляет собой реализацию алгоритма дифференцирования так, как его проходят в школе. Данная функция требует реализации функций number?, variable? и так далее, которые позволяют понять, какую природу имеет тот или иной элемент выражения. Также нужно реализовать дополнительные функции make-product и make-sum. Здесь используется пока неизвестная нам конструкция cond — это аналог оператора switch в таких языках программирования, как C и Java.

Перед тем как мы перейдем к реализации недостающих функций, стоит отметить, что в функциональном программировании довольно часто используется top-down подход к разработке. Это когда сначала пишутся самые общие функции, а затем небольшие функции, отвечающие за детали реализации.

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))

(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multiplicand p) (caddr p))

Реализация данных функций не требует специальных комментариев, за исключением, может быть, функций cadr и caddr. Это не что иное, как функции, которые возвращают второй и третий элементы списка соответственно.

Если воспользоваться интерактивным интерпретатором Scheme, то легко убедиться, что полученный код работает правильно, но без упрощения выражений:

(deriv '(+ x 3) 'x) =&gt;
(+ 1 0)
(deriv '(* (* x y) (+ x 3)) 'x) =&gt;
(+ (* (* x y) (+ 1 0))
(* (+ (* x 0) (* 1 y)) (+ x 3)))

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

Как и любой диалект, Lisp имеет большие возможности в метапрограммировании, по большей части связанные с использованием макросов. К сожалению, этот вопрос требует разбора в отдельной статье.

Давай напишем функцию, которая будет удалять синтаксический сахар из определения функции так, как это обсуждалось ранее:

(define (desugar-define def)
  (let ((fn-args (cadr def))
        (body (caddr def)))
  (let ((name (car fn-args))
        (args (cdr fn-args)))
       (list 'define name (list 'lambda args body)))))

Эта функция прекрасно работает с правильно сформированными определениями функций:

(desugar-define '(define (succ x) (+ x 1))) =&gt;
(define succ (lambda (x) (+ x 1)))

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

(define (sugared? def)
  (and (eq? (car def) 'define)
       (list? (cadr def))))

Такую проверку можно встроить прямо в функцию desugar-define, сделав так, чтобы в случае, если определение не нуждается в удалении синтаксического сахара, оно просто бы не менялось (данное тривиальное упражнение остается читателю). После чего можно обернуть всю программу в список и использовать map:

(map desugar-define prog)

В данной статье я не ставил себе задачу рассказать про Scheme сколь-нибудь подробно. Мне прежде всего хотелось показать несколько интересных особенностей языка и привлечь читателя к изучению функционального программирования. Этот чудесный язык при всей его простоте имеет свое очарование и особенности, которые делают программирование на нем очень увлекательным. Что касается инструмента для работы со Scheme, то сильные духом могут замахнуться на MIT-Scheme, а остальные — пользуйтесь прекрасной учебной средой Dr. Racket. В одной из следующих статей я обязательно расскажу, как написать собственный интерпретатор Scheme.

Что такое функциональное программирование? Учебное пособие с примером

Home
Тестирование
- - Назад
  - Agile Testing
  - BugZilla
  - Cucumber
  - Тестирование базы данных
  - 000 JTL
  - 000
  - 000 JR
  - 000 9274000
  - LoadRunner
  - Ручное тестирование
  - Мобильное тестирование
  - Mantis
  - Почтальон
  - QTP
  - Назад
  - Центр качества (ALM)
  - RPA
  - SAP Testing
  - 000
  - RPA
  - 0003 SAP Testing Management
SAP
- - Назад
  - ABAP
  - APO 9 0004
  - Начинающий
  - Basis
  - BODS
  - BI
  - BPC
  - CO
  - Назад
  - CRM
  - Crystal Reports
  - FICO
  - 000
  Назад
- Web
- - Интернет AngularJS
  - ASP.Net
  - C
  - C #
  - C ++
  - CodeIgniter
  - СУБД
  - JavaScript
  - Назад
  - Java
  - JSP
  - Kotlin
  - Linux
  - Linux
  - Kotlin
  - Linux
  - Perl
  - Назад
  - PHP
  - PL / SQL
  - PostgreSQL
  - Python
  - ReactJS
  - Ruby & Rails
  - Scala
  - SQL
  - SQL
  - UML
  - VB.Net
  - VBScript
  - Веб-службы
  - WPF
Обязательно учите!
- - Назад
  - Бухгалтерский учет
  - Алгоритмы
  - Android
  - Блокчейн
  - Business Analyst
  - Создание веб-сайта
  - CCNA
  - Облачные вычисления
  - 00030003 COBOL 9000 Compiler
    - 00030002 9000 Compiler 9000
    - Ethical Hacking
    - Учебники по Excel
    - Программирование на Go
    - IoT
    - ITIL
    - Jenkins
    - MIS
    - Сеть
    - Операционная система
    - Назад
    - Управление проектами Обзоры
    - Salesforce
    - SEO
    - Разработка программного обеспечения
    - VB A
- Big Data
  - - Назад
    - AWS
    - BigData
    - Cassandra
    - Cognos
    - Хранилище данных
    - HBOps
    - HBOps
    - MicroStrategy
.
Функциональное программирование: концепции, преимущества и приложения
Функциональное программирование — это парадигма программирования, в которой пытаются связать все и вся в чисто математических функциях. Это декларативный тип стиля программирования, который фокусируется на том, что решать, а не на том, как решать (нацеленный на императивный стиль программирования).
Clojure, Common Lisp, Erlang, Haskell и Scala — одни из наиболее известных языков программирования, следующих за подходом функционального программирования.Парадигма программирования основана на лямбда-исчислении, которое кратко объясняется ниже:
Лямбда-исчисление
Вместо операторов используются выражения. В отличие от оператора, который выполняется для присвоения переменных, оценка выражения дает значение. Лямбда-исчисление составляет основу почти всех используемых языков функционального программирования.
Разработанная Алонзо Черчем программа Lambda Calculus представляет собой основу для изучения вычислений с функциями.Все, что можно вычислить с помощью лямбда-исчисления, вычислимо. Удивительно, но его можно назвать самым емким языком программирования из всех.
По своим вычислительным возможностям лямбда-исчисление похоже на машину Тьюринга, заложившую основу императивного стиля программирования. Проще говоря, лямбда-исчисление представляет собой теоретическую основу, описывающую функции и их оценку.
Это концепции
Есть 5 самых важных концепций.
Чистые функции
Чистые функции имеют два важных свойства:
- Всегда производить один и тот же результат с одинаковыми аргументами без учета других факторов. Это свойство также известно как неизменность
- Детерминированы. Чистые функции либо выдают какой-либо результат, либо изменяют любой аргумент или глобальные переменные, т.е. у них нет побочных эффектов
Поскольку чистые функции не имеют побочных эффектов или скрытого ввода-вывода, программы, построенные с использованием функциональной парадигмы, легко отлаживать.Более того, чистые функции упрощают написание параллельных приложений.
Когда код написан с использованием стиля функционального программирования, соответствующий компилятор может:
- Запомните результаты
- Распараллелить инструкции
- Дождитесь оценки результатов
Рекурсия
В парадигме функционального программирования нет циклов for и while. Вместо этого языки функционального программирования полагаются на рекурсию для итерации.Рекурсия реализуется с помощью рекурсивных функций, которые повторно вызывают себя, пока не будет достигнут базовый вариант.
Ссылочная прозрачность
Переменным, однажды определенным на функциональном языке программирования, не разрешается изменять значение, которое они хранят на протяжении всего выполнения программы. Это известно как ссылочная прозрачность. Это гарантирует, что одно и то же языковое выражение дает одинаковый результат.
Функциональные программы не имеют операторов присваивания.Для сохранения дополнительных значений в программе, разработанной с использованием функционального программирования, необходимо определить новые переменные. Состояние переменной в такой программе постоянно в любой момент времени.
Ссылочная прозрачность устраняет даже малейшие шансы любых нежелательных эффектов из-за того, что любую переменную можно заменить ее фактическим значением в любой момент выполнения программы.
Функции первого класса и могут быть более высокого порядка
Функции в стиле функционального программирования обрабатываются как переменные.Следовательно, они являются первоклассными функциями. Эти первоклассные функции могут быть переданы другим функциям в качестве параметров, возвращены из функций или сохранены в структурах данных.
Функция высшего порядка — это функция, которая принимает другие функции в качестве аргументов и / или возвращает функции. Функции первого класса могут быть функциями высшего порядка в языках функционального программирования.
Переменные неизменяемые
Переменные неизменяемы, т. Е. Невозможно изменить переменную после ее инициализации.Хотя мы можем создать новую переменную, изменение существующих переменных запрещено.
Неизменяемость переменных в функциональном языке программирования дает преимущества в форме сохранения состояния на протяжении всего выполнения программы.
Преимущества
- Поскольку чистые функции не изменяют никаких состояний и полностью зависят от ввода, их легко понять. Возвращаемое значение, предоставляемое такими функциями, такое же, как результат, производимый ими.Аргументы и тип возвращаемого значения чистых функций выдаются их сигнатурой функции.
- Из-за природы чистых функций, позволяющих избежать изменения переменных или каких-либо данных за ее пределами, реализация параллелизма становится эффективной
- Он поддерживает концепцию ленивого вычисления, что означает, что значение оценивается и сохраняется только тогда, когда оно требуется.
- Чистые функции принимают аргументы один раз и выдают неизменяемый результат. Следовательно, они не производят скрытого вывода. Они используют неизменяемые значения, что упрощает отладку и тестирование.
- Этот стиль рассматривает функции как значения и передает их другим функциям как параметры. Это улучшает понимание и читаемость кода.
Недостатки
- Неизменяемые значения в сочетании с рекурсией могут привести к снижению производительности
- В некоторых случаях запись чистых функций приводит к ухудшению читаемости кода
- Хотя писать чистые функции легко, объединить их с остальной частью приложения, а также с операциями ввода-вывода сложно.
- Написание программ в рекурсивном стиле вместо использования для них циклов может быть сложной задачей
Приложения
Часто функциональные языки программирования предпочитают использовать в академических целях, а не для разработки коммерческого программного обеспечения.
Тем не менее, несколько известных языков программирования, следующих парадигме функционального программирования, таких как Clojure, Erlang, F #, Haskell и Racket, широко используются для разработки множества коммерческих и промышленных приложений.
WhatsApp использует Erlang, язык программирования, следующий парадигме функционального программирования, чтобы позволить более чем 100 сотрудникам управлять данными, принадлежащими более чем 1,5 миллиардам человек.
Другой важный знаменосец стиля функционального программирования — Haskell.Он используется Facebook в своей системе защиты от спама. Даже JavaScript, один из наиболее широко используемых языков программирования, демонстрирует свойства динамически типизированного функционального языка.
Более того, функциональный стиль программирования важен для того, чтобы различные языки программирования вели в разных областях. Например, R в статистике и J, K и Q в финансовом анализе.
Некоторые элементы этой парадигмы программирования даже используются предметно-ориентированными декларативными языками, такими как Lex / Yacc и SQL, для исключения изменяемых значений.
Как правило, эта парадигма широко используется в:
- Приложения, нацеленные на параллелизм или параллелизм
- Проведение математических вычислений
Сводка
Помимо чисто функциональных языков программирования, можно также установить функциональный подход к программированию на нефункциональных языках программирования. Есть несколько книг по этой теме.
В
C ++ 11, C # 3.0 и Java 8 добавлены конструкции для облегчения стиля функционального программирования.Одним из наиболее ярких примеров императивного языка программирования, использующего функциональный стиль программирования, является язык программирования Scala.
Хотя Scala обычно написана в функциональном стиле, она имеет побочные эффекты и изменяемые состояния. Следовательно, язык программирования может быть помещен в промежуточное состояние между императивным и функциональным стилями программирования.
Еще читают:
.
Введение в функциональное программирование на F #
- 29.10.2018
- 8 минут на чтение
В этой статье
Функциональное программирование — это стиль программирования, в котором упор делается на использование функций и неизменяемых данных. Типизированное функциональное программирование — это когда функциональное программирование сочетается со статическими типами, такими как F #.В целом, в функциональном программировании подчеркиваются следующие концепции:
- Функции как основные конструкции, которые вы используете
- Выражения вместо утверждений
- Неизменяемые значения переменных
- Декларативное программирование важнее императивного
В этой серии статей вы изучите концепции и шаблоны функционального программирования с использованием F #. Попутно вы также научитесь F #.
Терминология
Функциональное программирование, как и другие парадигмы программирования, содержит словарь, который вам в конечном итоге понадобится выучить.Вот несколько общих терминов, которые вы будете встречать постоянно:
- Функция — функция — это конструкция, которая производит вывод при задании ввода. Более формально он отображает элемент из одного набора в другой набор. Этот формализм во многом воплощается в жизнь, особенно при использовании функций, работающих с коллекциями данных. Это самая основная (и важная) концепция функционального программирования.
- Выражение — Выражение — это конструкция в коде, которая производит значение.В F # это значение должно быть привязано или явно проигнорировано. Выражение можно тривиально заменить вызовом функции.
- Чистота — Чистота — это такое свойство функции, что ее возвращаемое значение всегда одинаково для одних и тех же аргументов и что ее оценка не имеет побочных эффектов. Чистая функция полностью зависит от своих аргументов.
- Ссылочная прозрачность — Ссылочная прозрачность — это свойство выражений, позволяющее заменять их выводом, не влияя на поведение программы.
- Неизменяемость — Неизменяемость означает, что значение не может быть изменено на месте. Это контрастирует с переменными, которые могут меняться на месте.
Примеры
Следующие примеры демонстрируют эти основные концепции.
Функции
Самая распространенная и фундаментальная конструкция в функциональном программировании — это функция. Вот простая функция, которая добавляет 1 к целому числу:
```
  пусть addOne x = x + 1
  
```
Его подпись типа следующая:
```
  val addOne: x: int -> int
  
```
Подпись может быть прочитана так: « addOne принимает int с именем x и создаст int ».Более формально, addOne — это , отображающий значение из набора целых чисел в набор целых чисел. Маркер -> обозначает это сопоставление. В F # вы обычно можете посмотреть на сигнатуру функции, чтобы понять, что она делает.
Итак, почему важна подпись? В типизированном функциональном программировании реализация функции часто менее важна, чем фактическая сигнатура типа! Тот факт, что addOne добавляет значение 1 к целому числу, интересен во время выполнения, но когда вы создаете программу, тот факт, что она принимает и возвращает int , говорит о том, как вы на самом деле будете использовать эту функцию.Более того, если вы правильно используете эту функцию (в отношении сигнатуры ее типа), диагностика любых проблем может выполняться только в теле функции addOne . Это толчок к типизированному функциональному программированию.
Выражения
Выражения — это конструкции, которые вычисляют значение. В отличие от операторов, выполняющих действие, выражения можно рассматривать как выполнение действия, которое возвращает значение. В функциональном программировании выражения почти всегда используются вместо операторов.
Рассмотрим предыдущую функцию addOne . Тело addOne — это выражение:
```
  // 'x + 1' - это выражение!
пусть addOne x = x + 1
  
```
Это результат этого выражения, который определяет тип результата функции addOne . Например, выражение, составляющее эту функцию, может быть изменено на другой тип, например, строка :
```
  пусть addOne x = x.ToString () + "1"
  
```
Теперь подпись функции:
```
  val addOne: x: 'a -> строка
  
```
Поскольку для любого типа в F # может быть вызвана ToString () , тип x был сделан универсальным (так называемое автоматическое обобщение), а результирующий тип — это строка .
Выражения — это не просто тела функций. У вас могут быть выражения, которые производят значение, которое вы используете в другом месте. Обычный — , если :
```
  // Проверяет, нечетно ли 'x' с помощью оператора mod
пусть isOdd x = x% 2 <> 0

пусть addOneIfOdd input =
    пусть результат =
        если вход isOdd, то
            ввод + 1
        еще
            ввод

    результат
  
```
Выражение if дает значение результат . Обратите внимание, что вы можете полностью опустить результат , сделав выражение if телом функции addOneIfOdd .Главное, что нужно помнить о выражениях, — это то, что они производят значение.
Есть специальный тип, unit , который используется, когда нечего возвращать. Например, рассмотрим эту простую функцию:
```
  пусть printString (str: string) =
    printfn "Строка:% s" str
  
```
Подпись выглядит так:
```
  val printString: str: string -> unit
  
```
Блок Тип указывает, что фактическое значение не возвращается.Это полезно, когда у вас есть подпрограмма, которая должна «работать», несмотря на то, что в результате этой работы у нее нет возвращаемого значения.
Это резко контрастирует с императивным программированием, где эквивалент , если конструкция является оператором, а создание значений часто выполняется с изменяющимися переменными. Например, в C # код может быть записан так:
```
  bool IsOdd (int x) => x% 2! = 0;

int AddOneIfOdd (ввод целого числа)
{
    var result = input;

    если (IsOdd (ввод))
    {
        результат = ввод + 1;
    }

    вернуть результат;
}
  
```
Стоит отметить, что C # и другие языки в стиле C действительно поддерживают тернарное выражение, что позволяет использовать условное программирование на основе выражений.
В функциональном программировании редко можно изменять значения с помощью операторов. Хотя некоторые функциональные языки поддерживают операторы и изменения, эти концепции не часто используются в функциональном программировании.
Чистые функции
Как упоминалось ранее, чистые функции — это функции, которые:
- Всегда вычислять одно и то же значение для одного и того же входа.
- Не имеет побочных эффектов.
В этом контексте полезно подумать о математических функциях.В математике функции зависят только от своих аргументов и не имеют побочных эффектов. В математической функции f (x) = x + 1 значение f (x) зависит только от значения x . То же самое и с чистыми функциями в функциональном программировании.
При написании чистой функции функция должна зависеть только от своих аргументов и не выполнять никаких действий, приводящих к побочным эффектам.
Вот пример нечистой функции, поскольку она зависит от глобального изменяемого состояния:
```
  пусть изменяемое значение = 1

пусть addOneToValue x = x + значение
  
```
Функция addOneToValue явно нечистая, потому что значение может быть изменено в любое время, чтобы иметь значение, отличное от 1.Этого шаблона зависимости от глобального значения следует избегать в функциональном программировании.
Вот еще один пример нечистой функции, потому что она выполняет побочный эффект:
```
  пусть addOneToValue x =
    printfn "x is% d" x
    х + 1
  
```
Хотя эта функция не зависит от глобального значения, она записывает значение x в вывод программы. Хотя в этом нет ничего плохого, это означает, что функция не чистая.Если другая часть вашей программы зависит от чего-то внешнего по отношению к программе, например от буфера вывода, то вызов этой функции может повлиять на эту другую часть вашей программы.
Удаление оператора printfn делает функцию чистой:
```
  пусть addOneToValue x = x + 1
  
```
Хотя эта функция по своей сути не лучше , чем предыдущая версия с оператором printfn , она действительно гарантирует, что все, что эта функция делает, это возвращает значение.Вызов этой функции любое количество раз дает один и тот же результат: она просто возвращает значение. Предсказуемость, обеспечиваемая чистотой, — это то, к чему стремятся многие функциональные программисты.
Неизменность
Наконец, одна из самых фундаментальных концепций типизированного функционального программирования — неизменяемость. В F # все значения по умолчанию неизменяемы. Это означает, что они не могут быть изменены на месте, если вы явно не отметите их как изменяемые.
На практике работа с неизменяемыми значениями означает, что вы меняете свой подход к программированию с «Мне нужно что-то изменить» на «Мне нужно создать новое значение».
Например, добавление 1 к значению означает создание нового значения, а не изменение существующего:
```
  пусть значение = 1
пусть secondValue = значение + 1
  
```
В F # следующий код не , а не изменяет значение функции ; вместо этого он выполняет проверку равенства:
```
  пусть значение = 1
value = value + 1 // Производит логическое значение!
  
```
Некоторые языки функционального программирования вообще не поддерживают мутацию. В F # это поддерживается, но это не поведение по умолчанию для значений.
Эта концепция распространяется даже на структуры данных. В функциональном программировании неизменяемые структуры данных, такие как наборы (и многие другие), имеют другую реализацию, чем вы могли изначально ожидать. По сути, что-то вроде добавления элемента в набор не изменяет набор, а создает новый набор с добавленным значением. Скрытно это часто достигается с помощью другой структуры данных, которая позволяет эффективно отслеживать значение, чтобы в результате могло быть получено соответствующее представление данных.
Этот стиль работы со значениями и структурами данных очень важен, поскольку он заставляет вас рассматривать любую операцию, которая что-то изменяет, как если бы она создала новую версию этого. Это позволяет обеспечить согласованность в ваших программах таких вещей, как равенство и сопоставимость.
Следующие шаги
В следующем разделе подробно рассматриваются функции и исследуются различные способы их использования в функциональном программировании.
Первоклассные функции глубоко исследуют функции, показывая, как их можно использовать в различных контекстах.
Дополнительная литература
Серия «Функциональное мышление» — еще один отличный ресурс для изучения функционального программирования на F #. В нем прагматично и легко читается основы функционального программирования с использованием функций F # для иллюстрации концепций.
.
Страница не найдена · GitHub Pages
Страница не найдена · GitHub Pages
Файл не найден
Сайт, настроенный по этому адресу, не
содержать запрошенный файл.
Если это ваш сайт, убедитесь, что регистр имени файла соответствует URL-адресу.
Для корневых URL (например, http://example.com/ ) вы должны предоставить
index.html файл.
Прочтите полную документацию
для получения дополнительной информации об использовании GitHub Pages .
.
No related posts.

Пн	Вт	Ср	Чт	Пт	Сб	Вс
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Функция программирование: Понятие функции в программировании — SqrTT

Функция (программирование) — это… Что такое Функция (программирование)?

Побочный эффект

Функции и процедуры

Аргументы и параметры

Функция без аргументов

См. также

Ссылки

Чем отличаются понятия функции, процедуры и метода в программировании? — Хабр Q&A

Что такое функциональное программирование

🤔 Функциональное — это про функции?

Метафора: инструкция или книга правил

Императивное программирование

Функциональное программирование

Типы и функции / Хабр

Кому нужны типы?

Типы нужны для компонуемости

Что такое типы?

Зачем нам математическая модель?

Чистые и Грязные функции

Примеры типов

Функция (программирование) Википедия

Примеры функций[ | ]

JavaScript[

структура и интерпретация. Часть I — «Хакер»

Что такое функциональное программирование? Учебное пособие с примером

Функциональное программирование: концепции, преимущества и приложения

Лямбда-исчисление

Это концепции

Чистые функции

Рекурсия

Ссылочная прозрачность

Функции первого класса и могут быть более высокого порядка

Переменные неизменяемые

Преимущества

Недостатки

Приложения

Введение в функциональное программирование на F #

В этой статье

Терминология

Примеры

Функции

Выражения

Чистые функции

Неизменность

Следующие шаги

Дополнительная литература

Страница не найдена · GitHub Pages

Добавить комментарий Отменить ответ