Page Numbers: Yes First Page: 1
Heading:

April 28, 1979 1:18 PM[IVY]<KRL>document>proc-formal

Formal specification of processes in KRL

Specification of the top-down process mechanisms in KRL-1

This file contains descriptions of the process creation and scheduling mechanisms for the goal-driven part of programming (i.e. not the event-driven stuff). The approach in KRL-1 is similar to that of KRL-0, although generalized and sanitized. Essentially, there are processes and agendas; processes may be on any number of agendas (0,1, or more) and may appear on the same agenda at more than one place in its list of processes; special processes called Schedulers loop through the processes on their agendas running each one in turn. Part of a process specification includes LISP code to be run, either an S-expression or a function and arguments. Various kinds of scheduling regimes are provided and hooks exist for the user to specify his own.

The process units

# LispExpression
self:
knownValues:SetOf(An Atom)
valueExpression:A String

# Process
self:
schedulers:SequenceOf↑1(A MultiTaskProcess) 1: Comment("the ones whose agendas I’m on")
invokingScheduler:A Scheduler
expression:A LispExpression
function:A LispExpression
arguments:A LispList
status:Or(’NEW, ’RUNNING, ’SUSPENDED, ’DEAD)
Default(’NEW)
continuation:A LispStackPointer
terminationAction:A LispExpression↑22: Comment("Used by TerminateProcess")
resources:A ResourceMeasure

The nature of "resources" has not yet been determined.

A Process may be on any number (0, 1, or more) of Scheduler agendas, but may not be on any agenda more than once.

# Scheduler
self:↑2A Process with function = ’Scheduler2: WhenIdentified(describe
self as such)
Comment("for efficiency")
agenda:SequenceOf(A Process)
currentProcess:↑1A Process1: Comment("if this Scheduler is not RUNNING, but not
the current Scheduler (i.e., it is above the
current Scheduler), then this
is also the value of the variable
CURRENTPROCESS bound at an
appropriate location on the LISP stack.")
addor:A LispExpression with
knownValues = {AGENDA, NEWPROCESS}
valueExpression = "new AGENDA"
selector:A LispExpression with
knownValues = {PROCESSES}
valueExpression = "next process to be run"
loopAction:↑5A LispExpression5: Comment("do before running next process")
exitAction:↑6A LispExpression6: Comment("do when no more processes")

The function Scheduler loops through the following steps:

AGENDA ← ($ seek the scheduler’s agenda)

if AGENDA is
a.NIL, execute the exitAction and SuspendMe;
b.otherwise,

1.evaluate loopAction (this may explicitly invoke the exitAction);

2.run the result of evaluating the selector, which should be a process.

In addition to a Scheduler’s being run be virtue of being the next process chosen by some other Scheduler, a Scheduler process can be explicitly invoked through the command ($ \RunScheduler(NEWSCHEDULER)) , where NEWSCHEDULER is a unit described as a Scheduler.

It is invalid to attempt to run a Process at some level when it is already running above. This situation could come about if Scheduler2 were on the agenda of Scheduler1 and Scheduler3 and Scheduler1 activated Scheduler2 which in turn activated Scheduler3 which then attempted to activate Scheduler1. Remember, Schedulers are just special kinds of Processes and are treated as such.

# QueueScheduler
self:↑1A Scheduler with1: WhenIdentified(describe new as such)
selector =’(CAR AGENDA)↑22: Comment("FirstFromSequence")
addor =’(NCONC1 NEWPROCESS AGENDA)↑3
3: Comment("AddToBackOfSequence")
Comment("Should be TCONC eventually")

# StackScheduler
self:↑1A Scheduler with1: WhenIdentified(describe new as such)
selector =’(CAR AGENDA)↑22: Comment("FirstFromSequence")
addor =’(CONS NEWPROCESS AGENDA)↑3
3: Comment("AddToFrontOfSequence")

# SelectiveScheduler
self:↑1A Scheduler with1: WhenIdentified(describe new as such)
selector =LispValue(LIST X ’AGENDA)
binding X = PointerFor(My selectorFn)
addor =’(CONS NEWPROCESS AGENDA)↑3
3: Comment("AddToFrontOfSequence")
selectorFn:An Atom
A LispFunctionName

# KrlTopLevelScheduler
self:A QueueScheduler

The process commands

# KrlCommand
self:
translator: A LispExpression

# AddToAgenda↑11:HasFunctional(self, AddMeToCurrentAgenda with
process = LispValue(CURRENTPROCESS)
scheduler = LispValue(CURRENTSCHEDULER))
HasFunctional(self,AddToCurrentAgenda with
scheduler = LispValue(CURRENTSCHEDULER))
HasFunctional(self,AddMeToAgenda with
process = LispValue(CURRENTPROCESS))
self:A KrlCommand with
translator = ’[SELECTQ etc. . . .
AddToAgenda ($ Seek the process from THISCOMMAND
viewedAs An AddToAgenda))
($ Seek the scheduler from THISCOMMAND
viewedAs An AddToAgenda)]
process:A Process
scheduler:A Scheduler

