Inferencing

Nothing to see here, move along

2009-08-24T09:01:00.000-07:00

I am not using this blog anymore.

JAOO, day one

2008-09-30T03:50:00.000-07:00

I am currently at the JAOO conference :-)

The conference seems to be buzzing with functional programming today. It started with the keynote by Anders Hejlsberg, where he talked about the future of programming languages, of which he claimed that one of the key components was functional programming. Concurrency was also mentioned as a key component. The talk also mentioned DSL's and used LINQ as example. It does seem nice - almost makes me want to play with C#. The F# language from Microsoft also seems like a nice alternative to C# if you wish the utilize the dot.net runtime. Very CAML/ML like.

A few other talks of the day made a great impression on me. I didn't see that many presentation, because I'm was working as crew most of the day.

I originally planned to go to the Aslaks rspec talk (I missed it a Rubyfools) but it was cancelled and replaced with a talk about meta-programming, and while it's an interesting topic, I've seen my share of those talks. Instead I decided to go the Fortress talk by Guy Steele - and it blew my mind! Fortress seems like a really interesting concurrent programming language. I will have to play around with this.

After the fortress talk I went to a talk about Scala, by Bill Venners. Scala is a functional language which runs on the JVM an integrates with java libraries. The talk it self was more of an introduction to functional programming for Java programmers and it didn't really mention any of the really interesting features Scala.

The final talk I went to was "Why Functional Programming (Still) Matters" by Erik Meijer. This was mindblowing. He talked about dealing with the "impurity" of languages introduced by side-effects by using monads. The idea of embracing side-effects - in the right way - rather than than shunning them was eye opening.

Extracting facebook friends from public profiles

2008-08-31T11:06:00.000-07:00

Today I just discovered a small little disclosure issue with facebook and google. Actually, the discovery was due to my girlfriend.

When you enter a public facebook profile for a person, it will display five friends of that person. Since everybody who is friends with this person also have a public profile, which also lists five friends, there is a reasonable chance that the person turns up in their profile.

Google indexes these pages, so it is possible to search these public profiles. By searching for the a particular name on facebook using google, it is possible to find a lot more friends of the person. For instance, the query

http://www.google.com/search?q=%22Christian+Theil+Have%22+site:facebook.com&hl=en&safe=off&filter=0
will list a few of my facebook friends.

I imagine that it is possible to extract quite a big portion of the facebook social network using this method.

NLP keyword on google

2008-04-23T05:34:00.000-07:00

Searching on "NLP" on google seems to bring up pages and pages of stuff on neuro-linguistic programming (psychology stuff) rather than on natural language processing.

In a recent post to comp.ai.nat-lang Amnon urges NLP people "not cede the NLP keyword without a fight". I agree with him, that this is an issue. But I am not sure how to deal with it. Even though, I believe that the abbreviation "NLP" meaning natural language processing is more scientific and probably precedes the neuro-linguistic programming use of the abbreviation (I have no definite source for this), both uses of abbreviation is equally legitimate. However, there is a big overlap in terminology used eg. linguistics, language etc.

However, it's annoying for me to have a million pages neuro-lingustic programming pages pop when I search for NLP, because I am a million times more interested in natural language processing. But google neglects this fact, although this knowledge should be derivable from my previous searches. Oppositely, it's not transparent what kind of result a given query should give me. Pagerank results in an approximation which can be compared with the lowest common denominator of query results. With gradual improvement of my query I usually find what I am looking for though, but this is besides the point.

I think there is still room for other search engines out there. I could definitely use a search engine which gave me predictable result. And a search engine that took a lot more context into consideration. But google domination (and superiority in terms on amount of indexed pages) is quite a barrier. But I think it's slowly going to happen, as the quality of googles search results deteriorates because of the exceeding amount of information. One algorithm doesn't fit all.

A scary side-effect is that because of googles domination, I think googles indexing mechanisms might have some serious impacts on the development of language and ultimately the way we think. If a search term is drowned by a more popular search term, the less popular might slowly be forgotten or loose it's place in common speak. To add to seriousness of this, it's possible to affect this by means of google bombing or similar techniques. That is what SEO is mostly about.

Until we get better search engines, I guess I might as well throw in a link to the wikipedia definition of NLP.

Natural language processing: one, Neuro-lingustic programming: zero ;-)

Better Approximate Ruby Programming

2008-03-05T14:45:00.000-08:00

Griff just sent me a nicer version of the approximatize function, which dynamically defines a module. It's a really cool hack: Now approximatize works for classes, modules and objects alike!

If the target of the function turns out to be an other module, it will include the new module in it and it's included method will do the aliasing magic. Should the target be a class or an object, it will extend it and is able to re-alias the method_missing method directly. Nice.


