fn start() {
  def expr = "1 1 + 2 * 3 + 2 *\0";
  def result = eval(&expr);

  print("Ans = ");
  iprint(result);
  println("");
}

// Computes value of given RPN-expression.
//
// @sig: fn(string) -> int
fn eval(expr) {
  def stack = stack_new(32);
  def parsing = *expr;

  while parsing {
    def ch = *expr;

    if is_whitespace(ch) {
      eval_process_whitespace(&expr);
    } else {
      if is_digit(ch) {
        eval_process_number(stack, &expr);
      } else {
        if is_operator(ch) {
          eval_process_operator(stack, &expr);
        } else {
          def msg = "expression contains an unknown character\0";
          panic(&msg);
        }
      }
    }

    parsing = *expr;
  }

  if neq(stack_len(stack), 1) {
    def msg = "expression is unbalanced\0";
    panic(&msg);
  }

  def result = stack_pop(stack);

  stack_free(stack);

  return result;
}

// @vis: private
// @sig: fn(&&char)
fn eval_process_whitespace(expr) {
  // We're just skipping all the whitespaces
  *expr = add(*expr, 1);
}

// @vis: private
// @sig: fn(&stack, &&char)
fn eval_process_number(stack, expr) {
  def number = alloc(8);
  def number_ptr = number;

  def parsing = 1;

  while parsing {
    *number_ptr = **expr;
    number_ptr = add(number_ptr, 1);

    *expr = add(*expr, 1);

    parsing = is_digit(**expr);
  }

  *number_ptr = 0;

  stack_push(stack, atoi(number));
  free(&number, 8);
}

// @vis: private
// @sig: fn(&stack, &&char)
fn eval_process_operator(stack, expr) {  
  def b = stack_pop(stack);
  def a = stack_pop(stack);
  def c = 0;

  def op = **expr;

  if eq(op, "+") {
    c = add(a, b);
  }

  if eq(op, "-") {
    c = sub(a, b);
  }

  if eq(op, "*") {
    c = mul(a, b);
  }

  if eq(op, "/") {
    c = div(a, b);
  }

  if eq(op, "%") {
    c = mod(a, b);
  }

  stack_push(stack, c);

  *expr = add(*expr, 1);
}

// Returns whether given character is a whitespace.
//
// @sig: fn(char) -> bool
fn is_whitespace(ch) {
  def whitespaces = " \t\0";

  return strcnt(&whitespaces, ch);
}

// Returns whether given character is a digit.
//
// @sig: fn(char) -> bool
fn is_digit(ch) {
  def digits = "0123456789\0";

  return strcnt(&digits, ch);
}

// Returns whether given character is an operator.
//
// @sig: fn(char) -> bool
fn is_operator(ch) {
  def operators = "+-*/%\0";

  return strcnt(&operators, ch);
}

// ------------------------ //
// Stack-oriented functions //

// Creates a new, empty stack and returns a pointer to it.
//
// Since Free as-is doesn't support data types, we're modelling stack as a
// pointer into memory that we manually process as such:
//
//    [ stack ] [ stack + 1 ] [ stack + 2 ] [ ... ]
//        |           |       | ---- from this point on we've got actual
//        |           |              stack's items
//        |           |
//        |           ^ this contains stack's maximum size
//        |
//        ^ this contains stack's length
//
// More or less, it's:
//
// ```
// struct stack {
//   len: int,
//   size: int,
//   items: [int; int],
// }
// ```
//
// @sig: fn(int) -> &stack
fn stack_new(size) {
  // We're adding two bytes to the stack's size, because we're going to utilize
  // stack's first and second byte to store its length and size
  def stack = alloc(add(size, 2));

  *stack_len_ptr(stack) = 0;
  *stack_size_ptr(stack) = size;

  return stack;
}

// Releases memory associated with given stack.
//
// @sig: fn(&stack)
fn stack_free(stack) {
  free(stack, add(stack_len(stack), 2));
}

// Pushes given value onto the stack.
//
// @sig: fn(&stack, int)
fn stack_push(stack, value) {
  if stack_is_full(stack) {
    def msg = "stack overflowed\0";
    panic(&msg);
  }

  def len_ptr = stack_len_ptr(stack);
  def size_ptr = stack_size_ptr(stack);
  def value_ptr = stack_value_ptr(stack, *len_ptr);

  // Store value inside the stack
  *value_ptr = value;

  // Increase stack's size
  *len_ptr = add(*len_ptr, 1);
}

// Pops value from the top of given stack.
//
// @sig: fn(&stack) -> int
fn stack_pop(stack) {
  if stack_is_empty(stack) {
    def msg = "stack underflowed\0";
    panic(&msg);
  }

  def len_ptr = stack_len_ptr(stack);

  // Decrease stack's size
  *len_ptr = sub(*len_ptr, 1);

  // Load value from the stack
  def value_ptr = stack_value_ptr(stack, *len_ptr);

  return *value_ptr;
}

// Returns number of elements inside given stack right now.
//
// @sig: fn(&stack) -> int
fn stack_len(stack) {
  def len_ptr = stack_len_ptr(stack);

  return *len_ptr;
}

// Returns whether given stack is empty.
//
// @sig: fn(&stack) -> bool
fn stack_is_empty(stack) {
  def len_ptr = stack_len_ptr(stack);

  return eq(*len_ptr, 0);
}

// Returns whether given stack is full.
//
// @sig: fn(&stack) -> bool
fn stack_is_full(stack) {
  def len_ptr = stack_len_ptr(stack);
  def size_ptr = stack_size_ptr(stack);

  return gte(*len_ptr, *size_ptr);
}

