Не понимаю, что такое замыкание (closure)

Это омонимы.

Первое это https://en.wikipedia.org/wiki/Closure_(mathematics).

Второе — https://en.wikipedia.org/wiki/Closure_(computer_science).

Получается просто, что процедура использует глобальные переменные

Не только глобальные, локальные тоже. Нестатический метод класса в C++ это тоже пример замыкания (lambda с captures — частный случай, то есть функциональный объект у которого operator() это нестатический метод).

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

Ясно, спасибо. Я хоть правильно sicp'овую идею понял?

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

в ФП есть — это быдлокод называется.

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

def counter():
    x = 0
    def increment(y):
        nonlocal x
        x += y
        print(x)
    return increment

эта функция возвращает замыкание из другой функции(increment()) и переменной x. Т.е. замыкание это такой хитрый объект, который является функцией с какими-то переменными, но эти переменные не являются локальными для функции.

В классических ЯП замыканий быть не может, т.к. нет нормальных объектов-функций. Имитации/костыли из C++11 не совсем то, хотя и работает.

Я хоть правильно sicp'овую идею понял?

в SICP совсем другое зовётся «замыканием».

Там есть сноска

6 The use of the word ``closure" here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The Lisp community also (unfortunately) uses the word ``closure" to describe a totally unrelated concept: A closure is an implementation technique for representing procedures with free variables. We do not use the word ``closure" in this second sense in this book.

То есть только первый смысл.

А замыкания во втором смысле всё равно повсюду используются — вложенные define и возвращение lambda из под define в часте про объекты, например.

Нестатический метод класса в C++ это тоже пример замыкания (lambda с captures — частный случай, то есть функциональный объект у которого operator() это нестатический метод).

/*
(define new-withdraw
  (let ((balance 100))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient funds"))))
*/

#include <memory>
#include <functional>
#include <iostream>

int main()
{

    /* As method. */

    {

        class NewWithdraw {
            
            int balance = 100;

        public:

            // Non-static method == closure over `balance`.
            int withdraw(const int amount) {
                return
                    balance >= amount
                    ? balance -= amount
                    : throw "Insufficient funds";
            }

        };

        NewWithdraw nw;

        // Proper functional object from class object and its method.
        auto withdraw = std::bind(&NewWithdraw::withdraw, &nw, std::placeholders::_1);
        try {
            // Call method.
            std::cout << nw.withdraw(50) << std::endl;
            // Call functional object (class object already captured).
            std::cout << withdraw(100) << std::endl;
        } catch(char const* error) {
            std::cout << error << std::endl;
        }

    }

    /* As lambda. */

    auto new_withdraw = []() {

        std::shared_ptr<int> balance(new int(100));

        // Lambda with captures == closure over `balance` again.
        return [=](const int amount) {
            return
                *balance >= amount
                ? *balance -= amount
                : throw "Insufficient funds";
        };

    };

    auto withdraw = new_withdraw();
    try {
        std::cout << withdraw(50) << std::endl;
        std::cout << withdraw(100) << std::endl;
    } catch(char const* error) {
        std::cout << error << std::endl;
    }

}

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

Примечательно, то что ЯП автоматом освождает переменную, как только более не окажется ссылок на нее если все функции завершились и не передали ссылку на эту переменную в другие функции. В итоге один раз написанный код с использованием замыканий при многократном вызове создаст множество копий/выделений области ОЗУ переменных. Изменения значений переменных никак не повлияют на «соседние», в отличие от глобальной переменной.

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

Я хоть правильно sicp'овую идею понял?

А как ты понял?

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

Что замкнутость операций это «круто»? :)

потому что операция над изображением - это изображение.

Не операция, а результат применения операции — изображение.

Есть тип, есть его значения и операции над этим типом из одних значений этого типа в другие (ещё может быть индексация операций по значениям каких-то других типов, то есть, фактически, семейства операций над основным типом). Дальше, замкнутость операций это не то чтобы круто или правильно, это просто так вещи устроены (предметная область или нечто промежуточное) — одни операции над типом могут быть замкнуты, другие — нет. Для «морально» замкнутых операций композиционность простого в более сложное это, конечно, хорошо и естественно, но только для них. Хорошая композиционность частичных операций над типом при этом требует дополнительных усилий по постоянной валидации данных.

Например, списки замкнуты под операцией конкатенации списков (имею полное право приплести сюда моноид, потому что речь про алгебраическое понятие замкнутости), но не замкнуты относительно операции получения списка первых n (вот тут — индексация в семейство унарных операций на типом списков для разных n) элементов списка (так как любая такая операция для n > 0, имея тип List -> List, частична и может вызывать исключения).

