Подпрограммы, процедуры, функции, методы и лямбды

Начнем со сложного

Глоссарий

• Ассемблер - если вы даже примерно не знаете, что это такое, то первую часть статьи вероятно можно пролистать и перейти на обсуждение парадигм.
• Регистр - именованная численная переменная внутри процессора. Может иметь особое предназначение, а может просто использоваться для хранения любых чисел и арифметики. Их немного.
  
• Инструкция - одиночная команда, представляет из себя последовательность из нескольких байт со специальным значением. Любая программа представляет из себя последовательность инструкций внутри памяти. Указатель на инструкцию, которая будет выполнена следующей, содержится в регистре IP, который сам увеличивается после выполнения каждой инструкции. По-хорошему стоило нарисовать пошаговую наглядную анимацию с демонстрацией всех регистров и куском ассемблерного кода, но мне лень, а в гугле я ничего толкового не нашел.
• Метка - константа, содержащая адрес чего-либо. К примеру процедуры или глобальной переменной.  Примерно как метка для goto в высокоуровневых языках, но универсальнее. Применяются при написании на ассемблере, в процессоре как таковые не существуют и разрушаются до обычных чисел при ассемблировании и линковке.
• Разыменование - операция над указателем, когда тот превращается в переменную с адресом, который был записан в указателе (своеобразный пульт Д/У для переменной). 
• Парадигма - "стиль" написания и постройки архитектуры программы, частично определяется языком. Технически на том же C можно писать в практически любой парадигме (через костыли можно писать в стиле ООП, через макросы реализовать метапрограммирование, а через нестандартные расширения вообще ядерный бред), но родная для него - процедурная. А Go, к примеру, хоть и имеет недоклассы и методы, но лишен практически всех благ ООП и не сильно далеко ушел от C.
• Синтаксический сахар - необязательная возможность, которая сокращает количество кода, повышает его читаемость или удобство поддержки

Стек

Большинство процессоров Фон-Неймановской архитектуры в своей конструкции предлагают механизмы стека. Кто играл в покер должны вспомнить стеки фишек. То есть некие значения, сложенные друг на друга (обычно это переменные, в частности адреса в памяти). При этом основными операциями являются добавление фишки на вершину (инструкция PUSH) и ее снятие (инструкция POP). Еще можно косвенно читать и заменять (перезаписывать) фишки относительно вершины (на вершину указывает регистр SP, неявно обновляется через POP и PUSH) или основания (указывает регистр BP) вглубь.

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

А на этом адресе может быть функция. Сначала она кладет текущий BP на стек, после чего приравнивает основание к вершине (BP к SP), тем самым создав для себя "новый стек" сразу после предыдущего (это еще называется стековым кадром), в котором якобы лежит только значение старого основания стека (BP), чтобы можно было восстановить его перед возвратом.

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

После чего функция восстанавливает старое значение BP, сняв его со стека, и выполняет команду RET, которая снимает со стека адрес возврата и совершает переход на него, тем самым переключившись на инструкцию сразу после CALL.

И эта система так или иначе перекочевала в большинство высокоуровневых языков начиная с FORTRAN. К примеру в C CALL превратился в круглые скобки, RET в return, а адреса и метки в имена (при этом без скобок они все еще являются указателями, то есть адресами).

Пример кода (к сожалению, штатного форматирования не предусмотрено):

#include <stdio.h>
int pow2(int x) {
    return x * x;
}
int main() {
    int y = pow2(16); // Вызов функции. В y будет сохранено число 256
    printf("%p", pow2); // Без скобок вместо вызова просто выведет адрес функции
    return 0; // Возврат нуля из главной функции означает отсутствие ошибок.
}

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

А теперь скомпилируем этот код и разберем ассемблерный листинг

Интерактивный компилятор и дизассемблер. (printf я убрал для упрощения, его наличие добавляет слишком много лишних инструкций).

Важно понимать, что стек в большинстве архитектур традиционно растет от больших адресов к меньшим (и в x86). То есть для того, чтобы отодвинуть его вершину вверх, от регистра SP нужно отнимать значения, а вот для ужимания и съедания ненужных значений к указателю на вершину значения прибавляют. И для доступа к значениям относительно основания или вершины это тоже важно учитывать. Это может звучать запутанно, но через время привыкаешь и всё становится очевидным. 

Post scriptum

Это всё довольно упрощенно. Как минимум, в защищенном режиме используется больше 5 разных соглашений о вызове, которые отличаются деталями реализации. Это было описание для cdecl, обычно используемого в C. Еще часто используются соглашения pascal, fastcall, thiscall, winapi и другие. Fastcall, к примеру, избегает хранения аргументов на стеке, если их возможно передать через регистры, что улучшает производительность. А winapi отличается от cdecl тем, что функция сама очищает стек от аргументов для себя при возврате. А еще я упустил, к примеру, сохранение регистров, которые функция может перезаписать и испортить, а потому обязана предварительно сохранить и перед возвратом восстановить, передачу переменного количества аргументов (как в printf) и возврат значений шире 32 бит (которые не влезут в EAX).

