Arc Forumnew | comments | leaders | submit | waterhouse's commentslogin

With interpreter semantics, in which a macro gets expanded anew every time a function is called, the late binding comes for free. ;-) Then, if you want the runtime performance that comes from compilation, you optimize for the case where people are not redefining functions, and invalidate old compilation results when they do. I think that rough plan should be doable, though I haven't gotten around to implementing enough of a system to say how well it works. But I think that's the only way to get anything close to good performance in Javascript VMs (not that they expand macros, but I expect they inline function calls and such, which requires similar assumptions about global definitions), and it seems to have been done.

For separate compilation, it does seem clear that what gets serialized will be references like "the object [probably a function] named 'foo in module bar", and structures (s-expressions or otherwise) containing such references. Given that compilation implies macroexpansion, you do have to assume (or verify) that the macros from other modules are what they used to be—and that non-macros (used in functional position at least) are still non-macros. If you have a full-blown Makefile kind of build system, then by default I suppose every file's output depends on the contents of every other file that it uses; or, as an optimization, depends merely on the exact set and definitions of macros exposed from those files. (In the C++ system I encounter at work, code is separated into .cpp and .h files, and editing a .h file causes the recompilation of every .cpp file that recursively depends on it, but editing a .cpp file only causes its own recompilation. If you wanted to imitate that, I guess you'd put macros into a distinctively named set of files, and forbid exportable macros anywhere else.)

---

Thanks! I've sold out and have been working for a medium-sized company doing mostly C++ and bash (the latter is unbelievably useful) for the past 3.5 years. I make intermittent progress on the side doing other things.

reply


> To handle special forms, a solution is to come up with a globally unique random prefix long enough that no one could generate it accidentally (e.g. "xVrP8JItk2Ot"), and then rename the special forms `assign`, `fn`, etc. to `xVrP8JItk2Ot-assign`, `xVrP8JItk2Ot-fn` etc;

Would this prefix be present in the source files of the language implementation? Or generated at runtime, or something else? If the latter, it seems like gensyms are the right approach. If the former, what's the use case—someone writing programs that assume someone might have redefined "assign" and want to work with the builtin? (If it's just hacking arc3.1 to do what we want, I think you can create more or less arbitrary unique objects (vectors, cons cells, a new kind of struct), give them bindings in the base Arc environment, and replace e.g. '(eq? (xcar s) 'quote) with '(eq? (xcar s) the-quote-object).)

Speaking of gensyms, I had a plan recently. I like PG's approach of just sequentially named variables, but (a) my ideal language would probably expose its interned-symbol table, and it'd therefore be more orthogonal and simpler for it to directly expose the "create a symbol without interning it" function, so uninterned symbols should be available for free; (b) it is possible that people will name a variable "gs1", so that's another reason to use true gensyms; (c) many macros use gensyms, but I might like to bootstrap a system that likes macros the expansion of which incurs zero side effects, and incrementing a gensym counter is a side effect. For (c) there might be another approach, but I came up with this one: Have the printer assign sequential numbers to each uninterned symbol it encounters (with a weak hash table). This has the nice effect that, when you do print macroexpansions, the numbers you see will begin at 1, rather than in the hundreds or thousands and varying depending on how many libraries have been loaded.

> (Making `fn` a macro also has the advantage that features such as default arguments can be implemented in Arc).

Yes, that is nice. I actually did this in my Lisp in Summer Projects submission[1] many years ago.

> is there a reason to use different prefixes for macros and functions? We could have a read syntax which evaluated to the value of the symbol (whatever it is), and that would work for both functions and macros.

Eh, no strong reason. I'd thought about doing a reverse variable lookup for every value and printing the variable name if it existed, but it makes less sense if e.g. the value 10 gets printed as #V:<some global variable that happened to be bound to 10>. Also, I figured an IDE-type setup (such as DrRacket) might use different colors or fonts to distinguish macros/functions/special forms/other. Last, you do need a way to print lambdas that don't have a global name (and might not even have a local name), and I'm guessing you'd want that to appear as #f:<some attempt at indicating line number / REPL input>, looking analogous to but different from the global case.

