55311 items (47496 unread) in 19 feeds
Friends
(430 unread)
Build
(32008 unread)
Heads
(327 unread)
News
(14567 unread)
fun
(164 unread)
Friends (100 unread)
![]() |
| From Marriage Equality March |
![]() |
| From Marriage Equality March |
![]() |
| From Marriage Equality March |
![]() |
| From Marriage Equality March |
![]() |
| From Marriage Equality March |
![]() |
| From Marriage Equality March |
Heads up to anyone who reads this; I’ll be in Seattle next Wednesday night, Oct 22. I’ll be around until Saturday morning. Doing some recruiting at UW on Thursday and Friday.
At rallies this week in Florida, crowds jeered and taunted members of the news media. One man hurled a racial epithet at a black television crewman, telling him, "Sit down, boy".Holy crap, it's the two minutes hate! It is sad and truly frightening that this is what the Republican party has come to. They have turned themselves into the party of xenophobia and hate.
Yesterday, for the second time in three days, a speaker at a McCain rally in Pennsylvania referred to Obama's middle name, Hussein, in an effort to cast doubt in his religion and background. Obama is a Christian.
At the same rally, shouts of "terrorist" and "liar" could be heard following references to the Democratic candidate. On Saturday, McCain running mate Sarah Palin sought to link Obama to Ayers. "Kill him!" one man in the crowd shouted, not specifying who.
--The Guardian
It is unsolvable whether or not a context-free grammar is LL(k) for some k>=0: see Rosenkrantz and Stearns, Properties of deterministic top-down grammars, Information and Control 17:226–256, 1970 [www.dx.doi.org](70)90446-8
I’d like to second the // option. Given that an empty regex is not at all useful (at least, I can’t think of any use for one), the syntax can remain unambiguous. Looking at the rules:
s -> a // b;
s -> a / / b;
and
s -> a /x / b;
s -> a / x / b;
it would be a good idea disallow whitespace in the // operator, just to make things even more clear.
"When you try to prove she doesn't know anything, you lose, because audiences are enraptured by her," Halcro said. "And her biting comments give you a sense of how competitive she is. Anybody who doesn't take her seriously does so at their peril."So playing the expectations game that the campaigns love to play, I'd say that we should expect to see an aggressive and in-control Sarah Palin, judging by her previous performances.
One more thing about the new house—
After we moved in, I was doing some work in the crawl space and dropped a nail. Fumbling for it in the dark, I felt something that didn't seem like one of the normal rocks or bricks used to weigh down the black plastic sheeting. I grabbed it and brought it out into the light. It was an 8GB iPhone.
The iPhone was dead, so I took it to work the next morning and borrowed a colleague's charger. When I powered it on and opened the mail program, I could see it belonged to the previous owner of the house. I contacted him at the phone numbers and email address I found in the iPhone. He was very surprised when he responded, wondering where on earth I had found his phone.
Based on some investigation the phone company had done after the phone was lost, he knew that the phone had last been accessed on the day he moved out—after it had turned up missing. With my account, he was able to piece together a possible scenario: One of the movers, or someone else with access to the house, had picked up the phone, checked that it worked, and pocketed it, hoping to steal it. But later the thief became afraid of detection, and ditched the phone in the dark corner where I eventually found it.
I returned the iPhone to its grateful owner. I admit I was a little disappointed that I didn't get to keep it.
I'm sitting at home, unemployed, sick, taking care of a sick child, with no heat and no stove. And feeling pretty good.
My job at blist did not last very long. My peers were great, I feel I contributed a lot, and it was definitely a good change for me. But I was demotivated by the management style there, and the CEO/founder was never satisfied with my effort. So last week, as the company blew past its planned launch date with no shippable product and no achievable end in sight, I was let go. Our two contract engineers also left in the same week. I wish the best to the remaining five engineers. Personally I feel no regret - I knew it wasn't the right place for me, and was already planning on quitting soon.
If you know of a great job opening in Seattle (not including the Eastside, sorry), please see my resume and send me a note. I'm already talking to Google, and I'm on the fence about interviewing at Amazon again.
In other news, we're all moved in to our new house (photos here) and we're having a party this weekend. If you want to come and haven't gotten an invitation yet, just let me know!
I did finally come down with the cold that Sarah and Eleanor have had for over a week now. So my first few days of unemployment have been spent sleeping and reading Anathem. Our heater and other gas appliances are out while we wait for our new natural gas furnace to be approved by the city inspector. We haven't had a working dryer or dishwasher since we moved, or a working stove since our old electric one was hauled away weeks ago. Fortunately it's sunny and warm for once in Seattle, so we have the clothesline and grill set up in the back yard. Here's hoping everything's back to normal soon!









Hm. I’m writing a music catalogue page, with the first line of each score as embedded svg. Works like a charm in Firefox 3.0 on a W*ws box, but strange results on ubuntu: only text elements scale correctly with browser controls
Any hints or tips for resolving this? gratefully received!
Here’s a demo of some the cool things you could do :http://clockamatics.googlepages.com/live.html
Those clocks were written for Linux desktop in svg, all they needed to work in Firefox was javascript.
I fly out tomorrow and it was a great trip but I am ready to be back in the good ol’ USofA. We kept pretty busy for most of the trip except for the last day or so; which was a good for winding down.
It was pretty hot and humid every day I was here so it will be nice to be back in Cali where there is no humidity and nights are cool and refreshing. If you have had the luxury of living or camping in Illinois without AC, you know why night in Cali are awesome.
The play-by-play of the trip is below the fold.
I attended five Olympic events. Basketball, Volleyball, Wrestling, Table Tennis, and Baseball.
We started the trip in Shanghai and planned to spend more time there, but had to get to Beijing to see Yisong’s mom and sister before they flew home. We spent a few days in Beijing and then we flew to Huangshan to do a 3 day trip there hiking the mountains.
After touring Huangshan with Yisong’s cousins we took a night train and another train to their hometown, which is Yisong’s Dad’s hometown. We visited with them and had several good meals and did some shopping and took a night train back to Beijing.
As soon as we got back to Beijing at 8am on the night train, we headed to the Great Wall to do some sightseeing. That night we went to see women’s volleyball and it was an awesome quarter-final match with USA playing Italia.
I woke up the next day early went to the Wrestling venue and tried to see some freestyle wrestling. I figured that I really should watch some wrestling if I came all this way to see the olympics. It turned out that I accidentally went to see the weight classes that I am interested in, 66kg and 74kg (They have a 55kg and a 60kg, which would have also been cool). Even better, it was the 1/8 1/4 and semi-finals. So I basically got to watch the whole bracket for 2 weight classes in 3 hours. Some of these guys wrestled 3 times in under 3 hours, which is pretty tough.
After that success, we went to the 798 art district, which was pretty awesome. If you know me, you know that I’m not that into art, but I could have hung out there all day. There are like 400 galleries with all kinds of crazy art. We then went to see Ari’s friends’ Terra Cotta warrior marionette show, but they changed the times around, so we were late to the last show and they didn’t let us in. We then came back the next day, and it was rained out, so sad times on boats with respect to the show Ari suggested we see.
But all was well because that night we hit up the Peking duck and then did some serious clubbing. Yisong did not join us because he had a talk to give at Microsoft Research Asia in the morning. I however rolled in from partying at like 3:30am and had to wake up at like 7:30 to get ready to go to MSRA. After the talk we went out to a really nice lunch with the Microsoft people and then Yisong had meetings all day. I didn’t want to hang out in his research meetings for the rest of the day, so I met up with Lisa and we tried to go to the Terra Cotta thing (which was rained out), and after that didn’t pan out, we went to the Beijing Zoo and saw some Pandas.
I caught up on sleep that night and we went to see Table Tennis the next afternoon. We decided that partying was in order this Friday night so we started at karaoke and at about 1:30 moved to the clubs. We didn’t get home until like 4:30 and Yisong’s grandparents were just getting up. I thought we were busted for sure because it seemed like they had been waiting for us all night, but they had just gotten up and Yisong smoothed it over like a champ.
We got like 3 hours of sleep and were up for the 10:30am USA bronze metal baseball game. Baseball will not be an Olympic sport next year, so it is pretty awesome that we saw the last USA game of this era. It was a slug-fest with homers and was high scoring and back and forth and was a great game against Japan. We took the bronze and much sun (and beer) was had by all.
That pretty much wraps things up. We walked around the main Olympic area Saturday night; caught up on sleep. Sunday we watched Basketball and the closing ceremony on TV. Monday we went out shopping and hit up the local bars at night. And right now it is Monday night and Yisong and I are working through the last of the 24 pack of beer we bought 2 weeks ago and are being nerds writing our blog posts. yay!
It was a most excellent trip but I miss my life back home and am ready to be back! Now I just have that pesky 16 hours of travel tomorrow.
This might be a lame idea, but could you use // for the prioritized choice? I can not think of a reason why you would want to use // when defining a regular expression. Everybody knows that two is better then one.
Also, | is OR sometimes and || is OR other times, so why not / sometimes and // other times….
re. prioritised choice: How about |>
Wednesday we got into Beijing and went shopping for some cheap stuff. We followed that up with a big family dinner. Later that night we hit up the bar scene and partied late.
On Thursday, we woke up and went to the Forbidden city. Check out pictures here. Yisong and I followed that up with some awesome basketball games. I will send those pictures later, because there are over 400 of them to sort through. China won it’s match with Angola, which was fun to watch. The game of Russia against Lithuania was really close the whole way and was very exciting.
Shanghai is an awesome city. It’s too bad we didn’t get much time to enjoy it or the nightlife. I got in around 9pm and after a bus ride and cab ride, we were at the hotel just after 10. We had some food and got some sleep.
I had tried to fight the jet lag, but I was up at 6am the next morning and went around looking for a coffee shop, but nothing was open yet. We took a cab down to the Bund but the river trips didn’t start till 10am. We got some breakfast and hung out in the restaurant for a while because they had air conditioning and it was hot and really humid out. After the boat trip we hung out at the Jade Garden area and bought some souvenirs and a lot of food. We caught the night train to Beijing at 7pm and that was a 12 hour ride that got us into Beijing at 7:15am.
We took the subway then a taxi to Yisong’s grandparents’ house. We had breakfast, showered up and found an open wireless connection. Now we are about to head out and buy more cheap stuff and hang out in Beijing.
Check out the pictures of Shanghai here
FYI - Opera 9 and Safari 3 have similiar level of support for SVG. Firefox 3.1 should have some level of support for declarative animations (SMIL) as should the next version of Safari (after 3.1). Opera has had SMIL and SVG support for years.
The only browser really not playing the SVG game at the moment is Internet Explorer.
P.S. I was worried that DojoX GFX would have dependencies on a lot of the other (huge) Dojo libraries, but it looks like the dependencies are very minimal. So, that’s another point in Dojo’s favor.
I haven’t tried out dojox.gfx yet - still working down my list of libraries to try. It looks pretty usable and mature. (Raphael on the other hand was first released last week, so it’s hard to say yet.)
My use case is pretty simple (just some black-and-white line drawing), so it probably won’t make that much difference which library I use. At that level, they all have the same features. If I chose Raphael it would probably be because it would be less intimidating to customize or debug the library myself. On the other hand with a more mature library I might not need to.
@Matt: how is Raphaël different than DojoX GFX? Just that it’s more minimalistic?
As I’m adding more capabilities to the Gazelle grammar description language, I’ve come up against a problem for which I can’t find any solution I like. So I’m putting it to you, my esteemed readers, to suggest a solution I will like more than the ones I’ve already brainstormed.
Here’s the problem. I’m at a point where I want to support prioritized choice in Gazelle grammars. Prioritized choice is a way of letting grammar writers explicitly resolve ambiguities that have crept into their grammar. Take the following grammar rule:
s -> "X" | "Y";
The two alternatives in this rule (X and Y) have equal priority. That doesn’t actually matter in this case, since no text can match them both, but now consider changing the rule a bit:
s -> "X" | "X";
Now there is a problem, because an X matches both alternatives. There are two legal parse trees that are both correct according to the grammar. As a result this grammar is ambiguous. A parser doesn’t have any reason to choose one over the other, because they are of equal priority.
The solution to the problem is to let the user specify which alternative should be taken when both match. If we allow users to do this by introducing prioritized choice, our solution looks very much like how Parsing Expression Grammars (also known as PEG’s) work. And the syntax that has become very standard in the PEG literature is to use “/” as the operator for prioritized choice. So our ambiguous grammar would be made unambiguous by using prioritized choice:
s -> "X" / "X";
Now the parser will always choose the first alternative, and the grammar is no longer ambiguous. You might wonder “what’s the point?”, since the second alternative will never be taken, but in many other cases of ambiguity, the choice of lesser priority will be taken. The classic example of ambiguity (which can be resolved in this way) is if-then-else:
stmt -> "if" expr "then" stmt |
"if" expr "then" stmt "else" stmt |
expr;
expr -> "true" | "false" | /[0-9]+/;
This grammar is ambiguous, because the fragment:
if true then if true then 1 else 2
…can be parsed in two different ways. The “else” could be assigned to either “if” — both are valid according to the grammar.
So I definitely know I will be introducing prioritized choice. The question is what syntax to use. Like I mentioned before, I would really really like to use “/” since there is a strong convention from the PEG world for it. But unfortunately this introduces a major ambiguity in Gazelle’s own grammar, because it conflicts with the syntax for regex literals. What does this mean?
s -> a / b;
a -> c / d;
Is that two rules that both use prioritized choice, or is it one rule that has a giant regular expression in it?
s -> a / b;
a -> c / d;
I really don’t want to give up using slashes to introduce regular expression literals, because that is a really strong convention that a lot of programmers are familiar with. But I also really don’t want to give up using the really strongly established convention of using slash for prioritized choice.
Anyone have an idea for a compromise I might like? The only one I can think of is adding a prefix to the regex literals sort of like Perl’s m{} form for regular expressions. It could be something like m/regex/. But I hate to add that uglification to the grammar, especially since regular expressions are going to be SO much more common than prioritized choice.
Any ideas, anyone?
Bonus: the other form of ambiguity resolutionChoice/alternation isn’t the only possible source of grammar ambiguity. Gazelle’s constructs for optional and/or repeating grammar fragments can also be ambiguous. The if-the-else example is perhaps more idiomatically written in Gazelle like so:
s -> "if" expr "then" stmt ("else" stmt)? | expr;
It’s written differently, but it’s just as ambiguous as before. So we need the same sort of tool to resolve this ambiguity — a way to say “prefer to match the optional part” or “prefer to NOT match the optional part.” This is equivalent to defining a “greedyness” to these operators like Perl lets you do in regexes. The syntax I am planning for these is:
s -> a b?; // no preference to match the b or not
s -> a b+; // no preference to keep matching b or not
s -> a b*; // no preference to keep matching b or not
non-greedy variants
s -> a b?-; // prefer to NOT match b (non-greedy)
s -> a b+-; // prefer to STOP matching b (non-greedy)
s -> a b*-; // prefer to STOP matching b (non-greedy)
greedy variants
s -> a b?+; // prefer to KEEP matching b (greedy)
s -> a b++; // prefer to KEEP matching b (greedy)
s -> a b*+; // prefer to KEEP matching b (greedy)
I’m not following the Perl convention here (Perl uses “?” instead of “-” to make the match non-greedy). But on the other hand:
So to write the if-then-else example with explicit ambiguity resolution, you would write:
"if" expr "then" stmt ("else" stmt)?+ | expr;
…because when there is an ambiguity, we want to bind the else to the most recent if.
An aside: “great, so I can just start slapping greedy and non-greedy modifiers on everything, just to be safe, right?”Not so fast there. Ambiguity resolution isn’t something you should take lightly, because a grammar with an ambiguity in it presents a user-facing irregularity in your language. For example, the if-then-else example is a user-facing issue: either “else” pairing makes logical sense, and it’s totally arbitrary how you decide to resolve the ambiguity. You have to tell your users about it. You should strive to absolutely minimize the numbers of such ambiguities in your language whenever you can!
The danger of using ambiguity resolution operators willy-nilly is that you don’t necessarily know if they’re actually resolving ambiguities. For example, if you wrote:
s -> "X" / "Y";
…the prioritized choice here is completely extraneous, since this grammar is unambiguous already. Because ambiguities are so important to keep track of and educate your users about, you don’t want to have to wonder whether a prioritized choice is resolving an ambiguity or not. You want to know that it is.
To this end, Gazelle will keep track of all ambiguity-resolution operators and error if any of them are never actually used to resolve an ambiguity. So you can’t just sprinkle them around “just to be safe,” you must only use them where they are effective. And this will make Gazelle grammars much more useful, because you will know exactly where all your ambiguities are.
By the way, Gazelle can’t detect any ambiguity in your grammar; calculating whether an arbitrary context-free grammar is ambiguous or not is undecidable. Basically, all grammars fall into one of several categories:
If your grammar falls into category 3, Gazelle doesn’t know whether the grammar is ambiguous or not. But for grammars in categories 1 or 2, Gazelle knows exactly where the ambiguities are.
Bonus #2: a word about Parsing Expression GrammarsSomething you might say (especially if you’re a PEG fan) is “gosh Josh, if you’re going to all this work to introduce ambiguity resolution, why not just use PEG’s flat-out and abandon all this LL(*) nonsense?” Because essentially what I’m doing is supporting both PEG-based constructs (like ordered choice) and context-free grammar constructs like non-ordered choice. And PEG’s support a larger set of grammars than Gazelle ever will (I believe they support any non-left-recursive PEG, though I don’t have a reference for this).
There are two really major reasons why I don’t think PEG’s are the way to go. The first one is related to the point I was making before. With PEG’s all choice is prioritized choice. However, with PEG-based tools you have no idea if there are real ambiguities in your grammar or not. PEG’s are defined such that ambiguity does not exist, but this does not make if-then-else style issues go away, it just sweeps them under the rug. Even if you don’t call it “ambiguity,” it is still a user-facing issue that you as a language designer definitely want to know about! If you have the following in a PEG:
s -> a / b;
…you have no way of knowing if this represents an ambiguity, which means that you don’t know if changing the grammar to:
s -> b / a;
…will make a substantive difference or not! You’re flying blind.
The second reason is that Gazelle’s parsing algorithm will be far, far faster than packrat parsing (which is the algorithm used to parse PEG’s). Both algorithms will have linear asymptotic complexity (though as I briefly mentioned before, I believe that LL(*) grammars can degrade to n^2 in degenerate cases; though I will argue that this will never happen in any sane language). But though both are linear, packrat parsing’s constant factor is far higher, and packrat parsing uses O(n) space where n is the size of input.
This might all sound like hot air, but check out these real, hard numbers. On the homepage of the Aurochs parser generator, which uses PEG’s and packrat parsing to parse JavaScript, they say:
How much memory does it use?
An awful lot.
Grammar Input size Memory consumption CPU time Memory overhead Javascript 140kb 380Mb 1s 2700 Javascript 71kb 180Mb 0.45s 2500 Javascript 1717 5.6Mb 0.01s 3200
I can’t vouch for whether this is a great implementation of packrat parsing, but the authors sure seem to know what they’re doing. I hope you’ll agree that 380Mb of memory just to parse 140kb of text is horrendous, and 1s is quite slow too. Gazelle can’t parse JavaScript yet, but here is a rough ballpark estimate of what the performance will be like to parse 140kb of text once it can:
Like I said, the Aurochs authors seem to be very smart — I’m not saying they’ve done a bad job. I’m just saying that if Aurochs is any indication of what we can expect from packrat parsing, it is orders of magnitude slower, and takes enormous amounts of memory even for modest amounts of input text. If anyone has better numbers to show for packrat parsing, I’m all ears.
So even though it’s more work, I’m 110% convinced that using this combination of LL(*) with explicit ambiguity resolution is the way to go, and is the best way to achieve the goals that I have set out for this project.
Every year my family goes camping at Penrose Point with a group of other families that we've known since I was in daycare with them. We reserve the group camp site for two nights, drive in with our tents and coolers and Coleman stoves, and spend most of our time relaxing at the beach or around the campfire. On the second evening we have a party—usually with a theme and costumes. This has been going on for something like 26 years now. Sarah and I skipped last year's trip because we weren't ready to take the baby with us, so this year was our first time camping with Eleanor.
Eleanor was thrilled beyond words with the entire trip. She'd love to spend every hour of every day playing outside, but we normally have to bring her back inside after a couple hours for pesky things like food or sleeping. So camping was like paradise for her. She spent hours playing in the dirt and wading in the lagoon, and thought that eating and sleeping outside were highly amusing. It also helped that we had grandparents and other friends around to keep her entertained when Sarah and I got tired.
Oh, and our Dr Horrible costumes were a hit at the "Musicals" theme party.
I just found Raphaël, which is just the SVG-based, jQuery-like JavaScript library I’ve been searching for! Vector graphics, here I come…
Terence Parr (author of ANTLR) pointed out a mistake I made when I was describing how ANTLR deals with non-LL(*) grammars. I said that ANTLR’s option for dealing with non-LL(*) grammars is to do a depth-first search which runs in exponential time. While I believe this is true if you enable “backtrack=true” alone, ANTLR also has a “memoize=true” option that you can use together with backtrack=true to reduce the time complexity to linear, at the expense of more space.
I also claimed that ANTLR can handle all grammars when backtrack=true is on. Terence corrected me and said that even with backtrack=true, ANTLR does not handle all grammars — for example left-recursive ones. I mistakenly thought that depth-first search parsing would be capable of handling left-recursion, but after some more thought and some time with my trusty Grune and Jacobs I understood why this is not the case. There are other top-down algorithms that can handle this, but backtracking depth-first search (with or without memoization) is not one of them.
Apologies to Terence for my misstatements about ANTLR!
I wanted to follow-up a bit more on my recent posts about the grammars Gazelle and competing parsing frameworks can handle. Here is an Euler diagram showing my current understanding of what grammars Gazelle can handle compared with the well-known Strong-LL language classes as well as competing parsing frameworks.

Gazelle can currently generate lookahead for any LL(k) grammar, all LL(*) grammars that ANTLR can handle, and a few LL(*) grammars (namely tail-recursive ones) that ANTLR cannot. ANTLR can handle all LL(k) grammars and many LL(*) ones. SLK can handle