Skip to content

Instantly share code, notes, and snippets.

@bradparker
Last active March 17, 2016 04:18
Show Gist options
  • Save bradparker/a178743d08880f9361cd to your computer and use it in GitHub Desktop.
Save bradparker/a178743d08880f9361cd to your computer and use it in GitHub Desktop.
LIJSP... heh
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)
})
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment