Skip to content

Toy interpreter for the lambda calculus to explore Rust

Notifications You must be signed in to change notification settings

jez/rust-lc-interp

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

38 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

rust-lc-interp

I wrote a lambda calculus interpretter in Rust to get a feel for Rust.

If you care to look at the code, please know that I Have No Idea What I'm Doing.

Usage

Clone the repo and then cargo run to start the REPL. Syntax is Haskell syntax for lambdas and ReasonML syntax for let bindings:

❯ cargo run
...

λ> (\x -> x) (\x -> x)
...
=> \ -> #0
λ> let id = \x -> x; id id
...
=> \ -> #0

If you don't want to clone or don't have a cargo setup, you can play around with a release from the Releases page.

Notes

  • I had a really fun time with lalrpop. It feels really nice to use, especially the error messages for conflicts:

    ...
    src/lc.lalrpop:19:5: 19:57: Local ambiguity detected
    
      The problem arises after having observed the following symbols in the input:
        Atom Atom
      At that point, if the next token is a `"("`, then the parser can proceed in two different ways.
    
      First, the parser could execute the production at
      /Users/jez/Dropbox/Documents/Programming/rust/sandbox/src/lc.lalrpop:19:5: 19:57, which would consume
      the top 2 token(s) from the stack and produce a `Atom`. This might then yield a parse tree like
        Atom Atom Atom
        ├─Atom──┘    │
        └─Atom───────┘
    
      Alternatively, the parser could shift the `"("` token and later use it to construct a `Atom`. This might
      then yield a parse tree like
        Atom "(" Atom ")"
        │    └─Atom─────┤
        └─Atom──────────┘
    
      See the LALRPOP manual for advice on making your grammar LR(1).
    ...
    

    These are by far the best parser generator error messages I've ever seen.

  • There are still a bunch of things I miss coming from SML / OCaml / C++. On the SML side, I miss: global type inference, not having to worry about memory, not having to qualify names of patterns (Lam vs Expr::Lam), not having everything be mutually recursive by default, etc.

    On the C++ side, I find it's easier to do a mutable, in place traversal of a data structure. In rust, I found myself constantly trying to update a field of an enum in place, and fighting to make sure I was allowed to do so. What in C++ would have just been a field access + assignment, in Rust was either something like a ref mut x pattern match, and then trying to use that reference to update the field indirectly.

License

MIT License

About

Toy interpreter for the lambda calculus to explore Rust

Topics

Resources

Stars

Watchers

Forks

Packages

No packages published

Languages