exceptions:AlreadyOnAgenda

# RemoveFromAgenda↑11:HasFunctional(self, RemoveMeFromCurrentAgenda with
process = LispValue(CURRENTPROCESS)
scheduler = LispValue(CURRENTSCHEDULER))
self:A KrlCommand
process:A Process
scheduler:A Scheduler

exceptions:NotOnAgenda

Removes (Seek the process from this event) from (Seek the agenda from the scheduler from this event).

# RemoveFromAgendas↑11:HasFunctional(self, RemoveMeFromAllMyAgendas with
process = LispValue(CURRENTPROCESS)
schedulers = LispValue($ seek the schedulers
from process))
HasFunctional(self, RemoveMeFromAllItsAgendas with
schedulers = LispValue($ seek the schedulers
from process))
self:A KrlCommand
process:A Process
schedulers:SetOf(A MultiTaskProcess)

# SuspendProcess↑11:HasFunctional(self, SuspendMe with
process = LispValue(CURRENTPROCESS))
self:A KrlCommand
process:A Process

SuspendProcess doesn’t put the process back on an agenda.

# RescheduleProcess↑11:HasFunctional(self, RescheduleMe with
process = LispValue(CURRENTPROCESS)
scheduler = LispValue(CURRENTSCHEDULER))
self:A KrlCommand
process:A Process
scheduler:A Scheduler

RescheduleProcess suspends and puts back on an agenda.

# KillProcess↑11:HasFunctional(self, KillMe with
process = LispValue(CURRENTPROCESS))
self:A KrlCommand
process:A Process

KillProcess sets status of the Process to DEAD and if it had been running, returns control to its invoking scheduler. [If process is a Scheduler, it’s exitAction should be run???]

# TerminateProcess↑11:HasFunctional(self, TerminateMe with
process = LispValue(CURRENTPROCESS))
HasFunctional(self, TerminateMyScheduler with
process = LispValue($ seek the invokingScheduler
from process))
self:A KrlCommand
process:A Process

TerminateProcess EVALS the terminationAction of the process, then KillProcess.

# RunProcess↑11:HasFunctional(self, RunScheduler with
process = A Scheduler)
self:A KrlCommand
process:A Process

exceptions:ProcessDead, ProcessAlreadyRunning

RunProcess is not normally invoked by the user, but rather is internal to the Scheduler function. However, the user might want to invoke a special case of this through the RunScheduler functional in order to descend immediately to a lower scheduler rather than placing the new scheduler on the current agenda and waiting for its turn to come.

# Yield
self:A SchedulerEvent

Not specified yet: meant eventually to be a check of resources and continuation if OK.

Summary of the process commands

The following is a list of the process commands. Names on indented lines below a unit name indicate functionals associated with the unit.

AddToAgenda
AddMeToCurrentAgenda
AddToCurrentAgenda
AddMeToAgenda
RemoveFromAgenda
RemoveMeFromAgenda
RemoveFromAgendas
RemoveMeFromAllAgendas
SuspendProcess
SuspendMe
RescheduleProcess
RescheduleMe
KillProcess
KillMe
TerminateProcess
TerminateMe
TerminateMyScheduler
RunProcess
RunScheduler
Yield

Pieces of KRL needed to implement the Process commands

Seek the slot from !HANDLE variable viewedAs A Prototype returning a lispPointer
no triggering necessary

