diff options
| -rw-r--r-- | bruijn.cabal | 4 | ||||
| -rw-r--r-- | docs/index.html | 2 | ||||
| -rw-r--r-- | package.yaml | 1 | ||||
| -rw-r--r-- | samples/readme.md | 2 | ||||
| -rw-r--r-- | src/Reducer.hs | 23 |
5 files changed, 15 insertions, 17 deletions
diff --git a/bruijn.cabal b/bruijn.cabal index b3e4bf1..c57167a 100644 --- a/bruijn.cabal +++ b/bruijn.cabal @@ -1,6 +1,6 @@ cabal-version: 1.12 --- This file has been generated from package.yaml by hpack version 0.34.4. +-- This file has been generated from package.yaml by hpack version 0.35.1. -- -- see: https://github.com/sol/hpack @@ -55,7 +55,7 @@ library src default-extensions: LambdaCase - ghc-options: -Wall -Wextra -Wincomplete-uni-patterns -Wincomplete-record-updates -Widentities -Wredundant-constraints + ghc-options: -O3 -Wall -Wextra -Wincomplete-uni-patterns -Wincomplete-record-updates -Widentities -Wredundant-constraints build-depends: array , base >=4.7 && <5 diff --git a/docs/index.html b/docs/index.html index 97dc25e..1d0306f 100644 --- a/docs/index.html +++ b/docs/index.html @@ -46,7 +46,7 @@ <div class="example"> <pre class="code"> <span class="repl">></span> <span class="com">:time</span> <span class="symbol">factorial</span> <span class="ternary">(+30)</span> -<span class="time">0.35 seconds</span></pre> +<span class="time">0.15 seconds</span></pre> <p> Efficient call-by-need reduction using abstract machines. </p> diff --git a/package.yaml b/package.yaml index 3320244..6c7bfc8 100644 --- a/package.yaml +++ b/package.yaml @@ -45,6 +45,7 @@ dependencies: library: source-dirs: src ghc-options: + - -O3 - -Wall - -Wextra - -Wincomplete-uni-patterns diff --git a/samples/readme.md b/samples/readme.md index 8ffda4d..68b31c1 100644 --- a/samples/readme.md +++ b/samples/readme.md @@ -9,4 +9,4 @@ Code](https://adventofcode.com) problems. **Be aware** that lambda calculus is generally incredibly inefficient. For example, the obvious solution for the very simple problem 2022/01 -takes around 60s and 4GB of memory using the full input. +takes around 30s and 3GB of memory using the full input. diff --git a/src/Reducer.hs b/src/Reducer.hs index 8823b3c..d9ca557 100644 --- a/src/Reducer.hs +++ b/src/Reducer.hs @@ -9,8 +9,7 @@ import Data.List ( elemIndex ) import Data.Map ( Map ) import qualified Data.Map as Map import Helper -import System.IO.Unsafe ( unsafePerformIO ) -import System.Random ( randomIO ) +import System.Random hiding ( next ) type Store = Map Int Box type Stack = [Redex] @@ -21,22 +20,20 @@ data Rvar = Num Int | Hole data Redex = Rabs Int Redex | Rapp Redex Redex | Rvar Rvar | Rclosure Redex Store | Rcache Box Redex data Conf = Econf Redex Store Stack | Cconf Stack Redex | End --- TODO: unsafePerformIO is very unpure and ugly!! Unfortunately IO seems to --- make this function and therefore the entire reduction strict :/ toRedex :: Expression -> Redex -toRedex = convertWorker [] +toRedex = convertWorker (mkStdGen 42) [] where - convertWorker ns (Abstraction e) = - let v = unsafePerformIO randomIO :: Int - t = convertWorker (v : ns) e + convertWorker g ns (Abstraction e) = + let (v, g') = uniform g :: (Int, StdGen) + t = convertWorker g' (v : ns) e in Rabs v t - convertWorker ns (Application l r) = - let lhs = convertWorker ns l - rhs = convertWorker ns r + convertWorker g ns (Application l r) = + let lhs = convertWorker g ns l + rhs = convertWorker g ns r in Rapp lhs rhs - convertWorker ns (Bruijn i) = + convertWorker _ ns (Bruijn i) = Rvar $ Num (if i < 0 || i >= length ns then i else ns !! i) - convertWorker _ _ = invalidProgramState + convertWorker _ _ _ = invalidProgramState fromRedex :: Redex -> Expression fromRedex = convertWorker [] |