Futamura Projections Demo in Clojure

futamura.md

Futamura Projections

Insight

Name	Type
Inputs	Any
Output	Any
Program	Text
Compiler	Program => CompiledProgram
Interpreter	Program, DynamicInputs => Output
Specializer	Program, StaticInputs => OptimizedProgram

1. Specializer :: InterpreterProgram => InterpretedProgram => CompiledProgram
2. Specializer :: SpecializerProgram => InterpreterProgram => CompilerProgram
3. Specializer :: SpecializerProgram => SpecializerProgram => InterpreterProgram => CompilerProgram

or

1. Specializer(InterpreterProgram, InterpretedProgram) => CompiledProgram
2. Specializer(SpecializerProgram, InterpreterProgram) => CompilerProgram
3. Specializer(SpecializerProgram, SpecializerProgram) => InterpreterProgram->CompilerProgram

Example 1

(def Program 4)

(def Interpreter inc)

(Interpreter Program)
;; => 5

;; Clojure's `partial` fn
(let [plus2 (partial + 2)]
  (plus2 1))
;; => 3

(def Specializer partial)

;; First Projection
;; ================
(def P-Compiled
  (Specializer Interpreter Program))

(P-Compiled)
;; => 5

;; Second Projection
;; =================
(def Compiler_
  (Specializer Specializer Interpreter))

(let [p-compiled (Compiler_ Program)]
  (p-compiled))
;; => 5

;; Third Projection
;; ================
(def CompilerCompiler
  (Specializer Specializer Specializer))

(let [interpreter #(* 10 %)
      compiler (CompilerCompiler interpreter)
      program 7
      p-compiled (compiler program)]
  (p-compiled))
;; => 70

Example 2

;; futamura.clj
(ns futamura
  (:require [clojure.string :as str]))

;; ========= util =====================
(defn get-source-code [var]
  (let [{:keys [file line]} (meta var)
        file (slurp file)
        lines (->> file
                   str/split-lines
                   (drop (dec line)))
        text (str/join "\n" lines)]
    (read-string text)))

(defn quoted [code]
  (list 'quote code))
;; ====================================

(def Program
  '(+ x y 3))

(defn Specializer
  [code stat-in]
  (case (first code)
    'defn
    (let [[_ _ argv & body] code
          new-argv (->> argv
                        (remove #(contains? stat-in %))
                        vec)]
      `(fn  ~new-argv
         (let [~@(for [kv stat-in
                       x kv]
                   x)]
           ~@body)))

    ;; else
    `(let [~@(for [kv stat-in
                   x kv]
               x)]
       ~code)))

(Specializer Program '{x 1})
;; => (let [x 1] (+ x y 3))

(Specializer '(defn add [x y]
                (+ x y))
             '{x 1})
;; => (fn [y] (let [x 1] (+ x y)))


(defn Interpreter
  [code dyn-in]
  (eval (Specializer code dyn-in)))

(Interpreter Program '{x 1 y 2})
;; => 6


;; First Projection
;; ================
(def P-Compiled-Source
  (Specializer (get-source-code #'Interpreter)
               {'code (quoted Program)}))

P-Compiled-Source
;; => (fn [dyn-in] (let [code '(+ x y 3)] (eval (Specializer code dyn-in))))

(def P-Compiled
  (eval P-Compiled-Source))

(P-Compiled '{x 1 y 2})
;; => 6


;; Second Projection
;; =================
(def Compiler-Source
  (Specializer (get-source-code #'Specializer)
               {'code (quoted (get-source-code #'Interpreter))}))

(let [compiler (eval Compiler-Source)
      p-compiled-source (compiler {'code (quoted Program)})
      p-compiled (eval p-compiled-source)]
  (p-compiled '{x 1 y 2}))
;; => 6


;; Third Projection
;; ================
(def CompilerCompiler-Source
  (let [specializer-source (get-source-code #'Specializer)]
    (Specializer specializer-source
                 {'code (quoted specializer-source)})))

(let [compiler-compiler (eval CompilerCompiler-Source)
      interpreter-source (get-source-code #'Interpreter)
      compiler-source (compiler-compiler {'code (quoted interpreter-source)})
      compiler (eval compiler-source)
      p-compiled-source (compiler {'code (quoted Program)})
      p-compiled (eval p-compiled-source)]
  (p-compiled '{x 1 y 2}))
;; => 6