OrcWiki: ExpressionProperties
https://orc.csres.utexas.edu/wiki/
The Orc programming language project wiki (wiki changes feed)en-usJSPWiki 2.10.2
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=7
ExpressionProperties, version 7Arthur Peters changed this page on Wed Oct 17 17:33:43 CDT 2012:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 3 changed 2 lines</td></tr>
<tr><td class="diffrem">* Helpful: Always sends a negative result when it has finished publishing (0 or more results).</td></tr>
<tr><td class="diffrem">* Side-effect free: Does not have any side-effects and all information produced is in the forms of publications.[{orc runnable='false'</td></tr>
<tr><td class="diffadd">* __Helpful__: Always sends a negative result when it has finished publishing (0 or more results).</td></tr>
<tr><td class="diffadd">* __Side-effect free__: Does not have any side-effects and all information produced is in the forms of publications.[{orc runnable='false'</td></tr>
<tr><td class="diff">At line 8 changed 2 lines</td></tr>
<tr><td class="diffrem">* Pure: Its publications (0 or more) are always the same given the same arguments or values for free variables, and it is side-effect free. This is a generalization of pure functions similar to pure non-deterministic functions. </td></tr>
<tr><td class="diffrem">* Pure Functional: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.[{orc runnable='false'</td></tr>
<tr><td class="diffadd">* __Pure__: Its publications (0 or more) are always the same given the same arguments or values for free variables, and it is side-effect free. This is a generalization of pure functions similar to pure non-deterministic functions. </td></tr>
<tr><td class="diffadd">* __Pure Functional__: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.[{orc runnable='false'</td></tr>
<tr><td class="diff">At line 14 changed 2 lines</td></tr>
<tr><td class="diffrem">* Asynchronous: Ordering of publications of subexpressions does not affect the set of possible results of the expression. (TODO: is this correct?)</td></tr>
<tr><td class="diffrem">* Silent: Never publishes a value.[{orc runnable='false'</td></tr>
<tr><td class="diffadd">* __Asynchronous__: Ordering of publications of subexpressions does not affect the set of possible results of the expression. (TODO: is this correct?)</td></tr>
<tr><td class="diffadd">* __Silent__: Never publishes a value.[{orc runnable='false'</td></tr>
<tr><td class="diff">At line 19 changed 5 lines</td></tr>
<tr><td class="diffrem">* Deterministic: Will always produce the same result regardless of order of publication or scheduling. Note that asynchronous expressions can still be non-deterministic. (TODO: is this correct?)</td></tr>
<tr><td class="diffrem">* Resilient: The expression will ''not'' terminate if pruned.</td></tr>
<tr><td class="diffrem">* Atomic: The expression {{{e}}} is not effected by concurrently running expressions (including other copies of {{{e}}}). This is probably both atomic and co-atomic (in Kitchen terms).</td></tr>
<tr><td class="diffrem">* Blocking: The expression will always eventually respond.</td></tr>
<tr><td class="diffrem">* Strict: All free variables in {{{e}}} are needed without delay. All site calls are strict. The charactature for strict on {{{x}}} is: [{orc runnable='false'</td></tr>
<tr><td class="diffadd">* __Deterministic__: Will always produce the same result regardless of order of publication or scheduling. Note that asynchronous expressions can still be non-deterministic. (TODO: is this correct?)</td></tr>
<tr><td class="diffadd">* __Resilient__: The expression will ''not'' terminate if pruned.</td></tr>
<tr><td class="diffadd">* __Atomic__: The expression {{{e}}} is not effected by concurrently running expressions (including other copies of {{{e}}}). This is probably both atomic and co-atomic (in Kitchen terms).</td></tr>
<tr><td class="diffadd">* __Blocking__: The expression will always eventually respond.</td></tr>
<tr><td class="diffadd">* __Strict__: All free variables in {{{e}}} are needed without delay. All site calls are strict. The charactature for strict on {{{x}}} is: [{orc runnable='false'</td></tr>
<tr><td class="diff">At line 27 changed one line</td></tr>
<tr><td class="diffrem">* Idempotent: Executing an expression more than once has the same effect as executing it once.[{orc runnable='false'</td></tr>
<tr><td class="diffadd">* __Idempotent__: Executing an expression more than once has the same effect as executing it once.[{orc runnable='false'</td></tr>
<tr><td class="diff">At line 31 changed one line</td></tr>
<tr><td class="diffrem">* Talkative: Publishes at least once.</td></tr>
<tr><td class="diffadd">* __Talkative__: Publishes at least once.</td></tr>
<tr><td class="diffadd">* __Terminating__: Will eventually terminate even if it is not pruned.</td></tr>
<tr><td class="diff">At line 43 added 13 lines</td></tr>
<tr><td class="diffadd">!!!Decidability</td></tr>
<tr><td class="diffadd">Some of there properties are decidable based on axioms about sites. However most are not. For the undecidable properties it would still be possible to create a conservative estimate that will detect many useful cases of the property.</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">* __Side-effect free__ is decided by: [{orc runnable='false'</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">sideEffectFree (f | g) = sideEffectFree f && sideEffectFree g</td></tr>
<tr><td class="diffadd">sideEffectFree (f >x> g) = sideEffectFree f && (if not silent f then sideEffectFree g else true)</td></tr>
<tr><td class="diffadd">sideEffectFree (f <x< g) = sideEffectFree f && sideEffectFree g</td></tr>
<tr><td class="diffadd">sideEffectFree (f ; g) = sideEffectFree f && (if not talkative f then sideEffectFree g else true)</td></tr>
<tr><td class="diffadd">}] (this has not been proved correct)</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">This section should be completed with deciders and estimates for other properties.</td></tr>
<tr><td class="diffadd"></td></tr>
</table>Wed, 17 Oct 2012 22:33:43 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=6
ExpressionProperties, version 6Arthur Peters changed this page on Wed Oct 17 16:51:50 CDT 2012:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 8 changed 2 lines</td></tr>
<tr><td class="diffrem">* Pure: Its publications (0 or more) are derived only from its arguments (or bound variables) and it has no side effects. This is a generalization of pure functions similar to pure non-deterministic functions. </td></tr>
<tr><td class="diffrem">* Functional: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.[{orc runnable='false'</td></tr>
<tr><td class="diffadd">* Pure: Its publications (0 or more) are always the same given the same arguments or values for free variables, and it is side-effect free. This is a generalization of pure functions similar to pure non-deterministic functions. </td></tr>
<tr><td class="diffadd">* Pure Functional: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.[{orc runnable='false'</td></tr>
<tr><td class="diff">At line 13 changed one line</td></tr>
<tr><td class="diffrem">}]</td></tr>
<tr><td class="diffadd">}] </td></tr>
<tr><td class="diff">At line 19 changed one line</td></tr>
<tr><td class="diffrem">* Deterministic: Will always produce the same result regardless of order of publication. Note that asynchronous expressions can still be non-deterministic. (TODO: is this correct?)</td></tr>
<tr><td class="diffadd">* Deterministic: Will always produce the same result regardless of order of publication or scheduling. Note that asynchronous expressions can still be non-deterministic. (TODO: is this correct?)</td></tr>
<tr><td class="diff">At line 23 changed one line</td></tr>
<tr><td class="diffrem">* Strictness: All free variables in {{{e}}} are needed without delay. All site calls are strict. The charactature for strict on {{{x}}} is: [{orc runnable='false'</td></tr>
<tr><td class="diffadd">* Strict: All free variables in {{{e}}} are needed without delay. All site calls are strict. The charactature for strict on {{{x}}} is: [{orc runnable='false'</td></tr>
<tr><td class="diff">At line 26 changed one line</td></tr>
<tr><td class="diffrem">}] where {{{<x<$}}} performs termination but not late binding.</td></tr>
<tr><td class="diffadd">}] where {{{<x<$}}} performs termination but not late binding. Expressions can also be strict in specific variables and non-strict in others.</td></tr>
<tr><td class="diff">At line 31 changed one line</td></tr>
<tr><td class="diffrem">* Safe (or some better term): Publishes at least once.</td></tr>
<tr><td class="diffadd">* Talkative: Publishes at least once.</td></tr>
</table>Wed, 17 Oct 2012 21:51:50 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=5
ExpressionProperties, version 5Arthur Peters changed this page on Fri Oct 05 16:01:23 CDT 2012:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 31 added one line</td></tr>
<tr><td class="diffadd">* Safe (or some better term): Publishes at least once.</td></tr>
</table>Fri, 05 Oct 2012 21:01:23 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=4
ExpressionProperties, version 4Arthur Peters changed this page on Fri Oct 05 12:26:14 CDT 2012:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 7 changed 2 lines</td></tr>
<tr><td class="diffrem">}]</td></tr>
<tr><td class="diffrem">* Pure: Its publications (0 or more) are derived only from its arguments (or bound variables) and it has no side effects. This is a generalization of pure functions similar to pure non-deterministic functions.</td></tr>
<tr><td class="diffadd">}]An asynchronous side-effect free expression can be replaced with an expression {{{v1 | v2 | ... | vn}}} where {{{vi}}} are all the publications of the expression. A synchronous side-effect free expression is equivalent to: {{{Rwait(t1) >> v1 | Rwait(t2) >> v2 | ... | Rwait(tn) >> vn}}} where each pair {{{(ti, vi)}}} is a publication time and value.</td></tr>
<tr><td class="diffadd">* Pure: Its publications (0 or more) are derived only from its arguments (or bound variables) and it has no side effects. This is a generalization of pure functions similar to pure non-deterministic functions. </td></tr>
<tr><td class="diff">At line 20 changed 5 lines</td></tr>
<tr><td class="diffrem">* Resilient?</td></tr>
<tr><td class="diffrem">* Atomic?</td></tr>
<tr><td class="diffrem">* Blocking?</td></tr>
<tr><td class="diffrem">* Strictness on variables in scope?</td></tr>
<tr><td class="diffrem">* Idempotent?</td></tr>
<tr><td class="diffadd">* Resilient: The expression will ''not'' terminate if pruned.</td></tr>
<tr><td class="diffadd">* Atomic: The expression {{{e}}} is not effected by concurrently running expressions (including other copies of {{{e}}}). This is probably both atomic and co-atomic (in Kitchen terms).</td></tr>
<tr><td class="diffadd">* Blocking: The expression will always eventually respond.</td></tr>
<tr><td class="diffadd">* Strictness: All free variables in {{{e}}} are needed without delay. All site calls are strict. The charactature for strict on {{{x}}} is: [{orc runnable='false'</td></tr>
<tr><td class="diff">At line 25 added 7 lines</td></tr>
<tr><td class="diffadd">e <x< f =~~= e <x<$ f</td></tr>
<tr><td class="diffadd">}] where {{{<x<$}}} performs termination but not late binding.</td></tr>
<tr><td class="diffadd">* Idempotent: Executing an expression more than once has the same effect as executing it once.[{orc runnable='false'</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">e | e =~~= e</td></tr>
<tr><td class="diffadd">}] This is not be an accurate characture because {{{e}}} may not be atomic so it might conflict with itself. However {{{e >> e =~~= e}}} would not be correct either unless {{{e}}} is asynchronous.</td></tr>
<tr><td class="diffadd"></td></tr>
</table>Fri, 05 Oct 2012 17:26:14 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=3
ExpressionProperties, version 3Arthur Peters changed this page on Fri Oct 05 02:18:14 CDT 2012:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 20 added 5 lines</td></tr>
<tr><td class="diffadd">* Resilient?</td></tr>
<tr><td class="diffadd">* Atomic?</td></tr>
<tr><td class="diffadd">* Blocking?</td></tr>
<tr><td class="diffadd">* Strictness on variables in scope?</td></tr>
<tr><td class="diffadd">* Idempotent?</td></tr>
</table>Fri, 05 Oct 2012 07:18:14 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=2
ExpressionProperties, version 2Arthur Peters changed this page on Sun Sep 30 13:49:50 CDT 2012:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 4 changed 5 lines</td></tr>
<tr><td class="diffrem">* Pure: Its publications (0 or more) are derived only from its arguments (or bound variables) and it has no side effects.</td></tr>
<tr><td class="diffrem">* Functional: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.</td></tr>
<tr><td class="diffrem">* Asynchronous: (TODO: This is a poor definition) Is not effected by timing or order of publications and does not publish in a way the timing or order are important.</td></tr>
<tr><td class="diffrem">* Silent: Never publishes a value.</td></tr>
<tr><td class="diffrem">* Deterministic: Will always produce the same result regardless of order of publication. Note that asynchronous expressions can still be non-deterministic.</td></tr>
<tr><td class="diffadd">* Side-effect free: Does not have any side-effects and all information produced is in the forms of publications.[{orc runnable='false'</td></tr>
<tr><td class="diff">At line 6 added 15 lines</td></tr>
<tr><td class="diffadd">e >> stop =~~= stop </td></tr>
<tr><td class="diffadd">}]</td></tr>
<tr><td class="diffadd">* Pure: Its publications (0 or more) are derived only from its arguments (or bound variables) and it has no side effects. This is a generalization of pure functions similar to pure non-deterministic functions.</td></tr>
<tr><td class="diffadd">* Functional: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.[{orc runnable='false'</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">e =~~= x <x< e</td></tr>
<tr><td class="diffadd">e >> stop =~~= stop </td></tr>
<tr><td class="diffadd">}]</td></tr>
<tr><td class="diffadd">* Asynchronous: Ordering of publications of subexpressions does not affect the set of possible results of the expression. (TODO: is this correct?)</td></tr>
<tr><td class="diffadd">* Silent: Never publishes a value.[{orc runnable='false'</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">e =~= e >> stop</td></tr>
<tr><td class="diffadd">}]</td></tr>
<tr><td class="diffadd">* Deterministic: Will always produce the same result regardless of order of publication. Note that asynchronous expressions can still be non-deterministic. (TODO: is this correct?)</td></tr>
<tr><td class="diffadd"></td></tr>
</table>Sun, 30 Sep 2012 18:49:50 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExpressionProperties&version=1
ExpressionProperties, version 1Arthur Peters created this page on Thu Sep 27 18:22:45 CDT 2012:<br /><hr /><br /><h2 id="section-ExpressionProperties-PropertiesOfExpressions">Properties of Expressions<a class="hashlink" href="#section-ExpressionProperties-PropertiesOfExpressions">#</a></h2>
<ul><li><b>Helpful</b>: Always sends a negative result when it has finished publishing (0 or more results).
</li><li><b>Side-effect free</b>: Does not have any side-effects and all information produced is in the forms of publications.<div><script src="/orchard/orc.js" type="text/javascript"></script>
<link rel="stylesheet" type="text/css" href="/orchard/orc.css" media="screen"/><script type="text/javascript">function orcSpoiler(a) {var $a = jQuery(a);var $orc = $a.next();$orc.css('display', 'none');$orc.css('visibility', 'visible');$orc.css('position', 'static');$orc.slideDown();$a.hide();}</script><pre class="orc-snippet">e >> stop =~~= stop</pre></div>An asynchronous side-effect free expression can be replaced with an expression <span style="font-family:monospace; white-space:pre;">v1 | v2 | ... | vn</span> where <span style="font-family:monospace; white-space:pre;">vi</span> are all the publications of the expression. A synchronous side-effect free expression is equivalent to: <span style="font-family:monospace; white-space:pre;">Rwait(t1) >> v1 | Rwait(t2) >> v2 | ... | Rwait(tn) >> vn</span> where each pair <span style="font-family:monospace; white-space:pre;">(ti, vi)</span> is a publication time and value.
</li><li><b>Pure</b>: Its publications (0 or more) are always the same given the same arguments or values for free variables, and it is side-effect free. This is a generalization of pure functions similar to pure non-deterministic functions.
</li><li><b>Pure Functional</b>: Always publishes exactly 1 value and is pure. Equivalent to a total mathematical function.<div><pre class="orc-snippet">e =~~= x <x< e
e >> stop =~~= stop</pre></div>
</li><li><b>Asynchronous</b>: Ordering of publications of subexpressions does not affect the set of possible results of the expression. (TODO: is this correct?)
</li><li><b>Silent</b>: Never publishes a value.<div><pre class="orc-snippet">e =~= e >> stop</pre></div>
</li><li><b>Deterministic</b>: Will always produce the same result regardless of order of publication or scheduling. Note that asynchronous expressions can still be non-deterministic. (TODO: is this correct?)
</li><li><b>Resilient</b>: The expression will <i>not</i> terminate if pruned.
</li><li><b>Atomic</b>: The expression <span style="font-family:monospace; white-space:pre;">e</span> is not effected by concurrently running expressions (including other copies of <span style="font-family:monospace; white-space:pre;">e</span>). This is probably both atomic and co-atomic (in Kitchen terms).
</li><li><b>Blocking</b>: The expression will always eventually respond.
</li><li><b>Strict</b>: All free variables in <span style="font-family:monospace; white-space:pre;">e</span> are needed without delay. All site calls are strict. The charactature for strict on <span style="font-family:monospace; white-space:pre;">x</span> is: <div><pre class="orc-snippet">e <x< f =~~= e <x<$ f</pre></div> where <span style="font-family:monospace; white-space:pre;"><x<$</span> performs termination but not late binding. Expressions can also be strict in specific variables and non-strict in others.
</li><li><b>Idempotent</b>: Executing an expression more than once has the same effect as executing it once.<div><pre class="orc-snippet">e | e =~~= e</pre></div> This is not be an accurate characture because <span style="font-family:monospace; white-space:pre;">e</span> may not be atomic so it might conflict with itself. However <span style="font-family:monospace; white-space:pre;">e >> e =~~= e</span> would not be correct either unless <span style="font-family:monospace; white-space:pre;">e</span> is asynchronous.
</li><li><b>Talkative</b>: Publishes at least once.
</li><li><b>Terminating</b>: Will eventually terminate even if it is not pruned.
</li></ul><p>There are probably a few more that would be useful. This is a work in progress.
</p>
<p>Many of these properties have characteristic identities which totally encode their meaning. For instance, an expression e is silent iff the following statement is true.
<div><pre class="orc-snippet">e =~= e >> stop</pre></div>
(where =~= is equivalence of expression in the semantics.) Similar statements can and should be written for other properties. However this may not be not possible for all; what about purity it needs to be expressed in terms of all evaluations producing the same publications given the same input.
</p>
<h2 id="section-ExpressionProperties-Decidability">Decidability<a class="hashlink" href="#section-ExpressionProperties-Decidability">#</a></h2>
Some of there properties are decidable based on axioms about sites. However most are not. For the undecidable properties it would still be possible to create a conservative estimate that will detect many useful cases of the property.
<ul><li><b>Side-effect free</b> is decided by: <div><pre class="orc-snippet">sideEffectFree (f | g) = sideEffectFree f && sideEffectFree g
sideEffectFree (f >x> g) = sideEffectFree f && (if not silent f then sideEffectFree g else true)
sideEffectFree (f <x< g) = sideEffectFree f && sideEffectFree g
sideEffectFree (f ; g) = sideEffectFree f && (if not talkative f then sideEffectFree g else true)</pre></div> (this has not been proved correct)
</li></ul><p>This section should be completed with deciders and estimates for other properties.
</p>
<h2 id="section-ExpressionProperties-RelatedPages">Related Pages<a class="hashlink" href="#section-ExpressionProperties-RelatedPages">#</a></h2>
<ul><li><a class="wikipage" href="/wiki/Wiki.jsp?page=Deparallelization">Deparallelization</a>: Has some interesting properties and identities that may be useful.
</li><li><a class="wikipage" href="/wiki/Wiki.jsp?page=Identities">Identities</a>: A list of algebraic identities some of which depend on these properties.
</li></ul>Thu, 27 Sep 2012 23:22:45 GMT