LWN: Comments on "A look at two new languages: Vala and Clojure"

Transactional Memory does not require functional languages

j1m+5n0w — Wed, 17 Jun 2009 06:53:42 +0000

Very true, there's no technical reason why STM would require a functional language. The main advantage some functional languages have is purity, which means the type system can guarantee that a particular block of code does not cause side effects or otherwise interact with shared, mutable state in ways that aren't allowed by STM. In an impure language, the programmer would need to be extra vigilant.

Transactional Memory does not require functional languages

tvld — Thu, 11 Jun 2009 14:17:27 +0000

Please note that transactional memory does not require a functional language. In fact, the majority of publicly-available software implementations of TM target C/C++ applications.

Transactional Memory

tvld — Thu, 11 Jun 2009 14:10:47 +0000

Note that the Rock CPU's TM is a best-effort implementation. Even if there are no data conflicts, it does not guarantee that all transactions run without being aborted for some reason. The guarantee they seem to give is something close to an DCAS.

Transactional Memory

tvld — Thu, 11 Jun 2009 14:06:08 +0000

First, compare-and-set (CAS, cmpxchg,...) is universal, as is LL/SC.
Therefore, you can build nonblocking STMs, and people actually do (see, for example, the paper describing DSTM (one of the first STMs)).

Assuming that your memory transactions don't block by waiting for external events to happen, no sane (S)TM will deadlock. Some might live-lock, but that is just a question of contention management, and not a principal limitation (remember that CAS is universal...).

Please actually do read the relevant literature.

Transactional Memory

ekmett — Thu, 11 Jun 2009 12:33:00 +0000

Well, ~4 billion slots seems pretty flexible. ;)

Transactional Memory

ketilmalde — Thu, 11 Jun 2009 08:24:55 +0000

> Everybody talks about how STM removes locking. This is bollocks.

Really? I think there's a lot of talk about how STM is bollocks. While I haven't read the literature (as) extensively (as you seem to have), I've yet to see any rationale for this. More specific pointers than just a ream of research paper titles would be great.

> This is because pure STM requires the LL/SC

I'm sorry, but isn't this SOFTWARE transactional memory we're talking about? What's stopping the run-time system from abstracting away the underlying hardware?

> Every existing STM library actually uses locks internally. Period.
> Please, stop the cargo cult hyperbole. The only real STM implementations
> are on paper, or maybe in a lab w/ a custom ASIC.

While I've only made toy implementations using it, Haskell's STM library seems awfully real to me. I'm not aware of any locking, but I could be misunderstanding how it works, of course.

Further down, you go on to claim:

> Fact is, real STM does not exist.

and

> Everything else can deadlock, and can livelock

While I love unsubstianted claims as much as the next guy, your opinions would be more enlightening if you provide actual example code that demonstrates this.

Transactional Memory

wahern — Mon, 08 Jun 2009 19:52:58 +0000

How many slots?

Should I just tell pthread-win32 users, "POSIX signals work without any trouble... just don't use more than N threads"?

That's not STM per the theory, is it? That's something very close to STM, but still requires workarounds and caveats. And w/ that attitude, Intel or AMD will never give us the hardware support that's needed.

Unless STM is simple and straightforward (which, even if the algorithm is complicated, it's _universal_, and so you won't have to roll your own everytime), then people will still mostly just _talk_ about STM rather than actually _using_ real STM, w/ the concomitant _realized_ benefits.

Clojure - many Lisp implementations compiled, syntax alternatives

flewellyn — Mon, 08 Jun 2009 15:30:31 +0000

Personally, I find the parens much less difficult to deal with than the soup of braces, brackets, angle-brackets, semicolons, and the like that you get with languages like C++, Java, or C#. And the fact that there is no operator precedence (because there is no infix) means that there is no precedence lossage, and I can tell at a glance which operators will be called just by their position, without having to remember precedence rules.

Granted, the parens would be hard to keep track of without a good editor like Emacs, but I find the same to be true of other languages, be they braces-and-semicolon languages like C\C++\Java\PHP\Javascript\whatever, or whitespace-significant like Python. A good editor is essential no matter what.

Clojure - many Lisp implementations compiled, syntax alternatives

