Tag Archives: generator

Finite Sequence Generators in Java 8 – Part 2

In the last couple of articles we looked at generators. First we looked at ways of generating an infinite sequence. In the second we saw a way of generating a finite sequence. Let’s look at a few more aspects before we move on.

In the finite sequence article, we saw that unless we wanted to limit ourselves to a certain number of values we couldn’t use generate and iterate in a simple manner. This was because there was no way of indicating a stop condition. Limit is fine if we know how many values we need, but not if we don’t. If we use limit we’d have to create a new stream to get further values. There are a couple of other methods we could use for generating finite sequences without having to resort to using Iterable.

Let’s go back to our die throwing SixGame example from the last article. Instead of using an Iterator/Iterable, we’ll use an IntSupplier coupled with IntStream’s generate method. If any of that is new to you, then first review the article on generators with infinite sequences. We’re going to attempt (and I’m not saying this is good practice) to stop generating when we get a Six by throwing an exception:

public class SixGame
{
	public static class DieThrowSupplier implements IntSupplier
	{
		private Random rand = new Random(System.nanoTime());
		private boolean done = false;

		@Override
		public int getAsInt()
		{
			if (!done)
			{
				int dieThrow = Math.abs(rand.nextInt()) % 6 + 1;

				if (dieThrow == 6)
				{
					done = true;
				}

				return dieThrow;
			}
			else
			{
				throw new NoSuchElementException();
			}
		}
	}

	public static void main(String args[])
	{
		DieThrowSupplier dieThrows = new DieThrowSupplier();

		IntStream myStream = IntStream.generate(dieThrows);
		
		try
		{
			myStream.mapToObj(i -> "You threw a " + i).forEach(
					System.out::println);
		}
		catch (NoSuchElementException e)
		{
			// Escaped
		}
	}
}

Something here that’s new is the mapToObj call. We’re starting out with an IntStream, but we want to create a message which is a String. Thus we need to change the ‘shape’ of the stream from Integer to Object (there is no special String stream) and we can do that with mapToObj. It works like map, but instead of expecting an Integer being returned from the function, it expects an Object.

We have to catch the exception, but luckily (or perhaps sloppily given this is a demonstration) we are using a side-effect to do something with the string we generate: printing in forEach. Once we go parallel though we need to remove side effects. Although we’ve not covered it yet, what we need to do is collect the results from the stream, perhaps in a list, and then perform the printing outside of the stream chain. Although this seems a lot for our simple game, getting streams to work properly in parallel is one of the more difficult tasks that we’re going to have to master eventually.

Our problem in the parallel world is going to be that we’re collecting, but we need to assign that collection to something when the stream is done. Try changing the try/catch code to the broken:

            List<String> l = null;

            try
            {
                    l = myStream.parallel().mapToObj(i -> "You threw a " + i)
                                           .collect(Collectors.toList());
            }
            catch (NoSuchElementException e)
            {
                    // Escaped
            }

            l.stream().forEach(System.out::println);

Nothing gets printed this time, and we crash with a NullPointerException. Given we throw an exception during the stream which we catch after the assignment and not as part of the stream, the assignment never happens. Thus the list, l, stays null. We went through all the motions and got nothing for our troubles. Perhaps we could try making special collectors to handle exceptions, but given an exception is almost certainly a side-effect we should avoid these when going parallel. I can also imagine that catching exception outside of a stream and hoping we still get all the results might be quite flaky as we’re relying on the implementation to make it work. Implementations change, and other implementations come along. My verdict is – unless Oracle say otherwise, is avoid.

We also discussed that we wanted to avoid implementing a whole spliterator if there was another way available. To recap, a spliterator is an iterator that can be split into batches of work and is what drives streams. Getting that right isn’t trivial. We saw that we couldn’t get access to override InfiniteSupplyingSpliterator in order to make a version we could terminate. However, there exists a spliterator that is just missing tryAdvance which we use to inject the next value into the stream and indicate when we’re done. This is AbstractSpliterator, in particular AbstractIntSpliterator, which we can extend. Let’s have a look at our game using one of those:

public class SixGame
{
	public static class DieThrowSpliterator extends
			Spliterators.AbstractIntSpliterator
	{
		private Random rand = new Random(System.nanoTime());
		private boolean done = false;

		protected DieThrowSpliterator()
		{
			super(Long.MAX_VALUE, 0);
		}

		private int rollDie()
		{
			int dieThrow = Math.abs(rand.nextInt()) % 6 + 1;

			if (dieThrow == 6)
			{
				done = true;
			}

			return dieThrow;
		}

		@Override
		public boolean tryAdvance(IntConsumer action)
		{
			if (action == null)
			{
				throw new NullPointerException();
			}
			
			if (done)
			{
				return false;
			}

			action.accept(rollDie());

			return true;
		}

		@Override
		public boolean tryAdvance(Consumer<? super Integer> action)
		{
			if (action == null)
 			{
				throw new NullPointerException();
  			}

  			if (done)
  			{
				return false;
  			}

  			action.accept(rollDie());

  			return true;
		}
	}

	public static void main(String args[])
	{
		Stream<Integer> stream = StreamSupport.stream
					(new DieThrowSpliterator(), false);

		stream.map(i -> "You threw a " + i)
	              .forEach(System.out::println);
	}
}

First notice that we are creating the stream the same way we did when using an Iterable, but instead we are creating a spliterator which we pass to the stream. The second thing to notice is that we have to implement two tryAdvance functions. These take Consumers which will use our value. The first is a true IntConsumer, where as the second is a Consumer of any type which can hold an Integer (Object, Number and Integer). I’ve kept the null check used in other spliterators. If we’re already done, we can return false, otherwise pass a roll to the action and return true. The parent constructor of our spliterator takes two values, the first being how many values we expect (we don’t know) and flags for characteristics of the spliterator (0 being none of them).

No doubt we could continue the discussion on generation, particularly as we now have several ways to solve problems. For now we’ll move on and look at a few more aspects of Java 8 functional programming and lambda expressions.

Finite sequence generators in Java 8

… and introducing default methods.

Last time we looked at generators, and more specifically those generating an infinite sequence. We saw that there were several ways to achieve this:

  • The older Java 7 way with an iterator like class
  • Using Stream’s iterate method
  • Using Stream’s generate method

We also saw that when using a Stream we had to use the limit method on our infinite sequence otherwise it would keep generating and the program couldn’t continue. The problem with using limit was that once we’d got the values, we couldn’t use the stream again to get more. To solve this problem, we used an IntSupplier and created several streams with it to process batches of values.

What if the sequence we wanted to process was finite. We want to avoid buffering up values in advance. We also want to consume the sequence without knowing up front how many values it will return because of reasons such as:

  • We can’t work it out or it’s difficult to
  • There is a random element
  • We want to decouple the generating function from stream doing the consuming

We saw a simple finite sequence with our Hello World! example in the first article. In this case we were not generating the sequence with a function, we were instead processing a pre-initialised list. We also saw we could use an iterator when we discussed infinite sequences, but went on to discuss other ways. We’ll see that in this case, we are virtually forced into the Iterator solution.

Let’s take a simple sequence which we can’t know the length of. We’ll simulate a game where the idea is to keeping throwing a die until we get a six. First we’ll start with a non-functional implementation:

public class SixGame
{
	public static class DieThrowIterator implements Iterator<Integer>
	{
		private int dieThrow = 0;
		private Random rand = new Random(System.nanoTime());

		@Override
		public boolean hasNext()
		{
			return dieThrow != 6;
		}

		@Override
		public Integer next()
		{
			dieThrow = Math.abs(rand.nextInt()) % 6 + 1;
			return dieThrow;
		}
	}

	public static void main(String args[])
	{
		DieThrowIterator dieThrowIterator = new DieThrowIterator();

		while (dieThrowIterator.hasNext())
		{
			System.out.println("You threw a " + dieThrowIterator
                                  .next());
		}
	}
}

(Note our random number generation is not very robust, but for a simple demonstration it will do).

Let’s try to use a Stream. We can’t use Stream’s iterate function because it doesn’t allow a stop condition. Also an IntSupplier with generate is not an option unless we want to use limit(1) and create a stream for each die throw, when we might as well not use a stream at all.

