Having some unexpected behaviour with recursion function call

The below code is an expansion of an exercise dealing with character lists it is intended to parse a character list submitted as a calculation query.

The original exercise was just two values with one operator, however I expanded it too included multiple operators, powers and brackets.

I am having an issue with the brackets implementation. Everything seems to be working fine, until one of the recursion calls does not pass one of the arguments for the third parameter (the buffer parameter).

I would really appreciate some guidance here, I have not started control flow, however I think I have a good idea of what should be happening so I’ve been quite baffled by the behaviour of my brackets operators implementation.

This code has not been fully cleaned, but I took some steps to make the code more concise and remove some inefficiencies.

I’ve done some troubleshooting, and it seems as though the buffer arg is not updating from the default empty charlist that it is set to when the function is called from within the calculator(…,…,…,?( ) clause titled ###‘(’, parenthesis operator, ###########

Below the is the code:

defmodule Calc do

  def calculator(list, value \\ 0, buffer \\ '', operator \\ ?+)

  # def calculator([h|_], _, _, _) when not (h in ?(..?9 or h == ?^) or h == ?, do
  #   raise "Illegal character in calculation query"
  # end

  # def calculator([h|t], _, _, _) when h in '^*/+-)' and t != [] and hd(t) in '^*/+-)', do: raise "Illegal consecutive operators '#{[h, hd(t)]}'"

  # def calculator([?.|t], value, buffer, operator) do
  #   cond do
  #     ?. in buffer ->
  #       raise ~w"""
  #       Number #{buffer} already cotains maximum number of decimal points (1).
  #       Remove any other decimal points and leave only the one intended decimal.
  #       """
  #     buffer == '' ->
  #       calculator(t, value, '0.', operator)
  #     true ->
  #       calculator(t, value, buffer ++ [?.], operator)
  #   end
  # end

  # def calculator([h|[]], _value, _buffer, _operator) when h in '^*/+-(', do: raise "Improper character '#{[h]}' used to terminate calculation"

  # def calculator([?-|t], value, '', operator), do: calculator(t, value, ?-, operator)

  def calculator([], value, buffer, operator) do
    lsign = ((operator in '*+' && 1) || -1)
    v1 = (buffer |> to_number)
    v2 = (operator == ?^ && value ** v1) || (operator in '/*' && value * v1 ** lsign) || value + v1 * lsign
    {[], v2}
  end

  def calculator([h|t], value, buffer, operator) when h in ?0..?9 do
    calculator(t, value, buffer++[h], operator)
  end

  ###^, power operator, ###########
  # def calculator([h|t], value, buffer, ?^) do
  #   IO.puts "here1"
  #   cond do
  #     h in '^*/' ->
  #       value = value ** (buffer |> to_number)
  #        calculator(t, value, '', h)
  #     h in '+-' ->
  #       {[h|t], value ** (buffer |> to_number)}
  #     h == ?( ->
  #       if buffer != '' do
  #         value = value ** (buffer |> to_number)
  #         calculator([h|t], value, '', ?*)
  #       else
  #         {t, i_val} = calculator(t, 0, '', h)
  #         value = value ** i_val
  #         calculator(t, value)
  #       end
  #     h == ?) ->
  #       value =  value ** (buffer |> to_number)
  #       {[h|t], value}
  #   end
  # end

  ###*/, multiplication operators, ###########
  # def calculator([h|t], value, buffer, operator) when operator in '*/' do
  #   IO.puts "here2"
  #   IO.inspect value
  #   pow = (operator == ?* && 1) || -1
  #   cond do
  #     h == ?^ ->
  #       {t, i_val} = calculator(t, buffer |> to_number, '', h)
  #       {t, value * i_val ** pow}
  #     h in '*/' ->
  #       value = value * (buffer |> to_number) ** pow
  #       calculator(t, value, '', h)
  #     h in '+-' ->
  #       {[h|t], value * (buffer |> to_number) ** pow}
  #     h == ?( ->
  #       {[h_2|t_2], i_val} = calculator(t, 0, '', h)
  #       {t, i_val} = (h_2 not in '+-' && calculator(t_2, i_val ** pow, '', h_2)) ||  {[h_2|t_2], i_val}
  #       if buffer != '' do
  #         value = value * (buffer |> to_number) ** pow * i_val
  #         {t, value}
  #       else
  #         value = value * i_val
  #         {t, value}
  #       end
  #     h == ?) ->
  #       value =  value * (buffer |> to_number) ** pow
  #       {[h|t], value}
  #   end
  # end

  ###+-, addition operators, ###########
  def calculator([h|t], value, buffer, operator) when operator in '+-' do #and h in '^*/+-()'
    IO.inspect buffer
    s = (operator == ?+ && 1)|| -1
    cond do
      h == ?( ->
        {t, i_val} = calculator(t, 0, '', h)
        if t != [] do
          [h_2, t_2] = [hd(t), tl(t)]
          {t, i_val} = (h_2 not in '+-' && calculator(t_2, i_val, '', h_2)) ||  {[h_2|t_2], i_val}
          if buffer != '' do
            value = value + (buffer |> to_number) * s * i_val
            calculator(t, value)
          else
            value = value + s*i_val
            calculator(t, value)
          end
        else
          {t, i_val}
        end
      h == ?) ->
        value = value + s*(buffer |> to_number)
        {[h|t], value}
      h in '^*/+-' ->
        {t, i_val} = calculator(t, buffer |> to_number, '' ,  h)
        value = value + s*i_val
        calculator(t, value)
    end
  end

  ###'(', parenthesis operator, ###########
  def calculator(list, _, _, ?() do
    {list, value} = calculator(list)
    tail = tl list
    if tail != [] && hd tail in ?0..?9 do
      raise "Number should not follow bracket close"
    else
      {tail, value}
    end
  end

  def to_number(_number, value\\0, multiplier\\1, point\\false, pow\\0)

  def to_number([?-|t], value, _multiplier, _point, _pow), do: to_number(t, value, -1)

  def to_number([?.|[]], value, multiplier, _point, _pow), do: to_number([], value, multiplier)

  def to_number([?.|t], value, multiplier, _point, _pow), do: to_number(t, value, multiplier, true, -1)

  def to_number([h|t], value, multiplier, true, pow), do: to_number(t, value + (h - ?0) * 10 ** pow, multiplier, pow - 1)

  def to_number([h|t], value, multiplier, false, _pow), do: to_number(t, 10*value + (h - ?0), multiplier)

  def to_number([], value, multiplier, _point, _pow), do: value*multiplier

If there is any ambiguity please let me know. This is a somewhat rough implementation, that is, I’m just trying to get it working with some degree of adherence to conventions to aid in my understanding of the language.

Just wanted to add the path that the call should take:

So the below call…:

calculator '(5+2)' (output {, 2}, expected output {, 7})

…should take the following path (and it does but the buffer arg is not passed):

  1. Goes to ###±, addition operators, ########### as the default operator is +
  2. Within that function body the cond do requirements are met which results in the following call calculator(t, 0, '', h), where h = ?(
  3. Goes to ###‘(’, parenthesis operator, ########### which calls calculate passing the character list with ?( removed
  4. Goes to the calculate with h in 0?..?9 clause, and concatenates buffer with [h] calls calculate with the tail, t and the new buffer with the concatenation.
  5. Goes once again to the ###±, addition operators, ########### titled clause, but does not pass the updated buffer, instead the default buffer value is passed!

This path is confirmed with IO.puts/inspect and it does not bounce between any other clauses.

EDIT: I’ve commented out all code that is not relevant to the recursion call exampled and I have added the output for that recursion versus the expected output

God bless.

I am on my phone so can’t really make complete sense of your example. But when I am in these situations I put IO.inspect in every function head with some identifying information for the function head is being called plus what the values of the relevant parameters are. Then you will get a nice list in order of what is happening and the issue should be obvious when you see something you don’t expect.

edit: and similarly io.inspect in every possible branch that might lead to the next recursive call along with the arguments being passed into it. that is equally important.

I don’t have time to analysis your code but this video by @sasajuric is excellent to watch to gain a good understanding of a functional approach to parsing from first principles.

Then you might consider Nimbleparsec for your needs.

1 Like

I could delete the code that is not involved in the recursion for the relevant function argument.

Thanks for the video link.

I’ll try to get this running locally to see if anything jumps out, but it’s really hard to follow overall.

I’ll +1 the recommendation to print all the arguments when entering each function. Consider using the process dictionary to track the current “call level” and make logs like:

calculate(args, args, args)
  calculate(args, args, args)
    calculate(args, args, args
  calculate(args, args, args)
etc

A trace like that will also be helpful for readers that can’t execute the code themselves.

Some general Elixir-style thoughts:

  • single-function pipes aren’t great for readability, but they’re especially bad in arithmetic expressions. Compare:
      h in '+-' ->
        {[h|t], value * (buffer |> to_number) ** pow}

      h in '+-' ->
        {[h|t], value * to_number(buffer) ** pow}
  • && and || reduce readability when they’re overused, and putting more than zero recursive calls in them is (IMO) overusing them
{t, i_val} = 
  if h_2 not in '+-' do
    calculator(t_2, i_val, '', h_2))
  else
    {[h_2|t_2], i_val}
  end
2 Likes

Thanks a lot for those styling tips especially the && || ones as I did not know that if statements (are they called that in elixir?) in elixir would behave like expressions in this way.

I thought their blocks (if blocks) were scoped off like Enum.each. I wonder if some degree of scoping off is messing with the visibility of the buffer argument update.

I also did not know about process dictionaries since I have not covered debugging yet, so thanks for that as well.

What didn’t work?—Parenthesis. What do we want to watch?—Parenthesis handler. Let’s do it:

  ###'(', parenthesis operator, ###########
  def calculator(list, value, buffer, ?() do
    # ⇓ THIS ⇓
    dbg(list: list, value: value, buffer: buffer)
    
    # Below is already fixed version
    {list, value} = calculator(buffer ++ list) |> dbg()

    case list do
      [_, h | _] when h in ?0..?9 -> raise "★"
      [_ | tail] -> {tail, value}
    end
  end

With the dbg/1 call above, we’d immediately see that part of the list has been already moved to buffer (I did not dig it further,) so we should prepend buffer to list or like.

1 Like

Hi, apologies for any lack of clarity here, what is being appended to buffer is the head of list after the opening bracket character has been removed so in …

 h == ?( ->
        {t, i_val} = calculator(t, 0, '', h)
        if t != [] do
          [h_2, t_2] = [hd(t), tl(t)]
          {t, i_val} = (h_2 not in '+-' && calculator(t_2, i_val, '', h_2)) ||  {[h_2|t_2], i_val}
          if buffer != '' do
            value = value + (buffer |> to_number) * s * i_val
            calculator(t, value)
          else
            value = value + s*i_val
            calculator(t, value)
          end
        else
          {t, i_val}
        end

The

{t, i_val} = (h_2 not in ‘±’ && calculator(t_2, i_val, ‘’, h_2)) || {[h_2|t_2], i_val}

Removes ?( from ‘(5+2)’

Then 5 is appended to buffer.

the + operated makes the call go to the clause that processes 5 into it’s value form using to_number(?5), then calls calculator again to handle the rest of the character-list.

Please try the code I provided. It works as expected.

Also, you’d better use case/2 instead of cond/1 whenever possible:

    case h do
      ?( ->
        {t, i_val} = calculator(t, 0, '', h)
        if t != [] do
          [h_2, t_2] = [hd(t), tl(t)]
          {t, i_val} = (h_2 not in '+-' && calculator(t_2, i_val, '', h_2)) ||  {[h_2|t_2], i_val}
          value = 
            if buffer != '' do
              value + to_number(buffer) * s * i_val
            else
              value + s*i_val
            end
          calculator(t, value)
        else
          {t, i_val}
        end

      ?) ->
        {[h|t], value + s*to_number(buffer)}

      h when h in '^*/+-' ->
        {t, i_val} = calculator(t, buffer |> to_number, '' ,  h)
        value = value + s*i_val
        calculator(t, value)
    end
1 Like

Great! Keen to implement this as I’ve been stuck on this for a few days.

Edit: The problem still persists. This works on your system?

Oh I see you meant the code in the your first post. I’ll try that. No I’m not understanding.

Lol… that was a silly error.

Thanks a lot really appreciate it.

Wow. All I had to do was include a guard in the buffer appending function to exclude operators equaling ?(.

As you said, part of the list was already removed. I didn’t understand what you meant because the head of the list ?( is removed in the call, but one of the other clauses was also removing from the list 5 before it meets bracket.

  def calculator([h|t], value, buffer, operator) when h in ?0..?9 and operator != ?( do
    calculator(t, value, buffer++[h], operator)
  end

The

and operator != ?(

guard gets the expected results.

Think I’ll settle in the debugging section for a while when I reach it.

I’d better move def calculator(list, value, buffer, ?() do clause above def calculator([h|t], value, buffer, operator) when h in ?0..?9 do—they are tried in the order, and more strict ?( would win anyway, if stated earlier.

1 Like

Ah yes, will do.

My code is still bit buggy but that’s in other ways that I will resolve.

Thanks a lot for your help.

In Elixir, if is an expression and returns a result.

Any assignment to a “variable” (known as value binding) is always local to the block it occurs in. A binding does not leak outside the block it occurs in, so it won’t propogate up, but the binding is visible to inner blocks.

This is why if you try to assign to a variable within an if or else block it doesn’t change the binding on the scope above. What you do instead is return a value, as Elixir is fundamentally a functional language even if there might be some superficial resemblance to ruby it’s basically functions all the way down, no loops, only recursive functions. Even process state is achieved by passing a value in a recursive call in the runloop.

Elixir also allows re-binding of a variable using the same name, in Erlang you can’t actually do that and must provide a different name binding each time, like foo1, foo2. The underpinnings of Elixir are strictly immutable.

2 Likes

Thanks a lot for this, and I’m better appreciating the behavior of if expressions in elixir now.

This is the way a relevant section of the code’s implementation has been updated:

      h == ?( ->
        {t, i_val} = calculator(t, 0, '', h)
        {t, i_val} =
          if t != [] do
              if hd(t) not in '+-)' do
                calculator(tl(t), i_val ** pow, '', hd(t))
              else
                {t, i_val}
              end
          else
            {t, i_val}
          end
        if buffer != '' do
          value = value * to_number(buffer) ** pow * i_val ### An empty buffer means the form x (*/) (...) while a non empty buffer means x (*/) buffer(...), where buffer is a char list of real numbers, the buffer(...) gets converted into buffer * (...); note that it will always be multiplication due to the form, y(...). The buffer itself is not necessarily multiplying the x, and an earlier division will take precedent with respect to processing, thus the buffer is to the power of pow, which  is equal to 1 or -1 depending on the whether the operator (*/) is equal * or / respectively.
          {t, value}
        else
          value = value * i_val # Whether or not i_val is diving or multiplying is factored into  the a prior calculator call that returns when one of +- characters is encountered.
          {t, value}
        end
    ...
    ...

You can see I’m using them more as expressions now, so I’m comfortable ending the block with them, which is much cleaner than my prior implementation.

The code from yesterday is now fully working as far as I can tell; with embedded brackets and the presence of powers not causing any errors, so after control flow debugging and tooling, I’m going to come back and review the code for any improvements and I’ll also be looking at implementing some structs where necessary.

Edit: Just saw that I can make it even more concise as there was some wastage

      h == ?( ->
        {t, i_val} = calculator(t, 0, '', h)
        {t, i_val} =
            if  t != []  && hd(t) not in '+-)' do
              calculator(tl(t), i_val ** pow, '', hd(t))
            else
              {t, i_val}
            end
        if buffer != '' do
          value = value * to_number(buffer) ** pow * i_val ### An empty buffer means the form x (*/) (...) while a non empty buffer means x (*/) buffer(...), where buffer is a char list of real numbers, the buffer(...) gets converted into buffer * (...); note that it will always be multiplication due to the form, y(...). The buffer itself is not necessarily multiplying the x, and an earlier division will take precedent with respect to processing, thus the buffer is to the power of pow, which  is equal to 1 or -1 depending on the whether the operator (*/) is equal * or / respectively.
          {t, value}
        else
          value = value * i_val # Whether or not i_val is diving or multiplying is factored into  the a prior calculator call that returns when one of +- characters is encountered.
          {t, value}
        end
        ...
        ...

Even better. I didn’t know you could check if t != like that.

Thanks a lot.

God bless.

  h == ?( ->
    {t, i_val} = calculator(t, 0, '', h)
    {t, i_val} =
      case t do
        [h|t] when h not in '+-)' ->
          calculator(t, i_val ** pow, '', t)
        _ ->
          {t, i_val}
      end
    value = 
      if buffer != '',
        do: value * to_number(buffer) ** pow * i_val,
        else: value * i_val 

    {t, value}
2 Likes

Do you know that you can also match on values in your function headers and handle distinct cases elegantly in a declarative manner?

I would also suggest that you define a struct in your module to hold the state and make all your functions recursively reduce over that state. Meaning they take the module struct on the first argument and return an updated state.

In general most things in functional programming follow the Construct, Reduce, Convert (CRC) approach as explained by Bruce Tate and covered in his Designing Elixir Systems with OTP book.

1 Like

I hope to go over that book after Metaprogramming and Phoenix, in preparation for Ecto and building full applications within this ecosystem.

I’m going to be implementing structs in this program, bGG, so I’ll likely reupload my code once the changes have been made, but in a separate thread.