A little calculator

.gitignore

node_modules

compile.js

'use strict'

const debug = require('debug')('compile')
    , debugCache = require('debug')('compile:cache')
    , {List, Map, Record, fromJS} = require('immutable')

const reducers = {
  '*': (acc, rhs) => acc * rhs,
  '/': (acc, rhs) => acc / rhs,
  '+': (acc, rhs) => acc + rhs,
  '-': (acc, rhs) => acc - rhs,
  'mod': (acc, rhs) => acc % rhs,
}

const mem = id => ['memory', id]

const evaluators = {
  Identifier({identifier}) {
    return (state=State()) => state.set('value', state.getIn(mem(identifier)))
  },

  Assignment({lhs: {identifier}, rhs}) {
    const rhs_ = this.compile(rhs)
    return (state=State()) => state.setIn(mem(identifier), rhs_(state).value)
  },

  Literal({sign, digits}) {
    return (state=State()) => state.set('value',
      +`${sign}${digits}`)
  },

  Aggregate(
    {first, rest},
    initial=this.compile(first),
    operations=rest.map(({operator, rhs}) => ({
      operator,
      rhs: this.compile(rhs)
    }))
  ) {
    return (state=State()) => state.set('value',
      operations.reduce((lhs, {operator, rhs}) =>
        reducers[operator](lhs, rhs(state).value),
        initial(state).value
      ))
  },

  Program({lines}) {
    const program = lines.map(line => this.compile(line))
    return (state=State()) =>
      program.reduce((state, reduce) => reduce(state), state)
  },

  Noop() { return state => state }
}

const State = Record({
  memory: Map(),
  value: undefined,
})

class Calculation {
  constructor(cache=Map()) {
    this.cache = cache
  }

  compile(ast) {
    const {type} = ast
        , key = fromJS(ast)
        , hit = this.cache.get(key)
    if (hit) {
      debugCache('hit for key', key)
      return hit
    }
    if (type in evaluators) {
      debug('compiling %s node', type)
      const calculation = evaluators[type].call(this, ast)
      this.cache = this.cache.set(key, calculation)
      debugCache('inserted key', key)
      return calculation
    }
    debug('invalid type: %s', type)
    return this
  }
}

const compile = module.exports = (ast, calc=new Calculation()) => calc.compile(ast)
module.exports.Calculation = Calculation

grammar.js

'use strict'

// A simple calculator grammar.

const {
        Sequence
      , Exactly
      , CharIn
      , Or
      , Many
      , OneOrMore
      , ZeroOrMore
      , Fail
      , As
      , Drop
      , $
    } = require('./parse')

const __ = Drop(ZeroOrMore(Or(Exactly(' '))))
    , Optional = read => Many(read, {min: 0, max: 1})
    , Identifier = Sequence(__
        , As($(OneOrMore(CharIn('a', 'z'))), 'identifier')
        , state => Object.assign({}, state, {
          match: Object.assign({type: 'Identifier'}, state.match)
        }))
    , Digit = CharIn('0', '9')
    , Sign = Optional(Exactly('-'))
    , Literal = Sequence(__
        , As(Sign, 'sign')
        , As($(Many(Digit)), 'digits')
        , state => Object.assign({}, state, {
          match: Object.assign({type: 'Literal'}, state.match)
        })
    )
    , Parenthesized = Sequence(__
      , Drop(Exactly('(')), __
      , state => Expression(state), __
      , Drop(Exactly(')')), __
    )
    , Primary = Or(Parenthesized, Identifier, Literal)
    , InfixOperatorPrecedenceGroup =
        (type, [...operators], NextPrecedenceGroup=Primary) =>
          Or(Sequence(__
              , As(NextPrecedenceGroup, 'first'), __
              , As(
                  OneOrMore(Sequence(
                      As(Or(...operators.map(Exactly)), 'operator'), __
                    , As(NextPrecedenceGroup, 'rhs'), __
                  )),
                  'rest')
              , state => Object.assign({}, state, {
                match: Object.assign({type}, state.match)
              })        
            )
            , NextPrecedenceGroup)
    , Multiplicative = InfixOperatorPrecedenceGroup('Aggregate', ['*', '/', 'mod'])
    , Additive = InfixOperatorPrecedenceGroup('Aggregate', ['+', '-'], Multiplicative)
    , Expression = Or(Additive, Multiplicative, Primary)
    , Assignment = Sequence(__
        , As(Identifier, 'lhs'), __
        , Drop(Exactly('=')), __
        , As(Expression, 'rhs'), __
        , state => Object.assign({}, state, {
          match: Object.assign({type: 'Assignment'}, state.match)
        })
      )
    , Line = Or(Assignment, Expression)
    , Newlines = Drop(ZeroOrMore(Exactly('\n')))
    , Program = Sequence(
        OneOrMore(Sequence(Newlines, Line, Newlines)),
        state => Object.assign({}, state, {
          match: { type: 'Program', lines: state.match }
        })
      )

