Is it possible to implement such an example in Java without using destructive updates? Yes. However, as @Thiton and the article itself mentioned, it will be ugly (depending on one’s taste). One way is using recursion; here’s a Haskell example that does something similar:

unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []  

Note 1) the lack of mutation, 2) the use of recursion, and 3) the lack of loops. The last point is very important — functional languages don’t need looping constructs built into the language, since recursion can be used for most (all?) cases where loops are used in Java. Here’s a well-known series of papers showing how incredibly expressive function calls can be.

I found the article unsatisfying and would like to make a couple of additional points:

That article is a very poor and confusing explanation of functional programming and its benefits. I would strongly recommend other sources for learning about functional programming.

The most confusing part about the article is that it doesn’t mention that there are two uses for assignment statements in Java (and most other mainstream languages):

1. binding a value to a name: final int MAX_SIZE = 100;

2. destructive update: int a = 3; a += 1; a++;

Functional programming eschews the second, but embraces the first (examples: let-expressions, function parameters, top-level defineitions). This is a very important point to grasp, because otherwise the article just seems silly and might leave you wondering, what are take, squares-of, and integers if not variables?

In addition, the example is meaningless. It doesn’t show the implementations of take, squares-of, or integers. For all we know, they are implemented using mutable variables. As @Martin said, you can trivially write this example in Java.

Once again, I would recommend avoiding this article and others like it if you really want to learn about functional programming. It seems to be written more with the goal of shocking and offending rather than teaching concepts and fundamentals. Instead, why not check out one of my all-time favorite papers, by John Hughes. Hughes tries to tackle some of the same issues that the article covered (although Hughes doesn’t talk about concurrency/parallelization); here’s a teaser:

This paper is an attempt to demonstrate to the larger community of
(nonfunctional) programmers the significance of functional programming,
and also to help functional programmers exploit its advantages to the
full by making it clear what those advantages are.

[…]

We shall argue in the remainder of this paper that functional
languages provide two new, very important kinds of glue. We shall give
some examples of programs that can be modularized in new ways and can
thereby be simplified. This is the key to functional programming’s
power — it allows improved modularization. It is also the goal for
which functional programmers must strive — smaller and simpler and
more general modules, glued together with the new glues we shall
describe.

You wouldn’t. Variables are at the core of imperative programming, and if you try to program imperatively without using variables, you are just causing everyone a pain in the ass.
In different programming paradigms, the styles are different, and different concepts form your basis. A variable in Java, when used well with a small scope, is no evil. Asking for a Java program without variables is like asking for a Haskell program without functions, so you don’t ask for it, and you don’t let yourself be fooled into viewing imperative programming as inferior because it uses variables.

So, the Java way would be:

for (int i = 1; i <= 25; ++i) {
    System.out.println(i*i);
}

and don’t let yourself be fooled to write it in any more complex way due to a hatred of variables.

The simplest I can do with recursion is a function with one parameter. It’s not very Java-esque, but it does work:

public class squares
{
    public static void main(String[] args)
    {
        squares(15);
    }

    private static void squares(int x)
    {
        if (x>0)
        {
            System.out.println(x*x);
            squares(x-1);
        }
    }
}

In your functional example we don’t see how the squares-of and take functions are implemented. I’m not a Java expert, but I’m pretty sure we could write those functions to enable a statement like this…

squares_of(integers).take(25);

which is not so very different.

In Java you could do this (esp. the infinite list part) with iterators. In the following code sample, the number supplied to the Take constructor can be arbitrarily high.

class Example {
    public static void main(String[] a) {
        Numbers test = new Take(25, new SquaresOf(new Integers()));
        while (test.hasNext())
            System.out.println(test.next());
    }
}

Or with chainable factory methods:

class Example {
    public static void main(String[] a) {
        Numbers test = Numbers.integers().squares().take(23);
        while (test.hasNext())
            System.out.println(test.next());
    }
}

Where SquaresOf, Take and Integers extend Numbers

abstract class Numbers implements Iterator<Integer> {
    public static Numbers integers() {
        return new Integers();
    }

    public Numbers squares() {
        return new SquaresOf(this);
    }

