Colin Drake

You Could Have Invented Objects

2016-03-21T00:00:00-04:00

I’ve always been interested in programming languages and paradigms.

Usually, this manifests itself in reading about functional programming, the Lisp family of languages, compilers, and lately, protocol-oriented programming with Swift and Clojure.

However, I recently found myself circling back to a paradigm that most of us take for granted: object-oriented programming. After reading many articles on the c2.com wiki, I ended up playing around with a Pharo Smalltalk installation on my Mac. While I can’t say that I plan on using Smalltalk for my next project, my curiosity was piqued.

The sheer level of interaction and introspection supported by the Pharo object system/environment was amazing. So naturally, I wondered if I could build a small home-grown object system myself… The following is a short exploration in creating a (primitive) object system in Swift.

Overview

Let’s take a step back to CS 101: what are some of the basic, core facets of object oriented programming? Wikipedia lists a few:

Message Passing
Encapsulation
Composition/Inheritance/Delegation
Open Recusion

Now, pretend for a while that class, struct, enum, and friends don’t exist in Swift. What type of (more fundamental) structure is capable of expressing the above features? How about functions, or closures?

Message Passing: perform “procedures” dispatching based off of a passed-in message name parameter
Encapsulation: closures already capture lexical scope
Composition: isn’t this what the functional paradigm is about? 😃
Inheritance/Delegation: simply call another closure!
Open Recusion: well… we’ll get there…

With the above in mind, let’s jump in.

Message Passing

For our purposes, we’ll define a Message as a String and an object as some type that interprets a Message to (possibly) return some value.

typealias Message = String
typealias Object = (Message) -> Any?

Unfortunately, as you can see, we’ll be… sidestepping the type system for this hacky experiment 😉

Let’s start by defining our first “object” that can respond to messages. Our convention will be as such: messages that are not known by the objects will return nil, and all others will return some value.

let obj1: Object = { (msg: Message) in
    switch msg {
    case "do-something": return "sure!"
    default: return nil
    }
}

Great! Now we have an arbitrary object that can dispatch to code based off of messages.

obj1("do-something")   // => "sure!"
obj1("do-other-thing") // => nil

This buys us the simplest benefit of OOP: the ability to abstract out procedures packaged with data based off of some known interface.

Encapsulation

The above code snippets are fine and dandy, but we don’t really want to be defining our own objects ad-hoc all the time: we all know the benefits of using classes as reusable blueprints for creating objects. Luckily for us, this can be represented as… you guess it – another closure!

For us, a “class” is really just comprised of a constructor function that returns a new object/instance (another closure, as demonstrated above).

Additionally, closures can capture the lexical environment, so any parameters passed into our constructor function can act as a sort of read-only instance variable for our internal object. In a nutshell, we get encapsulation for free.

// Constructors are uppercase by convention...
let Person = { (firstName fn: String, lastName ln: String) -> Object in
    return { (msg: Message) -> Any? in
        switch msg {
        case "full-name": return "\(fn) \(ln)"
        case "description": return "<Person>"
        default: return nil
        }
    }
}

…and to use it…

// Define a person and test out methods...
let p = Person(firstName: "Colin", lastName: "Drake")

p("full-name")   // => "Colin Drake"
p("description") // => "<Person>"
p("address")     // => nil

Immutability is nice, but we can also package up mutable state pretty easily. All it really takes is copying the constructor parameters to a mutable local variable. Take, for instance, this Counter example:

let Counter = { (initial: Int) -> Object in
    var counter = initial
    return { (msg: Message) in
        switch msg {
        case "count": return counter
        case "increment":
            counter += 1
            return counter
        case "decrement":
            counter -= 1
            return counter
        default: return nil
        }
    }
}

Composition, Inheritance, and Delegation

One of the biggest attractions to OOP is the ability for code reuse. Both object composition and inheritance allow for this, but in two different ways. Composition allows us to delegate messages out to another object, and inheritance allows us to do the same, but specifically to some object we deem a “parent” to the current one.

We’ll implement inheritance as a simple delegated call to our known parent, if the object itself doesn’t know how to interpret the message. Most languages and object systems have this as a built-in to the syntax/model, but we’ll keep things simple and explicit.

/// Represents possible speeds at which atheletes can run.
enum RunSpeed: String {
    case Slow
    case Fast
}

/// Represents an Athelete, a subclass of Person.
let Athelete = { (firstName fn: String,
                  lastName ln: String,
                  runningSpeed rs: RunSpeed) -> Object in
    // Create a person "super" object to delegate to.
    let superInstance = Person(firstName: fn, lastName: ln)

    return { (msg: Message) -> Any? in
        switch msg {
        // Simple instance method.
        case "how-fast?": return rs
        // Override behavior of a Person.
        case "description": return "<A \(rs.rawValue)-Moving Athelete>"
        // Delegate unknown messages to superclass.
        default: return superInstance(msg)
        }
    }
}

And example usage:

let a = Athelete(firstName: "Colin",
                 lastName: "Drake",
                 runningSpeed: .Slow)

a("how-fast?")   // => RunSpeed.Slow
a("description") // => "<A Slow-Moving Athelete>"
a("full-name")   // => "Colin Drake" (a Person method)

Open Recursion

Within the context of OOP, open recursions refers to the ability to dispatch methods on yourself. As an object, you want the ability to call one of your own methods, but you don’t want the responsibility of needing to know the whereabouts of the raw implementation yourself.

This self-referential dispatch is pretty trivial (and IMHO more elegant) in a Lisp-like language, but we’re in the Swift world: a closure recursively calling itself will raise a compiler error indicating that a value is attempting to use itself in its own definition.

To get around this, we’ll use the Y-combinator, a function that “enables recursion, when you can’t refer to the function from within itself.” It’s a bit tricky to define, but easy to use.

// h/t: http://bit.ly/1U2N0HP
func Y<T, R>( f: (T -> R) -> (T -> R) ) -> (T -> R) {
    return { t in f(Y(f))(t) }
}

With that mess out of the way, let’s try to use it in the OOP context to recursively call our dispatch function:

let Cat = { (name n: String, age a: Int) -> Object in
    return Y {
        dispatch in { (msg: Message) -> Any? in
            switch msg {
            case "name": return "\(n) the Cat"
            case "description":
                // Dispatch on ourself.
                let me = dispatch("name")!
                return "<A Feline named \(me)>"
            default: return nil
            }
        }
    }
}

let leo = Cat(name: "Leo", age: 2)

leo("name") // => "Leo the Cat"
leo("description") // => "<A Feline named Leo the Cat>"

The value of this is that we don’t care if we implemented the method we’re calling, or if it is delegated to a super instance. All of that is abstracted from us via the call to dispatch.

And with that, our simple homegrown object system is complete! However, I’ve got one more trick up my sleeve…

Goodies

Using metaprogramming to aid in code readability is one of my favorite features of Ruby. An expressive, powerful example of this is the ability to call a find_by_<column> method on ActiveRecord models in Rails without needing to define said method. Rails achieves this via the method_missing feature in Ruby’s object system.

In Ruby, if a message is sent to an object, and that object doesn’t have an implementation for it, the method_missing method is called instead with the original method name as a parameter. By default, this raises an exception, but developers have the ability to override and provide custom behavior. This is where Rails builds and caches customized database query functions.

It turns out, we can emulate this dynamic nature pretty easily within our system:

let SQLBuilder = { (table: String) -> Object in
    return { (msg: Message) in
        let field = msg.stringByReplacingOccurrencesOfString(
            "sort-by-",
            withString: "")

        if field != msg {
            return "SELECT * FROM \(table) ORDER BY \(field)"
        }

        return nil
    }
}

let s = SQLBuilder("user")

s("sort-by-age")  // => "SELECT * FROM user ORDER BY age"
s("sort-by-name") // => "SELECT * FROM user ORDER BY name"
s("group-by-something") // => nil

We’re missing the robustness of a dynamic Object superclass to route things, but hey, we’ve got the same results 😉

Conclusion

In the end, our object system is neither featureful nor expressive.

But to me, the most important takeaway is that given certain fundamental functional language features, any developer could have come up with and implemented OOP. At its core, the concepts and patterns of OOP are very simple – and it’s just that.

OOP can be thought of as a set of (helpful!) patterns that can be implemented on top of a more fundamental, functional paradigm. We can truly say that “objects are a poor man’s closures”.

The code in this article is available as a gist.

Implementing a Small DSL in Swift

2015-10-28T00:00:00-04:00

I was working on an iOS project earlier today when I ended up running into an annoying bug in my Swift Core Data stack. My seemingly correct NSFetchRequest code was returning nil for all inputs, and I couldn’t figure out why.

After inspecting and thinking through totally different parts of the codebase, I had an ah-hah moment! I went back to my fetch request code and sure enough I saw something resembling the following:

let predicate = NSPredicate(format: "%@ = %@", key, value)

Those acquainted with Core Data will probably notice my error pretty quickly: I accidentally formatted key as a value type! The format string should actually be %K = %@, that way Core Data will know that key is in fact, a substitutable key. Otherwise, it will simply perform string comparison between the two String values.

I lamented that there was no error checking in format strings and quickly moved on. However, I had the idea in the back of my mind that a small, focused, problem-driven language, or Domain Specific Language, could easily be built in Swift to aid in basic validation/cleanliness of NSPredicate construction.

Overview

I figured a limited proof of concept DSL for NSPredicate construction could be made pretty quickly for “fun” 😉 As a baseline, all I wanted to support was:

Referencing keypaths and simple String-convertible constant values
Checking keys against values with comparison operators
Combining expressions with logical operators, such as AND and OR

My goal syntax was something resembling the following:

let predicate = NSPredicate("foo" == true && !("bar" == 4))

Luckily for me, this experiment turned out to be relatively straightforward thanks to many of Swift’s powerful language features. Let’s dive straight into the implementation!

Note: This article is also available as an Xcode Playground on Github.

Keys and Values

We’ll start with the most simple object to represent: a keypath. A keypath is simply a string that represents a (potentially nested) property, for example amountDeposited or parent.firstName. To encode this in our DSL, we’ll simply represent a KeyPath as a String:

typealias KeyPath = String

The second most simple object type to represent is a constant value. Again, in our simplified DSL, we’ll only be supporting values that can be directly represented as strings. Thus, we simply want ValueType to be those objects that are CustomStringConvertible:

typealias ValueType = CustomStringConvertible

A more full-featured DSL would not be encoding values into strings, but this representation will suit our small experiment 👍🏼

Operators

Now we can represent the names and values of things we want to query. However, we need a way to relate the two: this is where operators come into play.

We’ll support a small subset of comparison and logical operators for querying data. These can be easily represented by Swift’s ever-helpful RawRepresentable-backed enum type:

enum Comparison: String {
    case EqualTo = "="
    case GreaterThan = ">"
    case LessThan = "<"
    case And = "&&"
    case Or = "||"
}

Given that we’ll eventually want to convert these Comparison values into a String representation, we’ll adhere to CustomStringConvertible ourselves. Because we’ve already defined a nice string for the rawValue, we’ll simply return that for our implementation.

extension Comparison: CustomStringConvertible {
    var description: String { return rawValue }
}

Tip: We could have easily made calls to rawValue in our code later for String versions of our operators, but I consider implementing CustomStringConvertible a cleaner mechanism. For one, it gives you a free initializer: let str = String(Comparison.EqualTo). But more importantly, it keeps the “storage mechanism” of Comparison abstracted out.

Expressions

The Expression type will represent a value or compound comparison of values that we can convert to an NSPredicate. In our DSL’s simplified model, there are four types of values:

A property
A constant
A negated expression
A compound expression connecting two subexpressions

These concepts can be directly translated into Swift via yet another enum. However, this time we’ll be creating a recursive enumeration:

indirect enum Expression {
    case Property(KeyPath)
    case Constant(CustomStringConvertible)
    case Negated(Expression)
    case Binary(Expression, Comparison, Expression)
}

The complex cases to explain here are Negated and Binary.

An Expression of type Negated is simply a subexpression with an additional tag attached saying that it should be negated. Likewise, Binary is composed of two subexpressions related by a Comparison operator. In both of these cases, the subexpressions could be anything from a simple Property to another Binary relation.

Feel free to read up on Algebraic Data Types if you want to learn more about structuring data like this!

At this point, we have enough ground-level types to represent what we want to eventually generate. Next, let’s take a look at how we can build up an NSPredicate.

NSPredicate Creation

Our DSL implementation will create NSPredicates by concatenating String representations of our query together. Keypaths, constants, and operators are already strings (or string convertible) but how do we stringify an Expression?

You might have guessed it: Recursion again!

By defining how to convert the simple cases of Expression to a String (the Property and Constant cases), we can implement the more complicated cases on top. Let’s take a look at the code:

extension Expression: CustomStringConvertible {
    var description: String {
        switch self {
        case let .Property(key): return key
        case let .Constant(value): return String(value)
        case let .Negated(expression): return "!(\(expression))"
        case let .Binary(lhs, op, rhs): return "(\(lhs)) \(op) (\(rhs))"
        }
    }
}

Now that we can fully convert an Expression, our simplified representation of an NSPredicate, to a String, we simply need a clean way to pass it to NSPredicate itself. To do this, we can define a convenience initializer:

extension NSPredicate {
    convenience init(_ expression: Expression) {
        self.init(format: String(expression))
    }
}

After all this work, let’s stop, take a look, and verify that we’ve got something that works:

let expr1 = Expression.Property("amount")
let expr2 = Expression.Constant(300)
let expr3 = Expression.Binary(expr1, Comparison.EqualTo, expr2)
let pred = NSPredicate(expr3)  // amount == 300

Cool, but it’s still a lot of typing 😒 Now for the fun part…

Syntactic Sugar

The main problem with the current state of our DSL is that we have no clean way to create and combine expressions.

Swift’s literal convertible protocols will aid in being able to construct values and keypaths easily, while operator overloading will provide the basis of a sugary combination syntax.

Literal protocols will allow us to type a value such as 3 and have it automatically converted to Expression.Constant(3), for example. Likewise, it’d be great if strings were automatically interpreted as keypaths. We support this behavior by adhering to a number of different protocols and defining specialized initializers.

I’ve implemented Bool, String, and Integer conversion in the snippet below - it’s pretty much plug ‘n’ chug mapping values into Constant, etc. cases:

extension Expression: BooleanLiteralConvertible, IntegerLiteralConvertible, StringLiteralConvertible {
    typealias ExtendedGraphemeClusterLiteralType = StringLiteralType
    typealias UnicodeScalarLiteralType = StringLiteralType

    init(booleanLiteral: Bool) {
        self = .Constant(booleanLiteral)
    }

    init(integerLiteral: Int) {
        self = .Constant(integerLiteral)
    }

    init(unicodeScalarLiteral value: UnicodeScalarLiteralType) {
        self = .Property(value)
    }

    init(extendedGraphemeClusterLiteral value: ExtendedGraphemeClusterLiteralType) {
        self = .Property(value)
    }

    init(stringLiteral value: StringLiteralType) {
        self = .Property(value)
    }
}

Next, we’ll use (abuse?) some operators for combining expressions. The most obvious way of implementing a simple, readable DSL for predicates is by overloading the relevant comparison and logical operators to work on Expression objects as well.

Here’s a snippet of a couple of implementations as an example:

func ==(lhs: Expression, rhs: Expression) -> Expression {
    return Expression.Binary(lhs, Comparison.EqualTo, rhs)
}

// ...other operators omitted for brevity...

prefix func !(expr: Expression) -> Expression {
    return Expression.Negated(expr)
}

Implementing the syntactic sugar for this DSL ends up being little more than tying an operator with the matching Expression case.

As a note, it’s always worth thinking whether the above is a good idea, or if you should introduce your own operators instead. The second case should almost always be the preferred solution, but if the semantics of an existing operator fits 100% with your data structures (think a Vector type that could work with +, etc) then it might be okay to overload.

