apoelstra
commented
2 months ago This looks great. Right now the cat.simf program is broken (says there is a type mismatch). Did you mean to fix this?
Eventually we should weaken the parse tree to be more accepting because parse errors are hard for the user to understand. Like, right now if you remove type annotations from your example programs you get something like expected match_pattern but it'd be nicer if we'd parse these things, mark them as "unknown type" and then during AST conversion we'd give the user an error like "No type was specified for x. You need to provide a type annotation, like x: bool." (And maaaybe we could even figure out what the type annotation needs to be? Or at least make a guess based on context?)
Anyway that's all fine for a followup.
uncomputable
Add an abstract syntax tree (AST) as a type-checked variant of the parse tree. Compile the AST to Simplicity instead of the parse tree, which gives the compiler knowledge about the type of each expression which is to be compiled.
Previous: Program text → Parse tree → Simplicity Now: Program text → Parse tree → AST → Simplicity
I needed to annotate match arms and unwrap_left and unwrap_right with additional types so the type of each subexpression is unambiguous. This is not like Rust, but Rust supports type inference. All let statements have to be annotated, so also annotating match arms and unwraps should not be much more overhead.
The PR is so large because I replicate parse.rs (>1000 lines) in a type-checked fashion. Most of the changes are mechanical, so the PR should be easier to review than it looks. The sanity checks and the compiler require more attention.