Two Guys Arguing

Challenge – QuickPiet Interpreter

Posted in challenge by benjaminplee on 03.14.10

Create an interpreter for a new Language based on Piet: QuickPiet

To pair off of Nate’s Rock Paper Scissors challenge, here is one I am offering up to him: create an interpreter which will execute QuickPiet commands.  What is QuickPiet?  QuickPiet is a very basic language based off of the commands found in the esoteric Piet programming language.

Piet_hello_big from http://www.dangermouse.net/esoteric/piet/samples.html

Big Piet Hello World (25 pixels / codel)

Piet programmers are written as images which can be interpreted as actions based on a stack.  Recently I signed up to give a talk at the April Fool’s Day meeting of the Lambda Lounge where several people will be giving short talks on esoteric and useless programming languages.  Programming in Piet poses several challenges including working only with a single stack and building up your logic into pixels and colors.  I should have a few posts on writing programs in Piet in the next week or so. Until then, I have been mainly struggling with how to accomplish real work with just a single stack and a very limited menu of commands to choose from.  QuickPiet is an attempt to make that process easier.

The challenge:

  • Write an interpreter for the QuickPiet language I have posted in a new GitHub Gist;  http://gist.github.com/332040.
    [Edit: The language spec is now in the base QuickPiet repo on GitHub]
  • The interpreter should allow the user to enter in QuickPiet commands from a file or GUI text box
  • The interpreter should allow the user to enter text to be handled by STDIN and should display to the user any characters sent to STDOUT
  • Ideally the interpreter would be written in a cross-platform way (e.g. JVM, Ruby, Javascript/HTML) but anything is valid
  • Extra points for GUIs and/or the ability to see how the stack changes through program execution and/or at the end

The “complete” spec can be found on the Gist page, but a very quick rundown is below:

  • Program execution is top down, except for GOTO commands
  • Each line can be blank (ignored), a label, a comment, or a command
  • Only one command per line
  • There are no explicit looping or other control structures
  • The interpreter maintains a single “infinitely large” stack which different commands can act on
  • Example commands include (IN, OUT, PUSH, POP, ADD, SUBTRACT, GOTO, etc)
  • Commands are case-insensitive, labels are not

If you have any questions or are willing to venture a solution please leave a comment.  I just had this idea this morning so I am very interested in any feedback you may have.  I am planning on working on my own solution and hope to have something put together today or tomorrow.

Click the tag links for QuickPiet and Piet below to see all posts

Tagged with: , ,

5 comments

5 Responses

Subscribe to comments with RSS.

  1. benjaminplee said, on 03.14.10 at 12:24 pm

    I will be posting my version here: http://github.com/benjaminplee/QuickPiet

    Reply
    • youngnh said, on 03.14.10 at 8:29 pm

      I’m posting my code as I go along as a fork of your gist.
      I’m starting in Haskell because the pattern matching makes a lot of the stack operations trivial to implement and Parsec promises to be the easiest way to interpret and execute the actual script.
      http://gist.github.com/332400

      Reply
  2. benjaminplee said, on 03.15.10 at 9:25 pm

    Updated QuickPiet language spec w/ new assert command, updated docs, and some slight changes to pop, push, etc.


    # QuickPiet commands listed below with their effect/explanation to the right after the arrow (–>)
    # These commands follow the actions available with the Piet programming languages with some
    # small changes to allow algorithms to be tested without the need of creating valid Piet images.
    # Original Piet information can be found at http://www.dangermouse.net/esoteric/piet.html
    # Just as in Piet, this language spec assumes a single "infinite" stack and a linear command execution order.
    # Blank lines should be ignored.
    # An implicit "end" command is present at the bottom of the document.
    # Improperly formatted or typed commands should be ignored, allowing for future commands to be added.
    # [UPDATED 3/15/2010]
    push X Y Z … –> Pushes 1 or more space separated positive integer values onto the stack (X first, then Y, then Z and so on).
    –> Positive integer values may represent ASCII character codes or plain integers
    –> Do not include commas (,) in large values
    –> [UPDATED 3/15/2010]
    pop X –> Pops the top X value(s) of the stack and discards. If X is omitted, 1 is assumed.
    –> [UPDATED 3/15/2010]
    duplicate –> Pushes a copy of the top value of the stack onto the stack
    roll –> Pops the top two values, and "rolls" the remaining stack entries to a depth equal to the second value popped
    –> By a number of rolls equal to the first value popped
    –> A single roll to depth n is defined as burying the top value on the stack n deep
    –> And bringing all values above it up by 1 place
    –> A negative number of rolls rolls in the opposite direction
    –> Rolling the stack [1,2,3,4,5] 2 rolls to a depth of 3 results in [1,2,5,3,4]
    –> Another roll of value 2, with depth 3, results in [1,2,4,5,3]
    –> [UPDATED 3/15/2010]
    in –> Read a single value from STDIN and push it onto the stack; characters are read as their ASCII value
    out –> Pop the top value from the stack and output it to STDOUT in it's ASCII character value
    add –> Pops the top two values, adds them, and pushes the result
    subtract –> Pops the top two values, subtracts the top value from the second top value, and pushes the result
    multiply –> Pops the top two values, multiplies them, and pushes the result
    divide –> Pops the top two values, integer divides the second top value by the top value, and pushes the result
    mod –> Pops the top two values, calculates the second top value modulo the top value, and pushes the result
    not –> Replaces the top value of the stack with 0 if it is non-zero, and 1 if it is zero
    greater –> Pops the top two values
    –> Pushes 1 on to the stack if the second top value is greater than the top value, 0 otherwise
    –> [UPDATED 3/15/2010]
    end –> Stop program execution, values left on the stack are discarded
    # LINE COMMENT –> Line comment must begin wit a # and may contains zero or more characters of any type
    :label –> Line label must begin with a ":" character and one or more alpha-numeric characters (no whitespace)
    –> [UPDATED 3/15/2010]
    goto label label –> Pops the top value from the stack
    –> Label names should not include the ":" symbol
    –> If the value modded by 4 is equal to 1, program execution switches to the first label (e.g. 1, 5, etc)
    –> If the value modded by 4 equals 3, program execution switches to the second label (e.g. 3, 7, etc)
    –> If the value modded by 4 equals 0 or 2, execution continues to the next command
    –> Negative values go in the opposite "direction". -1 = 3, -2 = 0, -3 = 1, -4 = 0
    –> If either label is not to be used, replace with a single ":" symbol
    –> [UPDATED 3/15/2010]
    assert X Y Z … –> Pops all values from the stack, checking that each equals the given value in order
    –> Right most value is "top" of stack: Z = top of stack, Y second top, X third top
    –> If any value is not equal to the value on the stack, execution stops and error message is presented to STDOUT
    –> If there are different numbers of stack elements, execution stops and error message is presented to STDOUT
    –> This may be used in testing
    –> This could be created through a series of smaller commands,
    –> But is included as a convenience to test the current state of the stack
    –> [UPDATED 3/15/2010]

    view raw

    Piet! Language Spec

    hosted with ❤ by GitHub

    Reply
    • benjaminplee said, on 03.15.10 at 10:47 pm

      With the latest QuickPiet language additions I am working on some spec tests which should be able to be used to verify implementations of interpreters.

      Reply
  3. Ka said, on 04.01.10 at 4:09 pm

    Dear Friends, Happy Fool’s Day!

    A police officer pulls over this guy who had been weaving in and out of the lanes. He goes up to the guy’s window and says, “Sir, I need you to blow into this breathalyzer tube.”
    The man says, “Sorry officer, I can’t do that. I am an asthmatic. If I do that I’ll have a really bad asthma attack.”
    “Okay, fine. I need you to come down to the station to give a blood sample.”
    “I can’t do that either. I am a hemophiliac. If I do that, I’ll bleed to death.”
    “Well, then we need an urine sample.”
    “I’m sorry, officer, I can’t do that either. I am also a diabetic. If I do that I’ll get really low blood sugar.”
    “All right then I need you to come out here and walk this white line.”
    “I can’t do that, officer.”
    “Why not?”
    “Because I’m too drunk to do that!”

    Happy April Fool’s Day!

    Reply

Leave a reply to benjaminplee Cancel reply