Implementing an equation parser using functional paradigm

A Transition from C# to F#

Recently, I have become interested in functional paradigms. Learning about it makes me rethink my inner intuition of C# and programming in general. I simply prompted an LLM agent for simple project ideas that would improve my beginner functional programming skill. At first I implemented small projects like writing a kanban board with console UI.

Then I started a project to build a simple equation parser to convert expressions into an abstract syntax tree for calculating the expression. (Supporting + - * / and () operators with * / having operator precedence)

I tried to minimize the help coming from outer sources and maximize my own ingenuity. I only knew the application should have a string mathematical expression as an input and its result as output. My only clue for building a tree structure was the project name itself. It took multiple attempts before I figured out what a reasonable architecture could be. Initially I thought I can finish it within a few hours, eventually I needed a week with a few hours of work every day.

Learning about F# (or another functional programming language alike) helps a lot adopting modern C# techniques. It is not a coincidence that most of the modern C# features are actually coming from the functional paradigm. (lambda, higher order function, records, switch expression).

Functional Programming (FP) and Object-Oriented Programming (OOP) solve the same problems using fundamentally different abstractions. I felt as if I had to adopt a new thinking, orthogonal to the typical OOP solution.

OOP emphasizes nouns. What should achieve something, the verbs (methods) can only exist in relation to the noun. It tends to be stateful because it models systems as objects that change their internal data over time. Any instance method has implicitly the this parameter allowing changes in the object state.

On the other hand FP emphasizes verbs that act on immutable data transformations rather than state changes. It transforms, combines, or analyzes data without causing side effects.

What I like more in FP:

* No exceptions but discriminated unions: Exceptions are avoided in functional programming because hidden outputs break referential transparency. FP utilizes the Result pattern, where a function returns either a value or an error type. On the caller side, you must use pattern matching to handle every case. While this remotely resembles “throwing and catching an exception,” there is a fundamental difference. With exception the return type does not encode the error case. You no longer get a well-defined result from the method because errors are not part of the return type. I believe the Java development team tried to solve this by adding checked exceptions. However, this approach makes things worse, as checked exceptions violate the Open/Closed Principle. Every intermediate layer must be adjusted when changes occur, even if it doesn’t handle the error itself. In C#, a common solution is using helper NuGet packages such as OneOf.

Example:

//typical approach

public int BusinessLogic(Tree<AstNode> tree){
    //If cannot cast exception is thrown
    //The method no longer has a well defined behavior for every input
    //The unhappy paths can be handled with statements
    Operator op = (Operator)tree;
    //logic

}

let rec CalculateTree (tree: Tree<AstNode>) =
    match tree with
    | Leaf(Number n) -> Ok n
    | Node(Operator operator, left, right) ->
        match CalculateTree left, CalculateTree right with
        | Ok l, Ok r -> Ok(operator.Calculate l r)
        | _ -> Error “Incorrect abstract syntax tree”
    | _ -> Error “Incorrect abstract syntax tree”

# Consume:

    match CalculateTree lastOperator with
    | Ok resultValue -> printfn $”Happy path the number is: %d{resultValue}”
    | Error errorValue -> printfn $”Unhappy path, %s{errorValue}”

//Psuedo Result class

public Result<int> BusinessLogic(Tree<AstNode> tree){
    Operator op = tree as Operator;
    if(op is null) {
        return Errors(“unhappy path with an error”)
    }
    //logic
    return Ok(number);

}

public void Calculate(){
    var result = BusinessLogic(MyAstNodes);
    if(result.IsError){

    }
}

* Higher order function: until I learned about functional programming I didn’t realize that higher order functions can replace most of the popular programming loops. I over used for loops when a mapping (select) would have been a much more appropriate choice. I was not aware just how versatile higher-order functions can be.

public IEnumerable<int> MappingWithStatements(IEnumerable<int> myNumbers){
    List<int> returnList = new List<int>();
    foreach(var number in myNumbers){
        if(number == 42){
            //Filtering
            continue;
        }
        var numberWithTransformation = number * 2;
        returnList.Add(numberWithTransformation)
    }
    return returnList;
}

public IEnumerable<int> MappingWithExpression(IEnumerable<int> myNumbers) 
    => myNumbers
        .Where(number => number != 7)
        .Select(number => number*2)

Before reflecting on higher order function I would not realize that these two code describes the same thing, the second using a much concise syntax.

* Pipe operators: C# does not have a universal pipe operator for arbitrary functions, so chained function must be read backwards.

buildTree(getTokens(input).ToList())

let main2 (input: string) =
    input
    |> getTokens
    |> Seq.toList
    |> buildTree

Luckily it doesn’t apply to Linq functions and you can easily define your own mini Pipe operator anyway.

* Statements: Historically C# is a statement based language, but it is moving toward expressions. (opposed to F#). In modern C#, expression should almost always be favored to statements. There is more and more support for expression in every newer version of the language (Such as the switch expression) Of course within reasonable limits, for instance it would be awkward to use .ContinueWith() instead of using await.

What I disliked:

* Recursive functions/learning the loop replacement: Imperative languages rely on a few general-purpose loop constructs, functional programming uses a broader library of specialized higher-order functions and recursion. This requires a steeper initial learning curve, and takes time to get used to recursion but also shifts the developer’s focus from manual iteration logic to high-level data transformation patterns.

let groupTokens (tokens: string list) =
    let rec parse current (remaining: string list) =
        match remaining with
        | [] -> List.rev current, []
        | “)” :: tail -> List.rev current, tail
        | “(” :: tail ->
            let inner, next = parse [] tail
            parse (Group inner :: current) next
        | token :: tail -> parse (Scalar(strToOperator token) :: current) tail

    let result, _ = parse [] tokens
    result

In idiomatic functional programming there are no loops, recursion is used for achieving its effect. It was the first time I have seen this “pattern”. With an immature team it slows the development time down.

My repository is available here.