Add Reflection Module Proposal

[scolsen]

Inspired by @sdilts excellent proposal for resource handlers, I'd like to open a proposal for a Reflection module that (hopefully) achieves a similar level of fidelity.

Why?

The purpose of the Reflection module is to give authors macro/dynamic/pre-compile time insight into the properties of the forms, in particular, of the forms that define the bindings in the current environment. One can check the arity of a function, whether a given binding is a macro, function, or dynamic function, whether a def binds a name to a static value or a form that requires evaluation, whether the name of a function satisfies certain criteria, and even details about a function's body.

This functionality is only useful at the macro level, when one might generate a series of new forms based on the contents and properties of some forms previously defined.

Example Use Case

Let's say we want to create a generic version of the curry function. Our function should take a function, f, of any arity, figure out how many argument's it's been provided, and generate a requisite function to handle taking the remaining arguments required by f. With the Reflection module, we can achieve this using the proposed arity function:

(it's about 2am here, so I'm not paying too close attention to correctness, hope this gets the point across!)

(defndyanmic gen-arg-names [x acc] 
  (if (> 0 x)
       (gen-arg-names (- x 1) (append acc (gensym x)))
       acc))

;; assume concat has the type: (Fn [(List List)] List)
(defndynamic curry-internal [f args remaining]
  (list 'fn (gen-arg-names remaining (array)) 
    (concat (list f) args (gen-arg-names remaining (list)))))

