Slipwave Javascript

/***\n!ccTiddly config/marco\n!!!Disclaimer and warning\nThis tiddler is specially for ccTiddly. Please do not edit or save otherwise it may not work properly (unless you know what you are doing). If you happen to save it, and it didn't work, just delete the tiddler and the original config tiddler would reappear.\n***/\n\n/***\n!!!Changing the default options\n***/\n/*{{{*/\nconfig.options.chkHttpReadOnly = false; //make it HTTP writable by default\nconfig.options.chkSaveBackups = false; //disable save backup\nconfig.options.chkAutoSave = false; //disable autosave\n/*}}}*/\n\n/***\n!!!Put SiteTitle to webpage title\n***/\n/*{{{*/\n//window.title = convertUnicodeToUTF8((wikifyPlain("SiteTitle") + " - " + wikifyPlain("SiteSubtitle")).htmlEncode());\n/*}}}*/

\n/***\n!!!Option panel\nchange options panel to remove username\n***/\n//{{{\nconfig.shadowTiddlers.OptionsPanel ="<<option chkSaveBackups>> SaveBackups\sn<<option chkAutoSave>> AutoSave\sn<<option chkRegExpSearch>> RegExpSearch\sn<<option chkCaseSensitiveSearch>> CaseSensitiveSearch\sn<<option chkAnimate>> EnableAnimations\sn\snSee AdvancedOptions";\n//}}}\n\n/***\n!!!SideBarOption panel\nchange SideBarOption panel to add login panel\n***/\n//{{{\nconfig.shadowTiddlers.SideBarOptions="<<search>><<closeAll>><<permaview>><<newTiddler>><<newJournal 'DD MMM YYYY'>><<saveChanges>><<tiddler 'LoginPanel'>><<slider chkSliderOptionsPanel OptionsPanel 'options »' 'Change TiddlyWiki advanced options'>>";\n//}}}\n\n/***\n!!!Page template\n***/\n/*{{{*/\nconfig.shadowTiddlers.PageTemplate = "<div class='header' macro='gradient vert #18f #04b'>\sn<div class='headerShadow'>\sn<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span> \sn<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>\sn</div>\sn<div class='headerForeground'>\sn<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span> \sn<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>\sn</div>\sn</div>\sn<div id='mainMenu' refresh='content' tiddler='MainMenu'></div>\sn<div id='sidebar'>\sn<div id='sidebarOptions' refresh='content' tiddler='SideBarOptions'></div>\sn<div id='sidebarTabs' refresh='content' force='true' tiddler='SideBarTabs'></div>\sn<div id='sidebarCopyright' refresh='content' tiddler='Copyright'></div>\sn</div>\sn<div id='displayArea'>\sn<div id='messageArea'></div>\sn<div id='tiddlerDisplay'></div>\sn</div>";\n/*}}}*/

\n/***\n!!!Add password field to options\n***/\n/*{{{*/\n// time (in minutes, from now) for password to stay in cookie [0= default i.e. year 2038]\nconfig.macros.option.passwordTime = 0;\n//password variable\nconfig.options.pasSecretCode = "";\n/*}}}*/\n\n/***\n!!!Copyright panel\n***/\n/*{{{*/\nconfig.shadowTiddlers.Copyright = "powered by [[TiddlyWiki|http://www.tiddlywiki.com/]] ver. <<version>> and [[ccTiddly 0.5.5|http://cctiddly.sourceforge.net]]\sn[[stand alone|?standalone=1]]";\n/*}}}*/\n\n/***\n!!!Login panel\n***/\n//{{{\nconfig.shadowTiddlers.LoginPanel ="Username:\sn<<option txtUserName>>\snPassword:\sn<<option pasSecretCode>>\snWelcome annoymous\sn[[login|\~/tiddly.php?]]";\n//}}}

