tag:blogger.com,1999:blog-68142360172663580192024-03-05T00:20:00.496-08:00A Free EducationTHKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comBlogger71125tag:blogger.com,1999:blog-6814236017266358019.post-49324405674596758992021-01-20T22:01:00.004-08:002021-01-20T22:01:44.023-08:00Moving to Github Pages<p> To facilitate writing posts in my usual text editor, in markdown (finally, proper and painless code highlighting!), future content will be posted on Github Pages at <a href="https://tkuriyama.github.io/">https://tkuriyama.github.io/</a></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-77248051379366769382020-11-13T11:40:00.001-08:002020-11-13T11:50:05.791-08:00Elm Codegen Quirks with Servant-Elm and Persistent<p>Developing further on the <a href="https://learning.tarokuriyama.com/2020/11/hello-server-persistent.html">previous post,</a> building some slightly less trivial examples with the combination of <i>servant-elm</i> and <i>persistent </i>(with Sqlite backend) yields some interesting problems in the generated Elm code. </p><p><b>1. Phantom Types for Keys</b></p><p>Due to the way <a href="https://www.yesodweb.com/book/persistent#persistent_closer_look_at_types"><i>persistent </i>handles database primary keys</a>, <i>servant-elm </i>(via the underlying <i>elm-bridge</i>) currently generates Elm code with types such as <i>Key World</i> instead of <i>WorldId</i>, where, for Sqlite, ID variables are of type <i>Int, </i>used for database primary keys. </p><p>But what is <i>Key World </i>in terms of Elm types? And what happens when you try to sequence a JSON encoder / decoder for <i>Key </i>(which doesn't exist!), along with a JSON encoder / ecoder for <i>World -- </i>something altogether different from the desired <i>Int</i>? </p><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;">type alias User =<br /></span><span style="font-family: courier; font-size: x-small;"> <span data-darkreader-inline-bgcolor="" style="--darkreader-inline-bgcolor: #5eb33a; background-color: #04ff00;">{ userEnv: (Key World)</span><br /></span><span style="font-family: courier; font-size: x-small;"> , userName: String<br /></span><span style="font-family: courier; font-size: x-small;"><br /><span> </span>[...]<br /></span><span style="font-family: courier; font-size: x-small;"><br /></span><span style="font-family: courier; font-size: x-small;">jsonEncUser : User -> Value<br /></span><span style="font-family: courier; font-size: x-small;">jsonEncUser val =<br /></span><span style="font-family: courier; font-size: x-small;"> Json.Encode.object<br /></span><span style="font-family: courier; font-size: x-small;"> <span data-darkreader-inline-bgcolor="" style="--darkreader-inline-bgcolor: #5eb33a; background-color: #04ff00;">[ ("userEnv", (jsonEncKey (jsonEncWorld)) val.userEnv)</span><br /></span><span style="font-family: courier; font-size: x-small;"> , ("userName", Json.Encode.string val.userName)<br /></span><span style="font-family: courier; font-size: x-small;"> </span></div><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"><span> </span>[...]</span></div><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"><br /></span></div><div><br /></div><div>There's some discussion of <a href="https://github.com/agrafix/elm-bridge/issues/35">handling phantom types </a>in <i>elm-bridge</i>, as well as some existing support for custom type replacements in the <a href="https://hackage.haskell.org/package/elm-bridge-0.6.1/docs/Elm-Module.html"><i>elm-bridge </i>library</a><i>. </i>To get it working, I ended up needing the custom type replacements, as well as some direct manipulation of the generated Elm code. (I also found some fairly extensive <a href="https://gitlab.com/k-bx/meetup/-/blob/master/backend/meetup/src/Le/GenerateElm.hs">replacement ideas here</a>).</div><div><br /></div><div>The <i>elm-bridge </i>replacements are defined here: <a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/make/Make/Spacemonkey.hs">https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/make/Make/Spacemonkey.hs</a></div><div><br /></div><div>That takes care of the instances of <i>Key World</i> and the like in Elm type definitions, but not in the API call functions, and also introduces a new problem of missing definitions for <i>Id</i> type encoders/decoders. </div><div><br /></div><div><div><span style="font-family: courier; font-size: x-small;">type alias User =</span></div><div><span style="font-family: courier; font-size: x-small;"> <span data-darkreader-inline-bgcolor="" style="--darkreader-inline-bgcolor: #5eb33a; background-color: #04ff00;">{ userEnv: WorldId</span></span></div><div><span style="font-family: courier; font-size: x-small;"> , userName: String</span></div><div><span style="font-family: courier; font-size: x-small;"> [...]</span></div><div><span style="font-family: courier; font-size: x-small;"><br /></span></div><div><span style="font-family: courier; font-size: x-small;">jsonEncUser : User -> Value</span></div><div><span style="font-family: courier; font-size: x-small;">jsonEncUser val =</span></div><div><span style="font-family: courier; font-size: x-small;"> Json.Encode.object</span></div><div><span style="font-family: courier; font-size: x-small;"> <span data-darkreader-inline-bgcolor="" style="--darkreader-inline-bgcolor: #5eb33a; background-color: #04ff00;">[ ("userEnv", jsonEncWorldId val.userEnv)</span></span></div><div><span style="font-family: courier; font-size: x-small;"> , ("userName", Json.Encode.string val.userName)</span></div><div><span style="font-family: courier; font-size: x-small;"> [...]</span></div><div><span style="font-family: courier; font-size: x-small;"><br /></span></div><div><span style="font-family: courier; font-size: x-small;">getWorldByWid : (<span data-darkreader-inline-bgcolor="" style="--darkreader-inline-bgcolor: #5eb33a; background-color: #04ff00;">Key World</span>) -> (Result Http.Error ((Maybe World)) -> msg) -> Cmd msg</span></div><div><span style="font-family: courier; font-size: x-small;">getWorldByWid capture_wid toMsg =</span></div><div><span style="font-family: courier; font-size: x-small;"> [...]</span></div></div><div><br /></div><div>There may be some way to do replacements in a more integral way with the Template Haskell codegen, but I ended up just doing appends and naive text replacements on the final Elm output: <a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/scripts/PostCodeGen.hs">https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/scripts/PostCodeGen.hs</a></div><div><br /></div><div><br /></div><p><b>2. Missing URL String Encoders</b></p><p>I also couldn't get <i>servant-elm</i> to generate correct URL string encoders, despite defining instances of <i>toHttpApiData, </i>which seems like it <a href="https://docs.servant.dev/en/stable/tutorial/Server.html#the-fromhttpapidata-tohttpapidata-classes">should be the thing to do</a>. </p><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"> </span></div><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"><span> </span><span> </span>Http.request<br /></span><span style="font-family: courier; font-size: x-small;"> [...]</span><span style="font-family: courier; font-size: x-small;"><br /></span><span style="font-family: courier; font-size: x-small;"> , url =<br /></span><span style="font-family: courier; font-size: x-small;"> Url.Builder.crossOrigin "http://localhost:8080"<br /></span><span style="font-family: courier; font-size: x-small;"> [ "cellColor"<br /></span><span style="font-family: courier; font-size: x-small;"> , (capture_worldid |> String.fromInt)<br /></span><span style="font-family: courier; font-size: x-small;"> , (capture_x |> String.fromInt)<br /></span><span style="font-family: courier; font-size: x-small;"> , (capture_y |> String.fromInt)<br /></span><span style="font-family: courier; font-size: x-small;"> <span data-darkreader-inline-bgcolor="" style="--darkreader-inline-bgcolor: #5eb33a; background-color: #04ff00;">, (capture_color |> String.fromInt)</span><br /></span><span style="font-family: courier; font-size: x-small;"> ]<br /></span><span style="font-family: courier; font-size: x-small;"> [...</span></div><p><span style="font-family: courier; font-size: x-small;"><i></i></span></p><p>... where <i>Color </i>is defined on the Haskell side as:</p><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;">data Color<br /></span><span style="font-family: courier; font-size: x-small;"> = White<br /></span><span style="font-family: courier; font-size: x-small;"> | Yellow<br /></span><span style="font-family: courier; font-size: x-small;"> | Red<br /></span><span style="font-family: courier; font-size: x-small;"> | Green<br /></span><span style="font-family: courier; font-size: x-small;"> | Blue<br /></span><span style="font-family: courier; font-size: x-small;"> | Grey<br /></span><span style="font-family: courier; font-size: x-small;"> deriving (Show, Read, Eq, Generic, Enum, Bounded)</span></div><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"><br /></span><span style="font-family: courier; font-size: x-small;">instance FromHttpApiData Color where<br /></span><span style="font-family: courier; font-size: x-small;"> parseUrlPiece :: T.Text -> Either T.Text Color<br /></span><span style="font-family: courier; font-size: x-small;"> parseUrlPiece = myParse</span></div><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"><br /></span><span style="font-family: courier; font-size: x-small;">instance ToHttpApiData Color where<br /></span><span style="font-family: courier; font-size: x-small;"> toUrlPiece = T.pack . show<br /></span><span style="font-family: courier; font-size: x-small;"> toQueryParam = T.pack . show</span></div><p style="text-align: left;"></p><div style="text-align: left;">So for each sum type instance, the <a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/scripts/PostCodeGen.hs">post-code-gen script</a> from above also takes care of the string encoders for use in URL building, appending the functions to the generated Elm code.</div><div style="text-align: left;"><br /></div><div style="text-align: left;"> </div><p><b>Wrapping Up</b></p><p>With the above edits, the Elm code gen + persistence layer stack works again. There was a lot more research and work(arounds) required this time, and I needed some help from friends at the Recurse Center, but it still (mostly!) satisfies the property of writing data definitions only once for the whole stack. It's not hard to see that some of the type mapping issues across languages and data boundaries are non-trivial to resolve, so I hope more usage and development goes into these kinds of type-safe stacks. </p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-68763392146374265092020-11-09T12:50:00.002-08:002020-11-13T10:21:17.787-08:00Hello Server + Persistent<p> The<a href="https://learning.tarokuriyama.com/2020/11/hello-server-acid-state.html"> previous post</a> covered setting up a Servant server in Haskell, with automatic codegen for Elm bindings and using the <i><a href="https://hackage.haskell.org/package/acid-state">acid-state</a></i> package for persistence. </p><p>An obvious benefit of the stack is that one only ever needs to think in native Haskell data structures. It's relatively easy to use and achieves the goal of minimizing work across data boundaries (in this case, between the server and persistence layer). It's also self-contained, insofar as it doesn't require an external database server / process / engine.</p><p>On the other hand... many external database servers have been developed and refined for years -- if not decades -- yielding stability, tools, and all sorts of best practices and optimizations. </p><p><a href="https://www.yesodweb.com/book/persistent">Yesod's answer to the problem is persistent,</a> which provides a type-safe and unified way to interact with a variety of database backends (primarily Sqlite, MySQL, Postgres, and MongoDB). Although <a href="https://hackage.haskell.org/package/persistent">the library </a>was designed for Yesod, it is not tightly coupled and seems to work for Servant.</p><p><a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/src/Modules/HelloServerPersist.hs">This file</a> contains the data definitions for a revised version of Hello Server. <i>persist</i> also uses Template Haskell, so we adapt the data declarations accordingly:</p><table class="highlight tab-size js-file-line-container" data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" data-paste-markdown-skip="" data-tab-size="8" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #c4bfb6; background-color: white; border-collapse: collapse; border-spacing: 0px; color: #24292e; font-family: -apple-system, system-ui, "Segoe UI", Helvetica, Arial, sans-serif, "Apple Color Emoji", "Segoe UI Emoji"; font-size: 14px; tab-size: 8;"><tbody style="box-sizing: border-box;"><tr style="box-sizing: border-box;"><td class="blob-code blob-code-inner js-file-line" id="LC20" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;">share</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="21" id="L21" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC21" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> [mkPersist sqlSettings , mkMigrate <span class="pl-s" data-darkreader-inline-color="" style="--darkreader-inline-color: #bfb9b0; box-sizing: border-box; color: #032f62;"><span class="pl-pds" style="box-sizing: border-box;">"</span>migrateAll<span class="pl-pds" style="box-sizing: border-box;">"</span></span>]</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="22" id="L22" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC22" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> [<span class="pl-ent" data-darkreader-inline-color="" style="--darkreader-inline-color: #90c797; box-sizing: border-box; color: #22863a;">persistLowerCase</span>|</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="23" id="L23" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC23" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> ServerState</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="24" id="L24" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC24" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> state String</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="25" id="L25" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC25" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> counter Int</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="26" id="L26" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC26" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> deriving Eq Show Generic</td></tr><tr style="box-sizing: border-box;"><td class="blob-num js-line-number" data-line-number="27" id="L27" style="box-sizing: border-box; color: var(--color-diff-blob-num-text); cursor: pointer; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; min-width: 50px; padding: 0px 10px; text-align: right; user-select: none; vertical-align: top; white-space: nowrap; width: 50px;"></td><td class="blob-code blob-code-inner js-file-line" id="LC27" style="box-sizing: border-box; color: var(--color-text-primary); font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; line-height: 20px; overflow-wrap: normal; overflow: visible; padding: 0px 10px; position: relative; vertical-align: top; white-space: pre;"> |]</td></tr></tbody></table><p>Note that the <i>servant-elm</i> template invocations come later and works as expected -- i.e. first, <i>persistent</i> generates the <i>ServerState </i>data type and associate code it needs; then, <i>servant-elm</i> uses the generated <i>ServerState</i> data type for its purposes. </p><p><a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/server/Server/HelloServerPersist.hs">This file</a> contains the server instance, following the <a href="https://github.com/haskell-servant/example-servant-persistent">example</a> in the Servant repo. </p><p>And, with a few small changes on the <a href="https://github.com/tkuriyama/spacemonkey/blob/master/client/src/Modules/HelloServerPersist.elm">Elm client side</a> to accommodate API tweaks, it works!</p><p>There are a number of fundamental things I still haven't figured out (like... shouldn't the Sqlite connection pool be explicitly closed in the bracket pattern?). Overall, there are more things to think about compared to working with <i>acid-state -- </i>which seems reasonabl, since it corresponds to the relative power of the database engine (or at least, I assume so). Leveraging the "migrations" feature from <i>persistent</i>, though, I've still only written a single data definition in Haskell for the entire stack!</p><p>The repo with all examples: <a href="https://github.com/tkuriyama/spacemonkey">https://github.com/tkuriyama/spacemonkey</a></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-58860446937071828802020-11-05T16:51:00.003-08:002020-11-05T16:54:09.587-08:00Hello Server + Acid-State<p> The <a href="https://learning.tarokuriyama.com/2020/11/haskell-elm-across-data-boundaries.html">previous post</a> covered defining a Servant server with automatic code generation for Elm bindings.</p><p>Are there libraries that allow for type-safe persistence in Haskell?</p><p>Again referring to the <a href="https://github.com/Gabriel439/post-rfc/blob/master/sotu.md">state of the Haskell ecosystem</a>, one interesting library is <i><a href="https://github.com/acid-state/acid-state">acid-state</a></i>, which provides ACID guarantees for de/serializing (serializable) Haskell data structures directly, with no external DBMS.</p><p><i>acid-state </i>also uses Template Haskell, and it's <a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/src/Modules/HelloServerAcid.hs">relatively straightforward</a> to augment the prior Hello Server data definitions. We define some simple operations we want (query, write), as well as the template invocations:</p><p><span class="pl-k" data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #b46064; background-color: white; box-sizing: border-box; color: #d73a49; font-size: 12px; white-space: pre;"><span class="pl-c1" data-darkreader-inline-color="" style="--darkreader-inline-color: #75a7d0; box-sizing: border-box; color: #005cc5;"><span> </span>$</span></span><span data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #c4bfb6; background-color: white; color: #24292e; font-size: 12px; white-space: pre;">(deriveSafeCopy </span><span class="pl-c1" data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #75a7d0; background-color: white; box-sizing: border-box; color: #005cc5; font-size: 12px; white-space: pre;">0</span><span data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #c4bfb6; background-color: white; color: #24292e; font-size: 12px; white-space: pre;"> 'base ''ServerState)</span></p><p><span class="pl-k" data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #b46064; background-color: white; box-sizing: border-box; color: #d73a49; font-size: 12px; white-space: pre;"><span class="pl-c1" data-darkreader-inline-color="" style="--darkreader-inline-color: #75a7d0; box-sizing: border-box; color: #005cc5;"><span> </span>$</span></span><span data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #c4bfb6; background-color: white; color: #24292e; font-size: 12px; white-space: pre;">(makeAcidic ''ServerState ['writeState, 'queryState])</span></p><p>On the server side, <a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/server/Server/HelloServerAcid.hs">this file</a> has the updated logic to interact with the data store. Since <i>acid-state</i> uses monadic state, we can use <i>ReaderT </i>and again follow the <a href="https://docs.servant.dev/en/stable/tutorial/Server.html">Servant tutorial</a> to thread the data state through the server calls. Although it doesn't seem strictly necessary given the <i>acid-state</i> guarantees, we can use the bracket pattern from <i>Control.Exception </i>to ensure that the data store is closed normally in the event of unexpected server failure.</p><p>That's pretty much it! As promised by the stack, generating the Elm code is just a matter of changing some filename configs in the code. In this case, the REST interface didn't change, so changing the backend had no impact on the rest of the client code. </p><p>I haven't thought too much yet about the implications of this approach vs using some typed-SQL library like <a href="https://www.yesodweb.com/book/persistent">persistent</a>, which I intend the try next.</p><p><br /></p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-41830563518001302672020-11-05T16:08:00.005-08:002020-11-05T16:51:35.260-08:00Hello Server: Haskell + Elm Across Data Boundaries<p> I started with the thought that it would be fun to write a small, private social network app in Elm, for family and friends to share. This immediately begs the question: what should the backend be? </p><p>Setting aside for the moment the class of problems associated with running infrastructure with real users and data on the internet (e.g. security, availability, load, etc), there is the problem of type consistency and safety.</p><p>Maintaining safe, static data typing across data boundaries (say, client and server, or server and persistence layer) seems inherently tricky. Ideally, one wants to define data types (or data structures) somewhere, exactly once, and have some abstractions and / or tools that propagate the type guarantees throughout the stack. That would safe effort, minimize boilerplate, and prevent typ(e)o-related errors!</p><p>The Elm ecosystem actually has <a href="https://discourse.elm-lang.org/t/announcing-lamdera-open-alpha/5669">Lamdera</a>, whose the promise is that the server and persistence layers are abstracted away, leaving the developer to reason only about Elm data structures and what data maintain logically in the front vs back end. That's pretty much exactly what I want in this instance! Sadly, it remains in alpha, and doesn't appear to be open source for the moment.</p><p>Browsing through the <a href="https://github.com/Gabriel439/post-rfc/blob/master/sotu.md">State of the Haskell ecosystem</a>, there are a variety of options for running servers and handling persistence in Haskell (the most obvious fit with Elm). Some of them look like they need project status updates (like Spock... <a href="https://github.com/agrafix/Spock/issues/164">people want to know the status</a>, as it's been dormant for ~three years!). But of course I'm not the first to encounter this problem... so there are a few promising libraries. </p><p><br /></p><p><b>Haskell Server + Elm code gen + no persistence</b></p><p>The first is <i><a href="https://github.com/haskell-servant/servant-elm">servant-elm</a>,</i> which wraps the <i>elm-bridge library </i>for use with the Servant webserver. </p><p>Following Servant's <a href="https://docs.servant.dev/en/stable/tutorial/">tutorial</a> and the <i>servant-elm </i>README on Github, we can: </p><p></p><ol style="text-align: left;"><li>Define ADTs of our choice in Haskell, with corresponding typed REST APIs for Servant</li><li>auto-generate Elm code for corresponding data, including JSON serializers / deserializers that match the REST API (!)</li></ol><div><a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/src/Modules/HelloServer.hs">This file</a> defines the Haskell ADTs and API endpoints, with the Template Haskell line that <i>servant-elm </i>needs: <span data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #c4bfb6; background-color: white; color: #24292e; font-size: 12px; white-space: pre;">deriveBoth defaultOptions ''ServerState</span></div><div><br /></div><div><a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/server/Server/HelloServer.hs">This file</a> then defines the server logic, with an <span data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" face="SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #75a7d0; background-color: white; color: #005cc5; font-size: 12px; white-space: pre;">IORef </span>to maintain some simple in-memory state.</div><div><br /></div><div>Finally, <a href="https://github.com/tkuriyama/spacemonkey/blob/master/spacemonkey/make/Make/HelloServer.hs">this file</a> actually generates the Elm module (well, the binary that generates the Elm module).</div><div><br /></div><div>The <a href="https://github.com/tkuriyama/spacemonkey/blob/master/client/src/CodeGen/HelloServer.elm">resulting Elm code </a>works as expected, albeit with some long function names!</div><p></p><p>To actually use the Elm client with localhost, I needed to start a temporary version of Chrome with some web security options disabled to account for CORS (<a href="https://alfilatov.com/posts/run-chrome-without-cors/">borrowed from here</a>).</p><p><br /></p><p>Next post... adding persistence.</p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-52012785415252827432020-11-02T20:36:00.002-08:002020-11-02T20:37:09.912-08:00Parser Combinator for SQL Subset<p>Some more records from RC... a fellow Recurser and I presented on our toy SQL parser combinator at the Friday 5-minute talks (<a href="https://tarokuriyama.com/writing/RC_RSQL_Talk.html">talk slides</a>).</p><p>We actually ended up writing parser combinators from scratch twice during RC (first for <a href="https://www.cis.upenn.edu/~cis194/spring13/">CIS194</a> and again for <a href="https://github.com/bitemyapp/fp-course">fp-course</a>). The two had almost identical primitives like <i>satisfy :: (Char -> Bool) -> Parser Char, zeroOrMore, oneOrMore, </i>and building up from there... which makes me wonder if there's just a standard recipe for parser combinators? </p><p>For the toy SQL parser, we ended up referencing how Stephen Diehl uses Parsec in <a href="https://github.com/sdiehl/kaleidoscope">Kaleidescope</a> once we defined the syntax. It turns our that Parsec provides a bunch of primitives we previously wrote ourselves, like <i>brackets</i>, <i>parens</i>, <i>commaSep</i>... But I think it would have taken us much longer to figure out how to use the package, were it not for Diehl's examples.</p><p><a href="https://github.com/tkuriyama/toydb/blob/master/src/Database/Parser.hs">https://github.com/tkuriyama/toydb/blob/master/src/Database/Parser.hs</a></p><p><br /></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">*Database.Parser> process "Insert Into myTable [1, True, \"Jonathan\"];"</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">Insert "myTable" [FvInt 1,FvBool True,FvText "Jonathan"]</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">*Database.Parser> process "Insert Into myTable [1, True, \"Jonathan\"]"</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">(line 1, column 42):</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">unexpected end of input</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">expecting ";"</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">*Database.Parser> process "Insert myTable [1, True];"</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">(line 1, column 8):</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">unexpected "m"</span></p><p class="p1" data-darkreader-inline-color="" style="--darkreader-inline-color: #dad6ce; color: black; font-family: Menlo; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-size: x-small; font-variant-ligatures: no-common-ligatures;">expecting "Into"</span></p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-87626105003655778482020-11-02T11:21:00.002-08:002020-11-02T11:21:51.608-08:0012 Weeks of RC<p> Summary of my 12 weeks at Recurse Center (<a href="https://www.recurse.com/">https://www.recurse.com/</a>).</p><p><br /></p><p>It was, unequivocally, a fun and intellectually rewarding experience that I'd recommend to folks interested in programming -- at pretty much any stage of life or career. It's free to attend, for the moment virtual, and available in 1, 6, and 12 week formats).</p><p><br /></p><ul style="background-color: white; color: #222222; font-family: Arial, Helvetica, sans-serif; font-size: small;"><li style="margin-left: 15px;">Organized a daily study group for functional programming (mainly Haskell)</li><li style="margin-left: 15px;">Attended weekly study groups for systems programming and <a data-saferedirecturl="https://www.google.com/url?q=https://plfa.github.io/&source=gmail&ust=1604429299163000&usg=AFQjCNG1oV0ANflcuOCkPA4R6gVVjblqYA" href="https://plfa.github.io/" style="color: #1155cc;" target="_blank">type theory</a></li><li style="margin-left: 15px;">Learned about Elm and wrote some visualizations <a data-saferedirecturl="https://www.google.com/url?q=https://tarokuriyama.com/projects/sudoku.php&source=gmail&ust=1604429299163000&usg=AFQjCNFKTvajK3anGjMC0PXS0Tzdl0fHZQ" href="https://tarokuriyama.com/projects/sudoku.php" style="color: #1155cc;" target="_blank">(sudoku</a>, <a data-saferedirecturl="https://www.google.com/url?q=https://tarokuriyama.com/projects/risk.php&source=gmail&ust=1604429299163000&usg=AFQjCNFRp-1S6FajRV2Ld8sG237TtUQWaA" href="https://tarokuriyama.com/projects/risk.php" style="color: #1155cc;" target="_blank">risk</a>)</li><li style="margin-left: 15px;">Learned about networking primitives and wrote some <a data-saferedirecturl="https://www.google.com/url?q=https://github.com/tkuriyama/toyserver&source=gmail&ust=1604429299163000&usg=AFQjCNFU9kKWfvyIHRnrcspy7H-Yjz2W7g" href="https://github.com/tkuriyama/toyserver" style="color: #1155cc;" target="_blank">buggy toy servers</a></li><li style="margin-left: 15px;">Contributed to a friend's <a data-saferedirecturl="https://www.google.com/url?q=https://gitlab.com/awjchen/pixelpusher&source=gmail&ust=1604429299163000&usg=AFQjCNHKAd_21OyStefvwnOVDx2BIwh3Dw" href="https://gitlab.com/awjchen/pixelpusher" style="color: #1155cc;" target="_blank">Haskell game</a> (networked and concurrent!), soon to be internet-playable</li><li style="margin-left: 15px;">Spent some time with <a data-saferedirecturl="https://www.google.com/url?q=https://en.wikipedia.org/wiki/QuickCheck&source=gmail&ust=1604429299163000&usg=AFQjCNH-kZva67Ixrtod60DpUhsBh0uLvg" href="https://en.wikipedia.org/wiki/QuickCheck" style="color: #1155cc;" target="_blank">property-based testing,</a> test coverage, and <a data-saferedirecturl="https://www.google.com/url?q=https://learning.tarokuriyama.com/2020/09/trying-tcr.html&source=gmail&ust=1604429299163000&usg=AFQjCNEZo_YcKFQ49TR4o03B6YGAiqg6mQ" href="https://learning.tarokuriyama.com/2020/09/trying-tcr.html" style="color: #1155cc;" target="_blank">TCR == (Test && Commit) || Revert</a></li><li style="margin-left: 15px;">Procrastinated on writing computer-generated music (<a data-saferedirecturl="https://www.google.com/url?q=https://github.com/tkuriyama/hsom/tree/master/samples/collatz&source=gmail&ust=1604429299163000&usg=AFQjCNH0vEtvR6xd1ZZ6sa0SndnJTsudCA" href="https://github.com/tkuriyama/hsom/tree/master/samples/collatz" style="color: #1155cc;" target="_blank">small example</a> sonifying the Collatz sequence)</li><li style="margin-left: 15px;">Started a group project to write a <a data-saferedirecturl="https://www.google.com/url?q=https://github.com/tkuriyama/toydb&source=gmail&ust=1604429299163000&usg=AFQjCNFys7UzYcUpCV_x6fBYq_781u8d6g" href="https://github.com/tkuriyama/toydb" style="color: #1155cc;" target="_blank">toy database</a> in Haskell (with a toy SQL parser combinator and B-Trees)</li><li style="margin-left: 15px;">Attended 6-12 technical and non-technical a week (most of them 5 mins); gave five 5-min talks</li><li style="margin-left: 15px;">Attended a great talk on Turing's <a data-saferedirecturl="https://www.google.com/url?q=https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf&source=gmail&ust=1604429299163000&usg=AFQjCNEJLRAzij5y-g0FM4cUAXSX5kr7XA" href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf" style="color: #1155cc;" target="_blank">'36 paper on computation</a>; presented on Dijkstra's <a data-saferedirecturl="https://www.google.com/url?q=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD04xx/EWD447.html&source=gmail&ust=1604429299163000&usg=AFQjCNF9I5s8I7e_XQhWwuRqz89QzS3nTQ" href="https://www.cs.utexas.edu/users/EWD/transcriptions/EWD04xx/EWD447.html" style="color: #1155cc;" target="_blank">'74 essay on scientific thought</a></li><li style="margin-left: 15px;">Wrote a few thousand lines of code -- the below table is an inaccurate though representative summary (using <a data-saferedirecturl="https://www.google.com/url?q=https://docs.rs/tokei/12.0.4/tokei/&source=gmail&ust=1604429299163000&usg=AFQjCNGcnBdZBq0_rYtHWkSSK_KcB2koWQ" href="https://docs.rs/tokei/12.0.4/tokei/" style="color: #1155cc;" target="_blank">tokei</a>)</li></ul><div><pre style="background-color: #1c252f; border-radius: 4px; border: 1px solid rgba(0, 0, 0, 0.15); color: #a3cefe; direction: ltr; font-family: Menlo, Consolas, "Courier New", monospace; font-size: 0.8em; line-height: 1.4; margin-bottom: 5px; margin-top: 5px; overflow-wrap: normal; overflow-x: auto; padding: 5px 7px 3px; word-break: break-all;"><code style="border-radius: 3px; border: 0px rgba(0, 0, 0, 0.5); direction: ltr; font-family: Menlo, Consolas, "Courier New", monospace; font-size: inherit; overflow-x: scroll; padding: 0px; unicode-bidi: embed; white-space: inherit;">===============================================================================
Language Files Lines Code Comments Blanks
===============================================================================
C 8 1169 935 31 203
C Header 1 229 64 122 43
Elm 12 1322 1061 43 218
Haskell 49 5231 2232 2327 672
Org 3 236 155 0 81
Python 9 743 585 23 135
Shell 6 16 13 1 2
Zig 3 56 41 0 15
Zsh 1 26 20 1 5
-------------------------------------------------------------------------------
Jupyter Notebooks 4 0 0 0 0
|- Markdown 4 191 0 134 57
|- Python 4 722 623 21 78
(Total) 913 623 155 135
===============================================================================
Total 96 9941 5729 2703 1509
===============================================================================</code></pre></div>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-70609785673014610092020-10-20T09:55:00.004-07:002020-10-20T09:55:44.988-07:00Network Programming <p></p><div>We decided to a bit of socket-level network programming as part of the systems programming study group at <a href="https://www.recurse.com/">Recurse Center.</a> The canonical text would appear to be the Unix Network Programming book, but Beej's guide also came highly recommended -- with the added benefit of being quicker to get started and freely available online: </div><ul style="text-align: left;"><li><a href="https://beej.us/guide/bgnet/html/">https://beej.us/guide/bgnet/html/</a></li><li><a href="http://www.unpbook.com/">http://www.unpbook.com/</a></li></ul><div>It turns out that following the correct order of syscalls per Beej's incantations is relatively straightforward... yielding very simple toy servers in short order:</div><div><ul style="text-align: left;"><li><a href="https://github.com/tkuriyama/toyserver">https://github.com/tkuriyama/toyserver</a></li></ul><div>On the other hand, some fundamentals of C programming still elude me, e.g. I couldn't work out how to refactor the creation of sockets into a standalone function due to some (presumably basic) pointer issues...</div></div><div><br /></div><p></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-2977160125987012202020-10-19T13:39:00.006-07:002020-10-23T06:07:38.721-07:00fp-course<p>Following the <a href="https://github.com/bitemyapp/learnhaskell">Learn Haskell </a>recommendation, the FP study group at <a href="https://www.recurse.com/">Recurse Center </a> worked through the fp-course exercises after finishing CIS 194. </p><p><a href="https://github.com/bitemyapp/learnhaskell">https://github.com/bitemyapp/learnhaskell</a></p><p>The exercises seem to provide good practice, with modules like State and StateT requiring some mental gymnastics training..! </p><p>The repo unfortunately has some incomplete tests files, so I transcribed a few from the comments into HSpec format for Parser.hs and MoreParser.hs: <a href="https://github.com/tkuriyama/puzzles/tree/master/fp-course">https://github.com/tkuriyama/puzzles/tree/master/fp-course</a>. </p><p>The test cases were tedious but turned out to be worthwhile, since JsonParser.hs is comprised of more abstract parser combinators. (Interestingly, the parser combinator in CIS 194 is almost identical to fp-course in its building blocks... a coincidence, or a common design pattern?).</p><p>Anagrams and Cheque remain to be completed, but we're moving on to writing a toy database in Haskell (with the goal to complete in the last two weeks of the Fall 1 batch!).</p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-76125129359069329462020-10-12T14:16:00.001-07:002020-10-12T14:16:11.507-07:00Dijkstra '74 on Scientific Thought<p>Some slides from a short talk at Recurse Center on Dijkstra's 1974 essay <a href="https://www.cs.utexas.edu/users/EWD/transcriptions/EWD04xx/EWD447.html#:~:text=Scientific%20thought%20comprises%20%22intelligent%20thinking,of%20useful%20and%20helpful%20concepts.">"On the role of scientific thought"</a></p><p><a href="https://tarokuriyama.com/writing/dijkstra74.html">https://tarokuriyama.com/writing/dijkstra74.html</a> </p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-73974716527846493682020-10-11T13:45:00.002-07:002020-10-11T13:45:31.330-07:00Game of Risk Elm Visualization<p>Building on the previous post... an interactive(ish) Elm visualization of the game's probability trees: </p><p><a href="https://tarokuriyama.com/projects/risk.php">https://tarokuriyama.com/projects/risk.php</a></p><p><br /></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-66940030336507326722020-09-17T10:59:00.006-07:002020-09-17T11:09:33.624-07:00Game of Risk<p>The last assignment in the <a href="https://www.seas.upenn.edu/~cis194/spring13/lectures.html">CIS194</a> Haskell class is to simulate dice-throwing battles in the game of Risk. The combat rules, taken from assignment specs, are:</p><p></p><ul style="text-align: left;"><li>There is an attacking army (containing some number of units) and
a defending army (containing some number of units). </li><li>The attacking player may attack with up to three units at a time.
However, they must always leave at least one unit behind. That
is, if they only have three total units in their army they may only
attack with two, and so on. </li><li>The defending player may defend with up to two units (or only
one if that is all they have). </li><li>To determine the outcome of a single battle, the attacking and
defending players each roll one six-sided die for every unit they
have attacking or defending. So the attacking player rolls one, two,
or three dice, and the defending player rolls one or two dice. </li><li>The attacking player sorts their dice rolls in descending order. The
defending player does the same.</li><li>The dice are then matched up in pairs, starting with the highest
roll of each player, then the second-highest.</li><li>For each pair, if the attacking player’s roll is higher, then one of
the defending player’s units die. If there is a tie, or the defending
player’s roll is higher, then one of the attacking player’s units die.</li></ul><div>We assume it is optimal to always attack or defend with as many units as possible.</div><div><br /></div><div><br /></div><div><b>Given an initial number of attacking and defending units, what is the expected outcome (say, the probability that the attacker wins)? </b></div><div><br /></div><div>It's not obvious that there is a closed-form expression, but we can find programmatically the exact probabilities. </div><div><br /></div><div>First, from the game specs, we know that there are only a few primitive battle patterns (A, D), where A is attacked and D is defender: (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2). For each pattern, we can generate all possible permutations of die values. Each permutation represent a battle, with an outcome ("loss scenario") in which A and D both lose some number of units (which can be zero units, if they win all dice rolls). </div><div><br /></div><div>For example, for (A,D) of (1,1), both the attacker and defender role one die each, yielding 36 pairs of possible die rolls: (1,1), (1,2), (1,3) ... (6,5), (6,6). Tallying up the proportion of outcomes: A loses 1 unit 21 / 36; D loses 1 unit 15 / 36.</div><div><br /></div><div>(Incidentally, the closed-form expression for 1 vs 1 is relatively simple: for each N that the defender rolls, with 1/6 probability each, the attacker loses in N/6 scenarios. For example, if the defender rolls 4, the attacker loses for all die values <= 4. So we can evaluate the expression <i>(1/6) * (sum [1..6]) / 6</i>, which equals 21/36. See <a href="https://web.stanford.edu/~guertin/risk.notes.html">these notes</a> for a more detailed explanation.)</div><div><br /></div><div>Once we have the loss scenarios with proportions for each primitive battle pattern, finding the exact win probability for the attacker is recursive: for any given starting pattern (A, D), lookup the relevant primitive battle pattern. For each loss scenario in which the attacker does not lose the game, update the battlefield with the losses and recursively lookup the next loss scenario, chaining the proportions (probabilities) until the game ends for each branch. </div><div><br /></div><div>The win probabilities for the attacker for patterns up to (10, 10) are:</div><div><br /></div><div style="text-align: center;"><img border="0" data-original-height="642" data-original-width="1104" height="233" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgcUAS3hJIGPvxZxqXyNdXCE8_FxtImtR-hzPcFfP4Lrod7fEE4ITcox2xS6myPwtcV3gXQJdFBIeXgP77rqcBpmZ615iNgkNZHWcKM8cJl9Xghcqo6pL2NgEGX5CLeHZbjFyFLZMFODOY/w400-h233/Screen+Shot+2020-09-17+at+1.54.11+PM.png" width="400" /></div><div><br /></div><div><a href="https://gist.github.com/tkuriyama/b1b8b05ec10a733801370c566311df34">The Haskell implementation for the above is in this gist.</a> </div><div><br /></div><div>Using Rational numbers in Haskell allows the answers to be expressed exactly. For example for (4,2), the win probability for A is <span data-darkreader-inline-color="" style="--darkreader-inline-color: #c4bfb6; color: #24292e; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 13.6px; white-space: pre;">6610505 % 10077696</span><span data-darkreader-inline-bgcolor="" data-darkreader-inline-color="" style="--darkreader-inline-bgcolor: #2f2f2f; --darkreader-inline-color: #c4bfb6; background-color: white; color: #24292e; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, monospace; font-size: 12px; white-space: pre;"> </span>(see <a href="https://gist.github.com/tkuriyama/efe71096b8d550f7dbc19c6b154342f0">the rightmost column here</a>). </div><div><br /></div><div><br /></div><div><br /></div><p></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-51516879929550234362020-09-11T12:50:00.008-07:002020-09-11T13:18:18.945-07:00Trying TCR<p>A fellow at the Recurse Center hosted a workshop on TCR (see <a href="https://medium.com/@kentbeck_7670/test-commit-revert-870bbd756864" target="_blank">Kent Beck's post</a> for an introduction to the idea), using <a href="https://github.com/islomar" target="_blank">these templates</a>. </p><p>The short of it is: a watcher will automatically run tests upon file save; if any tests fail, it will revert to the prior commit; else, it will make a new commit. </p><p>Despite some initial mental (and practical workflow) resistance, I've warmed very rapidly to the idea. </p><p>By far the biggest change is the <i>revert </i>part of <i>test && commit || revert. </i>Some initial complaints:</p><p></p><ul style="text-align: left;"><li>I made a typo, and it revert to the last commit</li><li>I just lost a whole block of code</li><li>I can't just try this simple thing because it keeps failing a test and getting deleted </li></ul><div>The first one maybe retains some legitimacy, but in general, the idea is: </div><div><ul style="text-align: left;"><li>slow down</li><li>write fragments that you understand</li><li>write smaller fragments if necessary </li></ul><div>The process also highlights the fact that tests may evolve with the code; as an interface changes, so too do the tests need to change (or TCR won't let you make the commits!).</div></div><div><br /></div><div><b><br /></b></div><div><b>A few implementation notes for macOS users</b>, building on the Python example from <a href="https://github.com/islomar" target="_blank">these templates</a>. </div><div><br /></div><div><a href="https://gist.github.com/tkuriyama/9e7203cb1e45fd31a1d2178a254beecd" target="_blank">This gist</a> contains the edits discussed below.</div><div><br /></div><div><b>watch.sh</b></div><div><ul style="text-align: left;"><li>Instead of <i>inotifywait</i>, on macOS <i>fswatch</i> can be installed from Homebrew (<i>brew install fswatch)</i></li><li><i>fswatch </i>should be called with the <i>--one-event</i> flag, since it's already called in an infinite loop (otherwise it blocks the next line)</li></ul></div><div><b>commit.sh</b></div><div><ul style="text-align: left;"><li>By default, TCR will auto-commit with the same message; as one possible alternative, call AppleScript and ask for a commit message via a prompt</li></ul><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_lZli0WdKTu9fksDnA35DEVzPW7OWr6fU6JHwf_Cv18jFvA_v_wJGh_eRx63mG55jxkdTnV4lS_w9fOEAMjB8WU4EVMIMj9t5PV5BaQbWYb1qRqbJGnsFCOb5gCoQmMnKOC9Fni09ick/s2048/Screen+Shot+2020-09-11+at+3.08.26+PM.png" style="margin-left: 1em; margin-right: 1em; text-align: center;"><span> </span><img border="0" data-original-height="1156" data-original-width="2048" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_lZli0WdKTu9fksDnA35DEVzPW7OWr6fU6JHwf_Cv18jFvA_v_wJGh_eRx63mG55jxkdTnV4lS_w9fOEAMjB8WU4EVMIMj9t5PV5BaQbWYb1qRqbJGnsFCOb5gCoQmMnKOC9Fni09ick/s320/Screen+Shot+2020-09-11+at+3.08.26+PM.png" width="320" /></a><br /><div><b><br /></b></div><div><b>test.sh</b></div></div><div><ul style="text-align: left;"><li>The default example has some assertions in the main Python file; modify this to call a testing framework instead (in my case, <i>py.test</i>)</li></ul><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><div>There's a <a href="https://www.twitch.tv/videos/727440075" target="_blank">good video here</a> of doing TCR-style testing in Elm. An interesting aspect they mention is squashing a bunch of TCR-generated commits ("what changed") at a later point into more of an explanatory commit ("why the changes").</div></div><div><br /></div><div><br /></div><div>P.S. for best results with editors, autosave features should be disabled, and autoreload features should be enabled, e.g. in emacs: </div><div><br /></div><div><i>(global-auto-revert-mode t)</i></div><div><i>(setq auto-save-default nil)</i></div><div><br /></div><div><br /></div><p></p><p><i><br /></i></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-64183699812865757232020-08-28T14:34:00.005-07:002020-08-28T14:39:17.539-07:00Sudoku Visualization<p>The Sudoku solver visualization in Elm is done! </p><p><a href="https://tarokuriyama.com/projects/sudoku.php">https://tarokuriyama.com/projects/sudoku.php</a></p><p>Writing Elm feels similar to writing Haskell, with a bit of syntax that's more like F# (e.g. the pipeline operators <| and |>). Between the familiar format of <a href="https://learnyouanelm.github.io/" target="_blank">Learn You and Elm</a> and the examples in <a href="https://elmprogramming.com/" target="_blank">Beginning Elm</a>, it's relatively easy to pick up given a bit of functional programming background.</p><p>All of the code for the solver and visualization is on <a href="https://github.com/tkuriyama/sudoku" target="_blank">GitHub</a>.</p><p><br /></p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCvb2Yjr3PTkRlScUdDizbyFPJT0ABn0NjA4JubuRSdovD66bVM2HQ4iS94avV19Orp_5ruUGnvU4B1UgLxB6c3OM2_YKul4N4xH95RAOPQ6O2A5x3MmYR_w0OFtbFkGq77qDcRT-EDNI/s788/Screen+Shot+2020-08-28+at+5.37.55+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="788" data-original-width="780" height="410" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCvb2Yjr3PTkRlScUdDizbyFPJT0ABn0NjA4JubuRSdovD66bVM2HQ4iS94avV19Orp_5ruUGnvU4B1UgLxB6c3OM2_YKul4N4xH95RAOPQ6O2A5x3MmYR_w0OFtbFkGq77qDcRT-EDNI/w406-h410/Screen+Shot+2020-08-28+at+5.37.55+PM.png" width="406" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><a href="https://tarokuriyama.com/projects/sudoku.php"><br /></a> <p></p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-12588658806823540432020-08-26T19:49:00.006-07:002020-08-27T05:26:13.816-07:00Elm JSON Decoder<p>In the vein of functional programming, I've been learning Elm to visualize the progress of a Sudoku solver.</p><p>The JSON decoding tutorials are clear, and the <a href="https://package.elm-lang.org/packages/elm/json/latest/Json.Decode" target="_blank">JSON.Decode</a> library is well-documented once you know how to read it (in general, the library documentation in Elm seems to be on the terse side). </p><p></p><ul style="text-align: left;"><li><a href="https://elmprogramming.com/decoding-json-part-1.html">https://elmprogramming.com/decoding-json-part-1.html</a></li><li><a href="https://elmprogramming.com/decoding-json-part-2.html">https://elmprogramming.com/decoding-json-part-2.html</a></li></ul><p></p><p>Two things were not very clear from initial read of the docs: how to parse lists to tuples, and how to parse strings to custom types. </p><p><a href="https://stackoverflow.com/questions/42703764/decode-a-json-tuple-to-elm-tuple" target="_blank">Leaning on SO for the below example</a>, tuples apparently used to be supported as first-class decoders, but in the current version of Json.Decoder, <i>index</i> seems to be the official way to construct decoders for tuples. </p><p><span style="font-family: courier; font-size: x-small;">arrayAsTuple2 a b c =</span></p><p><span style="font-family: courier; font-size: x-small;"> Decode.index 0 a</span></p><p><span style="font-family: courier; font-size: x-small;"> |> Decode.andThen (\ aVal -> Decode.index 1 b</span></p><p><span style="font-family: courier; font-size: x-small;"> |> Decode.andThen (\ bVal -></span><span style="font-family: courier; font-size: small;"> Decode.succeed (aVal, bVal)))</span><span style="font-family: courier; font-size: small;"> </span></p><p><span style="font-family: courier; font-size: x-small;">boardDecoder : Decoder Board</span></p><p><span style="font-family: courier; font-size: x-small;">boardDecoder = Decode.list <| arrayAsTuple2 Decode.int Decode.int </span></p><p>Elm 0.19 only supports up to three-value tuples (somewhat surprising coming from Haskell, though with records and custom data types, the decision to limit unnamed tuples has a certain logic...). So the helper construction isn't too bad.</p><div><br /></div><div>Parsing strings to custom data types turns out to be more straightforward, though a bit repetitive (especially if you need to later get the string representation back out of custom data type -- there is no <i>deriving Show</i> in Elm). First decode the string, then chain a pattern match using <i>andThen</i>:</div><div><br /></div><div><div><span style="font-family: courier; font-size: x-small;">data Transform = Rows | Cols | Boxes</span></div><div><span style="font-family: courier; font-size: x-small;"><br /></span></div><div><span style="font-family: courier; font-size: x-small;">transformDecoder : Decoder Transform</span></div><div><span style="font-family: courier; font-size: x-small;">transformDecoder =</span></div><div><span style="font-family: courier; font-size: x-small;"> Decode.string</span></div><div><span style="font-family: courier; font-size: x-small;"> |> Decode.andThen</span></div><div><span style="font-family: courier; font-size: x-small;"> (\ s -></span></div><div><span style="font-family: courier; font-size: x-small;"> case s of</span></div><div><span style="font-family: courier; font-size: x-small;"> "Rows" -> Decode.succeed Rows</span></div><div><span style="font-family: courier; font-size: x-small;"> "Cols" -> Decode.succeed Cols</span></div><div><span style="font-family: courier; font-size: x-small;"> "Boxes" -> Decode.succeed Boxes</span></div><div><span style="font-family: courier; font-size: x-small;"> _ -> Decode.fail <| "Unknown transformation.")</span></div></div>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-38604070960123775312020-08-22T09:05:00.001-07:002020-08-22T09:08:16.458-07:00Recurse Center<p> I've wanted to attend the <a href="https://www.recurse.com/" rel="nofollow" target="_blank">Recurse Center</a> (formerly known as Hacker School) or a while, and have finally found the time to do so. It's very consistent with the free education path (it's free!), and so far has been a great source of exposure to new topics and ideas, as well as of inspiration to work on different classes of problems. They've put a lot of effort into fostering a healthy, supportive community, and the nature of the program is such that self-motivated, inquisitive learners more or less self-select themeselves into attendance. Some topics I was exposed to or participated in so far -- audio programming, gaming, lower-level / systems programming languages (eg Zig), functional programming (eg Haskell, Elm), procedural generetion, Web Assembly compilation... There are folks of all walks of life, skills, and interests in the community, making it something that I expect will continue to yield rich experiences for the remainder of the three-month batch. </p>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-88635121235437212082020-07-29T14:22:00.002-07:002020-07-29T14:25:05.385-07:00Stochastic Writing<div><a href="https://www.youtube.com/channel/UC2kxl-dcUYQQvTCuQtfuChQ">Bang Bang Con 2020</a> features a number of pithy, unexpected talks.</div><div><br /></div><div>Following <a href="https://www.youtube.com/watch?v=zNJAQcSA1vI" target="_blank">Andrew Yoon's talk about</a> his work on <a href="https://github.com/ajyoon/bml" target="_blank">BML</a> (a "stochastic markup language"), here's a short poem that changes under the reader's eyes... </div><div><br /></div><div><a href="https://tarokuriyama.com/writing/intersection.php" target="_blank">"Flatbush and Fulton"</a></div><div><a href="https://tarokuriyama.com/writing/intersection.php" target="_blank"><br /></a></div><div><br /></div><div><br /></div><br />THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-86369040112102674282020-06-21T05:50:00.000-07:002020-06-21T05:50:09.142-07:00What goes on in a computer in a millisecond?In a <a href="https://www.youtube.com/watch?v=zbJdgKATZEU">2001 Q&A session</a> (around 1h30m) Knuth is asked about unsolved challenges in the field of compute science, à la Hilbert's problems. Knuth's responds by referring to a prompt he posed to the World Computer Congress in 1989, in a keynote titled "Theory and Practice, IV" (Arxiv has <a href="https://arxiv.org/pdf/cs/9301114.pdf">a version,</a> though <a href="http://prl.korea.ac.kr/~pronto/home/resources/knuth-theory-practice.pdf">this version </a>appears to have the slides as well):<br />
<br />
<i>"Make a thorough
analysis of everything your computer does during one second of computation"</i><br />
<br />
Does the prompt require adjustment for context, some thirty years later? Knuth noted the practical challenges associated with monitoring and interpreting the computer's activities, whose difficulty would appear to remain on the same order of magnitude today. On the other hand, Knuth associated 1 second with approximately 250,000 instructions. Given that CPU clock speeds have jumped from standard units in MHz to GHz (<a href="https://en.wikipedia.org/wiki/Microprocessor_chronology">wikipedia notes</a> clock speeds in 1989 were in the 16-35 MHz range, in line with Knuth's approximation), maybe today's equivalent of the question is:<br />
<i><br /></i>
<i>"What goes on in a computer in a millisecond"</i>?<br />
<br />
In the same keynote, Knuth provides a set of guiding questions, including the correctness of the observed activities and their correspondence to theory -- that is, whether they reflect existing theory, and whether new theory would yield practical improvements.<br />
<br />
Despite the daunting scope of the problem, the fundamental idea of mapping theory to some atomic observations of computing practice seems widely applicable and useful for students and practitioners alike.THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-33276063838773354822020-06-07T14:24:00.004-07:002020-06-15T12:34:15.187-07:00Compilers, Project Euler 100It was sad to see Stanford retire Lagunita (apparently due to a decision to retire their Open edX implementation). Many of their classes appear to be slated for addition to edX, including the <a href="http://web.stanford.edu/class/cs143/">Compilers class</a> -- at least according to an email sent to Lagunita participants. I seem to recall the content originally being available on Coursera. It certainly has the look, feel, and substances of the original batch of very high quality courses (like Tim Roughgarden's Algorithms courses, Andrew Ng's AI course, Dan Boneh's Cryptography Part I... we're still waiting on Part II after many years, apparently because <a href="https://news.ycombinator.com/item?id=22013751">he is trying to finish his book</a>). There seems to be a great deal more of content on the MOOCs now, but also maybe some more noise.<br />
<br />
In any case, I spent most of my study time in March speeding through the Compilers videos and finishing the first programming assignment on lexing (yacc / flex) to make sure all the mechanics work. Fortunately, there are offline graders that can be run in the class VM, so it will be possible to complete the other programming assignments at a more leisurely pace. Given that there isn't currently an active forum for unaffiliated students like me to ask questions, GitHub has been in an invaluable resource to reference other students' implementations and try to triangulate certain issues.<br />
<br />
Speaking of using reference materials... seven years after starting Project Euler and learning about the Sieve of Eratosthenes, I've finally completed more than 100 problems. About 65 problems have been solved in Haskell over the past year (the balance at some point during prior years, in Python).<br />
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhC9CMpjeGqWNXGkpXSJu6H41yZUYsRl5h0ALqmjJ9NvZpskx62ndphm5FdXxB20YGA57Azou3BOobS3spZEoqdViHJlr03aNx_qHNnQDjYIgHeThY4nJ3x8-AF4feHTL7N-7jxVkX5C9o/s1192/Screen+Shot+2020-06-07+at+4.24.06+PM.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="546" data-original-width="1192" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhC9CMpjeGqWNXGkpXSJu6H41yZUYsRl5h0ALqmjJ9NvZpskx62ndphm5FdXxB20YGA57Azou3BOobS3spZEoqdViHJlr03aNx_qHNnQDjYIgHeThY4nJ3x8-AF4feHTL7N-7jxVkX5C9o/s320/Screen+Shot+2020-06-07+at+4.24.06+PM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
I had no qualms referencing the internet for many problems, since it's unlikely I would have independently stumbled upon many of the math theorems required to solve some problems efficiently (like the Sierpinski triangle and Lucas' Theorum behind one of the problems on Pascal's triangle). In that regard, I'm glad of folks who have ignored Proect Euler's rules of the road and posted their research online. At least for autodidactic purposes, it seems like more information is (almost?) always better. How to use and internalize the information, how to differentiate research from shortcuts, how to set boundaries of information taken vs internally synthesized -- those are all the responsibility of the student, with decisions ultimately depending on one's goals. My (recent) goals have been in rough descending order to learn functional programming paradigms, to learn Haskell, to enjoy problem solving, and last + least to learn some underlying math. As far as the first two go, continuing with more problems probably offers diminishing returns (especially compared to pursuing orthogonal problem spaces), but I'll likely continue with it on the slow path for the enjoyment. </div>
<div>
<br /></div>
THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-52124691466115916192020-02-16T13:50:00.001-08:002020-02-23T18:36:08.147-08:00Mini Regex<br />
Hacker News linked to <a href="https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html">Brian Kenighan's post about a small regex matcher</a>, which seemed like a good bite-sized problem to try implementing -- both in general and for practicing Haskell, particularly with this being a pattern matching problem.<br />
<br />
Following Kernighan's specifications, the regex language is limited to:<br />
<br />
<pre> c matches any literal character c
. matches any single character
^ matches the beginning of the input string
$ matches the end of the input string
* matches zero or more occurrences of the previous character</pre>
<pre></pre>
<br />
To make the exercise a bit more stateful, I chose to implement find (return the left-most occurrence of a pattern that matches the regex, if it exists), instead of just indicating the presence of a match. There is minimum lookahead required -- just one character to detect boundaries for the Kleene star.<br />
<br />
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
I first tried to implement find with a lazy map over the tails of the input (returning the head as the left-most match), but ran into the problem of inputs with no matches. Since I couldn't find an out-of-box function, mapUntil implements a map that stops when a non-default value is found, and otherwise returns the default value. This also has the benefit of using an empty string to indicate no match, which is more direct here than, say, using Maybe. Always wrapping and unwrapping the input with the start and end sentinels seemed like a reasonable price to avoid introducing special cases later on. <br />
<br /></div>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;">find :: Regex -> String -> Match
find r s = unwrap $ mapUntil "" (findWord r) (tails $ wrap s)
where wrap xs = ('^':xs) ++ "$"
unwrap xs = [c | c <- xs, c `notElem` ['^', '$']]</span></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;">mapUntil :: Match -> (String -> Match -> Match) -> [String] -> Match
mapUntil d _ [] = d
mapUntil d f (x:xs) = if m /= d then m else mapUntil d f xs
where m = f x ""</span></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;">
</span></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
The core matching function covers four patterns: non-star regex, star regex, the regex is consumed (success), or otherwise failure. </div>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;">findWord :: Regex -> String -> Match -> Match
findWord (x:'*':xs) s@(y:ys) ms = findWord xs ys' (reverse ms'++ ms)
where (ms', ys') = if not (match x y) then ("", s) else splitWhile (matchStar x xs) s
findWord (x:xs) (y:ys) ms = if match x y then findWord xs ys (y:ms) else ""
findWord "" _ ms = reverse ms
findWord _ _ ms = ""</span>
</pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
Match is very simple. MatchStar needs a bit of extra state, since '.*' matching should stop if the next part of the regex matches input. </div>
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
<br /></div>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;">match :: Char -> Char -> Bool
match x y = x == '.' || x == y
matchStar :: Char -> String -> Char -> Bool
matchStar x [] y = match x y
matchStar x (x':xs) y = (x == '.' && x' /= y) || x == y</span></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
SplitWhile seems like it should exist... it calls both takeWhile and dropWhile, so could be rewritten more efficiently to require only single pass over the input. <br />
<br /></div>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;">splitWhile :: (a -> Bool) -> [a] -> ([a], [a])
splitWhile f xs = (takeWhile f xs, dropWhile f xs)</span></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<pre style="overflow-wrap: break-word; white-space: pre-wrap;"></pre>
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
There are a few reverses and concatenations, which weren't immediately obvious to me to refactor into more efficient patterns. Code with some hand-written test cases: <span data-darkreader-inline-color="" style="--darkreader-inline-color: #88a2b6; color: #598dc9;"><a href="https://gist.github.com/tkuriyama/f60210a0e6dfa5bc0872494afaa0030b">https://gist.github.com/tkuriyama/f60210a0e6dfa5bc0872494afaa0030b</a></span></div>
<div style="overflow-wrap: break-word; white-space: pre-wrap;">
<br /></div>
THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-91457056352978336222019-10-07T03:58:00.001-07:002019-10-07T03:59:18.121-07:00Learn You a Haskell, AgainAfter a few failed attempts in past years, I feel like I've finally collected enough momentum and functional thinking to overcome the initial hurdle in learning Haskell.<br />
<br />
Brent Yorgey's <a href="https://www.cis.upenn.edu/~cis194/spring13/">2013 UPenn class</a> was recommended by a few sources, so I worked through that over the past two or three months. The class pulls together material from Learn You a Haskell (LYAH), Real World Haskell (RWH) and lectures notes into 12 weeks of materials. There are 11 weekly assignments that culminate in Functors, Applicatives, and Monads. At this point, I think I need significantly more practice in the last topics... Overall, the reinforcement provided by two independent texts in addition to the course materials was quite helpful in triangulating new topics, both conceptually and through worked examples.<br />
<br />
Some good next steps seem to be continue working through some later chapters in LYAH and RWH (with a particular interest in monadic parsing), as well as the next course suggested by <a href="https://github.com/bitemyapp/learnhaskell">https://github.com/bitemyapp/learnhaskell</a>.<br />
<br />
<br />
<br />THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-12730046806164840792018-08-26T17:39:00.000-07:002018-08-26T17:39:06.563-07:00Cryptopals Set 6 -- Bleichenbacher <br />
After another hiatus, I finally managed to wrap up Set 6 with Bleichenbacher's PKCS 1.5 padding oracle attack (original paper from '98 <a href="http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf">http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf</a>).<br />
<br />
<a href="https://github.com/tkuriyama/cryptopals/tree/master/set6">https://github.com/tkuriyama/cryptopals/tree/master/set6</a><br />
<br />
All of the padding-based attacks are quite interesting. From first principles, I guess it is difficult to design padding that is cryptographically sound, since by definition padding needs to be deterministic and reasonably easy to parse.<br />
<br />
One thing that escapes me is the use of ceiling division for a number of equations in Bleichenbacher's paper -- it doesn't seem to be specified, yet all the implementations I referenced seemed to apply it consistently.<br />
<br />
I will probably take a break from the Cryptopals for now (i.e. defer Sets 7 and 8) and tackle some other projects. I feel reasonably comfortable with F# now, but still want to learn Haskell, and meanwhile Python is fully transitioning to Python 3 and Guido has retired as BDFL...<br />
<br />
The MOOC landscape seems to have advanced in the past year or two as well, so it will be interesting to take up a few more courses again.<br />
<br />THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-78884017817738363342018-03-20T02:04:00.000-07:002019-07-17T06:42:23.056-07:00Cryptopals Set 6 -- F#<br />
I've worked through Set 6 up to the last two problems involving Bleichenbacher's PKCS 1.5 Padding Oracle attack. With a new job just started, it will likely take a while longer to complete those, so this will be a partial post in the meantime.<br />
<br />
Completing the first six problems of the set required me to revisit two shortcuts that I took thus far: a reasonably fast (probabilistic) prime gen algorithm, and a cube root (or n-root) algorithm for BigIntegers. In both cases the implementations are borrowed, but it was a good exercise to think through them.<br />
<br />
As a slight non sequitur: working with BigIntegers in F# has given me a deep appreciation for just how convenient it is to work with integers in a language like Python. Thanks to <a href="https://www.python.org/dev/peps/pep-0237/).">PEP 237</a>, integers are treated for the most part uniformly, so the user never needs to think about size. But of course, big integers that exceed the CPU word size do require implementation. Which is obvious from first principles, but not something that occurred to me in a meaningful way until I had to write a re-implement a number of functions to work for BigIntegers. Convenience and learning are uneasy friends.<br />
<br />
Overall in the first six problems, the exercise of forging a 1024-bit RSA signature (when e=3) was both the most interesting and the most challenging.<br />
<br />
<a href="https://github.com/tkuriyama/cryptopals/tree/master/set6">https://github.com/tkuriyama/cryptopals/tree/master/set6</a>THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-75079801239639945572017-11-23T06:52:00.002-08:002017-11-23T06:52:33.860-08:00Cryptopals Set 5 - F#<br />
Set 5 was advertised as difficult, but I found the implementations to be quicker that previous sets as they involve more number theory and less programming.<br />
<br />
<a href="https://github.com/tkuriyama/cryptopals/tree/master/set5">https://github.com/tkuriyama/cryptopals/tree/master/set5</a><br />
<br />
I took a few implementation shortcuts (each of them a good exercise to do properly, but I'd rather forge ahead and get through the cryptographic concepts at this point):<br />
<ul>
<li>Client-server interactions are simulated (still haven't sorted out F# package manager yet)</li>
<li>Prime numbers are drawn from known list rather than generated </li>
<li>Cube root solving is ignored (p40 just tests the result against the cube of the original message, rather than testing the cube root of the result against the original message)</li>
</ul>
<div>
I spent some time trying to implement Newton's method of approximating roots, which worked fine for square roots but in my implementation almost always did not converge for cube roots (once a guess became negative, it stayed negative... how to constrain to positive numbers while improving the guess in each iteration?). Something else to investigate in the future.</div>
THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.comtag:blogger.com,1999:blog-6814236017266358019.post-56970106656291120522017-10-29T15:04:00.001-07:002017-10-29T15:06:02.168-07:00Cryptopals Set 4<br />
As advertised, Set 4 was easier to work through than Set 3.<br />
<br />
<a href="https://github.com/tkuriyama/cryptopals/tree/master/set4">https://github.com/tkuriyama/cryptopals/tree/master/set4</a><br />
<br />
For better or for worse, I couldn't actually find implementations of SHA-1 and MD4 in F#, so I ended up implementing them using a combination of the standard descriptions and C# / Python implementations. (The MD4 implementation is still incorrect somewhere, so I'll probably need to fix it before attempting Wang's attack later on in the challenges.) As with the Mersenne Twister, there is something very reassuring about being forced to implement each digest iteration in a pure fashion without mutations.<br />
<br />
For the SHA1-HMAC timing leak attacks, I fell back to Python (trying Python 3!) since I haven't yet been able to get Paket / Nuget to work on my OS X machine. The F# tooling via Visual Studio for Mac seems like it is coming along, but I'm still trying to work in emacs... I'd like to play around with Suave and some of F#'s HTTP message handling libraries at some point. Meanwhile, setting up a virtualenv for Python 3 and running a tiny server via Flask was incredibly easy.<br />
<br />
<br />THKhttp://www.blogger.com/profile/12512759470164124692noreply@blogger.com