Example of transformation on a simple evaluator (from the expression problem)

We show here an example of transformation on the Expression Problem. The source code is available in the download section.

The archive from the download section contains:

The view of the program which is modular with respect to functions;
the transformation to get a behavior equivalent program but modular with respect to data constructors;
the transformation to transform the data-centered architecture of the program into to the function-centered architecture .

Function-oriented view

module Expr  where
 
data Expr = 
    Const Int
  | Add (Expr,Expr)
 
e1 = Add (Add (Const 1,Const 2),Const 3)
e2 = Add (Add (Const 0,Const 1),Const 2)

module Client where 
 
import Expr
import ToStringMod
import EvalMod
 
r1 = print (toString e1)
r2 = print (show (eval e1))
r3 = print (toString e2)
r4 = print (show (eval e2))

module EvalMod where
 
import Expr 
 
eval (Const i) = i
eval (Add (e1,e2))= eval e1 + eval e2

module ToStringMod where
 
import Expr
 
toString (Const i) = show i
toString (Add (e1,e2)) = 
   (toString e1) ++ "+" ++ (toString e2)

module ConstMod () where

module AddMod () where

Data-oriented view

module Expr  where
 
data Expr = 
    Const Int
  | Add (Expr,Expr)
 
e1 = Add (Add (Const 1,Const 2),Const 3)
e2 = Add (Add (Const 0,Const 1),Const 2)

module Client where 
 
import Expr
import ToStringMod
import EvalMod
 
r1 = print (toString e1)
r2 = print (show (eval e1))
r3 = print (toString e2)
r4 = print (show (eval e2))

module EvalMod where
 
import Expr 
import ConstMod (eval)
import AddMod (eval)
 
eval x = EvalMod.fold1 AddMod.eval ConstMod.eval x
 
fold1 c a (Const i) = a i
 
fold1 c a (Add (e1,e2))= 
   c (((fold1 c) a) e1) (((fold1 c) a) e2)

module ToStringMod where
 
import Expr
import ConstMod (toString)
import AddMod (toString)
 
toString x
    = ToStringMod.fold2 AddMod.toString ConstMod.toString x
 
fold2 c a (Const i) = a i
 
fold2 c a (Add (e1,e2)) = 
   c (((fold2 c) a) e1) (((fold2 c) a) e2)

module ConstMod (toString,eval) where
 
 toString x = show x
 
 eval x = x

module AddMod (toString,eval) where
 
 toString x y = (x) ++ ("+" ++ (y))
 
 eval x y = (x) + (y)

Transformation scripts

Transformation function-centered architecture → data-centered architecture (this is an Emacs-Lisp script driving the Haskell Refactorer) :

(defvar f1        "eval"           )
(defvar f2        "toString"       )
(defvar c1        "Const"          )
(defvar c2        "Add"            )
(defvar f1mod     "EvalMod"        )
(defvar f2mod     "ToStringMod"    )
(defvar f1c1      (concat f1 c1)   )
(defvar f1c2      (concat f1 c2)   )
(defvar f2c1      (concat f2 c1)   )
(defvar f2c2      (concat f2 c2)   )
(defvar c1mod     (concat c1 "Mod"))
(defvar c2mod     (concat c2 "Mod"))
(defvar f1reducer "fold1"          )
(defvar f2reducer "fold2"          )
(defvar dummyc1   "c"              )
(defvar dummyc2   "a"              )
(defvar clientmod "Client"         )
 
;; set branches as local definitions (preliminary to exhibit business functions)
(haskell-refac-exhibitFunction f1 c1 f1c1 f1mod)
(haskell-refac-exhibitFunction f1 c2 f1c2 f1mod)
(haskell-refac-exhibitFunction f2 c1 f2c1 f2mod)
(haskell-refac-exhibitFunction f2 c2 f2c2 f2mod) 
 
;; abstract these definitions over local arguments to create business functions
(haskell-refac-generalise f1 c1 f1c1 f1mod "0" "x" "Curried" "OtherType")
(haskell-refac-generalise f2 c1 f2c1 f2mod "0" "x" "Curried" "OtherType")
(haskell-refac-generalise f2 c2 f2c2 f2mod "1" "y" "UnCurried" "RecType")
(haskell-refac-generalise f2 c2 f2c2 f2mod "0" "x" "UnCurried" "RecType")
(haskell-refac-generalise f1 c2 f1c2 f1mod "1" "y" "UnCurried" "RecType")
(haskell-refac-generalise f1 c2 f1c2 f1mod "0" "x" "UnCurried" "RecType") 
 
