small language in python
Question: I'm writing what might not even be called a language in python. I currently
have several operators: `+`, `-`, `*`, `^`, `fac`, `@`, `!!`. `fac` computes a
factorial, `@` returns the value of a variable, `!!` sets a variable. The code
is below. How would I go about writing a way to define functions in this
simple language?

EDIT: i updated the code!

    
    
    import sys, shlex, readline, os, string
    List, assign, call, add, sub, div, Pow, mul, mod, fac, duf, read,\
    kill, clr, STO, RET, fib, curs = {}, "set", "get", "+", "-", "/", "^", "*",\
    "%", "fact", "func", "read", "kill", "clear", ">", "@", "fib", "vars"
    def fact(num):
        if num == 1: return 1
        else: return num*fact(num-1)
    def Simp(op, num2, num1):
        global List
        try: num1, num2 = float(num1), float(num2)
        except:
            try: num1 = float(num1)
            except:
                try: num2 = float(num2)
                except: pass
        if op == mul: return num1*num2
        elif op == div: return num1/num2
        elif op == sub: return num1-num2
        elif op == add: return num1+num2
        elif op == Pow: return num1**num2
        elif op == assign: List[num1] = num2; return "ok"
        elif op == call: return List[num1]
        elif op == fac: return fact(num1)
        elif op == duf: return "%s %s %s"%(duf, num1, num2)
        elif op == mod: return num1%num2
        elif op == kill: del List[num1]; return "ok"
        elif op == clr: os.system("clear")
        elif op == STO: List[num2] = num1; return "ok"
        elif op == RET: return List[num1]
        elif op == curs: return List
        elif op == read: List[num1] = Eval(raw_input("%s "%num1)); return "ok"
    def Eval(expr):
        ops = "%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s"%(mul, add, sub, div, Pow, assign, call, fac, duf, mod, read, kill, clr, STO, RET, curs)
        stack, expr, ops = [], shlex.split(string.lower(expr)), ops.split()
        for i in expr:
            if i[0] != ';':
                if i not in ops: stack.append(i)
                elif i in ops: stack.append(Simp(i, stack.pop(), stack.pop()))
            else: stack.append("ok")
        return stack[0]
    def shell():
        try:
            x = ""
            while x != "quit":
                x = raw_input("star>   ")
                try: l = Eval(x)
                except KeyError: l = "does not exist"
                except: l = "parse error!"
                if l != None: print "   =>",l,"\n"
        except (EOFError, KeyboardInterrupt): print
    if len(sys.argv) > 1:
        x = open(sys.argv[1], 'r'); l = x.readlines(); x.close()
        for i in l:
            if i[0] != ";":
                i = ' '.join(i.split())
                x = Eval(i)
                if x != None: print i,"\n   =>",x,"\n"
            else: pass
        shell()
    else: shell()
    


Answer: Your program is very confused, and it needs to be fixed before it can be
modified to support defining functions. I will do this in several steps and as
I complete them, I will add them into the answer. This answer will get to be
quite long.

Also, you obviously haven't decided what your language definition should be.
You've decided to make your language definition sort of follow your
implementation technique, and this is kind of broken, and results in a lot of
pain.

First, the definition for your `Simp` function is really broken. It demands
that everything take exactly two values off the stack, and put exactly one
value back on. This is broken. The factorial function doesn't work this way,
nor does the Fibonacci function, so you are forced to have a 'dummy' argument
that's never used. Also, things like assigning to an element of your global
list or dictionary have no reason to push values onto the stack, so you're
left pushing 'ok'. This is broken and needs fixing.

