(Point At Star)

As of late I’ve been exploring ruby’s support for metaprogramming. Turns out it’s incredibly powerful. Some highlights include:

• Runtime class creation via Class.new
• Scoped eval functions for runtime class redefinition, notably, Foo.class_eval and foo.instance_eval
• Class callback method invoked upon subclass creation: self.inherited(subclass)

All of this, combined with the very Lisp-y semantics and philosophy provided by ruby add up to a great language for prototyping DSLs (though the lack of serious macro support means that syntactic manipulation is somewhat limited and needs to be achieved through trickery and operator overloading). Given that framework creation is language construction, ruby seems ripe for some extremely interesting frameworks. Rails and active record are prime examples of this, though I think they fail to fully take advantage of the malleability of the language.

I’ve decided, 95% as a learning experience and 5% because it might actually end up being useful, to attempt to augment ruby’s class system to support strict(er) typing on members. There are two main goals:

1. Class Definition With Explicitly Typed Members

This is standard fair for statically typed languages, but ruby’s duck typing completely lacks any protections around the assignment of out-of-type values to class members (or to any variables, for that matter). The plan here is to allow class declarations that look like this:

Class.create :Employee,
{
:employee_id => int,
:name => string,
:boss => :Employee,
:subordinates => :Employee[]
}

This will then be usable with standard ruby class instantiation and access syntax:

joe = Employee.new

joe.employee_id = 7

joe.boss = Employee.new { :name => "frank" }

joe.boss.subordinates << joe

And, of course, assignments like the following would result in exceptions being raised and the assignments being prevented:

joe = Employee.new

joe.employee_id = 'one' # error

joe.boss = 4 # error

joe.subordinates = [6, 7] # error

2. Cross-Member Constraints In Class Definitions

A bit more unusual, even for statically typed languages, is cross member constraints. That is, the ability to say things like “the value of field foo is always less than that of field bar” or “the number of elements in list field foos is always less than the value of field bar“.

In more explicit terms, this will look like the following:

# build constraints

lt = Constraint.create { |x,y| x < y }

bound = Constraint.create { |xs,y| xs.size < y }

# define class, apply constraints

Class.create :Klass,
{
:foo => int,
:bar => int,
:foos => int[]
}, [ lt(:foo, :bar), bound(:foos, :bar) ]

Note that the constraint definition is decoupled from the application to specific members. This means the constraints are re-usable across classes and situations. Some examples of the kinds of assignments that will be prevented by the above definition:

obj = Klass.new

obj.foo = 2

obj.bar = 1 # error

obj.bar = 3

obj.foos = [1, 3]

obj.foos << 7

obj.foos << 12 # error

Most of the code to actually do this is done and working, though I want to finish up support for subclassing and then I’ll post it as well as a discussion of some of it’s more interesting internals.

As a quick learning-ruby exercise I decided to write a simple little app that allows two parties that don’t trust each other to conduct a coin flip over the phone (or any other medium). This works thanks to what’s known in cryptography as a “commitment scheme”: a mathematical mechanism that allows one party to commit to some choice without revealing that choice to the party that they’ve committed to. In the case of a coin flip, it works like so:

1. One party, the “caller”, decides to call either “heads” or “tails”
2. The caller picks a secret password
3. The caller combines their password with their choice to produce a combined string
4. The caller use a one-way function to produce a new “commitment value” from the combined string
5. The caller tells a second party, the “flipper”, the commitment value
6. The flipper flips a coin and tells the caller the outcome
7. The caller now reveals to the flipper which side they chose as well as their secret password
8. The flipper combines the revealed password and choice to produce a combined string
9. The flipper applies the same one-way function to the combined string
10. The flipper verifies that the computed result and the commitment value they were given earlier match

The basic idea was outlined by Manuel Blum back in 1981 in the paper Coin Flipping By Telephone. The commitment scheme that I’ve used is different from the schemes outlined in the paper. I simply use a SHA1 hash to generate the commitment value. Note that while in principle any hashing function would work, it’s incredibly important to choose one that’s not vulnerable to collision generation (MD5, for example, would be a very poor choice) since collisions would allow the calling party to cheat.

