Home » forums » LtU Forum

Depends on what "is" is

Sounds like B. Clinton's evasive (but syntactically correct) answer to some deposition. But it's just a little lesson in associativity.

We want "is" to be synonymous with "=". That sounds reasonable, right? We could do this at the lowest level, at the lexer, and really make things simple.

But here comes "not". It's already an operator, and you want it to be so. And in (my) typeless world, "not" operates on integers just as happily as it does on booleans. There are two reasonable implementations for "not" on integers: multiplying by -1 or the function y = 1 - x. The first is sort of intuitive, the second makes not(1) equal to 0 and not(0) equal to 1.

Either way, you lose. Choose the first, so

"not x" => -1 * x

and examine the expression

0 is not 0

You'd want this to be a false statement, but unfortunately, it might parse like this:

0 is (not 0)
0 is (-0)
0 is 0
true

Yikes!

Tell me that this is just an LL(2) thing and if I look ahead one more token I'll be OK.

What I mean by that is: is my hack a canonical hack? When I see "is" I just greedily look ahead to see if the next token is "not".

By andrewzboard at 2010-02-02 01:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 5494 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Doesn't it depend on the definition of "not"?

That strikes me as a somewhat questionable definition of "not", precisely because it has the property that "not 0" = "-1 * 0" = "0".

By Douglas McClean at Tue, 2010-02-02 02:50 | login or register to post comments

There's no out

Correct. But consider the alternative: not x = 1 - x. This has the advantage (as mentioned) that not 1 = 0 and not 0 = 1. But.. not 0.5 = 0.5!

So you have to have a definition of "not" for numbers that never crosses the x=y line. And that's "not" so easy.

By andrewzboard at Tue, 2010-02-02 04:38 | login or register to post comments

Exactly. And, having

Exactly. And, having discovered that there isn't an "obvious" definition of "not" over integers that obeys the rules we'd expect (forall x. not x != x && forall x. not (not x) == x), why insist on defining "not" to operate over integers at all? Wouldn't an error be just as useful?

Alternatively, if you define some implicit coercion from booleans to integers and integers to booleans (say, 0 is false, nonzero is true), why not define "not" to match up with this definition? Not 0 is 1, and not any-non-zero-number is 0?

By Douglas McClean at Tue, 2010-02-02 15:09 | login or register to post comments

Freedom =? no rules

"Wouldn't an error be just as useful?"

Well, it's perhaps my folly that I am shooting for a complete universality, applicability of all operators and operations to all types (which for me are numbers, strings, and bools). That may be too much freedom. I am contemplating an (optional) type-checking phase that warns (but does not prohibit) questionable combinations.

