argumentcomputer / lurk

Lurk is a Turing-complete programming language for zk-SNARKs. It is a statically scoped dialect of Lisp, influenced by Scheme and Common Lisp.
https://docs.argument.xyz
MIT License
47 stars 3 forks source link

Return chips refactors #391

Open gabriel-barrett opened 1 week ago

gabriel-barrett commented 1 week ago

Needed refactorization for #372. The changes are:

1) Ctrl::Choose will now match field elements onto indices of the list of unique branches (its third argument), instead of matching onto a duplicated branch. Execute and trace generation will now need to match onto the index and use the index to jump to the branch. That also means that the default case is also an index and thus the default branch has been added to the list of unique branches, which simplifies eval and compute_layout_sizes a bit. Doing this indirection is only a slight penalty, not really noticeable, and it is basically the same cost as using Arc, which is also another layer of indirection (though I believe the indices will be better for cache hits).

2) generate_trace has been refactored to remove duplicated work, get_func_range has also been refactored slightly

3) I've added the query_index to Record basically for identification of which coroutine has done the lookup. Nonces are not unique, thus they do not completely identify the caller. Chipset has also included the query index (i.e. which coroutine it is embedded in) so that it properly records the identification. Byte lookups have also included the index. Note: we could later perhaps parametrize this query_index field so that it accounts for whatever metadata is needed. Perhaps shard indices will also become important