Gergő Érdi

One drawback of the Hindley-Milner type system is that its typecheckers are necessarily non-compositional. The basic idea here is that this can result in "non-symmetrical" error messages[1]: given something like

MkPair :: a -> b -> Pair a b
not :: Bool -> Bool
succ :: Int -> Int

foo x = MkPair (succ x) (not x)

the error message will either complain that `x` has type `Bool` but it should be `Int`, or it will complain that `x` has type `Int` but it should be `Bool` -- depending on what implementation you use! For example, in Haskell, Hugs 98 will emit the first error message, but GHC 7.10 will emit the second (see the full example in my slides[2]). And in some sense, neither is right (and certainly neither is as helpful for the programmer as it could be).

So next time you're implementing vanilla HM, maybe consider a compositional type system[3] instead, which can give the following, much more informative error message:

Cannot unify 'Int' with 'Bool' when unifying 'x':
Cannot unify 'Int' with 'Bool' in the following context:

MkPair (succ x) (not x)

Bool -> Pair Int Bool Bool
x :: Int Bool

I have a simple implementation here[4], and am about to release a new version which works on `haskell-src-ext`'s AST to support more of Haskell 98 syntax (but still for vanilla HM only).

[1] https://gergo.erdi.hu/blog/2010-10-23-the_case_for_compositional_type_checking/
[2]…

Your sketch of a proof does not appear substantially different from the proof given in section 3.1 of the linked paper. Section 3.2 explains that this result does not apply to strongly normalising languages.

See also the slides titled “So what about, e.g. Fω instead of ℕ ⇒ ℕ?” in Gergo Erdi’s talk on the subject of the linked paper:

https://gergo.erdi.hu/talks/2015-11-fomega/FOmegaUnquote.pdf

Note that your sketch is one particular variation of a folklore argument, best recalled by Conor McBride in 2003:

https://mail.haskell.org/pipermail/haskell-cafe/2003-May/004343.html

Here’s what Conor McBride has to say on the subject in 2015:

https://www.reddit.com/r/haskell/comments/38wels/conor_mcbride_hasochistic_containers/cs11ppm/?context=3

If you are interested in discussing this further, please feel free to contact me privately.

There's also this https://gergo.erdi.hu/blog/2021-09-18-rust_on_the_mos_6502__beyond_fibonacci/ for rust on the 6502.

I wonder how's the performance vs. C (for both, C# and Rust).

Edit: It's my understanding that the 6502 is extremely stack-limited, so a well-versed assembler would use the stack very little and allocate mostly on the heap. In C, you can replicate this with global variables, and I believe (and I would be very happy if someone related to the 6502 rust port could chime in here) on Rust you can do the same with `static mut` on Rust 2021 and `Unsafecell` on Rust 2024.

I have seen more than one such compiler, usually from Haskell-like dialects to C++ metafunctions (e.g., http://gergo.erdi.hu/projects/metafun/).

In this case the metaprogramming seems unnecessary---even assuming that it makes any sense to run a snake game at compile time---since C++14's relaxed `constexpr` functions are a much more readable way to achieve the same thing. Metaprogramming is only required now when types need to be computed; most of everything else is more cleanly done with `constexpr`.