The simple (to implement, not use!) solution is simply to liberally use symeval! on functions used in macros. Also, my recommendation is to cause macros to expand to invocations on functions:

  (mac each (var seq . body)
    `(symeval!each-f ,seq (fn (,var) ,@body)))
  (def each-f (seq bf)
    (if seq
        (do (bf (car seq))
            (each-f (cdr seq) bf))))

Although my implementation uses <package>symbol syntax, because package::symbol feels too close to fun1:fun2 syntax.

Drawback is that intrasymbol syntax has to be processed by the reader, because of the symbol mapping by the contexter :(

Why not use (import (package-name symbol-name) new-symbol-name)? or just (import package symbol new-symbol-name) where the last two variables are optional? With that syntax, packages don't seem too far off from hash-tables. That doesn't mean hash tables should be used to implement packages, I'm just saying they're similar. Calling (package symbol) would just return the value of the symbol from that package, and (def new-name (package symbol)) would be the same as import. There would still be some use for import, or using, to register certain members of the package into the present context without renaming them.

Using and import statements could be equivalent to a "global with," that is only escaped by the complementary "not-using" statement. If you don't want to use the package for the whole file, you could just use a normal with block, or an equivalent statement for packages, possibly built into "using".

I understand your idea of "interfaces," and it seems useful. However, wouldn't that mean that the library file would need to maintain all of the old versions, even if you weren't using them? Is there any way around that?

Because PG suggested adding them to Lisp and related languages, citing the case of 'quote and 'quasiquote and friends.

That said I don't understand your concern about this here.

Edit2: Personally I'm also somewhat concerned about exploding syntax. This makes things harder, sometimes a lot harder. http://russ.unwashedmeme.com/blog/?p=58

>Adding all of these special case reader macros sounds like it might be nice to use if it was easy to add

cref. my ssyntaxes.arc on Anarki

> Calling (package symbol) would just return the value of the symbol from that package

This will require special handling for macros; if I wanted to use a macro explicitly from a particular package, I'd need to do something like this:

  ; library.arc
  (in-package foo)
  (mac a-macro (x) (+ "the foo macro says: " x))

  ; my-program.arc
  (in-package my-program)
       ; since a.b == (a b)
  (pr (foo.a-macro "temp"))

Your suggestion is certainly valid; one can implement packages as macros that perform lookup for a hidden global table and would probably use gensyms.

However the problem lies not in functions or macros but in types. Currently the standard Arc Way is to use plain symbols for types. Now, suppose package A defines a type 'parser, while package B also defines a type 'parser. If symbols are kept global (unpackaged!!) then we have a type clash: if you have an object of type 'parser, is it 'parser as known by A or 'parser as known by B? My proposal, on the other hand, will transform them into '<A>parser and '<B>parser.

Edit: PG: "I can't imagine why users would want to have type labels other than symbols, but I also can't see any reason to prevent it." http://www.paulgraham.com/ilc03.html

Edit: Of course, currently Arc is semi-standardized on using symbols, and I doubt it'll change sometime soon. In principle it's possible to use non-symbol type tags (say some random object containing inheritance and fields information)

Digression:

I'm also implementing multimethods/generic functions, and they depend on type. So you can do something like, say:

  (in-package foo)
  (using <arc>v3)
  (interface v1 my-type)
  (def my-type (x)
    (annotate 'my-type x))
  (defm <base>+ ((t a my-type) (t b my-type))
    (my-type (<base>+ (rep a) (rep b))))

  (using <foo>v1)
  (= a (my-type 1))
  (= b (my-type 2))
  (= c (my-type 3))
  (+ a b c)
  => #3(tagged <foo>my-type 6)

Of course, package <bar> can define <base>+ on its own my-type, and adding a <foo>my-type and <bar>my-type will correctly throw a typing error ^^, which is even cuter.

> However, wouldn't that mean that the library file would need to maintain all of the old versions, even if you weren't using them?

How good or bad is backwards compatibility? If you use a library today and someone fixes a bug in it, but in the process completely changes the interface from under you, would you be pleased or pissed?

Backwards compatibility accumulates cruft, true. BUT, it helps with a very human need to be lazy. If updating a library means I might have to look through all my other tools, checking that something the library provides in older versions is changed to conform to newer versions, I might prefer not to update anyway.

> How's snap going?

Badly. I'm stuck on I/O. The bad thing is with sockets. A socket is bidirectional (one FD number for input and output directions), but mzscheme splits it into two mzscheme ports, one for input and one for output. Arc-on-mzscheme thus expects monodirectional sockets. This means I might have to redesign a bit of the central I/O, since I was designing with listen/socket-accept returning a single port object.

I don't really know how you're doing scoping in SNAP, or even much of how it's done in arc, but if the lexical scoping is done the same way as it is according to SICP (which I'm just now reading), then each "environment" has a pointer to it's parent frame, and if the interpreter can't find the definition in the current frame, it moves up one level.

What if you just merged the concept of "packages" "environments" and "scope" into the same thing? I don't really know what the syntax should be but basically when you load a package at a certain level of the program, it adds a pointer to the current frame (maybe between this frame and its parent? I don't know how well multiple parents works for lexical scoping) and it's treated by the interpreter as if it was just another scope.

Then, to make things fun and interesting for more than just packages, you add a syntax for naming scopes, and referring to them either by name or by relative height. This way you can access not only package specific variables, but also get around some shadowing problems by telling it "I only want 'a if it's in this scope" or "I want 'a from the frame two levels up"

I don't really care too much what the syntax looks like, but this would be an interesting way to reference packages that should be (if scoping actually works in a way similar to I've presumed) a) fast and b) capable of managing more than just packages.

One major problem is that it would probably require lots of low-level munging in scheme to get this to work. It would probably be easier to do in SNAP, since I think you're implementing most of this from scratch there.

What do you think?

Your understanding of this is quite correct.

But this is how it's equivalent to, not necessarily how it's implemented. AST-traversal?

The problem with the nested-environment implementation is that mere variable lookup can be O(N) where N is the number of nested environments:

  (def foo (x)
    (fn (y)
      (fn (z)
          ;accessing x takes 2 indirections!
        (+ x y z))))

  (def foo (x)
    (fn (y)
      (let tmp (+ x y)
        (fn (z)
          (+ tmp z)))))

A faster way would be to "flatten" the environment. In effect, what's really done is:

  (def foo (x)
    (fn (y)
      (fn (z)
        (+ x y z))))
  =>
  (def foo (x)
    (closure (list x)
      (fn (y)
        (closure (list (my-environment 0) y)
          (fn (z)
            (+ (my-environment 0) (my-environment 1) z))))))

------- BUT!

Just because environment flattening is how it's usually implemented doesn't mean it's not possible to capture and name an environment.

For example consider that what we call a "function" is really an object constructed by a 'closure very-hidden function. It's really a pair of the environment and the function code. Similarly if Arc had ways of destructuring a function, we could implement a call-with-current-environment function. Suppose we had a 'environment-of function which extracts just the data of a given function:

  (def call-with-current-environment (f)
    (f:environment-of f))

  (mac w/environment (var . body)
    `(call-with-current-environment
       (fn (,var) ,@body)))

