From e92c82e2c9ff541cd321ad7a8aedcf34e615197c Mon Sep 17 00:00:00 2001 From: Lars-Dominik Braun Date: Sun, 14 Jun 2015 20:35:08 +0200 Subject: First public version --- src/Codec/Pesto/Graph.lhs | 206 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 206 insertions(+) create mode 100644 src/Codec/Pesto/Graph.lhs (limited to 'src/Codec/Pesto/Graph.lhs') diff --git a/src/Codec/Pesto/Graph.lhs b/src/Codec/Pesto/Graph.lhs new file mode 100644 index 0000000..4ea2886 --- /dev/null +++ b/src/Codec/Pesto/Graph.lhs @@ -0,0 +1,206 @@ +Language semantics +------------------ + +.. class:: nodoc + +> module Codec.Pesto.Graph ( +> toGraph +> , walkRoot +> , outgoing +> , incoming +> , firstNodeId +> , resolveReferences +> , test +> ) where +> import Data.Char (isSpace, toLower, isLetter) +> import Data.List (sort, nub) +> import Test.HUnit hiding (test) +> +> import Codec.Pesto.Parse hiding (test) + +Pesto’s syntax drives a stack-based machine that transforms the linear stream +of operations generated by the parser into a directed graph. Think of the stack +as your kitchen’s workspace that is used to prepare the food’s +components. You can add new ingredients, perform actions on them, put them +aside and add them again. + +This function processes a list of nodes, that is operations uniquely identified +by an integer and returns the edges of the directed graph as a list of tuples. + +> toGraph nodes = edges +> where +> (_, _, edges) = foldl f (Nothing, [[]], []) nodes + +Ingredients are simply added to the current workspace. They should for example +appear on the shopping list. + +> f ctx (i, Ingredient _) = addToStack ctx i + +The same happens for for tools. However they are not part of the final product, +but used in the process of making it. For instance they do not appear on the +shopping list. `Time is a tool `_. + +> f ctx (i, Tool _) = addToStack ctx i + +Actions take all ingredients and tools currently on the workspace, perform some +action with them and put the product back onto the workspace. + +> f (_, stack:sx, edges) (i, Action _) = (Just i, [i]:stack:sx, edgesTo i stack ++ edges) + +Results add a label to the current workspace’s contents and move them out of +the way. It should be a meaningful name, not just A and B obviously. +Consecutive Results add different labels to the same workspace. That’s useful +when an action yields multiple results at once that are processed in different +ways. + +> f ctx (i, Result _) = consumeStack ctx i + +Alternatives too add a label to the current workspace’s content, but they pick +one of things on the workspace and throw everything else away. This allows +adding optional or equivalent ingredients to a recipe (i.e. margarine or butter). + +> f ctx (i, Alternative _) = consumeStack ctx i + +References are similar to ingredients. They are used to add items from a +workspace labeled with Result or Alternative. More on that `in the next section +`_. + +> f ctx (i, Reference _) = addToStack ctx i + +Annotations add a description to any of the previous operations. They can be +used to provide more information about ingredients (so “hot water” becomes +“+water (hot)”, tools (“&oven (200 °C)”) or actions (“[cook] (XXX)”). + +> f ctx@(Nothing, s, edges) (_, Annotation _) = ctx +> f (Just prev, s, edges) (i, Annotation _) = (Just prev, s, (i, prev):edges) + +These are helper functions: + +> addToStack (_, stack:sx, edges) i = (Just i, (i:stack):sx, edges) +> consumeStack (_, s, edges) i = +> let +> stack = dropWhile null s +> (top:sx) = if null stack then [[]] else stack +> in (Just i, []:top:sx, edgesTo i top ++ edges) +> edgesTo i = map (\x -> (x, i)) + +Here are a few example of how this stack-machine works. Each edge is a tuple of +two integer numbers. These are the nodes it connects, starting with zero. +Ingredient, Tool and Reference itself do not create any edges: + +> testGraph = [ +> cmpGraph "+ketchup &spoon *foobar" [] + +But Action, Alternative and Result do in combination with them: + +> , cmpGraph "+foobar [barbaz]" [(0, 1)] +> , cmpGraph "+foobar |barbaz" [(0, 1)] +> , cmpGraph "+foobar >barbaz" [(0, 1)] +> , cmpGraph "+foobar +B >barbaz" [(0, 2), (1, 2)] +> , cmpGraph "+foobar >barbaz +foobar >barbaz" [(0, 1), (2, 3)] +> , cmpGraph "+foobar [barbaz] +foobar >barbaz" [(0, 1), (1, 3), (2, 3)] +> , cmpGraph "&foobar [barbaz] [C] >D" [(0, 1), (1, 2), (2, 3)] + +If the stack is empty, i.e. it was cleared by a Result or Alternative +operation, consecutive results or alternatives operate on the *previous*, +non-empty stack. + +> , cmpGraph "+foobar >barbaz >C" [(0, 1), (0, 2)] +> , cmpGraph "+foobar |barbaz |C" [(0, 1), (0, 2)] +> , cmpGraph "+foobar >barbaz |C" [(0, 1), (0, 2)] + +Unless that stack too is empty. Then they do nothing: + +> , cmpGraph ">foobar >foobar" [] +> , cmpGraph "|foobar |foobar" [] +> , cmpGraph "(foobar) (foobar)" [] +> , cmpGraph "[foobar]" [] + +The Annotation operation always creates an edge to the most-recently processed +node that was not an annotation. Thus two consecutive annotations create edges +to the same node. + +> , cmpGraph "+foobar (barbaz)" [(1, 0)] +> , cmpGraph "+foobar (barbaz) (C)" [(1, 0), (2, 0)] +> , cmpGraph "+foobar (barbaz) >barbaz" [(1, 0), (0, 2)] +> , cmpGraph "+foobar >barbaz (C)" [(0, 1), (2, 1)] +> , cmpGraph "+foobar |barbaz (C)" [(0, 1), (2, 1)] +> , cmpGraph "*foobar (C)" [(1, 0)] +> ] + +References +++++++++++ + +Results and alternatives can be referenced with the Reference operation. +Resolving these references does not happen while buiding the graph, but +afterwards. This allows referencing an a result or alternative before its +definition with regard to the their processing order. + +Resolving references is fairly simple: For every reference its object name a +case-insensitive looked is performed in a table containing all results and +alternatives. If it succeeds an edge from every result and alternative returned +to the reference in question is created. + +> resolveReferences nodes = foldl f [] nodes +> where +> f edges (i, ref@(Reference _)) = map (\x -> (x, i)) (findTarget nodes ref) ++ edges +> f edges _ = edges + +> findTarget nodes (Reference (Quantity _ _ a)) = map fst $ filter (isTarget a) nodes +> where +> lc = map toLower +> isTarget dest (_, Result x) = lc x == lc dest +> isTarget dest (_, Alternative x) = lc x == lc dest +> isTarget _ _ = False + + +References works before or after the result operation. + +> testRef = [ +> cmpGraphRef ">foobar *foobar" [(0, 1)] +> , cmpGraphRef ">foobar |foobar *foobar" [(0, 2), (1, 2)] +> , cmpGraphRef "+A >foobar +B >barbaz *foobar *barbaz" [(1, 4), (3, 5)] +> , cmpGraphRef "*foobar >foobar" [(1, 0)] + +Nonexistent references do not create an edge. + +> , cmpGraphRef ">foobar *barbaz" [] + +References can use amounts and units. + +> , cmpGraphRef ">foobar *1 _ foobar *2 _ foobar" [(0, 1), (0, 2)] + +There are a few cases that do not make sense here (like loops or multiple +results with the same name). They are permitted at this stage, but rejected +`later `_. + +> , cmpGraphRef "*foobar |foobar >foobar" [(1, 0), (2, 0)] +> , cmpGraphRef "|foobar *foobar >foobar *foobar" [(0, 1), (0, 3), (2, 1), (2, 3)] +> ] + +Appendix +++++++++ + +> runGraphWith f doc expect = sort edges ~?= sort expect +> where +> (Right op) = parse ("%pesto-1 " ++ doc) +> nodes = (zip [firstNodeId..] . map snd . operations) op +> edges = f nodes +> cmpGraph = runGraphWith toGraph +> cmpGraphRef = runGraphWith resolveReferences + +> firstNodeId = 0 :: Int + +Find graph’s root node(s), that is a node without outgoing edges: + +> walkRoot nodes edges = let out = nub $ map fst edges +> in filter (\(x, _) -> notElem x out) nodes + +Get all nodes with edges pointing towards nodeid + +> incoming edges (nodeid, _) = filter ((==) nodeid . snd) edges + +> outgoing edges (nodeid, _) = filter ((==) nodeid . fst) edges + +> test = ["graph" ~: testGraph, "ref" ~: testRef] + -- cgit v1.2.3