A software library has been developed that takes a highlevel description of a pattern to be satisfied and applies it to a target. If the two match, it returns success; otherwise, it indicates a failure. The target is semantically a tree that is constructed from elements of terminal and non-terminal nodes represented through lists and symbols. Additionally, functionality is provided for finding the element in a set that satisfies a given pattern and doing a tree search, finding all occurrences of leaf nodes that match a given pattern. This process is valuable because it is a new algorithmic approach that significantly improves the productivity of the programmers and has the potential of making their resulting code more efficient by the introduction of a novel semantic representation language. This software has been used in many applications delivered to NASA and private industry, and the cost savings that have resulted from it are significant.
This program was written by Mark James of Caltech for NASA's Jet Propulsion Laboratory. For more information, download the Technical Support Package (free white paper) at www.techbriefs.com/tsp under the Software category. This software is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-42732.
This Brief includes a Technical Support Package (TSP).
Pattern Matcher for Trees Constructed From Lists
(reference NPO-42732) is currently available for download from the TSP library.
Don't have an account?
Overview
The document titled "An Interpreted-based Pattern Matcher for Trees Constructed from Lists" (NASA Tech Brief NPO-42732) presents a software solution designed to enhance the efficiency of software development, particularly for applications that manipulate code as data or utilize symbolic representations. The primary challenge addressed is the cumbersome process of writing specialized, non-portable code to handle individual cases of data matching, which can lead to inefficiencies and increased error rates.
The software described in the document offers several key advantages:
-
Increased Productivity: It provides a high-level programming language that allows developers to express complex patterns using a minimal number of tokens, significantly reducing the amount of code needed.
-
Enhanced Reliability: By reducing the size of the code, the software minimizes the potential for errors, leading to more reliable applications.
-
Improved Debugging and Verification: The abstraction level offered by the software makes it easier to verify and debug code, as it aligns more closely with the problem being addressed.
-
Better Readability: The high-level nature of the code makes its purpose clearer, facilitating easier understanding and maintenance.
The core functionality of the software involves taking a high-level description of a pattern and applying it to a target, which is represented as a tree constructed from terminal and non-terminal nodes. If the pattern matches the target, the software returns success; otherwise, it indicates failure. Additionally, it includes features for identifying elements in a set that satisfy a given pattern and for conducting tree searches to find all occurrences of leaf nodes that match specified patterns.
This innovative algorithm has been successfully implemented in numerous applications for NASA, the Jet Propulsion Laboratory (JPL), and private industry, resulting in significant cost savings. The software is versatile, running on various platforms, including SUN, HP, Intel, Apple MACs, and flight processors. It can be distributed in both source code and binary form, requiring a LISP compiler for operation.
Overall, the document emphasizes the software's potential to revolutionize the way developers approach pattern matching in programming, making it a valuable tool for enhancing productivity and reliability in software development.
