Abstract: I wrote a distributed (mostly) Functional Compiler in Scheme, OCaml and Elixir that incorporates knowledge of Computational Linear Algebra and domain specific knowledge to generate highly optimized linear algebra code from specification of problems. This talk is about lessons learned in the process.

The problem:
In every domain that uses computational linear algebra (which is all of engineering and science), we encounter the 'how to optimize a linear algebra expression into an optimized sequence of BLAS (or LAPACK or $linear_algera library) kernel calls' problem.

Example: (if the math equations make you want to tear your hair out and go jump off a cliff, don't worry, it is just an example, you don't have to grok it. Just skim the equations The basic problem being addressed here is that solving such equations with code takes up a lot of effort and time from experts in computational linear algebra)

Here is a linear algebra expression from a genetics problem , specifically GWAS -Genome Wide Association Studies, looking for significant associations for millions of genetic markers- where the essence of the problem [1] comes down to generating the most efficient algorithm possible that solves these equations

This in turn involves solving a 2 dimensional sequence of Generalized Least Squared Problems of the form

The algorithms to solve these can be directly coded up in Matlab or Julia. But there are problems with this approach, with this specific problem.

1. For different input sizes, different algorithms give the most optimal performance. Which algorithm do you code up?

2. Even for a given input size, there are multiple algorithms that compute the same result, but have differing computational characteristics depending on the hardware etc. How do you generate the optimal algorithm for your hardware ?

3. Most importantly the structure of *this* specific problem allows optimizations that are specific to the problem which are not built into generic linear algebra routines. (Obviously, one can't expect MATLAB to incorporate problem specific information for every scientific/engineering problem ever). The GLS problems are connected to others, thus saving intermediate results can save hours of computation vs calculating every GLS problem from scratch

In practice, one needs to be an expert in Computational Linear Algebra to come up with the optimized algorithm for a domain specific problem, and then write (say Fortran) code to use BLAS, LAPACK etc optimally to actualize this algorithm, often with much iteration, often consuming 100s of hours.

The Solution:

Incorporating this 'expert knowledge' into a compiler speeds up the time taken to arrive at the best solution (often by a factor of 100 or 1000), and allows Computational Linear Algebra experts to do more interesting things, like focus on their research.

For this particular problem, the above equations, and additional knowledge of the problem domain are the input into an expression compiler. The output is highly efficient and 'proved correct' code

In compiler terms, incorporating domain knowldege into the compilation process results in being able to apply optimizations to the generated Syntax Trees/Graphs, resulting in optimal algorithms. (note: the output of the compiler is a program in another language- say Matlab).

In essence, "Domain Specific Compilers" consume knowledge about the structure of a problem and generate optimized code that solves that problem.

Shin is one such compiler. It consumes a problem description and outputs highly efficient Julia code that solves the problem.

This talk focuses on the engineering challenges I faced in building this compiler, with a special focus on the approaches that failed [5]

Trivia:

"Shin" is the Hebrew letter, not the English word meaning 'front of the leg between knee and ankle' ;-).

Every company uses names from a common theme to name their servers and components - Athena, Zeus, Hercules , or Thor, Loki, Odin, or Jedi, Sith, Skywalker etc. We use Hebrew words, so we have Ruach, Melekh, Malkuth etc..

Summary: An Experience Report on How a very time constrained Haskeller learned Erlang and PureScript "in small pieces" to create programmatic opponents aka 'bots' for complex boardgames

Every experience report tells a story - the story of a project, unvarnished and without artifice, programmer to programmer, out of the sight and hearing of the manager folks, often involving one or more of comedy, tragedy, farce etc. This report is no exception.

I have a fulltime 'dayjob' and my standard 'language toolkit' is Haskell + C + Lua. My co-founder is a bit of an Erlang maniac, and challenged me to learn Erlang and actually building something in it and *then* go on about the superiority of Haskell.

This is the story of my response to the challenge and how I learned and coded Erlang/Elixir in very small chunks of time (about 10 - 20 )minutes a day max) and attacked an interesting problem. This severe time constraint (and lack of any previous knowledge of Erlang) shaped the nature of the (still evolving) system.

The problem:

The number of boardgames that you can whip out at a gathering and expect people to want play is very small.. Monopoly, Snakes and Ladders, and maybe, if you are *very* lucky, Settlers of Catan. And that's about it.

Getting people to play these games is relatively easy.

However the world of boardgames is *much* wider.

There are literally tens of thousands of boardgames that simulate everything from very abstract geometry puzzles to ones that simulate complex economies and political situations.

Some of the latter are used in very unexpected ways, e.g to train spies and military officers.

Here is an example of an interesting game.

A Distant Plain (by GMT Games) is a boardgame for 4 players that put them in the roles of the US military forces, the Afghan government, the Taliban, and Warlords/drug dealers, all competing for power in Afghanistan.

Here is another
The War of the Ring, a game for 2 players.

"In War of the Ring, one player takes control of the Free Peoples (FP), the other player controls Shadow Armies (SA). Initially, the Free People Nations are reluctant to take arms against Sauron, so they must be attacked by Sauron or persuaded by Gandalf or other Companions, before they start to fight properly ...."

And one more

"The battle of Sekigahara, fought in 1600 at a crossroads in Japan, unified that nation under the Tokugawa family for more than 250 years.

Sekigahara allows you to re-contest that war as Ishida Mitsunari, defender of a child heir, or Tokugawa Ieyasu, Japan's most powerful daimyo (feudal lord)."

."

What these games have in common
1. They are wonderful games, immersing you into their respective worlds.
2. They have (relative to Snakes and Ladders or Monopoly) complex rulesets, which take effort and time to master.
3. They are rarely played in India.
4. Even when people own them, opponents are almost impossible to find and schedule.

Which means that if you own these games and live in India, getting to actually play these games is close to impossible.

Which is a problem.

The (incomplete, but ongoing) solution

Being a programmer, I solve this problem by writing programmatic opponents (aka 'bots') to take the place of other players. This involves all kinds of interesting sub problems - game representation, logic processing for rules, building AI 'smarts' for your opponents, gui and event handling etc.

Since I am doing this in my non existent spare time, and this being a response to an Erlang user's challenge, I learned (am sill learning) Erlang and Elixir (and some minimal PureScript), and built ( am still building) the system at the same time..

This talk is about the many challenges I faced in building automated game players (and extracting common frameworks/libraries) from them, while simultaneously learning two FP languages.

Since this is an experience report, it is basically a highly subjective list of lessons learned, victories *and defeats*, what worked *and more importantly what didn't work*.

If you can't use FP at work, but are considering doing so on a personal project, or want to learn how to get going on an FP learning effort, you might benefit from my experience - both successes and failures. I also talk about how to go about learning Erlang/Elixir in the shortest possible time.

Equational Reasoning [1,2] is an intermediate/advanced FP technique, that sits at the intersection of programming and mathematics and has many interesting uses. It can be used to prove that a piece of code is correct, has specific performance properties,  to drastically reduce the size of a particular piece of code , assure that your code will scale to a bazillion servers, etc etc.

But how this technique works is often considered a mystery. What is also  missing is a step by step way to learn this method so you can use it in your code. Many books and blog entries show you examples and then you, the reader, are supposed to infer from these examples how Equational Reasoning  works.  When I first ventured into FP, I could (more or less) follow published examples, but never could figure out how this technique works and how to apply it to my code.

The key to such understanding (as I discovered much later) is to grok the underlying mathematical structure, specifically the nature of the logic and proof technique that provides the working machinery of Equational Reasoning.

In this presentation, I look at the mathematical underpinnings of this excellent programming technique. Once you understand how the math works [3], it is easy to see how the programming technique works. And once you know how that  works, you can use Equational Reasoning as just another tool in your dev toolbox.

Once they learn the basics of FP, most programmers are stuck with respect to how to get to the next  level.

The most common solution  (especially for Haskellers) is to try to deep dive into  Category Theory and Algebra, and their uses in FP.  Which is a good step if you can pull it off, but  in practice this is  much harder than it needs to be (which is the topic of another lecture someday), and many people give up at this point.

(imo) Understanding Equational Reasoning levels up your FP skills without necessarily having to learn CT structures simultaneously (though, of course nothing prevents you from learning both and combining them, as many Haskellers do), and is a gentler 'level up' than wrestling with Categories and Arrows and such.

This presentation reveals the nuts and bolts of why and how Equational Reasoning works. Then you can read the existing literature and gain much more out of it than otherwise.

Essentially, this talk  is what I wish someone had told me when I was trying to learn FP and got stuck.  You might be able to gain from my struggles!

[1] A blog entry explaining the basics

[2] A good book with many examples 

Some quotes from the preface

".. I (Richard Bird) was interested in the specific task of taking a clear but inefficient functional program, a program that acted as a specification of the problem in hand, and using equational reasoning to calculate a more efficient one."

" One factor that stimulated growing interest
in functional languages in the 1990s was that such languages were good for
equational reasoning. Indeed, the functional language GOFER, invented by
Mark Jones, captured this thought as an acronym. GOFER was one of the
languages that contributed to the development of Haskell, the language on
which this book is based. Equational reasoning dominates everything in this
book."

To be clear, this talk is not about the problems tackled in the book, though I'll use a couple of them as dissection specimens. The book shows (excellent) examples of applied ER, with a focus on generating efficient algorithms. My talk is about how ER works, and bridging the mathematical and programmatic machinery. We'll see, for example, why such derivation of efficient algorithms via ER works.

[3] I keep the math bits programmer friendly, so don't worry if you are not big on formal math. This is a talk addressed to programmers.  If you can write nested if statements or SQL queries, say, (iow if you have a couple of years of programming experience), specifically if you understand how logical operators (and, or, not) work,  you'll be fine. I'll fill in the rest.

"General Game Playing  is the design of artificial intelligence programs that play more than one game"  Wikipedia [1]

In other words, one program has to be able to play (and win!) multiple games ( Chess, checkers, Go, Othello etc).

Summary: This experience report is about my  "Forever Project" [2,3,4] to build such a system in OCaml, and the problems (theoretical and practical) and will include a demo of the program, warts and all.

Detail: GGP is an active CS research area [5]Annual competitions are held every year where  ggp programs compete against each other[6], playing games which they have never seen before (the rules are supplied as an input file for the system to consume five minutes before the match begins).

Over the last year, in my non-existent spare time, I've been building a GGP engine to compete in a GGP competition.

Most such engines are written in Java, C++  etc.. I'm using OCaml for the game playing agent, and Manoj is building the backend in Erlang.

As mentioned above this is our "Forever Project"  We've made some decent progress.

Come, see, laugh, jeer!