Lecture 3 | Programming Methodology (Stanford)

TL;DR

Two common logical errors trip up beginner Karel programmers: infinite loops and off-by-one bugs. An infinite loop happens when a condition like 'while front is clear, turn left' never becomes false. An off-by-one bug means an action is done one time too few, such as forgetting to place a final beeper after a loop exits.

Transcript

this presentation is delivered by the Stanford center for professional development so a little bit of additional background on Carole before we dive into the real meat of things okay one thing you may have noticed all the Carroll code that you've either started writing if you're already working on an assignment number one or all the code that we wr... Read More

Key Insights

• Karel is implemented in Java, since all Karel code lives in files ending with .java, but students should use only the constructs shown in class and the Karel reader for Karel assignments rather than mixing in general Java.
• An infinite loop is a loop that keeps going forever, illustrated by shampoo instructions that say rinse, lather, and repeat, which would trap you in the shower for life because the repeat step never ends.
• A syntactically valid Karel program can still fail to work as intended, such as 'while front is clear, turn left' when Karel stands with no walls around him, causing him to turn left forever without escaping.
• The off-by-one bug, affectionately called an OBOB, means you forgot to do something one more time than seemed logically necessary, a common error that has been made by millions of qualified programmers.
• Filling a row of beepers with 'while front is clear, put beeper and move' leaves the last corner empty because Karel stops when his front is blocked before placing the final beeper.
• The fix for that off-by-one bug is to add a final put-beeper instruction after the loop exits, since Karel has not yet placed a beeper on the corner where his front became blocked.
• A comment is a way to put text in a program that another human can read and understand, with no impact at all on how the program executes, supporting the principle of writing programs understandable by people.
• Comments come in two forms: a block comment starting with slash-star and ending with star-slash that can span multiple lines, and a single-line comment starting with slash-slash that runs to the end of the line.

Questions & Answers

Q: Can you use Java code in Karel assignments?

No. For the purpose of the Karel assignments you should just use the constructs shown in class and in the Karel reader, even if you already know some Java. Karel is in fact implemented in Java, which is why all Karel code lives in files ending with .java, but mixing general Java into Karel assignments is not allowed. Those Karel constructs still give you plenty of material to work with, and starting Monday the course leaves Karel behind and moves fully into Java.

Q: How do you stop a Karel program that is stuck?

To stop a Karel program that is running, such as one stuck spinning in the corner, you simply go up to the little icon or control at the top of the window that lets you close the window, and close it. Karel will be okay and knows how to deal with that. Making an empty program called 'stop' does not work; closing the window is the correct way to halt a program that is not stopping on its own.

Q: What is an infinite loop in programming?

An infinite loop is a loop that keeps going forever. The lecture uses shampoo instructions that say rinse, lather, and repeat as an analogy: following them literally would keep you in the shower for the rest of your life because the repeat step never ends. In Karel, code like 'while front is clear, turn left' becomes an infinite loop when Karel stands with no walls around him, since his front never becomes blocked and he turns left forever.

Q: Why does 'while front is clear, turn left' loop forever?

This code loops forever when Karel is standing in a world with no walls around him. The intention might be that eventually Karel would turn to face something and his front would no longer be clear, but if there are no walls, his front never becomes blocked. So he just keeps turning left on the same corner endlessly. The syntax is perfectly valid, but the program fails to do what was intended, making it a logical rather than a syntax error.

Q: What is an off-by-one bug (OBOB)?

An off-by-one bug, affectionately called an OBOB, means you forgot to do something one more time than you really needed to, even though logically it did not seem like you needed to. It is a common logical error, not a syntax error. The lecture reassures students it has been done millions of times by very qualified programmers, so encountering it is normal and nothing to feel adrift or alone about when it happens.

Q: Why does filling a row of beepers leave the last corner empty?

When you write 'while front is clear, put a beeper and move to the next corner', Karel places beepers as he advances, but stops as soon as his front is no longer clear. Before he can put down the beeper on that last corner, he checks his front, finds it blocked, and stops. This leaves one corner without a beeper. It is an off-by-one bug because there was one more action he needed to do that the loop did not cover.

Q: How do you fix the off-by-one bug when filling a row of beepers?

