Simplify lookup

[jacereda]

I was thinking that having a lookup system mimicking the one in Forth would simplify the Haskell side and give more power to the Carp side.

https://forth-standard.org/standard/search/SET-ORDER

Basically, the haskell side would provide equivalents to:

• get-order: obtain current lookup order
• set-order: set current lookup order
• get-current: get the environment where current definitions are placed in.
• set-current: establish where new definitions will be placed.

We would also need the equivalent of Forth's wordlist.

[hellerve]

This is an awesome idea! I think adding more malleability like this is always a good idea; I also don’t think that moving away from our hardocded solution would be that much more difficult. This would also lend itself well to being able to select different lookup contexts (like primitives, commands, static, dynamic, etc.)!

[eriksvedang]

Intriguing. How would the code look when using this?

[scolsen]

I like the idea generally speaking, but one property of the current set up that's pretty nice is that it's monadic, so one can flexibly perform operations on results "on-demand" and then resume a lookup somewhere else, e.g. one can:

-- assume updateBinder returns (Env, Binder)
-- lookup a binder in one env, update it, look it up in another env, update it, return both updated envs
lookupBinder env foo >>= updateBinder env 
>>= \(e, b) -> lookupBinder otherEnv (binderName b)
>>= updateBinder otherEnv >>= \(otherE, otherB) -> (e, otherE)

to express looking up a binder in one env, updating it, looking it up in another env, updating it there as well, etc. This is obviously a contrived example, but my point is that when lookups are independent and monadic, it's easy to express different sequences of lookups/transformations using combinators.

I might be making an incorrect assumption, but it sounds like using this approach the order of lookups would not be as modular and would be internally encapsulated in some type or in a module somewhere. So, one would be bound to manipulating things in a more "record like" style should we need to adjust lookup order anywhere--which is fine in it's own right, but I think expressing things in terms of pure functions and combinators is really where haskell shines. A lookup takes any old value of Env and just possibly returns a Binder. While this leads to some inconsistencies in the way we use it in some places, I think that can also be solved by defining lookup "stanzas" at a higher level--defining some functions that have an order, e.g. something like (again contrived):

-- lookup path in Dynamic and Global, if found, update path using f in both, when successful, return the context with the updated environments
updateDynamicThenGlobal :: (Binder -> Binder) -> SymPath -> Context -> Maybe Context

Using this approach, we'd instead have something like a global state that manages the way we preform lookups. This would be a huge gain in terms of consistency of lookup code across the compiler, but we'd sacrifice some expressivity and flexibility as a result (I'm assuming). I guess we should determine which is more important. At the moment it seems like consistency is more important, so I think such a change is probably worthwhile even though I have some concerns about expressivity.

[hellerve]

But wouldn’t making the lookup order dynamic just mean taking all of the parts of the monadic pipeline and making their order dynamic, in pseudocode reduce >>= lookup pipeline? More to the point, all lookup functions could stay as they are, but the code gluing them together wouldn’t have to be.

[scolsen]

But wouldn’t making the lookup order dynamic just mean taking all of the parts of the monadic pipeline and making their order dynamic, in pseudocode reduce >>= lookup pipeline? More to the point, all lookup functions could stay as they are, but the code gluing them together wouldn’t have to be.

ahhhh, I think I see what you're suggesting now, do you mean we'd abstract away the ordering somehow? So instead of writing:

lookup e1 foo  <|>  lookup e2 foo

you'd write:

lookup order (doSomething to found binder >>= do something else to found binder)

I think that makes sense, and it does seem useful, but it also makes situations like the one I commented on above more complicated since you need to juggle more than one Maybe monad if you, say, want to get a module binder from both the value and type envs:

fromMaybe (lookup typeFirst (id)), fromMaybe (lookup globalFirst (id))

or something like that -- but I may also be misunderstanding here--it's not 100% clear to me how the proposed functions and wordlist data structure would play into this.

[scolsen]

I guess another way of putting this:

I quite like the notion of abstracting order functionally--passing an Order type as an argument to a generic lookup function--I dislike the notion of abstracting it via type indirection (introducing a new record type for lookups).

[hellerve]

I think I was still not quite clear about this: what I want to make scriptable is the way in which we perform the lookup, i.e. where to lookup when. This means that this code:

        tryAllLookups =
          ( case preference of
                PreferDynamic -> tryDynamicLookup
                PreferGlobal -> (tryLookup spath <|> tryDynamicLookup)
          )
            <|> (if null p then tryInternalLookup spath else tryLookup spath)

would be hackable instead of hardcoded. You’d be able to specify what lookup is performed first, and maybe even inject your own logic into there (though that second part is a little difficult to envision for me as of yet).

An example. Say we are in a dynamic environment, and from within Carp we want to script lookup logic. A simple API—not necessarily the one @jacereda is suggesting, but maybe good as an illustration—would be this:

(defndynamic swap-dynamic-and-static-lookup []
  (let [lookups (get-lookup-order) ; could for instance return '(dynamic static internal)
        fst (car lookups)
        snd (cadr lookups)]
    (set-lookup-order (cons snd (cons fst (caddr lookups))))))

With that function, we could do fun stuff, like

(defndynamic example []
  (let-do [x +] ; dynamic +, we’re in a dynamic env
    (swap-dynamic-and-static-lookup)
    (let [y +] ; the interface +, because we’re looking at statics
      (list x y))))

In terms of implementation, this would simply mean that the code above would have to be exchanged for something that looks at the current state of the lookup order in context, and determiness the lookup order based on that, instead of a hardcoded lookup.

[scolsen]

@hellerve thanks for the explanation! My disconnect was that I was limiting my thinking to haskell world, hah.

Yes, that seems like a very powerful feature indeed. I think as long as we can support this with sane defaults (so that only the users that really want to manually juggle lookups need to) it sounds great--we just need to maintain that balance of power/friendliness, there's definitely a segment of users that will want to totally ignore this and just be able to program using some sane default lookup order.

But it shouldn't be too hard to support both, right? Yes, I think this would be a great addition!

[hellerve]

I think the default would likely not change—the code would, but it would be completely unimportant to the users, since its behaviors would hopefully stay the same. The tiny fraction of users that need a different behavior would be able to use this feature to build really weird and powerful stuff, though.

On the other hand, there might be libraries that use the feature wrong (forgetting to reset the prior order, for instance), and that might lead to bugs that are hard to find—but such is life if you use advanced metaprogramming features, I guess?

[scolsen]

On the other hand, there might be libraries that use the feature wrong (forgetting to reset the prior order, for instance), and that might lead to bugs that are hard to find—but such is life if you use advanced metaprogramming features, I guess?

Yeah, I think we can just put that into the "warning: if you use a footgun you might lose a toe" category :)

[jacereda]

@hellerve is right in the interpretation. Just an example of how this could simplify the internals. We have With in the AST. Instead it could be something like:

(defmacro with [mod :rest forms]
  (let [orig (get-order)
    new (cons (quote mod) orig)
        ]
    (do
      (eval (cons 'set-order new))
      (eval forms)
      (eval (cons 'set-order orig)))))

Modules would be the equivalent of Forth wordlists (just a list of bindings). Symbols wouldn't have a SymPath. (Foo.Bar.baz) could be syntactic sugar for (with Foo (with Bar (baz))).

[scolsen]

@jacereda nice, with is certainly a very compelling use case for this, I suppose use could be implemented similarly too. I think it's a good idea! Might take a bit of work to get it right.

[jacereda]

I guess the same goes for defmodule. We have Mod in the AST but I guess it could just be implemented in dynamic land in terms of wordlist, set-order and set-current.

Which brings me to a question. Why are there so many Defxxx in the AST? Could we implement all of them in terms of Def?

[scolsen]

I guess the same goes for defmodule. We have Mod in the AST but I guess it could just be implemented in dynamic land in terms of wordlist, set-order and set-current.

Which brings me to a question. Why are there so many Defxxx in the AST? Could we implement all of them in terms of Def?

I believe we could, and some (most?) Lisps do it this way--defn would just be a macro that expands to (def x (fn ....))--but currently there are some discrepancies w/ def I think, so we'd have to fix those first.

[eriksvedang]

Many of those things only make sense as "defined things", no? I guess that something like a template could be passed around, but I'm also afraid that loosening the current restriction opens up a lot of corner cases and makes things too fluid. Would need more examples of how this would work to be convinced if it's merit.