Support for Prolog and Haskell

Split from discussion in #483:

I'd like to see some effort made to map these use cases to the existing model and then evaluate what remains unsolvable or what remains inefficient. The use case of multiple return sites might relate to supporting a catch operation or exception handling, but not sure.

On 11/30/2015 01:45 PM, Frank McCabe wrote:

Both Prolog and Haskell pose challenges to the current design. In some
ways they also have a common requirement: a non-standard evaluation
resulting in a need for more control over the representation of evaluation.

In the case of Prolog, it has an evaluation 'stack' (quotes required)
that has two features not found in normal languages: a non-local return
(when a Prolog program ends, its return is not necessarily near on the
stack. However, that stack must still be preserved in order to support
backtracking.

The second feature is backtracking. What /that/ means is that there are
two separate ways in which a program can return: successfully or
unsuccessfully.

Does prolog compiled to machine code keep a separate binding stack? How far can you get using a separate stack except for the control transfer? Even translated C is expected to have a separate stack for argument passing beyond the fixed arguments.

In general, a good Prolog implementation needs a lot more explicit
control of its evaluation stack than languages Java/C++ do.

Haskell is a different case again. It's implementation has a number of
features that are very foreign to conventional languages. In the first
case, arguments are not evaluated prior to entry to functions. The
effect of this is that /all/ data looks like code. It also means that
the normal array mapping of an evaluation stack is not efficient for
Haskell.

This sounds like a higher level issue. Machine code does not support this anyway, so surely it is translated into more primitive operations. For example arguments might be pointers to data structures, and perhaps these need to include an index to a function and a context?

In the second, there can be multiple return points to a function call:
one where the result is represented as a single value, and one or more
where the return result is 'postponed' with the components of the return
value spread across multiple registers.

Can this be handle by a single return site using multiple values (which are to be supported). The first value might be an index to dispatch to different range of return paths?

...

One additional remark: the kind of structures needed to support Haskell
and Prolog are also very good for supporting so-called asynchronous
programming. So, even JavaScript and C++ could benefit from these
techniques.

But they are compiled to machine code anyway, and machine code does not have specific support for 'asynchronous programming'. What we need to know is if the AST can efficiently support the primitive operations needed.

Supporting Prolog

1. A function can be 'returned to' more than once. This is a little like call/cc in scheme; but the current fixation on the function as the unit of evaluation is broken by this. The Prolog stack is significantly richer than the evaluation stack in most languages in order to support this. Note that, unlike call/cc, the continuation in Prolog is not reifiable.
2. Prolog has a deep need for variable-variable dereferencing. A memory reference may not have the actual value but a pointer to the actual value. In some systems, this accounts for 30-40% of all CPU cycles in a Prolog application.
3. The normal half-space based GC algorithms don't work well with Prolog because efficient backtracking relies on knowing the order of allocation.

It is normal in Prolog, for the garbage collector to also collect the stack. The cut operator in Prolog results in garbage stack entries.

Supporting Haskell
Note: I am not an expert of this.

1. The multiple return points can be approximated to by returning a sentinel and branching; but at substantial performance cost. Such a system could not claim to support Haskell natively.
2. Tail recursion. The tail-call should not be required to make assumptions about the tail call having the same number of parameters etc as the parent call. In many many cases in functional languages, it will not look the same.
3. Non-linear evaluation stack. The normal lazy evaluation mode of Haskell makes implementation on a stack very difficult. As far as I know, the Haskell compiler tries to map evaluation on to the stack but usually fails and ends up with a heap allocated stack.

[pizlonator]

On Nov 29, 2015, at 8:46 PM, Frank McCabe notifications@github.com wrote:

Supporting Prolog

A function can be 'returned to' more than once. This is a little like call/cc in scheme; but the current fixation on the function as the unit of evaluation is broken by this. The Prolog stack is significantly richer than the evaluation stack in most languages in order to support this. Note that, unlike call/cc, the continuation in Prolog is not reifiable.
What is the low level feature that you need? Is it multiple function entrypoints?

Note that nothing prevents a prolog implementation on the web to heap-allocate stack-like data structures and use those as the high level stack. If a prolog implementation did this when generating to C code, how much worse would it be - in terms of overall benchmark performance - than an implementation that targets machine code and does something more clever?

Prolog has a deep need for variable-variable dereferencing. A memory reference may not have the actual value but a pointer to the actual value. In some systems, this accounts for 30-40% of all CPU cycles in a Prolog application.
In what way is the desired machine code different from what a C compiler would generate if you expressed this using C?
The normal half-space based GC algorithms don't work well with Prolog because efficient backtracking relies on knowing the order of allocation.

It is normal in Prolog, for the garbage collector to also collect the stack. The cut operator in Prolog results in garbage stack entries.

Any GC features for wasm need to be compatible with the GC semantics of the web. It's not clear that what you describe would be compatible.

Nothing prevents a custom GC implementation using linear memory.

Supporting Haskell
Note: I am not an expert of this.

The multiple return points can be approximated to by returning a sentinel and branching; but at substantial performance cost. Such a system could not claim to support Haskell natively.
Tail recursion. The tail-call should not be required to make assumptions about the tail call having the same number of parameters etc as the parent call. In many many cases in functional languages, it will not look the same.
Non-linear evaluation stack. The normal lazy evaluation mode of Haskell makes implementation on a stack very difficult. As far as I know, the Haskell compiler tries to map evaluation on to the stack but usually fails and ends up with a heap allocated stack.
—
Reply to this email directly or view it on GitHub.

What is the low level feature that you need? Is it multiple function entrypoints?

A Prolog program simply does not correspond to a regular function. An exit from a Prolog program cannot be handled like a normal function return; and the corresponding call has more to do than a regular function call.

Mapping this to C results in either extremely voluminous code or, more likely, an extra layer of interpretation. Most decent Prolog systems do not compile to C.

In some systems, this accounts for 30-40% of all CPU cycles in a Prolog application.

In what way is the desired machine code different from what a C compiler would generate if you expressed this using C?

The key here is that you will get what looks like a type violation to the verifier. A pointer to a value may be a pointer to a pointer to a value or a pointer to a pointer to a pointer to a value; or it may just be a value.

Compiling via C inevitably results in a substantial performance loss.

A couple of places you say that one can just allocate a chunk of linear memory and play with it. This is true. But you cannot simultaneously use that as the preferred strategy and claim universality.

An extreme example might illustrate: you can map all C programs to Haskell. One could then claim that, given an efficient Haskell implementation, you also have an efficient implementation of C and you have universality. I would doubt many people would accept that.

On the other hand, it is not required to support either Prolog or Haskell. Just don't claim universality in that case.

Some other languages that also have non-standard execution models include SQL, Scheme, Ruby, ...

[kripken]

Nothing prevents a custom GC implementation using linear memory.

Just wanted to note that I think this is going to be common. There are just too many different GC models, no single VM can support them all (another example is languages that need GC finalizers, which JS lacks), and that's fine. The others can be implemented on top of linear memory (+ threads), with close to native speed.

[kripken]

A couple of places you say that one can just allocate a chunk of linear memory and play with it. This is true. But you cannot simultaneously use that as the preferred strategy and claim universality.

I don't think we are claiming strong universality in that sense. It's never been achieved, and is likely just not possible.

Is WebAssembly's main goal to act as an assembler for JavaScript? I thought that we already had a wide-spread implementation of JS.

I also thought that the initial goal was to be able to compile arbitrary C programs for distribution in browsers.

I guess that I was upping the ante a little. I think that there is the potential for a universal assembler.

[sunfishcode]

WebAssembly's goals are spelled out here. The initial focus (MVP) is indeed on C/C++, but it is also very much the intent to "up the ante" beyond that and add support for many other kinds of languages.

The FutureFeatures.md document is a list of some possible ideas (including fully general tail calls), and other ideas are possible too. It's not meant to be a comprehensive list; new ideas are welcome.

For Haskell, a good starting point for exploration might be the GHC LLVM backend. What special features of LLVM does it depend on? What are its weaknesses?

Closing as nothing specific enough has been identified, and if identified then it seems more appropriate to open new specific issues.

[ron-wolf]

Core

I’m surprised that Core hasn’t been brought up with respect to Haskell.

Another target

Our goal should not be to compile Haskell to WebAssembly, but rather to compile Core to WebAssembly. The Haskell compiler GHC already compiles Haskell to Core, which is smaller and easier to work with but still portable. Haskell has already been compiled via Core to assembly (using GHC) and JVM bytecode, so I don’t see why we couldn’t do something similar for WebAssembly.

GHC does even more work

We could even go further and intercept GHC later in compilation. For instance, GHC already compiles Core to the slightly simpler Spineless Tagless G-machine. It then converts STG code to a dialect of C--, at which point even function calls have been stripped away. See GHC § Architecture at Wikipedia for a holistic explanation.

Just make it possible

Of course, the WebAssembly team need only take the design of Haskell’s compilation system into account. Someone else can write the compiler; we just need to make sure WebAssembly is a suitable target for such a compiler while remaining relatively small and efficient. In all likelihood, it already is, considering how much work GHC already does to compile Haskell to lower-level languages.