ClojureScript, Core.Async, and Om

Summary: I combined ClojureScript, Core.Async, and Om (React.js), and then optimized based on benchmarks. Sample Page

While playing with an older iPad, David Nolen's 10,000 dom updates with core.async example came to mind. But, when I opened the page, the browser just didn’t run the sample code well at all. I knew ClojureScript worked perfectly well on mobile browsers, so I thought it might be the DOM manipulation itself. The source on the page didn’t show any obvious requests for animation frames. So, I thought, if I started synchronizing the DOM manipulations around animation frames it might work.

After some research, I found that Facebook's React.js will synchronize all DOM manipulations, performed on it’s virtual DOM, with animation frames automatically. So, instead of trying to write manual synchronization code, I decided to push all the rendering to React.js. I chose to use the Om library, which wraps React.js, because of it’s nice ClojureScript interface. (Interestingly, David Nolen is responsible for Om as well as the original Core.Async example.)

Setup

All of the following tests were performed in Google Chrome 32.0.1700.107, on a Macbook Air running OSX 10.9. And, each test consisted of multiple runs, but I am only showing a single “good example” for brevity. Each test builds on each other, in the order they are shown.

Project Configuration

One Channel To Rule Them All

Baseline:

200 Frames

Min 90.257 ms

Avg 113.301 ms (9 FPS)

Max 162.476 ms

Standard Deviation 14.002 ms

Function Calls 14.12 seconds (60.03%)

Removing Source Maps:

200 Frames

Min 86.879 ms

Avg 112.068 ms (9 FPS)

Max 169.367 ms

Standard Deviation 15.046 ms

Function Calls 13.87 seconds (56.66%)

I didn’t expect any change here, and the numbers show that, but I thought it could be a variable. So, I removed them from the test project.

Compilation with Advanced Optimizations:

200 Frames

Min 58.056 ms

Avg 81.560 ms (12 FPS)

Max 150.629 ms

Standard Deviation 16.589 ms

Function Calls 7.62 seconds (46.10%)

Compiling ClojureScript with “Advanced Optimizations” enables all the optimizations available to the Google Closure compiler. In this mode I did need to change the project.clj file to include the React.js extern file, but the test code did not change. Similar to a C-style header file, the extern file informs the compiler what functions it can, and cannot, optimize. It makes a big difference in both size and, in this case, performance. This test really shows why you should turn on advanced optimizations when compiling for production.

Many Channels To Rule Them All

One Channel per Table Cell:

200 Frames

Min 17.239 ms

Avg 58.557 ms (17 FPS)

Max 109.993 ms

Standard Deviation 24.080 ms

Function Calls 4.31 seconds (35.47%)

The previous architecture used a single channel and had all the table cells read from it. It was the simplest thing I could think of originally. But, I decided to better mimic the original example and move to a channel per cell arrangement. This architecture, while improving the frame rate, tripled the average heap size, from ~8mb to ~23mb.

And, a closer look at the animation frame timing shows the total time between frames is now being dominated by the random delay between updates, instead of actual computation.

Tuning the Random Delay:

200 Frames

Min 17.582 ms

Avg 36.219 ms (28 FPS)

Max 64.888 ms

Standard Deviation 8.091 ms

Function Calls 4.43 seconds (59.62%)

After tuning the random delay limit, from a maximum of 100 milliseconds, down, to a maximum of 20 milliseconds, I achieved close to an average of 30 frames per second. I wanted to maintain some level of randomness between the updates, so I did not completely remove the delay.

Code Cleanup

Some Code Cleanup:

200 Frames

Min 16.051 ms

Avg 34.972 ms (29 FPS)

Max 57.388 ms

Standard Deviation 7.898 ms

Function Calls 4.33 seconds (60.82%)

Sample Page

Over the course of the tests, I noticed the Chrome developer tools, while profiling, appeared to degrade the overall javascript performance, so all the above absolute times should be taken as “under test” numbers. The animations appeared to run faster without the Chrome developer tools enabled.

Circling back to my original goal of running David Nolen’s demo, my modified version appears to run at a good speed on iOS 7 Mobile Safari and the Android version of Google Chrome. When I ran my code on the iOS version of Google Chrome, the performance still suffered. I can only assume Mobile Safari is cheating.

Update

