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

I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this. So I know Python's evaluation order is applicative. But I seem to be overlooking something in how applicative order works. To compensate for applicative evaluation order I reasoned to build a Y-combinator that does not dive off into infinite recursion it would be sufficient to write it like this: ``` Y = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x))) ``` I arrived at this conclusion by first manually deriving `Y g` like so ``` Y g = (lambda f : (lambda x : f(x x)) (lambda x : f(x x))) g # Definition of Y -> (lambda x : g(x x)) (lambda x : g(x x)) # beta reduction -> g((lambda x : g(x x)) (lambda x : g(x x))) # beta reduction -> g((lambda f : (lambda x : f(x x)) (lambda x : f(x x))) g) # lambda abstraction = g(Y g) # put in Y ``` And then working my way backwards like this, adding in a lambda abstraction hat would delay the recursion until a value is passed in: ``` = g(lambda z : Y g z) = g(lambda z : (lambda f (lambda x : f(x x)) (lambda x : f(x x))) g z) -> g(lambda z : (lambda x : g(x x)) (lambda x : g(x x)) z) -> (lambda x : g(lambda z : x x z)) (lambda x : g(x x)) Y g = (lambda f : (lambda x : f( lambda z : x x z)) (lambda x : f(x x))) g ``` When I manually evaluate `factorial 3` where ``` factorial_ = lambda f : lambda n : 1 if n == 0 else n * f(n-1) factorial = Y(factorial_) ``` in applicative order I get ``` factorial 3 = (lambda n : 1 if n == 0 else n * (lambda z : Y factorial_ z)(n-1)) 3 -> 3 * (lambda z : Y factorial_ z)(3-1) -> 3 * (Y factorial_ 2)

Here is the game's setup: You're given a formula for a binary expression using and or not as the connectives. The connectives are combining many variables for which two players will assign truth values to them in the order specified beforehand. For Example: ``` formula: ((x and y) or ((y and z) or (not y and not z))) turns: AAB variables: xyz ``` In this example Player A will assign a truth to x first, then y, then Player B will assign a truth to z. (The variables will always show up in the order of appearance in the formula). After all of the truth values are assigned to each variable, the formula is evaluated and the truth is returned and a winner is declared. Player A is trying to make it False and B is trying to make it True. Assume that the other player and will always choose the best value for his variable on all of his turns. If there is no way for a player to make the formula win during his turn, or if choosing either true or false would lead to winning, then false is returned if it is player A’s turn, and true is returned if it is player B’s turn. Our job is to give the best move for the current turn given a formula the previous moves and the order of moves for the game. What would the strategy for approaching something this look like? I know this is a homework question but I've spent a week trying to figure this out without any avail. If you need further clarification about the problem as I know it's a big pill to swallow just comment below I'll be sure to reply. EDIT: For further clarification, variables can show up more than once in the formula

As I understand, evaluating something like the following in normal order evaluation is inefficient due to duplicate work: ``` double x = (x,x) main = double some_hard_computation ``` I remember someone telling me - That there are two ways to avoid this: strictness analysis (to recognise that `double` is strict in its one argument, and then deviating from normal order evaluation and evaluate the argument first) and graph rewriting (store pointers to `some_hard_computation` such that both elements of the tuple point to the same computation, and evaluating one side of the tuple automatically evaluates the other side as well). - That neither of the ways are sufficient on their own to avoid all cases where duplicate work can be introduced, and that it is best to apply both when writing a compiler. I can imagine that strictness analysis can be hard, but in what concrete case can duplicate work be introduced when utilising graph rewriting? Or is either of the two bullet points above incorrect? Note: while strictness analysis is done statically (as far as I know), graph rewriting is an evaluation strategy, not a compiler optimisation. It attempts to solve the same problem as the strictness analyser, but on a different level (runtime vs. compile time).

As per this explaination, it defines applicative and normal order evaluation in one form saying: This alternative "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contrast to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called applicative-order evaluation. while this explanation defines the other way around applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed They seem to contradict each other. Do these definitions mean the same thing?

The language I'm learning is Scheme and I'm working on an exercise that gives this: ``` (define (p) (p) ) (define (test x y) (if (= x 0) 0 y)) ``` Then the question asks to evaluate the expression: (test 0 (p) ) and to comment on the behavior that would be observed under normal - order and applicative order evaluation. These are my thoughts: Under normal order, the program would evaluate the subexpressions before proceeding: Thus `( test 0 (p) )` becomes: ``` (test 0 p) ( if (= x 0) 0 p)) ``` Returning output `0` The only difference in applicative order would be that the program would run as: `( test 0 (p) )` becomes: ``` (test 0 (p)) ( if (= x 0) 0 (p))) ``` Returning output `0` Thus `(p)` would never be evaluated as it won't be needed. Is this correct? Please let me know as I have almost no experience programming.

From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee exits, and that if the same variable is passed as more than one argument, it'll be treated as separate values in the callee instead of the same value as in call by reference. Neither fact helps me explain why call by value-result produces different output than call by reference in the following code: ``` program Param (input, output); var a, b: integer; procedure p (x, y : integer); begin x := x + 2 ; a := x * y ; (1) x := x + 1 (2) end; begin a := 1 ; b := 2 ; p (a, b) ; writeln (a) end. ``` Edit: here's my understanding of things: The insight here is that in CBR, in line (1), both `a` and `x` point to the same thing, so assigning to `a` updates both `a` and `x` to `x * y` which is 6. But in CBVR, `a` and `x` point to different things, so line 1 only updates `a` to 6. `x` remains 3. Then CBR updates `a` right away so `a` ends up being 7 outside `p`. But CBVR updates `a` to whatever `x` is at the end of `p`, which is 4, so even though `a` was 6 in line (1), after `p` exits it's changed to 4.