3 ms·

second, please help us laypeople here

sparkie 7mo ago
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 = <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 --- 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 = <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. 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 https://github.com/dbohdan/klisp

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 = <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 --- 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 = <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. 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 https://github.com/dbohdan/klisp