Top
Photo Drawings Software Writing Reading Memo Study Profile Bookmark 
Amethyst DumLambda PetitLambda Yamanba JSharp JFlat OOPS yash KumonoIto ML Toys 

Programming Language OOPS!

Keyword

GPS, constrainted programming, Prolog, unification

What is 'OOPS!' ?

'OOPS!' gives a sequence of operators which reduce the difference of given two state by using GPS(General Problem Solver) algorithm.
I designed and implemented this for a free subject assignment of the lecture "AI".
The name of 'OOPS!' is an abbreviation of 'Only One Problem Solver' (and also, "oops!" was the habbit of saying of the lecturer).

GPS

Terms.
Predicate
Ex:"at Tokyo","A is a man."
Assertion
assignment value to variables, if any, in predicates. Ex:"at Tokyo","Taro is a man."
State
a set of assertions. ex:{"at Ishikawa","be a student"}
Operator
An operator is a function on states. Each operators has its own condition that restricts states which it can apply to. For example, operator "take the Shinkansen bullet train 'Nozomi'" requires that argument state contains two assertions(precondition), "be at Tokyo station" and "have a ticket". When applied, this operator produces new state (= argument state - {"at Tokyo station","have a ticket"} + {"at Osaka station"}). {"at Osaka station"} is postcondition of this operator.
Problem
Problem is composed of two states (start and goal).
The purpose of GPS is to get a sequence of operators which produce a states that includes goal state when given start state.
on(...o1(start)...) ⊇ goal
GPS searches operators as following. start and goal are parameters of this procedure.
  1. If goal is unifiable with any subset of start, this iteration finishes.
  2. Otherwise, choose an operator O which reduces the difference of start and goal mostly. If there is no oeperator available, this iteratioin fails.
  3. Produce two sub-problem. One is composed of original start as its start ,and postcondition of o as its goal. The other is composed of precondition of o as its start, and original goal as its goal. And search solutions on these sub-problems recursively.
  4. If search on both sub-problem succeed, appends the obtained sequences of operators(O1,O2) and o
    O1 + o + O2

    and returns successfully.
  5. If any sub-problem fails, remove O from the available operators set, and back to step 2 and retry.

Sample Program

Plato also dies.

Prolog already have proved that "A Man is motal. Socrates is a man. Therefore Socrates is motal". Now, is this applicable to Plato? Let's examine it by using OOPS!.

alsoplatodie.ops
predicate man('W){ }
predicate mortal('W){ }
operator ManIsMortal('W){
    require { man('W) }
    ensure{ mortal('W) }
}
problem ('Who){
    start{ man(Plato) }
    goal{ mortal('Who) }
    priority{ }
}
Two predicates in line 1 and 2 declare two predicates. Former predicate states that "'W is a man" and latter states that "'W is mortal".
An operator in line 3-6 declares an operator which transforms a state where "'W is a man" is true to a state where "'W is mortal" is true.
A problem in line 7-11 defines a problem to be solved. It says that "Is it possible to transform a state where "Plato is a man" to a state "Any 'W is mortal"? If this is possible, give a sequence of operators which make that transition".

When given this program, OOPS! returns below solution.

Output
bash-2.02$ java OOPS < alsoplatodie.ops
** Solved **
Start:
man(Plato)
Operators:
ManIsMortal(Plato)
Goal:
mortal(Plato)
This output means that operator 'ManIsMortal' transforms initial state where "Plato is a man" to goal state where "Plato is mortal".

A Monkey wants to eat a banana.

In the lecture, this problem was presented as a example of GPS algorithm.
The goal to make OOPS! is to solve this problem.
('//' and '#' start comment.)

monkeybanana.ops
// definition of predicates

# A monkey is at location 'A, where 'A must be A, B or C.
predicate MonkeyAt('A) {   'A: A , B , C } 

# A box is at location 'A, where 'A must be A,B or C.
predicate BoxAt('A){   'A: A , B , C } 

# 'A is on the hand, where 'A must be Empty or Banana.
predicate hand('A) {  'A: Empty < Banana } 

// definition of operators
operator getBanana() { # get a banana at hand
    require { 
        MonkeyAt( C) # move to C where is a banana.
        BoxAt(C)     # be on the box to get the banana.
        hand(Empty)  # freehand
    }
    ensure {
        MonkeyAt( C) # monkey is at C.
        BoxAt(C)     # the box is also at C.
        hand(Banana) # Monkey has the banana in his hand.
    }
}
operator move('X,'Y){ # move to 'Y from 'X.
    require {
       MonkeyAt( 'X)
    }
    ensure {
       MonkeyAt( 'Y)
    }
}
operator moveBox('X,'Y){ # move the box to 'Y from 'X
    require {
       MonkeyAt('X)  # the monkey and the box are at same location.
       BoxAt('X)
       hand(Empty)   # the monkey must be free-hand.
    }
    ensure{
       MonkeyAt('Y)  # The monkey moves to 'Y with the box
       BoxAt('Y)
       hand(Empty)   # The monkey will be free-hand after he moved the box.
    }
}

// problem to solve
problem() {
    start {
        MonkeyAt(A)  # The monkey is at A.
        BoxAt(B)     # The box is at B.
        hand(Empty)  # The monkey is freehand.
    }
    goal{
        hand(Banana) # The goal is get the banana.
    }
    priority {
        MonkeyAt < BoxAt < hand 
    }
}

Output
bash-2.02$ java OOPS < monkeybanana.ops
** Solved **
Start:
MonkeyAt(A)
BoxAt(B)
hand(Empty)
Operators:
move(A,B)
moveBox(B,C)
getBanana()
Goal:
BoxAt(C)
MonkeyAt(C)
hand(Banana)

This output says

  • move from A to B(move(A,B))
  • move from B to C with a box in hand(moveBox(B,C))
  • then the monkey can get a banana.

OOPS!

If OOPS! cannot find any solution, OOPS! will response like following.
s
bash-2.02$ java OOPS < difficult.ops
** OOPS!! fail to solve **

Other

types

Variables have types.
FLAT type
Any value can be assigned to variable of flat type. And there is no order in these values.
NUM type
To variables of NUM type, only numeral values can be assigned.
Ordered type
You can restrict values to be assigned to variables of this type. And an order between these values can be defined.
predicate PersonalData ('Name,'Weight,'Height,'Address){
   'Name   : FLAT
   'Weight : NUM
   'Height : short < medium < high , tall
}

constraint condition

You can restrict values to be assigned to variables by where clause.
operator trip('From, 'To, 'Distance, 'Fare, 'Pocket) {
  require { 
    at('From) 
    distance('From,'To,'Distance)
    fare('From,'To,'Fare)
    haveMoney('Pocket)
  }
  ensure  { 
    at('To) 
  }
  where {
        'From <> 'To 
    and ('Distance > 100 or 'To = Kyoto) 
    and 'Fare <= 'Pocket
  }
}

Document

"Programming language OOPS!"(japanese) (PS) (pdf) (LaTex)

Sourece code

OOPS-1.0.tgz

In addition, JavaCC and JGL is required to compile.

JavaCC
http://www.metamata.com/JavaCC/
JGL
http://www.objectspace.com/jgl/prodJGL.asp

Install

gtar zxf OOPS-1.0.tgz
cd OOPS_1.0
modify CLASSPATH and JAVACOPTIONS in Makefile
gmake