As for your third proposed definition of not(#), see below. Of course, that gives me yet another idea: go with IEEE 754-ishness and call not(#) NaN.

By andrewzboard at Tue, 2010-02-02 17:10 | login or register to post comments

Not an integer

But.. not 0.5 = 0.5!

Surely this is (ahem) not a problem, since you specified that you only wanted not on integers?

If you really want to handle real numbers, then it is an easy-ish result that a continuous involution f has a fixed point. (The proof that comes to mind: Look at the supremum, or infimum if appropriate, of all real numbers x such that f(x) > x.) If you don't care about continuity, then you could just partition the real line into two disjoint equipollent subsets and let your involution exchange them.

By L Spice at Wed, 2010-02-03 07:00 | login or register to post comments

Why not?

Why not the following:

not x = if x is 0 then 1 else 0

It doesn't use "not", and it seems to me that it is the more common way of defining not; the two you mention would certainly surprise me if I came across them.

But I could be totally missing the point; maybe you want a one-to-one function?

[Sorry, I was missing the point; you want 1 is (not 2) == true I guess. In fact in my toy language I have two tokens, IS and NOT, and something like "expr := expr IS NOT expr", so it is "canonical" in the sense that one other person has done it!]

By zacharyrsnow at Tue, 2010-02-02 05:35 | login or register to post comments

Why not indeed?

Yes, you see the problem. Well, I have "solved" it for the common case by (as noted) being greedy and always binding the "not" tightly with the preceding "is" and creating a (pseudo)token is-not. (Of course, I could also have a keyword "isnt" or even "aint"! But that wouldn't evade the problem as long as "is" and "not" might still combine."

This solution still won't stop "problems" if people parenthesize to force evaluation order, as in your 1 is (not 2). But then I just say caveat programmer. Or... a bit of type-checking or coercion could be in order!

BTW, thanks all for your contributions. The S/N level on this blog is very high. :)

By andrewzboard at Tue, 2010-02-02 17:13 | login or register to post comments

The path I have chosen is as

The path I have chosen is as follows: "is not" is a pseudo-token as we both seem to understand it, but a free "not" is meaningless (so I have no issues with 1 is (not 2), and so on).

Then, why not use "!" (as I have) or some other token as Boolean negation? Since you want Boolean negation to be defined on all types, you've got to come up with a reasonable definition; maybe something like this:

!true = false
!false = true
!(x : int) = !(intToBool x)
!(x : string) = !(stringToBool x)

The point is that "!" really means Boolean negation, just like "-" really means numeric negation -- you will probably run into the same problems you were already having when it comes to unary minus. That is, try to let "!" and "-" have one meaning, not one per type.

For instance, what should unary minus mean for strings? I'm not sure, but if instead unary minus is really numeric negation, then its definition suggests itself:

-(x : int) = 0 - x
-(x : bool) = -(boolToInt x)
-(x : string) = -(stringToInt x)

Of course this sort of puts off the problem to defining these coercions, but I think these relatively simple definitions might be good enough:

intToBool(0) = false
intToBool(_) = true
stringToBool("") = false
stringToBool(_) = true

etc.

Anyway, the point is essentially that you might want "!" and "-" to have a meaning that is independent of the type of the argument. If you don't, the problem is that there isn't really a "correct" interpretation of, say, Boolean negation for integers, and so any of the examples you've given are correct, even if they are lead to unintuitive results. In fact, I would guess that they are unintuitive precisely because they don't implement Boolean negation is some sense.

[Not sure if the above is useful.]

By zacharyrsnow at Tue, 2010-02-02 17:45 | login or register to post comments

You could imitate Python

In Python "not" always returns a boolean value. It first converts its argument into a boolean and then inverts it (IMHO). User defined classes can implement a special function ("__nonzero__") that converts their instances to booleans.

Example session:

IPython 0.10 -- An enhanced Interactive Python.

In [1]: not 1
Out[1]: False

In [2]: not 0
Out[2]: True

In [3]: not "qwert"
Out[3]: False

In [4]: not ""
Out[4]: True

In [5]: bool("qwert")
Out[5]: True

By Eike Welk at Tue, 2010-02-02 21:53 | login or register to post comments

is snot

My mother was always quite insistent that I replace spoken "is not" with "isn't".

I favor binding the 'not' to the preceding 'is'.

x is y => x = y

x is not y => x != y

x isn't y => x != y

[Edit:]

I'd also suggest that (not N) for arbitrary integer N, not be an integer. Semantically, it should be a logic or constraint type.

2 is (not 3) should be false, otherwise you end up with weird transitivity semantics (if 2 is (not 3) and 5 is (not 3), this implies 2 is 5, does it not?

By dmbarbour at Tue, 2010-02-02 22:40 | login or register to post comments

I agree with dmbarbour

If 'not' binds to the right then (not 3) says to me "the set of everything excluding 3".

2 is (not 3) would be false, but 2 is-in (not 3) or 2 element-of (not 3) could be true.

By Rehno Lindeque at Wed, 2010-02-03 07:15 | login or register to post comments

coercive not

Good points. As well as binding the "is" tightly to "not", when I see a free-floating unary not, it will coerce its operand to an "asBoolean". Which for numbers is the (already suggested) zero if non-zero and 1 if zero.

This doesn't go quite as far as you suggest, having the result be a non-int. It would be cool if I could return a set (lazily evaluated, one would hope!) of all integers (or reals) excluding the operand.

By andrewzboard at Wed, 2010-02-03 16:27 | login or register to post comments

I take it back...

Oops, I must backtrack. For not(#), I ain't coercing. I'm using the 1-x approach. Could change my mind. We will see if this "polymorphously perverse" approach goes over well, or winds up looking a bit too much like APL re-animated. :)

By andrewzboard at Wed, 2010-02-03 18:16 | login or register to post comments