21
\$\begingroup\$

There are many challenges that say "interpret X", where X is a simple language. In my opinion, that is way too boring. To give all the procrastinating people on the internet something interesting to do, you can try to do this challenge:

Challenge

Choose a language $LANG. $LANG can be any turing complete programming language or a turing complete subset of a programming language. Beware that if you omit a feature of your language in $LANG for interpretation, you must not use it for your own program, too, since your submission must be written in $LANG, too.

Write a compiler / interpreter for $LANG written in $LANG. You may use all facilities (including eval and friends) of your language that are available to write this compiler. To make the task more challenging, there is one restriction: You program should be able to interpret / compile all valid programs of $LANG except your interpreter / compiler itself. If it occurs that the program to be interpreted / compiled is your interpreter or compiler itself (regardless of the filename), your program should do something completely unrelated to the functionality of an interpreter or compiler (such as barfing or printing Hello, world!).

To make this task even more complex, your program must not read its own source when compiling or interpreting.

Specifications

  • This task is code golf. The submission with the least characters that is correct wins. In case of a tie, the solution that was submitted first wins.
  • Your program / script should read the program to be interpreted from a file. You may hardcode its path and name. When the file is read, you may either compile the file to another file (That must be executable on your system) or run it directly. If $LANG lacks file-reading capabilities, you can choose another way to read in the code that fits $LANG. You may not choose $LANG as a subset of another language but with file-reading capabilites removed.
  • Usual code-golf rules apply. That is: your personal pet-language that you made up just to solve this challenge is forbidden, if the solution becomes trivial using it (Such as defining a single-char program that exactly implements the solution). Abuse of rules is encouraged.
\$\endgroup\$
  • \$\begingroup\$ Are we allowed to define a language for this, so long as it's turing complete? \$\endgroup\$ – Cruncher Dec 19 '13 at 14:20
  • \$\begingroup\$ @Cruncher Yes, you are. See the last bullet point of the specifications for more details. \$\endgroup\$ – FUZxxl Dec 19 '13 at 23:10

11 Answers 11

8
\$\begingroup\$

Ruby, 63

b=$<.read
t="b=$<.read\nt=%p\nb!=t%%t&&eval(b)"
b!=t%t&&eval(b)
\$\endgroup\$
  • \$\begingroup\$ Answer accepted as long as there is no smaller solution. \$\endgroup\$ – FUZxxl Dec 7 '11 at 19:53
11
\$\begingroup\$

Perl, 89 chars, no cheating

$_=q($_=q(Q);s/Q/$_/;($q=join"",<>)eq$_?die:eval$q);s/Q/$_/;($q=join"",<>)eq$_?die:eval$q

Note that this code is extremely picky about what counts as "itself". In particular, it will not recognize itself if there are any trailing newlines or other extra whitespace in the input. To test it, save it into a file named (for example) unquine.pl and do this:

$ perl unquine.pl unquine.pl
Died at unquine.pl line 1, <> line 1.

Remember, the unquine.pl file should be exactly 89 bytes long, no more, no less. Running it with some other Perl script as input just executes the other script, as it should:

$ perl unquine.pl hello.pl
Hello, world!

As the name might suggest, the implementation is based on a quine — specifically, this one:

$_=q($_=q(Q);s/Q/$_/);s/Q/$_/

This code sets $_ equal to itself; the rest of the program (which, of course, must be duplicated inside $_) just compares $_ to the input, dies if they match and evaluates the input otherwise.

\$\endgroup\$
  • \$\begingroup\$ You can replace that &&/; pair with a ternary (one char off, doubled by quining). Great idea and implementation! \$\endgroup\$ – J B Dec 5 '11 at 10:35
  • \$\begingroup\$ @JB: Good catch! Down to 89 chars now. \$\endgroup\$ – Ilmari Karonen Dec 5 '11 at 13:39
5
\$\begingroup\$

GolfScript, 30 chars

