[haskell-art] Is Haskell Really A Real-Time Language?

[Haskell Media]

Hi,

I've been reading conflicting things about Haskell being a language
suitable for DSP.

It's my understanding that a language needs to be designed for real-time
from the bottom up at the very beginning of the language design stage. I
know Paul Hudak was one of the designers of Haskell and he designed
Haskore/Euterpea.

Is Haskell really *hard* real-time? If not is it practically hard real-time?
What's the difference between soft and hard as far as designing your own
UGens are concerned? Does it matter?
Is it possible for a DSL to be hard real-time, but Haskell not be hard
realtime?
Is reactive-banana hard real-time?

HM

[Anton Kholomiov]

Haskell is not for hard real time.

Hard real time means for any operation you know
how long does it takes to execute it. Current GC makes
it impossible. You have to design GC for real-time.
There is one real world real time library in Haskell that I'm
aware of. It's Atom. It's code generator for C.
There is another library called Copilot and it is built
on top of the Atom.

So how can we build hard real-time apps in Haskell?
I can imagine two ways. First is code generation like Atom.
Second is having hard real-time server app and we can
send lightweight messages to it with Haskell.

Anton

[Stephen Sinclair]

On Mon, Aug 6, 2012 at 3:24 AM, Anton Kholomiov

Post by Anton Kholomiov
Haskell is not for hard real time.
Hard real time means for any operation you know
how long does it takes to execute it. Current GC makes
it impossible. You have to design GC for real-time.
There is one real world real time library in Haskell that I'm
aware of. It's Atom. It's code generator for C.
There is another library called Copilot and it is built
on top of the Atom.

I think it would be interesting to do online code generation using
LLVM and some DSL such as this attempt to copy FAUST semantics in
Haskell:

http://claudiusmaximus.goto10.org/cm/2009-12-04_heist_dataflow_algebra.html

One day when I have more time I want to do a project like that.
Basically, a Haskell DSL is used in a _declarative_ role to describe a
DSP graph, which is spawned as a real-time thread or process. I think
the trick that will make it interesting for use with Haskell is to
have seamless data interchange between the two. E.g. being able to
pass back and forth Num instances or even records between RT and
non-RT parts of the program. (The latter e.g. useful for game
programming.) Bonus if you can use polymorphism to have a DSP graph
that can be instantiated for either scalars or vectors to support
multi-channel audio.

Additionally, I wonder about the possibility of real-time extending of
the DSP graph. For example, while the DSP is running, the non-RT part
of the program could perform compilation of new blocks to a JITted RT
code block, which gets appended to the DSP graph by atomic swap of
function call pointers. (This might lead to weirdness if state is
involved I guess... e.g. delay lines would have to be properly
initialized.)

Post by Anton Kholomiov
So how can we build hard real-time apps in Haskell?
I can imagine two ways. First is code generation like Atom.
Second is having hard real-time server app and we can
send lightweight messages to it with Haskell.

This is effectively the SuperCollider approach, which of course works
fantastically well, though is maybe a bit less flexible, as UGens need
to be compiled ahead of time.

Steve

[Haskell Media]

Pure/Faust = Haskell/Supercollider? (maybe Faust is not a "server")

Has someone written an FRP language in C/C++?

I'm beginning to appreciate Pure-Data more everyday...

It's funny how difficult the realtime problem must be if most mainstream
languages can't guarantee a how long an operation will take to execute with
2012 hardware.

Post by Stephen Sinclair
On Mon, Aug 6, 2012 at 3:24 AM, Anton Kholomiov

Post by Anton Kholomiov
Haskell is not for hard real time.
Hard real time means for any operation you know
how long does it takes to execute it. Current GC makes
it impossible. You have to design GC for real-time.
There is one real world real time library in Haskell that I'm
aware of. It's Atom. It's code generator for C.
There is another library called Copilot and it is built
on top of the Atom.

I think it would be interesting to do online code generation using
LLVM and some DSL such as this attempt to copy FAUST semantics in
http://claudiusmaximus.goto10.org/cm/2009-12-04_heist_dataflow_algebra.html
One day when I have more time I want to do a project like that.
Basically, a Haskell DSL is used in a _declarative_ role to describe a
DSP graph, which is spawned as a real-time thread or process. I think
the trick that will make it interesting for use with Haskell is to
have seamless data interchange between the two. E.g. being able to
pass back and forth Num instances or even records between RT and
non-RT parts of the program. (The latter e.g. useful for game
programming.) Bonus if you can use polymorphism to have a DSP graph
that can be instantiated for either scalars or vectors to support
multi-channel audio.
Additionally, I wonder about the possibility of real-time extending of
the DSP graph. For example, while the DSP is running, the non-RT part
of the program could perform compilation of new blocks to a JITted RT
code block, which gets appended to the DSP graph by atomic swap of
function call pointers. (This might lead to weirdness if state is
involved I guess... e.g. delay lines would have to be properly
initialized.)

