Skip to content
LumenaryAcademy
Professional 70 min

A complete project, and where to go next

A small calculator language with variables, functions and helpful error messages, built from sealed types, data classes, recursion and lambdas, and a map of the Kotlin world beyond this course.

Code tested · 2AI-draftedAwaiting review by a computer scientist
MotivationH

Building a little language

Every program that reads structured text, from a compiler to a spreadsheet's formula bar to a database's query engine to a configuration loader, has the same three stages inside it. A tokenizer turns characters into meaningful pieces ("the number 3", "the name area", "the symbol *"). A parser arranges those pieces into a tree that captures their structure ("multiply pi by r squared"). And an evaluator (or, in a compiler, a code generator) walks the tree to produce a result.

This lesson's project is a small calculator language with all three stages. It understands arithmetic with the usual precedence, powers that group from the right, unary minus, parentheses, variables (let r = 3), a few built-in functions (sqrt, abs, min, max), and, most importantly for a tool people will use, it points at the exact column where something went wrong. It is about 230 lines, and it uses most of what this course has taught: sealed interfaces and data classes for tokens, trees and results; exhaustive when expressions; null safety and the Elvis operator for lookups; lambdas stored in a map; extension functions; buildList; and exceptions carrying data.

DefinitionsH

Definitions

Definition— Token

The smallest meaningful unit of the input: a number, a name, a symbol, or the end of the input. Each token here remembers its position, so errors can point at it.

Definition— Precedence and associativity

Precedence decides which operator binds tighter: * before +, so 1 + 2 * 3 is 7. Associativity decides how a chain of the same operator groups: - groups from the left (8 - 2 - 1 is (8 - 2) - 1), while ^ traditionally groups from the right (2 ^ 3 ^ 2 is 2 ^ (3 ^ 2)).

Definition— Abstract syntax tree

A tree representation of an expression with the parentheses and precedence already resolved: 1 + 2 * 3 becomes an addition whose right child is a multiplication.

Definition— Recursive descent

A parsing technique with one function per grammar rule, each calling the functions for the rules below it. Precedence falls out of the call structure: the function for + calls the function for *, which calls the function for ^, and so on down to numbers and parentheses.

The grammar, from lowest to highest precedence, is:

text
statement  = "let" NAME "=" expression | expression
expression = term (("+" | "-") term)*
term       = unary (("*" | "/") unary)*
unary      = "-" unary | power
power      = primary ("^" unary)?
primary    = NUMBER | NAME | NAME "(" arguments ")" | "(" expression ")"

Each line becomes one function in the parser. Notice that power calls unary for its exponent, which permits 2 ^ -1, and that unary sits below power in precedence, so -2 ^ 2 means -(2 ^ 2), as mathematicians expect.

Worked examplesH

Step one: tokens

kotlin
sealed interface Token {
    val pos: Int

    data class Num(val value: Double, override val pos: Int) : Token
    data class Name(val text: String, override val pos: Int) : Token
    data class Sym(val char: Char, override val pos: Int) : Token
    data class End(override val pos: Int) : Token
}

/** An error in the user's input, with the column where it was found. */
class CalcError(message: String, val pos: Int) : Exception(message)

fun tokenize(src: String): List<Token> = buildList {
    var i = 0
    while (i < src.length) {
        val c = src[i]
        val start = i
        when {
            c.isWhitespace() -> i++
            c.isDigit() || c == '.' -> {
                while (i < src.length && (src[i].isDigit() || src[i] == '.')) i++
                val text = src.substring(start, i)
                add(Token.Num(text.toDoubleOrNull() ?: throw CalcError("bad number '$text'", start), start))
            }
            c.isLetter() -> {
                while (i < src.length && (src[i].isLetterOrDigit() || src[i] == '_')) i++
                add(Token.Name(src.substring(start, i), start))
            }
            c in "+-*/^(),=" -> add(Token.Sym(src[i++], start))
            else -> throw CalcError("unexpected '$c'", start)
        }
    }
    add(Token.End(src.length))
}

fun main() {
    tokenize("let area = pi * r ^ 2").forEach(::println)
    try {
        tokenize("3 # 4")
    } catch (e: CalcError) {
        println("error at column ${e.pos + 1}: ${e.message}")
    }
}
text
Name(text=let, pos=0)
Name(text=area, pos=4)
Sym(char==, pos=9)
Name(text=pi, pos=11)
Sym(char=*, pos=14)
Name(text=r, pos=16)
Sym(char=^, pos=18)
Num(value=2.0, pos=20)
End(pos=21)
error at column 3: unexpected '#'

