The Traveling Santa Problem… a Neural Network solution

Once again the fantastic “F# Advent Calendar” organized by Sergey Tihon arrived bringing a festive spirit to all the F# enthusiasts.

The goal… helping Santa

This time, Santa has sent for help from his F# elves to help deliver toys to all the good boys and girls of the world. This year Santa is in a race to outpace all the Amazon drones and Jet deliveries, and is asking for our help to design the most efficient and effective flight path for his sleigh given a number of cities. This problem follows the format of the Traveling Salesman Problem. We will utilize Artificial Neural Network to design the perfect solution based on Elastic-Network learning algorithm.

The TSP is a combinatorial problem that involves Santa’s quest to visit a given number of cities and identifying the shortest path to travel between the cities. In addition, Santa is allowed to start and end the route from any city, but he can visit each city only once.

 

At first, this may not look like a complex program to solve, however, the number of possible combinations can dramatically (factorial) increase with the growth of the number of cities. For example, in the case of two cities the solution is only 1 path, with 5 cities there are 120 possible combinations, with 50, well… we have 30414093201713378043612608166064768844377641568960512000000000000 possible combinations. Understandably, a brute-force approach is not recommended, or Santa will be stuck in “recalculating” mode waiting on his MapQuest to come up with a route to deliver presents.

The Elastic Network we will use is a type of artificial neural network which utilizes unsupervised learning algorithms for clusterization problems and treats neural networks as a ring of nodes. The learning process keeps changing the shape of the ring, where each shape represents a possible solution.

 

Starting with Machine Learning

Machine learning is a fascinating and trendy topic these days, but like many other technologies it has its own terminology such as entropy error, resubstitution accuracy, linear and logistic regression that can sound intimidating at first.  Don’t let these terms turn you away, the effort you put into understanding Machine learning will be returned three fold.

In the last few months, I have started experimenting with and applying machine learning in different domains, including Natural Language Generation. In my work at STATMUSE, I am developing a Natural Language Processing back-end infrastructure in F# to provide Natural Language Interfaces for sports statistics. Check out this video to see a project interacting with Alexa (Amazon echo)

Thankfully, if you are a .NET developers, there many great resources to get more familiar with the topic. To name a few:

 

What’s the challenge?

In my opinion, the main challenge is figuring out how to map problems to a machine learning algorithm; as well as, how to choose the right machine learning algorithm to use. To help, the Microsoft Azure Machine Learning Team put together a very useful cheat-sheet here.

What really brought things home for me was seeing a video about Neural Networks in which James McCaffrey mentioned Neural Network as a Multi-Purpose machine learning algorithm!  See the video that spurred my revelation here.

 

What is a neural network?

An Artificial Neural Network (ANN) is an algorithm designed for pattern recognition and classification and can be used in many applications. Simply said, an ANN is composed by an interconnected set of artificial neurons. Even more fascinating is that computations are modeled and inspired after the biological brain in this learning algorithm, which can be applied to classification, recognition, prediction, simulation and many other different tasks.

Here, neurons are organized in sub-sets, called layers, where all the neurons in one layer are connected to all the neurons in the following layers.

For example, the following figure shows a three layered artificial neural network. The neurons from the first layer are propagated through the network and connected into to the second layer, and second to the third.

from the figure, a fully connected neural network with 3 inputs (the blue nodes), 4 nodes in the hidden layer (the green ones), and 2 nodes as outputs (the orange ones) has (3 * 4) + 4 + (4 * 2) + 2 = 26 weights and biases.  

The result of the ANN, referred to as output, relies on the weights of the connections between neurons. The most important concept is that ANN is capable of self-training to output distinct values determined by a particular given input.

The training of a neural network aims to find the values for the weights and biases that can be used to evaluate a set of given known inputs and outputs. The secret of a Neural Network is computing the most correct weight values. However, the Neural Network has to be trained to generate these values, which at the beginning are unknown.

 

Good News !

So, for the functional programmer enthusiast, you can think of a neural network as a mathematical function that accepts numeric inputs and generates numeric outputs.  Although, the value of the outputs is determined by other factors such as the number of layers, the activation functions, and the weights and bias values. Activation functions are used by the neurons to evaluate the inputs and calculate a relative output.

Neural Newark is fast!

Considering that ANNs are modeled after the biological brain, which in the case of a humans, means there are 10^16 synapses to execute multiple operations with a minimal energy.  Theoretically, ANNs could, achieve the same kind of performance, very impressive.

Neural Network can be faster… can run in parallel

The only thing more impressive than utilizing ANNs would be utilizing ANNs on a multicore platform applying concurrency…  That combination could effectively take Santa throughout the galaxy.

 

NOTE If you want to learn more on how to apply concurrency in your programming check out my book “Functional Concurrency in .NET”

It is time to code!

First, we are going to define each part that composes a ANN. Each component to compose the NN is defined using a RecordType. Ultimately we will run a benchmark to compare the sequential implementation, the parallel implementation with the variant of using the new F# 4.1 feature Struct RecordType.  More here

In F# 4.1, a record type can be represented as a struct with the [<Struct>] attribute. This allows records to now share the same performance characteristics as structs, without any other required changes to the type definition.

 

The User-Interface is all in F#

The User-Interface is WPF based, which implementation uses the FsXaml Type-Provider 

The graphic and animation are generated using the charts from FSharp.Charting library, specifically, the LiveChart

 

Neuron

The neuron is basic unit in a Neural Network. Each Layer in the ANN has a set of Neurons connected to the Neurons of the neighborhood layers, if any. In our ANN model, a Neuron contains the count of inputs and the output value, which is computed as the distance between its weights and inputs. More important, the weights array is used to train the NN to compute the best result.

The Neuron weights are initialized with random values, and successively updated in each iteration. The Threashold is a single value weight that can be used for Matrix operations, but irrelevant in our scenario.

 

Layer

A layer is simply a collection of Neurons of a same type. To solve the Traveling Santa Problem, only a single layer is needed. The compute function re-evaluates the output of each neuron, which is an array operation that can be parallelized.

Since a ANN requires a considerable number of Array operations to compute results, it is very suitable for implementation in a parallel programming model making the tasks considerably faster in a multi-processor environment.

The F# Array module used, provides Parallel functionality, which can is used to distribute processor intensive work to all processors and threads on the system.

 

Network

The Network is a record-type that contains and wraps the Layers of the NN. The compute function runs the re-computation of each underlying layers, which also in the case, the operation can be parallelized using the F# Array.Parallel module.

 

ElasticLearning

The ElasticLearning is an unsupervised learning algorithms, which desired output is not known on the learning stage, which lead to best result rather the perfect. The initialization (create function) sets some predefined arbitrary values. In the application, these values are configured in the WPF UI.

The “learning rate” value determinates how much each weight value can change during each update step, and can impact the training speed. A bigger value increases the speed of training but also increment hazard of skipping over optimal and correct weight values.

The compute function is used to train and to make the NN system learn from the updated weights, the inputs and the delta, which is measured according to the distance of the bestNetwork. The Array operation can be run in parallel updating the each Neuron weights values.

 

TravelingSantaProblem

