★ /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.

This interpreter/compiler can be written in any language? Jesus LISP fags have this easy...

>>2
I'm not so sure about that. A language implementation consisting largely of eval with trivial changes to another language's syntax is generally not very interesting or clever.

I'd like to participate.

However, I have never written a compiler or interpreter before so I am a complete and utter noob at this.

What is /prog/'s recommended reading on this subject?  I have Basics of Compiler Design¹ and Engineering A Compiler², and have only read the beginning of the latter so far (man is it wordy).

<sub>_________________________________________________
1. http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/ - Get it for free here
2. I donno, check The Pirate Bay.</sub>

>>4
Jesus christ, here's a hing: it's /prog/'s favorite book.

>>5
Ok, besides SICP.  I don't want to complete all of SICP to write a toy compiler.

>>6
Implementing a Lisp interpreter or compiler is usually easier than in most languages, since you don't have to write your own read (lexer/parser) if you're writing it in Lisp, and since the code is effectively an AST (S-Exp external representation) stored as normal lisp lists (chained cons cell trees) which the language usually provides extensive functions to work with (or if it doesn't, you can easily implement them anyway), you can get right to the task at hand: eval (interpretation) or compile(compilation). Not only that, but such languages are very nice for extending themselves from within via macros due to the language's homoiconic property.

Sadly, I've already written toy interpreters and compilers, so this isn't as interesting of a task, altough it's still fun, but I suppose I lack enough imagination for designing a truly awesome language (I'm sadly content with what I'm currently using, and only have small gripes with the language, which I can fix by writing a few functions/macros). Both interpreters and compilers being rather simple to do in Lisp, altough, real-world compilers are not trivial things, because one has many issues to consider when it comes to optimizations and code transformations one perform, not to mention things like gc's, the runtime, libraries, and so on.

>>7
Yeah, Lisp is cool and I'd like to learn it.  Just not right now.

I am already working on my own language, does that count if i finish and submit it?

>>1
pass, I've written enough toy interpreters to last a lifetime

Entries must be submitted prior to 2010-06-21 00:00, which gives one full week and two weekends.
I'm going to take this opportunity to remind everyone that the ICFP programming contest starts on Friday. So if you are going to compete in that, you really need to finish this by Thursday.

>>10
submit an old one

how long till Xarn posts a solution made using C and Allegro?

Ok. Count me in. I'm gonna to implement something like http://www.golfscript.com/golfscript/ just for sake of it.


Will report back later.

10 4 dispatch we're rolling.

Maybe I'll finally write Trollgol this time

>>12
I wrote an ANSI C compiler when I was 12

I predict exactly zero working entries.

I have written an interpreter in Haskell for AbcSM, an assembler-like extension to the abc programming language. Does that qualify?

>>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()

What did I win?
We won't know till it's over

EXPERT C SOLUTION. Work in progress. Currently solutions for problem 1 and 2.


/*   turd.c
 *
 *   turd language interpreter v0.01
 *
 *   Released under the GPL v3
 *
 *   Copyright (C)  (name withheld)
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define TYPE_UNKNOWN    0
#define TYPE_VAR        1
#define TYPE_BUILTIN    2
#define TYPE_FUNC        3

#define VAR_UNKNOWN        0
#define VAR_INT            1
#define VAR_STR            2

typedef struct {
    int type;
    int subtype;
    int iv;
    char *sv;
    int (*builtin)(int,char*);
} obj_t;

obj_t OBJ[128];
char *BUF[1024]; // 1024 lines max
int LINE;
char GOTO = 0;
int DEBUG = 0;

int *RI(char *s) {
    if(DEBUG) printf("RI: %s\n",s);
    static int I;
    I=0;
    if(isalpha(*s)) {
        if(OBJ[*s].type==TYPE_VAR) {
            switch(OBJ[*s].subtype) {
                case VAR_INT: I = OBJ[*s].iv; break;
                case VAR_STR: I = atoi(OBJ[*s].sv); break;
            }
        }
    } else {
        I = atoi(s);
    }
    return &I;
}

#define BUILTIN(n)    int builtin_ ## n (int v, char *s)
#define SET_BUILTIN(o,b) OBJ[o].type = TYPE_BUILTIN; OBJ[o].builtin = builtin_ ## b

BUILTIN(assign_int) {
    OBJ[v].iv = *RI(s);
    OBJ[v].type = TYPE_VAR;
    OBJ[v].subtype = VAR_INT;
    //printf("assign int: %c = %d\n",v,OBJ[v].iv);
    return 0;
}

BUILTIN(assign_str) {
    OBJ[v].type = TYPE_VAR;
    OBJ[v].subtype = VAR_STR;
    free(OBJ[v].sv);
    OBJ[v].sv = strdup(s);
    if(DEBUG) printf("assign str: %c = \"%s\"\n",v,OBJ[v].sv);
    return 0;
}

int *arithmetic_prepare(int v, char *s, int *c) {
    char *p,*f;
    int i;
    static int a[32];
    f = s = strdup(s);
    if(*s=='=') {
        // TODO verify current type
        if(DEBUG) printf("arithmetic: reflexive\n");
        s++;
    } else {
        if(DEBUG) printf("arithmetic: non-reflexive\n");
        OBJ[v].iv;
    }
    for(i=0;i<31;i++) {
        if((p = strchr(s,',')))
            *p++ = 0;
        a[i]=*RI(s);
        if(DEBUG) printf("list %02d: %d\n",i,a[i]);
        if(!p)
            break;
        s = p;
    }
END:
    OBJ[v].type = TYPE_VAR;
    OBJ[v].subtype = VAR_INT;
    if(*f=='=') {
        // reflexive
        *c = i+1;
        if(DEBUG) printf("list: return count %d\n",*c);
        free(f);
        return a;
    }
    free(f);
    *c = i;
    if(DEBUG) printf("list: return count %d\n",*c);
    OBJ[v].iv = a[0];
    return a+1;
}

BUILTIN(add) {
    int c,*a = arithmetic_prepare(v,s,&c);
    while(c--) { OBJ[v].iv += *a++; }
    if(DEBUG) printf("plus: result %c = %d\n",v,OBJ[v].iv);
    return 0;
}
BUILTIN(subtract) {
    int c, *a = arithmetic_prepare(v,s,&c);
    while(c--) { OBJ[v].iv -= *a++; }
    if(DEBUG) printf("subtract: result %c = %d\n",v,OBJ[v].iv);
    return 0;
}
BUILTIN(multiply) {
    int c, *a = arithmetic_prepare(v,s,&c);
    while(c--) { OBJ[v].iv *= *a++; }
    if(DEBUG) printf("multiply: result %c = %d\n",v,OBJ[v].iv);
    return 0;
}
BUILTIN(divide) {
    int n=0, c, *a = arithmetic_prepare(v,s,&c);
    while(*a) { n += *a; a++; }
    OBJ[v].iv = n;
    //printf("plus: result %c = %d\n",v,OBJ[v].iv);
    return 0;
}

BUILTIN(goto) {
    int l;
    char *p;
    if(v=='X') {
        exit(atoi(s));
    }
    for(l=0;l<1024;l++) {
        p = BUF[l];
        if(!p)
            break;
        if(*p++!='@')
            continue;
        if(v!=*p)
            continue;
        LINE = l;
        return 0;
    }
    printf("error: label not found: @%C\n",v);
    return -1;
}

BUILTIN(print) {
    /* TODO: parse \n etc and do not force newline */
    switch(OBJ[v].type) {
        case TYPE_VAR:
            switch(OBJ[v].subtype) {
                case VAR_INT: printf("%d\n",OBJ[v].iv); break;
                case VAR_STR: printf("%s\n",OBJ[v].sv); break;
            }
            break;
    }
    return 0;
}

BUILTIN(if) {
    static char a[256];
    strcpy(a,s);
    char *p = strrchr(a,'@');
    if(!p) {
        printf("error: expecting @ for ?\n");
        return -1;
    }
    *p++ = 0;
    GOTO = *p;
    switch(OBJ[v].type) {
        case TYPE_VAR:
            switch(OBJ[v].subtype) {
                case VAR_INT:
                    switch(*a) {
                        case '=':
                            return (OBJ[v].iv == *RI(a+1));
                        case '<':
                        case '>':
                            // TODO
                            break;
                    }
                case VAR_STR:
                    return (strcmp(OBJ[v].sv,s)==0);
            }
            break;
    }
    return -1;
}


int main(int argc, char **argv) {
    char *s,*p,op;
    int i,r=0;
    FILE *f = stdin;
    memset(OBJ,0,sizeof(OBJ));
    memset(BUF,0,sizeof(BUF));

    SET_BUILTIN('#',assign_int);
    SET_BUILTIN(':',assign_str);
    SET_BUILTIN('+',add);
    SET_BUILTIN('-',subtract);
    SET_BUILTIN('*',multiply);
    SET_BUILTIN('/',divide);
    SET_BUILTIN('>',print);
    SET_BUILTIN('@',goto);
    SET_BUILTIN('?',if);

    builtin_assign_str('Z',argv[0]);
    for(i=1;i<argc;i++) {
        printf("argv[%d]: %s\n",i,argv[i]);
        if(i==1 && strcmp(argv[1],"-f")==0) {
            f = NULL;
            if(argv[2]) {
                f = fopen(argv[2],"r");
            }
            if(!f) {
                printf("error: failed to open file\n");
                return 1;
            }
            printf("opened file %s\n",argv[2]);
            i++;
            r = 2;
            continue;
        }
        builtin_assign_str('@'+(i-r),argv[i]);
    }

    for(LINE=0;LINE<1024;LINE++) {
        s = malloc(256);
        if(!fgets(s,256,f))
            break;
        if((p = strchr(s,'\n')))
            *p = 0;
        while(isspace(*s))
            s++;
        BUF[LINE] = s;
    }

    for(LINE=0;LINE<1024;LINE++) {
        s = BUF[LINE];
        if(!s)
            break;
        if(DEBUG) printf("===========================\n");
        if(DEBUG) printf("line: %s\n",s);
        switch(*s) {
            case 0:        continue; //blank line
            case '#':    continue; //comment line
            case '@':    continue;  //goto label
            default:    break;
        }
        if(!isalpha(*s)) {
            printf("error: unexpected (%C)\n",*s);
            break;
        }
        op = s[1];
        if(OBJ[op].type!=TYPE_BUILTIN) {
            printf("error: invalid instruction (%C)\n",op);
            break;
        }
        r = OBJ[op].builtin(*s,s+2);
        if(r<0) {
            if(DEBUG) printf("exiting due to error\n");
            return 1;
        }
        if(r>0) {
            if(GOTO) {
                builtin_goto(GOTO,"");
                GOTO = 0;
            }
        }
    }
    return 0;
}

