Arc Forumnew | comments | leaders | submitlogin
A whacky new programming model with syntax and macros (gmane.org)
4 points by akkartik 1458 days ago | 15 comments


4 points by rocketnia 1456 days ago | link

I've made a prototype for you as a DSL in Arc 3.1. Since I didn't want to call it Blub, I'm calling it Whacky, but feel free to change it. ^_^;

  (mac $ (x)
    `(cdr `(0 . ,,x)))
  
  (def whacky-call (a b)
    (let call-fn
           (fn (f arg)
             ; Get the maximum Racket arity, treating varargs arities as
             ; though the rest arg is absent.
             (caselet arity
                        (apply max
                          (map [if $.arity-at-least?._
                                 $.arity-at-least-value._
                                 _]
                            (let arity $.procedure-arity.f
                              (if (or $.procedure-arity?.arity
                                      (isa arity 'int))
                                list.arity
                                arity))))
               0  (err "Can't use a 0-arity fn in whacky.")
                  ( (afn (rev-args n)
                      (if (is n arity)
                        (apply f rev.rev-args)
                        [self (cons _ rev-args) inc.n]))
                    list.arg 1)))
      (if (isa a 'fn)               (call-fn a b)
          (in type.a 'cons 'table)  a.b
          (isa b 'fn)               (call-fn b a)
          (in type.b 'cons 'table)  b.a
        (err "Neither part of a whacky-call was a fn."))))
  
  (def whacky-compile (expr)
    (if (~acons expr)
      expr
      (let (first . rest) expr
        (zap whacky-compile first)
        (if no.rest
          first
          (reduce
            (fn (op arg)
              (if (and op (isa op 'sym) (~ssyntax op)
                       (isa (bound&eval op) 'mac))
                `(,op ,arg)
                `(',whacky-call ,op ,whacky-compile.arg)))
            (cons first rest))))))
  
  (mac wh code
    whacky-compile.code)
This uses Arc procedures, tables, and lists as procedures, uses Arc macros as macros, and resolves variables in the Arc local environment.

When a call is made using a procedure and a procedure, the first procedure is called with the second as its argument. If the first procedure has arity 0 (after ignoring varargs), this results in an error. Note that lists and tables are treated as procedures here.

When calling a procedure, varargs arguments are never passed in. If you must use a varargs Arc procedure, define a non-varargs Arc procedure that proxies it.

When calling an Arc macro, only one argument is passed in, and that argument doesn't go through whacky-compile, so its exact parentheses are significant. Notably, this means you can use "do (...)" to get back to regular Arc code.

Ssyntax isn't processed, except to protect against evaluating an ssyntax symbol when checking whether it's a macro name.

As in Arc 3.1, a global macro shadows a local procedure. If you use this code in a variant of Arc where this shadowing bug has been fixed (e.g. Anarki), there's probably no way to make this code behave properly, since the 'wh macro can't look up the local environment to see if some macro is shadowed. Instead, this implementation will compile the expression as though it's a macro call (i.e. without compiling the body), and the local function shadowing the macro will be called instead.

  arc> (wh 1)
  1
  arc> (wh ((1)))
  1
  arc> (wh 1 cons 2)
  (1 . 2)
  arc> (wh obj a)
  #hash()
  arc> (let w- (fn (a b) (- a b)) (wh - 1 w- 2))
  -3
  arc> (wh map1 list (do '(1 2 3)))
  ((1) (2) (3))
  arc> (wh list map1 (do '(1 2 3)))
  Error: "Can't use a 0-arity fn in whacky."
  arc> (wh (3 cons (1 cons 2)))
  (3 1 . 2)
  arc> (wh ((1 cons 2) cons 3))
  Error: "list-ref: expects type <non-negative exact integer> as 2nd argument, given: #<procedure:cons>; other arguments were: '(1 . 2)"
  arc> (wh (cons (1 cons 2) 3))
  ((1 . 2) . 3)
  arc> (wh len (10 cons nil))
  1
  arc> (wh (10 cons nil) 0)
  10
  arc> (wh 0 (10 cons nil))
  10
  arc> (wh 10 cons nil 0)
  10
  arc> (wh 1 - sqrt)
  0+1i
The "0-arity fn" error is due to 'list, whose varargs parameters are ignored. The 'list-ref error is due to the fact that the cons cell (1 . 2) counts as a Whacky procedure.

-----

2 points by akkartik 1456 days ago | link

Oh this is awesome.

I spent a week thinking I should be able to crank it out with a few hours of work, but unable to actually do so. Finally I gave up and just threw the idea out there without any code, and boy am I glad I did!

Part of the problem was that hacking on wart I've forgotten that I have a mature lisp available to me.

-----

3 points by rocketnia 1456 days ago | link

You're welcome!

One thing Arc's good for is cobbled-together Arc Forum examples. ;) I'll start a thread about that, actually....

Here it is: http://arclanguage.org/item?id=16610

-----

4 points by Pauan 1458 days ago | link

"All of this suggests to me that all talk of lisp 'permitting macros' because it is 'homoiconic' is a canard. You can build parse trees and macros for any syntax. It's just that the people who want such syntax haven't cottoned on to the power of macros. Or they haven't realized the value of optional syntax, or of redundant syntax where multiple tokens mean exactly the same thing."

I don't think the problem is that macros are impossible in a syntax-rich language... the problem is that as the syntax moves further and further away from the AST, it becomes harder to understand macros, because you have to do all these mental syntax twists in your head. And so the harder it is to understand/read/write macros, the less likely you are to do so, and the more likely you are to conclude that macros are an unnecessary waste of time.

If the above is true, then any attempt to make a Lisp-like language with macros and lots of syntax is doomed to failure, not because it's impossible, but because the more syntax you add, the less useful macros become: normal people don't understand why macros are so great because they're used to syntax, and the Lisp crowd doesn't like syntax because it makes reasoning about macros harder.

This also suggests that if you want a language with more normalish syntax but with decent support for vaus/macros, then it should have a very simple and consistent syntax to minimize the mental overhead. Magpie seems like it fits the bill, essentially having a simpler and more consistent Pythonish/Rubyish syntax.

---

Nulan is based on the premise that syntax should be designed not to make Lisp more similar to normal languages, but instead to aid the programmer. So although Nulan does have syntax, I've tried to give it very clear 1-to-1 translations to S-expressions. I believe this makes vaus/macros a bit harder to reason about (due to the syntax) but in turn you gain some brevity and readability. My hope is that this will be an overall net gain.

---

Interestingly enough, Ruby has first-class environments and three kinds of `eval` that support strings and blocks as the first argument... and with string interpolation, you can write code that looks a lot like a macro...

Essentially, Ruby has all the things it needs for first-class vau, and it's actually idiomatic to use `eval` in certain situations... for instance, here's some Ruby code I wrote a while back:

  def self.make_toggle_setter *args
    args.each do |arg|
      class_eval "def #{arg} x
                    toggle_#{arg} if x != is_#{arg}?
                  end"
    end
  end
Looks a lot like a vau/macro, doesn't it? Except it uses string interpolation rather than building up a list. So Ruby has pretty much all the benefits of (unhygienic) macros despite not having a homoiconic syntax.

This suggests that all you really need for vau is some way to build up data (string, list, AST, whatever) which is then evaluated in a context. And as long as the data looks similar enough to the language itself, it'll be okay. Which is why interpolated strings work out well in Ruby's case: it looks like you're writing Ruby code.

The question then isn't whether the language is homoiconic or not... the question is whether it's easy to write data that looks like the language. In Ruby, you use a string to treat the language as data. Magpie uses quotations. Lisp uses lists.

-----

2 points by Pauan 1457 days ago | link

"The point then isn't whether the language is homoiconic or not... the question is whether it's easy to write data that looks like the language. In Ruby, you use a string to treat the language as data. In Magpie it's quotations. In Lisp it's lists."

By the way, in Lisp, a macro receives a list and returns a list. As shown above, Ruby can get the same (overall) effect using runtime eval + string interpolation.

But there is something that you can do with lists that is much harder with strings/ASTs, and that's to inspect or manipulate them. I've written macros in Arc that will essentially code-walk their body and do different things depending on what they find. This is fairly trivial with lists, because Lisp usually has plenty of functions to inspect/manipulate them.

The same is not true of blocks/strings in Ruby. In Ruby, you can inspect the arity of a block, and you can evaluate the block in a context, but that's about all you can do. Because of the power of first-class lambdas, you can still do a lot of nifty things with Ruby's eval, but it's not quite the same as manipulating lists in Lisp. And you can use regexps to inspect/manipulate strings, but that's obviously a big pain.

So, for simple cases, Ruby's interpolated strings work out just as well as unhygienic macros in Arc, but if you want to do anything more complicated that actually involves inspecting/manipulating the string/block, it'll be a lot harder if not impossible (excluding writing your own compiler/interpreter, of course :P)

---

By the way... because of their runtime nature, it's also impossible (or at least ridiculously difficult) to write a "deep" code-walker in a language that uses vau. I see two kinds of code-walkers: shallow and deep.

An example of a "shallow" code walker would be the `loop` macro in Common Lisp: it walks the macro's body, but it doesn't need to macro-expand anything, it just uses the immediate forms. Vaus can do those kinds of code-walks easily.

A "deep" code-walker would be something that needs to macro-expand the body and then walk the macro-expanded form. An example would be Arc's `setforms` (which is used by `=`, `zap`, etc). Vaus can't do that.

This suggests that for code-walkers, macros are actually more powerful than vau. But "deep" code-walkers are usually not created even in Lisps that have macros, so I think it's fine for vaus to give them up.

-----

1 point by akkartik 1457 days ago | link

"..for simple cases, Ruby's interpolated strings work out just as well as unhygienic macros in Arc, but if you want to do anything more complicated that actually involves inspecting/manipulating the string/block, it'll be a lot harder if not impossible."

Yeah. Another way of saying that is that packing the parsing of the AST into a macro-like feature is less powerful than exposing it to the rest of the language. This is why I don't consider string-interpolation-and-eval to be macro support.

Here are a few languages that have tried to build lisp macro support (none successfully, IMO):

http://opendylan.org/books/dpg/db_330.html#heading330-0

http://www.xoltar.org/old_site/2003//aug/13/templateHaskellT...

http://perlcabal.org/syn/S06.html#Macros

http://nemerle.org/wiki/index.php?title=Macros_tutorial

Lispers will hold these up as examples that you need s-expressions to do macros 'right'. But I'm starting to question this. Is smalltalk 'homoiconic'? I think you could argue yes. And factor certainly supports a very powerful notion of quotations.

My final evidence that the word 'homoiconic' is so fuzzy as to be useless: watch the discussion go around in circles at http://c2.com/cgi/wiki?HomoiconicLanguages, http://c2.com/cgi/wiki?HomoiconicityClassification.

-----

3 points by Pauan 1457 days ago | link

"This is why I don't consider string-interpolation-and-eval to be macro support."

Well it's not a macro anyways because `eval` runs at runtime. But it is roughly analogous to vaus in Kernel/Nulan, which in turn are a superset of (runtime) macros. Except that, in Ruby, it's a very hacky vau which is limited in power. :P

---

"Lispers will hold these up as examples that you need s-expressions to do macros 'right'."

I think it's just as I said. The more syntax you add (and especially the more complex the syntax is), the harder it is to deal with macros. That's all. S-expressions happen to be the simplest, most consistent, and readable syntax we've found, which makes it ideal for macros.

But Nulan is an example where it is possible to add syntax to a Lisp, just so long as the syntax translates easily into S-expressions underneath. Arc is another milder example of the same idea.

---

"My final evidence that the word 'homoiconic' is so fuzzy as to be useless"

I don't see how it's useless... as those pages suggest, "homoiconity" describes not a binary 1/0 but a continuum of languages. That does make it a fuzzy analog word, but a lot of words we use are like that: we humans think in fuzzy analog ways. That doesn't make it useless.

---

"But I'm starting to question this. Is smalltalk 'homoiconic'? I think you could argue yes. And factor certainly supports a very powerful notion of quotations."

I think you're worrying too much about "macros". What I care about isn't macros, but the ability to create new constructs that look and behave just like existing constructs.

If the language doesn't have any special forms (everything is a function), then the language only needs functions and not macros/vaus.

But Lisps usually do have special forms (lambda, if, etc.) and the primary way to define new special forms is with macros. Kernel/Nulan/wart achieve the same thing with vau.

Ruby's eval makes it possible to define certain constructs which would otherwise be impossible without eval. But you still can't define new things that look and act like "if", "def", etc. because the only way you can turn off evaluation in Ruby is with a block.

---

So, Ruby's string interpolation + eval is more powerful than languages like Python which don't have it, but it's still less powerful than macros/vaus in Lisp-like languages. And in languages with laziness like Haskell, you might not even need macros/vaus at all!

If Ruby had some way to plug into the parser, then it could add new syntax. But Ruby's syntax is quite complicated, so dealing with things at the parser level would probably be very hard. In any case, it's moot because Ruby doesn't let you do that, as far as I know.

Magpie does have the ability to plug new things into the parser, therefore Magpie is just as powerful as macros in Lisp. And Magpie's syntax seems simple enough to me that I think it can actually work out okay. Whether it's as easy as S-expressions or not is another story... I think the primary benefit of S-expressions is that they make macros easy, not that they make it possible.

---

I would say that Magpie is homoiconic, due to it representing its source code as a user-manipulable object, and it also has quotations which make it easy to create said objects.

That's why the word "homoiconity" is a fuzzy continuum: different languages have different abilities, and they achieve their abilities in different ways. And even two languages with very different abilities or ways of achieving those abilities can still be equivalent in power.

What I care about is the power to do things, so I'm trying not to get too hung up on one particular technique like macros. As long as it works well enough, it's fine by me, whether it's strings + eval, Magpie's quotations, Haskell's laziness, macros, vau, etc.

---

By the way, I'm not trying to argue that Ruby is homoiconic: I don't think it is. I was merely pointing out that even a non-homoiconic language with lots of complex syntax like Ruby can still get a lot of the same power that (unhygienic Arc-like) macros have. Just not all of it.

The same has been said of macros: they give you a lot of the same power that vaus have, just not all of it. Then again, there are some things that macros can do that vaus can't... so it seems that they are more like an evolutionary split in the tree: vaus don't replace macros, instead they grow alongside them in a different branch.

-----

1 point by Pauan 1457 days ago | link

"Here are a few languages that have tried to build lisp macro support (none successfully, IMO):"

I dunno, Nemerle and Perl seem okay to me. Can't really speak about Dylan or Template Haskell, except to say that it seems to me the only reason Haskell needs macros is due to its restrictive type system.

-----

1 point by akkartik 1457 days ago | link

You know, you're right. Nemerle in particular is ok. Perhaps that's all the existence proof I need.

-----

4 points by Pauan 1457 days ago | link

If adjacency means function application, how does the evaluator know that (+ 1) and (1 +) are the same? What happens if both are functions, like with (+ +) or (map car)?

An interesting idea: constants like 1 are functions that accept a function and call that function with themself, which means (1 +) is treated as similar to ((fn (x) (x 1)) +) in Arc.

That doesn't solve the (map car) case, though. I think you could solve that by saying that function application is always left-to-right, and then use the above "constants-as-functions" idea to enable infix (1 + 2) expressions.

And then symbols could be vaus that evaluate themself in their environment, so that (a +) is like (($vau (x) env ((eval x env) (eval ($quote a) env))) +) in Kernel.

Alternatively, if you make environments static like they are in Nulan... you could have (a +) evaluate to ((fn (x) (x <the value of a>)) +)

---

Originally this idea didn't seem very interesting to me, but combined with the above "everything is a vau/fn, even constants" idea... I might actually play around with this for a while.

-----

2 points by akkartik 1457 days ago | link

Yeah, I somehow hadn't considered higher-order functions at all :/

almkglor had an interesting suggestion: view this idea in terms of pattern matching. When you see a function you see if it makes sense to apply it in the given context.

So in (map f list), the f would likely not apply to map, so it would be treated as an object.

But this is still half-baked..

-----

2 points by Pauan 1457 days ago | link

That's an interesting idea too, and it looks like you're moving into a more fuzzy analog kind of system, not entirely unlike how JavaScript takes both operands into account with `+` so that 1 + "foo" returns "1foo"

-----

2 points by akkartik 1458 days ago | link

Just in case evidence was needed, here's me floating an idea with no sign of working code :)

(ref: http://arclanguage.org/item?id=16481)

-----

2 points by Pauan 1458 days ago | link

"The name for this language is blazingly self-evident: Blub."

I approve! :D

-----

3 points by rocketnia 1457 days ago | link

I disagree. "Blub" is useful enough as a rhetorical device that it shouldn't be the name of any one language.

However, if your name choices are ever limited to "Blub" and "Pseudocode," go with Blub. :-p

-----