Friday, February 24, 2017

Domestic servants: a modest proposal

I have fond memories of our Roomba, spinning mindlessly around our previous house, unable to empty itself and needing help to escape from under the bed. Didn't work in our current home - carpets too thick.

We're as far as ever from artificial general intelligence (AGI). But why try to solve a thousand problems of mental and physical agility when biology has already done the work for us over 400 million years?

"Wait!", I hear you say. Domestic servitude died out with the Edwardians. Besides, the idea of all those servants observing and judging your every move. It's so creepy. No privacy. It's like your home isn't your own.

But that was before CRISPR ...
"She paused. "Just out of curiosity, what's planned fo' the serfs along these lines?"

He relaxed. "Oh, much less. That was debated at the highest levels of authority, an' they decided to do very little beyond selectin' within the normal human range.

"Same sort of cleanup on things like hereditary diseases. Average height about 50 millimeters lower than ours. No IQs below 90, which'll bring the average up to 110. No improvements or increase in lifespan so they'll be closer to the original norm than the Race.

"Some selection within the personality spectrum: toward gentle, emotional, nonaggressive types. About what you'd expect."
If they like serving you, can it really be slavery?


More about the Draka.

Thursday, February 23, 2017

Liberals meet the Moties: high-K vs. high-r

My current after-dinner read to Clare is that wonderful old (1974) classic, "The Mote in God's Eye" by Larry Niven and Jerry Pournelle.

Amazon Link

Here's a brief plot summary (it's surely OK now for spoilers).
"An alien spaceship using a light sail to fly at speeds below the speed of light appears in the human system of New Caledonia. The ship has been traveling for at least 135 years.

The Viceroy ruling the New Caledonia system, the Emperor's appointed representative, determines that a mission of two ships will be sent to the alien system that sent out the pod. Both species are wary, protective, and secretive.

Communication is established; understanding, however, remains more distant. One of the warships is invaded by a lower alien species and must be destroyed. Three Midshipmen end up alone on the planet, uncovering the aliens' desperate secrets of uncontrollable population explosion and giving their lives to protect Empire secrets.

Three aliens are sent to accompany the remaining human ship and crew back to New Caledonia as ambassadors."
The Moties are an example of an r-selected species which, via their technological civilization, solve the high death-rate problem - at least until their numbers hit ultimate carrying capacity.

From Wikipedia:
"As the name implies, r-selected species are those that place an emphasis on a high growth rate, and, typically exploit less-crowded ecological niches, and produce many offspring, each of which has a relatively low probability of surviving to adulthood (i.e., high r, low K).

In unstable or unpredictable environments, r-selection predominates due to the ability to reproduce quickly. There is little advantage in adaptations that permit successful competition with other organisms, because the environment is likely to change again. Among the traits that are thought to characterize r-selection are high fecundity, small body size, early maturity onset, short generation time, and the ability to disperse offspring widely.

By contrast, K-selected species display traits associated with living at densities close to carrying capacity, and typically are strong competitors in such crowded niches, investing more heavily in fewer offspring, each of which has a relatively high probability of surviving to adulthood (i.e., low r, high K). ...

In stable or predictable environments, K-selection predominates as the ability to compete successfully for limited resources is crucial and populations of K-selected organisms typically are very constant in number and close to the maximum that the environment can bear (unlike r-selected populations, where population sizes can change much more rapidly).

Traits that are thought to be characteristic of K-selection include large body size, long life expectancy, and the production of fewer offspring, which often require extensive parental care until they mature. ... Organisms with K-selected traits include large organisms such as elephants, humans and whales, but also smaller, long-lived organisms such as Arctic terns. ...

The r/K dichotomy can be re-expressed as a continuous spectrum using the economic concept of discounted future returns, with r-selection corresponding to large discount rates and K-selection corresponding to small discount rates."

The novel revolves around the debate between liberals and conservatives as to how to deal with the Moties (who pretend to be high-K liberals). It's an eerie book to read, weirdly analogous to contemporary debates in the media. It's been suggested on a regular basis that it would make a stupendous film, but until Hollywood learns to love The Donald, I fear their immune system makes that prospect stillborn.


Advanced capitalist countries have been carrying out an interesting experiment with effective birth control over the last fifty years or so. A possible result has been a decline in fertility leading to projected population collapses: Japan is often mentioned as a trend-setter.

Birth control is a central theme in the novel too. The treatment is very game-theoretic: over their history, some Motie continents under strong political leadership did in fact practice population control. They were simply outbred and then conquered by their more numerous competitors.

