Archive for August, 2005
The fancy new mouse Apple are selling has a neat hardware feature: squeezing the sides together acts like a button click (on some nth button). They combine it, by default, with a kind of okayish software feature: squeezing the new button shows the dashboard until you stop squeezing.
Looking at CellDesigner’s “bird’s eye view” feature (from the manual) gave mikeb and I an idea: you could use the squeeze-button to control a spring-loaded zoom feature in a Raskinish zooming user interface.
- The user would start squeezing to begin zooming out. The zoom velocity would smoothly and quickly ramp up to a constant (configurable) rate.
- Zooming out would continue at that constant rate until either the user releases the squeeze-button (at which point it “drops” you back to the zoom level and position you started from) or the mouse moves more than a (configurable) epsilon from its starting position.
- If the mouse moves, the zooming process rapidly slows down and stops, hovering over the canvas. The user can use the mouse to pan while the squeeze-button is held in.
- When the button is finally released, it rapidly drops the camera back to whatever zoom level you used last time you visited this general vicinity. (Not the zoom level you started from. Deciding what the “vicinity” might mean is an interesting problem.)
You could indicate, with a mostly-transparent overlay, where letting go of the button will end up dropping you. When you squeeze, the current view turns transparent while the canvas drops out from underneath you as you rise; while panning, the transparent overlay is updated to reflect the view you’ll get if you let go here; and when you let go, the canvas rises up to meet you as you fall, until it eventually overlaps the transparent view, at which point the transparent view is redundant and can be removed until the next zoom.
Even better would be if the squeeze-button were an analogue control, that could measure pressure like a tablet stylus. You could use the force of squeezing to control the rate of ascent/braking. Then you’d only need that one control for zooming out (so long as there was a way of making your current hover level the new ground level); zooming in could perhaps be done by dragging out a rectangle on the current view that is to expand and become the new view, much as one does with old-school fractal programs.
August 25th, 2005
tonyg
I’ve taken my Scheme Packrat Parser library, ported it to MzScheme, documented it, and implemented a JSON reader-writer library on top of it.
The code is all available under the MIT license. A darcs repository is available at http://www.lshift.net/~tonyg/json-scheme/, or you can grab a snapshot tarball including a PDF version of the documentation.
$ darcs get http://www.lshift.net/~tonyg/json-scheme/
August 22nd, 2005
tonyg
Using Squeak over recent months, I’ve found myself wanting to move windows back and forth between various projects occasionally. (Projects in Squeak are a kind of hierarchical multiple-desktop setup, where subprojects of a project are displayed as thumbnails in little windows on the desktop, which when clicked, enter the displayed subproject. The main desktop menu allows you to navigate among all the projects in the image. This page has more detail on Projects.)
Today I decided to try implementing the feature. It turned out to take about 15 minutes: five minutes to conduct experiments to determine a workable procedure for doing the move, five minutes to actually implement the method on the correct class and hook it into the system menus, and five minutes to mail the changeset to the squeak-dev mailing list.
Here’s the code (on class SystemWindow):
sendToProject
| pr |
pr := CustomMenu new addList: (Project hierarchyOfNamesAndProjects); startUp.
pr ifNil: [^ self]. "Don't do anything if the user cancelled the menu."
World removeMorph: self.
pr world addMorph: self.
That prompts the user for a project to send the current window to, removes the current window from the active project, and inserts it into the target project. That’s all there was to it! This simplicity and directness is part of what I like about Squeak.
August 19th, 2005
tonyg
Today I implemented a JSON reader/writer library for Squeak, and a small extension to Seaside’s existing LivePage features for doing XMLHttpRequest-based server-push.
The JSON code is available on Squeakmap and also via SqueakSource, under either SqueakL (see here and here) or the MIT license. The Seaside extension is still in flux, but I’ll release something as soon as I have something releasable.
August 17th, 2005
tonyg
Of the many new ciphers proposed as part of the ECRYPT Stream Cipher Project, one of the most interesting is Christophe De Cannière and Bart Preneel’s TRIVIUM. TRIVIUM is designed to be very simple, admit a very low gate count implementation in hardware, and be reasonably efficient in both hardware and software, parallelizing in a straightforward way for fast hardware implementations and admitting of a straightforward bitslice implementation in software.
Today’s tip: I now think that the fastest way to write a software implementation for x86 is to store the inverses of the register contents, rather than the register contents themselves. Super bonus points for anyone who can figure out why.
August 15th, 2005
Paul Crowley
Does your internet go away occasionally? Do you have a computer hooked up to a moderately loud stereo system? Want to know as soon as the link comes back? Here’s a script (put it in a file, e.g. ~/bin/audible-ping) that pings some outside host, playing a short .wav file when ping finally starts to get some responses:
#!/bin/sh
ping "$@" | \
grep --line-buffered 'bytes from' 2>&1 | \
perl -e 'while (<>) { `play /path/to/the/ping/sound.wav`; }'
It will play the .wav file once per successful ping packet reply. (Obviously you’ll need to come up with your own short beep-like sound file, and replace the path given above appropriately; use play’s --volume=n parameter to adjust the volume to taste.)
We use it here when our DSL connection goes away, running
$ audible-ping 123.123.123.123
on our jukebox computer. (IP address changed to protect the innocent.) We use a literal IP address rather than a DNS name because if your ‘net is AWOL, the DNS query will time out and ping will exit rather than continuing to retry. The script lets us know the very moment our DSL connection comes back.
August 12th, 2005
tonyg
Thinking further on the problem of stateful parsing (from yesterday’s article), the way we’ve done it in the past (essentially by using Scheme’s parameter mechanism) is a special case of a transactional system, with rollback on error and commit after each toplevel expression parsed.
This suggests that if Scheme had an implementation of a Software Transactional Memory, then it would be a good fit for a stateful packrat parser. The symbol-table (or whatever state needs to be speculatively propagated along a line of parsing) would simply be placed under transactional control. Each time an attempt is made to match against a particular nonterminal a nested transaction would be entered. If the nonterminal matched the input successfully, the nested transaction would be committed; otherwise it would be rolled back, and any alternative options would be tried in their own nested transactions.
August 12th, 2005
tonyg
Francis reminded me of the Packrat Parsing algorithm the other day, so I took another look at the Scheme implementation I’d thrown together a few months ago for my ThiNG prototype. Currently, it’s just the basic parsing combinators and support data-structures, but I’d like to make it into an extensible reader, just like for codename. I think I could do a better job this time, since the host language is Scheme and I wouldn’t have to write an interpreter for the macro language, since I’d already have Scheme’s eval available.
The current packrat-parser macro expands into a function representing the parser. To build a quality extensible parsing system, with support for debugging and introspection, I suspect I’d need to move away from representing parsers as functions, and start to move toward representing them in a more self-describing way, perhaps more as objects in the OO sense. For instance, when expanding:
(packrat-parser expr
(expr ((a < - 'num '+ b <- 'num)
(+ a b))
((a <- mulexp) a))
(mulexp ((a <- 'num '* b <- 'num)
(* a b))))
the current implementation produces a parser built directly from packrat parsing combinators (hand-edited slightly for legibility):
(letrec ((expr (lambda (g1687)
(results->result g1687 'expr
(lambda ()
((packrat-or (packrat-check-base 'num
(lambda (A)
(packrat-check-base '+
(lambda (dummy1)
(packrat-check-base 'num
(lambda (B)
(lambda (g1693)
(make-result (+ A B) g1693))))))))
(packrat-check mulexp
(lambda (g1696)
(lambda (g1697) (make-result g1696 g1697)))))
g1687)))))
(mulexp (lambda (g1698)
(results->result g1698 'mulexp
(lambda ()
((packrat-check-base 'num
(lambda (A)
(packrat-check-base '*
(lambda (dummy2)
(packrat-check-base 'num
(lambda (B)
(lambda (g1704) (make-result (* A B) g1704))))))))
g1698))))))
expr)
whereas an extensible parser would require some kind of reified representation of the composite parser, along the lines of
`((expr (or (seq (num + num) ,(lambda (a _ b) (+ a b)))
(seq (mulexp) ,(lambda (a) a))))
(mulexp (or (seq (num * num) ,(lambda (a _ b) (* a b))))))
which could then be interpreted, in order to parse some input, or stepped through, in order to debug a parser or parser extension, or used in various diagnostic printouts to help pinpoint errors in parsed text or parsing extension grammars.
These guys seem to be thinking along the same lines as me, inasmuch as they think packrat-parsing is a good fit for Scheme. I note that they specifically mention stateful packrat parsing as an area of interest; some kind of pseudo-stateful parsing is needed to allow for local grammar extensions (similar to Scheme’s let-syntax), and we’ve come up with a few ideas for solving the stateful-parsing problem that could be tried here.
August 11th, 2005
tonyg
There’s a summary of an interesting discussion regarding semantics in HTML over on fantasai’s blog. Is the HR element only presentational or does it convey something about the content? It does seem to have a semantic role, but one which comes from it being a typographical convention of using a row of asterisks to mark context changes. The interesting bit is what comes after the discussion on HR (and SPAN and DIV); fantasai doesn’t say it explicitly, but Hixie’s proposed reforms to the HTML standard are in the same vein as with HR — they are clarifying what the element means by referring to what the typographical convention means. Compare the Web Applications 1.0 draft to the XHTML 2.0 draft.
August 8th, 2005
mikeb
As widely reported (even enthusiastically by people other than Sun themselves), Java 1.5 (otherwise known as Tiger, otherwise known as 5.0) has generics. This is done by erasure originally for reasons of backwards compatibility. The idea was that Sun wanted to be able to compile source code with generics in it and run the generated bytecode on old JVMs. However, apparently late in the day, Sun decided not to, citing reasons of missing Exception classes which is a fairly surmountable problem.
So, if you have any Java source file and compile it with javac from the Java 1.5 SDK, the resulting .class files blow up JVMs which don’t support Java 1.5. javac has -source and -target flags so you can do javac -source 1.5 -target 1.4 to try to get it to compile code suitable for 1.4 JVMs. javac blows up saying that source release 1.5 requires target release 1.5.
So, I created a very simple HelloWorld style program which didn’t use generics and compiled it twice: firstly with -source 1.4 -target 1.4 and then with -source 1.5 -target 1.5. The resulting .class file has 1 byte difference between the two versions (in fact, just 1 bit difference). So, I then wrote some code that uses generics, compiled with -source 1.5 -target 1.5, checked that it blew up if run on a 1.4 JVM and then edited this 1 byte in the class file. The change worked and as a result I could run the code with generics on a 1.4 JVM.
I then made use of Java libraries that have been genericifiedized, the most obvious example being the Collections API. I made the same hack and sure enough, it worked.
The danger is of course that you write code which uses APIs which were only introduced in Java 1.5 or worse, APIs who’s behaviour has changed between 1.4 and 1.5. Using javac from the 1.5 SDK will compile against the 1.5 libraries. When you run it in a 1.4 JVM, it’ll be run against the 1.4 libraries. So, you could try to change the libraries that javac compiles against, or you could change the libraries that java runs against — you could make the 1.4 JVM use the 1.5 libraries. For that to happen you would have to unpack all of the Jars in the 1.5 JRE, make the hack on every class, reassemble, point the 1.4 JVM at these hacked libraries and then hope that it all works.
Of course, I’m not sure that you would want to run with the 1.4 JVM when the 1.5 JVM is available unless there was specific behaviour that you wanted. If the cost of validating your products against a 1.5 JVM was exhorbitant then you could continue to use a 1.4 JVM but tell your developers to start using generics, hack up a 1.5 javac coupled with the 1.4 libraries and a hack to change this one magic byte as a development environment and get generics at no extra cost.
Oh and the magic byte? Well, look at the .class files in a hex mode (hexl-mode in emacs works well here). The first 4 bytes are ca fe ba be. The next three bytes are all zeros. Then the next byte is 30 (ASCII 0) for 1.4 and 31 (ASCII 1) for 1.5.
August 2nd, 2005
matthew
Previous Posts