OKlibrary  0.2.1.6
Maxima.hpp File Reference

General plans regarding the Maxima computer algebra system. More...

Go to the source code of this file.


Detailed Description

General plans regarding the Maxima computer algebra system.

For discussions (explanations, documentations) of Maxima-functionality see ComputerAlgebra/plans/MaximaTechniques.hpp.

Bug:
DONE (now setting the memory-limits when loading Maxima; resetting them from the command-line is okay with Ecl, but setting them when loading a file is asking for too much) Maxima seg-faults when loading a file setting memory-limits
  • When running at test_level=full, we get
    okltest_certificates_vdw_3k(certificates_vdw_3k)
    /bin/bash: line 6: 28062 Segmentation fault      (core dumped) HOME=/home/kullmann/OKplatform/ExternalSources/Installations/Maxima/ecl/5.23.2 /home/kullmann/OKplatform/ExternalSources/Installations/Maxima/ecl/5.23.2/bin/rmaxima --batch-string="" --very-quiet
    make[2]: *** [/home/kullmann/OKplatform/OKsystem/OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/testobjects/certificates.mac] Error 1
       
  • Same with 5.21.1 and 5.23.2.
  • The same happens when just running
    oklib_test_level:1;
    oklib_load("OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/testobjects/certificates.mac");
       
    from the Maxima-shell.
  • However
    oklib_test_level:1;
    load(sconcat(OKsystem,"/OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/testobjects/certificates.mac"));
       
    works?!
  • On the other hand,
    oklib_test_level:1;
    batch(sconcat(OKsystem,"/OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/testobjects/certificates.mac"));
       
    fails again with a segmentation fault.
  • Notify the Maxima mailing-list.
Todo:
Why is Maxima file output so slow?
  • We have the following very slow output in Maxima:
    (%i12) A : apply(sconcat,create_list("1",i,1,500))$
    Evaluation took 0.0000 seconds (0.0070 elapsed)
    (%i13) with_stdout("test.txt", for i : 1 thru 100000 do print(A))$
    Evaluation took 7.1600 seconds (7.4840 elapsed)
       
  • However, in C++, this would take a fraction of a section, and even in interpreted languages like python, this takes only 0.2 seconds.
  • MG has sent an e-mail to the Maxima mailing list regarding this issue.
  • It is suggested on the Maxima mailing list that the reason for slow printing is the checking and simplification Maxima performs on the expression passed to print.
  • For faster output of strings, we should pass the output directly to lisp print functions.
    maxima> A : apply(sconcat,create_list("1",i,1,500))$
    maxima> with_stdout("test.txt", for i : 1 thru 100000 do print(A))$
    Evaluation took 8.9100 seconds (9.1250 elapsed)
    maxima> with_stdout("test.txt", for i : 1 thru 100000 do (?princ(A), ?terpri()))$
    Evaluation took 3.3100 seconds (3.6900 elapsed)
       
  • Note that the lisp function princ doesn't print an extra space after the string, whereas Maxima's print function does.
Todo:
DONE (this was fixed in Maxima, after communication on the mailing-list) Stable sorting
  • DONE (we assume < is meant) The documentation of "sort" doesn't say anything about the behaviour in case of equal items.
  • DONE So it could even not work at all in case of equal items!
  • DONE The documentation is also faulty w.r.t. whether the supplied predicate should be reflexive or irreflexive.
    1. Actually from the documentation it should follow that equal elements can not be handled, since the predicate for subsequent elements shall be true, while the key example "orderlessp" is an irreflexive order!
    2. So it is not clear whether "<" or "<=" should be used.
  • Supposing that it works (it absolutely should!), without the specification one is in the worst situation: one has to assume that the order of equal elements is changed, without being able to rely on faster sorting. The Maxima mailing list has been contacted (12.11.2011).
  • See "Simplifications" in Satisfiability/Lisp/PseudoBoolean/plans/CardinalityConstraints.hpp for an example of this problem.
  • Also min_elements_l and max_elements_l in ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac rely on sort being stable.
Bug:
DONE (resolved with version 5.21.1) Strings cause errors in evaluation of expressions
  • Once there is anywhere a string, ">" can not be applied anymore:
    (%i1) is("x">0);
    Maxima encountered a Lisp error:
     "x" is not of type LIST.
    (%i2) is(f("x")>0);
    Maxima encountered a Lisp error:
     "x" is not of type LIST.
    (%i3) declare(f, posfun);
    (%i4) is(f(1) > 0);
    (%o4) true
    (%i5) is(f("x") > 0);
    Maxima encountered a Lisp error:
     "x" is not of type LIST.
       
  • DONE Notify the Maxima mailing-list.
