Wednesday, November 26, 2014

Issues with F# type inference

This week I continued my recent code rewrite efforts and was unhappy to note that F#'s type inference is still a bit flaky.

I had written a parser+type inference for an experimental functional language before I wrote my introduction-to-stateful-monads presentation. And although the original code was already lifting state monads (the last part of the presentation), it was doing so in a limited and heavy manner.  One of the ideas I have had for some time was to write an optimizer for specialized monadic code. Therefore, I thought it would be nice to rewrite my code to be fully "state lifting" centric because that would be closer to the type of code I would like to optimize.

To illustrate what I mean, the type inference monadic state has a counter. This counter is incremented to generate new free variables during the type inference. In my rewrite,  I tried to implement this increment function as:
let incVarCounter = liftState varCounter' (mapState inc)
where
let varCounter' f s = 
  let (r,x') = f s.varCounter
  (r,{s with varCounter=x'})
let mapState f = fun s -> (), f s
let liftState f m = fun s -> f m s 
(hopefully this is correct because I simplified the code for this blog).

varCounter is a field of a record with two type variables. Call it R<'a,'b>.
Unfortunately, the code above is inferred to the following by the F# compiler:
R < obj , obj > -> unit*R< obj , obj >
obj is the generic object type used when the type inference fails to deliver.

On the other hand, add a dummy unit argument to the function, as follow:
let incVarCounter() = liftState varCounter' (mapState inc)
This infers to:
unit -> R<'a,'b> -> unit*R<'a,'b>
which is has the correct type details.

These type details are needed because obj types are unusable. Adding the dummy unit argument is a work around; The question is "why do we still need workarounds for a language that is now at version 4"?  And more esthetically, if I want a monad, I want a monad, not a function that delivers a monad.

Friday, November 07, 2014

Do not confuse data logic and execution logic

I mentioned in my last post that I was looking for a bug in my autoindentation code.

Sadly, strong typing had given me a hint of my problem: I was returning a boolean that I had no use for, but I chose to ignore this by adding an operator that "swallowed" this return value. Yet the source of that boolean return value was my bug.  It just took me extra bit of time to find it.

My parser monad is like a Maybe monad: when a monadic expression fails,  the current expression branch stops and returns the failure up the call stack. If the failure happens to be within a higher order control structure, like an "or" statement or a "star" or "plus" repetition (for pattern matching), then another expression branch may be pursued which may succeed.

On the other hand, a monadic  expression may return a value. For example, a number may be parsed, and the number may be returned by the monadic expression.

It just so happened that my test to check if I was starting or not a block (for the autoindentation detection) was conceptually returning a boolean. Yet in fact it was not, it was either succeeding, or not, in its "higher order monadic logic". The correct code is something like: "if cond then return () else fail withErrorTagX" , while the false code reads "return cond" . When the second code fails, it returns a the failure (as a boolean) but it does not cause a change of execution behavior.

My autoindent code had three monadic functions: beginBlock, endBlock,  checkNotBeginOrEnd.
The two first functions had the correct logic,  the "check..." didn't. This last function was doing what its name was implying: it was checking, with pedantic code in the form of "if beginOfBlock then return false else if endOfBlock then return false else return true". But it should have said "if .. then fail ..."

I had two goals with this post. The first was to make clear the "dual level" of thinking that goes on when working with monadic constructions that have their own execution semantics. My second goal was to remark that execution logic is not the same as good old boolean logic. In my monadic operators, I have boolean operators, like "or", "and", "andNot". I come to realize that this denomination is not good because these are really not boolean operators and should not be confused with them.

Monday, November 03, 2014

Breakpoints in monadic code

I was trying to get my autoindenting parser working again in my old monadic F# code under Xamarin. To note that breakpoints are still an issue with higher order code. This post presents a simple way I get around the problem.

The problem is that higher order code, is first run to be assembled as higher order constructions, and then only later run "to do something". For example, monads are first bound, and then "run". The problem is that a breakpoint sets a stop during this construction phase, not during the execution phase. That is reasonable as the construction is what the top level function does, but it is of little use to the developer who wants to break the execution of the code and not its construction.

My parser monad is very combinatorial. I have operators for the classical parsing constructions like "and" and "or", but also a bunch of helper operators that are multiple variations of the bind operator, (e.g. combine two monads, return value of first), as well as error management helpers, and as well as monadic y-combinators to bootstrap recursive structures. When I use these, I rarely need to define functions on the fly, and therefore I end up with very few or even no anchor points for breakpoints.

To help with setting breakpoints, I have two functions both with the signature m<'a>->('a->'a)->m<'a> (give it a monad and a function and it  returns a monad). I define these as operators %>> and >>%. They are a form of restricted map function, the first calls the function before the execution of the monad, the second calls the function  after the execution of the monad. To use these, I define special breakpoint functions, for example "let breakHere x = x , on which I set breakpoints and which I slip in to my code, for example ... (m %>> breakHere) ... will break before the monad m.

This method needs a rebuild to set a new breakpoint. That does restrict its usage, but it is still very helpful.   

Tuesday, October 28, 2014

Lean Startup is about market making your product

I am a big fan of lean startup, and will therefore tell you why. Still, the method is not universal, and has its limits, I will tell you about that too.  If there is one thing you should remember is that lean startup gives you a simple recipe that can shape a new product both to meet the needs of its customers and to be profitable. To do that, the method needs customer interaction, and without enough of it, the method is likely to fail.

Lean startup is an iterative process. Yet unlike other development processes that only focus on the "how", lean startup gives you some very precise rules to follow on the "what".  Once you understand how the method works, these rules make sense. Here are the important "whats":
  • Value is defined relative to a reverse income statement (defined as the "engine of growth"). In effect you are expected to model both your product and your customers. You can use a simple model of fix price values per events (such as client clicks), or you can be more creative and use some real financial engineering tricks to build your notion of value.
  • Risk is to be minimized, and as risk is hard to measure, it is up to you to judge your uncertainties, and then to diminish your largest know risk/uncertainty at each development iteration.
  • Customers and products are understood through the data that can be collected out of them (this is the notion of "measure"). All value assumptions must be validated through the collection of data. Risk assumptions are not validated.
  • Continuous deployment means that software changes go directly into production (with some smart test automation in between). 
  • Software is "staged" into production. So new changes go into production, but normally only to be initially used by few. As data comes in that validates the code change and expected value improvements, the change will be made available to more users. Staged deployment makes it possible to simultaneously collect data on different versions of your product. This is the notion of split testing. If you have done enough math you will know that split testing, well implemented,  gives you the most reliable measure of how the customers are effected by your code changes.  Other ways to collect data will include much more noise..
  •  The careful observer will have noted that split testing within a "learn and change" loop is in effect a quasi-Newtonian optimization process. That is, we a looking for the best way to improve our product (equivalent to the steepest gradient). As we do not know that best way, and only know "a way", when the split testing confirms that the new version of the product is better than its previous version, we have a "quasi" method. As Newtonian methods are susceptible to getting stuck in local minimas, we need something more, and that is inspired by linear programming with the the notion "pivot": To pivot is to swivel variables into constraints and constraints into variable. Said differently, to pivot in business terms, is to change assumptions, to change your beliefs.
  • Data and data collection are core values in Lean Startup, and therefore the notion of pivot. In lean startup you must note all your assumptions down, and any change to these assumption (any "pivot")  must be noted down too. This type of detail may sound pedantic but that is how smart learning happens. And more importantly that is how good team learning happens, by making the effort to express and note down your assumptions, to validate them, and make the effort to update your notes (data) when you change these assumptions.
Expressed in this way, lean startup is one big algorithmic machine. People still have a role to play as they decide the changes they might want to bring to their income model and to their product. The lean startup algorithm makes sure that changes really do have impact on revenue and on product perception. The originality of the method is to be expressed within one recipe.

I do not know what made the creator of lean startup put his method together, but if you have worked in finance, and especially market making and algorithmic trading, then you have already been using  very similar methods. The big differences is that the method is meant for material products, and not immaterial financial products, and that these material products normally only have a single sided market, unlike financial markets where you can buy and sell. These two aspects do make the method a bit tricky when the income model is not obvious. For example, when income comes from advertisement, you can equate each advertisement screen refresh with income, therefore it is pretty simple to map customer events to income values. But suppose you want to move to a subscription model, now your customer is paying a monthly fee, how to map your products features to this income? If you have done enough math and worked in finance, you can think up a few ideas on how to do this, but nothing is obvious when you do not have this math experience. And that can make the method tricky to apply.

I like the method's smart tie into  financial theory. For example, simple portfolio theory say that it equivalent to maximize return under fixed variance, as to minimize variance under fixed return. So lean startup chooses the second option: minimize risk (variance) while having asked you to express return (inverse income statement, growth engine). To then make sure that you validate that return model with your collected data. As a full notion of variance would be impossibly complicated, lean startup says: focus on the largest risk. That is a simplest approach, but also the smartest approach.

Another tie to financial markets is that you need to make a market in your product for lean startup to exist. Making a market means that you attract customers to use your product. And because lean startup relies on a "market fitting" approach, that is, you fit your product and income model to your market of customer, the type and amount of customers you have will make all the difference in how your product evolves. This is a real issue because the good clients are not the ones that want to spend their time playing with small applications that only have a subset of functions. Therefore, a critical difficulty with lean startup is in how to bring valuable customers to a product that is not yet really valuable enough to them. This bootstrap phase can be most difficult and that explains why you need to cheat at bit and sometimes offer what you do not have to get the necessary feedback to validate your product's evolution. Unfortunately, customers will hesitate to come back to your product if the first time they came they felt deceived. So offering what you do not have, in order to get a feed back on the demand, will also tarnish you ability to grow later. This is especially true with small niche markets.

Market dynamics are much the higher order properties of a product. Many just ignore them and hope for the best when launching their new product. Lean startup makes the effort to try to learn about these market forces while you develop the product. It is not easy, it is not obvious, but it is still the right thing to do.


Sunday, October 05, 2014

Recreational programming: zipper augmentations

I rarely program professionally, so when I write software, it is in the spare moments I have between home and and work (theses days providing consultancy services). That really means on the bus and local tram and subway network here in Zurich.

I do not program for the fun of making my executables run; I mean, for the fun of having the program really do something useful. I program for the fun of the exploration! What I enjoy is understanding how to use new concepts. Usually these are in specific research domains,  which unfortunately for this blog, are still to remain unpublished, but the last two weeks have had me travel into more classical mathematical and software territories, which allows me to talk about them here.

The way research goes, is that you need take leaps of faith. There are lots of territories to explore, you have these gut feelings that tell you to go in one direction and in other. Yet each of these explorations will take time and effort, leaving you with no other choice than to do nothing with your feelings. Yet too much unexplored feeling will make you anxious. Therefore from time to time, you need to take the risk of following up on your desires, even if you do not know exactly where they will lead you.

This was the case for myself two weeks ago, I was feeling nostalgic of KD-Trees. I could not know for sure if part of me wanted to revisit them because my first (summer) job as a developer had me adding these tree structure to an electronic CAD program, or because there was more to find in revisiting them.  The only way to find out was to put in some real work. I therefore quickly implemented a KD-Tree for rectangles (it uses a four dimensional search space), in F# under Xamarin on my macbook.

Here I make a small parenthesis:  F# on Xamarin for iOS is great. Xamarin comes out with an update every week or two, and they keep it one of the most productive environment that I know of to develop mobile apps on.

Back to the trees. KD-Trees have the fancy property of allowing you to make quick proximity search with them (e.g. to find the nearest neighbor to a given point). Implementing them functional style allowed me to understand how to generalize this notion of  tree augmentation within the concept of zippers and focuses. A very nice and powerful concept. I try to explain this hereunder.
  • Take a search tree. 
  • Augment the tree
    • Tree augmentations are secondary key like values that are added to each tree node and that only depend depend the local subtree values. 
    • For example, in KD-Trees, you can store per node a bounding box of all elements stored at that node and below it. 
  • Now create a zipper for the tree
    •   A zipper is structure that breaks recursive structures, allowing you to serialize an access to them
  • Make a focus for this tree and zipper
    •   A focus allows you to travel up and down a tree with immutable data structures. It is a list of zippers and a node of the tree. The list of zippers is used to "go back up the tree".
    • See Huet paper for a good description of the focus/cursor/location.
  • Augment the zippers to complement the augmentations of the tree.
    • For example, in the case of the KD-Tree with nodes augmented with bounding boxes, the zippers can be augmented with a "bounding hole" that is what space around the current subtree search is known empty.
    • This is what my excursions into KD-Tree taught me: you can augment the zipper to complement the tree augmentation.
  •  Now create a map function that goes over the tree with a focus. With both the tree nodes and the zipper are augmented, the map can do proximity searches for each element of the tree in a record time.
  • Finally, wrap up this mapping function in a zipper comonad because it is cool! 
    • I tried to find a good zipper comonad example off the web to give you a reference but could not find any clean and obvious code. So just search for zipper comonad. 
(A note here that there seems to be a lots of variations on terminology. Some people use the term zipper to describe the focus, while others use the terms cursor, location, or context instead of focus. I just know that the first example I read about used the terminology I used above).

Finally, some people have used multiple KD-Tree to do parallel searches, but only partial search in each tree (example). Such a parallel "sampling" approach is a way to reduce the "skewing" effect that that each individual tree hierarchy has on the tree and zipper augmentations.

Friday, June 20, 2014

Scalable Designs for Multicore


I put together this presentation on how to design software that scales on multicores.
It uses examples in Java, yet the basic learning is same in all languages. (In fact, I learned it in C++).
(Original video on YouTube is: https://www.youtube.com/watch?v=op2Fh-iiKoA ).

Here's the summaries:

Basic multicore scalability (in Java)

  • Parallelize with threads and thread pools
  • Use enough threads (but not too many)
  • Thread pools assure execution on multiple cores
  • Keep same objects on same cores (as much as possible)
  • Avoid having multiple tasks working on the same data
  • Avoid locks (ex. attribute synchronized)
  • Avoid cache line contention

Patterns to manage lock conflicts

  1. Structured parallelism
  2. Non-blocking data structures
  3. Immutable or purely functional data structures

Patterns to manage core affinity

  1. Tasks last as long as program
  2. Tasks last as long as service they implement
  3. Tasks are dynamically extended

All original content copyright James Litsios, 2014.