Hindley-Milner

why?

because if we want to have map :: (a -> b) -> [a] -> [b] (Haskell syntax) we will need parametric polymorphism. we know we want at least map and foldl :: (b -> a -> b) -> b -> t a -> b.

we likely also want polymorphic arithmetic operators (+) :: Num a => a -> a -> a so we don't have to write plusNat :: Nat -> Nat -> Nat and plusU32 :: u32 -> u32 -> u32 and so on... type classes and "true generics" may be out of scope, but we can at least pick a monomorphic function at parse/typecheck time. by that I mean that when parsing (1: u32) + (2: u32), we would choose plusU32 and insert that into our AST, and when parsing (1: Nat) + (2: Nat) we would choose plusNat and insert that.

so I think we will need to do type inference. HM is sort of thought of as the best way. I haven't implemented it before, but based on materials I found in a quick search (see below) I don't think it will represent too much work.

I am reading through this tutorial now. it's nice.

I have my prototype Haskell Reputation DSL which is rather ugly at present, and I think I will tinker with it as I go through this tutorial and increase my understanding of type inference. at some point I think I'll add it to this repo under a haskell/ directory (since we'll want a Rust version later / in parallel, since that can run on Holochain).

Hindley-Milner in Rust:

• tutorial
  • associated implementation which is rather specific and probably has lots of details we would have to look past in order to extract the essence
• simpler looking implementation of HM in Rust

from rep_lang.

I just skimmed through the Haskell HM tutorial above. it’s really good.

I am now thinking I may attempt to reimplement their approach in Rust. since I am still beginner-ish to Rust this may be a nice learning exercise, and will inform me in how to translate concepts from purely functional Haskell to procedural Rust. I thought about reimplementing it in Haskell but it seems too tempting to copy-paste, and a little silly to guess my way through it when I have an elegant solution to look at.

the language that is built in the tutorial is the core of a “real PL”, whereas I think the reputation DSL only needs to support expressions (no statements). removing the unneeded features and paring it down later should be straightforward. it’ll be easier to do a mostly-verbatim translation into Rust as a first step.

from rep_lang.

from rep_lang.

Super exciting! I look forward to hearing how you go with this

Thanks! I’ll update here.

still outside my paygrade.

Pay implies hierarchy but I think there is no above or below here, just “different”! 🙂

I think you're right about not needing to support statements- the only statements we really need to be able to parse are those of const assignments... once they are substituted in, everything is really a giant single statement which evaluates against a set of input data until a single value is emitted at the top level.

Thanks, that is good confirmation to have. Seems like we will have some number of definitions, then a single top level expression which can reference definitions. Happily, this exactly matches the tutorial language’s AST 🎉

from rep_lang.

today I started this repo: https://github.com/mhuesch/poly-rs and made a lil' bit of progress on the core types and pretty printer.

pretty printers are fairly straightforward & my strategy is to do more straightforward things first so I can build Rust skills before tackling the meatier bits.

some interesting learnings about similarities and differences of Rust's traits and Haskell's type classes. so far, still digging Rust 🦀

from rep_lang.

I didn’t update yesterday but I have been chugging along on the parser yesterday & today 🚂

https://github.com/mhuesch/poly-rs/commits/parser

Parser is mostly implemented, but it’s incomplete and has some bugs that I’ve discovered using QuickCheck. Haven’t been able to shrink counterexamples down to minimal cases yet (so they are big and incomprehensible) but will figure that out soon.

from rep_lang.

Parser & pretty printer are done: mhuesch/poly-rs#3.

They aren’t all that interesting at the level of concepts, but I found them fun & a good introduction to some intermediate (ish?) Rust concepts.

Next up are the more core pieces like the constraint generator & solver (which comprise the type checker). I will probably do that before the interpreter / evaluator of programs.

from rep_lang.

I did a burst this morning on type inference. I’m planning to take the “constraint generation” approach where the AST is traversed, constraints are generated and outputted, then they are solved, and then the variables can be used to make sense of the AST.

Constraint gen approach: https://github.com/sdiehl/write-you-a-haskell/tree/master/chapter7/poly_constraints
All-at-once approach: https://github.com/sdiehl/write-you-a-haskell/tree/master/chapter7/poly

I think having separation of phases is nicer, and will make it easier to see what’s going on and also debug.

This morning I had a think about how to map the core essence from the Haskell implementation over to Rust. The Haskell version makes use of type classes and monad transformers. Rust has other ways of doing things. I think I have identified a nice pattern of using trait impl’s on structs, in order to accomplish what type classes are used to accomplish.

Then the monad transformer stack can be replaced by a bunch of functions returning Result (for error handling) and doing state full actions (for the equivalent of State and Writer).

I think this should work nicely.

from rep_lang.

just wrapping up a second burst on type inference. progress can be seen here (I realized that linking to branches isn't so good because they disappear once deleted from the remote).

I opted to implement the Env module/struct, copying from sdiehl's code. it's a newtype wrapper around Data.Map (Haskell) / HashMap (Rust) which exposes a subset of the functionality. not sure it's totally necessary, as documented in a comment.

I haven't ventured too much further than the Substitutable typeclass/trait yet, so my prognosis of "seems good so far" from yesterday still trivially holds.

from rep_lang.

another update!

I have type inference "working". progress is on the same branch. there's a bug somewhere that I have to track down where constraints are left too general from function application. presumably I messed up, unless the tutorial has a bug (which is def possible because there was a bug in let inference that was revised by someone submitting a PR - possible this is another occurrence of the same issue).

I made a little REPL to demo things - it parses & typechecks user input.

demo here: https://asciinema.org/a/UAqZoIS07DqDMzfJlia7IpY4P

🚀

from rep_lang.

ok I fixed type inference (at least that one bug, maybe there are others 🐛 ) - turns out it was quite simple.

demo.

from rep_lang.

I haven't updated here but have made a lot of progress in the past few days. I now have a whole type checker & interpreter with lists, tuples, map, foldl.

latest work is in this draft PR: mhuesch/poly-rs#9
demo here: https://asciinema.org/a/369953

I think the next step, after some polish, could be to put it in a hApp and figure out how to write "adapter" code. the MVP being something like "read all of these integers from the DHT and average them", written in the DSL.

there's some fancier things that could be added, like

• proper sum types (& case analysis)

(case x
 [(Left a) (+ a 3)]
 [(Right b) (if b 4 10)])

• proper record types

(+ (* (. x field_1) (. y field_1))
   (* (. x field_2) (. y field_2)))

• user-defined data types
  • for example, the above sum type Left/Right
• type classes
  • this would allow us to e.g. implement addition on floating point, and addition on integers, using the same + operator (without resorting to operator overloading).

however I think these things are not strictly necessary for an MVP. I think we can get away with a built-in list type (as already added) and product types...

from rep_lang.

closing this since we are using issues more in the conventional style, rather than as progress logs, as I did here.

from rep_lang.