Turing completeness

sed is a very powerful tool. A simple sed statement may turn a cat into cement. Observe: echo cat | sed statement I was asked by mariom@ircnet whether is it possible to implement the Euklidean algorithm (the one that computes the greatest common divisor) in awk. awk is a Turing complete language, so the answer is yes, it is possible. There is a snippet proposed by mariom:

{
    a = $1;
    b = $2;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    print a
}

Anyway, my response was that it is possible even in sed. Is it? Of course! Sed is a Turing complete language. Though I had no idea how to write it in sed. I use sed for simple substitutions only, but I could not admit that! I started googling for arithmetic operations in sed and I found

a dc implementation in pure sed. So the next question is how to implement the Euklidean algorithm in dc. It turned out to be quite simple, see:

[lalb%sclbsalcsblb0

This code assumes that there are two integers on the stack. So you can test it with something like that:

echo '20 25 [lalb%sclbsalcsblb0

Let’s analyze what is happening there. There is F macro that is equivalent of “while” loop in awk code. It

loads the values of a and b registers on the stack. Then replaces them with their reminder and saves it in the c registers.

lbsalcsb

statement just copies the value of

b to a and c to b. Finaly it compares the value of b with 0. If former is greater it executes F (note: recurrence. It is the only way to implement a loop in dc). Otherwise it quits.

sasblFxlap

statement is an entry point. It saves values from stack in the 

a and b registers, then executes F and prints the content of the a register. So this sed script is an equivalent of awk script that executes Euklidean algothm. Now it is enough to embed the dc script into dc.sed, et voila! Enjoy: Euclidean algorithm implemented in pure sed.

You May Also Like

Spring Security by example: securing methods

This is a part of a simple Spring Security tutorial:

1. Set up and form authentication
2. User in the backend (getting logged user, authentication, testing)
3. Securing web resources
4. Securing methods
5. OpenID (login via gmail)
6. OAuth2 (login via Facebook)
7. Writing on Facebook wall with Spring Social

Securing web resources is all nice and cool, but in a well designed application it's more natural to secure methods (for example on backend facade or even domain objects). While we may get away with role-based authorization in many intranet business applications, nobody will ever handle assigning roles to users in a public, free to use Internet service. We need authorization based on rules described in our domain.

For example: there is a service AlterStory, that allows cooperative writing of stories, where one user is a director (like a movie director), deciding which chapter proposed by other authors should make it to the final story.

The method for accepting chapters, looks like this:

Read more »