UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A procedural approach to constructions in euclidean geometry Funt, Brian V. 1973

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1973_A6_7 F85_7.pdf [ 3.32MB ]
Metadata
JSON: 831-1.0051786.json
JSON-LD: 831-1.0051786-ld.json
RDF/XML (Pretty): 831-1.0051786-rdf.xml
RDF/JSON: 831-1.0051786-rdf.json
Turtle: 831-1.0051786-turtle.txt
N-Triples: 831-1.0051786-rdf-ntriples.txt
Original Record: 831-1.0051786-source.json
Full Text
831-1.0051786-fulltext.txt
Citation
831-1.0051786.ris

Full Text

A PROCEDURAL APPROACH TO CONSTRUCTIONS IN EUCLIDEAN GEOMETRY by BRIAN V. FUNT B . S c , U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1971 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n t h e De p a r t m e n t o f Computer S c i e n c e We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH O c t o b e r , 1973 COLUMBIA In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the requirements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head o f my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be allowed without my w r i t t e n p e r m i s s i o n . Department o f Computer Science The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date October 9. 1973 A b s t r a c t A p r o b l e m s o l v i n g program c a p a b l e o f h a n d l i n g h i g h s c h o o l l e v e l E u c l i d e a n geometry s t r a i g h t - e d g e and compass c o n s t r u c t i o n s h as been w r i t t e n . F i g u r e s a r e c o n s t r u c t e d by d i s c o v e r i n g , f o r t h e p o i n t s c o m p o s i n g them, t h e l o c i which s a t i s f y t h e g i v e n s e t s o f c o n s t r a i n t s . The r e p r e s e n t a t i o n o f g e o m e t r i c knowledge i s p r o c e d u r a l . The r e l a t i o n t o t h e o r e m p r o v i n g i n g e o m e t r y , and a s p e c t s o f t h e l a n g u a g e PLANNER, which was used i n t h e i m p l e m e n t a t i o n o f t h e p r o g r a m , a r e d i s c u s s e d . T a b l e Of C o n t e n t s I n t r o d u c t i o n 1 I B a c k g r o u n d And P r e l i m i n a r y Remarks 5 1.1 R e l a t e d Work 5 1.2 The Domain 8 1.3 The P a t t e r n Of Two L o c i 8 I I The CONSTRUCTOR ....14 I I . 1 O v e r v i e w .14 I I . 2 C o n s e q u e n t Knowledge ., 17 I I . 2 . A The L o c i S p e c i a l i s t s .......18 I I . 2 . B The L i n e And S l o p e S p e c i a l i s t s ..24 I I . 2 . C A n g l e S p e c i a l i s t s 25 I I . 2 . D A s s u m p t i o n S p e c i a l i s t s ....26 11.3 I n p u t And P h r a s e S p e c i a l i s t s ........27 11.4 P o i n t O r d e r i n g And A s s u m p t i o n ........32 11.5 S o l u t i o n a b s t r a c t i o n 34 11.6 B a s i c C o n s t r u c t i o n s ....36 11.7 C a n o n i c a l Naming .37 11.8 Flow Of C o n t r o l 38 I I I Comments On PLANNER ............41 IV CONSTRUCTOR O u t p u t 48 V D i r e c t i o n s F o r F u r t h e r R e s e a r c h .....55 VI C o n c l u s i o n 59 V I I B i b l i o g r a p h y .......62 V I I I A p p e n d i x I 64 IX A p p e n d i x I I 65 i i T a b l e o f F i g u r e s I C o n s t r u c t a t r i a n g l e g i v e n t h e b a s e , t h e v e r t e x a n g l e and a s i d e . . . . . . . . . . 1 1 I I F l o w c h a r t .40 I I I C o n s t r u c t a t r i a n g l e g i v e n t h e t h r e e medians ..58 i i i Acknowledgement I w i s h p a r t i c u l a r i l y t o t h a n k Dr. Raymond R e i t e r , my t h e s i s s u p e r v i s o r , f o r h i s w e a l t h o f i d e a s and i l l u m i n a t i n g c r i t i c s m ; Dr. R i c h a r d R o s e n b e r g who o r i g i n a l l y i n t e r e s t e d me i n A r t i f i c i a l I n t e l l i g e n c e ; and K a r e n f o r h e r l o v e and i n s p i r a t i o n . 1 I n t r o d u c t i o n One o f t h e a n c i e n t and t r a d i t i o n a l r e a l m s o f p r o b l e m s o l v i n g i s p l a n e g e o m e t r y . The c o n t i n u e d r o l e o f g e o m e t r y i n t h e h i g h s c h o o l c u r r i c u l u m i s j u s t i f i e d n o t b e c a u s e o f i t s t h e o r e t i c a l i m p o r t a n c e , b u t b e c a u s e i t c o n t a i n s a w e a l t h o f p r o b l e m s f o r t h e t e a c h i n g and e x e r c i s e o f r i g o r o u s t h o u g h t . P l a n e g e o m e t r y and d i a g r a m s a r e i n s e p a r a b l e , and t h i s f a c t l e n d s a c o n c r e t e n e s s t o geometry which i s a b s e n t i n many o f t h e o t h e r domains o f r i g o r o u s t h i n k i n g . Geometry p r o b l e m s a r e n o t »toy p r o b l e m s 1 ; t h e y a r e p r o b l e m s w h i c h have been s t u d i e d f o r m i l l e n n i a . The c h a r a c t e r i s t i c s w h i c h make geometry s u c h an e x c e l l e n t a r e a f o r t h e t e a c h i n g o f p r o b l e m s o l v i n g a l s o make i t good f o r t h e s t u d y o f p r o b l e m s o l v i n g . ' S y s t e m s f o r p r o v i n g t h e o r e m s i n g e o m e t r y have been d e v e l o p e d by G e l e r n t e r , 1 + 2 and G o l d s t e i n . ' » H. G e l e r n t e r e t a l , " E m p i r i c a l E x p l o r a t i o n s o f t h e Geometry-Theorem P r o v i n g M a c h i n e , " Computers and T h o u g h t , ed. E.A. Feigenbaum and J . Feldman, (New Y o r k : HcGraw"~Hill7 1963) pp.153-163. 2 H. G e l e r n t e r , " R e a l i z a t i o n o f a Geometry-Theorem P r o v i n g H a c h i n e , " C o m p u t e r s and T h o u g h t , pp.134-152. 3 I r a G o l d s t e i n , E l e m e n t a r y Geometry Theorem_Proving, (Cambridge, H a s s . : M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1973) A l Nemo no. 280. 2 Work has a l s o been done on r e l a t e d p r o b l e m s : Wong* has d e v i s e d a s e t o f h e u r i s t i c s f o r c o n s t r u c t i o n s i n a p r o o f ; P r i c e s has exam i n e d t h e p r o b l e m o f d r a w i n g a d i a g r a m t o s a t i s f y t h e c o n s t r a i n t s s p e c i f i e d i n t h e h y p o t h e s i s o f a t h e o r e m . What i s c o n s i d e r e d h e r e i s t h e s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m . G i v e n a c o m p l e t e and c o n s i s t e n t s e t o f g e o m e t r i c c o n s t r a i n t s , t h e p r o b l e m i s t o c o n s t r u c t t h e f i g u r e which s a t i s f i e s them. T h i s p r o b l e m r e l a t e s t o t h e o t h e r p r o b l e m s m e n t i o n e d . P e r f o r m i n g a c o n s t r u c t i o n i s a f o r m o f th e o r e m p r o v i n g ; t h e theorem b e i n g p r o v e n i s t h a t t h e r e e x i s t s a s o l u t i o n f i g u r e s a t i s f y i n g t h e c o n s t r a i n t s . I n a d d i t i o n , some t h e o r e m p r o v i n g a b i l i t y i s r e q u i r e d f o r t h e p r o o f o f lemmas e x t e n d i n g what i s g i v e n t o o t h e r f a c t s c o n c e r n i n g t h e s o l u t i o n f i g u r e o r o t h e r a u x i l i a r y f i g u r e s u s e d i n i t s c o n s t r u c t i o n . A p r o c e d u r a l r e p r e s e n t a t i o n i s used f o r t h e r e q u i r e d g e o m e t r i c k n o w l e d g e . E a c h d e f i n i t i o n o r theorem i s c o d e d a s a p r o c e d u r e which d e t e r m i n e s whether i t s c o n d i t i o n s a r e met and i t s r e s u l t a p p l i c a b l e . T h i s p r o c e d u r a l knowledge i s e x p r e s s e d * R i c h a r d Wong, C o n s t r u c t i o n H e u r i s t i c s f o r Geometry and a V e c t o r A l g e b r a R e p r e s e n t a t i o n o f Geometry, (Cambridge, Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1972) T e c h n i c a l Memo no.28. 5 K e i t h P r i c e , " S a t i s f y i n g G e o m e t r i c C o n s t r a i n t s , " ( C ambridge, Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1971) u n p u b l i s h e d B a c h e l o r » s P a p e r . i 3 i n s u c h a way a s t o a i d i n t h e s e a r c h f o r t h e l o c i o f p o i n t s w h i c h s a t i s f y t h e c o n s t r a i n t s o f t h e p r o b l e m . When a p p r o p r i a t e l o c i a r e f o u n d t h e p r o b l e m i s s o l v e d . The a u t h o r has w r i t t e n a program, c a l l e d t h e CONSTRUCTOR, i n MICRO-PLANNER* ( t h e s u b s e t o f H e w i t t ' s l a n g u a g e PLANNER 7 which has t h u s f a r been implemented) f o r the s o l u t i o n o f s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m s . The program a c c e p t s t h e p r o b l e m d e s c r i p t i o n i n r e s t r i c t e d E n g l i s h , and p r o d u c e s an a l g o r i t h m d e s c r i b e d i n E n g l i s h f o r t h e c r e a t i o n o f t h e s o l u t i o n f i g u r e . P o l y a , 8 who has s t u d i e d p r o b l e m s o l v i n g i n o r d e r t o t e a c h i t , u s e s t h e c o n s t r u c t i o n p r o b l e m a s a medium f o r t h e c o m m u n i c a t i o n o f some ' p a t t e r n s * o f r e a s o n i n g . By p o i n t i n g o u t t h e common t h r e a d r u n n i n g t h r o u g h t h e s o l u t i o n s o f many p r o b l e m s he hopes t h a t t h e r e a d e r w i l l , a f t e r w o r k i n g many e x e r c i s e 6 G.J. Sussman e t a l , MICRO-PLANNER B e f e r e n c e Manual, (Cambridge, Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1971) AI Memo no. 203A. * 7 C a r l H e w i t t , D e s c r i p t i o n and T h e o r e t i c a l A n a l y s i s ( U s i n g Schemata}, .of .PLANNER: A Language f o r P r o v i n g Theorems_and M a n i p u l a t i n g M o d e l s i n a R o b o t , (Cambridge, Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1972) R e v i s e d Ph.D. D i s s e r t a t i o n , AI T e c h n i c a l R e p o r t no. 258. 8 George P o l y a , M a t h e m a t i c a l D i s c o v e r y : On U n d e r s t a n d i n g , L e a r n i n g , and T e a c h i n g P r o b l e m S o l v i n g , (New York: John W i l e y a n d S o n s , 1 9 6 2 ~ V o l . ~ 1 . 4 p r o b l e m s , i n t e r n a l i z e t h e u n d e r l y i n g p a t t e r n o f r e a s o n i n g . T h i s work i s an a t t e m p t t o i n c o r p o r a t e s u c h p a t t e r n s a s an i n t e g r a l p a r t o f a p r o b l e m s o l v i n g program. 5 I B a c k g r o u n d And P r e l i m i n a r y Remarks I i i R e l a t e d _ W o r k A l t h o u g h work has been done on o t h e r a s p e c t s o f p l a n e g e o m e t r y by r e s e a r c h e r s i a A r t i f i c a l I n t e l l i g e n c e , no e x p l o r a t i o n has been made o f t h e s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m c o n s i d e r e d h e r e . The main e m p h a s i s has been on machine p r o o f o f g e o m e t r y t h e o r e m s , t h e e a r l i e s t and most f a m i l i a r work i n t h i s r e g a r d b e i n g t h a t o f G e l e r n t e r and h i s c o - w o r k e r s . 9 The most i n t e r e s t i n g f e a t u r e o f t h e Geometry M a c h i n e i m p l e m e n t e d by G e l e r n t e r , and t h e c h i e f r e a s o n f o r i t s s u c c e s s i n p r o v i n g m o d e r a t e l y d i f f i c u l t t h e o r e m s , i s t h e i n t r o d u c t i o n o f s e m a n t i c s i n t o t h e p r o o f p r o c e s s by t h e use o f a d i a g r a m a s a model. A MICRO-PLANNER program c a l l e d BTP ( B a s i c Theorem P r o v e r ) h a s been w r i t t e n by G o l d s t e i n . * ° A p r o c e d u r a l a p p r o a c h i s used t o i n c o r p o r a t e and e x t e n d t h e i d e a s embedded i n t h e Geometry M a c h i n e . The e s t a b l i s h e d geometry theorems and d e f i n i t i o n s o f which BTP's knowledge i s composed, a r e e x p r e s s e d a s PLANNER * G e l e r n t e r e t a l . Computers and T h o u g h t , pp.134-163. *o G o l d s t e i n , E l e m e n t a r y Geometry Theorem P r o v i n g . 6 p r o c e d u r e s w h i c h G o l d s t e i n c a l l s • e x p e r t s 1 . I t a p p e a r s t h a t t h e e f f o r t i n v o l v e d i n t h e i m p l e m e n t a t i o n o f BTP was s u b s t a n t i a l l y l e s s t h a n t h a t o f t h e Geometry M a c h i n e . T h i s s a v i n g i s a t t r i b u t a b l e t o t h e p r o c e d u r a l a p p r o a c h which a l l o w e d G o l d s t e i n t o c o n c e n t r a t e more on t h e m a t h e m a t i c s and l e s s on t h e programming. The p r o c e d u r a l a p p r o a c h has been a d o p t e d i n t h i s t h e s i s . G o l d s t e i n a l s o d i s c u s s e s a ' p l a u s i b l e move g e n e r a t o r * w h i c h would d e c i d e t h e o r d e r i n which t h e ' e x p e r t s 1 s h o u l d be t r i e d r a t h e r t h a n s i m p l y l e t t i n g t h e r i g h t one be f o u n d by PLANNER f a i l u r e and b a c k u p . BTP, however, i s a l l t h a t G o l d s t e i n has i m p l e m e n t e d t h u s f a r . Even w i t h o u t t h e ' p l a u s i b l e move g e n e r a t o r ' , BTP has been a b l e t o p r o v e a l l t h e t h e o r e m s which t h e Geometry M a c h i n e p r o v e d . N e i t h e r t h e Geometry Machine n o r BTP c r e a t e t h e d i a g r a m w h i c h t h e y u s e t o f i l t e r i n v a l i d s u b g o a l s . A d i a g r a m must be p r e s e n t e d t o b o t h programs by t h e u s e r o f t h e s y s t e m . P r i c e has e x p l o r e d t h e p r o b l e m o f c r e a t i n g a d i a g r a m f r o m t h e c o n s t r a i n t s i m p l i c i t i n t h e h y p o t h e s i s o f a t h eorem, and has o u t l i n e d b u t n o t i m p l e m e n t e d , an a l g o r i t h m f o r s o l v i n g t h e p r o b l e m . T h i s p r o b l e m may a t f i r s t a p p e a r t o be t h e same o r v e r y s i m i l a r t o t h e s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m c o n s i d e r e d i n t h i s work; however, t h e r e a r e s e v e r a l c r u c i a l d i f f e r e n c e s . The c o n s t r a i n t s c o n t a i n e d i n t h e h y p o t h e s i s o f a theorem i n g e n e r a l do n o t t o t a l l y c o n s t r a i n t h e f i g u r e . I t i s p o s s i b l e t h a t one o r more l e n g t h s o r a n g l e s i n t h e f i g u r e may be c h o s e n f r e e l y . 7 P r i c e t h i n k s o f t h e number o f s u c h c h o i c e s as t h e d e g r e e o f f r e e d o m o f t h e d i a g r a m . I n a s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m t h e d e g r e e o f f r e e d o m o f t h e s o l u t i o n f i g u r e i s z e r o . Whereas t h e method o f c o n s t r u c t i o n i n a s t r a i g h t - e d g e and compass p r o b l e m i s r e s t r i c t e d a s i m p l i e d by t h e name, t h i s i s n o t t h e c a s e when d r a w i n g a d i a g r a m f o r a theorem p r o v e r ; any t e c h n i q u e , s t r a t e g y , o r t o o l c a n be u s e d . P r i c e s u g g e s t s c a l l i n g a c o n s t r u c t i o n r o u t i n e b a s e d upon t h e h e u r i s t i c s P o l y a d i s c u s s e s i n r e l a t i o n t o t h e s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m . " I n t h e a c t u a l c o n s t r u c t i o n o f a f i g u r e , g i v e n some e l e m e n t t o u s e , I depend on t h e work o f G. P o l y a i n h i s c h a p t e r on s o l v i n g c o n s t r u c t i o n p r o b l e m s . " 1 * A l t h o u g h t h e s e h e u r i s t i c s would u n d o u b t e d l y bei u s e f u l i n t h e p r o b l e m P r i c e c o n s i d e r s , t h e y s h o u l d be g e n e r a l i z e d t o e l i m i n a t e t h e r e s t r i c t i o n o f l o c i t o s t r a i g h t l i n e s and c i r c l e s . The main t h r u s t o f P r i c e ' s a l g o r i t h m i s t o a n a l y s e t h e d e g r e e o f f r e e d o m o f t h e f i g u r e t o be drawn; c h o o s e v a l u e s f o r as many u n c o n s t r a i n e d e l e m e n t s o f t h e f i g u r e as t h e r e a r e d e g r e e s o f f r e e d o m , t h e r e b y f u l l y c o n s t r a i n i n g t h e f i g u r e ; and t h e n t o p a s s t h i s new p r o b l e m t o a c o n s t r u c t i o n r o u t i n e . I t i s t o t h i s l a s t 1 1 P r i c e , " S a t i s f y i n g G e o m e t r i c C o n s t r a i n t s , " p.11. 8 s t e p t h a t work on t h e s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m i s most d i r e c t l y r e l a t e d . I i 2 The Domain The p r o b l e m domain i s a s u b s e t o f t h e c l a s s o f s t r a i g h t - e d g e and compass c o n s t r u c t i o n s . U n der t h e r e s t r i c t i o n t h a t o n l y a s t r a i g h t - e d g e and compass be u s e d , t h e p r o b l e m i s t o c o n s t r u c t a f i g u r e w hich s a t i s f i e s a l i s t o f c o n s t r a i n t s . The t y p e o f f i g u r e d e a l t w i t h h e r e has been l i m i t e d t o t h a t o f t r i a n g l e s and c i r c l e s ; however, t h e m a j o r i t y o f c o n s t r u c t i o n p r o b l e m s c o n c e r n them. A l t h o u g h c o n s t r u c t i o n p r o b l e m s r a n g e f r o m t h e v e r y d i f f i c u l t (or e v e n t h e i m p o s s i b l e t r i s e c t i o n o f an a n g l e ) t o t h e q u i t e s i m p l e , t h e p r o b l e m s used as e x a m ples a r e t a k e n f r o m h i g h s c h o o l g e o m e t r y t e x t s . The p r o b l e m s may s p e c i f y a n g l e s , s i d e s , r a d i i , m e dians, a l t i t u d e s , t a n g e n t i a l c i r c l e s , t a n g e n t i a l l i n e s , and p o i n t s on t h e c i r c u m f e r e n c e o f c i r c l e s . A l l p r o b l e m s a r e assumed n o t t o be c o n t r a d i c t o r y , and t o have a t l e a s t one s o l u t i o n . I i i ? h e _ P a t t e r n _ O f _ T w o L o c i T h e r e i s a schema i n which many s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m s o l u t i o n s may be c l a s s i f i e d . G e o m e t r i c o b j e c t s a r e s p e c i f i a b l e i n t e r m s o f key p o i n t s i n them: a t r i a n g l e by i t s t h r e e v e r t e x p o i n t s , a l i n e by two p o i n t s t h r o u g h which i t p a s s e s , and a c i r c l e by i t s c e n t e r and a p o i n t 9 o f i t s c i r c u m f e r e n c e . The p r o b l e m o f c o n s t r u c t i n g a f i g u r e c a n t h u s be c o n s i d e r e d t o be t h a t o f l o c a t i n g i t s e s s e n t i a l p o i n t s . W i t h t h e t o o l s a t hand, s t r a i g h t l i n e s and c i r c l e s may be drawn; s e t s o r l o c i o f p o i n t s a r e t h e r e b y c r e a t e d . The i n t e r s e c t i o n s e t o f two s u c h s t r a i g h t - e d g e o r compass l o c i i s e a s i l y d e t e r m i n e d d i a g r a m a t i c a l l y , and i f t h e l o c i a r e d i s t i n c t , has a t most two members. Th u s , t h r o u g h t h e c o n s t r u c t i o n o f l o c i o f t h e two a v a i l a b l e t y p e s , p o i n t s c a n be l o c a t e d . The s t a t e m e n t o f a s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m i s , i n i t s e s s e n t i a l n a t u r e , a l i s t o f c o n d i t i o n s o r r e s t r i c t i o n s which must be met by t h e f i g u r e . T hese c o n d i t i o n s c a n be r e f o r m u l a t e d i n t o c o n s t r a i n t s on t h e p o i n t s o f t h e f i g u r e . The s e t o f p o i n t s s a t i s f y i n g a c o n s t r a i n t c a n be used i n t h e c o n s t r u c t i o n o f t h e s o l u t i o n f i g u r e i f t h a t s e t f o r m s e i t h e r a c i r c u l a r o r r e c t i l i n e a r l o c u s . T h i s a p p r o a c h t o t h e s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m i s summarized by P o l y a : " F i r s t , r e d u c e t h e p r o b l e m t o t h e c o n s t r u c t i o n o f ONE p o i n t . Then, s p l i t t h e c o n d i t i o n i n t o TWO p a r t s so t h a t e a c h p a r t y i e l d s a l o c u s f o r t h e unknown p o i n t ; e a c h l o c u s must be e i t h e r a s t r a i g h t l i n e o r a c i r c l e . " 1 2 He r e f e r s t o i t a s t h e ' p a t t e r n o f two l o c i * . C o n s i d e r a s an example t h e p r o b l e m , " C o n s t r u c t a t r i a n g l e * 2 p o l y a , H a t h e m a t i c a l D i s c o v e r y , V o l . 1 p.5. 10 g i v e n t h e b a s e , t h e v e r t e x a n g l e and a s i d e . " I f we name t h e t r i a n g l e ABC, t h e b a s e BC, t h e a n g l e BAC, and t h e s i d e AB, a f t e r p l a c i n g t h e s i d e AB, p o i n t C c a n be d e t e r m i n e d u s i n g t h e • p a t t e r n o f two l o c i * . P o i n t C i s t h e i n t e r s e c t i o n o f t h e c i r c l e c e n t e r B r a d i u s BC, and t h e l i n e t h r o u g h p o i n t A a t a n g l e BAC t o BC. T h i s i s s k e t c h e d i n f i g u r e I . The s o l u t i o n o b t a i n e d by t h e CONSTRUCTOR i s g i v e n below. I n c l u d e d i s a dump o f t h e a s s e r t i o n s i n t h e d a t a b a s e as t h e y were g e n e r a t e d f r o m t h e E n g l i s h s t a t e m e n t o f the p r o b l e m . 1 3 The s o l u t i o n a l g o r i t h m i s t h e same as t h e one d e s c r i b e d a b o v e , e x c e p t i t i s more e x p l i c i t a b o u t p l a c i n g t h e f i r s t s i d e . 1 3 The a s s e r t i o n s a r e d i s c u s s e d i n d e t a i l i n s e c t i o n s I I . 3 and I I . 4 . Given: ' — — s i d e AB base BC A B FIGURE I 12 Example: ( c o n s t r u c t a t r i a n g l e g i v e n the base , the ve r t e x angle and a side) AC OF LINE2 , AND BC OF LINE3) CONSTRUCTING TRIANGLE A B C ) AB IS A SEGMENT OF LINE LINE1 BC IS THE BASE) ANGLE BAC IS A GIVEN ANGLE) AB IS A GIVEN SIDE) (LINE LINE3)) (LINE LINE2) ) (LINE LINE1)) (TRIANGLE A B C ) ) (POINT C)) (POINT B)) (POINT A)) (POINT C (CONDITION-ON C ST TRIANGLE A B C ) ) . 2 0 ) (POINT B (CONDITION-ON B ST TRIANGLE A B C ) ) . 20) (POINT A (CONDITION-ON A ST TRIANGLE A B C ) ) . 2 0 ) (C ON LINE3) ) (C ON LINE2) ) (B ON LINE3)) (B ON LINE1) ) (A ON LINE2)) (A ON LINE1) ) (KNOWN LENGTH AB)) (KNOWN ANGLE BAC)) (KNOWN LENGTH BC)) TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS A ST LOCI A ST LOCI C ST (CONDITION-ON (A B C) NO. OF (CONDITION-ON (A B C) NO. OF (CONDITION-ON (C) NO. OF LOCI FOUND: 0) (CONDITION—ON C ST TRIANGLE A B C ) ) (C) NO. OF LOCI FOUND: 1) TRIANGLE FOUND: 0) TRIANGLE FOUND: 1) TRIANGLE A B C ) ) A B C ) ) A B C ) ) ••••beginning of s o l u t i o n algorithm+*++ ((DRAW LINE LINE1 ANYWHERE) (A IS ON LINE LINE 1) (PLACE POINT B ANYWHERE ON LINE 1) (POINT A IS ON THE CIRCLE WITH CENTER B RADIUS AB) (CONSTRUCT LINE LINE2 THRU POINT A (AT ANGLE BAC TO LINE LINE 1 )(C IS ON LINE LINE2) (POINT C IS ON THE CIRCLE WITH CENTER B RADIUS BC)) 13 A l t h o u g h t h e ' p a t t e r n o f two l o c i ' i s o n l y u s e d h e r e i n t h e s o l u t i o n o f c o n s t r u c t i o n p r o b l e m s i t has a more g e n e r a l n a t u r e . P o l y a p o i n t s o u t t h a t i f t h e n o t i o n o f l o c u s i s b r o a d e n e d t o a s e t o f a r b i t r a r y i t e m s s a t i s f y i n g a r e s t r i c t i o n and t h e number o f s e t s i s two o r more, t h e p a t t e r n o f f i n d i n g t h e s o l u t i o n e l e m e n t i n t h e i n t e r s e c t i o n s t i l l p r o v e s u s e f u l . 1 4 The g e n e r a l i z e d p a t t e r n c an be s e e n : i n t h e i n t e r p l a y o f s y n t a x and s e m a n t i c s i n n a t u r a l l a n g u a g e ; i n t h e c h o i c e o f a theorem o r axiom f o r a p p l i c a t i o n i n a g e o m e t r y p r o o f f r o m t h e i n t e r s e c t i o n o f t h o s e h a v i n g a p p l i c a b l e r e s u l t s w i t h t h o s e whose r e s u l t i s t r u e i n t h e d i a g r a m ; and, o f c o u r s e , i n t h e s o l u t i o n o f a s e t o f s i m u l t a n e o u s a l g e b r a i c e q u a t i o n s . ** P o l y a , M a t h e m a t i c a l D i s c o v e r y . V o l . 1, pp. 133-138. 14 I I The CONSTRUCTOR H i ! O v e r v i e w A framework o r theme i s e s t a b l i s h e d by t h e ' p a t t e r n o f two l o c i * which has been i n c o r p o r a t e d i n t o a program f o r t h e s o l u t i o n o f geometry c o n s t r u c t i o n p r o b l e m s . The p a t t e r n i s n o t i n i t s e l f a s o l u t i o n t o t h e c o n s t r u c t i o n p r o b l e m , b ut r a t h e r an a p p r o a c h . The word ' p a t t e r n * i s used by P o l y a t o c o n n o t e t h e f a c t t h a t t h e s o l u t i o n s t o v a r i o u s p r o b l e m s have a s i m i l a r s t r u c t u r e , a s do t h e r e a s o n i n g p r o c e s s e s w h i c h l e a d t o them., The " p a t t e r n o f two l o c i ' i s a s k e l e t o n which must be f i l l e d o u t w i t h methods f o r t h e d i s c o v e r y o f t h e l o c i . * 3 One f o r m a l i s m i n which t h e p a t t e r n c a n be expanded upon i s t h a t o f f i r s t - o r d e r l o g i c . The p a t t e r n i s e x p r e s s e d by t h e e x i s t e n t i a l s t a t e m e n t / q u e s t i o n (E x y) (C1<x) & C2 (x) S . . . Cn(x) S C1 (y) 8 C 2(y) 8 . . . Cn (y) 6 ( c i r c l e (x) v l i n e (x)) 6 ( c i r c l e (y) v l i n e ( y ) ) & i n t e r s e c t i n g ( x , y ) S d i s t i n c t ( x , y ) ) where x,y a r e l o c i o f a p o i n t and C I , . . ,Cn a r e t h e c o n d i t i o n s o f t h e p r o b l e m r e l a t i n g t o t h a t p o i n t A p r o o f o f t h e p r e c e d i n g s t a t e m e n t c a n be a t t e m p t e d w i t h i n a *-s P o l y a , M a t h e m a t i c a l D i s c o v e r y , V o l . 1, pp.3-21. 15 f o r m a l s y s t e m c o n t a i n i n g a x i o m s e x p r e s s i n g t h e p r i m i t i v e c o n s t r u c t i o n s (a l i n e g i v e n two p o i n t s on i t , and a c i r c l e g i v e n i t s c e n t e r and r a d i u s ) , and t h e o r e m s . I n c l u d e d must be t h e o r e m s a b o u t t h e c o n s t r u c t i o n o f b a s i c g e o m e t r i c o b j e c t s ( d i s c u s s e d i n t h e s e c t i o n " B a s i c C o n s t r u c t i o n s " ) , a s w e l l a s t h e o r e m s c o n c e r n i n g l o c i and t h e c o n d i t i o n s t h e y s a t i s f y . When a p r o o f i s o b t a i n e d , a method f o r t h e c o n s t r u c t i o n o f a p o i n t i n t h e r e q u i r e d f i g u r e c a n be d e r i v e d f r o m i t . The e x i s t e n t i a l s t a t e m e n t / q u e s t i o n c a n be t r e a t e d d i r e c t l y i n PLANNER as a PROG o f two v a r i a b l e s . ( p r o g (x y) ( g o a l (C1 ? x ) ) ( g o a l (C2 ?x)) • • • . ( g o a l (Cn ?x)) ( g o a l (C1 ? y ) ) ( g o a l (C2 ? y ) ) • • • ( g o a l (Cn ? y ) ) (or ( g o a l ( C i r c l e ?x)) ( g o a l ( L i n e ? x ) ) ) (or ( g o a l ( C i r c l e ? y j ) ( g o a l ( L i n e ? y ) ) ) ( g o a l ( I n t e r s e c t i n g ?x ? y ) ) ( g o a l ( U n e q u a l ?x ? y ) ) ) T h i s e x p r e s s i o n o f t h e ' p a t t e r n o f two l o c i * embodies i t s e s s e n t i a l n a t u r e . The p a t t e r n i s f u r t h e r augmented t o make a f u l l s y s t e m f o r t h e s o l u t i o n o f c o n s t r u c t i o n p r o b l e m s by t h e e s t a b l i s h m e n t o f a s e t o f p r o c e d u r e s , PLANNER t h e o r e m s , r e p r e s e n t i n g t h e g e o m e t r i c knowledge o f b a s i c c o n s t r u c t i o n s and l o c u s t h e o r e m s . T h e s e p r o c e d u r e s a r e a c t i v a t e d by t h e g o a l s i n 16 t h e PROG. The i n s t a n t i a t i o n s o f t h e two PROG v a r i a b l e s a r e l o c i whose i n t e r s e c t i o n i s t h e l o c a t i o n o f a r e q u i r e d p o i n t . The CONSTRUCTOR, a MICRO-PLANNER program, e m p l o y s p r o c e d u r e s f o r t h e r e p r e s e n t a t i o n o f t h e g e o m e t r i c knowledge i t r e q u i r e s . T he u t i l i z a t i o n o f t h i s knowledge i s d i r e c t e d by t h e c o n d i t i o n s o f t h e p r o b l e m l i n k e d t o g e t h e r by t h e ' p a t t e r n o f two l o c i ' i n i t s PROG f o r m . The i n p u t t o t h e program i s a s i n g l e E n g l i s h s e n t e n c e which e x p r e s s e s t h e p r o b l e m ' s c o n d i t i o n s . O u t p u t i s a l i s t o f i n s t r u c t i o n s c o n s t i t u t i n g an a l g o r i t h m f o r t h e c o n s t r u c t i o n o f t h e f i g u r e s a t i s f y i n g t h e c o n d i t i o n s . S i n c e t h e c o n d i t i o n s a r e f i r s t s p e c i f i e d i n E n g l i s h t h e y must be t r a n s f o r m e d i n t o a more u s a b l e f o r m . T h i s t r a n s f o r m a t i o n c o u l d be made d i r e c t l y i n t o PLANNER g o a l s , w hich when amalgamated i n t o a PROG, c o u l d be p a s s e d t o t h e MICRO-PLANNER i n t e r p r e t e r f o r e v a l u a t i o n . However r a t h e r t h a n a c t u a l l y c r e a t i n g a PROG i t i s somewhat e a s i e r and more e f f i c i e n t t o w r i t e a c o n t r o l f u n c t i o n w h i c h e v a l u a t e s t h e g o a l s f o r t h e same n e t e f f e c t a s a PROG would have, b u t m a i n t a i n s g r e a t e r c o n t r o l o v e r t h e o r d e r i n which t h e y a r e e v a l u a t e d and t h e e f f e c t s o f b a c k t r a c k i n g when f a i l u r e o c c u r s . The ' p a t t e r n o f two l o c i * and t h e PROG f o r m a l i z a t i o n o f i t a r e t h e m o t i v a t i n g f o r c e b e h i n d t h e f o r m u l a t i o n o f t h e p r o c e d u r e s d e s c r i b e d i n t h e i m m e d i a t e l y s u c c e e d i n g s e c t i o n s . 17 II.. 2 C o n s e q u e n t Knowledge I n c o n s t r u c t i o n p r o b l e m s , l e n g t h s , a n g l e s , and r e l a t i o n s between p a r t s o f t h e f i g u r e t o be c o n s t r u c t e d a r e g i v e n . U s i n g t h i s i n f o r m a t i o n t o i m m e d i a t e l y b e g i n t h e c o n s t r u c t i o n o f t h e f i g u r e i s an i m p o s s i b i l i t y . A r e l a t i o n between v a r i o u s p a r t s o f t h e f i g u r e c a n n o t be d i r e c t l y r e p r e s e n t e d on a p i e c e o f p a p e r . The s o l u t i o n i s t o u s e t h e w e l l e s t a b l i s h e d a n a l y t i c method, t h a t o f w o r k i n g b a c k w a r d s f r o m t h e c o n c l u s i o n o f t h e p r o b l e m , i n t h i s c a s e t h e d e s i r e d f i g u r e , t o i t s h y p o t h e s i s , t h e i n f o r m a t i o n g i v e n a b o u t t h e f i g u r e . The f i g u r e i s d e t e r m i n e d when i t s p o i n t s have been d e t e r m i n e d , s o we have t h e f o l l o w i n g 'backward c h a i n i n g * s e r i e s o f s t e p s o r g o a l s a s t h e b a s i c mode o f o p e r a t i o n o f t h e c o n s t u c t o r . (1) C o n s t r u c t t h e f i g u r e (2) C o n s t r u c t i t s p o i n t s (3) C o n s t r u c t two l o c i on w h i c h a r e q u i r e d p o i n t l i e s . (4) C o n s t r u c t o t h e r l i n e s , p o i n t s , a n g l e s e t c . Which a r e needed f o r t h e c o n s t r u c t i o n o f t h e l o c i . 18 (n) E v e n t u a l l y i n t h e c o n s t r u c t i o n o f s u b g o a l f i g u r e s , i n f o r m a t i o n g i v e n a s p a r t o f t h e p r o b l e m s t a t e m e n t w i l l be r e q u i r e d . The l a n g u a g e , PLANNER, i s p a r t i c u l a r l y e f f e c t u a l i n t h e d e s c r i p t i o n o f ba c k w a r d s c h a i n i n g p r o c e s s e s , b e c a u s e o f i t s f e a t u r e d p a t t e r n d i r e c t e d p r o c e d u r e i n v o c a t i o n . E a c h ' p r o c e d u r e p r o c l a i m s i t s a b i l i t i e s t h r o u g h t h e use o f a p a t t e r n ; when a s u b g o a l must be s a t i s f i e d , t h e l i s t i n g s o f p r o c e d u r e p a t t e r n s a r e c u l l e d f o r t h e p r o c e d u r e most a p p r o p r i a t e t o t h e p u r p o s e . The c o n s e q u e n t knowledge o f t h e CONSTBDCTOR i s t h e r e f o r m u l a t i o n o f g e o m e t r y t h e o r e m s i n t o p r o c e d u r e s , c a l l e d s p e c i a l i s t s , 1 6 (THCONSE theorems) a b l e t o f u l f i l l g o a l s and t h e i r s u b g o a l s . II.2.A The L o c i S p e c i a l i s t s The l o c i s p e c i a l i s t s c o n s t i t u t e a g r o u p o f p r o c e d u r e s e a c h e x p e r t i n e x t r a c t i n g a l o c u s f r o m a c o n d i t i o n t h e d i a g r a m must f u l f i l l when c o m p l e t e . Each s p e c i a l i s t i s a d e p t a t t e s t i n g t h e d a t a b a s e t o d e t e r m i n e i f t h e l o c u s t o which i t p e r t a i n s i s u s a b l e i n s a t i s f y i n g t h e c u r r e n t c o n d i t i o n . A s s o c i a t e d w i t h a s p e c i a l i s t i s a p a t t e r n which must match t h e c u r r e n t c o n d i t i o n i n o r d e r f o r i t t o be i n v o k e d , i m p l y i n g t h a t o n l y s p e c i a l i s t s ** T h i s t e r m i's a d a p t e d from T. H i n o g r a d who d i s c u s s e s s e m a n t i c s p e c i a l i s t s . 19 r e l e v a n t t o t h e c o n d i t i o n expend any e f f o r t . T h e r e i s a body o f t h e o r e m s c o n c e r n i n g l o c i p r o v e n f o r t h e s t u d e n t i n most g e o m e t r y t e x t b o o k s . T h e s e t h e o r e m s r e l a t e a l o c u s t o a s e t o f c o n d i t i o n s a s i n : The l o c u s o f t h e v e r t e x o f a r i g h t t r i a n g l e , w i t h a g i v e n h y p o t e n u s e a s t h e b a s e , i s a c i r c l e upon t h e h y p o t e n u s e a s a d i a m e t e r . 1 7 T h e s e t h e o r e m s a r e i n c a r n a t e d i n t h e l o c i s p e c i a l i s t s . From some c o n d i t i o n s i t may be p o s s i b l e t o p r y more t h a n one l o c u s . S u ch c o n d i t i o n s a r e n o t p r i m i t i v e , and must be d i v i d e d i n t o t h e i r component c o n d i t i o n s b e f o r e e v e n a s i n g l e l o c u s c a n be o b t a i n e d . I n many c a s e s a c o n d i t i o n which t h e f i g u r e must meet, a s e x p r e s s e d i n t h e i n p u t , w i l l n a t u r a l l y r e s u l t i n a s i n g l e l o c u s o f p o i n t s . As an e x ample, t h e c o n d i t i o n , p o i n t C i s e g u i d i s t a n t f r o m p o i n t s A and B, i s one w h i c h r e s u l t s i n p o i n t C b e i n g on t h e p e r p e n d i c u l a r b i s e c t o r o f t h e l i n e segment AB. O t h e r c o n d i t i o n s , p o i n t A i s a v e r t e x o f t h e t r i a n g l e ABC, f o r i n s t a n c e , a r e compound i n n a t u r e and c a n be s u b d i v i d e d . I n t h i s c a s e t h e s u b d i v i s i o n i s i n t o t h e r e s t r i c t i o n : A i s d i s t a n c e AB f r o m p o i n t B, A i s d i s t a n c e AC f r o m C, A i s on t h e l i n e o f w h i c h AB i s a segment, and A i s on t h e l i n e o f which AC i s a segment. A compound c o n d i t i o n i s 1 7 A.H. H e l c h o n s , W.R K r i c k e n b e r g e r and H.R. P e a r s o n , P l a n e G eometry, ( B o s t o n , Mass.: G i n n , 1958) p. 353. ~ 20 c o n s i d e r e d t o be s a t i s f i e d i f t h e c o n j u n c t i o n o f i t s component c o n d i t i o n s i s s a t i s f i e d . The d i v i s i o n o f a compound c o n d i t i o n i n t o i t s component c o n d i t i o n s i s e a s i l y i m p l e m e n t e d i n PLANNER by c r e a t i n g one p r o c e d u r e f o r e a c h component c o n d i t i o n . Each p r o c e d u r e i s g i v e n a p a t t e r n m a t c h i n g t h e o r i g i n a l compound c o n d i t i o n . Below i s a d e s c r i p t i o n o f e a c h o f t h e l o c i s p e c i a l i s t s i n t e r m s o f t h e c o n d i t i o n t o w h i c h i t r e s p o n d s , t h e s u b g o a l s i t i n i t i a t e s , and t h e l o c u s i t r e t u r n s i f t h e s u b - c o n d t i o n s a r e met. C r A L T 1 C o n d i t i o n : S u b g o a l s : L o c u s : t h e a l t i t u d e ( d i s t a n c e ) f r o m p o i n t P t o l i n e L i s D i s L known o r c a n i t be c o n s t r u c t e d ? i s D known o r c a n i t be c o n s t r u c t e d ? P i s on a l i n e p a r a l l e l t o L which i s d i s t a n c e D f r o m L C-DIST1 C o n d i t i o n : S u b g o a l s : L o c u s : t h e d i s t a n c e o f p o i n t P f r o m Q i s D i s t h e p o s i t i o n o f Q known o r c a n i t be d e t e r m i n e d ? i s D known o r c a n i t be d e t e r m i n e d ? P i s on t h e c i r c l e o f r a d i u s D c e n t e r Q C-EQpiDIST C o n d i t i o n : t h e p o i n t P i s e q u i d i s t a n t f r o m p o i n t s Q and R S u b g o a l s : i s t h e l i n e segment QR known o r i L o c u s : C-MEDIAN1. C o n d i t i o n : S u b g o a l s : L o c u s : C-TRI2 C o n d i t i o n : S u b g o a l s : L o c u s : C-TRI3 C o n d i t i o n : S u b g o a l s : L o c u s : C-TRIU C o n d i t i o n : S u b g o a l l : L o c u s l : e q u i v a l e n t l y , a r e p o i n t s Q and R known o r c a n t h e y be d e t e r m i n e d ? P i s on t h e p e r p e n d i c u l a r b i s e c t o r o f QR p o i n t P i s t h e v e r t e x o f a t r i a n g l e from which t h e median o f l e n g t h M i s d r o p p e d t o t h e b a s e B i s t h e l e n g t h H known o r c a n i t be d e t e r m i n e d ? i s t h e m i d p o i n t o f B known o r c a n i t be d e t e r m i n e d ? P i s on t h e c i r c l e o f r a d i u s W, c e n t e r t h e m i d p o i n t o f B p o i n t P i s t h e v e r t e x o f a t r i a n g l e PQR (a compound c o n d i t i o n ) i s t h e l i n e t h r o u g h P and.Q known o r c a n -i t be c o n s t r u c t e d ? P i s on t h a t l i n e . p o i n t P i s t h e v e r t e x o f a t r i a n g l e PQR i s t h e l i n e t h r o u g h P and R known o r c a n i t be c o n s t r u c t e d ? P i s on t h a t l i n e . p o i n t P i s t h e v e r t e x o f a t r i a n g l e PQR what i s t h e l o c u s o f p o i n t s s u c h t h a t t h e d i s t a n c e o f P t o Q i s PQ th e same a s t h e r e s u l t o f s u b g o a l l S u b g o a l 2 : L o c u s 2 : C-IS0S1 C o n d i t i o n : S u b g o a l : L o c u s : C-RTTRI1 C o n d i t i o n : S u b g o a l : L o c u s : C - C I R C L E l C o n d i t o n : S u b g o a l s : L o c u s l : L o c u s 2 : what i s t h e l o c u s o f p o i n t s s u c h t h a t t h e d i s t a n c e f r o m P t o R i s PR? s u b g o a l 2 l o c u s p o i n t P i s t h e v e r t e x o f an i s o s c e l e s t r i a n g l e PQR what i s t h e l o c u s o f p o i n t s e q u i d i s t a n t f r o m Q and R? t h e r e s u l t o f t h e s u b g o a l . p o i n t P i s t h e v e r t e x o f a r i g h t t r i a n g l e PQR. i s QR a known l i n e segment? P i s on t h e c i r c l e h a v i n g segment QR a s a d i a m e t e r . p o i n t P i s t h e c e n t e r o f a c i r c l e C which i s t a n g e n t t o a c u r v e V. i s t h e r a d i u s R o f C known o r c a n i t be d e t e r m i n e d ? i s t h e c u r v e V known o r c a n i t be c o n s t r u c t e d ? i f V i s a c i r c l e , t h e n P i s on a c i r c l e whose c e n t e r i s t h a t o f V and whose r a d i u s i s t h a t o f V p l u s t h a t o f C. i f V i s a l i n e , t h e n P i s on a l i n e p a r a l l e l t o ? t h e r a d i u s o f c f r o m v. C-CIRCLE2 C o n d i t i o n : p o i n t P i s t h e c e n t e r o f a c i r c l e C w h i c h i s t a n g e n t t o a c u r v e V a t a p o i n t Q. 23 S u b g o a l s : i s V known o r c a n i t be c o n s t r u c t e d ? L o c u s l : i f V i s a c i r c l e , t h e n P i s on t h e l i n e w h i c h p a s s e s t h r o u g h Q and t h e c e n t e r o f V. L o c u s 2 : i f V i s a l i n e , t h e n P i s on the p e r p e n d i c u l a r t o V a t Q. C-CIRCLE3 C o n d i t i o n : S u b g o a l : L o c u s : p o i n t P i s t h e c e n t e r o f a c i r c l e h a v i n g Q and R a s p o i n t s on i t s c i r c u m f e r e n c e . what i s t h e l o c u s o f p o i n t s e q u i d i s t a n t f r o m Q and R? t h e r e s u l t o f t h e s u b g o a l . C-CIRCLE5 C o n d i t i o n : S u b g o a l : L o c u s l : L o c u s 2 : p o i n t P i s t h e c e n t e r o f a c i r c l e C w h i c h i s t a n g e n t t o two l i n e s . a r e t h e two l i n e s known o r c a n t h e y c o n s t r u c t e d ? be i f t h e l i n e s i n t e r s e c t , t h e n P i s on t h e b i s e c t o r o f t h e a n g l e t h e y f o r m . i f t h e two l i n e s a r e p a r a l l e l , t h e n P i s on t h e l i n e p a r a l l e l t o b o t h o f them and midway between them. One t h i n g e v e r y l o c u s s p e c i a l i s t must c h e c k b e f o r e s u c c e e d i n g , i s whether o r n o t e x a c t l y t h e same l o c u s has been p r o d u c e d a t some p r e v i o u s t i m e i n t h e d e t e r m i n a t i o n o f a p o i n t . The two l o c i f o r a p o i n t must o b v i o u s l y be d i s t i n c t . 2U I I . 2 . B T h e , L i n e _And_ S l o p e S p e c i a l i s t s The l i n e s p e c i a l i s t s a r e p r o c e d u r e s f o r t h e c o n s t r u c t i o n o f ( i n f i n i t e ) s t r a i g h t l i n e s . S u b g o a l s s e t up by t h e l o c i s p e c i a l i s t s o f t e n i n v o l v e t h e d e t e r m i n a t i o n o f a l i n e , and i t i s t o t h e s e r e q u e s t s t h a t t h e l i n e s p e c i a l i s t s r e s p o n d . The s l o p e s p e c i a l i s t s a r e e x p e r t i n f i n d i n g t h e s l o p e s o f l i n e s , and a r e c a l l e d when a l i n e s p e c i a l i s t must know a l i n e « s s l o p e i n o r d e r t o c o n s t r u c t i t . C-LINE2 a l i n e i s known i f i t p a s s e s t h r o u g h a known p o i n t and i t s s l o p e i s known o r c a n be d e t e r m i n e d . C-LINE1 a l i n e i s known i f i t p a s s e s t h r o u g h two known p o i n t s C-SLQPE1 t h e s l o p e o f a l i n e i s known i f i t i s p a r a l l e l t o a n o t h e r l i n e whose s l o p e i s ' k n o w n . C-SL0PE2 t h e s l o p e o f a l i n e i s known i f i t i n t e r s e c t s a n o t h e r known l i n e a t a known a n g l e . C-SE61 a l i n e segment i s known i f i t s two e n d p o i n t s a r e known. The l i n e and s l o p e s p e c i a l i s t s u s e t h e THUNIQUE f e a t u r e o f MICRO-PLANNER t o a v o i d i n f i n i t e r e c u r s i v e l o o p s . T h i s means, f o r example, t h a t b e f o r e e a c h l i n e s p e c i a l i s t b e g i n s , i t f i r s t c h e c k s t o s e e i f i t o r any o t h e r l i n e s p e c i a l i s t i s a l s o i n t h e 25 p r o c e s s o f d e t e r m i n i n g t h e same l i n e . The t i m e and s p a c e o v e r h e a d i n v o l v e d i s n e i t h e r u n r e a s o n a b l e i n r e l a t i o n t o o t h e r f a c t o r s , n o r i s t h e r e any o t h e r a v a i l a b l e s o l u t i o n . B e l a t e d t o t h e l i n e s p e c i a l i s t s i s an e c o n o m i z i n g s p e c i a l i s t O L I H E T E S T . Time c o s t s a r e h i g h f o r d e t e r m i n i n g l i n e s b e c a u s e , w i t h s l o p e s i n v o l v e d , o t h e r l i n e d e t e r m i n a t i o n s may be r e q u i r e d . To a v o i d f r u i t l e s s e x p e n d i t u r e o f e f f o r t i n t h e l i n e and s l o p e s p e c i a l i s t s , C-LIHETEST c h e c k s t h e d a t a b a s e (no o t h e r s p e c i a l i s t s a r e i n v o k e d ) f o r t h e p r e s e n c e o f a known l i n e o r p o i n t . I f no l i n e o r p o i n t s a r e known, t h e l i n e s p e c i a l i s t s c a n n o t p o s s i b l y s u c c e e d and a r e n o t i n v o k e d . I I . 2 . C A n g l e _ S p e c i a l i s t s The c o n s t r u c t i o n o f a n g l e s i s done by t h e a n g l e s p e c i a l i s t s . U s u a l l y t h e r e q u e s t s f o r t h e c o n s t r u c t i o n o f a n g l e s o r i g i n a t e i n t h e s l o p e s p e c i a l i s t s . The a n g l e s p e c i a l i s t s make u s e o f THUHIQUE f o r t h e same r e a s o n s a s t h e l i n e and s l o p e s p e c i a l i s t s do. an a n g l e i s c o n s t r u c t a b l e i f i t i s t h e a n g l e o f i n t e r s e c t i o n o f two l i n e s w h i c h a r e known o r can be c o n s t r u c t e d . C-AN£LE_2 an a n g l e i s c o n s t r u c t a b l e i f i t i s e q u a l t o a n o t h e r a n g l e w h i c h i s known o r c a n be c o n s t r u c t e d . 26 C-ANGLE3 an a n g l e i s c o n s t r u c t a b l e i f i t i s a m u l t i p l e o f a n o t h e r a n g l e which i s known o r c o n s t r u c t a b l e . C^AJJGLEO. an a n g l e i s c o n s t r u c t a b l e i f i t i s one a n g l e o f a t r i a n g l e and t h e o t h e r two a n g l e s o f t h e t r i a n g l e a r e known o r c a n be c o n s t r u c t e d . I I . 2 . D A s s u m p t i o n S p e c i a l i s t s When a p o i n t o r a l i n e i s n o t known and i s not c o n s t r u c t a b l e f r o m t h e h y p o t h e s i s o f t h e p r o b l e m , i t may be e x p e d i e n t and p e r m i s s i b l e t o l o c a t e i t a r b i t r a r i l y . Two s u c h a s s u m p t i o n s , t h a t o f one l i n e and one p o i n t , a r e a d m i s s i b l e i n an i n d i v i d u a l p r o b l e m . The r a t i o n a l e f o r t h i s f l e x i b i l i t y l i e s i n t h e f r e e d o m o f c h o i c e o f an o r i g i n and a x i s i n a c o o r d i n a t e s y s t e m . The d e c i s i o n a s t o which p o i n t and l i n e s h o u l d be assumed i s c r u c i a l . C h o o s i n g a p o i n t w h i c h might be d e t e r m i n e d by o t h e r means r e s u l t s i n a r e d u c t i o n i n t h e number o f c o n d i t i o n s c o n t r i b u t i n g t o w a r d t h e p r o b l e m s o l u t i o n . I n o r d e r t o g i v e a s much d i r e c t i o n a s p o s s i b l e t o t h i s d e c i s i o n , i t i s p o s t p o n e d u n t i l t h e c h o i c e which i s made w i l l be c e r t a i n t o be o f u s e . When a s p e c i a l i s t r e q u i r e s a l i n e o r a p o i n t i n o r d e r t o s u c c e e d , b u t i t i s n e i t h e r known n o r c o n s t r u c t a b l e i n t h e c u r r e n t c o n t e x t , i t s p o s i t i o n i s assumed whenever a l l o w a b l e . 27 The a s s u m p t i o n s p e c i a l i s t s t e s t t h e p e r m i s s i b l i t y o f t h e r e q u i s i t e a s s u m p t i o n , and i f i t p a s s e s , a s s e r t t h a t t h e p o i n t o r l i n e i s known. T h e r e a r e two a s s u m p t i o n s p e c i a l i s t s , one f o r l i n e s and one f o r p o i n t s , embodying t h e r e s t r a i n t s on t h e s i t u a t i o n s i n w h i c h a r b i t r a r y d e t e r m i n a t i o n o f p o s i t i o n s c a n be made. C-DTRMNPOINT a p o i n t P has t h e g r e a t e s t l i b e r t y whenever no o t h e r p o i n t s o r l i n e s a r e known. I t may under t h o s e c o n d i t i o n s be p l a c e d f r e e l y w i t h o u t c o n s t r a i n t . When P l i e s on a l i n e and t h a t l i n e i s known o r c o n s t r u c t a b l e , P may be p l a c e d anywhere a l o n g i t . P has no f r e e d o m and must n o t be assumed whenever a n o t h e r p o i n t i s a l r e a d y known. C-ASSDBELIWE whenever no l i n e s a r e known o r c o n s t r u c t a b l e and no p o i n t s on t h e l i n e i n q u e s t i o n a r e known, t h e l i n e may be p o s i t i o n e d a r b i t r a r i l y . I f a p o i n t on t h e l i n e i s known, t h e n t h e s l o p e o f t h e l i n e may be c h o s e n ; however, t h e l i n e must p a s s t h r o u g h t h e known p o i n t . II. 3 I n p u t And P h r a s e S p e c i a l i s t s A s i n g l e s e n t e n c e c o n s i s t i n g o f s e v e r a l c o n j o i n e d p h r a s e s i s a c c e p t e d by t h e CONSTRUCTOR. The u n d e r s t a n d i n g o f E n g l i s h i n p u t i s n o t a g o a l o f t h i s work, and t h u s t h e s t r u c t u r e and v o c a b u l a r y o f s e n t e n c e s u n d e r s t o o d by t h e CONSTRUCTOR has r e m a i n e d v e r y r e s t r i c t e d . S t a t e m e n t s o f s t r a i g h t - e d g e and 28 compass c o n s t r u c t i o n p r o b l e m s have many f e a t u r e s i n common, t h e e s s e n t i a l framework b e i n g : C o n s t r u c t an OBJECT g i v e n RESTRICTION!, RESTRICTI0N2 . . . RESTRICTIONn. S i n c e most p r o b l e m s c o n c e r n i n g t r i a n g l e s and c i r c l e s i n g e o m e t r y t e x t b o o k s a r e s t a t e d i n t h i s f o r m a t o r a r e e a s i l y amenable t o i t , t h e c o n v e n i e n c e o f h a v i n g a s e n t e n c e a s t h e medium o f c o m m u n i c a t i o n o u t w e i g h s t h e o v e r h e a d o f i t s i n t e r p r e t a t i o n . Example: C o n s t r u c t a r i g h t t r i a n g l e g i v e n a l e g and t h e a l t i t u d e on t h e h y p o t e n u s e . \ T r a n s l a t i o n o f t h e p r o b l e m s t a t e m e n t must r e s u l t i n a d a t a b a s e o f i n f o r m a t i o n f o r r e f e r e n c e by t h e c o n s e q u e n t knowledge s p e c i a l i s t s . T h i s t r a n s f o r m a t i o n o f t h e i n p u t i s a c c o m p l i s h e d by PLANNER a n t e c e d e n t t heorems c a l l e d p h r a s e s p e c i a l i s t s c o n t a i n i n g d e f i n i t i o n a l g e o m e t r i c k n o w l e d g e . A L I S P f u n c t i o n o p e r a t i n g under t h e a s s u m p t i o n t h a t ' g i v e n ' , 'and', • c o n s t r u c t ' , and ',' a c t as p h r a s e d e l i m i t e r s , s p l i t s t h e i n p u t s e n t e n c e i n t o p h r a s e s which a r e t h e n a s s e r t e d ( u s i n g t h e MICRO-PLANNER p r i m i t i v e THASSERT ) t r i g g e r i n g t h e e x e c u t i o n o f a p p r o p r i a t e p h r a s e s p e c i a l i s t s . The i n t e r p r e t a t i o n o f t h e i n p u t i s t h e r e f o r e e f f e c t i v e l y a p a t t e r n m a t c h i n g p r o c e s s . The p a t t e r n m a t c h i n g i s done when a p h r a s e i s matched t o t h e c a l l i n g p a t t e r n o f an a n t e c e d e n t s p e c i a l i s t , a l t h o u g h t h e f a c i l i t i e s a v a i l a b l e i n MICRO-PLANNER f o r p a t t e r n m a t c h i n g p u r p o s e s a r e v e r y r u d i m e n t a r y . 29 To c o n s t r u c t a f i g u r e b o t h t h e knowns and t h e unknowns o f t h e p r o b l e m must be s p e c i f i e d , and t h i s i n f o r m a t i o n must be r e p r e s e n t e d i n t h e d a t a b a s e . The knowns a r e t h e a n g l e s , l e n g t h s , and r e l a t i o n s h i p s i n t r o d u c e d a s ' g i v e n s ' i n t h e p r o b l e m . When an a l t i t u d e i s a »given», f o r example, t h e i n f o r m a t i o n c o n v e y e d i s t h a t a l e n g t h i s known and t h a t a v e r t e x o f a t r i a n g l e i s r e l a t e d t o i t s o p p o s i t e s i d e b y t h a t l e n g t h . I t i s i m p o r t a n t t o n o t e t h a t when an a n g l e o r l e n g t h i s s t a t e d a s *given», t h i s i s m e r e l y a d e c l a r a t i o n o f i t a s a known i n t h e p r o b l e m ; l e n g t h s and a n g l e s a r e r a r e l y a c t u a l l y s p e c i f i e d i n g e o e m t r y t e x t s by a c c o m p a n y i n g d i a g r a m s . The unknowns a r e t h e p o i n t s , l i n e s e g m e n t s , a n g l e s , l i n e s and c i r c l e s f r o m which t h e f i g u r e i s t o be composed, b u t a b o u t which n o t h i n g h a s been s p e c i f i e d . The knowledge u s e d t o d e v e l o p t h e knowns and unknowns i n t h e d a t a b a s e i s c o n t a i n e d i n t h e p h r a s e s p e c i a l i s t s . A d e s c r i p t i o n o f some o f t h e key p h r a s e s p e c i a l i s t s and an example i s g i v e n below. A-CTRI t h i s s p e c i a l i s t d e s c r i b e s a t r i a n g l e . I t a s s e r t s t h e e x i s t e n c e o f t h r e e p o i n t s and t h r e e l i n e s , and t h a t e a c h p o i n t l i e s on two o f t h e l i n e s . T h r e e compound l o c u s r e s t r i c t i o n s s t a t i n g t h a t e a c h o f t h e t h r e e p o i n t s i s p a r t o f a t r i a n g l e a r e a l s o a s s e r t e d . A-ALTHED1 t h i s s p e c i a l i s t h a n d l e s b o t h a l t i t u d e s and medians which a r e g i v e n . A l t i t u d e s and medians a r e 30 s p e c i f i e d w i t h r e s p e c t t o a s i d e o f a t r i a n g l e , however, i t i s t h e p o i n t o p p o s i t e t h a t s i d e which i s t h e one a f f e c t e d by t h e r e s t r i c t i o n . The a p p r o p r i a t e p o i n t i s d e t e r m i n e d by f i r s t f i n d i n g t h e s i d e t o w h i c h i t r e f e r s i n t h e d a t a b a s e . The p o i n t and i t s r e s t r i c t i o n a r e t h e n added t o t h e d a t a b a s e . A name f o r t h e l e n g t h o f t h e a l t i t u d e o r median i s g e n e r a t e d and u s i n g t h i s name, t h e l e n g t h i s a s s e r t e d t o be known. A-SIDE when a s i d e i s g i v e n t h i s s p e c i a l i s t i s i n v o k e d . I t s i m p l y c h e c k s t h e d a t a b a s e t o f i n d a s i d e o f a t r i a n g l e w h i c h i s n o t known and a s s e r t s t h a t i t i s known. A-CIRCLE a c i r c l e has a c e n t e r and r a d i u s f o r which names a r e g e n e r a t e d . A name f o r t h e c i r c l e i s a l s o g e n e r a t e d . The c i r c l e i s t h e n a s s e r t e d t o e x i s t , i t s c e n t e r t o be i t s c e n t e r and i t s r a d i u s i t s r a d i u s . The c o n d i t i o n t h a t t h e c e n t e r p o i n t must be t h e c e n t e r o f t h e c i r c l e i s added a s a r e s t r i c t i o n on t h a t p o i n t . A-TAN1 c i r c l e s a r e f r e q u e n t l y r e s t r i c t e d t o be t a n g e n t t o o t h e r c u r v e s ( l i n e s o r c i r c l e s ) a t g i v e n p o i n t s . T h i s r e q u i r e s t h e g e n e r a t i o n o f names f o r a new c u r v e and p o i n t , and t h e a s s e r t i o n o f t h e i r e x i s t e n c e . The p o i n t i s a s s e r t e d t o be on b o t h t h e c i r c l e and t h e c u r v e , a s w e l l a s b e i n g known. A l t h o u g h t h e r e a r e o t h e r p h r a s e s p e c i a l i s t s t h e above a r e i n d i c a t i v e o f t h e i r o p e r a t i o n . As an example o f t h e r e s u l t o f t h e p h r a s e s p e c i a l i s t s c o n s i d e r t h e c o n s t r u c t i o n p r o b l e m : 31 Example ( c o n s t r u c t a t r i a n g l e g i v e n a s i d e , t h e a l t i t u d e t o t h a t s i d e and t h e median t o t h a t s i d e ) • • • • b e g i n n i n g o f o u t p u t f r o m i n p u t and p h r a s e s p e c i a l i s t s * * * * (CONSTRUCTING TRIANGLE A B C ) (AB I S A SEGMENT OF LINE LINE1 , (AB IS A GIVEN SIDE) (LET THE GIVEN ALTITUDE BE OF LENGTH LENU) (LET THE GIVEN MEDIAN BE OF LENGTH LEN5) AC OF LINE2 , AND BC OF LINE3) * * * * e n d o f o u t p u t f r o m i n p u t and p h r a s e s p e c i a l i s t s * * * * • • • • b e g i n a s s e r t i o n base l i s t i n g * * * * MIDPT6 ON LINE 1)) MEDIAN C TO AB)) LINE LINE3)) LINE LINE2)) L I N E LINE1)) TRIANGLE A B C ) ) MIDPOINT MIDPT6 OF AB)) POINT C)) B)) A)) C (CONDITION-ON C (CONDITION-ON POINT POINT POINT POINT 100) POINT POINT POINT C ON ON ON ON ON ON C (CONDITION-ON B (CONDITION-ON A (CONDITION-ON C C C B A ST ST ST ST ST MEDIAN C ALTITUDE TRIANGLE TRIANGLE TRIANGLE TO AB IS LEN5)) . -110) C TO LINE 1 IS LEN4J) LINE3) ) LINE2)) LINE3)) LINE1)) LINE2)) LINE1)) KNOWN LENGTH KNOWN LENGTH LEN5) ) LEN4)) B B B C)) C)) C)) 20) 20) 20) * * * * e n d o f a s s e r t i o n b a s e l i s t i n g * * * * ( (KNOWN LENGTH AB) ) (TRYING CONDITION: (CONDITION-ON A ST TRIANGLE A B C ) ) ( UNKNOWN POINTS (A B C) NO. OF LOCI FOUND: 0) (TRYING CONDITION: (CONDITION-ON A ST TRIANGLE A B C ) ) 32 ( UNKNOWN POINTS (A B C) NO. OF LOCI FOUND: 1) (TRYING CONDITION: (CONDITION-ON C ST MEDIAN C TO AB IS LEN5)) ( UNKNOWN POINTS (C) NO. OF LOCI FOUND: 0) (TRYING CONDITION: (CONDITION-ON C ST MEDIAN C TO AB IS LEN5) ) ( UNKNOWN POINTS (C) NO. OF LOCI FOUND: 1) (TRYING CONDITION: (CONDITION-ON C ST ALTITUDE C TO LINE1 IS LEN4)) ( UNKNOWN POINTS (C) NO. OF LOCI FOUND: 1) ( (DRAW LINE LINE1 ANYWHERE) (A IS ON LINE LINE1) (PLACE POINT B ANYWHERE ON LINE1) (POINT A IS ON THE CIRCLE WITH CENTER B RADIUS AB) (POINT G IS ON CIRCLE OF RADIUS LEN5 WITH CENTER MIDPT6 , THE MIDPOINT OF AB)(POINT C IS ON A LINE PARALLEL TO LINE1 AT DISTANC LENU)) I I . 4 P o i n t O r d e r i n g And A s s u m p t i o n I n most c o n s t r u c t i o n p r o b l e m s t h e r e i s more t h a n one p o i n t t o be l o c a t e d i n t h e d e t e r m i n a t i o n o f t h e f i n a l f i g u r e . The g u e s t i o n a r i s e s a s t o t h e o r d e r i n which t h e p o i n t s s h o u l d be a t t e m p t e d . C e r t a i n l y t h e o r d e r i s i m p o r t a n t b e c a u s e t h e l o c i o f some p o i n t s c a n o n l y be f o u n d w i t h r e f e r e n c e t o o t h e r p o i n t s . A s i m p l e o r d e r i n g scheme b a s e d upon t h e i d e a t h a t t h o s e p o i n t s h a v i n g t h e l e a s t f r e e d o m s h o u l d be l o o k e d f o r f i r s t , has been i m p l e m e n t e d . T h i s l e a v e s t h e p o i n t s w i t h t h e most f r e e d o m a v a i l a b l e f o r a s s u m p t i o n , i f n e c e s s a r y . The more r e s t r i c t i o n s p l a c e d upon a p o i n t , t h e h i g h e r i s t h e l i k e l i h o o d t h a t t h e r e w i l l be a t l e a s t two l o c i f r o m which t o d e t e r m i n e i t . The o r d e r i n g s t r a t e g y i s : f i r s t , b e g i n w i t h t h e s e a r c h f o r t h e l o c i o f t h e most r e s t r i c t e d p o i n t ; t h e n , i f a s u b g o a l o f a l o c i s p e c i a l i s t r e q u i r e s a p o i n t t o be known, i t i s s i m p l y assumed t o 33 be known. T h a t i s a s l o n g a s t h e c o n d i t i o n s o f t h e p o i n t a s s u m p t i o n s p e c i a l i s t a r e met. Any p o i n t assumed i n t h i s manner w i l l be one w i t h more f r e e d o m t h a n t h e p o i n t whose l o c i a r e b e i n g s o u g h t . Never i s an e f f o r t made t o d e t e r m i n e a p o i n t w h ich i s r e q u i r e d by a l o c i s p e c i a l i s t , i f i t i s not s i m p l y s t a t e d t o be known i n t h e d a t a b a s e , s i n c e t h i s would mean i n v o k i n g t h e l o c i s p e c i a l i s t s f o r i t , t h e r e b y n e g a t i n g t h e t o p l e v e l o r d e r i n g o f p o i n t s . A l l o w i n g t h e a s s u m p t i o n o f l i n e s and p o i n t s on t h e demand o f a l o c i s p e c i a l i s t t h a t w i l l make i m m e d i a t e u s e o f t h e a s s u m p t i o n , g i v e s a n a t u r a l p r i o r i t y t o t h e c h o i c e o f t h e s i n g l e p o i n t and l i n e a v a i l a b l e i n any one c o n s t r u c t i o n p r o b l e m . Some c o n d i t i o n s on p o i n t s a r e more r e s t r i c t i v e t h a n o t h e r s , w i t h t h e e f f e c t t h a t a s i m p l e c o u n t o f t h e number o f c o n d i t i o n s r e l e v a n t t o t h e r e q u i r e d p o i n t s w i l l n o t n e c e s s a r i l y r e v e a l t h e most r e s t r i c t e d p o i n t . To f a c i l i t a t e t h e o r d e r i n g o f p o i n t s a c c o r d i n g t o t h e i r d e g r e e o f r e s t r i c t i o n a n u m e r i c c o e f f i c i e n t i s a s s i g n e d t o e a c h c o n d i t i o n which i s a s s e r t e d ( u s i n g t h e THPROP MICRO-PLANNER f e a t u r e ) i n c o n j u n c t i o n w i t h t h e c o n d i t i o n by t h e p h r a s e s p e c i a l i s t s . T h e s e c o e f f i c i e n t s a r e t o t a l l e d and t h e r e s u l t s s o r t e d i n t o d e c r e a s i n g o r d e r by a s u p e r v i s o r y L I S P f u n c t i o n t h a t i n i t i a t e s t h e p o i n t d e t e r m i n a t i o n s . The r e s t r i c t i o n c o e f f i c i e n t s o f t h e v a r i o u s c o n d i t i o n s a r e g i v e n below. t r i a n g l e e q u i d i s t a n t a l t i t u d e median r i g h t t r i a n g l e c i r c l e -110 20 10 100 50 100 The c o e f f i c i e n t f o r t h e median c o n d i t i o n i s an e x c e p t i o n b e c a u s e t h e l o c u s o f p o i n t s s a t i s f y i n g i t i s d e f i n e d i n t e r m s o f t h e m i d p o i n t o f a l i n e segment. S i n c e a l i n e segment (two p o i n t s ) c a n n o t be assumed •, t h e m i d p o i n t o f t h e segment would i t s e l f have t o be assumed i n o r d e r t o p r o c e e d . However, t h e m i d p o i n t i s n o t a good p o i n t on w h i c h t o e x e r c i s e t h e f r e e d o m o f a r b i t r a r y l o c a t i o n , b e c a u s e o t h e r p o i n t s i n t h e f i g u r e a r e u n l i k e l y t o be s p e c i f i e d w i t h r e s p e c t t o i t . The s p e c i a l i s t r e q u i r i n g t h e m i d p o i n t t o be known i s t h u s a p o o r one t o i n v o k e b e f o r e t h e l i n e segment i s l i k e l y t o have been c o n s t r u c t e d . The low median c o e f f i c i e n t e n s u r e s t h a t i t w i l l n o t be. I I . 5 S o l u t i o n A b s t r a c t i o n I n PLANNER t h e r e i s no e x p l i c i t method o r f e a t u r e t o be u s e d i n c o l l e c t i n g t h e s o l u t i o n a s i t i s d e v e l o p e d d u r i n g t h e e x e c u t i o n o f PLANNER p r o c e d u r e s . The onus o f p r o v i d i n g a s u i t a b l e f o r m a l i s m f o r a b s t r a c t i n g t h e s o l u t i o n f r o m t h e e x e c u t i o n s e q u e n c e r e s t s w i t h t h e u s e r . I n g e n e r a l , t h i s f o r m a l i s m e m bodies a g e n e r a l i z e d t r a c e o f t h e g o a l s and 35 p r o c e d u r e s i n v o l v e d i n f o r m i n g t h e s u c c e s s f u l b r a n c h o f t h e s e a r c h t r e e . The e v o l v i n g ' s t a t e o f t h e w o r l d * a s r e f l e c t e d dn c h a n g e s t o t h e d a t a b a s e , and a l i s t o f comments o r i n s t r u c t i o n s i n t e r p r e t a b l e by e i t h e r man o r machine r e g a r d i n g t h i s e v o l u t i o n , t o g e t h e r , f o r m t h e b a s i s o f t h i s t r a c e . F o r example, a change i n t h e s t a t e o f t h e ' b l o c k s * w o r l d 1 8 was r e p r e s e n t e d by t h e e r a s u r e o f an o l d l o c a t i o n and t h e a s s e r t i o n o f a new l o c a t i o n f o r an o b j e c t . T h i s was c o u p l e d w i t h t h e c o n c a t e n a t i o n o f a new command ( c h o s e n f r o m t h e s m a l l s e t ( m o v e h a n d , g r a s p , u n g r a s p ) ) t o a l i s t o f commands e a c h d e s c r i b i n g c h a n g e s i n t h e ' b l o c k s ' w o r l d . I n t e r p r e t a t i o n o f t h i s l i s t by g r a p h i c s r o u t i n e s r e s u l t e d i n a p i c t o r i a l t r a c e o f t h e s o l u t i o n b r a n c h . - A s i m i l a r t y p e o f f o r m a l i z a t i o n i s us e d i n t h e CONSTRUCTOR. Whenever an a n g l e , l i n e o r l o c u s , f o r example, i s d e t e r m i n e d , i n s t r u c t i o n s f o r i t s c o n s t r u c t i o n a r e added t o an e x p a n d i n g l i s t . The i n s t r u c t i o n s and t h e l i s t t h e y f o r m become an a l g o r i t h m f o r t h e c o n s t r u c t i o n o f t h e f i n a l f i g u r e . S i n c e t h e a l g o r i t h m i s i n t e n d e d f o r human i n t e r p r e t a t i o n t h e i n s t r u c t i o n s i t e n t a i l s a r e communicated i n E n g l i s h ; however, t h e y c o u l d j u s t a s s i m p l y be c o d e d as t h e names o f g r a p h i c s r o u t i n e s t o be c a l l e d , o r i n any o t h e r machine i n t e r p r e t a b l e f o r m . i s T e r r y W i n o g r a d , P r o c e d u r e s a s a R e p r e s e n t a t i o n f o r Data i n _ a _ C p m p u t e r Program f o r U n d e r s t a n d i n g N a t u r a l Language, ( C a m b r i d g e , Mass: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1971) R e v i s e d Ph.D. D i s s e r t a t i o n , MAC TR-84. 36 Two d i f f e r e n t t y p e s o f t r a c e s r e s u l t d e p e n d i n g upon t h e method used t o c o n c a t e n a t e new i n s t r u c t i o n s to t h e l i s t . P ermanent c o n c a t e n a t i o n , t h a t i s c o n c a t e n a t i o n which i s n o t u n d o a b l e by PLANNER b a c k t r a c k i n g , r e s u l t s i n a t r a c e o f a l l t h e s u b r e s u l t s o b t a i n e d en r o u t e t o t h e s o l u t i o n . C o n c a t e n a t i o n w h i c h i s u n d o a b l e under PLANNER f a i l u r e r e t u r n s a l i s t o f o n l y t h o s e r e s u l t s - f o r m i n g an i n t e g r a l p a r t o f t h e s o l u t i o n . II.6 B a s i c C o n s t r u c t i o n s The o u t p u t f r o m t h e CONSTRUCTOR i s a l i s t o f E n g l i s h c o n s t r u c t i o n s r e p r e s e n t i n g an a l g o r i t h m f o r t h e c o n s t r u c t i o n o f t h e a c t u a l f i g u r e d e s c r i b e d i n t h e p r o b l e m s t a t e m e n t . T h e s e i n s t r u c t i o n s a r e g i v e n i n t e r m s o f c o n s t r u c t i o n s which a r e c o n s i d e r e d t o be b a s i c a l t h o u g h n o t p r i m i t i v e . The p r i m i t i v e c o n s t r u c t i o n s a r e s i m p l y t h o s e o f d r a w i n g a l i n e g i v e n two p o i n t s on i t a n d , o f d r a w i n g a c i r c l e g i v e n i t s c e n t e r and r a d i u s . A b a s i c c o n s t r u c t i o n i s e i t h e r a p r i m i t i v e c o n s t r u c t i o n o r one s u c h a s : draw a l i n e p a r a l l e l t o a g i v e n l i n e a t a g i v e n d i s t a n c e . T h i s i s a s i m p l e c o n s t r u c t i o n , a l t h o u g h i t doe s r e q u i r e d e f i n i t i o n i n t e r m s o f t h e two p r i m i t i v e c o n s t r u c t i o n s . The j u s t i f i c a t i o n f o r t h e use o f a s e t o f b a s i c c o n s t r u c t i o n s i s t h a t a l g o r i t h m i c d i r e c t i o n s a r e g i v e n f o r t h e i r c o n s t r u c t i o n i n most ge o m e t r y t e x t s . A l i s t o f t h e b a s i c c o n s t r u c t i o n s i s g i v e n i n A p p e n d i x I. 37 H i l C a n o n i c a l .Naming As i n g e o m e t r y t h e o r e m p r o v i n g s y s t e m s , t h e p r o b l e m o f u n i q u e l y i d e n t i f y i n g g e o m e t r i c o b j e c t s a r i s e s h e r e . W i t h o u t a naming s y s t e m , r e d u n d a n c y i n t h e d e f i n i t i o n and e x e c u t i o n o f t h e s p e c i a l i s t s would be i n e v i t a b l e . I n t h e BTP o f G o l d s t e i n , 1 9 names were a s s i g n e d on t h e b a s i s o f t h e c o o r d i n a t e s o f t h e p o i n t s i n v o l v e d i n an o b j e c t , a s t h e y were d e t e r m i n e d f rom t h e d i a g r a m t h e t h e o r e m p r o v e r u s e d . S i n c e t h e CONSTRUCTOR doe s n o t use o r e v e r a c t u a l l y draw a d i a g r a m , a c a n o n i c a l naming b a s e d upon l e x i c o g r a p h i c o r d e r i n g i s employed. E a c h p o i n t i s g i v e n a name f r o m t h e l e t t e r s o f t h e a l p h a b e t and t h e s e a r e used t o f o r m t h e names o f o t h e r o b j e c t s . L e t t i n g x, y , z be v a r i a b l e s o v e r t h e s e t o f p o i n t names {A,B,C...} and l e t t i n g >, < be r e l a t i o n s o f a l p h a b e t i c a l o r d e r , t h e naming s y s t e m i s a s f o l l o w s : (a) xy i s a c a n o n i c a l l i n e segment name i f x and y a r e t h e e n d p o i n t s o f t h e segment, and x < y (b) x y z i s a c a n o n i c a l a n g l e name i f y i s t h e v e r t e x p o i n t ; x and z a r e p o i n t s on t h e two »» G o l d s t e i n , E l e m e n t a r y Geometry,Theorem P r o v i n g , pp. 13-14. 38 r a y s which form t h e a n g l e ; and x < y. (c) x y z i s a c a n o n i c a l t r i a n g l e name i f x < y < z. I f a t r i a n g l e i s r i g h t a n g l e d o r i s o s c e l e s , t h e d i s t i n g u i s h e d v e r t e x i s a l w a y s c h o s e n t o be t h e f i r s t c h a r a c t e r o f t h e t r i a n g l e name. (d) t h e naming o f l i n e s , a s d i s t i n c t f r o m l i n e s e g m e n t s, p r e s e n t s a somewhat d i f f e r e n t p r o b l e m . L i n e names L I N E 1 , LINE2, e t c . a r e g e n e r a t e d f o r l i n e s a s t h e y a r i s e . (e) c i r c l e names CIRCLE1, CIRCLE2, e t c . a r e g e n e r a t e d a s c i r c l e r e f e r e n c e s o c c u r i n t h e i n p u t t e x t . I I . 8 FLOW OF CONTROL The l i n k a g e between t h e segments o f t h e CONSTRUCTOR i s a c c o m p l i s h e d by a LISP-PLANNER h y b r i d f u n c t i o n . I t i s ba s e d i n L I S P , b u t makes e x p l i c i t c a l l s t o t h e MICRO-PLANNER i n t e r p r e t e r f o r t h e e v a l u a t i o n o f some PLANNER c o d e . The f i r s t s t e p s i n t h e e x e c u t i o n s e q u e n c e a r e t h o s e o f i n i t i a l i z a t i o n , and r e a d i n g t h e p r o b l e m s t a t e m e n t . T h i s s t a t e m e n t i s t h e n d i v i d e d i n t o p h r a s e s , a s d e s c r i b e d p r e v i o u s l y , a t which t i m e t h e MICRO-PLANNER 39 i n t e r p r e t e r i s c a l l e d t o a s s e r t e a c h p h r a s e i n t u r n . The a s s e r t i o n o f t h e p h r a s e s r e s u l t s i n t h e i n v o c a t i o n o f a n t e c e d e n t p h r a s e s p e c i a l i s t s , f a b r i c a t o r s o f a model d e l i n e a t i n g a l l t h e knowns and unknowns o f t h e p r o b l e m . When a l l t h e p h r a s e s have been a s s e r t e d , t h o s e p o i n t s e s s e n t i a l t o t h e c o n s t r u c t i o n o f t h e f i g u r e and t h e i r a s s o c i a t e d c o n d i t i o n s a r e l o o k e d up and s o r t e d i n t o o r d e r i n a c c o r d a n c e w i t h t h e r e s t r i c t i o n c o u n t . The MICRO-PLANNER i n t e r p r e t e r i s t h e n commanded i n t o a c t i o n a g a i n f o r e v a l u a t i o n o f t h e c o n d i t i o n s r e l e v a n t t o t h e f i r s t p o i n t . C o n d i t i o n s a r e e x p r e s s e d a s PLANNER g o a l s . When two o f t h e s e g o a l s have been s a t i s f i e d t h e p o i n t i s a s s e r t e d t o be known, and a t t e n t i o n i s s h i f t e d o n t o t h e n e x t p o i n t o f t h e o r d e r e d s e q u e n c e . T h i s p r o c e s s c o n t i n u e s u n t i l a l l t h e p o i n t s a r e d e t e r m i n e d . I f a s i t u a t i o n a r i s e s i n which no two g o a l s f o r a p o i n t a r e s a t i s f i a b l e , any a s s u m p t i o n s and c h a n g e s t o t h e d a t a b a s e a r e undone (by MICRO-PLANNER backup) and t h e l o c i p o s s i b i l i t i e s o f t h e o t h e r p o i n t s a r e e x p l o r e d . R e t u r n i s made t o t h e p o i n t i n q u e s t i o n o n l y a f t e r o t h e r p o i n t s have been e s t a b l i s h e d . When a l l p o i n t s a r e r e a l i z e d t h e l i s t o f i n s t r u c t i o n s c o m p r i s i n g t h e s o l u t i o n a l g o r i t h m i s p r i n t e d . The whole p r o c e s s i s e x p l i c a t e d by t h e a d j o i n i n g f l o w c h a r t . I n i t i a l i z e and read the problem statement i ~~ S p l i t problem statement into phrases 2£ Assert the phrases causing the antecedent theorems to expand the problem statement into the database — sk_ Order the points on the basis of the co e f f i c i e n t s of the conditions relevant to them .For the f i r s t / n e x t point i n order, do a MICPD-PLANNER evaluation of i t s conditions as goals  .^Are t h e r e \ . other points which have not yet been ^^>scpns idered>-^ Reorder the l i s t of points putting the current point at the end of the l i s t P r i n t f a i l u r e FIGURE I I 41 I I I Comments ,_Qn_PLA8HER PLANNER has r e c e i v e d s i m u l t a n e o u s p r a i s e and c r i t i c i s m . Of i t s t h r e e d i s t i n g u i s h i n g f e a t u r e s , an a s s o c i a t i v e d a t a b a s e , p a t t e r n d i r e c t e d p r o c e d u r e i n v o c a t i o n , and an a u t o m a t i c b a c k t r a c k i n g c o n t r o l s t r u c t u r e , t h e l a t t e r h as been s i n g l e d o u t f o r a c u t e c r i t i c i s m by G. Sussman and D. M c D e r m o t t . 2 ° The l a u d a b i l i t y o f PLANNER i s i l l u s t r a t e d by i t s i n s t r u m e n t a l r o l e i n t h e f o r m u l a t i o n o f t h e • b l o c k s 1 w o r l d , 2 * and t h e geo m e t r y t h e o r e m p r o v e r , B T P . 2 2 B a c k t r a c k i n g i s a s i n g l e term f o r a p r o c e s s which c a n be s e e n t o c o n s i s t o f two d i s t i n c t o p e r a t i o n s . The f i r s t o p e r a t i o n i n t h e b a c k t r a c k p r o c e s s i s t h e r e t u r n t o a p r e c e d i n g s t a t e i n t h e c o m p u t a t i o n , a d e c i s i o n p o i n t , an e a r l i e r node i n t h e s e a r c h t r e e . The e f f e c t o f a l l c o m p u t a t i o n o c c u r r i n g a f t e r t h a t node was p a s s e d , i s undone; t h e b r a n c h o f t h e s e a r c h t r e e d e v e l o p e d from t h a t node i s p r u n e d f r o m t h e t r e e . T h i s o p e r a t i o n i s t h e h e a r t o f b a c k t r a c k i n g ; however, t h e i n i t i a t i o n o f c o m p u t a t i o n on 2 ° G.J. Sussman and D.V. McDermott, "From PLANNER t o CONNIVER—A G e n e t i c A p p r o a c h , " F a l l J o i n t . C o m p u t e r C o n f e r e n c e 1222, PP- 1171-1179. 2 1 H i n o g r a d , P r o c e d u r e s a s a R e p r e s e n t a t i o n f o r Data i n a Computer Program,, f o r U n d e r s t a n d i n g N a t u r a l L a n g uage. 2 2 G o l d s t e i n , E l e m e n t a r y Geometry Theorem P r o v i n g . 42 a new b r a n c h e m a n a t i n g f r o m t h e d e c i s i o n p o i n t i s a l s o o f t e n c o n s i d e r e d t o be i m p l i e d by t h e term b a c k t r a c k i n g . T h i s i s most c e r t a i n l y t h e c a s e i n r e f e r e n c e t o t h e PLANNER a u t o m a t i c b a c k t r a c k i n g c o n t r o l s t r u c t u r e . C r i t i c i s m o f a u t o m a t i c b a c k t r a c k i n g i s s i m i l a r i l y d i v i s i b l e i n t o two com p o n e n t s ; what i t doe s and what i t d o e s n o t do. What i s n o t done i s t h e s a v i n g o f any r e s u l t s f r o m t h e abandoned b r a n c h . Not even a r e c o r d o f t h e h y p o t h e s i s which l e d t o t h e b r a n c h ' s e x p l o r a t i o n i s k e p t . The answer t o t h i s c r i t i c i s m seems t o l i e i n t h e e s t a b l i s h m e n t o f c o n t e x t s and o p e r a t i o n s f o r t h e i r m a n i p u l a t i o n , a s h a s been done i n Q A 4 2 3 and CONNIVER. 2* What i s done u n d e r t h e a u s p i c e s o f PLANNER b a c k t r a c k i n g i s t h e a u t o m a t i c e x a m i n a t i o n o f t h e n e x t p o s s i b i l i t y a t a d e c i s i o n p o i n t . T h e r e i s no c o n t r o l g i v e n t o t h e programmer o v e r t h i s r e s t a r t i n g o f c o m p u t a t i o n a t a p o i n t where i t may v e r y w e l l be u n e x p e c t e d . A c c o r d i n g t o Sussman and HcDermott t h e p r o b l e m t h a t "an u n e x p e c t e d f a i l u r e w i l l p r o p a g a t e b a c k . . . and compute w i t h o u t o u r e x p l i c i t programming o f t h i s a c t i v i t y . . . i s o b s e r v e d by r e a l u s e r s o f 2 3 J . F . R u l i f s o n , J.A. D e r k s e n and R . J . W a l d i n g e r , QA4: A P r o c e d u r a l C a l c u l u s f o r I n t u i t i v e R e a s o n i n g , (Menlo P a r k , C a l i f . : S t a n f o r d R e a s e a r c h I n s t i t u t e , 1973) A r t i f i c i a l I n t e l l i g e n c e C e n t e r T e c h n i c a l Note 73. 2 * G.J. Sussman and D.V. HcDermott, The_CONNIVER_Reference M a n u a l , (Cambridge, Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , 1972) AI Memo no. 259. 43 MICRO-PLANNER who c o m p l a i n t h a t t h e y c a n n o t u n d e r s t a n d t h e b e h a v i o r o f t h e i r p r ograms b e c a u s e t h e f l o w o f c o n t r o l i s n o t e x p l i c i t " i n t h e c o d e . " 2 5 An e s s e n t i a l d i f f i c u l t y l i e s w i t h t h e GOAL p r i m i t i v e , t h e most ' common and complex f o r m o f d e c i s i o n p o i n t . I t has t o o much power v e s t e d i n i t f o r t h e f r e q u e n c y w i t h which i t must be u s e d . The a u t h o r s u g g e s t s s y p h o n i n g some o f t h i s power o f f i n t o a new PLANNER p r i m i t i v e , t o be c a l l e d I S . T h i s new p r i m i t i v e i s a n a t u r a l c o n t r a c t i o n o f t h e power o f GOAL. Much f r u i t l e s s e x p l o r a t i o n and b a c k t r a c k i n g e f f o r t c a n be e l i m i n a t e d by r e p l a c i n g GOAL w i t h t h e l e s s p o w e r f u l IS whenever p o s s i b l e . The p r o b l e m w i t h t h e GOAL f u n c t i o n i s e f f e c t i v e l y i l l u s t r a t e d by an example w h i c h Sussman and McOermott use i n t h e i r c r i t i c i s m o f b a c k t r a c k i n g . The example i s : (CONSEQUENT (X Y Z) (?X IN ?Y) (GOAL (?X IN ?Z)) (GOAL (?Z IN ?Y)} ) 2 6 They comment t h a t t h i s t h e o r e m " . . . i f c a l l e d b y , e . g. (GOAL (BL0CK2 IN B0X1}), i t s o n l y p o s s i b l e a c t i o n s a r e e i t h e r t o f i n d a Z between BL0CK2 and B0X1, o r t o f a i l . A l t h o u g h which Z i s f o u n d c a n n o t p o s s i b l y a f f e c t 2 5 Sussman and McDermott, "From PLANNER t o CONNIVER—A G e n e t i c A p p r o a c h , " p.1173. 2* Sussman and McDermott, "From PLANNER t o CONNIVER—A G e n e t i c A p p r o a c h , " p.1171. 44 s u b s e q u e n t e v e n t s , a f a i l u r e back t o t h e theorem w i l l c a u s e i t t o l o o k up a n o t h e r Z, s u c c e e d , and a l l o w i t s c a l l e r t o f a i l a g a i n i n e x a c t l y t h e same w a y ! " " The d i f f i c u l t y a r i s e s i n t h a t t h e GOAL f u n c t i o n o p e r a t e s u n d e r t h e a s s u m p t i o n t h a t e v e r y d i s t i n c t p a t h used i n s a t i s f y i n g t h e g o a l c o u l d r e s u l t i n a d i f f e r e n t i n s t a n t i a t i o n o f the GOAL p a t t e r n o r i n a d i f f e r e n t m o d i f i c a t i o n o f t h e d a t a b a s e . Thus a l l p o s s i b l e methods o f s a t i s f y i n g t h e g o a l must be t r i e d . O f t e n , however, t h i s i s n o t t h e c a s e ; d i f f e r e n t t h e o r e m s , o r e v e n t h e same theo r e m w i t h d i f f e r e n t d a t a , a s i n t h e above example, may s a t i s f y t h e g o a l s e v e r a l t i m e s w i t h o u t r e - i n s t a n t i a t i o n o f t h e p a t t e r n o r r e l e v a n t c hange t o t h e d a t a b a s e . R e s t a r t i n g c o m p u t a t i o n a s e c o n d t i m e , a f t e r r e - s a t i s f y i n g t h e g o a l i n s u c h an i n c o n s e q u e n t i a l manner, i s p o i n t l e s s . The IS f u n c t i o n b e h a v e s more as a s i n g l e t e s t o f t h e e n v i r o n m e n t . A q u e r y i s made a s t o whether o r n o t t h e s t a t e m e n t r e p r e s e n t e d by t h e p a t t e r n o c c u r s i n t h e d a t a b a s e , theorem b a s e , e n v i r o n m e n t . E q u i v a l e n t l y , i s t h e r e a m a t c h i n g datum i n t h e d a t a b a s e , o r a m a t c h i n g theorem w h i c h , when i n v o k e d , s u c c e e d s ? The way i n wh i c h t h e p a t t e r n s t a t e m e n t i s f o u n d i s t a k e n t o be o f no c o n s e q u e n c e o r s i g n i f i c a n c e . The p r o b l e m i n t h e example i s overcome by u s i n g (IS (BLOCK2 IN B0X1)) t o c a l l t h e c o n s e q u e n t t h e o r e m . * 7 Sussman anS HcDermott, "From PLANNER t o CONNIVER—A G e n e t i c A p p r o a c h , " p.1173. 45 The I S f u n c t i o n i s e a s i l y u n d e r s t o o d when c o n t r a s t e d w i t h t h e GOAL f u n c t i o n . The GOAL f u n c t i o n o p e r a t e s i n t h e f o l l o w i n g way w i t h r e s p e c t t o s u c c e s s and f a i l u r e . I n i t i a l l y an a t t e m p t i s made t o s a t i s f y t h e g o a l by f i n d i n g a m a t c h i n g datum o r i n v o k i n g m a t c h i n g theorems. I f i t i s s a t i s f i e d , t h e g o a l s u c c e e d s and t h e n e x t s t a t e m e n t a f t e r t h e GOAL i s e v a l u a t e d . The i m p o r t a n t a s p e c t , i n r e l a t i o n t o b a c k t r a c k i n g , i s t h a t i f a f a i l u r e p r o p a g a t e s b a c k f r o m t h e s t a t e m e n t f o l l o w i n g t h e GOAL, t o t h e GOAL, t h e s e a r c h f o r a m a t c h i n g datum o r s u c c e s s f u l t h e o r e m , which was s u s p e n d e d when t h e GOAL was p r e v i o u s l y s a t i s f i e d , i s r e s t a r t e d . I n c o n t r a s t , t h e IS f u n c t i o n p a s s e s t h e f a i l u r e b a c k w a r d s r a t h e r t h a n a t t e m p t i n g t o s u c c e e d a s e c o n d t i m e . I n a l l o t h e r a s p e c t s t h e o p e r a t i o n o f IS i s t h e same a s GOAL. The use o f t h e IS f u n c t i o n s o l v e s t h e p r o b l e m , a r i s i n g i n t h e example, o f a n o t h e r Z b e i n g f o u n d e v e n t h o u g h i t c o u l d have no p o s s i b l e e f f e c t upon t h e s u b s e q u e n t c o m p u t a t i o n . R a t h e r t h a n r e s t a r t i n g t h e c o m p u t a t i o n on t h e s t a t e m e n t (GOAL (?X IH ? Z ) ) , t h e f a i l u r e i s p a s s e d beyond t h e (IS (BL0CK2 IH B0X1)) s t a t e m e n t . E x a m i n a t i o n o f MICRO—PLANNER t r a c e s o f t h e g o a l s and t h e o r e m s t r i e d by t h e CONSTRUCTOR r e v e a l e d t h e o c c u r r e n c e o f e x c e s s i v e b a c k t r a c k i n g w h i c h c o u l d be e l i m i n a t e d by u s i n g t h e IS p r i m i t i v e i n p l a c e o f GOAL. The IS f u n c t i o n , added by t h e a u t h o r a s THIS t o MICRO-PLAHHER, was used s l i g h t l y more o f t e n t h a n THGOAL i n t h e i m p l e m e n t a t i o n o f t h e CONSTRUCTOR. 46 The above d i s c u s s i o n i s n o t i n t e n d e d a s a j u s t i f i c a t i o n o f t h e i m p o s i t i o n o f an a u t o m a t i c b a c k t r a c k c o n t r o l s t r u c t u r e upon t h e u s e r o f a l a n g u a g e , a s i s t h e c a s e i n PLANNER. B a c k t r a c k i n g h a s n o t t u r n e d o u t t o be a s u s e f u l a f e a t u r e a s i t might a t f i r s t have a p p e a r e d . R u l i f s o n , D e r k s e n , and W a l d i n g e r have o b s e r v e d a s h i f t , w h i c h t h e y c o n s i d e r t o be a "most s u r p r i s i n g t r e n d i n QA4 programming", away from b a c k t r a c k i n g . 2 8 N o n e t h e l e s s , b a c k t r a c k i n g may n o t be an e n t i r e l y u s e l e s s t o o l , p r o v i d e d t h a t s u f f i c i e n t c o n t r o l o v e r i t i s a v a i l a b l e . I t c a n be u s e d d u r i n g t h e i n i t i a l f o r m u l a t i o n o f s o l u t i o n s i n o r d e r t o e s t a b l i s h t h e sh a p e o f a b e t t e r f o r m u l a t i o n , and f o r t h e h a n d l i n g o f t h e e l e m e n t o f s e a r c h w h i c h e x i s t s i n a l l n o n - i d e a l a l g o r i t h m s . The d i s t i n c t i o n must be made between p o o r l y f o r m u l a t e d s o l u t i o n s t o w e l l u n d e r s t o o d p r o b l e m s , and w e l l u n d e r s t o o d a t t e m p t s t o s o l v e o b s c u r e and p e r p l e x i n g p r o b l e m s . B a c k t r a c k i n g i n PLANNER c a n be a c c u s e d o f e n c o u r a g i n g t h e f o r m e r ; c o n t r o l l a b l e b a c k t r a c k i n g may e n a b l e t h e l a t t e r . T h e r e i s no q u e s t i o n t h a t t h e f e a t u r e s o f an a s s o c i a t i v e d a t a b a s e , and p a t t e r n d i r e c t e d p r o c e d u r e i n v o c a t i o n a r e i n v a l u a b l e . They a r e t h e f a c t o r s which have c o n t r i b u t e d t o t h e s u c c e s s PLANNER has e n j o y e d d e s p i t e t h e d i f f i c u l t i e s e n c o u n t e r e d 2 8 R u l i f s o n , D e r k s e n a n d H a l d i n g e r , QA4:_A P r o c e d u r a l C a l c u l u s f o r I n t u i t i v e R e a s o n i n g , p. 289. i n c o n t r o l l i n g i t s a u t o m a t i c b a c k t r a c k i n g c o n t r o l s t r u c t u r e . 48 I I CONSTRUCTOR_Out £ U t The s o l u t i o n s t o t h e ex a m p l e s i n p r e v i o u s s e c t i o n s , and t h o s e g i v e n h e r e were p r o d u c e d by t h e CONSTRUCTOR. The CONSTRUCTOR c o d e was i n t e r p r e t e d by t h e MICRO-PLANNER i n t e r p r e t e r , m o d i f i e d t o i n c l u d e t h e THIS f u n c t i o n , which i n t u r n was o p e r a t i n g under t h e L I S P i n t e r p r e t e r (no L I S P c o m p i l e r i s p r e s e n t l y a v a i l a b l e ) i n t h e e n v i r o n m e n t o f t h e M i c h i g a n T e r m i n a l System on an IBM 360/67. F o r t h e t r i a n g l e p r o b l e m s t i m i n g s r a n g e d f r o m 20 t o 35 CPU s e c o n d s , w h i l e f o r t h e c i r c l e p r o b l e m s t h e r a n g e was f r o m 10 t o 20 CPU s e c o n d s . A r e p r e s e n t a t i v e s e l e c t i o n o f t h e s o l u t i o n s f o u n d by t h e / CONSTRUCTOR i s g i v e n b e l o w . The CONSTRUCTOR, a s w e l l a s n o t s o l v i n g p r o b l e m s c o n c e r n i n g f i g u r e s w h i c h a r e d i f f e r e n t t h a n t h o s e s p e c i f i e d i n t h e s e c t i o n "The Domain", h a s a s i t s most s e r i o u s l i m i t a t i o n , t h e f a c t t h a t i t c a n n o t s o l v e any p r o b l e m r e g u i r i n g t h e i n t r o d u c t i o n o f a new p o i n t . E x a m p l e s o f s u c h p r o b l e m s a r e : c o n s t r u c t a t r i a n g l e g i v e n two s i d e s and t h e median t o t h e t h i r d s i d e ; and c o n s t r u c t a t r i a n g l e g i v e n i t s t h r e e medians. The l a t t e r p r o b l e m i s d i s c u s s e d i n more d e t a i l i n t h e s e c t i o n " D i r e c t i o n s f o r F u r t h e r R e s e a r c h " . A p p r o x i m a t e l y f i v e CPU m i n u t e s a r e r e q u i r e d i n o r d e r f o r t h e CONSTRUCTOR t o abandon s u c h p r o b l e m s and a d m i t f a i l u r e . The f o l l o w i n g comments may h e l p i n t h e u n d e r s t a n d i n g o f t h e o u t p u t f r o m t h e CONSTRUCTOR. The o u t p u t b e g i n s w i t h a s t a t e m e n t 49 o f t h e names t h e CONSTRUCTOR h a s g e n e r a t e d f o r t h e g e o m e t r i c e l e m e n t s r e f e r e d t o i n t h e p r o b l e m . F o l l o w i n g t h i s t h e r e i s a l i s t o f a l l t h e a s s e r t i o n s i n t h e d a t a b a s e g e n e r a t e d by t h e i n p u t and p h r a s e s p e c i a l i s t s . A f t e r t h e d a t a b a s e dump, a l l " c o n d i t i o n s w h i c h were s e t up a s g o a l s a r e p r i n t e d . I n a d d i t i o n , t h e p o i n t s i n t h e f i g u r e w h i c h were unknown, and t h e number o f l o c i which had been f o u n d f o r t h e f i r s t p o i n t on t h e l i s t o f unknown p o i n t s , a t t h e t i m e t h e g o a l was a t t e m p t e d , i s g i v e n . The f i n a l p a r t o f t h e o u t p u t i s t h e a l g o r i t h m f o r t h e c o n s t r u c t i o n o f t h e s o l u t i o n f i g u r e . I t i s a l i s t o f i n s t r u c t i o n s , e a c h i n s t r u c t i o n e n c l o s e d i n a s e p a r a t e s e t o f p a r e n t h e s e s . 50 ( c o n s t r u c t a r i g h t t r i a n g l e g i v e n a l e g and t h e a l t i t u d e t o t h e h y p o t e n u s e ) AC OF LINE2 , AND BC OF LINE3) BE OF LENGTH LEN4) NINETY)) CONSTRUCTING TRIANGLE A B C ) AB IS A SEGMENT OF LINE LINE1 AB IS A GIVEN SIDE) LET THE GIVEN ALTITUDE (ANGLE BAC EQUAL ANGLE (LINE LINE3) ) (LINE LINE2)) (LINE LINE1) ) (TRIANGLE A B C ) ) (RIGHT TRIANGLE A B C)) C)) B)) A)) A (CONDITION-ON A, ST ALTITUDE ft TO LINE3 IS LENU) ) (POINT (POINT (POINT (POINT 100) (POINT (POINT (POINT (POINT (C ON A (CONDITION-ON C (CONDITION-ON B (CONDITION-ON A (CONDITION-ON LINE3) ) LINE2)) LINE3) ) LINE1)) LINE2) ) LINE 1 ) ) LENGTH A ST RIGHT TRIANGLE A B C ) ) C ST TRIANGLE A B C ) ) . 20) B ST TRIANGLE A B C ) ) . 20) A ST TRIANGLE A B C ) ) . 20) 50) ,(C ON (B ON (B ON (A ON (A ON (KNOWN (KNOWN LENGTH (KNOWN TRYING LEN4) ) AB) ) ANGLE NINETY) ) CONDITION: (CONDITION-ON A ST ALTITUDE A TO LINE3 IS LEN4) ) < UNKNOWN POINTS (A B C) NO. OF TRYING CONDITION: (CONDITION-ON A LEN4)) UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS (DRAW LINE LINE3 LOCI FOUND: 0) ST ALTITUDE A TO LINE3 IS FOUND: 1) RIGHT TRIANGLE A FOUND: 1) TRIANGLE A B C)) FOUND: 1) TRIANGLE A B C ) ) (A B C) NO. OF LOCI (CONDITION-ON A ST A B C ) ) (A B C) NO. OF LOCI (CONDITION-ON A ST (A B C) NO. OF LOCI (CONDITION-ON C ST (C) NO. OF LOCI FOUND: 0) (CONDITION-ON C ST TRIANGLE A B C ) ) (C) NO. OF LOCI FOUND: 1) ANYWHERE) (POINT A IS ON A LINE PARALLEL TO LINE3 AT DISTANCE LEN4) (PLACE POINT B ANYWHERE ON LINE3) (POINT A IS ON THE CIRCLE WITH CENTER B RADIUS AB) (ANGLE BAC IS EQUAL TO ANGLE NINETY)(CONSTRUCT LINE LINE2 THRU POINT A (AT ANGLE BAC TO LINE LINE1)) (C IS ON LINE LINE2) (C IS ON LINE LINE3)) / 51 ( c o n s t r u c t a c i r c l e t a n g e n t t o a g i v e n l i n e and t a n g e n t t o a s e c o n d i n t e r s e c t i n g l i n e a t a g i v e n p o i n t ) (CIRCLE CIRCLE** IS TANGENT TO LINE LINE6) (THE CIRCLE IS TANGENT TO THE LINE LINE7 AT POINT C) ((INTERSECTING LINE7 LINE6)) ((RADIOS CIRCLEU RADIUS5) ) ( (CIRCLE CIRCLEU)) ((CIRCLEU TANGENT LINE6)) ((CIRCLED TANGENT LINE7 AT C)) ( ( L I N E LINE7)) ( (LINE LINE6) ) ( (POINT C) ) ( (POINT A) ) ((POINT A (CONDITION-ON A CENTER CIRCLE CIRCLEU)) . 100) ( (C ON CIRCLEU) ) ((C ON LINE7)) ( (B ON CIRCLEU) ) ((B ON LINE6)) ( (A CENTER CIRCLEU)) ( (KNOWN LINE L I N E 7 ) ) ( (KNOWN POINT C)) ( (KNOWN LINE LINE6)) (TRYING CONDITION: (CONDITION-ON A CENTER CIRCLE CIRCLEU)) ( UNKNOWN POINTS (A) NO. OF LOCI FOUND: 0) (TRYING CONDITION: (CONDITION-ON A CENTER CIRCLE CIRCLEU)) ( UNKNOWN POINTS (A) NO. OF LOCI FOUND: 1) ((CENTER POINT A IS ON THE BISECTOR OF THE ANGLE FORMED BY LINES LINE6 AND LINE7) (CENTER POINT A IS ON A LINE PERPENDICULAR TO LINE7 AT POINT C)) ( c o n s t r u c t an i s o s c e l e s t r i a n g l e g i v e n a bas e a n g l e and t h e a l t i t u d e t o a l e g ) (CONSTRUCTING TRIANGLE A B C) 52 AB I S A SEGMENT OF LINE LINE8 , AC OF LINE9 , AND BC OF LINE10) ANGLE ABC IS A GIVEN ANGLE) LET THE GIVEN ALTITUDE BE OF LENGTH LEN11) (ANGLE ABC EQUAL ANGLE ACB) ) (ISOSCELES TRIANGLE A B C ) ) (LENGTH AB EQUAL LENGTH AC)) (LINE LINE10)) (LINE LINE9) ) (LINE LINE8) ) (TRIANGLE A B C ) ) (POINT C)) (POINT B)) (POINT A) ) (POINT C (CONDITION-ON C ST ALTITUDE C TO LINE8 IS LEN11)) 100) (POINT A (CONDITION-ON A ST A EQUIDISTANT B AND C)) . HO) (POINT C (CONDITION-ON C ST TRIANGLE A B C ) ) . 20) (POINT B (CONDITION-ON B ST TRIANGLE A B C ) ) . 20) (POINT A (CONDITION-ON A ST TRIANGLE A B C ) ) . 20) (C ON LINE10)) (C ON LINE9)) (B ON LINE10)) (B ON LINE8) ) (A ON LINE9)) (A ON LINE8) ) (KNOWN LENGTH LEN11)) (KNOWN ANGLE ABC)) TRYING CONDITION: LEN11)) UNKNOWN POINTS TRYING CONDITION: LEN11)) UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS TRYING CONDITION: UNKNOWN POINTS (A) NO. OF LOCI FOUND: 0) TRYING CONDITION: (CONDITION-ON A ST A EQUIDISTANT B AND C) ) UNKNOWN POINTS (A) NO. OF LOCI FOUND: 1) TRYING CONDITION: (CONDITION-ON A ST TRIANGLE A B C ) ) UNKNOWN POINTS (A) NO. OF LOCI FOUND: 1) (CONDITION--ON C ST ALTITUDE C TO LINE8 IS (C A B) NO. OF LOCI FOUND: 0) (CONDITION--ON C ST ALTITUDE C TO LINE8 IS (C A B) NO. OF LOCI FOUND: 1) (CONDITION--ON C ST TRIANGLE A B C)) (C A B) NO. OF LOCI FOUND: 1) (CONDITION--ON A ST A EQUIDISTANT B AND C)) ((DRAW LINE LINE8 ANYWHERE) (POINT C IS ON A LINE PARALLEL TO LINE8 AT DISTANCE LEN11) (PLACE POINT B ANYWHERE ON LINE8) (CONSTRUCT LINE LINE10 THRU POINT B (AT ANGLE ABC TO LINE LINE8)) (C IS ON LINE LINE10) (POINT A IS ON THE PERPENDICULAR BISECTOR OF BC) (A IS ON LINE LINE8)) 53 ( c o n s t r u c t a c i r c l e o f g i v e n r a d i u s which i s t a n g e n t t o a g i v e n c i r c l e a t a g i v e n p o i n t ) (LET THE RADIOS BE OF LENGTH RADIUS 13) (THE CIRCLE IS TANGENT TO THE CIRCLE CIRCLE14 AT POINT B) ((RADIUS CIRCLE1 2 RADIUS 1 3) ) ((C I R C L E CIRCLE14)) ( (CIRCLE CIRCLE12)) ( (CIRCLE12 TANGENT CIRCLE14 AT B) ) ( (POINT B) ) ( (POINT ft) ) ( (POINT A (CONDITION-ON A CENTER CIRCLE CIRCLE12)) . 100) ( (B ON CIRCLE1 2) ) ( (B ON CIRCLE14)) ((A CENTER CIRCLE12)) ( (KNOWN CIRCLE CIRCLE14)) ( (KNOWN POINT B) ) ( (KNOWN LENGTH RADIUS 13)) (TRYING CONDITION: (CONDITION-ON A CENTER CIRCLE CIRCLE12)) ( UNKNOWN POINTS (A) NO. OF LOCI FOUND: 0) v (TRYING CONDITION: (CONDITION-ON A CENTER CIRCLE CIRCLE12)) ( UNKNOWN POINTS (A) NO. OF LOCI FOUND: 1) ( (CENTER POINT A IS ON A CIRCLE CENTER B WITH RADIUS RADIDS13) ( CENTER POINT A IS ON A LINE THRU POINT B AND THE CENTER OF CIRCLE14)) ( c o n s t r u c t a r i g h t t r i a n g l e g i v e n a ba s e a n g l e and t h e h y p o t e n u s e (CONSTRUCTING TRIANGLE A B C ) (AB IS A SEGMENT OF LINE LINE1 , AC OF LINE2 , AND BC OF LINE3 (ANGLE ABC IS A GIVEN ANGLE) (BC IS THE HYPOTENUSE) ( (ANGLE BAC EQUAL ANGLE NINETY)) ( (LINE L I N E 3 ) ) ( (LINE LINE2)) ( (LINE LINE1) ) ( (TRIANGLE A B C ) ) ( (RIGHT TRIANGLE A B C ) ) ( (POINT C) ) ((POINT B)) 54 (POINT &) ) (POINT a (CONDITION-ON a ST RIGHT TRIANGLE A B C ) ) . 5 0 ) (POINT C (CONDITION-ON C ST TRIANGLE A B C ) ) . 20) (POINT B (CONDITION-ON B ST TRIANGLE A B C ) ) . 2 0 ) (POINT A (CONDITION-ON A ST TRIANGLE A B C ) ) . 2 0 ) (C ON LINE3) ) (C ON LINE2)) (B ON LIN E 3 ) ) (B ON LINE1) ) (A ON LINE2) ) (A ON LINE1)) (KNOWN LENGTH BC)) (KNOWN ANGLE ABC)) (KNOWN ANGLE NINETY)) TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS TRYING CONDITION UNKNOWN POINTS (CONDITION (A B C) NO. (CONDITION (A B C) NO (CONDITION (A B C) NO (CONDITION (A B C) NO. (CONDITION (A B C) NO (CONDITION (A B C) NO. (CONDITION (A B C) NO (CONDITION (A B C) NO. (CONDITION (A) NO. OF (CONDITION (A) NO. OF (CONDITION (A) NO. OF -ON A ST RIGHT TRIANGLE A B C ) ) OF LOCI FOUND: 0) -ON A ST TRIANGLE A B C ) ) OF LOCI FOUND: 0) -ON A ST RIGHT TRIANGLE A B C ) ) OF LOCI FOUND: 1) -ON A ST TRIANGLE A B C ) ) OF LOCI FOUND: 1) -ON A ST RIGHT TRIANGLE A B C ) ) OF LOCI FOUND: 1) -ON A ST TRIANGLE A B C ) ) OF LOCI FOUND: 1) -ON B ST TRIANGLE A B C ) ) OF LOCI FOUND: 0) -ON B ST TRIANGLE A B C ) ) OF LOCI FOUND: 1) -ON A ST RIGHT TRIANGLE A B C ) ) LOCI FOUND: 0) -ON A ST RIGHT TRIANGLE A B C ) ) LOCI FOUND: 1) -ON A ST TRIANGLE A B C ) ) LOCI FOUND: 1) ((DRAW LINE LINE3 ANYWHERE) (B IS ON LINE LINE3) (PLACE POINT C ANYWHERE ON LINE3) (POINT B IS ON THE CIRCLE WITH CENTER C RADIUS BC) (DRAW CIRCLE WITH CENTER H AT THE MIDPOINT OF BC RADIUS BH) (CONSTRUCT LINE LINE1 THRU POINT B (AT ANGLE ABC TO LINE LINE3)) (A IS ON LINE LINE1)) 55 1 D i r e c t i o n s F o r F u r t h e r R e s e a r c h T h e r e a r e s e v e r a l a r e a s i n which f u r t h e r d e v e l o p m e n t c o u l d p r o c e e d . The COHSTROCTOR c o u l d e a s i l y be expanded t o h a n d l e a b r o a d e r c l a s s o f f i g u r e s t h a n c i r c l e s and t r i a n g l e s . O t h e r p o s s i b l e c a n d i d a t e s f o r c o n s t r u c t i o n m i g h t i n c l u d e : q u a d r i l a t e r a l s s u c h a s p a r a l l e l o g r a m s , s q u a r e s , and t r a p e z o i d s ; as w e l l a s l i n e s . O t h e r c o n s t r u c t i o n s i n which t h e s o l u t i o n f i g u r e i s composed o f s e v e r a l s u b f i g u r e s c o u l d a l s o be s o l v e d , a l t h o u g h a d i f f i c u l t y a r i s e s i n c o m m u n i c a t i n g t h e p r o b l e m s p e c i f i c a t i o n . Some f o r m o f i n p u t o t h e r t h a n a s i n g l e E n g l i s h s e n t e n c e would have t o be e m p l o y e d . The r e p e t o i r e o f t h e c u r r e n t s y s t e m c o u l d be expanded t o i n c l u d e p r o b l e m s i n t h r e e d i m e n s i o n s . J u s t a s two i n t e r s e c t i n g l o c i d e t e r m i n e s o l u t i o n p o i n t s i n two d i m e n s i o n s s o does t h e i n t e r s e c t i o n o f t h r e e l o c i i n t h r e e d i m e n s i o n s . The l o c i i n t h r e e d i m e n s i o n s a r e s u r f a c e s r a t h e r t h a n c u r v e s , b u t t h i s would n o t r e s u l t i n any c o m p l i c a t i o n . The s o l u t i o n f i g u r e c o u l d be a c t u a l l y drawn i f g r a p h i c s r o u t i n e s were d e v e l o p e d f o r t h e i n t e r p r e t a t i o n o f the o u t p u t a l g o r i t h m . T h e s p e c i f i c a t i o n o f d i f f e r e n t v a l u e s f o r t h e g i v e n l e n g t h s and a n g l e s o f t h e p r o b l e m would r e s u l t i n d i f f e r e n t s o l u t i o n f i g u r e s . One o f t h e s t i p u l a t i o n s l i m i t i n g t h e t y p e o f p r o b l e m u n d e r c o n s i d e r a t i o n i s t h a t t h e y must n o t be c o n t r a d i c t o r y and hence 56 u n s o l v a b l e . The CONSTRUCTOR d o e s n o t a t t e m p t t o p r o v e a c o n s t r u c t i o n i m p o s s i b l e ; i t s i m p l y s u c c e e d s w i t h an a l g o r i t h m o r r e p o r t s f a i l u r e . One t e c h n i g u e which c o u l d be used i n e x t e n d i n g t h e CONSTRUCTOR t o p r o v e t h e i m p o s s i b i l i t y o f a c o n s t r u c t i o n i s a n a l a g o u s t o t h e ' p a t t e r n o f two l o c i * . I f a p o i n t i s f o u n d t o be oh two l o c i , and t h e l o c i c a n be p r o v e d t o be n o n - i n t e r s e c t i n g , t h e n t h e c o n s t r u c t i o n i s i m p o s s i b l e . Examples o f l o c i which do n o t i n t e r s e c t a r e : two p a r a l l e l l i n e s and a l s o , two c o n c e n t r i c c i r c l e s . Not a l l c o n s t r u c t i o n p r o b l e m s a r e s o l v a b l e u s i n g o n l y t h e • p a t t e r n o f two l o c i 1 . I t i s , however, a b a s i c t e c h n i g u e , and i s r e g u i r e d i n f o r m i n g a t l e a s t p a r t o f t h e s o l u t i o n i n a l l s t r a i g h t - e d g e and compass c o n s t r u c t i o n s . The ' p a t t e r n o f two l o c i ' c a n be u s e d i n c o n s t r u c t i n g t h e ' s t e p p i n g s t o n e ' which i s r e f e r e d t o i n t h e ' p a t t e r n o f a u x i l i a r y f i g u r e s ' . " t r y t o d i s c o v e r some p a r t o f t h e f i g u r e o r some c l o s e l y r e l a t e d f i g u r e w h i c h you c a n c o n s t r u c t and which you c a n use a s a s t e p p i n g s t o n e i n c o n s t r u c t i n g t h e o r i g i n a l f i g u r e . " 2 9 D i s c o v e r i n g which a u x i l i a r y f i g u r e w i l l be o f use i s i n i t s e l f a d i f f i c u l t p r o b l e m f o r which t h e a u t h o r i s c u r r e n t l y d e v e l o p i n g t e c h n i g u e s . The employment o f a d i a g r a m would, o f c o u r s e , be i m p e r a t i v e when l o o k i n g f o r a u x i l i a r y f i g u r e s . An a u x i l i a r y 2 9 P o l y a , . M a t h e m a t i c a l D i s c o v e r y , V o l . 1, p. 15. 57 f i g u r e need n o t n e c e s s a r i l y o c c u r a s a p a r t o f t h e d i a g r a m o f t h e s o l u t i o n f i g u r e , b u t may be f o r m e d by t h e i n t r o d u c t i o n o f new p o i n t s and l i n e s , i n o t h e r words a c o n s t r u c t i o n . 3 0 A geome t r y t h e o r e m p r o v e r s u c h a s t h a t o f G o l d s t e i n would a l s o have a p l a c e a s a s u b p a r t o f a more p o w e r f u l s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o g r a m . A p r o o f t h a t an a u x i l i a r y f i g u r e h a s p a r t i c u l a r p r o p e r t i e s may be r e q u i r e d b e f o r e i t c a n be c o n s t r u c t e d . As an example c o n s i d e r t h e p r o b l e m , " C o n s t r u c t a t r i a n g l e g i v e n t h e t h r e e m e d i a n s " . C o n s t r u c t a t r i a n g l e g i v e n t h e t h r e e m e d ians An a u x i l i a r y f i g u r e , c o n s t r u c t a b l e by t h e CONSTRUCTOR, i s t r i a n g l e MGD. A new p o i n t D, t h e m i d p o i n t o f AM, i s i n t r o d u c e d i n t o t h e d i a g r a m . I t i s n e c e s s a r y t o p r o v e t h a t GD = MF, and t o r e c a l l t h e e s t a b l i s h e d r e s u l t t h a t t h e medians o f a t r i a n g l e i n t e r s e c t a t a p o i n t 2/3 t h e d i s t a n c e f r o m t h e v e r t i c e s a l o n g t h e me d i a n s . Once a t r i a n g l e MGO has been c o n s t r u c t e d , a n g l e GMD i s known. W i t h t h i s new i n f o r m a t i o n t r i a n g l e GAM c a n be c o n s t r u c t e d by t h e CONSTRUCTOR, and he n c e t r i a n g l e ABC. B o t h t h e CONSTRUCTOR and G o l d s t e i n * s theorem p r o v e r c o u l d be used a s s u b s y s t e m s . so The word ' c o n s t r u c t i o n * i s us e d h e r e i n a t h e o r e m p r o v i n g c o n t e x t and means t h e i n t r o d u c t i o n o f a new e l e m e n t i n t o t h e p r o b l e m , n o t t h e d i s c o v e r y o f a f i g u r e . 58 FIGURE I I I 59 VI C o n c l u s i o n T h i s s t u d y has begun t o e x p l o r e t h e embodiment, m a n i p u l a t i o n , and e x t e n t o f t h e knowledge r e q u i r e d f o r t h e d i s c o v e r y o f f i q u r e s s a t i s f y i n g a c o m p l e t e and c o n s i s t e n t s e t o f c o n s t r a i n t s . F o r t h e d e l i n e a t i o n and management o f t h e knowledge, p r o c e d u r e s have been e x p e r i m e n t e d w i t h a s a r e p r e s e n t a t i o n , and t h e p a t t e r n o f two l o c i has been t e s t e d a s a framework. A b a s e o f knowledge c o n s i s t i n g o f e s t a b l i s h e d r e s u l t s , some o f w h i c h a r e common t o t h e t h e o r e m p r o v e r s o f G e l e r n t e r and G o l d s t e i n , was r e q u i r e d . T h e r e i s a d i f f e r e n c e i n t o n e between t h e m a j o r i t y o f r e s u l t s used i n t h e two t a s k s however. The t h e o r e m p r o v e r s use r e s u l t s s t a t i n g t h a t i f c e r t a i n c o n d i t i o n s a r e met t h e n a p a r t i c u l a r c o n c l u s i o n i s j u s t i f i e d and v a l i d . The CONSTRUCTOR u s e s r e s u l t s s t a t i n g t h a t i f c e r t a i n c o n d i t i o n s e x i s t i n a p a r t i a l l y c o n s t r u c t e d f i g u r e t h e n i t i s p o s s i b l e t o c o n t i n u e t h e c o n s t r u c t i o n by f o l l o w i n g s p e c i f i c i n s t r u c t i o n s and d r a w i n g a n o t h e r l o c u s . The t h e o r e m p r o v e r s use a r e s u l t t o make a n o t h e r s t e p i n a p r o o f ; t h e CONSTRUCTOR u s e s a r e s u l t t o make a n o t h e r s t e p i n t h e c o n s t r u c t i o n o f a f i g u r e . E n c o d i n g t h e r e l e v a n t knowledge a s programs p r o v e d t o be b o t h a f l e x i b l e and a d e q u a t e a p p r o a c h . I t i s p o s s i b l e t o m a i n t a i n a c l a r i t y o f mind when e x p r e s s i n g theorems a s p r o c e d u r e s b e c a u s e t h e y a r e w r i t t e n i n t h e f i r s t p e r s o n . The 60 programmer dons t h e c l o a k o f a theo r e m and t h e n d e s c r i b e s i t s b e h a v i o u r a s h i s own. T h i s d o e s n o t i m p l y t h a t a l l s u c h p r o c e d u r e s must be c o n s i d e r e d t o be i n d e p e n d e n t . PLANNER e n c o u r a g e s t h i s a s s u m p t i o n , b u t i t i s n e i t h e r n e c e s s a r y n o r d e s i r a b l e . A p r o c e d u r e s h o u l d and c o u l d be a b l e t o behave i n a c c o r d a n c e w i t h t h e f a i l u r e s and a c c o m p l i s h m e n t s o f o t h e r p r o c e d u r e s . I t i s n a t u r a l t o f i r s t make t h e i n d e p e n d e n c e a s s u m p t i o n , w r i t e p r o c e d u r e s , and o b s e r v e t h e i r p e r f o r m a n c e ; t h e n d i s c a r d i n g t h e a s s u m p t i o n , i n t e r a c t i o n s between p r o c e d u r e s c a n be added on t h e b a s i s o f t h e i r o b s e r v e d b e h a v i o u r . R e g a r d l e s s o f t h e s h o r t c o m i n g s o f PLANNER i n t h i s r e s p e c t , t h e a b i l i t y t o f o r m u l a t e g e o m e t r i c c o n c e p t s a s p r o c e d u r e s p r o v e d i n v a l u a b l e . I t would be r e a s o n a b l e t o ask why a d i a g r a m was n e v e r used as an a i d i n s o l v i n g c o n s t r u c t i o n p r o b l e m s a s i t was by G e l e r n t e r and G o l d s t e i n i n p r o v i n g t h e o r e m s . O r i g i n a l l y i t was t h o u g h t t h a t a d i a g r a m would be e s s e n t i a l ; however, i n t h e a p p l i c a t i o n o f t h e ' p a t t e r n o f two l o c i ' a d i a g r a m s i m p l y i s n o t n e c e s s a r y . A l l t h e i n f o r m a t i o n c o n t a i n e d i n t h e p r o b l e m s t a t e m e n t c an be r e p r e s e n t e d d i r e c t l y i n t h e d a t a b a s e . T h e r e i s d e f i n i t e l y a p l a c e f o r d i a g r a m s i n t h e s o l u t i o n o f c o n s t r u c t i o n p r o b l e m s , b u t i t i s a s s o c i a t e d more w i t h t h e theorem p r o v i n g a s p e c t s o f t h e p r o b l e m . B e f o r e a l o c u s which m i g h t s a t i s f y t h e r e s t r i c t i o n s on a p o i n t c a n be drawn, o t h e r p o i n t s , l e n g t h s o r s l o p e s may have to' be f o u n d . Such f a c t s may p o s s i b l y be 61 d e t e r m i n e d by p r o v i n g t h e o r e m s r e l a t i n g them t o o t h e r known f a c t s . F o r example, an unknown l e n g t h may be t h a t o f a s i d e o f a q u a d r i l a t e r a l whose o p p o s i t e s i d e i s known. The unknown l e n g t h i s d e t e r m i n e d i f t h e q u a d r i l a t e r a l c a n be p r o v e n t o be a p a r a l l e l o g r a m . T h u s , t h e mechanism f o r t h e d e t e r m i n a t i o n o f t h e s e o t h e r f a c t s i s the o r e m p r o v i n g . The s o p h i s t i c a t i o n o f t h e m a c h i n e r y a v a i l a b l e i n t h e CONSTRUCTOR f o r t h i s i s n o t e x t e n s i v e , and i t i s i n e x t e n d i n g i t t h a t d i a g r a m s would have t o be i n t r o d u c e d . An e x c e l l e n t framework i s p r o v i d e d by t h e " p a t t e r n o f two loci» f o r t h e s o l u t i o n o f a l a r g e c l a s s o f s t r a i g h t - e d g e and compass c o n s t r u c t i o n p r o b l e m s o f a h i g h s c h o o l l e v e l . I n a d d i t i o n , a m a s t e r y o f t h e • p a t t e r n o f two l o c i * i s p r e r e q u i s i t e t o s o l v i n g more d i f f i c u l t p r o b l e m s . / 62 1. Baumgart, B r u c e G. M i c r o - p l a n n e r A l t e r n a t e R e f e r e n c e M a n u a l . P a l o a l t o , C a l i f . : S t a n f o r d U n i v e r s i t y , SAILON~no. 67, 1972. 2. G e l e r n t e r , H., J.R. Hansen, and D.W. L o v e l a n d . " E m p i r i c a l E x p l o r a t i o n s o f t h e Geometry-Theorem P r o v i n g M a c h i n e . " C o m p u t e r s and T h o u g h t . Ed. Edward A. Feigenbaum and J u l i a n Feldman. Hew Y o r k : McGraw H i l l , 1963, pp.153-163. 3. G e l e r n t e r , H. " R e a l i z a t i o n o f a Geometry-Theorem P r o v i n g M a c h i n e . " c9fP*?l£E s, and .Thought. E d . E . a . Feigenbaum and J . Feldman. Hew Y o r k : McGraw H i l l , 1963, pp.134-152. 4. G o l d s t e i n , I r a . E l e m e n t a r y G e o m e t r y Theorem p r o v i n g . C a m b r i d g e , Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , A l Memo no. 280, 1973. 5. H e w i t t , C a r l . D e s c r i p t i o n and T h e o r e t i c a l A n a l y s i s ( U s i n g Schemata), o f P l a n n e r : A Language f o r P r o v i n g _ T h e g r e m s a n d _ M a n i g u l a t i n g _ M o d g l s _ i n _ a _ R C a m b r i d g e , Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , R e v i s e d Ph.D. D i s s e r t a t i o n , A l T e c h n i c a l R e p o r t no. 258, 1972. 6. Morgan, P.M. And w.E. B r e c k e n r i d g e . P l a n e . G e o m e t r y . T o r o n t o , Ont.: Thomas N e l s o n & Sons, Rev. Ed., 1954. 7. P o l y a , G e o r g e . M a t h e m a t i c a l D i s c o v e r y : On U n d e r s t a n d i n g , L e a r n i n g and T e a c h i n g P r o b l g m S o l v i n g . New Y o r k : J o h n W i l e y S Sons, V o l . 1 , 1962. 8. P r i c e , K e i t h . " S a t i s f y i n g G e o m e t r i c C o n s t r a i n t s . " C a m b r i d g e , Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , u n p u b l i s h e d B a c h e l o r ' s P a p e r , 1971. 9. R u l i f s o n , J . F . , J.A. D e r k s e n and R . J . W a l d i n g e r . QA4: A P r o c e d u r a l C a l c u l u s f o r I n t u i t i v e R e a s o n i n g . Menlo 63 P a r k , C a l i f . : S t a n f o r d R e s e a r c h I n s t i t u t e , A r t i f i c i a l I n t e l l i g e n c e C e n t e r T e c h n i c a l Note 73, 1972. 10. Sussman, G e r a l d J . And Drew V. HcDermott. The_CONMIVER R e f e r e n c e Manual. C a m b r i d g e , Mass.: H a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , AI Memo no. 259, 1972. 11., Sussman, G e r a l d J . And Drew V. HcDermott. "From PLANNER t o CONNIVER - A G e n e t i c A p p r o a c h . " F a l l _ J . o i n t C o m p u t e r . C o n f e r e n c e - 1 9 7 2 , pp. 1171-1179. ~ 12. Sussman, G.J., T. W i n o g r a d and E. C h a r n i a k . MICRO-PLANNER R e f e r e n c e H a n u a l . C a m b r i d g e , Mass.: H a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , AI Memo no. 203A, 1971. 13. „ Sussman, G.J. And D.V. HcDermott. W h v _ C o n n i v i n q _ i s B e t t e r ^ t h a n P l a n n i n g . C a m b r i d g e , H a s s T T H a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , AI Memo no. 255A, 1972. 14. w e l c h o n s , A.M., W.R. K r i c k e n b e r g e r and H.R. P e a r s o n . P l a n e _ G e g m g t r y . B o s t o n , Mass.: G i n n , 1958. 15. Win o g r a d , T e r r y . P r o c e d u r e s a s a R e p r e s e n t a t i o n f o r Data i n a Computer Program f o r 0nderstandiD3_Natural ~ Lan g u a g e . C a m b r i d g e , Mass.: M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , R e v i s e d Ph.D. D i s s e r t a t i o n , MAC TR -84, 1971. 16. W i l c o x , B. And C. H a f n e r . LISP/MTS U s e r ' s G u i d e . Ann A r b o r , M i c h . : M e n t a l H e a l t h R e s e a r c h ~ l n s t l t u t e 7 ~ 1 9 7 3 . 17. Wong, R i c h a r d . C o n s t r u c t i o n H e u r i s t i c s f o r Geometry and a V e c t o r A l g e b r a R e p r e s e n t a t i o n o f Geometry. ~Cambridge7 Mass.: H a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , T e c h n i c a l Memo no. 28, 1972. 64 A p p e n d i x I (a) Draw a c i r c l e g i v e n i t s c e n t e r and r a d i u s . (b) Draw a l i n e g i v e n two p o i n t s on i t . (c) Draw an a n g l e e q u a l t o a n o t h e r g i v e n a n g l e . (d) Draw a l i n e a t a g i v e n d i s t a n c e , and p a r a l l e l t o a g i v e n l i n e . (e) Draw t h e p e r p e n d i c u l a r t o a g i v e n l i n e a t a g i v e n p o i n t . (f ) F i n d t h e m i d p o i n t o f a g i v e n l i n e segment. (g) Draw t h e b i s e c t o r o f a g i v e n a n g l e . (h) Draw t h e p e r p e n d i c u l a r b i s e c t o r t o a g i v e n l i n e segment. ( i ) Draw a l i n e a t a g i v e n a n g l e t o a g i v e n l i n e , and a t a g i v e n p o i n t on t h e i t . 65 A p p e n d i x , I I Sample _ C o n s e q u e n t Knowledge S p e c i a l i s t s ( t h c o n s e c - a l t 1 ; t h e l o c u s o f a p o i n t a known d i s t a n c e ;from a known l i n e i s a l i n e p a r a l l e l ; t o t h a t l i n e ( ( t h r e s t r i c t a •(lambda (x) (eg $?p x ) ) ) p l i n e h) ( c o n d i t i o n - o n $?p s t a l t i t u d e $?a t o $ ? l i n e i s $?h) ( t h i s (known l e n g t h $?h) ( t h u s e c - l e n g t h 2 c - l e n g t h 1 ) ) ( t h i s ( d e t e r m i n e l i n e $ ? l i n e ) ( t h u s e c - d t r m n l i n e ) ) ( c o n s t r u c t i o n p o i n t $?a i s on a l i n e p a r a l l e l t o $ ? l i n e a t d i s t a n c e $?h)) ( t h c o n s e c - a n g l e 1 ; an a n g l e i s known i f i t i s ; i s t h e a n g l e o f i n t e r s e c t i o n o f 2 known l i n e s , (a e v f ) (known a n g l e $?a) ( t h u n i g u e ' a n g l e $?a) ( t h g o a l ( e x p l o d e $?a $?e $?v $ ? f ) (thnodb) ( t h u s e c - e x p l o d e ) ) ( t h i s (known l i n e ( t h e v ( l i n e $?e $ ? v ) ) ) ( t h u s e c - l i n e t e s t ) ) ( t h i s (known l i n e ( t h e v ( l i n e $ ? f $ ? v ) ) ) ( t h u s e c - l i n e t e s t ) ) ( t h a s s e r t (known a n g l e $ ? a ) ) ) ( t h c o n s e c - a s s u m e l i n e ; a s s u m i n g a l i n e means t o ; a l i n e may be assumed t o ; i f no o t h e r l i n e has been (1 p o i n t ) (assume l i n e $?1) ( t h n o t ( t h g o a l (assumed l i n e M ? M ) ) ) ( t h a s s e r t (known l i n e $?1)) ( t h a s s e r t (assumed l i n e $?1)) d e t e r m i n e i t s p o s i t i o n a r b i t r a r i l y be known assumed 66 ( t h c o n d ( ( t h a n d ( t h g o a l ( $ ? p o i n t on $ ? 1 ) ) ; i f a p o i n t on t h e l i n e i s known t h e n ( t h g o a l (known p o i n t $ ? p o i n t ) ) ) ( c o n s t r u c t i o n draw l i n e $ ? 1 anywhere t h r u p o i n t $ ? p o i n t ) ) ; t h e l i n e must p a s s t h r u i t ( ( t h n o t ( t h g o a l (known p o i n t " ? " ) ) ) ( c o n s t r u c t i o n draw l i n e $ ? 1 anywhere)) ; o t h e r w i s e i t may go anywhere ( t ( t h f a i l t h e o r e m ) ) ) ) ( t h c o n s e c - d t r m n l i n e ; t o d e t e r m i n e a l i n e means t o f i r s t ;see i f i t i s known ( i n t h e d a t a b a s e o r by d e d u c t i o n ) ; and i f i t i s n o t known t o assume t h a t i t i s known (1 p o i n t ) ( d e t e r m i n e l i n e $?1) { t h o r ( t h i s (known l i n e $?1) ( t h u s e c - l i n e t e s t ) ) ( t h i s (assume l i n e $?1) ( t h u s e c - a s s u m e l i n e ) ) ) ( t h f a i l ? t • ( t h f a i l t h e o r e m ) ) ) ; i f f a i l u r e b a c k s up t o t h i s p o i n t t h e whole ;theorem s h o u l d f a i l ( t h c o n s e c - l i n e 2 ; a l i n e i s known i f i t p a s s e s t h r u ;a known p o i n t and has known s l o p e , ( l a s ) ( f i n d l i n e $?1) ( t h c o n d ( ( t h a n d ( t h g o a l ($?a on $ ? 1 ) ) ( t h g o a l (known p o i n t $ ? a ) ) ) ) ( ( t h a n d ( t h g o a l ($?a on $ ? 1 ) ) ( t h i s (known p o i n t $?a) (thnodb) ( t h u s e c - d t r m n p o i n t ) ) ) ) ) ( t h o r ( t h i s (known s l o p e $?1 $?s) ( t h u s e c - s l o p e 2 c - s l o p e 1 ) ) ( t h f a i l t h e o r e m ) ) ( t h a s s e r t (known l i n e $ ? 1 ) ) ( c o n s t r u c t i o n c o n s t r u c t l i n e $ ? 1 t h r u p o i n t $?a $ ? s ) ) ( t h c o n s e c - s l o p e 2 ; t h e s l o p e o f a l i n e i s known i f i t ; i n t e r s e c t s a n o t h e r known l i n e a t a known a n g l e . (1 m a s) (known s l o p e $?1 $?s) ( t h u n i g u e ' s l o p e $?1) ( t h g o a l ($?1 i n t e r s e c t s $?m a t a n g l e $?a) ( t h u s e c - i n t e r s e c t 1 ) ) ( t h i s (known a n g l e $?a) ( t h u s e c - a n g l e 2 c - a n g l e 3 ) ) ( t h i s (known l i n e $?m) ( t h u s e c - l i n e t e s t ) ) ( t h s e t g $ ? s ( " l i s t " ' a t ' a n g l e $?a ' t o ' l i n e $?m))) ( t h c o n s e c - c i r c l e 5 (c ded c i r c l e 11 r a d ( t h r e s t r i c t 12 ' ( l a m b d a (teg) ( n o t (eg ( t h v 11) t e g ) ) ) ) ) ( c o n d i t i o n - o n ( t h v c) c e n t e r c i r c l e (thv c i r c l e ) ) ( t h g o a l ( { t h v c i r c l e ) t a n g e n t ( t h v 1 1 ) ) ) ( t h c o n d ( ( t h g o a l ( ( t h v c i r c l e ) t a n g e n t ( t h v 1 2 ) ) ) ) ( ( t h g o a l {{thv c i r c l e ) t a n g e n t (t h v 12) a t " ? M ) ) ) ) ( t h c o n d { ( t h g o a l ( i n t e r s e c t i n g ( t h v 11) ( t h v 12)) ( t h u s e c - i n t e r s e c t i n g 1 c - i n t e r s e c t i n g 2 ) ) ( t h i s ( d e t e r m i n e l i n e (thv 11)) ( t h t b f t h t r u e ) ) ( t h i s ( d e t e r m i n e l i n e ( t h v 12)) ( t h t b f t h t r u e ) ) ( c o n s t r u c t i o n c e n t e r p o i n t (thv c) i s on t h e b i s e c t o r o f t h e a n g l e f o r m e d by l i n e s ( t h v 11) and ( t h v 1 2 ) ) ) ( ( t h g o a l ( p a r a l l e l ( t h v 11) ( t h v 12)) ( t h t b f t h t r u e ) ) ( t h i s ( d e t e r m i n e l i n e ( t h v 11)) ( t h t b f t h t r u e ) ) ( t h i s { d e t e r m i n e l i n e ( t h v 12)) ( t h t b f t h t r u e ) ) ( t h g o a l ( r a d i u s ( t h v c i r c l e ) ( t h v r a d ) ) ) ( t h d o ( t h a s s e r t (deduced l e n g t h ( t h v rad) ( i s one h a l f t h e s e p a r a t i o n o f t h e p a r a l l e l l i n e s ) ) ) ( t h a s s e r t (known l e n g t h ( t h v r a d ) ) ) ) ( c o n s t r u c t i o n c e n t e r p o i n t ( t h v c) i s on a l i n e p a r a l l e l t o l i n e s ( t h v 11) and ( t h v 12) midway between t h e m ) ) ) ) s,aBP^e,.. i i P S t , A n d _ P h r a s e S p e c i a l i s t s ( t h a n t e a - a l t m e d 1 ( s i d e l e n segment a b c ( t h r e s t r i c t o t onto) ( t h r e s t r i c t f a c t o r a ltmedp) ( t h r e s t r i c t t h '(lambda (th) (memq t h ' (the t h a t o n e ) ) ) ) ) ( g i v e n t h e $ ? f a c t o r $ ? o t $ ? t h $ ? s i d e ) ( t h c o n d ((memq $ ? s i d e »(base h y p o t e n u s e ) ) ( t h g o a l ( t r i a n g l e $?a $?b $ ? c ) ) ( t h s e t g $?segment (seg $?b $?c) $ ? p o i n t $?a)) ( ( e g $ ? s i d e * s i d e ) ( t h g o a l ( t r i a n g l e $?a $?b $ ? c ) ) ( t h c o n d ( ( t h g o a l (known l e n g t h ( t h e v ( s e g $?b $ ? a ) ) ) ) ( t h s e t g $?segment (seg $?b $?a) $ ? p o i n t $ ? c ) ) ( ( t h g o a l (known l e n g t h ( t h e v (seg $?a $ ? c ) ) ) ) ( t h s e t g $?segment ( t h e v (seg $?a $ ? c ) ) $ ? p o i n t $ ? b ) ) (t ( t h s e t g $?segment ( t h e v (seg $?b $ ? c ) ) $ ? p o i n t $ ? a ) ) ) ) (t ( t h e r t bad s i d e - a - a l t m e d 1 ) ) ) ( t h s e t q $ ? l e n (gensyml »len)) ( t h a s s e r t (known l e n g t h $ ? l e n ) ) ( t p r i n t l e t t h e g i v e n $ ? f a c t o r be o f l e n g t h $ ? l e n ) (or (eg $ ? f a c t o r ' a l t i t u d e ) ( t h a s s e r t (median $ ? p o i n t t o $?segment) $ t ) ) ( t h a s s e r t ( p o i n t $ ? p o i n t ( t h e v ( t l i s t c o n d i t i o n - o n $ ? p o i n t s t $ ? f a c t o r $ ? p o i n t t o (cond ( ( e g $ ? f a c t o r ' a l t i t u d e ) ( l i n e $?segment)) (t $?segment)) i s $ ? l e n } ) ) ( t h p r o p (cond ( ( e g $ ? f a c t o r ' a l t i t u d e ) 100) ( t - 1 1 0 ) ) ) ) ) ( t h a n t e a - a n y a n g l e ( ( t h r e s t r i c t a r t a r t i c l e p ) a b c) ( g i v e n $ ? a r t a n g l e ) ( t h g o a l ( t r i a n g l e $?a $?b $ ? c ) ) ( t h o r ( t h a n d ( t h a s s e r t (known a n g l e ( t h e v (ang $?a $?b $ ? c ) ) ) ) ( t p r i n t a n g l e (ang $?a $?b $?c) i s a g i v e n a n g l e ) ) ( t h a n d ( t h a s s e r t (known a n g l e ( t h e v (ang $?a $?c $ ? b ) ) ) ) ( t p r i n t a n g l e (ang $?a $?c $?b) i s a g i v e n a n g l e ) ) ( t h a n d ( t h a s s e r t (known a n g l e ( t h e v (ang $?b $?a $ ? c ) ) ) ) ( t p r i n t a n g l e (ang $?b $?a $?c) i s a g i v e n a n g l e ) ) ) ) ( t h a n t e a - i s o s 1 (a b c) ( i s o s c e l e s t r i a n g l e $?a $?b $?c) ( t h a s s e r t ( p o i n t $ ? a ( t h e v ( t l i s t c o n d i t i o n - o n $?a s t $?a e g u i d i s t a n t $?b and $ ? c ) ) ) ( t h p r o p 40)) ( t h a s s e r t ( l e n g t h ( t h e v (seg $ ? a $ ? b ) ) e q u a l l e n g t h ( t h e v (seg $?a $ ? c ) ) ) ) ) ( t h a n t e a - i s o s 2 (a b c) ( i s o s c e l e s t r i a n g l e $?a $?b $?c) ( t h a s s e r t ( a n g l e ( t h e v (ang $?a $?b $ ? c ) ) e g u a l a n g l e ( t h e v (ang $?a $?c $ ? b ) ) ) ) ) Sample LiSP-PLAHNBR H y b r i d F u n c t i o n s ( d e f u n c o n s t r u c t i o n f e x p r (cnarg) ; t h i s f u n c t i o n a d d s a new i n s t r u c t i o n t o t h e ; s o l u t i o n a l g o r i t h m a f t e r c h e c k i n g t h a t t h e ;same i n s t r u c t i o n has n o t been added p r e v i o u s l y . ; t h e i n s t r u c t i o n s may be removed by f a i l u r e ;backup i f n e c e s s a r y ( p r o g n i l ( s e t q cntemp (mapcar •(lambda (a) (cond ((atom a) a) ( t ( e v a l a ) ) ) ) c n a r g ) ) (cond ((member cntemp c o n s t r u c t i o n ) ( r e t u r n n i l ) ) (t ( s e t q t h e x p ( l i s t ' thand * ( t h s e t q c o n s t r u c t i o n (cons cntemp c o n s t r u c t i o n ) ) ( l i s t » threturn ( l i s t 'quote c n t e m p ) ) ) ) ) ) ( r e t u r n t ) )) ( s e t q cntemp n i l ) ( d e f u n l i n e e x p r c n s e g s (p r o g ( c n s e g a c n s e g b cnexp) (cond ( ( e q c n s e g s 2) ( s e t q c n s e g a ( a r g 1) c n s e g b ( a r g 2))) (t ( s e t q c n e x p ( e x p l o d e ( a r g 1)) c n s e g a ( c a r cnexp) c n s e g b ( c a d r c n e x p ) ) ) ) ( r e t u r n ( t h v a l • ( t h p r o g (1) ($g ($e c n s e g a on $?1)) ($g ($e c n s e g b on $?1)) ( t h r e t u r n $?1)) t h a l i s t ) ) ) ) ) ) ) ) ) ) ) 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051786/manifest

Comment

Related Items