// Returns a pointer to an integer indicating the total number of elements
// inside given stack right now.
//
// @vis: private
// @sig: fn(&stack) -> int
fn stack_len_ptr(stack) {
  return add(stack, 0);
}

// Returns a pointer to an integer indicating the total number of elements
// given stack can contain.
//
// @vis: private
// @sig: fn(&stack) -> int
fn stack_size_ptr(stack) {
  return add(stack, 1);
}

// Returns a pointer to given stack's value.
//
// @vis: private
// @sig: fn(&stack) -> &T
fn stack_value_ptr(stack, idx) {
  return add(stack, add(idx, 2));
}

// ------------------------- //
// String-oriented functions //

// Returns number of characters inside given null-terminated string.
//
// @sig: fn(&char) -> int
fn strlen(str) {
  def len = 0;
  def running = *str;

  while running {
    len = add(len, 1);
    str = add(str, 1);
    running = *str;
  }

  return len;
}

// Reverses given null-terminated string in-place.
//
// @sig: fn(&char)
fn strrev(str) {
  def len = strlen(str);
  def running = gte(len, 2);

  if running {
    def len_half = div(len, 2);

    def idx_a = 0;
    def idx_b = sub(len, 1);

    while running {
      pswap(
        add(str, idx_a),
        add(str, idx_b),
      );

      idx_a = add(idx_a, 1);
      idx_b = sub(idx_b, 1);

      running = neq(idx_a, len_half);
    }
  }
}

// Returns whether given null-terminated string contains given character.
// Similar to `strpos(str, ch) > 0`, but simpler.
//
// @sig: fn(&char, char) -> bool
fn strcnt(str, ch) {
  def result = 0;
  def running = *str;

  while running {
    if eq(*str, ch) {
      result = 1;
      running = 0;
    } else {
      str = add(str, 1);
      running = *str;
    }
  }

  return result;
}

// Converts given integer into a null-terminated string.
//
// Given buffer must be large enough to contain the entire number and the null
// terminator.
//
// @sig: fn(int, &char)
fn itoa(num, buf) {
  def ptr = buf;
  def len = 0;

  while num {
    *ptr = add(48, mod(num, 10));
    num = div(num, 10);

    ptr = add(ptr, 1);
    len = add(len, 1);
  }

  if eq(len, 0) {
    *ptr = 48;
    ptr = add(ptr, 1);
  }

  *ptr = 0;

  strrev(buf);
}

// Converts given null-terminated string into an integer.
//
// If given string contains non-digit characters, the behavior is undefined.
//
// @sig: fn(&char) -> int
fn atoi(str) {
  def res = 0;
  def running = *str;

  while running {
    res = mul(res, 10);
    res = add(res, sub(*str, 48));

    str = add(str, 1);
    running = *str;
  }

  return res;
}

// Prints a null-terminated string onto the stdout.
//
// @sig: fn(&char)
fn sprint(str) {
  def running = *str;

  while running {
    print(*str);
    str = add(str, 1);
    running = *str;
  }
}

// -------------------------- //
// Pointer-oriented functions //

// Swaps values under given pointers.
//
// @sig: fn(&T, &T)
fn pswap(a, b) {
  def tmp = *a;
  *a = *b;
  *b = tmp;
}

// Frees memory under given pointer.
//
// @sig: fn(&T, int)
fn free(ptr, size) {
  while size {
    size = sub(size, 1);
    free_byte(add(ptr, size));
  }
}

// -------------------------- //
// Integer-oriented functions //

// Prints an integer onto the stdout.
//
// @sig: fn(int)
fn iprint(num) {
  def buf = alloc(16);
  itoa(num, buf);
  sprint(buf);
}

// Multiplies both numbers and returns the result.
//
// @sig: fn(int, int) -> int
fn mul(a, b) {
  def res = 0;

  while b {
    res = add(res, a);
    b = sub(b, 1);
  }

  return res;
}

// Divides both numbers and returns the result.
//
// It utilizes repeated subtraction and thus is totally inefficient for bigger
// numbers.
//
// @sig: fn(int, int) -> int
fn div(a, b) {
  def res = 0;
  def running = 1;

  while running {
    if gte(a, b) {
      a = sub(a, b);
      res = add(res, 1);
    } else {
      running = 0;
    }
  }

  return res;
}

// Returns modulo of both numbers.
//
// It utilizes repeated subtraction and thus is totally inefficient for bigger
// numbers.
//
// @sig: fn(int, int) -> int
fn mod(a, b) {
  def res = 0;

  while a {
    if gte(a, b) {
      a = sub(a, b);
    } else {
      res = a;
      a = 0;
    }
  }

  return res;
}

// Returns whether both numbers are equal.
//
// @sig: fn(int, int) -> bool
fn eq(a, b) {
  if sub(a, b) {
    return 0;
  } else {
    return 1;
  }
}

// Returns whether both numbers are different.
//
// @sig: fn(int, int) -> bool
fn neq(a, b) {
  return sub(1, eq(a, b));
}

// Returns whether first number is greater than or equal to the second one.
//
// Since Free doesn't provide any built-ins that would allow us to compare
// numbers, what we're doing here is basically decreasing numbers by one until
// either one (or both) eventually are zeroed-out.
//
// @sig: fn(int, int) -> bool
fn gte(a, b) {
  def res = 0;
  def running = 1;

  while running {
    if a { } else {
      running = 0;
      res = 0;
    }

    if b { } else {
      running = 0;
      res = 1;
    }

    a = sub(a, 1);
    b = sub(b, 1);
  }

  return res;
}

// --------------- //
// Other functions //

// @sig: fn(&char)
fn panic(msg) {
  print("panic: ");
  sprint(msg);
  println("");

  def true = 1;

  while true {
    //
  }
}