{`".~"+"#{$<.read}".@=!{~}*}.~

This program reads the contents of a file named on the command line and, if it does not exactly equal the code above, interprets it as GolfScript. If the input is exactly equal to the code above, it will simply be printed unchanged (except for a newline appended to the end).

This is a fairly straightforward adaptation of this self-identifying program. Specifically:

  • { } is a code block literal in GolfScript.
  • .~, applied to a code block, duplicates the block and executes the copy.

Inside the code block:

  • ` stringifies the copy of the code block.
  • ".~"+ appends the characters .~ to it, yielding a string containing the source code of the program.
  • "#{$<.read}" is a documented hack that allow the execution of Ruby code within GolfScript. In this case, it executes the Ruby statement $<.read (shamelessly stolen from Lowjacker's Ruby solution), which reads and returns the contents of any files specified on the command line. This hack is needed because GolfScript itself provides no explicit file I/O capabilities.
  • .@ duplicates and shuffles the elements on top of the stack so that the stack contains two copies of the file contents followed by the source code of this program.
  • =! compares the top two items on the stack (i.e. the file contents and the source), returning 1 if they are different and 0 if they are the same.
  • {~}* evaluates the remaining copy of the file contents as GolfScript code, but only if the result of the comparison is 1. (Technically, it executes the code block {~} as many times as given by the number on the stack, i.e. 0 or 1 times. Inside the block, ~ is the GolfScript eval operator.)

Ps. If reading the code to execute from stdin is allowed, this challenge can be solved in 21 characters without having to shell out to Ruby:

{`".~"+1$=!{""\~}*}.~

This program will read an input string from stdin and, if it does not match its own source, executes it (with an empty input). Like the program above, input that does match the source is simply echoed back.

\$\endgroup\$
  • \$\begingroup\$ Looks nice, but it doesn't seem like you read input from a file. \$\endgroup\$ – FUZxxl Sep 5 '14 at 7:45
  • \$\begingroup\$ Fixed, now it reads from a file (exactly) like Lowjacker's solution. \$\endgroup\$ – Ilmari Karonen Sep 5 '14 at 14:40
5
\$\begingroup\$

Python, 167 130 118 bytes

This is my first attempt at golfing, so here goes! It interprets any program except itself

Improved version:

i=open(raw_input()).read();q='i=open(raw_input()).read();q=%s;i==q%%repr(q)and a;exec(i)\n';i==q%repr(q)and a;exec(i)

If it gets itself then it barfs with:

Traceback (most recent call last):
  File "pygolf.py", line 1, in <module>
    i=open(raw_input()).read();q='i=open(raw_input()).read();q=%s;i==q%%repr(q)and a;exec(i)\n';i==q%repr(q)and a;exec(i)
NameError: name 'a' is not defined

I think this solution works pretty much the same way as Ilmari Karonen's, the basic idea is something like:

input = read_some_file()
if input == some_quine()
    barf()
interpret(input)

The quine I used was based on this one:

(lambda x: x + repr((x,)))('(lambda x: x + repr((x,)))',)

But I since realized a much shorter quine is:

q='q=%s;q%%repr(q)';q%repr(q)

And that can be even shorter if you allow the interactive python shell, in which case you can do:

'%s;_%%repr(_)';_%repr(_)

Since python doesn't have a short way to get command line args, I went with raw_input() (which is still pretty long, but not as long as

import sys;sys.argv[1]

Usage is:

echo "foobar.py" | python quinterpretter.py

or

python quinterpretter.py
<type filename and hit enter>

I found a shorter quine to use, but here is my old version (for posterity):

i=open(raw_input()).read();a if i==(lambda x,y:x+repr((x,y))+y)('i=open(raw_input()).read();a if i==(lambda x,y:x+repr((x,y))+y)', ' else 1;exec(i)\n') else 1;exec(i)
\$\endgroup\$
  • \$\begingroup\$ Replace the %s with %r and remove the repr. %r means raw and it's basically he same thing. \$\endgroup\$ – Loovjo Jun 6 '15 at 9:05
4
\$\begingroup\$

I can't exactly read from a file using Javascript (ok, I could, using the HTML5 FileReader thing, but that makes things a lot more complicated than I need). So, this is a function that accepts a Javascript program as a string and runs it.

This probably isn't as golfed as it could be, but here it is anyway:

Javascript, 252

function c(p){q='\"';s='\\';a="function c(p){q='\"';s='\\';a=%;a=a.slice(0,17)+s+a.slice(17,24)+a[23]+a.slice(24);a=q+a.replace('%',q+a+q)+q;alert(a);}";a=a.slice(0,17)+s+a.slice(17,24)+a[23]+a.slice(24);a=a.replace('%',q+a+q);alert(a);if(p!=a)eval(p)}

Let me know if anybody knows a better technique for forming a quine in Javascript.

\$\endgroup\$
  • 1
    \$\begingroup\$ I posted a 135-char JS solution below, based on your code and my Perl solution. +1 for the inspiration! \$\endgroup\$ – Ilmari Karonen Dec 5 '11 at 14:51
2
\$\begingroup\$
read p<p;read c<c;[ "$p" = "$c" ]||. ./c

45 characters of sh (POSIX shell). The code to be run must be in the file ./c.

The code for the interpreter itself must be in the file ./p, so I guess I kind of cheated, although the challenge doesn't seem to forbid it. Or would this disqualify my "language" from being a "turing-complete programming language"?

Using a tool that's normally an external executable, but might theoretically be built into the shell, the code can be shortened:

cmp -s p c||. ./c

That's 18 characters, and the -s bit is just to suppress a line that would otherwise always be printed for valid (non-self) programs.

And then you can always build a version of the shell language that does the above with more concise syntax.

And then you can always build a program that, when the input consists of a single '.' --or hell, the empty string-- evaluates the contents of another file as normal code, and call this a programming language. So the empty string would be your solution to the challenge, in the language you built. In fact, here's an interpreter for such a language:

read code; if [ "$code" ]; then eval "$code"; else . ./othercode; fi

Using the language the above script interprets, the solution is the empty string. And the code location needn't be hardcoded anymore.

Problem?

\$\endgroup\$
  • 2
    \$\begingroup\$ The challenge does say that "your program must not read it's own source". \$\endgroup\$ – Ilmari Karonen Dec 4 '11 at 22:13
  • \$\begingroup\$ Darnit, wasted some time then. And I see it even says you mustn't use features that you will omit. This would go against the empty string feature. Then again, the interpreter must be omitting/changing functionality if the code for the compiler/interpreter itself causes different behaviour in the new language. In any case, i had fun writing fallacy. \$\endgroup\$ – TaylanUB Dec 4 '11 at 22:25
  • \$\begingroup\$ @TaylanUB Well, you actually have to interpret all valid $lang programs except the interpreter itself. \$\endgroup\$ – FUZxxl Dec 4 '11 at 22:29
  • \$\begingroup\$ @FUZxxl Yes, the "sh + empty string" language is otherwise equivalent to sh (if the code is not the empty string), and the empty string program written in it also interprets sh code (which must be put in ./othercode), and does nothing when the code is the empty string. I shouldn't have called the file ./othercode, it's misleading; it's just the code that the interpreter written in the empty string language will interpret. \$\endgroup\$ – TaylanUB Dec 4 '11 at 22:34
2
\$\begingroup\$

JavaScript, 135 chars

function c(p){q='function c(p){q=%27Q%27;p!=unescape(q).replace(/Q/,q)?eval(p):alert()}';p!=unescape(q).replace(/Q/,q)?eval(p):alert()}

Peter Olson's JavaScript solution inspired me to try porting my Perl solution to JS. Like his solution, this code defines a function c that accepts a string, and evals it if it's not equal to the code above.

It took me a while to figure out a good way to deal with the absence of balanced string delimiters in JavaScript, until I found what in hindsight is the obvious solution: unescape().

Conveniently, my code doesn't contain any backslashes or double quotes, so it can be safely stored in a double quoted strings. This makes it easy to test:

e = "function c(p){q='function c(p){q=%27Q%27;p!=unescape(q).replace(/Q/,q)?eval(p):alert()}';p!=unescape(q).replace(/Q/,q)?eval(p):alert()}"
h = "alert('Hello, world!')"

eval(e)  // defines the function c()

c(h)     // evaluates h
c(e)     // does not evaluate e, alerts "undefined" instead
\$\endgroup\$
  • \$\begingroup\$ You could replace alert() with 0 to make it not do anything instead of alerting undefined and save 13 chars. \$\endgroup\$ – Peter Olson Dec 5 '11 at 14:56
  • \$\begingroup\$ @PeterOlson: Yeah, but the task does say that "your program should do something completely unrelated" if it detects itself. I interpret that as meaning that it should do something -- preferably something visible to the user, I'd presume. Besides, I just like it better this way. :) (Ps. Yay, it's snowing outside! Winter's finally here!) \$\endgroup\$ – Ilmari Karonen Dec 5 '11 at 15:03
  • 1
    \$\begingroup\$ @Ilmari Doing nothing is unrelated to interpreting Javascript IMHO. \$\endgroup\$ – FUZxxl Dec 5 '11 at 21:43
  • \$\begingroup\$ You could go p=>... instead of function c(p) \$\endgroup\$ – FireCubez Oct 7 '18 at 20:22
2
\$\begingroup\$

Common Lisp, 59

#+~ #.(#:a)(defun L(p)(compile-file p))(push :~ *features*)
  • In a fresh Lisp REPL, compile your file (e.g. sbcl --load)
  • You now have a function L, which can compile Common Lisp files
  • However, if you call (L <your file>), an error is signaled while reading the file.

Why?

Because the first time, you pushed the :~ keyword into *features*. Now, your environment knows about the ~ feature, and the reader macro #+, upon evaluating the ~ feature expression, will succeed and read the following form instead of skipping it as it did the first time. In your file, the following form is #.(#:a), which asks to evaluate (#:a) at read-time and use the resulting value as the code being read. But (#:a) calls the function associated with the uninterned symbol #:a. Since #:a is uninterned, it is a fresh symbol which is not bound to any function (i.e. not fboundp). Error.

\$\endgroup\$
1
\$\begingroup\$

Scheme, 48 or 51 characters

Scheme is a language with many different implementations. Despite implementations having to conform to the latest RnRS, the latest working standard (R6RS) has been unpopular due to its lack of minimalism. R7RS is soon to be released as a remedy, while splitting the language in 2. The first language being powerful and minimalistic and the second, a superset of the first intended to provide feature extensions for interoperability between implementations. Until then, we rely on SRFIs (Scheme Requests For Implementation), which provide (if implemented in the host implementation or manually (as is common in scheme)) a means to portably accomplish common tasks. All this to say that the first code snippet (51 characters), while remaining as portable as it can, relies on SRFI-22 (executing scheme scripts in UNIX) for access to command-line arguments:

(define(main x y)(case y(x => error)(else => load)))

or more readably:

(define (main current-file arg)
  (case arg
    [current-file => error]
    [else => load]))

The second (48 characters) is an file-less means to interpretation which cannot evaluate itself (in a null environment):

(define(e)(write(eval(read)null-environment))(e))

or more readably:

(define (interpret)
  (write (eval (read) null-environment))
  (interpret))
\$\endgroup\$
  • \$\begingroup\$ Your code does not work if you copy your interpreter. \$\endgroup\$ – FUZxxl Dec 12 '11 at 5:49
  • 1
    \$\begingroup\$ Leave it to a scheme answer to contain nested parentheticals in its prose. \$\endgroup\$ – Cyoce Apr 5 '16 at 7:21
1
\$\begingroup\$

Groovy, 13 bytes

{Eval.me(it)}

This should interpret a subset of Groovy.

test cases:

p={Eval.me(it)}

p'''
    (0..37).each{println"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"[it..it+2]}
'''

p'''
    {Eval.me(it)}
'''

Unfortunately while it certainly barfs, it does so in a completely interpreter-like way, and it does it for quite a lot of input.

\$\endgroup\$
  • \$\begingroup\$ In which line do you read the program to be interpreted? Your code is interesting although it is not a valid submission for this task. \$\endgroup\$ – FUZxxl Dec 5 '11 at 18:23
  • \$\begingroup\$ I assume the error is something like "recursion limit exceeded"? \$\endgroup\$ – Ilmari Karonen Dec 6 '11 at 0:50
1
\$\begingroup\$

Javascript ES6, 45 bytes

$=(_=prompt())=>eval(_==`$=${$};$()`?0:_);$()

Still competitive! (thx @Downgoat)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.