Brand X: LISP Suport for Semantic Networks
Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Programming Environments. Pages 940-945.
© 1981 International Joint Conferences on Artificial Intelligence
Abstract
RRA Nil x is a simple representation language implemented as a pure exten sion of I.ISP . BRAND X provides the following additional facilities over I.I SP: Uniqut and canonical stru ctures. properly /isis for all objects, labels for all o bje cts . and a sy ntax to expre ss each of these . supponed by a rea der and printer. BRAND x is intended as an "assembly language" for repr ese ntati on lan gu a ges , attempting to provide facilities generally found use ful in th e simpl est manner, without any strong commitme nt to specific represe nt a ti o nal co nventions. The fund amental ideas of the language are d esc rib ed, an ove rvi ew of its featur es and no lltti on is given , and some inherent p ro blem s of impl ementation and sem a ntics are presented.
- I. l!lack. ~.. "Identit y of lndisccrnibles," Probltms of Analysis: Philosophical Essay~ Greenwood Press, (1954).
- Bobrow, D. G .. "A Note on !lash Linking," Comm. ACM 18. (7) (July 1975), 413-415.
- Jlobrow. D. G.. and Winograd, T., An Ovtrvitw of KR /, a Knowltdgt Rrpr<stntarion /,anguag e, Technical Report AIM-293. Stanford Artir~eial Intel• ligcnce Lab., Stanford, Ca., (1976).
- Goldstein, I. P., and Roberts. R. B .. NUDGE, A Knowlrdgr-Rased Schtduflng Program. AI Memo 405. MIT Artificial Intelligence I ah .. Cambridge, Mass., (1977).
- Goto, 1'., Monoeopy and Assoeiarivt Algorirhm.< in an l:'xrendrd l .isp, Technical Rcpon 74-03, Information Science Laboratories. Faculty of Science, University of Tokyo, Tokyo, Japan. (May 1974).
- llawkinson, L B., XI.MS: A Linguistic Memory System, TM-173. MIT Lab. for Comp. Sci. Cambridge. Mass.. (1980)
- llewill, C., Dt~ription and Theortrical ~nn(l'. !i.! (Using Sdrtmata) of PI.ANNI:.'R: .4 l.angiKigt for Pro••ing 'f'htortms and Manipulating Models in a Robot, AI• TR-258, MIT Artificial Intelligence Lab .. Cambridge, Mass., (1972).
- Liskov, B. H., Snyder. A., Atkinson, R .. and Schaffert, C., "Abstraction Mechanisms in CLU." Comm. ACAf 20, (8) (August 1977), 564-576.
- Manin, W. A. , Rolt~ co-d<•smptor~ and rhe fonnal rtprrsrntarion of quantified English txprtS5ion~ TM-139, MIT Lab. for Comp. Sci., Cambridge, Mass., (September 1979).
- Martin, W. A. aod Szolovits, P .. Stmantit Ntrwarks in Lisp: fundamental conctpt! and a specific impltmtnturion. MIT Lab. for Comp. Sci., Cambridge, Mass., (in preparation).
- II. Moon D. A., AfACUSP Reference Manua~ MIT Lab. for Comp. Sci., Cam- bridge. Mass.. (1974).
- Rulif.o;on, J. F. Derksen. J. A. and Waldinger. R. J.. QM: A procedural calculus for intuirivt rrasoning, Technical Note 7l. SRI International. Menlo rark. Ca .. (November 1972).
- Sussman. G. J .. and McDcnnott. D. V .. "From PLANNER to CONNIVER-A Genetic Approach." Proceedings oftht 1976 l'a/1 Joint Computer Corifertnct, AFIPS Press. (1976), 1171 -1179.
- Szolovits, P .. and Pauker, S. G., "Research on a Mcdic.1l Consultation System for Taking the Present Illness," Procredings of the 71rird Illinois Cartftnncc on Afrdical lnfonnation S)'stcm~ University of Illinois at Chicago Circle, (November 1976).
- Szolovits, P .. Hawkinson. L., and Martin, W. A .. An OvrnitiVofOWL, a Language for K11owhodgr Representation, MIT /I.CSn'M•86. MIT I ab. for Comp. Sci., Camhridge, Mass .. (June 1977). also in Rahmstorf. G .. and Ferguson. M .. (Eds.), l'rocerdings of rht Workshop on Natural Language lnrtracrion with Databases, International Institute for Applied Systems Analysis, Schloss l.axcnburg, Austria, Jan. 10, 1977.
- Szolovits, P .. and Martin , W. A., Brand X Manual. TM-186, MIT l.ab. for Comr. Sci., Cambridge, Mass.. (Nov. 1980).
- Weinreb. D. , and Moon. D .. l .isp Machine Manual, MIT Artificial Intelligence Lab .. Cambridge, Mass., (Jan. 1979).
- Woods, W. A .. Rrstarch in Natural /.anguagt Understanding; Annual Rtporr, Report No. 4274. Jlolt, Beranek , and Newman Inc., Cambridge, Mass., (1979), See especially Chapter 2, "An Introduction to KLIONE", pp. 13-46.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
BRAND X: LISP SUPPORT FOR SEMANTIC NETWORKS
Peter Szolmits and William !1. . Martin
MIT Laboratory fpr Computer Science and MIT !l.nifici:.! lntclligcncc Laboratory
well without overcommitment to representational conventions which are still . the proper subject of vatious research effons.
HRA:O.Il x has been designed and implemented with the above observa tions as iu. guiding principle: it allcmpts to provide a commonly useful set of facilities but to avoid decisions about how any specific features of seman tic networks should be represented. Thus. it is meant to be an "assembly language" of representation languages, providing a bottom layer above LISP in terms of which other conventions will be defined and implemented.
The recent lack of success of a second thread of development has also contributed to our desire to make RRANil x a simple extension to t.ISP rather than a self-contained programming language. Although many proposed At languages suggest that procedures as well as data should be encoded within the language iL~If. of\en that course has not been adequately supported. Either the issues of how to represent procedures (and how to interpret them) have been put ofT. leaving the language dependent on iL' implementation environment (LISP) for procedural suppon. or a very complex interpreter has been created which has limited (if any) appeal to users other than the ones who developed the language. As in the case of dallt structures mentioned above. the simplicity and power of IJSP seem elusive to language builders.
HltA~ Il x's immediate predecessor is the \I.MS language uf Hawkinson 16). which has hcen used by the authors and their colleagues both as a data ba.'c and a.' the implement" lion medium of OWl 19. IS]. IIKAI'<Il x w:L~ inspired by the observation that many of the thrilities provi<kd by \I MS appeared merely to duplicate feature-s already adequately provided hy t.ISI'. suggesting that its function muld be greaUy simplified by implementing instead a limited, general set of extensions to IJSP.
In summary, then, we t.alce the following position: Because IJSP is so successful as a base language for AI research, try to build directly on it when creating higher-level representation languages. In creating URAND x. we have chosen to add new data types and to extend the standard I.ISI' interpreter to exhibit some reasonable behavior for these types. In all this, however, we have tried to assure that all of LISP remains intact. Therefore. with vinually no exception. any valid t.ISP expression is a valid IIRANil x expression. and its interprellltion remains unchanged.
RRA!"D x is implemented as an extension of I.ISP (MACI.ISI' [II D. and ;uppons the following additional features:
- unique and canonical/is/ s/ruc/ures-providing a dallt base facility in which expressions may be id~ntical when composed of the SJme subexpressions,
- universal properly lists-permitting the attachment of property/value pairs to any object in the language,
- labels- providing an abbreviation for convenient referent·e to complex expressions.
- an ex/ended I.ISP nota/ion-allowing a convenient mechanism for reading and printing any I.ISP and IIRA!"Il x structures.
- triples- a special. compact da"' type having three components (especially for the suppon of OWl.), which is optionally present in the language.
IMPLEMENTING SEMANTIC NETWORKS
The authors are sometimes asked if they can explain in a simple way the ad\antage of implementing a Sl'mantic network in IIN A~Il x over implementing it directly in 1.151'. Typkall y. a st·m:mlic network b a diOkult data structure to read and print in I.ISI'. It ha> hadpointers whirh create drcular structurelo.
ABSTRACT
RRANil x is a simple representation language implemented as a pure extension of I.ISP. BRAND X provides the following additional facilities over I.ISP: Uniqut and canonical structures. properly /isis for all objects, labels for all objects. and a syntax to express each of these. supponed by a reader and printer. BRAND x is intended as an "assembly language" for representation languages, attempting to provide facilities generally found useful in the simplest manner, without any strong commitment to specific representational conventions. The fundamental ideas of the language are described, an overview of its features and nollttion is given, and some inherent problems of implementation and semantics are presented.
INTRODUCTION
The past decade has seen the introduction of numerous programming languages and representational languages specifically intended for use by the AI community. The early seventies SJw the introduction of languages (e.g., I'I.ANNLR. CONNIVER. QA4) which incorporated higher level data structures, novel invocation and control structures, context mechanisms, and rule-like representations of knowledge [7. 13, 12). Later research, focusing on problems of the meaning of representations. h:L' led to a new group of languages (e.g .. KR I . I·Rt . Kt ION!'.) cmphasi1ing the structure of r~prc'SCntations . multiple descriptions and vicwpoinL~. "frame· like" systems. and procedurdl att.1chment IJ. 4. IR). Despite the promise and even popularity of these languages, most AI programs continue to be written in that robust standby which precedes the above by at least a decade, I.ISP.
The all rae! ion of I.ISP continues to be its great simp I icity and mutability, allowing any user to build features of more power and incorporate them within the language. The contrasting weakness of each of the above-mentioned languages is that they make represcn"ttional and control commitments which, alU10ugh appropriate to some arplicalions which guided the development of the language. later appear arbitrary or wrung for other potential uses. To successive generations of AI researchers. it continues to seem more attractive to implement their own language extensions on top of LISP than to accept a wmplete package of conventions provided (or imposed) by the more recent language designers. However. some generality docs exist among the facilities that have been repeatedly invented-- mughly corresponding to the notion of Sl'mantic nrtM'orh if only as a medium oi implementing frame sysrems or indexing structure'S for logic or pmduetion-rule based inference programs. It b obviously desirable to provide as powerful a set of support facilities as possihle. without overstepping the bounds of commitment which may make the resulting language unacceptable.
Our intcre>l in extending IJSI' arises from our recent experience in build· ing large AI programs which represent knowledge in the form of semantic net works. In addition to st raightforward implemen"ttions of such data structures in terms of t.ISP symbols and property lisL~. we have also explored implementa tions huill on discrimination networks of expressions 114), a uniform indexable data type similar to I.EAI' triples, and several generations of representation languages embedded within I.ISI' 16. 15].
A useful bas~ l;mguage for implementing semantic networks must have fac ilities for creating. retrieving and manipulating nodes and links among U1cm. We have found that a wnsistent Sl't of extensions to I.ISI' which support unique expressions and the abil ity to attach properties to any object serves us and it is so str<m£IY inlcrmnnectcd that given any pit·cc or it to prinl. I.IS~ rrint rnnctions olkn prim the whok network. In liS!', lire traditional way to mcetthc'c diOk'uhies is to make CI'Cry node of the network an atomic symbol . with the network links on iL' propcny list. Given an atom. 1 lSI' will print just its name. not trueing down the property list. and thus not looping through the whole network . There arc at least four diffiwhics willr this solution.
l'irst. the names of lire network nodes arc ol\cn not meaningful. bpccially if user programs create new network nodl'S, the nodes are typi mlly r i1·en names surh <L'i GOOOt . G0002. etc These namt·s do nothing to impn11e the intdligihility of the scm;ullic network . NtKb nealcd hy the user can of wursc be given readahlc (if long) hyphenated names such tL'i LEFT lUSK -OF-ELEPHANT-CLYDE-1. If such names me. however. uninlerpreted by the system (as GOOOt must he). then lire user has no assurance that the given node name actually represents what its name implies. Such assurance can be gained by explicitly checking that the relationships the node enters into arc consistent with its name. but in that case the common information is redundantly stored in the network-once in the names and once in the links. One possible solution occasionally proposed is to penni! the system to extract tlwr information from the node name when needed. Because names cnmdcd as liS~ atomic symlx>ls have no innate Mn~tlurc. thb requires settling on a grammar of names and a parser for them-not "'r appealing strategy for lire fundamcnt;tl building blocks of a system. In our view. the encoding of some attributes of a node in its name is quite appropriate: we dcpan from the solution criticized here chiefly in using innately slmctured objects for names.
Second, because the standard LIS~ printer will print only the name of a node. the programmer must generally write a set of special purpose print !unctions to print just those links which are desired. Such code must be carefully written to avoid printing semantic network loops. Although sp~dal printers for displaying interesting portions of any large mllection of inl ~rmnnccted objects will ofien prove necessary, we have found that the sLandard printing action for IIRANI> x is oficn adequate and is certainly useful for browsing.
Third, there is no declarative notation whkh the pmgrammer can usc to make the task of inputting a semantic network easy. The pmgrammer may again write special funriJous for l11is purpose. Typically, the input not;1tion as drlined by these functions will diOcr from \\hat is generated by the special purpose print functions. Thus, the application may lad I.ISP's useful ability to read bad wh;llcver can he printed.
Finally, the atoms which represent nodes t;rkc up quite a bit of memory space. This space can be reduced somewhat if the alums arc not made unique in memory, but then one cannot refer 10 a node by typing in iL~ atom name.
In llRANil X, we provide the user with an allernativc lo using atoms for nodes and we deal with tlrc above dinicullics in a general manner. The essence of the solution is to make it possible for data stmrlurcs ollrer than atoms to be unique and to have pmpenies. These then become an alternative to atomic symbols for representing nodeS. A systematic approach to reading and printing all data structures is then provided. Other features and conventions for building semantic networks may also be useful, but the aUihors do not want to be committed to them at the implementation language (URAI\'D x) level (10].
EQUALITY, IDENTITY, UNIQUENESS, COMPOSED OBJECTS
If semantic network nodl'S arc to be named by dcwmposablc objects, we must have the ability to write the same name more than once-thus, the ahility to compose objects in unique ways. This desire leads to an an:dysis of the meaning of "same" and points 10 a reasonable solution and some troubling puulcs.
The traditional definition of equality holds thai two objects arc equal if they arc indistinguishahlc hy any known tesl. In that m,c, of course, one may as well speak of just one ohje<:t. ;llthough various paradoxes hascd on that intcrprc1~11ion have hccn suggc~tcd . 1 In computation , howt:\'Cr. the above deliuition of equality is not the one usually fal'llft'<l. 'I hiS is hera usc computer n11x1cts of lire rc;d w01ld oficn permit tests or distinguishability ·.l'hirh are artii:ICts of the impku1ent;ol1on. Typ~t· ,,lly , computer nnplcmenlallons can distinguish objects ba'iCd on their address in the memory of the computer: thus. two othcrwise·CA.jual ohicrL' may be distinguishable hy being at din'erent addrc'Sscs. For example. although we would like to think of the two numbers <J<J<J and <J<J9 as equal. some I.ISI' implementations lind them distinguishable under the EQ predicate. which tests equality of address.
One standard solution to the undesirable nature of strict equality is to distinguish between identity-true indi>linguishability-and equality-now taken to mean indistinguishable in the rc;ol world. Cl'en though distinguishable in the implemcnLation. LISP's EQ and EQUAL prcdi.-:1tcs capture the-se notions of identity and equality, respectively.'' The distinrtion between identity and equality is important nol only for very si~nificnll cllkiency wnsidcralions, hut abo lwrausc the ahilitr of pmgrams In cause sidc·clfccts permits them to distinguish among EQUAL hut non-idenliral (non-EQ) objects.
A second standard solution is to adopt a convention and mechanism for uniqueness. in which objects intended to he CA.jual are indeed made EQ-i .e .. ohjects are made unique according to the equality criteria. so the system pcnnits the existence of only the single unique representative of an (cquiralcncc) class of EQUAL objects. l.is~·s interning mechanism performs essentially this function for atomic symbols. This solution is motivated by the dl'Sire to use EQ as the standard equality lest. for the reasons cited in the ht'il paragraph. The additional effort needed on input to create or find the unique object implied hy the one actually input is more than rewarded by the possibility of cnicient algorithms based on the assnmption that some class of EQUAL objects is indeed unique (EQ) [5).
The case of us~·s handling of atomic symbols deserves investigation in its own right. as a guide 10 how interning is In be viewed in general. Suppose we intend liS~ atomic symbols to be lire same whenever they are spelled the s:rme. Then the desired equality test on us~ atomic symbols is SAMEPNAMEP. which is true just if its two arguments are atomic symbols which arc spelled identically. The us~ reader. using the system-provided INTERN function, chcxr;es a unique instance of all symbols with the same spelling and ;t<;Surcs llrat thai same instance is read each time a symbol of the same spelling is input.·' This assures th;rt (ordinarily) ;dl instances read of the s:tme-spelled symbol arc EQ-thus. atomic symbols arc unique.
To understand how we might define uniqueness for composite objects, consider in detail the ideal nature of the INTlRN funttion. Fnmrally, INTERN is a function whkh maps atomic symbols to atomic symbols such that its result is the rcprcscll/atir··· or lire equivalence class into which its argument falls when the sci of atomic symbols i~ p:~n i tioncd by the function SAMEPNAMEP. If IJSP interned all atomic symbols. we would say that
- aiPmk symbols are unique (with respect to EQ) under the predicate SAI~EPNAMEP.
We take all objects to have ccnain charactcristit'S known as criteria/. 'these arc the characteristics used hy the panitioning predicate of an interning scheme. For example, the spelling of an atomic symhol (the sequence of t·haractcrs in its wrillcn form) is criteria!. hut other chararlerislit-s such as iL'i value, properties. ;md address arc not. in the above interning scheme.
RRA~IJ x introduces two new list data types with different criteria for uniqueness: ULISTs (Unique LISTs) and CLISTs (Canonical LISTs). The fundamental interesting characteristics of these types are that:
- Uli~Ts are unique (with respect to EQ) under the condition llr:rt their criteria! components (CAR and CDR) are identical (EQ). and
- CL I STs are uni4ue (with respect to EQ) under the condition that their rrilcri ;d components (CAR and CDR) are equal (EQUAL).
Of thcS<' I) pes, CLISTs are the easier to comprehend because they have the property that "EQUAL imp 1 i es EQ." Any canonicalmmhinalion of canonical ohjccls yields another canonical object. and EQ tests are suftkientlo determine e(tuality. The other type. ULIST. is one of a possibly large number of other useful types which partition the universe of expressions by a predicate stronger th.m EQ hut weaker than EQUAL. ULISTs arc particularly useful for cnablin& the user to re-create the s;unc (EQ) stnlt'lure on a seroml unique construction ol the s:nnc pair of non-canonical ohjct'h. Surh an ability may nol he very important. though it has been proposed l<>r example as a way of assodating \':Jilll'S with pn.:\·iously evaluated expressions fGotoa]. Bt~M'\Il X :mtomatically crcalt's r;moniral rather llran unique s1rur1ures wl1r11 all mmptrnrnls of the stn1rturc arc c:monical , and under the control of a lbg may ;~ways ronstmct .:anon 1e<~l structures.
IIRA:o.tll x also provides a new dau1 type 1 R I PLE. and notions of uniqueness and canonicity for it. A triple is a nHnpound ohjcrl with three criteria! pam. irs ILK. TH. ;md CUE. Just~' ULISTsand CLISTsare defined thr lht strurturc. nRA"lX dcfinl'S UTRIPLEs and CTRIPLEs:'
Other MAl'I.ISI' dat<t types (arrays and hunks) are considered innately unique and canonical.'
A Puzzle
The essence of IIRA'\Il x canonical structures is that ''EQUAL implies EQ." Y cl is this a consistently tenable fonnulation? Consider the list structure P.

which could he created by evaluating the LISP expression
IIRA"l x provides the function CANONICAL which. given any object as argument. returns its canonical representative. (II is the canonical version of IN 1£ RN) What arc we to expect if we hand P 10 CANONICAL? The result (let "' ctll it PP) should clearly be a canonical list structure whose CAR and CADR are hoth PU7ZLE. whO\e CDOR is EQ IIl itself, and whose CDR is not llowncr. (COR PP) should ohviously he EQUAL to PP itself, yet the two st ntrturcs c:mnot he identical without doing 'iolcnce to our intuition that the t·annniral fi>rm of a two-cycle should not he a one-cycle. 6
1 he ,implcsl solution to this pu1.1lc is to claim that EQUAL cannot be applied to stnKlllfcs such as P or PP henursc EQUAL is defined as a recursive trcc-mmpari-.tn algorithm and is therefore inapplicable to circular structures. Althott).\lt this is cenainly true in !lSI' (e.g .. (EQUAL P (CDR P)) will lead to lmping). we li:el that this begs the que>tion-it reflect.:; EQUAL's failure to capture our notion of l'qUality rather than a true solution.
A more attral'live solution would he to follow the definition of CANONICAL as the par;~lel of INTERN. l.tsP's INTERN does not guarantee :.hal oulv a single atom witll the same name is ever created: it merely chooses one as the representative of the equivaknce class and maps all others onto th:tt. We wuld act simtlarly in this m~c and say that PP and (CDR PP) both htll into the S<tme equivalence class and CANONICAL chooses. say, PP as the representative. Then
(CANONICAL (CDR PP)) -+ PP
lhis proposal h:ts a grave problem. though. The point of having canonical struclll r<s is to enable us to make use of the "EQUAL implies EQ" rule. Yet now PP and (CDR PP) cannot be EQ. and mapping the lancr onto the former by CANONICAL is lillie or no hdp. In the case of INTERN. the mapping onlo the repre>cntativc ~11.1 useful because it was done consistently on input (by READ) and hecause I.ISP does not ordinarily rreate non-interned atomic symbols. By rontr;tst. simply t<tking the COR of PP retrieve> the non-canonical instance of PP. I he ranonirali7ation could be perliumed at "nm time" by requiring CAR and CDR 111 yield the canonical versions of components of canonical structures, hut at a very high cost
t 'urrentl y. BHA:>:Il x therefore adopts no solution-such drcular structures c: ttUH>I in general he made canonical.' ll1c puule presented here. however, i' interesting not only for ib diiTiculties fitr BRA~Il x. We observe that no ti trm:rl "·heme can permit the sperification of cyclic structures and also enforce "[QUAL implies EQ."
BRAND X LANGUAGE OVERVIEW
For a complete description of I!RA~Il x. we refer the reader to the BRAND x Manual (16]. In this section we merely summarize the facilities provided for suppon of unique and canonical objecb. for t:cneralized propeny lists, and for reading and printing.
Structure Building, Decomposition and Testing
lllL' fundamental construction opcraton.o of BRAr\n x are unique and c:tth·llir:rl '''"i""' 111' ttSI''s CONS. UCO tJS and CCONS . For suppon <'f triples, tltr lttthlll>t" lHJPII.. UIRIPI.l :rnd ClRIPLE serve the analogous purpose. C:AI! :ttu l COR dl'rntnposc li>Ls. ulists and disls. and ILK. TIE and CUE tku·rnoo>c' all krnds of triples. Higher level conslluc·or functions such as t.ISI''s LIST and LISP arc also prmided in unique and cat~onical versions. Predicates to test an ohject for hcing of a pallicular type are also given: the general predicate BR-AND-X-OBJECTP yields tlle type (ULIST, CLIST, TRIPLE. UTR I PLE. or CTR I Plf) of any of the BRAts:D X types and NIL for anything else.
An existing unique or canonical object may of course be found by simply re-creating it: iL~ uniqueness a.~sures that no second copy is made. Thi; technique cannot he u;cd merely to discover if the ohject already exists, because it has the elfcct of creating. it if il does not exist" HRAI'ID x therefore prm ides a synL<telic form. KNOWN. whirh causes its argument to be retriev«..'d if alr~ady present hut NIL to he returned if the argument is not present I.ISP's buck quote syntax'' is cspcrially u>eful in this appliration. allowing us to write ( K'JOWN · [ ,A . B)) to find out whether any unique list structure whose CAR is the value of A Uild whose COR is B has been constructed ..
Properties
HRA~Il x extends the LISP notion of properties to all objects of the l:tnguagc. including all \1ACt.tSP data types and other IIKA~t> x objects. Thus. any object may have a property list (2]. The functions GETP. GET PL. PUTP, REMP. PROPLIST. and SETPROPLIST are extensions of and subsume the corresponding \1,\l'IISI' functions GET . GETL. PUTPROP, REMPROP, PLIST. :tnd SETPLIST. 10
In addition to the a hove. we hare also found it useful to suppon explicitly the manipulation of properties which have lists as tllcir values. The fynclions AIJDP and DELP add and remove one value to or from a list of values on a property of any object. New values are added at the front of the list, and duplicates arc deleted. Equality chedin.g for duplicates and for deletion is bv EQ. lhe motivation for these functions is that we wanted to provide a synw (sec below) which allowed the expression of multiple values for properties such as DAUGHTERS or CHARACTERIZATION.
Each call to UCO,!S. CCONS. UT R I PLE and CTR I PLE causes the created cell to lx· :~ddcd under the CAR -I (inverse CAR) property of its CA~ (ILK, in the case of triples). This structure is nece.'Sal)' 10 maintain uniqueness and r.anonicity, and is also often useful for other indexing and searchin& applic.ttions. The function CAR -1 retrieves the list of objects so indexed under its argumenL
Labels
Any RRA'lll x object may be labeled. In a system in which names are typk:ally const:uctcd by composition'of other names. a facility for abbreviatin& n"mes is e'Sential to avoid priming an expression of size at least 2" for objecli built by n composi tions. By convention. labels are most often atomic symbols, although any object may label any other. The assignment of labels is intended to be pern1anent. and numerous implement<tlion problems result if labels are reassigned. llte relationship between a label and the object it labels is llOl to be viewed as the relationship between variables and values. Both the label and th~ object are read as the identical entity.
A label may be used in BRAND x before the expression it labels has been defined. and an expression may also be used and later have a label assigned to it. However. prohlcms again arise if hoth the label and the expression are used before they are associated.
Unique and Canonical
The functions UNIQUE and CANONICAL are provided to return the unique and canonical versions of their inputs. Listed here are
- the BRAND x types to which each function applies,
- the components of tllose types considered criteria! by the function.
- the equality predicate used on objects of that type, and
- a description of the resulting value returned by the function.
UNIQUE
atomic symhol
print name SAMEPNAMEP'
Atomic s)·mhols are made unique by the !.lSI' primitive INTERN. The representative clement of the equivalence class under SAMEPNAMEP is the first svmbol seen with that r.am~.
number
type and value EQUAL
Numbers are interned by NINTERN, which uses a hashing scheme defined by BRAND x and also used by the property list mechanism. The repre sentative is the first number of that type and value which is NINTERNed.
LIST or ULIST
CAR and CDR
EQ-PARTS
Yields the unique ULIST (or CLIST if the components arc canonical or the flag CCONS is non-NIL) formed of the CAR and CDR of the input If the input is a ULIST, it is unchanged. If a LIST, its CAR and CDR are UCONSed. The representative element cannot be EQ the first LIST made unique because liRA NO x implements LISTs and ULISTs as different LISP data types.
TRIPLE or UTRIPLE ILK, TIE and CUE EQ-PARTS
Yields the unique UTRIPLE (or CTRIPLE if the components are canonical or if the flag CCONS is non-NIL) fom1ed of the ILK, TIE and CUE of the input. If the input is a UTRIPLE, it is itself returned. If it is a TRIPLE, its components are combined by UTRIPLE.
CLIST or CTRIPLE self EQ
CLISTs and CTR IPLEs are innately unique because there is no mechanism for forming other copies of them-c-E QUAL implies E Q.
other self EQ
Hunks, arrays, and other LISP data types are considered to be unique, forming singleton classes under the chosen equivalence relation. A relatively straightforward extension of the ideas used for the creation of unique list structure could also be applied to hunks and arrays, but this has not been done in ORAND x.
CANONICAL
atomic symbol
print name SAMEPNAMEP
Atomic symbols are made canonical by the LISP primitive !Nl ERN. The representative element of the equivalence class under SAMEPN.~MEP is the first symbol seen with that name. This is the same as under UNIQUE.
number
type and .value EQUAL
Numbers are interned by NINTERN, which uses a hashing scheme defined by IIRANO x and also used by the property list mechanism. The repre sentative is the first number of that type and value which is NINTERNed. This is the same as under UNIQUE.
LIST, ULIST, or CLIST CAR and CDR F. QUAL
The canonical representative of any form of list is a CI.IST. The canonical fomt of a CLIST is itself. That of a LIST or ULIST i~ the CCONS of the CANONICAL versions of its CAR and CDR. Note that this may require the complete copying of LIST or ULIST structure into CLIST structure. CLISTs are easily recognized in the implementation, so that EQUAL tests can be performed by EQ and canonicalization is trivial.
TRIPLE, UTRIPLE or CTRIPLE ILK, TIE and CUE EQUAL
The canonical representative of any fornt of triple is a CTRIPLE. The canonical form of a CTRIPLE is itself. That of a TRIPLE or UTRIPLE is the CTRIPLE of the CANONICAL versions of its ILK, TIE and CUE. Note that, as for list structure, this may require the extensive copying of TRIPLE and UTRIPLE structures. EQUAL tests on CLISTs may also be performed by EQ.
other self EQ
Hunks, arrays, and other LISP data types are considered to be canonical as well as unique. forming singleton classes under the chosen equivalence relations. A relatively straightforward extension of the ideas used for the creation of canonical list structure could also be applied to hunks and arrays, but this has not been done in RRANO x.
The predicates UNIQUEP and CANONICALP test whether their arguments are unique and canonical respectively. The meaning of these predicates is that any object which passes one would itself be returned by the functions UNIQUE and CANONICAL. INTERNP and NINTERNP are special cases of these for atomic symbols and numbers.
NOTATION
One of the powerful simplicities of LISP is that, on the whole, any object may be printed out in such a way that it can later be reconstituted by reading in that printed representation. 11 This notion is preserved and extended to ORAND X objects.
Lists, Ulists, and Clists
Our· goal has been to preserve LISP syntax as much as possible. Therefore, LISTs and CONSes may be formed as in LISP:
reading (A . B) is equivalent to evaluating (CONS · A · B) . and
reading (ABC) is equivalent to evaluating (LIST 'A 'B 'C),
ULISTs and CLISTs are written in a manner similar to LISTs, but with square br-Jckets instead of parentheses. Thus,
reading [A . B) is equivalent to evaluating (UCONS 'A 'B), and
reading [A B C) is equivalent to evaluating (ULIST 'A 'B 'C).
ULISTs, when they are composed of non-unique components, are shown in the appropriat~ mixture of parentheses and square brackets. Thus, for exantple, reading [A (B)] is equivalent to evaluating (UCONS 'A '(B)).
Canonical stmctures must always be composed only of canonical substructures; thus, their printed representation is free of parentheses. In contr-dSt with the above example,
Triples, Utriples, and Ctriples
In a manner analogous to lists. a notation is defined for triples. The fundamental triple notation looks like a list of three elements, the ILK, TIE and CUE, but with an asterisk between the ILK and TIE. Thus.
reading (A·B C) is equivalent to evaluating (TRIPLE 'A 'B 'C). Similarly,
reading [A·B C) is equivalent to evaluating (UTRIPLE · A '8 'C). and CTR I PLEs are formed when each component of a UTRIPLE is canonical.'2 Labels
Labels are assigned by preceding the criteria] part of the expression by the label and the symbol " · ". (Note that this is within the brackets delimiting the expression.) For example,
[AN-EXAMPLE · THIS IS AN EXAMPLE)
assigns to the canonical four-list [THIS IS AN EXAMPLE) the label AN EXAMPLE.
A label is used by prefixing it with an exclamation point ·in the syntax. Thus, after the last example,
[NOW . IAN-EXAMPLE)
is entirely equivalent to
[NOW THIS IS AN EXAMPLE),
and will be printed in the shorter fonn.
Properties
LisP does not provide any explicit syntax for the assignment or display of properties. In BRAND x, within· the square brackets or parentheses used in writing an expression, the criteria! expression may be followed by any number of property assignment clauses. Each is of the fonn:
an ampersand (&). followed by the property indicator, followed by any number of values.
The values are added (via ADDP) so that they appear in the order given in the syntax. Thus, if [BALL 1] has no COLOR property to begin with, then after [BALL 1 &COLOR RED GREEN BLUE),
we have
(GETP '[BALL 1) 'COLOR) ·> (RED GREEN BLUE) .
To support effective optional cross-indexing in the data base, BRAND x pem1its the specification of both forward and reverse properties at the same time. To specify a reverse property link, follow the initial ampersand and property by a second antpersand and property, before the values. For example, after
[BALL 2 &COLOR &HAVING-THIS-COLOR RED WHITE) , we have
(GETP '(BALL 2) 'COLOR) => (RED WHITE), and (GETP 'REO 'HAVING-THIS-COLOR) => ((BALL 2)) .
In I.ISI', :m expression such as ( . X) is synlactically invalid, as it appears to CONS nothing onto X. In BRAND x, however, we interpret that fonn as equiv~lcnt to just X. 13 This provides a syntactic means of attaching p1opertics (and labels as well) to any IIRAI'D x object. For example, we use !he IC1IIowing not:1tion to att:1ch POSSIBLE -VALUES to COLOR:
[ . COLOR &POSSIBLE-VALUES RED ORANGE YELLOW GREEN BLUE INDIGO VIOLET)
Anaphora
We of\cn find it convenient to refer to parts of an expression as that expression is being written. In specifying the representation of a frame in a semantic nelwork, for example. we may need to refer to the subject role of UIC frame in close proximity to our specification of the expression representing the li'ame iL~el f. For example,
(RUN INTO TROUBLE &ROLES (SUBJECT (RUN INTO TROUBLE] &C PERSON)]
to indicate that run Into trouble has. a subject role and that whatever satisfies that role must also satisfy the characterization person. Note that, after the above,
(GETP '(RUN INTO TROUBLE) 'ROLES) yields
((SUBJECT (RUN INTO TROUBLE))) .
It is undesirable to have to repeat the expression (RUN INTO TROUBLE) each time a role of that frame is to be specified or referred to. Instead, nRAND x allows us to write
(RUN INTO TROUBLE &ROLES (SUBJECT : &C PERSON)],
which is read identically with the expanded fonn above. Here, the colon (:) acts as an anaphor, referring to the criteria! expression which is one level of parenthe~es or brackets out from the appearance of the colon.
BRAND x supports a general facility for anaphor:1, expressed via successive colons not separated by space. The number of colons specifies the number of levels of parenUtes~-s and brackets to move out to find the anaphor being referred to. For example, the (PERSON :: ) in
(RUN INTO TROUBLE &ROLES (SUBJECT : &C (PERSON :: ))),
slands for (PERSON (RUN INTO TROUBLE)).
Spaces are nonnally insignificant in BRAND x except to delimit atomic symbols. In the case of colon anaphora, however, spaces may not be placed between the colons. Thus, in the above, if we had written
(PERSON : :}
inslead. it would have been read as
(PERSON (SUBJECT [RUN INTO TROUBLE)] (SUBJECT (RUN INTO TROUBLE])).
When writing non-unique list structure, the colon anaphor is not only a convenience but more essential. because rewriting an expression cannot create uniquely the same one as a previous instance. Thus, if we wished to form a stmcture like that of the simpler example above, but from non-unique lists, we could write
(RUN INTO TROUBLE &ROLES (SUBJECT : &C PERSON)), which is not equivalent to the fully written-out version (RUN INTO TROUBLE &ROLES
(SUBJECT (RUN INTO TROUBLE) &C PERSON)),
because the two expressions (RUN INTO TROUBLE) are not EQ in the second case.
A naphora provide a fonn of local labeling. They also permit the printing of dr<·ular structures, and are capable of extension to pennit reading of all such stmcturcs as well. 14
Syntax
To recapitulate the syntax of BRAND x fomt:~ly, we present an extended IINF description:
<x-expr> :: · <Lisp-atom> 1 (<x-upr-body>) I
[<x-expr-body>] 1 <labef-spec> I <colon-anaphor> 1 <quoted-form> I <backquoted-form> I <conrna-form> <x-expr-body> : : · {<label : x-expr>·} <crlterial-ex.pr> {<prop-specs>}' <criter1al-expr> : : · {<x-expr>}' { . <x-upr>} I <ilk : x- exp r > ·< tie: x- exp r> <cut : x -expr> <nrop-spac> : := &<prop :x-expr> {&<prop :x-expr>} {<··al :x-expr>}+ <label-spec> : :· !<x-expr> <colon-anaphor> : : · { :}+ <quoted-form> :: · '<x-expr> <backquoted-form> :: · · <x-expr> <commJ-form> :: · , <x-expr>
In the above. we have used braces ( { . . . } ) to indicate optional phrases, · and + as superscripts on optional phmscs to indicate zero or more and one or more pennitted repetitions, respectively. Metasyntactic variables are in angle brackets (< . . . >): such a variable of the form <name:type> is an expressive variant of just <type>-thus, <prop:x-expr> is merely <x-expr> with a suggestion of its meaning as a property descriptor. Spaces arc not significant, except as separators and as noted above between successive colons in colon anaphors. Note that although any x-expr is acceptable as a label, by convention we will use only atomic symbols. Quotation is as in LisP, so that 'X is a convenient abbreviation of (QUOTE X):
Backquoted forms and comma forms require a little explanation because, although they arc commonly used in MACI.ISP, they are not innately part of LISP. lhey provide a facility for abbreviating programs which are to construct structures of a particular form. For example, the form
'(A B (C ,D) ,E (F G)) is read as (LIST 'A 'B (LIST 'CD) E '(F G)).
Variable parts of such a structure are preceded by a comma. Other parts are quoted if they are constants or formed up by the appropriate BRAND x operation.
IMPLEMENTATION
BRAND x is implemented in MACLISP as a number of functions, hooks into the reader. printer and evaluator which are provided by the base language, and objects implemented as MACI.ISP HUNK structures.
Representation of Objects and Properties
Unique and canonical lists and all triples are represented by MACI.JSP objects of type HUNK4. For list types, the CAR and CDR of the hunk are the CAR and CDR of the object, and a third component identifies the object as a BRAND x enti1y and holds its property list For triples. the hunk ·contains the ILK. TIE and CUE of the triple as well as the component which identifies _its type and holds its property list. The ILK of a triple is the CAR of its hunk. 'fliis is the only storage structure decision allowed to be visible at the language level. because it allows efficient algorithms which use the CAR- 1 function to retrieve unique or canonical objects whose CAR or ILK is the given object.
All unique and canonical objects are indexed under the CAR -1 property of their CAR or ILK; this is needed to enable BRAND x to find such an object given its components. This indexing is not symmetrical between the CAR and CDR; therefore, finding such an object among many with the same CAR is polenlially costly. At the cost of additional overhead in storage, a CDR -1 propelty could also be maintained and the search could be optimized. There is also other independent motivation for that property, to permit a user-level CDR -1 function. but we have so far not been persuaded to pay the storage cost lor its pos.~ible benefits. Label attachments are recorded under the LABEL and LABEL -1 properties of the object and label, respectively.
Unfortunately MACl.ISI' does not provide any way to prevent the rom ponents of user-defined types from being examined and altered by the system's primitive funttions. The integrity of a HRAND x data base can be seriously disruptcd by indiscriminately applying operations such as RPLACA and RPLACD ,o unique or canonical structures. Similarly. careless changing of the properties used by BRAND x can lead to trouble. Were BRA:-<D x implemented in a strongly-typed language with good modularity and information-hiding practices (e.g., CLU (8)). these problems could be avoided. Our planned implementation on the Lisp Machine will also be able to avoid them by similar means.
Numbers are made unique by a hashing scheme which uses MACLISP's SXHASH function. The hash table is also used to store the numbers' property lists. This method assures that EQUAL numbers, which arc not generally EQ in MACLISP. can share properties. llte primitive type of the numbers matters, and the fixed number I is different from the floating number 1.0.
Other non-atomic-symbol MACL.ISP objects, including normal list struc tures. are associated with properties by another hashing scheme based on the object's address. Only those objects are in the table which have properties. and the storage cost here is minor.
Interactions with the Lisp System
MACLISP gives primitive support for user-defined extended data types built as HUNKs. The I.ISP primitive functions EVAL, PRINT, EQUAL, SUBST and SXHASH, when applied to a hunk which is identifiable as an instance of a user-defined extended data type. �~l a handler function instead of performing their normal action. This mechanism is used in BRAND x to permit a completely integrated use of BRAND x objects in usP code and data.
The LISP printer has been augmented and put under the control of several flags. Printing in LISP's READ-EVAL·PRINT loop uses a pretty-printer which displays not only a formatted version of the expression to be printed but also its label, if present, and its properties. Anaphora are also used to abbreviate printout and to print circular structures.
The LISP reader has been augmented by the definition of reader-macro functions for characters such as "(" and "[" which direct the parsing of input expressions as specified in the description of the notation. above. The primitive LISP reader continues to be used for reading symbols and numbers. Implementation of the reader, especially because of difficult interactions between the use of anaphora and backquote. was especially difficult. lndee<l. although we hal'e been able to identity algonthms lor reaoua~; ., acast non canonical innately circular structures, we have not yet implemented them because of their difficulty.
In the course of developing URAND x syntax. we have also designed a reader extension for MACLISP to allow the mapping of different actual characters onto the virtual character set of the language. In tht.-se terms. DR AND X expressions are read in terms of virtual chamcters such as BEGIN -UN I QUE LIST and PROPERTY- INDICATOR, which arc mapped in the standard reader environment onto the characters "[" and "&". Such a mechanism. called an ear aner a suggestion of Gerald J. Sussman, pennits various I.ISP extension packages to be used together without causing syntactic conflicts; all that is required is to map the total set of logical characters needed in an application onto the available physical character SeL This facility is being implemented by Glenn Burke both for MACLISP and the Lisp Machine.
Evaluation
What should it mean to evaluate (in the sense of usP's EVAL) various BRAND x objects? By default, we treat evaluation of unique and canonical list structure just as if the lists were nom1al I.ISP lists. Thus, evaluating the expression
[CAR [QUOTE (A . B]]]
is no different from ev;~uating
(CAR (QUOTE (A . B))) Again by default. we say that EVAL cannot be applied to a triple; it yields an error.
Our intent is that this hook into the action ofusr's evaluation mechanism should serve as the basis for a more sophisticated evaluator to work on declarative structures of greater complexity than LJSI' s-expressions. An experimental version of such an interpreter has been programmed by Glenn Burke. 1 ' providing pattern-directed invOGation of procedures by examining the database of methods. Triples are used to express a hierarchic a·k·o slructure in which methods for evaluation are inherited. More specific ideas on how such interpretation ought to be organized will be given elsewhere [10), and other interpreter implementations arc planned. One imoortant criterion of these is that they arc Ill interface mnsi·;tently wilh l.ISI''s nomtal action of cvalualion-evaluating a simple I.LSI' expression should be the s;nnc in IIRA!':Il X as in LISP.
ANOTHER PUZZLE-WITH LABELS
Included here is a short discussion of a number of problems which can arise in the use of labels. These problems arc nut easily solved. and arc solved not at ;~I or only badly by the current implemelllalion of BRAND x.
The intent of a label is 10 be simply an abbreviation Ibr the object it labels. If labels were used only after the object they labeled was created. and if labels were never reassigned. then these problems would not arise. However. because of the possible need lbr mutual recur>il'e reference in d11la srmctures, and because of the more frequent need to refer to something in an interactive environment before having completely defined il. labels do get used before they arc assigned. The implementor of a system must choose some representation for. an unassigned label <Uld must decide how such an object can be used. One possible choice is to ban all use of such objects, but this fails the criteria outlined above and is also dimcult to implement in a language like LISP, in which informHtion hiding is impossible. Another choice allows reference to these objects but not an examinaliun of L11eir components. This would pcm1it the use of unassigned labels In constructing other objects. but would prohibit asking for. say, the CAR ol such an object. lltis is also impossible to implement in LISP, and any allempl to enforce such conventions systematically would be very expensive; many algorithms can be significan~y sp~cded up if they need not handle a special case of unassigned labels because the implementor knows Ihat the lr<it nlready in use in the algorithm will al;o succeed or f;til appropriately for these. Therefore, BRAND x permits the examination of the representation of unassigned labds. which have a standard internal structure.
However, the use of labels before they arc assigned creates very serious problems:
If an object and an unassigned label arc both used to construct other objects. and then if that label is assigned to that object. then there is in general no good way to assure that all previous uses of the two will indeed refer to the identical object. Thus. formerly-made references to the label will not be EQ to formerly-made references to the object. This could be fixed only by an elaborate indexing mechanism which keeps track of the use of all unassigned labels, or by lliJ alternative mechanism which scans the entire data base for uses of the label (references to iL~ dummy object) and replaces them with the actual object. An alternative. possibly available on different computer architectures, would be to define EQ to follow dat;t indirections ("hidden pointers") before making address comparison tcsiS, but this is not generally feasible. This problem is easily avoided (as it is in the current BRAND x implementation) if the label is unused before its assignment; then, the dummy object is never created. If the label has been used, but the object to which it is assigned has not yet been created, the problem is ;~so avoidable if the object can be created "on top of' the dummy object repre-senting the label. This is done in the current BRAND x whenever it can be; it fails if the underlying I.IS? data types of the intended object and the dummy object are distinr.t-e.g., if a formerly used dummy label (whose default is created as a UCONS or UTRIPLE, with underlying I.ISP data type flUNK4), is then assigned to a LIST.
Canonicalization of data structure can fail because some identity that depends on label assignment may not be known when it is computed. For example, [A B C] and (CCDNS 'A 'I FOO) may appear to have little in common; yet, if [B C] appears and [FOO = B C] is later done, the two expressions are seen to be identical. However. the second canonical structure was created before this was known, and cannot be simply made to be EQ to Itte first. llte same problem also appears when labels are used as a mechanism for creating circular stmctures. For inslance. after [ FOO = BAR . I FOO], we have a new stmcture whose CAR is BAR and whose CDR is itself. Repealing this operation with different labels will create distinct such stmctures, although of cour>e there should be only one because il is canonical. This is again the problem we have described in our earlier discussion of the punl~ 'Jf the canonicity of circular structures.
CONCLUSION
We have described a limited set of extensions to LISP to support its use for implementing semantic networks. The principal features given in BRAND x arc lhe ability to create unique and canonical list and triple structures. the availability of property lists on all objects, labeling of any object, reading and printing of objects and lheir properties, and lhe integration of IIRI\ND x objects into lhe standard LISP environment so lhat lhey appear as first-class data types lO lhe ORAND X user.
This package is available in lhe MACLISP environment and will shortly be made available on lhe Lisp Machine. h is currcnlly beu1g used as lhc representation medium for an English Query System EQS and several smaller projects of U1e authors and our colleagues. So far, it has satisfied its design mandate. to provide us a useful set of extensions to our favorite implementation language, LISP, wilhout overcommitting us to decisions best len lO a higher level of language design.
ACKNOWLEDGMENTS
The authors would like lO lhank Mr. Glenn S. Burke for his invaluable advice and programming help in lhe construction of ORAND x, especially in integrating it into lhe MACI.ISP system. This research was supported (in part) by lhe National Institutes of Heallh Grant No. I POI LM 03374-Q2 from lhe National Library of Medicine, and by lhc Defense Advanced Research Projects Agency (DOD) monitored by the Office of Naval Research under Contract No. NOOOI4·7S·C-<l661.
NOTES
- For example, ntack suggests (1] that we consider a universe consisting only of two Indistinguishable balls in orbit about each other. We have absolutely no features to tell "which ball is which," yet we would hesitate to claim that the two balls are the same.
- Jloth are defined more technically, of course. EO is defined as identity of address, :md lQUAL is defined as a recursive test which checks for the identity of primitive onjccl~ and tne cqualny ol constituents of coutpoun<l objects. EQUAL L~ further modified so that equality of numbers is tested by identity of type aod numerical equality (.c - y = 0) of the values.
- Even this has exceptions. as l.ISP's INTERN actually stores its representative instances in an OBLIST or OBARRAY. of which multiple versions may be maintained. In addition. some l.ISP functions can create atomic symbols without interning them. To add to the possible confusion, l.ISP's definition of EQUAL unfortunately yields false when two symbols arc SAMEPNAMEP but not EO.
- BRAND X exists in versions which either include or do not include support for triples. Such support may be omiucd simply to save a small amount of the (virtual) memory space used by the system for large applications which do not require the type. Although this was initially an important design consideration for us, experience indicates that all significant applications use triples. The remainder of this discussion will assume that they are present
- There is no reason why notions of uniqueness and canonicity could not be extended to these other structured objects as well, but this was deemed unnecessary and is not currently done. The extension would be done in analogy with the definitions for list structure and triples (two- and three-clement structures). although more efficient indexing schemes may be needed for larger structures.
- This issue is equivalent to the previously-cited question of whether two identical objecL< can even be spoken of as two objects. There is alm05t a formal equivalence between this puzzle and the problem of the universe of two balls.
- Note that this applies only to structures which arc circular in that they contain themselves as their own criteria! parts. Circularity in the more conventional form of self or mutual reference by links ~ fully supponed.
- 'Ibis problem is familiar to all USP users who have tried to tell whether an atomic symbol has already been illlcrncd: merely typing the symbol interns it
- Sec the later discussion of BRAND X syntax. A formal definition may be found in the Usp Machine Manual (17].
- 10 It might perhaps have bocn beucr to redefine the original functions and thus to avoid having both GET aod GETP. We decided. however, to leave the original functions unchanged so that users depending on their error detection capabilities would not be misled.
- This is not completely' true. as some data types (e.g., arrays in MI\CUSP) have no printed representation, and furthermore, circular structures (those which include themselves as a part) cannot normally be printed.
- Note that in a BRAND X without triples. the asterisk has no special significance and. for example. ( A·8 C) would be read as a list of two atoms, A 0 8 and C.
- The rationale for this is that MACLISP's LIST· function, which forms successive conscs of its ar~umcnts (e.g., ( ll S T· ' A '8 'C) ~ equivalent to (CONS 'A (CONS
- '8 'C)). which is of course (A 8 C)), yields just its single argument i( given only one argument.
- Tcchnically, the formation of tmly circular cxp1eso;ions present' some difficulties more severe 1han those encountered on forming structures that arc circular through p10pcrty auachmenl~. For example. in form in~ the structure [A [ 8 : ] ] (whose CADADR is [Q 10 itself), we appear to need the whole structure bch>1c we can forrn its substructure. Because of lhc dillkultics noted earlier. IIRI\ND X docs not now suppon an input S)ntax for circular structures of the kind in which an expression is its own suhc.·t>rcs.<ion. If such an expression is formed (e.g., by RPLACA). however, the printer v.ill print it with anaphora.
- Private communication.
@inproceedings{ijcai1981p179,
title = {Brand X: LISP Suport for Semantic Networks},
author = {Szolovits, Peter and Martin, William A.},
booktitle = {Proceedings of the Seventh International Joint Conference on
Artificial Intelligence, {IJCAI-81}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick J. Hayes},
pages = {940--945},
year = {1981},
month = {8},
note = {Programming Environments},
url = {https://ijcai.org/proceedings/1981/179},
}
TY - CPAPER TI - Brand X: LISP Suport for Semantic Networks AU - Szolovits, Peter AU - Martin, William A. T2 - Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81 PB - International Joint Conferences on Artificial Intelligence PY - 1981 SP - 940 EP - 945 UR - https://ijcai.org/proceedings/1981/179 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards