Multiple Filtered, Infinite, Lazy Streams (and the Sieve of Eratosthenes)

While playing about with some of the problems on Project Euler, I came across this one:

Calculate the 10,001st prime number.

While I find the maths interesting, the real reason I’m working through these problems is to flex some of my Lisp muscles. This particular problem reminded me of a very cool algorithm I saw a while back in “The Structure and Interpretation of Computer Programs” that used a combination of the Sieve of Eratosthenes and infinite, lazy streams.

The principle of the Sieve is as follows:

Every natural number is regarded as a candidate for being a prime number:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ….

We know that 2 is a prime number (we make a note of that). Any multiple of 2 is NOT a prime number, so we remove these from the list:

3 5 7 9 11 13 15 17 19 21 23 25 27 …

3 must be prime (we make a note of that). Any multiple of 3 is NOT a prime number, so we remove these from the list:

5 7 11 13 17 19 23 25 …

5 must be prime (we make a note of that). Any multiple of 5 is NOT a prime number, so we remove these from the list:

7 11 13 17 19 23 …

… and so on.

Implementations of this algorithm are not renowned for their speed; however, I wanted to implement this algorithm to not ony demonstrate the Sieve as a set of multiple filtered infinite lazy streams, but to show how easy it is to implement streams themselves within Scheme (specifically PLT Scheme), if someone has not been kind enough to do this for you already.

A stream is like a list. While a list contains all of its evaluated data, a stream contains only two things: the first item of data, and a promise to generate more of this data should it be asked for.

In Scheme, it’s very easy to implement both a promise to do something, and a means for forcing that promise to be fulfilled:

(define-syntax-rule (make-promise form)
  (lambda () form))
(define-syntax-rule (force-promise promise)
  (promise))

Thus:

(force-promise (make-promise (+ 1 2 3)))  ; => 6

Now, a stream contains a data item, and the promise of further data items. Here is an example of the syntax we’d like to use, inspired by the syntax of list manipulation:

(stream-car (cons-stream 5 7))   ; => 5
(stream-cdr (cons-stream 5 7))   ; => 7
(empty-stream? the-empty-stream) ; => #t

We can implement this as follows:

(define-syntax-rule (cons-stream x y)
  (cons x (make-promise y)))
(define (stream-car s) (car s))
(define (stream-cdr s) (force-promise (cdr s)))
(define the-empty-stream null)
(define (empty-stream? s) (null? s))

The Sieve of Eratosthenes works by repeated filtering on the set of all natural numbers. As no computer has enough memory to contain this entire set of numbers, this makes the method ideal for implementation using streams.

Here, we define a filtering mechanism:

(define (stream-filter pred s)
  (cond ((stream-null? s) the-empty-stream)
        ((pred (stream-car s)) (cons-stream (stream-car s)
                                            (stream-filter pred (stream-cdr s))))
        (else (stream-filter pred (stream-cdr s)))))

… and something to generate an infinite stream of natural numbers…

(define (integers-starting-from n)
  (cons-stream n
               (integers-starting-from (+ n 1))))

… and, hey presto, we now have enough working parts to building the Sieve!

(define (nth-prime N)
  (let iter ([count 1]
             [stream (integers-starting-from 2)])
    (if (= count N)
        (stream-car stream)
        (let ((prime-number (stream-car stream)))
          (iter (+ count 1)
                (stream-filter (lambda (x)
                                 (> (mod x prime-number) 0))
                               stream))))))

(nth-prime 10001)  ; => 104743

This particular implementation finds the 10,001st prime number.
As I said, it’s not an efficient implementation, but I found it to be an incredibly scenic route.

Building Correct Software

An Introduction to Contracts
There are two measures of the quality of software: how correct it is, and how robust it is.

This article is about using Contracts to improve the correctness of software, with the aim of getting it right the first time round.

An implementation’s correctness can only be judged according to its specification. If an implementation could somehow include its specification (or a subset of it), this would be a great step towards it meeting its specification and assessing its correctness.

It’s extremely common for developers to write code that does what they say, and not what they mean. Computers, while incredibly faithful, are utterly stupid, and a great deal of precision is required when instructing them to do something non-trivial. In the business world, Contracts are a formal agreement between partners, clarifying the terms of a relationship. Their purpose is to specify obligations and benefits with clarity, and remove ambiguity. This idea can be used to directly address the correctness of software, by expressing its specification in the form of Contracts which declare the obligations and benefits of routines, and the code that calls these routines.

