Other articles

  1. OAuth in GNOME Shell Extensions

    As you might know, I am the maintainer of the GNOME Twitchlive shell extensions. The Twitchlive panel allows you to see whether your favourite Twitch streamers are online or not.

    A few months ago, Twitch started to require OAuth authentication for its endpoints and things started to go sideways. Now there are two ways to communicate with Twitch's API:

    1. Authenticate your requests with a pre-shared application secret.
    2. Obtain a client secret through user authentication and use this secret.

    The first variant is only possible for server-to-server applications, as you're not allowed to distribute the application secret to users. So the second variant it is and we need to authenticate the user.

    In the OAuth process you open a webpage (of the oauth provider) with a callback url. That webpage contains a login form and if you enter valid credentials, the webpage will redirect you to your given callback url, passing as additional information the authorization token you can use to make a valid API call.

    To receive the token you need a webserver that you can redirect to. Even though GNOME's supposed to have a generic OAuth implementation it uses for its online services but it's not generic at all and you can't hook into that. You also can't create a webserver otherwise from within the GNOME Shell. Until a few weeks ago:

    I've implemented a small mechanism by starting a python-based webserver through the extension that has just enough capabilities to receive the OAuth token and write it to a file. As far as I know, that's a world first. If you base OAuth of you extension on this work, give me a shout on twitter.

    And now to the code which I think I boiled down right to the essentials (you'll also find it on github):

    We need to open a browser with the callback within the extension:

    function trigger_oauth() {
      const url = "https://id.twitch.tv/oauth2/authorize?response_type=token&client_id=" + client_id + "&redirect_uri=http://localhost:8877&scope=";
      GLib.spawn_command_line_async("xdg-open " + url);
      GLib.spawn_sync(null, ["python3", oauth_receiver,  oauth_token_path], null, GLib.SpawnFlags.SEARCH_PATH, null);
    }
    

    And the python3 reciver code:

    from http.server import *;
    from urllib.parse import *;
    import sys;
    import os.path;
    
    page = """<html>
    <head><title>Twitchlive GNOME Shell extension OAuth</title></head>
    <body><script>var tokens=document.location.hash.substring(1);
    document.write("<a href=\\"/tokens?" + tokens + "\\"> To finish OAuth-Process click here</a>");
    </script></body>
    """
    
    class handler(BaseHTTPRequestHandler):
      def log_requests(self):
          pass
    
      def do_GET(self):
          print(self.path)
          if self.path == '/':
              # initial call from twitch
              self.send_response(200)
              self.send_header("Content-Type", "text/html")
              self.end_headers()
    
              self.wfile.write(page.encode())
          elif self.path.startswith('/tokens'):
              # our own call
              code = parse_qs(urlparse(self.path).query)['access_token'][0]
              open(sys.argv[1], 'w').write(code)
    
              self.send_response(200)
              self.send_header("Content-Type", "text/plain")
              self.end_headers()
    
              self.wfile.write(b"Thank You. You can close this page.")
              sys.exit(0)
    

    Note that the OAuth-Token is passed as the url fragment that doesn't show up in the actual query so you really need a browser to read that value.

    And for now ... it works.


  2. Podcast Time Machine

    Recently one of my favourite podcasts ended after seven years. I have only been listening to this podcast for two years though. There is five year backlog for me to listen to. But there are many other podcasts I want to listen to and I do like the anticipation of waiting for a new episode.

    So I built the Podcast Time Machine (github) where you can enter a podcast url and a delay and you will get a new link where every podcast episode is delayed by that many days and all episodes that would lie in the future are filtered out. So stuff happpening a week in podcast time are happpening in a week of real time.

    I am looking forward to my first episode of harmontown, when it comes out after a seven-year delay. Feel free to subscribe to your own delayed podcasts. I do not keep access logs so listen to your favorite stuff again (and again).


  3. I bought a Cluster Hat

    I recently bought and installed a Cluster Hat.

    Cluster Hat

    Looks interesting

    I don't know what I will do with it. All my plans I had before hinged on Haskell supporting ARMv6, which it doesn't. Let's see what happens in the future. I am currently looking into installing Docker on it and maybe host some service through my VPS from home.


  4. Tuple Types, Notation, and Codings

    I wanted to write a bit about notation as I have seen students and programmers stumble quite a bit about this. What is "this"? When to write parentheses and commas in tuples and what does it mean.


    Tuple Notation

    Consider the set \(S = \{a, b\}\). Now lets take the cross product of itself. \(S \times S = \{(a,a), (a,b), (b,a), (b,b)\} = S^2\). By the same logic \(S^3 = \{(a, a,a), (a, a,b), (a, b,a), (a,b,b), (b,a,a), (b,a,b), (b,b,a), (b,b,b)\}\). This is somewhat strange since \(S^3 = S^2 \times S = S \times S^2\) meaning that these two should also be the same as \(S^3\):

    \(\{(a, (a,a)), (a, (a,b)), (a, (b,a)), (a,(b,b)), (b,(a,a)), (b,(a,b)), (b,(b,a)), (b,(b,b))\} = \\ \{((a, a),a), ((a, a),b), ((a, b),a), ((a,b),b), ((b,a),a), ((b,a),b), ((b,b),a), ((b,b),b)\}\)

    Let's step back a bit and look at the identity, meaning \(S^1\). We know that the power one is the identity but following the same logic as before we have the following: \(S = \{a, b\} = S^1 = \{(a), (b)\}\). The parantheses do not matter and we are supposed to think of them as just as sequence of values. Let's take a look at the empty sequence: \(S^0 = \{()\}\). Note that this is not the empty set but it is the neutral element for the cartesian product: \(\{()\} \times \{a, b\} = \{((), a), ((), b)\} = \{a, b\}\).

    What is going on here? The cartesian product is, as is the normal product, an extension of some kind of addition. In our case addition is concatenation of sequences and every value is a sequence of one element (singleton sequence). This is different to the singleton set which is distinct from the value it contains. \(\{a, b\} \times \{c, d\} = \begin{Bmatrix}a \circ c \ & a \circ d\\b \circ c & b \circ d\end{Bmatrix}\) looks very much like the cross product for vectors and of course, the empty sequence is the neutral element (or identity) of that operation.

    So actually we are supposed to take nested tuples as sequences of values that - in our mind - should be flattened. This also means, there is no one-tuple (it is the same as the value) and there ist just one zero-tuple.

    By the way: this notation fits nicely as it just maps the cardinality of the sets. So if you just take \(S=2\) you see that all the formulas just magically work out.

    Why do we even use this tuple notation? This has to do with something we call coding.

    Coding

    I will define code the following way: A set is a code if no two different sequences of elements of that look the same when written down consecutively (this is a layman's definition that shall suffice here). Take the set \(B = \{11, 100, 00, 001\}\). Both these sequences look the same when written consecutively: \((001,100)=(00,11,00)=001100\). Whether a set is a code is a special instance of the post correspondence problem. I leave it to the reader to define the mapping.

    If the carrier set is a code, we do not need to use the tuple syntax. For the following reasons a set might trivially be a code: All symbols have the same length. There are no overlaps (no non-empty prefix of one symbol is a suffix of another) between the symbols.

    So for the first set \(S\) we do not need to use the tuple notation as it is always quite clear what is meant: \(S^2 = \{aa,ab,ba,bb\}\). Using this notation we now need a new symbol for the empty sequence and we usually use \(\varepsilon\) (epsilon). Note that concatenation follows these axioms: \(a\circ\varepsilon = \varepsilon\circ a = a\) (neutral element) and \((ab)c=a(bc)\) (associativity). The concatenation operation forms a monoid under the carrier set (a semigroup with identity).

    Tuple Types in Programming

    Where does this confusion stem from? I think large part of it is that most programming languages do not properly support tuples in their type system in the way we want to use them in computer science theory. Programming langues do have tuple types but they are more rigid than what we want to use.

    Let us look at python first:

    # Python does have a native tuple type
    >>> (3, 6)
    (3, 6)
    # We have an empty unit sequence
    >>> ()
    ()
    # Using the correct syntax we can nest this arbitrarily deep
    >>> (((((),),),),)
    (((((),),),),)
    # We can construct one-tuples which are distinct from their value
    >>> (3,) == 3
    False
    # The standard library has a sequence-product operation
    >>> from itertools import product
    # the cartesian product with itself works as we expect
    >>> list(product([1,2,3], repeat=2))
    [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
    # Having a zero-product returns the sequence that contains unit, which we expect
    >>> list(product([1,2,3], repeat=0))
    [()]
    # Somewhat consistently, one-product returns the sequence of one-tuples but as seen above, this is not eqal to the original sequence
    >>> list(product([1,2,3], repeat=1))
    [(1,), (2,), (3,)]
    # Also we do not have associativity
    >>> list(product([1,2],product([3,4],[5,6])))
    [(1, (3, 5)), (1, (3, 6)), (1, (4, 5)), (1, (4, 6)), (2, (3, 5)), (2, (3, 6)), (2, (4, 5)), (2, (4, 6))]
    >>> list(product(product([1,2],[3,4]),[5,6]))
    [((1, 3), 5), ((1, 3), 6), ((1, 4), 5), ((1, 4), 6), ((2, 3), 5), ((2, 3), 6), ((2, 4), 5), ((2, 4), 6)]
    

    I also want to take a look at Haskell which is also interesting.

    -- Haskell has native tuple types
    > :t (3,5)
    (3,5) :: (Num a, Num b) => (a, b)
    -- But there is no singleton tuple type
    > :t (5)
    (5) :: Num p => p
    > (5) == 5
    True
    -- We have the unit type that is inhabited with the single instance unit which we also can not nest
    > :t ()
    () :: ()
    > :t ((((()))))
    ((((())))) :: ()
    -- Checking for associativity is a type error as both nestings are distinct types and can not be compared via equals
    Prelude> (1,(2,3)) == ((1,2),3)
    <interactive>:6:2: error:
    Prelude> :t (1,(2,3))
    (1,(2,3)) :: (Num a1, Num a2, Num b) => (a1, (a2, b))
    Prelude> :t ((1,2),3)
    ((1,2),3) :: (Num a, Num b1, Num b2) => ((a, b1), b2)
    

    The type system does not allow us to even construct a type-safe product function as it is in python as the tuple size of the result sequence is dependent on the value of the argument (something like a -> Int:Val -> (a,)*Val). This would need dependent types. There is a generic function for the cartesian product with the type [a] -> [b] -> [(a, b)] which, as we have seen from the interactive session, would not obey the associativity law either.

    Conclusion and Context

    We have seen that the tuple notation is just that: notation. It is not used for structure, only for disambiguity. If you want structure, you need to use uninterpreted functions \(t(1,t(2,3)) \neq t(t(1,2),3)\) that are not flattened. But programming languages and the type systems do see a structural difference in the tuple types. The 3-product in Haskell could have, depending on the implementation, three different types: [a] -> [b] -> [c] -> [(a,(b,c))] or [a] -> [b] -> [c] -> [((a,b),c)] or [a] -> [b] -> [c] -> [(a,b,c)] where we would expect all types to be the same.

    Why did this article come to pass? Two reasons. During the database lectures we wanted to write up some database state (a set of rows for each table, a row being a sequence of column values) and while one table had three columns (\(\{(1,2,3),(4,5,6)\}\)) one table only had one column and for symmetry \(\{(1),(2),(3)\}\) was brought to paper which I remarked to be at least confusing for students as it might convey something not meant (there being a difference between the singleton tuple and the value).

    The second example comes from computer science didactics, a module for the aspiring teachers. In a homework where some lesson had to be designed, one student had the topic of languages and grammars. In an example of a regular language they took this as an example alphabet: \(A=\{la,li,lu\}\). This is fine as the symbol of the alphabet are just syntax and are only of interest (as I've written above), in terms of whether the alphabet is a code or not and therefore which notation is used for concatenation operations. Now on a worksheet the following question was asked: \(lul \in A^*\). And this, I would claim, is a type error. The kleene closure of the alphabet only contains sequences of symbols from the alphabet (including the empty sequence) but "lul" is no sequence of symbols from the alphabet so it can not be of the same type (sequence from the alphabet) as the set (set of sequences from the alphabet). As the original alphabet was a code, all sequence can be written consecutively but it is unclear how "lul" can be deconstructed into elements of the alphabet. A possibiliy is, that the original alphabet was \(\{l,a,i,u\}\) and \(A\) was just a language over that alphabet but that was not written. For teachers, I believe, formalisms in that area are quite important.


Page 1 / 8 »

links

social

Theme based on notmyidea