ANN: unlambda.py

[Ben Wolfson]

unlambda.py is an interpreter for the Unlambda language and is the product
of work since all of yesterday, so I'm not sure that everything works
right.

The language is described at
<http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/>

'''
An interpreter for the Unlambda programming language.  I believe everything
is here and
working correctly, but not all of the functions are tested.  The d and c
primitives should
work correctly, and the script will correctly interpret
<ftp://quatramaran.ens.fr/pub/madore/unlambda/CUAN/quine/quine00.unl>, an
Unlambda quine, so I'm
reasonably confident that it should work.  getChurchNum() and
naiveAbsElim() could be used to
aid actually writing Unlambda programs, if for some reason you wanted to do
that, but currently
aren't integrated with the rest of the script.

There are probably some memory issues.

#---unlambda.py

'''

__version__ = '0.1'

import sys

def getChurchNum(num_or_numstring):
    num = int(num_or_numstring)
    result = '^f^x'
    for i in range(num):
        result = result + '`$f'
    return naiveAbsElim(result + '$x')

def naiveAbsElim(expr):
    #all valid expressions are at least 3 chrs
    print 'Recieved: ', expr
    myRepl = expr[1]
    result = ''
    expr = expr[2:]
    if expr[0] == '^':
        expr = naiveAbsElim(expr)
    i = 0
    while i < len(expr):
        ch = expr[i]
        if ch == '`':
            result = result + '``s'
        elif ch == '$':
            i = i + 1
            ch = expr[i]
            if ch == myRepl:
                result = result + 'i'
            else:
                result = result + '`k$%c' % ch
        else:
            result = result + '`k%c' % ch
        i = i + 1
    return result

def v_func(arg):
    return v_func

def dot_func(ch):
    def _dot_func(arg, ch=ch):
        sys.stdout.write(ch)
        return arg
    return _dot_func

def r_func(arg):
    sys.stdout.write('\n')
    return arg

def pipe_fun(arg):
    global curchar
    if curchar:
        return arg( dot_func(curchar) )
    return arg(v_func)

def i_func(arg):
    return arg

def s_func(firstarg):
    def s1_func(secondarg, firstarg=firstarg):
        def s2_func(thirdarg, secondarg=secondarg, firstarg=firstarg):
            result1 = firstarg(thirdarg)
            result2 = secondarg(thirdarg)
            return result1(result2)
        return s2_func
    return s1_func

def k_func(firstarg):
    def k1_func(secondarg, firstarg=firstarg):
        return firstarg
    return k1_func

class btick:
    def __call__(self, i=0):
        global theprogram
#        print 'in index %d,' % i,
        if isinstance(theprogram[i+1], btick):
#            print 'ascend to %d' % (i + 1)
            theprogram[i+1](i+1)
            return
#        else: print "don't go up one,",
        if isinstance(theprogram[i+2], btick) and not
isinstance(theprogram[i+1], continuation) and not
isinstance(theprogram[i+1],delay):
#            print 'ascend to %d' % (i + 2)
            theprogram[i+2](i+2)
            return
#        else: print "don't go up two,",
#        print 'apply %s to %s with index %d' % (ptp1(theprogram[i+1]),
ptp1(theprogram[i+2]), i) ###
        result = theprogram[i+1](theprogram[i+2])
        if type(result) == type(()):
            result, i = result
        if result: #necessary in case theprogram[i+1] was a continuation
            theprogram = theprogram[:i] + [result] + theprogram[i+3:]
#        print 'the program now:\n\t %s' % ptp() ###
        if not i: return
        for dex in range(i - 1, -1, -1):
            if isinstance(theprogram[dex], btick):
                call = theprogram[dex]
#                print 'drop back down to %i, where we' % dex,
                index = dex
                break
        else:
            return
        call(index)

class delay:
    def __call__(self, arg):
        global theprogram
        self.startofpromise = theprogram.index(self) + 1
        self.endofpromise = getendofexpression(self.startofpromise)
        self.promiseprogram =
theprogram[self.startofpromise:self.endofpromise]

        #Keep one from the promise section to make it look as if something
were actually evaluated
        del theprogram[self.startofpromise + 1:self.endofpromise]
        return self.promise

    def promise(self, arg):
        #restore promise
        global theprogram
        index = theprogram.index(self.promise)
        theprogram = theprogram[:index] + self.promiseprogram +
