sjs - geeky ramblings

Project Euler code repo in Arc

2008-03-04T00:24:00Z

Release early and often. This is a code repo web app for solutions to Project Euler problems. You can only see your own solutions so it’s not that exciting yet (but it scratches my itch… once it highlights syntax). You can try it out or download the source. You’ll need an up-to-date copy of Anarki to untar the source in. Just run arc.sh then enter this at the REPL:

arc> (load "euler.arc")
arc> (esv)

That will setup the web server on port 3141. If you want a different port then run (esv 25) (just to mess with ‘em).

Thoughts on Arc

2008-02-19T19:26:00Z

NB: This is just a braindump. There's nothing profound or particularly insightful in this post.

You may have heard that Paul Graham recently released his pet dialect of Lisp: Arc. It's a relatively small language consisting of just 4500 lines of code. In just under 1200 lines of PLT Scheme the core of Arc is defined. The rest of the language is written in Arc itself. The heart of that is a file arc.arc, weighing in at 1500 lines. The remaining 1000-1300 lines are spread between libraries, mainly for writing web apps: html.arc, srv.arc, app.arc, and a few others.

I'm not going to go into great detail, but Arc is a fun language. You can read all the code in one or two sittings and start hacking on it in no time. The code is simple where simple gets the job done and if you can follow SICP then you should understand it with relative ease (assuming you're somewhat familiar with Lisp).

Parsing, Markdown

I'm writing a simple parser combinators library (loosely modeled on Parsec) in order to write a nice Markdown implementation. Overkill? Indeed. Parsec is a wonderful library and it is written beautifully. If I end up with something 1/2 as powerful and 1/10th as beautiful I'll be pleased. This was all in order to beef up the version of Markdown bundled with Arc so I could write a basic wiki. I've been beaten to the punch, twice! Perhaps I'll retrofit Markdown onto jgc's wiki once I get something decent finished.

Brevity and Innovation

The brevity of Arc is both a blessing and a curse. On the one hand it makes for a very hacking-friendly language. It's easy/fun to try things in the REPL and write throwaway code for learning purposes. Paul's wanton removal of extraneous parentheses is a great boon. On the flip side Arc code can be a little cryptic at a first glance. While reading code there's a small period of time where you have to figure out what the short names are and what they do, but because the language is so small it's utterly trivial to grep or read the source and find out exactly how everything fits together and get the context you need. Once you're familiar with the domain then the terse names not only make sense, but they make the interesting parts of the code stand out more. I want to emphasize the pleasure of using Arc to learn. I think that Paul is on to something with the general brevity and simple nature of Arc.

Some interesting ways that Paul has reduced code is by introducing new intra-symbol operators. Besides the usual backquote/quasiquote and comma/unquote translations, several other special characters are translated when they appear within/around symbols.

There is the colon/compose operator that reduces code such as: (sym (string "pre-" something "-suffix")) to (sym:string "pre-" something "-suffix"). It can help with car/cdr chains without defining monstrosities such as cadadr, though whether (cadadr ...) is better than (cadr:cadr ...) is better than (car (cdr (car (cdr ...)))) is up to you.

My favourite is the tilde to mean logical negation: no in Arc, not in most other languages. It doesn't shorten code much but it helps with parens. (if (no (empty str)) ...) becomes (if (~empty str) ...). Not much to be said about it, but it reads very nicely in code.

Some newer ones are the dot and exclamation point to aide in the composition of functions requiring arguments. I won't go into detail as their use is trivial. If you're interested read Paul's explanation of them.

Web programming

Paul has touted Arc as a good web programming language, most notably in his Arc Challenge that caused a minor stir in a few blogs and on Reddit. I'm writing a small web app for myself in Arc. I may host it somewhere public when it's useable. It's a somewhat pastie-like app specifically for storing/sharing solutions to problems over at Project Euler, which I recently started tackling. "What's wrong with saving the code on your hard disk without a web app?", you ask? It doesn't give me an excuse to try Arc as a web language. ;-)