The fix is to add a final put-beeper instruction after the loop ends. Once Karel exits the loop his front is no longer clear, but he has not yet placed a beeper on the current corner. Adding one more put-beeper after the loop places a beeper on that last spot, completing the row. After saving and rerunning the program, the row fills correctly and the off-by-one bug is resolved.

Q: What is a comment and how do you write one?

A comment is a way to put text in your program that another human being can read and understand, and it has no impact on the execution of the program at all. It supports the software engineering principle of writing programs understandable by people, not just machines. A block comment starts with a slash and a star and can span multiple lines until you close it with a star and a slash. A shorthand single-line comment starts with slash-slash and runs to the end of that line.

Summary

In this video, the instructor discusses common errors, commenting, decomposition, and top-down design in programming. The instructor also demonstrates a stepwise refinement process to write a program that doubles the number of beepers on a corner.

Questions & Answers

Q: Can I use Java in conjunction with Karel?

For the purpose of the Karel assignments, you should only use the constructs that you've been shown in class and in the Karel reader. You can use Java for future assignments starting from Monday.

Q: How do I stop the program in Karel?

To stop the program, you can simply close the window using the little icon or button in the top corner of the window. Karel knows how to deal with it.

Q: What are some common errors in Karel programs?

One common error is an infinite loop, where the program keeps running forever. This can happen if the condition in a loop never becomes false. Another common error is an off-by-one bug, where you forget to do something one more time than necessary, leading to unexpected behavior.

Q: Can you explain the concept of comments in programming?

Comments are a way to include human-readable text in your program that does not affect the execution of the program. They are used to explain and clarify what the code is doing. In Java, comments can be written using the // syntax for single-line comments or /* ... */ syntax for multi-line comments.

Q: Should I comment all my methods in Karel programs?

Yes, it's a good practice to comment your methods in Karel programs. Comments help other programmers understand what your method does and its purpose. They can also help with debugging by indicating what the method's preconditions and postconditions are.

Q: Is it necessary to write comments for individual lines in a Karel program?

It is not necessary to write comments for every line in a Karel program. However, you should have comments for each method explaining what the method does. It's also helpful to have comments at the top of the file explaining what the program does.

Q: What is decomposition in programming?

Decomposition is the process of breaking down a problem or task into smaller subproblems or steps. It involves thinking at a higher level of abstraction and breaking things down into smaller, more manageable pieces. Decomposition helps in understanding and solving complex problems.

Q: What is top-down design?

Top-down design is a problem-solving approach where you start with a high-level description of the problem and gradually break it down into smaller subproblems. You focus on solving one subproblem at a time by defining methods or functions for each subproblem. This approach helps in organizing and structuring your code.

Q: How do you write a program in Karel to double the number of beepers on a corner?

To write a program in Karel to double the number of beepers on a corner, you can use a stepwise refinement process. First, start with a high-level description of the problem. Break it down into smaller steps and define methods to accomplish each step. In this case, the steps would involve picking up one beeper, putting down two beepers, and moving them back. Write the code for each step, and ensure that the preconditions and postconditions are satisfied in each method. Finally, put it all together in the run method to execute the program.

Q: What is the algorithm to double the number of beepers in Karel's world?

The algorithm to double the number of beepers in Karel's world is a process of picking up one beeper, putting down two beepers next door, and repeating this process until all the beepers are transferred. Once transferred, move back to the starting position and repeat the process if desired.

Q: Can I run the double beepers program multiple times to increase the number of beepers?

While you can run the double beepers program multiple times, there is a limit to the number of beepers that can be handled by Karel. If the number of beepers exceeds a certain threshold (around 100,000), the program may encounter issues or stop functioning properly. It is unlikely that you would need to reach such high numbers in Karel programs.

Summary & Key Takeaways

• The lecture opens by clarifying that Karel is built in Java because all Karel code sits in .java files, but students must restrict themselves to the constructs taught in class and the Karel reader for Karel assignments. Starting Monday the course leaves Karel behind and moves into Java itself.

• Two common logical errors are demonstrated. An infinite loop, like the shampoo 'rinse, lather, repeat' analogy, occurs when a loop condition such as 'while front is clear, turn left' never becomes false, leaving Karel turning forever with no wall ever appearing in front of him.

• The off-by-one bug (OBOB) is shown by filling a row of beepers: a while-front-is-clear loop stops one corner short, so a final put-beeper must be added after the loop. Comments, written with slash-star or slash-slash, let humans understand programs without affecting execution.