Pattern-based programming

New to Julia
1

Hi. Just curious: Is it possible to harness the Julia dispatcher as an inference engine by placing restrictions on function arguments to create a rule-based program? So for example I might implement the Greatest Common Denominator function gcd like this:

gcd(a,b) = gcd(b,mod(a,b))
gcd(a,0) = a

Clearly this code won’t work, but every now and then I get the feeling there might be some way of doing it using type restrictions, so I thought I’d ask. :grinning:

2

I don’t know if you could do that are not (my intuition is no and/or it would be a bad idea if you could).

You can use pattern matching in Julia though.

  1. Match.jl provides a handy API for defining pattern matching rules
  2. Symbolics.jl uses Metatheroy.jl which uses a fast pattern matching algorithm as one component of what it does.
3

The idea works:

struct IntNotZero
	x::Int
end
struct IntZero
	x::Int
end

function myMod(a::IntNotZero,b::IntNotZero)
	if a.x==0 
		return IntZero(0)
	elseif mod(a.x,b.x)==0
		return IntZero(0)
	else
		return IntNotZero(mod(a.x,b.x))
	end	
end

gcd(a::IntNotZero,b::IntZero) = a
gcd(a::IntNotZero,b::IntNotZero) = gcd(b,myMod(a,b))

julia> gcd(IntNotZero(4),IntNotZero(8))
IntNotZero(4)

julia> gcd(IntNotZero(4),IntNotZero(10))
IntNotZero(2)

julia> gcd(IntNotZero(4),IntNotZero(7))
IntNotZero(1)

But of course per definition:

julia> @code_warntype myMod(IntNotZero(4),IntNotZero(7))
Variables
  #self#::Core.Const(myMod)
  a::IntNotZero
  b::IntNotZero

Body::Union{IntNotZero, IntZero}
1 ─ %1  = Base.getproperty(a, :x)::Int64
│   %2  = (%1 == 0)::Bool
└──       goto #3 if not %2
2 ─ %4  = Main.IntZero(0)::Core.Const(IntZero(0))
└──       return %4
3 ─ %6  = Base.getproperty(a, :x)::Int64
│   %7  = Base.getproperty(b, :x)::Int64
│   %8  = Main.mod(%6, %7)::Int64
│   %9  = (%8 == 0)::Bool
└──       goto #5 if not %9
4 ─ %11 = Main.IntZero(0)::Core.Const(IntZero(0))
└──       return %11
5 ─ %13 = Base.getproperty(a, :x)::Int64
│   %14 = Base.getproperty(b, :x)::Int64
│   %15 = Main.mod(%13, %14)::Int64
│   %16 = Main.IntNotZero(%15)::IntNotZero
└──       return %16

Ok, red part isn’t visible.
The expected result is a type instability in myMod, which, in general isn’t very welcome in julia :wink:

1 Like
4

You can push values into type domain:

julia> gcd(::Val{a}, ::Val{b}) where {a, b} = gcd(Val(b), Val(mod(a, b)))
julia> gcd(::Val{a}, ::Val{0}) where {a} = Val(a)

julia> gcd(Val(5), Val(20))
Val{5}()
4 Likes
5

Oh wow. :smiley: Yes, that’s exactly the kind of thing I was wondering about.

:thinking: Now I just need to work out exactly what you’ve done here - I haven’t been able to penetrate the documentation on type restrictions very well yet.

Thanks for the food for thought!

6

The downside of this is that Julia compiles a new version of your function for each value you pass, which produces highly optimized code for that value but has a lot of compiler overhead. It doesn’t really make sense to do this for something like gcd.

4 Likes
8

I hope it is clear that this is just fun and not something which should be really done like this (Val or Types doesn’t matter). It will get clunky really fast.

Isn’t Prolog or Erlang better suited for problems like this?

Another attempt in julia can be perhaps some kind of DSL (domain specific language) but I don’t know much about this.

9

:grinning: Oh yes, I’m aware of that. I’m just kind of musing out loud. I’m thinking that the dispatcher is using some form of backtracking, which is the basis of the resolution logic in Prolog, and it struck me that that could make it possible to set up rulebases, or maybe even the high-performance pattern-matching of Mathematica.

As for whether it should be really done like this, I think that’s more a question of whether the idea fits the Julia compiler. If it does, that’d be an interesting new way of using it, but I must admit that converting every integer into a new type is probably not exactly what I had intended! :wink:

2 Likes
10

could we have

@pattern_match begin
gcd(a,0) = a
gcd(a,b) = gcd(b,mod(a,b))
end

macroexpand to

function gcd(a,b)
    if b == 0
        a
    else
        gcd(b,mod(a,b))
    end
end

?

11

That is

https://thautwarm.github.io/MLStyle.jl/latest/syntax/pattern.html

5 Likes
12

Thanks!

using MLStyle

_gcd(a, b) = @match (a, b) begin
    (a, 0) => a;
    (a, b) => _gcd(b,mod(a,b));

end

_gcd(12, 15)
# 3
6 Likes