Contracts are implemented by way of assertions; statements which are believed by the developer to be true. When an assertion is evaluated by the program and found to be true, all is well. But when the assertion is false, the software is deemed to be behaving contrarily to the developer’s expectations.

Assertions are nothing new to most developers. Despite this, they’re rarely used in software and, when they are, tend only to be pulled out of the toolbox after a bug has been found. Once a developer is thinking in terms of Contracts, it becomes second nature for her to make use of assertions before bugs are found, and even before an implementation has been written.

The specification of a routine can be expressed with two sets of assertions:

• Preconditions are checked upon entry to a routine.
• Postconditions are checked upon exit from a routine.

If an assertion fails, then an appropriate exception is thrown. If a precondition was violated, this was due to a bug in the Client (the part of the code that calls the routine). A postcondition violation indicates a bug in the Supplier (the module that supplied the routine being called).

Let’s look at how we would expect a stack to behave (the specification):

Routine Name	Description	Preconditions	Postconditions
Count	Returns the number of items on the stack
IsEmpty	Returns a boolean indicating if the stack is empty		The result should be true if Count = 0, false otherwise
IsFull	Returns a boolean indicating if the stack is full		The result should be true if Count = _capacity, false otherwise
Item	Returns the top-most item without popping the stack	Can only be executed if the stack isn’t empty
Put	Pushes an item onto the stack	Can only be executed if the stack isn’t full	Count must be incremented; the stack must not be empty; the top-most item must be the item just pushed
Remove	Pops an item from the stack	Can only be executed if the stack isn’t empty	Count must be decremented; the stack must not be full; the top-most item is not the item just Removed

_capacity is the number of items a stack may hold. This is a hidden feature (using the convention of a leading underscore to imply this), and is unavailable to the Client

In Python, the implementation of Put would look something like the following…

def Put(item):
    assert not IsFull, "The stack must not be full"
    oldCount = Count   # required for postcondition

    # ...
    # implementation
    # ...

    # postcondition
    assert Count == oldCount + 1, "Count must be incremented"
    assert not IsEmpty, "The stack must not be empty"
    assert item == Item, "The top-most item must be the item just pushed"

Python is good for this first example because it’s quite a nice pseudo-code-looking language. That said, it’s also the last example you’ll be seeing in Python, because it (along with most other programming languages) does not offer support for Contracts. Simply placing assert statements at the beginning and end of a routine simulates Contract-usage only at its most basic level. By examining a language that directly supports Contracts, we will see the full richness that Contracts offer.

Languages that were designed with Contracts in mind have Contract-specific syntax baked into the language. This allows the formal separation of contracts from implementation, opening up assistance from the compiler and automated documentation tools, and offering further advantages that will be addressed. The .Net 4 framework offers a rich Contracts library, called Code Contracts. However, the syntax is sufficiently verbose that it’s not so good for didactic examples. Instead, I shall focus on Eiffel, touted as the poster child for Contract-driven programming. Here is the same example, written using Eiffel notation:

Put(item: G) is
    require
        not IsFull
    do
        -- ...
        -- implementation
        -- ...
    ensure
        CountIncremented: Count = old Count + 1
        NotEmpty: not IsEmpty
        ItemJustPushed: Item = item
    end

A few things to notice about Contract-supportive languages:

• Preconditions and postconditions are formally separated from the implementation using the require and ensure clauses.
• A syntax is provided for accessing the values of expressions from before the routine was executed (old Count, in the example above). This removes the need to store this value separately at the beginning of the routine.
• The syntax allows for Assertion labels, such as CountIncremented, which are used to diagnose which assertion failed
• Preconditions and appropriate postconditions should be available to Client code. In a language that supports Contracts, this is more easily supported within automated document generators and development environments.

So, when the routine Put is called, the precondition is checked. If this fails, an exception is thrown. When this happens, we can be sure that the Client did not fulfill its obligations to the Supplier. If it succeeds, then execution continues as normal. When it’s time to exit the routine, the postcondition is checked. If this fails then an exception is raised, signifying that the Supplier has failed to fulfill its obligation to the Client.

