1 /* JitterLisp: s-expression header. 2 3 Copyright (C) 2017, 2018, 2019, 2020 Luca Saiu 4 Written by Luca Saiu 5 6 This file is part of the JitterLisp language implementation, distributed as 7 an example along with Jitter under the same license. 8 9 Jitter is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Jitter is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */ 21 22 23 #ifndef JITTERLISP_SEXPRESSION_H_ 24 #define JITTERLISP_SEXPRESSION_H_ 25 26 27 /* Include headers. 28 * ************************************************************************** */ 29 30 #include <stdalign.h> 31 #include <stdbool.h> 32 33 /* We need the jitter_int and jitter_uint types. */ 34 #include <jitter/jitter.h> 35 36 /* The macros in this header are based on the Jitter tagging subsystem. */ 37 #include <jitter/jitter-tagging.h> 38 39 /* We rely on our CPP general-purpose macros, in particular for token 40 concatenation. */ 41 #include <jitter/jitter-cpp.h> 42 43 44 45 46 /* About this file. 47 * ************************************************************************** */ 48 49 /* An "s-expression" is a datum containing both a Lisp value and its Lisp type, 50 encoded in an efficient way. The C view of an s-expression is the 51 jitterlisp_object type. 52 53 This header provides macro definitions for encoding and decoding 54 s-expressions, which is to say for converting from a C object to the tagged 55 Lisp representation of the same object, and vice-versa, and for checking 56 the Lisp type of an s-expression. 57 58 S-expression allocation and memory handling are *not* covered here: see 59 jitterlisp-allocator.h . Operations on Lisp objects are not defined here 60 either: see jitterlisp-operations.h . */ 61 62 63 64 65 /* Tagged object representation. 66 * ************************************************************************** */ 67 68 /* A JitterLisp object is a tagged object. */ 69 typedef jitter_tagged_object jitterlisp_object; 70 71 72 73 74 /* Tagged object representation: conventions. 75 * ************************************************************************** */ 76 77 /* Some operations on tagged objects are more efficient with specific stag 78 values, particularly arithmetic and bitwise operations. When an operation 79 below needs to make such assumptions it always does it within CPP 80 conditionals checking for the actual tag value. 81 82 Tag values and widths must be kept easy to change in the future, even 83 conditionally to accommodate for different hardware. */ 84 85 /* For every tagged type foo the following macros are defined: 86 - the tag size in bits for foos, named JITTERLISP_FOO_TAG_BIT_NO; 87 - the tag for foos, named JITTERLISP_FOO_TAG; 88 - the untagged C type for foos, named JITTERLISP_FOO_UNTAGGED_TYPE; 89 - the macro JITTERLISP_FOO_ENCODE(untagged_exp), expanding to an r-value 90 evaluating to the tagged representation of the result of the evaluation 91 of untagged_exp as a foo; 92 - the macro JITTERLISP_FOO_DECODE(tagged_exp), expanding to an r-value 93 evaluating to the untagged representation of the result of the evaluation 94 of tagged_exp, as a JITTERLISP_FOO_UNTAGGED_TYPE. 95 - the macro JITTERLISP_IS_FOO(tagged_exp), expanding to an r-value which 96 evaluates to a C boolean, non-false iff the tagged expression has type 97 foo. */ 98 99 100 101 102 /* Fast-branch-unless helper macro. 103 * ************************************************************************** */ 104 105 /* Fast-branch to the given label if the given object does not have the given 106 tag, of the given number of bits. The arguments may be evaluated more than 107 once. */ 108 #define JITTERLISP_BRANCH_FAST_UNLESS_HAS_TAG(jitterlisp_tagged_object, \ 109 tag, \ 110 tag_bit_no, \ 111 label) \ 112 do \ 113 { \ 114 JITTER_BRANCH_FAST_IF_AND (((jitterlisp_tagged_object) \ 115 /* xor would work just as well as \ 116 minus, except that on x86 the \ 117 lea instruction can simulate a \ 118 three-operand minus but not a \ 119 three-operand xor. */ \ 120 - (jitter_uint) (tag)), \ 121 ((1LU << (tag_bit_no)) - 1), \ 122 label); \ 123 } \ 124 while (false) 125 126 127 128 129 /* S-expression representation: dummy "anything" type. 130 * ************************************************************************** */ 131 132 /* This dummy tag check succeeds with any object. It is convenient to have for 133 machine-generated code containing a tag-checking macro, which sometimes need 134 no actual check. */ 135 #define JITTERLISP_IS_ANYTHING(_jitterlisp_tagged_object) \ 136 true 137 138 /* Fast-branch to the given label iff the given object is not of "anything" 139 type -- which is to say, never fast branch. */ 140 #define JITTERLISP_BRANCH_FAST_UNLESS_ANYTHING(jitterlisp_tagged_object, \ 141 label) \ 142 do {} while (false) 143 144 145 146 147 /* S-expression representation: fixnums. 148 * ************************************************************************** */ 149 150 /* Fixnums are encoded unboxed as two's complement signed integers. */ 151 152 /* The tag for fixnums. Notice that a zero tag allows for more efficient sum 153 and subtraction operations, and this is exploited in the operation 154 definitions. */ 155 #define JITTERLISP_FIXNUM_TAG_BIT_NO 4 156 #define JITTERLISP_FIXNUM_TAG 0b0000 157 158 /* The C type for untagged fixnums. Notice that fixnums are always signed. */ 159 #define JITTERLISP_FIXNUM_UNTAGGED_TYPE jitter_int 160 161 /* Expand to an r-value evaluating to a C (untagged) boolean which is non-false 162 iff the given tagged object evaluates to a fixnum. */ 163 #define JITTERLISP_IS_FIXNUM(_jitterlisp_tagged_object) \ 164 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 165 JITTERLISP_FIXNUM_TAG, \ 166 JITTERLISP_FIXNUM_TAG_BIT_NO) 167 168 /* Expand to an r-value evaluating to the encoded representation of the given 169 untagged integer expression as a Lisp fixnum. */ 170 #define JITTERLISP_FIXNUM_ENCODE(_jitterlisp_untagged_fixnum) \ 171 JITTER_WITH_TAG_SHIFTED_ON((_jitterlisp_untagged_fixnum), \ 172 JITTERLISP_FIXNUM_TAG, \ 173 JITTERLISP_FIXNUM_TAG_BIT_NO) 174 175 /* Expand to an r-value evaluating to the untagged jitter_int content of the 176 given tagged fixnum. No type check is performed. */ 177 #define JITTERLISP_FIXNUM_DECODE(_jitterlisp_tagged_fixnum) \ 178 ((jitter_int) \ 179 JITTER_WITH_TAG_ASHIFTED_OFF(_jitterlisp_tagged_fixnum, \ 180 JITTERLISP_FIXNUM_TAG, \ 181 JITTERLISP_FIXNUM_TAG_BIT_NO)) 182 183 /* Expand to a constant expression evaluating to the number of bits used 184 to represent a fixnum, not counting tag bits. */ 185 #define JITTERLISP_FIXNUM_NON_TAG_BIT_NO \ 186 JITTER_BITS_PER_WORD - JITTERLISP_FIXNUM_TAG_BIT_NO 187 188 /* Expand to a constant expression evaluating to the most (respectively) 189 negative or positive fixnum, tagged. */ 190 #define JITTERLISP_FIXNUM_MOST_NEGATIVE \ 191 JITTERLISP_FIXNUM_ENCODE \ 192 (JITTER_MOST_NEGATIVE_SIGNED_IN_BITS (JITTERLISP_FIXNUM_NON_TAG_BIT_NO)) 193 #define JITTERLISP_FIXNUM_MOST_POSITIVE \ 194 JITTERLISP_FIXNUM_ENCODE \ 195 (JITTER_MOST_POSITIVE_SIGNED_IN_BITS (JITTERLISP_FIXNUM_NON_TAG_BIT_NO)) 196 197 /* Fast-branch to the given label if the given object is not a fixnum. The 198 arguments may be evaluated more than once. */ 199 #define JITTERLISP_BRANCH_FAST_UNLESS_FIXNUM(jitterlisp_tagged_object, \ 200 label) \ 201 JITTERLISP_BRANCH_FAST_UNLESS_HAS_TAG (jitterlisp_tagged_object, \ 202 JITTERLISP_FIXNUM_TAG, \ 203 JITTERLISP_FIXNUM_TAG_BIT_NO, \ 204 label) 205 206 207 208 209 /* S-expression representation: unique and character values. 210 * ************************************************************************** */ 211 212 /* Unique Lisp types populated by a single object such as (), #t and #f only need 213 very few bits to represent, so can use a longer stag with a suffix to be shared 214 with another type whose elements are relatively few in number. A good candidate 215 for such a type is the character type. Distinct characters are only about one 216 million in Unicode and therefore can be easily represented unboxed along with 217 every unique object. 218 219 I prefer to assume a wide fixed-width encoding for characters in memory, such 220 as UCF-4; however using single UTF-8 bytes as characters works as well; each 221 one will be considered an object of its own. 222 223 This is still quite wasteful in terms of the actual bit configuration used 224 in the space of the possible configurations. Some other type might fit 225 here in the future, with just one more stag bit to discriminate. */ 226 227 /* How to distinguish unique values from characters. */ 228 #define JITTERLISP_UNIQUE_TAG_BIT_NO 5 229 #define JITTERLISP_UNIQUE_TAG 0b01000 230 #define JITTERLISP_CHARACTER_TAG_BIT_NO 5 231 #define JITTERLISP_CHARACTER_TAG 0b11000 232 233 /* Expand to an r-value evaluating to a C (untagged) boolean which is non-false 234 iff the given tagged object evaluates to a unique object. */ 235 #define JITTERLISP_IS_UNIQUE(_jitterlisp_tagged_object) \ 236 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 237 JITTERLISP_UNIQUE_TAG, \ 238 JITTERLISP_UNIQUE_TAG_BIT_NO) 239 240 /* Like JITTERLISP_IS_UNIQUE , for characters. */ 241 #define JITTERLISP_IS_CHARACTER(_jitterlisp_tagged_object) \ 242 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 243 JITTERLISP_CHARACTER_TAG, \ 244 JITTERLISP_CHARACTER_TAG_BIT_NO) 245 246 /* Encode operation for a character. */ 247 #define JITTERLISP_CHARACTER_ENCODE(_jitterlisp_untagged_character) \ 248 JITTER_WITH_TAG_SHIFTED_ON((_jitterlisp_untagged_character), \ 249 JITTERLISP_CHARACTER_TAG, \ 250 JITTERLISP_CHARACTER_TAG_BIT_NO) 251 252 /* Encode operation for a unique-object index. */ 253 #define JITTERLISP_UNIQUE_ENCODE(_jitterlisp_unique_index) \ 254 JITTER_WITH_TAG_SHIFTED_ON((_jitterlisp_unique_index), \ 255 JITTERLISP_UNIQUE_TAG, \ 256 JITTERLISP_UNIQUE_TAG_BIT_NO) 257 258 /* Decode operation for a character. */ 259 #define JITTERLISP_UNIQUE_DECODE(_jitterlisp_tagged_object) \ 260 JITTER_WITH_TAG_LSHIFTED_OFF((_jitterlisp_tagged_object), \ 261 JITTERLISP_UNIQUE_TAG, \ 262 JITTERLISP_UNIQUE_TAG_BIT_NO) 263 264 /* Decode operation for a unique-object index. */ 265 #define JITTERLISP_CHARACTER_DECODE(_jitterlisp_tagged_object) \ 266 JITTER_WITH_TAG_LSHIFTED_OFF((_jitterlisp_tagged_object), \ 267 JITTERLISP_CHARACTER_TAG, \ 268 JITTERLISP_CHARACTER_TAG_BIT_NO) 269 270 /* Every unique object has a unique printable name. The array is meant to be 271 indexed by decoded unique values and is defined to have exactly 272 JITTERLISP_UNIQUE_OBJECT_NO elements. */ 273 extern const char * const 274 jitterlisp_unique_object_names []; 275 276 277 278 279 /* S-expression representation: specific unique objects. 280 * ************************************************************************** */ 281 282 /* Unique objects are simple unboxed objects, each represented as a shifted 283 index. They are efficient to compare to, but by themselves hold no mutable 284 state and no attributes. */ 285 286 /* How many unique objects there are. This of course must agree with the 287 definitions below. */ 288 #define JITTERLISP_UNIQUE_OBJECT_NO 6 289 290 /* Define every unique object. The names in the definition of 291 jitterlisp_unique_object_names must follow this order. */ 292 293 /* The #f object. In JitterLisp this is distinct from () and the symbol named 294 nil, which is a symbol like any other. */ 295 #define JITTERLISP_FALSE JITTERLISP_UNIQUE_ENCODE(0) 296 297 /* The #t object. */ 298 #define JITTERLISP_TRUE JITTERLISP_UNIQUE_ENCODE(1) 299 300 /* The () object. In JitterLisp this is distinct from #f and the symbol named 301 nil, which is a symbol like any other. */ 302 #define JITTERLISP_EMPTY_LIST JITTERLISP_UNIQUE_ENCODE(2) 303 304 /* The end-of-file or end-of-input object. This object has no reader syntax. */ 305 #define JITTERLISP_EOF JITTERLISP_UNIQUE_ENCODE(3) 306 307 /* A unique object conventionally used as the result of forms not evaluating to 308 any useful result. No reader syntax. */ 309 #define JITTERLISP_NOTHING JITTERLISP_UNIQUE_ENCODE(4) 310 311 /* A unique object used to represent the global value of globally unbound or 312 temporarily undefined variables, for example in the expansion of letrec . 313 This is used in the internal representation but should never be the result of 314 a correct evaluation. No reader syntax. */ 315 #define JITTERLISP_UNDEFINED JITTERLISP_UNIQUE_ENCODE(5) 316 317 /* Unique object predicates. Since unique objects are unboxed (and unique) 318 these are simple comparisons by identity. The expansion evaluates to a 319 C (untagged) boolean r-value. */ 320 #define JITTERLISP_IS_EMPTY_LIST(_jitterlisp_tagged_object) \ 321 ((_jitterlisp_tagged_object) == JITTERLISP_EMPTY_LIST) 322 #define JITTERLISP_IS_TRUE(_jitterlisp_tagged_object) \ 323 ((_jitterlisp_tagged_object) == JITTERLISP_TRUE) 324 #define JITTERLISP_IS_FALSE(_jitterlisp_tagged_object) \ 325 ((_jitterlisp_tagged_object) == JITTERLISP_FALSE) 326 #define JITTERLISP_IS_EOF(_jitterlisp_tagged_object) \ 327 ((_jitterlisp_tagged_object) == JITTERLISP_EOF) 328 #define JITTERLISP_IS_NOTHING(_jitterlisp_tagged_object) \ 329 ((_jitterlisp_tagged_object) == JITTERLISP_NOTHING) 330 #define JITTERLISP_IS_UNDEFINED(_jitterlisp_tagged_object) \ 331 ((_jitterlisp_tagged_object) == JITTERLISP_UNDEFINED) 332 333 334 335 336 /* S-expression representation: Booleans. 337 * ************************************************************************** */ 338 339 /* The Boolean constants JITTERLISP_FALSE and JITTERLISP_TRUE are unique values 340 like any other, already defined above. Booleans are not a separate "type" 341 in the sense of tags or even extended tags, but it is convenient for the user 342 to see them that way. The following convenience macros provide the 343 illusion. */ 344 345 /* Expand to an r-value (untagged) boolean evaluating to non-false iff the 346 given tagged object is #t or #f . */ 347 #define JITTERLISP_IS_BOOLEAN(_jitterlisp_tagged_object) \ 348 (JITTERLISP_IS_TRUE(_jitterlisp_tagged_object) \ 349 || JITTERLISP_IS_FALSE(_jitterlisp_tagged_object)) 350 351 /* Expand to an r-value evaluating to a tagged boolean value, true iff the given 352 argument evalutes to non-false. 353 354 This is difficult to make always efficient without requiring C's booleans to 355 be canonical, but should not be very critical. The conditional expression 356 should always be easy for GCC to optimize away when the encoded value is the 357 result of a C comparison accessible to the compiler rather than coming, for 358 example, from a function argument. */ 359 #define JITTERLISP_BOOLEAN_ENCODE(_jitterlisp_untagged_bool) \ 360 ((_jitterlisp_untagged_bool) ? JITTERLISP_TRUE : JITTERLISP_FALSE) 361 362 /* Expand to an r-value evaluating to a C (untagged) boolean value, false 363 iff the argument evaluates to the false boolean tagged value. This is 364 the preferred way of checking a JitterLisp object for falsity. */ 365 #define JITTERLISP_BOOLEAN_DECODE(_jitterlisp_tagged_bool) \ 366 ((_jitterlisp_tagged_bool) != JITTERLISP_FALSE) 367 368 369 370 371 /* S-expression representation: symbols. 372 * ************************************************************************** */ 373 374 /* Symbols are handled in a special way allocation-wise: interned symbols are 375 allocated with malloc, and live until the memory subsystem is finalized. 376 Uninterned symbols, on the other hand, live on the garbage-collected heap. 377 378 Both symbol types are encoded pointers to a struct jitterlisp_symbol . */ 379 #define JITTERLISP_SYMBOL_TAG_BIT_NO 3 380 #define JITTERLISP_SYMBOL_TAG 0b001 381 382 /* A symbol datum. */ 383 struct jitterlisp_symbol 384 { 385 /* The symbol name as a malloc-allocated string, or NULL if the symbol is not 386 interned. */ 387 char *name_or_NULL; 388 389 /* The value bound to the symbol in the global environment, or 390 JITTERLISP_UNDEFINED if there is no global binding. 391 392 FIXME: this makes each symbol a GC root which will require some careful 393 testing in the case of interned symbols, as they are malloc-allocated. */ 394 jitterlisp_object global_value; 395 396 /* A unique index for uninterned symbols, used for the compact printed 397 representation. Not used for interned symbols. */ 398 jitter_uint index; 399 400 /* Non-false if the global binding for the symbol is constant. */ 401 bool global_constant; 402 }; 403 404 /* Symbol tag checking, encoding and decoding. */ 405 #define JITTERLISP_IS_SYMBOL(_jitterlisp_tagged_object) \ 406 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 407 JITTERLISP_SYMBOL_TAG, \ 408 JITTERLISP_SYMBOL_TAG_BIT_NO) 409 #define JITTERLISP_SYMBOL_ENCODE(_jitterlisp_untagged_symbol) \ 410 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_symbol, \ 411 JITTERLISP_SYMBOL_TAG, \ 412 JITTERLISP_SYMBOL_TAG_BIT_NO) 413 #define JITTERLISP_SYMBOL_DECODE(_jitterlisp_tagged_symbol) \ 414 ((struct jitterlisp_symbol *) \ 415 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_symbol), \ 416 JITTERLISP_SYMBOL_TAG, \ 417 JITTERLISP_SYMBOL_TAG_BIT_NO))) 418 419 420 421 422 /* S-expression representation: conses. 423 * ************************************************************************** */ 424 425 /* Conses are represented boxed, with no header. Accessing the car and cdr 426 fields in memory is a frequent operation so it's particularly important to 427 decode tagged conses with subtractions, which are often optimizable. */ 428 429 #define JITTERLISP_CONS_TAG_BIT_NO 3 430 #define JITTERLISP_CONS_TAG 0b010 431 432 /* A cons datum. */ 433 struct jitterlisp_cons 434 { 435 /* The first cons field. */ 436 jitterlisp_object car; 437 438 /* The second cons field. */ 439 jitterlisp_object cdr; 440 }; 441 442 /* Cons tag checking, encoding and decoding. */ 443 #define JITTERLISP_IS_CONS(_jitterlisp_tagged_object) \ 444 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 445 JITTERLISP_CONS_TAG, \ 446 JITTERLISP_CONS_TAG_BIT_NO) 447 #define JITTERLISP_CONS_ENCODE(_jitterlisp_untagged_cons) \ 448 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_cons, \ 449 JITTERLISP_CONS_TAG, \ 450 JITTERLISP_CONS_TAG_BIT_NO) 451 #define JITTERLISP_CONS_DECODE(_jitterlisp_tagged_cons) \ 452 ((struct jitterlisp_cons *) \ 453 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_cons), \ 454 JITTERLISP_CONS_TAG, \ 455 JITTERLISP_CONS_TAG_BIT_NO))) 456 457 /* Fast-branch to the given label if the given object is not a cons. The 458 arguments may be evaluated more than once. */ 459 #define JITTERLISP_BRANCH_FAST_UNLESS_CONS(jitterlisp_tagged_object, \ 460 label) \ 461 JITTERLISP_BRANCH_FAST_UNLESS_HAS_TAG (jitterlisp_tagged_object, \ 462 JITTERLISP_CONS_TAG, \ 463 JITTERLISP_CONS_TAG_BIT_NO, \ 464 label) 465 466 467 468 469 /* S-expression representation: boxes. 470 * ************************************************************************** */ 471 472 /* This implementation of boxes is a temporary hack. Boxed should have their 473 own tag, and not just be conses with a particular shape. */ 474 475 #define JITTERLISP_IS_BOX(_jitterlisp_tagged_object) \ 476 (JITTERLISP_IS_CONS(_jitterlisp_tagged_object) \ 477 && (JITTERLISP_EXP_C_A_CDR(_jitterlisp_tagged_object) \ 478 == JITTERLISP_NOTHING)) 479 480 /* Fast-branch to the given label if the given object is not a box. The 481 arguments may be evaluated more than once. */ 482 #define JITTERLISP_BRANCH_FAST_UNLESS_BOX(jitterlisp_tagged_object, \ 483 label) \ 484 /* Again, this is obviously a temporary hack for the temporary \ 485 representation. */ \ 486 do \ 487 { \ 488 JITTERLISP_BRANCH_FAST_UNLESS_CONS (jitterlisp_tagged_object, \ 489 label); \ 490 JITTER_BRANCH_FAST_IF_NOTEQUAL (JITTERLISP_EXP_C_A_CDR \ 491 (jitterlisp_tagged_object), \ 492 JITTERLISP_NOTHING, \ 493 label); \ 494 } \ 495 while (false) 496 497 498 499 500 /* S-expression representation: closures. 501 * ************************************************************************** */ 502 503 /* Closures are represented boxed, with no header. */ 504 505 #define JITTERLISP_CLOSURE_TAG_BIT_NO 3 506 #define JITTERLISP_CLOSURE_TAG 0b011 507 508 /* A C type specifying the kind of a closure. */ 509 enum jitterlisp_closure_kind 510 { 511 /* An interpreted closure, run using the AST interpreter. */ 512 jitterlisp_closure_type_interpreted, 513 514 /* A compiled closure, run using the Jittery VM. */ 515 jitterlisp_closure_type_compiled 516 }; 517 518 /* The fields of an intepreted closure object. */ 519 struct jitterlisp_interpreted_closure 520 { 521 /* The non-global environment, as an a-list. */ 522 jitterlisp_object environment; 523 524 /* The procedure formal arguments as a list of distinct symbols. */ 525 jitterlisp_object formals; 526 527 /* The procedure body as an AST. */ 528 jitterlisp_object body; 529 }; 530 531 /* The fields of a compiled closure object. */ 532 struct jitterlisp_compiled_closure 533 { 534 /* How many nonlocals there are. FIXME: remove this unless it's needed 535 for garbage collection. */ 536 jitter_uint nonlocal_no; 537 538 /* Nonlocals as used in compiled code, with no names and with boxed nonlocals 539 stored as boxes; NULL if no nonlocals are needed. 540 541 This is currently a list; it should become a vector, ideally with immutable 542 size to avoid an indirection, after I properly implement vectors. */ 543 jitterlisp_object nonlocals; 544 545 /* The non-executable VM routine for the closure code. FIXME: I may want to 546 remove this, or make it optional for disassembling only, after the new 547 Jitter API allows me to free this independently from executable_routine. */ 548 /* This is actually a struct jitterlispvm_mutable_routine * object, but I'm declaring 549 this as a generic pointer to avoid cyclical CPP inclusion. */ 550 void *mutable_routine; 551 552 /* The executable VM routine for the closure code. */ 553 /* This is actually a struct jitterlispvm_executable_routine * object, but I'm 554 declaring this as a generic pointer to avoid cyclical CPP inclusion. */ 555 void *executable_routine; 556 557 /* The first program point of the VM routine above, always a prolog 558 instructions. This could be extracted as a field from the code itself, but 559 it's better to keep a copy here and avoid a memory dereference at call 560 time. 561 This is actually a jitterlispvm_program_point object, but we declare it as 562 a const void * (which is safe: jitterlispvm_program_point is a constant 563 pointer type on every dispatching model) to avoid cyclical CPP inclusion 564 problems. */ 565 const void *first_program_point; 566 }; 567 568 /* A closure datum. */ 569 struct jitterlisp_closure 570 { 571 /* The kind of this closure. */ 572 enum jitterlisp_closure_kind kind; 573 574 /* How many arguments this closure takes. */ 575 jitter_uint in_arity; 576 577 /* The kind determines which field of the anonymous union is actually used. 578 Notice that it's allowed, and useful, for a closure to change kind at run 579 time without changing its identity. */ 580 union 581 { 582 /* An interpreted closure. */ 583 struct jitterlisp_interpreted_closure interpreted; 584 585 /* An compiled closure. */ 586 struct jitterlisp_compiled_closure compiled; 587 }; 588 }; 589 590 591 /* Closure tag checking, encoding and decoding. */ 592 #define JITTERLISP_IS_CLOSURE(_jitterlisp_tagged_object) \ 593 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 594 JITTERLISP_CLOSURE_TAG, \ 595 JITTERLISP_CLOSURE_TAG_BIT_NO) 596 #define JITTERLISP_CLOSURE_ENCODE(_jitterlisp_untagged_closure) \ 597 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_closure, \ 598 JITTERLISP_CLOSURE_TAG, \ 599 JITTERLISP_CLOSURE_TAG_BIT_NO) 600 #define JITTERLISP_CLOSURE_DECODE(_jitterlisp_tagged_closure) \ 601 ((struct jitterlisp_closure *) \ 602 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_closure), \ 603 JITTERLISP_CLOSURE_TAG, \ 604 JITTERLISP_CLOSURE_TAG_BIT_NO))) 605 606 /* Closure tag and kind checking. */ 607 #define JITTERLISP_IS_INTERPRETED_CLOSURE(_jitterlisp_tagged_object) \ 608 (JITTERLISP_IS_CLOSURE(_jitterlisp_tagged_object) \ 609 && (JITTERLISP_CLOSURE_DECODE(_jitterlisp_tagged_object)->kind \ 610 == jitterlisp_closure_type_interpreted)) 611 #define JITTERLISP_IS_COMPILED_CLOSURE(_jitterlisp_tagged_object) \ 612 (JITTERLISP_IS_CLOSURE(_jitterlisp_tagged_object) \ 613 && (JITTERLISP_CLOSURE_DECODE(_jitterlisp_tagged_object)->kind \ 614 == jitterlisp_closure_type_compiled)) 615 616 617 618 619 /* S-expression representation: primitives. 620 * ************************************************************************** */ 621 622 /* Primitives are represented boxed. */ 623 624 #define JITTERLISP_PRIMITIVE_TAG_BIT_NO 3 625 #define JITTERLISP_PRIMITIVE_TAG 0b100 626 627 /* How many arguments a primitive can take, as a maximum. */ 628 #define JITTERLISP_PRIMITIVE_MAX_IN_ARITY 6 629 630 /* Primitives are call-by-value (therefore they all behave as procedures: if and 631 or , for example, cannot be primitives) and have a fixed in-arity, which in 632 interpreted code must be checked at call time. Primitives, like procedures, 633 always return exactly one result, which may be #<nothing> . */ 634 635 /* A primitive C function takes as its only argument an initial pointer to a C 636 array of already evaluated actual arguments, and returns the result which is 637 always exactly one. The primitive function checks the actual argument types 638 (when needed), but not their number. */ 639 typedef jitterlisp_object (*jitterlisp_primitive_function) 640 (const jitterlisp_object *evaluated_actuals); 641 642 /* A primitive descriptor, used for both primitive procedures and primitive 643 macros. Primitives descriptors are all global constants and don't live on 644 the garbage-collected heap, and don't need to be GC roots as they don't 645 point to other Lisp objects. Still it's important that each structure 646 begins at a double word boundary, so that we may tag them. The C 647 specification requires a structure to be aligned to the minimum common 648 multiple of the alignment of its members, which is why we add the alignas 649 specifier to a field -- it doesn't really matter which one. */ 650 struct jitterlisp_primitive 651 { 652 /* Make the first field, and therefore the whole struct, double-word aligned: 653 this ensures that enough low-order zero bits in the address can be 654 overwritten by my tag. */ 655 alignas (sizeof (jitter_int) * 2) 656 657 /* The primitive Lisp name as a C string. */ 658 char *name; 659 660 /* How many arguments the primitive takes. */ 661 jitter_uint in_arity; 662 663 /* Non-false iff the descriptor is for a primitive procedure rather than a 664 primitive macro. */ 665 bool procedure; 666 667 /* A C function implementing the primitive procedure or primitive macro. */ 668 jitterlisp_primitive_function function; 669 }; 670 671 /* Primitive tag checking, encoding and decoding. */ 672 #define JITTERLISP_IS_PRIMITIVE(_jitterlisp_tagged_object) \ 673 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 674 JITTERLISP_PRIMITIVE_TAG, \ 675 JITTERLISP_PRIMITIVE_TAG_BIT_NO) 676 #define JITTERLISP_PRIMITIVE_ENCODE(_jitterlisp_untagged_primitive) \ 677 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_primitive, \ 678 JITTERLISP_PRIMITIVE_TAG, \ 679 JITTERLISP_PRIMITIVE_TAG_BIT_NO) 680 #define JITTERLISP_PRIMITIVE_DECODE(_jitterlisp_tagged_primitive) \ 681 ((struct jitterlisp_primitive *) \ 682 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_primitive), \ 683 JITTERLISP_PRIMITIVE_TAG, \ 684 JITTERLISP_PRIMITIVE_TAG_BIT_NO))) 685 686 687 688 689 /* S-expression representation: vectors. 690 * ************************************************************************** */ 691 692 /* Vectors are represented boxed as a header pointing to the actual vector 693 elements as a separate heap buffer, not directly accessible by the user. */ 694 695 #define JITTERLISP_VECTOR_TAG_BIT_NO 3 // disabled: see below. 696 #define JITTERLISP_VECTOR_TAG 0b100 // disabled: see below. 697 698 // FIXME: vectors are currently disabled, until I implement object headers. 699 700 /* A vector header. */ 701 struct jitterlisp_vector 702 { 703 /* How many elements there are. */ 704 jitter_uint element_no; 705 706 /* A pointer to the first element. */ 707 jitterlisp_object *elements; 708 }; 709 710 // FIXME: vectors are currently disabled, until I implement object headers. 711 712 /* Vector tag checking, encoding and decoding. */ 713 /* #define JITTERLISP_IS_VECTOR(_jitterlisp_tagged_object) \ */ 714 /* JITTER_HAS_TAG((_jitterlisp_tagged_object), \ */ 715 /* JITTERLISP_VECTOR_TAG, \ */ 716 /* JITTERLISP_VECTOR_TAG_BIT_NO) */ 717 #define JITTERLISP_IS_VECTOR(_jitterlisp_tagged_object) \ 718 false 719 #define JITTERLISP_VECTOR_ENCODE(_jitterlisp_untagged_vector) \ 720 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_vector, \ 721 JITTERLISP_VECTOR_TAG, \ 722 JITTERLISP_VECTOR_TAG_BIT_NO) 723 #define JITTERLISP_VECTOR_DECODE(_jitterlisp_tagged_vector) \ 724 ((struct jitterlisp_vector *) \ 725 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_vector), \ 726 JITTERLISP_VECTOR_TAG, \ 727 JITTERLISP_VECTOR_TAG_BIT_NO))) 728 729 730 731 732 /* [FIXME: tentative] Non-primitive macros. 733 * ************************************************************************** */ 734 735 /* Non-primitive (low-level) macros are implemented exactly like interpreted 736 closures using struct jitterlisp_interpreted_closure , with a different 737 tag. */ 738 739 #define JITTERLISP_NON_PRIMITIVE_MACRO_TAG_BIT_NO 3 740 #define JITTERLISP_NON_PRIMITIVE_MACRO_TAG 0b101 741 742 743 /* Non-primitive-macro tag checking, encoding and decoding. */ 744 #define JITTERLISP_IS_NON_PRIMITIVE_MACRO(_jitterlisp_tagged_object) \ 745 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 746 JITTERLISP_NON_PRIMITIVE_MACRO_TAG, \ 747 JITTERLISP_NON_PRIMITIVE_MACRO_TAG_BIT_NO) 748 #define JITTERLISP_NON_PRIMITIVE_MACRO_ENCODE(_jitterlisp_untagged_non_primitive_macro) \ 749 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_non_primitive_macro, \ 750 JITTERLISP_NON_PRIMITIVE_MACRO_TAG, \ 751 JITTERLISP_NON_PRIMITIVE_MACRO_TAG_BIT_NO) 752 #define JITTERLISP_NON_PRIMITIVE_MACRO_DECODE(_jitterlisp_tagged_non_primitive_macro) \ 753 ((struct jitterlisp_interpreted_closure *) \ 754 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_non_primitive_macro), \ 755 JITTERLISP_NON_PRIMITIVE_MACRO_TAG, \ 756 JITTERLISP_NON_PRIMITIVE_MACRO_TAG_BIT_NO))) 757 758 759 760 /* [FIXME: tentative] Primitive macros. 761 * ************************************************************************** */ 762 763 /* Primitive macros are implemented exactly like primitives using struct 764 jitterlisp_primitive , with a different tag. */ 765 766 #define JITTERLISP_PRIMITIVE_MACRO_TAG_BIT_NO 3 767 #define JITTERLISP_PRIMITIVE_MACRO_TAG 0b110 768 769 /* Primitive-macro tag checking, encoding and decoding. */ 770 #define JITTERLISP_IS_PRIMITIVE_MACRO(_jitterlisp_tagged_object) \ 771 JITTER_HAS_TAG((_jitterlisp_tagged_object), \ 772 JITTERLISP_PRIMITIVE_MACRO_TAG, \ 773 JITTERLISP_PRIMITIVE_MACRO_TAG_BIT_NO) 774 #define JITTERLISP_PRIMITIVE_MACRO_ENCODE(_jitterlisp_untagged_primitive_macro) \ 775 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_primitive_macro, \ 776 JITTERLISP_PRIMITIVE_MACRO_TAG, \ 777 JITTERLISP_PRIMITIVE_MACRO_TAG_BIT_NO) 778 #define JITTERLISP_PRIMITIVE_MACRO_DECODE(_jitterlisp_tagged_primitive_macro) \ 779 ((struct jitterlisp_primitive *) \ 780 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_primitive_macro), \ 781 JITTERLISP_PRIMITIVE_MACRO_TAG, \ 782 JITTERLISP_PRIMITIVE_MACRO_TAG_BIT_NO))) 783 784 785 786 787 /* [FIXME: tentative] Macros. 788 * ************************************************************************** */ 789 790 /* A macro is either a primitive macro or a non-primitive macro. */ 791 #define JITTERLISP_IS_MACRO(_jitterlisp_tagged_object) \ 792 (JITTERLISP_IS_PRIMITIVE_MACRO(_jitterlisp_tagged_object) \ 793 || JITTERLISP_IS_NON_PRIMITIVE_MACRO(_jitterlisp_tagged_object)) 794 795 796 797 798 /* S-expression representation: ASTs. 799 * ************************************************************************** */ 800 801 // FIXME: support "extended" types sharing tags at the cost of having a header. 802 803 #define JITTERLISP_AST_TAG_BIT_NO 3 804 #define JITTERLISP_AST_TAG 0b111 805 806 /* Just a declaration for the AST data structure. Its definition is in 807 jitterlisp-ast.h . */ 808 struct jitterlisp_ast; 809 810 /* AST tag checking, encoding and decoding. */ 811 #define JITTERLISP_IS_AST(_jitterlisp_tagged_object) \ 812 JITTER_HAS_TAG(_jitterlisp_tagged_object, \ 813 JITTERLISP_AST_TAG, \ 814 JITTERLISP_AST_TAG_BIT_NO) 815 #define JITTERLISP_AST_ENCODE(_jitterlisp_untagged_AST) \ 816 JITTER_WITH_TAG_ADDED(_jitterlisp_untagged_AST, \ 817 JITTERLISP_AST_TAG, \ 818 JITTERLISP_AST_TAG_BIT_NO) 819 #define JITTERLISP_AST_DECODE(_jitterlisp_tagged_AST) \ 820 ((struct jitterlisp_ast *) \ 821 (JITTER_WITH_TAG_SUBTRACTED((_jitterlisp_tagged_AST), \ 822 JITTERLISP_AST_TAG, \ 823 JITTERLISP_AST_TAG_BIT_NO))) 824 825 826 827 828 /* Printed representation recursivity. 829 * ************************************************************************** */ 830 831 /* Expand to an r-value evaluating to a C boolean, non-false iff the argument 832 evaluates to a Lisp object of a type which may contain other Lisp objects in 833 its printed representation. The argument may be evaluated multiple times. 834 835 Rationale: this is used to avoid circularity checks when printing, for types 836 which cannot be recursive. */ 837 #define JITTERLISP_IS_RECURSIVE(_jitterlisp_object) \ 838 (JITTERLISP_IS_CONS(_jitterlisp_object) \ 839 || JITTERLISP_IS_CLOSURE(_jitterlisp_object) \ 840 || JITTERLISP_IS_MACRO(_jitterlisp_object) \ 841 || JITTERLISP_IS_VECTOR(_jitterlisp_object) \ 842 || JITTERLISP_IS_AST(_jitterlisp_object)) 843 844 845 846 847 /* Alignment requirement. 848 * ************************************************************************** */ 849 850 /* In order to represent tags we need this number of low-order bits to be 851 zero in initial heap pointers. */ 852 #define JITTERLISP_INITIAL_POINTER_ZERO_BIT_NO 3 853 854 855 856 857 /* Globally named objects. 858 * ************************************************************************** */ 859 860 /* A few s-expressions, particularly some interned symbols, are important enough 861 for performance reasons to be bound to global C variables. It would be nice 862 to make them constant, but this is not possible since most of them require 863 heap-allocation. 864 865 This requires them to be GC roots, which will need some work if I switch to a 866 moving GC. */ 867 extern jitterlisp_object jitterlisp_else; 868 extern jitterlisp_object jitterlisp_label; 869 extern jitterlisp_object jitterlisp_low_level_macro_args; 870 extern jitterlisp_object jitterlisp_primitive_make_constantb; 871 872 873 874 875 /* Not for the user: s-expression initialization and finalization. 876 * ************************************************************************** */ 877 878 /* These functions are called by jitterlisp_initialize and jitterlisp_finalize 879 as needed. They are not for the user to call directly. */ 880 881 /* Initialize the s-expression subsystem. This must be called before using any 882 other function declared here. */ 883 void 884 jitterlisp_sexpression_initialize (void); 885 886 /* Finalize the s-expression subsystem and free resources. After this is called 887 no other function declared here may be used again, until the subsystem is 888 re-initialized with jitterlisp_sexpression_initialize. */ 889 void 890 jitterlisp_sexpression_finalize (void); 891 892 #endif // #ifndef JITTERLISP_SEXPRESSION_H_ 893