The tokenizer is a loop over characters with a when that decides what kind of token starts here. Three details are worth copying into your own code:

  • buildList { ... } builds the result with add and returns it as a read-only List<Token>; no mutable list escapes the function.
  • Every token carries pos, declared once as an abstract property of the sealed interface and overridden in each case. That small decision is what makes good error messages possible later.
  • Errors are values with positions. CalcError extends Exception with an extra property. text.toDoubleOrNull() ?: throw ... turns "not a number" into a precise error in one line, using the Elvis operator with throw, which has type Nothing.
ComputationC

The complete program

kotlin
import kotlin.math.E
import kotlin.math.PI
import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt

// ---------------------------------------------------------------- tokens

sealed interface Token {
    val pos: Int

    data class Num(val value: Double, override val pos: Int) : Token
    data class Name(val text: String, override val pos: Int) : Token
    data class Sym(val char: Char, override val pos: Int) : Token
    data class End(override val pos: Int) : Token
}

/** An error in the user's input, with the column where it was found. */
class CalcError(message: String, val pos: Int) : Exception(message)

fun tokenize(src: String): List<Token> = buildList {
    var i = 0
    while (i < src.length) {
        val c = src[i]
        val start = i
        when {
            c.isWhitespace() -> i++
            c.isDigit() || c == '.' -> {
                while (i < src.length && (src[i].isDigit() || src[i] == '.')) i++
                val text = src.substring(start, i)
                add(Token.Num(text.toDoubleOrNull() ?: throw CalcError("bad number '$text'", start), start))
            }
            c.isLetter() -> {
                while (i < src.length && (src[i].isLetterOrDigit() || src[i] == '_')) i++
                add(Token.Name(src.substring(start, i), start))
            }
            c in "+-*/^(),=" -> add(Token.Sym(src[i++], start))
            else -> throw CalcError("unexpected '$c'", start)
        }
    }
    add(Token.End(src.length))
}

// ---------------------------------------------------------------- syntax tree and parser

sealed interface Expr {
    data class Num(val value: Double) : Expr
    data class Var(val name: String, val pos: Int) : Expr
    data class Neg(val operand: Expr) : Expr
    data class Binary(val op: Char, val left: Expr, val right: Expr, val pos: Int) : Expr
    data class Call(val name: String, val args: List<Expr>, val pos: Int) : Expr
}

/** A statement is either `let name = expr` or a bare expression. */
sealed interface Statement {
    data class Let(val name: String, val value: Expr) : Statement
    data class Eval(val value: Expr) : Statement
}

/** Recursive descent: one function per precedence level, lowest first. */
class Parser(private val tokens: List<Token>) {
    private var i = 0
    private val peek get() = tokens[i]

    private fun isSym(c: Char) = (peek as? Token.Sym)?.char == c
    private fun expect(c: Char) {
        if (!isSym(c)) throw CalcError("expected '$c'", peek.pos)
        i++
    }

    fun statement(): Statement {
        val first = peek
        val second = tokens.getOrNull(i + 1)
        val result = if (first is Token.Name && first.text == "let" && second is Token.Name) {
            i += 2
            expect('=')
            Statement.Let(second.text, expression())
        } else {
            Statement.Eval(expression())
        }
        if (peek !is Token.End) throw CalcError("unexpected input", peek.pos)
        return result
    }

    private fun expression(): Expr {                         // + and -, left to right
        var left = term()
        while (isSym('+') || isSym('-')) {
            val op = tokens[i++] as Token.Sym
            left = Expr.Binary(op.char, left, term(), op.pos)
        }
        return left
    }

    private fun term(): Expr {                               // * and /, left to right
        var left = unary()
        while (isSym('*') || isSym('/')) {
            val op = tokens[i++] as Token.Sym
            left = Expr.Binary(op.char, left, unary(), op.pos)
        }
        return left
    }

    private fun unary(): Expr =                              // -x binds looser than ^, so -2^2 = -4
        if (isSym('-')) { i++; Expr.Neg(unary()) } else power()

    private fun power(): Expr {                              // ^, right to left: 2^3^2 = 2^9
        val base = primary()
        if (!isSym('^')) return base
        val op = tokens[i++] as Token.Sym
        return Expr.Binary('^', base, unary(), op.pos)
    }

