LIJSP... heh

lijsp.js

import { expect } from 'chai'

const head = (arr = []) => arr.slice(0)[0]
const tail = (arr = []) => arr.slice(1)
const last = (arr = []) => arr.slice(0).pop()
const init = (arr = []) => arr.slice(0, arr.length - 1)

const subExpression = (tokens, depth = 0, currentBranch = []) => {
  if (tokens.length === 0 || head(tokens) === ')') {
    return [currentBranch, tail(tokens)]
  }

  if (head(tokens) === '(') {
    const [subBranch, nextTokens] = subExpression(tail(tokens), depth + 1)
    const [restBranch, restTokens] = subExpression(nextTokens, depth)
    return [[...currentBranch, subBranch, ...restBranch], restTokens]
  } else {
    return subExpression(tail(tokens), depth, [...currentBranch, head(tokens)])
  }
}

const ast = (tokens) => (head(subExpression(tokens)))

describe('ast()', () => {
  it('takes a list of tokens and returns nested scoped expressions', () => {
    expect(ast(['1', '2'])).to.eql(['1', '2'])
    expect(ast(['(', '1', ')', '(', '2', ')'])).to.eql([['1'], ['2']])
    expect(ast(['(', '1', '(', '2', '(', '3', ')', ')', ')'])).to.eql([['1', ['2', ['3']]]])
    expect(ast(['(', '1', '(', '2', '(', '3', ')', ')', '1', ')'])).to.eql([['1', ['2', ['3']], '1']])
    expect(ast(['+',  '1.5', '(', '/',  '(', '+', '2.5', '20', ')', '5', ')'])).to.eql(['+',  '1.5', ['/',  ['+', '2.5','20'], '5']])
  })
})

const primitives = {
  ['+'](a, b) {
    return parseFloat(a) + parseFloat(b)
  },
  ['-'](a, b) {
    return parseFloat(a) - parseFloat(b)
  },
  ['*'](a, b) {
    return parseFloat(a) * parseFloat(b)
  },
  ['/'](a, b) {
    return parseFloat(a) / parseFloat(b)
  }
}

const nullEnv = {
  parent: {},
  current: {}
}

const isNumber   = (str) => (str.match(/^\d+(.\d+)?$/g))
const isValue    = (candidate) => (isNumber(candidate))
const isFunction = (candidate) => (candidate instanceof Function)

const lookup = (atom, { current, parent }) => {
  if (isValue(atom)) {
    return atom
  } else if (current[atom]) {
    return current[atom]
  } else {
    return lookup(atom, parent)
  }
}

const lambda = (parentEnv, params, expression) => {
  return (...args) => {
    const env = {
      parent: parentEnv,
      current: params.reduce((env, param, index) => ({
        ...env,
        [param]: args[index]
      }), {})
    }
    return head(evaluate(expression, env))
  }
}

const define = ({ parent, current }, symbol, value) => ({
  parent,
  current: {
    ...current,
    [symbol]: value
  }
})

const isExpression = (candidate) => (candidate instanceof Array)
const isSelf       = (candidate) => (isExpression(candidate) && candidate.length === 1)
const isDefinition = (candidate) => (isExpression(candidate) && head(candidate) === 'define')
const isLambda     = (candidate) => (isExpression(candidate) && head(candidate) === 'lambda')
const isApplicable = (candidate) => (isExpression(candidate) && isFunction(head(candidate)))

const evalDefinition = (definition, env) => {
  const [atom, value] = tail(definition)
  const evaledVal = isExpression(value)
    ? head(evaluate(value, env))
    : lookup(value, env)

  return [
    atom,
    define(env, atom, evaledVal)
  ]
}

const evalLambda = (expression, env) => {
  const [params, body] = tail(expression)

  return lambda(env, params, body)
}

