$ od -c -N 50000 [phylum]<LISP>KOTO>Lispusers>BOYERMOORE.TEDIT!1 0000000 X E R O X \t B O Y E R M O O R E 0000020 \r 2 \r \r 4 \r \r 1 \r \r B O Y E R M 0000040 O O R E \r 1 \r \r 4 \r \r O u r T 0000060 h e o r e m P r o v e r 0000100 0000120 \r B y : R 0000140 . S . B o y e r a n d J 0000160 S t r o t h e r M o o r e 0000200 0000220 \r A u s t i n , T e 0000240 x a s \r c i r c a 1 9 8 3 \r I 0000260 N T R O D U C T I O N B Y K 0000300 E L L Y R O A C H ( R o a c 0000320 h . p a @ X e r o x . c o m ) \r 0000340 T h i s i s t h e i n f a 0000360 m o u s B o y e r - M o o r e 0000400 T h e o r e m P r o v e r 0000420 w r i t t e n b y B o y e r 0000440 a n d M o o r e . I ( K 0000460 e l l y R o a c h ) h a v e 0000500 g o n e t o t h e t r o 0000520 u b l e o f t r a n s l a t 0000540 i n g B o y e r a n d M o 0000560 o r e ' s t h e o r e m p r 0000600 o v e r f r o m Z e t a l i 0000620 s p i n t o I n t e r l i s 0000640 p - D i n o r d e r t o 0000660 u s e i t a n d u n d e r 0000700 s t a n d i t f o r m y 0000720 o w n e n l i g h t e n m e n 0000740 t . I t h i n k o t h e 0000760 r s t o o w o u l d l i k 0001000 e t o e x p e r i m e n t 0001020 w i t h t h i s c l a s s i 0001040 c p r o g r a m a n d s o 0001060 I h a v e p u t m y t 0001100 r a n s l a t i o n o n t o 0001120 L I S P U S E R S . T h e 0001140 s h o r t d o c u m e n t a t 0001160 i o n i s t o L O A D B 0001200 O Y E R M O O R E . D C O M & 0001220 B O Y E R M O O R E D A T A 0001240 a n d d o \r ( P R O V E A L L 0001260 1 ) \t \t \t \t \t \t \t \t \t \t [ F u 0001300 n c t i o n ] \r ( * B o o t s 0001320 t r a p t h e t h e o r e m 0001340 p r o v e r . * ) \r ( P R O 0001360 V E A L L 2 ) \t \t \t \t \t \t \t \t 0001400 \t \t [ F u n c t i o n ] \r ( * 0001420 P r o v e b a s i c t h e o 0001440 r e m s & d e f i n e s o 0001460 m e b a s i c f n s . * ) 0001500 \r T h e m o s t i m p o r t 0001520 a n t u s e r i n t e r f a 0001540 c e f u n c t i o n s a r e 0001560 D E F N a n d P R O V E - 0001600 L E M M A . Y o u c a n 0001620 P P P R O V E A L L 2 a n d 0001640 s e e h o w I s e t u 0001660 p D E F N & a n d P R O V 0001700 E - L E M M A & t o c a l l 0001720 D E F N a n d P R O V E - 0001740 L E M M A f a i r l y d i r 0001760 e c t l y . T h e r e a r 0002000 e o t h e r P R O V E A L L 0002020 i f u n c t i o n s w h i c 0002040 h I h a v e n o t r u n 0002060 a s t h o r o u g h l y 377 377 0002100 \0 357 % 377 \0 I a l s o n e e d 0002120 t o u n d o a s m a l l 0002140 a m o u n t o f d a m a g 0002160 e i n s o m e o f t h e 0002200 P R O V E A L L i f o r i 0002220 > 2 b r o u g h t o n b y 0002240 m y t r a n s l a t i o n . 0002260 I ' m g o i n g t o t 0002300 r y t o g e t w h a t o 0002320 f f i c i a l d o c u m e n t 0002340 a t i o n I c a n a t s 0002360 o m e p o i n t a n d m o 0002400 d i f y i t t o b e c o 0002420 r r e c t f o r I n t e r l 0002440 i s p - D . P l e a s e d i 0002460 r e c t a n y p r o b l e m 0002500 s w i t h t h i s p a r t 0002520 i c u l a r t r a n s l a t i 0002540 o n t o R O A C H . P A @ X 0002560 E R O X . A R P A . T h e 0002600 r e m a i n d e r o f t h i 0002620 s d o c u m e n t i s g e 0002640 n e r a l c o m m e n t a r y 0002660 e x c e r p t e d f r o m 0002700 B o y e r a n d M o o r e ' 0002720 s o w n d o c u m e n t a t 0002740 i o n . 0002760 0003000 \r L A N G U A G E S A N 0003020 D M A C H I N E S \r \r W e b 0003040 e g a n w o r k i n g o n 0003060 t h i s c o d e i n 1 9 7 0003100 2 i n E d i n b u r g h a 0003120 t t h e M e t a m a t h e m 0003140 a t i c s U n i t . T h e 0003160 f i r s t v e r s i o n w 0003200 a s w r i t t e n i n P O 0003220 P - 2 f o r a n I C L 4 0003240 1 3 0 . I n P a l o A l 0003260 t o i n 1 9 7 4 w e t r 0003300 a n s l a t e d i t i n t o 0003320 I n t e r l i s p - 1 0 f o 0003340 r a X e r o x M A X C a 0003360 n d a D E C P D P 1 0 / B 0003400 B N - T E N E X . W e c o 0003420 n t i n u e d d e v e l o p i 0003440 n g i t a t X e r o x P 0003460 A R C , S R I , a n d t h 0003500 e U n i v e r s i t y o f 0003520 T e x a s o n t w o D E C 0003540 - 2 0 6 0 s . I n 1 9 8 3 0003560 , w e t r a n s l a t e d 0003600 i t i n t o M a c l i s p 0003620 f o r a D E C - 2 0 6 0 a 0003640 H o n e y w e l l M u l t i 0003660 c s a n d i n t o Z e t a 0003700 l i s p f o r a S y m b o 0003720 l i c s 3 6 0 0 . J o h n 0003740 N a g l e m a d e i t c 0003760 o m p a t i b l e w i t h F 0004000 r a n z L i s p f o r t h 0004020 e V A X . \r O W N E R S H I P 0004040 \r \r T h e d e v e l o p m e n 0004060 t o f t h i s s y s t e m 0004100 h a s b e e n p r i m a r 0004120 i l y f i n a n c e d b y 0004140 t h e N a t i o n a l S c i 0004160 e n c e F o u n d a t i o n 0004200 a n d t h e O f f i c e o 0004220 f N a v a l R e s e a r c h 0004240 . T h e N S F G r a n t 0004260 P o l i c y M a n u a l N 0004300 S F - 7 7 - 4 7 , R e v i s e 0004320 d O c t o b e r 1 9 7 9 , 0004340 s t a t e s i n p a r a g r 0004360 a p h 7 5 4 . 2 " D a t a 0004400 b a n k s a n d s o f t w a 0004420 r e , p r o d u c e d w i t 0004440 h t h e a s s i s t a n c e 0004460 o f N S F g r a n t s , 0004500 h a v i n g u t i l i t y t 0004520 o o t h e r s i n a d d i 0004540 t i o n t o t h e g r a n 0004560 t e e , s h a l l b e m a 0004600 d e a v a i l a b l e t o 0004620 u s e r s , a t n o c o s 0004640 t t o t h e g r a n t e e 0004660 , b y p u b l i c a t i o n 0004700 o r , o n r e q u e s t , 0004720 b y d u p l i c a t i o n 0004740 o r l o a n f o r r e p r 0004760 o d u c t i o n b y o t h e 0005000 r s . . . . A n y o u t 0005020 o f p o c k e t e x p e n s 0005040 e s i n c u r r e d b y t 0005060 h e g r a n t e e i n p r 0005100 o v i d i n g i n f o r m a t 0005120 i o n t o t h i r d p a r 0005140 t i e s m a y b e c h a r 0005160 g e d t o t h e t h i r d 0005200 p a r t y . \r D O C U M E N T 0005220 A T I O N \r \r T h e 1 9 7 8 0005240 v e r s i o n o f t h i s 0005260 s y s t e m w a s c a r e f 0005300 u l l y d e s c r i b e d i 0005320 n " A C o m p u t a t i o n 0005340 a l L o g i c , " A c a d e 0005360 m i c P r e s s , 1 9 7 9 . 0005400 B u t m u c h h a s c 0005420 h a n g e d . ( 1 ) A n 0005440 e x t e n s i v e a m o u n t 0005460 o f " l i n e a r " a r i 0005500 t h m e t i c h a s b e e n 0005520 b u i l t - i n . ( 2 ) 0005540 W e h a v e a d d e d t h 0005560 e n o t i o n o f m e t a 0005600 f u n c t i o n s d e s c r i 0005620 b e d i n " M e t a f u n c 0005640 t i o n s : P r o v i n g 0005660 T h e m C o r r e c t a n 0005700 d U s i n g T h e m E f f 0005720 i c i e n t l y a s N e w 0005740 P r o o f P r o c e d u r e s 0005760 " i n " T h e C o r r e c 0006000 t n e s s P r o b l e m i n 0006020 C o m p u t e r S c i e n c 0006040 e , " R . S . B o y e r 0006060 a n d J S . M o o r e ( 0006100 e d i t o r s ) , A c a d e m 0006120 i c P r e s s , 1 9 8 1 . 0006140 ( 3 ) E q u a l i t y r e 0006160 a s o n i n g i n t h e g 0006200 r o u n d c a s e i s c o 0006220 m p l e t e . ( 4 ) T h e 0006240 m e c h a n i s m f o r g 0006260 u e s s i n g w e l l - f o u 0006300 n d e d r e l a t i o n s a 0006320 t d e f i n i t i o n t i m 0006340 e h a s b e e n v a s t l 0006360 y s i m p l i f i e d b u t 0006400 n o w r e q u i r e s m o 0006420 r e e x p l i c i t g u i d 0006440 a n c e f r o m t h e u s 0006460 e r i n t h e n o n t r i 0006500 v i a l c a s e s . ( 5 ) 0006520 A v a r i e t y o f h i 0006540 n t s c a n b e g i v e n 0006560 t o t h e t h e o r e m - 0006600 p r o v e r . \r T h e u s e r 0006620 ' s m a n u a l f o r t h 0006640 e 1 9 7 8 v e r s i o n o 0006660 f t h e t h e o r e m - p r 0006700 o v e r i s e x t r e m e l 0006720 y o u t o f d a t e . 0006740 T h e b e s t w e c a n 0006760 o f f e r a t t h i s t i 0007000 m e i s t h e f i l e C 0007020 O D E . S U B , " A P o o r 0007040 S u b s t i t u t e f o r 0007060 a U s e r ' s M a n u a l 0007100 f o r a T h e o r e m P r 0007120 o v e r f o r a C o m p u 0007140 t a t i o n a l L o g i c . " 0007160 \r T H E S Y S T E M \r T h i s 0007200 c o d e w o r k s i n M 0007220 a c l i s p o n a D E C 0007240 2 0 6 0 a n d o n a H o 0007260 n e y w e l l M u l t i c s , 0007300 i n Z e t a l i s p o n 0007320 a S y m b o l i c s 3 6 0 0 0007340 , i n F r a n z L i s p 0007360 o n V a x e s . \r \0 \0 \0 \0 \0 003 0007400 ( L I S T ( ( P A G E N I L 0007420 ( P A P E R S I Z E L e t t 0007440 e r F O L I O I N F O ( A R 0007460 A B I C ) S T A R T I N G 0007500 P A G E # 1 ) ( 0 0 6 1 0007520 2 7 9 2 ) ( ( F O L I O N 0007540 I L ( P A R A L O O K S ( Q 0007560 U A D C E N T E R E D ) C H 0007600 A R L O O K S ( S U P E R S C 0007620 R I P T 0 I N V I S I B L E 0007640 O F F S E L E C T P O I N T 0007660 O F F P R O T E C T E D O 0007700 F F S I Z E 1 0 F A M I L 0007720 Y M O D E R N O V E R L I N 0007740 E O F F S T R I K E O U T 0007760 O F F U N D E R L I N E O F 0010000 F E X P A N S I O N R E G U 0010020 L A R S L O P E R E G U L A 0010040 R W E I G H T M E D I U M 0010060 I N V E R T E D O F F U S E 0010100 R I N F O N I L S T Y L E 0010120 N I L ) F O R M A T I N F O 0010140 ( A R A B I C ) ) ( 1 7 4 0010160 3 6 2 8 8 3 6 ) N I L ) 0010200 ( H E A D I N G N I L ( H 0010220 E A D I N G T Y P E R U N N I 0010240 N G H E A D ) ( 8 4 7 4 4 0010260 5 2 8 3 6 ) N I L ) ( T E 0010300 X T N I L N I L ( 8 4 9 0010320 6 4 5 6 6 0 0 ) N I L ) ) 0010340 ) ( P A G E N I L ( P A P 0010360 E R S I Z E L e t t e r F O 0010400 L I O I N F O ( A R A B I C 0010420 ) ) ( 0 0 6 1 2 7 9 2 0010440 ) ( ( F O L I O N I L ( P 0010460 A R A L O O K S ( Q U A D C 0010500 E N T E R E D ) C H A R L O O 0010520 K S ( S U P E R S C R I P T 0010540 0 I N V I S I B L E O F F 0010560 S E L E C T P O I N T O F F 0010600 P R O T E C T E D O F F S I 0010620 Z E 1 0 F A M I L Y M O D 0010640 E R N O V E R L I N E O F F 0010660 S T R I K E O U T O F F U 0010700 N D E R L I N E O F F E X P 0010720 A N S I O N R E G U L A R S 0010740 L O P E R E G U L A R W E I 0010760 G H T M E D I U M I N V E R 0011000 T E D O F F U S E R I N F O 0011020 N I L S T Y L E N I L ) 0011040 F O R M A T I N F O ( A R A B 0011060 I C ) ) ( 1 7 4 3 6 2 0011100 8 8 3 6 ) N I L ) ( H E A 0011120 D I N G N I L ( H E A D I N 0011140 G T Y P E R U N N I N G H E A 0011160 D ) ( 8 4 7 4 4 5 2 8 3 0011200 6 ) N I L ) ( T E X T N I 0011220 L N I L ( 8 4 9 6 4 5 6 0011240 6 0 0 ) N I L ) ) ) ( P A 0011260 G E N I L ( P A P E R S I Z 0011300 E L e t t e r F O L I O I N 0011320 F O ( A R A B I C ) ) ( 0011340 0 0 6 1 2 7 9 2 ) ( ( F 0011360 O L I O N I L ( P A R A L O 0011400 O K S ( Q U A D C E N T E R 0011420 E D ) C H A R L O O K S ( S 0011440 U P E R S C R I P T 0 I N V 0011460 I S I B L E O F F S E L E C 0011500 T P O I N T O F F P R O T E 0011520 C T E D O F F S I Z E 1 0 0011540 F A M I L Y M O D E R N O 0011560 V E R L I N E O F F S T R I 0011600 K E O U T O F F U N D E R L 0011620 I N E O F F E X P A N S I O 0011640 N R E G U L A R S L O P E 0011660 R E G U L A R W E I G H T M 0011700 E D I U M I N V E R T E D O 0011720 F F U S E R I N F O N I L 0011740 S T Y L E N I L ) F O R M A 0011760 T I N F O ( A R A B I C ) 0012000 ) ( 1 7 4 3 6 2 8 8 3 6 0012020 ) N I L ) ( H E A D I N G 0012040 N I L ( H E A D I N G T Y P E 0012060 R U N N I N G H E A D ) ( 8 0012100 4 7 4 4 5 2 8 3 6 ) N I 0012120 L ) ( T E X T N I L N I L 0012140 ( 8 4 9 6 4 5 6 6 0 0 ) 0012160 N I L ) ) ) ) ) \0 \0 \0 \0 \0 005 \0 0012200 005 \0 ( \0 \0 \0 \0 001 310 \0 \v \0 \0 \0 004 002 0012220 003 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0012240 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 ( \0 \0 \0 \0 001 0012260 310 \0 \v \0 \0 \0 004 002 004 \0 \0 \0 \0 \0 \0 \0 0012300 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0012320 \0 \0 ( \0 212 \0 212 001 8 \0 006 \0 \0 \0 004 002 0012340 003 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0012360 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 ( \0 212 \0 212 001 0012400 8 \0 \0 \0 \0 \0 004 002 004 \0 \0 \0 \0 \0 \0 \0 0012420 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0012440 \0 \0 D \0 \0 \0 \0 001 310 \0 \0 \0 \0 \0 \0 003 0012460 004 \0 \0 001 001 310 001 \0 \0 \0 \0 \0 \0 \0 \v P 0012500 A G E H E A D I N G \0 \v R U N N 0012520 I N G H E A D \0 \0 \0 \0 \0 \0 \0 \0 \0 0012540 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 004 \0 005 \0 024 \0 0012560 006 M O D E R N \0 \f \0 \0 \0 \0 \0 \0 002 0012600 \0 \0 024 \0 006 M O D E R N \0 006 \0 \0 \0 0012620 \0 \0 \0 \0 \0 \0 022 \0 004 L O G O \0 030 \0 0012640 \0 \0 \0 \0 \0 \0 \0 \0 024 \0 006 M O D E R 0012660 N \0 \n \0 \0 \0 \0 \0 \0 002 \0 \0 024 \0 006 M 0012700 O D E R N \0 \n \0 \0 \0 \0 \0 \0 \0 \0 \0 0012720 \0 \0 \0 \0 002 \0 005 \0 \0 \0 005 \0 \0 \0 \0 003 0012740 \0 \0 \0 001 \0 \0 \0 \0 002 \0 \0 \0 \v \0 \0 \0 0012760 \0 005 \0 \0 \0 \0 \0 002 \0 005 \0 \0 \0 002 \0 001 0013000 \0 \v H R U L E . G E T F N 001 \0 024 0013020 \0 006 M O D E R N \0 \n \0 \0 \0 \0 \0 \0 0013040 \0 \0 \0 \0 \0 001 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 0013060 002 \0 004 \0 \0 \0 002 \0 001 \0 \v H R U L E 0013100 . G E T F N 001 \0 024 \0 006 M O D E R 0013120 N \0 \n \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 001 \0 0013140 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 004 \0 \0 \0 002 0013160 \0 001 \0 \v H R U L E . G E T F N 001 0013200 \0 024 \0 006 M O D E R N \0 \n \0 \0 \0 \0 0013220 \0 \0 \0 \0 \0 \0 \0 001 \0 \0 \0 \0 005 \0 \0 \0 0013240 \0 \0 002 \0 003 \0 \0 \0 \v \0 \0 \0 \0 001 \0 \0 0013260 \0 \0 \0 002 \0 003 \0 \0 \0 002 \0 001 \0 \v H R 0013300 U L E . G E T F N 001 \0 024 \0 006 M O 0013320 D E R N \0 \f \0 \0 \0 \0 \0 \0 002 \0 \0 \0 0013340 \0 001 \0 \0 \0 \0 001 \0 \0 \0 \0 \0 002 \0 004 \0 0013360 \0 \0 002 \0 001 \0 \v H R U L E . G E T 0013400 F N 001 \0 024 \0 006 M O D E R N \0 \f \0 0013420 \0 \0 \0 \0 \0 002 \0 \0 \0 \0 001 \0 \0 \0 \0 001 0013440 \0 \0 \0 \0 \0 002 \0 001 \0 \0 \0 0 \0 \0 \0 \0 0013460 005 \0 \0 \0 \0 \0 002 \0 001 \0 \0 \0 ; \0 \0 \0 0013500 \0 005 \0 \0 \0 \0 \0 002 \0 001 \0 \0 \0 016 \0 \0 0013520 \0 \0 005 \0 \0 \0 \0 \0 002 \0 001 \0 \0 \0 \n \0 0013540 \0 \0 \0 005 \0 \0 \0 001 \0 \0 \0 \0 004 \0 \0 \0 0013560 \0 \0 002 \0 002 \0 \0 \0 \f \0 \0 \0 \0 004 \0 \0 0013600 \0 % \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 002 \0 0013620 \0 001 307 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 002 0013640 \0 \0 \0 ! \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 0013660 002 \0 \0 \0 $ \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 0013700 \0 002 \0 \0 \0 ! \0 \0 \0 \0 005 \0 \0 \0 \0 \0 0013720 002 \0 002 \0 \0 \0 4 \0 \0 \0 \0 005 \0 \0 \0 \0 0013740 \0 002 \0 002 \0 \0 \0 375 \0 \0 \0 \0 005 \0 \0 \0 0013760 005 \0 \0 002 \0 005 \0 \0 001 301 \0 \0 \0 \0 005 \0 0014000 \0 \0 \0 \0 002 \0 002 \0 \0 \0 026 \0 \0 \0 \0 004 0014020 \0 \0 001 374 \0 \0 \0 \0 005 \0 \0 \0 001 \0 \0 \0 0014040 \0 004 \0 \0 \0 \0 \0 002 \0 002 \0 \0 \0 \t \0 \0 0014060 \0 \0 004 \0 \0 002 g \0 \0 \0 \0 005 \0 \0 \0 001 0014100 \0 \0 \0 \0 004 \0 \0 \0 \0 \0 002 \0 002 \0 \0 \0 0014120 \r \0 \0 \0 \0 004 \0 \0 002 363 \0 \0 \0 \0 005 \0 0014140 \0 \0 \0 \0 002 \0 002 \0 \0 \0 351 \0 \0 \0 \0 005 0014160 \0 \0 \0 \0 \0 002 \0 002 \0 \0 \0 \n \0 \0 \0 \0 0014200 004 \0 \0 \0 001 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 0014220 \0 002 \0 \0 \0 ~ \0 \0 \0 \0 005 \0 \0 016 372 \0 0014240 B z 272 0014243