    private fun primary(): Expr = when (val t = tokens[i]) {
        is Token.Num -> { i++; Expr.Num(t.value) }
        is Token.Name -> {
            i++
            if (isSym('(')) Expr.Call(t.text, arguments(), t.pos) else Expr.Var(t.text, t.pos)
        }
        is Token.Sym if t.char == '(' -> {
            i++
            expression().also { expect(')') }
        }
        else -> throw CalcError("expected a value", t.pos)
    }

    private fun arguments(): List<Expr> = buildList {
        expect('(')
        if (!isSym(')')) {
            add(expression())
            while (isSym(',')) { i++; add(expression()) }
        }
        expect(')')
    }
}

// ---------------------------------------------------------------- evaluation

class Calculator {
    private val variables = mutableMapOf("pi" to PI, "e" to E)

    private val functions: Map<String, (List<Double>) -> Double> = mapOf(
        "sqrt" to { args -> sqrt(args.single()) },
        "abs" to { args -> abs(args.single()) },
        "max" to { args -> args.max() },
        "min" to { args -> args.min() },
    )

    private fun eval(e: Expr): Double = when (e) {
        is Expr.Num -> e.value
        is Expr.Var -> variables[e.name] ?: throw CalcError("unknown variable '${e.name}'", e.pos)
        is Expr.Neg -> -eval(e.operand)
        is Expr.Call -> {
            val f = functions[e.name] ?: throw CalcError("unknown function '${e.name}'", e.pos)
            val args = e.args.map(::eval)
            runCatching { f(args) }.getOrElse { throw CalcError("wrong arguments for ${e.name}", e.pos) }
        }
        is Expr.Binary -> {
            val a = eval(e.left)
            val b = eval(e.right)
            when (e.op) {
                '+' -> a + b
                '-' -> a - b
                '*' -> a * b
                '/' -> if (b == 0.0) throw CalcError("division by zero", e.pos) else a / b
                '^' -> a.pow(b)
                else -> error("unknown operator ${e.op}")      // the parser never produces one
            }
        }
    }

    /** Runs one line: a value, an assignment, or a failure with the column to point at. */
    fun run(line: String): Reply = try {
        when (val s = Parser(tokenize(line)).statement()) {
            is Statement.Let -> {
                val value = eval(s.value)
                variables[s.name] = value
                Reply.Value("${s.name} = ${value.pretty()}")
            }
            is Statement.Eval -> Reply.Value(eval(s.value).pretty())
        }
    } catch (e: CalcError) {
        Reply.Failure(e.pos, e.message ?: "error")
    }
}

sealed interface Reply {
    data class Value(val text: String) : Reply
    data class Failure(val pos: Int, val message: String) : Reply
}

/** Whole numbers without a trailing .0; everything else as Kotlin prints doubles. */
fun Double.pretty(): String = if (this % 1.0 == 0.0 && abs(this) < 1e15) toLong().toString() else toString()

// ---------------------------------------------------------------- demo and self-checks

fun main() {
    val script = """
        1 + 2 * 3
        (1 + 2) * 3
        2 ^ 3 ^ 2
        -2 ^ 2
        let r = 3
        let area = pi * r ^ 2
        max(r, 10, area / 2)
        sqrt(2) * sqrt(2)
        10 / (r - 3)
        2 * (r + 1
        foo(1) + 1
        r * height
        3 # 4
    """.trimIndent()

    val calc = Calculator()
    for (line in script.lines()) {
        println(">>> $line")
        when (val reply = calc.run(line)) {
            is Reply.Value -> println("    ${reply.text}")
            is Reply.Failure -> println(" ".repeat(4 + reply.pos) + "^ ${reply.message}")
        }
    }

    val fresh = Calculator()
    val checks = listOf(
        fresh.run("2 + 3 * 4") == Reply.Value("14"),
        fresh.run("2 ^ -1") == Reply.Value("0.5"),
        fresh.run("let x = 4") == Reply.Value("x = 4"),
        fresh.run("x * x - x") == Reply.Value("12"),
        fresh.run("min(5, x, 9)") == Reply.Value("4"),
        fresh.run("1 / 0") == Reply.Failure(2, "division by zero"),
        fresh.run("sqrt(1, 2)") == Reply.Failure(0, "wrong arguments for sqrt"),
    )
    check(checks.all { it }) { "self-check failed: $checks" }
    println("${checks.size} self-checks passed")
}
text
>>> 1 + 2 * 3
    7
