Ternary C extensions

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Ternary C extensions

Postby You, sir, name? » Wed Mar 26, 2008 8:34 pm UTC

I'm not sure if this goes in coding or in CS, but I'll try putting it here.

I'm looking to implement a C-like language for a ternary computer emulator (see .sig). I've gotten a fairly long way along the road, but I feel I haven't quite taken advantage of the architecture. Right now it pretty much looks and feels like C. The only changes I have made are

Removal of the ~-operator. It is useless in balanced ternary, since two's complement isn't used and the minus operator does the same thing as ~ would. Instead, it's gotten the functionality of returning the sign of a value: -TYPE_MAX if negative, 0 if zero, TYPE_MAX if positive.

A quadternary complement of the ternary operator.
Both
expr ? expr : expr //(true, false)
and
expr ? expr: expr: expr // (true, unknown, false)
are valid.

I'd like to extend if-else with some third state. I'm leaning towards if-mu-else, where, if mu is omitted, it collapses back into the regular if-else behavior. I'm not quite sure on the name though, I've tried if-perhaps-else, if-maybe-else, etc. None of them sits quite right...

I'd appreciate suggestions and ideas.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Ternary C extensions

Postby EvanED » Wed Mar 26, 2008 8:56 pm UTC

I would just suggest that the "unknown" case be listed last... in other words, <cond> ? <true> : <false> : <unknown>; and if <cond> { <true> } else { <true> } mu { <unknown> }, but this may be just personal preference.

(Also, I have signatures disabled, so don't know what's in it.)

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Ternary C extensions

Postby You, sir, name? » Wed Mar 26, 2008 9:10 pm UTC

EvanED wrote:I would just suggest that the "unknown" case be listed last... in other words, <cond> ? <true> : <false> : <unknown>; and if <cond> { <true> } else { <true> } mu { <unknown> }, but this may be just personal preference.



Hm, that might be a good idea. More syntactically backwards compatible with regular C.

EvanED wrote:(Also, I have signatures disabled, so don't know what's in it.)

.sig wrote:I've tinkered together a small ternary (a.k.a. 'trinary') computer emulator loosely based on the 6502. Try it out. Maycauseinsanityseizureorspontaneoushumancombustion.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Ternary C extensions

Postby Xanthir » Wed Mar 26, 2008 10:15 pm UTC

Hmm. I'm assuming you're using a form of ternary logic where -1 = FALSE, 1 = TRUE, and 0 = UNKNOWN.

I wouldn't use if/else at all, actually. That verbage reeks of binary logic. Now, if/else should *exist*, certainly, because plenty of times you won't *need* a full trivalent boolean and just want a good ol' binary test, but when you're testing for trinary values I'd suggest using the terms true/false/unknown for the control structure.

This makes it nice and explicit, and also clearly shows when you're testing for a trivalent boolean and when you're just interested in a binary boolean.

Edit: So it would look like:

Code: Select all

true( ::some boolean test:: ) {
  blah;
  blah;
} false {
  blah;
  blah;
} unknown {
  blah;
  blah;
}
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Ternary C extensions

Postby You, sir, name? » Wed Mar 26, 2008 10:42 pm UTC

Xanthir wrote:Hmm. I'm assuming you're using a form of ternary logic where -1 = FALSE, 1 = TRUE, and 0 = UNKNOWN.


Yeah, that's how I've implemented it. I was considering 0 = FALSE, 1 = TRUE, -1 = UNKNOWN, because it would be more binary compatible, but then positive = true, negative = false seemed more intuitive.

Xanthir wrote:I wouldn't use if/else at all, actually. That verbage reeks of binary logic. Now, if/else should *exist*, certainly, because plenty of times you won't *need* a full trivalent boolean and just want a good ol' binary test, but when you're testing for trinary values I'd suggest using the terms true/false/unknown for the control structure.

This makes it nice and explicit, and also clearly shows when you're testing for a trivalent boolean and when you're just interested in a binary boolean.

Edit: So it would look like:

Code: Select all

true( ::some boolean test:: ) {
  blah;
  blah;
} false {
  blah;
  blah;
} unknown {
  blah;
  blah;
}


I'm really liking how that looks.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Ternary C extensions

