Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am recently working on a project aiming at evaluating whether an android app crashes or not. The evaluation process is

  1.Collect the logs(which record the execution process of an app).
  2.Generate formulas to predict the result
    (formulas is generated by GP)
  3.Evaluate the logs by formulas 



Now I can produce formulas, but for convenience for users, I want to translate formulas into form of natural language and tell users why crash happened.(I think it looks like "inverse natural language processing".)

To explain the idea more clearly, imagine you got a formula like this:

  155 - count(onKeyDown) >= 148

It's obvious that if count(onKeyDown) > 7, the result of "155 - count(onKeyDown) >= 148" is false, so the log contains more than 7 onKeyDown event would be predicted "Failed".

I want to show users that if onKeyDown event appears more than 7 times(155-148=7), this app will crash.

However, the real formula is much more complicated, such as:

  (< !( ( SUM( {Att[17]}, Event[5]) <= MAX( {Att[7]}, Att[0] >= Att[11]) OR SUM( {Att[17]}, Event[5]) > MIN( {Att[12]}, 734 > Att[19]) ) OR count(Event[5]) != 1 ) > (< count(Att[4] = Att[3]) >= count(702 != Att[8]) + 348 / SUM( {Att[13]}, 641 < Att[12]) mod 587 - SUM( {Att[13]}, Att[10] < Att[15]) mod MAX( {Att[13]}, Event[2]) + 384 > count(Event[10]) != 1))

I tried to implement this function by C++, but it's quite difficult, here's the snippet of code I am working right now.

Does anyone knows how to implement this function quickly?(maybe by some tools or research findings?)Any idea is welcomed: )

Thanks in advance.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

I'm not sure that C++ is the ideal tool for this project. This sounds a lot like Logic Programming. A friend of mine has been using Clojure's built in the core.logic library (I had previously mentioned Frenchy64, but that's someone using core.logic to add type-safety to clojure).

This looks like the kind of problem that Functional or Lisp-ish programming was made to solve - turning mathematical statements into code. This is not a procedural problem (like making a to-do list). You might have a look at Lisp, or any of its derivatives (Clojure, Haskell, Erlang, Scala, Scheme, etc.).

SICP is a great training resource for learning functional programming. Martin Odersky is using it as a basis for his Functional Programming in Scala free online course which started this week. I'm guessing though that Clojure is closest to your needs. I'll see if I can get my friend to comment.

share|improve this answer
    
Thanks for your answer, I'll give it a try~ –  Po-Jen Lai Sep 24 '12 at 9:14
add comment

I'm definitely not the best person to answer this, but I'll give it a go:

What you have, to some extent, is a DSL: a domain-specific language. All of the formulas that you generate have a specific syntax and grammar, which is what constitutes a language. It's a "domain-specific" language because it specifically has to do with the domain of the formulas that you create.

Because the formulas you mention above have a specific grammar, they can assumedly be evaluated to create a "AST" or abstract syntax tree.

You could thus do the following:

  1. Use lex/yacc or bison write a parser generator. I'd suggest antlr (java-based), but you're using c++.
  2. Write your own C++ code that would then process the AST/structure that your generated parser provides.

The lex/yacc/flex/bison page above says the following:

A compiler or interpreter for a programming language is often decomposed into two parts:

  • Read the source program and discover its structure.
  • Process this structure, e.g. to generate the target program.

Lex and Yacc can generate program fragments that solve the first task.

The "source program" in this case is each formula that you evaluate. The "structure" is then the AST or similar structure that your (generated) parser will generate. You then write more code to process the structure.

Amazon (or your favorite book source) will have books on this, not to mention all the information on the internets.

Learning to write a parser generator is unfortunately not easy -- I only vaguely remember some of the theory from my university days. However, it's really worth it, because there are lots of applications for it, even in your every day work. DSL's are increasingly popping up in many different situations, and being able to work with them (or invent them!) is a valuable skill. (In short, I wish I was better at it.. )

share|improve this answer
    
Thanks for your answer, this is a good analysis. –  Po-Jen Lai Sep 24 '12 at 9:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.