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/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 }