Method and system for reducing an intentional program tree represented by high-level computational constructs

• US 6,097,888 A
• Filed: 04/28/1995
• Issued: 08/01/2000
• Est. Priority Date: 10/29/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Simonyi, Charles
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/431,049
• Time in Patent Office: 1,922 Days
• Field of Search: 395/700, 395/701, 395/702, 395/703, 395/705, 395/706, 395/707, 395/708, 395/709, 345/967
• US Class Current: 717/144
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/33 Intelligent editors
• CPC Class Codes: Y10S 715/967 Visual or iconic programming

Abstract

A method and system for generating a computer program in the manner that uses no computer programming language syntax. The system represents a computer program as an intentional program tree, which is a high-level program tree that is a syntax-independent representation using high-level computational constructs. The intentional program tree represents a programmer'"'"'s intent, rather than an implementation of the programmer'"'"'s intent. The programmer creates an intentional program tree using a syntax-independent editor. The editors allows a programmer to directly manipulate the intentional program tree. Because the program is stored as an intentional program tree in a syntax-independent manner, the editor allows the program to select in which of a various programming language the computer program is to be displayed. In addition, the system transforms an intentional program tree to a reduced program tree, which is a program tree comprising low-level computational constructs, in a process called reduction. The reduction process replaces expressions of programmer'"'"'s intents with a representation of one of possible multiple implementations of those intents using low-level computational constructs.

Claims

1. A method in a computer system for generating executable code for a computer program, the method comprising the steps of:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein the step of receiving an intentional program tree includes creating the intentional program tree by direct manipulation of the intentional program tree by a programmer; and

including the step of receiving a new high-level computational construct and receiving an implementation of the new high-level computational construct that uses low-level computational constructs, wherein the step of creating the intentional program tree includes adding a node to the intentional program tree representing the new high-level computational construct, and wherein the node representing the new high-level computational construct is transformed using the received implementation.

2. A method in a computer system for generating executable code for a computer program, the method comprising the steps of:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein each high-level computational construct has a function for transforming a node representing the high-level computational construct into a node representing an implementation of the high-level computation construct using low-level computational constructs and wherein the step of transforming the node representing a high-level computation construct includes invoking the function to transform the node.

3. A method in a computer system for generating executable code for a computer program, the method comprising the steps of:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein each high-level computational construct has a function for displaying a representation of a node representing the high-level computational construct, and upon receiving the intentional program tree, for each node invoking the function of the high-level computational construct represented by the node.

4. A method in a computer system for generating executable code for a computer program, the method comprising the steps of:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct including the step of before the step of transforming, preprocessing nodes to store indications to control the transforming to identify errors.

5. The method of claim 4 wherein the indications include flags to indicate a low-level computational construct that corresponds to an overloaded high-level computational construct.

6. The method of claim 5 wherein the step of preprocessing is performed as a background activity during the step of receiving the intentional program tree.

7. A computer system for generating a computer program, the computer program having a plurality of high-level computational constructs, each high-level computational construct having a behavior, the computer system comprising;

means for creating an intentional program tree by direct manipulation of the intentional program tree, the intentional program tree having nodes representing the high-level computational constructs of the computer program;

means for reducing the intentional program tree to a reduced program tree, the reduced program tree having nodes representing low-level computational constructs, each high-level computational construct having a reduction enzyme for reducing a node representing the high-level computational construct into one or more nodes that implement the behavior of the high-level computational construct, each of the nodes representing a low-level computational construct;

means for adding a new high-level computational construct for use in creating the intentional program tree, the new high-level computational construct having a reduction enzyme, the new high-level computational construct for use in the intentional program tree; and

means for generating executable code based in the reduced program tree.

8. A computer system for generating executable code for a computer program, comprising:

an editor with a graphical user interface through which an intentional program is input by a user in a syntax-independent manner, the intentional program being stored in an intentional program tree with high-level computational constructs;

a reducer that reduces the high-level computational constructs of the intentional program tree to low-level computational constructs by replacing portions of the intentional program tree to form a reduced program tree; and

a code generator for generating executable code based on the reduced program tree representation of the computer program.

9. The computer system of claim 8 wherein the intentional program tree is a tree data structure in which nodes of the tree data structure represent the high-level computational constructs that form the computer program.

10. The computer system of claim 8 wherein the intentional program tree has nodes representing high-level computational constructs, each high-level computational construct having a display enzyme for displaying a representation of the high-level computational construct.

11. The computer system of claim 10 wherein a computational construct has a plurality of display enzymes, each display enzyme for displaying a different representation of the high-level computational construct.

12. The computer system of claim 11 wherein a user selects one of the different representations for displaying the computer program.

13. The computer system of claim 8 wherein the intentional program tree is a tree data structure in which nodes of the tree data structure represent the high-level computational constructs that form the computer program and the reducer replaces nodes that represent high-level computational constructs with nodes representing low-level computational constructs.

14. The computer system of claim 8 wherein the intentional program tree has nodes representing high-level computational constructs, each high-level computational construct having a reduction enzyme for reducing the high-level computational construct to corresponding low-level computational constructs that implement behavior of the high-level computational construct.

15. The computer system of claim 14 wherein a high-level computational construct has a plurality of reduction enzymes, each reduction enzyme for providing different low-level computational constructs that implement the behavior of the high-level computational construct.

16. The computer system of claim 15 wherein a user selects one of the different reduction enzymes for reducing the high-level computational construct.

17. The computer system of claim 8 wherein the code generator is a code generator portion of an existing compiler for a programming language.

18. The computer system of claim 17 wherein the reducer generates a reduced program tree that is compatible with an input format of the code generator portion of the existing compiler.

19. The computer system of claim 8 including;

a markup component that annotates the intentional program tree with information to facilitate reduction of the intentional program tree to the reduced program tree.

20. The computer system of claim 19 wherein the markup component indicates that a polymorphic operator with operands should be replaced with a non-polymorphic operator that is specific to the type of the operands.

21. The computer system of claim 19 wherein the markup component operates concurrently with the editor.

22. A method in a computer system for generating executable instructions that implement a computer program represented by an intentional program tree, the intentional program tree having nodes representing high-level computational constructs that form the computer program, the method comprising:

for each node of the intentional program tree,

selecting a reduction enzyme for the high-level computational construct of the node; and

invoking the selected reduction enzyme to transform a portion of the intentional program tree relating to the node to represent the high-level computational construct using low-level computational constructs; and

after invoking the selected reduction enzymes, generating executable code from the transformed representation of the intentional program tree to implement the computer program.

23. The method of claim 22 wherein a high-level computational construct has a plurality of reduction enzymes, each reduction enzyme for providing different low-level computational constructs that implement the behavior of the high-level computational construct.

24. The method of claim 23 wherein a user selects one of the different reduction enzymes for reducing the high-level computational construct.

25. The method of claim 22 wherein each reduction enzyme includes a match function and a transform function and wherein the selecting of a reduction enzyme includes invoking the match functions of a plurality of reduction enzymes until an invoked match function returns an indication that the transform function of the corresponding reduction enzyme should be invoked.

26. The method of claim 25 wherein the invoking of the selected reduction enzyme invokes the transform function corresponding to the match function that returned the indication.

27. The method of claim 22 wherein customized reduction enzymes can be added by users of the computer system and wherein the selecting selects a customized reduction enzyme.

28. The method of claim 22 wherein the generating of executable code is performed by a code generator portion of an existing compiler for a programming language.

29. The method of claim 27 wherein the transform by the reduction enzyme produces a reduced program tree that is compatible with an input format of the code generator portion of the existing compiler.

30. The method of claim 22 including before selecting and invoking the reduction enzymes annotating the intentional program tree with information to facilitate the transforming of the intentional program tree by the reduction enzymes.

31. The method of claim 30 wherein the annotating indicates that a polymorphic operator with operands should be replaced with a non-polymorphic operator that is specific to the type of the operands.

32. A computer-readable medium containing instructions for causing a computer system to generate executable code for a computer program, by:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein the receiving of an intentional program tree includes creating the intentional program tree by direct manipulation of the intentional program tree; and

including receiving a new high-level computational construct and receiving an implementation of the new high-level computational construct that uses low-level computational constructs, wherein the creating of the intentional program tree includes adding a node to the intentional program tree representing the new high-level computational construct, and wherein the node representing the new high-level computational construct is transformed using the received implementation.

33. A computer-readable medium containing instructions for causing a computer system to generate executable code for a computer program, by:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein each high-level computational construct has a function for transforming a node representing the high-level computational construct into a node representing an implementation of the high-level computation construct using low-level computational constructs and wherein the transforming of the node representing a high-level computation construct includes invoking the function to transform the node.

34. A computer-readable medium containing instructions for causing a computer system to generate executable code for a computer program, by:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein each high-level computational construct has a function for displaying a representation of a node representing the high-level computational construct.

35. A computer-readable medium containing instructions for causing a computer system to generate executable code for a computer program, by:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

