7 ms·

Sure, you could likely compile a Haskell program to an embedded architecture, but Haskell is a garbage collected language. Allocating memory takes a long, nonde

Sure, you could likely compile a Haskell program to an embedded architecture, but Haskell is a garbage collected language. Allocating memory takes a long, nondeterministic amount of time on a microcontroller. And microcontroller are often used in control systems, where latency kills. Haskell also suffers from space leaks due to its lazyness. Microcontrollers have memory in the order of kilobytes, sometimes even less than that. You simply can't risk running out of memory, which is why micros are programmed in C or assembly, where you have a vice-like grip on how much RAM you use. For a higher-level look at the problem, consider that embedded systems are a high volume product. Saving a penny by using a cheaper, weaker micro adds up very quickly when you're shipping tens, or hundreds of thousands of devices. At that scale, it's profitable to spend more on non-recurring engineering (programmer time) in order to reduce the cost of manufacturing. If you want a functional-style language that is likely very well suited to embedded devices, look no further than Rust. While I haven't had the time to learn it (maybe next year), the language looks very promising due to its memory model.

m_mueller 8y ago
Thanks! That‘s pretty much exactly what I thought and I agree Rust looks promising for this purpose. On the other hand this is a variation of the two-language-problem and I wonder if it couldn’t in theory be solved with an approach like in Julia (even though it hasn’t so far in practice).
setr 8y ago
There’s not really any reason you couldn’t have a language that eventually offer almost all of haskell’s compile-level safety features, while keeping the vice grip, is there? Most of haskell’s benefits comes from its “sufficiently advanced compiler”, without reliance on gc benefits, I would think. Other than laziness, is haskell-the-language actually that dependent on a gc?
- m_mueller 8y ago
  A language is not just a set of possible semantics, it‘s also an ecosystem that herds people towards using it in a certain way. If that ecosystem breaks down under certain conditions the language becomes unusable. I think that aspect of language design is often underappreciated and maybe the main reason why we don’t have (and maybe will never) a one language to rule them all.
pjmlp 8y ago
While you are kind of right, when comparing managed languages with modern micro-controllers, people should go back and check the hardware capabilities of those 70's mainframes running Lisp binaries. A PIC won't do it, but there are others that will surely be able to.
- pflanze 8y ago
  The PIC18 can run the following Scheme implementation: https://github.com/stamourv/picobit https://github.com/stamourv/picobit (The (last of the original) main author(s) has stopped maintaining it, although there are many forks, some of which might be maintained, I haven't checked.)
  - pjmlp 8y ago
    Thanks for the link.
calebh 8y ago
I've worked extensively with functional programming on tiny microcontrollers like the Arduino. I created a research language called Juniper[1], which is a Haskell/F#-like language targeting the Arduino. As you mentioned, the memory size and the program size are the biggest two constraints. There's no space for a garbage collector, and everything has to be allocated on the stack. It turns out that it is possible to make the entire thing stack-free. The two biggest hurdles are function closures, arrays, and recursive data types. Function closures are typically allocated on the heap since it's possible to return functions from other functions. The solution is to include the closure as part of the function type, which means that they can then be allocated on the stack. Arrays are a bit more tricky to allocate on the stack. My solution is to statically size arrays with type level natural numbers, which means that the sizes are known at compile time. Recursive datatypes are a problem that I have not dealt with yet. In most Arduino projects recursive datatypes are not really used, so I just don't allow them. It might be possible to use type level natural numbers to put a bound on recursion depth. Another idea I had was to use run-timed size datatypes. For example, let's say you have a function F1 which calls F2. The frame pointers for their corresponding frames are at S1 and S2. When F2 returns a value of size N, the solution is to copy the value to a scratch space, return to F1, decrement the frame pointer, and then copy the value back into the stack frame. I'm not sure if this is really suitable for embedded systems since it's a lot of code/machinery which takes up precious program space. Rust is a great language which can work around these issues due to its linear types. I'm looking forward to using Rust once it starts to support the Arduino microcontrollers. [1]: http://www.juniper-lang.org/ http://www.juniper-lang.org/
- naasking 8y ago
  Very cool! Hadn't heard of Juniper before. Do you use something like regions to group and inline memory allocations?
  - calebh 8y ago
    In the next version of Juniper everything will be moved over to purely stack based allocation. Currently only function closures and refs are allocated on the heap. The refs are only created once when the program initializes itself, so that isn't an issue. The closures will become part of the function type. The FRP model works very well for the Arduino platform since you're essentially modelling a data-flow from input to output devices. Currently the compilation target is C++, which means that the Juniper compiler doesn't have a ton of control over the final assembly code.
