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

• US 6,189,143 B1
• Filed: 06/27/1997
• Issued: 02/13/2001
• 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): Vo, Ted T.
• Application Number:
  US08/884,441
• Time in Patent Office: 1,327 Days
• Field of Search: 395/706, 395/707, 395/708, 717/1, 717/2, 717/3, 717/4, 717/5, 717/6, 717/7, 717/8, 717/9, 717/10, 717/11
• US Class Current: 717/109
• 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 is described for generating executable code for a computer program, A programmer creates an intentional program tree using a syntax-independent editor. The editor allows a programmer to directly manipulate the intentional program tree. The intentional program tree has nodes. Each node represents a high-level computational construct of the computer program. For each node representing a high-level computational construct, the system transforms the node into an implementation of the high-level computational construct using low-level computational constructs. For each node representing a low-level computational construct, the system generates executable code that implements the low-level computational construct. The system further provides that where a high-level computational construct has a plurality of implementations of the high-level computational construct, the system transforms the nodes by selecting one of the implementations and transforms the node in accordance with the selected implementation. The system further provides that the implementation is selected by automatically analyzing semantics of the intentional program tree.

Claims

1. A method in a computer system for specifying a new computational construct for use in defining a computer program, comprising:

providing a display enzyme for each of a plurality of computational constructs, each display enzyme for displaying a representation of the computational construct;

when displaying a computer program represented by an intentional program tree;

for each computational construct represented by a node in the intentional program tree;

identifying a display enzyme for the computational construct from among the provided display enzymes; and

invoking the identified display enzyme passing a reference to the node wherein the identified display enzyme displays a representation of the computational construct represented by the passed node; and

adding a new display enzyme for the new computational construct to the provided display enzymes so that the new computational construct can be specified in another computer program and wherein previously defined computer programs can be displayed without conflict with the new computational construct.

2. The method of claim 1 wherein the identifying includes searching the provided display enzymes for a display enzyme for the computational construct represented by the node.

3. The method of claim 2 wherein the searching includes invoking a matching function associated with a display enzyme passing a reference to the node wherein the matching function returns an indication whether the associated display enzyme is for the computation construct represented by the node.

4. The method of claim 2 wherein each node contains a reference to a display enzyme for the computational construct represented by the node.

5. The method of claim 4 wherein the reference is an indirect reference through a declaration node corresponding to the computational construct.

6. The method of claim 1 wherein each computational construct has a plurality of display enzymes and wherein the identifying includes selecting one of the plurality of display enzymes for the computational construct.

7. A method in a computer system for displaying a computer program represented by an intentional program tree, the method comprising:

providing a display enzyme for each of a plurality of computational constructs, each display enzyme for displaying a representation of the computational construct; and

for each computational construct represented by a node in the intentional program tree;

identifying a display enzyme for the computational construct from among the provided display enzymes; and

when such a display enzyme is found, invoking the identified display enzyme passing a reference to the node wherein the identified display enzyme displays of a representation of the computational construct represented by the passed node.

8. The method of claim 7 wherein the identifying includes searching the provided display enzymes for a display enzyme for the computational construct represented by the node.

9. The method of claim 8 wherein the searching includes invoking a matching function associated with a display enzyme passing a reference to the node wherein the matching function returns an indication whether the associated display enzyme is for the computational construct represented by the node.

10. The method of claim 8 wherein each node contains a reference to a display enzyme for the computational construct represented by the node.

11. The method of claim 10 wherein the reference is an indirect reference through a declaration node corresponding to the computational construct.

12. The method of claim 7 wherein each computational construct has a plurality of display enzymes and wherein the identifying includes selecting one of the plurality of display enzymes for the computational construct.

13. A method in a computer system for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the method comprising:

receiving, through the input device, data representing a plurality of nodes for a program tree, the program tree being a representation of the computer program, each node having one of a plurality of node types, the nodes of the program tree specifying operators and operands of the computer program;

storing the received data representing the nodes in the memory in a program tree structure;

retrieving an indication of one of a plurality of display representation formats for displaying a representation of the program tree based on the stored data, each display representation format having a display representation for each of the plurality of node types, each display representation being a visual indication of the node type;

generating a display representation of the program tree in accordance with the retrieved indication of the display representation format, the generated display representation including the visual indication of the node type of each node in the program tree; and

displaying the generated display representation on the display device.

14. The method of claim 13 wherein each node has an associated display enzyme for displaying a representation of the node, and wherein the step of generating a display representation includes

retrieving data representing the nodes of the program tree from the program tree structure; and

invoking the display enzyme associated with the retrieved node to generate a display representation of the retrieved node.

15. The method of claim 13 wherein the generating includes invoking a display enzyme associated with a node of the program tree to generate a display representation for the node.

16. The method of claim 15 wherein the display enzyme generates a graphics-based representation of the node.

17. The method of claim 15 wherein the display enzyme generates a bitmapped representation of the node.

18. The method of claim 15 wherein the display enzyme generates an iconic representation of the node.

19. The method of claim 13 wherein the nodes include declaration nodes corresponding to definitions and nodes in the program tree structure contain references to corresponding declaration nodes.

20. The method of claim 19 wherein a declaration node has a corresponding display enzyme for generating a display representation for a node that contains a reference to the declaration node and wherein the generating of a display representation for the node containing the reference invokes the display enzyme corresponding to the declaration node referenced by the node.

21. The method of claim 20 wherein the declaration node contains a resettable display attribute and wherein the corresponding display enzyme generates a display representation based on the setting of the display attribute.

22. A method in a computer system for displaying a computer program generated by direct manipulation of a program tree so that new computational constructs can be defined, the method comprising:

receiving data representing a plurality of nodes of a program tree representing the computer program, the received data representing operations and operands that comprise the computer program;

storing the received data representing the plurality of nodes within a program tree data structure of the computer system, the nodes of the program tree data structure forming a tree data structure containing the specification of the computer program;

generating a display representation of the computer program in a display representation format from the data stored in the program tree data structure by invoking display enzymes based on the operations and operands of the nodes; and

displaying the generated display representation on a display device of the computer system.

23. The method of claim 22 including selecting one of a plurality of display representation formats for use in generating the display representation.

24. The method of claim 23 including

selecting a second one of the plurality of display representation formats; and

generating a second display representation of the computer program from the data stored in the program tree data structure in the second selected display representation format by invoking display enzymes based on the operations and operands of the nodes.

25. The method of claim 23 wherein the program tree has a plurality of subtrees, wherein the generating includes:

traversing a subtree of the program tree data structure by visiting each node of the subtree, each node of the subtree having a display representation for each of the plurality of display representation formats; and

for each visited node, inserting the display representation of the visited node corresponding to the selected display representation format into a display representation of the computer program at a position corresponding to the position of the visited node in the subtree.

26. The method of claim 22 wherein the receiving includes:

positioning an insertion point within the program tree; and

wherein the storing of the received data includes inserting a node into the program tree data structure at a position corresponding to the positioned insertion point.

27. The method of claim 26, further including receiving an insertion point positioning instruction from a user of the computer system, and wherein the positioning positions in response to the receiving of an insertion point positioning instruction.

28. The method of claim 27 wherein receiving an insertion point positioning instruction includes receiving an absolute insertion point positioning instruction.

29. The method of claim 26 wherein receiving an insertion point positioning instruction includes receiving an insertion point positioning instruction chosen from a menu by the user.

30. The method of claim 26 wherein each node of the program tree is of one of a plurality of types, further including receiving an insert node instruction specifying the type of node to insert, and wherein the inserting inserts a new node of the type specified in the received insert node instruction.

31. The method of claim 30 wherein the receiving of an insert node instruction specifying the type of node to insert includes receiving an insert node instruction specifying the type of node chosen from a menu by the user.

32. The method of claim 26, further including inserting a placeholder node into the program tree to reserve a place for a required child node of the inserted node.

33. The method of claim 32, further including repositioning the insertion point at the placeholder node.

34. A method in a computer system for displaying a representation of a program tree when modifying a program tree in a way that allows new computational constructs to be defined, the program tree representing a computer program, the program tree having nodes describing elements of the computer program, a representation of the program tree being stored in a program tree data structure in memory of the computer system, the method comprising:

retrieving the nodes of the program tree from the program tree data structure for generating a display representation of the program tree based on the retrieved nodes;

displaying the display representation of the program tree on a display device;

selecting a displayed representation of a node of the program tree to effect the selection of the node as a currently selected node;

receiving from a user of the computer system a location of an insertion point relative to the displayed representation of the currently selected node;

positioning the insertion point at the received location;

receiving from the user a computational construct to insert into the program tree;

creating a node corresponding to the received computational construct;

inserting the created node into the program tree data structure at a point corresponding to the insertion point; and

re-displaying the display representation of the program tree with the inserted node on the display device.

35. The method of claim 34 wherein the receiving from a user of a location of an insertion point includes receiving an indication that the location is above the currently selected node.

36. The method of claim 35 wherein the inserting of the created node inserts the node such that the currently selected node is a child node of the created node.

