In 1999 and 2000, and again in 2005 and 2006, and again now, the science journal Nature published and is publishing short SF stories under the name Futures. They're linked from its Futures page; but to see them, you must pay or be at a subscribing organisation. Last night, however, I chanced upon a selection of free Futures stories from The Science Fact & Science Fiction Concatenation.
February 2010 Archives
To teach a friend how compilers work, I've written a compiler for a small subset of Pascal. It lexically analyses and parses a program, code-generates the syntax tree into code for a stack machine not unlike the Ocode virtual machine once used by C's ancestral language BCPL, and interprets the code. I'm going to write a few essays about the compiler and its target machine; in this first one, I'll demonstrate how a stack machine evaluates expressions.
I was looking for a tree-drawing utility, to depict the syntax trees generated by a compiler I wrote in Prolog in order to teach a friend how compilers work. I have just found Christoph Lehner's Prolog Tree Drawing Program.
Although Prolog can be remarkably concise, it's far from ideal when we want to compose function calls. Even an expression as simple as "length of list A appended to list B" must be unwrapped into "append A to B giving C, then return the length of C". I'll explain how I overcame this by writing a preprocessor that translates functional notation into Prolog. It lets me define predicates as if defining functions, and write nested function calls without having to do what Fortran implementors had taught their compilers to do in the 1950s. The version described here works with SWI-Prolog.
I have scripts on my Web site that call SWI-Prolog from PHP 5. They run: a game for teaching Prolog, where the players are "intelligent" lorries that survive by buying and selling their freight, and buying petrol with the profit thereby earned; a science-fiction plot generator; and a generator of examples in category theory. A reader saw these last week and asked me why his Prolog-from-PHP script didn't work; so I'm going to explain how to code ones that do. My examples should work, mutatis mutandis, with other Prologs and other languages; and if you program in SWI-Prolog, they'll give you tested code that will get you started straight away.
It's a pun between logic and control flow: a pun where you hear "A or B" with one ear but "Do A; until something fails, then try B" with the other. In most languages, there are Boolean expressions that return a TRUE or a FALSE, and conditions that jump to a THEN or an ELSE. But in Snobol, there are pattern matches that succeed or they fail; and if a match fails, the matcher will backtrack to already-matched subpatterns, seeking alternative matches that make the current match succeed. And in Prolog, there are calls to predicates that succeed or they fail; and if a call fails, Prolog will backtrack to already-called predicates, seeking alternative solutions that make the current call succeed. "It is not enough", as Gore Vidal wrote, "to succeed. Others must fail". I am going to show you how I implemented Snobol's "bal" pattern, which matches a string that's balanced in round brackets, with Prolog Definite Clause Grammar rules; and how to use failure to probe "bal"'s behaviour.