A case/switch statement for Julia

[bpr]

Proposal

This is a Julep suggested by @StefanKarpinski during this julia-users group discussion.

Julia lacks a C-style switch statement. This issue has come up before on various fora. Unsurprisingly, Julia also lacks pattern matching, a useful generalization of case and switch, which has been implemented as a macro for Julia.

This proposal is concerned with using switch statements over integral (isbits) types to exploit the ability of LLVM's switch instruction to provide a branch table implementation of switch, which is more performant than a sequence of if-else conditionals. It should be amenable to supporting extended switch and pattern capabilities in the future; for that reason I'll suggest using adding the case keyword to introduce the form. If it's desired that the statement only be used as a C style switch and that pattern matching be introduced separately, perhaps switch is the better choice.

I'll skip the arguments in around whether to include such a feature at all; interested readers can review some of those arguments in the context of Python or Lua, as the arguments on both sides would be similar for Julia.

Syntax

If we'd like to subsume this in a future pattern matching Julia extension, I suggest a syntax influenced by the Match.jl macro, replacing @match with the keyword case, and adding a new keyword of to use instead of begin. I chose of because that's used in many other languages that use case, and because Julia constructs like if/for/while don't require a begin for their end (Objection sustained).

case case_expr
    case0 => expr0
    case1 => expr1
    .
    .
    .
    caseNMinusOne => exprNMinusOne
    else => exprN
end

The optional else at the end could be replaced by _ or even otherwise or default, at the cost of using more keywords.

Each case above could be preceded by an of if that syntax is preferable. It strikes me as a little wordy but it's a syntax used in other languages and perhaps people find it more readable.

case case_expr
    of case0 => expr0
    of case1 => expr1
    .
    .
    .
    of caseNMinusOne => exprNMinusOne
    else => exprN
end

Examples

n = rand(0:32)
function print_if_lt_3(n)
    case n
        0 => println("zero")
        1 => println("one")
        2 => println("two")
        else => println("too big")
    end
end

Should be semantically equivalent to

n = rand(0:32)
function print_if_lt_3(n)
    if n == 0 
        println("zero")
    elseif n == 1
        println("one")
    elseif n == 2
        println("two")
    else
        println("too big")
    end
end

An example with enums

@enum Dir north northeast east southeast south southwest west northwest
function degree_of_dir(d)
    case d
        north => 90
        northeast => 45
        east => 0
        southeast => 315
        south => 270
        southwest => 225
        west => 180
        northwest => 135
    end
end

The intent is that @enum should work well with this case statement, which means that the conversion to the enum's Int value should be implicit, as above.

[yuyichao]

Dup of #5410

[vchuravy]

@bpr It seems that there is agreement that we should have a switch statement and your proposal seems valid, but to make it happen it would be best to have a PR implementing the proposal.

[timholy]

I'm not certain how I feel about adding case: I'd like to get a sense for the potential performance advantages for "real world code," since I think the syntactic gains are relatively modest.

But either way I'd like to point out that this is a well-written, well-researched, and well-balanced proposal. I'd like to argue for reopening this and closing #5410, since this contains many things that are not in #5410 (an explicit API proposal and quite a few helpful links, including to #5410). Closing this effectively discards all of the careful work behind this.

[KristofferC]

+1 On opening this and closing #5410.

I have seen case used in binary search code to unroll the search when the range is small enough but I don't really know the performance impact.

[yuyichao]

The proposal here should just be copied to #5410 , this does summarize some pieced from #5410 but we should put all the discussion on a same issue and not opening a new one every time someone come up with this.

[yuyichao]