>>> (1 + 2) * 3
    9
>>> 2 ^ 3 ^ 2
    512
>>> -2 ^ 2
    -4
>>> let r = 3
    r = 3
>>> let area = pi * r ^ 2
    area = 28.274333882308138
>>> max(r, 10, area / 2)
    14.137166941154069
>>> sqrt(2) * sqrt(2)
    2.0000000000000004
>>> 10 / (r - 3)
       ^ division by zero
>>> 2 * (r + 1
              ^ expected ')'
>>> foo(1) + 1
    ^ unknown function 'foo'
>>> r * height
        ^ unknown variable 'height'
>>> 3 # 4
      ^ unexpected '#'
7 self-checks passed
Worked examplesH

Reading the output, and one parse traced

Each input line is echoed after >>>, followed by either its value or a caret under the column where the problem was found. The successful lines confirm the grammar: 1 + 2 * 3 is 7 (precedence), 2 ^ 3 ^ 2 is 512 (right associativity), -2 ^ 2 is −4 (unary minus binds looser than ^), and the let lines store variables that later lines use. The failures are the interesting part. 10 / (r - 3) points at the /, because the evaluator found a zero divisor there. 2 * (r + 1 points just past the end of the input, where the parser expected a closing parenthesis. foo(1) + 1 and r * height point at the unknown names, and 3 # 4 at the character the tokenizer could not understand. Each message names what was expected or what was wrong, which is what a user needs to fix it.

Example— Parsing 1 + 2 * 3

The tokens are Num(1), Sym(+), Num(2), Sym(*), Num(3), End.

  1. statement sees no let, so it calls expression.
  2. expression calls term for its first operand. term calls unary, which calls power, which calls primary: that consumes 1 and returns Num(1). power sees no ^, term sees no * or /, so term returns Num(1).
  3. Back in expression, the next token is +, so it consumes it and calls term for the right operand.
  4. This term gets Num(2) the same way, then sees *, consumes it, and calls unary for its right operand, which yields Num(3). It returns Binary(*, Num(2), Num(3)).
  5. expression builds Binary(+, Num(1), Binary(*, Num(2), Num(3))) and, seeing End, returns it.

The multiplication ended up inside the addition, not because of any precedence table, but because term (which handles *) is called from within expression (which handles +). Deeper in the call chain means tighter binding. Evaluating the tree from the leaves up gives 1 + 6 = 7.

Design decisions and their trade-offs

  • A hand-written parser or a generator? Tools such as ANTLR generate parsers from a grammar file, and they are the right choice for large languages. For a small grammar, recursive descent by hand is short, needs no build step, and makes it easy to produce precise error messages, which is why many production compilers (including Kotlin's own) parse by hand.
  • Exceptions inside, values at the edge. Inside the tokenizer, parser and evaluator, an error throws CalcError, because unwinding through many nested calls is exactly what exceptions are good at. At the public boundary, run converts it into a Reply, so callers handle every outcome with an exhaustive when and cannot forget the failure case.
  • Immutable trees, mutable environment. The syntax tree is made of data classes and never changes after parsing; only the variable map changes, and only in one place. That separation makes the tree easy to test, print and reuse.
ExplanationH

How it fits together

The parser mirrors the grammar. expression, term, unary, power and primary correspond line for line to the grammar above. In expression, the loop while (isSym('+') || isSym('-')) builds a left-leaning tree, which is what makes - left-associative. In power, the exponent is parsed by a recursive call (through unary, which reaches power again), which builds a right-leaning tree: 2 ^ 3 ^ 2 became 2 ^ (3 ^ 2) = 2⁹ = 512. primary is a when with a guard (is Token.Sym if t.char == '('), a Kotlin 2.2 feature, and its else branch produces the "expected a value" error.

The evaluator is one exhaustive when. Because Expr is sealed, the compiler checks that eval handles every kind of node. Adding a new node type (say, a conditional expression) would make eval fail to compile until it was handled, the safety net from Classes, data classes, sealed classes and objects. Variables are looked up in a map, and a missing one becomes an error through ?: throw.

Built-in functions are data. functions maps names to lambdas of type (List<Double>) -> Double. Adding round or log is one line. Calling sqrt with two arguments makes args.single() throw, and runCatching { ... }.getOrElse { ... } turns that into a user-facing error rather than a crash.

Results are a sealed type too. run returns a Reply that is either a Value or a Failure with a position, and never throws for bad input. main decides how to show each: values indented, failures as a caret under the offending column. Because Reply cases are data classes, the self-checks compare whole replies with ==, including positions.

Floating point is honest. sqrt(2) * sqrt(2) printed 2.0000000000000004, because doubles are binary fractions, exactly as in Values, types and null safety. A calculator for money would use BigDecimal instead. The pretty extension only hides the .0 of whole numbers.

Where to take it next. Good extensions, in rising order of difficulty: a % operator; more functions; comparison operators and an if(condition, a, b) function; user-defined functions (let square(x) = x * x, which needs a new statement type and environments for parameters); and moving the self-checks into a Gradle project with kotlin.test, as in the previous lesson. Because the core uses only the Kotlin standard library (apart from pow and sqrt, which exist on every Kotlin platform), it could be shared through Kotlin Multiplatform with an Android app, an iOS app and a web page.

Further reading

Where to go next

Kotlin is used in a few distinct worlds, and the next step depends on which you want to enter:

  • Android. Start from Google's Kotlin on Android pages, and learn Jetpack Compose, the declarative user-interface toolkit written in Kotlin; coroutines and flows from this course are used throughout modern Android code.
  • Servers. Ktor is JetBrains' coroutine-based framework for HTTP servers and clients; Spring supports Kotlin fully, including coroutines in its reactive stack. Either is a good home for the patterns in this course: data classes for requests and responses, sealed types for results, suspend functions for I/O.
  • Kotlin Multiplatform. Kotlin Multiplatform shares business logic (and, with Compose Multiplatform, user interfaces) across Android, iOS, desktop and the web.
  • The language itself. Kotlin Koans are short exercises on every feature; the language specification answers precise questions; the KEEP repository on GitHub holds the design proposals for new features, with their reasoning. Among books, Kotlin in Action (Manning), written by members of the Kotlin team, is a thorough guide.

Whatever you choose, read good Kotlin code: the standard library's own sources (open any function in IntelliJ IDEA and jump to its definition), kotlinx.coroutines, and well-maintained open-source apps. Idioms are learned by seeing them used well.

Optional Christian reflection · Words that mean something

A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.

A calculator language is a tiny exercise in giving words exact meaning: let r = 3 must mean the same thing every time, for everyone. The Gospel of John opens, "In the beginning was the Word" (John 1:1, King James Version), and Christians have long seen in human language, with its power to name, describe and promise, a reflection of the One who speaks things into being. Programmers handle words for a living. Choosing clear names, writing error messages that tell the truth kindly, and keeping a function's promise to its callers are small ways of honouring the gift.

Exercises

Exercises

1. A complete project, and where to go next

CoreComputational

What value does the calculator give for -3 ^ 2 + 10?

2. A complete project, and where to go next

Warm-upComputational

What value does the calculator give for (2 + 3) * 4 - 6 / 2?

3. A complete project, and where to go next

CoreComputational

What does the calculator show for the line let x = 2 ^ -2? (Give the text of the reply, as main would print it after the indentation.)

4. A complete project, and where to go next

CoreComputational

For the input 1 + * 2, the calculator reports "expected a value". At which column does the caret point, counting the first character of the input as column 1?

5. A complete project, and where to go next

StretchComputational

What error message does the calculator give for max()?

6. A complete project, and where to go next

CoreHuman

Why does 2 ^ 3 ^ 2 evaluate to 512 rather than 64?

Choose one

7. A complete project, and where to go next

StretchHuman

You want to add a remainder operator % with the same precedence as * and /. Which changes are needed? Choose all that apply.

Choose all that apply

Further reading and resources

  • Kotlin Koans · JetBrainsShort exercises covering the whole language, runnable in the browser.
  • Kotlin Multiplatform (Kotlin documentation) · JetBrainsSharing Kotlin code across Android, iOS, desktop, web and servers.
  • Kotlin on Android · GoogleThe starting point for Android development with Kotlin and Jetpack Compose.
  • Ktor · JetBrainsA Kotlin framework for servers and HTTP clients, built on coroutines.
  • SpringThe Java application framework, with first-class Kotlin support.