calc.vim

calc.vim

let s:Calc = {}

function s:Calc.new(...)
  let obj = copy(self)
  call call(obj.__init__, a:000, obj)
  return obj
endfunction

function s:Calc.__init__()
  let self.namespace = [{}]
endfunction

function s:Calc.eval(input)
  let tokenizer = s:Tokenizer.new(a:input)
  let parser = s:Parser.new(tokenizer)
  let ast = parser.parse()
  let compiler = s:Compiler.new()
  let code = compiler.compile(ast)
  call self.execute(code)
endfunction

function s:Calc.execute(code)
  let stack = []
  let callstack = []
  let pc = 0
  let code = a:code
  while pc < len(code)
    let insn = code[pc]
    let pc += 1
    if insn.type == 'PUSH'
      call add(stack, insn.value)
    elseif insn.type == 'POP'
      call remove(stack, -1)
    elseif insn.type == 'COPY'
      call add(stack, stack[-1])
    elseif insn.type == 'IDENTIFIER'
      let r = self.val('IDENTIFIER', insn.value)
      call add(stack, r)
    elseif insn.type == 'NUMBER'
      let r = self.val('NUMBER', insn.value)
      call add(stack, r)
    elseif insn.type == 'FUNCTION'
      let r = self.val('FUNCTION',
            \ [insn.value[0], insn.value[1], copy(self.namespace)])
      call add(stack, r)
    elseif insn.type == 'ADD'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value + y.value)
      call add(stack, r)
    elseif insn.type == 'SUB'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value - y.value)
      call add(stack, r)
    elseif insn.type == 'MUL'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value * y.value)
      call add(stack, r)
    elseif insn.type == 'DIV'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value / y.value)
      call add(stack, r)
    elseif insn.type == 'MOD'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', fmod(x.value, y.value))
      call add(stack, r)
    elseif insn.type == 'PLUS'
      let x = remove(stack, -1)
      let x = self.rvalue(x)
      let r = self.val('NUMBER', +x.value)
      call add(stack, r)
    elseif insn.type == 'MINUS'
      let x = remove(stack, -1)
      let x = self.rvalue(x)
      let r = self.val('NUMBER', -x.value)
      call add(stack, r)
    elseif insn.type == 'ASSIGN'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.lvalue(x), self.rvalue(y)]
      let self.namespace[-1][x.value] = y
      call add(stack, x)
    elseif insn.type == 'EQEQ'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value == y.value)
      call add(stack, r)
    elseif insn.type == 'NOTEQ'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value != y.value)
      call add(stack, r)
    elseif insn.type == 'LT'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value < y.value)
      call add(stack, r)
    elseif insn.type == 'GT'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value > y.value)
      call add(stack, r)
    elseif insn.type == 'LTEQ'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value <= y.value)
      call add(stack, r)
    elseif insn.type == 'GTEQ'
      let [x, y] = remove(stack, -2, -1)
      let [x, y] = [self.rvalue(x), self.rvalue(y)]
      let r = self.val('NUMBER', x.value >= y.value)
      call add(stack, r)
    elseif insn.type == 'BRANCHT'
      let x = remove(stack, -1)
      let x = self.rvalue(x)
      if !empty(x.value)
        let pc += insn.value
      endif
    elseif insn.type == 'BRANCHF'
      let x = remove(stack, -1)
      let x = self.rvalue(x)
      if empty(x.value)
        let pc += insn.value
      endif
    elseif insn.type == 'BRANCH'
      let pc += insn.value
    elseif insn.type == 'CALL'
      let nargs = insn.value
      let f = remove(stack, -1)
      let f = self.rvalue(f)
      if f.type != 'FUNCTION'
        throw 'Error: cannot call ' . f.type
      endif
      if len(f.value[0]) < nargs
        throw 'Error: too few arguments'
      endif
      if len(f.value[0]) > nargs
        throw 'Error: too many arguments'
      endif
      let namespace = copy(f.value[2])
      call add(namespace, {})
      for name in reverse(copy(f.value[0]))
        let x = remove(stack, -1)
        let namespace[-1][name] = self.rvalue(x)
      endfor
      call add(callstack, [code, pc, self.namespace])
      let [code, pc, self.namespace] = [f.value[1], 0, namespace]
    elseif insn.type == 'RETURN'
      let r = remove(stack, -1)
      let r = self.rvalue(r)
      call add(stack, r)
      let [code, pc, self.namespace] = remove(callstack, -1)
    elseif insn.type == 'PRINT'
      let x = remove(stack, -1)
      let x = self.rvalue(x)
      if x.type == 'FUNCTION'
        echo '<FUNCTION>'
      else
        echo x.value
      endif
    else
      throw 'Unknown instruction: ' . string(insn)
    endif
  endwhile