dwheeler — Mon, 08 Jun 2009 14:24:53 +0000

Quite true. Many Lisp-based implementations include compilers, and many can generate very nice code (especially if given some type hints).

Some people are put off by Lisp's syntax ((((((lots of parens, no built-in infix)))))). If you're one of them, you might want to check out this page on making Lisps readable, in particular, sweet expressions.

A look at two new languages: Vala and Clojure

aanno — Sat, 06 Jun 2009 14:03:59 +0000

Just to be complete, there is another functional language that compiles to Java bytecode called CAL. CAL is inspired by Haskell and hence strongly typed.

Transactional Memory

ekmett — Sat, 06 Jun 2009 01:34:12 +0000

You can get by with the 8 byte version of cmpxchg by using an array of slots
rather than raw pointers, it is just less elegant.

But even so thats a far cry from no implementation being possible. ;)

Are you sure all the language developers are mad?

amaranth — Fri, 05 Jun 2009 18:53:39 +0000

Vala does have some type inference, btw. Just like C#, it supports things like this:

var reader = new Reader ();

Transactional Memory

wahern — Fri, 05 Jun 2009 17:29:38 +0000

I am/was aware of that paper.

There are other DCAS algorithms, too, including (IIRC) one which is probabilistic (but strong). One problem I encountered is that early Opterons don't implement a 128-bit CAS.

Also, my particular task was implementing POSIX signals for pthreads-win32, which ruled out dynamic allocation (requiring locking) of context structures--required by many (all?) of these CAS algorithms.

Transactional Memory

Frej — Thu, 04 Jun 2009 20:08:24 +0000

I think your angle on (software) transactional memory is lockfree/nonblocking/wait-free stuff (the terms are somewhat vaguely defined imo).

But it's not the only point of STM (today). It's about safety and ease of concurrent programming on shared memory architectures.

Secondly, you missed the paper that inspired Software TM:
Transactional Memory: Architectural Support for Lock-Free Data Structures
Herlihy & Moss (1993)

Note that transactional hardware as an idea goes further back. But the above paper is pure hardware. Shavit and Toutiou later introduced Software Transactional Memory in the paper you posted.

So it is correct to distinguish between Transactional Memory and Software (assisted) Transactional Memory. Also, it does not make it pen and paper because the implementation uses locks. So surely STM exists, there are many implementations - The best are compiler/language assisted.

Are you sure all the language developers are mad?

khim — Thu, 04 Jun 2009 19:28:16 +0000

Sure (and what is ironic about it?), but what I am claiming it that it's not overly useful in a heavily imperative/OO context, given that C++/Java/C# programmers have gone many years without it.

Then why it's added to C#, C++ (gcc 4.4 at least does have it), etc? Are you sure developers do it because they all are mad?

Eclipse does a good enough job at filling out generics right now for me.

Yup. Basically you are using type inference - just implemented not in compiler as sane people are doing but in editor. And it produces tons of useless clutter because it's implemented in wrong place.

We can't use GC in the lower level components of the GNOME stack because then if you wanted to use a higher level language (like OCaml!) on them, you'd have two different garbage collectors in the same process which is a recipe for disaster.

Why is it a disaster? You can combine compiled Java code (GCJ) and Scheme code (Guile) in a single process - and everything "just works". Sure, it's not exactly super-fast (you are scanning some small regions of memory twice), but no other problems are shown...

Anyways, you seem to be essentially saying that because Vala isn't OCaml it must be broken, when there are actual engineering tradeoffs that you're not recognizing.

Nope. If you want to see the language designed around existing OO-system, but which is done right - take look on Groovy. It's not perfect (no language is perfect) but it adds a lot of usefull features to Java while reusing the same JVM. Sure, JVM does have richer set of features if you compare it with GLib/GObject, but still the Vala is pretty pathetic language.

Transactional Memory

wahern — Thu, 04 Jun 2009 18:37:02 +0000

From the Wikipedia entry I think this is closer to hardware transactional memory. STM is a way to get transactional semantics by the use of a simple primitive and fancy algorithms where parallel threads do a complicated dance to arrive at the completion of a [compound] transaction.