Once decent Contracts in place, it can be easier to see how we go about writing an implementation. It clarifies both the obligations required of the Client code before it may expect the benefits of the routine, and the checklist of tasks that must be achieved within the routine. Assertions help us get our software right in the first place by aiding in analysis, design, implementation and documentation. It is software with reliability built-in, as opposed to reliability achieved through iterations of post-implementation debugging.

When developers are writing Client code, they shouldn’t have to inspect the Supplier’s implementation. In fact, the source may not even be available for inspection. This makes Contracts a very useful device, serving as abstract descriptions for routines.

The whole point of preconditions is that they are available to Client code, giving it a fair chance to ensure the conditions are correct for calling the routine. It would therefore be unfair for preconditions to depend on attributes hidden from the Client. This is why private attributes are not allowed in preconditions, and why a compiler should flag such a violation.

There is no such rule for postconditions. Any postcondition that refers to features that are kept secret from the Client are simply not mentioned in the documentation generated for Client authors.

Preconditions and Defensive Programming
Preconditions allow the Supplier’s implementation to be simpler. The implementation can be written, safe in the knowledge that the preconditions have been satisfied, without having to provide checks for calling errors that may have been passed on from the Client code. Authors often try to achieve robustness by writing routines that accept a wide range of input states, by second-guessing malformed Client requests. Ironically, this can often lead to code that is less robust. It complicates the routine, bringing all the traditional problems associated with such complexity: difficult and costly to maintain, less reliable, brittle, and buggy. It also blurs the distinction between the Client’s and Supplier’s obligations. Is the Client asking something unreasonable of the Supplier? Or, if implemented ‘robustly’, is it a failure of the Supplier’s robustness?

For example, consider a square root function, SQRT. Ignoring complex numbers, it does not make sense to calculate the square root of a negative number. Such a request should be considered an error in the Client code.

SQRT(x: INT) is
    do
        if (x = 0
    do
        -- Remainder of implementation
    end

SQRT(x: INT) is
    require
        x >= 0
    do
        -- Remainder of implementation
    end

The first example of the SQRT function is an example of defensive programming. The idea here is that in order to build reliable software, every component should be designed to protect itself and the Client as much as possible. The second example uses Contracts. Which method to choose is a matter of personal choice, but a stronger case can be made for Contracts.

Any correctness condition required to successfully call a routine should be met by either the Client or the Supplier, but not both (to avoid redundancy). But which one?

• We could assign this responsibility to the Supplier – rather than use a precondition, if…else statements are used to check for unsuitable conditions. The Supplier then handles these somehow. This is the Tolerant approach.
• We could assign this responsibility to the Client – checks are performed to ensure the correct state before calling the Supplier’s routine. This is the Demanding approach.

The Tolerant approach, at first glance, looks quite appealing. It’s common for a Supplier to have multiple Clients, so effort could be saved by placing the ensuring of correctness conditions within the Supplier. But what happens if the Supplier is asked to, for example, pop an empty stack? Within the Supplier, it’s difficult to know how to react appropriately to such a request. Should it be ignored? Is it an error? Should an exception be raised? Should there be a correction, followed by a re-attempt? Should a user-visible message be printed? The Supplier can’t make this sort of decision, because it lacks the context that the Client has. It’s the Client’s role to know why there is an attempt to pop an empty stack, and what this means.

With a Demanding approach, the Supplier does not try to do everything. It aims to perform a well-defined job, and to be strict about cases it cannot handle. A Supplier that computes, checks for abnormal cases, takes corrective actions, notifies Clients and produces results will be complex and could easily fail some or all of these goals. The preconditions are available to Client authors, so it’s obvious what conditions are required to call the routine correctly.

The Tolerant approach is akin to “killing with kindness”, whereas the Demanding approach is like being “cruel to be kind”.
That said, the Tolerant approach still has its uses; for example, dealing with data coming from the outside world: user input, sensor data, …

Class Invariants
Up until this point, everything that has been said about Contracts has been applicable to any programming language paradigm. However, Contracts start to really shine when used in Object-Oriented languages.

To recap, preconditions and postconditions are Contracts that are checked upon entering and exiting a routine, respectively. Together, they characterise routines, providing an abstract description of what they do.

An invariant is a Contract that characterises the properties of an entire class. When any routine of the class is called remotely (i.e. by Client code, outside of the class), the invariant is checked both on entering and exiting the routine.

Returning to our stack example:

1. Put‘s precondition ensures that it may only be called if the stack is not full (Count != _capacity)
2. Remove‘s precondition ensures that it may only be called if the stack is not empty (Count > 0)

While other Contracts also hint at the relationship between Count and _capacity, we only get a clear view of the larger picture once we’ve collected together the fragments to form the invariant:

0 <= Count; Count <=_capacity

As the invariant, this condition must always be met, regardless of which routine is about to be executed, or has finished executing. If it is not true, then an exception is thrown. If the class implementation is correct, the invariant will be satisfied at the following three times:

1. just after the class has been instantiated (and the constructor has been called)
2. just before a remote call to a routine of the class
3. just after a remote call to a routine of the class

Invariants are not checked at other times, as it may be necessary for a class’ routines to violate the invariant if they are to get any useful work done.

Logically speaking, when remote calling a routine, the following assertions are checked;

1. Entering the routine: Invariant AND Precondition
2. Exiting the routine: Invariant AND Postcondition.

So, technically, we don’t need the invariant – we could simply add it to all preconditions and postconditions. This would be a bad idea, for the following reasons:

1. it introduces unnecessary redundancy
2. the invariant states something meaningful about the class as a whole. When merged with preconditions and postconditions, this deeper meaning is lost
3. someone needs to remember to add this invariant to the preconditions and postcondition of every new routine

Plain old Assert
Most languages support the plain old Assert instruction. It expresses a certainty that a property will be satisfied at that point in a computation. As well as providing reassurance, the hypotheses upon which you have been relying are made explicit for future readers of your software. While such Assert statements aren’t really Contracts, this article concerns not just Contracts, but correctness, so it will not be too much of a deviation to give a brief summary.

An invaluable application of the Assert instruction is just before a call to a routine with a precondition. If you are convinced that the call satisfies the precondition, but this is not immediately obvious from the context, the Assert instruction makes your conviction clear. Assertions also remind the reader that the lack of routine call protection is deliberate, and not an oversight.

x = a*a + b*b
Assert(X >= 0)  // because x is the sum of two squares
y = sqrt(x)

(This may be a poor example if you’re a mathematician for whom it _is_ immediately obvious that the sum of two squares is non-negative!)

In software construction, calls and operations usually rely on assumptions that are largely implicit. An author will work hard to convince herself that a particular property always holds at a particular point. Such careful consideration is necessary when writing good quality software. After a while, as memory fades or a project’s resources are re-assigned, all that survives is the text, with no trace of the rationale. If someone (perhaps even the original author) needs to understand the text, they will no longer have access to the resulting assumptions of the mental effort that went into writing the text, and will have to recreate the rationale that the previous author had. If an assumption is non-trivial, document it with an assert statement.

In summary:
Contracts:

1. improve the correctness of software, by embedding specification within implementation.
2. force obligations upon Client (preconditions), which are beneficial to the Supplier.
3. force obligations upon the Supplier (postconditions), which are beneficial to the Client.
4. aid in analysis, design, implementation and documentation.
5. provide an abstract description of whole classes (invariants) and routines, whether or not the source code is available for inspection.

Additionally, assertions provide reassurance to the author, whilst preserving the efforts of reasoning about the code by expressing certainties and hypotheses to future readers.

Building PLT-Scheme on Ubuntu (Intrepid Ibex)

I had reason to build PLT-Scheme 4.1.5 the other day on an Ubuntu system (Intrepid Ibex) (OK, I was trying to get a build of Fluxus up and running).

It was almost entirely straightforward, except for not knowing ahead of time which development packages were needed for the build to complete successfully. As I had to run the process a number of times on an old laptop, it took quite a few hours with a number of manual interventions. Hopefully, the below steps will save someone some time:

1. Go to: download.plt-scheme.org
2. Choose the “Source code for Unix (X11)” platform, and click Download, seleccting the closest location to you.
3. Save the download to its own folder, then untar it with: tar -xzvf plt-4.1.5-src-unix.tgz
4. Change directory, to plt-4.5.1/src
5. You will need a C++ compiler: sudo apt-get install g++
6. Some windowing packages to compile MrEd: sudo apt-get install libX11-dev libxt-dev libxaw7-dev
7. You will also need libcrypto.so to prevent the compilation of the web-server’s scribble documentation from breaking horribly: sudo apt-get install libssl-dev
8. Run the following:
   • ./configure –enable-shared –prefix=/usr/local
   • make
   • sudo make install
9. Your shiny new build will be installed across the following locations: /usr/local/bin;/usr/local/lib/plt/collects;/usr/local/share/plt/doc;/usr/local/lib;/usr/local/include/plt;/usr/local/lib/plt;/usr/local/share/man

Scheme REPLs and readline (or lack thereof)

Most Scheme implementations provide a command-line REPL, allowing you to interactively enter commands and play about with the language. Unfortunately, they can be incredibly frustrating to use out-of-the-box, all because Scheme distributions tend ship without readline support. As far as I can tell, this is down to licensing issues.

readline is what provides the wonderful interactivity of the command line. If you type a long command and notice an error early on in your text, you can navigate to that spot with cursor keys and edit it, rather than having to delete all your text back to that point. It also provides the command history functionality (typing up and down to navigate through commands you have issued in the past).

Trying to use the editing and history features of readline with readline support enabled, you end up with funny-looking characters being spouted into your REPL.

There are two solutions:

1. You can recompile your favourite Scheme implementation with readline support. I have never bothered with this, and just booted up DrScheme instead.
2. Secondly, you can install rlwrap. (You can “apt-get install rlwrap” in Debian/Ubuntu). Once installed, simply invoke “rlwrap {your-favourite-scheme}“, and you magically have readline functionality!
   I have tried this out with mzscheme (it worked fantastically, and it provides you with paren-matching too) and scheme48 (worked well, but no paren-matching).

Now I no longer need to load up the behemoth that is DrScheme when I just want to use a Scheme-based calculator. It took 3 years of dabbling in Scheme before I heard of this. I hope this post saves someone out there some Scheme-related REPL-angst.

Remapping Caps Lock

This week, I bit the bullet and ripped the Caps Lock key out of my keyboard. Not content with that, I ripped out the left Ctrl key too, and stuck it back in where the Caps Lock had been. I didn’t put the Caps Lock back in – I left it on a spike next to my monitor, as a warning against all crap interface design decisions.

Windows

To make the keyboard usable again, I tried the following registry modification: create a file called swapCapCtrl.reg and copy-paste the following lines of text into it:

REGEDIT4
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Keyboard Layout]
"Scancode Map"=hex:00,00,00,00,00,00,00,00,03,00,00,00,1d,00,3a,00,3a,00,1d,00,00,00,00,00


