Dynamic evaluator evaluates too much

[eriksvedang]

There is something wrong with the implementation of the dynamic evaluation of Carp code. Expressions returning things that can be evaluated (i.e. lists) are evaluated an "extra" time, which is often wrong. This extra step needs to be removed, and the reason it was added there investigated.

One simple example of how this bug manifests is that if you enter a quoted expression in the repl it will evaluate:

> '(+ 2 3)
=> 5

[eriksvedang]

The problem stems from Eval.hs, line 460. See comment there.

[scolsen]

So, straight up removing the hack and returning the evaluated form as is has the following effects:

1. When starting the repl, a bunch of meta-sets are echoed:

-> (meta-set! print-doc "doc" "Print the documentation for a binding.")
-> (meta-set! sig "doc" "Annotate a binding with the desired signature.")
-> (meta-set! print-sig "doc" "Print the annotated signature for a binding.")
-> (meta-set! hide "doc" "Mark a binding as hidden, this will make it not print with the 'info' command.")
-> (meta-set! private "doc" "Mark a binding as private, this will make it inaccessible from other modules.")
-> (meta-set! todo "doc" "sets the todo property for a binding.")
-> (meta-set! private? "doc" "Is this binding private?")
-> (meta-set! private? "todo" "This is buggy, will report true when meta is set to 'false'!")
-> (meta-set! hidden? "doc" "Is this binding hidden?")
-> (meta-set! hidden? "todo" "This is buggy, will report true when meta is set to 'false'!")
-> (meta-set! annotate "doc" "Add an annotation to this binding.")
-> (meta-set! defproject "doc" "Define a project configuration.")
-> (meta-set! const-assert "doc" "asserts that the expression `expr` is true at compile time.\nOtherwise it will fail with the message `msg`.\n\nThe expression must be evaluable at compile time.")
...many more meta-set! forms.

2. The vast majority of cases are unproblematic. Also, one no longer needs to quote certain forms that one needed to quote before:

(list 'foo)
; => (foo)

;; contrasted with carp as it stands right now, executing 
(list 'foo)
;; results in 
; I couldn’t find the symbol 'foo' at line 1, column 8 in 'REPL'.

Maybe you wanted one of the following?
    Bool
    doc
    fmt
    for
    not
    or
    todo 
;; the extra eval we're trying to fix here.

3. The case this workaround was designed to solve, notably, a dynamic function or macro that generates a definition, indeed results in the form itself--the definition doesn't get evaluated nor added to the environment:

鲮 (list 'defn 'foo (array) '2)
-> (defn foo [] 2)
鲮 foo
Can't find symbol 'foo' at REPL:1:1.

So! The way forward seems to be to specialize the workaround to the specific forms we need to account for, namely, a returned def, defn, defndynamic, defmacro, etc.

Ideally, we could simply remove the workaround and treat this as intended behavior. Returning a form that constitutes a definition and actually defining something are, after all, different things. We could argue that this is how macros/dynamic functions should work--they return forms--it's up to the user to determine when and how these forms are evaluated. However, there seems to be no way for the user to "force evaluation" of a form. Perhaps adding this functionality is the more appropriate solution?

I will open a PR that pursues 1. If I can figure it out, I'll also open a change that pursues the alternative of adding a function that forces evaluation of a form, as I think this gives the programer more control and keeps the semantics cleaner (if we use solution 1. carp users have to recall that some forms, when returned, are evaluated immediately, while others aren't--hardly convenient.)

[eriksvedang]

Thanks for your investigations! I have worked on removing the hack, and yes, the problem is to make the returned code from macros "execute". I haven't gotten to any conclusions though, I can mess around more with it today and write up any of my own findings here.

[hellerve]

How about these terms do not get evaluated unless they’re passed to an eval dynamic form? This is how a lot of other Lisps do it, and it would also buy us eval, which is either a great or a terrible idea.

[eriksvedang]

That would work, but then you'd have to wrap calls to macros in eval to get them to do anything, like:

(eval (doc foo "does something"))

I have a feeling this can be solved in a nicer way...
Exposing eval might be a good idea anyways though, I'm up for that!

[hellerve]

Not necessarily, you could do the eval inside the doc, but I agree that this isn’t necessarily super for all commands. Special-casing might be necessary for sure.

[eriksvedang]

Right, didn't think of that! Hmm, need to reconsider..!

[eriksvedang]

After looking through the code and poking at it a bit without much success, I think it would be beneficial if I do some kind of rewrite of the Eval module. Ideally we could decide on the desired semantics first though, so I have something more concrete to implement.

[scolsen]

The module as it is now is pretty beefy which makes it a little tricky to grok at times, so I think a rewrite could be good!

I actually like the eval approach. I think it gives programmers more control, plus, it establishes a nice boundary between macro code and evaluated code--to use a loose, forced analogy from haskell, eval is how we step out of the "macro monad". Like you mentioned @eriksvedang, the issue with eval is that having to call it manually on some forms is not ideal.

Is this issue only problematic in the REPL? Are there two passes for compilation--macro-expansion and then compile? Or are the REPL and compiler basically equivalent?

My sense is that we can skirt around the issue if we have two passes for the compiler, but not for the REPL. Macro calls in the source file should be expanded, and then we should compile the resulting code (this is, I think, roughly how its handled in common lisp). However, in the REPL, it might be a nicer experience to return only the result of expansion on evaluation of a macro call, providing an explicit method like eval to force evaluation of the result.

So, given this file:

(defmacro id-function [] 
  (list 'defn 'id (array 'x) 'x))

(id-function)

The following happens on compile/load:

• the call to (id-function) is expanded, yielding the new source for compilation:

(defmacro id-function [] 
  (list 'defn 'id (array 'x) 'x))

(defn id [x] x)

• The resulting code is then compiled and loaded into the environment.

When you load this file into the REPL then, the following forms are available:

• id-function, id

I think evaluating (id-function) in the REPL should be one-pass by default:

(id-function)
;; => (defn id [x] x)

If one wants to evaluate the result of a macro call in the REPL:

(eval (id-function))
;; => id redefined in environment...

This approach, I think, should make things like doc work while also fixing the too-much evaluation issue:

;; foo.carp
(doc foo "foo function")
(defn foo [x] x)

(load foo.carp)

Macro Expansion:

(meta-set! foo "doc" "foo function")
(defn foo [x] x)

load:

foo is brought into the environment, and its meta is set.

In other words, the evaluator just does one pass on whatever forms it encounters, the compiler is designed to do two evaluator passes (macro-expansion phase and compilation phase) and the REPL is equivalent to the evaluator (one pass). Not sure if this fairytale approach actually meshes with Carp's design, though!

[eriksvedang]

Interesting thoughts! I'm not sold on the idea of having the REPL and file loading be different things – right now they are exactly the same which means you can work interactively (with a file in your editor) sending forms to the REPL process mixed with the load:ing of files. Losing that seems like a steep price to pay, unfortunately.

I really like the analogy with a Haskell "macro monad" though! I guess that's what's used in template Haskell? And it also reminds me of the REPL in Idris where nothing is ever executed unless you tell it to be. Having that kind of more principled approach to the whole compile time programming model in Carp seems extremely worthwhile.

Inspired by @hellerve's comment I started thinking though... Since macros can call side-effecting code, perhaps the way to solve this with top-level "things" like doc is to have it not produce the code for setting the meta data, but rather just set the meta data on its own (returning Unit, or whatever). I will try this as a proof of concept in the current runtime and see if it works...

[eriksvedang]

... and that actually works. For some reason, adding this plus turning off the "double step evaluation" in executeCommand (Eval.hs:443) triggers a bug with functions within modules referring to the module itself (I think it has to do with documentation stubs), but the code for the doc macro and its siblings work:

(defmacro doc [name string]
  (meta-set! name "doc" string))

The take-away from this macro is that it's not so much a code generator as a compile time function that does not evaluate it's arguments before being applied. Any thoughts? :)

[hellerve]

I think this makes sense. As I see it, there are two distinct ways in which we use the evaluator:

• Evaluate code at compile time, which may or may not lead to code generation, and
• code generation itself.

I thus am now tempted to think the default workflow should be evaluation, and generating code should be a special case.

[scolsen]

Ah interesting! So the "type" of macros is basically: Macro a = a -> () | a -> Form? Is this distinction, between compile time functions that do not evaluate their arguments and functions that return carp code/forms, something we should differentiate in the language itself? Or are they close enough that the distinction wouldn't matter in practice?

If the distinction doesn't matter, I think removing the workaround from the evaluator and providing a function like eval to handle macros that return code that we want to evaluate is probably sufficient. (plus rewriting a few existing macro definitions that should just perform a side effect, like doc).

[hellerve]

@scolsen Sorry for never responding! I think they are quite different, but do not need to have different expressions within the language, i.e. when I say register I don’t want to know whether this is a special side-effecting function or a form that desugars to something else. In other words: these forms should be opaque, unless you really want to dig into the innards (and that shouldn’t be the default case).

So, should we settle on providing something like eval for now? Or did any of us have a better idea in the meantime?

[sdilts]

As far as my understanding goes, to evaluate macros in other lisps, the evaluator treats macro expansion like a separate compiler pass: the macro expander walks the input list and expands all of the forms that are macros, then hands off the produced list to the next step in the compilation phase. If there are no macros to expand, then the expander simply returns its input. The REPL is essentially implemented with the following function:

(defun repl ()
   (loop
      (print (simple-eval (macroexpand-all (read-from-string (read-line)))))))

What is stopping a similar mechanism from being implemented in Carp?

[hellerve]

The main problem is that we don’t have eval, since we compile everything statically.

We do have macroexpansion as a pass between parsing and type inference, but the problem that is described above is that it is buggy, basically.

[hellerve]

Here’s another neat something I realized over the holidays: Once we have eval as a special form in carp we can define defndynamic in terms of defmacro.

(defmacro defndynamic-evald [arg]
  (let [e (eval arg)]
     (list e (list ˋeval e))))

(defmacro defndyamic [name args body]
   (list 'defmacro name args
      (list 'let (flatten (map defndynamic-evald args))
          body)))

This depends on map not being defined in terms of defndynamic. Alternatively it could be defined as a regular manual fold.

[eriksvedang]

That's pretty wild!

[hellerve]

I think we can close this now, finally!