ReplaceDescribe the slot from !variable viewedAs A Prototype with !LISP variable
no triggering necessary

mechanism for hanging translators someplace: proposal exists to use a KrlCommand unit with a translator slot; the lisp code would be executed (note that functionals would expand to perspectives so that the command unit and all its functionals would have the same translator) and if it returned NIL, it would be assumed that the translator had interpret the command, otherwise what it returned would replace the $ expression as its CLISP translation.

for efficiency, it will be necessary to have a WhenIdentified type of trigger on prototypes so that individuals described as them would also be described as what the prototype self slot is described as (e.g., describe X as a Scheduler, want it also automatically described as a Process rather than having Seek have to do much extra work each time in tracking down descriptions on the self slot, etc.)

WhenIdentified, WhenDescribed, WhenKnown, etc. will have to provide pointers at least to the anchor just modified, if not the relevant pieces such as the unit, slot, prototype, etc., and a pointer to the new information so that the triggers could take action that includes using the new information (for selection of response, or for describing something else based on that information, etc.).

MISCELLANEOUS

To start KRL: KRL(CONTINUEFLG)

CONTINUEFLG=T:continue, i.e. do not restore agendas, etc.

As in KRL-0, you are put in a user executive loop and are expected to add processes to the KrlTopLevelScheduler (normally with the AddToCurrentAgenda command -- CURRENTSCHEDULER is bound to KrlTopLevelScheduler at this point). To quit, surrendering control to KrlTopLevelScheduler, type OK or GO.

Variables Available to User

CURRENTPROCESS

CURRENTSCHEDULERa Scheduler

LASTPROCESSRESULTused to allow processes to return values [this is in effect the same as AC1 for machine code in LISP function returns]; at the present time, this variable is not used anywhere in the process code and so must be manipulated entirely by the user’s code.

EXAMPLES

Alpha-Beta AND/OR Tree Search

We consider a depth-first search of an AND/OR tree aided by alpha-beta and the use of estimation functions to order search of successor nodes. The static evaluation function ESTIMATE, which takes as its argument a unit which is a TreeNode, is presumed to be available and meet the required constraints for such tree-searches (bounds, etc.). [see Nilsson, chapter 5]