\n/***\n!!!Add, save and load cookie\n***/\n/*{{{*/\nwindow.loadOptionsCookie = function()\n{\n var cookies = document.cookie.split(";");\n for(var c=0; c<cookies.length; c++)\n {\n var p = cookies[c].indexOf("=");\n if(p != -1)\n {\n var name = cookies[c].substr(0,p).trim();\n var value = cookies[c].substr(p+1).trim();\n switch(name.substr(0,3))\n {\n case "txt":\n config.options[name] = unescape(value);\n break;\n case "chk":\n config.options[name] = value == "true";\n break;\n case "pas":\n config.options[name] = unescape(value);\n break;\n }\n }\n }\n};\nwindow.saveOptionCookie = function(name)\n{\n var c = name + "=";\n var t = "; expires=Fri, 1 Jan 2038 12:00:00 UTC; path=/";\n\n switch(name.substr(0,3))\n {\n case "txt":\n c += escape(config.options[name].toString());\n break;\n case "chk":\n c += config.options[name] ? "true" : "false";\n break;\n case "pas":\n c += (escape(config.options[name].toString()));\nif( config.macros.option.passwordTime!=0 ) //if not using default time, calculate new time\n{\n var date = new Date();\n date.setTime(date.getTime()+config.macros.option.passwordTime*60000);\n t = "; expires="+date.toGMTString()+"; path=/";\n}\n break;\n }\n c += t;\n document.cookie = c;\n};\n/*}}}*/\n\n\n/***\n!!!Reload config file\nuncomment it to enable\nrequire variables defined by this time\n***/\n/*{{{*/\n//window.loadOptionsCookie();\n/*}}}*/

\n/***\n!Password field\nThese are use to create the password box under options. Please enable reload of option cookie at the bottom of this plugin if you would like it to display the md5 of your password.\n***/\n\n/***\n!!!Marco onChange and handler\n***/\n/*{{{*/\nconfig.macros.option.onChangeOption = function(e)\n{\n var opt = this.getAttribute("option");\n var elementType,valueField;\n if(opt)\n {\n switch(opt.substr(0,3))\n {\n case "txt":\n elementType = "input";\n valueField = "value";\n break;\n case "chk":\n elementType = "input";\n valueField = "checked";\n break;\n case "pas":\n elementType = "input";\n valueField = "value";\n break;\n }\nif( opt.substr(0,3) == "pas" )\n{\n config.options[opt] = hex_md5(this[valueField]);\n}else{\n config.options[opt] = this[valueField];\n}\n saveOptionCookie(opt);\n var nodes = document.getElementsByTagName(elementType);\n for(var t=0; t<nodes.length; t++)\n {\n var optNode = nodes[t].getAttribute("option");\n if(opt == optNode)\n nodes[t][valueField] = this[valueField];\n }\n }\n return(true);\n};\n\nconfig.macros.option.handler = function(place,macroName,params)\n{\n var opt = params[0];\n if(config.options[opt] == undefined)\n return;\n var c;\n switch(opt.substr(0,3))\n {\n case "txt":\n c = document.createElement("input");\n c.onkeyup = this.onChangeOption;\n c.setAttribute("option",opt);\n c.size = 15;\n place.appendChild(c);\n c.value = config.options[opt];\n break;\n case "chk":\n c = document.createElement("input");\n c.setAttribute("type","checkbox");\n c.onclick = this.onChangeOption;\n c.setAttribute("option",opt);\n place.appendChild(c);\n c.checked = config.options[opt];\n break;\n case "pas":\n c = document.createElement("input");\n c.setAttribute("type","password");\n c.onkeyup = this.onChangeOption;\n c.setAttribute("option",opt);\n c.size = 15;\n place.appendChild(c);\n c.value = config.options[opt];\n break;\n }\n};\n/*}}}*/\n

\n/***\n!! MD5 function\nobtained from http://pajhome.org.uk/crypt/md5\n***/\n//{{{\n//variable\nconfig.macros.option.passwordHexcase = 0; //hex output format. 0 - lowercase; 1 - uppercase\nconfig.macros.option.passwordChrsz = 8; //bits per input character. 8 - ASCII; 16 - Unicode\n\n//md5 function\nwindow.hex_md5 = function(s) { return binl2hex(core_md5(str2binl(s), s.length * config.macros.option.passwordChrsz));}\n\n//Calculate the MD5 of an array of little-endian words, and a bit length\nwindow.core_md5 = function (x, len)\n{\n /* append padding */\n x[len >> 5] |= 0x80 << ((len) % 32);\n x[(((len + 64) >>> 9) << 4) + 14] = len;\n\n var a = 1732584193;\n var b = -271733879;\n var c = -1732584194;\n var d = 271733878;\n\n for(var i = 0; i < x.length; i += 16)\n {\n var olda = a;\n var oldb = b;\n var oldc = c;\n var oldd = d;\n\n a = md5_ff(a, b, c, d, x[i+ 0], 7 , -680876936);\n d = md5_ff(d, a, b, c, x[i+ 1], 12, -389564586);\n c = md5_ff(c, d, a, b, x[i+ 2], 17, 606105819);\n b = md5_ff(b, c, d, a, x[i+ 3], 22, -1044525330);\n a = md5_ff(a, b, c, d, x[i+ 4], 7 , -176418897);\n d = md5_ff(d, a, b, c, x[i+ 5], 12, 1200080426);\n c = md5_ff(c, d, a, b, x[i+ 6], 17, -1473231341);\n b = md5_ff(b, c, d, a, x[i+ 7], 22, -45705983);\n a = md5_ff(a, b, c, d, x[i+ 8], 7 , 1770035416);\n d = md5_ff(d, a, b, c, x[i+ 9], 12, -1958414417);\n c = md5_ff(c, d, a, b, x[i+10], 17, -42063);\n b = md5_ff(b, c, d, a, x[i+11], 22, -1990404162);\n a = md5_ff(a, b, c, d, x[i+12], 7 , 1804603682);\n d = md5_ff(d, a, b, c, x[i+13], 12, -40341101);\n c = md5_ff(c, d, a, b, x[i+14], 17, -1502002290);\n b = md5_ff(b, c, d, a, x[i+15], 22, 1236535329);\n\n a = md5_gg(a, b, c, d, x[i+ 1], 5 , -165796510);\n d = md5_gg(d, a, b, c, x[i+ 6], 9 , -1069501632);\n c = md5_gg(c, d, a, b, x[i+11], 14, 643717713);\n b = md5_gg(b, c, d, a, x[i+ 0], 20, -373897302);\n a = md5_gg(a, b, c, d, x[i+ 5], 5 , -701558691);\n d = md5_gg(d, a, b, c, x[i+10], 9 , 38016083);\n c = md5_gg(c, d, a, b, x[i+15], 14, -660478335);\n b = md5_gg(b, c, d, a, x[i+ 4], 20, -405537848);\n a = md5_gg(a, b, c, d, x[i+ 9], 5 , 568446438);\n d = md5_gg(d, a, b, c, x[i+14], 9 , -1019803690);\n c = md5_gg(c, d, a, b, x[i+ 3], 14, -187363961);\n b = md5_gg(b, c, d, a, x[i+ 8], 20, 1163531501);\n a = md5_gg(a, b, c, d, x[i+13], 5 , -1444681467);\n d = md5_gg(d, a, b, c, x[i+ 2], 9 , -51403784);\n c = md5_gg(c, d, a, b, x[i+ 7], 14, 1735328473);\n b = md5_gg(b, c, d, a, x[i+12], 20, -1926607734);\n\n a = md5_hh(a, b, c, d, x[i+ 5], 4 , -378558);\n d = md5_hh(d, a, b, c, x[i+ 8], 11, -2022574463);\n c = md5_hh(c, d, a, b, x[i+11], 16, 1839030562);\n b = md5_hh(b, c, d, a, x[i+14], 23, -35309556);\n a = md5_hh(a, b, c, d, x[i+ 1], 4 , -1530992060);\n d = md5_hh(d, a, b, c, x[i+ 4], 11, 1272893353);\n c = md5_hh(c, d, a, b, x[i+ 7], 16, -155497632);\n b = md5_hh(b, c, d, a, x[i+10], 23, -1094730640);\n a = md5_hh(a, b, c, d, x[i+13], 4 , 681279174);\n d = md5_hh(d, a, b, c, x[i+ 0], 11, -358537222);\n c = md5_hh(c, d, a, b, x[i+ 3], 16, -722521979);\n b = md5_hh(b, c, d, a, x[i+ 6], 23, 76029189);\n a = md5_hh(a, b, c, d, x[i+ 9], 4 , -640364487);\n d = md5_hh(d, a, b, c, x[i+12], 11, -421815835);\n c = md5_hh(c, d, a, b, x[i+15], 16, 530742520);\n b = md5_hh(b, c, d, a, x[i+ 2], 23, -995338651);\n\n a = md5_ii(a, b, c, d, x[i+ 0], 6 , -198630844);\n d = md5_ii(d, a, b, c, x[i+ 7], 10, 1126891415);\n c = md5_ii(c, d, a, b, x[i+14], 15, -1416354905);\n b = md5_ii(b, c, d, a, x[i+ 5], 21, -57434055);\n a = md5_ii(a, b, c, d, x[i+12], 6 , 1700485571);\n d = md5_ii(d, a, b, c, x[i+ 3], 10, -1894986606);\n c = md5_ii(c, d, a, b, x[i+10], 15, -1051523);\n b = md5_ii(b, c, d, a, x[i+ 1], 21, -2054922799);\n a = md5_ii(a, b, c, d, x[i+ 8], 6 , 1873313359);\n d = md5_ii(d, a, b, c, x[i+15], 10, -30611744);\n c = md5_ii(c, d, a, b, x[i+ 6], 15, -1560198380);\n b = md5_ii(b, c, d, a, x[i+13], 21, 1309151649);\n a = md5_ii(a, b, c, d, x[i+ 4], 6 , -145523070);\n d = md5_ii(d, a, b, c, x[i+11], 10, -1120210379);\n c = md5_ii(c, d, a, b, x[i+ 2], 15, 718787259);\n b = md5_ii(b, c, d, a, x[i+ 9], 21, -343485551);\n\n a = safe_add(a, olda);\n b = safe_add(b, oldb);\n c = safe_add(c, oldc);\n d = safe_add(d, oldd);\n }\n return Array(a, b, c, d);\n\n}\n\n\n//These functions implement the four basic operations the algorithm uses.\nwindow.md5_cmn = function (q, a, b, x, s, t)\n{\n return safe_add(bit_rol(safe_add(safe_add(a, q), safe_add(x, t)), s),b);\n}\nwindow.md5_ff = function (a, b, c, d, x, s, t)\n{\n return md5_cmn((b & c) | ((~b) & d), a, b, x, s, t);\n}\nwindow.md5_gg = function (a, b, c, d, x, s, t)\n{\n return md5_cmn((b & d) | (c & (~d)), a, b, x, s, t);\n}\nwindow.md5_hh = function (a, b, c, d, x, s, t)\n{\n return md5_cmn(b ^ c ^ d, a, b, x, s, t);\n}\nwindow.md5_ii = function (a, b, c, d, x, s, t)\n{\n return md5_cmn(c ^ (b | (~d)), a, b, x, s, t);\n}\n\n//Add integers, wrapping at 2^32. This uses 16-bit operations internally\n//to work around bugs in some JS interpreters.\nwindow.safe_add = function (x, y)\n{\n var lsw = (x & 0xFFFF) + (y & 0xFFFF);\n var msw = (x >> 16) + (y >> 16) + (lsw >> 16);\n return (msw << 16) | (lsw & 0xFFFF);\n}\n\n//Bitwise rotate a 32-bit number to the left.\nwindow.bit_rol = function (num, cnt)\n{\n return (num << cnt) | (num >>> (32 - cnt));\n}\n\n\n//Convert a string to an array of little-endian words\n// If config.macros.option.passwordChrsz is ASCII, characters >255 have their hi-byte silently ignored.\nwindow.str2binl = function (str)\n{\n var bin = Array();\n var mask = (1 << config.macros.option.passwordChrsz) - 1;\n for(var i = 0; i < str.length * config.macros.option.passwordChrsz; i += config.macros.option.passwordChrsz)\n bin[i>>5] |= (str.charCodeAt(i / config.macros.option.passwordChrsz) & mask) << (i%32);\n return bin;\n}\n\n//Convert an array of little-endian words to a hex string.\nwindow.binl2hex = function (binarray)\n{\n var hex_tab = config.macros.option.passwordHexcase ? "0123456789ABCDEF" : "0123456789abcdef";\n var str = "";\n for(var i = 0; i < binarray.length * 4; i++)\n {\n str += hex_tab.charAt((binarray[i>>2] >> ((i%4)*8+4)) & 0xF) +\n hex_tab.charAt((binarray[i>>2] >> ((i%4)*8 )) & 0xF);\n }\n return str;\n}\n//}}}

\n/***\n!!!saveChanges\nused to generate RSS (and used as import in future version)\n***/\n/*{{{*/\nfunction saveChanges()\n{\n clearMessage();\n // Save Rss\n if(config.options.chkGenerateAnRssFeed)\n {\ndocument.forms.invisiForm.msg.value = "rss";\ndocument.forms.invisiForm.modifier.value = config.options.txtUserName;\ndocument.forms.invisiForm.body.value = generateRss();\ndocument.forms.invisiForm.submit();\ndisplayMessage("Rss generated and saved");\n }else{\n alert("This is only used for generating Rss. Changes were autosaved in ccTiddly");\n }\n}\n/*}}}*/

\n/***\n!!!saveTiddler\n***/\n//{{{\nTiddlyWiki.prototype.saveTiddler = function(title,newTitle,newBody,modifier,modified,tags)\n{\n var tiddler = this.fetchTiddler(title);\n var created;\n var omodified;\n if(tiddler)\n {\n created = tiddler.created; // preserve created date\nomodified = tiddler.modified; // get original modified date\n this.deleteTiddler(title);\n }\n else\n {\n tiddler = new Tiddler();\n created = modified;\n omodified = modified;\n }\n tiddler.set(newTitle,newBody,modifier,modified,tags,created);\n this.addTiddler(tiddler);\n if(title != newTitle)\n this.notify(title,true);\n this.notify(newTitle,true);\ndocument.forms.invisiForm.msg.value = "save";\ndocument.forms.invisiForm.oldtitle.value = title;\ndocument.forms.invisiForm.title.value = newTitle;\ndocument.forms.invisiForm.body.value = newBody;\ndocument.forms.invisiForm.modifier.value = modifier;\ndocument.forms.invisiForm.omodified.value = omodified.convertToYYYYMMDDHHMM();\ndocument.forms.invisiForm.modified.value = modified.convertToYYYYMMDDHHMM();\ndocument.forms.invisiForm.tags.value = tags;\ndocument.forms.invisiForm.submit();\n return tiddler;\n}\n//}}}

\n/***\n!!!removeTiddler\n***/\n//{{{\nTiddlyWiki.prototype.removeTiddler = function(title)\n{\n var tiddler = this.fetchTiddler(title);\n if(tiddler)\n {\n this.deleteTiddler(title);\n this.notify(title,true);\ndocument.forms.invisiForm.msg.value = "delete";\ndocument.forms.invisiForm.title.value = title;\ndocument.forms.invisiForm.modifier.value = config.options.txtUserName;\ndocument.forms.invisiForm.submit();\n }\n}\n//}}}

\n/***\n!!!createExternalLink\nusing ~ before link would override open in new window\n***/\n/*{{{*/\nwindow.createExternalLink=function (place,url)\n{\n var theLink = document.createElement("a");\n theLink.className = "externalLink";\nif( url.substring(0,1) == "\s~" )\n{\nurl = url.substring(1,url.length);\n theLink.href = url;\n theLink.title = config.messages.externalLinkTooltip.format([url]);\n place.appendChild(theLink);\n return(theLink);\n}\n theLink.href = url;\n theLink.title = config.messages.externalLinkTooltip.format([url]);\n if(config.options.chkOpenInNewWindow)\n theLink.target = "_blank";\n place.appendChild(theLink);\n return(theLink);\n}\n/*}}}*/

[[comonads]]

http://slipwave.info/

/***\n!ccTiddly config/macro\n!!!Disclaimer and warning\nThis tiddler is specially for ccTiddly. Please do not edit or save otherwise it may not work properly (unless you know what you are doing). If you happen to save it, and it didn't work, just delete the tiddler and the original config tiddler would reappear.\n***/\n\n/***\n!!!Changing the default options\n***/\n/*{{{*/\nconfig.options.chkHttpReadOnly = false; //make it HTTP writable by default\nconfig.options.chkSaveBackups = false; //disable save backup\nconfig.options.chkAutoSave = false; //disable autosave\n/*}}}*/\n\n/***\n!!!Put SiteTitle to webpage title\n***/\n/*{{{*/\nwindow.title = "Slipwave Info";\n/*}}}*/

[[libraries]]\n

for lazy functional programmers

I have a number of javascript libraries that I currently intend to bundle up under an [[Apache License]] as soon as I refactor more things and work out some of the [[kinks|js/test.results]]. In the meantime, feel free to browse around. You'll notice that the javascript below relies on the C preprocessor to build a coherent script. This way I can avoid relying on some form of external module system, and can cheat and use the C preprocessor to work around incompatibilities in various implementations of javascript.\n\n<<tabs txtJsTab \naop 'Browse the js.aop namespace' js.aop\ncps 'Browse the js.cps namespace' js.cps\ndom 'Browse the js.dom namespace' js.dom\nio 'Browse the js.io namespace' js.io\nlang 'Browse the js.lang namespace' js.lang \nmath 'Browse the js.math namespace' js.math\nmonad 'Browse the js.monad namespace' js.monad\nnative 'Browse the js.native namespace' js.native\nnet 'Browse the js.net namespace' js.net\ntest 'Browse the js.test namespace' js.test\nutil 'Browse the js.util namespace' js.util\n>>

This class implements a simple parser for javascript written in javascript. The idea was inspired by the existence of [[Brendan Eich]]'s [[Narcissus]] project, but the goal was to create a smaller more modular parser that could run in a wider array of browsers and remain unencumbered by the [[GPL]].\n\nThe parser creates an abstract syntax tree of [[Tokens|js.lang.Token]], which can then be used by [[other components|js.lang]].\n\nInternally, the parser is implemented a pair of recursive descent parsers sandwiching an operator precedence parser. Token types are either the operator or keyword itself or a numerical identifier in the case of open classes of terminals, exploiting javascript's loose type system.\n\nThe parser is currently capable of parsing a superset of [[ECMA-262]], but does not always give error messages appropriately on erroneous input. Its original purpose was to parse code for the [[recompiler|js.lang.Recompiler]], so it was originally presumed that its input would be syntactically correct. Since then, the utility of having a generic javascript parser, has expanded its role slightly, so error message are becoming more important.\n\nIt handles a couple of the easier extensions from the [[E4x]] specification - in particular the [[for each]] loop.\n\nThe parser can also be configured to support [[Spidermonkey]]-style [[atline directives]]. The build process, which bundles up the source code transforms the [[GCC]] C preprocessor's line directives into this form.\n\nWhen [[compressed|javascript compression]], the entire parser fits into under 6k.\n\nCurrent goals including extending it to handle a reasonable subset of [[ECMAScript 4]] and [[E4x]] without bloating it too severely.\n\n[[js/lang/Parser.js]]\n[[js/lang/Parser/progress.js]]

A [[Token|js.lang.Token]] performs multiple functions, serving as both the token generated by the lexer portion of the [[Parser|js.lang.Parser]] and as the abstract syntax tree node type that it returns for use by the [[Interpreter|js.lang.Interpreter]] and [[Recompiler|js.lang.Recompiler]].\n\nTokens support a basic [[toString|Object.toString]] method, tht can be used to transform them back into source code, and can be compiled to accept arbitrary visitor functions.\n\n[[js/lang/Token.h]]\n[[js/lang/Token.js]]\n[[js/lang/Token/visit.js]]\n[[js/lang/Token/tree.js]]

[[js.lang.Interpreter]] is a minimalist javascript interpreter that is capable of evaluating the syntax tree returned by our [[Parser|js.lang.Parser]]. The only optimization performed is some preliminary [[constant folding]].\n\nWhen [[compressed|javascript compression]], the [[parser|js.lang.Parser]] and interpreter together fit in under 8k. There are compilation options that enable us to emulate exceptions even when they are not available within limitations. This allows us to run more or less [[ECMA-262]] compliant code in browsers with poor javascript implementations. The result is that as long as the exception occurs in the interpreted code, the exception will be handled correctly.\n\n[[js/lang/Interpreter.js]]

This class provides a simple javascript code mangler intended to help improve performance and reduce bandwidth requirements for javascript-intensive applications.\n\nThe idea was engendered by considering LISP and other languages which have [[atoms|atom]] as a primitive type. They typically intern the atom by hashing, so that they can be compared for identity in a constant amount of time. On the other hand, accessing an identifier in javascript takes time proportional to the length of the string, and such identifiers take up more space when sent over the wire.\n\n[[We|we]] mimic traditional atom support by generating short strings instead of hash codes, since the short strings are of fixed length (at most 3 characters), string comparisons on them take a constant amount of time, at the expense of their being a small number of possible atoms, and comparatively long computation time to generate the atoms.\n\nThe atomizer exposes three methods that each accept an abstract syntax tree as an argument.\n* ''preserve'' - does no atomization. it scans the tree for identifiers and ensures that all identifiers used in this code will not be further mangled by subsequent atomizations. This allows you to specify a public interface.\n* ''intern'' - scans the abstract syntax tree for identifiers, and marks each one of them as used, so subsequent atomizations will not use of that name while shortening other variable names.\n* ''atomize'' - first interns the list of all identifiers used by the tree, then it assigns unique short variable names to each identifier that has been interned but not preserved. The unique names are guaranteed not to conflict with the names of any previously interned variable name. The syntax tree is modified in place.\nBetween these three functions you can arrange passes over your source code to make sure, for instance, that the source code to your web page remains unaltered and maintainable, while you [[compress|javascript compression]] the libraries that you are using behind the scenes.\n\nThe atomizer isn't sufficient to [[compress|javascript compression]] the source code by itself. You should also consider running [[Dean Edwards' packer|http://dean.edwards.name/packer/]] to help finish the job, and optionally [[gzip]] the output, depending on your intended audience. \n\n[[js/lang/Atomizer.js]]

In javascript the toString method of each object specifies how to convert that object to a string for display.\n\n

This object generates a [[partial CPS transform|partial CPS transformation]] of the source code it is supplied. You can control the transformation with [[recompiler directives]].\n\nThe goal of the recompiler is to support larger scale development in javascript with as little change in programming style and development speed as possible. To achieve that there are a number of items that need to be worked around in current browsers.\n* Javascript only lets you execute around a million instructions before it tells the user a script is taking too long.\n* Javascript lacks an interface for multitasking beyond the creation of a large number of callbacks and explicitly managing the state between calls.\nThe trampoline pauses itself for a millisecond after a number of [[quanta|quantum]] have elapsed to manage the first problem, and the [[thread|js.cps.Thread]] interface manages the second concern.\n\nWhen [[compressed|javascript compression]] the [[parser|js.lang.Parser]], recompiler, and [[runtime library]] fit in under 12k.\n\n<<tiddler [[recompiler internals]]>>\n\nTechnically the [[atomizer|js.lang.Atomizer]] is also a recompiler pass, but it is presently intended to be used separately. Any ECMAScript Edition 4 support added in the near future will also be by way of recompiler passes.\n\n[[js/lang/Recompiler.js]]

Tail-call optimization is the practice of replacing the current stack frame with the stack frame of the function you are calling, when the only thing you would otherwise do with the result is pass it to your caller. This is feature of many functional programming languages, since they tend to rely on recursion as their principle looping construct. It is a requirement, for instance of any standard Scheme compiler, and is performed by the [[GCC]] C/C++ compilers.\n\nView [[an implementation|tail-call optimization implementation]].

[[Andrew Appel|http://www.cs.princeton.edu/~appel/]] proposed an alternative form of [[trampoline]] to [[Henry Baker|http://en.wikipedia.org/wiki/Henry_Baker]] that was used in slightly modified form by the [[Chicken Scheme compiler|http://www.call-with-current-continuation.org/]]. Instead of [[thunking|thunk]] and returning each [[continuation|continuations]], Appel proposed using up the stack and using setjmp/longjmp to empty the stack. This minimizes the overhead associated with trampolining, replacing it with the required maintenance of a stack position counter. \n\n[[Chicken|http://www.call-with-current-continuation.org/]] uses it to maintain the first stage of a generational garbage collector, and stores its items locally on the stack.\n\nOn most platforms, this form of trampoline trades in cache coherence and localization for an almost factor of two reduction in function call overhead. In the case of javascript it is nearly impossible to see any real cache coherent benefits in the first place, so the down side is never realized.\n\n[[We|we]] use this approach for the code output by [[js.lang.Recompiler]]. It nets us an appreciable performance gain over a simple [[thunk]] and [[trampoline]] approach. Javascript implementations typically provide a fixed number of stack frames, rather than an actual stack size limitation, so we simply count down to stack frames, and eventually {{{throw}}} or {{{return}}} a special exception that indicates that execution should resume from the point indicated by the exception. This provides us with a form of [[tail-call optimization]].\n\nOne full pass through the stack doubles as a natural quantum for [[threading|js.cps.Thread]] purposes.\n\nView [[a simple implementation|Appel trampoline implementation]].

A trampoline is a special function often used to interpret languages with tail-call optimization in languages that do not support it themselves.\n\nThe idea is that you [[thunk]] each recursive call, and pass the thunk back to a special function called a trampoline. The trampoline then executes the thunked function. Assuming that our trampoline is passed a function that never calls return except to return a null or undefined value when there is no further continuation, a simple trampoline might be as follows\n\n{{{\nfunction trampoline(f) {\n while(f=f());\n}\n}}}

A [[thunk]] is a function that when called performs some task that was previously set up, but not executed. \n\n{{{\nfunction prepare_something(a,b,c,d) { \n return function() { \n ... do something with a,b,c,d ...\n };\n}\n}}}\n\nThunks can be used for lazy evaluation, and by [[trampoline]]s to provide [[tail-call optimization]].

A partial CPS transformation is a [[CPS transformation]] that leaves some function calls untransformed for performance reasons. Following a convention from Hailiwiki, we transform function calls to methods that end with an underscore. The remaining functions are considered to be atomic and are called traditionally.\n\nThis behavior can be changed by sending appropriate [[recompiler directives]].

A [[CPS]] transformation is a way to turn a program inside-out and eliminate the need for a {{{return}}} statement by converting the code to [[continuation-passing style]]. \n\nView [[an example|CPS transformation example]].

Tail-recursion is when a function calls itself as its last operation before returning. It is a special case of [[tail-call optimization]]. For most of your undergraduate career in computer science, you are taught to replace recursion with iteration; for most of your graduate career you wind up putting it back.

/*{{{*/\nversion.extensions.smileyMacro = {major: 0, minor: 1, revision: 0, date: new Date(2005,7,20)};\n//Author: Alan Hecht\nconfig.macros.smiley = {}\nconfig.macros.smiley.handler = function(place,macroName,params)\n{\n var palette = ["transparent","#000000","#1a1507","#352e18","#464646","#666666","#a3141e","#b06b63","#cc9900","#dd9030","#dddddd","#e89d00","#edc32a","#f3cb3c","#fdf201","#fdf526","#ff3149","#ffac00","#ffbf06","#ffc846","#ffcc66","#ffd758","#ffdd01","#ffea7b","#ffed55","#ffffff"];\n var data = params;\n var imageMap = null;\n if(data[0] == ":-)" || data[0] == ":)")\n\n imageMap = "aaaaabbbbbaaaaaaaabdtyyvtdbaaaaabnyxxxxxujbaaabmyyffyffuujbaadyyyeeyeetttdabppppddyddpmmlbbwoooooooowsrlbbwwpooooowwmrlbbwwboooowwwbllbbwwwboooowbrllbacwwwbbbbbrllcaablswwwwsrrlibaaablsssrrllibaaaaabcrrlllcbaaaaaaaabbbbbaaaaa";\n else if(data[0] == ":-(" || data[0] == ":(")\n imageMap = "aaaaabbbbbaaaaaaaabdtyyvtdbaaaaabnyxxxxxujbaaabmyyyyyyyuujbaadyyyeeyeetttdabppppddyddpmmlbbwoooooooowsrlbbwwpooooowwmrlbbwwoooooowwrllbbwwwwbbbbbsrllbacwwbwwwwsbllcaablswwwwsrrlibaaablsssrrllibaaaaabcrrlllcbaaaaaaaabbbbbaaaaa";\n else if(data[0] == ";-)" || data[0] == ";)")\n imageMap = "aaaaabbbbbaaaaaaaabdtyyvtdbaaaaabnyxxxxxujbaaabmyyxxxxxuujbaadyyyxxxeetttdabppphddyddpmmlbbwoooooooowsrlbbwwpooooowwmrlbbwwboooowwwbllbbwwwboooowbrllbacwwwbbbbbrllcaablswwwwsrrlibaaablsssrrllibaaaaabcrrlllcbaaaaaaaabbbbbaaaaa";\n else if(data[0] == ":-|" || data[0] == ":|")\n imageMap = "aaaaabbbbbaaaaaaaabdtyyvtdbaaaaabnyxxxxxujbaaabmyyffyffuujbaadyyyeeyeetttdabppppddyddpmmlbbwoooooooowsrlbbwwpooooowwmrlbbwwoooooowwrllbbwwwwbbbbbsrllbacwwwwwwwsrllcaablswwwwsrrlibaaablsssrrllibaaaaabcrrlllcbaaaaaaaabbbbbaaaaa";\n else if(data[0] == ":-D" || data[0] == ":D")\n imageMap = "aaaaabbbbbaaaaaaaabdtyyvtdbaaaaabnyxxxxxujbaaabmyyeeyeeuujbaadyyyeeyeetttdabppppyyyyypmmlbbwbbbbbbbbbbblbbwbkzzzzzzzkbwbbwbfzzzzzzzfbwbbwbkzzzzzzzkbwbacwbkzzzzzkblcaablsbkzzzkblibaaablsbbbbblibaaaaabcrrlllcbaaaaaaaabbbbbaaaaa";\n else\n createTiddlyElement(place,"span",null,"errorNoSuchMacro","unknown smiley");\n if(imageMap)\n {\n var box = createTiddlyElement(place,"span",null,"smiley",String.fromCharCode(160));\n box.style.position = "relative";\n box.style.width = "15px";\n box.style.height = "15px";\n box.style.marginLeft = "1px";\n box.style.marginRight = "1px";\n box.style.paddingRight = "12px";\n box.style.verticalAlign = "top";\n\n //now divide into 15x15 grid and create each pixel\n // rows\n for(r=0; r<15; r++)\n {\n // columns\n for(c=0; c<15; c++)\n {\n //create each pixel with the correct background\n var pix = document.createElement("img");\n pix.className = "smileyPixel";\n pix.style.position = "absolute";\n pix.border = 0;\n pix.style.top = r + "px";\n pix.style.left = c + "px";\n pix.style.width = "1px";\n pix.style.height = "1px";\n pix.style.backgroundColor = palette[imageMap.charCodeAt((r*15)+c)-97];\n pix.src = "data:image/gif,GIF89a%01%00%01%00%91%FF%00%FF%FF%FF%00%00%00%C0%C0%C0%00%00%00!%F9%04%01%00%00%02%00%2C%00%00%00%00%01%00%01%00%40%02%02T%01%00%3B";\n box.appendChild(pix);\n }\n }\n }\n}\n/*}}}*/

CPS is an abbreviation for [[continuation-passing style]].

Continuation-passing style ([[CPS]]) is an alternative way to think about functions, in which functions never return. Instead they invoke another function (called a [[continuation|continuations]]) with their result upon completion. This requires [[tail-call optimization]] to be used for anything larger than a toy problem, and becomes fairly complicated in the face of traditional imperative programming loop constructions that need to be transformed into [[tail-recursion]] or emulated by means of an [[inverted Duff's Device]].\n\nYou can think of [[callback functions]] as a primitive form of continuation-passing style. A [[CPS transformation]] is just an automatic way to generate the appropriate callbacks while transforming function definitions to use such callbacks rather than return their result.\n

<<tiddler 'LoginPanel'>>

[[js.net.Uri]]

A simple functional object for URI manipulation. Used to resolve and relativize [[URI]]s. The interface is designed to roughly follow that of the Java's java.net.URI class.\n\n[[js/net/Uri.js]]

[[js.util.DisjointSet]]\n[[js.util.Heap]]\n[[js.util.Timer]]\n[[js.util.Treap]]\n[[js.util.Trie]]\n

A simple genericHeap implementation.\n\nUsage:\n\n{{{\n var heap = new js.util.Heap(compare,init,sentinel);\n}}}\n\nParameters:\n\n* "compare" is a function that takes two arguments a and b, and compares them returning true if a>b (for a min-heap).\n* "init" is an optional 0-based array containing initial values, that is build-heap'ed. This is more efficient than inserting the elements one at a time, but the passed array is destructively modified.\n* "sentine" is a sentinel value that will be returned when you attempt to pop an element off of an empty stack.\n\n[[js/util/Heap.js]]

{{{\nversion.extensions["view-sourceMacro"] = {major: 0, minor: 1, revision: 0, date: new Date(2006,6,13)};\n\n// Author: Edward Kmett. No warrantee expressed or implied.\n// You may freely distribute the source code to this macro. \n// NB: this relies on a couple of external script tags and a stylesheet\n// and is implemented using http://www.dreamprojections.com/SyntaxHighlighter and MochiKit.\n\nif(typeof XMLHttpRequest=='undefined'&&typeof window.ActiveXObject=='function')\n var XMLHttpRequest=navigator.userAgent.toLowerCase().indexOf('msie 5')>=0\n ?function(){return new ActiveXObject("Microsoft.XMLHTTP")}\n :function(){return new ActiveXObject("Msxml2.XMLHTTP")};\n\nconfig.macros["view-source"] = {};\nconfig.macros["view-source"].handler = function(place,macroName,data) {\n var options = data, language = data[0], source=data[1], opts = {}, b = dp.sh.Brushes, map = {};\n for (var i=0;i<options.length;++i) opts[options[i]] = 1;\n for (var i in b) {\n var a = b[i].Aliases;\n for (var j=0;j<a.length;++j) map[a[j]] = i;\n }\n highlighter = new dp.sh.Brushes[map[data[0]]]();\n highlighter.addGutter = !opts.nogutter;\n highlighter.addControls = !opts.nocontrols;\n highlighter.collapse = opts.collapse;\n highlighter.firstLine = 1;\n var request = new XMLHttpRequest();\n request.onreadystatechange = function() { \n if (request.readyState == 4) { \n highlighter.Highlight(request.responseText);\n var div = createTiddlyElement(null,'div',null,'dp-highlighter');\n div.appendChild(highlighter.table);\n place.appendChild(div);\n }\n };\n request.open("GET","http://slipwave.info/jslib/"+source,true);\n request.send(null);\n /* var a = document.createElement("a");\n a.setAttribute("href","http://slipwave.info/jslib/"+source,true);\n var t = document.createTextNode(source);\n a.appendChild(t);\n place.appendChild(a);*/\n};\n}}}

[[js.cps.Thread]] works with the [[Recompiler|js.lang.Recompiler]] to provide a functional equivalent to Java's java.lang.Thread interface. The recompiler transforms your code to use [[continuations]] transparently and uses them to provide a more traditional multitasking interface. [[Semaphores|js.cps.Semaphore]] are available to provide blocking semantics, and threads can be organized into [[groups|js.cps.Thread.Group]].\n\n[[js/cps/Thread.h]]\n[[js/cps/Thread.js]]

The [[recompiler|js.lang.Recompiler]] extends the javascript language slightly by interpreting certain labels that it encounters while parsing to change its behavior. In effect these special labels become new keywords.\n\n* marked: - transform only function calls to identifiers that end in _ to continuation-passing style. This is the default. \n* native: - Perform no transformations other than what is absolutely necessary to deal with whatever flowgraph flattening has been performed outside of the current scope.\n* cps: - Transform all calls to use continuation passing stye through a simple proxy. If a function exists with the name called followed by an _, then it is called with CPS. Otherwise, we call the function, and then pass its result to the continuation.

Narcissus is another javascript-in-javascript parser/interpreter. It was created by [[Brendan Eich]] and is part of the Mozilla project, available at http://lxr.mozilla.org/mozilla/source/js/narcissus/.

A URI is a Uniform Resource Identifier. To be pedantic it is a supersets of both [[URL]]s and [[URN]]s, where [[URL]]s specify a specific protocol and address, while [[URN]]s name a resource without specifying necessarily how to retrieve it.

A URL is a Uniform Resource Locator. It tells you how to find a resource without necessarily telling you what it is. These are what you type into the address bar of your browser. They are a type of [[URI]].

A URN is a Uniform Resource Name. XML namespaces are classic examples of [[URN|URNs]]. They specify the name of a resource, without necessarily telling you how to find it. A [[URN]] is a type of [[URI]].

The concept of an atom was introduced by LISP. Atoms are strings that are pre-hashed, so comparisons for equality between them take a constant amount of time. They are typically used inside of compilers and interpreters to reduce the dependency of execution time on the length of the identifiers used.\n

\n<<tabs txtLibrariesTab Javascript 'Browse the js namespace' js Haskell 'Browse haskell code' Haskell C/C++ 'Browse C/C++ source code' C/C++>>\n

These are generic programming topics, without a specific javascript bent.

A pragmatist tends to think of a continuation is a formal way of thinking about [[callback functions]], and is borrowed from functional programming languages like LISP. Theoretical computer scientists like to think about them as the [[dual|http://en.wikipedia.org/wiki/Duality_%28mathematics%29]] of functions. Functions generate values, continuations consume them by telling you what to do when you get the value back. There are nice theorems that shows you you can [[transform|CPS transformation]] any program that uses {{{return}}} into one that uses [[continuation-passing style]] and that in fact, any control structure can be implemented with continuations.

Slipwave is a forum for the insane ramblings of [[Edward Kmett]]. <<smiley :-D>>\n\nThis page exists more or less as a blog in code form; the source code here is updated in real time. I will likely add the ability to post comments in the near future, but feel free to [[contact me|mailto:ekmett (-at-) gmail (.dot.) com]] in the meantime. \n\n\n

A callback function is a function that you pass as an argument to another function, which gets invoked after some event - usually the completion of your desired task. Event handlers in javascript are callbacks. Explicit use of a lot of callbacks can lead to confusing code.

<<search>><<closeAll>><<permaview>><<slider chkSliderEditPanel EditPanel 'edit »' 'Editing options'>><<slider chkSliderOptionsPanel OptionsPanel 'options »' 'Change advanced options'>>

[[js.math.Perlin]]

Provides static implementations of the bias and gain functions by [[Ken Perlin|http://mrl.nyu.edu/~perlin/]]. These are particularly useful when you want to ease in and out of an animation.\n\n[[js/math/Perlin.js]]

A simple disjoint set data structure for use in fast union-find algorithms.\n\n[[js/util/DisjointSet.js]]

A joint binary-tree/heap implementation that can be used in most places you would employ balanced trees. It provides a randomized tree with nice balance properties with a lot less overhead than a traditional AVL or Red-Black tree, and can be used to provide sorted dictionaries.\n\n[[js/util/Treap.js]]

A minimal Trie implementation used to generate leafy regular expressions. The following regular expression, which recognizes javascript keywords was generated by this mechanism. This is based on public domain code from perl's Regexp::Trie by Dan Kogai.\n\n{{{\n/(?:break|c(?:a(?:se|tch)|on(?:st|tinue))|d(?:e(?:fault|lete)|o)|else|f(?:alse|inally|or|unction)|i(?:n(?:stanceof)?|f)|n(?:ew|ull)|return|switch|t(?:h(?:is|row)|r(?:ue:y)|ypeof)|v(?:ar|oid)|w(?:hile|ith))/\n}}}\n\n[[js/util/Trie.js]]

Roughly mimics the java.lang.ThreadGroup interface over [[js.cps.Thread|js.cps.Thread]]s. This allows you to suspend or interrupt a large number of [[threads|js.cps.Thread]] at once. Unlike java's thread groups, you assign Threads to a Thread.Group after it has been created and threads can belong to multiple groups.\n\n[[js/cps/Thread/Group.js]]

Provides both the semantics of a Dijkstra-style PV semaphore and a simple wait/notify condition variable for [[threads|js.cps.Thread]].\n\n[[js/cps/Semaphore.js]]

Multiplexes the use of one browser timer for multiple tasks by way of a [[heap|js.util.Heap]]. This helps support heavily parallel tasks in a browser, since the number of timers that you are allowed to have outstanding in one window is unspecified.\n\n[[js/util/Timer.js]]

/*{{{*/\nversion.extensions.tagCloud = {major: 1, minor: 0 , revision: 1, date: new Date(2005,8,16)};\n//Created by Clint Checketts, contributions by Jonny Leroy and Eric Shulman\n\nconfig.macros.tagCloud = {\n noTags: "No tag cloud created because there are no tags.",\n tooltip: "%1 tiddlers tagged with '%0'"\n};\n\nconfig.macros.tagCloud.handler = function(place,macroName,params) {\n \nvar tagCloudWrapper = createTiddlyElement(place,"div",null,"tagCloud",null);\n\nvar tags = store.getTags();\nfor (t=0; t<tags.length; t++) {\n for (p=0;p<params.length; p++) {\n if (tags[t][0] == params[p] || tags[t][0].indexOf('/')>=0) tags[t][0] = "";\n }\n}\n\n if(tags.length == 0) \n createTiddlyElement(tagCloudWrapper,"span",null,null,this.noTags);\n //Findout the maximum number of tags\n var mostTags = 0;\n for (t=0; t<tags.length; t++) if (tags[t][0].length > 0){\n if (tags[t][1] > mostTags) mostTags = tags[t][1];\n }\n //divide the mostTags into 4 segments for the 4 different tagCloud sizes\n var tagSegment = mostTags / 4;\n\n for (t=0; t<tags.length; t++) if (tags[t][0].length > 0){\n var tagCloudElement = createTiddlyElement(tagCloudWrapper,"span",null,null,null);\n tagCloudWrapper.appendChild(document.createTextNode(" "));\n var theTag = createTiddlyButton(tagCloudElement,tags[t][0],this.tooltip.format(tags[t]),onClickTag,"tagCloudtag tagCloud" + (Math.round(tags[t][1]/tagSegment)+1));\n theTag.setAttribute("tag",tags[t][0]);\n }\n\n};\n\nsetStylesheet(".tagCloud span{height: 1.8em;margin: 3px;}.tagCloud1{font-size: 1.2em;}.tagCloud2{font-size: 1.4em;}.tagCloud3{font-size: 1.6em;}.tagCloud4{font-size: 1.8em;}.tagCloud5{font-size: 1.8em;font-weight: bold;}","tagCloudsStyles");\n/*}}}*/

Spidermonkey is the reference implementation of javascript maintained by the Mozilla Foundation. It is directly descended from the original implementation of javascript by [[Brendan Eich]], and so is usually considered the canonical reference.\n\n

Constant folding is the process of precalculating derived constants. \n\nFor example: {{{ print(2*2); }}} becomes {{{ print(4); }}}\n

Rhino is an implementation of javascript in Java. Documentation on Rhino is available at http://www.mozilla.org/rhino/. It implements [[ECMA-262]], [[E4x]] and provides built-in support for [[continuations]]

Edward Kmett is the author of these pages (er.. this page?) and of the source code buried herein. He tried wearing a suit and tie and playing corporate big-wig, but since the dot-com bubble burst he has been spending his time collecting degrees, lecturing at [[EMU|http://emich.edu]], playing with [[linguistics|http://linguistlist.org/people/edward.html]], and letting his hair grow out. He also appears to like to talk about himself in the third person.\n\nYou may contact him by [[e-mail|mailto:ekmett (at) gmail (dot) com]] or continue to mutter about him behind his back as you see fit.

Er.., well [[I|Edward Kmett]]. <<smiley ;-)>>

A minimal [[Appel trampoline]] implementation follows.\n{{{\nFunction.prototype.appel = function(c) {\n c = c || 1;\n return "("+this.toString().replace(/\s{/, "{ if((appel_d-="+c+")<0) return appel_a(this,arguments);")+")";\n};\n\nvar appel_d = 0;\nvar appel_a = function(t,a) {\n var d = appel_d;\n var f = function(){return a.callee.apply(t,a)};\n try {\n appel_a = function(t,a) {\n return function() {\n return a.callee.apply(t,a)\n }\n };\n do {\n appel_d = 990;\n } while(f=f());\n } finally {\n appel_a = arguments.callee; appel_d = d;\n }\n}\n}}}\n\nTo use it you would usually recompile a function with the idiom:\n\n{{{ eval(function(a,b,...){...}.appel()); }}}\n\nThe reason has to do with the fact that the only way to evaluate in the context that a function was created is to actually do the evaluation then and there. Otherwise, when you evaluate the function later you will be doing so in a different lexical scope, with different local variables. The above example returns its thunk. It could equally well throw them. The performance of both implementations is identical.\n\nNote that we sneakily replace {{{appel_a}}} while the function is running, so that the first Appel'ed function called creates the trampoline, then puts itself on it. Then when the stack runs out of room, it unwinds the stack before resuming the thunk. \n\n

[[The GNU Public License|http://www.gnu.org/copyleft/gpl.html]].

[[We|we]] process javascript in several stages. Exactly which process is applied is a function of the role the code will play.\n\nFirst we use the C preprocessor on it, to manage module dependencies.\n\nWe can then either\n* just [[clean up line directives|cleaning up line directives]], pack the code to the beginning of line to take some air out of it, [[gzip]] the result and call it done. Thanks to [[atline directives]], this approach is reasonably efficient and gzipping is remarkably effective at dealing with long identifiers,\n* or we can atomize the resulting code, pack the code using [[Dean Edwards' packer|http://dean.edwards.name/packer/]] and gzip the result.\n

The C preprocessor leaves an awful lot of [[line directives]] in the source file that are not strictly necessary to determine what line the error occured on, and it is not designed to shift them around to minimize subsequent and preceding whitespace. After converting to [[atline directives]], a little bit of perl can clean the code right up.\n\n!!! minimize-lines\n{{{\n#!/usr/bin/perl\n$emitted = 1;\n$file = "<stdin>";\n$line = 0;\n$q = "";\n$n = "";\nwhile(<>){\n if (m/^\s/\s/\s@line\ss*(\sd+)\ss*"([^"]+)".*$/ms) {\n # line directive.\n $emitted = 0;\n $line = $1;\n $file = $2;\n } else {\n $line++;\n if (!m/^$/ || $emitted) {\n if (!$emitted++) {\n $q=~ s/[\ss\sn]*$//s; # remove blanks before @line directive\n print(qq{$q$n//\s@line $line "$file"\sn});\n $q = "";\n $n = "\sn";\n }\n $q .= $_;\n }\n }\n}\n\nprint $q;\n}}}

The C preprocessor leaves lines either of the traditional form {{{ #line <number> ["<file>"] }}} or of the GCC style {{{ # <number> ["<file>"] [<number>] }}} littered throughout the code that it feeds forward to the C/C++ compiler. These are used to locate where in the original source files an error occured. We transform these into [[atline directives]].

The [[GNU Compiler Collection|http://gcc.gnu.org]], although historically it just stood for the GNU C Compiler.

The following [[tail-call optimization]] decorator is based on [[a blog entry by Sjoerd Visscher|http://w3future.com/weblog/2006/02/]]\n\n{{{\nFunction.prototype.tco = function() {\n var g = this;\n return function() {\n for (var caller = arguments.callee.caller; caller; caller = caller.caller)\n if (caller == arguments.callee)\n throw { tail_call_arguments: arguments, t: this };\n\n var args = arguments;\n var me = this;\n while (true) try {\n return g.apply(me, args);\n } catch(e) {\n if (!e.tail_call_arguments) throw e;\n args = e.tail_call_arguments;\n me = e.t;\n }\n };\n};\n}}}

[[GNU zip|http://www.gzip.org/]] is a long-time standard compression program. Its underlying algorithm is supported by most web browsers directly, enabling us to send compressed content to the browser.

In javascript we cannot nest our cases within child blocks, so we have to invert [[Duff's Device]] to obtain:\n\n{{{\nout: do switch($state) { \ncase 0:\n\ncase 1:\n\ncase 2:\n\n} while (1);\n}}}\n\nInside of the modified device, the code "{$state=<x>;break}" becomes equivalent to a traditional "goto <x>" and "break out," breaks us out of the loop. In order to support multiple loops we have to flatten the flowgraph of the function, effectively transforming all of our nice high level language constructs programmatically into "gotos". Fortunately [[js.lang.Recompiler]] takes care of this task for us. A proof of the clasical result that it is possible to transform nested loops into a single loop is given in:\n\nKozen, D., //Kleene algebra with tests//. Transactions on Programming Languages and Systems, 19 (1997) pp.427-43.

The [[recompiler|js.lang.Recompiler]] extends the javascript language slightly by interpreting certain labels that it encounters while parsing to change its behavior. In effect these special labels become new keywords.\n* ''marked'': - transform only function calls to identifiers that end in _ to [[continuation-passing style]]. This is the default. \n* ''native'': - Perform no transformations other than what is absolutely necessary to deal with whatever [[flowgraph flattening]] has been performed outside of the current scope.\n* ''cps'': - Transform all calls to use continuation passing stye through a simple proxy. If a function exists with the name called followed by an {{{_}}}, then it is called with [[CPS]]. Otherwise, we call the function, and then pass its result to the [[continuation|continuations]].

A naive [[CPS]] transformation might transform the following:\n{{{\nfunction square(x) { return x*x; }\nprint(square(x));\n}}}\ninto:\n{{{\nfunction square(x,return_) { return_(x*x); }\nsquare(x,print);\n}}}\nThe above example is somewhat misleading because, when we transform more than just a single expression the continuation also has to include the remaining statements to be executed not just the remainder of the current expression.\n\nIn other words, {{{ expr[f(x)];other statements }}} becomes {{{ f_(x,function(<temp>) { expr[<temp>]; ... }); }}}.\n\nThe above approach is naive, because the lexical scope chains grow in proportion to the number of continuations used in each function body. This can be avoided by using an [[inverted Duff's Device]] and a flattened flowgraph.

We try to avoid [[global namespace pollution]] and [[prototype pollution]] as much as possible, and more or less follow the structure of Java's namespaces - if only for mnemonic reasons. We are not out to reinvent Java, and as such we do not follow [[Java Bean]] naming conventions and if a feature would be prohibitively bloated or impractical to implement in the Java way, we go in another direction.\n\nThe code has been optimized to minimize bandwidth and server requirements once [[processed|javascript compression]], not for readability. These libraries are designed to be largely employed independently, and to include only the minimum set of requirements to operate. Variable names should be short, functions should be small. Code should be aggressively optimized for space, and not be afraid to use side-effects to achieve that goal.

Used to store [[abstract syntax tree nodes|js.lang.Token]] that can handle an arbitrary number of arguments.\n\n[[js/lang/Token/Array.js]]

Javascript's {{{ for (var i in object) {} }}} loop is somewhat unusual, compared to other scripting languages, in that it iterates over keys, not values.\n\n[[E4x]] introduced a {{{for}}} loop that iterates over the values contained in the object with the syntax {{{ for each (var i in object) {} }}} without making {{{each}}} into a keyword. \n\nSupport for this expression does not require us to break any syntactically correct [[ECMA-262]] program and is trivial, so it was added to the [[parser|js.lang.Parser]] and [[interpreter|js.lang.Interpreter]].

If enough interest is generated, [[we]]'ll supply anonymous CVS access.

<<newTiddler>>\n<<newJournal 'DD MMM YYYY'>>\n<<saveChanges>>\nUsername:\n<<option txtUserName>>\nPassword:\n<<option pasSecretCode>>\nWelcome Edward Kmett\n[[login|~/index.php?]]

<<list all>>

<div class='toolbar' macro='toolbar -closeTiddler closeOthers +editTiddler permalink references jump'></div>\n<div><span class='title' macro='view title'></span><span class='tagged' macro='tags'></span></div>\n\n<div class='subtitle'><span macro='view modifier link'></span>, <span macro='view modified date [[DD MMM YYYY]]'></span> (created <span macro='view created date [[DD MMM YYYY]]'></span>)\n</div>\n<div class='tagging' macro='tagging'></div>\n<div class='viewer' macro='view text wikified'></div>\n<div class='tagClear'></div>

<<list missing>>

This namespace isn't really a namespace. Code in this folder typically implements missing functionality for the current platform. Hence the code is listed by source file, not class.\n\n[[Array]]\n[[Boolean]]\n[[Function]]\n[[Object]]\n[[Platform]]\n[[String]]\n[[XMLHttpRequest]]\n

A java.io.BufferedOutputStream clone.\n\n[[js/io/BufferedOStream.js]]

[[js.dom.Event]]

The Event namespace contains methods for manipulating events. These events do not even have to be DOM specific. \n\nYou can \n* ''listen'' to an event\n* ''remove'' an event handler\n* or ''trigger'' an event\n\n[[js/dom/Event.js]]

A java.io.BufferedInputStream clone.\n\n[[js/io/BufferedIStream.js]]

Every function declaration in javascript brings with it its own lexical scope, variables declared in that function are placed in that scope. The chain of these formed by containment is a lexical scope chain. Variable name resolution in javascript takes time proportional to the number of lexical scopes between the reference and the declaration. Consequently, code that looks like \n\n{{{ var a = 12; function b(){ return function c() { return function d() { ... return function e() { while (--a) { print("Hi"); return a; } ... } } } }}}\n\ncan execute quite slowly, because each additional function declaration creates a new lexical scope on the chain between the reference and declaration of the variable. To resolve the variable, javascript checks each lexical scope in turn before proceeding to the next one, because the language has so little structure, this is the only way this can proceed.\n\n

Flowgraph flattening is the process of taking the [[flowgraph]] of a function and transforming it into a sequence of statements and jumps, much like the final output of a compiler generates assembly code. Since in the traversal of the flowgraph by the [[recompiler|js.lang.Recompiler]], unreachable code is not never touched, this implicitly performs [[dead-code elimination]].

We attempt to eliminate redundant labels from the states in the [[flowgraph]] before we proceed to [[flowgraph flattening]]. All states in the flowgraph are initially numbered, then once the flowgraph is constructed, we perform [[constant folding]] and [[dead-code elimination]] to prune branches that cannot be reached. Finally we merge consecutive states when there only one entry point to the second state. The result is then flattened to form an [[inverted Duff's Device]] with a small number of states and all iteration folded into the single while statement that wraps the device.

ECMA-262 is the ECMA standard that defines ECMAScript 3, a standardized form of javascript syntax.

E4x is an ECMA specification describing extensions to the javascript language for supporting snippets of XML as a first-class language primitive.

An atline directive is a line of the form\n\n{{{\n//@line <number> ["<optional filename>"]\n}}}\n\nwhich indicates that the following lines were taken originally from the named file, starting at line <number>.\n\nThey fill the same purpose as C line directives.

ECMAScript 4 is the new version of Javascript that is being developed. It adds strong typing, templates, traditional classes, namespaces, and the kitchen sink to the language we all know and love.\n\n[[See the public export of the specification draft wiki|http://developer.mozilla.org/es4/]]

[[Brendan Eich]] is the original author of Javascript. He has a blog available online at http://weblogs.mozillazine.org/roadmap/.

/***\nCustom CSS\n***/\n/*{{{*/\n\n.dp-highlighter table.dp-c {\n border: 0px 0px 0px 0px;\n}\n\n.dp-highlighter table.dp-c td, .dp-highlighter table.dp-c th {\n border: 0px;\n}\n\n/*}}}*/

/***\n!Sections in this Tiddler:\n*Generic rules\n**Links styles\n**Link Exceptions\n*Header\n*Main menu\n*Sidebar\n**Sidebar options\n**Sidebar tabs\n*Message area\n*Popup\n*Tabs\n*Tiddler display\n**Viewer\n**Editor\n*Misc. rules\n!Generic Rules /%==============================================%/\n***/\n/*{{{*/\nbody {\n font-size: .75em;\n font-family: helvetica, arial, sans-serif;\n position: relative;\n margin: 0;\n padding: 0;\n}\n\nh1,h2,h3,h4,h5 {\n font-weight: bold;\n text-decoration: none;\n padding-left: 0.4em;\n}\n\nh1 {font-size: 1.35em;}\nh2 {font-size: 1.25em;}\nh3 {font-size: 1.1em;}\nh4 {font-size: 1em;}\nh5 {font-size: .9em;}\n\nhr {\n height: 1px;\n}\n\na{\n text-decoration: none;\n}\n\nol { list-style-type: decimal }\nol ol { list-style-type: lower-alpha }\nol ol ol { list-style-type: lower-roman }\nol ol ol ol { list-style-type: decimal }\nol ol ol ol ol { list-style-type: lower-alpha }\nol ol ol ol ol ol { list-style-type: lower-roman }\nol ol ol ol ol ol ol { list-style-type: decimal }\n/*}}}*/\n/***\n''General Link Styles'' /%-----------------------------------------------------------------------------%/\n***/\n/*{{{*/\n.externalLink {\n text-decoration: underline;\n}\n\n.tiddlyLinkExisting {\n font-weight: bold;\n}\n\n.tiddlyLinkNonExisting {\n font-style: italic;\n}\n\n/* the 'a' is required for IE, otherwise it renders the whole tiddler a bold */\na.tiddlyLinkNonExisting.shadow {\n font-weight: bold;\n}\n/*}}}*/\n/***\n''Exceptions to common link styles'' /%------------------------------------------------------------------%/\n***/\n/*{{{*/\n\n#mainMenu .tiddlyLinkExisting, \n#mainMenu .tiddlyLinkNonExisting,\n#sidebarTabs .tiddlyLinkExisting,\n#sidebarTabs .tiddlyLinkNonExisting{\n font-weight: normal;\n font-style: normal;\n}\n\n/*}}}*/\n/***\n!Header /%==================================================%/\n***/\n/*{{{*/\n\n.header {\n position: relative;\n}\n\n.header a:hover {\n background: transparent;\n}\n\n.headerShadow {\n position: relative;\n padding: 1.5em 0em 1.5em 1em;\n left: 1px;\n top: 1px;\n}\n\n.headerForeground {\n position: absolute;\n padding: 1.5em 0em 1.5em 1em;\n left: 0px;\n top: 0px;\n}\n\n.siteTitle {\n font-size: 3em;\n}\n\n.siteSubtitle {\n font-size: 1.2em;\n}\n\n/*}}}*/\n/***\n!Main menu /%==================================================%/\n***/\n/*{{{*/\n#mainMenu {\n position: absolute;\n left: 0;\n width: 10em;\n /*text-align: right;*/\n line-height: 1.6em;\n padding: 1.5em 0.5em 0.5em 0.5em;\n font-size: 1.1em;\n}\n\n/*}}}*/\n/***\n!Sidebar rules /%==================================================%/\n***/\n/*{{{*/\n#sidebar {\n position: absolute;\n right: 3px;\n width: 16em;\n font-size: .9em;\n}\n/*}}}*/\n/***\n''Sidebar options'' /%----------------------------------------------------------------------------------%/\n***/\n/*{{{*/\n#sidebarOptions {\n padding-top: 0.3em;\n}\n\n#sidebarOptions a {\n margin: 0em 0.2em;\n padding: 0.2em 0.3em;\n display: block;\n}\n\n#sidebarOptions input {\n margin: 0.4em 0.5em;\n}\n\n#sidebarOptions .sliderPanel {\n margin-left: 1em;\n padding: 0.5em;\n font-size: .85em;\n}\n\n#sidebarOptions .sliderPanel a {\n font-weight: bold;\n display: inline;\n padding: 0;\n}\n\n#sidebarOptions .sliderPanel input {\n margin: 0 0 .3em 0;\n}\n/*}}}*/\n/***\n''Sidebar tabs'' /%-------------------------------------------------------------------------------------%/\n***/\n/*{{{*/\n\n#sidebarTabs .tabContents {\n width: 15em;\n overflow: hidden;\n}\n\n/*}}}*/\n/***\n!Message area /%==================================================%/\n***/\n/*{{{*/\n#messageArea {\nposition:absolute; top:0; right:0; margin: 0.5em; padding: 0.5em;\n}\n\n*[id='messageArea'] {\nposition:fixed !important; z-index:99;}\n\n.messageToolbar {\ndisplay: block;\ntext-align: right;\n}\n\n#messageArea a{\n text-decoration: underline;\n}\n\n#messageArea div {\n padding-bottom: 2px;\n}\n/*}}}*/\n/***\n!Popup /%==================================================%/\n***/\n/*{{{*/\n.popup {\n font-size: .9em;\n padding: 0.2em;\n list-style: none;\n margin: 0;\n}\n\n.popup hr {\n display: block;\n height: 1px;\n width: auto;\n padding: 0;\n margin: 0.2em 0em;\n}\n\n.popup li.disabled {\n padding: 0.2em;\n}\n\n.popup li a{\n display: block;\n padding: 0.2em;\n}\n/*}}}*/\n/***\n!Tabs /%==================================================%/\n***/\n/*{{{*/\n.tabset {\n padding: 1em 0.1em 0.1em 0.5em;\n}\n\n.tab {\n margin: 0em 0em 0em 0.25em;\n padding: 2px;\n}\n\n.tabContents {\n padding: 0.5em;\n}\n\n.tabContents ul, .tabContents ol {\n margin: 0;\n padding: 0;\n}\n\n.txtMainTab .tabContents li {\n list-style: none;\n}\n\n.tabContents li.listLink {\n margin-left: .75em;\n}\n/*}}}*/\n/***\n!Tiddler display rules /%==================================================%/\n***/\n/*{{{*/\n#displayArea {\n margin: 1em 17em 0em 14em;\n}\n\n\n.toolbar {\n text-align: right;\n font-size: .9em;\n visibility: hidden;\n}\n\n.selected .toolbar {\n visibility: visible;\n}\n\n.tiddler {\n padding: 1em 1em 0em 1em;\n}\n\n.missing .viewer,.missing .title {\n font-style: italic;\n}\n\n.title {\n font: Georgia, Time, serif;\n font-size: 1.6em;\n font-weight: bold;\n}\n\n.missing .subtitle {\n display: none;\n}\n\n.subtitle {\n font-size: 1.1em;\n}\n\n/* I'm not a fan of how button looks in tiddlers... */\n.tiddler .button {\n padding: 0.2em 0.4em;\n}\n\n.tagging {\nmargin: 0.5em 0em 0.5em 0.5em;\nfloat: right;\nclear: right;\ndisplay: none;\npadding: 0.25em;\n}\n\n.isTag .tagging {\ndisplay: block;\n}\n\n.tagged {\nmargin: 0em 0em 0.5em 0.5em;\nposition: relative;\ntop: -5px;\n}\n\n.tagging ,.tagged {\nfont-size: 0.9em;\n}\n\n.tagging ul, .tagged ul {\nlist-style: none;margin: 0.25em;\npadding: 0;\n}\n\n.tagged ul, .tagged ul li { \n display: inline;\n}\n\n.tagClear {\nclear: both;\n}\n\n\n.footer {\n font-size: .9em;\n}\n\n.footer li {\ndisplay: inline;\n}\n/***\n''The viewer is where the tiddler content is displayed'' /%------------------------------------------------%/\n***/\n/*{{{*/\n* html .viewer pre {\n width: 99%;\n padding: 0 0 1em 0;\n}\n\n.viewer {\n line-height: 1.4em;\n padding-top: 0.5em;\n}\n\n.viewer .button {\n margin: 0em 0.25em;\n padding: 0em 0.25em;\n}\n\n.viewer blockquote {\n line-height: 1.5em;\n padding-left: 0.8em;\n margin-left: 2.5em;\n}\n\n.viewer ul, .viewer ol{\n margin-left: 0.5em;\n padding-left: 1.5em;\n}\n\n.viewer table {\n border-collapse: collapse;\n margin: 0.8em 1.0em;\n}\n\n.viewer th, .viewer td, .viewer tr,.viewer caption{\n padding: 3px;\n}\n\n.viewer pre {\n padding: 0.5em;\n margin-left: 0.5em;\n font-size: 1.2em;\n line-height: 1.4em;\n overflow: auto;\n}\n\n.viewer code {\n font-size: 1.2em;\n line-height: 1.4em;\n}\n/*}}}*/\n/***\n''The editor replaces the viewer in the tiddler'' /%------------------------------------------------%/\n***/\n/*{{{*/\n.editor {\nfont-size: 1.1em;\n}\n\n.editor input, .editor textarea {\n display: block;\n width: 100%;\n font: inherit;\n}\n\n\n.editorFooter {\n padding: 0.25em 0em;\n font-size: .9em;\n}\n\n.editorFooter .button {\npadding-top: 0px; padding-bottom: 0px;}\n\n.fieldsetFix {border: 0;\npadding: 0;\nmargin: 1px 0px 1px 0px;\n}\n/*}}}*/\n/***\n!Misc rules /%==================================================%/\n***/\n/*{{{*/\n.sparkline {\n line-height: 1em;\n}\n\n.sparktick {\n outline: 0;\n}\n\n.zoomer {\n font-size: 1.1em;\n position: absolute;\n padding: 1em;\n}\n\n.cascade {\n font-size: 1.1em;\n position: absolute;\n overflow: hidden;\n}\n/*}}}*/

/***\n!Colors Used\n*@@bgcolor(#ccf): #ccf - Background blue@@\n*@@bgcolor(#18f): #18f - Top blue@@\n*@@bgcolor(#04b): #04b - Mid blue@@\n*@@bgcolor(#014):color(#fff): #014 - Bottom blue@@\n*@@bgcolor(#ffc): #ffc - Bright yellow@@\n*@@bgcolor(#fe8): #fe8 - Highlight yellow@@\n*@@bgcolor(#db4): #db4 - Background yellow@@\n*@@bgcolor(#841): #841 - Border yellow@@\n*@@bgcolor(#703):color(#fff): #703 - Title red@@\n*@@bgcolor(#866): #866 - Subtitle grey@@\n!Generic Rules /%==============================================%/\n***/\n/*{{{*/\nbody {\n background: #fff;\n color: #000;\n}\n\na{\n color: #04b;\n}\n\na:hover{\n background: #04b;\n color: #fff;\n}\n\na img{\n border: 0;\n}\n\nh1,h2,h3,h4,h5,h6 {\n font-family: Georgia, Times, serif;\n color: #703;\n background: #ccf;\n}\n\n.button {\n color: #014;\n border: 1px solid #fff;\n}\n\n.button:hover {\n color: #014;\n background: #fe8;\n border-color: #db4;\n}\n\n.button:active {\n color: #fff;\n background: #db4;\n border: 1px solid #841;\n}\n\n/*}}}*/\n/***\n!Header /%==================================================%/\n***/\n/*{{{*/\n.header {\n background: #04b;\n}\n\n.headerShadow {\n color: #000;\n}\n\n.headerShadow a {\n font-weight: normal;\n color: #000;\n}\n\n.headerForeground {\n color: #fff;\n}\n\n.headerForeground a {\n font-weight: normal;\n color: #ccf;\n}\n\n/*}}}*/\n/***\n!General tabs /%=================================================%/\n***/\n/*{{{*/\n\n.tabSelected{\n color: #014;\n background: #eee;\n border-left: 1px solid #ccc;\n border-top: 1px solid #ccc;\n border-right: 1px solid #ccc;\n}\n\n.tabUnselected {\n color: #fff;\n background: #999;\n}\n\n.tabContents {\n color: #014;\n background: #eee;\n border: 1px solid #ccc;\n}\n\n.tabContents .button {\n border: 0;}\n\n/*}}}*/\n/***\n!Sidebar options /%=================================================%/\n~TiddlyLinks and buttons are treated identically in the sidebar and slider panel\n***/\n/*{{{*/\n#sidebar {\n}\n\n#sidebarOptions input {\n border: 1px solid #04b;\n}\n\n#sidebarOptions .sliderPanel {\n background: #ccf;\n}\n\n#sidebarOptions .sliderPanel a {\n border: none;\n color: #04b;\n}\n\n#sidebarOptions .sliderPanel a:hover {\n color: #fff;\n background: #04b;\n}\n\n#sidebarOptions .sliderPanel a:active {\n color: #04b;\n background: #fff;\n}\n/*}}}*/\n/***\n!Message Area /%=================================================%/\n***/\n/*{{{*/\n#messageArea {\n border: 1px solid #841;\n background: #ffc;\n color: #014;\n}\n\n#messageArea .button {\n padding: 0.2em 0.2em 0.2em 0.2em;\n color: #014;\n background: #fff;\n}\n\n/*}}}*/\n/***\n!Popup /%=================================================%/\n***/\n/*{{{*/\n.popup {\n background: #18f;\n border: 1px solid #04b;\n}\n\n.popup hr {\n color: #014;\n background: #014;\n border-bottom: 1px;\n}\n\n.popup li.disabled {\n color: #04b;\n}\n\n.popup li a, .popup li a:visited {\n color: #eee;\n border: none;\n}\n\n.popup li a:hover {\n background: #014;\n color: #fff;\n border: none;\n}\n/*}}}*/\n/***\n!Tiddler Display /%=================================================%/\n***/\n/*{{{*/\n.tiddler .defaultCommand {\n font-weight: bold;\n}\n\n.shadow .title {\n color: #866;\n}\n\n.title {\n color: #703;\n}\n\n.subtitle {\n color: #866;\n}\n\n.toolbar {\n color: #04b;\n}\n\n.tagging, .tagged {\n border: 1px solid #eee;\n background-color: #eee;\n}\n\n.selected .tagging, .selected .tagged {\n background-color: #ddd;\n border: 1px solid #bbb;\n}\n\n.tagging .listTitle, .tagged .listTitle {\n color: #014;\n}\n\n.tagging .button, .tagged .button {\n border: none;\n}\n\n.footer {\n color: #ddd;\n}\n\n.selected .footer {\n color: #888;\n}\n\n.sparkline {\n background: #ccf;\n border: 0;\n}\n\n.sparktick {\n background: #014;\n}\n\n.errorButton {\n color: #ff0;\n background: #f00;\n}\n\n.cascade {\n background: #eef;\n color: #aac;\n border: 1px solid #aac;\n}\n\n.imageLink, #displayArea .imageLink {\n background: transparent;\n}\n\n/*}}}*/\n/***\n''The viewer is where the tiddler content is displayed'' /%------------------------------------------------%/\n***/\n/*{{{*/\n\n.viewer .listTitle {list-style-type: none; margin-left: -2em;}\n\n.viewer .button {\n border: 1px solid #db4;\n}\n\n.viewer blockquote {\n border-left: 3px solid #666;\n}\n\n.viewer table {\n border: 2px solid #333;\n}\n\n.viewer th, thead td {\n background: #db4;\n border: 1px solid #666;\n color: #fff;\n}\n\n.viewer td, .viewer tr {\n border: 1px solid #666;\n}\n\n.viewer pre {\n border: 1px solid #fe8;\n background: #ffc;\n}\n\n.viewer code {\n color: #703;\n}\n\n.viewer hr {\n border: 0;\n border-top: dashed 1px #666;\n color: #666;\n}\n\n.highlight, .marked {\n background: #fe8;\n}\n/*}}}*/\n/***\n''The editor replaces the viewer in the tiddler'' /%------------------------------------------------%/\n***/\n/*{{{*/\n.editor input {\n border: 1px solid #04b;\n}\n\n.editor textarea {\n border: 1px solid #04b;\n width: 100%;\n}\n\n.editorFooter {\n color: #aaa;\n}\n\n/*}}}*/

Dead code elimination is the process of removing code that cannot be executed. The [[recompiler|js.lang.Recompiler]] performs dead-code elimination implicitly, because once it has performed [[constant folding]], it recompiles branching constructs to always take a given branch if the test is a constant. since the flowgraph that results does not contain one of the branches, that dead code is eliminated.

A flowgraph is a data structure that represents the possible execution path of a function, much like a flowchart. However, it is represented as a graph so it can be explicitly manipulated by software. It is used by the [[recompiler|js.lang.Recompiler]] to perform many optimizations.

<<view-source js js/test.results>>

Meta is a namespace that contains some simple [[meta-continuations]] that are used frequently. They are useful for D.H.D Warren's [[tail-recursion modulo cons|http://foldoc.org/?tail+recursion+modulo+cons]] and similar techniques. See also [[js.cps.PartialMeta]].\n\n[[js/cps/Meta.js]]

A meta-continuation is a function that takes a [[continuation|continuations]] as an argument and returns a new continuation.

This package provides our runtime library with an [[Appel trampoline]]. \nFor efficiency reasons, it pollutes the global namespace with the following identifiers.\n* {{{appel_h}}} - a global stack frame count ticked down by the APPEL macro. \n* {{{appel}}} - the method that sets up and throws down to the Appel trampoline.\n[[js/cps/Appel.js]]\n\nThe associated header file registers the following {{{#defines}}} for common usage patterns.\n* {{{APPEL}}}\n* {{{APPEL_n}}}\n* {{{APPEL_expr}}}\n* {{{APPEL_n_expr}}}\n\n[[js/cps/Appel.h]]\n

These are still experimental and provide both blocking and [[non-blocking I/O]] to avoid requiring [[continuations]] on every call.\n\n[[js.io.BufferedIStream]]\n[[js.io.BufferedOStream]]\n[[js.io.IStream]]\n[[js.io.OStream]]\n[[js.io.PushbackIStream]]

Provides an interface analogous to java.io.InputStream. The differences are primarily due to a different language emphasis. Blocking and [[non-blocking|non-blocking I/O]] versions of most calls are available. Blocking calls require an explicit continuation to be passed.\n\n[[js/io/Istream.js]]

Provides an interface analogous to java.io.~OutputStream.\n\n[[js/io/OStream.js]]

Provides an interface analogous to java.io.~PushbackInputStream.\n\n[[js/io/PushbackIStream.js]]

[[js.test.Assert]]\n[[js.test.Simple]]\n\n

<<timeline modified 20>>\n\n[[more|Timeline]]\n

<<timeline modified>>

Partial [[meta-continuations]] directly modify the passed [[continuation|continuations]] directly in some cases. This means it is not necessarily safe to save the continuation and resume it multiple times. The benefit is that they can be used to incrementally reduce results in a variable attached to the continuation, so that when the continuation resumes it only has to perform one intermediate step. In effect they use half the stack space of recursion with the associated pure meta-continuations.\n\n[[js/cps/PartialMeta.js]]

Copyright 2006 Edward Kmett\n\nLicensed under the Apache License, Version 2.0 (the "License"); \nyou may not use this file except in compliance with the License. \nYou may obtain a copy of the License at \n\nhttp://www.apache.org/licenses/LICENSE-2.0 \n\nUnless required by applicable law or agreed to in writing, software distributed \nunder the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES \nOR CONDITIONS OF ANY KIND, either express or implied. See the License for \nthe specific language governing permissions and limitations under the License.

<<tagCloud systemConfig excludeSearch excludeLists excludeOptions js source glossary js.lang.Thread js.lang.Token related>>

<<allTags>>

Duff's Device is a programming [[idiom|idioms]] named for [[Tom Duff|http://www.iq0.com/]] that has been used traditionally for loop unrolling, and to provide a form of "poor man's coroutines" in the past. It is an old C programming trick that relies on the fact that code such as the following is legal in C.\n\n{{{\nint state = 0;\nswitch (state) { \ncase 0:\n do {\n ...\ncase 1:\n } while (<condition>);\ndefault:\n}\n}}}\n\nWe have to use an [[inverted Duff's Device]] in javascript.

This interface was created with [[TiddlyWiki|http://www.tiddlywiki.com/]] by [[Jeremy Ruston|http://www.tiddlywiki.com/#JeremyRuston]] and uses [[ccTiddly|http://sourceforge.net/projects/cctiddly/]] for the backend. \nIt uses the following extensions:\n* a [[view-source macro]]: by [[Edward Kmett]]\n* a [[smiley macro]] by [[Alan Hecht|http://www.personal.psu.edu/staff/a/c/ach12/tiddlywiki/extensions.htm]]\n* a [[tag-cloud macro]] by Clint Checketts, with contributions by Jonny Leroy and Eric Shulman\n* the [[broccoli-links macro]] by Clint Checketts and Simon Baird is used because so much of Java and JavaScript appear to be wiki words.\nFuthermore, some random tools have been put together to populate much of this documentation automatically.

/***\n|Name|Broccoli Links|\n|Created by|Clint Checketts and Simon Baird|\n|Location|http://checkettsweb.com/styles/themes.htm#%5B%5BBroccoli%20Links%5D%5D|\n|Summary|Provides options to disable auto-linking of camel case words and lets pretty links point to tiddlers rather than external files|\n|Current version|1.0 (20-Oct-2005)|\n!Description\nThis plugin changes the default behaviors of pretty links (links that display one text but link to a different tiddler like [[this|Welcome!]]). Pretty links that point to non-existent tiddlers are asumed to point to external files. This plugin allows you to disable that functionality, and instead point to the non-existent tiddler. This plugin also allows you to disable the auto wikification of camel case words (ThisIsACamelCaseWord). The name 'broccoli' was inspired by the Jeremy's [[photo|http://www.flickr.com/photos/jermy/10134618/]], and with a name like TiddlyWiki, extensions deserve silly names too (who names a broccoli Mervyn?).\n\nTo switch this functionality on or off, select the corresponding check boxes in the [[AdvancedOptions]] tiddler or right here:\n<<option chkPrettyLinksPointToFile>> PrettyLinksPointToFiles\n<<option chkAutoLinkCamelCase >> AutoLinkCamelCaseWords\n\nChange the following 'config.options' lines to true if you want the plugins off by default\n***/\n//{{{\nconfig.options.chkPrettyLinksPointToFile = true;\nconfig.options.chkAutoLinkCamelCase = false;\n\n\nconfig.shadowTiddlers.AdvancedOptions += "sn<<option chkPrettyLinksPointToFile>> PrettyLinksPointToFilessn<<option chkAutoLinkCamelCase >> AutoLinkCamelCaseWords";\n\n\nfor (var i=0;i<config.formatters.length;i++)\n if (config.formatters[i].name == "prettyLink"){\n config.formatters[i].handler= function(w)\n {\n var lookaheadRegExp = new RegExp(this.lookahead,"mg");\n lookaheadRegExp.lastIndex = w.matchStart;\n var lookaheadMatch = lookaheadRegExp.exec(w.source)\n if(lookaheadMatch && lookaheadMatch.index == w.matchStart && lookaheadMatch[2]) // Simple bracketted link\n {\n var link = createTiddlyLink(w.output,lookaheadMatch[1],false);\n w.outputText(link,w.nextMatch,w.nextMatch + lookaheadMatch[1].length);\n w.nextMatch += lookaheadMatch[1].length + 2;\n }\n else if(lookaheadMatch && lookaheadMatch.index == w.matchStart && lookaheadMatch[3]) // Pretty bracketted link\n {\n var e;\n if(store.tiddlerExists(lookaheadMatch[4]))\n e = createTiddlyLink(w.output,lookaheadMatch[4],false);\n else\n// Extra 'if' statement to decide whether to use point to files or not (by Clint)==========\n if (config.options.chkPrettyLinksPointToFile)\n e = createExternalLink(w.output,lookaheadMatch[4]);\n else\n e = createTiddlyLink(w.output,lookaheadMatch[4],false);\n// end additions ================================================\n w.outputText(e,w.nextMatch,w.nextMatch + lookaheadMatch[1].length);\n w.nextMatch = lookaheadMatch.index + lookaheadMatch[0].length;\n }\n }\n}\n\n\n\nfor (var i=0;i<config.formatters.length;i++)\n if (config.formatters[i].name == "wikiLink"){\n config.formatters[i].handler= function(w){\n// Check to see if you want the wirds turned into links (by Clint) ===========\n if (!config.options.chkAutoLinkCamelCase){\n w.outputText(w.output,w.matchStart,w.nextMatch);\n return false;\n }\n// end additions ==========================================\n var preRegExp = new RegExp(config.textPrimitives.anyLetter,"mg");\n var preMatch = null;\n if(w.matchStart > 0)\n {\n preRegExp.lastIndex = w.matchStart-1;\n preMatch = preRegExp.exec(w.source);\n }\n if(preMatch && preMatch.index == w.matchStart-1)\n w.outputText(w.output,w.matchStart,w.nextMatch);\n else if(w.matchText.substr(0,1) == config.textPrimitives.unWikiLink)\n w.outputText(w.output,w.matchStart + 1,w.nextMatch);\n else\n {\n var link = createTiddlyLink(w.output,w.matchText,false);\n w.outputText(link,w.matchStart,w.nextMatch);\n }\n }\n}\n//}}}

/***\n| Name:|QuickOpenTagPlugin|\n| Purpose:|Makes tag links into a Taggly style open tag plus a normal style drop down menu|\n| Creator:|SimonBaird|\n| Source:|http://simonbaird.com/mptw/#QuickOpenTagPlugin|\n| Requires:|TW 2.x|\n| Version|1.1 (7-Feb-06)|\n\n!History\n* Version 1.1 (07/02/2006)\n** Fix Firefox 1.5.0.1 crashes\n** Updated by ~BidiX[at]~BidiX.info\n* Version 1.0 (?/01/2006)\n** First release\n\n***/\n//{{{\n\nwindow.createTagButton_orig_mptw = createTagButton;\nwindow.createTagButton = function(place,tag,excludeTiddler) {\n var sp = createTiddlyElement(place,"span",null,"quickopentag");\n createTiddlyLink(sp,tag,true,"button");\n var theTag = createTiddlyButton(sp,config.macros.miniTag.dropdownchar,config.views.wikified.tag.tooltip.format([tag]),onClickTag);\n theTag.setAttribute("tag",tag);\n if(excludeTiddler)\n theTag.setAttribute("tiddler",excludeTiddler);\n return(theTag);\n};\n\nconfig.macros.miniTag = {handler:function(place,macroName,params,wikifier,paramString,tiddler) {\n var tagged = store.getTaggedTiddlers(tiddler.title);\n if (tagged.length > 0) {\n var theTag = createTiddlyButton(place,config.macros.miniTag.dropdownchar,config.views.wikified.tag.tooltip.format([tiddler.title]),onClickTag);\n theTag.setAttribute("tag",tiddler.title);\n theTag.className = "miniTag";\n }\n}};\n\nconfig.macros.miniTag.dropdownchar = (document.all?"▼":"▾"); // the fat one is the only one that works in IE\n\nconfig.macros.allTags.handler = function(place,macroName,params) {\n var tags = store.getTags();\n var theDateList = createTiddlyElement(place,"ul",null,null,null);\n if(tags.length === 0)\n createTiddlyElement(theDateList,"li",null,"listTitle",this.noTags);\n for (var t=0; t<tags.length; t++)\n {\n var theListItem =createTiddlyElement(theDateList,"li",null,null,null);\n var theLink = createTiddlyLink(theListItem,tags[t][0],true);\n var theCount = " (" + tags[t][1] + ")";\n theLink.appendChild(document.createTextNode(theCount));\n\n var theDropDownBtn = createTiddlyButton(theListItem," "+config.macros.miniTag.dropdownchar,this.tooltip.format([tags[t][0]]),onClickTag);\n theDropDownBtn.setAttribute("tag",tags[t][0]);\n }\n};\n\n\nsetStylesheet(\n ".quickopentag { margin-right:.1em; border:0px; padding:2px; padding-right:0px; padding-left:1px; }\sn"+\n ".quickopentag .tiddlyLink { padding:1px; padding-left:1px; }\sn"+\n ".quickopentag a.button { padding:0px; padding-left:0px; padding-right:0px;}\sn"+\n "a.miniTag {font-size:150%;}\sn"+\n "",\n "QuickOpenTagStyles");\n\n//}}}\n\n/***\n<html>⊻ ⊽ ⋁ ▼ ▾</html>\n***/

This namespace is for aspect-oriented programming, which is remarkably easy to do in javascript and is effective at crosscutting concerns.\n\n[[js.aop.Aspect]]\n[[js.aop.Observable]]\n[[js.aop.PointCut]]\n\n

Roughly analogous to the {{{aspect}}} keyword in AspectJ, an Aspect object represents a concern that cuts across a many classes. See [[js.aop.Observable]] for a simple example.\n\n[[js/aop/Aspect.js]]

A PointCut represents a wildcard match of methods and properties to which we can apply [[advice]]. This serves the same general function as the {{{pointcut}}} keyword in AspectJ, although the syntax and idioms for applying advice to one differ significantly.\n\nSince not all javascript implementations support getters and setters, we limit ourselves to supporting only method advice. The following forms of advice are supported.\n* {{{before}}} - called before a cut method is invoked either as a constructor or method.\n* {{{after}}} - called after a cut method runs, regardless of if it returns or throws\n* {{{after_return}}} - called after a cut method returns normally\n* {{{after_throw}}} - called after a cut method throws\n* {{{around}}} - called in place of a cut method. \n\nThe one thing to note is that an advised method cannot be called as a constructor. It should generate a subclass, but there is no way to safely construct the prototype chain in all cases.\n\n[[js/aop/Aspect.js]]

This simple [[aspect]] can be used to extend existing prototypes to make them support the [[js.dom.Event]] interface with minimal changes. By default when weaved onto an object or prototype it replaces all set methods with equivalent methods that subsequently trigger a {{{change}}} event.\n\n\nSee [[js/aop/Observable.t]] for an example.\n\nTodo: make a more robust Observable class that allows the use of {{{preventDefault}}} and {{{stopPropagation}}} by using around advice and provides bubbling and capturing support. This aspect was intended more as a technology demonstration than a practical bit of code.\n\n[[js/aop/Observable.js]]

At present the runtime library consists of \n* the contents of [[js.cps]] except for the [[meta-continuations]] \n* a handful of classes from [[js.util]] used to support the timed blocking.\n* the relevant patches from [[js.native]] for the target platform set.

In operating system parlance, the quantum is the amount of time a given process or [[thread|js.cps.Thread]] can run before being pre-empted by the kernel. In our case, it is the number of stack frames allowed to be created before the thread gives up control and another thread takes over.

Internally, the [[recompiler|js.lang.Recompiler]] uses an [[inverted Duff's Device]] and [[flowgraph flattening]] to minimize the length of [[lexical scope chains]] and an [[Appel trampoline]] to work around the lack of [[tail-call optimization]] in javascript. The recompiler performs [[constant folding]] and [[simplifies|flowgraph simplification]] the [[flowgraph]] of the [[syntax tree|js.lang.Token]] returned by the [[parser|js.lang.Parser]] to reduce the size of the resulting code. The output expects to run in the presence of a small [[runtime library]].

Provides a simple c style assert macro.\n\nThese exceptions should NOT be relied upon. They may be conditionally compiled out.\n\n* {{{assert(condition)}}} - if (!condition) throws an exception indicating that something has gone wrong.\n* {{{pre(condition)}}} - if (!condition) throws an exception indicating a failure on the behalf of the calling function to comply with the usage contract.\n* {{{post(condition)}}} - if (!condition) throws an exception indicating that the failure is on the behalf of the called function.\n\nAs in C, these are not functions. They are #defines. Therefore calling member functions with the names assert, pre or post will also blow up in your face. You have been warned.

Clones the interface for perl's Test::Simple module.\n\n* {{{plan(count)}}} - how many tests are planned.\n* {{{ok(test,name,comments)}}} - the current test passes or fails based on test. Optionally you may specify a name and comments.\n* {{{todo(name,comments)}}} - makes the current test fail, but marks that the current test is expected to fail. \n* {{{skip(name,comments)}}} - skips the current test.\n\nThe output it sent out via {{{print}}}.\n\nTodo: crash if attempting to run more tests than planned.\n

A toy namespace for playing with monads in javascript. The implementation here assumes functions take only one parameter, so you have to [[curry]].\n\n[[js.monad.Base]]\n[[js.monad.Boxed]]\n[[js.monad.Exception]]\n

An abstract base class for monads. You have to overload at least the {{{star}}} method or both {{{map}}} and {{{join}}}. This works around the lack of function polymorphism on base types by - drum roll please - assuming that all functions deal with Objects and that other primitive types do not exist. Descendants serve the role of monad data types, though they may have to subclass themselves to effectively implement the interface.\n\n[[js/monad/Base.js]]

A simple monad for bundling up an object into a box. This enables function polymorphism.\n\n[[js/monad/Boxed.js]]

A simple monad for dealing allowing functions to return exceptions. Possibly useful in emulating exceptions on MSIE 5.2 on the Macintosh, but its just another standard monad test case.\n\n[[js/monad/Exception.js]]

October 11\n* Picked up a new domain name.\n\nOctober 8\n* Started writing an x86-64 assembler as a DSL in haskell. Currently playing with the internal representation to get something that will allow me to take advantage of the myriad optimizations available in just selecting the best opcode for the job.\n\n{{{\nmymain = assemble $ do\n section ".bss"\n foo <- resd 1024\n section ".text"\n main <- proc "main"\n xor eax eax\n mov ebx [foo .+ ecx]\n add ebx 12\n mov [foo .+ ecx] ebx\n ...\n ifnz $ do\n mov ecx [eax .+ ebx.*4 .+ foo]\n -- or more efficiently: cmovnz ecx [eax + ebx.*4 .+ foo]\n ...\n jmp main\n}}}\n\nOctober 1\n* Received the information I was needing for my Javascript compiler from [[Dave Herman|http://calculist.blogspot.com/]] at ICFP. \n\n

[[ICFP06 Universal Machine]]

(This has been excerpted from my old [[Harmless Algorithms]] articles, and its contents may well be out of date)\n\nThe s-buffer algorithm is a data structure that can facilitate visibility computations in a 3d scene, that is described in [[Paul Nettle's s-buffer FAQ|http://www.gamedev.net/reference/articles/article668.asp]], and is a good starting place for looking at [[fine-occlusion culling]].\n\nA classic s-buffer span-converts a polygon into a list of line segments. You have 1 bucket per scanline, and in that scanline you maintain a structures or class for an individual span which generally looks like:\n\n{{{\n class classic_sbuffer_span {\n float start_x;\n float end_x;\n float start_ooz; // 1/z, d(1/z)/dx\n\n ... // gradient setup for u and v, etc\n\n classic_sbuffer_poly * poly;\n classic_sbuffer_span * next;\n };\n}}}\n\nIn your polygon object you contain information that is invariant over the entire polygon (i.e. d(1/z)/dx, d(1/z)/dy) and as you insert spans into the buffer you clip against existing spans. How this is done depends on whether or not you can depend on the polygons going into the s-buffer to be sorted or not.\n\nInterpenetrating Version:\n\n Given the truly general case, which would allow for interpenetrating spans and spans being inserted out of order, your inner loop for inserting a given span not only has to look for what spans your introduced polygon overlaps, but whether the interpolated 1/z regions overlap, and if they do, if the intersection is on or off of the existing span and the inserted span. The number of special cases you need to handle in your inner insertion loop can grow prohibitive. Also since you can later occlude a polygon that seemed like it was going to be in front, you have to do all of your rendering in a post process or you risk unnecessary overdraw. \n\nNon-Interpenetrating Version:\n\n Given the slightly less general case of assuming that there are no interpenetrating while still inserting spans out of order, you can handle most static worlds. Your inner loop simplifies tremendously compared to the more general algorithm. \n\nImmediate Rendering Version:\n\n Next option. Instead of storing the gradient information, or for that matter any information about the polygon in a span other than its starting and ending x position, and its starting z and d(1/z)/dx, you can make the assumption that whatever is feeding you polygons is doing so in a 'roughly' front to back order. If this is the case you can render each span when you clip it. This greatly shrinks the size of the individual span structures (to less than the size of a cache line), which can improve your performance quite significantly. Now you no longer have a second pass through a fairly large data structure, but you risk some overdraw in the case of an imperfectly sorted scene and software rendering. This algorithm also has the advantage that it renders in a texture coherent fashion.\n\n This data structure looks more like:\n\n{{{\n class immediate_sbuffer_span {\n float start_x;\n float end_x;\n float start_ooz;\n float doozdx;\n immediate_sbuffer_span * next;\n };\n}}}\n\n

{{{\ndarcs get http://slipwave.info/haskell/thash\n}}}\n\n[[Data.THash|haskell/thash/dist/doc/html/Data-THash.html]] [ [[hs|haskell/thash/src/Data/THash.hs]] ]\n[[Data.THash.THT|haskell/thash/dist/doc/html/Data-THash-THT.html]] [ [[hs|haskell/thash/src/Data/THash/THT.hs]] ]\n[[Data.Hashable|haskell/thash/dist/doc/html/Data-Hashable.html]] [ [[hs|haskell/thash/srcData/Hashable.hs]] ]

The haskell code below is available via Darcs under a BSD license.\n \n<<tabs txtHaskellNamespaces Data 'Browse the Data namespace' Data Type 'Browse the Type namespace' Type Assembler 'Browse the Assembler namespace' Assembler>>

<<view-source js js/lang/Interpreter.js>>

\nA simple [[Universal Machine|ICFP06 Universal Machine]] (see the [[ICFP Contest|http://icfpcontest.org/]]). Don Stewart has been [[benchmarking|http://www.cse.unsw.edu.au/~dons/um.html]] various implementations:\n\n[[um.c|/icfp/um.c]]\n\nA [[JIT]] based implementation in Haskell that generates Haskell code on the fly from UM code.\n\n[[icfp/jit/API.hs|icfp/jit/API.hs]]\n[[icfp/jit/JIT.hs|icfp/jit/JIT.hs]]\n[[icfp/jit/Main.hs|icfp/jit/Main.hs]]\n\nA hybrid interpreter/JIT based implementation in Perl that generates C code on the fly from UM code. Runs pretty fast.... the second time you use it on something.\n\n[[icfp/jit/jit.pl|icfp/jit/jit.pl]]\n[[icfp/jit/jit.h|icfp/jit/jit.h]]\n[[icfp/jit/Inline/C/Psychic.pm|icfp/jit/Inline/C/Psychic.pm]]\n\n

Back at the turn of the century, I wrote a series of articles under the label [[Harmless Algorithms|http://flipcode.com/harmless]] on visibility problems in 3d graphics for the now defunct website [[flipCode|http://flipcode.com/]]. I retained the copyright, so I have chosen to post the text of them here in a more navigable form. I will be adding the content to this site as I find time.\n\nI've only posted up the [[fine-occlusion culling]] algorithms and the [[boilerplate pattern]] so far.

(This list has been excerpted from my old [[Harmless Algorithms]] articles, and its contents may well be out of date)\n* [[s-buffer]]\n* [[binary span tree]]\n* [[c-buffer]]\n* [[active edge list]]\n* [[active edge heap]]\n* [[triage masks]]\n* [[beam tree]]\n\nThese algorithms do not in-and-of-themselves solve visibility problems; they are merely ways to take polygons from a pretty good guess of what is visible and determine if they are indeed visible. When combined with some on-the-fly gross culling/vis system they can be used to build a viable engine. Next time I'll review some of the various visibility systems, which of these that they will work with, and the relative merits and flaws of each.\n\nIndeed all of the algorithms above can potentially run afoul of problems when used in conjunction with hardware; if your edge conversion doesn't exactly correspond with the algorithm used by the graphics card you may wind up with fragments of polygons that your algorithm says aren't visible. The [[beam tree]] avoids one stage in which this error usually crops up, but it doesn't shrink as quickly when polygons are added as the [[c-buffer]] structure.\n\nWhich of these you use (or if you use another) should probably be determined by what gross culling and visibility determination algorithm you are using and whether or not you are writing for hardware, software, or a hybrid game engine.

Tom Hammersley devised this algorithm and used to have a detailed description and source code up on his now non-existant website. The span tree is very similar to the classic binary search tree algorithm.\n\nThe first assumption made is that all polygons will be coming to this algorithm in presorted order as from a conventional BSP tree or a recursive portal engine.\n\nNow you can only handle input that comes in perfect front-to-back order. Certain portal algorithms and BSP key sorting can provide this, but generally they do not provide this for dynamic actors. This generally means that dynamic objects have to be moved off into another stage of the pipeline in order to use this algorithm. This is not necessarily a bad thing depending on the purpose for the engine in question.\n\nDynamic objects would then need to be z-buffered in, or clipped and then inserted into the BSP before this stage. For hardware, inserting all of the objects which are in visible BSP nodes directly into the zbuffer is generally the most expedient approach.\n\nThe fundamental change is switching to a binary tree based structure:\n\n{{{\n class bst_span {\n float start_x, end_x; \n bst_span * next, * prev;\n };\n}}}\n\nInsertions clip their way down the tree. If you are lucky, the tree may reduce the number of spans visited as you clip your node.\n\nRelative to the more general [[s-buffer]] algorithm, its primary speed up comes from the assumption of front-to-back order reducing the amount of clipping, than from any gains made by the tree itself.\n\nThe problems I see with this algorithm is that its really just not seeing the forest for the trees. (no pun intended) In general, the goal of this algorithm, that is, the reduction of the number of spans visited during the clipping and display of a given span is valid, but I have found that in practice (for me) a simpler algorithm (the c-buffer algorithm which follows) gives better results.\n\nAn additional trait that is important in several of these algorithms, that this approach provides, is the ability to check if a polygon silhouette would be visible (span convert the polygon as if you were going to insert into the tree, quit when you get your first visible sub span). You can perform this operation on the [[s-buffer]] algorithm, but not without a great deal of z computations.\n

What I dubbed a coverage buffer (c-buffer for short) is another constrained variant on the [[s-buffer]] algorithm for [[fine-occlusion culling]]. Again, like the [[binary span tree]] we will make the assumption that you can get your polygons to this stage of the pipeline in BSP front-to-back order.\n\nYour span definition shrinks to:\n{{{\n class cbuffer_span {\n float start_x, end_x;\n cbuffer_span * next;\n };\n}}}\nThen walk left to right through the linked list per scanline. As you walk if you clip on an existing node, congeal with it by just lowering its minimum x value or raising its maximum x value, if you are clipped on both sides, remove the second node, and expand the first one to its end boundary\n{{{\n Example 1 \n Poly to draw -------------|XXXXXXXXXXXX|----------- \n Existing Span -----|XXXXXXXXXXXX|------------------- \n Rendered portion ------------------|XXXXXXX|----------- \n New Span in cbuffer -----|XXXXXXXXXXXXXXXXXXXX|----------- \n\n Example 2 \n Poly to draw ---------|XXXXXXXXXXXX|--------------- \n Existing Spans ------|XXXXX|------|XXXXXX|----------- \n Rendered Portion ------------|XXXXXX|------------------ \n New Span in cbuffer ------|XXXXXXXXXXXXXXXXXXX|----------- \n\n Example 3 \n Poly to draw ---|XXXXXXXXXXXXXXXXXX|--------------- \n Existing Spans ------|XXXXX|------|XXXXXX|----------- \n Rendered Portions ---|XX|-----|XXXXXX|------------------ \n New Span in cbuffer ---|XXXXXXXXXXXXXXXXXXXXXX|----------- \n}}}\nNotice that examples 2 and 3 actually reclaimed a span data structure for use in later spans. As the screen fills up the coverage buffer, this algorithm actually lowers the number of spans in circulation, thus improving performance. The reason that it works is because with perfect front-to-back ordering, you do not care about the z information at all in the span buffer; you simply need to know the portions of the screen which have been covered. You know by definition of a bsp tree that the portions already rendered cannot be concealed by polygons further away in the tree. Render the portions as you walk the span buffer, and clip your polygon fragment. This way you do not need to retain any of the clipped values in the span buffer because you have already rendered them and filled in your z-buffer if you so choose.\n\nNotice also that now there is no longer a correlation between the number of spans and the call to the rasterization routine, yet you still retain a single draw per pixel. When the scene is filled, you end up with a single fragment per scanline.\n\nThis algorithm also shares the desirable quick would-this-polygon-be-visible test as the [[binary span tree]].\n\nA variant proposed by Chris Babcock:\n\nIn practice it is better to start with one span per scanline, and redefine your spans to be areas where there are no polygons. In this case you start with one span and converge an empty list by eating away pieces of it.\n\nHere's the "is visible" test for this variant:\n{{{\n bool test_visible(cbuffer_line & line,int start_x,int end_x) {\n cbuffer_span *scan = line.spans;\n while (scan) {\n if (end_x < scan->start_x) return false;\n if (start_x <= scan->end_x) return true;\n scan = scan->next;\n }\n return false;\n }\n}}}

There are at least two very good descriptions of this algorithm floating around in Michael Abrash's Black Book (I can't recall if it was in the earlier Zen of Graphics Programming) and in Computer Graphics: Principles and Practice; because of this, I will just summarize the algorithm's relative strengths and weaknesses. An active edge list allows insertion of the polygons in any order, but requires a two-pass walk since you have to build up the data structure and then afterwards you walk across the screen in a scanline coherent order while drawing.\n\nIts strength resides in the fact that it scales better to higher resolutions than most of the algorithms above for software. Just like the first arbitrary order [[s-buffer]] variants , you can throw any old polygon at it and this stage of the pipeline will not choke.\n\nUnfortunately it renders in a scanline coherent manner, which generally causes a speed hit because almost all of your texture accesses are incoherent. Also, the two-stage rendering structure means you wind up building up the structure, having it go out of cache while you walk the scene and then have to walk through it all over again.\n\nOther concerns include that there are many data structures built up here, a linked list per scanline of edges that begin and end, a structure representing all of the information needed to rasterize a given polygon, and then the sorted list of edges that you use as you walk across the scanline, and the small list of polygons that overlap the current pixel. Each one unto themselves is fairly minor, but it does add significant complexity to an implementation.\n\nThis algorithm does not possess a corollary to the visible polygon test, which means that every potentially visible polygon needs to be inserted into the structure that is walked in the second stage. Depending on how conservative of a set your gross culling and occlusion algorithm is this may or may not be a problem (Witness quake which uses this algorithm).

(Originally posted to [[flipCode|http://flipcode.com]] as [[Harmless Algorithms]] Issue 3)\n\nIn an article on GameSpy, Tim Sweeney sought to introduce a new concept he wanted in object oriented programming called virtual classes. The pattern I describe below can be used to provide this concept, and is very useful in cases where you need to generate a facade over a wide number of implementations that don't cleanly break down to one-class per implementation. Examples include graphs, a networking layer, your rendering api, and your sound subsystem. In each of these you have multiple related classes nodes and edges, sockets and ports, textures and models, sound snippets, etc that need to perform operations behind the scenes and often need to tie back to managers to actually do things. The Java answer to this is to define a series of purely abstract interfaces (black box inheritance) and implement the connections in each set of implementations separately. This approach generally leads to code duplication as each driver has to generate a bunch of boilerplate code. The pattern below shows a way to make a template perform the busy work you usually achieve with cut & paste coding for these 'fast' implementations.\n\nI call this the 'Boilerplate' pattern, and the first time that I saw this outside of my own code was in the Finite State Machines chapter of 'C++ Gems' by Stanley Lippman. (ISBN: 0135705819) The treatment of this pattern given by 'C++ Gems' is different than mine and if you have trouble with my half-baked code below you may want to pick it up. In fact you may want to pick it up yourself after of course you purchase the Design Patterns book if you have not already done so. This pattern twists the eye and seems deceptively simple the first couple of times you look at it, but without it you can wind up writing a lot of duplicate code.\n\nI'll attempt to demonstrate with a skeletal interface that could be the start of a rendering API. Obviously in a fully fleshed out rendering API you'd have a lot more methods and probably a lot more classes, meshes, clippers, visibility and occlusion structures come to mind.\n{{{\n #ifndef INCLUDED_RENDERER\n #define INCLUDED_RENDERER\n \n class Texture {\n public:\n virtual ~Texture() {}\n virtual void makeCurrent()=0;\n };\n \n class Renderer {\n public:\n virtual Texture * loadTexture(const char * name);\n };\n \n #endif\n \n Figure 1. renderer.h \n}}}\n\n\nAll is well and good, given a {{{Renderer}}}, you can ask for a {{{Texture}}}, and have that {{{Texture}}} make itself current. If your {{{Renderer}}} had a set of other operations for rendering polygons and managing matrices, hacking out code to use this interface looks like a straightforward proposition.\n\nUnfortunately implementing all of your {{{Renderer}}} and {{{Texture}}} classes for different 3D APIs could lead to the onset of repetitive strain injury and if you now have to deal with several duplicate implementations of the behind the scenes linkages between the {{{Texture}}} class and the {{{Renderer}}}. Admittedly in this contrived example we're probably only talking about 3 Implementations so its not so bad, but envision a case where you may have 50-100 implementations, perhaps your monster AI if this all seems like too much work.\n\nThe real evil in cut & paste code comes when you discover a bug. If the code that you cut&pasted in 30 places to manage a linked list leaks memory whenever you delete a node, you may wind up discovering and fixing each of these mistakes as you find them rather than fixing them all at once, simply because you're apt to forget all the locations you pasted the code to, so OOP came around and people started generalizing algorithms and structures and the C++ Standard Template Library was born, which had all sorts of handy-dandy containers that worked of void*'s to juggle and sort and mangle your objects, these ran afoul of the fact that void*'s could be cast to anything and miscasting is a source of a good deal of bugs. The Standard Template Library implements these algorithms and structures using templates, trading a bit of compiler time for type checking your code.\n\nContinuing with the example, I'm going to use templates that change who they inherit from based on a passed in parameter. This is a sneaky way to avoid the overhead of writing repetitive proxy code for mixin classes and other such busywork.\n\n{{{\n #ifndef INCLUDED_RENDERER_TEMPLATES\n #define INCLUDED_RENDERER_TEMPLATES\n \n #include "renderer.h"\n \n template <class Baseclass, class Renderer> class TextureTemplate : public Baseclass {\n private:\n Renderer * m_renderer;\n public:\n TextureTemplate(Renderer & rend, const char * name) : m_renderer(&rend), Baseclass(name) { }\n ~TextureTemplate() { \n m_renderer->unregisterTexture(this);\n }\n void makeCurrent() { \n m_renderer->makeCurrent(this);\n }\n };\n \n template <class Baseclass, class TextureBase> class RendererTemplate : public Baseclass {\n public:\n typedef TextureTemplate<TextureBase,Baseclass> MyTexture;\n \n Texture * loadTexture(const char * name) {\n return new MyTexture(this,name)\n }\n };\n \n #endif\n \n Figure 2. renderer_templates.h \n}}}\nNow we've got 2 classes and 2 templates that don't seem to do anything. The templates lie in a separate header because we don't want to trouble anyone who is just using the interface with templates that are only useful for implementing the interface.\n{{{\n #ifndef INCLUDED_GLRENDERER\n #define INCLUDED_GLRENDERER\n \n #include "renderer_templates.h"\n \n class GLTextureImpl : public Texture {\n public:\n GLTextureImpl(const char * name, blah blah blah) {\n load up texture using opengl...\n }\n virtual ~GLTextureImpl() {}\n };\n \n class GLRendererImpl : public Renderer { \n public:\n void makeCurrent(GLTextureImpl & texture) {\n ... do gl texture stuff here ...\n }\n void unregisterTexture(GLTextureImpl & texture) { \n ... do gl texture stuff here ...\n }\n \n };\n \n typedef TextureTemplate<GLTextureImpl,GLRendererImpl> GLTexture;\n typedef RendererTemplate<GLRendererImpl,GLTextureImpl> GLRenderer;\n \n #endif\n \n Figure 3. glrenderer.h\n}}}\n\n\nThe templates are initially a fair chunk of work, but the work pays off as you add implementations by reducing mindless repetitive tasks and letting you focus on real work. The templates do not affect your overall compile time appreciably as they are included only in the individual source files that have to do with implementing your Renderer. You gain implementation while maintaining type safety by sandwiching your code between the templated typed code and the abstract implementation. Inheritance allows you to let calls trickle down the hierarchy and the template allows calls to be made 'up' the hierarchy without the virtual function call overhead.\n{{{\n Interface \n Implementation : public Interface\n TemplateWrapper<Implementation> : public Implementation\n \n Figure 4. Hierarchy \n}}}\nCombined with other patterns like the Singleton and Factory you can reduce the repetitiveness of your code. While this may have perverse effects when a customer or old fashioned manager rates you by lines of code written, it can make for much more maintainable code and gain you the respect and fear of your peers. =)\n

This is an algorithm I used briefly in a software rendering engine that I found useful enough to relate. Its goal was to address the number of data structures floating around in the [[active edge list]] structure by using a binomial heap.\n\nLike an active edge list, this structure does not require front to back sorting, nor does it even gain anything from it.\n\nFor those not familiar with a binomial heap, I refer you to any of Robert Sedgewick's books on algorithms (or for that matter almost any algorithm text). A binomial heap is also known as a priority queue, and is used for the heap sort.\n\nA heap is a form of binary tree that is always packed in memory (which is very good for cache coherence). The basic change is to use either an xy pair or a screen coordinate as a key for a node in the binomial heap. Initialize each edge with the position along each edge at its top y coordinate.\n\n{{{\n class aeh_edge {\n int type; // start or end of a span - 1 or -1.\n float x, ooz;\n int y, last_y;\n float dxdy, doozdx, doozdy;\n aeh_poly * poly;\n };\n}}}\n\nOne property provided by a binomial heap is the ability to quickly extract the entry with the highest priority (or lowest key). Using the key as the current xy value of a given entry, you will automatically start on the top scanline with the beginning of the first span by extracting the top node of the heap.\n\npsuedo-code:\n\n{{{\n while (heap isnt empty) {\n look at node at top of heap\n if its the start of an edge add poly to the list of current spans. \n else remove poly from the list of current spans.\n\n increase y, if its less than last_y then\n add dxdy and doozdy to the x and ooz values and reinsert (you can\n quickly reinsert the top node of a binomial heap by decreasing its\n priority and then verifying the heap sorting property.)\n\n draw from the coordinate stated to the node at the top of the heap.\n }\n}}}\n\nThere are fewer data structures than in the case of an AEL. You no longer have the separate buckets per scanline for insertion and deletion of nodes on each pass. The initial insertion cost of each of the edges is higher than for an AEL and you are still stuck with a two-pass data structure. On the other hand, you aren't stuck iterating through the list of active edges for every scanline to insert and delete each one that begins or ends on a given scanline.\n\nI present this algorithm as an example of the trade-offs involved in different approaches. This lacks a quick polygon visibility just test like the [[active edge table]] method unfortunately does.

Ned Greene of Apple published a very interesting and often overlooked [[paper|http://www.cs.princeton.edu/courses/archive/fall02/cs526/papers/greene93.pdf]] on the subject of a variant on Warnock's algorithm (quadtree subdivision of the view) that used what he called triage masks. Rather than present his work here, I'll simply provide a pointer to the original document, a brief overview, and compare and contrast it with the other algorithms above.\n\nA triage mask is a hierarchial form of coverage buffering that uses binary bit operations to check for occlusion or probable occlusion. In his paper, Ned Greene used 8x8 masks which required 64 bit binary operations. The intersection or union of 3 or more masks provides the silhouette at a given depth of this hierarchial occlusion structure. In short the triage mask data structure enables you to quickly evaluate if a polygon is visible or not with a few binary operations, and if the resolution of that query is insufficient to find out what subcels you need to zoom in on and evaluate to determine whether or not the polygon is visible.\n\nThe requirements are the same as for the [[binary span tree]] and for the [[c-buffer]]: Perfect front to back pre-sorting.\n\nThe good part of this algorithm is that as your scene fills up you can quickly reject whole polygons with a handful of binary operations.\n\nProblems include that the preprocess of generating the masks is easy to mess up and I haven't yet found a way to do the edge of cel intersections as fast as I'd like to. Scaling up in multiples of 8x8 is somewhat scary, given your virtual screen resolutions for this go from 8x8 to 64x64 to 512x512 to 4096x4096, and while that is reassuring for future video resolutions, under 1024x768 or so this algorithm seems to be, for me, a net loss.\n\nThis algorithm supplies a very good spot checked polygon visibility test.

Unlike the other [[fine-occlusion culling]] algorithms, this algorithm takes place in object space. This means that you can get away cheaper on the polygons that you do not display. Another concern not addressed by the methods above is the matter of subpixel accuracy and conservative estimation. This algorithm is also applicable for shadow casting light sources, but that is another topic for another day.\n\nA beamtree, as I describe herein, should really be thought of as a 3 dimensional structure. It really is just a specialized form of BSP tree. In a beamtree all planes pass through the origin (the eye point). Other than that it subdivides the view as you walk from front to back through the scene into drawn and undrawn sections, much like a solid BSP can divide between solid portions of the map and air. Since all planes pass through the origin, their 'd' component is always 0, which means you do not need to normalize the planes during beamtree generation because when you use the distances from the plane for linear interpolation, the magnitude of the plane 'normal' is irrelevant and cancels itself out.\n\nIn short, the plane passing through two points in the scene and the origin is:\n{{{\nplane' = (v1-eye) cross (v2-eye) \n}}}\n\nthen to get the side of that plane any point is on:\n{{{\nside = the sign of ((vertex-eye) . plane') \n}}}\n\nFor a given viewpoint, the beamtree is used by putting in place 4 'slabs' representing the left, right, top and bottom of the viewing fustrum.\n\nThis gives you a degenerate tree like:\n\n{{{\n left\n / \s\nsolid right\n / \s\n solid top\n / \s\n solid bottom\n / \s\n solid open\n}}}\n\nThe above use of an arbitrary plane and its opposite is necessary, because otherwise the first plane you inserted into the beamtree would cause half of the field of view from the light source to fall into shadow.\n\nWhen you insert a polygon, you walk down the beamtree with all of the points in your polygon, visiting each side that the points lie on.\n\nYou do not need to define the leaf nodes. Anything that opens to an empty 'left' child is solid anything opening to an empty 'right' child is open and unrendered. so think of left and right as 'drawn/undrawn' or vice versa.\n\nYour recursive insertion routine would look something like:\n\n{{{\n #define EPSILON 1.0e-6\n\n int convervative_signof(float value) {\n int result;\n if (value < -EPSILON) return 1;\n else if (value > EPSILON) return 2;\n else return 0;\n }\n\n bool recursive_insertion(vertex * fragment, int nvertices, beamtree_node & node) {\n int sign=0, * signs = (int *)alloca(nvertices*sizeof(int));\n for (int i=0;i<nvertices;++i) {\n sign |= signs[i] = conservative_signof (fragment[i] dot node.plane);\n }\n if (sign == 1) {\n // generally you just throw these away as terminating on a solid node.\n } else if (sign == 2) {\n right_attach(fragment,nvertices,node);\n } else if (sign == 3) {\n if (node->left) {\n\n in here find the contiguous set of vertices that have a\n conservative_signof of all 0's and 1's, passing along any\n 2's that precede or follow a beginning or final 1. this\n needs to wrap around to the beginning of the set as well.\n\n recursive_insertion(the set, # of verts, *node->left);\n } else {\n // throw it away as terminating on a solid node\n }\n\n out here find the contiguous set of vertices that have a\n conservative_signof of all 0's and 2's, and along any 1's\n that precede or follow a beginning or final 2.\n\n if (node->right) {\n recursive_insertion(the set, # of verts, *node->right);\n } else {\n right_attach(the set, number of vertices in the set, node);\n }\n }\n }\n}}}\n\n{{{right_attach}}} takes the edges between the supplied vertices and inserts them as planes using the equation given on the right hand side of the current plane.\n\nIn short, when you recurse to a solid node you throw away that fragment because its occluded.\n\nWhen you recurse to an open node, you take all edges of the polygon that have a point that has recursed this far and insert those edges as solid planes, the consistency of your clockwise or counter-clockwise winding will orient the plane to maintain the proper sidedness relationship.\n\nAny polygon that requires you to modify the tree is visible.\n\nYou can give the eye a 360 degree frustum with the following trickery:\n\n{{{ \n plane\n / \s \n -plane open\n / \s\n solid open\n}}}\n\nIf you don't start with some arbitrary plane, the first plane being inserted at the root would occlude half the surfaces from the standpoint of the light.\n\nRelative to the rest of the algorithms above, this approach is least likely to run afoul of pixel sized gaps due to scan conversion problems.\n\nIf you are looking for similar algorithms to compare with, this is very similar to Naylor's algorithm for performing CSG with a BSP tree and a B-rep.\n\nThis algorithm provides a polygon visibility test, its not as fast as the triage or cbuffer polygon visibility test, but it has the potential to avoid a lot of scan conversion problems that affect the other algorithms.\n\nYou can collapse a beam tree in a manner similar to the c-buffer algorithm as it fills up.

JIT refers to Just-In-Time compilation. This technique is used by most fast java compilers to execute the java byte-code. A couple of [[code examples|ICFP06 Universal Machine]] on this site employ this technique.

30 July 2006\n* Posted another JIT for the [[Universal Machine|ICFP06 Universal Machine]], this time in a mixture of C and Perl. \n29 July 2006\n* Posted a not-so-simple JIT based [[Universal Machine|ICFP06 Universal Machine]] written in Haskell as a (failed) proof of concept. I wouldn't recommend using this in practice. \n26 July 2006\n* Removed the view-source macros, as they were causing Firefox to crash in Linux.\n25 July 2006\n* Posted a simple [[Universal Machine|ICFP06 Universal Machine]] for the ICFP'06 contest.\n* Started transcribing my old [[Harmless Algorithms]] articles, so they wouldn't be lost due to the death of flipCode. \n20 July 2006\n* It has come to my attention that a number of Internet Explorer users have been having trouble viewing these pages. I will run the stock wiki code through the [[CPS]] transformer as soon as I get back to working on the [[recompiler|js.lang.Recompiler]]; The current direction the [[ECMAScript 4]] specification is heading has led me to instead fiddle with an ECMAScript 4 compiler in Haskell to take advantage of the strong type system and compositional monadic parsing. More information should be available shortly.\n

[[ICFP06 Universal Machine]] (perl, c, haskell)

{{{\ndarcs get http://slipwave.info/haskell/type-int/\n}}}\n\nThe following code freely makes use of GHC extensions, including multi-parameter type classes, functional dependencies, and template haskell.\n\n[[Type.Binary|haskell/type-int/dist/doc/html/Type-Binary.html]] [ [[hs|haskell/type-int/src/Type/Binary.hs]] ]\n[[Type.Binary.TH|haskell/type-int/dist/doc/html/Type-Binary-TH.html]] [ [[hs|haskell/type-int/src/Type/Binary/TH.hs]] ]\n[[Type.Binary.Internals|haskell/type-int/dist/doc/html/Type-Binary-Internals.html]] [ [[hs|haskell/type-int/src/Type/Binary/Internals.hs]] ]\n[[Type.Boolean|haskell/type-int/dist/doc/html/Type-Boolean.html]] [ [[hs|haskell/type-int/src/Type/Boolean.hs]] ]\n[[Type.Hex|haskell/type-int/dist/doc/html/Type-Hex.html]] [ [[hs|haskell/type-int/src/Type/Hex.hs]] ]\n[[Type.Hex.Stage1|haskell/type-int/dist/doc/html/Type-Hex-Stage1.html]] [ [[hs|haskell/type-int/src/Type/Hex/Stage1.hs]] ]\n[[Type.Hex.Stage2|haskell/type-int/dist/doc/html/Type-Hex-Stage2.html]] [ [[hs|haskell/type-int/src/Type/Hex/Stage2.hs]] ]\n[[Type.Hex.Stage3|haskell/type-int/dist/doc/html/Type-Hex-Stage3.html]] [ [[hs|haskell/type-int/src/Type/Hex/Stage3.hs]] ]\n[[Type.Maybe|haskell/type-int/dist/doc/html/Type-Maybe.html]] [ [[hs|haskell/type-int/src/Type/Maybe.hs]] ]\n[[Type.Ord|haskell/type-int/dist/doc/html/Type-Ord.html]] [ [[hs|haskell/type-int/src/Type/Ord.hs]] ]\n\nStages 2 and 3 of Type.Hex cannot be parsed fully by Haddock, so many of the instances are necessarily undocumented, but present.

24 August 2006\n* Work is continuing apace on my thesis as I continue playing with substructural dependent type systems.\n* Work on the haskell javascript compiler has stalled awaiting a response from the ecmascript 4 mailing list - over a month and no replies. I thought at first it was an error on my part, but no, its there in the archives. Without an official response of some sort I am hesitant to implement the computational model that my solution would allow, lest my entire implementation have to be rebuilt when they finally come to a consensus. =/\n\n4 August 2006\n* Added a large chunk of template haskell generated hexadecimal arithmetic with the same underlying structure as the binary code below to my [[Type]] library. This should scale better, and handle all realizing fake dependant typing needs. The binary version capped out around 2^21 (2,097,152), while this version caps out around 2^80 (1,208,925,819,614,629,174,706,176). I still have to write the multiplier and shifter, but template haskell seems to be holding up well to generating a couple of thousand instance declarations for me. I'm keeping both versions, since the Binary version doesn't absolutely require template haskell, while the hexadecimal version does. Also the former serves as good motivating documentation for the approaches in the second. //Update: August 5th: Multiplier and exponentiation added, and the actual cap is __+__ 2^73-1//\n\n3 August 2006\n* Posted some type-level [[2's complement binary arithmetic|Type]] code for Haskell. I needed it for some fake dependant typing, and I wanted to play around with type-level programming.

[[libraries]]\n[[harmless algorithms|Harmless Algorithms]]

coming soon...

<<view-source js js/util.js>>

<<view-source js js/test/Assert.js>>

<<view-source js js/test/Assert.t>>

<<view-source js js/test/Simple.js>>

<<view-source js js/test/Simple.t>>

<<view-source js js/test/Assert.h>>

Warning: opendir(../src/jslib/js/dom/ref) [function.opendir]: failed to open dir: Permission denied in /home/ekmett/comonad.com/public/includes/source.php on line 8

Warning: readdir(): supplied argument is not a valid Directory resource in /home/ekmett/comonad.com/public/includes/source.php on line 9

<<view-source js js/dom/Event.js>>

<<view-source js js/dom/Ready.js>>

<<view-source js js/xml.js>>

<<view-source js js/lang/Token.h>>

<<view-source js js/lang/Token/tree.js>>

<<view-source js js/lang/Token/visit.js>>

<<view-source js js/lang/Recompiler/ConstantFolding.inc>>

<<view-source js js/lang/Recompiler/CToken.inc>>

<<view-source js js/lang/Recompiler/Context.inc>>

<<view-source js js/lang/Recompiler/Flowgraph.inc>>

<<view-source js js/lang/all.js>>

<<view-source js js/lang/Parser/progress.js>>

<<view-source js js/lang/Recompiler.js>>

<<view-source js js/lang/Parser.o>>

<<view-source js js/lang/Parser.js>>

<<view-source js js/lang/Recompiler.h>>

<<view-source js js/lang/testme>>

<<view-source js js/lang/Atomizer.js>>

<<view-source js js/lang/Interpreter.js>>

<<view-source js js/lang/Interpreter.t>>

<<view-source js js/lang/Parser.t>>

<<view-source js js/lang/Token.js>>

<<view-source js js/lang/Parser.atoms>>

<<view-source js js/cps/PartialMeta.js>>

<<view-source js js/cps/Semaphore.js>>

<<view-source js js/cps/Meta.js>>

<<view-source js js/cps/Thread.h>>

<<view-source js js/cps/Appel.js>>

<<view-source js js/cps/Appel.h>>

<<view-source js js/cps/Thread.js>>

<<view-source js js/cps/Thread/Group.js>>

<<view-source js js/dom.js>>

<<view-source js js/all.js>>

<<view-source js js/test.js>>

<<view-source js js/math.js>>

<<view-source js js/math/all.js>>

<<view-source js js/math/Perlin.js>>

<<view-source js js/net.js>>

<<view-source js js/lang.js>>

<<view-source js js/io/BufferedIStream.js>>

<<view-source js js/io/BufferedOStream.js>>

<<view-source js js/io/PushbackIStream.js>>

<<view-source js js/io/StringIStream.js>>

<<view-source js js/io/OStream.js>>

<<view-source js js/io/common.js>>

<<view-source js js/io/IStream.js>>

<<view-source js js/aop.js>>

<<view-source js js/io.js>>

<<view-source js js/aop/PointCut.js>>

<<view-source js js/aop/Aspect.js>>

Warning: opendir(../src/jslib/js/aop/ref) [function.opendir]: failed to open dir: Permission denied in /home/ekmett/comonad.com/public/includes/source.php on line 8

Warning: readdir(): supplied argument is not a valid Directory resource in /home/ekmett/comonad.com/public/includes/source.php on line 9

<<view-source js js/aop/Observable.js>>

<<view-source js js/aop/Observable.t>>

<<view-source js js/net/Uri/toString.t>>

<<view-source js js/net/Uri/normalize.t>>

<<view-source js js/net/all.js>>

<<view-source js js/net/Uri.js>>

<<view-source js js/native.js>>

<<view-source js js/native/Boolean.js>>

<<view-source js js/native/Platform.h>>

<<view-source js js/native/String.js>>

<<view-source js js/native/all.js>>

<<view-source js js/native/Array/join.js>>

<<view-source js js/native/Array/push.js>>

<<view-source js js/native/Array.js>>

<<view-source js js/native/XMLHttpRequest.js>>

<<view-source js js/native/Platform.js>>

<<view-source js js/native/Function.js>>

<<view-source js js/native/Object.js>>

<<view-source js js/native/print.js>>

<<view-source js js/util/Treap.js>>

<<view-source js js/util/all.js>>

<<view-source js js/util/Heap.js>>

<<view-source js js/util/Heap.t>>

<<view-source js js/util/Trie.js>>

<<view-source js js/util/DisjointSet.js>>

<<view-source js js/util/Timer.js>>

<<view-source js js/util/DisjointSet.t>>

<<view-source js js/cps.js>>