The theory of the problem with threads

The problem with threads has been very concisely explained in the famous paper[pdf link] of Edward A. Lee. Very simply put, the author argues that threads are a problem because they add non-determinism to an application, and that the programmer has to put in extra effort to control the non-determinism, while this should be the other way around. Quoting the author, Threads, as a model of computation, are wildly nondeterministic, and the job of the programmer
becomes one of pruning that nondeterminism. (..) I argue that this is approaching the problem backwards. Rather than pruning nondeterminism, we should build from essentially deterministic, composable components. Nondeterminism should be explicitly and judiciously introduced where needed, rather than removed where not needed

The author goes on to suggest few ways to allievate the problem

  1. Better software engineering process
  2. Use vetted design patterns for concurrent computation
  3. Using patterns which can be encapsulated into language libraries (for example, MapReduce)
  4. Extend the existing programming language with annotations to indicate concurrent compuations
  5. Using promises / futures as implemented in the E language (work on proxies of shared data instead of the actual)
  6. Using tools to determine if the existing code is indeed thread safe or not

The author then goes on to suggest an alternative to threads, as a system modeled closely like CSPs. In this model, the various components of the system are deterministic. The rendezvous director is the one which controls the nondeterministic part of the system. In such a system, the component is deterministic, but the merge is the one which is nondeterministic. In such a case, the merge block is where one can concentrate on to ensure that any rollbacks be transmitted back to the components. The discussion at LtU, has some interesting points (some of which are OHT for me right now).

This post of course is not deal with the problem of threads in detail. Rather, I want to concentrate on how the author presents a model of threads as a computation, and how one can clearly see the problem of nondeterminism creep. This makes is very difficult to reason about systems which are heavily threaded. As I am not aware of how to integrate the LaTEX plugin, I shall try to write the equations as closely to the document.

Let N={0,1,2…} be the set of natural numbers

B={0,1} the set of binary bits

B* is the infinite set of all finite sequences of bits

Bw =(N->B) i.e. it is the infinite set of infinite sequences of bits which give an output. An output of zero or one. Consider the Bw as that set of those bits which have some output (codomain in {0,1})

B** = B* U Bw i.e. B** is the set of all finite sequences of bits and those infinite sequences which have a finite ouput i.e. the finite sequences could either give an output or needn’t give any. This is the computing machine, which can potentially infinite inputs and potentially infinite outputs (remember it is the union between B* which is an infinite set).

Q is a partial function of values between B** and B** i.e. there can be values in B**’s domain which don’t map back to values in B** (that is what a partial function is). Simply put, this means that there are sequences (finite / infinite) which don’t have a solution in B**.

An imperative machine (A, c) is a finite set of actions and control functions. The set A is the set of actions are generally the instructions that are executed in a computation.

A program of length m is represented as p : N->A – a function between the number and set of actions. A way to say that for every N there is one program (actions) of length N. In simple words, a program of length m.

Now, that a program has been defined of length m, it is time to consider the state of the program as it executes (via a thread). bn+1 = p(c(bn))(bn), for bn being the state in B**. Here,

  • c(bn) gives the nth number to execute
  • p(c(bn)) the nth instruction to execute
  • p(c(bn))(bn) – result of this execution (apply the nth instruction determined by c(bn), to the bnth data to get the output of the execution)

Now, the author explains the actual problem with threads. For a sequential process b(n+1) is always defined for a given n. The output is always deterministic. But, if there are (say) two threads running concurrently accessing this data, then the equation becomes: bn+1 = pi(c(bn))(bn) for i in {1, 2}. (please read the pi as p subscript i). In this case, given the value of i, the next state is determined by either p1(c(bn))(bn) or p2(c(bn))(bn). So, even though, the next instruction as returned by the control function is known, the next state is nondeterministic because of the value of i that is picked up at that instance of time. And of course, if there are two CPUs (or cores) whose time slice is given to both of these threads, then the data access problems become compounded.

