Drawingand the fudgets
hyperGraphicsF. In this chapter, we will present a set of combinators that can be used for building syntax-oriented editors. Such editors present a graphical view of a structured value in an abstract syntax, for example a program in a programming language. The editors let the user manipulate the (graphical view of) the program in various controlled ways.
One problem the programmer must deal with, when developing syntax-oriented editors, is how the values of the abstract syntax should be represented, and how they should be connected to the graphical objects. We will present a solution where the operations on the abstract syntax is defined closely with the corresponding operations on the graphical objects, to avoid inconsistencies between the abstract syntax and its graphical view.
As a concrete example, consider a grammar for a tiny expression language with arithmetic operations on numbers.
Such an abstract syntax is straightforward to represent in Haskell using one datatype for each non-terminal in the grammar, and where each alternative corresponds to a data constructor.
Expr ::= Integer | Expr Op Expr Op ::= + |
| × | /
How should we connect these datatypes to the graphical objects? One solution is to definedata Expr = Number Integer | Operation Expr Op Expr data Op = Add | Subtract | Multiply | Divide
Graphicinstances for each type, which means that they can be used as leaves in the type
Drawing(confer Section 27.4). The drawing can be decorated with labels containing functions for building the abstract syntax when needed, and manipulation functions describing how the user can modify different parts of the abstract syntax. However, all labels in a
Drawingmust have the same type, which presents a complication when we want to use different datatypes for different non-terminals. In contrast, the combinators in this chapter allow editors of different type, representing different non-terminals, to be combined.
The inspiration of the combinators comes from a certain style of
parsing combinators that is part of the functional folklore (the
earliest publication we know of is [Röj95a]). If
P a is the type of parsers which returns a value of type
a, the combinators that are interesting in this context
ap :: P (a -> b) -> P a -> P b, which combines two parsers sequentially. It also acts as lifted function application, in that the function returned by the first parser is applied to the value returned by the second, yielding a value that the combination returns.
map :: (a -> b) -> P a -> P b, which applies a function to the value that a parser returns.
apcombinator is left associative (just like function application), and
maphas higher precedence than
ap. This allow a concise style when writing parsers. For example, if
pExpris an expression parser, and
pOpis an operation parser,
parses an expression followed by an operation and another expression, and returns the appropriateOperation `map` pExpr `ap` pOp `ap` pExpr :: P Expr
Exprvalue using the
The next section presents the basic combinators for building editors. Section 28.2 shows how the combinators can be used to build an editor for arithmetic expressions. Section 28.3 discusses how non-local editing operations, like variable renaming, can be handled. The implementation of the combinators is outlined in Section 28.4.
SOM i o h a(Syntax Oriented Manipulation), which represents a value (or piece of abstract syntax) of type a, that can be manipulated through input/output of values of type i and o. The parameter h is used to pass inherited attributes. The parameter a can also be used for passing synthesised attributes, if needed.
SOM expression not only represents a (structured) value,
but also contains information about how different parts of this
value might be manipulated, and how the value should be
somF :: h -> SOM i o h a -> F (Either i (SOM i o h a)) (Either o a) leaf :: Graphic g => g -> a -> SOM i o h a ap :: SOM i o h (a -> b) -> SOM i o h a -> SOM i o h b map :: (a -> b) -> SOM i o h a -> SOM i o h b select :: (h -> a -> o) -> (h -> a -> i -> Maybe (SOM i o h a)) -> SOM i o h a -> SOM i o h a attr :: (h -> a -> (h',a')) -> SOM i o h' a -> SOM i o h a'
Figure 72. The
The combinators that operate on
SOM expressions are
shown in Figure 72. The display and manipulation
SOM expressions are controlled by
somF h s will initially display the
SOM expression s, given an attribute h to
inherit. This expression can at any time be replaced by sending
SOM expression to the fudget. The fudget can also
output the value that the manipulated expression
represents. This happens when a new expression is sent to the
fudget, or when a selected part of it is replaced. The message
somF are used for the
manipulation of selected subexpressions.
SOM expressions are built with the function
leaf. The arguments to
leaf are a graphical object
to display, and the value it represents. This combinator is used,
map, to compose
expressions in the same style as parsers.
To manipulate a
SOM expression, the user must first
select a subexpression. A
SOM expression might contain
some nodes that are not possible to manipulate (for example,
syntactic decorations like keywords), and some that are. The
programmer declares that it should be possible to select and
manipulate a node by using the
select combinator. The
select fo fi s makes the
SOM expression s selectable. When the user clicks inside the graphical
representation of s, but not inside any inner selectable
node, the composition is selected and highlighted. As a result,
the output function fo is applied to the inherited
attribute and the current value. The result is output from
somF that contains the composition, and is
typically a set of editing operations that are applicable to
the selected node. Initially, the current value is merely the
value that s represents, but this might change if some
part of s is replaced. If some input (typically an
editing operation picked by the user) is sent to the fudget
while s is selected, the input function fi
is applied to the inherited attribute, the current value and
the input, yielding a new expression which replaces
select fo fi s. The input
function also has a choice of returning
Nothing, in case
the input could not be handled. This is used to delegate input
to selectable ancestors, and is covered in
attr allows the inherited attribute and
the current value to be modified simultaneously. In the
f `attr` s, f is
applied to the inherited attribute and the current value that
s represents. The result of f is the attribute
that s will inherit, and the current value of the
map, we can turn structured values into
SOMexpressions. As an example, let us consider the expression language from the introduction. We will define the functions
edOpthat turn arithmetic expressions and operators into SOM expressions. Since we do not need any inherited attributes for the moment, and the type of input and output will always be the same, we define a type synonym for the kind of SOM expressions that we will form.
The expression editortype ArithSOM a = SOM Choice [Choice] () a edExpr :: Expr -> ArithSOM Expr edOp :: Op -> ArithSOM Op
edExpris used in
exprFto form the fudget that presents the editor.
When the user selects a subexpression,exprF :: Expr -> F (Either Choice (ArithSOM Expr)) (Either [Choice] Expr) exprF e = somF () (edExpr e)
exprFoutputs a list of choices that is presented in a menu. These choices represent the operations that are available on the subexpression. If a choice is picked, it will be sent back to the editor.
exprFalso outputs the arithmetic expression for evaluation in the main fudget. A screen dump of the program is shown in Figure 73.
Figure 73. An arithmetic expression manipulator. The user has selected the subexpression
2 × 3, which can be replaced by
0 + 0.
main = fudlogue $ loopF (shellF "Choose" (smallPickListF show >+< (displayF >=^< (show . evalExpr))) >==< shellF "Expression" (scrollF (exprF (Number 0))) )
evalExpr :: Expr -> Integer evalExpr (Number i) = i evalExpr (Operation e1 b e2) = evalOp b (evalExpr e1) (evalExpr e2)
When we defineevalOp :: Op -> (Integer -> Integer -> Integer) evalOp Add = (+) evalOp Subtract = (-) evalOp Multiply = (*) evalOp Divide = \x y -> if y == 0 then 0 else x `div` y
edOp, we use a programming style which resembles the one we presented for parsing combinators in the introduction:
Numbers are shown as they are, whereas binary expressions are handled recursively and by means ofedExpr e = selExpr $ case e of Number i -> Number `map` leaf i i Operation e1 b e2 -> Operation `map` edExpr e1 `ap` edOp b `ap` edExpr e2
edOp. Each subexpression can be selected and manipulated by
selExpr, which is defined later.
The definition of
edOp is similar.
edOp b = selOp $ leaf (showOp b) b
We define the typeshowOp Add = "+" showOp Subtract = "-" showOp Multiply = "×" showOp Divide = "/"
Choiceto contain expressions that can replace the selected subexpression. Since subexpressions can be of both type
Op, we use a union type for the output.
When the user selects an expression, we arbitrarily choose to present three alternatives which let the user replace the expression with its value plus or minus one, or replace it withdata Choice = ReplaceExpr Expr | ReplaceOp Op
0 + 0. The interface is not at all the most convenient one could imagine, but it allows a patient user to enter an arbitrary expression (the
+can be replaced with any of the other operators, as we will see below). This part of the editor could of course be elaborated as desired.
selExpr :: ArithSOM Expr -> ArithSOM Expr selExpr = select outf inf where outf _ e = map ReplaceExpr [Number (evalExpr e-1), Number (evalExpr e+1), Operation (Number 0) Add (Number 0)] inf _ _ = map edExpr . stripExpr
If the user picks one of the choices, it will be propagated to the selected node, the expression is extracted from the type union, and a replacementstripExpr (ReplaceExpr e) = Just e stripExpr _ = Nothing
SOMexpression is formed. However, the type system cannot prevent programming errors that result in an operator being sent to
selExpr. To get a more robust program, the function
stripExprignores the input in this case and returns
When an operator is selected, we present a choice of the four arithmetic operators.
selOp :: ArithSOM Op -> ArithSOM Op selOp = select outf inf where outf _ _ = map ReplaceOp [Add,Subtract,Multiply,Divide] inf _ _ = map edOp . stripOp
stripOp (ReplaceOp b) = Just b stripOp _ = Nothing
SOMsubexpression, and arbitrary replacements can be specified for that expression. If a manipulation would imply a change in other parts of the expression, we are forced to replace the complete expression globally, by sending a new
somF. There are situations where we want the possibility to specify replacements that are somewhere in between the local and global alternatives. Suppose that we want to add variables to our arithmetic expressions. We would then like to provide an operation for changing the name of a variable, by selecting one occurrence (possibly the binding occurrence), and give a new name to it. This is an operation that affects the whole subtree that starts with the binding of the variable.
This effect can be achieved by using the possibility to delegate input as follows. Recall that the input function (the
second parameter of
select) can return
for input that cannot be handled. Instead of discarding the
somF will delegate it to the closest selectable
ancestor, and apply its input function. This delegation
propagates towards the root of the
SOM expression, until
a select node is found that accepts the input.
In the case of variable manipulation, delegation can be used to propagate input to the node where the variable is bound. We will do this in the following section, where we present a variant of the expression manipulator in Section 28.2, extended with variables.
Exprwith constructors for variables and let expressions.
In the construction of adata Expr = ... | Var Name | Let Name Expr Expr type Name = String
SOMexpression, we assume the presence of an environment where we can lookup the value of variables.
We will use the inherited attribute for propagating the environment. The type of SOM expressions we will use are instances oftype Env = [(Name,Integer)]
We introduce the additional combinatorstype ArithEnvSOM a = SOM Choice [Choice] Env a
drRightto prepend or append a graphical decoration to an expression.
These are used for drawing keywords, as we will see in the case of let expressions.drLeft :: Graphic g => g -> SOM i o h a -> SOM i o h a drRight :: Graphic g => SOM i o h a -> g -> SOM i o h a
The associativity of
drRight are set so that we avoid parentheses, at least in
Haskell does not declare any fixity forinfixl 3 `ap` infixr 8 `drLeft` infixl 8 `drRight`
map, which means that it gets a default declaration.
But the type ofinfixl 9 `map`
mapsuggests that it should be right associative. If it were, and had the same precedence level as
drLeft, we could skip the parentheses in expressions like
f `map` (d `drLeft` s). If local fixity declarations were allowed in Haskell, we could fix the fixity.
Local fixity declarations are not allowed in Haskell, so we giveedExpr e = let infixr 8 `map` in ...
mapa new name with the desired fixity.
infixr 8 `mapp`
Withmapp :: (a -> b) -> SOM i o h a -> SOM i o h b mapp = map
mapp, we can construct
SOMexpressions in the style shown in in Figure 74.
edExpr :: Expr -> ArithEnvSOM Expr edExpr e = case e of Number i -> selExpr $ Number `mapp` leaf i i Operation e1 b e2 -> selExpr $ Operation `mapp` edExpr e1 `ap` edOp b `ap` edExpr e2 Var n -> selVar n $ Var `mapp` leaf n n Let n e1 e2 -> selLet $ extendEnv `attr` Let `mapp` "let" `drLeft` edName n `ap` "=" `drLeft` (dropEnv `attr` edExpr e1) `ap` "in" `drLeft` edExpr e2 extendEnv :: Env -> Expr -> (Env,Expr) extendEnv = \env e@(Let n e1 _) -> ((n,evalExpr env e1):env,e) dropEnv :: Env -> Expr -> (Env,Expr) dropEnv = \env e -> (tail env,e)
Figure 74. The function
edExprextended for variables.
extendEnv will be applied to the
current let expression, from which it will extract
sufficient information to extend the environment that the
body should inherit. To avoid that the right-hand side in
the let expression also inherits the extended environment,
we use the function
dropEnv to pop the added
binding. (If we want to allow recursive declarations, we
Note that we have also used different selection functions for
different kinds of expressions. Variables are handled by
selVar, let expressions by
selLet, and the
The binding occurrence of a variable is handled by
edName (Figure 75), and selecting such a name
results in a choice of renaming it. For simplicity, we pick
an arbitrary new name that is not present in the
environment by using
edName :: Name -> ArithEnvSOM Name edName n = selName $ leaf n n selName :: ArithEnvSOM Name -> ArithEnvSOM Name selName = select outf inf where outf env n = [renameCommand n env] inf _ _ _ = Nothing renameCommand :: Name -> Env -> Choice renameCommand old env = Rename old (freshVar env) freshVar :: Env -> Name freshVar env = head (map (:) ['a'..] \\ map fst env)
Figure 75. The editor for variable names.
The input function in
selName ignores all input,
which instead is delegated to
We have extended the manipulation type with a command for renaming a variable.
data Choice = ... | Rename Name Name
The selection functions are defined in Figure 76.
selExpr :: ArithEnvSOM Expr -> ArithEnvSOM Expr selExpr = selExpr' (const ) exprInf selLet :: ArithEnvSOM Expr -> ArithEnvSOM Expr selLet = selExpr' (const ) letinf where letinf env (Let n e1 e2) (Rename n' new) | n == n' = Just (edExpr (Let new (rename n new e1) (rename n new e2))) letinf env e i = exprInf env e i selVar :: Name -> ArithEnvSOM Expr -> ArithEnvSOM Expr selVar n = selExpr' (\env -> [renameCommand n env]) exprInf selExpr' :: (Env -> [Choice]) -> (Env -> Expr -> Choice -> Maybe (ArithEnvSOM Expr)) -> ArithEnvSOM Expr -> ArithEnvSOM Expr selExpr' xchoices inf = select outf inf where outf env e = xchoices env ++ map ReplaceExpr ([ Number (v+1) , Number (v-1) , Operation n0 Add n0 , Let (freshVar env) n0 n0 ] ++ map (Var . fst) env ) where v = evalExpr env e n0 = Number 0 exprInf :: Env -> Expr -> Choice -> Maybe (ArithEnvSOM Expr) exprInf env _ = map edExpr . stripExpr
Figure 76. The selection functions for expressions.
The functions for let expressions and variables
are variants of the original
Section 28.2. We define a parameterised version (
selExpr'), which lets us add choices and specify the input
function. Note that we have added choices for all variables
The standard selection function (
selExpr) does not
have any additional choices, whereas the selection function
for let expressions (
selLet) defines an extended
input function which handles the renaming command. For a
renaming command to match, the old variable must equal the
bound variable. Otherwise, input is meant for some outer
let expression. We assume a function
rename old new e substitutes
new for old in e.
When selecting a variable, we extend the expression
selection menu with a renaming choice. Variable renaming
can then take place at any occurrence of a variable. Note
that we do not handle renaming in the input function, it is
the same as in
The rest of the program is almost the same as in the first
example, except that we pass the empty environment as an
initial inherited attribute in
exprF. The program is
seen in action in Figure 77.
exprF :: Expr -> F (Either Choice (ArithEnvSOM Expr)) (Either [Choice] Expr) exprF e = somF emptyEnv (edExpr e) emptyEnv :: Env emptyEnv = 
Figure 77. Manipulating variables. There are additional choices for the variables in the environment. Since a variable is selected, there is also a choice of renaming it.
SOMas a datatype with constructors corresponding to the combinators
ap. Since the types of the arguments to
aphave variables that do not show up in the result type, we use the possibility to specify local existential quantification using variables beginning with
?in the datatype declaration. Again, existential quantification in datatypes proves to be a useful extension to Haskell (see also Section 27.4.2).
The first four constructors correspond directly to the respective combinators.data SOM i o h a = Select (h -> a -> o) (h -> a -> i -> Maybe (SOM i o h a)) (SOM i o h a) | Map (?b -> a) (SOM i o h ?b) | Ap (SOM i o h (?b -> a)) (SOM i o h ?b) | Attr (h -> ?a -> (?h,a)) (SOM i o ?h ?a) | Leaf Dr a | Decor (Dr -> Dr) (SOM i o h a)
The first argument to theselect = Select ap = Ap attr = Attr instance Functor (SOM i o h) where map = Map
Leafconstructor is a drawing:
The label typetype Dr = Drawing SOMPointer Gfx
SOMPointer, which is defined later, is used to identify what part of a
SOMexpression the user has selected. The type
Gfxis used to store arbitrary graphical objects in the leaves (Section 27.4.2). In the definition of
leaf, we turn these graphics into drawings by means of
g(which was defined in Section 27.4.2).
The final constructor inleaf :: Graphic g => g -> a -> SOM i o h a leaf d a = Leaf (g d) a
Decor, and can be used to define layout or add additional graphics on a part of a
SOMexpression. Its first argument is a function which will be applied to a drawing that is constructed from its second argument. The combinators
drRightuses this constructor:
The fudgetdrLeft d n = Decor (\d' -> hboxD [g d,d']) n drRight n d = Decor (\d' -> hboxD [d',g d]) n
somFis built around a
hyperGraphicsF, which outputs a
SelectionPtrwhenever the user selects a subexpression.
Adata Dir = Le | Ri type SelectionPtr = [Dir]
SelectionPtris a list of turns to take whenever an
Apnode is encountered in the
SOMtree, and points out a
selectnode. Using the function
somOutputin Figure 78,
somFcan get the output choices of a selected node.
somOutput :: h -> SOM i o h a -> SelectionPtr -> o somOutput h n p = case n of Select outf _ n -> case p of  -> outf h (somValue h n) _ -> somOutput h n p Ap f n -> case p of Le:p -> somOutput h f p Ri:p -> somOutput h n p Map _ n -> somOutput h n p Attr f n -> somOutput (fst (apAttr f h n)) n p Decor _ n -> somOutput h n p
Figure 78. The function
somF receives an input choice for the selected
node, the function
somInput (Figure 79) is
applied to the input and the selection pointer, to
get the modified
somInput :: h -> SOM i o h a -> i -> SelectionPtr -> Maybe (SelectionPtr,SOM i o h a) somInput h n i p = case n of Select o inf n -> case p of  -> myInput _ -> mapSOM (Select o inf) (somInput h n i p) ++ myInput where myInput = map (\n->(,n)) (inf h (somValue h n) i) Ap f n -> case p of  -> Nothing Le:p -> map (mapPair ((Le:),(`ap` n))) (somInput h f i p) Ri:p -> map (mapPair ((Ri:),(f `ap`))) (somInput h n i p) Map f n -> mapSOM (Map f) (somInput h n i p) Attr f n -> mapSOM (Attr f) (somInput (fst (apAttr f h n)) n i p) Leaf dr a -> Nothing Decor f n -> mapSOM (Decor f) (somInput h n i p) where mapSOM = map . apSnd mapPair f g (x,y) = (f x,g y)
Figure 79. The function
somInput also returns the pointer to the node whose
input function accepted the input, which is used by
somF to update the correct part of the drawing. If all input
functions ignore the input,
somInput use the
somValue, to get the current value of a
SOM expression, and the function
apAttr, to apply
attribute functions (Figure 80).
somValue :: h -> SOM i o h a -> a somValue h n = case n of Select _ _ n -> somValue h n Ap n1 n2 -> (somValue h n1) (somValue h n2) Map f n -> f (somValue h n) Leaf _ a -> a Attr f n -> snd (apAttr f h n) Decor _ n -> somValue h n apAttr :: (h -> a -> (h',a')) -> h -> SOM i o h' a -> (h',a') apAttr f h n = h'a' where h'a' = f h (somValue (fst h'a') n)
Figure 80. The functions
The recursive definition in
apAttr mirrors the fact
that attributes and values can have cyclic dependencies.
The implementation of
somF is shown in Figure 81,
and as mentioned previously, it is built around
hyperGraphicsF. The auxiliary functions
replaceDr are routing
functions that are typical when programming with
loopThroughRightF. The function
out is used when
outputting messages from
replaceDr are used when updating part of or the whole
of the drawing in the
hyperGraphicsF. (Compare with
the type of
hyperGraphicsF in Section 27.4.)
The controlling stream processor
ctrl has an internal
state which consists of the
SOM expression being
n), and a pointer to the selected node (
p). If there is no selected node,
Nothing. An incoming message to
ctrl is either a
click from the
hyperGraphicsF, indicating a new
selection by the user (handled by
click), an input
choice (handled by
input) or a new
expression (handled by
old selection cursor is removed, and a new node is
somF :: h -> SOM i o h a -> F (Either i (SOM i o h a)) (Either o a) somF h n = loopThroughRightF (absF (ctrl n Nothing)) (hyperGraphicsF (unselectedSomDr n)) where tohg = putSP . Left out = putSP . Right updateDr = tohg . Left . unselectedSomDr replaceDr = tohg . Right unselectedSomDr = somDrawing  ctrl n p = getSP $ click `either` (input `either` replace) where same = ctrl n p click p' = maybe id (deselect n) p $ selectO n p' $ ctrl n (Just p') input i = flip (maybe same) p $ \jp -> flip (maybe same) (somInput h n i jp) $ \(rp,n') -> replaceDr (rp,somDrawing rp n') $ selectO n' jp $ out (Right (somValue h n')) $ ctrl n' p replace n' = updateDr n' $ ctrl n' Nothing -- Select subnode and send its output. selectO n p = select n p . out (Left (somOutput h n p)) -- Draw cursor select = setselect cursor -- Remove cursor deselect = setselect id setselect cu n p = replaceDr (p,cu (somDrawing p n)) -- The cursor is a frame around the node cursor d = placedD overlayP (boxD [d,(g (frame' 1))]) -- Extract selected subdrawing somDrawing :: SelectionPtr -> SOM i o h a -> Dr
Figure 81. The function