Плюс сейчас мало кто компилирует ПО под защищенный 32-битный режим, а в длинном режиме (AMD64) используется пара других соглашений, основанных на fastcall и имеющих несколько отличий друг от друга.

Так процедура или функция? Или подпрограмма?

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

Процедура от функции отличается только тем, что функция возвращает какое-то значение (как в математике), а вот процедура этого не делает. Не во всех языках явно есть процедуры (в Pascal есть, но не в C). В таком случае их заменяют функции, возвращающие ничего (void, Unit, undefined, None).

Хотя и тут есть свои особенности. К примеру функция, возвращающая void в C и Java является прямым аналогом процедур, как-либо использовать возвращенное значение из такой функции невозможно, ибо его нет физически. А вот Unit в Kotlin это синглтон (а-ля единственная и уникальная константа уникального типа), ссылку на который можно присвоить в переменную, но в этом особого смысла нет. Undefined в JS и None в Python тоже уникальные константы специальных типов. 

Но не тут-то было

Вроде бы процедура никогда не может ничего вернуть...

Только она этого никогда не делает напрямую. При она этом может записать результат в глобальную переменную, а еще часто принимает в себя указатели или ссылки, по которым может записать результат. Это еще удобно тем, что можно "вернуть" несколько значений. Пример:

void procedure(int x1, int *x2, int *x3) { // Функция ничего не возвращает, то есть это процедура
    *x2 = x1 * x1; // Разыменовываем указатель и записываем по его адресу результат.
    *x3 = x1 * x1 * x1; // Разыменовываем другой указатель и записываем по его адресу результат.
}
int y1, y2;
procedure(16, &y1, &y2); // В y1 оказался результат, аналогичный прошлому примеру. А в y2 куб числа.

PS: оператор звездочка при указании типа превращает его в тип-указатель, а при применении на переменную-указатель разыменовывает ее до изначальной переменной. Амперсанд превращает переменную в указатель на нее (иногда еще называется оператором получения адреса).

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

Еще про связь с математикой

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

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

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

Чистые функции через ключевое слово pure явно есть в D и FORTRAN (проверка на чистоту во время компиляции), а также являются основой функционального программирования.

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

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

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

document.tags.A.color = "blue" /* Императивный (JSSS). Сделать ссылки синими */

a { color: blue } /* Декларативный (CSS). Ссылки должны быть синими */

Почувствуйте разницу.

И функциональное программирование я никогда не изучал и слишком мало о нем знаю. Так что готовьтесь к ошибкам и не воспринимайте всё за чистую монету.

Внутри чистого функционального программирования

Основано полностью на математике, все функции обязаны быть чистыми. Операция присваивания запрещена (разрешены константы), переменных в привычном виде нет. Прикольно? Очень!

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

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

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

Это не все особенности функциональных языков, но одни из самых важных. Самый известный такой язык: Haskell. Функциональные F#, Lisp, ML и многие другие не являются 100% чистыми.

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

Последнее время часто используются смешанные языки, к примеру вместе с процедурным или объектно-ориентированным программированием, что избавляет от ограничений математики, но дает гибкость в том, что функциями можно оперировать как с любыми другими типами данных, а еще дает много очень удобного сахара вроде замыканий и лямбд. Это C#, Python, JS, частично Java и C++ (в них нужны костыли в виде интерфейсов из одного метода или оберток над указателями).

Особенности

Функции как объект первого класса. К примеру в C# это реализовано через систему делегатов, которые представляют из себя тип-обертку для функций:

Action<string> printer = Console.WriteLine; // Action<string> - тип-делегат. Неявно создаем его объект и присваиваем туда функцию
printer("Hello, World!"); // Вызываем функцию через делегат

Локальные функции: как обычные, только вложенные в другую функцию (объявленные внутри нее)

void Func1() { // Глобальная функция
    void Func2() { // Локальная функция
        Console.WriteLine("В локальной функции");
    }
    Func2();
}

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

var pow2AsLambda = x => x * x; // => - оператор лямбда-выражения
pow2AsLambda(5); // Вернет 25

Замыкания (можно использовать вместе с лямбдами и локальными функциями):

int someValue = 42;
var pow2AsLambda = x => x * x + someValue; // someValue будет захвачено замыканием, хотя напрямую не передано
pow2AsLambda(5); // Вернет 67

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

ООП

Посмотрим на индекс TIOBE по популярности языков. Фиолетовым я пометил чистые функциональные языки. Языки, имеющие возможности, присущие функциональным языкам (смешанные) - синим, процедурным - красным, а объектно-ориентированным (ООП) - зеленым. Языки, в которых нельзя объявить функцию, принадлежащую самой себе или модулю, процедурными считать не совсем корректно (Java).

Видите фиолетовые точки? И я не вижу. А вот синих 12. В то же время красных и зеленых по 16. При этом реально применяемый чисто процедурный язык всего 1: С. Остальные имеют какую-либо встроенную поддержку других парадигм.

И сейчас практически всё большое ПО пишут в ООП. Ибо позволяет хоть как-то сдерживать структурированность кода после перехода с десятков тысяч строк к сотням (и миллионам).

Внутри

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

