Re: Factor

Monday, March 8, 2010

Working with CGI: Part 4

In parts 1, 2, and 3, we learned about parsing CGI requests using Factor.

I wanted to take a moment and talk about using templates to develop web sites. Many web developers will suggest that using templates is a good way to separate presentation and content, making it easier for teams to work together to build a website, as well as other benefits.

There is no magic to most template systems. Fundamentally, these systems take some text (usually in a hybrid "template language"), compile it into code, using the compiled template to output a dynamic page.

In Factor, the html.templates vocabulary allows access to several HTML template implementations including Chloe and FHTML. Some differences between the two include:

requiring XML (Chloe) or HTML (FHTML)
embedding data (Chloe) or Factor code (FHTML)

Depending on your use-case, you might have a preference for one versus the other. If neither suite your purpose, you could even implement your own with a modest amount of work.

Embedding a template into a Factor CGI script is pretty easy. Here is an example of using the FHTML vocabulary to parse a template and then call it to render a page.

#! /path/to/factor

USE: io

"Content-type: text/html\n\n" print

USE: html.templates.fhtml

"""
<% USING: calendar formatting math math.parser io ; %>

<html>
    <head><title>Simple Embedded Factor Example</title></head>
    <body>
        The time is <% now "%c" strftime write %>
        <br>
        <% 5 [ %><p>I like repetition</p><% ] times %>
    </body>
</html>

""" parse-template call( -- )

When run from Factor, or accessed as a CGI script, this will print a page something like the following:

The time is Mon Mar 08 23:12:47 2010.

I like repetition

I like repetition

I like repetition

I like repetition

I like repetition

Many large web applications are built with some kind of template engine, frequently using smart caching of compiled templates for performance, and usually storing the template files separately from the CGI script that loads and calls them.

But, it all basically starts with this.

Wednesday, February 3, 2010

Working with CGI: Part 3

In Part 2, we implemented simple parsing of QUERY_STRING and handling of the GET request method.

In getting to the conclusion, I skipped describing an important convention of HTTP application development. Specifically, that GET requests should be idempotent. Because of this, as well as privacy concerns, it is frequently common practice to submit HTML forms with a POST request.

According to the POST convention, the request data is placed in the message body and usually "URL-encoded" (as described in RFC 2396). This is similar to how certain characters are "escaped" when included in a URL (for example, spaces are represented by %20).

To properly parse these types of POST requests, we will need to parse a few other environment variables that are provided to the CGI script. First, we need a way to parse "content types". As described in RFC 2616 (the specification for HTTP/1.1), this represents a mime-type and optional parameters.

For example, a server can specify that the response type will be HTML inside of a UTF-8 character encoding by including the following in the HTTP response headers:

Content-Type: text/html; charset=utf-8

To parse this, we can simple separate the mime-type and parse the parameters:

: (content-type) ( string -- params media/type )
    ";" split unclip [
        [ H{ } clone ] [ first (query-string) ] if-empty
    ] dip ;

When we submit a form, the values are included in the body and provided to the CGI script using a mime-type of "application/x-www-form-urlencoded". The contents are provided by parameters encoded in the message body. (Technically, some of the parameters could also be specified in the URL).

We can define a function that will parse the CONTENT_LENGTH, read the specified number of bytes from the stream, and then assemble and parse the URL-encoded query string:

: (urlencoded) ( -- assoc )
    "CONTENT_LENGTH" os-env "0" or string>number
    read [ "" ] [ "&" append ] if-empty
    "QUERY_STRING" os-env [ append ] when* (query-string) ;

These two words are sufficient to parse POST requests. However, it's worth noting that some forms can be submitted with a mime-type of "multipart/form-data", which is used for uploading files to servers. We will put a placeholder word that can remind us to come back to this:

: (multipart) ( -- assoc )
    "multipart unsupported" throw ;

Now that we have that, we can write the implement the parsing routine:

: parse-post ( -- assoc )
    "CONTENT_TYPE" os-env "" or (content-type) {
       { "multipart/form-data"               [ (multipart) ] }
       { "application/x-www-form-urlencoded" [ (urlencoded) ] }
       [ drop parse-get ]
   } case nip ;

And then extend our <cgi-form> word to handle POST requests:

: <cgi-form> ( -- assoc )
    "REQUEST_METHOD" os-env "GET" or >upper {
        { "GET"  [ parse-get ] }
        { "POST" [ parse-post ] }
        [ "Unknown request method" throw ]
    } case ;

And simple as that, we can now change our form method from "get" to "post", and our CGI scripts will continue to work.

Tuesday, February 2, 2010

Working with CGI: Part 2

In Part 1, we created a simple debugging script to print out the environment the CGI script is being executed within.

Many CGI scripts are simple "form handlers". These scripts take input via an HTML form and generate a dynamic response. We are going to write a CGI script that will be able to parse input from an HTML form submission.

The most common type of HTTP request is the GET method. The web browser sends a URL to the server and requests the server "get" the contents of the URL and send it back. When HTML forms are submitted using the GET method, the form elements are "URL encoded" and passed to the server as the "query string" part of the URL.

For example, if I had a "calculator" application to add two numbers (e.g., "x+y"), you could imagine getting the result of 2+3 by calling:

http://server/add?x=2&y=3

We need a word that will parse the QUERY_STRING and return a map of submitted parameters. Luckily, Factor has such a word in the urls.encoding vocabulary:

( scratchpad ) "x=2&y=3" query>assoc .
H{ { "x" "2" } { "y" "3" } }

For our use case, the query>assoc word isn't quite what we need. For one thing, it handles empty strings in an odd way:

( scratchpad ) "" query>assoc .
H{ { "" f } }

Also, it doesn't handle multiple inputs with the same name consistently with single inputs. If a parameter is represented in the query string multiple times, it will appear in the result as a list of values.

( scratchpad ) "a=2&a=3" query>assoc .
H{ { "a" { "2" "3" } } }

So to "fix" this, we will develop a word that filters out f values, and returns both single and multiple parameters as sequences.

: (query-string) ( string -- assoc )
    query>assoc [ nip ] assoc-filter
    [ dup string? [ 1array ] when ] assoc-map ;

Now that we have our building blocks, we can begin supporting the GET request. Let's start by designing the API. We want to parse the request method, handle the GET method, and return the parameters submitted. The REQUEST_METHOD and QUERY_STRING are available as environment variables:

: parse-get ( -- assoc )
    "QUERY_STRING" os-env "" or (query-string) ;

: <cgi-form> ( -- assoc )
    "REQUEST_METHOD" os-env "GET" or >upper {
        { "GET"  [ parse-get ] }
        [ "Unknown request method" throw ]
    } case ;

Since frequently we will only need to worry about the first parameter value (ignoring subsequent values if present), we can make a simple version that can be optionally used:

: <cgi-simple-form> ( -- assoc )
    <cgi-form> [ first ] assoc-map ;

Putting all of this together, we can build something useful: a Brainfuck interpreter accessible from a web page!

USING: assocs brainfuck cgi formatting io kernel ;

"Content-type: text/html\n\n" write

"code" <cgi-simple-form> at
"""
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
------.--------.>+.>.
""" or dup get-brainfuck

"""
<html>
<head><title>Brainfuck</title></head>
<body>
<form method='get'>
<textarea id="text" name="code" cols="80" rows="15">
%s
</textarea><br>
<input type="submit" value="Submit"> 
<input type="reset" value="Reset">
</form>
<pre>%s</pre>
</body>
</html>
""" printf

If nothing is specified, this will happily calculate and then print "Hello World!", otherwise it will compute the result of the code provided.

Wednesday, January 20, 2010

Working with CGI: Part 1

While Factor can be used to develop many different kinds of programs, some uses just aren't as common as others, for many reasons.

One such case is its use to develop CGI scripts. The "Common Gateway Interface" (sometimes called "CGI/1.1") is the documented version of conventions developed for web programming in the late 1990's. If you are curious, you can read RFC 3875 for more details.

The way it works is simple. The web server:

receives an HTTP request
parses the request headers and payload, and then
calls an application with the request details, which then
renders a response that is then sent back to the client

When developing and testing CGI scripts, it is useful to understand the environment that your program will be running within. For this, we can build a simple Factor program that prints the environment variables it is called with to HTML that can be rendered in a web browser.

Our CGI script should be executable, and on a UNIX system (like Mac OS X or Linux) should contain a shebang which indicates what program should process the files contents. This is used to call the Factor interpreter with our CGI script. Note that the shebang has a space after it, which is not required by most interpreters, but is by Factor:

#! /path/to/factor

The vocabularies that we will be using:

USING: assocs environment kernel io namespaces sequences
sorting ;

The first response from a CGI script is typically the HTTP headers, including the type of content that is being returned. Your script could return any content, including images, audio, or video. But in this case, we will just return plain HTML:

"Content-type: text/html\n\n" print

We can then print the HTML header and begin the body:

"""
<html>
<head>
<title>Debug</title>
</head>
<body>
<pre>
""" print

Next, we will get all the environment variables available to our process and print them, sorted alphabetically:

os-envs >alist sort-keys [
    [ "<b>" write first write "</b>" write ]
    [ " = " write second write nl ] bi
] each

And then finish the HTML document with closing tags:

"""
</pre>
</body>
</html>
""" print

If you run this program from the shell, it will print your local user environment. But, when run from a web server, it prints the CGI script's environment. According to the CGI specification, certain environment variables are used to pass the HTTP request details to the CGI program. Some of the commonly used ones include:

`DOCUMENT_ROOT`	The root directory of your server
`HTTP_COOKIE`	The visitor's cookie, if one is set
`HTTP_HOST`	The hostname of the page being attempted
`HTTP_REFERER`	The URL of the page that called your program
`HTTP_USER_AGENT`	The browser type of the visitor
`HTTPS`	"on" if the program is being called through a secure server
`PATH`	The system path your server is running under
`QUERY_STRING`	The query string (see GET, below)
`REMOTE_ADDR`	The IP address of the visitor
`REMOTE_HOST`	The hostname of the visitor (if your server has reverse-name-lookups on; otherwise this is the IP address again)
`REMOTE_PORT`	The port the visitor is connected to on the web server
`REMOTE_USER`	The visitor's username (for .htaccess-protected pages)
`REQUEST_METHOD`	GET or POST
`REQUEST_URI`	The interpreted pathname of the requested document or CGI (relative to the document root)
`SCRIPT_FILENAME`	The full pathname of the current CGI
`SCRIPT_NAME`	The interpreted pathname of the current CGI (relative to the document root)
`SERVER_ADMIN`	The email address for your server's webmaster
`SERVER_NAME`	Your server's fully qualified domain name
`SERVER_PORT`	The port number your server is listening on
`SERVER_SOFTWARE`	The server software you're using (e.g. Apache)

This is a useful fact for testing, since you can easily simulate the request that the web server will be sending to your CGI script by configuring the environment in the appropriate way. More to come on that later...

Wednesday, December 30, 2009

Counting Word Frequencies

One of my favorite memes right now is for people to write small programs in various languages to compare and contrast and learn from one another.

Recently, someone blogged an example of counting word frequencies in a collection of newsgroup articles. The initial implementation was written in Ruby and Scala, with someone else implementing a Clojure solution. These solutions are compared for lines of code as well as time to run.

The basic idea is to iterate over a bunch of files, where each represents a newsgroup posting and is organized by newsgroup into directories. Split each file into words, and then increment a count per word found (comparing case-insensitively).

First, we need a test that is equivalent to the "\w" regular expression. In ASCII, this is essentially a-zA-Z0-9_. We use a short-circuit combinator to break early if one of the tests succeeds.