Post by Anton Kholomiov
So how can we build hard real-time apps in Haskell?
I can imagine two ways. First is code generation like Atom.
Second is having hard real-time server app and we can
send lightweight messages to it with Haskell.

This is effectively the SuperCollider approach, which of course works
fantastically well, though is maybe a bit less flexible, as UGens need
to be compiled ahead of time.
Steve
_______________________________________________
haskell-art mailing list
http://lists.lurk.org/mailman/listinfo/haskell-art

[Stephen Sinclair]

Post by Haskell Media
Pure/Faust = Haskell/Supercollider? (maybe Faust is not a "server")

No, it is a functional language for describing DSP graphs that
compiles to C++. (Or other back-ends, LLVM, C, JVM, JavaScript, etc.)

Post by Haskell Media
Has someone written an FRP language in C/C++?
I'm beginning to appreciate Pure-Data more everyday...

Pure Data is great but I prefer textual languages.

Post by Haskell Media
It's funny how difficult the realtime problem must be if most mainstream
languages can't guarantee a how long an operation will take to execute with
2012 hardware.

You know very well that it has nothing to do with "2012 hardware."
Garbage collection makes certain things easier, but certain things
harder, that is all. It makes expressing functional paradigms easier,
but makes real-time semantics more difficult to guarantee--it's just a
trade-off. The trick is figuring out how to "port" nice functional
ideas back to the non-GC'ed, real-time world without losing high-level
expressivity. However, there may be fundamental limits. In the
meantime you can always use C, and a good compromise is to simply make
low- and high-level paradigms talk to each other more seamlessly.

So... it's not that "we can't guarantee how long an operation will
take to execute with 2012 hardware," the things we _know_ how to do
well are still perfectly possible on 2012 hardware, it's just that
some _new_ problems are just fundamentally difficult to solve.

Steve

[Stephen Tetley]

The "French School" of reactive programming has mostly extended
imperative languages with reactivity (Reactive C, SugarCubes -> Java,
...).

Stephen Edwards and Edward Lee proposed "a new era of processors whose
temporal behaviour is as easily controlled as their logical function"
five years ago, sadly chip manufacturers haven't followed their call:

http://www.cs.columbia.edu/~sedwards/papers/edwards2007case.pdf

(FWIW - PRET machines target "control realtime" - for audio synthesis
"realtime" is something rather different).

Post by Haskell Media
Pure/Faust = Haskell/Supercollider? (maybe Faust is not a "server")
Has someone written an FRP language in C/C++?
I'm beginning to appreciate Pure-Data more everyday...
It's funny how difficult the realtime problem must be if most mainstream
languages can't guarantee a how long an operation will take to execute with
2012 hardware.

[Anton Kholomiov]

Online code generation is an interesting option.
You can do many optimisations. For example if
we have chain of units

-> a -> b -> c -> d ->

We can (in theory) make one loop, instead of four loops.

[Henning Thielemann]

Post by Anton Kholomiov
Online code generation is an interesting option.
You can do many optimisations. For example if
we have chain of units
-> a -> b -> c -> d ->
We can (in theory) make one loop, instead of four loops.

That's what I do with the LLVM-JIT.

[Anton Kholomiov]

Cool stuff! Is it a great win in practice?

Post by Anton Kholomiov
Online code generation is an interesting option.

Post by Anton Kholomiov
You can do many optimisations. For example if
we have chain of units
-> a -> b -> c -> d ->
We can (in theory) make one loop, instead of four loops.

That's what I do with the LLVM-JIT.
______________________________**_________________
haskell-art mailing list
http://lists.lurk.org/mailman/**listinfo/haskell-art<http://lists.lurk.org/mailman/listinfo/haskell-art>

[Henning Thielemann]

Post by Anton Kholomiov
Cool stuff! Is it a great win in practice?

I have compared SuperCollider and my synthesizer-llvm and they are
comparable in speed (it is difficult to find equivalent processes in both
projects). That is, synthesizer-llvm is really fast, but not faster than
SuperCollider, although synthesizer-llvm fuses loops and SuperCollider
does not.

[Anton Kholomiov]

