Jump to content

Little man computer

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Sam Varner (talk | contribs) at 01:10, 14 September 2013 (→‎Example: Initialize RESULT and COUNT for each input.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Little Man Computer (LMC) is an instructional model of a computer, created by Dr. Stuart Madnick in 1965.[1] The LMC is generally used to teach students, because it models a simple von Neumann architecture computer - which has all of the basic features of a modern computer. It can be programmed in machine (albeit usually in decimal) or assembly code.

System architecture

The LMC model is based on the concept of a little man shut in a small room or a computer in this scenario. At one end of the room, there are 100 mailboxes (memory), numbered 0 to 99, that can each contain a 3 digit instruction or data (ranging from 000 to 999). Furthermore, there are two mailboxes at the other end labeled INBOX and OUTBOX which are used for receiving and outputting data. In the center of the room, there is a work area containing a simple two function (addition and subtraction) calculator known as the Accumulator and a resettable counter known as the Program Counter. The Program Counter holds the address of the next instruction the Little Man will carry out. This Program Counter is normally incremented by 1 after each instruction is executed, allowing the Little Man to work through a program sequentially. Branch instructions allow iteration (loops) and conditional programming structures to be incorporated into a program. The latter by setting the Program Counter to a non-sequential memory address if a particular condition is met (typically the value stored in the accumulator being zero or positive). As specified by the von Neumann architecture, memory contains both instructions and data. Care therefore needs to be taken to stop the Program Counter reaching a memory address containing data or the Little Man will attempt to treat it as an instruction. To use the LMC the user loads data into the mailboxes and then signals the Little Man to begin execution, starting with the instruction stored at memory address zero. Resetting the Program Counter to zero effectively restarts the program.

Execution cycle

See also: Instruction cycle

To execute a program, the little man performs these steps:

  1. check the Program Counter for the mailbox number that contains a program instruction (e.g. zero)
  2. fetch the instruction from the mailbox with that number
  3. increment the Program Counter (so that it contains the mailbox number of the next instruction)
  4. decode the instruction (includes finding the mailbox number for the data it will work on) (say it says get data from box 42)
  5. fetch the data from the mailbox with the number found in the previous step (for example, store the data in the accumulator)
  6. execute the instruction
  7. store the new data in the mailbox from which the old data was retrieved
  8. repeat the cycle or halt

Commands

While the LMC does reflect the actual workings of binary processors, the simplicity of decimal numbers was chosen to minimize the complexity for students who may not be comfortable working in binary/hexadecimal.

Instructions

Each LMC instruction is a 3 digit decimal number. The first digit represents the command to be performed and the final two digits represent the address of the mailbox affected by the command.

Instructions
Numeric code Mnemonic code Instruction Description
1xx ADD ADD Add the value stored in mailbox xx to whatever value is currently on the accumulator (calculator).
Note: the contents of the mailbox are not changed, and the actions of the accumulator (calculator) are not defined for add instructions that cause sums larger than 3 digits.
2xx SUB SUBTRACT Subtract the value stored in mailbox xx from whatever value is currently on the accumulator (calculator).
Note: the contents of the mailbox are not changed, and the actions of the accumulator are not defined for subtract instructions that cause negative results - however, a negative flag will be set so that 8xx (BRP) can be used properly.
3xx STA STORE Store the contents of the accumulator in mailbox xx (destructive).
Note: the contents of the accumulator (calculator) are not changed (non-destructive), but contents of mailbox are replaced regardless of what was in there (destructive)
5xx LDA LOAD Load the value from mailbox xx (non-destructive) and enter it in the accumulator (destructive).
6xx BRA BRANCH (unconditional) Set the program counter to the given address (value xx). That is, value xx will be the next instruction executed.
7xx BRZ BRANCH IF ZERO (conditional) If the accumulator (calculator) contains the value 000, set the program counter to the value xx. Otherwise, do nothing.
Note: since the program is stored in memory, data and program instructions all have the same address/location format.
8xx BRP BRANCH IF POSITIVE (conditional) If the accumulator (calculator) is 0 or positive, set the program counter to the value xx. Otherwise, do nothing.
Note: since the program is stored in memory, data and program instructions all have the same address/location format.
901 INP INPUT Go to the INBOX, fetch the value from the user, and put it in the accumulator (calculator)
Note: this will overwrite whatever value was in the accumulator (destructive)
902 OUT OUTPUT Copy the value from the accumulator (calculator) to the OUTBOX.
Note: the contents of the accumulator are not changed (non-destructive).
000 HLT/COB HALT/COFFEE BREAK Stop working.
DAT DATA This is an assembler instruction which simply loads the value into the next available mailbox. DAT can also be used in conjunction with labels to declare variables. For example, DAT 984 will store the value 984 into a mailbox.

Examples

Numeric

This program (instruction 901 to instruction 000) is written just using numeric codes. The program takes two numbers as input and outputs the difference. Notice that execution starts at Mailbox 00 and finishes at Mailbox 07. The disadvantages of this as a way of programming in machine code are discussed below.

Mailbox Numeric code Operation Comments
00 901 INBOX --> ACCUMULATOR INPUT the first number, enter into calculator (erasing whatever was there)
01 308 ACCUMULATOR --> MEMORY[08] STORE the calculator's current value (to prepare for the next step...)
02 901 INBOX --> ACCUMULATOR INPUT the second number, enter into calculator (erasing whatever was there)
03 309 ACCUMULATOR --> MEMORY[09] STORE the calculator's current value (again, to prepare for the next step...)
04 508 MEMORY[08] --> ACCUMULATOR (Now that both INPUT values are STORED in Mailboxes 08 and 09...)

LOAD the first value back into the calculator (erasing whatever was there)

05 209 ACCUMULATOR = ACCUMULATOR - MEMORY[09] SUBTRACT the second number from the calculator's current value (which was just set to the first number)
06 902 ACCUMULATOR --> OUTBOX OUTPUT the calculator's result to the OUTBOX
07 000 (no operation performed) HALT the LMC

Mnemonic

The convenience of mnemonics is made apparent from the assembly language version of the same program shown below - the programmer is no longer required to memorize a set of anonymous numeric codes, and can now program with a set of more memorable mnemonic codes (this example also uses labels as a further aid to programming).

This example program can be compiled and run on the LMC simulator[2] available on the website of York University (Toronto, Canada) or on the desktop applications written by Matthew Consterdine[3] or Mike Coley.[4] All these simulators include full instructions and sample programs, compilers to convert the assembly into machine code, control interfaces to execute and monitor programs, and a step-by-step detailed description of each LMC instruction.
INP
STA FIRST
INP
STA SECOND
LDA FIRST
SUB SECOND
OUT
HLT
FIRST DAT
SECOND DAT

Labels

Without labels the programmer is required to manually keep track of mailbox (memory) locations. In the numeric example, if a new instruction was to be inserted before the final HLT instruction then that HLT instruction would move from address 07 to address 08 (address labeling starts at address location 00). Suppose the user entered 600 as the first input. The instruction 308 would mean that this value would be stored at address location 08 and overwrite the 000 (HLT) instruction. Since 600 means "branch to mailbox address 00" the program, instead of halting, would get stuck in an endless loop.

To work around this difficulty, most assembly languages (including the LMC) allow the use of labels. A label is simply a word that is used to either name a memory address where an instruction or data is stored, or to refer to that address in an instruction.

When a program is assembled.

  • A label to the left of an instruction mnemonic is converted to the memory address the instruction or data is stored at.
  • A label to the right of an instruction mnemonic takes on the value of the memory address referred to above.

In the assembly language example which uses mnemonics and labels, if a new instruction was inserted before the final HLT instruction then the address location labeled FIRST would now be at memory location 09 rather than 08 and the STA FIRST instruction would be converted to 309 (STA 09) rather than 308 (STA 08) when the program was assembled.

Labels are therefore used to:

  • identify a particular instruction as a target for a BRANCH instruction
  • identify a memory location as a named variable (using DAT) and optionally load data into the program at assembly time for use by the program (this use is not obvious until one considers that there is no way of adding 1 to a counter. One could ask the user to input 1 at the beginning, but it would be better to have this loaded at the time of assembly)

Example

This program will take a user input, and count down to zero. 

     INP
LOOP SUB ONE  // Label this memory address as LOOP, The instruction will subtract the value stored at ONE from the accumulator
     OUT
     BRZ QUIT // If the accumulator value is 0, jump to the memory address labeled QUIT
     BRA LOOP // If the accumulator value is not 0, jump to the memory address labeled LOOP
QUIT HLT      // Label this memory address as QUIT
ONE  DAT 1    // Store the value 1 in this memory address, and label it ONE (variable declaration)

This program will take a user input, square it, output the answer and then repeat. Entering a zero will end the program.
(Note: an input that results in an output greater than 999 will cause an error due to the LMC 3 digit number limit). 

START   LDA ZERO     // Initialize for multiple program run
        STA RESULT
        STA COUNT
        INP          // User provided input
        BRZ END      // Branch to program END if input = 0
        STA VALUE    // Store input as VALUE
LOOP    LDA RESULT   // Load the RESULT
        ADD VALUE    // Add VALUE, the user provided input, to RESULT
        STA RESULT   // Store the new RESULT
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        SUB VALUE    // Subtract the user provided input VALUE from COUNT
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        BRA LOOP     // Branch to LOOP to continue adding VALUE to RESULT
ENDLOOP LDA RESULT   // Load RESULT
        OUT          // Output RESULT
        BRA START    // Branch to the START to initialize and get another input VALUE
END     HLT          // HALT - a zero was entered so done!
RESULT  DAT          // Computed result (defaults to 0)
COUNT   DAT          // Counter (defaults to 0)
ONE     DAT 1        // Constant, value of 1
VALUE   DAT          // User provided input, the value to be squared (defaults to 0)
ZERO    DAT          // Constant, value of 0 (defaults to 0)

(Note: DAT's default to the value 0 because the default value in all memory locations in Little Man Computer is 0, and so does not need to be set to 0 - any other number however must be specified.)

References

  1. ^ "Little Man Computer". Illinois State University. May 1, 2000. Retrieved March 8, 2009.
  2. ^ Chen, Stephen Y.; Cudmore, William C. "The Little Man Computer". York University. Retrieved October 7, 2010.
  3. ^ Consterdine, Matthew R. "The Little Man Computer". Retrieved October 18, 2011.
  4. ^ Coley, Mike. "The Little Man Computer". Retrieved April 12, 2012.

Simulators

Retrieved from "https://en.wikipedia.org/w/index.php?title=Little_man_computer&oldid=572829233"