Loop Invariant Based Programming in Graphics

Loop Invariant Based Programming in Graphics 1 Introduction This essay suggests and explores a graphical paradigm for teaching loop programming that is based on the Loop Invariant [13, 17]. This approach is used in the context of a course on introduction to programming (CS1) that alternates between particular principles related to the C programming language and algorithmic elements. The course's primary goal is to introduce first-year students to the fundamentals of programming. In the framework of a rigorous programming technique, the idea of a right and efficient algorithm is emphasised. An algorithm often calls for the creation of a series of instructions that must be repeated a certain number of times. This is often referred to as a programme loop. The way we offer for writing a loop is based on a loose interpretation. Floyd and Hoare's Loop Invariant, a programme loop attribute that is checked at each iteration, or at each assessment of the Loop Condition [13, 17]. Prior to creating any code, we decide on a problem-solving strategy (based on the Loop Invariant) and then use that approach to construct the code, following Dijkstra's original suggestion [11]. As a result, the Loop Invariant may be thought of as the foundation of programming. The problem is that, if the Loop Invariant is stated as a logical claim, it may be confusing to pupils who do not have the appropriate foundation in abstract thought. This is the rationale cited by Astrachan [1] for the typical avoidance of loop invariants in beginning courses. This claim is supported by a large body of research [20, 22] that demonstrates how challenging it is to teach CS1 because students frequently struggle to comprehend how programmes operate [27], create elegant and efficient programmes [10] (conditionals and loops have been found to be particularly challenging [8]), be proficient in math and problem-solving [22], and determine whether a programme is working properly [5]. Furthermore, we are unable to draw any conclusions regarding the backgrounds of firstyear students in our situation because of the wide range of students enrolling in the CS1 programme in Belgium1. We suggest a Graphical Loop Invariant (Gli) to make sure students adhere to a disciplined programming style despite their (possible) deficiencies. The Gli information at least explains the variables, constant(s), and data structures used by the programme, together with any attributes and any relationships they could have that are maintained during all iterations. To generalise what the programme must have done after each iteration is the idea behind this. Along with the advantages that drawings naturally have [15, 25, 26], the Gli gives programmers the ability to visually infer instructions before, during, and after a loop. This technique develops abstraction abilities without the need for a mathematical foundation and establishes the groundwork for more formal ways, with the Gli serving as a first step towards a formal Loop Invariant (which is a logical claim). An integrated tool named Café supports our programme- ming approach. The rest of this essay is divided into the following sections: Sect. Section 2 explains the Gli and how to build it; Sect. 3 explains the Gli-based programming technique; Sect. The integrated instrument for assisting Gli teaching and practise is introduced in Section 4; Sect. Preliminary findings on how students grab the Gli are shown in Figure 5; Sect. Finally, Sect. 6 places this paper in relation to the state of the art. The last section of this essay, 7, summarises its major accomplishments and discusses possible study avenues. Visual Loop Invariant 2.1 Overview A programme loop's attribute known as a "Loop Invariant" [13, 17] is one that is tested to see whether it is true at each iteration (i.e., each loop condition assessment). The 1 In which, with a few exceptions, free access to higher education is the norm. The goal of a loop invariant is to explain what has been computed up to this point by the loop in a general and formal manner using a logical statement. The Loop Invariant has historically been used to demonstrate the validity of code (for examples of automated code verification, see Cormen et al. [9] and Bradley et al. [6]). As a result, the Loop Invariant is applied "a posteriori"—that is, after writing the code. Instead, Dijkstra [11] suggested figuring out the Loop Invariant first, then using it to infer the code's instructions. Therefore, "a priori" use of the Loop Invariant is made. Our approach departs from Dijkstra's in that we suggest the Graphical Loop Invariant (Gli), which visualises the Loop Invariant. This diagram must show the variables, constants, and data structures that will be used in the code, along with any restrictions on them, any possible connections between them, and any relationships that must be preserved over iterations. Throughout the article, a fairly simple issue is used as an example to demonstrate the Gli: Two numbers, a and b, as in a b, as input The result will be the sum of all the integers in [a, b]. Figure 1a illustrates the proper Gli to use to answer the given issue. We first use a graded line marked with the integers symbol (Z) to represent the integers between the problem's bounds (a and b). It simulates the process of iterating over each integer from a to b. A vertical red bar (known as a Dividing Line) is then painted to split the integer line into two regions in order to reflect the situation after a certain number of iterations. Integers that have previously been multiplied in a variable p are shown in the left section, which is coloured blue. P is the accumulator that stores intermediate results throughout the iterations. The integers that still need to be multiplied are covered in the green region on the right. We choose to assign the variable i, which serves as the iterator variable in the range [a, b], to the closest integer to the right of the Dividing Line. Of course, the code has to utilise the variables i and p. We present an approach for making the construction of a proper Gli (see Sect. 2.2) easier in the following, based on seven guidelines (see Fig. 2) and pre-defined drawing patterns (see Sect. 2.3). Next, Sect. Based on this illustration, 3 describes how to infer code instructions from a Gli manipulation. It is important to note that using a graphical representation of the Loop Invariant enables students to practise using formal method programming without having to deal with mathematical notations. In fact, Fig. The formal Loop Invariant matching to the Gli seen in Fig. 1b is provided in 1b. 1a (using a similar colour code). Making such a predicate could seem more difficult to pupils since it calls for the use of mathematical notations (like IT) with free (i, a, and b) and bound (j) variables. variables. Consequently, it is possible to examine how the Gli is used in code development. is a first step in understanding and using formal programming techniques. Building a Graphical Loop Invariant (2.2) It may seem difficult to find a Loop Invariant to solve an issue. A Loop Invariant may be found in a variety of methods, including by induction, working from the precondition, and beginning from the postcondition. In our course, we like to show students how to use the constant relaxation approach [14] visually, which involves using i = n as part of or all of the Stop Condition to replace an expression from the postcondition (that does not change throughout programme execution, such as some n). We provide seven guidelines that students should follow while looking for a solid and correct Gli in order to aid them in navigating that abstract process, as shown in Fig. 2. These guidelines are divided into two primary categories: (i) syntactic (concentrating only on the drawing elements; Rules 1 to 4); and (ii) semantic (concentrating solely on the justifications provided to the drawings; Rules 1 to 7). Specifically, Fig. The programme purpose is then explained (blue arrow and text in Figure 2) before the programme output is drawn using a pre-defined pattern (Rule 1 - the many potential patterns are discussed in Sect. 2.3). This rule suggests accurately depicting the data or data structures relevant to the specified issue. Rule 1 advises correctly labelling each drawn data structure (for example, with a variable name). Multiple data structures must be managed by the programme in order to prevent errors from occurring when developing the code. Then, each construction must have borders around it (Rule 2). When writing the code (see Section 3), using Rule 2 helps avoid mistakes like array overflows and out-of-bounds problems. These mistakes would occur. be less probable if the Gli accurately states the data structure length. Rules 3 through Rule 6 are then successively used to roll back the final viewpoint and see the solution being built via each variable. state. When Rule 3 is used, the Dividing Line emerges, lowering the length of the blue zone (Rule 5) and allowing space for the green zone (Rule 6). The foundation of our system is the Dividing Lines. They represent the difference between what the programme has already calculated and what has to be done to achieve the programme target. In order to determine the coding instructions, they make it possible to visually edit the artwork (see Sect. 3). Applying Rule 4 necessitates choosing whether to position the iteration variable on the left (thus being part of what has already been accomplished by prior iterations) or on the right (as part of the 'to do' zone) around the Dividing Line. Typically, we advise students to position it to the right, referencing the element that is currently being processed in the Loop Body. Since a dividing line distinguishes between what has been done and what will be, if we illustrated such a line on the data representation as the programme is run, it would move from one position to another, with the first position representing the initial state and the last representing the final one. Rule 5 is now only partially applied since there isn't a variable for accounting for intermediate outcomes. Thus, it suffices to introduce the accumulator (i.e., variable p) into the text below the arrow. Applying Rule 5 encourages consideration of the program's conduct. One could consider "what has been accomplished so far" by asking: "What should have been calculated thus far in order to attain the programme goal? What variables' properties need to be guaranteed?This step of reflection often reveals the requirement for extra variables that hold partial results or the connections between variables that must be preserved during the code execution. On the other hand, knowing what has already been accomplished is important when developing code since it makes it easier to determine which instructions should be carried out during an iteration, or to determine the Loop Body (see Sect. 3). Last but not least, it is sufficient to identify the drawing with the 'to do' zone up to the Dividing Line, in accordance with Rule 6. The Gli acquired here is, of course, precisely the similar to the one seen in Fig. 1a. Since applying Rule 6 doesn't provide any new information about the answer, it seems like a less important rule to follow. In reality, there wouldn't be any logical notation to indicate "what should still be done" if we represented a Gli in a formal way (i.e., as a predicate). To make the representation of the program's starting and final stages easier, a region showing what has to be done is best drawn. When first introduced, this "to Do area" should include all of the data that the programme is interested in. Contrarily, in the final condition, this area should have vanished, with the sole area left standing in for what the programme has accomplished. In such a situation, it is simple to determine if the program's goal has been achieved. Additionally, as the lines must be adjusted in order to reduce the area, this "to do area" aids in the deduction of the changes to the variables marking the Dividing Lines (see Sect. 3). Finding a loop variant also helps. The size of the "to do area" is often an excellent candidate for the Loop Variant (b +1 a on the Gli shown in Fig. 1), which commonly indicates loop ending. Fig. 3. Gli's predetermined sketching styles. The last guideline serves as a reminder to make sure that the code contains all of the variables found during the reflection step. Additionally, we use a color-coded system to aid students with recognising the many rules and how they apply to a Gli (see Fig. 2). Students can better grasp presented Gli in class because to the color-coding system that has been devised and is used consistently throughout the course and its tools (see Sect. 4). 2.3 Graphical Patterns with Loop Invariance In a CS1 course, this part presents several common patterns for visually displaying common data structures. For a valid Gli and accompanying colour code, the patterns require on the first two principles (see Fig. 2). Gradient Line. The graded line is one of the most fundamental patterns since it may be used to depict ordered sets like subsets of Natural or Integers. The set name (such as N or Z) is shown as the line's label. There are values associated with each tick on the line, and each value is offset by the same step. The line's far-right arrow points to the values' ascending order. That pattern, which can be seen as coming from Rule 1 in Fig., was supporting the Gli stated in the preceding subsection. 2. Furthermore, limits should surround that line, as is done. Rule 2. That specifically demonstrates how a and b are related. Number. One may express this number as a string of digits with the name dj in order to solve difficulties with number representation (whether it be binary, decimal, hexadecimal, etc.). The most important digit is on the right, followed by the least important on the left. Often, the dj are just figures that collectively represent the variable rather than variables that are explicitly utilised in the code. It is possible to indicate in the image which are the first and final digits to be treated if a programme has to explore the values of the digits in a certain sequence, as it is, for example, finished in Fig. Where the least significant digit (shown in orange) is used first and the most significant digit (shown in magenta) is used last in Figure 3A. Array. A depiction of an array with N items is shown in Figure 3b. To show how the parts are stored together, the pattern is rectangular in form. The first (i.e., 0 - always on the left of the picture regardless of the direction the array is processed) and the size N are the indices of interest that are shown above this rectangle. In order to understand that N is not a valid index since it is outside of the array, it is crucial to note that N is written to the right of the array's boundary. limits of the array that fall inside [0..N 1]. The name of the variable used to access the Its left is where array is written. Fig. 4. Logic assertions and loop zones. Arrows show the direction of the programme flow, whereas orange diamonds represent an expression that has been evaluated as a Boolean. States are shown with green boxes. (Online colour figure) There are other patterns as well, including linked lists and files, but at our university, they are typically covered in a CS2 course.