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


Автор: Ch0bits 14.5.2006, 21:44
САБЖ
Объясните пожалуйста!
 smile  

Автор: Void 14.5.2006, 22:01
В контексте языков программирования под лямбда-функцией понимают анонимную функцию. Т.е. функцию, которой не сопоставлено никакое имя, просто значение функционального типа. Например:
C# 2.0:
Код
delegate(int x) { return x + 1; }

Код
lambda x: x + 1

OCaml:
Код
fun x -> x + 1

Haskell:
Код
\x -> x + 1

Lisp:
Код
(lambda (x) (+ x 1))

Название пошло от http://ru.wikipedia.org/wiki/%D0%9B%D1%8F%D0%BC%D0%B1%D0%B4%D0%B0-%D0%B8%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5.
Лямбда-функции чаще всего используются совместно с http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D1%8B%D0%BA%D0%B0%D0%BD%D0%B8%D0%B5_%28%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29, однако это ортогональные понятия. 

Автор: Ch0bits 15.5.2006, 11:00
Ну ты полиглот smile  

Но я ничего не понял! smile 
Ни про исчисления, ни про замыкания...  smile  

Цитата(Void @  14.5.2006,  22:01 Найти цитируемый пост)
ортогональные понятия

Как это понимать? 

Автор: Void 15.5.2006, 19:06
Замыкание, это, фактически, захват контекста вызова. Т.е. в точке вызова функции доступны переменные, которые были в зоне видимости определения функции, но не видны в самой точке вызова. Например:
Код
delegate void Lambda(int x);

static void foo(Lambda f)
{
    f(3);
}

static void bar()
{
    int n = 4;
    foo(delegate(int x) { n = x; });
    Console.WriteLine(n);
}

foo через замыкание получила доступ к n в bar, хотя прямой видимости нет.
Почитай еще http://c2.com/cgi/wiki?LexicalClosure.

А про лямбда-исчисление написано в замечательной книги Харрисона и Филда «Функциональное программирование», которая есть на lib.ru.

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

Автор: Ch0bits 15.5.2006, 20:25
В чём же преимущества такого подхода? Я пока вижу одну путаницу.  smile  

Автор: Void 15.5.2006, 21:51
Преимущества появляются, когда есть адекватный синтаксис и нормальная поддержка функций высшего порядка [1] со стороны библиотеки. В C# 2.0 первое хромает, а второе находится в зачаточном состоянии.
Преимущества в том, что многие операции можно параметризовать функциями. И очень часто функции, которые надо передать, имеют небольшой размер и имеют значение только для маленького участка кода, где они применяются. Отсюда возникает необходимость в синтаксисе, позволяющем описывать такие функции прямо по месту использования, не засоряя пространство имен. Далее, логично было бы использовать в этой анонимной функции переменные, описанные в текущей функции и внешнем пространстве имен.

[1] — функцией высшего порядка называется функция, принимающая другие функции в качестве параметров и/или возвращающая функциональные значения.

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

Шаг первый: ни анонимных функций, ни замыканий. Чистый Си.
Код
typedef /* какая структра */ IntList;

int find(IntList *list, int (*predicate)(int)) { /* реализация */ }

void test()
{
    
    IntList *t; /* наш список */
    int n; /* какое-то значение */
    /* что-то мы с ними делали и возжелали найти в
       t первый элемент, больший n */
    x = find(t, /* Обломись! А что здесь писать-то? */);
    ...
}

Мы можем написать функцию greater где-то в файле, но передать значение n в нее мы можем только через глобальную переменную, а делать этого нам бы не хотелось. Выход один: добавить в find еще один параметр, который она будет передавать предикату при каждом его вызове. Поскольку предикату может понадобиться все что угодно, параметр придется делать типа void*. Прощай, типобезопасность, но мы же все-таки на Си пишем. Итак, новый вариант:
Код
int *find(IntList *list, void *param, int (*predicate)(int, *void));

int greater(int x, void *param) {
    return x >= *((int*) param);
}

...
int *x = find(t, &n, greater);

Не очень красиво, но достаточно гибко.

Шаг один с половиной. Анонимных функций нет, замыкания есть, но толку от них… Паскаль.
Код
type IntList = { какая структура };

type Predicate = function(x: Integer): Boolean;

function Find(list: IntList; f: Predicate): Integer;
begin
    { реализация }
end;