    public Numbers take(int c) {
        return new Take(c, this);
    }
    public void remove() {}
}

Short version:

In order to make single-assignment style work reliably in Java, you’d need (1) some kind of immutable-friendly infrastructure, and (2) compiler- or runtime-level support for tail-call elimination.

We can write much of the infrastructure, and we can arrange things to try to avoid filling the stack. But as long as each call takes a stack frame, there will be a limit on how much recursion you can do. Keep your iterables small and/or lazy, and you shouldn’t have major issues. At least most of the problems you’ll run into don’t require returning a million results at once. 🙂

Also note, since the program has to actually effect visible changes in order to be worth running, you can’t make everything immutable. You can, however, keep the vast majority of your own stuff immutable, using a tiny subset of essential mutables (streams, for example) only at certain key points where the alternatives would be too onerous.

Long version:

Simply put, A Java program can not totally avoid variables if it wants to do anything worth doing. You can contain them, and thus restrict mutability to a huge degree, but the very design of the language and API — along with the need to eventually change the underlying system — make total immutability infeasible.

Java was designed from the start as an imperative, object-oriented language.

• Imperative languages nearly always depend on mutable variables of some kind. They tend to favor iteration over recursion, for example, and nearly all iterative constructs — even while (true) and for (;;)! — are utterly dependent on a variable somewhere changing from iteration to iteration.
• Object-oriented languages pretty much envision every program as a graph of objects sending messages to each other, and in nearly all cases, responding to those messages by mutating something.

The end result of those design decisions is that without mutable variables, Java has no way to change the state of anything — even something as simple as printing “Hello world!” to the screen involves an output stream, which involves sticking bytes in a mutable buffer.

So, for all practical purposes, we’re limited to banishing the variables from our own code. OK, we can kinda do that. Almost. Basically what we’d need is to replace almost all iteration with recursion, and all mutations with recursive calls returning the changed value. like so…

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()));
}

Basically, we build a linked list, where each node is a list in itself. Each list has a “head” (the current value) and a “tail” (the remaining sublist). Most functional languages do something akin to this, because it’s very amenable to efficient immutability. A “next” operation just returns the tail, which is typically passed to the next level in a stack of recursive calls.

Now, this is an extremely oversimplified version of this stuff. But it’s good enough to demonstrate a serious problem with this approach in Java. Consider this code:

public function doStuff() {
    final Ints integers = ...somehow assemble list of 20 million ints...;
    final Ints result = take(25, squares_of(integers));
    ...
}

Although we only need 25 ints for the result, squares_of doesn’t know that. It is going to return the square of every number in integers. Recursion 20 million levels deep causes pretty big problems in Java.

See, the functional languages you’d typically do wackiness like this in, have a feature called “tail call elimination”. What that means is, when the compiler sees code’s last act being to call itself (and return the result if the function’s non-void), it uses the current call’s stack frame instead of setting up a new one and does a “jump” instead of a “call” (so the stack space used remains constant). In short, it goes about 90% of the way toward turning tail-recursion into iteration. It could deal with those billion ints without overflowing the stack. (It’d still eventually run out of memory, but assembling a list of a billion ints is going to mess you up memorywise anyway on a 32-bit system.)

Java doesn’t do that, in most cases. (It depends on the compiler and runtime, but Oracle’s implementation doesn’t do it.) Each call to a recursive function eats up a stack frame’s worth of memory. Use up too much, and you get a stack overflow. Overflowing the stack all but guarantees the death of the program. So we have to make sure not to do that.

One semi-workaround…lazy evaluation. We still have the stack limitations, but they can be tied to factors we have more control over. We don’t have to calculate a million ints just to return 25. 🙂

So let’s build us some lazy-evaluation infrastructure. (This code was tested a while back, but i’ve modified it quite a bit since then; read the idea, not the syntax errors. :))

// 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()); }
    };
}

(Keep in mind that if this were actually viable in Java, code at least somewhat like the above would already be part of the API.)

Now, with an infrastructure in place, it’s rather trivial to write code that doesn’t need mutable variables and is at least stable for smaller amounts of input.

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);
}

This mostly works, but it’s still somewhat prone to stack overflows. Try takeing 2 billion ints and doing some action on them. 😛 It will eventually throw an exception, at least until 64+ GB of RAM becomes standard. Problem is, the amount of a program’s memory that’s reserved for its stack is not that big. It’s typically between 1 and 8 MiB. (You can ask for bigger, but it doesn’t matter all that much how much you ask for — you call take(1000000000, someInfiniteSequence), you will get an exception.) Fortunately, with lazy evaluation, the weak spot is in an area we can better control. We just have to be careful about how much we take().

It’ll still have lots of problems scaling up, because our stack usage increases linearly. Each call handles one element and passes the rest off to another call. Now that i think about it, though, there is one trick we can pull which might gain us quite a bit more headroom: turn the chain of calls into a tree of calls. Consider something more like this:

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);
}

workWith basically breaks up the work into two halves, and assigns each half to another call to itself. Since each call reduces the size of the working list by half rather than by one, this should scale logarithmically rather than linearly.

Problem is, this function wants an input — and with a linked list, getting the length requires traversing the whole list. That’s easily solved, though; simply don’t care how many entries there are. 🙂 The above code would work with something like Integer.MAX_VALUE as the count, since a null stops the processing anyway. The count is mostly there so we have a solid base case. If you anticipate having more than Integer.MAX_VALUE entries in a list, then you can check workWith‘s return value — it should be null at the end. Otherwise, recurse.

Keep in mind, this touches as many elements as you tell it to. It’s not lazy; it does its thing immediately. You only want to do it for actions — that is, thingies whose sole purpose is to apply itself to every element in a list. As i’m thinking it over right now, it seems to me that sequences would be a lot less complicated if kept linear; shouldn’t be a problem, since sequences don’t call themselves anyway — they just create objects that call them again.

I’ve previously tried to create an interpreter for a lisp-like language in Java, ( a few years ago and all the code was lost as it was in CVS at sourceforge ), and the Java util iterators are a bit verbose for functional programming on lists.

Here’s something based on a sequence interface, which just has the two operations you need to get the current value and get the sequence starting at the next element. These are named head and tail after the functions in scheme.

It’s important to use something like the Seq or Iterator interfaces as it means the list is created lazily. The Iterator interface can’t be an immutable object, so is less suited to functional programming – if you can’t tell if the value you pass into a function has been changed by it, you lose one of the key advantages of functional programming.

Obviously integers should be a list of all the integers, so I started at zero and alternately returned positive and negative ones.

There’s two version of squares – one creating a custom sequence, the other using map which takes a ‘function’ – Java 7 doesn’t have lambdas so I used an interface – and applies it to each element in the sequence in turn.

The point of the square ( int x ) function is only to remove the need to call head() twice – normally I would have done this by putting the value into a final variable, but adding this function means there are no variables in the program, only function parameters.

The verbosity of Java for this sort of programming led me to write the second version of my interpreter in C99 instead.

public class Squares {
    interface Seq<T> {
        T head();
        Seq<T> tail();
    }

    public static void main (String...args) {
        print ( take (25, integers ) );
        print ( take (25, squaresOf ( integers ) ) );
        print ( take (25, squaresOfUsingMap ( integers ) ) );
    }

    static Seq<Integer> CreateIntSeq ( final int n) {
        return new Seq<Integer> () {
            public Integer head () {
                return n;
            }
            public Seq<Integer> tail () {
                return n > 0 ? CreateIntSeq ( -n ) : CreateIntSeq ( 1 - n );
            }
        };
    }

    public static final Seq<Integer> integers = CreateIntSeq(0);

    public static Seq<Integer> squaresOf ( final Seq<Integer> source ) {
        return new Seq<Integer> () {
            public Integer head () {
                return square ( source.head() );
            }
            public Seq<Integer> tail () {
                return squaresOf ( source.tail() );
            }
        };
    }

    // mapping a function over a list rather than implementing squaring of each element
    interface Fun<T> {
        T apply ( T value );
    }

    public static Seq<Integer> squaresOfUsingMap ( final Seq<Integer> source ) {
        return map ( new Fun<Integer> () {
            public Integer apply ( final Integer value ) {
                return square ( value );
            }
        }, source );
    }

