# Is this A-normal shape a realistic linear in size AST?

The essence of compilation with sequels Flanagan et.al. describe a linear time algorithm for converting a term to A-normal form . In short, A-normal form has all applications that only accept trivial arguments (like variables), and all non-trivial members must be concatenated.

Here's a (stupid) example of A-normal form:

``````let x0 = x0 in
let x2 = \ x1 -> x1 in
let x3 = 1 in
x2 x3
```

```

created from this non-normal member of the form:

``````let y = y in
(\ x0 -> x0) 1
```

```

I translated the schema code at the end of the article (page 11) into a lower Haskell module. However, I introduced monads to give me a source of fresh names and keep the display of renamed variables. My question is, does using monads destroy O (n) execution time of an algorithm in a document? I'm particularly worried about nesting `>>=`

, which for some monads results in O (n ^ 2) behavior.

``````-- Based on http://slang.soe.ucsc.edu/cormac/papers/pldi93.pdf
import Control.Applicative
import qualified Data.Map.Strict as M

type Name = String
data Term = Var Name
| Lam Name Term
| App Term Term
| Let Name Term Term
| Lit Int
deriving Show

type NameSupply a = ReaderT (M.Map Name Name) (State [Name]) a

fresh :: NameSupply String
fresh = do
(name:rest) <- get
put rest
return name

normalizeTerm :: Term -> NameSupply Term
normalizeTerm m = normalize m return

normalize :: Term -> (Term -> NameSupply Term) -> NameSupply Term
normalize m k = case m of
Var x       -> do
case mx' of
Just x' -> k (Var x')
Lam x body  -> do
x' <- fresh
k =<< (Lam x' <\$> local (M.insert x x') (normalizeTerm body))
Let x m1 m2 -> do
x' <- fresh
local (M.insert x x') \$ normalize m1 (\ n1 -> Let x' n1 <\$>  (normalize m2 k))
App m1 m2   -> normalizeName m1 (\ n1 -> normalizeName m2 (k . App n1))
(Lit _)     -> k m

normalizeName :: Term -> (Term -> NameSupply Term) -> NameSupply Term
normalizeName m k = normalize m \$ \ n -> do
x <- fresh
Let x n <\$> k (Var x)

run :: Term -> Term
run = flip evalState names . flip runReaderT M.empty . normalizeTerm
where names = (map (("x" ++) . show) [0..])

example :: Term
example = Let "y" (Var "y") (App (Lam "x0" (Var "x0")) (Lit 1))
```

```
+3

source to share

Your monad is simple `ReaderT ... (State ...)`

and both `ReaderT`

and `State`

are passing single values ​​around, so there is no reason to wait for linear time `(>>=)`

or for an O (n) chain to take O (n ^ 2) time.

You can get left-nested quadratic blow-ups when the monad uses lists or sets or similar.

+2

source

All Articles