;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;  declare.lisp
;;;  Written by:  Shaul Markovitch
;;;  Last time modified: 10/1/2000 
;;;
;;; This file contains declarations of global variables and structures 
;;; used by the system.
;;; It should be loaded before compiling other files.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; The following variables hold the default value for each of the 
;;; filters.  The defaults are set in the file "defaults" at the end
;;; of the loading sequence.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defvar *default-generation-filtering-technique* nil)
(defvar *default-attention-filtering-technique* nil)
(defvar *default-acquisition-filtering-technique* nil)
(defvar *default-retention-filtering-technique* nil)
(defvar *default-utilization-filtering-technique* nil)
(defvar *default-training-search-strategy* nil  
    "The search strategy used during training")
(defvar *default-testing-search-strategy* nil
    "The search strategy used during testing")
(defvar *default-search-strategy* nil)
(defvar *default-learning-strategy* nil)
(defvar *default-search-technique* nil)
(defparameter *default-use-hash* t)
(defvar *default-macro-db* nil)
(defvar *default-problem-set* nil)

(defvar *domains*  nil "A list of possible domains")
(defvar *default-domain* nil "The default domain")
(defvar *default-search-use-macros-flag* t)
(defvar *default-use-macros-in-training-flag* t
    "Macros are useually used during testing.  This flag tells whether to use 
    macros while learning")
(defparameter *default-test-set-size* 100 
    "The default size of the set used for testing")
(defparameter *default-resource-type* 'problems
    "The default type of resource used to limit learning. Can be problems, 
    generated, expanded and cpu-seconds")
(defparameter *default-max-resources* 1000
    "The default amount of resourecs for limiting the learning session")
(defparameter *default-number-of-testing-points* 10
  "the default number of test points during learning.")

(defparameter *learning-report-flag* t
    "This flag controls whether the learning procedure prints various 
    information during learning")


(deftype boolean () '(member t nil))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; parameter-spec
;;;
;;; A structure used to hold various information about parameters throuout 
;;; the system.  The information is mainly used by the GUI subsystem to
;;; allow the usr changing values of pparameters.  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct parameter-spec
  (name nil :type symbol)
					; The name of the parameter.
					; Must be a symbol.
  (default nil)
					; The default value for the
					; parameter
  (possible-values nil :type list)
					; Possible values of the parameter.
					; Should be expanded to allow
					; specification of ranges of numbers.
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; search-node
;;;
;;; A node in the search graph (or search tree).  Used by the search
;;; procedures to build and search the search graph.  Also used by the
;;; acquisition procedure to extract macros from the solution path.
;;; Most of the search procedure use only the parent pointer to point
;;; to ther ancestor.  This pointer is later used for extracting
;;; the solution path.  The children field should be used when we want
;;; to pass to the acquisition procedure a whole trace of the search tree.
;;; There is a good chance that this structure will be expanded to
;;; store more information that is needed by the learning programs.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct search-node
  (state nil)
					;  The state.
  (h 0 :type number)
					;  The heuristic value of the state
  (g 0 :type number)
					;  The cost of the current path
					;  from the initial node
  (f 0 :type number)
					;  g+h
  (parent nil :type (or search-node null))
					;  A pointer to the parent.  Used to
					;  recover the solution 
					;   path.
  (op nil)
					;  The operator used to generate this
					;  node.  Empty for the 
					;  Initial state.  May be a macro
					;  operator.
  (reopened 0 :type fixnum)
  (children nil)
					;  A list of pointers to the successor
					;  nodes.  Usually this field is not
					;  used 
)



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; learning-resources
;;;
;;; A structure for storing the various resources consumed during
;;; learning.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct learning-resources
  (generated 0 :type number)
					; The accumulated number of
					; generated nodes
  (expanded 0 :type number)
					; The accumulated number of
					; expanded nodes
  (cpu-seconds 0 :type number)
					; The accumulated number of
					; cpu seconds
  (problems 0 :type number)
					; the accumulated number of
					; training problem solved
  (macros 0 :type number)
					; The total number of macros
					; learned.

  )




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;  search-outcome
;;;
;;;  A structure used to hold the result of the search.  Includes the 
;;;  node of the goal state (which can be used to extract the solution 
;;;  path.)  It also includes various statistics gathered during the 
;;;  search.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(defstruct search-outcome
  (solution-found nil)
					; T if found. FAIL if not.
					; LIMIT if the
					; resource limit was exhausted.
  (solution-path nil :type (or search-node null))
					; The node of the goal state.
  (generated 0 :type number)
					; The number of nodes genrated
  (expanded 0 :type number)
					; The number of nodes expanded
  (reopened 0 :type number)
  
  (cpu-seconds 0 :type number)
					; The cpu time consumed in seconds 
  (solution-cost 0 :type number)
					; The sum of the costs of the arcs
					; on the solution path.
  (solution-length 0 :type fixnum)
					; The length of the solution
					; path
  (total-cost 0 )
  (data nil)
)                                
                                
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; problem-set-outcome
;;; 
;;; This structure is used for returning information about the results 
;;; of solving a set of problems.  It is similar to the search-outcome 
;;; structure, however there are two main differences.  The numbers given
;;; here are averages over the search-outcomes of the whole set of 
;;; problems.  Also there are no solution fields here.
;;; All the fields here are of type "statistics".  That means that they
;;; contain a structure that contains the mean, variance, standard 
;;; deviation, minimum and maximum.  These structures are produced by
;;; utility function "collect-statistics" found in the file 
;;; "utilities.lisp"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
                                 
(defstruct (problem-set-outcome (:type list))
  (n 0 :type fixnum)
					; The number of problems in  this set.      
  (generated nil)
					; The mean number of generated
					; nodes
  (generated-list nil)
  (expanded nil )
					; The mean number of expanded
					; nodes
  (reopened nil)
  
  (cpu-seconds nil)
					; The mean number of seconds
  (solution-cost nil)
					; The mean solution cost
  (solution-length nil)
					; The mean solution length
  (length-list nil)
 (total-cost nil)
 (total-cpu 0.0 :type float)

  )
                    
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; learning-outcome
;;; 
;;; This structure is used for returning information about the results 
;;; of a learning session.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct learning-outcome
  (macros nil)
					; The macros learned
  (resources nil :type (or learning-resources null))
					; The resources consumd during learning
  (test-results nil :type list)
					; A list of result records for all
					; the test performed
)



(defstruct search-data
   (open nil :type list)
   (closed nil :type list)
   (open-hash nil)
   (closed-hash nil))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; search
;;; 
;;; A structure used to specify various parameters of the search strategy 
;;; used.   While the domain structure is used to specify the list of 
;;; possible heuristic functions, the search structure specifies the actual 
;;; heuristic used for the search.   It also contains a flag that 
;;; specifies whether to use macros during the search.
;;; It contains a flag that specifes whether to use 
;;; a utilization filter and the technique used for filtering.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  
(defclass search ()
   (
  (resource-limit :accessor search-resource-limit
		  :initform most-positive-fixnum
		  :initarg :resource-limit
		  :type fixnum)
					;A limit on the number of nodes allowed
                                        ;to be generated during the search.
  (use-macros-flag :accessor search-use-macros-flag
		   :initform *default-search-use-macros-flag*
		   :initarg :use-macros-flag
		   :type boolean)
					;A flag.  If T macros will be used
                                        ;during search.
  (use-utilization-filter-flag :accessor
				search-use-utilization-filter-flag
				:initform t
				:initarg :use-utilization-filter-flag
				:type boolean)
					;A flag.  If T utilization filtering
                                        ;will be applied to the macros before
                                        ;passing it to the seacrh procedure.
  (utilization-filtering-technique :accessor
				   search-utilization-filtering-technique
				   :initform 
				   *default-utilization-filtering-technique*
				   :initarg :utilization-filtering-technique
				   )
                                        ;The technique used for utilization 
                                        ;filtering
  (graph-flag :accessor search-graph-flag
	      :initform t
	      :initarg graph-flag
	      :type boolean)
					;A flag. If T the search space is
                                        ;searched as graph.  I.e., a
					;closed  list
                                        ;is kept and a new node is
					;created only
                                        ;if the state is not in closed or open.
  (mixup-flag :accessor search-mixup-flag
	      :initform t
	      :initarg :mixup-flag
	      :type boolean)
					;A flag tells whether to mixup
                                        ;generated nodes.  This costs
                                        ;some time but helps prevent
                                        ;repeatetions of experiments

  (next-node-selector
                 :accessor search-next-node-selector
		 :initform #'(lambda (open strategy)(declare (ignore
							      strategy))(first open))
		 :initarg :next-node-selector
		 :type (or symbol function))
  (sort-accessor :accessor search-sort-accessor
		 :initform #'search-node-f
		 :initarg :sort-accessor
		 :type (or symbol function))
  (test-open :accessor search-test-open
		    :initform t
		    :initarg :test-open
		    :type boolean)
  (test-closed :accessor search-test-closed
		    :initform t
		    :initarg :test-closed
		    :type boolean)
  (use-hash :accessor search-use-hash
		    :initform *default-use-hash*
		    :initarg :use-hash
		    :type boolean)
  (update-g  :accessor search-update-g
		    :initform t
		    :initarg :update-g
		    :type boolean)
  (reopen-flag :accessor search-reopen-flag
		    :initform t
		    :initarg :reopen-flag
		    :type boolean)
  
  ))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; graphic-display