endfunction

function s:Calc.val(type, value)
  return {'type': a:type, 'value': a:value}
endfunction

function s:Calc.lvalue(x)
  return a:x
endfunction

function s:Calc.rvalue(x)
  if a:x.type == 'IDENTIFIER'
    for i in range(len(self.namespace) - 1, 0, -1)
      if has_key(self.namespace[i], a:x.value)
        return self.namespace[i][a:x.value]
      endif
    endfor
    throw 'Undefined variable: ' . a:x.value
  else
    return a:x
  endif
endfunction

let s:Tokenizer = {}

function s:Tokenizer.new(...)
  let obj = copy(self)
  call call(obj.__init__, a:000, obj)
  return obj
endfunction

function s:Tokenizer.__init__(...)
  let self.input = get(a:000, 0, '')
  let self.i = 0
  let self.tokenbuf = []
endfunction

function s:Tokenizer.token(type, value)
  return {'type': a:type, 'value': a:value}
endfunction

function s:Tokenizer.peek()
  if empty(self.tokenbuf)
    call add(self.tokenbuf, self.read())
  endif
  return self.tokenbuf[-1]
endfunction

function s:Tokenizer.get()
  if !empty(self.tokenbuf)
    return remove(self.tokenbuf, -1)
  endif
  return self.read()
endfunction

function s:Tokenizer.read()
  let items = [
        \ ['\v^\s+', 'SPACE'],
        \ ['\v^%(\r\n|\r|\n)', 'NEWLINE'],
        \ ['\v\c^%(IF|ELSE|ELSEIF|ENDIF|WHILE|ENDWHILE|BREAK|CONTINUE|FUNCTION|ENDFUNCTION|RETURN)>', 'KEYWORD'],
        \ ['\v^\d+%(\.\d+)?', 'NUMBER'],
        \ ['\v^\h\w*>', 'IDENTIFIER'],
        \ ['\v^\=\=', 'EQEQ'],
        \ ['\v^\!\=', 'NOTEQ'],
        \ ['\v^\<\=', 'LTEQ'],
        \ ['\v^\>\=', 'GTEQ'],
        \ ['\v^\|\|', 'LOGOR'],
        \ ['\v^\&\&', 'LOGAND'],
        \ ['\v^\+', 'ADD'],
        \ ['\v^\-', 'SUB'],
        \ ['\v^\*', 'MUL'],
        \ ['\v^\/', 'DIV'],
        \ ['\v^\%', 'MOD'],
        \ ['\v^\(', 'LPAR'],
        \ ['\v^\)', 'RPAR'],
        \ ['\v^\=', 'EQ'],
        \ ['\v^\<', 'LT'],
        \ ['\v^\>', 'GT'],
        \ ['\v^,', 'COMMA'],
        \ ['\v^\[', 'LSQ'],
        \ ['\v^\]', 'RSQ'],
        \ ['\v^\?', 'QUESTION'],
        \ ['\v^:', 'COLON'],
        \ ]
  while self.i < len(self.input)
    let m = []
    for [mx, type] in items
      let m = matchlist(self.input, mx, self.i)
      if !empty(m)
        let self.i += len(m[0])
        if type == 'SPACE'
          break
        endif
        return self.token(type, m[0])
      endif
    endfor
    if empty(m)
      throw 'Unknown token: ' . strpart(self.input, self.i)
    endif
  endwhile
  return self.token('EOF', '<EOF>')
endfunction

let s:Parser = {}

function s:Parser.new(...)
  let obj = copy(self)
  call call(obj.__init__, a:000, obj)
  return obj
endfunction