theprogram[index+1:]
        return (None, index-1)
            
    

def getendofexpression(start):
    global theprogram
    ticks = 1
    while ticks != 0:
        if isinstance(theprogram[start], btick):
            ticks = ticks + 1
        else:
            ticks = ticks - 1
        start = start + 1
    return start

class continuation:
    def __call__(self, arg):
        index = theprogram.index(self)
        self.applicationpoint = getendofexpression(index + 1)
        global theprogram
        self.preservedprogram = theprogram[:]
        for i in range(index - 1, -1, -1):
            if isinstance(theprogram[i], btick):
                self.indexofcaller = i
                break
        del theprogram[index]
        theprogram.insert(self.applicationpoint - 1, self.timetravel)
        theprogram[index-1]() #apply the backtick

    def timetravel(self, arg):
        #get here only if there had been a `cEXPRESSION, and in the
resulting `EXPRESSION<cont>
        #something was applied to the continuation
#        print 'traveled through time' ###
        global theprogram
        #restore the program
        theprogram = self.preservedprogram[:]
#        print 'restored program: \n\t%s' % ptp()
#        print 'restored index of caller: %d' % self.indexofcaller
#        print 'returning %s' % ptp1(arg)
        #return whatever it was the continuation was called on
        #plus info to properly restore state of caller
        return (arg, self.indexofcaller)


def e_func(arg):
    if arg == v_func:
        sys.exit(1)
    sys.exit(0)

def at_func():
    def _at_func(arg):
        global curchar
        try:
            curchar = sys.stdin.read(1)
        except EOFError:
            return result_func(v_func)
        else:
            return result_func(i_func)
    return _at_func


def qmark_func(cmpchar):
    def _qmark_func(arg,cmpchar=cmpchar):
        if cmpchar == curchar:
            return arg(i_func)
        return arg(v_func)
    return _qmark_func
        
def genlist(program):
    result = []
    i = 0
    while i < len(program):
        char = program[i]
        if char == '#':
            i = i + 1
            while program[i] != '\n' and i < len(program):
                i = i + 1
            continue
        elif char in (' ','\t','\n'):
            pass
        elif simplechartofunc.has_key(char):
            result.append(simplechartofunc[char])
        elif constructorchartofunc.has_key(char):
            result.append( constructorchartofunc[char]() )
        elif takenextchar.has_key(char):
            i = i + 1
            nextchar = program[i]
            result.append( takenextchar[char](nextchar) )
        i = i + 1
    if not checkticks(result):
        raise Exception, "Apparently incorrect tick count in: \n\n\t%s" %
program
    global theprogram
    theprogram = result
#    print ptp()

def checkticks(oplist):
    if not (isinstance(oplist[0], btick)): return None
    ticks = 1
    for node in oplist:
        if isinstance(node, btick):
            ticks = ticks + 1
        else:
            ticks = ticks - 1
    return not ticks

def ptp():
    global theprogram, reversemap
    result = ''
    for i in theprogram:
        result = result + ptp1(i)
    return result

def ptp1(a):
    global reversemap
    name = getattr(a, 'func_name', 0)
    if not name:
        name = getattr(a, '__name__',0)
    if not name:
        name = a.__class__.__name__
    return reversemap[name]
    

simplechartofunc = {
    'e':e_func,
    'v':v_func,
    'i':i_func,
    'k':k_func,
    's':s_func,
    'r':r_func,
    '@':at_func,
    '|':pipe_func
    }

takenextchar = {
    '.':dot_func,
    '?':qmark_func
    }

constructorchartofunc = {
    'c':continuation,
    '`':btick,
    'd':delay
    }

curchar = None

reversemap = {}
for key, value in simplechartofunc.items() + takenextchar.items():
    reversemap[value.func_name] = key
reversemap[k_func(1).func_name] = 'k1'
reversemap[s_func(1).func_name] = 's1'
reversemap[dot_func(1).func_name] = '.1'
reversemap[s_func(1)(1).func_name] = 's2'
reversemap[continuation.timetravel.__name__] = 'C'
reversemap[btick.__name__] = '`'
reversemap[continuation.__name__] = 'c'
reversemap[delay.__name__] = 'd'

def main():
    if len(sys.argv) == 2:
        genlist(open(sys.argv[1], 'r').read())
    else:
        genlist(sys.stdin.read())
    theprogram[0]()

if __name__ == '__main__':
    main()

#---End unlambda.py