diff options
Diffstat (limited to 'doc/codewalk')
| -rw-r--r-- | doc/codewalk/codewalk.css | 234 | ||||
| -rw-r--r-- | doc/codewalk/codewalk.js | 305 | ||||
| -rw-r--r-- | doc/codewalk/codewalk.xml | 124 | ||||
| -rw-r--r-- | doc/codewalk/functions.xml | 115 | ||||
| -rw-r--r-- | doc/codewalk/markov.go | 130 | ||||
| -rw-r--r-- | doc/codewalk/markov.xml | 308 | ||||
| -rw-r--r-- | doc/codewalk/pig.go | 124 | ||||
| -rw-r--r-- | doc/codewalk/popout.png | bin | 0 -> 213 bytes | |||
| -rw-r--r-- | doc/codewalk/sharemem.xml | 181 | ||||
| -rw-r--r-- | doc/codewalk/urlpoll.go | 117 |
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><codewalk></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:/<step/,/step>/"> + Each step in the codewalk is a <code><step></code> element + nested inside the main <code><codewalk></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 “Title” 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>/<step/,/step>/</code> looks for the first instance of + <code><step</code> in the file, and then starting after that point, + looks for the first instance of <code>step></code>. + (Click on the “Steps” step above to see the highlight in action.) + Note that the <code><</code> and <code>></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>/"> + 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 && 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 < $GOROOT/go/README +This is the source code repository for the Go source +$ ./markov -prefix=1 -words=10 < $GOROOT/go/README +This is the go directory (the one containing this README). +$ ./markov -prefix=1 -words=10 < $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 Binary files differnew file mode 100644 index 000000000..9c0c23638 --- /dev/null +++ b/doc/codewalk/popout.png 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 "I'm done with this Resource" 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) + } +} |
