Lisp parser from https://www.recurse.com/pairing-tasks.

lisp_parser_dart.dart

import 'dart:core';

// Lisp parser from https://www.recurse.com/pairing-tasks.

/// Tokenize the input Lisp code
List<String> tokenize(String code) {
  return code
      .replaceAll('(', ' ( ')
      .replaceAll(')', ' ) ')
      .trim()
      .split(RegExp(r'\s+'));
}

// Dump the tokenized tokens into an AST
Object dumpAST(List<String> tokens) {
  assert(tokens.isNotEmpty, 'Unexpected tokens');

  String token = tokens.removeAt(0);
  if (token == '(') {
    List<Object> list = [];
    while (tokens.isNotEmpty && tokens[0] != ')') {
      list.add(dumpAST(tokens));
    }
    assert(tokens.isNotEmpty, 'Unbalanced parentheses');

    tokens.removeAt(0); // remove ')'
    return list;
  } else if (token == ')') {
    assert(false, 'Unexpected closing parenthesis');
    return token; // Unreachable.
  } else {
    return _parseAtom(token);
  }
}

// Convert token to number or symbol
Object _parseAtom(String token) {
  if (RegExp(r'^[+-]?\d+$').hasMatch(token)) {
    return int.parse(token);
  } else if (RegExp(r'^[+-]?\d+\.\d+$').hasMatch(token)) {
    return double.parse(token);
  } else {
    return token;
  }
}

/// Built-in functions, or global variables.
Map<String, Object Function(List<Object>, Object Function(Object ast))> _env = {
  '+': _evaluatePlus,
  '-': _evaluateMinus,
  '*': _evaluateMulti,
  '/': _evaluateDivide,
  'list': _evaluateList,
  'first': _evaluateFirst,
};

Object _evaluatePlus(List<Object> args, Object Function(Object ast) evaluater) {
  return args.map((arg) => evaluater(arg)).cast<num>().reduce((a, b) => a + b);
}

Object _evaluateMinus(
    List<Object> args, Object Function(Object ast) evaluater) {
  return args.map((arg) => evaluater(arg)).cast<num>().reduce((a, b) => a - b);
}

Object _evaluateMulti(
    List<Object> args, Object Function(Object ast) evaluater) {
  return args.map((arg) => evaluater(arg)).cast<num>().reduce((a, b) => a * b);
}

Object _evaluateDivide(
    List<Object> args, Object Function(Object ast) evaluater) {
  return args.map((arg) => evaluater(arg)).cast<num>().reduce((a, b) => a / b);
}

Object _evaluateList(List<Object> args, Object Function(Object ast) evaluater) {
  return args.map((arg) => evaluater(arg)).toList();
}

Object _evaluateFirst(
    List<Object> args, Object Function(Object ast) evaluater) {
  final first = args.map((arg) => evaluater(arg)).first;
  return first is List ? first.first : first;
}

Object _evaluateInternal(
  Object ast,
) {
  if (ast is int || ast is double || ast is String) {
    return ast;
  } else if (ast is List) {
    // Evaluate expression
    assert(ast.isNotEmpty);

    var operator = ast[0];
    var args = ast.sublist(1);

    assert(
      _env.containsKey(operator),
      'Unsupported built-in function: $operator',
    );

    return _env[operator]!(List.from(args), _evaluateInternal);
  }

  assert(false, 'Invalid expression: $ast');
  return ast; // Unreachable.
}

Object evaluate(
  String code,
) {
  List<String> tokens = tokenize(code);
  var ast = dumpAST(tokens);
  return _evaluateInternal(ast);
}

void main() {
  String code = "(first (list 1 (+ 2 3) 9))";
  List<String> tokens = tokenize(code);
  var ast = dumpAST(tokens);
  print("AST: $ast"); // Should print: ['first', ['list', 1, ['+', 2, 3], 9]]

  var result = evaluate(code);
  print("Result: $result"); // Should print: 1
}