19
\$\begingroup\$

The Challenge

In this challenge, you specify a source language S and a target language T. Your task is to write the following program P in the language S. If a valid program Q in the language T is given as input to P, it will output a valid program R in the language T which takes no input and outputs Q(R), that is, the program Q applied to the source code of R. In addition, you should present in your answer a nontrivial example program Q (the more interesting, the better, although you score no points for this), the resulting program R, and the output of R. This is code-golf, so the shortest code for P wins.

In other words, this is a challenge about writing a "universal quine constructor" that can create arbitrary types of generalized quines.

Clarifications

  • Your source and target languages may be identical.
  • The program P should take one string as input (from STDIN or equivalent), and output one string (to STDOUT or equivalent), as should every output program R.
  • The input programs Q should also transform a string to another string, but their form is more flexible: they can be string-to-string functions, code snippets that modify a variable with a certain name, snippets that modify the data stack if your target language has one, etc. You can also further restrict the form of the Q's by stating that, for example, they may not contain any comments. However, you must be able to implement any computable string-to-string function as an input program Q, and you must explicitly state how they function and what further constraints you place on them.
  • The output program R should really be a (generalized) quine, so it must not read any input (user input, files etc.) unless Q does so.
  • Standard loopholes are disallowed.

An Example

Suppose I choose Python as my source language, and Haskell as my target language, and I further require that the input program should be a one-line definition of a String -> String function named f. If I give the string-reversing program

f x = reverse x

as input to my Python program P, it will output the source code of another Haskell program R. This program prints to STDOUT the source code of R, but reversed. If P is given the identity function

f x = x

as input, the output program R is a quine.

\$\endgroup\$
7
\$\begingroup\$

Source = Target = CJam, 19 17 16 bytes

{`"_~"+}`)q\"_~"

This assumes that the input program Q (given on STDIN) is some CJam snippet which expects a string on the top of the stack and leaves another string on top of the stack.

Test it here.

Examples

  1. The identity would just be an empty snippet, so leaving STDIN empty prints

    {`"_~"+}_~
    

    Which is the standard quine, with an additional +.

  2. To reverse a string in CJam, you can use W%, so putting that on STDIN, this yields:

    {`"_~"+W%}_~
    

    which we can run to obtain

    ~_}%W+"~_"`{
    
  3. As a third example, say we use a snippet which intersperses a string with spaces: ' *. Running P with that as input, we get

    {`"_~"+' *}_~
    

    which in turn prints

    { ` " _ ~ " + '   * } _ ~  
    
  4. It now also works if Q contains line breaks (although that's never necessary in CJam). Here is a program with a line break, which removes all line breaks from a string (in an unnecessarily convoluted way - split into lines, then join):

    N/
    ""
    *
    

    This results in the following R:

    {`"_~"+N/
    ""
    *}_~
    

    which in turn prints

    {`"_~"+N/""*}_~
    

Explanation

Let's look at the produced output first:

The standard CJam quine is

{`"_~"}_~

