1 /* Logiweb, a system for electronic distribution of mathematics 2 Copyright (C) 2004-2010 Klaus Grue 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; either version 2 of the License, or 7 (at your option) any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program; if not, write to the Free Software 16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 18 Contact: Klaus Grue, DIKU, Universitetsparken 1, DK2100 Copenhagen, 19 Denmark, grue@diku.dk, http://logiweb.eu/, http://www.diku.dk/~grue/ 20 21 Logiweb is a system for distribution of mathematical definitions, 22 lemmas, and proofs. For more on Logiweb, consult http://logiweb.eu/. 23 */ 24 25 /********** 26 * Config * 27 **********/ 28 29 /* Max percentage of available ram that can be allocated for the heap */ 30 #ifndef HEAPMAX0 31 #define HEAPMAX0 90 32 #endif 33 34 /* Percentage of max heap required to be free after GC. Quit if not met. */ 35 #ifndef HEAPMAX1 36 #define HEAPMAX1 90 37 #endif 38 39 /* Percentage of heap required to be free after GC. Allocate if not met. */ 40 #ifndef HEAPMAX2 41 #define HEAPMAX2 70 42 #endif 43 44 /* Percentage of heap to be free after allocation if permitted by HEAPMAX0 */ 45 #ifndef HEAPMAX3 46 #define HEAPMAX3 50 47 #endif 48 49 /* Size of memory area reserved for stack */ 50 #ifndef STACKSIZE 51 #define STACKSIZE 50000000 52 #endif 53 54 /* Area reserved for defined constants */ 55 #ifndef STORESIZE 56 #define STORESIZE 10000 57 #endif 58 59 /* When TRUE: do Garbage Collection (GC) for *each* allocation (takes time!) */ 60 #ifndef ALWAYSGC 61 #define ALWAYSGC FALSE 62 #endif 63 64 /* When TRUE: Print Garbage Collection (GC) statistics for each GC */ 65 #ifndef PRINTGC 66 #define PRINTGC FALSE 67 #endif 68 69 70 71 /************ 72 * INCLUDES * 73 ************/ 74 75 #include 76 #include 77 #include 78 #include 79 #include 80 #include 81 #include 82 #include 83 #include 84 #include 85 #include 86 #include 87 #include 88 #include 89 #include 90 #ifndef __CYGWIN__ 91 #include 92 #else 93 #include 94 #endif /* __CYGWIN__ */ 95 96 97 98 /****************** 99 * INCLUDED PAGES * 100 ******************/ 101 102 #include "pages.c" 103 104 105 106 /*********** 107 * DEFINES * 108 ***********/ 109 110 /* 111 cons(TAG_FALSE ,NIL ,NIL ) The constant F 112 cons(TAG_INT ,val ,int ) Val is the least significant word of the integer 113 cons(TAG_VECT ,bytes,vect ) Bytes are the least significant word of the vect 114 cons(TAG_PAIR ,head ,tail ) Tagged pair 115 cons(TAG_EX ,arg ,NIL ) Exception 116 cons(TAG_MAP ,map ,info ) Tagged map. the 'info' is for the optimizer 117 cons(TAG_OBJ ,tag ,val ) Object 118 cons(TAG_GARB ,NIL ,NIL ) Garbage 119 cons(TTAG_APPLY ,fct ,arg ) Functional applicationat term level 120 cons(TTAG_LAMBDA ,term ,NIL ) Lambda abstraction at term level 121 cons(TTAG_VAR ,index,NIL ) The variable with the given deBruijn index 122 cons(TTAG_PAIR ,head ,tail ) Raw pairing at term level 123 cons(TTAG_CONST ,rnf ,NIL ) A term whose value is the given rnf 124 cons(TTAG_CALL ,term ,term*) Evaluate term in given term* environment 125 cons(TTAG_ECALL ,eterm,term*) Evaluate eager term in given term* environment 126 cons(MTAG_CLOSURE,term ,env ) Value of term in given closure* environment 127 cons(MTAG_INDIR ,NIL ,rnf ) Indirection to the given rnf 128 cons(MTAG_PAIR ,head ,tail ) Raw pairing at map level 129 cons(MTAG_LAMBDA ,term ,env ) \x.term in given closure* environment 130 cons(MTAG_FIX ,NIL ,NIL ) Fixed point operator 131 132 Eager term tags: 133 134 ETAG_var 135 ETAG_ecall 136 ETAG_digit0 " %0 137 ETAG_digit1 " %1 138 ETAG_digit2 " %2 139 ETAG_digit3 " %3 140 ETAG_digit4 " %4 141 ETAG_digit5 " %5 142 ETAG_digit6 " %6 143 ETAG_digit7 " %7 144 ETAG_digit8 " %8 145 ETAG_digit9 " %9 146 ETAG_times " * " 147 ETAG_plus " + " 148 ETAG_minus " - " 149 ETAG_and " .and. " 150 ETAG_or " .or. " 151 ETAG_then " .then. " 152 ETAG_pair " :: " 153 ETAG_lt " < " 154 ETAG_le " <= " 155 ETAG_equal " = " 156 ETAG_gt " > " 157 ETAG_ge " >= " 158 ETAG_apply " apply " 159 ETAG_boolp " boolp 160 ETAG_catch " catch 161 ETAG_maptag1 " catching maptag 162 ETAG_div " div " 163 ETAG_head " head 164 ETAG_intp " intp 165 ETAG_boolg " is bool : " 166 ETAG_intg " is int : " 167 ETAG_mapg " is map : " 168 ETAG_objg " is object : " 169 ETAG_pairg " is pair : " 170 ETAG_mapp " mapp 171 ETAG_maptag " maptag 172 ETAG_mod " mod " 173 ETAG_norm " norm 174 ETAG_objp " objectp 175 ETAG_pairp " pairp 176 ETAG_raise " raise 177 ETAG_root " root 178 ETAG_tail " tail 179 ETAG_untag " untag 180 ETAG_digitend %% 181 ETAG_par ( " ) 182 ETAG_uplus + " 183 ETAG_dplus +" 184 ETAG_uminus - " 185 ETAG_dminus -" 186 ETAG_not .not. " 187 ETAG_Base Base 188 ETAG_LET LET " BE " 189 ETAG_ash ash ( " , " ) 190 ETAG_bottom bottom 191 ETAG_bt2bytes bt2byte* ( " ) 192 ETAG_bt2vects bt2vector* ( " ) 193 ETAG_bt2vector bt2vector ( " ) 194 ETAG_ceiling ceiling ( " , " ) 195 ETAG_destruct destruct ( " ) 196 ETAG_evenp evenp ( " ) 197 ETAG_exception exception 198 ETAG_false false 199 ETAG_floor floor ( " , " ) 200 ETAG_half half ( " ) 201 ETAG_if if " then " else " 202 ETAG_intlength integer-length ( " ) 203 ETAG_logand logand ( " , " ) 204 ETAG_logandc1 logandc1 ( " , " ) 205 ETAG_logandc2 logandc2 ( " , " ) 206 ETAG_logbitp logbitp ( " , " ) 207 ETAG_logcount logcount ( " ) 208 ETAG_logeqv logeqv ( " , " ) 209 ETAG_logior logior ( " , " ) 210 ETAG_lognand lognand ( " , " ) 211 ETAG_lognor lognor ( " , " ) 212 ETAG_lognot lognot ( " ) 213 ETAG_logorc1 logorc1 ( " , " ) 214 ETAG_logorc2 logorc2 ( " , " ) 215 ETAG_logtest logtest ( " , " ) 216 ETAG_logxor logxor ( " , " ) 217 ETAG_map map ( " ) 218 ETAG_prenorm norm " 219 ETAG_notnot notnot " 220 ETAG_object object ( " ) 221 ETAG_print print ( " ) 222 ETAG_round round ( " , " ) 223 ETAG_spy spy ( " ) 224 ETAG_timer timer ( " ) 225 ETAG_trace trace ( " ) 226 ETAG_truncate truncate ( " , " ) 227 ETAG_vector vector ( " ) 228 ETAG_vnorm vector-norm ( " ) 229 ETAG_vempty vector-empty ( " ) 230 ETAG_vindex vector-index ( " , " ) 231 ETAG_vlength vector-length ( " ) 232 ETAG_vprefix vector-prefix ( " , " ) 233 ETAG_vsubseq vector-subseq ( " , " , " ) 234 ETAG_vsuffix vector-suffix ( " , " ) 235 ETAG_v2bytes vector2byte* ( " ) 236 ETAG_v2vects vector2vector* ( " ) 237 ETAG_vt2bytes vt2byte* ( " ) 238 ETAG_vt2vects vt2vector* ( " ) 239 ETAG_vt2v vt2vector ( " ) 240 ETAG_yy YY 241 ETAG_compile compile ( " ) 242 ETAG_ripemd ripemd ( " ) 243 ETAG_sl2rack sl2rack ( " ) 244 ETAG_rack2sl rack2sl ( " ) 245 */ 246 247 /* Accessors */ 248 #define ROOT(x) (((cell*)(x))->root) 249 #define HEAD(x) (((cell*)(x))->head) 250 #define TAIL(x) (((cell*)(x))->tail) 251 252 /* Number of tags */ 253 #define TAG_SIZE 256 254 255 /* Data tags */ 256 #define TAG_FALSE 1 257 #define TAG_INT 2 258 #define TAG_VECT 3 259 #define TAG_PAIR 4 260 #define TAG_EX 5 261 #define TAG_MAP 6 262 #define TAG_OBJ 7 263 #define TAG_GARB 8 264 265 /* Term tags */ 266 #define TTAG_APPLY 20 267 #define TTAG_LAMBDA 21 268 #define TTAG_VAR 22 269 #define TTAG_PAIR 23 270 #define TTAG_CONST 24 271 #define TTAG_CALL 25 272 #define TTAG_ECALL 26 273 274 /* Map tags */ 275 #define MTAG_CLOSURE 30 276 #define MTAG_INDIR 31 277 #define MTAG_PAIR 32 278 #define MTAG_LAMBDA 33 279 #define MTAG_FIX 34 280 281 /* Class tags */ 282 #define CTAG_MAP 40 283 #define CTAG_EMAP 41 284 #define CTAG_TRUE 42 285 #define CTAG_APPLY 43 286 #define CTAG_IF 44 287 288 /* Optimized function tags 289 (ETAG for "eager tag" since most optimized functions are eager) */ 290 #define ETAG_var 100 291 #define ETAG_ecall 101 292 #define ETAG_digit0 102 293 #define ETAG_digit1 103 294 #define ETAG_digit2 104 295 #define ETAG_digit3 105 296 #define ETAG_digit4 106 297 #define ETAG_digit5 107 298 #define ETAG_digit6 108 299 #define ETAG_digit7 109 300 #define ETAG_digit8 110 301 #define ETAG_digit9 111 302 #define ETAG_times 112 303 #define ETAG_plus 113 304 #define ETAG_minus 114 305 #define ETAG_and 115 306 #define ETAG_or 116 307 #define ETAG_then 117 308 #define ETAG_pair 118 309 #define ETAG_lt 119 310 #define ETAG_le 120 311 #define ETAG_equal 121 312 #define ETAG_gt 122 313 #define ETAG_ge 123 314 #define ETAG_apply 124 315 #define ETAG_boolp 125 316 #define ETAG_catch 126 317 #define ETAG_maptag1 127 318 #define ETAG_div 128 319 #define ETAG_head 129 320 #define ETAG_intp 130 321 #define ETAG_boolg 131 322 #define ETAG_intg 132 323 #define ETAG_mapg 133 324 #define ETAG_objg 134 325 #define ETAG_pairg 135 326 /* ETAG_valg 136*/ 327 #define ETAG_mapp 137 328 #define ETAG_maptag 138 329 #define ETAG_mod 139 330 #define ETAG_norm 140 331 #define ETAG_objp 141 332 #define ETAG_pairp 142 333 #define ETAG_raise 143 334 #define ETAG_root 144 335 #define ETAG_tail 145 336 #define ETAG_untag 146 337 #define ETAG_digitend 147 338 #define ETAG_par 148 339 #define ETAG_uplus 149 340 #define ETAG_dplus 150 341 #define ETAG_uminus 151 342 #define ETAG_dminus 152 343 #define ETAG_not 153 344 #define ETAG_Base 154 345 #define ETAG_LET 155 346 #define ETAG_ash 156 347 #define ETAG_bottom 157 348 #define ETAG_bt2bytes 158 349 #define ETAG_bt2vects 205 350 #define ETAG_bt2vector 159 351 #define ETAG_ceiling 160 352 #define ETAG_destruct 161 353 #define ETAG_evenp 162 354 #define ETAG_exception 163 355 #define ETAG_false 164 356 #define ETAG_floor 165 357 #define ETAG_half 166 358 #define ETAG_if 167 359 #define ETAG_intlength 168 360 #define ETAG_logand 169 361 #define ETAG_logandc1 170 362 #define ETAG_logandc2 171 363 #define ETAG_logbitp 172 364 #define ETAG_logcount 173 365 #define ETAG_logeqv 174 366 #define ETAG_logior 175 367 #define ETAG_lognand 176 368 #define ETAG_lognor 177 369 #define ETAG_lognot 178 370 #define ETAG_logorc1 179 371 #define ETAG_logorc2 180 372 #define ETAG_logtest 181 373 #define ETAG_logxor 182 374 #define ETAG_map 183 375 #define ETAG_prenorm 184 376 #define ETAG_notnot 185 377 #define ETAG_object 186 378 #define ETAG_print 187 379 #define ETAG_round 188 380 #define ETAG_spy 189 381 #define ETAG_timer 190 382 #define ETAG_trace 191 383 #define ETAG_truncate 192 384 #define ETAG_vector 193 385 #define ETAG_vnorm 208 386 #define ETAG_vempty 194 387 #define ETAG_vindex 195 388 #define ETAG_vlength 196 389 #define ETAG_vprefix 197 390 #define ETAG_vsubseq 198 391 #define ETAG_vsuffix 199 392 #define ETAG_v2bytes 200 393 #define ETAG_v2vects 206 394 #define ETAG_vt2bytes 201 395 #define ETAG_vt2vects 207 396 #define ETAG_vt2v 202 397 #define ETAG_yy 203 398 #define ETAG_compile 204 399 #define ETAG_ripemd 209 400 #define ETAG_sl2rack 210 401 #define ETAG_rack2sl 211 402 403 /* True if x is *not* of given type */ 404 405 #define GD_INT(x) ((ROOT(x)|1)!=TAG_VECT) 406 #define GD_PAIR(x) (ROOT(x)!=TAG_PAIR) 407 #define GD_EX(x) (ROOT(x)!=TAG_EX) 408 #define GD_MAP(x) (ROOT(x)!=TAG_MAP) 409 #define GD_OBJ(x) (ROOT(x)!=TAG_OBJ) 410 411 /* True if x is *not* of given type */ 412 413 #define NO_BOOL(x) (((x)!=T)&&(ROOT(x)!=TAG_FALSE)) 414 #define NO_INT(x) (((x)==T)||GD_INT(x)) 415 #define NO_PAIR(x) (((x)==T)||GD_PAIR(x)) 416 #define NO_EX(x) (((x)==T)||GD_EX(x)) 417 #define NO_MAP(x) (((x)==T)||GD_MAP(x)) 418 #define NO_OBJ(x) (((x)==T)||GD_OBJ(x)) 419 420 /* True if x is of given type */ 421 422 #define IS_BOOL(x) (!NO_BOOL(x)) 423 #define IS_INT(x) (!NO_INT (x)) 424 #define IS_PAIR(x) (!NO_PAIR(x)) 425 #define IS_EX(x) (!NO_EX (x)) 426 #define IS_MAP(x) (!NO_MAP (x)) 427 #define IS_OBJ(x) (!NO_OBJ (x)) 428 429 /* NIL pointer, map truth, C truth and C falsehood */ 430 #define NIL 0 431 #define T 0 432 #define TRUE 1 433 #define FALSE 0 434 #define ENDFILE 256 435 436 /* Conversion of negative x to -1 and other x to 0 */ 437 #define SIGN(x) ((x)&signmask?M:Z) 438 439 /* Operations on halfwords */ 440 #define HALFHEAD(x) ((x)&halfmask) 441 #define HALFTAIL(x) ((x)>>halfsize) 442 #define HALFCONS(x,y) (((x)&halfmask)+((y)<=TAG_SIZE) return TRUE; 747 if(tag2string[tag]==NIL) return TRUE; 748 return FALSE;} 749 750 char *safe_tag2string(pnt tag){ 751 if(invalid_tag(tag)) return "TAG_UNKNOWN"; 752 return tag2string[tag];} 753 754 void spytag(pnt tag){ 755 if(tag&signmask) printf("*"); 756 if(tag&markmask) printf("#"); 757 printf("%s",safe_tag2string(tag&~signmask&~markmask));} 758 759 void spytag0(pnt tag){ 760 spytag(tag); 761 printf("\n");} 762 763 void spytagroot1(pnt x){ 764 if(x==T) printf("TAG_TRUE"); else spytag(ROOT(x));} 765 766 void spytagroot0(pnt x){ 767 spytagroot1(x); 768 printf("\n");} 769 770 void unexpected_tag(char *msg,pnt value){ 771 printf("%s: unexpected tag: ",msg); 772 spytagroot0(value); 773 die("Goodbye");} 774 775 #define PNTBUFSIZE 100 776 777 char pntbuffer[PNTBUFSIZE]; 778 779 int ptoa1(pnt x){ 780 int position; 781 if(x==0) return 0; 782 position=ptoa1(x/10); 783 pntbuffer[position++]='0'+x%10; 784 if(position>=PNTBUFSIZE) die("Internal error: pnt buffer overflow"); 785 return position;} 786 787 char *ptoa(pnt x){ 788 if(x==0){ 789 pntbuffer[0]='0'; 790 pntbuffer[1]=0;} 791 else{ 792 pntbuffer[ptoa1(x)]=0;} 793 return pntbuffer;} 794 795 void spydigits1(FILE *f,pnt x){ 796 if(x==0) return; 797 spydigits1(f,x/10); 798 fprintf(f,"%d",(int)(x%10));} 799 800 void spydigits(FILE *f,pnt x){ 801 if(x==0) fprintf(f,"0"); else spydigits1(f,x);} 802 803 void spydigitsln(char *msg,pnt x){ 804 fprintf(stderr,"%s ",msg); 805 spydigits(stderr,x); 806 fprintf(stderr,"\n");} 807 808 void spyint0(pnt x){ 809 spydigits(stdout,HEAD(x)); 810 for(x=TAIL(x);x;x=TAIL(x)){printf(" ");spydigits(stdout,HEAD(x));}} 811 812 /* 813 void spyint0(pnt x){ 814 printf("%u",HEAD(x)); 815 for(x=TAIL(x);x;x=TAIL(x)) printf(" %u",HEAD(x));} 816 */ 817 818 void spyvect(pnt x){ 819 printf("\""); 820 for(;TAIL(x);x=TAIL(x)){ 821 pnt i; 822 pnt y=HEAD(x); 823 for(i=0;i>8;}} 826 for(x=HEAD(x);x>1;x=x>>8) printchar(x); 827 printf("\"");} 828 829 /* 830 void spyint1(pnt x){ 831 if((TAIL(x)==T)&&((HEAD(x)<10000)||((HEAD(x))>1+~10000))){ 832 printf("%5d",(int)(HEAD(x))); 833 return;} 834 printf("#"); 835 spyvect(x);} 836 */ 837 838 void spyname(pnt x,pnt arglist){ 839 for(;TAIL(x);x=TAIL(x)){ 840 pnt i; 841 pnt y=HEAD(x); 842 for(i=0;i>8;}} 846 for(x=HEAD(x);x>1;x=x>>8) 847 if((x&255)!='"'||NO_PAIR(arglist)) printchar(x); 848 else {spy1(HEAD(arglist));arglist=TAIL(arglist);} 849 if(arglist==T) return; 850 printf(":"); 851 spy1(arglist);} 852 853 pnt root2name(pnt x){ 854 pnt root,ref,idx,name; 855 root=HEAD(x); 856 if(NO_PAIR(root)) return TRUE; 857 ref=HEAD(root); 858 if(NO_INT(ref)) return TRUE; 859 if(NO_PAIR(TAIL(root))) return TRUE; 860 idx=HEAD(TAIL(root)); 861 if(NO_INT(idx)) return TRUE; 862 if(ref==Z){printf("(");spy1(idx);printf(")");return FALSE;} 863 name=nameget(state,ref,idx); 864 if(name==T) return TRUE; 865 spyname(name,TAIL(x)); 866 return FALSE;} 867 868 void spy1(pnt x){ 869 pnt tag; 870 if(spycnt==0){printf("...");return;} 871 spycnt--; 872 if(x==T){printf("T");return;} 873 tag=ROOT(x); 874 if(tag&signmask) printf("*"); 875 if(tag&markmask) printf("#"); 876 tag=tag&~signmask&~markmask; 877 switch(tag){ 878 case TAG_FALSE: printf("F");return; 879 case TAG_INT: spyint0(x);return; 880 case TAG_VECT: spyvect(x);return; 881 case TAG_PAIR: /*if(root2name(x))*/ prn2("P",HEAD(x),TAIL(x));return; 882 case TAG_EX: prn1("X",HEAD(x));return; 883 case TAG_MAP: printf("M(%s,",safe_tag2string(TAIL(x))); 884 spy1(HEAD(x));printf(")");return; 885 case TAG_OBJ: prn2("O",HEAD(HEAD(x)),TAIL(HEAD(x)));spy1(TAIL(x));return; 886 case TAG_GARB: printf("G(%s)",ptoa(x));return; 887 case TTAG_VAR: printf("TTAG_VAR(%s)",ptoa(HEAD(x)));return; 888 case TTAG_LAMBDA: prn1("TTAG_LAMBDA",HEAD(x));return; 889 case TTAG_CONST: prn1("TTAG_CONST",HEAD(x));return; 890 case MTAG_INDIR: prn1("MTAG_INDIR",TAIL(x));return; 891 case MTAG_CLOSURE:printf("CLOSURE");return; 892 case ETAG_var: printf("ETAG_var(%s)",ptoa(HEAD(x)));return; 893 case ETAG_ecall: prn2("ETAG_ecall",HEAD(x),TAIL(x));return;} 894 if(invalid_tag(tag)) {printf("??");return;} 895 prn2(tag2string[tag],HEAD(x),TAIL(x));} 896 897 void spy2(pnt x,pnt y){ 898 spycnt=x; 899 spy1(y);} 900 901 pnt spy0(pnt x){ 902 spy2(100,x); 903 printf("\n"); 904 return x;} 905 906 void spydie(pnt x,char *msg){ 907 spy0(x); 908 die(msg);} 909 910 void backtrace(pnt x,pnt cnt){ 911 pnt c; 912 pnt i; 913 pnt y; 914 pnt tag; 915 if(cnt==0) return; 916 printf("backtrace %3s: %10s\n",ptoa(cnt),ptoa(x)); 917 spy0(x); 918 if(x==state){printf("Referenced from state\n");return;} 919 if(x==global_x){printf("Referenced from head\n");return;} 920 if(x==global_y){printf("Referenced from tail\n");return;} 921 for(i=sp;i>8;}} 971 for(x=HEAD(x);x>255;x=x>>8) print3(x);} 972 973 void print1(pnt x){ 974 pnt tag; 975 if(x==T) return; 976 tag=ROOT(x); 977 switch(tag){ 978 case TAG_FALSE: return; 979 case TAG_INT: print2(x);return; 980 case TAG_VECT: print2(x);return; 981 case TAG_PAIR: print1(HEAD(x));print1(TAIL(x));return; 982 case TAG_MAP: return; 983 case TAG_OBJ: return;} 984 printf("\nInternal error in 'print': Unexpected tag"); 985 if(invalid_tag(tag)) printf("TAG=%s\n",ptoa(tag)); 986 else printf("TAG=%s\n",tag2string[tag]); 987 deathReport(); 988 exit(1);} 989 990 991 992 /********** 993 * Spying * 994 **********/ 995 996 #define TIMERS 1000 997 #define MEGA 1000000 998 int currentTimer=-1; 999 struct timeval timers[TIMERS]; 1000 int counters[TIMERS]; 1001 1002 void initTimers(){ 1003 int i; 1004 for(i=0;i=MEGA){ 1016 timers[currentTimer].tv_usec-=MEGA; 1017 timers[currentTimer].tv_sec+=1;}} 1018 currentTimer=i; 1019 if((0<=currentTimer)&(currentTimerheapmax/100*HEAPMAX1) die("Heap too small, goodbye."); 1338 heapsize1=used/HEAPMAX3*100; 1339 if(heapsize1>heapmax) heapsize1=heapmax; 1340 if(heapsize1<=heapsize) return; 1341 heapsize1-=heapsize; 1342 #if(PRINTGC) 1343 fprintf(stderr,"allocate %9d cells\n",heapsize1); 1344 #endif 1345 heapalloc(heapsize1); 1346 if(!garb) die("Internal error in GC, goodbye.");} 1347 1348 1349 1350 /**************** 1351 * CONSTRUCTORS * 1352 ****************/ 1353 1354 /* Get fresh cell */ 1355 pnt fresh(pnt x,pnt y){ 1356 pnt result; 1357 if(always_gc || !garb) gc(x,y); 1358 result=garb; 1359 /*if(ROOT(result)!=TAG_GARB) die("Attempt to allocate non-garbage.\n");*/ 1360 garb=HEAD(result); 1361 return result;} 1362 1363 /* General constructor */ 1364 pnt cons(pnt root,pnt head,pnt tail){ 1365 pnt result; 1366 result=fresh(head,tail); 1367 ROOT(result)=root; 1368 HEAD(result)=head; 1369 TAIL(result)=tail; 1370 return result;} 1371 1372 /* General constructor with cardinal head */ 1373 pnt cons2(pnt root,pnt head,pnt tail){ 1374 pnt result=fresh(NIL,tail); 1375 ROOT(result)=root; 1376 HEAD(result)=head; 1377 TAIL(result)=tail; 1378 return result;} 1379 1380 /* General constructor with cardinal tail */ 1381 pnt cons1(pnt root,pnt head,pnt tail){ 1382 pnt result=fresh(head,NIL); 1383 ROOT(result)=root; 1384 HEAD(result)=head; 1385 TAIL(result)=tail; 1386 return result;} 1387 1388 /* Part of safe constructor */ 1389 pnt scons(pnt root,pnt tail){ 1390 pnt result; 1391 result=fresh(NIL,tail); 1392 ROOT(result)=root; 1393 HEAD(result)=pop(); 1394 TAIL(result)=tail; 1395 return result;} 1396 1397 1398 1399 /************************ 1400 * INTEGER CONSTRUCTORS * 1401 ************************/ 1402 1403 /* Simple integer cons */ 1404 pnt icons(pnt head,pnt tail){ 1405 return cons2(TAG_INT,head,tail);} 1406 1407 /* Normalization preserving integer cons */ 1408 pnt intcons(pnt head,pnt tail){ 1409 if((head&signmask)==0){ 1410 if(tail!=Z) return icons(head,tail); 1411 if(head==0) return Z; 1412 return icons(head,NIL);} 1413 else{ 1414 if(tail!=M) return icons(head,tail); 1415 if(head==~(pnt)0) return M; 1416 return icons(head,NIL);}} 1417 1418 /* Integer tail with sign extend if needed */ 1419 pnt inttail(pnt cons){ 1420 if(TAIL(cons)) return TAIL(cons); 1421 if((HEAD(cons)&signmask)==0) return Z; else return M;} 1422 1423 /* Convert C integer to twos complement pnt */ 1424 pnt int2pnt(spnt i){ 1425 if(i>=0) return (pnt)i; 1426 return 1+~(pnt)(-i);} 1427 1428 /* Convert C integer to integer */ 1429 pnt int2int(spnt i){ 1430 return icons(int2pnt(i),NIL);} 1431 1432 /* Convert C integer to normalized integer */ 1433 pnt JN(spnt i){ 1434 if(i==0) return Z; 1435 if(i==-1) return M; 1436 return keep(int2int(i));} 1437 1438 pnt K2(spnt i,spnt j){ 1439 return keep(intcons(int2pnt(i),JN(j)));} 1440 1441 1442 1443 /*********************** 1444 * VECTOR CONSTRUCTORS * 1445 ***********************/ 1446 1447 pnt consvec(pnt head,pnt tail){ 1448 pnt result=fresh(NIL,tail); 1449 ROOT(result)=TAG_VECT; 1450 HEAD(result)=head; 1451 TAIL(result)=tail; 1452 return result;} 1453 1454 pnt int2vec(pnt x){ 1455 if(NO_INT(x)) return x; 1456 return consvec(HEAD(x),TAIL(x));} 1457 1458 /* Destructive. Only for use in main */ 1459 pnt vec2int(pnt x){ 1460 if(NO_INT(x)) die("vec2int applied to non-int"); 1461 ROOT(x)=TAG_INT; 1462 return x;} 1463 1464 pnt str2vec2(unsigned char *str,pnt len){ 1465 if(len==0) return 1; 1466 return (*str)|(str2vec2(str+1,len-1)<<8);} 1467 1468 pnt str2vec1(unsigned char *str,pnt len){ 1469 if(len " */ 1784 if(NO_INT(x)) return X; 1785 if(NO_INT(y)) return X; 1786 if(cmp1(x,y)>1) return T; else return F;} 1787 1788 pnt le(pnt x,pnt y){/* " <= " */ 1789 if(NO_INT(x)) return X; 1790 if(NO_INT(y)) return X; 1791 if(cmp1(x,y)<=1) return T; else return F;} 1792 1793 pnt ge(pnt x,pnt y){/* " >= " */ 1794 if(NO_INT(x)) return X; 1795 if(NO_INT(y)) return X; 1796 if(cmp1(x,y)>=1) return T; else return F;} 1797 1798 pnt evenp(pnt x){/* evenp ( " ) */ 1799 if(NO_INT(x)) return X; 1800 if(HEAD(x)&1) return F; else return T;} 1801 1802 pnt half1(pnt x){ 1803 pnt v=HEAD(x); 1804 pnt y=v>>1; 1805 pnt z=TAIL(x); 1806 if(!z){if(v&signmask) return intcons(y+signmask,M); else return intcons(y,Z);} 1807 if(HEAD(z)&1) y=y+signmask; 1808 return intcons(y,half1(z));} 1809 1810 pnt half(pnt x){/* half ( " ) */ 1811 if(NO_INT(x)) return X; 1812 return half1(x);} 1813 1814 pnt small(pnt x){ 1815 if(NO_INT(x)) return X; 1816 if(x==Z) return T; 1817 if(x==M) return T; 1818 return F;} 1819 1820 pnt base(){/* Base */ 1821 return I[10];} 1822 1823 pnt zero(){/* %% */ 1824 return Z;} 1825 1826 pnt unaryPlus(pnt x){/* + " */ 1827 if(NO_INT(x)) return X; 1828 return x;} 1829 1830 pnt plus1(pnt x,pnt y,pnt c){ 1831 pnt X=HEAD(x); 1832 pnt Y=HEAD(y); 1833 pnt u=HALFHEAD(X)+HALFHEAD(Y)+c; 1834 pnt v=HALFTAIL(X)+HALFTAIL(Y)+HALFTAIL(u); 1835 pnt w=HALFCONS(u,v); 1836 if(TAIL(x)||TAIL(y)) 1837 return intcons(w,plus1(inttail(x),inttail(y),HALFTAIL(v))); 1838 if(w&signmask){ 1839 if((X&signmask)||(Y&signmask)) 1840 return intcons(w,M); 1841 else 1842 return intcons(w,Z);} 1843 else{ 1844 if((!(X&signmask))||(!(Y&signmask))) 1845 return intcons(w,Z); 1846 else 1847 return intcons(w,M);}} 1848 1849 pnt plus(pnt x,pnt y){/* " + " */ 1850 if(NO_INT(x)) return X; 1851 if(NO_INT(y)) return X; 1852 return plus1(x,y,0);} 1853 1854 pnt minus(pnt x,pnt y){/* " - " */ 1855 if(NO_INT(x)) return X; 1856 if(NO_INT(y)) return X; 1857 push(x); 1858 return ret(1,plus1(x,lognot(y),1));} 1859 1860 pnt unaryMinus(pnt x){/* - " */ 1861 return minus(Z,x);} 1862 1863 pnt integerLength3(pnt x){ 1864 if(!x) return 0; 1865 return 1+integerLength3(x>>1);} 1866 1867 pnt integerLength2(pnt x){ 1868 if(x&signmask) return integerLength3(~x); 1869 return integerLength3(x);} 1870 1871 pnt integerCombine(pnt x,pnt y){ 1872 pnt u=HALFHEAD(y)*pntsize+x; 1873 pnt v=HALFTAIL(y)*pntsize+HALFTAIL(u); 1874 return intcons(HALFCONS(u,v),intcons(HALFTAIL(v),Z));} 1875 1876 pnt integerLength1(pnt x,pnt y){ 1877 if(TAIL(x)) return integerLength1(TAIL(x),y+1); 1878 return integerCombine(integerLength2(HEAD(x)),y);} 1879 1880 pnt integerLength(pnt x){/* integer-length ( " ) */ 1881 if(NO_INT(x)) return X; 1882 return integerLength1(x,0);} 1883 1884 pnt logcount2(pnt x){ 1885 if(!x) return 0; 1886 return (x&1)+logcount2(x>>1);} 1887 1888 pnt logcount1(pnt x,pnt y){ 1889 y=y+logcount2(HEAD(x)); 1890 if(y&signmask) die("logcount overflow"); 1891 if(TAIL(x)) return logcount1(TAIL(x),y); 1892 return intcons(y,Z);} 1893 1894 pnt logcount(pnt x){/* logcount ( " ) */ 1895 if(NO_INT(x)) return X; 1896 if(ge(x,Z)==T) return logcount1(x,0); 1897 return logcount1(lognot(x),0);} 1898 1899 /* compute 10*x+y */ 1900 pnt digit(pnt x,pnt y){ 1901 pnt x0=HEAD(x); 1902 pnt x1=HALFHEAD(x0)*10+y; 1903 pnt x2=HALFTAIL(x0)*10+HALFTAIL(x1); 1904 pnt x3=HALFCONS(x1,x2); 1905 pnt y1=HALFTAIL(x2); 1906 if(!TAIL(x)&&(y1==0)&&!(x3&signmask)) return intcons(x3,Z); 1907 if(!TAIL(x)&&(y1==9)&&(x3&signmask)) return intcons(x3,M); 1908 return intcons(x3,digit(inttail(x),y1));} 1909 1910 pnt digit0(pnt x){if(NO_INT(x)) return X;return digit(x,0);} /* " %0 */ 1911 pnt digit1(pnt x){if(NO_INT(x)) return X;return digit(x,1);} /* " %1 */ 1912 pnt digit2(pnt x){if(NO_INT(x)) return X;return digit(x,2);} /* " %2 */ 1913 pnt digit3(pnt x){if(NO_INT(x)) return X;return digit(x,3);} /* " %3 */ 1914 pnt digit4(pnt x){if(NO_INT(x)) return X;return digit(x,4);} /* " %4 */ 1915 pnt digit5(pnt x){if(NO_INT(x)) return X;return digit(x,5);} /* " %5 */ 1916 pnt digit6(pnt x){if(NO_INT(x)) return X;return digit(x,6);} /* " %6 */ 1917 pnt digit7(pnt x){if(NO_INT(x)) return X;return digit(x,7);} /* " %7 */ 1918 pnt digit8(pnt x){if(NO_INT(x)) return X;return digit(x,8);} /* " %8 */ 1919 pnt digit9(pnt x){if(NO_INT(x)) return X;return digit(x,9);} /* " %9 */ 1920 1921 pnt str2int1(char *str,pnt result){ 1922 if(*str==0) return result; 1923 if(*str=='-') return unaryMinus(str2int1(str+1,result)); 1924 if(*str<'0') return str2int1(str+1,result); 1925 if(*str>'9') return str2int1(str+1,result); 1926 return str2int1(str+1,digit(result,*str-'0'));} 1927 1928 pnt str2int0(unsigned char *str){ 1929 pnt result=store_find((pnt)2,str); 1930 if(result!=T) return result; 1931 return keep3((pnt)2,str,str2int1((char *)str,Z));} 1932 1933 pnt str2int(char *str){ 1934 return str2int0((unsigned char *)str);} 1935 1936 pnt alloc1(pnt x){ 1937 if(!x) return NIL; 1938 return icons(0,alloc1(TAIL(x)));} 1939 1940 pnt alloc2(pnt x,pnt y){ 1941 if(!x) return alloc1(y); 1942 return icons(0,alloc2(TAIL(x),y));} 1943 1944 pnt normalize(pnt x){ 1945 pnt u=HEAD(x); 1946 if(TAIL(x)) return intcons(u,normalize(TAIL(x))); 1947 if(u==0) return Z; 1948 if(u==~(pnt)0) return M; 1949 return x;} 1950 1951 /* 1952 x: First factor 1953 y: Second factor 1954 z: Product 1955 x1: Pointer which traverses x 1956 y1: Pointer which traverses y 1957 z1: Pointer which traverses z synchronously with x 1958 z2: Pointer which traverses z synchronously with y 1959 a: Current word from x 1960 b: Current word from y 1961 c1: Carry 1 1962 c2: Carry 2 1963 d0: Product, low half 1964 d1: Product, high half 1965 */ 1966 pnt umul(pnt x,pnt y){ 1967 pnt z,x1,y1,z1,z2,a,b,c1,c2,d0,d1,d2; 1968 z=alloc2(x,y); 1969 z1=z; 1970 for(x1=x;x1;x1=TAIL(x1)){ 1971 c1=0; 1972 z2=z1; 1973 a=HEAD(x1); 1974 for(y1=y;y1;y1=TAIL(y1)){ 1975 b=HEAD(y1); 1976 c2=HEAD(z2); 1977 d0=HALFHEAD(a)*HALFHEAD(b)+HALFHEAD(c1)+HALFHEAD(c2); 1978 d1=HALFHEAD(a)*HALFTAIL(b)+HALFTAIL(d0)+HALFTAIL(c1); 1979 d2=HALFTAIL(a)*HALFHEAD(b)+HALFHEAD(d1)+HALFTAIL(c2); 1980 c1=HALFTAIL(a)*HALFTAIL(b)+HALFTAIL(d1)+HALFTAIL(d2); 1981 HEAD(z2)=HALFCONS(d0,d2); 1982 z2=TAIL(z2); 1983 } 1984 HEAD(z2)=c1; 1985 z1=TAIL(z1); 1986 } 1987 return normalize(z);} 1988 1989 pnt times(pnt x,pnt y){/* " * " */ 1990 if(NO_INT(x)) return X; 1991 if(NO_INT(y)) return X; 1992 push(x); 1993 push(y); 1994 if(ge(x,Z)==T){ 1995 if(ge(y,Z)==T) return ret(2,umul(x,y)); 1996 push(unaryMinus(y)); 1997 return ret(3,unaryMinus(umul(x,stack[sp])));} 1998 push(unaryMinus(x)); 1999 if(ge(y,Z)==T) return ret(3,unaryMinus(umul(stack[sp],y))); 2000 push(unaryMinus(y)); 2001 return ret(4,umul(stack[sp],stack[sp+1]));} 2002 2003 pnt logbitp1(pnt x,pnt y){ 2004 if(!y) die("logbitp internal error"); 2005 if(x>=pntsize) return logbitp1(x-pntsize,TAIL(y)); 2006 if((HEAD(y)>>x)&1) return T; 2007 return F;} 2008 2009 pnt logbitp(pnt x,pnt y){/* logbitp ( " , " ) */ 2010 if(NO_INT(x)) return X; 2011 if(NO_INT(y)) return X; 2012 if(lt(x,Z)==T) return X; 2013 if(le(integerLength(y),x)==T) return lt(y,Z); 2014 if(TAIL(x)) die("logbitp overflow"); 2015 return logbitp1(HEAD(x),y);} 2016 2017 pnt asll(pnt x,pnt y){ 2018 if(y==0) return x; 2019 return intcons(0,asll(x,y-1));} 2020 2021 pnt asrr(pnt x,pnt y){ 2022 if(y==0) return x; 2023 return asrr(inttail(x),y-1);} 2024 2025 pnt asl1(pnt x,pnt y,pnt c){ 2026 pnt x1=HEAD(x); 2027 pnt x2=(x1<>(pntsize-y)); 2029 if(x==Z) return intcons(x2,Z); 2030 if(x==M) return intcons(x2,M); 2031 return intcons(x2,asl1(inttail(x),y,c2));} 2032 2033 pnt asl(pnt x,pnt y){ 2034 if(y==0) return x; 2035 return asl1(x,y,0);} 2036 2037 pnt asr(pnt x,pnt y){ 2038 if(y==0) return x; 2039 return inttail(asl1(x,pntsize-y,0));} 2040 2041 pnt ash(pnt x,pnt y){/* ash ( " , " ) */ 2042 pnt z; 2043 if(NO_INT(x)) return X; 2044 if(NO_INT(y)) return X; 2045 if(TAIL(y)) die("ash overflow"); 2046 z=HEAD(y); 2047 if(ge(y,Z)==T) return asll(asl(x,z%pntsize),z/pntsize); 2048 z=1+~z; 2049 return asrr(asr(x,z%pntsize),z/pntsize);} 2050 2051 /* 2052 The division algorithms below leave room for HUGE improvements. 2053 */ 2054 2055 /* Returns 2x */ 2056 pnt twice0(pnt x){ 2057 return asl1(x,1,0);} 2058 2059 /* Returns 2x+1 */ 2060 pnt twice1(pnt x){ 2061 return asl1(x,1,1);} 2062 2063 /* pairUnaryMinus(q::r)=(-q)::(-r) */ 2064 pnt pairUnaryMinus(pnt x){ 2065 pnt y=HEAD(x); 2066 pnt z=TAIL(x); 2067 push(z); 2068 y=unaryMinus(y); 2069 push(y); 2070 return ret(2,pair(y,unaryMinus(z)));} 2071 2072 /* divAdjust(q::r,d)=(q+1)::(r-d) */ 2073 pnt divAdjust(pnt x,pnt d){ 2074 pnt q=HEAD(x); 2075 pnt r=TAIL(x); 2076 push(q); 2077 r=minus(r,d); 2078 push(r); 2079 return ret(2,pair(plus(q,I[1]),r));} 2080 2081 /* 2082 Divide non-negative remainder with positive divisor. 2083 floor1(x,y) divides x by y and returns pair(quotient,remainder). 2084 The remainder satisfies 0 <= remainder < y. 2085 floor1 does not secure its first argument against GC. 2086 */ 2087 2088 pnt floor1(pnt dividend,pnt divisor){ 2089 pnt result,quotient,remainder,remainder1; 2090 push(divisor); 2091 if(lt(dividend,divisor)==T) return ret(1,pair(Z,dividend)); 2092 result=floor1(dividend,twice0(divisor)); 2093 push(result); 2094 quotient=HEAD(result); 2095 remainder=TAIL(result); 2096 remainder1=minus(remainder,divisor); 2097 if(lt(remainder1,Z)==T) return ret(2,pair(twice0(quotient),remainder)); 2098 push(remainder1); 2099 return ret(3,pair(twice1(quotient),remainder1));} 2100 2101 /* Version of floor which secures both arguments against GC */ 2102 pnt floor0(pnt dividend,pnt divisor){ 2103 push(dividend); 2104 return ret(1,floor1(dividend,divisor));} 2105 2106 /* dividend>=0, divisor>0 */ 2107 pnt ceiling0(pnt dividend,pnt divisor){ 2108 pnt result; 2109 result=floor0(dividend,divisor); 2110 if(TAIL(result)==Z) return result; 2111 return divAdjust(result,divisor);} 2112 2113 /* dividend>=0, divisor>0 */ 2114 pnt round0(pnt dividend,pnt divisor){ 2115 pnt result,result1; 2116 push(divisor); 2117 result=floor0(dividend,divisor); 2118 push(result); 2119 result1=cmp1(twice0(TAIL(result)),divisor); 2120 if(result1==0) return ret(2,result); 2121 if(result1==2) return ret(2,divAdjust(result,divisor)); 2122 if(evenp(HEAD(result))==T) return ret(2,result); 2123 return ret(2,divAdjust(result,divisor));} 2124 2125 pnt floorx(pnt x,pnt y){/* floor ( " , " ) */ 2126 if(NO_INT(x)) return X; 2127 if(NO_INT(y)) return X; 2128 if(le(y,Z)==T) return X; 2129 if(ge(x,Z)==T) return floor0(x,y); 2130 push(y); 2131 return ret(1,pairUnaryMinus(ceiling0(unaryMinus(x),y)));} 2132 2133 pnt ceilingx(pnt x,pnt y){/* ceiling ( " , " ) */ 2134 if(NO_INT(x)) return X; 2135 if(NO_INT(y)) return X; 2136 if(le(y,Z)==T) return X; 2137 if(ge(x,Z)==T) return ceiling0(x,y); 2138 push(y); 2139 return ret(1,pairUnaryMinus(floor0(unaryMinus(x),y)));} 2140 2141 pnt truncatex(pnt x,pnt y){/* truncate ( " , " ) */ 2142 if(NO_INT(x)) return X; 2143 if(NO_INT(y)) return X; 2144 if(le(y,Z)==T) return X; 2145 if(ge(x,Z)==T) return floor0(x,y); 2146 push(y); 2147 return ret(1,pairUnaryMinus(floor0(unaryMinus(x),y)));} 2148 2149 pnt roundx(pnt x,pnt y){/* round ( " , " ) */ 2150 if(NO_INT(x)) return X; 2151 if(NO_INT(y)) return X; 2152 if(le(y,Z)==T) return X; 2153 if(ge(x,Z)==T) return round0(x,y); 2154 push(y); 2155 return ret(1,pairUnaryMinus(round0(unaryMinus(x),y)));} 2156 2157 pnt divx(pnt x,pnt y){/* " div " */ 2158 if(NO_INT(x)) return X; 2159 if(NO_INT(y)) return X; 2160 if(le(y,Z)==T) return X; 2161 if(ge(x,Z)==T) return HEAD(floor0(x,y)); 2162 push(y); 2163 return ret(1,unaryMinus(HEAD(ceiling0(unaryMinus(x),y))));} 2164 2165 pnt modx(pnt x,pnt y){/* " mod " */ 2166 if(NO_INT(x)) return X; 2167 if(NO_INT(y)) return X; 2168 if(le(y,Z)==T) return X; 2169 if(ge(x,Z)==T) return TAIL(floor0(x,y)); 2170 push(y); 2171 return ret(1,unaryMinus(TAIL(ceiling0(unaryMinus(x),y))));} 2172 2173 2174 2175 pnt raise0(pnt x){/* " raise */ 2176 return cons(TAG_EX,x,NIL);} 2177 2178 pnt object(pnt x){/* object ( " ) */ 2179 pnt tag,ref,idx,val,cmp; 2180 if(NO_PAIR(x)) return X; 2181 tag=HEAD(x); 2182 val=TAIL(x); 2183 if(NO_PAIR(tag)) return X; 2184 ref=HEAD(tag); 2185 idx=TAIL(tag); 2186 if(NO_INT(ref)) return X; 2187 if(NO_INT(idx)) return X; 2188 cmp=cmp1(ref,Z); 2189 if(cmp==0) return X; 2190 if(T==lt(idx,I[(cmp==1)?5:0])) return X; 2191 return cons(TAG_OBJ,tag,val);} 2192 2193 pnt destruct(pnt x){/* destruct ( " ) */ 2194 if(NO_OBJ(x)) return X; 2195 return pair(HEAD(x),TAIL(x));} 2196 2197 pnt vector2(pnt x){ 2198 if(x<256) return 1; 2199 return (x&0xFF)|(vector2(x>>8)<<8);} 2200 2201 pnt vector1(pnt x){ 2202 pnt u=HEAD(x); 2203 pnt y=TAIL(x); 2204 if(y==NIL||y==Z) return consvec(vector2(u),NIL); 2205 return consvec(u,vector1(y));} 2206 2207 pnt vector(pnt x){/* vector ( " ) */ 2208 if(x==T) return X; 2209 switch(ROOT(x)){ 2210 case TAG_VECT: return x; 2211 case TAG_INT: 2212 if(le(x,Z)==T) return E; 2213 return vector1(x); 2214 default: return X;}} 2215 2216 pnt endlength(pnt x){ 2217 if(TAIL(x)) return endlength(TAIL(x)); 2218 return integerLength3(HEAD(x));} 2219 2220 pnt vectorNorm(pnt x){/* vector-norm ( " ) */ 2221 if(x==T) return X; 2222 switch(ROOT(x)){ 2223 case TAG_VECT: return x; 2224 case TAG_INT: 2225 if(le(x,Z)==T) return T; 2226 if(endlength(x)%8!=1) return T; 2227 return vector1(x); 2228 default: return X;}} 2229 2230 pnt vectorEmpty(pnt x){/* vector-empty ( " ) */ 2231 return le(x,I[255]);} 2232 2233 pnt vectorLength2(pnt x){ 2234 if(x<256) return 0; 2235 return 1+vectorLength2(x>>8);} 2236 2237 pnt vectorLength1(pnt x){ 2238 pnt y=TAIL(x); 2239 if((!y)||(y==Z)) return vectorLength2(HEAD(x)); 2240 return bytesize+vectorLength1(y);} 2241 2242 pnt negative(pnt x){ 2243 if(ROOT(x)==TAG_VECT) return FALSE; 2244 for(;TAIL(x);x=TAIL(x)); 2245 return (HEAD(x)&signmask)!=0;} 2246 2247 pnt vectorLength(pnt x){/* vector-length ( " ) */ 2248 if(NO_INT(x)) return X; 2249 if(negative(x)) return Z; 2250 return intcons(vectorLength1(x),Z);} 2251 2252 pnt vectorIndex2(pnt x,pnt y){ 2253 if(y==0) return x&0xFF; 2254 return vectorIndex2(x>>8,y-1);} 2255 2256 pnt vectorIndex1(pnt x,pnt y){ 2257 if(y=vectorLength1(x)) return X; 2266 return intcons(vectorIndex1(x,HEAD(y)),Z);} 2267 2268 pnt consvec1(pnt x,pnt y){ 2269 if(y) return consvec(x,y); 2270 if(x==0) return NIL; 2271 return consvec(vector2(x),NIL);} 2272 2273 pnt vectorSuffix2(pnt x,pnt y,pnt z){ 2274 pnt u=HEAD(x); 2275 pnt v=TAIL(x); 2276 if(v) return consvec1((u>>y)|(HEAD(v)<>y,NIL);} 2278 2279 pnt vectorSuffix1(pnt x,pnt y){ 2280 if(y==0) return vector(x); 2281 if(y>8,y-1)<<8);} 2295 2296 pnt vectorPrefix1(pnt x,pnt y){ 2297 pnt u=HEAD(x); 2298 if(y>y1)|(v<>y1)|(HEAD(v)<>8,y));} 2343 2344 pnt vector2bytes2(pnt x,pnt y,pnt z){ 2345 if(!y) return z; 2346 return pair(I[x&0xFF],vector2bytes2(x>>8,y-1,z));} 2347 2348 pnt vector2bytes1(pnt x,pnt y){ 2349 if(!TAIL(x)) return vector2bytes3(HEAD(x),y); 2350 return vector2bytes2(HEAD(x),bytesize,vector2bytes1(TAIL(x),y));} 2351 2352 pnt vector2bytes(pnt x){/* vector2byte* ( " ) */ 2353 if(NO_INT(x)) return X; 2354 if(negative(x)) return T; 2355 return vector2bytes1(x,T);} 2356 2357 pnt vector2vects3(pnt x,pnt y){ 2358 if(x<=255) return y; 2359 return pair(bytevect[x&0xFF],vector2vects3(x>>8,y));} 2360 2361 pnt vector2vects2(pnt x,pnt y,pnt z){ 2362 if(!y) return z; 2363 return pair(bytevect[x&0xFF],vector2vects2(x>>8,y-1,z));} 2364 2365 pnt vector2vects1(pnt x,pnt y){ 2366 if(!TAIL(x)) return vector2vects3(HEAD(x),y); 2367 return vector2vects2(HEAD(x),bytesize,vector2vects1(TAIL(x),y));} 2368 2369 pnt vector2vects(pnt x){/* vector2vector* ( " ) */ 2370 if(NO_INT(x)) return X; 2371 if(negative(x)) return T; 2372 return vector2vects1(x,T);} 2373 2374 pnt bt2bytes1(pnt x,pnt y){ 2375 if(x==T) return y; 2376 switch(ROOT(x)){ 2377 case TAG_FALSE: 2378 case TAG_MAP: 2379 case TAG_OBJ: 2380 return y; 2381 case TAG_INT: 2382 case TAG_VECT: 2383 if(TAIL(x)) return y; 2384 if(HEAD(x)>255) return y; 2385 return pair(x,y); 2386 case TAG_PAIR: 2387 push(x); 2388 return ret(1,bt2bytes1(HEAD(x),bt2bytes1(TAIL(x),y))); 2389 default: 2390 unexpected_tag("bt2bytes1",x); 2391 return T; /* This never happens */}} 2392 2393 pnt bt2bytes(pnt x){/* bt2byte* ( " ) */ 2394 return bt2bytes1(x,T);} 2395 2396 pnt bt2vects1(pnt x,pnt y){ 2397 if(x==T) return y; 2398 switch(ROOT(x)){ 2399 case TAG_FALSE: 2400 case TAG_MAP: 2401 case TAG_OBJ: 2402 return y; 2403 case TAG_INT: 2404 case TAG_VECT: 2405 if(TAIL(x)) return y; 2406 if(HEAD(x)>255) return y; 2407 return pair(bytevect[HEAD(x)],y); 2408 case TAG_PAIR: 2409 push(x); 2410 return ret(1,bt2vects1(HEAD(x),bt2vects1(TAIL(x),y))); 2411 default: 2412 unexpected_tag("bt2vects1",x); 2413 return T; /* This never happens */}} 2414 2415 pnt bt2vects(pnt x){/* bt2vector* ( " ) */ 2416 return bt2vects1(x,T);} 2417 2418 pnt vt2bytes1(pnt x,pnt y){ 2419 if(x==T) return y; 2420 switch(ROOT(x)){ 2421 case TAG_FALSE: 2422 case TAG_MAP: 2423 case TAG_OBJ: 2424 return y; 2425 case TAG_INT: 2426 case TAG_VECT: 2427 if(negative(x)) return y; 2428 return vector2bytes1(x,y); 2429 case TAG_PAIR: 2430 push(x); 2431 return ret(1,vt2bytes1(HEAD(x),vt2bytes1(TAIL(x),y))); 2432 default: 2433 unexpected_tag("bt2bytes1",x); 2434 return T; /* This never happens */}} 2435 2436 pnt vt2bytes(pnt x){/* vt2byte* ( " ) */ 2437 return vt2bytes1(x,T);} 2438 2439 pnt vt2vects1(pnt x,pnt y){ 2440 if(x==T) return y; 2441 switch(ROOT(x)){ 2442 case TAG_FALSE: 2443 case TAG_MAP: 2444 case TAG_OBJ: 2445 return y; 2446 case TAG_INT: 2447 case TAG_VECT: 2448 if(negative(x)) return y; 2449 return vector2vects1(x,y); 2450 case TAG_PAIR: 2451 push(x); 2452 return ret(1,vt2vects1(HEAD(x),vt2vects1(TAIL(x),y))); 2453 default: 2454 unexpected_tag("vt2vects1",x); 2455 return T; /* This never happens */}} 2456 2457 pnt vt2vects(pnt x){/* vt2vector* ( " ) */ 2458 return vt2vects1(x,T);} 2459 2460 pnt bytes2vector(pnt n,pnt x){ 2461 pnt u,y; 2462 if(x==T) return consvec(1,NIL); 2463 u=HEAD(HEAD(x)); 2464 if(n==bytesize) return consvec(u,bytes2vector(1,TAIL(x))); 2465 y=bytes2vector(n+1,TAIL(x)); 2466 HEAD(y)=(HEAD(y)<<8)|u; 2467 return y;} 2468 2469 pnt bt2vector(pnt x){/* bt2vector ( " ) */ 2470 return bytes2vector(1,bt2bytes(x));} 2471 2472 pnt vt2vector(pnt x){/* vt2vector ( " ) */ 2473 return bytes2vector(1,vt2bytes(x));} 2474 2475 pnt spy(pnt x){/* spy ( " ) */ 2476 spyvar=x; 2477 return const_spy;} 2478 2479 pnt trace(pnt x){/* trace ( " ) */ 2480 spy0(x); 2481 return const_trace;} 2482 2483 pnt print(pnt x){/* print ( " ) */ 2484 print1(x); 2485 return const_print;} 2486 2487 pnt timer(pnt x){/* timer ( " ) */ 2488 if(x==T) setTimer(-1); 2489 else if(ROOT(x)!=TAG_INT&&ROOT(x)!=TAG_VECT) setTimer(-1); 2490 else if(TAIL(x)!=NIL) setTimer(-1); 2491 else if(HEAD(x)>TIMERS) setTimer(-1); 2492 else setTimer(HEAD(x)); 2493 return const_timer;} 2494 2495 2496 2497 /********************* 2498 * GENERAL FUNCTIONS * 2499 *********************/ 2500 2501 pnt term_apply(pnt fct,pnt arg){ 2502 return cons(TTAG_APPLY,fct,arg);} 2503 2504 pnt term_lambda(pnt body){ 2505 return cons(TTAG_LAMBDA,body,NIL);} 2506 2507 pnt term_lambdas(pnt arity,pnt body){ 2508 if(arity==0) return body; 2509 return term_lambda(term_lambdas(arity-1,body));} 2510 2511 pnt term_call(pnt fct,pnt arg){ 2512 return cons(TTAG_CALL,fct,arg);} 2513 2514 pnt term_ecall(pnt fct,pnt arg){ 2515 return cons(TTAG_ECALL,fct,arg);} 2516 2517 pnt term_var(pnt index){ 2518 return cons2(TTAG_VAR,index,NIL);} 2519 2520 pnt term_pair(pnt x,pnt y){ 2521 return cons(TTAG_PAIR,x,y);} 2522 2523 pnt term_const(pnt x){ 2524 return cons(TTAG_CONST,x,NIL);} 2525 2526 pnt closure(pnt term,pnt env){ 2527 return cons(MTAG_CLOSURE,term,env);} 2528 2529 pnt overwrite(pnt closure,pnt rnf){ 2530 ROOT(closure)=MTAG_INDIR; 2531 TAIL(closure)=rnf; 2532 return rnf;} 2533 2534 pnt map_pair(pnt x,pnt y){ 2535 return cons(MTAG_PAIR,x,y);} 2536 2537 pnt map_lambda(pnt term,pnt env){ 2538 return cons(MTAG_LAMBDA,term,env);} 2539 2540 pnt bit2map(pnt x){ 2541 if(x&1) return map_f; else return map_t;} 2542 2543 pnt small2rnf(pnt card){ 2544 if(card==0) return T; 2545 return map_pair(bit2map(card),small2rnf(card>>1));} 2546 2547 pnt card2rnf1(pnt card,pnt cnt,pnt result){ 2548 if(cnt==0) return result; 2549 return map_pair(bit2map(card),card2rnf1(card>>1,cnt-1,result));} 2550 2551 pnt card2rnf(pnt card){ 2552 pnt tmp1; 2553 if(TAIL(card)==T) return small2rnf(HEAD(card)); 2554 tmp1=HEAD(card); 2555 return card2rnf1(tmp1,pntsize,card2rnf(TAIL(card)));} 2556 2557 pnt map2rnf(pnt map){ 2558 if(map==T) return T; 2559 switch(ROOT(map)){ 2560 case MTAG_INDIR: return TAIL(map); 2561 case MTAG_CLOSURE: 2562 push(map); 2563 return ret(1,overwrite(map,term2rnf(HEAD(map),TAIL(map)))); 2564 case MTAG_PAIR: 2565 case MTAG_LAMBDA: 2566 case MTAG_FIX: 2567 case TAG_FALSE: 2568 case TAG_INT: 2569 case TAG_VECT: 2570 case TAG_PAIR: 2571 case TAG_EX: 2572 case TAG_MAP: 2573 case TAG_OBJ: 2574 return map; 2575 default: 2576 unexpected_tag("map2rnf",map); 2577 return T; /* This never happens */}} 2578 2579 pnt fixpoint(pnt map){ 2580 pnt env=map_pair(T,map_pair(map,T)); 2581 pnt result=closure(term_fix,env); 2582 HEAD(env)=result; 2583 return map2rnf(result);} 2584 2585 void spyenv(pnt env){for(;env;env=TAIL(env)) spy0(HEAD(env));} 2586 2587 pnt terms2closures(pnt terms,pnt env){ 2588 pnt closure0; 2589 if(terms==NIL) return NIL; 2590 closure0=closure(HEAD(terms),env); 2591 push(closure0); 2592 return ret(1,map_pair(closure0,terms2closures(TAIL(terms),env)));} 2593 2594 pnt terms2tagged(pnt terms,pnt env){ 2595 pnt tagged1,tagged2; 2596 if(terms==NIL) return NIL; 2597 tagged2=terms2tagged(TAIL(terms),env); 2598 if(IS_EX(tagged2)) return tagged2; 2599 push(tagged2); 2600 tagged1=untag1(term2rnf(HEAD(terms),env)); 2601 if(IS_EX(tagged1)) return ret(1,tagged1); 2602 return ret(1,pair(tagged1,tagged2));} 2603 2604 pnt map_apply(pnt map,pnt arg){ 2605 pnt rnf; 2606 push(arg); 2607 push(rnf=map2rnf(map)); 2608 if(rnf==T) return ret(2,rnf); 2609 switch(ROOT(rnf)){ 2610 case MTAG_PAIR: 2611 if(map2rnf(arg)==T) return ret(2,map2rnf(HEAD(rnf))); 2612 return ret(2,map2rnf(TAIL(rnf))); 2613 case MTAG_LAMBDA: 2614 return ret(2,term2rnf(HEAD(rnf),map_pair(arg,TAIL(rnf)))); 2615 case MTAG_FIX: 2616 return ret(2,fixpoint(arg)); 2617 case TAG_FALSE: 2618 map2rnf(arg); /* ensure infinite looping when appropriate */ 2619 return ret(2,T); 2620 case TAG_INT: 2621 case TAG_VECT: 2622 if(T==map2rnf(arg)) return ret(2,maptag_int); 2623 if(negative(rnf)) return ret(2,map_pair(map_f,card2rnf(unaryMinus(rnf)))); 2624 return ret(2,map_pair(map_t,card2rnf(rnf))); 2625 case TAG_PAIR: 2626 if(T==map2rnf(arg)) return ret(2,maptag_pair); 2627 return ret(2,map_pair(HEAD(rnf),TAIL(rnf))); 2628 case TAG_EX: 2629 if(T==map2rnf(arg)) return ret(2,maptag_ex); 2630 return ret(2,HEAD(rnf)); 2631 case TAG_MAP: 2632 if(T==map2rnf(arg)) return ret(2,maptag_map); 2633 return ret(2,map2rnf(HEAD(rnf))); 2634 case TAG_OBJ: 2635 if(map2rnf(arg)!=T) return ret(2,TAIL(rnf)); 2636 return ret(2, 2637 MAP_PAIR(card2rnf(HEAD(HEAD(rnf))),card2rnf(TAIL(HEAD(rnf))))); 2638 default: 2639 unexpected_tag("map_apply",rnf); 2640 return T; /* This never happens */}} 2641 2642 pnt term2rnf(pnt term,pnt env){ 2643 push(term); 2644 push(env); 2645 switch(ROOT(term)){ 2646 case TTAG_APPLY:{ 2647 pnt rnf; 2648 rnf=term2rnf(HEAD(term),env); 2649 if(rnf==T) return ret(2,T); 2650 push(rnf); 2651 switch(ROOT(rnf)){ 2652 case MTAG_PAIR: 2653 if(T==term2rnf(TAIL(term),env)) return ret(3,map2rnf(HEAD(rnf))); 2654 return ret(3,map2rnf(TAIL(rnf))); 2655 case MTAG_LAMBDA: 2656 return ret(3, 2657 term2rnf(HEAD(rnf),map_pair(closure(TAIL(term),env),TAIL(rnf)))); 2658 case MTAG_FIX: 2659 return ret(3,fixpoint(term2rnf(TAIL(term),env))); 2660 case TAG_FALSE: 2661 term2rnf(TAIL(term),env); /* ensure infinite looping when appropriate */ 2662 return ret(3,NIL); 2663 case TAG_INT: 2664 case TAG_VECT: 2665 if(T==term2rnf(TAIL(term),env)) return ret(3,maptag_int); 2666 if(negative(rnf)) return ret(3,map_pair(map_f,card2rnf(unaryMinus(rnf)))); 2667 return ret(3,map_pair(map_t,card2rnf(rnf))); 2668 case TAG_PAIR: 2669 if(T==term2rnf(TAIL(term),env)) return ret(3,maptag_pair); 2670 return ret(3,map_pair(HEAD(rnf),TAIL(rnf))); 2671 case TAG_EX: 2672 if(T==term2rnf(TAIL(term),env)) return ret(3,maptag_ex); 2673 return ret(3,HEAD(rnf)); 2674 case TAG_MAP: 2675 if(T==term2rnf(TAIL(term),env)) return ret(3,maptag_map); 2676 return ret(3,map2rnf(HEAD(rnf))); 2677 case TAG_OBJ: 2678 if(term2rnf(TAIL(term),env)) return ret(3,TAIL(rnf)); 2679 return ret(3, 2680 MAP_PAIR(card2rnf(HEAD(HEAD(rnf))),card2rnf(TAIL(HEAD(rnf))))); 2681 default: 2682 unexpected_tag("term2rnf/apply",rnf);}} 2683 case TTAG_LAMBDA: 2684 return ret(2,map_lambda(HEAD(term),env)); 2685 case TTAG_CALL:{ 2686 /* current version allows call of n-ary CLOSED terms */ 2687 return ret(2,term2rnf(HEAD(term),terms2closures(TAIL(term),env)));} 2688 case TTAG_ECALL:{ 2689 pnt args; 2690 /* current version allows call of n-ary CLOSED terms */ 2691 args=terms2tagged(TAIL(term),env); 2692 if(IS_EX(args)) return ret(2,args); 2693 push(args); 2694 return ret(3,eval(HEAD(term),args));} 2695 case TTAG_VAR:{ 2696 pnt i; 2697 pnt n=HEAD(term); 2698 for(i=0;i0;cnt--) result=TAIL(result); 2869 result=HEAD(result); 2870 goto unstack; 2871 case ETAG_ecall: 2872 push(env); 2873 push(HEAD(term)); 2874 term=TAIL(term); 2875 if(term==T){ 2876 env=T; 2877 term=pop(); 2878 push(env); 2879 push(bytevect[ETAG_ecall]); 2880 goto resume;} 2881 push(TAIL(term)); 2882 push(T); 2883 push(I[ETAG_ecall]); 2884 term=HEAD(term); 2885 goto resume; 2886 STACK1(ETAG_digit0 ) 2887 STACK1(ETAG_digit1 ) 2888 STACK1(ETAG_digit2 ) 2889 STACK1(ETAG_digit3 ) 2890 STACK1(ETAG_digit4 ) 2891 STACK1(ETAG_digit5 ) 2892 STACK1(ETAG_digit6 ) 2893 STACK1(ETAG_digit7 ) 2894 STACK1(ETAG_digit8 ) 2895 STACK1(ETAG_digit9 ) 2896 STACK2(ETAG_times ) 2897 STACK2(ETAG_plus ) 2898 STACK2(ETAG_minus ) 2899 STACK2(ETAG_and ) 2900 STACK2(ETAG_or ) 2901 STACK2(ETAG_then ) 2902 STACK2(ETAG_pair ) 2903 STACK2(ETAG_lt ) 2904 STACK2(ETAG_le ) 2905 STACK2(ETAG_equal ) 2906 STACK2(ETAG_gt ) 2907 STACK2(ETAG_ge ) 2908 STACK2(ETAG_apply ) 2909 STACK1(ETAG_boolp ) 2910 STACK1(ETAG_catch ) 2911 STACK1(ETAG_maptag1 ) 2912 STACK2(ETAG_div ) 2913 STACK1(ETAG_head ) 2914 STACK1(ETAG_intp ) 2915 STACK2(ETAG_boolg ) 2916 STACK2(ETAG_intg ) 2917 STACK2(ETAG_mapg ) 2918 STACK2(ETAG_objg ) 2919 STACK2(ETAG_pairg ) 2920 STACK1(ETAG_mapp ) 2921 STACK1(ETAG_maptag ) 2922 STACK2(ETAG_mod ) 2923 STACK1(ETAG_norm ) 2924 STACK1(ETAG_objp ) 2925 STACK1(ETAG_pairp ) 2926 STACK1(ETAG_raise ) 2927 STACK1(ETAG_root ) 2928 STACK1(ETAG_tail ) 2929 STACK1(ETAG_untag ) 2930 STACK0(ETAG_digitend ,zero ) 2931 STACK1(ETAG_par ) 2932 STACK1(ETAG_uplus ) 2933 STACK1(ETAG_dplus ) 2934 STACK1(ETAG_uminus ) 2935 STACK1(ETAG_dminus ) 2936 STACK1(ETAG_not ) 2937 STACK0(ETAG_Base ,base ) 2938 STACK2(ETAG_LET ) 2939 STACK2(ETAG_ash ) 2940 STACK0(ETAG_bottom ,bottom ) 2941 STACK1(ETAG_bt2bytes ) 2942 STACK1(ETAG_bt2vects ) 2943 STACK1(ETAG_bt2vector ) 2944 STACK2(ETAG_ceiling ) 2945 STACK1(ETAG_destruct ) 2946 STACK1(ETAG_evenp ) 2947 STACK0(ETAG_exception ,exception ) 2948 STACK0(ETAG_false ,false ) 2949 STACK2(ETAG_floor ) 2950 STACK1(ETAG_half ) 2951 case ETAG_if: 2952 push(TAIL(term)); 2953 push(I[ETAG_if]); 2954 term=HEAD(term); 2955 goto resume; 2956 STACK1(ETAG_intlength ) 2957 STACK2(ETAG_logand ) 2958 STACK2(ETAG_logandc1 ) 2959 STACK2(ETAG_logandc2 ) 2960 STACK2(ETAG_logbitp ) 2961 STACK1(ETAG_logcount ) 2962 STACK2(ETAG_logeqv ) 2963 STACK2(ETAG_logior ) 2964 STACK2(ETAG_lognand ) 2965 STACK2(ETAG_lognor ) 2966 STACK1(ETAG_lognot ) 2967 STACK2(ETAG_logorc1 ) 2968 STACK2(ETAG_logorc2 ) 2969 STACK2(ETAG_logtest ) 2970 STACK2(ETAG_logxor ) 2971 case ETAG_map: 2972 result=mapcons(TAIL(term)); 2973 goto unstack; 2974 STACK1(ETAG_prenorm ) 2975 STACK1(ETAG_notnot ) 2976 STACK1(ETAG_object ) 2977 STACK1(ETAG_print ) 2978 STACK2(ETAG_round ) 2979 STACK1(ETAG_spy ) 2980 STACK1(ETAG_timer ) 2981 STACK1(ETAG_trace ) 2982 STACK2(ETAG_truncate ) 2983 STACK1(ETAG_vector ) 2984 STACK1(ETAG_vnorm ) 2985 STACK1(ETAG_vempty ) 2986 STACK2(ETAG_vindex ) 2987 STACK1(ETAG_vlength ) 2988 STACK2(ETAG_vprefix ) 2989 STACK2(ETAG_vsubseq ) /* STACK2 also applicable for arity 3 */ 2990 STACK2(ETAG_vsuffix ) 2991 STACK1(ETAG_v2bytes ) 2992 STACK1(ETAG_v2vects ) 2993 STACK1(ETAG_vt2bytes ) 2994 STACK1(ETAG_vt2vects ) 2995 STACK1(ETAG_vt2v ) 2996 STACK1(ETAG_compile ) 2997 STACK1(ETAG_ripemd ) 2998 STACK1(ETAG_sl2rack ) 2999 STACK1(ETAG_rack2sl ) 3000 /* GRD-2009-04-19: Ensure eager constants evaluated once only. */ 3001 case MTAG_INDIR: 3002 result=TAIL(term); 3003 goto unstack; 3004 case MTAG_CLOSURE: 3005 push(term); 3006 result=overwrite(term,term2rnf(HEAD(term),TAIL(term))); 3007 pop(); 3008 goto unstack; 3009 default: unexpected_tag("eval",term);} 3010 unstack: 3011 switch(HEAD(pop())){ 3012 case STOP: 3013 return result; 3014 case ETAG_ecall: 3015 if(IS_EX(result)){sp+=4;goto unstack;} 3016 result=pair(result,pop()); 3017 term=pop(); 3018 if(term==T){ 3019 env=result; 3020 term=pop(); 3021 push(env); 3022 push(bytevect[ETAG_ecall]); 3023 goto resume;} 3024 push(TAIL(term)); 3025 push(result); 3026 push(I[ETAG_ecall]); 3027 term=HEAD(term); 3028 goto resume; 3029 case ETAG_ecall+256: 3030 pop(); 3031 env=pop(); 3032 goto unstack; 3033 UNSTACK1(ETAG_digit0 ,digit0 ) 3034 UNSTACK1(ETAG_digit1 ,digit1 ) 3035 UNSTACK1(ETAG_digit2 ,digit2 ) 3036 UNSTACK1(ETAG_digit3 ,digit3 ) 3037 UNSTACK1(ETAG_digit4 ,digit4 ) 3038 UNSTACK1(ETAG_digit5 ,digit5 ) 3039 UNSTACK1(ETAG_digit6 ,digit6 ) 3040 UNSTACK1(ETAG_digit7 ,digit7 ) 3041 UNSTACK1(ETAG_digit8 ,digit8 ) 3042 UNSTACK1(ETAG_digit9 ,digit9 ) 3043 UNSTACK2(ETAG_times ,times ) 3044 UNSTACK2(ETAG_plus ,plus ) 3045 UNSTACK2(ETAG_minus ,minus ) 3046 case ETAG_and: 3047 term=pop(); 3048 if(result!=T) goto unstack; 3049 goto resume; 3050 case ETAG_or: 3051 term=pop(); 3052 if(result==T) goto unstack; 3053 if(IS_EX(result)) goto unstack; 3054 goto resume; 3055 UNSTACK2(ETAG_then ,then ) 3056 UNSTACK2(ETAG_pair ,pair ) 3057 UNSTACK2(ETAG_lt ,lt ) 3058 UNSTACK2(ETAG_le ,le ) 3059 UNSTACK2(ETAG_equal ,eq ) 3060 UNSTACK2(ETAG_gt ,gt ) 3061 UNSTACK2(ETAG_ge ,ge ) 3062 UNSTACK2(ETAG_apply ,apply ) 3063 UNSTACK1(ETAG_boolp ,boolp ) 3064 case ETAG_catch: 3065 result=IS_EX(result)?pair(T,HEAD(result)):pair(F,result); 3066 goto unstack; 3067 case ETAG_maptag1: 3068 result=mapcons(result); 3069 goto unstack; 3070 UNSTACK2(ETAG_div ,divx ) 3071 UNSTACK1(ETAG_head ,head ) 3072 UNSTACK1(ETAG_intp ,intp ) 3073 UNSTACK2(ETAG_boolg ,boolg ) 3074 UNSTACK2(ETAG_intg ,intg ) 3075 UNSTACK2(ETAG_mapg ,mapg ) 3076 UNSTACK2(ETAG_objg ,objg ) 3077 UNSTACK2(ETAG_pairg ,pairg ) 3078 UNSTACK1(ETAG_mapp ,mapp ) 3079 UNSTACK1(ETAG_maptag ,mapcons ) 3080 UNSTACK2(ETAG_mod ,modx ) 3081 UNSTACK1(ETAG_norm ,norm ) 3082 UNSTACK1(ETAG_objp ,objp ) 3083 UNSTACK1(ETAG_pairp ,pairp ) 3084 UNSTACK1(ETAG_raise ,raise0 ) 3085 UNSTACK1(ETAG_root ,root ) 3086 UNSTACK1(ETAG_tail ,tail ) 3087 UNSTACK1(ETAG_untag ,untag ) 3088 UNSTACK1(ETAG_par ,norm ) 3089 UNSTACK1(ETAG_uplus ,unaryPlus ) 3090 UNSTACK1(ETAG_dplus ,unaryPlus ) 3091 UNSTACK1(ETAG_uminus ,unaryMinus ) 3092 UNSTACK1(ETAG_dminus ,unaryMinus ) 3093 UNSTACK1(ETAG_not ,not ) 3094 case ETAG_LET: 3095 term=pop(); 3096 if(IS_EX(result)) goto unstack; 3097 env=pair(result,env); 3098 push(env); 3099 push(bytevect[ETAG_LET]); 3100 goto resume; 3101 case ETAG_LET+256: 3102 env=TAIL(pop()); 3103 goto unstack; 3104 UNSTACK2(ETAG_ash ,ash ) 3105 UNSTACK1(ETAG_bt2bytes ,bt2bytes ) 3106 UNSTACK1(ETAG_bt2vects ,bt2vects ) 3107 UNSTACK1(ETAG_bt2vector,bt2vector ) 3108 UNSTACK2(ETAG_ceiling ,ceilingx ) 3109 UNSTACK1(ETAG_destruct ,destruct ) 3110 UNSTACK1(ETAG_evenp ,evenp ) 3111 UNSTACK2(ETAG_floor ,floorx ) 3112 UNSTACK1(ETAG_half ,half ) 3113 case ETAG_if: 3114 if(result==T){term=HEAD(pop());goto resume;} 3115 if(IS_EX(result)){pop();goto unstack;} 3116 term=TAIL(pop());goto resume; 3117 UNSTACK1(ETAG_intlength,integerLength) 3118 UNSTACK2(ETAG_logand ,logand ) 3119 UNSTACK2(ETAG_logandc1 ,logandc1 ) 3120 UNSTACK2(ETAG_logandc2 ,logandc2 ) 3121 UNSTACK2(ETAG_logbitp ,logbitp ) 3122 UNSTACK1(ETAG_logcount ,logcount ) 3123 UNSTACK2(ETAG_logeqv ,logeqv ) 3124 UNSTACK2(ETAG_logior ,logior ) 3125 UNSTACK2(ETAG_lognand ,lognand ) 3126 UNSTACK2(ETAG_lognor ,lognor ) 3127 UNSTACK1(ETAG_lognot ,lognot ) 3128 UNSTACK2(ETAG_logorc1 ,logorc1 ) 3129 UNSTACK2(ETAG_logorc2 ,logorc2 ) 3130 UNSTACK2(ETAG_logtest ,logtest ) 3131 UNSTACK2(ETAG_logxor ,logxor ) 3132 UNSTACK1(ETAG_prenorm ,norm ) 3133 UNSTACK1(ETAG_notnot ,notnot ) 3134 UNSTACK1(ETAG_object ,object ) 3135 UNSTACK1(ETAG_print ,print ) 3136 UNSTACK2(ETAG_round ,roundx ) 3137 UNSTACK1(ETAG_spy ,spy ) 3138 UNSTACK1(ETAG_timer ,timer ) 3139 UNSTACK1(ETAG_trace ,trace ) 3140 UNSTACK2(ETAG_truncate ,truncatex ) 3141 UNSTACK1(ETAG_vector ,vector ) 3142 UNSTACK1(ETAG_vnorm ,vectorNorm ) 3143 UNSTACK1(ETAG_vempty ,vectorEmpty ) 3144 UNSTACK2(ETAG_vindex ,vectorIndex ) 3145 UNSTACK1(ETAG_vlength ,vectorLength ) 3146 UNSTACK2(ETAG_vprefix ,vectorPrefix ) 3147 case ETAG_vsubseq: 3148 term=pop(); 3149 if(IS_EX(result)) goto unstack; 3150 push(result); 3151 push(TAIL(term)); 3152 push(bytevect[ETAG_vsubseq]); 3153 term=HEAD(term); 3154 goto resume; 3155 case ETAG_vsubseq+256: 3156 term=pop(); 3157 if(IS_EX(result)){pop();goto unstack;} 3158 push(result); 3159 push(I[ETAG_vsubseq2]); 3160 goto resume; 3161 case ETAG_vsubseq2: 3162 term=pop(); 3163 cnt=pop(); 3164 if(IS_EX(result)) goto unstack; 3165 result=vectorSubseq(cnt,term,result); 3166 goto unstack; 3167 UNSTACK2(ETAG_vsuffix ,vectorSuffix ) 3168 UNSTACK1(ETAG_v2bytes ,vector2bytes ) 3169 UNSTACK1(ETAG_v2vects ,vector2vects ) 3170 UNSTACK1(ETAG_vt2bytes ,vt2bytes ) 3171 UNSTACK1(ETAG_vt2vects ,vt2vects ) 3172 UNSTACK1(ETAG_vt2v ,vt2vector ) 3173 UNSTACK1(ETAG_compile ,compile ) 3174 UNSTACK1(ETAG_ripemd ,ripemd ) 3175 UNSTACK1(ETAG_sl2rack ,sl2rack ) 3176 UNSTACK1(ETAG_rack2sl ,rack2sl ) 3177 default: 3178 die("Internal error in eval: stack corrupted"); 3179 return T; /* This never happens */}} 3180 3181 /* 3182 GRD-2009-07-20: The eval() below was replaced by the one above 3183 to save a lot of C-stack. Here, the 'C-stack' is the one used 3184 by C for function calls. The change of eval() does not save 3185 space in the stack[] array. Saving C-stack is useful on Linux 3186 and essential on Cygwin. 3187 3188 pnt R0; 3189 3190 #define EVAL0(fct) \ 3191 return fct(); 3192 3193 #define EVAL1(fct) \ 3194 R0=eval(TAIL(term),env); \ 3195 if(IS_EX(R0)) return R0; \ 3196 return fct(R0); 3197 3198 #define EVAL2(fct) \ 3199 R0=eval(HEAD(term),env); \ 3200 if(IS_EX(R0)) return R0; \ 3201 push(R0); \ 3202 R0=eval(TAIL(term),env); \ 3203 if(IS_EX(R0)) return ret(1,R0); \ 3204 return ret(1,fct(TOP,R0)); 3205 3206 #define EVAL3(fct) \ 3207 R0=eval(HEAD(term),env); \ 3208 if(IS_EX(R0)) return R0; \ 3209 push(R0); \ 3210 R0=eval(HEAD(TAIL(term)),env); \ 3211 if(IS_EX(R0)) return ret(1,R0); \ 3212 push(R0); \ 3213 R0=eval(TAIL(TAIL(term)),env); \ 3214 if(IS_EX(R0)) return ret(2,R0); \ 3215 return ret(2,fct(stack[sp+1],TOP,R0)); 3216 3217 pnt eval(pnt term,pnt env){ 3218 pnt u,v; 3219 if(term==T) return T; 3220 switch(ROOT(term)){ 3221 case TAG_FALSE: 3222 case TAG_INT: 3223 case TAG_VECT: 3224 case TAG_PAIR: 3225 case TAG_EX: 3226 case TAG_MAP: 3227 case TAG_OBJ: 3228 return term; 3229 case ETAG_var : 3230 for(R0=HEAD(term);R0>0;R0--) env=TAIL(env); 3231 return HEAD(env); 3232 case ETAG_ecall : 3233 push(T); 3234 for(u=TAIL(term);u!=T;u=TAIL(u)){ 3235 v=eval(HEAD(u),env); 3236 if(IS_EX(v)) return ret(1,v); 3237 TOP=cons(TAG_PAIR,v,TOP);} 3238 return ret(1,eval(HEAD(term),TOP)); 3239 case ETAG_digit0 : EVAL1(digit0 ) 3240 case ETAG_digit1 : EVAL1(digit1 ) 3241 case ETAG_digit2 : EVAL1(digit2 ) 3242 case ETAG_digit3 : EVAL1(digit3 ) 3243 case ETAG_digit4 : EVAL1(digit4 ) 3244 case ETAG_digit5 : EVAL1(digit5 ) 3245 case ETAG_digit6 : EVAL1(digit6 ) 3246 case ETAG_digit7 : EVAL1(digit7 ) 3247 case ETAG_digit8 : EVAL1(digit8 ) 3248 case ETAG_digit9 : EVAL1(digit9 ) 3249 case ETAG_times : EVAL2(times ) 3250 case ETAG_plus : EVAL2(plus ) 3251 case ETAG_minus : EVAL2(minus ) 3252 case ETAG_and : 3253 R0=eval(HEAD(term),env); 3254 if(R0!=T) return R0; 3255 return eval(TAIL(term),env); 3256 case ETAG_or : 3257 R0=eval(HEAD(term),env); 3258 if(R0==T) return T; 3259 if(IS_EX(R0)) return R0; 3260 return eval(TAIL(term),env); 3261 case ETAG_then : EVAL2(then ) 3262 case ETAG_pair : EVAL2(pair ) 3263 case ETAG_lt : EVAL2(lt ) 3264 case ETAG_le : EVAL2(le ) 3265 case ETAG_equal : EVAL2(eq ) 3266 case ETAG_gt : EVAL2(gt ) 3267 case ETAG_ge : EVAL2(ge ) 3268 case ETAG_apply : EVAL2(apply ) 3269 case ETAG_boolp : EVAL1(boolp ) 3270 case ETAG_catch : 3271 R0=eval(TAIL(term),env); 3272 if(IS_EX(R0)) return pair(T,HEAD(R0)); 3273 return pair(F,R0); 3274 case ETAG_maptag1 : 3275 return mapcons(eval(TAIL(term),env)); 3276 case ETAG_div : EVAL2(divx ) 3277 case ETAG_head : EVAL1(head ) 3278 case ETAG_intp : EVAL1(intp ) 3279 case ETAG_boolg : EVAL2(boolg ) 3280 case ETAG_intg : EVAL2(intg ) 3281 case ETAG_mapg : EVAL2(mapg ) 3282 case ETAG_objg : EVAL2(objg ) 3283 case ETAG_pairg : EVAL2(pairg ) 3284 case ETAG_mapp : EVAL1(mapp ) 3285 case ETAG_maptag : 3286 R0=eval(TAIL(term),env); 3287 if(IS_EX(R0)) return R0; 3288 return mapcons(R0); 3289 case ETAG_mod : EVAL2(modx ) 3290 case ETAG_norm : EVAL1(norm ) 3291 case ETAG_objp : EVAL1(objp ) 3292 case ETAG_pairp : EVAL1(pairp ) 3293 case ETAG_raise : EVAL1(raise0 ) 3294 case ETAG_root : EVAL1(root ) 3295 case ETAG_tail : EVAL1(tail ) 3296 case ETAG_untag : EVAL1(untag ) 3297 case ETAG_digitend : EVAL0(zero ) 3298 case ETAG_par : EVAL1(norm ) 3299 case ETAG_uplus : EVAL1(unaryPlus ) 3300 case ETAG_dplus : EVAL1(unaryPlus ) 3301 case ETAG_uminus : EVAL1(unaryMinus ) 3302 case ETAG_dminus : EVAL1(unaryMinus ) 3303 case ETAG_not : EVAL1(not ) 3304 case ETAG_Base : EVAL0(base ) 3305 case ETAG_LET : 3306 R0=eval(HEAD(term),env); 3307 if(IS_EX(R0)) return R0; 3308 R0=pair(R0,env); 3309 push(R0); 3310 return ret(1,eval(TAIL(term),R0)); 3311 case ETAG_ash : EVAL2(ash ) 3312 case ETAG_bottom : EVAL0(bottom ) 3313 case ETAG_bt2bytes : EVAL1(bt2bytes ) 3314 case ETAG_bt2vects : EVAL1(bt2vects ) 3315 case ETAG_bt2vector: EVAL1(bt2vector ) 3316 case ETAG_ceiling : EVAL2(ceilingx ) 3317 case ETAG_destruct : EVAL1(destruct ) 3318 case ETAG_evenp : EVAL1(evenp ) 3319 case ETAG_exception: EVAL0(exception ) 3320 case ETAG_false : EVAL0(false ) 3321 case ETAG_floor : EVAL2(floorx ) 3322 case ETAG_half : EVAL1(half ) 3323 case ETAG_if : 3324 R0=eval(HEAD(term),env); 3325 if(R0==T) return eval(HEAD(TAIL(term)),env); 3326 if(IS_EX(R0)) return R0; 3327 return eval(TAIL(TAIL(term)),env); 3328 case ETAG_intlength: EVAL1(integerLength) 3329 case ETAG_logand : EVAL2(logand ) 3330 case ETAG_logandc1 : EVAL2(logandc1 ) 3331 case ETAG_logandc2 : EVAL2(logandc2 ) 3332 case ETAG_logbitp : EVAL2(logbitp ) 3333 case ETAG_logcount : EVAL1(logcount ) 3334 case ETAG_logeqv : EVAL2(logeqv ) 3335 case ETAG_logior : EVAL2(logior ) 3336 case ETAG_lognand : EVAL2(lognand ) 3337 case ETAG_lognor : EVAL2(lognor ) 3338 case ETAG_lognot : EVAL1(lognot ) 3339 case ETAG_logorc1 : EVAL2(logorc1 ) 3340 case ETAG_logorc2 : EVAL2(logorc2 ) 3341 case ETAG_logtest : EVAL2(logtest ) 3342 case ETAG_logxor : EVAL2(logxor ) 3343 case ETAG_map : 3344 return mapcons(TAIL(term)); 3345 case ETAG_prenorm : EVAL1(norm ) 3346 case ETAG_notnot : EVAL1(notnot ) 3347 case ETAG_object : EVAL1(object ) 3348 case ETAG_print : EVAL1(print ) 3349 case ETAG_round : EVAL2(roundx ) 3350 case ETAG_spy : EVAL1(spy ) 3351 case ETAG_timer : EVAL1(timer ) 3352 case ETAG_trace : EVAL1(trace ) 3353 case ETAG_truncate : EVAL2(truncatex ) 3354 case ETAG_vector : EVAL1(vector ) 3355 case ETAG_vnorm : EVAL1(vectorNorm ) 3356 case ETAG_vempty : EVAL1(vectorEmpty ) 3357 case ETAG_vindex : EVAL2(vectorIndex ) 3358 case ETAG_vlength : EVAL1(vectorLength ) 3359 case ETAG_vprefix : EVAL2(vectorPrefix ) 3360 case ETAG_vsubseq : EVAL3(vectorSubseq ) 3361 case ETAG_vsuffix : EVAL2(vectorSuffix ) 3362 case ETAG_v2bytes : EVAL1(vector2bytes ) 3363 case ETAG_v2vects : EVAL1(vector2vects ) 3364 case ETAG_vt2bytes : EVAL1(vt2bytes ) 3365 case ETAG_vt2vects : EVAL1(vt2vects ) 3366 case ETAG_vt2v : EVAL1(vt2vector ) 3367 case ETAG_compile : EVAL1(compile ) 3368 case ETAG_ripemd : EVAL1(ripemd ) 3369 case ETAG_sl2rack : EVAL1(sl2rack ) 3370 case ETAG_rack2sl : EVAL1(rack2sl ) 3371 // GRD-2009-04-19: Ensure eager constants evaluated once only. 3372 case MTAG_INDIR : 3373 return TAIL(term); 3374 case MTAG_CLOSURE: 3375 push(term); 3376 return ret(1,overwrite(term,term2rnf(HEAD(term),TAIL(term)))); 3377 default: unexpected_tag("eval",term);}} 3378 */ 3379 3380 3381 3382 /******************* 3383 * Array functions * 3384 *******************/ 3385 3386 void printdom(pnt a){ 3387 pnt head; 3388 if(a==T) return; 3389 if(GD_PAIR(a)) die("Unexpected type in array"); 3390 head=HEAD(a); 3391 if(!NO_INT(head)){ 3392 spy0(head); 3393 return;} 3394 printdom(head); 3395 printdom(TAIL(a));} 3396 3397 pnt aget(pnt a,pnt i){ 3398 pnt head,i1,i2,bit; 3399 if(NO_INT(i)) return X; 3400 i2=i; 3401 i1=HEAD(i2); 3402 bit=0; 3403 for(;;){ 3404 if(a==T) return T; 3405 if(GD_PAIR(a)) return X; 3406 head=HEAD(a); 3407 if(IS_INT(head)){if(eq0(head,i)) return TAIL(a); else return T;} 3408 if((i1>>bit)&1) a=TAIL(a); else a=head; 3409 bit++; 3410 if(bit=pntsize) return getbit(x-pntsize,inttail(y)); 3455 return (HEAD(y)>>x)&1;} 3456 3457 pnt aput2(pnt i1,pnt a,pnt i2,pnt v2,pnt b){ 3458 if(getbit(b,i1)==0){ 3459 if(getbit(b,i2)==0) return pair(aput2(i1,a,i2,v2,b+1),T); 3460 return pair(a,pair(i2,v2));} 3461 else{ 3462 if(getbit(b,i2)==1) return pair(T,aput2(i1,a,i2,v2,b+1)); 3463 return pair(pair(i2,v2),a);}} 3464 3465 pnt aput1(pnt a,pnt i,pnt v,pnt b){ 3466 pnt head; 3467 pnt tail; 3468 if(a==T) return semipair2(i,v); 3469 if(GD_PAIR(a)) return a; 3470 head=HEAD(a); 3471 tail=TAIL(a); 3472 if(IS_INT(head)){ 3473 if(eq0(head,i)) return semipair2(i,v); 3474 if(v==T) return a; 3475 if(tail==T) return pair(i,v); 3476 return aput2(head,a,i,v,b);} 3477 if(getbit(b,i)==0) return semipair1(aput1(head,i,v,b+1),tail); 3478 return semipair1(head,aput1(tail,i,v,b+1));} 3479 3480 pnt aput0(pnt a,pnt i,pnt v){ 3481 if(NO_INT(i)) return a; 3482 push(a); 3483 push(i); 3484 push(v); 3485 return ret(3,aput1(a,i,v,0));} 3486 3487 pnt mput1(pnt array,pnt value,pnt index1){ 3488 return aput0(array,index1,value);} 3489 3490 pnt mput2(pnt array,pnt value,pnt index1,pnt index2){ 3491 pnt subarray=aget(array,index1); 3492 push(array); 3493 push(index1); 3494 subarray=ret(2,mput1(subarray,value,index2)); 3495 return mput1(array,subarray,index1);} 3496 3497 pnt mput3(pnt array,pnt value,pnt index1,pnt index2,pnt index3){ 3498 pnt subarray=aget(array,index1); 3499 push(array); 3500 push(index1); 3501 subarray=ret(2,mput2(subarray,value,index2,index3)); 3502 return mput1(array,subarray,index1);} 3503 3504 pnt mput4(pnt array,pnt value,pnt index1,pnt index2,pnt index3,pnt index4){ 3505 pnt subarray=aget(array,index1); 3506 push(array); 3507 push(index1); 3508 subarray=ret(2,mput3(subarray,value,index2,index3,index4)); 3509 return mput1(array,subarray,index1);} 3510 3511 3512 3513 /************* 3514 * Scripting * 3515 *************/ 3516 3517 /* 3518 In scripts, blank lines and lines starting with a hash mark 3519 are ignored. 3520 3521 LF (10) as well as CR (13) are considered as line terminators. 3522 A CRLF is considered as two linebreaks, but nobody will notice 3523 since blank lines are ignored. 3524 3525 Sample scripts: 3526 3527 #!/home/kgr/code/red/red/red.exe script 3528 codex 3529 017451CF6643931035C71796AC493D382EC8357EE9A390D5D6DBCDAA0806 3530 017451CF6643931035C71796AC493D382EC8357EE9A390D5D6DBCDAA0806 3531 0 3532 0 3533 execute 3534 /home/kgr/code/red/lisp/cache 3535 /home/kgr/code/red/lisp/cache1 3536 3537 #!/home/kgr/code/red/red/red.exe script 3538 assoc 3539 017451CF6643931035C71796AC493D382EC8357EE9A390D5D6DBCDAA0806 3540 017451CF6643931035C71796AC493D382EC8357EE9A390D5D6DBCDAA0806 3541 0 3542 0 3543 executables 3544 hello 3545 /home/kgr/code/red/lisp/cache 3546 /home/kgr/code/red/lisp/cache1 3547 3548 #!/home/kgr/code/red/red/red.exe script 3549 execute 3550 017451CF6643931035C71796AC493D382EC8357EE9A390D5D6DBCDAA0806 3551 /home/kgr/code/red/lisp/cache 3552 /home/kgr/code/red/lisp/cache1 3553 3554 #!/home/kgr/code/red/red/red.exe script 3555 executables 3556 017451CF6643931035C71796AC493D382EC8357EE9A390D5D6DBCDAA0806 3557 hello 3558 /home/kgr/code/red/lisp/cache 3559 /home/kgr/code/red/lisp/cache1 3560 3561 */ 3562 3563 unsigned char *mbufstart; 3564 unsigned char *mbufpnt; 3565 unsigned char *mbufend; 3566 off_t mbufsize; 3567 3568 void mmapdie(char *caller,char *filename,char *fct){ 3569 printf("%s trying to mmap %s:\n",caller,filename); 3570 pdie(fct);} 3571 3572 int mmap1(char *caller,char *filename){ 3573 int fd; 3574 struct stat stats; 3575 fd=open(filename,O_RDONLY); 3576 if(fd<0){if(errno==ENOENT) return -1; else mmapdie(caller,filename,"open");} 3577 if(fstat(fd,&stats)) mmapdie(caller,filename,"fstat"); 3578 if(!S_ISREG(stats.st_mode)) return -1; 3579 mbufstart=mmap(0,stats.st_size,PROT_READ,MAP_SHARED,fd,0); 3580 if(mbufstart==MAP_FAILED) mmapdie(caller,filename,"mmap"); 3581 if(close(fd)) mmapdie(caller,filename,"close"); 3582 mbufsize=stats.st_size; 3583 mbufpnt=mbufstart; 3584 mbufend=mbufstart+mbufsize; 3585 return 0;} 3586 3587 void munmap1(){ 3588 if (munmap(mbufstart,mbufsize)) pdie("munmap");} 3589 3590 /* Return next input byte or ENDFILE (256) */ 3591 pnt getch(){ 3592 if(mbufpnt==mbufend) return ENDFILE; 3593 return *(mbufpnt++);} 3594 3595 /* Return TRUE if line read or FALSE at ENDFILE 3596 Skip comment lines (lines starting with hash mark) */ 3597 pnt readln(unsigned char line[PATHSIZE]){ 3598 pnt i; 3599 pnt c; 3600 i=0; 3601 for(;;){ 3602 if(i>=PATHSIZE) die("Line too long"); 3603 c=getch(); 3604 line[i]=0; 3605 if(c==ENDFILE) return i!=0; 3606 if((c!=CR)&&(c!=LF)) line[i++]=c; 3607 else if((i>0)&&(line[0]!='#')) return TRUE; 3608 else i=0;}} 3609 3610 /* Read one pnt, die on ENDFILE, die on overflow */ 3611 pnt readpnt(){ 3612 pnt result; 3613 pnt byte=getch(); 3614 if(byte==ENDFILE) die("Unexpected end of file"); 3615 if(byte<128) return byte; 3616 result=readpnt(); 3617 if(result&septetmask) die("Pnt overflow"); 3618 return result*128+byte-128;} 3619 3620 /************* 3621 * Read rack * 3622 *************/ 3623 3624 /* 3625 Read one rack file and convert it into a structure with sharing. 3626 The reference is given as a file descriptor. 3627 3628 The input file is treated as a sequence of bytes. 3629 3630 The output structure is composed of the constant NIL, cardinals, 3631 and conses. 3632 3633 In the input file, most cardinals are expressed base 128. Each such 3634 cardinal is represented as a sequence of 'middle septets' followed 3635 by an 'end septet'. Middle septets are represented by bytes in 3636 the range 128..255. End septets are represented by bytes in the 3637 range 0..127. Cardinals are expressed in little endian. As an example, 3638 "129 130 003" represents 1+128*2+16384*3. 3639 3640 An input file represents a sequence of values, the last of which is 3641 the rack to be constructed. 3642 3643 Each value in the sequence has an "index". The index of the first 3644 value is RACK_START, the index of the next is RACK_START+1, and 3645 so on. 3646 3647 The constant NIL is represented by the cardinal RACK_NIL in base 128. 3648 3649 A cardinal x is represented by the cardinal RACK_INT in base 128 3650 followed by the cardinal x in base 128. 3651 3652 A cons of two values y and z is represented by the index of y followed 3653 by the index of z. The indices of y and z are smaller than the index 3654 of the cons, so when scanning a rack file from start to end, the 3655 arguments of a cons will be constructed before the cons is constructed. 3656 3657 A vector x is represented by the cardinal RACK_ARRAY in base 128 3658 followed by the number of bytes in x expressed in base 128 followed 3659 by the bytes of x. Since a vector ultimately represents a cardinal, 3660 this is just a slightly more compact and less CPU consuming way of 3661 representing cardinals. 3662 */ 3663 pnt readrack1(){ 3664 pnt sp1=sp; 3665 pnt sp2=sp+1; 3666 pnt card0; 3667 pnt card1; 3668 pnt index; 3669 pnt vector; 3670 pnt position; 3671 pnt *location; 3672 pnt result; 3673 push(T); /* stack[sp1-RACK_NIL] represents T */ 3674 push(T); /* stack[sp1-RACK_ARRAY] is unused */ 3675 for(;;){ 3676 index=sp2-sp; 3677 card0=readpnt(); 3678 if(card0==RACK_INT){ 3679 vector=icons(0,0); 3680 push(vector); 3681 location=stack+sp; 3682 position=0; 3683 do{ 3684 card1=getch(); 3685 HEAD(vector)|=((card1&127)<=pntsize){ 3688 position-=pntsize; 3689 TAIL(vector)=icons((card1&127)>>(7-position),0); 3690 location=&TAIL(vector); 3691 vector=TAIL(vector);}} 3692 while(card1>127); 3693 if(HEAD(vector)<256) *location=I[HEAD(vector)];} 3694 else if(card0==RACK_ARRAY){ 3695 vector=consvec(0,0); 3696 push(vector); 3697 for(card1=readpnt();card1>=bytesize;card1-=bytesize){ 3698 for(position=0;position=index) die("Malformed rack (Pointer too large)"); 3708 if(card1==RACK_INT) die("Malformed rack (Invalid tail)"); 3709 if(card1==RACK_ARRAY) die("Malformed rack (Invalid tail)"); 3710 push(pair(stack[sp1-card0],stack[sp1-card1]));} 3711 else if(card0==index) break; 3712 else die("Malformed rack (Pointer too large)");} 3713 result=stack[sp]; 3714 sp=sp1; 3715 return result;} 3716 3717 /* 3718 Read one rack file and convert it into a structure with sharing. 3719 The reference is given as a mixed endian hexadecimal string. 3720 The readrack() function scans the path for a rack file with the 3721 given name and then invokes readrack1 on the file found. 3722 */ 3723 3724 char *memcpy1(char *dest,char *src,size_t n){ 3725 memcpy(dest,src,n); 3726 return dest+n;} 3727 3728 /* 3729 If p1="aa:bb", p2="cc", p3="dd", and p4="ee" construct aaccddee 3730 If p1="aa:bb", p2="cc", p3="dd", and p4="" construct aaccddbb 3731 */ 3732 pnt make_path(char *result,pnt size,char *p1,char *p2,char *p3,char *p4){ 3733 char *result1=result; 3734 char *match0=strchr(p1,';'); 3735 pnt l0=match0?(pnt)(match0-p1):(pnt)strlen(p1); 3736 char *match1=memchr(p1,':',l0); 3737 pnt l1=match1?(pnt)(match1-p1):(pnt)strlen(p1); 3738 pnt l2=strlen(p2); 3739 pnt l3=strlen(p3); 3740 pnt l4=strlen(p4); 3741 if(match1==NULL) die("Missing colon in LGW_PATH element"); 3742 if(l4==0){l4=l0-l1-1;p4=p1+l1+1;} 3743 if(l1+l2+l3+l4>=size) die("Path too long"); 3744 result1=memcpy1(result1,p1,l1); 3745 result1=memcpy1(result1,p2,l2); 3746 result1=memcpy1(result1,p3,l3); 3747 result1=memcpy1(result1,p4,l4); 3748 result1=memcpy1(result1,"",1); 3749 return l0;} 3750 3751 #define DEFAULT_LGW_PATH "/.logiweb/logiweb/:/rack.lgr" 3752 char *get_lgw_path(){ 3753 char *path; 3754 if(lgw_path) return lgw_path; 3755 path=getenv("LGW_PATH"); 3756 if(path&&path[0]){ 3757 make_path(lgw_path1,sizeof(lgw_path1),":","","",path); 3758 lgw_path=lgw_path1; 3759 return lgw_path;} 3760 path=getenv("HOME"); 3761 if(path&&path[0]){ 3762 make_path(lgw_path1,sizeof(lgw_path1),":","",path,DEFAULT_LGW_PATH); 3763 lgw_path=lgw_path1; 3764 return lgw_path;} 3765 die("Neither LGW_PATH nor HOME set"); 3766 return T; /* This never happens */} 3767 3768 pnt readrack(char *hexref){ 3769 pnt result; 3770 char *path=get_lgw_path(); 3771 pnt length; 3772 char filename[PATHSIZE]; 3773 if(path==0) die("LGW_PATH not set"); 3774 for(;;){ 3775 length=make_path(filename,sizeof(filename),path,"",hexref,""); 3776 path+=(length+1); 3777 if(length==0) continue; 3778 if(mmap1("readrack",filename)==0){ 3779 TRUSTGC; 3780 result=readrack1(); 3781 UNTRUSTGC; 3782 if(getch()!=ENDFILE) die("Malformed rack (ENDFILE expected)"); 3783 munmap1(); 3784 return result;} 3785 if(errno!=ENOENT) pdie("lgwam: readrack: open()"); 3786 if(*(path-1)==';') continue; 3787 printf("%s not found\n",hexref); 3788 printf("LGW_PATH=%s\n",get_lgw_path()); 3789 die("Goodbye");}} 3790 3791 3792 3793 /********************************************* 3794 * Optimized function sl2rack for rack input * 3795 *********************************************/ 3796 3797 pnt sl2rack_sl; 3798 pnt sl2rack_X=(pnt)(-1); 3799 3800 /* Essentially the same as getch() */ 3801 pnt sl2rack_getch(){ 3802 pnt result; 3803 if(NO_PAIR(sl2rack_sl)) return sl2rack_X; 3804 result=HEAD(sl2rack_sl); 3805 sl2rack_sl=TAIL(sl2rack_sl); 3806 if(NO_INT(result)) return sl2rack_X; 3807 if(TAIL(result)!=NIL) return sl2rack_X; 3808 result=HEAD(result); 3809 if((result>>8)!=1) return sl2rack_X; 3810 return result&0xFF;} 3811 3812 /* Essentially the same as readpnt() */ 3813 pnt sl2rack_readpnt(){ 3814 pnt result; 3815 pnt byte=sl2rack_getch(); 3816 if(byte==sl2rack_X) return sl2rack_X; 3817 if(byte<128) return byte; 3818 result=sl2rack_readpnt(); 3819 if(result==sl2rack_X) return sl2rack_X; 3820 if(result&septetmask) die("sl2rack: Pnt overflow"); 3821 result=result*128+byte-128; 3822 if(result==sl2rack_X) die("sl2rack: Pnt overflow"); 3823 return result;} 3824 3825 /* Essentially the same as readrack1() */ 3826 pnt sl2rack_readrack1(){ 3827 pnt sp1=sp-1; 3828 pnt sp2=sp; 3829 pnt card0; 3830 pnt card1; 3831 pnt byte; 3832 pnt index; 3833 pnt vector; 3834 pnt position; 3835 pnt *location; 3836 push(T); /* stack[sp1-RACK_INT] is unused */ 3837 push(T); /* stack[sp1-RACK_NIL] represents T */ 3838 push(T); /* stack[sp1-RACK_ARRAY] is unused */ 3839 for(;;){ 3840 index=sp2-sp; 3841 card0=sl2rack_readpnt(); 3842 if(card0==sl2rack_X) return X; 3843 if(card0==RACK_INT){ 3844 vector=icons(0,0); 3845 push(vector); 3846 location=stack+sp; 3847 position=0; 3848 do{ 3849 card1=sl2rack_getch(); 3850 if(card1==sl2rack_X) return X; 3851 HEAD(vector)|=((card1&127)<=pntsize){ 3854 position-=pntsize; 3855 TAIL(vector)=icons((card1&127)>>(7-position),0); 3856 location=&TAIL(vector); 3857 vector=TAIL(vector);}} 3858 while(card1>127); 3859 if(HEAD(vector)<256) *location=I[HEAD(vector)];} 3860 else if(card0==RACK_ARRAY){ 3861 vector=consvec(0,0); 3862 push(vector); 3863 card1=sl2rack_readpnt(); 3864 if(card1==sl2rack_X) return X; 3865 for(;card1>=bytesize;card1-=bytesize){ 3866 for(position=0;position=index) die("sl2rack: Malformed rack (Pointer too large)"); 3881 if(card1==RACK_INT) die("sl2rack: Malformed rack (Invalid tail)"); 3882 if(card1==RACK_ARRAY) die("sl2rack: Malformed rack (Invalid tail)"); 3883 push(pair(stack[sp1-card0],stack[sp1-card1]));} 3884 else if(card0==index) break; 3885 else die("sl2rack: Malformed rack (Pointer too large)");} 3886 return stack[sp];} 3887 3888 pnt sl2rack(pnt sl){/* sl2rack ( " ) */ 3889 pnt result; 3890 pnt sp0=sp; 3891 push(sl); 3892 sl2rack_sl=sl; 3893 result=sl2rack_readrack1(); 3894 sp=sp0; 3895 return result;} 3896 3897 3898 3899 /********************************************** 3900 * Optimized function rack2sl for rack output * 3901 **********************************************/ 3902 3903 #define RACK2SL_KEY 19 3904 pnt rack2sl_sp; 3905 pnt rack2sl_size; 3906 pnt rack2sl_pnt; 3907 pnt rack2sl_index; 3908 3909 /* 3910 Compare the integers x and y for equality 3911 This function also occurs inside eq0 3912 */ 3913 pnt rack_eq_int(pnt x,pnt y){ 3914 for(;;){ 3915 if(HEAD(x)!=HEAD(y)) return FALSE; 3916 x=TAIL(x); 3917 y=TAIL(y); 3918 if(x==0||y==0) return x==y;}} 3919 3920 /* 3921 During rack conversion, we use a hash table 3922 The hash table is stored on the stack below stack[sp] 3923 The garbarge collector does not see the hash table because it is below stack[sp] 3924 rack_pnt2index(r) converts the pointer r to its index using the hash table 3925 */ 3926 pnt rack_pnt2index(pnt r){ 3927 pnt root; 3928 pnt head; 3929 pnt tail; 3930 pnt hash; 3931 pnt s; 3932 if(r==T) return 1; 3933 root=ROOT(r); 3934 root=root&~markmask; 3935 if(root==TAG_INT||root==TAG_VECT){ 3936 hash=HEAD(r); 3937 hash=hash%rack2sl_size; 3938 hash=hash*RACK2SL_KEY; 3939 hash=hash%rack2sl_size; 3940 for(;(s=stack[rack2sl_sp+hash*2])!=T;hash=(hash+1)%rack2sl_size){ 3941 if((ROOT(s)&~markmask)==TAG_PAIR) continue; 3942 if(!rack_eq_int(r,s)) continue; 3943 return stack[rack2sl_sp+hash*2+1];} 3944 die("rack2sl: Internal error 1, cannot find cardinal");} 3945 if(root==TAG_PAIR){ 3946 head=HEAD(r); 3947 tail=TAIL(r); 3948 hash=(head%rack2sl_size+tail%rack2sl_size)*RACK2SL_KEY; 3949 hash=hash%rack2sl_size; 3950 for(;(s=stack[rack2sl_sp+hash*2])!=T;hash=(hash+1)%rack2sl_size){ 3951 if((ROOT(s)&~markmask)!=TAG_PAIR) continue; 3952 if(HEAD(s)!=head) continue; 3953 if(TAIL(s)!=tail) continue; 3954 return stack[rack2sl_sp+hash*2+1];} 3955 die("rack2sl: Internal error 2, cannot find pair");} 3956 unexpected_tag("Internal error 3 in rack2sl",r); 3957 return T; /* This never happens */} 3958 3959 /* 3960 Return size of rack measured in entities (pairs and integers) 3961 T counts as zero entities, entities for one each. 3962 Only count shared entities once. 3963 Put a mark on each entity when counted. 3964 Return sl2rack_X, i.e. (pnt)(-1) in case of unexpected data 3965 */ 3966 pnt rack_size(pnt r){ 3967 pnt root; 3968 pnt head; 3969 pnt tail; 3970 if(r==T) return 0; 3971 root=ROOT(r); 3972 if(root&markmask) return 0; 3973 if(root==TAG_INT){ 3974 if(lt(r,Z)==T){ROOT(r)=root|markmask;return sl2rack_X;} 3975 ROOT(r)=root|markmask;return 1;} 3976 ROOT(r)=root|markmask; 3977 if(root==TAG_VECT) return 1; 3978 if(root!=TAG_PAIR) return sl2rack_X; 3979 head=rack_size(HEAD(r)); 3980 if(head==sl2rack_X) return sl2rack_X; 3981 tail=rack_size(TAIL(r)); 3982 if(tail==sl2rack_X) return sl2rack_X; 3983 return 1+head+tail;} 3984 3985 /* 3986 Search rack for sharing. 3987 Build a hash table which maps entities (pairs and integers) to indexes 3988 Remove mark after processing an entity. 3989 Turn duplicates into garbage and let the garbage point to its twin. 3990 Link all duplicates into a list pointed at by rack2sl_pnt 3991 */ 3992 pnt rack_merge(pnt r){ 3993 pnt root; 3994 pnt head; 3995 pnt tail; 3996 pnt hash; 3997 pnt s; 3998 if(r==T) return r; 3999 root=ROOT(r); 4000 if(!(root&markmask)) return (root==TAG_GARB)?HEAD(r):r; 4001 root=root&~markmask; 4002 ROOT(r)=root; 4003 if(root==TAG_GARB) return HEAD(r); 4004 if(root==TAG_INT||root==TAG_VECT){ 4005 hash=HEAD(r); 4006 hash=hash%rack2sl_size; 4007 hash=hash*RACK2SL_KEY; 4008 hash=hash%rack2sl_size; 4009 for(;(s=stack[rack2sl_sp+hash*2])!=T;hash=(hash+1)%rack2sl_size){ 4010 if(ROOT(s)==TAG_PAIR) continue; 4011 if(!rack_eq_int(r,s)) continue; 4012 ROOT(r)=TAG_GARB; 4013 HEAD(r)=s; 4014 TAIL(r)=rack2sl_pnt; 4015 rack2sl_pnt=r; 4016 return s;} 4017 stack[rack2sl_sp+hash*2]=r; 4018 stack[rack2sl_sp+hash*2+1]=rack2sl_index++; 4019 return r;} 4020 if(root==TAG_PAIR){ 4021 head=rack_merge(HEAD(r)); 4022 tail=rack_merge(TAIL(r)); 4023 HEAD(r)=head; 4024 TAIL(r)=tail; 4025 hash=(head%rack2sl_size+tail%rack2sl_size)*RACK2SL_KEY; 4026 hash=hash%rack2sl_size; 4027 for(;(s=stack[rack2sl_sp+hash*2])!=T;hash=(hash+1)%rack2sl_size){ 4028 if(ROOT(s)!=TAG_PAIR) continue; 4029 if(HEAD(s)!=head) continue; 4030 if(TAIL(s)!=tail) continue; 4031 ROOT(r)=TAG_GARB; 4032 HEAD(r)=s; 4033 TAIL(r)=rack2sl_pnt; 4034 rack2sl_pnt=r; 4035 return s;} 4036 stack[rack2sl_sp+hash*2]=r; 4037 stack[rack2sl_sp+hash*2+1]=rack2sl_index++; 4038 return r;} 4039 unexpected_tag("Internal error 4 in rack2sl",r); 4040 return T; /* This never happens */} 4041 4042 /* 4043 Turn duplicates back from garbage to duplicates 4044 */ 4045 void rack2sl_restore(){ 4046 pnt r,s; 4047 while(rack2sl_pnt!=T){ 4048 r=rack2sl_pnt; 4049 rack2sl_pnt=TAIL(rack2sl_pnt); 4050 s=HEAD(r); 4051 ROOT(r)=ROOT(s); 4052 HEAD(r)=HEAD(s); 4053 TAIL(r)=TAIL(s);}} 4054 4055 /* 4056 Push one byte onto the result 4057 The result is pointed at by TAIL(stack[sp]) 4058 rack2sl_pnt points to the last cell of the result 4059 */ 4060 void rack_byte_dump(pnt r){ 4061 pnt x=pair(bytevect[r],T); 4062 TAIL(rack2sl_pnt)=x; 4063 rack2sl_pnt=x;} 4064 4065 /* 4066 Push one small cardinal onto the result 4067 */ 4068 void rack_int_dump(pnt r){ 4069 for(;r>=128;r=r/128) rack_byte_dump(r%128+128); 4070 rack_byte_dump(r);} 4071 4072 /* 4073 Find the integer-length of the cardinal x 4074 Resembles integerLength(x) 4075 */ 4076 pnt rack_int_length(pnt x){ 4077 pnt result=0; 4078 for(;TAIL(x);x=TAIL(x)) result+=pntsize; 4079 x=HEAD(x); 4080 if(x&signmask) return 0; 4081 for(;x;x=x>>1) result+=1; 4082 return result;} 4083 4084 /* 4085 Push the rack (excluding the end mark) onto the result 4086 */ 4087 void rack_dump(pnt r){ 4088 pnt root; 4089 pnt head; 4090 pnt tail; 4091 pnt len; 4092 pnt i; 4093 if(r==T) return; 4094 root=ROOT(r); 4095 if(root&markmask) return; 4096 ROOT(r)=root|markmask; 4097 if(root==TAG_INT||root==TAG_VECT){ 4098 len=rack_int_length(r); 4099 if(len%8==1){ 4100 rack_int_dump(2); 4101 len=len/8; 4102 rack_int_dump(len); 4103 for(;TAIL(r);r=TAIL(r)) 4104 for(i=0;i>(8*i))&0xFF); 4106 r=HEAD(r); 4107 for(;r>1;r=r>>8) rack_byte_dump(r&0xFF); 4108 return;} 4109 if(TAIL(r)) die("rack2sl conversion of non-vector bigints not implemented"); 4110 rack_int_dump(0); 4111 rack_int_dump(HEAD(r)); 4112 return;} 4113 if(root==TAG_PAIR){ 4114 head=HEAD(r); 4115 tail=TAIL(r); 4116 rack_dump(head); 4117 rack_dump(tail); 4118 rack_int_dump(rack_pnt2index(head)); 4119 rack_int_dump(rack_pnt2index(tail)); 4120 return;} 4121 unexpected_tag("Internal error 5 in rack2sl",r);} 4122 4123 4124 4125 /* 4126 Scan the heap and remove marks on all entities 4127 */ 4128 void rack_unmark(pnt r){ 4129 pnt root; 4130 if(r==T) return; 4131 root=ROOT(r); 4132 if(!(root&markmask)) return; 4133 root=root&~markmask; 4134 ROOT(r)=root; 4135 if(root!=TAG_PAIR) return; 4136 rack_unmark(HEAD(r)); 4137 rack_unmark(TAIL(r));} 4138 4139 /* 4140 Clear the part of the stack used for the hash table 4141 The hash table is stored below stack[sp] so that gc() does not note it 4142 */ 4143 void clear_hash(){ 4144 pnt sp1; 4145 for(sp1=0;sp1=PATHSIZE) die("ref2string overflow"); 4236 if((head<256)&&(tail==NIL)){bufrefname[index]=0;return;} 4237 bufrefname[index++]=pnt2hex(head>>4); 4238 bufrefname[index++]=pnt2hex(head); 4239 head>>=8;} 4240 ref=tail;}} 4241 4242 /* Convert a mixed endian hexadecimal string to a vector */ 4243 pnt string2ref2(unsigned char *str,pnt len){ 4244 if(len==0) return 1; 4245 return (hex2pnt(*str)<<4)|hex2pnt(*(str+1))|(string2ref2(str+2,len-1)<<8);} 4246 4247 pnt string2ref1(unsigned char *str,pnt len){ 4248 if(len \""); 4333 init_name(ETAG_ge ,T,"\" >= \""); 4334 init_name(ETAG_apply ,T,"\" apply \""); 4335 init_name(ETAG_boolp ,T,"\" boolp"); 4336 init_name(ETAG_catch ,F,"\" catch"); 4337 init_name(ETAG_maptag1 ,F,"\" catching maptag"); 4338 init_name(ETAG_div ,T,"\" div \""); 4339 init_name(ETAG_head ,T,"\" head"); 4340 init_name(ETAG_intp ,T,"\" intp"); 4341 init_name(ETAG_boolg ,T,"\" is bool : \""); 4342 init_name(ETAG_intg ,T,"\" is int : \""); 4343 init_name(ETAG_mapg ,T,"\" is map : \""); 4344 init_name(ETAG_objg ,T,"\" is object : \""); 4345 init_name(ETAG_pairg ,T,"\" is pair : \""); 4346 init_name(ETAG_mapp ,T,"\" mapp"); 4347 init_name(ETAG_maptag ,F,"\" maptag"); 4348 init_name(ETAG_mod ,T,"\" mod \""); 4349 init_name(ETAG_norm ,T,"\" norm"); 4350 init_name(ETAG_objp ,T,"\" objectp"); 4351 init_name(ETAG_pairp ,T,"\" pairp"); 4352 init_name(ETAG_raise ,T,"\" raise"); 4353 init_name(ETAG_root ,T,"\" root"); 4354 init_name(ETAG_tail ,T,"\" tail"); 4355 init_name(ETAG_untag ,T,"\" untag"); 4356 init_name(ETAG_digitend ,T,"%%"); 4357 init_name(ETAG_par ,F,"( \" )"); 4358 init_name(ETAG_uplus ,T,"+ \""); 4359 init_name(ETAG_dplus ,T,"+\""); 4360 init_name(ETAG_uminus ,T,"- \""); 4361 init_name(ETAG_dminus ,T,"-\""); 4362 init_name(ETAG_not ,T,".not. \""); 4363 init_name(ETAG_Base ,T,"Base"); 4364 init_name(ETAG_LET ,F,"LET \" BE \""); 4365 init_name(ETAG_ash ,T,"ash ( \" , \" )"); 4366 init_name(ETAG_bottom ,T,"bottom"); 4367 init_name(ETAG_bt2bytes ,T,"bt2byte* ( \" )"); 4368 init_name(ETAG_bt2vects ,T,"bt2vector* ( \" )"); 4369 init_name(ETAG_bt2vector,T,"bt2vector ( \" )"); 4370 init_name(ETAG_ceiling ,T,"ceiling ( \" , \" )"); 4371 init_name(ETAG_destruct ,T,"destruct ( \" )"); 4372 init_name(ETAG_evenp ,T,"evenp ( \" )"); 4373 init_name(ETAG_exception,T,"exception"); 4374 init_name(ETAG_false ,T,"false"); 4375 init_name(ETAG_floor ,T,"floor ( \" , \" )"); 4376 init_name(ETAG_half ,T,"half ( \" )"); 4377 init_name(ETAG_if ,F,"if \" then \" else \""); 4378 init_name(ETAG_intlength,T,"integer-length ( \" )"); 4379 init_name(ETAG_logand ,T,"logand ( \" , \" )"); 4380 init_name(ETAG_logandc1 ,T,"logandc1 ( \" , \" )"); 4381 init_name(ETAG_logandc2 ,T,"logandc2 ( \" , \" )"); 4382 init_name(ETAG_logbitp ,T,"logbitp ( \" , \" )"); 4383 init_name(ETAG_logcount ,T,"logcount ( \" )"); 4384 init_name(ETAG_logeqv ,T,"logeqv ( \" , \" )"); 4385 init_name(ETAG_logior ,T,"logior ( \" , \" )"); 4386 init_name(ETAG_lognand ,T,"lognand ( \" , \" )"); 4387 init_name(ETAG_lognor ,T,"lognor ( \" , \" )"); 4388 init_name(ETAG_lognot ,T,"lognot ( \" )"); 4389 init_name(ETAG_logorc1 ,T,"logorc1 ( \" , \" )"); 4390 init_name(ETAG_logorc2 ,T,"logorc2 ( \" , \" )"); 4391 init_name(ETAG_logtest ,T,"logtest ( \" , \" )"); 4392 init_name(ETAG_logxor ,T,"logxor ( \" , \" )"); 4393 init_name(ETAG_map ,F,"map ( \" )"); 4394 init_name(ETAG_prenorm ,T,"norm \""); 4395 init_name(ETAG_notnot ,T,"notnot \""); 4396 init_name(ETAG_object ,T,"object ( \" )"); 4397 init_name(ETAG_print ,T,"print ( \" )"); 4398 init_name(ETAG_round ,T,"round ( \" , \" )"); 4399 init_name(ETAG_spy ,T,"spy ( \" )"); 4400 init_name(ETAG_timer ,T,"timer ( \" )"); 4401 init_name(ETAG_trace ,T,"trace ( \" )"); 4402 init_name(ETAG_truncate ,T,"truncate ( \" , \" )"); 4403 init_name(ETAG_vector ,T,"vector ( \" )"); 4404 init_name(ETAG_vnorm ,T,"vector-norm ( \" )"); 4405 init_name(ETAG_vempty ,T,"vector-empty ( \" )"); 4406 init_name(ETAG_vindex ,T,"vector-index ( \" , \" )"); 4407 init_name(ETAG_vlength ,T,"vector-length ( \" )"); 4408 init_name(ETAG_vprefix ,T,"vector-prefix ( \" , \" )"); 4409 init_name(ETAG_vsubseq ,T,"vector-subseq ( \" , \" , \" )"); 4410 init_name(ETAG_vsuffix ,T,"vector-suffix ( \" , \" )"); 4411 init_name(ETAG_v2bytes ,T,"vector2byte* ( \" )"); 4412 init_name(ETAG_v2vects ,T,"vector2vector* ( \" )"); 4413 init_name(ETAG_vt2bytes ,T,"vt2byte* ( \" )"); 4414 init_name(ETAG_vt2vects ,T,"vt2vector* ( \" )"); 4415 init_name(ETAG_vt2v ,T,"vt2vector ( \" )"); 4416 init_name(ETAG_yy ,F,"YY"); 4417 init_name(ETAG_compile ,T,"compile ( \" )"); 4418 init_name(ETAG_ripemd ,T,"ripemd ( \" )"); 4419 init_name(ETAG_sl2rack ,T,"sl2rack ( \" )"); 4420 init_name(ETAG_rack2sl ,T,"rack2sl ( \" )"); 4421 } 4422 4423 4424 4425 /****************** 4426 * Term accessors * 4427 ******************/ 4428 4429 pnt term2ref(pnt term){ 4430 return head(head(term));} 4431 pnt term2idx(pnt term){ 4432 return head(tail(head(term)));} 4433 pnt term2arg1(pnt term){ 4434 return head(tail(term));} 4435 pnt term2arg2(pnt term){ 4436 return head(tail(tail(term)));} 4437 pnt term2arg3(pnt term){ 4438 return head(tail(tail(tail(term))));} 4439 pnt def2lhs(pnt def){ 4440 return term2arg2(def);} 4441 pnt def2arg(pnt def){ 4442 return tail(def2lhs(def));} 4443 pnt def2rhs(pnt def){ 4444 return term2arg3(def);} 4445 4446 4447 4448 /******************* 4449 * Translate names * 4450 *******************/ 4451 4452 pnt name2sym4(pnt cache,pnt idx,pnt ref,pnt name){ 4453 pnt cache1; 4454 cache1=mget2(cache,Z,const_name); 4455 if(cache1==T) return T; 4456 cache1=head(tail(tail(tail(cache1)))); 4457 cache1=head(tail(head(cache1))); 4458 if(eq0(cache1,name)) return pair(ref,idx); 4459 return T;} 4460 4461 pnt name2sym3(pnt cache,pnt ref,pnt name){ 4462 pnt result; 4463 if(cache==T) return T; 4464 if(IS_INT(head(cache))) 4465 return name2sym4(TAIL(cache),HEAD(cache),ref,name); 4466 result=name2sym3(HEAD(cache),ref,name); 4467 if(result!=T) return result; 4468 return name2sym3(TAIL(cache),ref,name);} 4469 4470 pnt name2sym2(pnt cache,pnt ref,pnt name){ 4471 return name2sym3(mget3(cache,ref,const_codex,ref),ref,name);} 4472 4473 pnt name2sym1(pnt cache,pnt name){ 4474 pnt result; 4475 if(cache==T) return T; 4476 if(IS_INT(head(cache))) return name2sym2(TAIL(cache),HEAD(cache),name); 4477 result=name2sym1(HEAD(cache),name); 4478 if(result!=T) return result; 4479 return name2sym1(tail(cache),name);} 4480 4481 pnt name2sym(char name1[]){ 4482 pnt name; 4483 name=str2vec1((unsigned char *)name1,strlen(name1)); 4484 return name2sym1(state,name);} 4485 4486 pnt name2ref(char name1[]){ 4487 pnt sym=name2sym(name1); 4488 if(sym==T) {printf("%s\n",name1);die("No code found");} 4489 return head(sym);} 4490 4491 pnt name2idx(char name1[]){ 4492 pnt sym=name2sym(name1); 4493 if(sym==T) {printf("%s\n",name1);die("No code found");} 4494 return tail(sym);} 4495 4496 pnt name2code(char name1[]){ 4497 pnt sym; 4498 pnt ref; 4499 pnt idx; 4500 sym=name2sym(name1); 4501 if(sym==T) {printf("%s\n",name1);die("No code found");} 4502 ref=HEAD(sym); 4503 idx=TAIL(sym); 4504 return mget4(state,ref,ref,const_code,idx);} 4505 4506 pnt name2code1(pnt code,char name1[]){ 4507 return mget1(code,name2idx(name1));} 4508 4509 4510 4511 /************************ 4512 * Compilation, stage 1 * 4513 ************************/ 4514 4515 /* 4516 During stage 1, an initial value for the code array is constructed. 4517 4518 The code array is constructed in the top element of the stack. 4519 4520 The code array has one entry per construct with a non-empty value aspect. 4521 4522 The code array is indexed by the index of each construct. 4523 4524 For proclaimed constructs (lambda, quote, true, apply, and if), 4525 code[idx] is set to the value code[idx] is eventually going to have. 4526 (0 for lambda, 1 for quote, and various tagged maps for the other three). 4527 4528 For defined and introduced constructs, code[idx] is set to a tagged map 4529 whose 'hidden tag' is set to CTAG_EMAP because any definition is deemed 4530 eager until the converse has been proved. During later stages, this hidden 4531 tag is updated to reflect the outcome of various static analysis. The 4532 hidden tag has no influence on the semantics of the entries. 4533 4534 For defined and introduced constructs, the map part of code[idx] is set 4535 to as many lambdas as the arity of the construct indicates followed by 4536 a pair construct followed by the definition of the construct. During 4537 stage 5 and 6, the pair is overwritten with the compiled version of the 4538 definition. This allows to implement mutual recursion with circular 4539 call structures. 4540 */ 4541 4542 pnt term2fct(pnt arity,pnt term){ 4543 if(arity==0) return closure(term,NIL); 4544 return map_lambda(term_lambdas(arity-1,term),NIL);} 4545 4546 void initcode(pnt codex){ 4547 pnt hd; 4548 pnt tl; 4549 pnt def; 4550 pnt arg; 4551 pnt arity; 4552 if(codex==T) return; 4553 if(GD_PAIR(codex)) die("Unexpected type in codex"); 4554 hd=HEAD(codex); 4555 tl=TAIL(codex); 4556 if(NO_INT(hd)){initcode(hd);initcode(tl);return;} 4557 def=mget2(tl,Z,const_value); 4558 if(def==T) return; 4559 if(!eq0(head(head(def)),Z)){ 4560 arity=0; 4561 for(arg=tail(head(tail(tail(def))));arg!=T;arg=TAIL(arg)) arity++; 4562 TOP=aput0(TOP,hd,mapcons2(CTAG_EMAP,term2fct(arity,pair(def,T)))); 4563 return;} 4564 def=head(tail(head(def))); 4565 if(eq0(def,const_lambda)){TOP=aput0(TOP,hd,fct_lambda); return;} 4566 if(eq0(def,const_apply)){TOP=aput0(TOP,hd,fct_apply); return;} 4567 if(eq0(def,const_if)){TOP=aput0(TOP,hd,fct_if); return;} 4568 if(eq0(def,const_true)){TOP=aput0(TOP,hd,fct_true); return;} 4569 if(eq0(def,const_quote)){TOP=aput0(TOP,hd,fct_quote); return;} 4570 spy0(int2vec(def)); 4571 die("Unknown value proclamations");} 4572 4573 4574 4575 /***************************************** 4576 * Compilation, stage 2, record patterns * 4577 *****************************************/ 4578 4579 /* 4580 During the stage 2, the official definitions of optimized functions 4581 are collected. 4582 4583 This is done on basis of the cache of a reference page. The constructs 4584 on the reference page are recognized using their Logiweb names. 4585 4586 Optimized function i is supposed to have Logiweb name tag2name[i]. 4587 Once a construct with name tag2name[i] is located in the cache of 4588 the reference page, the value definition of that construct is taken 4589 to be the official definition of optimized function i. 4590 4591 Stage 2 of the compilation is only performed when translating the 4592 reference page. A complete compilation consists of compilation of the 4593 reference page, including stage 2, followed by compilation of the 4594 source page, excluding stage 2. 4595 4596 Note that the source page can be identical to the reference page in 4597 which case translation of the source page will be trivial since it 4598 is already compiled. 4599 4600 Also note that the source page may transitively reference to reference 4601 page in which case the reference page is only compiled once. 4602 4603 One could stop compilation of the reference page after stage 2 if it 4604 is not transitively referenced by the source page, but the reference 4605 page is translated to completion in all cases for simplicity. 4606 4607 The algorithm uses the code array produced in stage 1. 4608 One could have based the algorithm on the codex instead of the 4609 code, leading to a cleaner but more complex algorithm. The algorithm 4610 actually used is "unclean" in the sense that it depends on the 4611 particular output from stage 1 even though it could have depended 4612 only on the completely standardized format of the cache and codex. 4613 */ 4614 4615 pnt nameget(pnt caches,pnt ref,pnt idx){ 4616 pnt def=defget(caches,ref,idx,const_name); 4617 if(def==T) return T; 4618 return term2idx(def2rhs(def));} 4619 4620 void nameprint3(pnt x){ 4621 x=x&0xFF; 4622 if(x<32) printesc(x); else 4623 if(x<127) printf("%c",(int)x); else 4624 printesc(x);} 4625 4626 void nameprint2(pnt x){ 4627 for(;TAIL(x);x=TAIL(x)){ 4628 pnt i; 4629 pnt y=HEAD(x); 4630 for(i=0;i>8;}} 4631 for(x=HEAD(x);x>1;x=x>>8) nameprint3(x);} 4632 4633 void nameprint1(pnt caches,pnt term){ 4634 pnt ref=term2ref(term); 4635 pnt idx=term2idx(term); 4636 pnt name; 4637 if(term==T) printf(" T"); 4638 else if(ref==Z){printf("string ");spy2(1,idx);} 4639 else { 4640 printf("Index "); 4641 spy2(1,term2idx(term)); 4642 name=nameget(caches,ref,idx); 4643 if(name==T) return; 4644 printf(": "); 4645 nameprint2(name);}} 4646 4647 void nameprint0(pnt caches,pnt term){ 4648 nameprint1(caches,term); 4649 printf("\n");} 4650 4651 /* 4652 Skip the mtag_closure, mtag_lambda, and ttag_lambda constructs 4653 at the root of code entries and return the pair which is eventually 4654 going to be overwritten with the compiled version of the code entry. 4655 4656 The given term entry is supposed to be a mapcons so skiparg cannot 4657 be used on lambdas and quotes. 4658 */ 4659 pnt code2pair(pnt term){ 4660 for(term=HEAD(term);ROOT(term)!=TAG_PAIR;term=HEAD(term)); 4661 return term;} 4662 4663 /* 4664 Same as above, but return the untranslated definition instead of the pair 4665 */ 4666 pnt code2def(pnt term){ 4667 return HEAD(code2pair(term));} 4668 4669 void record_pattern1(pnt caches,pnt code,pnt def){ 4670 pnt lhs=term2arg2(def); 4671 pnt ref=term2ref(lhs); 4672 pnt idx=term2idx(lhs); 4673 pnt arg=tail(lhs); 4674 pnt rhs=term2arg3(def); 4675 pnt i; 4676 pnt name=nameget(caches,ref,idx); 4677 if(name==T) return; 4678 for(i=0;i