Kevin Reid's blog

Latest Posts

 

new
Name
Kevin Reid
Website
My Website

View

Navigation

February 25th, 2014

How to really fix a bug

Add to Memories Share
new

If you're feeling virtuous:

  1. Figure out what's going on.
  2. Figure out why what's going on wasn't immediately obvious.
  3. Make it so that such failures are caught and reported obviously.
  4. Make it so that the rest of the system recovers from such failures.
  5. Write a test for the bug, and a couple more while you're at it.
  6. Write the actual fix.

(I ought to do more actual concrete blogging, like what I've been doing lately. This crossed my mind as a light and easy piece — I actually followed part of this procedure yesterday after pushing a version (of what, I'll get to later) that was rather broken.)

July 23rd, 2013

One of the nice things about Common Lisp is the pervasive use of (its notion of) symbol objects for names. For those unfamiliar, I'll give a quick introduction to the relevant parts of their semantics before going on to my actual proposal for a “good parts version”.

A CL symbol is an object (value, if you prefer). A symbol has a name (which is a string). A CL package is a map from strings to symbols (and the string key is always equal to the symbol's name). A symbol may be in zero or more packages. (Note in particular that symbol names need not be unique except within a single package.)

Everywhere in CL that something is named — a variable, a function, a class, etc. — the name is a symbol object. (This is not impractical because the syntax makes it easy to write symbols; in fact, easier than writing strings, because they are unquoted.)

The significance of this is that the programmer need never give significance to characters within a string name in order to avoid collisions. Namespacing of explicitly written symbols is handled by packages; namespacing of programmatically generated symbols is handled by simply never putting them in any package (thus, they are accessible only by passing references); these are known as gensyms.

Now, I don't mean to say that CL is perfect; it fails by way of conflating too many different facilities on a single symbol (lexical variables, dynamic variables, global non-lexical definitions, ...), and some of the multiple purposes motivate programmers to use naming conventions. But I think that there is value in the symbol system because it discourages the mistake of providing an interface which requires inventing unique string names.

(One thinking along capability lines might ask — why use names rather than references at all? Narrowly, think about method names (selectors, for the Smalltalk/ObjC fans) and module exports; broadly, distribution and bootstrapping.)


So, here’s my current thought on a “good parts version”, specifically designed for an E-style language with deep equality/immutability and no global mutable state.

There is a notion of name, which includes three concrete types:

  1. A symbol is an object which has a string-valued name, and whose identity depends solely on that string.
  2. A gensym also has a name, but has an unique identity (selfish, in E terms). Some applications might reject gensyms since they are not data.
  3. A space-name holds two names and its identity depends solely on that combination. (That is, it is a “pair” or “cons” specifically of names.)

Note that these three kinds of objects are all immutable, and use no table structures, and yet can produce the same characteristics of names which I mentioned above. (For implementation, the identity of a name as above defined can be turned into pointer identity using hash consing, a generalization of interning.) Some particular examples and notes:

  • A CL symbol in a package corresponds to a pair of two symbols, or perhaps a gensym and a symbol. This correspondence is not exact, of course. (In particular, there is no notion here of the set of exported symbols in a package. But that's the sort of thing you have to be willing to give up to obtain a system without global mutable state. And you can still imagine 'linting' for unexpected symbols.)
  • The space-name type means that names can be arbitrary binary trees. If we consistently give the left side a “namespace” interpretation and the right side a “local name” one, then we have a system, I think, where people can carve out all sorts of namespaces without ever fearing collisions or conflicts, should it become necessary. Which probably means it's massively overdesigned (cf. "worse is better").
  • Actual use case example: Suppose one wishes to define (for arbitrary use) a subtype of some well-known interface, which adds one method. There is a risk that your choice of name for that method conflicts with someone else's different subtype. Under this system, you can construct a space-name whose two components are a large random number (i.e. a unique ID) acting as the namespace, and a symbol which is your chosen simple name. One can imagine syntax and tools which make it easy to forget about the large random number and merely use the simple name.
  • It's unclear to me how these names would be used inside the lexical variable syntax of a language, if they would at all; I suspect the answer is that they would not be, or mostly confined to machine-generated-code cases. The primary focus here is improving the default characteristics of a straightforwardly written program which uses a map from names to values in some way.

(This is all very half-baked — I'm just publishing it on the grounds described in my previous post: in the long run I'll have more ideas than I ever implement, and this is statistically likely to be one of them, so I might as well publish it and hope someone else finds some use for it; if nothing else, I can stop feeling any obligation to remember it in full detail.)

May 19th, 2013

I have come to realize that I have more ideas for programs than I'll ever have time to write. (This means they're not actually all that significant, on average — see all that's been said on ‘ideas vs. execution’.) But maybe I have the time to scribble a blog post about them, and that's stuff to blog about, if nothing else.

So, a video game idea I had today: reverse bullet-hell shooter.

A regular bullet-hell shooter is a game where you move in a 2D space dodging an immense number of mostly dumb instant-death projectiles launched in mostly predefined patterns, and trying to shoot back with dinkier, but better aimed, weapons. Instead, here you design the bullet pattern so as to trap and kill AI enemies doing the dodging.

The roles seem a bit similar to tower defense, but the space of strategies would be considerably more, ah, bumpy, since you're not doing a little bit of damage at a time and how it plays out depends strongly on the AI's choices.

That's probably the downfall of this idea: either the outcome is basically butterfly effect random due to enemy AI decisions and you mostly lose, or there are trivial ways to design undodgeable bullet patterns and you mostly win. I don't immediately see how to make the space of inputs and outcomes “smooth” enough.

April 20th, 2013

Thoughts on Tron

Add to Memories Share
new

Tron was one of my childhood favorite movies.

Before I watched Tron: Legacy, I reminded myself to not critique it overly harshly compared to the original — after all, there had been the grid bug scene. (Which, if you don’t happen to recall, introduces grid bugs, without any relationship to the rest of the action, which then never appear again.)

Then they had to throw a bunch of philosophical blather in the middle, which I could only think of at the time as “let’s be all profound like The Matrix”.

But, I was just thinking about that, and the closing scene where the very last of the [SPOILER] is going out and about and [SPOILER], and the early scene in Tron in the laser lab (“Not disintegrating — digitizing!”), and:

Imagine an alternate universe (it can’t happen here, they went too long without) where a key scene goes like this:

MENTOR FIGURE: Remember, that which can be digitized, can be copied.

April 7th, 2013

Yesterday I completely rewrote my resource embedding test to cover more cases (especially ones new in HTML5) and be more usable. In the likely event you're not familiar with it, it's a HTML document which embeds many types of resources (images, audio, other HTML, etc.) using all of the possible containers (<img>, <iframe>, etc.) to see how browsers react.

The results can be quite interesting; for example, with the current expansion I discovered that JavaScript embedded in a SVG document will not execute if embedded using <img>, but will with <object>. (In hindsight, this makes perfect sense given the fundamental design principle of Web security, namely “don't add anything which would obviously make existing sites' security assumptions false”, the assumption here being that it's safe to allow <img>s as user-generated content.)

Specific new features:

  • Audio, HTML, and plain text content. (Unfortunately, some combinations cause the audio to autoplay; I tried to make it quiet and plain to make up for that.)
  • <audio> and <video> containers.
  • Scripts inside HTML and SVG content, which also attempt to modify window.top.
  • Fixed-scrolling headers so you don't need a large window to make sense of the large table.

Let me know if you've thought of any additional useful cases.

Tags: ,

March 26th, 2013

Let's say you have two or more independent Git branches, and you want to make sure the combination of them works correctly, but aren't ready to permanently merge or rebase them together. You can do a merge and discard it (either by resetting afterward or using a temporary branch), but that takes extra commands when you're done with the trial. Here's the script I put together to eliminate all unnecessary steps:

#!/bin/sh
set -e
set -x
git checkout --detach HEAD
git merge --no-edit -- "$@"

In a single command, this merges HEAD and any branches given as arguments and leaves you at the merge as a detached HEAD. This means that when you're done with it you can just switch back to your branch (git checkout - is a shortcut for that) and the merge is forgotten. If you committed changes on top of the merge, git checkout will tell you about them and you can transplant them to a real branch with git cherry-pick.

February 21st, 2013

“:”

Add to Memories Share
new

When Larry Wall was designing Perl 6, he started with lots of community proposals, from which he made the following observation:

I also discovered Larry's First Law of Language Redesign: Everyone wants the colon.

When I was recently trying to redesign E, I found that this holds true even if only one person is involved in the process. One of the solutions considered was having “” and “ :” be two different tokens…

February 11th, 2013

Portal 2 puzzles

Add to Memories Share
new

Here's another thing I've been doing: designing Portal 2 puzzles.

The Cube Goes in the Other Pit

(F)utile Independence

Balance, Beam

I’m probably going to keep doing this (as the inspiration strikes) — all feedback welcome!

Tags: ,

I really haven't been posting very much, have I? It's mostly the job occupying most of my “creative energy”, but I've also been doing a little bit of this and that and not ever finishing something to the point of feeling like writing it up.

On the programming-projects front, I'm attempting to extract two reusable libraries from Cubes for the benefit of other web-based games.

  • Measviz takes performance-measurement data (frames per second and whatever else you want) and presents (in HTML) a compact widget with graphs; my excuse for not announcing it is that the API needs revision, and I haven't thought of a good toy example to put in the documentation-and-demo page I'm writing, but if you're willing to deal with later upgrades it's ready to use now.
  • The other library, currently in need of a good name, is a generalized keybinding library (generalized in that it also handles gamepads/joysticks, which are completely different). You define the commands in your application, and it handles feeding events into them. Commands can be polled, or you can receive callbacks on press and release, with optional independent autorepeat. It's currently in need of a name, and also of API cleanup.

I've been making some sketches towards a redesign of E (list archive pointer: starting here), basically to take into account everything we've learned over the years without being constrained by compatibility, but it hasn't gotten very far, partly because language syntax is hard — all options are bad. (The current E syntax is pretty good for usability, but it has some particularly verbose/sea-of-punctuation corner cases, and I'd also like to see a simpler syntax, with more facilities moved into code libraries.)

January 18th, 2013

stdin, stdout, stderr, stdcpu, stdmem, stdfs

November 6th, 2012

  1. Premise: Any attack on a password — whether online (login attempts) or offline (hash cracking) — will be designed so that the more likely a given password is, out of the space of all possible passwords, the less work is required to recover that password (unless a trivial amount of work is required to discover any possible password).

  2. From (1), there exists a probability distribution of passwords.

  3. Premise: There is a (practical) maximum length for passwords.

  4. From (3), the set of possible passwords is finite.

  5. From (2) and (4), there is a minimum probability in that distribution.

  6. Use one of the passwords which has that minimum probability.

(There are at least two ways this doesn't work.)

October 28th, 2012

Server change

Add to Memories Share
new

switchb.org web and Subversion services are now running on a different server. Do let me know if you notice something broken.

Tags: ,

September 7th, 2012

My GLToyJS project now has a live instance so you can play with it without setting up your own server. Caveats: • I don't promise it will remain at this URL or that the parameter format won't change. • There is an automatic 5-minute-interval change to a new random effect which cannot be disabled (but you can undo it by going back). • It doesn't tell you if your browser doesn't have WebGL, it just stops (gray screen).

Closure is now available on Mac and Windows via Steam (previously on PS3). If you like platform puzzle games, or if you like games that play with the nature of the virtual universe, then you need to play this game. Convinced my description is inadequate for a purchase decision? Play the free Flash original.

I bought it as soon as it came out and while I haven't finished it, I've played through several of the puzzles and it is living up to what I'd hoped it would be. The one thing that bothers me a bit is the loss of the original version's 1-bit aesthetic. (Yes, I said 1-bit, not 8-bit. I'm talking about color depth, not word size.)

August 23rd, 2012

Software-defined radio

Add to Memories Share
new

A couple weekends ago, I was musing that among my electronic devices there was no radio — as in AM/FM, not WiFi and Bluetooth and NFC and etc. Of course, radio is not exactly the most generally useful of information or entertainment sources, but it still has some things to be said for it, such as being independent of Internet connections.

Another thing that came to mind was my idle curiosity about software-defined radio. So, having read that Wikipedia article, it led me to an article with a neat list of radio hardware, including frequency range, sampling rate (≈ bandwidth) and price. Sort by price, and — $20, eh? Maybe I’ll play around with this.

What that price was for was RTL-SDR — not a specific product, but any of several USB digital TV receivers built around the Realtek RTL2832U chip, which happens to have a mode where it sends raw downshifted samples to the host computer — intended to be used to provide FM radio receiving without requiring additional hardware for the task. But there's plenty of room to do other things with it.

I specifically bought the “ezTV”/“ezcap” device, from this Amazon listing by seller NooElec (who also sells on eBay, I hear) (note: not actually $20). One of the complications in this story is that different (later?) models of the same device have slightly different hardware which cannot tune as wide a frequency range. (Side note: when buying from Amazon, what you actually get depends on the “seller” you choose, not just the product listing, and as far as I know, any seller can claim to sell any product. If you see a product with mixed “this is a fake!” and “no it's not!” reviews, you're probably seeing different sellers for the same product listing.)

Of course, the point of SDR is to turn hardware problems into software problems — so I then had a software problem. Specifically, my favorite source for unixy software is MacPorts, but they have an obsolete version of GNU Radio. GNU Radio is a library for building software radios, and it is what is used by the first-thing-to-try recommendation on the Osmocom RTL-SDR page (linked above), multimode.py. The MacPorts version of GNU Radio, 3.3.0, is too old for the RTL-SDR component, which requires 3.5.3 or later. So I ended up building it from source, which took a bit of tinkering. (I'm working on contributing an updated port for MacPorts, however.)

I've had plenty of fun just using it “scanner” style, seeing what I can pick up. A coworker and friend who is into aviation posed a problem — receive and decode VOR navigation signals — which has led to several evenings of fiddling with GNU Radio Companion, and reading up on digital signal processing while I wait for compiles and test results at work. (It sort-of works!)

This is also notable as the one time in my life where a ferrite bead on a cable actually did something — putting one on the computer end of the USB extension cord noticeably reduced the noise level. (And, of course, there remains a large, metallic hardware problem: antennas!)

(I could say more, such as the detailed fiddling to build GNU Radio, and various useful links, but it's taken me long enough to get around to writing this much. Let me know if you'd like me to expand on any particular technical details.)

July 8th, 2012

Status update

Add to Memories Share
new

Arrived in California a few days ago; setting up assorted arrangements. I start work in a week.

June 30th, 2012

Porting GLToy to WebGL

Add to Memories Share
new

Started a new project, GLToyJS; I’m porting my GLToy to WebGL. The advantage, besides using a higher-level language and modern OpenGL (shaders!), is that it is more cross-platform, rather than being a Mac-only screensaver. The disadvantage is that it’s not a screensaver at all, but a web page; I plan to add a wrapper to fix that, and I have a working proof of concept.

So far I’ve put together the core framework and ported 6 of the original 13 effects (most of the in-my-current-opinion good ones, of course). An additional feature is that an effect’s parameters are described in JSON, which will be used to allow you to save a particularly good random result for future viewing. (I could just put them in the URL, in fact — I think I’ll try that next.)

I haven't yet created any new effects, so nothing takes obvious advantage of the additional capabilities provided by shaders (other than refinements such as Phong-rather-than-Gouraud lighting and GPU-side particle systems). I also wrote a sketchy compatibility layer for the GLSL Sandbox’s interface so that you can drop in a fragment shader from there to make an effect; a possible thing to do would be automatically downloading from their gallery (if politeness and copyright law permits).

It's not published as a web page anywhere yet, but it should be and I’ll let you know as soon as it is.

June 25th, 2012

The draft-standard Gamepad API allows JavaScript in the browser to obtain input from connected gamepad/joystick devices. This is of course useful for games, so I have worked on adding support for it to Cubes.

This (about) is the only Gamepad API demo that I found that worked with arbitrary gamepads (or rather, the junk one I had around) rather than ignoring or crashing on anything that wasn't a known-to-it devices such as a PS3 or Xbox controller. (It's part of a game framework called Construct 2, but I haven't investigated that further.) It was critical to my early setup in making sure that I had a compatible gamepad and browser configuration.

(There's a reason for libraries having information about specific devices — the Gamepad API just gives you a list of inputs and doesn't tell you what the buttons should be called in the user interface — and these days you're almost expected to have pictures of the buttons, too. But there's no reason not to have a fallback, too. Incidentally, the USB HID protocol which most gamepads use is capable of including some information about the layout/function of buttons, but this information is often incorrect and the Gamepad API does not expose it.)

In order to integrate gamepad support into Chrome, I used Toji's Game Shim library, a very nice lightweight library which only adapts browser-provided interfaces to the current draft standards so that you can use the Gamepad API, as well as requestAnimationFrame, fullscreen, and pointer lock, without making your code full of conditionals or browser-specific prefixes.

June 7th, 2012

Graphics bugs are fun

Add to Memories Share
new

An early stage in the development of lighting in Cubes (long since past).

Powered by LiveJournal.com