if (module === require.main) {
  const input = `
    x = -2 * y
    x * z + k
    f+n
  `
  console.log(JSON.stringify(Program({input}), 0, 2))
}

module.exports = {Line, Program}

index.js

'use strict'

// A little calculator.

const readline = require('readline')
    , debug = require('debug')
    , trace = {
      ast: debug('calc:ast'),
    }
    , fs = require('fs')
    , compile = require('./compile')
    , {Program, Line} = require('./grammar')

if (module === require.main) { main(process.argv) }

function main([_node, _self, file]) {
  // If a file was given at the command line, run it.
  if (file) {
    return fs.readFile(file, (err, ok) => err
      ? console.error('%s: %s', file, err)
      : runProgram(ok.toString()))
  }

  // Interactive mode.
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  })
  rl.setPrompt('>>> ')
  rl.prompt()
  rl.on('line', repl(rl))
}

function repl(rl, state=undefined, calculation=new compile.Calculation()) {
  return input => {
    try {
      const {input: noise, match, error} = Line({input})
      if (noise) console.error('Warning: ignoring noise at end of line: "%s"', noise)
      if (error) return console.error(error)
      trace.ast(JSON.stringify(match, 0, 2))
      const run = calculation.compile(match)
      state = run(state)
      print(state, calculation)
    } finally {
      rl.prompt()
    }
  }
}

function runProgram(input, filename='__inputfile__') {
  const {error, match} = Program({input})
  if (error) {
    return console.error('%s: %s', filename, error)
  }
  const calculation = new compile.Calculation()
      , program = calculation.compile(match)
  print(program(), calculation)
}

function print(state, calculation) {
  console.log('value:', state.get('value'), '\tmem:', state.get('memory').toJS())
  if (calculation) console.log('(%s entries in cache)', calculation.cache.size)
}

package.json

{
  "name": "calc",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "",
  "license": "ISC",
  "dependencies": {
    "debug": "^2.6.6",
    "immutable": "^3.8.1"
  }
}

parse.js

'use strict'

// Functional composition tools for building a parser.

const willExport = () => ({
  Fail,
  CharIn,
  Exactly,

  Sequence,    
  Or,
  Many,
  OneOrMore: Many,
  ZeroOrMore: read => Many(read, {min: 0}),
  As,  
  Drop,
  $,
})

// Fail(state, message) => (state => state)
//
// Return parser state object representing failure with the input
// denoted by state.
const Fail = (state, message) => Object.assign({}, state,  {
  error: new Error(message)
})

// Exactly(match: String) => (state => state)
//
// Exactly match the specified string.
const Exactly = match => state =>
  state.input.startsWith(match)?
    {input: state.input.slice(match.length), match}
    : Fail(state, `expected ${match}`)