Now that we’ve got some of the philosophy out of the way, let’s give it a spin:

let bourbonExpr: Expression = ("proof" > 100 && "name" == "Wild Turkey")
let deletedExpr: Expression = ("deleted" == true)

Final Example

As a working final example, we’ll define a Person structure, and filter an NSArray of people using an NSPredicate constructed in our DSL:

class Person: NSObject {
    let tweets: Int
    let age: Int

    init(tweets: Int, age: Int) {
        self.tweets = tweets
        self.age = age
    }
}

// Setup some contrived, inaccurate data ;)

let people: NSArray = [Person(tweets: 250, age: 18),
                       Person(tweets: 80, age: 22)]

// --> [{NSObject, tweets 250, age 18}, {NSObject, tweets 80, age 15}]

let pred = NSPredicate("tweets" > 200 && "age" == 18)

// --> "tweets > 200 AND age == 18"

let filtered = people.filteredArrayUsingPredicate(pred)

// --> [{NSObject, tweets 250, age 18}]

Looks neat, plus you get some minor validation wins done by the compiler. Note, however, it is still entirely possible to construct an invalid NSPredicate with the existing DSL - it’s more demo/thought experiment than production-ready library!

Practically speaking, a similar, type-checked, more fleshed out DSL could perhaps end up being useful for Core Data development, where you are limited to the string parsing predicate API. For other applications, however, block predicates or SequenceType’s filter function will potentially solve the problem better.

Wrapping a C Library in a Swift Framework

2015-10-05T00:00:00-04:00

I recently started work on a project where I wanted to wrap up a C library for OS X with a more palatable Swift framework interface. My first thought was to follow what I saw in Apple’s Mix and Match documentation, a guide to integrating C/Objective-C with Swift code.

The guide tells you to create a Bridging Header, a file where you can denote the needed non-Swift dependencies for the compiler to then expose to your Swift code. However, when following this advice with a framework target, Xcode gives you this friendly error:

After much searching, poking, and prodding, I came across the SwiftGo project, which appeared to have the same setup as I needed. (Kudos to @loganwright from the iOS Developers Slack for pointing this out!)

I ended up reading the source of SwiftGo and creating an example wrapper project for progressbar, a simple C library to display a progress bar with ncurses, as I went along. Check out the final project here.

Now, let’s take a look at how it’s set up.

Creating the Project

First, we’ll start out by creating the project. Given that we want to target Mac OS X, we’ll want to start out with a Cocoa Framework type:

Name the project “Progressbar” and save it somewhere.

The Wrapped Library

Next, we’ll want to pull in the progressbar C library, our only dependency:

$ cd Progressbar
$ mkdir Dependencies
$ git clone git@github.com:doches/progressbar.git

If you take a look at progressbar’s code, you’ll see it is actually comprised of only a few files:

$ cd progressbar
$ ls include/
progressbar.h statusbar.h
$ ls lib/
progressbar.c statusbar.c

To include these in our wrapper library, open a Finder window and drag all of the above files into the existing Xcode project. I created a few Groups in the project to help organize things:

Module Mapping

We’ve now got our C library into our Swift project (and Xcode will even compile it all), but we have no way to call it from Swift. To remedy this, we use a Module Map.

The module.map file is a Clang-specific file that “describes how a collection of existing headers maps on to the (logical) structure of a module.” Luckily for us, these files are simple to create and will allow Clang to do most of the work for us!

Inside of the main source directory (Progressbar), create a file called module.map with the following contents:

module Libprogressbar [system] {
  header "Dependencies/progressbar/include/progressbar.h"
  export *
}

Feel free to drag and drop it into Xcode for easy editing (but note this is not actually necessary).

Next, we need to inform Xcode of the whereabouts of this file. Open up the Project settings for Progressbar, select Build Settings, and look for the one titled Import Paths under Swift Compiler - Search Paths.

Change it the value of this setting to $(SRCROOT)/Progressbar and ensure that non-recursive is selected. Your module.map file should be in the folder displayed by Xcode.

Now we can now simply (in Swift parlance) import Libprogressbar and access all of the C functions, macros, etc. underneath it.

The Wrapper

For this example project, I only ended up writing a minimal wrapper around the original C library for demonstrative purposes. In any case, wrapping a C library like this allows callers to only have to deal with native Swift types, keeping their application layer nice and clean.

The code for our Progressbar wrapper is below (any calls to the Libprogressbar module are interfacing directly with the C library we included):

import Foundation
import Libprogressbar

/// Class outputting an animated terminal progress bar.
public final class Progressbar {
    let bar: UnsafeMutablePointer<progressbar>

    public init(text: String, max: UInt) {
        let cstring = (text as NSString).UTF8String
        bar = Libprogressbar.progressbar_new(cstring, max)
    }

    public func increment() {
        Libprogressbar.progressbar_inc(bar)
    }

    public func finish() {
        Libprogressbar.progressbar_finish(bar)
    }
}

Example Usage

With our wrapper defined, we can finally write some simple application code to test our framework:

import Cocoa
import Progressbar

let max: UInt = 30
let bar = Progressbar(text: "foo", max: max)

for i in 1...max {
    bar.increment()
    sleep(1)
}

bar.finish()

// Example Output:
// foo |==================================   | ETA: 0h00m02s

If you’re following along with the Xcode project, check out the Playground file under the Example group. If you have the Console Window open (⌘-Shift-Y), you should see a progress bar animating over the course of 30 seconds.

An Observable Pattern Implementation in Swift

2015-10-01T00:00:00-04:00

Over the past few days, I’ve been working a new Mac app in Swift as a part of Gumroad’s Small Product Lab challenge. This app contains a simple struct type, AppConfig, representing the application’s editable configuration. What I needed to build was a view controller for the user to edit and update said values, and this is where I ran into trouble.

The normal pattern in the Objective-C world to implement this is to use Cocoa Bindings, an awesome feature implemented on top of KVO that allows you to automatically bind your (Mac) UI to instance variables in Interface Builder.

However, Cocoa Bindings will only work for types that are subclasses of NSObject. I felt that porting my AppConfig struct over to a class, let alone an NSObject subclass, conflicted with the fact that it was better represented as a value type, and I definitely didn’t want to needlessly bring in the Objective-C runtime for this simple case.

Given that I’ve been working on this app to both scratch an itch and to use Swift in a practical setting, I decided to write my own native Swift implementation of the Observable Pattern.

Protocols Everywhere

To begin with, I wanted to come up with a protocol that I could implement to satisfy my data binding woes. I decided on a subscribe/unsubscribe type model, passing in an owner/observer as the object to update a subscription off of.

protocol ObservableProtocol {
    typealias T
    var value: T { get set }
    func subscribe(observer: AnyObject,
                   block: (newValue: T, oldValue: T) -> ())
    func unsubscribe(observer: AnyObject)
}

Assuming we are in some type of object context with self, implementing the Observable protocol would allow code to be written somewhat like this:

let initial = 3
var v = initial
var obs = Observable(initial)

obs.subscribe(self) { (newValue, oldValue) in
    print("Object updated!")
    v = newValue
}

obs.value = 4  // Trigger update.
print(v)       // 4!

Perfect! Now to write it…

Implementation

Given that the Observable object has state/a lifecycle, I decided to make it a class:

public final class Observable<T>: ObservableProtocol {
    // ...
}

We’ll start out by defining a variable and a couple of handy types.

Our model of subscribers is observers, a variable array of ObserversEntry entries. Each entry is a tuple composed of a listening object and the block it expects to run upon the Observable firing. By passing in this listening object and associating it with the block to execute, we can easily look for it in the unsubscribe method to remove it.

typealias ObserverBlock = (newValue: T, oldValue: T) -> ()
typealias ObserversEntry = (observer: AnyObject, block: ObserverBlock)
private var observers: Array<ObserversEntry>

Now we’ll need to implement an init for our class. The default initializer will simply take an initial value for the observable (declaration forthcoming). Given that we’re writing Swift here, we’ll need to initialize our non-optional observers array as well.

init(_ value: T) {
    self.value = value
    observers = []
}

At this point, when we construct an Observable we’ll have an initial value. This value is even assignable, but currently we don’t have any way of telling the objects in our observers array that the value changed. To do this, we’ll implement didSet for our value variable. All we need to do is loop through our listeners and call their associated blocks. Simple!

var value: T {
    didSet {
        observers.forEach { (entry: ObserversEntry) in
            // oldValue is an implicit parameter to didSet in Swift!
            let (_, block) = entry
            block(newValue: value, oldValue: oldValue)
        }
    }
}

Last but not least, the mechanism to notify observers is in place, but we have no way to update the observers array. We’ll implement subscribe and unsubscribe to package up and add/remove observer tuples into the internal array.

func subscribe(observer: AnyObject, block: ObserverBlock) {
    let entry: ObserversEntry = (observer: observer, block: block)
    observers.append(entry)
}

func unsubscribe(observer: AnyObject) {
    let filtered = observers.filter { entry in
        let (owner, _) = entry
        return owner !== observer
    }

    observers = filtered
}

That’s all it takes!

Note: Please keep in mind that this is a simple, naïve, implementation without any considerations for performance, etc.

Syntactic Sugar

While this works, I figured I could throw in just a little syntactic sugar to reduce the repetition of writing foo.value = <value>. I decided to override the << operator:

func <<<T>(observable: Observable<T>, value: T) {
    observable.value = value
}

Update: It appears I’ve been (fairly!) called out here by none other than Chris Lattner (the designer of the Swift language) himself for overriding and repurposing the bit shift operator 😉 I can’t say I disagree:

Interesting approach to implementing a bindings like system, but not too enthused about repurposing shift operator! https://t.co/qiNqvx6BS2
— Chris Lattner (@clattner_llvm) October 3, 2015

As such, if you use this code I’d recommend defining the <~ operator instead, or something else similarly unique!

Example

With the above code, you can now wire up Observable objects to UI elements and instance variables. Just what I needed! Here’s an example NSViewController implementation with an editable port value:

/// A view controller supporting editing of the app's config.
class PreferencesViewController: NSViewController {
    // The model layer.
    var configuration: ApplicationConfiguration

    // The view and object supporting the "controller".
    @IBOutlet var portTextField: NSTextField!
    var port: Observable<Int>

    // ...

    // MARK: NSViewController
    override func viewDidLoad() {
        super.viewDidLoad()

        port.subscribe(self) { (port, _) in
            // Ignore the old value, but update config with the new.
            self.configuration.port = port

            // You can trigger anything from here! Save to disk, etc...
            // Keeps action/UI code clean.
        }

        // ...
        // Assume `portTextFieldDidUpdate` is wired to be
        // called when portTextField's value updates.
        // ...
    }

    // MARK: Helpers
    func portTextFieldDidUpdate(value: Int) {
        port << value
    }
}

Download this as an Xcode Playground.

Pure Data: An Introduction

2015-08-03T00:00:00-04:00

Overview

Pure Data is a cross platform and open source visual programming language allowing you to work with audio, video, and more in a simple dataflow programming model. Over the past week or so, I’ve been exploring Pd for music and audio use and figured that a series of blog posts documenting my path of learning would be fun, helpful for others, and a good way to reinforce what I’ve covered.

This is the first entry in this potential series: we’ll be covering installation for Mac OS X, some basic dataflow programming concepts, and a few simple audio object types. In the end, we’ll build a simple Hi-Hat patch with a few tweakable parameters.

Installation

Pure Data comes in two flavors:

Pure Data Vanilla: A basic setup, but will cover everything you need to get started.
Pure Data Extended: Vanilla plus some very helpful documentation, libraries, and packages.

I’d recommend installing Pure Data Extended, as it comes with a variety of useful objects types that you would otherwise be missing. Additionally, I’ve noticed that many times Cycling74/Pure Data forum threads will reference objects built-in to only the Extended version (the helpful [sfv~] for instance).

On Mac OS X, you can either manually download these or install them with the brew command, if you are familiar.

$ brew search pd
Caskroom/cask/pd-extended
Caskroom/cask/pd

Note: I haven’t tested the Homebrew versions to see how up-to-date or functional they are. YMMV.

Before continuing, I’ll assume you have a little bit of familiarity with the Pd interface, i.e. that you have at least explored around it before reading this article. Additionally, some experience with sound synthesis will help out, but I’ll attempt to link out for further reading when needed.

Dataflow Model

The dataflow programming model of Pure Data allows you to abstract out your ideas into sequences of composable functions that immediately react to new values produced by inputs. In the audio world, this allows you to build out your instruments with a DSP-centric model of the world.

Within Pure Data, this is graphically represented by objects with wires connecting their inputs to the outputs of other objects. For example, the following patch will print out the number sent as input to the print function. Upon, changing the value of the number in Play mode (Command-E to toggle between Edit/Play modes), [print] will automatically react and print the value to the console window.

This automatic reaction to inputs is what lets us easily build interactive synthesizers, instruments, etc. Note that these inputs may come from a variety of sources: manual user input, MIDI messages, OSC, serial port data from an Arduino, and more. We’ll stick with manual user input from the GUI for now.

Next, we’ll cover some of the object and data types that are available for us to use and start building with.

Object Types

The following are the most basic forms of data and types that Pure Data supports:

Object: Think of this as similar to a function. [print], [+], [*] are examples. They may take input via pins at the top, and will produce output via pins at the bottom.
Number Box: This data type allows you to input and edit a numerical (integer or float) value. This may be sent to an input pin of an object and will re-send whenever the value changes.
Message Box: List of data that may be sent to an object upon click from the user. For example, you may describe a sequence of sampled amplitudes to send to an audio object. In a way, these are similar to function arguments.
Bang: Upon clicking, this will “trigger” another object in realtime. May be used to begin a sound’s audio envelope, etc.

Additionally, many UI components such as sliders, VU meters, etc. are supported to make your patch more usable to other people.

When it comes to the audio domain, most of what we’ll work with will be simple Object types, or functions. Sound generators, audio filters, and more are all provided as objects in Pure Data that generate potentially constantly changing signals over time. It’s worthy of note that audio objects typically have names ending in ~, such as [phasor~].

Audio Patches

Let’s start out by exploring the simplest generator available to us.

Generating Sound

The [osc~] object outputs a constant (co)sine wave at the specified frequency. You can provide a frequency to this object via a couple of methods:

[osc~ 440] will generate a constant 440-Hz sine wave.
A plain [osc~] with a Number Box connected to the top left pin will allow you to adjust the frequency of the wave at will. You may also use the first form with a Number Box attached, providing a default value that is user changeable.

[dac~], the digital to analog convertor object, allows you to output a signal to the left and right output stereo channels of your computer. When you create this object, you’ll note it has two pins: the left and right pins (obviously) map to the left and right sound output channels.

Try to set up the two prior configurations (one at a time) with output connected to the DAC in Pure Data. Press Command-/ to enable audio and Command-. to disable it. You should hear a pure, constantly sounding tone. Your patches should look something like these:

Next, we’ll try to modify (process) this audio signal before sending it to the speaker.

Processing Sound

The simplest case for modifying a signal is by affecting the the amplitude. The [*~] object will multiply N audio signals together over time. By multiplying a signal by zero, you silence it, and by multiplying it by one, you leave it unaffected. Less than one is negative gain, and greater than one is positive gain. Lets build a user-editable volume control for our oscillator by using a Number box:

Be careful when entering gain values greater than one for this patch. Given that [osc~] produces a waveform with a peak of one for amplitude, increasing this value will cause the signal to hard-clip.

By connecting up some additional machinery, we can verify that the signal is being affected as we’re expecting. Here’s a graph showing the output of the oscillator (you can see that the amplitude looks like one-quarter of the height of the graph, per the 0.25 amplitude factor):

It’s actually possible for the [*~] object to multiply two changing audio signals as well, creating a sort of amplitude/volume modulation. Instead of passing in a constant number, let’s replace it with another sine wave so that the volume changes periodically over time. You’re able to see how the amplitude of the wave changes from the graph:

