[Haskell-cafe] A static analyzer

[Richard O'Keefe]

There are very few programming language mailing lists or newsgroups
that tolerate "do my homework" questions, although many, including this,
are helpful to beginners.

The thing you need to understand is that this assignment has three aspects:
(1) understand the problem
(2) craft a solution to the problem
(3) implement the solution in your chosen programming language.

It is only the last of these aspects which actually has anything to do
with Haskell.  If you cannot complete (1) and (2) in *any* form, then
Haskell is not going to help you.

(1) I presume BIPL is the "Basic Imperative Programming Language"
defined in "Software Languages: Syntax, Semantics, and Metaprogramming"
by Ralf Lämmel.  BIPL-E is not mentioned in that book, so I have no clear
idea of it, and I don't suppose others on this mailing list had any more luck
finding it than I did.  A reference to the definition would be handy.

Having understood the data that you will work with (the abstract syntax of
a programming language), you have to understand what kind of problem
you have.  What are you supposed to COMPUTE?

This is a *data-flow* problem.  There are many books about
data-flow analysis, and lecture slides and tutorials in great abundance
on the web.

However, it is a *simplified* problem because the programming
language you are using is composed using single-entry single-exit
control structures, with no exception handling, and where
expressions cannot contain assignments.  (I haven't actually read
the book, so I don't know what BIPL-E does about procedures.)

The things you need to know in your traversal are
 - which variables are DEFINED on entry to a statement
 - which variables BECOME defined during a statement
 - which variables are defined on exit from a statement
 - which variables are USED within a statement (whether
   redefined in that statement or not).
The nasty problem is that getting a precise answer is not
possible, but you have been given a hint.  In
   if <expr> then <stmt> [else <stmt>]
   while <expr> do <stmt>
you don't know whether <expr> will come out true or false.
In (if E then S1 else S2), a variable should be treated as used
if it is used in E, S1, or S2.  A variable will become defined only
if it becomes defined in both S1 and S2.
In (while E do S), a variable should be treated as used
if it is used in E or S.  Since S might not be executed,
a variable is certain to be defined after the while only if it
is certain to be defined before it.
That is, you are not calculating WILL be defined/used but
MUST be defined/MIGHT be used.

Work through a number of exercises by hand to make sure
you understand the problem and formulate a solution.

(3) You will have to figure out a way to represent a set of
variables.  If memory serves me correctly, BIPL does not have
indexed variables, so a variable is just a variable name.  You
might want to see what data structures Haskell already has for
sets.  That would be a good question to ask here.

On Fri, 21 Feb 2020 at 09:28, Eirik Ravnskog <eirik.ravnskog92 at gmail.com> wrote:
>
> Hi. I have a homework-assignment where one of the tasks is to make a static Analyzer for BIPL-E, BIPL-E being the BIPL Language with input- and output-parameters.
>
> The Analyzer is supposed to
>
> check that all variables has been defined before use. If not, give an error message.
>
> You can do this by traversing each statement in the program to check if it uses values that
>
> haven’t been defined before. You can keep track of which variables that has been defined so far in a list, and put new ones to the list when you encounter Assign-statements
>
> check that all output parameters have been given a value when the program has ended
> You don’t care about what the different statements really evaluates to .
>
>
>
> As a start:
>
>
>
> static_analyzer :: BIPLE -> ..
>
> ..
>
>
>
> Best regards,
>
> Eirik
>
>
>
> Sendt fra E-post for Windows 10
>
>
>
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.