forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
ibcm.html
120 lines (120 loc) · 6.46 KB
/
ibcm.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>Program and Data Representation: Itty Bitty Computing Machine (IBCM)</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../markdown.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1
id="program-and-data-representation-itty-bitty-computing-machine-ibcm">Program
and Data Representation: Itty Bitty Computing Machine (IBCM)</h1>
<p><a href="../readme.html">Go up to the main README file</a> (<a
href="../readme.md">md</a>)</p>
<p>The Itty Bitty Computing Machine (IBCM) is a machine language
designed to be simple enough to teach the concepts of machine language,
while being complicated enough to write any program. The <em>IBCM
computational model</em> (which is slighly different than the IBCM
presented here) is <a
href="http://en.wikipedia.org/wiki/Turing_complete">Turing complete</a>.
IBCM is meant to be taught in a week of lecture.</p>
<p>IBCM was described in a SIGCSE 2011 article: “<a
href="http://dl.acm.org/citation.cfm?id=1953273">IBCM: The Itty Bitty
Computing Machine</a>” by Aaron Bloomfield and William Wulf (Proceedings
of the 42nd ACM Technical Symposium on Computer Science Education
(SIGCSE), March 2011, Dallas, TX); that article describes the Turing
completeness of IBCM. Due to copyright restrictions, that article cannot
be included in this repository. However, much of that material is
similar to the material found in the <a href="../book/index.html">book
chapter</a> on IBCM.</p>
<p>The primary mechanism for learning IBCM is through the <a
href="../slides/07-ibcm.html">IBCM slide set</a> and the <a
href="../book/ibcm-chapter.pdf">IBCM book chapter</a>. The material in
both of those largely duplicates itself, but in different formats. IBCM
is utilized through an online set of web pages, described next. A few
C++ utilities are described at the bottom of this page.</p>
<h2 id="website">Website</h2>
<p>The IBCM is utilized through an online series of webpages. The IBCM
simulator needs PHP in order to run, and thus must be run from a web
server (i.e., not as a local file). Most of the computational load is on
the client side (via Javascript), and little is on the server side.
There are a few mirros of this website available, which are listed
below. All the necessary code to run a separate copy are included in
this repository.</p>
<p>The primary file for the website is <a
href="index.html">index.html</a>, and the directions are on the <a
href="directions.html">directions.html</a> page. The simulator itself is
on the <a href="simulator.php">simulator.php</a> page – but as described
above, this must be run on an actual web server. Two supporting files
(<a href="simulator.js">simulator.js</a> and <a
href="ibcm.css">ibcm.css</a>) and the entire img/ directory are needed
as well. Note that two of the programs listed below (<a
href="summation.ibcm">summation.ibcm</a> and <a
href="array-summation.ibcm">array-summation.ibcm</a>) are linked to from
the various website pages.</p>
<p>The simulator can be accessed via <a
href="http://pegasus.cs.virginia.edu/ibcm/">http://pegasus.cs.virginia.edu/ibcm/</a>.</p>
<h2 id="sample-ibcm-code">Sample IBCM code</h2>
<p>The sample IBCM code included in this repository:</p>
<ul>
<li><a href="summation.ibcm">summation.ibcm</a>: a program that reads in
a single integer value <em>n</em>, and computes the sum from 1 to
<em>n</em>. This is the first program that is discussed in the <a
href="../slides/07-ibcm.html">IBCM slide set</a>.</li>
<li><a href="array-summation.ibcm">array-summation.ibcm</a>: a program
that will compute the sum of a number of elements in an array. Due to
the fact that IBCM is intentionally a simplistic language, array
indexing instrcutions must be created during run-time. This is the
second program that is discussed in the <a
href="../slides/07-ibcm.html">IBCM slide set</a>.</li>
<li><a href="multiply.ibcm">multiply.ibcm</a>: a program that creates an
activation to allow for recursive calls. It can call itself recursively
about 1,300 times before it runs out of memory. The ‘stack’, which
contains the activation records, starts at the end of memory, and
contains only the two parameters to the subroutine and the reutrn
address.</li>
<li><a href="turing.ibcm">turing.ibcm</a>: a Turing machine simulator.
The automaton simulated is a four state <a
href="http://en.wikipedia.org/wiki/Busy_beaver">Busy Beaver</a>
automaton, shown below. Details about the Turing completeness can be
found in the <a href="http://dl.acm.org/citation.cfm?id=1953273">IBCM
article</a>.</li>
</ul>
<figure>
<img src="busy-beaver.png" alt="Busy Beaver automaton" />
<figcaption aria-hidden="true">Busy Beaver automaton</figcaption>
</figure>
<h2 id="c-utilities">C++ Utilities</h2>
<p>There are two C++ utility programs included, which are primarly
useful for grading. In particular, they allow the programs to be run
through a series of scripts (or other automated grading system).</p>
<p><a href="ibcm-parse.cpp.html">ibcm-parse.cpp</a> (<a
href="ibcm-parse.cpp">src</a>) is a program that will quickly check if
the file names passed in via command line arguments look like IBCM
files. In particular, it checks if the first four digits on each line
are all hexadecimal digits. It does not program validity checking beyond
this. It is useful to tell the students if, on submission, their
programs will parse correctly in an IBCM simulator.</p>
<p><a href="ibcm-simulator.cpp.html">ibcm-simulator.cpp</a> (<a
href="ibcm-simulator.cpp">src</a>) will simulate an IBCM program, and it
has a number of command line switches that control its execution. This
program is useful for automating the execution of a number of IBCM
programs without having to load each one into the web interface. It will
also print out traces of the entire program execution, if desired. Run
with the <code>-help</code> flag to see the full list of options.</p>
</body>
</html>