Monthly Archives: May 2013

Testing Browser Gamepad API

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

I did not bother to see the Browser Gamepad API specs I just grab the first code on the Internet that works for me and modified it to my needs.
I would like to put here the original code url but I lost it :(. The code was made by Marcin Wichary from google and is license under Apache license.

So I am doing a simple application that is on development phase (BETA) and can be found in my new website Fsvieira Desktop that I am working on. To access the app just click on the gamepad icon. I have to develop some solution so I can pass a direct url to my applications 😀 instead of saying please click on the icon X.

The only browser that I was able to put the application working was with latest Chrome, I tested with Firefox and Chromium and it doesn’t work. Gamepad API is still in discussion so I guess its not very well supported.

If anyone tests this please tell me how it goes. Just comment on this post or if you like send me a email.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

JavaScript lambda-tree generation (or something like that).

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Hi,
In my previous posts I talked about generating an Abstract Syntax Tree (AST) from JavaScript functions using the great lib Esprima and manipulated it to create pure lambda functions. The simple examples that I used were simple logic formulas using only the ‘not’ operator. Executing this simple converted lambda functions would return a Value (True or False).
I also concluded that it would be more useful to my goal of using JavaScript as a proof assistance for software validation if it was possible to build a lambda-tree representation of the function to enable a deeper analysis.

Firstly, to make this post more interesting than the last one, I will implement the new operators ‘and’ and ‘or':

lambda.logic.True = function(a,b) {return a;};
lambda.logic.False = function(a,b) {return b;};
lambda.logic.nand = function(a,b) {return (a(b, lambda.logic.False))(lambda.logic.False, lambda.logic.True);}

lambda.logic.not = function(a) {return lambda.logic.nand(a, a);};

// new logic operators 
lambda.logic.and = function(a, b) {return lambda.logic.not(lambda.logic.nand(a, b));};
lambda.logic.or = function(a, b) {return lambda.logic.nand(lambda.logic.not(a), lambda.logic.not(b));};

As you can see in the code above I use nand to define ‘not’, ‘and’ and ‘or’, so I will only need to change the function lambda.logic.nand to return a tree, defined as:

function lambda(application, variables) {
  this.application = application;
  this.variables = variables;
}

where the application is like a function and the variables are the function’s arguments.
Now that we have a nice representation the nand definition would be like this:

lambda.logic.nand = function(a,b) {
  return new lambda(new lambda(a,[b, lambda.logic.False]), [lambda.logic.False, lambda.logic.True]);
};

For the test function I chose this logic formula ‘p / (q / r) -> (p / q / (p / r))’ that I found in the Internet and have no idea what it means :D.
JavaScript doesn’t have the logic operator -> (implication), but ‘p -> q’ can be easily written with not/or operators: ‘!p || q’ and the whole formula be written like this:

function pqr(p,q,r) {
  // p / (q / r) -> (p / q / (p / r))
  return !(p || (q && r)) || ((p || q) && (p || r));
}

To convert the above formula the following code is executed:

eval(lambda.program(pqr));

Which will result in this function:

function lambda_pqr(p,q,r) {return lambda.logic.or(lambda.logic.not(lambda.logic.or(p,lambda.logic.and(q,r))),lambda.logic.and(lambda.logic.or(p,q),lambda.logic.or(p,r)));}; 

Executing the lambda_pqr (I chose to pass string arguments because I wanted to name the variables, but I could have passed the values as True or False).

var r = lambda_pqr('p', 'q', 'r');

will return the lambda tree:

r = ((((((((((p p False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) ((((p p False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) False) False True) ((((((p p False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) ((((p p False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) False) False True) False) False True) ((((((((((p p False) False True) ((q q False) False True) False) False True) ((((p p False) False True) ((r r False) False True) False) False True) False) False True) ((((((p p False) False True) ((q q False) False True) False) False True) ((((p p False) False True) ((r r False) False True) False) False True) False) False True) False) False True) ((((((((p p False) False True) ((q q False) False True) False) False True) ((((p p False) False True) ((r r False) False True) False) False True) False) False True) ((((((p p False) False True) ((q q False) False True) False) False True) ((((p p False) False True) ((r r False) False True) False) False True) False) False True) False) False True) False) False True) False) False True)

I made two functions in lambda ‘class’. One is ‘replace’, that receives a dictionary and replaces all matching keys in the lambda tree with the corresponding value. The other is the ‘solve’ function that will apply arguments to any application on the tree that can be applied.

Ex.

r_replace = r.replace({'p': lambda.logic.True});

/* Result:
r_replace = ((((((((((True True False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) ((((True True False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) False) False True) ((((((True True False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) ((((True True False) False True) ((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False) False True) False) False True) False) False True) ((((((((((True True False) False True) ((q q False) False True) False) False True) ((((True True False) False True) ((r r False) False True) False) False True) False) False True) ((((((True True False) False True) ((q q False) False True) False) False True) ((((True True False) False True) ((r r False) False True) False) False True) False) False True) False) False True) ((((((((True True False) False True) ((q q False) False True) False) False True) ((((True True False) False True) ((r r False) False True) False) False True) False) False True) ((((((True True False) False True) ((q q False) False True) False) False True) ((((True True False) False True) ((r r False) False True) False) False True) False) False True) False) False True) False) False True) False) False True)
*/

As you can see in the result, all occurrences of ‘p’ are replaced by the True value, if we try to solve it we get:

 
r_replace.solve();

// Result: True.  

From the original formula it’s easy to see that the result is actually right: p / (q / r) -> (p / q / (p / r)) => replace p with True => True / (q / r) -> (True / q / (p / r)) => True -> True => True.

But it’s more interesting when p is False:

r_replace = r.replace({'p': lambda.logic.False});
r_replace.solve();

/* Result:
r_replace = (((((((((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False True) (((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False True) False) False True) (((((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False True) (((((((q r False) False True) ((q r False) False True) False) False True) ((((q r False) False True) ((q r False) False True) False) False True) False) False True) False True) False) False True) False) False True) (((((((((q q False) False True) False True) (((r r False) False True) False True) False) False True) (((((q q False) False True) False True) (((r r False) False True) False True) False) False True) False) False True) (((((((q q False) False True) False True) (((r r False) False True) False True) False) False True) (((((q q False) False True) False True) (((r r False) False True) False True) False) False True) False) False True) False) False True) False) False True)
*/

The tree is partially solved because there isn’t anything else to replace. q and r are not defined so the result can’t be reduced any more.

Conclusions

The idea of this post was to experiment with the tree representation of a function. The chosen example is a logical formula because it is easier to experiment with.
There are some limitations in the code regarding the use of propositional logic. One is that I have to use the values True and False and it isn’t possible to say, instead of p=True, just say that p exists and apply some elimination rules.
I don’t know if in the current state of the tree representation it would be possible to somehow apply the propositional logic techniques and rules, but even if is possible (I think) a very handy feature would be to keep different levels of representation, being the lambda calculus the base and lowest level.
With representation levels it would be much easier to maintain a human representation and in the case of propositional logic it would be great to deal with the normal logic symbols ->, /, / … and use what is already in the field, for example the method of analytic tableaux.

So I guess in the next post about this subject I will try to add different levels of representation to the tree.

See you soon…

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)