Feel free to experiment with the frequency at which the volume is modulating. By setting the frequency of the modulation to a frequency in the audible spectrum (for example, 880), you can achieve what’s known to musicians as a tremelo.

Here’s a fun exercise: Create a vibrato effect by ever so slightly modulating the frequency, not amplitude, of the original oscillator over time at an audible speed.

Sample Patch

Next, we’re going to take what we now know and turn it into a playable patch. This section is going to cover how to create a classic white-noise based Hi-Hat instrument.

We’re going to start with the [noise~] object, an audio generator that outputs white noise, a random signal with each area of the audible spectrum equally represented. This harsh sound actually can form the basis of many other percussion instruments, such as a snare drum. If you connect [noise~] directly to [dac~], you’ll hear a sound that’s quite harsh, so we’re going to filter out some frequencies using a bandpass filter.

The [vcf~] (voltage-controlled filter) object takes three parameters: an input audio signal to filter, the base frequency at which the filtering will occur, and a Q (resonance) value that determines how “far out” the filtering will reach. Go ahead and connect the output of [noise~] to the input of a new [vcf~], with number boxes inputting 1.1kHZ (11000) and 5 for frequency and Q, respectively. Connecting this to [dac~] will produce something a little less irritating, however it’s still just a constantly playing sound, not an instrument. What we’ve done here is setup a tight filter that only allows a specific range of high frequencies from the original signal to come through, emulating the high pitch of a real hi-hat.

An ASDR envelope can shape a waveform’s amplitude over a period of time, which is what we’ll want to be able to trigger. By triggering changes in the amplitude (which should be at zero normally) on a button press, we can get the distinctive short, percussive “blip” sound of a Hi-Hat from this filtered noise. The [line~] object is a simple way to accomplish this in Pure Data.

[line~] takes a list of amplitudes and times and generates a linearly interpolated audio waveform according to the values passed in. For example, if you use a message box to feed in 1, 0.7 40, 0 30 to [line~], when triggered it will generate a waveform that initially has an amplitude of 1, moves down to 0.7 after 40ms, and falls back down to 0 after 30ms. By multiplying (*~) this with our white noise audio signal, we can create a new, snappy signal that varies over time when the envelope is triggered (via a click in Play Mode), and otherwise stays quiet. This is the basis of creating “playable” instruments within Pure Data.

For bonus points, you can hook up a Button to the ASDR message box, providing a more user-friendly (in a way) mechanism to toggle the sound. Clicking the button in Play mode will send a bang to the message box, triggering the envelope and temporarily lifting the amplitude.

If you’ve followed the above, you’ll hopefully have something similar to the following:

Your browser does not support the audio element.

It turns out that many classic drum synthesizers create sounds in similar (but perhaps more complex) ways. Bass drums can be synthesized using low-frequency sine waves, and snares can be also be created by combining a low-frequency sine wave mixed with some white noise to simulate the “snap”. Once you get started here, the possibilities are pretty much endless, only limited by your imagination.

Further Tips and Notes

MidiMock

I’ve found it helpful to download MidiMock from the App Store, and create a setup similar to the Input Stage of the demo synthesizer from the Pd tutorial on FLOSS Manuals to explore your patch more naturally with an onscreen piano.

Check the “Mac OS X” section of the Pure Data documentation on MIDI Input to get your computer wired properly.

Max/MSP and Max4Live

Max/MSP and Max4Live are two excellent products by Cycling74 and Ableton. The former is a commercial Pure Data-like programming environment with an excellent GUI, documentation, and more, and the latter is a collaboration between C74 and Ableton allowing you to seamlessly interact with Max patches as an Ableton device in your tracks. I would highly recommend both.

Other Resources

FLOSS Manuals provides an excellent, deep guide to getting started using Pure Data. Additionally, they also maintain a glossary of available objects.

Conclusion

Overall, I’ve found Pure Data/Max wonderful to work with, and it’s nice to have the ability to open up some M4L patches and see what’s going on under the covers. Additionally, just having the ability to quickly mock up an instrument idea without having to learn a VST library, etc. is phenomenal. Hopefully this guide was able to transfer some of my excitement over to you! My plan for the next article in this series is to build a MIDI-capable, monophonic, two-oscillator synthesizer.

Vim for iOS Development: Setting up ctags

2015-06-25T00:00:00-04:00

Overview

With projects like cocoa.vim and vim-ios, iOS developers have a variety of helpful tools when deciding to build an app in Vim. However, with implementation files, header files, and the numerous set of frameworks we use to build apps, I’ve always found auto-completion and code navigation to be particularly difficult when writing Objective-C, especially when dealing with larger projects.

To remedy this, I’ve started using a very old tool, called ctags. ctags is able to parse source code and index methods, functions, classes, etc. for quick access later. Modern versions of Vim are built with ctags support by default, so this makes for a very easy integration.

Let’s get started.

Setup

Luckily for us, Mac OS X comes with ctags installed by default …but unfortunately for us, this version (despite what the documentation says) doesn’t support Objective-C. We’ll have to use Homebrew to install a newer version. Start by executing the following to install the latest and greatest version of ctags:

$ brew install ctags --HEAD

Next, let’s define a few default flags to always use when running ctags. These can be specified in a .ctags file in your home directory:

$ cat ~/.ctags
--recurse=yes
--tag-relative=yes
--exclude=.git

Finally, we’ll set up a bash alias to make our lives easier when running ctags. Unfortunately, ctags assumes all .m files are Matlab files, not Objective-C implementation files, so we’ll create a new command we can use that will ensure .m files are treated in the way that we need. Go ahead and add the following line of code to the .bash_profile file in your home directory:

alias ctags-objc="ctags --languages=objectivec --langmap=objectivec:.h.m"

At this point, we’re ready to start processing our code.

Indexing Your Project

If you’ve been following along word-for-word so far, you can simply run the following command from your project’s root directory to create a local tag index:

$ ctags-objc

This will create a file called tags that Vim is smart enough to read. Now, if you open Vim in this directory, you should be able to start jumping through your project’s source code already. Try the following command from within Vim:

    :tag <ClassFromYourProject>

You should be taken directly to the @interface declaration for your class.

This is a great start, but oftentimes as iOS developers we find that we need to take a deeper look and check out the headers or documentation for an Apple Framework instead of our own code.

Indexing System Headers

Let’s begin by generating tags for some of the more commonly-used Apple Frameworks. We’ll start by opening up the folder containing all of the iOS and Mac OS X frameworks and peering inside:

$ cd /System/Library/Frameworks
$ ls
AGL.framework
AVFoundation.framework
AVKit.framework
Accelerate.framework
Accounts.framework
AddressBook.framework
AppKit.framework
AppKitScripting.framework
AppleScriptKit.framework
AppleScriptObjC.framework
ApplicationServices.framework
AudioToolbox.framework
...

Here, every Framework that we can include and link to has a corresponding *.framework folder with parseable header files inside. We can use these files to generate a global tag list for all of the Frameworks we use on a daily basis. I’d start with just a few Frameworks - a tag file containing all of them gets pretty slow to search, at least on my system.

By using the --append and -f flags in ctags, we can output and append tags to a file of our choice. I like to keep the MapKit, CoreLocation, and Foundation frameworks in my database. Anytime you want to add a Framework to your tags database, a command like the following will work:

$ cd CoreData.framework/
$ ctags-objc --append -f ~/Documents/global-objc-tags

Do this for a couple of your most often-used Frameworks to get a good base.

Next, we’ll add tags for UIKit. The UIKit frameworks are stored on a per-iOS SDK basis deep inside of the Xcode.app folder, so we’ll need to start by navigating there (make sure to substitute the 8.3 in the next command for the iOS version you want):

cd /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS8.3.sdk/System/Library/Frameworks/UIKit.framework/Headers

Now, we can just run the same command as above to append to our global tag list:

$ ctags-objc --append -f ~/Documents/global-objc-tags

At this point we’ve got two tag databases ready — one for our project, and one for the Frameworks we intend to use. Let’s jump back over to Vim.

