Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LEM improvements #1051

Open
1 of 3 tasks
gabriel-barrett opened this issue Jan 14, 2024 · 0 comments
Open
1 of 3 tasks

LEM improvements #1051

gabriel-barrett opened this issue Jan 14, 2024 · 0 comments

Comments

@gabriel-barrett
Copy link
Member

gabriel-barrett commented Jan 14, 2024

I've decided to write an issue to list the improvements we could make to LEM, which have been floating around in my head and which I haven't yet had time to work on.

  • return statements should be optimized in certain cases. All LEM blocks have to return a certain number of values, and as of now, we always allocate variables to be returned, even though this is not always needed. For instance, a func like
flip(x, y): 2 {
  return (y, x)
}

will allocate 8 variables (i.e. 2 input pointers and 2 output pointers) and 4 constraints, to constrain the return values, instead of 4 variables and 0 constraints, since we can simply return the already allocated pointers. The only need for allocating return variables is when there are divergent paths in the computation (i.e. if or match). An example is

maybe_flip(x, y, b): 2 {
  if b {
    return (y, x)
  }
  return (x, y)
}

in this case we must allocate output variables and constrain them (with implies_equal) accordingly

  • Add different types to LEM. Internally, LEM already has types: bools, numbers and pointers. But we're not able to pass bools and numbers around to funcs, nor return them. We always assume funcs work on pointers. We must be able to enhance funcs with input and output types, so that we can properly pass and return non-pointer values to funcs
  • Replace AllocatedNum with Num or something more general, in order to make add operations accumulate a linear combination and not always cost 1 constraint. It is possible to make constants cost 0 as well
This was referenced Feb 29, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant