Minimal scoping pass that uniquely renames variables and supports shadowing

scope.hs

import qualified Data.Map as Map
import qualified Control.Monad.State as State

data NamedExpr = 
  NamedLet String Int | -- let x = 1
  NamedBlock NamedStatements | -- { ... }
  NamedPrint String -- print(x)
  
type NamedStatements = [NamedExpr]

data NumberedExpr =
  NumberedLet Int Int | -- let _0 = 1
  NumberedBlock NumberedStatements | -- { ... }
  NumberedPrint Int -- print(_0)
  deriving Show
  
type NumberedStatements = [NumberedExpr]

data Result = Result {
  expr :: NumberedStatements,
  numToName :: Map.Map Int String
} deriving Show

scopifyHelper :: NamedStatements -> (Map.Map String Int) -> State.State Int Result
scopifyHelper [] _ = do
  pure Result { expr = [], numToName = Map.empty }

scopifyHelper (stat:stats) nameToNum = case stat of
  (NamedLet varName value) -> do
    i <- State.get
    let nameToNum' = Map.insert varName i nameToNum
    State.put (i + 1)
    
    result <- scopifyHelper stats nameToNum'
    let result' = Result {
      expr = NumberedLet i value : expr result,
      numToName = Map.insert i varName (numToName result)
    }

    pure result'

  (NamedBlock blockStats) -> do
    blockResult <- scopifyHelper blockStats nameToNum
  
    -- This is the key part of the algo,
    --`nameToNum` is the same after the block as it is before
    result <- scopifyHelper stats nameToNum
    let result' = Result {
      expr = NumberedBlock (expr blockResult) : expr result,
      numToName = Map.union (numToName blockResult) (numToName result)
    }
  
    pure result'

  (NamedPrint varName) -> do
    result <- scopifyHelper stats nameToNum
  
    -- Real code should check if the variable is defined
    let i = Map.findWithDefault (-1) varName nameToNum
    pure result { expr = NumberedPrint i : expr result }

scopify :: NamedStatements -> Result
scopify expr = State.evalState (scopifyHelper expr Map.empty) 0

input :: NamedStatements
input = [
  NamedLet "x" 3,
  NamedBlock [
    NamedLet "x" 4,
    NamedPrint "x"],
  NamedPrint "x"]

main :: IO ()
main = putStrLn $ show $ scopify input