You can grab the code here.

The core of the functionality is really simple:

class SecureCoinCaller

    def initialize(password)
        @password = password;
    end

    def call(side)
        @side = side;
        return Digest::SHA1.hexdigest(@password + side);
    end

end

class SecureCoinFlipper

    def receiveCall(commitment)
        @commitment = commitment;
    end

    def verify(password, call)
        result = Digest::SHA1.hexdigest(password + call);
        return (result == @commitment);
    end

end

The rest of the code in the linked source file just handles interactive prompting to walk a user of the app through the steps necessary to carry out the interaction. To try it out fire up irb and load(’secure_coin.rb’) and then instantiate a new InteractiveMode like so: InteractiveMode.new

Forgive any messiness in the code, it was hacked together quickly.

I’ve been doing a lot of thinking lately about the structure of news distribution and consumption, and in order to organize my ideas I made a sequence of diagrams depicting the organizational changes that the system’s undergone over the past 15 years or so.

First, there were just the major news organizations. They interacted with the sources of breaking news, decided what was important, summarized it, sometimes provided opinions, and then passed that on to the news consumer.

Next, blogs entered the scene. They added an additional layer of filtering, processing, commentary, and aggregation to the news consumption process. Most of their material tended to be sourced from the news organizations, but they created considerable value by providing, through their diversity, rich commentary and discussion. They also came to serve as a fairly effective error (and corruption) checking mechanism for the major news organizations.

Now, social news tools like twitter, friendfeed, and facebook have added yet another layer by filtering and processing news and links through a social network. The concept of “sharing” (or “retweeting”, or “liking”, depending on the app/platform) is essential here, and allows for highly bi-directional, horizontal information flows. Blogs, having become more numerous and mature, as well as individuals, have started contributing information about events directly as they happen, bypassing the major news organizations almost entirely in some cases.

Now to ask the question that @cshirky would say we can’t answer: what’s next? Another layer? Possibly. I’m not sure what the diagram would look like though. If there is another layer to be added, my guess would be that intelligent agents (weak AI) will be employed, and perhaps interspersed throughout our existing social networks, performing data mining and filtering on the information that passes between nodes and fetching additional items of interest from the cloud at large based on this data. Xark! has an excellent projected timeline through 2020 that’s worth checking out. It’s considerably more detailed than this post, but it’s also a bit more concerned with business models and a bit less concerned with structure of the system as a whole.

I tend to think the next step won’t be the addition of a new layer. Rather, we’ll start removing some of the old layers that the current system has been built on, much as the scaffolding for a building is removed once the structure is fully in place. It’s worth noting that prior to the development of the professional news organizations, the distribution mechanism was only the social network: we called it “word of mouth”. It had the same advantages that the newly developing web-based social news distribution networks have. It provided highly relevant information to the consumer, and allowed bi-directional commentary and discussion. It unfortunately suffered from some major flaws, specifically, it was incredibly lossy and it was highly geography-centric. This didn’t work in modern, global society. So news organizations, while failing to deliver the relevancy and two-way communication, filled the gap with lossless distribution mechanisms (papers, radio, television) that could be delivered relatively quickly to a large geographically dispersed population. Now that the internet has democratized efficient communication we’re able to drop the lumbering, inefficient intermediaries and still retain their lossless, geography-agnostic advantages. So my projection: the future is just the social network. Individuals, possibly aided by artificially intelligent agents, will describe events as they experience them, collect related information, provide commentary and opinions, and disseminate this information through a variety of sharing mechanisms.

So I’m restarting this blog from scratch. I let it stagnate too long and I didn’t really like the direction it was going in. Thus, fresh start. I’m going to attempt to keep it primarily tech and code related this time, so I’m going to be publishing snippets of code that I’m working on or theories I have about various algorithmic/CS problems. I’ll also probably engage in some internet punditry and light futurism from time to time. Feel free to comment or get in touch with me via twitter @microsage if you have any feedback.