chas

What resources are there on the state of the art algorithm-wise for doing that conversion?

Haskell has been used to build embedded software to great effect. As you move out of the domain of simple sequencing in embedded systems and into hard realtime systems, coordinating tasks correctly becomes very difficult. Being able to track and infer information about timing and dependencies with the type system becomes extremely useful in order to make it easier. This is a very simple intro example of an DSL built in Haskell for realtime systems[0]. This is a talk on using Haskell for robotics in particular[1].

[0] https://leepike.wordpress.com/2009/05/05/an-atomic-fibonacci... [1] https://vimeo.com/77164337

I've used differential equations building a physics-based optimization system for an industrial process. Symbolically solving parts of the system really increased its accuracy and stability.

I think zzzcpan is suggesting to compile from the new toy language to C and then use a C compiler to get native code. This doesn't preclude only using libraries written in the new language. CHICKEN is a Scheme compiler that takes this approach.[0]

The submitted essay addresses the problems that can result from this sort of compilation style with the question "Will native compilation of a big project result in so much code that there's a global slowdown (something actually true of mid-1990s Erlang to C translators)?"

[0]http://www.call-cc.org/

I feel like the corollary to this is how quickly one could solve the problems in a pet programming language if $100M was on the line. If the compiler doesn't scale well, hire one of the authors for a bit as a consultant. C with Classes was once someone's pet programming language.

It sounds like imanaccount247 is from IMVU, they wrote up their experience with Haskell here: http://engineering.imvu.com/2014/03/24/what-its-like-to-use-...

It was previously discussed on HN here: https://news.ycombinator.com/item?id=7472452

Type theory is a framework for doing logic that predates computers as we know them. If you have used first-order predicate logic before (e.g. ∀x∀y(P(f(x))→¬(P(x)→ Q(f(y),x,z)))), it performs a similar role to type theory and is the same sort of mathematical thing, it just has different properties. Logical frameworks are interesting to programmers and computer scientists because logical systems and programming languages/computation are related through the Curry-Howard correspondence. http://math.stackexchange.com/questions/166430/curry-howard-...

This[1] isn't a perfect description of type theory in general because it is aimed at a particular branch of type theory called homotopy type theory, but I feel like it does a pretty good job of explaining the differences between type theory and set theory and what motivated those differences. [1]http://planetmath.org/11typetheoryversussettheory

Category theory is a particularly abstract part of abstract algebra primarily concerned with extremely general mathematical structures. It concerns itself with identifying and understanding the core structures common to a large number of mathematical objects and operations such as the one shared by multiplication, the cartesian product, least common multiple, logical conjunction (&&), and structs (or record types) in programming. This structure is usually referred to as the categorical product.

Category theory is often brought up when discussing type theory because there is a close relationship between these sorts of abstract structures like the one linking structs and conjunction and the structures that are described by type theory. In general, there is a close relationship between type theories and certain types of categories so you can learn interesting things about type theory from studying category theory and vice versa, but category theory contains many things which are not primarily useful for or associated with type theory.

Agda-mode will translate from symbol names to unicode for you. For example, \\to gets translated to → and \\== goes to ≡. It is very easy to work with after a short learning curve. There is more explanation available on the Agda Wiki. [0]

[0] http://wiki.portal.chalmers.se/agda/pmwiki.php?n=Docs.Unicod...

If you want an overview of the ideas behind this sort of research and a quick summary of some results, Greg Wilson gave a great talk on it[0].

I haven't read through the site to see what is there, but software engineering methodology and technique research* uses techniques from research of management techniques in business, making it closer to psychology or sociology. For more information, the blog "It Will Never Work in Theory"[1] does a good job of highlighting these sorts of results that are directly useful and has some explanation of the tools they are using to study software engineering practices. The book Making Software[2] goes into much more detail on software engineering research methodologies if you are interested.

*As opposed to CS theory research that could be used in software engineering, which is usually math.

[0] http://vimeo.com/9270320 [1] http://neverworkintheory.org/index.html [2] http://shop.oreilly.com/product/9780596808303.do