Wednesday, February 22, 2017

Perhaps no-one understands Maxwell's equations

"Microsoft CEO Satya Nadella spoke at a public event in India on Monday ...

"The first time I put on a HoloLens was to see something Cleveland Clinic [a non-profit academic medical center] had built for medical innovation... As an electrical engineer who never understood Maxwell's equations, I thought if I had a HoloLens, I would have been a better electrical engineer. Overall I feel that augmented reality is perhaps the ultimate computer," he said.
From here.

Actually, the article was entitled, "Microsoft CEO says artificial intelligence is the 'ultimate breakthrough'", but I was struck by his confession of ignorance about the foundational theory of classical electromagnetism.

Maxwell's equations

This looks bad, of course. But let's cut the CEO some slack: Maxwell's equations are notoriously unintuitive, as I observed in this post.

You can use the equations, solving them for particular physical configurations. But what picture do they give of the nature of the field(s) themselves?

What are we to make of the fact that a stationary observer of a motionless charged ball sees a static spherical electric field E, while an observer moving past that same ball sees electric and magnetic fields (E' and B')?

The magnetic field is a relativistic effect.

The charge is at rest in frame F, so this observer notes a static electric field. An observer in another frame F′ moves with velocity v relative to F, and notices the charge to move with velocity −v with an altered electric field E due to length contraction and a magnetic field B due to the motion of the charge. (Wikipedia).

That's implicit in Maxwell's equations, but don't tell me it's obvious. For that, you need to write the equations in a manifestly covariant form, but they don't teach you that in undergraduate electrical engineering.


Oh, and he's surely right about augmented reality being the main deliverable from the current state of the art in artificial neural net technologies. The Holy Grail of AGI will be a product of mastering situated social cognition, a post for another day (but see here).

Tuesday, February 21, 2017

"From Eternity to Here" - Sean Carroll

Amazon Link

Just finished Sean Carroll's 2011 book, which - after an exhaustive exploration of all other options - locates the origin of 'the arrow of time' in the quantum-fluctuation emergence of super-low-entropy 'baby universes' from a preceding high-entropy de Sitter universe.

Yep, that would be the baby universe in which I'm sitting writing this post.

This may seem extravagant, to explain why eggs produce omelettes but not the reverse, but he refutes all the simpler explanations.

It presently seems unclear, however, whether a de Sitter universe could even make baby universes, absent a better theory of quantum gravity.

Carroll's latest thinking tends in a different direction, suggesting that framing the issue within the spacetime realm may itself be a mistake; the true nature of reality may be Hilbert space with Schrödinger equation dynamics. Spacetime, with its arrow of time, may be emergent.

Strange that the weirdest ideas of modern physics - the MWI, emergent spacetime - seem to be the most plausible.

This is a fine book, and an excellent introduction for the smart non-physicist to general relativity, quantum theory (QM/QFT) and cosmology.

Monday, February 20, 2017

The deep state *is* the state

Much excitement in the States (but also in Brexit Britain) about elements of the state apparatus actively working to undermine the policies of an 'insurgent' government.

The governments in question are of the right, not the extreme left, but the founders of Marxism were clear that a truly revolutionary government cannot just take over the 'controls' of a 'neutral' state apparatus. They will be thwarted at every turn.

This is, of course, true of all bureaucracies. Successful 'turnaround' CEOs bring their own posse of senior managers - and waste no time clearing out the old regime. If they don't, their mission is toast. The political right, in order to to secure their victory, will have to purge the state of their enemies and repopulate it with supporters in their own ideological image.

Marxists, however, are seldom called out on what they think should replace the bourgeois state. Lenin and Trotsky, following the model of the Paris Commune, thought that the mobilised masses, organised in soviets (councils), would constitute a non-bureaucratic socialist state - a social formation not separate from broader society.

Marx himself never wrote much about it.

Yet the state is neither a contingent formation nor just 'bodies of armed men' safeguarding existing property relations. The state has an enormous, and under-analysed, role in social-coordination.


Turn now to the economy. All Marxists agree that their post-capitalist economic model will replace private decision-making about the allocation of resources with 'consciously democratic', centrally-planned directives.

Given the complex and highly-technical nature of policy-making and implementation, both as regards the state and the putative planned-economy, this is not going to something managed by the masses through their councils. Nor is it going to be that old favourite, the mere 'administration of things, not of people'.

The PDF version is here

It's hard to resist the conclusion that - until the AIs take over (and where does that leave us?) - the post-capitalist state will continue to be large, bureaucratic and unresponsive. Much like the bourgeois state.

