Lisplog

Blogging in Lisp

Search

Feed Aggregator

Rendered on Wed, 17 Jan 2018 01:32:27 GMT  newer latest older 
Next udpate: Wed, 17 Jan 2018 02:00:00 GMT feeds

Constant time immutable hash map?

via Elm Discourse - Latest posts by @robin.heggelund Robin Heggelund Hansen on Tue, 16 Jan 2018 22:34:31 GMT

Yeah, the key word here is “effectively” (constant time). Another thing to mention is that n is never greater than 7 (32^6.4 maxes out an int).

I’m already exploring something like this for Elm, just need to find the time. An implementation for Elm already exists (https://github.com/Skinney/collections-ng) but there are bunch of things that can be improved to increase the performance, like a proper hash function and applying lessons learned from Array.Hamt. Expect to read more about this soon.

Constant time immutable hash map?

via Elm Discourse - Latest posts by @ilias Ilias Van Peer on Tue, 16 Jan 2018 21:30:38 GMT

Hash array mapped tries usually have a bunch of “slots” per level. So where a binary tree has branching factor of 2, a HAMT will usually have many more. Array.Hamt uses 32, for example. So, with a good hashing function, the depth becomes log32(n), which means that even for an array of 1024 elements, you only need 2 levels in the tree.

In practice, that’s “close enough” to call it constant time.

Constant time immutable hash map?

via Elm Discourse - Latest posts by @rtfeldman Richard Feldman on Tue, 16 Jan 2018 20:43:39 GMT

:thinking: I thought HAMTs had logarithmic access times…maybe I’m mistaken?

cc @robin.heggelund

Constant time immutable hash map?

via Elm Discourse - Latest posts by @matt.cheely on Tue, 16 Jan 2018 20:28:45 GMT

The docs say it uses a hash trie, which I suspect is more specifically a hash array mapped trie. Clojure also uses a HAMPT map and describes performance characteristics as “effectively constant-time”. I’ve seen some good Clojure talks on the topic, although it seems I didn’t save links to any of them.

Constant time immutable hash map?

via Elm Discourse - Latest posts by @rtfeldman Richard Feldman on Tue, 16 Jan 2018 18:35:31 GMT

Scala claims to have “effectively constant” lookup, add, and remove for their immutable HashMap and HashSet implementations - http://docs.scala-lang.org/overviews/collections/performance-characteristics.html

Does anyone know how Scala’s implementation managed to get those characteristics? I’m trying to determine if it would be possible to implement a collection like that (assuming the caller specified the hashing function) in Elm.

Quicklisp news: The Quicklisp local-projects mechanism

via Planet Lisp by on Tue, 16 Jan 2018 16:29:00 GMT

Quicklisp provides a lot of software, but there's also a simple way to load things that Quicklisp doesn't provide. That same mechanism can be used to override libraries Quicklisp does provide.

The local projects mechanism sets up a special directory that is automatically scanned for software to load. Here are a few quick examples.

Trying a library not in Quicklisp

First, imagine that you just heard about a great new library and want to try it. However, it's not available through Quicklisp yet, only through a git repository on https://example.com/fun-project.git. One easy way to try it:
$ cd ~/quicklisp/local-projects
$ git clone https://example.com/fun-project.git
After the git command completes, and there is a fun-project subdirectory with a fun-project/fun-project.asd file present, the system is visible to ASDF and can be loaded either with ql:quickload or asdf:find-system. When loaded through ql:quickload, Quicklisp will automatically fetch and load any prerequisites automatically as well.

Overriding a library in Quicklisp

Second, imagine that you want to hack on a library that Quicklisp already provides. You don't want to load and hack on the version from Quicklisp - that software is not under version control, and just represents a snapshot of the project at a particular point in time.

Once again, the procedure is to put the software in the ~/quicklisp/local-projects/ directory:
$ cd ~/quicklisp/local-projects/
$ git clone https://github.com/xach/vecto.git
After the git command completes, (ql:quickload "vecto") will load the library from local-projects rather than from the standard Quicklisp release.

How it works

The local-projects mechanism is relatively automatic. Here's how it works underneath, and how to fix problems that might crop up.

ASDF has an extensible mechansim (the asdf:*system-definition-search-functions* variable) for searching for system files. Quicklisp extends this mechanism with a function that does the following, all in the context of the local-projectsdirectory.
  1. If there is no file named system-index.txt, it is created by scanning the directory tree for system files (matching "*.asd"). Each pathname is added to the file.
  2. If the system-index.txt file exists, but its timestamp is older than its containing directory, the directory is rescanned and the index recreated.
  3. The system-index.txt is searched for any entry with a pathname-name that matches the desired system name. If there's a match, matching pathname is probed. If it still exists, it is returned. If it has disappeared, the system-index.txt is recreated as in step 1 and the search is retried.
  4. Otherwise the system search is deferred to the remaining ASDF system search functions.
When there are multiple system files with the same name in the directory tree, the one with the shortest full pathname name is returned. In the case of a pathname length tie, the one that is #'string< is returned.

Timestamp problems can sometimes crop up with step 2 above. For example, if you have a directory local-projects/my-project/ and you create local-projects/my-project/supporting-system.asd, the timestamp of local-projects/ is not updated and supporting-system.asd won't be automatically added to the system index file.

There are a couple ways to force an update of the system index file. Within Lisp, you can use (ql:register-local-projects) to immediately regenerate system-index.txt. Outside of Lisp, you can use the touch command (or an equivalent) to update the timestamp of the local-projects directory, which will trigger a rebuild of the index on the next attempt to find systems..

Because of how the system index file is created (and recreated as needed), Quicklisp must have write access to the local-projects directory to make use of it.

Configuration

The local-projects mechanism is configured through a special variable ql:*local-project-directories*. By default, it includes only the local-projects subdirectory in the Quicklisp install directory, but you can add or remove directories at any time to have more places scanned for systems.
To disable the local-projects mechanism entirely, set ql:*local-project-directories* to NIL.

Quicklisp news: Build failures with ASDF 3.3.1

via Planet Lisp by on Tue, 16 Jan 2018 15:48:00 GMT

SBCL 1.4.3 ships with ASDF 3.3.1, and a number of Quicklisp projects have build problems as a result. Linedit, mgl, micmac, cl-string-match, and others are affected.

Here is a build failure report for yesterday. (You can ignore the gendl failures - it's a special case.) If anyone has ways to fix these projects, please do so as soon as you can - otherwise they will be removed from the January Quicklisp dist update in a few weeks.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rtfeldman Richard Feldman on Tue, 16 Jan 2018 16:31:37 GMT

Sure!

At least in Elm 0.18, SPA routing between pages is by far the most common use case. (I expect that in a future release, code splitting will result in an alternative API for doing this, but Html.map seems to be the right approach for today.)

The other two modules (besides Main) that use Html.map are Home and Profile. Both of them use it for Feed.

The reason I used it for Feed is that Feed has 6 Msg values and their update logic is nontrivial.

I default to not creating Feed.Msg and Feed.update, because they’re usually not worth the cost, but this is one of the rare cases where the alternative would be worse! In the alternative world, Feed.view would have to accept 6 different toMsg functions, every page that used a Feed would be required to add 6 constructors to its own Msg, and the corresponding update clauses would have to call ~6 different Feed functions because their implementations are nontrivial.

Because of the high Msg count and nontrivial update logic that goes with them, in this case—unlike every other case in the app—the comparatively lightweight approach was to use Feed.Msg and Feed.update…even though everywhere else in the project, a view function alone was the better API.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rupert Rupert Smith on Tue, 16 Jan 2018 16:30:57 GMT

I feel I should also comment on this too. OO design patterns are to a significant degree influenced by Parnas’ modular design principles. Those principles manifest themselves in OO as encapsulating state within the object, and providing a minimal set of methods on the object to interact with that state. That is related state and functionality is kept together (high cohesion) and the API is kept minimal (low coupling).

Even though Elm takes a different path to OO, I still think that Parnas’ modular design principles can find valid and useful expression in Elm. Elm provides 3 levels on which this can be explored; at the functional language level, at the module level and at the package level. The package level is the one that demands it the most, since each package really is a module of re-usable software.

It would be quite interesting to explore the idea of a retraining program from OO to Elm. First understand the principles of OO in the context of Parnas, then explore all the ways that Parnas can be expressed in Elm, and out of those, which ones lead to the most productive coding patterns that allow safe and better software to be written.

To me, Parnas is the master mental model that runs through everything I do that is related to computer software.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rupert Rupert Smith on Tue, 16 Jan 2018 16:04:30 GMT

BTW, would you care to comment on what motivated you to use it in the elm-spa-example, in the few places that you did use it?

It is interesting to learn about what the limits of the techniques to avoid it are, and what factors justify its use. Or perhaps you would consider refactoring elm-spa-example to completely avoid it, were you to do it again?

I count 8 places it is used, 7 of the pages under Pages/ are child MVUs, and so is Views/Article/Feed.elm. I must be counting differently to you as you say there are only 3 places, but perhaps you are counting the parent MVUs.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rupert Rupert Smith on Tue, 16 Jan 2018 15:59:25 GMT

I do recognize this as being true BTW, I just did not make a good job of stating it clearly enough in the opening post. However, as I can see it used in the elm-spa-example, I think it is important to acknowledge that it is a valid technique and there are occasions where we resort to it. (And as you can see from my code, I resorted to it too soon).

I’ll start a new thread I think to discuss the Program convolution - now that I’ve gone from grasping at ideas to a rough outline I think I have something that will work nicely for what I am trying to do with my auth package and its API. I will also try and provide some justification as to why I think it is a reasonable choice for what I am trying to do with that.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rtfeldman Richard Feldman on Tue, 16 Jan 2018 15:12:30 GMT

Sure, but I think the social key here is buy-in.

If some people on a team want to use [Elm/React/Vue/Angular] but others on the team prefer the way [a different technoloy] solves a particular problem, there’s going to be friction!

None of these technologies will ever be all things to all people; I think they’re all best served by playing to their own strengths, and leaving teams to figure out which strengths appeal most to them.

Well no, because I don’t use everything in CSS. :smile:

One of the design goals of elm-css is to provide a typed interface to the CSS API. The minimal API to achieve that goal is quite large!

Model is practically the opposite of global mutable variables!

Any code in a program can read and write to global mutable variables. In stark contrast, permission to both read and write Model are extremely strictly controlled. view and subscriptions get read-only access; to them, Model is an immutable constant. Only update has permission to modify Model, and it can create more granular permissions by delegating to functions that work with subsets of Model. Outside of those 3 pure functions, the rest of the program can’t even read it!

It’d be more accurate to say that Model has nothing in common with global mutable variables.

The implication here is that “structuring Elm programs as nested M/V/U triplets is a reasonable choice, but how to do it nicely is an unsolved design problem,” even though the language’s foundational design, Occam’s Razor, and a mountain of historical evidence all say the reality is actually that “structuring Elm programs as nested M/V/U triplets is a mistake.”

The most recent case in point is earlier in this thread. I showed how to refactor an API that used a nested Model/View/Update design into a much simpler API that did not use it. How lucky was I that out of the 1 (one) motivating code example for nested M/V/U, it turned out there was a simpler, nicer API within reach…that was obtained by doing nothing more than declining to use nested M/V/U in the first place?

This was not a lucky coincidence; I’ve seen this so many times, I’ve lost count! Nested M/V/U turning out to be a mistake in practice is normal.

As an aside, I never could have imagined the teaching challenge that our industry’s OO monoculture would create for Elm. It’s nobody’s fault—people come from OO backgrounds and reflexively follow OO design patterns. I know that feeling well, since I did it myself when I was starting out!—but it’s surprising nonetheless.

Literal Names Policy (i.e. how to name packages)

via Elm Discourse - Latest posts by @bob-shelline Bob Shelline on Tue, 16 Jan 2018 14:44:44 GMT

I have mixed feelings about the literal naming policy, and I agree with @Sebastian. It is really nice to be able to search for a package based on its functionality, but it makes it complicated to try and find a specific package. It’s confusing and difficult to find the version of Elm WebGL that is the correct, up-to-date version, winding a path through a deprecated elm-community package, to a specific author’s version of that package, back to the up-to-date elm-community version.

I mean… Elm isn’t called “delightful language for reliable webapps”. That’s its description. It can be handy to have some marketing and presentation.

Is TEA a comonad?

via Elm Discourse - Latest posts by @MarkHamburg Mark Hamburg on Tue, 16 Jan 2018 14:26:50 GMT

That’s more or less where I settled but with the caveat that if changing APIs is going to cause excessively widespread ripples — i.e., across multiple projects because the view function is actually being written by a team trying to establish corporate UX standards — or within a project with multiple engineers there are engineers who will try hard to avoid updating either lots of code or other people’s code, then one may want to consider use cases beyond the present case. I’ve worked with engineers who would have no concerns with updating something to support animations even if it wasn’t their code and even if it meant potentially touching a bunch of call sites (though adding viewWithAnimations might be a better if inconsistent choice in such a case) and I’ve worked with engineers who would say that they were just trying to use a control bar and clearly Elm sucks compared to whatever they came from before. Code exists in a social context as well as a technical context. Boilerplate causes friction. API updates cause friction. Which one matters depends on social factors.

Mark

P.S. What I suspect is an example of why API minimalism isn’t always the right choice: Have you actually had cause to use everything in your CSS library?

Is TEA a comonad?

via Elm Discourse - Latest posts by @rtfeldman Richard Feldman on Tue, 16 Jan 2018 13:53:31 GMT

For the love of all that is good in the world, please only when the design calls for it.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rtfeldman Richard Feldman on Tue, 16 Jan 2018 13:50:05 GMT

The relevant point is that shown doesn’t change based on any ControlBar state—it’s something strictly controlled by the caller. The typical Elm API for hiding something is to decline to render it. There’s no Html.Button.hide, for example—if you don’t want a button there, don’t call Html.button!

I changed the API to be like button: if the caller wants a ControlBar, they call ControlBar.view; otherwise, they don’t.

One background wroker, multiple views of the same state possible?

via Elm Discourse - Latest posts by @zinggi on Tue, 16 Jan 2018 13:49:47 GMT

Hi all :wave:

Before I come to the actual question, first the important background:

I’m working on a browser extension in Elm (WebExtension / Chrome Extension).

I want my extension to be running all the time in the background, so I created a Platform.program and start it as a worker inside my background script. This works well so far.

Now, I want to have different views on the internal state of my worker, e.g. one for the popup of the extension, another simpler one to inject into the current tab.

I do have an idea how I could do this, but I don’t like it very much:

I could create a new elm Program for each view that looks kinda like this:

port module Popup exposing (main)

import Html exposing (Html)
import Json.Encode exposing (Value)
import Background    -- This is my background worker
import MainView      -- A view of the background model


type alias Model =
    Result String Background.Model


init : Value -> ( Model, Cmd Msg )
init model =
    ( Background.decodeModel model, Cmd.none )


type Msg
    = NewState Value
    | BackgroundMsg Background.Msg


update : Msg -> Model -> ( Model, Cmd msg )
update msg model =
    case msg of
        NewState bgModel ->
            ( Background.decodeModel bgModel, Cmd.none )

        BackgroundMsg bgMsg ->
            ( model, sendMsgToBackground (Background.encodeMsg bgMsg) )


port sendMsgToBackground : Value -> Cmd msg


port newState : (Value -> msg) -> Sub msg


subs : Model -> Sub Msg
subs model =
    [ Result.map Background.subs model
        |> Result.withDefault Sub.none
        |> Sub.map BackgroundMsg
    , newState NewState
    ]
        |> Sub.batch


view : Model -> Html Msg
view model =
    Result.map MainView.view model
        |> Result.withDefault (Html.text "")
        |> Html.map BackgroundMsg


main : Program Value Model Msg
main =
    Html.programWithFlags
        { init = init
        , update = update
        , view = view
        , subscriptions = subs
        }

Then, I could wire up those ports and let the background page communicate with those multiple frontends this way.

However I don’t like this solution.

Since my Model and Msg both contain union types, I would have to encode/decode the entire thing as a Json.Value, as the automatic conversation elm does can’t deal with union types.
Plus, this is a lot of unnecessary encoding/decoding. I don’t know if that will impact performance.
Plus, an identical version of the state now lives at multiple locations in memory.
Additionally, that’s a lot of boilerplate…

My question now is the following:

Is there a better way?
Can I somehow share the state of one elm program with another?

I’m also prepared to write native/kernel code if that would help reduce the boilerplate.

Is TEA a comonad?

via Elm Discourse - Latest posts by @rupert Rupert Smith on Tue, 16 Jan 2018 12:00:10 GMT

So here is a rough sketch of what I was thinking.

There are 2 programs, one is subscribed to the a clock tick, it sends this as a message to another program which receives it and displays it.

I used the Html.Alternative.Program type as a starting point, just because it already had an implementation of the Day convolution. I think I would actually not use this Program type, but the Html.Program type.

My authentication package could be a headless Platform.Program(WithChannel), and my UI an Html.Program(WithChannel). I could evolve the channel structure a bit so that these two programs end up with nice APIs into each other. The UI can send/invoke login, logout, and unauthed and the authentication program can send/invoke a small model describing the current authentication state.

Nice clean APIs, type checking on the messages, each program has zero knowledge of the internal model of the other and easy to integrate with a suitable program convolution function.

 newer latest older