Upgrading to Om 0.5.0-RC1:

200 Frames

Min 26.105 ms

Avg 84.024 ms (12 FPS)

Max 148.848 ms

Standard Deviation 29.089 ms

Function Calls 11.88 seconds (69.43%)

While writing this post, Facebook released version 0.9.0-RC1 of React.js. I reran the last test with the updated version to check for breakage, and found a large performance degradation. It is a release candidate, so I would expect the final release version to improve.

Centering a Div Tag with Physics, Instead of CSS

Summary: I combined a Javascript CSS parser and a Javascript physics engine to layout DOM elements with physics.

After reading yet another guide to layout with CSS, and yet another flame-war over CSS’s flaws, I just wanted to ditch CSS entirely. Tex has had a box and glue model, that has functioned well, for decades in print, but the tooling looks unusable for rendering webpage layouts requiring dynamic flexing and reflowing. So, why can’t I just connect two DOM nodes with a spring and have it flex as the the document resizes? (And, this is 2014. Where is my flying car?)

Using the real physical laws of motion, that people expect out of real world objects, actually makes some sense when you think of a document as in motion. CSS grids, using frameworks such as Twitter Bootstrap, have different layout configurations for ranges of different window sizes, based on CSS media queries. But, you can also see it as a page squeezing and stretching based on the user’s window size, with the DOM nodes connected by springs, colliding as the window is squeezed and stretching apart as the window is stretched. So, I built a Physics-based Page Layout system (Live demo).

Conceptual Springs

I am, currently, using a modified physics engine, originally built by by jonobr1, but there are numerous other engines to choose from. If I get the urge, I may swap it out for one that does continuous collision detection. This would help layouts squeeze correctly in response to other nodes, but would require a better abstraction around the current physics engine.

All the DOM nodes mentioned in a selector, or a declaration, are lazily assigned a particle group, containing one particle for each side (top, right, bottom, left) of a box. If the node is only mentioned inside a declaration, the particles are fixed in position, relative to the DOM node. This allows nodes to be used as anchors, without taking them out of the normal document flow. If the node is mentioned in a selector, the node is taken out of the document flow (absolute positioning) and given internal springs connecting each edge particle in a diamond pattern (top to right, right to bottom, bottom to left, left to top). This allows the particles, and thus the node, to flex in response to external springs. It would be interesting to conditionally disable those internal springs to provide partially-rigid boxes. But, that is not currently in the code base.

Originally, I kept the physics animation, of the springs flexing, as the system sought equilibrium. This behavior was fun to watch, but it resulted in terrible performance for document layout. So, now, it runs a fixed number of steps in time (500) without updating the DOM, and repeating as necessary to reach equilibrium. It might be nice to be able to conditionally re-enable the animation, as a way to assist debugging complex layouts, but that is not yet a priority.

After building this system, I think I now have a better understanding of the complexities around document layout. The current implementation is not much more than a proof-of-concept. To make it usable would require adding rigid connections, one-dimensional springs, minimum and maximum spring lengths, layers, cross-layer connections, shorthand declaration syntax, better performance, and more. So, for right now, it is just a neat proof-of-concept.

Infinite Lorem Ipsum with Markov chains

Summary: You can train a Markov chain on Latin text and build an infinite Lorem Ipsum string.

There are hundreds of websites, apps, plugins, and test pages utilizing to the semi-coherent, utterly incomprehensible, and much loved Lorem Ipsum text. After using it a large number of times, to fill gaps in preliminary designs, I took a moment to stare into it. In the middle of a late-night coding session, I stared into it, wondering if I too could build something of such infinite semi-coherence.

According to a Straight Dope post, the main source for the Lorem Ipsum Wikipedia article, the semi-coherent text is based on selections from the De finibus bonorum et malorum text by Cicero. Since my goal was an infinite string of semi-coherent text, the simplest solution is to train a Markov chain with Cicero’s text. Then, I could lazily pull as many words as I needed. They were still valid Latin words, but letter-order scrambling could be done on the resulting words.

I first became aware of using Markov chains for text synthesis with Garkov, a Garfield comic strip where the character’s dialog is replaced by a probabilistic model trained on genuine Garfield comic strips. I have never had a use for Markov chains in normal projects. Most of my efforts involve finding libraries and gluing them together (PostModern Programming style). And, I have never found a way to sneak such a fun way to generate semi-coherent text into a project.