So far I find that Arc is quite a nice web language. With the handy HTML tag library you can generate 90s-style, quirks-mode-compliant tag soup in a blink. I haven't had trouble producing HTML 4.01 (strict) that validates. There's no need for a template language or partials (à la Rails), you just compose tags-as-sexps using Arc itself. This turns out to be quite elegant, even if somewhat reminiscent of my first forays into web programming with PHP. I don't feel as if I'm writing a web app so much as I'm writing an app that happens to present its UI in HTML. (I'm reminded a little of web.py, which I enjoy as the antithesis of Rails.) I suppose it takes some discipline to separate your logic & design when everything's mixed in the same file, but there's nothing stopping you from separating the logic and views into their own files if you really prefer to do it that way.

There's no distinction between GET and POST params. This surprised me, but then I thought about it and it's not a big deal for most apps, imo.

The app I'm writing is standard CRUD stuff so I haven't done anything cool using continuations yet. I plan to use call/cc for backtracking in my parser, but I'm still a ways from implementing that kind of functionality!

Non-conclusion

I feel as though I should have a conclusion, but I don't. I've only been using Arc for a short time. It feels nice. I think Paul is doing a good job on the design by keeping it small, compact, and simple. Seeing as it's still in its infancy it's just a toy for me, but a toy with some decent potential. And hopefully an impact on other Lisps. Common Lisp may have industrial implementations and a 1500 page spec, but Arc is more fun and hackable. More so than Scheme, too. I think Arc has out-Schemed Scheme.

Random pet peeve of the day

2008-01-08T01:42:00Z

So long since my last post, and all I’m going to do is complain. ;-) Seriously though, if you have a website and the content on said site is dated then please – for the love of our almighty saviour, the Flying Spaghetti Monster – put the date at the top of the page. Don’t make me scroll down to the end of the article just to see how relevant it is or just to give me some context. Not to mention that I always end up doing a “Where is the end? Oh crap, I passed it and now I’m in the comments, blargh!”

I’m looking at Lifehacker since they’re the most recent offender I’ve come across, but they are definitely not the only ones guilty of this.

Gtkpod in Gutsy Got You Groaning?

2007-10-30T04:14:00Z

I recently upgraded the Ubuntu installation on my workstation from Feisty Fawn to Gutsy Gibbon and for the most part I am happy with the changes. One thing I don’t care much for is the fact that gtkpod-aac is a sham. Ubuntu provides the gtkpod-aac package for one to transfer aac files, and thus mp4 files with aac audio tracks, to their iPod. The version in the Gutsy repos is broken. This shows a weakness in Ubuntu, and though it’s rather small it is one that will piss off a lot of people who expect things to just work. The kind of people who would buy an iPod. The kind of people who use Linux. The kind of Linux users that use Ubuntu. The kicker is that it doesn’t look like they will ship a working version of gtkpod-aac for Gutsy at all. I know it’s only 6 months but that seems like an eternity when you have the same old crap to watch on your iPod for that long.

All is not lost. A kind soul left a helpful comment on the bug report explaining how he got it to work. It’s a pretty simple fix. Just google for libmpeg4ip and find a Debian repo that has the following packages for your architecture:

libmpeg4ip-0
libmpeg4ip-dev
libmp4v2-0
libmp4v2-dev

Download those 4 .deb files and install them. You can ignore any advise to use an older version in the official repo. Once you have those installed, download and build the latest version of gtkpod from their Subversion repo.

Now that you know what to do I’ll give you what you probably wanted at the beginning. As long as you have wget, subversion, and use a Bourne-like shell this should work for you.

↓ gtkpod-aac-fix.sh

mkdir /tmp/gtkpod-fix
cd /tmp/gtkpod-fix
wget http://ftp.uni-kl.de/debian-multimedia/pool/main/libm/libmpeg4ip/libmp4v2-0_1.5.0.1-0.3_amd64.deb
wget http://ftp.uni-kl.de/debian-multimedia/pool/main/libm/libmpeg4ip/libmp4v2-dev_1.5.0.1-0.3_amd64.deb
wget http://ftp.uni-kl.de/debian-multimedia/pool/main/libm/libmpeg4ip/libmpeg4ip-0_1.5.0.1-0.3_amd64.deb
wget http://ftp.uni-kl.de/debian-multimedia/pool/main/libm/libmpeg4ip/libmpeg4ip-dev_1.5.0.1-0.3_amd64.deb
for f in *.deb; do sudo gdebi -n "$f"; done
svn co https://gtkpod.svn.sourceforge.net/svnroot/gtkpod/gtkpod/trunk gtkpod
cd gtkpod
./autogen.sh --with-mp4v2 && make && sudo make install
cd
rm -rf /tmp/gtkpod-fix