The Rock CPU ops would seem to mostly obviate the need for the dance.

Transactional Memory

ekmett — Thu, 04 Jun 2009 18:01:35 +0000

<start lock-free STM cargo cult hyperbole>
STM _can_ remove locking on modern hardware, but you're using the wrong primitives.

To implement a fully lock-free STM you use an atomic n-CAS. You are correct that LL/SC or DCAS isn't available on a modern CPU directly. However, you CAN build an n-CAS out of that very same x86 cmpxchg16b-style CAS operation. The derivation isn't very straight forward, so I'm not surprised that you didn't come up with it by yourself, but a construction exists. You wind up comparing and swapping the values of n 'slots' atomically, rather than swapping n machine integers directly.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1...

Once you have that, the derivation is straightforward.

The reason almost all transactional memory implementations fall back on ordered locks is because in practice the n-CAS STM is slower than the lock-based STM, not because no such construction exists.

Transactional Memory

wahern — Thu, 04 Jun 2009 17:51:34 +0000

Actually, Software Transactional Memory is the correct term. To wit:

"Software Transactional Memory", Nir Shavit and Dan Toutiou, 1997.

The confusion is part of what I'm raging about ;) You can't simply say, "well, by 'software' I mean whatever I want it to mean, and not what I'm implying".

Fact is, real STM does not exist. It doesn't exist in the JVM, it doesn't exist anywhere in production (notwithstanding the Rock CPU mention). It can only exist w/ a universal primitive like LL/SC, as proven by, I believe, Herlihy.

