Crazy Ideas

swannodette edited this page Jul 30, 2011 · 25 revisions

Note

None of these things are implemented. This is a sketchbook of what I'm thinking about implementing. core.logic will make some of these things easier.

Hello World!

(defpred pos? pos?)
(defm fib [n] :guard [(pos? n)]
  (+ fib (dec n) (fib (- n 2)))
(defm fib [1] 1)
(defm fib [0] 0)

Order

Could core.logic help us determine equivalent terms elegantly? Perhaps that's what Rich Hickey meant about implication? We don't want to pay for a runtime logic engine though. For example, the following in Standard ML would be problematic.

(defm precip
  ([n] :guard [(integer? n)] (/ 1 n))
  ([0] 0))

We could use the guard to test the literal to reorder the statements. Guards are not functions. They are predicates that must be declared. This simplifies a lot of things. Undeclared predicates will raise an error.

Using rules to optimize predicate dispatch

(?- complement even? odd?)

(defm record-match [a b]
  ([(A. 0) 1])
  ([(A. x) 3] :guard [(even? x)])
  ([(A. 1) b])
  ([(A. x) b] :guard [(odd? x)]))

There's no way normally to know that two predicates are complementary. By making users to define their predicates we get correctness and the most efficient decision tree.

Why stop?

(defpred even? even?)       ; declare the predicate even? maps to even? fn
(defpred number? number?)   ;
(defpred integer? integer?) ;

(?- even? x :- integer? x)   ; anything that is even is an integer
(?- integer? x :- number? x) ; anything that is an integer is a number

Now we can can error-check defm - we know what predicates are subsumed.

Expressiveness + Correctness + Performance

(defpred div3? (fn [n] (= (mod n 3) 0))
(defm gf2
  ([v1] (gf2 (transient [])))
  ([[] v2] (persistent! v2))
  ([[a & r] v2] :guard [(even? a)]
    (recur r (conj v {:even a})))
  ([[a & r] v2] :guard [(odd? a) (div3? a)]
    (recur r (conj v {:odd-div3 a})))
  ([[a & r] v2]
    (recur r v2))
  :where [(vector? v1) (vector? v2)])