search

koka-lang / koka

Koka language compiler and interpreter
http://koka-lang.org
Other
3.26k stars 162 forks source link

Start of Koka self-hosted implementation #317

Closed TimWhiting closed 9 months ago

TimWhiting commented 1 year ago

Working in this commit:

The files should all compile without errors

I've verified the Lexer by lexing the lexer.kk itself. The lexer is rather slow right now, but I've started looking into the parser machinery as mentioned here: https://github.com/koka-lang/koka/issues/103#issuecomment-742852707

Before I go any farther I'd like to seek input from @daanx.

I think it would be great to have a self-hosted compiler for the following reasons:

I also understand that Koka is currently a research language and that this introduces a larger maintenance burden during a transition period from the Haskell compiler, and the fact that Haskell has more libraries that can be used for the vscode extension protocol, and other helpful utilities like the Alex lexer library and Parsec, which I have definitely felt the lack of when trying to make the Lexer fast.

Regardless of whether this would eventually become the default compiler, I have found it a useful project to get familiar with Koka & Haskell & Koka's Haskell compiler, so I'll probably continue work on it for those reasons, and would welcome contributions from others who are also interested in this.

TimWhiting commented 1 year ago

Marking as draft for now, but willing to incrementally add the self-hosted implementation in chunks if that is better.

timjs commented 1 year ago

Very brave to start working on this! Maybe you can split this up in a PR for an extended and more structured core lib first. Would be great to have general access to a map implementation for example. Next to an LSP implementation, it is something I'm missing atm. Building a community and great tools for Kok's would be awesome!

timjs commented 1 year ago

About an optimised lexer/parser. Don't know if it's helpful, bu I experimented with an modular interface around parsers a la MegaParsec but stumbled on some internal compiler errors. See #258.

TimWhiting commented 1 year ago

About an optimised lexer/parser. Don't know if it's helpful, bu I experimented with an modular interface around parsers a la MegaParsec but stumbled on some internal compiler errors. See https://github.com/koka-lang/koka/discussions/258.

@timjs I'll definitely take a look!

Maybe you can split this up in a PR for an extended and more structured core lib first. Would be great to have general access to a map implementation for example.

Good thought. There is some considerations for the map interface though, and collections in general.

  1. Haskell uses typeclasses to enforce that you can sort the keys. Koka does not have typeclasses yet.
  2. The sorting function could be passed into every method (inconvenient)
  3. The sorting function could be an effect - inconvenient when you have two maps with different key types because of the swap rule for generic effect types (https://github.com/koka-lang/koka/discussions/247)
  4. The sorting function has to be stored in the map type (probably not on every node, but as a wrapper object). The wrapper object is probably not a big deal if just using the map interface, but could be confusing if you want to traverse the map yourself with match

I've actually put some thought and research into using generic effect types to implement a typeclass-like constraints on the types of arguments of functions, by getting rid of some of the pain points of approach 3. I've got some basic stuff working such as automatically inserting user-defined default handlers for types. This is something I'm considering exploring further as a part of my PhD, but I'm curious if it aligns with what @daanx was thinking about for typeclasses in Koka, since he said he had a version of them in a design phase. I've got a branch for this and the start of a research proposal, and can discuss it more if there is interest. Mostly it involves default effects, and type-indexed generic effect handlers. I'm interested in pursuing this for my PhD as well as some optimizations of effect handlers such that the linear property could be inferred or proved via static analysis.

TimWhiting commented 9 months ago

My work on this has moved elsewhere