Everything else can deadlock, and can livelock (if you're providing STM semantics).

Now, as pointed out elsethread, yes, STM can provide conceptual amelioration regarding the semantics of a language. But when that new language is running on your desktop, there is no way to "fake" it.

Existing STM is analagous to Perl5/6's "quantum" operators. Conceptually useful, but it's not literally doing it.

But don't take my word for it. Here's a small list of relevant material. These are the papers I still have in my research directory:

"Software Transactional Memory", Shavit and Toutiou, 1997.

"A Methodology for Implementing Highly Concurrent Data Objects", Herlihy, 1993.

"A Methodology for Implementing Highly Concurrent Data Structures", Herlihy, 1990.

"A Practical Multi-Word Compare-and-Swap Operation", Harris, Fraser, Pratt, 2002.

"Impossibility and Universality Results for Wait-Free Synchronization", Herlihy, 1988.

"Practical Lock-Free and Wait-Free LL:SC:VL Implementations Using 64-bit CAS", Michael, 2004.

"Wait-Free Synchronization", Herlihy, 1991.

Transactional Memory

mitchskin — Thu, 04 Jun 2009 14:38:05 +0000

The only real STM implementations are on paper, or maybe in a lab w/ a custom ASIC.

It sounds like you're thinking about hardware transactional memory. Software transactional memory (STM) may indeed be implemented using locks, but it does provide an interface that means client code can avoid using locks directly. You're right that there still may be locking somewhere, but that can still be a win since it isolates locking to one widely shared piece of code.

A look at two new languages: Vala and Clojure

rwmj — Thu, 04 Jun 2009 14:13:11 +0000

You really should read this essay!

A look at two new languages: Vala and Clojure

walters — Thu, 04 Jun 2009 14:11:02 +0000

Type inference is possible with OO languages. Ironically recent versions of C# have a rather pathetic form of type inference.

Sure (and what is ironic about it?), but what I am claiming it that it's not overly useful in a heavily imperative/OO context, given that C++/Java/C# programmers have gone many years without it. Eclipse does a good enough job at filling out generics right now for me.

Unfortunately all of this research seems to have passed over the heads of the developers of Vala.

You missed by point that garbage collection would have been incompatible with a key Vala design goal. It didn't "pass over their head".

We can't use GC in the lower level components of the GNOME stack because then if you wanted to use a higher level language (like OCaml!) on them, you'd have two different garbage collectors in the same process which is a recipe for disaster.

design contracts, modularity, strong typing, phantom types, test-driven development.

Vala definitely has modularity and strong typing. I'd argue test-driven development is not a language feature but a cultural feature. I'm not familiar with phantom types.

Anyways, you seem to be essentially saying that because Vala isn't OCaml it must be broken, when there are actual engineering tradeoffs that you're not recognizing.

A look at two new languages: Vala and Clojure

alankila — Thu, 04 Jun 2009 14:01:37 +0000

I'd like to say that type inference makes it somewhat possible to write code without an IDE. Static languages like C# and Java are chock full of classes, and you'd be dipping into the manuals all the time to figure out which returns what and so on.

With a C# keyword like "var" you can make the type information implicit, which makes it easier to write and change the code. Plus there's just something about:

Reader reader = new Reader()

collapsing to:

var reader = new Reader()

that makes the code much more readable to me. It's removing the type information that looks and feels like noise to me.

Then again, when there's a typo somewhere and the compiler can't figure out what the implicit type stands for, the errors that result are almost incomprehensible. I'm hoping Mono people can fix the parser to abort earlier instead of filling "var" with "object" and proceeding until it crashes and burns 5 lines later with missing methods and wrong types for calls etc. Usually the first thing to debug problems like this is to add some type information back so you'll pínpoint the line where it goes wrong.

A look at two new languages: Vala and Clojure

rwmj — Thu, 04 Jun 2009 13:54:04 +0000

Type inference is possible with OO languages. Ironically recent versions of C# have a rather pathetic form of type inference. Anyway, OCaml has type inference, duck typing, strong typing and excellent OO.

GUI toolkits can be designed on pure functional principles, although that wasn't what I was advocating. Look up Functional Reactive Programming. There are various toolkits for Haskell implementing these techniques.

Safety is always a good thing to build into modern languages, not just because no one wants their programs to crash so much, but because in some cases it really matters - errors and inaccuracies in GUI programs can have all sorts of effects from wasted time right up to death. Languages should be designed to reduce programmer mistakes. Garbage collection is one of many techniques in this area. Others include: design contracts, modularity, strong typing, phantom types, test-driven development.

Unfortunately all of this research seems to have passed over the heads of the developers of Vala.

A look at two new languages: Vala and Clojure

walters — Thu, 04 Jun 2009 13:30:51 +0000

It's not clear to me that type inference is a huge win for an imperative OO language in general. The general imperative/OO versus FP debate aside, in the specific domain Vala originated from (GUI programming for GNOME), OO languages are just a much more natural fit than FP, since the GUI is a massive chunk of state. Certainly all of the libraries are heavily OO and imperative.

Not clear what you mean by "safe programming"? Memory safety/garbage collection? In that case true, but it was a design goal of Vala to be independent of higher level runtimes and thus usable for lower level libraries in the stack.

A look at two new languages: Vala and Clojure

NAR — Thu, 04 Jun 2009 13:23:34 +0000

No locks are required, therefore there are no deadlocks or race conditions.

Famouos last words :-) Erlang doesn't have mutable variables, so there's no need to use locks, still it's fairly easy to introduce deadlocks and race conditions as long as there's message passing between threads.

Transactional Memory

zdzichu — Thu, 04 Jun 2009 13:15:15 +0000

What about Sun's Rock CPU?

Clojure and JVM languages

tnoo — Thu, 04 Jun 2009 12:45:41 +0000

well, version 2.5 is under way, which is not bad considering that language changes small between versions.

Clojure and JVM languages

rfunk — Thu, 04 Jun 2009 11:58:44 +0000

Yes, but my understanding is that Jython is well behind CPython, with
somewhat slow development. The languages I mentioned are either JVM-only
languages or are current and competitive with the C equivalent.

A look at two new languages: Vala and Clojure

njh — Thu, 04 Jun 2009 11:03:21 +0000

Yes - hopefully what was meant by the original comment was that one can have a source distribution which contains both the Vala sources and the generated C files, such that someone who just wants to "./configure && make install" can do so with only a C development environment installed.

Someone who wants to exercise "freedom 1" can do so, but will need to get a Vala development environment (much as someone who wants to do non-trival hacking on a project that includes a YACC parser will need Bison installed, but if they just want to build the program unmodified then they only need a C compiler).

A look at two new languages: Vala and Clojure

wingo — Thu, 04 Jun 2009 09:50:54 +0000

