Interpret Grass

Question

Grass is a procedural functional programming language whose program is written with three alphabets of Wvw and with byte-by-byte I/O capability.

Reference implementations

Running environment

Has (1) input and (2) output, both of they are represented with byte sequences:

interface Environment {
   input: Uint8Array;
   output: Uint8Array;
}

Program halting

The program shall halt (1) as described in Semantics, or (2) when runtime-error occurs.

Built-in type

Everything is curryable function. Function is either (1) a Byte or (2) not a Byte.

Built-in functions

Six.

read
Byte
1. true and false
next
out

read

Takes one argument and return a Byte from standard input regardless of the argument. Return the argument if standard input is empty.

-- If [72, 104] is given
f4 = read read -- @72
f5 = read read -- @104
f6 = read read -- read
f7 = read read -- read

Byte

Is an unsigned 8-bit integer. Takes one argument and return true or false to indicate the function itself and the argument are same value:

f4 = @119 @119 -- true
f5 = @119 @118 -- false
f6 = @119 read -- false

-- NOTE wrapping a Byte inside a function makes it non-Byte
f7 a7 = do
  a8 = @119 a7
  return a8
f8 = @119 f7 -- false
f9 = f7 @119 -- true

true and false

Church-encoded Booleans:

f4 = true f1
f5 = f4 f2 -- f1

f6 = true f1
f7 = f6 f2 -- f2

out

Takes a Byte and return, with side effects of outputting to standard output. It's runtime-error to give a non-Byte:

f4 = out @72 -- @72; stdout = [72]
f5 = out f4 -- @72; stdout = [72, 72]
f6 = out read -- error "out expected Byte, got read"

Valid Program Syntax

Program is a list of Abstraction -- w+(W+w+)* -- and Application(s) -- (W+w+)+ --, separated by lowercase v.

Represented as follows, with BNF notation and regular expressions:

Program = Program'
Program' = Abstraction | Abstraction Statements
Statements = Statement | Statement Statements
Statement = Abstraction | Applications

Abstraction = Parameters Body
Parameters = /w+/
Body = EndOfAbstraction | Application Body
EndOfAbstraction = EndOfProgram | /v+/

Applications = EndOfApplications | Application Applications
Application = FunctionIndex ArgumentIndex
FunctionIndex = /W+/
ArgumentIndex = /w+/
EndOfApplications = EndOfProgram | /v+/

EndOfProgram = /$/

Semantics

Program
Statement
Application
- Referring non-existing value
Abstraction

Program

Predefined values

Every valid program has following implicit global values of builitins:

f0 = read
f1 = @119
f2 = next
f3 = out

then the content of Program' follows.

Implicit last statement

And every valid program, as the implicit last statement, shall call last statement with itself:

-- If last defined value is f99:

_ = f99 f99

Completing the statement makes the program halt.

Statement

Every 0-indexed N-th statement represents 0-indexed (N+4)-th global value.

Here is valid Grass Program with comments. The comments describe meanings of each statement:

f4 a4 a5 = do
ww
  a6 = a4 a5
 WW w
  a7 = a4 a6
 WWW w
  return a7
v

f5 = f3 f4
WW w

f6 = f5 f1
W www_ww

Application

Application is (1) relative index of value as function and (2) relative index of value as argument. See the following applications again:

f5 = f3 f4
WW w

f6 = f5 f1
W www_ww

The statement WWw has two Ws and one w, so it means to apply 1st previous value to 2nd previous value. Similar for f6: Wwwwww.

Referring non-existing value

...results in runtime-error, no matter as a function or as an argument. Example of program wWWWWWWwwwwwWWwvWww:

f4 a4 = do
  a5 = f-1 f0 -- error "No such function: f-1"
 WWW_WWW www_ww
  a6 = a4 a5 -- Unreachable because of f-1
 WW w
  return a6 -- Unreachable 
v
f5 = f4 f3 -- Runtime-error occurs
W ww
-- End of program
_ = f5 f5 -- Unreachable

Another example of program wWWWWWWwwwwwWWwvWWwwww

f4 a4 = do
  a5 = f-1 f0 -- error "No such function: f-1"
 WWW_WWW www_ww
  a6 = a4 a5 -- Unreachable because of f-1
 WW w
  return a6 -- Unreachable 