naasking 8y ago
You don't need to actually run Haskell on the target, you could just use Haskell as a imperative DSL which compiles to C. Copilot does this for hard realtime programs in avionics.

m_mueller 8y ago

Thanks! That‘s pretty much exactly what I thought and I agree Rust looks promising for this purpose. On the other hand this is a variation of the two-language-problem and I wonder if it couldn’t in theory be solved with an approach like in Julia (even though it hasn’t so far in practice).

setr 8y ago

There’s not really any reason you couldn’t have a language that eventually offer almost all of haskell’s compile-level safety features, while keeping the vice grip, is there? Most of haskell’s benefits comes from its “sufficiently advanced compiler”, without reliance on gc benefits, I would think. Other than laziness, is haskell-the-language actually that dependent on a gc?

m_mueller 8y ago
A language is not just a set of possible semantics, it‘s also an ecosystem that herds people towards using it in a certain way. If that ecosystem breaks down under certain conditions the language becomes unusable. I think that aspect of language design is often underappreciated and maybe the main reason why we don’t have (and maybe will never) a one language to rule them all.

pjmlp 8y ago

While you are kind of right, when comparing managed languages with modern micro-controllers, people should go back and check the hardware capabilities of those 70's mainframes running Lisp binaries. A PIC won't do it, but there are others that will surely be able to.

pflanze 8y ago
The PIC18 can run the following Scheme implementation: https://github.com/stamourv/picobit https://github.com/stamourv/picobit (The (last of the original) main author(s) has stopped maintaining it, although there are many forks, some of which might be maintained, I haven't checked.)
- pjmlp 8y ago
  Thanks for the link.

calebh 8y ago

I've worked extensively with functional programming on tiny microcontrollers like the Arduino. I created a research language called Juniper[1], which is a Haskell/F#-like language targeting the Arduino. As you mentioned, the memory size and the program size are the biggest two constraints. There's no space for a garbage collector, and everything has to be allocated on the stack. It turns out that it is possible to make the entire thing stack-free. The two biggest hurdles are function closures, arrays, and recursive data types. Function closures are typically allocated on the heap since it's possible to return functions from other functions. The solution is to include the closure as part of the function type, which means that they can then be allocated on the stack. Arrays are a bit more tricky to allocate on the stack. My solution is to statically size arrays with type level natural numbers, which means that the sizes are known at compile time. Recursive datatypes are a problem that I have not dealt with yet. In most Arduino projects recursive datatypes are not really used, so I just don't allow them. It might be possible to use type level natural numbers to put a bound on recursion depth. Another idea I had was to use run-timed size datatypes. For example, let's say you have a function F1 which calls F2. The frame pointers for their corresponding frames are at S1 and S2. When F2 returns a value of size N, the solution is to copy the value to a scratch space, return to F1, decrement the frame pointer, and then copy the value back into the stack frame. I'm not sure if this is really suitable for embedded systems since it's a lot of code/machinery which takes up precious program space. Rust is a great language which can work around these issues due to its linear types. I'm looking forward to using Rust once it starts to support the Arduino microcontrollers. [1]: http://www.juniper-lang.org/ http://www.juniper-lang.org/

naasking 8y ago
Very cool! Hadn't heard of Juniper before. Do you use something like regions to group and inline memory allocations?
- calebh 8y ago
  In the next version of Juniper everything will be moved over to purely stack based allocation. Currently only function closures and refs are allocated on the heap. The refs are only created once when the program initializes itself, so that isn't an issue. The closures will become part of the function type. The FRP model works very well for the Arduino platform since you're essentially modelling a data-flow from input to output devices. Currently the compilation target is C++, which means that the Juniper compiler doesn't have a ton of control over the final assembly code.

naasking 8y ago

You don't need to actually run Haskell on the target, you could just use Haskell as a imperative DSL which compiles to C. Copilot does this for hard realtime programs in avionics.