cduce:496c41bdeee73def0eb1769b440cfb6e36664a4d commitshttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commits/496c41bdeee73def0eb1769b440cfb6e36664a4d2015-02-21T03:16:35Zhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/496c41bdeee73def0eb1769b440cfb6e36664a4dRevert "Implement a cache for the positive equation solver (partial results a...2015-02-21T03:16:35ZKim Nguyễnkn@lri.fr
This reverts commit <a href="/cduce/cduce/commit/a8ba6ab61f5ce5818ead46c8139821d4c94f6e88" data-original="a8ba6ab61f5ce5818ead46c8139821d4c94f6e88" data-link="false" data-link-reference="false" data-project="160" data-commit="a8ba6ab61f5ce5818ead46c8139821d4c94f6e88" data-reference-type="commit" data-container="body" data-placement="bottom" title="Implement a cache for the positive equation solver (partial results are stored in nodes)" class="gfm gfm-commit has-tooltip">a8ba6ab6</a>.
This commit introduces a regression where suprious type variables are introduced in the final type.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/a8ba6ab61f5ce5818ead46c8139821d4c94f6e88Implement a cache for the positive equation solver (partial results are store...2015-02-20T21:55:22ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/083edd022de8ff57c1e538a0cc71ec50b8dec806Seal the representation of SortedList.Make(X).t (by making the type private)....2015-02-20T13:11:30ZKim Nguyễnkn@lri.frSeal the representation of SortedList.Make(X).t (by making the type private). Expose Var.Set as a SortedList.S
https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/f217bc2678649fe4cd78ded48e5df1139c784fefPerform a more aggressive memoization of substituted types and register the...2015-02-19T09:40:57ZKim Nguyễnkn@lri.frPerform a more aggressive memoization of substituted types and register the name if the original type was named.
Make the pretty-printer re-entrant.
https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/6149608ac6f298e88aac81a3d24077f46062974cAdd a memoization table to remember previously applied substitutions.2015-02-19T00:11:34ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/3aab1b01cc7b4847d33defa5e4639d285a9504aaImplement a safety-check to guarantee that recursive parametric types2015-02-18T15:46:18ZKim Nguyễnkn@lri.frremain regular. Within their recursive definitions, parametric types
must always be instantiated with their original parameters and all
types of mutually recursive definitions must have the same parameters.
We use Tarjan's strongly connected components algorithm to group type definitions accordingly.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/64b01477c33372ebe85acc2256d349e35638dde1Change the behaviour introduced by commit:bcf40231ba0beb63984fe6ec225907b3ce0...2015-02-17T09:51:16ZKim Nguyễnkn@lri.fr[ 'abc'ab ] is now parsed as [ 'abc' ab ] to maintain backward compatibility.
Change the warning message accordingly.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/b862df33e7a0869e19ee7e420f15ad2c5604a179Update the dependency file after moving some code from typing/typer.ml to par...2015-02-17T09:49:15ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/4f49a2af7b54e58a27429bb063ef1a07bfa0bed5Remove the a workaround the AST for patterns that was used to2015-02-16T21:24:54ZKim Nguyễnkn@lri.frcorrectly handle insantiated types in regular expressions.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/bcf40231ba0beb63984fe6ec225907b3ce07620dAdd a warning when the lexer encounters the ambiguous ``[ 'a'a ]'' and2015-02-16T21:13:57ZKim Nguyễnkn@lri.frsuggest to put a space before the second quote.
Move the auxiliary 'warning' function from the typechecker to the
Cduce_loc module.
Re-indent some comments in ulexer.mlhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/b05e438fd4815a7f8c48c08da1333b196e156b60Correctly flush the toplevel output in case the lexer consumes the2015-02-16T21:12:56ZKim Nguyễnkn@lri.fr"\n" after the ;; token.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/36b83c45bcc77d90b511b9e62f3a333dd4ad5834Fix the handling of polymorphic variables in the lexer. The solution2015-02-16T16:09:23ZKim Nguyễnkn@lri.frto use two lexers (depending on whether we are between square brackets
or not) is too brittle (it crudely tries to parse
``( [whitespace] 'a [whitespace] )'' as a variable, to force the user
to write the variable beetween parenthesis. However this does not scale
to types with two arguments (says [ t ('a, 'b) ]).
We use a simpler heuristic (with look ahead)
(1) try to see if the regular expression
' (anything but ', \n)* '(anything but the first letter of an identifier)
can be found. If so, we put back the lexeme in the buffer and parse it as as
a string.
(2) if (1) failed, try to parse it as a variable
(3) if (3) failed, try to parse it again as a string. We are
guaranteed to fail here but it means we have a malformed string, so we
parse as a string to get a proper error message.
The only thing this does not cover are cases like
type t = [ 'abcd'Int ]
which was tokenized before as [, 'abcd', Int, ]
and is now tokenized as [, 'abcd, 'Int, ]
It does not seem to be a problem in practice though (since in the code
I have seen thus far, people were at least putting a space).
it is easy to emmit a warning in this case, suggesting the user to add
a whitespace to get the old behaviour back.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/77556e8b12ac2546d6df64675b80fa39b7b41045Fix handling of intersection of polymoprhic types in regular expression.2015-02-16T14:03:29ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/07bc7bc14d48c9dbe8482c589fff1b0e0570f303Implement the syntax ``t (t1, …, tn)'' for type instantiation, without2015-02-16T13:20:15ZKim Nguyễnkn@lri.frrequiring an abscence of whitespace between ``t'' and ``(''. Outside
of regular expression contexts, ``t (t1, …, tn)'' is parsed with a
higher precedence than & and \, to allow one to write
``t (Int) & Bool'' without extra parentheses (i.e.
``(t (Int)) & Bool''). Inside a regular expression, type
instantiation and sequencing become ambiguous, and there is no way to
distinguish syntactically: ``[ Int (Int, Int) ]'' from
``[ t (Int, Int) ]''. The former should resolve to a sequence while
the latter only makes sense as an instantiation (if ``t'' is a
parametric type). Both are treated as element sequencing and
disambiguated during identifier resolution (more precisely during the
"derecurse" phase, before typechecking).
Note that due to the lower precedence of sequencing w.r.t to other
regular expression constructs, a type ``[ t (Int)* ]'' will be parsed
correctly, but yield an error message saying that t is not fully
intantiated. One has to write ``[ (t (Int))* ]'' which is similar to
function applications for expressions.
Finally, we also re-order sequencing after typing to always group a
potential type instantiation with its argument, i.e. we transform
sequences such as
``[ t1 t2 t3 ... tn ]'' (which are parsed as
``[ (((t1 t2) t3) ... tn) ]'' because sequence concatenation is
left-associative) into ``[ ... (ti tj) ... ]'' if ``ti'' is an
identifier and ``tj'' is of the form ``(s1,...,sk)''. This is sound
because concatenation of regular expression is associative (and the
original sequence would fail, anyway).https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/bd1de27e41a7eb2b0d40353438cb63da2bcc6265Fix a regression introduced by commit:8852caa where sequence typing2015-02-15T21:44:46ZKim Nguyễnkn@lri.frcontaining variables but no toplevel variables would not be printed as
regular expressions but nested pairs.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/10678fc8cedf72db80e5d04cbb2d16890ca15243Remove the need for mandatory spaces around ':' in function parameters.2015-02-15T13:25:09ZKim Nguyễnkn@lri.frNow functions such as
let fun f (x:Int):Int = ...
are parsed correctly (that is, its parameter is 'x' with type Int).https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/09feaa190e9a64a14905c4c58fe3699f55debae1Remove the need to create a .stamp file for the camlp4 extension.2015-02-13T20:51:30ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/cb23ae0d9cf2249c3bfd54163375d79768dee74cAdd more generated files to .gitignore2015-02-13T20:47:08ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/8852caa65ec69f03847ebd99c7af637bf67dc6a0Fix a pretty-printing bug where top-level variables intersected with2015-02-10T22:38:38ZKim Nguyễnkn@lri.frsequence type would not show up (e.g. 'a & [ Any *] would be displayed
as [ Any * ], while the 'a would still be present internally).https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/31915c44ddfb116043481465c40ef13f4114db86Add a .gitignore file to the project.2015-02-10T14:57:39ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/24523591c4da236d5cd3a4c21ee1d4f891ea322cAdd a println builtin function that prints a newline.2015-02-10T14:55:15ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/d9edaee1aae47c196015f2a357974f1312289688Working code ... still need to type it.2014-12-19T20:14:32ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/8796e6aaa024c325505458083e668e942332792bCommited for a bug2014-12-19T14:54:06ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/7a7520a032fc9c291b75bc684ec4e4b3409f4093Added comments2014-12-18T13:12:36ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/11ecd5f6074d509ba0077485750f449f67b4c910Error in the definition of cardinal2014-12-16T21:56:06ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/8b04fb93d4f0bb98bee3531ee078a8c26099b3aedeleted old version of red-black2014-12-16T21:52:35ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/bd0debdd85925292bca4a1ac74def0236d33afa6added few more operations2014-12-16T21:51:45ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/e7f9356813b521a9fee27352ef1975462824f74dChanged syntax of types for type parameters2014-12-16T16:58:29ZGiuseppe CastagnaGiuseppe.Castagna@cnrs.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/aa9f66549015bacfa1db315781b2909d71d05169In Positive, only update the kind of variables not in delta.2014-12-14T13:29:41ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/d4737ec101b84bdad6022fe81b7e2a2d4885edafAdd a missing function to the Loc module in ulexer.ml (so that the current trunk2014-12-14T12:42:14ZKim Nguyễnkn@lri.frcompiles with the patched camlp4 bundled with fedora 21)https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/912c5b2cdbce93c7f26d2b7c17e3700264353f39Start refactoring the Types module2014-12-06T22:26:07ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/674264c7595601ca49f143a6cea7a48f60354a6aFix a subtle bug in Positive.decompose (for some complex recursive types,2014-12-06T17:30:38ZKim Nguyễnkn@lri.frPositive.solve(Positive.decompose t) was not the identity but added spurious types at toplevel.
Added more test cases in poly-ok.cd to cover such regressionshttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/411a2ab0593952cab3a361cb6208ef8347847f58re-organise the test files and add new typing tests.2014-12-06T08:38:34ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/9d34f8a789fd73dd8ee8e7fee4241ddeba67f38fFix the check that no polymorphic variables occurs in the accepted type of a ...2014-12-04T16:31:16ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/867489617b5f988515b067492345c72bfc31b57cRecursively check in the global normalisation hash table whether the2014-12-01T16:30:31ZKim Nguyễnkn@lri.frtype has already been normalized. Without this patch, in the following usage:
norm(T1, delta)
norm(<a>[ T1 ], delta)
the fact that T1 has already been normalized against some delta is not taken into
account while normalizin <a>[T1].https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/7932c0717701b1ffb079bc44867491801bfaa8b3Improve the complexity of constraint normalisation by using a hash2014-12-01T16:15:51ZKim Nguyễnkn@lri.frtable instead of a 'recursion set' like in the paper. The hash table
is tricky:
- its keys should be both the type we are normalizing and
delta
- we should store a flag together with the constraint set, indicating
whether the computation of the normalization for the corresponding
type has finished. If it has, we can use the associated constraint set
instead of CS.sat and stop recursion. If it has not, we can return
CS.sat (like the previous base case).
We also update the test case files to check that everything is in order:
- part2.cd has been rewritten to make use of the new syntax and remove
the red-black trees examples that are now in a separate file
- red-black.cd is a fully typechecking file
- rb-fail.cd has the type definition and the wrong balance function.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/42dda81a3fb7690c0ceb94fa991e93e3cbef5f96Fix a bug in toplevel definition of types:2014-12-01T15:15:04ZKim Nguyễnkn@lri.fr
when a type such as
type t('a) = (Int,'a)
is introduced, the variables occuring in the definitions are replaced by fresh occurences.
The variables in the left-hand-side were note renamed accordingly, yielding a type definition:
type t('a_0) = (Int, 'a_1)
when performing type substitutions, none of the occurences of 'a_1 were replaced.https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/01e9ada96fbefb30ea97de8b8c3db4e5c049be76Simplify (and fix) the code adding variables of a function interface to delta...2014-12-01T15:03:04ZKim Nguyễnkn@lri.frSimplify (and fix) the code adding variables of a function interface to delta during the typing of its body.
https://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/d7b41a1a2c1df0f9b776f7620d6f439e1e90e381Remove unused exception handling code.2014-12-01T15:00:39ZKim Nguyễnkn@lri.frhttps://gitlab.math.univ-paris-diderot.fr/cduce/cduce/commit/2b0f24c66cf14c27b6e61b7d1344954a674615d9Delay the check that detects types variables occurring in patterns until...2014-12-01T14:58:19ZKim Nguyễnkn@lri.frDelay the check that detects types variables occurring in patterns until type-checking time (this allows us to have access to delta and thus know the monomorphic variables, which are allowed)