MAP-CLOSURE: A GENERAL PURPOSE MECHANISM FOR NONSTANDARD INTERPRETATION

• US 20080163188A1
• Filed: 11/13/2007
• Published: 07/03/2008
• Est. Priority Date: 11/10/2006
• Status: Active Grant

• Current Assignee: National University of Ireland, Maynooth, Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Siskind, Jeffrey Mark, Pearlmutter, Barak Avrum
• Granted Patent: US 8,281,299 B2
• Time in Patent Office: Days
• US Class Current: 717/168
• CPC Class Codes: G06F 17/13 Differential equations using digital differential analysers G06F7/64
• CPC Class Codes: G06F 8/60 Software deployment

Abstract

The disclosed system provides a functional programming construct that allows convenient modular run-time nonstandard interpretation via reflection on closure environments. This construct encompasses both the ability to examine the contents of a closure environment and to construct a new closure with a modified environment. Examples of this powerful and useful construct support such tasks as tracing, security logging, sandboxing, error checking, profiling, code instrumentation and metering, run-time code patching, and resource monitoring. It is a non-referentially-transparent mechanism that reifies the closure environments that are only implicit in higher-order programs. A further example provides a novel functional-programming language that supports forward automatic differentiation (AD).

Claims

1. A computing system, comprising a processor and a memory in communication with the processor, the memory storing programming instructions executable by the processor to,

from outside the body of a first closure having one or more entries that map one or more free variables to their respective bindings, access the content of the first closure and make a second closure, the making comprising:

copying the body of the first closure, and

modifying values to which free variables of the second closure are bound relative to the free variables of the first closure;

wherein the making process preserves the identities of the free variables through the modifying step.

2. The system of claim 1, wherein:

the copy is made by applying a specified function to the slot values in the closure, and

where each slot value in the new closure is derived by applying the specified function to the corresponding slot in the existing closure.

3. The system of claim 2,

wherein the making process

is applied recursively to traverse and locally redefine all reachable functions and variable values in a program, and

does not affect the reachable functions and values of variables outside a local scope of redefinition;

wherein the local scope of redefinition is defined dynamically based on the invocation pattern of the program.

4. The system of claim 3, wherein the making process is effective to perform a nonstandard interpretation process.

5. The system of claim 3, wherein the making process is applied to compose two or more nonstandard interpretation processes.

6. The system of claim 4, wherein the making process is applied to compose two or more nested nonstandard interpretation processes.

7. The system of claim 4, wherein the nonstandard interpretation process comprises a debugging process.

8. The system of claim 4, wherein the nonstandard interpretation process comprises an execution tracing process.

9. The system of claim 4, wherein the nonstandard interpretation process comprises logging during execution of the program.

10. The system of claim 9, wherein the logging comprises logging of errors during execution of the program.

11. The system of claim 4, wherein the nonstandard interpretation process ensures the safety of the executing program.

12. The system of claim 4, wherein the nonstandard interpretation process comprises measuring utilization of resources during execution of the program.

13. The system of claim 5, wherein the nonstandard interpretation process comprises patching code in the program as it executes.

14. The system of claim 5, wherein the nonstandard interpretation process comprises enforcing a security policy on execution of the program.

15. The system of claim 5, wherein the nonstandard interpretation process comprises at least one of:

redefining semantics of a programming language, and

redefining semantics of a library.

16. The system of claim 15, wherein the nonstandard interpretation process implements automatic differentiation.

17. The system of claim 15, wherein the nonstandard interpretation process redefines the input/output semantics of the program to operate transparently with a plurality of user interfaces.

18. The system of claim 17, wherein at least one of the user interfaces is a web browser.

19. The system of claim 4,

further comprising a call-with-current-continuation operation;

wherein the modifying step and the call-with-current-continuation operation are effective to implement mutation.

20. The system of claim 2, wherein the copying and the modification are facilitated by closure conversion.

21. The system of claim 2, wherein the copying and the modification are optimized by flow analysis, abstract interpretation, and partial evaluation.

22. A system, comprising a processor and a memory in communication with the processor, the memory storing instructions executable by the processor to implement an API for programmatically applying nonstandard interpretation to a given program.

23. The system of claim 22, wherein the given program also applies nonstandard interpretation to another program.