What is the difference? The difference is that interpretation ends on terminal expressions, and for non-terminal expressions it continues in depth along all incoming nodes\/arguments. If the AST tree consisted only of non-terminal expressions, then the application execution would never be completed, since some finiteness of any process is required, and this finiteness is represented by terminal expressions, they usually contain data, such as strings.<\/p>\n
An example of an AST tree is below:<\/p>\n
![\"\"](\"https:\/\/demensdeum.com\/blog\/wp-content\/uploads\/2022\/06\/ast.png\")
\nDcoetzee, CC0, via Wikimedia Commons<\/p>\n
As you can see, terminal expressions are constant and variable, non-terminal expressions are the rest.<\/p>\n
What is not included<\/h3>\n
The implementation of the Interpreter does not include parsing the language string input into an AST tree. It is enough to implement classes of terminal, non-terminal expressions, Interpret methods with the Context argument at the input, format the AST tree from expressions, and run the Interpret method at the root expression. The context can be used to store the application state during execution.<\/p>\n
Implementation<\/h3>\n
The pattern involves:<\/p>\n
- \n
- Client \u2013 \u200b\u200breturns the AST tree and runs Interpret(context) for the root node (Client)<\/li>\n
- Context \u2013 contains the state of the application, passed to expressions during interpretation (Context)<\/li>\n
- Abstract expression \u2013 an abstract class containing the Interpret(context) (Expression) method<\/li>\n
- A terminal expression is a final expression, a descendant of an abstract expression (TerminalExpression)<\/li>\n
- A non-terminal expression is not a final expression, it contains pointers to nodes deep in the AST tree, subordinate nodes usually affect the result of interpreting the non-terminal expression (NonTerminalExpression)<\/li>\n<\/ul>\n
C# Client Example<\/p>\n
\nstatic void Main(string[] args)\n {\n var context = new Context();\n var initialProgram = new PerformExpression(\n new IExpression[] {\n new SetExpression(\"alpha\", \"1\"),\n new GetExpression(\"alpha\"),\n new PrintExpression(\n new IExpression[] {\n new ConstantExpression(\"Hello Interpreter Pattern\")\n }\n )\n }\n );\n System.Console.WriteLine(initialProgram.interpret(context));\n }\n}\n<\/code><\/pre>\n<\/div>\nAbstract Expression Example in C#<\/p>\n
\n{\n String interpret(Context context);\n}\n<\/code><\/pre>\n<\/div>\nExample of Terminal Expression in C# (String Constant)<\/p>\n
\n{\n private String constant;\n\n public ConstantExpression(String constant) {\n this.constant = constant;\n }\n\n override public String interpret(Context context) {\n return constant;\n }\n}\n<\/code><\/pre>\n<\/div>\nExample of Non-Terminal Expression in C# (Start and concatenate results of subordinate nodes, using the separator “;”<\/p>\n
\n{\n public PerformExpression(IExpression[] leafs) : base(leafs) {\n this.leafs = leafs;\n }\n \n override public String interpret(Context context) {\n var output = \"\";\n foreach (var leaf in leafs) {\n output += leaf.interpret(context) + \";\";\n }\n return output;\n }\n}\n<\/code><\/pre>\n<\/div>\nCan you do it functionally?<\/h3>\n
As we know, all Turing-complete languages \u200b\u200bare equivalent. Is it possible to transfer the Object-Oriented pattern to the Functional programming language?<\/p>\n
For the experiment, we can take the FP language for the web called Elm. Elm does not have classes, but it does have Records and Types, so the following records and types are involved in the implementation:<\/p>\n
- \n
- Expression \u2013 an enumeration of all possible expressions of the language (Expression)<\/li>\n
- Subordinate expression \u2013 an expression that is subordinate to a Nonterminal expression (ExpressionLeaf)<\/li>\n
- Context \u2013 a record that stores the state of the application (Context)<\/li>\n
- Functions implementing Interpret(context) methods \u2013 all necessary functions implementing the functionality of Terminal, Non-terminal expressions<\/li>\n
- Auxiliary records of the Interpreter state \u2013 necessary for the correct operation of the Interpreter, store the state of the Interpreter, context<\/li>\n<\/ul>\n
An example of a function implementing interpretation for the entire set of possible expressions in Elm:<\/p>\n
\ncase input.expression of\n Constant text ->\n { \n output = text, \n context = input.context \n }\n Perform leafs ->\n let inputs = List.map (\\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in\n let startLeaf = { expressionLeaf = (Node (Constant \"\")), context = { variables = Dict.empty } } in\n let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in\n {\n output = (runExpressionLeaf outputExpressionInput).output,\n context = input.context\n }\n Print printExpression ->\n run \n { \n expression = printExpression, \n context = input.context \n }\n Set key value ->\n let variables = Dict.insert key value input.context.variables in\n {\n output = \"OK\",\n context = { variables = variables }\n }\n Get key ->\n {\n output = Maybe.withDefault (\"No value for key: \" ++ key) (Dict.get key input.context.variables),\n context = input.context\n }\n<\/code><\/pre>\n<\/div>\nAnd parse?<\/h3>\n
Parsing source code into an AST tree is not part of the Interpreter pattern, there are several approaches to parsing source code, but we’ll talk about that some other time.
In the implementation of the Interpreter for Elm, I wrote the simplest parser in the AST tree, consisting of two functions – parsing the node, parsing the subordinate nodes.<\/p>\n\nparseLeafs state =\n let tokensQueue = state.tokensQueue in\n let popped = pop state.tokensQueue in\n let tokensQueueTail = tail state.tokensQueue in\n if popped == \"Nothing\" then\n state\n else if popped == \"Perform(\" then\n {\n tokensQueue = tokensQueue,\n result = (state.result ++ [Node (parse tokensQueue)])\n }\n else if popped == \")\" then\n parseLeafs {\n tokensQueue = tokensQueueTail,\n result = state.result\n }\n else if popped == \"Set\" then\n let key = pop tokensQueueTail in\n let value = pop (tail tokensQueueTail) in\n parseLeafs {\n tokensQueue = tail (tail tokensQueueTail),\n result = (state.result ++ [Node (Set key value)])\n }\n else if popped == \"Get\" then\n let key = pop tokensQueueTail in\n parseLeafs {\n tokensQueue = tail tokensQueueTail,\n result = (state.result ++ [Node (Get key)])\n }\n else \n parseLeafs {\n tokensQueue = tokensQueueTail,\n result = (state.result ++ [Node (Constant popped)])\n }\n\nparse tokensQueue =\n let popped = pop tokensQueue in\n let tokensQueueTail = tail tokensQueue in\n if popped == \"Perform(\" then\n Perform (\n parseLeafs {\n tokensQueue = tokensQueueTail, \n result = []\n }\n ).result\n else if popped == \"Set\" then\n let key = pop tokensQueueTail in\n let value = pop (tail tokensQueueTail) in\n Set key value\n else if popped == \"Print\" then\n Print (parse tokensQueueTail)\n else\n Constant popped\n<\/code><\/pre>\n<\/div>\nLinks<\/h3>\n
https:\/\/gitlab.com\/demensdeum \/patterns\/-\/tree\/master\/interpreter\/elm<\/a>
https:\/\/gitlab.com\/demensdeum\/patterns\/-\/tree\/master\/interpreter\/csharp<\/a><\/p>\nSources<\/h3>\n
https:\/\/en.wikipedia.org\/wiki\/Interpreter_pattern<\/a>
https:\/\/elm-lang.org\/<\/a>
\nhttps:\/\/docs.microsoft.com\/en-us\/dotnet\/csharp\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"What’s included The Interpreter pattern is a Behavioral design pattern. This pattern allows you to implement your own programming language by working with an AST tree, the nodes of which are terminal and non-terminal expressions that implement the Interpret method, which provides the functionality of the language. Terminal expression \u2013 for example, the string constantContinue reading “Pattern Interpreter”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[95],"class_list":["post-3131","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-patterns","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"en","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3131","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/comments?post=3131"}],"version-history":[{"count":15,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3131\/revisions"}],"predecessor-version":[{"id":3886,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3131\/revisions\/3886"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/media?parent=3131"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/categories?post=3131"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/tags?post=3131"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}