Minimalist Parser Combinator Library [Kotlin] [WIP]

Combinators.kt

fun <A, B, R> curry2(fn: (A, B) -> R): (A) -> (B) -> R = { a -> { b -> fn(a, b) } }
fun <A, B, C, R> curry3(fn: (A, B, C) -> R): (A) -> (B) -> (C) -> R = { a -> { b -> { c -> fn(a, b, c) } } }
fun <A, B> const(a: A, b: B): A = a
fun <A, B, C> flip(fn: (A, B) -> C): (B, A) -> C = { b, a -> fn(a, b) }

infix fun <A, B> Parser<A>.pairing(p: Parser<B>): Parser<Pair<A, B>> =
        Parser.liftA2(curry2(::Pair), this, p)

infix fun <A> Parser<A>.or(p: Parser<A>): Parser<A> =
        this alt p

infix fun <A> Parser<A>.withError(message: String): Parser<A> =
        this alt Parser.fail(message)

infix fun <A, B> Parser<A>.ignoreThen(p: Parser<B>): Parser<B> =
        Parser.liftA2(curry2(flip(::const)), this, p)

infix fun <A, B> Parser<A>.thenIgnore(p: Parser<B>): Parser<A> =
        Parser.liftA2(curry2(::const), this, p)

fun <A> Parser<A>.lookAhead(): Parser<A> =
        Parser { st -> this.runParser(st) bind { success(it.result, st) } }

infix fun <A> Parser<A>.orDefault(def: A): Parser<A> =
        this or Parser.pure(def)

fun <A> Parser<A>.void(): Parser<Unit> =
        this map { Unit }

fun <A> Parser<A>.rep(min: Int = 0, max: Int = Int.MAX_VALUE): Parser<List<A>> =
        Parser { st0 ->
            val acc = mutableListOf<A>()
            var st = st0
            var failed = false
            while (!failed && !st.eof) {
                val result = this.runParser(st)
                when (result) {
                    is Left -> failed = true
                    is Right -> {
                        acc.add(result.right.result)
                        st = result.right.state
                    }
                }
            }
            if (min > 0 && acc.size < min)
                failure("Expected to parse at least $min items, got ${acc.size}", st0)
            else if (acc.size > max)
                failure("Expected to parse at most $max items, got ${acc.size}", st0)
            else
                success(acc.toList(), st)
        }

val anyChar: Parser<Char> =
        Parser { st ->
            if (st.eof)
                failure("Unexpected EOF", st)
            else
                success(st.currentChar(), st.advance())
        }

val anyDigit: Parser<Char> =
        (anyChar bind {
            if (it.isDigit())
                Parser.pure(it)
            else
                Parser.fail("Expected $it to be a digit")
        }).attempt()

val lowerCaseLetter: Parser<Char> =
        (anyChar bind {
            if (it.isLetter() && it.isLowerCase())
                Parser.pure(it)
            else
                Parser.fail("Expected $it to be a lowercase letter")
        }).attempt()

val upperCaseLetter: Parser<Char> =
        (anyChar bind {
            if (it.isLetter() && it.isUpperCase())
                Parser.pure(it)
            else
                Parser.fail("Expected $it to be a lowercase letter")
        }).attempt()

val anyLetter = lowerCaseLetter or upperCaseLetter withError "Expected a letter"

val alphaNum = anyLetter or anyDigit withError "Expected number or letter"

fun string(s: String, ignoreCase: Boolean = false): Parser<String> =
        Parser { st ->
            when {
                st.eof -> failure("Unexpected EOF", st)
                st.content.regionMatches(st.pos, s, 0, s.length, ignoreCase) ->
                    success(s, st.advance(s.length))
                else -> failure(s, st)
            }
        }

val eof: Parser<Unit> =
        Parser { st ->
            if (st.eof)
                success(Unit, st)
            else
                failure("Expected EOF", st)
        }

fun satisfy(pred: (Char) -> Boolean): Parser<Char> =
        (anyChar bind {
            if (pred(it))
                Parser.pure(it)
            else
                Parser.fail("Character $it did not satisfy the predicate")
        }).attempt()

fun char(c: Char): Parser<Char> =
        satisfy { char -> char == c }

val whitespace: Parser<String> =
        (satisfy { c -> c == '\n' || c == '\t' || c == ' ' || c == '\r' }).rep() map { it.joinToString("") }

val skipWhitespace: Parser<Unit> =
        whitespace.void()

fun regex(pattern: String): Parser<MatchResult> =
        Parser { st ->
            TODO()
        }

Either.kt

