`register` is a hint if you don't specify which register you want to use - however, if you specify the register it will clobber it.

    noinline void bar() 
    {
        register void *parent __asm__("r10");
        ...
    }

    noinline void bar() 
    {
        void *volatile parent;
        // set parent = %r10 before anything else.
        asm volatile ("mov{q}\t{%%r10, %0|%0, r10}" : "=r"(parent) : : "r10");
        ...
    }

In both cases you would set the register immediately before making the call, again using `volatile`. Since `r10` is not used by a typical call in SYSV - it's the static chain pointer in the SYSV convention, but otherwise usable as a GP register, a call will not overwrite it.

    void foo()
    {
        struct foo_frame {
            int x;
        } locals = { 
            .x = 999
        };

        // Set `r10` to our function's local frame
        asm volatile("mov{q}\t{%0, %%r10|r10, %0}" : : "r"(&locals) : "r10")
        
        bar();
    }

Demo: https://godbolt.org/z/cM9d8e1r5

For other registers which are part of the regular calling convention, we might be able to clobber them if they wouldn't normally be used for the call. Eg, if our function takes regular 2 arguments, they would be in `rdi` and `rsi` - so we could use `rdx`, `rcx`, `r8`, `r9` like the above, but if our function took 6 or more regular arguments we wouldn't be able to use any of these in this way. If we wanted a custom calling convention we could just make all functions have zero-arguments and perform all of the setting and capturing ourself - which gives us more control than using [[musttail]] - though less portable, and may prevent optimizations the compiler could otherwise make.

Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.

The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.

[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...

The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).

You can use the trick if the array can shrink as long as you always shrink the allocation when length goes below the next power of 2 not greater than len (which may make use of stdc_bit_floor).

[1]:https://cl-pdx.com/static/techlists.pdf

    #define Array(T) struct array_##T
    #define DEFINE_ARRAY(T) struct array_##T { size_t len; T *elems; }
    
    DEFINE_ARRAY(int);
    Array(int) foo;
    Array(int) bar;

    #define Array(T) struct array_##T { size_t len; T *elems; }

    Array(int) foo;
    Array(int) bar;

With a struct we would need one struct for each element type - at least prior to C23 which provides a better approach where we can declare the same struct multiple times in a translation unit.

    #define Array(T) struct array_##T { size_t len; T *elems; }

However, using an 2-element array to avoid using a struct is silly.

Anything needs to be demonstrated and used in practice before being included in the standard. The standard is only meant to codify existing practices, not introduce new ideas.

It's up to compiler developers to ship first, standardize later.

They appear procedural because of syntax sugar - ie, the body of a function is basically implicitly wrapped in (progn ...), (begin ...), ($sequence ...), etc - which are all equivalent expression forms which evaluate their sub-expressions in order and return the result of the last one.

   (progn a b c)      ;; CommonLisp
   (begin a b c)      ;; Scheme
   ($sequence a b c)  ;; Kernel

   ;; evaluate a, then b, then c, 
   ;; ignore the results of evaluating a and b 
   ;; return the result of evaluating c.

   (define (foo)
       (expr1)
       (expr2)
       (expr3))

    (define foo (lambda () (begin (expr1) (expr3) (expr3))))

A similarity is the comma operator in C. Imagine you didn't write statements but the body of your C functions was entirely chains of comma operators.

