Languages: Logic

We have been ignoring a big aspect of what happens in a programming language: programmers express the logic of whatever they need done.

Languages: Logic

We have seen the basics built from expressions (in most languages) and statements (in most languages we know except Haskell). Those can be combined in functions (or similar).

But let's look a little closer at control flow: the stuff that was loops and conditionals in CMPT 120.

Conditionals

The tool we reach for the most often for conditional code: the if statement.

You've probably also seen a switch/case, and probably think of it working like in C: with an equality comparison for each case (and maybe a default).

std::string number_word(int n) {
    std::string result;
    switch( n ) {
        case 1: result = "one"; break;
        case 2: result = "two"; break;
        default: result = std::to_string(n); break;
    }
    return result;
}

Conditionals

We have also seen Haskell's case that uses its pattern matching to choose the applicable case.

describeList :: [Int] -> String
describeList values = case values of
    []     -> "empty list"
    [0]    -> "just a zero"
    [_]    -> "single element"
    [_, _] -> "two elements"
    _      -> "unremarkable"

That's more flexible (assuming a language with interesting pattern matching).

Conditionals

Python introduced pattern matching in 3.10 (released 2021) that can be used with its match/case, and it feels similar to Haskell:

match some_list:
    case []:
        print("empty list")
    case [0]:
        print("just a zero")
    case [n]:
        print(f"single element {n}")
    case [_,_] | [_,_,_]:
        print(f"two or three elements")
    case lst:
        print(f"unremarkable list {lst}")

Conditionals

You can pattern match very flexibly around a class and it can make quite nice-looking code.

@dataclasses.dataclass
class Person:
    first: str
    last: str

p = Person("Brian", "Fraser")
match p:
    case Person("Simon", "Fraser"):
        print("university namesake")
    case Person(last="Fraser", first=first):
        print(f"maybe a relative named {first}?")
    case p:
        print(f"rando named {p.first}")

Conditionals

Rust also has pattern matching semantics in its match and if/let blocks.

Have a look at your favourite language: are there non-if ways to express conditionals that would fit better in certain circumstances? Use them where it would make your code more beautiful/expressive.

Iteration

You're likely used to iteration in a programming language coming from loops: for, while, an friends.

You also knew that iteration can be done with recursion.

Iteration

With Haskell, we met several ways to iteration without loops (which I called implicit loops for lack of a universal term).

-- combine values with an operation and accumulator
mySum :: (Num a) => [a] -> a
mySum values = foldl (+) 0 values

-- process values and aggregate
halfOfEvens :: (Integral a) => [a] -> a
halfOfEvens values = foldl (+) 0
    $ map (`div` 2) $ filter even values
halfOfEvens' :: (Integral a) => [a] -> a
halfOfEvens' values = foldl (+) 0 
    $ [n `div` 2 | n <- values, even n]

Iteration

Many languages have analogous tools you can reach for. They are often more beautiful and clear than a manual loop. In many languages they produce solutions with similar or better performance.

You don't have to write C from 1972 spelled with a different language's syntax.

Iteration

