Archive for August, 2011

Articles

API discovery with Scheme

In APIhackday,Scheme,Web development on August 2, 2011 by gcbenison

By now JSON is a widely-accepted standard, well-supported in the most common web development languages. But the whole point of an open standard is that one ought to be able work with it in any language and on any platform. Attempting to work with a standard on an unusual platform is a good way to test how “open” it really is, and standards have good reason to pay attention to the results: not only do fringe players sometimes become more important (see, e.g. Linux kernel), they also help keep standards honest by preventing language-dependent or platform-dependent “conveniences” from sneaking in.

So when my 13-year-old brother-in-law Lucien and I arrived at APIhackday, we decided to work with web API’s in two of our favorite languages – lua and Scheme – even though these are not often thought of as web programming languages. We chose to work with PDXCouncilConnect, which provides access to civic records of the City of Portland through a web API. A typical JSON result stream looks like this:

{
    "sessions": [
        {
            "header": "", 
            "id": 304, 
            "location": "City Hall - 1221 SW Fourth Avenue", 
            "message": "Due to lack of an agenda there will be no meeting.", 
            "start_date": "2011-06-01 14:00:00.0", 
            "title": ""
        }, 
        {
            "header": "THOSE PRESENT WERE:  Commissioner Saltzman, Presiding; Commissioners Fish \nand Fritz, 3. ", 
            "id": 302, 
            "items": [
                {
                    "bureaus": "", 
                    "disposition": "", 
                    "disposition_url": "", 
                    "emergency": 0, 
                    "files": "", 
                    "heading": "Times Certain", 
                    "id": 921, 
                    "item_number": "", 
                    "item_number_string": "", 
                    "motions": [
                        {
                            "status": "passed", 
                            "title": "Accepted", 
                            "type": "motion", 
                            "votes": [
                                {
                                    "owner": "City Auditor LaVonne Griffin-Valade", 
                                    "vote": "-"
                                }, 
etc...

A simple JSON parser can be written quickly, but it is also possible to find at least a rudimentary one in almost any language. Lucien found a lua JSON parser, and using the CouncilConnect stream, actually found a bug, wrote a workaround, and by the end of the session was parsing the JSON stream. Though there seems to be no dominant JSON parser for Scheme, I quickly found a simple one. Now that I had the JSON stream as a Scheme object, what to do with it? My first idea was to pull in the guile-gnome library and use it to build a graphical desktop app (using GTK+ widgets) that draws its data from the web stream. By the end of the one-day hackathon it was working, demonstrating the utility of Scheme in pulling together disparate libraries quickly. Though interesting, this result didn't seem to harness the unique advantages of the Scheme language. After all, JSON comprises nested lists of values, and manipulating lists is what Scheme is for. Couldn't we use Scheme to transform the data in some useful way? Here is the CouncilConnect stream, represented as a tree:

Tree representation of JSON input

JSON input, represented as a tree

As I watched people around the room working with this API for the first time, I noticed that I and others were spending much of our time studying the JSON stream to understand this underlying tree structure. Though we often knew immediately which element we were interested in (for example, the "votes" node, highlighted), we first had to learn how to navigate the tree in order to get to it. What if there was a way to bring this part of the API, buried deep in the tree, to the forefront without having to understand the whole API? We can re-root a tree at any node by changing the direction of some of the links (visually, grab the new root and hold it up; let the rest of the tree dangle down):

.Re-rooted JSON tree

JSON tree, re-rooted at "votes" element. Edges that have been flipped are highlighted

Now, the most interesting piece of information is easily accessible, right at the top of the tree. It is generally easier - both conceptually and in code - to navigate down a tree than it is to backtrack up it: in the rotated tree, I can still see that the "votes" object is part of a "motions" object which is part of an "items" object which is part of a "session", and I can still navigate those relationships, but I don't need to understand them just to get at the "votes" data.

It is possible to write a completely generic Scheme function that takes as arguments any JSON tree and any node-matching predicate, and returns a tree re-rooted at the node matching the predicate (or a list of such trees where more than one node matches). This is the sort of thing Scheme excels at; the heart of the code looks like this:

;; Return an array node,
;; whose members are trees T' which are T re-rooted
;; at nodes N matching (pred N)
(define (reroot T pred)
  (node 'array
	#f
	#f
	(let loop ((T T)
		   (path '()))
	  (if (pred T)
	      (list (rebuild T path 1))
	      (apply append
		     (map-partitions
		      (lambda (child other-children)
			(loop child
			      (cons
			       (node:replace-children T other-children)
			       path)))
		      (node:children T)))))))

;; Rebuild tree rooted at T, but appending links following 'path'
(define (rebuild T path level)
  (if (null? path)
      T
      (node 'object
	    (node:key T)
	    #f
	    (list
	     (node:replace-missing-key T "new_root")
	     (rebuild (node:replace-key
		       (car path)
		       (format #f "xpath-~a-~a"
			       level
			       (or (node:key (car path)) "NA")))
		      (cdr path)
		      (+ level 1))))))

Now, having the re-rooted tree, what should we do with it? How about de-parsing it straight back into JSON? The Scheme program is now acting as a sort of middleware or API virtualization layer - the re-factored JSON stream can be fed to any other JSON-capable tool (in any language). Here is an excerpt of the CouncilConnect JSON stream with "votes" rotated to the top:

[ { "votes": [
            { "owner": "City Auditor LaVonne Griffin-Valade", 
              "vote": "-"  }, 
            {   "owner": "Commissioner Amanda Fritz", 
                "vote": "Yea" }, 
            {   "owner": "Commissioner Nick Fish", 
                "vote": "Yea" }, 
            { "owner": "Mayor Sam Adams", 
                "vote": "-" }
        ], 
        "xpath-1-NA": {
            "xpath-1-NA": {
                "status": "passed", 
                "title": "Accepted", 
                "type": "motion"
            }, 
            "xpath-2-motions": {
                "xpath-2-motions": [], 
                "xpath-3-NA": {
                    "xpath-3-NA": {
                        "bureaus": "", 
                        "emergency": 0, 
                        "heading": "Times Certain", 
                        "id": 921, 
                        "owners": "", 
                        "title": "Portland City Council Agenda", 
                        "topic": "TIME CERTAIN: 9:30 AM - Combined Sewer Overflow Program  (Report introduced by Commissioner Saltzman)  30 minutes requested"
                    }, 

Now, I can easily access the contents of the "vote" object at the head of the stream, and if I care to, I can drill down further to see that the vote was passed and that it was related to a Sewer program.

For another example, let's hoist the node called "bureaus" to the top and see what happens. In the result below, we find at the head of the JSON stream a piece of business related to the transportation bureau; navigating down a level, we see the result of a vote; down one more level, and we see that this was about disabled parking permits.

[
    { "bureaus": [  "Portland Bureau of Transportation" ], 
        "xpath-1-NA": {
            "xpath-1-NA": {
                "emergency": 0, 
                "files": "", 
                "heading": "Regular Agenda", 
                "id": 922, 
                "item_number": "", 
                "item_number_string": "", 
                "motions": [
                    {
                        "status": "", 
                        "title": "", 
                        "type": "item", 
                        "votes": [
                            {   "owner": "Commissioner Nick Fish", 
                                "vote": "Yea"
                            }, 
                            ...
                        ]
                    }
                ], 
                "owners": [ "Mayor Sam Adams" ], 
                "title": "Portland City Council Agenda", 
                "topic": "Extend the date of the privileges for regular disabled person parking permits (Second Reading Agenda 520; amend Code Section 16.20.640)"
...

So, there it is: an application of Scheme code to web API programming, which leverages the strengths of the language, and which might even be useful. Here is the full code for the JSON-refactoring program:

(Updated 8/7/2011: this code is now also available on github)

;; Greg Benison, 1 August 2011
;; transform JSON input stream (stdin) into a tree;
;; re-root the tree and re-output as JSON (stdout).

(use-modules (json reader)
	     (json writer)
	     (srfi srfi-1)
	     (ice-9 pretty-print))

;; Change this as desired...
(define node-of-interest "votes")

; ---------------- utility functions -----------

(define (->string x)(format #f "~a" x))

(define (compose . ops)
  (if (null? ops)
      (lambda (x) x)
      (lambda (x)
	((car ops)
	 ((apply compose (cdr ops)) x)))))

;; like 'map', but supplies a second
;; argument to 'op' consisting of
;; "the other elements of set" in their
;; original order.
(define (map-partitions op set)
  (let loop ((first-part '())
	     (result '())
	     (rest set))
    (if (null? rest)
	(reverse result)
	(let ((this-element   (car rest))
	      (other-elements (append (reverse first-part)(cdr rest))))
	  (loop (cons this-element first-part)
		(cons (op this-element other-elements) result)
		(cdr rest))))))

(define (json:dump-to-file json fname)
  (let ((outfile (open-output-file fname)))
    (display (json:dump json) outfile)
    (close outfile)))

(define (hash-keys ht)(hash-fold (lambda (k v p)(cons k p)) '() ht))

; ---------------- JSON as tree ----------
(define (node type key value children)
  (cons (cons type key)
	(cons value children)))

(define node:type     caar)
(define node:key      cdar)
(define node:value    cadr)
(define node:children cddr)

(define (node:replace-children N new-children)
  (node (node:type  N)
	(node:key   N)
	(node:value N)
	new-children))

(define (node:replace-key N new-key)
  (node (node:type N)
	new-key
	(node:value N)
	(node:children N)))

(define (node:replace-missing-key N new-key)
  (if (node:key N) N (node:replace-key N new-key)))

(define (node:key? key)
  (lambda (N)(equal? key (node:key N))))

(define (node:take N limit)
  (node:replace-children N (take (node:children N) limit)))

(define (json->tree json key)
  (cond ((hash-table? json)
	 (node 'object
	       key
	       #f
	       (hash-fold
		(lambda (k v p)
		  (cons (json->tree v k) p))
		'()
		json)))
	((list? json)
	 (node 'array
	       key
	       #f
	       (map (lambda (v)(json->tree v #f)) json)))
	(else (node 'scalar key json '()))))

(define (tree->json tree)
  (case (node:type tree)
    ((scalar)(node:value tree))
    ((array)(map tree->json (node:children tree)))
    ((object)
     (let ((table (make-hash-table)))
       (for-each
	(lambda (node)
	  (hash-set! table (node:key node) (tree->json node)))
	(node:children tree))
       table))))

;; Rebuild tree rooted at T, but appending links following 'path'
(define (rebuild T path level)
  (if (null? path)
      T
      (node 'object
	    (node:key T)
	    #f
	    (list
	     (node:replace-missing-key T "new_root")
	     (rebuild (node:replace-key
		       (car path)
		       (format #f "xpath-~a-~a"
			       level
			       (or (node:key (car path)) "NA")))
		      (cdr path)
		      (+ level 1))))))


;; Return an array node,
;; whose members are trees T' which are T re-rooted
;; at nodes N matching (pred N)
(define (reroot T pred)
  (node 'array
	#f
	#f
	(let loop ((T T)
		   (path '()))
	  (if (pred T)
	      (list (rebuild T path 1))
	      (apply append
		     (map-partitions
		      (lambda (child other-children)
			(loop child
			      (cons
			       (node:replace-children T other-children)
			       path)))
		      (node:children T)))))))

; ---------------- input parsing ---------------

(define infile
  (cond ((null? (cdr (command-line)))       (current-input-port))
	((equal? "-" (cadr (command-line))) (current-input-port))
	(else (open-input-file (cadr (command-line))))))

(define input (json:read-value infile))
(define input-as-tree (json->tree input #f))

; ---------------- transform & output ----------

(display
 (json:dump
  (tree->json
   (reroot input-as-tree (node:key? node-of-interest)))))
Follow

Get every new post delivered to your Inbox.