---------------

#!/change/to/your/path/turd -f

# factorial.turd
#

# Create integer n with value of command line argument 1 (A)
n#A

# Create integer a with value of n
a#n

# Label L
@L

# Decrement n
n-=1

# If n = 1 goto @E
n?=1@E

# Derp
a*=n

# Goto @L
L@

# Label @E
@E

# Print a to stdout
a>
------------

#!/path/turd -f
#
# Fibonacci sequence generator. Pass number of terms as
# command line argument

a#0
b#1
a>
b>

@L
n+=1
n?=A@X
c+a,b
c>
a#b
b#c
L@

>>22
Copyright (C)  (name withheld)
I don't think you know how copyright works.

>>22
Expert Orphan Work Creator

>>22
^{MUST... REMAIN... ANONYMOUS}

>>21
Ten Susscoins.

>>23
The author has asserted that the work belongs to someone and not the public domain. It's not very enforceable but the thought counts for something -- if the author can prove that he is the originator then his rights to the work would hold.

Who was the genius that designed Turd? Such mystery will confound historians 400 years from now.

>>28
Turd
This article is about the programming language. For other uses, see Turd (disambiguation).

Turd is a programming language named after the stuff that comes out of anii. It is famous for being both the only major programming language for which the original designer is completely unknown^[1]. Read more...

