# [erlang-questions] second try for understanding recursion

Richard A. O'Keefe ok@REDACTED
Thu Feb 12 01:58:33 CET 2015

```On 8/02/2015, at 10:48 pm, Roelof Wobben <r.wobben@REDACTED> wrote:
> I  did a portion of this exercise :
>
> Write a module boolean.erlthat takes logical expressions and Boolean values (represented as the atoms  trueand  false) and returns their Boolean result.

"How to Solve It".  You will find copies on the Web these days, see
https://notendur.hi.is/hei2/teaching/Polya_HowToSolveIt.pdf
for one.

He speaks of four phases:

* UNDERSTANDING THE PROBLEM
* DEVISING A PLAN
* CARRYING OUT THE PLAN
* LOOKING BACK

(By the way, it's a strange experience looking at the "Dictionary
of Heuristic" in this book with "Design Patterns" eyes.  He had a
pattern language for problem solving before anyone coined the
term "pattern language"...)

Page 214 has the entry

WHAT IS THE UNKNOWN?
- What is required?
- What do you want?
- What are you supposed to seek?
* What are the data?
- What is given?
- What [do you already have]?
* What is the condition?
- By what condition is the unknown linked to the problem?
...
The questions are of the greatest importance...

The single most important skill you need to develop at this point is
UNDERSTANDING THE PROBLEM AND STATING IT CLEARLY.

In this case, what does "takes logical expressions" mean?
(Oh, and what is the distinction between "logical" expressions
and "Boolean" values?)

The way *I* read it, "taking logical expressions" means
ACCEPTING AS ARGUMENTS DATA STRUCTURES THAT ARE TREES
REPRESENTING BOOLEAN EXPRESSIONS.

So we need to start by saying how that will be done, and
I offer
+ false
+ true
+ {not,E1} where E1 is a logical expression
+ {and,E1,E2} where E1, E2 are logical expressions
+ {or,E1,E2} where E1, E2 are logical expressions
and that data type pretty much *forces* the following structural
recursion:

eval(false) ->
false;
eval(true) ->
true;
eval({not,E1}) ->
case eval(E1)
of true  -> false
; false -> true
end;
eval({and,E1,E2}) ->
case eval(E1)
of true  -> eval(E2)
; false -> false
end;
eval({or,E1,E2}) ->
case eval(E1)
of true  -> true
; false -> eval(E2)
end.

> The functions
> you write should include b_not/1, b_and/2, b_or/2, and b_nand/2. You should not use
> the logical constructs  and,  or, and  not, but instead use pattern matching to achieve your
> goal.

With that in hand, we can write

b_not(E1) ->
eval({not,E1}).

b_and(E1, E2) ->
eval({and,E1,E2}).

b_or(E1, E2) ->
eval({or,E1,E2}).

b_nand(E1, E2) ->
eval({not,{and,E1,E2}}).

If that is _not_ what the problem is about, what _does_ "take logical expressions"
mean, and where does recursion come into it?

By the way, supposing that we are just working with false and true, that is,
with logical CONSTANTS, not logical EXPRESSIONS, we can meet the letter of the
specification easily while violating its spirit:

b_and(V1, V2) -> V1 andalso V2.
b_or(V1, V2)  -> V1 orelse  V2.

We can also meet the letter and violate the spirit another way:

b_and(V1, V2) when V1 -> V2;
b_and(_,  _ )         -> false.

b_or(V1, _ ) when V1 -> true;
b_or(_,  V2)         -> V2.

I don't really expect you to understand all these solutions.
What I very much hope you will understand is that
WHAT COUNTS AS A SOLUTION DEPENDS ON WHAT THE PROBLEM IS
so that
IT IS OF THE GREATEST IMPORTANCE TO UNDERSTAND WHAT THE PROBLEM *IS*.

And not just to understand, but to *write down*.

> -module(boolean).
>
> -export([b_not/1]).
>
> % if a empty string is given , the answer will be a empty string.
> b_not('') ->
>  '';
>
The two values you are supposed to work with are 'false' and 'true'.
There is nothing in the problem specification you gave us, such as
it is and what there is of it, that requires *any* particular
behaviour for the empty atom ('' is NOT a string).

This clause is literally worse than useless.  Not only does it
contribute nothing to a correct solution of the problem, if the
b_not/1 function _should_ happen to be called incorrectly, the
error might be propagated instead of being caught.

> % is false is given, the answer will be true.
This is a junk comment.  It just paraphrases the code.
> b_not(false) ->
>  true;
>
> % is true is given, the answer will be false
This is a junk comment.  It just paraphrases the code.
> b_not(true) ->
>  false.

The code tells us what DOES happen.
Comments ought to tell us what IS SUPPOSED TO happen.
Or the reason.  So a comment like

%    When is_boolean(V), b_not(V) should equal (not V).
%    The exercise is to do this with pattern matching only.

tells us what is supposed to happen and why.

```