Vim Configurations

As we saw above, Vim was smart enough to find and automatically take a look at the local tags file to process our codebase. However, we need to tell Vim about the global Objective-C tags we just generated. Using an autocmd will be a great solution to make this database searchable only when we’re in an Objective-C file.

Open your .vimrc file and add the following:

if has("autocmd")
  autocmd BufNewFile,BufRead *.h,*.m set tags+=~/Documents/global-objc-tags
endif

Now, we’ll be able to automatically search our local and global tag databases for any project that we open.

Basic Usage

Now that we’ve built our full tag archive, we can start querying and jumping around our (and Apple’s) codebases. The following commands and key combinations will form a good start for poking around.

:tag <Class, Method, Protocol, Type...>

This command will let you go to the definition of the given tag (try it with an Apple Framework class this time — UITableViewDataSource always has details to the method signatures that I forget). Once you’re done, you may use <c-t> or :bd to leave.

:tselect <...>

This form is the same as the above tag except that if more than one match is found, a menu is presented where you may choose which definition you want to jump to. Additionally, this is a good command to use the / search modifier with. For example, to find tags beginning with NSAss the :tselect /NSAss command may be issued.

:tags

This command provides a menu of previously-found tags from your current session. Simply type the number of the tag you want to view and press Enter to jump to it again.

<c-]>

This normal mode command will perform a :tag command for the currently selected word. Try putting your cursor within a class name and executing this.

<c-x> <c-p>

In insert mode, this will provide an autocompletion menu based on tag file contents. The arrow keys navigate the list, <c-y> accepts and inserts, and <c-e> cancels the prompt.

:CtrlPTag

Finally, if you’re a ctrlp.vim user (which you should be!), you can use this command to search tags in realtime. I use this often enough that I’ve bound it to <leader>t.

Conclusion

You should now have a basic working knowledge of how to generate and view tags for Objective-C projects in Vim. However, there are many, many more commands available to aid in navigating your source with ctags. Give the :help tags page a read for more information.

Additionally, it’s worth noting that there are a wide variety of user-contributed plugins that can aid your usage of ctags. Check out TagBar and EasyTags for viewing and maintaining your tags, respectively.

Shameless plug: If you’re a Vim user and iOS developer, you also may enjoy my vim-carthage plugin. Give it a shot!

Visual notifications for nose Tests

2011-08-03T00:00:00-04:00

I’d like to announce that I’ve written a very simple, but useful, plugin for the nose testing framework. It uses pynotify, the Python interface to the Notify OSD server, to display notifications at the end of test suites. I’ve given it the decidedly uncreative name of nose-pynotify. Here it is in action after runing a simple test suite:

Installation

You have a couple of options to install nose-pynotify. These include using easy_install, pip, or manually running setuptools on the code downloaded from the repository:

$ easy_install nose-pynotify

$ pip install nose-pynotify

$ python setup.py install

Usage

To enable nose-pynotify for a single run, you can simply pass in a command-line switch:

$ nosetests ... --with-pynotify

# Or export the environment variable $NOSE_WITH_PYNOTIFY
# to enable the plugin by default:

$ cat ~/.zshrc

# ...
export NOSE_WITH_PYNOTIFY=1
# ...

$ nosetests

Conclusion

Naturally, the plugin is hosted on Github. Have fun testing and feel free to send me pull requests!

Clustering in Ruby

2011-05-28T00:00:00-04:00

Clustering algorithms play a very important role in many modern web applications that feature machine learning. This article will introduce you to one of the simplest techniques for the unsupervised grouping of related objects, or clustering.

If you’re at all interested in automated data grouping or sorting you should at least be familiar with one or two types of these algorithms (in addition to more advanced Machine Learning topics, but this serves a good start). In this article, I’m going to go through the process of implementing a very simple Ruby program that can group a set of 2D coordinates into clusters, where each group is composed of a center point, and all of the data points closest to it.

The algorithm that we’ll be using to accomplish this task is a simple one; k-means clustering will give us the behavior that we want with little fuss.

Overview

Our k-means clustering algorithm takes in, as input, a set of points in the 2-dimensional plane. As output, the points will be grouped into k clusters, where k is an integer specified by the user. Unfortunately, the algorithm can’t decide how many groups there are by itself without more complication, so k must be given. Nonetheless, I’ll describe the algorithm below:

Start by choosing k random points within the dataset’s range as an initial guess for the positions of all the clusters. These points form the centroid point of all the clusters. All distances to other points will be measured from here.
For each point in the input data, assign it to the cluster that it is nearest to. After this step, each cluster will somehow be associated with a set of nearby points.
For each cluster, go through the set of associated datapoints and calculate the average among them. This will give a new centroid point that is directly in the center of all of the member points.
If the clusters didn’t move from their previous locations after recentering, or if they all move less than a certain delta value, return the k clusters and their associated points. Otherwise, go back to Step 2 after deassociating all of the associated points with their cluster. This lets the algorithm start fresh, but with more accurate centroid points.

Implementation

To begin with, we’ll need a class to store the points to be clustered by the algorithm. Essentially, we just need a Point class to hold x and y values. This is implemented below (I won’t insult your intelligence trying to explain it):

class Point
  attr_accessor :x, :y

  # Constructor that takes in an x,y coordinate
  def initialize(x,y)
    @x = x
    @y = y
  end

  # Calculates the distance to Point p
  def dist_to(p)
    xs = (@x - p.x)**2
    ys = (@y - p.y)**2
    return Math::sqrt(xs + ys)
  end

  # Return a String representation of the object
  def to_s
    return "(#{@x}, #{@y})"
  end
end

Next, there has to be a class to hold clusters of data. As the algorithm described, clusters have groups of member points and a center point (not necessarily in the dataset) associated with them. This corresponds to two instance variables: @points, a list of Points, and @center, a single Point. Additionally, there needs to be a way for Clusters to update by averaging their member points. This is implemented in recenter!.

class Cluster
  attr_accessor :center, :points

  # Constructor with a starting centerpoint
  def initialize(center)
    @center = center
    @points = []
  end

  # Recenters the centroid and removes associated points
  def recenter!
    xa = ya = 0
    old_center = @center

    # Sum up all x/y coords
    @points.each do |point|
      xa += point.x
      ya += point.y  
    end

    # Average out data
    xa /= points.length
    ya /= points.length

    # Reset center and return distance moved
    @center = Point.new(xa, ya)
    return old_center.dist_to(center)    
  end
end

Finally, the algorithm itself needs to be implemented.

The parameters to the kmeans function are a dataset (list of Points), data, number of clusters to find, k, and an optional halting delta, delta. The algorithm will halt when all of the clusters are updated by a value less than delta on an iteration.

def kmeans(data, k, delta=0.001)

Initially, the algorithm needs to choose the starting guesses for cluster centers. It does this by generating k Cluster objects, and assigning them a center from a randomly selected Point from data.

clusters = []

# Assign intial values for all clusters
(1..k).each do |point|
  index = (data.length * rand).to_i

  rand_point = data[index]
  c = Cluster.new(rand_point)

  clusters.push c
end

# ... code to follow below ...

Next is the main meat of the algorithm. The code loops indefinitely and assigns points to clusters by finding, for each point, which cluster center is the closest. This assignment will be updated, and become more accurate, each iteration of the loop while the clusters recenter.

# Loop
while true
  # Assign points to clusters
  data.each do |point|
    min_dist = +INFINITY
    min_cluster = nil

    # Find the closest cluster
    clusters.each do |cluster|
      dist = point.dist_to(cluster.center)

      if dist < min_dist
        min_dist = dist
        min_cluster = cluster
      end
    end

    # Add to closest cluster
    min_cluster.points.push point
  end

  # ... code from below ...
end  # end of while loop

