F# Lisp fun for everyone!
-
(Continuing from F# Lisp Fun so Help category doesn't get flooded with non-help.)
I had some time last night and this morning and wrote a parser for a veeeeery simplified Scheme (just simple ints, bools, strings, identifiers, quote, let and lambda). Then I run some errands and got back to it in the evening. In the meanwhile I've did some reading and realized I did everything wrong and that's not how Lisp works at all, so I wrote a second parser. Then I had the idea that it would be much easier to implement evaluator if I had flat token stream instead of syntax tree. So I wrote a third parser, and this time I made it lazy for bonus geek pointzzz.
Also, a quick and dirty REPL. Because I've yet to write evaluator, it just prints tokens.
Off to write bytecode compiler!
@Magus, how's yours going?
-
@Gąska You might also try this:
Trigger warning: It uses Haskell.
-
@antiquarian but where's the fun in following a tutorial? I've made freakin' whole-program type inference, I can make Lisp too.
-
@Gąska Fine, but your decision to use a token stream instead of a syntax tree may cause you grief later if you ever decide to implement macros.
-
@antiquarian good thing I don't! Though I'm not entirely sure how much it changes - the flat stream is just initial input, any quoted lists have to be converted to arbitrarily nesting lists anyway (but only the quoted lists - immediately evaluated ones go straight into bytecode). I expect it to be more performant that way, although honestly that wasn't my motivation. I just want to program the interpreter a certain way because it looks like the most fun way to do it. I'm absolutely sure it'll be slow as hell anyway due to all the list reversing I have to do on each function call.
-
-
@Magus right. Forgot normal people have lives.
-
@Gąska said in F# Lisp fun for everyone!:
@Magus right. Forgot normal people have lives.
I'm going to make a sandwich.
-
@Gąska said in F# Lisp fun for everyone!:
I've made freakin' whole-program type inference
How is that different from local type inference?
-
@topspin depends on what you mean by local. The
auto/varkind of inference is trivial because you already know types of all the expressions involved. On the other hand, with ML-style inference you have functions of unknown types being called with arguments of unknown types, and every declared function is potentially a generic function, and it must be as generic as possible by default. So you have to bring out the big guns, convert constraints into equations on types, and run unification solver on everything. It gets even better when your type system has subtyping - because the equations are now inequalities.
-
@Gąska I meant the ML style. Is that what you mean by whole program or is what you did stronger than that?
(I.e., I simply inferred from your phrasing that "whole program" is in contrast to something else, thus "local")
-
@topspin no, that's it. ML is the worst case. But compare for example Rust, which only has local type inference, but what's more important, let bindings only allow declaring values, not functions. In result, all functions have explicit type except lambdas, and lambdas are never generic in Rust. That means there's no automatic generalization at all, which greatly simplifies the inference algorithm (you don't have to keep track of bound and free type variables, for example).
-
Quoting works! Bytecode generation too! Although right now it can only generate one opcode...
-
Basic language done. Only special forms remaining.
-
Halfway through implementing partially applied functions, I realized Common Lisp has no partially applied functions. Oh well.
-
Next: let bindings and lambdas.
-
@Gąska said in F# Lisp fun for everyone!:
Basic language done.
I thought you were implementing Lisp.
-
@Gąska said in F# Lisp fun for everyone!:
Pole parses parameters pertaining Polish (prefix) parlance.
-
I'm making a note here:
HUGE SUCCESS
-
This thread is fascinating in a way that makes me go
-
@antiquarian said in F# Lisp fun for everyone!:
@Gąska Fine, but your decision to use a token stream instead of a syntax tree may cause you grief later if you ever decide to implement macros.
After more reading about Lisp I finally understood what you meant.
In the last few days, I've been rewriting the parser and compiler so it operates on values directly instead of token streams. Sadly, I couldn't avoid non-tail recursion as well as with the previous design, so stack frames are being made. On the plus side, implementing
evalis trivial now, and macros aren't much more difficult! And it still compiles to bytecode!After getting feature parity with the old version, I've decided to get more fancy with the compiler first, then implement more features. Previously, the "make closure out of lambda" opcode contained the entire compiled lambda. Right now I'm busy rewriting this part so all nested functions have their code stored in the same array as the main function. Also, adding conditional statements which the previous version lacked. Also, some small optimizations like inlining let-bound immediates.
As nothing new has been finished yet, no new screenshots.
-
Also, I've come up with this operator that now I'm using all over the place to do horrible things like passing a single instance of highly mutable object along a chain of functions.
let inline (^>) f g x = f x g xI wonder if there's a canonical name and symbol for it.
-
This post is deleted!
-
Fun fact: turns out you don't need to know lambda's number of arguments after closure is made!
-
Conditionals work! And the jump-to-return optimization didn't break anything! Yay!
See how instructions 3 and 7 do early return instead of jumping after if? That's optimization!
But instruction 12 should've been elided too... I'll look into it after work.Wait, the instruction shouldn't be elided, it just has the wrong address (should be 1 farther). I'll look into it after work.