Todo:
DONE (transferred to docus) Restricted recursion for memoised functions
  • Consider
    fib_mem[n] := if n <= 1 then n else fib_mem[n-1] + fib_mem[n-2];
    
    fib_mem[6100];
    Maxima encountered a Lisp error:
     C-STACK overflow at size 8421376. Stack can probably be resized.
       
  • In Ecl we can resize the c-stack:
    get_c_stack_ecl();
      8421376
    set_c_stack_ecl(2^24);
      16777216
    
    is(fib_mem[6100] = fib(6100));
      true
       
  • Another (general) possibility is to write for memoised recursive functions a wrapper which calls the function bottom-up.
  • _fib_mem[n] := if n <= 1 then n else _fib_mem[n-1] + _fib_mem[n-2]$
    fib_mem(n) := (for i : 0 thru n-1 do _fib_mem[i], _fib_mem[n])$
    is(fib_mem(6100) = fib(6100));
      true
       
Todo:
Memoised functions
  • Consider
    _fib_mem[n] := if n <= 1 then n else _fib_mem[n-1] + _fib_mem[n-2]$
    fib_mem(n) := (for i : 0 thru n-1 do _fib_mem[i], _fib_mem[n])$
    is(fib_mem(6100) = fib(6100));
      true
       
  • It would be better if one could find out whether the value _fib_mem[n] is already defined.
  • Then fib_mem would first check whether _fib_mem[n] is already defined, and only if this is not the case would it run through the loop.
Todo:
Argument-length restriction
  • In CLisp we have the very restrictive maximal argument-length of 4095 (at least on 32-bit machines), which is better in ECL (2^16), however in CLisp "union" can be applied to arbitrarily many arguments, while in ECL it is restricted by the maximal argument-length.
  • We need to find out about these restrictions, and its variations.
    1. One test is
      apply(union,create_list({},i,1,2^17));
           
  • DONE (we have now uaapply) Perhaps the cmucl is the only usable Lisp, since apparently it does not pose any restriction on the argument-length?
Todo:
How to use function-parameters reliably??
  • The biggest problem with Maxima is that function-parameters are not handled properly, not even the arguments of lambda-terms.
  • It is unclear what actually happens, but names of parameter, which take functions or lambda-terms as values, must be all different!
    1. On the other hand, calling test-functions from other test-functions doesn't cause problems.
    2. We need clear examples, where errors occur.
  • It seems that nested function calls though are not a problem (this would render it hopeless!).
  • This must be discussed on the Maxima mailing list (but I (OK) fear nothing will happen).
    1. Take as example "every_s" from ComputerAlgebra/DataStructures/Lisp/Lists.mac (how to write it properly).
    2. If the function-parameter would be called "npred", then "okltest_some_ndiag_scom_p" in ComputerAlgebra/CombinatorialMatrices/Lisp/tests/Basics.mac runs into an infinite loop.
  • One thing is to reserve names for the library:
    1. Everything that starts with "_".
    2. Then we have "f"; likely we should rename it everywhere to "_f".
    3. Or perhaps "f" is an exception.
    4. Within the library, parameters naming functions must always be somewhat longer and specific (except of "f"); and they start with "_".
Todo:
Problems with errcatch
  • We get an error message
    errcatch(map(0,[]));
    Improper name or value in functional position:
    0
       
    which shouldn't be the case.
  • Contact the Maxima mailing list.
Todo:
What is "equalp" ?
  • It seems impossible to evaluate "equalp(0,0)" sensibly??
  • is(equalp(0,0)) returns "unknown" ?
  • So then the only sensible check for being zero is
    is(equal(x,0))
       
    ?? (yielding true,false, or unknown)