If we look under the hood at the implementation of IntStream’s generate function we see that it creates an InfiniteSupplyingSpliterator. This has a problem for us – the tryAdvance function always returns true meaning we can never stop.

We could implement our own Spliterator where our tryAdvance checks for a stop condition. We can’t simply extend InfiniteSupplyingSpliterator and override the tryAdvance method since it’s an inner class of a default access class. So the only way is a cut and paste job rather than inheritance. I’m very nervous about copying large parts of code which might change in future versions; this is saying to me it’s not what was intended. We should look for other ways first.

Let’s look to see how List does its streaming. List’s streaming comes from inheriting Iterable. To create an Iterable we only need to implement its iterator() function – for the example let’s do so as an inner-class:

	public static class DieThrowIterable implements Iterable<Integer>
	{
		@Override
		public Iterator<Integer> iterator()
		{
			return new DieThrowIterator();
		}
	}

We can then stream:

	public static void main(String args[])
	{
		Stream<Integer> stream = StreamSupport.stream(
				new DieThrowIterable().spliterator(), false);

		stream.map(i -> "You threw a " + i).forEach(System.out::println);
	}

Wait a moment… Iterable is an interface, yet it has a spliterator() method implemented. How can that be?

If we look at the interface, there is indeed a spliterator() method creating a new spliterator for us. If we also look closely, we see the default keyword. This was added in Java 8 (cunningly default is already a reserved word for switch statements so it won’t break old code). When we write interfaces we can provide default methods already implemented. Now some people might have reservations about this as it’s turning an interface in to effectively an abstract class. There are some good reasons and advantages this gives us:

  • It avoids having to create abstract classes to implement interfaces to supply default methods. Thus there is less boiler-plate to write, and also prevents the consumer of the API implementing the interface when we expected the abstract class to be used instead.

  • It helps with multiple inheritance issues (inherting from two or more classes which C++ supports, but not Java). In Java, the problems with multiple inheritance were avoided by allowing only single inheritance from classes, but we can implement as many interfaces as desired. Problem is we had to implement large portions of those interfaces in each class that used them – a real pain.

  • Our API vendors can also now add new methods to interfaces without breaking old code. This is one reason we see a default method here. A new interface would make the JDK even larger and make things more complicated.

  • Lambda expressions bind to interfaces with one single method left to implement. If there were more we couldn’t do this binding. We’ll look at this in a future article.

Note: If we implement more than one interface with an identical default method, and we do not override it by implementing in the class or a parent class, this is an error. Whether eventually it’ll be possible to use Scala-like mix-in traits is an interesting question.

So using Iterable is one way to do finite sequence generators, although the documentation accompanying the default spliterator() method suggests it should be overridden for better performance. In a later article we’ll come back and look at spliterators in some more detail.

In the next article we’ll look another couple of ways to implement finite sequence generators, one good, and one we should avoid.

Generators with Java 8

Today we’ll look at creating generators. In simple terms, a generator is a function which returns the next value in a sequence. Unlike an iterator, it generates the next value when needed, rather than returning the next item of a pre-generated collection. Some languages such as Python support generators natively via keywords such as yield. When a generator’s next value is requested in Python, the generator function continues to run until the next yield statement, where a value is returned. The generator function is able to continue where it left off which can be quite confusing for the uninitiated. So how to do something similar in Java?

We saw in the last article that we can use an IntStream to generate a simple set of numbers, but we had to generate them all up front. That’s fine if we know how many we’re going to need. What if we don’t, and we want to be able to get the next whenever we like? This is where a generator comes in.

Let’s choose a simple infinite sequence, the square numbers. In a standard Java implementation we’d end up with something like the following:

public class Squares
{
        private int i = 1;

        public int next()
        {
                int thisOne = i++;
                return thisOne * thisOne;
        }

        public static void main(String args[])
        {
                Squares squareGenerator = new Squares();

                System.out.println(squareGenerator.next());
                System.out.println(squareGenerator.next());
                System.out.println(squareGenerator.next());
        }
}

This prints the first three square numbers. Note we could have gone further and implemented this as an iterator.

What we have here is an example of lazy evaluation in a non-functional style. Wikipedia defines lazy evaluation as: ‘In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed’. Lazy evaluation is useful because we don’t need to worry about infinite sequences, performing computationally expensive operations up-front, and about storage.

Let’s expand on the example to allow getting a batch of results. This is easy – create a nextN function which calls next() a number of times and returns the results in say a List:

public class Squares2
{
        private int i = 1;

        public int next()
        {
                int thisOne = i++;
                return thisOne * thisOne;
        }

        public List<Integer> nextN(int n)
        {
                List<Integer> l = new ArrayList<>();

                for (int i = 0; i < n; i++)
                {
                        l.add(next());
                }

                return l;
        }

        public static void main(String args[])
        {
                Squares2 squareGenerator = new Squares2();

                squareGenerator.nextN(10).forEach(System.out::println);
        }
}

A few points:

  • Notice in the nextN function there is the empty diamond in the new ArrayList statement. This was added in Java 7 to save having to state the type both on the left and the right hand side; the compiler now works it out.
  • List is an Iterable, and Iterable now has a forEach() method which was added in Java 8. We could use stream() as before to create a stream, but if all we want to do is pass the contents to a function forEach() does nicely.

Now, to save having to write nextN for every sequence we make, we could create a new type which extends Iterator providing the nextN function.

The only problem we face here is that we have to save the batch in a list before we can operate on it. Java 8 provides another way. Let’s go back and start again with the following code:

public class Squares3
{
        public static void main(String args[])
        {
                IntStream.rangeClosed(1, 10).map(i -> i * i)
                         .forEach(System.out::println);
        }
}

This uses IntStream to get the indexes of the sequence in a stream and calls map to convert them into their squares. The problem is that to get more squares than the tenth we need to duplicate the pipeline and start it off from the right place. Let’s look at another way without using a range:


        public static void main(String args[])
        {
                IntStream myStream = IntStream.iterate(1, i -> i + 1);

                myStream.limit(10).map(i -> i * i)
                                  .forEach(System.out::println);
        }

This also generates the first 10 square numbers. This time it uses the iterate function. This takes two parameters, the first is our initial value, and the second is a function defining how to get to the next value from the previous. It’s a good place to use a lambda function. We can even dispense of the map function since we can undo squaring easily in iterate to get what the last index was:

        public static void main(String args[])
        {
                IntStream myStream = IntStream.iterate(1,
                        i -> ((int) Math.pow(Math.sqrt(i) + 1, 2)));

                myStream.limit(10).forEach(System.out::println);
        }

This solves one of the problems of having to buffer beforehand. However, we need to use the limit operator on the stream to limit it to 10 items, otherwise it would keep on going. Unfortunately this is a problem, since once we’ve got the 10 the stream is ‘operated on’ and we can’t use it again to generate more. If we try, we get an IllegalStateException. We’d have to create another stream to get more.

So how do we get around the problem of the stream being used up? Instead of using IntStream’s iterate function, we can use generate instead. IntStream’s generate function takes an instance of an IntSupplier. IntSupplier has a getAsInt() function which returns the next int in the sequence which is very much like our next() function. Here is an example that prints the first 20 square numbers in two batches:

public class SquaresGenerator
{
        private static class SqSupplier implements IntSupplier
        {
                int i = 0;

                @Override
                public int getAsInt()
                {
                        i++;
                        return i * i;
                }
        }

        public static void main(String args[])
        {
                SqSupplier sqSupplier = new SqSupplier();
                IntStream myStream = IntStream.generate(sqSupplier);
                IntStream myStream2 = IntStream.generate(sqSupplier);

                myStream.limit(10).forEach(System.out::println);
                myStream2.limit(10).forEach(System.out::println);
        }
}

Again we’re using limit to stop the stream continuing indefinitely. However unlike last time, although the stream is used up, the generator still survives and can be used again. No buffering needed either, just keeping hold of the supplier. The only downside vs the old Java way is that we have to use Streams to get sequence members, although this comes with other benefits such as parallelism which we’ll see in a later article.

Overall, there are several ways to generate a sequence and which we chose may depend on our needs. Using an IntSupplier is a good way to integrate with the rest of the Java 8 functional programming support.