// CharIn(min: Char, max: Char) => (state => state)
//
// Match one character in the open range [min, max].
const CharIn = (min, max) => {
  const minCh = min.charCodeAt(0)
      , maxCh = max.charCodeAt(0)
  return state => {
    const match = state.input[0]
    if (!match) return Fail(state, `Unexpected end of input`)
    const inCh = match.charCodeAt(0)
    if (inCh >= minCh && inCh <= maxCh) {
      return {
        input: state.input.slice(1),
        match
      }
    }
    return Fail(state, `${match}: expected ${min} to ${max}`)
  }
}

// Sequence(...readers: state => state) => (state => state)
//
// Takes a sequence of readers and reduces over them, starting
// from an undefined match at the current position.
const Sequence = (...readers) => state => {
  state = Object.assign({}, state, {match: undefined})
  for (const read of readers) {
    state = read(state)
    if (state.error) return state
  }
  return state
}

// Or(...alternatives: state => state) => (state => state)
//
// Takes a sequence of alternatives and attempts each of them in
// turn. Returns the first match state to succeed, or the last failure.
const Or = (...alternatives) => state => {
  let error
  for (const attempt of alternatives) {
    const next = attempt(state)
    if (!next.error) return next
    error = next.error
  }
  return {error}
}

// Many(reader: state => state,
//      options: {min, max, reduce, initial}) => (state => state)
//
// Run reader multiple times. By default, min is 1 and max is Infinity,
// so this is equivalent to OneOrMore of the specified reader. Returns
// a state with an array of matches in match, though this can be changed
// by setting the initial and reduce options.
const Many = (
  read,
  {
    min=1,
    max=Infinity,
    reduce=(all, one) => [...all, one],
    initial=() => []
  }={}
) => state => {
  let match = initial()
    , count = 0
    , next
  while (!state.error && count < max) {
    next = read(state)
    if (next.error) break
    match = reduce(match, next.match)
    ++count
    state = next
  }
  if (count < min) {
    return next
  }
  return Object.assign({}, state, {match})
}

// As(read: state => state, name: String|Symbol) => (state => state)
//
// Match the specified reader. If it fails, return the error. If
// it succeeds, return a state whose match contains the current
// match, along with a new key of `name` and a value of the match.
//
// Best used with Sequence.
const As = (read, name) => state => {
  const next = read(state)
  if (next.error) return next
  return {
    input: next.input,
    match: Object.assign({}, state.match, {
      [name]: next.match
    })
  }
}

// Drop(read: state => state) => (state => state)
//
// Run a reader and drop the result. On a successful match, only the parser's
// positon is changed.
const Drop = read => state => {
  const next = read(state)
  if (next.error) return next
  return {
    input: next.input,
    match: state.match,
  }
}

// $(read: state => state) => (state => state)
//
// Run a reader and convert the resulting match to a string.
const $ = read => state => {
  const next = read(state)
  if (next.error) return next
  return {
    input: next.input,
    match: next.match && next.match.join('')
  }
}

module.exports = willExport()

test.calc

x = 2
y = 10
x + 2

x * y

yarn.lock

# THIS IS AN AUTOGENERATED FILE. DO NOT EDIT THIS FILE DIRECTLY.
# yarn lockfile v1


debug@^2.6.6:
  version "2.6.6"
  resolved "https://registry.yarnpkg.com/debug/-/debug-2.6.6.tgz#a9fa6fbe9ca43cf1e79f73b75c0189cbb7d6db5a"
  dependencies:
    ms "0.7.3"

immutable@^3.8.1:
  version "3.8.1"
  resolved "https://registry.yarnpkg.com/immutable/-/immutable-3.8.1.tgz#200807f11ab0f72710ea485542de088075f68cd2"

[email protected]:
  version "0.7.3"
  resolved "https://registry.yarnpkg.com/ms/-/ms-0.7.3.tgz#708155a5e44e33f5fd0fc53e81d0d40a91be1fff"