Is there a way to use this MACRO-based language to calculate fibnacci iteratively?

Question

I tried to work out a python-like language which combined with the feature of MACRO(weird, but just for fun..), for example, the codes to calculate fibonacci seq analyticly is like this:

from math import *

def analytic_fibonacci(n):
  sqrt_5 = sqrt(5);
  p = (1 + sqrt_5) / 2;
  q = 1/p;
  return int( (p**n + q**n) / sqrt_5 + 0.5 )

print analytic_fibonacci(10),

And I can rewrite it in the python-like-with-MACRO language like this:

from math import sqrt
sqrt
def analytic_fibonacci(n):
    _2(5)
    (1+_1)/2
    1/_1
    return int((_2**n+_1**n)/_3+0.5)
print analytic_fibonacci(10)

The idea is to use line number to expand the expression so that no explicit assignment is needed. The _2 means to replace it with the expression appeared 2 lines smaller than the current line, so the _2 in the 4th line becomes the expression in the 2nd line, which is sqrt, and _2(5) is expanded to sqrt(5). (Lines before current line starts with _, after current line starts with |)

The example above is simple. When I tried to rewrite a more complex example, I encountered problem:

def fibIter(n):
    if n < 2:
        return n
    fibPrev = 1
    fib = 1
    for num in xrange(2, n):
        fibPrev, fib = fib, fib + fibPrev
    return fib

I don't know how to use the line-number-based MACRO to express fibPrev, fib = fib, fib + fibPrev. I think some features is missing in this "MACRO langugage" , and fibPrev, fib = fib, fib+fibPrev is expressible if I fixed it.. (I heard that the MACRO in Lisp is Turing Complete so I think the example above should be expressed by MACRO) Does anyone have ideas about this?

Answer 1

I see two ways to interpret your language. Neither is very powerful.

The first way is to literally expand the macros to expressions, rather than values. Then analytic_fibonacci expands to

def analytic_fibonacci(n):
    return int(((1+sqrt(5))/2**n+1/(1+sqrt(5))/2**n)/sqrt(5)+0.5)

You probably want some parentheses in there; depending on how you define the language, those may or may not be added for you.

This is pretty useless. Multiple-evaluation problems abound (where a function is reexecuted every time a macro refers to it), and it only lets you do things you could have done with ordinary expressions.

The second interpretation is that every statement consisting of a Python expression implicitly assigns that expression to a variable. This is also pretty useless, because only one statement can assign to any of these implicit variables. There's no way to do

x = 0
for i in range(5):
    x += i

because you can't have the equivalent of x refer to either _2 or _0 depending on where the last assignment came from. Also, this really isn't a macro system at all.

Using the second interpretation, we can add a new operator to bring back the power of ordinary variable assignments. We'll call this the merge operator.

merge(_1, _2)

evaluates to either _1 or _2, depending on which was evaluated most recently. If one of the arguments hasn't yet been evaluated, it defaults to the other. fibIter then becomes

def fibIter(n):
    if n < 2:
        return n
    1 # fibPrev
    1 # fib
    for num in xrange(2, n):
        merge(_2, _-1) # temp
        merge(_4, _-1) + merge(_3, _0) # fib
        _2 # fibPrev
    return merge(_2, _5)

This is quite awkward; essentially, we have to replace every use of a variable like x by a merge of every location it could have been assigned. It also requires awkward line counting, making it hard to tell which "variable" is which, and it doesn't handle multiple assignments, for loop targets, etc. I had to use negative indices to refer to future lines, because we need some way to refer to things assigned later.

Lisp macros are more powerful than your language because they let you apply arbitrary Lisp code to your Lisp code. Your language only allows a macro to expand to fixed expressions. A Lisp macro can take arbitrary code as arguments, cut it up, rearrange it, replace parts of it with different things depending on conditionals, recurse, etc. Your macros can't even take arguments.