2
$\begingroup$

I'm thinking these familiar concepts of DO and LET/LET* in the context of Lambda Calculus (LC).

LET is an abbreviation for this LC expression:

(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

and LET* is an abbreviation for this LC expression:

(LET* a 1 b 2 e) = (λ a . (λ b . e 2) 1)

where e is the body of the function. LET* just enables to use former variable inside latter variable in the following way:

(LET* a 1 b a e) = (λ a . (λ b . e a) 1)

DO is an abbreviation too and can be used in conjunction with LET's to achieve same than LET*:

(DO (LET a 1) (LET b 2) e) = (λ a . (λ b . e 2) 1)

So I have three different shorthands to construct LC expressions. Now, my questions is that is this syntactic sugar throwing me out from pure LC (or functional programming in general sense) and am I introducing side effects by this syntax?

In a way it looks like it, but on the other hand these three shorthands are only abbreviations and they translate to Lambda Calculus expressions that are well defined and reducible as any LC expressions.

$\endgroup$
2
$\begingroup$

Anything that can be encoded in the pure lambda calculus, as you realize in the last paragraph, can not have side effects. Otherwise, the lambda calculus itself would be able to express those side effects as well.

However, note that your encoding looks a bit weird. For instance,

(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

does not bind 1 to a and 2 to b. You probably want instead

(LET a 1 b 2 e) = (((λ a . (λ b . e)) 1) 2)

which does the correct binding. The other encoding should be fixed similarly.

I would suggest you "test" these encoding by performing $\beta$ steps. If you don't reach $e\{1/a,2/b\}$ something looks wrong.

$\endgroup$
  • $\begingroup$ You can encode effects such as exceptions with continuations. $\endgroup$ – xavierm02 Sep 25 '17 at 17:33
  • $\begingroup$ @chi Right, that is exactly how I interpret the notation in my original post. I think both notations should be fine, mainly because expression could be written even less verbose λa.λb.e 1 2 or λab.e 1 2 right? Anyway, we can safely say, that LET and DO as they are presented above, do not side effect? I wonder what would be the global scope then, that would make side effects possible, if not in LC, but some other similar system? $\endgroup$ – MarkokraM Sep 25 '17 at 17:57
  • $\begingroup$ I mean, what is the trick to jump from the nullipotent to the side-effected system? $\endgroup$ – MarkokraM Sep 25 '17 at 18:02
  • $\begingroup$ @xavierm02 I agree, but then, what is an "effect" and what is "pure computation", if you can encode the former in the latter? $\endgroup$ – chi Sep 25 '17 at 18:24
  • $\begingroup$ @chi I have shown in LET and LET* that parentheses do matter in my notation too. Otherwise it is just a matter of decision on evaluation strategy in what order to apply functions, bind arguments and so forth. Evidently it all has an effect to the result. But in this case, because of selection of my strategy, we do talk about same results, with or without parentheses. $\endgroup$ – MarkokraM Sep 26 '17 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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