;;;
;;; A structure which supplies the information of how to graphically
;;; display a search for a particular domain.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct graphic-display
  (initialize-display-fn nil)
					;A function that initializes
					;the display
  (draw-domain-fn nil)
					;A function that draws an
					;initial representation of the
					;domain before the search
  (draw-search-transition-fn nil)
					;A function that draws an
					;application of an operator
					;during the search.
  (draw-solution-fn nil)
					; A function that draws the
					; solution path of a search
  )

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;  Macro
;;;
;;; This structure stores all the necessary information about a macro.
;;; The main elements of a macro are the start and end states and the set
;;; of operators that transfer the start state to the end state.
;;; There are some statistics field that store information about the usage
;;; of the macros.  They are likely to be used by the various filters.
;;; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct (macro (:type list) :named)
  (start-state nil)
					; The start state of the macro
  (end-state nil)
					; The end state of the macro
  (operators nil :type list)
					; The sequence of operators
					; that  when applied
					; To the start state produces the
					; end state.
  (length 0 :type fixnum)
					; The length of the macro
  (times-applied 0 :type fixnum)
					; The number of times the macro
					; was applied during 
					; search
  (times-used 0 :type fixnum)
					; The number of times the macro
					; was used as a part of a 
					; solution path
  (times-mislead 0 :type fixnum)
					; The number of times that the
					; macro was applied to 
					; states on the solution path but
					; did not participate
					; in the solution
  )

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; domain
;;; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defclass domain ()
  ((name :initform nil
	 :accessor domain-name
	 :initarg :name
	 :type (or symbol string))
					; A name for this type.
  (operators :initform nil
	     :accessor domain-operators
	     :initarg :operators
	     :type list)
					; A list of operators.
  (apply-op-fn :initform nil
	       :accessor domain-apply-op-fn
	       :initarg apply-op-fn
	       :type (or symbol function)
	       )
					; A function that takes an
					; operator and a state and 
					; returns a new state or NIL
					; if  the operator can not
					; be applied.
  (heuristic-functions :initform nil
		       :accessor domain-heuristic-functions
		       :initarg :heuristic-functions
		       :type list)
					; A set of heuristic
					; functions. This is 
					; mainly used for the GUI for
					; leting the user select
					; a function.  The particular
					; function used for a search
					; is stored in the "search" data
					; structure.
  (state-equal-fn :initform #'equalp
		  :accessor domain-state-equal-fn
		  :initarg :state-equal-fn
		  :type (or symbol function))
					; A function for deciding when
					; two states are 
					; equal.  The default function,
					; equalp, will be 
					;sufficient for most domains.
  (state-copy-fn :initform #'copy-tree
		 :accessor domain-state-copy-fn
		 :initarg :state-copy-fn
		 )
  (heuristic-fn :accessor domain-heuristic-fn
		:initform #'(lambda (s1 s2)(declare (ignore s1 s2)) 0)
		:initarg :heuristic-fn
		:type (or symbol function))
					;The heuristic function used
					;for  the search
   
  (cost-fn :initform #'(lambda (s1 s2 op)(declare (ignore s1 s2 op)) 1)
	   :accessor domain-cost-fn
	   :initarg :cost-fn
	   :type (or symbol function) )
					; A function that returns the
					; cost  of the edge 
					;between two 
					; successive states.  For most
					; cases  the cost of 
					; an edge will be 1.
  
  (gen-goal-fn :initform nil
	       :accessor domain-gen-goal-fn
	       :initarg :gen-goal-fn
	       :type (or symbol function))
					; A function that generates a
					; random goal state
  (reverse-operators :initform nil
		     :accessor domain-reverse-operators
		     :initarg :reverse-operators
		     :type list)
					; A set of reverse operators for
					; generating 
					; random problems (by generating
					; random goals and 
					; applying
					; a random sequence of reverse
					; operators.  
					;  Many times the set of reverse
					;  operators will be 
					; the same 
					; as the set of operators.
  (apply-rev-op-fn :initform nil
		   :accessor domain-apply-rev-op-fn
		   :initarg :apply-rev-op-fn
		   :type (or symbol function))
					; A function for applying a reverse
					; operators on 
					; a state.  In many cases it will
					; be the same as 
					; "apply-op-fn".
  (initialize-hash-fn :initform  #'(lambda (d) (declare (ignore d))
                                           (make-hash-table :test #'equal))
		      :accessor domain-initialize-hash-fn
		      :initarg :initialize-hash-fn
		      :type (or symbol function))
					; Initialize cache for states
  (get-hashed-state-fn :initform #'gethash
		       :accessor domain-get-hashed-state-fn
		       :initarg :get-hashed-state-fn)
					; Get cached state
  (put-hashed-state-fn :initform #'(lambda (state hash node)
                            (setf (gethash state hash) node))
		       :accessor domain-put-hashed-state-fn
		       :initarg :put-hashed-state-fn)
					; put argument into the cached
					; state
  (generation-seed :initform nil
		       :accessor domain-generation-seed
		       :initarg :generation-seed

   )
  
 
  
))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; learning
;;;
;;; A major data structure that defines a learning system.  It
;;; includes the learning domain and the techniques used for learning,
;;; including all the filters and the search methods for both training
;;; and testing.  In addition it contains various parameters of the
;;; learning process.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct learning
  (domain *default-domain* )
					; The domain used for learning.
  (generation-filtering *default-generation-filtering-technique*
			)
					; The method used for
					; generating and filtering
					; training problems.
  (training-search-strategy *default-training-search-strategy*)
					; :type (or search null))
					;  Bug in CMUCL
					; The search strategy used for
					; training. 
  (attention-filtering *default-attention-filtering-technique*)
				
					; The attention filtering
					; technique.  Used for
					; selecting subpathes and
					; converting them to macros.
  (acquisition-filtering *default-acquisition-filtering-technique*
			 			 )
					; The technique used to decide
					; whether to add a newly
					; generated macro to the macro
					; knowledge base.
  (retention-filtering  *default-retention-filtering-technique*
		)
					; The method used for
					; forgetting part of the macro
					; database. 
  (utilization-filtering *default-utilization-filtering-technique*
			 )
					; The method used for
					; filtering macros before
					; handing them to the problem
					; solver. 
  (testing-search-strategy *default-testing-search-strategy*)
					;:type (or search null)) 
					; The search method used when
					; using the macros for problem
					; solving. 
  (max-resources *default-max-resources*)
					; The resource limit
					; for learning.  The type of
					; the resource is stored in
					; the next field.
  (resource-type *default-resource-type*
       :type  (member generated expanded problems cpu-seconds macros))
					; The type of resources used
					; for limiting the learning
					; and setting test points.  In
					; most cases the resources
					; will be of type "problem"
					; which means that the
					; learning will stop after
					; processing "max-resources"
					; training problems.
  (testing-points *default-number-of-testing-points*
		  :type fixnum)
					; The number of points during
					; learning where tests will be
					; performed. 
  )
   


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; problem
;;;
;;; A structure that describes a problem.  Usually a problem is
;;; defined by an initial state and a final state but sometimes it can
;;; be defined by a goal predicate.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct problem
  (init-state nil)
					; The initial state
  (goal-state nil)
					; The goal state.  Not
					; necessary if the next field
					; is given.
  (goal-p nil)
					; A goal predicate.  A
					; function that returns true
					; iff the given state is a
					; goal state.
  )


(defclass macro-db
  ()
  ((macros :initform nil
	   :initarg :macros
	   :accessor macro-db-macros)
   (hash   :initform nil
	   :initarg :hash
	   :accessor macro-db-hash)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; statistics
;;;
;;; A general structure to hold a statistics about a single
;;; variable/measurement.  The function collect-statistics
;;;  gets a list of values and returns a
;;; structure of this kind.  Most of the results obtained during
;;; experimentation will be of this type.  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defstruct (statistics ( :type list))
  (mean 0.0 :type float)
					; mean (average)

  (var 0.0 :type float)                 ; variance
  (std 0.0 :type float)
					; Standard deviation
  (median 0 :type number)

  (confidence-intervals nil :type list)
  
  (min 0 :type number)
					; minimum
  (max 0 :type number)
					; maximum
  (n 0 :type fixnum)
					; The size of the population.
  )