Introduction to Computer Engineering CS ECE 252 Spring 2010 Prof Guri Sohi Computer Sciences Department University of Wisconsin Madison Chapter 6 Programming Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Solving Problems using a Computer Methodologies for creating computer programs that perform a desired function Problem Solving How do we figure out what to tell the computer to do Convert problem statement into algorithm using stepwise refinement Convert algorithm into LC 3 machine instructions Debugging How do we figure out why it didn t work Examining registers and memory setting breakpoints etc Time spent on the first can reduce time spent on the second 6 3 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Stepwise Refinement Also known as systematic decomposition Start with problem statement We wish to count the number of occurrences of a character in a file The character in question is to be input from the keyboard the result is to be displayed on the monitor Decompose task into a few simpler subtasks Decompose each subtask into smaller subtasks and these into even smaller subtasks etc until you get to the machine instruction level 6 4 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Problem Statement Because problem statements are written in English they are sometimes ambiguous and or incomplete Where is file located How big is it or how do I know when I ve reached the end How should final count be printed A decimal number If the character is a letter should I count both upper case and lower case occurrences How do you resolve these issues Ask the person who wants the problem solved or Make a decision and document it 6 5 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Three Basic Constructs There are three basic ways to decompose a task Task True False Test condition Subtask 1 Test condition False True Subtask 2 Sequential Subtask 1 Subtask 2 Subtask Conditional Iterative 6 6 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Sequential Do Subtask 1 to completion then do Subtask 2 to completion etc Get character input from keyboard Count and print the occurrences of a character in a file Examine file and count the number of characters that match Print number to the screen 6 7 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Conditional If condition is true do Subtask 1 else do Subtask 2 True Test character If match increment counter file char input False Count Count 1 6 8 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Iterative Do Subtask over and over as long as the test condition is true Check each element of the file and count the characters that match more chars to check False True Check next char and count if matches 6 9 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Problem Solving Skills Learn to convert problem statement into step by step description of subtasks Like a puzzle or a word problem from grammar school math What is the starting state of the system What is the desired ending state How do we move from one state to another Recognize English words that correlate to three basic constructs do A then do B sequential if G then do H conditional for each X do Y iterative do Z until W iterative 6 10 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display LC 3 Control Instructions How do we use LC 3 instructions to encode the three basic constructs Sequential Instructions naturally flow from one to the next so no special instruction needed to go from one sequential subtask to the next Conditional and Iterative Create code that converts condition into N Z or P Example Condition Is R0 R1 Code Subtract R1 from R0 if equal Z bit will be set Then use BR instruction to transfer control to the proper subtask 6 11 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Code for Conditional Exact bits depend on condition being tested True Test Condition Subtask 1 Instruction A False PC offset to address C Generate Condition B 0000 C Subtask 1 Subtask 2 0000 111 D C Subtask 2 Next Subtask Unconditional branch to Next Subtask D Next Subtask Assuming all addresses are close enough that PC relative branch can be used PC offset to address D 6 12 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Code for Iteration Exact bits depend on condition being tested Test Condition Instruction A False Generate Condition 0000 True C B Subtask Subtask 0000 111 C Next Subtask PC offset to address C Unconditional branch to retest condition Assuming all addresses are on the same page A Next Subtask PC offset to address A 6 13 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Example Counting Characters A START Initialize Put initial values into all locations that will be needed to carry out this task Input a character Set up a pointer to the first location of the file that will be scanned Get the first character from the file Zero the register that holds the count Input a character Then scan a file counting occurrences of that character Finally display on the monitor the number of occurrences of the character up to 9 B STOP C Initial refinement Big task into three sequential subtasks START Scan the file location by location incrementing the counter if the character matches Display the count on the monitor STOP 6 14 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Refining B B Yes B Scan the file location by location incrementing the counter if the character matches B1 Done No Test character If a match increment counter Get next character Refining B into iterative construct 6 15 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Refining B1 Yes B Yes B1 Done No Test character If a match increment counter Get next character Done No B1 B2 Test character If matches increment counter B3 Get next character Refining B1 into sequential subtasks 6 16 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Refining B2 and B3 Yes Done No B2 Yes Yes Done No R1 R0 No R2 R2 1 B1 B2 Test character If matches increment counter B3 B3 Get next character R3