Browse Prior Art Database

MICHIGAN ALGORITHM DECODER

IP.com Disclosure Number: IPCOM000128762D
Original Publication Date: 1966-Aug-01
Included in the Prior Art Database: 2005-Sep-19

Publishing Venue

Software Patent Institute

Related People

Elliot Organick: AUTHOR [+5]

Abstract

";Begin at the beginning,"; the King said gravely, ";and go on till you come to the end; then stop."; Lewis Carroll, Alice in Wonderland In presenting a problem to a digital computer for solution, one transmits to the machine a procedure for solving it (usually called an algorithm for the solution of that problem), and the data for a particular case. The algorithm must be stated unambiguously and completely. As a simple example, let us consider the problem of determining the largest number in a collection of n + 1 numbers A = {a 0 , a l , a 2 ,...,a n } with n ≥ 1. A verbal description of the procedure (algorithm) might be (1) Pick up the first number. (2) Compare it with the second number. (3) If the first is larger or if they are equal, keep the first one. (4) If the second is larger, keep the second one. (5) Whichever one was saved from this comparison is now compared with the third number. (6) Continue to repeat Steps 2 through 5 (each time moving down the list) until the n + 1st number has been included in the comparison. (7) The number which has been finally saved is then the largest number in the collection A. Unfortunately, this method of description is not very precise. Such words as ";compare";, ";moving down the list";, and ";finally saved"; should really be spelled out more exactly. The following restatement of the procedure would probably be more suitable: (1) Let Z = a 0 . (2) Let j = 1. (3) If j > n, the problem is done, [ Footnote ] This test is redundant the first time, but after n times through Steps 3 through 6 it will terminate the process for us. It is redundant the first time because if n ≥ 1 as set forth in the problem statement, then for j = 1, j > n will always be false. go to Step 7; otherwise, go on. (4) If Z < a j , let Z = a j ; otherwise, go on. (5) Let j increase by 1. (6) Return to Step 3. (7) Z is the answer.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 2% of the total text.

Page 1 of 133

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

MICHIGAN ALGORITHM DECODER

AUGUST

The Michigan Algorithm Decoder

(The MAD Manual)

Revised Edition -- 1966

"Though this be madness, yet there is method in't."

Shakespeare: Hamlet

The Michigan Algorithm Decoder (MAD) is a computer program which translates statements describing algorithms into the equivalent machine instructions. This descriptive language -- also called MAD -- is explained in this manual. ALGOL 58, which was proposed at one time as a standard language for the description of algorithms, was used as a pattern for this language; the original translating program was written in 1959 for an IBM 704 computer with 8192 words of core storage. Translators were subsequently written for the IBM 709/90/94 machines by the University of Michigan Computing Center staff. Interested groups elsewhere have adapted the language for the IBM 7040, Philco 210-211, and Sperry-Rand 1107 machines. The translator was originally included in the University of Michigan Executive System (UMES), but its construction as a subroutine has permitted its inclusion in a number of different operating systems.

Over the years a number of useful extensions to the language have been incorporated. These were documented as addenda and minor revisions in the many printings of the first edition, which was written by Arden, Galler, and Graham. This edition is a major revision -- one by Professor Elliott Organick of the University of Houston -- which incorporates these addenda and corrects a number of shortcomings of the early version. Donald W. Boettner and Bruce J. Bolas of the University of Michigan assisted in this revision.

The MAD language has been widely used by the students and staff of the University of Michigan and it has been used at a number of other centers as well. There are a number of versions extant and some of these may not contain all of the features described herein.

TABLE OF CONTENTS

CHAPTER I INTRODUCTION.....1

CHAPTER II DESCRIPTION OF THE LANGUAGE.....13

1. Constants, Identifiers, Operations and Expressions.....13
1.1 Constants.....13
1.1.1 Integer Constants.....13
1.1.2 Floating Point Constants.....13

University of Michigan Computing Center Page 1 Aug 01, 1966

Page 2 of 133

MICHIGAN ALGORITHM DECODER

1.1.3 Alphabetic Constants.....14
1.1.4 Boolean Constants.....14
1.1.5 Octal Constants.....14
1.1.6 Constants of Other Modes.....14
1.2 Variables.....15
1.3 Statement Labels.....15
1.3.1 Statement Label Constants.....15
1.3.2 Statement Label Variables.....15
1.4 Functions.....15
1.5 Arithmetic Operations.....16
1.6 Arithmetic Expressions.....17
1.7 Boolean Operations.....18
1.8 Boolean Expressions.....18
1.9 Parentheses Conventions.....19
1.10 Mode of Expressions.....20
1.11 Subscript Expressions.....22
1.12 Block Notation.....22
1.13 Function Name Constants and Variables.....22

2.Statements (Executable).....23
2.1 Assignment Statement.....23
2.2 Transfer Statement.....24
2.3 Cond...