The TravelingSantaProblem type has a single function foundBestPath, which execute the Neural Network algorithm by performing the computation of the ElasticLearning, and yielding an updated path for each iteration. The code is quite self-explanatory, it glues each components of the Neural Network and computes them to obtain the best path result. The function uses the FSharp.Control.AsyncSeq (details hereto yield asynchronously each updated path, which is used to update the LiveChart.

 

Here below the partial code of the main WPF ViewModel.

The implementation of the Neural Network to help Santa is done.  But lets take a look at the performance.

 

Benchmarking

Now, is time to benchmark and compare the sequential version of the NN with the parallel implementation that has been shown previously. In addition, we are comparing the performance of the same NN implementation but with the adoption of the new Struct RecordType introduced in F# .4.1. Here the graph of the benchmark.

The test has been executed on a 8 logical cores machine, and the Neural Network settings are:

  • Cities : 150
  • Neuron: 50
  • Itertaion: 30000
  • Learning Rate : 0.5

The parallel versions of the NN with Struct RecordType is the fastest.

The Neural Network that uses Reference RecordType produces (and updates) a large number of neuros, which increases the number of short-living objects in memory. In this case, the Garbage Collector is forced to perform several generations, which is impacting the performance negatively.

 

You can found the complete code implementation here.

The implementation is WPF based, but in the App.fs file you can uncomment some code to run the program as a console project.

 

In conclusion, I am far from being capable of building a self driving car or a Cyberdyne Systems series T-800 (aka Terminator), but ANN is not as complex as I had once thought.

 

What’s next?

I will speak at LambdaDays 2016  (here more details) “Fast Neural Networks… a no brainer!“, if you are in the are .. Please stop by and say !

I will talk about how to develop a fast Neural Network using a parallel K-Means algorithm for the training and leveraging GP-GPU.

 

This solution in the end ensures a Merry Christmas for all and for all a Happy New Year!

“The Ugly Duckling” – A Little Story About Functional Programming

Functional Programming has been around for possibly as long as the fable of the “ugly duckling”. The impetus for FP started in the 1930s thanks to Alonzo Church, a mathematician best known for formulating lambda calculus, a formal theory for expressing computation based on function abstraction and application using variable binding and substitution. The syntax and behavior of most programming languages today reflect this model. This early origin means that Functional Programming is a paradigm that existed from ideas older than the first programmable computer. Since then, functional languages have introduced several concepts later adopted by other languages. In 1950 the first functional language, Lisp came into use.

In 1959, in response to memory issues found in Lisp, John McCarty invented the Garbage Collector. Forty years later, mainstream languages such as Java and C# adopted the Garbage Collector. In 1960, the concept of first-class function was coined by Cristopher Strachey, who also invented the term currying, one of the fundamental principles of FP. In 1973, the functional language ML introduced the concepts of Type-Inference and parametric polymorphism. Forty years later these same concepts were introduced as “Generics” in mainstream languages. So as the story of the “ugly duckling” goes, a concept that initially was seen as strange and different eventually came into its prime. For FP that time is now because of its ability to maximize multicore core platforms.
In 1954 Fortran, the first imperative language was introduced in the market, and a year later Cobol, one other imperative language made its first appearance. Both these languages have had an enormous success in the software business world to the point that the imperative paradigm dominated the industry for thirty years.

In the 1970s, there was the need and interest in the Software industry for different and more practical solutions to solve increasingly complex problems. The rise of the Object-Oriented paradigm came from the growing demand for an improved programming model.
Since then, the OO has increasingly matured and evolved, today this paradigm is widely accepted by enterprises and has become the most popular paradigm in use.
The technology world is in a continuous and unstoppable evolution, the natural consequence of this expansion is more complex computing problems. Industry is realizing that FP is better than OO because of its declarative and expressive coding style. FP’s mathematical approach promotes immutability and functions without side effects allowing the programmer to solve the full spectrum of problems in less time and with less bugs. FP addresses computational problems in a manner similar to mathematics, ensuring the correctness of the program.

An increasing number of programming languages support the functional paradigm including C#, C++, Java and Python. In 1994, Python introduced support of lambda expression and list comprehension for data manipulation. Likewise, C# from the beginning has supported a functional paradigm for program writing, but the complexity of doing so has prevented programmers from using it. In 2007, C# 3.0 introduced first-class functions in the language and new constructs such as lambda expression and type inference to allow programmers to introduce functional programming concepts. Soon to follow was LINQ (Language Integrate Query), which permits a declarative programming style. More recently, in 2010, Microsoft introduced F# as a supported functional language in the .NET ecosystem. The latest generation of functional languages is impure because they allow side effects; the result of this variation is a reduced learning curve for those who embrace this paradigm for the first time. To combat unwanted side effects, the most successful implementation of functional languages today are “hybrids”. These functional languages bridge the gap between object oriented and functional paradigms allowing both programming styles.

If the current job demand is an indication of the future, interest in utilizing Functional Programming in applications will continue to increase, and so will the need for programmers who can bring this paradigm to business solutions.

Solving the Santa Claus Problem in F#

 

Christmas is no doubt my favorite time of the year; there is something magical about the holidays. To be true to this festive time of year, I was looking for a good topic to share on the fantastic “F# Advent Calendar 2015” organized by Sergey Tihon

Immediately, a paper that I read a little while ago came to mind.  It is from the title “Beautiful Concurrency” by Simon Peyton Jones (Microsoft Research, Cambridge May 1, 2007). You can download the paper here.

In this paper is a section titled “The Santa Claus Problem”, a well-known example originally introduced by John Trono in 1994. The Santa Claus problem provides an excellent exercise in concurrent programming. Trono published the exercise and provided a solution based on semaphores, designed for low-level mutual exclusion. While semaphores can and should be used to introduce concurrency concepts, they are not necessarily appropriate for writing concurrent programs.

Being that concurrent and parallel computing are areas of interest for me, I have decided to solve “The Santa Claus Problem” using F#.  Utilizing F# with it’s message passing semantic built in the MailboxProcessor will show the simplicity and readability that is possible to achieve by adopting these concurrent constructors.  Also, it is of course an appropriate and festive topic for the holiday season.

Here the running WPF Santa Claus Problem in F#

WPF Santa Claus Problem
 

INTRO

One of the main tenants of the functional paradigm is immutability. In computer programming, an object is immutable when it’s state cannot be updated after creation. In .NET for example, “Strings” are typically immutable objects.

Immutable objects are more thread-safe than mutable objects. Immutable data structures facilitate sharing data amongst otherwise isolated tasks in an efficient zero-copy manner. Functional programming excels in parallel computation for the reason that immutability is the default choice.  The real benefit is that no multi-thread access synchronization is necessary.

Using immutable objects in a programming model forces each thread to process against its own copy of data. Furthermore, it is completely safe to have multiple threads accessing shared data simultaneously if that access is read-only.

Immutability is a key concept to write lock free multithreaded software. One other critically important concept for writing lock-less concurrent code is natural isolation. In a multithreaded program, isolation solves the problem of “share of state” by giving each thread a copied portion of data to perform local computation.  When using isolation, there is no race condition because each task is processing an independent copy of its own data.  Isolation can be achieved by process isolation, which is based on independent and separate memory address space.

F# is a great functional-first multi paradigm programming language with powerful concurrent constructors, which provide an enormous boost to productivity. More over, The F# programming language, is naturally parallelizable because it uses immutably as default type constructor.  F# Async Workflow and MailboxProcessor (a.k.a. Agent) provides a simple concurrent programming model that is able to deliver fast and reliable concurrent programs, which are easy to understand.

The F# MailboxProcessor primitive is based on message passing also known as the “share nothing approach”. We will use these two contractors extensively to solve “The Santa Claus Problems”

 

The Problem

Santa Claus sleeps at the North Pole until awakened by either all nine reindeer collectively back from their holidays, or by a group of three out of ten elves.

In the case that Santa Claus is awakened by the reindeer, he harnesses each of them (9) to the sleigh to deliver the toys. When the toys have been delivered, Santa Claus then unharnesses the reindeer, and sends them off on vacation till next Christmas.

In the case that Santa Claus is awakened by a group of three or more elves, he meets them in his office to discuss the status of the toy production, solve existing problems and consult on toy R&D. When the meeting is over, Santa Claus allows the elves to go back to work. Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting.  Marshalling the reindeer or elves into a group must not be done by Santa since his time is extremely valuable. 
One of the challenges of the Santa Clause problem is to ensure the order of execution by enforcing the rules mentioned. In fact, if Santa Clause is already consulting with elves in his office, the program should not allow any extra elves to join a group nor should Santa Clause be able to deliver the toys regardless of the number of reindeer available if he is occupied by the elves and vice versa.

 

Summary of Santa’s tasks

  • Santa Claus sleeps at the North Pole until awakened by either (a) all of the nine reindeer, or (b) a group of three out of ten elves.
  • If awakened by the group of reindeer, Santa harnesses them to a sleigh, delivers toys, and finally unharnesses the reindeer who then go on vacation.
  • If awakened by a group of elves, Santa shows them into his office, consults with them on toy R&D, and finally shows them out so they can return to work constructing toys.
  • A waiting group of reindeer must be attended to by Santa before a waiting group of elves.
  • Since Santa’s time is extremely valuable, marshaling the reindeer or elves into a group must not be done by Santa.

 

The Solution

F# is a functional language with exceptional support for Asynchronous Workflow and with built-in message passing semantics with the MailboxProcessor.

To solve the Santa Claus Problem, we are using a message passing semantics, which show how the lack of shared state can simplify concurrent programming. The solution design uses the MailboxProcessor to create independents units, each responsible to coordinate and to marshal the groups of Elves or Reindeers. Each group has to organize among themselves without help from a Santa thread. One Agent is responsible to coordinate the Reindeer queue for when the Reindeer come back from vacation, and a separate and independent Agent to coordinate the Elf queue for when the Elves need to consult with Santa and join the waiting room.

One of the benefits of a system built using agents, is that the coordination and the synchronization between various threads can be implemented easily without sharing of state and therefore without locks, which removes pitfalls such as deadlock, livelock, and starvation.

Distributed memory systems using the message passing semantic, are simpler to write and prove correctness and also easier to refactor.

For example, in the Santa Claus problem, the constraint of having only three elves at time to consult with Santa, is implemented by a separate Elf queue, decoupling the Santa and Elf code further than the shared memory solutions.

The concurrency primitives of F# can be used to develop a sophisticated solution to the Santa Claus problem. The main problem is to synchronize a set of threads, that can be either reindeer or elves, and to manage them atomically by ensuring that one group of elves or reindeer does not overtake another group.  This synchronization, by using the agent model, is particularly simple to ensure. 

To easily terminate the program, we are using a ‘cancellation token’, which is generated and injected for each Agent and Async Operation. When the last year of Christmas is reached as expected, the ‘cancellation token’ is triggered provoking the cancellation and stop of all the processes involved, and consequentially to fire up the function registered to cleanup the resources and do some logging.

 

 

 

 

BarrierAsync

The BarrierAsync is a type whose job is to provide a re-entrance barrier for multiple threads to synchronize on. The purpose of BarrierAsync is to eliminate the need for an explicit shared state among synchronization threads.

 

 
The purpose of the asynchronous barrier implementation is to suspend asynchronous workflow until the barrier rolls. This type is constructed with a given number of ‘workers’, which are threads that are blocked awaiting the barrier to roll, releasing the threads.
 

The implementation of the BarrierAsync is using a message passing approach with the F# MailboxProcessor to convert concurrently posted messages into a sequence of messages. The function ‘AsyncSignalAndWait’ is sending an asynchronous ‘PostAndAsyncReply’ request to the agent using a ‘AsyncReplyChannel’ type, which is blocking the Asynchronous Workflow until all the workers have signaled the Barrier, which is rolling and releasing the threads by replying back to the channel of each worker.

For example, the BarrierAsync is used to synchronize the “three elves at a time” constraint. The Elf threads share state in the form of a counter so that every third elf in the waiting room will go and wake Santa. Each time an elf needs help from Santa, he sends an ‘AsyncSignalAndWait’ to the BarrierAsync, when the workers counter reaches the expected number, in this case three, the Barrier rolls and replies to all the workers to continue.

 

 SyncGate

The SyncGate type, is to deliver a threads synchronization equivalent to a Semaphore, but with specific interest in targeting the asynchronous workflow. The purpose of the SyncGate is to allow a given number of an asynchronous workflow to run simultaneously, and blocking further requests until a running workflow sends a request of release to the SyncGate.  This type is constructed with a given number of ‘locks’, which is the number of threads that are allowed to execute in parallel. The remaining threads are put in a queue and blocked awaiting for the SyncGate to receive a release signal when an executing thread terminates the work.

The implementation of the SyncGate, like the BarrierAsync, is using a message passing approach with the F# MailboxProcessor. There are two functions exposed, respectively to ‘Acquire’ a lock asynchronously, and to ‘Release’ a lock.

 

For example, in the implementation of the “Santa Claus Problem”, there is a SyncGate representing Santa Claus. In this case the SyncGate is constructed with only one lock available, to ensure that Santa is awakened either by the ninth reindeer or each third elf.

 

 

The complete source code can be found here.

There are two implementations, one is a console application which logs the output into the console, the second one is a WPF application.
 

This solution in the end ensures a Merry Christmas for all and for all a good night!

Parallelizing Async Tasks with Dependencies

Design your code to optimize performance

 

A little while ago, I had the requirement to write a tool that could execute a series of Async I/O tasks; each with a different set of dependencies, which influenced the order of the operation. This can be addressed simply with sequential execution, however if you want to maximize the performance, sequential operations just wont do – you must build the tasks to run in parallel.
To optimize performance these tasks need to be scheduled based on the dependency and the algorithm must be optimized to run the dependent tasks in serial as necessary and in parallel as much as possible.
Below is a typical example of a data structure such as a Graph, which can be used to represent scheduling constraints. A graph is an extremely powerful data structure in computer science that gives rise to very powerful algorithms.
A graph data structure consists of two basic elements:
Vertex – A single node in the graph, often encapsulates some sort of information.
Edge – Connects one or two vertices. Can contain a value.

A graph is collection of vertices connected by edges.
The implication of a directed graph leads to an expressive programming model. By using directed graph it is easy to enforce the one-way restriction. The definition says that a directed graph is a set of vertices and a collection of directed edges. Each directed edge connects an ordered pair of vertices. Here each task is represented as a Node in a graph, and the dependency between two nodes is represented by a direct edge.
dag

In this representation of a Directed Graph, Node 1 has dependencies on Node 4 and 5, Node 2 depends on Node 5, Node 3 has dependencies on Node 5 and 6 and so on.

See the code below for a simple implementation of a Directed Graph. The implementation is not the most elegant. It follows the imperative paradigm with mutable variable, but for demo purpose you get the idea of implementation.

This code is a good starting point, but there are some problems.

How can we ensure that all the edges required have been registered? Consider if Node 2 with dependencies to Node 7 and 8 is registered, but maybe Node 8 isn’t. Moreover, it could happen that some edges depend on each other, which would lead to a Directed Cycle. In the case of a Directed Cycle, it is critical to run some tasks in parallel; otherwise certain tasks could wait on another forever in a deadlock.

Another problem is registering a set of computations that have an order and precedence constraint. This means that some tasks must complete before some other task is begun. How can the system enforce and verify that all the tasks are completed while still respecting the ordered constraint?
The solution is called Topological Sort, which means that I can order all the vertices of the graph in such a way that all its directed edges target from a vertex earlier in the order to a vertex later in order. For example, if a Task A must be completed before Task B, and Task B must be compete before Task C which must complete before Task A; then there is a cycle reference and the system will notify of the mistake by throwing an exception. If a precedence constraint has a direct cycle, then there is not a solution. This kind of checking is called Directed cycle detection.
If a Directed Graph has satisfied these rules, it is considered a Directed Acyclic Graph (DAG), which is primed to run several tasks, which have dependencies in parallel.
The link here is a great article providing additional information about DAGs Paralleling operation with dependencies

Back to the figure above, Task 7 and 8 run in parallel. As soon as Task 8 complete the Task 5 starts and Task 6 will run after Task 7 and 8 are both complete, and so on.
Let’s implement the DAG solution applying the strategy we have learn here to run in tasks in parallel while respecting the order of the dependencies for increasing the performance.

Now, let’s define the data type representing the Task

The Type TaskInfo contains and keeps track of the details of the registered task, the id, function operation and dependency edges. The execution context is captured to be able to access information during the delayed execution such as the current user, any state associated with the logical thread of execution, code-access security information, and so forth. The start and end for the execution time will be published when the event fires.

The purpose of the function AddTask is to register a task including arbitrary dependency edges. This function accepts a unique id, a function task that has to be executed and a set of edges which are representing the ids of other registered tasks which all must all be completed before the current task can executed. If the array is empty, it means there are no dependencies.

The event OnTaskCompleted triggered each time a task is completed providing details such as execution time.

The function ExecuteTasks starts the process executing the tasks.

The core of the solution is implemented using a MailboxProcessor (aka Agent) which provides several benefits. Because the natural thread-safety of this is primitive, I can use .NET mutable collection to simplify the implementation of DAG. Immutability is an important component for writing correct and lock-free concurrent applications. Another important component to reach a thread safe result is isolation. The MailboxProcessor provides both concepts out of the box. In this case, I am taking advantage of isolation.

Overall is about finding the right tool for the job and being pragmatic in your approach,  in this case the .NET generic mutable collections work.

The MailboxProcessor named dagAgent is keeping the registered tasks in a current state “tasks” which is a map (tasks : Dictionary<int, TaskInfo>) between the id of each task and its details. Moreover, the Agent also keeps the state of the edge dependencies for each task id (edges : Dictionary<int, int list>). When the Agent receives the notification to start the execution, part of the process involves verifying that all the edge dependencies are registered and that there are no cycles within the graph.

If any of the validations are not satisfied, the process is interrupted and an error is thrown. For demo purposes only the message is printed in the console, a better solution should be to provide a public handler.

If the validation passed successfully, the process starts the execution, checking each task for dependencies thus enforcing the order and prioritization of execution. In this last case the edge task is re-queued into the dagAgent using the “QueueTask” message. Upon completion of a task, we simply remove the task from the graph. This frees up all its dependencies to be executed.

Here below the full implementation of the dagAgent:

You can find the complete code implementation here .

To run an example we can replicate the edge dependencies in the figure above.

The ouput should be

ouput

I hope you find this to be a useful example of how you can leverage parallelism to optimize your applications.

F# European Tour

The Geeks guide to F# travel

 

My tickets are purchased, bags packed, and laser pointer ops tested!   I am excited to begin my F# adventure which will take me to 10 presentations in 9 countries in 32 days! I will keep you posted as I travel along and invite you to follow me here or on twitter @TRikace.

 

Date Location Link
3/28 Bologna, Italy www.lamdbacon.org
3/30 Zurich, Switzerland http://www.meetup.com/zurich-fsharp-users/
3/31 Madrid, Spain http://www.meetup.com/madrid-fsharp/
4/2 Prague, Czech Republic http://www.meetup.com/Lambda-Meetup-Group/
4/6 Berlin, Germany http://www.meetup.com/thefunclub/
4/8 Amsterdam, Netherlands http://www.meetup.com/fp-ams
4/10 Paris, France meetup.com/Functional-Programming-in-F/
4/13 London, England  http://www.meetup.com/FSharpLondon/events/219808946/
4/14 Dublin, Ireland http://www.meetup.com/FunctionalKats/
4/17 London, England  https://skillsmatter.com/conferences/6724-fsharp-exchange-2015#program

Update – I am back!

I am back from my “European F# Adventure”, it was both wonderful and exhausting.  I met a lot of wonderful F# enthusiasts and had a ton of fun in the process.

The main reason for this trip was to spread the word on the benefits of F# and to establish our presence in the technology community. During and after the presentations I received many great questions and positive feedback, so much so, I am confident that F# has captured interested in several new developers.

I would like to thank the organizers of the Meetups and Conference that helped make my adventure possible and while making me feel welcome. There is no better way to visit these beautiful European Cities than under the guidance of its proud “locals” .

Thanks to Luigi Berettini (Bologna – LambdaCon), Marc Sigrist (Zurich F# UG), Alfoso Garcia (Madrid F# UG), Daniel Skarda (Praha FP UG), Kai Wu (Berlin FP UG), Michel Rijnders (Amsterdam FP UG), Tomasz Jaskula (Paris, F# UG), Philip Trelford (London F# UG), Andrea Magnorsky (Dublin FP UG), SkillsMatter London F# eXchange.

The F# Community is absolutely fantastic! During my journey I received supporting tweets and emails from fellow F#-pers that kept me going and enthusiastic for the next challenge!

 

 

The major take-away for me was that we are living in an exceptional time for technology especially for those embracing all that Functional programming and F# have to offer.  It seems that interest in our community and topics are popping up in many diverse forums.   Conferences and User roups focused on Functional Programming are multiplying with more Software Engineering and companies getting interested in the Functional Paradigm… there must be a reason!

 

Stay functional my friend!

F# and Named-Pipes

I am currently working on a project where I have an existing .NET application written in C# that is running on top of a Unity3D engine.

As part of the requirement, I have to develop a WPF host environment that in addition to hosting the Unity3D process is also able to send and receive commands.

The WPF application must also print the results in a report. The user will fill out a WPF form, which will feed the properties of a command. Once completed the user will send the command triggering an event.

In order to do this, I need a way to communicate between two different processes that could belong to different AppDomains.

2

 

 

I used the class NamedPipeClientStream and NamedPipeServerStream that support both synchronous and asynchronous read and write operations. Named pipes are a mechanism to provide interprocess communication in a client and server architecture style.

The reason I chose NamedPipe stream is because it supports full duplex communication, and is bi-directional per nature improving communication between a pipe server and one or more pipe clients.

Using NamedPipes is similar to using socket but with less code and layers of indirection to process.

PipeStream can communicate among processes through the Windows Pipes protocol. It is also great for intreprocess communication on a single computer, as a low-level abstraction that provides very high performance for sending and receiving data.

There are two type of windows pipe:

  • Named Pipe : which allows two-way communication between two processes on the same machine.
  • AnonymousPipe: which provides one-way communication between processes on the same machine.

For my scenario, I chose Named piped because it offers a two-way communication feature.

The NamedPipe has two subtype classes:

  • NamedPipeServerStream – which when instantiated will wait for a connection using the method “WaitForConnection”
  • NamedPipedClientStream – which when instantiated will attempt a connection to a NamedPipeServerStream

To ensure success it is important that in the creation of two way communication, both Named Piped streams agree on the same Name and protocol used. Equally important is to acknowledgethat both NamedPipe have to share the same size of the Data transmitted.

To help the transmission of lengthy messages, it is recommended to enable and leverage the “message transmission mode”.  If this modality is utilized, the PipeStream that is reading the message can check the “IsMessageComplete” property to evaluate if the Message is completed or if the Stream has to keep reading.

I highly recommend to use the “Message” transmission mode because it is impossible to determinate if the PipeStream has terminated sending the bytes stream or if it has completed reading a message simply checking if the Read bytes count is “0” zero.  According to the MSDN documentation, the PipeStream is acting like a Network stream which has no definite end.

I have chosen to implement the PipeStream using full Async capabilities and leveraging the F# Async computation expression.

The NamedPipServerStream out of the box uses the old Asynchronous Programming Model (APM), the NamedPipeServerStream class has BeginWaitForConnection and EndWaitForConnection methods defined, but it does not yet have a WaitForConnectionAsync method defined. To implement a custom Async method for waiting a connection it is very easy (not trivial) using the F# Async primitive types:

The NamedPipClentStream doesn’t have an asynchronous version of the connect API. Similar to the process previously used with NamedPipeServerStream, F# Async primitive can be used to create an asynchronous version of the connect method. Because the NamedPipClentStream doesn’t have an Asynchronous Programming Model (APM) for the Connect method, a delegate was created to help build the Asynchronous version

I have to say that using F# for this project allowed me to easily write code to meet the requirements while being expressive and concise. I was able to have all my code in one single “monitor page”.

My code has been reviewed by other developers who were unfamiliar with F# and they were able to easily understand the code without issues.

Ultimately, the application is used in a client side version that involves a responsive user interface. For this reason, I was able to leverage the F# Async computation expression to build a fully asynchronous Interprocess communicator providing a great user experience

Let’s check the code step by step.

1) The server process is started and NamedPipeServerStream waits asynchronously for a connection.

2) The client process is started and the NamedPipeClientStream waits to be connected to the server process.

I am setting two events are created to notify when the connection is established and when a message is received and completed. When the connection is successful, the NamedPipe is asynchronously waiting for incoming messages and the message received event will be triggered.

Because the program has to interpolate with code written in C#, the events are decorated with the [<CLIEventAttribute>] attribute .

3) The following recursive function is partially applied with signature (byte[] -> Async<unit>).  The purpose of this function is to return a bytes array as a representation of the message received.

4) The method to send a message is straight forward and self explanatory

5) The method that is listening for connection is using the Async version of the classic Asynchronous Programming Model “BeginWaitForConnection” as described previously.

For demonstration purposes I have created a struct Person that it is serialized in a bytes array to be able to be sent to the client process. The client process will receive the message and rehydrate the bytes array in the Person struct.

Here below the C# code that is consuming the F# library.