In Python the list-indexing for loop (i.e. the C programmer's solution spelled with Python syntax) takes 6.8 s on a large list:

def half_of_evens_index(values: list[int]) -> int:
    acc = 0
    for i in range(len(values)):
        v = values[i]
        if v % 2 == 0:
            acc += v // 2
    return acc

Iteration

Just realizing that Python's for is actually a for each gets the time down to 4.9 s:

def half_of_evens_foreach(values: Iterable[int]) -> int:
    acc = 0
    for v in values:
        if v % 2 == 0:
            acc += v // 2
    return acc

Iteration

But knowing Python's comprehension syntax does the job in 4.4 s:

def half_of_evens_comprehension(values: Iterable[int]) -> int:
    return sum(v // 2 for v in values if v % 2 == 0)

… and I'd argue is more beautiful and easier to understand.

Iteration

Python's map and filter can produce nice code, but are slower in this case: they incur the cost of function calls many times, taking 8.2 s:

def half_of_evens_mapfilter(values: Iterable[int]) -> int:
    result = map(
        lambda v: v // 2,
        filter(lambda v: v % 2 == 0, values)
    )
    return sum(result)

Iteration

In C#, there seems to be a slight speed penalty to LINQ (at least here). On a large List<long>, this took 7.6 s:

long total = values
    .Where(v => v % 2 == 0)
    .Select(v => v / 2)
    .Aggregate(0L, (acc, v) => acc + v);  // or .Sum()

This took 5.5 s:

long total = 0;
foreach (long v in values) {
    if (v % 2 == 0) {
        total += v / 2;
    }
}

Iteration

An indexed for loop took 5.5 s: the C# and/or .NET tools seem to optimize old-fashioned code styles (today).

long total = 0;
for (int i=0; i < values.Count; i++) {
    long v = values[i];
    if (v % 2 == 0) {
        total += v / 2;
    }
}
return total;

I'd argue that the LINQ solution is better in all but the most-performance-critical code: it's so much easier to read and understand.

Iteration

Here are a bunch of C++ equivalents, each take exactly the same amount of time (compiled g++ -O2 -std=c++23 -march=native).

C-style, pretending vectors are just fancy arrays:

long half_of_evens_index(std::vector<long> &values) {
    long acc = 0;
    for (size_t i = 0; i < values.size(); i++) {
        long v = values[i];
        if (v % 2 == 0) {
            acc += v / 2;
        }
    }
    return acc;
}

Iteration

A little more C++-style, using an iterator in the for loop:

long half_of_evens_foriter(std::vector<long> &values) {
    long acc = 0;
    for (auto itr=values.cbegin(); itr!=values.cend(); itr++) {
        long v = *itr;
        if (v % 2 == 0) {
            acc += v / 2;
        }
    }
    return acc;
}

Iteration

The C++ for-each loop:

long half_of_evens_foreach(std::vector<long> &values) {
    long acc = 0;
    for (auto v : values) {
        if (v % 2 == 0) {
            acc += v / 2;
        }
    }
    return acc;
}

Iteration

In C++20 (some C++23?) you can write very functional-like thoughts with C++ syntax that I'm not particularly fond of:

long half_of_evens_views(std::vector<long> &values) {
    auto half_of_evens = values
    | std::views::filter([](long v) { return v % 2 == 0; })
    | std::views::transform([](long v) { return v / 2; });
    return std::ranges::fold_left(
        half_of_evens,
        0,
        [](long a, long b) { return a + b; });
}

The [](args){ body } is a C++ lambda expression.

Iteration

Or not piping between views, if that feels more clear to you:

long half_of_evens_views2(std::vector<long> &values) {
    auto only_evens = std::views::filter(values, 
        [](long v) { return v % 2 == 0; });
    auto half_of = std::views::transform(only_evens,
        [](long v) { return v / 2; });
    return std::reduce(
        half_of.cbegin(), half_of.cend(), 0L,
        [](long a, long b) { return a + b; }
    );
}

Iteration

Or if we're okay with modifying the vector, we can:

long half_of_evens_vecmodify(std::vector<long> &values) {
    // destructive: modifies values
    std::erase_if(values, [](long v) { return v % 2 != 0; });
    return std::ranges::fold_left(
        values,
        0,
        [](long a, long b) { return a + b/2; });
}

Slightly different performance: it's doing a different thing than the others.

Iteration

Remember: in this test at least, all of these had identical performance. Choose the one that you think is most readable.

Compiling with -O3 leaves the ranges/views implementation notably slower: likely the compilers haven't fully sorted out how to handle these tools.

Iteration

Equivalent code in Rust, again with all-identical performance. The C-style indexing for loop:

pub fn half_of_evens_forindex(values: &Vec<i64>) -> i64 {
    let mut acc = 0;
    for i in 0..values.len() {
        let v = values[i];
        if v % 2 == 0 {
            acc += v / 2;
        }
    }
    acc
}

Iteration

A for-each loop:

pub fn half_of_evens_foreach(values: &Vec<i64>) -> i64 {
    let mut acc = 0;
    for v in values {
        if v % 2 == 0 {
            acc += v / 2;
        }
    }
    acc
}

Iteration

Using an iterator over the values:

pub fn half_of_evens_iter(values: &Vec<i64>) -> i64 {
    values.iter()
        .filter(|&v| v % 2 == 0)
        .map(|v| v / 2)
        .fold(0, |acc, v| acc + v)  // or .sum()
}

I think the Rust syntax makes this more beautiful than the explicitly-looping versions.

Iteration

Here's a version that's several times faster:

pub fn half_of_evens_pariter(values: &Vec<i64>) -> i64 {
    values.par_iter()
        .filter(|&v| v % 2 == 0)
        .map(|v| v / 2)
        .sum()
}

The difference: .iter() became Rayon's .par_iter() and it used all of my CPU cores.

Algorithms

Even better than simplifying your loop: don't write one because you're just calling a more general algorithm implementation that does the job.

Algorithms

Sean Parent's suggestion: don't write raw loops. Basically, either write a function that implements a relatively general algorithm, or don't use loops and only call more general algorithm implementations.

If you're going to follow that advice, I see two options: write the general algorithm, or find an existing implementation in a library. Then call it.

Algorithms

Relative to a solution you would create, a library function is probably some of:

faster,
more correct,
more robust,
works on more general data types,
evaluatable at compile-time (constexpr in C++, const in Rust).

Algorithms

Some examples in Python:

bisect: generalized binary-searches;
heapq: heap queue algorithm;
itertools.groupby: aggregate on identical keys;
itertools.product, .permutations, .combinations: various combinatorial things;
pip-installable: NetworkX graph algorithms, PyParsing for parsing strings, SymPy for symbolic math.

Algorithms

In C++:

<algorithm> any_of, find_if, count_if, is_permutation, swap_ranges, is_sorted, merge, make_heap, … .
<queue>, <list>, <numeric>, … .

Algorithms

In Rust:

std::collections containers and their methods, e.g. on a Vec or array .binary_search, .contains, .dedup, .retain, .sort, … .
std::iter::Iterator to allow manipulation of elements from any iterable source.
Popular crates: priority_queue, itertools, petgraph graph algorithms, Rayon for data-parallelism, … .

Summary

A lot of programming introductions/textbooks guide you to express logic like languages required 30 or 40 years ago. That code still works because programmers demand compatibility, and its occasionally better/clearer/necessary.

But the abstrations it presents (e.g. arrays are the only data structure; do exactly one thing at a time, sequentially across all elements) isn't always what you need done.

Summary

There are many other ways to express even very basic ideas in many programming languages.

There are also many tools available to let you not have to do it yourself.

Know them, and use them when it makes your code more clear.