: \w? ( ch -- ? )
    { [ Letter? ] [ digit? ] [ CHAR: _ = ] } 1|| ; inline

We can then build a word to split a sequence of characters.

: split-words ( seq -- seq' )
    [ \w? not ] split-when harvest ;

This now leaves the main task of counting and aggregating the word counts. The Ruby and Scala examples do this sequentially, but the Clojure example tries to do things in parallel. We are going to keep it simple, and do things sequentially.

: count-words ( path -- assoc )
    f recursive-directory-files H{ } clone [
        '[
            ascii file-contents >lower 
            split-words [ _ inc-at ] each
        ] each
    ] keep ;

We need a word to generate the desired output (tab-delimited words and counts).

: print-words ( seq -- )
    [ first2 "%s\t%d\n" printf ] each ;

And another word to do the actual writing of output to files.

: write-count ( assoc -- )
    >alist [
        [ "/tmp/counts-decreasing-factor" ascii ] dip
        '[ _ sort-values reverse print-words ] with-file-writer
    ] [
        [ "/tmp/counts-alphabetical-factor" ascii ] dip
        '[ _ sort-keys print-words ] with-file-writer
    ] bi ;

Unfortunately, performance isn't quite what I was hoping. I tested this on a 2.8 GHz MacBook Pro. Ruby (using 1.8.7) runs in roughly 41 seconds, Factor runs in 20 seconds, and Python (using 2.6.1) runs in 13 seconds.

I was sort of hoping Factor would come in under the typical scripting languages, and I'd love to get feedback on how to improve it.

For reference, the Python version that I wrote is:

import os
import re
import time
from collections import defaultdict
from operator import itemgetter

root = '/tmp/20_newsgroups'
#root = '/tmp/mini_newsgroups'

t0 = time.time()

counts = defaultdict(int)

for dirpath, dirname, filenames in os.walk(root):
    for filename in filenames:
        f = open(os.path.join(dirpath, filename))
        for word in re.findall('\w+', f.read()):
            counts[word.lower()] += 1
        f.close()

print "Writing counts in decreasing order"
f = open('counts-decreasing-python', 'w')
for k, v in sorted(counts.items(), key=itemgetter(1), reverse=True):
    print >> f, '%s\t%d' % (k, v)
f.close()

print "Writing counts in decreasing order"
f = open('counts-alphabetical-python', 'w')
for k, v in sorted(counts.items(), key=itemgetter(0)):
    print >> f, '%s\t%d' % (k, v)
f.close()

print 'Finished in %s seconds' % (time.time() - t0)

Tuesday, December 29, 2009

Recursively Listing Files

Update: It was pointed out to me that the recursive-directory-files word in io.directories.search solves this problem. Good to know, and the below article can be thought of as a learning exercise! :)

Factor has several vocabularies for interacting with the filesystem, and quite a lot of work has been done on making these useful. Some interesting blog posts from early 2009 include:

One feature that I haven't found yet, is a word to simply (and recursively) list files within a directory. This is often useful with the intent of processing some (or all) of the files in some way.

This feature exists in other language standard libraries with different names. In Python, this is called os.walk(). In Perl, this is called File::Find. Usually, even if it doesn't exist, it can be built relatively easily.

I'm going to show you how to create a word to do that with Factor.

Many words within the standard library are implemented by a public word that defers to a private word for part of the functionality. In this case, I want to separate the "setup" functionality of the word, from the "work" functionality.

Let's define a word list-files that will recursively list all the files within a directory. First, we need to create a growable sequence (in this case a vector) to hold the result, and then we want to call a word that will be used to do the actual work.

: list-files ( path -- seq )
    [ V{ } clone ] dip (list-files) ;

For each path that we process, we will want to handle differently depending on what type of file the path points to:

If a symbolic link, we want to read the link and recurse into it.
If a directory, we want to recurse into each of the files within it.
If a regular file, we want to add it to the list of files.

