Хорошее объяснение “Combinators” (Для не математики)
В Java все переменные, которые вы объявляете, на самом деле являются «ссылками» на объекты (или примитивы), а не самими объектами.
При попытке выполнить один метод объекта , ссылка просит живой объект выполнить этот метод. Но если ссылка ссылается на NULL (ничего, нуль, void, nada), то нет способа, которым метод будет выполнен. Тогда runtime сообщит вам об этом, выбросив исключение NullPointerException.
Ваша ссылка «указывает» на нуль, таким образом, «Null -> Pointer».
Объект живет в памяти виртуальной машины пространство и единственный способ доступа к нему - использовать ссылки this. Возьмем этот пример:
public class Some {
private int id;
public int getId(){
return this.id;
}
public setId( int newId ) {
this.id = newId;
}
}
И в другом месте вашего кода:
Some reference = new Some(); // Point to a new object of type Some()
Some otherReference = null; // Initiallly this points to NULL
reference.setId( 1 ); // Execute setId method, now private var id is 1
System.out.println( reference.getId() ); // Prints 1 to the console
otherReference = reference // Now they both point to the only object.
reference = null; // "reference" now point to null.
// But "otherReference" still point to the "real" object so this print 1 too...
System.out.println( otherReference.getId() );
// Guess what will happen
System.out.println( reference.getId() ); // :S Throws NullPointerException because "reference" is pointing to NULL remember...
Это важно знать - когда больше нет ссылок на объект (в пример выше, когда reference и otherReference оба указывают на null), тогда объект «недоступен». Мы не можем работать с ним, поэтому этот объект готов к сбору мусора, и в какой-то момент VM освободит память, используемую этим объектом, и выделит другую.
8 ответов
Если Вы не глубоко в теорию, можно рассматривать Y combinator как аккуратный прием с функциями, как монады.
Монады позволяют Вам цепочечным действиям, Y combinator позволяет Вам определять саморекурсивные функции.
Python имеет встроенную поддержку саморекурсивных функций, таким образом, можно определить их без Y:
> def fun():
> print "bla"
> fun()
> fun()
bla
bla
bla
...
fun доступен внутренний fun самостоятельно, таким образом, мы можем легко назвать его.
, Но что, если Python отличался, и fun, не были доступен внутренний fun?
> def fun():
> print "bla"
> # what to do here? (cannot call fun!)
решение состоит в том, чтобы передать fun само как аргумент fun:
> def fun(arg): # fun receives itself as argument
> print "bla"
> arg(arg) # to recur, fun calls itself, and passes itself along
И Y делает это возможным:
> def Y(f):
> f(f)
> Y(fun)
bla
bla
bla
...
Все это делает это вызывает функцию с собой как аргумент.
(я не знаю, на ли это определение Y 100% корректно, но я думаю, что это - общее представление.)
Reginald Braithwaite (иначе Раганвальд) писал большой ряд на combinators в Ruby в его новом блоге, гомографический .
, В то время как он не делает (к моему знанию) смотрят на сам Y-combinator, он действительно смотрит на другой combinators, например:
- пустельга
- Дрозд
- Кардинал
- Закоснелая пустельга
- другие Изворотливые Птицы
и несколько сообщений о том, как Вы можете использование их.
Я довольно короток на теории, но я могу дать Вам пример, который устанавливает мое трепещущее воображение, который может быть полезен Вам. Самый простой интересный combinator является, вероятно, "тестом".
Hope Вы знаете Использование Python
tru = lambda x,y: x
fls = lambda x,y: y
test = lambda l,m,n: l(m,n)
:
>>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break'
тест оценивает к второму аргументу, если первый аргумент является верным, иначе третьим.
>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'
Все системы могут быть созданы от нескольких основных combinators.
(Этот пример более или менее копируется из Типов и Языков программирования Benjamin C. Pierce)
Это - польза статья . Примеры кода находятся в схеме, но за ними не должно быть трудно следовать.
Вкратце, комбинатор Y - это функция более высокого порядка, которая используется для реализации рекурсии на лямбда-выражениях (анонимные функции). Посмотрите статью Майка Ваньера How to Succeed at Recursion without Really Recursing - это одно из лучших практических объяснений этого вопроса, которые я видел.
Также просканируйте SO архивы:
Комбинатор - это функция без свободных переменных . Это означает, среди прочего, что комбинатор не имеет зависимостей от вещей вне функции, только от параметров функции.
Используя F #, я так понимаю комбинаторы:
let sum a b = a + b;; //sum function (lambda)
В приведенном выше случае сумма является комбинатором, потому что и a , и b привязаны к параметрам функции.
let sum3 a b c = sum((sum a b) c);;
Вышеупомянутая функция не является комбинатором, поскольку в ней используется сумма , которая не является связанной переменной (т.е. не зависит от параметров).
Мы можем сделать sum3 комбинатором, просто передав функцию суммы в качестве одного из параметров:
let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);;
Таким образом, sumFunc является ограниченным и, следовательно, вся функция является комбинатором.
Итак, это мое понимание комбинаторов. С другой стороны, их значение до сих пор ускользает от меня. Как указывали другие, комбинаторы с фиксированной точкой позволяют выразить рекурсивную функцию без явной рекурсии. Т.е. вместо того, чтобы вызывать себя, рекурсивная функция вызывает лямбда-выражение, которое передается как один из аргументов.
Вот одно из наиболее понятных производных комбинаторов, которые я нашел:
Цитата из Википедии:
Комбинатор - это функция высшего порядка, которая использует только приложение функции и ранее определенные комбинаторы для определения результата из своих аргументов.
Что это значит? Это означает, что комбинатор - это функция (выход определяется исключительно ее входом), вход которой включает функцию в качестве аргумента.
Как выглядят такие функции и для чего они используются? Вот несколько примеров:
(fog) (x) = f (g (x))
Здесь o - комбинатор, который принимает 2 функции, f и g , и в качестве результата возвращает функцию, композицию f с g , а именно туман .
Комбинаторы могут использоваться, чтобы скрыть логику. Допустим, у нас есть тип данных NumberUndefined , где NumberUndefined может принимать числовое значение Num x или значение Undefined , где ] x a - это число . Теперь мы хотим построить сложение, вычитание, умножение и деление для этого нового числового типа.Семантика такая же, как для Число , за исключением того, что Undefined является входом, выход также должен быть Undefined и при делении на число 0 вывод также Undefined .
Можно написать утомительный код, как показано ниже:
Undefined +' num = Undefined
num +' Undefined = Undefined
(Num x) +' (Num y) = Num (x + y)
Undefined -' num = Undefined
num -' Undefined = Undefined
(Num x) -' (Num y) = Num (x - y)
Undefined *' num = Undefined
num *' Undefined = Undefined
(Num x) *' (Num y) = Num (x * y)
Undefined /' num = Undefined
num /' Undefined = Undefined
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x / y)
Обратите внимание, что все имеют одинаковую логику в отношении Неопределенных входных значений. Только разделение делает немного больше. Решение состоит в том, чтобы извлечь логику, превратив ее в комбинатор.
comb (~) Undefined num = Undefined
comb (~) num Undefined = Undefined
comb (~) (Num x) (Num y) = Num (x ~ y)
x +' y = comb (+) x y
x -' y = comb (-) x y
x *' y = comb (*) x y
x /' y = if y == Num 0 then Undefined else comb (/) x y
Это можно обобщить в так называемую монаду Maybe , которую программисты используют в функциональных языках, таких как Haskell, но я не буду вдаваться в подробности.
Выглядит неплохо: http://www.catonmat.net/blog/derivation-of-ycombinator/