function s:Parser.__init__(tokenizer)
  let self.tokenizer = a:tokenizer
endfunction

function s:Parser.node(type, value)
  return {'type': a:type, 'value': a:value}
endfunction

function s:Parser.parse()
  let ast = []
  while 1
    let token = self.tokenizer.peek()
    if token.type == 'EOF'
      break
    elseif token.type == 'NEWLINE'
      call self.tokenizer.get()
    else
      let node = self.parse_statement()
      call add(ast, node)
    endif
  endwhile
  return self.node('BEGIN', ast)
endfunction

function s:Parser.parse_newline()
  let token = self.tokenizer.peek()
  if token.type == 'NEWLINE' || token.type == 'EOF'
    call self.tokenizer.get()
    return
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_statement()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD'
    if token.value ==? 'IF'
      return self.parse_if()
    elseif token.value ==? 'WHILE'
      return self.parse_while()
    elseif token.value ==? 'CONTINUE'
      return self.parse_continue()
    elseif token.value ==? 'BREAK'
      return self.parse_break()
    elseif token.value ==? 'FUNCTION'
      return self.parse_function()
    elseif token.value ==? 'RETURN'
      return self.parse_return()
    else
      throw 'Unexpected token: ' . token.value
    endif
  else
    let node = self.parse_exp()
    call self.parse_newline()
    let node = self.node('PRINT', node)
    return node
  endif
endfunction

function s:Parser.parse_if()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD' && token.value =~ '\v\c^%(IF|ELSEIF)$'
    call self.tokenizer.get()
    let cond = self.parse_exp()
    call self.parse_newline()
    let ifblock = self.node('IF',
          \ [cond, self.node('BEGIN', []), self.node('BEGIN', [])])
    let block = ifblock.value[1]
    while 1
      let token = self.tokenizer.peek()
      if token.type == 'KEYWORD' && token.value ==? 'ELSEIF'
        if block is ifblock.value[2]
          throw 'Erorr: elseif after else'
        endif
        let ifblock.value[2] = self.parse_if()
        break
      elseif token.type == 'KEYWORD' && token.value ==? 'ELSE'
        if block is ifblock.value[2]
          throw 'Error: multiple else'
        endif
        call self.tokenizer.get()
        call self.parse_newline()
        let block = ifblock.value[2]
      elseif token.type == 'KEYWORD' && token.value ==? 'ENDIF'
        call self.tokenizer.get()
        call self.parse_newline()
        break
      else
        let statement = self.parse_statement()
        call add(block.value, statement)
      endif
    endwhile
    return ifblock
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_while()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD' && token.value ==? 'WHILE'
    call self.tokenizer.get()
    let cond = self.parse_exp()
    call self.parse_newline()
    let whileblock = self.node('WHILE', [cond, self.node('BEGIN', [])])
    let block = whileblock.value[1]
    while 1
      let token = self.tokenizer.peek()
      if token.type == 'KEYWORD' && token.value ==? 'ENDWHILE'
        call self.tokenizer.get()
        call self.parse_newline()
        break
      else
        let statement = self.parse_statement()
        call add(block.value, statement)
      endif
    endwhile
    return whileblock
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_continue()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD' && token.value ==? 'CONTINUE'
    call self.tokenizer.get()
    call self.parse_newline()
    return self.node('CONTINUE', [])
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_break()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD' && token.value ==? 'BREAK'
    call self.tokenizer.get()
    call self.parse_newline()
    return self.node('BREAK', [])
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_function()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD' && token.value ==? 'FUNCTION'
    call self.tokenizer.get()
    let token = self.tokenizer.peek()
    if token.type != 'IDENTIFIER'
      throw 'Unexpected token: ' . token.value
    endif
    call self.tokenizer.get()
    let name = token.value
    let token = self.tokenizer.peek()
    if token.type != 'LPAR'
      throw 'Unexpected token: ' . token.value
    endif
    call self.tokenizer.get()
    let args = []
    while 1
      let token = self.tokenizer.peek()
      if token.type == 'IDENTIFIER'
        call self.tokenizer.get()
        call add(args, token.value)
        let token = self.tokenizer.peek()
        if token.type == 'COMMA'
          call self.tokenizer.get()
        endif
      elseif token.type == 'RPAR'
        call self.tokenizer.get()
        break
      else
        throw 'Unexpected token: ' . token.value
      endif
    endwhile
    call self.parse_newline()
    let funblock = self.node('FUNCTION', [name, args, self.node('BEGIN', [])])
    let block = funblock.value[2]
    while 1
      let token = self.tokenizer.peek()
      if token.type == 'KEYWORD' && token.value ==? 'ENDFUNCTION'
        call self.tokenizer.get()
        call self.parse_newline()
        break
      else
        let node = self.parse_statement()
        call add(block.value, node)
      endif
    endwhile
    return funblock
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_return()
  let token = self.tokenizer.peek()
  if token.type == 'KEYWORD' && token.value ==? 'RETURN'
    call self.tokenizer.get()
    let token = self.tokenizer.peek()
    if token.type == 'NEWLINE' || token.type == 'EOF'
      let value = self.node('NUMBER', 0)
    else
      let value = self.parse_exp()
    endif
    call self.parse_newline()
    return self.node('RETURN', value)
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_exp()
  return self.parse_assignment_exp()