def approximatize(target, max_edit_distance = 1)
  m = Module.new do
    def self.included(other)
      other.send :alias_method, :method_missing_without_approximate, :method_missing
      other.send :alias_method, :method_missing, :method_missing_with_approximate
    end
      
    define_method :method_missing_with_approximate do |*args|
      meth = args.shift
      similar_methods = {}

      self.methods.each do |m|
       dist = m.edit_distance(meth.to_s)
        if dist <= max_edit_distance then
         if similar_methods[dist].nil? then
            similar_methods[dist] = [ m.to_s ]
         else
           similar_methods[dist] << m.to_s
          end
        end
      end

      # Eliminate candidates with higher edit distances than the candidates with the lowest
      similar_methods = similar_methods.min.pop unless similar_methods.min.nil?

      # Call method only if there is _exactly_ one element with the minimum edit distance
      if similar_methods.nil? or similar_methods.size != 1 then
        method_missing_without_approximate(meth, *args)
      else
        self.send(similar_methods.first,*args)
      end
    end
  end
  
  if target.kind_of? Module
    target.send :include, m
  else
    target.extend m
    target.instance_eval do
      alias :method_missing_without_approximate :method_missing
      alias :method_missing :method_missing_with_approximate
    end
  end
end

Thanks :-)

Approximate Ruby Programming

2008-03-04T04:28:00.000-08:00

What if your programming language interpreter didn't mind small spelling mistakes. Imagine that you type a method name a wee bit wrong, but the the interpreter seems to read your mind and call the correct method instead of throwing an NoMethodFound exception at you.

I've been playing a bit with this idea and found a simple but naive way this in Ruby. If you try to call a method that doesn't exist, then the method_missing method gets called. If this method_missing in turn figured out what method you really meant to call and called that instead, you where in the clear? Of course, programs can't read your mind, but a simple way of approximate this is to find the existing method with the shortest edit distance to the misspelled method and call that instead. This is pretty naive, but it will work in many cases and serve as a simple baseline. And it has a very straight-forward implementation in Ruby. Say hello to ... drumroll, please ... approximatize!.


class Example
  def test(str)
    puts "test method called: #{str}\n"
  end
end

approximatize(Example)

ex = Example.new
ex.test "a normal method call"
ex.text "Did you mean test?"
ex.tes "Did you mean test? (then you forgot a letter)"
ex.ttest "Did you mean test? (then wrote a letter to much)"
ex.and_now_for_something_completely_different

This example illustrates a simple use of approximatize. In both all cases, but the last, the test method gets called even though the method name was misspelled. However, the are no methods whose spelling resembles the last call, and thus a NoMethodError is thrown. It's possible to adjust how much error to allow, but it's recommended to keep the max_edit_distance low.

The implementation of approximatize:


def approximatize(target, max_edit_distance = 1)
  target = target.class unless target.class == Class

  target.class_eval do
    define_method :method_missing do |*args|
      meth = args.shift
      similar_methods = {}

      self.methods.each do |m|
       dist = m.edit_distance(meth.to_s)
        if dist <= max_edit_distance then
         if similar_methods[dist].nil? then
            similar_methods[dist] = [ m.to_s ]
         else
           similar_methods[dist] << m.to_s
          end
        end
      end

      # Eliminate candidates with higher edit distances than the candidates with the lowest
      similar_methods = similar_methods.min.pop unless similar_methods.min.nil?

      # Call method only if there is _exactly_ one element with the minimum edit distance
      if similar_methods.nil? or similar_methods.size != 1 then
        raise NoMethodError.new("undefined method ‘#{meth.to_s}’ for #{self}",meth,args)
      else
        self.__send__(similar_methods.first,*args)
      end
    end
  end
end

Approximatize defines an method_missing method on the target class. When invoked this method runs through all the methods of the target class and calculates the edit distance of the method. It then selects the method with the lowest edit distance and invokes it (assuming there is only one with such a low edit distance and the this edit distance is lower than the allowed threshold). If no such method can be found, it will throw a NoSuchMethod exception, as would normally have happened when you call a non-existing method.

The dynamic programming version of the edit distance algorithm is implemented directly on the String class. The running time is O(m*n) so it's feasible (polynomial) even though it is executed for each method in the target class. In practice, this doesn't seem to be a problem, since method names tend to be rather short. However, it would probably be a good idea to cache the result of the calculations, instead doing them each time a non-existing method gets called.


class String
  def edit_distance(other)
    m = []

    # create base case entries:
    0.upto(size) { |i| m[i] = []; m[i][0] = i }
    0.upto(other.size) { |j| m[0][j] = j }

    # Fill out the rest of the matrix
    1.upto size do |i|
      1.upto other.size do |j|
        etj = (self[i-1] == other[j-1])?0:1
        m[i][j] = [ m[i-1][j-1] + etj , m[i][j-1]+1, m[i-1][j]+1 ].min
      end
    end

    m[size][other.size]
  end
end

If you're the type who likes to live life dangerously and are not afraid to break things, why not approximatize your entire Ruby environment?

def approximatize_world(max_edit_distance=1)
  ObjectSpace.each_object(Class) do |clazz|
    approximatize_class(clazz,max_edit_distance)
  end
end

But there are some obvious problems with the concept and the approach:

Expect the unexpected: Sometimes the wrong method gets called. One obviously dangerous case springs to mind: The way Ruby has destructive methods ending with an exclamation mark; an edit distance of one from the original name. As such, edit distance is not very clever, and it's really sensitive when it comes to short method names. It should be possible to come up with something better, but until then, edit distance serves as reasonable baseline approximation.

It's possible to get a list of defined methods of a class, but these doesn't include aliases for methods or methods implemented using method_missing. Actually, using approximatize on a class might break it's functionality if it depends on method_missing. This can probably be fixed with some clever aliasing though. However, using method_missing like this is asking for trouble.

Of course, the approach only handles method names. Syntax errors still cause the interpreter to complain like a "strict old aunt", even though it was perfectly clear what I meant ;-) I would be nice with approximate syntax, but that would require a different kind of Ruby parser

Ahh well, so it isn't very useful in practice, but the idea seems worthwhile, doesn't it? Even if it isn't very useful it is a working prototype illustrating an interesting concept (imho). And more importantly it provided me with a couple of hours of fun :-)

php has problems

2007-11-01T01:01:00.000-07:00

Arrggh! I'm coding stuff in PHP again at work. I've done a lot PHP in past times, and even though the language has improved it's still such a exemplary piece of crap. Language design at it's worst. PHP is supposed to be a recursive acronym of: PHP: Hypertext Processor, however, these acronyms seems to describe the language equally well:

PHP Has Problems
Pretty Half-baked Programming-language
PHP Hates Programmmers (and also the other way around for many...)

Feel free to add to list..

I just needed to get my frustrations out...

RANLP conference

2007-09-30T11:42:00.000-07:00

This week I attended the RANLP conference (Recent Advances in Natural Language Processing) in Bulgaria and it has been an amazing experience. There were many really good and interesting presentations. It seems that NLP is maturing in many respects. A mindblowing conference :-)

By the way, many of the papers from the workshops are available online on the workshop homepages.

I presented a poster,
From Use Cases to UML Class Diagrams using Logic Grammars and Constraints, with Henning Christiansen and we got some good feedback.

At the Context conference

2007-08-22T13:25:00.000-07:00

I am currently attending the Context conference. The last previous two days there has been workshops and today the conference officially started.

The first day, I went to the CSLP workshop. I presented the paper, Reasoning about Use Cases using Logic Grammars and Constraints which I have coauthored with Henning Christiansen and Knut Tveitane. It was the first presentation of the day and my first paper presentation at a conference. Quite the experience trying.There were many interesting presentations at the workshop some of which I found particularly inspiring and thought provoking.

The second day I attended some talks from the MRC&CHUT-07 workshop as well as a few from the CIR workshop. Both contained some fairly interesting talks.

The third day started with very interesting talk given by David Kirsh On being situated. There were several other exciting papers presented during the day as well as a poster
session in the afternoon.

The invited talk by Peter Gärdenfors on "Concepts, cognition and context" was also a really exciting talk. He talked about some the concepts from his book "The geometry of thought". Really interesting stuff.

Definitely a nice conference. There were many definitions of context and some splitting hairs over what context really is. There doesn't seem to be a consensus about this. However, there many good talks on various topics related to context such as the semantic web, ontologies, linguistics, cognition and other areas. Many of the talks were really interesting and it's nice to get some different perspectives.

Artificial artificial intelligence

2007-08-06T23:54:00.000-07:00

To follow up on my post on human computation, I should mention Amazons new Mechanical Turk. It's a sort of a broker of human computation tasks (HIT's, in their terminology).

The basic idea is that requesters define a HIT and people get paid to perform these task.

I wondering what the prices of HIT's will be. The minimum commission charge is $0.005 per HIT, which isn't a lot. However, solving these tasks might appeal to people in countries where the average salary is very low.

It's an interesting idea. I'm sure we will see some exciting applications of it.

The Long Road from Text to Meaning

2007-07-04T03:13:00.000-07:00

I stumbled upon this very interesting lecture with Adam Kilgarriff on google videos.

Key points from the talk:

Approaches to language study: Rationalist vs. Empiricist

Lemmatizers and Part-of-speech tagging

Word sense, use and meaning

Word sketching and thesaurus creation from corpora is discussed along with important problems such as representation and ambiguity.

Using google as a NLP tool. Very interesting perspective!

Abstract: Computers have given us a new way of thinking about language. Given a large sample of language, or corpus, and computational tools to process it, we can approach language as physicists approach forces and chemists approach chemicals. This approach is noteworthy for missing out what, from a language-user's point of view, is important about a piece of language: its meaning.

I shall present this empiricist approach to the study of language and show how, as we develop accurate tools for lemmatisation, part-of-speech tagging and parsing, we move from the raw input -- a character stream -- to an analysis of that stream in increasingly rich terms: words, lemmas, grammatical structures, Fillmore-style frames. Each step on the journey builds on a large corpus accurately analysed at the previous levels. A distributional thesaurus provides generalisations about lexical behaviour which can then feed into an analysis at the ‘frames' level. The talk will be illustrated with work done within the ‘Sketch Engine' tool.

For much NLP and linguistic theory, meaning is a given. Thus formal semantics assumes meanings for words, in order to address questions of how they combine, and WSD (word sense disambiguation) typically takes a set of meanings (as found in a dictionary) as a starting point and sets itself the challenge of identifying which meaning applies. But, since the birth of philosophy, meaning has been problematic. In our approach meaning is an eventual output of the research programme, not an input.

Links

Adam Kilgarriff is a research scientist working at the intersection of computational linguistics, corpus linguistics, and dictionary-making. Following a PhD on "Polysemy" from Sussex University, he has worked at Longman Dictionaries, Oxford University Press, and the University of Brighton, and is now Director of two companies, Lexicography MasterClass (http://www.lexmasterclass.com) and Lexical Computing Ltd (http://www.sketchengine.co.uk/) which provide software, training and consultancy in the research areas.

Sketch Engine (SkE, also known as Word Sketch Engine) is a Corpus Query System incorporating word sketches, grammatical relations, and a distributional thesaurus. A word sketch is a one-page, automatic, corpus-derived summary of a word’s grammatical and collocational behaviour. You can try it using a free trial account.

Google sets creates a list of similar items given a few items. For instance, the set {apple,banana,strawberry} will result in a larger set with different fruits.

Human computation

2007-06-10T03:57:00.001-07:00

Human computation is the concept of using humans to solve problems that computers suck at. This is the same sort of goal that artificial intelligence has; namely, solving problems that humans are good at but are difficult for computers.

Human computation might well be the next big paradigm of Artificial Intelligence, even though this sounds like a paradox. Efficient machine learning algorithms usually require supervised training to learn how to solve a given problem, but training can be a daunting task. In unsupervised learning, some sort of fitness or reward function is required. Writing a good fitness function can be really complex. For instance, it would definitely not be trivial writing a fitness function which determines if a picture contains pornographic material. Humans, on the other hand, have little trouble doing this. Karl Sims has suggested using humans as fitness functions in genetic algorithms, and applied the technique to evolving beautiful art.

I think that the potential effect of Human Computation in an AI context can be compared to the effect that web 2.0 has had on content on the web.

The difficult part is motivating people to collaborate in the training process.

Money for nothing and cycles for free

Human cycles are usually more expensive than computer cycles. That is, unless you get them for free. Luis von Ahn has found a clever way to get those cycles for free: By designing computer games where the players sort a specific kind of problems. The first batch of games he has designed deals with image classification. For instance the ESP Game is two player game where both players have to agree on a word for an image. The result is a set of classifications tags for the image.

The other games are Peekaboom and Phetch.

In this video Luis von Ahn explains the concept and gives some examples of "human computation" games he has designed.

I am especially excited about a not-yet-released game, Verbosity, which deals with the problem of creating a large corpus of common-sense knowledge. The MIT project ConceptNet has attempted to do this using web-collaboration. It's currently the best corpus around, but there is certainly room for improvement. Entering common-sense knowledge seems really boring, but this game might actually make the process fun enough to get people to collaborate.

Article about McCarthy's Ambiguous Operator in Ruby

2007-06-08T05:20:00.000-07:00

I just discovered an article about an implementation of McCarthy's amb operator in Ruby, written by Erid Kidd. What a gem, it's a beautiful construction.

It uses continuations to implement backtracking and provides a straight-forward way of representing constraint satisfaction problems in Ruby.

Find the details, implementation and article here: www.randomhacks.net.
It's also the subject of a Ruby Quiz. Here is an other implementation in scheme with a detailed description.

A short introduction to CHR

2007-05-29T04:37:00.001-07:00

Constraint Handling Rules (CHR) is a declarative language for solving constraint problems. It's mainly used in conjunction with Prolog, but implementations for Java and Haskell are also available. I am currently working on making a Ruby implementation (as a Ruby DSL of course).

What is interesting about CHR is that it can be used to express constraint problems in a concise manner. It has successfully been applied to a wide range of constraint problems such as planning and language processing.

The language is quite simple. It consists of three kinds of rules that modify a constraint store (a database of constraints). All the rule definitions have a similar syntax:
rule :- head, operator, body.
The head and the body is basically a list of constraints. A rule is used when the head of the rule is matched by existing constraints in the constraint store. The constraints specified in the body gets added to the constraint store.

Propagation rules

c1, ..., c ==> Guard | cn+1, ... , cm
Propagation rules create new rules in the constraint store. Thee rules in the body (cn+1 .. cm) are added to the constraint store given that the guard is true. The rules from the head (c1 ... cn) remains in the constraint store.

Simplification rules

c1, ..., cn <=> Guard | cn+1, ... , cm
Simplification rules, has purpose of simplifying constraints in a particular way.
Rules in head (c1 .. cn) are removed from constraint store and rules in the body (cn+1 ... cm) is added to the store, provided that the Guard is true.

Simpagation rules

c1, ..., ci \ ci+1, ..., cn <=> Guard | cn+1, ..., cm
Simpagation rules is a sort of combination of the two others. The head is separated by a backslash. The rules before the backslash (c1 .. ci) stays in constraint store, while the rules after (ci+1 .. cn) is removed. The rules in the body (cn+1 .. cm) is added, provided the guard is true.

Marvin Minsky interview

2007-05-13T13:20:00.000-07:00

I just stumbled upon an interview with AI pioneer Marvin Minsky. The interview is mostly about his new book The emotion machine, "a machine that can switch between all the different kinds of thinking". I definitely want to read this book.

It's clear that Marvin Minsky has some profoundly different views on what AI should be like. He complains that the field is focused on solving problems with brain models and statistic models, but hardly no-one is working on making systems that can reason by analogy, or in other terms, think like a human.

He also talks about a bit about scifi, and if you are into that you will love this quote from the interview: "General fiction is pretty much about ways that people get into problems and screw their lives up. Science fiction is about everything else." I really laughed when I read it (because there is so much truth to it).

Colorless green ideas sleep furiously: Fun with a Ruby ChomskyBot

2007-05-13T09:32:00.000-07:00

I recently fell over the concept of a Chomsky bot. A funny little thing which generates random paragraphs of text from a set sentence building blocks. It combines four kinds of phrases (introduction phrases, subject phrases, verb phrases and object phrases) into a sentence. The sentences this simple construction can create are amazing. They are syntactically correct and "hovers on the edge on understandability".

By the way, the title of this post "Colorless green ideas sleep furiously" is a syntactically correct but nonsensical sentence devised by Noam Chomsky. Noam Chomsky pioneered the field of generative grammars. The ChomskyBot implements a simple generative grammar.

The sentences generated by the bot are similar to the language of Noam Chomsky's works, and I guess the pun is intended.

Of course, I couldn't resist the temptation to write a Ruby version of the Chomsky bot:


class ChomskyBot 
  @@phrase_elems = [ "intro", "subject", "verb", "object" ] 

  def initialize(intro_file, subject_file, verb_file, object_file)
    @@phrase_elems.each do |e| 
      instance_eval("@#{e}s = []") 
      instance_eval("File.open(#{e}_file).each_line" + 
                    "{ |l| @#{e}s.push l.chop }")
    end
  end

  def generate_lines(n)
    lines = []
    n.times do
      @@phrase_elems.each do |e|
        eval("lines << @#{e}s.slice!(rand(@#{e}s.size-1)) << ' '")
      end
    end
   lines
  end

  def paragraph 
    generate_lines(5).join
  end
end

I tried to make it as simple as I could get away with. I shaved quite a few lines using eval, hope it doesn't hurt readability to much.

You'll need some phrase files to play with it. You can find those here:

Introduction phrases
Subject phrases
Verb phrases
Object sentences

You can try the original version of the ChomskyBot online. It's written in Perl (source) by Kevin McGovan. For more information, pay a visit to Chomsky bot inventor John Lawlers website.

Nagios as a test suite

2007-05-09T01:45:00.000-07:00

Nagios is designed for network monitoring, and this is reflected in the plugins and the configuration language (e.g. everything is centered around the concepts of hosts and services) However, the flexiblity of Nagios also means that it works nicely as a blackbox test suite. I used this approach to the development of an sms broker solution for a customer recently (a Tomcat based application with a MySQL backend). As an added benefit, the test suite now also works as monitoring of the production system.

Diverse applications
Many applications consists of different components and bits and parts in different languages. The complicates testing with a standard, language specific tool like jUnit. Nagios is a nice piece of glue that lets you write tests in whatever way you like.

It's so easy to write a plugin in any language you like.
Sometimes it's just easier to write that database consistency check in Ruby/Perl/PHP than in Java. You might even be able to find a plugin that suits your needs on NagiosExchange.

Continuous testing with different intervals.
Test suites like jUnit have the drawback that they are usually run manually, so the discovery of an introduced bug may creep up late, if you don't run your testsuite often enough. In Nagios on the other hand, tests can be scheduled on an individual level.

Notify you when a test fails
Notifications can be done in a variety of ways (email/sms/im), but it's probably most useful in the monitoring phase (e.g. production). However, there are usually cases you want to know upfront when some part of the code mysteriously fails.

Apple responds to critisism from Greenpeace

2007-05-03T01:56:00.000-07:00

Steve Jobs have written a response to the criticism about Apples environmental standards. It seems that they actually do better than Greenpeace thought they did. Well, that's positive :-)

According to Apple they do better than HP and Dell, and have some sensible plans for chemical reduction and recycling.

I'm glad that Apple finally put some focus this. We need focus on this. Consumers have a lot to say, but they don't always contextualize. When they do contextualize they have a tendency to do it on a limited information basis. For instance the Greenpeace campaign (which I fully support) apparently didn't have all the relevant information about Apple.

While the power of the consumer is great to create focus on an issue, in this case, I think what we need is legislation. Set some limits for what chemical levels are allowed and require computer manufacturers to have a recycling policy. I think we need a objective and trusted investigation entity to determine how the computer manufacturers are doing.

A solution would be to put a tax on chemicals in computers. That would certainly encourage computer manufacturers to reduce those chemicals.

Transmoglyphing textual logic expression into Latex math

2007-05-02T12:32:00.000-07:00

Recently I've been doing some exercises which included a lot of logic expressions. Writing those in Latex becomes really tedious after a while, so I got sidetracked and wrote a small ruby program :-) It transforms a textual logic expression to the Latex equivalent.

For instance, this is a textual of a common logic function (can you see which one?):
(x and not y) or (!x && y)

It translates into latex math:
$(x \wedge \neg y) \vee ( \neg x \wedge y)$

When rendered it looks like this:

Other things like implication, biiimplication and entailment are also supported. The syntax allows a certain degree of freedom in choice of textual logic operators.

The code:


#!/usr/bin/env ruby
# Encode text with logic expressions as a latex math expression

symbols = { 
 '\wedge' => [ 'and', '&&' ],
 '\vee' => [ 'or', '||' ],
 '\neg' => [ '^', '!', 'not' ],
 '\Leftrightarrow' => [ '<=>', '<->' ],
 '\Rightarrow' => [ '=>', '->' ],
 '\models' => [ ':-', ':=', 'entails' ]
}

match_exp = {}
symbols.keys.each { |k| symbols[k].each { |re| match_exp[re] = k } }  

# Sort string by their length so that longest regexps are matched first

class String
        def <=>(other)
                other.length <=> length
        end
end

loop do
 puts "Enter logic text:"
 text = $stdin.gets.chomp
 break if text == "quit"

 match_exp.keys.reverse.each { |k| text.gsub!(k, " #{match_exp[k]} ") }
 puts "Latex math expr: $#{text.chomp}$"
end

Generate and Test in Ruby

2007-05-01T11:30:00.000-07:00

The Generate and Test algorithm (GT) is without comparison the simplest and most inefficient way of solving constraints. Actually, it's not useful for anything but very, very small problems. But it is serves as a nice little illustrating of the concept of constraint solving. Just for fun I wrote a very small GT constraint solver in Ruby the other day, that I decided sharing.

Here is a small toy problem for it to solve and a demonstration of how it works:

gt = GT.new
 
gt.add_var("a", 0..4)
gt.add_var("b", 0..4)
gt.add_var("c", 0..4)
 
gt.add_constraint("a % 3 == 0")
gt.add_constraint("b + a < c")
gt.add_constraint("c-a > b")
gt.solve

Running this code will print:


Solutions:
{"a"=>0, "b"=>0, "c"=>1}
{"a"=>0, "b"=>0, "c"=>2}
{"a"=>0, "b"=>0, "c"=>3}
{"a"=>0, "b"=>0, "c"=>4}
{"a"=>0, "b"=>1, "c"=>2}
{"a"=>0, "b"=>1, "c"=>3}
{"a"=>0, "b"=>1, "c"=>4}
{"a"=>0, "b"=>2, "c"=>3}
{"a"=>0, "b"=>2, "c"=>4}
{"a"=>0, "b"=>3, "c"=>4}
{"a"=>3, "b"=>0, "c"=>4}

The implementation:


class GT
  def initialize
    @variables = Hash.new
    @constraints = Array.new
  end
  
  def add_var(varname, domain)
      @variables[varname] = domain
  end
  
  def add_constraint(constraint)
    constraint.freeze
    @constraints << constraint
  end
  
  def generate
    gen(@variables, Hash.new,nil)
  end
  
  def gen(variables, partial_assignment, solutions)
    solutions = Array.new if solutions.nil?

    if variables.empty?
      if test(partial_assignment)
        solutions << partial_assignment.clone
      end
      return nil # termination
    end

    # pick the first available variable:
    vars = variables.clone
    var_name = variables.keys.first
    domain = vars[var_name] 
    vars.delete(var_name)
    
    # Loop over each variable in domain
    domain.each do |value|
      partial_assignment[var_name] = value
      gen(vars, partial_assignment, solutions)
    end
    solutions
  end
    
  def test(assignment)
    @constraints.each do |constraint|
      c = String.new(constraint)
      assignment.each do |key,val|
        c.gsub!(key,val.to_s)
      end
      result = instance_eval(c)
      return false if result == false
    end
  end
  
  def solve
    puts "Solutions:"
    solutions = generate
    solutions.each do |s|
      pp s
    end

  end
end

It is not useful for solving anything interesting though. I tried to make it solve the the send more money puzzle. But this poor algorithm searches it self to death in vain. It took so long, that it was never allowed to terminate...


[ "s", "e", "n", "d", "m", "o", "r", "n", "y" ].each { |var| gt.add_var(var, 0..9) }

gt.add_constraint("m != 0")
gt.add_constraint("s != 0")
gt.add_constraint("m < 3")
gt.add_constraint("(1000*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e) == (10000*m + 1000*o + 100*n + 10*e + y)")  

gt.solve

Update:Also heck out amb

iWaste: Apples aren't green :-(

2007-04-25T07:55:00.000-07:00

I am the happy owner of a MacBook Pro, a nice computer with a really nice OS. Or, at least I used to be happy about it. I have had quite ambivalent feelings since I discovered that Apple is one of the biggest pigs when it comes to toxic chemicals in computers :-(

Then I heard that Apple is going to let the share holders vote about removing those toxics. Actually it seems that the board opposes doing it:

"Apple's board says it opposes the resolution, arguing that the company already has adequate environmental standards."

from computer world article

Yeah right! Your standards are about the lousiest in the industry! I hope that your sales drops if this doesn't change. Is the only way of being environmental about this to not buy Apple computers any more? If that is the case, I already bought my last mac. Doesn't Apple realize that this is going to drive their stock down?

Greenpeace is running a campaign where you write Steve and tell him that you are unhappy to. Consider doing it. Go to www.greenmyapple.org to check it out.

Update
Follow up: Apple has responded to criticism from Greenpeace

Sleipner is dead

2007-04-22T16:28:00.000-07:00

With a slight feeling of sadness, I updated the Sleipner website to reflect the fact that the project isn't actively being developed anymore. Neither me nor Jens has the time to do it and other more promising projects in the same category has surfaced since the dawn of Sleipner. But it was a fun project to work on back then :-)

My answer to ruby quiz 121

2007-04-22T06:28:00.000-07:00

My solution to Ruby quiz 121.

Given some morse code without breaks between letters (which can have ambiguous interpretations), it will generate the words that the morse code can generate.

It's implemented as a recursive depth-first search in Ruby. Branches are expanded dynamically in the first_letters function.


require 'pp'

class Morse
 @@alpha = {
  "a" => ".-",
  "b" => "-...",
  "c" => "-.-.",
  "d" => "-..",
  "e" => ".",
  "f" => "..-.",
  "g" => "--.",
  "h" => "....",
  "i" => "..",
  "j" => ".---",
  "k" => "-.-",
  "l" => ".-..",
  "m" => "--",
  "o" => "---",
  "p" => ".--.",
  "q" => "--.-",
  "r" => ".-.",
  "s" => "...",
  "t" => "-",
  "u" => "..-",
  "v" => "...-",
  "w" => ".--",
  "x" => "-..-",
  "y" => "-.--",
  "z" => "--.."
 }

 def initialize
  # turn around hash index to use morse chars index
  @rev = {}
  @@alpha.each { |k,v| @rev[v] = k.to_s }
 end

 # Returns all letters matching the morse str at this pos
 def first_letters(morse, pos)
  letters = []
  @rev.keys.each do |k|  
   letters << k unless morse[pos..-1].scan(/^#{k.gsub(".","\\.")}.*/).empty?
  end
  letters
 end

 # Returns an array of words that matches 'morse' string 
 # It's basically a recursive function implementing depth-first search 
 def morse2words(morse, pos = 0 , seen = "")
  solutions = []
  first_letters(morse, pos).each do |l|
   if morse.length == pos + l.length
    solutions << "#{seen}#{@rev[l]}"
   else
    result = morse2words(morse,(pos+l.length),"#{seen}#{@rev[l]}")
    solutions += result
   end
  end

  solutions
 end

 # Converts a word to a morse string, used for testing
 def word2morse(word)
  morse = ""
  word.each_byte { |b| morse << @@alpha[b.chr] }
  morse
 end
end


######################
# Test:

def test_word2morse
 m = Morse.new
 raise unless  m.word2morse("sofia") == "...---..-....-"  
end

def test_first_letters
 m = Morse.new
 raise unless m.first_letters(".", 0) == [ "." ];
 raise unless m.first_letters("--.--..--.-.", 0) == ["--", "-", "--.", "--.-"] 
end

def test_morse2words
 m = Morse.new
 sofia = "...---..-....-" 
 solutions = m.morse2words(sofia)
 pp solutions
 solutions.each do |s|
  if m.word2morse(s) != sofia 
   puts "bad solution: #{s}"
   puts "yields #{m.word2morse(s)} in morse"
   raise
  end
 end
end

test_word2morse
test_first_letters
test_morse2words

substr in Ruby

2007-04-22T04:20:00.001-07:00

Some times you want to extract the characters from a certain offset within a string. In Perl and PHP you have the substr function, e.g.


$str = "Hello world";
substr($str, 6);  # --> "world"

In Ruby, this is done using the slice method of the String class. However, slice works a little different; slice is really an alias to [], so:


str = "Hello world"
str.slice(6) # --> 119
str[6] # --> 119

This may come as a surprise if you are used to substr; this returns the value of the character and not the rest of the string. Instead, we can do the same using negative indices, since negative indices count from the end of the string:


str.slice(6..-1) # --> "world"
str[6..-1] # --> "world"

Social bookmarking

2006-02-02T12:46:00.000-08:00

I started bookmarking using http://del.icio.us recently. Awesome site!

It's displays several trades of an excellent web-application; It's simple, user driven and bloat-free.

What really made me realize how powerful http://del.icio.us is, was an excellent podcast from http://www.itconversions.com called "Ontology is overrated" by Clay Shirky.

An ontology is a categorization of things that exists. The categorization tends to take on a dominating perspective influenced by the authors of the ontology.

For instance, the books in a library is sorted by author rather than by color. So if you're looking to find a specific red book in a library (and you don't know the author), you're out of luck. That's not a supported way of thinking :-(

Of course, computers and networks and especially the web is excellent for cross-referencing things. So there's no reason at all why you shouldn't be able to do this. It's just that it didn't occur to the people designing the system that you would wan't to do strange stuff like that.

http://del.icio.us is sort of a dynamic ontology realized by having users share bookmarks and apply tags (keywords) to those bookmarks. And yes, this is categorizing, but the users define their own categories. Categories form where different peoples bookmarks intersect. These are also intersections of peoples interests and by copying other peoples bookmarks you're exercising and forming social relations.

Del.icio.us builds the ontology buttom-up instead of top-down.

One of the interesting things Clay Shirky talks about is how ontologies tend to degenerate over time. This is bound to happen because the world of existing things on which the ontology reflects, changes. Categories are collapsed and information made up by their difference is inherently lost. Del.icio.us doesn't collapse categories, instead new categories becomes popular.

Instead of following the traditional model of trying to force users to use and adopt an ontology (like yahoo groups and the library does), del.icio.us is an adaptive and more useful ontology.

Links
Found an interesting article on social bookmarking tools.

Simulating polymorphism in PHP

2005-10-09T12:43:00.001-07:00

Today, I was tearing hairs out of my head to find out how to do polymorphism as described by the Liskov substitution principle in PHP (version 4).

The problem I was faced with was the following: I have an object of supertype and I wish to use it as an object of a subtype. Apparently, this is not readily possible in PHP.

I found my answer in a comment to the php manual, credit to Simon Li. It's quite a hack.

What happens is that the object is serialized, it's transformed into a string like this:
string(32) "O:6:"answer":1:{s:6:"answer";i:42;}"
The class name, the third element, is replaced with the class name desired. And finally, the modified string is transformed into a real object again.

I generalized the code from the comment and ended up with following:


// hack to simulate polymorphism in php
// you're not gonna like it
class castable {
  function cast_to($name) {
    $tmp = explode(":",serialize($this));
    $tmp[1] = strlen($name);
    $tmp[2] = "\"$name\"";
    $this = unserialize(implode(":",$tmp));
  }
}

class answer extends castable {
  var $answer = 42;
}

class question extends answer {
  function tell_me_the_answer () {
    echo "The answer is: ";
  }
}

$deepthought = new answer();
$deepthought->cast_to("question");
$deepthought->tell_me_the_answer();

echo $deepthought->answer . "\n";

This outputs:


The answer is 42

Object filesystems

2005-09-30T12:48:00.000-07:00

I just stumbled upon RailsFS. Nice.

RailsFS is a filesystem that maps the ActiveRecord classes in an Rails app as a Linux filesystem. It's written in my new favourite language Ruby and uses FUSE and a Ruby binding for FUSE. It's almost no code, impressive.

Actually, I wrote a very similar filesystem JCFS (Java Class FileSystem) about a year ago also using fuse and some very ugly JNI hacking. JCFS lets you mount Java classes and access class variables and run class methods.

Never really got around to writing a paper or even making the code remotely readable. But hey, you can download it and play with yourself if you're curious.

It release a readable and maybe useable revision of the code soon. Promise.

I will save a discussion about the deficiencies of FUSE (and the merits of Nimloth) for an other post someday...

ajax stuff

2005-08-20T12:40:00.000-07:00

I've been reading a bit about AJAX lately. Mostly because its the hot topic that everybody on the web is talking about, but also partly because it's pretty darn useful ;-)

I've decided to use it in an application I am developing at work.

This application is suppossed to replace an existing windows app which is partly developed using MFC and partly web-based using IE browser component embedded in the windows application and IE only html. Makes me shiver.

So I decided to develop it using Ruby on Rails and it's builtin support for AJAX.

So what is AJAX

AJAX is short for Asynchronous Javascript And XML. AJAX is a way of using JavaScript to develop web applications that are far more responsive than your average form.

A common limitation with web applications is the request-response model of http. With this model everytime you want some interaction with the server, you pretty much have to reload the entire page. This makes webapplications seem heavy and bothersome compared to native desktop applications.

Basically, what AJAX does is to let you interact with the server on a much more granular level. It utilizes JavaScript to let you asynchronously call server-side scripts and update content without reloading the page.

If you want to see AJAX in action take a look at google maps and script.aculo.us.

I can recommend the links below for learning more about AJAX:

Rasmus' 30 second AJAX Tutorial
Rasmus Lerdorf of PHP fame explains AJAX with a very simple code example, really nice...

Wikipedia has good coverage as usual

State of AJAX.
Originally from slashdot. Links AJAX with Service-Oriented Architectures (SOA). The article is overrated, but it has a lot of good links.