37. The method of claim 36 wherein the inserting of the created node inserts the node such that the currently selected node is a left child node of the created node.

38. The method of claim 36 wherein the inserting of the created node inserts the node such that the currently selected node is a right child node of the created node.

39. A method in a computer system of displaying selected portions of a program tree so that new computational constructs can be defined, the program tree representing a computer program, the computer program having a plurality of computational constructs, the program tree having nodes describing each computational construct of the computer program, the program tree being stored in a program tree data structure in memory of the computer system, the method comprising:

selecting a node as a currently selected node;

receiving from a user of the computer system an indication to select a subtree of the program tree with the currently selected node as the root of the subtree;

selecting the subtree of the currently selected node as the selected portion of the program tree;

generating and displaying a display representation of the program tree from the nodes of the program tree stored in the program tree data structure, the display representation being generated by invoking display enzymes for the nodes of the program tree; and

highlighting the display representation corresponding to the selected subtree.

40. A method in a computer system for displaying representations of computer programs so that a new computational construct can be added to a current set of computational constructs without affecting the computer programs that are already represented, each computer program having a plurality of computational constructs from the current set of computational constructs, the method comprising:

for each computer program;

storing the computer program in a program tree data structure having a plurality of nodes, each node corresponding to a computational construct of the computer program and having a reference to any node corresponding to an operand of the computational construct;

modifying the computer program by directly manipulating the nodes of a program tree data structure;

displaying the computer program by retrieving the nodes of the program tree data structure, generating a display representation corresponding to the computational construct of each retrieved node, and displaying the generated display representations; and

generating object code for the computer program by retrieving the nodes of the program tree data structure and generating code corresponding to the computational constructs of the retrieved nodes

wherein when the new computational construct is added to the current set of computational constructs, the object code of each computer program can be regenerated without modification to the program tree data structure of the computer program.

41. A computer-readable medium containing instructions for causing a computer system to specify a new computational construct for use in defining a computer program, the computer system having a display enzyme for each of a plurality of computational constructs, each display enzyme for displaying a representation of the computational construct, by:

when displaying a computer program represented by program tree,

for each computational construct represented by a node in the program tree,

identifying a display enzyme for the computational construct from among the display enzymes; and

invoking the identified display enzyme passing a reference to the node wherein the identified display enzyme displays of a representation of the computational construct represented by the passed node; and

adding a new display enzyme for the new computational construct to the display enzymes so that the new computational construct can be specified in another computer program and wherein previously defined computer programs can be displayed without conflict with the new computational construct.

42. The computer-readable medium of claim 41 wherein the identifying includes searching the display enzymes for a display enzyme for the computational construct represented by the node.

43. The computer-readable medium of claim 42 wherein the searching includes invoking a matching function associated with a display enzyme passing a reference to the node wherein the matching function returns an indication whether the associated display enzyme is for the computational construct represented by the node.

44. The computer-readable medium of claim 42 wherein each node contains a reference to a display enzyme for the computational construct represented by the node.

45. The computer-readable medium of claim 44 wherein the reference is an indirect reference through a declaration node corresponding to the computational construct.

46. The computer-readable medium of claim 41 wherein each computational construct has a plurality of display enzymes and wherein the identifying includes selecting one of the plurality of display enzymes for the computational construct.

47. A computer-readable medium containing instructions for causing a computer system to display a computer program represented by a program tree, the computer system having a display enzyme for each of a plurality of computational constructs, each display enzyme for displaying a representation of the computational construct;

and

for each computational construct represented by a node in the program tree,

searching for a display enzyme for the computational construct from among the provided display enzymes; and

when such a display enzyme is found, invoking the identified display enzyme passing a reference to the node wherein the identified display enzyme displays of a representation of the computational construct represented by the passed node.

48. The computer-readable medium of claim 47 wherein the identifying includes searching the provided display enzymes for a display enzyme for the computational construct represented by the node.

49. The computer-readable medium of claim 48 wherein the searching includes invoking a matching function associated with a display enzyme passing a reference.

50. The computer-readable medium of claim 48 wherein each node contains a reference to a display enzyme for the computational construct represented by the node.

51. The computer-readable medium of claim 50 wherein the reference is an indirect reference through a declaration node corresponding to the computational construct.

52. The computer-readable medium of claim 47 wherein each computational construct has a plurality of display enzymes and wherein the identifying includes selecting one of the plurality of display enzymes for the computational construct.

53. A method in a computer system for specifying a new computational construct for use in defining a computer program, comprising:

providing a display enzyme for each of a plurality of computational constructs;

identifying a display enzyme for each computational construct from among the provided display enzymes; and

invoking the identified display enzyme to display a representation of the computational construct.

54. The method of claim 53 and further comprising adding a new display enzyme for a new computational construct for a further computer program such that the previously provided computational constructs can be displayed without conflict with the new computational construct.

55. A method in a computer system for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the method comprising:

receiving, through the input device, data representing a plurality of nodes for a program tree wherein the nodes of the program tree specify operators and operands of the computer program;

storing the received data representing the nodes in the memory in a program tree structure;

retrieving an indication of one of a plurality of display representation formats for displaying a representation of the program tree based on the stored data;

generating a display representation of the program tree in accordance with the retrieved indication of the display representation format; and

displaying the generated display representation on the display device.

56. A method in a computer system for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the method comprising:

receiving, through the input device, data representing a plurality of nodes for an intentional program tree wherein the nodes of the program tree specify operators and operands of the computer program;

storing the received data representing the nodes in the memory in an intentional program tree structure;

retrieving an indication of one of a plurality of display representation formats for displaying a representation of the intentional program tree based on the stored data;

generating a display representation of the intentional program tree in accordance with the retrieved indication of the display representation format; and

displaying the generated display representation on the display device.

57. A computer readable medium having instructions stored thereon for causing a computer to implement a method for specifying a new computational construct for use in defining a computer program, comprising:

providing a display enzyme for each of a plurality of computational constructs;

identifying a display enzyme for each computational construct from among the provided display enzymes; and

invoking the identified display enzyme to display a representation of the computational construct.

58. The computer readable medium of claim 57 and further comprising instructions for adding a new display enzyme for a new computational construct for a further computer program such that the previously provided computational constructs can be displayed without conflict with the new computational construct.

59. A computer readable medium having instructions stored thereon for causing a computer to implement a method for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the method comprising:

receiving, through the input device, data representing a plurality of nodes for a program tree wherein the nodes of the program tree specify operators and operands of the computer program;

storing the received data representing the nodes in the memory in a program tree structure;

retrieving an indication of one of a plurality of display representation formats for displaying a representation of the program tree based on the stored data;

generating a display representation of the program tree in accordance with the retrieved indication of the display representation format; and

displaying the generated display representation on the display device.

60. A computer readable medium having instructions stored thereon for causing a computer to implement a method for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the method comprising:

receiving, through the input device, data representing a plurality of nodes for an intentional program tree wherein the nodes of the program tree specify operators and operands of the computer program;

storing the received data representing the nodes in the memory in an intentional program tree structure;

retrieving an indication of one of a plurality of display representation formats for displaying a representation of the intentional program tree based on the stored data;

generating a display representation of the intentional program tree in accordance with the retrieved indication of the display representation format; and

displaying the generated display representation on the display device.

61. A system for specifying a new computational construct for use in defining a computer program, comprising:

means for providing a display enzyme for each of a plurality of computational constructs;

means for identifying a display enzyme for each computational construct from among the provided display enzymes; and

means for invoking the identified display enzyme to display a representation of the computational construct.

62. A system for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the system comprising:

means for receiving, through the input device, data representing a plurality of nodes for a program tree wherein the nodes of the program tree specify operators and operands of the computer program;

means for storing the received data representing the nodes in the memory in a program tree structure;

means for retrieving an indication of one of a plurality of display representation formats for displaying a representation of the program tree based on the stored data;

means for generating a display representation of the program tree in accordance with the retrieved indication of the display representation format; and

means for displaying the generated display representation on the display device.

63. A system for displaying a representation of a computer program, the computer system having a memory, a display device, and an input device, the system comprising:

means for receiving, through the input device, data representing a plurality of nodes for an intentional program tree wherein the nodes of the program tree specify operators and operands of the computer program;

means for storing the received data representing the nodes in the memory in an intentional program tree structure;

means for retrieving an indication of one of a plurality of display representation formats for displaying a representation of the intentional program tree based on the stored data;

means for generating a display representation of the intentional program tree in accordance with the retrieved indication of the display representation format; and

means for displaying the generated display representation on the display device.

64. A method in a computer system for specifying a new computational construct for use in defining a computer program by using multiple computational constructs, the method comprising:

providing a plurality of display enzymes for a plurality of computational constructs, each display enzyme for displaying a representation of one of the computational constructs;

identifying a display enzyme for each computational construct from the plurality of display enzymes;

invoking the identified display enzyme to display a representation of each computational construct forming the computer program; and

adding a new display enzyme to the plurality of display enzymes for the new computational construct.