Skip to content
Implementation of type classes and ad-hoc polymorphism
Haskell OCaml
Branch: develop
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
app Add: Enable to convert from Source syntax Nov 13, 2019
src
test
.gitignore Change: Rename the project Nov 14, 2019
.travis.yml Fix: Install ocaml in CI Nov 14, 2019
ChangeLog.md Initialize Project Oct 23, 2019
LICENSE
README.md Add: Add a bibliography in README Nov 17, 2019
Setup.hs
env.yaml Change: Update env.yaml Nov 14, 2019
package.yaml Change: Store literal type mapping in Array Nov 15, 2019
stack.yaml Add: Implement environment-related things Oct 25, 2019
stack.yaml.lock Add: Implement environment-related things Oct 25, 2019

README.md

ad-hoc-poly

Travis

ad-hoc-poly is an implementation of ad-hoc polymorphism and type classes.

Try it out

ad-hoc-poly works as a transpiler to OCaml. There are two source languages named mlx1 and mlx2.

To see how this works, save the code below as sample.mlx2:

class<T> Num {
  add :: T -> T -> T,
  mul :: T -> T -> T,
  neg :: T -> T,
} in
impl Num<Int> {
  add = add_int,
  mul = mul_int,
  neg = neg_int,
} in
impl Num<Float> {
  add = add_float,
  mul = mul_float,
  neg = neg_float,
} in
let square = \x. mul x x in
let x = add (square 3) (int_of_float (square 2.7)) in
print_int x

And perform translation with:

stack run mlx2 -- sample.mlx2

You can find more examples under test/data. Also, you can configure the type environment by editing env.yaml. Enjoy!

Two languages

mlx1

mlx1 is a language with overloadings. A type-directed translation pass resolves overloadings and compiles mlx1 into well-typed OCaml code.

mlx2

mlx2 is a language with type classes. mlx2 is desugared to mlx1.

FAQ

Q. Is "default implementation" supported in this implementation?

A. Currently, No.

See #1.

Q. I don't want to enter non-ascii symbols such as or λ

A. You can use forall for and \ for λ and Λ.

Q. Is this implementation proven to be correct?

A. No.

Q. Why is mlx2 syntax designed to look like Rust's traits, but not Haskell's type classes?

A. To separate two compilation phases.

To perform the dictionary conversion, it is needed to identify each class declaration.

class and instance declarations take type expressions to represent constraints and instantiations in Haskell-like syntax. Thus, a type evaluation is required to identify the class declarations. I don't want this because the translation from mlx1 to OCaml also requires type evaluation.

class and impl declarations in mlx2 syntax take class names as a simple identifier and I can implement dictionary conversion easily because of it.

Q. Is it necessary to introduce type-level lambda like this implementation to implement ad-hoc polymorphism?

A. No.

Haskell is one of the major conterexamples.

Q. Is it feasible to implement this in one-pass?

A. Yes.

I've implemented this as two-pass compilation just for simplicity.

Q. Does this implementation support higher-kinded types (HKT)?

A. No.

AFAIK, higher order unification is required to introduce HKT in a system with type lambdas. To keep simplicity, I didn't implemented that.

Bibliography

  • Wadler, Philip, and Stephen Blott. "How to make ad-hoc polymorphism less ad hoc." Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, 1989.
You can’t perform that action at this time.