Optimize Compiler for simple Reverse Polish Notation Programming Language

Question

Description

Imaginary programming language (IPL) uses Polish Reverse Notation. It has the following commands:

• i -- input number and push it to the stack
• o -- non-destructive output top of the stack (number stays on the stack)
• d -- discard top of stack
• integer number -- push this number to the stack
• +-* -- pop two numbers from the stack, perform corresponding operation and push back the result. There is no division in IPL.

IPL works only with integers and is used for simple calculations. An IPL program is written on one line and separated by spaces. Empty string is a valid IPL program.

IPL Program:

i i + o 

Inputs two numbers, adds them together and outputs the result.

Input numbers and integers that can be pushed to stack are in range [-999, 999], however output can be any. If your language do not support big numbers it is okay though.

Input/output format

You may choose any input/output format as long as it clear to understand and read/write: string, list, tokens etc.

Task

You are given some IPL program, you need to optimize it (reduce length):

i 12 + 3 + o d 2 3 + d

After optimization will become

i 15 + o

You do not have to preserve stack state, but amount of inputs and outputs and their order should match for the original and optimized program.

So IPL program:

-40 i * 2 * o i + 3 1 + o i 2 *

After optimisation will become

i -80 * o i 4 o i

or

-80 i * o i 4 o i

(note that you have to save all inputs, even if they are irrelevant).

There should be no hardcoding for test cases, code should work on any arbitrary IPL program and produce shortest possible IPL program that meets the requirements.

Scoring

Default code-golf scoring.

UPDATE: changed scoring to pure code golf scoring, as per @Sanchises suggestion.

Test cases:

Input:

(empty string)

Possible output:

(empty string)

Input:

i 4 * 2 + 3 * 6 - o

Possible output:

i 12 * o

Input:

1 1 + o

Possible output:

2 o

Input:

i 2 + 3 + o d 2 3 + d

Possible output:

i 5 + o

Input:

-40 i * 2 * o i + 3 1 + o i 2 *

Possible output:

-80 i * o i 4 o i

Input:

i i 1 + i 1 + i 1 + i 1 + d d d d o 

Possible output:

i i i i i d d d d o 

Input:

i i i 0 * * * o

Possible output:

i i i 0 o

Input:

i i i 1 * * * o

Possible output:

i i i * * o

Input:

i 222 + i 222 - + o

Possible output:

i i + o

Input:

i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

Possible output:

i i i i i o 1 o

Input:

i 1 + 2 * 1 + o 

Possible output:

i 2 * 3 + o

Input:

1 1 + o i 2 + 3 + o d 2 3 + d 4 i * 2 * o i + 3 1 + o i 2 * i i 1 + i 1 + i 1 + i 1 + d d d d o i i i 0 * * * o i i i 1 * * * o i 2 + i 2 - + o i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

Possible output:

2 o i 5 + o 8 i * o i 4 o i i i i i i d d d d o i i i 0 o i i i * * * o i i + o i i i i i o 1 o

Answer 1

Wolfram Language (Mathematica), 733 728 690 564 516 506 513 548 bytes