procedure Test;
    var t: IntList;
    var n: Integer;

    function GreaterN(x: Integer): Boolean;
    begin
        GreaterN := x >= n
    end;
begin
    ...
    x := Find(t, GreaterN); { Опа, что это у нас тут? }
end;

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

Шаг два. В языке вроде бы нет ни того, ни другого, но все можно сделать своими руками. C++.
Код
/* Не буду объвлять структуру List и функцию find!
   Да здравствует ООП и стандартная библиотека. */
#include <list>
#include <algorithm>

void test() {
    // здесь все знакомо:
    list<int> t;
    int n;
    // и не надоело число в списке искать?
    
    // Нам нужен предикат.
    class Greater {
    private:
        int &n; // ссылка на перменную окружения, которая нам нужна
    public:
        // кто-то добрый все-таки должен передать предикату n —
        // но всего один раз!
        Greater(int &n) : n(n) { }
        
        bool operator()(int x) const { return x > n; }
    };
    list<int>::iterator x = find_if(
        t.begin(), t.end(), // ищем от начала и до конца
        Greater(n) // вот оно, замыкание ручками
    );
}

Синтаксис не блещет, но задачу мы все-таки решили, не вылезая за пределы своей функции и не теряя типобезопасности (хвала шаблонам). А предикат в виде класса можно вообще куда-нибудь в библиотеку выделить. Что, впрочем, создатели стандартной библиотеки и сделали.
Код
// делаем то же самое средствами STL
find_if(t.begin(), t.end(), bind2nd(greater<int>(), n));

Запись стала сущестенно короче, но не слишком понятнее.
Отдельные индивидуумы пошли дальше, и задействовав головокружительную смесь шаблонов и перегрузки операторов, сумели создать библиотеку, позволяющую писать так:
Код
find_if(t.begin(), t.end(), _1 > n);

Выглядит неплохо, но до первой опечатки. Компилятор с удовольствием выльет на вас килобайты грязи из несметных полчищ шаблонов. А когда исходник с десятком таких выражений будет компилироваться с минуту, вы поймете, что в C++ хоть и можно все сделать своими руками, но получается обычно через одно место.

Шаг третий. Есть и анонимные функции и замыкания. Вот только пользоваться ими не очень удобно. C# 2.0.
Код
// стандартная библиотека по-прежнему рулит
List<int> t = new List<int>();
int n;
...
int x = t.Find(delegate(int x) { return x > n; });

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

Шаг три с половиной. Синтаксис рулит, библиотеку писали с учетом всех возможностей языка. OCaml.
Код
let t = [1; 2; 3; 4]
and n = 3 in
let x = List.find (fun x -> x > n) t

Или даже так:
Код
List.find ((<=) n) t

Почему всего полшага? Если бы не один просчет создателей .NET Framework, я бы поставил OCaml на одну полку с C#. Дело в том, что функции высшего порядка в стандартной библиотеке что там, что там неполиморфны. В .NET нет функций, работающих с IList или IEnumerable. Только методы List, Array и т.д., хотя сам язык позволяет их написать. OCaml увы, этого рода полиморфизма лишен из-за свойств самого языка.

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

Disclaimer: я упомянул далеко не все языки, поддерживающие замыкания и анонимные функции. Например, Python и Ruby (особенно Ruby) замечательно поддерживают и то и другое. И даже полиморфизм работает, правда, за счет duck typing'а со всеми вытекающими.

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

Автор: batigoal 16.5.2006, 08:42
Void, я потрясён. 

Автор: Void 16.5.2006, 16:51
Lamer George, спасибо smile

to all: Буду очень благодарен за любые дельные замечания к посту. Думаю, после некоторой обработки это можно разместить в Вики. 

Автор: ALKS 16.5.2006, 17:04
Хм.... а пример того же на Java?  smile 

Автор: Void 16.5.2006, 17:20
ALKS, увы, Java я в лучшем случае могу читать. AFAIK, замыкания в Java можно изобразить на анонимных классах.

Добавлено @ 17:23 
Уточнил в Гугле. Inner classes в Java копируют контекст вызова, а не захватывают его. Т.е. мы можем использовать внешние переменные, но не модифицировать их. 

Автор: maxim1000 16.5.2006, 18:04
Цитата(Void @  15.5.2006,  20:51 Найти цитируемый пост)
Шаг два. В языке вроде бы нет ни того, ни другого, но все можно сделать своими руками. C++.

