Thursday, December 18, 2014

Gopher

The Gopher protocol is relatively dated now, but when it was first released in 1991, it had a number of modern features that we would later enjoy in the World Wide Web. In particular, in RFC 1436, it lists these features:

  • A file-like hierarchical arrangement that would be familiar to users.
  • A simple syntax.
  • A system that can be created quickly and inexpensively.
  • Extending the file system metaphor, such as searches.

We're going to build a simple word to let us look through Gopherspace using Factor.

Using the URLs vocabulary, we will build a tool to fetch documents from a Gopher server using a URL that looks like this:

gopher://gopher.floodgap.com/0/gopher/proxy

This specifies a host, an optional port (defaulting to 70 if not specified), and a path which includes an item type and a selector identifying the document to obtain.

Once a network connection is opened, we can retrieve the specified document by sending the selector followed by a CRLF (carriage return and line feed, ASCII bytes 13 and 10 respectively), and then reading the response:

: get-selector ( selector -- document )
   "/" split1 "" or nip write "\r\n" write flush contents ;

: gopher ( url -- document )
    >url {
        [ host>> ]
        [ port>> 70 or <inet> ascii ]
        [ path>> rest ]
    } cleave '[ _ get-selector ] with-client ;

The item type, which we are ignoring in the code above, can be used a bit like a filename extension to handle documents of different types in particular ways. Some common types that you might see:

  • 0 - plain text
  • 1 - menus
  • 9 - binary
  • s - sound
  • g - GIF images

Right now, our code assumes that all the documents we will fetch are ASCII, and it doesn't have any special handling for menus, or support for a query string that would allow using Gopher "search servers". I added some basic support for those items in the new gopher vocabulary that I committed yesterday. In addition, I built a simple Gopher browser complete with history support and ability to view GIF images in the gopher.ui vocabulary.

Here's how you would use it:

IN: scratchpad USE: gopher.ui

IN: scratchpad "gopher://gopher.floodgap.com/1"
               open-gopher-window

That will pop up a window that looks like this, with clickable links and everything:

It's neat using some of these early protocols, both because they tend to be simpler, but especially when you see that they have a passionate following. As of December 2014, Veronica-2 has indexed 150 gopher servers with over 3 million unique selectors. You can see current stats by going to:

gopher://gopher.floodgap.com/0/v2/vstat

Check it out!

Wednesday, December 3, 2014

Binary Puzzle

I've enjoyed being a subscriber to The ListServe, a mailing list where each day one subscriber wins a lottery to write to the entire list of over 24,000 subscribers. There has been a lot of life advice, stories, recipes, music and book recommendations, and even puzzles posted to the list. You can see some of the past posts on The ListServe Blog.

In today's post, someone includes a quick puzzle, which (semi-spoiler alert!) I wanted to show how to solve using Factor:

One preachy puzzle (easy to solve with the aid of the Internet, and therein lies the irony): 01001000 01110101 01101101 01100001 01101110 01110011 00100000 01100001 01110010 01100101 00100000 01101101 01101111 01110010 01100101 00100000 01110100 01101000 01100001 01101110 00100000 01100100 01100001 01110100 01100001

At first glance, it looks like binary numbers separated by spaces in a sequence with some meaning, probably some kind of sentence, probably in English, and probably ASCII encoded.

Let's try and solve it with that in mind:

"""
01001000 01110101 01101101 01100001 01101110 01110011
00100000 01100001 01110010 01100101 00100000 01101101
01101111 01110010 01100101 00100000 01110100 01101000
01100001 01101110 00100000 01100100 01100001 01110100
01100001
"""
[ blank? ] split-when harvest [ bin> ] "" map-as .

It's a neat message, but I won't spoil the answer for you.

Tuesday, December 2, 2014

Heaps

Yesterday, I committed a performance improvement to the heap implementation in Factor.

There's an interesting comment on the pypy implementation of the "heapq" module that discusses a performance optimization that takes advantage of the fact that sub-trees of the heap satisfy the heap invariant. The strategy is to reduce the number of comparisons that take place when sifting items into their proper place in the heap.

Below, I demonstrate the time it takes to run our heaps benchmark and to sort 1 million random numbers using heapsort, before and after making the change.

Before:

IN: scratchpad gc [ heaps-benchmark ] time
Running time: 0.224253523 seconds

IN: scratchpad 1,000,000 random-units gc [ heapsort drop ] time
Running time: 2.210408992 seconds

After:

IN: scratchpad gc [ heaps-benchmark ] time
Running time: 0.172660576 seconds

IN: scratchpad 1,000,000 random-units gc [ heapsort drop ] time
Running time: 1.688299185 seconds

Not a bad improvement!