#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;
C23 has relaxed rules for redefining the same struct, so we can avoid having to create the struct up front. #define Array(T) struct array_##T { size_t len; T *elems; }
Array(int) foo;
Array(int) bar; #define Array(T) struct array_##T { size_t len; T *elems; }
We can use `Array(int)` in multiple places in the same TU - but in C11 or earlier, this is an error. (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.
So when you see: (define (foo)
(expr1)
(expr2)
(expr3))
If we desugar, it would be (define foo (lambda () (begin (expr1) (expr3) (expr3))))
We get behavior that looks just like other procedural languages (without a "return" keyword) - but everything is still an 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))
`foo` is a function, when it is combined with the arguments, it receives the values 5 and 7. ($vau (operands) dynamic-env . body)
Compare to: ($lambda (arguments) . body)
So operatives are called in the same way a function is called - but the operands are not reduced, and the environment is passed implicitly. (eval operands dynamic-env)
But it can chose other evaluation strategies for the operands - such as evaluating them in a custom created environment which we can make with (make-environment) or ($bindings->environment). [#environment]
The environment type is encapsulated, so it doesn't give you very useful debug information. ($define! z 10)
($define! @add-z
($template (x y)
(+ x y z)))
In this template `x` and `y` are bound variables and `+` and `z` are free. The template resolves the free symbols and returns an operative expecting 2 operands, effectively providing an operative with the body: ([#applicative: +] x y 10)
When we call the template with the two operands, it resolves any symbols in the arguments and returns the full expression with no symbols present, but it doesn't evaluate the expression yet. > ($let ((x 9)
(y 7))
(@add-z (* x 3) (- y 13)))
([#applicative: +] ([#applicative: *] 9 3) ([#applicative: -] 7 13) 10)
When we decide to evaluate the expression, no symbol lookup is necessary - it can perform the operation rather quickly, despite the slow interpretation. ($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)))))))
--- true #t
false #f
null ()
[...] (& ...)
"k" : v (: k v)
{...} (@ ...)
Where &, :, @ are defined as: ($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))))
Using the "person" example from the JSON/syntax section on Wikipedia: ($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 ())))
I would then define `?` ($define! ? $remote-eval)
Now we can query the object. > (? 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" S = <symbol>
| <number>
| (S . S) ;; aka pair
| () ;; aka null
There's some syntax sugar for right chains of pairs to form lists: (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
--- C = <symbol>
| <number>
| (C . C) ;; eml
| () ;; 1
We have basically the same context-free structure - we can encode complex numbers as lists. Let's define ourselves a couple of symbols for use in the examples: ($define x (string->symbol "x"))
($define y (string->symbol "y"))
And now we can define the `eml` function as an alias for `cons`. ($define! eml cons)
(eml x y)
;; Output: (x . y)
We can now write a bunch of functions which construct trees, representing the operations they perform. We use only `eml` or previously defined functions to construct each tree: ;; 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))))))))
I'll stop there, but we continue for implementing all the trig, pi, etc using the same approach. ($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
So we didn't need to actually compute any `exp(x)` or `ln(y)` to perform this addition - we just needed to pattern match over the tree, which in this case the language does for us via deconstructing `$let`. ($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
There's a bit more work involved for a full pattern matcher which will take some arbitrary `expr` and perform the relevant computation. I'm still working on that.
The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).