Double-clicking this file and rebooting the computer will swap the Caps Lock and Left Control keys around. To undo this, just fire up regedit.exe and remove the entry that was placed in HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Keyboard Layout and then reboot.

This all works, but you need to go through this rigmarole every time someone who can’t handle this keyboard modification wants to use your computer.

To solve this, download and install AutoHotKey, create a file called swapCapsCtrl.ahk and place the following code in it:

CapsLock::Ctrl
RCtrl::CapsLock

Double-click the file to set the script running in the background, and right-click->Exit its System Tray icon to remove it. This is my preferred method because: I already have and use AutoHotKey; the behaviour is readily toggled; Caps Lock is moved to the Right Ctrl key, where I’m even less likely to hit it accidentally (although, I still find that I do, so I’ve removed that second line entirely).

Linux

Add the following text to your ~/.xmodmap file, then restart your desktop session:

remove Lock = Caps_Lock
keysym Caps_Lock = Control_L
add Control = Control_L

This deals with the X server side of things, but you must do something else to get this effect in a virtual terminal (i.e. when you press Ctrl-Alt-F1, etc.). Edit the file /etc/console-tools/remap, such that it contains the following line: s/keycode 58 = Caps_Lock/keycode 58 = Control/;

If none of the above works for you, for whatever reason, I refer you to Moving The Ctrl Key, over on the Emacs Wiki.

With this keyboard tweak, I did have something of an uncertain start, but it nows feels to have been worth it. Ctrl-Tabbing and Ctrl-Shift-Tabbing between Firefox tabs seems more natural, and I now look at Ctrl-T on my laptop’s unmodifed keyboard and think did I really used to go to all that effort just to open a new tab?.

Mog