I hope I was able to explain the theory (I do know that it is not possible to explain theory withouth the right mathematical symbols, I shall fix that soon, once I get my head around either MathML or using LaTEX in HTML) as to why there is a problem with threads. The last equation of the program presentation is the crux of the complete problem. The bn+1 i.e the next stage is very clearly defined in the case of a sequential program, whereas in the concurrent program with threads, it is not defined. This essentially is the crux of the problem.

The author at the end of the paper tries to model the concurrent computation thus:

f: (T->B**) -> (T->B**). Here T is an ordered set of tags. The order of these tags can be determined by various factors like time, causality etc. In simple terms, based on some order within a set of tags, the next instruction to execute is picked, and that tries to find an output from a similar set of outputs – nondeterminism in its fullest.

Please let me know if I have made any factual errors in trying to explain the theory of the problem with threads. The idea behind the post was to make it easy for people to understand what those (sometimes scary) formal symbols actually meant.

Behind Deep Blue – an average read

Feng Hsiung Hsu’s book, Behind Deep Blue is the chronology of events that finally resulted in IBM’s Big Blue computer defeating Gary Kasparov. The text under the title (hmm, is sub-title the word for this ? or is there a better word ?) goes something like building the computer that defeated the world chess champion. If one were to not read anything more from this, then the book does justice. But, if you are expecting more details into the guts of it, then you might be disappointed. I give this book a 5 out of 10, and suggest you to borrow it if you can.

So, what is good with the book. The nice things about the book are when the author describes the design hurdles. Any large, parallel system throws up its own set of design hurdles. The author explains, sometimes technically (good if you are the technical sort), how they went about designing the system. How certain parts were set for the hardware and some for the software. There are also interesting notes about the various chess strategies, though he does not dwelve deep into it.

What is not so good about the book. Well, the book is more of a biography of the IBM Big Blue. Parts about its genesis, its design and then the calm after the storm. There are lots of personal details, including the author’s collaboration with people in CMU and then in IBM. These details, interspersed between the technical sections of the book, can sometimes catipulate the reader’s interest. I thought, lesser content regarding this, and more regarding the system itself would have made the book a lot more interesting.

This book made me wonder, where does one draw the line when trying to explain a system. Building a large parallel system is a challenge, and most people can’t fathom the challenges faced in designing something as large as the Big Blue. So, if one were to explain to a layman, there are lots of parts – the interesting ones, which might need to be skipped. It is an interesting thought, and I shall try to write about this some other time.

What is constraint propagation

Constraint satisfaction problem (CSP) is a problem composed of a set of variables, each with a domain of values, where we have a set of constraints that restrict combinations of variable assignments. We are then to assign values to variables, satisfying those constraints (or show that no assignment exists).

An essential part of constraint programming is constraint propagation. Constraint propagation, put simply, is a way for a system to spontaneously produce the consequences of a decision.What this means is that, propagation sets the values of certain variables based on the values that other variables hold. So, if some variables hold some values, by propagation, we can set the values to the other variables based on the constraints. This automatic inference of the values for the second set of variables is called constraint propagation. Constraint propagation provides a natural way for a system to spontaneously produce the consequences of a decision.

One of the ways for constraint propagation is arc consistency. It can be explained via an example. Consider thus: X = {23…45} and Y = {35…76}
And the constraint is: X > Y
Using arc-consistency which says variable x (belonging to set X) is consistent with y (belonging to set Y), if, for each value a in the domain of X there exists a value b in the domain of Y such that (a,b) satisfies the constraint between X and Y.
So, using arc-consistency, for the constraint X > Y, we can reduce the set X to {36…45} because X should always be greater than Y. Applying arc-consistency on Y, for the reduced set X, Y reduces to {35…44}. Now, this is not the solution for the constraint satisfaction problem (CSP). Just because we have non-empty sets after reduction, doesn’t give the actual solution. Also, the exact tuples (as there are only two variables in the constraint), are the ones that constitute the solution, and not the reduced domains of the variables. To get the solution, we need to drop to the search part of the solution.