I'm not going to claim it solves concurrency, but Haskell's combination of STM, expressive types, and immutable data by default make it the nicest language I have used for concurrency. (I have heard similar praise of Clojure as well, but I don't have any experience with it.)

Edward Kmett's answer to this[1] question on Quora does a good job of explaining the value of lazy evaluation.

[1] http://www.quora.com/Programming-Languages/When-did-you-real...

Google has publically described their build system here http://google-engtools.blogspot.com/2011/08/build-in-cloud-h... (low fidelity) and here https://www.youtube.com/watch?v=2qv3fcXW1mg (high fidelity)

Microcontrollers are very useful if you have very tight power constraints because they have much less complexity than application processors and thus require much less power. For instance, the CC2538 uses ~1uA when sleeping whereas the best I have seen quoted for a Raspberry Pi (using a SleepyPi module), is ~500uA. [1]

This sort of OS is very useful in situations like wireless mesh networks where the code is more complex than would be suitable for a super-loop architecture, but the system is too resource-constrained to run something like Linux because it is trying to hit power requirements.

[1] http://spellfoundry.com/sleepy-pi/sleepy-pi-faq/#What_Is_The...

If you are comfortable with it, I think assembling your own openmotes[1] is the cheapest option. The actual parts on there are relatively cheap and hand solderable if you are okay with CFN components. In addition, there are other cheap and relatively easy options available in the community if you are feeling more adventurous. [2]

[1] http://www.openmote.com/openmote-cc2538/ [2] https://github.com/dmarion/cc2538-dev

This is incredible! After hearing about the MIT tinker toy optimal tic-tac-toe machine[1], I built a half-adder out of dominoes[2] around the same time period as that video and hadn't ever heard of anyone else messing with the concept.

[1] http://museum.mit.edu/nom150/entries/1215 [2] http://imgur.com/a/qq7Kl

I think the key bit of the title is "Algebra of Programs". This is a piece about being able to calculate programs. In section 12, Backus goes into some detail on how this construction makes algebraic reasoning easier and gives some specific examples. While it is not required to have a pure FP system to have a language that can be reasoned about algebraically, introducing arbitrary ad-hoc iteration will certainly destroy those algebraic properties.

I think this ties in well with Erik Meijer's essay from a few days ago[1]. If you are trying to produce a framework for mathematical reasoning, it does not make sense to allow arbitrary exceptions. As a species, humans are pretty new to this whole computing thing, so I would agree we don't have it figured out yet. However, over the last 5000 years or so we have developed a shockingly effective toolkit for reasoning about arbitrarily-defined abstract objects and I don't think it is unreasonable to try to bring those tools to bear on a newer class of abstract object, that is to say programs. The cost of this is that we have to figure out how to formalize our ad-hoc methods. This will be painful, but every engineering discipline does it. In essence, formalized design methods applied to practical problems are the core of engineering practice in general. For example, I think software engineering right now is in the same place as electronic filter design was in the 1920's. We have methods that work, given enough design effort, but our results are brittle and it is very difficult to make changes to working systems without introducing problems.

[1] https://news.ycombinator.com/item?id=7654601 [2] http://en.wikipedia.org/wiki/Butterworth_filter#Original_pap...

Note: I am blown away by Sussman's talk every time I watch it, but I think throwing out math as a tool for understanding computing is very premature given its success as a tool for building and understanding abstraction, especially given that computing as a field started as an attempt to understand some deep questions about the foundations of mathematics.

We did have practical functional programming languages 20 years ago. PG has been very vocal about the advantages of using Common Lisp to create Viaweb. Viaweb started the summer of 1995 and meets my bar for practicality. To the best of my knowledge, functional programming languages weren't as widely used then but it was not because no practical languages existed.

This is a few years old and leaves out 6LoWPAN[1], which wasn't yet commercially viable. 6LoWPAN is based on the same 802.15.4 hardware that ZigBee uses, but it has two significant advantages over ZigBee. First, it is TCP/IP that works on microcontrollers, so embedded devices running the protocol become first-class members of the internet with the addition of a very inexpensive router[2] to the network. This means that sensor nodes and embedded devices can seamlessly interoperate with traditional servers in a distributed computing environment and many programming techniques can be directly adapted.

Second, 6LoWPAN can be configured so that all nodes involved can sleep, whereas ZigBee requires always-on routing nodes in order to produce a true mesh. This means it isn't possible to use ZigBee to construct a mesh out of fungible battery-powered devices, which is a big problem for many applications.

If this interests you, there are a couple of very capable chips that have been released recently that are ideal for use with 6LoWPAN, namely TI's CC2538 [3] and Atmel's SAM R21 [4]. They both are supported by Contiki OS[5], which provides network stacks for extremely resource-constrained devices. It has been under development for ~10 years at this point as an open source academic/hobby project but in the last couple of years it has become significantly more professional and it is now used in many commercial applications. In addition, its core architects have launched a company called Thingsquare[6] based on Contiki which aims to be Heroku for low-powered wireless devices.

[1] IPv6 over Low power Wireless Personal Area Networks

[2] http://redwire.myshopify.com/collections/frontpage/products/...

[3] http://www.ti.com/product/cc2538

[4] http://www.atmel.com/tools/atsamr21-xpro.aspx?tab=devices

[5] http://contiki-os.org/

[6] http://thingsquare.com/

[7] If you want some CC2538-based open hardware: http://www.openmote.com/

You might be interested in Edward Kmett's automatic differentiation[0] package, ad[1]. It is one of my favorite non-trivial blendings of computer science techniques and more traditional mathematics. In specific, it uses Haskell's type system to prevent subtle numerical errors which other automatic differentiation libraries require the user to prevent by being very careful. The resulting code is much more trustworthy.

[0] http://en.wikipedia.org/wiki/Automatic_differentiation [1] https://github.com/ekmett/ad/

If anyone reading this wants to see what a basic "guess the number"-style game looks like in Haskell, I wrote one with the same basic logic, but a ton of different coding styles as well as java code that implements the same logic. https://gist.github.com/cleichner/6086604

Note: As you go farther down the page, the techniques become increasingly overkill for a program this small. For this sort of program, I actually like RandomProblem2.hs the most.

You are absolutely right that this isn't particularly novel. It generalizes a pretty wide range of concepts, which makes it hard to talk about accurately without resorting to jargon.

Iterators and generators are solutions to the same sort of problem but aren't quite as general. They do a good job of abstracting over streams and data structures, but I don't think they are as useful for dealing with single pieces of data with something special about them such as computations that could fail. It would be interesting to hack __iter__ to cover that case, but it's not idiomatic python. I think the "special types of data" idea works better in a statically-typed language so it would be non-pythonic on a couple of levels.

I use generators extensively in my python code, but I find they tend to infect programs. Once generators are used in one place, everything that interacts with that code works better as a generator. In Haskell, it is easier to use lifting for part of an expression without affecting the style of the rest of the program.

In addition, Haskell's type system and type inference make it possible to use these techniques in ways that would be very strange and difficult to do in Python which I didn't get in to in my original post because I wanted to stay in somewhat familiar territory. For example, functions are Functors and there are some interesting patterns that can be abstracted over by taking advantage of that. That said, if you thought of lifting like this as a strongly-typed slightly more general __iter__, you could be quite productive with it in Haskell. This is also useful for other languages because it makes it clear how much more general the __iter__ interface is and how it can be applied to things that are not data structures or streams.

I'm sorry that my explanation was so alienating to you. It was intended to be practical, but clearly I missed that mark for people without a certain amount of Haskell experience. Is there anything particularly confusing there that you would like explained?

The reason that I used the phrase "computational context" is because functors are very general. A Functor can be thought of as something that lets you translate functions with nothing special about them, just a function from a value to a value, into functions that operate correctly on non-vanilla values. Some examples of non-vanilla values (values with a computational context) are any value in a data structure (this is regular mapping over lists of values and trees of values), values that depend on external configuration or storing internal state (more useful for pure FP), operating on streaming data with functions that don't know about how you are streaming data, operating on data that might be missing without needing a null check, operating on data that might be actual data or an error code, operating on the results of a parser.

To give a python example, the lift function would be a decorator that made the function it was applied to correctly operate on almost any input value you gave it. If you give it a data structure, it is applied to all values in the data structure. If you give it a generator, it creates a new generator that runs the function over each element as it is generated, something like:

    return (f(x) for x in argument_generator)

where f is the function that the decorator was applied to. This isn't as popular in Python, but .then() in promises/futures is a lifting function that lifts functions operating on data to functions operating on data that may asynchronously arrive in the future or fail to arrive at all.

This is very practical because it allows you to write code with very little repetition or boilerplate. When someone makes a data structure or processing technique (streaming, parsing, non-determinism), they write the code to operate on values inside of the data structure or process. This code is now only located in the definition of lift/map instead of being spread between every function that wants to work with that data structure, but not take advantage of anything special about the data structure. This removes boilerplates from functions and makes them easier to read and understand. In addition, this makes functions more extensible with less work. Anyone who comes along with a new data structure or processing technique can use all of the existing functions they have without having to write a new compatibility layer between the new data structure or processing technique and their old functions. Writing lifting functions separates particular data structure or processing techniques from general functions. A function can be lifted into many different contexts without any changes. This decouples specific implementations from general functions.

Lifting like this is one of the most useful ideas I have taken from Haskell, but I think it's hard to see its utility through the C++. At it's core, lifting allows functions that don't require a computational context to be composed with values and functions that have a computational context. For instance, `unwords . reverse . words` is a function from Strings to Strings and is used like

    unwords . reverse . words $ "The quick brown fox" => "fox brown quick The"

or

    (unwords . reverse . words) "The quick brown fox" => "fox brown quick The".

This is just a pure deterministic function mapping values to values, it has no special context. To compose it with a value with a context like strings may not be present (Maybe String), it can be lifted with fmap (which really would be more informatively named liftF to keep with the Haskell lift function naming scheme).

    fmap (unwords . reverse . words) (Just "The quick brown fox") => Just "fox brown quick The"
    fmap (unwords . reverse . words) Nothing => Nothing

It now has failure awareness for free, with no effort by the original function author. Haskell has an infix synonym for fmap, <$>, that makes this even more natural:

    unwords . reverse . words <$> Just "The quick brown fox" => Just "fox brown quick The"

This looks very much like the first example:

   unwords . reverse . words $ "The quick brown fox" => "fox brown quick The"

This is really powerful because it means any function with no special context can now be used with any context that implements Functor (or Applicative for multi-argument functions). The view that fmap executes functions with no context in a special context also explains why fmap for lists is map. A function returning a list can be looked at as a function non-deterministically returning multiple values. This can be seen when using monadic bind (flatMap/concatMap) with functions returning lists:

   [1..5] >>= (\x -> [x-1, x, x+1]) => [0,1,2,1,2,3,2,3,4,3,4,5,4,5,6]

Looking at lists like this, a function with only one return value is deterministic, so if it is given a non-deterministic value, the result should be the result of applying the deterministic function to each possible non-deterministic value with no change in the number of possible non-deterministic values, that is to say that it should be mapped over the list!

   show  $   1     =>  "1"
   show <$> [1..5] => ["1","2","3","4","5"]
   fmap show [1..5] =>["1","2","3","4","5"]

The key idea here is that lifting like this provides a way to easily and extensibly compose functions with different expectations about the context in which they will be executing. This idea could be fruitfully applied in many languages outside of Haskell and I'm excited to see how it interacts with other parts of C++.

In my experience, C++ is really a double-edged sword in this regard.

At its best, it provides tools for building cost-free abstractions that hide bit-twiddling and assembly hacks while providing an expressive set of building blocks for the semantic layers above them. In this case a programmer only thinks about one layer at a time, so the mapping and messaging can be tuned to their domain, but the implementation is abstracted.

At its worst, it provides the verbosity of Enterprise Java with the memory safety of C and it becomes very difficult to trace what the program is doing and how. I have found this is very strongly related to the widespread use of non-smart pointers. This lets the semantic domains smear into each other and tends to produce astonishingly brittle code.

Exactly. I was trying to avoid any mathematical jargon while describing monoids because they are such general and pervasive structures in programming. Further, being able to construct useful new monoids is crucial for making full use of a finger tree and I didn't want to have someone find an interesting structure unapproachable because they had to walk through an abstract algebra jargon storm in order to understand it. I realize I referenced associativity without describing it, so I didn't quite achieve my goal, but hopefully the examples got the idea across to someone who might otherwise have dismissed it due to the perception that it was too academic and unapproachable.

As an aside, trying to remove the jargon from a definition like this is surprisingly hard and really expands the size of the definition. I think it is still worthwhile to try when writing for a general audience because algebraic structure is everywhere and very useful to recognize for people who are interested in rigorously manipulating abstraction, i.e. programmers.

I'm happy to see finger trees got mentioned. Finger trees[0] are extremely useful and general data structure that can be used to implement persistent sequences, priority queues, search trees and priority search queues. (Haskell's Data.Sequence[1] uses specialized 2-3 finger trees internally) They can form the basis of all sorts of interesting custom structures by supplying the appropriate monoid[3], but this does make them harder to approach if you are not familiar with the abstractions.