# TreeNode
self:
contents:
value:↑1An Integer1: ToSeek(///TreeNodeSeekFn this Node)
WhenKnown(///ValueKnownFn this Node)
WhenKnown(///KillMe)
provisionalBackedUpValue:↑2An Integer2: WhenDescribed(///NewPBVFn this Node)
type:Or(’OR, ’AND)
parent:A TreeNode with type = Not(My type)
children:SequenceOf(A TreeNode with type = Not(My type))

[TreeNodeSeekFn (Node)

(PROG ((CHILDREN (Seek the children from Node viewedAs A TreeNode)))
(if (NULL CHILDREN)
then (RETURN (ESTIMATE ($ Seek the contents from Node)))
else [$ \Describe(!H Node, \A SelectiveScheduler with
exitAction = ’($ \KillMe())
selectorFn: ’BestEstimate
agenda = <!!R CHILDREN>]
[for CH in CHILDREN do ($ Describe(!!R CH, \A Process with
expression = !R
’(///something
which is a seek of the value from
CH viewedAs a TreeNode]

[ValueKnownFn (Node)

(PROG ((PAR (Seek the parent of Node))
(TYP (Seek the type of Node)PBV)
(PBV ← (Seek the PBV of PAR))
(if (OR (NULL PBV)(AND (EQ TYP ’OR)(IGREATERP NEWDESC PBV))
(AND (EQ TYP ’AND)(IGREATERP PBV NEWDESC))) then
($ \Describe(!H PAR, A TreeNode with PBV = !R NEWDESC)))
]

[NewPBVFn (Node)

(IF type = ’OR THEN
(look at all AND parents (start with parent and skip every other generation)
and if ANY has PBV >= NEWDESC then Value(Node) ← PBV(Node)
and KillProcess associated with this Node)
]

ELSE (look at all OR parents (start with parent and skip every other generation)
and if ANY has PBV <= NEWDESC then Value(Node) ← PBV(Node))
]

Pieces of KRL needed to implement the above example (in addition to pieces for KRL commands)

A ToSeek "trigger" that Seek would look for.

WhenKnown and WhenDescribed triggers containing arbitrary Lisp Code in terms of the unit just described and the value that just replaced the old one (these are ReplaceDescribes)

# # # # # # # # # # # # # # #

Units having to do with processors and processing

# Event
predecessors: SetOf(\An Event)
followers: SetOf(\An Event)

# *NOW*
self/Instance: An Event
1: Comment ("This is a very special instance which represents the immediate,
everchanging present moment. When it appears in descriptions, it
must be handled specially.")

# PastEvent
self: An Event with successors = Which HasElement *NOW*

# Processor↑11: HasFunctional (worldModel, WorldModel, self)
baseSpace:↑2 A DescriptionSpace
2:A TimeDependentSlot
Comment ("This represents the description space of everything the processor
can conceptualize.")
worldModel:↑3 A DescriptionSpace
3:A TimeDependentSlot
Comment ("This represents the description space of what the processor
believes about the real world.")

# *ME*↑1 1: Comment ("This represents the KRL processor itself, information about Me
is used in modelling itself, but is not interpreted in
normal functioning.")
self/Instance: A Processor with
baseSpace = *M*
worldModel = RealWorld

# ComputationProcess
self: An Event
processor: A Processor
descriptionSpace:
A DescriptionSpace
The↑1 baseSpace from a Processor thatIs My processor1: A Default
input: SetOf(\A Description with baseSpace = My descriptionSpace)
result: Or(A Success, A Failure)
output: SetOf(\A Description with baseSpace = My descriptionSpace)

# Seek↑11: FurtherSpecified(\ComputationProcess)
self: A ComputationProcess with
input = {My target, My specifier}
output = {My resultDesc}
processor: ; result: ; descriptionSpace: ; input: ; output:
target: A Description
specifier: A Description; A↑2 UniqueEntityCoreference2: A Default
resultEntity: An Entity; EntityOf(My descriptionSpace)
resultDesc:
A Description with baseSpace = My descriptionSpace
Which Describes My resultEntity
WhichIs DescribedAs My specifier

# Match↑11: FurtherSpecified(\ComputationProcess)
self: A ComputationProcess with
input = {My pattern, My datum}
processor: ; result: ; descriptionSpace: ; input: ; output:
pattern: A Description
datum: A Description

# RunProgram
self: A DoOperation
@?WhatIsThis??
(A Mapping with
pairs = {<My program, My self>,
<The inputs from My program, My inputs>,
<The outputs from My program, My outputs>})
processor: A Processor
program: A Program
inputs: SetOf(A Form)
result: A SuccessOrFailure
outputs: SetOf(A Form)

# # # # # # # # # # # # # # #

# ReasoningOperation
self: Categorized(’Type, {Inference,
DescriptionActivation,
DataModification,
ServantInvocation,
DemonInvocation}

# Inference
self: An Operation
previousState = A DescriptionState with
activeDescriptions = My oldDescriptions
resultingState = A DescriptionState with
activeDescriptions = SetUnion
({My oldDescriptions,
My newDescriptions})
system: A ConceptSystem
oldDescriptions: A DescriptionSet with content = HasSubset(My premises)
newDescriptions: A DescriptionSet with content = My conclusions
premises: SubsetOf(The beliefs from My system)
conclusions: SetOf(A Belief)

# DescriptionActivation
oldDescs: SubsetOf(The activeDescriptions from
a DescriptionState thatIs
the initialState from My self
viewedAs an Operation)
newDesc: A Description; A LongTermDescription
activeForm: A Description with meaning = The meaning from My newDesc
MemberOf(The activeDescriptions from
a DescriptionState thatIs
the resultingState from My self
viewedAs an Operation)

# DataModification
oldForms: SubsetOf(The structures from
a DescriptionState thatIs
the initialState from My self
viewedAs an Operation)
SetOf(Not(MemberOf(The structures from
a DescriptionState thatIs
the resultingState from My self
viewedAs an Operation)
newVersion: SubsetOf(The structures from
a DescriptionState thatIs
the resultingState from My self
viewedAs an Operation)

# ServantInvocation

# DemonInvocation