In fact, Clojure compiles to java bytecode as well. It's as good as java inside functions, but values leaving functions have to be boxed.

Transactional Memory

farnz — Thu, 04 Jun 2009 09:44:35 +0000

For those who want to be accurate about it, STM moves responsibility for locking from the application developer to the STM implementor; the contract is that STM applications cannot deadlock, and as a quality of implementation issue, should not livelock.

As with many things in programming, the hope is to trade off the possibility of more performance (given a high enough standard of programmer), for reliability now.

A look at two new languages: Vala and Clojure

rwmj — Thu, 04 Jun 2009 09:05:57 +0000

Vala is a bit of a lost opportunity.

It could have been a great step forward: type inference, non-intrusive static typing, ideas from functional languages, strong emphasis on safe programming practices ... All things which are needed by the free software community.

Instead we got a warmed-over C# clone with a syntax more verbose than Java, and none of the innovations in language design which have happened in the past decades.

Rich.

Clojure and JVM languages

rwmj — Thu, 04 Jun 2009 09:03:12 +0000

And OCaml ...

Clojure and JVM languages

tnoo — Thu, 04 Jun 2009 06:05:21 +0000

and Jython, of course.

Transactional Memory

jamesh — Thu, 04 Jun 2009 05:18:56 +0000

Well Clojure isn't running on a real CPU, so the capabilities of real CPUs are not directly relevant.

The language's home page seems to be saying that STM is the concurrency model provided to programs written in the language (and that those semantics are limited to a single type of variable).

I am sure you are correct that it is implemented via locks internally -- it'd use the primitives provided by the JVM.

Transactional Memory

wahern — Thu, 04 Jun 2009 04:06:41 +0000

Everybody talks about how STM removes locking. This is bollocks. I read all the relevant theoretical papers, and poured over the code of existing implementations. I tried to implement a simple STM mechanism, and it's not possible for any amount of data more than 16-bytes (the largest atomic xchgcmp on the ubiquitous x86). This is because pure STM requires the LL/SC (load-linked/store-conditional) processor capability. But NO EXISTING CPU DOES FULL LL/SC, and x86 doesn't even have LL/SC, period (cmpxchg was _proven_ insufficient as a universal primitive for STM 20 years ago). LL/SC requires complicated and non-performant chip circuitry to guarantee the LL/SC requirements. Basically, _any_ write--no matter the op--to an LL address needs to set a flag so a following SC can fail and the code can restart the copy operation; in practice this costs too much. Chips which nominally support LL/SC only make the guarantee for the width of a cache line, IIRC.

Every existing STM library actually uses locks internally. Period. Please, stop the cargo cult hyperbole. The only real STM implementations are on paper, or maybe in a lab w/ a custom ASIC.

Clojure and JVM languages

rfunk — Thu, 04 Jun 2009 03:18:52 +0000

It's worth noting that Clojure is far from the only non-Java language
running on the JVM. That space seems to be getting a lot of activity these
days, most notably (besides Clojure) with Scala, Groovy, and JRuby. The
dynamic-language support planned for the next major JRE release will
likely accelerate this trend.

A look at two new languages: Vala and Clojure

flewellyn — Thu, 04 Jun 2009 01:05:14 +0000

>> Like other Lisp implementations, Clojure is interpreted

Ah, careful, you'll get a lot of Lispers' backs up with that one. Modern Lisps like Common Lisp and Scheme are not "interpreted". They are interactive, but most of them include compilers; the Common Lisp standard requires a minimal compiler, in fact, and many CL implementations don't have interpreters at all, instead compiling code as it's read in (to bytecode or machine code, depending).

A look at two new languages: Vala and Clojure

JoeBuck — Thu, 04 Jun 2009 00:57:39 +0000

The resulting C compiles normally with gcc, plus it can be distributed as source packages fully usable on platforms that do not have Vala installed.

Careful. It's a nice feature that users who don't have Vala can build a program from the C output from the Vala compiler. But one of the functions of source packages is license compliance, and it's important to remember that for purposes of GPLv2 or GPLv3, the source code is defined as the preferred form for modification, thus the Vala code is the source and the C code produced by the Vala compiler is not. Vala source must be made available for license compliance.