Todo:
Maxima/CLisp bug for larger data-sets
  • On csltok (laptop of OK) running
    oklib_store : true;
    set_random_state(make_random_state(0));
    all_unsinghitting_mvd(8, 'all_n8);
       
    produced a segmentation fault after running a bit more than 214 hours (nearly 9 full days).
  • Apparently this just happened when writing the session file.
  • A core-file has been produced --- how to analyse this?
  • When by mistake printing out the repository to the screen, I got "string too long: desired length 6553600 exceeds the supported maximum length".
  • So perhaps Maxima, when writing the file, just puts everything into a big string, and then the error occurred when this string was too long?
    1. We had one slightly bigger file in the past; however this contained the annotation-strings.
    2. So perhaps each value is transformed into a string, and now a single value (the hash-map), was too big?
    3. Repeating the experiment with seed 10 produced after nearly the same running time again a segmentation fault, so the string-problem should be the cause.
    4. With seed 11, at nearly the same file size the segmentation fault happened, but this time the file was apparently correctly written, and the fault happened a bit after writing the file?
    5. On cs-wsok, a 64-bit machine, these errors don't happen.
  • Tell the Maxima mailing-list about that and ask for a different "save", call it "fsave" (fast save):
    1. No list-annotations.
    2. No unnecessary spaces.
    3. Values are broken into small strings, if necessary.
Todo:
General design: Lists *here* are more fundamental than sets
  • It seems that instead of clause-sets we should use clause-lists as the fundamental objects.
  • In the mathematical cosmos there is no creation and destruction, thus no order, however in the computational cosmos there is before and after, construction and destruction.
  • In this way we obtain control over enumeration aspects.
    1. Typically the enumeration is controlled by ordering the elements of certain sets.
    2. Yet this done by applying listify, thus without control.
    Now, when enumerating all possibilities in some function:
    1. Either the given orders are used.
    2. Or random_permutation is applied.
    3. Perhaps we have a global flag "oklib_randomise_order", which controls this behaviour.
    4. In this way we have a simple way of random sampling.
  • But clauses should stay as sets.
  • A formal clause-list has then also a list of variables (without repetition).
  • An "ordered hypergraph" is then also given as a list of hyperedges, together with a list of vertices (the latter without repetition).
  • But the hyperedges still are sets.
  • In the same vein, "ordered graphs" are given by lists of vertices and lists of edges, the former without repetition, the latter with sets as elements.
  • So it seems that we should rewrite all of of the Maxima-functions.
  • This combined with the general clean-up.
  • The clause-sets etc. are still available, via conversions.
  • What about combinatorial matrices? Their point is, after all, the order-*independence* ?!
    1. So perhaps they stay as they are, using index-sets?
    2. However, there are the same issues regarding enumerations.
    3. So we should have also "ordered combinatorial matrices", where indices are given by 2 lists.
  • We use the adjective "ordered" as follows:
    1. Speaking of "ordered clause-sets", "ordered graphs", "ordered hypergraphs" etc.
    2. Different from the "list-types", here we do not have multiple occurrences.
    3. So an "ordered clause-set" is the same structure as a "clause-list", but we do not have multiple occurrences of the same clause (while an "clause-list" may have them).
  • Handling the multiplicity of types:
    1. We do not introduce abstraction at the Maxima/Lisp level (except of the "mathematical abstraction" given by using terms and functions).
    2. Functions are implemented for the appropriate input-types (formal clause-sets, or just clause-sets, etc.).
    3. The user applies conversions.
    4. What about providing convenience functions, which just convert their argument, and then apply the main function:
      1. It seems to me (OK), that this just yields confusion, since for some functions we have it, for some others we don't.
      2. So we should have different versions only in case they really implement different behaviour!
Todo:
Plan the redesign
Todo:
Recovering of partial results after long (unsuccessful) computations
  • See "all_unsinghitting" in ComputerAlgebra/Satisfiability/Lisp/ConflictCombinatorics/HittingClauseSets.mac for an example how to pass variable-names as parameters, and how to store the elements of the result-set piecewise in this variable.
  • And see all_hitting_DP_reductions_def in ComputerAlgebra/Satisfiability/Lisp/ConflictCombinatorics/HittingClauseSets.mac for a more advanced example how to make make these recovering-variables optional; here we have also a state-variable (the permutation count), which allows re-starting the computation from an arbitrary point.
  • In this way we should rewrite all functions which perform long computations, and for which it makes sense to collect partial results.
  • Using "oklib --maxima -g", a running computation can be interrupted by Ctrl-C, a variable "var" can be displayed by "$var" (using "(displa $var)" one gets Maxima-representation), and by "continue" (at break-level 1 !) the computation can be continued.
    1. Does this slow down computations? Some tests seem to indicate that this is not the case.
    2. So perhaps this should be our default?
    3. If something goes wrong with displaying values, then suddenly "continue" doesn't work anymore (but is treated as variable name)?!?
    4. And also for some other reasons continuation becomes impossible?? (Then we don't have a "Continuable Error").
    5. This looks like a clisp compiler weakness. Perhaps with 2.44.1 this is solved?
    6. Perhaps the problem is that when the execution is inside a sub-function then continuation is not possible?
    7. Anyway, this mechanism doesn't look really reliable yet.
  • Using "oklib_save()" in a functions stores the whole state of Maxima to a session file, after oklib_storage_interval minutes have passed, given that oklib_store is true.
    1. This should be applied throughout.
Todo:
Debugging
  • Again and again it happens that somehow the Lisp-debugger is entered, and apparently there is NO ESCAPE (":top" apparently should be the escape, but doesn't work).
  • How to disable the debugger ??
Todo:
Documentation
  • A work-around to obtain doxygen-documentation:
    1. The solution seems to be to start the .mac-files with the usual preamble, and then via "\htmlonly" and "\endhtmlonly" to suppress the extraction of code-comments (the source code is shown verbatim!).
    2. We should discuss this on the doxygen mailing list: Perhaps a dedicated doxygen-command could be introduced?
    3. Or should one use the verbatim-commands?
  • How to create function-documentation inside Maxima (usable via "? function-name") ?
Todo:
Handling of demos
  • The demos-files are put into demos-subdirectory, and are plain .mac-files (intended to be processed).
  • How to run the maxima-demos-files?
    1. Apparently, "batch" is when we want to "run through it", while "demo" is when we want to pause after each expression.
  • How to name the demos-files?
    1. If the demonstration accompanies a file, then it has the same name.
    2. Otherwise any appropriate name.
    3. The suffix ".dem" is mentioned in the Maxima-manual. This or ".mac" ?!
  • How to create pauses?
    1. On a global level one has the distinction between "oklib_batch" and "oklib_demo".
  • Integrate the demos into the test-system.
  • DONE How to print out explanations?
    1. The problem is that when using "batch" or "demo", where expressions are reported before being printed, the explanations, for which we only have the print-statement, are printed twice??
    2. The solution seems to be to use just the expression
      "Text to be shown"$
           
  • DONE How is it integrated into the general demos-system for the OKlibrary? Likely nothing special is done, only we need load-capabilities, likely here only for single files.
  • DONE (oklib_batch, oklib_demo) Extend "oklib_load" to process the maxima-demos? Perhaps better a dedicated function.
Todo:
Monitoring
  • We introduce a global variable "oklib_monitor", which our functions can use, and if set to true then they output progress information.
  • Additionally we have "oklib_monitor_level":
    1. The default is level 0, meaning that only basic messages are print.
    2. Greater values are then used at the discretion of the affected function.
    3. "inf" always indicates full output.
  • This output should happen in a standardised way, so that the source of the output is recognisable.
    1. We use "M[function_name]:" to start the message.
    2. Perhaps we can offer some general services, like functions which print the opening and ending. Something similar to the Messages-system for C++ perhaps.
      • But we don't consider internationalisation.
      • And, of course, no compile-time-issues.
      • Is there a general facility to find out the current function? Otherwise perhaps we use some standard variable, which is then set to the name of the function.
  • The monitoring code uglifies the procedure:
    1. Could there be a general scheme, that certain variables are watched and printed if they changed value, and this happens non-intrusively? But we need dedicated text etc., so this doesn't seem to hlep.
    2. Or functions which support monitoring come in two versions? This would created too much code-bloat.
    3. Output should always happen via helper-functions, so the interruption is minimal. Standard: "monitorcheck".
    4. This procedure just inherits all variable etc. via dynamic binding.
  • DONE For the introduction of "oklib_monitor", apparently "define_variable" should be used?
  • See first examples:
    1. ComputerAlgebra/Satisfiability/Lisp/Resolution/Basics.mac
    2. ComputerAlgebra/Satisfiability/Lisp/Backtracking/DLL_solvers.mac
Todo:
Contexts
  • There is the notion of a "context" --- what does it mean?
Todo:
Lisp integration
  • The Lisp-dialect is "CLisp" --- are there books?
  • How to integrate CLisp with Maxima ?
  • Shouldn't we consider our code as Lisp-code, which uses the maxima-library ? Perhaps we can discuss this on the Maxima mailing list.
Todo:
Collaboration with the Maxima community
  • On the plans for the "Google Summer of code" at http://maxima.sourceforge.net/wiki/index.php/Design%20Notes there are quite some overlaps with the OKlibrary (especially regarding "Boolean algebra and logic").
  • At some point we should contact "the Maxima community", and discuss possibilities for collaborations:
    1. The OKlibrary uses the Maxima-level only for "procedural specifications".
    2. So the Maxima community can use this as a map for the whole field, and produce some specific more efficient implementations at the Lisp level.
    3. Of course, also input on the use of Maxima in the OKlibrary would be welcome.
    4. And doxygen support for Maxima would be great.
  • A "Logic Algebra" (title of the email) module has been submitted to the maxima mailing list for consideration for inclusion in share/contrib and is viewable at http://beshenov.ru/maxima/logic/ . Perhaps some collaboration could initially occur here?

Definition in file Maxima.hpp.