{
"cells": [
{
"cell_type": "markdown",
"id": "6543120d",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Using Stacks, Introduction to debugging\n",
"\n",
"#### CS 66: Introduction to Computer Science II"
]
},
{
"cell_type": "markdown",
"id": "11cf4d01",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## References for this lecture\n",
"\n",
"\n",
"_The __Stack__ Abstract Data Type_ Problem Solving with Algorithms and Data Structures using Python, Section 4.4: [https://runestone.academy/ns/books/published/pythonds/BasicDS/TheStackAbstractDataType.html](https://runestone.academy/ns/books/published/pythonds/BasicDS/TheStackAbstractDataType.html)\n",
"\n",
"\n",
"Visual Studio Python Debugging documentation:\n",
"[https://code.visualstudio.com/docs/python/debugging](https://code.visualstudio.com/docs/python/debugging)\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "df6e0fc9",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Group Activity Problem 1\n",
"\n",
"Before running the code below, manually step through it line by line and write down what values are in the stack.\n",
"\n",
"What do you think will be printed by this code?\n",
"\n",
"After you have come to an agreement, run the code and see if you were right."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b5aca9a5",
"metadata": {},
"outputs": [],
"source": [
"from pythonds.basic import Stack\n",
"\n",
"my_stk = Stack()\n",
"my_stk.push(4)\n",
"my_stk.push(7)\n",
"my_stk.push(11)\n",
"my_stk.pop()\n",
"my_stk.push(8)\n",
"my_stk.pop()\n",
"my_stk.push(5)\n",
"my_stk.push(9)\n",
"\n",
"print(\"Size:\",my_stk.size())\n",
"\n",
"while not my_stk.isEmpty():\n",
" print(my_stk.pop())"
]
},
{
"cell_type": "markdown",
"id": "83504f60",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Example Application: reverse\n",
"\n",
"We can use a stack to reverse a string.\n",
"\n",
"1. Scanning the string from left-to-right, push each character\n",
"2. Pop each character, adding it onto an accumulator string until the stack is empty"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "128a9378",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "47e040de",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from pythonds.basic import Stack\n",
"\n",
"def reverse_string(astring):\n",
" \n",
" char_stack = Stack()\n",
" \n",
" for char in astring:\n",
" char_stack.push(char)\n",
" \n",
" rev_astring = \"\"\n",
" \n",
" while not char_stack.isEmpty():\n",
" rev_astring += char_stack.pop()\n",
" \n",
" return rev_astring\n",
"\n",
"print(reverse_string(\"this is a test\"))"
]
},
{
"cell_type": "markdown",
"id": "e6785591",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Example Application: Matching parentheses\n",
"\n",
"We can use a stack to check for matched sets of parentheses.\n",
"\n",
"Some test cases\n",
"\n",
"correctly matched:\n",
"\n",
"```\n",
"\"Here is a profound message (plus some less profound words (which are in parentheses))\"\n",
"\"(()(()))\"\n",
"\"(()()()())\"\n",
"\"(((())))\"\n",
"\"(()((())()))\"\n",
"```\n",
"\n",
"not matched:\n",
"\n",
"```\n",
"\"Here is a profound message (plus some less profound words (which are in parentheses)\"\n",
"\"()(()()\"\n",
"\"((((((())\"\n",
"\"()))\"\n",
"\"(()()(()\"\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3718037c",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "9a998425",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"def check_parens(astring):\n",
" \n",
" paren_stack = Stack()\n",
" \n",
" #checking each character in the string\n",
" for char in astring:\n",
" \n",
" if char == \"(\":\n",
" paren_stack.push(char)\n",
" \n",
" elif char == \")\":\n",
" if paren_stack.isEmpty():\n",
" return False #there's no ( to match this )\n",
" else:\n",
" paren_stack.pop()\n",
" \n",
" if paren_stack.isEmpty():\n",
" return True #all parens matched\n",
" else:\n",
" return False #there is an extra ( that was unmatched\n",
" \n",
"print( check_parens(\"(()(()))\") )"
]
},
{
"cell_type": "markdown",
"id": "4b3dbfda",
"metadata": {},
"source": [
"## Debugging Problems...\n",
"\n",
" Is my issue a formal exception thrown by the code, resulting in a stack trace?\n",
" Do my users understand or even see this problem?\n",
" Is the problem only present on certain inputs or all of them?\n",
" Is the problem something I know is somewhere in the code even though everything seems to work (so far)?\n",
" Can I do away with my problem completely or does fixing it introduce other problems?\n",
" What happens to me or someone else if I don't fix this problem in time?"
]
},
{
"cell_type": "markdown",
"id": "237af08e",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Code isn't perfect. Some of those imperfections Python will never detect - sometimes we just write code that doesn't do what we think it does. Other times, we might really break the rules - Python will detect an error and will make it our problem.\n",
"\n",
"When the interpreter runs into an issue with your code, it can do a number of things. The code that invoked that code may suppress that error (e.g. try-except). More likely, your code will report that error to you. \n",
"\n",
"It may be the only error in your code, but it may not be. The interpreter will let you know immediately about the first error that it finds, and execution will halt. Upon fixing that error, you may find there are others - or that you've created more problems by fixing the first one! This is the joy of programming."
]
},
{
"cell_type": "markdown",
"id": "727003f5",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Here is some code that doesn't throw an error even though it has a serious problem:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "73adf63f",
"metadata": {},
"outputs": [],
"source": [
"#return the unique multiple of x and y\n",
"def multiply(x,y):\n",
" return x+y\n",
"\n",
"print(multiply(2,3))"
]
},
{
"cell_type": "markdown",
"id": "2203758d",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Consider the following code:\n",
"\n",
"It contains a (fatal) error - not only one that makes the program behave poorly but, in fact, prevents the program from running completely. An actual exception is thrown: a TypeError. \n",
"\n",
"Along with this error, we get a stack trace: it is the contents of the stack of function invocations. It can be a bit hard to read but we need to try, or we won't find the error. In any case, it makes us detectives."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "af7865fc",
"metadata": {
"scrolled": true,
"slideshow": {
"slide_type": "-"
}
},
"outputs": [],
"source": [
"from math import fabs\n",
"import py_compile\n",
"import random\n",
"\n",
"chars = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','.','/','&','$','@','!','*','(',')','-','=','+','_',\"\\'\",'~',':',';',\"\\\"\",\"<\",\">\",\"\\n\"]\n",
"\n",
"def randomLength():\n",
" return random.randint(0,20000)\n",
"\n",
"def random_letter():\n",
" return chars[random.randint(0,len(chars))]\n",
"\n",
"def randomString(i):\n",
" random_string = \"\"\n",
" for x in range(i):\n",
" random_string += random_letter()\n",
" return random_string\n",
"\n",
"def compile_random_Python_Programs_forever():\n",
" # while(True):\n",
" progr = randomString(randomLength())\n",
" print(progr)\n",
" f = open(\"hopefully_a_program.py\",\"w\")\n",
" f.write(progr)\n",
" try: \n",
" pr = py_compile.compile(f)\n",
" print(\"Everyone gets an A!\")\n",
" #break\n",
" except:\n",
" print(\"not a python program\")\n",
"\n",
"compile_random_Python_Programs_forever()"
]
},
{
"cell_type": "markdown",
"id": "c8bca4de",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Before we get into techniques, a few comments about why it is worthwhile to learn how to debug code:\n",
" \n",
" 1. Whether the code is yours or somebody else's, broken code cannot hang around in a 'living' environment for long. If you upload broken code to a production environment, increasingly frustrated people will start walking into your office looking over your shoulder until you find your error and correct it. We need techniques for finding errors, not random luck.\n",
" \n",
" 2. It doesn't feel good to be totally helpless in the face of incomprehensible error (a stack trace)\n",
" \n",
" 3. The only feedback you are always guaranteed to get from a compiler is cryptic errors and stack traces. We need to know how to interpret these no matter what kind of code we are writing, in what context we are writing it, etc."
]
},
{
"cell_type": "markdown",
"id": "750ac385",
"metadata": {},
"source": [
"## Group Activity Problem 2: Debugging a simple program\n",
"\n",
"Try debugging the following program - how did you do it? Before you make any changes to the code, be able to explain to your group members why you think that change is worth making.\n",
"\n",
"Again, the following code is broken. We don't know if it's broken in one place or ten. Find out!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "85339cd5",
"metadata": {},
"outputs": [],
"source": [
"#exp takes two parameters: x,y both integers - and raises x to the power y\n",
"def exp(x,y):\n",
" temp = x\n",
" for i in len(y):\n",
" temp*=x\n",
" return temp \n",
" \n",
"print(\"hello\")\n",
"z = exp(2,5) \n",
"print(z)"
]
},
{
"cell_type": "markdown",
"id": "1e182779",
"metadata": {},
"source": [
"Suppose we didn't even look at the stack trace or error - only the output. What's your biggest clue as to where the error might lie?"
]
},
{
"cell_type": "markdown",
"id": "c86e44a5",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## A basic, but solid technique for debugging: print statements\n",
"\n",
"Our biggest clue above is that \"hello\" was printed before the stack trace, but nothing else - even though we may have expected to reach the other print statement inside of the function we called. Why wasn't it printed? Because we didn't make it that far before running into an error.\n",
"\n",
"How can we turn this idea into a tool?\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7c6f7c41",
"metadata": {},
"outputs": [],
"source": [
"def exp(x,y):\n",
" print(\"testing1\")\n",
" temp = x\n",
" print(\"testing2\")\n",
" for i in len(y):\n",
" print(\"testing3\")\n",
" temp*=x\n",
" print(\"testing4\")\n",
" \n",
" print(\"testing5\") \n",
" print(x) \n",
" \n",
"print(\"hello\")\n",
"z = exp(2,5) \n",
"print(\"testing6\")\n",
"print(z)\n"
]
},
{
"cell_type": "markdown",
"id": "ffb82c50",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Group Activity Problem 3 - a harder case\n",
"\n",
"\n",
"Try debugging the following program. If you got it working - would you say there is some technique to *how* you got it working? Is your approach generalizable? What about it can be applied to other problems? Are there situations where your technique doesn't work?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5f7c913b",
"metadata": {},
"outputs": [],
"source": [
"def calculate_pay(wage,hours):\n",
" if hours <= 40:\n",
" pay = wage*hours\n",
" elif(hours>40):\n",
" overtime_hours = hours-40\n",
" pay = (wage*40) + (wage*1.5*overtimehours)\n",
"\n",
" print(\"Total pay:\" pay)\n",
" \n",
"calculate_pay(10,20)"
]
},
{
"cell_type": "markdown",
"id": "1f10a969",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Group Activity Problem 4 - we don't even know what this is but we'll get it working\n",
"\n",
"Copy the following code into a python file, then use information given to you by the stack trace to make this code run.\n",
"You don't have to make it pretty, and you don't even need to know exactly what everything does. The goal here is to understand where errors might be coming from, what the errors mean, and how to make them go away. Your chances of understanding what's going on in someone else's code are far better when you can actually see some output.\n",
"\n",
"Hint: solve_ivp is a real method - it's inside scipy.integrate. How would you have found this out without this hint?\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7cac4ce4",
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"#Lotka-Volterra predator-prey model\n",
"import numpy as np\n",
"import scipy.integrate as intg\n",
"import matplotlib.pyplot as plt\n",
"\n",
"def lotkavolterra(t, z, a, b, c, d):\n",
" x, y = z\n",
" return [a*x - b*x*y, -c*y + d*x*y]\n",
"\n",
"sol = solve_ivp(lotkavolterra, [0, 15], [10, 5], args=(1.5, 1, 3, 1), dense_output=True)\n",
"\n",
"t = np.linspace(0, 15, 300)\n",
"z = sol.sol(t)\n",
"plt.plot(t, z.T)\n",
"plt.xlabel('t')\n",
"plt.legnd(['x', 'y'], shadow=True)\n",
"plt.title('Lotka-Volterra System')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "2ae45fc5",
"metadata": {},
"source": [
"## VSCode debugging\n",
"\n",
"Let's look at the VSCode debugging mode. Other tools you use will have a very similar style."
]
}
],
"metadata": {
"celltoolbar": "Slideshow",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.6"
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 5
}