Code: https://gist.github.com/Jared314/7983375

The wikipedia page does a great job explaining the details behind Markov chains, so I will only include the following images visualizing the training and text synthesis. In this case I used the letters in the string “at noon you can” to train the model, and generate the string “at nou”.

Input

Generated Model

Generated Text

In this case, the function, that generates the probability hash-map, relies on Clojure’s treatment of strings as a Seqable collection of characters and the hash-map keys being of semi-arbitrary type. So, the code will work on a seqable collection of strings without modification.

Since the probability hashmap is only limited by the allowed types for hashmap keys, numbers, objects, other collections, and functions will also work.

Note: As long as the training list can be chained, without error, the generated model prevents invalid function chaining.

I’m not exactly sure how infinite probabilistic function chaining is useful, but it … um ... sounds cool.

Adventures in Validating Email Addresses with Instaparse

Summary: The email address specifications are complex enough to require a full parser for proper validation.

It started simply enough. I wanted a function to validate the format of an email address.

The regex handled all the invalid cases I could think of. I just needed to test some valid addresses, to make sure I didn't have any false-negatives. So, I looked through the Wikipedia article on Email Addresses.

OK. I've covered those cases.

I didn't know TLDs were valid domains. But, the regex had that case covered.

Really? I guess that makes sense. I just needed to add a few characters to the regex.

Quoted strings?

That's valid?!

Email addresses can have comments?! Alright. Screw regex. I'm using the EBNF hammer.

Note: I'm using some of the PEG extensions for Instaparse, so this is neither pure EBNF nor a pure CFG.

With something this complex, I wanted a more extensive test suite to validate my validator. I found just that in Dominic Sayers’s project is_email(), which was built to solve the same problem in PHP. In the process, he created a test suite covering invalid, deprecated, standard specific, and other syntax cases. It looked like a good metric. And, at the time of writing, the above grammar identifies 74% of valid test cases as valid, and 100% of the invalid test cases as invalid. Since this is meant as a generic format validation function, I consider any test in the “ISEMAIL_ERR” category as an “invalid” case, and all other categories as “valid” cases, including deprecated syntax and length restrictions.

While writing my own grammar, I also ran across a similar post by George Pollard done with Ruby, in 2009. While I didn’t use any of his grammar, it’s nice to know i’m on the right track. Because, while you can use regex, you shouldn’t use regex to parse, or validate, an email address.

Improving the Clojure-Git Interface with a Nice Facade

Summary: A more composable Git interface can be built with a facade that implements standard Clojure interfaces.

In a previous post, I used clj-jgit to interact with a local Git repository. The functions, and general workflow, matched what I would have performed at the command line (git-add followed by git-commit). The workflow made it very easy to get started, and is preferable to using jgit directly, but, to me, it didn’t feel very Clojure-like. It felt like Bash.

While I was using git-add and git-commit, I wanted conj. A Git branch can almost be imagined as a very-persistent strongly-ordered hashmap. Every commit is addressable by a “key”, and has a sequence of commits behind it. I should be able to get commits, map and reduce over them, and conj on a new ones using the built-in clojure functions.

Associative, IFn, IObj, Oh My!

Dig into the Clojure (JVM) internals and you will quickly find a list of common interfaces for everything from metadata to data structure access. I only wanted the behavior of a hashmap, so my implementation list, after much exploration, shrunk to Associative, IFn, IObj, and Object. Associative accounted for most of the functionality, but did not provide map-as-function, metadata handling, or toString.

Proof of Concept

Full Source: https://gist.github.com/Jared314/6418917

Usage

Some points of interest:

• The idea of a staging area disappears because you can now construct a commit, as a hashmap, independently of Git.
• The metadata, and commit information, is queried lazily, and not cached, because the repository could be changed from outside the application.
• I have reused the TreeIterator from a previous post to allow commits without writing to the file system.

There is missing functionality (commit totals, changing branches, and a clean commit data format to name a few), but most of it was outside of my original goal of using conj to add a new commit. There are no technical hurdles to prevent those features in the future, but my application did not call for them. This might make for a nice feature to submit to the clj-jgit project, if I ever fill in the missing features.