>>29
s/both//

http://en.wikipedia.org/w/index.php?title=Turd_(programming_language)

Son of a bitch!

Feces
From Wikipedia, the free encyclopedia
  (Redirected from Turd)

I should try finishing http://dis.4chan.org/read/prog/1249714306/62.

>>33
That's a better place

>>34
PLACE MY ANUS

I've devised an esolang specifically designed to annoy people who can't figure out how to input Unicode. It's my first esolang, so nothing terribly adventurous. I've named it Codan.

It's pretty straightforward: there's an unspecified number of memory cells, each containing a (signed) integer (initialised to 0). Furthermore, there are three registers: Α, Β, and Λ. (Note that Α and Β are uppercase alpha and beta, not the Latin A and B.)
Α and Β just refer to memory cells (the contents of which can be easily accessed through special variables α and β, respectively), but Λ is a special I/O register: trying to fetch its contents will prompt the user for input (in the form of a number), trying to store a number in it will output that number to the screen.

Assigning to cells works like this:

Α ← 0
Β ← 1
10 → α
β ← α
β → Λ
(All whitespace is optional.)
This has Α refer to memory[0], Β to memory[1], then sets the value at memory[0] to 10, the value at memory[1] to the value at memory[0], and finally outputs the value at memory[1], being 10. x → y is completely equivalent to y ← x.
You can also just go 10 ← 1 (which assigns 1 directly to memory location 10) or 2 → Λ (which outputs 2 directly), if you like.

Next there are expressions, which are of the form function → target (or the other way around, of course). The functions are +, −, ×, ÷, and ↑, for addition, subtraction, multiplication, division, and exponentiation, respectively.
The functions operate on the values pointed to by Α and Β.

Α ← 0
Β ← 1
2 → 0
3 → 1
× → Λ
This would output 6.

Finally, there's the loop, which uses « to open and » to close.
By itself it just runs forever, so you can put assertions inside, which are of the form left-operand comparison-operator right-operand.
The operands can be anything you'd expect. The operator is one of =, ≠, <, ≤, >, ≥, ≮, ≯, ≰, or ≱, which should be self-explanatory. When the assertion is false, the innermost loop execution is currently in will be escaped from.

Α ← 0
Β ← Α
α ← 1
«
α < 10
+ → α
»
α → Λ
This will output 16.

Here's the factorial calculator:

1 ← Λ
1 → 2
1 → 3
Α ← 1
Β ← 2
«
α ≰ 0
× → 2
Β ← 3
− → α
Β ← 2
»
β → Λ

And the Fibonacci sequence generator (as far as signed ints will go):

Α ← 1
Β ← 2
α ← 0
β ← 1
«
α ≮ 0
α → Λ
+ → 3
α ← β
Α ← 3
β ← α
Α ← 1
»

And finally, the prime number sieve (up to 1000, but in principle it's only limited by the size of the memory):

Α ← 2
Β ← 2
«
    Α ≤ 1000
    «
        α = 0
        Α → Λ
        α ← Α
        Β ← Α
        «
            0 ← Β
            0 → Β
            + → Β
            Β ≤ 1000
            1 → β
        »
        0 = 1
    »
    α ← Α
    0 → Β
    1 → 0
    + → Α
»

The ``compiler'' I wrote for Codan is a Python script that outputs C and then calls gcc. Because this post is long enough as it is, I've put it on Sprunge:

http://sprunge.us/eOhB?py

>>36
GOOD.

>>36
excuse me sir but your operators appear to be backwards

>>38
They aren't.

I would like to create a programming language that is based only on formulas in mathematical notation.