Also, please use ``` for quoting code instead of **, especially for macros.

[yuyichao]

As @timholy said, the proposal here also doesn't address, IMHO, the most important issue for #5410, i.e. how should this be related to LLVM switch instruction.

The LLVM switch instruction / C switch statement is really limited in terms of what is acceptable as the target value (constants), which is much more restricted than what's usually presented in high level languages AFAIK. Since the proposal mentions that

It should be amenable to supporting extended switch and pattern capabilities in the future

I expect that the julia switch statement proposed here shouldn't have the LLVM restriction and it'll have to be purely a syntax sugar for a list of if as already provided by packages using macros and the lowering to LLVM switch statement has to be done via optimization and it doesn't matter if we have a special syntax or not. I'll be a little surprised if LLVM doesn't already have a pass to do this.

Also worth noting that

Julia lacks a C-style switch statement. This issue has come up before on various fora. Unsurprisingly, Julia also lacks pattern matching, a useful generalization of case and switch, which has been implemented as a macro for Julia.

Isn't accurate. The syntax can be / is already implemented nicely as macros and unless there's something we can't do with macros, e.g. if we want to have special lowering for it (directly to a switch statement with LLVM restriction) or if we want to allow special handling at surface syntax level (like @simd/@thread/@parallel for), we don't really need to give it a special syntax.

[JeffBezanson]

LLVM does (or did) have a pass to convert a sequence of integer comparisons to a jump table. I remember seeing this work at some point, but the optimization has come and gone as LLVM has changed. I haven't looked for this in a while; we should see if it's working currently.

[carlobaldassi]

Regarding the proposed syntax, I don't see why the of keyword would be needed at all. It seems to me that this could be parsed without any particular issues:

case n
    0 => println("zero")
    1 => println("one")
    2 => println("two")
    else => println("too big")
end

[eschnett]

A switch-like statement enriches the language that a programmer can use. If there is already a pass that converts a series of elseif statements to a LLVM switch statement, then we can ignore this part in the discussion here, and concentrate on the advantages we get at the language or syntactic level.

• often more concise than an elseif sequence
• can ensure there are no duplicates, or no overlapping ranges
• can ensure all cases are handled, in particular for enums
• can implicitly produce an error if a case isn't handled, without having to explicitly call throw
• can be extended to handle types, not just integer-like values; type inference can be taught about this

Some of these are difficult to implement via macros. (And for the sake of the discussion here, it doesn't really matter whether one writes case or @case in the beginning.)

[bpr]

@yuyichao Sorry I didn't continue #5410, I had an email exchange with @StefanKarpinski in which I'd referenced that issue, and he replied that the best way to get something like this in the next Julia is to write a Julep and once that's accepted a PR.

The reason I put the LLVM restriction in there is that my reading of the previous threads and investigation into the issue revealed that the LLVM does not provide this optimization currently. I reran @stevengj 's experiment and I get a sequence of comparisons.

As I mentioned, the main point of this proposal is to provide a high level syntax for Julia to access LLVM's switch instruction. I suppose in a future language spec it can spell out that the construct has to implement the branch over a restricted set via some kind of O(1) structure.

@timholy That's a good point, some performance experiments are really necessary to strengthen the argument for inclusion.

@carlobaldassi Syntax bikeshedding is great fun! But seriously, I'm not married to any particular syntax, but hopefully whatever is chosen looks like Julia.

@eschnett I completely agree that a switch like statement enhances the language, as does pattern matching.

[yuyichao]

he replied that the best way to get something like this in the next Julia is to write a Julep and once that's accepted a PR.

You should mention that or briefly explain why a dup is necessary. Otherwise, closing duplicated issue is the default. IMHO a good proposal fits well in the comment of existing issue, especially since the original issue isn't too long to read through, unlike, e.g. JuliaLang/LinearAlgebra.jl#42.

[eschnett]

@yuyichao I think you are accidentally mis-reading my arguments as if I suggested to not use a macro. Instead, I am making an argument comparing a switch statement to a hand-written if-elseif sequence, and list some benefits of the latter, at the language level.

[StefanKarpinski]

@yuyichao, Since this is intended as a Julep, having a separate issue about a specific proposal seems appropriate to me. A single long, impossible to follow thread on every subject isn't optimal.

I like the proposed syntax – specifically @carlobaldassi's variant of it without the of keyword. As @eschnett points out, the semantic benefits are entirely orthogonal to the potential performance benefits (which are largely a detail of the underlying compiler).

[yuyichao]

In that case 👎 for adding the syntax since AFAICT there isn't a benefit for having it as a syntax instead of a macro.

[StefanKarpinski]

Aside from the five things that @eschnett listed.

[yuyichao]

Aside from the five things that @eschnett listed.

No. Pasting back my comment from #5410 with slight modifications / typo fixes. Basically all of those are benefits of macro or syntax over elseif sequence, not macro over syntax.

often more concise than an elseif sequence

Can be handled with macro.

can ensure there are no duplicates, or no overlapping ranges

Can also be handled with macro. Having a syntax doesn't help. Will likely have runtime overhead unless we restrict the condition to constant. And this behavior may not be wanted.

can ensure all cases are handled, in particular for enums

Can be handled with macro.

can implicitly produce an error if a case isn't handled, without having to explicitly call throw

Can be handled with macro.

can be extended to handle types, not just integer-like values; type inference can be taught about this

Lowering to elseif in a macro can trivially handle this. Type inference doesn't need to know anything special about it.

[bpr]

While my quick experiments with clang++ didn't show a significant performance win for
LLVM's switch, it's not absurd to assume that there may be alternative Julia backends in the future (C, WebAssembly, whatever) and some of those backends may provide some branch table or switch primitive. Web Assembly does. If we assume that Julia will not do the transformation of if-then sequences to branch tables, then a macro will not be able to do what a core language feature can.

I suppose similar questions will come up as new LLVM features are added. I just noticed that LLVM 4.0 has coroutines; I bet in a few years we'll want to see Julia able to access those LLVM intrinsics too!

[yuyichao]

If we assume that Julia will not do the transformation of if-then sequences to branch tables, then a macro will not be able to do what a core language feature can.

Yes, this is the single difference between a language level construction and a macro. However, the question is still that do we want to have the same set of restrictions as such low level features (i.e. guaranteed constants, bitstype, and probably more).

Everyone who have commented so far (you included) seems to think that we don't want to have such restrictions. Given that, an optimization pass seems to be the way to go if we've identified cases where such transformation can lead to higher performance and if it is not done by llvm automatically.

[denius]

Are there possible any variants with ranges or intervals:

@enum Dir north northeast east southeast south southwest west northwest
function to_north(d)
    case d of
        east:west => false
        else => true
    end
end

or next one

function to_north(d)
    case d of
        east <= _ <= west => false
        else => true
    end
end

The current Match.jl syntax for ranges with if and end is very ugly, especially with built-in Enums.

[be5invis]

But... Isn’t this being better and more Mathematical?

abstract Term
immutable Free <: Term
    name :: String
end
immutable Lam <: Term # HOAS
    fn :: Function    # String -> Term
end
immutable App <: Term
    fn  :: Term
    arg :: Term
end

# CBV normalization
normalize(n' = Free(n)) = n'
normalize(f' = Lam(f)) = f'
normalize(App(f, x)) = apply(context, normalize(f), (x)) where
    apply(Lam(f), x) = normalize(f(x))
end

normalize(App(Lam(x -> x), Free('a'))) # ==> Free('a')

[thautwarm]

FYI, a sufficiently efficient pattern matching has been implemented by MLStyle.jl which could be 20+ times faster than Match.jl, and the benchmark script is provided at the root dir of project.
In fact, I doubt that MLStyle.jl could always generate faster codes than humans' handwritten.
I'll make benchmarks about the performance of the handwritten and the MLStyle.jl generated.

[thautwarm]

@yuyichao Achieving this via macros cannot be always sufficient.
Thank about a case expression combined with others, the associativity could be an issue:

1 + @case begin
        a => b
       ...
end  + 1

[yuyichao]

How is this @case specific? You can easily fix that with parentheses. And if you want you can even pick a syntax that requires parentheses or even multiple syntax similar to if.

[thautwarm]

Well, if you feel okay with adding parentheses.

P.S: Picking a syntax like if wouldn't help at all, macros just break the associativity.

[yuyichao]

Well, if you feel okay with adding parentheses.

This is the estabilished solution for exactly this kind of problem for all macros.

P.S: Picking a syntax like if wouldn't help at all, macros just break the associativity.

By picking multiple syntaxes similar to if I mean having, well, multiple syntaxes depending on the usecase, i.e. ?: or if else end, one of them clearly is more intended for "expression" while the other is more intended for "statement". One of them naturally fits looks better with parenthesis than the other one. Obviously you can't just take that syntax.

[thautwarm]

This is the estabilished solution for exactly this kind of problem for all macros.

My point is for pattern matching is super useful for some domains, it's worthwhile to make it a special macro. I mean that we can provide macros for pattern matching in standard library and just transform Expr(:case,...) into corresponding macrocalls.

By picking multiple syntaxes similar to if I mean having ....

Thanks for reminding me of some useful notations. Now I have a better idea to bring pattern matching into Julia than using something like @match.

[thautwarm]

Now I'm too excited to fall into sleep!!!

@allowpattern module M
case(target) do
     pat1 => body1
     pat2  => body2
     ...
end
end

[o314]

Hello Julia syntax extenders,

To whom it may concern, i suggest you to read extension points, or how ocaml is becoming more like lisp that relates a same story that has occured with ocaml few years ago.

[...]
OCaml’s syntax, on the other hand, is very specific and inflexible. It lets you parse OCaml’s syntax exactly, and any deviation is flagged as a syntax error. Almost any interesting syntax extension will require parsing programs that are not syntactically valid OCaml programs.

That’s where extension points come in. Extension points are a collection of extensions to OCaml’s grammar that adds a notation for annotations. With these annotations, OCaml’s syntax becomes general enough to accommodate many different syntax extensions. Indeed, Alain Frisch, who is the main author and advocate of this change, organized a survey of existing camlp4-based syntax extensions, and made sure that extension points were rich enough to accommodate them.

OCaml now has a very clever and powerful mechanism, OCaml syntax extensions that allows to create, combine, update, extend a fully featured set of syntax enhancement ...

[ghost]

@thautwarm

1 + @case begin
        a => b
       ...
end  + 1

Can macros pick up their arguments from multiple lines? If not, that would be an interesting addition and will allow macro uses to be formatted nicely.
Macros with variable number of arguments could be handled with parentheses or backslashes before newlines.

[cmcaine]

Macros don't see whitespace, they see the AST. The details are in the Julia manual under "Metaprogramming". Ask on slack if you need a hand.

[norru]

Sorry, newbie to Julia here. Does it mean that I have to always install the Match package? I can't imagine a scenario where I would not use it.

it's surprising that such a useful feature requires an external package.

[yuyichao]

I can't imagine a scenario where I would not use it.

Given that it's not used in Base and it's not a dependency of every single packages out there I'd say it's actually very easy to imagine.

it's surprising that such a useful feature requires an external package.

There's nothing wrong with "external packages". I'm pretty sure many "useful" features are in "external packages". There's nothing hard about using an external packages so if you really can't imagine yourself ever not using it installing is a very easy solution. If anything, that is indeed something you should get used to as "newbie to Julia". Here, being in an external package doesn't mean it's not useful, it just mean a combination of not needed in Base and doesn't have to be in Base.

Also, if out of the several proposed macro syntax and semantics Match is indeed what everyone agrees on, there's no problem moving Match into stdlib. (I did not check if it is already).

[o314]

Strongly guessing he was not talking about Base but about the parser / lowerer / interpreter / compiler etc.
So it's not only a Base concern, neitheir a package something somewhere one.

[yuyichao]

lowerer / interpreter / compiler etc.

Well, there's basically nothing other than syntax here. There's basically zero chance we'll have a syntax for a switch with C semantics without a deep overall change of the whole language. In no where else we expose a syntax anywhere closed to the level of a C switch.

I don't want to guess what he meant even though I believe he is implying that Match satisfies his need. However, as I believe I mentioned many times above, the only differenece base (which include everything in this repo, not just the Base module) can make is to provide a non-macro syntax. However, there are significant flexibility in terms of what that syntax should mean (equal or pattern matching, basically) so it doesn't make much sense for base to provide one when it can be implemented and is already implemented in a package.

By all mean, this is only a base vs package concern.

[suharizen]

@yuyichao should be an integral part of the language

[theAkito]

There's nothing wrong with "external packages".

I think, you never used JavaScript based apps. Each external dependency has a risk of breaking your whole application, especially if it is maintained by a single random person. Just spamming external dependencies into your project is extremely bad practice and design. ESPECIALLY if you are using a tiny lib, that only provides a switch statement.

https://www.zdnet.com/article/another-one-line-npm-package-breaks-the-javascript-ecosystem/
https://www.theregister.com/2016/03/23/npm_left_pad_chaos/
https://www.zdnet.com/article/disgruntled-developer-breaks-thousands-of-javascript-node-js-apps/

[thautwarm]

@theAkito

Just spamming external dependencies

I don't believe this is a proper statement for Julia.

[theAkito]

I don't believe this is a proper statement for Julia.

This isn't a proper statement for any language.

That said, before people start disliking a comment, how about they check its sources, themselves... I provided 3 links for 2 great breakdowns in external dependency madness. Those are only the biggest ones. There are way more than that, because apparently too many developers think, that they should import every oneliner fart, that exists on Github, instead of just writing that one line themselves.

Can anyone propose at least one rational argument against my reasoning?

[yuyichao]

Can anyone propose at least one rational argument against my reasoning?

Yes, above.

Also, if out of the several proposed macro syntax and semantics Match is indeed what everyone agrees on, there's no problem moving Match into stdlib. (I did not check if it is already).

So please read through the comments above and understand the difference between a language feature and stdlib as well as what's even possible first.

[thautwarm]

The reason why I said it's not proper to Julia is not due to:

That said, before people start disliking a comment, how about they check its sources, themselves...

The reason for small and separate packages for Julia is quite different from languages like JS. Julia is in some degree relying on this practice to ease issues like JIT startup. The good performance of a dynamic language does not come out of thin air, intergrating too many into one package or stdlib does has drawbacks(though greatly improved by Revise.jl).

There are way more than that, because apparently too many developers think, that they should import every oneliner fart, that exists on Github, instead of just writing that one line themselves.

It seems that you're quite negative about the how developers manage dependencies. However being negative does not mean this point of view is valid: Several scripting langauges similar to JS just like Python or Ruby, developers of which do not regularly create or import one-liner library, and sometimes even get crazy for reducing/cleaning the dependency.

Besides.

The 3 posts are not convincing in this scope:

One-liner library is more likely to be inlined and self-maintained in Julia community.
"Disgruntled developer" problem cannot be actually got rid of, because you've chosen working with open source world. Instead of getting rid of this problem, calling for more care about developers' mental health could be better.

[bpr]

Structural pattern matching, more like that found in ML or Erlang than a C-like switch, is being added to Python

https://www.python.org/dev/peps/pep-0636/#appendix-a

[PallHaraldsson]

if out of the several proposed macro syntax and semantics Match is indeed what everyone agrees on, there's no problem moving Match into stdlib. (I did not check if it is already).

It isn't, and should Match.jl be made a stdlib (sooner rather than later)? If it's trivial to do, is there an exception to be made for 1.7 (in case it ends up LTS), at least merge for 1.8 right away (if only done for 1.8 we could back out later)?

I see this was moved to 2.0 milestone, then back to 1.x, presumably because this doesn't need to be a breaking change, and I suppose than means in macro form rather than syntax.

Another possible change (alone) would be to recommend Match.jl in the docs. I tried to search for case/switch, and [pattern] matching and found nothing, at least not here:

https://docs.julialang.org/en/v1/manual/control-flow/

I see Match.jl is stable for several years now, so that doesn't seem like a hindrance.

FYI, a sufficiently efficient pattern matching has been implemented by MLStyle.jl which could be 20+ times faster than Match.jl

At least MLStyle has slower startup (while not bad). It's unclear to me if its "syntax"/"API" is better, and if we choose Match.jl over some other package, we've painted ourselves into a corner. Could MLStyle's "20+ times" faster code later by applied to Match?

[For Julia itself, I see plenty of elseif (that could have been @match, let alone all case/switch in C code), so pattern matching might also well be useful internally, one line some draw for inclusion. I'm not proposing changing old code in Base.]

[ARKAD97]

Well, you can just do it via short-circuit operators instead:

function print_if_lt_3(n)
    n == 0 && return println("zero")
    n == 1 && return println("one")
    n == 2 && return println("two")
    println("too big")
end

Same for enums:

function degree_of_dir(d)
    d == north && return 90
    d == northeast && return 45
    d == east && return 0
    d == southeast && return 315
    d == south && return 270
    d == southwest && return 225
    d == west && return 180
    d == northwest && return 135
end

Or more exotic, but little slower:

degree_of_dir2 = begin
    pattern = Dict(
        north => 90,
        northeast => 45,
        east => 0,
        southeast => 315,
        south => 270,
        southwest => 225,
        west => 180,
        northwest => 135
    )
    (d) -> pattern[d]
end

No elseifs

Though it might be useful to do some clever pattern matching, but in my opinion simple C-style switch case syntax doesn't worth it while you can just use short circuits