This has been implemented. Take a look at lib/module/module1.arc . But aside from having problems with macros, there's also....

> I've been thinking again ^^, and I just realized that though this might be an interesting way to implement packages, I don't think it would fix your typing issue.

Quite right ^^

> Maybe variables should all carry around info of which scope they're from (kind of what you were suggesting)?

> Err. I don't quite understand this. Also, I don't quite understand how this realates to symbols-as-types...

Well, what I had originally thought when I said this was rather silly, which was that in the value of the variable there should be information about which scope it's located in. Doh! Maybe that would work if it looked in the current env to figure out where the "real" var is.

What I now think is something very similar to what you've been saying, except I still think it would be cool if this could be a method of managing general environments, instead of just modules. I don't know if that was what you were thinking, or not; it's more of an implementation detail.

I do like the idea of being able to extract and name the environment at any point in the code. If all that a package was was an environment with a name and we had the ability to access items from each environment directly, it could (possibly?) be useful for a lot more than just modules.

I really like the syntax (env sym), where env is the environment object, and 'var is the symbol we're looking up. This way env.sym works. That's probably a syntax that many people are used to. I just don't know if it would work or not.

For your typing problem, I would do what you recommended. If it made any sense, I would use the syntax env.sym, so that it can be evaluated to figure out what type it is. You would still have to evaluate everything in head position to see if it evaluated to a macro. On the other hand, you could just check the car of the first item, and see if it was an environment. Or you could treat the whole thing as a single symbol and have it bypass the reader? How does arc's typing system work?

