7 ms·

Strand Programming Language

117 points by QuinnWilton 5y ago

skissane 5y ago
Their implementation approach is interesting: they have their own custom Forth implementation, with a kernel written in assembly language (ARM, aarch64, x86_64 and ppc64le). Then Strand is written in a mixture of Forth and itself.
- QuinnWilton 5y ago
  I think this is very indicative of Winkelmann's philosophies about software in general. On his site he writes a little bit about why he thinks Forth is so important, and I think it makes for a good explanation of why he probably implemented Strand like this: http://www.call-with-current-continuation.org/articles/forth.txt http://www.call-with-current-continuation.org/articles/forth...
ADavison2560 5y ago
A good introduction to concurrent logic languages: Parlog86 and the dining logicians G. A. Ringwood Communications of the ACM January 1988 https://doi.org/10.1145/35043.35044 https://doi.org/10.1145/35043.35044 https://dl.acm.org/doi/10.1145/35043.35044 https://dl.acm.org/doi/10.1145/35043.35044
gnufx 5y ago
I wasn't involved, but I remember considerable interest in Strand from parallel programming people in the lab about the time it appeared. I don't think that lasted long, but unfortunately I don't remember why it failed (if I knew then). SISAL was probably a better bet as a dataflow-ish language, but I don't remember anyone else looking at it, despite Manchester being "just" down the road.
anentropic 5y ago
No idea if related in any meaningful way, but https://github.com/rust-lang/chalk/tree/master/chalk-engine/src https://github.com/rust-lang/chalk/tree/master/chalk-engine/... (a "PROLOG-like logic solver" for the Rust trait system) also makes use of "strands"
- QuinnWilton 5y ago
  Oh thank you for sharing! I've never come across this, but there's some great references in the README I'll have to go through.
pie_flavor 5y ago
From the User's Manual: ä¸‰å€‹å’Œå°šæ²’æ°´å– (Chinese Proverb)
- suzuki 5y ago
  It is a "mojibake" of 三個和尚沒水喝[1]. [1] https://en.wikipedia.org/wiki/Three_Monks https://en.wikipedia.org/wiki/Three_Monks
simplify 5y ago
A sample from their user manual[0]: % print even numbers between 1 and 10 main :- count(1). count(11). count(N) :- N =< 10 | even(N), N2 is N + 1, count(N2). even(N) :- M is N \\ 2, even(M, N). even(0, N) :- writeln(N). even(_, _) :- otherwise | true. [0] http://www.call-with-current-continuation.org/strand/MANUAL http://www.call-with-current-continuation.org/strand/MANUAL
- rad_gruchalski 5y ago
  Looks very similar to erlang, for sure the devil is in details but it’s quite easy to read when applying erlang line of thought to it.
  - pfraze 5y ago
    Erlang was originally built from Prolog, I believe.
    - QuinnWilton 5y ago
      Yup! The original Prolog implementation is described in "Use of Prolog for developing a new programming language" [0], and took place in 1986. After performance eventually became an issue, they cross-compiled Erlang to a few other concurrent languages (Strand included), before opting to directly implement Erlang in C. [0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3972 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3...
  - QuinnWilton 5y ago
    Joe Armstrong and Robert Virding actually experimented with compiling Erlang to Strand. I'm not familiar with all of the details, but I believe they saw a factor of six speedup as compared to the Prolog implementation [0], but deemed the project a failure because of the complexity involved in restricting Strand's parallelism and failure to meet their target of a 70x speedup [1]. I'm actually sharing this in the first place because I managed to acquire a copy of "Strand: New Concepts in Parallel Programming" [2] yesterday, and it includes a case study about the Erlang -> Strand compiler, so I've been having fun trying to piece together the lineage. [0] https://erlang.org/download/armstrong_thesis_2003.pdf https://erlang.org/download/armstrong_thesis_2003.pdf [1] http://erlang.org/pipermail/erlang-questions/2007-September/028864.html http://erlang.org/pipermail/erlang-questions/2007-September/... [2] https://www.amazon.com/Strand-New-Concepts-Parallel-Programming/dp/013850587X https://www.amazon.com/Strand-New-Concepts-Parallel-Programm...
doublec 5y ago
From the same author, and in the same family of languages, is FLENG: http://www.call-with-current-continuation.org/fleng/fleng.html http://www.call-with-current-continuation.org/fleng/fleng.ht... It lacks Strand's distributed features but includes prolog's unification.
chrisjharris 5y ago
I find this fascinating, if a bit incomprehensible, but what might an intended use case be?
- chriswarbo 5y ago
  A nice property of logic programming is that its semantics don't depend on "time": it just turns data into data (unlike "imperative" programming, like C, Java, etc. which rely on state changing over time). This is why logic programming is sometimes called "declarative". Whilst concurrency and parallelism are a bit of a nightmare in imperative languages (e.g. multithreading), they turn out to be trivial in such "declarative" languages; in fact the difficulty is usually in reducing parallelism, to keep down the context-switching overheads. Traditional logic programming languages like Prolog work in a single-threaded depth-first manner, i.e. to execute something like `main` we look at its definition, which might have multiple "clauses" depending on the input data (a bit like doing a `switch` or `cond` to figure out what to return); Prolog will see if the first condition applies, and if so it will start calculating the corresponding definition, which will probably involve some mixture of calls to other functions; it will execute those functions in a similar way. However, it will also "remember where it got up to" during the execution of 'main'; if the definition fails (or if we've asked for more than one result!), it will "back track" and try the next clause. This sort of like having a try/catch in each switch clause, and moving on to the next clause if there's an exception. Strand seems similar, but rather than trying one clause at a time, depth-first; it instead runs all of the clauses concurrently. This doesn't need to "remember" anything or back-track; if a particular clause fails then its thread dies, leaving the others (if any) to keep going. It seems like a remarkably simple way to achieve massive parallelism, especially for those already familiar with logic programming.

117 points by QuinnWilton 5y ago

Their implementation approach is interesting: they have their own custom Forth implementation, with a kernel written in assembly language (ARM, aarch64, x86_64 and ppc64le). Then Strand is written in a mixture of Forth and itself.

QuinnWilton 5y ago
I think this is very indicative of Winkelmann's philosophies about software in general. On his site he writes a little bit about why he thinks Forth is so important, and I think it makes for a good explanation of why he probably implemented Strand like this: http://www.call-with-current-continuation.org/articles/forth.txt http://www.call-with-current-continuation.org/articles/forth...

ADavison2560 5y ago

A good introduction to concurrent logic languages: Parlog86 and the dining logicians G. A. Ringwood Communications of the ACM January 1988 https://doi.org/10.1145/35043.35044 https://doi.org/10.1145/35043.35044 https://dl.acm.org/doi/10.1145/35043.35044 https://dl.acm.org/doi/10.1145/35043.35044

gnufx 5y ago

I wasn't involved, but I remember considerable interest in Strand from parallel programming people in the lab about the time it appeared. I don't think that lasted long, but unfortunately I don't remember why it failed (if I knew then). SISAL was probably a better bet as a dataflow-ish language, but I don't remember anyone else looking at it, despite Manchester being "just" down the road.

anentropic 5y ago

No idea if related in any meaningful way, but https://github.com/rust-lang/chalk/tree/master/chalk-engine/src https://github.com/rust-lang/chalk/tree/master/chalk-engine/... (a "PROLOG-like logic solver" for the Rust trait system) also makes use of "strands"

QuinnWilton 5y ago
Oh thank you for sharing! I've never come across this, but there's some great references in the README I'll have to go through.

pie_flavor 5y ago

From the User's Manual: ä¸‰å€‹å’Œå°šæ²’æ°´å– (Chinese Proverb)

