summaryrefslogtreecommitdiff
path: root/doc/codewalk
diff options
context:
space:
mode:
Diffstat (limited to 'doc/codewalk')
-rw-r--r--doc/codewalk/codewalk.css234
-rw-r--r--doc/codewalk/codewalk.js305
-rw-r--r--doc/codewalk/codewalk.xml124
-rw-r--r--doc/codewalk/functions.xml115
-rw-r--r--doc/codewalk/markov.go130
-rw-r--r--doc/codewalk/markov.xml308
-rw-r--r--doc/codewalk/pig.go124
-rw-r--r--doc/codewalk/popout.pngbin0 -> 213 bytes
-rw-r--r--doc/codewalk/sharemem.xml181
-rw-r--r--doc/codewalk/urlpoll.go117
10 files changed, 1638 insertions, 0 deletions
diff --git a/doc/codewalk/codewalk.css b/doc/codewalk/codewalk.css
new file mode 100644
index 000000000..a0814e4d2
--- /dev/null
+++ b/doc/codewalk/codewalk.css
@@ -0,0 +1,234 @@
+/*
+ Copyright 2010 The Go Authors. All rights reserved.
+ Use of this source code is governed by a BSD-style
+ license that can be found in the LICENSE file.
+*/
+
+#codewalk-main {
+ text-align: left;
+ width: 100%;
+ overflow: auto;
+}
+
+#code-display {
+ border: 0;
+ width: 100%;
+}
+
+.setting {
+ font-size: 8pt;
+ color: #888888;
+ padding: 5px;
+}
+
+.hotkey {
+ text-decoration: underline;
+}
+
+/* Style for Comments (the left-hand column) */
+
+#comment-column {
+ margin: 0pt;
+ width: 30%;
+}
+
+#comment-column.right {
+ float: right;
+}
+
+#comment-column.left {
+ float: left;
+}
+
+#comment-area {
+ overflow-x: hidden;
+ overflow-y: auto;
+}
+
+.comment {
+ cursor: pointer;
+ font-size: 16px;
+ border: 2px solid #ba9836;
+ margin-bottom: 10px;
+ margin-right: 10px; /* yes, for both .left and .right */
+}
+
+.comment:last-child {
+ margin-bottom: 0px;
+}
+
+.right .comment {
+ margin-left: 10px;
+}
+
+.right .comment.first {
+}
+
+.right .comment.last {
+}
+
+.left .comment.first {
+}
+
+.left .comment.last {
+}
+
+.comment.selected {
+ border-color: #99b2cb;
+}
+
+.right .comment.selected {
+ border-left-width: 12px;
+ margin-left: 0px;
+}
+
+.left .comment.selected {
+ border-right-width: 12px;
+ margin-right: 0px;
+}
+
+.comment-link {
+ display: none;
+}
+
+.comment-title {
+ font-size: small;
+ font-weight: bold;
+ background-color: #fffff0;
+ padding-right: 10px;
+ padding-left: 10px;
+ padding-top: 5px;
+ padding-bottom: 5px;
+}
+
+.right .comment-title {
+}
+
+.left .comment-title {
+}
+
+.comment.selected .comment-title {
+ background-color: #f8f8ff;
+}
+
+.comment-text {
+ overflow: auto;
+ padding-left: 10px;
+ padding-right: 10px;
+ padding-top: 10px;
+ padding-bottom: 5px;
+ font-size: small;
+ line-height: 1.3em;
+}
+
+.comment-text p {
+ margin-top: 0em;
+ margin-bottom: 0.5em;
+}
+
+.comment-text p:last-child {
+ margin-bottom: 0em;
+}
+
+.file-name {
+ font-size: x-small;
+ padding-top: 0px;
+ padding-bottom: 5px;
+}
+
+.hidden-filepaths .file-name {
+ display: none;
+}
+
+.path-dir {
+ color: #555;
+}
+
+.path-file {
+ color: #555;
+}
+
+
+/* Style for Code (the right-hand column) */
+
+/* Wrapper for the code column to make widths get calculated correctly */
+#code-column {
+ display: block;
+ position: relative;
+ margin: 0pt;
+ width: 70%;
+}
+
+#code-column.left {
+ float: left;
+}
+
+#code-column.right {
+ float: right;
+}
+
+#code-area {
+ background-color: #f8f8ff;
+ border: 2px solid #99b2cb;
+ padding: 5px;
+}
+
+.left #code-area {
+ margin-right: -1px;
+}
+
+.right #code-area {
+ margin-left: -1px;
+}
+
+#code-header {
+ margin-bottom: 5px;
+}
+
+#code {
+ background-color: white;
+}
+
+code {
+ font-size: 100%;
+}
+
+.codewalkhighlight {
+ font-weight: bold;
+ background-color: #f8f8ff;
+}
+
+#code-display {
+ margin-top: 0px;
+ margin-bottom: 0px;
+}
+
+#sizer {
+ position: absolute;
+ cursor: col-resize;
+ left: 0px;
+ top: 0px;
+ width: 8px;
+}
+
+/* Style for options (bottom strip) */
+
+#code-options {
+ display: none;
+}
+
+#code-options > span {
+ padding-right: 20px;
+}
+
+#code-options .selected {
+ border-bottom: 1px dotted;
+}
+
+#comment-options {
+ text-align: center;
+}
+
+div#content {
+ padding-bottom: 0em;
+}
diff --git a/doc/codewalk/codewalk.js b/doc/codewalk/codewalk.js
new file mode 100644
index 000000000..f780bc7a5
--- /dev/null
+++ b/doc/codewalk/codewalk.js
@@ -0,0 +1,305 @@
+// Copyright 2010 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+/**
+ * A class to hold information about the Codewalk Viewer.
+ * @param {jQuery} context The top element in whose context the viewer should
+ * operate. It will not touch any elements above this one.
+ * @constructor
+ */
+ var CodewalkViewer = function(context) {
+ this.context = context;
+
+ /**
+ * The div that contains all of the comments and their controls.
+ */
+ this.commentColumn = this.context.find('#comment-column');
+
+ /**
+ * The div that contains the comments proper.
+ */
+ this.commentArea = this.context.find('#comment-area');
+
+ /**
+ * The div that wraps the iframe with the code, as well as the drop down menu
+ * listing the different files.
+ * @type {jQuery}
+ */
+ this.codeColumn = this.context.find('#code-column');
+
+ /**
+ * The div that contains the code but excludes the options strip.
+ * @type {jQuery}
+ */
+ this.codeArea = this.context.find('#code-area');
+
+ /**
+ * The iframe that holds the code (from Sourcerer).
+ * @type {jQuery}
+ */
+ this.codeDisplay = this.context.find('#code-display');
+
+ /**
+ * The overlaid div used as a grab handle for sizing the code/comment panes.
+ * @type {jQuery}
+ */
+ this.sizer = this.context.find('#sizer');
+
+ /**
+ * The full-screen overlay that ensures we don't lose track of the mouse
+ * while dragging.
+ * @type {jQuery}
+ */
+ this.overlay = this.context.find('#overlay');
+
+ /**
+ * The hidden input field that we use to hold the focus so that we can detect
+ * shortcut keypresses.
+ * @type {jQuery}
+ */
+ this.shortcutInput = this.context.find('#shortcut-input');
+
+ /**
+ * The last comment that was selected.
+ * @type {jQuery}
+ */
+ this.lastSelected = null;
+};
+
+/**
+ * Minimum width of the comments or code pane, in pixels.
+ * @type {number}
+ */
+CodewalkViewer.MIN_PANE_WIDTH = 200;
+
+/**
+ * Navigate the code iframe to the given url and update the code popout link.
+ * @param {string} url The target URL.
+ * @param {Object} opt_window Window dependency injection for testing only.
+ */
+CodewalkViewer.prototype.navigateToCode = function(url, opt_window) {
+ if (!opt_window) opt_window = window;
+ // Each iframe is represented by two distinct objects in the DOM: an iframe
+ // object and a window object. These do not expose the same capabilities.
+ // Here we need to get the window representation to get the location member,
+ // so we access it directly through window[] since jQuery returns the iframe
+ // representation.
+ // We replace location rather than set so as not to create a history for code
+ // navigation.
+ opt_window['code-display'].location.replace(url);
+ var k = url.indexOf('&');
+ if (k != -1) url = url.slice(0, k);
+ k = url.indexOf('fileprint=');
+ if (k != -1) url = url.slice(k+10, url.length);
+ this.context.find('#code-popout-link').attr('href', url);
+};
+
+/**
+ * Selects the first comment from the list and forces a refresh of the code
+ * view.
+ */
+CodewalkViewer.prototype.selectFirstComment = function() {
+ // TODO(rsc): handle case where there are no comments
+ var firstSourcererLink = this.context.find('.comment:first');
+ this.changeSelectedComment(firstSourcererLink);
+};
+
+/**
+ * Sets the target on all links nested inside comments to be _blank.
+ */
+CodewalkViewer.prototype.targetCommentLinksAtBlank = function() {
+ this.context.find('.comment a[href], #description a[href]').each(function() {
+ if (!this.target) this.target = '_blank';
+ });
+};
+
+/**
+ * Installs event handlers for all the events we care about.
+ */
+CodewalkViewer.prototype.installEventHandlers = function() {
+ var self = this;
+
+ this.context.find('.comment')
+ .click(function(event) {
+ if (jQuery(event.target).is('a[href]')) return true;
+ self.changeSelectedComment(jQuery(this));
+ return false;
+ });
+
+ this.context.find('#code-selector')
+ .change(function() {self.navigateToCode(jQuery(this).val());});
+
+ this.context.find('#description-table .quote-feet.setting')
+ .click(function() {self.toggleDescription(jQuery(this)); return false;});
+
+ this.sizer
+ .mousedown(function(ev) {self.startSizerDrag(ev); return false;});
+ this.overlay
+ .mouseup(function(ev) {self.endSizerDrag(ev); return false;})
+ .mousemove(function(ev) {self.handleSizerDrag(ev); return false;});
+
+ this.context.find('#prev-comment')
+ .click(function() {
+ self.changeSelectedComment(self.lastSelected.prev()); return false;
+ });
+
+ this.context.find('#next-comment')
+ .click(function() {
+ self.changeSelectedComment(self.lastSelected.next()); return false;
+ });
+
+ // Workaround for Firefox 2 and 3, which steal focus from the main document
+ // whenever the iframe content is (re)loaded. The input field is not shown,
+ // but is a way for us to bring focus back to a place where we can detect
+ // keypresses.
+ this.context.find('#code-display')
+ .load(function(ev) {self.shortcutInput.focus();});
+
+ jQuery(document).keypress(function(ev) {
+ switch(ev.which) {
+ case 110: // 'n'
+ self.changeSelectedComment(self.lastSelected.next());
+ return false;
+ case 112: // 'p'
+ self.changeSelectedComment(self.lastSelected.prev());
+ return false;
+ default: // ignore
+ }
+ });
+
+ window.onresize = function() {self.updateHeight();};
+};
+
+/**
+ * Starts dragging the pane sizer.
+ * @param {Object} ev The mousedown event that started us dragging.
+ */
+CodewalkViewer.prototype.startSizerDrag = function(ev) {
+ this.initialCodeWidth = this.codeColumn.width();
+ this.initialCommentsWidth = this.commentColumn.width();
+ this.initialMouseX = ev.pageX;
+ this.overlay.show();
+};
+
+/**
+ * Handles dragging the pane sizer.
+ * @param {Object} ev The mousemove event updating dragging position.
+ */
+CodewalkViewer.prototype.handleSizerDrag = function(ev) {
+ var delta = ev.pageX - this.initialMouseX;
+ if (this.codeColumn.is('.right')) delta = -delta;
+ var proposedCodeWidth = this.initialCodeWidth + delta;
+ var proposedCommentWidth = this.initialCommentsWidth - delta;
+ var mw = CodewalkViewer.MIN_PANE_WIDTH;
+ if (proposedCodeWidth < mw) delta = mw - this.initialCodeWidth;
+ if (proposedCommentWidth < mw) delta = this.initialCommentsWidth - mw;
+ proposedCodeWidth = this.initialCodeWidth + delta;
+ proposedCommentWidth = this.initialCommentsWidth - delta;
+ // If window is too small, don't even try to resize.
+ if (proposedCodeWidth < mw || proposedCommentWidth < mw) return;
+ this.codeColumn.width(proposedCodeWidth);
+ this.commentColumn.width(proposedCommentWidth);
+ this.options.codeWidth = parseInt(
+ this.codeColumn.width() /
+ (this.codeColumn.width() + this.commentColumn.width()) * 100);
+ this.context.find('#code-column-width').text(this.options.codeWidth + '%');
+};
+
+/**
+ * Ends dragging the pane sizer.
+ * @param {Object} ev The mouseup event that caused us to stop dragging.
+ */
+CodewalkViewer.prototype.endSizerDrag = function(ev) {
+ this.overlay.hide();
+ this.updateHeight();
+};
+
+/**
+ * Toggles the Codewalk description between being shown and hidden.
+ * @param {jQuery} target The target that was clicked to trigger this function.
+ */
+CodewalkViewer.prototype.toggleDescription = function(target) {
+ var description = this.context.find('#description');
+ description.toggle();
+ target.find('span').text(description.is(':hidden') ? 'show' : 'hide');
+ this.updateHeight();
+};
+
+/**
+ * Changes the side of the window on which the code is shown and saves the
+ * setting in a cookie.
+ * @param {string?} codeSide The side on which the code should be, either
+ * 'left' or 'right'.
+ */
+CodewalkViewer.prototype.changeCodeSide = function(codeSide) {
+ var commentSide = codeSide == 'left' ? 'right' : 'left';
+ this.context.find('#set-code-' + codeSide).addClass('selected');
+ this.context.find('#set-code-' + commentSide).removeClass('selected');
+ // Remove previous side class and add new one.
+ this.codeColumn.addClass(codeSide).removeClass(commentSide);
+ this.commentColumn.addClass(commentSide).removeClass(codeSide);
+ this.sizer.css(codeSide, 'auto').css(commentSide, 0);
+ this.options.codeSide = codeSide;
+};
+
+/**
+ * Adds selected class to newly selected comment, removes selected style from
+ * previously selected comment, changes drop down options so that the correct
+ * file is selected, and updates the code popout link.
+ * @param {jQuery} target The target that was clicked to trigger this function.
+ */
+CodewalkViewer.prototype.changeSelectedComment = function(target) {
+ var currentFile = target.find('.comment-link').attr('href');
+ if (!currentFile) return;
+
+ if (!(this.lastSelected && this.lastSelected.get(0) === target.get(0))) {
+ if (this.lastSelected) this.lastSelected.removeClass('selected');
+ target.addClass('selected');
+ this.lastSelected = target;
+ var targetTop = target.position().top;
+ var parentTop = target.parent().position().top;
+ if (targetTop + target.height() > parentTop + target.parent().height() ||
+ targetTop < parentTop) {
+ var delta = targetTop - parentTop;
+ target.parent().animate(
+ {'scrollTop': target.parent().scrollTop() + delta},
+ Math.max(delta / 2, 200), 'swing');
+ }
+ var fname = currentFile.match(/(?:select=|fileprint=)\/[^&]+/)[0];
+ fname = fname.slice(fname.indexOf('=')+2, fname.length);
+ this.context.find('#code-selector').val(fname);
+ this.context.find('#prev-comment').toggleClass(
+ 'disabled', !target.prev().length);
+ this.context.find('#next-comment').toggleClass(
+ 'disabled', !target.next().length);
+ }
+
+ // Force original file even if user hasn't changed comments since they may
+ // have nagivated away from it within the iframe without us knowing.
+ this.navigateToCode(currentFile);
+};
+
+/**
+ * Updates the viewer by changing the height of the comments and code so that
+ * they fit within the height of the window. The function is typically called
+ * after the user changes the window size.
+ */
+CodewalkViewer.prototype.updateHeight = function() {
+ var windowHeight = jQuery(window).height() - 5 // GOK
+ var areaHeight = windowHeight - this.codeArea.offset().top
+ var footerHeight = this.context.find('#footer').outerHeight(true)
+ this.commentArea.height(areaHeight - footerHeight - this.context.find('#comment-options').outerHeight(true))
+ var codeHeight = areaHeight - footerHeight - 15 // GOK
+ this.codeArea.height(codeHeight)
+ this.codeDisplay.height(codeHeight - this.codeDisplay.offset().top + this.codeArea.offset().top);
+ this.sizer.height(codeHeight);
+};
+
+jQuery(document).ready(function() {
+ var viewer = new CodewalkViewer(jQuery());
+ viewer.selectFirstComment();
+ viewer.targetCommentLinksAtBlank();
+ viewer.installEventHandlers();
+ viewer.updateHeight();
+});
diff --git a/doc/codewalk/codewalk.xml b/doc/codewalk/codewalk.xml
new file mode 100644
index 000000000..9cd8361e8
--- /dev/null
+++ b/doc/codewalk/codewalk.xml
@@ -0,0 +1,124 @@
+<codewalk title="How to Write a Codewalk">
+
+<step title="Introduction" src="doc/codewalk/codewalk.xml">
+ A codewalk is a guided tour through a piece of code.
+ It consists of a sequence of steps, each typically explaining
+ a highlighted section of code.
+ <br/><br/>
+
+ The <a href="/cmd/godoc">godoc</a> web server translates
+ an XML file like the one in the main window pane into the HTML
+ page that you're viewing now.
+ <br/><br/>
+
+ The codewalk with URL path <code>/doc/codewalk/</code><i>name</i>
+ is loaded from the input file <code>$GOROOT/doc/codewalk/</code><i>name</i><code>.xml</code>.
+ <br/><br/>
+
+ This codewalk explains how to write a codewalk by examining
+ its own source code,
+ <code><a href="/doc/codewalk/codewalk.xml">$GOROOT/doc/codewalk/codewalk.xml</a></code>,
+ shown in the main window pane to the left.
+</step>
+
+<step title="Title" src="doc/codewalk/codewalk.xml:/title=/">
+ The codewalk input file is an XML file containing a single
+ <code>&lt;codewalk&gt;</code> element.
+ That element's <code>title</code> attribute gives the title
+ that is used both on the codewalk page and in the codewalk list.
+</step>
+
+<step title="Steps" src="doc/codewalk/codewalk.xml:/&lt;step/,/step&gt;/">
+ Each step in the codewalk is a <code>&lt;step&gt;</code> element
+ nested inside the main <code>&lt;codewalk&gt;</code>.
+ The step element's <code>title</code> attribute gives the step's title,
+ which is shown in a shaded bar above the main step text.
+ The element's <code>src</code> attribute specifies the source
+ code to show in the main window pane and, optionally, a range of
+ lines to highlight.
+ <br/><br/>
+
+ The first step in this codewalk does not highlight any lines:
+ its <code>src</code> is just a file name.
+</step>
+
+<step title="Specifiying a source line" src='doc/codewalk/codewalk.xml:/title="Title"/'>
+ The most complex part of the codewalk specification is
+ saying what lines to highlight.
+ Instead of ordinary line numbers,
+ the codewalk uses an address syntax that makes it possible
+ to describe the match by its content.
+ As the file gets edited, this descriptive address has a better
+ chance to continue to refer to the right section of the file.
+ <br/><br/>
+
+ To specify a source line, use a <code>src</code> attribute of the form
+ <i>filename</i><code>:</code><i>address</i>,
+ where <i>address</i> is an address in the syntax used by the text editors <i>sam</i> and <i>acme</i>.
+ <br/><br/>
+
+ The simplest address is a single regular expression.
+ The highlighted line in the main window pane shows that the
+ address for the &ldquo;Title&rdquo; step was <code>/title=/</code>,
+ which matches the first instance of that <a href="/pkg/regexp">regular expression</a> (<code>title=</code>) in the file.
+</step>
+
+<step title="Specifying a source range" src='doc/codewalk/codewalk.xml:/title="Steps"/'>
+ To highlight a range of source lines, the simplest address to use is
+ a pair of regular expressions
+ <code>/</code><i>regexp1</i><code>/,/</code><i>regexp2</i><code>/</code>.
+ The highlight begins with the line containing the first match for <i>regexp1</i>
+ and ends with the line containing the first match for <i>regexp2</i>
+ after the end of the match for <i>regexp1</i>.
+ Ignoring the HTML quoting,
+ The line containing the first match for <i>regexp1</i> will be the first one highlighted,
+ and the line containing the first match for <i>regexp2</i>.
+ <br/><br/>
+
+ The address <code>/&lt;step/,/step&gt;/</code> looks for the first instance of
+ <code>&lt;step</code> in the file, and then starting after that point,
+ looks for the first instance of <code>step&gt;</code>.
+ (Click on the &ldquo;Steps&rdquo; step above to see the highlight in action.)
+ Note that the <code>&lt;</code> and <code>&gt;</code> had to be written
+ using XML escapes in order to be valid XML.
+</step>
+
+<step title="Advanced addressing" src="doc/codewalk/codewalk.xml:/Advanced/,/step&gt;/">
+ The <code>/</code><i>regexp</i><code>/</code>
+ and <code>/</code><i>regexp1</i><code>/,/</code><i>regexp2</i><code>/</code>
+ forms suffice for most highlighting.
+ <br/><br/>
+
+ The full address syntax is summarized in this table
+ (an excerpt of Table II from
+ <a href="http://plan9.bell-labs.com/sys/doc/sam/sam.html">The text editor <code>sam</code></a>):
+ <br/><br/>
+
+ <table>
+ <tr><td colspan="2"><b>Simple addresses</b></td></tr>
+ <tr><td><code>#</code><i>n</i></td>
+ <td>The empty string after character <i>n</i></td></tr>
+ <tr><td><i>n</i></td>
+ <td>Line <i>n</i></td></tr>
+ <tr><td><code>/</code><i>regexp</i><code>/</code></td>
+ <td>The first following match of the regular expression</td></tr>
+ <!-- not supported (yet?)
+ <tr><td><code>–/</code><i>regexp</i><code>/</code></td>
+ <td>The first previous match of the regular expression</td></tr>
+ -->
+ <tr><td><code>$</code></td>
+ <td>The null string at the end of the file</td></tr>
+
+ <tr><td colspan="2"><b>Compound addresses</b></td></tr>
+ <tr><td><i>a1</i><code>+</code><i>a2</i></td>
+ <td>The address <i>a2</i> evaluated starting at the right of <i>a1</i></td></tr>
+ <tr><td><i>a1</i><code>-</code><i>a2</i></td>
+ <td>The address <i>a2</i> evaluated in the reverse direction starting at the left of <i>a1</i></td></tr>
+ <tr><td><i>a1</i><code>,</code><i>a2</i></td>
+ <td>From the left of <i>a1</i> to the right of <i>a2</i> (default <code>0,$</code>).</td></tr>
+ </table>
+</step>
+
+
+
+</codewalk>
diff --git a/doc/codewalk/functions.xml b/doc/codewalk/functions.xml
new file mode 100644
index 000000000..986a017e1
--- /dev/null
+++ b/doc/codewalk/functions.xml
@@ -0,0 +1,115 @@
+<codewalk title="First-Class Functions in Go">
+
+<step title="Introduction" src="doc/codewalk/pig.go">
+ Go supports first class functions, higher-order functions, user-defined
+ function types, function literals, closures, and multiple return values.
+ <br/><br/>
+
+ This rich feature set supports a functional programming style in a strongly
+ typed language.
+ <br/><br/>
+
+ In this codewalk we will look at a simple program that simulates a dice game
+ called <a href="http://en.wikipedia.org/wiki/Pig_(dice)">Pig</a> and evaluates
+ basic strategies.
+</step>
+
+<step title="Game overview" src="doc/codewalk/pig.go:/\/\/ A score/,/thisTurn int\n}/">
+ Pig is a two-player game played with a 6-sided die. Each turn, you may roll or stay.
+ <ul>
+ <li> If you roll a 1, you lose all points for your turn and play passes to
+ your opponent. Any other roll adds its value to your turn score. </li>
+ <li> If you stay, your turn score is added to your total score, and play passes
+ to your opponent. </li>
+ </ul>
+
+ The first person to reach 100 total points wins.
+ <br/><br/>
+
+ The <code>score</code> type stores the scores of the current and opposing
+ players, in addition to the points accumulated during the current turn.
+</step>
+
+<step title="User-defined function types" src="doc/codewalk/pig.go:/\/\/ An action/,/bool\)/">
+ In Go, functions can be passed around just like any other value. A function's
+ type signature describes the types of its arguments and return values.
+ <br/><br/>
+
+ The <code>action</code> type is a function that takes a <code>score</code>
+ and returns the resulting <code>score</code> and whether the current turn is
+ over.
+ <br/><br/>
+
+ If the turn is over, the <code>player</code> and <code>opponent</code> fields
+ in the resulting <code>score</code> should be swapped, as it is now the other player's
+ turn.
+</step>
+
+<step title="Multiple return values" src="doc/codewalk/pig.go:/\/\/ roll returns/,/stay.*true\n}/">
+ Go functions can return multiple values.
+ <br/><br/>
+
+ The functions <code>roll</code> and <code>stay</code> each return a pair of
+ values. They also match the <code>action</code> type signature. These
+ <code>action</code> functions define the rules of Pig.
+</step>
+
+<step title="Higher-order functions" src="doc/codewalk/pig.go:/\/\/ A strategy/,/action\n/">
+ A function can use other functions as arguments and return values.
+ <br/><br/>
+
+ A <code>strategy</code> is a function that takes a <code>score</code> as input
+ and returns an <code>action</code> to perform. <br/>
+ (Remember, an <code>action</code> is itself a function.)
+</step>
+
+<step title="Function literals and closures" src="doc/codewalk/pig.go:/return func/,/return roll\n\t}/">
+ Anonymous functions can be declared in Go, as in this example. Function
+ literals are closures: they inherit the scope of the function in which they
+ are declared.
+ <br/><br/>
+
+ One basic strategy in Pig is to continue rolling until you have accumulated at
+ least k points in a turn, and then stay. The argument <code>k</code> is
+ enclosed by this function literal, which matches the <code>strategy</code> type
+ signature.
+</step>
+
+<step title="Simulating games" src="doc/codewalk/pig.go:/\/\/ play/,/currentPlayer\n}/">
+ We simulate a game of Pig by calling an <code>action</code> to update the
+ <code>score</code> until one player reaches 100 points. Each
+ <code>action</code> is selected by calling the <code>strategy</code> function
+ associated with the current player.
+</step>
+
+<step title="Comparing functions" src="doc/codewalk/pig.go:/if action/,/currentPlayer\)\)\n\t\t}/">
+ Functions can be compared for equality in Go. From the
+ <a href="http://golang.org/doc/go_spec.html#Comparison_operators">language specification</a>:
+ Function values are equal if they refer to the same function or if both are <code>nil</code>.
+ <br/><br/>
+
+ We enforce that a <code>strategy</code> function can only return a legal
+ <code>action</code>: either <code>roll</code> or <code>stay</code>.
+</step>
+
+<step title="Simulating a tournament" src="doc/codewalk/pig.go:/\/\/ roundRobin/,/gamesPerStrategy\n}/">
+ The <code>roundRobin</code> function simulates a tournament and tallies wins.
+ Each strategy plays each other strategy <code>gamesPerSeries</code> times.
+</step>
+
+<step title="Variadic function declarations" src="doc/codewalk/pig.go:/\/\/ ratioS/,/string {/">
+ Variadic functions like <code>ratioString</code> take a variable number of
+ arguments. These arguments are available as a slice inside the function.
+</step>
+
+<step title="Simulation results" src="doc/codewalk/pig.go:/func main/,/\n}/">
+ The <code>main</code> function defines 100 basic strategies, simulates a round
+ robin tournament, and then prints the win/loss record of each strategy.
+ <br/><br/>
+
+ Among these strategies, staying at 25 is best, but the <a
+ href="http://www.google.com/search?q=optimal+play+pig">optimal strategy for
+ Pig</a> is much more complex.
+</step>
+
+</codewalk>
diff --git a/doc/codewalk/markov.go b/doc/codewalk/markov.go
new file mode 100644
index 000000000..959c2b158
--- /dev/null
+++ b/doc/codewalk/markov.go
@@ -0,0 +1,130 @@
+// Copyright 2011 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+/*
+Generating random text: a Markov chain algorithm
+
+Based on the program presented in the "Design and Implementation" chapter
+of The Practice of Programming (Kernighan and Pike, Addison-Wesley 1999).
+See also Computer Recreations, Scientific American 260, 122 - 125 (1989).
+
+A Markov chain algorithm generates text by creating a statistical model of
+potential textual suffixes for a given prefix. Consider this text:
+
+ I am not a number! I am a free man!
+
+Our Markov chain algorithm would arrange this text into this set of prefixes
+and suffixes, or "chain": (This table assumes a prefix length of two words.)
+
+ Prefix Suffix
+
+ "" "" I
+ "" I am
+ I am a
+ I am not
+ a free man!
+ am a free
+ am not a
+ a number! I
+ number! I am
+ not a number!
+
+To generate text using this table we select an initial prefix ("I am", for
+example), choose one of the suffixes associated with that prefix at random
+with probability determined by the input statistics ("a"),
+and then create a new prefix by removing the first word from the prefix
+and appending the suffix (making the new prefix is "am a"). Repeat this process
+until we can't find any suffixes for the current prefix or we exceed the word
+limit. (The word limit is necessary as the chain table may contain cycles.)
+
+Our version of this program reads text from standard input, parsing it into a
+Markov chain, and writes generated text to standard output.
+The prefix and output lengths can be specified using the -prefix and -words
+flags on the command-line.
+*/
+package main
+
+import (
+ "bufio"
+ "flag"
+ "fmt"
+ "io"
+ "os"
+ "rand"
+ "strings"
+ "time"
+)
+
+// Prefix is a Markov chain prefix of one or more words.
+type Prefix []string
+
+// String returns the Prefix as a string (for use as a map key).
+func (p Prefix) String() string {
+ return strings.Join(p, " ")
+}
+
+// Shift removes the first word from the Prefix and appends the given word.
+func (p Prefix) Shift(word string) {
+ copy(p, p[1:])
+ p[len(p)-1] = word
+}
+
+// Chain contains a map ("chain") of prefixes to a list of suffixes.
+// A prefix is a string of prefixLen words joined with spaces.
+// A suffix is a single word. A prefix can have multiple suffixes.
+type Chain struct {
+ chain map[string][]string
+ prefixLen int
+}
+
+// NewChain returns a new Chain with prefixes of prefixLen words.
+func NewChain(prefixLen int) *Chain {
+ return &Chain{make(map[string][]string), prefixLen}
+}
+
+// Build reads text from the provided Reader and
+// parses it into prefixes and suffixes that are stored in Chain.
+func (c *Chain) Build(r io.Reader) {
+ br := bufio.NewReader(r)
+ p := make(Prefix, c.prefixLen)
+ for {
+ var s string
+ if _, err := fmt.Fscan(br, &s); err != nil {
+ break
+ }
+ key := p.String()
+ c.chain[key] = append(c.chain[key], s)
+ p.Shift(s)
+ }
+}
+
+// Generate returns a string of at most n words generated from Chain.
+func (c *Chain) Generate(n int) string {
+ p := make(Prefix, c.prefixLen)
+ var words []string
+ for i := 0; i < n; i++ {
+ choices := c.chain[p.String()]
+ if len(choices) == 0 {
+ break
+ }
+ next := choices[rand.Intn(len(choices))]
+ words = append(words, next)
+ p.Shift(next)
+ }
+ return strings.Join(words, " ")
+}
+
+func main() {
+ // Register command-line flags.
+ numWords := flag.Int("words", 100, "maximum number of words to print")
+ prefixLen := flag.Int("prefix", 2, "prefix length in words")
+
+ flag.Parse() // Parse command-line flags.
+ rand.Seed(time.Nanoseconds()) // Seed the random number generator.
+
+ c := NewChain(*prefixLen) // Initialize a new Chain.
+ c.Build(os.Stdin) // Build chains from standard input.
+ text := c.Generate(*numWords) // Generate text.
+ fmt.Println(text) // Write text to standard output.
+}
diff --git a/doc/codewalk/markov.xml b/doc/codewalk/markov.xml
new file mode 100644
index 000000000..a89b4d0ce
--- /dev/null
+++ b/doc/codewalk/markov.xml
@@ -0,0 +1,308 @@
+<!--
+Copyright 2011 The Go Authors. All rights reserved.
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file.
+-->
+
+<codewalk title="Generating arbitrary text: a Markov chain algorithm">
+
+<step title="Introduction" src="doc/codewalk/markov.go:/Generating/,/line\./">
+ This codewalk describes a program that generates random text using
+ a Markov chain algorithm. The package comment describes the algorithm
+ and the operation of the program. Please read it before continuing.
+</step>
+
+<step title="Modeling Markov chains" src="doc/codewalk/markov.go:/ chain/">
+ A chain consists of a prefix and a suffix. Each prefix is a set
+ number of words, while a suffix is a single word.
+ A prefix can have an arbitrary number of suffixes.
+ To model this data, we use a <code>map[string][]string</code>.
+ Each map key is a prefix (a <code>string</code>) and its values are
+ lists of suffixes (a slice of strings, <code>[]string</code>).
+ <br/><br/>
+ Here is the example table from the package comment
+ as modeled by this data structure:
+ <pre>
+map[string][]string{
+ " ": {"I"},
+ " I": {"am"},
+ "I am": {"a", "not"},
+ "a free": {"man!"},
+ "am a": {"free"},
+ "am not": {"a"},
+ "a number!": {"I"},
+ "number! I": {"am"},
+ "not a": {"number!"},
+}</pre>
+ While each prefix consists of multiple words, we
+ store prefixes in the map as a single <code>string</code>.
+ It would seem more natural to store the prefix as a
+ <code>[]string</code>, but we can't do this with a map because the
+ key type of a map must implement equality (and slices do not).
+ <br/><br/>
+ Therefore, in most of our code we will model prefixes as a
+ <code>[]string</code> and join the strings together with a space
+ to generate the map key:
+ <pre>
+Prefix Map key
+
+[]string{"", ""} " "
+[]string{"", "I"} " I"
+[]string{"I", "am"} "I am"
+</pre>
+</step>
+
+<step title="The Chain struct" src="doc/codewalk/markov.go:/type Chain/,/}/">
+ The complete state of the chain table consists of the table itself and
+ the word length of the prefixes. The <code>Chain</code> struct stores
+ this data.
+</step>
+
+<step title="The NewChain constructor function" src="doc/codewalk/markov.go:/func New/,/}/">
+ The <code>Chain</code> struct has two unexported fields (those that
+ do not begin with an upper case character), and so we write a
+ <code>NewChain</code> constructor function that initializes the
+ <code>chain</code> map with <code>make</code> and sets the
+ <code>prefixLen</code> field.
+ <br/><br/>
+ This is constructor function is not strictly necessary as this entire
+ program is within a single package (<code>main</code>) and therefore
+ there is little practical difference between exported and unexported
+ fields. We could just as easily write out the contents of this function
+ when we want to construct a new Chain.
+ But using these unexported fields is good practice; it clearly denotes
+ that only methods of Chain and its constructor function should access
+ those fields. Also, structuring <code>Chain</code> like this means we
+ could easily move it into its own package at some later date.
+</step>
+
+<step title="The Prefix type" src="doc/codewalk/markov.go:/type Prefix/">
+ Since we'll be working with prefixes often, we define a
+ <code>Prefix</code> type with the concrete type <code>[]string</code>.
+ Defining a named type clearly allows us to be explicit when we are
+ working with a prefix instead of just a <code>[]string</code>.
+ Also, in Go we can define methods on any named type (not just structs),
+ so we can add methods that operate on <code>Prefix</code> if we need to.
+</step>
+
+<step title="The String method" src="doc/codewalk/markov.go:/func[^\n]+String/,/}/">
+ The first method we define on <code>Prefix</code> is
+ <code>String</code>. It returns a <code>string</code> representation
+ of a <code>Prefix</code> by joining the slice elements together with
+ spaces. We will use this method to generate keys when working with
+ the chain map.
+</step>
+
+<step title="Building the chain" src="doc/codewalk/markov.go:/func[^\n]+Build/,/\n}/">
+ The <code>Build</code> method reads text from an <code>io.Reader</code>
+ and parses it into prefixes and suffixes that are stored in the
+ <code>Chain</code>.
+ <br/><br/>
+ The <code><a href="/pkg/io/#Reader">io.Reader</a></code> is an
+ interface type that is widely used by the standard library and
+ other Go code. Our code uses the
+ <code><a href="/pkg/fmt/#Fscan">fmt.Fscan</a></code> function, which
+ reads space-separated values from an <code>io.Reader</code>.
+ <br/><br/>
+ The <code>Build</code> method returns once the <code>Reader</code>'s
+ <code>Read</code> method returns <code>os.EOF</code> (end of file)
+ or some other read error occurs.
+</step>
+
+<step title="Buffering the input" src="doc/codewalk/markov.go:/bufio\.NewReader/">
+ This function does many small reads, which can be inefficient for some
+ <code>Readers</code>. For efficiency we wrap the provided
+ <code>io.Reader</code> with
+ <code><a href="/pkg/bufio/">bufio.NewReader</a></code> to create a
+ new <code>io.Reader</code> that provides buffering.
+</step>
+
+<step title="The Prefix variable" src="doc/codewalk/markov.go:/make\(Prefix/">
+ At the top of the function we make a <code>Prefix</code> slice
+ <code>p</code> using the <code>Chain</code>'s <code>prefixLen</code>
+ field as its length.
+ We'll use this variable to hold the current prefix and mutate it with
+ each new word we encounter.
+</step>
+
+<step title="Scanning words" src="doc/codewalk/markov.go:/var s string/,/\n }/">
+ In our loop we read words from the <code>Reader</code> into a
+ <code>string</code> variable <code>s</code> using
+ <code>fmt.Fscan</code>. Since <code>Fscan</code> uses space to
+ separate each input value, each call will yield just one word
+ (including punctuation), which is exactly what we need.
+ <br/><br/>
+ <code>Fscan</code> returns an error if it encounters a read error
+ (<code>os.EOF</code>, for example) or if it can't scan the requested
+ value (in our case, a single string). In either case we just want to
+ stop scanning, so we <code>break</code> out of the loop.
+</step>
+
+<step title="Adding a prefix and suffix to the chain" src="doc/codewalk/markov.go:/ key/,/key\], s\)">
+ The word stored in <code>s</code> is a new suffix. We add the new
+ prefix/suffix combination to the <code>chain</code> map by computing
+ the map key with <code>p.String</code> and appending the suffix
+ to the slice stored under that key.
+ <br/><br/>
+ The built-in <code>append</code> function appends elements to a slice
+ and allocates new storage when necessary. When the provided slice is
+ <code>nil</code>, <code>append</code> allocates a new slice.
+ This behavior conveniently ties in with the semantics of our map:
+ retrieving an unset key returns the zero value of the value type and
+ the zero value of <code>[]string</code> is <code>nil</code>.
+ When our program encounters a new prefix (yielding a <code>nil</code>
+ value in the map) <code>append</code> will allocate a new slice.
+ <br/><br/>
+ For more information about the <code>append</code> function and slices
+ in general see the
+ <a href="http://blog.golang.org/2011/01/go-slices-usage-and-internals.html">Slices: usage and internals</a> article.
+</step>
+
+<step title="Pushing the suffix onto the prefix" src="doc/codewalk/markov.go:/p\.Shift/">
+ Before reading the next word our algorithm requires us to drop the
+ first word from the prefix and push the current suffix onto the prefix.
+ <br/><br/>
+ When in this state
+ <pre>
+p == Prefix{"I", "am"}
+s == "not" </pre>
+ the new value for <code>p</code> would be
+ <pre>
+p == Prefix{"am", "not"}</pre>
+ This operation is also required during text generation so we put
+ the code to perform this mutation of the slice inside a method on
+ <code>Prefix</code> named <code>Shift</code>.
+</step>
+
+<step title="The Shift method" src="doc/codewalk/markov.go:/func[^\n]+Shift/,/\n}/">
+ The <code>Shift</code> method uses the built-in <code>copy</code>
+ function to copy the last len(p)-1 elements of <code>p</code> to
+ the start of the slice, effectively moving the elements
+ one index to the left (if you consider zero as the leftmost index).
+ <pre>
+p := Prefix{"I", "am"}
+copy(p, p[:1])
+// p == Prefix{"am", "am"}</pre>
+ We then assign the provided <code>word</code> to the last index
+ of the slice:
+ <pre>
+// suffix == "not"
+p[len(p)-1] = suffix
+// p == Prefix{"am", "not"}</pre>
+</step>
+
+<step title="Generating text" src="doc/codewalk/markov.go:/func[^\n]+Generate/,/\n}/">
+ The <code>Generate</code> method is similar to <code>Build</code>
+ except that instead of reading words from a <code>Reader</code>
+ and storing them in a map, it reads words from the map and
+ appends them to a slice (<code>words</code>).
+ <br/><br/>
+ <code>Generate</code> uses a conditional for loop to generate
+ up to <code>n</code> words.
+</step>
+
+<step title="Getting potential suffixes" src="doc/codewalk/markov.go:/choices/,/}\n/">
+ At each iteration of the loop we retrieve a list of potential suffixes
+ for the current prefix. We access the <code>chain</code> map at key
+ <code>p.String()</code> and assign its contents to <code>choices</code>.
+ <br/><br/>
+ If <code>len(choices)</code> is zero we break out of the loop as there
+ are no potential suffixes for that prefix.
+ This test also works if the key isn't present in the map at all:
+ in that case, <code>choices</code> will be <code>nil</code> and the
+ length of a <code>nil</code> slice is zero.
+</step>
+
+<step title="Choosing a suffix at random" src="doc/codewalk/markov.go:/next := choices/,/Shift/">
+ To choose a suffix we use the
+ <code><a href="/pkg/rand/#Intn">rand.Intn</a></code> function.
+ It returns a random integer up to (but not including) the provided
+ value. Passing in <code>len(choices)</code> gives us a random index
+ into the full length of the list.
+ <br/><br/>
+ We use that index to pick our new suffix, assign it to
+ <code>next</code> and append it to the <code>words</code> slice.
+ <br/><br/>
+ Next, we <code>Shift</code> the new suffix onto the prefix just as
+ we did in the <code>Build</code> method.
+</step>
+
+<step title="Returning the generated text" src="doc/codewalk/markov.go:/Join\(words/">
+ Before returning the generated text as a string, we use the
+ <code>strings.Join</code> function to join the elements of
+ the <code>words</code> slice together, separated by spaces.
+</step>
+
+<step title="Command-line flags" src="doc/codewalk/markov.go:/Register command-line flags/,/prefixLen/">
+ To make it easy to tweak the prefix and generated text lengths we
+ use the <code><a href="/pkg/flag/">flag</a></code> package to parse
+ command-line flags.
+ <br/><br/>
+ These calls to <code>flag.Int</code> register new flags with the
+ <code>flag</code> package. The arguments to <code>Int</code> are the
+ flag name, its default value, and a description. The <code>Int</code>
+ function returns a pointer to an integer that will contain the
+ user-supplied value (or the default value if the flag was omitted on
+ the command-line).
+</step>
+
+<step title="Program set up" src="doc/codewalk/markov.go:/flag.Parse/,/rand.Seed/">
+ The <code>main</code> function begins by parsing the command-line
+ flags with <code>flag.Parse</code> and seeding the <code>rand</code>
+ package's random number generator with the current time.
+ <br/><br/>
+ If the command-line flags provided by the user are invalid the
+ <code>flag.Parse</code> function will print an informative usage
+ message and terminate the program.
+</step>
+
+<step title="Creating and building a new Chain" src="doc/codewalk/markov.go:/c := NewChain/,/c\.Build/">
+ To create the new <code>Chain</code> we call <code>NewChain</code>
+ with the value of the <code>prefix</code> flag.
+ <br/><br/>
+ To build the chain we call <code>Build</code> with
+ <code>os.Stdin</code> (which implements <code>io.Reader</code>) so
+ that it will read its input from standard input.
+</step>
+
+<step title="Generating and printing text" src="doc/codewalk/markov.go:/c\.Generate/,/fmt.Println/">
+ Finally, to generate text we call <code>Generate</code> with
+ the value of the <code>words</code> flag and assigning the result
+ to the variable <code>text</code>.
+ <br/><br/>
+ Then we call <code>fmt.Println</code> to write the text to standard
+ output, followed by a carriage return.
+</step>
+
+<step title="Using this program" src="doc/codewalk/markov.go">
+ To use this program, first compile and link it.
+ If you are using <code>6g</code> as your compiler, the command
+ would look something like this:
+ <pre>
+$ 6g markov.go &amp;&amp; 6l -o markov markov.6</pre>
+ And then execute it while piping in some input text:
+ <pre>
+$ echo "a man a plan a canal panama" | ./markov -prefix=1
+a plan a man a plan a canal panama
+ </pre>
+ Here's a transcript of generating some text using the Go distribution's
+ README file as source material:
+ <pre>
+$ ./markov -words=10 &lt $GOROOT/go/README
+This is the source code repository for the Go source
+$ ./markov -prefix=1 -words=10 &lt $GOROOT/go/README
+This is the go directory (the one containing this README).
+$ ./markov -prefix=1 -words=10 &lt $GOROOT/go/README
+This is the variable if you have just untarred a</pre>
+</step>
+
+<step title="An exercise for the reader" src="doc/codewalk/markov.go">
+ The <code>Generate</code> function does a lot of allocations when it
+ builds the <code>words</code> slice. As an exercise, modify it to
+ take an <code>io.Writer</code> to which it incrementally writes the
+ generated text with <code>Fprint</code>.
+ Aside from being more efficient this makes <code>Generate</code>
+ more symmetrical to <code>Build</code>.
+</step>
+
+</codewalk>
diff --git a/doc/codewalk/pig.go b/doc/codewalk/pig.go
new file mode 100644
index 000000000..9e415f589
--- /dev/null
+++ b/doc/codewalk/pig.go
@@ -0,0 +1,124 @@
+// Copyright 2011 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+ "fmt"
+ "rand"
+)
+
+const (
+ win = 100 // The winning score in a game of Pig
+ gamesPerSeries = 10 // The number of games per series to simulate
+)
+
+// A score includes scores accumulated in previous turns for each player,
+// as well as the points scored by the current player in this turn.
+type score struct {
+ player, opponent, thisTurn int
+}
+
+// An action transitions stochastically to a resulting score.
+type action func(current score) (result score, turnIsOver bool)
+
+// roll returns the (result, turnIsOver) outcome of simulating a die roll.
+// If the roll value is 1, then thisTurn score is abandoned, and the players'
+// roles swap. Otherwise, the roll value is added to thisTurn.
+func roll(s score) (score, bool) {
+ outcome := rand.Intn(6) + 1 // A random int in [1, 6]
+ if outcome == 1 {
+ return score{s.opponent, s.player, 0}, true
+ }
+ return score{s.player, s.opponent, outcome + s.thisTurn}, false
+}
+
+// stay returns the (result, turnIsOver) outcome of staying.
+// thisTurn score is added to the player's score, and the players' roles swap.
+func stay(s score) (score, bool) {
+ return score{s.opponent, s.player + s.thisTurn, 0}, true
+}
+
+// A strategy chooses an action for any given score.
+type strategy func(score) action
+
+// stayAtK returns a strategy that rolls until thisTurn is at least k, then stays.
+func stayAtK(k int) strategy {
+ return func(s score) action {
+ if s.thisTurn >= k {
+ return stay
+ }
+ return roll
+ }
+}
+
+// play simulates a Pig game and returns the winner (0 or 1).
+func play(strategy0, strategy1 strategy) int {
+ strategies := []strategy{strategy0, strategy1}
+ var s score
+ var turnIsOver bool
+ currentPlayer := rand.Intn(2) // Randomly decide who plays first
+ for s.player+s.thisTurn < win {
+ action := strategies[currentPlayer](s)
+ if action != roll && action != stay {
+ panic(fmt.Sprintf("Player %d is cheating", currentPlayer))
+ }
+ s, turnIsOver = action(s)
+ if turnIsOver {
+ currentPlayer = (currentPlayer + 1) % 2
+ }
+ }
+ return currentPlayer
+}
+
+// roundRobin simulates a series of games between every pair of strategies.
+func roundRobin(strategies []strategy) ([]int, int) {
+ wins := make([]int, len(strategies))
+ for i := 0; i < len(strategies); i++ {
+ for j := i + 1; j < len(strategies); j++ {
+ for k := 0; k < gamesPerSeries; k++ {
+ winner := play(strategies[i], strategies[j])
+ if winner == 0 {
+ wins[i]++
+ } else {
+ wins[j]++
+ }
+ }
+ }
+ }
+ gamesPerStrategy := gamesPerSeries * (len(strategies) - 1) // no self play
+ return wins, gamesPerStrategy
+}
+
+// ratioString takes a list of integer values and returns a string that lists
+// each value and its percentage of the sum of all values.
+// e.g., ratios(1, 2, 3) = "1/6 (16.7%), 2/6 (33.3%), 3/6 (50.0%)"
+func ratioString(vals ...int) string {
+ total := 0
+ for _, val := range vals {
+ total += val
+ }
+ s := ""
+ for _, val := range vals {
+ if s != "" {
+ s += ", "
+ }
+ pct := 100 * float64(val) / float64(total)
+ s += fmt.Sprintf("%d/%d (%0.1f%%)", val, total, pct)
+ }
+ return s
+}
+
+func main() {
+ strategies := make([]strategy, win)
+ for k := range strategies {
+ strategies[k] = stayAtK(k + 1)
+ }
+ wins, games := roundRobin(strategies)
+
+ for k := range strategies {
+ fmt.Printf("Wins, losses staying at k =% 4d: %s\n",
+ k+1, ratioString(wins[k], games-wins[k]))
+ }
+}
diff --git a/doc/codewalk/popout.png b/doc/codewalk/popout.png
new file mode 100644
index 000000000..9c0c23638
--- /dev/null
+++ b/doc/codewalk/popout.png
Binary files differ
diff --git a/doc/codewalk/sharemem.xml b/doc/codewalk/sharemem.xml
new file mode 100644
index 000000000..1a669f7b5
--- /dev/null
+++ b/doc/codewalk/sharemem.xml
@@ -0,0 +1,181 @@
+<codewalk title="Share Memory By Communicating">
+
+<step title="Introduction" src="doc/codewalk/urlpoll.go">
+Go's approach to concurrency differs from the traditional use of
+threads and shared memory. Philosophically, it can be summarized:
+<br/><br/>
+<i>Don't communicate by sharing memory; share memory by communicating.</i>
+<br/><br/>
+Channels allow you to pass references to data structures between goroutines.
+If you consider this as passing around ownership of the data (the ability to
+read and write it), they become a powerful and expressive synchronization
+mechanism.
+<br/><br/>
+In this codewalk we will look at a simple program that polls a list of
+URLs, checking their HTTP response codes and periodically printing their state.
+</step>
+
+<step title="State type" src="doc/codewalk/urlpoll.go:/State/,/}/">
+The State type represents the state of a URL.
+<br/><br/>
+The Pollers send State values to the StateMonitor,
+which maintains a map of the current state of each URL.
+</step>
+
+<step title="Resource type" src="doc/codewalk/urlpoll.go:/Resource/,/}/">
+A Resource represents the state of a URL to be polled: the URL itself
+and the number of errors encountered since the last successful poll.
+<br/><br/>
+When the program starts, it allocates one Resource for each URL.
+The main goroutine and the Poller goroutines send the Resources to
+each other on channels.
+</step>
+
+<step title="Poller function" src="doc/codewalk/urlpoll.go:/func Poller/,/\n}/">
+Each Poller receives Resource pointers from an input channel.
+In this program, the convention is that sending a Resource pointer on
+a channel passes ownership of the underlying data from the sender
+to the receiver. Because of this convention, we know that
+no two goroutines will access this Resource at the same time.
+This means we don't have to worry about locking to prevent concurrent
+access to these data structures.
+<br/><br/>
+The Poller processes the Resource by calling its Poll method.
+<br/><br/>
+It sends a State value to the status channel, to inform the StateMonitor
+of the result of the Poll.
+<br/><br/>
+Finally, it sends the Resource pointer to the out channel. This can be
+interpreted as the Poller saying &quot;I'm done with this Resource&quot; and
+returning ownership of it to the main goroutine.
+<br/><br/>
+Several goroutines run Pollers, processing Resources in parallel.
+</step>
+
+<step title="The Poll method" src="doc/codewalk/urlpoll.go:/Poll executes/,/\n}/">
+The Poll method (of the Resource type) performs an HTTP HEAD request
+for the Resource's URL and returns the HTTP response's status code.
+If an error occurs, Poll logs the message to standard error and returns the
+error string instead.
+</step>
+
+<step title="main function" src="doc/codewalk/urlpoll.go:/func main/,/\n}/">
+The main function starts the Poller and StateMonitor goroutines
+and then loops passing completed Resources back to the pending
+channel after appropriate delays.
+</step>
+
+<step title="Creating channels" src="doc/codewalk/urlpoll.go:/create our/,/complete/">
+First, main makes two channels of *Resource, pending and complete.
+<br/><br/>
+Inside main, a new goroutine sends one Resource per URL to pending
+and the main goroutine receives completed Resources from complete.
+<br/><br/>
+The pending and complete channels are passed to each of the Poller
+goroutines, within which they are known as in and out.
+</step>
+
+<step title="Initializing StateMonitor" src="doc/codewalk/urlpoll.go:/launch the StateMonitor/,/statusInterval/">
+StateMonitor will initialize and launch a goroutine that stores the state
+of each Resource. We will look at this function in detail later.
+<br/><br/>
+For now, the important thing to note is that it returns a channel of State,
+which is saved as status and passed to the Poller goroutines.
+</step>
+
+<step title="Launching Poller goroutines" src="doc/codewalk/urlpoll.go:/launch some Poller/,/}/">
+Now that it has the necessary channels, main launches a number of
+Poller goroutines, passing the channels as arguments.
+The channels provide the means of communication between the main, Poller, and
+StateMonitor goroutines.
+</step>
+
+<step title="Send Resources to pending" src="doc/codewalk/urlpoll.go:/send some Resources/,/}\(\)/">
+To add the initial work to the system, main starts a new goroutine
+that allocates and sends one Resource per URL to pending.
+<br/><br/>
+The new goroutine is necessary because unbuffered channel sends and
+receives are synchronous. That means these channel sends will block until
+the Pollers are ready to read from pending.
+<br/><br/>
+Were these sends performed in the main goroutine with fewer Pollers than
+channel sends, the program would reach a deadlock situation, because
+main would not yet be receiving from complete.
+<br/><br/>
+Exercise for the reader: modify this part of the program to read a list of
+URLs from a file. (You may want to move this goroutine into its own
+named function.)
+</step>
+
+<step title="Main Event Loop" src="doc/codewalk/urlpoll.go:/range complete/,/\n }/">
+When a Poller is done with a Resource, it sends it on the complete channel.
+This loop receives those Resource pointers from complete.
+For each received Resource, it starts a new goroutine calling
+the Resource's Sleep method. Using a new goroutine for each
+ensures that the sleeps can happen in parallel.
+<br/><br/>
+Note that any single Resource pointer may only be sent on either pending or
+complete at any one time. This ensures that a Resource is either being
+handled by a Poller goroutine or sleeping, but never both simultaneously.
+In this way, we share our Resource data by communicating.
+</step>
+
+<step title="The Sleep method" src="doc/codewalk/urlpoll.go:/Sleep/,/\n}/">
+Sleep calls time.Sleep to pause before sending the Resource to done.
+The pause will either be of a fixed length (pollInterval) plus an
+additional delay proportional to the number of sequential errors (r.errCount).
+<br/><br/>
+This is an example of a typical Go idiom: a function intended to run inside
+a goroutine takes a channel, upon which it sends its return value
+(or other indication of completed state).
+</step>
+
+<step title="StateMonitor" src="doc/codewalk/urlpoll.go:/StateMonitor/,/\n}/">
+The StateMonitor receives State values on a channel and periodically
+outputs the state of all Resources being polled by the program.
+</step>
+
+<step title="The updates channel" src="doc/codewalk/urlpoll.go:/updates :=/">
+The variable updates is a channel of State, on which the Poller goroutines
+send State values.
+<br/><br/>
+This channel is returned by the function.
+</step>
+
+<step title="The urlStatus map" src="doc/codewalk/urlpoll.go:/urlStatus/">
+The variable urlStatus is a map of URLs to their most recent status.
+</step>
+
+<step title="The Ticker object" src="doc/codewalk/urlpoll.go:/ticker/">
+A time.Ticker is an object that repeatedly sends a value on a channel at a
+specified interval.
+<br/><br/>
+In this case, ticker triggers the printing of the current state to
+standard output every updateInterval nanoseconds.
+</step>
+
+<step title="The StateMonitor goroutine" src="doc/codewalk/urlpoll.go:/go func/,/}\(\)/">
+StateMonitor will loop forever, selecting on two channels:
+ticker.C and update. The select statement blocks until one of its
+communications is ready to proceed.
+<br/><br/>
+When StateMonitor receives a tick from ticker.C, it calls logState to
+print the current state. When it receives a State update from updates,
+it records the new status in the urlStatus map.
+<br/><br/>
+Notice that this goroutine owns the urlStatus data structure,
+ensuring that it can only be accessed sequentially.
+This prevents memory corruption issues that might arise from parallel reads
+and/or writes to a shared map.
+</step>
+
+<step title="Conclusion" src="doc/codewalk/urlpoll.go">
+In this codewalk we have explored a simple example of using Go's concurrency
+primitives to share memory through commmunication.
+<br/><br/>
+This should provide a starting point from which to explore the ways in which
+goroutines and channels can be used to write expressive and concise concurrent
+programs.
+</step>
+
+</codewalk>
diff --git a/doc/codewalk/urlpoll.go b/doc/codewalk/urlpoll.go
new file mode 100644
index 000000000..b51be9502
--- /dev/null
+++ b/doc/codewalk/urlpoll.go
@@ -0,0 +1,117 @@
+// Copyright 2010 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+ "http"
+ "log"
+ "time"
+)
+
+const (
+ numPollers = 2 // number of Poller goroutines to launch
+ second = 1e9 // one second is 1e9 nanoseconds
+ pollInterval = 60 * second // how often to poll each URL
+ statusInterval = 10 * second // how often to log status to stdout
+ errTimeout = 10 * second // back-off timeout on error
+)
+
+var urls = []string{
+ "http://www.google.com/",
+ "http://golang.org/",
+ "http://blog.golang.org/",
+}
+
+// State represents the last-known state of a URL.
+type State struct {
+ url string
+ status string
+}
+
+// StateMonitor maintains a map that stores the state of the URLs being
+// polled, and prints the current state every updateInterval nanoseconds.
+// It returns a chan State to which resource state should be sent.
+func StateMonitor(updateInterval int64) chan<- State {
+ updates := make(chan State)
+ urlStatus := make(map[string]string)
+ ticker := time.NewTicker(updateInterval)
+ go func() {
+ for {
+ select {
+ case <-ticker.C:
+ logState(urlStatus)
+ case s := <-updates:
+ urlStatus[s.url] = s.status
+ }
+ }
+ }()
+ return updates
+}
+
+// logState prints a state map.
+func logState(s map[string]string) {
+ log.Println("Current state:")
+ for k, v := range s {
+ log.Printf(" %s %s", k, v)
+ }
+}
+
+// Resource represents an HTTP URL to be polled by this program.
+type Resource struct {
+ url string
+ errCount int64
+}
+
+// Poll executes an HTTP HEAD request for url
+// and returns the HTTP status string or an error string.
+func (r *Resource) Poll() string {
+ resp, err := http.Head(r.url)
+ if err != nil {
+ log.Println("Error", r.url, err)
+ r.errCount++
+ return err.String()
+ }
+ r.errCount = 0
+ return resp.Status
+}
+
+// Sleep sleeps for an appropriate interval (dependant on error state)
+// before sending the Resource to done.
+func (r *Resource) Sleep(done chan *Resource) {
+ time.Sleep(pollInterval + errTimeout*r.errCount)
+ done <- r
+}
+
+func Poller(in <-chan *Resource, out chan<- *Resource, status chan<- State) {
+ for r := range in {
+ s := r.Poll()
+ status <- State{r.url, s}
+ out <- r
+ }
+}
+
+func main() {
+ // create our input and output channels
+ pending, complete := make(chan *Resource), make(chan *Resource)
+
+ // launch the StateMonitor
+ status := StateMonitor(statusInterval)
+
+ // launch some Poller goroutines
+ for i := 0; i < numPollers; i++ {
+ go Poller(pending, complete, status)
+ }
+
+ // send some Resources to the pending queue
+ go func() {
+ for _, url := range urls {
+ pending <- &Resource{url: url}
+ }
+ }()
+
+ for r := range complete {
+ go r.Sleep(pending)
+ }
+}