★ /prog/ Challenge Vol. 5 ★

The challenge suggestion thread was too busy going nowhere, and I feel like writing some code, so here is a /prog/ challenge.

THE CHALLENGE:
Design a ^_toy programming language. You may implement either a compiler or interpreter, and you may write the implementation in any language of your choosing.

Post the source code to your implementation as well as programs in your language to accomplish ^{at least} two of the following tasks, plus one ``wild card'' program not listed here.

    • Factorial calculator
    • Fibonacci sequence generator
    • Prime number sieve (e.g. Eratosthenes, Atkin, etc.)
    • fgrep (output lines of input containing a given string)
    • Caesar cipher
    • Simple interactive calculator
    • Tic-tac-toe (AI not required)
    • The game of Nim (http://en.wikipedia.org/wiki/Nim)

Entries must be submitted prior to 2010-06-21 00:00, which gives one full week and two weekends. Judgment will be in three categories: presentation and cleverness of designed language, clarity of implementation, and overall usefulness/entertainment/trolling value of the ``wild card'' program.

Winner will receive ten Susscoins, to be transferred via /prog/mail.

>>14 is done. It even fit in comments. Though I gave up on implementing langauge with lists, zips because tasks do not require it.

What did I win?

#!/usr/bin/python3

# ANonymous
# Artifical Language

import sys


# Syntax:
# something - instruction / guranteed stack delta

# INTEGER x(2 x, 3 x, 555 x) - pops top element and push it INTEGER times. /INTEGER-2
# INTEGER m- moves top element INTEGER times into the stack:
#    stack:{a b c d e} cmd:2 m -> {a b e c d}
#
# << read integer
# >> output integer/string
# [code block/array] - pushes  code block on stack/1
# integer - pushes integer on stack /1
# [code block] ! - executes code block, /-2
# [code block] N ! - executes code block N times /-3
# + addition

def readInt():
    return int(sys.stdin.readline())

def parseAnal(source):
    commands0 = source.split()
   
    commands = []

    # pack blocks
    blocks = []
    blocks.append(commands)

    i = 0
    while i < len(commands0):
        if commands0[i] not in "[]":
            blocks[-1] += [commands0[i]]
            i += 1
            continue
        if commands0[i] == '[':
            newBlock = []
            blocks[-1] += [newBlock]
            blocks += [newBlock]
            i += 1
            continue
        if commands0[i] == ']':
            del blocks[-1]
            i += 1
            continue
   
    assert len(blocks) == 1
    return blocks[0]

# return true if types of top of stack matches the given pattern
# examples: stack: ["hello",3], pattern: "SI" (string, integer) return true
# (note, we don't have strings yet)
#
def stackMatches(stack, pattern):
    if len(stack) < len(pattern):
        return False
    matches = {str : 'S', int: 'I', list: 'B'}
    pattern = pattern[::-1] # reverse to match stack order
    for i in range(len(pattern)):
        if matches[type(stack[-1-i])] != pattern[i]:
            return False
    return True

stack = []
def evalAnal(blocks):
    global stack
    while True:
        [block, i] = blocks[-1]
        if i >= len(block):
            break

        if type(block[i]) == list:
            stack.append(block[i])
            blocks[-1][1] += 1
            continue

        if type(block[i]) == str:
            #push int
            if block[i][0] in "0123456789":
                stack.append(int(block[i]))
                blocks[-1][1] += 1
                continue
            # dup
            if block[i] == "x":
                n = stack[-1]
                del stack[-1]
                top = stack[-1]
                del stack[-1]
                stack += [top] * n
                blocks[-1][1] += 1
                continue
            # debug: print stack
            if block[i] == "p":
                print(stack)
                blocks[-1][1] += 1
                continue
            # pop
            if block[i] == ">>>":
                del stack[-1]
                blocks[-1][1] += 1
                continue
            # move
            if block[i] == "m":
                delta = -stack[-1]
                del stack[-1]
                stack.insert(delta-1, stack[-1])
                del stack[-1]
                blocks[-1][1] += 1
                continue
            # mult
            if block[i] == "*":
                stack.append(stack[-1] * stack[-2])
                del stack[-2]
                del stack[-2]
                blocks[-1][1] += 1
                continue
            # add
            if block[i] == "+":
                stack.append(stack[-1] + stack[-2])
                del stack[-2]
                del stack[-2]
                blocks[-1][1] += 1
                continue
            # read
            if block[i] == "<<":
                stack.append(readInt())
                blocks[-1][1] += 1
                continue
            # write
            if block[i] == ">>":
                print(stack[-1])
                del stack[-1]
                blocks[-1][1] += 1
                continue
            # exec
            if block[i] == "!":
                if stackMatches(stack, "BI"):
                    n = stack[-1]
                    b = stack[-2]
                    del stack[-2:]
                    blocks[-1][1] += 1
                    while n > 0:
                        n-=1
                        evalAnal([[b,0]])
                    continue
                   
        print(block[i])
        assert not "implemented"


def execAnal(source):
    commands = parseAnal(source)
    blocks = [[commands,0]]
    evalAnal(blocks)

def fibo():
    execAnal("0 1 [ 3 x >> 2 m + ] << !")

def fact():
    execAnal("1 0 [  1 + 2 x 2 m * 1 m ] << ! >>> >> ")

def additor():
    execAnal("<< << + >>")

if len(sys.argv) > 1:
    execAnal(sys.argv[1])
    exit(1)

fibo()