    public static <T> Seq<T> map ( final Fun<T> fun, final Seq<T> source ) {
        return new Seq<T> () {
            public T head () {
                return fun.apply ( source.head() );
            }
            public Seq<T> tail () {
                return map ( fun, source.tail() );
            }
        };
    }

    public static Seq<Integer> take ( final int count,  final Seq<Integer> source ) {
        return new Seq<Integer> () {
            public Integer head () {
                return source.head();
            }
            public Seq<Integer> tail () {
                return count > 0 ? take ( count - 1, source.tail() ) : nil;
            }
        };
    }

    public static int square ( final int x ) {
        return x * x;
    }

    public static final Seq<Integer> nil = new Seq<Integer> () {
        public Integer head () {
            throw new RuntimeException();
        }
        public Seq<Integer> tail () {
            return this;
        }
    };

    public static <T> void print ( final Seq<T> seq ) {
        printPartSeq ( "[", seq.head(), seq.tail() );
    }

    private static <T> void printPartSeq ( final String prefix, final T value, final Seq<T> seq ) {
        if ( seq == nil) {
            System.out.println("]");
        } else {
            System.out.print(prefix);
            System.out.print(value);
            printPartSeq ( ",", seq.head(), seq.tail() );
        }
    }
}

How to write useful Java programs without using mutable variables.

You can in theory implement just about anything in Java using just recursion and no mutable variables.

In practice:

• The Java language is not designed for this. Many constructs are designed for mutation, and are hard to use without it. (For instance, you can’t initialize a variable length Java array without mutation.)

• Ditto for the libraries. And if you limit yourself to library classes that don’t use mutation under the cover, it is even harder. (You can’t even use String … take a look at how hashcode is implemented.)

• Mainstream Java implementations don’t support tail-call optimization. That means that recursive versions of algorithms tend to be stack space “hungry”. And since Java thread stacks don’t grow, you need to preallocate big stacks … or risk StackOverflowError.

Combine these three things, and Java is not really a viable option for writing useful (i.e. non-trivial) programs without mutable variables.

(But hey, that’s OK. There are other programming languages available for the JVM, some of which do support functional programming.)

As we’re looking for an example of the concepts, I’d say let’s set aside Java and look for a different yet familiar setting in which to find a familiar version of the concepts. UNIX pipes are rather similar to chaining lazy functions.

cat /dev/zero | tr '' 'n' | cat -n | awk '{ print $0 * $0 }' | head 25

In Linux this means, give me bytes each of which is composed of false rather than true bits, until I lose my appetite; change each of those bytes to a newline character; number each line thus created; and produce the square of that number. Furthermore I have appetite for 25 lines and no more.

I claim that a programmer wouldn’t be ill advised to write a Linux pipeline in that manner. It’s relatively normal Linux shell scripting.

I claim that a programmer would be ill advised to attempt writing the same thing similarly in Java. The reason is software maintenance as a major factor in the lifetime cost of software projects. We don’t want to befuddle the next programmer by presenting what is ostensibly a Java program but actually is written in effect in a custom one-off language by elaborately duplicating functionality that already exists in the Java platform.

On the other hand, I claim that the next programmer could be more accepting if some of our “Java” packages are actually Java Virtual Machine packages written in one of the functional or object/functional languages such as Clojure and Scala. These are designed to be coded by chaining functions together and to be called from Java in the normal manner of Java method calls.

Then again, it can still be a good idea for a Java programmer to take inspiration from functional programming, in places.

Recently my favorite technique [was] to use an immutable, uninitialized return variable and a single exit so that, as some functional language compilers do, Java checks that no matter what happens in the body of the function, I always provide one and only one return value. Example:

int f(final int n) {
    final int result; // not initialized here!
    if (n < 0) {
        result = -n;
    } else if (n < 1) {
        result = 0;
    } else {
        result = n - 1;
    }
    // If I would leave off the "else" clause,
    // Java would fail to compile complaining that
    // "result" is possibly uninitialized.
    return result;
}

The easiest way to find that out would be feed the following to the Frege compiler, and look at the generated java code:

module Main where

result = take 25 (map sqr [1..]) where sqr x = x*x