Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

10 files changed, 417 insertions, 197 deletions

diff --git a/src/main/smp/sys.smp b/src/main/smp/sys.smp
index 6a6d3ca3..7705a187 100644
--- a/src/main/smp/sys.smp
+++ b/src/main/smp/sys.smp
@@ -1,199 +1,11 @@
-// -*- mode: java;  -*-
 
-// top-level default import
-struct sys {
-    // libc bindings
-    /** https://www.man7.org/linux/man-pages/man2/<libc call>.2.html */
-    struct libc {
-        i32 errno = "C";
-        // fd  buf len -> len
-        {  i32 i64 u32 -> u32 } write = "C";
-        // fd  buf len -> len
-        {  i32 i64 u32 -> u32 } read = "C";
-        // status
-        {  i32 -> i32 } _exit = "C";
-        // addr len prot flags fd  off -> void*
-        {  i64  i64 i32  i32   i32 i32 -> i64 } mmap = "C";
-        // mmap flags
-        i32 PROT_EXEC = 4;
-        i32 PROT_READ = 1;
-        i32 PROT_WRITE= 2;
-        i32 PROT_NONE = 0;
-        i32 MAP_PRIVATE = 2;
-        i32 MAP_ANON = 32;
-    };
-    struct ary {
-        val copy = { u8[] dst, int doff, u8[~] src, int soff, int len ->
-            for( int i=0; i<len; i++ )
-                dst[i+doff] = src[i+soff];
-            return dst;
-        };
-    };
+// top-level default standard library import
 
-    // Ary/Vector of u8s - a resizable array of bytes.
-    struct aryu8 {
-        u32 !len = 0;
-        u8[] !buf;
-        // Grow as needed
-        val _grow = { int len2 ->
-            if( len+len2 < buf# ) return self;
-            int newlen = buf# * 2;
-            while( len+len2 >= newlen ) newlen *= 2;
-            u8[] buf2 = new u8[newlen];
-            sys.ary.copy(buf2,0,buf,0,buf#);
-            buf = buf2;
-            self;
-        };
-
-        // Add a character to aryu8
-        val add = { u8 c ->
-            _grow(1).buf[len++] = c;
-            self;
-        };
-
-        // Add a plain array to the aryu8
-        val addAry = { u8[~] ary ->
-            _grow(ary#);
-            sys.ary.copy(buf,len,ary,0,ary#);
-            len += ary#;
-            self;
-        };
-
-        // Remove x chars from the tail.
-        val undo = { int x ->
-            len = len >= x ? len-x : 0;
-            self;
-        };
-
-        // Print ASCII number into aryu8
-        val num = { i64 x ->
-            if( !x ) { add('0'); return self; }
-            if( x < 0 ) { add('-'); x = -x; }
-            i64 ten = 1, log = 0;
-            while( ten <= x ) { ten *= 10; log++; }
-            for( int i=0; i<log; i++ ) {
-                ten /= 10;
-                i64 q = x/ten;
-                u8 digit = q+'0';
-                add(digit);
-                x -= q*ten;
-            }
-            self;
-        };
-
-        // Write to fd, returns the number of bytes written (len).
-        val write = { i32 fd -> i64 ptr = buf; sys.libc.write(fd,ptr,len); };
-    };
-
-
-    // Scanner; a simple string parser.
-    struct Scan {
-        int !x;
-        u8[~] buf;
-
-        // Skip whitespace
-        val skip = { ->
-            while( buf[x] <= ' ' )
-                x++;
-            return self;
-        };
-
-        // True if find required character, and skip it; else False.
-        val match = { u8 c ->
-            skip();
-            if( buf[x] != c ) return false;
-            x++;
-            return true;
-        };
-
-        // Parse a simple number
-        val number = { ->
-            skip();
-            bool neg = match('-');
-            i64 n = 0;
-            while( '0' <= buf[x] & buf[x] <= '9' )
-                n = n*10 + (buf[x++] - '0');
-            return neg ? -n : n;
-        };
-    };
-
-    // Ary/Vector of i64s
-    struct aryi64 {
-        u32 !len = 0;
-        i64[] !buf;
-        // Grow as needed
-        val _grow = { int len2 ->
-            if( len+len2 < buf# ) return self;
-            int newlen = buf# * 2;
-            while( len+len2 >= newlen ) newlen *= 2;
-            i64[] buf2 = new i64[newlen];
-            for( int i=0; i<buf#; i++ )
-                buf2[i] = buf[i];
-            buf = buf2;
-            self;
-        };
-
-        // Add a i64 to aryu8
-        val add = { i64 c ->
-            _grow(1).buf[len++] = c;
-            self;
-        };
-
-        // Write to aryu8
-        val str = { ->
-            // TODO: clunky default constructor syntax
-            var str = new sys.aryu8 { buf = new u8[1]; }.add('[');
-            for( int i=0; i<len; i++ )
-                str.num(buf[i]).add(',').add(' ');
-            str.undo(2).add(']');
-        };
-    };
-
-    // Parse a comma-separated list of numbers, wrapped with square brackets,
-    // with optional whitespace  e.g. "[ -17, 0,99,12456789   ]  ".
-    // parseAryI64 & aryi64.str are bijections modulo whitespace.
-    // Returns null if the parse failed.
-    val parseAryI64 = { u8[~] str ->
-        !sys.Scan !s = new sys.Scan{ buf = str; };
-        if( !s.match('[') ) return null;
-        // Array of parsed results
-        var nums = new sys.aryi64{ buf=new i64[1]; };
-        // Parse a list of numbers
-        if( !s.match(']') ) {        // Handle the empty list
-            // Parse "123, " until a something else
-            while( s.x < s.buf# ) {
-                nums.add(s.number());
-                if( !s.match(',') )
-                    break;
-            };
-            if( !s.match(']') ) return null; // Close the list
-        }
-        return nums;
-    };
-
-    struct io {
-        // Print string to stdout
-        val p = { u8[~] str ->
-            i64 ptr = str;  // cast array base to i64
-            return sys.libc.write(1,ptr,str#);
-        };
-
-        // Return stdin as a u8[]
-        val stdin = { ->
-            var buf = new u8[8*1024];
-            i64 ptr = buf;
-            int len = 0;
-            while( true ) {
-                int rez = sys.libc.read(0,ptr,buf#);
-                if( rez < 0 ) sys.libc._exit(sys.libc.errno);
-                len += rez;
-                if( rez < buf# )
-                    break;
-                sys.libc._exit(-2); // Need to implement
-            }
-            // Compress
-            var dst = new u8[len];
-            return sys.ary.copy(dst,0,buf,0,len);
-        };
-    };
-};
+val adt = adt;                  // Abstract Data Types
+val ary = ary;                  // Array utilities
+val aryi64 = aryi64;            // Variable sized array of i64
+val aryu8 = aryu8;              // Variable sized array of u8
+val char = char;                // Character utilities
+val io = io;                    // IO library
+val libc = libc;                // libc FFI bindings
+val scan = scan;                // A simple string parser
diff --git a/src/main/smp/sys/adt.smp b/src/main/smp/sys/adt.smp
new file mode 100644
index 00000000..a4fe40bf
--- /dev/null
+++ b/src/main/smp/sys/adt.smp
@@ -0,0 +1,3 @@
+
+// Abstract data types.
+val bitset = bitset;
diff --git a/src/main/smp/sys/adt/bitset.smp b/src/main/smp/sys/adt/bitset.smp
new file mode 100644
index 00000000..d02cd2fe
--- /dev/null
+++ b/src/main/smp/sys/adt/bitset.smp
@@ -0,0 +1,57 @@
+
+// A set of non-negative integers, represented one bit per value.
+struct bitset {
+    i64[] !_bits;
+
+    new bitset = { ->
+        _bits = new i64[1];
+    };
+
+    // Return 0 for missing, non-zero for true
+    val get = { int bit ->
+        if( (bit >> 6) >= _bits# ) return false;
+        i64 mask = 1 << (bit & 63);
+        return (_bits[bit >> 6] & mask);
+    };
+
+    val _grow = { int bit ->
+        int x = bit >> 6;
+        int len = _bits#;
+        if( x < len ) return self;
+        while( x >= len ) len *= 2;
+        var bits = new i64[len];
+        for( int i=0; i<_bits#; i++ )
+            bits[i] = _bits[i];
+        _bits = bits;
+        return self;
+    };
+
+    // Set
+    val set = { int bit ->
+        i64 mask = 1 << (bit & 63);
+        _grow(bit)._bits[bit >> 6] |= mask;
+        return self;
+    };
+
+    // Test and set
+    val tset = { int bit ->
+        int idx = bit >> 6;
+        i64 mask = 1 << (bit & 63);
+        if( _grow(bit)._bits[idx] & mask )
+          return true;          // Already set
+        _bits[idx] |= mask;
+        return false;           // Was false (and now set)
+    };
+
+    val clr = { int bit ->
+        if( (bit >> 6) >= _bits# ) return self;
+        i64 mask = 1 << (bit & 63);
+        _bits[bit >> 6] &= (mask ^ -1);
+        return self;
+    };
+
+    val clear = { ->
+        for( int i=0; i<_bits#; i++ ) _bits[i] = 0;
+        return self;
+    };
+};
diff --git a/src/main/smp/sys/ary.smp b/src/main/smp/sys/ary.smp
new file mode 100644
index 00000000..8312e94c
--- /dev/null
+++ b/src/main/smp/sys/ary.smp
@@ -0,0 +1,24 @@
+
+// Array utilities
+
+// Copy byte array contents.  Copies the shorter of the buffers and len
+val copy = { u8[] dst, int doff, u8[~] src, int soff, int len ->
+    if( len > dst# - doff ) len = dst# - doff;
+    if( len > src# - soff ) len = src# - soff;
+    for( int i=0; i<len; i++ )
+        dst[i+doff] = src[i+soff];
+    return dst;
+};
+
+// Compare lexigraphically array contents.  Compares up to shorter array or
+// len.  Returns <0 or >0 for first non-matching byte.  Returns <0 or >0 for
+// the larger array after that, or 0 if both arrays are fully equal.
+val cmp = { u8[~] src1, u32 off1, u8[~] src2, u32 off2, u32 len ->
+    u32 len1 = len > src1# - off1 ? src1# - off1 : len;
+    u32 len2 = len > src2# - off2 ? src2# - off2 : len;
+    u32 max = len1 > len2 ? len2 : len1;
+    for( int i=0; i<max; i++ )
+        if( src1[off1+i] != src2[off2+i] )
+            return src1[off1+i] - src2[off2+i]; // Bytes determine compare
+    return len1 - len2;                         // Length determines compare
+};
diff --git a/src/main/smp/sys/aryi64.smp b/src/main/smp/sys/aryi64.smp
new file mode 100644
index 00000000..98b72605
--- /dev/null
+++ b/src/main/smp/sys/aryi64.smp
@@ -0,0 +1,82 @@
+
+// Ary/Vector of i64s
+struct aryi64 {
+    u32 !len = 0;
+    i64[] !buf;
+
+    new aryi64 = { i64[] b ->
+        buf = b;
+    };
+
+    // Grow as needed
+    val _grow = { int len2 ->
+        if( len+len2 < buf# ) return self;
+        int newlen = buf# * 2;
+        while( len+len2 >= newlen ) newlen *= 2;
+        i64[] !buf2 = new i64[newlen];
+        for( int i=0; i<buf#; i++ )
+            buf2[i] = buf[i];
+        buf = buf2;
+        self;
+    };
+
+    // Add a i64 to aryu8
+    val add = { i64 c ->
+        _grow(1).buf[len++] = c;
+        self;
+    };
+
+    val get = { int index -> return buf[index]; };
+
+    // Write the bracketed array-list form to aryu8.
+    val str = { ->
+        // TODO: clunky default constructor syntax
+        var str = new aryu8().add('[');
+        for( int i=0; i<len; i++ )
+            str.num(buf[i]).add(',').add(' ');
+        if( len ) str.undo(2);
+        return str.add(']');
+    };
+
+    val swap = { int i, int j ->
+        i64 tmp = buf[i];
+        buf[i] = buf[j];
+        buf[j] = tmp;
+        self;
+    };
+};
+
+
+
+// Parse a comma-separated list of numbers, wrapped with square brackets,
+// with optional whitespace  e.g. "[ -17, 0,99,12456789   ]  ".
+// parseAryI64 & aryi64.str are bijections modulo whitespace.
+// Returns null if the parse failed, without giving a clue as to why.
+val parseAryI64 = { u8[~] str ->
+    !scan !s = new scan(str);
+    if( !s.match('[') ) return null;
+    // Array of parsed results
+    var nums = new aryi64(new i64[1]);
+
+    // Parse a list of numbers
+    if( s.match(']') )          // Handle the empty list
+        return nums;
+
+    // Parse number commas "123, " until something else
+    while( s.x < s.buf# ) {
+        nums.add(s.number());
+        if( s.bad ) return null;
+        if( !s.match(',') )
+            break;
+    };
+    // Close the list
+    if( !s.match(']') ) return null;
+    s.skip();
+    return s.x == s.buf# ? nums : null;
+};
+
+val copy = { i64[] dst, int doff, i64[~] src, int soff, int len ->
+    for( int i=0; i<len; i++ )
+        dst[i+doff] = src[i+soff];
+    return dst;
+};
diff --git a/src/main/smp/sys/aryu8.smp b/src/main/smp/sys/aryu8.smp
new file mode 100644
index 00000000..21cf920b
--- /dev/null
+++ b/src/main/smp/sys/aryu8.smp
@@ -0,0 +1,87 @@
+
+// Ary/Vector of u8s - a resizable array of bytes.
+struct aryu8 {
+    u32 !len = 0;
+    u8[] !buf;
+
+    new aryu8 = { -> buf = new u8[1]; };
+
+    // Grow as needed
+    val _grow = { int len2 ->
+        if( len+len2 < buf# ) return self;
+        int newlen = buf# * 2;
+        while( len+len2 >= newlen ) newlen *= 2;
+        u8[] !buf2 = new u8[newlen];
+        ary.copy(buf2,0,buf,0,buf#);
+        buf = buf2;
+        self;
+    };
+
+    val clear = { -> len = 0; self; };
+
+    // Add a character to aryu8
+    val add = { u8 c ->
+        _grow(1).buf[len++] = c;
+        self;
+    };
+
+    // Add all of a plain array to the aryu8
+    val addAry = { u8[~] xs ->
+        _grow(xs#);
+        ary.copy(buf,len,xs,0,xs#);
+        len += xs#;
+        self;
+    };
+
+    // Remove x bytes from the tail.
+    val undo = { int x ->
+        len = len >= x ? len-x : 0;
+        self;
+    };
+
+    // Print ASCII number into aryu8
+    val num = { i64 x ->
+        if( !x ) { add('0'); return self; }
+        if( x < 0 ) { add('-'); x = -x; }
+        i64 ten = 1, log = 0;
+        while( ten <= x ) { ten *= 10; log++; }
+        for( int i=0; i<log; i++ ) {
+            ten /= 10;
+            i64 q = x/ten;
+            u8 digit = q+'0';
+            add(digit);
+            x -= q*ten;
+        }
+        self;
+    };
+
+    // Write to fd, returns the number of bytes written (len).
+    val write = { i32 fd ->
+        i64 ptr = buf; // Cast buffer pointer to i64 for native C call
+        libc.write(fd,ptr,len);
+    };
+};
+
+
+// Parse one integer, ignore trailing data; returns 0 with an empty string.
+// If you want a more robust parsing, use the `scan` class
+val atoi = { u8[~] str ->
+    int x = 0;
+    while( x < str# && str[x] <= ' ' ) x++;
+    if( x == str# ) return 0;
+    bool neg = false;
+    if( str[x]=='-' ) { neg=true; x++; }
+    i64 n = 0;
+    while( x < str# && '0' <= str[x] <= '9' )
+        n = n*10 + str[x++]-'0';
+    return neg ? -n : n;
+};
+
+// Zero-terminate string for libc strings.  No error checking, just copies and
+// appends a zero.
+{ u8[~] -> u8[] } str0 = { u8[~] str ->
+  u8[] !strz = new u8[str#+1];
+  ary.copy(strz,0,str,0,str#);
+  strz[str#] = '\0';
+  strz;
+};
diff --git a/src/main/smp/sys/char.smp b/src/main/smp/sys/char.smp
new file mode 100644
index 00000000..22ca4213
--- /dev/null
+++ b/src/main/smp/sys/char.smp
@@ -0,0 +1,8 @@
+
+val toupper = { u8 c ->
+    return c >= 'a' && c <= 'z' ? c - ('a' - 'A') : c;
+};
+
+val tolower = { u8 c ->
+    return c >= 'A' && c <= 'Z' ? c + ('a' - 'A') : c;
+};
diff --git a/src/main/smp/sys/io.smp b/src/main/smp/sys/io.smp
new file mode 100644
index 00000000..d6263ffe
--- /dev/null
+++ b/src/main/smp/sys/io.smp
@@ -0,0 +1,64 @@
+
+// Simple I/O Library
+
+// Write byte array to stdout
+val p          = { u8[~] str -> write(1,str); };
+val p_noInline = { u8[~] str -> write(1,str); };
+
+// Return fd contents as a u8[].
+val read = { i32 fd ->
+    var buf = new u8[8*1024];
+    i64 ptr = buf;
+    int len = 0;
+    while( true ) {
+        i32 rez = libc.read(fd,ptr,buf#);
+        if( rez > buf# ) libc._exit(libc.errno());
+        len += rez;
+        if( rez < buf# )
+            break;
+        libc._exit(-2); // Need to implement for more than 8K input
+    }
+    var out = new u8[len];
+    ary.copy(out,0,buf,0,len);
+};
+
+// Write all of str to fd.
+val write = { i32 fd, u8[~] str ->
+  i64 ptr = str;                // Convert array pointer to a i64 for the native call
+  libc.write(fd,ptr,str#);
+};
+
+// Write all of str to fd.
+val writeOff = { i32 fd, u8[~] str, u32 off, u32 len ->
+  i64 ptr = str;                // Convert array pointer to a i64 for the native call
+  ptr += off;                   // Skip offset
+  // Cap at available length
+  if( len > str# - off ) len = str# - off;
+  // Do the write
+  libc.write(fd,ptr,len);
+};
+
+// Return stdin as a u8[].
+val stdin = { -> read(0); };
+
+// Create file for writing.  Return fd, or -1 and errno has the error code
+val create = { u8[~] str ->
+    i64 ptr = sys.aryu8.str0(str);
+    i32 perms = 6*64 + 6*8 + 6; // 0666
+    return libc.creat(ptr, perms);
+};
+
+// Open file for reading.  Return fd, or -1 and errno has the error code
+val open = { u8[~] str ->
+    i64 ptr = sys.aryu8.str0(str);
+    return libc.open(ptr, sys.libc.O_RDONLY, 0);
+};
+
+// Close an open fd.  Return 0, or -1 and errno has the error code
+val close = { i32 fd -> return libc.close(fd); };
+
+// Remove a file.  Return 0, or -1 and errno has the error code
+val remove = { u8[~] str ->
+    i64 ptr = sys.aryu8.str0(str);
+    return libc.unlink(ptr);
+};
diff --git a/src/main/smp/sys/libc.smp b/src/main/smp/sys/libc.smp
new file mode 100644
index 00000000..17ee65cb
--- /dev/null
+++ b/src/main/smp/sys/libc.smp
@@ -0,0 +1,44 @@
+
+// libc bindings:
+//   https://www.man7.org/linux/man-pages/man2/<libc call>.2.html
+
+// The buffers are int-versions of zero-terminated strings.
+//     int buf = aryu8.str0("some_file");
+// buf mode perm-> fd
+{  i64 i32  i32 -> i32 } open = "C";
+// buf perm -> fd
+{  i64 i32 -> i32 } creat = "C";
+
+// fd  buf len -> len
+{  i32 i64 u32 -> i32 } write = "C";
+// fd  buf len -> len
+{  i32 i64 u32 -> i32 } read = "C";
+// fd  -> err
+{  i32 -> i32 } close = "C";
+// path -> err
+{  i64 -> i32 } unlink = "C";
+
+i32 O_RDONLY = 0;
+i32 O_WRONLY = 1;
+i32 O_RDWR   = 2;
+i32 O_CREAT = 512; // 02000 on x86_64-pc-cygwin
+i32 O_TRUNC = 1024; // 04000 on x86_64-pc-cygwin
+
+i32 STDIN  = 0;
+i32 STDOUT = 1;
+i32 STDERR = 2;
+
+// status
+{  i32 -> i32 } _exit = "C";
+// errno is not an ordinary C data symbol; read it through the native runtime.
+{ i32 } simple_errno = "C";
+val errno = { -> simple_errno(); };
+// addr len prot flags fd  off -> void*
+{  i64  i64 i32  i32   i32 i32 -> i64 } mmap = "C";
+// mmap flags
+i32 PROT_EXEC = 4;
+i32 PROT_READ = 1;
+i32 PROT_WRITE= 2;
+i32 PROT_NONE = 0;
+i32 MAP_PRIVATE = 2;
+i32 MAP_ANON = 32;
diff --git a/src/main/smp/sys/scan.smp b/src/main/smp/sys/scan.smp
new file mode 100644
index 00000000..44bedaaa
--- /dev/null
+++ b/src/main/smp/sys/scan.smp
@@ -0,0 +1,39 @@
+
+// Scanner; a simple string parser.
+struct scan {
+    int !x;                     // Cursor
+    bool !bad;                  // True after a malformed token
+    u8[~] buf;                  // Buffer to parse
+
+    new scan = { u8[~] b -> buf = b; };
+
+    // Skip whitespace
+    val skip = { ->
+        while( x < buf# && buf[x] <= ' ' )
+            x++;
+        return self;
+    };
+
+    // True if find required character, and skip it; else False.
+    val match = { u8 c ->
+        skip();
+        if( x >= buf# ) return false;
+        if( buf[x] != c ) return false;
+        x++;
+        return true;
+    };
+
+    // Parse a simple number
+    val number = { ->
+        skip();
+        bool neg = match('-');
+        if( x >= buf# || buf[x] < '0' || '9' < buf[x] ) {
+            bad = true;
+            return 0;
+        }
+        i64 n = 0;
+        while( x < buf# && '0' <= buf[x] & buf[x] <= '9' )
+            n = n*10 + (buf[x++] - '0');
+        return neg ? -n : n;
+    };
+};