Here is the version with this problem fixed. Notice that I've renamed `Simp`
to `builtin_op` to more accurately reflect its purpose:

    
    
    import sys, shlex, readline, os, string
    List, assign, call, add, sub, div, Pow, mul, mod, fac, duf, read,\
    kill, clr, STO, RET, fib, curs = {}, "set", "get", "+", "-", "/", "^", "*",\
    "%", "fact", "func", "read", "kill", "clear", ">", "@", "fib", "vars"
    def fact(num):
        if num == 1: return 1
        else: return num*fact(num-1)
    def builtin_op(op, stack):
        global List
        if op == mul: stack.append(float(stack.pop())*float(stack.pop()))
        elif op == div: stack.append(float(stack.pop())/float(stack.pop()))
        elif op == sub: stack.append(float(stack.pop())-float(stack.pop()))
        elif op == add: stack.append(float(stack.pop())+float(stack.pop()))
        elif op == Pow: stack.append(float(stack.pop())**float(stack.pop()))
        elif op == assign: val = List[stack.pop()] = stack.pop(); stack.append(val)
        elif op == call: stack.append(List[stack.pop()])
        elif op == fac: stack.append(fact(stack.pop()))
        elif op == duf: stack.append("%s %s %s" % (duf, stack.pop(), stack.pop()))
        elif op == mod: stack.append(float(stack.pop())%float(stack.pop()))
        elif op == kill: del List[stack.pop()]
        elif op == clr: os.system("clear")
        elif op == STO: val = List[stack.pop()] = stack.pop(); stack.append(val)
        elif op == RET: stack.append(List[stack.pop()])
        elif op == curs: stack.append(List)
        elif op == read: prompt = stack.pop(); List[prompt] = Eval(raw_input("%s "%prompt)); stack.append(List[prompt])
    def Eval(expr):
        ops = "%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s"%(mul, add, sub, div, Pow, assign, call, fac, duf, mod, read, kill, clr, STO, RET, curs)
        stack, expr, ops = [], shlex.split(string.lower(expr)), ops.split()
        for i in expr:
            if i[0] != ';':
                if i not in ops: stack.append(i)
                elif i in ops: builtin_op(i, stack)
            else: stack.append("ok")
        return stack[0]
    def shell():
        try:
            x = ""
            while x != "quit":
                x = raw_input("star>   ")
                try: l = Eval(x)
                except KeyError: l = "does not exist"
                except: l = "parse error!"
                if l != None: print "   =>",l,"\n"
        except (EOFError, KeyboardInterrupt): print
    if len(sys.argv) > 1:
        x = open(sys.argv[1], 'r'); l = x.readlines(); x.close()
        for i in l:
            if i[0] != ";":
                i = ' '.join(i.split())
                x = Eval(i)
                if x != None: print i,"\n   =>",x,"\n"
            else: pass
        shell()
    else: shell()
    

There are still a number of problems here that aren't fixed, and I won't fix
in any future version. For example, it's possible a value on the stack cannot
be interpreted as a floating point number. This will cause an exception, and
this exception may be thrown before the other value is read off the stack.
This means that if the wrong 'types' are on the stack the stack could be in an
ambiguous state after a 'parse error'. Generally you want to avoid situations
like this in a language.

Defining functions is an interesting problem. In your language, evaluation is
immediate. You don't have a mechanism for delaying evaluation until later.
But, you're using the `shlex` module for parsing. And it has a way of saying
that a whole group of characters (including spaces and such) are part of one
entity. This gives us a quick and easy way to implement functions. You can do
something like this:

    
    
    star>   "3 +" add3 func
    

to create your function, and:

    
    
    star>   2 add3 get
    

to call it. I used `get` because that's what you've assigned to `call` in your
program.

The only problem is that the function is going to need access to the current
state of the stack in order to work. You can easily feed the string for the
function back into `Eval`, but `Eval` always creates a brand new stack each
time it is called. In order to implement functions, this needs to be fixed. So
I've added a defaulted `stack` argument to the `Eval` function. If this
argument is left at its default value, `Eval` will still create a new stack,
just like before. But if an existing stack is passed in, `Eval` will use it
instead.