[3] A monoid is any structure that has members that can combine associatively. In addition, it must have an element that can combine with any other element and result in the other element. Some examples: (strings, string concatenation, the empty string); (integers, addition, 0); (natural numbers, max, 0); (booleans, and, True); (functions, composition, the identity function). The functional pearl[2] that describes the design of Haskell's diagrams library[4] goes into much more detail if you are interested in their application to programming.

[0] http://apfelmus.nfshost.com/articles/monoid-fingertree.html

[1] http://hackage.haskell.org/package/containers-0.5.4.0/docs/D...

[2] http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf

[4] http://projects.haskell.org/diagrams/

It isn't strictly required, but a background in algebraic topology is really useful for understanding the homotopy bit. That has point-set topology and abstract algebra as pre-reqs. Abstract algebra is a very useful tool for reasoning about computing in its own right.

In addition, experience with proof assistants and dependently typed programming would be really useful.

The last paper mentioned is likely one by Sapna Cheryan. She gives an overview of her work on stereotypes, identity, and computer science on her homepage[0] as well as links to relevant papers.

[0] http://faculty.washington.edu/scheryan/research.htm

I have had similar experiences with Kivy. I previously developed a simple game with PyMT[0] relatively easily, so I was very excited when Kivy came out. I had another project requiring multitouch support on a PC recently and decided to use Kivy and it immediately crashed my window manager every time I tried to run it which turned me off pretty quickly.

I ended up doing the multi-touch UI in JavaScript and HTML instead. It felt much clunkier to work with, but I wasn't comfortable with wrangling Kivy's instability for the rest of the project.

[0] http://cleichner.blogspot.com/2011/02/multitouch-project.htm...

You might be interested in tangible functional programming, which aims to bring useful composition to GUI programs.

http://conal.net/blog/posts/tangible-functional-programming-...