History tends to support this view.

I would guess that Marxists would not agree, but for people proposing a radical makeover of society's fundamentals, they seem remarkably coy about their proposed replacement model.

Such studied casualness wouldn't work in engineering.

Why does the far left get a free pass on something of such fundamental importance?

Sunday, February 19, 2017

People are boring - so what chance chatbots?

The BBC's Dave Lee writes:
"It's been nearly a year since Microsoft's Satya Nadella proclaimed "bots are the new apps".

"Yet despite the promise of a revolution in how we interact with services and companies online, progress has been utterly miserable - the vast majority of chatbots are gimmicky, pointless or just flat out broken. ...

The CNN news chatbot, for example, is worse at giving you the news than any of CNN’s other products. ...

"Google's AI-powered messaging app Allo, since being launched to much fanfare last year, has failed to make even a minor dent in a messaging app market dominated by Whatsapp and Facebook Messenger.

"And that's because there's no compelling reason to bother with Allo. None of its features - like asking it for directions - provide enough of a benefit beyond what you'd get from just tapping in your request the "old fashioned" way. Users have an incredibly short fuse for chatbots not working exactly as we expect."

We have a special name for those few people who we (mostly) don't find boring.


We don't much enjoy extended interactions with random folk. People who, nevertheless:
  • have been completely socialised into our culture for decades, 
  • come with detailed background knowledge of the world,
  • are endowed with common sense and full conversational abilities.
So why did the AI companies think we'd enjoy interacting with chatbots, which are cognitively impoverished in every conceivable way?

It's a good question and I'm not sure of the answer.
- Were they over-impressed by their mighty artificial neural nets? But they're only fantastic recognisers and classifiers, a far cry from artificial general intelligences (AGI).

- Did they think that we're all keen to have conversational, hands-free interaction with our pocket devices? In fact that's socially way too intrusive most of the time, plus we're talking to conversational muppets.

- Was there a belief that in some narrow, vertical and tightly-constrained domains there might be a niche for a conversational interface? There's almost certainly something to that - but we don't yet know what.
My own feeling is that the successful mass consumer chatbot can be nothing less than a truly effective virtual friend. To that end it will have to posses AGI and be malleable to your own personality and 'friend-preferences'.

We'll have starships before we have that; I haven't seen the first clue we're on that road.


All of the above presupposes peer-relationships, typically with kids or adults. Those conversations - most of the time! - exhibit an irreducible core of rational and relevant 'aboutness'.

So hard to replicate for an artefact.

But there are natural agents around without much cognitive competence: babies, small children and pets. The bond here is emotional .. and so is the interaction.

So if you're in the business of designing chatbots which could conceivably bond with your customers, you might want to take note .. .*


* In the old days, we called them 'dolls', and they came without batteries.

Saturday, February 18, 2017

Diary: my day with a Prolog interpreter in Lisp

The subject: implementing a Prolog interpreter in Common Lisp, using an excellent - if rather old-fashioned - textbook as my guide. I had copied-and-pasted the code across (it never quite works first time) and was debating this morning: finally get Peter Norvig's code to run, or strike out in my own direction?

There's a lot in Chapter 11 of "Paradigms of Artificial Intelligence programming" to be wary of:
  • For efficiency reasons he stores the clauses on clause-head-predicate property lists
  • He uses destructive operations such as nconc
  • The resolution inference step and depth-first control strategy are interwoven.
I'd prefer to keep the clause database as an explicit object to be transformed and analysed throughout the proof. I'd also like to modularise the 'which clauses to try to resolve next' strategy, trying different things such as unit preference, set-of-support, hyperresolution. And it would be good to extract a proof tree, not just the final question-answering bindings.

All these things demand a rewrite.

But I was glad I persevered, because Peter Norvig's code finally came good this afternoon and I was able to successfully run it on a serious logic puzzle - the Zebra problem.

Where it ran remarkably quickly - forty times faster than in Dr Norvig's textbook-writing days. I was reminded of AI programming back in the late 1980s, when everything was slow and hard.

I imagined him developing his code on some ancient VAX 11/780 (as I used to do).

A simple Prolog interpreter in Lisp

I happen to think that the code for 'prove' et al below is extremely opaque. You will search in vain for any clear modularisation into:

  • Resolution operation
  • Depth-first control strategy
  • Bindings and solution management.

For conceptual, pedagogical and tool-creation reasons, a rational reconstruction is necessary (which also recasts the code in a less 'destructive' style). When this is completed, I will post a link to the rewritten - and hopefully much clearer code - here.

; ---- Lisp code starts here ---
;;;  Prolog in Lisp:  February 14th 2017 - February 18th 2017
;;;  From Peter Norvig's book: Chapter 11
;;; "Paradigms of Artificial Intelligence Programming"
;;; Unification, Prolog, Resolution, inference control strategies
;;; Posted:
;;;  Reminder: (how to load and access files)
; (load  "C:\\Users\\HP Owner\\Google Drive\\Lisp\\Prog-Prolog\\Prolog-in-Lisp.lisp")

;;; --- Unification ---

(defconstant +fail+ nil "Indicates pat-match failure.")

(defconstant +no-bindings+ '((t . t))
"Indicates pat-match success but with no variables.")

(defun variable-p (x)    ; Symbol -> Bool
  "Is x a variable, a symbol beginning with '?'"
  (and (symbolp x) (equal (char (symbol-name x) 0) #\? )))

(defun get-binding (var bindings)
  "Find a (variable . value) pair in a binding list."
  (assoc var bindings))

(defun binding-val (binding)
  "Get the value part of a single binding."
  (cdr binding))

(defun lookup (var bindings)
  "Get the value part (for var) from a binding list."
  (binding-val (get-binding var bindings) ))

(defun extend-bindings (var val bindings)
  "Add a (var . value) pair to a binding list, remove (t . t)"
  (cons (cons var val) (if (equal bindings +no-bindings+) nil bindings)))

(defparameter *occurs-check* t "Should we do the occurs check?")

(defun unify (x y &optional (bindings +no-bindings+))   ; -> Bindings
  "See if x and y match with given bindings"
  (cond ((eq bindings +fail+) +fail+)
        ((eql x y) bindings)
        ((variable-p x) (unify-variable x y bindings))
        ((variable-p y) (unify-variable y x bindings))
        ((and (consp x) (consp y))
         (unify (rest x) (rest y)
                (unify (first x) (first y) bindings) ) )
        (t +fail+) ) )

(defun unify-variable (var x bindings)              ; -> Bindings
  "Unify var with x, using (and maybe extending) bindings"
  (cond ((get-binding var bindings)
             (unify (lookup var bindings) x bindings))
        ((and (variable-p x) (get-binding x bindings))
             (unify var (lookup x bindings) bindings))
        ((and *occurs-check* (occurs-check var x bindings))
        (t (extend-bindings var x bindings))))

(defun occurs-check (var x bindings)             ; -> Bool
  "Does var occur anywhere 'inside x'?"
  (cond ((eq var x) t)
        ((and (variable-p x) (get-binding x bindings))
         (occurs-check var (lookup x bindings) bindings))
        ((consp x) (or (occurs-check var (first x) bindings)
                       (occurs-check var (rest x) bindings)))
        (t nil)))

(defun unifier (x y )
  "Return something that unifies with both x and y (or +fail+)"
  (subst-bindings (unify x y) x ) )

(defun subst-bindings (bindings x)   ; Bindings x Term -> Term
  "Substitute the value of variables in bindings into x,
taking recursively bound variables into account"
  (cond ((eql bindings +fail+) +fail+ )
        ((eql bindings +no-bindings+) x)
        ((and (variable-p x) (get-binding x bindings))
              (subst-bindings bindings (lookup x bindings) ))
        ((atom x) x)
        ( t (cons (subst-bindings bindings (car x))
                        (subst-bindings bindings (cdr x )) ) ) ) )

;;; --- Now let's try unify on some examples ---
; (setf b '((?Z . ?X) (?Y . 4) (?X . 3)))
; (subst-bindings b '?y)           ; => 4
; (subst-bindings b '?z)           ; => 3
; (subst-bindings b '(f ?z ?y))    ; => (F 3 4)
; (unify '(?x ?y a) '(?y ?x ?x))   ; =>  ((?Y . A) (? X . ?Y))
; (unify '?x '(f ?x))    ; => NIL  (occurs check nil: ((?X F ?X)))
; (unify '(?x ?y) '((f ?y) (f ?x)) ; =>  NIL  (occurs check)
; (unify '(?x ?y ?z) '((?y ?z) (?x ?z) (?x ?y))) => NIL  (occurs check)
; (unify 'a 'a)   ; => ((T . T))
; Finally, the function unifier calls unify and substitutes
; the resulting binding list into one of the arguments.
; The choice of x is arbitrary; an equal result would come
; from substituting the binding list into y.

; Here are some examples of unifier:
;  (unifier '(?x  ?y a) '(?y ?x ?x))  ;  =>  (A A A)
;  (unifier '((?a * ?x ^ 2) + (?b * ?x) + ?c) '(?z + (4 * 5) + 3)) ; =>
;        ((?A * 5 ^ 2) + (4 * 5) + 3)

;;; ----------------- Prolog Interpreter -----------------
From Wikipedia: Clause (logic)

Every nonempty clause is logically equivalent to an implication of a head
from a body, where the head is an arbitrary literal of the clause and the
body is the conjunction of the negations of the other literals. That is,
if a truth assignment causes a clause to be true and none of the literals
of the body satisfy the clause, then the head must also be true.

This equivalence is commonly used in logic programming, where clauses are
usually written as an implication in this form. More generally, the head
may be a disjunction of literals. If b1,...,bm are the literals in the body
of a clause and h1,...,hn are those of its head, the clause is usually
written as follows:

h1,...,hn <-  b1,...,bm

If n=1 and m=0, the clause is called a (Prolog) fact.
If n=1 and m>0, the clause is called a (Prolog) rule.
If n=0 and m>0, the clause is called a (Prolog) query.
If n>1, the clause is no longer Horn.

;; --- Clauses are represented as (head . body) cons cells: example ---
;  ( (member ?item (?item . rest))) )                                         ; fact
;  ( (member ?item (?x . ?rest)) . ((member ?item ?rest)))       ; rule

(defun clause-head (clause) (first clause))     ; Clause -> Literal

(defun clause-body (clause) (rest clause))      ; Clause -> Literal-list

;; Clauses are stored on the predicate's plist

(defun get-clauses (pred) (get pred 'clauses)) ; symbol -> Clause-list

(defun predicate (literal) (first literal))    ; Literal -> Symbol (predicate)

(defvar *db-predicates* nil
  "A list of all predicates stored in the database")

(defmacro <- (&rest clause)
  "Add a clause to the database"
  `(add-clause ',clause))

; (macroexpand-1 '(<- (likes Kim Robin)))    ; =>
; (ADD-CLAUSE (QUOTE ((LIKES KIM ROBIN))))        ; ... which is correct.

(defun replace-?-vars (exp)
  "Replace any ? within exp with a var of the form ?123"
  (cond ((eq exp '?) (gensym "?"))
        ((atom exp) exp)
        (t (cons (replace-?-vars (first exp))
                 (replace-?-vars (rest exp))) ))  )

(defun add-clause (clause)
  "Add a clause to the data base, indexed by head's predicate"
  ;; The predicate must be a non-variable symbol.
  (let* ((clause1 (replace-?-vars clause))
         (pred (predicate (clause-head clause1))))
    (assert (and (symbolp pred) (not (variable-p pred))))
    (pushnew pred *db-predicates*)
    (setf (get pred 'clauses)
          (nconc (get-clauses pred) (list clause1))) pred) )

; (setf clause '((P ?x ?y) . ((Q ?x ?y))))
; (add-clause clause)                       ; => P
; *db-predicates*                            ; => (P)
; (get 'P 'clauses)                             ; (((P ?X ?Y) (Q ?X ?Y)))

(defun clear-db ()
  "Remove all clauses (for all predicates) from the database"
  (mapc #'clear-predicate *db-predicates*))

(defun clear-predicate (predicate)
  "Remove the clauses for a single predicate"
  (setf (get predicate 'clauses) nil) )

;;; So here is an example:
;;;  clause = '((P ?x ?y) . ((Q ?x ?y)))
;;;  goal = '(P a b)
;;; ----------------------------------------------------------------------------------
;;; and here is how 'prove' works:
;;; (get-clauses (predicate goal)) finds 'clause' = '((P ?x ?y) . ((Q ?x ?y)))
;;; 'clause' would then get variable-renamed -> new-clause
;;; Get binding from (unify goal (clause-head new-clause) bindings)
;;; Using that binding, try to prove clause body literals
;;; Return bindings (via prove-all)

(defvar *countr* 0)        ; count how many times 'prove' is called

(defun count-prove-calls ()
   (setf *countr* (1+ *countr*))
   (format t "~& Call to prove = ~a" *countr*) )

(defun prove (goal bindings)    ; Literal x Bindings -> Bindings
  "Return a 1ist of possible solutions to goal"
  (mapcan #'(lambda (clause)
              (let ((new-clause (rename-variables clause)))
                (prove-all (clause-body new-clause)
                           (unify goal (clause-head new-clause) bindings))))
          (get-clauses (predicate goal))))

(defun prove-all (goals bindings) ; Literal-list x Bindings -> Bindings
  "Return a list of solutions to the conjunction of goals"
  (cond ((eql bindings +fail+) +fail+)
        ((null goals) (list bindings))
        (t (mapcan #'(lambda (goal1-solution)
                       (prove-all (rest goals) goal1-solution))
                   (prove (first goals) bindings)))))

(defun rename-variables (x)       ; clause -> clause (with vars renamed)
  "Replace all variables in x with new ones"
  (sublis (mapcar #'(lambda (var) (cons var (gensym (string var))))
                  (variables-in x))

; (setf clause '((P ?X ?Y) (Q ?X ?Y)))
; (rename-variables clause)     ; => ((P #:?X932 #:?Y933) (Q #:?X932 #:?Y933))
; (setf clause1 '((F (G ?x (H ?y)) (J ?u ?v))))
; (rename-variables clause1)  ; => ((F (G #:?X872 (H #:?Y873)) (J #:?U874 #:?V875)))

; This version of ?- superseded by later definition below
; (defmacro ?- (&rest goals) `(prove-all ',goals +no-bindings+))

;;; --- Example ---
(add-clause '((likes Kim Robin)))
(add-clause '((likes Sandy Lee)))
(add-clause '((likes Sandy Kim)))
(add-clause '((likes Robin cats)))
(add-clause '((likes Sandy ?x) (likes ?x cats)))
(add-clause '((likes Kim ?x) (likes ?x Lee) (likes ?x Kim)))
(add-clause '((likes ?x ?x)))

(prove '(likes Sandy ?who) +no-bindings+)   ; =>

; (((?WHO . LEE))
;  ((?WHO . KIM))
;  ((#:?X846 . ROBIN)
;  (?WHO . #:?X846))
;  ((#:?X850 . CATS) (#:?X847 . CATS) (#:?X846 . SANDY) (?WHO . #:?X846))
;  ((#:?X855 . CATS) (#:?X846 . #:?X855) (?WHO . #:?X846))
;  ((?WHO . SANDY) (#:?X857 . SANDY)))

; --     and here with macros <-   and ?-     ---

(<- (likes Kim Robin))
(<- (likes Sandy Lee))
(<- (likes Sandy Kim))
(<- (likes Robin cats))
(<- (likes Sandy ?x) (1ikes ?x cats))
(<- (likes Kim ?x) (likes ?x Lee) (likes ?x Kim))
(<- (likes ?x ?x)

> (?- (likes Sandy ?who))

; (((?WHO . LEE))
;  ((?WHO . KIM ) )
;  ((?X2856 . ROBIN) (?WHO . ?X2856))
;  ((?X2860 . CATS) (?X2857 . CATS) (?X2856 . SANDY) (?WHO . ?X2856))
;  ((?X2865 . CATS) (?X2856 . ?X2865) (?WHO . ?X2856))
;  ((?WHO . SANDY) (?X2867 . SANDY)))


;;; --- TOP-LEVEL-PROVE ---

(defmacro ?- (&rest goals) `(top-level-prove ',(replace-?-vars goals)))

; (macroexpand-1 '(?- goals))     ; Check macro expands properly

(defun variables-in (exp)
  "Return a list of all the variables in exp"
  (unique-find-anywhere-if #'variable-p exp))

(defun unique-find-anywhere-if (predicate tree &optional found-so-far)
  "Return a list of leaves of tree satisfying predicate, with duplicates removed"
  (if (atom tree)
      (if (funcall predicate tree) (adjoin tree found-so-far) found-so-far)
      (unique-find-anywhere-if predicate (first tree)
                            (unique-find-anywhere-if predicate (rest tree) found-so-far)

(defun top-level-prove (goals)
  "Prove the goals, and print variables readably"
  (show-prolog-solutions (variables-in goals) (prove-all goals +no-bindings+)))

(defun show-prolog-solutions (vars solutions)
  "Print the variables in each of the solutions"
  (if (null solutions)
      (format t "~&No.")
      (mapc #'(lambda (solution) (show-prolog-vars vars solution)) solutions))

(defun show-prolog-vars (vars bindings)
  "Print each variable with its binding"
  (if (null vars)
      (format t "~&Yes")
    (dolist (var vars)
      (format t "~&~a = ~a" var (subst-bindings bindings var))))
  (princ ";"))

;;; --- Examples ---

; Now let's try some queries:
;  (?- (likes Sandy ?who))
; ?WHO = LEE;
; ?WHO = KIM;
; ?WHO = CATS;
;  ( ?- (likes ?who Sandy))
; ?WHO = KIM;
;  ( ?- (likes Robin Lee))
; No.
;For a more sophisticated test, try the Zebra Puzzle at:
;                                            ----------------- End ------------------

The Zebra Puzzle (Prolog in Lisp)

I am delighted to have got Peter Norvig's Lisp interpreter for Prolog working (in its simplest form) from Chapter 11 of his book, "Paradigms of Artificial Intelligence programming".

I tested it on his Zebra puzzle, where he states:
"This took 278 seconds, and profiling (see page 288) reveals that the function prove was called 12,825 times. A call to prove has been termed a logical inference, so our system is performing 12825/278 = 46 logical inferences per second, or LIPS.

Good Prolog systems perform at 10,000 to 100,000 LIPS or more, so this is barely limping along."
On my Windows 10 HP laptop, the computation took 7 seconds with 29,272 calls to 'prove'.

I guess that's 4,182 LIPS for compiled Lisp from LispWorks - program totally unoptimised.

His book is rather old (1992).


The Zebra puzzle

"Here is an example of something Prolog is very good at: a logic puzzle. There are fifteen facts, or constraints, in the puzzle:
1. Five houses in a line, each with an owner, a pet, a cigarette, a drink, and a color.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Winston smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house on the left.
11. The man who smokes Chesterfields lives next to the man with the fox.
12. Kools are smoked in the house next to the house with the horse.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.
The questions to be answered are: who drinks water and who owns the zebra?"

The translation into Prolog in Lisp uses a Lisp-like syntax for Prolog facts and rules (both are clauses). Here's the Prolog 'program' coding the above problem.

;;; --- Lisp code follows - comments from Norvig's book  ---
;;; To solve this puzzle, we first define the relations nextto (for "next to") and
;;;  iright (for 'immediately to the right of'). They are closely related to member,
;;; which is repeated here.

(<- (member ?item (?item . ?rest )))
(<- (member ?item (?x . ?rest) ) (member ?item ?rest))

(<- (nextto ?x ?y ?list) (iright ?x ?y ?list))
(<- (nextto ?x ?y ?list) (iright ?y ?x ?list))

(<- (iright ?left ?right (?left ?right . ?rest)))
(<- (iright ?left ?right (?x . ?rest)) (iright ?left ?right ?rest))
(<- (= ?x ?x))

;;; We also defined the identity relation, =. It has a single clause that says that any x is
;;; equal to itself. One might think that this implements eq or equal. Actually, since
;;; Prolog uses unification to see if the two arguments of a goal each unify with ?x, this
;;; means that = is unification.

;;; Each house is of the form:
;;; (house nationality pet cigarette drink house-color)
;;; ?h is the variable representing the list of the five houses

(<- (zebra ?h ?w ?z)

  (= ?h  ((house norwegian ? ? ? ?) ? (house ? ? ? milk ?) ? ? ) )              ; 1, 10, 9
  (member (house englishman ? ? ? red) ?h)                                             ; 2
  (member (house spaniard dog ? ? ?) ?h)                                                 ; 3
  (member (house ? ? ? coffee green) ?h)                                                  ; 4
  (member (house ukrainian ? ? tea ?) ?h)                                                 ; 5
  (iright (house ? ? ? ? ivory)                                                                     ; 6
             (house ? ? ? ? green) ?h)
  (member (house ? snails winston ? ?) ?h)                                               ; 7
  (member (house ? ? kools ? yellow) ?h)                                                 ; 8
  (nextto (house ? ? chesterfield ? ?)                                                         ; 11
             (house ? fox ? ? ?) ?h)
  (nextto (house ? ? kools ? ?)                                                                   ; 12
              (house ? horse ? ? ?) ?h)
  (member (house ? ? luckystrike orange-juice ?) ?h)                              ; 13
  (member (house japanese ? parliaments ? ?) ?h)                                   ; 14
  (nextto (house norwegian ? ? ? ?)                                                          ; 15
              (house ? ? ? ? blue) ?h)

;; Now for the questions:

   (member (house ?w ? ? water ?) ?h)                                                     ; Q1
   (member (house ?z zebra ? ? ?)  ?h) )                                                   ; Q2

; Here's the query

  (?- (zebra ?houses ?water-drinker ?zebra-owner))

; .. and here's the result



I'll publish the Lisp code for the Prolog interpreter separately (here):

Friday, February 17, 2017

Le terrible dilemme de la glorieuse France

Prior to Germany's unification in the mid-nineteenth century, France had regularly been top dog in Europe for a thousand years. From Charlemagne through the Sun King to Bonaparte, the French do not forget.

After the second world war, with Germany both beaten and shamed, the French seized upon the idea of the EEC/EU. They would lead an exhausted continent, and the humiliated Germans would pay.

This vision of the EU as a greater, more glorious France endured for fifty years. It took the post-Cold War reunification of Germany and a new generation of Germans with declining guilt, to parlay Germany's economic power into European political leadership.

Who can forget those pictures of Angela Merkel, striding into power-summits with a diminutive Francois Hollande trotting beside her, as if a handbag dog?

A Germany coming into its own will have its natural satellites: Austria, parts of Eastern Europe. But France? Here is the dilemma. The EU project has become a suffocating straitjacket for France, forcing it into subservience to Germany. German-interest policies inflicted upon the whole EU have created popular discontent within France as elsewhere.

The result has been the collapse of the establishment parties in France, the Socialists and the Republicans, and the emergence of a Tony Blair-lite politician (Emmanuel Macron) along with the nationalist Front National as the main contenders for power.

The French establishment is solidly pro-EU, and as defeatist as the British powers-that-be. Its 'realistic' view is that the economic realities cannot be denied and that the best France can hope for is German satellite status with influence.

Marine Le Pen speaks for a France which, like Brexit UK, decouples from German domination.

It's not clear whether the upcoming Presidential election will coincide with a decisive rupture in the dynamics of French politics, which could hand Le Pen the victory. But the tensions between la glorieuse France and its default deferential future will only grow.

If not this time, then the next.

Thursday, February 16, 2017

Stonehenge in the February rain

Perverse to visit Stonehenge yesterday, with heavy rain forecast for most of the day. Perhaps it was only Bristol Water, turning off our supply for 8 hours for 'urgent repairs', who could have forced us out.

Anyway, a chance to see the new Visitor Centre and admire the A303 before it vanishes into a tunnel forever.

Clare approaches the new Visitor Centre - henge-themed

An ancestor of Trevor Eve was found here 5,000 years ago
(click on image to make larger and read the caption).

Never have I seen such bedraggled sheep

Traffic jams on the A303 .. oh, and some rocks

Clare was sampling something from the local druids I guess

We did have a conversation about it.

Afterwards we took a late lunch in Warminster. Much as I would like the town to be associated with the heavy military presence on the adjacent Salisbury Plain, in fact:
"The town's name has evolved over time, known as Worgemynstre in approximately 912 and it was referred to in the Domesday Book in 1086 as Guerminstre.

The town name of Warminster is thought to derive from the River Were, a tributary of River Wylye which runs through the town, and from an Anglo-Saxon minster or monastery, which existed in the area of St Denys's Church.

The river's name, "Were" may derive from the Old English "worian" to wander."

Wednesday, February 15, 2017

The problem of dialogue as regards chatbots

Me: "So here's my plan."

Clare: "OK."

Me: "I've copied Peter Norvig's chapter 11 code for a Prolog interpreter in Lisp into a Notepad file. Unfortunately copying from PDF introduces all kinds of formatting errors, so it takes a while to get it into a compilable state."

Clare: "?"

Me: "I need to work through his main functions - principally to exactly understand his unification algorithm to start with. I may modify the code a bit, make it more transparent."

Clare: "??"

Me (oblivious): "And then I'm not sure I like the way he's storing clauses as plists on the clause head predicate. I think an assoc list would be clearer, if less efficient. Also, I need to do a few paper and pen examples to understand exactly the rationale for variable-renaming between clauses during resolution."

Clare: "???"

Me: "I'll get his standard Prolog depth-first search to work first of course. But I think it would be a good idea to explicitly break out the resolution procedure as a standalone function, and then parameterise the proof procedure by a range of possible search methods including breadth-first and best-first."

Clare: "????"

Me: "Of course, all this is just to get a series of tools in place for my speech-act planner, the one that's going to make my chatbot able to steer a conversation."

Clare: "?????"

Me: "I really think this could be a stellar app. I can see it on Google Play. The trouble is, 'in the knowledge lies the power' is just as relevant here and I might need to spend way too much time just data-filling various knowledge-bases, ... hmm, unless I can get it to safely learn from users. That's where Google does have an advantage ..."


Clare: "Is that Mr Bullfinch I see on the fat block?"