Generating identifiers for tuples of recursively defined relations

Patent metadata

Field	Value
Publication number	US-9830358-B1
Application number	US-201715466696-A
Country	US
Kind code	B1
Filing date	Mar 22, 2017
Priority date	Sep 30, 2016
Publication date	Nov 28, 2017
Grant date	Nov 28, 2017

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating identifiers for tuples of recursively defined relations. One of the methods includes selecting one or more of the recursively defined relations to evaluate. Respective keys are computed for each tuple of any new tuples computed during recursive evaluation. For each key that occurs in a cache of keys, obtaining a tuple for the key from the cache and adding the obtained tuple to a new relation. For each key that does not occur in the cache of keys, generating a new identifier for the key, and adding, to a new relation for each key of each tuple of any keys that do not occur in the cache of keys for a relation, a new tuple comprising (1) elements of the tuple and (2) the new identifier for the key.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving a request to compute identifiers for domain tuples of a relation for a first alternative subtype of an algebraic data type, wherein the first alternative subtype depends on a definition of a second alternative subtype of the algebraic data type; and
until evaluating a definition of the first alternative subtype generates no new domain tuples, performing operations comprising:
evaluating the definition of the first alternative subtype using tuples in a relation for the second alternative subtype to generate one or more new domain tuples for the first alternative subtype;
computing, for each new domain tuple of the one or more new domain tuples generated for the first alternative subtype, a respective key using each element belonging to the new domain tuple;
determining, for each key computed for each new domain tuple, whether the key for the new domain tuple has been previously generated;
for each key that had been previously generated, obtaining an identifier previously generated for the key and adding a new identifier tuple to the relation for the first alternative subtype, the new identifier tuple comprising the identifier and each element belonging to the new domain tuple; and
for each key that had not been previously generated, generating a new identifier for the key and adding a new identifier tuple to the relation for the first alternative subtype, the new identifier tuple comprising the new identifier and each element belonging to the new domain tuple.

2. The method of claim 1 , wherein determining, for each key computed for each new domain tuple, whether the key for the new domain tuple has been previously generated comprises determining whether the key for the new domain tuple occurs in a cache of keys.

3. The method of claim 2 , further comprising for each key that had not been previously generated, adding the key to the cache in association with the new identifier for the key.

4. The method of claim 2 , further comprising:
maintaining a distinct cache of keys for each of a plurality of recursively defined relations, wherein the plurality of recursively defined relations includes the first alternative subtype.

5. The method of claim 2 , further comprising:
maintaining a distinct cache of keys for each of a plurality of different arities for domain tuples generated for recursively defined alternative subtypes.

6. The method of claim 2 , further comprising:
maintaining a distinct cache of keys for each of a plurality of representative types, each representation type representing types of elements of domain tuples generated for recursively defined alternative subtypes.

7. The method of claim 1 , wherein the first alternative subtype also depends on itself, and wherein evaluating the definition of the first alternative subtype comprises using second domain tuples in the relation for the second alternative subtype and any domain tuples generated for the first alternative subtype.

8. The method of claim 1 , wherein the second alternative subtype depends on a definition of the first alternative subtype.

9. The method of claim 8 , further comprising alternating between generating new domain tuples of the relation for the first alternative subtype and second domain tuples of a second relation for the second alternative subtype.

10. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving a request to compute identifiers for domain tuples of a relation for a first alternative subtype of an algebraic data type, wherein the first alternative subtype depends on a definition of a second alternative subtype of the algebraic data type; and
until evaluating a definition of the first alternative subtype generates no new domain tuples, performing operations comprising:
evaluating the definition of the first alternative subtype using tuples in a relation for the second alternative subtype to generate one or more new domain tuples for the first alternative subtype;
computing, for each new domain tuple of the one or more new domain tuples generated for the first alternative subtype, a respective key using each element belonging to the new domain tuple;
determining, for each key computed for each new domain tuple, whether the key for the new domain tuple has been previously generated;
for each key that had been previously generated, obtaining an identifier previously generated for the key and adding a new identifier tuple to the relation for the first alternative subtype, the new identifier tuple comprising the identifier and each element belonging to the new domain tuple; and
for each key that had not been previously generated, generating a new identifier for the key and adding a new identifier tuple to the relation for the first alternative subtype, the new identifier tuple comprising the new identifier and each element belonging to the new domain tuple.

11. The system of claim 10 , wherein determining, for each key computed for each new domain tuple, whether the key for the new domain tuple has been previously generated comprises determining whether the key for the new domain tuple occurs in a cache of keys.

12. The system of claim 11 , wherein the operations further comprise for each key that had not been previously generated, adding the key to the cache in association with the new identifier for the key.

13. The system of claim 11 , wherein the operations further comprise:
maintaining a distinct cache of keys for each of a plurality of recursively defined relations, wherein the plurality of recursively defined relations includes the first alternative subtype.

14. The system of claim 11 , wherein the operations further comprise:
maintaining a distinct cache of keys for each of a plurality of different arities for domain tuples generated for recursively defined alternative subtypes.

15. The system of claim 11 , wherein the operations further comprise:
maintaining a distinct cache of keys for each of a plurality of representative types, each representation type representing types of elements of domain tuples generated for recursively defined alternative subtypes.

16. The system of claim 10 , wherein the first alternative subtype also depends on itself, and wherein evaluating the definition of the first alternative subtype comprises using second domain tuples in the relation for the second alternative subtype and any domain tuples generated for the first alternative subtype.

17. The system of claim 10 , wherein the second alternative subtype depends on a definition of the first alternative subtype.

18. The system of claim 17 , wherein the operations further comprise alternating between generating new domain tuples of the relation for the first alternative subtype and second domain tuples of a second relation for the second alternative subtype.

19. One or more non-transitory computer storage media encoded with computer program instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
receiving a request to compute identifiers for domain tuples of a relation for a first alternative subtype of an algebraic data type, wherein the first alternative subtype depends on a definition of a second alternative subtype of the algebraic data type; and
until evaluating a definition of the first alternative subtype generates

Assignees

• Semmle Ltd

Inventors

• Eyers-Taylor Alexander
• Schaefer Max

Classifications

• G06F17/30513 Primary

  Physics · mapped topic

• G06F17/30421

  Physics · mapped topic

• G06F17/3048

  Physics · mapped topic

• G06F17/30321

  Physics · mapped topic

• G06F16/2448 Primary

  for particular applications; for extensibility, e.g. user defined types · CPC title