Using some of the words in io.directories, io.files, io.files.info, io.files.links, and io.files.types, we can build such a function:

: (list-files) ( seq path -- seq )
    normalize-path dup link-info type>> {
        { +symbolic-link+ [ read-link (list-files) ] }
        { +directory+ [
            [ directory-files ] keep
            '[ normalize-path _ prepend (list-files) ] each ] }
        { +regular-file+ [ over push ] }
        [ "unsupported" throw ]
    } case ;

We can setup a directory structure like so:

$ tree -f /tmp/foo
/tmp/foo
|-- /tmp/foo/bar
`-- /tmp/foo/baz
    `-- /tmp/foo/baz/foo

1 directory, 2 files

And then use our new function from Factor:

( scratchpad ) "/tmp/foo" list-files .
V{ "/tmp/foo/bar" "/tmp/foo/baz/foo" }

This could be improved further by handling file permissions issues, infinite recursion, and lazily generating the list of files (for better performance with large directory trees).

Sunday, December 27, 2009

Generating Text in Factor

Some months back, I came across a few blog posts about generating text using algorithms. A simple algorithm was implemented in Clojure and Haskell.

Basically, the idea is to:

Read in a text document.
Count the frequency of word pairs in the document.
Pick a starting word.
Generate random text, using the word pair probabilities.

I wanted to see what a simple Factor implementation would look like, and thought I would share one below.

First, create a list of words from some lines of text. In Factor, it is easy to write a processing word that can then be used from standard input, files, or other input streams.

: split-words ( -- sequence )
    V{ } clone [
        "\r\n\t.,\" " split [ over push ] each
    ] each-line harvest ;

Next, create a sequence of all word pairs (including the pair linking the tail to the head of the list) from the input sequence.

: word-pairs ( sequence -- sequence' )
    dup 1 head-slice append
    dup 1 tail-slice zip ;

Next, we need a map of word pairs, for random sampling by frequency of occurrence. I have chosen to use words in the text as keys, and have the values be a sequence of all words that ever followed it in the text.

: word-map ( sequence -- assoc )
    [ H{ } clone ] dip word-pairs [
        [ second ] [ first ] bi pick push-at
    ] each ;

This makes sampling words with the proper probability quite simple:

: next-word ( word assoc -- word' )
    at random ;

We can now generate paragraphs of random text with the "feel" of the original document.

: wordgen-from ( start n -- string )
    [ [ 1vector ] keep split-words word-map ] dip
    [ [ next-word dup pick push ] keep ] times
    2drop " " join ;

And for convenience, as in the original blog posts, we can start generating from a common English word.

: wordgen ( n -- string )
    "the" swap wordgen-from ;

Putting all of this together, we can make 250 words from Dracula:

( scratchpad ) "/tmp/345.txt" ascii [ 250 wordgen ] with-file-reader .

"the bank notes of electronic works based on the same time to you are fading and it came I too much Without taking a quick he had struck by our eyes and she was not asleep twice when she sank down again There were striving to think yet when the Huns This to get to her all at her on it really Lucy's father Goodbye my own time when she look at the facts before them away and his diary which is out Look! Look! Look! The bright as ever since then we had said Dr Van Helsing will be a chair with you said Yes! And it was a pistol shot up to write for a woman can love and added Friend John and pain nor a long enough You were so seeing it high tide altogether I awoke She is confined within a room lit by the old sweet that the temptation of lion-like disdain His cries are great love must go there would tear my eyes the colour of him and quiet; but still Renfield sitting on one ready Madam Mina Harker had retired early Lucy and there ran downstairs then we get out his fair accuracy when I found that my dear do our visit to oppose him can look had a measure of the other since I secured and seemed to tell upon your all our furs and the face I put in his eyes never be This afternoon she was that such horrors when the"

Not quite Bram Stoker, but just enough to taste the flavor. More complex algorithms exist and can be used for fun and profit. Similar ideas can even be applied to other areas, such as music.