Open Collections

A MACHINE INDEPENDENT IMPLEMENTATION OF LOGO by V i n c e n t S. M a n i s * B.Sc., U n i v e r s i t y Of B r i t i s h C o l u m b i a A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMEUT FOR THE DEGBEE OF MASTER OF SCIENCE i n t h e D e p a r t m e n t o f COMPUTER SCIENCE He 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 COLUMBIA O c t o b e r 1973 In presenting t h i s thesis i n p a r t i a l f ulfilment of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t freely available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department The University of B r i t i s h Columbia Vancouver 8, Canada Date 1 0 O C T O S E g 1 0 7 1 . A b s t r a c t An i m p l e m e n t a t i o n o f t h e programming l a n g u a g e Logo i s d e s c r i b e d . Logo, a programming l a n g u a g e somewhat l i k e L i s p , i s i n t e n d e d t o t e a c h t h e n a i v e u s e r t h e e l e m e n t s c f programming and p r o b l e m - s o l v i n g , e s p e c i a l l y i n s y m b o l i c programming a p p l i c a t i o n s s u c h a s g r a p h i c s , n a t u r a l l a n g u a g e p r o c e s s i n g , m u s i c a l c o m p o s i t i o n , and t h e s o l u t i o n o f e l e m e n t a r y a r t i f i c i a l i n t e l l i g e n c e p r o b l e m s . The s y s t e m d e s c r i b e d h e r e , BCLogo, i s an a t t e m p t t o b u i l d a p o r t a b l e i m p l e m e n t a t i o n which would n e t be p a r t i c u l a r l y s e n s i t i v e t o t h e computer on which i t was r u n . The t h e s i s d e s c r i b e s b o t h t h e manner i n which t h e s y s t e m a p p e a r s t o t h e u s e r and t h e way i n which t h e s y s t e m was b u i l t . A M a c h i n e I n d e p e n d e n t Locjo I m p l e m e n t a t i o n Acknowledgements D u r i n g t h e p r e p a r a t i o n o f t h i s t h e s i s , I have b e n e f i t t e d from t h e h e l p o f a number o f p e o p l e . F i r s t , my s u p e r v i s o r s , J . E . L . Peck, Raymond R e i t e r , and D.ft.R. S e e l e y , p r o v i d e d a g r e a t d e a l o f s u p p o r t ( e s p e c i a l l y moral) o v e r t h e l a s t few months. I am i n d e b t e d f o r a l a r g e number o f t h e good i d e a s h e r e t o W a l l a c e F e u r z e i g and G e o r g e L u k a s , o f B o l t , B e r a n e k , and Newman, I n c . , who s p e n t a g r e a t d e a l o f t h e i r t i m e e x p l a i n i n g why t h e o r i g i n a l BBN i m p l e m e n t a t i o n was t h e way i t was. & number o f o t h e r p e o p l e , i n c l u d i n g P e t e r VandenBosch, P a u l F r i e d m a n , Hark OuMont, and N i g u e l A l e m p a r t e , h e l p e d me t o p i n p o i n t e r r o r s i n t h e s y s t e m . The f i n a n c i a l s u p p o r t c f t h e N a t i o n a l R e s e a r c h C o u n c i l o f Canada i s g r a t e f u l l y a c k n o w l e d g e d . iv T a b l e Of C o n t e n t s P a r t 1 I n t r o d u c t i o n 1 P a r t 2 A U s e r ' s G u i d e To BCLogo ..5 2.1 I n t r o d u c t i o n 5 2.2 Logo D a t a 7 2.2.1 Words 8 2.2.2 S e n t e n c e s 8 2.2.3 L i s t s ...................9 2. 2.4 Q u o t i n g T h i n g s ......10 2.2.5 The Empty T h i n g ............11 2.2.6 Some F r i l l s .......12 2.3 The S y n t a x Of Logo .13 2.3.1 L o g o ' s S y n t a x R u l e s 13 2.3.2 Some Examples ...................................15 2.3.3 N o i s e Words And Comments . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 D e f i n i n g P r o c e d u r e s ...17 2.4.1 P r o c e d u r e s .....17 2.4.2 S i m p l e P r o c e d u r e s ...19-2.1.3 I n p u t s 20 2.4.4 O u t p u t t i n g R e s u l t s ...21 2.4.5 R e c u r s i o n 22 V 2.4.6 C o n d i t i o n s 22 2.4.7 More R e c u r s i o n 24 2.4.8 V a r i a b l e s 26 2.4.9 F r i l l s .28 2.4.10 A n o t h e r Example .......29 2.5 E d i t i n g And Workspace Management 30 2.6 Data S t r u c t u r e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.7 The Logo F u n c t i o n s 38 2.7.1 T e x t P r o c e s s i n g 38 2.7.2 P r e d i c a t e s 39 2.7.3 A r i t h m e t i c ., .39 2.7.4 F u n c t i o n s .40 2.7.5 C o n d i t i o n a l s ...41 2.7.6 I n p u t / O u t p u t .....41 2.7.7 T i m i n g 42 2.7.8 System C o n t r o l F u n c t i o n s 42 2.7.9 V a r i a b l e s ...43 2.7.10 Program M a n i p u l a t i o n F u n c t i o n s .43 2.8 A G l o s s a r y Of Logo F u n c t i o n s ....44 P a r t 3 BCPL .......52 P a r t 4 System D e s c r i p t i o n .................................57 4.1 Data S t r u c t u r e s 58 4.2 S t o r a g e Management ..................................62 4.3 The P a r s e r ..........67 4.4 The I n t e r p r e t e r . .......67 4.5 V a r i a b l e B i n d i n g 70 4.6 The P r i m i t i v e F u n c t i o n s .......71 4.7 I n i t i a l i s a t i o n 74 P a r t 5 M a c h i n e I n d e p e n d e n c e ....78 5.1 BCPL ............78 5.2 P u t t i n g B C l c g o On a n o t h e r Machine 80 5.2.1 O p e r a t i n g S y s t e m s 80 5.2.2 C h a n g i n g M a c h i n e s .81 P a r t 6 C o n c l u s i o n s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .....82 6.1 Bough S p o t s .....82 6.2 F r i e n d l i n e s s 84 6.3 F u t u r e D e v e l o p m e n t s .................................85 P a r t _1 I n t r o d u c t i o n 1 i :—'- '"• •'. ~ 1 1 I | PART 1 INTRODUCTION | 1 I I I I ; I Logo i s a l a n g u a g e d e v e l o p e d j o i n t l y by B e l t , B e r a n e k , and Newman, I n c . , and t h e A r t i f i c i a l I n t e l l i g e n c e L a b o r a t o r y a t B I T , t o a i d n o v i c e computer u s e r s i n programming c o m p u t e r s . The l a n g u a g e i s v e r y d i f f e r e n t f r o m o t h e r n a i v e u s e r s y s t e m s , s u c h as B a s i c o r APL, i n t h a t t h e l a n g u a g e i s not d e s i g n e d f o r n u m e r i c c a l c u l a t i o n s , b u t f o r s y m b o l i c p r o c e s s i n g . T y p i c a l a p p l i c a t i o n s o f t h e l a n g u a g e a r e : g r a p h i c s ( e s p e c i a l l y " t u r t l e g e o m e t r y " , a t y p e o f g e o m e t r y u s i n g o n l y t h e c o n c e p t s o f p o s i t i o n and d i r e c t i o n ) [ P A P E 7 2 ] , w o r k i n g w i t h l a b y r i n t h s [ FEUR71], e x p e r i m e n t s i n c o n t r o l t h e o r y , s u c h a s t h e p r o c e s s e s o f b a l a n c i n g a s t i c k [PAPE71 ], p o e t r y g e n e r a t i o n £ P A P E 7 1 ], and d i f f e r e n t i a l c a l c u l u s [ L U K A 7 2 ] . The l a n g u a g e has been d e s c r i b e d a s a "baby L i s p " i n t h a t i t , l i k e L i s p , employs l i s t p r o c e s s i n g , o r s y m b o l i c , t e c h n i g u e s — t h e b a s i c datum i s n e t t h e number, but t h e c h a r a c t e r s t r i n g . The l a n g u a g e e m p h a s i z e s s t r u c t u r e d programming [ D I J K 7 2 ] [ F R E E 7 2 ] , i n p a r t i c u l a r t h e u s e o f f u n c t i o n a l programming. I am p r i m a r i l y c o n c e r n e d w i t h e n c o u r a g i n g t h e use c f Logo i n s e c o n d a r y s c h o o l s . However, most s e c o n d a r y s c h o o l s c u r r e n t l y d o i n g c o m p u t i n g use a l a n g u a g e s u c h as EASIC. One o f t h e p r i m a r y r e a s o n s g i v e n f o r t h e w i d e s p r e a d use o f BASIC i s t h a t a l m o s t e v e r y computer m a n u f a c t u r e r p r o v i d e s i t — t h e same t i r e d o l d j u s t i f i c a t i o n g i v e n f o r F o r t r a n . The a v a i l a b i l i t y c f a Logo i m p l e m e n t a t i o n w h i c h c o u l d be e a s i l y a d a p t e d t o r u n on P a r t \ I n t r o d u c t i o n 2 a l a r g e number o f d i f f e r e n t c o m p u t e r s would go a l o n g way t o w a r d a n s w e r i n g t h e o b j e c t i o n o f B A S I C » s u b i q u i t y . The p u r p o s e s o f t h e work r e p o r t e d i n t h i s t h e s i s a r e a s f o l l o w s : • t o c o n s t r u c t a r e a s o n a b l y e f f i c i e n t i m p l e m e n t a t i o n o f L o g o . • t o b u i l d a s y s t e m t o which new s e t s o f p r i m i t i v e f u n c t i o n s c o u l d e a s i l y be added. T h i s f a c i l i t y w i l l p r o v i d e t e a c h e r s w i t h t h e a b i l i t y t o c o n s t r u c t m i c r o - w o r l d s f o r t h e i r s t u d e n t s t o e x p l o r e u s i n g L o g o . One example o f s u c h a m i c r c -w o r l d i s t h a t o f c o n t r o l t h e o r y : t h e t e a c h e r may i n t e r f a c e t h e Logo computer t o a p h y s i c a l d e v i c e s u c h as a t u r t l e c r a c a r t , and t h e n g i v e t h e s t u d e n t a t a s k s u c h as moving t h e t u r t l e a l o n g t h e edge o f an o b j e c t o r b a l a n c i n g a s t i c k . I t must he p o s s i b l e t o m o d i f y Logo t o s u p p o r t s u c h new d e v i c e s e a s i l y . • t o c o n s t r u c t a s y s t e m which i s g u i t e " f r i e n d l y " t o t o t h e n a i v e u s e r , i n t h a t e a c h u s e r c a n a p p r o a c h i t a t h i s own l e v e l , and t h e s y s t e m ( i n p a r t i c u l a r t h e e r r o r messages) does n o t f r i g h t e n b e g i n n e r s o f f . Many s y s t e m s p r o d u c e e r r o r messages s u c h as "ERROR NUMBER K014", o r " F I L E NOT O P E N — E D I T LINE NOT ADDED". Such messages a r e n o t c a l c u l a t e d t o i n s p i r e c o n f i d e n c e . • t o b u i l d a r e l a t i v e l y machine i n d e p e n d e n t i m p l e m e n t a t i o n . The l a s t p o i n t needs some e x p l a n a t i o n : machine i n d e p e n d e n c e i s a v e r y e l u s i v e g u a n t i t y . F o r e x ample, we c o u l d have a f o u r t h o u s a n d l i n e F o r t r a n program w r i t t e n e n t i r e l y i n P a r t J I n t r o d u c t i o n 3 ANSI F o r t r a n , p a y i n g no a t t e n t i o n t o s u c h g u e s t i c n s as word s i z e o r o p e r a t i n g s y s t e m p e c u l i a r i t i e s . Y e t i f t h e p a r t i c u l a r c o m p u t e r we happen t o be u s i n g d o e s n ' t have a F o r t r a n c o m p i l e r (many m i n i - c o m p u t e r s have e i t h e r no F o r t r a n c o m p i l e r , c r o n l y a F o r t r a n i n t e r p r e t e r ) , t h e n we a r e r e a l l y i n t r o u b l e , b e c a u s e we now must t r a n s l a t e o u r program i n t o some o t h e r l a n g u a g e ; and nobody c l a i m s t h a t F o r t r a n i s a " r e a s o n a b l e " l a n g u a g e (ANSI has n o t s e t any s t a n d a r d s on t h a t ) . The method f o r machine i n d e p e n d e n c e w h i c h I have a t t e m p t e d i s d i f f e r e n t f r o m t h e " s t a n d a r d " a p p r o a c h o f t e n u s e d : I have n o t t r i e d t o b u i l d s o m e t h i n g which would r u n i n s t a n t l y on e v e r y c o m p u t e r ; i n s t e a d , I t r i e d t o c o n s t r u c t a s y s t e m which would r u n on a number o f c o m p u t e r s , and was c l e a r l y enough e x p r e s s e d t h a t i t c o u l d be e a s i l y t r a n s l a t e d i n t o an a p p r o p r i a t e l a n g u a g e f o r o t h e r s . T h i s Logo i m p l e m e n t a t i o n i s w r i t t e n i n BCPL, a f a i r l y m a c h i n e - i n d e p e n d e n t (but e f f i c i e n t ) l a n g u a g e d e s i g n e d e s p e c i a l l y f o r c o m p i l e r w r i t i n g . The l a n g u a g e i s s u c h t h a t a l g o r i t h m s c a n be c l e a r l y e x p r e s s e d , and n o n n u m e r i c a l p r o b l e m s s u c h a s i n t e r p r e t e r d e s i g n become e x t r e m e l y s t r a i g h t f o r w a r d . The l a n g u a g e has been i m p l e m e n t e d upon a number o f d i f f e r e n t m a c h i n e s * i n c l u d i n g t h e A t l a s 2 a t C a m b r i d g e , t h e GE (now H o n e y w e l l ) 645 and TX-2 a t BIT, t h e PDP-10 a t B o l t , Beranek and Newman, and t h e IBB 360/370. N e v e r t h e l e s s , i t i s e m i n e n t l y s e n s i b l e t o assume t h a t t h e r e a r e a l a r g e number o f u s e r s who might wish t h i s s y s t e m on t h e i r machine, b u t do not have a BCPL i m p l e m e n t a t i o n . I t i s my hope t h a t t h i s s y s t e m might s e r v e as a model, i n t h a t a t l e a s t t h e d e s i g n does n o t have t o be r e a t t e m p t e d e a c h t i m e t h e s y s t e m i s moved t o a new machine. P a r t 1 I n t r o d u c t i o n I have c a l l e d t h i s Logo i m p l e m e n t a t i o n "BCLogo", w h i c h , i f you t h i n k a b o u t i t , i s a r a t h e r bad pun. I t c u r r e n t l y o p e r a t e s on t h e UBC IBM 360/67 under t h e M i c h i g a n T e r m i n a l S y s t e m . A v e r s i o n r u n n i n g w i t h i n OS/360 w i l l s h o r t l y be b u i l t . P a r t 2 A U s e r ' s G u i d e To BCLogo 5 f ' - ~ 1 , 1 " 1 • 1 •" •• • : 1 I I | PART 2 A USER'S GUIDE TO BCLOGO | I I I I I U , J { The meaning d o e s n ' t m a t t e r i f i t ' s o n l y i d l e c h a t t e r o f a t r a n s c e n d e n t a l k i n d . — W.S. G i l b e r t , P a t i e n c e } T h i s p a r t o f t h e t h e s i s i s a u s e r ' s manual f o r t h e c u r r e n t s y s t e m ; i t d e s c r i b e s t h e f a c i l i t i e s a v a i l a b l e t o t h e Logo programmer, and t h e Logo e n v i r o n m e n t . l i l I n t r o d u c t i o n Logo i s b o t h a f o r m a l n o t a t i o n f o r d e s c r i b i n g a l g o r i t h m s and a p r a c t i c a l s y s t e m f o r programming c o m p u t e r s . The f a c t t h a t i t i s d e s i g n e d t o work w i t h s y m b o l s r a t h e r t h a n n u m e r i c v a l u e s i s t h e p r i m e f a c t o r which d i s t i n g u i s h e s i t from l a n g u a g e s s u c h a s B a s i c and F o r t r a n . Many p e o p l e a l s o f i n d t h a t a l g o r i t h m s programmed i n Logo a r e e a s i e r t o r e a d and u n d e r s t a n d t h a n t h e same a l g o r i t h m s programmed i n B a s i c . T h i s manual a t t e m p t s t o d e s c r i b e Logo from a somewhat e l e m e n t a r y v i e w p o i n t . I f you u n d e r s t a n d l a n g u a g e s s u c h as L i s p o r APL you s h o u l d n ' t have t o o much t r o u b l e w i t h L e g o . However, i f y o u r o n l y e x p o s u r e t o c o m p u t e r s has been w i t h B a s i c c r F o r t r a n , you may have some t r o u b l e . In t h i s c a s e , p l e a s e b e a r w i t h me, and t r y n o t t o l e t y o u r p r e v i o u s programming e x p e r i e n c e i n t e r f e r e w i t h y o u r l e a r n i n g o f a v e r y d i f f e r e n t P a r t 2 a D s e r j s G u i d e To BCLogo 6 l a n g u a g e . I n o r d e r t o l e a r n a computer l a n g u a g e , you must s t u d y two a s p e c t s o f t h e l a n g u a g e : t h e s y n t a x — t h e r u l e s r e g a r d i n g which p r o g r a m s a r e g r a m m a t i c a l l y c o r r e c t , and t h e s e m a n t i c s — t h e d e s c r i p t i o n o f what a program d o e s . One f e a t u r e o f Lego i s t h a t t h e s y n t a x has a v e r y s u b o r d i n a t e r o l e — t h e r e a r e v e r y few s y n t a x r u l e s t o l e a r n . C o r r e s p o n d i n g l y , t h e p r i m a r y e f f o r t you w i l l have t o make l i e s i n l e a r n i n g what t h e v a r i o u s f e a t u r e s o f Logo do, r a t h e r t h a n how you w r i t e them down. Many programming manuals s t a r t o f f w i t h a s e c t i o n on n o t a t i o n ; t h i s one i s no d i f f e r e n t . P l e a s e remember t h e f o l l o w i n g r u l e when r e a d i n g t h e e x a m p l e s : t h e u s e r ' s i n p u t t o t h e computer i s u n d e r l i n e d ; t h e c o m p u t e r ' s r e s p o n s e s a r e n o t . N o r m a l l y , L o g o o p e r a t e s i n d i r e c t e x e c u t i o n mode. T h i s pompous p h r a s e means t h a t as you t y p e a l i n e i n t o Logo, Logo o b e y s y o u r command, r a t h e r t h a n s t o r i n g i t away f o r l a t e r r e f e r e n c e . l o u s h o u l d t h i n k o f Logo a s a v e r y f a s t , b u t n o t v e r y s m a r t , f r i e n d who i s l i s t e n i n g t o what you s a y , and a t t e m p t i n g t o c a r r y o u t y o u r r e g u e s t s t o t h e b e s t o f i t s a b i l i t i e s . Bowever, Logo a l w a y s s e e s t h i n g s from i t s p o i n t o f v i e w ; t h e r e f o r e , i t w i l l a l w a y s do what you s a y , n o t what you mean. P a r t 2 A U s e r ' s G u i d e To BCLogo 7 2-.2 Logo D a t a { The Boman C o n q u e s t was, however, a Good T h i n g . — S e l l a r And Yeatman, 1066 And A l l T h a t } One o f t h e most i m p o r t a n t c o n s t r a i n t s upon any programming l a n g u a g e i s t h e c h o i c e o f d a t a t y p e t h a t may be m a n i p u l a t e d . F o r example, F o r t r a n i s v e r y good a t m a n i p u l a t i n g numbers, and c o r r e s p o n d i n g l y p o o r a t p r o c e s s i n g t e x t u a l m a t e r i a l * Logo e x c e l s a t p r o c e s s i n g t e x t , and i s n o t p a r t i c u l a r l y s u i t e d t o n u m e r i c c a l c u l a t i o n . N o n e t h e l e s s , f o r a r e a s o n a b l y s m a l l c a l c u l a t i o n ( f o r example, any program w r i t t e n by a h i g h - s c h o o l s t u d e n t i n B a s i c ) , Logo w i l l work q u i t e w e l l . * one i n t e r e s t i n g c o n s e q u e n c e o f F o r t r a n ' s r i s e t o dominance i n t h e c o m p u t i n g w o r l d i s t h a t t h e r e i s a b r e e d o f F o r t r a n programmers who a r e good a t t e x t p r o c e s s i n g ; t h e y w r i t e s u b r o u t i n e s f o r a l l t h e o t h e r F o r t r a n programmers, who r e g a r d e v e n t h e s i m p l e s t p r o c e s s i n g o f c h a r a c t e r t e x t as a m y s t e r i o u s e x p e r i e n c e t o be a v o i d e d w h erever p o s s i b l e . P a r t 2 A u s e r ' s G u i d e To BCJLgcjo 8 IAZS.1 Words { I n t h e B e g i n n i n g was t h e Word — The G o s p e l A c c o r d i n g To John } The b a s i c o b j e c t w i t h which Logo d e a l s i s t h e word. A word i s a n ; s t r i n g o f l e t t e r s and d i g i t s . As e x a m p l e s , c o n s i d e r EGGPLANT, 1000X, THIS.IS.A.LONG.WORD....., and 45. A word c a n have a s few a s one and a s many as 255 c h a r a c t e r s i n i t . 2.2.2 S e n t e n c e s Once you have c r e a t e d a s e t o f words, you w i l l p r o b a b l y want t o t e l l some s o r t o f s t o r y . I n E n g l i s h , we combine words i n t o s e n t e n c e s ; Logo does t h e same: a Lego s e n t e n c e i s s i m p l y a s e g u e n c e o f words s e p a r a t e d by b l a n k s . F o r example, THE EGGPLANT ATE THE AARDVARK 1 AND BOT I! 4 D9NUBT6L GJBDJD a r e s e n t e n c e s . You s h o u l d n o t i c e t h a t we d o n ' t end Logo s e n t e n c e s w i t h p e r i o d s . P a i l 2 h D s e r ' s G u i d e To B C L 0 3 0 9 2.2.3 l i s t s Be c a n g e t even more e x t r a v a g a n t , by j o i n i n g s e n t e n c e s t o g e t h e r . F o r example, we c o u l d have a t h i n g made by j o i n i n g t h r e e o t h e r t h i n g s t o g e t h e r : t h e f i r s t and t h i r d e l e m e n t s c o u l d be s e n t e n c e s and t h e s e c o n d a word. We c a l l any t h i n g made by j o i n i n g words o r s e n t e n c e s t o g e t h e r a l i s t . (What r e l a t i o n do s e n t e n c e s b e a r t o l i s t s ? ) L i s t s p r o v i d e you w i t h a g r e a t d e a l o f p o w e r — y o u c a n c r e a t e e x t r e m e l y complex t h i n g s w i t h l i s t s f o r example, you c a n s t o r e a m a t r i x a s a l i s t — a m a t r i x c an be v i e w e d a s a l i s t e a c h o f whose e l e m e n t s i s a s e n t e n c e . The m a t r i x r t I 1 4 ft I I 2 5 B | I 3 6 C | t J H i g h t be r e p r e s e n t e d a s [ [1 4 a] [2 5 B] [3 6 C] ] o r a s [ [1 2 3] [4 5 6] [ A B C ] ] d e p e n d i n g on whether we a r e p r i m a r i l y i n t e r e s t e d i n rows c r c o l u m n s . L e s t a l l t h i s power r u n t o y o u r head, I must p o i n t o u t t h a t f o r r e a s o n a b l e p r o b l e m s no g r e a t u t i l i t y has been f o u n d f o r l i s t s which a r e n o t s e n t e n c e s ( t h e r e a r e o t h e r P a r t 2 A U s e r ' s G u i d e To B C L 0 3 0 10 methods o f c r e a t i n g c o m p l i c a t e d o b j e c t s which a r e e a s i e r t o u n d e r s t a n d and d e b u g ) , and, t h e r e f o r e , you s h o u l d p r o b a b l y s t a y w i t h words and s e n t e n c e s . 2.2.U Q u o t i n g T h i n g s { Ah y e s ! I w rote t h e " P u r p l e Cow"— I*m s o r r y now I wrote i t ! B u t I c a n t e l l you anyhow 1*11 k i l l you i f you g u o t e i t ! — F.G. B u r g e s s , C i n g Ans A p r e s } So f a r , we have o n l y d i s c u s s e d t h e k i n d s o f a b s t r a c t t h i n g s you c a n use when w o r k i n g w i t h L o g o . S i n c e Logo i s n o t o n l y a f o r m a l n o t a t i o n , but a l s o a computer l a n g u a g e , you must have some means f o r d e s c r i b i n g Logo t h i n g s t o y o u r c o m p u t e r — y o u must be a b l e t o g u o t e a t h i n g t o t h e c o m p u t e r . You may use a number o f c o n v e n t i o n s f o r s p e c i f y i n g t h e d a t a : • s u r r o u n d a word w i t h g u o t e s : "HELLO" "100051" "4" a s u r r o u n d a s e n t e n c e w i t h g u o t e s : "A MESS OF POTTAGE" • s u r r o u n d a l i s t w i t h b r a c k e t s 1 : £ HE ATE [THE L A S T ] EARTHWORM ] As a s p e c i a l c o n c e s s i o n t o o u r h i s t o r i c a l c o n v e n t i o n s , you c a n e n t e r a word composed e n t i r e l y o f d i g i t s w i t h o u t t h e s u r r o u n d i n g g u o t e s . L o g o w i l l assume t h a t t h e g u o t e s were 1 i t i s p o s s i b l e f o r y o u r s y s t e m programmer t o c r e a t e a v e r s i o n o f t h e Logo p r o c e s s o r which u s e s o t h e r c h a r a c t e r s i n p l a c e o f t h e b r a c k e t s . I f you a r e u s i n g s u c h a v e r s i o n c f t h e s y s t e m , p l e a s e ( m e n t a l l y ) s u b s t i t u t e t h e c h o s e n c h a r a c t e r s f o r t h e b r a c k e t s t h r o u g h o u t t h i s manual. P a r t 2 A U s e r ' s G u i d e To BCLogo 11 p r e s e n t — t h u s i t w i l l t r e a t US and nU5n i d e n t i c a l l y . S i n c e t h i s f e a t u r e o n l y a p p l i e s t o numbers, i t c a n l e a d t o some c o n f u s i o n — a t l e a s t when you a r e l e a r n i n g l o g o . T h e r e f o r e , I would recommend t h a t you a v o i d t h i s f e a t u r e , and a l w a y s use q u o t e s t o s u r r o u n d words. 2,2,5 The Empty T h i n g { He f i n d s i t empty, swept, and put i n o r d e r — The G o s p e l A c c o r d i n g To Hatthew } One o f t h e more amusing t h i n g s a b o u t Logo i s t h e empty t h i n g . T h i s u n i q u e c r e a t u r e i s n e i t h e r word n o r s e n t e n c e ( n c r l i s t ) . I t p l a y s t h e r o l e i n Logo t h a t z e r o p l a y s i n a r i t h m e t i c . To make a j o k e , t h e empty t h i n g i s w r i t t e n as f o l l o w s : b u t , when t a l k i n g a b o u t i t t o L o g o , we s u r r o u n d i t w i t h q u o t a t i o n marks: n n Empty i s a g r e a t d e a l o f f u n : i t i s an o b j e c t which i s n ' t t h e r e — w h e n you combine empty w i t h a n o t h e r o b j e c t , you end up w i t h t h e o r i g i n a l one. I f you were t o r e p e a t e d l y remove P a r t 2 A U s e r ' s G u i d e To BCLogo 12 s o m e t h i n g from some word, s e n t e n c e , o r l i s t , you would e v e n t u a l l y end up w i t h empty. F i n a l l y , n o t e t h a t e v e r y Logo t h i n g has an i n f i n i t e s u p p l y o f e m p t i e s h i d d e n i n i t , j u s t as e v e r y number has an i n f i n i t e s u p p l y o f z e r o e s h i d d e n w i t h i n i t . 2.2.6 Some F r i l l s When you q u o t e a Logo t h i n g t o the co m p u t e r , e x c e s s b l a n k s w i l l be i g n o r e d . F o r example, " A B C " i s e q u i v a l e n t t o "A B C", and " " i s e q u i v a l e n t t o "" I f you r e a l l y want t o e n t e r a b l a n k a s a l i t e r a l c h a r a c t e r , you must t y p e a s h a r p (#). T h u s , "FLEE,#HB#CRIED n i s one s i n g l e word, not a s e n t e n c e , which c o n t a i n s s h a r p s , n e t b l a n k s . N o n e t h e l e s s , i t w i l l p r i n t o u t a s F L E E / HE CRIED Note t h a t "A###B" i s n o t e q u i v a l e n t t o «A # B " . P a r t 2 A U s e r ' s G u i d e To BCLogo 13 2.3 The S y n t a x Of Logo 2.. 3.^ L o g o ' s S y n t a x R u l e s E v e r y l a n g u a g e has a s e t o f r u l e s which d e f i n e t h o s e t h i n g s t h a t a r e v a l i d i n t h a t p a r t i c u l a r l a n g u a g e . Logo i s no e x c e p t i o n — y o u must f o l l o w L o g o ' s r u l e s v e r y c a r e f u l l y , c r Logo w i l l n o t do what you want. The s y n t a x o f a l a n g u a g e i s s i m p l y t h e s e t o f r u l e s which d e f i n e t h e t h i n g s you c a n s a y i n t h a t l a n g u a g e . To u n d e r s t a n d L o g o ' s s y n t a x , we must r e c a l l t h a t a c o m p u t e r l a n g u a g e d e s c r i b e s e s s e n t i a l l y two d i f f e r e n t k i n d s o f t h i n g s : t h e d a t a t o be o p e r a t e d upon, and t h e o p e r a t i o n s t o be a p p l i e d t o t h e d a t a . Note t h a t t h e s e a s p e c t s a r e i n t e r d e p e n d e n t — * i t makes a s l i t t l e s e n s e t o t e l l t h e computer what t o do ( w h i l e n e g l e c t i n g t o i n f o r m i t o f what d a t a a r e t o be used) a s i t d o e s t o m e r e l y g i v e t h e computer some d a t a , w i t h no i n s t r u c t i o n s as t o what n e e d s t o be done. The Logo s y n t a x i s e x t r e m e l y s i m p l e : a l m o s t e v e r y i n s t r u c t i o n i s o f t h e f o r m : < o p e r a t i o n > <datum 1> <datum 2> ... <datum n> In o t h e r words, t h e a c t i o n t o be p e r f o r m e d a l w a y s p r e c e d e s t h e l i s t i n g o f t h e d a t a t o be u s e d . W h i l e t h a t i s n o t g u i t e a l l o f P a r t 2 a U s e r ' s G u i d e To BCLogo 14 t h e s y n t a x o f Logo, i t w i l l h e l p you w i t h most o f t h e i n s t r u c t i o n s you might want t o w r i t e . A t t h i s p o i n t , we must examine t h e k i n d s o f i n s t r u c t i o n s one m i g h t w r i t e . One k i n d i s t h e command, which i s an o r d e r t o do s o m e t h i n g ("Open y o u r book t o page 57."). C o n t r a s t t h i s w i t h an o p e r a t i o n , w h i c h a n s w e r s a g u e s t i o n ("when d i d t h e Venomous Bead l i v e , and what d i d he w r i t e ? " ) . The e s s e n t i a l d i f f e r e n c e i s t h a t w h i l e t h e r e s u l t o f a command i s some a c t i o n , t h e r e s u l t o f an o p e r a t i o n i s i t s e l f some s o r t c f datum. T h i s means t h a t an i n p u t t o an o p e r a t i o n (one o f t h e d a t a l i s t e d a f t e r t h e name o f t h e o p e r a t i o n ) c o u l d i t s e l f be t h e o u t p u t , o r r e s u l t , o f a n o t h e r o p e r a t i o n . The same phenomenon o c c u r s i n E n g l i s h ("Who wrote ' U t o p i a ' ? " ; "How was t h e p e r s o n who w rote ' U t o p i a * e x e c u t e d ? " ) ; t h e r e f o r e , i t s h o u l d h a r d l y be s u r p r i s i n g t o you i n L ogo. S u d d e n l y t h e Logo i n s t r u c t i o n s become more i n t e r e s t i n g — you c a n c r e a t e v e r y e x t r a v a g a n t commands which c a u s e l a r g e numbers o f o p e r a t i o n s t o be e x e c u t e d . N e v e r t h e l e s s , t h e s y n t a x r u l e s a r e v e r y s i m p l e i n d e e d : • f o r b o t h o p e r a t i o n s and commands, t h e i n s t r u c t i o n i s w r i t t e n w i t h t h e name o f t h e d e s i r e d a c t i o n , f o l l o w e d by t h e d a t a t h a t t h e a c t i o n n e e d s . • t h e i n p u t t o an o p e r a t i o n o r command may i t s e l f be t h e o u t p u t o f a n o t h e r o p e r a t i o n (remember, commands d o n ' t o u t p u t ) . « a s t a t e m e n t (a c o m p l e t e i n s t r u c t i o n t o Logo) must a l w a y s be a command. P a r t 2 A U s e r ' s G u i d e To BCLogo 15 2.3.2 Some Examples At t h i s p o i n t , l e t ' s l o o k a t some e x a m p l e s ; but f i r s t , we need some a c t i o n s t o t a l k a b o u t . • PRINT x i s a command which c a u s e s i t s i n p u t t o be t y p e d on t h e u s e r ' s c o n s o l e . • SUM x y o u t p u t s t h e sum o f t h e two numbers 'x* and »y'. « WORD x y o u t p u t s a word composed o f t h e c h a r a c t e r s c f 'x' f o l l o w e d i m m e d i a t e l y by t h o s e o f 'y'. a IGNORE x i s a command which t a k e s i t s i n p u t and does a b s o l u t e l y n o t h i n g w i t h i t . PRINT "HELLO" c a u s e s HELLO t o be t y p e d on t h e u s e r ' s c o n s o l e . PRINT SUM " 1 " "2" c a u s e s 3 t o be t y p e d on t h e u s e r ' s t e r m i n a l . PRINT SUM " 4 " SUM " 5 " WORD " 6 " " 7 " t y p e s o u t 76 . IGNORE SUM " 1 " "2" c a u s e s 3 t o be computed, and a b s o l u t e l y n o t h i n g done w i t h t h e r e s u l t . N o t h i n g i s t y p e d o u t . SUM " 1 " "2" c a u s e s Logo t o c o m p l a i n "IOU DIDN'T TELL ME WHAT TO DO WITH 3." P a r t 2 A U s e r ' s G u i d e To BCLocjo 16 2..3..3 N o i s e Words And Comments Logo a l l o w s you t o i n s e r t " n o i s e words" i n t o y o u r commands i n o r d e r t o h e l p c l a r i f y t h e i r meaning. T h e s e words a r e i g n o r e d by Lo g o , and may be i n s e r t e d o r l e f t o u t , a s you w i s h . The n o i s e words p e r m i t t e d a r e : • OF may be i n s e r t e d between a f u n c t i o n name and i t s i n p u t s . F o r example: PRINT SUM OF 21 11 • AND may be i n s e r t e d between two i n p u t s o f a f u n c t i o n : PRINT SUM ^V! M S ^ 2 ^ PRINT SUM OF *±VL MJ2 SUM OF ^ 2 ^ AND " 3 " I n a d d i t i o n , you may s u r r o u n d an i n p u t w i t h p a r e n t h e s e s , i n o r d e r t o r e m i n d y o u r s e l f t h a t i t i s one i n p u t . F o r example: PRINT JSUM OF AND PRINT JSUM OF JflHl AND JSUM OF £21 AND Note t h a t PRINT SUM OF S'll- M S . " ? " ) . I s i n v a l i d , s i n c e t h e p a r e n t h e s e s do n o t s u r r o u n d a s i n g l e i n p u t . I t i s sometimes c o n v e n i e n t t o a n n o t a t e y o u r commands. Ycu may p l a c e a comment (to y o u r s e l f ) i n any command by s u r r o u n d i n g i t w i t h s e m i c o l o n s . I f t h e comment i s t h e l a s t P a r t 2 A O s e r j s G u i d e To B C L 0 3 0 17 t h i n g on t h e l i n e , t h e t r a i l i n g s e m i c o l o n may be e l i d e d . PI 1!! i l S l l S2J5 QI J.INPUTSJ. »V± AND PRINT WORD of /nil M S " I " i § H O U L B ~ P R I N T "AB". 2.4 D e f i n i n g P r o c e d u r g g i i l i i P r o c e d u r e s I f a l l t h a t l o g o a l l o w e d you t o do were t o use t h e p r o c e d u r e s which t h e d e s i g n e r s o f t h e l a n g u a g e saw f i t t o i n c l u d e , t h e n i t w o u l d n ' t be much good. The c h i e f v i r t u e o f Lo g o , i n f a c t , i s t h a t i t p e r m i t s you t o make new p r o c e d u r e s t o f i t y o u r n e e d s . To t a k e one o f G e r a l d W e i n b e r g ' s examples [WEIN71], you c a n n o t e x p e c t y o u r l a n g u a g e t o have a c a n n e d p r o c e d u r e f o r g e n e r a t i n g B u d d h i s t p r a y e r s , o r e v e n f o r g e n e r a t i n g p r a y e r s f o r any d e n o m i n a t i o n ( f o r e x a m p l e , PRAY 143 "HALACANERIAN"). However, i f t h e l a n g u a g e a l l o w s you t o w r i t e a PRAY p r o c e d u r e , and t h e n u s e i t i n s u c h a way t h a t you d o n ' t have t o worry whether i t ' s b u i l t - i n o r n o t , t h e n you c a n r e g a r d PRAY as b u i l t - i n . P u t a n o t h e r way, Logo by i t s e l f p r o v i d e s you w i t h a b a t t e r y o f r e s o u r c e s ; i f none o f t h e r e s o u r c e s e x a c t l y s u i t s y o u r n e e d s , you can e a s i l y c r e a t e one which d o e s . Then, y c u would have y o u r own v e r s i o n o f Logo, which had a l l o f t h e f e a t u r e s o f Log o , p l u s t h e one e x t r a f u n c t i o n you need t o s o l v e y o u r p r o b l e m . P a r t 2 a U s e r ' s G u i d e To BCLogo 18 T h i s v i e w p o i n t i s i n s h a r p d i s t i n c t i o n from t h a t o f , s a y , B a s i c , i n which t h e e m p h a s i s i s on w r i t i n g a p r o b l e m t o do s o m e t h i n g , and you n e v e r name t h e components o f t h e program a c c o r d i n g t o what t h e y do. The b a s i c t h i n g s you must do when d e f i n i n g a p r o c e d u r e a r e • t h i n k up a name t h a t i s v e r y d e s c r i p t i v e o f t h e p r o c e d u r e . I f you do t h i s f i r s t , you may s a v e y o u r s e l f a l o t o f t r o u b l e l a t e r on, i n t h a t now a t l e a s t you have some s o r t o f i d e n t i f i c a t i o n f o r t h e p r o b l e m you a r e t r y i n g t o s o l v e . • d e c i d e on what i n p u t s t h e p r o c e d u r e i s t o have, and whether t h e p r o c e d u r e i s t o be a command o r an c p e r a t i c n . I f i t ' s t o be an o p e r a t i o n , d e c i d e what t h e o u t p u t i s t o be. at t h i s p o i n t , you have d e f i n e d a " b l a c k box": an o b j e c t which has c l e a r l y d e f i n e d b e h a v i o r (on g i v e n i n p u t s a, B, and C, t h e r e s u l t i s D); you a l s o have a name f o r t h e box, which h e l p s you when t a l k i n g a b o u t t h e f u n c t i o n t o o t h e r s . • d e c i d e upon t h e a l g o r i t h m t o lie u s e d . P a r t 2 A U s e r ' s G u i d e To B C l o g g 19 2_.4_.2 S i m p l e P r o c e d u r e s L e t us t a k e a v e r y s i m p l e c a s e : we want a p r o c e d u r e which p r i n t s o u t "HELLO MORTIMER". We c a n d e f i n e t h i s p r o c e d u r e as f o l l o w s : TO GREETMORTIMER l l l l I N T ".HELLO MORTIMER" END N o t i c e s e v e r a l t h i n g s : f i r s t , we t y p e d i n a " t i t l e l i n e " , c o n s i s t i n g o f t h e word •TO* f o l l o w e d by s o m e t h i n g which i s h i g h l y u n l i k e l y t o be a l r e a d y d e f i n e d i n Logo. At t h i s p o i n t t h e c o m p u t e r i s p r e p a r e d n o t o n l y t o honour commands which a r e t y p e d i n ; i t a l s o a l l o w s you t o t y p e i n l i n e s b e g i n n i n g w i t h a number. I f you t y p e s u c h a l i n e , you w i l l o b s e r v e no immediate r e s u l t . The computer w i l l m e r e l y s t o r e y o u r l i n e away, n o t i n g t h a t i t i s l i n e 10 ( i n t h i s c a s e ) o f t h e f u n c t i o n you a r e c u r r e n t l y w o r k i n g w i t h . You c a n t y p e as many l i n e s a s you l i k e i n t o a f u n c t i o n ; t h i s example j u s t has one l i n e (note t h a t i f you e v e r have a f u n c t i o n l o n g e r t h a n a b o u t 15 l i n e s , you w i l l p r o b a b l y f i n d i t b o t h u n r e a d a b l e and u n d e b u g g a b l e ) . The command END c a u s e s Logo t o n o t e t h a t you have f i n i s h e d e d i t i n g t h e c u r r e n t f u n c t i o n ; i t w i l l r e s p o n d w i t h GREETMORTIMER DEFINED. Now you a r e i n a p o s i t i o n t o t r y o u t y o u r new p r o c e d u r e : GREETMORTIHER HELLO MORTIMER GREETMORTIMER HELLO MORTIMER 2.4.3 i n p u t s A f t e r y o u have r u n GREETMORTIHER a few t h o u s a n d t i m e s t h e f u n w i l l b e g i n t o p a l l . What we would r e a l l y l i k e i s a f u n c t i o n which w i l l g r e e t anybody a t a l l . L e t ' s l o o k a t t h i s o ne: TO GREET ^PERSON: 10 PRINT SENTENCE "HELLO" :PERSON: END GREET "ELMER" HELLO ELMER GREET ?FERDY" HELLO FERDI The d i f f e r e n c e h e r e i s i n t h e t i t l e l i n e . Note t h a t we have p l a c e d t h e word PERSON a f t e r t h e name o f t h e p r o c e d u r e . By e n c l o s i n g PERSON i n c o l o n s , we a r e i n d i c a t i n g t o Logo t h a t PERSON i s a p l a c e h o l d e r , s t a n d i n g f o r any i n p u t we c a r e t o hand t o GREET, ( i n c i d e n t a l l y , •:PERSOH:' i s p r o n o u n c e d " d o t s PERSON" by Logo c o g n o s c e n t i ) . You may d e f i n e a p r o c e d u r e w i t h a s many i n p u t s as you want; f o r example TO GBDMBLJ : WHY: :HOWMANY: JO PRINT 2£ ftJ3 SO ONHAPPY" 20 PRINT SENTENCE "BECAUSE" :WHY: 30 PRINT WORD :HOWMANY: WORD :BOWMANY: :HOWMANY: END GROMBLE " I LOST MY KIWI]I "GREEN^ I AM SO UNHAPPY BECAUSE I LOST MY KIWI GREENGREENGREEN GRUMBLE "WOLVES ATE MY PTARMIGAN" "HA',' I AM SO UNHAPPY ~ BECAUSE WOLVES ATE MY PTARMIGAN HAHAHA 2.U.U O u t p u t t i n g R e s u l t s You can make a procedure behave as an o p e r a t i o n by using the OUTPUT command. For example: TO T R I P L E JX: J O O U T P U T WORD Zlz AND WORD j X j . M S j X j 20 P R I N T •'HELLO^ I A M ~ T R I 1 L E " END P R I N T T R I P L E "ORK" ORKORKORK OUTPUT causes i t s i n p u t to be retur n e d as the value of the procedure from which i t was c a l l e d . Execution then s t o p s . T h e r e f o r e l i n e 20 of TRIPLE had no e f f e c t — l i n e 10 was the l a s t to be executed. P a r t 2 A U s e r ' s G u i d e To BCLogo 22 2.4.5 R e c u r s i o n The p r o c e d u r e s we have l o o k e d a t so f a r d o n ' t do v e r y much. What we want i s a mechanism f o r r e p e a t i n g a p r o c e d u r e o v e r and o v e r a g a i n . T h i s way, we d o n ' t have t o w r i t e a l o n g l i s t o f t h i n g s f o r t h e computer t o do; i n s t e a d , once we have t o l d Logo how t o do s o m e t h i n g , we can have Logo r e p e a t t h a t a c t i o n a s many t i m e s a s we want, one mechanism we can use i s c a l l e d r e c u r s i o n . I t c o n s i s t s o f h a v i n g a p r o c e d u r e which c a l l s i t s e l f . C o n s i d e r TO CACKLE JO PRINT ILPf 20 CACKLE I N D T h i s p r o c e d u r e e x e c u t e s l i n e 10, t h u s p r i n t i n g o u t HA. Next i t e x e c u t e s l i n e 20, which r e g u e s t s a n o t h e r CACKLE., So i t does i t . L i n e 10 p r i n t s o u t HA, and t h e n l i n e 20 r e g u e s t s a n o t h e r CACKLE. So i t d o e s : l i n e 10, l i n e 10, l i n e 10, ... 2.4.6 C o n d i t i o n s Now t h a t we have c r e a t e d a maniac computer which i s g i b b e r i n g "HA HA HA ...*», we want t o b r i n g i t u n d e r c o n t r o l . One way i s o b v i o u s l y t o p r e s s t h e i n t e r r r u p t b u t t o n ; however, t h i s s o l u t i o n l a c k s a c e r t a i n amount o f e l e g a n c e (we c a n c a l l t h i s t h e a d - h o c , s o l u t i o n ) . A n o t h e r method i s t o i n c l u d e w i t h i n t h e program a command t o s t o p when i t has c h o r t l e d e n ough. In o t h e r words, t h e computer must make a d e c i s i o n . P a r t 2 A U s e r * s G u i d e To B C L 0 3 0 23 What k i n d o f d e c i s i o n c a n a computer make? I t can c h e c k t o s e e whether a number i s z e r o , whether a word i s empty, c r whether one word i s e g u a l t o a n o t h e r . ( T h e r e a r e a l a r g e number o f o t h e r d e c i s i o n s which c a n be made, but t h e s e a r e enough f o r t h e moment). A l l o f t h e s e d e c i s i o n s y i e l d an o u t p u t o f e i t h e r TRUE o r F A L S E — b e c a u s e o f t h i s , t h e y a r e known a s p r e d i c a t e s . A p r e d i c a t e i s any o p e r a t i o n which a l w a y s o u t p u t s e i t h e r TRDE o r FALSE. F o r example, t h e Logo o p e r a t i o n IS i s a p r e d i c a t e which t a k e s two i n p u t s , e a c h o f which i s any Logo t h i n g . I t o u t p u t s TBUE i f t h e two i n p u t s a r e e g u a l , and FALSE o t h e r w i s e . T h e r e f o r e , IS "ABC DEF" "ABC DEF" i s TRUE, whereas IS "ABB CEF" "ABC DEF" i s FALSE. I f we were t o f e e d t h e o u t p u t o f IS a s an i n p u t t o PRINT, we would know whether t h e two i n p u t s were e g u a l o r n o t . However, t h e whole p o i n t o f p r e d i c a t e s i s t o have t h e computer make t h e d e c i s i o n . T h e r e f o r e , we u s e TEST, which i s a command which t a k e s as i n p u t a t r u t h v a l u e — T R U E o r FALSE. TEST d o e s n ' t a p p e a r t o do v e r y m u c h — i t s i m p l y s t o r e s i t s i n p u t away i n a s p e c i a l l o c a t i o n c a l l e d t h e t r u t h f l a g . We c a n t h e n use a number c f o t h e r commands t o i n t e r r o g a t e t h e t r u t h f l a g . F o r example, c o n s i d e r t h e f o l l o w i n g s e g u e n c e : TEST IS ''APPLE? "ORANGE? IFTRUE PRINT "RASPBERRY" I F F A L S E PRINT "PEACH" PEACH TEST IS "APPLE" "APPLE" IFTRUE PRINT "PEAR" PEAR I F F A L S E PRINT "CHERRY" The p r i m a r y use o f TEST i s i n p r o c e d u r e s . F o r example. T O L O O K A T rgORD: J O T E S T " I S :WORD: " S T O P " 20 I F T R D E P R I N T « O K ^ 30 T E S T I s ' T w p B p T ' y G O " 40 I F T R D E P R I N T ? B I G H T ! ' J I I I F | A L S E P R I N T !!NOJ!jj2 E N D LOOKAT " S T O P " OK L O O K A T gGQ" R I G H T ! L O O K A T " P S I T T A C O S I S " N O l l ! 2.4.7 More R e c u r s i o n Now we can l o o k a t some r e a l e x a m p les o f r e c u r s i o n . Our f i r s t example i s a p r o c e d u r e c a l l e d GIGGLE, which t a k e s a p a r a m e t e r w h i c h i n d i c a t e s how many t i m e s t o l a u g h . TO GIGGLE IXl JO TEST IS TlSz 0 20 I F F A L S E PRINT 30 I F F A L S E GIGGLE DIFFERENCE i N : J END GIGGLE DEFINED. GIGGLE 5 HA HA HA HA HA GIGGLE'S f i r s t s t e p i s t o s e whether i t has done enough. I f s o , t h e r e m a i n d e r o f t h e p r o c e d u r e i s b y p a s s e d by t h e I F F A L S E s . O t h e r w i s e , we do some work, and t h e n c a l l GIGGLE a g a i n w i t h an i n p u t w h i c h i s 1 l e s s t h a n i t was the p r e v i o u s P a r t 2 A U s e r ' s G u i d e To fiCLoc[o 25 We c a n use t h e T8ACE f u n c t i o n t o s e e what GIGGLE i s d o i n g . TRACE GIGGLE GIGGLJjf 3 GIGGLE OF " 3 " HA GIGGLE OF "2" HA GIGGLE OF " 1 " HA GIGGLE OF "0" GIGGLE STOPS GIGGLE STOPS GIGGLE STOPS GIGGLE STOPS F o r a s e c o n d example, c o n s i d e r a p r o c e d u r e which r e v e r s e s a word: 19 R E V E R S E zUz 10 T E S T * I S J.HT »" 20 I F T R U E ^ O U T P U T 212 30 O U T P U T WORD R E V E R S E ( B U T F I R S T lWz± F I R S T Ztiz E N D R E V E R S E D E F I N E D . T R A C E R E V E R S E P R I N T R E V E R S E " M I H S Y " R E V E R S E O F " H I H S Y " R E V E R S E O F " I M S Y " R E V E R S E O F " M S Y " R E V E R S E O F " S I " R E V E R S E O F " Y " R E V E R S E O F " " R E V E R S E O U T P U T S " " R E V E R S E O U T P U T S »I« R E V E R S E O U T P U T S "5S" R E V E R S E O U T P U T S " X S H " R E V E R S E O U T P U T S " I S H I " R E V E R S E O U T P U T S " Y S M I M " Y S H I H FIRST o u t p u t s t h e f i r s t e l e m e n t o f i t s i n p u t ; BUTFIRST o u t p u t s a l l b u t t h e f i r s t e l e m e n t o f i t s i n p u t . T h u s , f o r example, FIRST "HELLO" i s "H", w h i l e BUTFIRST "HELLO" o u t p u t s P a r t 2 A u s e r ' s G u i d e To BCLogo 26 "ELLO". 2.4.8 V a r i a b l e s By now, you must be g e t t i n g a b i t s u s p i c i o u s a b o u t a l l t h e s e names e n c l o s e d i n c o l o n s . The t e c h n i c a l name f o r a word e n c l o s e d i n c o l o n s i s " v a r i a b l e " . A v a r i a b l e s i m p l y i s s o m e t h i n g t h a t c a n v a r y : f o r e x ample, i n o u r p r o c e d u r e GREET, t o d a y :PERSOH: m i g h t be "FRED" and tomorrrow i t might be "MIKE". A v a r i a b l e i s s i m p l y t h e name o f a p i g e o n h o l e i n which any Logo t h i n g c a n be s t o r e d . The s i m p l e s t k i n d o f v a r i a b l e i s t h e i n p u t t o a p r o c e d u r e . I n p u t s a r e s e t t o t h e v a l u e g i v e n when you c a l l t h e p r o c e d u r e . However, s i n c e a number o f p r o c e d u r e s might use t h e same name f o r an i n p u t , Logo does a b i t o f b o o k k e e p i n g f o r y o u . I f you have a p r o c e d u r e HYPBOC, w i t h an i n p u t named :Y:, t h e n when you c a l l MXPROC, Logo w i l l s a v e t h e p r e v i o u s v a l u e o f :!:, and s e t :¥: t o t h e v a l u e s p e c i f i e d a s t h e i n p u t t o MYPROC. When HYPROC f i n i s h e s , :Y: w i l l be s e t t o i t s p r e v i o u s v a l u e . S i n c e t h e i n p u t s t o a p r o c e d u r e a r e used o n l y i n t h e l o c a l e o f t h a t p r o c e d u r e , we c a l l them ? l g c a l v a r i a b l e s ? . We o f t e n c a l l t h e v a l u e a s s o c i a t e d w i t h a v a r i a b l e t h e " T h i n g " o f t h e v a r i a b l e . O f t e n we would l i k e t o use a v a r i a b l e w i t h i n a p r o c e d u r e , e v e n t h o u g h t h a t v a r i a b l e i s n o t an i n p u t t o t h e p r o c e d u r e . F o r example. P a r t 2 A User's Guide To B C I 0 3 0 27 MAKJ "SJ! i l S I s . IS A VERY LONG SEJTENCE" TO PR~:y: i i PRINT j J i 20 PRINT Z_sl END PB ?gELLO? HELLO THIS IS A VERY LONG SENTENCE HAKE i s a command which s e t s the Thing of i t s f i r s t input to be i t s second i n p u t . T h i s procedure uses the value of S, even though S i s not an i n p u t ; S i s t h e r e f o r e c a l l e d " g l o b a l " . T h i s usage i s g u i t e permissable, and a l l o w s a g r e a t d e a l of convenience i n t h a t not e v e r y t h i n g a procedure uses needs to be an i n p u t . However, i t i s p o s s i b l e to get i n t o t r o u b l e , as shown i n the f o l l o w i n g example: BAKE "X" JO T0~MESS :Y.g JO PRINT J J J 20 MAKE ^X^ SUM J.Y: 1 30 PRINT :X:~ END MESS DEFINED MESS 3 3 U PRINT zjz 4 In t h i s example, we ( u n i n t e n t i o n a l l y ) changed the " g l o b a l " X. What we would l i k e to do i s to " p r o t e c t " the g l o b a l X, i n i n the same way t h a t an i n p u t named Y p r o t e c t s the g l o b a l Y ( i f th e r e i s one). He do t h i s by d e c l a r i n g X " l o c a l " , with a t i t l e l i n e l i k e P a r t 2 A U s e r * s G u i d e To B C L 0 3 0 28 TO MESS tit USING : Xj. T h i s d e c l a r e s t h a t MESS w i l l " u s e " X; we want t h e g l o b a l X t o be p r o t e c t e d . T h e r e f o r e , when we s t a r t e x e c u t i n g MESS, Logo w i l l s a v e t h e p r e v i o u s v a l u e o f X (and, f o r t h a t m a t t e r , Y ) . When MESS s t o p s , t h e p r e v i o u s v a l u e s w i l l be r e s t o r e d . 2.4.9 F r i l l s S ometimes i t i s c o n v e n i e n t t o h a l t e x e c u t i o n o f a p r o c e d u r e b e f o r e t h e END l i n e . The STOP command c a u s e s e x e c u t i o n o f t h e p r o c e d u r e f r o m which i t was c a l l e d t o c e a s e i m m e d i a t e l y , and r e t u r n t o i t s c a l l e r . STOP i s used f o r t h o s e p r o c e d u r e s which r e t u r n no v a l u e s i n t h e same way t h a t OUTPUT o p e r a t e s f o r t h o s e p r o c e d u r e s which do r e t u r n v a l u e s . The command GOTOLINE t a k e s one i n p u t which must e v a l u a t e t o a number. C o n t r o l i n t h e c u r r e n t p r o c e d u r e i s t r a n s f e r r e d t o t h e l i n e i d e n t i f i e d by i t s i n p u t . TO FRILL 10 HAKE ;.'NW "DOG" J5 PHINT "HELLO" 20 TEST IS zKz "CAT? 30 IFTRUE STOP 40 PRINT "CANINES HATE F E L I N E S " 50 HAKE »m "CAT" 60 GOTOLINE 20 END FRI L L HELLO CANINES HATE FELINES P a r t 2 A U s e r ' s G u i d e To BCLogo 29 2.4,10 A n o t h e r Example As a l a s t e xample, we g i v e a s o l u t i o n t o t h e famous Towers o f H a n o i p u z z l e . T h i s p u z z l e i s p l a y e d w i t h t h r e e p e g s , and a number o f d i s c s o f d i f f e r i n g s i z e s . One s t a r t s w i t h t h e d i s c s on t h e " s o u r c e " peg, a r r a n g e d i n o r d e r o f s i z e , w i t h t h e s m a l l e s t d i s c on t o p . The o b j e c t i s t o move t h e e n t i r e s t a c k o n t o t h e " d e s t i n a t i o n " peg, s u b j e c t t o t h e f o l l o w i n g r e s t r i c t i o n s : • o n l y t h e t o p d i s c on a s t a c k may be moved a t any t i m e . • o n l y one d i s c a t a t i m e may be moved. • no d i s c may be p l a c e d on a s m a l l e r one. The f o l l o w i n g p r o g ram i m p l e m e n t s t h e most famous s o l u t i o n : t h e r e c u r s i v e one i n which a p r o b l e m o f o r d e r N i s s o l v e d i n t h r e e s t e p s : * s o l v e t h e p r o b l e m o f o r d e r N-1 i n o r d e r t o move a l l b u t t h e bottom d i s c f r o m t h e " s o u r c e " t o t h e " i n t e r m e d i a t e " peg. • move t h e bot t o m d i s c t o t h e " d e s t i n a t i o n " peg. • move a l l o f t h e d i s c s on t h e " i n t e r m e d i a t e " peg t o t h e " d e s t i n a t i o n " . P a r t 2 A User's Guide To BCLogo 30 TO HANOI :Ni ^ S: II 10 TEST IS J. Nj. 0 20 IETRUE STOP ~ 30 HANOI~JDIFFERENCE :1 40 PRINT S "WOVE DISC" 50 HANOI JDJFFERENCE U END 1 11 -$1 lUl ill S ;N:~S !!FROM2! I i 3 1 I I I " I S T ~ T D T :S: S "TO" :D: HANOI [ DEFINED. HANOI 4 "SOURCE" HOVE DISC 1 FROM HOVE DISC 2 FROM HOVE DISC 1 FROM HOVE DISC 3 FROM MOVE DISC 1 FROM MOVE DISC 2 FROM MOVE DISC 1 FROM MOVE DISC 4 FROM MOVE DISC 1 FROM MOVE DISC 2 FROM HOVE DISC 1 FROM HOVE DISC 3 FROM MOVE DISC 1 FROM MOVE DISC 2 FROM MOVE DISC 1 FROM SOURCE TO INTERMEDIATE SOURCE TO DESTINATION INTERMEDIATE TO DESTINATION SOURCE TO INTERMEDIATE DESTINATION TO SOURCE DESTINATION TO INTERMEDIATE SOURCE TO INTERMEDIATE SOURCE TO DESTINATION INTERMEDIATE TO DESTINATION INTERMEDIATE TO SOURCE DESTINATION TO SOURCE INTERMEDIATE TO DESTINATION SOURCE TO INTERMEDIATE SOURCE TO DESTINATION INTERMEDIATE TO DESTINATION S i s a Logo synonym f o r SENTENCE. T r a c i n g HANOI may help ycu understand i t . 2.5 E d i t i n g And Workspace Management Once you have d e f i n e d a f u n c t i o n , you may change t h a t d e f i n i t i o n by using the EDIT command. For example, i f you were to do T O C H I R P 19. P B I N T H C H I R P C H I R P " E N D " Now suppose you wish to modify l i n e 10. You cou l d execute P a r t 2 A U s e r ' s G u i d e To BCLogp 31 EDIT CHIRP How you a r e i n e d i t i n g mode; you c a n i n s e r t o r d e l e t e l i n e s , and you can SHOW t h e a c t i v e f u n c t i o n , j u s t a s i f you were d e f i n i n g CHIRP a g a i n . F o r example . EDIT CHIRP 20 PRINT ^HELLO THERE" END CHIRP CHIRP CHIRP HELLO THERE I f you a r e i n e d i t i n g o r d e f i n i t i o n mode, you c a n use t h e SHOWLINE command t o d i s p l a y a s p e c i f i c l i n e o f y o u r f u n c t i o n . F o r example, assume t h a t we're e d i t i n g CHIRP. EDIT CHIRP SHOWLINE*"l0 10 PRINT "CHIRP CHIRP" Sometimes i t i s c o n v e n i e n t t o d i s p l a y t h e e n t i r e d e f i n i t i o n o f a f u n c t i o n . I f you a r e e d i t i n g a f u n c t i o n , t h e command SHOW w i l l d i s p l a y t h e d e f i n i t i o n o f t h a t f u n c t i o n . EDIT CHIRP SHOW TO CHIRP 10 PRINT "CHIRP CHIRP" 20 PRINT "HELLO THERE" END At any t i m e (even i f you a r e n o t c u r r e n t l y e d i t i n g a n y t h i n g ) , you may d i s p l a y t h e d e f i n i t i o n o f a f u n c t i o n X by t y p i n g SHOW X P a r t 2 A O s e r ^ s G u i d e To E C L 0 3 0 32 SHOW CHIRP TO CHIRP 10 PRINT "CHIRP CHIRP" 20 PRINT "HELLO THERE" END To e r a s e t h e d e f i n i t i o n o f a f u n c t i o n , e x e c u t e EHASE CHIRP CHIRP ERASED. CHIRP I DON'T KNOW HOW TO CHIRP. In o r d e r t o a l l o w you t o d e v e l o p a program o v e r a l o n g p e r i o d o f t i m e , Logo a l l o w s you t o s a v e t h e c u r r e n t workspace ( c o n s i s t i n g o f y o u r p r o c e d u r e s , t h e t r u t h f l a g , and t h e v a l u e s o f t h e v a r i a b l e s ) , and r e l o a d i t a t some l a t e r t i m e . W o rkspaces a r e s a v e d i n f i l e s ; a f i l e i s an a r e a o f d i s c s t o r a g e t o which you have g i v e n a name. I f you have done some work and w i s h t o s a v e i t , e x e c u t e SAVE f i l e n a m e Where ' f i l e n a m e ' i s t h e name you wish t o g i v e t h e f i l e . I f • f i l e n a m e ' a l r e a d y e x i s t s , you w i l l be a s k e d t o c o n f i r m t h a t you r e a l l y d i d want t o s a v e t h e f i l e under t h a t name, s i n c e you might a c c i d e n t a l l y w r i t e o v e r a v a l u a b l e w o r k s p a c e . One v e r y common use o f t h e s e f a c i l i t i e s i s t h e f o l l o w i n g : • s t a r t a s e s s i o n o f f by G E T t i n g a w o r k s p a c e . • d e f i n e o r e d i t f u n c t i o n s . • s a v e t h e r e s u l t i n g w orkspace (the m a t e r i a l which was g o t t e n , p l u s what you have j u s t d o n e ) , back i n t o t h e f i l e you g o t t h e o r i g i n a l w orkspace f r o m . P a r t 2 A U s e r ' s G u i d e To BCLogo 3 3 To r e t r i e v e t h e i n f o r m a t i o n you have SAVEd, you c a n e x e c u t e GET f i l e n a m e T h i s command ad d s t h e m a t e r i a l s t o r e d i n t h e f i l e t o what i s c u r r e n t l y i n t h e w o r k s p a c e . 2.6 Data S t r u c t u r e s B o t e : t h i s s e c t i o n i s p r o b a b l y o f no i n t e r e s t t o t h e b e g i n n i n g Logo programmer; i t i s i n t e n d e d f o r t h e e d i f i c a t i o n o f t h o s e f a m i l i a r w i t h t h e l i s t - p r o c e s s i n g f a c i l i t i e s o f , f o r example . L i s p , A l g o l H, o r P L / I . A l t h o u g h Logo i s a v e r y s i m p l e l a n g u a g e , you c a n use i t f o r many l i s t - p r o c e s s i n g p r o b l e m s . T h i s s e c t i o n i s i n t e n d e d t o e x p l a i n how t o a c c o m p l i s h t h i s . A l i s t - p r o c e s s i n g a l g o r i t h m i s one which b u i l d s i t s d a t a s t r u c t u r e f r o m e l e m e n t a r y o b j e c t s , o r nodes, t o g e t h e r w i t h h o u s e k e e p i n g i n f o r m a t i o n which i s used t o c o n n e c t t h e nodes t o g e t h e r i n some o r d e r . The h o u s e k e e p i n g d a t a a r e c a l l e d p o i n t e r s , o r node names. I t d o e s n ' t m a t t e r what t h e y a r e , as l o n g a s we c a n a l w a y s r e l y upon a g i v e n p o i n t e r t o " p o i n t o u r way" t o t h e same node. I n F o r t r a n we c a n use i n t e g e r s , i n A l g o l W o r P L / I machine a d d r e s s e s , and i n Logo words. I n a d d i t i o n , we must have a " n u l l " , w h i c h d o e s n ' t p o i n t anywhere. Suppose we had a c o l l e c t i o n o f o b j e c t s which we wanted t o P a r t 2 A U s e r ' s G u i d e To ECLpjgo 34 b u i l d i n t o a c h a i n e d d a t a s t r u c t u r e . One way would g i v e us a d a t a s t r u c t u r e which would l o o k l i k e t h a t o f f i g u r e 2-1. The f i r s t segment o f e a c h node i s t h e o b j e c t under c o n s i d e r -a t i o n , and t h e s e c o n d segment p o i n t s t o t h e n e x t node i n t h e s t r u c t u r e . I n Logo t e r m s , a p o i n t e r t o a node N c a n s i m p l y be a word whose T h i n g i s N. F o r example, i f we were t o e x e c u t e MAKE "SUBSCBUBIAL" "NUGATORY" Then we c o u l d s a y t h a t SUBSCRUBIAL p o i n t s t o NUGATORY. T h e r e f o r e , i f we have a p o i n t e r P, we c a n g e t t o t h e o b j e c t i t r e f e r s t o by s i m p l y e x e c u t i n g THING OF "P". Our n u l l c a n be t h e empty t h i n g , a s i t c a n ' t be u s e d t o name a n y t h i n g , anyway. As a l i s t p r o c e s s i n g example, s u p p o s e we have t h e d a t a s t r u c t u r e o f f i g u r e 2-1. We c a n p r i n t i t o u t by e x e c u t i n g TO PSTRUC zJPz JO TEST EMPTYP 20 IFTRUE STOP 30 PRINT FIRST J. P: 40 PSTRUC THING"OF LAST OF _:Pj. END To c r e a t e s u c h a d a t a s t r u c t u r e , we must have a s u p p l y o f names. We c o u l d , i n p r i n c i p l e , use any Logo word as a p o i n t e r ; however, i n o r d e r t o a v o i d c o n f u s i o n between p o i n t e r s and o t h e r names (such as t h o s e f o r i n p u t s ) , we s h o u l d use ' " s t r a n g e l y s p e l l e d " names. One s e g u e n c e which w i l l a d m i r a b l y s u i t o u r p u r p o s e s i s $$1, $$2, $$3, ... F a i l u r e t o d i f f e r e n t i a t e between names used f o r p o i n t e r s and o t h e r names i s a common b u t d i f f i c u l t t o i n t e r p r e t bug. We c a n have a NOD El NODE2 NODE 3 X 1 Each node i n the data structure consists of: * a datum, and * a pointer to the next node i n the structure. The structure could have been b u i l t by executing: MAKE "N0DE1" "X NODE2" MAKE "NODE2" "Y NODE3" MAKE "N0DE3" "Z (empty)" Figure 2-1 A Data Structure. P a r t 2 A U s e r ' s G u i d e To ECLocjo 37 p r o c e d u r e POINTER, which r e t u r n s a new p o i n t e r e a c h t i m e i t i s c a l l e d . TO POINTER "lO TEST JMPTYP :PCOONTER: 20 IFTROE MAKE "PCOUHTER" 0 30 iAKE~^PJO0NTER]l SUM ?PCOUNTER" 1 40 OUTPUT WORD ? $ $ " AND tPCOUNTER:" END L i n e s 10 and 20 a r e f o r i n i t i a l i s a t i o n : t h e f i r s t t i m e POINTER i s c a l l e d , PCOUNTER w i l l be u n a s s i g n e d ; t h u s t h e s e l i n e s w i l l s e t i t t o 0. Now we c a n c r e a t e o u r d a t a s t r u c t u r e : TO C R E A T E U S I N G j_Pj_ i£z_ I P . T Y P E I N 20 T E S T I S : P : ^/END/^ 30 I F T R U E OUTPUT ™ 40 MAKE"" WQ'!"P0INTER 50 HAKE i&l S E N T E N C E : P : C R E A T E 60 O U T P U T zQz END CREATE r e a d s i n a datum. I f i t i s the s p e c i a l s e n t i n e l /END/, we know we have r e a c h e d t h e end o f t h e l i s t b e i n g b u i l t . O t h e r w i s e , we make an a new p o i n t e r , and s e t i t t o a new node c o n s i s t i n g o f t h e datum we j u s t r e a d i n , j o i n e d w i t h t h e p o i n t e r p r o d u c e d by a n o t h e r c a l l t o CREATE. H e r e * s a t r a c e o f CREATE. P a r t 2 A U s e r ' s G u i d e To BCLogo 38 TRACE CREATE HAKE J^MIIST" CREATE CREATE OF A CREATE OF B CREATE OF C CREATE OF CREATE OUTPUTS «" CREATE OUTPUTS « $ $ 1 " CREATE OUTPUTS " $ $ 2 n CREATE OUTPUTS " $ $ 3 M 2.7 The Logo F u n c t i o n s The i n t e n t o f t h i s s e c t i o n i s t o g i v e you an i d e a o f t h e v a r i o u s Logo f u n c t i o n s , and a vague i d e a o f what t h e y do. The f u n c t i o n s a r e l i s t e d by c l a s s e s . F o r a p a r t i c u l a r f u n c t i o n , a c o m p l e t e d e s c r i p t i o n w i l l be f o u n d i n s e c t i o n 2.8. 2 T 7.1 T e x t P r o c e s s i n g « FIRST, LAST, BUTFIRST, and BUTLAST a l l o w you t o t a k e a p a r t words, s e n t e n c e s , o r l i s t s . • COUNT o u t p u t s a number i n d i c a t i n g how many e l e m e n t s a r e i n i t s i n p u t . a WORD, SENTENCE, and LI S T a l l o w you t o c r e a t e new t h i n g s . P a r t 2 A U s e r ' s G u i d g To BCLogo 39 2.7.2 P r e d i c a t e s • IS i s TRUE when i t s two i n p u t s a r e e q u a l . • WORDP i s TRUE when i t s i n p u t i s a word. • SENTENCEP i s TBUE when i t s i n p u t i s a s e n t e n c e o r l i s t . • BOTH i s TRUE when b o t h o f i t s i n p u t s i s . • EITHER i s TRUE when e i t h e r o f i t s i n p u t s i s . • HOT i s TRUE when i t s i n p u t i s f a l s e . • NUMBERP i s TRUE when i t s i n p u t i s a n u m e r i c word. • GREATEBP i s TRUE when i t s f i r s t i n p u t i s n u m e r i c a l l y g r e a t e r t h a n i t s s e c o n d . • LESSP i s TRUE when i t s f i r s t i n p u t i s n u m e r i c a l l y l e s s t h a n i t s s e c o n d . • EQUALP i s TRUE when i t s i n p u t s a r e n u m e r i c a l l y e q u a l . • ZEROP i s TRUE when i t s i n p u t i s n u m e r i c a l l y e g u a l t o 0. 2.7.3 A r i t h m e t i c • SUM, DIFFERENCE, and PRODUCT do t h e f a m i l i a r o p e r a t i o n s o f a d d i t i o n , s u b t r a c t i o n , and m u l t i p l i c a t i o n . • DIVISION o u t p u t s a s e n t e n c e o f t h e q u o t i e n t and r e m a i n d e r f r o m a d i v i s i o n . QUOTIENT and REMAINDER can be used t o compute j u s t one o r t h e o t h e r r e s u l t . • RANDOM o u t p u t s a random d i g i t ; RANDNO o u t p u t s a random number w i t h i n a s p e c i f i e d r a n g e . SEED c a n be used t o examine o r c hange t h e random number s e e d . P a r t 2 A U s e r ' s G u i d e To BCLogo 40 a MAXIMUM and MINIMUM s e l e c t t h e maximum o r minimum o f two numbers. 2.J.7.H F u n c t i o n s a TO a l l o w s y ou t o d e f i n e a new f u n c t i o n . a EDIT a l l o w s you t o change t h e d e f i n i t i o n o f an e x i s t i n g f u n c t i o n . a END s i g n a l s t h a t you have f i n i s h e d d e f i n i n g o r c h a n g i n g a f u n c t i o n . a SHOW d i s p l a y s t h e d e f i n i t i o n o f a f u n c t i o n , a SHOWLINE d i s p l a y s a p a r t i c u l a r l i n e o f a f u n c t i o n , a ERASE e x p u n g e s t h e d e f i n i t i o n o f a f u n c t i o n , a ERASELINE a l l o w s you t o d e l e t e a p a r t i c u l a r l i n e o f a f u n c t i o n . a T I T L E c h a n g e s t h e t i t l e l i n e o f a f u n c t i o n . a OUTPUT c a u s e s t h e c u r r e n t l y - e x e c u t i n g f u n c t i o n t c r e t u r n OUTPUT'S i n p u t a s i t s v a l u e . a GOTOLINE t r a n s f e r s c o n t r o l w i t h i n t h e c u r r e n t l y e x e c u t i n g f u n c t i o n . a STOP t e r m i n a t e s e x e c u t i o n o f t h e c u r r e n t l y e x e c u t i n g f u n c t i o n . a EXIT t y p e s i t s i n p u t , and t h e n b e h a v e s as i f an e r r o r had o c c u r r e d . P a r t 2 ft U s e r ' s G u i d e To BCLo^o 41 2iI-.5 C o n d i t i o n a l s • TEST s e t s t h e t r u t h f l a g f r o m i t s i n p u t . • IFTRUE e x e c u t e s a s t a t e m e n t o n l y i f t h e t r u t h f l a g i s TRUE. • I F F A L S E e x e c u t e s a s t a t e m e n t o n l y i f t h e t h e t r u t h f l a g i s FALSE. 2.7.6 I n p u t / O u t p u t • REQUEST r e a d s i n a l i n e o f d a t a , and o u t p u t s a l i s t r e p r e s e n t i n g t h a t l i n e . • TYPEIN t a k e s an i n p u t ; i t i s e g u i v a l e n t t o "MAKE i n p u t REQUEST". • TYPE p r i n t s i t s i n p u t o n t o t h e u s e r ' s c o n s o l e . • PRINT b e h a v e s a s TYPE d o e s , b u t f o l l o w s t h e p r i n t i n g by t y p i n g a c a r r i a g e r e t u r n . P a r t 2 A U s e r ' s G u i d e To BCIogo 42 2.7.7 T i m i n g a CLOCK o u t p u t s t h e amount o f t i m e you have used s o f a r . a BESETCLOCK s e t s t h e CLOCK v a l u e t o 0. a TIHE o u t p u t s t h e t i m e o f day i n t h e form o f a s e n t e n c e "hh mm s s " , i n which hh i s t h e hour ( i n t h e 24-hour c l o c k ) , mm th e m i n u t e , and s s t h e s e c o n d . a DATE o u t p u t s t h e d a t e a s a s e n t e n c e o f t h e form Mww y y y y mm dd", i n wh i c h ww i s t h e name o f t h e day c f t h e week, y y y y i s t h e y e a r , mm i s t h e name o f t h e month, and dd i s t h e day o f t h e month. F o r example, "TUESDAY 1973 OCTOBEB 9". 2.7.8 System C o n t r o l F u n c t i o n s a GOODBYE g e t s you o u t o f L o g o . a LOGOUT g e t s you o u t o f Log o , and i n a d d i t i o n , hangs up t h e t e l e p h o n e l i n e t o t h e c o m p u t e r . a GET a l l o w s you t o add m a t e r i a l f r o m a f i l e t o t h e pro g r a m s and v a r i a b l e s w i t h which you a r e c u r r e n t l y w o r k i n g . a SAVE s t o r e s y o u r c u r r e n t workspace i n a f i l e . a TRACE c a u s e s a s p e c i f i e d f u n c t i o n t o be m o n i t o r e d f o r d e b u g g i n g p u r p o s e s . a UNTRACE t u r n s o f f debug m o n i t o r i n g f o r a f u n c t i o n . P a r t 2 A U s e r 1 s G u i d e To ECLogo 43 2.7.9 V a r i a b l e s • MAKE c h a n g e s t h e v a l u e o f a s p e c i f i e d v a r i a b l e . • THING r e t u r n s t h e t h i n g o f a v a r i a b l e . 2.7. 10 P rogram M a n i p u l a t i o n F u n c t i o n s • DO t a k e s as i t s i n p u t a t h i n g r e p r e s e n t i n g a Logo s t a t e m e n t ; i t e x e c u t e s t h a t s t a t e m e n t . • LINES and TEXT a r e used t o m a n i p u l a t e p r o c e d u r e s : i f X i s t h e u s e r p r o c e d u r e TO X :A: 10 PRINT "HELLO" 20 PRINT :A: END Then LINES "X" r e t u r n s t h e s e n t e n c e "10 2 0 " — t h e s e n t e n c e c f l i n e numbers o f a p r o c e d u r e . TEXT "X" 20 r e t u r n s t h e s e n t e n c e "20 PRINT :A:". T h e s e two f u n c t i o n s a l l o w y o u r program t o go t h r o u g h a f u n c t i o n , s c a n n i n g f o r s o m e t h i n g , o r d o i n g some s y s t e m a t i c a l t e r a t i o n . I n o r d e r t o a l l o w you t o g e t t h e t i t l e l i n e , l i n e number 0 r e f e r e n c e s t h e t i t l e : TEXT "X" 0 i s "TO X :A:". Note t h a t DO can be u s e d t o i n s e r t a l i n e : BO "10 PRINT 1", | s e { » 2 . 7 . 11 m i s c e l l a n e o u s f u n c t i o n s ' ) • IGNORE t a k e s one i n p u t and does a b s o l u t e l y n o t h i n g w i t h i t . P a r t 2 A U s e r ^ s G u i d e To B C L 0 3 0 44 2.8 A G l o s s a r y Of L o j o F u n c t i o n s T h i s s e c t i o n d e s c r i b e s t h e s e t o f Logo f u n c t i o n s c u r r e n t l y a v a i l a b l e . The f u n c t i o n s a r e l i s t e d i n a l p h a b e t i c a l o r d e r . Some f u n c t i o n s have synonyms ( f o r example, PRINT and P have t h e same e f f e c t ) ; t h e synonyms o f a g i v e n f u n c t i o n name a r e l i s t e d a f t e r t h e f u n c t i o n name. W h i l e t h i s l i s t l o o k s v e r y i m p o s i n g , you s h o u l d n o t t a k e i t t o o s e r i o u s l y : nobody r e a l l y e x p e c t s t h a t a b e g i n n i n g Logo s t u d e n t s h o u l d r e a l l y l e a r n f i f t y f u n c t i o n s o f f by h e a r t . When t e a c h i n g Logo, one s h o u l d s t a r t o f f w i t h a s u b s e t o f a b o u t 15 f u n c t i o n s ; t h e e x a c t s e t would v a r y a c c o r d i n g t o t h e needs o f t h e s t u d e n t . One s u c h s e t would be: FIRST, BUTFIRST, WORD, SENTENCE, TEST, I S , IFTRUE, I F F A L S E , TO, EDIT* SHOW, ERASE, END, GOODBYE, OUTPUT However, you can t a i l o r t h e e x a c t s e t t o y o u r n e e d s . BOTH ( 2 - i n p u t o p e r a t i o n ) o u t p u t s TRUE i f bo t h o f i t s i n p u t s a r e TRUE; o t h e r w i s e i t o u t p u t s FALSE. BUTFIRST BP ( 1 - i n p u t o p e r a t i o n ) o u t p u t s a t h i n g made up o f a l l b u t t h e f i r s t e l e m e n t o f i t s i n p u t . G e n e r a t e s an e r r o r i f g i v e n empty. BUTLAST BL ( 1 - i n p u t o p e r a t i o n ) o u t p u t s an t h i n g made o f a l l b u t t h e l a s t e l e m e n t o f i t s i n p u t . G e n e r a t e s an e r r o r i f g i v e n t h e empty t h i n g . ( O - i n p u t o p e r a t i o n ) o u t p u t s t h e amount o f t i m e s i n c e t h e l a s t c a l l t o BESETCLOCK. I f RESETCLOCK has n e t been c a l l e d , o u t p u t s t h e amount o f t i m e s i n c e Logo was s t a r t e d . ( 1 - i n p u t o p e r a t i o n ) o u t p u t s a number i n d i c a t i n g how many e l e m e n t s a r e i n t h e i n p u t . COUNT o f a word i s t h e number o f c h a r a c t e r s i n i t . COUNT c f a s e n t e n c e i s t h e number c f words i n i t . COUNT o f empty i s 0. ( 0 - i n p u t o p e r a t i o n ) o u t p u t s a s e n t e n c e o f 4 e l e m e n t s : t h e f i r s t i s t h e day o f t h e week, t h e s e c o n d i s t h e y e a r , t h e t h i r d t h e name o f t h e month, and t h e f o u r t h t h e day o f t h e month. F o r example, "MONDAY 1973 OCTOBER 8". ( 2 - i n p u t o p e r a t i o n ) g i v e n two n u m e r i c words, DIFFERENCE o u t p u t s t h e a r i t h m e t i c d i f f e r e n c e . ( 2 - i n p u t o p e r a t i o n ) o u t p u t s a s e n t e n c e whose FIRST i s QUOTIENT c f i t s i n p u t s , and whose LAST i s REMAINDER o f i t s i n p u t s . ( 1 - i n p u t command) e x e c u t e s t h e l o g o s t a t e m e n t s p e c i f i e d by t h e i n p u t , w h ich i s a word c r s e n t e n c e i n d i c a t i n g a Logo command. F o r example, "DC "PRINT 1 n " w i l l c a u s e 1 t o be p r i n t e d . An i n p u t may be a command, o r i t may be a command p r e f i x e d by a l i n e number: DO "10 PRINT 1" i n s e r t s "PRINT 1" as l i n e 10 o f t h e f u n c t i o n c u r r e n t l y b e i n g e d i t e d . (command f o l l o w e d by p r o c e d u r e name) c a u s e s you t o e n t e r e d i t i n g mode, w i t h t h e s p e c i f i e d f u n c t i o n made t h e c u r r e n t l y e d i t e d f u n c t i o n . ( 2 - i n p u t o p e r a t i o n ) o u t p u t s TRUE i f e i t h e r i n p u t i s TRUE. I f b o t h a r g u m e n t s a r e FALSE, i t o u t p u t s FALSE. ( 1-input o p e r a t i o n ) o u t p u t s TRUE i f i t s i n p u t i s EMPTY; o t h e r w i s e i t o u t p u t s f a l s e . ( 0-input command) c a u s e s an e x i t f r o m d e f i n i t i o n o r e d i t i n g mode i n t o i mmediate e x e c u t i o n mode. ( 2-input o p e r a t i o n ) o u t p u t s TRUE i f i t s i n p u t s a r e n u m e r i c a l l y e g u a l , and FALSE o t h e r w i s e . Two numbers a r e compared n u m e r i c a l l y by d i s r e g a r d i n g l e a d i n g z e r o ' s , and t a k i n g s i g n s i n t o a c c o u n t . (command f o l l o w e d by p r o c e d u r e name) d e l e t e s t h e d e f i n i t i o n o f t h e s p e c i f i e d p r o c e d u r e . (1-input command) d e l e t e s t h e l i n e s p e c i f i e d by t h e i n p u t from t h e c u r r e n t l y e d i t e d f u n c t i o n . (1-input o p e r a t i o n ) o u t p u t s t h e f i r s t e l e m e n t o f i t s i n p u t ; g e n e r a t e s an e r r o r i f t h e i n p u t i s empty. (command f o l l o w e d by f i l e name) adds t h e d a t a s t o r e d i n t h e f i l e t o t h e c u r r e n t w o r k s p a c e . ( 0-input command) c a u s e s Logo t o r e t u r n c o n t r o l t o t o t h e o p e r a t i n g s y s t e m . (2-input o p e r a t i o n ) o u t p u t s TRUE i f th e f i r s t argument i s n u m e r i c a l l y g r e a t e r t h a n t h e s e c o n d , and FALSE o t h e r w i s e . ( 1 - i n p u t command) t h e i n p u t must be a l i n e number i n t h e c u r r e n t l y e x e c u t i n g f u n c t i o n . C o n t r o l i s t r a n s f e r r e d t o t h e s p e c i f i e d l i n e . (command f o l l o w e d by s t a t e m e n t ) i f t h e t r u t h f l a g i s c u r r e n t l y s e t t o FALSE, t h e n t h e s t a t e m e n t i s e x e c u t e d ; o t h e r w i s e , n o t h i n g happens. P a r t 2 A U s e r ' s G u i d e To B C L 0 3 0 47 IFTRUE IFT IGNORE (command f o l l o w e d by s t a t e m e n t ) i f t h e t r u t h f l a g i s c u r r e n t l y s e t t o TRUE, t h e s t a t e m e n t i s e x e c u t e d ; o t h e r w i s e , n o t h i n g h a p p e n s . ( 1-input command) does n o t h i n g a t a l l . IS ( 2 - i n p u t o p e r a t i o n ) t h e i n p u t s may be any Logo t h i n g s . IS r e t u r n s TRUE i f t h e y a r e t h e same o b j e c t , and FaLSE o t h e r w i s e . LaST L LESSP ( 1 - i n p u t o p e r a t i o n ) o u t p u t s t h e l a s t e l e m e n t o f i t s i n p u t . G e n e r a t e s an e r r o r i f g i v e n empty. ( 2 - i n p u t o p e r a t i o n ) o u t p u t s TRUE i f t h e f i r s t argument i s n u m e r i c a l l y l e s s t h a n t h e s e c o n d , and FALSE o t h e r w i s e . LINES L I S T LOGOUT ( 1 - i n p u t o p e r a t i o n ) o u t p u t s a s e n t e n c e o f t h e l i n e numbers o f t h e f u n c t i o n named by t h e i n p u t . ( 2 - i n p u t o p e r a t i o n ) o u t p u t s a two-e l e m e n t l i s t , whose FIRST i s t h e f i r s t i n p u t , and whose LAST i s t h e s e c o n d i n p u t . ( 0-input command) c o n t r o l i s r e t u r n e d t o t h e o p e r a t i n g s y s t e m i n i n s u c h a way t h a t t h e computer d i s c o n n e c t s t h e c o m m u n i c a t i o n s l i n e . MAKE ( 2 - i n p u t command) c a u s e s t h e t h i n g o f t h e f i r s t i n p u t t o be t h e s e c o n d i n p u t . F o r example, MAKE "A" "THE COW ATE THE CHEESE" c a u s e s :A: CHEESE. t o be THE COW ATE THE An i n t r o d u c t o r y f o r m o f MAKE i s a l s o p r o v i d e d . T h i s f o r m i s used as f o l l o w s : MAKE NAME: BELLA THING: CCOLA Logo prompts t h e u s e r f o r t h e name and t h i n g when t h e i n t r o d u c t o r y BAKE i s used. P a r t 2 A User's Guide To BCLogo 48 MAXIMUM MAX NOT NUMBERP (2-input operation) outputs the maximum of the two arguments, compared n u m e r i c a l l y . | f('minimum min»,2-input operation*) outputs the minimum of the two arguments, compared n u m e r i c a l l y . (1-input operation) outputs TRUE i f i t s i n p u t i s FALSE, and FALSE i f i t s i n p u t i s TRUE. (1-input operation) outputs TRUE i f i t s i n p u t i s a number, and FALSE otherwise. OUTPUT PRINT P (1-input command) causes the c u r r e n t l y executing procedure to r e t u r n with the i n p u t as i t s output. (1-input command) types i t s input cn the user's console, and then types a c a r r i a g e r e t u r n . PRODUCT PROD (2-input operation) outputs the a r i t h m e t i c product of i t s two i n p u t s , which must be numbers. QUOTIENT (2-input operation) outputs g u o t i e n t of i t s two i n p u t s . the RANDNO (1-input operation) outputs a number chosen a t random which i s n u m e r i c a l l y l e s s than the number given as i n p u t . 0 i s a p o s s i b l e output from RANDNO. RANDOM (0-input operation) chosen a t random. 0 output. outputs a d i g i t i s a p o s s i b l e REMAINDER (2-input operation) outputs remainder of i t s two i n p u t s . the REQUEST (0-input operation) reads a l i n e , and r e t u r n s a t h i n g corresponding to the l i n e . The r e s u l t of REQUEST i s aJLwajjs a l i s t . RESETCLOCK RESET (0-input command) r e s e t s the i n t e r n a l c l o c k . P a r t 2 A U s e r ' s G u i d e To BCLogg 49 SAVE (command f o l l o w e d by f i l e name) s a v e s t h e p r o c e d u r e s and v a r i a b l e s o f t h e c u r r e n t workspace i n t h e s p e c i f i e d f i l e . SEED ( 1 - i n p u t o p e r a t i o n ) o u t p u t s t h e c u r r e n t v a l u e o f t h e s e e d f o r t h e random number g e n e r a t o r . I f t h e i n p u t i s n o n - z e r o , t h e s e e d w i l l be s e t t o t h e v a l u e g i v e n by t h e i n p u t , which must be n u m e r i c . SENTENCE S ( 2-input o p e r a t i o n ) o u t p u t s a s e n t e n c e made from t h e f i r s t i n p u t f o l l o w e d by t h e s e c o n d i n p u t . I f e i t h e r i n p u t i s a word, i t i s c o n v e r t e d t o a o n e - e l e m e n t s e n t e n c e . SENTENCEP ( 1 - i n p u t o p e r a t i o n ) o u t p u t s TRUE i f i t s i n p u t i s a s e n t e n c e (or a l i s t ) , and FALSE o t h e r w i s e . SHOW SHOWLINE STOP (command f o l l o w e d by p r o c e d u r e name) p r i n t s o u t t h e d e f i n i t i o n c f t h e s p e c i f i e d p r o c e d u r e . I n e d i t i n g o r d e f i n i t i o n mode, t h e p r o c e d u r e name need n o t be s p e c i f i e d , i n which c a s e t h e f u n c t i o n c u r r e n t l y b e i n g e d i t e d w i l l be d i s p l a y e d . ( 1 - i n p u t command) d i s p l a y s t h e l i n e o f t h e c u r r e n t l y e d i t e d f u n c t i o n s p e c i f i e d by t h e i n p u t . ( 0-input command) c a u s e s t h e c u r r e n t l y e x e c u t i n g p r o c e d u r e t o r e t u r n . SUH TEST ( 2-input o p e r a t i o n ) t h e i n p u t s must be numbers. SUH o u t p u t s a word which i s t h e a r i t h m e t i c sum o f t h e two i n p u t s . ( 1 - i n p u t command) t h e i n p u t , which must be one o f t h e words TRUE o r FALSE, i s s t o r e d away i n t h e t r u t h f l a g . P a r t 2 A U s e r ' s G u i d e To BCLogo 50 TEXT ( 2-input o p e r a t i o n ) o u t p u t s a l i n e o f th e f u n c t i o n s p e c i f i e d by t h e f i r s t a rgument. F o r example: TO GREET :X: 10 PRINT "HELLO" 20 PRINT :X: END TEXT OF "GREET" 20 w i l l o u t p u t "20 PRINT :X:". S p e c i f i y i n g l i n e 0 w i l l o b t a i n t h e t i t l e l i n e . THING TIHE T I T L E TO TRACE TYPE TYPEIN WAIT ( 1-input o p e r a t i o n ) o u t p u t s t h e t h i n g o f t h e word g i v e n by t h e i n p u t . ( 0-input o p e r a t i o n ) o u t p u t s t h e t i m e o f day a s a s e n t e n c e o f "h o u r m i n u t e day". (command f o l l o w e d by t i t l e l i n e ) c h a n g e s t h e t i t l e o f t h e c u r r e n t l y e d i t e d f u n c t i o n t o t h a t s p e c i f i e d . (command f o l l o w e d by t i t l e l i n e ) e n t e r s d e f i n i t i o n mode, e d i t i n g t h e f u n c t i o n s p e c i f i e d i n t h e t i t l e l i n e . G e n e r a t e s an e r r o r i f t h e f u n c t i o n i s a l r e a d y d e f i n e d . (command f c a u s e s t h t r a c e d : ea c a l l e d , a t o i n d i c a t h e a r g u p r o c e d u r e w i l l be p r o u t p u t , i f o l l o w e d by pr e s p e c i f i e d ch t i m e t h e message w i l l t e t h e d e p t ments. Each r e t u r n r e t u i n t e d o u t , i any, o f t h e o c e d u r e name) f u n c t i o n t o be p r o c e d u r e i s be p r i n t e d o u t h o f c a l l , and t i m e t h e r n s , a message n d i c a t i n g t h e p r o c e d u r e . ( 1 - i n p u t command) p r i n t s o u t i t s i n p u t on t h e u s e r ' s c o n s o l e , but does n o t t y p e a c a r r i a g e r e t u r n a f t e r w a r d . ( 1-input command) HAKE i n p u t REQUEST. e q u i v a l e n t t o ( 1 - i n p u t command) w a i t s t h e number o f s e c o n d s g i v e n by t h e i n p u t . P a r t 2 A U s e r ' s G u i d e To BCIggo 51 UHTRACE WORD W WORDP (command f o l l o w e d by p r o c e d u r e name) t u r n s o f f t r a c i n g f o r t h e s p e c i f i e d p r o c e d u r e . ( 2 - i n p u t o p e r a t i o n ) o u t p u t s a word made from t h e c h a r a c t e r s o f t h e f i r s t i n p u t f o l l o w e d by t h o s e o f t h e s e c o n d i n p u t . G e n e r a t e s an e r r o r i f e i t h e r i n p u t i s a s e n t e n c e o r l i s t . ( 1 - i n p u t o p e r a t i o n ) o u t p u t s TRUE i f i t s argument i s a word, and FALSE o t h e r w i s e . ZEROP ( 1 - i n p u t o p e r a t i o n ) o u t p u t s TRUE i f i t s i n p u t i s n u m e r i c a l l y e g u a l t o 0 , and FALSE o t h e r w i s e . P a r t 3 BCPL 52 I : : 1 I t 1 PAST 3 BCPL J I I I I i j { They have been a t a g r e a t f e a s t c f l a n g u a g e s , and s t o l e n t h e s c r a p s . — S. S h a k e s p e a r e , L o v e ' s L a b o u r ' s L o s t } A l t h o u g h i t would be o u t o f p l a c e t o g i v e a c o m p l e t e d e s c r i p t i o n o f BCPL h e r e ( f o r f u l l d e t a i l s , t h e r e a d e r i s r e f e r r e d t o [ R I C H 6 9 ] ) ; a summary o f t h e l a n g u a g e w i l l p e r h a p s a i d i n u n d e r s t a n d i n g t h e s t r u c t u r e o f t h e s y s t e m . BCPL i s an A l g o l - l i k e l a n g u a g e d e s i g n e d f o r c o m p i l e r w r i t i n g ; i t s two p r i m e a n c e s t o r s a r e CPL [BABB63] and A l g o l 60 {NAUR63], The l a n g u a g e i s d e s i g n e d w i t h two p a r t i c u l a r g o a l s i n mind: • machine i n d e p e n d e n c e , e v e n a t t h e c o s t o f a s l i g h t d e c r e a s e i n e f f i c i e n c y , and • "good programming s t y l e " , i n e n c o u r a g i n g m o d u l a r i t y and d i s c o u r a g i n g a r b i t r a r y u s e o f GOTO's. The b a s i c datum o f t h e l a n g u a g e i s t h e word, o r c e l l . A word i s a s t r i n g o f b i t s : i t i s presumed t o be t h e p r i m a r y a d d r e s s i n g u n i t o f t h e c o m p u t e r . H h i l e word l e n g t h i s n o t s p e c i f i e d , i t i s assumed t o be a t l e a s t 16. I n p a r t i c u l a r , a word must be a b l e t o c o n t a i n a machine a d d r e s s . S i n c e a word i s s i m p l y a b i t s e g u e n c e , t h e o b j e c t i n a word can be o f any t y p e : an u n s i g n e d i n t e g e r , a s i g n e d i n t e g e r , a c h a r a c t e r , a p o i n t e r , a f l o a t i n g - p o i n t number, o r a P a r t 3 BCPL 53 b i t mask. T h i s means t h a t BCPL does no t y p e c h e c k i n g w h a t s o e v e r — t h e onus i s on t h e programmer t o e n s u r e t h a t he d o e s n o t use a s t a t e m e n t a d d r e s s when, f o r example, d o i n g f l o a t i n g p o i n t a r i t h m e t i c . I t may seem t h a t t h i s l e a v e s t h e programmer e x p o s e d t o a l l k i n d s o f d a n g e r s ; however, from my e x p e r i e n c e s w h i l e w r i t i n g BCLogo, I had v e r y few e r r o r s t h a t c o u l d have been c a u g h t by t h e t y p e - c h e c k i n g m a c h i n e r y o f t h e a v e r a g e A l g o l 60 c o m p i l e r — m o s t o f my e r r o r s were i n t r y i n g t o u s e NULL a s a v a l i d p o i n t e r . I h a v e more t o s a y on t h i s t o p i c i n t h e c o n c l u s i o n s . One f e a t u r e which makes BCPL machine i n d e p e n d e n t i s t h a t s u c c e s s i v e word a d d r e s s e s a r e g u a r a n t e e d t o d i f f e r by 1. T h i s means t h a t even t h o u g h word a d d r e s s e s on t h e 360, f o r example, d i f f e r by 4, a BCPL program which r u n s on a word o r i e n t e d machine s u c h as a PDP10 w i l l work c n t h e 360. As f a r as good programming s t y l e i s c o n c e r n e d , t h e r e a r e two p a r t i c u l a r l y p l e a s a n t BCPL f e a t u r e s : t h e g l o b a l v e c t o r , and t h e s t a c k . The g l o b a l v e c t o r i s s i m p l y an a r r a y which i s a c c e s s i b l e f r o m a l l modules o f t h e program. The programmer may d e c l a r e t h a t an i d e n t i f i e r X r e f e r s t o c e l l n o f t h e g l o b a l v e c t o r . I f he d o e s so i n a l l h i s modules, t h e n he can use X i n a l l h i s m o d u l e s . T h i s means t h a t X has become a g l o b a l v a r i a b l e . The whole a r r a n g e m e n t i s much l i k e F o r t r a n ' s COMMON b l o c k s , but much l e s s u n r e l i a b l e — t h e a s s o c i a t i o n w i t h common words i s n o t done by o r d e r i n g w i t h i n t h e d e c l a r a t i o n s , b u t by e x p l i c i t l y s p e c i f i e d numbers. A l s o , s i n c e t h e g l o b a l v e c t o r i s an a r r a y , one c a n i n d e x i n t o i t . T h i s f e a t u r e i s p u t t o good P a r t 3 BCPL 54 use by t h e p r i m i t i v e f u n c t i o n s . Each BCPL o b j e c t module c o n t a i n s a t a b l e i n d i c a t i n g t h o s e g l o b a l v e c t o r l o c a t i o n s w h i c h a r e t o be p r e s e t w i t h s p e c i f i e d r o u t i n e a d d r e s s e s . T h e r e f o r e , t h e modules o f p r i m i t i v e f u n c t i o n s s p e c i f y t h a t t h e p r i m i t i v e s a r e t o be l o a d e d i n t o s p e c i f i c g l o b a l v e c t o r l o c a t i o n s . T h e n , a t i n i t i a l i s a t i o n t i m e , commands a r e r e a d which i n e f f e c t s a y " f u n c t i o n E00, l o c a t e d a t g l o b a l v e c t o r e n t r y n, i s p r e d e f i n e d . " T h i s means t h a t t h e s y s t e m does not have t o be r e c o m p i l e d when e a c h new f u n c t i o n i s a d d e d . S i n c e BCPL i s o r i e n t e d a r o u n d a s t a c k , i t i s v e r y e a s y t o a l l o c a t e s t o r a g e d y n a m i c a l l y f o r s h o r t - t e r m needs, w i t h o u t t y i n g c o r e up o v e r a l o n g e r p e r i o d , a l s o , e v e n though one wants, f o r e f f i c i e n c y r e a s o n s , t o a v o i d r e c u r s i o n whenever p o s s i b l e ^ some p r o c e d u r e s ( e s p e c i a l l y i n p u t / o u t p u t ) a r e most n a t u r a l l y programmed r e c u r s i v e l y . & s t a c k makes t h i s p o s s i b l e . One p r o b l e m w h i c h v i t i a t e d t h e use o f t h e s t a c k t o some d e g r e e d u r i n g d e b u g g i n g was an e r r o r i n t h e BCPL r u n - t i m e s u p p o r t p a c k a g e which made t h e s y s t e m e x p i r e n o i s i l y when t h e s t a c k o v e r f l o w e d . D u r i n g t h e p l a n n i n g s t a g e s o f t h e t h e s i s , I e v a l u a t e d a number o f d i f f e r e n t l a n g u a g e s . I r e j e c t e d some, s u c h as A s s e m b l e r and PL360 a s b e i n g t o o machine d e p e n d e n t ; a l s o , t o o much i s a s k e d o f t h e p e r s o n who s i m p l y w i s h e s t o add a new p r i m i t i v e f u n c t i o n . F o r t r a n c a n be made m a c h i n e - i n d e p e n d e n t ( a l t h o u g h nobody e v e r r e a l l y i m p l e m e n t s AHSI s t a n d a r d F o r t r a n ) ; however, I d i d n o t r e l i s h t h e t h o u g h t o f programming i n a s u n s t r u c t u r e d a P a r t 3 BCPL 55 l a n g u a g e a s F o r t r a n — i n a d d i t i o n , F o r t r a n l a c k s seme o f t h e a b s o l u t e n e c e s s i t i e s o f a s y s t e m programming l a n g u a g e : dynamic s t o r a g e a l l o c a t i o n , named c o n s t a n t s , and b i t m a n i p u l a t i o n . A l g o l W and P L / I a r e a l s o g u i t e r e a s o n a b l e c a n d i d a t e s — b o t h have been i m p l e m e n t e d on a number o f machines (one c o u l d g u i t e r e a s o n a b l y t r a n s l a t e an A l g o l W program i n t o SAIL [ swin73], f o r e x a m p l e ) ; y e t t h e i m p l e m e n t a t i o n s a v a i l a b l e cn o u r s y s t e m d i d not g e n e r a t e e f f i c i e n t enough c o d e . Of t h e l a n g u a g e s a v a i l a b l e on o u r s y s t e m , o n l y BCPL had t h e r i g h t c o m b i n a t i o n o f s t r u c t u r e , e f f i c i e n c y , machine i n d e p e n d e n c e , and power. I f e e l t h a t i t would have been no h a r d e r t o have w r i t t e n t h e s y s t e m i n P L / I o r A l g o l ; however, t h e s e l a n g u a g e s were n o t e c o n o m i c a l l y r e a s o n a b l e on o u r s y s t e m . The r e s u l t s have been g u i t e p l e a s i n g : t h e l a n g u a g e i s a t l e a s t a s c o n v e n i e n t a s , s a y A l g o l W; y e t , o f c o u r s e , t h e i m p l e m e n t a t i o n i s more e f f i c i e n t t h a n A l g o l H. P r o b a b l y t h e main h u r d l e was i n d e b u g g i n g — s i n c e t h e r e i s c u r r e n t l y no s y m b o l i c d e b u g g i n g s y s t e m f o r BCPL, t h e main d e b u g g i n g method was t h e i n s e r t i o n o f more o u t p u t s t a t e m e n t s . L u c k i l y , t h e c o m p i l e r i s c h e a p enough t o r u n t h a t t h i s was no g r e a t drawback. N e v e r t h e l e s s , t h e r e were a number o f t i m e s a t which I l o n g e d f o r t h e CHECK c o n d i t i o n s o f P L / I , o r t h e f o r m a t t e d p ost-mortem dumps o f A l g o l W. On t h e whole, however, i t was v e r y e a s y t o l o c a t e e r r o r s — t h e r e were a l m o s t no e r r o r s which were not a t once l o c a t a b l e i n a g i v e n module. BCPL co d e i s a t l e a s t as r e a d a b l e as t h a t o f A l g o l W o r P L / I , and t h u s t h e r e were v e r y few o c c a s i o n s when I a s k e d m y s e l f "What was I P a r t 3 BCPL 56 t h i n k i n g when I wrote t h a t ? " . One s i g n i f i c a n t p l u s which some P L / I i m p l e m e n t a t i o n s ( b u t n o t o u r s ) s h a r e w i t h BCPL i s t h a t p r o c e d u r e a d d r e s s e s a r e d a t a — t h e r e f o r e , one c a n have an a r r a y o f p r o c e d u r e s . I u s e d t h a t f e a t u r e i n t h e a d m i n i s t r a t i o n c f p r o c e d u r e s . a l a n g u a g e which d o e s n o t a l l o w a r r a y s o f p r o c e d u r e s would r e g u i r e t h a t p r i m i t i v e s be r e a c h e d by s o m e t h i n g l i k e a c a s e s t a t e m e n t i n a l g o l , o r a computed go t o i n F o r t r a n . T h i s i n t u r n makes new p r i m i t i v e f u n c t i o n s h a r d e r t o a d d . P a r t i i System D e s c r i p t i o n 57 r : : T ! I t PART 4 SYSTEM DESCRIPTION | i I I I t ; I { My name i s Ozymandias, k i n g o f k i n g s Look upon my works, ye m i g h t y , and d e s p a i r — P.B. S h e l l e y , Ozymandias } T h i s s e c t i o n a t t e m p t s t o g i v e t h e r e a d e r a f e e l i n g f o r how t h e s y s t e m i s c o n s t r u c t e d . F o r f u l l d e t a i l s , t h e r e a d e r i s r e f e r r e d t o a f o r t h c o m i n g document [MANI73]. BCLogo i s g u i t e m o d u l a r , i n t h a t t h e components o f t h e s y s t e m a r e r e l a t i v e l y i n d e p e n d e n t . A l m o s t a l l c o m m u n i c a t i o n between components o c c u r s e i t h e r i n g l o b a l v a r i a b l e s o r i n t h e • d a t a b a s e ' — t h e g a r b a g e c o l l e c t e d a r e a . The components p r e s e n t l y i n t h e s y s t e m a r e : • t h e p a r s e r i s used t o c o n v e r t from c h a r a c t e r s t r i n g s i n t o i n t e r n a l p r o g r a m f o r m a t . L a t e r , when i n f i x o p e r a t o r s a r e added, t h e p a r s e r w i l l be e x t e n d e d t o put t h e o p e r a t o r s i n t h e r i g h t p l a c e . • t h e i n t e r p r e t e r i s used t o e x e c u t e program l i n e s . I t s c a n s e a c h l i n e , and e v a l u a t e s a l l t h e f u n c t i o n c a l l s o f a l i n e . • t h e s t o r a g e manager and q a r b a g e c o l l e c t o r a l l o c a t e s p a c e . When i t i s n o t p o s s i b l e t o a l l o c a t e more s p a c e , t h e g a r b a g e c o l l e c t o r t h e n f r e e s a l l • u s e l e s s 1 s p a c e — t h a t which i s n o t c u r r e n t l y b e i n g r e f e r e n c e d . When i t i s n e t p o s s i b l e t o r e c l a i m any s p a c e a t a l l , t h e s y s t e m s i m p l y r e t i r e s w i t h t h e comment "Logo needs more s p a c e — s e e y o u r t e a c h e r " . M i n e r 4 System D e s c r i p t i o n 58 m o d i f i c a t i o n s c o u l d be made t o a l l o w t h e s y s t e m t o a c q u i r e more s t o r e d y n a m i c a l l y a t t h i s p o i n t . • t h e p r i m i t i v e f u n c t i o n s a c c o m p l i s h t h e a c t i o n s s p e c i f i e d by t h e Logo b u i l t - i n f u n c t i o n s . • t n e i n i t i a l i s a t i o n r o u t i n e c l e a r s t h e w o r k s p a c e , and p u t s i n t h e d e f i n i t i o n s o f t h e b u i l t - i n f u n c t i o n s . • t h e u n p a r s e r c o n v e r t s f r o m i n t e r n a l p rogram f o r m a t t o c h a r a c t e r s t r i n g f o r m a t . • a number o f m i s c e l l a n e o u s r o u t i n e s h a n d l e e r r o r s and i n t e r f a c i n g t o t h e s y s t e m . 4.1 D a t a S t r u c t u r e s BCLogo u s e s two p r i m a r y t y p e s o f d a t a : f i x e d l e n g t h b l o c k s , o r nodes, and v a r i a b l e l e n g t h s t r i n g s , o r p r i n t names, any L i s p programmer w i l l f e e l a t home w i t h t h e i n t e r n a l s t r u c t u r e : • words a r e s t o r e d u n i q u e l y u s i n g an O b l i s t . m s e n t e n c e s a r e l i n k e d l i s t s o f nodes. a word i s r e p r e s e n t e d i n t e r n a l l y by a d a t a s t r u c t u r e c a l l e d an atom, which i s composed o f two p a r t s : t h e atomhead i s a node c o n t a i n i n g a p o i n t e r t o t h e T h i n g o f t h e word, a p o i n t e r t o t h e u s e r p r o c e d u r e ( i f any) d e f i n e d f o r t h i s word, s w i t c h e s s u c h as whether t h e p r o c e d u r e i s t r a c e d o r n o t , and a p o i n t e r t o t h e atom t a i l * which c o n t a i n s t h e p r i n t name r e p r e s e n t i n g t h e word. The s t r u c t u r e o f an atom i s shown i n f i g u r e 4-1. MAKE WV TO a \6 PRINT N HELLO" Chcut\ pointer {0r atoms in sajflve €^ u\u. class Pointer to atom u\x/" Pomter far control b\ocK •tor Q <pf$ cedars Ao\6\ces>s o\ tt OLC^vkmeni^5 t r a c e f te^ FIGURE. THE FORMAT OF AM /VTOM P a r t 4 System D e s c r i p t i o n 60 S i n c e atoms a r e r e p r e s e n t e d u n i q u e l y , we must have some means o f d e t e r m i n i n g f o r a g i v e n word what atom r e p r e s e n t s i t . I have f o l l o w e d t h e s t a n d a r d L i s p s o l u t i o n t o t h i s p r o b l e m : t h e O b l i s t , w hich i s s i m p l y an a r r a y i n t o which a d d r e s s e s a r e computed by means o f a h a s h i n g f u n c t i o n on t h e p r i n t name. Each e l e m e n t o f t h e a r r a y p o i n t s t o a l i n k e d l i s t o f atoms, e a c h o f which i s i n t h e same e q u i v a l e n c e c l a s s . To f i n d a g i v e n word, t h e s y s t e m s e a r c h e s a l o n g t h e p a r t i c u l a r e q u i v a l e n c e c l a s s . I f t h e word i s f o u n d , t h e a d d r e s s o f t h e e x i s t i n g atom i s u s e d f o r t h e word. O t h e r w i s e , a new atom i s c o n s t r u c t e d and added t o t h e O b l i s t ; i t s a d d r e s s i s t h e n u s e d . T h i s p r o c e s s s o u n d s q u i t e e x p e n s i v e . However, i t i s o n l y n e c e s s a r y t o i n t e r n ( u s i n g L i s p j a r g o n ) a word when i t i s c r e a t e d , e i t h e r by a p r i m i t i v e f u n c t i o n , o r by r e a d i n g i t i n . As an example o f t h e use o f atoms, s u p p o s e t h a t we had e x e c u t e d MAKE "GHOTI" " F I S H " TO GHOTI j O PRINT "PSHAWS END The r e s u l t i n g d a t a s t r u c t u r e i s shown i n f i g u r e 4 - 2 . THE O&LIST A 5 C Y L #f ?PCIHT P a r t 4 System D e s c r i p t i o n 62 4.2 S t o r a g e Management { A l l t h e r i v e r s r a n i n t o t h e s e a ; y e t t h e s e a i s not f o i l . — E c c l e s i a s t e s } The s t o r a g e management p r o b l e m s o f a l i s t p r o c e s s i n g s y s t e m s u c h a s Logo a r e p r o b a b l y t h e most i m p o r t a n t o n e s . I a t t e m p t e d t o b u i l d a s t o r a g e management s y s t e m which would l e t me f o r g e t a b o u t t h e s e p r o b l e m s when i m p l e m e n t i n g t h e r e s t c f t h e s y s t e m . I have had somewhat mixed r e s u l t s . The r e s u l t i n g s y s t e m was s o c o n v e n i e n t t o use t h a t I went a b o u t b l i t h e l y c r e a t i n g nodes w i t h o u t any c a r e as t o whether t h e g a r b a g e c o l l e c t o r c o u l d h a n d l e ( o r e v e n know a b o u t ) them. The b a s i c s t r a t e g y w h i c h I f o l l o w e d was c o n s t r a i n e d by t h e f o l l o w i n g f a c t o r s : • s i n c e I wanted t o be a b l e t o p u t t h e s y s t e m o n t o a s m a l l c o m p u t e r , I c o u l d n o t a f f o r d a •copy* s t y l e o f g a r b a g e c o l l e c t i o n s u c h as t h a t o f [HANS69 ] . • I d i d n o t wish t o worry a b o u t p a g i n g p r o b l e m s , s i n c e t h e a v e r a g e Logo d a t a s t r u c t u r e i s v e r y s m a l l . The r e s u l t i n g s t o r a g e management s y s t e m has t h e f o l l o w i n g c h a r a c t e r i s t i c s : • node s t o r a g e ( t h e "heap") i s d i v i d e d up i n t o p a g e s ; a l l t h e p a ges a r e o f t h e same s i z e ( f o r any r e a s o n a b l e e f f i c i e n c y , t h e p a g e s i z e must be a power o f 2 ) . m t h e programmer d e f i n e s e a c h t y p e o f node he i s g o i n g t o P a r t 4 System D e s c r i p t i o n 63 use t o t h e s t o r a g e manager. Each t y p e o f node i s o f f i x e d s i z e . The words o f a node may c o n t a i n e i t h e r p o i n t e r s t c o t h e r nodes ( r e f e r e n c e s ) o r o t h e r d a t a , fill n odes o f a g i v e n t y p e c o n t a i n t h e same number o f r e f e r e n c e s — i n t h e node, a l l t h e r e f e r e n c e s p r e c e d e t h e o t h e r d a t a . • a l l o f t h e nodes on a g i v e n page a r e o f t h e same t y p e . I n o r d e r t o e m p h a s i z e t h e i n d e p e n d e n c e o f t h e s t o r a g e management p a c k a g e f r o m t h e r e m a i n d e r o f t h e s y s t e m , t h e f o l l o w i n g p a r a g r a p h s p r e t e n d t h a t t h e s t o r a g e manager i s o f g e n e r a l use, and o u t l i n e how t h e package i s u s e d . The programmer d e f i n e s e a c h o f h i s node t y p e s by a c a l l i n g a p r o c e d u r e w i t h a u n i q u e i n t e g e r code which i d e n t i f i e s t h e p a r t i c u l a r t y p e , and two l e n g t h s : t h e l e n g t h c f t h e node, and t h e number o f r e f e r e n c e s . T h i s p r o c e d u r e i n i t i a l i s e s c e r t a i n t a b l e e n t r i e s . A t any t i m e a f t e r t h i s i n i t i a l i s a t i o n c a l l , t h e programmer may c r e a t e a new node o f a s p e c i f i e d t y p e by c a l l i n g t h e p r o c e d u r e *new». T h i s p r o c e d u r e i s g i v e n a t y p e c o d e : i t does a n y t h i n g n e c e s s a r y ( i n c l u d i n g i f n e c e s s a r y a g a r b a g e c o l l e c t i o n ) t o a l l o c a t e a s p e c i f i e d node. In g e n e r a l , t h e programmer i s not e n c o u r a g e d t c f r e e n o d e s . T h e r e i s a p r o c e d u r e p r o v i d e d t o do s o ; however, t h e programmer may d e s t r o y a node t o which a n o t h e r node s t i l l p o i n t s . The recommended way t o r e c l a i m d a t a i s by u s i n g t h e g a r b a g e c o l l e c t o r . T h i s r o u t i n e f o l l o w s a l l p o i n t e r s i n t o t h e node a r e a , m a r k i n g a l l nodes which c a n be r e a c h e d f r o m one o f P a r t 4 System D e s c r i p t i o n 64 t h e s e p o i n t e r s . I t t h e n p r o c e e d s t o f r e e a l l unmarked n o d e s , s i n c e t h e s e unmarked nodes c a n n o t c u r r e n t l y be u s e d . A l l f r e e d nodes a r e p l a c e d o n t o a " f r e e l i s t " , c f which t h e r e i s one p e r page. T h e r e f o r e , a l l t h a t 'new' has t o do i s t o go t o a page c o n t a i n i n g t h e r i g h t k i n d o f n o d e s , and remove one. P r i n t names a r e c o l l e c t e d i n a d i f f e r e n t way: s i n c e t h e y a r e v a r i a b l e i n l e n g t h , one c a n n o t s i m p l y use a f r e e l i s t a p p r o a c h — f r a g m e n t a t i o n would r e s u l t , i n s t e a d , e a c h p r i n t name has a back l i n k t o i t s atomhead. Then one can l i n e a r l y s c a n t h e p r i n t n a m e s — f o r e a c h p r i n t name, one c h e c k s t o s e e whether i t s atomhead i s marked. I f s o , one s i m p l y moves t h e s t r i n g t o t h e v a l i d s t r i n g a r e a , m o d i f y i n g t h e atomhead a p p r o p r i a t e l y . O t h e r w i s e , t h e s t r i n g c a n s i m p l y be i g n o r e d . T h i s a p p r o a c h i s t a k e n f r o m [ F E 0 H 7 1 ] . T h e r e i s one l a s t r e f i n e m e n t we c a n make: t h e r e i s a l a r g e c l a s s o f words which a p p e a r f o r a w h i l e , b u t a r e t h e n u s e l e s s . F o r ex a m p l e , i f we r e a d i n t h e atom "FOO", o p e r a t e upon i t f o r a w h i l e , and t h e n f o r g e t a b o u t i t , we have FOO f o r e v e r , s i n c e i t i s p o i n t e d t o by t h e O b l i s t . However, i f we have f o r g o t t e n a b o u t i t , we might a s w e l l r e c l a i m i t s s t o r a g e . T h e r e f o r e , d u r i n g e a c h c o l l e c t i o n , t h e g a r b a g e c o l l e c t o r e x a m i n e s e a c h atom; i f an atom i s " t r u l y w o r t h l e s s " , i n t h a t i t i s n e i t h e r marked, n o r t h e name o f some T h i n g , n o r t h e name o f a f u n c t i o n , i t i s d e l e t e d . T h e r e i s n o t h i n g v e r y s t a r t l i n g a b o u t t h i s whole d e s i g n — i t seems t o have been t h e way t h e o r i g i n a l L i s p i m p l e m e n t a t i o n was done. The r e a s o n s I c h o s e i t a r e t h a t i t i s v e r y s i m p l e t o P a r t 4 System D e s c r i p t i o n 65 p r o g r a m , and t h a t t h e a l l o c a t i o n o f a node i s r e l a t i v e l y f a s t , s i n c e i n most c a s e s a l l t h a t needs t o be done i s t c pop a node o f f a f r e e l i s t . The page i d e a came from two d i r e c t i o n s : t h e A l g o l W s y s t e m [BAUE68] u s e s a v e r y s i m i l a r d e s i g n ; a l s o , a c o n v e r s a t i o n w i t h W a l l a c e F e u r z e i g and G eorge L u k a s c o n v i n c e d me t h a t e v e r y t h i n g s h o u l d be i n t h e heap. T h i s meant t h a t there, were t o be a r e l a t i v e l y l a r g e number ( c u r r e n t l y 7) c f d i f f e r e n t node t y p e s , w h i c h meant t h a t e i t h e r one had t o have 7 d i f f e r e n t c o r e a r e a s , o r t h a t t h e g a r b a g e c o l l e c t i o n p r o b l e m would become messy. The page s o l u t i o n s o l v e s t h i s p r o b l e m , a l l o w i n g g u i t e a wide v a r i a t i o n s i n t h e amount c f s p a c e f o r e a c h node t y p e , let a n o t h e r r e a s o n f o r d i v i d i n g s t o r a g e i n t o p a g e s came f r o m t h e f a c i l i t y t h a t some o p e r a t i n g s y s t e m s have f o r a l l o c a t i n g s t o r e d y n a m i c a l l y . W h i l e t h e c u r r e n t s t o r a g e manager assumes t h a t t h e pages a r e c o n t i g u o u s i n s t o r e , o n l y a s m a l l number o f c h a n g e s need t o be made t o a l l o w pages t o be a l l o c a t e d d y n a m i c a l l y . T h i s f e a t u r e a l l o w s much more f l e x i b i l i t y t h a n t h e use o f s e p a r a t e a r r a y s f o r t h e v a r i o u s t y p e s o f nodes. See f i g u r e 4-3 f o r t h e a r r a n g e m e n t o f page t a b l e s . Cavr^nt t y e o\ nodes Record Tft.t\e P a r t 4 System D e s c r i p t i o n 67 4.3 The P a r s e r { find I c o p i e d a l l t h e l e t t e r s i n a b i g r o u n d hand! — W.S. G i l b e r t , H.M.S. P i n a f o r e } T h e r e r e a l l y i s n ' t much t o s a y a b o u t t h e p a r s e r . I t o p e r a t e s i n two p a s s e s : t h e f i r s t i s e s s e n t i a l l y a l e x i c a l s c a n n e r , which b u i l d s l i s t s t r u c t u r e f r o m t h e s t r i n g o f c h a r a c t e r s which t h e u s e r e n t e r s . The s e c o n d p a s s g o e s o v e r t h e l i s t s t r u c t u r e , c h e c k i n g t h a t n o i s e words and p a r e n t h e s e s a r e c o r r e c t l y u s e d . T h i s p a s s w i l l l a t e r be e x t e n d e d t o h a n d l e i n f i x o p e r a t o r s . 4.4 The I n t e r p r e t e r The b a s i c o b j e c t s w i t h w h i c h t h e i n t e r p r e t e r i t s e l f o p e r a t e s a r e t h e l i n e b e i n g i n t e r p r e t e d , and t h e push-down s t a c k . The s t a c k c o n t a i n s a chunk o f d a t a (a frame) f o r e v e r y p e n d i n g f u n c t i o n c a l l . E a c h f r a m e c o n t a i n s t h e f o l l o w i n g i n f o r m a t i o n : • t h e name o f t h e f u n c t i o n t o be c a l l e d . • t h e a r g u m e n t s o f t h e f u n c t i o n . • v a r i o u s g l o b a l v a r i a b l e s which must be s a v e d , s u c h as t h e p o s i t i o n w i t h i n t h e c u r r e n t l i n e , t h e l i n e b e i n g e x e c u t e d , { I t r e v o l t s me, b u t I do i t ! — W.S. G i l b e r t , The Mikado } P a r t 4 System D e s c r i p t i o n 68 and t h e t r u t h f l a g . S i n c e t h e i n t e r p r e t e r s c a n s a l i n e f r o m l e f t t o r i g h t , i t s e e s t h e f u n c t i o n name b e f o r e i t s e e s t h e a r g u m e n t s . T h e r e f o r e , on s e e i n g a new f u n c t i o n name, t h e i n t e r p r e t e r b u i l d s a new fram e f o r t h e f u n c t i o n . As e a c h argument i s s c a n n e d , i t i s a d d e d t o t h e f r a m e . F i n a l l y , when a l l t h e i n p u t s have been e v a l u a t e d (the i n t e r p r e t e r , o f c o u r s e , knows how many i n p u t s e a c h f u n c t i o n i s e x p e c t i n g ) , t h e f u n c t i o n u n d e r c o n s i d e r a t i o n i s c a l l e d . I f i t i s a p r i m i t i v e , i t i s c a l l e d r i g h t away; i f i t i s a u s e r p r o c e d u r e , t h e i n t e r p r e t e r s t o r e s i t s g l o b a l v a r i a b l e s away i n t h e new f r a m e , and c h a n g e s them t o make i t a p p e a r t h a t i t i s now e x e c u t i n g t h e c a l l e d f u n c t i o n . At t h i s t i m e , l e t ' s l o o k a t an example: TO DOBLE zjz. TO OUTPUT SUM :Xz AND zJl END PRINT LAST OF DOBLE OF 34 The f o l l o w i n g s e g u e n c e happens: • we s t a r t o f f by e n c o u n t e r i n g PRINT. S i n c e t h i s i s a f u n c t i o n name, we b u i l d a new s t a c k f r a m e . • n e x t , we e n c o u n t e r LAST. Be b u i l d a new fram e f o r i t . • OF i s a n o i s e w o r d—we i g n o r e i t . • DOBLE i s a f u n c t i o n name; t h e r e f o r e , we b u i l d y e t a n o t h e r f r a m e . • 34 i s a datum. He add i t t o t h e c u r r e n t s t a c k frame (the a r g u m e n t s f o r DOBLE). • now, s e e i n g t h a t DOBLE t a k e s one i n p u t , we c a l l i t , by c h a n g i n g o u r a t t e n t i o n t o t h e d e f i n i t i o n o f DOBLE. B u t f i r s t , we s e t X t o 34. • we s t a r t e x e c u t i n g t h e f i r s t l i n e o f t h e f u n c t i o n : l i n e 1 0 . • OUTPUT i s a f u n c t i o n , s o we c r e a t e a n o t h e r s t a c k frame f o r i t . • SUM c a u s e s a n o t h e r s t a c k f r a m e t o be c r e a t e d . • :X: i s a v a r i a b l e ; t h e r e f o r e , we g e t i t s T h i n g , 34, and P a r t 4 System D e s c r i p t i o n 69 p l a c e i t on t h e s t a c k . • we s e e t h a t we have n o t y e t g o t enough i n p u t s f o r SUM. T h e r e f o r e , we do n o t c a l l a n y t h i n g . • we i g n o r e t h e n o i s e word^ AND. • we e v a l u a t e :X: a g a i n , p u t t i n g i t s v a l u e o n t o t h e s t a c k . • now we have a l l o f SUM ,s i n p u t s — w e c a n c a l l SUM. I t r e t u r n s r i g h t away, w i t h a new v a l u e - 6 8 . He put t h i s v a l u e o n t o t h e s t a c k . a now we n o t i c e t h a t we have s a t i s f i e d OUTPUT•s r e g u i r e m e n t s f o r i n p u t s . He c a l l i t ; i t i m m e d i a t e l y f o r c e s a r e t u r n from DOBLE. Now we t a k e OUTPUT'S i n p u t , and p l a c e i t on t o p o f t h e c u r r e n t s t a c k f r a m e , which i s t h e f r a m e f o r LAST. • now we have s a t i s f i e d LAST. He c a l l i t , r e c e i v i n g i m m e d i a t e l y i t s o u t p u t - 8 . • PRINT has now r e c e i v e d i t s i n p u t . We c a l l i t w i t h 8; i t p r i n t s o u t 8, and r e t u r n s , • t h e r e i s n o t h i n g more t o do, s o t h e i n t e r p r e t e r r e t u r n s t o g e t t h e n e x t command. The i n t e r p r e t a t i o n a l g o r i t h m seems t o have come from t h i n a i r ; y e t a l i t t l e t h o u g h t s h o u l d c o n v i n c e t h e r e a d e r t h a t i t i s e x a c t l y t h e a l g o r i t h m w h i c h one would use when e x p l a i n i n g how Logo works. The o n l y d i f f e r e n c e i s t h a t one would n o r m a l l y s a y "and when you c a l l a u s e r d e f i n e d f u n c t i o n , t h e i n t e r p r e t e r c a l l s i t s e l f " . However, i t i s o b v i o u s t h a t a r e c u r s i v e i m p l e m e n t a t i o n o f t h e i n t e r p r e t e r would consume a g r e a t d e a l o f s t o r a g e . E v e n worse, i f t h e u s e r were t o e x e c u t e a p r o c e d u r e s u c h a s TO OROAN 1 0 GROAN END The f i r s t t h i n g t o happen would be t h a t t h e i n t e r p r e t e r wouia go i n t o an i n f i n i t e r e c u r s i o n l o o p . E v e n t u a l l y t h e BCPL s t a c k (which i s u s e d t o s t o r e b o o k k e e p i n g i n f o r m a t i o n a b o u t e a c h BCPL f u n c t i o n c a l l ) would o v e r f l o w , and, s i n c e BCPL d o e s n ' t c h e c k f o r t h i s u n f o r t u n a t e o c c u r r e n c e , a program f a u l t would o c c u r . T h e r e f o r e ^ we must make o u r i n t e r p r e t e r i t e r a t e — a non-t r i v i a l t a s k f o r s o m e t h i n g which i s so e a s y t o dc r e c u r s i v e l y . P a r t U System D e s c r i p t i o n 70 U. 5 V a r i a b l e B i n d i n g So f a r , we have g l o s s e d o v e r what happens t o t h e names c f t h e i n p u t s o f a p r o c e d u r e . O b v i o u s l y , one must s a v e t h e p r e v i o u s v a l u e s o f t h e i n p u t names: f o r example, i n o u r DOBLE example, we may have had an X somewhere e l s e ; we would be g r e a t l y d i s t r e s s e d i f t h a t X were o v e r w r i t t e n d u r i n g a c a l l t o DOBLE. T h e r e f o r e , when i t c a l l s a p r o c e d u r e BCLogo s a v e s t h e p r e v i o u s v a l u e o f t h e v a r i a b l e on t h e s t a c k , and s e t s t h e T h i n g o f t h e v a r i a b l e t o t h e s p e c i f i e d i n p u t . When t h e p r o c e d u r e r e t u r n s , t h e whole p r o c e s s i s r e v e r s e d — X i s r e s t o r e d t o i t s i n i t i a l v a l u e . T h i s t y p e o f p r o c e s s i s c a l l e d " s h a l l o w b i n d i n g " . The p o i n t i s t h a t t h e v a l u e o f a v a r i a b l e V i s a l w a y s t h e T h i n g o f V. One n e v e r l o o k s on t h e s t a c k f o r t h e v a l u e o f t h e v a r i a b l e — i t i s a l w a y s i n t h e T h i n g c e l l . W h i l e t h i s scheme i s t h e most o b v i o u s — i t i s used i n s e v e r a l L i s p i m p l e m e n t a t i o n s ( f o r example, MACLisp [WHIT70] and L i s p / K T S [ WILC73 ]) — i t i s n o t t h e most g e n e r a l . C o n s i d e r f o r example a w o r l d i n w h i c h we had two p r o c e s s e s , each w i t h i t s own p r i v a t e V — f o r example, two i n d e p e n d e n t r o b o t s e a c h f i g h t i n g i t s way o u t o f a l a b y r i n t h . S i n c e e a c h r o b o t has h i s own v a l u e o f V, we c a n * t v e r y w e l l u s e t h e T h i n g c e l l t o s t o r e t h e v a l u e s . The g e n e r a l l y a c c e p t e d way o f h a n d l i n g t h i s s o r t o f s i t u a t i o n i s t o u s e a t r e e o f s t a c k s [BOBH72], a l w a y s s t o r i n g t h e v a l u e c f a v a r i a b l e on t h e s t a c k . T h i s method, c a l l e d "deep b i n d i n g " i s f a r more g e n e r a l , a t t h e c o s t o f a s m a l l l o s s i n e f f i c i e n c y . I c h o s e t h e s h a l l o w b i n d i n g method n o t b e c a u s e o f i t s s m a l l g a i n i n e f f i c i e n c y , b ut b e c a u s e Logo a t p r e s e n t does not need deep P a r t 4 System D e s c r i p t i o n 71 b i n d i n g . I f we e v e r want t o a l l o w p a r a l l e l i s m o r b a c k t r a c k i n g , o n l y s m a l l c h a n g e s t o BCLogo w i l l be needed i n o r d e r t o i m p l e m e n t deep b i n d i n g . U.6 The P r i m i t i v e F u n c t i o n s S i n c e one o f t h e main g o a l s o f t h i s p r o j e c t has been t o c o n s t r u c t an e a s i l y e x t e n d a b l e s y s t e m , a g r e a t d e a l o f e f f o r t has been s p e n t i n making t h e w r i t i n g o f p r i m i t i v e f u n c t i o n s v e r y e a s y . In p a r t i c u l a r , i t i s n o t n e c e s s a r y t o r e c o m p i l e t h e s y s t e m s i m p l y t o add a new f u n c t i o n , A l l t h a t i s n e c e s s a r y i s c o m p i l a t i o n o f t h e f u n c t i o n ( a l o n g w i t h a g i g a n t i c f i l e o f d e c l a r a t i o n s ) , l o a d i n g ( o r l i n k - e d i t i n g ) t h e o b j e c t code f o r t h e f u n c t i o n w i t h t h e r e s t o f t h e s y s t e m , and t h e n making t h e a p p r o p r i a t e e n t r i e s i n t h e i n i t i a l i s a t i o n f i l e . T h i s means, i n p a r t i c u l a r , t h a t new t y p e s o f g r a p h i c s s u p p o r t , o r f i l e management, o r a n y t h i n g e l s e , may be added a t any p o i n t . A l l t h a t i s n e c e s s a r y i s t h a t t h e f u n c t i o n programmer have a w o r k i n g knowledge o f BCPL, p l u s a m i n i m a l u n d e r s t a n d i n g o f t h e s y s t e m . As a t e s t o f t h e e a s e o f a d d i n g new f u n c t i o n s , I s p e n t a b o u t t e n m i n u t e s e x p l a i n i n g t h e method o f a d d i n g new f u n c t i o n s t o a n o t h e r s t u d e n t i n o u r d e p a r t m e n t , P e t e r V a n d e nBosch, who t h e n w r o t e some t u r t l e f u n c t i o n s . He had no p r o b l e m a d d i n g t h e s e f u n c t i o n s t o t h e s y s t e m . The r u l e s t h a t a p r i m i t i v e f u n c t i o n must f o l l o w a r e r e m a r k a b l y s i m p l e : P a r t 4 System D e s c r i p t i o n 72 • a l l p r i m i t i v e f u n c t i o n s a r e BCPI f u n c t i o n s ( i . e . , t h e y a l w a y s r e t u r n a v a l u e ) . They a l w a y s r e c e i v e one i n p u t , which i s s e t t o t h e number o f i n p u t s s p e c i f i e d by t h e u s e r i n t h i s c a l l . ( S i n c e most u s e r f u n c t i o n s w i l l t a k e a f i x e d number o f a r g u m e n t s , i n g e n e r a l t h i s p a r a m e t e r may be i g n o r e d ) . a t h e i n p u t s t o t h e f u n c t i o n a r e i n t h e a r r a y ARG. The f i r s t i s i n ARG!1, t h e s e c o n d i n ARG!2, and so on. a when t h e f u n c t i o n has f i n i s h e d i t s o p e r a t i o n , i t a l w a y s r e t u r n s s o m e t h i n g ; i f i t i s an o p e r a t i o n , i t r e t u r n s t h e r e s u l t i n g v a l u e . I f i t i s a command, i t r e t u r n s t h e c o n s t a n t NOTHING. a a number o f u s e f u l r o u t i n e s a r e p r o v i d e d f o r t h e programmer's u s e : INTERN (BDFF) t h i s p r o c e d u r e t a k e s a BCPL unpacked s t r i n g (one i n which word 0 c o n t a i n s t h e number o f c h a r a c t e r s , and t h e r e m a i n i n g words c o n t a i n t h e c h a r a c t e r s ) . I t r e t u r n s a p o i n t e r t o t h e atomhead f o r t h e Logo v e r s i o n o f t h e s t r i n g . P a r t 4 System D e s c r i p t i o n 73 ITOS (NUM) t h i s f u n c t i o n t a k e s a b i n a r y i n t e g e r , and r e t u r n s a p o i n t e r t o a Logo atom c o r r e s p o n d i n g t o t h e i n t e g e r . STOI (ATOH) g i v e n a L o g o atom, t h i s p r o c e d u r e r e t u r n s t h e b i n a r y r e p r e s e n t a t i o n o f t h e i n p u t . I f t h e atom c o n t a i n s n o n - n u m e r i c c h a r a c t e r s , i t w i l l g e n e r a t e an e r r o r . CONS (A,B) g i v e n two Logo p o i n t e r s , t h i s f u n c t i o n w i l l r e t u r n a p o i n t e r t o a new c e l l . C a r o f which i s A, and Cdr o f which i s B. ERROR (A,X,Y,Z,W,...) t h i s s u p e r amazing f u n c t i o n p r i n t s e r r o r messages. A i s an i n t e g e r c o d e i n d i c a t i n g w hich e r r o r message from t h e i n i t i a l i s a t i o n f i l e i s t o be d i s p l a y e d . X, Y, and t h e o t h e r p a r a m e t e r s a r e d a t a w h i c h a r e i n s e r t e d i n t o t h e e r r o r message. T h e s e p a r a m e t e r s may be any BCPL d a t a ; t h e y may a l s o be p o i n t e r s t o atoms o r c e l l s . P l e a s e s e e t h e d e s c r i p t i o n o f t h e i n i t i a l i s a t i o n f i l e f o r more d e t a i l s . As an example, a l i s t i n g o f t h e p r i m i t i v e f o r * WORD* f o l l o w s . Part 4 System D e s c r i p t i o n 74 GLOBAL $( WORD: FT+71 $) LET WORD (I) = VALOF $( LET V = VEC 255 // RESULTS ACCUMULATED HERE. AND U = VEC 255 // TEMPORARY. AND L = 0 // # CHARS ACCUMULATED SO FAR. FOR J = 1 TO I DO $( // CHECK EACH ARGUMENT. LET ARG = ARGS!J IF ARG = NULL THEN LOOP IF TYPE (ARG) =ATOHHEAD THEN ERROR(50, ARG) UNPACK (ARG, U) FOR K = 1 TO U!0 DO $( L := L+1 V!L := U!K *> *> V!0 := L RESULTIS INTERN (V) $) More examples may be found i n a forthcoming document on t u r t l e geometry [MANI73B ]. HaJ. I p i t i a l i s a t i o n BCLogo i s i n i t i a l i s e d by rea d i n g i n a f i l e of commands. These commands cause procedures to be d e f i n e d , e r r o r messages to be s t o r e d , i n i t i a l i s a t i o n procedures to be c a l l e d , and messages to be typed to the user, as well as s e t t i n g v a r i o u s o p t i o n s , such as whether a d r i b b l e f i l e (a f i l e i n which a r e c o r d of the complete d i a l o g u e i s s t o r e d , f o r l a t e r p e r u s a l by a teacher) i s to be kept, the amount of space to be a l l o c a t e d , and other parameters. T h i s approach was chosen f o r two reasons: f i r s t , i t means t h a t o n l y the i n i t i a l i s a t i o n r o u t i n e need stay i n memory P a r t 4 System D e s c r i p t i o n 75 t h r o u g h o u t e x e c u t i o n ; t h e r e f o r e , t h e d a t a used f o r i n i t i a l i s a t i o n d i s a p p e a r r i g h t a f t e r t h e y a r e u s e d . N a t u r a l l y , t h e r e i s a d i s a d v a n t a g e : t h e r e i s an e x t r a f i l e o p e n i n g and c l o s i n g o p e r a t i o n , p l u s a number o f i n p u t o p e r a t i o n s , f o r t h e i n i t i a l i s a t i o n f i l e . T h i s means t h a t t h e s y s t e m t a k e s a b i t l o n g e r t o l o a d t h a n i t would i f t h e i n i t i a l i s a t i o n d a t a were b u i l t r i g h t i n t o t h e s y s t e m . However, on t h e 360/67, o n l y a b o u t a s e c o n d o f CPO t i m e i s i n v o l v e d — a n amount I h a r d l y f e e l w o r t h w o r r y i n g a b o u t . The i n i t i a l i s a t i o n d a t a i s i n t h e f o r m o f l i n e s , each o f which s t a r t s w i t h a command l e t t e r , f o l l o w e d by d a t a f o r t h a t command. The a v a i l a b l e commands a r e : • C ( c a l l ) t h i s command t a k e s one p a r a m e t e r , t h e i n d e x i n t o t h e g l o b a l v e c t o r o f a p r o c e d u r e which i s t o be c a l l e d . * T h i s command l e t s p a c k a g e s o f f u n c t i o n s (such a s t h e t u r t l e f u n c t i o n s ) p r o v i d e an i n i t i a l i s a t i o n e n t r y p o i n t . • D ( d e f i n e ) T h i s command t a k e s f o u r , c o u n t them, f o u r p a r a m e t e r s . The f i r s t o f t h e s e i s t h e name o f a f u n c t i o n t o be d e f i n e d . The s e c o n d i s an i n d e x i n t o t h e g l o b a l v e c t o r f o r t h e p r o c e d u r e t o be c a l l e d . Next comes t h e number o f ar g u m e n t s f o r t h e f u n c t i o n ; a v a r i a d i c f u n c t i o n s u c h a s SENTENCES i s f l a g g e d by c o d i n g 99 h e r e . The l a s t p a r a m e t e r i s u s u a l l y 0; i t i n d i c a t e s whether t h e f u n c t i o n i s • n o r m a l * ( i n t h e s e n s e m e n t i o n e d when d i s c u s s i n g t h e i n t e r p r e t e r ) . F o r an »abnormal* f u n c t i o n , c o d e a 1. • E ( e r r o r ) d e f i n e s an e r r o r message. I t t a k e s two p a r a m e t e r s : t h e f i r s t i s t h e number o f t h e e r r o r message, and t h e s e c o n d i s t h e t e x t t o be p r i n t e d o u t when t h a t e r r o r message i s p r o d u c e d . The t e x t may have embedded e d i t i n g c o d e s , f l a g g e d by a p r e c e d i n g p e r c e n t (%) s i g n , a s f o l l o w s : % p r i n t a p e r c e n t s i g n . C p r i n t t h e n e x t argument a s a c h a r a c t e r . In p r i n t t h e n e x t argument as an i n t e g e r i n a f i e l d o f w i d t h n. N p r i n t t h e n e x t argument as an i n t e g e r , i n minimum w i d t h . P p r i n t t h e n e x t argument a s a Logo datum (Atom o r C e l l ) . S p r i n t t h e argument a s a BCPL s t r i n g . • 0 ( o p t i o n ) s e t s t h e v a r i o u s o p t i o n f l a g s from t h e r e m a i n d e r o f t h e l i n e , a s s p e c i f i e d by c h a r a c t e r s i n t h e l i n e . The f o l l o w i n g c h a r a c t e r s c u r r e n t l y do s o m e t h i n g D e n a b l e s d r i b b l e f i l e . H i n d i c a t e s t h a t you a r e c r e a t i n g a "new s y s t e m " , and want some a d d i t i o n a l r e a s s u r i n g i n f o r m a t i o n d u r i n g i n i t i a l i s a t i o n . You w i l l t h e n g e t a summary o f hew t h e w o r k s p a c e was s u b d i v i d e d , and a few e x t r a t i m i n g r e s u l t s . G c a u s e s a message d u r i n g e a c h g a r b a g e c o l l e c t i o n ; o n l y o f i n t e r e s t t o s y s t e m s f r e a k s . • X ( e x i t ) c a u s e s i n i t i a l i s a t i o n t o t e r m i n a t e , and r e g u l a r p r o c e s s i n g t o b e g i n . T h i s method o f i n i t i a l i s a t i o n (by r e a d i n g commands from a f i l e ) i s g u i t e c o n v e n i e n t , a l t h o u g h , o f c o u r s e , h a r d l y n e w — prog r a m s have been r e a d i n g i n i n i t i a l i s a t i o n d a t a f o r y e a r s . P a r t U System D e s c r i p t i o n 77 The e x a c t f o r m o f t h e i n p u t comes from t h o u g h t s c n how i n i t i a l i s a t i o n o u ght t o be d o n e — t h o u g h t s i n s p i r e d by t h e manner i n w h i c h s y n t a x - d i r e c t e d c o m p i l e r s r e a d i n t h e d e s c r i p t i o n s o f t h e l a n g u a g e s which t h e y w i l l c o m p i l e t o d a y . P a r t 5 Machine I n d e p e n d e n c e 78 I : 1 I t | PAST 5 MACHINE INDEPENDENCE 1 I I I I i , i 5.1 BCPL As one o f t h e p r i m e a i m s o f the p r o j e c t was t h e p r o d u c t i o n o f a m a c h i n e - i n d e p e n d e n t s y s t e m , i t i s n e c e s s a r y t o e v a l u a t e how w e l l BCPL s e r v e d t h i s g o a l . BCPL, a l t h o u g h a sem programming l a n g u a g e » y s t i s o l a t e s t h e programmer f r o m t h e machine and t h e h o s t o p e r a t i n g s y s t e m ; t h e o n l y e x c e p t i o n i s t h a t a l i b r a r y o f m a c h i n e - d e p e n d e n t p r o c e d u r e s i s p r o v i d e d f o r i n p u t / o u t p u t and o t h e r s y s t e m s t a s k s . The o n l y machine d e p e n d e n t f e a t u r e s o f t h e l a n g u a g e i t s e l f a r e t h o s e o f d a t a f o r m a t and word s i z e , where, o b v i o u s l y , a program d e p e n d i n g upon t h e two's complement a r i t h m e t i c o f t h e 360 w i l l f a i l u t t e r l y when r u n on a one's complement machine s u c h as t h e U n i v a c 1108. I n o r d e r t o comply w i t h t h e l e a s t common d e n o m i n a t o r , I have p r e t e n d e d t h a t a word was 16 b i t s w ide. W h i l e a few masks assume a 32 b i t word, t h e r e i s nowhere an a t t e m p t t o s q u e e z e more t h a n 16 b i t s w orth o f i n f o r m a t i o n i n t o one word. ( A d d r e s s e s a p p e a r t o be an e x c e p t i o n , b u t on a l m o s t a l l c o m p u t e r s , a n a d d r e s s f i t s i n t o one w o r d ) . * a t l e a s t one o p e r a t i n g s y s t e m has been w r i t t e n i n i t [STOY72 P a r t 5 Machine I n d e p e n d e n c e 79 The o n l y e x c e p t i o n t o t h i s r u l e i s i n t h e g a r b a g e c o l l e c t o r , which assumes t h a t a word c a n h o l d an a d d r e s s p l u s one e x t r a b i t , which i s u s e d d u r i n g t h e m a r k i n g phase o f g a r b a g e c o l l e c t i o n . S i n c e some m i n i c o m p u t e r s need e v e r y b i t o f a word t o s t o r e an a d d r e s s ( f o r example, t h e PDP-11), one may have t o r e w r i t e t h e g a r b a g e c o l l e c t o r t o make use o f a b i t map, which c o n t a i n s one b i t f o r e v e r y word o f t h e w o rkspace. I n g e n e r a l , a c h i e v i n g machine i n d e p e n d e n c e means l o s i n g e f f i c i n c y ) . T h r e e s e p a r a t e i n e f f i c i e n c i e s show up: • s i n c e BCPL r u n s on a h y p o t h e t i c a l machine i n which s u c c e s s i v e word a d d r e s s e s d i f f e r by 1, a BCPL a d d r e s s i s a word a d d r e s s . On t h e o t h e r hand, a 360 machine a d d r e s s i s a b y t e a d d r e s s . T h i s means t h a t e v e r y t i m e we f o l l o w a p o i n t e r , we must c o n v e r t from one t o t h e o t h e r . Even t h o u g h the BCPL c o m p i l e r e m p l o y s an o p t i m i s a t i o n which c u t s down t h e e x c e s s o v e r h e a d t o two b y t e s o f s t o r a g e and l e s s t h a n one m i c r o s e c o n d , i t s t i l l a d ds up. • t h e most e f f i c i e n t way t o s t o r e s t r i n g s i s t c pack them f o u r (on t h e 360) t o a word. Y e t t h e o n l y m a c h i n e - i n d e p e n d e n t way t o p r o c e s s a s t r i n g i s t o s t o r e i t one c h a r a c t e r p e r word. T h i s means a g r e a t d e a l o f p a c k i n g and u n p a c k i n g , which i s t o t a l l y u n r e a s o n a b l e . One r e a s o n a b l e o p t i m i s a t i o n i s t o p r o v i d e an a s s e m b l e r v e r s i o n o f INTERN, the r o u t i n e which does most o f t h e c h a r a c t e r s t r i n g h a n d l i n g — t h e p a r s e r c o u l d a l s o be r e w r i t t e n i n a s s e m b l e r , b u t i t i s n o t c l e a r t h a t t h e s a v i n g s would be v e r y g r e a t from s u c h a r e w r i t i n g . P a r t 5 Machine independence 80 5.2 P u t t i n g BClogg On Another Machine I f BCLogo i s t r u l y machine independent, i t should he very easy to move from machine to machine. We s h a l l c o n s i d e r tvo s e p a r a t e v e r s i o n s of the problem—moving from o p e r a t i n g system t o o p e r a t i n g system, and then moving from machine to machine. The f o l l o w i n g s e c t i o n c o n s i d e r s the problem i n the a b s t r a c t . For f u l l d e t a i l s , the reader i s r e f e r r e d t o [MANI73]. 5 . 2 a j Operating Systems Changing o p e r a t i n g systems should be very easy. There are onl y a few p l a c e s i n the system which depend upon a p a r t i c u l a r o p e r a t i n g system. The only dependencies are those concerning f i l e s : the r o u t i n e s OPENINPUT, OPENODTPOT, and CLOSE w i t h i n the main segment of code may have to be r e w r i t t e n f o r each o p e r a t i n g system. Apart from t h i s , the only r e a l problem i s t h a t many o p e r a t i n g systems do not allow enough c o n t r o l over the such t h i n g s as a t t e n t i o n i n t e r r u p t s . I f i t i s d e s i r e d to run BCLogo under such an o p e r a t i n g system, i t w i l l not be p o s s i b l e f o r Logo t o c a t c h a t t e n t i o n i n t e r r u p t s . T h e r e f o r e , t r a n s p o r t i n g BCLogo from one o p e r a t i n g system to another on the same machine means r e w r i t i n g only a s m a l l amount of BCPL code, p l u s m o d i f i c a t i o n to the BCPL system to run on the new system. Bote t h a t i t i s not p o s s i b l e to run BCLogo on an P a r t 5 Machine I n d e p e n d e n c e 81 o p e r a t i n g s y s t e m which makes u n w a r r a n t e d demands, s u c h as r e q u i r i n g t h a t c e r t a i n r e g i s t e r s a l w a y s c o n t a i n a d d r e s s e s , o r t h a t a c e r t a i n r e g i s t e r a l w a y s p o i n t t o some a r e a . T h i s means, f o r example, t h a t BCLogo i s n o t o p e r a b l e under CALL/360. 5.2.2 C h a n g i n g M a c h i n e s The g r e a t e s t amount o f work i n moving f r o m machine t o machine i s c o n v e r t i n g BCPL t o r u n on t h e new machine. T h i s means t h a t t h e c o d e g e n e r a t o r o f t h e c o m p i l e r ( l e s s t h a n 1000 l i n e s o f code) must be r e w r i t t e n t o g e n e r a t e o b j e c t code f o r t h e d e s i r e d m a c h i n e . At t h i s p o i n t , a l l t h a t i s n e c e s s a r y i s r e c o m p i l a t i o n o f t h e BCLogo s y s t e m , t h u s g e n e r a t i n g o b j e c t c o d e f o r t h e new machine. P a r t 6 C o n c l u s i o n s 82 i — — — 1 I I | PART 6 CONCLUSIONS I I ! I I i ,.., _ ,,. -,_ j 6 . 1 Rough S p o t s a l t h o u g h a v e r y r e a s o n a b l e s y s t e m i s c u r r e n t l y r u n n i n g , i t s h o u l d be o b v i o u s t h a t BCLogo i s nowhere n e a r c o m p l e t i o n . T h e r e a r e a number o f r o u g h s p o t s — i n p a r t i c u l a r , some o f t h e e r r o r c h e c k i n g i s n o t q u i t e f o o l p r o o f . i N o n e t h e l e s s , I f e e l t h a t t h e b a s i c framework i s now p r e s e n t . The s y s t e m i s modu l a r enough t h a t a l a r g e number o f i n c r e m e n t a l c h a n g e s c a n be made w i t h o u t s i g n i f i c a n t l y c h a n g i n g t h e b a s i c s t r u c t u r e . S p e c i f i c a l l y , i n t h e n e a r f u t u r e , I i n t e n d t o r e w r i t e b o t h t h e s t o r a g e manager and t h e i n t e r p r e t e r , i n o r d e r t o c o r r e c t t h e e r r o r s m e n t i o n e d a b o v e , and t o change some o f t h e d a t a s t r u c t u r e s — n o t a b l y t h e s t a c k . T h e s e c h a n g e s s h o u l d be c o m p l e t e l y t r a n s p a r e n t t c t h e r e s t c f t h e s y s t e m . T h e r e i s one s i g n i f i c a n t p r o b l e m f o r which I c u r r e n t l y have no s o l u t i o n . I n o r d e r t o be machine i n d e p e n d e n t , we must use a l a n g u a g e s u c h a s BCPL, which d e l i b e r a t e l y s e t s o u t t o i s o l a t e t h e u s e r from t h e machine. Y e t t h i s i s o l a t i o n c o s t s a g r e a t d e a l , b o t h i n t h e e f f i c e n c y d e g r a d a t i o n m e ntioned i n t h e p r e v i o u s p a r t , and i n t h e o v e r h e a d o f wasted p r o c e d u r e c a l l s . F o r example, i f t h e Logo programmer i s s u e s a t u r t l e command. P a r t 6 C o n c l u s i o n s 83 t h e f o l l o w i n g s e g u e n c e o f c a l l s i s n e c e s s a r y : t h e Logo p r o c e d u r e c a l l s t h e BCPL t u r t l e p r i m i t i v e , which c a l l s an i n t e r f a c e module i n a s s e m b l e r , which c a l l s a F o r t r a n r o u t i n e , which c a l l s t h e s y s t e m p l o t r o u t i n e s . T h i s d e g r e e o f n e s t i n g seems t o me t o be a b i t e x c e s s i v e . R e g a r d i n g t h e use o f p o i n t e r s , I f e e l t h a t my s y s t e m s u f f e r s f r o m a p r o b l e m i n i t s d e s i g n f o r g a r b a g e c o l l e c t i o n . The p r o b l e m i s t h a t s i n c e g a r b a g e c o l l e c t i o n c a n o c c u r a t any t i m e , i t i s n e c c e s s a r y t o e n s u r e t h a t a l l p o i n t e r s i n t o t h e heap a r e a c c e s s i b l e t o t h e g a r b a g e c o l l e c t o r . But c o n s i d e r a r e c u r s i v e l i s t b u i l d i n g r o u t i n e : i t needs a number o f p o i n t e r s t o t h e l i s t t h a t i t i s m a n u f a c t u r i n g . N a t u r a l l y , t h e g a r b a g e c o l l e c t o r must know a b o u t t h e s e p o i n t e r s . Y e t , s i n c e t h e r o u t i n e i s r e c u r s i v e , i t i s n o t a d e g u a t e s i m p l y t o make t h e p o i n t e r s g l o b a l , s i n c e t h e r e i s one s e t o f p o i n t e r s f o r e a c h l e v e l o f t h e r o u t i n e . The o n l y r e a s o n a b l e s o l u t i o n t o t h i s p r o b l e m i s t o p u t t h e p o i n t e r s o n t o t h e s t a c k . My p r e s e n t s y s t e m d o e s n o t do t h i s . Part 6 C o n c l u s i o n s 84 6.2 F r i e n d l i n e s s So f a r , I have not been a b l e to do anything about making the system " f r i e n d l y " . There are a number of hypotheses one can frame about the f r i e n d l i n e s s of a system, such as: • a system i s f r i e n d l y i f i t can be anthropomcrphised by the user, g i v i n g him the i l l u s i o n t h a t he i s conducting a c o n v e r s a t i o n with a human being. Systems with t h i s property are E l i z a [HEIZ66 ] ( f o r 5 minutes or s o ) , and the INTEBLISP programmer's a s s i s t a n t [TEIT71] (to someone whose n a t i v e language i s L i s p ) . T h i s may be a very dangerous i l l u s i o n to promote. • a system i s f r i e n d l y i f i t behaves i m p e r s o n a l l y , thus not g i v i n g the user the f e e l i n g of a harsh c r i t i c who comments on each command (very o f t e n a d v e r s e l y ) . • a system i s f r i e n d l y i f i t does what the user means, net what he says [ T E I T 7 1 ] . • a system i s f r i e n d l y i f , when i t doesn't understand something, i t does not presume on the r e l a t i o n s h i p i t has b u i l t up with the user, c o n t e n t i n g i t s e l f with commenting cn the f a u l t ( s ) i t has observed. • a system i s f r i e n d l y i f i t immediately r e p o r t s e r r o r s i t has found. • a system i s f r i e n d l y i f i t waits to r e p o r t e r r o r s u n t i l the l a s t p o s s i b l e moment, commenting upon as many e r r o r s i n the command or program as i t can. • a system i s f r i e n d l y i f i t g i v e s only t e r s e messages, thus not f r u s t r a t i n g the user by making him wait f o r a long P a r t 6 C o n c l u s i o n s 85 message, t h e c o n t e n t s o f which he a l r e a d y knows. • a s y s t e m i s f r i e n d l y i f i t e x p l a i n s e a c h e r r o r t h o r o u g h l y , s o a s t o c o r r e c t a s many wrong i d e a s , d i p l o m a t i c a l l y , a s p o s s i b l e . • [ S E E L 7 3 ] a s y s t e m i s f r i e n d l y i f i t promotes t h e " g r o w t h " o f t h e u s e r ( i t e n c o u r a g e s l e a r n i n g a b o u t t h e u s e r ' s programming e n v i r o n m e n t and a b o u t h i m s e l f ) . Put a n o t h e r way, a s y s t e m i s f r i e n d l y i f i t c a r e s a b o u t t h e u s e r . The a s t u t e , o r a t l e a s t awake, r e a d e r w i l l have n o t i c e d some c o n t r a d i c t o r y t e n d e n c i e s among t h e h y p o t h e s e s . I would v e n t u r e t h a t t h e p e r c e i v e d p e r s o n a l i t y o f a computer program v a r i e s f r o m u s e r t o u s e r , and t h a t no one s y s t e m w i l l be f r i e n d l y t o e v e r y o n e . N e v e r t h e l e s s , I hope t h a t we can use BCLogo t o t e s t o u t t h e s e h y p o t h e s e s , and o t h e r s , i n t h e n e a r f u t u r e . 6.3 F u t u r e D e v e l o p m e n t s I n t h e n e a r f u t u r e , I hope t o add a number o f r e f i n e m e n t s t o t h e s y s t e m , i n c l u d i n g f l o a t i n g p o i n t a r i t h m e t i c and i n f i x o p e r a t o r s . N e i t h e r o f t h e s e f e a t u r e s i s o f a g r e a t d e a l c f w o r t h , s i n c e f l o a t i n g p o i n t a r i t h m e t i c may e a s i l y be i m p l e m e n t e d i n L o g o , s t o r i n g a r a t i o n a l number a s a s e n t e n c e , e i t h e r o f n u m e r a t o r a n d d e n o m i n a t o r , o r o f m a n t i s s a and e x p o n e n t . However, r a t i o n a l numbers add a g r e a t d e a l o f a p p e a l t o t h e l a n g u a g e f o r t h o s e who l i k e l a n g u a g e s s u c h a s B a s i c . I n f i x o p e r a t o r s have a b o u t t h e same u t i l i t y . The o n l y P a r t 6 C o n c l u s i o n s 86 r e a s o n one p u t s them i n i s t o c o n f o r m t o o u r p r e c o n c e p t i o n s a b o u t m a t h e m a t i c a l n o t a t i o n . Y e t i t i s n o t c l e a r t h a t c l u t t e r i n g t h e l a n g u a g e w i t h i n f i x a r i t h m e t i c does a n y t h i n g . P e r h a p s i t i s w o r t h w h i l e e n c o u r a g i n g c h i l d r e n , e s p e c i a l l y , t o w r i t e «SUB 1 2' r a t h e r t h a n *1+2»; a t l e a s t t h e f o r m e r n o t a t i o n makes c l e a r t h a t SOB i s a f u n c t i o n , n e v e r t h e l e s s , one must e v e n t u a l l y bow t o h i s t o r i c a l c o n v e n t i o n s Our o t h e r p l a n s a r e t o m a n u f a c t u r e a number o f BCLogo's f o r d i f f e r i n g m i n i - c o m p u t e r s . The hope i s t h a t Logo r u n n i n g i d e n t i c a l l y on d i f f e r i n g c o m p u t e r s w i l l be more c o m p e t i t i v e w i t h t h e p l e t h o r a o f BASIC'S c u r r e n t l y i n e x i s t e n c e . 87 B i b l i o g r a p h y [BARR63 ] B a r r o n , D.W., E t A l . , "The Main F e a t u r e s Of CPL." Computer J . , 6(1963) pp134-143. £ BA0E68 ] B a u e r , H, A l g o l W I m p l e m e n t a t i o n . Department Of Computer S c i e n c e , S t a n f o r d U n i v e r s i t y , 1968. [B0BR72] Bobrow, D.G., " R e q u i r e m e n t s F o r Advanced Programming Systems F o r L i s t P r o c e s s i n g . " C o m m u n i c a t i o n s Of The ACM 15(1972) pp618-627. [ D I J K 7 2 ] D i j k s t r a , E.W., "The Humble Programmer". C o m m u n i c a t i o n s Of The ACM 15(1972) pp859-866. [ F R E E 7 3 ] Freeman, P, " F u n c t i o n a l Program T e s t i n g And Machine A i d s . " Program T e s t Methods, P r e n t i c e - H a l l , 1973; Pp4 9-56. [ F E H I 6 9 ] F e n i c h e l , R.R., "A L i s p G a r b a g e C o l l e c t o r F o r v i r t u a l Memory Computer S y s t e m s . " C o m m u n i c a t i o n s Of The ACM 12(1969) pp611-612. [ F E 0 R 7 1 ] F e u r z e i g , W., E t A l . , C o n c e p t u a l Framework F o r B e r a n e k , And Newman, I n c , 1 Programming-Languages As A T e a c h i n g M a t h e m a t i c s . B o l t , 71. T e c h n i c a l R e p o r t 2165. [HANS69] Hansen, W.J., "Compact L i s t R e p r e s e n t a t i o n . " C o m m u n i c a t i o n s Of The ACM 12(1969) ppU99-507. [LUKA72] L u k a s , G., "Use Of The Logo Programming Language I n U n d e r g r a d u a t e I n s t r u c t i o n . " P r o c e e d i n g s Of The 1972 A n n u a l C o n f e r e n c e Of The A s s o c i a t i o n F o r Computing M a c h i n e r y , pp1130-1135. [MANI73A] M a n i s , V.S., "BCLogo I n t e r n a l S p e c i f i c a t i o n s . " D epartment Of Computer S c i e n c e , U n i v e r s i t y Of B.C. [MANI73B] M a n i s , V.S., " T u r t l e Geometry I n BCLogo." Department Of Computer S c i e n c e , U n i v e r s i t y Of B.C. 88 [NAUR63] Naur, P, E d . , " R e v i s e d R e p o r t On The a l g o r i t h m i c Language A l g o l 60." C o m m u n i c a t i o n s Of The ACM 6(1963) pp1-17. [ P A P E 7 1 ] P a p e r t , S., and C. Solomon, "Twenty T h i n g s To Do With A Computer." MIT A r t i f i c i a l I n t e l l i g e n c e L a b o r a t o r y , Logo Memo 3, 1971. [ P A P E 7 2 ] P a p e r t , S., "Making A Theorem F o r A C h i l d . " P r o c e e d i n g s Of The 1972 A n n u a l C o n f e r e n c e Of The A s s o c i a t i o n F o r C o m p u t i n g M a c h i n e r y , pp345-3*»9. [ R I C H 6 9 ] R i c h a r d s , M., BCPL R e f e r e n c e Manual. U n i v e r s i t y M a t h e m a t i c a l L a b o r a t o r y , C a m b r i d g e U n i v e r s i t y , 1971. [ S E E L 7 3 ] S e e l e y , B.A.R., P r i v a t e C o m m u n i c a t i o n . [STOY72] S t o y , J . E . , and C. S t r a c h e y , O S 6 — a n E x p e r i m e n t a l O p e r a t i n g System F o r S m a l l C o m p u t e r s . " Computer J o u r n a l 15(1972) pp117-124, 195-203. [SWIN73] S w i n h e a r t , D., and R. S p r o u l l , SAIL R e f e r e n c e Manual. S t a n f o r d a r t i f i c i a l I n t e l l i g e n c e L a b o r a t o r y , 1973. [ T E I T 7 2 ] T e i t e l m a n , W, "Automated P r o g r a m m i n g — T h e Programmer's A s s i s t a n t . " P r o c e e d i n g s Of The 1972 F a l l J o i n t Computer C o n f e r e n c e , Pp917-921. [WEIN71] W e i n b e r g , G.M., P L / I : A Manual Of S t j l e . M c G r a w - H i l l , 1971. [WEIZ66] Weizenbaum, J . , " E L I Z A — A Computer Program F o r The S t u d y Of N a t u r a l Language C o m m u n i c a t i o n Between Man And M a c h i n e . " C o m m u n i c a t i o n s Of The ACM 9(1966) pp36-45. [WHIT70] White, J . L . , An I n t e r i m L i s p U s e r ' s G u i d e . MIT A r t i f i c i a l I n t e l l i g e n c e L a b o r a t o r y , R e p o r t 190, 1970. [ WILC73] W i l c o x , B., and C. H a f n e r , Lis£/MTS U s e r ' s G u i d e . U n i v e r s i t y Of M i c h i g a n , M e n t a l H e a l t h R e s e a r c h I n s t i t u t e , 1973. 89 { B e t t e r i s t h e end o f a t h i n g t h a n t h e b e g i n n i n g t h e r e o f . — E c c l e s i a s t e s }