j=Integer;f=Flatten;s=SequenceReplace;A=FixedPoint[f@s[#,{{x_j,p,y_j,t}->{y,t,x*y,p},{x_j,y_j,p}->x+y,{x_j,y_j,t}->x*y,{x_j,p,y_j,p}->{x+y,p},{x_j,t,y_j,t}->{x*y,t},{0,p}|{1,t}->{},{0,t}->{d,0}}]//.{a___,Except[i|o]}->{a}&,#]&;B=Expand@Check[f@FoldPairList[f/@Switch[#2,i,{{i},{#,i@c++}},o,{{Last@#},#},d,{{},Most@#},p,{{},{#[[;;-3]],Tr@#[[-2;;]]}},t,{{},{#[[;;-3]],#[[-2]]*Last@#}},_,{{},{##}}]&,c=0;{},#],x]&;F=MinimalBy[w=A@f[#/.m->{-1,t,p}];z=B@w;s[#,{-1,t,p}->m]&/@A/@Select[Permutations@Join[w,Cases[z /.i@_->i,_j,∞]],B@#==z&],Length][[1]]&

Try it online!

This is a four-step tour-de-force that (1) replaces "-" with "-1 * +" so that we don't have to deal with subtractions, (2) simplifies the list of commands a bit, (3) makes a list of all permutations of this list of commands and picks out those that give the same result when parsed (executed), and (4) simplifies these lists of commands a bit and picks the shortest, after converting certain operations back to subtractions.

This code is terribly inefficient because it goes through the list of all permutations of the input code. For long input codes I don't recommend running this code; but as I read it there are no runtime or memory restrictions in this challenge.

This code does the optimization step after converting all "-" operations to "+" operations with signs flipped, and only at the end re-introduces the "-" operator when converting code back to strings. This implies for example that "i -1 i * + o" is correctly optimized to "i i - o".

As the i/o format requirement is quite loose, this code takes and returns code as lists, where the symbols "+", "-", "*" are represented by p, m, t, tokens respectively. The conversion from and to strings is done in the wrapper function given on TIO:

G[S_] := StringReplace[{"p" -> "+", "m" -> "-", "t" -> "*"}]@StringRiffle@
         Quiet@F@
         ToExpression[StringSplit[S] /. {"+" -> p, "-" -> m, "*" -> t}]

Un-golfed version, including the string-format wrapper and minimizing the final code string length instead of the number of tokens, and including a few more transformation niceties:

(* convert code string to list of operators *)
inputfilter[s_] := ToExpression[Flatten[StringSplit[s] /.
  {"i" -> i, "o" -> o, "d" -> d, "+" -> p, "-" -> {-1, t, p}, "*" -> t}]]

(* convert list of operators to code string *)
outputfilter[s_] := StringReplace[StringRiffle@Flatten@SequenceReplace[s,
  {{-1, t, p} -> m,                         (* convert "-1 t p" back to "-"             *)
   {x_ /; x < 0, p} -> {-x, m},             (* convert "y x +" to "y -x -" when x<0     *)
   {x_ /; x < 0, t, p} -> {-x, t, m}}],     (* convert "y x * +" to "y -x * -" when x<0 *)
  {"m" -> "-", "p" -> "+", "t" -> "*"}]     (* backsubstitution of symbols              *)

(* simplify a list of operators somewhat *)
simplifier[s_] := FixedPoint[Flatten@SequenceReplace[#,
  {{x_Integer, p, y_Integer, t} -> {y, t, x*y, p},  (*  "x + y *" -> "y * (xy) +"       *)
   {x_Integer, y_Integer, p} -> x + y,              (*  "x y +" -> "(x+y)"              *)
   {x_Integer, y_Integer, t} -> x*y,                (*  "x y *" -> "(xy)"               *)
   {x_Integer, p, y_Integer, p} -> {x + y, p},      (*  "x + y +" -> "(x+y) +"          *)
   {x_Integer, t, y_Integer, t} -> {x*y, t},        (*  "x * y *" -> "(xy) *            *)
   {0, p} | {1, t} -> {},                           (*  "0 +" and "1 *" are deleted     *)
   {x_Integer, i, p} -> {i, x, p},                  (*  "x i +" -> "i x +"              *)
   {x_Integer, i, t} -> {i, x, t},                  (*  "x i *" -> "i x *"              *)
   {0, t} -> {d, 0}}] //.                           (*  "0 *" -> "d 0"                  *)
  {a___, Except[i | o]} -> {a} &, s]                (* delete trailing useless code     *)

(* execute a list of operators and return the list of generated outputs *)
parse[s_] := Expand@Quiet@Check[Flatten@FoldPairList[  (* stack faults are caught here     *)
  Function[{stack, command},                        (* function called for every command*)
    Flatten /@ Switch[command,                      (* code interpretation:             *)
    i, {{i}, {stack, i[inputcounter++]}},           (* output "i" and add input to stack*)
    o, {{stack[[-1]]}, stack},                      (* output top of stack              *)
    d, {{}, Most[stack]},                           (* delete top of stack              *)
    p, {{}, {stack[[;; -3]], stack[[-2]] + stack[[-1]]}},  (* add two stack elements    *)
    t, {{}, {stack[[;; -3]], stack[[-2]]*stack[[-1]]}},    (* multiply two stack elements*)
    _, {{}, {stack, command}}]],                    (* put number onto stack            *)
    inputcounter = 0; {},                           (* start with zero input counter and empty stack*)
    s],                                             (* loop over code list              *)
  x]                                                (* return "x" if an error occurred  *)

(* the main function that takes a code string and returns an optimized code string *)
F[s_] := Module[{w, q},
  w = simplifier@inputfilter@s;      (* convert input to useful form *)
  q = parse[w];                      (* execute input code *)
  MinimalBy[
    outputfilter@*simplifier /@      (* simplify and stringify selected codes          *)
      Select[Permutations[w],        (* all permutations of code list                  *)
             parse[#] == q &],       (* select only those that give the correct output *)
    StringLength] // Union]          (* pick shortest solution by length               *)

Thanks to @redundancy for catching a bug: The parser needs a Expand applied to the output in order to handle distributive equivalence. 506→513

update

Now also optimizes 1 o 1 + o to 1 o 2 o. This was a surprisingly difficult case and made the code much slower. 513→548