v
f5 = f3 f1 -- out @119; Not runtime-error
WW www_w
-- End of program
_ = f5 f5

Abstraction

Abstraction is (1) number of parameters -- as number of leadings ws -- and (2) list of applications.

Take the function wWWwwwwWWwwv: it has leading one w so it takes one argument:

f4 a4 = do
w

then the function body follows, with local and global scopes:

  a5 = f3 f1
 WW www_w
  a6 = a4 a4
 WW ww

the function shall return last local value;

  return a6
v

The function may lack Applications: example for function wwwv:

f5 a5 a6 a7 = do
www
  return a7
v

Task

Choose one of the following two:

Given (1) a valid Grass Program without comments and (2) a list of bytes for the Program input, output a list of bytes as desired.
Given (1) a valid Grass Program without comments, output a program/function in your language other than Grass that accepts (2) a list of bytes, output a list of bytes as desired.

Test cases

In TOML v1.1. Some cases has newlines for readability; your program may expect comments to be removed.

Some test cases may not halt; those uses output_begins_with. Some programs output long ones, and are described with output_regex.

Program with null input shall output constant output no matter what is given.

# https://web.archive.org/web/20250126114618/https://blue.sky.or.jp/grass/

[[case]]
## Very simple
program = "wWWwwww"
input = null
output = "w"

[[case]]
## Infinite loop example
program = "wWWwwwwWWww"
input = null
output_begins_with = "wwwwwwwwww"

[[case]]
## 1 + 1
program = "wwWWwvwwwwWWWwwWwwWWWWWWwwwwWwwvwWWwwwWwwwwWwwwwwwWwwwwwwwww"
input = null
output= "ww"

# http://blog.livedoor.jp/naoya_t/archives/51026653.html
# https://w.atwiki.jp/s-irie/pages/20.html

[[case]]
## (2^2)^(2^2)
program = "wwWWwWWWwvwWWwwWwwwWwwwwwWwwwwwwww"
input = null
output_regex = "w{16}"

[[case]]
## ASCII printables
program = """wWWwWWWWwvwwWWwWWWwvwwwWWWwwWwwWWWWwv
wWWwwwWWWwWWWWWwwWwwwwwWwwwWWWWWWWWwWWWWwwwWwww
WWWWWWWWWWwWWWWwwwwwwwwwwwwwww
WwwwwwwwwwwwwwwwwwWWWwwwwwwwwwwwwwwwWww"""
input = null
output = """ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"""

[[case]]
## w or not w
program = "wWWWwwwwWWWWWWwWwwwwwwWwwwwwwwWwwwwWWWWWWWw"
[[case.io_spec]]
input = "w"
output = "w"
[[case.io_spec]]
input = "W"
output = "x"
[[case.io_spec]]
input = ""
output = "x"

[[case]]
## Fake cat
program = """wwWWwWWWwvwWWwwWwwwwwWwwwwwwwWWwWWWWWWWWWWwWwwWwWwwwwwwwwwwWwwwwWWWwwwwwwwwwwWw
wwwwwwwwww"""
[[case.io_spec]]
input = "Hello \x03 World"
output = "Hello \x03 World"
[[case.io_spec]]
input = "Hello \x7f World"
output = "Hello "

[[case]]
## Fibonacci sequence 12 items
program = """wwWWwwWwwvwwWWWwWWWwvwWWwWwvwvwwWWWwwvwwvwWWWwwWWwWwwwwwvwwwWWwwwWWwvwwwWWWWwwW
WWWWWWWwwWWWWWwwWwwWwwwwwwwwwwwwvwwwWWWwwWwwWWWWwvwwWWwvwWWWwwWwWWWWWwwWwwwwwwW
wwwWWWWWwWwwwwwwwwwwwwwwwwwwwwWWWWWwWwwwwwwwwwwwwwwwwwwwwwwwWWWWWWWWWWwwwwwwwww
wwwwwwwwwwwwwWwwwwwwwwwwwwwwwwwwwwwwwwwWWWWWWWWWWWWWWWWWWWWWWWWwwwvwwwwWWWWWwwW
WWWwwwwwwwwWwwwwWWWWWWWWWWWwwwwWWWWWWWWWWWWWWwWwWwwwwwwwwwwWwwwwwwwwwWwwwwwwWww
wwwwvwWWWWWwwwwWwWwwwwwwwWwwWWwWWWWWWWWWWWWWWWWWwwwwwwwWwwwwwwwwwwwwwwwWwwwwwww
wwwwWwwww"""
input = null
output_regex = """w
w
ww
www
wwwww
w{8}
w{13}
w{21}
w{34}
w{55}
w{89}
w{144}"""

