Who needs typeclasses? Or static type system even? Why have side-effects
to be so complicated? And what are monads?
There must be something better!
dg is Python with Haskell syntax. In a short talk (15 minutes) I want
to introduce, on a funny note, the "better Haskell".
Under the slogan "what we don't have, you won't need" we will be looking at
features of the Haskell language and their counterparts in dg. To conclude,
we will take a look at how intelligent a Python program can look, if it has
the proper syntax.
Through the work with dogelang I am currently looking at pureness
of python functions and on how to decide and annotate pureness so that I,
in theory, could write a static checker that checks whether the annotated
functions are pure.
We can take the definition of pureness from the wikipedia
and it is as follows
The function always evaluates the same result value given the same argument
value(s). The function result value cannot depend on any hidden information
or state that may change while program execution proceeds or between
different executions of the program, nor can it depend on any external
input from I/O devices.
Evaluation of the result does not cause any semantically observable side
effect or output, such as mutation of mutable objects or output to I/O
devices.
Python makes few restrictions on side-effects and mutability and since we even
can override basic operators (like the dot-operator for attribute access), it
is hard to infer anything remotely useful or non-trivial from a python-program.
I have been, for example, responsible for code like that (paracoded for your
convenience):
defcls(object):def__init__(self):self.d={}def__getattr__(self,attr)ifnotattrinself.d:self.d[attr]=someobj(attr)returnself.d[attr]A=cls()A.foo# this line has side effects
This violates the basic principle of python that an expression should either
have a return value or a side-effect but not both. But we might have done this
for good reason. In this case, the academic value of the "front-end" of the
library outweighs the atrocities of the implementation. But it serves as a fine
example that, it is hard to reason about even simple looking expressions, if they
include the dot-operator (or any other operator for that matter), especially if
you don't have the full class definition at hand.
But it isn't only user-made classes that don't hold true to that principle. Most
low-level functions that interact with the operating system do that in some way.
They have their side-effect within the realms of the rest of the system and still
they have a return value that represents some aspect of the operation within our
program.
os.write(fd, str)
Write the bytestring in str to file descriptor fd. Return the number of
bytes actually written.
open(file, ...)
Open file and return a corresponding file object. If the file cannot be
opened, an OSError is raised.
So we would want to mark any function as impure that has a reference to one of
these impure functions. But we would also want to mark any functions defined
within these impure functions to be themselves impure. Looking at the following
code it would be hard to infere whether a function has a reference to, let's
say 'open'.
o,f=open,"file.tmp"deffun():o(f)
Given Rice's theorem, I'd think that properly tracking references would either
be undecidable or at least a problem of exponential growth (tracking all possible
assignments to some reference). So to be on the safe side, we state the following
as our impurity rule number 1: A function is impure if it uses a reference
from an impure function or has a reference to an impure function. We would also
want an exhaustive list of builtin impure functions, applying the rules recursively.
In the former code example the surrounding block leaks (that's what we will call
it) the reference to both o and f into the namespace of fun. This would
not be a problem. We even want this behaviour. Let's look at this example:
This is contrary to our definition of purity, that the function, given the same
arguments should evaluate to the same value. So this only happened, because the
reference was updated. Let's add impurity rule number 2: A function is impure
if a name is assigned twice and a reference to that name is leaked. This should
cover all cases since shenanigans like the following cause a NameError.
defa():yield(lambda:x*x)x=3yieldNonex,i=5,a()g=next(i)print(g())# Name Error: free variable 'x' referenced before assignment in enclosing scopenext(i)print(g())
Here we see the yield-keyword we have the case of suspended computation. The
next-function is of course part of the set of impure builtin functions because
it returns a value and advances the internal state of the generator. Since
for rule 2 we introduced the leaked name, we can still allow multiple assignments
within a function if the name is not leaked because we want to allow, for example,
the generator-function infinity to be pure.
definfinity():i=0whileTrue:yieldii=i+1
Here, I find, we arrive at an impasse. Every iteration over a generator "uses
the generator up". We could say that we won't allow references to generator-objects
but that seems arbitrarily strict. Also, we can't really know which name could
be used by a generator-object which would lead to not allowing any bare names
(only function calls). Disallowing generators seems impossible since map
and filter and other functional primitives depend on it.
I would welcome any ideas for a rule that would solve this issue of leaking
the internal state of a generator.
I think by now everybody has read that Babai et al will hold a seminar next
week where they want to "outline an algorithm that solves the Graph Isomorphism
problem [...] in quasipolynomial time".
So they are shooting for a result with the complexity \(2^{O(log(n))^c}\)
while the best former result (by Luks, 1983) for Graph Isomorphism was
\(2^{O(\sqrt{n*log(n)})}\).
What is Graph Isomorphism? Given two graphs, the question is, whether there
is a mapping function \(f\) between the nodes of one graph \(G_1\) to
the nodes of the other graph \(G_2\) so that every edge \((a,b) \in G_1\)
is also an edge \((f(a),f(b)) \in G_2\).
So why is this quasipolynomial when \(2^x\) is obviously not a polynome?
That's where the quasi comes from. If the \(c\) in \(2^{O(log(n))^c}\) is
\(1\) then this simplifies to \(2^{O(log(n))}\) which is a polynomial.
Remember that the base of both the logarithm and the exponentiation isn't actually
\(2\) so this doesn't simplify to \(O(n)\) but some other polynomial
(but a polynomial nevertheless). And the \(c\) is just a factor in the
formula (like the base the logarithm and the exponentiation) that have no impact
on the complexity properties (the general shape of the formula describing the
complexity) but can be changed by optimization (opposite to groundbreaking
research). So given proper optimization the algorithm we will be presented
could be (theoretically) as fast as a polynomial algorithm.
When we talk about
"fast" we talk about how the runtime changes (relatively) when the problem size
grows larger. A "faster" algorithm has smaller relative growth while it might
still be orders of magnitude slower in actual runtime for any practically sized
input.
Is this result surprising? Well, yes and no. On the one hand the "witness"
(or positive solution to the problem) is only of linear size
(one mapping for every node in the graph) and the algorithm for checking would
be basically quadratic in complexity (checking the definition given above for all
edges and there are only quadratically many). This holds for problems in NP-complete
but also for problems in P. I think it is obvious that this answer would
not be very hard to find (we surely don't need to check every possible mapping
- this would basically be the case for NP-complete) but it isn't obvious that the
answer is easy to find either (like for a problem in P).
So what we're probably going to see is a clever application of some result of group
theory that is applicable here and excludes a large number of all possible
isomorphism as possible solutions. So the problem is still not easy but math
can help a lot.
What does it mean? It is not known whether Graph Isomorphism is NP-Complete.
This result would be a strong hint, that it isn't (albeit no proof). Even if
we found Graph Isomorphism to be in P, this would have no larger impact
on the field of complexity theory in general.
What's the next thing? That would be finding an algorithm properly in P.
If such an algorithm exists, we would also find a way to compute a small "witness"
(or in this case "proof trail") that is an easily checkable answer to the question
"is there no such isomorphism?". How this proof trail would look is even less obvious.
There could be some function that, given a graph as input calculates a value
and all graphs that have an isomorphism between them have the same value (which
would also need to not be exponential in size). In practice it is very difficult
to even find hard instances of Graph Isomorphisms. So it might turn out that there
are actually only easy cases, we just don't know it yet.
If you haven't read about dogelang, you really
should. It is python with haskell-syntax where you can use all python modules.
So basically coffee-script but for a language that is already useful. And
python bytecode is emitted instead of first compiling to python itself, but
that just as a side-node.
On my behest, the developer of dg
added pattern matching so that in an
if-condition a tuple-unpacking-expression does not raise an exception if
the unpacking fails but returns false.
Therefore one can now implement their own zip and list-constructor in the
following manner: