Krótka wersja:
Aby styl pojedynczego przydziału działał niezawodnie w Javie, potrzebujesz (1) pewnego rodzaju niezmiennej infrastruktury i (2) wsparcia na poziomie kompilatora lub środowiska wykonawczego w celu eliminacji wywołania ogonowego.
Możemy napisać dużą część infrastruktury i możemy zorganizować rzeczy, aby uniknąć zapełniania stosu. Ale tak długo, jak każde wywołanie zajmuje ramkę stosu, będzie istniało ograniczenie liczby możliwych rekurencji. Staraj się, aby iterery były małe i / lub leniwe, i nie powinieneś mieć większych problemów. Przynajmniej większość problemów, na które napotkasz, nie wymaga natychmiastowego powrotu miliona wyników. :)
Pamiętaj również, że ponieważ program musi faktycznie wprowadzać widoczne zmiany, aby być wartym uruchomienia, nie można sprawić, by wszystko było niezmienne. Możesz jednak zachować ogromną większość własnych rzeczy na niezmiennym poziomie, używając niewielkiego podzbioru niezbędnych zmiennych (na przykład strumieni) tylko w niektórych kluczowych punktach, w których alternatywy byłyby zbyt uciążliwe.
Długa wersja:
Mówiąc najprościej, program Java nie może całkowicie ominąć zmiennych, jeśli chce zrobić coś, co warto zrobić. Można zawierać je, a tym samym ograniczyć zmienność na ogromnym stopniu, ale bardzo zaprojektować języka i API - wraz z potrzebą, aby w końcu zmienić system podstawowy - dokonać całkowitej niezmienności niewykonalne.
Java została zaprojektowana od początku jako imperatywny , zorientowany obiektowo język.
- Języki imperatywne prawie zawsze zależą od zmiennych zmiennych. Na przykład preferują iterację nad rekurencją i prawie wszystkie konstrukty iteracyjne - nawet
while (true)i for (;;)! - są całkowicie zależne od zmiennej, która zmienia się gdzieś z iteracji na iterację.
- Języki zorientowane obiektowo właściwie wyobrażają sobie każdy program jako wykres obiektów wysyłających do siebie wiadomości, a prawie we wszystkich przypadkach, odpowiadających na te wiadomości poprzez mutowanie czegoś.
Efektem końcowym tych decyzji projektowych jest to, że bez zmiennych zmiennych Java nie ma możliwości zmiany stanu czegokolwiek - nawet czegoś tak prostego jak wydruk „Witaj świecie!” do ekranu wiąże się strumień wyjściowy, który polega na umieszczaniu bajtów w buforze , który można modyfikować .
Tak więc dla wszystkich praktycznych celów ograniczamy się do usuwania zmiennych z własnego kodu. OK, możemy to zrobić. Prawie. Zasadniczo potrzebowalibyśmy zastąpić prawie całą iterację rekurencją, a wszystkie mutacje rekurencyjnymi wywołaniami zwracającymi zmienioną wartość. tak jak ...
class Ints {
final int value;
final Ints tail;
public Ints(int value, Ints rest) {
this.value = value;
this.tail = rest;
}
public Ints next() { return this.tail; }
public int value() { return this.value; }
}
public Ints take(int count, Ints input) {
if (count == 0 || input == null) return null;
return new Ints(input.value(), take(count - 1, input.next()));
}
public Ints squares_of(Ints input) {
if (input == null) return null;
int i = input.value();
return new Ints(i * i, squares_of(input.next()));
}
Zasadniczo budujemy listę połączoną, w której każdy węzeł jest listą samą w sobie. Każda lista ma „nagłówek” (bieżąca wartość) i „ogon” (pozostała lista podrzędna). Większość języków funkcjonalnych robi coś podobnego, ponieważ jest bardzo podatna na niezmienność. „Następna” operacja po prostu zwraca ogon, który zwykle jest przekazywany do następnego poziomu w stosie wywołań rekurencyjnych.
To jest bardzo uproszczona wersja tych rzeczy. Ale to wystarczy, aby zademonstrować poważny problem z tym podejściem w Javie. Rozważ ten kod:
public function doStuff() {
final Ints integers = ...somehow assemble list of 20 million ints...;
final Ints result = take(25, squares_of(integers));
...
}
Chociaż do wyniku potrzebujemy tylko 25 liczb wewnętrznych, squares_ofnie wie o tym. Zwróci kwadrat każdej liczby w integers. Rekurencja na głębokości 20 milionów poziomów powoduje całkiem duże problemy w Javie.
Widzisz, funkcjonalne języki, w których zwykle robisz takie dziwactwa, mają funkcję zwaną „eliminacją ogona”. Oznacza to, że gdy kompilator widzi, że ostatnim działaniem kodu jest wywołanie samego siebie (i zwrócenie wyniku, jeśli funkcja nie jest nieważna), używa ramki stosu bieżącego wywołania zamiast konfigurowania nowego i wykonuje zamiast tego „skok” „wywołania” (więc używane miejsce na stosie pozostaje stałe). Krótko mówiąc, idzie to w około 90% w kierunku przekształcenia rekurencji ogona w iterację. Może poradzić sobie z tymi miliardami ints bez przepełnienia stosu. (W końcu wciąż zabraknie pamięci, ale zestawienie miliarda ints i tak zepsuje pamięć w systemie 32-bitowym).
W większości przypadków Java tego nie robi. (Zależy to od kompilatora i środowiska wykonawczego, ale implementacja Oracle tego nie robi.) Każde wywołanie funkcji rekurencyjnej zużywa pamięć ramki stosu. Zużyj za dużo, a otrzymasz przepełnienie stosu. Przepełnienie stosu prawie gwarantuje śmierć programu. Musimy więc upewnić się, że tego nie zrobimy.
Jedno pół obejście ... leniwa ocena. Nadal mamy ograniczenia dotyczące stosów, ale można je powiązać z czynnikami, nad którymi mamy większą kontrolę. Nie musimy obliczać miliona ints tylko po to, aby zwrócić 25. :)
Zbudujmy więc trochę leniwej infrastruktury do oceny. (Ten kod został przetestowany jakiś czas temu, ale od tego czasu go trochę zmodyfikowałem; przeczytaj pomysł, a nie błędy składniowe. :))
// Represents something that can give us instances of OutType.
// We can basically treat this class like a list.
interface Source<OutType> {
public Source<OutType> next();
public OutType value();
}
// Represents an operation that turns an InType into an OutType.
// Note, these can be the same type. We're just flexible like that.
interface Transform<InType, OutType> {
public OutType appliedTo(InType input);
}
// Represents an action (as opposed to a function) that can run on
// every element of a sequence.
abstract class Action<InType> {
abstract void doWith(final InType input);
public void doWithEach(final Source<InType> input) {
if (input == null) return;
doWith(input.value());
doWithEach(input.next());
}
}
// A list of Integers.
class Ints implements Source<Integer> {
final Integer value;
final Ints tail;
public Ints(Integer value, Ints rest) {
this.value = value;
this.tail = rest;
}
public Ints(Source<Integer> input) {
this.value = input.value();
this.tail = new Ints(input.next());
}
public Source<Integer> next() { return this.tail; }
public Integer value() { return this.value; }
public static Ints fromArray(Integer[] input) {
return fromArray(input, 0, input.length);
}
public static Ints fromArray(Integer[] input, int start, int end) {
if (end == start || input == null) return null;
return new Ints(input[start], fromArray(input, start + 1, end));
}
}
// An example of the spiff we get by splitting the "iterator" interface
// off. These ints are effectively generated on the fly, as opposed to
// us having to build a huge list. This saves huge amounts of memory
// and CPU time, for the rather common case where the whole sequence
// isn't needed.
class Range implements Source<Integer> {
final int start, end;
public Range(int start, int end) {
this.start = start;
this.end = end;
}
public Integer value() { return start; }
public Source<Integer> next() {
if (start >= end) return null;
return new Range(start + 1, end);
}
}
// This takes each InType of a sequence and turns it into an OutType.
// This *takes* a Transform, rather than just *implementing* Transform,
// because the transforms applied are likely to be specified inline.
// If we just let people override `value()`, we wouldn't easily know what type
// to return, and returning our own type would lose the transform method.
static class Mapper<InType, OutType> implements Source<OutType> {
private final Source<InType> input;
private final Transform<InType, OutType> transform;
public Mapper(Transform<InType, OutType> transform, Source<InType> input) {
this.transform = transform;
this.input = input;
}
public Source<OutType> next() {
return new Mapper<InType, OutType>(transform, input.next());
}
public OutType value() {
return transform.appliedTo(input.value());
}
}
// ...
public <T> Source<T> take(int count, Source<T> input) {
if (count <= 0 || input == null) return null;
return new Source<T>() {
public T value() { return input.value(); }
public Source<T> next() { return take(count - 1, input.next()); }
};
}
(Należy pamiętać, że jeśli byłoby to faktycznie wykonalne w Javie, kod przynajmniej nieco podobny do powyższego byłby już częścią API).
Teraz, gdy istnieje infrastruktura, pisanie kodu, który nie wymaga zmiennych i jest co najmniej stabilny przy mniejszych ilościach danych, jest dość trywialny.
public Source<Integer> squares_of(Source<Integer> input) {
final Transform<Integer, Integer> square = new Transform<Integer, Integer>() {
public Integer appliedTo(final Integer i) { return i * i; }
};
return new Mapper<>(square, input);
}
public void example() {
final Source<Integer> integers = new Range(0, 1000000000);
// and, as for the author's "bet you can't do this"...
final Source<Integer> squares = take(25, squares_of(integers));
// Just to make sure we got it right :P
final Action<Integer> printAction = new Action<Integer>() {
public void doWith(Integer input) { System.out.println(input); }
};
printAction.doWithEach(squares);
}
To głównie działa, ale wciąż jest podatne na przepełnienia stosu. Wypróbuj take2 miliardy intów i wykonaj na nich jakąś akcję. : P W końcu wyrzuci wyjątek, przynajmniej dopóki 64+ GB pamięci RAM nie stanie się standardem. Problem polega na tym, że ilość pamięci programu zarezerwowana dla stosu nie jest tak duża. Zazwyczaj wynosi od 1 do 8 MiB. (Można poprosić o większe, ale to nie ma znaczenia aż tak dużo, ile prosisz - dzwonisz take(1000000000, someInfiniteSequence), to będzie uzyskać wyjątek.) Kontrolę szczęście z oceny leniwy, słabym punktem jest w obszarze możemy lepiej . Musimy tylko uważać, ile my take().
Nadal będzie miał wiele problemów ze skalowaniem, ponieważ nasze zużycie stosu rośnie liniowo. Każde połączenie obsługuje jeden element, a resztę przekazuje do innego połączenia. Teraz, gdy o tym myślę, jest jedna sztuczka, którą możemy wyciągnąć, która może dać nam nieco więcej rezerwy: zmienić łańcuch połączeń w drzewo połączeń. Zastanów się nad czymś takim:
public <T> void doSomethingWith(T input) { /* magic happens here */ }
public <T> Source<T> workWith(Source<T> input, int count) {
if (count < 0 || input == null) return null;
if (count == 0) return input;
if (count == 1) {
doSomethingWith(input.value());
return input.next();
}
return (workWith(workWith(input, count/2), count - count/2);
}
workWithw zasadzie dzieli pracę na dwie połowy i przypisuje sobie każdą połowę do innego wezwania. Ponieważ każde wywołanie zmniejsza rozmiar listy roboczej o połowę, a nie o jedną, powinno to być skalowane logarytmicznie, a nie liniowo.
Problem polega na tym, że ta funkcja potrzebuje danych wejściowych - a przy połączonej liście uzyskanie długości wymaga przejścia całej listy. Łatwo to jednak rozwiązać; po prostu nie obchodzi mnie, ile jest wpisów. :) Powyższy kod działałby z czymś takim Integer.MAX_VALUEjak liczenie, ponieważ null i tak zatrzymuje przetwarzanie. Liczba jest głównie tam, więc mamy solidną podstawę. Jeśli spodziewasz się, że Integer.MAX_VALUEna liście będzie więcej niż kilka pozycji, możesz sprawdzić workWithwartość zwracaną - na końcu powinna ona być pusta. W przeciwnym razie powtórz.
Pamiętaj, że dotyka to tyle elementów, ile chcesz. To nie jest leniwe; robi to natychmiast. Chcesz to zrobić tylko dla akcji - to znaczy dla rzeczy , których jedynym celem jest zastosowanie się do każdego elementu na liście. W tej chwili myślę, że sekwencje byłyby o wiele mniej skomplikowane, gdyby były liniowe; nie powinno stanowić problemu, ponieważ sekwencje i tak nie nazywają się same - po prostu tworzą obiekty, które wywołują je ponownie.