Testing & debugging after completion of rewrite: 1. Read/write ordering bug in pop() -- returned top of stack after having already removed it. Needed to store to a temporary. 2. "return SC_NULL" instead of "RETURN(SC_NULL)" in reader. Considered renaming the macro, but by any other name it would still refer to the same concept and still be subject to confusion. Seems like a fundamental pun between C and the embedded stack machine language. Wouldn't happen in Scheme since there return is just something that happens to the last expresssion in a sequence, not a command. 3. Toplevel error handler seems to be getting run without an actual error. Replacing toplevel with more basic evaluation tests for now. 1 -> ERROR: apply: not a procedure: -945832504593831248 The error is correct (1 is not a procedure) but the display is wrong. (Incorrect untagging?) Problem was in parse_integer / parse_decimal. Before, I used a C heap based dynamic buffer mechanism, which tracked buffer pointer, allocation size and filled size in a struct. In the rewrite I converted this to a string on the Scheme heap, but since that doesn't distinguish fill from allocation, I tracked fill in the lexeme_length global variable. (Ugly, but this one internal use didn't seem to justify a whole new Scheme type.) But in porting the integer parsers I used the Scheme string's length (allocation) rather than the global. The chief hazard seems to be the two notions of length, and passing around this un-truncated buffer in the reader internals for efficiency. Reviewed other use of R_LEXEME for similar problems, finding none. Changed the number parsers to take length as an argument to at least reduce use of the global. #(1 2 3) -> ERROR: apply: not a procedure: #() Again, a correct error but bad read or print of the vector. In the reader, the length header of the vector was being set after the "len" variable had already been used to count down to zero. Rather than building the vector "by hand" I replaced this with the recently added make_vector_uninit function. But this also revealed that the local variable "len" was being unsafely used across a recursive call. Rather than push/popping it every time I took it out of the loop to be computed later by list_length(). Except here we already know the list is really a list, so I wrote a new unsafe_list_length function to omit the type and cycle checks of list_length. (letrec () 1) -> ERROR: eval: empty combination LETREC was passing the body to EVAL_BODY through R_EXPR instead of R_BODY. (Missed during manual register optimization.) Verified the other call to EVAL_BODY. This fixed #3. 4. A register conflict in the error handler, where r_error_handler was assigned to R_PROC, then R_ERR_DETAIL was referenced, but the latter two had been optimized to share a register. Solved by reassigning R_ERR_DETAIL to a free register. I did go to some pains to verify the register assignments but perhaps gave short shrift to the error handler. It would be a good exercise to do a full audit for register conflicts, once the code is a bit more settled. The rules for this are detailed in a comment. 5. Two bugs relating to list_length, which is supposed to return -1 for safely detecting non-lists. First, builtin_list_length stored its result in a "value" instead of a "long", which being an unsigned type, prevented recognizing the negative. Second, for odd length improper lists (e.g. (1 2 3 . 4)), the is_pair check after the first of the two "fast = cdr(fast)" pointer advancements in the loop returned directly, bypassing the "fast != SC_NULL" improper list check after the loop. This irregularity resulted from being overly preoccupied with (premature) hand-optimization (doing a single length += 2 after the two advances in each loop instead of a length++ after each one), a tendency I've had to fight in other places as well. (Chiefly, using the friendly type constructor and accessor functions, which tag/untag values as needed, rather than duplicating their functionality to save a few instructions on redundant tag operations. In this, it helped that I convinced myself, by examining the generated assembly, that the compiler optimizations really are smart enough to factor out the tag operations, at least in some cases, and at least with static functions.) 6. In SET, checked for cdr(R_EXPR) == SC_NULL after having overwritten the intended R_EXPR with car(R_EXPR). Swapped the order. (Discovered by running the "bad" semantic test set, but woulda come up soon enough anyway as it completely broke "set!".) (Later... somewhere around Jan 2017) 7. yes '(' | gscm -> inf loop between gc/error handler for out of memory. sc_error1 does a string() allocation to set R_ERR_MSG, but the stack doesn't get dropped until after the longjmp. Fixed by dropping stack in the error handler. Also wrote a toplevel error handler callable from Scheme implementing the same behavior using a captured continuation. 8. The "apply" builtin did not copy its final argument (a list). The standard doesn't seem to specify whether it should or not, but "list" is required to return a newly allocated list, and my no-op implementation was assuming its argument list was already a fresh copy. Wrote a test case and fixed by making builtin_apply copy. Also broken in tinyscheme. Affects what is probably the simplest way to copy a list, (apply list some-list). Major refactoring: compiler, variable references... October 2017: 9. Register effect bugs in assoc and member builtins (see tests-misc.scm). 10. Miscompilation of "delay" (see tests-misc.scm). 11. The compiler was not immune to redefinition of builtins. (REPL too?) Implemented immutable environments with a separate copy for the interaction environment. Immutable string/list/vector constants still need doing. Implemented piped subprocess extension 12. Realized input_port()/output_port() could leak the file object and descriptor if they hit an out of memory error. November 2017: fuzz testing 13. Infinite loop in the lexer for EOF in a comment. Implemented CLI options, memory stats, floor/ceiling/truncate/round/port? January 2018: 14. Heap discipline broken in arithmetic builtins on flonums by way of "fold" helper. April 2018: Partial implementation of the long-missing number->string and string->number builtins, enabling removal of a bunch of printfs. 15. Discovered by inspection that the open_file helper was unsafely storing a port in a local variable across a call to string_append_null. Made it pass the port by register instead and refactored a bit. 16. Realized that the changes implemented for #12 can't actually solve the problem; file objects and descriptors still leak if a subsequent unrelated call gets the memory error. Backed them out in order to simplify port construction. 17. builtin_open_subprocess was a mess all around. Changed the interface, improved comments, simplified the temporary argv construction (resolving a strict aliasing warning), and tightened syscall error handling. As above, realized that leaking resources due to allocation failures is not a problem that can be solved within the scope of this function (so e.g. it's fine to allocate the return value list after the child is spawned). 18. REPL now accepts multi-valued returns, printing them one per line. 19. Extensions are now available in an immutable (gales-scheme-environment), analogous to (scheme-report-environment 5), in addition to the interaction environment. This allows for hygienic packages making use of the extensions without dependency injection. Probably useless flush-input-port removed. Some toplevel error handler setup inconsistencies fixed, but the error plumbing needs more scrutiny. 20. Implemented double-width multiply functions, signed and unsigned, in portable C and x86_64 assembly, plus range checking and float conversion helpers. Used these to fix long-standing overflows in * and expt builtins. Implemented extensions for wrapped, carried and bitwise arithmetic on fixnums. Factored tagging macros out of machine-specific #if-blocks and tightened their types by casting. Need to finish correctness proof for signed wide multiply. May 2018: 21. Fixed self-initialization bug in macro expansion in fx-/wrap builtin (and added -Winit-self to gcc flags). Added fx-/carry-unsigned and fxmaj builtins. Made some internal functions static. Added startup assertion to enforce the assumption that unsigned long matches the value / pointer size. Minor tweaks to build in C99 pedantic mode; would like to move toward C89. 22. Implemented if-exists extension for open-output-file. Switched to "let" forms in toplevel. Made static symbol variable setup/usage more consistent. 23. Core: - Catch I/O errors in flush_port, read_char and peek_char, simplifying spec for flush-output-port builtin. - Light comment editing. Remove specification comments for nonstandard builtins, which now have their own extensions document. - Make eqv? and equal? do the simpler checks first, short-circuiting deep inspection where possible. - Rename quit builtin to exit. - Add a GC thrash factor (knob not exposed yet) to hasten OOM detection when GC reclaims less than heap_size/factor space. - Wipe registers on OOM detection (previously just the stack was dropped in sc_error1, with reason unclear). - Rename fallback error handlers to fatal/fatal1 for clarity. Core/compiler/toplevel: - Implement "error" as a normal builtin, parallel to sc_error1, making set-error-handler! work for Scheme-signalled errors too and removing the compiler's special error procedure with its null-terminator wrangling. - Remove syn-env from the special compiler environment as it can be handled purely from Scheme. - Merge the compiler environment (now just one binding) into the privileged toplevel environment. Toplevel: - Extend call-with-output-file and with-output-to-file to pass through the if-exists option. - Make with-input-from-file and with-output-to-file restore the current ports on escape or reentry, not required by spec but clearly the right thing. (Using a stub dynamic-wind, so won't actually work yet.) - Fix all four of those to work with multi-valued returns. - Make REPL error handler support multiple detail arguments (though the other components don't yet). 24. Added sync and data-sync options to flush-output-port extension. Refactoring of port argument wranglers. 25. Big move of builtins to library. Startup time and performance of the builtins in question is degraded, but much hazardous and hard-to-verify microcode is eliminated. Removed compiler dependence on builtin forms: and or Removed compiler dependence on builtin procedures: append apply assq for-each list list-tail map memq vector->list zero? Compiler now depends on some extensions and uses eq? for fixnum comparison, in hopes of reducing performance impact on replaced builtins. Merged the syntax library into the toplevel, removing some startup complexity and allowing the toplevel to use library syntax. Fixed some edge cases of the "case" macro. The "load" builtin, by way of exec-from-port, now reads the whole file before evaluating the forms. Forms moved from core to syntax library: and or Builtins moved to library: list append reverse list-tail list-ref memq memv member assq assv assoc vector->list apply map for-each New privileged builtins: apply/unchecked car/unchecked cdr/unchecked set-cdr/unchecked! vector-ref/unchecked fx+/unchecked Wrote some tests for the new library procedures. Accelerated negative tests by replacing bash/sed gunk with a custom error handler to run all in one process. Moved the currently failing immutability test to the negatives and expanded. June 2018: 26. Make "string-append" run in linear rather than quadratic time, fixing a FIXME. Make toplevel "apply" and "append" list copying helpers work tail recursively, by mutation in one pass as in the original C, reducing memory overhead. 27. Implemented dynamic-wind by adding a "spool" register and a new field in continuation objects to capture it, the necessary additions to the APPLY subroutine (now separated into APPLY_CONTINUATION), and a lowest common ancestor helper function. Substantially refactored error handling in both core and toplevel to: * work with dynamic winding while avoiding infinite loops; * avoid some unnecessary C to Scheme string conversions; * remove string_append helper, a poor interface (per change 26); * support multiple detail arguments to ERROR, per SRFI-23; * be generally clearer, I think. Similarly, the EXIT extension is now implemented using a continuation that returns the given code from the toplevel (and sc_toplevel now returns the code to main). This both makes it support unwinding and removes the need for a builtin exposing exit(). (At some point it might be nice to eliminate remaining uses of exit(), but so far it's still needed as an error handling fallback.) Builtins moved to library: string string->list vector set-error-handler! exit New privileged builtins: push-winding! string-ref/unchecked set-error-continuation! Extension added to library: error builtin_error still exists, but only for reporting startup errors before it's replaced by the toplevel. Fixed a few cases where pointers were being followed into the heap without untagging. This had gone unnoticed because the three tag bits happen to overflow in the shift for array indexing on 64-bit. Some minor clarity and error context improvements to library procedures. Renamed list_length/unsafe_list_length, to avoid giving the impression that safety can be assumed for these internal helper functions. Some C89ist shuffling of declarations. Optimized builtin_cons: reuse pair from arg list as it's freshly allocated. sc_toplevel now returns the integer exit code, TODO: think thorough / test what happens on error or other escape in unwinding/rewinding, explicitly unspecified by R5RS. 28. Minor optimization: compile quoted empty lists and quoted vectors to the values themselves, as they're not valid expressions and thus can be made self-evaluating simply by removing the check. Deprioritize "quote" in the builtin syntax dispatch (based on pure guesswork as to frequency). 1% speedup observed in some existing tests, 5% in a contrived one. Condense some redundant register aliases (R_OPERATOR->R_EXPR; R_BODY->R_OPERANDS), avoiding some pedantic self-assignment. 29. Fixed a subtle semantics bug in FORCE, and wrote test: a promise's code may be entered more than once if it forces itself recursively; if results differ, the first must not be clobbered. Found by re-reading rationale in R5RS. In the same spirit of "mutability is not your friend", reverted the builtin_cons optimization from #27. While safe, arglist mutation is premature at this point; for example it may hinder debugging, which ought to be a strength of an interpreter. If I do decide to allow it, there's a bunch of other builtins that could do it too. But a better optimization might be to avoid building arglists in the first place for fixed-arity builtins. 30. New builtins, with tests: immutable? cons/immutable string-copy/immutable vector-copy/immutable Slightly simplified some related code. In previous immutability work, rather than expose new primitives I had the reader construct strings and vectors as immutable. This was neither correct nor useful. Literal constants are now properly petrified by the compiler, and with that, all my tests are finally passing. 31. Mega-IO-refactor, replacing stdio with Scheme-managed buffering, and implementing sockets extension. Port-based write functions now all use R_PORT rather than an argument and signal errors rather than returning status. This tidies up the printer quite a bit. Checking for open port on each read/write no longer needed - the kernel's FD validity check is enough. - Added bonus: (close-output-port (current-output-port)) at REPL was a segfault as the check had been missed in the fallback error handler. Now "FATAL: Bad file descriptor". - Should probably prevent closing stdin/out though. (close-input-port (current-input-port)) at REPL is an infinite loop. Replaced posix_spawn* with vfork, simplifying builtin_open_subprocess, possibly making it fast on more platforms, and removing another likely malloc user. New privileged builtins operating at the file descriptor level: inet-stream-socket inet-dgram-socket unix-stream-socket unix-dgram-socket socket-ports getsockname getpeername connect-inet connect-unix listen accept close New library procedures: open-tcp-connection open-tcp-listener open-udp-socket open-unix-connection open-unix-listener open-unix-datagram-socket call-with-tcp-connection call-with-unix-connection sequential-tcp-server sequential-unix-server 32. Fix assertion violation (buffer overflow) introduced in #31, when writing to a closed port, catching the error, then writing again. Relatedly, any other write errors on the underlying FD will now close the port. (Rationale: if recovery were possible, the underlying system should already be doing it, so write errors are generally permanent; even if not, they can be asynchronous so no way to know how much was successfully written.) REPL error handler changed back to restarting using a captured continuation. (I think I had removed this deliberately in #27 in the spirit of simplifying, but the result was the REPL exiting with error status on a normal ^D termination if an error had ever been caught, because error handlers aren't really supposed to return.) Ugly (define-r5rs 'foo (lambda ...)) forms changed to internal definitions followed by bulk registration, in the same manner as the extensions in #31. 33. New builtin: char-ready?, made possible by direct access to input buffers. Stream sockets are made nonblocking to work around poll/select defects, but undetected blocking is still possible, e.g. reading from disk or if standard input is an externally provided socket. Builtin moved to library and tests added: equal? 34. Libc in-sourcing: - Removed stdio from main.c and indirect use via assert - Removed last direct uses of malloc by replacing GC root linked list with an array and heap creation with mmap, also enabling the hugepages option - Removed last indirect use of malloc via atexit - Replaced stdlib.h/string.h with individual declarations Made write_err handle EINTR/EAGAIN/EWOULDBLOCK, sharing with flush_output_port. July 2018: 35. Start of library-level bignum support, including addition, subtraction, Comba multiplication, and automatic fixnum promotion and demotion. Using non-opaque values until the proper privileged interface is settled. It looks like the reader and printer will have to be done in Scheme now. (They'd have to make non-tail calls back into Scheme to do base conversion, and such C-level recursion is verboten.) So much the better for sanity and future rewrites of the core though. A pared-down bootstrap reader will be preserved. Core: - More assertions - Flush ports on abort (with re-entry check, as flushing itself has assertions) - Bignum awareness in number predicates - Start replacing car(cdr(x)) pattern with cadr macro Builtins moved to library: + - * New builtin: fxvector/unchecked Builtins moved to library: read string->number The full range of numeric syntax is now supported except for rational and complex: alternate radix (2/8/10/16), radix and exactness prefixes, exponents and sharped-out digits (though significant figures aren't actually tracked). Bignums come "for free", though base conversion is the naive quadratic algorithm. Simplified the (now) bootstrap number decoder by removing float syntax and promotions. Internal tweaks to the lexer and (now) bootstrap reader to support read-token. Also loosened the overly anal interpretation of allowed whitespace. Started downcasing labels (all-caps doesn't really serve a purpose and risks interference from libc extensions). 37. Bignum division, conversion to flonum and output. Bugfix: bignum negation failed to demote in the case of *LEAST-FIXNUM*. Minor optimization: avoid some unnecessary untagging in fixnum ops. Builtins moved to library: zero? positive? negative? abs quotient remainder modulo exact->inexact number->string write display newline In addition to bignum support, quotient/remainder/modulo now properly maintain inexactness for flonum inputs, though can produce inf/nan. In the Scheme rewrite of the printer, I realized the special save/restore of current ports for error recovery is unnecessary now that dynamic-wind is taking care of it (they can't be set directly by user code). New library procedures: gcd lcm New builtins: fx= fx< fx<= fx<=/unsigned fxlength/unsigned Renamed builtin: fxshift-unsigned to fxshift/unsigned New privileged builtins: fxdiv/unchecked fxdiv/ext/unchecked fixnum->dec/unchecked fixnum->hex/unchecked fixnum->oct/unchecked fixnum->bin/unchecked flonum->dec/unchecked flonum/unsigned/unchecked flodiv/unchecked floquotient/unchecked floremainder/unchecked builtin? builtin-name promise? continuation? 38. Full bignum integration. Serious bugfix: (QUOTIENT *LEAST-FIXNUM* -1) => *LEAST-FIXNUM* (On the first pass for #37 it didn't occur to me that signed fixnum quotient had an edge case besides zero divisor. The equivalent problem existed in the prior C-only implementation, or possibly worse as C leaves negative division implementation-defined.) Builtins moved to library: eqv? = < > <= >= odd? even? max min / floor ceiling truncate round exp log sin cos tan asin acos atan sqrt expt inexact->exact Bignums now opaque and supported by all generic operators. Unlike the fixnum and flonum ops, which could also exist as unprivileged extensions, the bignum primitives are implicitly unchecked. In addition to bignum support, the irrational functions now handle some special cases for exactness e.g. zero (as encouraged but not required). New privileged builtins: toplevel-environment set-car/unchecked! fxbin/unsigned/unchecked flo=/unchecked flofixnum/unchecked floor/unchecked ceiling/unchecked truncate/unchecked round/unchecked exp/unchecked log/unchecked sin/unchecked cos/unchecked tan/unchecked asin/unchecked acos/unchecked atan/unchecked atan2/unchecked sqrt/unchecked make-bignum bignum? bignum-negative? bignum-set-negative! bignum-ref bignum-set! bignum-length bignum bignum/unsigned bignum2 bignum-truncate! Renamed privileged builtins: fxdiv/unchecked -> fxdiv/unsigned/unchecked fxdiv/ext/unchecked -> fxdiv/ext/unsigned/unchecked (They were already unsigned; I think I'd been trying to avoid the crazy long names, but it was a hazard.) Core: - Grabbed the last extended type slot to fit the bignum sign bit - Type assertions added to fixnum_val, new counterpart unsigned_fixnum_val, and flonum_val, expanding coverage while reducing boilerplate - Bounds check assertion added to vector_ref and vector_set - With flonum coercion headaches out of core, finally replaced safe_fixnum_val and exact_fixnum_val with something simple and correct - is_number optimized based on extended number type tag values being contiguous - is_integer made possibly more standard conformant by using ROUND (nearbyint) instead of FLOOR for flonums (don't see how this could make a difference but neither am I sure it can't) - Made shallow_print report particular environment specifiers, the internal specials, immutability, and vector lengths - make_str and make_vector size checks simplified based on the unsigned trick Compiler: - Removed fairly useless vector support from macro language - Fixed old bug: improper rejection of macros expanding to #f - Removed trivial dependency on generic < - Switched to storing error context as symbol, avoiding SYMBOL->STRING calls in the normal case Toplevel: - Pretty "evaluates to" symbol prefixing REPL results - Tracing for library procedure calls, allowing removal of the growing sprawl of ad-hoc error context reporting - Filled in stubs for bignum to hex, octal and binary conversion - Handled bignum status in EXIT by remaindering there rather than in core asm-generic: - Replaced "seems right but can't prove" implementation of signed double-width multiply with ugly but more obvious method August 2018: 39. Serious bugfix: plug leaks of uncompiled subtrees in named LET and DO, while simplifying, by feeding the full expansions back through compilation as is done for ordinary macros. (Less seriously, the same for lambda annotation in plain LET, at worst a performance issue.) Core: - Add is_port assertions to R_PORT-based I/O routines - Remove unnecessary variable pre-check in SET, allowing resolve_variable_ref to operate on unresolved refs only, saving a few branches - Remove fairly pointless and expensive is_list assertion in EVAL - Remove redundant is_fixnum assertion from builtin_make_bignum Compiler: - More consistently unquote self-evaluating objects - Reject non-readable objects (possible through EVAL) Syntax library: - OR: optimize by avoiding unnecessary temporary binding (multiple evaluation is safe for non-list expressions as they're all side-effect free and O(1)) - Explain how the hardcoded temporary names are safe - COND: simplify by handling the temporary binding case with OR - CASE: optimize by using EQV? instead of MEMV for the single-datum case 40. Core/compiler: - Prevent integer overflows by limiting parameter list length (number of bindings per lexical frame) - Save a word in the procedure object and a pair in the annotated lambda form by encoding variadic status in the sign of the arity Core: - Avoid possibly undefined overflow behavior in untag_signed by doing the left shift as unsigned - Note a hazard in add_tag/ext_add_tag and audit Compiler: - Slight simplifications/optimizations: filterize CHECK-IDENT; avoid repeated SYMBOL->STRING in duplicate search 40.maint1. Starting a maintenance branch as the crucial variable lookup optimization has not yet made it back after the compiler overhaul of revision 41. Core: - Remove assertions in stack ops, redundant since adding type assertions to car/cdr long ago - Remove invalid assertion added in r39: input_port_ready doesn't use R_PORT - Remove mostly redundant is_list assertions in the full environment lookups March 2020: 40.maint2. Overall: - Restructure tree for slashpackage - Trim Makefile - Write install + check scripts and README Main (backports): - Make default heap size build-time tunable (isolating magic numbers) - Report build configuration in help text - Remove "strtol" stdlib dependency 40.maint3. Bulk reindent & reflow. - Tabs: good - Non-meaningful newlines in human text: bad - "if" as a special "lisp word" producing less indentation: bad - Code width: mostly sticking to 80 columns