Arc Forumnew | comments | leaders | submitlogin
Some Arc questions from a beginner
7 points by graphene 5245 days ago | 7 comments
Hello,

I have been toying with arc and lurking on the forum for a while now and over the holidays decided to take a really close look. From that, I have a few questions which I hope some of you can answer. I hope none of them are too stupid :-)

Here goes:

1. I'm not fully understanding the distinction between functions and macros. Take for example the definition of when: (mac when (test . body) `(if ,test (do ,@body)))

Easily comprehensible if you have read the tutorial. However, my naive mind thinks the same effect should also be able to be achieved with a function. My fisrt attempt was simply

(def when1 (test . body) `(if ,test (do ,@body)))

but of course, since functions by definition return the result of evaluating the last expression in their body, this simply returns the list starting with "if" which the macro would have inserted into the code.

However, when you do this

(def when2 (test . body) (if test (do body)))

you get a function when2 which does the same thing as the macro when, but gives different return values:

  >(when2 1 (= a 3) (= b 2))
   (3 2)
  >a
   3
  >b
   2
whereas

  >(when 1 (= r 3) (= p 2))
   2
  >r
   3
  >p
   2
I'm probably missing something or using a bad example, but from this, I can't see the magic of lisp macros.. Maybe an experienced lisper can show me the light.. is there a fundamental (or practical) difference between the two approaches outlined above? (or is the fact that they have different return values more important than I seem to realize)?

Why was a macro used to define when and not a function?

Similarly in defining in, why can't we use something like

   >(def in (x . choices)
      (some x choices))
instead of the more complicated (to me at least) macro used now?

2. In the definition of pair, I think (list (f (car xs))) would produce more consistent behavior than the current (list (list (car xs))). Currently, if you do something like

   >(pair '(1 3 5 7 9) +)
    (4 12 (9))
where one (or at least I) would expect (4 12 9) to be returned. Of course, this would give errors if the passed function requires two arguments, but I would say you should just watch out not to call it on a list with an odd number of elements. Any thoughts?

3. In the definition of w/uniq, why is + used instead of join? It seems strange to define join when + can do the same job.

4. In the definition of reclist, wouldn't it be easier to put f:car in the definition, and save some :car's in the definitions of some, mem, and find?

5. I'm new to lisp, and don't have a CS background, but I thought the whole point of trying to get tail recursion was so that a compiler can take a recursive definition and transform it into a more efficient loop. Given that, isn't it a little backwards to define the loop macro using an anonymous, recursive function? Or is efficiency not the primary goal here? (I would also think an imperative implementation would be more readable, but perhaps I just haven't read enough lisp yet :-) ).

6. In many of the .arc files, there are names appended with asterisks, often things that would remain constant. Is there any specific significance to this?

[edit: code formatting]



6 points by fallintothis 5245 days ago | link

1.

  arc> (when nil (prn "I will not get evaluated, because this is a macro."))
  nil
  arc> (def when2 (test . body) (if test (do body)))
  #<procedure: when2>
  arc> (when2 nil (prn "I get evaluated anyways, because this is a function call."))
  I get evaluated anyways, because this is a function call.
  nil
in is an interesting case, because it's a macro for efficiency reasons: it expands into simpler code with fewer function calls than, say, a call to some. This is kind of how Arc does function inlining, rather than making a compiler infer it. See http://en.wikipedia.org/wiki/Inline_function.

2. Different strokes for different folks, I guess. I don't think I've ever used the f argument of pair, myself. You can accomplish your goal with

  arc> (map [apply + _] (pair '(1 3 5 7 9)))
  (4 12 9)
though that's inefficient.

3. The comment above the definition of join says

  ; Rtm prefers to overload + to do this
Rtm is Robert Morris, who plays a role in Arc's implementation / design. This would indicate that Paul Graham (the "main" designer of Arc) prefers to use join, but is unsure which is best.

4. Ah, but then you'd lose information. e.g., the definition of mem is

  (def mem (test seq)
    (let f (testify test)
      (reclist [if (f:car _) _] seq)))
Here, we want to return the entire sublist, not just the car, but we want to apply f specifically to the car of the sublist. So, we don't want to make reclist only work on the car, since we'd lose said sublist. That is, the current mem behavior is

  arc> (mem 5 '(8 6 7 5 3 0 9))
  (5 3 0 9)
But by adding car to reclist, we'd only be able to do something like

  arc> (mem 5 '(8 6 7 5 3 0 9))
  5
5. Tail calls should be recognizable in the call-graph of the code. For example, the mutually recursive functions

  (def even/r (n)
    (if (is n 0)
        t
        (odd/r (- n 1))))

  (def odd/r (n)
    (if (is n 0)
        nil
        (even/r (- n 1))))
involve tail recursion, even though neither even/r nor odd/r call themselves directly. Since the function in loop is a tail call (the ,gfn call is the last function before a return), it should still be optimized. Someone please correct me if I'm wrong.

6. No significance aside from naming conventions: asterisks follow the names of global variables.

-----

1 point by graphene 5243 days ago | link

Thanks to both of you for your answers; they're very helpful.

I had to take some time to digest them (and my day job got in the way) but I have a few follow-up remarks/questions:

1. is clear now; however I get the feeling that I need to play with macros more to get a real feeling for when and why they are as useful as many people say.

2. refering to fallintothis' answer, do you mean inefficient in execution (why, and as opposed to what?) or simply a bit of a drag to type out?

referring to akkartik's response, It's not that I thought the definition of pair breaks anything, just that it produces non-useful behavior (my original wording of inconsistent probably doesn't describe well what I mean); Is there a use case where you would pass a function to pair, but in the event of an odd number of elements, want the last element simply returned as a one-element list instead of the result of calling the function on it?

5. I get that it should still be optimized, but it just seems strange to me to implement it recursively when that's not the most straightforward (to me at least) way to define a loop macro.

Is the rule in Arc (or lisp in general) that preference is given to functional implementations wherever possible, or am I reading too much into this?

6. Both your explanations seemed strange to me at first (since in other languages, global variables are technically different from normal (is there a term for this?) variables). But it makes sense to me when you consider lisp's lexical scope (which the arc tutorial unfortunately doesn't cover other than mentioning closures); is a global variable simply one that is defined at the highest level of the code, i.e. only enclosed within one (the outermost) pair of parentheses?

-----

5 points by fallintothis 5243 days ago | link

1. My dirty little secret: after enough experience with macros, they seem pretty "normal" to me. They're a natural way to do what they do, so when I pause to write a macro, it doesn't even seem like some deep magic of an ultra-language. There's no need to be a zealot to appreciate macros, though their utility is apparent with time. For example, the definition of the while macro

  (mac while (test . body)
    (w/uniq (gf gp)
      `((rfn ,gf (,gp)
          (when ,gp ,@body (,gf ,test)))
        ,test)))
