Preface: A Gentle Obsession

About a year ago, I picked up John McCarthy’s paper on Elephant 2000. I have to admit that I only understood about 10% of it. But I was so intrigued by the ideas that it sent me on a quest. I re-read it numerous times, slept with it under my pillow, and finally decided that I needed to read his other papers to get an insight into his thoughts. I began a considered effort with Seven McCarthy Papers in Seven Weeks. It ended up taking about three months, rather than seven 7 weeks. Again I came back to Elephant 2000. I began to understand more as other ideas and concepts sunk in, like ascribing beliefs and goals to machines. But to really explore the ideas, I really wanted to try to implement parts of Elephant in my own programming language. The problem was, having no formal training in computer science, (my background is Physics), I had never created a programming language before. The stars aligned and I found the Instaparse Clojure library. The result is Babar, a language designed to explore communication with machines via Speech Acts.

What are the Speech Acts?

When I say say “Pass the salt.”, the meaning behind the utterance is that I would like someone to reach out and move the salt shaker to me. I am requesting an action be performed. It doesn’t really matter if the utterance is in English, French, or Spanish. The intention is the same. Furthermore, if you accept my request to pass the salt. It creates a commitment on your part to actually perform the action. There are two types of speech acts that Babar is concerned with. The first is called an Illocutionary Act. Some of the english verbs denoting these acts are “assert”, “command”, “request”, and “query”. The second is a Perlocutionary Act. These are acts that are concerned with the effects of hearing them on future actions. Some of english verbs denoting these acts are “convince”, “persuade”, and “warn”.

Hello Babar

Babar is an experimental language that uses these Speech Acts to communicate. It also combines one of the other ideas of McCarthy, that is of beliefs and goals. The ultimate aim in the language is discover ways of thinking about computers and communicating with them based on the way that we communicate with each other. The state of a computer at any given point in time can be very complex and hard to understand. If we ascribe this state to be a “belief”, it becomes easier to understand and thus easier to program. The Babar REPL has internal commitments and internal beliefs. The goal of the Babar REPL is to keep all of its commitments. Speech acts are used to “convince” Babar of beliefs and to make “requests” that form commitments. The Babar REPL continually checks to see if it needs to fulfill a commitments. It fulfills them based on its beliefs. As an optional configuration, the REPL will speak aloud its beliefs as the become true – or as it “holds” the belief.

Syntax and Basics

The language uses basic Clojure datatypes and makes the parens optional in most cases to make the expressions look more like syntactically sugared speech acts.

1     ;=> 1
2.3   ;=> 2.3
-3.4  ;=> 3.4
"cat" ;=> cat
:bird ;=> bird
true  ;=> true
{:cat :meow :dog :bark} ;=> {:cat :meow :dog :bark}
[1 2 true :bird] ;=> [1 2 true bird]
atom 1 ;=> #

(def dog 16)
dog ;=> 16
def cat 18
cat ;=> 18

Vectors are a bit interesting in the respect that you don’t need to input the square brackets. If you just put in space delimited items, it will automatically construct a vector for you.

1 2 3 4 ;=> [1 2 3 4]

You can create anonymous functions with the fn [x] syntax from clojure. And call them with surrounding parens. You can call regular functions by the () notation or the shorthand :.

fn [x] + x 1 ;=> fn
(fn [x] + x 1) ;=> fn
((fn [x] + x 1) 3) ;=> 4
((fn [x y z] + x y z) 1 2 3) ;=> 6
((fn [] [4 5 6])) ;=> [4 5 6]

defn dog [] "woof"
dog: ;=> "woof"

To see the complete documentation – please visit the Github repo.

Show Me Babar Speech Acts

Now that we have the basics. Let’s look at example of running a program with speech acts.
This one speaks its beliefs and has assertions, a request, and queries.

