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 first-year 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.