[m-dev.] proof-of-concept code for choosing a grade

[Zoltan Somogyi]

Around oct 22-26 we discussed my proposal for a new approach
to specifying grades. We agreed that it would need to be accessible
not just in the Mercury compiler, but also in shell scripts.

While writing a constraint solver as a shell script is a VERY unappealing
prospect, writing it in standard C allows it to be called from shell
scripts, even before we have configured Mercury. So the attached
code is in C. While this code is now a standalone program, my intention
is that it should eventually divided into two or more separate .c files.
One .c file would contain the actual constraint solver, but would do
no I/O. Other .c files would act as wrappers: they would get the
list of desired features and the results of autoconfiguration tests
(such as whether we can use GCC registers), either from a file or
from the command line, give this info to the solver, and output the
results. There may be more than one of these, because you may
want more than one input format and/or output format. And
of course we could wrap the solver with Mercury code as well;
such a wrapper should be able to replace (most of) the current
compiler/compute_grade.m.

This code is VERY preliminary. It implements only four solver
variables instead of the couple of dozen we discussed, and
only a few constraints. It takes input and generate output
in a very simple form, as a set of solver var name = value
pairs, which is NOT intended to be final. It is designed
to be as simple as possible, not to run as fast as possible,
but given the small problem size, I don't expect runtime
to be a problem anyway.

I am mostly seeking feedback on the overall design approach.

- The decision to do it in C.

- The representation of constraints. A conceptual constraint
  such as "debugging requires low level code" is expressed
  as two low-level constraints in cg.c: DBG=debug is allowed
  only if CL=lo, and CL=hi is allowed only if DBG=none.
  Each of the low level constraints expresses a requirement
  on a given solver variable s1 having a given value s1a:
  it requires that some other solver variable s2 have value
  s2a or s2b or ... If s1=s1a imposes requirements on
  more than other solver variable, those requirements
  need to be implemented as more than one low-level
  constraint. These low level constraints act as one
  directional propagators: if s2 cannot have ANY of
  the values listed (s2a, s2b etc), then s1 cannot be s1a.

- When we rule out a value for a solver variable, we record
   the id of the rule that did it. This SHOULD allow us,
   eventually, to give detailed reasons why e.g. asking for
   DBG=debug and TARGET=java at the same time won't work.
   (The code does not yet handle inconsistent constraints.)

- The solving process consists of alternating propagation
   and labeling steps, but we don't backtrack over labeling
   steps; we commit to them. This works in this small
   constraint set; I am not sure whether it will work on
   our full constraint set.

- The labeling step works by choosing a value for the
   lowest numbered solver variable, and the value it chooses
   is the lowest numbered value that hasn't been ruled
   out yet. Therefore order matters for both solver vars
   and their values.

- C is typeless, but I tried to use a naming scheme that
  makes putting e.g. an integer representing a solver var id
  into a slot that expects e.g. an integer representing a value
  stand out. I also added a sanity check.

I await your comments. I want us to get to a consensus
on the overall approach before I work on finishing the solver
(much less writing the wrappers), and before we discuss
such details as the names of the options that ask for
each feature.

Zoltan.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cg.c
Type: application/octet-stream
Size: 15252 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/developers/attachments/20151205/edc601f4/attachment.obj>