Finally, in the code at the bottom of the while loop, we recalculate the centers of the clusters for the next iteration. This is done by calling recenter! on all of the Cluster objects. Additionally, we do some delta checking because we need to leave the loop eventually. By keeping track of the most that any Cluster was updated, we can compare it against delta to see if all of the Clusters were below the input delta. If the delta was hit, the algorithm terminates, returning a list of all of the Clusters found in the dataset.

  # Loop
  while true

    # ... code from above ...

    # Check deltas
    max_delta = -INFINITY

    clusters.each do |cluster|
      dist_moved = cluster.recenter!

      # Get largest delta
      if dist_moved > max_delta
        max_delta = dist_moved
      end
    end

    # Check exit condition
    if max_delta < delta
      return clusters
    end

    # Reset points for the next iteration
    clusters.each do |cluster|
      cluster.points = []
    end

  end  # end of while
end  # end of kmeans()

Overall, k-means clustering is a pretty simple algorithm, as you can see from above. The entire source file, along with glue/integration code, is available here to download and/or view. Next, let’s see the program in action.

Example Run

As you can see from the link above, I ended up writing some additional shell code to implement reading in data, getting k, and plotting the output of the algorithm. For the plotting, I used rgplot (gem install gnuplot) to pipe commands to a running instance of Gnuplot.

To run the full program, open up a terminal and execute:

$ ruby kmeans.rb CSVFILE

The program assumes CSVFILE has two comma-separated floating point numbers per line, specifying both the x and y coordinates of a single point.

To give you a feel for the output that k-means generates, I ran it on a random dataset. In the graph below, each set of points plotted with the same color indicates a Cluster object’s member points. To run this yourself, you can grab my dataset here, although creating your own with more definite, pre-designed clusters may be more interesting to see.

Conclusion

While this is a very simple example, note that the x and y axis can be whatever you want them to be (latitude/longitude of households, baseball stats, etc). You could even (easily) extend the program to support 3 or more parameters (dimensions). Thus, k-means clustering can actually be a powerful tool for grouping real-world datasets, despite the apparent simplicity.

tq: A Tool to Stay Focused

2011-05-15T00:00:00-04:00

I like simple tools. I like tools that do their one required thing, get out of my way, and let me get stuff done. When looking for a way to keep a task list, I was completely overwhelmed by all the to-do software out there. So I built my own.

Enter tq

After reflecting on how I work when I actually get stuff done, I realized I typically like to finish my tasks in a queue, one at a time. I come up with the tasks I need done, break them into a bunch of simple subtasks, write them down sequentially, and hack on down the list. So I wrote a shell script that lets me manage tasks like that. tq, or task queue, is the result of this idea. It implements the following actions:

tq push ITEM — Add a todo item to the end of the list.
tq pop — Mark the current item as “done” and display the next item in line.
tq peek — Display the current item.
tq cheat — Open the task list in $EDITOR.

This is the most basic feature set I could come up with, and from experiments using it, the design seems to work well. It’s easy to stay on task, keep focused, and get stuff done. Just how I like it.

Example

Here’s a look at how the tool works:

$ tq
  Usage: tq CMD

    CMD can be:
      push ITEM Add ITEM to the end of the queue
      pop       Remove current item from the queue and
                print out the next item
                in the list to work on
      peek      Print the current item being worked on,
                i.e. the front of the queue
      cheat     Edit the taskfile with $EDITOR

$ tq push "ponder some ideas..."
$ tq push "write resulting CLI app"
$ tq push "write blog post"
$ tq push "PROFIT?"
$ tq peek
ponder some ideas...
$ tq pop
write resulting CLI app
$ tq pop
write blog post
...

Source

I wrote tq as a simple 31-line bash script. It’s not much, but it has paid off its rent, so to speak.

Note: Before using this tool, you should set $TASKFILE to the file you want to keep your task queue in (I actually keep mine on Dropbox).

#!/usr/bin/env bash
# tq - a script to maintain a simple task queue
 
TASKFILE=~/Documents/tq.txt
 
# File check
if [ ! -f $TASKFILE ]; then
  touch $TASKFILE  
fi
 
# Main driver
if [ "$1" == "push" ]; then
  shift
  echo "$*" >> $TASKFILE
elif [ "$1" == "pop" ]; then
  tail -n +2 $TASKFILE | tee $TASKFILE | head -n 1
elif [ "$1" == "peek" ]; then
  head -n 1 $TASKFILE
elif [ "$1" == "cheat" ]; then
  $EDITOR $TASKFILE
else
  cat <<EOF
Usage: tq CMD
 
CMD can be:
  push ITEM Add ITEM to the end of the queue
  pop       Remove the current item from the queue
            and print out the next item
            in the list to work on
  peek      Print the current item being worked on,
            i.e. the front of the queue
  cheat     Edit the taskfile with \$EDITOR
EOF
fi

You can wget the raw source file here.

A Genetic Algorithm in Python

2011-05-01T00:00:00-04:00

In the spirit of taking biology and artificial intelligence this quarter, I decided to try to throw together a program combining the concepts of the two. I ended up writing a python script that performs “natural selection” of a population of initially random strings towards an ideal “Hello, World” string, implementing a really basic genetic algorithm.

The Algorithm of Evolution

Before we look at the code, I’m going to go over the basics of how the “algorithms” of evolution and genetics work (or at least the simple model of it that we’ll use).

To begin, we generate a random initial population of organisms. This will serve as the set of organisms from which we will evolve better, more-fit forms. Next, we implement natural selection by iterating over the following steps for each generation that we would like to simulate:

Assign a fitness value to each organism in the population. This should reflect how well the individual is suited to survival in the current environment.
Map the fitness value to a probability of being picked to survive into the next generation. Individuals with more fitness should be more likely to be selected to survive.
Create a “working population” by choosing individuals from the population with the chance of each being chosen based on their calculated probabilities. This means that individuals can be chosen many times, once, or even not at all.
Create “offspring” between each pair of two organisms from the working population by combining DNA from each parent. In our program, each set of parents will produce 2 offspring to drive the new generation, keeping the population levels constant.
Randomly mutate each individual’s genes slightly. This ensures genetic diversity remains within the population.

At the end of this process (once a certain fitness or generation cap has been hit), the resulting population should be significantly more fit to the environment than in the initial population.

However: while this process can produce optimized solutions difficult for humans to design from the start, it’s important to note that nothing in this algorithm guarantees a perfectly fit organism in the end.

Implementation in Python

Now that we know how the algorithm itself will work, we can get to the code. You can either interpret this as an experiment in literate programming or as me being too lazy to write any explanation at all! Here’s the (at least highly annotated) source:

"""
helloevolve.py implements a genetic algorithm that starts with a base
population of randomly generated strings, iterates over a certain number of
generations while implementing 'natural selection', and prints out the most fit
string.
 
The parameters of the simulation can be changed by modifying one of the many
global variables. To change the "most fit" string, modify OPTIMAL. POP_SIZE
controls the size of each generation, and GENERATIONS is the amount of 
generations that the simulation will loop through before returning the fittest
string.
 
This program subject to the terms of the BSD license listed below.

Copyright (c) 2011 Colin Drake
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
"""
 
import random
 
#
# Global variables
# Setup optimal string and GA input variables.
#
 
OPTIMAL     = "Hello, World"
DNA_SIZE    = len(OPTIMAL)
POP_SIZE    = 20
GENERATIONS = 5000
 
#
# Helper functions
# These are used as support, but aren't direct GA-specific functions.
#
 
def weighted_choice(items):
  """
  Chooses a random element from items, where items is a list of tuples in
  the form (item, weight). weight determines the probability of choosing its
  respective item. Note: this function is borrowed from ActiveState Recipes.
  """
  weight_total = sum((item[1] for item in items))
  n = random.uniform(0, weight_total)
  for item, weight in items:
    if n < weight:
      return item
    n = n - weight
  return item
 
def random_char():
  """
  Return a random character between ASCII 32 and 126 (i.e. spaces, symbols,
  letters, and digits). All characters returned will be nicely printable.
  """
  return chr(int(random.randrange(32, 126, 1)))
 
def random_population():
  """
  Return a list of POP_SIZE individuals, each randomly generated via iterating
  DNA_SIZE times to generate a string of random characters with random_char().
  """
  pop = []
  for i in xrange(POP_SIZE):
    dna = ""
    for c in xrange(DNA_SIZE):
      dna += random_char()
    pop.append(dna)
  return pop
 