endfunction

function s:Parser.parse_assignment_exp()
  let lhs = self.parse_conditional_exp()
  let token = self.tokenizer.peek()
  if token.type == 'EQ'
    call self.tokenizer.get()
    let rhs = self.parse_assignment_exp()
    let lhs = self.node('EQ', [lhs, rhs])
  endif
  return lhs
endfunction

function s:Parser.parse_conditional_exp()
  let lhs = self.parse_logical_or_exp()
  let token = self.tokenizer.peek()
  if token.type == 'QUESTION'
    call self.tokenizer.get()
    let t = self.parse_exp()
    let token = self.tokenizer.peek()
    if token.type != 'COLON'
      throw 'Unexpected token: ' . token.value
    endif
    call self.tokenizer.get()
    let e = self.parse_conditional_exp()
    let lhs = self.node('CONDEXP', [lhs, t, e])
  endif
  return lhs
endfunction

function s:Parser.parse_logical_or_exp()
  let lhs = self.parse_logical_and_exp()
  let token = self.tokenizer.peek()
  while token.type == 'LOGOR'
    call self.tokenizer.get()
    let rhs = self.parse_logical_and_exp()
    let lhs = self.node('LOGOR', [lhs, rhs])
    let token = self.tokenizer.peek()
  endwhile
  return lhs
endfunction

function s:Parser.parse_logical_and_exp()
  let lhs = self.parse_equality_exp()
  let token = self.tokenizer.peek()
  while token.type == 'LOGAND'
    call self.tokenizer.get()
    let rhs = self.parse_equality_exp()
    let lhs = self.node('LOGAND', [lhs, rhs])
    let token = self.tokenizer.peek()
  endwhile
  return lhs
endfunction

function s:Parser.parse_equality_exp()
  let lhs = self.parse_relational_exp()
  let token = self.tokenizer.peek()
  while token.type =~ '\v^%(EQEQ|NOTEQ)$'
    call self.tokenizer.get()
    if token.type == 'EQEQ'
      let rhs = self.parse_relational_exp()
      let lhs = self.node('EQEQ', [lhs, rhs])
    elseif token.type == 'NOTEQ'
      let rhs = self.parse_relational_exp()
      let lhs = self.node('NOTEQ', [lhs, rhs])
    endif
    let token = self.tokenizer.peek()
  endwhile
  return lhs
endfunction

function s:Parser.parse_relational_exp()
  let lhs = self.parse_additive_exp()
  let token = self.tokenizer.peek()
  while token.type =~ '\v^%(LT|GT|LTEQ|GTEQ)$'
    call self.tokenizer.get()
    if token.type == 'LT'
      let rhs = self.parse_additive_exp()
      let lhs = self.node('LT', [lhs, rhs])
    elseif token.type == 'GT'
      let rhs = self.parse_additive_exp()
      let lhs = self.node('GT', [lhs, rhs])
    elseif token.type == 'LTEQ'
      let rhs = self.parse_additive_exp()
      let lhs = self.node('LTEQ', [lhs, rhs])
    elseif token.type == 'GTEQ'
      let rhs = self.parse_additive_exp()
      let lhs = self.node('GTEQ', [lhs, rhs])
    endif
    let token = self.tokenizer.peek()
  endwhile
  return lhs