const evaluate = (expression = [], env = nullEnv, evaluated = []) => {
  if (expression.length === 0) {
    return [evalReturn(evaluated), env]
  } else if (isDefinition(expression)) {
    return evalDefinition(expression, env)
  } else if (isLambda(expression)) {
    return [evalLambda(expression, env), env]
  } else if (isExpression(head(expression))) {
    const [value, newEnv] = evaluate(head(expression), env)
    return evaluate(tail(expression), newEnv, [...evaluated, value])
  } else {
    const value = lookup(head(expression), env)
    return evaluate(tail(expression), env, [...evaluated, value])
  }
}

const evalReturn = (expression) => {
  if (isApplicable(expression)) {
    return apply(head(expression), tail(expression))
  } else {
    return last(expression)
  }
}

const apply = (operator, operands) => (
  operator(...operands)
)

describe('evaluate()', () => {
  context('passed a value', () => {
    it('returns that value', () => {
      const [val] = evaluate(['1'])
      expect(val).to.eq('1')
    })
  })

  context('passed a variable', () => {
    it('returns the lookup of that variable', () => {
      const [val] = evaluate(['a'], { current: { a: '1' } })
      expect(val).to.eq('1')
    })
  })

  context('passed a definition', () => {
    it('returns the symbol for that definition', () => {
      const [val, newEnv] = evaluate(['define', 'a', '1'])
      expect(val).to.eq('a')
      expect(newEnv.current).to.eql({ a: '1' })
    })
  })

  context('passed a lambda definition', () => {
    it('returns the created lambda', () => {
      const [val] = evaluate(['lambda', ['a'], ['a']])
      expect(typeof val).to.eq('function')
    })
  })

  context('passed an immeditately executing lambda', () => {
    it('returns the return value of the executed lambda', () => {
      const [val] = evaluate([['lambda', ['a'], ['a']], '1'])
      expect(val).to.eq('1')
    })
  })

  context('passed a definition of a function and a call to that function', () => {
    it('returns the return value of the executed, newly definition, function', () => {
      const [val] = evaluate([['define', 'a', ['lambda', ['b'], ['b']]], ['a', '1']])
      expect(val).to.eq('1')
    })
  })
})

const controlCharacters = ['(', ')', ' ']
const includes = (arr = [], elem) => (arr.indexOf(elem) !== -1)

const tokenize = (str) => {
  return str.split('').reduce((tokens, character) => {
    const lastToken = last(tokens)
    if (!lastToken ||
        includes(controlCharacters, lastToken) ||
        includes(controlCharacters, character)) {
      return [...tokens, character]
    } else {
      return [...init(tokens), (lastToken + character)]
    }
  }, []).filter((token) => token !== ' ')
}

describe('tokenize()', () => {
  it('turns a string into an array of tokens', () => {
    expect(tokenize('1 2')).to.eql(['1', '2'])
    expect(tokenize('1.1 2')).to.eql(['1.1', '2'])
    expect(tokenize('1.1.1 2')).to.eql(['1.1.1', '2'])
    expect(tokenize('1. 2')).to.eql(['1.', '2'])
    expect(tokenize('+ 1.3 2')).to.eql(['+', '1.3', '2'])
    expect(tokenize('+ 103456.3 2')).to.eql(['+', '103456.3', '2'])
    expect(tokenize('+ (+ 1.3 2) (/ 4 5)')).to.eql(['+', '(', '+', '1.3', '2', ')', '(', '/', '4', '5', ')'])
  })
})

const execute = (str) => (
  head(evaluate(ast(tokenize(str)), { current: primitives }))
)

describe('execute()', () => {
  it('returns the result of a parsed string', () => {
    expect(execute('+ 1 2')).to.eq(3)
    expect(execute('+ 1.5 (+ 2.5 (/ 20 5))')).to.eq(8)
    expect(execute('+ 1.5 (/ (+ 2.5 20) 5)')).to.eq(6)
    expect(execute('(define square (lambda (n) (* n n)))(square 2)')).to.eq(4)
  })
})