diff options
| -rw-r--r-- | app/Main.hs | 4 | ||||
| -rw-r--r-- | jottary.cabal (renamed from jotter.cabal) | 18 | ||||
| -rw-r--r-- | package.yaml | 10 | ||||
| -rw-r--r-- | readme.md | 45 | ||||
| -rw-r--r-- | src/Lib.hs | 39 |
5 files changed, 53 insertions, 63 deletions
diff --git a/app/Main.hs b/app/Main.hs index 7a8bffa..c1f1c2d 100644 --- a/app/Main.hs +++ b/app/Main.hs @@ -11,7 +11,7 @@ import Term reduce :: String -> IO () reduce path = do file <- readFile path - let termified = fromJotter file + let termified = fromJottary file putStrLn $ "input: " ++ show termified normal <- nf termified putStrLn $ "reduced: " ++ show normal @@ -21,4 +21,4 @@ main = do args <- getArgs case args of ["reduce", path] -> reduce path - _ -> putStrLn "Usage: jotter [transpile|reduce] <file>" + _ -> putStrLn "Usage: jottary [transpile|reduce] <file>" diff --git a/jotter.cabal b/jottary.cabal index c61e73d..c633640 100644 --- a/jotter.cabal +++ b/jottary.cabal @@ -4,11 +4,11 @@ cabal-version: 1.12 -- -- see: https://github.com/sol/hpack -name: jotter +name: jottary version: 0.1.0.0 -description: Please see the README on GitHub at <https://github.com/githubuser/jotter#readme> -homepage: https://github.com/marvinborner/jotter#readme -bug-reports: https://github.com/marvinborner/jotter/issues +description: Please see the README on GitHub at <https://github.com/githubuser/jottary#readme> +homepage: https://github.com/marvinborner/jottary#readme +bug-reports: https://github.com/marvinborner/jottary/issues author: Marvin Borner maintainer: git@marvinborner.de copyright: 2023 Marvin Borner @@ -19,7 +19,7 @@ extra-source-files: source-repository head type: git - location: https://github.com/marvinborner/jotter + location: https://github.com/marvinborner/jottary library exposed-modules: @@ -27,7 +27,7 @@ library Term Utils other-modules: - Paths_jotter + Paths_jottary hs-source-dirs: src ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints @@ -37,10 +37,10 @@ library , containers default-language: Haskell2010 -executable jotter +executable jottary main-is: Main.hs other-modules: - Paths_jotter + Paths_jottary hs-source-dirs: app ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints -threaded -rtsopts -with-rtsopts=-N -O3 -fllvm @@ -48,5 +48,5 @@ executable jotter async , base >=4.7 && <5 , containers - , jotter + , jottary default-language: Haskell2010 diff --git a/package.yaml b/package.yaml index 03236d2..31b7235 100644 --- a/package.yaml +++ b/package.yaml @@ -1,6 +1,6 @@ -name: jotter +name: jottary version: 0.1.0.0 -github: "marvinborner/jotter" +github: "marvinborner/jottary" license: MIT author: "Marvin Borner" maintainer: "git@marvinborner.de" @@ -16,7 +16,7 @@ extra-source-files: # To avoid duplicated efforts in documentation and dealing with the # complications of embedding Haddock markup inside cabal files, it is # common to point users to the README.md file. -description: Please see the README on GitHub at <https://github.com/githubuser/jotter#readme> +description: Please see the README on GitHub at <https://github.com/githubuser/jottary#readme> dependencies: - base >= 4.7 && < 5 @@ -38,7 +38,7 @@ library: source-dirs: src executables: - jotter: + jottary: main: Main.hs source-dirs: app ghc-options: @@ -48,4 +48,4 @@ executables: - -O3 - -fllvm dependencies: - - jotter + - jottary @@ -1,34 +1,27 @@ -# Jotter +# Jottary -Jotter (pronounced /dʒɑt.ər/) is a Turing tarpit and an even better -Gödel-numbering than its sister language +Jottary (pronounced /dʒɑteri/) is a unary Turing tarpit and an even +better Gödel-numbering than its sister language [Jot](https://esolangs.org/wiki/Jot). -## Semantics of Jotter +Read my [blog post](https://text.marvinborner.de/2023-10-05-15.html) for +more information. - [] -> I - [F0]ₗ -> (S[F]ᵣ) - [F0]ᵣ -> ([F]ₗS) - [F1]ₗ -> (K[F]ᵣ) - [F1]ᵣ -> ([F]ₗK) +## Performance -`[F]` converts the Jotter program `F` to combinatory logic. The -associativity toggles between left and right (denoted by `ₗ/ᵣ`). +The [bruijn +implementation](https://github.com/marvinborner/bruijn/blob/main/samples/fun/jottary.bruijn): -The starting state depends on the length of the program: `ₗ` if -`len % 2 == 0` (even) and `ᵣ` if `len % 2 == 1` (odd). Don’t worry, this -only forces the core (the empty string, `I`) to always be on the left -side of the application. +``` bash +$ hyperfine "printf '1%.0s' {1..503} | bruijn -y jottary.bruijn" + Time (mean ± σ): 756.4 ms ± 35.2 ms [User: 1816.9 ms, System: 1735.2 ms] + Range (min … max): 706.9 ms … 808.2 ms 10 runs +``` -## Jot vs. Jotter +This implementation: -Jotter has exactly the same (regular) syntax as Jot, including support -for the null program. - -Every Jot program can easily be translated to Jotter: - - [] -> -> I - [F0] -> [F]01 -> ([F]S) - [F1] -> ??? - -Therefore Jotter is *Turing-complete*. +``` bash +$ hyperfine "jottary reduce <(printf '1%.0s' {1..503})" + Time (mean ± σ): 10.8 ms ± 0.7 ms [User: 1.7 ms, System: 9.0 ms] + Range (min … max): 9.5 ms … 12.5 ms 163 runs +``` @@ -1,13 +1,15 @@ {-# LANGUAGE LambdaCase #-} module Lib - ( fromJotter + ( fromJottary + , s + , k + , i ) where +import Control.Monad ( replicateM ) +import Debug.Trace ( trace ) import Term -import Utils - -data State = L | R s :: Term s = Abs (Abs (Abs (App (App (Idx 2) (Idx 0)) (App (Idx 1) (Idx 0))))) @@ -18,22 +20,17 @@ k = Abs (Abs (Idx 1)) i :: Term i = Abs (Idx 0) -clean :: String -> String -clean (x : xs) | x == '0' || x == '1' = x : clean xs - | otherwise = clean xs -clean [] = [] +count :: String -> Int +count (x : xs) | x == '1' = 1 + count xs + | otherwise = count xs +count [] = 0 --- reverse wouldn't be needed if [0F] instead of [F0] -fromCleanJotter :: String -> Term -fromCleanJotter t | even $ length t = go L $ reverse t - | otherwise = go R $ reverse t +fromDecimalJottary :: Int -> Term +fromDecimalJottary p = foldr1 App (reverse (gen !! p) ++ [i]) where - go L ('0' : xs) = App s (go R xs) - go R ('0' : xs) = App (go L xs) s - go L ('1' : xs) = App k (go R xs) - go R ('1' : xs) = App (go L xs) k - go _ [] = i - go _ _ = invalid - -fromJotter :: String -> Term -fromJotter = fromCleanJotter . clean + lio = Abs (App (App (Idx 0) s) k) + rio = Abs (App s (App k (Idx 0))) + gen = [0 ..] >>= (`replicateM` [lio, rio]) + +fromJottary :: String -> Term +fromJottary t = trace (show $ count t) (fromDecimalJottary $ count t) |