1/*
2mondo.test.mjs - <short description TODO>
3Copyright (C) 2022 Strudel contributors - see <https://github.com/tidalcycles/strudel/blob/main/packages/mini/test/mini.test.mjs>
4This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program.  If not, see <https://www.gnu.org/licenses/>.
5*/
6
7import { describe, expect, it } from 'vitest';
8import { MondoParser, printAst, MondoRunner } from '../mondo.mjs';
9
10const parser = new MondoParser();
11const p = (code) => parser.parse(code, -1);
12
13describe('mondo tokenizer', () => {
14  const parser = new MondoParser();
15  it('should tokenize with locations', () =>
16    expect(
17      parser
18        .tokenize('(one two three)')
19        .map((t) => t.value + '=' + t.loc.join('-'))
20        .join(' '),
21    ).toEqual('(=0-1 one=1-4 two=5-8 three=9-14 )=14-15'));
22  // it('should parse with loangleions', () => expect(parser.parse('(one two three)')).toEqual());
23  it('should get loangleions', () =>
24    expect(parser.get_locations('s bd rim')).toEqual([
25      [0, 1],
26      [2, 4],
27      [5, 8],
28    ]));
29});
30describe('mondo s-expressions parser', () => {
31  it('should parse an empty string', () => expect(p('')).toEqual({ type: 'list', children: [] }));
32  it('should parse a single item', () =>
33    expect(p('a')).toEqual({ type: 'list', children: [{ type: 'plain', value: 'a' }] }));
34  it('should parse an empty list', () => expect(p('()')).toEqual({ type: 'list', children: [] }));
35  it('should parse a list with 1 item', () =>
36    expect(p('(a)')).toEqual({ type: 'list', children: [{ type: 'plain', value: 'a' }] }));
37  it('should parse a list with 2 items', () =>
38    expect(p('(a b)')).toEqual({
39      type: 'list',
40      children: [
41        { type: 'plain', value: 'a' },
42        { type: 'plain', value: 'b' },
43      ],
44    }));
45  it('should parse a list with 2 items', () =>
46    expect(p('(a (b c))')).toEqual({
47      type: 'list',
48      children: [
49        { type: 'plain', value: 'a' },
50        {
51          type: 'list',
52          children: [
53            { type: 'plain', value: 'b' },
54            { type: 'plain', value: 'c' },
55          ],
56        },
57      ],
58    }));
59  it('should parse numbers', () =>
60    expect(p('(1 .2 1.2 10 22.3)')).toEqual({
61      type: 'list',
62      children: [
63        { type: 'number', value: '1' },
64        { type: 'number', value: '.2' },
65        { type: 'number', value: '1.2' },
66        { type: 'number', value: '10' },
67        { type: 'number', value: '22.3' },
68      ],
69    }));
70  it('should parse comments', () =>
71    expect(p('a // hello')).toEqual({
72      type: 'list',
73      children: [
74        { type: 'plain', value: 'a' },
75        { type: 'comment', value: '// hello' },
76      ],
77    }));
78});
79
80let desguar = (a) => {
81  return printAst(parser.parse(a), true);
82};
83
84describe('mondo sugar', () => {
85  it('should desugar []', () => expect(desguar('[a b c]')).toEqual('(square a b c)'));
86  it('should desugar [] nested', () => expect(desguar('[a [b c] d]')).toEqual('(square a (square b c) d)'));
87  it('should desugar <>', () => expect(desguar('<a b c>')).toEqual('(angle a b c)'));
88  it('should desugar <> nested', () => expect(desguar('<a <b c> d>')).toEqual('(angle a (angle b c) d)'));
89  it('should desugar mixed [] <>', () => expect(desguar('[a <b c>]')).toEqual('(square a (angle b c))'));
90  it('should desugar mixed <> []', () => expect(desguar('<a [b c]>')).toEqual('(angle a (square b c))'));
91
92  it('should desugar #', () => expect(desguar('s jazz # fast 2')).toEqual('(fast 2 (s jazz))'));
93  it('should desugar # square', () => expect(desguar('[bd cp # fast 2]')).toEqual('(fast 2 (square bd cp))'));
94  it('should desugar # twice', () => expect(desguar('s jazz # fast 2 # slow 2')).toEqual('(slow 2 (fast 2 (s jazz)))'));
95  it('should desugar # nested', () => expect(desguar('(s cp # fast 2)')).toEqual('(fast 2 (s cp))'));
96  it('should desugar # within []', () => expect(desguar('[bd cp # fast 2]')).toEqual('(fast 2 (square bd cp))'));
97  it('should desugar # within , within []', () =>
98    expect(desguar('[bd cp # fast 2, x]')).toEqual('(stack (fast 2 (square bd cp)) x)'));
99
100  // it('should desugar .(.', () => expect(desguar('[jazz hh.(.fast 2)]')).toEqual('(square jazz (fast 2 hh))'));
101
102  it('should desugar , |', () => expect(desguar('[bd, hh | oh]')).toEqual('(stack bd (or hh oh))'));
103  it('should desugar , | of []', () =>
104    expect(desguar('[bd, hh | [oh rim]]')).toEqual('(stack bd (or hh (square oh rim)))'));
105  it('should desugar , square', () => expect(desguar('[bd, hh]')).toEqual('(stack bd hh)'));
106  it('should desugar , square 2', () => expect(desguar('[bd, hh oh]')).toEqual('(stack bd (square hh oh))'));
107  it('should desugar , square 3', () =>
108    expect(desguar('[bd cp, hh oh]')).toEqual('(stack (square bd cp) (square hh oh))'));
109  it('should desugar , angle', () => expect(desguar('<bd, hh>')).toEqual('(stack bd hh)'));
110  it('should desugar , angle 2', () => expect(desguar('<bd, hh oh>')).toEqual('(stack bd (angle hh oh))'));
111  it('should desugar , angle 3', () =>
112    expect(desguar('<bd cp, hh oh>')).toEqual('(stack (angle bd cp) (angle hh oh))'));
113  it('should desugar , ()', () => expect(desguar('(s bd, s cp)')).toEqual('(stack (s bd) (s cp))'));
114  it('should desugar * /', () => expect(desguar('[a b*2 c d/3 e]')).toEqual('(square a (* 2 b) c (/ 3 d) e)'));
115  it('should desugar []*x', () => expect(desguar('[a [b c]*3]')).toEqual('(square a (* 3 (square b c)))'));
116  it('should desugar []*<x y>', () => expect(desguar('[a b*<2 3> c]')).toEqual('(square a (* (angle 2 3) b) c)'));
117  it('should desugar x:y', () => expect(desguar('x:y')).toEqual('(: y x)'));
118  it('should desugar x:y:z', () => expect(desguar('x:y:z')).toEqual('(: z (: y x))'));
119  it('should desugar x:y*x', () => expect(desguar('bd:0*2')).toEqual('(* 2 (: 0 bd))'));
120  it('should desugar x&y:z', () => expect(desguar('bd&3:8')).toEqual('(& (: 8 3) bd)'));
121  it('should desugar a..b', () => expect(desguar('0..2')).toEqual('(.. 2 0)'));
122  /* it('should desugar x $ y', () => expect(desguar('x $ y')).toEqual('(x y)'));
123  it('should desugar x $ y z', () => expect(desguar('x $ y z')).toEqual('(x (y z))'));
124  it('should desugar x $ y . z', () => expect(desguar('x $ y . z')).toEqual('(z (x y))')); */
125
126  it('should desugar README example', () =>
127    expect(desguar('s [bd hh*2 (cp # crush 4) <mt ht lt>] # speed .8')).toEqual(
128      '(speed .8 (s (square bd (* 2 hh) (crush 4 cp) (angle mt ht lt))))',
129    ));
130
131  it('should desugar (#)', () => expect(desguar('(#)')).toEqual('(fn (_) _)'));
132  it('should desugar lambda', () => expect(desguar('(# fast 2)')).toEqual('(fn (_) (fast 2 _))'));
133  it('should desugar lambda call', () => expect(desguar('((# mul 2) 2)')).toEqual('((fn (_) (mul 2 _)) 2)'));
134  it('should desugar lambda with pipe', () =>
135    expect(desguar('(# fast 2 # room 1)')).toEqual('(fn (_) (room 1 (fast 2 _)))'));
136  /* const lambda = parser.parse('(lambda (_) (fast 2 _))');
137  const target = { type: 'plain', value: 'xyz' };
138  it('should desugar_lambda', () =>
139    expect(printAst(parser.desugar_lambda(lambda.children, target))).toEqual('(fast 2 xyz)')); */
140});
141
142describe('mondo arithmetic', () => {
143  let multi =
144    (op) =>
145    (init, ...rest) =>
146      rest.reduce((acc, arg) => op(acc, arg), init);
147
148  let lib = {
149    '+': multi((a, b) => a + b),
150    add: multi((a, b) => a + b),
151    '-': multi((a, b) => a - b),
152    sub: multi((a, b) => a - b),
153    '*': multi((a, b) => a * b),
154    '/': multi((a, b) => a / b),
155    mod: multi((a, b) => a % b),
156    eq: (a, b) => a === b,
157    lt: (a, b) => a < b,
158    gt: (a, b) => a > b,
159    and: (a, b) => a && b,
160    or: (a, b) => a || b,
161    not: (a) => !a,
162    run: (...args) => args[args.length - 1],
163    def: () => 0,
164    sin: Math.sin,
165    cos: Math.cos,
166    PI: Math.PI,
167    cons: (a, b) => [a, ...(Array.isArray(b) ? b : [b])],
168    car: (pair) => pair[0],
169    cdr: (pair) => pair.slice(1),
170    list: (...items) => items,
171    nil: [],
172    isnull: (items) => items.length === 0,
173    concat: (...msgs) => msgs.join(''),
174    error: (...msgs) => {
175      throw new Error(msgs.join(' '));
176    },
177  };
178  function evaluator(node, scope) {
179    if (node.type !== 'list') {
180      // is leaf
181      return scope[node.value] ?? lib[node.value] ?? node.value;
182    }
183    // is list
184    const [fn, ...args] = node.children;
185    if (typeof fn !== 'function') {
186      throw new Error(`"${fn}": expected function, got ${typeof fn} "${fn}"`);
187    }
188    return fn(...args);
189  }
190  const runner = new MondoRunner({ evaluator });
191  let evaluate = (exp, scope) => runner.run(`run ${exp}`, scope);
192  let pretty = (exp) => printAst(runner.parser.parse(exp), false);
193  //it('should eval nested expression', () => expect(runner.run('add 1 (mul 2 PI)').toFixed(2)).toEqual('7.28'));
194
195  it('eval number', () => expect(evaluate('2')).toEqual(2));
196  it('eval string', () => expect(evaluate('abc')).toEqual('abc'));
197  it('eval list', () => expect(evaluate('(+ 1 2)')).toEqual(3));
198  it('eval nested list', () => expect(evaluate('(+ 1 (+ 2 3))')).toEqual(6));
199  it('def number', () => expect(evaluate('(def a 2) a')).toEqual(2));
200  it('def + ref number', () => expect(evaluate('(def a 2) (* a a)')).toEqual(4));
201  it('def + call lambda', () => expect(evaluate('(def sqr (fn (x) (* x x))) (sqr 3)')).toEqual(9));
202
203  // sicp
204  it('sicp 8.1', () => expect(evaluate('(+ 137 349)')).toEqual(486));
205  it('sicp 8.2', () => expect(evaluate('(- 1000 334)')).toEqual(666));
206  it('sicp 8.3', () => expect(evaluate('(* 5 99)')).toEqual(495));
207  it('sicp 8.4', () => expect(evaluate('(/ 10 5)')).toEqual(2));
208  it('sicp 8.5', () => expect(evaluate('(+ 2.7 10)')).toEqual(12.7));
209  it('sicp 9.1', () => expect(evaluate('(+ 21 35 12 7)')).toEqual(75));
210  it('sicp 9.2', () => expect(evaluate('(* 25 4 12)')).toEqual(1200));
211  it('sicp 9.3', () => expect(evaluate('(+ (* 3 5) (- 10 6))')).toEqual(19));
212  it('sicp 9.4', () =>
213    expect(pretty('(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))')).toEqual(`(+ 
214 (* 3 
215  (+ 
216   (* 2 4) 
217   (+ 3 5)
218  )
219 ) 
220 (+ 
221  (- 10 7) 6
222 )
223)`)); // this is not exactly pretty printing by convention..
224
225  let scope = {};
226  it('sicp 11.1', () => expect(evaluate('(def size 2) (* 5 size)', scope)).toEqual(10));
227  it('sicp 11.2', () =>
228    expect(evaluate('(def pi 3.14159) (def radius 10) (* pi (* radius radius))', scope)).toEqual(314.159));
229  it('sicp 11.3', () => expect(evaluate('(def circumference (* 2 pi radius))', scope)).toEqual(0));
230  it('sicp 11.4', () => expect(evaluate('circumference', scope)).toEqual(62.8318));
231  it('sicp 13.1', () => expect(evaluate('(* (+ 2 (* 4 6)) (+ 3 5 7))')).toEqual(390));
232  it('sicp 16.1', () => expect(evaluate('(def (square x) (* x x))', scope)).toEqual(0));
233  // it('sicp 16.1', () => expect(evaluate('(def (square x) (* x x))', scope)).toEqual(0));
234  it('sicp 17.1', () => expect(evaluate('(square 21)', scope)).toEqual(441));
235  it('sicp 17.2', () => expect(evaluate('(square (+ 2 5))', scope)).toEqual(49));
236  it('sicp 17.3', () => expect(evaluate('(square (square 3))', scope)).toEqual(81));
237  it('sicp 17.4', () => expect(evaluate(`(def (sumofsquares x y) (+ (square x) (square y)))`, scope)).toEqual(0));
238  it('sicp 17.5', () => expect(evaluate(`(sumofsquares 3 4)`, scope)).toEqual(25));
239  it('sicp 17.6', () => expect(evaluate(`(def (f a) (sumofsquares (+ a 1) (* a 2))) (f 5)`, scope)).toEqual(136));
240  it('sicp 21.1', () => expect(evaluate(`(sumofsquares (+ 5 1) (* 5 2))`, scope)).toEqual(136));
241
242  it('sicp 22.1', () =>
243    expect(
244      evaluate(
245        `(def (abs x) 
246        (match 
247         ((gt x 0) x) 
248         ((eq x 0) 0)
249         ((lt x 0) (- 0 x))
250      ))`, // sicp was doing (- x), which doesnt work with our -
251        scope,
252      ),
253    ).toEqual(0));
254
255  it('sicp gt1', () => expect(evaluate(`(gt -12 0)`, scope)).toEqual(false));
256  it('sicp gt2', () => expect(evaluate(`(gt 0 -12)`, scope)).toEqual(true));
257  it('sicp lt1', () => expect(evaluate(`(lt -12 0)`, scope)).toEqual(true));
258  it('sicp lt2', () => expect(evaluate(`(lt 0 -12)`, scope)).toEqual(false));
259
260  it('sicp 24.1', () => expect(evaluate(`(abs (- 3))`, scope)).toEqual(3));
261  it('sicp 24.2', () => expect(evaluate(`(abs (+ 3))`, scope)).toEqual(3));
262  it('sicp 24.3', () => expect(evaluate(`(abs -12)`, scope)).toEqual(12));
263
264  it('sicp 24.4', () => expect(evaluate(`(def (abs x) (if (lt x 0) (- 0 x) x))`, scope)).toEqual(0));
265  it('sicp 24.5', () => expect(evaluate(`(abs -13)`, scope)).toEqual(13));
266  it('sicp 25.1', () => expect(evaluate(`(and (gt 6 5) (lt 6 10))`, scope)).toEqual(true));
267  it('sicp 25.2', () => expect(evaluate(`(and (gt 4 5) (lt 6 10))`, scope)).toEqual(false));
268
269  it('sicp ex1.1.1', () => expect(evaluate(`(def a 3)`, scope)).toEqual(0));
270  it('sicp ex1.1.2', () => expect(evaluate(`(def b (+ a 1))`, scope)).toEqual(0));
271  it('sicp ex1.1.3', () => expect(evaluate(`(+ a b (* a b))`, scope)).toEqual(19));
272  it('sicp ex1.1.4', () => expect(evaluate(`(if (and (gt b a) (lt b (* a b))) b a)`, scope)).toEqual(4));
273  it('sicp ex1.1.5', () => expect(evaluate(`(match ((eq a 4) 6) ((eq b 4) (+ 6 7 a)) (else 25))`, scope)).toEqual(16));
274  it('sicp ex1.1.6', () => expect(evaluate(`(+ 2 (if (gt b a) b a))`, scope)).toEqual(6));
275  it('sicp ex1.1.7', () =>
276    expect(evaluate(`(* (match ((gt a b) a) ((lt a b) b) (else -1)) (+ a 1))`, scope)).toEqual(16));
277
278  // .. cant use "+" and "-" as standalone expressions, because they are parsed as operators...
279  it('sicp ex1.4.1', () => expect(evaluate(`(def (foo a b) ((if (gt b 0) add sub) a b))`, scope)).toEqual(0));
280  it('sicp ex1.4.1', () => expect(evaluate(`(foo 3 1)`, scope)).toEqual(4));
281  it('sicp ex1.4.2', () => expect(evaluate(`(foo 3 -1)`, scope)).toEqual(4));
282
283  // 1.1.7 Example: Square Roots by Newton’s Method
284  it('sicp 30.1', () =>
285    expect(evaluate(`(def (goodenuf guess x) (lt (abs (- (square guess) x)) 0.001))`, scope)).toEqual(0));
286  it('sicp 30.2', () => expect(evaluate(`(goodenuf 1 1.001)`, scope)).toEqual(true));
287  it('sicp 30.3', () => expect(evaluate(`(goodenuf 1 1.002)`, scope)).toEqual(false));
288  it('sicp 30.4', () => expect(evaluate(`(def (average x y) (/ (+ x y) 2))`, scope)).toEqual(0));
289  it('sicp 30.5', () => expect(evaluate(`(average 18 20)`, scope)).toEqual(19));
290  it('sicp 30.6', () => expect(evaluate(`(def (improve guess x) (average guess (/ x guess)))`, scope)).toEqual(0));
291  it('sicp 31.1', () =>
292    expect(
293      evaluate(
294        `(def (sqrtiter guess x) (if (goodenuf guess x)
295      guess
296      (sqrtiter (improve guess x) x)))`,
297        scope,
298      ),
299    ).toEqual(0));
300  it('sicp 31.2', () => expect(evaluate(`(def (sqrt x) (sqrtiter 1.0 x))`, scope)).toEqual(0));
301  it('sicp 31.3', () => expect(evaluate(`(sqrt 9)`, scope)).toEqual(3.00009155413138));
302  it('sicp 31.4', () => expect(evaluate(`(sqrt (+ 100 37))`, scope)).toEqual(11.704699917758145));
303  // eslint-disable-next-line no-loss-of-precision
304  it('sicp 31.5', () => expect(evaluate(`(sqrt (+ (sqrt 2) (sqrt 3)))`, scope)).toEqual(1.77392790232078925));
305  it('sicp 31.6', () => expect(evaluate(`(square (sqrt 1000))`, scope)).toEqual(1000.000369924366));
306
307  // lexical scoping
308  it('sicp 39.1', () =>
309    expect(
310      evaluate(
311        `
312(def (sqrt x)
313 (def (goodenough guess)
314  (lt (abs (- (square guess) x)) 0.001)) 
315(def (improve guess)
316 (average guess (/ x guess))) 
317(def (sqrt-iter guess)
318 (if (goodenough guess) guess (sqrt-iter (improve guess))))
319(sqrtiter 1.0))
320  
321  `,
322        scope,
323      ),
324    ).toEqual(0));
325
326  // recursive fac
327  it('sicp 41.1', () => expect(evaluate(`(def (fac n) (if (eq n 1) 1 (* n (fac (- n 1)))))`, scope)).toEqual(0));
328  it('sicp 41.2', () => expect(evaluate(`(fac 4)`, scope)).toEqual(24));
329
330  // iterative fac
331  it('sicp 41.3', () =>
332    expect(
333      evaluate(
334        `
335(def (factorial n) (factiter 1 1 n))
336(def (factiter product counter maxcount) 
337 (if (gt counter maxcount)
338  product
339  (factiter (* counter product)
340             (+ counter 1)
341             maxcount)))
342`,
343        scope,
344      ),
345    ).toEqual(0));
346  it('sicp 41.4', () => expect(evaluate(`(fac 4)`, scope)).toEqual(24));
347
348  // 46.1
349  /* (def (+ a b)
350(if (= a 0) b (inc (+ (dec a) b))))
351(def (+ a b)
352(if (= a 0) b (+ (dec a) (inc b)))) */
353
354  // Exercise 1.10
355  //  Ackermann’s function
356  it('sicp 47.1', () =>
357    expect(
358      evaluate(
359        `
360(def (A x y) (match ((eq y 0) 0) 
361((eq x 0) (* 2 y))
362((eq y 1) 2)
363(else (A (- x 1) (A x (- y 1))))))
364`,
365        scope,
366      ),
367    ).toEqual(0));
368  it('sicp 47.2', () => expect(evaluate(`(A 1 10)`, scope)).toEqual(1024));
369  it('sicp 47.3', () => expect(evaluate(`(A 2 4)`, scope)).toEqual(65536));
370  it('sicp 47.4', () => expect(evaluate(`(A 3 3)`, scope)).toEqual(65536));
371  it('sicp 47.5', () =>
372    expect(
373      evaluate(
374        `
375(def (f n) (A 0 n))
376(def (g n) (A 1 n)))
377(def (h n) (A 2 n))
378(def (k n) (* 5 n n))
379    `,
380        scope,
381      ),
382    ).toEqual(0));
383
384  // Tree Recursion
385  // recursive process
386  it('sicp 48.1', () =>
387    expect(
388      evaluate(
389        `
390(def (fib n) (match ((eq n 0) 0) ((eq n 1) 1)
391(else (+ (fib (- n 1)) (fib (- n 2))))))
392(fib 7)
393    `,
394        scope,
395      ),
396    ).toEqual(13));
397
398  // iterative process
399  it('sicp 48.2', () =>
400    expect(
401      evaluate(
402        `
403(def (fib n) (fibiter 1 0 n))
404(def (fibiter a b count) (if (eq count 0)
405      b
406      (fibiter (+ a b) a (- count 1))))
407(fib 7)
408    `,
409        scope,
410      ),
411    ).toEqual(13));
412
413  // example: counting change
414  it('sicp 52.2', () =>
415    expect(
416      evaluate(
417        `
418(def (countchange amount) (cc amount 5))
419(def (cc amount kindsofcoins)
420 (match 
421  ((eq amount 0) 1)
422  ((or (lt amount 0) (eq kindsofcoins 0)) 0)
423  (else (+ 
424   (cc amount (- kindsofcoins 1))
425   (cc (- amount (firstdenomination kindsofcoins)) kindsofcoins)))))
426
427(def (firstdenomination kindsofcoins)
428(match 
429 ((eq kindsofcoins 1) 1) 
430 ((eq kindsofcoins 2) 5)
431 ((eq kindsofcoins 3) 10)
432 ((eq kindsofcoins 4) 25)
433 ((eq kindsofcoins 5) 50)))
434
435(countchange 100)
436    `,
437        scope,
438      ),
439    ).toEqual(292));
440
441  // todo: pascals triangle
442  it('sicp 57.1', () =>
443    expect(
444      evaluate(
445        `
446(def (cube x) (* x x x))
447(def (p x) (sub (* 3 x) (* 4 (cube x))))
448(def (sine angle)
449(if (not (gt (abs angle) 0.1)) angle
450(p (sine (/ angle 3.0)))))
451
452(sine 12.15)
453    `,
454        scope,
455      ),
456    ).toEqual(-0.39980345741334));
457
458  // exponentiation recursive
459  it('sicp 57.2', () =>
460    expect(
461      evaluate(
462        `
463(def (expt b n) (if (eq n 0) 1 (* b (expt b (- n 1)))))
464(expt 2 4)
465`,
466        scope,
467      ),
468    ).toEqual(16));
469
470  // exponentiation iterative
471  it('sicp 58.1b', () =>
472    expect(
473      evaluate(
474        `
475(def (expt b n) (exptiter b n 1))
476(def (exptiter b counter product) (if (eq counter 0)
477      product
478      (exptiter b (- counter 1) (* b product))))
479(expt 2 5)
480  `,
481        scope,
482      ),
483    ).toEqual(32));
484
485  // exponentiation fast
486  it('sicp 58.2', () =>
487    expect(
488      evaluate(
489        `
490(def (fastexpt b n) (match ((eq n 0) 1)
491((iseven n) (square (fastexpt b (/ n 2)))) (else (* b (fastexpt b (- n 1))))))
492(def (iseven n)
493(eq (mod n 2) 0))
494(fastexpt 2 5)
495   `,
496        scope,
497      ),
498    ).toEqual(32));
499
500  // * = repeated addition
501  it('sicp 60.1', () =>
502    expect(
503      evaluate(
504        `(def (mult a b) (if (eq b 0)
505        0
506        (+ a (* a (- b 1)))))
507        (mult 3 15)
508   `,
509      ),
510    ).toEqual(45));
511
512  // gcd / euclid
513  it('sicp 63.1', () =>
514    expect(
515      evaluate(
516        `(def (gcd a b) (if (eq b 0)
517      a
518      (gcd b (mod a b))))
519      (gcd 20 6)
520     `,
521        scope,
522      ),
523    ).toEqual(2));
524
525  // 65 smallest divisor
526  // 67 fermat test
527  // ....
528
529  // higher order procedures
530
531  it('sicp 77.1', () =>
532    expect(
533      evaluate(
534        `
535(def (sum term a next b)
536(if (gt a b) 0 (+ (term a)
537(sum term (next a) next b))))
538`,
539        scope,
540      ),
541    ).toEqual(0));
542
543  it('sicp 78.1', () =>
544    expect(
545      evaluate(
546        `
547(def (inc n) (+ n 1))
548(def (cube a) (* a a a))
549(def (sumcubes a b)
550(sum cube a inc b))
551(sumcubes 1 10)
552  `,
553        scope,
554      ),
555    ).toEqual(3025));
556
557  it('sicp 78.2', () =>
558    expect(
559      evaluate(
560        `
561    (def (identity x) x)
562    (def (sumintegers a b)
563    (sum identity a inc b))
564    (sumintegers 1 10)
565    `,
566        scope,
567      ),
568    ).toEqual(55));
569
570  // pisum
571  it('sicp 79.1', () =>
572    expect(
573      evaluate(
574        `
575(def (pisum a b) 
576 (def (piterm x)
577  (/ 1.0 (* x (+ x 2)))) 
578(def (pinext x) (+ x 4))
579(sum piterm a pinext b))
580(* 8 (pisum 1 1000))
581`,
582        scope,
583      ),
584    ).toEqual(3.139592655589783));
585
586  // integral
587  it('sicp 79.2', () =>
588    expect(
589      evaluate(
590        `
591(def (integral f a b dx) 
592 (def (adddx x) (+ x dx))
593(* (sum f (+ a (/ dx 2.0)) adddx b) dx))
594(integral cube 0 1 0.01)
595  `,
596        scope,
597      ),
598    ).toEqual(0.24998750000000042));
599  // maximum callstack...
600  //it('sicp 79.3', () => expect(evaluate(`(integral cube 0 1 0.001)`, scope)).toEqual(0.249999875000001));
601
602  //lambdas
603  it('sicp 83.1', () => expect(evaluate(`((fn (x) (+ x 4)) 5)`)).toEqual(9));
604
605  it('sicp 83.2', () =>
606    expect(
607      evaluate(
608        `
609(def (pisum a b)
610  (sum (fn (x) (/ 1.0 (* x (+ x 2))))
611        a
612        (fn (x) (+ x 4)) 
613        b))
614(* 8 (pisum 1 1000))
615`,
616        scope,
617      ),
618    ).toEqual(3.139592655589783));
619  it('sicp 83.3', () =>
620    expect(
621      evaluate(
622        `
623(def (integral f a b dx) 
624 (* (sum f
625         (+ a (/ dx 2.0)) 
626         (fn (x) (+ x dx)) 
627         b)
628    dx))
629(integral cube 0 1 0.01)
630`,
631        scope,
632      ),
633    ).toEqual(0.24998750000000042));
634  it('sicp 84.1', () => expect(evaluate(`((fn (x y z) (+ x y (square z))) 1 2 3)`, scope)).toEqual(12));
635
636  // let expressions
637  it('sicp 87.1', () =>
638    expect(
639      evaluate(
640        `
641(+ (let ((x 3))
642(+ x (* x 10))) x)
643`,
644        { x: 5 },
645      ),
646    ).toEqual(38));
647  it('sicp 87.2', () =>
648    expect(
649      evaluate(
650        `
651(let ((x 3)
652(y (+ x 2)))
653(* x y))
654  `,
655        { x: 2 },
656      ),
657    ).toEqual(12));
658  it('sicp 88.1', () =>
659    expect(
660      evaluate(
661        `
662(def (f g) (g 2))
663(f square)
664      `,
665        scope,
666      ),
667    ).toEqual(4));
668  it('sicp 88.2', () =>
669    expect(
670      evaluate(
671        `
672  (def (f g) (g 2))
673  (f (fn (z) (* z (+ z 1))))
674            `,
675        scope,
676      ),
677    ).toEqual(6));
678
679  // Finding roots of equations by the half-interval method
680  it('sicp 89.1', () =>
681    expect(
682      evaluate(
683        `
684(def (search f negpoint pospoint)
685 (let ((midpoint (average negpoint pospoint)))
686 (if (closeenough negpoint pospoint) 
687  midpoint
688  (let ((testvalue (f midpoint))) 
689   (match ((positive testvalue)
690           (search f negpoint midpoint))
691          ((negative testvalue)
692           (search f midpoint pospoint)) 
693          (else midpoint))))))
694
695(def (closeenough x y) (lt (abs (- x y)) 0.001))
696
697(def (negative x) (lt x 0))
698(def (positive x) (gt x 0))
699
700(def (halfintervalmethod f a b) (let ((avalue (f a))
701(bvalue (f b)))
702(match ((and (negative avalue) (positive bvalue))
703(search f a b))
704((and (negative bvalue) (positive avalue))
705(search f b a)) (else
706(error "Values are not of opposite sign" a b)))))
707
708(halfintervalmethod sin 2.0 4.0)
709`,
710        scope,
711      ),
712    ).toEqual(3.14111328125));
713
714  it('sicp 89.1', () =>
715    expect(evaluate(`(halfintervalmethod (fn (x) (- (* x x x) (* 2 x) 3)) 1.0 2.0)`, scope)).toEqual(1.89306640625));
716
717  // Finding fixed points of functions
718  it('sicp 92.1', () =>
719    expect(
720      evaluate(
721        `
722(def tolerance 0.00001)
723(def (fixedpoint f first-guess)
724 (def (closeenough v1 v2) (lt (abs (- v1 v2)) tolerance)) 
725 (def (try guess)
726  (let ((next (f guess)))
727  (if (closeenough guess next) next (try next))))
728 (try first-guess))
729
730(fixedpoint cos 1.0)
731`,
732        scope,
733      ),
734    ).toEqual(0.7390822985224023));
735  it('sicp 93.1', () =>
736    expect(evaluate(`(fixedpoint (fn (y) (+ (sin y) (cos y))) 1.0)`, scope)).toEqual(1.2587315962971173));
737  // Maximum call stack size exceeded (expected)
738  /* it('sicp 93.2', () =>
739    expect(evaluate(`(def (sqrt x) (fixedpoint (fn (y) (/ x y)) 1.0)) (sqrt 4)`, scope)).toEqual(0)); */
740  it('sicp 93.3', () =>
741    expect(evaluate(`(def (sqrt x) (fixedpoint (fn (y) (average y (/ x y))) 1.0)) (sqrt 7)`, scope)).toEqual(
742      2.6457513110645907,
743    ));
744  // Procedures as Returned Values
745  it('sicp 97.1', () =>
746    expect(evaluate(`(def (averagedamp f) (fn (x) (average x (f x)))) ((averagedamp square) 10)`, scope)).toEqual(55));
747  it('sicp 98.1', () =>
748    expect(evaluate(`(def (sqrt x) (fixedpoint (averagedamp (fn (y) (/ x y))) 1.0)) (sqrt 7)`, scope)).toEqual(
749      2.6457513110645907,
750    ));
751  it('sicp 98.2', () =>
752    expect(
753      evaluate(`(def (cuberoot x) (fixedpoint (averagedamp (fn (y) (/ x (square y)))) 1.0)) (cuberoot 7)`, scope),
754    ).toEqual(1.912934258514886));
755  it('sicp 99.1', () =>
756    expect(
757      evaluate(
758        `
759        (def (deriv g) (fn (x) (/ (- (g (+ x dx)) (g x)) dx))) 
760        (def dx 0.00001)
761        (def (cube x) (* x x x))
762        ((deriv cube) 5)
763        `,
764        scope,
765      ),
766    ).toEqual(75.00014999664018));
767  // With the aid of deriv, we can express Newton’s method as a fixed-point process:
768  it('sicp 100.1', () =>
769    expect(
770      evaluate(
771        `
772(def (newtontransform g)
773(fn (x) (- x (/ (g x) ((deriv g) x)))))
774(def (newtonsmethod g guess) (fixedpoint (newtontransform g) guess))
775(def (sqrt x) (newtonsmethod (fn (y) (- (square y) x)) 1.0))
776(sqrt 7)
777          `,
778        scope,
779      ),
780    ).toEqual(2.6457513110645907));
781  // whatever this is
782  it('sicp 101.1', () =>
783    expect(
784      evaluate(
785        `
786  (def (fixedpointoftransform g transform guess) (fixedpoint (transform g) guess))
787  (def (sqrt x) (fixedpointoftransform
788  (fn (y) (/ x y)) averagedamp 1.0))
789  (sqrt 7)
790  `,
791        scope,
792      ),
793    ).toEqual(2.6457513110645907));
794  it('sicp 101.2', () =>
795    expect(
796      evaluate(
797        `
798(def (sqrt x) (fixedpointoftransform
799(fn (y) (- (square y) x)) newtontransform 1.0))
800(sqrt 7)
801    `,
802        scope,
803      ),
804    ).toEqual(2.6457513110645907));
805
806  // data abstraction
807
808  // rational arithmetic
809  it('sicp 114.1', () =>
810    expect(
811      evaluate(
812        `
813(def (addrat x y)
814 (makerat (+ (* 
815   (numer x) (denom y))
816   (* (numer y) (denom x)))
817  (* (denom x) (denom y))))
818(def (subrat x y)
819 (makerat (- (* (numer x) (denom y))
820   (* (numer y) (denom x)))
821  (* (denom x) (denom y))))
822(def (mulrat x y)
823 (makerat (* (numer x) (numer y))
824  (* (denom x) (denom y)))) 
825(def (divrat x y)
826  (makerat (* (numer x) (denom y))
827   (* (denom x) (numer y))))
828(def (equalrat x y)
829  (eq (* (numer x) (denom y))
830     (* (numer y) (denom x))))
831        `,
832        scope,
833      ),
834    ).toEqual(0));
835
836  // markerat number denom
837  it('sicp 117.1', () =>
838    expect(
839      evaluate(
840        `
841(def (makerat n d) (cons n d)) 
842(def (numer x) (car x))
843(def (denom x) (cdr x))
844(def (printrat x) (concat (numer x) ':' (denom x)))
845      `,
846        scope,
847      ),
848    ).toEqual(0));
849
850  it('sicp 117.1', () => expect(evaluate(`(def onehalf (makerat 1 2)) (printrat onehalf)`, scope)).toEqual('1:2'));
851  it('sicp 117.2', () =>
852    expect(evaluate(`(def onethird (makerat 1 3)) (printrat (addrat onehalf onethird))`, scope)).toEqual('5:6'));
853  it('sicp 117.3', () => expect(evaluate(`(printrat (mulrat onehalf onethird))`, scope)).toEqual('1:6'));
854  it('sicp 117.4', () => expect(evaluate(`(printrat (addrat onethird onethird))`, scope)).toEqual('6:9'));
855  it('sicp 118.1', () =>
856    expect(evaluate(`(def (makerat n d) (let ((g (gcd n d))) (cons (/ n g) (/ d g))))`, scope)).toEqual(0));
857  it('sicp 118.1', () => expect(evaluate(`(printrat (addrat onethird onethird))`, scope)).toEqual('2:3'));
858
859  let lscope = {};
860  // pairs with lambda
861  it('sicp 124.1', () =>
862    expect(
863      evaluate(
864        `
865(def (cons x y) 
866 (def (dispatch m)
867  (match 
868   ((eq m 0) x) 
869   ((eq m 1) y)
870   (else (error "argument not 0 or 1: CONS" m)))
871  ) dispatch)
872 (def (car z) (z 0)) 
873 (def (cdr z) (z 1))
874      `,
875        lscope,
876      ),
877    ).toEqual(0));
878  it('sicp 124.1', () => expect(evaluate(`(car (cons first second))`, lscope)).toEqual('first'));
879  it('sicp 124.2', () => expect(evaluate(`(cdr (cons first second))`, lscope)).toEqual('second'));
880  // lists
881  it('sicp 135.1', () => expect(evaluate(`(list 1 2 3 4)`)).toEqual([1, 2, 3, 4]));
882  it('sicp 137.1', () => expect(evaluate(`(car (list 1 2 3 4))`)).toEqual(1));
883  it('sicp 137.2', () => expect(evaluate(`(cdr (list 1 2 3 4))`)).toEqual([2, 3, 4]));
884  it('sicp 137.3', () => expect(evaluate(`(car (cdr (list 1 2 3 4)))`)).toEqual(2));
885  it('sicp 137.4', () => expect(evaluate(`(cons 10 (list 1 2 3 4))`)).toEqual([10, 1, 2, 3, 4]));
886  // listref
887  it('sicp 138.1', () =>
888    expect(
889      evaluate(
890        `
891(def (listref items n) (if (eq n 0) (car items) 
892 (listref (cdr items) (- n 1)))) 
893(def squares (list 1 4 9 16 25)) 
894(listref squares 3)`,
895        scope,
896      ),
897    ).toEqual(16));
898  // length recursive
899  it('sicp 138.2', () =>
900    expect(
901      evaluate(
902        `
903  (def (length items) 
904   (if (isnull items) 0
905    (+ 1 (length (cdr items))))) 
906  (def odds (list 1 3 5 7)) 
907  (length odds)`,
908      ),
909    ).toEqual(4));
910  // length iterative
911  it('sicp 139.1', () =>
912    expect(
913      evaluate(
914        `
915  (def (length items)
916  (def (lengthiter a count)
917   (if (isnull a) count
918    (lengthiter (cdr a) (+ 1 count))))
919    (lengthiter items 0))
920  (def odds (list 1 3 5 7)) 
921  (length odds)
922  `,
923        scope,
924      ),
925    ).toEqual(4));
926  // append
927  it('sicp 139.1', () =>
928    expect(
929      evaluate(
930        `
931(def (append list1 list2) 
932(if (isnull list1)
933  list2
934  (cons (car list1) (append (cdr list1) list2))))
935  (append squares odds)
936    `,
937        scope,
938      ),
939    ).toEqual([1, 4, 9, 16, 25, 1, 3, 5, 7]));
940  // (define (f x y . z) ⟨body⟩) <- tbd: variable argument count
941  // Mapping over lists
942
943  it('sicp 143.1', () =>
944    expect(
945      evaluate(
946        `
947(def (scalelist items factor) (if (isnull items) nil
948    (cons (* (car items) factor)
949          (scalelist (cdr items) factor))))
950(scalelist (list 1 2 3 4 5) 10)
951    `,
952        scope,
953      ),
954    ).toEqual([10, 20, 30, 40, 50]));
955
956  it('sicp 143.1', () =>
957    expect(
958      evaluate(
959        `
960  (def (map proc items) (if (isnull items) nil
961        (cons (proc (car items))
962              (map proc (cdr items)))))
963  (map abs (list -10 2.5 -11.6 17))
964  `,
965        scope,
966      ),
967    ).toEqual([10, 2.5, 11.6, 17]));
968  it('sicp 143.1', () => expect(evaluate(`(map (fn (x) (* x x)) (list 1 2 3 4))`, scope)).toEqual([1, 4, 9, 16]));
969  it('sicp 143.1', () =>
970    expect(
971      evaluate(
972        `
973(def (scalelist items factor) (map (fn (x) (* x factor)) items))
974(scalelist (list 1 2 3 4 5) 10)
975`,
976        scope,
977      ),
978    ).toEqual([10, 20, 30, 40, 50]));
979});