Single-Assignment C

http://www.sac-home.org/doku.php

by lelf • 7 years ago

91 43 7 years ago

sac-home.org

dang2• 7 years ago

Related from 2013: https://news.ycombinator.com/item?id=6949525

jagged-chisel• 7 years ago

I think you mean 2013

dang2• 7 years ago

Ah yes. Thanks! Fixed.

coldtea2• 7 years ago

  p = p + v * dt;
  v = v + a * dt;

How is this "single assignment"? Aren't v and p assigned values already before those lines? Or do they have some default initial value for their type that doesn't count as an assignment?

Arnavion• 7 years ago

It's not C, but a new language with similar syntax. Based on reading the docs at [1], the assignment is sugar for generating a new binding for the result of that expression that shadows the previous one.

[1] http://www.sac-home.org/doku.php?id=about:core

nwallin2• 7 years ago

I don't understand.

What does the "single assignment" bit get you that a compiler with an SSA pass doesn't?

seanmcdirmid• 7 years ago

Maybe it’s short for:

    p[t+dt] = p[t]+v[t]*dt
    v[t+dt] = v[t]+a[t]*dt

?

slavik81• 7 years ago

As an aside,

  v = v + a * dt;
  p = p + v * dt;

is typically more accurate. The first form is Forward Euler integration [1], while my suggestion is Semi-implicit Euler [2].

[1] https://en.wikipedia.org/wiki/Euler_method [2]: https://en.wikipedia.org/wiki/Semi-implicit_Euler_method

WalterBright2• 7 years ago

I thought this was about adopting a programming style where each variable is assigned to only once. But it was something else entirely.

I was interested because I've started adopting the single assignment style in my own code, and like the results (the code is easier to comprehend).

glouwbug• 7 years ago

Agreed, I'm currently taking a similar approach, but forgoing pointers as much as possible as well. This leads to structs being passed by value, and const abuse.

    Ray h_cast(const Hero hero, const Hit hit, const Sheer sheer, const int yres, const int xres)
    {
        const Point end = p_sub(hit.where, hero.where);
        const Point corrected = p_turn(end, -hero.yaw);
        const Line trace = { hero.where, hit.where };
        const Projection projection = p_project(yres, xres, hero.fov.a.x, hero.pitch, corrected, hero.height);
        const Ray ray = { trace, corrected, p_sheer(projection, sheer), hit.surface, hit.offset, hero.torch };
        return ray;
    }

It leads to some nice somewhat functional styles. I estimate its 80% pure, given its C99 alone. I've adopted this style in my Age of Empires 2 engine rewrite if anyone is curious: https://github.com/glouw/openempires

As for performance I am heavily relying on LTO. I seem to get a 50% performance boost with pass by values on structs - as I've sedded openempires to replace occurrences of _Type name_ with C++'s _Type& name_ for all functions arguments - and the added pointer aliasing and de-references bogged the engine down in heavily forested areas.

Compilers love singly assigned const values, and seem to suffer under heavy pointer aliasing.

saagarjha• 7 years ago

I've sedded openempires to replace occurrences of _Type name_ with C++'s _Type& name_ for all functions arguments

This isn’t a valid transformation :/

Compilers love singly assigned const values

I mean, they’re going to convert to SSA for you anyways.

and seem to suffer under heavy pointer aliasing

Have you tried restrict?

voldacar• 7 years ago

This leads to structs being passed by value

do compilers generally optimize this away on -O3, or do you just accept the performance hit in exchange for prettier code?

ternaryoperator2• 7 years ago

I was interested because I've started adopting the single assignment style in my own code

What benefit have you seen from doing this? Genuinely curious.

guerrilla2• 7 years ago

It's easier for compilers to optimize. https://en.wikipedia.org/wiki/Static_single_assignment_form

WalterBright2• 7 years ago

It does have some positive consequences for optimization. For example, if you "recycle" local variables by using them again for different purposes, you might think you're saving stack space by sharing the space. You're not. Optimizers are pretty good at storing multiple variables in the same stack slot when their usages (i.e. "live ranges") are disjoint.

On the other hand, if you write:

    int i = value;
    ... use i ...
    ... lots of code ...
    i = another value;
    ... use i ...

the optimizer may not be smart enough to split this into two distinct variables, unless it does the SSA optimization. Hence, you'll lose the optimization where in [... lots of code ...] i will not be occupying a register.

But just for code comprehension, it is better to use different variables for disjoint uses. A related point is to "shrink wrap" a variable into the smallest scope you can. The less you have to look over the rest of the function for uses, the better.

And lastly,

    int x = value;
    if (condition) x = another;

is just better written as:

    const int x = condition ? value : another;

It reads better, and it enables x to be const, which is always better.

Animats• 7 years ago

That's what I thought, too.

There's a lot to be said for real single-assignment programming. It provides many of the advantages of functional programming. The code is more readable, because the intermediate variables have names. When you need to do something imperative, you don't have to jump through hoops to do it. Go and Rust both encourage that style - the default is to create a new variable, not assign to an old one. (The semantics of multiple := assignment in Go, where some variables are assigned and others are created, though...)

One of the historical headaches of C is that function parameters are non-const by-value by default. That's backwards. The default should be const ref. If you need a local mutable copy, or the parameter is an "in-out", as Ada calls it, you should have to specify that. Those are the less likely cases and the ones that cause trouble if missed. Passing small const ref values by value is a compiler optimization; the programmer shouldn't have to worry about it, especially since whether it's a win varies with the target machine.

The language in the article seems more like a variant of Matlab, not C.

wirrbel• 7 years ago

Single assignment style has structural similarities to continuation-passing style in FP iirc.

johnthescott• 7 years ago

i recall a micro language built around the infamous brainfuck that has a non destructive read for function arguments. seems like a bigger concept exists. let the caller determine what the called can modify.

kick3• 7 years ago

This is interesting; I just investigated SAC for the first time about seven hours ago (I actually posted a license-fragment from it on my social media account: https://blob.cat/notice/9qMowPTjR9F7fjid3Q), finding it technically impressive but unfortunately proprietary.

Was there news about it, or something? It came to mind because something I was wanting to try depended on it, and it doesn't get posted to HN very often, so I'm really curious as to how you found it.

Athas2• 7 years ago

What did you find that depends on SaC?

kick3• 7 years ago

An ancient APL compiler, unfortunately. A really cool one, too!

HeraldEmbar• 7 years ago

The home page is fairly free of any details about SaC, though I do now know an awfully lot about who is involved. Also, there's no reference manual.

Where can I find a tutorial, examples, or any concrete details?

antonvs• 7 years ago

There's a docs page linked from the home page with a tutorial and various other docs:

http://www.sac-home.org/doku.php?id=docs:main

Single-Assignment C

Related Stories