sealed class Either<out A, out B> {
    companion object
}
data class Left<A, B>(val left: A) : Either<A, B>()
data class Right<A, B>(val right: B) : Either<A, B>()

private fun <A> id(a: A) = a

infix fun <E, A, B> Either<E, A>.map(fn: (A) -> B): Either<E, B> = when(this) {
    is Left -> Left(this.left)
    is Right -> Right(fn(this.right))
}

infix fun <E, F, A> Either<E, A>.lmap(fn: (E) -> F): Either<F, A> = when(this) {
    is Left -> Left(fn(this.left))
    is Right -> Right(this.right)
}

fun <E, A> Either.Companion.pure(v: A): Either<E, A> = Right(v)

infix fun <E, A, B> Either<E, (A) -> B>.apply(v: Either<E, A>): Either<E, B> = when(this) {
    is Left -> Left(this.left)
    is Right -> when(v) {
        is Left -> Left(v.left)
        is Right -> Right(this.right(v.right))
    }
}

infix fun <E, A, B> Either<E, A>.bind(fn: (A) -> Either<E, B>): Either<E, B> = when(this) {
    is Left -> Left(this.left)
    is Right -> fn(this.right)
}

fun <E, A> Either<E, Either<E, A>>.join(): Either<E, A> = this bind ::id

fun <E, F, A, B> Either<E, A>.bimap(lf: (E) -> F, rf: (A) -> B): Either<F, B> = when(this) {
    is Left -> Left(lf(this.left))
    is Right -> Right(rf(this.right))
}

Parser.kt

//////////////////
// Parser State //
//////////////////

data class ParserState(val content: String, val pos: Int) {
    val eof: Boolean = pos >= content.length
    fun currentChar(): Char = content[pos]

    fun advance(amt: Int = 1): ParserState =
            ParserState(content, pos + amt)

    companion object {
        fun of(input: String): ParserState = ParserState(input, 0)
    }
}

//////////////////
// Parse Result //
//////////////////

data class Failure(val message: String, val state: ParserState)
data class Success<out A>(val result: A, val state: ParserState)
typealias ParseResult<A> = Either<Failure, Success<A>>

// Smart Constructors //
fun <A> success(a: A, state: ParserState): ParseResult<A> = Right(Success(a, state))
fun <A> failure(message: String, state: ParserState): ParseResult<A> = Left(Failure(message, state))

private infix fun <A, B> Success<A>.map(fn: (A) -> B): Success<B> =
        Success(fn(this.result), this.state)

private fun <A> ParseResult<A>.unwrap(): Either<String, A> =
        this.bimap({ it.message }, { it.result })

/////////////////
// Core Parser //
/////////////////

data class Parser<A>(val runParser: (ParserState) -> ParseResult<A>) {
    fun withInput(input: String) =
            runParser(ParserState.of(input))

    fun parse(state: ParserState) =
            runParser(state).unwrap()

    fun parse(input: String) =
            withInput(input).unwrap()

    infix fun <B> map(fn: (A) -> B): Parser<B> =
            Parser { st -> runParser(st) map { it map fn } }

    infix fun <B> bind(fn: (A) -> Parser<B>): Parser<B> =
            Parser { st -> runParser(st) bind { fn(it.result).runParser(it.state) } }

    infix fun alt(other: Parser<A>): Parser<A> =
            Parser { st ->
                val result = runParser(st)
                when(result) {
                    is Left -> other.runParser(st)
                    is Right -> result
                }
            }

    fun attempt(): Parser<A> =
            Parser { st -> runParser(st) lmap { Failure(it.message, st) } }

    companion object {
        fun <A> pure(a: A): Parser<A> =
                Parser { st -> success(a, st) }

        fun <A> fail(message: String): Parser<A> =
                Parser { st -> failure<A>(message, st) }

        fun <A, B, C> liftA2(fn: (A) -> (B) -> C, p1: Parser<A>, p2: Parser<B>): Parser<C> =
                (p1 map fn) ap p2

        fun <A, B, C> liftA2(fn: (A, B) -> C, p1: Parser<A>, p2: Parser<B>): Parser<C> =
                liftA2({ a: A -> { b: B -> fn(a, b) } }, p1, p2)

        infix fun <A, B> Parser<(A) -> B>.ap(v: Parser<A>): Parser<B> =
                Parser { st ->
                    runParser(st) bind { s1 ->
                        v.runParser(s1.state) bind { s2 ->
                            Parser.pure(s1.result(s2.result)).runParser(s2.state)
                        }
                    }
                }
    }
}