It's potentially useful for computer algebra with complex numbers - we might be able to simplify formulas using non-standard methods, but instead via pattern matching. We might use this to represent
exact numbers internally, and only produce an inexact result when we later reduce the expression.
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
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
---
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
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.
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
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`.
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
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.
Examples are in the Kernel programming language, tested using klisp[1]
[1]:https://github.com/dbohdan/klisp