My visit this week to Cal­gary to work with Brian and Robin is com­ing to an end and has def­in­itely paid off again. We have another day at least of work ahead of us, but prob­ably not much more real work will get done by then since we still have the FOPARA paper to fin­ish up and get cam­era ready. But, just in the past couple of days we’ve already made tre­mend­ous pro­gress in improv­ing and sta­bil­iz­ing the lan­guage. It won’t be too much longer before “core Pola” is finalized.

I should say there was one inter­est­ing res­ult that Brian told me about. The peek con­struct is a unique con­struct to the lan­guage, which allows one to, under some restric­tions, break affine­ness, i.e., allows one to ref­er­ence a vari­able mul­tiple times to give the pro­gram­mer more express­ive­ness. It’s a del­ic­ate busi­ness since affine­ness is what keeps Pola pro­grams polynomial-​​time, par­tic­u­larly in the con­text of recur­sion. As it turns out, if you remove the recursion-​​symbol restric­tions on peeks — allow­ing recur­sion within the con­di­tion of a peek—but keep the other restric­tions on peeks, you exactly cap­ture PSPACE! We demon­strated this by chan­ging just a couple lines of code, allow­ing recur­sion, and cod­ing up QSAT to play with. (more…)

First, some excit­ing news that I’ve added the Pola pro­ject as my first pro­ject. There is a Sub­ver­sion repos­it­ory for it as well. We’ve been talk­ing about get­ting a site set up around Pola, with examples and user’s guides and maybe some inter­act­ive fea­tures, so this is a very small first step towards that.

Code-​​wise, what I’ve been work­ing on lately is finally try­ing to do bounds infer­ence prop­erly in the imple­ment­a­tion. The bounds infer­ence still isn’t entirely done and what’s there still isn’t work­ing entirely per­fectly, but it is excit­ingly close! Type in any well-​​typed func­tion which relies only on induct­ive data types and it will give you poly­no­mial bound on the run­ning time! Coin­duct­ive data types will come soon.

In an effort to mak­ing my “bor­ing” research blog more inter­est­ing, I’ve now even got a screen­shot! Is code any more excit­ing when it’s in screen­shot form?

The biggest prob­lem I’ve had so far is writ­ing my own Poly­no­mial data type in Haskell. I don’t even need any­thing fancy: I need addi­tion, sub­trac­tion and mul­ti­plic­a­tion of poly­no­mi­als over arbit­rary vari­ables. Sadly I haven’t found any­thing suit­able and had to build my own. I’m a little out of my depth here: it would be a pretty big under­state­ment to say that I’m ignor­ant when it comes to com­puter algebra. It’s a vir­tual cer­tainty that I’m doing my data rep­res­ent­a­tions and arith­metic oper­a­tions in the least effi­cient way pos­sible. But I can’t worry too much about; this isn’t really what my research is about.

If I find time today I think I’ll go through some com­puter algebra sys­tems to find one which has a suit­ably free licence and has a reas­on­able For­eign Func­tion Inter­face (so that I can use it pain­lessly from Haskell). Does such a thing exist?