I don’t have RSI but, in the past, I’ve been well on the way to developing it thanks to applications that pretty much make the mouse a requirement (oh, and poor posture).

About 6 months ago, I saw Mouser by Adam Pash, over at LifeHacker, and liked it quite a bit.

You navigate in Mouser by effectively throwing away large sections of screen and navigating around the area that remains. For example, if you move the mouse pointer left, the area that was to the right of the cursor is marked as off-limits and the mouse pointer is placed in the centre of the remaining area. It’s like the navigational equivalent of the binary search method.

As cool as it was, it wasn’t quite a replacement for the mouse. So: I reimplemented it, fixed some unresponsiveness and dodgy behaviour, made it more customizable and released it.

I’ve called it mog, and it’s available for download here: http://code.google.com/p/moggie/ (mog was already taken, sadly, and it’s Windows-only for extra sadness).

It’s _still_ not an effective replacement for the mouse… but I believe it qualifies as an acceptable-for-the-time-being alternative. The problem is the number of key presses required to navigate to a 20×20 pixel area (we rarely require pixel precision). If you have two fairly high resolution monitors, the worst case scenario is about 12-14 key presses. I’d guess that about 8 key presses is the average. Unfortunately, it’s easy to make a mistake and, without an undo feature, this will add another 8 key presses. So I’d say the average number of key presses is more like 12. Not very effective.

Fortunately, I have plans to incorporate other navigation methods into mog. Once I’ve run out of ideas, I intend to look at ways of bringing the best of those ideas to other platforms (AutoHotKey is only available for Windows).

Please do let me know what you think, criticisms and praise both accepted.

Vimperator

Being rather keen on Vim and mouseless-ness in general, I was chuffed to discover Vimperator, a Firefox extension for providing a Vim-like interface to web-browsing. If you’re not already familiar with Vim, this may not be an extension you’ll be wanting to try out soon. At least, not until you’re accustomed to and happy with Vim. Or perhaps I’m wrong, and Vimperator will lead you to Vim. That would be weird.

Vim is a modal text editor. This means you flip between two different modes: one for entering text, and one for doing things with the text, such as manipulation and navigation. Learning Vim can be profoundly irritating to learn, because beginners invariably end up typing text whilst in the wrong mode, and wonder why critical pieces of their novel have had the William Burroughs Cut-up Technique applied. In the end, for many people, this infuriation pays off and we find it actually works pretty well for us. I’m really interested to see how a modal web browser will work for me.

Firstly, download the extension from vimperator.mozdev.org (look for it hovering on the right-hand side). After restarting Firefox, you’ll find things look a little different. In the spirit of Vim, the tools and widgets at the top of the brower window will have been hidden. These can be brought back by hitting escape, and typing :set guioptions+=mT (it can be hidden again with :set guioptions-=mT).

To start off the tour, we’ll do a web search in a new window. ‘:wo google.com’ will open a new window and take you to google.com. Do that, then arrange the window such that it can be seen alongside this text.

• Press f – this places you in QuickHint mode. A small label is placed next to each interactive element on the page. Type the label name for the main Google search box in lower-case. This gives the search box focus. Search for ‘vimperator’.
• Use j and k to scroll up and down the page. If this is too slow for you, Ctrl-f and Ctrl-b will do this a page at a time. Firefox’s default bindings of spacebar and Shift-spacebar work equally well. gg and G scrolls to the beginning and end of the document, respectively.
• Follow a link by using the above method.
• You can return to the previous page by press H. You can move forward through the browser history by pressing L.
• Follow a link using the above method, but this time enter the label name in upper-case. This causes the page to be loaded in a tab.
• You can move between tabs using gt and gT.
• d closes a tab, and u brings it back.
• t opens a new tab, inviting you to enter a URL in the status bar.
• ZZ closes the entire browser window.
• Occasionally, there will be a need to disable Vimperator’s handling of key presses. Pressing I will cause Vimperator to ignore key presses by handing them straight on to the next event handler. GMail is one such service that can require this feature.
• Vimperator’s search features are exactly as found in Vim: / searches forwards, ? searches backwards. n and N search for the next and previous result, respectively.

Vimperator has quite a bit more to offer than this. I’ve just listed the features that I personally need to browse mouselessly. If you want to learn more about what Vimperator is capable of, type :help. There’s also a mailing list and a wiki.