# Pattern-based programming

**URL:** <https://discourse.julialang.org/t/pattern-based-programming/73493>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [December 22, 2021, 2:49pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493 "2021-12-22T14:49:44Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Niall](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/niall/32/22517_2.png) [@Niall](https://discourse.julialang.org/u/Niall)\
**Post date:** [December 22, 2021, 2:49pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/1 "2021-12-22T14:49:44Z")

</div>

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:

```julia
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. 😀

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [December 22, 2021, 3:03pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/2 "2021-12-22T15:03:40Z")

</div>

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](https://kmsquire.github.io/Match.jl/latest/) provides a handy API for defining pattern matching rules
2. [Symbolics.jl](https://github.com/JuliaSymbolics/Symbolics.jl) uses [Metatheroy.jl](https://github.com/JuliaSymbolics/Metatheory.jl) which uses a fast pattern matching algorithm as one component of what it does.

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [December 22, 2021, 3:33pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/3 "2021-12-22T15:33:35Z")

</div>

The idea works:

```julia
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
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
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 😉

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [December 22, 2021, 4:39pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/4 "2021-12-22T16:39:04Z")

</div>

You can push values into type domain:

```julia
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}()

```

---

<div class="post-metadata">

**Author:** ![Niall](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/niall/32/22517_2.png) [@Niall](https://discourse.julialang.org/u/Niall)\
**Post date:** [December 22, 2021, 5:00pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/5 "2021-12-22T17:00:25Z")

</div>

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

🤔 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!

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [December 22, 2021, 5:30pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/6 "2021-12-22T17:30:08Z")

</div>

> [@aplavin](#):
>
> You can push values into type domain:

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`.

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [December 22, 2021, 5:50pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/8 "2021-12-22T17:50:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Niall](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/niall/32/22517_2.png) [@Niall](https://discourse.julialang.org/u/Niall)\
**Post date:** [December 22, 2021, 6:05pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/9 "2021-12-22T18:05:57Z")

</div>

😀 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! 😉

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [December 22, 2021, 8:00pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/10 "2021-12-22T20:00:53Z")

</div>

could we have

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

```

macroexpand to

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

```

?

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [December 22, 2021, 10:11pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/11 "2021-12-22T22:11:20Z")

</div>

That is

[https://thautwarm.github.io/MLStyle.jl/latest/syntax/pattern.html](https://thautwarm.github.io/MLStyle.jl/latest/syntax/pattern.html)

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [December 22, 2021, 10:33pm UTC](https://discourse.julialang.org/t/pattern-based-programming/73493/12 "2021-12-22T22:33:56Z")

</div>

Thanks!

```julia
using MLStyle

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

end

_gcd(12, 15)
# 3

```