Personal tools

Yhc/Erlang/Proof of concept

From HaskellWiki

< Yhc(Difference between revisions)
Jump to: navigation, search
(forcing expressions)
(CAFs)
Line 98: Line 98:
 
====Thunks====
 
====Thunks====
   
Thunks, or delayed function calls, are tagged with atom ''@ap''.
+
Thunks, or delayed function calls, are tagged with atom ''@ap''. Below, possible types of thunks, and their evaluation logic are discussed.
  +
  +
General structure of an application thunk is as follows:
  +
  +
<code>
  +
{'@ap', Func, Arity, Args}
  +
</code>
  +
  +
''Func'' may be a 2-tuple directly identifying a function, or some expression that may evaluate to a function. ''Arity'' is usually 1 for partial and oversaturated applications, otherwise it is an arity of a function involved in a saturated call. ''Args'' is a list (in Erlang sense) of arguments.
  +
  +
* Saturated application (''Arity'' == length (''Args'')): <code>erlang:apply</code> is called upon ''Func'' and ''Args''; result is forced again.
  +
  +
* Oversaturated application (''Arity'' == 1, length (''Args'') > ''Arity''): ''Func'' is applied to the head of ''Args'', the result is applied to the remainder of ''Args'', etc. (also known as [www.haskell.org/~simonmar/papers/eval-apply.pdf Eval-Apply] evaluation strategy). Only curried versions of functions may be involved (of arity 1); thus partial application is simply impossible.
  +
  +
* Partial/oversaturated application of n-ary function: should not occur.
  +
  +
====CAFs====
  +
CAFs (nullary functions) are tagged with atom ''@caf'' and structured as follows:
  +
  +
<code>
  +
{'@caf', Module, Function}
  +
</code>
  +
  +
If a CAF is part of function application, it is called first, and whatever is returned, is evaluated again (this may be another CAF, or a function). Then the application is processed as described above.
  +
   
 
====Data constructors====
 
====Data constructors====

Revision as of 03:46, 16 May 2008

Contents


1 Introduction

This Wiki article describes an experiment targeting execution of Haskell programs on top of the Erlang Virtual Machine (BEAM). Haskell source code is compiled to Yhc Core with York Haskell Compiler (Yhc), then the program further discussed converts Yhc Core to Core Erlang; finally Erlang Compiler (erlc) compiles Core Erlang to the BEAM file format which can be loaded and executed by the Erlang VM.

There have been numerous discussions about Haskell (mainly GHC) runtime lacking some properties that are available in Erlang environment, as well as about possible improvements in Erlang language syntax and type system to bring some elements available in Haskell.

This experiment is an attempt to answer the critics from both sides. Once it becomes possible to execute Haskell programs in Erlang environment, Haskell users get access to the robust concurrency-oriented runtime, still being able to use Haskell native syntax. Erlang users get possibility to develop some algorithms with regard to the Haskell strong type system, while still being able to code directly in Erlang, where it seems more appropriate implementation-wise.

2 Implementation details

This section discusses in deep the approach taken in this experiment. It is good to remember that nothing yet is final; some of the techniques described may possibly make it into the mainstream code, while others may not. This is only the beginning.

2.1 Core Erlang overview

The Core Erlang initiative project is a "collaboration between the High-Performance Erlang (HiPE) project at the Department of Information Technology of Uppsala University, and Ericsson's OTP/Erlang developers".

Core Erlang is an intermediate form of Erlang source compilation. It provides a desugared (compared to Erlang) syntax of a strict functional language. Erlang source may be compiled to Core Erlang, and Core Erlang may be compiled to BEAM bytecode.

Core Erlang plays the same role in the Erlang compilation process as Yhc Core in the Haskell (Yhc) compilation process. So, it turns out to be the most convenient to do the conversion between these formats rather than between e. g. Haskell source and Erlang source.

There was an attempt made earlier to do similar things, only converting from Haskell source (indeed, a subset of Haskell syntax) to Core Erlang. This project is called Haskerl, developed by Torbjörn Törnkvist, (not to be confused with Will Partain's Haskerl. Some source code from Haskerl was used in this experiment, in particular, the algebraic data type to represent Core Erlang internally, and the pretty printer module for Core Erlang, both with some necessary extensions.

The whole compilation chain looks like this:

  1. Haskell source modules are compiled into Yhc Core and linked;
  2. Some overall program optimizations (functionality provided with the Yhc Core library) are performed on the linked Yhc Core;
  3. Yhc Core is converted to Core Erlang;
  4. The Erlang compiler erlc produces a BEAM file.

2.2 Haskell on BEAMs ;)

From the Erlang VM standpoint, a Haskell program is just a large(ish) Erlang module. To run the program, certain function exported from that module (usually,
main
) needs to be called with arguments as necessary. Often the special force function has to be applied to values returned from Haskell-originated module: otherwise some unfinished computation may be returned instead of the expected result.

