http://qntm.org/ the personal website of Sam Hughes http://qntm.org/fib http://qntm.org/fib Code » This is me attempting to decode this. The problem Let's say you've got a function of one argument. Basic Fibonacci sequence. Recursive, calls itself. Returns an integer. var fibo = function(n) { return n == 0 ? 0 : n == 1 ? 1 : fibo(n-1) + fibo(n-2); }; alert("fibo(32) = " + fibo(32)); // Takes a little while Is there a way to create a new function which is identical but automatically caches answers before it returns them? Let's say, for simplicity of implementation, that the argument can always be used as the index in an object, which means that a simple object cache can be used to cache the results from the function. Then there sure is. For example, we could manually create a wrapper function fibo_caching: var fibo = function(n) { return n == 0 ? 0 : n == 1 ? 1 : fibo(n-1) + fibo(n-2); }; var fibo_caching = function(n, cache) { if(!cache[n]) { cache[n] = fibo(n); } return cache[n]; }; var ...]]> Wed, 07 Sep 2011 19:11:47 +0100 http://qntm.org/tetris http://qntm.org/tetris Code » Exactly one of the following statements is true. In Tetris, you can always get at least one line before losing. In Tetris, a sufficiently evil AI can always force you to lose without getting a single line, by providing bad pieces. Which one? Prove it. The setup I created HATETRIS last year because I wanted Tetris players to suffer. It was something I created for my own amusement and as a programming challenge and to investigate the use of JavaScript as a gaming platform. HATETRIS explores only to a depth of 1 piece. It looks at the immediate future and chooses the single worst piece for the present situation, ignoring the possibility of the player using the current piece to set up a situation where the 2nd piece forces a line. After the first iteration of the game, I started using a bit mask to express each row of the playing field ("well"), which made testing the insertion and removal of possible pieces faster, to the extent that a new piece appeared more or less instantl...]]> Wed, 20 Jul 2011 23:26:17 +0100 http://qntm.org/locoparser http://qntm.org/locoparser Code » Following up from Loco, which introduced Loco.php, here are some more examples built using this parser combinator library. Each of these examples enables you to parse a grammar and return a Grammar object capable of recognising that grammar. bnf.php - Defines $bnfGrammar, which parses grammars presented in Backus-Naur Form. wirth.php - Defines $wirthGrammar, which parses grammars presented in Wirth syntax notation. ebnf.php - Defines $ebnfGrammar, which parses grammars presented in Extended Backus-Naur Form. locoNotation.php - Defines $locoGrammar, which parses grammars presented in Loco notation (see below). Examples and demonstrations can be found in the unit testing sections at the bottom of each script. Alternatively, read on to see what each notation gives you: Backus-Naur Form BNF is generally pretty low-tech and lacks a lot of features. Sample grammar in Backus-Naur Form This appears on Wikipedia. This is a pretty clunky example because it doesn't handle wh...]]> Sun, 10 Jul 2011 18:36:29 +0100 http://qntm.org/loco http://qntm.org/loco Code » Loco is a library of parser combinators for PHP. Loco uses single-valued parsers called MonoParsers. A conventional, "enthusiastic" parser returns a set of possible results (which is empty if parsing is not possible). A "lazy" parser returns one possible result on the first call, and then returns further results with each subsequent call until no more are possible. MonoParsers simply return a single result or failure. By explicitly disallowing backtracking, this keeps parsing time linear (unless you use advanced, non-regular "regular expressions", but that's crazy talk). Loco.php Examples json.php - parse JSON expressions regEx.php - take simple regular expressions and parse them into data structures simpleComment.php - recognise HTML comments for here on qntm.org More examples For examples of using Loco to recognise grammar syntax notations such as Backus-Naur Form, see More Loco examples. Great things about Loco Parse in linear time Simple, logical,...]]> Thu, 30 Jun 2011 12:49:38 +0100 http://qntm.org/railroad2 http://qntm.org/railroad2 Code » Alert! Don't use this! It is hideously, unnecessarily, unmaintainably complicated under the covers and I no longer support it in any meaningful sense. Use Loco instead! Much more sensible. Here's the PHP script containing the Lexer and Parser classes that you'll need to create your own PHP lexers and parsers. RailroadParser.php And here are some pre-built samples. json.php - lexer and parser for the JSON data format. Turns JSON strings into pleasant PHP arrays. simpleComment.php - lexer and parser for user comments here at qntm.org. Validates that the supplied string fits the strict subset of HTML that is permitted. Returns the original comment in string form, but could just as easily return a cleaned-up comment, or nothing. bnf.php - lexer and parser for a very basic subset of Backus-Naur Form. Actually returns a new Parser object as output. bracketMatch.php - very simple worked example for Wikipedia's example well-formed parentheses context-free grammar. With extens...]]> Sat, 16 Apr 2011 15:33:55 +0100 http://qntm.org/railroad http://qntm.org/railroad Code » Okay! This is a much more useful collection of PHP scripts than the earlier ones because they are actually useful for the purposes of parsing (well, validation). In order to make this work, put these three files in the same directory so that they can require_once() one another properly. Lexer.php ContextFreeGrammar.php Railroad.php Here's a simple script which demonstrates how to use these libraries. Or modules or packages or whatever they're called in PHP. demo.php Info Lexers There is no explicit line in the sand which says what a lexer must do and what the actual parser must do. In theory, parser combinators are of unlimited power and can handle actual context-free grammars and better, but for practical purposes this is not what parser combinators are best at. Likewise it a waste of processing power running pedestrian finite-state-machine nonsense on a full-blown CFG parser. So, basically, anything that a regex can do (i.e. concatenation, alternation, multiplicatio...]]> Sun, 06 Mar 2011 19:29:25 +0000 http://qntm.org/tax http://qntm.org/tax Code » So this is what I was doing with all of that graphing. I guess some people might find this useful. I found the information interesting. A more interesting summary graph is on Wikipedia: Historical tax rates for the highest and lowest income earners. U.S. federal individual income taxation 2011 U.S. federal individual income taxation 2010 U.S. federal individual income taxation 2009 U.S. federal individual income taxation 2008 U.S. federal individual income taxation 2007 U.S. federal individual income taxation 2006 U.S. federal individual income taxation 2005 U.S. federal individual income taxation 2004 U.S. federal individual income taxation 2003 U.S. federal individual income taxation 2002 U.S. federal individual income taxation 2001 U.S. federal individual income taxation 2000 U.S. federal individual income taxation 1999 U.S. federal individual income taxation 1998 U.S. federal individual income taxation 1997 U.S. federal individual income taxation 1996 U.S....]]> Mon, 28 Feb 2011 19:59:34 +0000 http://qntm.org/pda http://qntm.org/pda Code » This is more of a progress report than a finished, usable library. This is a set of PHP scripts which allow you to create an arbitrary context-free grammar object and then turn that into a pushdown automaton object capable of recognising strings in that grammar. In order to make it work, put these three files in the same directory so that they can require_once() one another properly. DirectedGraph.php ContextFreeGrammar.php PushdownAutomaton.php Here's a simple script which demonstrates how to use these libraries. Or modules or packages or whatever they're called in PHP. demo.php Info Use You create a ContextFreeGrammar object in the same way that this was accomplished last time I mentioned it. The new function getPda() can be used to return a PushdownAutomaton object which will accept that grammar. This is checked using the willAcceptString() method on the PushdownAutomaton, which returns a boolean. You can also create a PushdownAutomaton object yourself in mu...]]> Tue, 15 Feb 2011 23:03:21 +0000 http://qntm.org/chomsky http://qntm.org/chomsky Code » Backus-Naur Form is the standard means by which a context-free grammar may be represented in text. Backus-Naur Form can be used to represent any context-free rule from any context-free grammar. However, it is sometimes more useful to render a context-free grammar into Chomsky Normal Form. In Chomsky Normal Form, only the following forms of context-free rule are allowed: S → ε, where S is the start symbol A → BC, where B and C are non-terminal symbols and B ≠ S and C ≠ S A → α, where A is a nonterminal symbol and α is a terminal symbol. It can be proven that any context-free grammar, whether presented in Backus-Naur Form or otherwise, can be converted into Chomsky Normal Form. The following PHP script describes a Rule class and a ContextFreeGrammar class to which Rules can be added. The ContextFreeGrammar class also contains a function toCnf() which can be called to convert the grammar to Chomsky Normal Form. cfg.php Use Use of this co...]]> Tue, 08 Feb 2011 10:11:39 +0000 http://qntm.org/greenery http://qntm.org/greenery Code » In part one I made a Python-based library for creating and manipulating finite state machines in Python, using fsm.py and fsmops.py. In part two I made a Python-based library for parsing a regular expression into a data structure and manipulating them, using lego.py and legoops.py. Most recently I posted a semi-original algorithm for converting a finite state machine back into a regular expression and promised a Python implementation. So here we are! fsmops.py fsm.py legoops.py lego.py mainops.py main.py The FSM and regex libraries are prerequisites for these to work correctly. mainops.py This library contains two basic functions. As you saw before, legoops.py contains a legobuild() function which turns a regular expression from a string into a pattern object. Here, fsmbuild() takes a pattern object and turns it into a finite state machine object. The clever bit, however, is regexbuild() which takes a finite state machine object and, using the...]]> Sat, 09 Oct 2010 17:16:22 +0100 http://qntm.org/lego http://qntm.org/lego Code » lego.py legoops.py Previously. Okay, part two of three. The aim with this collection of modules was provide a way to read a regular expression, as provided in the form of a string, into a manipulable nested data structure, and provide various methods for manipulating that data structure while keeping the structure as simple as possible. Note that this is an entirely different concept from that of simply creating and using those regexes, functionality which is present in basically every programming language in the world, Python included. It's been proven that there is no canonical regular expression for any specific regular language. Many regular expressions describe the precise same language and many of those regexes are incomprehensibly long. It's also been proven that the process of simplifying a regular expression to any significant extent is seriously computationally challenging. In fact, it's a really interesting subject to me because you can start with some very basic...]]> Sun, 01 Aug 2010 18:10:45 +0100 http://qntm.org/fsm http://qntm.org/fsm Code » fsm.py fsmops.py Okay, so I had an idea for a project and I decided that this would be as good a time as any to also learn Python so here's the first part of it. I can't release all of it right now but the rest is forthcoming. This is (and I realise that this has been done before) a library for the creation and manipulating of deterministic finite state machines in Python. I realise that this has been done before in basically every language under the sun, Python included, but doing it for myself was incredibly good fun and highly educational. fsm.py This contains the basic fsm class. This allows you to create a deterministic finite-state machine (I guess "automaton" is a more correct term but never mind, if that bothers you too much you can do a find-and-replace). A finite state machine is a combination of three things: A finite alphabet Σ of symbols A finite set S of states A map δ : S × Σ → S which tells the machine what to do when a symbol is ...]]> Sat, 31 Jul 2010 17:40:31 +0100 http://qntm.org/hatetris http://qntm.org/hatetris Code » Play Hate Tetris. This is bad Tetris. It's hateful Tetris. It's Tetris according to the evil AI from "I Have No Mouth And I Must Scream". I have to be honest, this is not an entirely original idea. However, RRRR's implementation of the concept of a game of Tetris which always gives you the worst possible pieces leaves much to be desired: the keyboard interface frequently doesn't work the conditions for failure are ambiguous and inconsistent the playing field is only 8 blocks wide as compared to the standard 10 the AI is either overly generous, or stupid, and frequently does NOT provide you with the worst possible piece (UPDATE: there is also Bastet, which can be played online here, but is also far too forgiving.) HATETRIS was an experiment to rectify those flaws. Also, every coder has to build Tetris at least once in their life. In addition, I also have a passionate hatred of JavaScript, but I felt that that hatred was borne out of ignorance, so this was an attempt to r...]]> Sat, 03 Apr 2010 23:58:47 +0100 http://qntm.org/utf-8 http://qntm.org/utf-8 Code » Since UTF-8 is a complex beast to validate I've made some slight further changes to the parser that's used to validate comments here on the site. One of the great things about HTML is how easy it is to parse and how many flexible approaches there are. I've managed to come up with a way which while working in linear time also involves quite a lot of raw data to specify exactly what is permitted and what isn't. This parser is clever, though, because it parses the text literally one character at a time, which means that I can seamlessly combine it with my new UTF-8 validating routines instead of having to rely on PHP's abysmal UTF-8 support, such as the mb_substr() function which utterly fails to notice when invalid UTF-8 is passed to it. I deliberately set out to avoid the use of magic numbers and to make the routine as simple to parse as possible. And then I also remembered that other than my Perl Snake Cube solver which I presented a few weeks ago, it's been years since I actually put...]]> Wed, 31 Mar 2010 11:36:43 +0100 http://qntm.org/snakecube http://qntm.org/snakecube Code » For Christmas one of my friends presented me with a block puzzle. This puzzle was basically a Rubik's Cube, but the difference was, instead of having colours on each side, all the sides were coloured yellow. Instead, a snake, with two heads, starts at the centre of one of the faces of the cubies and snakes around the other cubies to its endpoint. Once scrambled, the idea is to unscramble the cube so that the snake forms one continuous curve. Attempt 1: solving legitimately This proved to be extremely difficult. To begin with, I am very bad at the Rubik's Cube puzzle, so simply rearranging the cubies using ordinary legal turns is not something I can do. I was restricted to trial and error. Attempt 2: take the cube apart and solve by eye The next problem was that even having taken the cube apart - and unfortunately I broke one of the pieces in order to do this, but the puzzle itself was still intact enough to be entirely solvable, so no worries - you still don't know what the solutio...]]> Fri, 19 Feb 2010 21:45:47 +0000