Postby evilbeanfiend » Thu Mar 27, 2008 2:13 pm UTC

it may interest you to look at some HDL's they typically have multipvalue logic to model busses, VHDL uses 9-value logic iirc
(U, X, 1, 0, W, H, L, Z, -)

systemC in particular has 4-value logic (1 , 0 , Z , X) and is mostly a c++ library.

of course with HDL the different values have quite specific meanings e.g.
U = unitialised
X = bus contention (driving a 1 and a 0 on the same wire)
1 = true
0 = false
W = weak contention (driving a H and a L on the same wire) iirc
H = float high iirc (a bit like 1 but a 0 can be driven on at the same time without causing contention)
L = float low iirc (a bit like 0 but a 1 can be driven on at the same time without causing contention)
Z = high impedence (nothing driving the bus at all)
- = don't care
in ur beanz makin u eveel

Horsman
Posts: 16
Joined: Fri Mar 21, 2008 5:49 pm UTC

Re: Ternary C extensions

Postby Horsman » Thu Mar 27, 2008 11:07 pm UTC

Cool, I ran into your emulator on freshmeat earlier today. Good luck.

GrahamM
Posts: 4
Joined: Tue Apr 01, 2008 10:33 pm UTC

Re: Ternary C extensions

Postby GrahamM » Sat Apr 05, 2008 1:16 am UTC

Do you have an operator which cycles through the three possible values? I.e. the operator (Let's call it #, for example) does:

#-1 = 0
#0 = 1
#1 = -1

Or one which goes in the opposite direction? (Let's say, @):

@-1=1
@0=-1
@1=0

Would there be any use for something like this?

User avatar
aleflamedyud
wants your cookies
Posts: 3307
Joined: Tue Oct 09, 2007 7:50 pm UTC
Location: The Central Bureaucracy

Re: Ternary C extensions

Postby aleflamedyud » Sat Apr 05, 2008 2:14 am UTC

Why not just implement a cond statement? It's a lot more flexible than a mere three-fork conditional branch.

EDIT: And an optimizing compiler can turn it into a three-fork conditional branch if that's what the coder wrote.
"With kindness comes naïveté. Courage becomes foolhardiness. And dedication has no reward. If you can't accept any of that, you are not fit to be a graduate student."

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Ternary C extensions

Postby You, sir, name? » Sat Apr 05, 2008 9:35 am UTC

GrahamM wrote:Do you have an operator which cycles through the three possible values? I.e. the operator (Let's call it #, for example) does:

#-1 = 0
#0 = 1
#1 = -1

Or one which goes in the opposite direction? (Let's say, @):

@-1=1
@0=-1
@1=0

Would there be any use for something like this?


I have an operator that does that on a trit-level that shifts sort of like you describe. To get exactly your behavior, you simply use TYPE_MAX and -TYPE_MAX. Say you have two values <-1, 0, 0, 1> # <0, 1, 1, -1> = <-1, 1, 1, 0>.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

coppro
Posts: 117
Joined: Mon Feb 04, 2008 6:04 am UTC

Re: Ternary C extensions

Postby coppro » Sun Apr 27, 2008 5:32 am UTC

You, sir, name? wrote:A quadternary complement of the ternary operator.
Both
expr ? expr : expr //(true, false)
and
expr ? expr: expr: expr // (true, unknown, false)
are valid.
That won't work. In this code:
expr ? expr ? expr : expr : expr : expr
it's ambiguous as to the expression the second colon should bind to. I'd recommend another symbol for this - perhaps :? or ?: would look good.

Checked the "disable smilies" post to keep it from turning :? into one.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Ternary C extensions

Postby EvanED » Sun Apr 27, 2008 6:35 am UTC

This may or may not be a problem though. After all, if() {..} if() {...} else {...} is ambiguous, and yet that's allowed all the C-like languages AFAIK. They disambiguate by arbitrarily picking which 'if' the 'else' binds to.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Ternary C extensions

Postby Xanthir » Mon Apr 28, 2008 7:17 pm UTC

EvanED wrote:This may or may not be a problem though. After all, if() {..} if() {...} else {...} is ambiguous, and yet that's allowed all the C-like languages AFAIK. They disambiguate by arbitrarily picking which 'if' the 'else' binds to.

I don't think you meant to put the braces there, because afaict that's not ambiguous at all. Maybe something like this?

Code: Select all

if(condition1)
    if(condition2)
        blah1;
else
    blah2;

That's valid but definitely ambiguous. And considering that *every* code styling guide requires braces around your if/else blocks specifically so ambiguous crap like this doesn't happen (in addition to the "I was only using one line of code for that condition originally!" bug), I'd say making it explicit is a good thing.

Ambiguous code is crap. It means the spec authors failed.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Ternary C extensions

Postby Berengal » Tue Apr 29, 2008 1:09 am UTC

Xanthir wrote:Ambiguous code is crap. It means the spec authors failed.

Agreed, but most IDEs will catch this. if you go "if (statement) something;", it'll go "NO! DEDENT!" when you press enter. If you go

Code: Select all

if(condition1)
    if(condition2)
        blah1;
else
    blah2;

It will go "NO! REINDENT!" and reindent the else.

Also, the "if-if-else" isn't as much ambiguous as it's hard to follow for humans. An else binds to the last if available, and an "if-else" is considered a single statement which doesn't need braces inside another if.
It's sort of like parenthesis-matching, except the parenthesis don't need closing.

Code: Select all

if (true) if (false);else System.out.println("Foo"); else System.out.println("Bar");
if (true)               [statement]                ; else System.out.println("Bar");

Note that if you ever write code like this, without the brackets, you deserve to be shot.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Ternary C extensions

Postby EvanED » Tue Apr 29, 2008 1:36 am UTC

Xanthir wrote:
EvanED wrote:This may or may not be a problem though. After all, if() {..} if() {...} else {...} is ambiguous, and yet that's allowed all the C-like languages AFAIK. They disambiguate by arbitrarily picking which 'if' the 'else' binds to.

I don't think you meant to put the braces there, because afaict that's not ambiguous at all.

I did make a mistake. The first set of braces (including the "...") shouldn't be there. if() if() {...} else {...} is what I intended to write.

I knew I should have written it out on multiple lines.

And considering that *every* code styling guide requires braces around your if/else blocks specifically so ambiguous crap like this doesn't happen (in addition to the "I was only using one line of code for that condition originally!" bug), I'd say making it explicit is a good thing.

I agree. But style guides could also specify that you should put parens around ?: statements.

Ambiguous code is crap. It means the spec authors failed.

Regardless of whether your style manual tells you how to bracket it, C-like languages still pretty much all accept the ambiguous form above. Does that mean that the designers of C, C++, Java, C#, hell, all the way back to ALGOL and who knows what else all failed on account of it?

Berengal wrote:Also, the "if-if-else" isn't as much ambiguous as it's hard to follow for humans. An else binds to the last if available, and an "if-else" is considered a single statement which doesn't need braces inside another if.

I realize that. But again, the same thing could probably be done with ambiguous ?: expressions.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Ternary C extensions

Postby Xanthir » Tue Apr 29, 2008 4:00 am UTC

EvanED wrote:
Xanthir wrote:Ambiguous code is crap. It means the spec authors failed.

Regardless of whether your style manual tells you how to bracket it, C-like languages still pretty much all accept the ambiguous form above. Does that mean that the designers of C, C++, Java, C#, hell, all the way back to ALGOL and who knows what else all failed on account of it?


In this case, yes. The C family and predecessors assumed that anything they could *possibly* disambiguate should be allowed, even if was far from clear in writing. This is a bad thing. A bit of flexibility can be useful, but explicitness in syntax is a wonderful thing. It's now far too late for the C family to change, but that doesn't suddenly make their decision correct.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Ternary C extensions

Postby EvanED » Tue Apr 29, 2008 4:02 am UTC

And yet new language like Java still allow you to write if statements without braces. Of all the decisions Java's designers made, I would have been far happier with that than many of their others...

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Ternary C extensions

Postby Berengal » Tue Apr 29, 2008 4:45 am UTC

Forcing braces around conditional expression just one line long would be bad. Why? Because you would either need a new keyword "elif" (like python does), or you'd have to write your else if's like

Code: Select all

if (foo){
  ...
} else { if (bar) {
  ...
} else { if (baz){
  ...
}}}

You don't have to do this in the current system because "if [else]" is considered a single statement which doesn't require braces. It might not look like it, but the current else if's are nested syntactically, not level like the switch statement, or lisp's cond, or python's if-elif-else.
I could survive a new keyword though, or a more powerful, fallthroughless switch statement. Something like

Code: Select all

conditional (n > 1){
  return n+(n-1);
} (n < 0) {
  return (n+1) - n;
} else {
  return 1;
}

This is essentially just an if-else if-else structure, but without the "else if" inbetween. Anything that evaluates to a boolean immediately after a case followed by a set of braces is considered a continuation of the conditional. The else terminates it (allowing a final statement, of course). Also, a semicolonless boolean followed by a scope is invalid everywhere else but as a continuation of a "conditional" statement, so it shouldn't be ambiguous. The advantage over the if-else paradigm is a level syntax, so you can force braces without adding more ending braces as you add more items to the conditional.

I could be persuaded to shorted the keyword to "cond".
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Rysto
Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Ternary C extensions

Postby Rysto » Tue Apr 29, 2008 2:42 pm UTC

EvanED wrote:And yet new language like Java still allow you to write if statements without braces. Of all the decisions Java's designers made, I would have been far happier with that than many of their others...

It's not really an ambiguity -- it's not hard to write a CFG that disambiguates that case.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Ternary C extensions

Postby EvanED » Tue Apr 29, 2008 7:25 pm UTC

Berengal wrote:Forcing braces around conditional expression just one line long would be bad. Why? Because you would either need a new keyword "elif" (like python does), or you'd have to write your else if's like

Code: Select all

if (foo){
  ...
} else { if (bar) {
  ...
} else { if (baz){
  ...
}}}

You don't have to do this in the current system because "if [else]" is considered a single statement which doesn't require braces. It might not look like it, but the current else if's are nested syntactically, not level like the switch statement, or lisp's cond, or python's if-elif-else.

They could also special case it out. Currently there might be something like

Code: Select all

if_stmt ::= "if" "(" expr ")" stmt | "if" "("expr") stmt "else" stmt ;
stmt ::= if_stmt | while_stmt | ... | "{" stmt_list "}" ;
stmt_list ::= stmt ";" stmt_list

As orginally worded, I was suggesting

Code: Select all

if_stmt ::= "if" "(" expr ")" stmt_list | "if" "(" expr ")" stmt "else" stmt_list

But you could also use

Code: Select all

if_stmt ::= "if" "(" expr ")" stmt_list | "if" "(" expr")" stmt_list "else" stmt_list_or_if ;
stmt_list_or_if ::= stmt_list | if_stmt ;


I didn't actually verify that this does what I want, but I think it does.

Rysto wrote:
EvanED wrote:And yet new language like Java still allow you to write if statements without braces. Of all the decisions Java's designers made, I would have been far happier with that than many of their others...

It's not really an ambiguity -- it's not hard to write a CFG that disambiguates that case.

And thus missing my point... it would also probably be easy to write a CFG that would make the ?: "ambiguity" that originally got us on this track unambiguous.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Ternary C extensions

Postby Berengal » Wed Apr 30, 2008 1:14 am UTC

EvanED wrote:I didn't actually verify that this does what I want, but I think it does.
Looks like it. What you've done is essentially turn "else if" into a keyword. I guess "cond" vs "if-elif-else" vs "if-else if-else" is a religious war then, since I see no objective superiority of one over the other.

EvanED wrote:And thus missing my point... it would also probably be easy to write a CFG that would make the ?: "ambiguity" that originally got us on this track unambiguous.

You could force the ternary ?: to take three outcomes all the time. That way "expr1? expr2? expr3: expr4: expr5: expr6" wouldn't be ambiguous, and would read like "expr1? [trinary ?:]: epxr6", which is illegal since the outer one is lacking a statement. You could also introduce a new binary operator that reads something like "expr?* trueexpr:* falseexpr" and works exactly like the c ternary operator except unknown does nothing. That way you could write "expr1? expr2?* expr3:* expr4: expr5: expr6" clearly. Switch them around? "expr1?* expr2? expr3: expr4: expr5:* expr6". This seems unambiguous enough for me.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 7 guests