Using a Z combinator in Snap with the appearance of Lambda Calculus definitions

[s5bug]

I've been working on implementing the basics of lambda calculus in Snap, and a problem I have just run into is taking the length of a linked list.

(the length block is the same as length of, I've added an en translation)

All of these blocks in essence return functions.

Is this a bug in how Snap treats functions or is there something I have to do on my end?

[rdococ]

I don't know about the problem you're having, but "block variables" are used so that blocks in the script area can keep their own state in between calls (it's useful for boolean blocks in the generic "when <>" hat block). I think you want script variables, which when used in a procedure definition are local to that procedure.

[s5bug]

They're blocks in the variables area because they are just defined functions. I didn't really know where else to put them that would've made sense.

[rdococ]

Block variables do not act like local variables. They are used for blocks that need to keep data between the times they are run or called, such as boolean blocks in "when" hats. You don't want that, you want script variables.

Instead of this:

do this:

[s5bug]

Alright, I'll fix that up. It doesn't solve the problem with length of not evaluating properly however.

[jeandrek]

Snap! uses applicative order evaluation, so both branches are evaluated before if, then, else is applied.

[s5bug]

Which is interesting, because then a Y combinator should solve that problem, but it doesn't (see updated link, length of block)

[brianharvey]

I think if you really want a perfect rendition of lambda calculus, you have to make your own little interpreter with normal order evaluation. The alternative is to cheat for the specific case of IF, making it a special form by declaring the second and third inputs to be of type "Any (Unevaluated)."

I made a project in BYOB to implement Church numerals. A few years back, I tried reimplementing it in Snap!, and ran into the problem that script variables had a scope of the entire script in which they appear, so another SCRIPT VARIABLES with the same variable name would give the same binding a new value. I made Jens change it so the scope is from the SCRIPT VARIABLES block to the end, with the understanding that if a prior binding is encapsulated in a lambda, it keeps its original value even though a new value is used below it in the script. But since then I haven't gotten around to reviving the project. Maybe you'll inspire me...

[brianharvey]

P.S. A proper Y combinator for an applicative order language is messy. Look it up in Wikipedia. I always cheat with something that isn't quite a real combinator: λ f . λ x . f f x. It's not infinitely elegant because to make, e.g., the factorial function, you have to use (lambda (fact n) (if...)) as the input to this pseudo-combinator, rather than being able to use (lambda (n) (if...)).

[s5bug]

So this should solve recursion problems? I think I have the order of operations wrong but I'm on the right track.

[s5bug]

It took a lot of debugging, but I found a real issue here. Using a y combinator that works in applicative order languages, λf.(λx.f (λy.x x y))(λx.f (λy.x x y)), the upvars aren't cooperating with eachother. I.e. instead of working, you are required to use

Otherwise, you get an error that the x upvar somewhere is set to the value of "x" and not whatever it is being called with.

Should the issue be renamed or should this one be closed and a new one opened?

[jmoenig]

upvars in Snap! are not named inputs to rings, they're the same as script vars, and - contrary to Scheme and what you seem to expect - do not add a new scope, but instead modify - and in this case even reset - the script scope. What you probably want is named parameters to your input rings, not upvars.

[s5bug]

@jmoenig is there any way to keep the λx. _ appearance using that method?

[brianharvey]

I've tried this, too, as I said above.

The problem, as @jonathan50 said, is that your if,then,else has all its inputs evaluated before the block itself is called. So even when the list is empty it tries to make a recursive call.

The solution is to declare the second and third inputs to if,then,else to be of type Reporter, That will put a grey ring around those input slots in the block, so that the expressions inside the rings aren't evaluated in advance. Then inside if,then,else you have to CALL whichever branch wins.

And the same is true of lambda. You have to declare its second input to be of type Reporter (and you have to be careful about putting in something already ringed, because Snap! will absorb a ring, which is what everyone who isn't doing lambda calculus wants. :)

If it kills you to see those rings, you can declare the relevant inputs to be "Any (unevaluated)" instead of "Reporter"; that will make the input slot look like a regular Any slot, but with an implicit lambda around whatever input you give.

[brianharvey]

P.S. How do you get the block in the palette to have different title text from the block in the Block Editor?

[jguille2]

Hi @brianharvey ,

I also asked myself about this. He uses the translations features of custom blocks. If you see, the lambda pictures is only the English translation.

Certainly this is a bit strange... the result is English will show those symbols, and other languages will show English words!!

[brianharvey]

Ah, thanks for the explanation. @jmoenig: Is this the desirable behavior, or should the prototype in the Block Editor also be translated? For some applications it doesn't matter, because maybe users of a project won't look inside custom blocks. But if users are supposed to build on the program, they'll be confused just as I was. (Yes, this use of translation is more confusing than a real translation to another language, but still.)

[jmoenig]

yes, the prototype in the block editor cannot be translated, because it might accidentally not have all the label parts, and then there'd be no way back. This is correct. imo.

[brianharvey]

Maybe the block editor should have a picture of the (maybe translated) block in the margin somewhere?

[s5bug]

The problem with unevaluated parameters is that I don't know if they need to be evaluated or not. I could wrap both result branches in a lambda in my length function and call them afterwards?

As for the way I handle the translations, I found that the block's prototype name is how it is referenced in the XML (which is how the default blocks are referenced, e.g. move forward _ steps being goForward I believe).

[brianharvey]

No, you do know. On each call to ifelse, exactly one of the second and third inputs will be chosen, so you CALL that one and ignore the other. It's just like wrapping lambdas around the branches, but it happens automatically instead of every caller of ifelse having to do it by hand. This gives the effect of normal order evaluation in the one place where it really matters.

[s5bug]

Ifelse is just a function definition, it can't exclusively be called with unevaluated results. The application block, (_ _), doesn't know what is needed and what isn't. The most I can do is make the results of the ifelse lambdas and call them outside of the entire lengthof definition. Which doesn't work the way I have tried it. It reports 0 for an empty list, 2 for a single element, and 1 for any other list.

I also have this feeling that these solutions should be elegant and shouldn't rely on throwaway variables (u).

[ghost]

at this point I doubt children (the original target of scratch) would ever use this function.

[brianharvey]

In Snap! we aren't aiming at children, but at teenagers and up.

I see what you're saying now. You couldn't use generic function application with ifelse unless the user manually makes thunks (functions of no inputs) out of the 2nd and 3rd inputs. I fixed this in my version by making ifelse a piece of syntax, which I agree is suboptimal.

Oh, wait, what if you make ( ) automatically lambdafy its second input? That would give you normal order evaluation. You'd have to CALL inputs when you do beta-reduction, I think? (Well, not just CALL-once, but keep CALLing until you have an actual value -- which means you have to be able to distinguish these under-the-surface thunks from user-intended lambdas.) Am I making any sense? In the SICP normal-order evaluator that I have in mind, the thunks are unwound when you call a Scheme primitive, but there are no primitives in λ calculus, so you have to figure out when to dethunkify,

[s5bug]

Yes, that makes some sense. The only problem I see with it are the "thunks", which, from what I've seen of lambda calculus, variables are only thrown away for logic decisions, but one or another is always used. Thunks seem like they dirty up the "elegance" of lambda calculus.

I would also (as the issue title states) like to get a Y combinator working anyways, as it allows for more general solutions to recursive problems without these loopholes.

[brianharvey]

In real lambda calculus, which is normal order, the thunks are still there, but buried in the evaluator. We just have to make them visible because we're embedding lambda calculus in an applicative order evaluator.

[s5bug]

So I've tried implementing a handful of different combinators at this point, and none of them seem to work. The Z combinator is the most widely used for this purpose and I just can't seem to make it function properly. I also don't know what is happening internally when it is run (I can't really grasp the meaning of how it traces in slowmode).

I know this is no longer a Snap issue, sans the smaller issue of nice-looking lambda definitions, but I'd still like some way to get assistance with this.

[brianharvey]

It's probably the same issue: applicative order. But I'm not an expert.

[s5bug]

The Z combinator is specifically designed for languages that apply and evaluate things eagerly.

[s5bug]

Would it be possible to use some sort of JS or Snap Library to make a named input block that takes the shape of my lambda block?