transforms clear code like

  (while (> x 10)
    (-- x))
into tedious code like

  ((rfn gs1722 (gs1723)
     (when gs1723
       (-- x)
       (gs1722 (> x 10))))
   (> x 10))
before it gets evaluated. We didn't even need to bake a while loop into the language -- we can define it using the macro.

It's not impossible to write while without macros. For instance, in the Factor language, while works by using anonymous functions instead of unevaluated code. It's similar to the Arc function

  (def while (test body)
    ((afn (condition)
       (when condition
         (body)
         (self (test))))
     (test)))
But in Arc, you'd need to write something like

  (while (fn () (> x 10))
         (fn () (-- x)))
Whereas Factor has less syntactic overhead for anonymous functions. So for Arc, a while macro is a clear solution.

2. All of the above! It's clearly longer. One way it's inefficient is in how many cons cells it creates (more cons = more memory):

  arc> (= cons-count* 0)
  0
  arc> (let old-cons cons
         (def cons (x y)
           (++ cons-count*)
           (old-cons x y)))
  *** redefining cons
  #<procedure: cons>
  arc> (pair '(1 3 5 7 9) +)
  (4 12 (9))
  arc> cons-count*
  4
  arc> (= cons-count* 0)
  0
  arc> (map [apply + _] (pair '(1 3 5 7 9)))
  (4 12 9)
  arc> cons-count*
  11
In the map version we first pair up the elements into a new list, then iterate through that to add the pairs, putting those into yet another list. We're doing twice the work. If pair worked right, we'd only go through '(1 3 5 7 9) once, adding the pairs of numbers as we went.

5. Not reading too much into it: functional solutions are generally preferred. My best guess says it's a matter of taste. To me, state is weird to reason about, but recursion is straightforward. Also consider that, to implement a loop statefully, you'd need something like goto. But we still have first-class functions, so if we can model loops as tail calls at no cost to efficiency, then we don't need to add goto to Arc. It keeps the language simpler.

This isn't the case in all Lisps. For example, Common Lisp has tagbody wherein you can use go, which is a goto statement. See http://sunsite.univie.ac.at/textbooks/cltl/clm/node91.html. Implementations often use it for, e.g., the loop macro (which is quite different from Arc's, but still loops).

6. Yes, global variables are the ones "at the top".

  arc> (= global* 10)                                        
  10
Local variables (the opposite of global variables) only live inside a block of code (i.e., locally), and can be different values during different function calls.

  arc> (def f (local)
         (+ global* local))
  #<procedure: f>
  arc> (f 10) ; during execution, 'local' is bound to 10 inside 'f'
  20
  arc> (f 123) ; during execution, 'local' is bound to 123 inside 'f'
  133
Global variables live everywhere (i.e., globally), and tend to change less frequently -- you set them explicitly to some value.

  arc> global*
  10
  arc> local ; isn't around outside of 'f'
  Error: "reference to undefined identifier: _local"
  arc> (= global* 5)
  5
  arc> (f 10)
  15
  arc> (f 123)
  128
You can alter local variables, too, but they still only live locally.

  arc> (let local 5
         (= local 10)
         (+ global* local))
  15
  arc> global*
  5
  arc> local
  Error: "reference to undefined identifier: _local"

-----

2 points by graphene 5243 days ago | link

Thanks for the explanations, I really appreciate it; everything seems clear now...

Now I'm off to build my own facebook clone :-)

-----

4 points by akkartik 5245 days ago | link

Some of these are pretty good questions. I'll start with the easiest.

6. * suffix denotes globals. It's just a convention, may be violated in some places.

3. Yes, you could use +. The arc codebase is like others in that it was added to over time, and you can see the evidence for that. In this example, + probably didn't support lists until after w/uniq was implemented. Other examples are new syntactic sugar that hasn't spread through the codebase (http://arclanguage.org/item?id=10974)

Update Another example of arc's non-uniform implementation: functions like copylist, map1, pair could be shorter by inverting the condition. I can't help thinking I'm missing something there, though.

4. At first glance, reclist also returns a list suffix rather than just an element.

Your version is less general, but if you keep finding yourself doing f:car perhaps there's a case for a variant.

2. Is there an example where the current version is broken?

5. I'd be very surprised if an iterative version bought you much performance, with all the other inefficiencies in arc. Also, it's kinda pretty to imagine recursion implemented by iteration implemented by recursion.. :)

-----

4 points by aw 5245 days ago | link

Why was a macro used to define when and not a function?

Ah, but your definition of when2 doesn't work:

  arc> (= x 1)
  1
  arc> (when nil (= x 2))
  nil
  arc> x
  1
  arc> (when2 nil (= x 3))
  nil
  arc> x
  3
When you call a function, the arguments to the function are evaluated before the function is called.

-----

3 points by graphene 5245 days ago | link

OK thanks, I feel as if I should have caught that..

I'll have to put some thought into what the consequences of that are exactly..

Thanks for your answer :-)

-----