I/O Reader

• Languages have structure.
• We can make a new language, X, to describe the structure of languages.
• Language X itself has a structure and as a result the structure of language X can be described.
• We made language X to describe the structure of languages.
• Therefore, language X can describe its own structure.

Update:
The code for the GUI and functional parts of the Java code that I used in my MineSweeper implementation can be found in the code/java section of my website.

Recently I have been working on a Java implementation of the popular desktop game MineSweeper for a software engineering class I am currently taking. One of the project requirements is that Java Swing must be used and that NetBeans could not be used. I have now finished the programming side of the assignment and decided that I wanted to talk about a few ways that I made it easier for myself to use some of the components in the Swing Framework.

For those interested, a picture of the game with a bit of the code displayed nearby can be found here.

In this article I will refer to two types of functions. The first type is which are public static methods of a class and the second type is a special Function type. Lack of capitalization will distinguish the former from the latter.

Types

The following types are, for the most part, necessary to understand how any of the bits of code work. Originally, I used the long, descriptive names for each of these types; however, once I started using them so often I decided to follow the lead of the Functional Java library and shorten the names to a single letter. Although convenient, the shortened names have some drawbacks: the programmer needs to know ahead of time what each type represents and needs to be careful when writing generic code.

A final note is that I have likely re-created a few of the existing classes or interfaces in one of Java's standard libraries or in existing third-party libraries (such as Functional Java). In each of the cases, I've added my own touch to each of the classes.

D: Delegate

A delegate is an abstract class that uses a single value of a given type as a means to the end of causing some sort of side-effect. I.e.: a delegate goes and does something with a single input.

Delegates can be chained together in sequence, which I felt was a nice touch; however, in MineSweeper I never ended up using this functionality.

G: Generator

Generators, in the sense that I have built them (not in the sense of continuations) as being the complement of Delegates and not as powerful as a Functions. A generator is a class that does something to the end of producing a single value of some type.

Again, generators in this sense were nice in terms of their symmetry with Delegates; however, they were not used.

F, F2: Function

There are two function types: one that takes a single argument of one type and returns a single value of another and one that takes two arguments and returns a single value. The former is suitable for mapping operations whereas the latter is best for folds.

Functions of one argument support function composition. Functions of two arguments do not support composition; however, either of the two arguments can be curried—the result being a Function of one argument.

P: Predicate

I made predicates in response to a future need that I will have when developing code for this course. Currently, predicates are supported by the filter operation. Predicates come with a set of combinators: and, or, nand, and nor. Predicates can also be negated using the not operation.

Taming Swing

Frames

Making a frame was the first and most obvious challenge I needed to tackle. I'm reaching when I say that frames were a challenge; my application only requires a single frame and I could have easily used the frame code as outlined in the Java Swing documentation.

The challenge was thus one of coding style. I started my application by making a frame and so it set the stage for how I wanted to go about coding the rest of the application.