For each variable x belonging to X’ and y belonging to Y’ we need to evaluate the constraint validity. Only after we get the resultant set can we be guaranteed that we have a solution. In this case, the solution will be:
(36,35) (37,35), (37,36)……

As this link puts it, constraint propagation is an *inference* rule for finite domain problems that narrows the domains of variables.

I didn’t know how to include mathematical symbols in wordpress (may be using MathML), so have expanded the text corresponding to the generally mathematical symbols.

Visibroker idl2java and vbjc error

visibroker, idl2java, vbjc error, solution

If you are using Visibroker, and idl2java fails with this error: : unrecoverable error launching tool; aborting, then this has to do with the PATH and CLASSPATH variable setting on your machine. Also, from the BDP help page, the right way of launching Java-written CORBA servers and clients is using the vbj and vbjc files. These files are executables on Windows, but on other operating systems (*nixes), these two files are shell scripts which set the Java’s system properties and the required Class variable names before invoking the JVM. It is not needed to use these files on Windows, if you know what should be the parameters that should be passed. Also, another common error seen when launching the vbjc is vbjc requires JDK 1.1.6 or above installed. This will be seen even if you have the latest SUN’s JDK installed or even if you use BDP’s JDK. It is suggested that you always use Borland’s JDK for reasons only known to Borland.

To fix the above mentioned errors, you can have a batch file (or a shell script) which has settings like this: @ECHO OFF
SET CLASSPATH=E:\BDP\lib\vbdev.jar;E:\BDP\lib\vbjdev.jar;E:\BDP\lib\vbjorb.jar;E:\BDP\jdk\jdk1.4.2\lib\tools.jar;%CLASSPATH%
SET PATH=E:\BDP\jdk\jdk1.4.2\bin;E:\BDP\jdk\jdk1.4.2\jre\bin\;E:\BDP\bin\;%PATH%

The JDK’s bin directory should preced the JRE’s bin directory. I found this by trial and error. Once you set these settings, you should be able to use both idl2java and vbjc.

Coming to the parameters that get passed to (say)a Java client by the vbjc, it looks something like this (again from the BDP’s bank_agent example): java -Djava.endorsed.dirs=E:\BDP\lib\endorsed -Djavax.rmi.CORBA.StubClass=com.inprise.vbroker.rmi.CORBA.StubImpl -Djavax.rmi.CORBA.UtilClass=com.inprise.vbroker.rmi.CORBA.UtilImpl -Djavax.rmi.CORBA.PortableRemoteObjectClass=com.inprise.vbroker.rmi.CORBA.PortableRemoteObjectImpl -Dorg.omg.CORBA.ORBClass=com.inprise.vbroker.orb.ORB -Dorg.omg.CORBA.ORBSingletonClass=com.inprise.vbroker.orb.ORBSingleton -Dvbroker.agent.port=18656 -Dborland.enterprise.licenseDir=E:\BDP\var -Dborland.enterprise.licenseDefaultDir=E:\BDP\license -Dvbroker.orb.procId=3008 -Dapplication.home=E:\BDP -Djava.class.path=E:\BDP\lib\vbdev.jar;E:\BDP\lib\vbjdev.jar;E:\BDP\lib\vbjorb.jar;E:\BDP\jdk\jdk1.4.2\lib\tools.jar;E:\BDP\lib\vbejb.jar;E:\BDP\lib\asrt.jar;E:\BDP\lib\jdsserver.jar;E:\BDP\lib\xmlrt.jar;E:\BDP\lib\vbjorb.jar;E:\BDP\lib;E:\BDP\bin;E:\BDP\lib\lm.jar;E:\BDP\lib\EccpressoAll.jar;E:\BDP\lib\flexlm.jar;E:\BDP\lib\sanct2.jar;E:\BDP\lib\mail.jar;E:\BDP\lib\dom4j.jar;E:\BDP\lib\log4j.jar;E:\BDP\lib\xmlParserAPIs.jar;E:\BDP\lib\xercesImpl.jar;E:\BDP\lib\jsse.jar;E:\BDP\lib\jcert.jar;E:\BDP\lib\jnet.jar;E:\BDP\lib\jaas.jar;E:\BDP\lib\vbsec.jar;E:\BDP\lib\jce1_2_1.jar;E:\BDP\lib\sunjce_provider.jar;E:\BDP\lib\local_policy.jar;E:\BDP\lib\US_export_policy.jar;E:\BDP\lib\tomcat\common\servlet.jar;.;e:\bdp\jdk\jdk1.4.2\lib\tools.jar;.; Client
If you see, the osagent port is passed to the JVM. Another important thing to note is this line:-Dorg.omg.CORBA.ORBClass=com.inprise.vbroker.orb.ORB. This line basically tells the JVM that the ORB class to be used is Visibroker’s ORB and not the default SUN’s ORB that is shipped with the JVM. I have tested this with Visibroker 6.0, but this should work for the higher versions of Visibroker too. If it doesn’t please let me know and I will try to provide the instructions for the higher versions too.

