Looking for ideas on evaluating a string of nested bools to a single bool

Questions / Help
1

I am looking to parse a string like the following to a single boolean.

"(false and (true or true) or (true and (false or false)))"

I was using Code.eval_string as a temp solution(only in local testing) and now am looking to switch it to something safe.

I have a couple ideas in my head but would like some other opinions.

This string for brevity you can assume is to be passed by a user.

2 
iex(1)> quote do: (false and (true or true) or (true and (false or false)))
{:or, [context: Elixir, import: Kernel],
 [{:and, [context: Elixir, import: Kernel],
   [false,
    {:or, [context: Elixir, import: Kernel], 
     [true, true]}]},
  {:and, [context: Elixir, import: Kernel],
   [true,
    {:or, [context: Elixir, import: Kernel],
     [false, false]}]}]}

That’ll give you it in AST format which, due to its prefix notation nature, is probably easy to vet and interpret.

3

I am trying to figure out how I could get that ast from a variable that is a string. You are doing quote on the code but I can not do that as it would be unsafe(user passed string)

4

Another way is to use leex and yecc…

If you put this in src folder… into string_lexer.xrl.

Definitions.

WHITESPACE       = [\s\t]
TERMINATOR       = \n|\r\n|\r

Rules.

\(               : {token, {'(', TokenLine}}.
\)               : {token, {')', TokenLine}}.
or               : {token, {union, TokenLine, atom(TokenChars)}}.
and              : {token, {intersection, TokenLine, atom(TokenChars)}}.
true             : {token, {true, TokenLine, atom(TokenChars)}}.
false            : {token, {false, TokenLine, atom(TokenChars)}}.
{WHITESPACE}     : skip_token.
{TERMINATOR}     : skip_token.

Erlang code.

atom(TokenChars) -> list_to_atom(TokenChars).

Then You could

iex> {:ok, tokens, _} = :string_lexer.string "(false and (true or true) or (true and (false or false)))" |> to_charlist()
{:ok,
 [
   {:"(", 1},
   {false, 1, false},
   {:intersection, 1, :and},
   {:"(", 1},
   {true, 1, true},
   {:union, 1, :or},
   {true, 1, true},
   {:")", 1},
   {:union, 1, :or},
   {:"(", 1},
   {true, 1, true},
   {:intersection, 1, :and},
   {:"(", 1},
   {false, 1, false},
   {:union, 1, :or},
   {false, 1, false},
   {:")", 1},
   {:")", 1},
   {:")", 1}
 ], 1}

And You could parse those tokens with yecc, You just need a grammar file :slight_smile:

1 Like
5

Ah, of course. It’s late here :wink:

In that case, I’d go the safe route and write a parser. My first look would be https://github.com/bitwalker/combine probably.

1 Like
6

Just a note I noticed that I can use Code.string_to_quoted to get the ast of the string at runtime and parse it so I think I am going to explore that route.

1 Like
7

This will also work for …

iex(8)> Code.string_to_quoted "(hello and (world or remove true) or (file and (String.split(\"a\") or Error)))"
{:ok,
 {:or, [line: 1],
  [
    {:and, [line: 1],
     [
       {:hello, [line: 1], nil},
       {:or, [line: 1],
        [{:world, [line: 1], nil}, {:remove, [line: 1], [true]}]}
     ]},
    {:and, [line: 1],
     [
       {:file, [line: 1], nil},
       {:or, [line: 1],
        [
          {{:., [line: 1], [{:__aliases__, [line: 1], [:String]}, :split]},
           [line: 1], ["a"]},
          {:__aliases__, [line: 1], [:Error]}
        ]}
     ]}
  ]}}
8

This is the code that I ended up with. I am pretty happy with it. The task ended up pretty easy after finding Code.string_to_quoted

def eval_start(str) do
    try do
      eval(Code.string_to_quoted!(str))
    rescue
      e -> {:error, :format}
    end
  end 
  def eval({:or, _, [arg1,arg2]}) do
    eval(arg1) === true or eval(arg2) === true 
  end
  def eval({:and, _, [arg1,arg2]}) do
    eval(arg1) === true and eval(arg2) === true 
  end
  def eval(true) do
   true 
  end
  def eval(false) do
   false 
  end

Let me know if this looks correct but basically if their string is malformed or contains anything other then bools and / or the function will return {:error, :format}

I still have to write more tests to double check but this seems to do the trick.

9

Why not just use the erlang lua library? That way you can add more boolean operations if you want. :slight_smile:

10

I think KISS might be a very good reason to not do that :stuck_out_tongue_winking_eye:.

11

That is precisely the point of using lua, any manual implementation has a higher chance of bugs and so forth. The user code is minimal. ^.^

12

@OvermindDL1 But it would require an understanding of the user of Lua.
What I mean is that it might make sense to use Lua at the time that more operations turn out to be required, but not before.

For that matter, by the way, there might be room for a ‘restricted Elixir’ library. I know that @arjan was working on a chatbot-language that uses a lite-form of the Elixir AST as well :smiley: .

13

Eh only enough that is demonstrated in examples in the readme.

Entirely an experiment and not ‘useful’ yet, but an interesting test (yeesh I wish I had time to work on everything… if only I didn’t need to work, we need a Basic Income here…). ^.^

1 Like
14

Well for my use case it will only ever end up a string of bools or nested bools so won’t need extending for other uses in the future. I will definitely look at lua if I come across the need though!

1 Like
15

Ended up exploring the idea of Lua after thinking about the possibilities:

1 Like
16

Just for completeness: you’ll want to pass the existing_atoms_only: true option to Code.string_to_quoted!, otherwise it can be used to crash the VM.

2 Likes
17

Thanks for that!

1 Like