[1] https://github.com/waterhouse/emiya : "[O]ptional arguments are implemented by redefining "fn" (Arc's equivalent of "lambda") as a macro that expands to a call to "underlying-fn", which is bound to the fn special object--again, by the user. Then everything is recompiled, so that this redefinition does not cost anything at runtime; some care is needed here, to avoid an infinite loop, if a function used to recompile "fn" itself uses "fn"."

reply


Thanks for the pointer. He has an entire chapter on hygiene... And then there is this:

"There is no need to provide quotation here because, having failed to enforce the prohibition against embedding combiners in a macro expansion, we don’t need to embed their unevaluated names in the expansion."

It's nice that his primitive $vau grabs the current lexenv, as this enables another kind of macro-like behavior I've thought might be useful: taking subexpressions, fully macroexpanding them, and doing something with the result (e.g. determining whether a variable is ever used, and omitting a computation if not). I don't know how that would mesh with the interpreter's semantics, though...

I'll probably have to read and brood on this further.

reply

3 points by waterhouse 37 days ago | link | parent | on: Recursive anonymous functions?

The Y combinator itself is more cumbersome, having an extra currying step or two. I prefer the form hjek is using—which is a function that expects to take "itself" as an extra parameter, like this:

  (fn (f i)
    (aif i!parent
         (+ 1 (f f (item it)))
         0))
So the recursive call, "(<self> (item it))", is implemented as "(f f (item it))". And then usage is very simple: actually give it itself as an extra argument.

The Y combinator works with a different function signature:

  (fn (f)
    (fn (i)
      (aif i!parent
           (+ 1 (f (item it)))
           0)))
That is, the function takes "something that's not quite itself" as an argument, and returns a function which does one step of computation and may do a "recursive" call using the thing that was passed into it. The implementation would therefore like to be:

  (def fix (f) ;aka Y
    (fn (i)
      ((f (fix f)) i)))
But, if we're doing the entire thing with anonymous recursion, we can (laboriously) implement fix like this:

  (= fix ;aka Y
     (fn (f)
       ((fn (g) (g g))
        (fn (g)
          (fn (i)
            ((f (g g)) i))))))
Every recursion step involves creating multiple lambdas. Eek. (It's even worse if you use the general, n-argument Y combinator, in which case you must use "apply" and create lists.) Whereas with hjek's non-curried approach, only a constant number of lambdas have to be created at runtime. (Optimizing compilers might be able to cut it down to 0.)

If you want to create a macro like afn or rfn, and want the user to be able to act like the function is named F and accepts just the parameter i, you can put a wrapper into the macroexpansion, like this:

  (rfn F (i)
    (aif i!parent
         (+ 1 (F (item it)))
         0))
  ->
  (fn (i)
    ((fn (f)
       (f f i))
     (fn (f i)
       (let F (fn (i) (f f i))
         (aif i!parent
              (+ 1 (F (item it)))
              0)))))
And in this case, while the code does call for creating an F-lambda on every recursive call, I think it's easier for the compiler to eliminate it—I don't remember whether I'd gotten Racket to do it. (I think it probably did eliminate it when working with Racket code, but Arc, which generates all the ar-funcall expressions, might not have allowed that.)

The actual code for rfn will create a variable and then modify it, creating a lexical environment with a cycle in it. That's certainly a more straightforward approach. I figure the above is useful only if you're working in a context where you really want to avoid mutation or true cycles. (For example, I am considering a system that detects macros whose expansion is completely side-effect-free. It might be easier to use the above approach to defining iteration than to teach the system that rfn is "close enough" to being side-effect-free.)

reply


By the way, "what you'd expect" is apparently not what I expected:

  ; SBCL
  * (defmacro plus (&rest args) (cons #'+ args))
  PLUS
  * (plus 1 2 3)
  ; in: PLUS 1
  ;     (#<FUNCTION +> 1 2 3)
  ;
  ; caught ERROR:
  ;   illegal function call
  
  ; CLISP
  [1]> (defmacro plus (&rest args) (cons #'+ args))
  PLUS
  [2]> (plus 1 2 3)
  *** - EVAL: #<SYSTEM-FUNCTION +> is not a function name; try using a symbol instead
  
  ; Racket
  > (eval (list '+ 1 2))
  3
  > (eval (list + 1 2))
  3

reply

5 points by waterhouse 537 days ago | link | parent | on: How many people still lurk here?

Hello there.

(This experiment also serves as a sample of how regularly the lurkers lurk.)

-----

4 points by lojic 511 days ago | link

True :)

I had high hopes for Arc over a decade ago, then it languished, then pg stopped participating.... then I looked at Racket (then PLT-Scheme) since that's what Arc was built on and realized Racket was the language I was looking for :)

I still pop in occasionally out of curiosity.

-----

2 points by waterhouse 925 days ago | link | parent | on: Multiple Return Values

The corresponding macro in Common Lisp has an 18-character name.

  ; SBCL
  * (destructuring-bind (x y) '(1 2) (+ x y))
  3
  ; Arc
  arc> (let (x y) '(1 2) (+ x y))
  3

-----


The first (and only) reason that comes to my mind is: efficiency. Calling a function that takes rest args means allocating a list at runtime; the usual expansion for "do" is a direct call to a lambda, which the Racket compiler seems able to handle with no runtime cost. Thus:

  arc> (def do-func args last.args)
  #<procedure: do-func>
  arc> (mac do-macro args `((fn () ,@args)))
  #(tagged mac #<procedure: do-macro>)
  arc> (time:repeat 1000000 (do-func 1 2 3))
  time: 270 cpu: 270 gc: 6 mem: -4392856
  nil
  arc> (time:repeat 1000000 (do-macro 1 2 3))
  time: 69 cpu: 70 gc: 0 mem: 928
  nil
  arc> (time:repeat 1000000 1 2 3)
  time: 67 cpu: 68 gc: 0 mem: 128
  nil
It is not too far-fetched an idea for a compiler to eliminate the runtime overhead of the calls to "do-func". Basically this would require assuming that "do-func" will not be redefined at runtime--which is permitted in Arc, so it would require the compiler to make optimistic assumptions and be prepared to invalidate the code when they are violated (i.e. if someone actually does redefine "do-func" at runtime). I've heard the best Javascript engines do this, but Racket does not.

In your use case, having a "do" that works at all is better than none, and I don't think there is any logical problem with doing so. (Strictly speaking, it makes it possible to "do" [!] more things, since you can't apply a macro.)

-----

2 points by Pauan 1383 days ago | link

That's a good point. In Nulan, you can't redefine things (all variables are constant). I'm not so worried about performance right now. My main concern is simplicity, since implementing "do" as a macro introduces a lot of extra complexity (because Nulan compiles to JavaScript).

-----

4 points by waterhouse 1462 days ago | link | parent | on: Re: waterhouse's AVL trees

Thank you for your kind words. I'm glad you've found my post useful. And that's a good catch about node/r.

It looks like the two versions of node/r differ just in the case when (depth x!lf) = (depth x!rt) [and likewise for y], which it appears I had assumed would not be true; perhaps that was valid for insertions but not deletions. (I must admit deletions came as a bit of an afterthought, as evidenced by the typos in "aremove".) I'm pleased that the resolution is so simple.

Anyway, thanks to you, we now have AVL trees that are actually tested and proven to work.

-----


Congratulations, zck!

If you want to see my quasiquote, here it is defined:

https://github.com/waterhouse/emiya/blob/master/arc3.1/inter...

-----

3 points by zck 1579 days ago | link

Congrats to you too!

What's the future path for emiya? It looks really cool, but it seems like you haven't done much with it since last fall.

-----

3 points by waterhouse 1578 days ago | link

Well, since you ask. :-) And since the judging is all done, I might as well update it. So. Currently things are broken up into "dyn-cont", which has the Arc interpreter, "arc-boot", which is the code the interpreter will run on startup, and "memory-system", which is where I'm prototyping the stuff the next version of "dyn-cont" will run on: fake assembly code, which is a preparation for writing real assembly code.

https://github.com/waterhouse/emiya/blob/master/arc3.1/inter...

https://github.com/waterhouse/emiya/blob/master/arc3.1/inter...

https://github.com/waterhouse/emiya/blob/master/arc3.1/inter...

-----

More