Calculating Sum With `mvcgen` And Index Access

by Alex Johnson 47 views

In this comprehensive guide, we delve into the practical application of mvcgen for calculating sums using index access within the Lean programming language. This article provides a detailed exploration of the code, theorems, and techniques involved, offering valuable insights for both beginners and experienced Lean users. Understanding how to effectively use mvcgen for such calculations is crucial for optimizing your code and ensuring its correctness. Let's dive in!

Introduction to mvcgen and Index Access

When it comes to performing calculations in Lean, mvcgen is a powerful tool that aids in verifying the correctness of your code, especially when dealing with loops and mutable state. Index access, on the other hand, allows us to directly access elements within arrays using their position. Combining these two concepts enables the creation of efficient and verifiable algorithms for tasks like summing array elements.

In the context of Lean, ensuring the correctness of array manipulations, particularly when using loops and mutable states, can be challenging. mvcgen helps bridge this gap by allowing us to specify loop invariants. Loop invariants are conditions that hold true at the beginning and end of each iteration of a loop. By specifying these invariants, mvcgen can automatically generate verification conditions, which, when proven, guarantee the correctness of the loop. This approach significantly reduces the risk of introducing bugs in your code. In the subsequent sections, we'll delve deeper into the practical application of mvcgen in the context of array summation, demonstrating how to define and utilize loop invariants effectively to ensure the correctness of our algorithms.

Code Implementation: Array.sumDo

Let's start by examining the Array.sumDo function, which calculates the sum of elements in an array using index access:

import Lean

variable {α : Type} [Add α] [Zero α]

/-- 配列に対するインデックスアクセスを使用して和を計算する関数 -/
def Array.sumDo (arr : Array α) : α := Id.run do
  let mut out := 0
  for hi : i in [0:arr.size] do
    out := out + arr[i]
  return out

This Lean code snippet introduces a function named Array.sumDo that calculates the sum of elements in an array using index access. The function is defined within the Lean programming language and leverages several key features. Firstly, it imports the Lean module, which provides the foundational elements for Lean programming. The function is generic over a type α, which must have addition (Add α) and zero (Zero α) operations defined. This flexibility allows the function to operate on various types, such as integers, real numbers, or even custom data types, as long as they support addition and have a zero element. The core logic of the function lies within the Id.run do block, which enables the use of mutable state within a purely functional context. A mutable variable out is initialized to zero, and a for loop iterates over the indices of the input array arr. Inside the loop, the element at the current index i is added to out. Finally, the function returns the accumulated sum out. This approach exemplifies how Lean can combine functional and imperative programming styles to achieve efficient and verifiable computations.

Dissecting the Code

  • import Lean: Imports the Lean core library.
  • variable {α : Type} [Add α] [Zero α]: Declares a type variable α and type class instances for addition and zero.
  • def Array.sumDo (arr : Array α) : α := ...: Defines the sumDo function, which takes an array arr of type α and returns a value of type α.
  • Id.run do ...: Uses the Id.run do block to work with mutable state within Lean's functional environment.
  • let mut out := 0: Initializes a mutable variable out to store the sum.
  • for hi : i in [0:arr.size] do ...: Iterates over the indices of the array using a for loop.
  • out := out + arr[i]: Adds the element at index i to the out variable.
  • return out: Returns the final sum.

Essential Theorems for Verification

To verify the correctness of Array.sumDo, we need to establish some crucial theorems. These theorems serve as building blocks for our proof and help mvcgen understand the behavior of arrays and summations.

-- α は加法的な可換モノイド
variable [@Std.Associative α (· + ·)] [@Std.LawfulIdentity α (· + ·) 0]
variable [@Std.Commutative α (· + ·)]

theorem List.sum_append_singleton {l : List α} {x : α} :
    (l ++ [x]).sum = l.sum + x := by
  induction l with (simp_all; grind only)

