System monad

[emilaxelsson]

As seen in #122, I'm working on adding support for system calls to Feldspar.

There are some issues related to this that I would like to discuss.

Which monad?

I'm currently (ab)using the M monad for system calls which is not so good given that M is for mutable data structures and that it has a run function. A better solution seems to be to define a new Sys monad as a newtype wrapper. The core language would use the same monad for both Sys and M, but the interfaces would be different:

• Sys calls are only allowed in Sys
• runMutable only works for M

The only problem I see with this is that one would have to redefine the mutable data structures for the Sys monad, since we need references and arrays also at the system level.

Another option might be to just have a single monad, and have a static analysis that checks for sys calls under runMutable.

Semantics

foreignCall requires a semantic function to be provided. But I think it will be hard to model all sys calls as Haskell functions. So I suggest that we simply leave the semantics undefined for sys calls (when there is no sensible semantics to give).

Here is my motivation: Sys calls will be used to implement various system abstractions in Feldspar. These abstractions should be implemented as shallow or deep EDSLs on top of Feldspar, but their implementation should not rely on sys calls. Instead, we will provide one or more compilation functions that translate the EDSL to Feldspar programs with sys calls. But when evaluating the EDSL, we should not use the compilation function but rather a specialized evaluator for the EDSL (that calls Feldspar's eval).

As an example, the implementation of Stream does not use sys calls, but one can imagine a compilation function that translates a stream into a loop in the Sys monad that uses sys calls write out the output stream.

[pjonsson]

I agree that we can't reasonably expect the Feldspar host environment to contain a complete system emulator for the target platform. I've left my FFI calls as undefined in my own code, but that is clearly wrong. There should be a way to provide a mockup (hi @josefs!) for testing, and I'm not sure the programmer should be forced to provide a Feldspar equivalent if they don't care about evaluation.

I'd like to avoid a monad at almost any cost because we don't handle them very well wrt code generation right now. If we have to go down the monad road I suggest to select the weakest monad possible for our purposes.

[josefs]

Regarding the monads. One option is to have two monads, Sys and M but provide a way to lift M-computations into Sys. That way there would be no need to duplicate the functionality of mutable references and arrays.

[emilaxelsson]

(Removed a comment about FFI semantics after realizing that we agree :-) )

@pjonsson wrote:

I'd like to avoid a monad at almost any cost because we don't handle them very well wrt code generation right now. If we have to go down the monad road I suggest to select the weakest monad possible for our purposes.

I'm open to suggestions. But we do need a way to generate interactive Feldspar programs, and the monadic machinery is already mostly in place (except perhaps that we need to make sure that the back end respects impure system calls). Note also that the use of the Sys monad is completely optional. If you don't need impure system calls, you can use Feldspar exactly as today.

[emilaxelsson]

@josefs wrote:

One option is to have two monads, Sys and M but provide a way to lift M-computations into Sys. That way there would be no need to duplicate the functionality of mutable references and arrays.

Yes, that's a good idea. But I think for common operations like getRef it might be worth making a simple wrapper interface so that you don't get too many lifts in the code.

I guess I'll go on making a Sys monad then, and we can tweak the exact interface later.

[pjonsson]

We do not have a backend that is sufficient to handle the monadic machinery for most practical purposes that we've seen so far. I'm not convinced that building more things on top of that machinery is going to somehow improve the state of the backend.

Elements deliberately side-stepped the monadic machinery and the backend had a much simpler problem to solve. Perhaps you can do something similar for the interactive programs you're trying to write? Can you tell us what program you're currently trying to write?

[emilaxelsson]

As a first step, I want to be able to read inputs and write outputs from/to some devices. I want to do this in a way that is not locked to a specific system or specific input/output resources. In the longer run, I would also like to be able to talk to the RTS for creating tasks, etc.

The idea of using a system monad for these kind of things is based on the fact that in the end we just want to produce C code that performs a sequence of calls with some pure computations in between. I think it was good to avoid a monad for the elements library, because it would make it harder to analyze the code, but I don't think this is so important at the system level.

I'd be happy to use something else than a system monad, but I'd like to avoid having to hack the compiler every time we want to target a new platform (or use a platform in a new way).

[pjonsson]

How sequential does your outputs need to be? It sounds like a Writer-ish monad might be enough. Are you implementing blocking reads? What is your definition of a task? We create tasks for parallell with Wool and the input program doesn't have to be monadic for that to work. Arguably it could be the same for the OpenMP backend, but those details are hidden inside the runtime system.

The effects on code generation from entering a monad are not completely local in our experience. The consequence is that programs that previously ran fine in a pure setting might be much slower when called from a monadic context, so that messes with the robustness to program changes property that we currently seem to have in practice.

Can you explain how a system monad would side-step the problem of having to port the compiler to new platforms?

[emilaxelsson]

Those are all good questions. But part of the point is that I don't want to make those decisions now. I'm just thinking about the underlying implementation machinery.

If we ignore parallelism for now, I basically just want to be able to read and write data. On host I may want to use fscanf and fprintf for this; on an embdded system I may want to use something else (don't ask me what).

A system monad and foreign calls would make this convenient, but maybe there are other options. The flexibility of supporting new architectures does not depend on the use of a monad per se, but on the fact that foreign calls can be added in separate libraries.

[emilaxelsson]

It seems that a much better approach is to add this system monad on top of existing Feldspar. This will give more flexibility and we can avoid making the compiler more complicated.

I've started working on this idea here: https://github.com/emilaxelsson/monadic-edsl

As far as I can see, we need two things from the Feldspar implementation for this to work:

• The ability to inject variables from a separate name space
• The ability to compile open expressions to snippets of inline C code

I think this can be done with relatively small effort.

[pjonsson]

I don't understand the first bullet, but it sounds like a syntactic-related issue. The second bullet I do understand. Those snippets will interact with our optimizer in the same way that unsafeCoerce/unsafePerformIO does with GHC's optimize, effectively being a barrier between expressions wherever they end up. That might or might not work, trying it out is the only way to know.

None of this matters though as long as we keep it off by default. Good luck!

[emilaxelsson]

A system program may look like this:

system = do
    inp <- getChunkFromSoundCard
    let outp = ifft $ window $ fft inp
    putChunkToSoundCard outp

In order to compile this, we need to (1) create a unique variable expression to pass to the fft, (2) ask the existing Feldspar compiler to compile the open expression ifft $ window $ fft inpVar, and (3) wrap the resulting C snippet with calls corresponding to getChunkFromSoundCard and putChunkFromSoundCard.

(1) and (2) are what I referred to in my previous message.

I don't think this will interfere with optimizations, because we're not interested in optimizing across system calls. But as you say, this monad will be completely optional, and the compiler will stay as it is, except that we may need to make sure it works in a situation where it just produces parts of the code. For example, we need to guarantee that variable 234 declared in the system monad has a predictable name in the generated C code when used in a Feldspar expression.