#
# GA functions
# These make up the bulk of the actual GA algorithm.
#
 
def fitness(dna):
  """
  For each gene in the DNA, this function calculates the difference between
  it and the character in the same position in the OPTIMAL string. These values
  are summed and then returned.
  """
  fitness = 0
  for c in xrange(DNA_SIZE):
    fitness += abs(ord(dna[c]) - ord(OPTIMAL[c]))
  return fitness
 
def mutate(dna):
  """
  For each gene in the DNA, there is a 1/mutation_chance chance that it will be
  switched out with a random character. This ensures diversity in the
  population, and ensures that is difficult to get stuck in local minima.
  """
  dna_out = ""
  mutation_chance = 100
  for c in xrange(DNA_SIZE):
    if int(random.random()*mutation_chance) == 1:
      dna_out += random_char()
    else:
      dna_out += dna[c]
  return dna_out
 
def crossover(dna1, dna2):
  """
  Slices both dna1 and dna2 into two parts at a random index within their
  length and merges them. Both keep their initial sublist up to the crossover
  index, but their ends are swapped.
  """
  pos = int(random.random()*DNA_SIZE)
  return (dna1[:pos]+dna2[pos:], dna2[:pos]+dna1[pos:])
 
#
# Main driver
# Generate a population and simulate GENERATIONS generations.
#
 
if __name__ == "__main__":
  # Generate initial population. This will create a list of POP_SIZE strings,
  # each initialized to a sequence of random characters.
  population = random_population()
 
  # Simulate all of the generations.
  for generation in xrange(GENERATIONS):
    print "Generation %s... Random sample: '%s'" % (generation, population[0])
    weighted_population = []
 
    # Add individuals and their respective fitness levels to the weighted
    # population list. This will be used to pull out individuals via certain
    # probabilities during the selection phase. Then, reset the population list
    # so we can repopulate it after selection.
    for individual in population:
      fitness_val = fitness(individual)
 
      # Generate the (individual,fitness) pair, taking in account whether or
      # not we will accidently divide by zero.
      if fitness_val == 0:
        pair = (individual, 1.0)
      else:
        pair = (individual, 1.0/fitness_val)
 
      weighted_population.append(pair)
 
    population = []
 
    # Select two random individuals, based on their fitness probabilites, cross
    # their genes over at a random point, mutate them, and add them back to the
    # population for the next iteration.
    for _ in xrange(POP_SIZE/2):
      # Selection
      ind1 = weighted_choice(weighted_population)
      ind2 = weighted_choice(weighted_population)
 
      # Crossover
      ind1, ind2 = crossover(ind1, ind2)
 
      # Mutate and add back into the population.
      population.append(mutate(ind1))
      population.append(mutate(ind2))
 
  # Display the highest-ranked string after all generations have been iterated
  # over. This will be the closest string to the OPTIMAL string, meaning it
  # will have the smallest fitness value. Finally, exit the program.
  fittest_string = population[0]
  minimum_fitness = fitness(population[0])
 
  for individual in population:
    ind_fitness = fitness(individual)
    if ind_fitness <= minimum_fitness:
      fittest_string = individual
      minimum_fitness = ind_fitness
 
  print "Fittest String: %s" % fittest_string
  exit(0)

Result

Here’s an example of output generated by the script:

Generation 0... Random sample: 'RE}36#qP'_u%'
Generation 1... Random sample: '{z?.;7CEYy#g'
Generation 2... Random sample: '0/5^aGk]yx1='
Generation 3... Random sample: 'lP6]`HBUS|1='
Generation 4... Random sample: 'l,iK%6{;<|Lk'
Generation 5... Random sample: '0/5^aGk]y][j'

Generation 1337... Random sample: 'Hdllo-fWorme'

Generation 2717... Random sample: 'Hdllo, Worme'

Generation 4999... Random sample: 'HeClo, World'
Fittest String: Hello, World

Why I Like the BSD

2011-02-28T00:00:00-05:00

Let’s find some common ground here before we start. For those of you that don’t know, the BSD is an open source software license. It is one of many “competing” licenses that aims at maximizing freedom for some group in the realm of software development and distribution. Specifically, the BSD attempts to maximize this desired freedom by saying as little as possible. Less clauses means less words means less chances to restrict a participant in the software development cycle. This stark simplicity has many implications which I will discuss later in the article.

Note: I’m not going to provide the text of the BSD license here, however short it may be. There’s Wikipedia for that. I want to discourage copying, pasting, and using without thinking (even though I’d love for the world to have more BSD-licensed software). This article merely reflects my own opinions and preferences. Furthermore, I am not a lawyer, so take what I say about this with a grain of salt. But enough with the disclaimers…

Control

As I’ve said before, the BSD is a very simple license. Unlike many of its competitors, it directly restricts only a handful of freedoms, putting it particularly near a declaration of public domain. Most importantly though, the BSD opts to say less about the developer’s liberties, which in turn increases the liberties allowed towards the end user. This is the most important quality of the BSD, because in that regard, it is unique when compared to other open source licenses, such as the GPL.

This simple ruleset manages to elegantly retain developer’s most basic rights to their code while keeping other routes of usage, not traditionally allowed by open source, free for use.

Commercialization

This lack of control allows for corporations, businesses, and users alike to share, copy, sell, and modify the project to their heart’s content. The amount of freedom given to them is very high: users can extend, rebrand, give commercial support for, or even start a business around somebody else’s BSD project. As long as a copy of the BSD license with the original author’s name is retained, the end user basically has the right to do whatever they want with it. The BSD’s sole goal here is the lack of warranty and prevention of somebody claiming other’s work as their own.

This freedom allowed Microsoft to implement Windows networking systems at a minimal cost, and gave Apple a stable base to start Mac OSX from. Rather than having to redesign and implement the wheel, both of these companies could focus on the facets of their respective project thats were the most important. This helped them get their product out of the door, and gave end users a time-tested infrastructure to work on. In short, the BSD isn’t just free. It’s profitable (both monetarily and pragmatically speaking) for all involved parties.

Simplicity

If you know me, it’s no big secret that I’m a fan of minimalism. Philip Glass’ simple arpeggios, Hemingway’s “iceburg” writing style, and the BSD all share an underlying philosophy behind them. Make your point with the least amount of extraneous bells and whistles as possible.

The BSD excels in this arena. Look at the GPL. Now, look at your man — Err, the BSD. In a few short paragraphs, the BSD manages to describe a system of distribution that strikes a perfect balance between exclusivity and openness in a way that’s fair and beneficial to everyone.

Counterarguments

Typically, I’ve found that the BSD is very versatile. Whether you’re writing your sassy new jQuery plugin to turn all H2 tags baby blue, or a device driver for an OS kernel, the BSD normally has some type of net benefit to offer you. However, I concede that there are special cases where other licenses might be more apt to your interests.

Sometimes, by choice, you don’t want people to go off and run with your idea or code. This suggests that the GPL may be a better route. This is especially true in academic or learning projects, where your main goal is not utility, but obtaining an increase in personal knowledge. The “cost” of using or modifying your project essentially becomes more open source code given back to you.

Furthermore, not all source code can or should be open sourced. I like to make as much code as I can free or open source, but sometimes you may find that your business is surviving purely because you are the only one that knows how to do something, or at least do it effectively. In these cases, a more limited, or even proprietary license, may suffice.

Cases like these don’t illustrate a failing of the BSD. They only show that you should always take into consideration your goals for any given project. Software licenses should not be a dogmatic matter. No matter how much I like the BSD, I still evaluate different licenses on a per-project basis, because sometimes a different license is just flat out better suited.

Conclusion

Again, I’d like to state that the goal of this article is not to undermine the efforts of the GPL, WTFPL, et. al. I’m only here to provide a rationale for my own preference. That being said, I think the BSD is, in general, a good choice for many kinds of projects. It is open, allows authors to get credit for their work, is compatible with for-profit software, and yet still provides freedom all around the table.