Automating a Clojure Project's File Layout

I have come to accept the file's place in application development. In Leiningen based Clojure projects, a clean project layout has a file per namespace layout, and a directory per parent namespace. But, as a developer, I write functions, not files. The files are just artifacts. The creation and organization of code files is so systematic, it could be automated with something that maps functions/declarations into the hierarchical file structure used by project tooling.

Proof of concept: (https://gist.github.com/Jared314/6144582)

The idea behind this “object-hierarchical mapper” is to abstract out the project file layout from the functions and namespaces. There is too much tooling around files to replace them as a code storage format, but there is very little reason to think about file organization.

This code works by passing the function declarations (thing1, thing2, and thing3), with their corresponding namespace declarations (tester1.core, tester1.server), to the parse function which builds a tree whose nodes correspond to the namespace hierarchy. That tree (nested hash-maps) is then written out to the file system, using the write! function, into a valid project structure. The current issues center around optimizations, and messy code. In the generated files, the namespace declarations are not combined efficiently, and the functions are preceded by a list of declares to prevent reference ordering issues.

This is not a new concept. I would guess the idea extends as far back as the 1960s, because that really appears to be the case with most ideas in CS. I just remember the first time I was amazed by the idea after watching the Code Bubbles demo. More recently, Light Table also had a similar demo, where code was edited in a single visual workspace. I believe they plan to bring that feature back in a future version. No matter where the idea came from, it seems like a useful layer of indirection.

This might end up working best as a lein plugin, with editors saving their changes “through” it, because the project file layout is tied to lein and other lein plugins. It might also be an interesting experiment to use a git repository as an additional backend, but that would have to happen after a refactoring of the write! function to something more functionally pure.

Learning core.async: A High School Tale

The examples use the 2013-07-24 snapshot of core.async. At the time of writing, the API is still in flux and very experimental.

[org.clojure/core.async "0.1.0-SNAPSHOT"]

from:

["sonatype-oss-public" "https://oss.sonatype.org/content/repositories/snapshots/"]

Once upon a time, Alice wanted to invite Bob to an awesome party she had heard about, but she didn’t know where the party is going to be yet. So, she told Bob to wait by his phone, and she would send him the location, when she found out.

https://gist.github.com/Jared314/6043638

Unfortunately for them, the police were monitoring all the text messages. So, the police showed up, about an hour after the party had started, and arrested everyone for underage drinking.

Broadcasting

Alice, now feeling bad about the last party, decided to make it up to Bob and Carol by inviting them both to the next party she heard about. But, this time, she wanted to make sure no one else could see the message. So, she made a Facebook group, and only included Bob and Carol.

https://gist.github.com/Jared314/6047489

Unfortunately for them, the police were monitoring all the Facebook groups and messages. So, the police showed up, about an hour after the party had started, and arrested everyone for underage drinking.

Chaining Go Blocks

Alice decided to try one more time. This time also including Dave, to make up for the last failed party. But, Alice was getting slightly paranoid, so she decided to only tell Bob the location of the party, then have Bob tell Carol, and then have Carol pass it on to Dave.

https://gist.github.com/Jared314/6047624

Unfortunately for them, Dave got pulled over by the police, for a broken tail light, on his way to the party. Being within one hundred miles of the border, the police searched his car and found the handwritten note from Carol. So, the police showed up, about an hour after the party had started, and arrested everyone for underage drinking.

Timeouts

With this being the third time Alice, Bob, Carol, Dave, and Eve had appeared in his court, Judge Frank was ready to throw them in jail. In each case he decided to sentence them to several months in jail, based on their honesty (represented by a random number), with the option of letting them out early on good behavior (represented by an extra channel for each person).

https://gist.github.com/Jared314/6047789

Takeaways:

1. Go blocks will block and execute in their own thread pool or, for the cljs version, their own state-machine-context-like-thing.
2. The broadcast and multiplex (a.k.a. fan-out and fan-in) currently exist only as experiments. I hope they get rolled into the library, because I don’t want to have to write them myself.
3. There is no “wait for all channels to have a value” function. Alts! and Multiplex return on the first channel to have a value.
4. It looks like you could change the underlying channel implementation to something like a ZeroMQ (zmq-async) or RabbitMQ, but i’m not sure if it would actually be a useful abstraction.