A new way of writing client-side browser code

If lambdas are something that you have used in callbacks in the Javascript code or have used a list of functions in a list as subscribers to an event, then you might benefit from looking at FlapJax. FlapJax can be used to write client side browser code using behaviors. I am not familiar with Aspect programming, so I don’t know if this equates to that, but the idea is very nice. There are behaviors and events that are created as part of the system (the HTML page). Any change in the behavior automatically gets reflected in all the subscribers(for the lack of a better word) of the behavior. Any expression containing a behavior also behaves as another behavior. Not impressed ? Even better, you can write code in JavaScript and FlapJax side-by-side. The FlapJax compiler ensures that the lifting of the JavaScript functions happen automatically. This means that existing JavaScript code can be incrementally changed. What are the potential applications ? Hmm, I can think of a reddit style system wherein the resultant HTML can be continuously updated as the rankings change (this of course will need a server-side persistence layer aka behavior whose changes reflect on the final HTML). Hmm, may be I can suggest this to the good people behind this language.

Continuations and Scheme – Part I

Continuations howto, scheme, continuations explained, understand continuations in scheme

My guess is that anyone coming from the OO or structural world of programming style trying to learn Scheme, will take a while to get his/her mind around continuations and how they can be used in Scheme. I still am trying to get my mind around it. The problem is exacerbated by the thought that I think I know it but can’t point at what I don’t know 🙁 This post is an attempt to brain-dump whatever I know and see if it makes sense; both to me and to anyone reading this post, in the fervent hope to try to understand Continuations and Scheme.

The first place to head to understand continuations is the wikipedia.Another nice place to understand what continuations are seems to be this excellent post on comp.lang.scheme. Look for the post by bear wherein he/she explains continuations as can be understood by a C programmer. The moment one thinks of the stack frames as being on the heap and not on the stack, the possibility of continuations becomes very clear. If each of the stack frames are always available for access at any time during the program’s execution, one can jump to any part of the program. This part of the program that one can jump to can be in the future or can be in the past. The continuation as a concept liberates from the sequential stack based model.

Coming to continuations in Scheme, it took me a while to get a hang of it, and even now, I don’t think I have fully gotten it. May be writing more code that uses continuations might help reduce the haze. Or it could be one of those things, you just get it while writing some code or understanding some code.I found The Scheme Programming Language more helpful in trying to understand continuations in Scheme, than the TY Scheme in fixed num days. Of course, YMMW. Once the idea of continuations is clear, lets dive into how Scheme implements them with the call/cc. Whenever a Scheme S-expression is executed, there is some other S-expression waiting for the result of the previous expression’s result. This S-expression which is waiting for the results, or in other words, the expression that will be executed in the future is the continuation.I am going to use an example similar to the one in the The Scheme Programming Language to derive the usage of call/cc.Take the following example
(define myproc
(lambda (k)
(display k)
(+ 5 ( k 4))))
(define t1
(lambda (x) (+ 12 x)))

Simple example ? I guess so. The myproc takes a procedure, to which it applies 4 and then takes the result and adds it to 5 and returns it to the caller. I have just described the various continuations that are part of the code – the addition of 5 to the result of the procedure result of (k 4) is a continuation. The caller waiting on the result of myproc is also another continuation. As for the invocation of the above code, it can be invoked thus:
> (myproc t1) # 21
The t1 procedure is passed as a parameter to myproc. So first the evaluation of (t1 4) happens and the result is returned, to which 5 is added. So the output of the call is 21 ( (5+ (12+4)). This is fine till now ? Now lets enter the realm of continuations. Now consider the case wherein you wanted to return from the myproc immediately without any processing. Some parameter that was passed to myproc was invalid and you don’t want to perform any operation at all and return some value immediately. How do you achieve that ? Before answering that question, lets look at what happens if we do this (call/cc myproc ). It results in a continuation being displayed and 4 being the result.
What happened here ? The myproc was supposed to take a procedure as a parameter and pass 4 to it as the parameter and then add 5 to it. But when the procedure is called with (call/cc myproc) then the procedure returns a 4. The procedure call/cc packages up the current continuation into a procedure and passes it as the parameter to the function. And the output shows that the parameter k is a continuation. The current continuation is the procedure myproc and it was supposed to do all the calculations and return a value, but we have effectively short-circuited the entire process. In the S-expression (k 4) the current continuation is applied to 4, and as you know the current continuation is the procedure myproc ==> the result of the entire procedure is 4. The remaining expressions are not evaluated (in this example).Any top level expression using the result of the myproc though will be processed. Take a look at this example
(+ 2
(lambda (k)
(* 5 (k 4)))))
In this example, once the continuation returns 4, the top level addition 2 + is executed and the result is 6.

I hope I was able to explain continuations in a very layman’s terms; and also continuations in Scheme. If there are any errors in my explanation please write a comment, and I shall fix it. Also, this is titled Continuations-I because, I assume that I will be writing more about this topic. May be I will try to provide more examples which make it very easy to understand how continuations are used in Scheme.

Yacc/Bison parser states

So, I was trying to teach myself Lex & Yacc. Understanding how it works, is not trivial. The important thing to note is how the look ahead logic in bison works. The look-ahead changes the state of the parser, after looking ahead one token and then deciding whether to change the state or not. This link describes how the look ahead works. For example, if I had a grammar like this:
/*prologue copied as is in the generated file */
statement : NAME '=' expression
| expression {printf("=%d\n",$1);}
expression: expression '+' mulexp { $$ = $1 + $3; }
| expression '-' mulexp { $$ = $1 - $3; }
| mulexp { $$ = $1; }

mulexp: mulexp '*' primary { $$ = $1 * $3; }
| mulexp '/' primary { $$ = $1 / $3; }
| primary { $$ = $1; }

primary: '(' expression ')' { $$ = $2; }
| '-' primary { $$ = -$2; }
| NUMBER { $$ = $1; }
int main()
return yyparse();

The lexer code for the parser above is:

#include ""
extern int yylval;

[0-9]+ {yylval = atoi(yytext); printf("num=%d\n",yylval);return NUMBER;}
[ \t] ; /*ignore whitespaces */
\n {return 0; /* logical EOF */ }
. return yytext[0];

And the makefile for these looks like this:

rm -f cal.exe lex.yy.c cal.output
rm -f *.*~
rm Makefile~

cal.exe : lex.yy.c
gcc -g -o cal.exe lex.yy.c -lfl -ly cal.y
bison -v --report=state -d cal.y
lex.yy.c: cal.l
flex cal.l

Note that the -v and –report flags are used to print the states of the bison parser.
Continue reading “Yacc/Bison parser states”