What is the canonical way to lift an interpreter to an abstract interpreter, while ensuring convergence ---figuring out how and when to widen?<div><br></div><div>Thanks</div><div>Siddharth<br><div dir="auto"><br><div class="gmail_quote"><div dir="ltr">On Thu, 22 Nov, 2018, 18:52 Holger Siegel via Haskell-Cafe, <<a href="mailto:haskell-cafe@haskell.org">haskell-cafe@haskell.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello Olaf,<br>
<br>
to me that sounds as if you want to do an abstract interpretation with a <br>
forward collecting semantics that employs non-relational abstract <br>
domains for the primitive data types and summarizes the dimensions of <br>
arrays. That is what the Java compiler does when it analyzes whether a <br>
variable is 'effectively final' (except that it doesn't even have to <br>
summarize arrays for that), and it should suffice for the kind of bugs <br>
you want to find.<br>
<br>
I would start by writing a simple interpreter for the language to be <br>
analyzed. That way you fix messy details before they bite you, e.g. the <br>
order in which submodules are loaded and initialized. You also get a <br>
clear formalization of the semantics, and you can annotate the syntax <br>
tree and implement informative error messages for the bugs you want to <br>
detect. You don't even need to implement every primitive function - it <br>
suffices that they return some random value, provided that the intended <br>
return value is one of the possible values. Lifting the interpreter to <br>
an abstract interpreter can then be done in a canonical way.<br>
<br>
<br>
Regards,<br>
<br>
Holger<br>
<br>
<br>
Am 21.11.2018 um 22:01 schrieb Olaf Klinke:<br>
> Dear Cafe,<br>
><br>
> I want to build a linter for a C-like language. My company uses a UI system that comes with a C-like language that is used to provide functionality to the UI elements. The language is interpreted at runtime. The user, however, has no access to the built-in parser and checking functions. Only a basic syntax check comes with their editor. Therefore many stupid mistakes only show at runtime and can not be tested for statically.<br>
> The language is in many respects even simpler than C. No structs, no enumerations, only a handful of basic data types and arrays thereof, plus pointers and the usual control flow structures. On the other hand, there are some features that make static analysis near impossible, e.g. the possibility of dynamic registration of variables. Higher-order types are emulated by passing the name of other functions as strings. There is explicit referencing of other sources (#include statements) as well as implicit referencing within UI elements and within the project hierarchy.<br>
><br>
> We want to catch basic programming mistakes - misspelled variables, missing return statements, usage of variables before assignment, wrong number of function arguments/types. A project's code is scattered across multiple files and layers - a function declaration can mask a declaration from the layer below. Therefore, a per-file-linter will not suffice.<br>
> As a side-effect this may also yield a documentation generator (boy do I miss haddock while working with that), which is also missing in the system.<br>
><br>
> I have never done something like this and will seek help from local CS departments (If you are a CS student in Paderborn or Bielefeld, Germany, get in touch!). My company would be willing to sponsor a Bachelor or Master's thesis project. Ultimately this will be comercialized as an add-on, so anyone who helps will also profit from the result financially. The user community is not large, but includes big names such as Siemens, London Heathrow, the Metros in NYC and Bilbao, and CERN.<br>
><br>
> What kind of expertise shall I look for? Compiler theorists? What information shall I request from the language author? I feel that Haskell might be a good language to represent the AST in. But I am overwhelmed by the numerous AST libraries on hackage.<br>
><br>
> How similar is my problem to what is covered by, say, haskell-src-exts, hlint, alex or syntactic? Can I re-use code from these projects?<br>
><br>
> What solutions are out there for dependency resolution between source files?<br>
><br>
> I suppose for informative error messages I need to decorate each semantic bit with information about<br>
> - source file and location<br>
> - what is in scope at that position, plus the source of the symbols in scope<br>
> What data structures can be used to build and represent this information?<br>
><br>
> Any pointers welcome.<br>
> Olaf<br>
><br>
><br>
> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> To (un)subscribe, modify options or view archives go to:<br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
> Only members subscribed via the mailman list are allowed to post.<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Sending this from my phone, please excuse any typos!</div></div>