Home

Paris Research Laboratory of Digital

1. 2 2 Examples In order to point out some of the difficulties in implementing functions let s assume the definitions below and the sort hierarchy in Figure 3 2A formal treatment of functions in LIFE can be found in 1 Technical Note No 18 December 1992 4 Seth Copen Goldstein Figure 3 A sample sort hierarchy incr X int X 1 incr X string increment insurance P person spouse gt S temp gt 1 insurance P person spouse gt S person gt 2 isspouse P person spouse gt S S person spouse gt P true If incr is called with an integer or string argument we get a result For example the answer produced follows the A incr 5 gt A 6 A incr hello A increment In addition to these obvious results if an argument to incr is incompatible with the formal definitions then it will result in failure A incr person failure The interesting case is where the argument in the function call is under specified i e its sort is neither incompatible nor a subsort of the formal argument For example A incr X A X X real A X real X 7 A 8 X 7 In this example X starts off being the top sort represented by the character so the function incr residuates on its argument When X is lowered to the sort real the function is awakened and because the sort of X is still to general again residuated When X is finally lowered to the integer 7
2. 32 residNil stash one two three maybeListl maybeList 1sList cFfail 0 jmp stash CFfail maybeListl CE gt body isNil CE gt residCount R1 tryAddSimple cF checkNil CE gt result RR CF gt 1 R1 CFL R2 ret CPTC List ret CPT car ret CPT cdr ret R1 cF gt 1 R2 CFL cFfail 0 CE gt body isListl R1CList one Rl car 1 two Rl cdr 1 three resid residList CF gt 1 R1 CF result RR R1 Rl cdr RR new Psi call reg_append December 1992 Seth Copen Goldstein If rule 1 residuates on the first pass we end up here to fixup the frame and to create the residuation Since rule 1 uses an explicit form of the subsort instruc tion we must create the residuation our selves Recheck subsort constraint for rule 2 Entry point if rule 1 resumes after resid uating and then fails Entry pointif rule 1 fails on the first pass Everything needed is in a register and the current frame may be uninitialized Since the frame may be uninitialized we must do some work before returning to caller if we are to residuate We did not residuate but we may never have stored anything in the frame so save what we need to Digital PRL An Abstract Machine to Implement Functions in LIFE 33 R2 new Psi List addfeature R2 car CE gt 1 car addfeature R2 cdr RR unify CF gt result R2 free CF pop CF ret isList1 R1 cF gt 1 Entry point if we suc
3. as X is equal to X and X f X as X is the feature of X We can always associate with an OSF term Y X s 1 gt Y1 ln gt Yn a corresponding OSF clause p 1 as follows dp X 58X X 8 8 XL X amp olp amp amp O n where Xj X are the roots of 1 Yn respectively We say that is obtained from dissolving the OSF term 4 For example the term in Figure 1 could be represented by four sort constraints X person F fred S person and M mary and three feature constraints X name F X spouse S S name M and S spouse X While an OSF clause is just a conjunction of the primitive constraints it can also be represented by a tree which shows how the individual constraints are related to each other Figure 2 shows the above term s constraint tree In LIFE the function call is represented by a term where the sort of the term is the name of the function being invoked and the arguments to the function are p terms connected to the root by features that label them as arguments For instance the function call append 1 2 3 4 5 is really shorthand for append 1 gt 1 2 3 2 December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 3 Figure 2 The Constraint Tree representation of the dissolved term 4 5 As will be seen later representing the function calls and function definitions as constraint trees leads to a nat
4. causing another residuation to fire Again the CF register is pushed checkPlus executed See Figure 15 for the state of the machine just before checkPlus is called and the intPlus routine finally called putting a 14 in D as expected The second frame returns popping the CF for the first frame The first frame returns popping the top level CF and then the code continues This example is contrived and given the above code a peephole optimizer should be able to rearrange this so no residuations occur 10 Detailed Data Structures and Routines This section describes the structure of the basic constraints needed to execute matching It defines the data structures auxiliary routines and abstract machine structure necessary to understand the execution of the constraints The definitions are presented in an object oriented fashion It is hoped that the definitions presented here can be turned into executable C code 10 1 The Three Basic Data Structures 10 1 1 The Psiterm This class defines the basic data structure used in the system that of the psiterm Each psiterm has a sort a set of features and a potentially null list of residuations attached to it class Psiterm Sort sort Features features Residuation rlist public return sort of this psiterm Sort sort December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 41 Return residuation for frame f if it doesn t exist create
5. we can eliminate building the term In the case of append the recursive call in the second clause can use registers instead of constructing a term Further compiler analysis can also check sort definitions to see if a term being built will not violate its theory In the trivial case this happens when the sort has no attached theory For append this results in the following optimizations applied to the second clause body isList R1 CE gt argl cdr R2 CF gt L RR new Psi call reg_append R2 new Psi List addfeature R2 car CF arg1 car addfeature R2 cdr RR unify CF gt result R2 free CF pop CF ret December 1992 R1 will get first arg to append Caller must establish the result term Execute recursive call and then the rest 1s the same Digital PRL An Abstract Machine to Implement Functions in LIFE 31 The above versions of append use only the implicit versions of the instructions While the implicit versions are more compact they also require more setup which means that for the simple case here more instructions are executed to establish a context than there are instructions in the head or body of the function Another defect with this code is that the common case the second rule is the slowest case To alleviate this problem the explicit subsort and residuation check instructions can be used Since the explicit instructions make no assumptions about what is in the current frame nothing i
6. written Ry Rx In other words the code presented here will not draw a clear distinction between the case where an assignment is sufficient and the case where a deref is necessary The compiler can make all assignments deref s or if a good optimizer is available can eliminate some deref operations in favor of simpler moves Ry Rx while Ry gt ref 0 Ry Ry gt ref endwhile PC PC 1 eval Rx ads Evaluate by Normalization evalfunc Rx evalpsi Rx Rx Rx points to a Y term The evaluation instructions cause a term to be made consistent If the term is a function call or a closure then the evaluation instruction will attempt to evaluate the term by executing the function based on the term s sort If the sort of the term is not a function then the evaluation instruction will enforce the sort definition on the term If there is no sort definition then the instruction is a nop This instruction is a full fledged interpreter and as such is very costly It is hoped that after compilation there are few instances of this instruction and that instead the unification matching and normalization that it implies has been encoded with by the other instructions presented here The general eval instruction makes no assumption about whether Rx is a function or a sort evalfunc assumes that Rx points to a term with a function sort evalpsi assumes that Rx points to a normal 1 term adr lookupSort Rx gt sort ca
7. 0 else RR new Psi endif Now execute function body PC PC 1 December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 23 else Must curry this function call C new Psi C addCurryResid Rx PC ref Rx C see the ref instruction ret endif endif resid Residuation Check resid residadr residadr residadr is the next address that will be executed if the frame has any residuations The Residuation Check instruction checks to see if CF residCount is zero or not If it is zero then the next instruction is executed If it is not zero then the implicit version resid will execute a ret instruction and the explicit version resid residadr will transfer control to residadr While both the implicit and explicit versions require that the CF register and CF gt residCount be initialized the explicit version gives the user a chance to perform any clean up that might be required if the function has residuated Pseudo code for the implicit version is if CE gt residCount gt O then ret else PC PC 1 endif Pseudo code for the explicit version is if CE gt residCount gt O then PC residadr else PC PC 1 endif 6 4 Body Instructions The instructions described in this section can appear in either the head or the body of a function or a predicate definition These instructions include both constraints and general purpose instructions Technical Note No 18 December 1992 24 Seth Copen
8. Copen Goldstein Psiterm Residuation feature set ly A cae E PR EgResidInfo Resume Address Figure 16 terms and their associated residuations after the execution of the first equality constraint Double lines represent features Single lines pointers Dotted lines pointers from one EqResidInfo to another December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 49 Psiterm Psiterm Residuation ptr to frame Residuation ptr to frame EgResidInfo Resume Address EqResidinfo Resume Address EgResidInfo Resume Address APsiterm eee ae eae AN Residuation ptr to frame ae Sa Psiterm AAA TT Residuation EgResidInfo EgResidinfo Resume Address ye A Sl Figure 17 The intermediate structures built during the execution of the second constraint Technical Note No 18 December 1992 50 Seth Copen Goldstein 10 2 4 Initialized Constraint See Page 20 for the pseudo code definition of this constraint void initialized Psiterm r psiterm we want are checking Code label address to goto on resumption Code skip address to continue at on residuation This is a funny constraint which is inserted by the compiler so that equality constraints can be cleaner It is called with a pointer to a psiterm in t
9. Goldstein AN Unify with Sort Rx Rx must point to a term s s is a sort defined in the sort hierarchy The instruction Rx s will succeed if it can set the sort of the term Rx to glb Rx sort s otherwise it will fail If the sort of Rx is lowered it will cause any residuations attached to Rx to fire s glb Rx sort s switch s case L PC CFA otherwise Rx gt sort s if Rx rlist then Rx lower endif endswitch PC PC 1 a daa Fetch Feature Ry Ry points to a term is a feature name The Fetch Feature instruction stores the term at Ry in register Rx It does a destructive store into register Rx If Ry does not have the feature then it will add the feature to Ry and attach it to a new term of sort T The act of adding a new feature will cause any residuations attached to Ry to fire if not Ry hasFeature then Ry gt addFeature new Psi if Ry gt rlist then Ry lower endif endif Rx Ry PC PC 1 addfeature Rx f Ry 2 0 c cece cece eee cece eee neeeeees Feature Creation December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 25 Rx Rx is a term without feature is a feature name Ry Ry is the term that will be pointed to by The Feature Creation instruction adds a new feature to term Rx This instruction is only valid when it is known that Rx does not have feature and when Rx has no re
10. Research Report 13 Digital Equipment Corporation Paris Research Laboratory June 1991 Revised November 1992 2 Hassan Ait Kaci and Andreas Podelski Towards a meaning of LIFE PRL Research Report 11 Digital Equipment Corporation Paris Research Laboratory Rueil Malmaison France 1991 3 Hassan Ait Kaci Andreas Podelski and Seth Copen Goldstein Order sorted feature theory unification 1992 4 Gerard Ellis and Peter Van Roy Constraints control compilation or how to compile matching and residuation in LIFE draft 1991 5 A Mari n and B Demoen A new scheme for unification in wam In 7991 International Symposium on Logic Programming pages 257 271 MIT Press Oct 1991 6 M Meier Compilation of compound terms in prolog In North American Conference on Logic Programming pages 63 79 MIT Press Oct 1990 Technical Note No 18 December 1992 PRL Technical Notes The following documents may be ordered by regular mail from Librarian Technical Notes Digital Equipment Corporation Paris Research Laboratory 85 avenue Victor Hugo 92563 Rueil Malmaison Cedex France It is also possible to obtain them by electronic mail For more information send a message whose subject line is help to doc server prl dec com or from within Digital to decprl doc server Technical Note 1 Wild LIFE a User Manual Hassan Ait Kaci and Richard Meyer being revised Technical Note 2 Wild LIFE an Implementation
11. an equality residuation additional work will occur only if there is a corresponding term involved i e it already has an EqResidInfo attached Thus for each frame in which a term has any residuations there will be one Residuation structure attached to the 4 term For each constraint in the same frame on which the w term residuated there will be either a ResidInfo ora EgResidInfo structure linked to the Residuat ion structure Forexample ifn terms were involved in n 1 equality constraints all of which residuated there would be n Residuation structures each attached to one of the n 4 terms In addition there would be n 1 pairs of EqResidInfo structures one for each constraint linking up the terms that were involved in the n 1 equality constraints 5 3 Resumption When a term is modified the unification routine will check to see if there are any residuations depending on the modified 4 term If there are then each residuation is executed in turn If any of the functions becomes satisfied then it in turn continues to execute In other words if during unification of a 4 term a function that was residuated on the term is enabled it will be executed immediately Thus the enabled function runs and either fails or completes before continuing with the code that caused the unification to happen in the first place 5 4 Currying If an attempt is made to execute a function without a
12. been seen before start A new Psi Create a new psi term for A B new Psi Create a new psi term for A RI A Get ready for a function call R2 B RR new Psi Create the result term call reg_plus C RR afterOne R1 5 Put sort for the integer 5 in R1 for second call R2 RR RR new Psi Create the result term call reg_plus afterTwo D RR lowerA AY Unify A with the integer 4 lowerB B S Unify B with the integer 4 After the execution of the first call from the label start until the instruction before label afterOne three w terms one frame and two residuations will have been created This is pictured in Figure 12 When the second call finishes right before the label afterTwo another Technical Note No 18 December 1992 36 Seth Copen Goldstein Toplevel Frame First Frame 7 ResidInfo asl Figure 12 The structures created by executing the first seven instructions of the example code December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 37 Toplevel Frame First Frame Second Frame ResidInfo La Figure 13 The structures created after the second call to the plus Technical Note No 18 December 1992 38 Seth Copen Goldstein Toplevel Frame First Frame Second Frame doPlus ResidInfo EA Figure 14 After A has been lowered and its residuation re
13. classify the arcs and nodes in such a way as to guide optimizations For instance in Figure 5 the solid arcs can be rearranged in any order while the dashed arcs are fixed It is also worth noticing that since the arity constraint is the same for all the clauses of a definition it might be inlined into the calling code so that terms don t have to be built for function calls Technical Note No 18 December 1992 8 Seth Copen Goldstein 4 Data Structures This section gives an overview of the data structures used in describing the LAM instruction set The basis of the machine is the representation of Y terms The class Psiterm defined here is used to express the parts of a term that concern matching December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 9 class Psiterm Sort sort the sort for this Psiterm Features features the features Residuation Pla ses residuations for this Psiterm Psiterm ref the dereference chain link hi sort is the sort that the term currently has The field features points to all the features in the term Its internal representation does not concern us here Any collection that supports fetching adding and testing the existence of a feature will suffice The most interesting field in terms of matching is the rlist field it points toa Residuation which is described below The ref field is used to implement dereference chains If it is not NULL then the te
14. constraint trees In Section 4 we present an overview of the data structures used for describing the algorithms that implement the functionality of LAM The mechanics of currying and residuation in particular for the equality constraint are described in Section 5 In Section 6 the actual register set and instructions of LAM are described in detail This is followed with some example LAM code in Section 7 Finally the nitty gritty details of the implementation are described in Section 10 1 2 terms A termis a generalization of record like data structures in traditional programming languages It is an extension of first order terms to include sorts and features For a coherent and complete discussion of terms the reader can see 2 Here I will briefly outline the notation A term or OSF term in normal form is of the form Y X s l1 gt Y1 la gt Yn where e there is at most one occurrence of a variable Y in such that Y is the root variable of a non trivial OSF term i e different than Y T e sis a non bottom sort in S e 1 f are pairwise distinct features in F n gt 0 e 1b1 Y are normal OSF terms The sorts of a term live in a lattice The least sort is bottom L the highest or most general is top T If a sort a is below another sort b then we say that a implies b a entails b a is more specific than b or equally that a is subsumed by b Thus all sorts are subsumed by T and L implies ever
15. s then PC Pc 1 else Create a residuation and attach it to Rx Rx gt tryAddSimple CF s recheckadr endif endswitch PC PC 1 Description of RxCs failadr residadr s glb Rx gt sort s switch s case PC failadr constraint fails otherwise December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 19 if s lt s then PC PC 1 constraint succeeds else PC residadr constraint residuates endif endswitch Rx Feature Existence Rx residadr Rx residadr recheckadr Rx Rx must points to a term l l is a feature name residadr residadr is the next address that will be executed if the constraint residuates If residadr is not present in the instruction then its value defaults to the subsequent instruction in the program text recheckadr recheckadr is the address of the re evaluation routine If recheckadr is not present its value defaults to the current PC The Feature Existence instruction tests for the existence of a feature in the term in Rx If the feature exists then the instruction succeeds and the next instruction is executed If the feature does not exist then the instruction residuates and continues execution at residadr The residuation created will restart execution at recheckadr if Rx is ever modified A possibly more optimized LAM would have a more complex feature existence constraint Instead of creating a simple residuation which will be run when
16. 18 An Abstract Machine to Implement Functions in LIFE PARIS RESEARCH LABORATORY 7 December 1992 Seth Copen Goldstein PRL TECHNICAL NOTE 18 An Abstract Machine to Implement Functions in LIFE Seth Copen Goldstein December 1992 Publication Notes This work was done during the author s three month internship at Digital Equipment Corpora tion s Paris Research Laboratory Digital Equipment Corporation 1994 This work may not be copied or reproduced in whole or in part for any commercial purpose Permission to copy in whole or in part without payment of fee is granted for non profit educational and research purposes provided that all such whole or partial copies include the following a notice that such copying is by permission of the Paris Research Laboratory of Digital Equipment Centre Technique Europe in Rueil Malmaison France an acknowledgement of the authors and individual contributors to the work and all applicable portions of the copyright notice Copying reproducing or republishing for any other purpose shall require a license with payment of fee to the Paris Research Laboratory All rights reserved Abstract This note outlines the Life Abstract Machine LAM an abstract machine used as an inter mediate target for the efficient compilation of LIFE LAM focuses primarily on the efficient implementation of matching residuation and currying of functions Although the topic is not discussed in this note LAM a
17. 5 Obvious instructions The following instructions are used in the examples and should be obvious Lin Sieg eee bea Aia Free Heap Allocated Storage e TOO Qe Uo de RE he Oe e MEA da Push onto the Stack SP Rx SP SP 1 A id ad des Pop from the Stack SP SP 1 Rx SP RT Return from Subroutine SP SP 1 PC SP Technical Note No 18 December 1992 28 Seth Copen Goldstein Call destad Pili i6i ee i She dana Call Subroutine SP PC SP SP 4 1 PC destadr jp destadr vta di paa a a aa da Unconditional Branch PC destadr 7 Example LAM Code This section illustrates how LIFE functions are compiled for the LAM It uses append as an example function First it presents a simple term based function definition Next it optimizes the code to use registers for the recursive call Finally it explores how the explicit versions of certain instructions can substantially reduce overhead We will first explore an example using the append function in Section 8 Then in Section 9 we will show how the mechanism of resumption works 8 The Append Function append L gt L append H T L H append T L In general an n rule function in LIFE is compiled into 2n 2 sections The first section is the term entrance to the function It consists of an arity instruction followed by the instructions to deconstruct the term into registers The next section is the frame building section It allocates a fr
18. Boolean isBottom void return the greatest lower bound of the sorts defined by a and b friend Sort glb Sort amp a Sort amp b Je 10 2 The Head Instructions In this section the C code for the basic head instructions listed in Section 6 3 1s presented Each constraint is listed using the data structures and routines presented above In some sense this code represents the macros that would be inlined into a LAM function definition The code uses three macros to guide the flow of control in the abstract machine CONTINUE FAIL and SKIP_TO The CONTINUE macro has essentially the same meaning as PC PC 1 in the pseudo code presented in Section 6 3 In these macros it means execute the code after the end of the current macro The FAIL macro is like the headfail macro Finally SKIP_TO skip means to restart execution at the instruction labeled skip These macros imply a certain compilation regime that the entire function head will be encapsulated in a single C function Thus both the SKIP_TO and CONTINUE macros become local gotos and the FAIL macro becomes a return statement If the function returns the address of the next c function to execute then on failure a fail routines address can be returned on success the next LIFE function routine s address can be returned 10 2 1 Sort Constraint See Page 17 for the pseudo code definition of this constraint void subsort Psiterm amp r psiterm that we are testing Sort
19. Manual Richard Meyer being revised Technical Note 3 Characterising Perle0 Alan Skea October 1990 Technical Note 4 Perle1DC a C Library for the Simulation and Generation of DECPeRLe 1 Designs Herve Touati February 1994 Technical Note 5 TiGeR Version 1 0 User Guide Olivier Coudert Jean Christophe Madre and Herv Touati January 1994 Technical Note 6 Tgr Version 1 0 Reference Manual Olivier Coudert Jean Christophe Madre and Herv Touati August 1993 Technical Note 7 Compiling Order Sorted Feature Term Unification Hassan Ait Kaci and Roberto Di Cosmo December 1993 Technical Note 8 Compiling LIFE Richard Meyer December 1993 Technical Note 9 Riviera Class Library Reference Manual Didier Martineau and Thierry Pudet May 13 1994 Technical Note 10 Riviera Data Library Reference Manual J r me Barraquand Didier Martineau and Thierry Pudet May 10 1994 Technical Note 11 Riviera Pricer Library Reference Manual J r me Barraquand Didier Martineau and Thierry Pudet Apr 21 1994 Technical Note 12 Riviera Wrapper Library Reference Manual Didier Martineau Thierry Pudet Apr 14 1994 Technical Note Sep 15 1993 Technical Note 28 1994 Technical Note 1994 Technical Note Technical Note 13 14 15 16 17 Riviera Documentation Extractor Reference Manual Didier Martineau Riviera Mathematical Library Reference Manual Didier Martineau Mar Riviera Visualization Tool R
20. See Figure 10 for the various possibilities The Subsort Constraint instruction has an implicit and explicit version The implicit version is RxCs_recheckadr If recheckadr is not specified then it is set to the current PC The explicit version is RxCs failadr residadr Both the implicit and explicit versions check to see if the sort of Rx is compatible with s without altering Rx in any way If it is compatible then the next instruction executed is the subsequent one in the function definition The two versions differ in how they handle residuation and failure If the instruction residuates the implicit version will create a sort residuation which will be attached to Rx and will resume at recheckadr The explicit version will transfer control to residadr It will not create any residuation structures nor will it increment the residCount in the current frame Technical Note No 18 December 1992 18 Seth Copen Goldstein Residuates ia oe Seer eat eae os EE E EEEE i EEEE ae e Poca Figure 10 Different regions of sort intersection If the sort of Rx and s are incompatible then the implicit version will execute the headfail macro The explicit version will transfer control to failadr Description ofRxCs recheckadr s glb Rx gt s0rt s switch s case headfail otherwise if s lt
21. ame and stores necessary information into the frame Finally for each rule a head section is followed by a body section In the following non optimized version of append the first section starts at the label append which contains the arity constraint and the deconstruction instructions The frame building section begins at the label reg_append The first clause s head is only two instruction long They are right before the label isNil The body of the first clause is the 5 instructions following isNil The second clause s head starts at maybeList and its body starts at isList In this version of append no special attempt is made to use registers instead it builds a term for the recursive call to itself The frame definition for append is as follows class Append public Frame Psiterm argl pointer to argument 1 Psiterm L pointer to argument 2 y December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE append cpT 1 2 R1 CPT 1 R2 CPT 2 ref CPT RR reg append push CF cF new Frame append CE gt body isNil CF gt ofail maybeList CF result RR CF gt argl RI CF L R2 R1C zero resid isNil cF gt fail 0 unify CF result CF gt L free CF pop CF ret zero cPTC ret one CPTC List ret two CPT car ret three CPT cdr ret maybeList CF body isList cF fail 0 R1 cFargl R1CList one Rl car 1 two Rl cdr 1 three Technical No
22. any feature or sort of the term is changed it could be create a residuation which will only be executed when the particular feature mentioned in the constraint is added the the term I have ruled out this more efficient instruction in LAM to keep the residuation structures smaller and more concise It is not clear whether having the specialized feature residuations would improve efficiency since whenever a feature is added it would still be necessary to check whether the added feature participates in a residuation If LAM is oriented to more efficiency in the case of feature constraints it might instead be better to investigate the possibility of actually adding the feature when the constraint is executed The added feature could point to a term which has sort top and has a residuation attached that would have to perform a special check related to currying of the original term If unification is performed on the original term no problems are introduced However if matching is performed on the 4 term some special mechanism would have to be used to ensure that the ghost feature added by the constraint was not matched since if it were curried functions would not behave correctly I chose the simple route and instead have feature constraints residuate on the top level term if Rx hasFeature 1 then Technical Note No 18 December 1992 20 Seth Copen Goldstein PC PC 1 else Rx gt tryAddSimple CF recheckadr PC r
23. cation of order sorted feature terms 3 In addition by showing a possible approach to successfully compiling away the overhead of matching and residuation in LIFE it should be a good starting point to the creation of the actual LIFE compiler Technical Note No 18 December 1992 54 Seth Copen Goldstein A Instruction Summary ReGS AA lata Subsort Constraint RxCs recheckadr RxCs failadr residadr RAG A casa AE Feature Existence Rx f residadr Rx f residadr recheckadr Re Ry A dad Equality Constraint Rx Ry recheckadr MANISES Initialized Constraint X residadr recheckadr RA O ds O aldo As i ea Arity Constraint resid asi a ao Residuation Check resid residadr Rita aie ewe ean oa AS Unify with Sort Ree Ryle tee se a a tad peers aes Fetch Feature addfeature Rx f RY cece ccc eee eet een rnnr rro eeeees Feature Creation Re Ryo ah eis pau sia Jala ee kel See ei eda date Rade thks daa General Unify unify Rx Ry ref Re Ryanin ahed tune A hells th tee ass Create Reference Link deref Rx RY iis ea hoes ee pda Retrieve a Dereferenced term SS ks isa wleie eteina i iani meee aad Evaluate by Normalization evalfune Rx evalpsi Rx MewPsi 0 Hebe be SN ds Heap Allocation new Psi s new Frame name new SortResid recheckadr Rx Ry December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 55 References 1 Hassan Ait Kaci and Andreas Podelski Functions as passive constraints in LIFE
24. ceed after residu ating R2 CF gt L jmp isList This version of append is significantly harder to read than the previous versions for two reasons First the code is organized so that the most common case requires the fewest jumps Thus all the interesting but hopefully rare cases involve many jumps Second one must keep in mind the different states that the frame can be in to determine which code is executed In general the compiler will need to provide code for two different states initial entry and resumed entry For instance in this code the second clause can be entered in one of three ways failure of the first clause in the first pass failure of the first clause after it residuated or residuation of the second clause In the first case the flow of control passes though reg_append and then to maybeList via the explicit subsort constraint In this case none of the frame has been established In the second case the flow of control passes through reg_append residNil because the explicit subsort residuated checkNil when the frame was resumed maybeList1 because the constraint in checkNil failed and the fail of the field was set to maybeList1 in residNil In the second case the frame has already been initialized In the third case the frame also has been initialized The flow of control is reg append maybeList residList one of the resumed labels one two or three and then finally isList1 9 The Plus Function In order
25. e function call but rather will add arguments to the call For example A incr A X A extra gt 2 X A 6 extra gt 2 X 5 A incr A 1 gt X 0 A extra gt 2 X 5 cme ie CR In this series of queries A is first set equal to the curried function incr then the first and only argument is unified with A and then A becomes the result of the function call which has residuated on X An extra feature is then added to the result of the function call Finally X is lowered and the function completes Notice that the order of the second and third line cannot be changed because in the second query A represents the call and in the third it represents the result 3 Representing Function Definitions as Constraint Trees In order to obtain the behavior described above this note proposes a compilation scheme based on decomposing function definitions into function trees where each clause of the function is represented by a constraint tree gt The idea of using executable constraints was found in 4 December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 7 S Clause Tree Arity Constraint Y oo rN rguments f Tee oy Yj V s Y Y y Figure 5 Tree representing an m clause n ary function definition Each function is defined by a possibly unit series of clauses Each clause is tried in turn until either all are disentailed or one is entailed If a particular clause res
26. eference Manual Didier Martineau Fev 18 Riviera Utility Library Reference Manual Thierry Pudet May 13 1994 Riviera Leak Library Reference Manual Thierry Pudet May 13 1994 Technical Note 18 An Abstract Machine to Implement Functions in LIFE Seth Copen Goldstein December 1992 PARIS RESEARCH LABORATORY 85 Avenue Victor Hugo 92563 RUEIL MALMAISON CEDEX FRANCE UIa SpjOD UsdoD yles 3417 ul suonouny jueua dui 0 sulyoey 198 11SQY uy Q L
27. ending in adr refer to addresses in the code space otherwise an italic name is a generic label Feature names are represented by and sort names are represented by s Each instruction is followed by an informal description and pseudo code that describes its function The pseudo code will often refer to data structures and routines defined in Sections 4 and 10 Whenever an instruction operates on a 4 term it is assumed that the term has already been dereferenced at the time it is fetched In the descriptions of the instructions the phrase the term Y or if the context is clear just Y is understood to mean the term that is at the end of the reference chain from the term pointed to by Y As LAM instructions are already fairly high level no real constraints are placed on the addressing modes that the operands may use unless otherwise specified The three basic modes used here and in the examples are register register offset and memory The register offset mode is represented by writing R offset Notice that this is distinct from R f which retrieves the term reached by following the feature from the term pointed to by R The instructions are broken down into two categories head instruction and body instruction The head instructions are those instructions that can only appear in function heads The distinction between head and body instructions are between those that modify terms and those that do not Head instruction
28. esidadr endif Rx Ry Equality Constraint Rx Ry recheckadr Rx Rx points to a term Ry Ry points to a term recheckadr recheckadr is the address of the re evaluation routine If not present in the instruction it defaults to the current PC The Equality Constraint instruction checks to see if Rx and Ry are the same dereferenced pointer to a term In other words it succeeds if Rx and Ry have been unified If they are the same term then the constraint succeeds and the next instruction is executed If they could become the same 4 term in other words if they could be unified then the constraint residuates and the next instruction is executed If they are inconsistent then the headfail macro is executed All of the real work performed by this instruction is contained in the canUnify routine see Section 10 2 3 which will either create a residuation and return or execute the headfail macro The CF register and CF fail must be set before this instruction can be executed if Rx4 Rythen canUnify Rx Ry recheckadr endif PC PC 1 X Initialized Constraint X residadr recheckadr residadr residadr is the next address that will lt be executed if the constraint residuates If residadr is not present in the instruction then its value defaults to the current PC 2 recheckadr recheckadr is the address of the re evaluation routine If recheckadr is not present its value defaults to the current PC The nitialized Con
29. field of the residuations for the term in R1 is set to b Second note that there are no residuations attached to the term attached to R1 gt y When the second constraint is executed the canUni fy routine will be invoked on the terms pointed to by registers two and three rx will point to the residuation for R2 in Figure 16 The test hasEqResidWith will fail since no equality constraint yet exists between the second two terms Next a new residuation will be created attached to the R3 4 term and assigned to ry The best known sort computed for these terms will be bc However when the setsort routine is executed for rx it will find another residuation already attached thus it will check all the attached residuations to make sure that the new sort bc does not cause any disentailment The structures that result at this point in the execution are shown in Figure 17 After the new EqResidInfo structures have been added canUni fy is called recursively on each pair of term that can be reached by the features in common to both of the original terms In this case the only common feature is x Since there is no equality constraint for this frame between R2 x and R3 gt x the best sort will be computed in this case it results in failure since ab N c is bottom Technical Note No 18 December 1992 48 Residuation EgResidInfo Resume Address TA Residuation EgResidInfo Resume Address E Seth
30. fore the residuation is created the sort of the term is also compared to the sort field in the Residuation structure If they are incompatible then the function definition is disentailed Technical Note No 18 December 1992 12 Seth Copen Goldstein In this manner information about equality between the actual arguments is maintained even though the arguments themselves cannot be modified during the matching phase The three simple constraints subsort feature existence initialized each create a ResidInfo which is attached to the corresponding Residuation object for the term and frame involved The equality constraint on the other hand must create a structure so that if either object in the constraint is modified then the constraint will be re executed Further if either of the terms involved in the equality constraint contains subparts that cannot be unified then the constraint must generate a failure This added complexity is handled by having the constraint traverse both terms adding EqResidInfo objects to all common children For example in Figure 8 the terms attached to the features in common to A and V must each be checked to see if possible conflict yielding failure or possible unification yielding more EqResidInfo structures results also see the example on Page 47 Notice how each pair of corresponding terms involved records the sort of their intersection Further if a new feature is added to a term involved in
31. he frame If the frame slot has not been filled in because a subtree was never executed due to some other constraint residuating then the slot will be NULL If the slot is NULL then we create a psiterm in the slot with TOP as its sort and residuate if r CONTINUE T GI Create a new dummy psiterm It will get unified with the psiterm inserted into the frame slot which will kick off this computation r new Psiterm TOP r tryAddSimple CF TOP label SKIP_TO skip 10 2 5 Check Residuation Count Instruction See Page 23 for the pseudo code definition of this constraint void resid void Check to see if this frame has any residuation If it does then we return from this frame s context and continue at the point after the call to this function was made if CF gt hasResids RETURN Let s execute the function CF gt execute 10 3 Auxiliary Functions and Class Implementations void Psiterm tryAddSimple Frame f Sort s Code label December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 51 Residuation resid resid findResid CF Get the residuation for the current frame CF It will be created if necessary Make sure that the residuation that is already attached to this psiterm doesn t have a sort conflicting with s Also update the sort in the residuation to reflect the fact that this psiterm will fi
32. he function references across suspension or residuation points is kept in the frame The class frame describes the common structure that every frame must have Each function will create a new subclass of frame which will add all the variables needed in order to execute the function The class Frame describes the minimum structure that every function will create when itis executed Each particular function will define its own additional fields i e variables needed to execute the function and inherit all of the class Frame s variables and methods class Frame Technical Note No 18 December 1992 42 Seth Copen Goldstein int residCounter counts number of residuated variables Code body address of body of function Code fail the address to goto if a fail is executed Psiterm result result of function gets put here public increment and decrement the residuation counter void incrResiduation void decrResiduation returns residCounter to indicate whether or not this frame has any residuations attached to it void hasResids when this function is called then all residuations have been checked and the function is ready to go void execute y An example frame definition It inherits from Frame and defines two of its own variables class SomeFunction class Frame Psiterm VO Psiterm V1 10 1 3 The Residuation A residuation is a structure conta
33. heory unification was a truly enlivening process Finally I want to thank Deborah for well everything Contents 1 8 9 Introduction TE AOVERVIOW iaf arras Ge hc e A ant Bhan a Bow We AO terse taa a a E Matching Zeki Definition and a ande Fee a 22 HEXAMpleS ao oars a Sie eee ee Se awe ee See S 2 3 Introduction to Currying oie eg oop ake Oka dae Representing Function Definitions as Constraint Trees Data Structures The Mechanism Behind the Machine 5 1 The Phases of a Function Call 5 2 Residual on ot 8 aE ane an Bea ace Wea are a ere SOS G3 HeSumpllo sais ehh he e e 54 A A aed ae wt Bae LAM The Life Abstract Machine 6 1 The LAM Register Set o 6 2 The LAM Instruction Set 6 3 Head Instructions eens 6 4 Body Instructions o e 6 5 Obvious instructions Example LAM Code The Append Function The Plus Function 10 Detailed Data Structures and Routines 10 1 The Three Basic Data Structures 10 4 1 TRE PSIHELMN oi A ee BO A 1031 27 Th Fram as on Shee EBD Ae Re we hg Mo ge a A 10 1 3 The Residuation sssr i ro miie tiara i ee es 101 4 The Sort serino A ee E a a a N G 10 2 The Head Instructions 10 2 1 Sort Constraint aoaaa o 10 2 2 Feature Constraint 0 aaa 10 2 3 Equality Constraint aaau 10 2 4 Initial
34. iduates then it is only when 1t is disentailed that the remaining clauses are tested Each function head or clause is compiled into a series of constraints In this note the individual clauses are joined together into a complete function definition in the most basic way serially through the use of the failure mechanism It is expected that optimization techniques can be performed on the individual clauses to create a more efficient conglomeration One way to view a function definition is as a tree The root of the tree will hold an arity constraint which succeeds iff the actual function call has the same number of arguments as in the definition The function represented in the tree in Figure 5 is an n ary function The children of the arity constraint node represent each clause in the function definition The clauses are ordered from left to right Each clause then has n children representing the constraint tree needed to do the matching for each of the n arguments of the function These constraint trees are created by dissolving the terms that represent each argument in the clause It is similar to the constraint tree in Figure 2 When a failure is detected then control is transferred to the next clause node in the tree The advantages in viewing a function definition this way are many First the wavefront algorithm 4 6 5 as implemented in this note treats the constraints on the arguments as if they were arranged in a tree Second one can
35. ing is different in that it doesn t re create the toplevel residuations since they already exist canReUnify CPT other void Frame execute This function is only called when there are no residuated terms assert residCounter 0 we have committed to a particular definition of the function A failure now resorts to the general failure trailing mechanism fail NULL establish the result psiterm RR result start execution SKIP_TO body December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 53 11 Conclusion Although compiling LIFE a very rich and powerful language into native machine code appears daunting LAM is a lever which makes the task feasible This note outlines LAM and the mechanisms which give LAM the power to operate on LIFE structures easily and efficiently It has been our experience that getting the architecture correct with respect to residuation and entailment has not been difficult However getting disentailment to work correctly has proved elusive In particular equality constraints pose a hard problem LAM handles the case of an equality constraint in the function head with minimal overhead However we need to extend the model slightly to handle special cases of equality introduced by the function call In spite of this shortcoming LAM has led to valuable insights about LIFE It has pointed the way towards the correct handling of lazy unifi
36. ining all the information about functions that depend on psiterms on which they are residuated A residuation identifies the function depending on the psiterm the best known sort for the psiterm i e the glb of all the formals in the function definition that this psiterm is participating in and a list of addresses that should be executed if the psiterm is ever changed class Residuation Frame parent frame of function to be activated Sort sort the best known sort for this term i e the glb of all formals and all actuals linked by equality contraints Residuation next next residuation for this var ResidInfo info info about each resid for this parent public Compare the sort in this residuation and s If they are incompatible then execute FAIL Otherwise set sort to glb sort s boolean compatibleWith Sort s December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 43 create a ResidInfo and attach it to the list of already created residInfo s for this psiterm void addSimpleResid Code label return best known sort 1 e return sort field Sort sort set the sort field to s If s is different than the current value of the sort then the best known sort for this psiterm has been changed and we should pretend the psiterm has been lowered void setSort sort s returns true if y has an equality residuation in frame f with the recei
37. ion and failure On the other hand the explicit version will transfer control to an explicitly named address if either residuation or failure occurs so that nothing needs to have been preset in the current frame The implicit versions of the instructions will invoke the macro headfail if a failure occurs This macro will check cF fail If CF fail is nonzero then control will be transferred to CF fail otherwise control will be transferred to the address in CFA This is the mechanism used to handle multiple rules in a function definition The pseudo code for the macro headfail is headfail if cr gt fail 0 then PC CF gt fail else PC CFA endif RxGs Subsort Constraint RxCs recheckadr RxCs failadr residadr Rx Rx must points to a term s s is a sort defined in the sort hierarchy recheckadr recheckadr is the address of the re evaluation routine failadr failadr is the next address that will be executed if the constraint fails residadr residadr is the next address that will be executed if the constraint residuates The Subsort Constraint instruction determines if the sort of Rx is a subsort of s There are three possible outcomes for this instruction success failure or residuation If Rx sort is subsumed by s then this constraint succeeds If the Rx gt sort A s is L then the instruction fails If neither of these occur or in other words Rx sort neither entails or disentails s then the instruction residuates
38. it Residuation findResid Frame f If s is compatible with best known sort for this psiterm then add a simple residuation that will continue at label for frame f boolean tryAddSimple Frame f Sort s Code label Return a the list of features that is the intersection between fset and this psiterms features list Features intersect Features fset Add feature with attached psi term p void addFeature Feature 1 Psiterm p return true if this psiterm has the feature boolean hasFeature Feature 1 get the psiterm that is pointed to by feature f Psiterm get Feature f this Psiterm has been lowered so if it has any residuations they must be executed void lower Add a residuation that will invoke the handleCurry routine if anything is ever unified to this psiterm The original function call psiterm is specified by orig The function to be invoked is func void addCurryResid Psitermg orig Code func return true if X and Y are unifiable Also set up the structures that will ensure they remain compatible or a failure takes place friend boolean canUnify Psiterm amp X Psiterm Y y 10 1 2 The Frame The name for this class was chosen to evoke the image of a stack frame used to execute a function However since residuations can cause functions to execute in a non stacklike manner they cannot be allocated on a sequential stack Everything that t
39. ized Constraint aaaea aaa aaa 10 10 11 12 12 14 15 15 16 23 27 28 28 33 10 2 5 Check Residuation Count Instruction o o 10 3 Auxiliary Functions and Class Implementations 11 Conclusion A Instruction Summary References 53 54 55 An Abstract Machine to Implement Functions in LIFE 1 1 Introduction 1 1 Overview This note outlines the Life Abstract Machine LAM an abstract machine used as an inter mediate target for the efficient compilation of LIFE LAM focuses primarily on the efficient implementation of matching residuation and currying of functions Although the topic is not discussed in this note LAM also implements lazy unification LAM should be viewed as an intermediate target for compiling LIFE to a native instruction set for a general purpose processor Thus this note presents LAM as an abstract machine along with its instructions However we also discuss how LAM would be realized in terms of data structures and basic routines This should facilitate the implementation of both a LIFE to LAM compiler and a LAM to native code compiler While this document is intended to be self contained it is assumed that the reader is familiar with at least the informal parts of 2 After presenting the basic properties of terms we give a brief of description of matching residuation and currying in Section 2 Section 3 explains how function definitions are decomposed into
40. ll adr December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 27 new Psi Heap Allocation new Psi s new Frame name new SortResid recheckadr Rx Ry s s is a sort name name is the name of a function recheckadr recheckadr is the address of the re evaluation routine Ry Ry is the term that residuated The Heap Allocation instructions allocate storage from the heap new Psi s will allocate a new term with sort s and no features If s is not present it defaults to top new Frame name allocates a new frame for the function name It will also set every slot in the frame to 0 It is assumed that the compilation process will create a routine for allocating a new function frame for each function It is this routine that will be invoked when the new Frame routine is executed A more general way of looking at this would be to say that for every sort a routine is created that will handle its allocation and initialization For general sorts this will allocate some space and set the sort to top One could imagine that if a sort definition were present for the sort then this routine would also execute the code in the definition For sorts that represent functions this code would allocate the frame and initialize it new SortResid recheckadr Rx Ry allocates a new sort residuation which will resume at recheckadr The residuation will be for the frame pointed to in Rx and it will be attached to the term Ry 6
41. ll of its arguments then the function will curry and return At a later time the extra arguments may be unified with the function call and then the function will execute As currying is not a common occurrence we strove to Tt was recently noted that storing the sort in and of itself is not sufficient to provide complete disentailment For instance assume the function definition f s a s b gt 1 Ifa Abis L then the call f X X should fail However since our model only compares the sorts of residuated terms it will not cause failure This can be fixed by following the model of the equality constraint December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 13 third t The EqResidInfo structures that would be created by executing the equality constraint on terms A and V Figure 8 The additional structures that would be added if the third feature were added to term A Technical Note No 18 December 1992 14 Seth Copen Goldstein esiterm a function eae ama Residuation Figure 9 This figure shows the result of executing the arity constraint when the function needs to be curried allow currying without increasing the cost of doing general operations like unification This is achieved by treating currying like residuation If a function curries a new 4 term called a curry term will be created with sort top and no features The curry term will have an a
42. lso implements lazy unification LAM should be viewed as an intermediate target for compiling LIFE to a native instruction set for a general purpose processor Thus this note presents LAM as an abstract machine along with its instructions However we also discuss how LAM would be realized in terms of data structures and basic routines This should facilitate the implementation of both a LIFE to LAM compiler and a LAM to native code compiler Keywords Logic programming inheritance functional programming constraint logic programming object oriented programming abstract machine execution model constraint implementation feature structures LIFE Acknowledgements Working at PRL has been a great experience and I want to thank everyone at the lab for a summer full of learning and fun In particular I want to thank everyone in the LIFE group for keeping me on my toes teaching me new things and tolerating my bad French I have special thanks for Peter Van Roy my advisor at PRL Besides introducing me to LIFE and stimulating me with more ideas than I could digest he kept me on course Without his support and careful and continual reviews this note and the work it contains would not have been completed In addition to working with Peter it was a true pleasure to work with Hassan Ait Kaci and Andreas Podelski Between the two of them I learned a great deal about the theoretical nature of LIFE Working with them on order sorted feature t
43. moved December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 39 Psiterm STACK First Frame Toplevel Frame Residuation Second Frame ResidInfo pra Figure 15 The structures and stack after the first frame has fired but before the second one has fired Technical Note No 18 December 1992 40 Seth Copen Goldstein term frame and residuation will be created see Figure 13 Note that in executing the second call the first subsort constraint succeeds but the second one testing the sort of C residuates At this point both result terms have sort top and neither of the functions have fired Next the term A will be lowered to the integer 4 This causes the residuation attached to A to fire The result is that the current Frame is pushed on the stack the CPT register is set to A and the code at checkPlus is executed After this returns the residuation attached to A will be removed and the the residCount attached to the first frame will be lowered to one See Figure 14 Finally B is lowered This will cause checkPlus to be executed with CF pointing to the first frame All the residuations will have been removed and thus the execute function See Page 52 will invoke the first frame When the first frame executes it will unify the sorts between RR which is top and R3 which contains a 9 The result is a lowering of RR which is also the term D
44. n has only one clause Execute the add primitive and put the result a term into R3 Unify the resulting number with the re sult P term Compiler analysis should do better here since we know intPlus re turns a term that has no features and RR is a null term Save current value of CF Since the frame is now all set and we know we are residuating already use an implicit subsort constraint for second argument Digital PRL An Abstract Machine to Implement Functions in LIFE 35 checkPlus CPTCint Recheck sort constraint ret doPlus R1 CF gt one R2 CF two RR CF gt yresult R3 intPlus R1 R2 Execute the add primitive and put the result a 7 term into R3 unify RR R3 Unify the resulting number with the re sult term pop CF ret The above function has two additional places for optimizations than the append function First both arguments have the same sort constraint so only one resumption address is needed checkPlus Second in the case that no residuations occur which is the common case no frame needs to be created either Thus we see that the CF register is not pushed nor is a frame created unless a residuation occurs see labels residFirst or residSecond Armed with the above definition for plus lets see what happens for our example LIFE code A B C A B D C 5 A 4 B 5 The compiled version of this code is as follows We assume that none of these variables has
45. n the frame needs to be set up before executing the head of the function Thus if the function does not residuate no extra work will be performed in setting up the body fail or result fields of the frame Notice also that more registers are used as a result of this compilation approach The extra overhead involved when a function residuates is smaller than it appears here because on a RISC processor everything would have to be loaded into registers anyway Furthermore some of the work that is made explicit here was actually happening behind the scenes in the definitions of the implicit instructions append reg_append 1sNill 1sNil checkNil residList CPT 1 2 R1 CPT 1 R2 CPT 2 ref CPT RR push CF cF new Frame append R1C maybeList residNil unify RR R2 free CF pop CF ret RR CF gt result R2 CF gt L jmp isNill cerc ret CE gt body isList1 Technical Note No 18 1V term entrance to function Save current value of CF Create a new frame All values are set to 0 by allocator Explicit subsort constraint will only continue to next instruction if it suc ceeds So no resid is needed We can assume everything needed is in a register and CF fail is already set to 0 Entry point for body if came back from a residuation Must setup registers Recheck sort constraint from rule 1 If rule 2 residuates on the first pass we end here to fixup the frame December 1992
46. nally end up with a sort which is lt to s if resid gt compatibleWith s FAIL everything is ok so far so add label to the list of addresses to be resumed when the psiterm is lowered resid gt addSimpleResid label lower is called only if there are any residuations attached to this Psiterm and the Psiterm has been lowered void Psiterm lower Residuation r save current environment on stack push CPT push CF match down rlist invoking every ResidInfo that we encounter CPT this set the CPT register to point to this Psiterm foreach r rlist restore current environment r gt lower pop CF pop CPT The lower routine for class Residuation will activate all the rinfo s for the frame of this residuation It assumes that the CPT register has been setup void Residuation lower Technical Note No 18 December 1992 52 Seth Copen Goldstein ResidInfo todo CF parent establish the current frame foreach t todo t gt resume execute this ResidInfo now lets see if we can execute the function if CF gt hasResids CF gt execute void ResidInfo resume SKIP_TO address void EqResid resume if CPT other CF gt decrResiduation SKIP_TO address else just like a call to canUnify but the book keep
47. nstead pass features not in the set of argument names to the result 4 term It is not apparent how such a lenient approach could be implemented efficiently If on the other hand the features in Rx are a subset of 2 n then the instruction will curry Rx and return to the caller A term is curried by creating a reference link between Rx and a new term with sort top A special residuation called a handleCurry residuation will then be attached to the new 4 term In general the Arity Constraint is the first constraint executed at the head the matching code for a function It is used to handle the case when the compiler cannot figure out what function will be invoked at compile time and instead must build a complete 4 term before the function can be invoked Following the arity constraint will be code that will deconstruct the w term placing arguments in registers etc see Section 5 1 If on the other hand the compiler can determine the function being called then it can place the arguments into registers as specified by some mapping of features to registers and start execution of the function after the Arity Constraint and the deconstruction code if Rx features 41 fo 0 then headfail Rx has too many arguments else if Rx features N 1 2 then constraint succeeds setup result term if Rx gt ref 0 then This function had previously curried RR Rx gt ref Rx gt ref
48. nting the function call is deconstructed and the execution of the function passes into the matching phase otherwise the function call is curried and immediately returns The deconstruction of a term is just placing the arguments into registers by tracing the features from the original function term When the function has passed into the matching phase a frame will be allocated to the function Every function will have frames with at least the structure described above for class Frame In addition the frames will have fields for any variables that are manipulated in the function In the matching phase the constraints that result from the function definition are executed in order to find the clause of the function definition If any constraint fails then the next clause is tried until no clauses remain at which point the function invocation fails If any December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 11 residCouner body fail Matching Code result For the Function constraint constraint Body code Result for the Function e Argument Residuation ResidIinfo ResidInfo Figure 7 Schematic representation of a term with two residuations attached for the same function invocation address clause completes with success and none of the constraints have residuated then the clause that matched enters the execution phase and executes the body of the function If a con
49. programs It includes mechanisms that directly facilitate the compilation of LIFE features This section describes the registers and instruction set of LAM While a complete abstract machine would have to implement all LIFE functionality i e residuation unification choice point handline etc LAM and this document focus primarily on the mechanisms needed to handle function calls and residuation December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 15 PC Program Counter SP Stack Pointer Rn General purpose register Rn There are an unlimited number of general purpose registers They can each hold a pointer to a term an integer or any other basic data type They are denoted as the letter R followed by a number e g R8 CFA Current Fail Address The CFA register holds the code address to jump to if a unification operation fails CF Current Frame The CF register contains a pointer to the frame of the function currently executing CPT Current term The CPT register by convention points to the root of the term being operated on RR Result Register The RR register points to the term that the last function returned It is only used when arguments are passed in registers Table 1 The LAM register set 6 1 The LAM Register Set In addition to general purpose registers LAM includes registers used to control the process of unification and matching All of these additional registers are used as poin
50. quality Constraint instruction M L in Figure 11 has no meaning Thus we introduce the Initialized Constraint instruction L into the tree in Figure 11 If it residuates the M L Equality Constraint will be skipped if X 0 then X gt try AddSimple CF recheckadr PC residadr else PC PC 1 endif RA ss A E semua a AiR abe Arity Constraint Rx Rx must point to a term Technical Note No 18 December 1992 22 Seth Copen Goldstein lato bn Li l2 ln is a set of argument names or features The Arity Constraint instruction succeeds iff the Rx has the features 1 2 n and no others It is used here as a way of specifying the number and names of the arguments to a function If a function call does not have all the arguments specified in the definition then the function call becomes curried If the Arity Constraint succeeds then the function call represented by the term Rx will be executed If Rx is not a closure i e it has never curried before then a new term will be created and assigned to register RR This term will become the result of the function If Rx has previously curried then a result term will already have been created and it is now assigned to RR If Rx contains features that are not present in the set 41 f2 bn then the Arity Constraint fails This should probably also signal some kind of exception since this kind of failure is not expected Another implementation of LAM might i
51. rm has been unified to the term pointed to by ref Every function invocation is associated with a Frame The relevant parts are class Frame int residCounter counts number of residuated variables Code body address of body of function Code fail the address to goto if a constraint fails Psiterm result result of the function gets put here y Missing from the above definition is any information about local variables and so forth that every function frame will hold This definition is just sufficient for describing the matching process The residCounter is initialized on entry to zero and every residuated goal increments this counter The instruction resid checks this field If it is zero then the function body pointed to by the field body is executed The fail is a pointer to the next clause in the function definition to be executed if any of the constraints in the current clause tree fail If the current clause tree is the last then this will point to code that will invoke the general backtracking routine The term that is returned by the function is pointed to by the result field When a constraint residuates it creates if necessary a Residuat ion which is attached to the term that caused the residuation class Residuation Frame parent frame of function to be activated Sort sort the best known sort for this term i e the glb of the formal and the actual Residuation next next resid
52. rson Z person boss gt joe X person spouse gt Z A X person spouse gt Z Y person Z person boss gt joe Y person boss gt fred failure Up until the last query Z the spouse of X was unifiable with Y However in the last step Z and Y became incompatible and thus the original query had to result in failure Although the arguments to a function call cannot be modified in the matching process infor mation needs to be propagated in the term between constraints For example assume the sort hierarchy in Figure 4 and the following function definition theSame X X X gt 1 The call theSame A a B b C c must fail immediately This is because the terms A B and C can never unify Technical Note No 18 December 1992 6 Seth Copen Goldstein Figure 4 A sample sort hierarchy 2 3 Introduction to Currying The final difficulty in implementing functions in LIFE is that function calls can curry If a function call does not have all its arguments specified in the function definition then executing the function returns a term that is a curried function call It does not return a term that stands for the result of the function call This curried function call is a first class object If the rest of the arguments are added to the curried function call then the function will execute Thus any unification performed on the term representing the curried function will not affect the result of th
53. s do not modify the value of 1P terms they only check there contents and sometime cause residuations to be associated with them Body instruction on the other hand cause the terms they operate on to change value The one exception to this is deref which can be used in either section It is listed in the body instruction section We will use a four part format to describe all the instructions First the name and syntax of the instruction will appear as follows instr ctionformat eee eect e eee e nee E instruction name After the instruction format will be a description of each operand then a textual description of the function and finally a pseudo code description of the instruction s functionality 6 3 Head Instructions Each head instruction is a constraint that checks its operand the actual argument to the function against the function definition The constraints are different from the body instructions in that they don t modify the operands and in that they can create residuations Thus while body constraint instructions will either succeed or fail head constraints will either succeed residuate or fail All the head instructions have an implicit form and some of them have an explicit form The December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 17 implicit form to work correctly requires the CF register and certain of the fields of the current frame to have been initialized for residuat
54. siduations In other words it is used to construct new w terms After this instruction has been executed Rx will always succeed and the sequence Rz Rx amp Rz Ry will always succeed Rx gt addFeature Ry PC PC 1 R Ry levantar RR Oran General Unify unify Rx Ry Rx Rx points to a Y term Ry Ry points to a term The General Unify instruction unifies the terms Rx and Ry If the unification succeeds then one of Rx and Ry will be modified so that its dereference link points to the other In general the younger variable should be modified to point to the older to minimize trailing If the unification fails then control will be transferred to the address in the CFA register if unify Rx Ry then PC PC 1 else PC CFA endif ets AA ok Ok SE tae A Create Reference Link Rx Rx points to a term Ry Ry points to a term The Create Reference Link instruction sets the reference field of the Rx term to point to Ry After this instruction has executed Rx Ry would succeed Rx gt ref Ry PC Pc 1 Technical Note No 18 December 1992 26 Seth Copen Goldstein deref Rx Ry noviciado iaa Retrieve a Dereferenced term Rx Rx points to the term to be dereferenced Ry Ry the dereferenced term is returned here This instruction will trace down the reference links starting with the term in Rx It will put the term at the end of the chain into Ry As a shorthand deref Rx Ry will often be
55. siterm rl The psiterm we check to be equal with r0 Code label The address to continue at on resumption If rO and r1 both point to same psiterm we re golden if r0 rl CONTINUE All the real work happens in canUnify r0 r1 Technical Note No 18 December 1992 46 Seth Copen Goldstein If we get here then the psiterms can be unified so CONTINUE The heart of the equality constraint is the canUnify routine It checks to see that two psiterms can be unified This is an expensive procedure that not only checks the sorts of its two arguments but all features of each term that could be unified void canUnify Psiterm amp x Psiterm y Residuation rx The x s residuation for this frame Residuation ry The y s residuation for this frame rx x findResid CF Get and if necessary create x s residuation for the current frame if rx gt hasEqResidWith y CF If x and y are already involved in an equality constraint then we have already checked to see that they and all the psiterms reached through their features are compatible so we just return This is in essence the mark that is used to stop infinite loops from happening in this canUnify routine return x and y haven t been checked yet so create a resid for y ry y findResid CF Get the glb of the BEST KNOWN sorts of x and y g glb rx gt sort ry gt
56. sort if g isBottom FAIL Force both x s and y s best known sort to be their glb The setsort procedure will also invoke any residuations that might already be attached to x and y rx gt setsort g ry gt setsort g Add an equality residuation to each of rx and ry rx gt addEgResidWith y label ry gt addEgResidWith x label Now each of the features that are in common between x and y must be checked to December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 47 see if they can unify foreach f x intersect y features if we made it this far then x and y can unify canUnify x get f y get f The complexity of the equality constraint and in particular the canUnify procedure described above is due to catching disentailment caused by argument unification To see how the above code works we will work out an example based on the sort hierarchy in Figure 4 the function definition theSame X X X 31 and the call theSame x gt a b x gt b y gt b c x gt c First note that the LAM code produced for the function definition will include the following segment R1 R2 R2 R3 We assume that the registers have been loaded with the first second and third arguments respectively Upon execution of the first constraint the terms and their associated residuations will be as shown in Figure 16 First note that the best sort
57. straint instruction determines whether a memory location points to a term or is uninitialized This instruction will either succeed or residuate It is used to make sure that a variable has been defined before it is used For instance if a variable is initialized in part of a constraint tree that could have been skipped because a feature constraint residuated i e the term in question was missing a feature then an equality constraint depending on the skipped variable will have to be skipped until the variable is initialized December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 21 Figure 11 A constraint tree for the one argument one clause function definition This tree has been augmented with the Initialized Constraint L In general this constraint will be immediately followed by an equality constraint Since the equality constraint can only be executed if this constraint succeeds the default address to jump to if the constraint residuates is the one following the next instruction i e the PC 2 For example the function definition of one clause with one argument spouseName X person name gt I id first gt F last gt L spouse gt S person name gt id last L body creates a constraint tree as in Figure 11 with an equality constraint between the terms at the end of the last features Notice that if either the name feature of X or the last feature of I is not present then the E
58. straint residuates during the matching phase a Residuation is created which is attached to the term involved The remaining constraints the ones below the residuating constraint in the tree will be skipped If all of the executed constraints either succeed or residuate the function becomes quiescent and returns to the caller If any of the terms that have residuations are later modified then the residuations will resume execution to recheck the constraint that caused the residuation during the matching phase This is called the resumption phase 5 2 Residuation When a constraint in the head of a function definition residuates a series of objects is created and attached to the term that caused the constraint to residuate The objects created have two primary functions first to force disentailment if necessary and second to allow the constraint to be resumed if the term is modified In order to keep the amount of information stored in each residuation to a minimum the residuation structure is broken down into two objects a Residuation object which records the information about the frame on which the term is residuated and a ResidInfo object which records the particular constraint that residuated In this way if a single term is involved in multiple residuated constrains for a particular frame only multiple ResidInfo objects need to be created See Figure 7 for an example of a frame with a term that has residuated twice Be
59. sy the sort it must agree with Code label address of code to resume if this residuates Sort g g glb r sort s if g isBottom FAIL if it is bottom then FAIL if g lt s CONTINUE if it is under s succeed December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 45 we must residuate so create a residuation for the current frame which will have a sort compatible with g and will continue at label when the psiterm is lowered If tryAddSimple can t create the residuation because g is incompatible with the sort already in this psiterm s residuation for the current frame then it will execute the FAIL macro r tryAddSimple CF g label CONTINUE 10 2 2 Feature Constraint See Page 19 for the pseudo code definition of this constraint void featureExistence Psiterm amp r The psiterm that we are testing Feature l The feature we want to check for Code label The address to resume to Code skip The place to continue if this constraint residuates Does r have the feature 1 If so succeed if r hasFeature 1 CONTINUE OK guess we have to residuate r tryAddSimple CF g label Continue execution at skip SKIP_TO skip 10 2 3 Equality Constraint See Page 20 for the pseudo code definition of this constraint void equality Psiterm amp r0 The psiterm we check to be equal with rZ P
60. te No 18 29 Check that caller has two arguments This is the term entrance section Any reference to the function will now point to the result of the function This is the register interface entry Al locate a new frame Setup for executing the first rule If the first rule fails try the second one Is the first rule ok Any failure now is a general failure Since we don t know if there is already aresult we must assume there is and do a general unification Clean up and return Recheck sort constraint from rule 1 Recheck subsort constraint from rule 2 Recheck existence constraint Recheck existence constraint First rule failed so setup for executing second rule If this rule fails the whole function call fails Begin checking head of second rule December 1992 30 isList resid CPT new Psi append addfeature CPT 1 CE gt argl cdr addfeature CPT 2 CF gt 2L evalfunc CPT R2 new Psi List addfeature R2 car CF gt arg1 car addfeature R2 cdr RR evalpsi R2 unify CF gt result R2 free CF pop CF ret Seth Copen Goldstein Executing second rule so call append recursively Perform actual function call Build cons cell Make it the result Clean up and return We can optimize append in two ways First compiler analysis should let us check the function definition to see if the function call we are performing satisfies the arity constraint If it does
61. ters to data structures in memory They are not special except that their use is predetermined so that we can more easily describe the instruction set By having them implicit in the instructions we are also able to pack more information into each instruction LAM makes no assumptions about the number of registers in the machine It is assumed that the mapping from LAM to the machine language of a general purpose computer would map the LAM registers as efficiently as possible LAM also assumes that no tags are available in memory or in the registers Figure 1 lists all the registers in LAM important to this document 6 2 The LAM Instruction Set This section describes the instructions in the LAM instruction set It focuses on the instructions needed to do matching The instruction set is specified at a high level so as to allow latitude in the Technical Note No 18 December 1992 16 Seth Copen Goldstein LAM to native instruction set mapping For instance it does not specify how heap allocated structures are managed It does not take a position on the actual representation of integers in their boxed or unboxed form Its primarily addresses the functionality of matching residuation failure and unification It ignores the handling of choice points and the implementation of built in operations In the instruction descriptions below operand names that begin with R denote any register X is used to denote a memory location Italicized names
62. the function is reactivated and fires December 1992 Digital PRL An Abstract Machine to Implement Functions in LIFE 5 The function insurance like incr has two clauses in its definition But it differs from incr in that the formal argument in the second clause is not incomparable with that in the first clause Instead it is more general than the one in the first clause A insurance X person A X person X person boss gt joe A X person boss gt joe X person spouse gt Y person A 6G X person boss gt joe spouse gt Y Y person In this example the function residuates not because the root sort of the argument is under specified but rather because the argument is missing a feature term Notice that when the argument X is lowered by adding the feature boss it does not affect the residuation When it is lowered again by adding the feature spouse the function remains residuated even though the second clause is satisfied This brings out the point that before the next clause is tried the current clause must be completely disentailed To continue this example Y intern A 2 X person boss joe spouse gt Y Y intern We see that once the first clause is disentailed because intern A temp L the second clause is checked and in this case fires This example also shows how equality constraints must be considered in disentailment A isspouse X person Y person A X person Y pe
63. to clarify the mechanisms used for residuation and resumption we will examine the flow of control for the following contrived segment of LIFE code A B C A B D C 5 A 4 B 5 We will assume that is not a built in function but rather is defined by the one clause LIFE code A int B int gt intplus A B Technical Note No 18 December 1992 34 Seth Copen Goldstein Where intplus A B treats the sorts of A and the sort that is an integer that is their sum The frame definition and compiled LAM code for thi class Plus public Frame Psiterm Psiterm argl arg2 hi plus cpT 1 2 R1 CPT 1 R2 CPT 2 ref CPT RR reg plus R1Cint fail residFirst R2Cint fail residSecond body R3 intPlus R1 R2 unify RR R3 ret push CF cF new Frame append R1 tryAddSimple CF int checkPlus R2Cint residFirst stash CE body doPlus CE gt residCount CF gt one R1 CF gt one R2 pop CF ret residSecond push CF CF new Frame append R2 tryAddSimple CF int checkPlus jmp stash December 1992 B as integers and returns a a term with s function are as follows Check that caller has two arguments This is the P term entrance section Any reference to the function will now point to the result of the function Explicit subsort constraint will execute general fail routine if this constraint fails since this definitio
64. ttached ResidInfo which has a pointer to the handleCurry routine see Figure 9 Further the original term will be unified with the newly created curry term in the sense that dereferencing the original term will return the new curry term Furthermore when the newly created term is unified with the special curry term the old term will will have its arguments copied into the new term This allows the curry term to represent a closure and be used as many times as the curried function is applied Thus if extra arguments are added to the original function call the unification procedure will unify the extra arguments with the curry term Since the curry term has no features and is of sort top the unification will always succeed invoking the residuation attached to the curry term in the process The residuation function invoked will always be the handleCurry routine The handleCurry routine will first break the dereference link between the original function and its curry term It will then copy the original term to the curry term and then it will then try to unify the curry term with the term representing the original function call If the unification succeeds it will retry the function Otherwise the unification will fail in the normal way Thus the mechanism for residuation handles currying without any extra overhead 6 LAM The Life Abstract Machine The LAM is an abstract machine used as the intermediate target for the compilation of LIFE
65. uation for this var ResidInfo info info about each resid for this parent y Each term can have only one Residuation per frame in which it has residuated Each constraint that it residuates on is pointed to by the info field of the Residuation Sort constraints feature constraints and initialized constraints all create ResidInfo instances Equality constraints create an instance of EqgResidInfo In addition to its use for residuation ResidInfo is also used when functions curry class ResidInfo Technical Note No 18 December 1992 10 Seth Copen Goldstein Psiterm Residuation Frame ResidInfo EgResidInfo Figure 6 Representation of the basic data structures Code address address of constraint to re execute ResidInfo next next ResidInfo for this frame if it exists else NULL y class EqResidInfo public ResidInfo Residuation other Residuation for the other psiterm used in constraint y In what follows we will represent the data structures by schematic diagrams The diagrams will not name the fields of the data structures but will just stack the fields upon each other as in Figure 6 5 The Mechanism Behind the Machine 5 1 The Phases of a Function Call The execution of a function has several phases The first is upon initial entry to the function In this phase the arity constraint see Section 6 3 is executed If the arity constraint succeeds the w term represe
66. ural and efficient compilation strategy 2 Matching 2 1 Definition Function invocation in LIFE is accomplished with matching As a result the rules for invoking functions in LIFE follow the rules of implication which means there are three cases that need to be considered when implementing function invocation 1 when the actual arguments imply i e entail the formal arguments 2 when the actuals imply the negation of the formals i e they disentail the formals and 3 when the actuals neither entail nor disentail the formals In the last case we say that the function invocation has residuated on its arguments The requirements for an implementation of function invocation in LIFE are that a function invocation either fire or fail as soon as the actuals either entail or disentail the formals and that no changes be made to the arguments unless and until the function fires Finally the implementation must maintain the church Rosser property of functions The main challenge to the implementor is to perform the smallest possible number of checks This section describes an efficient implementation which will perform each check only once regardless of the number of times a function residuates or its arguments are lowered There are two components to this implementation an abstract machine and a compilation strategy Most important it will also handle the most common cases that of direct entailment or disentailment with surprising efficiency
67. ver otherwise it returns false boolean hasEgResidWith Psiterm y Frame f adds an equality residuation between the this psiterm and x void addEqResidWith Psitermg x Code label Indicates that the psiterm connected that this residuation is attached to has been lowered so we should activate this residuation void lower Add a ResidInfo to this residuation that should resume at label void addSimpleResid Code label a these two classes hold the address of the code chunk to be executed if the psiterm pointing to these is ever lowered class ResidInfo Code address address of constraint to re execute ResidIiInfo next next ResidInfo for this frame if it exists else NULL public This function calls the routine at address CPT and CF have already been set up virtual void resume class EqResid ResidInfo Psiterm other psiterm used in constraint public This function executes the equality constraint between the psiterm in CPT and the Psiterm in other If it succeeds then the routine at address is executed virtual void resume Je Technical Note No 18 December 1992 44 Seth Copen Goldstein 10 1 4 The Sort The class sort represents the sorts in the system The choice of representation should be made with efficiency of taking the glb in mind class Sort public Return TRUE is this is bottom sort otherwise FALSE
68. y sort Intersection of sorts is carried out by the greatest lower bound The details of sort implication and in particular how they relate to function invocation in LIFE can be found in 1 Technical Note No 18 December 1992 2 Seth Copen Goldstein name fred person spouse spouse person Figure 1 Graphical representation of a Y term The nodes represent sorts and the arcs features The capital letters in the nodes correspond to the variables used in the textual representation of the 4 term operator written A terms can be represented in many ways The first two considered here are the textual and graphical representations For example the term X person name gt F fred spouse gt S person name gt M mary spouse gt X Can also be represented by the directed graph in Figure 1 The graphical representation does not actually need the variable names used in the textual representation to capture equality constraints However to aid in referencing the nodes and arcs we will keep them An alternative representation of terms is the OSF clause An OSF clause is a conjunction of a OSF constraints An OSF constraint is one of 1 X s 2 X X or 3 X L X where X and X are variables in Y s is a sort in S and is a feature in F An OSF clause is either an OSF constraint or of the form amp where and are OSF clauses We can read X sas X lies in sort s X X

Paris Research Laboratory of Digital

Contents

Download Pdf Manuals

Related Search

Related Contents