/supercompilation

An implementation of the supercompilation ideas

Primary LanguageKotlinMIT LicenseMIT

Supercompilation of HLL language

KMP algorithm implementation comparison

Comparison table -- step reductions

The time measured in beta reduction steps. There are 15 measures averaged in one cell of the table!

+-----------------------------------------------------------------------------------------------+
+                                 Results of original program                                   +
+-----------------------------------------------------------------------------------------------+
+   input size  |                                pattern size                                   +
+---------------+---------------+---------------+---------------+---------------+---------------+
|               |             1 |             2 |             3 |             4 |             5 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|             5 |         86.80 |        127.20 |        147.67 |        143.33 |        169.20 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            10 |        154.00 |        248.87 |        251.80 |        302.73 |        338.07 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            15 |        197.00 |        370.27 |        445.53 |        385.13 |        460.53 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            20 |        293.20 |        385.67 |        479.40 |        631.33 |        572.40 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            30 |        259.33 |        431.27 |        819.20 |        940.27 |        790.47 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            40 |        493.53 |        992.00 |        935.87 |       1103.67 |        972.20 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            50 |        457.27 |        742.00 |       1538.53 |       1568.67 |       1531.20 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            75 |        820.27 |       1035.20 |       1927.27 |       1828.87 |       2014.73 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           100 |        818.80 |       1776.27 |       1668.07 |       2748.47 |       3106.20 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           125 |        971.53 |       1366.80 |       2324.00 |       3780.00 |       3202.53 |
+---------------+---------------+---------------+---------------+---------------+---------------+

+-----------------------------------------------------------------------------------------------+
+                              Results of supercompiled program                                 +
+-----------------------------------------------------------------------------------------------+
+   input size  |                                pattern size                                   +
+---------------+---------------+---------------+---------------+---------------+---------------+
|               |             1 |             2 |             3 |             4 |             5 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|             5 |         15.60 |         19.93 |         21.60 |         20.87 |         24.07 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            10 |         27.47 |         40.27 |         37.73 |         44.93 |         51.60 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            15 |         34.60 |         58.73 |         69.40 |         57.33 |         69.20 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            20 |         51.47 |         60.80 |         72.20 |         96.80 |         83.60 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            30 |         45.07 |         67.93 |        128.27 |        143.13 |        118.73 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            40 |         85.87 |        159.60 |        141.80 |        168.27 |        142.53 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            50 |         79.33 |        118.40 |        238.40 |        237.00 |        230.40 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            75 |        142.20 |        163.27 |        297.13 |        275.00 |        305.80 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           100 |        141.67 |        279.93 |        255.47 |        417.80 |        469.47 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           125 |        168.00 |        216.00 |        357.13 |        577.00 |        485.33 |
+---------------+---------------+---------------+---------------+---------------+---------------+

KMP comparison table -- timing (in seconds)

The time measured in seconds. There are 15 measures averaged in one cell of the table!

+-----------------------------------------------------------------------------------------------+
+                                 Results of original program                                   +
+-----------------------------------------------------------------------------------------------+
+   input size  |                                pattern size                                   +
+---------------+---------------+---------------+---------------+---------------+---------------+
|               |             1 |             2 |             3 |             4 |             5 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|             5 |          0.01 |          0.01 |          0.01 |          0.01 |          0.01 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            10 |          0.02 |          0.01 |          0.02 |          0.02 |          0.02 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            15 |          0.02 |          0.02 |          0.03 |          0.03 |          0.04 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            20 |          0.03 |          0.04 |          0.04 |          0.07 |          0.07 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            30 |          0.04 |          0.10 |          0.11 |          0.12 |          0.16 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            40 |          0.08 |          0.20 |          0.20 |          0.25 |          0.31 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            50 |          0.09 |          0.28 |          0.42 |          0.46 |          0.53 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            75 |          0.31 |          0.83 |          1.05 |          1.41 |          1.39 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           100 |          0.73 |          1.72 |          2.64 |          2.76 |          3.13 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           125 |          0.89 |          2.79 |          4.71 |          5.30 |          5.49 |
+---------------+---------------+---------------+---------------+---------------+---------------+

+-----------------------------------------------------------------------------------------------+
+                              Results of supercompiled program                                 +
+-----------------------------------------------------------------------------------------------+
+   input size  |                                pattern size                                   +
+---------------+---------------+---------------+---------------+---------------+---------------+
|               |             1 |             2 |             3 |             4 |             5 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|             5 |          0.00 |          0.00 |          0.00 |          0.01 |          0.01 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            10 |          0.00 |          0.01 |          0.01 |          0.02 |          0.03 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            15 |          0.01 |          0.01 |          0.02 |          0.03 |          0.05 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            20 |          0.01 |          0.02 |          0.03 |          0.07 |          0.10 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            30 |          0.01 |          0.05 |          0.08 |          0.13 |          0.24 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            40 |          0.02 |          0.09 |          0.16 |          0.27 |          0.43 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            50 |          0.02 |          0.13 |          0.32 |          0.50 |          0.75 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|            75 |          0.08 |          0.39 |          0.78 |          1.47 |          1.85 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           100 |          0.20 |          0.81 |          1.91 |          2.78 |          4.29 |
+---------------+---------------+---------------+---------------+---------------+---------------+
|           125 |          0.23 |          1.27 |          3.37 |          5.24 |          7.12 |
+---------------+---------------+---------------+---------------+---------------+---------------+

Roadmap

pt. 1 -- basic

  • Tree program representation
  • Tree pretty-printer
  • Interpreter
  • Tests

pt. 2 -- expressions operation and relations

  • Tightest expression generalization (e1 ⨅ e2)
  • Homeomorphic embedding relation (◁, ⊴)
  • Tests ❗ (\x.x x)(\x.x x) <=> f f where f = \x.x x

pt. 3 -- tree operations

  • Driving
  • Whistle(b, ◁) (a.k.a. find)

    find ancestor node a such that a ◁ b

  • Folding (if expr is renaming, make backtrace edge)
  • Let-abstraction generalization
  • Build program process tree
  • Extract program from process tree
  • Tests

Optional

  • Lambda-lifting preprocessing (move lambdas to where block and name them)
  • Tree parser
  • CLI
  • KMP Test

Program example

sum (squares (upto 1 n)) 0
 where
  sum     = \xs . \a .
          case xs of
          []     -> a
          x : xs -> sum xs (x + a)
          esac
          
  squares = \xs.
          case xs of
          []     -> []
          x : xs -> (x * x) : squares xs
          esac
          
  upto   = \m. \n.
          case (m > n) of
          True -> []
          False -> m : (upto (m + 1) n)
          esac