CommonLisp has a couple of other useful related forms - prog1 and prog2. They still evaluate their sub-expressions in order, but prog1 returns the result of evaluating the first expression, and prog2 returns the result of the second expression.

    (define (foo) (prog1 (expr1) (expr2) (expr3))
    (foo)
 
    ;; evaluates expr1, then expr2, then expr3
    ;; returns the result of evaluating expr1
    ;; ignores the results of evaluating expr2 and expr3

    (foo (+ 2 3) (* 3 4))
    ($bar (+ 2 3) (* 3 4))

`$bar` however, receives its operands verbatim. It receives (+ 2 3) as its first operand and (* 3 4) as its second - unevaluated.

The operative/FEXPR body decides how to evaluate the operands - if at all.

The difference between an operative/FEXPR and a macro is that macros are second-class objects which must appear in their own name - we cannot assign them to variables, pass them or return them from functions. Operatives and FEXPRs are first-class objects that can be treated like any other.

The difference between FEXPRs and Operatives is to do with scoping and environments. FEXPRs were around before Scheme - when Lisps were dynamically scoped. This meant we could have unpredictable behavior and so called "spooky action at distance". They were problematic and basically abandoned almost entirely in the 1980s.

Shutt introduced Operatives as a more hygienic version - based on statically scoped Scheme. Instead of the operative being able to mutate the dynamic environment arbitrarily, there are limitations. The first part of this is that environments are made into first-class objects - so we can assign them to a symbol and pass them around. The final part is that an operative receives a reference to the dynamic environment of its caller - which we bind to a symbol using the operative constructor, `$vau`.

    ($vau (operands) dynamic-env . body)

    ($lambda (arguments) . body)

The body can decide to evaluate the operands using the environment of the caller - essentially behaving as if the caller had evaluated them

    (eval operands dynamic-env)

This also allows the operative to mutate the environment of its callee - but only the locals of that environment. The parent environments cannot be mutated through the reference `dynamic-env`.

Technically, `$lambda` is not primitive in Kernel - though it is the main constructor of applicatives (functions) - the primitive constructor is called `wrap` - and it takes another combiner (an operative or applicative) as its parameter. Wrapping a combiner simply forces the evaluation of its arguments when called - so functions are just wrappers around operatives - and the underlying operative of any function can be extracted with `unwrap`.

There's a lot more to them. They're conceptually quite simple in terms of implementation, but they have enormous potential use cases that are unexplored.

Read more on the Kernel page[1]. In particular, the Kernel report[2]. There's also a formal calculus describing them, called the vau calculus[3].

[1]:https://web.cs.wpi.edu/~jshutt/kernel.html

[2]:https://ftp.cs.wpi.edu/pub/techreports/pdf/05-07.pdf

[3]:https://web.archive.org/web/20150224035948/http://www.wpi.ed...

    [#environment]

Perhaps having `@` produce an environment is the wrong approach and we should just produce an association list instead - then move `$bindings->environment` into the `?` operative to enable querying.

I've written a number of less complete interpreters over the years. I currently have a long-running side-project to provide a more complete, highly optimized implementation for x86_64.

[1]:https://github.com/dbohdan/klisp

[2]:https://github.com/ghosthamlet/bronze-age-lisp

I use C preprocessor macros extensively and don't have the typical dislike for them that many people have - though I clearly understand their limitations and the advantage Scheme macros have over them.

Since learning Kernel, the boundary of "compile time" and "runtime" is more blurry - I can write operatives which behave somewhat like a macro, and I do more "multi-stage" programming, where one operative optimizes its argument to produce something more efficient which is later evaluated - though there are still limitations due to the inability to fully compile Kernel.

As one example, I've used a kind of operative I call a "template", which evaluates its free symbols ahead of time but doesn't actually evaluate the body. When we later apply the some operands it replaces the bound symbols with the operands, looking up any symbols to produce an expression which we don't need to immediately evaluate either - but this expression has all symbols fully resolved. This is somewhere between a macro and regular operative.

Consider:

    ($define! z 10)

    ($define! @add-z
        ($template (x y)
            (+ x y z)))

    ([#applicative: +] x y 10)

    > ($let ((x 9)
             (y 7))
          (@add-z (* x 3) (- y 13)))
    ([#applicative: +] ([#applicative: *] 9 3) ([#applicative: -] 7 13) 10)

---

The $template form above isn't too difficult to implement. I've iterated several forms of this - some which only partially resolved the bound symbols, but lost them in a RAID failure. An earlier version which has some issues I still have because I put it online:

    ($provide! ($template)
        ($define! $resolve-free-symbols
            ($vau (params expr) env
                ($cond
                    ((null? expr) ())
                    ((pair? expr)
                        (cons (apply (wrap $resolve-free-symbols) 
                                     (list params (car expr)) 
                                     env)
                              (apply (wrap $resolve-free-symbols) 
                                     (list params (cdr expr)) 
                                     env)))
                    ((symbol? expr)
                        ($if (member? expr params)
                             expr
                             (eval expr env)))
                    (#t expr))))

        ($define! $resolve-bound-symbols
            ($vau (params expr) env
                ($cond
                    ((null? expr) ())
                    ((pair? expr)
                        (cons (apply (wrap $resolve-bound-symbols)
                                     (list params (car expr))
                                     env)
                              (apply (wrap $resolve-bound-symbols)
                                     (list params (cdr expr))
                                     env)))
                    ((symbol? expr)
                        ($if (member? expr params)
                             (eval expr env)
                             expr))
                    (#t expr))))

        ($define! zip
            ($lambda (fst snd)
                ($cond
                    (($and? (null? fst) (null? snd)) ())
                    (($and? (pair? fst) (pair? snd))
                        (cons (list (car fst)
                                    (list* (($vau #ignore #ignore list)) (car snd)))
                              (zip (cdr fst) (cdr snd)))))))

        ($define! $template
            ($vau (params body) senv
                ($let ((newbody 
                        (eval (list $resolve-free-symbols params body) senv)))
                    ($vau args denv
                        (eval (list $resolve-bound-symbols params newbody)
                              (eval (list* $bindings->environment
                                           (zip params args))
                                    denv))))))) 

At present the best interpreter is klisp, and the fastest is bronze-age-lisp, which uses klisp - with parts of hand-written 32-bit x86 assembly.

I've been working on a faster interpreter for a number of years as a side project, optimized for x86_64 with some parts C and some parts assembly. It has diverged in some parts from the Kernel report, but still retains what I see are the key ingredients.

My modified Kernel has optional types, and we have operatives to `$typecheck` complex expressions ahead of evaluating them. I intend to go all in on the "multi-stage" aspect and have operatives to JIT-compile expressions in a manner similar to the above template.

    true        #t
    false       #f
    null        ()
    [...]       (& ...)
    "k" : v     (: k v)
    {...}       (@ ...)  

    ($define! &
        ($lambda args (cons list args)))

    ($define! : 
        ($vau (key value) env
            (list key (eval value env))))
            
    ($define! @ 
        (wrap 
            ($vau kvpairs env 
                (eval (list* $bindings->environment kvpairs) env))))

    ($define! person
        (@
            (: first_name "John")
            (: last_name "Smith")
            (: is_alive #t)
            (: age 27)
            (: address 
                (@
                    (: street_address "21 2nd Street")
                    (: city "New York")
                    (: state "NY")
                    (: postal_code "10021-3100")))
            (: phone_numbers
                (& (@ (: type "home") (: number "212 555-1234"))
                   (@ (: type "office") (: number "646 555-4567"))))
            (: children
                (& "Catherine" "Thomas" "Trevor"))
            (: spouse ())))

    ($define! ? $remote-eval)

    > (? age person)
    27

    > (? postal_code (? address person))
    "10021-3100"

    > (car (? children person))
    "Catherine"

    > (cdr (? children person))
    ("Thomas" "Trevor")

    > (? type (cadr (? phone_numbers person)))
    "office"

    > (? number (car (? phone_numbers person)))
    "212 555-1234"

    > ($define! full_name ($lambda (p) (string-append (? first_name p) " " (? last_name p))))
    > (full_name person)
    "John Smith"

I've not written a Scheme macro since. I've written hundreds of Kernel operatives though.

I was also a typoholic previously, but am in remission now thanks to Kernel.

https://web.cs.wpi.edu/~jshutt/kernel.html

Consider it a bit like a "church encoding" for complex numbers. I'll try to demonstrate with an S-expression representation.

---

A small primer if you're not familiar. S-expressions are basically atoms (symbols/numbers etc), pairs, or null.

    S = 
      | 
      | (S . S)      ;; aka pair
      | ()           ;; aka null
    

    (a b c)          == (a . (b . (c . ()))   ;; a proper list
    (a b . c)        == (a . (b . c))         ;; an improper list
    (#0=(a b c) #0#) == ((a b c) (a b c))     ;; a list with a repeated sublist using a reference

So, we have a function `eml(x, y) and a constant `1`. `x` and `y` are symbols.

Lets say we're going to replace `eml` with an infix operator `.`, and replace the unit 1 with `()`.

    C = 
      | 
      | (C . C)      ;; eml
      | ()           ;; 1

    ($define x (string->symbol "x"))
    ($define y (string->symbol "y"))

    ($define! eml cons)

    (eml x y)
    ;; Output: (x . y)

    ;; e^x

        ($define! exp     ($lambda (x) (eml x ())))
        
        (exp x)
        ;; Output: (x)
        ;; Note: (x) is syntax sugar for (x . ())

    ;; Euler's number `e`

        ($define! c:e     (exp ()))
        
        c:e          
        ;; Output: (())
        ;; Note: (()) is syntax sugar for (() . ())

    ;; exp(1) - ln(x)

        ($define! e1ml    ($lambda (x) (eml () x)))
        
        (e1ml x) 
        ;; Output: (() . x)

    ;; ln(x)

        ($define! ln      ($lambda (x) (e1ml (exp (e1ml x)))))
        
        (ln x)
        ;; Output: (() (() . x))

    ;; Zero

        ($define! c:0      (ln ()))
        
        c:0
        ;; Output: (() (()))

    ;; -infinity

        ($define! c:-inf   (ln 0))
        
        c:-inf
        ;; Output: (() (() () (())))

    ;; -x
        
        ($define! neg      ($lambda (x) (eml c:-inf (exp x))))

        (neg x)
        ;; Output: ((() (() () (()))) x)
        
    ;; +infinity
    
        ($define! c:+inf   (neg c:-inf))
        
        c:+inf
        ;; Output: (#0=(() (() () (()))) #0#)
        
    ;; 1/x
    
        ($define! recip    ($lambda (x) (exp (eml c:-inf x))))
        
        (recip x)
        ;; Output: (((() (() () (()))) . x))
  
    ;; x - y
    
        ($define! sub      ($lambda (x y) (eml (ln x) (exp y))))
    
        (sub x y)
        ;; Output: ((() (() . x)) y)
    
    ;; x + y
    
        ($define! add      ($lambda (x y) (sub x (neg y))))
    
        (add x y)
        ;; Output: ((() (() . x)) ((() (() () (()))) y))
    
    ;; x * y
    
        ($define! mul      ($lambda (x y) (exp (add (ln x) (exp (neg y))))))
        
        (mul x y)
        ;; Output: (((() (() () (() . x))) (#0=(() (() () (()))) ((#0# y)))))
        
    ;; x / y
    
        ($define! div      ($lambda (x y) (exp (sub (ln x) (ln y)))))
        
        (div x y)
        ;; Output: (((() (() () (() . x))) (() (() . y))))
        
    ;; x^y
    
        ($define! pow      ($lambda (x y) (exp (mul x (ln y)))))
  
        (pow x y)
        ;; Output: ((((() (() () (() . x))) (#0=(() (() () (()))) ((#0# (() (() . y))))))))
  

So basically, we have a way of constructing trees based on `eml`

Next, we pattern match. For example, to pattern match over addition, extract the `x` and `y` values, we can use:

    ($define! perform-addition
        ($lambda (add-expr)
            ($let ((((() (() . x)) ((() (() () (()))) y)) add-expr))
                (+ x y))))  

    ;; Note, + is provided by the language to perform addition of complex numbers

    (perform-addition (add 256 512))
    ;; Output: 768

We can simplify the defintion of perform-addition by expanding the parameters of a call to `add` as the arguments to the function:

    ($define! $let-lambda
        ($vau (expr . body) env
            ($let ((params (eval expr env)))
                (wrap (eval (list* $vau (list params) #ignore body) env)))))
                
    ($define! perform-addition
        ($let-lambda (add x y)
            (+ x y)))

    ($define! perform-subtraction
        ($let-lambda (sub x y)
            (- x y)))


    ($define! sub-expr (sub 256 512))
    ;; Output: #inert
    sub-expr
    ;; Output: ((() (() . 256)) 512)

    (perform-subtraction sub-expr)
    ;; Output: -256

Examples are in the Kernel programming language, tested using klisp[1]

[1]:https://github.com/dbohdan/klisp