Python and Ruby brain dump

2007-09-26T17:34:00Z

It turns out that Python is the language of choice on the OLPC, both for implementing applications and exposing to the users. There is a view source key available. I think Python is a great choice.

I’ve been using Ruby almost exclusively for over a year but the last week I’ve been doing a personal project in Python using Storm (which is pretty nice btw) and urwid. I’m remembering why I liked Python when I first learned it a few years ago. It may not be as elegant as Ruby, conceptually, but it sure is fun to code in. It really is executable pseudo-code for the most part.

I’m tripping up by typing obj.setattr^W^Wsetattr(obj and def self.foo^W^Wfoo(self but other than that I haven’t had trouble switching back into Python. I enjoy omitting end statements. I enjoy Python’s lack of curly braces, apart from literal dicts. I hate the fact that in Emacs, in python-mode, indent-region only seems to piss me off (or indent-* really, anything except TAB). I really like list comprehensions.

The two languages are so similar that at a glance you may think there are only shallow differences between the languages. People are always busy arguing about the boring things that every language can do (web frameworks anyone?) while ignoring the interesting differences between the languages and their corresponding ecosystems.

Python has more libraries available as it’s the more popular language. The nature of software written in the languages is different though as the languages themselves are quite different.

Ruby has some Perl-ish features that make it a good sysadmin scripting language, hence we see nice tools such as Capistrano and god written in Ruby and used by projects written in other languages.

Python is faster than Ruby so it is open to classes of software that would be cumbersome in Ruby. Source control, for example. You can write a slow SCM in Python though, as Bazaar demonstrates. You could probably write a passable one in Ruby as well. If it didn’t quite perform well enough right now it should fare better in a year’s time.

I still think that my overall joy is greater when using Ruby, but if Ruby isn’t the right tool for the job I’ll probably look to Python next (unless some feature of the problem indicates something else would be more appropriate). The reason I chose Python for my current project is because of libs like urwid and I needed an excuse to try out Storm and brush up on my Python. ;-)

Learning Lisp? Read PCL

2007-09-25T16:59:00Z

Yes, it’s a book. But it’s so well written you should breeze through it as if it were a Lisp tutorial!

Captivating little creatures

2007-08-26T19:35:00Z

Someone posted this JavaScript implementation of an old gem on Reddit, Lemmings! There goes my Sunday! :)

Cheat productively in Emacs

2007-08-22T01:20:00Z

By now you may have heard about cheat, the command line cheat sheet collection that’s completely open to editing, wiki style. A couple of weeks ago I posted cheat.el which allows one to cheat from within Emacs. There’s an update. However, before I get to cheat.el there’s a small detour.

Cheat is not just about Ruby! A few examples of cheats available are:

bash and zsh
$EDITOR (if you happen to like e, TextMate, vi, emacs, RadRails, ...)
GNU screen
Version control (darcs, svn, git)
Firebug
Markdown and Textile
Oracle and MySQL
Regular expressions
and of course Ruby, Rails, Capistrano, etc.

As of today, Aug-21 2007, the count is at 166 cheat sheets so there’s probably something there that you’ll want to look up from the command line or Emacs sometime. That’s enough stroking cheat’s ego, but there seems to be a notion that cheat is only for Ruby stuff and that’s really not the case.

So what’s new in this version of cheat.el? Completion! The only thing that bothered me about cheating in Emacs was the lack of completion. It now has completion, thus it is now perfect. :) In all likeliness this won’t be the last release, but I can’t really foresee adding anything else to it in the near future. Enjoy!

Download it now: cheat.el