including before the transforming of a node, preprocessing nodes to store indications to control the transforming.

36. A computer-readable medium containing instructions for causing a computer system to generate executable code for a computer program, by:

receiving an intentional program tree having nodes, each node representing a high-level computational construct of the computer program;

for each node representing a high-level computational construct, transforming the node into an implementation of the high-level computational construct, the implementation represented by one or more nodes representing low-level computational constructs; and

for each node representing a low-level computational construct, generating executable code that implements the low-level computational construct;

wherein each high-level computational construct has a function for displaying a representation of a node representing the high-level computational construct, and upon receiving the intentional program tree, for each node invoking the function of the high-level computational construct represented by the node.

37. A computer system for generating a computer program, the computer program having a plurality of high-level computational constructs, each high-level computational construct having a behavior, the computer system comprising:

a component that creates an intentional program tree by direct manipulation of the intentional program tree, the intentional program tree having nodes representing the high-level computational constructs of the computer program;

a component that reduces the intentional program tree to a reduced program tree, the reduced program tree having nodes representing low-level computational constructs, each high-level computational construct having a reduction enzyme for reducing a node representing the high-level computational construct into one or more nodes that implement the behavior of the high-level computational construct, each of the nodes representing a low-level computational construct;

a component that adds a new high-level computational construct for use in creating the intentional program tree, the new high-level computational construct having a reduction enzyme, the new high-level computational construct for use in the intentional program tree; and

a component that generates executable code based in the reduced program tree.

38. The computer system of claim 37 wherein a high-level computational construct has two different reduction enzymes and a user selects one of the different reduction enzymes for reducing the high-level computational construct.

39. The computer system of claim 37 wherein each reduction enzyme includes a match function and a transform function and wherein the reducing includes invoking the match functions of a plurality of reduction enzymes until an invoked match function returns an indication that the transform function of the corresponding reduction enzyme should be invoked.

40. The computer system of claim 39 wherein the invoking invokes the transform function corresponding to the match function that returned the indication.

41. The computer system of claim 37 wherein the component that adds a new high-level computational construct adds customized reduction enzymes defined by users of the computer system.

42. The computer system of claim 37 wherein the component that generates executable code is a code generator portion of an existing compiler for a program language.

43. The computer system of claim 42 wherein the reducing produces a reduced program tree that is compatible with an input format of the code generator portion of the existing compiler.

44. The computer system of claim 37 including a component that annotates the intentional program tree with information to facilitate the transforming of the intentional program tree by the reduction enzymes.

45. The computer system of claim 44 wherein the annotating indicates that a polymorphic operator with operands should be replaced with a non-polymorphic operator that is specific to the type of the operands.

46. A computer-readable medium containing instructions that cause a computer system to generate executable instructions that implement a computer program represented by a program tree, the program tree having nodes representing high-level computational constructs that form the computer program, by:

for each node of the program tree,

selecting a reduction function for the high-level computational construct of the node; and

invoking the selected reduction function to transform a portion of the program tree relating to the node to represent the high-level computational construct using low-level computational constructs; and

after invoking the selected reduction function, generating executable code from the transformed representation of the program tree to implement the computer program.

47. The computer-readable medium of claim 46 wherein a high-level computational construct has a plurality of reduction functions, each reduction function for providing different low-level computational constructs that implement the behavior of the high-level computational construct.

48. The computer-readable medium of claim 47 wherein a user selects one of the different reduction functions for reducing the high-level computational construct.

49. The computer-readable medium of claim 46 wherein each reduction function has a match function and a transform function and wherein the selecting of a reduction function includes invoking the match functions of a plurality of reduction functions until an invoked match function returns an indication that the transform function of the corresponding reduction function should be invoked.

50. The computer-readable medium of claim 49 wherein the invoking of the selected reduction function invokes the transform function corresponding to the match function that returned the indication.

51. The computer-readable medium of claim 46 wherein customized reduction functions can be added by users of the computer system and wherein the selecting selects a customized reduction function.

52. The computer-readable medium of claim 46 wherein the generating of executable code is performed by a code generator portion of an existing compiler for a programming language.

53. The computer-readable medium of claim 52 wherein the transform by the reduction function produces a reduced program tree that is compatible with an input format of the code generator portion of the existing compiler.

54. The computer-readable medium of claim 46 including before selecting and invoking the reduction functions annotating the program tree with information to facilitate the transforming of the intentional program tree by the reduction functions.

55. The computer-readable medium of claim 54 wherein the annotating indicates that a polymorphic operator with operands should be replaced with a non-polymorphic operator that is specific to the type of the operands.