Extending the shunting-yard algorithm to support the conditional ternary operator - ternary-operator

How to extend the shunting yard algorithm, that's originally meant for binary operators to support the conditional ternary operator ("a ? b : c") ?
I haven't seen an answer to this here and I have one, so I'm posting it.

The way I did it was to add three new operators:
"?" ternary-open-if
":" ternary-else
ternary-closed-if
Only the first two will be created directly when reading the initial expression.
However, only the third one will exists in the output (the RPN of the initial expression).
The ternary-open-if is put on the operators stack whenever a "?" is seen.
The ternary-else is never put on the stack. Rather, the stack is poped until a ternary-open-if is found, then the ternary-open-if is replaced with the ternary-closed-if (thus indicating that we're in the else part of the conditional operator).
All three operators have higher precedence than all other operators (higher meaning they're evaluated AFTER other operators).
The ternary-if operators have the same precedence and right associativity (like in C), meaning that a ternary-if will never cause a pop of another ternary-if.
The ternary-else has a precedence higher than the ternary-ifs, and its associativity is irrelevant (since it is never put on the stack). So, when encountering a ternary-open-if it will convert it to a closed one as mentioned before.
When encountering a ternary-closed-if it will pop it.
Examples (ternary-closed-if notated as "?:"):
"a ? b : c" -->
"a b c ?:"
"a ? b : x ? y : z" -->
"a b x y z ?: ?:"
"a ? x ? y : z : b" -->
"a x y z ?: b ?:"
This method is more hard to explain than to implement, and it does make a slight change to the algorithm, so if anyone has a simpler solution, please post it.

Related

prolog syntax problem

I can't distinguish these symbols:
= and =:=
\= and =\=
[X,Y] and [X|Y]
What’s the difference ?
For the comparison operators (=, =:=, \=, =\=):
= succeeds if the terms unify (basically, if they're bound together)
=:= succeeds if the values of the terms are equal (should be equivalent to = if you're dealing with numbers, I believe)
\= is the negation of =
=\= is the negation of =:=
For more info about these operators and more, see this page.
For the list operators, [X|Y] is a way to refer to a list where X is the first element and Y is the list of the remaining elements. [X, Y] is just another way to refer to this, but it limits Y to being a single element, instead of possibly a whole list of them. For more info, see this section of the same page.

How to do an inductive definition over “booleans” in Isabelle

In Isabelle, I want to define operators that take predicates 'a => bool and modify them based on the "inductive structure of predicates". For example, one might want to compute the Disjunctive Normal Form (DNF) on these predicates, e.g. D (λ x. P x --> Q x) = (λ x. ¬ P x \/ Q x).
The problem here is that bool is not an inductive datatype. I have thought of two possible solutions:
Create an inductive datatype that allows me to define my operators on them. Give predicate (P::'a => bool) semantics for this datatype and then use it to prove the lemmas I want to check.
Prove the theorems for each one of the possible inductive cases. Then show a general case that uses all of the previous rules.
As a third option, I am (wishfully) hoping that a more experienced Isabelle user might enlighten my approach with a secret function/typedef that circumvents this "inductive issue". So the questions here are:
Are there any other simpler options? If yes, which ones? If not, do any of my approaches seem flawed or doomed?
WARNING: I gave as an example, the DNF, however, the general case where the operator does not necessarily preserve the truth value of the predicate is of more interest to me, e.g. D could do this: D (λ x. P x /\ Q x) = (λ x. P x \/ Q x).
HOL functions cannot look into the syntactic representation of their arguments. The reason is the substitution axiom, i.e., logically equal terms may be replaced in any context. Otherwise, one could define a function D satisfying D (λ x. P x) = True and D (λ x. P x & True) = False, which leads to a proof of False.
For a function like conversion to DNF, whose semantics in HOL does not depend on the syntax of the argument, one can still define such a transformation. For the DNF conversion, the semantic operation is the identity, i.e.,
definition DNF :: "('a => bool) => ('a => bool)" where "D = id"
Then, you can derive rewriting rules that actually perform the conversion. For example,
lemma DNF_imp: "DNF (λx. P x --> Q x) = DNF (λx. ~ P x | Q x)"
If you call Isabelle's simplifier with such a dedicated set of rules, you effectively get a conversion into DNF (although you will never ever be able to formally express in HOL that your set of rules works in all cases).
Very often, rules like DNF_imp are not enough to implement such a function. In that case, you can write a simproc in Isabelle/ML which triggers on DNF _ terms and performs the transformation. Since you are stepping out of the logic, the simproc can look at the HOL syntax of the argument and behave differently for logically equal terms.
Conversely, if you do want to express and reason about the conversion function D within the logic, there is no way around to introduce syntax to work on, as you have suggested with a datatype.

foldList adverb in J

In response to the question of FoldList like primitive in J, I wanted to create an adverb fold so that x u fold y is to fold y with verb u and inital value x:
fold =: 2 : 0
z =.x
for_item. y do. z =. z u item end.
z
)
But I got error when trying it out:
1 (+fold) 1 2 3
|value error: x
| z=. x
what's wrong here? thanks.
Just a couple small things.
First, the numeric code for an adverb is 1. The 2 : 0 you have is defining a conjunction, not an adverb. The way it stands now, J is expecting two direct arguments to fold, and you've only provided one (the +; the two numeric arrays are indirect, not direct, arguments). However, that's not what J is complaining about here, because the other issue is actually tripping it up first. I'll get to that in a second, but nevertheless the first thing you need to do is define fold as an adverb [1].
The more immediate issue that J is complaining about is that it doesn't know what you mean by x. Why? For the same reason that it would if you replaced 2 : 0 (or conjunction define) -- or even, more pertinently, adverb define -- with verb define. Because explicit verbs (direct or derived) are monadic by default and have no x argument (hence mentioning x is a value error). If you want to define a dyadic verb, you must ask for it explicitly.
Now, defining a dyadic verb directly is straightforward: instead of saying verb define, you simply say dyad define. But deriving a dyadic verb from a modifier (adverb or conjunction) is a little less obvious. You must use the special colon syntax which allows you to separate the monadic and dyadic valences of explicit definitions. This syntax applies to all explicit definitions, including verbs, adverbs, and conjunctions, but for adverbs and conjunctions it is the only way to derive an explicit verb.
Bottom line:
fold =: adverb define
NB. Note solitary colon on next line. Everything after that is dyadic.
:
z =.x
for_item. y do. z =. z u item end.
z
)
[1]: You may find using the standard covers for nameclasses easier to remember (and read later), as in adverb define and conjunction define (for one-liners, you can use def in place of define).

Are there any right associative short-circuit operators

I'm working on a interrupter the lets one define their own operators. The goal then is to take an AST that looks like exp op exp op exp and turn it into either exp op (exp op exp) or (exp op exp) op exp based on the relative precedence and associativity of the two operators. The language is dynamic so the only way to know what version of the operator to use is to evaluate the first expression and ask it what version of op to use.
On the other hand, it is important that we not evaluate the second expression because if op is || (as commonly used) then we should be able to short-circuit if the first exp is false.
a problem would arise if some operator were both right associative and short-circuiting. My question is are there any right associative, short-circuiting operators in common use (for a chosen value of "common")?
N.b. assignment is handled separately by the parser so = is not an operator and a (op)= b is syntactic sugar for a = a op b.
Boolean implication might be.
I would probably read
a → b → c
as "a implies that b implies c" which would suggest that it should parenthesize
a → (b → c)
and boolean implication should probably be short-circuiting since when a is false then the right side of (a → b) is irrelevant to the result.

What's the -> operator in Prolog and how can I use it?

I've read about it in a book but it wasn't explained at all. I also never saw it in a program. Is part of Prolog syntax? What's it for? Do you use it?
Thanks
It represents implication. The righthand side is only executed if the lefthand side is true. Thus, if you have this code,
implication(X) :-
(X = a ->
write('Argument a received.'), nl
; X = b ->
write('Argument b received.'), nl
;
write('Received unknown argument.'), nl
).
Then it will write different things depending on it argument:
?- implication(a).
Argument a received.
true.
?- implication(b).
Argument b received.
true.
?- implication(c).
Received unknown argument.
true.
(link to documentation.)
It's a local version of the cut, see for example the section on control predicated in the SWI manual.
It is mostly used to implement if-then-else by (condition -> true-branch ; false-branch). Once the condition succeeds there is no backtracking from the true branch back into the condition or into the false branch, but backtracking out of the if-then-else is still possible. Therefore it is called local cut or soft cut.
It is possible to avoid using it by writing something more wordy. If I rewrite Stephan's predicate:
implication(X) :-
(
X = a,
write('Argument a received.'), nl
;
X = b,
write('Argument b received.'), nl
;
X \= a,
X \= b,
write('Received unknown argument.'), nl
).
(Yeah I don't think there is any problem with using it, but my boss was paranoid about it for some reason, so we always used the above approach.)
With either version, you need to be careful that you are covering all cases you intend to cover, especially if you have many branches.
ETA: I am not sure if this is completely equivalent to Stephan's, because of backtracking if you have implication(X). But I don't have a Prolog interpreter right now to check.

Resources