Anti Compiler: an Educational Tool in First Year Programming
Anti Compiler: an Educational Tool in First Year Programming
Computer Science & Software Engineering
Monash University, Clayton, Australia
© 2002, Kymberly Fergusson, Melbourne, Australia
May 16, 2002
Semantic errors in programming are extremely difficult to locate and solve, unlike syntax errors which are located by the compiler. Semantic errors often generate no errors at compile or run time, depending on language, but cause the program to behave in an unexpected way. Students learning to program often have great difficulty analysing their programs for semantic errors, getting bogged down in the language syntax. Many of the sematic errors students, and experienced programmers make are extremely common, an infinite loop caused by a failure to increment the loop variable is just one example. It would be useful to automatically process code to identify these common errors, for both the students/programmers writing the programs, and the teacher who could use the common errors as a focus for refining teaching methods. Running a program to highlight potential problems could simplify error-detection and correction.
This project aims to discover if it would be feasible for a conversion program translating a more complex language (C) to a more familiar language, to automatically detect common semantic errors. Based on the findings, a software tool may be developed that would analyse and diagnose possible semantic errors in programs written by students learning programming. The`anti-compiler' would take code written in the C programming language and convert it into an English or ‘pseudo code' algorithm which would allow the students to see the underlying algorithm better than when written in a syntax they are just beginning to learn.
The C programming language has notoriously terse and obscure syntax, meaning that students beginning to learn the language have a lot of trouble finding and solving problems. Converting a program into a more descriptive language may help students to identify and fix their semantic errors quickly. It may also help them develop a better understanding of programming concepts and debugging procedures, as well as solve immediate problems in their code. Learning to step through code, and being able to trace the flow of a program is essential in debugging. Following the pseudo-code of their program, rather than getting`bogged down' in syntax, should help develop this skill.
To develop the anti-compiler, it is necessary to analyse examples of student programs to determine how similar their algorithms are. From this, common semantic problems may be identified, enabling us to target problems in the underlying understanding of algorithms, and representing these algorithms in the C programming language. It is also necessary to design a good pseudo-language in order for the more verbose representation of the students' programs to be understood quickly and clearly, minimising misunderstandings. It is known that more verbose languages lead to a higher ambiguity, as there are many more possible ways of interpreting meaning, thus careful design is necessary to minimised misunderstandings.
From this analysis and language design, it should be possible to determine whether it is feasible for an automatic tool converting C programs to a pseudo-language to reliably identify semantic errors. A tool may then be designed and written to parse student code and generate the pseudocode representation, checking for common semantic problems (as found in the analysis of the student code), and highlighting possible errors.
Much research has found that the development of languages is specifically driven by technological advances, by experts in the field, with no or little regard for beginner programmers [MC96, Pan00, Mur93]. This tends to result in very specific and complex syntaxes and representations of programming constructs. This causes programmers to present solutions unnaturally [Pan00].
Languages designed with Human Computer Interaction (HCI) principles in mind should be more accessible to beginners. In particular the most important principle is: "to speak the user's natural language" [Pan00]. Many studies have shown that novice programmers resort to natural language solutions when they reach an impasse [BS85, AE99].
It has been reported in many studies that the more like the natural language of the user the programming language is, the easier it is to learn [PRM01, Mur93]. The closer the language is to the novice's natural problem solving language, the easier the novice can find problems, design solutions, which would result in fewer overall bugs in the code [MC99, McI00].
Perkins et. al.[PHH +89], categorised novice learners into "Stoppers" and "Movers", those who stop when at an impasse and do not try to look for a solution, and those who continually try something different, often repeating solutions. It was found in this study that with appropriate prompting, students of both types would often continue and find a solution.
A complex language such as C is very difficult as both a language to learn and to teach to novice programmers, as they need to deal with a terse non-natural syntax, at the same time learning programming constructs. Development of solutions to programming problems is often encouraged to include designing the solution in a pseudo-language first. It may be useful for students to be able to compare their design, with a more natural representation of what their C programs are actually doing. It may also provide the encouragement that`Stoppers' need to get past an impasse.
Classification of types of errors is important in understanding how novice programmers learn programming, and common misconceptions [SSP85]. Several studies have classified types of errors in different ways, the most common just splitting errors into semantic or logic errors vs syntax errors [McI00]. Spohrer, Soloway and Pope classified a sub-type of semantic errors as`goal drop out' and`goal fragmentation' [SSP85]. These two categories occur where students`merge' goals together, resulting in a more complex design when using loops and control structures where multiple sentinels need to be updated or tested.
One other classification of semantic errors by Pea [Pea86], identifies`parallelism' where conditions of a loop are continually tested, instead of once per iteration, ‘intentionality' where the computer is attributed to have some intelligence to look ahead in the code and evaluate such, and finally,`egocentrism' where students acted (not necessarily believed) that the computer had intelligence to`know' what they meant without their intentions being specified in the code. This behaviour was also noted by Perkins et. al. [PHH +89].
Many studies have been conducted into the more complex programming constructs such as loops and Boolean conditionals, and have found that there are ambiguities when translating the user's natural language knowledge of keywords such as WHILE and the Boolean operators NOT and AND in particular, to the programming language. It was commonly found that conditions on While loops were expected to be evaluated at all times, dropping the flow of control out of the loops as soon as the condition is false [MC99, SSP85, Pea86].
In the analysis of sample programs, it will be necessary to classify semantic errors in some way, to facilitate the design of a program which can identify these errors based on type. The representation of looping and Boolean constructs will require detailed consideration, as these are the two most common areas of semantic errors.
One other interesting proposal, put forward by Spohrer et al [SSP85], is that in 200 separate solutions to a problem by novice programmers, if you received two the same, they would be from students who collaborated in designing the solution. It will be educational to see if students indeed create very different programs solving the same problem, as it may complicate the analysis and detection of semantic errors by an automatic program.
Discovering the similarity of students' algorithmic development, is necessary to figure out if a semantic analysis program is feasible. Analysing beginner programmers' code will highlight which semantic problems are most common, and help with the design of an automated tool which could identify and highlight the problem.
Code needs to be collected at various stages of development by first year students studying CSE1301, but in order to be analysed for semantic errors, it must be syntactically correct, as syntax errors will not be dealt with - the compiler already checks, analyses and reports errors for this. Collecting examples at varying stages will allow identification of patterns in development, and may enable identification of where in the implementation of algorithms, semantic errors occur, if there is a commonality across the program segments collected.
Reviewing literature on pseudo-language design is crucial, as much research has been done into various representations of programming constructs, and common semantic errors. This will aid in the design of a verbose, clear and unambiguous language to which the C program will be converted. The pseudo-language will be developed from existing research on language design and semantic representation of programming constructs for beginners. The language may be tested on beginners to see how clear the representations of the more difficult programming constructs are in the new pseudo-language.
Once the pseudo-language has been designed, a parser will need to be written to parse the C programs, and a conversion tool to convert them to the pseudo-language. When developed, this tool will need to be tested on the original programs, and on common algorithms with introduced errors to make sure the conversion works well.
Further development of the program if feasible, will include semantic error checking, to automatically detect and highlight the semantic errors in a C program. This will also need to be tested on the original sample collected, as well as on common algorithms, with and without introduced errors, to ensure that the detection is reliable.
The parser and conversion tool will be custom written in Perl as a module, as this is an excellent language for parsing text. Matching common semantic problems may also use various existing Perl modules for pattern matching.
The program will be tested on the original programs collected for analysis, and on further collected programs from beginner programmers, increasing in complexity. These programs will all be written in C, and are required to be syntactically correct.
- Beginner programming
- Conclusion and Future Work
As seen in Chapter 3, much research has been conducted trying to discover how to design languages so that novices can learn more naturally. This research only related to new language design. So far, not much research has been found analysing methods or the feasibility of automated tools to make existing languages more accessible.
The analysis of students' code will prove enlightening, allowing us to see if there is any similarity in developed algorithms/solutions to a problem, or if as Sporher et.al. [SSP85] claim, the only similar code in 200 submissions is where students have collaborated. If they are indeed as varied as reported, it may pose a difficulty in reliably detecting semantic errors.
In the analysis of the submissions, errors will have to be classified, which will make designing the tool easier and more focused on discovering the common types of semantic errors made.
There has been research done on how to teach existing complex languages in a way that is easier for the students to comprehend, but an automated tool that can represent a student's solution in a language that they understand more would be enormously helpful in their learning process. It may provide that encouragement and knowledge that can get them past an impasse.
A tool such as the one proposed, would also be helpful for instructors wanting to improve the focus of their teaching by providing them with information on common misconceptions/errors made by students.
The pseudo-language will need to be carefully designed, so as to be accessible to students, utilising their natural language knowledge, but minimising ambiguities between it and the programmer's natural language. Careful analysis of looping and conditional constructs is needed, to decide on the clearest way to translate these from an imperative language (C), to the pseudo language.
Combining the analysis of novice programmer solutions, the design of an intuitive and natural pseudo representation of the complex language of C, and an automated tool will have many benefits, both to the programmers and the instructors.
[MC99] L. McIver and D. Conway. Grail: A zero'th programming language. In G Cummings, T. Okamoto, and L. Gomex, editors, 7th International Conference on Computers in Education ICCE'99, volume 2, pages 43-50. IOS Press, November 1999.
[Pan00] B. Pane, J. Myers. The influence of the psychology of programming on a language design: Project status report. 12th Annual Meeting of the Psychology of Programming Interest Group, 10-13 April 2000. PPIG 2000.
[PRM01] J. F. Pane, C. Ratanamahatana, and B. A. Myers. Studying the language and structure in non-programmers' solutions to programming problems. International Journal of Human-Computer Studies, 54:237-264, 2001.