Looking for a list of small (or not?) miniML dialects

Community
1

I’m preparing a list of dialect of ML that could be gives as an exercise to student for implementation. (The current plan is to give a typechecker for miniML, and they will implement an extension + interpreter).

I’m collecting a list of possible extensions of miniML that could fit here. I can’t remember all possible extensions, could you help?
(If you think that an extension is too complicated to implement, I wish you to mention it anyway).

  1. algebraic data types
  2. polymorphic variants (normal or set-theoretic)
  3. active patterns from F#
  4. lazyness a la Haskell
  5. type classes (minimal)
  6. objects with mutable fields and methods
  7. algebraic effects
    • Looks complicated, but last year a pair of students managed to implement something workable
  8. typed effects (a la Leo White talk)
    • looks complicated but a minimal implementation isn’t
  9. assignment, optional and default arguments
  10. equality types from SML + value restriction
  11. mini-Gallina (should not be too complicated but I didn’t try)
    • a restriction to make algebraic types inductive
    • a checker that functions are structurally recursive over an argument
  12. GADT (a suicidal task)
  13. delim/cc (another suicidal variant)
    • AFAIR typing in OchaCaml is mysterious, because type of variables could change during execution
1 Like
2

  • Compiling pattern-matching is non-trivial and interesting; you could ask them to translate deep pattern matching into just shallow pattern matches (all subpatterns are variables or wildcards) before interpretation.

  • Easier than GADTs, existential types. (Not much to do on the interpreter side.)

  • One extension that is easier than delim/cc or effect handlers is to support angelic non-determinism with choice : 'a list -> 'a (choice [] is a failure).

  • Unification and unification variables :slight_smile:

1 Like
3

Some ideas:

  • JIT compilation.
  • Incremental execution ala Facebook’s Skip.
  • Unboxed tuples.
  • Parallelism.
  • An IDE.
  • Typeset code, i.e. a graphical front-end.

Are you after type system extensions specifically or anything that might make a better tool?

4

I think no one has mentioned 1st class modules yet (presumably in the F-ing encoding).

5

Back in the day, I really enjoyed writing a Prolog interpreter using @ddr 's call/cc hack in caml-light. Boy howdy that was fun. I think that might make a nice exercise for your students, once they implement call/cc and use that to implement shift/reset.

6

Thanks for an idea about call/cc and delim/cc but here I’m currently looking for miniML extensions. I have other topics about language implementation, which include Scheme+call/cc, Scheme+delim/cc, BQN, etc.

I thought about this, but I think it is too comlicated. I have troubles understanding 1ML paper. Despite it should look simlier than OCaml modules, it looks like more bizzare. Also, It seems that it need System-F in type system. Maybe, I should invent a task that should “upgrade” HM type inference to non-prenex System-F one?.. I’m not sure… Looks complicated.

Thanks for your ideas, but in this thread I’m looking for langugage extensions. I will write down your ideas in another list of tasks