gulcii-0.3: src/GC.hs

{-
    gulcii -- graphical untyped lambda calculus interpreter
    Copyright (C) 2011, 2013, 2017  Claude Heiland-Allen

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-}

module GC (gc) where

import Graph

import Data.Map as Map

gc
  :: References -> Term
  -> (References, Term)

gc refs term
  = let counts = refCount refs term Map.empty
    in ( Map.fromList
           [ (r, compact counts refs (refs Map.! r))
           | (r, n) <- Map.toList counts
           , n > 1 ]
        , compact counts refs term )


type Count = Integer

refCount
  :: References -> Term
  -> Map Integer Count -> Map Integer Count

compact
  :: Map Integer Count -> References
  -> Term -> Term


refCount refs (Scope a) counts
  = refCount refs a counts

refCount refs (Lambda _ a) counts
  = refCount refs a counts

refCount refs (Apply a b) counts
  = refCount refs a (refCount refs b counts)

refCount refs (Reference r) counts
  = case r `Map.lookup` counts of
      Just n ->
        Map.insert r (n + 1) counts
      Nothing ->
        refCount refs (refs Map.! r)
               (Map.insert r 1 counts)

refCount _ _ counts = counts


compact counts refs (Scope term)
  = Scope (compact counts refs term)

compact counts refs (Lambda strat term)
  = Lambda strat (compact counts refs term)

compact counts refs (Apply a b)
  = Apply (compact counts refs a)
          (compact counts refs b)

compact counts refs term@(Reference r)
  = case r `Map.lookup` counts of
      Just 1 -> compact counts refs (refs Map.! r)
      _ -> term

compact _ _ term = term