Module: MicroKanren::Core

Includes:
Lisp
Defined in:
lib/micro_kanren/core.rb

Instance Method Summary collapse

Methods included from Lisp

#assp, #car, #cdr, #cons, #cons_cell?, #print_ast

Instance Method Details

#bind(d, g) ⇒ Object 



78
79
80
81
82
83
84
85
86
 
# File 'lib/micro_kanren/core.rb', line 78

def bind(d, g)
  if d.nil?
    mzero
  elsif d.is_a?(Proc) && !cons_cell?(d)
    -> { bind(d.call, g) }
  else
    mplus(g.call(car(d)), bind(cdr(d), g))
  end
end

#call_fresh(f) ⇒ Object

Call function f with a fresh variable.



61
62
63
64
65
66
 
# File 'lib/micro_kanren/core.rb', line 61

def call_fresh(f)
  -> (s_c) {
    c = cdr(s_c)
    f.call(var(c)).call(cons(car(s_c), c + 1))
  }
end

#conj(g1, g2) ⇒ Object 



94
95
96
97
98
 
# File 'lib/micro_kanren/core.rb', line 94

def conj(g1, g2)
  -> (s_c) {
    bind(g1.call(s_c), g2)
  }
end

#disj(g1, g2) ⇒ Object 



88
89
90
91
92
 
# File 'lib/micro_kanren/core.rb', line 88

def disj(g1, g2)
  -> (s_c) {
    mplus(g1.call(s_c), g2.call(s_c))
  }
end

#empty_state ⇒ Object 



100
101
102
 
# File 'lib/micro_kanren/core.rb', line 100

def empty_state
  cons(mzero, 0)
end

#eq(u, v) ⇒ Object

Constrain u to be equal to v.



42
43
44
45
46
47
 
# File 'lib/micro_kanren/core.rb', line 42

def eq(u, v)
  ->(s_c) {
    s = unify(u, v, car(s_c))
    s ? unit(cons(s, cdr(s_c))) : mzero
  }
end

#ext_s(x, v, s) ⇒ Object 



12
13
14
 
# File 'lib/micro_kanren/core.rb', line 12

def ext_s(x, v, s)
  cons(cons(x, v), s)
end

#mplus(d1, d2) ⇒ Object 



68
69
70
71
72
73
74
75
76
 
# File 'lib/micro_kanren/core.rb', line 68

def mplus(d1, d2)
  if d1.nil?
    d2
  elsif d1.is_a?(Proc) && !cons_cell?(d1)
    -> { mplus(d2, d1.call) }
  else
    cons(car(d1), mplus(cdr(d1), d2))
  end
end

#mzero ⇒ Object 



10
 
# File 'lib/micro_kanren/core.rb', line 10

def mzero ; nil ; end

#unify(u, v, s) ⇒ Object 



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/micro_kanren/core.rb', line 16

def unify(u, v, s)
  u = walk(u, s)
  v = walk(v, s)

  if var?(u) && var?(v) && vars_eq?(u, v)
    s
  elsif var?(u)
    ext_s(u, v, s)

  elsif var?(v)
    ext_s(v, u, s)

  elsif pair?(u) && pair?(v)
    if s = unify(car(u), car(v), s)
      unify(cdr(u), cdr(v), s)
    end
  elsif u == v
    s
  end
end

#unit(s_c) ⇒ Object 



37
38
39
 
# File 'lib/micro_kanren/core.rb', line 37

def unit(s_c)
  cons(s_c, mzero)
end

#var(*c) ⇒ Object 



5
 
# File 'lib/micro_kanren/core.rb', line 5

def var(*c)       ; Array.new(c)   ; end

#var?(x) ⇒ Boolean

Returns:

  • (Boolean) 


6
 
# File 'lib/micro_kanren/core.rb', line 6

def var?(x)       ; x.is_a?(Array) ; end

#vars_eq?(x1, x2) ⇒ Boolean

Returns:

  • (Boolean) 


8
 
# File 'lib/micro_kanren/core.rb', line 8

def vars_eq?(x1, x2) ; x1 == x2    ; end

#walk(u, s) ⇒ Object

Walk environment S and look up value of U, if present.



50
51
52
53
54
55
56
57
58
 
# File 'lib/micro_kanren/core.rb', line 50

def walk(u, s)
  if var?(u)
    pr = assp(-> (v) { u == v }, s)
    pr ? walk(cdr(pr), s) : u

  else
    u
  end
end