speak-config true.
assert sunny false.
convince #nice-day "It is a nice day." fn [] = sunny true.
request *open-window when #nice-day fn [] println "Opened the window".
query request-is-done *open-window?
assert sunny true.
query request-is-done *open-window?

Here is another one that shows using a request until a belief is held.

speak-config true.

assert counter atom 1.
convince #done "I am done counting" fn [] > @counter 3.
request *count-up until #done fn [] swap! counter inc.
sleep 25.
query request-value *count-up?

Here the REPL asks you a question if you give it an undeclared var

speak-config true.
ask-config true.

request *task1 fn [] + 10 x.
query request-is-done *task1?
assert x 3.
sleep 10.
query request-is-done *task1?
query request-value *task1?

Autonomous AR Drone Flight with Babar REPL

Since the language is aimed at communincating with machines. It is only natural that I use it to talk to the AR Drone.
Here is a program that has the drone take off, get to a cruising altitude, and land – all using speech acts (and the clj-drone library).

speak-config true.

import "clj-drone.core".
import "clj-drone.navdata".

assert get-navdata [key] get @nav-data key.
assert navdata-equal [key val] = (get-navdata key) val.
assert navdata-gt [key val] > (get-navdata key) val.
assert init-drone [] (drone-initialize).
assert init-nav [] (drone-init-navdata).

convince #landed "I am on the ground" fn [] (navdata-equal :control-state :landed).
convince #flying "I am flying" fn [] or (navdata-equal :control-state :flying)
                                        (navdata-equal :control-state :hovering).
convince #high-enough "I am high enough" fn [] (navdata-gt :altitude 1.5).

request *take-off when #landed fn [] (drone :take-off).
request *cruising-alt when #flying until #high-enough fn [] (drone :up 0.1).
request *land when #high-enough fn [] (drone :land).

convince #done "Whee! I am done." fn [] and (navdata-equal :control-state :landed)
                                            query request-is-done *land.
request *end-navstream when #done fn [] (end-navstream).

Conclusion and Thanks

I can honestly say, that this has been one of the most enjoyable programming quests. I encourage you all to look at McCarthy’s papers, Clojure, Instaparse, and of course, hacking robots. A special thanks to all the Cincy folks at Neo who have supported me through my gentle obsessions and have let me have the freedom to follow my curiosity.

Starting with a Single Word

Let’s start with the simplest example:  a number.  When we start up our REPL in our brand new language, we want to be able to enter an integer, and have evaluate as an integer.

MyCoolLang> 1
1

Using the instaparse library, we define a number to be a regex matching an integer.

(ns coollang.parser
  (:require [instaparse.core :as insta]))
 
(def parser
  (insta/parser
   "number = #'[0-9]+'"))
 
(parser "1") ;=>; [:number "1"]

We now have a parser tree node that is of a type number. Pretty nice so far, but more rainbows are coming. You can make elegant transformations on the parser tree, and does them in a bottom up fashion, so you can use it for evaluation as well. In our simple number example, we are applying the read-string function on the :number node to turn it into a int.

(def transform-options
  {:number read-string})
 
(defn parse [input]
  (->> (parser input) (insta/transform transform-options)))
 
(parse "1") ;=> 1

Adding on spaces and vectors

Let’s build on a bit more. When someone enters in a sequence of numbers separated by spaces, it will be defined as a vector.

MyCoolLang> 1 2 3 4
[1 2 3 4]

We need to add the notion of spaces, spaces with numbers, and vectors into our grammar, as well as the rules
for evaluating these new nodes. Notice that we use the <> notation to hide the definition in the parser tree. The + means one or more times. The * means 0 or more times, and the | means or.