For the most part, I dislike needlessly assigning values to local variables—especially in Java (as it's type system is verbose). This usually stems from only needing something once. As a result of this somewhat odd dislike of mine, I decided that any of my GUI simplification code must return a value of the component they construct (assuming they construct one) so that they can be assigned to variables when needed. Also, I wanted to be able to pass in delegates that would initialize some of the components. This strategy has the nice property that construction of a particular component is isolated in a single function and that function is responsible for calling the delegate and passing in the constructed instance.

The following is an example of making a frame:

frame("Mine Sweeper", new D<JFrame>() {
    public void call(final JFrame f) {
        // initialize the frame
    }
});

Menus

Menus are one of the more obviously hierarchical elements of a GUI (despite all GUI components being part of an implicit hierarchy). The goal here was to make the code representative of the structure of the menu itself and that was very straightforward. Again, each function has a return value. Also, instead of taking in initialization delegates, the menus take in delegates to deal with their on-click events. The following is an example of the menu I use in MineSweeper.

menu_bar(f,
    menu("File",
        menu("New Game", 
            menu_item("4 x 4 (3 mines)", new D<JMenuItem>() {
                public void call(JMenuItem item) {
                    self.safeCreateMineField(f, 4, 4, 7);
                }
            }),
            menu_item("6 x 4 (7 mines)", new D<JMenuItem>() {
                public void call(JMenuItem item) {
                    self.safeCreateMineField(f, 6, 4, 7);
                }
            }),
            menu_item("8 x 8 (10 mines)", new D<JMenuItem>() {
                public void call(JMenuItem item) {
                    self.safeCreateMineField(f, 8, 8, 10);
                }
            }),
            menu_item("Custom Dimensions", new D<JMenuItem>() {
                public void call(JMenuItem item) {
                    self.createCustomMineField(f);
                }
            }),
            menu_item("Using Current Dimensions", new D<JMenuItem>() {
                public void call(JMenuItem item) {
                    self.recreateMineField(f);
                }
            })
        ),
        menu_item("Quit", new D<JMenuItem>() {
            public void call(JMenuItem item) {
                self.quit_program_delegate.call(f);
            }
        })
    ),
    
    // ...
);

Grids

I wanted the most flexibility in laying out objects in the GUI so I chose to use the GridBagLayout. This is a notoriously annoying layout manager to work with; however, I feel like I came to a decent compromise between brevity in code and understandability.

The first thing to understand is the GridCell. This is actually a tuple (ordered pair) with a Component and a GridBagConstraints instance in it. All of its methods can be chained together (i.e.: each method returns the GridCell instance). The important methods I needed to provide were: pos (position), padding, margin (insets), and anchor (where to align the component within the cell). Another important feature that needed to be covered was the ability to have a cell span many rows or columns.

I approached by the problem of having a cell span rows/columns through the function that creates a GridCell. Using method overloading, I made the order of arguments to the grid_cell function significant. Thus, a 1x1 cell can be constructed by passing in a component to grid_cell(); however, should one want to, one can call grid_cell with as many as three parameters: column span (int), component (Component), row span (int).

Margin, padding, and position are self-explanatory. Margin and padding work in the same way as they do in CSS. Position takes integer x, y coordinates. Anchoring is slightly more interesting. It takes four integers, all either zero or one (this is enforced by taking only their low-order bit). In order, the integers represent north, east, south, west. To centre a component within its cell, one sets all of them to 1. To get something anchored to the north-east, only north and east need be set to one. Finally, something can be anchored to only a specific direction by setting any one of the inputs to one and the others to zero.

The following is a code sample that lays out the form to input custom dimensions for a minesweeper game.

// create the form for inputting the custom mine field 
// dimensions
return grid(

    // number of rows
    grid_cell(label("Number of Rows"))
        .margin(10, 10, 10, 10)
        .anchor(0,1,0,0), // align east

    grid_cell(rows)
        .pos(1, 0),

    // number of columns
    grid_cell(label("Number of Columns"))
        .pos(0, 1)
        .margin(0, 10, 10, 10)
        .anchor(0,1,0,0),

    grid_cell(cols)
        .pos(1, 1)
        .margin(0, 0, 10, 0),

    // number of bombs
    grid_cell(label("Number of Mines"))
        .pos(0, 2)
        .margin(0, 10, 10, 10)
        .anchor(0,1,0,0),

    grid_cell(bombs)
        .pos(1, 2)
        .margin(0, 0, 10, 0),

    // play button, create a game using the dimensions
    grid_cell(button("Play", new D<JButton>() {
        public void call(JButton b) {
            // ...
        }
    }), 3).pos(2, 0).margin(0, 10, 0, 10).anchor(0, 0, 0, 1)
);

The result is a nice form with all of the text field labels right-aligned to their text fields. Each label/text field pair is in a new row. Finally, the play button is in the third column, vertically centered.

The Rest

The rest includes dialogs, buttons, icons, text fields, etc. I don't think it's really worth it to go into each of those as they follow a similar pattern to the above code and it fairly trivial to simplify the Swing API into this coding style for those components.

Final Thoughts

I wouldn't consider any of this to be breaking any ground; I suspect someone who has had to use the Swing framework and has a similar dislike for its API has made similar simplifications.

Another thing to note is that while such a library might very well exist elsewhere on the Internet, I decided it would be prudent to only use my own code for this assignment and in the end I'm fairly happy with the result.

Finally, this assignment was very interesting for me because my entire programming career has focused on web-based technologies and with websites the languages used for logic and that used for GUI are so distinct that it's easy to separate them. I found that I wasn't really following any real architectural style when writing this code as it was more difficult to distinguish what was GUI-specific and what was logic-specific.

I suspect my uncertainty of where to draw the line between logic and GUI code in this case stems from the fact that desktop GUI programming is new to me and that all of the GUI is constructed through code anyway. Regardless, I had a lot of fun writing code to make my life simpler and in the end, using Swing became much more enjoyable than it otherwise looked from the online documentation.

Recently I've been having a lot of fun learning and hacking with Common Lisp. Two of the more interesting (and not particularly elegant) pieces of code I've written include a recursive descent parser interpreter and a recursive descent parser generator. I'm happy with these two programs because both work (although the interpreter might have a few quirks) and because they were simple to make (despite the large amount of code).

Interpreter

The interpreter takes patterns (written in lisp) and at run time goes through the parts of the patterns and generates functions that can parse certain parts of text. Everything is considered a pattern function, be it a string or character or an explicit call to a pattern operator such as OR or FIND-NEXT.

The way the interpreter matches text is fairly simple: each function that is generated takes two parameters: the current list of matches, and the remaining text that hasn't been seen yet. These functions then return three parameters: the updated list of matches, the remaining text that hasn't been seen yet, and whether or not the function succeeded in matching something. The following is a simplified diagram of how the interpreter goes through the a pattern and matches text against the current part of the pattern it is looking at.

As is clear from the image, there can be no back-tracking of any sorts because every matching function gets either the same or a smaller version of the text than the previous one. This fulfills the descent component of the parser: it always goes down by consuming text and cannot go back up. The interpreter is recursive in two ways: the way it interprets the patterns and creates matching functions is recursive and because this is done on-the-fly the pattern matching is inherently recursive because of this. It is also recursive because one can define multiple different pattern functions and call them from within other pattern functions.

Parser Generator

The parser generator works in a similar way but is much less elegant than the interpreter in terms of how it works. At compile time, macros do a depth-first expansion of the pattern operators into blocks of code and end up making a large chunk of code representing a pattern-matching function. Each block of code returns three values: any matches that the block found, whether or not the block matched anything, and whether or not the match consumed any text. It is up to any parent operators to deal with these values, and it's usually the case that the matches bubble up to the top-level of a pattern function and are handled there.

The three values reported by each block are important for several reasons. Pattern operators such as OR can sometimes always return a positive match but not consume any text. Consider this pattern: (maybe "hello"). This is translated into to the OR operator: (or "hello" ""). As can be seen, if the operator fails to match "hello" then it will always succeed at matching "" (an empty string). When used in the REPEAT or FIND-NEXT operators this can be dangerous, so those operators require that the patterns match as well as consume.

At first glance the matched boolean seems redundant given that each block also returns a list of matched values. The matched value is required because of the NO-CAPTURE operator, which allows the pattern to match something but not record the match. This operator is very useful because it's often required that we match some part of a pattern but where that specific part gives us no useful information. For example, when matching XML-like tags, the < and > symbols delimit tags but do not represent useful match information.

Example: Splitting Up an HTML Document

The following pattern functions properly split up some text by HTML tags. Note: the pattern functions do not validate the HTML.

When we apply the above patterns to some HTML (from the older version of this blog) using the parser generator we get the following code and parse tree:

prefix text
<div class="post">
    <a name="comment-{$comment.comment_ID}" id="comment-{$comment.comment_ID}"></a>
    {$comment.content}
    <ul class="categories">
        by 
        <cond:if var="comment.comment_author_url" neq="">

            <a href="{$comment.comment_author_url}" title="{$comment.comment_author}">
                {$comment.comment_author}
            </a>
        <cond:else />
            {$comment.comment_author}
        </cond:if>

        on {$comment.date}
    </ul>
</div>
postfix text

The Code

You can find the code for the parser interpreter and parser generators at the following locations:

• Parser Interpreter
• Parser Generator

One thing to note is that I am new to common lisp and I recognize that some of the code is not exceptionally attractive. If any Common Lisp hackers read this post then please feel free to comment on how I might improve the coding style! A final note is to say that the interpreter is coded in a more functional way whereas the parser generator is much more procedural.

It always sucks to write a "sorry for not posting" blog post and so here is the plan for the next few months. PINQ development is temporarily on hold. It's at a point where I like the ideas in it but where the implementation of the packages system is overly complex. My plans are to take a bunch of stuff out of the database and model/gateway areas and move them permanently into the PQL-specific stuff. This makes a lot of sense, especially since I think it would be worthwhile to make PQL as module-like as possible so that I can release it alone for those interested in it.

On the personal development side of things, I have been buying up a huge number of books which I intend to read over the next few/many months. The books that I have queued up to read align nicely with my long-term goals. I just finished reading The C Programming Language (a.k.a. K&R) and am now getting into ANSI Common Lisp. After ANSI CL I plan on reading through Practical Common Lisp (which if you are a longtime reader then you will know I've previously read parts of this book). My main motivation for getting into Common Lisp is that I want to be able to read The Art of the Metaobject Protocol and know exactly what's going on in it.

That's about all there is on the Lisp side of things. I then get into the more systems programmy things that I'm into: language design, compilers, garbage collection, etc. Not too long ago I started reading the dragon book (Compilers: Principles, Techniques, and Tools) and have paused reading of that. It's a dense book so I want to ease into it a bit more. I intend to do that by first reading Programming Language Pragmatics and Compiler Design in C. After those I think I will be ready to finish off the dragon book. Finally, I'm going to jump into Virtual Machines and Garbage Collection: Algorithms for Automatic Dynamic Memory Management

Throughout all of this, I've got side reading of The Pragmatic Programmer and Beautiful Code to read into.

This is my really long term reading schedule. I can imagine reading these books could take me well over a year-- especially now that my third year of university is about to start. School is an increasingly important part of my life, as is my job as a residence advisor at my school and so all of this together will likely limit my blogging ability. However, expect a few random posts now and then, especially around statutory holidays.

Finally, if anyone is ever looking for PHP help, I'm a regular on the SitePoint forums so either create a thread or send me a private message. My username is: Peter Goodman.

See you all on the other side!

I was a bit bored so I whipped up this little diagram in OmniGraffle of the control flow within the PINQ framework and an application. Most things will seem familiar to programmers who regularly use MVC frameworks. It's actually slightly more complex than what is going on in there; however, I was limited to using 20 object with the demo version of OmniGraffle and so I was rather limited on what I could show.

The one interesting bit in here is the yield resource exception. As I've written in previous posts, it changes control from one controller to another.