CSCE 434 Lecture 8

« previous | Wednesday, September 11, 2013 | next »

Substitute professor

Dr. Robert Mentsker^?

Debugging

By Editing

most all students start debugging like this.

By Interacting

use a debugger superficially

Find out a little how the program works while running

By Repeating

"trial by error" on how to debug software (and hardware) wastes a lot of time; bugs randomly stumbled across

By Thinking

Born of Proofs in Mathematics

Multidisciplinary

Self-Awareness of

• Assumptions
• Methodologies
• Tendencies to make mistakes

Problem Solving in Mathematics

Book: Mathematical Problem Solving

• Describes how to solve math problems
• Ways of thinking to approach problem solving in general
• There is proof that this works

Hierarchy of Reasoning

1. Resources: General factual knowledge
2. Heuristics: Rules of thumb for problem solving (Another book: How to Solve It by Polya)
3. Control: "Am I making any progress?"
4. Belief Systems

Analogous Methods in Computer Science

Analogous things in debugging:

1. Tactics (knowing how to do something in code; like printing a variable)
2. Heuristics (same as above)
3. Strategies

Binary Search

Control Structures

We can find that we're making progress using evaluating mechanism.

For example, reproducing an error

• narrow scope of bug locality
• reduce effort required to reproduce

Is the number of disproved hypotheses increasing?

Assumptions

Data has to be sorted

We can apply binary search to debugging code.

Use topological sorting to induce a linear ordering of function/method calls (profilers can be used to do this for you)

This method does not apply globally: event driven systems (like GUIs and OSs) cannot be topologically ordered.

Good Test Suite

Has to be comprenensive; may even take 1 hour to complete

This can be automated with CI tools

Compilers

Data Structures

It is vital to store the source code position throughout the compilation process.

Checking Data Validity

Why is it important to check validity of Data Structures?

Catch many problems between each "filter pass" of a compiler by traversing data structure

You may have to build several checkers for each phase because information may be added (e.g. register numbers) or lost (e.g. complex types)

Use debugging breakpoints and watch points to pause/validate

Assertions of input for each input; maintaining an invariant

Displaying Data Structures

Insert calls to display data structures

The data structures can get very complicated

This can be used to find problems, but is very expensive; it should only be done during testing)

It can also make some problems (like stack corruption or optimization during meta-compilation) go away

dot can be used to display graphs visually

Whatever you print you have to read; cut it down if possible

Printing Elements of Structure

Binary flags are common for lists of boolean attributes. Don't print out Hex code for flags; convert them to tests.

Enumerations are common (e.g. Type Names, Operator Names, etc.), so create a way to convert enum values to human-readable text.

Human-readable values can be long, so create a terse (just dump the data) and verbose (more readable) way of printing

Summary

1. Write hypotheses down
2. Tactics: Should tell you information that invalidate or validate a hypothesis; what's happening with program
3. Heuristics suggest new hypotheses

Build debugging structures into compiler

it will be easy to spot problems later

Meta-thinking

Why am I doing this?

Keep simple records to track hypotheses and progress

Know your hypothesis: "What is my hypothesis?"