From Haskell program standpoint, Erlang VM is just an execution environment providing system calls that are strict on all their arguments, and may have variable number of arguments. Haskell program may spawn concurrent processes able to receive messages of certain types (the idea of typed processes was borrowed from this Livejournal article (in Russian). The message distribution/transport mechanism is entirely provided by the Erlang VM runtime.

2.3 Lazy computations

Erlang is a strict language. This means that functions always evaluate their agruments, and values get passed around already computed. In Haskell, due to its lazy/non-strict nature, some values are passed around un-evaluated, and may be evaluated later as needed (or never at all). "Traditional" implementation of Haskell runtime often combine non-strict evaluation with memoization which serves to avoid redundant evaluation of the same value several times.

However memoization is not possible when compiling Haskell into (Core) Erlang because of Erlang's single assignment nature. Once created, objects in Erlang are immutable (with few exceptions that are of no value in this experiment). As alternative to memoization, the following approach, based on strictness analysis is used.

The Yhc Core Strictness Analyzer is able to determine whether a function is strict on some (or none) of its arguments. This is done via analysis from the bottom up, with OS/platform primitives (usually assumed strict on all arguments, and the same applies to Erlang primitives). If a function passes its argument to another function which will evaluate it, the former function is also strict on that argument. If a function unconditionally evaluates its argument as a case statement scrutinee, it is also strict on that argument, and this strictness propagates to other functions which call it.

After Yhc Core is linked and optimized, strictness analysis is run on it. All Erlang primitives (see below about possible ways to call Erlang functions from Haskell) are considered strict on all arguments (and they naturally are). If a function is determined to be strict on some of its arguments, for each such argument a code is inserted into the function's body to make sure these arguments will be evaluated as early as possible, and will be passed around evaluated. While this does not replace memoization, it is expected that such approach will at least eliminate some redundant computations.

Another consequence, for functions with side effects involved in sequential computations, the runtime implementation must carefully observe that already computed value is passed to the continuation, rather than an unevaluated thunk, since repeated evaluation of the thunk results in repeated side effect.

2.4 Haskell objects

This section describes Erlang data structures used to represent objects visible to Haskell programs.

2.4.1 Functions

Each Haskell (or, more precisely, Yhc Core) function is translated to corresponding Core Erlang function. Names of functions are not generally preserved. Functions that are exported (expected to be called by Erlang code) keep their names with module name stripped off(remember that Yhc Core file is linked from multiple individual Core files), and some characters replaced (such as primes as they are used in Core Erlang to quote atom names) with underscores. Functions not to be exported are given unique numeric identifiers prepended with dot (.) to form valid Erlang atom names. Thus, for example the
Prelude.map
function is translated from this Yhc Core representation:
Prelude;map v22178 v22179_f =
    let v22179 = _f_ v22179_f
    in let v22179_c = _f_ v22179
       in case v22179_c of
              Prelude;[] -> Prelude;[]
              (Prelude;:) v22180 v22181 ->
                  (Prelude;:) (v22178 v22180) (Prelude;map v22178 v22181)

to this Core Erlang representation:

'.56'/2 =

 fun (_v22178,_v22179_f) ->
   let <_v22179> =
     <call 'hserl':'force'(_v22179_f)>
     in let <_v22179_c> =
     <call 'hserl':'force'(_v22179)>
     in case <_v22179_c> of
     <{'@dt','.EOL'}> when 'true' ->
       {'@dt','.EOL'}
     <{'@dt','.CONS',_v22180,_v22181}> when 'true' ->
       {'@dt','.CONS',{'@ap',_v22178,1,[_v22180|[]]},{'@ap',{'hs_test1','.56'},2,[_v22178|[_v22181|[]]]}}
   end

The code above also shows how some other Haskell objects are represented in Core Erlang.

The function interface shown above (with arity in Core Erlang equal to arity in Yhc Core) is used for saturated calls. For partial and oversaturated function applications, however a slower but more flexible curried interface (of arity 1) is provided:

'.56_c'/1 =

 fun (_v22178) ->
   fun (_v22179_f) ->
     call 'hs_test1':'.56'(_v22178,_v22179_f)

This function, if applied to one argument, returns another function of one argument, which in turn calls the "target" function with both arguments.

Names of curried functions are formed by appending _c to the name of the target function.

2.4.2 Forcing evaluation of Haskell expressions

Non-function Haskell objects are represented using Erlang tuples, tagged with the first member, an atom. The runtime support module (written in Erlang) provides the force/1 function that is called every time a Haskell expression needs to be evaluated (see example og the
map
function above when hserl:force is called upon a case scrutinee variable. For expressions already evaluated, force/1 returns its argument as supplied, but in some cases it will actually evaluate its argument, and return a computed value.

2.4.3 Thunks

Thunks, or delayed function calls, are tagged with atom @ap. Below, possible types of thunks, and their evaluation logic are discussed.

General structure of an application thunk is as follows:

{'@ap', Func, Arity, Args}

Func may be a 2-tuple directly identifying a function, or some expression that may evaluate to a function. Arity is usually 1 for partial and oversaturated applications, otherwise it is an arity of a function involved in a saturated call. Args is a list (in Erlang sense) of arguments.

  • Saturated application (Arity == length (Args)): erlang:apply is called upon Func and Args; result is forced again.
  • Oversaturated application (Arity == 1, length (Args) > Arity): Func is applied to the head of Args, the result is applied to the remainder of Args, etc. (also known as [www.haskell.org/~simonmar/papers/eval-apply.pdf Eval-Apply] evaluation strategy). Only curried versions of functions may be involved (of arity 1); thus partial application is simply impossible.
  • Partial/oversaturated application of n-ary function: should not occur.

2.4.4 CAFs

CAFs (nullary functions) are tagged with atom @caf and structured as follows:

{'@caf', Module, Function}

If a CAF is part of function application, it is called first, and whatever is returned, is evaluated again (this may be another CAF, or a function). Then the application is processed as described above.


2.4.5 Data constructors

2.4.6 Special cases

2.5 Haskell calling Erlang

2.5.1 General calling convention

2.5.2 Primitive calls

2.5.3 Hardcoded BIFs

2.6 Erlang calling Haskell

2.7 Typed processes

2.7.1 Spawning processes

2.7.2 Receiving messages

2.7.3 Sending messages

3 Examples

Sample code to demonstrate results of the experiment was checked into the Yhc Darcs repo. Haskell and Erlang sources as well as compiled BEAM files are located at http://darcs.haskell.org/yhc/src/translator/erlang/00proof/ .

3.1 Factorial

3.2 Merging lists

3.3 Ping-pong