(def parser
  (insta/parser
   "expr = number | vector
    vector = snumber+ number
    <snumber> = (number space)*
    <space> = <#'[ ]+'>
    number = #'[0-9]+'"))
 
(parser "1 2 3 4") ;=> [:expr [:vector [:number "1"] [:number "2"] [:number "3"] [:number "4"]]]
 
(def transform-options
  {:number read-string
   :vector (comp vec list)
   :expr identity})
 
(defn parse [input]
  (->> (parser input) (insta/transform transform-options)))
 
(parse "1 2 3 4") ;=> [1 2 3 4]

Adding in operations

Pretty cool. We have numbers and vectors. Let’s see if we can do something fun like do some simple math on these vectors or numbers. We want it so when we type in + and some numbers, it adds them up.

MyCoolLang> + 1 2 3 4
10

Of course we need to further expand our grammar and rules.

(def parser
  (insta/parser
   "expr = number | vector | operation
    operation = operator space+ vector
    operator = '+' | '-' | '*' | '/'
    vector = snumber+ number
    <snumber> = (number space)*
    <space> = <#'[ ]+'>
    number = #'[0-9]+'"))
 
(parser "+ 1 2 3 4") ;=> [:expr
 ;                        [:operation
 ;                         [:operator "+"]
 ;                           [:vector [:number "1"] [:number "2"] [:number "3"] [:number "4"]]]
 
(defn choose-operator [op]
  (case op
    "+" +
    "-" -
    "*" *
    "/" /))
 
(def transform-options
  {:number read-string
   :vector (comp vec list)
   :operator choose-operator
   :operation apply
   :expr identity})
 
(defn parse [input]
  (->> (parser input) (insta/transform transform-options)))
 
(parse "+ 1 2 3 4") ;=> 10

Add a REPL

All we need now is a cool REPL to start working in:
We just need a main function to call our REPL, (Read – Evaluate – Print – Loop), and we are all set.

(ns coollang.repl
  (:require [coollang.parser :as parser]))
 
(defn repl []
  (do
    (print "MyCoolLang> ")
    (flush))
  (let [input (read-line)]
    (println (parser/parse input))
    (recur)))
 
(defn -main [& args]
  (println "Hello MyCoolLang!")
  (println "===============")
  (flush)
  (repl))

Closing and Inspiration

I have enjoyed playing around and learning about creating programming languages with Clojure and instaparse.
It truly is a beautiful library. If you need any more inspiration to start creating your own programming language, may I recommend:

• Growing a Program Language by Guy Steele - A classic and amazing talk about designing programming languages.
• BODOL – A language experiment using Clojure and Instaparse

Now go forth and create!

I want a coworking space to exist.

Coworking has changed my life. About three years ago, I became independent and starting doing development work out of my house. I found myself feeling increasingly lonely and isolated, working alone at my kitchen table day after day. I heard of a coworking space close to downtown called Cincy CoWorks, started by the visionaries Gerard Sychay and Bill Barnett. I joined and started going down there to work a few days a week. It was wonderful. Work became fun again. They day was peppered with serendipitous encounters and conversations the sparked my imagination and curiosity. I got involved in the Ruby community, usergroups, and eventually became part of the EdgeCase (and now Neo) company that makes me happy every day. In fact, the people that I met coworking are still an important part of my life today. So when I heard that Cincy Coworks suspended operations, I was a bit sad. I was sad that there was no longer an environment where the coworking magic could live. I had a small thought germinate in the back of my head then, that I would like to open a coworking space one day.

Someone told me it could not be done.

Sometimes there are clear catalysts in life. For me, it was someone telling me that a successful coworking space in Cincinnati could not be done. They may be right. I don’t know. But I do know, that the moment I heard that, something changed. I have this little part of me that can’t stand it when someone tells me I can’t do something. In fact, it is most likely one of the reasons that went into software development in the first place. That little part of me went a grabbed that small thought about starting a coworking place and dragged it out to the front where I couldn’t ignore it any more and said – DO IT.

A Lean Experiment

Serendipity happens. I had just finished reading Eric Ries’s book, The Lean Startup. It is a great book and highly recommend it. The main idea is using scientific methods for businesses. It got me thinking about what a coworking MVP, (minimun viable product), would be. I started looking around at spaces in Loveland just for fun, and stumbled into to one that would be perfect. I discovered The Loveland Art Studios on Main, a old school building turned into mostly art studios, but also housed a gym, spinning center, and training field for kids. The rent was very reasonable, had a 6 month lease, and already had wifi throughout the building. It was too perfect to pass up. I defined a hypothesis and experiment on the spot.

Hypothesis: There are enough people in the North and East part of Cincinnati interested to support a self-sustaining coworking space.
Experiment: Open a small coworking space for 6 months
Metrics: Monthly income – Monthly expenses

If at the end of the 6 months, the hypothesis is proven incorrect, I will accept my outcome and close up shop. However, even if the experiment is not successful, I will be capturing metrics on this and other experiments to save as artifacts to share with others that come after me. Hopefully, it will make it better and easier for the next person to launch coworking spaces. If you are interested in monthly updates on my metrics and experiments, ping me, and I will happily add you to my monthly distribution list.

Doing something you believe in

I don’t think this part needs much explaining. Doing something you believe in is worthwhile just in itself. Enough said.

Getting involved in the community is magic

Starting up a coworking space is all about building community. The very act of building something together creates magic. I am so thankful for all the people that have pitched in a helped me with their advice, encouragement, and assistance so far. Shout outs to Bill Barnett, Gerard Sychay, Paul Heinrich, Jacki Keys, Elizabeth Naramore, Chris Moore, Rob Biederhorn, Mason Stewart, and others. You all rock. really.

An Excuse for a Biscuit Tasting

One of the fun perks of running a coworks is you get to have Open Houses and other excuses to eat biscuits. When I say “biscuits”, I mean biscuits in the British form, that translates into American as “delicious cookies”. So if you are in Cincinnati, sign up for the Open House of Locolo. Where you can not only see the space and meet awesome people, but also rate various cookies on important factors such as dunkablility and crunchiness.

Thanks & Toodles for now,

Carin

Ever since I found out that you could program and control your drone over UDP, I couldn’t wait to try it out in Clojure.  I had dreams of controlling it with my Emacs REPL.  That dream came true and it has been a true joy to fly in a function language. This blog post shows some of the features that the clj-drone project has so far.  There is still a bit of work to go to make it complete.  But, I wanted to share and hopefully encourage others to start playing with it too.

The Simple Take-off and Landing

(ns clj-drone.example.simple
  (:require [clj-drone.core :refer :all]))
 
(drone-initialize)
;Use ip and port for non-standard drone ip/port
;(initialize ip port)
(drone :take-off)
(Thread/sleep 10000)
(drone :land)

Here is a video of executing the entire program in nrepl/ emacs

Controlling the Drone with Emacs/ Clojure REPL

Running the program all at once to control the drone is fun. But, I prefer to have more control over it in flight. I find being able to execute commands with keystrokes in emacs, the best way to do it. Here is a short video demonstrating control via the REPL. (Note: I am just doing simple take off / up and landings because of the constraints of flying indoors in my kitchen. There are many more moves you can do if you have more space.)

(ns clj-drone.example.moves
  (:require [clj-drone.core :refer :all]))
 
(drone-initialize)
;Use ip and port for non-standard drone ip/port
;(initialize ip port)
(drone-do-for 4 :take-off)
(drone-do-for 2 :up 0.3)
(drone-do-for 3.75 :fly 0.2 0 0 0.5) ; sprial
(drone :hover)
(drone :land)

Looking at the Navigation Data

You can also hook into the navigation feed. There are many drone states and properties to look at. There is a list of all the ones currently available on the github project site. There are also many more, including targeting information, that have yet to be added. There is a logging function that will pair down the navigation properties that you are interested in. The navigation data map as an atom, so it can be de-referenced anywhere in your program. Here is a short video of what the navigation logging data looks like when it is turned on.

(ns clj-drone.example.nav-test
  (:require [clj-drone.core :refer :all]
            [clj-drone.navdata :refer :all]))
 
;; logging is configured to go to the logs/drone.log file
 
(set-log-data [:seq-num :flying :battery-percent :control-state :roll :pitch :yaw
                :velocity-x :velocity-y :velocity-z])
(drone-initialize)
(drone-init-navdata)
(drone :take-off)
(drone :land)
(end-navstream)

Auto-piloting with goals and beliefs

Inspired by reading John McCarthy’s paper on Ascribing Mental Qualities to Machines, the drone can also auto-pilot itself based on goals and beliefs about its streaming navigation data. You define belief-actions and then goals. Finally, you set a vector of the current goals for the drone to process. You can see an example here of the AR drone having three goals: Take off, Get to a cruising altitude, and then land. It does it solely by inspecting and acting on the streaming navigation data.
Code for the program is here: https://github.com/gigasquid/clj-drone/blob/master/examples/nav_goals.clj

Go Fly!

I have had a lot of fun so far working on this project. I hope that you get a chance to play with it too. The project is still very young, so stay tuned for updates and, of course, pull requests are always welcome :)

To be continued….

Developers Who Enjoy Clojure Also Enjoy:
(In no particular order)

• Go (adorable mascot)
• OCaml
• Factor
• Haskell
• Scala
• Julia
• MetaII
• caerbannog
• J
• Boo (.Net)
• JavaScript / Bash

and of course MORE Clojure

• ClojureScript
• core.logic
• Overtone
• Quil

This holiday edition blog post covers two McCarthy papers instead of just one.  We will be talking about Free Will – Even for Robots and the companion paper Simple Deterministic Free Will.

In which we deftly sidestep the philosophers

We know that computers and programs are completely deterministic.  A philosophical question is whether we, as humans are ruled by determinism, (although complex it may be), or not.  If we take the decision that humans are deterministic, then we can argue that either there is no free will – or that free will is “compatible” with determinism.  Philosophers, of course, could discuss such questions interminably, trying to get a theory to fit for all people and all occasions.  Thankfully, McCarthy takes a very admirable and practical view on free will.  Let’s try out something simple for a computer program and see how it works.  He explores a philosophy ”Compatibilist’s” view, which regards a person to have free will if his actions are decided by an internal process, even if this process itself is deterministic.  But by exploring this view with computer programs, he makes clear:

… I don’t need to take a position on determinism itself.

 

Simple Deterministic Free Will

So what would Free Will look like for a machine. How do we go about defining it? McCarthy proposes the idea of Simple Deterministic Free Will. The main idea is that the mechanism of free will is broken up into two parts. The first part looks at the possible actions and the consequences of those actions, and the second part decides which of those actions are preferable and does them. He gives the example of a chess program:

People and chess programs carry thinking about choice beyond the first level. Thus “If I make this move, my opponent (or nature regarded as an opponent) will have the following choices, each of which will give me further choices.” Examining such trees of possibilities is an aspect of free will in the world, but the simplest form of free will in a deterministic world does not involve branching more than once.

So perhaps we could find an example that is simpler than chess to work with …

…it would be interesting to design the simplest possible system exhibiting deterministic free will. A program for tic-tac-toe is simpler than a chess program, but the usual program does consider choices.

Simple Deterministic Free Will Tic Tac Toe

So to explore McCarthy’s idea of Simple Deterministic Free Will, I decided to try to construct a game of Tic Tac Toe with SDFW principles. Coincidentally, my six year old daughter, just learned how to play Tic Tac Toe as well. I wanted to construct a program that would “reason” about the game as would a child. Even though the game of Tic Tac Toe is simple enough to have all the possibility trees of moves completely solved, this is not how a my daughter approaches the game. Each time it is her move, she only looks one move ahead to see if she can win three in a row, or if she needs to block her opponent from winning the next move.

My Tic Tac Toe Program has Beliefs

It has three beliefs to be precise. It believes that no one is going to win, or it is going to win, or its opponent is going to win.

(def beliefs
  { :win "I am going to win."
    :lose "My opponent is going to win."
    :noone "No one is going to win."})

McCarthy thinks that ascribing programs beliefs can be useful. One of the reasons is that it helps us as humans, reason and debug our programs. I definitely saw the value of this when I was trying to debug my tic tac toe game. After it failed to block my winning move, I could see what its false belief was – ah – it thought that “No one is going to win”. I wrote another failing unit test to fix its bad belief.

My Tic Tac Toe Program Looks to See What Its Possible Actions and Preferences Are

It looks at the board and computes all its possible next moves. Then it computes all the possible next moves of its opponent. It looks at the consequences of these moves by assigning a belief from one of its three beliefs. Next, it ranks the moves according to the preference of its beliefs.

(def belief-action-preferences
  { (beliefs :win) 1
    (beliefs :lose) 2
    (beliefs :noone) 3})

It then chooses the move to take that has the highest rank. If it believes that no-one is going to win, I opted to have it choose a random move from the list of possible choices. But this randomness is completely arbitrary on my part and not necessary to SDFW at all.

Why ClojureScript is Awesome

I coded the core tic-tac-toe program in Clojure, but then I thought that having a web page UI would be nice for my daughter to play with. So, I just took the game logic and moved it to ClojureScript. Let me say that again slower… I used the same code on the server on the browser. Awesome. Using the lein-cljsbuild crossover support, I was able to simply configure my UI ClojureScript code to access my regular clojure game engine. Very cool. I was also very pleased to work with the https://github.com/levand/domina DOM manipulation library for ClojureScript.

End Result

It was a fun project that let me play with ClojureScript, explore McCarthy’s free will for robots, have some very interesting conversations about free will with my co-wokers and code and coffee friends, and make a game for my daughter to play and enjoy. If you are interested in checking out the program for yourself – http://gigasquid.github.com/sdfw-tic-tac-toe/. The last belief is displayed at the bottom. I have only tried it on Chrome, so beware. Finally, if you find any false beliefs, feel free to submit a pull request to https://github.com/gigasquid/sdfw-tic-tac-toe.

P.S. If you are wondering, I drew the awesome graphics all by myself.

Fist let’s look at the kind of AI that McCarthy is describing in paper. He talks of a program that can use common sense knowledge about the world around it and have this knowledge structured well enough that it can be reasoned about mathematically. In fact, he describes four levels of logic:

1. The computer program has its “beliefs” completely defined by its internal state. If you are confused by the term “beliefs”, it refers to ascribing mental qualities to machines. In his famous example, a thermostat has three beliefs: the room is too hot, the room is too cold, and the room is just right.
2. The programs express their beliefs in sentences in machine memory. However, they do not use ordinary logic. They use other methods like rules and procedures.
3. In addition to expresses their beliefs in sentences, they also use first order logic and logical deduction to reach their conclusions.
4. The fourth level is still a goal today. It is to have the program represent general facts about the world as logical sentences. Furthermore, to have a database of these commonsense facts that programs can share.

Let’s step back now for a moment, to a excerpt from the very beginning of the paper:

One path to human-level AI uses mathematical logic to formalize common-sense knowledge in such a way that common-sense problems can be solved by logical reasoning. This methodology requires understanding the common-sense world well enough to formalize facts about it and ways of achieving goals in it. Basing AI on understanding the common-sense world is different from basing it on understanding human psychology or neurophysiology.

This approach to AI is just one approach. It is commonly referred to as a “top down” approach. In the early years of AI it was the dominant way of thinking about things. Looking back at the history of AI, the golden years were full of optimism, (and funding), that this was the path to achieving fully intelligent machines. Disenchantment with unfulfilled promises, led to the first AI winter. There was a rise of expert systems later on that limited their scope to small domains and avoided the common sense problem, but eventually ended in a second AI winter and ushered in our current world. This basic approach is an opposite ground-up view of AI. It uses neural networks and statistics from a physical inspiration. Some of this inspiration is from human neurophysiology, some of it is from insect and animal world, but simplicity behavior of a “body” is emphasized. With the advances in hardware and computing power today, the innovations and accomplishments have been breath taking.

A good example of the two approaches can be seen in my Roomba. A top down approach, would require my Roomba to have a complete room model in its program. It would have to understand what my couch was, where the doors where and have logically reasoning to direct it to which areas to clean and when to stop cleaning and recharge itself. The creators of the Roomba were from the opposite camp of thinking. They took the simpler behavior approach of having the Roomba just take a random walk in the room and turn around when it ran into an obstacle. It took a bit longer to get the room clean in such a random fashion, but not having to deal with the overhead of a mental model was well worth the trade off.

Noam Chomsky recently argued that the pendulum has swung too far in favor of this simplified behaviorist approach. Even in the light of Norvig’s response, I think Chomsky has a point. We would do well to search for gems of true intelligent systems in the historical landscape of the AI Winter. Some of the breakthroughs of current sheer computing power and new modeling techniques, might yield great fruits.

One of the comments by nagelonce, on the Chomsky article, puts this very well:

AI has a hole in the middle. There’s top-down AI, which focuses on abstractions and reductionism. There’s bottom-up AI, which focuses on reactive systems and the front end of visual processing. They have yet to meet in the middle. They are, however, much closer to doing so than they were twenty years ago.

If you are interested in checking out a top-down open source AI project, take a look at OpenCyc. After a brief look at it the other night, it suffers from the lack of love and documentation. But, I can also see the promise of McCarthy’s common sense knowledge and logic system, covered in a thin layer of snow.

I have realized that it generally takes me more than a week to read a paper, reflect on it, experiment, and finally blog about it. But, since I made up the rules of the project in the first place,  I am not going to dwell on the time frame and just move forward with the next paper.

When I picked the paper First Order Theories of Individual Concepts and Propositions, I thought to myself that it would be a rather narrow, more self contained paper than the first two broad papers that I read. However, the connections that it drew to current technologies caught me by surprise.

The main point of the paper is how to formalize language statements, including concepts, so that a computer can apply mathematical rules and logic to them. McCarthy had mentioned concepts and thoughts in his “Ascribing Mental Qualities” paper, where he says:

“..the deep structure” of a publicly expressible thought is a node is the public network.”

This immediately brought to my mind the Semantic Web.   In Semantic Web, data is structured in RDF statements as triples – <subject> <predicate> <object>.  The data contained in these triples are structured and described so that machines can derive context and meaning from it.  For example, instead of just putting  ”cat” as the subject.  In RDF you would use http://dbpedia.org/resource/Cat as the subject. Which, is pretty much dead on McCarthy’s expressible thought as a node in the public network.

McCarthy uses the following example to illustrate how to construct First Order statements.

Frege (1892) discussed the need to distinguish direct and indirect use of words. According to one interpretation of Frege’s ideas, the meaning of the phrase “Mike’s telephone number” in the sentence “Pat knows Mike’s telephone number” is the concept of Mike’s telephone number, whereas its meaning in the sentence “Pat dialed Mike’s telephone number” is the number itself. Thus if we also have Mary’s telephone number = Mike’s telephone number”, then Pat dialed Mary’s telephone number” follows, but “Pat knows Mary’s telephone number does not. phone number” is the number itself. Thus if we also have Mary’s telephone number = Mike’s telephone number”, then Pat dialed Mary’s telephone number” follows, but Pat knows Mary’s telephone number does not.

McCarthy express the statement “Pat knows Mike’s telephone number” as:

true Know(Pat; Telephone Mike)

He then uses more formalized statements to derive logic statements and reasoning from this example.

At this point, I was seeing more connections to the field of Semantic Web. Expressing data in RDF/ OWL gives computers exactly this type of logic and reasoning ability too.

So how would you go about expressing “Pat knows Mike’s telephone number” in Semantic Web data form?   This question is not a simple one,(at least for me),  because there are so many different ways that you can construct RDF.  The choices were a bit overwhelming.

One option might be to use RDF reification, in which you can make statements about statements.  Another option might be using OWL classes and properties.  There are some excellent answers when I posed the question on http://stackoverflow.com/questions/13114018/how-to-state-pat-knows-mikes-telephone-number-in-rdf-owl.

Indeed, it seems that we can express individual concepts and propositions in Semantic Web form quite well.  I had not realized that John McCarthy is the father of Sematic Web as well.

In closing, he speaks of AI Applications. Reasoning and predication are familiar applications that we use today. However he hits upon one that is quite interesting to me. That is “..determining that it does not know something or that someone else doesn’t.” This is not a common area to think about with computer programs. We are usually much more focused on what it does know and how to reason about it. But, if we are really to build intelligent, learning systems, we need to be able to identify what it does not know as well.  Perhaps then the AI can help us humans, who are pretty bad at that too.

I read Towards a Mathematical Science of Computation. It is quite a meaty paper and was certainly a lot to digest. Here are some highlights that I gleaned from it.

How can a Mathematical Science of Computation help in a practical way?

McCarthy points out that while it is hard to predict practical applications ahead of time. A couple of could be

• Provide a systematic way to create of programming language. Rather than just arguing and arbitrarily adding language features whilly nilly.
• “It should be possible to eliminate debugging. Debugging is the testing of a program on cases one hopes are typical, until it seems to work. This frequently is in vain.”

This last point of being able to eliminate debugging really stuck with me. Even with the best of TDD and test suites, we as developers still struggle with the testing of programs against what we hope is “typical”. Over the past years we have improved our techniques and made our programs more robust, but it would certainly be nice to be able to prove a program correct.

If fear that even if this was possible, it would not be enough. At least in my experience, a considerable amount of debugging happens at the human level:

• The translation of understanding of what the human product owner wants to what the software developer can understand.
• The human product owner’s understanding of what they want in the first place.

In my experience, we have just as much trouble (or even more) stating the problem for the program as we do in attempting to solve and prove that it works.

What we already know that can be applied to a Mathematical Science of Computation

• The existence of Turing’s Universal computers
• The existence of classes of unsolvable problems

Perhaps a sonic screwdriver will help?

McCarthy then goes on to add another tool to the Mathematical Science of computation toolbox. He shows that conditional expressions can be defined recursively. Then he expands this to relate to programs/computers that can be defined recursively.

Can a man make a computer program that is as intelligent as him?

Here is the real question. McCarthy has us consider the following problem of whether a program on a computers with unlimited memory will ever stop:

A procedure does the following

1. If the number is in a creative set then return -> yes.
   If a number is not in a creative set then return -> no
   or it may run indefinitely

2. There is no procedure while will always return -> yes when the answer is yes. and return -> no when the answer is no

It is a bit depressing that we can’t figure out which ones that are really no and which ones run forever. But don’t give up. We can just try to do the best we can. Emil Post discovered that whenever we try to do the best we can, one can always improve upon it. He showed that given any procedure, he could make a new procedure that solved all the previous cases plus some new ones. McCarthy pointed out that this process, even though it is really like trying to count the biggest ordinal number, can be mechanized. So really there is no reason why a machine could not continually improve its own program.

In summary, McCarthy’s own words are the best:

“In conclusion, let me re-assert that the question of whether there are limitations in principle of what problems man can make machines solve for him as compared to his own ability to solve problems, really is a technical question in recursive function theory.”