Also, how much would changing the type symbol to <env>sym help? How would it help the code decide how to interpret it?

I just don't know enough about scheme's pointer and environment system, or arc's typing system to know if any of my thoughts are even going in the right direction. So I just make more of them to cover the bases, and have you explain why none of them work. ^^

Basically at this point, I'll agree with anything you say, because I don't know enough to disagree with you. I would be very interested in learning/having you teach me all of the details about arc's implementation. As always, I'd love to help, but I don't know nearly enough to be useful.

Maybe we should start a new thread for the module system that you're proposing?

As per one of you previous comments: If symbols weren't global, how would you do them?

Yes, it would definitely be cool to access the environment. For one, it would make serializing functions possible: aside from giving accessors to the environment and to the function code, you can give constructors for functions that accept a serializable environment and a serializable function code.

> If it made any sense, I would use the syntax env.sym, so that it can be evaluated to figure out what type it is.

Typical 'isa pattern:

  (isa foo 'cons)

  (isa foo 'arc.cons)

First things first. We want to make the type arc.cons readable, don't we? So if say 'arc here is a macro, it will expand to a symbol, which is basically "the symbol for cons in the arc package".

Now that symbol can't be a 'uniq symbol, since those are perfectly unreadable.

What we could do is....... oh, just make up a symbol from the package name and the given symbol. Like, say...... <arc>cons. The choice of <> is completely arbitrary.

Now.... if (arc cons) is a macro that expands to <arc>cons, why go through the macro?

> And how is the isa statement going to be updated to work independent of which module it's running in? Does each module type all of it's objects that way from the beginning, or were you going to have the interpreter do something fancy?

Something fancy, of course. Specifically it hinges on the bit about the "contexter". Remember that in my proposal I proposed adding an additional step after the reader, viz. the contexter.

Basically the contexter holds the current package and it puts any unpackaged symbols it finds into the mapping for the current package.

So for example we have:

  (in-package foo)
  (using <arc>v3)
  (interface <foo>v1
    make-a-foo foo-type is-a-foo)
  (def make-a-foo (x)
    (annotate 'foo-type x))
  (def is-a-foo (x)
    (isa x 'foo-type))

Initially the contexter has the package "User".

It encounters:

  (in-package foo)

  t

Then it accepts:

  (using <arc>v3)

  def => <arc>def
  isa => <arc>isa
  annotate => <arc>annotate
  ...etc.

  t

  (interface <foo>v1
    make-a-foo foo-type is-a-foo)

After creating the interface, it then returns:

  t

  (def make-a-foo (x)
    (annotate 'foo-type x))

  (<arc>def <foo>make-a-foo (<foo>x)
    (<arc>annotate '<foo>foo-type <foo>x))

Then the contexter accepts:

  (def is-a-foo (x)
    (isa x 'foo-type))

  (<arc>def <foo>is-a-foo (<foo>x)
    (<arc>isa <foo>x '<foo>foo-type))

So, how hard is it to take what you've made so far, and generalize it to work with any kind of environment, and not just packages? So, things like destructuring functions, naming environments, passing them around, etc. Would this allow us to avoid shadowing variables by naming which level they came from explicitly?

Also, if I type in the symbol '<arc>bar, will the contexter read that and presume I'm looking for the bar in arc, or will it rename it <foo><arc>bar? And which is better?

Hmm. Well, if you want to be technical about things, one Neat Thing (TM) that most compilers of lexical-scope languages (like Scheme and much of CL, as well as Arc) do is "local renaming". Basically, suppose you have the following code:

  (fn (x)
    (let x (+ x 1)
      x))

  (fn (x@1)
    (let x@2 (+ x@1 1)
      x@2))

  (fn (<fn>x)
    (let <fn/let>x (+ <fn>x 1)
      <fn/let>x))

In fact I am reasonably sure that Scheme's hygienic macros work after local renaming, unlike CL's which work before renaming. You'll probably have to refer to some rather turgid papers though IMO, and decompressing turgid papers is always hard ^^.

> Also, if I type in the symbol '<arc>bar, will the contexter read that and presume I'm looking for the bar in arc, or will it rename it <foo><arc>bar? And which is better?

   (let list '(this is a test case)
       (all is-a-foo (map make-a-foo list)))
   

   (sym "make-a-foo")

Assuming you mean in the same file with the example foo package:

  (<arc>let <arc>list (<axiom>quote (<arc>this <arc>is <foo>a <foo>test <arc>case))
    (<arc>all <foo>is-a-foo (<arc>map <foo>make-a-foo <arc>list)))

About macros, hasn't there been some interest for a while in getting macros to be "first-class" and so forth? How are they implemented, exactly, that makes this so hard? Is it really that hard for the reader to take the output of a function and automatically interpret it as code?

Also, you mention some effort being made into allowing arc to see if the form in head position resolves to a macro. How hard is that to do? I really don't know how macros work, though I understand what they do.

Aren't they just functions tagged to let the interpreter know that they can a) be expanded at compile time, because the output is not dependent upon the value of the input, and b) return forms that need to be evaluated?

How hard would it be to let normal functions do this? Suppose we had a syntactical feature on function definitions, such that (fn x 'a) prequoted a, so that the form located at a is captured, instead of it's value. Would that be enough to "simulate" macros? Or does the interpreter need to know that the forms that come out the other end probably need evaluation?

I should think that all a macro is is a tag that guarantees to the compiler that it's output is completely independent of it's input, and can thus be expanded at compile time.

I know we kind of went through something like this before, but what am I missing. If you clear this up, maybe I'll finally understand how macros really work ;)

And good luck on SNAP. I would love to help you, as lisp + erlang (feature wise) is something I am very interested in. Unfortunately, it's just way beyond my abilities at this point. I shall look forward to reading your blog!

Erlang source files, on the other hand, are a set of function definitions - they aren't executed at the time you load. There are no globals in Erlang (although the function names are effectively equivalent to global variables that can't be mutated normally). Each Erlang source file is compiled as a single unit, meaning one source file == one Erlang module.

> About macros, hasn't there been some interest for a while in getting macros to be "first-class" and so forth?

I presume you mean something like this:

  (let my-macro (annotate 'mac
                  (fn (x y)
                    (+ "my-macro says " x " and " y)))
    (my-macro "hmm" "haw"))

It isn't how macros, per se, are implemented that makes this hard, it's how efficient interpreters are implemented that makes this hard.

One of the slowest implementations of interpreters are what's called "AST traversers". Basically, the interpreter simply goes through the list-like tree structure of the code and executes it. In a Lisp-like, the AST is the list structures input by the s-expression syntax. This is what macros fool around with.

The slowness of this is usually because it needs to enter each sub-AST (i.e. a sub-expression, e.g. in (foo bar (qux quux)), (qux quux) is a sub-AST) and then return to the parent AST (in the example, it has to return to (foo bar _)).

However a faster way to do it is to pre-traverse the syntax tree and create a sequence of simple instructions. This is usually called a "bytecode" implementation, but take note that it doesn't have to be a byte code.

For example (foo bar (qux quux)) would become:

  (call qux quux) ; puts the return value in 'it
  (call foo bar it)

However, consider the above sequence if 'foo turns out to be a macro. If it is, then it's too late: the program has already executed 'qux. If it were part of say a 'w/link macro, then it shouldn't have executed yet. Also, recreating the original form is at best difficult and in general highly intractible, and remember that the macro expects the original form.

So in general for efficient execution most Lisplike systems force macros to execute before pretraversing the AST into the bytecoded form. This also means that macros aren't true first class, because they must be executed during compilation.

In short: most lisplikes (mzscheme included) do not execute the AST form (i.e. the list structures). They preprocess it into a bytecode. But macros work on the AST form. So by the time the code is executed, macros should not exist anymore.

> Also, you mention some effort being made into allowing arc to see if the form in head position resolves to a macro. How hard is that to do?

Trivial, just add a few lines in ac.scm. However rntz didn't push it on Anarki, which suggests that the modification hasn't been very well tested yet. http://arclanguage.com/item?id=7451 but the patch itself has been lost T.T . I think it'll work, but I haven't done the patch too either ^^.

> And good luck on SNAP. I would love to help you, as lisp + erlang (feature wise) is something I am very interested in.

Is there any way to optimize the interpreter without sacrificing AST interpretation? Or should I write my own language that says "interpreted languages are supposed to be slow; don't worry about it" for the sake of more powerful (in theory) macros? ^^

You might be interested in Common Lisp's 'macrolet form. I've actually implemented this in Arc waaaaaaay back.