;; lift the business functions to the top-level
(haskell-refac-makeGlobalOfLocalIn f1 f1c1 f1mod)
(haskell-refac-makeGlobalOfLocalIn f1 f1c2 f1mod)
(haskell-refac-makeGlobalOfLocalIn f2 f2c1 f2mod)
(haskell-refac-makeGlobalOfLocalIn f2 f2c2 f2mod) 
 
;; abstract the functions of interest over the business functions 
(haskell-refac-generaliseIdent f1 f1mod f1c1 dummyc1)
(haskell-refac-generaliseIdent f1 f1mod f1c2 dummyc2)
(haskell-refac-generaliseIdent f2 f2mod f2c1 dummyc1)
(haskell-refac-generaliseIdent f2 f2mod f2c2 dummyc2) 
 
;; rename these functions of interest (they have become traversal functions)
(haskell-refac-renameToplevel f1 f1mod f1reducer)
(haskell-refac-renameToplevel f2 f2mod f2reducer) 
 
;; reconstruct the functions of interest as calls to the traversal functions
;; with appropriate arguments
(haskell-refac-newDefFunApp f1reducer "3" f1 clientmod)
(haskell-refac-newDefFunApp f2reducer "3" f2 clientmod) 
(haskell-refac-makeGlobalOfLocal f1 clientmod)
(haskell-refac-makeGlobalOfLocal f2 clientmod) 
(haskell-refac-generaliseIdent f1 clientmod "e1" "x") 
(haskell-refac-generaliseIdent f2 clientmod "e1" "x") 
 
(haskell-refac-foldToplevelDefinition f1 clientmod)
(haskell-refac-foldToplevelDefinition f2 clientmod)
 
(haskell-refac-moveDefBetweenModules f1 clientmod f1mod )
(haskell-refac-moveDefBetweenModules f2 clientmod f2mod ) 
 
(haskell-refac-unfoldInstanceIn (concat f1 "_gen") f1 f1mod)
(haskell-refac-unfoldInstanceIn (concat f1 "_gen_1") f1 f1mod)
(haskell-refac-unfoldInstanceIn (concat f2  "_gen") f2 f2mod)
(haskell-refac-unfoldInstanceIn (concat f2  "_gen_1") f2 f2mod) 
(haskell-refac-removeDefCmd (concat f1 "_gen") f1mod)
(haskell-refac-removeDefCmd (concat f1 "_gen_1") f1mod)
(haskell-refac-removeDefCmd (concat f2 "_gen") f2mod)
(haskell-refac-removeDefCmd (concat f2 "_gen_1") f2mod) 
 
;; move business functions to the appropriate modules
(haskell-refac-moveDefBetweenModules f1c1 f1mod c1mod)
(haskell-refac-moveDefBetweenModules f1c2 f1mod c2mod)
(haskell-refac-moveDefBetweenModules f2c1 f2mod c1mod)
(haskell-refac-moveDefBetweenModules f2c2 f2mod c2mod) 
 
;; rename the business functions to make them share the same name
(haskell-refac-renameToplevel f1c1 c1mod f1)
(haskell-refac-renameToplevel f1c2 c2mod f1)
(haskell-refac-renameToplevel f2c1 c1mod f2)
(haskell-refac-renameToplevel f2c2 c2mod f2)

Transformation data-centered view → function-centered view:

(defvar f1        "eval"           )
(defvar f2        "toString"       )
(defvar c1        "Const"          )
(defvar c2        "Add"            )
(defvar f1mod     "EvalMod"        )
(defvar f2mod     "ToStringMod"    )
(defvar f1c1      (concat f1 c1)   )
(defvar f1c2      (concat f1 c2)   )
(defvar f2c1      (concat f2 c1)   )
(defvar f2c2      (concat f2 c2)   )
(defvar c1mod     (concat c1 "Mod"))
(defvar c2mod     (concat c2 "Mod"))
(defvar f1reducer "fold1"          )
(defvar f2reducer "fold2"          )
(defvar dummyc1   "c"              )
(defvar dummyc2   "a"              )
(defvar clientmod "Client"         )
 
