Stack Based Calculator in R

R Stack Based Calulator

I've been reading a lot of Scott Wlaschin's functional programming material lately. I found his Stack Based Calculator example particularly interesting, and wanted to re-implement it in R to get a better grasp of the material.

Setup

FROM rocker/rstudio:latest
# rocker/tidyverse didn't seem to have a prebuilt arm64 image, so
# we can build our own
RUN Rscript -e "install.packages(c('rlang', 'tidyverse', 'lobstr', 'zeallot'))"

docker build . -t r_stack_based_calculator:latest

docker run --rm --name r_stack_based_calculator -dti r_stack_based_calculator

71c8b86a9fb6a97f920beab481d929dab3ecbdd1a3943eb75f499e31b26186b7

# turn off ANSI escape codes
options(cli.num_colors = 1)

The Calculator

Helpers

The original article used F# (as all the material on the site does), which includes a native function composition infix operator as well as the ability to unpack a tuple into multiple assignments. We can't do this natively in R, but can come close.

library(zeallot) # for unpacking-assignment  %<-%

# infix function composition
`%>>%` <- function(lhs, rhs) {
  purrr::compose(lhs, rhs, .dir = "forward")
}

The Stack

A list is used here, and functions as expected. `lobstr::tree` is used to visualize lists better.

push <- function(value, stack) {
  append(value, stack)
}

push(3, list(2,1)) |> lobstr::tree()

<list>
├─3
├─2
└─1

Creating partially applied functions in R is not as friendly as in F#, so we create a helper function to accomplish this more readably. Partial application here bakes the stack into the function's environment.

p_push <- function(value) {
  # partialized push
  purrr::partial(push, value)
}

ONE <- p_push(1)

list(11, 12) |> ONE() |> lobstr::tree()

<list>
├─1
├─11
└─12

Popping off the stack happens as expected too, using a list instead of a tuple with the first element being the popped element and the second the remaining stack.

pop <- function(stack) {
  list(stack[[1]], tail(stack, n = -1))
}

pop(list(7,8,9)) |> lobstr::tree()

<list>
├─7
└─<list>
  ├─8
  └─9

The Math

Using zeallot's unpacking assignment makes the R code look and act as the F# code does.

ADD <- function(stack) {
  c(x, s) %<-% pop(stack)
  c(y, s2) %<-% pop(s)
  push(x + y, s2)
}

list(11,12,13,14) |> ADD() |> lobstr::tree()

<list>
├─23
├─13
└─14

We aren't in a strongly typed language here, so we don't have (or require, really) any generics to refactor out the binary math ops. We can just run the given function against the top two elements of the stack and hope for the best. We could do some checking on the argument types and number of arguments, but I'm not going to.

binary <- function(fn) {
  function(stack) {
    c(x, s) %<-% pop(stack)
    c(y, s2) %<-% pop(s)
    push(fn(x, y), s2)
  }
}

MUL <- binary(`*`)
list(10,11,12,13) |> MUL() |> lobstr::tree()

<list>
├─110
├─12
└─13

SWAP <- binary(function(x, y) c(y, x))
list(3,4,5) |> SWAP() |> lobstr::tree()

<list>
├─4
├─3
└─5

Tying it All Together

EMPTY <- list()
TWO <- p_push(2)
THREE <- p_push(3)

EMPTY |>
  THREE() |>
  THREE() |>
  TWO() |>
  ONE() |>
  MUL() |>
  MUL() |>
  SWAP() |>
  lobstr::tree()

<list>
├─3
└─6

This looks very similar to the original.

Function Composition

We also don't have function signatures to adhere to (for better or worse), but can still compose functions if we know they are compatible, in that the output of one step is compatible with the input of the next.

DUP <- function(stack) {
  c(x, s) %<-% pop(stack)
  push(x, stack)
}

# using the infix composition operator defined earlier
SQUARE <- DUP %>>% MUL

list(2) |> SQUARE()

[[1]]
[1] 4