Here is the modified code:

    
    
    import sys, shlex, readline, os, string
    List, assign, call, add, sub, div, Pow, mul, mod, fac, duf, read,\
    kill, clr, STO, RET, fib, curs = {}, "set", "get", "+", "-", "/", "^", "*",\
    "%", "fact", "func", "read", "kill", "clear", ">", "@", "fib", "vars"
    funcdict = {}
    def fact(num):
        if num == 1: return 1
        else: return num*fact(num-1)
    def builtin_op(op, stack):
        global List
        global funcdict
        if op == mul: stack.append(float(stack.pop())*float(stack.pop()))
        elif op == div: stack.append(float(stack.pop())/float(stack.pop()))
        elif op == sub: stack.append(float(stack.pop())-float(stack.pop()))
        elif op == add: stack.append(float(stack.pop())+float(stack.pop()))
        elif op == Pow: stack.append(float(stack.pop())**float(stack.pop()))
        elif op == assign: val = List[stack.pop()] = stack.pop(); stack.append(val)
        elif op == call: Eval(funcdict[stack.pop()], stack)
        elif op == fac: stack.append(fact(stack.pop()))
        elif op == duf: name = stack.pop(); funcdict[name] = stack.pop(); stack.append(name)
        elif op == mod: stack.append(float(stack.pop())%float(stack.pop()))
        elif op == kill: del List[stack.pop()]
        elif op == clr: os.system("clear")
        elif op == STO: val = List[stack.pop()] = stack.pop(); stack.append(val)
        elif op == RET: stack.append(List[stack.pop()])
        elif op == curs: stack.append(List)
        elif op == read: prompt = stack.pop(); List[prompt] = Eval(raw_input("%s "%prompt)); stack.append(List[prompt])
    def Eval(expr, stack=None):
        ops = "%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s"%(mul, add, sub, div, Pow, assign, call, fac, duf, mod, read, kill, clr, STO, RET, curs)
        if stack is None:
            stack = []
        expr, ops = shlex.split(string.lower(expr)), ops.split()
        for i in expr:
            if i[0] != ';':
                if i not in ops: stack.append(i)
                elif i in ops: builtin_op(i, stack)
            else: stack.append("ok")
        return stack[0]
    def shell():
        try:
            x = ""
            while x != "quit":
                x = raw_input("star>   ")
                try: l = Eval(x)
                except KeyError: l = "does not exist"
                except: l = "parse error!"
                if l != None: print "   =>",l,"\n"
        except (EOFError, KeyboardInterrupt): print
    if len(sys.argv) > 1:
        x = open(sys.argv[1], 'r'); l = x.readlines(); x.close()
        for i in l:
            if i[0] != ";":
                i = ' '.join(i.split())
                x = Eval(i)
                if x != None: print i,"\n   =>",x,"\n"
            else: pass
        shell()
    else: shell()
    

In stack based languages, two very useful built in operators are `dup` and
`swap`. `dup` takes the top stack element and duplicates it. `swap` swaps the
top two stack elements.

If you have `dup` you can implement a `square` function like so:

    
    
    star>   "dup *" square func
    

Here is your program with `dup` and `swap` implemented:

    
    
    import sys, shlex, readline, os, string
    List, assign, call, add, sub, div, Pow, mul, mod, fac, duf, read,\
    kill, clr, STO, RET, fib, curs, dup, swap = {}, "set", "get", "+", "-", "/", "^", "*",\
    "%", "fact", "func", "read", "kill", "clear", ">", "@", "fib", "vars", "dup", "swap"
    funcdict = {}
    def fact(num):
        if num == 1: return 1
        else: return num*fact(num-1)
    def builtin_op(op, stack):
        global List
        global funcdict
        if op == mul: stack.append(float(stack.pop())*float(stack.pop()))
        elif op == div: stack.append(float(stack.pop())/float(stack.pop()))
        elif op == sub: stack.append(float(stack.pop())-float(stack.pop()))
        elif op == add: stack.append(float(stack.pop())+float(stack.pop()))
        elif op == Pow: stack.append(float(stack.pop())**float(stack.pop()))
        elif op == assign: val = List[stack.pop()] = stack.pop(); stack.append(val)
        elif op == call: Eval(funcdict[stack.pop()], stack)
        elif op == fac: stack.append(fact(stack.pop()))
        elif op == duf: name = stack.pop(); funcdict[name] = stack.pop(); stack.append(name)
        elif op == mod: stack.append(float(stack.pop())%float(stack.pop()))
        elif op == kill: del List[stack.pop()]
        elif op == clr: os.system("clear")
        elif op == STO: val = List[stack.pop()] = stack.pop(); stack.append(val)
        elif op == RET: stack.append(List[stack.pop()])
        elif op == curs: stack.append(List)
        elif op == dup: val = stack.pop(); stack.append(val); stack.append(val)
        elif op == swap: val1 = stack.pop(); val2 = stack.pop(); stack.append(val1); stack.append(val2)
        elif op == read: prompt = stack.pop(); List[prompt] = Eval(raw_input("%s "%prompt)); stack.append(List[prompt])
    def Eval(expr, stack=None):
        ops = "%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s"%(mul, add, sub, div, Pow, assign, call, fac, duf, mod, read, kill, clr, STO, RET, curs, dup, swap)
        if stack is None:
            stack = []
        expr, ops = shlex.split(string.lower(expr)), ops.split()
        for i in expr:
            if i[0] != ';':
                if i not in ops: stack.append(i)
                elif i in ops: builtin_op(i, stack)
            else: stack.append("ok")
        return stack[0]
    def shell():
        try:
            x = ""
            while x != "quit":
                x = raw_input("star>   ")
                try: l = Eval(x)
                except KeyError: l = "does not exist"
                except: l = "parse error!"
                if l != None: print "   =>",l,"\n"
        except (EOFError, KeyboardInterrupt): print
    if len(sys.argv) > 1:
        x = open(sys.argv[1], 'r'); l = x.readlines(); x.close()
        for i in l:
            if i[0] != ";":
                i = ' '.join(i.split())
                x = Eval(i)
                if x != None: print i,"\n   =>",x,"\n"
            else: pass
        shell()
    else: shell()
    

