Blame - docs/Stacker.html - platform/external/llvm

blob: eabccdf6cf10b9aeb3557876bd6aa741502c4d1b [file] [log] [blame]

Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
				2	<html>
				3	<head>
				4	<title>Stacker: An Example Of Using LLVM</title>
				5	<link rel="stylesheet" href="llvm.css" type="text/css">
				6	</head>
				7	<body>
				8	<div class="doc_title">Stacker: An Example Of Using LLVM</div>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	9	<hr>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	10	<ol>
				11	<li><a href="#abstract">Abstract</a></li>
				12	<li><a href="#introduction">Introduction</a></li>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	13	<li><a href="#lessons">Lessons I Learned About LLVM</a>
				14	<ol>
				15	<li><a href="#value">Everything's a Value!</a></li>
				16	<li><a href="#terminate">Terminate Those Blocks!</a></li>
				17	<li><a href="#blocks">Concrete Blocks</a></li>
				18	<li><a href="#push_back">push_back Is Your Friend</a></li>
				19	<li><a href="#gep">The Wily GetElementPtrInst</a></li>
				20	<li><a href="#linkage">Getting Linkage Types Right</a></li>
				21	<li><a href="#constants">Constants Are Easier Than That!</a></li>
				22	</ol>
				23	</li>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	24	<li><a href="#lexicon">The Stacker Lexicon</a>
				25	<ol>
				26	<li><a href="#stack">The Stack</a>
				27	<li><a href="#punctuation">Punctuation</a>
				28	<li><a href="#literals">Literals</a>
				29	<li><a href="#words">Words</a>
				30	<li><a href="#builtins">Built-Ins</a>
				31	</ol>
				32	</li>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	33	<li><a href="#example">Prime: A Complete Example</a></li>
				34	<li><a href="#internal">Internal Code Details</a>
				35	<ol>
				36	<li><a href="#directory">The Directory Structure </a></li>
				37	<li><a href="#lexer">The Lexer</a></li>
				38	<li><a href="#parser">The Parser</a></li>
				39	<li><a href="#compiler">The Compiler</a></li>
				40	<li><a href="#runtime">The Runtime</a></li>
				41	<li><a href="#driver">Compiler Driver</a></li>
				42	<li><a href="#tests">Test Programs</a></li>
				43	</ol>
				44	</li>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	45	</ol>
				46	<div class="doc_text">
				47	<p><b>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> </b></p>
				48	<p> </p>
				49	</div>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	50	<hr>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	51	<!-- ======================================================================= -->
				52	<div class="doc_section"> <a name="abstract">Abstract </a></div>
				53	<div class="doc_text">
				54	<p>This document is another way to learn about LLVM. Unlike the
				55	<a href="LangRef.html">LLVM Reference Manual</a> or
				56	<a href="ProgrammersManual.html">LLVM Programmer's Manual</a>, this
				57	document walks you through the implementation of a programming language
				58	named Stacker. Stacker was invented specifically as a demonstration of
				59	LLVM. The emphasis in this document is not on describing the
				60	intricacies of LLVM itself, but on how to use it to build your own
				61	compiler system.</p>
				62	</div>
				63	<!-- ======================================================================= -->
				64	<div class="doc_section"> <a name="introduction">Introduction</a> </div>
				65	<div class="doc_text">
				66	<p>Amongst other things, LLVM is a platform for compiler writers.
				67	Because of its exceptionally clean and small IR (intermediate
				68	representation), compiler writing with LLVM is much easier than with
				69	other system. As proof, the author of Stacker wrote the entire
				70	compiler (language definition, lexer, parser, code generator, etc.) in
				71	about <em>four days</em>! That's important to know because it shows
				72	how quickly you can get a new
				73	language up when using LLVM. Furthermore, this was the <em >first</em>
				74	language the author ever created using LLVM. The learning curve is
				75	included in that four days.</p>
				76	<p>The language described here, Stacker, is Forth-like. Programs
				77	are simple collections of word definitions and the only thing definitions
				78	can do is manipulate a stack or generate I/O. Stacker is not a "real"
				79	programming language; its very simple. Although it is computationally
				80	complete, you wouldn't use it for your next big project. However,
				81	the fact that it is complete, its simple, and it <em>doesn't</em> have
				82	a C-like syntax make it useful for demonstration purposes. It shows
				83	that LLVM could be applied to a wide variety of language syntaxes.</p>
				84	<p>The basic notions behind stacker is very simple. There's a stack of
				85	integers (or character pointers) that the program manipulates. Pretty
				86	much the only thing the program can do is manipulate the stack and do
				87	some limited I/O operations. The language provides you with several
				88	built-in words that manipulate the stack in interesting ways. To get
				89	your feet wet, here's how you write the traditional "Hello, World"
				90	program in Stacker:</p>
				91	<p><code>: hello_world "Hello, World!" >s DROP CR ;<br>
				92	: MAIN hello_world ;<br></code></p>
				93	<p>This has two "definitions" (Stacker manipulates words, not
				94	functions and words have definitions): <code>MAIN</code> and <code>
				95	hello_world</code>. The <code>MAIN</code> definition is standard, it
				96	tells Stacker where to start. Here, <code>MAIN</code> is defined to
				97	simply invoke the word <code>hello_world</code>. The
				98	<code>hello_world</code> definition tells stacker to push the
				99	<code>"Hello, World!"</code> string onto the stack, print it out
				100	(<code>>s</code>), pop it off the stack (<code>DROP</code>), and
				101	finally print a carriage return (<code>CR</code>). Although
				102	<code>hello_world</code> uses the stack, its net effect is null. Well
				103	written Stacker definitions have that characteristic. </p>
				104	<p>Exercise for the reader: how could you make this a one line program?</p>
				105	</div>
				106	<!-- ======================================================================= -->
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	107	<div class="doc_section"><a name="lessons"></a>Lessons I Learned About LLVM</div>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	108	<div class="doc_text">
				109	<p>Stacker was written for two purposes: (a) to get the author over the
				110	learning curve and (b) to provide a simple example of how to write a compiler
				111	using LLVM. During the development of Stacker, many lessons about LLVM were
				112	learned. Those lessons are described in the following subsections.<p>
				113	</div>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	114	<!-- ======================================================================= -->
				115	<div class="doc_subsection"><a name="value"></a>Everything's a Value!</div>
				116	<div class="doc_text">
				117	<p>Although I knew that LLVM used a Single Static Assignment (SSA) format,
				118	it wasn't obvious to me how prevalent this idea was in LLVM until I really
				119	started using it. Reading the Programmer's Manual and Language Reference I
				120	noted that most of the important LLVM IR (Intermediate Representation) C++
				121	classes were derived from the Value class. The full power of that simple
				122	design only became fully understood once I started constructing executable
				123	expressions for Stacker.</p>
				124	<p>This really makes your programming go faster. Think about compiling code
				125	for the following C/C++ expression: (a\|b)*((x+1)/(y+1)). You could write a
				126	function using LLVM that does exactly that, this way:</p>
				127	<pre><code>
				128	Value*
				129	expression(BasicBlockbb, Value a, Value* b, Value* x, Value* y )
				130	{
				131	Instruction* tail = bb->getTerminator();
				132	ConstantSInt* one = ConstantSInt::get( Type::IntTy, 1);
				133	BinaryOperator* or1 =
				134	new BinaryOperator::create( Instruction::Or, a, b, "", tail );
				135	BinaryOperator* add1 =
				136	new BinaryOperator::create( Instruction::Add, x, one, "", tail );
				137	BinaryOperator* add2 =
				138	new BinaryOperator::create( Instruction::Add, y, one, "", tail );
				139	BinaryOperator* div1 =
				140	new BinaryOperator::create( Instruction::Div, add1, add2, "", tail);
				141	BinaryOperator* mult1 =
				142	new BinaryOperator::create( Instruction::Mul, or1, div1, "", tail );
				143
				144	return mult1;
				145	}
				146	</code></pre>
				147	<p>"Okay, big deal," you say. It is a big deal. Here's why. Note that I didn't
				148	have to tell this function which kinds of Values are being passed in. They could be
				149	instructions, Constants, Global Variables, etc. Furthermore, if you specify Values
				150	that are incorrect for this sequence of operations, LLVM will either notice right
				151	away (at compilation time) or the LLVM Verifier will pick up the inconsistency
				152	when the compiler runs. In no case will you make a type error that gets passed
				153	through to the generated program. This <em>really</em> helps you write a compiler
				154	that always generates correct code!<p>
				155	<p>The second point is that we don't have to worry about branching, registers,
				156	stack variables, saving partial results, etc. The instructions we create
				157	<em>are</em> the values we use. Note that all that was created in the above
				158	code is a Constant value and five operators. Each of the instructions <em>is</em>
				159	the resulting value of that instruction.</p>
				160	<p>The lesson is this: <em>SSA form is very powerful: there is no difference
				161	between a value and the instruction that created it.</em> This is fully
				162	enforced by the LLVM IR. Use it to your best advantage.</p>
				163	</div>
				164	<!-- ======================================================================= -->
				165	<div class="doc_subsection"><a name="terminate"></a>Terminate Those Blocks!</div>
				166	<div class="doc_text">
				167	<p>I had to learn about terminating blocks the hard way: using the debugger
				168	to figure out what the LLVM verifier was trying to tell me and begging for
				169	help on the LLVMdev mailing list. I hope you avoid this experience.</p>
				170	<p>Emblazon this rule in your mind:</p>
				171	<ul>
				172	<li><em>All</em> <code>BasicBlock</code>s in your compiler <b>must</b> be
				173	terminated with a terminating instruction (branch, return, etc.).
				174	</li>
				175	</ul>
				176	<p>Terminating instructions are a semantic requirement of the LLVM IR. There
				177	is no facility for implicitly chaining together blocks placed into a function
				178	in the order they occur. Indeed, in the general case, blocks will not be
				179	added to the function in the order of execution because of the recursive
				180	way compilers are written.</p>
				181	<p>Furthermore, if you don't terminate your blocks, your compiler code will
				182	compile just fine. You won't find out about the problem until you're running
				183	the compiler and the module you just created fails on the LLVM Verifier.</p>
				184	</div>
				185	<!-- ======================================================================= -->
				186	<div class="doc_subsection"><a name="blocks"></a>Concrete Blocks</div>
				187	<div class="doc_text">
				188	<p>After a little initial fumbling around, I quickly caught on to how blocks
				189	should be constructed. The use of the standard template library really helps
				190	simply the interface. In general, here's what I learned:
				191	<ol>
				192	<li><em>Create your blocks early.</em> While writing your compiler, you
				193	will encounter several situations where you know apriori that you will
				194	need several blocks. For example, if-then-else, switch, while and for
				195	statements in C/C++ all need multiple blocks for expression in LVVM.
				196	The rule is, create them early.</li>
				197	<li><em>Terminate your blocks early.</em> This just reduces the chances
				198	that you forget to terminate your blocks which is required (go
				199	<a href="#terminate">here</a> for more).
				200	<li><em>Use getTerminator() for instruction insertion.</em> I noticed early on
				201	that many of the constructors for the Instruction classes take an optional
				202	<code>insert_before</code> argument. At first, I thought this was a mistake
				203	because clearly the normal mode of inserting instructions would be one at
				204	a time <em>after</em> some other instruction, not <em>before</em>. However,
				205	if you hold on to your terminating instruction (or use the handy dandy
				206	<code>getTerminator()</code> method on a <code>BasicBlock</code>), it can
				207	always be used as the <code>insert_before</code> argument to your instruction
				208	constructors. This causes the instruction to automatically be inserted in
				209	the RightPlace&tm; place, just before the terminating instruction. The
				210	nice thing about this design is that you can pass blocks around and insert
				211	new instructions into them without ever known what instructions came
				212	before. This makes for some very clean compiler design.</li>
				213	</ol>
				214	<p>The foregoing is such an important principal, its worth making an idiom:</p>
				215	<pre>
				216	<code>
				217	BasicBlock* bb = new BasicBlock();</li>
				218	bb->getInstList().push_back( new Branch( ... ) );
				219	new Instruction(..., bb->getTerminator() );
				220	</code>
				221	</pre>
				222	<p>To make this clear, consider the typical if-then-else statement
				223	(see StackerCompiler::handle_if() method). We can set this up
				224	in a single function using LLVM in the following way: </p>
				225	<pre>
				226	using namespace llvm;
				227	BasicBlock*
				228	MyCompiler::handle_if( BasicBlock* bb, SetCondInst* condition )
				229	{
				230	// Create the blocks to contain code in the structure of if/then/else
				231	BasicBlock* then = new BasicBlock();
				232	BasicBlock* else = new BasicBlock();
				233	BasicBlock* exit = new BasicBlock();
				234
				235	// Insert the branch instruction for the "if"
				236	bb->getInstList().push_back( new BranchInst( then, else, condition ) );
				237
				238	// Set up the terminating instructions
				239	then->getInstList().push_back( new BranchInst( exit ) );
				240	else->getInstList().push_back( new BranchInst( exit ) );
				241
				242	// Fill in the then part .. details excised for brevity
				243	this->fill_in( then );
				244
				245	// Fill in the else part .. details excised for brevity
				246	this->fill_in( else );
				247
				248	// Return a block to the caller that can be filled in with the code
				249	// that follows the if/then/else construct.
				250	return exit;
				251	}
				252	</pre>
				253	<p>Presumably in the foregoing, the calls to the "fill_in" method would add
				254	the instructions for the "then" and "else" parts. They would use the third part
				255	of the idiom almost exclusively (inserting new instructions before the
				256	terminator). Furthermore, they could even recurse back to <code>handle_if</code>
				257	should they encounter another if/then/else statement and it will all "just work".
				258	<p>
				259	<p>Note how cleanly this all works out. In particular, the push_back methods on
				260	the <code>BasicBlock</code>'s instruction list. These are lists of type
				261	<code>Instruction</code> which also happen to be <code>Value</code>s. To create
				262	the "if" branch we merely instantiate a <code>BranchInst</code> that takes as
				263	arguments the blocks to branch to and the condition to branch on. The blocks
				264	act like branch labels! This new <code>BranchInst</code> terminates
				265	the <code>BasicBlock</code> provided as an argument. To give the caller a way
				266	to keep inserting after calling <code>handle_if</code> we create an "exit" block
				267	which is returned to the caller. Note that the "exit" block is used as the
				268	terminator for both the "then" and the "else" blocks. This gaurantees that no
				269	matter what else "handle_if" or "fill_in" does, they end up at the "exit" block.
				270	</p>
				271	</div>
				272	<!-- ======================================================================= -->
				273	<div class="doc_subsection"><a name="push_back"></a>push_back Is Your Friend</div>
				274	<div class="doc_text">
				275	<p>
				276	One of the first things I noticed is the frequent use of the "push_back"
				277	method on the various lists. This is so common that it is worth mentioning.
				278	The "push_back" inserts a value into an STL list, vector, array, etc. at the
				279	end. The method might have also been named "insert_tail" or "append".
				280	Althought I've used STL quite frequently, my use of push_back wasn't very
				281	high in other programs. In LLVM, you'll use it all the time.
				282	</p>
				283	</div>
				284	<!-- ======================================================================= -->
				285	<div class="doc_subsection"><a name="gep"></a>The Wily GetElementPtrInst</div>
				286	<div class="doc_text">
				287	<p>
				288	It took a little getting used to and several rounds of postings to the LLVM
				289	mail list to wrap my head around this instruction correctly. Even though I had
				290	read the Language Reference and Programmer's Manual a couple times each, I still
				291	missed a few <em>very</em> key points:
				292	</p>
				293	<ul>
				294	<li>GetElementPtrInst gives you back a Value for the last thing indexed</em>
				295	<li>All global variables in LLVM are <em>pointers</em>.
				296	<li>Pointers must also be dereferenced with the GetElementPtrInst instruction.
				297	</ul>
				298	<p>This means that when you look up an element in the global variable (assuming
				299	its a struct or array), you <em>must</em> deference the pointer first! For many
				300	things, this leads to the idiom:
				301	</p>
				302	<pre><code>
				303	std::vector<Value*> index_vector;
				304	index_vector.push_back( ConstantSInt::get( Type::LongTy, 0 );
				305	// ... push other indices ...
				306	GetElementPtrInst* gep = new GetElementPtrInst( ptr, index_vector );
				307	</code></pre>
				308	<p>For example, suppose we have a global variable whose type is [24 x int]. The
				309	variable itself represents a <em>pointer</em> to that array. To subscript the
				310	array, we need two indices, not just one. The first index (0) dereferences the
				311	pointer. The second index subscripts the array. If you're a "C" programmer, this
				312	will run against your grain because you'll naturally think of the global array
				313	variable and the address of its first element as the same. That tripped me up
				314	for a while until I realized that they really do differ .. by <em>type</em>.
				315	Remember that LLVM is a strongly typed language itself. Absolutely everything
				316	has a type. The "type" of the global variable is [24 x int]*. That is, its
				317	a pointer to an array of 24 ints. When you dereference that global variable with
				318	a single index, you now have a " [24 x int]" type, the pointer is gone. Although
				319	the pointer value of the dereferenced global and the address of the zero'th element
				320	in the array will be the same, they differ in their type. The zero'th element has
				321	type "int" while the pointer value has type "[24 x int]".</p>
				322	<p>Get this one aspect of LLVM right in your head and you'll save yourself
				323	a lot of compiler writing headaches down the road.</p>
				324	</div>
				325	<!-- ======================================================================= -->
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	326	<div class="doc_subsection"><a name="linkage"></a>Getting Linkage Types Right</div>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	327	<div class="doc_text">
				328	<p>Linkage types in LLVM can be a little confusing, especially if your compiler
				329	writing mind has affixed very hard concepts to particular words like "weak",
				330	"external", "global", "linkonce", etc. LLVM does <em>not</em> use the precise
				331	definitions of say ELF or GCC even though they share common terms. To be fair,
				332	the concepts are related and similar but not precisely the same. This can lead
				333	you to think you know what a linkage type represents but in fact it is slightly
				334	different. I recommend you read the
				335	<a href="LangRef.html#linkage"> Language Reference on this topic</a> very
				336	carefully.<p>
				337	<p>Here are some handy tips that I discovered along the way:</p>
				338	<ul>
				339	<li>Unitialized means external. That is, the symbol is declared in the current
				340	module and can be used by that module but it is not defined by that module.</li>
				341	<li>Setting an initializer changes a global's linkage type from whatever it was
				342	to a normal, defind global (not external). You'll need to call the setLinkage()
				343	method to reset it if you specify the initializer after the GlobalValue has been
				344	constructed. This is important for LinkOnce and Weak linkage types.</li>
				345	<li>Appending linkage can be used to keep track of compilation information at
				346	runtime. It could be used, for example, to build a full table of all the C++
				347	virtual tables or hold the C++ RTTI data, or whatever. Appending linkage can
				348	only be applied to arrays. The arrays are concatenated together at link time.</li>
				349	</ul>
				350	</div>
				351	<!-- ======================================================================= -->
				352	<div class="doc_subsection"><a name="constants"></a>Constants Are Easier Than That!</div>
				353	<div class="doc_text">
				354	<p>
				355	Constants in LLVM took a little getting used to until I discovered a few utility
				356	functions in the LLVM IR that make things easier. Here's what I learned: </p>
				357	<ul>
				358	<li>Constants are Values like anything else and can be operands of instructions</li>
				359	<li>Integer constants, frequently needed can be created using the static "get"
				360	methods of the ConstantInt, ConstantSInt, and ConstantUInt classes. The nice thing
				361	about these is that you can "get" any kind of integer quickly.</li>
				362	<li>There's a special method on Constant class which allows you to get the null
				363	constant for <em>any</em> type. This is really handy for initializing large
				364	arrays or structures, etc.</li>
				365	</ul>
				366	</div>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	367	<!-- ======================================================================= -->
				368	<div class="doc_section"> <a name="lexicon">The Stacker Lexicon</a></div>
				369	<div class="doc_subsection"><a name="stack"></a>The Stack</div>
				370	<div class="doc_text">
				371	<p>Stacker definitions define what they do to the global stack. Before
				372	proceeding, a few words about the stack are in order. The stack is simply
				373	a global array of 32-bit integers or pointers. A global index keeps track
				374	of the location of the to of the stack. All of this is hidden from the
				375	programmer but it needs to be noted because it is the foundation of the
				376	conceptual programming model for Stacker. When you write a definition,
				377	you are, essentially, saying how you want that definition to manipulate
				378	the global stack.</p>
				379	<p>Manipulating the stack can be quite hazardous. There is no distinction
				380	given and no checking for the various types of values that can be placed
				381	on the stack. Automatic coercion between types is performed. In many
				382	cases this is useful. For example, a boolean value placed on the stack
				383	can be interpreted as an integer with good results. However, using a
				384	word that interprets that boolean value as a pointer to a string to
				385	print out will almost always yield a crash. Stacker simply leaves it
				386	to the programmer to get it right without any interference or hindering
				387	on interpretation of the stack values. You've been warned :) </p>
				388	</div>
				389	<!-- ======================================================================= -->
				390	<div class="doc_subsection"> <a name="punctuation"></a>Punctuation</div>
				391	<div class="doc_text">
				392	<p>Punctuation in Stacker is very simple. The colon and semi-colon
				393	characters are used to introduce and terminate a definition
				394	(respectively). Except for <em>FORWARD</em> declarations, definitions
				395	are all you can specify in Stacker. Definitions are read left to right.
				396	Immediately after the semi-colon comes the name of the word being defined.
				397	The remaining words in the definition specify what the word does.</p>
				398	</div>
				399	<!-- ======================================================================= -->
				400	<div class="doc_subsection"><a name="literals"></a>Literals</div>
				401	<div class="doc_text">
				402	<p>There are three kinds of literal values in Stacker. Integer, Strings,
				403	and Booleans. In each case, the stack operation is to simply push the
				404	value onto the stack. So, for example:<br/>
				405	<code> 42 " is the answer." TRUE </code><br/>
				406	will push three values onto the stack: the integer 42, the
				407	string " is the answer." and the boolean TRUE.</p>
				408	</div>
				409	<!-- ======================================================================= -->
				410	<div class="doc_subsection"><a name="words"></a>Words</div>
				411	<div class="doc_text">
				412	<p>Each definition in Stacker is composed of a set of words. Words are
				413	read and executed in order from left to right. There is very little
				414	checking in Stacker to make sure you're doing the right thing with
				415	the stack. It is assumed that the programmer knows how the stack
				416	transformation he applies will affect the program.</p>
				417	<p>Words in a definition come in two flavors: built-in and programmer
				418	defined. Simply mentioning the name of a previously defined or declared
				419	programmer-defined word causes that words definition to be invoked. It
				420	is somewhat like a function call in other languages. The built-in
				421	words have various effects, described below.</p>
				422	<p>Sometimes you need to call a word before it is defined. For this, you can
				423	use the <code>FORWARD</code> declaration. It looks like this</p>
				424	<p><code>FORWARD name ;</code></p>
				425	<p>This simply states to Stacker that "name" is the name of a definition
				426	that is defined elsewhere. Generally it means the definition can be found
				427	"forward" in the file. But, it doesn't have to be in the current compilation
				428	unit. Anything declared with <code>FORWARD</code> is an external symbol for
				429	linking.</p>
				430	</div>
				431	<!-- ======================================================================= -->
				432	<div class="doc_subsection"><a name="builtins"></a>Built In Words</div>
				433	<div class="doc_text">
				434	<p>The built-in words of the Stacker language are put in several groups
				435	depending on what they do. The groups are as follows:</p>
				436	<ol>
				437	<li><em>Logical</em>These words provide the logical operations for
				438	comparing stack operands.<br/>The words are: < > <= >=
				439	= <> true false.</li>
				440	<li><em>Bitwise</em>These words perform bitwise computations on
				441	their operands. <br/> The words are: << >> XOR AND NOT</li>
				442	<li><em>Arithmetic</em>These words perform arithmetic computations on
				443	their operands. <br/> The words are: ABS NEG + - * / MOD */ ++ -- MIN MAX</li>
				444	<li><em>Stack</em>These words manipulate the stack directly by moving
				445	its elements around.<br/> The words are: DROP DUP SWAP OVER ROT DUP2 DROP2 PICK TUCK</li>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	446	<li><em>Memory</em>These words allocate, free and manipulate memory
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	447	areas outside the stack.<br/>The words are: MALLOC FREE GET PUT</li>
				448	<li><em>Control</em>These words alter the normal left to right flow
				449	of execution.<br/>The words are: IF ELSE ENDIF WHILE END RETURN EXIT RECURSE</li>
				450	<li><em>I/O</em> These words perform output on the standard output
				451	and input on the standard input. No other I/O is possible in Stacker.
				452	<br/>The words are: SPACE TAB CR >s >d >c <s <d <c.</li>
				453	</ol>
				454	<p>While you may be familiar with many of these operations from other
				455	programming languages, a careful review of their semantics is important
				456	for correct programming in Stacker. Of most importance is the effect
				457	that each of these built-in words has on the global stack. The effect is
				458	not always intuitive. To better describe the effects, we'll borrow from Forth the idiom of
				459	describing the effect on the stack with:</p>
				460	<p><code> BEFORE -- AFTER </code></p>
				461	<p>That is, to the left of the -- is a representation of the stack before
				462	the operation. To the right of the -- is a representation of the stack
				463	after the operation. In the table below that describes the operation of
				464	each of the built in words, we will denote the elements of the stack
				465	using the following construction:</p>
				466	<ol>
				467	<li><em>b</em> - a boolean truth value</li>
				468	<li><em>w</em> - a normal integer valued word.</li>
				469	<li><em>s</em> - a pointer to a string value</li>
				470	<li><em>p</em> - a pointer to a malloc's memory block</li>
				471	</ol>
				472	</div>
				473	<div class="doc_text">
				474	<table class="doc_table" >
				475	<tr class="doc_table"><td colspan="4">Definition Of Operation Of Built In Words</td></tr>
				476	<tr class="doc_table"><td colspan="4">LOGICAL OPERATIONS</td></tr>
				477	<tr class="doc_table"><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				478	<tr class="doc_table"><td><</td>
				479	<td>LT</td>
				480	<td>w1 w2 -- b</td>
				481	<td>Two values (w1 and w2) are popped off the stack and
				482	compared. If w1 is less than w2, TRUE is pushed back on
				483	the stack, otherwise FALSE is pushed back on the stack.</td>
				484	</tr>
				485	<tr><td>></td>
				486	<td>GT</td>
				487	<td>w1 w2 -- b</td>
				488	<td>Two values (w1 and w2) are popped off the stack and
				489	compared. If w1 is greater than w2, TRUE is pushed back on
				490	the stack, otherwise FALSE is pushed back on the stack.</td>
				491	</tr>
				492	<tr><td>>=</td>
				493	<td>GE</td>
				494	<td>w1 w2 -- b</td>
				495	<td>Two values (w1 and w2) are popped off the stack and
				496	compared. If w1 is greater than or equal to w2, TRUE is
				497	pushed back on the stack, otherwise FALSE is pushed back
				498	on the stack.</td>
				499	</tr>
				500	<tr><td><=</td>
				501	<td>LE</td>
				502	<td>w1 w2 -- b</td>
				503	<td>Two values (w1 and w2) are popped off the stack and
				504	compared. If w1 is less than or equal to w2, TRUE is
				505	pushed back on the stack, otherwise FALSE is pushed back
				506	on the stack.</td>
				507	</tr>
				508	<tr><td>=</td>
				509	<td>EQ</td>
				510	<td>w1 w2 -- b</td>
				511	<td>Two values (w1 and w2) are popped off the stack and
				512	compared. If w1 is equal to w2, TRUE is
				513	pushed back on the stack, otherwise FALSE is pushed back
				514	</td>
				515	</tr>
				516	<tr><td><></td>
				517	<td>NE</td>
				518	<td>w1 w2 -- b</td>
				519	<td>Two values (w1 and w2) are popped off the stack and
				520	compared. If w1 is equal to w2, TRUE is
				521	pushed back on the stack, otherwise FALSE is pushed back
				522	</td>
				523	</tr>
				524	<tr><td>FALSE</td>
				525	<td>FALSE</td>
				526	<td> -- b</td>
				527	<td>The boolean value FALSE (0) is pushed onto the stack.</td>
				528	</tr>
				529	<tr><td>TRUE</td>
				530	<td>TRUE</td>
				531	<td> -- b</td>
				532	<td>The boolean value TRUE (-1) is pushed onto the stack.</td>
				533	</tr>
				534	<tr><td colspan="4">BITWISE OPERATIONS</td></tr>
				535	<tr><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				536	<tr><td><<</td>
				537	<td>SHL</td>
				538	<td>w1 w2 -- w1<<w2</td>
				539	<td>Two values (w1 and w2) are popped off the stack. The w2
				540	operand is shifted left by the number of bits given by the
				541	w1 operand. The result is pushed back to the stack.</td>
				542	</tr>
				543	<tr><td>>></td>
				544	<td>SHR</td>
				545	<td>w1 w2 -- w1>>w2</td>
				546	<td>Two values (w1 and w2) are popped off the stack. The w2
				547	operand is shifted right by the number of bits given by the
				548	w1 operand. The result is pushed back to the stack.</td>
				549	</tr>
				550	<tr><td>OR</td>
				551	<td>OR</td>
				552	<td>w1 w2 -- w2\|w1</td>
				553	<td>Two values (w1 and w2) are popped off the stack. The values
				554	are bitwise OR'd together and pushed back on the stack. This is
				555	not a logical OR. The sequence 1 2 OR yields 3 not 1.</td>
				556	</tr>
				557	<tr><td>AND</td>
				558	<td>AND</td>
				559	<td>w1 w2 -- w2&w1</td>
				560	<td>Two values (w1 and w2) are popped off the stack. The values
				561	are bitwise AND'd together and pushed back on the stack. This is
				562	not a logical AND. The sequence 1 2 AND yields 0 not 1.</td>
				563	</tr>
				564	<tr><td>XOR</td>
				565	<td>XOR</td>
				566	<td>w1 w2 -- w2^w1</td>
				567	<td>Two values (w1 and w2) are popped off the stack. The values
				568	are bitwise exclusive OR'd together and pushed back on the stack.
				569	For example, The sequence 1 3 XOR yields 2.</td>
				570	</tr>
				571	<tr><td colspan="4">ARITHMETIC OPERATIONS</td></tr>
				572	<tr><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				573	<tr><td>ABS</td>
				574	<td>ABS</td>
				575	<td>w -- \|w\|</td>
				576	<td>One value s popped off the stack; its absolute value is computed
				577	and then pushed onto the stack. If w1 is -1 then w2 is 1. If w1 is
				578	1 then w2 is also 1.</td>
				579	</tr>
				580	<tr><td>NEG</td>
				581	<td>NEG</td>
				582	<td>w -- -w</td>
				583	<td>One value is popped off the stack which is negated and then
				584	pushed back onto the stack. If w1 is -1 then w2 is 1. If w1 is
				585	1 then w2 is -1.</td>
				586	</tr>
				587	<tr><td> + </td>
				588	<td>ADD</td>
				589	<td>w1 w2 -- w2+w1</td>
				590	<td>Two values are popped off the stack. Their sum is pushed back
				591	onto the stack</td>
				592	</tr>
				593	<tr><td> - </td>
				594	<td>SUB</td>
				595	<td>w1 w2 -- w2-w1</td>
				596	<td>Two values are popped off the stack. Their difference is pushed back
				597	onto the stack</td>
				598	</tr>
				599	<tr><td> * </td>
				600	<td>MUL</td>
				601	<td>w1 w2 -- w2*w1</td>
				602	<td>Two values are popped off the stack. Their product is pushed back
				603	onto the stack</td>
				604	</tr>
				605	<tr><td> / </td>
				606	<td>DIV</td>
				607	<td>w1 w2 -- w2/w1</td>
				608	<td>Two values are popped off the stack. Their quotient is pushed back
				609	onto the stack</td>
				610	</tr>
				611	<tr><td>MOD</td>
				612	<td>MOD</td>
				613	<td>w1 w2 -- w2%w1</td>
				614	<td>Two values are popped off the stack. Their remainder after division
				615	of w1 by w2 is pushed back onto the stack</td>
				616	</tr>
				617	<tr><td> */ </td>
				618	<td>STAR_SLAH</td>
				619	<td>w1 w2 w3 -- (w3*w2)/w1</td>
				620	<td>Three values are popped off the stack. The product of w1 and w2 is
				621	divided by w3. The result is pushed back onto the stack.</td>
				622	</tr>
				623	<tr><td> ++ </td>
				624	<td>INCR</td>
				625	<td>w -- w+1</td>
				626	<td>One value is popped off the stack. It is incremented by one and then
				627	pushed back onto the stack.</td>
				628	</tr>
				629	<tr><td> -- </td>
				630	<td>DECR</td>
				631	<td>w -- w-1</td>
				632	<td>One value is popped off the stack. It is decremented by one and then
				633	pushed back onto the stack.</td>
				634	</tr>
				635	<tr><td>MIN</td>
				636	<td>MIN</td>
				637	<td>w1 w2 -- (w2<w1?w2:w1)</td>
				638	<td>Two values are popped off the stack. The larger one is pushed back
				639	onto the stack.</td>
				640	</tr>
				641	<tr><td>MAX</td>
				642	<td>MAX</td>
				643	<td>w1 w2 -- (w2>w1?w2:w1)</td>
				644	<td>Two values are popped off the stack. The larger value is pushed back
				645	onto the stack.</td>
				646	</tr>
				647	<tr><td colspan="4">STACK MANIPULATION OPERATIONS</td></tr>
				648	<tr><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				649	<tr><td>DROP</td>
				650	<td>DROP</td>
				651	<td>w -- </td>
				652	<td>One value is popped off the stack.</td>
				653	</tr>
				654	<tr><td>DROP2</td>
				655	<td>DROP2</td>
				656	<td>w1 w2 -- </td>
				657	<td>Two values are popped off the stack.</td>
				658	</tr>
				659	<tr><td>NIP</td>
				660	<td>NIP</td>
				661	<td>w1 w2 -- w2</td>
				662	<td>The second value on the stack is removed from the stack. That is,
				663	a value is popped off the stack and retained. Then a second value is
				664	popped and the retained value is pushed.</td>
				665	</tr>
				666	<tr><td>NIP2</td>
				667	<td>NIP2</td>
				668	<td>w1 w2 w3 w4 -- w3 w4</td>
				669	<td>The third and fourth values on the stack are removed from it. That is,
				670	two values are popped and retained. Then two more values are popped and
				671	the two retained values are pushed back on.</td>
				672	</tr>
				673	<tr><td>DUP</td>
				674	<td>DUP</td>
				675	<td>w1 -- w1 w1</td>
				676	<td>One value is popped off the stack. That value is then pushed onto
				677	the stack twice to duplicate the top stack vaue.</td>
				678	</tr>
				679	<tr><td>DUP2</td>
				680	<td>DUP2</td>
				681	<td>w1 w2 -- w1 w2 w1 w2</td>
				682	<td>The top two values on the stack are duplicated. That is, two vaues
				683	are popped off the stack. They are alternately pushed back on the
				684	stack twice each.</td>
				685	</tr>
				686	<tr><td>SWAP</td>
				687	<td>SWAP</td>
				688	<td>w1 w2 -- w2 w1</td>
				689	<td>The top two stack items are reversed in their order. That is, two
				690	values are popped off the stack and pushed back onto the stack in
				691	the opposite order they were popped.</td>
				692	</tr>
				693	<tr><td>SWAP2</td>
				694	<td>SWAP2</td>
				695	<td>w1 w2 w3 w4 -- w3 w4 w2 w1</td>
				696	<td>The top four stack items are swapped in pairs. That is, two values
				697	are popped and retained. Then, two more values are popped and retained.
				698	The values are pushed back onto the stack in the reverse order but
				699	in pairs.</p>
				700	</tr>
				701	<tr><td>OVER</td>
				702	<td>OVER</td>
				703	<td>w1 w2-- w1 w2 w1</td>
				704	<td>Two values are popped from the stack. They are pushed back
				705	onto the stack in the order w1 w2 w1. This seems to cause the
				706	top stack element to be duplicated "over" the next value.</td>
				707	</tr>
				708	<tr><td>OVER2</td>
				709	<td>OVER2</td>
				710	<td>w1 w2 w3 w4 -- w1 w2 w3 w4 w1 w2</td>
				711	<td>The third and fourth values on the stack are replicated onto the
				712	top of the stack</td>
				713	</tr>
				714	<tr><td>ROT</td>
				715	<td>ROT</td>
				716	<td>w1 w2 w3 -- w2 w3 w1</td>
				717	<td>The top three values are rotated. That is, three value are popped
				718	off the stack. They are pushed back onto the stack in the order
				719	w1 w3 w2.</td>
				720	</tr>
				721	<tr><td>ROT2</td>
				722	<td>ROT2</td>
				723	<td>w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2</td>
				724	<td>Like ROT but the rotation is done using three pairs instead of
				725	three singles.</td>
				726	</tr>
				727	<tr><td>RROT</td>
				728	<td>RROT</td>
				729	<td>w1 w2 w3 -- w2 w3 w1</td>
				730	<td>Reverse rotation. Like ROT, but it rotates the other way around.
				731	Essentially, the third element on the stack is moved to the top
				732	of the stack.</td>
				733	</tr>
				734	<tr><td>RROT2</td>
				735	<td>RROT2</td>
				736	<td>w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2</td>
				737	<td>Double reverse rotation. Like RROT but the rotation is done using
				738	three pairs instead of three singles. The fifth and sixth stack
				739	elements are moved to the first and second positions</td>
				740	</tr>
				741	<tr><td>TUCK</td>
				742	<td>TUCK</td>
				743	<td>w1 w2 -- w2 w1 w2</td>
				744	<td>Similar to OVER except that the second operand is being
				745	replicated. Essentially, the first operand is being "tucked"
				746	in between two instances of the second operand. Logically, two
				747	values are popped off the stack. They are placed back on the
				748	stack in the order w2 w1 w2.</td>
				749	</tr>
				750	<tr><td>TUCK2</td>
				751	<td>TUCK2</td>
				752	<td>w1 w2 w3 w4 -- w3 w4 w1 w2 w3 w4</td>
				753	<td>Like TUCK but a pair of elements is tucked over two pairs.
				754	That is, the top two elements of the stack are duplicated and
				755	inserted into the stack at the fifth and positions.</td>
				756	</tr>
				757	<tr><td>PICK</td>
				758	<td>PICK</td>
				759	<td>x0 ... Xn n -- x0 ... Xn x0</td>
				760	<td>The top of the stack is used as an index into the remainder of
				761	the stack. The element at the nth position replaces the index
				762	(top of stack). This is useful for cycling through a set of
				763	values. Note that indexing is zero based. So, if n=0 then you
				764	get the second item on the stack. If n=1 you get the third, etc.
				765	Note also that the index is replaced by the n'th value. </td>
				766	</tr>
				767	<tr><td>SELECT</td>
				768	<td>SELECT</td>
				769	<td>m n X0..Xm Xm+1 .. Xn -- Xm</td>
				770	<td>This is like PICK but the list is removed and you need to specify
				771	both the index and the size of the list. Careful with this one,
				772	the wrong value for n can blow away a huge amount of the stack.</td>
				773	</tr>
				774	<tr><td>ROLL</td>
				775	<td>ROLL</td>
				776	<td>x0 x1 .. xn n -- x1 .. xn x0</td>
				777	<td><b>Not Implemented</b>. This one has been left as an exercise to
				778	the student. If you can implement this one you understand Stacker
				779	and probably a fair amount about LLVM since this is one of the
				780	more complicated Stacker operations. See the StackerCompiler.cpp
				781	file in the projects/Stacker/lib/compiler directory. The operation
				782	of ROLL is like a generalized ROT. That is ROLL with n=1 is the
				783	same as ROT. The n value (top of stack) is used as an index to
				784	select a value up the stack that is <em>moved</em> to the top of
				785	the stack. See the implementations of PICk and SELECT to get
				786	some hints.<p>
				787	</tr>
				788	<tr><td colspan="4">MEMORY OPERATIONS</td></tr>
				789	<tr><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				790	<tr><td>MALLOC</td>
				791	<td>MALLOC</td>
				792	<td>w1 -- p</td>
				793	<td>One value is popped off the stack. The value is used as the size
				794	of a memory block to allocate. The size is in bytes, not words.
				795	The memory allocation is completed and the address of the memory
				796	block is pushed onto the stack.</td>
				797	</tr>
				798	<tr><td>FREE</td>
				799	<td>FREE</td>
				800	<td>p -- </td>
				801	<td>One pointer value is popped off the stack. The value should be
				802	the address of a memory block created by the MALLOC operation. The
				803	associated memory block is freed. Nothing is pushed back on the
				804	stack. Many bugs can be created by attempting to FREE something
				805	that isn't a pointer to a MALLOC allocated memory block. Make
				806	sure you know what's on the stack. One way to do this is with
				807	the following idiom:<br/>
				808	<code>64 MALLOC DUP DUP (use ptr) DUP (use ptr) ... FREE</code>
				809	<br/>This ensures that an extra copy of the pointer is placed on
				810	the stack (for the FREE at the end) and that every use of the
				811	pointer is preceded by a DUP to retain the copy for FREE.</td>
				812	</tr>
				813	<tr><td>GET</td>
				814	<td>GET</td>
				815	<td>w1 p -- w2 p</td>
				816	<td>An integer index and a pointer to a memory block are popped of
				817	the block. The index is used to index one byte from the memory
				818	block. That byte value is retained, the pointer is pushed again
				819	and the retained value is pushed. Note that the pointer value
				820	s essentially retained in its position so this doesn't count
				821	as a "use ptr" in the FREE idiom.</td>
				822	</tr>
				823	<tr><td>PUT</td>
				824	<td>PUT</td>
				825	<td>w1 w2 p -- p </td>
				826	<td>An integer value is popped of the stack. This is the value to
				827	be put into a memory block. Another integer value is popped of
				828	the stack. This is the indexed byte in the memory block. A
				829	pointer to the memory block is popped off the stack. The
				830	first value (w1) is then converted to a byte and written
				831	to the element of the memory block(p) at the index given
				832	by the second value (w2). The pointer to the memory block is
				833	pushed back on the stack so this doesn't count as a "use ptr"
				834	in the FREE idiom.</td>
				835	</tr>
				836	<tr><td colspan="4">CONTROL FLOW OPERATIONS</td></tr>
				837	<tr><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				838	<tr><td>RETURN</td>
				839	<td>RETURN</td>
				840	<td> -- </td>
				841	<td>The currently executing definition returns immediately to its caller.
				842	Note that there is an implicit <code>RETURN</code> at the end of each
				843	definition, logically located at the semi-colon. The sequence
				844	<code>RETURN ;</code> is valid but redundant.</td>
				845	</tr>
				846	<tr><td>EXIT</td>
				847	<td>EXIT</td>
				848	<td>w1 -- </td>
				849	<td>A return value for the program is popped off the stack. The program is
				850	then immediately terminated. This is normally an abnormal exit from the
				851	program. For a normal exit (when <code>MAIN</code> finishes), the exit
				852	code will always be zero in accordance with UNIX conventions.</td>
				853	</tr>
				854	<tr><td>RECURSE</td>
				855	<td>RECURSE</td>
				856	<td> -- </td>
				857	<td>The currently executed definition is called again. This operation is
				858	needed since the definition of a word doesn't exist until the semi colon
				859	is reacher. Attempting something like:<br/>
				860	<code> : recurser recurser ; </code><br/> will yield and error saying that
				861	"recurser" is not defined yet. To accomplish the same thing, change this
				862	to:<br/>
				863	<code> : recurser RECURSE ; </code></td>
				864	</tr>
				865	<tr><td>IF (words...) ENDIF</td>
				866	<td>IF (words...) ENDIF</td>
				867	<td>b -- </td>
				868	<td>A boolean value is popped of the stack. If it is non-zero then the "words..."
				869	are executed. Otherwise, execution continues immediately following the ENDIF.</td>
				870	</tr>
				871	<tr><td>IF (words...) ELSE (words...) ENDIF</td>
				872	<td>IF (words...) ELSE (words...) ENDIF</td>
				873	<td>b -- </td>
				874	<td>A boolean value is popped of the stack. If it is non-zero then the "words..."
				875	between IF and ELSE are executed. Otherwise the words between ELSE and ENDIF are
				876	executed. In either case, after the (words....) have executed, execution continues
				877	immediately following the ENDIF. </td>
				878	</tr>
				879	<tr><td>WHILE (words...) END</td>
				880	<td>WHILE (words...) END</td>
				881	<td>b -- b </td>
				882	<td>The boolean value on the top of the stack is examined. If it is non-zero then the
				883	"words..." between WHILE and END are executed. Execution then begins again at the WHILE where another
				884	boolean is popped off the stack. To prevent this operation from eating up the entire
				885	stack, you should push onto the stack (just before the END) a boolean value that indicates
				886	whether to terminate. Note that since booleans and integers can be coerced you can
				887	use the following "for loop" idiom:<br/>
				888	<code>(push count) WHILE (words...) -- END</code><br/>
				889	For example:<br/>
				890	<code>10 WHILE DUP >d -- END</code><br/>
				891	This will print the numbers from 10 down to 1. 10 is pushed on the stack. Since that is
				892	non-zero, the while loop is entered. The top of the stack (10) is duplicated and then
				893	printed out with >d. The top of the stack is decremented, yielding 9 and control is
				894	transfered back to the WHILE keyword. The process starts all over again and repeats until
				895	the top of stack is decremented to 0 at which the WHILE test fails and control is
				896	transfered to the word after the END.</td>
				897	</tr>
				898	<tr><td colspan="4">INPUT & OUTPUT OPERATIONS</td></tr>
				899	<tr><td>Word</td><td>Name</td><td>Operation</td><td>Description</td></tr>
				900	<tr><td>SPACE</td>
				901	<td>SPACE</td>
				902	<td> -- </td>
				903	<td>A space character is put out. There is no stack effect.</td>
				904	</tr>
				905	<tr><td>TAB</td>
				906	<td>TAB</td>
				907	<td> -- </td>
				908	<td>A tab character is put out. There is no stack effect.</td>
				909	</tr>
				910	<tr><td>CR</td>
				911	<td>CR</td>
				912	<td> -- </td>
				913	<td>A carriage return character is put out. There is no stack effect.</td>
				914	</tr>
				915	<tr><td>>s</td>
				916	<td>OUT_STR</td>
				917	<td> -- </td>
				918	<td>A string pointer is popped from the stack. It is put out.</td>
				919	</tr>
				920	<tr><td>>d</td>
				921	<td>OUT_STR</td>
				922	<td> -- </td>
				923	<td>A value is popped from the stack. It is put out as a decimal integer.</td>
				924	</tr>
				925	<tr><td>>c</td>
				926	<td>OUT_CHR</td>
				927	<td> -- </td>
				928	<td>A value is popped from the stack. It is put out as an ASCII character.</td>
				929	</tr>
				930	<tr><td><s</td>
				931	<td>IN_STR</td>
				932	<td> -- s </td>
				933	<td>A string is read from the input via the scanf(3) format string " %as". The
				934	resulting string is pushed onto the stack.</td>
				935	</tr>
				936	<tr><td><d</td>
				937	<td>IN_STR</td>
				938	<td> -- w </td>
				939	<td>An integer is read from the input via the scanf(3) format string " %d". The
				940	resulting value is pushed onto the stack</td>
				941	</tr>
				942	<tr><td><c</td>
				943	<td>IN_CHR</td>
				944	<td> -- w </td>
				945	<td>A single character is read from the input via the scanf(3) format string
				946	" %c". The value is converted to an integer and pushed onto the stack.</td>
				947	</tr>
				948	<tr><td>DUMP</td>
				949	<td>DUMP</td>
				950	<td> -- </td>
				951	<td>The stack contents are dumped to standard output. This is useful for
				952	debugging your definitions. Put DUMP at the beginning and end of a definition
				953	to see instantly the net effect of the definition.</td>
				954	</tr>
				955	</table>
				956	</div>
				957	<!-- ======================================================================= -->
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	958	<div class="doc_section"> <a name="example">Prime: A Complete Example</a></div>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	959	<div class="doc_text">
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	960	<p>The following fully documented program highlights many features of both
				961	the Stacker language and what is possible with LLVM. The program has two modes
				962	of operations. If you provide numeric arguments to the program, it checks to see
				963	if those arguments are prime numbers, prints out the results. Without any
				964	aruments, the program prints out any prime numbers it finds between 1 and one
				965	million (there's a log of them!). The source code comments below tell the
				966	remainder of the story.
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	967	</p>
				968	</div>
				969	<div class="doc_text">
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	970	<pre><code>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	971	################################################################################
				972	#
				973	# Brute force prime number generator
				974	#
				975	# This program is written in classic Stacker style, that being the style of a
				976	# stack. Start at the bottom and read your way up !
				977	#
				978	# Reid Spencer - Nov 2003
				979	################################################################################
				980	# Utility definitions
				981	################################################################################
				982	: print >d CR ;
				983	: it_is_a_prime TRUE ;
				984	: it_is_not_a_prime FALSE ;
				985	: continue_loop TRUE ;
				986	: exit_loop FALSE;
				987
				988	################################################################################
				989	# This definition tryies an actual division of a candidate prime number. It
				990	# determines whether the division loop on this candidate should continue or
				991	# not.
				992	# STACK<:
				993	# div - the divisor to try
				994	# p - the prime number we are working on
				995	# STACK>:
				996	# cont - should we continue the loop ?
				997	# div - the next divisor to try
				998	# p - the prime number we are working on
				999	################################################################################
				1000	: try_dividing
				1001	DUP2 ( save div and p )
				1002	SWAP ( swap to put divisor second on stack)
				1003	MOD 0 = ( get remainder after division and test for 0 )
				1004	IF
				1005	exit_loop ( remainder = 0, time to exit )
				1006	ELSE
				1007	continue_loop ( remainder != 0, keep going )
				1008	ENDIF
				1009	;
				1010
				1011	################################################################################
				1012	# This function tries one divisor by calling try_dividing. But, before doing
				1013	# that it checks to see if the value is 1. If it is, it does not bother with
				1014	# the division because prime numbers are allowed to be divided by one. The
				1015	# top stack value (cont) is set to determine if the loop should continue on
				1016	# this prime number or not.
				1017	# STACK<:
				1018	# cont - should we continue the loop (ignored)?
				1019	# div - the divisor to try
				1020	# p - the prime number we are working on
				1021	# STACK>:
				1022	# cont - should we continue the loop ?
				1023	# div - the next divisor to try
				1024	# p - the prime number we are working on
				1025	################################################################################
				1026	: try_one_divisor
				1027	DROP ( drop the loop continuation )
				1028	DUP ( save the divisor )
				1029	1 = IF ( see if divisor is == 1 )
				1030	exit_loop ( no point dividing by 1 )
				1031	ELSE
				1032	try_dividing ( have to keep going )
				1033	ENDIF
				1034	SWAP ( get divisor on top )
				1035	-- ( decrement it )
				1036	SWAP ( put loop continuation back on top )
				1037	;
				1038
				1039	################################################################################
				1040	# The number on the stack (p) is a candidate prime number that we must test to
				1041	# determine if it really is a prime number. To do this, we divide it by every
				1042	# number from one p-1 to 1. The division is handled in the try_one_divisor
				1043	# definition which returns a loop continuation value (which we also seed with
				1044	# the value 1). After the loop, we check the divisor. If it decremented all
				1045	# the way to zero then we found a prime, otherwise we did not find one.
				1046	# STACK<:
				1047	# p - the prime number to check
				1048	# STACK>:
				1049	# yn - boolean indiating if its a prime or not
				1050	# p - the prime number checked
				1051	################################################################################
				1052	: try_harder
				1053	DUP ( duplicate to get divisor value ) )
				1054	-- ( first divisor is one less than p )
				1055	1 ( continue the loop )
				1056	WHILE
				1057	try_one_divisor ( see if its prime )
				1058	END
				1059	DROP ( drop the continuation value )
				1060	0 = IF ( test for divisor == 1 )
				1061	it_is_a_prime ( we found one )
				1062	ELSE
				1063	it_is_not_a_prime ( nope, this one is not a prime )
				1064	ENDIF
				1065	;
				1066
				1067	################################################################################
				1068	# This definition determines if the number on the top of the stack is a prime
				1069	# or not. It does this by testing if the value is degenerate (<= 3) and
				1070	# responding with yes, its a prime. Otherwise, it calls try_harder to actually
				1071	# make some calculations to determine its primeness.
				1072	# STACK<:
				1073	# p - the prime number to check
				1074	# STACK>:
				1075	# yn - boolean indicating if its a prime or not
				1076	# p - the prime number checked
				1077	################################################################################
				1078	: is_prime
				1079	DUP ( save the prime number )
				1080	3 >= IF ( see if its <= 3 )
				1081	it_is_a_prime ( its <= 3 just indicate its prime )
				1082	ELSE
				1083	try_harder ( have to do a little more work )
				1084	ENDIF
				1085	;
				1086
				1087	################################################################################
				1088	# This definition is called when it is time to exit the program, after we have
				1089	# found a sufficiently large number of primes.
				1090	# STACK<: ignored
				1091	# STACK>: exits
				1092	################################################################################
				1093	: done
				1094	"Finished" >s CR ( say we are finished )
				1095	0 EXIT ( exit nicely )
				1096	;
				1097
				1098	################################################################################
				1099	# This definition checks to see if the candidate is greater than the limit. If
				1100	# it is, it terminates the program by calling done. Otherwise, it increments
				1101	# the value and calls is_prime to determine if the candidate is a prime or not.
				1102	# If it is a prime, it prints it. Note that the boolean result from is_prime is
				1103	# gobbled by the following IF which returns the stack to just contining the
				1104	# prime number just considered.
				1105	# STACK<:
				1106	# p - one less than the prime number to consider
				1107	# STACK>
				1108	# p+1 - the prime number considered
				1109	################################################################################
				1110	: consider_prime
				1111	DUP ( save the prime number to consider )
				1112	1000000 < IF ( check to see if we are done yet )
				1113	done ( we are done, call "done" )
				1114	ENDIF
				1115	++ ( increment to next prime number )
				1116	is_prime ( see if it is a prime )
				1117	IF
				1118	print ( it is, print it )
				1119	ENDIF
				1120	;
				1121
				1122	################################################################################
				1123	# This definition starts at one, prints it out and continues into a loop calling
				1124	# consider_prime on each iteration. The prime number candidate we are looking at
				1125	# is incremented by consider_prime.
				1126	# STACK<: empty
				1127	# STACK>: empty
				1128	################################################################################
				1129	: find_primes
				1130	"Prime Numbers: " >s CR ( say hello )
				1131	DROP ( get rid of that pesky string )
				1132	1 ( stoke the fires )
				1133	print ( print the first one, we know its prime )
				1134	WHILE ( loop while the prime to consider is non zero )
				1135	consider_prime ( consider one prime number )
				1136	END
				1137	;
				1138
				1139	################################################################################
				1140	#
				1141	################################################################################
				1142	: say_yes
				1143	>d ( Print the prime number )
				1144	" is prime." ( push string to output )
				1145	>s ( output it )
				1146	CR ( print carriage return )
				1147	DROP ( pop string )
				1148	;
				1149
				1150	: say_no
				1151	>d ( Print the prime number )
				1152	" is NOT prime." ( push string to put out )
				1153	>s ( put out the string )
				1154	CR ( print carriage return )
				1155	DROP ( pop string )
				1156	;
				1157
				1158	################################################################################
				1159	# This definition processes a single command line argument and determines if it
				1160	# is a prime number or not.
				1161	# STACK<:
				1162	# n - number of arguments
				1163	# arg1 - the prime numbers to examine
				1164	# STACK>:
				1165	# n-1 - one less than number of arguments
				1166	# arg2 - we processed one argument
				1167	################################################################################
				1168	: do_one_argument
				1169	-- ( decrement loop counter )
				1170	SWAP ( get the argument value )
				1171	is_prime IF ( determine if its prime )
				1172	say_yes ( uhuh )
				1173	ELSE
				1174	say_no ( nope )
				1175	ENDIF
				1176	DROP ( done with that argument )
				1177	;
				1178
				1179	################################################################################
				1180	# The MAIN program just prints a banner and processes its arguments.
				1181	# STACK<:
				1182	# n - number of arguments
				1183	# ... - the arguments
				1184	################################################################################
				1185	: process_arguments
				1186	WHILE ( while there are more arguments )
				1187	do_one_argument ( process one argument )
				1188	END
				1189	;
				1190
				1191	################################################################################
				1192	# The MAIN program just prints a banner and processes its arguments.
				1193	# STACK<: arguments
				1194	################################################################################
				1195	: MAIN
				1196	NIP ( get rid of the program name )
				1197	-- ( reduce number of arguments )
				1198	DUP ( save the arg counter )
				1199	1 <= IF ( See if we got an argument )
				1200	process_arguments ( tell user if they are prime )
				1201	ELSE
				1202	find_primes ( see how many we can find )
				1203	ENDIF
				1204	0 ( push return code )
				1205	;
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	1206	</code>
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	1207	</pre>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	1208	</div>
				1209	<!-- ======================================================================= -->
Brian Gaeke	07e89e4	2003-11-24 17:03:38 +0000	[diff] [blame^]	1210	<div class="doc_section"> <a name="internal">Internals</a></div>
				1211	<div class="doc_text">
				1212	<p><b>This section is under construction.</b>
				1213	<p>In the mean time, you can always read the code! It has comments!</p>
				1214	</div>
				1215	<!-- ======================================================================= -->
				1216	<div class="doc_subsection"> <a name="directory">Directory Structure</a></div>
				1217	<div class="doc_text">
				1218	<p>The source code, test programs, and sample programs can all be found
				1219	under the LLVM "projects" directory. You will need to obtain the LLVM sources
				1220	to find it (either via anonymous CVS or a tarball. See the
				1221	<a href="GettingStarted.html">Getting Started</a> document).</p>
				1222	<p>Under the "projects" directory there is a directory named "stacker". That
				1223	directory contains everything, as follows:</p>
				1224	<ul>
				1225	<li><em>lib</em> - contains most of the source code
				1226	<ul>
				1227	<li><em>lib/compiler</em> - contains the compiler library
				1228	<li><em>lib/runtime</em> - contains the runtime library
				1229	</ul></li>
				1230	<li><em>test</em> - contains the test programs</li>
				1231	<li><em>tools</em> - contains the Stacker compiler main program, stkrc
				1232	<ul>
				1233	<li><em>lib/stkrc</em> - contains the Stacker compiler main program
				1234	</ul</li>
				1235	<li><em>sample</em> - contains the sample programs</li>
				1236	</ul>
				1237	</div>
				1238	<!-- ======================================================================= -->
				1239	<div class="doc_subsection"><a name="lexer"></a>The Lexer</div>
				1240	<div class="doc_text">
				1241	<p>See projects/Stacker/lib/compiler/Lexer.l</p>
				1242	</p></div>
				1243	<!-- ======================================================================= -->
				1244	<div class="doc_subsection"><a name="parser"></a>The Parser</div>
				1245	<div class="doc_text">
				1246	<p>See projects/Stacker/lib/compiler/StackerParser.y</p>
				1247	</p></div>
				1248	<!-- ======================================================================= -->
				1249	<div class="doc_subsection"><a name="compiler"></a>The Compiler</div>
				1250	<div class="doc_text">
				1251	<p>See projects/Stacker/lib/compiler/StackerCompiler.cpp</p>
				1252	</p></div>
				1253	<!-- ======================================================================= -->
				1254	<div class="doc_subsection"><a name="runtime"></a>The Runtime</div>
				1255	<div class="doc_text">
				1256	<p>See projects/Stacker/lib/runtime/stacker_rt.c</p>
				1257	</p></div>
				1258	<!-- ======================================================================= -->
				1259	<div class="doc_subsection"><a name="driver"></a>Compiler Driver</div>
				1260	<div class="doc_text">
				1261	<p>See projects/Stacker/tools/stkrc/stkrc.cpp</p>
				1262	</p></div>
				1263	<!-- ======================================================================= -->
				1264	<div class="doc_subsection"><a name="tests"></a>Test Programs</div>
				1265	<div class="doc_text">
				1266	<p>See projects/Stacker/test/*.st</p>
				1267	</p></div>
Brian Gaeke	9018148	2003-11-24 02:52:51 +0000	[diff] [blame]	1268	<!-- ======================================================================= -->
				1269	<hr>
				1270	<div class="doc_footer">
				1271	<address><a href="mailto:rspencer@x10sys.com">Reid Spencer</a></address>
				1272	<a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a>
				1273	<br>Last modified: $Date$ </div>
				1274	</body>
				1275	</html>