endfunction

function s:Parser.parse_additive_exp()
  let lhs = self.parse_mult_exp()
  let token = self.tokenizer.peek()
  while token.type =~ '\v^%(ADD|SUB)$'
    call self.tokenizer.get()
    if token.type == 'ADD'
      let rhs = self.parse_mult_exp()
      let lhs = self.node('ADD', [lhs, rhs])
    elseif token.type == 'SUB'
      let rhs = self.parse_mult_exp()
      let lhs = self.node('SUB', [lhs, rhs])
    endif
    let token = self.tokenizer.peek()
  endwhile
  return lhs
endfunction

function s:Parser.parse_mult_exp()
  let lhs = self.parse_unary_exp()
  let token = self.tokenizer.peek()
  while token.type =~ '\v^%(MUL|DIV|MOD)$'
    call self.tokenizer.get()
    if token.type == 'MUL'
      let rhs = self.parse_unary_exp()
      let lhs = self.node('MUL', [lhs, rhs])
    elseif token.type == 'DIV'
      let rhs = self.parse_unary_exp()
      let lhs = self.node('DIV', [lhs, rhs])
    elseif token.type == 'MOD'
      let rhs = self.parse_unary_exp()
      let lhs = self.node('MOD', [lhs, rhs])
    endif
    let token = self.tokenizer.peek()
  endwhile
  return lhs
endfunction

function s:Parser.parse_unary_exp()
  let token = self.tokenizer.peek()
  if token.type == 'ADD'
    call self.tokenizer.get()
    let opr = self.parse_unary_exp()
    return self.node('PLUS', opr)
  elseif token.type == 'SUB'
    call self.tokenizer.get()
    let opr = self.parse_unary_exp()
    return self.node('MINUS', opr)
  else
    return self.parse_postfix_exp()
  endif
endfunction

function s:Parser.parse_postfix_exp()
  let opr = self.parse_primary_exp()
  return opr
endfunction

function s:Parser.parse_primary_exp()
  let token = self.tokenizer.peek()
  if token.type == 'IDENTIFIER'
    call self.tokenizer.get()
    let name = token.value
    let token = self.tokenizer.peek()
    if token.type == 'LPAR'
      let args = self.parse_args()
      return self.node('CALL', [name, args])
    else
      return self.node('IDENTIFIER', name)
    endif
  elseif token.type == 'NUMBER'
    call self.tokenizer.get()
    return self.node('NUMBER', str2float(token.value))
  elseif token.type == 'LPAR'
    call self.tokenizer.get()
    let opr = self.parse_exp()
    let token = self.tokenizer.peek()
    if token.type != 'RPAR'
      throw 'Unexpected token: ' . token.value
    endif
    call self.tokenizer.get()
    return opr
  else
    throw 'Unexpected token: ' . token.value
  endif
endfunction

function s:Parser.parse_args()
  let args = []
  let token = self.tokenizer.peek()
  if token.type != 'LPAR'
    throw 'Unexpected token: ' . token.value
  endif
  call self.tokenizer.get()
  while 1
    let token = self.tokenizer.peek()
    if token.type == 'RPAR'
      call self.tokenizer.get()
      break
    else
      let node = self.parse_exp()
      call add(args, node)
      let token = self.tokenizer.peek()
      if token.type == 'COMMA'
        call self.tokenizer.get()
      elseif token.type != 'RPAR'
        throw 'Unexpected token: ' . token.value
      endif
    endif
  endwhile
  return args
endfunction

let s:Compiler = {}

function s:Compiler.new(...)
  let obj = copy(self)
  call call(obj.__init__, a:000, obj)
  return obj
endfunction

function s:Compiler.__init__()
endfunction

function s:Compiler.compile(ast)
  let code = []
  if a:ast.type == 'BEGIN'
    for node in a:ast.value
      call extend(code, self.compile(node))
    endfor
  elseif a:ast.type == 'IDENTIFIER'
    call add(code, self.insn('IDENTIFIER', a:ast.value))
  elseif a:ast.type == 'NUMBER'
    call add(code, self.insn('NUMBER', a:ast.value))
  elseif a:ast.type == 'ADD'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('ADD', []))
  elseif a:ast.type == 'SUB'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('SUB', []))
  elseif a:ast.type == 'MUL'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('MUL', []))
  elseif a:ast.type == 'DIV'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('DIV', []))
  elseif a:ast.type == 'MOD'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('MOD', []))
  elseif a:ast.type == 'PLUS'
    call extend(code, self.compile(a:ast.value))
    call add(code, self.insn('PLUS', []))
  elseif a:ast.type == 'MINUS'
    call extend(code, self.compile(a:ast.value))
    call add(code, self.insn('MINUS', []))
  elseif a:ast.type == 'EQ'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('ASSIGN', []))
  elseif a:ast.type == 'EQEQ'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('EQEQ', []))
  elseif a:ast.type == 'NOTEQ'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('NOTEQ', []))
  elseif a:ast.type == 'LT'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('LT', []))
  elseif a:ast.type == 'GT'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('GT', []))
  elseif a:ast.type == 'LTEQ'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('LTEQ', []))
  elseif a:ast.type == 'GTEQ'
    call extend(code, self.compile(a:ast.value[0]))
    call extend(code, self.compile(a:ast.value[1]))
    call add(code, self.insn('GTEQ', []))
  elseif a:ast.type == 'LOGOR'
    let lhs = self.compile(a:ast.value[0])
    let rhs = self.compile(a:ast.value[1])
    call extend(code, lhs)
    call add(code, self.insn('COPY', []))
    call add(code, self.insn('BRANCHT', len(rhs) + 1))
    call add(code, self.insn('POP', []))
    call extend(code, rhs)
  elseif a:ast.type == 'LOGAND'
    let lhs = self.compile(a:ast.value[0])
    let rhs = self.compile(a:ast.value[1])
    call extend(code, lhs)
    call add(code, self.insn('COPY', []))
    call add(code, self.insn('BRANCHF', len(rhs) + 1))
    call add(code, self.insn('POP', []))
    call extend(code, rhs)
  elseif a:ast.type == 'CONDEXP'
    let c = self.compile(a:ast.value[0])
    let t = self.compile(a:ast.value[1])
    let e = self.compile(a:ast.value[2])
    call extend(code, c)
    call add(code, self.insn('BRANCHT', len(e) + 1))
    call extend(code, e)
    call add(code, self.insn('BRANCH', len(t)))
    call extend(code, t)
  elseif a:ast.type == 'IF'
    let c = self.compile(a:ast.value[0])
    let t = self.compile(a:ast.value[1])
    let e = self.compile(a:ast.value[2])
    call extend(code, c)
    call add(code, self.insn('BRANCHT', len(e) + 1))
    call extend(code, e)
    call add(code, self.insn('BRANCH', len(t)))
    call extend(code, t)
  elseif a:ast.type == 'WHILE'
    let c = self.compile(a:ast.value[0])
    let t = self.compile(a:ast.value[1])
    for i in range(len(t))
      if t[i].type == 'CONTINUE'
        let t[i] = self.insn('BRANCH', -(i + 1 + (len(c) - 1) + 2))
      elseif t[i].type == 'BREAK'
        let t[i] = self.insn('BRANCH', (len(t) - i - 1) + 1)
      endif
    endfor
    call extend(code, c)
    call add(code, self.insn('BRANCHF', len(t) + 1))
    call extend(code, t)
    call add(code, self.insn('BRANCH', -(len(t) + 1 + (len(c) - 1) + 2)))
  elseif a:ast.type == 'CONTINUE'
    call add(code, self.insn('CONTINUE', 0))
  elseif a:ast.type == 'BREAK'
    call add(code, self.insn('BREAK', 0))
  elseif a:ast.type == 'FUNCTION'
    let t = self.compile(a:ast.value[2])
    call add(code, self.insn('IDENTIFIER', a:ast.value[0]))
    call add(code, self.insn('FUNCTION', [a:ast.value[1], t]))
    call add(code, self.insn('ASSIGN', []))
    call add(code, self.insn('POP', [])) " remove assign result
  elseif a:ast.type == 'RETURN'
    call extend(code, self.compile(a:ast.value))
    call add(code, self.insn('RETURN', []))
  elseif a:ast.type == 'CALL'
    for arg in a:ast.value[1]
      call extend(code, self.compile(arg))
    endfor
    call add(code, self.insn('IDENTIFIER', a:ast.value[0]))
    call add(code, self.insn('CALL', len(a:ast.value[1])))
  elseif a:ast.type == 'PRINT'
    call extend(code, self.compile(a:ast.value))
    call add(code, self.insn('PRINT', []))
  else
    throw 'Unknown node: ' . string(a:ast)
  endif
  return code