как-то пробовал так делать... ругается smile
не хочет использовать локальный тип при специализации шаблона
компилятор из VC++ 2003 Toolkit
вопрос: это самодеятельность Microsoft или так должно быть по стандарту? 

Автор: maxim1000 16.5.2006, 18:30
зато можно так (только в том случае если тот не работает):
Код

class CFunc
{
  public:
    virtual void function()=0;
};
void MakeSomething(CFunc &f)
{
  f.function();
}

void f()
{
  class myfunc:public CFunc
  {
    public:
      virtual void function()
      {
        cout<<"qqq";
      }
  };
  MakeSomething(myfunc());
}

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

Автор: svg 16.5.2006, 20:04
Цитата(Void @  16.5.2006,  16:51 Найти цитируемый пост)
to all: Буду очень благодарен за любые дельные замечания к посту. Думаю, после некоторой обработки это можно разместить в Вики.  


Полиморфная find (erlang)
Код

find([], _) ->
  nil;
find([X|Rest], Test) ->
  case Test(X) of
    true ->
      X;
    false ->
      find(Rest, Test)
  end;
find(T, Test) when is_tuple(T) ->
  find(tuple_to_list(T), Test).

Example:

find([1, 2, 3], fun (X=3) -> true; (_) -> false end).
   

Автор: Ch0bits 16.5.2006, 21:49
svg
Это что у тебя за язык?

Void
Читал 5 раз, в разное время суток. Вроде что-то понял, но мне до этого расти да расти.   smile 
Лови плюс. smile  

Автор: Void 16.5.2006, 22:08
Ch0bits, это главное — понимать, что есть куда расти, и стремиться к этому smile

Цитата(Ch0bits @  16.5.2006,  23:49 Найти цитируемый пост)
Это что у тебя за язык?

http://www.erlang.org/ 

Автор: maxim1000 5.6.2006, 13:31
пришла в голову мысль: анонимные функции в C++ вполне можно организовать через for
примеры мы пишем постоянно: когда перебираем элементы контейнера с помощью итератора и т.д.
но можно пойти и дальше:
делаем объект алгоритм, который соответствует последовательности действий, в которой нужно вызывать пользовательскую функцию
у него должно быть три части:
1. инициализация
2. критерий окончания
3. шаг до следующего вычисления внешней функции
в качестве параметров и возвращаемых значений можно использовать поля/методы этого объекта
например, попробуем сделать сортировку (по-моему, называется сортировка выбором):
Код

class CSorter
{
public:
  CSorter(std::vector<int> &array):array_(array),sortedpart_(0),current_(1),argmin_(0) {}
  bool completed() const {return sortedpart_==array_.size()-1;}
  void step()
  {
    std::cout<<"sordetpart:"<<sortedpart_<<",current:"<<current_<<"\n";
    if(FirstIsBigger)
      argmin_=current_;
    ++current_;
    if(current_==array_.size())
    {
      int temp=array_[sortedpart_];
      array_[sortedpart_]=array_[argmin_];
      array_[argmin_]=temp;
      ++sortedpart_;
      argmin_=sortedpart_;
      current_=sortedpart_+1;
    }
    if(!completed())
    {
      ToCompare1=array_[argmin_];
      ToCompare2=array_[current_];
    }
  }
  int ToCompare1;
  int ToCompare2;
  bool FirstIsBigger;
protected:
  std::vector<int> &array_;
  unsigned int sortedpart_;
  unsigned int current_;
  unsigned int argmin_;
};

тогда сортировка по возрастанию младшей цифры будет выглядеть так:
Код

  for(CSorter s(v);!s.completed();s.step())
    s.FirstIsBigger=(s.ToCompare1%10)>(s.ToCompare2%10);

преимущества - "полное погружение" в текущий контекст - можно использовать всё, что сейчас доступно, и не надо передавать это в качестве параметров в класс (например, основание системы счисления могло бы задаваться параметром функции, в которой происходит сортировка)
недостатки - нужно представлять алгоритм в автоматном виде, что не всегда удобно
Цитата(maxim1000 @  16.5.2006,  17:04 Найти цитируемый пост)
не хочет использовать локальный тип при специализации шаблона
компилятор из VC++ 2003 Toolkit

выбросил его, поставил 2005 smile 

Автор: Любитель 23.12.2006, 17:22
А почему бы (для плюсов) просто не посмотреть в сторону boost::bind и boost::lambda? Вещи очень развитые. C++ никогда не будет функциональным языком как таковым, но ФП с помощью библиотек давно реализовано.

Автор: Delphist 4.9.2008, 09:29
Цитата(Void @  15.5.2006,  22:51 Найти цитируемый пост)
Шаг один с половиной. Анонимных функций нет, замыкания есть, но толку от них… Паскаль.

Код

type IntList = { какая структура };

type Predicate = function(x: Integer): Boolean;

function Find(list: IntList; f: Predicate): Integer;
begin
    { реализация }
end;

procedure Test;
    var t: IntList;
    var n: Integer;

    function GreaterN(x: Integer): Boolean;
    begin
        GreaterN := x >= n
    end;
begin
    ...
    x := Find(t, GreaterN); { Опа, что это у нас тут? }
end;



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


Void, посмотри пожалуйста вот это новшество http://8vmr.livejournal.com/6114.html в Delphi2009 появилась такая возможность, как лямбда-функции, в связи с чем хотелось поинтересоваться возможно ли теперь решить постовленную задачу:
Цитата(Void @  15.5.2006,  22:51 Найти цитируемый пост)
Допустим, у нас есть задача: найти в списке элемент, удовлетворяющий заданному условию (предикату). Представим себе, что у нас уже есть структура данных «список» и функция поиска, принимающая предикат, который также является функцией, возвращающей значений булевского типа.

возможно ли теперь упростить работу

Автор: Void 4.9.2008, 13:55
Delphist, да, похоже в этом вопросе Delphi теперь практически повторяет C# 2.0.

Обалдеть, люди ссылаются на мой пост двухлетней давности.

Автор: Delphist 5.9.2008, 15:24
Цитата(Void @  4.9.2008,  14:55 Найти цитируемый пост)
Delphist, да, похоже в этом вопросе Delphi теперь практически повторяет C# 2.0.

Это не важно. Кодом не мог бы показать решение задачи

Автор: minyor 22.10.2009, 11:17
Я тут про С++ нашел тему:
http://blogs.msdn.com/vorobiev/archive/2009/07/30/9853791.aspx
Сам правда еще попробовать не успел, но выглядит вроде прикольно   smile 

Автор: k0rvin 12.3.2010, 23:23
Цитата(Void @ 16.5.2006,  16:51)
Lamer George, спасибо smile

to all: Буду очень благодарен за любые дельные замечания к посту. Думаю, после некоторой обработки это можно разместить в Вики.

более интересным применением функций как объектов первого класса является создание таблиц функций, объединённых по какому-либо качеству (или нескольким качествам) и построение собственной системы диспетчеризации по этим качествам, что весьма полезно при реализации DSL/eDSL.

например обобщенные методы можно реализовать таким образом:
функция-метод обращается к хеш-таблице генериков для взятия своего генерика, из которого затем берётся функция-специализация, типа того:

Код

(defparameter *generics* (make-hash-table))

(defclass generic ()
  ((name :accessor generic-name :initarg :name)
   (spec :accessor generic-spec :initform (make-hash-table :test #'equal))))

(defmacro define-generic (name lambda-list &body body)
  `(progn
     (setf (gethash ',name *generics*)
           (make-instance 'generic
                          :name        ',name
                          :lambda-list ',lambda-list))
     (defun ,name ,lambda-list
       (call-generic-method ',name ,(clean-ll lambda-list)))))

(defun call-generic-method (name lambda-list)
  (let* ((generic (gethash name *generics*))
         (method  (gethash (types lambda-list) (spec generic))))
    (if method
        (apply method (arguments lambda-list))
        (error "No applicable method ~a for arguments ~a." name (types lambda-list)))))

...


или пример компилирования бинарных деревьев в "On Lisp", но для этого нужны еще и замыкания =)

Автор: k0rvin 13.3.2010, 00:08
Цитата(Void @ 4.9.2008,  13:55)
Delphist, да, похоже в этом вопросе Delphi теперь практически повторяет C# 2.0.

Обалдеть, люди ссылаются на мой пост двухлетней давности.

не знаком с С#, поэтому мне больше напомнило С++, хотя лямбды и замыкания выглядят не так костыльно как в плюсах, но думается мне, что внутри это всё реализовано не очень-то красиво и паскаль/делфи рискует разделить судьбу С++ -- превратиться в монстра.

думаю следующим шагом в развити паскаля/делфи должна быть замена системы типов, ибо существующая ну уж очень устарела

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)