Lastly, here is my version in Python that's much clearer (in my opinion
anyway) than the Python you've written:

    
    
    import shlex, functools, sys, StringIO
    
    def bin_numeric_op(func):
        @functools.wraps(func)
        def execute(self):
            n2, n1 = self._stack.pop(), self._stack.pop()
            n1 = float(n1)
            n2 = float(n2)
            self._stack.append(func(n1, n2))
        return execute
    
    def relational_op(func):
        @functools.wraps(func)
        def execute(self):
            n2, n1 = self._stack.pop(), self._stack.pop()
            self._stack.append(bool(func(n1, n2)))
        return execute
    
    def bin_bool_op(func):
        @functools.wraps(func)
        def execute(self):
            n2, n1 = self._stack.pop(), self._stack.pop()
            n1 = bool(n1)
            n2 = bool(n2)
            self._stack.append(bool(func(n1, n2)))
        return execute
    
    class Interpreter(object):
        def __init__(self):
            self._stack = []
            self._vars = {}
            self._squarestack = []
    
        def processToken(self, token):
            if token == '[':
                self._squarestack.append(len(self._stack))
            # Currently inside square brackets, don't execute
            elif len(self._squarestack) > 0:
                if token == ']':
                    startlist = self._squarestack.pop()
                    lst = self._stack[startlist:]
                    self._stack[startlist:] = [tuple(lst)]
                else:
                    self._stack.append(token)
            # Not current inside list and close square token, something's wrong.
            elif token == ']':
                raise ValueError("Unmatched ']'")
            elif token in self.builtin_ops:
                self.builtin_ops[token](self)
            else:
                self._stack.append(token)
        def get_stack(self):
            return self._stack
        def get_vars(self):
            return self._vars
        @bin_numeric_op
        def add(n1, n2):
            return n1 + n2
        @bin_numeric_op
        def mul(n1, n2):
            return n1 * n2
        @bin_numeric_op
        def div(n1, n2):
            return n1 / n2
        @bin_numeric_op
        def sub(n1, n2):
            return n1 - n2
        @bin_numeric_op
        def mod(n1, n2):
            return n1 % n2
        @bin_numeric_op
        def Pow(n1, n2):
            return n1**n2
        @relational_op
        def less(v1, v2):
            return v1 < v2
        @relational_op
        def lesseq(v1, v2):
            return v1 <= v2
        @relational_op
        def greater(v1, v2):
            return v1 > v2
        @relational_op
        def greatereq(v1, v2):
            return v1 > v2
        @relational_op
        def isequal(v1, v2):
            return v1 == v2
        @relational_op
        def isnotequal(v1, v2):
            return v1 != v2
        @bin_bool_op
        def bool_and(v1, v2):
            return v1 and v2
        @bin_bool_op
        def bool_or(v1, v2):
            return v1 or v2
        def bool_not(self):
            stack = self._stack
            v1 = stack.pop()
            stack.append(not v1)
        def if_func(self):
            stack = self._stack
            pred = stack.pop()
            code = stack.pop()
            if pred:
                self.run(code)
        def ifelse_func(self):
            stack = self._stack
            pred = stack.pop()
            nocode = stack.pop()
            yescode = stack.pop()
            code = yescode if pred else nocode
            self.run(code)
        def store(self):
            stack = self._stack
            value = stack.pop()
            varname = stack.pop()
            self._vars[varname] = value
        def fetch(self):
            stack = self._stack
            varname = stack.pop()
            stack.append(self._vars[varname])
        def remove(self):
            varname = self._stack.pop()
            del self._vars[varname]
        # The default argument is because this is used internally as well.
        def run(self, code=None):
            if code is None:
                code = self._stack.pop()
            for tok in code:
                self.processToken(tok)
        def dup(self):
            self._stack.append(self._stack[-1])
        def swap(self):
            self._stack[-2:] = self._stack[-1:-3:-1]
        def pop(self):
            self._stack.pop()
        def showstack(self):
            print"%r" % (self._stack,)
        def showvars(self):
            print "%r" % (self._vars,)
        builtin_ops = {
            '+': add,
            '*': mul,
            '/': div,
            '-': sub,
            '%': mod,
            '^': Pow,
            '<': less,
            '<=': lesseq,
            '>': greater,
            '>=': greatereq,
            '==': isequal,
            '!=': isnotequal,
            '&&': bool_and,
            '||': bool_or,
            'not': bool_not,
            'if': if_func,
            'ifelse': ifelse_func,
            '!': store,
            '@': fetch,
            'del': remove,
            'call': run,
            'dup': dup,
            'swap': swap,
            'pop': pop,
            'stack': showstack,
            'vars': showvars
            }
    
    def shell(interp):
        try:
            while True:
                x = raw_input("star>   ")
                msg = None
                try:
                    interp.run(shlex.split(x))
                except KeyError:
                    msg = "does not exist"
                except:
                    sys.excepthook(*sys.exc_info())
                    msg = "parse error!"
                if msg != None:
                    print "   =>",msg,"\n"
                else:
                    print "   => %r\n" % (interp.get_stack(),)
        except (EOFError, KeyboardInterrupt):
            print
    
    interp = Interpreter()
    if len(sys.argv) > 1:
        lex = shlex.shlex(open(sys.argv[1], 'r'), sys.argv[1])
        tok = shlex.get_token()
        while tok is not None:
            interp.processToken(tok)
            tok = lex.get_token()
    shell(interp)
    

