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

Answer 2

APL (Dyalog Unicode), 268 bytes

r←¯999+⍳1999
{⍺←,⊂(⍵∊,¨'io')/⍵⋄p←⊃⍺⋄≡/{⍺←⍬⍬⋄s o←⍺⋄0=≢⍵:o⋄h←¯2↓s⋄t←¯2↑s⋄u←⊃⍵⋄v←1↓⍵⋄∨/u∊⎕D:(s,⊂,⍎u)o∇v⋄'i'=u:((s,⊂,0)o∇v),¨(s,⊂,1)o∇v⋄0=≢s:.1⋄'o'=u:s(o,¯1↑s)∇v⋄'d'=u:(¯1↓s)o∇v⋄1≥≢s:.1⋄(h,,¨∘.(⍎u)/t)o∇v}¨p⍵:p⋄((1↓⍺),,(⍳≢p)∘.{(⍺↑p),(⊂⍵),⍺↓p}(,¨'d+-×'),('-'@('¯'=⊢)⍕)¨r)∇⍵}

Try it online!

An anonymous function that takes tokenized program as input, and gives the tokenized minimal program as output. Uses × instead of * for multiplication.

The idea is that each output can only be linearly dependent on each input. This means that if we want to check the equivalence of two programs, it is enough to compute and compare the outputs for each input being 0 or 1 (2^n cases if the original program has n input commands). We can entirely avoid symbolic computation this way.

Since trying out ~2000 constants takes forever, I put the variable r outside of the function so that we can test for small ranges and observe that the code actually solves the challenge.

Pseudocode

Take a tokenized program.
Create the minimal candidate program by removing all commands except I/O.
Create a queue of candidate programs.
While the head of the queue is not equivalent to the original program
  Pop the head
  For all possible tokens except I/O (Note 1)
    For all possible positions in the program (Note 2)
      Insert the token at the given position of the program
      Push it at the end of the queue
Output the minimal equivalent program

Note 1: All possible tokens include d, +-×, and the numbers -999 to 999 (inclusive).

Note 2: Given a program of length n, only the positions 0 to n-1 need to be considered. The head (position 0) is needed to account for the cases like 1 i - o. The tail (position n) is not needed because it doesn't affect the output(s) in any way.

Ungolfed with comments

⍝ takes tokenized words, 'i' 'o' 'd' '+' '-' '×' or 'num'
⍝ [stk out] runIPL tokens → output
runIPL←{
  ⍺←⍬⍬  ⍝ Initialize stack and output
  stk out←⍺
  0=≢⍵:out  ⍝ Nothing to process
  h←¯2↓stk ⋄ t←¯2↑stk
  u←⊃⍵ ⋄ v←1↓⍵

  ⍝ If the next token is num, push it
  ∨/u∊⎕D: (stk,⊂,⍎u)out∇v
  ⍝ If it is 'i', collect the results for 0 and 1
  'i'=u: ((stk,⊂,0)out∇v),¨(stk,⊂,1)out∇v
  ⍝ Stack underflow; break out and output an invalid value
  0=≢stk: .1
  ⍝ Output
  'o'=u: stk(out,¯1↑stk)∇v
  ⍝ Drop
  'd'=u: (¯1↓stk)out∇v
  1≥≢stk: .1
  ⍝ Arithmetic
  (h,,¨∘.(⍎u)/t)out∇v
}

⍝ strip non-IOs
⍝ takeIO tokens → IO tokens
takeIO←{(⍵∊,¨'io')/⍵}

range←¯1+⍳15

⍝ search for the shortest program whose output exactly matches the original
⍝ should terminate eventually when it meets the original program
⍝ [prog.queue] search tokens → tokens of equivalent program
search←{
  ⍝ Initialize the queue with single program with only I/O commands
  ⍺←,⊂takeIO⍵
  ⍝ List of tokens to try inserting
  newToks←(,¨'d+-×'),('-'@('¯'=⊢)⍕)¨range
  prog←⊃⍺ ⋄ rest←1↓⍺
  ⍝ List of indexes to insert the token
  idxs←⍳≢prog
  ⍝ If the program's output matches the original, it is the answer
  (runIPL prog)≡runIPL⍵: prog
  ⍝ Otherwise, add all possible insertions to the queue
  (rest,,idxs ∘.{(⍺↑prog),(⊂⍵),⍺↓prog} newToks)∇⍵
}

Try it online!