MIXTUS (1)


NAME

mixtus - an automatic partial evaluator for full Prolog (v.0.3.5)

SYNOPSIS

mixtus

DESCRIPTION

mixtus is an automatic partial evaluator for full Prolog. Given a Prolog program and a query it will produce a new program specialized for all instances of that query. The partial evaluator is guaranteed to terminate for all input programs and queries.

USAGE

  • By simply writing mixtus as a command, SICStus Prolog is entered with the latest version of mixtus loaded compiled.

  • Load the program file prog to be partially evaluated by pconsult(prog).
    prog may be a list of filenames.
    Not all files used by the program need to be loaded; calls to predicates not defined in the files loaded will be handled correctly. Of course, no unfolding will be done for those predicates.

  • Given for instance the query p(17,X,Y), the partial evaluator is started by pe(p(17,X,Y)). The resulting program will be written to standard output. Alternatively, the program may be written to a file if a second argument is given to pe , e.g. pe(p(17,X,Y),filename). .

  • Normally it is assumed that all variables in the top level query can be instantiated to any value. Alternatively, a subset of the query variables can be specified as input variables . The remaining variables are then assumed to uninstantiated, and Mixtus is sometimes able to produce better code utilizing this information. This is accomplished by starting Mixtus with pei(query,inputvariables) or pei(query,inputvariables,filename)

  • A list of top-level queries can be given to Mixtus, instead of just one. For example, pe([p(f(X)),q(g(Y)]).

  • A file consulted may be partially evaluated with respect to all possible queries, that is the queries are all of the form predname(Var1,...,Varn) for all predicates predname with arity n. This can be done by the command pe_all or pe_all(filename).

  • All predicates loaded by pconsult may be erased by calling erase_all .

    OPTIONS

    Although the partial evaluator is automatic, the program produced may be improved if some general parameters are changed. The parameters are of two kinds: flags (which are changed with set(flagname) and unset(flagname) and values (changed with set(valuename,value)). The values of the current settings can be printed with the command settings. The default values of the setting are given below.

    set(maxrec,2). Sets the maximum number of recursions allowed with arguments of a size smaller or same.

    set(max_depth,4). Sets the maximum number of layers that a term is searched for different structures in the loop prevention test. At this level only comparisons of the size of the terms are performed.

    set(maxfinite,7). In the loop prevention test recursion is allowed if the arguments of a are elements from a finite set. This option determines which subset of the integers that are considered finite. The integer N belongs to the finite set iff abs(N)<maxfinite.

    set(quickpe,0). If set to 1 a very quick partial evaluation is done as recursive calls are never unfolded. The flags maxrec, maxleading and maxfinite are not used at all if quickpe is set to 1. In effect, when a quick partial evaluation is done, most of the power of Mixtus is turned off, so don't use this option unless you have to.

    set(maxnondeterm,10). If a predicate generated has more than maxnondeterm clauses, it will not be unfolded.
    maxnondeterm=10 is a reasonable value for interpreters being partially evaluated, whereas maxnondeterm=1 might be good for general programs as it guarantees that no indexing will be lost.

    unset(delayoutput). Terms in the head of clause that cannot cause the unification to fail are moved right in the clause.

    set(unfold_cut). If set, calls to clauses containing a cut will sometimes be unfolded as if the following two rules are satisfied. The first rule is that a goal is never unfolded in the test-part of an if-then-else-construct if that would lead to an introduction of cut into the test. The other rule can be satisfied in two ways. The goal p will be unfolded in the clause
    head :- g1, p, g2.
    if that clause is the last in the predicate definition and g1 cannot create any choice-points. Also, the goal p will be unfolded in any clause of the form
    head :- g, !, g1, p, g2.
    if g1 cannot create any choice-points.

    unset(unfold_cut2). Unfolding is done for a very special case for clauses containing cut.
    head :- g1, p, g2, !, g3.
    p :- g4, !, g5.
    p :- g6, !, g7.
    The goal p is unfolded if:
    - the goals between the call to p and cut (g2) cannot fail
    - for each clause defining p having a cut the goals after the cut cannot fail (i.e. the goals g5 and g7 cannot fail above).
    Note that this optimization is seldom applicable, and that it is normally turned off.

    unset(if2cut). If set, the if-then- else-construct
    (Test -> Then; Else)
    is converted into
    (Test, !, Then; Else)
    The conditions when this is done is identical to the conditions for unfolding a predicate containing a cut, as described for the parameter unfold_cut above.

    set(maxpropleft,3). Sets the maximum number of times a binding may propagate left into the same predicate call. The should normally be no need to change this value.

    set(maxlevel,0). Determines how many times the following rewrite is allowed in a clause:
    (Test -> Then; Else), Goals ---> (Test -> Then,Goals; Else,Goals)
    For implementation reasons, this rewrite is never done within the test-part of an if-then-else construct.

    unset(preserve_loops). Normally nonproductive loops followed by a failure are replaced by just a failure. If this switch is set, all loops are preserved.

    unset(tracing). Sets a tracing mode so that the current goal-stack is printed on the terminal (vt100 compatible).

    unset(tracegoalstack). Almost like tracing, but lists the goals in the goal-stack where recursive calls are indented. (Does not need vt100 compatibility.)
    Never have tracing and tracegoalstack set at the same time.

    set(comments). Comments are included in the program produced, relating the original predicates with the newly produced predicates.

    unset(print_settings). If set, the settings of these parameters is printed just before the generated code.

    set(arithopt). If set, some transformations of arithmetic expressions may not preserve the type. For example X*0 is simplified into 0 although it is 0.0 if X is a float.

    unset(functor_logical). If set, the built-in predicate functor/3 is considered logical although functor(X,F,N),X=a fails, whereas functor(a,F,N) succeeds. If functor/3 is never called so that it is meant to fail due to insufficient instantiations, the code produced may be improved if this parameter is set.
    For SICStus Prolog version 2.1 or later, functor/3 generates an error message when called insufficiently instantiated and is therefore always considered logical, and the parameter cannot be unset.

    unset(arg_logical). If set, the built-in predicate arg/3 is considered logical although arg(N,f(a),_),N=1 fails, whereas arg(1,f(a),_) succeeds.
    For SICStus Prolog version 2.1 or later, arg/3 generates an error message when called insufficiently instantiated and is therefore always considered logical, and the parameter cannot be unset.

    set(handle_freeze). If unset, freeze and dif are not handled and the execution of Mixtus is slightly faster.

    set(cyclic). All unifications are checked for cyclic structures. If unset, Mixtus execution is faster but may crash!

    set(indexargs) Normally Mixtus will not rearrange the order of the variables in the newly generated predicates, but if the flag indexargs is set, arguments which are known to be unbound at calling time are put last. This will facilitate indexing in some cases.

    Mixtus will always terminate with a correct program for all settings of all parameters except arithopt, functor_logical, arg_logical, handle_freeze, and cyclic.

    EXECUTABLE PREDICATES

    Predicates may now be declared as executable , if they can safely be executed instead of being partially evaluated. The main advantage is a considerable speed-up compared to partial evaluation. A predicate p(A,B,C) is declared executable if the fact
    executable(p(A,B,C)).
    is asserted before partial evaluation. The assertion may of course be conditional, for example:
    executable(p(A,B,C)) :- nonvar(A), var(B).
     
    Declaring a predicate as executable will most probably result in incorrect code or a nonterminating execution of Mixtus unless the predicate meets the following requirements:
    1. the predicate must be logical, i.e. it must not call nonlogical predicates such as var/1 or cut.
    2. an exhaustive search must terminate (a finite number of solutions and no infinite loops).
    The predicate may well be non-deterministic. Please be careful when declaring predicates executable as Mixtus does not check the above requirements for correctness.
    Don't forget to compile or consult predicates that are declared executable.

    DISCUSSION

    Programs that rely heavily on assert/1 and retract/1 are not likely to gain much by partial evaluation as Mixtus never tries to execute these predicates. However, the produced program is guaranteed to be correct.
    If the partial evaluation takes too long time, try decreasing the parameters maxrec and max_depth . The code produced is not likely to be as optimal then however. If that does not help, set the parameter quickpe to 1.
    Many meta-interpreters use clause/2 for accessing program clauses. Unfortunately, in SICStus Prolog clause/2 is only applicable to dynamic code. As this denotes that the code may be changed during execution Mixtus never unfolds clause/2 applied to a predicate being declared dynamic. However, and here Mixtus for practical reasons deviates from SICStus, clause/2 is unfolded for predicates not being declared dynamic.

    NEW FEATURES IN VERSION 0.3

    dif-constraints are much better handled.
    findall, bagof, setof are fully supported.
    The loop-prevention mechanism is more sophisticated.

    NEW FEATURES IN VERSION 0.3.1

    The parameters print_settings, functor_logical, arg_logical, unfold_cut and if2cut have been added. A list of top level queries can be given to Mixtus. All consulted predicates may be partially evaluated in just a single call to Mixtus.

    NEW FEATURES IN VERSION 0.3.2

    Performance improvements for dif/2, ==/2 and ==/2 and some minor bug-fixes.

    NEW FEATURES IN VERSION 0.3.3

    Limited support for numbervars/2 if the flag handle_VAR is set. As the SICStus built-in predicate portray_clause/1 cannot distinguish between '$VAR'(I) and variable names, all $VAR- structures are converted before printout. They can be reconverted by the filter fixvar in the source code directory.
    Prolog systems not supporting call_residue/2 and frozen/2 can be used if the flag handle_freeze is unset.

    NEW FEATURES IN VERSION 0.3.4

    It is now possible to declare predicates executable (see above).
    Mixtus may now run under SICStus 2.1 and later. However, the features supported by Mixtus in the program to be partially evaluated still correspond to SICStus 0.7 patch 4.

    NEW FEATURES IN VERSION 0.3.5

    More support for features in SICStus 2.1, including block- declarations. As an extra feature, a program with the now obsolete wait-declarations will be converted into a program with block-declarations if Mixtus is run under SICStus 2.1. The opposite conversion will take place, if possible, if Mixtus is run under earlier versions of SICStus.
    Note that a bug was fixed in SICStus 2.1#3 related to dif/2 on SPARCstations, and Mixtus will not handle dif/2 correctly without this bugfix.
    A bug has been fixed in Mixtus which made it loop in some rare circumstances.
    The parameters arg_logical and functor_logical are sometimes always turned on as described above.
    The parameters indexargs and unfold_cut2 have been introduced.
    A slight improvement has been made in the determinacy analysis regarding head unifications that cannot fail.

    NEW FEATURES IN VERSION 0.3.6

    Mixtus normally automatically tries to estimate the purity of a predicate (side effect, propagation sensitive or logical) and the number of solutions. This classification can now also be done manually for selected predicates (see the file executable ).
    Some minor bug-fixes and improvements of Quintus-compatibility.

    BUGS

    Please send all bugs, suggestions for improvements and interesting examples to dan@sics.se .

    REFERENCES

     An Automatic Partial Evaluator for Full Prolog , Dan
    Sahlin, SICS 
    Dissertation Series. To make Mixtus behave exactly as described in the thesis unset the parameter unfold_cut .
     The Mixtus Approach to Automatic Partial Evaluation of Full
    Prolog , 
    Dan Sahlin, In proceedings of the North American Conference on Logic Programming 1990, MIT Press.

    AUTHOR

    Written by Dan Sahlin, SICS
    email: dan@sics.se
    phone: +46 8 7521544
    fax: +46 8 7517230
    teletex: 2401-812 6154 012=SICS
    telex: 812 6154 012 SICS S

    COPYRIGHT

    Copyright SICS 1991
     

  • SunOS manual pages can be browsed from the top-level index.

    watson@csd.abdn.ac.uk