suzuki 5y ago
It is a "mojibake" of 三個和尚沒水喝[1]. [1] https://en.wikipedia.org/wiki/Three_Monks https://en.wikipedia.org/wiki/Three_Monks

simplify 5y ago

A sample from their user manual[0]: % print even numbers between 1 and 10 main :- count(1). count(11). count(N) :- N =< 10 | even(N), N2 is N + 1, count(N2). even(N) :- M is N \\ 2, even(M, N). even(0, N) :- writeln(N). even(_, _) :- otherwise | true. [0] http://www.call-with-current-continuation.org/strand/MANUAL http://www.call-with-current-continuation.org/strand/MANUAL

rad_gruchalski 5y ago
Looks very similar to erlang, for sure the devil is in details but it’s quite easy to read when applying erlang line of thought to it.
- pfraze 5y ago
  Erlang was originally built from Prolog, I believe.
  - QuinnWilton 5y ago
    Yup! The original Prolog implementation is described in "Use of Prolog for developing a new programming language" [0], and took place in 1986. After performance eventually became an issue, they cross-compiled Erlang to a few other concurrent languages (Strand included), before opting to directly implement Erlang in C. [0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3972 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3...
- QuinnWilton 5y ago
  Joe Armstrong and Robert Virding actually experimented with compiling Erlang to Strand. I'm not familiar with all of the details, but I believe they saw a factor of six speedup as compared to the Prolog implementation [0], but deemed the project a failure because of the complexity involved in restricting Strand's parallelism and failure to meet their target of a 70x speedup [1]. I'm actually sharing this in the first place because I managed to acquire a copy of "Strand: New Concepts in Parallel Programming" [2] yesterday, and it includes a case study about the Erlang -> Strand compiler, so I've been having fun trying to piece together the lineage. [0] https://erlang.org/download/armstrong_thesis_2003.pdf https://erlang.org/download/armstrong_thesis_2003.pdf [1] http://erlang.org/pipermail/erlang-questions/2007-September/028864.html http://erlang.org/pipermail/erlang-questions/2007-September/... [2] https://www.amazon.com/Strand-New-Concepts-Parallel-Programming/dp/013850587X https://www.amazon.com/Strand-New-Concepts-Parallel-Programm...

doublec 5y ago

From the same author, and in the same family of languages, is FLENG: http://www.call-with-current-continuation.org/fleng/fleng.html http://www.call-with-current-continuation.org/fleng/fleng.ht... It lacks Strand's distributed features but includes prolog's unification.

chrisjharris 5y ago

I find this fascinating, if a bit incomprehensible, but what might an intended use case be?

chriswarbo 5y ago
A nice property of logic programming is that its semantics don't depend on "time": it just turns data into data (unlike "imperative" programming, like C, Java, etc. which rely on state changing over time). This is why logic programming is sometimes called "declarative". Whilst concurrency and parallelism are a bit of a nightmare in imperative languages (e.g. multithreading), they turn out to be trivial in such "declarative" languages; in fact the difficulty is usually in reducing parallelism, to keep down the context-switching overheads. Traditional logic programming languages like Prolog work in a single-threaded depth-first manner, i.e. to execute something like `main` we look at its definition, which might have multiple "clauses" depending on the input data (a bit like doing a `switch` or `cond` to figure out what to return); Prolog will see if the first condition applies, and if so it will start calculating the corresponding definition, which will probably involve some mixture of calls to other functions; it will execute those functions in a similar way. However, it will also "remember where it got up to" during the execution of 'main'; if the definition fails (or if we've asked for more than one result!), it will "back track" and try the next clause. This sort of like having a try/catch in each switch clause, and moving on to the next clause if there's an exception. Strand seems similar, but rather than trying one clause at a time, depth-first; it instead runs all of the clauses concurrently. This doesn't need to "remember" anything or back-track; if a particular clause fails then its thread dies, leaving the others (if any) to keep going. It seems like a remarkably simple way to achieve massive parallelism, especially for those already familiar with logic programming.