For any newcomers, just drop this into ~/.emacs.d, ~/.elisp, or any directory in your load-path and then (require 'cheat). For more info check the original article for a rundown on the cheat commands.

Catch compiler errors at runtime

2007-08-20T05:17:00Z

While coding just now I had a small epiphany about Ruby. Though Ruby is highly dynamic and compiled at runtime, that doesn’t preclude one catching some mistakes at compile time. I’m not talking about mere syntax errors or anything either. The only proviso to catching mistakes at compile time is that you must have a decent chunk of code executed during compilation. One benefit of Ruby’s blurring of compile time and runtime is that you can run real code at compile time. This is largely how metaprogramming tricks are pulled off elegantly and with ease in projects such as Rails.

Sure you won’t get all the benefits of a strictly and/or statically typed compiler, but you can get some of them. If you have a library that makes substantial use of executing code at compile time then the mere act of loading your library causes your code to run, thus it compiles. If you require your lib and get true back then you know the code that bootstraps the runtime code is at least partially correct.

Compile time is runtime. Runtime is compile time. Just because you have to run the code to compile it doesn’t mean you can’t catch a good chunk of compiler errors before you send out your code. Tests will always be there for the rest of your mistakes, but if you can pull work into compile time then Ruby’s compiler can augment your regular testing practices.

I admit that this is of limited use most of the time, but let it not be said that you can’t catch any errors with your compiler just because you have to run your code to compile it. With Ruby the more meta you get the more the compiler rewards you.

[Of course this is true of languages such as Common Lisp too, which make available the full programming language at compile time. I just happened to be using Ruby when I realized this.]

Opera is pretty slick

2007-08-11T19:11:00Z

Though I usually prefer free software, I don’t have any problems using proprietary stuff if I think it’s good. I had Firefox open for a couple of days and noticed that it was using 700M of memory. That’s not a problem at all since I have 4G but it’s also a lot of RAM to be in use for just one window with one tab open. The fact that Firefox gets sluggish after some time and needs to be restarted tells me that this isn’t expected behaviour and is likely not due to caching for quick back/forward or whatever they claim is taking up the leaked memory.

Konqueror is ok but I’m not a huge fan of it, partly due to its kitchen-sink browser/file manager hybrid design. IMO the KDE folks should break out the file manager part, but I digress. I can’t really put my finger on anything specific I dislike about Konqueror, it’s just not for me. To my dismay it seems to be the snappiest browser on Linux.

The only other decent browser I know of (for Linux) is Opera so I found some quick instructions on the Ubuntu forums and shoehorned the x86 build of it into my amd64 installation. Everything went well, Flash works and all that stuff. Opera is not nearly as snappy as I like but it is still fairly pleasant to use, once you find a skin that fits into your desktop. For the record Firefox isn’t snappy enough either. Apart from AdBlock I don’t miss many extensions for every day browsing.

I’m not sure if I’m going to stick with it yet but I’ve been using it for 2 days and haven’t really missed Firefox at all. Of course as soon as I do any development I need Firefox for Firebug and the Web Developer extension and such. I’ve yet to investigate development tools on Opera. I’m comfortable developing in Firefox already so why switch?

Man am I glad we’re not in a Netscape/IE world anymore! If I open up my MacBook I can choose from at least 2 other browsers for every day browsing (Camino, Safari).

Cheat from Emacs

2007-08-10T08:56:00Z

Update: I had inadvertently used string-join, a function provided by something in my ~/.emacs.d. The script has been updated to work with a vanilla Emacs (23, but should work with 22 as well).

Update #2 [2007.08.10]: Editing cheats and diffs have been implemented.

Update #3 [2007.08.21]: I added completion to cheat.el. The file linked on this page is still the latest version.

We all know and love cheat. Now you can cheat without leaving Emacs (and without using a shell in Emacs).

Just save cheat.el in ~/.emacs.d and then (require 'cheat) in your ~/.emacs. I also bind C-z C-c to cheat, you may want to do something similar.

~~You can’t do everything you can do with cheat on the command line yet~~, and for most of the commands the cheat command itself is used. Now you can do everything the command line client does from within Emacs, though you may need to revert to using cheat-command (described below).

Here’s the rundown:

Any time you enter a cheat name there are both completion and a cheat-specific history available. Unless you are adding a new cheat. In that case you should use a new, unique name (duh).

cheat – Lookup a cheat sheet interactively (cheat <name>)
cheat-sheets – List all cheat sheets (cheat sheets)
cheat-recent – List recently added cheat sheets (cheat recent)
cheat-versions – List versions of a cheat sheet interactively (cheat <name> --versions)
cheat-clear-cache – Clear all cached sheets.
cheat-add-current-buffer – Add a new cheat using the specified name and the contents of the current buffer as the body. (cheat <name> --add)
cheat-edit – Retrieve a fresh copy of the named cheat and display the body in a buffer for editing.
cheat-save-current-buffer – Save the current cheat buffer, which should be named *cheat-<name>*.
cheat-diff – Show the diff between the current version and the given version of the named cheat. If the version given is of the form m:n then show the diff between versions m and n. (cheat <name> --diff <version>)
cheat-command – Pass any arguments you want to cheat interactively.

(Added) ~~I may add support for --diff and --edit in the future.~~

Please do send me your patches so everyone can benefit from them.

Snap, crunchle, pop

2007-08-09T17:17:00Z

I think that every now and then we need to be reminded of the frail nature of our human bodies. Yesterday morning as I walked to my kitchen I was turning right by pivoting on my right foot when my 24 years of walking experience suddenly failed me. I clearly did something wrong, as I heard a crunching pop or two in my right ankle and went down. Luckily it’s just a sprain but my foot is fairly bruised and still sore today. I’m trying to follow the RICE method for recuperating but one can only lay down for so long before having to eat, work, use the bathroom, etc. Thank goodness I don’t work on my feet or I’d be out of commission. If it still hurts next week I’m going to see a doctor but till then I’m trying not to leave my house. The idea of hopping and hobbling to a bus to go to a doctor does not thrill me in the slightest.

Oh, if you find yourself in a bind an upside down hockey stick is a decent makeshift crutch. You’ll need 2 hands to operate the thing though.

At the opposite end of the spectrum there are times when we seem to be amazingly resilient creatures. Check out a documentary called “101 Things Removed from the Human Head” if you can find it anywhere. One of those things was a boat anchor, I kid you not.

ElSchemo: Boolean logic and branching

2007-08-02T23:59:00Z

Well it has been a while since my last post. I’ll try not to do that frequently. Anyhow, on to the good stuff.

I’ve been developing a Scheme interpreter in Haskell called ElSchemo. It started from Jonathan’s excellent Haskell tutorial which I followed in order to learn both Haskell and Scheme. Basically that means the code here is for me to get some feedback as much as to show others how to do this kind of stuff. This may not be too interesting if you haven’t at least browsed the tutorial.

I’m going to cover 3 new special forms: and, or, and cond. I promised to cover the let family of special forms this time around but methinks this is long enough as it is. My sincere apologies if you’ve been waiting for those.

Short-circuiting Boolean logic

Two functions from the tutorial which may irk you immediately are and and or, defined in Scheme in the given standard library. If your code is free of side-effects then it may not bother you so much. It bothered me. The problem with the implementation in stdlib.scm is that all the arguments are evaluated before control enters the function. Besides being inefficient by doing unnecessary work, if any of the arguments have side-effects you can make use of short-circuiting by using and to sequence actions, bailing out if any fail (by returning nil), and using or to define a set of alternative actions which will bail out when the first in the list succeeds (by returning anything but nil). Had we macros then we could implement them as macros. We don’t, so we’ll write them as special forms in Haskell.

Unlike the special forms defined in the tutorial I’m going to implement these as separate functions for clarity, rather than lump them all in eval. However, they will be invoked directly from eval so their type is easy; it’s the same as eval’s.

Code first, ask questions later. Haskell is a pretty clear and concise language. My explanations may be redundant because of this.

lispAnd

lispAnd :: Env -> [LispVal] -> IOThrowsError LispVal
lispAnd env [] = return $ Bool True
lispAnd env [pred] = eval env pred
lispAnd env (pred:rest) = do
    result <- eval env pred
    case result of
      Bool False -> return result
      _ -> lispAnd env rest

Starting with the trivial case, and returns #t with zero arguments.

With one argument, a single predicate, simply evaluate and return that argument.

Given a list of predicates, evaluate the first and inspect its value. If the argument evaluated to #f then our work is done and we return #f, otherwise we keep plugging along by making a recursive call with the first argument stripped off. Eventually we will reach our base case with only one predicate.

It’s possible to eliminate the case of one predicate. I think that just complicates things but it’s a viable solution.

lispOr

Predictably this is quite similar to lispAnd.

lispOr :: Env -> [LispVal] -> IOThrowsError LispVal
lispOr env [] = return $ Bool False
lispOr env [pred] = eval env pred
lispOr env (pred:rest) = do
    result <- eval env pred
    case result of
        Bool False -> lispOr env rest
        _ -> return result

With no arguments lispOr returns #f, and with one argument it evaluates and returns the result.

With 2 or more arguments the first is evaluated, but this time if the result is #f then we continue looking for a truthy value. If the result is anything else at all then it’s returned and we are done.

A new branching construct

First let me define a convenience function that I have added to ElSchemo. It maps a list of expressions to their values by evaluating each one in the given environment.

12	evalExprs :: Env -> [LispVal] -> IOThrowsError [LispVal]evalExprs env exprs = mapM (eval env) exprs

lispCond

Again, lispCond has the same type as eval.

lispCond :: Env -> [LispVal] -> IOThrowsError LispVal
lispCond env (List (pred:conseq) : rest) = do
    result <- eval env pred
    case result of
        Bool False -> if null rest then return result else lispCond env rest
        _ -> liftM last $ evalExprs env conseq

Unlike Lisp – which uses a predicate of T (true) – Scheme uses a predicate of else to trigger the default branch. When the pattern matching on Atom "else" succeeds, we evaluate the default expressions and return the value of the last one. This is one possible base case. Atom "else" could be defined to evaluate to #t, but we don’t want else to be evaluated as #t anywhere except in a cond so I have chosen this solution.

If the first predicate is not else then we evaluate it and check the resulting value. If we get #f then we look at the rest of the statement, if it’s empty then we return #f, otherwise we recurse on the rest of the parameters. If the predicate evaluates to a truthy value – that is, anything but #f – then we evaluate the consequent expressions and return the value of the last one.

Plumbing

Now all that’s left is to hook up the new functions in eval.

123	eval env (List (Atom "and" : params)) = lispAnd env paramseval env (List (Atom "or" : params)) = lispOr env paramseval env (List (Atom "cond" : params)) = lispCond env params

You could, of course, throw the entire definitions in eval itself but eval is big enough for me as it is. YMMV.

Done!

So, that’s a wrap. It only took 20 lines of code for the 3 new special forms, and it could easily be done with less code. Next time I will show you how to implement the various let functions. Really!

Do you like me describing ElSchemo piece by piece as I have been? I plan on posting the Haskell code and my stdlib.scm in their entirety sometime, and I could do that before or after I finish writing about the features I’ve developed beyond the tutorial. Just let me know in the comments.

people

2007-07-12T19:28:00Z

Sometimes this is difficult to remember for someone who (likes to think that he) thinks somewhat logically.

When dealing with people, let us remember that we are not dealing with creatures of logic. We are dealing with creatures of emotion, creatures bristling with prejudices and motivated by pride and vanity.

—Dale Carnegie, How to Win Friends and Influence People

See your regular expressions in Emacs

2007-07-06T23:45:00Z

First, if you are an Emacs newbie then be sure to read (at least) the introduction of Being Productive with Emacs. For some reason the PDF and HTML versions are slightly similar.

Anyway, it mentions re-builder which is an awesome little gem if you use regular expressions at all¹. What this baby does is open a small window at the bottom of your screen in which you can type a regex. It is parsed as you type it and matches are highlighted in the other window. Genius.

[1] If you don’t use them I encourage you to “learn them”http://regex.info/. Don’t pay any attention to Jamie Zawinsky and his lack of appreciation for a fantastic tool.