It works as follows:

  • Push the block {`"_~"}.
  • Duplicate it with _.
  • Execute the copy with ~.
  • Now inside the block, ` turns the first block into its string representation.
  • "_~" pushes the two characters of the source that are not part of the block (and hence missing from the string representation).
  • The two strings are printed back to back at the end of the program.

In the basic quine the ` is unnecessary, because if you just leave the block as it is, it's printed all the same at the end of the program.

The output of my program P is a modified version of this snippet. First, I've added a + to the block, which concatenates the two strings into one string containing the entire source. Note that this will be true no matter what I do inside the block, because that will all get added to the string representation obtained with `. Now I can simply put the program/snippet Q inside the block after the +, so that it can modify the source string before it is printed. Again, since Q goes inside the block, it will be part of said source string.

In summary, P prints

{`"_~"+Q}_~

Now, for how I go about constructing this output in P:

{`"_~"+}         "Push the block without Q.";
        `        "Turn it into a string. This is shorter than writing a string right away,
                  because I'd have to escape the quotes, and I'd need two quotes instead of
                  one backtick.";
         )       "Pop off the last character (the brace) and push it on the stack.";
          q      "Read input Q.";
           \     "Swap Q with the brace.";
            "_~" "Push the final two characters.";

The four strings are printed automatically (back-to-back) at the end of the program.

\$\endgroup\$
  • 1
    \$\begingroup\$ Well, this was fast! And certainly hard to beat. The explanation is nice too. \$\endgroup\$ – Zgarb Nov 11 '14 at 6:59
  • \$\begingroup\$ Where did you learn that W% reverses? dl.dropboxusercontent.com/u/15495351/cjam.pdf doesn't have it \$\endgroup\$ – Faraz Masroor Apr 7 '16 at 15:42
  • \$\begingroup\$ Is there a more complete list of methods? \$\endgroup\$ – Faraz Masroor Apr 7 '16 at 15:42
  • \$\begingroup\$ @FarazMasroor sourceforge.net/p/cjam/wiki/Basic%20operators/#percent (no. 3) ... it's a feature borrowed from GolfScript and at some point someone told me that's how it works in GolfScript. It appears to be such a common idiom that it's some weird implicit knowledge every CJam/GS user has but which isn't actually explained in a lot places. (For more, not thoroughly documented operators, see sourceforge.net/p/cjam/wiki/Operators) \$\endgroup\$ – Martin Ender Apr 7 '16 at 15:47
3
+50
\$\begingroup\$

Haskell expressions → Haskell expressions, 41 bytes

((++)<*>show).('(':).(++")$(++)<*>show$")

Try it online!

How it works

P $ "Q" = ((++)<*>show).('(':).(++")$(++)<*>show$") $ "Q" constructs "R" by

  1. (++")$(++)<*>show$"): appending the string ")$(++)<*>show$",
  2. ('(':): prepending the character '(', and
  3. (++)<*>show (= \x->x++show x): appending a quoted version of that,

resulting in "R" = "(Q)$(++)<*>show$\"(Q)$(++)<*>show$\"".

R = (Q)$(++)<*>show$"(Q)$(++)<*>show$" works by

  1. taking the string "(Q)$(++)<*>show$",
  2. (++)<*>show: appending a quoted version of that,
  3. applying Q to that,

resulting in Q "(Q)$(++)<*>show$\"(Q)$(++)<*>show$\"" = Q "R".

(The parens around Q are necessary because Q might contain $ just as easily as R does, and $ is unfortunately right-associative.)

Demo

λ> putStrLn $ ((++)<*>show).('(':).(++")$(++)<*>show$") $ "id"
(id)$(++)<*>show$"(id)$(++)<*>show$"
λ> putStrLn $ (id)$(++)<*>show$"(id)$(++)<*>show$"
(id)$(++)<*>show$"(id)$(++)<*>show$"
λ> putStrLn $ ((++)<*>show).('(':).(++")$(++)<*>show$") $ "reverse"
(reverse)$(++)<*>show$"(reverse)$(++)<*>show$"
λ> putStrLn $ (reverse)$(++)<*>show$"(reverse)$(++)<*>show$"
"$wohs>*<)++($)esrever("$wohs>*<)++($)esrever(
λ> putStrLn $ ((++)<*>show).('(':).(++")$(++)<*>show$") $ "length"
(length)$(++)<*>show$"(length)$(++)<*>show$"
λ> print $ (length)$(++)<*>show$"(length)$(++)<*>show$"
44
\$\endgroup\$
  • \$\begingroup\$ Not just $ needs the parentheses, but also trailing let, do or lambda expressions. \$\endgroup\$ – Ørjan Johansen Jun 22 '17 at 18:53
  • \$\begingroup\$ @ØrjanJohansen Right, but I could have defined a language subset that disallows unparenthesized lambda/let/if/case/do if I don’t emit them myself. Perhaps it’s just as well that I didn’t have to. \$\endgroup\$ – Anders Kaseorg Jun 22 '17 at 20:59
2
\$\begingroup\$

Source = Target = JavaScript, 66

console.log("function a(){console.log("+prompt()+"(a+'a()'))}a()")

Assumptions for Q:

  • Q should be a string-to-string JavaScript anonymous function.

Examples:

  • Reverse. Q = function(s) { return s.split('').reverse().join(''); }

In this case, P(Q) (or R) will be: function a(){console.log(function(s) { return s.split('').reverse().join(''); }(a+'a()'))}a(), and by executing it, we will get: )(a}))')(a'+a(} ;)''(nioj.)(esrever.)''(tilps.s nruter { )s(noitcnuf(gol.elosnoc{)(a noitcnuf which is exactly the same as Q(R).

  • Identity. Q = function(s) { return s; }

in this case, P(Q) (or R) will be: function a(){console.log(function(s) { return s; }(a+'a()'))}a() which is a JavaScript Quine. Needless to say, Q(R) will be the same, since Q is the Identity function.


Some notes:

STDIN in JavaScript is traditionally prompt(), however, I allowed myself to refrain from the tradition of alert() as STDOUT, in order to make the process of run output as a progrem using copy-paste easier. (I do realize I can save up to 12 characters when changing to alert()).

I can also make things much shorter in ES6, but I want to stay with Native JavaScript for now. I'm considering submitting a S=Scala,T=ECMA6 answer in future, just for the experience.

I also realize JavaScript can almost never beat CJam in , but I had to take this challenge! It was surly a fun one.

\$\endgroup\$
  • \$\begingroup\$ Thanks! It would indeed be cool to have an entry with different source and target languages. \$\endgroup\$ – Zgarb Nov 18 '14 at 17:59
2
\$\begingroup\$

Jelly7, 9 bytes

“ṚƓ^ṾṂ’³3

Try it online!

Q is a 7 function (i.e. that doesn't look beyond the top stack element, and does I/O via the stack), and is given as a command-line argument.

Explanation

The 7 program

The universal quine constructor in 7 that I use here is:

717162234430…3

The first thing to note is that the leading 7 is the equivalent of leading whitespace, and doesn't have any effect on the program. The only reason it's there is to obey PPCG's rules against literal-only quines (it's encoded by the second 1 in the program rather than itself).

The rest of the program is a single stack element (it has balanced 7s and 6s), which does the following when run:

717162234430…3
 1716           Push a stack element "7" onto the stack
     2          Copy it
      23        Pop and output one of the copies (selecting format 7)
        4430    Prepend it to the top of stack
             3  Output it

In other words, this stack element is a program that prints the top of the stack, with 7 prepended, in output format 7 (which means "print literally, using the same encoding as the source code", and thus is clearly the best encoding for quines). It's fairly fortunate here that we can reuse the literal 7 for two purposes (the output format, and the leading whitespace.) Clearly, by inserting something just before the final 3, we can output a function of 7 + the input, rather than just outputting 7 and the input directly.

How does this stack element get at its own source code? Well, when the end of the program is reached, 7 evals the top stack element by default. However, it's not actually popped from the stack in the process, so the stack element literal that was evalled is still there. (In other words, the program isn't reading its own source – as evidenced by the fact that it's unable to see the 7 at the start of the program, which is a stack element separator rather than part of a literal – but rather, it consists mostly of a literal that gets evalled by default.)

The Jelly program

This is perhaps one of the least Jelly-like Jelly programs I've written; it consists of three nilads (“ṚƓ^ṾṂ’, ³, 3), which are just output in sequence because no operations are performed on them. The 3 is obvious enough, just being an integer constant. The ³ is also simple if you know Jelly: it's Jelly's explicit notation for the first command-line argument (which is where Jelly typically takes its input). The rest of the Jelly program represents the bulk of my 7 universal quine constructor: by exploiting the fact that all the commands in 7 can be represented using ASCII digits, we can interpret 717162234430 not as a series of commands, or even as an octal number (like it conceptually is), but as a decimal number, meaning that we don't need any special formatting for the output. That decimal number becomes “ṚƓ^ṾṂ’ in Jelly's compressed integer notation.

Example

If we give 24053 as program Q, we'll get the following output:

717162234430240533

Try it online!

2405 concatenates the top stack element to itself:

2405   Stack   Explanation
       x
2      x|x     Duplicate top of stack
 4     x||x    Swap two stack elements, with an empty element between
  0    x|(X)   Escape the top stack element, then concatenate the top two
   5   xx      Execute the top stack element

(The last step might look a little confusing; what's happening is that escaping a stack element converts each command in it from "run this command" to "append this command to the top of the stack", so each command appends itself to the original top stack element as it runs.)

As such, running the resulting program R gives us two copies of R:

7171622344302405371716223443024053
\$\endgroup\$
2
\$\begingroup\$

CJam → CJam, 13 bytes

{`"_~"+7}_~qt

