<script type="text/javascript">
WebAssembly.instantiate(new Uint8Array([
0,97,115,109,1,0,0,0,1,8,2,96,1,127,0,96,0,0,2,7,1,1,105,1,
102,0,0,3,2,1,1,7,5,1,1,101,0,1,10,8,1,6,0,65,42,16,0,11]),
{i:{f:x => alert(x)}}).then(x => x.instance.exports.e());
</script>
WebAssembly
Click below to compile an expression to WebAssembly and run it.
wasm:
Available operators:
abs neg ceil floor trunc nearest sqrt +  * / min max copysign
The wasm binary format
We walk through a small standalone wasm binary.
We open with the 4byte magic string "\0asm", then the 4byte version, which is 1 in littleendian:
00 61 73 6d 01 00 00 00
Apart from this version number, WebAssembly encodes integers with LEB128, using the signed variant when appropriate. We shall refer to the encoded numbers as varuints and varints.
The numbers in our example are small enough that a varint or a varuint can be thought of as a byte (holding a number between 0 and 127, or 64 and 63).
A number of sections follow the first 8 bytes. Each section begins with a varuint for the section ID, followed by a varuint for the length of the section.
Section 1 declares the types of function signatures. We’ll export a function e for JavaScript to call, and import a function f from the import object i through which it returns a 32bit integer.
The type signature of the imported function is:
60 ; Function. 01 ; One input. 7f ; 32bit integer (i32). 00 ; No outputs.
and the type signature of the exported function is:
60 ; Function. 00 ; No inputs. 00 ; No outputs.
Thus the entire type section is:
01 08 ; Type section follows. It's 8 bytes long. 02 ; Two type signatures follow. 60 01 7f 00 60 00 00
Section 2 declares imports. We declare an import object i containing one function f mentioned above. A string is encoded with a varint holding its length followed by the string contents.
02 07 ; 7byte import section. 01 ; One import. 01 69 ; The string "i". 01 66 ; The string "f". 00 ; Function. 00 ; Index of signature in section 1.
Section 3 declares signatures of the functions defined in section 10.
03 02 ; 2byte function section. 01 ; One signature. 01 ; Index of signature in section 1.
Section 7 declares exports:
07 05 ; 5byte export section. 01 ; One signature. 01 65 ; The string "e". 00 ; Function. 01 ; Function index.
Functions are numbered from 0, so function index 1 refers to the second function. The first function mentioned was the function in section 2, and the second function mentioned is the function in section 3. In general,
if there are \(m\) functions in section 2 and \(n\) functions in section 3, then the function index \(k\) will lie in \([m..n  1]\) and refer to the \((k  m)\)th function of section 3.
Section 10 holds the code. Here, we define the body of our exported function, which calls the imported function with the constant 42 (0x2a).
0a 08 ; 8byte code section. 01 ; One function body. 06 ; Length of function body. 00 ; No local variables. 41 2a ; Encoding of "i32.const 42". 10 00 ; Call function 0. 0b ; End of code.
We can put this altogether in an HTML snippet that uses WebAssembly to show "42" in an alert:
Parser
We modify a grammar from another demo so it accepts Haskellstyle expressions: application associates to the left and functions are curried. For example, min 4 3, the minimum of 4 and 3, is interpreted as (min 4) 3, and 1 + 2 is translated internally to ((+) 1) 2.
var ::= ('a'..'z''A'..'Z')+ num ::= ('0'..'9''.')+ factor ::= [''] ( var  num  '(' expr ')' )+ term ::= factor ( ('*''/') factor )* expr ::= term ( ('+''') term )* line ::= expr EOF
We parse an expression into simplified version of the data structure we used to hold lambda calculus terms. A leaf node either holds a double constant, or a string representing a primitive function. All internal nodes represent function application. Lambda abstraction is absent.
{# LANGUAGE CPP #}
{# LANGUAGE OverloadedStrings #}
#ifdef __HASTE__
import Haste.DOM
import Haste.Events
import Haste.Foreign
import Data.List.Split
import Numeric
import System.IO.Unsafe
#else
import Data.ReinterpretCast
#endif
import Data.Char
import Text.ParserCombinators.Parsec
data Expr = D Double  V String  App Expr Expr
line :: Parser Expr
line = spaces >> expr >>= (eof >>) . pure where
eat :: Parser a > Parser a
eat p = p >>= (spaces >>) . pure
var = eat $ V <$> many1 letter
num = eat $ D . read <$> many1 (digit <> char '.')
tok = eat . string
una = option id (tok "" >> pure (App (V "neg")))
fac = una <*> (foldl1 App <$> many1
(var <> num <> between (tok "(") (tok ")") expr))
term = fac `chainl1` ((tok "*" >> bin "*") <> (tok "/" >> bin "/"))
expr = term `chainl1` ((tok "+" >> bin "+") <> (tok "" >> bin ""))
bin s = pure $ \a b > App (App (V s) a) b
Compiler
Our compiler generates the above example with two changes:

Our import function expects a doubleprecision floating point input (f64) instead of a 32bit integer.

Our function body consists of a translation of the given expression instead of the constant 42.
Rather than simply dump a wall of bytes, we write some helper routines to output them so the structure of a wasm binary is apparent.
toAsm e = concat [
[0, 0x61, 0x73, 0x6d, 1, 0, 0, 0],  Magic string, version.
 Type section.
sect 1 [encSig ["f64"] [], encSig [] []],
 Import section.
 [0, 0] = external_kind Function, index 0.
sect 2 [encStr "i" ++ encStr "f" ++ [0, 0]],
 Function section.
 [1] = Type index.
sect 3 [[1]],
 Export section.
 [0, 1] = external_kind Function, index 1.
sect 7 [encStr "e" ++ [0, 1]],
 Code section.
 0 = local variable count.
 [0x10, 0, 0xb] = call function 0, end of code.
sect 10 [lenc $ 0 : compile [] e ++ [0x10, 0, 0xb]]]
lenc xs = length xs : xs
sect t xs = t : lenc (length xs : concat xs)
encStr s = lenc $ ord <$> s
encType "i32" = 0x7f
encType "f64" = 0x7c
encSig ins outs = 0x60  Function type.
: lenc (encType <$> ins) ++ lenc (encType <$> outs)
No type checking is performed, though this is easy to add. Thus the only nontrivial task is compiling the expression to assembly.
Wasm is stackbased, so for each operator:

We recursively compile the subtrees for each of its operands (from left to right), so when executed, the operaands will be on top of the stack.

We output the opcode corresponding to the operator.
We place the arity and opcodes for all the f64 operators in an associative list, which suffices for our simple demo.
In wasm, the 8 bytes of a double are encoded in littleendian. Normally, we can take care of this in Haskell with, say, the Data.ReinterpretCast package but Haste lacks support for the relevant Haskell primitives. For the Haste version, we use JavaScript to get at the bytes representing a double:
<script type="text/javascript">
function fromDouble(d) {return new Uint8Array(new Float64Array([d]).buffer);}
</script>
We wrap it in unsafePerformIO so we can use it as a pure function.
f64una = zip (words "abs neg ceil floor trunc nearest sqrt") [0x99..]
f64bin = zip (words "+  * / min max copysign") [0xa0..]
ops =
((\(x, b) > (x, (1, b))) <$> f64una) ++
((\(x, b) > (x, (2, b))) <$> f64bin)
compile m e = case e of
App a b > compile (b:m) a
#ifdef __HASTE__
D d > 0x44 : map fromIntegral (doubleToBytes d) where
doubleToBytes :: Double > [Int]
doubleToBytes = unsafePerformIO . ffi "fromDouble"
#else
D d > 0x44 : map fromIntegral
[doubleToWord d `div` (256^i) `mod` 256  i < [0..7]]
#endif
V s > case lookup s ops of
Nothing > error $ "bad op: " ++ s
Just (a, b) > concatMap (compile m) (take a m) ++ [b]
User Interface
For the web version, we compile a given expression, dump the assembly in a textarea element, and run the assembly which calls a function that shows the result on the page:
<script type="text/javascript">
function runWasmInts(a) {
WebAssembly.instantiate(new Uint8Array(a),
{i:{f:x => Haste.setResult(x)}}).then(x => x.instance.exports.e());
}
</script>
For the commandline version of the program, we compile a predefined program.
#ifdef __HASTE__
dump s = unlines $ unwords . map xxShow <$> chunksOf 8 s where
xxShow c = reverse $ take 2 $ reverse $ '0' : showHex c ""
main = withElems ["input", "output", "asm", "evalB"] $
\[iEl, oEl, aEl, evalB] > do
let
setResult :: Double > IO ()
setResult d = setProp oEl "innerHTML" $ " = " ++ show d
export "setResult" setResult
evalB `onEvent` Click $ const $ do
setProp oEl "innerHTML" ""
ee < parse line "" <$> getProp iEl "value"
case ee of
Left m > do
setProp aEl "value" ""
setProp oEl "value" $ "parse error: " ++ show m
Right e > do
let asm = toAsm e
setProp aEl "value" $ dump asm
ffi "runWasmInts" asm :: IO ()
#else
main = print $ toAsm e where Right e = parse line "" "min (sqrt 8) 2"
#endif