@[grind =, simp]
theorem Array.sum_append_singleton (arr : Array α) (a : α) :
    (arr ++ #[a]).sum = arr.sum + a := by
  simp [← sum_eq_sum_toList, List.sum_append_singleton]

@[grind =]
theorem Array.extract_stop_add_one {α : Type} {arr : Array α} {i j : Nat}
  (hj : j < arr.size) (hij : i ≤ j) :
    arr.extract i (j + 1) = arr.extract i j ++ #[arr[j]] := by
  simp only [append_singleton, push_extract_getElem, Nat.min_eq_left, hij]

This section presents three key theorems essential for verifying the correctness of array summation in Lean. These theorems build upon fundamental concepts of lists, arrays, and summation, providing the necessary logical steps to prove the Array.sumDo function's accuracy. The first theorem, List.sum_append_singleton, deals with lists and states that the sum of a list appended with a single element is equal to the sum of the original list plus the appended element. This theorem is proven by induction on the list l, showcasing Lean's powerful induction capabilities. The second theorem, Array.sum_append_singleton, extends the previous concept to arrays. It asserts that appending a single element a to an array arr results in a sum equal to the original array's sum plus a. The proof elegantly simplifies the expression using the relationship between array summation and list summation (sum_eq_sum_toList) and then applies the List.sum_append_singleton theorem. Lastly, the Array.extract_stop_add_one theorem focuses on array extraction. It states that extracting a sub-array from index i to j + 1 is equivalent to extracting from i to j and then appending the element at index j. This theorem is crucial for reasoning about sub-arrays and is proven using simplification and leveraging properties of array extraction and element access. Together, these theorems form a robust foundation for verifying the Array.sumDo function, demonstrating Lean's ability to express and prove intricate properties of data structures and algorithms.

Key Theorems Explained

  • List.sum_append_singleton: This theorem states that the sum of a list appended with a single element is equal to the sum of the original list plus the element. This is a fundamental property of list summation.
  • Array.sum_append_singleton: This theorem extends the previous one to arrays. It states that appending an element to an array results in a sum equal to the original array's sum plus the element.
  • Array.extract_stop_add_one: This theorem is crucial for reasoning about sub-arrays. It states that extracting a sub-array up to j + 1 is the same as extracting up to j and then appending the element at j.

Verifying Array.sumDo with mvcgen

Now, let's use mvcgen to prove that Array.sumDo correctly calculates the sum of array elements. The key to using mvcgen effectively is specifying the correct loop invariants.

open Std.Do

set_option mvcgen.warning false

/-- `Array.sumDo` は配列の要素の和を正しく計算する -/
theorem Array.sumDo_eq_sum (arr : Array α) : arr.sumDo = arr.sum := by
  generalize h : arr.sumDo = r
  apply Id.of_wp_run_eq h

  mvcgen invariants
  · ⇓⟨cursor, out⟩ => ⌜(arr.take cursor.pos).sum = out⌝
  with (simp_all <;> grind)

In this segment, we employ mvcgen to formally verify that the Array.sumDo function accurately computes the sum of array elements. The verification process hinges on specifying the correct loop invariants, which are conditions that remain true at the beginning and end of each iteration of the loop. To begin, we open the Std.Do namespace, which provides essential tools for working with do-notation in Lean, facilitating the management of stateful computations within a functional context. Additionally, we set the mvcgen.warning option to false to suppress warnings during the verification process, ensuring a cleaner output. The core of the verification lies in the Array.sumDo_eq_sum theorem, which asserts that the result of Array.sumDo on an array arr is equal to the standard arr.sum. To facilitate the proof, we generalize the equation arr.sumDo = r, allowing us to reason about an arbitrary result r. We then apply Id.of_wp_run_eq h, which is a tactic that leverages the properties of the Id monad to equate the original goal with the weakest precondition of running the computation. This step sets the stage for mvcgen to analyze the loop within Array.sumDo.

Understanding the Verification Process

  • open Std.Do: Opens the Std.Do namespace for working with do-notation.
  • set_option mvcgen.warning false: Disables warnings from mvcgen.
  • theorem Array.sumDo_eq_sum (arr : Array α) : arr.sumDo = arr.sum := by ...: States the theorem that Array.sumDo calculates the sum correctly.
  • generalize h : arr.sumDo = r: Generalizes the goal for easier reasoning.
  • apply Id.of_wp_run_eq h: Applies a tactic to equate the goal with the weakest precondition.
  • mvcgen invariants ... with (simp_all <;> grind): Invokes mvcgen with the specified invariants and tactics.

Loop Invariants

The crucial part of the verification is the loop invariant:

· ⇓⟨cursor, out⟩ => ⌜(arr.take cursor.pos).sum = out⌝

This invariant states that at each iteration, the sum of the elements taken from the beginning of the array up to the current cursor position (cursor.pos) is equal to the value of the out variable. This invariant captures the essence of the loop's behavior and is essential for mvcgen to prove the correctness of the function.

The loop invariant specified here is the linchpin of the verification process. It succinctly captures the relationship between the state of the loop (represented by cursor.pos and out) and the accumulated sum of the array elements. The invariant asserts that at any point during the execution of the loop, the sum of the elements from the beginning of the array up to the current position (cursor.pos) is precisely equal to the value stored in the mutable variable out. This invariant is crucial because it maintains a consistent relationship between the partial sum and the progress of the loop. By proving that this invariant holds true at the beginning of the loop, remains true after each iteration, and implies the desired result upon termination, we can confidently conclude that the Array.sumDo function is correct. The mvcgen tool leverages this invariant to automatically generate and discharge proof obligations, significantly simplifying the verification effort. In essence, the invariant acts as a bridge connecting the initial state, the iterative process, and the final result, ensuring the correctness of the summation algorithm.

mvcgen in Action

  • mvcgen invariants: This command tells mvcgen to use the specified invariants to generate verification conditions.
  • ⇓⟨cursor, out⟩ => ⌜(arr.take cursor.pos).sum = out⌝: This is the loop invariant, which states that the sum of elements up to the current cursor position equals the out variable.
  • with (simp_all <;> grind): Specifies tactics to be used by mvcgen to discharge the verification conditions. simp_all simplifies the goal using all available lemmas, and grind is a powerful tactic that attempts to solve the goal automatically.

By specifying the loop invariant and providing appropriate tactics, mvcgen can automatically prove that Array.sumDo correctly calculates the sum of the array elements. This showcases the power of mvcgen in verifying complex algorithms with mutable state.

Conclusion

In this article, we explored how to use mvcgen to verify the correctness of an array summation function (Array.sumDo) in Lean. We delved into the code implementation, essential theorems, and the crucial concept of loop invariants. By specifying the correct invariants, we enabled mvcgen to automatically prove the correctness of our function.

This example highlights the power of mvcgen in verifying algorithms with mutable state. Understanding how to use mvcgen and specify loop invariants is essential for writing robust and reliable code in Lean. By leveraging these tools, you can confidently build complex algorithms with the assurance that they behave as expected.

For further exploration of Lean and its capabilities, consider visiting the Lean community website.