Transcript Haskell.NET - Microsoft Research

Haskell.NET
The Art of Avoiding Work
Oliver Hunt & Nigel Perry
University of Canterbury, New Zealand
Summary
Introduction
 Background
 Prior Art
 Challenges & Solutions
 Results
 The Future
 Questions

Introduction: What?

Implementation of Haskell 98 on
Rotor/.NET
Haskell is one of the worlds most popular
functional programming languages.
 How to compile Haskell for .NET is still a
research problem

• Can it be done “reasonably”?
• Would IL changes provide “worthwhile”
benefit:cost?
Introduction: Haskell
Well known
 Used in industry and academia
 Non-strict
 Glasgow Haskell Compiler (GHC)

Provides intermediate-level output to support
new backends
 Extends Haskell 98 – providing future
avenues of research

Introduction: Why?

Different language families are suited to
different tasks


This adds a non-strict functional language to
the languages available on .NET
To test the extent to which .NET can run
many languages.

Primarily used by object oriented imperative
languages.
Prior Art: Bridges
The functional language runs natively on
the real machine
 A software bridge is provided to the VM
 Examples:

Lambada (Haskell for JVM)
 Hugs.Net (Haskell for .NET)

Prior Art: New Languages

Designed to work on the VMs




Reduced features
Mixed compile/interpretive approaches
More OO-like type systems
Examples:

Pizza (JVM)
• Strict
• Introduced parametric polymorphism to JVM

Mondrian (.NET)
• OO-like type system
• Used a mixed compiled/interpretive approach
• Targeted at scripting applications
Haskell 98 on .NET: Challenges
Non-strict evaluation
 Functions as values
 Partial evaluation/“currying”
 Type switches

Challenge: Non-strict Evaluation

Mondrian: “External” non-strictness

Client must know
• Manual evaluation


Interpretive-like
JIT Objects: “Internal” non-strictness

Non-strictness hidden from client
• Automatic evaluation

Doesn’t support disjoint union types well
• Disjoint union types central to Haskell 98…
Haskell.NET: Non-strict Evaluation

Use “Internal” non-strictness


Primitive types




Best for interworking
Follow JIT Objects
Optimise to use single class, rather than
type/subtype combination
Auto conversion to/from values & boxed values
Function types

Use hidden nested subtype
Non-strict Evaluation (cont)

Disjoint union types



Type: abstract class
Alternatives: sub-classes
Discrimination:
• use tag fields

Resolution:
• “asX” methods rather than casting

Non-strictness
• Hidden sub-class
• Internal: evaluation hidden by tag/asX

Issues:


Casting only works for evaluated values
Not totally transparent
• But disjoint unions not “standard” OO
Non-strict types

data List a = Cons a (List a) : Nil
Challenge: Functions as values


.NET provides delegates, which are “OO function
pointers”
Unfortunately:



Relatively inefficient given the high usage in Haskell
Difficult to combine with non-strictness
Replace using a parametric function type



Provide conversions to/from delegates for inter-language
working
Extends to support partial application
Might extend to support higher-rank types (Glasgow extension)
Challenge: Partial Evaluation

Calling a function omitting arguments, to
create a new function, e.g.
Inc x = x+
 Calling (inc 3) returns a function that adds 3
to its argument


We extend our previous function type

Instance fields used to store pre-supplied
arguments
Challenge: Type Switches

Very slow in .NET
Must use a series of type checks/casts
 These checks take account of subtypes


Addressed by the addition of an explicit
tag enumerand to each type. I.e:
Effectively duplicate the hidden VM tag
 Do exact, as opposed to subtype, matching

Status

Compiler functional

But incomplete…
• Large %age of Haskell 98 language
• Smaller %age of Haskell 98 libraries
• Largely engineering, not research, left

Performance?

Primes Sieve (first 1000 primes)
• GHC Native: 0.9s
• GHC .NET: 1.5s
Future Work: Glasgow Haskell

Higher Rank Types


Passing generic functions as values
Partly supported now:
• Wrap inside interface

Higher Kind Types


E.g. allow M<X> where both M & X are variable
How to do reasonably efficiently in .NET?
• Fallback is reflection/runtime code generation…

Currently by-passed (e.g. hardwire Monad to IO)
Future Work: IL Changes?

Compared to “native” implementation:
More classes – adds VM load
 Some extra indirections – a runtime cost
 Virtual dispatch for tag checking
 Etc.


Investigate if IL changes would:
Provide Haskell a good benefit:cost
 Benefit other languages

Demo

It really does work…
Q & (maybe) A