17
$\begingroup$

I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH is imperative whereas Cat is functional).

An imperative language would modify the stack, and a purely functional language, such as Joy, would return a new stack, but the point is that only one stack is used at a time.

So, can stack-based programming languages be concurrent? Could they achieve concurrency by using multiple stacks at the same time or something alike?

Is it possible to implement lazy evaluation in a stack-based programming language?

Please correct me if I am misunderstanding anything about the languages and concepts mentioned above

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ How can any imperative language be concurrent? $\endgroup$
    – Bergi
    Apr 8, 2018 at 10:36
  • 3
    $\begingroup$ docs.factorcode.org:8080/content/article-threads.html $\endgroup$
    – Bergi
    Apr 8, 2018 at 10:40
  • $\begingroup$ Do you really mean concurrency (which isn't so hard to achieve, just use multiple threads running with independent stacks plus shared memory) or parallelism? $\endgroup$
    – Daniel Jour
    Apr 8, 2018 at 22:30
  • $\begingroup$ @DanielJour if I understand well, parallelism means simultaneous execution while concurrency means independent execution, so, yes, I mean concurrency. Could you elaborate more about the independent stacks for each thread? $\endgroup$
    – Joan Vene
    Apr 8, 2018 at 23:10

2 Answers 2

Reset to default
17
$\begingroup$

So, can stack-based programming languages be concurrent?

Sure.

Could they achieve concurrency by using multiple stacks at the same time or something alike?

Already for normal languages multi-threading usually means having multiple "call" stacks. It would be completely natural to give each thread its own data stack. It would be straightforward to have an actor, say, whose body was implemented by code in a stack-based language. Explicit parallelism a la GHC's par annotations should be reasonably straightforward. The main issue with executing things in parallel is that you don't know what the stack effect of the code will be until you execute it. However, using a Joy-like syntax, one could imagine [a b c] par as executing a b c either against an empty stack or a copy of the stack and only keeping the top-most element of the stack on completion (or pushing some dummy value if the stack is empty). You could imagine variations. Implicit parallelism would be harder to do naively as compared to, say, a purely functional language, but certainly could be done as well. The compiled code of a user-defined combinator is often not too different from "normal" code.

Is it possible to implement lazy evaluation in a stack-based programming language?

Unknown stack effects are again the tricky part. If you design the language such that all stack effects can be determined statically, then it doesn't seem too challenging. If you have laziness be explicit, then it also seems relatively straightforward and would look roughly like Joy's quotations and i. One language that calls itself a lazy concatenative language seems to do a mixture of both of the above approaches from what I can tell. I don't really see how an implicitly lazy concatenative language would work in the face of dynamic stack effects, at least not in any vaguely usable way, but that might just be a lack of imagination on my part.

Incidentally, it is not uncommon for stack-based languages to have multiple stacks, e.g. Forth has a data stack and a return stack upon which you can also place arbitrary data.

Improve this answer
$\endgroup$
8
$\begingroup$

I know a bit about FORTH so I will confine myself to that. It is a low level language, giving you as programmer access to all the hardware resources. So you can do whatever you like.

Concurrency

In order to have parallell programs (edit: used to say real concurrent programs) you need at least two execution units (CPU-s). It would be rather trivial to implement a word in FORTH saying, as example, "run this word on processor 2 using these two arguments". The word would allocate the two needed stacks on processor 2 and start running the word. You would need to restrict yourself somewhat in exactly what constructs you can use in that program.

If the number of concurrent programs is larger than the number of execution units you would go for "pseudo parallell" programs. Basically there are two ways to do that: coroutines or preemptive multitasking. In any case it is possible (not easy, but well described in literature) how to achieve this and FORTH allows you to access all the low level stuff you need.

Lazy evaluation

Of course you can do this in FORTH as in just about any programming language. It will not be as elegant or "built-in" as in say Haskell. I will use a very naive example.

The idea is that you define a "function" (used loosely here) that returns a set of things. One example would be a function that returns all integers. You then do operations on this set and when you are done give the result. As example, you might want to sum all integers until the sum is larger then 1000. A non-lazy evaluation would firstly allocate all integers as a set, which is impossible as there are an infinite number of integers. It would then start to work on this set. A lazy implementation would have a way of "give me the next value in the set". Doing this really only needs one variable in the funktion "last value give".

Haskell does things this way. Of course it handles more complicated situations but the idea is the same. It sugarcoates the evaluation in a way that allows you as a programmer to concentrate on the problem, not on how to solve it.

Improve this answer
$\endgroup$
5
  • 5
    $\begingroup$ "In order to have real concurrent programs you need at least two execution units ". This is merely an implementation issue. From a programming language perspective, there is almost no difference between two threads running on a single CPU or on two. In a sense, each thread can be considered a 'execution unit' of its own. $\endgroup$
    – Discrete lizard ♦
    Apr 8, 2018 at 11:09
  • 1
    $\begingroup$ Sometimes, implemtation details have to be taken into consideration. One example is when interfacing with the real world outside a real computer. In hard real time, as per "right answer too late is wrong", timing may be different when you compare running on two exekution units to running intermixed on one unit. $\endgroup$
    – ghellquist
    Apr 8, 2018 at 14:11
  • $\begingroup$ Sometimes we do. However, I doubt this is such a case. For instance, the question doesn't mention real time scheduling requirements. $\endgroup$
    – Discrete lizard ♦
    Apr 8, 2018 at 14:30
  • 4
    $\begingroup$ "Concurrency" != "parallelism". Multiple threads running on a single-CPU machine can be said to run concurrently with one another, even though no parallel processing is happening. $\endgroup$
    – Solomon Slow
    Apr 8, 2018 at 15:21
  • $\begingroup$ Point taken about concurrency vs parallells. I will change the text. $\endgroup$
    – ghellquist
    Apr 8, 2018 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.