This new version supports an `if` and `ifelse` statement. With this and
function calls, it's possible to implement the `fib` and `fact` functions in
the language. I will add in how you would define these later.

Here is how you would define the `fib` function:

    
    
    star>   fib [ dup [ pop 1 0 + ] swap [ dup 1 - fib @ call swap 2 - fib @ call + ] swap 0 + 2 0 + < ifelse ] !
       => []
    
    star>   15 fib @ call
       => [987.0]
    

The `0 + 2 0 +` sequence before the `<` is to force the comparison to be a
numeric comparison.

Also notice how the `[` and `]` single characters are quoting operators. They
cause everything between them to be not executed and instead stored on the
stack as a single list of items. This is the key to defining functions.
Functions are a sequence of tokens that you can execute with the `call`
operator. They can also be used for 'anonymous blocks' that are sort of a
cross between `lambda` expressions and a standard Python block. These are used
in the `fib` function for the two possible paths of the `ifelse` statement.

The parser for this is ridiculously simple. And `shlex` is plenty powerful
enough as a lexer for this simple language. Other projects would be fetching
individual items out of a list. Creating a new list that consists of only a
portion of a previous list. 'Listifying' a single token on the stack.
Implementation of a `while` primitive. Numeric operators that operate on
integers (in actual Forth, the numeric operations by default operate on
integers and you need to specify something like `+.` to get a floating point
version). And some operations on symbol tokens that allow string manipulation.
Perhaps a 'split' and 'join' operation that turns a token into a list of
individual tokens for the characters or joins a list together into a single
token would be sufficient.

