Forwarded from empty spaces
John Glover (1767-1849) : A view of the artist's house and garden, in Mills Plains, Van Diemen's Land (1835)
Forwarded from empty spaces
Paul Oscar Droege (German, 1898-1982)
"Birches in Storm," ca.1930
Color woodcut
35.6 x 23.5 cm
"Birches in Storm," ca.1930
Color woodcut
35.6 x 23.5 cm
#website #wiki
Handwiki
from "about" section :
"HandWiki is the world's largest wiki-style encyclopedia dedicated to science, technology, computing and general knowledge."
Handwiki
from "about" section :
"HandWiki is the world's largest wiki-style encyclopedia dedicated to science, technology, computing and general knowledge."
handwiki.org
Wiki Encyclopedia of Knowledge
#discussion
How can we compare expressive power between two Turing-complete languages?
tl;dr :
Q: Is this possible?
Is there an accepted (and unambiguous) notion of "expressive power" that could differ between two different Turing-complete languages?
A: Yes, this is possible
a bit less tl;dr (tried to copypaste essentials only):
The concept we need is called observational equivalence.
. . .
The key idea is this: Consider taking a Turing-complete language L and adding feature X. Now think about how we could translate code written in L+X back into into L. If feature X makes the language "more expressive," then this transformation will require you to apply a large-scale, "global" transformation. On the other hand, if language L and L+X are "equally expressive," then L+X can be transformed into L using only a "local" transformation.
. . .
This distinction between "feature only requiring local transformation" and "feature requiring global transformation" is what we want to formalize.
We can get closer to a formal statement by saying: a feature does not "add expressive power" if we can implement it as a macro that turns it into something in the original language. Even if the language doesn't have macros, you could imagine using some kind of preprocessor to implement a local transformation as a kind of macro.
This is not quite a formal description yet, but we're getting there! For one thing, how do we prove that a macro cannot exist for some feature? To do this, we still need a formal description of the problem.
. . .
First, we need a way to compare programs for equality.
"given two things in our language x and y, is there any way to write a program in our language that behaves differently if you used x vs if you used y?"
Formalizing all this is where we get observational equivalence.
But first, we need to talk about what happens when you take a program and cut a hole out of it.
Imagine you take a valid program in your language and print it out. Then you physically cut out exactly one subterm and throw it away. What you have left is a "program with a hole in it," or a printout of a "one-hole context" (sometimes just called "a context").
. . .
If we call our context C and the new term we're taping into it t then the complete program we obtain when we tape t into C is called C[t].
Our definition of observational equivalence will center around these contexts (that is, programs with exactly one hole in them).
. . .
>Observational equivalence
Two expressions e1 and e2 are called "observationally equivalent" if, for every context C, we have: C[e1] halts if and only if C[e2] halts
This might seem a bit weird. Think about this for a minute. Does this seem, somehow, wrong?
Take a moment to consider this question: "Are we saying that 1 and 2 are 'observationally equivalent'? Both 1 and 2 very straightforwardly terminate!"
I am not saying they are observationally equivalent! An example: Can you write a Python program with one hole in it that will halt if the hole is filled with 1 but will loop forever if it is filled with 2 (you could just write <hole> for the hole and fill it in as appropriate)?
If so, you've proven that 1 and 2 are observationally distinct in Python!
To show that they are distinct, all you have to do is find one context C where C[1] halts but C[2] does not (or visa-versa). If they were the same then every context would behave the same (with regard to halting) regardless of whether you plugged in 1 or 2.
What if we only have a isZero(x) builtin function, but no builtin equality operation? Can we still tell 1 apart from 2? Well, how about the context while (isZero(1 - <hole>)) { }? This is why the definition works well: we need to consider all possible contexts!
How can we compare expressive power between two Turing-complete languages?
tl;dr :
Q: Is this possible?
Is there an accepted (and unambiguous) notion of "expressive power" that could differ between two different Turing-complete languages?
A: Yes, this is possible
a bit less tl;dr (tried to copypaste essentials only):
The concept we need is called observational equivalence.
. . .
The key idea is this: Consider taking a Turing-complete language L and adding feature X. Now think about how we could translate code written in L+X back into into L. If feature X makes the language "more expressive," then this transformation will require you to apply a large-scale, "global" transformation. On the other hand, if language L and L+X are "equally expressive," then L+X can be transformed into L using only a "local" transformation.
. . .
This distinction between "feature only requiring local transformation" and "feature requiring global transformation" is what we want to formalize.
We can get closer to a formal statement by saying: a feature does not "add expressive power" if we can implement it as a macro that turns it into something in the original language. Even if the language doesn't have macros, you could imagine using some kind of preprocessor to implement a local transformation as a kind of macro.
This is not quite a formal description yet, but we're getting there! For one thing, how do we prove that a macro cannot exist for some feature? To do this, we still need a formal description of the problem.
. . .
First, we need a way to compare programs for equality.
"given two things in our language x and y, is there any way to write a program in our language that behaves differently if you used x vs if you used y?"
Formalizing all this is where we get observational equivalence.
But first, we need to talk about what happens when you take a program and cut a hole out of it.
Imagine you take a valid program in your language and print it out. Then you physically cut out exactly one subterm and throw it away. What you have left is a "program with a hole in it," or a printout of a "one-hole context" (sometimes just called "a context").
. . .
If we call our context C and the new term we're taping into it t then the complete program we obtain when we tape t into C is called C[t].
Our definition of observational equivalence will center around these contexts (that is, programs with exactly one hole in them).
. . .
>Observational equivalence
Two expressions e1 and e2 are called "observationally equivalent" if, for every context C, we have: C[e1] halts if and only if C[e2] halts
This might seem a bit weird. Think about this for a minute. Does this seem, somehow, wrong?
Take a moment to consider this question: "Are we saying that 1 and 2 are 'observationally equivalent'? Both 1 and 2 very straightforwardly terminate!"
I am not saying they are observationally equivalent! An example: Can you write a Python program with one hole in it that will halt if the hole is filled with 1 but will loop forever if it is filled with 2 (you could just write <hole> for the hole and fill it in as appropriate)?
If so, you've proven that 1 and 2 are observationally distinct in Python!
To show that they are distinct, all you have to do is find one context C where C[1] halts but C[2] does not (or visa-versa). If they were the same then every context would behave the same (with regard to halting) regardless of whether you plugged in 1 or 2.
What if we only have a isZero(x) builtin function, but no builtin equality operation? Can we still tell 1 apart from 2? Well, how about the context while (isZero(1 - <hole>)) { }? This is why the definition works well: we need to consider all possible contexts!
Okay, but what if there is actually no way to tell 1 and 2 apart? Then we would actually say that are observationally equivalent! Observational equivalence captures the idea of what it means for two things to be indistinguishable inside a programming language.
Now how does all of this relate to expressiveness? I'll return to the question: Is it possible to distinguish between 2 * 3 and 3 + 3?
My answer: It depends on the features of the language! It certainly is not possible in the language which only has basic arithmetic, functions and recursion.
Can you think of a feature we could add where it is possible to distinguish them?
Operator overloading! Say we have operator overloading and the ability to redefine existing function. If we overload * to do something weird, like return the first argument but we don't overload +. We can now distinguish between those two expressions!
By adding that feature, we broke an observational equivalence. The expressions 2 * 3 and 3 + 3 used to be observationally equivalent. Then we added operator overloading and now they are observationally distinct.
Now we need to address how to tell if a feature requires a "local" transformation vs "global" transformation :
If feature X can be implemented for language L as a local transformation to obtain the language L+X, then for any two expressions e1 and e2 that are observationally equivalent in L, it is also the case that they are observationally equivalent in L+X
This is saying that if feature X only required a local transformation to implement, then it did not "break" any observational equivalences. All of the observational equivalences from L are still true in L+X.
Note that this was not the case for operator overloading. Adding operator overloading did break some observational equivalences. On the other hand, when we added unary negation we did not break any observational equivalences.
Now we can say that when we add expressiveness to a language, we break some observational equivalences.
Now how does all of this relate to expressiveness? I'll return to the question: Is it possible to distinguish between 2 * 3 and 3 + 3?
My answer: It depends on the features of the language! It certainly is not possible in the language which only has basic arithmetic, functions and recursion.
Can you think of a feature we could add where it is possible to distinguish them?
Operator overloading! Say we have operator overloading and the ability to redefine existing function. If we overload * to do something weird, like return the first argument but we don't overload +. We can now distinguish between those two expressions!
By adding that feature, we broke an observational equivalence. The expressions 2 * 3 and 3 + 3 used to be observationally equivalent. Then we added operator overloading and now they are observationally distinct.
Now we need to address how to tell if a feature requires a "local" transformation vs "global" transformation :
If feature X can be implemented for language L as a local transformation to obtain the language L+X, then for any two expressions e1 and e2 that are observationally equivalent in L, it is also the case that they are observationally equivalent in L+X
This is saying that if feature X only required a local transformation to implement, then it did not "break" any observational equivalences. All of the observational equivalences from L are still true in L+X.
Note that this was not the case for operator overloading. Adding operator overloading did break some observational equivalences. On the other hand, when we added unary negation we did not break any observational equivalences.
Now we can say that when we add expressiveness to a language, we break some observational equivalences.