Структуры были удобным способом объединить несколько переменных в единое целое. Пример:

typedef struct user_struct {
    char *username;
    int userid;
    int reputation;
} user_t;
user_t someuser = { "IvanKr08", 17002, 253 }; // Инициализируем значениями
someuser.reputation += 10; // Обращаемся к полю

(Вместе с этим объявляем структуру новым типом через typedef, что не делается по умолчанию в C, в отличии от C++. Один из ярких примеров несовместимости C и C++):

После чего user_t превращается в новый тип, как int или char. Можно создать полноценную переменную типа user_t (или массив такого типа), а потом обратиться к какой-нибудь ее части (полю) через оператор точки (.). Можно сделать функцию, которая будет принимать или возвращать переменную типа user_t (к примеру someuser). Можно сделать указатель на user_t, тогда для обращение к полю используется оператор стрелки (->). Или можно встроить переменную типа одной структуры в другую, это тоже не запрещено. Внутри структурная переменная представляет из себя последовательно слепленные поля в одно целое.

Возвращаемся к ООП

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

Метод принципиально ничем не отличается от любой процедуры или функции, кроме того, что неявно принимает в себя специальный аргумент this (в Python это делается явно, в некоторых языках вместо this может быть self). Он содержит в себе ссылку/указатель на объект класса, от которого был вызван. Пример:

class User {
public:
    char *username;
    int userid;
    int reputation;

    void print() {
        printf("Пользователь \"%s\" (%i). Репутация: %i\n", this->username, this->userid, this->reputation);   
        // Постоянно писать this-> не обязательно. Если локальной переменной с таким именем нет, то будет произведен доступ к полю
    }
};
User someuser = { "IvanKr08", 17002, 253 }; // Инициализируем значениями
someuser.print(); // Вызвали метод, print() неявно получил в себя указатель this, который указывает на someuser
someuser.reputation += 10; // Обращаемся к полю
someuser.print(); // Теперь вывод поменяется

Да, никто не мешает объявить обычную функцию, которая будет явно принимать в себя указатель на User и ничего не поменяется, и так повсеместно делают в C (тот же WinAPI на этом построен целиком и полностью), но ООП на самом деле крайне сложная, большая и холиварная тема, которая развивалась на протяжении 60 лет в разных направлениях и которую поднимать тут глупо. Только опишу еще несколько разновидностей методов:

• Статичный метод - как обычный метод, только не получает в себя this и вызывается от имени класса, а не объекта (не someuser.method(), а User::method()). Зачем это нужно и в чем отличие от просто функции? Статичный метод можно спрятать за инкапсуляцией, плюс он привязан к классу, а не болтается в глобальном пространстве имен.
• Конструктор - автоматически вызывается при создании нового объекта. Может иметь аргументы, тогда обязан явно вызываться как функция с именем класса, т.е. User("IvanKr08", 17002, 253)
• Деструктор - есть в C++. В C# называется финализатором и имеет несколько важных отличий. Автоматически вызывается перед уничтожением объекта (к примеру выход из области видимости, явное удаление оператором delete или удаление сборщиком мусора в C#). Не может иметь аргументов.
  
• Свойство - есть в Delphi и C#, куда перешел от первого. С точки зрения синтаксиса это поле, которое можно читать и записывать, только вместо прямого обращения в память вызываются соответствующие методы (set и get). Пример:
  ...
  int SomeProperty{ get => 42; set => Console.WriteLine("Set"); }
  ...
  test.SomeProperty = 10; // Значение никуда не сохранится, будет выведено "Set" в консоль
  Console.WriteLine(test.SomeProperty); // Всегда будет 42
  
• Перегрузка оператора - специальный метод, который позволяет переопределить стандартные операции для типа. К примеру нельзя сложить два объекта User или User и число, но если перегрузить оператор +, то можно будет определить свою логику для этого (не обязательно, чтобы оно что-то реально складывало. Это может быть любое действие).
• Индексатор - синоним перегрузки оператора квадратных скобок. Объект начинает вести себя как массив.
  
• Функтор - перегрузка оператора круглых скобок (иначе называется перегрузкой оператора вызова функции). Позволяет "вызывать" объект так же, как и функцию. Звучит запутанно, но можно погуглить. Есть в C++. Также бывает функтор в функциональном программировании, но он не имеет ничего общего с функтором в C++.
• Виртуальная функция (метод) - самый интересный и сложный тип, составляет основу полиморфизма. Вкратце объяснить его невозможно, но одним из ключевых принципов ООП является наследование, то есть один класс (наследник) копирует в себя все поля и методы другого класса (родитель), и может добавить новые. И суть в том, что указатель (ссылка) на объект класса-наследника может быть присвоен в переменную-указатель родительского типа. А самое интересное то, что любые обращения (к примеру вызовы методов), сделанные через родительский указатель, будут вести себя аналогично обращениям, сделанным напрямую через указатель с типом наследника. Это называется полиформизмом. Но это было бы не слишком полезным, если бы не возможность объявить метод в родительском классе виртуальным, а в наследнике полностью переопределить его код.
• И то, что я забыл

Послесловие

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

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