;; use specific names for business functions
(haskell-refac-renameToplevel f1 c1mod f1c1)
(haskell-refac-renameToplevel f1 c2mod f1c2)
(haskell-refac-renameToplevel f2 c1mod f2c1)
(haskell-refac-renameToplevel f2 c2mod f2c2)
 
;; prepare the generative fold operations :
;; the equations for functions of interest are saved into  comments
(haskell-refac-duplicateIntoComment f1 f1mod)
(haskell-refac-duplicateIntoComment f2 f2mod)
 
;; unfold the use of the traversal function
;; in the definition of functions of interest
(haskell-refac-unfoldInstanceIn f1reducer f1 f1mod)
(haskell-refac-unfoldInstanceIn f2reducer f2 f2mod)
 
;; fold the use of the traversal function in the body of the
;; functions of interest in order to find a recursive definition of them
;; (without a call to the traversal function)
(haskell-refac-generativeFold f1reducer "3" f1mod)
(haskell-refac-generativeFold f1reducer "3" f1mod)
(haskell-refac-generativeFold f2reducer "3" f2mod)
(haskell-refac-generativeFold f2reducer "3" f2mod)
 
;; comments introduced for the generative fold can be deleted
(haskell-refac-rmCommentBefore f1 f1mod)
(haskell-refac-rmCommentBefore f2 f2mod)
 
;; generative fold has produced case expressions that have
;; to be simplified
(haskell-refac-simplifyCasePattern f1 f1mod)
(haskell-refac-unfoldInstanceIn dummyc2 f1 f1mod)
(haskell-refac-removeLocalDef dummyc2 f1 f1mod)
 
(haskell-refac-simplifyCasePattern f1 f1mod)
(haskell-refac-unfoldInstanceIn dummyc1 f1 f1mod)
(haskell-refac-removeLocalDef dummyc1 f1 f1mod)
 
(haskell-refac-simplifyCasePattern f2 f2mod)
(haskell-refac-unfoldInstanceIn dummyc2 f2 f2mod)
(haskell-refac-removeLocalDef dummyc2 f2 f2mod)
 
(haskell-refac-simplifyCasePattern f2 f2mod)
(haskell-refac-unfoldInstanceIn dummyc1 f2 f2mod)
(haskell-refac-removeLocalDef dummyc1 f2 f2mod)
 
;; the case expressions introduced by the generative fold 
;; have to be transformed into equations
(haskell-refac-caseToEq f1 f1mod)
(haskell-refac-caseToEq f2 f2mod)
 
;; replace calls to the business functions by their bodies (unfold)
(haskell-refac-unfoldInstanceIn f1c1 f1 f1mod)
(haskell-refac-unfoldInstanceIn f1c2 f1 f1mod)
(haskell-refac-unfoldInstanceIn f2c1 f2 f2mod)
(haskell-refac-unfoldInstanceIn f2c2 f2 f2mod)
 
;; business functions are not used an can be deleted 
;; (imports, exports and declarations)
(haskell-refac-cleanImportsCmd f1mod) ;; useless but not costly
(haskell-refac-cleanImportsCmd f2mod) ;; useless
 
(haskell-refac-rmFromExports f1c1 c1mod)
(haskell-refac-rmFromExports f2c1 c1mod)
(haskell-refac-rmFromExports f1c2 c2mod)
(haskell-refac-rmFromExports f2c2 c2mod)
 
(haskell-refac-removeDefCmd f1c1 c1mod)
(haskell-refac-removeDefCmd f1c2 c2mod)
(haskell-refac-removeDefCmd f2c1 c1mod)
(haskell-refac-removeDefCmd f2c2 c2mod)
 
;; the traversal functions can be deleted
(haskell-refac-removeDefCmd f1reducer f1mod)
(haskell-refac-removeDefCmd f2reducer f2mod)

Demonstration (video)

In the following video demonstration, we consider we have to modify the behavior of each function on the addition data constructor but the architecture is function-oriented. We first switch in the view where the evolution is modular, then we implement the evolution, and finally we go back to the first view. Of course, the result of the evolution is visible in the first view.

Fullscreen tip: if the video doesn't display when you switch in fullscreen (Ubuntu), try to desactivate the hardware acceleration with a right-click in the video.

internet/view_switcher/examples/expression_problem.txt · Last modified: 2011/04/18 08:30 by cohen-j