Reusing existing computation

Consider the following Keelung program, notReused, which returns two copies of the input raised to the 4th power:

src/Tutorial.hs

notReused :: Comp [Field]
notReused = do
  x <- input Public
  let y = x * x * x * x
  return [y, y]

Elaborating the program produces the following output:

stack repl

> elaborate notReused
Right {
  expression:
    [ $FI0 * $FI0 * $FI0 * $FI0
    , $FI0 * $FI0 * $FI0 * $FI0
    ]

  compuation state:
    {
      variable counter: 0
      input variable counter: 1
      address counter: 0
      input variables: $I0
      num assignments: []
      bool assignments: []
      assertions: []
    }

}

The elaboration seems alright, but there's a problem! Let's compile it and see what's wrong:

stack repl

> compile GF181 notReused
Right R1CS {
  Constriant (6):
    Ordinary constriants (6):

      $2 * $2 = $4
      $2 * $2 = $6
      $3 * $2 = $0
      $4 * $2 = $3
      $5 * $2 = $1
      $6 * $2 = $5

  Variables (7):

    Output variables: $0 ... $1
    Private Input variable : $2

}

As you can see, there are two copies of the same constraints. This is because the variable y has no meaning to Keelung:

  let y = x * x * x * x
  return [y, y]

And after elaboration it is simply replaced by the same expression used twice.

  return [x * x * x * x, x * x * x * x]

reuse to the rescue!

To solve this issue, we can use the reuse function to assign an expression to a variable that is observable by Keelung, so that we can reference it in the future when we want to reuse it:

reuse :: t -> Comp t

For example, let's consider another program reused which uses reuse to compute the same expression as notReused:

src/Tutorial.hs

reused :: Comp [Field]
reused = do
  x <- input Public
  y <- reuse $ x * x * x * x
  return [y, y]

Compiling this program would result in a lot less constraints because we're able to share and reuse existing computations:

> compile GF181 reused
Right R1CS {
  Constriant (4):
    Ordinary constriants (4):

      - $0 + $1 = 0
      $2 * $2 = $4
      $3 * $2 = $0
      $4 * $2 = $3

  Variables (5):

    Output variables: $0 ... $1
    Public Input variable : $2

}