(defndynamic curry [f :rest args]
  (curry-internal f args (- (arity f) (length args)))

(defn foo [x y z] x)
(curry 'foo "hello")
=> (fn [a1 a2] (foo "hello" a1 a2))
(defn bar [x y z g w] x)
(curry 'bar "hello" "world")
=> (fn [a1 a2 a3] (foo "hello" "world" a1 a2 a3))

Another Example Use Case

I'm working on a library now that attempts to provide a macro-based implementation of "typeclasses" for carp. This approach requires, it turns out, a good amount of introspection. One needs to take a look at various definitions in the environment and check their properties to ensure they meet certain criteria. For example, in my approach, one implements a typeclass using a deftypeclass macro. The macro, to really be robust, needs to verify:

• the number of type parameters of a type definition passed to the macro.
• whether the user passed interfaces, and whether these interfaces either return instances of the typeclass or take it as arguments.

This requires inspecting the contents of definitions passed to the macro by the user. At present, the user needs to pass in the defining forms themselves for the macro to work--however, if the macro could call utility functions that facilitate the inspection of bindings, the user could simply pass bound names instead of definitions.

This:

(deftypeclass (Monad a) (definterface return (Fn [a] (Monad a))))
(Monad (deftype (Maybe a) (Just [a]) (Nothing [])))

becomes this:

(definterface return (Fn [a] b))
(deftypeclass (Monad a) '(return join)) ;; assuming join is also defined somewhere
(Monad Maybe) ;; like most languages, the type declaration does not have to be specially 
;; passed to the macro, potentially restricting its use, but can instead be used flexibly,
;; with or without the "typeclass"

Which makes the macros easier to use and more adaptable, and prevents the interfaces from being "captured" by the macro, retaining maximal generality (in the first example, the interface is defined within the confines of the macro and only usable based on whatever the macro decides to do with the interface definition it's given, whereas, in the second instance, a highly generic interface is both available to whatever modules want to implement it, as well as the macro for defining a typeclass).

Reflection Module

In order to support the use-case described in the section above, as well as a number of other macrological use cases, I propose adding Reflection submodule to the existing Dynamic module, that exposes the following functions, expressed as pseudo signatures:

(defmodule Reflection
  ;; Returns true when the binding resolves to a `defn` form.
  (defn? (Fn [Binding] Bool))
  ;; Returns true when the binding resolves to a `defndynamic form`
  (dynamic? (Fn [Binding] Bool))
  ;; Returns true when the binding resolves to a `def` form
  (def? (Fn [Binding] Bool))
  ;; Returns true when the binding resolves to a `defmacro` form
  (macro? (Fn [Binding] Bool))
  ;; Returns the arity, number of arguments, of function bindings. 
  (arity (Fn [Binding] Int))
  ;; Returns true when the return value of a function or def form is a static value, 
  ;; false when it requires evaluation. 
  (static? (Fn [Binding] Bool))
  ;; Returns true if the function contains a possible recursive call, i.e. the binding name is 
  ;; referred to in the function body.
  (recursive? (Fn [Binding] Bool))
)

I'd also like to support the following functions, which at present, afaict, cannot be implemented using the current evaluator:

• deftype?: Can't be implemented at present. Unlike functions, types do not resolve to their type definitions. while, 'foo resolves to, e.g. (defn foo [x] x) 'Bar presently resolves to just Bar, even if there's a corresponding (deftype Bar Nothing).
• arity on types: Because of the limitation described above (we can't retrieve the definition of a type), arity cannot tell us the number of type variables a given type takes, which could be useful information.
• enum?: Returns true if a given type is an enumeration, i.e. (deftype Bar A B C)Again, because of the same limitation around types, currently impossible to implement in pure carp.

Alternatives

Special Commands

Other functions that implement similar "reflective" behavior are already provided as special commands, for example the members function on structs and sumtypes. This suggests that perhaps some of the functions proposed here, if deemed useful, should similarly be implemented as commands.

I motion against this simply because Carp already provides us the ability to gather this reflective information in Carp itself, so, rather than bloat the compiler with additional special functionality, we can simply implement the functions as a carp module. To me, this feels cleaner and easier to manage and it might help keep the compiler complexity lower.

Third Party Library

Perhaps these functions don't belong in core carp at all, but should be implemented as a third party library, maintained separately and adopted only by those who want to use it. This approach has the benefit of keeping the core language libs small and simple, and there's nothing in particular that recommends against it aside from ubiquity/availability of the utilities.

Thanks for reading! Let me know if you have any thoughts. I'm happy to implement this as a separate library, but figured I'd open a discussion to see if there's any interest for this sort of thing in core.

[hellerve]

TL;DR: I’m in favor and @scolsen is an amazing human being.

Thank you for this thoughtful proposal! This is amazing!

I concur with you that this would be fun and interesting. I also think that most of this should be implemented in the standard library (i.e. not in a third party library, and not as special forms).

For this to work reliably we have to be a bit more precise about the Carp evaluator, though, and really clearly communicate the proposed semantics—make it less ad-hoc, if you will—, something that hasn’t been attempted yet. A big dynamic undertaking like this would really be helped by a very thought-through compile-time interpreter.

I’m as of yet unsure what should be provided by the compiler in the way of special forms to make this happen or whether a few tweaks of existing forms could get us far already—as the problem around deftype? suggests. Do you already have some ideas for this?

[scolsen]

Thanks @hellerve! :) I find you equally amazing! And I'm confident that if we're both looking at this, we can take it a long ways!

Thinking through and being explicit about the evaluator's semantics seems like a great idea--Like you mention, the evaluator's semantics would need to be in a more or less well-defined/stable state, or have some kind of standard or specification around them to ensure these methods can be implemented in carp itself. A good number of these functions are definable already[1], but if the evaluator suddenly changes out from underneath us (if we were to decide, for example, that passing a naked binding like foo should be a no-op instead of returning the defining form) they'd all break instantly.

I'm not totally sure what modifications are necessary to get the deftype case working--it must be possible because members is fairly analogous--only it returns a portion of the deftype form instead of the complete definition (and if we provide the special command necessary to return the entire deftype form for a binding, members should also be implementable in carp itself, instead of as a special command). I played around with a special command for a little while in efforts to make this work, but I couldn't seem to figure it out. I'm not sure if part of it the difficulty relates to #555. It's possible I was simply missing something, I can try taking another look.

[1]: For example, here's a valid definition of the arity function in the current version of Carp:

;; Checks that a form is  "function-like", notably, that it has an array specifying 
;; bindable variables in a body. defn, defndynamic, and defmacro 
;; all satisfy this stipulation.
(defndynamic function-form? [binding]
  (if (not (list? binding))
       false
       (array? (caddr binding))))

(defndynamic arity [binding]
  (if (not (function-form? binding))
       ;; we could just return 0 here as well, instead of erroring out.
       (macro-error "arity passed a non-function form.")
       (length (caddr binding))))

(defn foo [x] x)
(defn bar [x y z] x)
(def baz 2)

(arity foo)
; => 1
(arity bar)
; => 3
(function-form? baz)
; => false
(arity baz)
; => arity passed a non-function form at ...
;; passing an undefined symbol works the same as passing an undefined symbol 
;; to the evaluator at the top level.
(arity qux)
; => can't find symbol qux at ...

[hellerve]

I too often have trouble with more advanced macros (like the builder macro) because of #555 and the evaluator hanging on certain inputs—like in #409—, so I guess step 1 would be tackling those bits and any other bugs that we come across along the way.

Relatedly, I was thinking of a kind of destructuring pattern match form for compile time that would make this simple (I’ll put this in another feature request soonishly) which would change function form to something like this:

(defn function-form? [binding]
  ; maybe another name would be better to avoid conclusion with the existing match form
  (match binding
     (defn _ [_*] _) true
     _ false))

I don’t think this is required for the feature discussed in this issue, but I do think that it would help make the checkers more readable and robust.

[scolsen]

Whoa! That would be really sweet! Destructing on forms looks ultra powerful. 💪

I do think naming it something other than match might be good, just because match is so fundamental when working with sumtypes--it might be good to keep it limited to one use. As for an alternative name...that's the hard part. Part of me likes keeping match as a suffix but prefixing it with something to make the context clearer.

(literal-match binding
     (defn _ [_*] _) true
     _ false))

Or we could reference the lisp lexicon :D

(s-match binding
     (defn _ [_*] _) true
     _ false))

;; or 

(s-expression binding
     (defn _ [_*] _) true
     _ false))

;; or even
;;Might be too cheeky but I kind of like it since carp already has a `c` function 
; that does a sort of similar thing. Then again, the single character name is a bit esoteric looking.
(s binding
     (defn _ [_*] _) true
     _ false))

I can look into #555, best case scenario it's just a matter of making the evaluator more precise for the edge cases @eriksvedang pointed out in the issue.

[eriksvedang]

This idea of a reflection module seems really cool, I'm all in! By adding it to core and writing tests we can make sure that it will keep working.

I think it's fine to re-use names like match but give them slightly different semantics, that's what we do with the other special forms already. I actually think that the statically compiled version of match should try to become more powerful with additions like other kinds of types (numbers, strings, structs, etc), destructuring, and so on. So the dynamic version "leading the way" is no problem.

When it comes to the inprecise semantics of dynamic eval I agree that it's too buggy and unreliable as it is now. Basically the code in Eval.hs & Expand.hs is in need of a very thorough refactoring and clean up. Perhaps we should couple this with a document that pinpoints the semantics, both in static and dynamic code. It could clarify the operational semantic in a terse but human-friendly way in regards to things like order of evaluation, undefined behaviour, etc. I've never done something like that though so perhaps it's way more work than I expect. But if you guys think it's worth a shot, we could add a Semantics.md in the docs directory and start filling it in?

[hellerve]

I think this is a good idea, but it needs to be stewarded by someone who has the time to do most of the prototyping work for this document. I think I’ll have that time in October, but I’m not quite sure yet. If anyone else wants to do it and has time earlier that’d be fantastic!

[scolsen]

I could start a draft for the doc now, devoting approximately 1h of time to fleshing it out each evening.

You both know way more about Carp than I do though, so I would need a healthy dose of your input in reviews!

[hellerve]

I’m happy to review anything you write!

[eriksvedang]

Yay! I will help as much as I can! (and start doing the rewrite when we have something we're happy with)

[eriksvedang]

I've created this document now, it can be found here: https://github.com/carp-lang/Carp/blob/master/docs/DynamicSemantics.md

Any help in fleshing it out will be greatly appreciated!

[scolsen]

Amazing!

Business business, I've already missed the first Carp Friday :/ -- but I will certainly try to contribute to this!

[eriksvedang]

There were some discussion in the chat about changing some existing functions like members and adding things like struct? etc. I think those are great ideas, if anyone has a more clear proposal for a better API, please share!

[scolsen]

I think these functions from the op would still be useful:

;; Returns true when the binding resolves to a `defn` form.
(defn? (Fn [Binding] Bool))
;; Returns true when the binding resolves to a `defndynamic form`
(dynamic? (Fn [Binding] Bool))
;; Returns true when the binding resolves to a `def` form
(def? (Fn [Binding] Bool))
;; Returns true when the binding resolves to a `defmacro` form
(macro? (Fn [Binding] Bool))
;; Returns the arity, number of arguments, of function bindings. 
(arity (Fn [Binding] Int))
;; Returns true when the return value of a function or def form is a static value, 
;; false when it requires evaluation. 
(static? (Fn [Binding] Bool))
;; Returns true if the function contains a possible recursive call, i.e. the binding name is 
;; referred to in the function body.
(recursive? (Fn [Binding] Bool))

If we introduce a single new primitive called form or definition that always returns the underlying form (XObj) associated with a binding, these can be implemented in Carp directly, and the only compiler change we'd need is the single new primitive.

actually, if you currently define a Dynamic id function, it already works this way for some types but not for all:

鲤 (defndynamic id [x] x)
鲤 (defn foo [x] 2)
鲤 (id foo)
=> (defn foo [x] 2)
鲤 (id Maybe)
=> Maybe
鲤 (id Pair)
=> Pair
鲤 (def bar 4)
鲤 (id bar)
=> (def bar 4)
鲤 (defndynamic goo [x] x)
鲤 (id goo)
=> (dynamic goo [x] x)

I think we should extend the defn and def style behaviors to do the same for things like Maybe (so it'd return (deftype (Maybe a) (Just [a]) (Nothing [])) and stick this functionality behind a new primitive called form or s-expression or Dynamic.id or definition.

All the other functions can then be implemented in terms of this one. e.g.

(defndynamic defn? [binding] 
  (let [form (definition binding)]
    (= 'defn (car form)))

One can even implement type checking functions like struct? using this function, but it's a tad more complex (e.g. would have to check that the binding returns a deftype then inspect the cases to see whether or not they are sumtype style or struct style).

This would make our compiler changes small and allow us to implement a lot of great introspection functions in carp itself.