lambda.rb

def lit(expected, &action)
  -> input {
    if input[0 ... expected.size] == expected
      node = [:lit, expected]
      node = action.call(node) if action
      [node, input[expected.size .. -1]]
    end
  }
end

def exp(pattern, &action)
  -> input {
    mdata = pattern.match(input)
    if mdata and mdata.offset(0).first == 0
      a, b = mdata.offset(0)
      node = [:lit, input[a ... b]]
      node = action.call(node) if action
      [node, input[b .. -1]]
    end
  }
end

def seq(*tokens, &action)
  -> input {
    result = tokens.inject([[], input]) do |state, token|
      next unless state
      matches, input = state

      res = token.call(input)
      next unless res

      match, remain = res
      [matches + [match], remain]
    end

    if result
      node = [:seq, result[0]]
      node = action.call(node) if action
      [node, result[1]]
    end
  }
end

def rep(n, token)
  -> input {
    matches, k = [], n
    result = nil

    loop do
      res = token.call(input)
      if res
        matches << res[0]
        input    = res[1]
        k       -= 1
      else
        if k <= 0
          node = [:seq, matches]
          result = [node, input]
        end
        break
      end
    end

    result
  }
end

def alt(*tokens)
  -> input {
    tokens.inject(nil) { |state, token| state || token.call(input) }
  }
end

def ref(name)
  -> input {
    Kernel.const_get(name).call(input)
  }
end



ATOM = alt(ref(:PAREN_EXPR), ref(:ABSTRACTION), ref(:VARIABLE))

EXPRESSION = alt(ref(:APPLICATION), ATOM)

WS_0 = rep(0, lit(' '))
WS_1 = rep(1, lit(' '))

PAREN_EXPR = seq(lit('('), WS_0, EXPRESSION, WS_0, lit(')')) { |_, elements|
  elements[2]
}

VARIABLE = exp(/[a-z]/) { |_, name|
  [:var, name]
}

ABSTRACTION = seq(lit('λ'), VARIABLE, lit('.'), WS_0, EXPRESSION) { |_, elements|
  [:abs, elements[1], elements[4]]
}

# this won't work because application is left-associative but this produces a
# right-associative parse

APP = seq(ATOM, WS_1, EXPRESSION) { |_, elements|
  [:app, elements[0], elements[2]]
}

# so we need to do some shenanigans to parse a flat list of arguments and then
# convert this into a left-fold

APPLICATION = seq(ATOM, rep(1, seq(WS_1, ATOM))) { |_, (op, args)|
  args = args.last.map { |_, e| e.last }
  ([op] + args).inject { |a, b| [:app, a, b] }
}



tree, remain = EXPRESSION.call('(λx. x) y z')
p tree
p remain