tag:blogger.com,1999:blog-69794855747398130122024-03-14T06:54:27.770+01:00Sebastian Millies: Dev-Blog Coding, Software Engineering and ArchitectureSebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-6979485574739813012.post-83655309747459874592016-10-21T00:59:00.001+02:002017-03-01T16:42:40.993+01:00Lazy tree walking made easy with Kotlin coroutinesLet's imagine a simple unbalanced binary tree structure, in which an abstract <span style="font-family: "courier new" , "courier" , monospace;">BinaryTree<E> </span>is either a concrete <span style="font-family: "courier new" , "courier" , monospace;">Node </span>labelled with a <span style="font-family: "courier new" , "courier" , monospace;">value </span>attribute of type <span style="font-family: "courier new" , "courier" , monospace;">E</span> and having a <span style="font-family: "courier new" , "courier" , monospace;">left </span>and <span style="font-family: "courier new" , "courier" , monospace;">right </span>subtree, or a concrete <span style="font-family: "courier new" , "courier" , monospace;">Empty</span> unlabelled tree. With trees, one very common requirement is to traverse the nodes in some appropriate order (preorder, inorder, or postorder).<br />
<br />
In this post, we are going to consider how to do that lazily. That is, we want to be able to short-circuit the traversal, visiting only as many nodes in the tree as we require to see. Moreover, we'd prefer a single-threaded solution. <br />
<ol>
</ol>
It's actually not trivial to do that in Java. With regard to iteration, you have to keep track of a lot state. (Cf. <a href="https://inst.eecs.berkeley.edu/~cs61b/sp06/labs/s9-3-1.html" target="_blank">these explanations</a> or look at the <a href="http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/TreeMap.java#l2143" target="_blank">source code</a> of <span style="font-family: "courier new" , "courier" , monospace;">java.util.TreeMap</span>) You might scrap single-threadedness and actually have two threads communicating over a blocking queue, but that also entails some complexity, especially with task cancellation on short-circuiting.<br />
<br />
And even when turning to stream-based processing instead of iteration, it doesn't quite work out as expected. Here's a proposed solution in a hypothetical <span style="font-family: "courier new" , "courier" , monospace;">BinaryTreeStreamer </span>class:<br />
<br />
<pre class="brush: java">/**
* Supplies a postorder stream of the nodes in the given tree.
*/
public static <E> Stream<Node<E>> postorderNodes(BinaryTree<E> t) {
return t.match(
empty -> Stream.<Node<E>> empty(),
node -> concat(Stream.of(node.left, node.right).flatMap(BinaryTreeStreamer::postorderNodes),
Stream.of(node)));
}
</pre>
The corresponding inorder- or preorder-traversals would be similar. The technique for structural pattern-matching with method <span style="font-family: "courier new" , "courier" , monospace;">BinaryTree#match()</span> goes back to Alonzo Church and is explained in more detail on <a href="http://blog.higher-order.com/blog/2009/08/21/structural-pattern-matching-in-java/" target="_blank">Rúnar Bjarnason's blog</a>. Basically, each subclass of <span style="font-family: "courier new" , "courier" , monospace;">BinaryTree </span>applies the appropriate function to itself, i. e. <span style="font-family: "courier new" , "courier" , monospace;">Empty </span>invokes the first argument of <span style="font-family: "courier new" , "courier" , monospace;">match</span>, and <span style="font-family: "courier new" , "courier" , monospace;">Node </span>the second.<br />
<br />
The code above looks quite reasonable, but unfortunately it is broken by the same JDK feature/bug that I mentioned over a year ago <a href="http://sebastian-millies.blogspot.de/2015/05/streamflatmap-may-cause-short.html" target="_blank">in this post</a>. Embedded <span style="font-family: "courier new" , "courier" , monospace;">flatMap </span>just isn't lazy enough, and breaks short-circuiting. Suppose we construct ourselves a tree representing the expression (3 - 1) * (4 / 2 + 5 * 6).<i><span style="font-family: inherit;"> </span></i>I'll use this as an example throughout this article. Then we start streaming, with the aim of finding out whether the expression contains a node for division:<br />
<br />
<pre class="brush: java">boolean divides = BinaryTreeStreamer.postorderNodes(tree).filter(node -> node.value.equals("/")).findAny().isPresent();
</pre>
<br />
which leads the code to traverse the entire tree down to nodes 5 and 6. And anyway, we are no closer to an iterating solution.<br />
<br />
Now in Python, things look quite different. The thing is, Python has <i>coroutines, </i>called <i>generators</i> in Python. Here's how <a href="https://en.wikipedia.org/wiki/Coroutine" target="_blank">Wikipedia</a> defines coroutines:<br />
<blockquote class="tr_bq">
<b>Coroutines</b> are <a href="https://en.wikipedia.org/wiki/Computer_program" title="Computer program">computer program</a> components that generalize <a href="https://en.wikipedia.org/wiki/Subroutine" title="Subroutine">subroutines</a> for <a class="mw-redirect" href="https://en.wikipedia.org/wiki/Nonpreemptive_multitasking" title="Nonpreemptive multitasking">nonpreemptive multitasking</a>, by allowing multiple <a href="https://en.wikipedia.org/wiki/Entry_point" title="Entry point">entry points</a> for suspending and resuming execution at certain locations.</blockquote>
<span class="rendered_qtext">In
Python you can say "yield" anywhere in a coroutine and
the calling coroutine starts up again with the value that was yielded.
Coroutines are like functions that return multiple times and keep their
state (which would </span><span class="rendered_qtext"><span class="rendered_qtext">include the values of local variables plus the command pointer) </span>so they can resume from where they yielded. Which means they have multiple entry points as well.</span> <span class="rendered_qtext">So here's a Python solution to our problem, with the <span style="font-family: "courier new" , "courier" , monospace;"><a href="https://dzone.com/articles/python-the-handy-defaultdict" target="_blank">defaultdict</a> </span>as the tree implementation, using <span style="font-family: "courier new" , "courier" , monospace;">value</span>, <span style="font-family: "courier new" , "courier" , monospace;">left </span>and <span style="font-family: "courier new" , "courier" , monospace;">right </span>as the dictionary keys. </span>(For a presentation that goes a bit beyond our simple example, e. g. see <a href="http://thatmattbone.com/binary-tree-traversal-in-python-with-generators.html" target="_blank">Matt Bone's page</a>.)<br />
<br />
<pre class="brush: python">tree = lambda: defaultdict(tree)
def postorder(tree):
if not tree:
return
for x in postorder(tree['left']):
yield x
for x in postorder(tree['right']):
yield x
yield tree
</pre>
<br />
<br />
One thing to note is that we must yield
each value from the sub-generators. Without that, although the recursive
calls would dutifully yield all required nodes, they would yield them
in embedded generators. We must append them one level up. That
corresponds to the successive flat-mapping in our Java code. Here's how
we can enumerate the first few nodes of our example tree in postorder. I
also show a bit of the Python tree encoding.<br />
<br />
<pre class="brush: python">expr = tree()
expr['value'] = '*'
expr['left']['value'] = '-'
expr['left']['left']['value'] = '3'
expr['left']['right']['value'] = '1'
…
node = postorder(expr)
print(next(node)['value'])
print(next(node)['value'])
print(next(node)['value'])
</pre>
<br />
Many other languages besides Python have coroutines, or something similar, if not in the language, then at least as a library. Java does not have them, so I started looking for other JVM languages that do. There aren't many. But I found <a href="http://storm-enroute.com/coroutines/learn/" target="_blank">a library for Scala</a>. However, Scala is not a language that Java developers readily embrace. The happier I was to learn that <a href="https://blog.jetbrains.com/kotlin/2016/07/first-glimpse-of-kotlin-1-1-coroutines-type-aliases-and-more/" target="_blank">coroutines will be a feature of Kotlin 1.1</a>, which is now in the early access phase.<br />
<br />
I had already known of <a href="https://kotlinlang.org/docs/reference/" target="_blank">Kotlin</a>. It is fun. It's very like Java, only better in many respects, it is 100% interoperable with Java, and – being developed by JetBrains – has great tool support from IntelliJ IDEA out-of-the-box. It really has a host of nice features. You might want to check out the following articles, which piqued my interest in the language.<br />
<ol>
<li><a href="https://blog.jooq.org/2016/03/31/10-features-i-wish-java-would-steal-from-the-kotlin-language/" target="_blank">10 Features I Wish Java Would Steal From the Kotlin Language</a> </li>
<li><a href="http://petersommerhoff.com/dev/kotlin/kotlin-for-java-devs/" target="_blank">Kotlin for Java Developers: 10 Features You Will Love About Kotlin</a></li>
<li><a href="https://medium.com/@octskyward/why-kotlin-is-my-next-programming-language-c25c001e26e3" target="_blank">Why Kotlin is my next programming language</a> </li>
</ol>
Kotlin seems to have gained popularity especially among Android developers, among the reasons being its small footprint and the fact that up to the release of <a href="https://www.android.com/versions/nougat-7-0/" target="_blank">Android Nougat</a>, people had been stuck with Java 6 on Android.<br />
<br />
The current milestone is <a href="https://blog.jetbrains.com/kotlin/2016/12/kotlin-1-1-m04-is-here/" target="_blank">Kotlin 1.1-M04</a>. In Kotlin, unlike Python, <span style="font-family: "courier new" , "courier" , monospace;">yield </span>is not a keyword, but a library function. Kotlin as a language has a more basic notions of <i>suspendable computation</i>. You can read all about it in <a href="https://github.com/Kotlin/kotlin-coroutines/blob/master/kotlin-coroutines-informal.md" target="_blank">this informal overview</a>. All that talk about <i>suspending lambdas</i> and <i>coroutine builders</i> and what not may seem somewhat intimidating, but fortunately there are already libraries that build upon standard Kotlin to provide functions that are easy to understand and use.<br />
<br />
One such library is <a href="https://github.com/Kotlin/kotlinx.coroutines" target="_blank">kotlinx-coroutines</a>. It contains a function <span style="font-family: "courier new" , "courier" , monospace;">generate</span> that takes a coroutine parameter. Inside that coroutine we can use <span style="font-family: "courier new" , "courier" , monospace;">yield</span> to suspend and return a value, just as in Python. The values are returned as a Kotlin <span style="font-family: "courier new" , "courier" , monospace;">Sequence</span> object. Let me show you my attempt to port the above Python code to Kotlin. I tried to do a faithful translation, almost line by line. That turned out to be pretty straightforward, which I can only explain by guessing that the designers of Kotlin's <span style="font-family: "courier new" , "courier" , monospace;">generate</span> must have been influenced by Python. <br />
<br />
<pre class="brush: plain">fun <E> postorderNodes(t : BinaryTree<E>): Iterable<Node<E>> = generate<Node<E>> {
when(t) {
is Empty -> {}
is Node -> {
postorderNodes(t.left).forEach { yield(it) }
postorderNodes(t.right).forEach { yield(it) }
yield(t)
}
}
}.asIterable()
</pre>
<br />
We can seamlessly use Kotlin classes in Java code and vice versa. However, instead of the Kotlin sequence, <span style="font-family: "courier new" , "courier" , monospace;">java.util.Iterable<span style="font-family: "courier new" , "courier" , monospace;"> </span></span>is much nicer to work with on the Java side of things. Fortunately, as shown above, we can simply call <span style="font-family: "courier new" , "courier" , monospace;">asIterable()</span> on the sequence to effect the conversion. So, let <span style="font-family: "courier new" , "courier" , monospace;">BinaryTreeWalker </span>be a Kotlin class that contains the Iterable-returning generator method, and look at some Java code exercising that method:<br />
<br />
<pre class="brush: java">Iterable<Node<String>> postfix = new BinaryTreeWalker().postorderNodes(expr);
Iterator<Node<String>> postfixIterator = postfix.iterator();
System.out.println(postfixIterator.next().value);
System.out.println(postfixIterator.next().value);
System.out.println(postfixIterator.next().value); </pre>
<br />
For our example tree, this will correctly print the sequence "31-" and visit no further nodes.<br />
<br />
Stream-processing is for free, as you can easily obtain a <span style="font-family: "courier new" , "courier" , monospace;">Stream </span>from the <span style="font-family: "courier new" , "courier" , monospace;">Iterable </span>with <span style="font-family: "courier new" , "courier" , monospace;">StreamSupport.stream(postfix.spliterator(), false)</span> That gives you a Java stream based on an iterator over a sequence backed by a Kotlin generator. On that stream, that little snippet looking for a division-node would work as well, only now it would <i>really </i>be lazy.<br />
<br />
Seamless integration also means that you are at liberty to migrate any class in a project to Kotlin, while all the rest stays in Java. For example, having written some JUnit tests for the expected behavior of the tree iterator in Java, I could simply keep these tests to verify the Kotlin class, after I had thrown out the Java implementation as insufficient.<br />
<br />
You can try this out yourself. The easiest way is to <a href="https://www.jetbrains.com/idea/download/" target="_blank">download </a>and install IntelliJ IDEA Community Edition. Then follow the instructions under "How to try it" in the <a href="https://blog.jetbrains.com/kotlin/2016/12/kotlin-1-1-m04-is-here/" target="_blank">Kotlin blog post</a>. I was able to create a Maven project with dependencies on kotlin-stdlib 1.1-M04 and kotlinx-coroutines 0.2-beta without problems.<br />
<br />
<span style="background-color: #eeeeee;"><i>Edit 2017-03-01: Today Kotlin 1.1 has been released. The <span style="font-family: "courier new" , "courier" , monospace;">generate </span>method has been moved to the Kotlin standard library under the name of <code><span style="font-size: 10.0pt;">buildSequence</span></code>. Thus to use it you don't have to depend on <code><span style="font-size: 10.0pt;">kotlinx.coroutines</span></code>,
just import that function from the package<code> <span style="font-size: 10.0pt;">kotlin.coroutines.experimental</span></code>. Here is the <a href="https://blog.jetbrains.com/kotlin/2017/03/kotlin-1-1/" target="_blank">release announcement</a>. </i></span><br />
<br />
In closing, I should mention the <a href="http://docs.paralleluniverse.co/quasar/" target="_blank">Quasar</a> library. I must admit I am not sure of the relation between Quasar and Kotlin coroutines. On the one hand, on the page cited, Quasar claims to "provide high-performance lightweight threads, Go-like channels,
Erlang-like actors, and other asynchronous programming tools for Java <b>and Kotlin</b>", on the other hand, this <a href="http://www.slideshare.net/abreslav/jvmls-2016-coroutines-in-kotlin" target="_blank">very informative presentation from JVMLS 2016</a> says that Kotlin coroutines are not based on Quasar, and are in effect a much simpler construct. The distinction here is between <i>stackless</i> and <i>stackful </i>coroutines. However, as the Kotlin blog now says (my emphasis)<br />
<blockquote class="tr_bq">
suspending functions are only allowed to make <i>tail-calls</i> to other suspending functions.
<i>This restriction will be lifted in the future. </i></blockquote>
this distinction may not be so relevant after all. There seems to be discussion at JetBrains whether to integrate more tightly with Quasar (<a href="https://github.com/Kotlin/kotlin-coroutines/issues/41" target="_blank">see this issue</a>). It will be interesting to see how this develops.<br />
<br />
Addendum: Just in case you're wondering, no, Kotlin sequences are no lazier than Java streams, the following Kotlin version of the initial Java attempt also traverses the entire tree when trying to find the first division node:<br />
<br />
<pre class="brush: plain"> fun <E> postorderNodes(t: BinaryTree<E>): Sequence<Node<E>> =
when(t) {
is Node -> {
(sequenceOf(t.left, t.right).flatMap { postorderNodes(it) }
+ sequenceOf(t))
}
else -> emptySequence()
}
</pre>
<br />Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-7093169216495377162016-09-30T12:18:00.000+02:002016-09-30T12:18:01.362+02:00Map InversionRecently, I had occasion to invert a map, i. e. exchange its keys and values. Having read several discussions on Stackoverflow (see <a href="http://stackoverflow.com/questions/36795890/functionally-inverting-a-map-with-a-nested-data-structure-in-java-8" target="_blank">here</a>, <a href="http://stackoverflow.com/questions/20412354/reverse-hashmap-keys-and-values-in-java" target="_blank">here</a>, and <a href="http://stackoverflow.com/questions/30021229/reverse-map-structure-using-java-8-streams" target="_blank">here)</a>, I decided to create my own utility, internally using Java streams. Besides simple maps, I wanted to be able to convert multimaps, both of the Google <a href="https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Multimap.html" target="_blank">Guava</a> and "standard Java" kind, the difference being that the entry set of a Guava multimap contains only elements with single values, whereas the entry set of a standard multimap contains an element with a Collection value.<br />
<br />
As an example, here's the code for the latter (and most complicated) case:<br />
<br />
<pre class="brush:java">/**
* Inverts a map. The map may also be a non-Guava multimap (i. e. the entrySet elements may have collections as values).
*
* @param map the map to inverted
* @param valueStreamer a function that converts an original map value to a stream. (In case of a multimap, may stream the original
* value collection.) Can also perform any other transformation on the original values to make them suitable as keys.
* @param mapFactory a factory which returns a new empty Map into which the results will be inserted
* @param collectionFactory a factory for the value type of the inverted map
* @return the inverted map, where all keys that map to the same value are now mapped from that value
*/
public static <K, V, V1, C extends Collection<K>> Map<V, C> invertMultiMap(Map<K, V1> map, Function<V1, Stream<V>> valueStreamer,
Supplier<Map<V, C>> mapFactory, Supplier<C> collectionFactory) {
Map<V, C> inverted = map.entrySet().stream().flatMap(e ->
valueStreamer.apply(e.getValue()).map(v -> new SimpleEntry<>(v, newCollection(e.getKey(), collectionFactory))))
.collect(toMap(Entry::getKey, Entry::getValue, (a, b) -> {a.addAll(b); return a;}, mapFactory));
return inverted;
}
private static <T, E extends T, C extends Collection<T>> C newCollection(E elem, Supplier<C> s) {
C collection = s.get();
collection.add(elem);
return collection;
}
</pre>
<br />
You can find the complete code, covering some more cases and with some tests, in <a href="https://gist.github.com/smillies/736659e0042fac48384c398eda6596ca" target="_blank">this Gist</a>. The tests depend on Guava.<br />
<br />
<br />Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-58724644835572688392016-05-03T00:02:00.002+02:002016-05-03T07:43:44.969+02:00Concurrent Recursive Function MemoizationRecently on concurrency-interest, there has been a <a href="http://concurrency.markmail.org/search/?q=#query:%20list%3Aedu.oswego.cs.concurrency-interest+page:3+mid:tf7xddfa6i6ow6d3+state:results" target="_blank">discussion </a>triggered by an observation that Heinz Kabutz made about <i>ConcurrentHashMap</i>. The observation being that the following plausible-looking coding is broken:<br />
<br />
<pre class="brush:java">public static class FibonacciCached {
private final Map<Integer, BigInteger> cache = new ConcurrentHashMap<>();
public BigInteger fib(int n) {
if (n <= 2) return BigInteger.ONE;
return cache.computeIfAbsent(n, key -> fib(n - 1).add(fib(n - 2)));
}
}
</pre>
<br />
<i>ConcurrentHashMap </i>livelocks for n ≥ 16. The reason, explained by Doug Lea, is that if the computation attempts to update any mappings, the results of this operation are undefined, but may include <i>IllegalStateExceptions</i>, or in concurrent contexts, deadlock or livelock. This is partially covered in the <a href="http://docs.oracle.com/javase/8/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function-" target="_blank"><i>Map </i>Javadocs</a>: "The mapping function should not modify this map during computation."<br />
<br />
Mainly in conversation between Viktor Klang and me, and based on an original idea of Viktor's, another approach was developed that appears workable compared to <i>computeIfAbsent</i>. The approach also harks back to two previous posts in this blog, namely the ones about <a href="http://sebastian-millies.blogspot.com/2016/02/recursive-function-memoization-with.html" target="_blank">memoization</a> and <a href="http://sebastian-millies.blogspot.com/2015/12/completablefuture-as-trampoline-for.html" target="_blank">trampolining</a>. The idea improves on the memoization scheme by providing reusable, thread-safe components for memoizing recursive functions, and combines that with a trampoline to process the function calls in such a way as to eliminate stack overflows.<br />
<br />
I'll present the idea with a few explanatory comments. If you want a step-by-step derivation, you can get that by reading the mail list archives. There are three parts to the code.<br />
<br />
First, a general purpose memoizer<br />
.
<br />
<pre class="brush:java">public static class ConcurrentTrampoliningMemoizer<T, R> {
private static final Executor TRAMPOLINE = newSingleThreadExecutor(new ThreadFactoryBuilder().setDaemon(true).build());
private final ConcurrentMap<T, CompletableFuture<R>> memo;
public ConcurrentTrampoliningMemoizer(ConcurrentMap<T, CompletableFuture<R>> cache) {
this.memo = cache;
}
public Function<T, CompletableFuture<R>> memoize(Function<T, CompletableFuture<R>> f) {
return t -> {
CompletableFuture<R> r = memo.get(t);
if (r == null) {
final CompletableFuture<R> compute = new CompletableFuture<>();
r = memo.putIfAbsent(t, compute);
if (r == null) {
r = CompletableFuture.supplyAsync(() -> f.apply(t), TRAMPOLINE).thenCompose(Function.identity())
.thenCompose(x -> {
compute.complete(x);
return compute;
});
}
}
return r;
};
}
}
</pre>
<br />
Second, a class that uses the memoizer to compute Fibonacci numbers.<br />
<br />
<pre class="brush:java">public static class Fibonacci {
private static final CompletableFuture<BigInteger> ONE = completedFuture(BigInteger.ONE);
private final Function<Integer, CompletableFuture<BigInteger>> fibMem;
public Fibonacci(ConcurrentMap<Integer, CompletableFuture<BigInteger>> cache) {
ConcurrentTrampoliningMemoizer<Integer, BigInteger> memoizer = new ConcurrentTrampoliningMemoizer<>(cache);
fibMem = memoizer.memoize(this::fib);
}
public CompletableFuture<BigInteger> fib(int n) {
if (n <= 2) return ONE;
return fibMem.apply(n - 1).thenCompose(x ->
fibMem.apply(n - 2).thenApply(y ->
x.add(y)));
}
}
</pre>
<br />
Third, any number of clients of a Fibonacci instance.<br />
<br />
<pre class="brush:java">Fibonacci fibCached = new Fibonacci(new ConcurrentHashMap<>());
BigInteger result = fibCached.fib(550_000).join();
</pre>
<br />
As the final usage example shows, the 550.000<sup>th</sup> Fibonacci number is about the largest I can get on my box, before all the cached <i>BigInteger </i>values cause an <i>OutOfMemoryError</i>. The <i>Fibonacci</i> instance may be shared among several threads. The whole thing seems to scale OK, as my tests with 2, 4, or 8 threads sharing the same instance indicate.<br />
<br />
The formulation of the <i>fib </i>method should be familiar to you from the <a href="http://sebastian-millies.blogspot.de/2016/02/recursive-function-memoization-with.html" target="_blank">previous blog entry on memoization</a>, except we're using a different monad here (<i>CompletableFuture </i>instead of <i>StateMonad</i>).<br />
<br />
The most interesting thing of course is the memoizer. Here are a few observations:<br />
<ul>
<li>On a cache miss a container (in the form of a <i>CompletableFuture</i>) is inserted into the cache which will later come to contain the value.</li>
<li>Different threads will always wind up using the same value instances, so the cache is suitable also for values that are supposed to be singletons. Null values are not allowed.</li>
<li>Only the thread that first has a cache miss calls the underlying function.</li>
<li>Concurrent readers/writers won't block each other (<i>computeIfAbsent </i>would do that for instance). </li>
<li>The trampolining happens because we can bounce off the queue in the executor to which <i>supplyAsync </i>submits tasks. The technique has been explained in <a href="http://sebastian-millies.blogspot.de/2015/12/completablefuture-as-trampoline-for.html" target="_blank">a previous post</a>. We are just inlining our two utility methods <i>terminate </i>and <i>tailcall</i>, and <i>fibMem </i>is the thunk. I find it interesting to see how we benefit from this even if there is no tail recursion.</li>
</ul>
I haven't shown a few obvious static imports. The <i>ThreadFactoryBuilder </i>is from Guava.<br />
<ul>
</ul>
You might want to pass in an executor to the memoizer from the outside. This would facilitate separate testing of the implementation vs. performance/scalability. However, performance seems to degrade when using anything but a dedicated single thread, so it may not be worth much in practice.<br />
<br />
I am sure there are very many ways to improve on the idea, but I'll leave it at that.Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com1tag:blogger.com,1999:blog-6979485574739813012.post-67474586655733276322016-02-08T21:00:00.000+01:002016-05-01T22:23:10.683+02:00Recursive Function Memoization with the State Monad<h3>
The State Monad
</h3>
What is the <i>State Monad?</i> If you have been following this blog, you already know the answer. In fact, the parser that we have seen in the <span style="color: blue;"><a href="http://sebastian-millies.blogspot.com/2016/01/dsls-with-graham-huttons-functional.html?spref=bl" target="_blank">previous pos<b>t</b></a></span> is one embodiment of it. In general terms, the state monad is just a glorified function that takes a state and computes from that a result value and some new state. Apart from embedding this function, the state monad has a few bells and whistles that help in combining such functions together. In functional
programming languages, the state monad is used to simulate external mutable state. The state monad's role is to pass down the state
through the calls of the function. The state parameter disappears from the
functions actually used.<br />
<br />
You have already seen a practical application of this in our parser. In the parser, the state values have been character sequences. We were able to process the input sequence without ever seeing a corresponding parameter in our methods.<br />
<br />
Besides parsing, another often-mentioned application of the state monad is recursive function memoization. In this case, the state will consist of pre-computed function values (a <i>memo</i>). We'll see how to memoize a recursive function that computes the Fibonacci numbers without tacking an extra memo argument onto the function (such as a HashMap). It is the state monad that will keep a memo of already computed values between recursive calls.<br />
<br />
You can google this stuff. People write about it often. For example, here are two articles that both deal with memoizing Fibonacci numbers, in a fashion similar to but not identical with mine: <span style="color: blue;"><a href="https://dzone.com/articles/do-it-in-java-8-state-monad" target="_blank">one in Java</a></span> by Pierre-Yves Saumont and <span style="color: blue;"><a href="http://blog.tmorris.net/posts/memoisation-with-state-using-scala/index.html" target="_blank">another in Scala</a></span> by Tony Morris. But both miss a point I am going to make below, namely how to factor out the memoization logic from the function itself. (Saumont, by the way, is in the process of writing what looks to be an <a href="https://www.manning.com/books/functional-programming-in-java" target="_blank">interesting book</a>.) <br />
<br />
I'll first show you how <a href="https://www.blogger.com/blogger.g?blogID=6979485574739813012#application">memoizing Fibonacci numbers</a> is done, and define <a href="https://www.blogger.com/blogger.g?blogID=6979485574739813012#memoize">a generic memoize method</a> that will enable memoization for any function. Only then will I show you how to derive the underlying <a href="https://www.blogger.com/blogger.g?blogID=6979485574739813012#monad">state monad implementation</a> through a few little refactorings of our <span style="font-family: "courier new" , "courier" , monospace;">SimpleParser</span>. This way, you won't be inundated with details, having no idea what they lead up to. I'm hoping that the code is clear enough to grasp its <i>intent </i>even without knowing the internals. If it doesn't work for you, try reading this post from the end to the beginning.<br />
<br />
And in <a href="https://www.blogger.com/blogger.g?blogID=6979485574739813012#discussion">the last section</a>, I'll give you my evaluation of the whole thing.<br />
<br />
<h3 id="application">
Memoizing Fibonacci numbers</h3>
I expect you all know from your introduction to algorithms course that the following naive version will blow up in your face:<br />
<br />
<pre class="brush: java">BigInteger fibNaive(int n) {
if (n <= 2) {
return BigInteger.ONE;
}
BigInteger x = fibNaive(n - 1);
BigInteger y = fibNaive(n - 2);
return x.add(y);
}
</pre>
<br />
One way to make the algorithm feasible is to remember previously computed values.<br />
<br />
<pre class="brush: java">BigInteger fibMemo(int n, Map<Integer, BigInteger> memo) {
BigInteger value = memo.get(n);
if (value != null) {
return value;
}
BigInteger x = fibMemo(n - 1, memo);
BigInteger y = fibMemo(n - 2, memo);
BigInteger z = x.add(y);
memo.put(n, z);
return z;
}
</pre>
<br />
The above is written in a non-functional style with an explicit extra argument. (I'll name it the <i>explicit version</i>.) You would call it like this, with a memo already containing the first two Fibonacci numbers:<br />
<br />
<pre class="brush: java">BigInteger fibMemo(int n) {
if (n <= 2) {
return BigInteger.ONE;
}
Map<Integer, BigInteger> memo = new HashMap<>();
memo.put(1, BigInteger.ONE);
memo.put(2, BigInteger.ONE);
return fibMemo(n, memo);
}
</pre>
<br />
Now wouldn't it be nice if we could get rid of that extra argument and the tedium of looking up and storing values, to derive a memoizing version that is closer to the naive version? And, yes, we can. Simply apply a new function, called <i>memoize</i>, to the original function.<br />
<br />
<pre class="brush: java">StateMonad<BigInteger, Memo<Integer,BigInteger>> fib(int n) {
return memoize(this::fib).apply(n-1).bind(x -> // x = memoize (fib) (n-1)
memoize(this::fib).apply(n-2).bind(y -> // y = memoize (fib) (n-2)
StateMonad.get(_s -> x.add(y)))); // return x.add(y)
}
</pre>
<br />
Basically, this is only a notational variant of the naive version, a bit difficult to read at first because Java lacks the syntactic sugar other
languages have. I have tried to indicate such sugar in the inline comment. Having had time to get used to it, I find it doesn't read too bad, just ignore the clutter of "apply" and "bind", and remember that the assignment is notated at the end of the line instead of the beginning. <br />
<br />
Well, we also had to change the return type a bit, it no longer represents a value, but a computation that yields this value (the function represented by the state monad). As you perhaps have guessed, the method <i>bind </i>above is the equivalent of <i>then </i>in our parser: the signature is the same, except the continuation that we put in, and the combined computation that we get out, are not parsers, but a more general <i>StateMonad</i> class that can have a memo as its state. As with the parser, the function inside the monad takes no arguments except the state, all other arguments are supplied beforehand.<br />
<br />
<br />
My main point is that here we have a very clear separation of concerns: There is one entity <i>memoize</i>, concerned with caching computed values, another entity, the <i>StateMonad</i>, concerned with passing the cached values between function calls, and finally <i>fib </i>itself, that embodies the definition of the Fibonacci numbers and is concerned with making recursive calls and combining their results.This is in contrast to the explicit version and also to both posts quoted above, where these concerns are more intertwined.<br />
<br />
For me, this is of the essence of functional programming, and therein lies its beauty: that it is so neat and modular on a small scale.<br />
<br />
In order to get a value from the computation that is returned by <i>fib</i>, we need to evaluate it against some suitable initial state. The function that does this is called <i>evalState</i>. (And this you also already know from the parser, where it was called just <i>eval</i>.)<br />
<br />
<pre class="brush: java">BigInteger fibMonadic(int n) {
return n <= 2 ? BigInteger.ONE
: fib(n).evalState(new Memo<Integer,BigInteger>().insert(1, BigInteger.ONE).insert(2, BigInteger.ONE));
}</pre>
<br />
The class <i>Memo </i>is intended to be a functional equivalent to HashMap.<br />
<br />
<h3 id="memoize">
Implementing generic memoization</h3>
So, what is <i>memoize</i>? The signature of <i>memoize </i>is obvious. It takes a function of the type of <i>fib </i>and returns another function of the same type. We can abstract over the input and result value types <i>Integer </i>and <i>BigInteger </i>of <i>fib</i> and replace them with generic type parameters <span style="font-family: "courier new" , "courier" , monospace;">T</span> and <span style="font-family: "courier new" , "courier" , monospace;">R</span>.<br />
<br />
Now think of what <i>memoize </i>has to do. It takes a function as its parameter. It must return a new function that<br />
<ul>
<li>when given an argument, tries to look up a previously computed value from the memo</li>
<li>if it finds the value, returns a function that will yield this value</li>
<li>otherwise, applies the given function to the given argument, stores that result in the memo, and returns a function will yield this value plus an updated state </li>
</ul>
As usual with functional maps, the memo shall return an <i>Optional</i> upon lookup, so that we can make the case distinction with <i>Optional</i>'s methods <i>map </i>and <i>orElse</i>.Without further ado, here's the code:<br />
<br />
<pre class="brush: java; wrap-lines: false">static <T,R> Function<T, StateMonad<R, Memo<T,R>>> memoize(Function<T, StateMonad<R, Memo<T,R>>> f) {
return t -> {
StateMonad<Optional<R>, Memo<T,R>> s = StateMonad.get(m -> m.lookup(t)); // create a computation that would try to find a cached entry
return s.bind(v -> // perform the computation, call the result v and do:
v.map(s::unit) // if value is present, return a computation that will yield the value
.orElse( // otherwise
f.apply(t).bind(r -> // compute r = f(t)
s.mod(m -> m.insert(t, r)).map(_v -> r) // apply a function to the memo that stores r in it, set the value of s to r
))); // return a computation that will yield r
};
};
</pre>
<h3>
</h3>
<br />
The appeal of <i>memoize </i>is that it is completely general and can be applied to any unary function.<br />
<br />
What about functions that take multiple arguments? Well, in Java you cannot abstract over functions with arbitrary arity. I suggest to take a suitable class, like the one from the wonderful <span style="color: blue;"><a href="https://github.com/jOOQ/jOOL" target="_blank"> jOOλ</a></span> library, that can represent an n-ary tuple, and treat an n-ary function as a unary function of such a tuple. (They should have added tuples to Java, every functional programming person is asking for them.)<br />
<br />
<h3 id="monad">
Implementing the state monad</h3>
The state monad itself is not so interesting. As I have noted above, it should be self-explanatory to readers familiar with the simple parser. Here's how you might change the parser to derive the monad in a few simple steps, mainly consisting of renamings:<br />
<ul>
<li>Abstract over the type of the state (replace <i>CharSequence </i>with a type variable <span style="font-family: "courier new" , "courier" , monospace;">S</span>)</li>
<li>Rename a few methods to what's customary in the functional world (e. g. Haskell)</li>
<ul>
<li><i>eval </i>to <i>evalState</i></li>
<li><i>parse </i>to <i>runState</i></li>
<li><i>then </i>to <i>bind</i></li>
</ul>
<li>Delete <i>many, </i><i>many1, </i>and <i>orElse.</i> (We don't need <i>orElse </i>in our example, but you might nevertheless decide to keep it. I guess that in some contexts, it might be useful for backtracking.) </li>
<li>Simplify <i>evalState </i>by removing the checking for unused input that was completely specific to parsing</li>
<li>You might also wish to rename a few variables. (I renamed <i>inp </i>for "input" to <i>s</i> for "state", <i>p</i> for "parser" to <i>m </i>for "monad" etc.)</li>
</ul>
All that remains is to define the new state-manipulating method <i>mod</i> and the static value-extracting utility <i>get</i>, which are used in the definition of <i>memoize</i>. That is very little work, and here is the complete resulting code. (I've left out the overloaded version of <i>bind</i>/<i>then</i> that we don't need for this example. Furthermore, the state monad is usually given a few more convenience methods, which we also don't need and which I'm not going to discuss here.) <br />
<br />
<pre class="brush: java">@FunctionalInterface
public interface StateMonad<T,S> {
default T evalState(S s) {
Objects.requireNonNull(s);
Tuple<T, S> t = runState(s);
if (t.isEmpty()) {
throw new IllegalArgumentException("Invalid state: " + s);
}
return t.first();
}
/**
* The type of the functional interface. A state monad is an abstraction over a function:
* StateMonad<T,S> :: S -> Tuple<T, S>
* In other words, a state monad represents a stateful computation that derives a value and
* some new state from an input state.
*/
abstract Tuple<T, S> runState(S s);
// Monadic operations
default <V> StateMonad<V,S> unit(V v) {
return inp -> tuple(v, inp);
}
default <V> StateMonad<V,S> bind(Function<? super T, StateMonad<V,S>> f) {
Objects.requireNonNull(f);
StateMonad<V,S> m = s -> {
Tuple<T, S> t = runState(s);
if (t.isEmpty()) {
return empty();
}
return f.apply(t.first()).runState(t.second());
};
return m;
}
default <V> StateMonad<V,S> map(Function<? super T, V> f) {
Objects.requireNonNull(f);
Function<V, StateMonad<V,S>> unit = x -> unit(x);
return bind(unit.compose(f));
}
// Additional functions
/** Modify the current state with the given function. */
default StateMonad<T, S> mod(Function<S, S> f) {
return s -> runState(f.apply(s));
}
/** Create a computation that extracts a value from the state with the given function. */
static <V, S> StateMonad<V, S> get(Function<S, V> stateProjector) {
return s -> tuple(stateProjector.apply(s), s);
}
}
</pre>
<br />
Of course we could have inlined that static call to the convenience function <i>StateMonad.get</i> in <i>memoize</i> (i. e. used the lambda directly), but that would have made the use of tuples visible in <i>memoize</i>.<br />
<br />
<h3 id="discussion">
Discussion</h3>
The trick I've shown you in this post is certainly appealing in its cleverness, and sometimes I quite admire it. But most of the time I feel that it is too clever by half. You've got to think practically. The functional version is (in Java) no better with regard to conciseness or readability than the explicit version. The effort to rewrite the naive definition to make use of memoization is also about the same in each case, because you have to make all those additional syntactic changes in addition to just throwing in a call to <i>memoize</i>. And as for performance, the monadic solution is about 5 times slower on my machine than the explicit one (for 100 ≤ n ≤ 1000).<br />
<br />
Then there is the matter of representing state. In OO, state is most naturally represented as a member variable of a class. Here's equivalent coding that fits into this paradigm.(Well, almost equivalent. This solution is not thread-safe. On the other hand one might reuse the <i>Memoizer </i>instance.)<br />
<br />
<pre class="brush: java">static class Memoizer<T, R> {
private final Map<T, R> memo;
public Memoizer(Map<T, R> memo) {
this.memo = memo;
}
public Function<T, R> memoize(Function<T, R> f) {
return t -> {
R r = memo.get(t);
if (r == null) {
r = f.apply(t);
memo.put(t, r);
}
return r;
};
}
}
Memoizer<Integer, BigInteger> m = new Memoizer<>(new HashMap<>());
BigInteger fib(int n) {
if (n <= 2) return BigInteger.ONE;
return m.memoize(this::fib).apply(n - 1).add(
m.memoize(this::fib).apply(n - 2));
} </pre>
<br />
And of course there is a simple, idiomatic, non-recursive, constant-space solution with mutable variables:<br />
<br />
<pre class="brush: java">BigInteger fib(int n) {
if (n <= 2) return BigInteger.ONE;
BigInteger x = BigInteger.ONE;
BigInteger y = BigInteger.ONE;
BigInteger z = null;
for (int i = 3; i <= n; i++) {
z = x.add(y);
x = y;
y = z;
}
return z;
}
</pre>
<br />
So be careful when you take over an idea from functional programming. You may be able to retain some of the beauty, but in other respects you won't always win. In fact, sometimes you'll lose. Don't overdo it. Functional thinking may offer you a different - and useful - perspective on a problem, as I hope to have shown with the parser and some other posts. But a functional solution is not guaranteed to be <i>per se</i> more readable, more maintainable, or more efficient than a good old vanilla object-oriented or imperative solution. Often, it will be neither. Java is not a functional programming language!<br />
<br />
<h3>
Addendum </h3>
For the sake of completeness, here's the <i>Memo </i>class that I have used for demo purposes. It's a mutable map masquerading as a functional data structure. Very bad. Don't copy it. You may put trace statements in these two methods to see in what order elements are computed and retrieved, and that they are indeed computed only once. The method names are the same as in <a href="http://totallylazy.com/" target="_blank">TotallyLazy</a>'s <i>PersistentMap</i>.<br />
<br />
<pre class="brush: java">class Memo<K, V> extends HashMap<K, V> {
public Optional<V> lookup(K key) {
Optional<V> value = Optional.ofNullable(get(key));
return value;
}
public Memo<K, V> insert(K key, V value) {
put(key, value);
return this;
}
}
</pre>
Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com3tag:blogger.com,1999:blog-6979485574739813012.post-52250996296131742282016-01-10T23:05:00.000+01:002016-01-10T23:05:14.366+01:00DSLs with Graham Hutton's Functional ParserOne of the best introductions to functional programming is Graham Hutton's excellent book <i>Programming in Haskell</i>. Although it is primarily a course on the Haskell programming language, it also provides an introduction to the underpinnings of functional programming in general. It is very readable, aimed at the undergraduate level. I think it should be on the shelf of every student of functional programming.<br />
<br />
I had thought of writing a book review, but there's really no need for it. You can find in-depth technical reviews on <a href="http://www.cs.nott.ac.uk/~pszgmh/book.html" target="_blank">the book's site</a>, and more: You can download slides for each chapter, watch video lectures, and get the complete Haskell source code of all the examples. That is for free, without even buying the book - a tremendous service.<br />
<br />
Instead of a review, I'll show you what I did for an exercise. I ported the functional parser that Hutton presents in chapter 8 of his book to Java. My aim is to demonstrate the following:<br />
<ul>
<li>Mastering functional idioms will help you to create powerful interfaces supporting a fluent programming style in Java</li>
<li>Of particular use in abstracting from tedious glue code are <i>monadic </i>interfaces, i. e. basically those that have a <span style="font-family: "Courier New",Courier,monospace;">flatMap </span>method</li>
<li>There is a special way of encapsulating internal state that is sometimes useful</li>
</ul>
The parser itself is a recursive descent parser of the kind you wouldn't necessarily use for large and complex grammars. (You'd perhaps use a compiler-compiler or parser generator tool like ANTLR or Xtext/Xtend.) However, you might use it to quickly spin-off a little DSL or demo coding. The real point is not the parser, but the approach to application design.<br />
<br />
In the following, some of the text is taken verbatim from Hutton's book, some is my own. I shall not bother with quotes and attributions, because I am not claiming any original ideas here. Remember: this is just an exercise in porting Haskell to Java. However, I'll try to be helpful by interspersing a few extra examples and comments.<br />
<br />
Nevertheless, this post is going to be a bit tedious, in the way textbooks are. I apologize in advance. If you're feeling impatient, perhaps you might want to scroll down and look at the <a href="https://www.blogger.com/blogger.g?blogID=6979485574739813012#arithmetic">final example</a>, a little parser for arithmetic expressions. I summarize my experiences and give some advice in the <a href="https://www.blogger.com/blogger.g?blogID=6979485574739813012#lessons">concluding section</a>.<br />
<br />
<h3>
Basic parsers</h3>
<br />
So what is a parser? It is a function that takes an input character sequence and produces a pair comprising a result value and an output character sequence, the unconsumed rest of the input. Let's abstract over the type of the result value and define a corresponding functional interface:<br />
<br />
<pre class="brush: java">@FunctionalInterface
public interface SimpleParser<T> {
abstract Tuple<T, CharSequence> parse(CharSequence cs);
}
</pre>
<br />
Hutton's parser in fact returns a list, to include the possibility of returning more than one result if the input sequence can be parsed in more than one way. For simplicity, however, he only considers parsers that return at most one result. For that reason, I have opted for the simpler signature. It follows that our parser cannot handle ambiguity. You might want to do the generalization yourself.<br />
<br />
I shall assume the existence of a special <span style="font-family: "Courier New",Courier,monospace;">empty</span> tuple, which has no components, as an analogue to the empty list, which signifies that the input cannot be parsed at all. (Otherwise, the type <span style="font-family: "Courier New",Courier,monospace;">Tuple</span> is just what you might expect.)<br />
<br />
We will now define some basic parsers, and then see how we can arrange them in a hierarchy of ever higher-level derived parsers. First, here's a method that produces a basic parser that always succeeds with the given result value without consuming any input:<br />
<br />
<pre class="brush: java">default <V> SimpleParser<V> unit(V v) {
return inp -> tuple(v, inp);
}
</pre>
<br />
In Haskell, this method would be called "return", but of course that's not possible in Java. We'll also provide <span style="font-family: "Courier New",Courier,monospace;">output, </span>a static analogue to <span style="font-family: "Courier New",Courier,monospace;">unit</span>, and <span style="font-family: "Courier New",Courier,monospace;">failure</span>, a way to produce a parser that always fails regardless of the input. In fact, we'll define quite a few static factory methods for creating parsers. These I have collected in a separate utility class <span style="font-family: "Courier New",Courier,monospace;">SimpleParserPrimitives</span>. The parser interface itself will contain only the (non-static) methods to combine and manipulate parsers. It will turn out that these methods are quite general. You might re-use them, and each time you might well provide a different set of parsing "primitives" for a different parsing purpose. The primitives I will be discussing are geared towards parsing programming languages.<br />
<br />
<pre class="brush: java">public static <T> SimpleParser<T> output(T v) {
return inp -> tuple(v, inp);
}
public static <T> SimpleParser<T> failure() {
return _inp -> empty();
}
</pre>
<br />
The method <span style="font-family: "Courier New",Courier,monospace;">empty </span>returns the empty tuple, representing failure. Our final basic parser is <span style="font-family: "Courier New",Courier,monospace;">item</span>, which fails if the input string is empty, and succeeds with the first character as the result value otherwise.<br />
<br />
<pre class="brush: java">public static SimpleParser<Character> item() {
return inp -> inp.length() == 0 ? empty() : tuple(inp.charAt(0), inp.subSequence(1, inp.length()));
}
</pre>
<br />
<h3>
Sequencing</h3>
<br />
Suppose we want to parse an arithmetic expression like "5 + 4 * 3". One way to decompose the problem is to create a parser for the numeral "5", and a parser for the rest of the expression "+ 4 * 3" (which we would again decompose into a parsers for the symbol "+" and the expression "4 * 3" and so on.) We then look for a way to combine these parsers into a parser for the whole expression. The combined parser shall execute the parsing steps one after the other. In the process of doing that we need to make decisions based on the result of the previous step. One such decision is if and how to continue parsing the rest of the input or not. If we want to continue, we must pass on the intermediate result to the following step.<br />
<br />
Here's the signature of such a method that takes a description of the future parsing steps, and returns a new parser that will execute the current step combined with those future ones:<br />
<br />
<pre class="brush: java">default <V> SimpleParser<V> then(Function<? super T, SimpleParser<V>> f)
</pre>
<br />
The returned parser fails if the application of the current parser to the input string fails, and otherwise applies the function f to the result value to give a second parser q, which is then applied to the output string to give the final result. Thus, the result value produced by this parser is made directly available for processing in the remaining steps by binding it to a lambda variable in a function describing those remaining steps. For example, the expression<br />
<br />
<pre class="brush: java">p.then(x -> output(x));
</pre>
<br />
may be read as: Parse the input using the parser p, and then, calling the result "x", apply output() to x.<br />
<br />
The method <span style="font-family: "Courier New",Courier,monospace;">then</span> corresponds to <span style="font-family: "Courier New",Courier,monospace;">flatMap </span>on Java <span style="font-family: "Courier New",Courier,monospace;">Stream </span>and <span style="font-family: "Courier New",Courier,monospace;">Optional</span>, resp. to<span style="font-family: "Courier New",Courier,monospace;"> CompletableFuture.thenCompose()</span>, which are the three "monadic" interfaces built into Java 8. These methods all have the property of chaining computations together (in the case of streams like nested for-loops, as I have discussed in several earlier posts.) Here's the implementation. You can see how each line corresponds to a part of the description we have given above.<br />
<br />
<pre class="brush: java">default <V> SimpleParser<V> then(Function<? super T, SimpleParser<V>> f) {
Objects.requireNonNull(f);
SimpleParser<V> pf = inp -> {
Tuple<T, CharSequence> t = parse(inp);
if (t.isEmpty()) {
return empty();
}
return f.apply(t.first()).parse(t.second());
};
return pf;
}
</pre>
<br />
Let's look what we can do with the building blocks we have assembled so far. Here's a contrived example. The parser<span style="font-family: "Courier New",Courier,monospace;"> p</span> consumes three characters, discards the second, and returns the distance between the first and the third:<br />
<br />
<pre class="brush: java">@Test
public void composition() {
SimpleParser<Integer> p =
item().then( x ->
item().then( y ->
item().then( z ->
output(z - x)
)));
assertEquals(tuple(2,"def"), p.parse("abcdef"));
assertEquals(empty(), p.parse("ab"));
}
</pre>
Notice how the formatting goes some way to hide the nesting of the constructs. I find the code better readable that way, because conceptually, we are just executing parsing steps in sequence. Note, too, how we are ignoring the variable <span style="font-family: "Courier New",Courier,monospace;">y</span> in the last two steps. Let's introduce a variant on <span style="font-family: "Courier New",Courier,monospace;">then</span> that allows us to dispense with this superfluous variable.<br />
<br />
<pre class="brush: java">default <V> SimpleParser<V> then(Supplier<SimpleParser<V>> p) {
Objects.requireNonNull(p);
return then(_v -> p.get());
}</pre>
<br />
The above parser can now be rewritten without the unused variable:<br />
<br />
<pre class="brush: java"> SimpleParser<Integer> p =
item().then( x ->
item().then( () ->
item().then( z ->
output(z - x)
)));
</pre>
<br />
Note the use of <span style="font-family: "Courier New",Courier,monospace;">Supplier</span> to enforce laziness: One could not simply overload <span style="font-family: "Courier New",Courier,monospace;">then</span> to accept a parser instance, because that would imply that the argument parser <span style="font-family: "Courier New",Courier,monospace;">p</span> were immediately constructed by the caller, while otherwise it is constructed only <i>after </i>the current parser has completed successfully. But at least we do no longer have to litter our code with dummy variables. Haskell has nice syntactic sugar ("do-notation") that allows just leaving out the unused variables, and also hides the nesting of the calls (what I have tried to achieve by code formatting).<br />
<br />
Also note how there's no reference to the input that is being parsed in the definition of our little parser. There is no explicit variable of type <span style="font-family: "Courier New",Courier,monospace;">CharSequence</span> being threaded through the calls, or anything like that. All the mechanics of state handling are neatly encapsulated inside <span style="font-family: "Courier New",Courier,monospace;">then</span>. <br />
<br />
<h3>
Derived parsers</h3>
<br />
We can now start combining our basic parsers in meaningful ways to derive more parsing primitives. First, we build upon <span style="font-family: "Courier New",Courier,monospace;">item </span>to define a parser that
accepts a certain character only if it satisfies some predicate. And
with the help of the utility methods in <span style="font-family: "Courier New",Courier,monospace;">java.lang.Character</span>
we can go on to define parsers for all kinds of character classes, like
digits, lower and upper case letters, alphanumeric characters or
whitespace. For example:<br />
<br />
<pre class="brush: java">/** A parser that returns the next character in the input if it satisfies a predicate. */
public static SimpleParser<Character> sat(Predicate<Character> pred) {
Objects.requireNonNull(pred);
return item().then(x -> pred.test(x) ? output(x) : failure());
}
/** A parser that returns the next character in the input if it is the given character. */
public static SimpleParser<Character> character(Character c) {
return sat(x -> c.equals(x));
}
/** A parser that returns the next character in the input if it is a digit. */
public static SimpleParser<Character> digit() {
return sat(Character::isDigit);
}
/** A parser that returns the next character in the input if it is a whitespace character. */
public static SimpleParser<Character> whitespace() {
return sat(Character::isWhitespace);
}
</pre>
<br />
With <span style="font-family: "Courier New",Courier,monospace;">character</span> we can recursively recognize strings.<br />
<br />
<pre class="brush: java">public static SimpleParser<String> string(String s) {
Objects.requireNonNull(s);
return s.isEmpty() ? output("") : character(s.charAt(0)).then(() -> string(s.substring(1)).then(() -> output(s)));</pre>
<pre class="brush: java">}</pre>
<br />
The base case states that the empty string can always be parsed. The recursive case states that a non-empty string can be parsed by parsing the first character, parsing the remaining characters, and returning the entire string as the result value.<br />
<br />
<h3>
Choice and repetition</h3>
<br />
There are more ways to combine parsers than simple sequencing. We often need to express alternative ways of parsing one string ("choice"), and we need repetition, where a string is parsed by the repeated application of the same parser.<br />
<br />
<pre class="brush: java">/** Applies the given parser if this parser fails. */
default SimpleParser<T> orElse(SimpleParser<T> p) {
Objects.requireNonNull(p);
return inp -> {
Tuple<T, CharSequence> out = parse(inp);
return out.isEmpty() ? p.parse(inp) : out;
};
/** Applies this parser at least once or not at all. */
default SimpleParser<List<T>> many() {
return many1().orElse(unit(emptyList()));
}
/** Applies this parser once and then zero or more times. */
default SimpleParser<List<T>> many1() {
return then(c -> many().then(cs -> unit(cons(c, cs))));
}
</pre>
<br />
(<span style="font-family: "Courier New",Courier,monospace;">cons </span>is a utility that adds an element at the front of a persistent list. Think of copying the <span style="font-family: "Courier New",Courier,monospace;">cs</span> to a new list and adding <span style="font-family: "Courier New",Courier,monospace;">c</span> at index 0.)<br />
<br />
Note that <span style="font-family: "Courier New",Courier,monospace;">many</span> and <span style="font-family: "Courier New",Courier,monospace;">many1</span> are mutually recursive. In particular, the definition for <span style="font-family: "Courier New",Courier,monospace;">many</span> states that a parser can either be applied at least once or not at all, while the definition for <span style="font-family: "Courier New",Courier,monospace;">many1</span> states that it can be applied once and then zero or more times. The result of applying a parser repeatedly is a list of the collected results. At some point, we may want to convert this list back to a single value, e. g. we'd perhaps like to convert a sequence of digits to an integer value.<br />
<br />
<pre class="brush: java">public static SimpleParser<Integer> nat() {
return digit().many1()
.then(cs -> output(ParserUtils.charsToString(cs)))
.then(s -> output(Integer.parseInt(s)));
}
</pre>
<br />
This looks a bit clumsy, after all we are only transforming the result value inside a parser without actually consuming any input. It would be more natural if we had a method <span style="font-family: "Courier New",Courier,monospace;">map </span>to do that. (BTW, Hutton does not include such a method.) Fortunately, <span style="font-family: "Courier New",Courier,monospace;">map </span>is easy to define in terms of <span style="font-family: "Courier New",Courier,monospace;">unit</span> and <span style="font-family: "Courier New",Courier,monospace;">then</span>. In fact, it is axiomatic that this definition should be valid, otherwise we have made a mistake in the definition of our flatMap-analogue <span style="font-family: "Courier New",Courier,monospace;">then</span> (probably not with <span style="font-family: "Courier New",Courier,monospace;">unit</span>, since it is so simple).<br />
<br />
<pre class="brush: java">default <V> SimpleParser<V> map(Function<? super T, V> f) {
Objects.requireNonNull(f);
Function<V, SimpleParser<V>> unit = this::unit;
return then(unit.compose(f));
}</pre>
<br />
A new parser is "wrapped" around the output of the function f, as opposed to <span style="font-family: "Courier New",Courier,monospace;">then</span>, which already takes a parser-bearing function and does not wrap it with another parser. The analogy with <span style="font-family: "Courier New",Courier,monospace;">map </span>and <span style="font-family: "Courier New",Courier,monospace;">flatMap </span>on <span style="font-family: "Courier New",Courier,monospace;">Stream </span>is obvious. Our code for parsing a natural number now becomes more readable. And we can now also use method references.<br />
<br />
<pre class="brush: java">public static SimpleParser<Integer> nat() {
return digit().many1()
.map(ParserUtils::charsToString)
.map(Integer::parseInt);
}
</pre>
<br />
<h3>
Tokenization</h3>
<br />
In order to handle spacing, we introduce a new parser <span style="font-family: "Courier New",Courier,monospace;">token </span>that ignores any space before and after applying some given parser to an input string.<br />
<br />
<br />
<pre class="brush: java">/** A parser that collapses as many whitespace characters as possible. */
public static SimpleParser<String> space() {
return whitespace().many().map(s -> "");
}
/** A parser that ignores any space around a given parser for a token. */
public static <T> SimpleParser<T> token(SimpleParser<T> p) {
Objects.requireNonNull(p);
return space().then(() -> p.then(v -> space().then(() -> output(v))));
}
</pre>
<br />
We may be interested in a diversity of tokens, according to our target language, such as tokens for variable names and other identifiers, reserved words, operators, numbers etc. For example, we can define<br />
<br />
<pre class="brush: java">/** A parser for a natural number token. */
public static SimpleParser<Integer> natural() {
return token(nat());
}
/** A parser for a symbol token. */
public static SimpleParser<String> symbol(String sym) {
Objects.requireNonNull(sym);
return token(string(sym));
}
</pre>
<br />
This completes our overview of the parsing primitives. Let's see a few applications.<br />
<br />
<h3>
Lists of numbers </h3>
<br />
The following test defines a parser for a non-empty list of natural numbers that ignores spacing around tokens. This definition states that such a list begins with an opening square bracket and a natural number, followed by zero or more commas and natural numbers, and concludes with a closing square bracket. Note that the parser should only succeed if a complete list in precisely this format is consumed.<br />
<br />
<pre class="brush: java">@Test
public void tokenization() {
SimpleParser<List<Integer>> numList =
symbol("[").then(() ->
natural().then(n ->
symbol(",").then(() -> natural()).many().then(ns ->
symbol("]").then(() ->
output(cons(n,ns))))));
assertEquals(tuple(asList(1,2,3),""), numList.parse("[1,2,3]"));
assertEquals(tuple(asList(11,22,33),""), numList.parse(" [11, 22, 33 ] "));
assertEquals(tuple(asList(11,22,33),"abc"), numList.parse(" [11, 22, 33 ] abc"));
assertEquals(empty(), numList.parse("[1, 2,]"));
}
</pre>
<br />
You get the idea. There is one shortcoming: Detecting failure on account of ill-formed or unused input involves examining the output tuples in caller code. This may not always be what we want.<br />
<br />
<h3>
Representing failure</h3>
<br />
What would one expect to happen when some input is not accepted? In Java one would certainly expect an exception to be thrown. However, that is not so easy here. Of course, we cannot make <span style="font-family: "Courier New",Courier,monospace;">then</span> or <span style="font-family: "Courier New",Courier,monospace;">failure </span>throw an exception instead of returning <span style="font-family: "Courier New",Courier,monospace;">empty()</span>, because that would abort <i>all </i>possible search paths, not just the one we're currently on. Putting exception handling code for regular control flow into <span style="font-family: "Courier New",Courier,monospace;">orElse</span> I also consider bad. The best thing to do, I suppose, is to add a top-level method to the parser that would examine the parsing result.<br />
<br />
<pre class="brush: java">default T eval(CharSequence cs) {
Objects.requireNonNull(cs);
Tuple<T, CharSequence> t = parse(cs);
if (t.isEmpty()) {
throw new IllegalArgumentException("Invalid input: " + cs);
}
CharSequence unusedInput = t.second();
if (unusedInput.length() > 0) {
throw new IllegalArgumentException("Unused input: " + unusedInput);
}
return t.first();
}
</pre>
<br />
This way, we have also successfully hidden the internal use of tuples from callers of the parser, which is a good thing.<br />
<br />
<h3 id="arithmetic">
Arithmetic expressions</h3>
<br />
Hutton presents an extended example for parsing arithmetic expressions. The example serves to show how easy it can be to create a little DSL.<br />
<br />
Consider a simple form of arithmetic expressions built up from natural numbers using addition, multiplication, and parentheses. We assume that addition and multiplication associate to the right, and that multiplication has higher priority than addition. Here's an unambiguous BNF grammar for such expressions.<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;">expr ::= term (+ expr | nil)</span><br />
<span style="font-family: "Courier New",Courier,monospace;">term ::= factor (∗ term | nil)<br />factor ::= natural | (expr)<br />natural ::= 0 | 1 | 2 | · · ·</span><br />
<br />
It is now straightforward to translate this grammar into a parser for expressions, by simply rewriting the rules using our parsing primitives. We choose to have the parser itself evaluate the expression to its integer value, rather than returning some form of tree.<br />
<br />
<pre class="brush: java">SimpleParser<Integer> expr() {
return term().then(t ->
symbol("+").then(() -> expr().then(e -> output(t + e)))
.orElse(output(t)));
}
SimpleParser<Integer> term() {
return factor().then(f ->
symbol("*").then(() -> term().then(t -> output(f * t)))
.orElse(output(f)));
}
SimpleParser<Integer> factor() {
return natural()
.orElse(
symbol("(").then(() ->
expr().then(e ->
symbol(")").then(() ->
output(e)))));
}
</pre>
<br />
I like the look of that. Once you get used to the formalism, writing the parser is as easy as writing the grammar in the first place. Let's test the whole thing:<br />
<br />
<pre class="brush: java">@Test
public void multiplicationTakesPrecedence() {
assertThat( expr().eval("2+3*5"), is(17) );
}
</pre>
<h3>
Laziness</h3>
<br />
Notice how we have created functions at each
step that only get evaluated when we actually use them. Only then is a
new parser instantiated. The construction of the parser is interleaved
with its execution. As mentioned above, it is important in this context that <span style="font-family: "Courier New",Courier,monospace;">then</span>
always takes a function, if necessary even a no-argument function, that
yields a parser, never directly a parser instance. If that were
different, we might actually have an infinite loop, e. g. expr() →
term() → factor() → expr(), where the last call to expr() would be that
in the "orElse"-clause, because Java as a strict language evaluates
method arguments immediately.<br />
<br />
<h3>
Recursive lambdas</h3>
<br />
You may wonder why I have written the expression parser in terms of methods, instead of declaring instance variables for the functions <i>expr</i>, <i>term</i>, and <i>factor</i>.The reason is that lambdas capture local variables by value when they are created, and we would therefore get a compile-time error: "Cannot reference a field before it is defined". The only way to write recursive lambdas is to make everything static and use fully qualified names (see <a href="http://www.lambdafaq.org/can-lambda-expressions-be-used-to-define-recursive-functions/" target="_blank">the Lambda FAQ</a>).<br />
<br />
<br />
<h3 id="lessons">
Lessons learned</h3>
<br />
I feel I have learned something from this exercise, especially about the feel of functional programming in Java. A few particular lessons have been:<br />
<ul>
<li>"Monadic" interfaces are easy to design once you get your head around <span style="font-family: "Courier New",Courier,monospace;">flatMap</span> and its relatives. This method in its various guises, in <span style="font-family: "Courier New",Courier,monospace;">Stream</span>, <span style="font-family: "Courier New",Courier,monospace;">Optional</span>, <span style="font-family: "Courier New",Courier,monospace;">CompletableFuture</span> or our <span style="font-family: "Courier New",Courier,monospace;">SimpleParser</span>, is a powerful tool you need to understand.</li>
<li>When you need to add functionality to your lambdas, default methods in interfaces are the way to go. You can instantiate your functions with lambda expressions, and then combine them fluently in a variety of interesting ways.This is also what the JDK does, e. g. the <span style="font-family: "Courier New",Courier,monospace;">Function</span> interface has a default method <span style="font-family: "Courier New",Courier,monospace;">compose</span> for functional composition.</li>
<li>Our parser interface has rather many (in fact, eight) default methods. All these default methods are strongly coupled. It is generally accepted that this is bad when designing for inheritance (cf. what Josh Bloch has to say in <i>Effective Java</i>, 2nd ed., items 17 and 18). Perhaps that is a reason to feel a bit queasy about the approach.Which leads me to the next point.</li>
<li>Functional interfaces need not be designed for inheritance, so that in contrast to "ordinary" interfaces, strong coupling is acceptable: I have adopted a practice according to which I do not extend functional interfaces and
implement them only with lambdas. (It's nevertheless OK to extend another functional interface in order to specialize a generic type variable or add a few little static utilities. That is what <span style="font-family: "Courier New",Courier,monospace;">UnaryOperator</span> and <span style="font-family: "Courier New",Courier,monospace;">BinaryOperator</span> do, and they are the only two of the 57 functional interfaces in the JDK to extend another interface.) </li>
<li>Functions are great for re-usability. Being implemented via interfaces, they
are usually public. As a consequence, data structures tend to leak all over the
place. (We had to take special care to hide the use of tuples.) I guess that this is part of the functional mind-set: While in the OO-world, we encapsulate and hide as
much we can (with reason), this is less important in the functional world. </li>
<li>Don't clutter your interfaces with too many static methods. It is sometimes difficult to decide where a static method should go (e. g. <span style="font-family: "Courier New",Courier,monospace;">output </span>and <span style="font-family: "Courier New",Courier,monospace;">failure </span>are so essential, should they have been put into the parser interface?).</li>
<li>Java is really not a functional programming language.Stay with idiomatic Java as far as possible. Some of the things that I found to be missing in Java to make it more "functional" are </li>
<ul>
<li>persistent collections, tuples (you can pull-in third party libraries)</li>
<li>some important syntactic sugar like do-notation, inconspicuous unused variables (perhaps underscore only) etc. Nested constructs can quickly become difficult to read.</li>
<li>the ability to write non-static recursive lambdas. </li>
<li>a nice syntax for functional application.</li>
</ul>
<li>Beware of Java's eagerness, prefer lazy idioms. </li>
<li>Don't kill your backtracking with exceptions.</li>
<li>Do not throw checked exceptions from your code. Sooner or later (probably sooner) it's going to be a pain when you want it to work with lambdas, because all the most important standard functional methods in the JDK - like <span style="font-family: "Courier New",Courier,monospace;">Function#apply()</span> - do not have a <i>throws</i>-clause.</li>
</ul>
In my IDE (Eclipse Mars) I have been annoyed by two things in particular. I don't know if other IDEs offer a better experience.<br />
<ul><ul>
</ul>
<li>Debugging lambdas is a pain. (As an exercise, you might replace <span style="font-family: inherit;"><span style="font-family: "Courier New",Courier,monospace;">equals</span> </span>with <span style="font-family: "Courier New",Courier,monospace;">==</span> in the <span style="font-family: "Courier New",Courier,monospace;">character</span>
parser, pretend you didn't know that you made this silly mistake, and
try to fix it.) Unit testing becomes all the more important. Here are a few negative experiences I have made:</li>
<ul>
<li>Being restricted to line breakpoints is bad when you're interested only in a part of those nice one-liners. </li>
<li>In order to set breakpoints inside a lambda, you need blocks, again bad for elegance. </li>
<li>When you're inside the lambda, you may see synthetic members named <i>arg$1</i> etc. without being really able to tell what they are. It helps a bit when you at least show the declared type in the <i>Variables </i>view. </li>
<li>Stepping into a lambda is not really an option, because of all the synthetic stuff in between. </li>
</ul>
<li>Formatting lambdas is not always easy (I often do it manually, case by case, because I don't always like what Eclipse does automatically). </li>
<ul>
</ul>
</ul>
And do have a look at Hutton's book! Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-55952326903533813202015-12-05T00:12:00.001+01:002015-12-05T00:12:27.477+01:00CompletableFuture as a Trampoline for Tail Recursion EliminationA function is said to be <i>tail recursive</i> when the result of the recursive call is what we return from the function. In other words, the recursive call is the last thing we do, and in particular, when the recursive call returns, we do not need any of the local variables and parameters of the current stack frame.<br />
<br />
In many languages, the compiler will recognize this situation and re-use the current stack frame for the recursive call. This is called <i>tail recursion elimination</i> (or <i>tail call optimization</i>, in the more general case that the final function call is not recursive). But it doesn't happen in Java.<br />
<br />
There are standard techniques to implement tail call optimization when the language does not have it. One possibility is to transform the recursive function to a loop manually, which is easy to do, typically easier than transforming a non-tail-recursive function into a tail recursive one. Another such method is called <i>trampolining</i>. A trampoline is simply a loop that performs the function calls iteratively, one after the other. In order to achieve that, the recursive function is rewritten so that it is no longer actually recursive, but instead returns immediately with a higher-order function that will call the original function when evaluated inside the loop. These higher-order wrappers are usually called <i>thunks</i>. The term "trampoline" derives from the visual image of control bouncing up and down between the loop and the function, without ever spiralling downwards as in true recursion.<br />
<br />
Information on trampolining is not hard to find. For example, <a href="http://www.datchley.name/recursion-tail-calls-and-trampolines/" target="_blank">here </a>and <a href="http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html" target="_blank">here </a>are two nice posts, with illustrations. As for Java, Pierre-Yves Saumont presents a trampoline implementation in <a href="http://www.javacodegeeks.com/2015/10/stack-safe-recursion-in-java.html" target="_blank">this post</a> (without actually mentioning the term).<br />
<br />
I have noticed that Java actually contains a built-in class that implements trampolining, namely <i>CompletableFuture</i>. You get the desired behavior by making <i>asynchronous tail calls</i> (Viktor Klang's term). We won't need any custom classes or explicit loops. Let's use the Fibonacci function as an example. Here's a tail recursive formulation of it:<br />
<br />
<pre class="brush: java">public static BigInteger fibTailRecursive(int n) {
return n <= 2 ? ONE : fibTailRecursiveAux(n, ZERO, ONE);
}
private static BigInteger fibTailRecursiveAux(int n, BigInteger a, BigInteger b) {
return n <= 0 ? a : fibTailRecursiveAux(n - 1, b, a.add(b));
}
</pre>
<br />
To get the trampoline, we delay the recursive calls by wrapping them in CompletableFuture. The terminal value will be wrapped in an already completed future. Here's the corresponding thunked version of the above function definition:<br />
<br />
<pre class="brush: java">public static BigInteger fibCF(int n) {
return n <= 2 ? ONE : fibCF(n, ZERO, ONE).join();
}
private static CompletableFuture<BigInteger> fibCF(int n, BigInteger a, BigInteger b) {
return n <= 0 ? terminate(a) : tailcall(() -> fibCF(n - 1, b, a.add(b)));
}
</pre>
<br />
The complete "framework" consists only of the two utility methods <i>terminate </i>and <i>tailcall</i>. Plus we also should provide a dedicated thread to run the async calls in. (Adding more threads, or using the common Fork-Join pool actually slows things down in my environment.)<br />
<br />
<pre class="brush: java">public static <T> CompletableFuture<T> terminate(T t) {
return CompletableFuture.completedFuture(t);
}
public static <T> CompletableFuture<T> tailcall(Supplier<CompletableFuture<T>> s) {
return CompletableFuture.supplyAsync(s, POOL).thenCompose(identity());
}
private static final ExecutorService POOL = Executors.newSingleThreadExecutor(new ThreadFactoryBuilder().setDaemon(true).build());
</pre>
<br />
The class ThreadFactoryBuilder is from Guava. Composing with the identity function will unwrap the nested CompletableFuture that comes out of the call to <i>supplyAsync</i>.<br />
<br />
Note that it is essential to use <i>supplyAsync</i>. Making synchronous calls, or using an Executor that runs tasks immediately in the caller thread (for example, <span style="font-family: "courier new" , "courier" , monospace;">Executor e = Runnable::run</span>), would lead to a stackoverflow for large inputs.The trampoline loop is realised inside CompletableFuture by taking tasks from the queue associated with the Executor. This feature is not really documented. Although Doug Lea has pointed out to me that there is an implementation comment at the top of CompletableFuture that points in that direction<br />
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Normale Tabelle";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-fareast-language:EN-US;}
</style>
<blockquote class="tr_bq">
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* Method
postComplete is called upon completion unless the target</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* is
guaranteed not to be observable (i.e., not yet returned or</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* linked).
Multiple threads can call postComplete, which</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* atomically
pops each dependent action, and tries to trigger it</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* via method
tryFire, in NESTED mode.<span style="mso-spacerun: yes;"> </span>Triggering can
propagate</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>*
recursively, so NESTED mode returns its completed dependent (if</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* one exists)
for further processing by its caller (see method</div>
<div class="MsoPlainText">
<span style="mso-spacerun: yes;"> </span>* postFire).</div>
</blockquote>
<br />
The bad news is performance. I have benchmarked this solution against a manually optimized iterative version and against Saumont's <i>TailCall </i>class. The upshot is that TailCall performs as well as the manually coded loop. Using CompletableFuture is three times as slow. Here's a representative measurement for computing the 5000th Fibonacci number:<br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;"># Warmup: 5 iterations, 1 s each<br /># Measurement: 25 iterations, 1 s each<br /># Threads: 1 thread, will synchronize iterations<br /># Benchmark mode: Average time, time/op<br /><br />Benchmark Mode Cnt Score Error Units<br />TrampolineBenchmark.measureLoop avgt 25 0.403 ± 0.004 ms/op<br />TrampolineBenchmark.measureTC avgt 25 0.415 ± 0.002 ms/op<br />TrampolineBenchmark.measureCF avgt 25 1.258 ± 0.009 ms/op</span><br />
<br />
Nevertheless, I like the simplicity of it.Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-19795707145056732032015-11-13T18:39:00.000+01:002015-11-14T16:32:49.126+01:00Deterministic and Non-Deterministic Finite State Machines with CyclopsI have just recently become aware of the <a href="https://github.com/aol/cyclops" target="_blank">Cyclops </a>library for functional programming with Java 8. This exciting library offers many excellent features, among them<br />
<ul>
<li>Enhancements and utilities for Streams</li>
<li>Advanced monadic operations </li>
<li>Powerful pattern matching</li>
<li>Interoperability with both <a href="http://totallylazy.com/" target="_blank">TotallyLazy</a> and <a href="http://javaslang.com/" target="_blank">javaslang</a></li>
</ul>
and more. I have only looked at a part of it, and I'm sure there are many useful things to discover. Go look for yourself!<br />
<br />
<h3>
Abstracting over Monads</h3>
<br />
The feature that drew my attention initially, however, were Cyclops' tools for monadic programming. In particular, they can abstract over the three monads in JDK 8: Stream, Optional
and CompletableFuture (and any other monads you may find or create). By using what they call <i>Comprehenders</i>, indeed they can coerce even classes that are technically non-monadic (like List) into a monad. You can find pointers to articles about this on the Cyclops page, for example<a href="https://medium.com/@johnmcclean/introducing-the-cyclops-monad-api-a7a6b7967f4d" target="_blank"> this readable introduction</a>.<br />
<br />
Why did this interest me so much? Well, monads are particularly good at combining computations into a coherent whole, abstracting away some boilerplate code. The algorithm for combining the computations can always be the same (using a method that is usually called <i>flatMap </i>or <i>bind</i>), with the details of what happens being delegated to the particular monad. An instructive example is given by Mike MacHenry in <a href="https://www.quora.com/In-simple-terms-what-is-a-sequence-monad" target="_blank">this post</a>. MacHenry models a deterministic finite state machine (DFA) with a transition function that has type Optional, and a nondeterminstic fine state machine (NFA) with a transition function that has type List. He then shows how we can abstract over DFAs and NFAs by implementing a traversal function that works for both kinds of machines. The advantage is interface economy, and consequently more elegance and less maintenance. <br />
<br />
MacHenry's post is in the context of Haskell, and I have always wished to be able to do the same thing in Java. But in the
JDK, although Optional basically implements the same conceptual API as List (you might think of Optional as a sequence with a cardinality of at most 1, cf. <a href="http://blog.jooq.org/2015/08/20/divided-we-stand-optional/" target="_blank">here</a>), there is no actual interface to capture the common functionality. You might even be driven to model a DFA as an NFA and place the constraint that the lists must contain at most one state in the Javadoc. The point is that this would be a decidedly inferior DFA model.<br />
<br />
Finally, with Cyclops, we can do what we really want. Cyclops introduces a simple wrapper class, called <i>AnyM</i>, to
manage the abstraction.<br />
<br />
The technicalities of working with AnyM, however, can also be a bit involved, so we want to hide that from our application logic and provide a common implementation for DFAs and NFAs with an API that exposes only standard JDK classes. I'd like to show you how I did it. The solution requires Cyclops 6.1.1 or later.<br />
<br />
<h3>
Modelling Finite State Machines</h3>
<br />
A finite state machine is defined by it's inventory of states, an alphabet of permissible input symbols and a transition table that takes the current state, the next input symbol to be consumed and yields the next state (or states, in the case of an NFA). In Java, the transition function can be modelled by <br />
<br />
<pre class="brush:java">BiFunction<S, Character, M>
</pre>
<br />
where <i>S</i> denotes the type of the machine's states, and <i>M </i>the monadic container used as the result value of the transition function (Optional<S> or List<S> for a DFA or NFA, resp.)<br />
<br />
The states and alphabet will be left implicit in the transition table. In addition, for convenience we will allow the transition table to be
partial, in the sense that it need only contain the valid transitions.
The appropriate empty value that signifies an invalid transition is supplied separately when creating a state machine. Here's the factory method signature:<br />
<br />
<pre class="brush:java">public static <S, M> StateMachine<S,M> newStateMachine(BiFunction<S, Character, M> partialTransitions, M defaultValue)
</pre>
<br />
The machine itself is represented as a traversal function that takes a state and a sequence of input characters, and returns the resulting state(s) after consuming the entire input, in which case the input is said to have been accepted. (Well, really it is only accepted when you start from a properly identified <i>initial </i>state and end up in a <i>final </i>state, but I'm ignoring this detail here. You can easily build it on top of the implementation given below.)<br />
<br />
<pre class="brush:java">@FunctionalInterface
public interface StateMachine<S, M> {
M accept(S state, CharSequence input);
}
</pre>
<br />
The states themselves can be anything. We will assume a simple immutable class <i>State </i>hat has an integer identity attribute with <i>equals </i>and <i>hashCode </i>defined accordingly, and an associated factory method <i>state(int)</i>.<br />
<br />
<h3>
Working with Finite State Machines</h3>
<br />
In proper test-first fashion, let us first consider how we want to be able to use our state machines. Here are a couple of JUnit tests. I will use <a href="https://github.com/google/guava" target="_blank">Guava</a>'s two-dimensional array table to provide the transition function.<br />
<br />
<pre class="brush:java">import static java.util.Arrays.asList;
import static java.util.Collections.emptyList;
import static java.util.Optional.empty;
import static java.util.Optional.of;
@Test
public void demoDFA() {
ArrayTable<State, Character, Optional<State>> transitiontable = ArrayTable.create(
asList(state(1), state(2)), asList('a', 'b'));
transitiontable.put(state(1), 'a', of(state(2)));
transitiontable.put(state(1), 'b', of(state(1)));
transitiontable.put(state(2), 'b', of(state(1)));
StateMachine<State,Optional<State>> dfa = newStateMachine(transitiontable::get, empty());
Optional<State> finalState = dfa.accept(state(1), "ab");
assertEquals(state(1), finalState.get());
}
@Test
public void demoNFA() {
ArrayTable<State, Character, List<State>> transitiontable = ArrayTable.create(
asList(state(1), state(2), state(3)), asList('a', 'b'));
transitiontable.put(state(1), 'a', asList(state(2), state(3)));
transitiontable.put(state(2), 'a', asList(state(2)));
transitiontable.put(state(3), 'b', asList(state(3)));
StateMachine<State, List<State>> nfa = newStateMachine(transitiontable::get, emptyList());
List<State> finalStates = nfa.accept(state(1), "ab");
assertEquals(asList(state(3)), finalStates);
}
</pre>
<br />
I have not shown any test with inacceptable input. In that case, because the transition function will return either an empty Optional or empty List when it encounters a state out of which there is no path, the result will also be empty. And of course, in case the input is empty, we shall expect the result to be just the initial state (wrapped in its appropriate monad).<br />
<br />
<h3>
Implementing the Finite State Machine</h3>
<br />
Without further ado, here's the implementation. It's quite concise. Explanatory comments will follow.<br />
<br />
<pre class="brush:java">public static <S, M> StateMachine<S,M> newStateMachine(BiFunction<S, Character, M> partialTransitions, M defaultValue) {
Objects.requireNonNull(partialTransitions);
Objects.requireNonNull(defaultValue);
BiFunction<S, Character, AnyM<S>> totalTransitions = (s, c) ->
AnyM.ofMonad(Optional.ofNullable(partialTransitions.apply(s, c)).orElse(defaultValue));
Function<S, AnyM<S>> unit = s -> AnyM.ofMonad(defaultValue).unit(s);
return (state,input) -> machine(totalTransitions, unit).accept(state, input).unwrap();
}
private static <S> StateMachine<S, AnyM<S>> machine(BiFunction<S, Character, AnyM<S>> transitions, Function<S, AnyM<S>> unit) {
return (state,input) -> {
if (input.length() == 0) return unit.apply(state);
return transitions.apply(state, input.charAt(0))
.flatMap(next -> machine(transitions,unit).accept(next, input.subSequence(1, input.length())));
};
}
</pre>
<br />
First thing in the factory method <i>newStateMachine </i>we extend the given function to a total function, and make it put the function value into Cyclops' AnyM wrapper. (Making the function total will obviate dealing with any null value later.) <i>AnyM.ofMonad</i> takes an Object that is already of a supported type and makes it accessible through the wrapper's monadic interface. <br />
<br />
Then we define a function that creates a new instance of the underlying monad when given a state. We need that function to terminate the recursive traversal. Cyclops provides a <i>unit </i>method that we can use. We can supply the given default value to provide the required monad type.<br />
<br />
Finally, we return the traversal function. Cyclops' <i>unwrap </i>method will remove the AnyM wrapper around the resulting monad.<br />
<br />
The traversal function is recursive, terminating with the current state when the input is exhausted. It uses the transition function to look up any new state (or states) reachable from the current state while consuming the next input character, and for each new state that it finds calls that state <i>next</i> and continues to traverse the graph with <i>next</i> as the current state and consuming the rest of the input.<br />
<br />
<h3>
Cyclops API</h3>
<br />
Cyclops before release 6.1.1 used to contain a host of conversion functions. It was really difficult to know when to use what method. I am indebted to John McClean, the author of Cyclops, for some friendly help with the correct usage of the Cyclops APIs, having made many wrong choices myself. This has not been an easy library to learn!<br />
<br />
Fortunately, with Cyclops 6.1.1 many of these methods have been deprecated (see the <a href="https://github.com/aol/cyclops/releases/tag/v6.1.1" target="_blank">release note</a>s), which has improved the situation a lot. Just use the factory methods on class <i>AnyM</i>. Javadoc coverage has also been extended. <br />
<br />
Some conversion methods ensure that the wrapped type inside
AnyM remains unchanged, some convert to <i>Stream</i> implicitly. The latter approach (although it can be more efficient) may impose some additional burden on the application coding. In our case that burden would be allowing for a different monadic type to be returned from <i>newStateMachine </i>than was put in, and explicitly collecting to a list in the caller. The choice is yours.<br />
<br />
<h3>
Conclusion</h3>
<br />
With DFAs, flatMap over Optional abstracts away the tedium of looking at the intermediate result and checking whether it's empty and continuing only with a non-empty value. With NFAs, flatMap over List abstracts away the tedium of applying a map and concatenating the results. With Cyclops, we can do both in a uniform manner.<br />
<br />
I hope you have found this example as instructive as I did.<br />
<br />
<br />Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com1tag:blogger.com,1999:blog-6979485574739813012.post-77039579023853375142015-09-10T13:29:00.000+02:002015-09-30T23:16:10.546+02:00Cartesian Products with Kleisli Composition<br />
Over at the <a href="http://blog.jooq.org/" target="_blank">JOOQ blog</a>, they have written about <a href="http://blog.jooq.org/2015/09/09/how-to-use-java-8-functional-programming-to-generate-an-alphabetic-sequence/" target="_blank">How to use Java 8 Functional Programming to Generate an Alphabetic Sequence</a>. By "alphabetic sequence" they mean the (n-order) Cartesian product of the letters in the alphabet. For example, the third-order Cartesian product of the alphabet would be<br />
<blockquote class="tr_bq">
AAA, AAB, AAC, ..., ZZZ</blockquote>
The author of that post (it is unsigned, but I believe it was written by Lukas Eder) claims that <br />
<blockquote class="tr_bq">
the Java 8 Stream API does not offer enough functionality for this task.</blockquote>
I will show that this claim is wrong, and that there is in fact a pure Java 8 solution. This solution brings out the structure of the problem rather nicely. It is general in the sense that it uses a general function combinator well-known in functional programming. It relies only on the Java 8 Streams API without needing any constructs from <a href="https://github.com/jOOQ/jOOL" target="_blank">jOOλ</a>.<br />
<br />
The first building block of the solution is provided by <a href="http://stackoverflow.com/users/3920048/misha" target="_blank">Misha </a>in his <a href="http://stackoverflow.com/a/31374887/4847731" target="_blank">answer</a> to this <a href="http://stackoverflow.com/questions/31374411/implement-cartesian-product-of-collections-by-java-8" target="_blank">Stackoverflow question</a>. Here's Misha's function that will create a stream of combinations of its first argument with the given stream, where the mode of combination can be externally specified as well. (In the following I will not only call this method <span style="font-family: "Courier New",Courier,monospace;">crossJoin</span>, but also the function that it returns.)<br />
<pre class="brush: java"><T, U, R> Function<T, Stream<R>> crossJoin(Supplier<Stream<? extends U>> streamSupplier, BiFunction<? super T, ? super U, ? extends R> combiner) {
return t -> streamSupplier.get().map(u -> combiner.apply(t, u));
}
</pre>
<br />
Now you can do the nth-order Cartesian product by applying <span style="font-family: "Courier New",Courier,monospace;">flatMap </span>with <span style="font-family: "Courier New",Courier,monospace;">crossJoin</span> a fixed number of times. A question that goes unanswered in that Stackoverflow discussion is at the core of the JOOQ post: How deal with the situation when the required number of applications is not fixed, but supplied at runtime as a parameter? That is, how do we implement<br />
<br />
<pre class="brush: java">List<String> cartesian(int n, Collection<String> coll)
</pre>
Of course, you might do it recursively. But that would rather count as supporting the claim that Java streams were not sufficient! Fortunately, the implementation becomes easy once we remember that the repeated application of functions is equivalent to a single application of the composition of these functions. In our case, we actually want sequential composition, which is just the flip of regular composition<span style="font-family: "Courier New",Courier,monospace;"></span>. Looking at the signature<br />
<br />
<pre class="brush: java">crossJoin :: a -> Stream b
</pre>
it may be hard to see at first how we might compose functions of this signature sequentially. Actually, however, there is guaranteed to be such a combinator. It is called "Kleisli composition", written "<span style="font-family: "Courier New",Courier,monospace;">>=></span>", and has the following signature:<br />
<br />
<pre class="brush: java">>=> :: (a -> Stream b) -> (b -> Stream c) -> (a -> Stream c)
</pre>
<br />
In fact, >=> has a completely general definition for all so-called "monadic types", of which <span style="font-family: "Courier New",Courier,monospace;">Stream </span>in Java is one. What this means is that we could even abstract over <span style="font-family: "Courier New",Courier,monospace;">Stream </span>in the above signature, and implement sequential composition for all those types in the same way. This is easier in some languages (Haskell, Scala) than in others (Java). <a href="http://www.javacodegeeks.com/2015/09/refactoring-with-kleisli-composition.html" target="_blank">This article</a> by Yoav Abrahami gives an instructive example of what you can do with Kleisli composition in Scala. It demonstrates the same trick we are about to perform, namely replacing recursion with a form of functional composition.<br />
<br />
For the sake of example, instead of generalizing we will simplify somewhat. In our case we are dealing only with streams of strings. Here's the Java implementation of <span style="font-family: "Courier New",Courier,monospace;">>=></span> for this special case:<br />
<pre class="brush: java">BinaryOperator<Function<String,Stream<String>>> kleisli = (f,g) -> s -> f.apply(s).flatMap(g);
</pre>
The Stream type, being "monadic", obeys certain axioms, one of which states that <span style="font-family: "Courier New",Courier,monospace;">>=></span> is associative. So we may use it in a reduction. The required identity function is<span style="font-family: "Courier New",Courier,monospace;"> s -> Stream.of(s)</span>. You can easily convince yourself of that by considering the first-order product, which is of course just the original list, which we'll get by lifting every element to <span style="font-family: "Courier New",Courier,monospace;">Stream </span>and flat-mapping back down, without invoking <span style="font-family: "Courier New",Courier,monospace;">crossJoin </span>at all. (Of course, you can also prove it by plugging the identity into the definition of <span style="font-family: "Courier New",Courier,monospace;">>=></span>.)<br />
<br />
Let's put it all together: The idea is to create a stream of as many <span style="font-family: "Courier New",Courier,monospace;">crossJoin </span>functions as we need, reduce this stream to a single function in memory by composing them together, and finally apply the entire function chain in one fell swoop.<br />
<br />
<pre class="brush: java">List<String> cartesian(int n, Collection<String> coll) {
return coll.stream()
.flatMap( IntStream.range(1, n).boxed()
.map(_any -> crossJoin(coll::stream, String::concat)) // create (n-1) appropriate crossJoin instances
.reduce(s -> Stream.of(s), kleisli) // compose them sequentially with >=>
) // flatMap the stream with the entire function chain
.collect(toList());
}
</pre>
The following call will give you a list of all three-letter alphabetic sequences:<br />
<pre class="brush: java">cartesian(3, alphabet)
</pre>
A variation on the above is when you do not want to multiply a collection n times with itself, but with n other collections (all of the same type). Instead of passing in <span style="font-family: "Courier New",Courier,monospace;">n</span>, you might pass in the sequence of those other collections, and instead of streaming an integer range you might stream that sequence, creating a <span style="font-family: "Courier New",Courier,monospace;">crossJoin </span>function for each element, like this: <span style="font-family: "Courier New",Courier,monospace;">Stream.of(colls).map(c -> crossJoin(c::stream, String::concat)) </span><br />
<br />
For good measure, here's how you may construct the list of letters <span style="font-family: "Courier New",Courier,monospace;">alphabet</span>, if you do not wish to write them down severally with <span style="font-family: "Courier New",Courier,monospace;">Arrays.asList</span>:<br />
<pre class="brush: java">List<String> alphabet = IntStream.rangeClosed('A','Z')
.mapToObj(c -> String.valueOf((char) c))
.collect(toList());
</pre>
<br />
[Addendum]:<br />
<ol>
<li>It's important that we pass a <span style="font-family: "Courier New",Courier,monospace;">Supplier<Stream></span> to <span style="font-family: "Courier New",Courier,monospace;">crossJoin</span>, not the stream itself. </li>
<li>You might also be interested in <a href="http://stackoverflow.com/questions/32631602/cartesian-product-of-streams-in-java-8-as-stream-using-streams-only/32644753#32644753" target="_blank">Tagir Valeev's answer</a> to a related question on Stackoverflow.</li>
</ol>
Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com1tag:blogger.com,1999:blog-6979485574739813012.post-52910882189744549512015-06-03T11:23:00.001+02:002016-02-09T01:11:26.720+01:00Recursive Parallel Search with Shallow BacktrackingThe implementation in th<span style="background-color: white;">e <span style="color: blue;"><b><a href="http://sebastian-millies.blogspot.de/2015/05/recursive-parallel-search.html" target="_blank">previous post</a></b></span></span><b> </b>had a serious disadvantage: We generated substitutions for all the letters, and then checked if those
substitutions constituted a solution. However, in a more efficient approach some partial substitutions could be rejected out-of-hand as not leading to a solution. This is called "shallow backtracking". In this post I show how to examine the letters as they occur from right to left in the
operands, and interleave the checking of arithmetic constraints with the
generation of substitutions.<br />
<br />
This solution combines the advantages of flatMap-based search in Java 8, parallelization, persistent collections, and recursion. This code that I will show is completely general for cryptarithmetic puzzles with two summands, because the constraints are no longer problem-specific: in fact they encode only the rules of long addition plus a general side condition.<br />
<br />
The implementation is also a bit more idiomatic (for Java), with less clutter in the method interfaces, because we keep the read-only operands in instance variables instead of passing them around explicitly.<br />
<br />
The really nice thing is that this approach is about 25 times faster than the original parallel flatMap solution with exhaustive search.<br />
<br />
Here's the code:<br />
<pre class="brush: java">import static com.googlecode.totallylazy.collections.PersistentList.constructors.list;
import static com.googlecode.totallylazy.collections.PersistentMap.constructors.map;
import static java.util.stream.Collectors.toList;
import java.util.Collection;
import java.util.Map;
import java.util.stream.Stream;
import com.googlecode.totallylazy.collections.PersistentList;
import com.googlecode.totallylazy.collections.PersistentMap;
public class SendMoreMoneyShallow {
static final int PRUNED = -1;
static final char PADDING = ' ';
static final PersistentList<Integer> DIGITS = list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
// padded puzzle arguments: op1 + op2 = op3
final String op1;
final String op2;
final String op3;
public static void main(String[] args) {
SendMoreMoneyShallow puzzle = new SendMoreMoneyShallow(" send", " more", "money");
Collection<String> solutions = puzzle.solve();
System.out.println("There are " + solutions.size() + " solutions: " + solutions);
}
public SendMoreMoneyShallow(String op1, String op2, String op3) {
// the arguments come padded with blanks so they all have the same length
// there is no need to reverse the strings, because we have random access and can process them backwards
assert op1.length() == op3.length();
assert op2.length() == op3.length();
this.op1 = op1;
this.op2 = op2;
this.op3 = op3;
}
public Collection<String> solve() {
PersistentMap<Character, Integer> subst = map();
Collection<String> solutions = go(op1.length() - 1, subst, 0).collect(toList());
return solutions;
}
Stream<String> go(int i, PersistentMap<Character, Integer> subst, int carry) {
// Each level of recursion accomplishes up to three substitutions of a character with a number. The recursion
// should end when we run out of characters to substitute. At this point, all constraints have already been
// checked and therefore the substitutions must represent a solution.
if (i < 0) {
return solution(subst);
}
// the state consists of partial substitutions and the carry. Every time we have made a substitution for a column
// of letters (from right to left), we immediately check constraints.
Character sx = op1.charAt(i);
Character sy = op2.charAt(i);
Character sz = op3.charAt(i);
return candidates(sx, subst).stream().parallel().flatMap(x -> {
PersistentMap<Character, Integer> substX = subst.insert(sx,x);
return candidates(sy, substX).stream().flatMap(y -> {
PersistentMap<Character, Integer> substXY = substX.insert(sy,y);
return candidates(sz, substXY).stream().flatMap(z -> {
PersistentMap<Character, Integer> substXYZ = substXY.insert(sz, z);
// recurse if not pruned, using the tails of the strings, the substitutions we have just made, and
// the value for carry that results from checking the arithmetic constraints
int nextCarry = prune(substXYZ, carry, x, y, z);
return nextCarry == PRUNED ? Stream.empty() : go(i - 1, substXYZ, nextCarry);
});});});
}
int prune(PersistentMap<Character, Integer> subst, int carry, Integer x, Integer y, Integer z) {
// neither of the most significant digits may be 0, and we cannot be sure the substitutions have already been made
if (subst.getOrDefault(mostSignificantLetter(op1), 1) == 0 || subst.getOrDefault(mostSignificantLetter(op2), 1) == 0) {
return PRUNED;
}
// the column sum must be correct
int zPrime = x + y + carry;
if (zPrime % 10 != z) {
return PRUNED;
}
// return next carry
return zPrime / 10;
}
PersistentList<Integer> candidates(Character letter, PersistentMap<Character, Integer> subst) {
if (letter == PADDING) {
return list(0);
}
// if we have a substitution, use that, otherwise consider only those digits that have not yet been assigned
return subst.containsKey(letter) ? list(subst.get(letter)) : DIGITS.deleteAll(subst.values());
}
Stream<String> solution(PersistentMap<Character, Integer> subst) {
// transform the set of substitutions to a solution (in this case a String because Java has no tuples)
int a = toNumber(subst, op1.trim());
int b = toNumber(subst, op2.trim());
int c = toNumber(subst, op3.trim());
return Stream.of("(" + a + "," + b + "," + c + ")");
}
static final int toNumber(Map<Character, Integer> subst, String word) {
// return the integer corresponding to the given word according to the substitutions
assert word.length() > 0;
return word.chars().map(x -> subst.get((char)x)).reduce((x, y) -> 10 * x + y).getAsInt();
}
static char mostSignificantLetter(String op) {
return op.trim().charAt(0);
}
}
</pre>
<br />
And here's a representative performance measurement:<br />
<br />
# JMH 1.9.1 (released 40 days ago)<br />
# VM invoker: C:\Program Files\Java\jdk1.8.0_25\jre\bin\java.exe<br />
# VM options: -Dfile.encoding=UTF-8<br />
# Warmup: 5 iterations, 1 s each<br />
# Measurement: 25 iterations, 1 s each<br />
# Timeout: 10 min per iteration<br />
# Threads: 1 thread, will synchronize iterations<br />
# Benchmark mode: Average time, time/op<br />
# Benchmark: java8.streams.SendMoreMoneyShallowBenchmark.measureShallowBacktrackingPerformance<br />
<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;">Benchmark Mode Cnt Score Error Units<br />measureShallowBacktrackingPerformance avgt 25 6.319 ± 0.082 ms/op</span><br />
<br />
There is room for still more improvement, because the substitution for "z" in each round is in fact determined by the previous substitutions and need not be guessed.Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com3tag:blogger.com,1999:blog-6979485574739813012.post-57084233951043769712015-05-27T22:26:00.004+02:002015-05-27T22:26:38.164+02:00Recursive Parallel SearchBartosz Milewski has been discussing monadic programming in C++. In <b><span style="color: blue;"><a href="http://bartoszmilewski.com/2015/05/25/using-monads-in-c-to-solve-constraints-4-refactoring/" target="_blank">this post</a></span></b> he presents a recursive version of the flatMap-based solution of the "Send more money" cryptarithmetic puzzle.<br />
<br />
(BTW: Bartosz' writings always make for excellent reading if you're at all interested in functional programming.)<br />
<br />
Here's a Java version of the recursive approach. I have already discussed the non-recursive solution in a <span style="background-color: white;"><b><a href="http://sebastian-millies.blogspot.de/2015/04/easy-exhaustive-search-with-flatmap.html" target="_blank">previous blog entry</a></b></span>. The main advantage over the original solution is that the recursive approach is less redundant and much easier to generalize. The main drawback is that on my machine it is about 6 times slower.<br />
<br />
Please note how easy it is to parallelize this recursive solution when using persistent collections, in this case the ones from the<span style="background-color: white;"> </span><a href="http://totallylazy.com/" target="_blank"><span style="background-color: white;"><b>TotallyLazy</b></span> </a>framework. Please spend a minute thinking about how you would go about coding this solution using only classes from the JDK. It's not trivial. (I would guess the same is true of the C++ implementation).<br />
<br />
So here goes:<br />
<br />
<pre class="brush: java">import static com.googlecode.totallylazy.collections.PersistentList.constructors.list;
import static com.googlecode.totallylazy.collections.PersistentMap.constructors.map;
import static java.util.stream.Collectors.toList;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.stream.Stream;
import com.googlecode.totallylazy.collections.PersistentList;
import com.googlecode.totallylazy.collections.PersistentMap;
public class SendMoreMoneyRecursive {
static final PersistentList<Character> LETTERS = list(uniqueChars("sendmoremoney"));
static final PersistentList<Integer> DIGITS = list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
public static void main(String[] args) {
SendMoreMoneyRecursive puzzle = new SendMoreMoneyRecursive();
Collection<String> solutions = puzzle.solve(LETTERS, DIGITS);
System.out.println("There are " + solutions.size() + " solutions: " + solutions);
}
Collection<String> solve(PersistentList<Character> str, PersistentList<Integer> digits) {
PersistentMap<Character, Integer> subst = map();
Collection<String> solutions = go(str, digits, subst).collect(toList());
return solutions;
}
Stream<String> go(PersistentList<Character> str, PersistentList<Integer> digits,
PersistentMap<Character, Integer> subst) {
// Each level of nesting accomplishes one substitution of a character by a number.
// The recursion ends when we run out of characters to substitute.
if (str.isEmpty()) {
return prune(subst);
}
return digits.stream().parallel().flatMap(n -> go(str.tail(), digits.delete(n), subst.insert(str.head(), n)));
}
Stream<String> prune(PersistentMap<Character, Integer> subst) {
// we know that we never look up a value that’s not in the map
if (subst.get('s') == 0 || subst.get('m') == 0) {
return Stream.empty();
}
int send = toNumber(subst, "send");
int more = toNumber(subst, "more");
int money = toNumber(subst, "money");
return send + more == money ? Stream.of(solution(send, more, money)) : Stream.empty();
}
String solution(int send, int more, int money) {
return "(" + send + "," + more + "," + money + ")";
}
static final int toNumber(Map<Character, Integer> subst, String word) {
assert word.length() > 0;
return word.chars().map(x -> subst.get((char)x)).reduce((x, y) -> 10 * x + y).getAsInt();
}
static List<Character> uniqueChars(String s) {
return s.chars().distinct().mapToObj(d -> Character.valueOf((char) d)).collect(toList());
}
}
</pre>
Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-39378704199610101992015-05-01T13:42:00.001+02:002015-05-01T13:43:55.690+02:00Stream#flatMap() may cause short-circuiting of downstream operations to breakThere is a <a href="http://bugs.java.com/bugdatabase/view_bug.do?bug_id=8075939" target="_blank">bug report</a> showing how flatMapping to an infinite stream may lead to non-termination of stream processing even in the presence of a short-circuiting terminal operation.<br />
<br />
On StackOverflow, there is a <a href="http://stackoverflow.com/questions/29229373/why-filter-after-flatmap-is-not-completely-lazy-in-java-streams/29986041#29986041" target="_blank">discussion </a>(in fact it was this discussion that led to the entry in the bug database) in which participants agree that the behavior is confusing and perhaps unexpected, but do not agree on whether it is actually a bug. There seem to be different ways to read the spec.<br />
<br />
Here's an example:<br />
<pre class="brush: java">Stream.iterate(0, i->i+1).findFirst()
</pre>
works as expected, while<br />
<pre class="brush: java">Stream.of("").flatMap(x->Stream.iterate(0, i->i+1)).findFirst()
</pre>
will end up in an infinite loop.<br />
<br />
The behavior of flatMap becomes still more surprising when one throws in an <b>intermediate</b> (as opposed to terminal) short-circuiting operation. While the following works as expected, printing out the infinite sequence of integers<br />
<pre class="brush: java">Stream.of("").flatMap(x -> Stream.iterate(1, i -> i + 1)).forEach(System.out::println);
</pre>
the following code prints out only the "1", but still does <b>not</b> terminate:<br />
<pre class="brush: java">Stream.of("").flatMap(x -> Stream.iterate(1, i -> i + 1)).limit(1).forEach(System.out::println);
</pre>
<br />
I cannot imagine a reading of the spec in which this were not a bug.Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com1tag:blogger.com,1999:blog-6979485574739813012.post-55768743361345415832015-04-27T23:11:00.001+02:002015-04-29T18:16:44.363+02:00Yield Return in Java (comment on Benji Webber)Benji Webber has<span style="color: blue;"><span style="background-color: white;"> <a href="http://benjiweber.co.uk/blog/2015/03/21/yield-return-in-java/"><span style="color: blue;"><b>said</b></span> </a>t</span></span>hat a feature often missed in Java by C# developers is <a href="https://msdn.microsoft.com/en-us/library/9k7k7cf0.aspx">yield return</a>, and considers very complex ways of bringing this into Java for the implementation of iterators and generators. In particular he discusses a threading approach in some detail, which makes it seem really hard to generate and print out the integers from one to five.<br />
<br />
In fact, with Java 8, there is no need for any of that, because the required behavior is already built into the lazy execution model of streams. Iterators and generators are part and parcel of the Stream API.<br />
<br />
The following code, for example, will print the infinite series of positive numbers:<br />
<br />
<pre class="brush: java">Stream.iterate(1, x->x+1).forEach(System.out::println);
</pre>
Throwing in a <span style="font-family: "Courier New",Courier,monospace;">limit(5)</span> will give you the one-to-five example.<br />
<br />
The reason that this works is that each stream element is only generated (lazily) when a downstream method explicitly asks for it. Contrary to appearances, no list of five elements is ever constructed in the snippet<br />
<br />
<pre class="brush: java">Stream.iterate(1, x->x+1).limit(5).forEach(System.out::println);</pre>
<br />
To my eyes, the Java 8 code is even nicer to read than the corresponding code in C#.Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-42104742667361586862015-04-27T20:15:00.000+02:002015-04-29T22:34:24.008+02:00Easy exhaustive search with Java 8 StreamsI have just been reading <a href="http://blog.plover.com/prog/haskell/monad-search.html"><b>this post</b> </a>by Mark Dominus on Haskell. It discusses how the Haskell list monad can be used to hide some of the glue code involved in doing exhaustive searches. Java 8 Streams, which are somewhat similar to Haskell lists in also being monadic, lend themselves to the same style of coding.<br />
<br />
The example used in the post I have quoted is the well-known crypt-arithmetics puzzle in which you are asked to find all possible ways of mapping the letters <code>S</code>, <code>E</code>, <code>N</code>, <code>D</code>, <code>M</code>,
<code>O</code>, <code>R</code>, <code>Y</code> to <i>distinct</i> digits 0 through 9 (where we may assume that <code>S</code> is not 0) so that the following comes out true:<br />
<br />
<pre> S E N D
+ M O R E
---------
M O N E Y
</pre>
<br />
Here's my Java 8 port of Mark's Haskell example. <br />
<br />
<pre class="brush: java">public class SendMoreMoney {
static final List<Integer> DIGITS = unmodifiableList(asList(0,1,2,3,4,5,6,7,8,9));
public static void main(String[] args) {
List<String> solutions =
remove(DIGITS, 0).stream().flatMap( s ->
remove(DIGITS, s).stream().flatMap( e ->
remove(DIGITS, s, e).stream().flatMap( n ->
remove(DIGITS, s, e, n).stream().flatMap( d ->
remove(DIGITS, s, e, n, d).stream().flatMap( m ->
remove(DIGITS, s, e, n, d, m).stream().flatMap( o ->
remove(DIGITS, s, e, n, d, m, o).stream().flatMap( r ->
remove(DIGITS, s, e, n, d, m, o, r).stream().flatMap( y ->
{ int send = toNumber(s, e, n, d);
int more = toNumber(m, o, r, e);
int money = toNumber(m, o, n, e, y);
return send + more == money ? Stream.of(solution(send, more, money)) : Stream.empty();
}
))))))))
.collect(toList());
System.out.println(solutions);
}
static String solution(int send, int more, int money) {
return "(" + send + "," + more + "," + money + ")";
}
static final int toNumber(Integer... digits) {
assert digits.length > 0;
return Stream.of(digits).reduce((x,y) -> 10*x + y).get();
}
static final List<Integer> remove(List<Integer> xs, Integer... ys) {
// this naive implementation is O(n^2).
List<Integer> zs = new ArrayList<>(xs);
zs.removeAll(asList(ys));
return zs;
}
}
</pre>
The minor optimization of not unncecessarily recomputing "send" and
"more" is left out for the sake of readability. The methods <span style="font-family: "Courier New",Courier,monospace;">remove() </span>-
which implements list difference -<span style="font-family: "Courier New",Courier,monospace;"> toNumber()</span>, and <span style="font-family: "Courier New",Courier,monospace;">solution()</span> have
simple implementations. Of these, <span style="font-family: "Courier New",Courier,monospace;">toNumber()</span> is again a lot like the
corresponding Haskell code. Method <span style="font-family: "Courier New",Courier,monospace;">solution()</span> here returns a String because Java does not have tuples.<br />
<br />
Too bad that in Java one must have the nested method calls, but the
formatting goes some way to hide this. All in all, I think this is quite
nice.<br />
<br />
But how fast is it? I did a simple micro-benchmark with JMH 1.9.1 (available from Maven
Central) on my laptop computer, which is a quad-core machine with an
Intel i7 processor.
<br />
<br />
Here are the measurement parameters:
<br />
<br />
# JMH 1.9.1 (released 5 days ago)
<br />
# VM invoker: C:\Program Files\Java\jdk1.8.0_25\jre\bin\java.exe
<br />
# VM options: -Dfile.encoding=UTF-8
<br />
# Warmup: 5 iterations, 1 s each
<br />
# Measurement: 25 iterations, 1 s each
<br />
# Timeout: 10 min per iteration
<br />
# Threads: 1 thread, will synchronize iterations
<br />
# Benchmark mode: Average time, time/op
<br />
<br />
I measured the flatMap solution against the equivalent formulation with
eight nested forEach-loops and an external accumulator variable. The flatMap solution is about half as fast.
Here's a representative measurement:
<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;">Benchmark Mode Cnt Score Error Units
<br />measureFlatMapSearchPerformance avgt 25 662.377 ± 3.747 ms/op
<br />measureForLoopSearchPerformance avgt 25 316.105 ± 3.823 ms/op
</span><br />
<br />
The nice thing abbout Streams is they are so easily parallelizable.
Just throw in a <span style="font-family: "Courier New",Courier,monospace;">.parallel()</span> in the first line like this:<br />
<br />
<pre class="brush: java"> remove(DIGITS, 0).stream().parallel().flatMap( s ->
</pre>
<br />
leaving everything else unchanged, and the (parallel) flatMap version
becomes twice as fast as the (serial) for-loop version:
<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;">Benchmark Mode Cnt Score Error Units
<br />measureFlatMapSearchPerformance avgt 25 168.278 ± 1.700 ms/op
<br />measureForLoopSearchPerformance avgt 25 315.806 ± 2.878 ms/op
</span>Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-70013540510009771962013-09-16T12:16:00.001+02:002014-01-13T14:58:38.716+01:00The Y CombinatorThe Y combinator is one of the most beautiful ideas in programming theory. It allows one to define recursive functions from non-recursive, anonymous functions. The "anonymous" is what makes this particularly amazing: We are going to have recursion without having a way for a function to refer to itself by name. The usual example is the factorial function.<br />
<br />
The theoretical background is beautifully and thoroughly explained by Mike Vanier in his article <a href="http://mvanier.livejournal.com/2897.html?nojs=1">The Y Combinator (Slight Return)</a>, which I am not going to repeat here. (For a very short, readable intro to the topic, you might also refer to Deron Meranda's <a href="http://deron.meranda.us/ruminations/fixpoints/">blog post on fixpoints</a>.)<br />
<br />
Many people seem to enjoy implementing the Y combinator, even in Java. Most implementations seem in some way to go back to <a href="http://www.righto.com/2009/03/y-combinator-in-arc-and-java.html">this one</a> by Ken Shirriff, which is in Java 7 and almost unreadable due to the use of inner classes. And <a href="https://gist.github.com/aruld/3965968/#comment-604392">here </a>is a Java 8 implementation by Arul Dhesiaseelan. Note that the code on that last-mentioned post uses a method name <i><b>Y</b></i>, and that the comments on it propose a simplification which uses the <b><i>this </i></b>reference. Both are strictly not allowed, one might say that this is cheating. So here is my own, very similar but non-cheating implementation:<br />
<br />
<pre class="brush: java">
import java.util.function.Function;
public class YCombinator {
// First a few abbreviations
/** Function on T returning T. */
interface Func<T> extends Function<T,T> {
}
/**
* Higher-order function returning a T function.
* <br>F: F -> (T -> T)
* <br>This is the type of the Y combinator subexpressions.
*/
interface FuncToTFunc<T> extends Function<FuncToTFunc<T>, Func<T>> {
}
/**
* Function from a function on T functions to a T function.
* <br>((T -> T) -> (T -> T)) -> (T -> T)
* <br>This is the type of the fixed point operator.
*/
interface Fix<T> extends Function<Func<Func<T>>, Func<T>> {
}
// And now the real thing
/**
* Computes the factorial with the applicative-order Y combinator.
* <br>Y = λr.(λf.(f f)) λf.(r λx.((f f) x))
*/
public static int factorial(int n) {
return // Y combinator
((Fix<Integer>) r ->
((FuncToTFunc<Integer>) (f -> f.apply(f)))
.apply(f -> r.apply(x -> f.apply(f).apply(x)))
)
.apply(
// Recursive function generator
f -> x -> (x == 0) ? 1 : x * f.apply(x - 1)
)
.apply(
// Argument
n);
}
}
</pre>
<br />
This code really computes the factorial function. And it does this using only anonymous functions: no function names or variables anywhere except lamba parameters. (You can plug-in any other recursive function you might want to compute, e. g. Fibonacci, or Ackermann, etc.).<br />
<br />
The regrettable thing is having to have those casts. It would be nice to be able to get rid of them.<br />
<br />
-- SebastianSebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0tag:blogger.com,1999:blog-6979485574739813012.post-24840168166123845752013-06-14T11:45:00.000+02:002013-09-16T12:16:22.786+02:00Higher-Order Functions in Java 8 (Part 2) - LazinessIn this post I'd like to show that the typical elegance that results from the combination of lazy evaluation and higher-order functions in functional programming languages can sometimes also be had in Java. As our example, let's look at generating the first n primes,
for some arbitrary n. We'll use the method of trial division, which determines the primality of a number k by testing whether it is divisible by any prime smaller than k.We will see how to use Java lambda expressions to generate an
infinite sequence of integers and filter out the non-primes from it.<br />
<br />
Of course, we will not <i>really </i>generate an infinite sequence, but rather an unbounded one, and limit ourselves to taking out n elements. This is where <i>lazy evaluation </i>comes in. Being lazy means computing a value only when it is actually needed. (The opposite - immediate evaluation - is called being <i>strict</i>. The article <a href="http://www.defmacro.org/ramblings/fp.html">Functional Programming For the Rest of Us</a>, which offers an elementary and informal introduction to functional programming concepts from a Java perspective, contains, among other things, a discussion of laziness and its advantages as well as disadvantages.)<br />
<br />
Some functional languages like Haskell are inherently lazy, others like
Scala have both kinds of evaluation. Java 8 also falls into this latter
category: Traditionally, Java is a strict language: all method parameters are evaluated before a method is called etc. However, the new Streams API is inherently lazy: An object is only
created from the stream when there is demand for it, i. e. only when
some terminal operation like <span style="font-family: "Courier New",Courier,monospace;">collect </span>or <span style="font-family: "Courier New",Courier,monospace;">forEach </span>is called. And lambda expressions allow passing functions as arguments for delayed evaluation.<br />
<br />
Let's return to our example. In Scala, we might write the following code, lifted from <a href="http://louisbotterill.blogspot.de/2009/07/scala-lazy-evaluation-and-sieve-of.html">Louis Botterill's blog</a>:<br />
<br />
<pre class="brush: scala">def primes : Stream[Int] = {
var is = Stream from 2
def sieve(numbers: Stream[Int]): Stream[Int] = {
Stream.cons(
numbers.head,
sieve(for (x <- numbers.tail if x % numbers.head > 0) yield x))
}
sieve(is)
}
</pre>
<br />
By the way, this algorithm is <i>not </i>the Sieve of Eratosthenes, although it is often so presented. <a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">This paper</a> by Melissa O'Neill has all the details. It's an interesting read: O'Neill describes an optimized implementation of the genuine sieve, making use of heap-like data structures in Haskell. I'd be interested to know if someone has ported this to Java 8. We'll stick with the <i>unfaithful sieve</i> (O'Neill 's term) for now.<br />
<br />
What's important in the above code is the ability to
access the head of the stream and still lazily operate on the rest.Unfortunately, in Java <a href="http://download.java.net/jdk8/docs/api/java/util/stream/Stream.html#findFirst%28%29"><span style="font-family: "Courier New",Courier,monospace;">findFirst </span></a>is also one of those terminal operations on streams, so there is no obvious way to port this bit to Java without creating our own lazy list structure. We'll do that by building on the simple <span style="font-family: "Courier New",Courier,monospace;">ConsList </span>implementation alluded to in the <a href="http://sebastian-millies.blogspot.com/2013/06/higher-order-functions-in-java-8-part-1.html">previous post</a>, and extending it in several ways:<br />
<ul>
<li> add a factory method that accepts a <span style="font-family: "Courier New",Courier,monospace;">Function<T,T></span> to generate the elements in the tail in sequence</li>
<li>add a factory method that accepts a <span style="font-family: "Courier New",Courier,monospace;">Supplier<FilterableConsList<T>></span> to create a tail</li>
<li>add an instance method that accepts a <span style="font-family: "Courier New",Courier,monospace;">Predicate<T></span> to filter out non-matching elements from a list</li>
<li>make the implementation class lazy for the tail (but strict for the head).
</li>
</ul>
As a further goodie, we can easily implement the collection interface by providing an iterator and make the thing streamable by providing a spliterator of unknown size that is based on the iterator. The coding is lengthy but straightforward, it is shown at the bottom of this post. With it, the driver for generating the first 100 primes becomes:
<br />
<pre class="brush: java"> LazyConsList<Integer> s = sieve(LazyConsList.newList(2, x -> x + 1));
s.stream().limit(100).forEach(x->System.out.print(x + " "));
</pre>
where the interesting sieve-method is this:
<br />
<pre class="brush: java"> private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
Integer p = s.head();
return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
}
</pre>
Now I think that looks pretty neat (and very similar to the
corresponding Scala code). That's all I wanted to show. However, as Java 8 is still very new, it may not be quite obvious to many readers what's going on here. Let me try to explain.<br />
<br />
The text declares very clearly what it takes to output the first 100 primes: Create a list of integers starting at two, sieve it, take the first 100 elements and output them severally, where sieving consists of taking the first element of the list, then taking the rest disregarding any multiples of the first element, and sieving that again.<br />
<br />
Procedurally, the picture is very different: some method calls are deferred until the tail of a cons-list is accessed. In particular, there is no infinite loop, because every call to <span style="font-family: "Courier New",Courier,monospace;">sieve </span>in the expression<span style="font-family: "Courier New",Courier,monospace;"> () -> sieve(...)</span>is delayed until <span style="font-family: "Courier New",Courier,monospace;">forEach </span>requests another prime for output. Here's the sequence:<br />
<ol>
<li><span style="font-family: "Courier New",Courier,monospace;">forEach </span>causes the stream to get the next element from its underlying iterator</li>
<li>whereupon the iterator will return the first list element and change its own state by retrieving the tail of its list, which will be a list based on a <span style="font-family: "Courier New",Courier,monospace;">Supplier, </span>namely the one which came out of the previous call to sieve</li>
<li>the iterator's call to <span style="font-family: "Courier New",Courier,monospace;">tail </span>will in turn lead to strict evaluation of the method arguments to <span style="font-family: "Courier New",Courier,monospace;">sieve</span>, accessing the tail of the generator-based list and creating a new list from it by adding a new filter </li>
<li>so that when sieve is executed, a new cons-cell with a supplied tail is constructed, the head of which is the first element of the filtered list from step 4 and therefore a prime</li>
<li>which will be the next element returned from the stream when processing continues at step 1.</li>
</ol>
Contrary to appearances (and to the suggestive wording of the declarative meaning of the program) no list containing 100 primes is ever constructed and then output. Instead, you might say that the processing takes place "vertically", constructing a series of one-element lists and outputting their heads. You can see that clearly in a debugger, or by including some logging when entering and leaving the sieve.<br />
<br />
-- Sebastian<br />
<br />
Here's the complete code for our lazy list. I'm sure there's much to improve. One thing is that the <span style="font-family: "Courier New",Courier,monospace;">toString()</span> method that is inherited from the superclass is based on the list's iterator and will not terminate for an infinite list. I'd be grateful for suggestions or error reports (perhaps someone might like to write some unit tests?). First the interface:<br />
<pre class="brush: java">
import java.util.function.Predicate;
/**
* Interface for a list that may be filtered.
* @param <T> element type
* @author Sebastian Millies
*/
public interface FilterableConsList<T> extends ConsList<T> {
/**
* Applies the given filter to this list.
*
* @param f a filter predicate
* @return a list containing the elements of this list for which the filter
* predicate returns <code>true</code>)
*/
FilterableConsList<T> filter(Predicate<T> f);
/**
* Returns the tail of this list.
*
* @return tail
* @throws EmptyListException if the list is empty
*/
@Override
FilterableConsList<T> tail();
}
</pre>
And then the implementation:
<br />
<pre class="brush: java"> import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.function.UnaryOperator;
/**
* An immutable, filterable list that can be based on a generator function and
* is strict for the head and lazy for the tail. The tail can also be computed
* on demand by a Supplier instance. Via the Collection interface, this class
* is connected to the streams API.
*
* @param <T> element type
* @author Sebastian Millies
*/
public abstract class LazyConsList<T> extends AbstractCollection<T> implements FilterableConsList<T> {
// ------------- Factory methods
/**
* Create a non-empty list based on a generator function. The generator is
* evaluated when the first element in the tail of the list is accessed.
* @param <T> element type
* @param head the first element
* @param next the generator function.
* @return a new list with head as its head and the tail generated by next
*/
public static <T> LazyConsList<T> newList(final T head, final UnaryOperator<T> next) {
Objects.requireNonNull(next);
return new FunctionTail<>(head, next, x->true);
}
/**
* Create a list containing the given elements.
*
* @param <T> element type
* @param elems elements
* @return a new list
*/
public static <T> LazyConsList<T> newList(T... elems) {
LazyConsList<T> list = nil();
for (int i = elems.length - 1; i >= 0; i--) {
list = cons(elems[i], list);
}
return list;
}
/**
* Add an element at the front of a list.
* @param <T> element type
* @param elem new element
* @param list list to extend
* @return a new list with elem as its head and list as its tail
*/
public static <T> LazyConsList<T> cons(T elem, FilterableConsList<T> list) {
Objects.requireNonNull(list);
return new Cons<>(elem, list, x->true);
}
/**
* Add an element at the front of a list that will be supplied by the given supplier.
* @param <T> element type
* @param elem new element
* @param listSupplier list to extend
* @return a new list with elem as its head and list as its tail
*/
public static <T> LazyConsList<T> cons(T elem, Supplier<FilterableConsList<T>> listSupplier) {
Objects.requireNonNull(listSupplier);
return new SuppliedTail<>(elem, listSupplier, x->true);
}
/**
* Create an empty list.
* @param <T> element type
* @return an empty list
*/
public static <T> LazyConsList<T> nil() {
return new Nil<>();
}
/**
* Utility method that recurses through the specified list and its
* tails until it finds the first one with a head matching the filter.
* @param <T> element type
* @param list list that is filtered
* @param filter element filter
* @return the specified list or one of its tails
*/
protected static <T> FilterableConsList<T> applyFilter(FilterableConsList<T> list, Predicate<T> filter) {
FilterableConsList<T> filtered = list;
while (!filter.test(filtered.head())) {
filtered = filtered.tail();
}
return filtered;
}
// ------------- Constructor
protected LazyConsList() {
}
// ------------- Collection interface
@Override
public final Iterator<T> iterator() {
return new Iterator<T>() {
private ConsList<T> current = LazyConsList.this;
@Override
public boolean hasNext() {
return !current.isNil();
}
@Override
public T next() {
T head = current.head();
current = current.tail();
return head;
}
};
}
@Override
public final int size() {
throw new UnsupportedOperationException("the size of a lazy list cannot be determined");
}
@Override
public Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
// ------------- concrete subclasses
/**
* A non-empty list.
* @param <T> element type
*/
private static class Cons<T> extends LazyConsList<T> {
private final T head;
private final FilterableConsList<T> tail;
private final Predicate<T> filter;
public Cons(T head, FilterableConsList<T> tail, Predicate<T> filter) {
assert filter.test(head);
this.head = head;
this.tail = tail;
this.filter = filter;
}
@Override
public T head() {
return head;
}
@Override
public FilterableConsList<T> tail() {
return tail;
}
@Override
public boolean isNil() {
return false;
}
@Override
public FilterableConsList<T> filter(Predicate<T> f) {
Predicate<T> newFilter = filter.and(f);
FilterableConsList<T> filtered = applyFilter(this, newFilter);
return new Cons(filtered.head(), filtered.tail(), newFilter);
}
}
/**
* A non-empty list based on a generator function. The tail is lazily computed
* on demand and cached.
* @param <T> element type
*/
private static class FunctionTail<T> extends LazyConsList<T> {
private final T head;
private final UnaryOperator<T> next;
private final Predicate<T> filter;
private FilterableConsList<T> tailCache;
public FunctionTail(T head, UnaryOperator<T> next, Predicate<T> filter) {
assert filter.test(head);
this.head = head;
this.next = next;
this.filter = filter;
}
@Override
public T head() {
return head;
}
@Override
public FilterableConsList<T> tail() {
// construct a new lazy list with the first element that passes the filter.
// use the generator function to construct the elements.
if (tailCache == null) {
T nextHead = head;
do {
nextHead = next.apply(nextHead);
} while (!filter.test(nextHead));
tailCache = new FunctionTail(nextHead, next, filter);
}
return tailCache;
}
@Override
public boolean isNil() {
return false;
}
@Override
public FilterableConsList<T> filter(Predicate<T> f) {
Predicate<T> newFilter = filter.and(f);
FilterableConsList<T> filtered = applyFilter(this, newFilter);
return new FunctionTail(filtered.head(), next, newFilter);
}
}
/**
* A non-empty list based on a supplied computation. The tail is lazily computed
* on demand and cached.
* @param <T> element type
*/
private static class SuppliedTail<T> extends LazyConsList<T> {
private final T head;
private final Supplier<FilterableConsList<T>> supplier;
private final Predicate<T> filter;
private FilterableConsList<T> tailCache;
public SuppliedTail(T head, Supplier<FilterableConsList<T>> supplier, Predicate<T> filter) {
assert filter.test(head);
this.head = head;
this.supplier = supplier;
this.filter = filter;
}
@Override
public T head() {
return head;
}
@Override
public FilterableConsList<T> tail() {
// construct a new lazy list with the first element that passes the filter.
// delegate to the supplied function to create the tail of the current list.
if (tailCache == null) {
tailCache = applyFilter(supplier.get(), filter);
}
return tailCache;
}
@Override
public boolean isNil() {
return false;
}
@Override
public FilterableConsList<T> filter(Predicate<T> f) {
Predicate<T> newFilter = filter.and(f);
FilterableConsList<T> filtered = applyFilter(this, newFilter);
return new Cons(filtered.head(), filtered.tail(), newFilter);
}
}
/**
* An empty list. Trying to access components of this class will result in
* an EmptyListException at runtime.
* @param <T> element type
*/
private static class Nil<T> extends LazyConsList<T> {
@Override
public T head() {
throw new EmptyListException();
}
@Override
public FilterableConsList<T> tail() {
throw new EmptyListException();
}
@Override
public boolean isNil() {
return true;
}
@Override
public FilterableConsList<T> filter(Predicate<T> f) {
return this;
}
}
}
</pre>
Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com2tag:blogger.com,1999:blog-6979485574739813012.post-24397935053460889162013-06-14T10:55:00.000+02:002015-09-26T09:37:55.059+02:00Higher-Order Functions in Java 8 (Part 1)This post will show how the first few examples (pages 4 - 7) from John Hughes' 1984 paper <i>Why Functional Programming Matters</i> ([WHYFP]) may be implemented in Java 8. The paper has been revised several times, here's a link to the <a href="http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf">1990 version</a>. It's a useful <span style="font-size: small;"><span style="font-family: inherit;">starting point </span></span>to get acquainted with functional programming idioms. What's more, we'll reconstruct part of the new Java Collection (or Streams) API, namely the map/reduce operations.<br />
<br />
What this post is not:<br />
<ul>
<li>a general discussion of what's new in Java 8. Here is<a href="http://www.techempower.com/blog/2013/03/26/everything-about-java-8/"> an excellent overview</a>. In addition, I found this description of <a href="http://doanduyhai.wordpress.com/2012/07/15/java-8-lambda-in-details-part-iv-multiple-inheritance-resolution-for-defender-methods/">multiple inheritance resolution</a> very helpful.</li>
<li>An introduction to functional programming with lambdas in Java.Good places to start with that topic would be the "official" <a href="http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-4.html">State of the Lambda</a> and <span style="font-weight: normal;"><span style="font-family: inherit;"><span style="font-size: small;"><a href="http://www.lambdafaq.org/">Maurice Naftalin's Lambda FAQ</a></span></span></span> or <a href="http://www.angelikalanger.com/Lambdas/TOC.html#LambdaTutorial">Angelika Langer's Lambda Tutorial</a>.</li>
</ul>
I'd like to make one very technical point: Often, lambda expressions in Java are presented as syntactic sugar for (anonymous) inner classes. They're not. They are translated to byte code differently and make use of new JVM instructions. If you would like to know more about this, read Brian Goetze's article <span style="font-weight: normal;"><span style="font-size: small;"><span style="font-family: inherit;"><a href="http://cr.openjdk.java.net/~briangoetz/lambda/lambda-translation.html">Translation of Lambda Expressions</a> </span></span></span><span style="font-weight: normal;"><span style="font-size: small;"><span style="font-family: inherit;">and consult the Java API docs, perhaps starting with <a href="http://download.java.net/jdk8/docs/api/java/lang/invoke/LambdaMetafactory.html">LambdaMetaFactory</a>. </span></span></span><br />
<br />
The code examples have been compiled and tested with <a href="http://download.java.net/lambda/b88/">Java Lambda b88</a> and the Netbeans IDE Development version. (Build jdk8lambda-1731-on-20130523). They may or may not work with the latest builds, which can be downloaded from<br />
<ul>
<li><a href="http://bertram2.netbeans.org:8080/job/jdk8lambda/lastSuccessfulBuild/artifact/nbbuild/">NetBeans IDE</a> (<a href="http://www.jetbrains.com/idea/download/">IntelliJ IDEA CE 12.1.3</a> or higher also has good Java 8 support)</li>
<li><a href="http://jdk8.java.net/lambda/">Java 8 JDK </a></li>
</ul>
Set up your environment as follows:<br />
<ol>
<li>Download and unzip NetBeans and Java 8 </li>
<li>Run NetBeans with command line parameter --jdkhome <path to jdk8></li>
</ol>
Before we can get started, we need to define the recursive list data structure with which we're going to work: a list is something that is either <i>nil </i>(empty) or a <i>cons</i>-cell consisting of a <i>head </i>and a <i>tail</i> which is itself a list. Here's the interface:<br />
<pre class="brush: java">
public interface ConsList<T> {
/**
* Returns the first element of this list.
*
* @return head
* @throws EmptyListException if the list is empty
*/
T head();
/**
* Returns the tail of this list.
*
* @return tail
* @throws EmptyListException if the list is empty
*/
ConsList<T> tail();
/**
* Tests if this list is nil. Nil is the empty list.
*
* @return <code>true</code> if the list is empty, otherwise <code>false</code>
*/
boolean isNil();
}
</pre>
The implementation class (here called <span style="font-family: "Courier New",Courier,monospace;">SimpleConsList</span>) is not shown. It should provide some static factory methods (signatures see below) and a useful <span style="font-family: "Courier New",Courier,monospace;">toString </span>method.
Implementation guidelines can be found <a href="http://people.cis.ksu.edu/~schmidt/300s05/Lectures/Week7a.html">here</a>. (An enhanced version, which you can use with only minimal adjustments to some code shown later, is included in the <a href="http://sebastian-millies.blogspot.com/2013/06/higher-order-functions-in-java-8-part-2.html">follow-up</a> to this post.)<br />
<pre class="brush: java">
/**
* Create a list containing the given elements.
*
* @param <T> element type
* @param elems elements
* @return a new list
*/
public static <T> SimpleConsList<T> newList(T... elems);
/**
* Add an element at the front of a list.
* @param <T> element type
* @param elem new element
* @param list list to extend
* @return a new list with elem as its head and list as its tail
*/
public static <T> SimpleConsList<T> cons(T elem, ConsList<T> list);
/**
* Create an empty list.
* @param <T> element type
* @return an empty list
*/
public static <T> SimpleConsList<T> nil();
</pre>
<br />
Here's the motivating example taken from [WHYFP]: Suppose we wanted to add all the elements of a list of integers. Consider the following code:<br />
<pre class="brush: java">
public static Integer sum(ConsList<Integer> list) {
if (list.isNil()) {
return 0;
} else {
return list.head() + sum(list.tail());
}
}
</pre>
<br />
What's really Integer specific here? Only the type, the neutral element, and the addition operator. This means that the computation of a sum can be modularized into a general recursive pattern and the specific parts. This recursive pattern is conventionally called <span style="font-family: "Courier New",Courier,monospace;">foldr</span>. Here's it:
<br />
<pre class="brush: java"> public static <T, R> R foldr(BiFunction<T, R, R> f, R x, ConsList<T> list) {
if (list.isNil()) {
return x;
}
return f.apply(list.head(), foldr(f, x, list.tail()));
}
</pre>
<span style="font-family: "Courier New",Courier,monospace;">BiFunction </span>is a functional interface from the package <span style="font-family: "Courier New",Courier,monospace;">java.util.function</span>. It is the type of functions taking two arguments. Now we may print out the sum of a list of integers like this:
<br />
<pre class="brush: java">
ConsList<Integer> ints = SimpleConsList.newList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
System.out.println("Sum = " + foldr((x, y) -> x + y, 0, ints)); </pre>
<span style="font-family: "Courier New",Courier,monospace;">foldr </span>is called a <i>higher-order function</i>, because it takes another function as its argument. (This is sometimes expressed from a programming perspective as having "code as data".)<br />
<br />
There is also a closely related way to traverse a list, called <span style="font-family: "Courier New",Courier,monospace;">foldl</span>, which does the function application from left to right:
<br />
<pre class="brush: java"> public static <T, R> R foldl(BiFunction<T, R, R> f, R x, ConsList<T> list) {
if (list.isNil()) {
return x;
}
return foldl(f, f.apply(list.head(), x), list.tail());
}
</pre>
<br />
In fact a variant of <span style="font-family: "Courier New",Courier,monospace;">foldl </span>has been built into the Java Streams API. It's called <span style="font-family: "Courier New",Courier,monospace;">reduce</span>, because it may be used to "reduce" all the elements of a list to a single value (e. g. their sum). The naming is unfortunate, in my opinion, because as we shall see it relates only to a special (if typical) case of what can be done with it, but is usual in functional programming. Here's corresponding code using that built-in method on a <span style="font-family: "Courier New",Courier,monospace;">java.util.List</span>
<br />
<pre class="brush: java"> List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
System.out.println("Sum = " + intList.stream().reduce(0, (x, y) -> x + y));
</pre>
<br />
There is no correspondence to <span style="font-family: "Courier New",Courier,monospace;">foldr</span> in the Java API. Perhaps because <span style="font-family: "Courier New",Courier,monospace;">foldl </span>is tail recursive. However, <span style="font-family: "Courier New",Courier,monospace;">reduce</span> also differs in important ways from <span style="font-family: "Courier New",Courier,monospace;">foldl</span>: It requires the folding function to be associative (as in our example), and it is in fact not guaranteed to process the stream elements in a left-to-right order.<br />
<br />
The following code demonstrates how <span style="font-family: "Courier New",Courier,monospace;">foldr </span>(and its relative <span style="font-family: "Courier New",Courier,monospace;">foldl</span>) can be used to write many other functions on lists with no more programming effort. Here's how it works (cf. [WHYFP]):<br />
<ul>
<li><i>length </i>increments 0 as many times as there are <i>cons</i>'es</li>
<li><i>copy cons</i>'es the list elements onto the front of an empty list from right to left</li>
<li><i>reverse </i>is similar, except it uses <span style="font-family: "Courier New",Courier,monospace;">foldl </span>to do the <i>cons</i>-ing from left to right. Just for fun, the lambda expression has been replaced with a method reference.</li>
<li><i>append cons</i>'es the elements of chars1 onto the front of chars2 </li>
</ul>
<pre class="brush: java"> ConsList<Integer> ints = SimpleConsList.newList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
ConsList<Boolean> bools = SimpleConsList.newList(true, true, false);
ConsList<Character> chars1 = SimpleConsList.newList('a', 'b', 'c');
ConsList<Character> chars2 = SimpleConsList.newList('x', 'y', 'z');
System.out.println("Product = " + foldr((x, y) -> x * y, 1, ints));
System.out.println("One true = " + foldr((x, y) -> x || y, false, bools));
System.out.println("All true = " + foldr((x, y) -> x && y, true, bools));
System.out.println("Length = " + foldr((Boolean x, Integer y) -> y + 1, 0, bools));
System.out.println("Copy = " + foldr((x, y) -> cons(x, y), nil(), chars1));
System.out.println("Reverse = " + foldl(SimpleConsList::cons, nil(), chars1));
System.out.println("Append = " + foldr((x, y) -> cons(x, y), chars2, chars1));
</pre>
<br />
There's one more higher-order function I'd like to mention, namely <span style="font-family: "Courier New",Courier,monospace;">map</span>. This function takes a function argument <i>f</i> and applies<i> f </i>to all elements of a list, yielding a new list. For example, we may use it to double every element in a list:
<br />
<pre class="brush: java"> System.out.println("Double all = " + map(x -> 2 * x, ints));
</pre>
The map-function is also part of the Java Streams API. Following the derivation in [WHYFP] we may reconstruct it like this:
<br />
<pre class="brush: java"> // map f = foldr (cons . f ) nil
public static <T, R> ConsList<R> map(Function<T, R> f, ConsList<T> list) {
Function<R, Function<ConsList<R>, ConsList<R>>> cons = curry((x, y) -> cons(x, y));
return foldr((T x, ConsList<R> y) -> cons.compose(f).apply(x).apply(y), nil(), list);
}
</pre>
<span style="font-family: inherit;"><span style="font-size: small;">Here we observe several things: <span style="font-family: "Courier New",Courier,monospace;">map </span>makes use of functional composition, a standard operator which is built into the interface<span style="font-family: "Courier New",Courier,monospace;"> java.util.function.Function</span>. The expression <span style="font-family: "Courier New",Courier,monospace;">cons.compose(f) </span>returns a new function that first applies<i> f</i> to its argument and then applies <i>cons </i>to the result of that application. </span></span><span style="font-family: inherit;"><span style="font-size: small;">(Download the JDK source code and study how <span style="font-family: "Courier New",Courier,monospace;">compose </span>is implemented.) </span></span><br />
<br />
<span style="font-family: inherit;"><span style="font-size: small;">In order to apply functional composition, we must first "curry" the binary function. Currying transforms a single function of n arguments into n functions with a single argument each. Of course, we could just have defined <span style="font-family: "Courier New",Courier,monospace;">cons </span>in the method above as <span style="font-family: "Courier New",Courier,monospace;">x -> y -></span></span></span><span style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;"> </span>cons(x, y)<span style="font-family: inherit;"><span style="font-family: inherit;">,<span style="font-size: small;"> </span></span></span></span>but it's perhaps instructive to see a method that curries a <span style="font-family: inherit;"><span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;">BiFunction </span>(side note: unfortunately, I see no general way to curry an n-ary function for arbitrary n in Java, the type system is just not flexible enough):
</span></span><br />
<pre class="brush: java">public static <T, U, R> Function<T, Function<U, R>> curry(BiFunction<T, U, R> f) {
return (T t) -> (U u) -> f.apply(t, u);
}
</pre>
<span style="font-family: inherit;"><span style="font-size: small;">
Note that no actual function invocation takes place, i. e. <span style="font-family: "Courier New",Courier,monospace;">apply </span>is not invoked until both function arguments have been supplied. </span></span><span style="font-family: inherit;"><span style="font-size: small;">After all this effort, although the coding may look intimidating, <span style="font-family: "Courier New",Courier,monospace;">map</span> is just like our simple copy-list example above, except that the list elements are not just copied, but first transformed through <i>f</i>.</span></span><br />
<br />
<span style="font-family: inherit;"><span style="font-size: small;">Now we have all the pieces in hand to sum the elements of a matrix, where a matrix (implementation not shown) is represented as a list of lists.</span></span><span style="font-family: inherit;"><span style="font-size: small;"> The function <i>sumList </i>adds up all the rows</span></span><span style="font-family: inherit;"><span style="font-size: small;">, and then the leftmost</span></span><span style="font-family: inherit;"><span style="font-size: small;"> application of that function </span></span><span style="font-family: inherit;"><span style="font-size: small;">adds up the row totals to get the sum of the whole matrix.</span></span><br />
<pre class="brush: java"> Matrix<Integer> matrix = new Matrix(ints, ints, ints);
Function<ConsList<Integer>, Integer> sumList = x -> foldr((a, b) -> a + b, 0, x);
System.out.println("Matrix sum = " + sumList.compose((Matrix<Integer> m) -> map(x -> sumList.apply(x), m)).apply(matrix));
</pre>
<br />
In my opinion, this is not too verbose, but they certainly have not turned Java into Scala or Haskell. In Scala the same expression would read something like <span style="font-family: "Courier New",Courier,monospace;">val summatrix: List[List[Int]] => Int = sum.compose(map(sum))</span><br />
<br />
In fact, by partially evaluating the above expression with respect to functional composition and application to the matrix argument, we can manually derive the following equivalent expression, which is somewhat easier to understand: <span style="font-family: "Courier New",Courier,monospace;">sumList.apply(map(x -> sumList.apply(x), matrix))</span><br />
<br />
Mark Mahieu has written on the topic of <a href="http://markmahieu.blogspot.de/2007/12/currying-and-partial-application-with.html">partial evaluation</a> in Java.<br />
<br />
In this post you have seen how Java 8 makes it possible to pass functions around not only to apply them to data but also to manipulate them and combine them into other functions. You have also seen how the map-/reduce operations from the Java 8 Streams API may be understood in these terms. This has been textbook stuff. In <a href="http://sebastian-millies.blogspot.com/2013/06/higher-order-functions-in-java-8-part-2.html">another post</a>, I'll discuss the more exciting (I hope) topic of how lambda expressions are especially useful when combined with lazy evaluation. <br />
<br />
-- Sebastian<br />
<br />
Note: If you're curious how to use higher-order functions without language support for functional expressions, there are Java 7 (no lambda) versions of <span style="font-family: "Courier New",Courier,monospace;">foldr</span>, <span style="font-family: "Courier New",Courier,monospace;">foldl</span>, and <span style="font-family: "Courier New",Courier,monospace;">map </span>on <a href="http://www.adrianwalker.org/2010/04/map-foldr-foldl-higher-order-functions.html">Adrian Walker's blog</a>.Sebastian Millieshttp://www.blogger.com/profile/11109789625080423651noreply@blogger.com0