{-
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