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 toyprogramminglanguage. 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.
Name:
Anonymous2010-06-12 0:12
This interpreter/compiler can be written in any language? Jesus LISP fags have this easy...
Name:
Anonymous2010-06-12 0:16
>>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.
Name:
Anonymous2010-06-12 1:44
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 Design1 and Engineering A Compiler2, and have only read the beginning of the latter so far (man is it wordy).
>>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.
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.
# 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
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));
>>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.
Name:
Anonymous2010-06-12 12:13
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...
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.
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:
# stack.pl - an interpreter for a very simple stack-based language.
I'm bored to tears already.
Name:
Anonymous2010-06-14 22:00
>>60
it gets better when you get to the ``wild card'' program.
that program hints at the real purpose of the language... to make small programs that could be run simultaneously over a large set of data, on dirt-cheap massively parallel hardware. of course that perl script doesn't do the parallel thing, but it does a pretty good job of showing how it'd be used.
>>61
Can't that be said of any "very simple stack-based language"? I mean, if you chose to use them that way?
Name:
Anonymous2010-06-14 23:16
I'm working on FRNPL Recursively Named Programming Language. You read it left to right with each line going straight down, here's the Fibonacci program for example:
print @ @ @ while ........... exit
"How high should I go? " a b c < @ @ @ print
_getnum 0 1 c d b c c
a + c d
b
c
The interpreter's basically done, I guess I'll just add features during the next few days.
Is Xarn in? If he's not in, I refuse to submit an entry. If he's in, I see no point in submitting my entry.
Name:
Anonymous2010-06-15 19:14
>>69
Have you seen Tubes? The project seems to be in the hands of brain-damaged high school kids, but the code looks conceptually similar, except less ass-key.
Hi, Turd author here. Been busy with actual work coding - A rather exciting windows Credential Provider that sucks you off and anaylzes your semen to authenticate you. Actually I made that bit up. But some exciting new features are being added to turd and I plan to implement some more programs from the list and a wild card
Name:
Anonymous2010-06-16 14:03
>>82
You forgot to note that Codan was designed by Xarn.
>>80
Whilst thinking about it further, I'm changing it slightly, so you can write it in any direction you want(as long as it fits the down right up left(and is surrounded by whitespace).
So you can write it like this:
n
= .
_ n
c }
= 1
0i=1t=0n*{t -
= n
0t+it+ci=cc=t
Or in any darn order really, trying to work in a way. Also adding in so you can reuse operators and variables by crossing over paths. There's only five operators, = + - _ ., or equals, add, subtract, get input, output variable. Only support for integers, no strings or arrays. I have exams next week, I'll try to finish it, but at the moment, all there is is a simple interpreter for the base language.
>>90
Oh, and there's also the control operator *, which works like brainfuck's [ symbol with the preceding variable, on the next set of curly brackets.
Sage because I've already bumped it.
Name:
Anonymous2010-06-17 10:17
Bump. We need more languages. ah fuck, I'm going to create new one.
>>111
Sure you can! I just started today, and I have a nice chunk of code working already. I might be able to get JIT compilation working before the deadline.
Though I'm working backwards, so I don't have the parser written yet.
>>114
Implement a prototype parser/compiler in another language, re-implement the parser/compiler in the language itself, then enjoy the pleasure of being boostrapped inside.
>>115
Or implement a hacky "throw-away" interpreter in one language, then write the actual compiler (and maybe a new interpreter) in the language you were designing. Less time spent.
>>116
Or just write a compiler/interpreter in whatever language, then write the compiler/interpreter for your designed language in your designed language and do it that way. Less time spent.
>>133 Xarn's is atually one of the least interesting languages.
Name:
Anonymous2010-06-21 3:35
>>134
None of the languages are very interesting, really. Codan has the Unicode gimmick, >>131 has the sound gimmick, and that's about it. >>131 probably has the fanciest implementation, and Codan probably has the fanciest wild card program, but neither of those are strictly categories.
>>137
ps: not late if using baker island time as you didn't specifiy tz
Name:
Anonymous2010-06-21 6:36
God damnit i didnt even finsh my “lisp like„ interpreter.
Name:
Anonymous2010-06-21 9:45
WHERE'S MY PRIZEs AT
Name:
Anonymous2010-06-21 10:27
I'd submit my entry if the deadline was extended by a week :<
Name:
12010-06-21 11:52
RESULTS TIME
Presentation and cleverness - Codan, for its detailed introductory explanation. To be honest, none of the languages here struck me as being particularly clever; I have seen esolangs and stack languages resembling pieces of all of them. >>64 could potentially have won in that respect, as I don't recall having seen a language written horizontally like that. Alas, it can't really be awarded anything without an implementation or samples.
Clarity of implementation - tied between Codan and the latest version of Turd. Codan benefits from being much more straightforward, since it simply generates code and leaves the task of actually making it do something to the C compiler. Turd is necessarily a bit more complex, but it contains a full interpreter, handles both numbers and text, and still manages to be fairly easy to understand at a glance.
Wild card program - I suppose calculating π to 1000 decimal places could surely be considered "useful" for some definition of the term, and it was fairly entertaining to see it after spending several minutes looking at the code and not having a clue what it did. Turd's SUSSMAN printer definitely wins in terms of trolling value, though.
Overall, it's a close choice between Codan and Turd. Since Turd is overall a more usable language (having implemented the largest set of implemented programs of all those submitted), owing to its long and open development cycle, and thanks to its text processing capabilities that seem to be absent from Codan, I would be inclined to award the winning prize in favor of it. Unfortunately, its author appears not to have a /prog/mail address, so I suppose I will have to award the ten Susscoins to Codan.
I should note that I am intentionally not including Soda in the voting: first because it was submitted late, but more importantly to avoid a conflict of interest (since I wrote it).
On a side note, I'm somewhat disappointed in the absence of LISP here. Maybe the lengthy development process of Arc and similar such projects are an indication that this is because implementing a language in Lisp is an inherently difficult and time-consuming process which couldn't be accomplished in such a short time frame. Although the prize has been awarded for this challenge already, perhaps we will still see more implementations here in the coming months.
>>142
There's no lisp because making lisp interpreters in lisp is easy if not cheating (no need for writing one's own parser, free AST representation, homoiconicity of the language giving you cheap low-level macros and making eval easy to describe in itself). The tricky part is making something new, which is what the challenge is. Reimplementing someone else's lisp is easy. Inventing some new unique semantics or ideas that nobody else had is something much harder and rarer in the Lisp world, because just about anything was already tried.
Trivial interpreters can be expressed in a single page of code.
Of course, some simple esolangs shouldn't be hard to make in it, but it's more fun to try to create something which you could find useful yourself.
>>142 >>64 could potentially have won in that respect, as I don't recall having seen a language written horizontally like that.
Are you serious? I got bored, figured I wouldn't win anyway, and quit writing it. God damn it.
Anyways, congratulations, Xarn.
Name:
Anonymous2010-06-21 13:45
Xarn wins. Life goes on as always.
Name:
Anonymous2010-06-21 14:02
I considered adding a %d/%c output toggle to Codan (like the # of the Optimising Brainfuck via-C Compiler which inspired it; though the function of # varies wildly from Brainfuck implementation to implementation) so I could implement a bunch of ciphers and CGOL in it, but decided an entirely numerical language would be purer and more annoying to work with.
I'm actually surprised how many working entries we ended up with, even if they weren't terribly adventurous. Way to go, /prog/.
>>174
sorry, turd is untouched since then. the one letter variable system was not right for the perfect language that i will one day write. also i wasn't happy with \n terminated lines as it hindered the writing of ugly terse one-liners. and also it was a massive hack designed at the keyboard.