File: fmscripts/benchmarks_test.go 1 package fmscripts 2 3 import ( 4 "math" 5 "testing" 6 ) 7 8 const ( 9 interferingRipples = "" + 10 "exp(-0.5 * sin(2 * hypot(x - 2, y + 1))) + " + 11 "exp(-0.5 * sin(10 * hypot(x + 2, y - 3.4)))" 12 13 smilingGhost = "" + 14 "log1p(((x - 1)**2 + y*y - 4)*((x + 1)**2 + y*y - 4)*" + 15 "(x*x + (y - sqrt(3))**2 - 4) - 5)" 16 ) 17 18 var benchmarks = []struct { 19 Name string 20 Script string 21 Native func(float64, float64) float64 22 }{ 23 {"Load", "x", func(x, y float64) float64 { return x }}, 24 {"Constant", "4.25", func(x, y float64) float64 { return 4.25 }}, 25 {"Constant Addition", "1+2", func(x, y float64) float64 { return 1 + 2 }}, 26 {"0 Additions", "x", func(x, y float64) float64 { return x }}, 27 {"1 Additions", "x+x", func(x, y float64) float64 { return x + x }}, 28 {"2 Additions", "x+x+x", func(x, y float64) float64 { return x + x + x }}, 29 {"0 Multiplications", "x", func(x, y float64) float64 { return x }}, 30 {"1 Multiplications", "x*x", func(x, y float64) float64 { return x * x }}, 31 {"2 Multiplications", "x*x*x", func(x, y float64) float64 { return x * x * x }}, 32 {"0 Divisions", "x", func(x, y float64) float64 { return x }}, 33 {"1 Divisions", "x/x", func(x, y float64) float64 { return x / x }}, 34 {"2 Divisions", "x/x/x", func(x, y float64) float64 { return x / x / x }}, 35 {"e+pi", "e+pi", func(x, y float64) float64 { return math.E + math.Pi }}, 36 {"1-2", "1-2", func(x, y float64) float64 { return 1 - 2 }}, 37 {"e-pi", "e-pi", func(x, y float64) float64 { return math.E - math.Pi }}, 38 {"Add 0", "x+0", func(x, y float64) float64 { return x + 0 }}, 39 {"x*1", "x*1", func(x, y float64) float64 { return x * 1 }}, 40 {"Abs Func", "abs(-x)", func(x, y float64) float64 { return math.Abs(-x) }}, 41 {"Abs Syntax", "&(-x)", func(x, y float64) float64 { return math.Abs(-x) }}, 42 { 43 "Square (pow)", 44 "pow(x, 2)", 45 func(x, y float64) float64 { return math.Pow(x, 2) }, 46 }, 47 {"Square", "square(x)", func(x, y float64) float64 { return x * x }}, 48 {"Square Syntax", "*x", func(x, y float64) float64 { return x * x }}, 49 { 50 "Linear", 51 "3.4 * x - 0.2", 52 func(x, y float64) float64 { return 3.4*x - 0.2 }, 53 }, 54 {"Direct Square", "x*x", func(x, y float64) float64 { return x * x }}, 55 { 56 "Cube (pow)", 57 "pow(x, 3)", 58 func(x, y float64) float64 { return math.Pow(x, 3) }, 59 }, 60 {"Cube", "cube(x)", func(x, y float64) float64 { return x * x * x }}, 61 {"Direct Cube", "x*x*x", func(x, y float64) float64 { return x * x * x }}, 62 { 63 "Reciprocal (pow)", 64 "pow(x, -1)", 65 func(x, y float64) float64 { return math.Pow(x, -1) }, 66 }, 67 { 68 "Reciprocal Func", 69 "reciprocal(x)", 70 func(x, y float64) float64 { return 1 / x }, 71 }, 72 {"Direct Reciprocal", "1/x", func(x, y float64) float64 { return 1 / x }}, 73 {"Variable Negation", "-x", func(x, y float64) float64 { return -x }}, 74 {"Constant Multip.", "1*2", func(x, y float64) float64 { return 1 * 2 }}, 75 {"e*pi", "e*pi", func(x, y float64) float64 { return math.E * math.Pi }}, 76 { 77 "Variable y = mx + k", 78 "2.1*x + 3.4", 79 func(x, y float64) float64 { return 2.1*x + 3.4 }, 80 }, 81 {"sin(x)", "sin(x)", func(x, y float64) float64 { return math.Sin(x) }}, 82 {"cos(x)", "cos(x)", func(x, y float64) float64 { return math.Cos(x) }}, 83 {"exp(x)", "exp(x)", func(x, y float64) float64 { return math.Exp(x) }}, 84 {"expm1(x)", "expm1(x)", func(x, y float64) float64 { return math.Expm1(x) }}, 85 {"ln(x)", "ln(x)", func(x, y float64) float64 { return math.Log(x) }}, 86 {"log2(x)", "log2(x)", func(x, y float64) float64 { return math.Log2(x) }}, 87 {"log10(x)", "log10(x)", func(x, y float64) float64 { return math.Log10(x) }}, 88 {"1/2", "1/2", func(x, y float64) float64 { return 1.0 / 2.0 }}, 89 {"e/pi", "e/pi", func(x, y float64) float64 { return math.E / math.Pi }}, 90 {"exp(2)", "exp(2)", func(x, y float64) float64 { return math.Exp(2) }}, 91 { 92 "Club Beat Pulse", 93 "sin(10*tau * exp(-20*x)) * exp(-2*x)", 94 func(x, y float64) float64 { 95 return math.Sin(10*2*math.Pi*math.Exp(-20*x)) * math.Exp(-2*x) 96 }, 97 }, 98 { 99 "Interfering Ripples", 100 interferingRipples, 101 func(x, y float64) float64 { 102 return math.Exp(-0.5*math.Sin(2*math.Hypot(x-2, y+1))) + 103 math.Exp(-0.5*math.Sin(10*math.Hypot(x+2, y-3.4))) 104 }, 105 }, 106 { 107 "Floor Lights", 108 "abs(sin(x)) / y**1.4", 109 func(x, y float64) float64 { 110 return math.Abs(math.Sin(x)) / math.Pow(y, 1.4) 111 }, 112 }, 113 { 114 "Domain Hole", 115 "log1p(sin(x + y) + (x - y)**2 - 1.5*x + 2.5*y + 1)", 116 func(x, y float64) float64 { 117 v := x - y 118 return math.Log1p(math.Sin(x+y) + v*v - 1.5*x + 2.5*y + 1) 119 }, 120 }, 121 { 122 "Beta Gradient", 123 "lbeta(x + 5.1, y + 5.1)", 124 func(x, y float64) float64 { return lnBeta(x+5.1, y+5.1) }, 125 }, 126 { 127 "Hot Bars", 128 "abs(x) + sqrt(abs(sin(2*y)))", 129 func(x, y float64) float64 { 130 return math.Abs(x) + math.Sqrt(math.Abs(math.Sin(2*y))) 131 }, 132 }, 133 { 134 "Grid Pattern", 135 "sin(sin(x)+cos(y)) + cos(sin(x*y)+cos(y**2))", 136 func(x, y float64) float64 { 137 return math.Sin(math.Sin(x)+math.Cos(y)) + 138 math.Cos(math.Sin(x*y)+math.Cos(y*y)) 139 }, 140 }, 141 { 142 "Smiling Ghost", 143 smilingGhost, 144 func(x, y float64) float64 { 145 xm1 := x - 1 146 xp1 := x + 1 147 v := y - math.Sqrt(3) 148 w := (xm1*xm1 + y*y - 4) * (xp1*xp1 + y*y - 4) * (x*x + v*v - 4) 149 return math.Log1p(w - 5) 150 }, 151 }, 152 { 153 "Forgot its Name", 154 "1 / (1 + x.abs/y*y)", 155 func(x, y float64) float64 { 156 return 1 / (1 + math.Abs(x)/y*y) 157 }, 158 }, 159 } 160 161 func BenchmarkEmpty(b *testing.B) { 162 b.Run("empty program", func(b *testing.B) { 163 var p Program 164 b.ReportAllocs() 165 b.ResetTimer() 166 167 for i := 0; i < b.N; i++ { 168 _ = p.Run() 169 } 170 }) 171 172 f := func(float64, float64) float64 { 173 return math.NaN() 174 } 175 176 b.Run("empty function", func(b *testing.B) { 177 b.ReportAllocs() 178 b.ResetTimer() 179 180 for i := 0; i < b.N; i++ { 181 _ = f(0, 0) 182 } 183 }) 184 } 185 186 func BenchmarkBasicProgram(b *testing.B) { 187 for _, tc := range benchmarks { 188 var c Compiler 189 defs := map[string]any{ 190 "x": 0.05, 191 "y": 0, 192 "z": 0, 193 } 194 195 b.Run(tc.Name, func(b *testing.B) { 196 p, err := c.Compile(tc.Script, defs) 197 if err != nil { 198 const fs = "while compiling %q, got error %q" 199 b.Fatalf(fs, tc.Script, err.Error()) 200 return 201 } 202 203 x, _ := p.Get("x") 204 _, _ = p.Get("y") 205 _, _ = p.Get("z") 206 207 b.ResetTimer() 208 for i := 0; i < b.N; i++ { 209 _ = p.Run() 210 *x++ 211 } 212 }) 213 } 214 } 215 216 func BenchmarkBasicFunc(b *testing.B) { 217 for _, tc := range benchmarks { 218 b.Run(tc.Name, func(b *testing.B) { 219 x := 0.05 220 y := 0.0 221 fn := tc.Native 222 b.ResetTimer() 223 224 for i := 0; i < b.N; i++ { 225 fn(x, y) 226 x++ 227 y++ 228 } 229 }) 230 } 231 } 232 233 func BenchmarkSoundProgram(b *testing.B) { 234 var soundBenchmarkTests = []struct { 235 Name string 236 Script string 237 }{ 238 { 239 "Sine Wave", 240 "sin(1000 * tau * x)", 241 }, 242 { 243 "Laser Pulse", 244 "sin(100 * tau * exp(-40 * u))", 245 }, 246 { 247 "Club Beat Pulse", 248 "sin(10 * tau * exp(-20 * x)) * exp(-2 * x)", 249 }, 250 } 251 252 for _, tc := range soundBenchmarkTests { 253 var c Compiler 254 defs := map[string]any{ 255 "t": 0.05, 256 "u": 0, 257 } 258 259 const seconds = 2 260 const sampleRate = 48_000 261 dt := 1.0 / float64(sampleRate) 262 // buf is the destination buffer for all calculated samples 263 buf := make([]float64, 0, seconds*sampleRate) 264 265 b.Run(tc.Name, func(b *testing.B) { 266 p, err := c.Compile(tc.Script, defs) 267 if err != nil { 268 const fs = "while compiling %q, got error %q" 269 b.Fatalf(fs, tc.Script, err.Error()) 270 return 271 } 272 273 // input parameters for the program 274 t, _ := p.Get("t") 275 u, _ := p.Get("u") 276 277 b.ResetTimer() 278 for i := 0; i < b.N; i++ { 279 // avoid buffer expansions after the first run 280 buf = buf[:0] 281 282 // benchmark 1 second of generated sound 283 for j := 0; j < seconds*sampleRate; j++ { 284 // calculate time in seconds from current sample index 285 v := float64(j) * dt 286 *t = v 287 _, *u = math.Modf(v) 288 289 // calculate a mono sample 290 buf = append(buf, p.Run()) 291 } 292 } 293 }) 294 } 295 } 296 297 func BenchmarkNativeSoundProgram(b *testing.B) { 298 const tau = 2 * math.Pi 299 300 var soundBenchmarkTests = []struct { 301 Name string 302 Fun func(float64, float64) float64 303 }{ 304 { 305 "Sine Wave", 306 func(t, u float64) float64 { 307 return math.Sin(1000 * tau * t) 308 }, 309 }, 310 { 311 "Laser Pulse", 312 func(t, u float64) float64 { 313 return math.Sin(100 * tau * math.Exp(-40*u)) 314 }, 315 }, 316 { 317 "Club Beat Pulse", 318 func(t, u float64) float64 { 319 return math.Sin(10*tau*math.Exp(-20*t)) * math.Exp(-2*t) 320 }, 321 }, 322 } 323 324 for _, tc := range soundBenchmarkTests { 325 const seconds = 2 326 const sampleRate = 48_000 327 dt := 1.0 / float64(sampleRate) 328 // buf is the destination buffer for all calculated samples 329 buf := make([]float64, 0, seconds*sampleRate) 330 331 b.Run(tc.Name, func(b *testing.B) { 332 // input parameters for the program 333 t := 0.05 334 u := 0.00 335 fn := tc.Fun 336 b.ResetTimer() 337 338 for i := 0; i < b.N; i++ { 339 // avoid buffer expansions after the first run 340 buf = buf[:0] 341 342 // benchmark 1 second of generated sound 343 for j := 0; j < seconds*sampleRate; j++ { 344 // calculate time in seconds from current sample index 345 v := float64(j) * dt 346 t = v 347 _, u = math.Modf(v) 348 349 // calculate a mono sample 350 buf = append(buf, fn(t, u)) 351 } 352 } 353 }) 354 } 355 } 356 357 func BenchmarkImageProgram(b *testing.B) { 358 const ( 359 // use part of a full HD pic to give more runs for each test, giving 360 // greater statistical-stability/comparability across benchmark runs 361 w = 1920 / 4 362 h = 1080 / 4 363 364 intRipples = "" + 365 "exp(-0.5 * sin(2 * hypot(x - 2, y + 1))) + " + 366 "exp(-0.5 * sin(10 * hypot(x + 2, y - 3.4)))" 367 domainHole = "" + 368 "log1p(sin(x + y) + pow(x - y, 2) - 1.5*x + 2.5*y + 1)" 369 gridPatPow = "" + 370 "sin(sin(x)+cos(y)) + cos(sin(x*y)+cos(pow(y, 2)))" 371 gridPatSquare = "" + 372 "sin(sin(x)+cos(y)) + cos(sin(x*y)+cos(square(y)))" 373 smilingGhostFunc = "" + 374 "log1p((pow(x - 1, 2) + y*y - 4)*" + 375 "(pow(x + 1, 2) + y*y - 4)*" + 376 "(x*x + pow(y - sqrt(3), 2) - 4) - 5)" 377 smilingGhostSyntax = "" + 378 "log1p((*(x - 1) + *y - 4)*" + 379 "(*(x + 1) + *y - 4)*" + 380 "(*x + *(y - sqrt(3)) - 4) - 5)" 381 ) 382 383 var imageBenchmarkTests = []struct { 384 Name string 385 Width int 386 Height int 387 Script string 388 }{ 389 {"Horizontal Linear", w, h, "x"}, 390 {"Multiplication", w, h, "x*y"}, 391 {"Star", w, h, "exp(-0.5 * hypot(x, y))"}, 392 {"Interfering Ripples", w, h, intRipples}, 393 {"Floor Lights", w, h, "abs(sin(x)) / pow(y, 1.4)"}, 394 {"Domain Hole", w, h, domainHole}, 395 {"Beta Gradient", w, h, "lbeta(x + 5.1, y + 5.1)"}, 396 {"Hot Bars", w, h, "abs(x) + sqrt(abs(sin(2*y)))"}, 397 {"Grid Pattern (pow)", w, h, gridPatPow}, 398 {"Grid Pattern (square)", w, h, gridPatSquare}, 399 {"Smiling Ghost (pow)", w, h, smilingGhostFunc}, 400 {"Smiling Ghost (square syntax)", w, h, smilingGhostSyntax}, 401 } 402 403 for _, tc := range imageBenchmarkTests { 404 var c Compiler 405 defs := map[string]any{ 406 "x": 0, 407 "y": 0, 408 } 409 410 // 4k-resolution results buffer 411 buf := make([]float64, 1920*1080*4) 412 413 b.Run(tc.Name, func(b *testing.B) { 414 p, err := c.Compile(tc.Script, defs) 415 if err != nil { 416 const fs = "while compiling %q, got error %q" 417 b.Fatalf(fs, tc.Script, err.Error()) 418 return 419 } 420 421 // input parameters for the program 422 x, _ := p.Get("x") 423 y, _ := p.Get("y") 424 425 w := tc.Width 426 h := tc.Height 427 dx := 1.0 / float64(w) 428 dy := 1.0 / float64(h) 429 xmin := -5.2 430 ymax := 23.91 431 b.ResetTimer() 432 for i := 0; i < b.N; i++ { 433 // avoid buffer expansions after the first run 434 buf = buf[:0] 435 436 for j := 0; j < h; j++ { 437 *y = ymax - float64(j)*dy 438 for i := 0; i < w; i++ { 439 *x = float64(i)*dx + xmin 440 buf = append(buf, p.Run()) 441 } 442 } 443 } 444 }) 445 } 446 } 447 448 func BenchmarkCompiler(b *testing.B) { 449 f := func(name string, src string) { 450 b.Run(name, func(b *testing.B) { 451 for i := 0; i < b.N; i++ { 452 var c Compiler 453 _, err := c.Compile(src, map[string]any{ 454 "x": 0.05, 455 "y": 0, 456 "z": 0, 457 }) 458 459 if err != nil { 460 const fs = "while compiling %q, got error %q" 461 b.Fatalf(fs, src, err.Error()) 462 } 463 } 464 }) 465 } 466 467 for _, tc := range mathCorrectnessTests { 468 f(tc.Name, tc.Script) 469 } 470 471 for _, tc := range benchmarks { 472 f(tc.Name, tc.Script) 473 } 474 } File: fmscripts/compilers.go 1 package fmscripts 2 3 import ( 4 "fmt" 5 "math" 6 "strconv" 7 ) 8 9 // unary2op turns unary operators into their corresponding basic operations; 10 // some entries are only for the optimizer, and aren't accessible directly 11 // from valid source code 12 var unary2op = map[string]opcode{ 13 "-": neg, 14 "!": not, 15 "&": abs, 16 "*": square, 17 "^": square, 18 "/": rec, 19 "%": mod1, 20 } 21 22 // binary2op turns binary operators into their corresponding basic operations 23 var binary2op = map[string]opcode{ 24 "+": add, 25 "-": sub, 26 "*": mul, 27 "/": div, 28 "%": mod, 29 "&&": and, 30 "&": and, 31 "||": or, 32 "|": or, 33 "==": equal, 34 "!=": notequal, 35 "<>": notequal, 36 "<": less, 37 "<=": lessoreq, 38 ">": more, 39 ">=": moreoreq, 40 "**": pow, 41 "^": pow, 42 } 43 44 // Compiler lets you create Program objects, which you can then run. The whole 45 // point of this is to create quicker-to-run numeric scripts. You can even add 46 // variables with initial values, as well as functions for the script to use. 47 // 48 // Common math funcs and constants are automatically detected, and constant 49 // results are optimized away, unless builtins are redefined. In other words, 50 // the optimizer is effectively disabled for all (sub)expressions containing 51 // redefined built-ins, as there's no way to be sure those values won't change 52 // from one run to the next. 53 // 54 // See the comment for type Program for more details. 55 // 56 // # Example 57 // 58 // var c fmscripts.Compiler 59 // 60 // defs := map[string]any{ 61 // "x": 0, // define `x`, and initialize it to 0 62 // "k": 4.25, // define `k`, and initialize it to 4.25 63 // "b": true, // define `b`, and initialize it to 1.0 64 // "n": -23, // define `n`, and initialize it to -23.0 65 // "pi": 3, // define `pi`, overriding the default constant named `pi` 66 // 67 // "f": numericKernel // type is func ([]float64) float64 68 // "g": otherFunc // type is func (float64) float64 69 // } 70 // 71 // prog, err := c.Compile("log10(k) + f(sqrt(k) * exp(-x), 45, -0.23)", defs) 72 // // ... 73 // 74 // x, _ := prog.Get("x") // Get returns (*float64, bool) 75 // y, _ := prog.Get("y") // a useless pointer, since program doesn't use `y` 76 // // ... 77 // 78 // for i := 0; i < n; i++ { 79 // *x = float64(i)*dx + minx // you update inputs in place using pointers 80 // f := prog.Run() // method Run gives you a float64 back 81 // // ... 82 // } 83 type Compiler struct { 84 maxStack int // the exact stack size the resulting program needs 85 ops []numOp // the program's operations 86 87 vaddr map[string]int // address lookup for values 88 faddr map[string]int // address lookup for functions 89 ftype map[string]any // keeps track of func types during compilation 90 91 values []float64 // variables and constants available to programs 92 funcs []any // funcs available to programs 93 } 94 95 // Compile parses the script given and generates a fast float64-only Program 96 // made only of sequential steps: any custom funcs you provide it can use 97 // their own internal looping and/or conditional logic, of course. 98 func (c *Compiler) Compile(src string, defs map[string]any) (Program, error) { 99 // turn source code into an abstract syntax-tree 100 root, err := parse(src) 101 if err != nil { 102 return Program{}, err 103 } 104 105 // generate operations 106 if err := c.reset(defs); err != nil { 107 return Program{}, err 108 } 109 if err = c.compile(root, 0); err != nil { 110 return Program{}, err 111 } 112 113 // create the resulting program 114 var p Program 115 p.stack = make([]float64, c.maxStack) 116 p.values = make([]float64, len(c.values)) 117 copy(p.values, c.values) 118 p.ops = make([]numOp, len(c.ops)) 119 copy(p.ops, c.ops) 120 p.funcs = make([]any, len(c.ftype)) 121 copy(p.funcs, c.funcs) 122 p.names = make(map[string]int, len(c.vaddr)) 123 124 // give the program's Get method access only to all allocated variables 125 for k, v := range c.vaddr { 126 // avoid exposing numeric constants on the program's name-lookup 127 // table, which would allow users to change literals across runs 128 if _, err := strconv.ParseFloat(k, 64); err == nil { 129 continue 130 } 131 // expose only actual variable names 132 p.names[k] = v 133 } 134 135 return p, nil 136 } 137 138 // reset prepares a compiler by satisfying internal preconditions func 139 // compileExpr relies on, when given an abstract syntax-tree 140 func (c *Compiler) reset(defs map[string]any) error { 141 // reset the compiler's internal state 142 c.maxStack = 0 143 c.ops = c.ops[:0] 144 c.vaddr = make(map[string]int) 145 c.faddr = make(map[string]int) 146 c.ftype = make(map[string]any) 147 c.values = c.values[:0] 148 c.funcs = c.funcs[:0] 149 150 // allocate vars and funcs 151 for k, v := range defs { 152 if err := c.allocEntry(k, v); err != nil { 153 return err 154 } 155 } 156 return nil 157 } 158 159 // allocEntry simplifies the control-flow of func reset 160 func (c *Compiler) allocEntry(k string, v any) error { 161 const ( 162 maxExactRound = 2 << 52 163 rangeErrFmt = "%d is outside range of exact float64 integers" 164 typeErrFmt = "got value of unsupported type %T" 165 ) 166 167 switch v := v.(type) { 168 case float64: 169 _, err := c.allocValue(k, v) 170 return err 171 172 case int: 173 if math.Abs(float64(v)) > maxExactRound { 174 return fmt.Errorf(rangeErrFmt, v) 175 } 176 _, err := c.allocValue(k, float64(v)) 177 return err 178 179 case bool: 180 _, err := c.allocValue(k, debool(v)) 181 return err 182 183 default: 184 if isSupportedFunc(v) { 185 c.ftype[k] = v 186 _, err := c.allocFunc(k, v) 187 return err 188 } 189 return fmt.Errorf(typeErrFmt, v) 190 } 191 } 192 193 // allocValue ensures there's a place to match the name given, returning its 194 // index when successful; only programs using unreasonably many values will 195 // cause this func to fail 196 func (c *Compiler) allocValue(s string, f float64) (int, error) { 197 if len(c.values) >= maxOpIndex { 198 const fs = "programs can only use up to %d distinct float64 values" 199 return -1, fmt.Errorf(fs, maxOpIndex+1) 200 } 201 202 i := len(c.values) 203 c.vaddr[s] = i 204 c.values = append(c.values, f) 205 return i, nil 206 } 207 208 // valueIndex returns the index reserved for an allocated value/variable: 209 // all unallocated values/variables are allocated here on first access 210 func (c *Compiler) valueIndex(s string, f float64) (int, error) { 211 // name is found: return the index of the already-allocated var 212 if i, ok := c.vaddr[s]; ok { 213 return i, nil 214 } 215 216 // name not found, but it's a known math constant 217 if f, ok := mathConst[s]; ok { 218 return c.allocValue(s, f) 219 } 220 // name not found, and it's not of a known math constant 221 return c.allocValue(s, f) 222 } 223 224 // constIndex allocates a constant as a variable named as its own string 225 // representation, which avoids multiple entries for repeated uses of the 226 // same constant value 227 func (c *Compiler) constIndex(f float64) (int, error) { 228 // constants have no name, so use a canonical string representation 229 return c.valueIndex(strconv.FormatFloat(f, 'f', 16, 64), f) 230 } 231 232 // funcIndex returns the index reserved for an allocated function: all 233 // unallocated functions are allocated here on first access 234 func (c *Compiler) funcIndex(name string) (int, error) { 235 // check if func was already allocated 236 if i, ok := c.faddr[name]; ok { 237 return i, nil 238 } 239 240 // if name is reserved allocate an index for its matching func 241 if fn, ok := c.ftype[name]; ok { 242 return c.allocFunc(name, fn) 243 } 244 245 // if name wasn't reserved, see if it's a standard math func name 246 if fn := c.autoFuncLookup(name); fn != nil { 247 return c.allocFunc(name, fn) 248 } 249 250 // name isn't even a standard math func's 251 return -1, fmt.Errorf("function not found") 252 } 253 254 // allocFunc ensures there's a place for the function name given, returning its 255 // index when successful; only funcs of unsupported types will cause failure 256 func (c *Compiler) allocFunc(name string, fn any) (int, error) { 257 if isSupportedFunc(fn) { 258 i := len(c.funcs) 259 c.faddr[name] = i 260 c.ftype[name] = fn 261 c.funcs = append(c.funcs, fn) 262 return i, nil 263 } 264 return -1, fmt.Errorf("can't use a %T as a number-crunching function", fn) 265 } 266 267 // autoFuncLookup checks built-in deterministic funcs for the name given: its 268 // result is nil only if there's no match 269 func (c *Compiler) autoFuncLookup(name string) any { 270 if fn, ok := determFuncs[name]; ok { 271 return fn 272 } 273 return nil 274 } 275 276 // genOp generates/adds a basic operation to the program, while keeping track 277 // of the maximum depth the stack can reach 278 func (c *Compiler) genOp(op numOp, depth int) { 279 // add 2 defensively to ensure stack space for the inputs of binary ops 280 n := depth + 2 281 if c.maxStack < n { 282 c.maxStack = n 283 } 284 c.ops = append(c.ops, op) 285 } 286 287 // compile is a recursive expression evaluator which does the actual compiling 288 // as it goes along 289 func (c *Compiler) compile(expr any, depth int) error { 290 expr = c.optimize(expr) 291 292 switch expr := expr.(type) { 293 case float64: 294 return c.compileLiteral(expr, depth) 295 case string: 296 return c.compileVariable(expr, depth) 297 case []any: 298 return c.compileCombo(expr, depth) 299 case unaryExpr: 300 return c.compileUnary(expr.op, expr.x, depth) 301 case binaryExpr: 302 return c.compileBinary(expr.op, expr.x, expr.y, depth) 303 case callExpr: 304 return c.compileCall(expr, depth) 305 case assignExpr: 306 return c.compileAssign(expr, depth) 307 default: 308 return fmt.Errorf("unsupported expression type %T", expr) 309 } 310 } 311 312 // compileLiteral generates a load operation for the constant value given 313 func (c *Compiler) compileLiteral(f float64, depth int) error { 314 i, err := c.constIndex(f) 315 if err != nil { 316 return err 317 } 318 c.genOp(numOp{What: load, Index: opindex(i)}, depth) 319 return nil 320 } 321 322 // compileVariable generates a load operation for the variable name given 323 func (c *Compiler) compileVariable(name string, depth int) error { 324 // handle names which aren't defined, but are known math constants 325 if _, ok := c.vaddr[name]; !ok { 326 if f, ok := mathConst[name]; ok { 327 return c.compileLiteral(f, depth) 328 } 329 } 330 331 // handle actual variables 332 i, err := c.valueIndex(name, 0) 333 if err != nil { 334 return err 335 } 336 c.genOp(numOp{What: load, Index: opindex(i)}, depth) 337 return nil 338 } 339 340 // compileCombo handles a sequence of expressions 341 func (c *Compiler) compileCombo(exprs []any, depth int) error { 342 for _, v := range exprs { 343 err := c.compile(v, depth) 344 if err != nil { 345 return err 346 } 347 } 348 return nil 349 } 350 351 // compileUnary handles unary expressions 352 func (c *Compiler) compileUnary(op string, x any, depth int) error { 353 err := c.compile(x, depth+1) 354 if err != nil { 355 return err 356 } 357 358 if op, ok := unary2op[op]; ok { 359 c.genOp(numOp{What: op}, depth) 360 return nil 361 } 362 return fmt.Errorf("unary operation %q is unsupported", op) 363 } 364 365 // compileBinary handles binary expressions 366 func (c *Compiler) compileBinary(op string, x, y any, depth int) error { 367 switch op { 368 case "===", "!==": 369 // handle binary expressions with no matching basic operation, by 370 // treating them as aliases for function calls 371 return c.compileCall(callExpr{name: op, args: []any{x, y}}, depth) 372 } 373 374 err := c.compile(x, depth+1) 375 if err != nil { 376 return err 377 } 378 err = c.compile(y, depth+2) 379 if err != nil { 380 return err 381 } 382 383 if op, ok := binary2op[op]; ok { 384 c.genOp(numOp{What: op}, depth) 385 return nil 386 } 387 return fmt.Errorf("binary operation %q is unsupported", op) 388 } 389 390 // compileCall handles function-call expressions 391 func (c *Compiler) compileCall(expr callExpr, depth int) error { 392 // lookup function name 393 index, err := c.funcIndex(expr.name) 394 if err != nil { 395 return fmt.Errorf("%s: %s", expr.name, err.Error()) 396 } 397 // get the func value, as its type determines the calling op to emit 398 v, ok := c.ftype[expr.name] 399 if !ok { 400 return fmt.Errorf("%s: function is undefined", expr.name) 401 } 402 403 // figure which type of function operation to use 404 op, ok := func2op(v) 405 if !ok { 406 return fmt.Errorf("%s: unsupported function type %T", expr.name, v) 407 } 408 409 // ensure number of args given to the func makes sense for the func type 410 err = checkArgCount(func2info[op], expr.name, len(expr.args)) 411 if err != nil { 412 return err 413 } 414 415 // generate operations to evaluate all args 416 for i, v := range expr.args { 417 err := c.compile(v, depth+i+1) 418 if err != nil { 419 return err 420 } 421 } 422 423 // generate func-call operation 424 given := len(expr.args) 425 next := numOp{What: op, NumArgs: opargs(given), Index: opindex(index)} 426 c.genOp(next, depth) 427 return nil 428 } 429 430 // checkArgCount does what it says, returning informative errors when arg 431 // counts are wrong 432 func checkArgCount(info funcTypeInfo, name string, nargs int) error { 433 if info.AtLeast < 0 && info.AtMost < 0 { 434 return nil 435 } 436 437 if info.AtLeast == info.AtMost && nargs != info.AtMost { 438 const fs = "%s: expected %d args, got %d instead" 439 return fmt.Errorf(fs, name, info.AtMost, nargs) 440 } 441 442 if info.AtLeast >= 0 && info.AtMost >= 0 { 443 const fs = "%s: expected between %d and %d args, got %d instead" 444 if nargs < info.AtLeast || nargs > info.AtMost { 445 return fmt.Errorf(fs, name, info.AtLeast, info.AtMost, nargs) 446 } 447 } 448 449 if info.AtLeast >= 0 && nargs < info.AtLeast { 450 const fs = "%s: expected at least %d args, got %d instead" 451 return fmt.Errorf(fs, name, info.AtLeast, nargs) 452 } 453 454 if info.AtMost >= 0 && nargs > info.AtMost { 455 const fs = "%s: expected at most %d args, got %d instead" 456 return fmt.Errorf(fs, name, info.AtMost, nargs) 457 } 458 459 // all is good 460 return nil 461 } 462 463 // compileAssign generates a store operation for the expression given 464 func (c *Compiler) compileAssign(expr assignExpr, depth int) error { 465 err := c.compile(expr.expr, depth) 466 if err != nil { 467 return err 468 } 469 470 i, err := c.allocValue(expr.name, 0) 471 if err != nil { 472 return err 473 } 474 475 c.genOp(numOp{What: store, Index: opindex(i)}, depth) 476 return nil 477 } 478 479 // func sameFunc(x, y any) bool { 480 // if x == nil || y == nil { 481 // return false 482 // } 483 // return reflect.ValueOf(x).Pointer() == reflect.ValueOf(y).Pointer() 484 // } 485 486 // isSupportedFunc checks if a value's type is a supported func type 487 func isSupportedFunc(fn any) bool { 488 _, ok := func2op(fn) 489 return ok 490 } 491 492 // funcTypeInfo is an entry in the func2info lookup table 493 type funcTypeInfo struct { 494 // AtLeast is the minimum number of inputs the func requires: negative 495 // values are meant to be ignored 496 AtLeast int 497 498 // AtMost is the maximum number of inputs the func requires: negative 499 // values are meant to be ignored 500 AtMost int 501 } 502 503 // func2info is a lookup table to check the number of inputs funcs are given 504 var func2info = map[opcode]funcTypeInfo{ 505 call0: {AtLeast: +0, AtMost: +0}, 506 call1: {AtLeast: +1, AtMost: +1}, 507 call2: {AtLeast: +2, AtMost: +2}, 508 call3: {AtLeast: +3, AtMost: +3}, 509 call4: {AtLeast: +4, AtMost: +4}, 510 call5: {AtLeast: +5, AtMost: +5}, 511 callv: {AtLeast: -1, AtMost: -1}, 512 call1v: {AtLeast: +1, AtMost: -1}, 513 } 514 515 // func2op tries to match a func type into a corresponding opcode 516 func func2op(v any) (op opcode, ok bool) { 517 switch v.(type) { 518 case func() float64: 519 return call0, true 520 case func(float64) float64: 521 return call1, true 522 case func(float64, float64) float64: 523 return call2, true 524 case func(float64, float64, float64) float64: 525 return call3, true 526 case func(float64, float64, float64, float64) float64: 527 return call4, true 528 case func(float64, float64, float64, float64, float64) float64: 529 return call5, true 530 case func(...float64) float64: 531 return callv, true 532 case func(float64, ...float64) float64: 533 return call1v, true 534 default: 535 return 0, false 536 } 537 } File: fmscripts/compilers_test.go 1 package fmscripts 2 3 import ( 4 "testing" 5 ) 6 7 func TestBuiltinFuncs(t *testing.T) { 8 list := []map[string]any{ 9 determFuncs, 10 } 11 12 for _, kv := range list { 13 for k, v := range kv { 14 t.Run(k, func(t *testing.T) { 15 if !isSupportedFunc(v) { 16 t.Fatalf("%s: invalid function type %T", k, v) 17 } 18 }) 19 } 20 } 21 } 22 23 var mathCorrectnessTests = []struct { 24 Name string 25 Script string 26 Expected float64 27 Error string 28 }{ 29 { 30 Name: "value", 31 Script: "-45.2", 32 Expected: -45.2, 33 Error: "", 34 }, 35 { 36 Name: "simple", 37 Script: "1 + 3", 38 Expected: 4, 39 Error: "", 40 }, 41 { 42 Name: "fancier", 43 Script: "1*8 + 3*2**3", 44 Expected: 32, 45 Error: "", 46 }, 47 { 48 Name: "function call", 49 Script: "log2(1024)", 50 Expected: 10, 51 Error: "", 52 }, 53 { 54 Name: "function call (2 args)", 55 Script: "pow(3, 3)", 56 Expected: 27, 57 Error: "", 58 }, 59 { 60 Name: "function call (3 args)", 61 Script: "fma(3.5, 56, -1.52)", 62 Expected: 194.48, 63 Error: "", 64 }, 65 { 66 Name: "vararg-function call", 67 Script: "min(log10(10_000), log10(1_000_000), log2(4_096), 100 - 130)", 68 Expected: -30, 69 Error: "", 70 }, 71 { 72 Name: "square shortcut", 73 Script: "*-3", 74 Expected: 9, 75 Error: "", 76 }, 77 { 78 Name: "abs shortcut", 79 Script: "&-3", 80 Expected: 3, 81 Error: "", 82 }, 83 { 84 Name: "negative constant", 85 Script: "(-3)", 86 Expected: -3, 87 Error: "", 88 }, 89 { 90 Name: "power syntax", 91 Script: "2**4", 92 Expected: 16, 93 Error: "", 94 }, 95 { 96 Name: "power syntax order", 97 Script: "3*2**4", 98 Expected: 48, 99 Error: "", 100 }, 101 { 102 Script: "2*3**4", 103 Expected: 162, 104 Error: "", 105 }, 106 { 107 Script: "2**3*4", 108 Expected: 32, 109 Error: "", 110 }, 111 { 112 Script: "(2*3)**4", 113 Expected: 1_296, 114 Error: "", 115 }, 116 { 117 Script: "*2*2", 118 Expected: 8, 119 Error: "", 120 }, 121 { 122 Script: "2*2*2", 123 Expected: 8, 124 Error: "", 125 }, 126 { 127 Script: "3 == 3 ? 10 : -1", 128 Expected: 10, 129 Error: "", 130 }, 131 { 132 Script: "3 == 4 ? 10 : -1", 133 Expected: -1, 134 Error: "", 135 }, 136 { 137 Script: "log10(-1) ?? 4", 138 Expected: 4, 139 Error: "", 140 }, 141 { 142 Script: "log10(10) ?? 4", 143 Expected: 1, 144 Error: "", 145 }, 146 { 147 Script: "abc = 123; abc", 148 Expected: 123, 149 Error: "", 150 }, 151 { 152 Name: "calling func(float64, ...float64) float64", 153 Script: "horner(2.5, 1, 2, 3)", 154 Expected: 14.25, 155 Error: "", 156 }, 157 } 158 159 func TestCompiler(t *testing.T) { 160 for _, tc := range mathCorrectnessTests { 161 name := tc.Name 162 if len(name) == 0 { 163 name = tc.Script 164 } 165 166 t.Run(name, func(t *testing.T) { 167 var c Compiler 168 p, err := c.Compile(tc.Script, map[string]any{"x": 1}) 169 if err != nil { 170 t.Fatalf("got compiler error %q", err.Error()) 171 } 172 173 f := p.Run() 174 if (err != nil || tc.Error != "") && err.Error() != tc.Error { 175 const fs = "expected error %q, got error %q instead" 176 t.Fatalf(fs, err.Error(), tc.Error) 177 } 178 179 if f != tc.Expected { 180 const fs = "expected result to be %f, got %f instead" 181 t.Fatalf(fs, tc.Expected, f) 182 } 183 }) 184 } 185 } File: fmscripts/doc.go 1 /* 2 # Floating-point Math Scripts 3 4 This self-contained package gives you a compiler/interpreter combo to run 5 number-crunching scripts. These are limited to float64 values, but they run 6 surprisingly quickly: various simple benchmarks suggest it's between 1/2 and 7 1/4 the speed of native funcs. 8 9 There are several built-in numeric functions, and the compiler makes it easy 10 to add your custom Go functions to further speed-up any operations specific to 11 your app/domain. 12 13 Finally, notice how float64 data don't really limit you as much as you might 14 think at first, since they can act as booleans (treating 0 as false, and non-0 15 as true), or as exact integers in the extremely-wide range [-2**53, +2**53]. 16 */ 17 package fmscripts File: fmscripts/go.mod 1 module fmscripts 2 3 go 1.18 File: fmscripts/math.go 1 package fmscripts 2 3 import ( 4 "math" 5 ) 6 7 const ( 8 // the maximum integer a float64 can represent exactly; -maxflint is the 9 // minimum such integer, since floating-point values allow such symmetries 10 maxflint = 2 << 52 11 12 // base-2 versions of size multipliers 13 kilobyte = 1024 * 1.0 14 megabyte = 1024 * kilobyte 15 gigabyte = 1024 * megabyte 16 terabyte = 1024 * gigabyte 17 petabyte = 1024 * terabyte 18 19 // unit-conversion multipliers 20 mi2kmMult = 1 / 0.6213712 21 nm2kmMult = 1.852 22 nmi2kmMult = 1.852 23 yd2mtMult = 1 / 1.093613 24 ft2mtMult = 1 / 3.28084 25 in2cmMult = 2.54 26 lb2kgMult = 0.4535924 27 ga2ltMult = 1 / 0.2199692 28 gal2lMult = 1 / 0.2199692 29 oz2mlMult = 29.5735295625 30 cup2lMult = 0.2365882365 31 mpg2kplMult = 0.2199692 / 0.6213712 32 ton2kgMult = 1 / 907.18474 33 psi2paMult = 1 / 0.00014503773800722 34 deg2radMult = math.Pi / 180 35 rad2degMult = 180 / math.Pi 36 ) 37 38 // default math constants 39 var mathConst = map[string]float64{ 40 "e": math.E, 41 "pi": math.Pi, 42 "tau": 2 * math.Pi, 43 "phi": math.Phi, 44 "nan": math.NaN(), 45 "inf": math.Inf(+1), 46 47 "minint": -float64(maxflint - 1), 48 "maxint": +float64(maxflint - 1), 49 "minsafeint": -float64(maxflint - 1), 50 "maxsafeint": +float64(maxflint - 1), 51 52 "false": 0.0, 53 "true": 1.0, 54 "f": 0.0, 55 "t": 1.0, 56 57 // conveniently-named multipliers 58 "femto": 1e-15, 59 "pico": 1e-12, 60 "nano": 1e-09, 61 "micro": 1e-06, 62 "milli": 1e-03, 63 "kilo": 1e+03, 64 "mega": 1e+06, 65 "giga": 1e+09, 66 "tera": 1e+12, 67 "peta": 1e+15, 68 69 // unit-conversion multipliers 70 "mi2km": mi2kmMult, 71 "nm2km": nm2kmMult, 72 "nmi2km": nmi2kmMult, 73 "yd2mt": yd2mtMult, 74 "ft2mt": ft2mtMult, 75 "in2cm": in2cmMult, 76 "lb2kg": lb2kgMult, 77 "ga2lt": ga2ltMult, 78 "gal2l": gal2lMult, 79 "oz2ml": oz2mlMult, 80 "cup2l": cup2lMult, 81 "mpg2kpl": mpg2kplMult, 82 "ton2kg": ton2kgMult, 83 "psi2pa": psi2paMult, 84 "deg2rad": deg2radMult, 85 "rad2deg": rad2degMult, 86 87 // base-2 versions of size multipliers 88 "kb": kilobyte, 89 "mb": megabyte, 90 "gb": gigabyte, 91 "tb": terabyte, 92 "pb": petabyte, 93 "binkilo": kilobyte, 94 "binmega": megabyte, 95 "bingiga": gigabyte, 96 "bintera": terabyte, 97 "binpeta": petabyte, 98 99 // physical constants 100 "c": 299_792_458, // speed of light in m/s 101 "g": 6.67430e-11, // gravitational constant in N m2/kg2 102 "h": 6.62607015e-34, // planck constant in J s 103 "ec": 1.602176634e-19, // elementary charge in C 104 "e0": 8.8541878128e-12, // vacuum permittivity in C2/(Nm2) 105 "mu0": 1.25663706212e-6, // vacuum permeability in T m/A 106 "k": 1.380649e-23, // boltzmann constant in J/K 107 "mu": 1.66053906660e-27, // atomic mass constant in kg 108 "me": 9.1093837015e-31, // electron mass in kg 109 "mp": 1.67262192369e-27, // proton mass in kg 110 "mn": 1.67492749804e-27, // neutron mass in kg 111 112 // float64s can only vaguely approx. avogadro's mole (6.02214076e23) 113 } 114 115 // deterministic math functions lookup-table generated using the command 116 // 117 // go doc math | awk '/func/ { gsub(/func |\(.*/, ""); printf("\"%s\": math.%s,\n", tolower($0), $0) }' 118 // 119 // then hand-edited to remove funcs, or to use adapter funcs when needed: removed 120 // funcs either had multiple returns (like SinCos) or dealt with float32 values 121 var determFuncs = map[string]any{ 122 "abs": math.Abs, 123 "acos": math.Acos, 124 "acosh": math.Acosh, 125 "asin": math.Asin, 126 "asinh": math.Asinh, 127 "atan": math.Atan, 128 "atan2": math.Atan2, 129 "atanh": math.Atanh, 130 "cbrt": math.Cbrt, 131 "ceil": math.Ceil, 132 "copysign": math.Copysign, 133 "cos": math.Cos, 134 "cosh": math.Cosh, 135 "dim": math.Dim, 136 "erf": math.Erf, 137 "erfc": math.Erfc, 138 "erfcinv": math.Erfcinv, 139 "erfinv": math.Erfinv, 140 "exp": math.Exp, 141 "exp2": math.Exp2, 142 "expm1": math.Expm1, 143 "fma": math.FMA, 144 "floor": math.Floor, 145 "gamma": math.Gamma, 146 "inf": inf, 147 "isinf": isInf, 148 "isnan": isNaN, 149 "j0": math.J0, 150 "j1": math.J1, 151 "jn": jn, 152 "ldexp": ldexp, 153 "lgamma": lgamma, 154 "log10": math.Log10, 155 "log1p": math.Log1p, 156 "log2": math.Log2, 157 "logb": math.Logb, 158 "mod": math.Mod, 159 "nan": math.NaN, 160 "nextafter": math.Nextafter, 161 "pow": math.Pow, 162 "pow10": pow10, 163 "remainder": math.Remainder, 164 "round": math.Round, 165 "roundtoeven": math.RoundToEven, 166 "signbit": signbit, 167 "sin": math.Sin, 168 "sinh": math.Sinh, 169 "sqrt": math.Sqrt, 170 "tan": math.Tan, 171 "tanh": math.Tanh, 172 "trunc": math.Trunc, 173 "y0": math.Y0, 174 "y1": math.Y1, 175 "yn": yn, 176 177 // a few aliases for the standard math funcs: some of the single-letter 178 // aliases are named after the ones in `bc`, the basic calculator tool 179 "a": math.Abs, 180 "c": math.Cos, 181 "ceiling": math.Ceil, 182 "cosine": math.Cos, 183 "e": math.Exp, 184 "isinf0": isAnyInf, 185 "isinfinite": isAnyInf, 186 "l": math.Log, 187 "ln": math.Log, 188 "lg": math.Log2, 189 "modulus": math.Mod, 190 "power": math.Pow, 191 "rem": math.Remainder, 192 "s": math.Sin, 193 "sine": math.Sin, 194 "t": math.Tan, 195 "tangent": math.Tan, 196 "truncate": math.Trunc, 197 "truncated": math.Trunc, 198 199 // not from standard math: these custom funcs were added manually 200 "beta": beta, 201 "bool": num2bool, 202 "clamp": clamp, 203 "cond": cond, // vector-arg if-else chain 204 "cube": cube, 205 "cubed": cube, 206 "degrees": degrees, 207 "deinf": deInf, 208 "denan": deNaN, 209 "factorial": factorial, 210 "fract": fract, 211 "horner": polyval, 212 "hypot": hypot, 213 "if": ifElse, 214 "ifelse": ifElse, 215 "inv": reciprocal, 216 "isanyinf": isAnyInf, 217 "isbad": isBad, 218 "isfin": isFinite, 219 "isfinite": isFinite, 220 "isgood": isGood, 221 "isinteger": isInteger, 222 "lbeta": lnBeta, 223 "len": length, 224 "length": length, 225 "lnbeta": lnBeta, 226 "log": math.Log, 227 "logistic": logistic, 228 "mag": length, 229 "max": max, 230 "min": min, 231 "neg": negate, 232 "negate": negate, 233 "not": notBool, 234 "polyval": polyval, 235 "radians": radians, 236 "range": rangef, // vector-arg max - min 237 "reciprocal": reciprocal, 238 "rev": revalue, 239 "revalue": revalue, 240 "scale": scale, 241 "sgn": sign, 242 "sign": sign, 243 "sinc": sinc, 244 "sq": sqr, 245 "sqmin": solveQuadMin, 246 "sqmax": solveQuadMax, 247 "square": sqr, 248 "squared": sqr, 249 "unwrap": unwrap, 250 "wrap": wrap, 251 252 // a few aliases for the custom funcs 253 "deg": degrees, 254 "isint": isInteger, 255 "rad": radians, 256 257 // a few quicker 2-value versions of vararg funcs: the optimizer depends 258 // on these to rewrite 2-input uses of their vararg counterparts 259 "hypot2": math.Hypot, 260 "max2": math.Max, 261 "min2": math.Min, 262 263 // a few entries to enable custom syntax: the parser depends on these to 264 // rewrite binary expressions into func calls 265 "??": deNaN, 266 "?:": ifElse, 267 "===": same, 268 "!==": notSame, 269 } 270 271 // DefineDetFuncs adds more deterministic funcs to the default set. Such funcs 272 // are considered optimizable, since calling them with the same constant inputs 273 // is supposed to return the same constant outputs, as the name `deterministic` 274 // suggests. 275 // 276 // Only call this before compiling any scripts, and ensure all funcs given are 277 // supported and are deterministic. Random-output funcs certainly won't fit 278 // the bill here. 279 func DefineDetFuncs(funcs map[string]any) { 280 for k, v := range funcs { 281 determFuncs[k] = v 282 } 283 } 284 285 func sqr(x float64) float64 { 286 return x * x 287 } 288 289 func cube(x float64) float64 { 290 return x * x * x 291 } 292 293 func num2bool(x float64) float64 { 294 if x == 0 { 295 return 0 296 } 297 return 1 298 } 299 300 func logistic(x float64) float64 { 301 return 1 / (1 + math.Exp(-x)) 302 } 303 304 func sign(x float64) float64 { 305 if math.IsNaN(x) { 306 return x 307 } 308 if x > 0 { 309 return +1 310 } 311 if x < 0 { 312 return -1 313 } 314 return 0 315 } 316 317 func sinc(x float64) float64 { 318 if x == 0 { 319 return 1 320 } 321 return math.Sin(x) / x 322 } 323 324 func isInteger(x float64) float64 { 325 _, frac := math.Modf(x) 326 if frac == 0 { 327 return 1 328 } 329 return 0 330 } 331 332 func inf(sign float64) float64 { 333 return math.Inf(int(sign)) 334 } 335 336 func isInf(x float64, sign float64) float64 { 337 if math.IsInf(x, int(sign)) { 338 return 1 339 } 340 return 0 341 } 342 343 func isAnyInf(x float64) float64 { 344 if math.IsInf(x, 0) { 345 return 1 346 } 347 return 0 348 } 349 350 func isFinite(x float64) float64 { 351 if math.IsInf(x, 0) { 352 return 0 353 } 354 return 1 355 } 356 357 func isNaN(x float64) float64 { 358 if math.IsNaN(x) { 359 return 1 360 } 361 return 0 362 } 363 364 func isGood(x float64) float64 { 365 if math.IsNaN(x) || math.IsInf(x, 0) { 366 return 0 367 } 368 return 1 369 } 370 371 func isBad(x float64) float64 { 372 if math.IsNaN(x) || math.IsInf(x, 0) { 373 return 1 374 } 375 return 0 376 } 377 378 func same(x, y float64) float64 { 379 if math.IsNaN(x) && math.IsNaN(y) { 380 return 1 381 } 382 return debool(x == y) 383 } 384 385 func notSame(x, y float64) float64 { 386 if math.IsNaN(x) && math.IsNaN(y) { 387 return 0 388 } 389 return debool(x != y) 390 } 391 392 func deNaN(x float64, instead float64) float64 { 393 if !math.IsNaN(x) { 394 return x 395 } 396 return instead 397 } 398 399 func deInf(x float64, instead float64) float64 { 400 if !math.IsInf(x, 0) { 401 return x 402 } 403 return instead 404 } 405 406 func revalue(x float64, instead float64) float64 { 407 if !math.IsNaN(x) && !math.IsInf(x, 0) { 408 return x 409 } 410 return instead 411 } 412 413 func pow10(n float64) float64 { 414 return math.Pow10(int(n)) 415 } 416 417 func jn(n, x float64) float64 { 418 return math.Jn(int(n), x) 419 } 420 421 func ldexp(frac, exp float64) float64 { 422 return math.Ldexp(frac, int(exp)) 423 } 424 425 func lgamma(x float64) float64 { 426 y, s := math.Lgamma(x) 427 if s < 0 { 428 return math.NaN() 429 } 430 return y 431 } 432 433 func signbit(x float64) float64 { 434 if math.Signbit(x) { 435 return 1 436 } 437 return 0 438 } 439 440 func yn(n, x float64) float64 { 441 return math.Yn(int(n), x) 442 } 443 444 func negate(x float64) float64 { 445 return -x 446 } 447 448 func reciprocal(x float64) float64 { 449 return 1 / x 450 } 451 452 func rangef(v ...float64) float64 { 453 min := math.Inf(+1) 454 max := math.Inf(-1) 455 for _, f := range v { 456 min = math.Min(min, f) 457 max = math.Max(max, f) 458 } 459 return max - min 460 } 461 462 func cond(v ...float64) float64 { 463 for { 464 switch len(v) { 465 case 0: 466 // either no values are left, or no values were given at all 467 return math.NaN() 468 469 case 1: 470 // either all previous conditions failed, and this last value is 471 // automatically chosen, or only 1 value was given to begin with 472 return v[0] 473 474 default: 475 // check condition: if true (non-0), return the value after it 476 if v[0] != 0 { 477 return v[1] 478 } 479 // condition was false, so skip the leading pair of values 480 v = v[2:] 481 } 482 } 483 } 484 485 func notBool(x float64) float64 { 486 if x == 0 { 487 return 1 488 } 489 return 0 490 } 491 492 func ifElse(cond float64, yes, no float64) float64 { 493 if cond != 0 { 494 return yes 495 } 496 return no 497 } 498 499 func lnGamma(x float64) float64 { 500 y, s := math.Lgamma(x) 501 if s < 0 { 502 return math.NaN() 503 } 504 return y 505 } 506 507 func lnBeta(x float64, y float64) float64 { 508 return lnGamma(x) + lnGamma(y) - lnGamma(x+y) 509 } 510 511 func beta(x float64, y float64) float64 { 512 return math.Exp(lnBeta(x, y)) 513 } 514 515 func factorial(n float64) float64 { 516 return math.Round(math.Gamma(n + 1)) 517 } 518 519 func degrees(rad float64) float64 { 520 return rad2degMult * rad 521 } 522 523 func radians(deg float64) float64 { 524 return deg2radMult * deg 525 } 526 527 func fract(x float64) float64 { 528 return x - math.Floor(x) 529 } 530 531 func min(v ...float64) float64 { 532 min := +math.Inf(+1) 533 for _, f := range v { 534 min = math.Min(min, f) 535 } 536 return min 537 } 538 539 func max(v ...float64) float64 { 540 max := +math.Inf(-1) 541 for _, f := range v { 542 max = math.Max(max, f) 543 } 544 return max 545 } 546 547 func hypot(v ...float64) float64 { 548 sumsq := 0.0 549 for _, f := range v { 550 sumsq += f * f 551 } 552 return math.Sqrt(sumsq) 553 } 554 555 func length(v ...float64) float64 { 556 ss := 0.0 557 for _, f := range v { 558 ss += f * f 559 } 560 return math.Sqrt(ss) 561 } 562 563 // solveQuadMin finds the lowest solution of a 2nd-degree polynomial, using 564 // a formula which is more accurate than the textbook one 565 func solveQuadMin(a, b, c float64) float64 { 566 disc := math.Sqrt(b*b - 4*a*c) 567 r1 := 2 * c / (-b - disc) 568 return r1 569 } 570 571 // solveQuadMax finds the highest solution of a 2nd-degree polynomial, using 572 // a formula which is more accurate than the textbook one 573 func solveQuadMax(a, b, c float64) float64 { 574 disc := math.Sqrt(b*b - 4*a*c) 575 r2 := 2 * c / (-b + disc) 576 return r2 577 } 578 579 func wrap(x float64, min, max float64) float64 { 580 return (x - min) / (max - min) 581 } 582 583 func unwrap(x float64, min, max float64) float64 { 584 return (max-min)*x + min 585 } 586 587 func clamp(x float64, min, max float64) float64 { 588 return math.Min(math.Max(x, min), max) 589 } 590 591 func scale(x float64, xmin, xmax, ymin, ymax float64) float64 { 592 k := (x - xmin) / (xmax - xmin) 593 return (ymax-ymin)*k + ymin 594 } 595 596 // polyval runs horner's algorithm on a value, with the polynomial coefficients 597 // given after it, higher-order first 598 func polyval(x float64, v ...float64) float64 { 599 if len(v) == 0 { 600 return 0 601 } 602 603 x0 := x 604 x = 1.0 605 y := 0.0 606 for i := len(v) - 1; i >= 0; i-- { 607 y += v[i] * x 608 x *= x0 609 } 610 return y 611 } File: fmscripts/math_test.go 1 package fmscripts 2 3 import "testing" 4 5 func TestTables(t *testing.T) { 6 for k, v := range determFuncs { 7 t.Run(k, func(t *testing.T) { 8 if !isSupportedFunc(v) { 9 t.Fatalf("unsupported func of type %T", v) 10 } 11 }) 12 } 13 } File: fmscripts/mit-license.txt 1 The MIT License (MIT) 2 3 Copyright © 2024 pacman64 4 5 Permission is hereby granted, free of charge, to any person obtaining a copy of 6 this software and associated documentation files (the “Software”), to deal 7 in the Software without restriction, including without limitation the rights to 8 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 9 of the Software, and to permit persons to whom the Software is furnished to do 10 so, subject to the following conditions: 11 12 The above copyright notice and this permission notice shall be included in all 13 copies or substantial portions of the Software. 14 15 THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 20 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 21 SOFTWARE. File: fmscripts/optimizers.go 1 package fmscripts 2 3 import ( 4 "math" 5 ) 6 7 // unary2func matches unary operators to funcs the optimizer can use to eval 8 // constant-input unary expressions into their results 9 var unary2func = map[string]func(x float64) float64{ 10 // avoid unary +, since it's a no-op and thus there's no instruction for 11 // it, which in turn makes unit-tests for these optimization tables fail 12 // unnecessarily 13 // "+": func(x float64) float64 { return +x }, 14 15 "-": func(x float64) float64 { return -x }, 16 "!": func(x float64) float64 { return debool(x == 0) }, 17 "&": func(x float64) float64 { return math.Abs(x) }, 18 "*": func(x float64) float64 { return x * x }, 19 "^": func(x float64) float64 { return x * x }, 20 "/": func(x float64) float64 { return 1 / x }, 21 } 22 23 // binary2func matches binary operators to funcs the optimizer can use to eval 24 // constant-input binary expressions into their results 25 var binary2func = map[string]func(x, y float64) float64{ 26 "+": func(x, y float64) float64 { return x + y }, 27 "-": func(x, y float64) float64 { return x - y }, 28 "*": func(x, y float64) float64 { return x * y }, 29 "/": func(x, y float64) float64 { return x / y }, 30 "%": func(x, y float64) float64 { return math.Mod(x, y) }, 31 "&": func(x, y float64) float64 { return debool(x != 0 && y != 0) }, 32 "&&": func(x, y float64) float64 { return debool(x != 0 && y != 0) }, 33 "|": func(x, y float64) float64 { return debool(x != 0 || y != 0) }, 34 "||": func(x, y float64) float64 { return debool(x != 0 || y != 0) }, 35 "==": func(x, y float64) float64 { return debool(x == y) }, 36 "!=": func(x, y float64) float64 { return debool(x != y) }, 37 "<>": func(x, y float64) float64 { return debool(x != y) }, 38 "<": func(x, y float64) float64 { return debool(x < y) }, 39 "<=": func(x, y float64) float64 { return debool(x <= y) }, 40 ">": func(x, y float64) float64 { return debool(x > y) }, 41 ">=": func(x, y float64) float64 { return debool(x >= y) }, 42 "**": func(x, y float64) float64 { return math.Pow(x, y) }, 43 "^": func(x, y float64) float64 { return math.Pow(x, y) }, 44 } 45 46 // func2unary turns built-in func names into built-in unary operators 47 var func2unary = map[string]string{ 48 "a": "&", 49 "abs": "&", 50 "inv": "/", 51 "neg": "-", 52 "negate": "-", 53 "reciprocal": "/", 54 "sq": "*", 55 "square": "*", 56 "squared": "*", 57 } 58 59 // func2binary turns built-in func names into built-in binary operators 60 var func2binary = map[string]string{ 61 "mod": "%", 62 "modulus": "%", 63 "pow": "**", 64 "power": "**", 65 } 66 67 // vararg2func2 matches variable-argument funcs to their 2-argument versions 68 var vararg2func2 = map[string]string{ 69 "hypot": "hypot2", 70 "max": "max2", 71 "min": "min2", 72 } 73 74 // optimize tries to simplify the expression given as much as possible, by 75 // simplifying constants whenever possible, and exploiting known built-in 76 // funcs which are known to behave deterministically 77 func (c *Compiler) optimize(expr any) any { 78 switch expr := expr.(type) { 79 case []any: 80 return c.optimizeCombo(expr) 81 82 case unaryExpr: 83 return c.optimizeUnaryExpr(expr) 84 85 case binaryExpr: 86 return c.optimizeBinaryExpr(expr) 87 88 case callExpr: 89 return c.optimizeCallExpr(expr) 90 91 case assignExpr: 92 expr.expr = c.optimize(expr.expr) 93 return expr 94 95 default: 96 f, ok := c.tryConstant(expr) 97 if ok { 98 return f 99 } 100 return expr 101 } 102 } 103 104 // optimizeCombo handles a sequence of expressions for the optimizer 105 func (c *Compiler) optimizeCombo(exprs []any) any { 106 if len(exprs) == 1 { 107 return c.optimize(exprs[0]) 108 } 109 110 // count how many expressions are considered useful: these are 111 // assignments as well as the last expression, since that's what 112 // determines the script's final result 113 useful := 0 114 for i, v := range exprs { 115 _, ok := v.(assignExpr) 116 if ok || i == len(exprs)-1 { 117 useful++ 118 } 119 } 120 121 // ignore all expressions which are a waste of time, and optimize 122 // all other expressions 123 res := make([]any, 0, useful) 124 for i, v := range exprs { 125 _, ok := v.(assignExpr) 126 if ok || i == len(exprs)-1 { 127 res = append(res, c.optimize(v)) 128 } 129 } 130 return res 131 } 132 133 // optimizeUnaryExpr handles unary expressions for the optimizer 134 func (c *Compiler) optimizeUnaryExpr(expr unaryExpr) any { 135 // recursively optimize input 136 expr.x = c.optimize(expr.x) 137 138 // optimize unary ops on a constant into concrete values 139 if x, ok := expr.x.(float64); ok { 140 if fn, ok := unary2func[expr.op]; ok { 141 return fn(x) 142 } 143 } 144 145 switch expr.op { 146 case "+": 147 // unary plus is an identity operation 148 return expr.x 149 150 default: 151 return expr 152 } 153 } 154 155 // optimizeBinaryExpr handles binary expressions for the optimizer 156 func (c *Compiler) optimizeBinaryExpr(expr binaryExpr) any { 157 // recursively optimize inputs 158 expr.x = c.optimize(expr.x) 159 expr.y = c.optimize(expr.y) 160 161 // optimize binary ops on 2 constants into concrete values 162 if x, ok := expr.x.(float64); ok { 163 if y, ok := expr.y.(float64); ok { 164 if fn, ok := binary2func[expr.op]; ok { 165 return fn(x, y) 166 } 167 } 168 } 169 170 switch expr.op { 171 case "+": 172 if expr.x == 0.0 { 173 // 0+y -> y 174 return expr.y 175 } 176 if expr.y == 0.0 { 177 // x+0 -> x 178 return expr.x 179 } 180 181 case "-": 182 if expr.x == 0.0 { 183 // 0-y -> -y 184 return c.optimizeUnaryExpr(unaryExpr{op: "-", x: expr.y}) 185 } 186 if expr.y == 0.0 { 187 // x-0 -> x 188 return expr.x 189 } 190 191 case "*": 192 if expr.x == 0.0 || expr.y == 0.0 { 193 // 0*y -> 0 194 // x*0 -> 0 195 return 0.0 196 } 197 if expr.x == 1.0 { 198 // 1*y -> y 199 return expr.y 200 } 201 if expr.y == 1.0 { 202 // x*1 -> x 203 return expr.x 204 } 205 if expr.x == -1.0 { 206 // -1*y -> -y 207 return c.optimizeUnaryExpr(unaryExpr{op: "-", x: expr.y}) 208 } 209 if expr.y == -1.0 { 210 // x*-1 -> -x 211 return c.optimizeUnaryExpr(unaryExpr{op: "-", x: expr.x}) 212 } 213 214 case "/": 215 if expr.x == 1.0 { 216 // 1/y -> reciprocal of y 217 return c.optimizeUnaryExpr(unaryExpr{op: "/", x: expr.y}) 218 } 219 if expr.y == 1.0 { 220 // x/1 -> x 221 return expr.x 222 } 223 if expr.y == -1.0 { 224 // x/-1 -> -x 225 return c.optimizeUnaryExpr(unaryExpr{op: "-", x: expr.x}) 226 } 227 228 case "**": 229 switch expr.y { 230 case -1.0: 231 // x**-1 -> 1/x, reciprocal of x 232 return c.optimizeUnaryExpr(unaryExpr{op: "/", x: expr.x}) 233 case 0.0: 234 // x**0 -> 1 235 return 1.0 236 case 1.0: 237 // x**1 -> x 238 return expr.x 239 case 2.0: 240 // x**2 -> *x 241 return c.optimizeUnaryExpr(unaryExpr{op: "*", x: expr.x}) 242 case 3.0: 243 // x**3 -> *x*x 244 sq := unaryExpr{op: "*", x: expr.x} 245 return c.optimizeBinaryExpr(binaryExpr{op: "*", x: sq, y: expr.x}) 246 } 247 248 case "&", "&&": 249 if expr.x == 0.0 || expr.y == 0.0 { 250 // 0 && y -> 0 251 // x && 0 -> 0 252 return 0.0 253 } 254 } 255 256 // no simplifiable patterns were detected 257 return expr 258 } 259 260 // optimizeCallExpr optimizes special cases of built-in func calls 261 func (c *Compiler) optimizeCallExpr(call callExpr) any { 262 // recursively optimize all inputs, and keep track if they're all 263 // constants in the end 264 numlit := 0 265 for i, v := range call.args { 266 v = c.optimize(v) 267 call.args[i] = v 268 if _, ok := v.(float64); ok { 269 numlit++ 270 } 271 } 272 273 // if func is overridden, there's no guarantee the new func works the same 274 if _, ok := determFuncs[call.name]; c.ftype[call.name] != nil || !ok { 275 return call 276 } 277 278 // from this point on, func is guaranteed to be built-in and deterministic 279 280 // handle all-const inputs, by calling func and using its result 281 if numlit == len(call.args) { 282 in := make([]float64, 0, len(call.args)) 283 for _, v := range call.args { 284 f, _ := v.(float64) 285 in = append(in, f) 286 } 287 288 if f, ok := tryCall(determFuncs[call.name], in); ok { 289 return f 290 } 291 } 292 293 switch len(call.args) { 294 case 1: 295 if op, ok := func2unary[call.name]; ok { 296 expr := unaryExpr{op: op, x: call.args[0]} 297 return c.optimizeUnaryExpr(expr) 298 } 299 return call 300 301 case 2: 302 if op, ok := func2binary[call.name]; ok { 303 expr := binaryExpr{op: op, x: call.args[0], y: call.args[1]} 304 return c.optimizeBinaryExpr(expr) 305 } 306 if name, ok := vararg2func2[call.name]; ok { 307 call.name = name 308 return call 309 } 310 return call 311 312 default: 313 return call 314 } 315 } 316 317 // tryConstant tries to optimize the expression given into a constant 318 func (c *Compiler) tryConstant(expr any) (value float64, ok bool) { 319 switch expr := expr.(type) { 320 case float64: 321 return expr, true 322 323 case string: 324 if _, ok := c.vaddr[expr]; !ok { 325 // name isn't explicitly defined 326 if f, ok := mathConst[expr]; ok { 327 // and is a known math constant 328 return f, true 329 } 330 } 331 return 0, false 332 333 default: 334 return 0, false 335 } 336 } 337 338 // tryCall tries to simplify the function expression given into a constant 339 func tryCall(fn any, in []float64) (value float64, ok bool) { 340 switch fn := fn.(type) { 341 case func(float64) float64: 342 if len(in) == 1 { 343 return fn(in[0]), true 344 } 345 return 0, false 346 347 case func(float64, float64) float64: 348 if len(in) == 2 { 349 return fn(in[0], in[1]), true 350 } 351 return 0, false 352 353 case func(float64, float64, float64) float64: 354 if len(in) == 3 { 355 return fn(in[0], in[1], in[2]), true 356 } 357 return 0, false 358 359 case func(float64, float64, float64, float64) float64: 360 if len(in) == 4 { 361 return fn(in[0], in[1], in[2], in[3]), true 362 } 363 return 0, false 364 365 case func(float64, float64, float64, float64, float64) float64: 366 if len(in) == 5 { 367 return fn(in[0], in[1], in[2], in[3], in[4]), true 368 } 369 return 0, false 370 371 case func(...float64) float64: 372 return fn(in...), true 373 374 case func(float64, ...float64) float64: 375 if len(in) >= 1 { 376 return fn(in[0], in[1:]...), true 377 } 378 return 0, false 379 380 default: 381 // type isn't a supported func 382 return 0, false 383 } 384 } File: fmscripts/optimizers_test.go 1 package fmscripts 2 3 import ( 4 "math" 5 "reflect" 6 "testing" 7 ) 8 9 func TestOptimizerTables(t *testing.T) { 10 for k := range unary2func { 11 t.Run(k, func(t *testing.T) { 12 if _, ok := unary2op[k]; !ok { 13 t.Fatalf("missing unary constant optimizer for %q", k) 14 } 15 }) 16 } 17 18 for k := range binary2func { 19 t.Run(k, func(t *testing.T) { 20 if _, ok := binary2op[k]; !ok { 21 t.Fatalf("missing binary constant optimizer for %q", k) 22 } 23 }) 24 } 25 26 for k, name := range func2unary { 27 t.Run(k, func(t *testing.T) { 28 if _, ok := determFuncs[k]; !ok { 29 const fs = "func(x) optimizer %q has no matching built-in func" 30 t.Fatalf(fs, k) 31 } 32 33 if _, ok := unary2op[name]; !ok { 34 t.Fatalf("missing unary func optimizer for %q", k) 35 } 36 }) 37 } 38 39 for k, name := range func2binary { 40 t.Run(k, func(t *testing.T) { 41 if _, ok := determFuncs[k]; !ok { 42 const fs = "func(x, y) optimizer %q has no matching built-in func" 43 t.Fatalf(fs, k) 44 } 45 46 if _, ok := binary2op[name]; !ok { 47 t.Fatalf("missing binary func optimizer for %q", k) 48 } 49 }) 50 } 51 52 for k := range vararg2func2 { 53 t.Run(k, func(t *testing.T) { 54 if _, ok := determFuncs[k]; !ok { 55 const fs = "vararg optimizer %q has no matching built-in func" 56 t.Fatalf(fs, k) 57 } 58 }) 59 } 60 } 61 62 func TestOptimizer(t *testing.T) { 63 var tests = []struct { 64 Source string 65 Expected any 66 }{ 67 {"1", 1.0}, 68 {"3+4*5", 23.0}, 69 70 {"e", math.E}, 71 {"pi", math.Pi}, 72 {"phi", math.Phi}, 73 {"2*pi", 2 * math.Pi}, 74 {"4.51*phi-14.23564", 4.51*math.Phi - 14.23564}, 75 {"-e", -math.E}, 76 77 {"exp(2*pi)", math.Exp(2 * math.Pi)}, 78 {"log(2342.55) / log(43.21)", math.Log(2342.55) / math.Log(43.21)}, 79 {"f(3)", callExpr{name: "f", args: []any{3.0}}}, 80 {"min(3, 2, -1.5)", -1.5}, 81 82 {"hypot(x, 4)", callExpr{name: "hypot2", args: []any{"x", 4.0}}}, 83 {"max(x, 4)", callExpr{name: "max2", args: []any{"x", 4.0}}}, 84 {"min(x, 4)", callExpr{name: "min2", args: []any{"x", 4.0}}}, 85 86 {"rand()", callExpr{name: "rand"}}, 87 88 { 89 "sin(2_000 * x * tau * x)", 90 callExpr{ 91 name: "sin", 92 args: []any{ 93 binaryExpr{ 94 "*", 95 binaryExpr{ 96 "*", 97 binaryExpr{"*", 2_000.0, "x"}, 98 2 * math.Pi, 99 }, 100 "x", 101 }, 102 }, 103 }, 104 }, 105 106 { 107 "sin(10 * tau * exp(-20 * x)) * exp(-2 * x)", 108 binaryExpr{ 109 "*", 110 // sin(...) 111 callExpr{ 112 name: "sin", 113 args: []any{ 114 // 10 * tau * exp(...) 115 binaryExpr{ 116 "*", 117 10 * 2 * math.Pi, 118 // exp(-20 * x) 119 callExpr{ 120 name: "exp", 121 args: []any{ 122 binaryExpr{"*", -20.0, "x"}, 123 }, 124 }, 125 }, 126 }, 127 }, 128 // exp(-2 * x) 129 callExpr{ 130 name: "exp", 131 args: []any{binaryExpr{"*", -2.0, "x"}}, 132 }, 133 }, 134 }, 135 } 136 137 defs := map[string]any{ 138 "x": 3.5, 139 "f": math.Exp, 140 } 141 142 for _, tc := range tests { 143 t.Run(tc.Source, func(t *testing.T) { 144 var c Compiler 145 root, err := parse(tc.Source) 146 if err != nil { 147 t.Fatal(err) 148 return 149 } 150 151 if err := c.reset(defs); err != nil { 152 t.Fatal(err) 153 return 154 } 155 156 got := c.optimize(root) 157 if !reflect.DeepEqual(got, tc.Expected) { 158 const fs = "expected result to be\n%#v\ninstead of\n%#v" 159 t.Fatalf(fs, tc.Expected, got) 160 return 161 } 162 }) 163 } 164 } File: fmscripts/parsing.go 1 package fmscripts 2 3 import ( 4 "errors" 5 "fmt" 6 "strconv" 7 "strings" 8 ) 9 10 // parse turns source code into an expression type interpreters can use. 11 func parse(src string) (any, error) { 12 tok := newTokenizer(src) 13 par, err := newParser(&tok) 14 if err != nil { 15 return nil, err 16 } 17 18 v, err := par.parse() 19 err = par.improveError(err, src) 20 return v, err 21 } 22 23 // pickLine slices a string, picking one of its lines via a 1-based index: 24 // func improveError uses it to isolate the line of code an error came from 25 func pickLine(src string, linenum int) string { 26 // skip the lines before the target one 27 for i := 0; i < linenum && len(src) > 0; i++ { 28 j := strings.IndexByte(src, '\n') 29 if j < 0 { 30 break 31 } 32 src = src[j+1:] 33 } 34 35 // limit leftover to a single line 36 i := strings.IndexByte(src, '\n') 37 if i >= 0 { 38 return src[:i] 39 } 40 return src 41 } 42 43 // unaryExpr is a unary expression 44 type unaryExpr struct { 45 op string 46 x any 47 } 48 49 // binaryExpr is a binary expression 50 type binaryExpr struct { 51 op string 52 x any 53 y any 54 } 55 56 // callExpr is a function call and its arguments 57 type callExpr struct { 58 name string 59 args []any 60 } 61 62 // assignExpr is a value/variable assignment 63 type assignExpr struct { 64 name string 65 expr any 66 } 67 68 // parser is a parser for JavaScript-like syntax, limited to operations on 69 // 64-bit floating-point numbers 70 type parser struct { 71 tokens []token 72 line int 73 pos int 74 toklen int 75 } 76 77 // newParser is the constructor for type parser 78 func newParser(t *tokenizer) (parser, error) { 79 var p parser 80 81 // get all tokens from the source code 82 for { 83 v, err := t.next() 84 if v.kind != unknownToken { 85 p.tokens = append(p.tokens, v) 86 } 87 88 if err == errEOS { 89 // done scanning/tokenizing 90 return p, nil 91 } 92 93 if err != nil { 94 // handle actual errors 95 return p, err 96 } 97 } 98 } 99 100 // improveError adds more info about where exactly in the source code an error 101 // came from, thus making error messages much more useful 102 func (p *parser) improveError(err error, src string) error { 103 if err == nil { 104 return nil 105 } 106 107 line := pickLine(src, p.line) 108 if len(line) == 0 || p.pos < 1 { 109 const fs = "(line %d: pos %d): %w" 110 return fmt.Errorf(fs, p.line, p.pos, err) 111 } 112 113 ptr := strings.Repeat(" ", p.pos) + "^" 114 const fs = "(line %d: pos %d): %w\n%s\n%s" 115 return fmt.Errorf(fs, p.line, p.pos, err, line, ptr) 116 } 117 118 // parse tries to turn tokens into a compilable abstract syntax tree, and is 119 // the parser's entry point 120 func (p *parser) parse() (any, error) { 121 // source codes with no tokens are always errors 122 if len(p.tokens) == 0 { 123 const msg = "source code is empty, or has no useful expressions" 124 return nil, errors.New(msg) 125 } 126 127 // handle optional excel-like leading equal sign 128 p.acceptSyntax(`=`) 129 130 // ignore trailing semicolons 131 for len(p.tokens) > 0 { 132 t := p.tokens[len(p.tokens)-1] 133 if t.kind != syntaxToken || t.value != `;` { 134 break 135 } 136 p.tokens = p.tokens[:len(p.tokens)-1] 137 } 138 139 // handle single expressions as well as multiple semicolon-separated 140 // expressions: the latter allow value assignments/updates in scripts 141 var res []any 142 for keepGoing := true; keepGoing && len(p.tokens) > 0; { 143 v, err := p.parseExpression() 144 if err != nil && err != errEOS { 145 return v, err 146 } 147 148 res = append(res, v) 149 // handle optional separator/continuation semicolons 150 _, keepGoing = p.acceptSyntax(`;`) 151 } 152 153 // unexpected unparsed trailing tokens are always errors; any trailing 154 // semicolons in the original script are already trimmed 155 if len(p.tokens) > 0 { 156 const fs = "unexpected %s" 157 return res, fmt.Errorf(fs, p.tokens[0].value) 158 } 159 160 // make scripts ending in an assignment also load that value, so they're 161 // useful, as assignments result in no useful value by themselves 162 assign, ok := res[len(res)-1].(assignExpr) 163 if ok { 164 res = append(res, assign.name) 165 } 166 167 // turn 1-item combo expressions into their only expression: some 168 // unit tests may rely on that for convenience 169 if len(res) == 1 { 170 return res[0], nil 171 } 172 return res, nil 173 } 174 175 // acceptSyntax advances the parser on the first syntactic string matched: 176 // notice any number of alternatives/options are allowed, as the syntax 177 // allows/requires at various points 178 func (p *parser) acceptSyntax(syntax ...string) (match string, ok bool) { 179 if len(p.tokens) == 0 { 180 return "", false 181 } 182 183 t := p.tokens[0] 184 if t.kind != syntaxToken { 185 return "", false 186 } 187 188 for _, s := range syntax { 189 if t.value == s { 190 p.advance() 191 return s, true 192 } 193 } 194 return "", false 195 } 196 197 // advance skips the current leading token, if there are still any left 198 func (p *parser) advance() { 199 if len(p.tokens) == 0 { 200 return 201 } 202 203 t := p.tokens[0] 204 p.tokens = p.tokens[1:] 205 p.line = t.line 206 p.pos = t.pos 207 p.toklen = len(t.value) 208 } 209 210 // acceptNumeric advances the parser on a numeric value, but only if it's 211 // the leading token: conversely, any other type of token doesn't advance 212 // the parser; when matches happen the resulting strings need parsing via 213 // func parseNumber 214 func (p *parser) acceptNumeric() (numliteral string, ok bool) { 215 if len(p.tokens) == 0 { 216 return "", false 217 } 218 219 t := p.tokens[0] 220 if t.kind == numberToken { 221 p.advance() 222 return t.value, true 223 } 224 return "", false 225 } 226 227 // demandSyntax imposes a specific syntactic element to follow, or else it's 228 // an error 229 func (p *parser) demandSyntax(syntax string) error { 230 if len(p.tokens) == 0 { 231 return fmt.Errorf("expected %s instead of the end of source", syntax) 232 } 233 234 first := p.tokens[0] 235 if first.kind == syntaxToken && first.value == syntax { 236 p.advance() 237 return nil 238 } 239 return fmt.Errorf("expected %s instead of %s", syntax, first.value) 240 } 241 242 func (p *parser) parseExpression() (any, error) { 243 x, err := p.parseComparison() 244 if err != nil { 245 return x, err 246 } 247 248 // handle assignment statements 249 if _, ok := p.acceptSyntax(`=`, `:=`); ok { 250 varname, ok := x.(string) 251 if !ok { 252 const fs = "expected a variable name, instead of a %T" 253 return nil, fmt.Errorf(fs, x) 254 } 255 256 x, err := p.parseExpression() 257 expr := assignExpr{name: varname, expr: x} 258 return expr, err 259 } 260 261 // handle and/or logical chains 262 for { 263 if op, ok := p.acceptSyntax(`&&`, `||`, `&`, `|`); ok { 264 y, err := p.parseExpression() 265 if err != nil { 266 return y, err 267 } 268 x = binaryExpr{op: op, x: x, y: y} 269 continue 270 } 271 break 272 } 273 274 // handle maybe-properties 275 if _, ok := p.acceptSyntax(`??`); ok { 276 y, err := p.parseExpression() 277 expr := callExpr{name: "??", args: []any{x, y}} 278 return expr, err 279 } 280 281 // handle choice/ternary operator 282 if _, ok := p.acceptSyntax(`?`); ok { 283 y, err := p.parseExpression() 284 if err != nil { 285 expr := callExpr{name: "?:", args: []any{x, nil, nil}} 286 return expr, err 287 } 288 289 if _, ok := p.acceptSyntax(`:`); ok { 290 z, err := p.parseExpression() 291 expr := callExpr{name: "?:", args: []any{x, y, z}} 292 return expr, err 293 } 294 295 if len(p.tokens) == 0 { 296 expr := callExpr{name: "?:", args: []any{x, y, nil}} 297 return expr, errors.New("expected `:`") 298 } 299 300 s := p.tokens[0].value 301 expr := callExpr{name: "?:", args: []any{x, y, nil}} 302 err = fmt.Errorf("expected `:`, but got %q instead", s) 303 return expr, err 304 } 305 306 // expression was just a comparison, or simpler 307 return x, nil 308 } 309 310 func (p *parser) parseComparison() (any, error) { 311 x, err := p.parseTerm() 312 if err != nil { 313 return x, err 314 } 315 316 op, ok := p.acceptSyntax(`==`, `!=`, `<`, `>`, `<=`, `>=`, `<>`, `===`, `!==`) 317 if ok { 318 y, err := p.parseTerm() 319 return binaryExpr{op: op, x: x, y: y}, err 320 } 321 return x, err 322 } 323 324 // parseBinary handles binary operations, by recursing depth-first on the left 325 // side of binary expressions; going tail-recursive on these would reverse the 326 // order of arguments instead, which is obviously wrong 327 func (p *parser) parseBinary(parse func() (any, error), syntax ...string) (any, error) { 328 x, err := parse() 329 if err != nil { 330 return x, err 331 } 332 333 for { 334 op, ok := p.acceptSyntax(syntax...) 335 if !ok { 336 return x, nil 337 } 338 339 y, err := parse() 340 x = binaryExpr{op: op, x: x, y: y} 341 if err != nil { 342 return x, err 343 } 344 } 345 } 346 347 func (p *parser) parseTerm() (any, error) { 348 return p.parseBinary(func() (any, error) { 349 return p.parseProduct() 350 }, `+`, `-`, `^`) 351 } 352 353 func (p *parser) parseProduct() (any, error) { 354 return p.parseBinary(func() (any, error) { 355 return p.parsePower() 356 }, `*`, `/`, `%`) 357 } 358 359 func (p *parser) parsePower() (any, error) { 360 return p.parseBinary(func() (any, error) { 361 return p.parseValue() 362 }, `**`, `^`) 363 } 364 365 func (p *parser) parseValue() (any, error) { 366 // handle unary operators which can also be considered part of numeric 367 // literals, and thus should be simplified away 368 if op, ok := p.acceptSyntax(`+`, `-`); ok { 369 if s, ok := p.acceptNumeric(); ok { 370 x, err := strconv.ParseFloat(s, 64) 371 if err != nil { 372 return nil, err 373 } 374 if simpler, ok := simplifyNumber(op, x); ok { 375 return simpler, nil 376 } 377 return unaryExpr{op: op, x: x}, nil 378 } 379 380 x, err := p.parsePower() 381 return unaryExpr{op: op, x: x}, err 382 } 383 384 // handle all other unary operators 385 if op, ok := p.acceptSyntax(`!`, `&`, `*`, `^`); ok { 386 x, err := p.parsePower() 387 return unaryExpr{op: op, x: x}, err 388 } 389 390 // handle subexpression in parentheses 391 if _, ok := p.acceptSyntax(`(`); ok { 392 x, err := p.parseExpression() 393 if err != nil { 394 return x, err 395 } 396 397 if err := p.demandSyntax(`)`); err != nil { 398 return x, err 399 } 400 return p.parseAccessors(x) 401 } 402 403 // handle subexpression in square brackets: it's just an alternative to 404 // using parentheses for subexpressions 405 if _, ok := p.acceptSyntax(`[`); ok { 406 x, err := p.parseExpression() 407 if err != nil { 408 return x, err 409 } 410 411 if err := p.demandSyntax(`]`); err != nil { 412 return x, err 413 } 414 return p.parseAccessors(x) 415 } 416 417 // handle all other cases 418 x, err := p.parseSimpleValue() 419 if err != nil { 420 return x, err 421 } 422 423 // handle arbitrarily-long chains of accessors 424 return p.parseAccessors(x) 425 } 426 427 // parseSimpleValue handles a numeric literal or a variable/func name, also 428 // known as identifier 429 func (p *parser) parseSimpleValue() (any, error) { 430 if len(p.tokens) == 0 { 431 return nil, errEOS 432 } 433 t := p.tokens[0] 434 435 switch t.kind { 436 case identifierToken: 437 p.advance() 438 // handle func calls, such as f(...) 439 if _, ok := p.acceptSyntax(`(`); ok { 440 args, err := p.parseList(`)`) 441 expr := callExpr{name: t.value, args: args} 442 return expr, err 443 } 444 // handle func calls, such as f[...] 445 if _, ok := p.acceptSyntax(`[`); ok { 446 args, err := p.parseList(`]`) 447 expr := callExpr{name: t.value, args: args} 448 return expr, err 449 } 450 return t.value, nil 451 452 case numberToken: 453 p.advance() 454 return strconv.ParseFloat(t.value, 64) 455 456 default: 457 const fs = "unexpected %s (token type %d)" 458 return nil, fmt.Errorf(fs, t.value, t.kind) 459 } 460 } 461 462 // parseAccessors handles an arbitrarily-long chain of accessors 463 func (p *parser) parseAccessors(x any) (any, error) { 464 for { 465 s, ok := p.acceptSyntax(`.`, `@`) 466 if !ok { 467 // dot-chain is over 468 return x, nil 469 } 470 471 // handle property/method accessors 472 v, err := p.parseDot(s, x) 473 if err != nil { 474 return v, err 475 } 476 x = v 477 } 478 } 479 480 // parseDot handles what follows a syntactic dot, as opposed to a dot which 481 // may be part of a numeric literal 482 func (p *parser) parseDot(after string, x any) (any, error) { 483 if len(p.tokens) == 0 { 484 const fs = "unexpected end of source after a %q" 485 return x, fmt.Errorf(fs, after) 486 } 487 488 t := p.tokens[0] 489 p.advance() 490 if t.kind != identifierToken { 491 const fs = "expected a valid property name, but got %s instead" 492 return x, fmt.Errorf(fs, t.value) 493 } 494 495 if _, ok := p.acceptSyntax(`(`); ok { 496 items, err := p.parseList(`)`) 497 args := append([]any{x}, items...) 498 return callExpr{name: t.value, args: args}, err 499 } 500 501 if _, ok := p.acceptSyntax(`[`); ok { 502 items, err := p.parseList(`]`) 503 args := append([]any{x}, items...) 504 return callExpr{name: t.value, args: args}, err 505 } 506 507 return callExpr{name: t.value, args: []any{x}}, nil 508 } 509 510 // parseList handles the argument-list following a `(` or a `[` 511 func (p *parser) parseList(end string) ([]any, error) { 512 var arr []any 513 for len(p.tokens) > 0 { 514 if _, ok := p.acceptSyntax(`,`); ok { 515 // ensure extra/trailing commas are allowed/ignored 516 continue 517 } 518 519 if _, ok := p.acceptSyntax(end); ok { 520 return arr, nil 521 } 522 523 v, err := p.parseExpression() 524 if err != nil { 525 return arr, err 526 } 527 arr = append(arr, v) 528 } 529 530 // return an appropriate error for the unexpected end of the source 531 return arr, p.demandSyntax(`)`) 532 } 533 534 // simplifyNumber tries to simplify a few trivial unary operations on 535 // numeric constants 536 func simplifyNumber(op string, x any) (v any, ok bool) { 537 if x, ok := x.(float64); ok { 538 switch op { 539 case `+`: 540 return x, true 541 case `-`: 542 return -x, true 543 default: 544 return x, false 545 } 546 } 547 return x, false 548 } File: fmscripts/programs.go 1 package fmscripts 2 3 import ( 4 "math" 5 ) 6 7 // So far, my apps relying on this package are 8 // 9 // - fh, a Function Heatmapper which color-codes f(x, y), seen from above 10 // - star, a STAtistical Resampler to calculate stats from tabular data 11 // - waveout, an app to emit sample-by-sample wave-audio by formula 12 13 // Quick Notes on Performance 14 // 15 // Note: while these microbenchmarks are far from proper benchmarks, Club Pulse 16 // can still give a general idea of what relative performance to expect. 17 // 18 // While funscripts.Interpreter can do anything a Program can do, and much more, 19 // a fmscripts.Program is way faster for float64-only tasks: typical speed-ups 20 // are between 20-to-50 times. Various simple benchmarks suggest running speed 21 // is between 1/2 and 1/4 of native funcs. 22 // 23 // Reimplementations of the Club Pulse benchmark, when run 50 million times, 24 // suggest this package is starting to measure the relative speed of various 25 // trigonometric func across JIT-ted script runners, running somewhat slower 26 // than NodeJS/V8, faster than PyPy, and much faster than Python. 27 // 28 // Other scripted tests, which aren't as trigonometry/exponential-heavy, hint 29 // at even higher speed-ups compared to Python and PyPy, as well as being 30 // almost as fast as NodeJS/V8. 31 // 32 // Being so close to Node's V8 (0.6x - 0.8x its speed) is a surprisingly good 33 // result for the relatively little effort this package took. 34 35 const ( 36 maxArgsLen = 1<<16 - 1 // max length for the []float64 input of callv 37 maxOpIndex = 1<<32 - 1 // max index for values 38 ) 39 40 // types to keep compiler code the same, while changing sizes of numOp fields 41 type ( 42 opcode uint16 43 opargs uint16 // opcode directly affects max correct value of maxArgsLen 44 opindex uint32 // opcode directly affects max correct value of maxOpIndex 45 ) 46 47 // numOp is a numeric operation in a program 48 type numOp struct { 49 What opcode // what to do 50 NumArgs opargs // vector-length only used for callv and call1v 51 Index opindex // index to load a value or call a function 52 } 53 54 // Since the go 1.19 compiler started compiling dense switch statements using 55 // jump tables, adding more basic ops doesn't slow things down anymore when 56 // reaching the next power-of-2 thresholds in the number of cases. 57 58 const ( 59 // load float64 value to top of the stack 60 load opcode = iota 61 62 // pop top of stack and store it into value 63 store opcode = iota 64 65 // unary operations 66 neg opcode = iota 67 not opcode = iota 68 abs opcode = iota 69 square opcode = iota 70 // 1/x, the reciprocal/inverse value 71 rec opcode = iota 72 // x%1, but faster than math.Mod(x, 1) 73 mod1 opcode = iota 74 75 // arithmetic and logic operations: 2 float64 inputs, 1 float64 output 76 77 add opcode = iota 78 sub opcode = iota 79 mul opcode = iota 80 div opcode = iota 81 mod opcode = iota 82 pow opcode = iota 83 and opcode = iota 84 or opcode = iota 85 86 // binary comparisons: 2 float64 inputs, 1 booleanized float64 output 87 88 equal opcode = iota 89 notequal opcode = iota 90 less opcode = iota 91 lessoreq opcode = iota 92 more opcode = iota 93 moreoreq opcode = iota 94 95 // function callers with 1..5 float64 inputs and a float64 result 96 97 call0 opcode = iota 98 call1 opcode = iota 99 call2 opcode = iota 100 call3 opcode = iota 101 call4 opcode = iota 102 call5 opcode = iota 103 104 // var-arg input function callers 105 106 callv opcode = iota 107 call1v opcode = iota 108 ) 109 110 // Program runs a sequence of float64 operations, with no explicit control-flow: 111 // implicit control-flow is available in the float64-only functions you make 112 // available to such programs. Such custom funcs must all return a float64, and 113 // either take from 0 to 5 float64 arguments, or a single float64 array. 114 // 115 // As the name suggests, don't create such objects directly, but instead use 116 // Compiler.Compile to create them. Only a Compiler lets you register variables 117 // and functions, which then become part of your numeric Program. 118 // 119 // A Program lets you change values before each run, using pointers from method 120 // Program.Get: such pointers are guaranteed never to change before or across 121 // runs. Just ensure you get a variable defined in the Compiler used to make the 122 // Program, or the pointer will be to a dummy place which has no effect on final 123 // results. 124 // 125 // Expressions using literals are automatically optimized into their results: 126 // this also applies to func calls with standard math functions and constants. 127 // 128 // The only way to limit such optimizations is to redefine common math funcs and 129 // const values explicitly when compiling: after doing so, all those value-names 130 // will stand for externally-updatable values which can change from one run to 131 // the next. Similarly, there's no guarantee the (re)defined functions will be 132 // deterministic, like the defaults they replaced. 133 // 134 // # Example 135 // 136 // var c fmscripts.Compiler 137 // 138 // defs := map[string]any{ 139 // "x": 0, // define `x`, and initialize it to 0 140 // "k": 4.25, // define `k`, and initialize it to 4.25 141 // "b": true, // define `b`, and initialize it to 1.0 142 // "n": -23, // define `n`, and initialize it to -23.0 143 // "pi": 3, // define `pi`, overriding the automatic constant named `pi` 144 // 145 // "f": numericKernel // type is func ([]float64) float64 146 // "g": otherFunc // type is func (float64) float64 147 // } 148 // 149 // prog, err := c.Compile("log10(k) + f(sqrt(k) * exp(-x), 45, -0.23)", defs) 150 // // ... 151 // 152 // x, _ := prog.Get("x") // Get returns (*float64, bool) 153 // y, _ := prog.Get("y") // a useless pointer, since program doesn't use `y` 154 // // ... 155 // 156 // for i := 0; i < n; i++ { 157 // *x = float64(i)*dx + minx // you update inputs in place using pointers 158 // f := prog.Run() // method Run gives you a float64 back 159 // // ... 160 // } 161 type Program struct { 162 sp int // stack pointer, even though it's an index 163 164 stack []float64 // pre-allocated by compiler to max length needed by program 165 values []float64 // holds all values, whether literals, or variables 166 167 ops []numOp // all sequential operations for each run 168 funcs []any // all funcs used by the program 169 170 names map[string]int // variable-name to index lookup 171 dummy float64 // all pointers for undefined variables point here 172 173 // data []float64 174 } 175 176 // Get lets you change parameters/variables before each time you run a program, 177 // since it doesn't return a value, but a pointer to it, so you can update it 178 // in place. 179 // 180 // If the name given isn't available, the result is a pointer to a dummy place: 181 // this ensures non-nil pointers, which are always safe to use, even though 182 // updates to the dummy destination have no effect on program results. 183 func (p *Program) Get(name string) (ptr *float64, useful bool) { 184 if i, ok := p.names[name]; ok { 185 return &p.values[i], true 186 } 187 return &p.dummy, false 188 } 189 190 // Clone creates an exact copy of a Program with all values in their current 191 // state: this is useful when dispatching embarassingly-parallel tasks to 192 // multiple programs. 193 func (p Program) Clone() Program { 194 // can't share the stack nor the values 195 stack := make([]float64, len(p.stack)) 196 values := make([]float64, len(p.values)) 197 copy(stack, p.stack) 198 copy(values, p.values) 199 p.stack = stack 200 p.values = values 201 202 // can share everything else as is 203 return p 204 } 205 206 // Memo: the command to show all bound checks is 207 // go test -gcflags="-d=ssa/check_bce/debug=1" fmscripts/programs.go 208 209 // Discussion about go compiler optimizing switch statements into jump tables 210 // https://go-review.googlesource.com/c/go/+/357330/ 211 212 // Run executes the program once. Before each run, update input values using 213 // pointers from method Get. 214 func (p *Program) Run() float64 { 215 // Check for empty programs: these happen either when a compilation error 216 // was ignored, or when a program was explicitly declared as a variable. 217 if len(p.ops) == 0 { 218 return math.NaN() 219 } 220 221 p.sp = 0 222 p.runAllOps() 223 return p.stack[p.sp] 224 } 225 226 type func4 = func(float64, float64, float64, float64) float64 227 type func5 = func(float64, float64, float64, float64, float64) float64 228 229 // runAllOps runs all operations in a loop: when done, the program's result is 230 // ready as the only item left in the stack 231 func (p *Program) runAllOps() { 232 for _, op := range p.ops { 233 // shortcut for the current stack pointer 234 sp := p.sp 235 236 // Preceding binary ops and func calls by _ = p.stack[i-n] prevents 237 // an extra bound check for the lhs of assignments, but a quick 238 // statistical summary of benchmarks doesn't show clear speedups, 239 // let alone major ones. 240 // 241 // Separating different func types into different arrays to avoid 242 // type-checking at runtime doesn't seem to be worth it either, 243 // and makes the compiler more complicated. 244 245 switch op.What { 246 case load: 247 // store above top of stack 248 p.stack[sp+1] = p.values[op.Index] 249 p.sp++ 250 case store: 251 // store from top of the stack 252 p.values[op.Index] = p.stack[sp] 253 p.sp-- 254 255 // unary operations 256 case neg: 257 p.stack[sp] = -p.stack[sp] 258 case not: 259 p.stack[sp] = deboolNot(p.stack[sp]) 260 case abs: 261 p.stack[sp] = math.Abs(p.stack[sp]) 262 case square: 263 p.stack[sp] *= p.stack[sp] 264 case rec: 265 p.stack[sp] = 1 / p.stack[sp] 266 267 // binary arithmetic ops 268 case add: 269 p.stack[sp-1] += p.stack[sp] 270 p.sp-- 271 case sub: 272 p.stack[sp-1] -= p.stack[sp] 273 p.sp-- 274 case mul: 275 p.stack[sp-1] *= p.stack[sp] 276 p.sp-- 277 case div: 278 p.stack[sp-1] /= p.stack[sp] 279 p.sp-- 280 case mod: 281 p.stack[sp-1] = math.Mod(p.stack[sp-1], p.stack[sp]) 282 p.sp-- 283 case pow: 284 p.stack[sp-1] = math.Pow(p.stack[sp-1], p.stack[sp]) 285 p.sp-- 286 287 // binary boolean ops / binary comparisons 288 case and: 289 p.stack[sp-1] = deboolAnd(p.stack[sp-1], p.stack[sp]) 290 p.sp-- 291 case or: 292 p.stack[sp-1] = deboolOr(p.stack[sp-1], p.stack[sp]) 293 p.sp-- 294 case equal: 295 p.stack[sp-1] = debool(p.stack[sp-1] == p.stack[sp]) 296 p.sp-- 297 case notequal: 298 p.stack[sp-1] = debool(p.stack[sp-1] != p.stack[sp]) 299 p.sp-- 300 case less: 301 p.stack[sp-1] = debool(p.stack[sp-1] < p.stack[sp]) 302 p.sp-- 303 case lessoreq: 304 p.stack[sp-1] = debool(p.stack[sp-1] <= p.stack[sp]) 305 p.sp-- 306 case more: 307 p.stack[sp-1] = debool(p.stack[sp-1] > p.stack[sp]) 308 p.sp-- 309 case moreoreq: 310 p.stack[sp-1] = debool(p.stack[sp-1] >= p.stack[sp]) 311 p.sp-- 312 313 // function calls 314 case call0: 315 f := p.funcs[op.Index].(func() float64) 316 // store above top of stack 317 p.stack[sp+1] = f() 318 p.sp++ 319 case call1: 320 f := p.funcs[op.Index].(func(float64) float64) 321 p.stack[sp] = f(p.stack[sp]) 322 case call2: 323 f := p.funcs[op.Index].(func(float64, float64) float64) 324 p.stack[sp-1] = f(p.stack[sp-1], p.stack[sp]) 325 p.sp-- 326 case call3: 327 f := p.funcs[op.Index].(func(float64, float64, float64) float64) 328 p.stack[sp-2] = f(p.stack[sp-2], p.stack[sp-1], p.stack[sp]) 329 p.sp -= 2 330 case call4: 331 f := p.funcs[op.Index].(func4) 332 st := p.stack 333 p.stack[sp-3] = f(st[sp-3], st[sp-2], st[sp-1], st[sp]) 334 p.sp -= 3 335 case call5: 336 f := p.funcs[op.Index].(func5) 337 st := p.stack 338 p.stack[sp-4] = f(st[sp-4], st[sp-3], st[sp-2], st[sp-1], st[sp]) 339 p.sp -= 4 340 case callv: 341 i := sp - int(op.NumArgs) + 1 342 f := p.funcs[op.Index].(func(...float64) float64) 343 p.stack[sp-i+1] = f(p.stack[i : sp+1]...) 344 p.sp = sp - i + 1 345 case call1v: 346 i := sp - int(op.NumArgs) + 1 347 f := p.funcs[op.Index].(func(float64, ...float64) float64) 348 p.stack[sp-i+1] = f(p.stack[i], p.stack[i+1:sp+1]...) 349 p.sp = sp - i + 1 350 } 351 } 352 } 353 354 // debool is only used to turn boolean values used in comparison operations 355 // into float64s, since those are the only type accepted on a program stack 356 func debool(b bool) float64 { 357 if b { 358 return 1 359 } 360 return 0 361 } 362 363 // deboolNot runs the basic `not` operation 364 func deboolNot(x float64) float64 { 365 return debool(x == 0) 366 } 367 368 // deboolAnd runs the basic `and` operation 369 func deboolAnd(x, y float64) float64 { 370 return debool(x != 0 && y != 0) 371 } 372 373 // deboolOr runs the basic `or` operation 374 func deboolOr(x, y float64) float64 { 375 return debool(x != 0 || y != 0) 376 } File: fmscripts/programs_test.go 1 package fmscripts 2 3 import "testing" 4 5 func TestCallVarFuncs(t *testing.T) { 6 tests := []struct { 7 name string 8 src string 9 exp float64 10 }{ 11 {"check 1 var arg", "numargs(34)", 1}, 12 {"check 2 var arg", "numargs(34, 33)", 2}, 13 {"check 3 var arg", "numargs(34, 322, 0.3)", 3}, 14 {"check 4 var arg", "numargs(34, -1, 553, 42)", 4}, 15 {"check 5 var arg", "numargs(34, 3, 4, 5, 1)", 5}, 16 } 17 18 numargs := func(args ...float64) float64 { return float64(len(args)) } 19 20 for _, tc := range tests { 21 t.Run(tc.name, func(t *testing.T) { 22 var c Compiler 23 p, err := c.Compile(tc.src, map[string]any{ 24 "numargs": numargs, 25 }) 26 if err != nil { 27 t.Fatal(err) 28 return 29 } 30 31 got := p.Run() 32 const fs = "failed check (var-arg): expected %f, got %f instead" 33 if got != tc.exp { 34 t.Fatalf(fs, tc.exp, got) 35 return 36 } 37 }) 38 } 39 } File: fmscripts/random.go 1 package fmscripts 2 3 import ( 4 "math" 5 "math/rand" 6 ) 7 8 // These funcs are kept separate from the larger lookup table so they aren't 9 // mistaken for deterministic funcs which can be optimized away. 10 // 11 // var randomFuncs = map[string]any{ 12 // "rand": Random, 13 // "rint": RandomInt, 14 // "runif": RandomUnif, 15 // "rexp": RandomExp, 16 // "rnorm": RandomNorm, 17 // "rgamma": RandomGamma, 18 // "rbeta": RandomBeta, 19 // } 20 21 func Random(r *rand.Rand) float64 { 22 return r.Float64() 23 } 24 25 func RandomInt(r *rand.Rand, min, max float64) float64 { 26 fmin := math.Trunc(min) 27 fmax := math.Trunc(max) 28 if fmin == fmax { 29 return fmin 30 } 31 32 diff := math.Abs(fmax - fmin) 33 return float64(r.Intn(int(diff)+1)) + fmin 34 } 35 36 func RandomUnif(r *rand.Rand, min, max float64) float64 { 37 return (max-min)*r.Float64() + min 38 } 39 40 func RandomExp(r *rand.Rand, scale float64) float64 { 41 return scale * r.ExpFloat64() 42 } 43 44 func RandomNorm(r *rand.Rand, mu, sigma float64) float64 { 45 return sigma*r.NormFloat64() + mu 46 } 47 48 // Gamma generates a gamma-distributed real value, using a scale parameter. 49 // 50 // The algorithm is from Marsaglia and Tsang, as described in 51 // 52 // A simple method for generating gamma variables 53 // https://dl.acm.org/doi/10.1145/358407.358414 54 func RandomGamma(r *rand.Rand, scale float64) float64 { 55 d := scale - 1.0/3.0 56 c := 1 / math.Sqrt(9/d) 57 58 for { 59 // generate candidate value 60 var x, v float64 61 for { 62 x = r.NormFloat64() 63 v = 1 + c*x 64 if v > 0 { 65 break 66 } 67 } 68 v = v * v * v 69 70 // accept or reject candidate value 71 x2 := x * x 72 u := r.Float64() 73 if u < 1-0.0331*x2*x2 { 74 return d * v 75 } 76 if math.Log(u) < 0.5*x2+d*(1-v+math.Log(v)) { 77 return d * v 78 } 79 } 80 } 81 82 // Beta generates a beta-distributed real value. 83 func RandomBeta(r *rand.Rand, a, b float64) float64 { 84 return RandomGamma(r, a) / (RandomGamma(r, a) + RandomGamma(r, b)) 85 } File: fmscripts/tokens.go 1 package fmscripts 2 3 import ( 4 "errors" 5 "fmt" 6 "strings" 7 "unicode" 8 "unicode/utf8" 9 ) 10 11 // tokenType is the specific type of a token; tokens never represent 12 // whitespace-like text between recognized tokens 13 type tokenType int 14 15 const ( 16 // default zero-value type for tokens 17 unknownToken tokenType = iota 18 19 // a name 20 identifierToken tokenType = iota 21 22 // a literal numeric value 23 numberToken tokenType = iota 24 25 // any syntactic element made of 1 or more runes 26 syntaxToken tokenType = iota 27 ) 28 29 // errEOS signals the end of source code, and is the only token-related error 30 // which the parser should ignore 31 var errEOS = errors.New(`no more source code`) 32 33 // token is either a name, value, or syntactic element coming from a script's 34 // source code 35 type token struct { 36 kind tokenType 37 value string 38 line int 39 pos int 40 } 41 42 // tokenizer splits a string into a stream tokens, via its `next` method 43 type tokenizer struct { 44 cur string 45 linenum int 46 linepos int 47 } 48 49 // newTokenizer is the constructor for type tokenizer 50 func newTokenizer(src string) tokenizer { 51 return tokenizer{ 52 cur: src, 53 linenum: 1, 54 linepos: 1, 55 } 56 } 57 58 // next advances the tokenizer, giving back a token, unless it's done 59 func (t *tokenizer) next() (token, error) { 60 // label to allow looping back after skipping comments, and thus avoid 61 // an explicit tail-recursion for each commented line 62 rerun: 63 64 // always ignore any whitespace-like source 65 if err := t.skipWhitespace(); err != nil { 66 return token{}, err 67 } 68 69 if len(t.cur) == 0 { 70 return token{}, errEOS 71 } 72 73 // remember starting position, in case of error 74 line := t.linenum 75 pos := t.linepos 76 77 // use the leading rune to probe what's next 78 r, _ := utf8.DecodeRuneInString(t.cur) 79 80 switch r { 81 case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9': 82 s, err := t.scanNumber() 83 return token{kind: numberToken, value: s, line: line, pos: pos}, err 84 85 case '(', ')', '[', ']', '{', '}', ',', '+', '-', '%', '^', '~', '@', ';': 86 s := t.cur[:1] 87 t.cur = t.cur[1:] 88 t.linepos++ 89 res := token{kind: syntaxToken, value: s, line: line, pos: pos} 90 return res, t.eos() 91 92 case ':': 93 s, err := t.tryPrefixes(`:=`, `:`) 94 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 95 96 case '*': 97 s, err := t.tryPrefixes(`**`, `*`) 98 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 99 100 case '/': 101 s, err := t.tryPrefixes(`//`, `/*`, `/`) 102 // double-slash starts a comment until the end of the line 103 if s == `//` { 104 t.skipLine() 105 goto rerun 106 } 107 // handle comments which can span multiple lines 108 if s == `/*` { 109 err := t.skipComment() 110 if err != nil { 111 return token{}, err 112 } 113 goto rerun 114 } 115 // handle division 116 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 117 118 case '#': 119 // even hash starts a comment until the end of the line, making the 120 // syntax more Python-like 121 t.skipLine() 122 goto rerun 123 124 case '&': 125 s, err := t.tryPrefixes(`&&`, `&`) 126 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 127 128 case '|': 129 s, err := t.tryPrefixes(`||`, `|`) 130 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 131 132 case '?': 133 s, err := t.tryPrefixes(`??`, `?.`, `?`) 134 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 135 136 case '.': 137 r, _ := utf8.DecodeRuneInString(t.cur[1:]) 138 if '0' <= r && r <= '9' { 139 s, err := t.scanNumber() 140 res := token{kind: numberToken, value: s, line: line, pos: pos} 141 return res, err 142 } 143 s, err := t.tryPrefixes(`...`, `..`, `.?`, `.`) 144 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 145 146 case '=': 147 // triple-equal makes the syntax even more JavaScript-like 148 s, err := t.tryPrefixes(`===`, `==`, `=>`, `=`) 149 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 150 151 case '!': 152 // not-double-equal makes the syntax even more JavaScript-like 153 s, err := t.tryPrefixes(`!==`, `!=`, `!`) 154 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 155 156 case '<': 157 // the less-more/diamond syntax is a SQL-like way to say not equal 158 s, err := t.tryPrefixes(`<=`, `<>`, `<`) 159 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 160 161 case '>': 162 s, err := t.tryPrefixes(`>=`, `>`) 163 return token{kind: syntaxToken, value: s, line: line, pos: pos}, err 164 165 default: 166 if isIdentStartRune(r) { 167 s, err := t.scanIdentifier() 168 res := token{kind: identifierToken, value: s, line: line, pos: pos} 169 return res, err 170 } 171 const fs = `line %d: pos %d: unexpected symbol %c` 172 return token{}, fmt.Errorf(fs, t.linenum, t.linepos, r) 173 } 174 } 175 176 // tryPrefixes tries to greedily match any prefix in the order given: when all 177 // candidates fail, an empty string is returned; when successful, the tokenizer 178 // updates its state to account for the matched prefix 179 func (t *tokenizer) tryPrefixes(prefixes ...string) (string, error) { 180 for _, pre := range prefixes { 181 if strings.HasPrefix(t.cur, pre) { 182 t.linepos += len(pre) 183 t.cur = t.cur[len(pre):] 184 return pre, t.eos() 185 } 186 } 187 188 return ``, t.eos() 189 } 190 191 // skipWhitespace updates the tokenizer to ignore runs of consecutive whitespace 192 // symbols: these are the likes of space, tab, newline, carriage return, etc. 193 func (t *tokenizer) skipWhitespace() error { 194 for len(t.cur) > 0 { 195 r, size := utf8.DecodeRuneInString(t.cur) 196 if !unicode.IsSpace(r) { 197 // no more spaces to skip 198 return nil 199 } 200 201 t.cur = t.cur[size:] 202 if r == '\n' { 203 // reached the next line 204 t.linenum++ 205 t.linepos = 1 206 continue 207 } 208 // continuing on the same line 209 t.linepos++ 210 } 211 212 // source code ended 213 return errEOS 214 } 215 216 // skipLine updates the tokenizer to the end of the current line, or the end of 217 // the source code, if it's the last line 218 func (t *tokenizer) skipLine() error { 219 for len(t.cur) > 0 { 220 r, size := utf8.DecodeRuneInString(t.cur) 221 t.cur = t.cur[size:] 222 if r == '\n' { 223 // reached the next line, as expected 224 t.linenum++ 225 t.linepos = 1 226 return nil 227 } 228 } 229 230 // source code ended 231 t.linenum++ 232 t.linepos = 1 233 return errEOS 234 } 235 236 // skipComment updates the tokenizer to the end of the comment started with a 237 // `/*` and ending with a `*/`, or to the end of the source code 238 func (t *tokenizer) skipComment() error { 239 var prev rune 240 for len(t.cur) > 0 { 241 r, size := utf8.DecodeRuneInString(t.cur) 242 t.cur = t.cur[size:] 243 244 if r == '\n' { 245 t.linenum++ 246 t.linepos = 1 247 } else { 248 t.linepos++ 249 } 250 251 if prev == '*' && r == '/' { 252 return nil 253 } 254 prev = r 255 } 256 257 // source code ended 258 const msg = "comment not ended with a `*/` sequence" 259 return errors.New(msg) 260 } 261 262 func (t *tokenizer) scanIdentifier() (string, error) { 263 end := 0 264 for len(t.cur) > 0 { 265 r, size := utf8.DecodeRuneInString(t.cur[end:]) 266 if (end == 0 && !isIdentStartRune(r)) || !isIdentRestRune(r) { 267 // identifier ended, and there's more source code after it 268 name := t.cur[:end] 269 t.cur = t.cur[end:] 270 return name, nil 271 } 272 end += size 273 t.linepos++ 274 } 275 276 // source code ended with an identifier name 277 name := t.cur 278 t.cur = `` 279 return name, nil 280 } 281 282 func (t *tokenizer) scanNumber() (string, error) { 283 dots := 0 284 end := 0 285 var prev rune 286 287 for len(t.cur) > 0 { 288 r, size := utf8.DecodeRuneInString(t.cur[end:]) 289 290 switch r { 291 case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '_', 'e': 292 end += size 293 t.linepos++ 294 prev = r 295 296 case '+', '-': 297 if end > 0 && prev != 'e' { 298 // number ended, and there's more source code after it 299 num := t.cur[:end] 300 t.cur = t.cur[end:] 301 return num, nil 302 } 303 end += size 304 t.linepos++ 305 prev = r 306 307 case '.': 308 nr, _ := utf8.DecodeRuneInString(t.cur[end+size:]) 309 if dots == 1 || isIdentStartRune(nr) || unicode.IsSpace(nr) || nr == '.' { 310 // number ended, and there's more source code after it 311 num := t.cur[:end] 312 t.cur = t.cur[end:] 313 return num, nil 314 } 315 dots++ 316 end += size 317 t.linepos++ 318 prev = r 319 320 default: 321 // number ended, and there's more source code after it 322 num := t.cur[:end] 323 t.cur = t.cur[end:] 324 return num, nil 325 } 326 } 327 328 // source code ended with a number 329 name := t.cur 330 t.cur = `` 331 return name, nil 332 } 333 334 // eos checks if the source-code is over: if so, it returns an end-of-file error, 335 // or a nil error otherwise 336 func (t *tokenizer) eos() error { 337 if len(t.cur) == 0 { 338 return errEOS 339 } 340 return nil 341 } 342 343 func isIdentStartRune(r rune) bool { 344 return ('A' <= r && r <= 'Z') || ('a' <= r && r <= 'z') || r == '_' 345 } 346 347 func isIdentRestRune(r rune) bool { 348 return isIdentStartRune(r) || ('0' <= r && r <= '9') 349 } File: fmscripts/tokens_test.go 1 package fmscripts 2 3 import ( 4 "reflect" 5 "testing" 6 ) 7 8 func TestTokenizer(t *testing.T) { 9 var tests = []struct { 10 Script string 11 Tokens []string 12 }{ 13 {``, nil}, 14 {`3.`, []string{`3.`}}, 15 {`3.2`, []string{`3.2`}}, 16 {`-3.2`, []string{`-`, `3.2`}}, 17 {`-3.2+56`, []string{`-`, `3.2`, `+`, `56`}}, 18 } 19 20 for _, tc := range tests { 21 t.Run(tc.Script, func(t *testing.T) { 22 tok := newTokenizer(tc.Script) 23 par, err := newParser(&tok) 24 if err != nil { 25 t.Fatal(err) 26 return 27 } 28 29 var got []string 30 for _, v := range par.tokens { 31 got = append(got, v.value) 32 } 33 34 if !reflect.DeepEqual(got, tc.Tokens) { 35 const fs = "from %s\nexpected\n%#v\nbut got\n%#v\ninstead" 36 t.Fatalf(fs, tc.Script, tc.Tokens, got) 37 return 38 } 39 }) 40 } 41 }