Try it online!

The input Q should be a code snippet that modifies the only string in the stack. Q is read from stdin.

Example

Input:

S*W%

It adds a space between every two characters, and reverses the string.

Output:

{`"_~"+S*W%}_~

Output of the generalized quine:

~ _ } % W * S + " ~ _ " ` {

Explanation

{`"_~"+7}_~      e# Evaluate a generalized quine in CJam that only appends a 7.
q                e# Read the input.
t                e# Replace the 7th character (0-based) with the input.

It firstly evaluates the quine, so we can get its string representation without unnecessary double quotes. Then replace the payload with the input.

It could be {`"_~"+ }_~7qt where the space is the placeholder of the payload. But changing the payload to 7 saves a byte.

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

CharcoalPerl (5), 29 33 bytes

A$_=q(αA);evalβαS"\α$_β\n";printβ

Try it online!

The Perl program Q should return a snippet that takes input as a string to its right hand side and provides output in the variable $_. (Arbitrary Perl functions can be converted to this form via wrapping them as sub x {…}; $_=x. In most cases, though, Perl's syntax means that no wrapping is required.)

Explanation

The Perl

Here's what the universal Perl quine constructor looks like:

$_=q(…"\$_=q($_);eval";print);eval

(In most cases you'd want to golf this down to $_=q(say…"\$_=q($_);eval");eval, but I'm not sure you can fit arbitrary Perl code into the there.)

In other words, we have an outside wrapper $_=q(…);eval which assigns a string to $_ and then evaluates it. Inside the wrapper is "\$_=q($_);eval", i.e. a reconstruction of the wrapper together with its contents via using the value we stored in $_, plus the code Q specified by the user, plus print to print the output. (Unfortunately we can't use say; it adds a newline, and that's relevant in quines.)

The Charcoal

The "point" of this answer was to produce generalized quines in Perl, so once I had a golfed strategy for doing that (one I've used in many other answers), it was time to write the program P, which basically just substitutes a string into a template. What I wanted here was a language which was good at printing constant strings (ideally compressing them a bit), and interpolating user input into them.

After trying a few, I settled on Charcoal, which I've never used before (and which could really do with some documentation); it's designed for ASCII art but capable of writing strings in one dimension too. ASCII characters are printed literally in Charcoal, meaning that printing constant strings takes no boilerplate, and we can use the command to interpolate a string taken from user input into the program.

It's possible to go (slightly) shorter, though. The Perl universal quine constructor contains two fairly long repeated sections. We can thus use the command to assign them to variables (e.g. A…α assigns to the variable α), and simply interpolate the variables into the string we're printing via using their names. That saves a few bytes over just writing the string literally.

Unfortunately, Charcoal also appends a newline to the program, but that's not a huge deal; it simply costs two bytes for an \n to add that newline to the input of Q too.

Example

If we give the input $_=reverse (which reverses a string), we get the following output:

$_=q($_=reverse"\$_=q($_);eval\n";print);eval

Try it online!

which is a quine-alike that prints its source backwards, as expected.

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

JellyUnderload, 15 bytes

“(a(:^)*“S):^”j

Try it online!

Takes the input Underload function Q as a command-like argument. Q must take input from the stack and push output to the stack, without attempting to inspect deeper stack elements (as they won't exist).

Explanation

The Underload

The Underload universal quine constructor used here is:

(a(:^)*…S):^

Most of the program is a single literal. We follow that by :^, which copies it, then evaluates one copy (leaving the other copy on the stack).

When the literal starts evaluating, we run a (escape, which brings it back into the same form as the original programA), and (:^)* (which appends :^), thus reconstructing the entire program's source code. We can then run the function Q to transform this in an arbitrary way, and print the result with S.

The Jelly

I can't use Charcoal this time because a validating Underload interpreter crashes at the end of the program if the program ends with a newline. (Some Underload interpreters, such as the one on TIO, don't enforce this rule, but I wanted to be properly portable.) Unfortunately, Charcoal naturally adds trailing newlines to its output. Instead, I used Jelly, which is almost as terse in simple cases like this; the program consists of a list literal with two elements (““”), and joins them on the input (j), thus interpolating the user input into the program.

Example

Using the input :S^ (print a copy, then evaluate the original), we get the following Underload program:

(a(:^)*:S^S):^

Try it online!

This prints itself infinitely many times, in a fairly interesting way: after doing the normal quine behaviour, it then runs eval on a copy of what it output. That causes the entire reconstructed program to run again, indefinitely (Underload is tail-recursive). Quining yourself and doing an eval is actually the only way to do an infinite loop in Underload.

\$\endgroup\$
  • \$\begingroup\$ Charcoal doesn't add trailing newlines anymore (yay) \$\endgroup\$ – ASCII-only Jul 27 '17 at 5:01
1
\$\begingroup\$

RProgN 2, 11 bytes

'{`{.%s}{'F

Program Explination

'{`{.%s}{'F
'{`{.%s}{'  # Push the string "{`{.%s}{" to the stack.
          F # Format the input with the top of the stack as a template. Which produces {`{.<INPUT>}{

Quine Explination

The quine that's produced is simple, yet uses the functionality of unmatched function handlers in RProgN2 to create a short and sweet quine, called a "Looping" quine. It's a surprisingly similar concept to a <>< quine.

{`{.}{
{`{.}   # Push the function {`{.} to the stack.
     {  # Try to define a new function, fail, loop back to index 1. (Which in turn, skips the function definition.)
 `{     # Push the string "{" to the stack.
   .    # Concatenate the top two values of the stack, which stringifies the function, then appends { to it.
    }   # Try to terminate a function, fail quietly, and terminate the program.

Of course, because of the structure of this quine, anything but true no-ops (Which don't get stringified) can be placed after the concatenate function, and

Some quines

  • {`{.i}{: Outputs {}i.{`{. i is just the "inverse" function, so this program outputs itself reversed.
  • {`{.S§.}{: Outputs ..S`{{{}§. S converts the string to a stack of characters, § sorts the stack lexographically, then . joins it back together, outputting itself sorted.

Try it online!

\$\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.