1/*
2mondo.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
7// evolved from https://garten.salat.dev/lisp/parser.html
8export class MondoParser {
9  // these are the tokens we expect
10  token_types = {
11    comment: /^\/\/(.*?)(?=\n|$)/,
12    quotes_double: /^"(.*?)"/,
13    quotes_single: /^'(.*?)'/,
14    open_list: /^\(/,
15    close_list: /^\)/,
16    open_angle: /^</,
17    close_angle: /^>/,
18    open_square: /^\[/,
19    close_square: /^\]/,
20    open_curly: /^\{/,
21    close_curly: /^\}/,
22    number: /^-?[0-9]*\.?[0-9]+/, // before pipe!
23    // TODO: better error handling when "-" is used as rest, e.g "s [- bd]"
24    op: /^[*/:!@%?+\-&]|^\.{2}/, // * / : ! @ % ? ..
25    // dollar: /^\$/,
26    pipe: /^#/,
27    stack: /^[,$]/,
28    or: /^[|]/,
29    plain: /^[a-zA-Z0-9-~_^#]+/,
30  };
31  op_precedence = [['*', '/', ':', '!', '@', '%', '?', '+', '-', '..'], ['&']];
32  // matches next token
33  next_token(code, offset = 0) {
34    for (let type in this.token_types) {
35      const match = code.match(this.token_types[type]);
36      if (match) {
37        let token = { type, value: match[0] };
38        if (offset !== -1) {
39          // add location
40          token.loc = [offset, offset + match[0].length];
41        }
42        return token;
43      }
44    }
45    throw new Error(`mondo: could not match '${code}'`);
46  }
47  // takes code string, returns list of matched tokens (if valid)
48  tokenize(code, offset = 0) {
49    let tokens = [];
50    let locEnabled = offset !== -1;
51    let trim = () => {
52      // trim whitespace at start, update offset
53      offset += code.length - code.trimStart().length;
54      // trim start and end to not confuse parser
55      return code.trim();
56    };
57    code = trim();
58    while (code.length > 0) {
59      code = trim();
60      const token = this.next_token(code, locEnabled ? offset : -1);
61      code = code.slice(token.value.length);
62      offset += token.value.length;
63      tokens.push(token);
64    }
65    return tokens;
66  }
67  // take code, return abstract syntax tree
68  parse(code, offset) {
69    this.code = code;
70    this.offset = offset;
71    this.tokens = this.tokenize(code, offset);
72    const expressions = [];
73    while (this.tokens.length) {
74      expressions.push(this.parse_expr());
75    }
76    if (expressions.length === 0) {
77      // empty case
78      return { type: 'list', children: [] };
79    }
80    // do we have multiple top level expressions or a single non list?
81    if (expressions.length > 1 || expressions[0].type !== 'list') {
82      return {
83        type: 'list',
84        children: this.desugar(expressions),
85      };
86    }
87    // we have a single list
88    return expressions[0];
89  }
90  // parses any valid expression
91  parse_expr() {
92    if (!this.tokens[0]) {
93      throw new Error(`unexpected end of file`);
94      // TODO: could we allow that? like (((((((( s bd
95      // return { type: 'list', children: [] };
96    }
97    let next = this.tokens[0]?.type;
98    if (next === 'open_list') {
99      return this.parse_list();
100    }
101    if (next === 'open_angle') {
102      return this.parse_angle();
103    }
104    if (next === 'open_square') {
105      return this.parse_square();
106    }
107    if (next === 'open_curly') {
108      return this.parse_curly();
109    }
110    return this.consume(next);
111  }
112  // Token[] => Token[][], e.g. (x , y z) => [['x'],['y','z']]
113  split_children(children, split_type) {
114    const chunks = [];
115    while (true) {
116      let splitIndex = children.findIndex((child) => child.type === split_type);
117      if (splitIndex === -1) break;
118      const chunk = children.slice(0, splitIndex);
119      chunks.push(chunk);
120      children = children.slice(splitIndex + 1);
121    }
122    chunks.push(children);
123    return chunks;
124  }
125  desugar_split(children, split_type, next) {
126    const chunks = this.split_children(children, split_type);
127    if (chunks.length === 1) {
128      return next(children);
129    }
130    // collect args of stack function
131    const args = chunks
132      .map((chunk) => {
133        if (!chunk.length) {
134          return; // useful for things like "$ s bd $ s hh*8" (first chunk is empty)
135        }
136        if (chunk.length === 1) {
137          // chunks of one element can be added to the stack as is
138          return chunk[0];
139        }
140        // chunks of multiple args
141        chunk = next(chunk);
142        return { type: 'list', children: chunk };
143      })
144      .filter(Boolean); // ignore empty chunks
145    return [{ type: 'plain', value: split_type }, ...args];
146  }
147  // prevents to get a list, e.g. ((x y)) => (x y)
148  unwrap_children(children) {
149    if (children.length === 1) {
150      return children[0].children;
151    }
152    return children;
153  }
154  desugar_ops(children, types) {
155    while (true) {
156      let opIndex = children.findIndex((child) => child.type === 'op' && types.includes(child.value));
157      if (opIndex === -1) break;
158      const op = { type: 'plain', value: children[opIndex].value };
159      if (opIndex === children.length - 1) {
160        //throw new Error(`cannot use operator as last child.`);
161        children[opIndex] = op; // ignore operator if last child.. e.g. "note [c -]"
162        continue;
163      }
164      if (opIndex === 0) {
165        // regular function call (assuming each operator exists as function)
166        children[opIndex] = op;
167        continue;
168      }
169      // convert infix to prefix notation
170      const left = children[opIndex - 1];
171      const right = children[opIndex + 1];
172      if (left.type === 'pipe') {
173        // "x !* 2" => (* 2 x)
174        children[opIndex] = op;
175        continue;
176      }
177      // some careful error handling
178      if (left.type === 'op') {
179        throw new Error(`got 2 ops in a row: "${left.value}${op.value}"`);
180      }
181      if (right.type === 'op') {
182        let err = `got 2 ops in a row: "${op.value}${right.value}"`;
183        if (op.value === '-') {
184          // yes i know this file is not supposed to know about rests x.X
185          err += '. you probably want a rest, which is "_" in mondo!';
186        }
187        throw new Error(err);
188      }
189      const call = { type: 'list', children: [op, right, left] };
190      // insert call while keeping other siblings
191      children = [...children.slice(0, opIndex - 1), call, ...children.slice(opIndex + 2)];
192      children = this.unwrap_children(children);
193    }
194    return children;
195  }
196  get_lambda(args, children) {
197    // (.fast 2) = (fn (_) (fast _ 2))
198    children = this.desugar(children);
199    const body = children.length === 1 ? children[0] : { type: 'list', children };
200    return [{ type: 'plain', value: 'fn' }, { type: 'list', children: args }, body];
201  }
202  // returns location range of given ast (even if desugared)
203  get_range(ast, range = [Infinity, 0]) {
204    let union = (a, b) => [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
205    if (ast.loc) {
206      return union(range, ast.loc);
207    }
208    if (ast.type !== 'list') {
209      return range;
210    }
211    return ast.children.reduce((range, child) => {
212      const childrange = this.get_range(child, range);
213      return union(range, childrange);
214    }, range);
215  }
216  errorhead(ast) {
217    return `[mondo ${this.get_range(ast)?.join(':') || '?'}]`;
218  }
219  // returns original user code where the given ast originates (even if desugared)
220  get_code_snippet(ast) {
221    const [min, max] = this.get_range(ast);
222    return this.code.slice(min - this.offset, max - this.offset);
223  }
224  desugar_pipes(children) {
225    let chunks = this.split_children(children, 'pipe');
226    while (chunks.length > 1) {
227      let [left, right, ...rest] = chunks;
228
229      if (!left.length) {
230        const arg = { type: 'plain', value: '_' };
231        return this.get_lambda([arg], [arg, ...children]);
232      }
233      // s jazz hh.fast 2 => (fast 2 (s jazz hh))
234      const call = left.length > 1 ? { type: 'list', children: left } : left[0];
235      chunks = [[...right, call], ...rest];
236    }
237    // return next(chunks[0]);
238    return chunks[0];
239  }
240  parse_pair(open_type, close_type) {
241    const begin = this.tokens[0].loc?.[0];
242    this.consume(open_type);
243    const children = [];
244    while (this.tokens[0]?.type !== close_type) {
245      children.push(this.parse_expr());
246    }
247    const end = this.tokens[0].loc?.[1];
248    this.consume(close_type);
249    const node = { type: 'list', children };
250    if (begin !== undefined) {
251      node.loc = [begin, end];
252      node.raw = this.code.slice(begin, end);
253    }
254    return node;
255  }
256  desugar(children, type) {
257    // if type is given, the first element is expected to contain it as plain value
258    // e.g. with (square a b, c), we want to split (a b, c) and ignore "square"
259    children = type ? children.slice(1) : children;
260    children = this.desugar_split(children, 'stack', (children) =>
261      this.desugar_split(children, 'or', (children) => {
262        // chunks of multiple args
263        if (type) {
264          // the type we've removed before splitting needs to be added back
265          children = [{ type: 'plain', value: type }, ...children];
266        }
267        // for each precendence group, call desugar_ops once
268        this.op_precedence.forEach((ops) => {
269          children = this.desugar_ops(children, ops);
270        });
271        children = this.desugar_pipes(children);
272        return children;
273      }),
274    );
275    return children;
276  }
277  parse_list() {
278    let node = this.parse_pair('open_list', 'close_list');
279    node.children = this.desugar(node.children);
280    return node;
281  }
282  parse_angle() {
283    let node = this.parse_pair('open_angle', 'close_angle');
284    node.children.unshift({ type: 'plain', value: 'angle' });
285    node.children = this.desugar(node.children, 'angle');
286    return node;
287  }
288  parse_square() {
289    let node = this.parse_pair('open_square', 'close_square');
290    node.children.unshift({ type: 'plain', value: 'square' });
291    node.children = this.desugar(node.children, 'square');
292    return node;
293  }
294  parse_curly() {
295    let node = this.parse_pair('open_curly', 'close_curly');
296    node.children.unshift({ type: 'plain', value: 'curly' });
297    node.children = this.desugar(node.children, 'curly');
298    return node;
299  }
300  consume(type) {
301    // shift removes first element and returns it
302    const token = this.tokens.shift();
303    if (token.type !== type) {
304      throw new Error(`expected token type ${type}, got ${token.type}`);
305    }
306    return token;
307  }
308  get_locations(code, offset = 0) {
309    let walk = (ast, locations = []) => {
310      if (ast.type === 'list') {
311        return ast.children.forEach((child) => walk(child, locations));
312      }
313      if (ast.loc) {
314        locations.push(ast.loc);
315      }
316    };
317    const ast = this.parse(code, offset);
318    let locations = [];
319    walk(ast, locations);
320    return locations;
321  }
322}
323
324export function printAst(ast, compact = false, lvl = 0) {
325  const br = compact ? '' : '\n';
326  const spaces = compact ? '' : Array(lvl).fill(' ').join('');
327  if (ast.type === 'list') {
328    return `${lvl ? br : ''}${spaces}(${ast.children.map((child) => printAst(child, compact, lvl + 1)).join(' ')}${
329      ast.children.find((child) => child.type === 'list') ? `${br}${spaces})` : ')'
330    }`;
331  }
332  return `${ast.value}`;
333}
334
335// lisp runner
336export class MondoRunner {
337  constructor({ evaluator } = {}) {
338    this.parser = new MondoParser();
339    this.evaluator = evaluator;
340    this.assert(typeof evaluator === 'function', `expected an evaluator function to be passed to new MondoRunner`);
341  }
342  // a helper to check conditions and throw if they are not met
343  assert(condition, error) {
344    if (!condition) {
345      throw new Error(error);
346    }
347  }
348  run(code, scope, offset = 0) {
349    const ast = this.parser.parse(code, offset);
350    //console.log(printAst(ast));
351    return this.evaluate(ast, scope);
352  }
353  evaluate_let(ast, scope) {
354    // (let ((x 3) (y 4)) ...body)
355    // = ((fn (x y) ...body) 3 4)
356    const defs = ast.children[1].children;
357    const args = defs.map((pair) => pair.children[0]);
358    const vals = defs.map((pair) => pair.children[1]);
359    const body = ast.children.slice(2);
360    const lambda = {
361      type: 'list',
362      children: [{ type: 'plain', value: 'fn' }, { type: 'list', children: args }, ...body],
363    };
364    return this.evaluate({ type: 'list', children: [lambda, ...vals] }, scope);
365  }
366  evaluate_def(ast, scope) {
367    // function definition special form?
368    if (ast.children[1].type === 'list') {
369      // (def (add a b) (+ a b))
370      // => (def add (fn (a b) (+ a b)) )
371      const args = ast.children[1].children.slice(1);
372      const lambda = {
373        // lambda
374        type: 'list',
375        children: [
376          { type: 'plain', value: 'fn' },
377          { type: 'list', children: args },
378          ...ast.children.slice(2), // body
379        ],
380      };
381      // we mutate to make sure the old ast wont make a mess later
382      ast.children[1] = ast.children[1].children[0];
383      ast.children[2] = lambda;
384      ast.children = ast.children.slice(0, 3); // throw away rest
385    }
386    // (def name body)
387    if (ast.children.length !== 3) {
388      throw new Error(`expected "def" to have 3 children, but got ${ast.children.length}`);
389    }
390    const name = ast.children[1].value;
391    const body = this.evaluate(ast.children[2], scope);
392    scope[name] = body;
393    // def with fall through
394  }
395  evaluate_match(ast, scope) {
396    // (match (p1 e1) (p2 e2) ... (pn en))
397    // = cond in lisp
398    if (ast.children.length < 2) {
399      return;
400    }
401    const [_, ...body] = ast.children;
402    for (let i = 0; i < body.length; ++i) {
403      const [predicate, exp] = body[i].children;
404      if (predicate.value === 'else') {
405        return this.evaluate(exp, scope);
406      }
407      const outcome = this.evaluate(predicate, scope);
408      if (outcome) {
409        return this.evaluate(exp, scope);
410      }
411    }
412    return undefined; // nothing was matched
413  }
414  evaluate_if(ast, scope) {
415    // if is a special case of match
416    if (ast.children.length !== 4) {
417      return;
418    }
419    // (if predicate consequent alternative)
420    const [_, predicate, consequent, alternative] = ast.children;
421    // (match (predicate consequent) (else alternative))
422    const matcher = {
423      type: 'list',
424      children: [
425        { type: 'plain', value: 'match' },
426        { type: 'list', children: [predicate, consequent] },
427        { type: 'list', children: [{ type: 'plain', value: 'else' }, alternative] },
428      ],
429    };
430    return this.evaluate_match(matcher, scope);
431  }
432  evaluate_lambda(ast, scope) {
433    // (fn (_)   (ply 2 _)
434    //     ^args ^ body
435    const [_, formalArgs, ...body] = ast.children;
436    return (...args) => {
437      const params = Object.fromEntries(formalArgs.children.map((arg, i) => [arg.value, args[i]]));
438      const closure = {
439        ...scope,
440        ...params,
441      };
442      // body can have multiple expressions
443      const res = body.map((exp) => this.evaluate(exp, closure));
444      // last expression is the return value
445      return res[res.length - 1];
446    };
447  }
448  evaluate_list(ast, scope) {
449    // evaluate all children before evaluating list (dont mutate!!!)
450    const args = ast.children
451      .filter((child) => child.type !== 'comment') // ignore comments
452      .map((arg) => this.evaluate(arg, scope));
453    const node = { type: 'list', children: args };
454    return this.evaluator(node, scope);
455  }
456  evaluate_leaf(ast, scope) {
457    if (ast.type === 'number') {
458      ast.value = Number(ast.value);
459    } else if (['quotes_double', 'quotes_single'].includes(ast.type)) {
460      ast.value = ast.value.slice(1, -1);
461      ast.type = 'string';
462    }
463    return this.evaluator(ast, scope);
464  }
465  evaluate(ast, scope = {}) {
466    if (ast.type !== 'list') {
467      return this.evaluate_leaf(ast, scope);
468    }
469    const name = ast.children[0]?.value;
470    if (name === 'fn') {
471      return this.evaluate_lambda(ast, scope);
472    }
473    if (name === 'match') {
474      return this.evaluate_match(ast, scope);
475    }
476    if (name === 'if') {
477      return this.evaluate_if(ast, scope);
478    }
479    if (name === 'let') {
480      return this.evaluate_let(ast, scope);
481    }
482    if (name === 'def') {
483      this.evaluate_def(ast, scope);
484    }
485    return this.evaluate_list(ast, scope);
486  }
487}