Post by Anton Kholomiov
Cool stuff! Is it a great win in practice?
I have compared SuperCollider and my synthesizer-llvm and they are
comparable in speed (it is difficult to find equivalent processes in both
projects). That is, synthesizer-llvm is really fast, but not faster than
SuperCollider, although synthesizer-llvm fuses loops and SuperCollider does
not.

Maybe it's win in memory not in speed.
Suppose we have `na`, `nb`, `nc` and `nd` operations
per cycle. And `bs` is a block size.
How many samples we store per buffer.

In the first case we are doing

bs * na + bs * nb + bs * nc + bs * nd

and in the second case we are doing

bs * ( na + nb + + nc + nd )

But the first case needs five buffers, and the second
need only two.

Anton

[Hudak, Paul]

Just wanted to mention that CCA (Causal Commutative Arrows) is meant to address this somewhat. An expression in causal commutative normal form (CCNF) has just one loop (to simulate the passage of time) and no memory allocations - essentially it's a Mealy machine - and can be compiled into very efficient code. The problem (as Henning notes) is that you can still write arbitrary Haskell code that's outside this loop which can take an arbitrary amount of time.

Hard real time is real hard to do (pardon the pun on grammar) in any language, and the problem is not just GC. If you have a loop or recursion, then you somehow have to bound the number of iterations to get any kind of real-time guarantee.

Best, -Paul


From: Anton Kholomiov [mailto:***@gmail.com]
Sent: Tuesday, August 14, 2012 1:31 AM
To: haskell-***@lurk.org
Subject: Re: [haskell-art] Is Haskell Really A Real-Time Language?


2012/8/14 Henning Thielemann <***@henning-thielemann.de<mailto:***@henning-thielemann.de>>

On Tue, 14 Aug 2012, Anton Kholomiov wrote:
Cool stuff! Is it a great win in practice?

I have compared SuperCollider and my synthesizer-llvm and they are comparable in speed (it is difficult to find equivalent processes in both projects). That is, synthesizer-llvm is really fast, but not faster than SuperCollider, although synthesizer-llvm fuses loops and SuperCollider does not.


Maybe it's win in memory not in speed.
Suppose we have `na`, `nb`, `nc` and `nd` operations
per cycle. And `bs` is a block size.
How many samples we store per buffer.

In the first case we are doing

bs * na + bs * nb + bs * nc + bs * nd

and in the second case we are doing

bs * ( na + nb + + nc + nd )

But the first case needs five buffers, and the second
need only two.

Anton

[Conal Elliott]

Thanks to a Functor law: fmap g . fmap f == fmap (g . f) .

Post by Anton Kholomiov
Online code generation is an interesting option.
You can do many optimisations. For example if
we have chain of units
-> a -> b -> c -> d ->
We can (in theory) make one loop, instead of four loops.
_______________________________________________
haskell-art mailing list
http://lists.lurk.org/mailman/listinfo/haskell-art

[Conal Elliott]

Second is having hard real-time server app and we can send lightweight
messages to it with Haskell.

An early Fran implementation worked in this way, giving hundreds (sometimes
thousands) of frames per second on a late 1990s PC (until slowed to match
video refresh rate). See http://conal.net/papers/padl99/ .

-- Conal

On Mon, Aug 6, 2012 at 12:24 AM, Anton Kholomiov

Haskell is not for hard real time.
Hard real time means for any operation you know
how long does it takes to execute it. Current GC makes
it impossible. You have to design GC for real-time.
There is one real world real time library in Haskell that I'm
aware of. It's Atom. It's code generator for C.
There is another library called Copilot and it is built
on top of the Atom.
So how can we build hard real-time apps in Haskell?
I can imagine two ways. First is code generation like Atom.
Second is having hard real-time server app and we can
send lightweight messages to it with Haskell.
Anton
_______________________________________________
haskell-art mailing list
http://lists.lurk.org/mailman/listinfo/haskell-art

[Henning Thielemann]

Post by Anton Kholomiov
Haskell is not for hard real time.
Hard real time means for any operation you know
how long does it takes to execute it. Current GC makes
it impossible. You have to design GC for real-time.
There is one real world real time library in Haskell that I'm
aware of. It's Atom. It's code generator for C.
There is another library called Copilot and it is built
on top of the Atom.

There is also Feldspar which compiles signal processing code to C.

Heinrich has already kindly pointed to my synthesizer-llvm project. There
I create LLVM code for inner loops in audio signal processing that contain
no allocations and thus no garbage collection and thus should be realtime.
However, when it comes to synthesis of some sounds according to MIDI input
I use a lot of Haskell code which is not hard realtime.