endfunction

function s:Compiler.insn(type, value)
  return {'type': a:type, 'value': a:value}
endfunction

function! s:test()
  let calc = s:Calc.new()
  call calc.eval('42')
  call calc.eval('3 + 4 + 5')
  call calc.eval('3 + 4 * 5')
  call calc.eval('3 * 4 + 5')
  call calc.eval('3 * 4 * 5')
  call calc.eval('1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10')
  call calc.eval('((3 + 4) * 5) / 2')
  call calc.eval('+3')
  call calc.eval('-3')
  call calc.eval('+3 * -3')
  call calc.eval('+3 + -3')
  call calc.eval('3 % 4')
  call calc.eval('5 % 4')
  call calc.eval('x = 32')
  call calc.eval('y = x + 64')
  call calc.eval('y')
  call calc.eval('y == 96')
  call calc.eval('y != 96')
  call calc.eval('1 == 1 ? 2 : 3')
  call calc.eval('1 != 1 ? 2 : 3')
  call calc.eval('1 != 1 && 1 == 1 ? 2 + 90 : 3 + 80')
  call calc.eval('1 != 1 || 1 == 1 ? 2 + 90 : 3 + 80')
  call calc.eval(
        \   "if 1\n"
        \ . "  2\n"
        \ . "else\n"
        \ . "  3\n"
        \ . "endif")
  call calc.eval(
        \   "if 0\n"
        \ . "  2\n"
        \ . "else\n"
        \ . "  3\n"
        \ . "endif")
  call calc.eval(
        \   "if 0\n"
        \ . "  2\n"
        \ . "elseif 1\n"
        \ . "  4\n"
        \ . "else\n"
        \ . "  3\n"
        \ . "endif")
  call calc.eval(
        \   "x = 0\n"
        \ . "while x < 10\n"
        \ . "  x = x + 1\n"
        \ . "endwhile")
  call calc.eval(
        \   "x = 0\n"
        \ . "while 1\n"
        \ . "  x = x + 1\n"
        \ . "  if x > 5\n"
        \ . "    break\n"
        \ . "  else\n"
        \ . "    continue\n"
        \ . "  endif\n"
        \ . "  999\n"
        \ . "endwhile")
  call calc.eval(
        \   "function add(x, y)\n"
        \ . "  return x + y\n"
        \ . "endfunction\n"
        \ . "x = 10 * add(1, 2)")
  call calc.eval(
        \   "function cmp(x, y)\n"
        \ . "  if x < y\n"
        \ . "    return -1\n"
        \ . "  elseif x > y\n"
        \ . "    return 1\n"
        \ . "  else\n"
        \ . "    return 0\n"
        \ . "  endif\n"
        \ . "endfunction\n"
        \ . "cmp(1, 1)\n"
        \ . "cmp(1, 2)\n"
        \ . "cmp(2, 1)\n")
  call calc.eval(
        \   "function f(x)\n"
        \ . "  function g(y)\n"
        \ . "    return x + y\n"
        \ . "  endfunction\n"
        \ . "  return g\n"
        \ . "endfunction\n"
        \ . "x = f(100)\n"
        \ . "x(23)")
  call calc.eval(
        \   "function fib(n)\n"
        \ . "  if n < 2\n"
        \ . "    return n\n"
        \ . "  else\n"
        \ . "    return fib(n - 1) + fib(n - 2)\n"
        \ . "  endif\n"
        \ . "endfunction\n"
        \ . "fib(6)")
  call calc.eval("1 && (x=200) || (x=500)\nx")
endfunction

call s:test()