Friday, March 03, 2017

Diary: programming is hard!

I remember a post by James Thompson (can't find it - sorry) describing the joy of giving IQ tests to bright students. Their smug condescension as they breeze through the early items; their horror as they hit their cognitive limits and start to sweat: "Wait a mo, .., just can't seem to see it ... ."

In artificial intelligence textbooks it's standard to cover the coding of theorem provers for propositional-calculus. Hidden away in the advanced exercises is the suggestion to extend the program to cover the full predicate-calculus. Inevitably, this is flagged as hard.

Tell me about it. Today I got basic binary resolution to work. Great! I can do inference. And yet this is not the central mystery of a predicate-calculus resolution theorem prover (RTP).

The conceptual problems arise from the layers of abstraction around the proof procedure. At the risk of boring you even further, binary resolution is driven by the unification of complementary literals (basic formulae). These two literals occur in the two clauses offered to the resolution function (hence binary resolution).

A  problem addressed by an RTP comprises: assumptions  = the axioms, a set of clauses, plus the problem itself, a goal clause.

Here's my working example. First come the axiom clauses:
(defvar *c3*   (mk-fact-clause '(likes rod horvath)))
(defvar *c4*   (mk-fact-clause '(likes sally renner)))
(defvar *c5*   (mk-fact-clause '(likes sally rod)))
(defvar *c6*   (mk-fact-clause '(likes hardy renner)))
(defvar *c7*   (mk-fact-clause '(likes hardy rod)))
(defvar *c8*   (mk-fact-clause '(amusing hardy)))
(defvar *c9*   (mk-fact-clause '(likes horvath moties)))
(defvar *c10* (mk-rule-clause '(likes sally ?x) '((likes ?x moties)) ) )
(defvar *c11* (mk-rule-clause '(likes rod ?x) '((likes ?x renner) (likes ?x rod)) ) )
(defvar *c12* (mk-rule-clause '(likes ?x ?y) '((amusing ?y) (likes rod ?y)) ) )
(defvar *c13* (mk-fact-clause '(likes ?x ?x)))

(defvar *g1* (mk-goal-clause '((likes sally ?who)) ) )  ; this is the problem clause
You may notice a "Mote in God's Eye" theme here.

Despite the simplicity of these facts and rules, you'll struggle a bit to figure out the complete list of who, exactly, Sally Fowler likes.

I expect better from my program - once completed.


So a clause might look like this (which you will recognise as a Prolog-style Horn-clause):
'( (likes sally ?x) ← ((likes ?x ?y) (likes ?y moties)) )   ; a rule clause
which is already a bit complicated.

Then we have to set up structures for the knowledge-base (facts and rules), the goals which emerge from the resolution process, and the pointers and bindings which allow a reconstruction of proofs.


In telling you this, my intention is not to document the program, my point is more psychological.

You need to keep a very great deal of abstract structure in your head simultaneously if you hope to put this not-entirely-trivial program together. Plus lots of functions.

It's very g-loaded, much like doing mathematics.
"It's quite hard getting figures but ... it appears that the average IQ of students applying for PhD programmes at good universities in computer science is around 128.

"That sounds right to me. Most software development companies don't take people without good first degrees or a higher degree in a STEM subject - and that's just the pool we're talking about here."

Parenthetically, thank God for Lisp, a gift from the deity for clear, conceptual, exploratory thinking.


I read endless texts in the media from innumerate journalists about how unemployed or newly-redundant workers are going to retrain as software developers. Those writers couldn't hack it themselves and sadly, neither will most of those no-longer-required workers.
"Wait a mo, ..., just can't seem to see it ... ."
At an IQ threshold of 128, we're talking about 2.5% of a population normed at 100.

A caveat. It's intellectually hard writing machine learning programs or configuring recalcitrant artificial neural nets on novel problem-domains .. or programming RTPs. Yet for everyone doing those things, there are ten people paid to use graphical web design tools or load databases, or do a bit of scripting. Things which are not that hard.

Like many occupations, there has been mission-creep in the definition of software developer.


And why am I making such heavy weather of this wretched theorem-prover? This.

No comments:

Post a Comment

Comments are moderated. Keep it polite and no gratuitous links to your business website - we're not a billboard here.