Другой пример — обобщённые контейнеры в современных ЯП (начиная где-то с STL, простые параметрически полиморфные ADT — с ML), в этом случае операции работают не над значениями какого-то типа, а над всеми типами — из одних (регулярных) типов можно сконструировать конструкторами типов новые (регулярные) типы и так далее, так что в итоге можно получать сложные вложенные контейнеры. Пример индексации в семейство в этом случае — std::array из C++ индексированный длинной массива.

То есть, существует некая (осознаваемая или нет) последовательность моделирования:

1) предметная область -> 2) абстрактные структуры -> 3) реализация.

Где-то на этапе 1 / 2 становится понятно какие операции замкнуты и могут подвергаться простой композиции (и если теперь смотреть на эти операции как на объекты, а на их композиции как на операции, то какая структура следующего порядка получается в этом случае?).

http://swizard.livejournal.com/124189.html

да, очень красиво и эффективно.

Остальное:

unlessM p x = p >>= flip unless x

syn f g h = f $ g <*> h

fromBinary path f = f =<< decodeFile path

fromBinaryList path f = mapM_ f =<< decodeFile path

synBinary path = syn (fromBinary path) (flip const) evaluate

synBinaryListToHT key path ht = syn (fromBinaryList path)
  (\x -> unlessM $ isJust <$> HT.lookup ht (key x)) (\x -> HT.insert ht (key x) x)

data User = User
  { _login :: !ByteString
  , _uid :: !Word
  , _gid :: !Word
  , _name :: !ByteString
  , _home :: !ByteString
  , _shell :: !ByteString
  } deriving ( Eq, Generic )
instance Binary User

synUsersToHTByName = synBinaryListToHT _name

test = do
  
  let root = User "root" 0 0 "root" "/root" "sh"
      user = User "user" 1 1 "user" "/user" "sh"
  
  encodeFile "/tmp/test1" root
  root' :: User <- synBinary "/tmp/test1"
  assert (root == root') $! return ()

  encodeFile "/tmp/test2" [root, user]
  ht :: BasicHashTable ByteString User <- HT.new
  synUsersToHTByName "/tmp/test2" ht
  root' <- HT.lookup ht "root"
  user' <- HT.lookup ht "user"
  assert (isJust root' && isJust user' && root == fromJust root' && user == fromJust user') $! return ()

вместо passwd тут сериализация от binary.

В классических ЯП замыканий быть не может

sub make_peniser {
    my $penis_msg = "PENIS\n";
    return sub { print $penis_msg; }
}

my $peniser = make_peniser();
$peniser->()

имелись ввиду «по настоящему» классические ЯП вроде фортрана или там сишечки. Но уж никак не скрипты.

имелись ввиду «по настоящему» классические ЯП вроде фортрана или там сишечки. Но уж никак не скрипты.

А чем скриптовые языки не «по-настоящему» классические? И уж тем более олдскульный perl.

А чем скриптовые языки не «по-настоящему» классические? И уж тем более олдскульный perl.

перловка — изначально инструмент для написания костылей на скорую руку. Practical Extraction and Report Language жеж! И не надо всуе Тьюринга поминать, sed тоже полный, одна девочка на нём даже тетрис написала(а один тролль — напейсал калькулятор, пруф в info). Его и «ЯП» назвать можно только условно.

изначально инструмент для написания костылей на скорую руку

Да, но в итоге на нём написано много серьёзных вещей, нормальных аналогов которым просто нет (например cowsay).

 __________
< hi there >
 ----------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

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

func Synchronize(src interface {
	Next() *User
}, dst interface {
	Exists(u *User) bool
	Add(u *User)
}) {
	for u := src.Next(); u != nil; u = src.Next() {
		if !dst.Exists(u) {
			dst.Add(u)
		}
	}
}

«по настоящему» классические ЯП

А что там с настоящестью лиспа?

Ну и, по традиции, всё остальное: http://play.golang.org/p/uAqQ2V63Et

Ой. Я думал там будет больше о замыканиях, а там их практически нет. Там больше ФВП. Извиняюсь.

ну кто-бы спорил? Однако — всё равно это скрипт. А я вроде уже выше писал, что в скриптах это обычная фича(функциональность).

А что там с настоящестью лиспа?

а LISP использует не классический процедурный, а более новый функциональный подход.

процедура использует глобальные переменные

Не глобальные, а из вышележащего (или вообще другого) кадра, контекста.

и если теперь смотреть на эти операции как на объекты, а на их композиции как на операции

имеется в виду последовательность операций над объектом как одна операция, являющаяся композицией? то есть, на примере списков, что-то типа: есть A<List -> List>; B<List -> List> и их композиция, C<<List -> List> -> List> , рассматривается как целая абстракция-операция. Или я что-то не вкуриваю?

LISP использует не классический процедурный, а более новый функциональный подход.

А ничего, что LISP был вторым ЯП, после Фортрана? И сразу «более новый»? При этом Фортран не то чтобы демонстрировал процедурный подход, изначально.

А ничего, что LISP был вторым ЯП, после Фортрана?

ничего страшного. Все ошибаются. Первым был очевидно машинный язык, т.е. язык кодов конкретного вычислителя. Причём первые вычислители никак не были функциональными, а совсем таки процедурными. Конечно математики уже давно додумались до того, что можно всё свести к функциям, но потребовалось несколько десятков лет, что-бы реализовать это в железе. Почти сразу выяснилось также и то, что ФП не нужно на уровне железа, просто тупо потому, что преобразование функций в функции не нужно 95% на практике (хотя 146% без зазрения совести пользовались алгоритмами, придуманными функциональщиками)

А фортран был далеко не первым ЯП. Это первый оптимизирующий компилятор, который впервые мог упрощать математические формулы в более быстрый/компактный код. Конечно без ФП это просто невозможно. Наверное это ещё и первый _реальный_ успех этого вашего ФП. Собственно LISP появился чуть позже фортрана. Но это уже совсем другая история.

Первым ЯП был Plankalkül, а не Фортран.

Шкворец набираешь, толстяк? В sicp в первой же сноске о замыканиях написано, что слово используется только в математическом контексте.

http://en.wikipedia.org/wiki/History_of_programming_languages

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

В общем, пойнт в том, что говорить «новое» по поводу ФП по отношению к ПП - это совершенно неверно исторически.

Не обратил внимания значит.

Что такое «шкворец»?

Все, что до фортрана - машиноспецифичное ковырялово

не только. Были и переносимые ЯП. Не JS конечно, но что-то было. Читай внимательнее свою ссылку.

Были и переносимые ЯП

Ок, нехай. Хотя остальные все сдохли, по факту... Это как-то отменяет мою мысль про «новизну» ФП?

Были и переносимые ЯП

Ок, нехай.

ну хоть что-то...

Хотя остальные все сдохли, по факту...

естественно. FORTRAN тоже не сильно живой.

Это как-то отменяет мою мысль про «новизну» ФП?

отменяет. Изначально был процедурный подход к программированию, и только в 40х годах математики догадались, что куча не нужных операторов типа циклов и goto не нужны, необходимо и достаточно функций. Понадобилось ещё 20 лет, что-бы сделать что-то такое, что _можно_ применять на практике (LISP), даже пытались применять, но в большинстве случаев фэйлились ещё 20 лет. В 80х годах даже пытались это всё сделать массово и в железе, но тоже fail. Да, меня тоже учили на LISP'е писать, может потому я его так и НЕНАВИЖУ. :-)

FORTRAN тоже не сильно живой.

Вполне живой. Вполне еще значится во всяких списках популярности. Входит в первые 2-3 десятка.

Изначально был процедурный подход к программированию, и только в 40х годах

???????? Какое ПРОГРАМИРОВАНИЕ до 40х???? Изначально программирование было императивным - это правда, в силу архитектуры машин (и невозможности сделать что-то уровнем выше машинного кода, такие уж были мощности). Но это совсем не то же, что процедурное программирование.
Первые попытки ФП появились примерно в то же время, что и попытки ПП - конец 50х. Очевидно, разницу в год-другой с высоты 50+ лет можно поскипать.

ну до 40х годов тоже программирование было. Мало того, в 40х и 50х как раз почти всё и придумали. А в 60х Кнут всё вместе скомпилировал. Потом уже ничего революционно нового не было, только всякие дотнеты, и прочие NIH появились.

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

А вот в начале 60х наконец-то осилили свести разрозненных попытки формализовать программирование, и назвали эту ерунду LISP. Правда с тех лет и до сего дня это всё остаётся «ненужным» матаном, который рядовому программисту знать надо лишь в образовательных целях (как таблицу умножения, которая тоже «не нужна»). На практике ФП применяется пока редко, с этим, ИМХО, сложно спорить.

ну до 40х годов тоже программирование было

И как оно выглядело? Какие языки, отличные от машинного кода, применялись в реальности?

Потом уже ничего революционно нового не было

«Раньше вода была мокрее, и сахар слаще». Боюсь предположить Ваш возраст.

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

Да не было толком процедур как таковых. Стек придумали в конце 50х, если верить гуглу. А какие могут быть процедуры без стека?

На практике ФП применяется пока редко, с этим, ИМХО, сложно спорить.

И не буду. Я спорю с тем, то ФП новее ПП. Нифига не новее. Менее распространено в явном виде - это да.

И как оно выглядело? Какие языки, отличные от машинного кода, применялись в реальности?

по твоему ассемблер уже не ЯП? А вот по моему — ЯП. Извиняй, если неправильно с терминологией договорились.

«Раньше вода была мокрее, и сахар слаще». Боюсь предположить Ваш возраст.

uptime 1`218`140`549 секунд примерно. А в профиле вроде ДР написан. Да, старость не радость...

Да не было толком процедур как таковых. Стек придумали в конце 50х, если верить гуглу. А какие могут быть процедуры без стека?

стек может быть и в 50х, меня тогда не было, не застал. Но старые люди рассказывали, что процедуры ещё во времена памяти на перфокартах были. Уж я не в курсе, как они их запускали, может отдельной стопкой, без понятия. Ну а Кнут ссылался не только на работы подпрограмм, но и на алгоритмы с сопрограммами, это по нашему «многозадачность» называется. Т.е. процедуры не только могли быть отдельными и вложенными, но и даже параллельными. К сожалению, сам Кнут сокрушался, что найти достоверные пруфы не представляется возможным, но я ему верю, что он не сам это всё придумал.

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

И не буду. Я спорю с тем, то ФП новее ПП. Нифига не новее. Менее распространено в явном виде - это да.

ну я использую определения, которые выложены здесь: http://en.wikipedia.org/wiki/Procedural_programming

Может у тебя какие-то другие определения ПП?

Да, меня тоже учили на LISP'е писать, может потому я его так и НЕНАВИЖУ. :-)

1. учить - не значит научить, равно как слышать - не значит слушать

и/или

2. не в коня корм

ИТОГО: надо быть выше собственных предрассудков :р

ты разве смайлик не разглядел? :(

ну как можно ненавидеть _инструмент_? Особенно такой годный и полезный??

Извиняй, если неправильно с терминологией договорились.

Я даже готов признать, что асмы - ЯП (ну ок, с примечаниями). Но это опять таки вторично, по отношению к сравнению возраста ПП и ФП.

процедуры ещё во времена памяти на перфокартах были

Запросто. Не вижу противоречий;)

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

И это сколько угодно. Кнут начал писать книжки в 1962. Стек уже был изобретен. Если верить Кнуту - Тюрингом, в 1947. Другие говорят про 50е. Ок, пусть 1947. Значит, говорить о ПП до этого времени не приходится - без стека нет процедур. Теперь, IPL, прародитель LISP и по сути начало ФП - это середина 1956. Т.е. «вилка» получается максимум в 9 лет. В реальности, если посмотреть на языки и архитектуры, которые смогли использовать идею Тюринга - и того меньше, они ж не сразу появились. И как можно после этого из 2013 года говорить, что ФП более новая идея, чем ПП?

Ок, пусть 1947. Значит, говорить о ПП до этого времени не приходится - без стека нет процедур.

4.2

лично я в юности напейсал тест памяти к спектруму, и никакой стек я при этом не использовал, ибо тест памяти должен работать с битой памятью, К.О. А процедуры я тоже использовал, ибо как тест памяти укажет мне битый чип памяти? Без процедур это заняло-бы десятки К, а у меня было всего 100..200 байт(или чуть больше, но точно ненамного, ибо я три дня пытался туда затолкать, учитывая то, что память юзать нельзя, а регистров там штук 10, и те в 1 байт)

Hint: Вместо стека можно использовать регистры.

Ну и вообще «процедуры» это на самом деле не какая-то особенность ПП, как не странно. Суть ПП в том, что программа разбивается на части, которые выполняются последовательно, при этом порядок выполнения процедур может меняться в зависимости от данных. Вовсе не обязательно, что-бы процедура была реализована отдельно где-то сбоку. Не важно даже то, что она годна для повторного использования. Да и если годна, она вполне может выполняться в ЦИКЛЕ, без всякого стека возвратов.

Принципиальная разница ПП и ФП это контексты, в ПП контекст считается единым, а вот в ФП контекст гвоздями приколочен к функции. В ФП даже сама _функция_ приколочена к «процедуре». Т.е. «выполнить процедуру X» в ФП означает «выполнить какие-то действия в контексте X. И данные, и сами действия, полностью определяются этим X.

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

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

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

Это же неэквивалентный код. Оригинал тут намного лучше.

И как оно выглядело? Какие языки, отличные от машинного кода, применялись в реальности?

Первые программы безо всяких проблем писались на старом добром английском.

Да не было толком процедур как таковых. Стек придумали в конце 50х, если верить гуглу. А какие могут быть процедуры без стека?

Процедуры появились за 100 (прописью - сто) лет до введения стека.

а лечебные процедуры - и того раньше

Да нет, я про те процедуры, которые подпрограммы.

ты разве смайлик не разглядел? :(

:( пора купить очки и принимать «для внимания, для памяти» :)