# CGCC

[[case]]
## https://codegolf.stackexchange.com/a/287062/113493
program = "wvwwwWWWwwWWWwwWWwv
WwwWwwwwwWWWwwWWWwwwwWwwWwwwwWWWwwWwwv
wwWWWWWWWWWWWWWwwWWWWwWWWWWWWWWWWWWWWWWwWwwwwWwWwv
WWWWWWWWWWWWWWWwWWw"
[[case.io_spec]]
input = "0"
output = "0"
[[case.io_spec]]
input = "1"
output_begins_with = "11111111"

[[case]]
## https://codegolf.stackexchange.com/a/95207/113493
program = """wWWWwWWWWwv
wWWwWWWwv
wWWWwWWWWWwWWWWWWwwwWWWWWWWwWWWWWWwwwWWWWWWWWWWwWWWWWWWWWWwv
wWWWwWWWWwv
wWWwWWWwvwWWwWWWwvwWWwWWWwv
wWWwwwwwwwwwwwWWWwWWWWWwWWWWWWWwWWWWWWWWWwWWWWWWWWWWWWWWWwWWWWWWWWWWWWwv"""
input = null
output = "2007"

[[case]]
## https://codegolf.stackexchange.com/a/120737/113493
program = """wWWWwWWWWwv
wWWwWWWwv
w WWWw WWWWWWWWw WWWWw WWWWWWWw WWWWWWWWwwww v
wWWWwWWWWwv
wWWwWWWwv
wWWwWWWwv
wWWwWWWwv
wWWwwwwwwwwwwwWWWwWWWWWwWWWWWWWwWWWWWWWWWwWWWWWWWWWWWWWWWwWWWWWWWWWWWWwv"""
input = null
output = "62"

[[case]]
## https://codegolf.stackexchange.com/a/163613/113493
program = """wWWWwWWWWwWWWWWwvwwWWwWWWwv
WwWwwwwwWWWwWWWwWWWWWwv
wWWwwwwwwwwwwwWWWwWWWWWwWWWWwv
wWWwwwwwWWWWWWWWWWWWwWWWwv
WwwwwwwwwwwwWWwwwwwwWWWWWWWWwWWWWWWWwwWWWWWWwwwwwwwv
wWWWWWWWwwwwwwwwwWWWWWWWWWWWWWwWWWwv
WwwwwwwwwwwwwwwwwwWWwwwwwwwwwwwwWWWWWWWWWWWWWWWWWwv
wWwWwwwwwwwwWwwwwwwWwwwwwwWwwwwwwwWwwwwwwwWwwwwwwwwwwwwwwWWWWWWWWWWWWWWWWWWwv
wwWWWWWWWWWWWWWWWWWWWWWWwWWWwwwv
WWwWWWWWWWWWWWWWWWWWWWWWwwwwWWwwwwwwwwwWwwwwwwWwwwWwwwwwwwwwWWWWWWWWWWWWwWwwwwwwwwwwwwwwwwww"""
input = null
output = "Hello, World!"

More test cases

Simple cat program - @aschepler, 2020
Unscramble the Source Code - @jimmy23013, 2014
Hello ASCII World! - @emirps, 2022
Print every other character in string starting with second character - @bluswimmer, 2023

Ideally every submission in Grass on CGCC, which were since 2014 until submission of this task, should work.

Non-essential ones

The following programs are out of test cases

ASCII's 95 Characters...95 Movie Quotes - @jimmy23013, 2014

Sandbox

I have the strange feeling that this language isn't all that complicated, and yet I don't understand anything about the spec. — Arnauld
– Arnauld, Commented Apr 14 at 15:22

Daniel T · Accepted Answer · 2026-04-23 09:27:08Z

Perl 5, 389 bytes

@_=(sub{($_)=@_;ref?exit:print chr;$_},sub{($_[0]+1)&255},119,sub{$/=\1;$_=<STDIN>;defined?ord:$_[0]});map{$w=0,$v=$s=sub{@_};map{my($S,$x,$X)=($s,$w-1,$W-1);/W/?++$W:$W&&($v=$s=sub{$_=$_[$X];$S->((ref?$_[$x]->$_(@_):$_[$x]==$_?sub{my($s)=@_;sub{$s}}:sub{sub{$_[0]}})[0],@_)},$W=$w=0);/w/&&do{++$w,my$V=$v;$v=sub{my@s=@_;sub{$_[0]->$V(@s)},@_}}}(reverse/./g),v;@_=&$v}<>=~/[^v]+/g;&{$_[0]}

Try it online!

Assumptions based on "Valid Program Syntax":

I consider newlines in Grass to be comments, so they're not supported. Add -g and replace <> with <>=~y/\n//dr to add support (+13)
Fullwidth is not supported. Add uconv -x Fullwidth-Halfwidth| to add support (+29)
stderr should be ignored for Hello ASCII World!. Add 2>&- (+5) or replace &{$_[0]} with ref$_[0]&&&{$_[0]} (+10) if it's important

Design:

Explaining each statement will not help. The architecture underwent massive trial-and-error and I rewrote things 5 times until it worked
I skipped the (Code, Environment, Dump) structure the specification and reference implementations used. It was too academic to understand and I would save bytes by executing things directly
- The map{...} contains a state machine. Iterating the Statement backwards is easier. Think about the w→W and W→w transitions. A dummy final v must be readded to have a last transition that forces data out
- When previous/current letters are identical, it only counts, like the Awk implementation
- The Program of Statements cannot be reversed as non-Abstraction must run immediately and have previous stack values, so I split by "v"
I didn't create a stack data structure.
- My previous version had a stack, but saving and restoring it was easy to get wrong
- I just pass invoked functions the arguments i.e. @_. [0] retrieves only the callee's return value. When without this code, I implement non-Abstractions i.e. bare Applications, which replace us with their entire stack so that WwWw will work without a middle v. ,@_ adds the parent stack. Perl returns the last statement's value
- I later saved 40+ bytes by restricting the return @_ to the Application callers not their callees e.g. primitives. This also allowed eliminating recursion
- The new "stack" is upside down. The last-in element is [0] to save minus signs
my saves values in the closure
The default variable i.e. $_ is heavily used, and I can omit writing it
Like most implementations, I use chr and ord
Like the Python implementation, my int-as-equality handling is in the Application-calling code

Deobfuscation:

~~@q and &p~~ outer map: unprocessed_statement_queue and process_program, will process the queue and be primed with primitives
$w, previous version becomes $x: "w" count
$W, previous version becomes $X: "W" count
$s, previous iteration becomes $S: executable part of current statement so far going right-to-left
$v, previous iteration becomes $V: curried wrapper for $s. Discarded upon W and returned upon v
@s, and $s once: saved stack
$/=\1: Read one letter at a time

Space usage:

26% Grass primitives
26% Splitting/looping over grass code
33% W / Application-calling
15% w / Currying

Stack Exchange Network

Interpret Grass

Reference implementations

Table of Contents

Running environment

Program halting

Built-in type

Built-in functions

read

Byte

true and false

next

out

Valid Program Syntax

Semantics

Program

Predefined values

Implicit last statement

Statement

Application

Referring non-existing value

Abstraction

Task

Test cases

More test cases

Non-essential ones

1 Answer 1

Perl 5, 389 bytes

Linked

Hot Network Questions

Interpret Grass

Reference implementations

Table of Contents

Running environment

Program halting

Built-in type

Built-in functions

read

Byte

true and false

next

out

Valid Program Syntax

Semantics

Program

Predefined values

Implicit last statement

Statement

Application

Referring non-existing value

Abstraction

Task

Test cases

More test cases

Non-essential ones

1 Answer 1

Perl 5, 389 bytes

Linked

Related

Hot Network Questions