< # head figure from sprouting niang, address: https://zh.moegirl.org.cn/File:Bg_chara_201912.png # >

preface

This article will document the author’s initial exploration of the recursive world.

There are currently three parts:

Part I –Recursion to tail recursion: I sorted out a fewExamples of non-tail recursion being translated as tail recursion. At first, it was just because non-tail recursion seemed like a lot of work to the author.
Part 2 –Genius and bursting stack! ❄Found an easy way to create stack overflows (or similar). The idea is to do modular arithmetic by recursive subtraction. Oh by the way,There are examples of various languages applying this scheme 。
Part 3 –An infinite number of Y combinators: Accidentally found something wonderful in the second part of the supplement; A little research has opened the door to a new world of very general ways to manually implement functional tail-recursion, which is probably the essence of functional tail-recursion; And this part is going to beThe previous part of the program introduced this amazing thing that was discovered 。

🙃 🐚 🦀

I have a functional tail recursion here, where “functional” is just an emphasis. All values are functions, and ordinary values are just special functions that return themselves without arguments. In this way, tail-recursion does not create a stack. Instead, it simply returns the function that was originally called at the return point as the value and then calls it. In effect, tail-recursion at this point is like a smarter GOTO. You don’t need to specify which line to jump back to, you just need to specify which function to re-execute with what new arguments — and that’s the effect.

🐙 🐙 🐍

Why tail recursion?

As opposed to non-tail recursion, the first is the well-known reason:

Tail recursion is less storage (i.e. less space complexity)

There is a more important reason to me than non-tail recursion:

I don’t need to remember all the previous calls if I want my brain to pass a value to a function. (It’s a matter of space complexity, but this time it’s my brain.)

The so-called optimization here is conditional. In general, it is more difficult to call yourself multiple times on the return (this is like a tree with multiple forks). (Of course, there is no need to optimize if they are all returned as values because there is no stack crush)

In addition, multiforked recursion can be easily optimized by the compiler for concurrent scheduling of computations. And it can be easily scheduled for distributed computation if the function has no side effects. Of course, the maximum reachable concurrency is not fixed and the space complexity is not reduced.

In contrast to the cyclic structure:

With tail recursion instead of loops, the brain doesn’t need to remember how many levels it has indented, it can just point the arrow to where it should point like a flowchart (this is my experience with Erlang). Whether or not this is a “circular structure” is entirely irrelevant.
Using tail recursion instead of loops lowers the bar for beginners, and even for skilled programmers frees up the mind by eliminating some of the theoretically unnecessary work. Because then, there are only two things you need to remember: understand what the function definition and function call are doing, and the syntax. Other syntax? Key words? Theoretically, there’s no need to even use it, and naturally, there’s no need to devote some of your energy to matching specific keywords while reading the code. Because, whether you are used to the work or not, there are ways to avoid this part of the work, the end result is exactly the same, so much of the work is actually useless. So why not avoid it? You are speaking a language that requires you to remember these keywords and be able to focus on recognizing them. So you have to pay more attention even when you don’t have to pay more attention, look at the code and see if it’s necessary, and then you might think there should be a comment here. But what about annotations? Without a machine to constrain the normality of annotations, is it expected to be anything?
In addition, if you use tail recursion instead of a loop, you can write to the function name what you had to write in the comment in the previous loop. Have a purpose? Notes but want to write anything to become ah! Do you think that if you ask someone to annotate it they will write what you think is necessary here? Also, do you think it is better to describe the business logic in comments in language that has no standard specification, or in code that is clear and clear and can be interpreted by a computer? 🙃
It’s all about the friendliness of the code itself…

Why Erlang?

Most of the logic in this article is implemented in Erlang code. The reasons are as follows:

The boundaries are well defined and the signs are not redundant.

In Erlang, the newline character can be removed, which means that the logic of compressing the code is very simple. At the same time, it doesn’t use too many superfluous symbols.
The notation is concise and reasonable.

It’s from Prolog
.
;
. To make it easy and clear to express different levels of content; The boilerplate structure of the function definition has reached a point where it can be concise and ideographic without losing any of the necessary parts. (Some languages lose their endings and have to make their indentation semantically — whether this is a bad thing depends on the situation.)
Almost any logical flow can be expressed simply by defining and calling functions.

🦑 From recursion to tail recursion

This section gives examples of recursive code for factorials, Fibonacci sequences, filtering from sets, and lazy values, respectively. Each example has two versions, tail recursion and non-tail recursion, for contrast heuristics.

In the following context, the part of the [Tail] word might indicate that this is an example of Tail recursion, whereas [Tree] is a single-branch Tree recursion unless otherwise specified.

Train of thought

It’s a trick:

Include everything you can in the parameter list!

Multi – tree I don’t intuitively think it can be optimized for tail recursion. And sometimes it’s not necessarily that optimization is good. But I’ll think about it and try again.

case

factorial

This is the Erlang guide, and I couldn’t get my head around the way it was written and I thought it would be tail recursion, so I made it tail recursion for the sake of thinking.

The following code is written in Erlang. They all compile, but for now, you don’t have to worry about syntax. If you know, a function must have parts like this:

The function name
Function parameter list
The body of the function (where the definition of the return is explicit based on parameters)
Start and stop marks for each part above

Then you will be able to understand the following grammar. If not, read the guide (or translation) below, or the aforementioned Lyse book.

Erlang – Tree

- module (recursion_tree) .
- export ([fac/1]) .

fac (0) -> 1 ;
fac (N) -> N * fac (N - 1) .

use:

c(recursion_tree). recursion_tree:fac(7). % ret: 5040

Erlang – Tail

- module (recursion_tail) .
- export ([fac/1]) .

fac (N) -> fac(N, 1) .

fac (0, FacRes) -> FacRes ;
fac (NumNeed, FacResPart) -> fac(NumNeed - 1, FacResPart * NumNeed) .

use:

c(recursion_tail). recursion_tail:fac(7). % ret: 5040

`% % % %`

This is probably the simplest example of converting ordinary recursion to tail recursion.

The tail-recursive code looks as if it could define more information.

Before the “Why tail recursion?” As for “less brainpower” mentioned in the section, this is also a good time to check and compare which of the two logic is more brainpower intensive.

In tail-recursive code, you don’t have to remember the previous call after the call, just forget about it, just think of it as a new call,
Every time is the first time.

Even if you really had to run through the code in your head, it wouldn’t be impossible, even if it was a big number to plug in. Even if you try to write each step on paper, you should be able to experience the difference.

Fibonacci sequence

Scheme

This was written in Scheme when I looked at SICP.

The functionality has only been tested by Chez (Cisco/Chez Scheme).

#| some def |# (define (=? a b) (= a b) ) (define (or? a b) (or a b) ) ;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;; #| tree invoke fib |# (define (fib n) (if (or? (=? n 0) (=? n 1)) n (+ (fib (- n 1)) (fib (- n 2))) ) ) ;; (fib 4) need: ;; |___(fib 3) need: ;; | |___(fib 2) need: ;; | | |___(fib 1) = 1 <-: ;; | | |___(fib 0) = 0 <-: ;; | | = 1; | |___(fib 1) = 1 <-: ;; | = 2; |___(fib 2) need: ;; |___(fib 1) = 1 <-: ;; |___(fib 0) = 0 <-: ;; = 1; = 3 - > :;; ;; tree rec #| tail invoke fib |# (define (fib n) (define (fib-iter next this step) (if (=? 0 step) this (fib-iter (+ next this) next (- step 1)) ) ) (fib-iter 1 0 n) ) ;; (fib 4) same: ;; (fib-iter 1 0 4) same: ;; (fib-iter 1 1 3) same: ;; (fib-iter 2 1 2) same: ;; (fib-iter 3 2 1) same: ;; (fib-iter 5 3 0) = 3 <-: ->: ;; ;; no-need-to-tree rec #| desc desc |# ;; need: means, need to got the func value to get(=) the res. ;; same: means, same as. just while tail invoke can same as! ;; <-: get(=) the res without need: . ;; ->: whole func res. #|-------------|# ;; end of file ;;

Let’s try to write it in Erlang

Erlang – Tree

- module (recursion_tree) .
- export ([fib/1]) .
fib (0) -> 0 ;
fib (1) -> 1 ;
fib (NumOfIndex) -> fib(NumOfIndex - 1) + fib(NumOfIndex - 2) .

use:

c(recursion_tree). 
recursion_tree:fib(7). % ret: 13
recursion_tree:fib(13). % ret: 233

Erlang – Tail

- module (recursion_tail) .
- export ([fib/1]) .
fib (NumOfIndex) -> fib(0, 1, NumOfIndex) .

fib (ThisValue, _, 0) -> ThisValue ; % or better: fib (_, NextValue, 1) -> NextValue ;
fib (ThisValue, NextValue, RestStep) -> 
    fib(NextValue, NextValue + ThisValue, RestStep - 1) .

use:

c(recursion_tail). 
recursion_tail:fib(7). % ret: 13
recursion_tail:fib(13). % ret: 233

`% % % %`

The sequence looks like this: [0 1 1 2 3…] Index starts at 0.

This example of the Fibonacci sequence looks like a tail recursion of a binary tree recursion. You can’t really say that. In my case, at least, this was the case: I reapplied a different train of thought.

That said, this, I think, is just to show that what tail recursion can do is also possible (but not necessary) with tree recursion, that’s all…

But it might be a good example of a heuristic idea: there is no guarantee that all tree recurrences will be rewritten as tail recurrences, but it should provide perhaps a good inspiration for the work of rewriting some tree recurrences as tail recurrences, even if they are not monomorphs. (At least to me as the author 😬, and if this can be summed up into a general approach, so much the better.)

The list is filtered by condition

Now we have a sequence [2,1,3,0, 9,1,7,1, 7,1,2, 9,1,8,4] and we want to take the first (2/3/99) odd numbers out of them in that order.

Scala

If implemented in Scala (2.12.13), the best way to write it is ideologically:

List (2,1,3,0, 9,1,7,1, 1,7,1,2, 9,1,8,4). ToStream. Filter (_ % 2! =0).take(2).toList

To verify this, however, you need to write the filter parameter as a defined function

def oddfilter (x: Int): Boolean = { println("filt: "+x) ; x%2! = 0}; ,1,3,0 List (2, 9,1,7,1, 1,7,1,2, 9,1,8,4). ToStream. Filter (oddfilter.) take (2) toList

You can see it on the REPL:

Welcome to Scala 2.12.13 (OpenJDK 64-Bit Server VM) Java 11.0.10). Type in Expressions for Evaluation. Or Try: Help. Scala > def oddfilter (x: Int): Boolean = { println("filt: "+x) ; x%2! = 0}; oddfilter: (x: Int)Boolean Scala > List(2,1,3,0, 9,1,7,1, 1, 1, 1,2, 9,1,8,4).tostream.filter (oddfilter).take(2).toList filt: 2 filt: 1 filt: 3 res0: List[Int] = List(1, 3) Scala > List(2,1,3,0, 9,1,7,1, 1, 1, 1, 9,1,8,4).tostream. 2 filt: 1 filt: 3 filt: 0 filt: 9 res1: List[Int] = List(1, 3, 9) scala>

As for the effect of not using Stream, try it for yourself ~ 😛

Is deleted
.toStreamTo perform

The source of the above implementation:

Functional programming in Scala (6) lazy loading and Stream
The application scenario of Stream in Scala and its implementation principle

But author, you don’t seem to have itTail recursionCome!

That’s right, so I’ll try to write it in Erlang (just the parts I know now).

Why Erlang? Because I find my language to be the most enjoyable by far when writing plain code.

Erlang – Tree

- module (recursion_tree) .
- export ([take_odds/2]) .

take_odds (_, 0) -> [] ; % like a `break` in loop code lang, but here is ret a val !!

take_odds ([ElementThis| RestElems], NeedTakeCount) 
    when ElementThis rem 2 =/= 0 
-> 
    [ElementThis| take_odds(RestElems, NeedTakeCount - 1)] ;

take_odds ([ElementThis| RestElems], NeedTakeCount) 
    when ElementThis rem 2 =:= 0 
-> 
    take_odds(RestElems, NeedTakeCount) ;

take_odds ([], _) -> [] .

use:

C (recursion_tree). Recursion_tree: take_odds ([2,1,3,0, 9,1,7,1, 1,7,1,2, 9,1,8,4], 77). The % ret: ,3,9,1,7,1,1,7,1,9,1 [1] recursion_tree: take_odds ([2,1,3,0, 9,1,7,1, 1,7,1,2, 9,1,8,4], 3). % ret:,3,9 [1]

Erlang – Tail

- module (recursion_tail) .
- export ([take_odds/2]) .

take_odds (List, HowManyNeedToTake) -> 
    take_odds(List, [], HowManyNeedToTake) .

take_odds (_, TakenRes, 0) -> TakenRes ;

take_odds ([ElementThis| OldListRest], NewList, NeedToTake) 
    when ElementThis rem 2 =/= 0 
-> 
    take_odds(OldListRest, [ElementThis| NewList], NeedToTake - 1) ;
take_odds ([ElementThis| OldListRest], NewList, NeedToTake) 
    when ElementThis rem 2 =:= 0 
-> 
    take_odds(OldListRest, NewList, NeedToTake) ;

take_odds ([], TakenResFew, _) -> TakenResFew .

use:

C (recursion_tail). Recursion_tail: take_odds ([2,1,3,0, 9,1,7,1, 1,7,1,2, 9,1,8,4], 77). The % ret: ,9,1,7,1,1,7,1,9,3,1 [1] recursion_tail: take_odds ([2,1,3,0, 9,1,7,1, 1,7,1,2, 9,1,8,4], 3). % ret:,3,1 [9]

`% % % %`

But then again, in terms of meaning and logic, the tree recursion is actually a little bit more relevant.

But you can put more information in the tail-recursive form, so it’s still better.

I learned this tail recursion from the “Reverse” definition in the More About Lists section of the Erlang Guide, so the results are also placed in reverse order…

And it’s not yet clear how to make it turn out to be true while keeping it natural. In addition, non-tail recursion is also written from the convert_list_to_c definition in the same section, but is used for a different requirement.

And remember this little thing:

If you want a remainder (modulus) in Erlang, use REM instead of percent sign %.

.

The percent sign % is a comment. In Erlang, you use REM.

🦑 Genius and bursting stack! ❄

This section will provide a slightly better way of creating stack bursts than factorial. The factorial is too big!

What is that day? It’s just a cute meme, never mind! 🙃 🙃

Way to

Is to make a function that can do modular arithmetic.

I was playing with the Bash return code when I found that 114514 would be changed to a different number, and the dichotomy was used (Exit 2221); echo $? After touching the bottom line of change and invariance, I found that the rule had a sense of recursion, so I implemented a function in Java that input a number will give me the corresponding return code of Bash. As a result, I found that I could flexibly input large and small numbers to detect the allowable depth of tail recursion in Java, so I had such a method. But that was a long time ago.

Funny thing is, until recently, I didn’t think, this is the model method!! It was when I saw this:
iex> <<1>> === <<257>>
true
It comes from the official handbook of the language here.

The following Scheme code shows what I have in mind. (If you don’t understand it, you can skip it and continue reading.)

(define (remb num rem)
        (if (< num rem) num (remb (- num rem) rem) )
)

The logic is:

There’s something calledrembTake two arguments to the functionnum 和 remWords:
If the former is small, the function returns the former, and if it’s not, it subtracts the former as the newnumAnd the latter continues to do itrem Then call the function again with the new set of parameters.

This, of course, is very low performance. So, you shouldn’t use it to actually do any computation. Its value is simply that it is simple to define, and it is also easy to indirectly specify the number of tail-recursion occurrences by using different parameters.

And this test leads to a great idea:

Is it possible to run a runtime that does not support tail recursion:

It just takes advantage of the various capabilities provided by the runtime itself

And keep the expression of the tail-recursive form on the code’s style

To do:

Enable a runtime that does not support tail recursion to support tail recursion

What about this kind of thing?

The answer is yes.

Sample code for several languages (runtimes) to run this detection logic is shown below, along with corresponding code that is not supported by proponents (so far, only techniques to support tail recursion on Bash have been given).

Ice clever genius arithmetic ❄❄❄

What is this? This is not actually the code example described above.

You can skip it (it’s a cruel thing to say, but you can skip it), but if you want to relax, you can finish it.

Now let’s welcome Mrs. Geruno.

Hello and welcome to Geruno’s arithmetic class.

The above implementation, as you can see, does not take into account the negative number num.

Because you don’t really need it.

Of course I know. Do you take me for an idiot? Hum! ❄ In a word, this is not perfect! ❄.

Cheruno is here to bring you an enhanced version of what could be called a genius arithmetic tool!

Well, let’s take a look at Geruno’s great work:

Pet-name ruby ❄ ❄ ❄

- module (playfuns) . 
- export ([remb/2, bakacal/1]) .

%% remb/2 define:
remb (Num, RemNum) 
    when 0 =< Num 
    andalso Num < RemNum 
-> 
    Num ;
remb (NumReming, RemNum) 
    when RemNum =< NumReming 
-> 
    remb(NumReming - RemNum, RemNum) ;
remb (NumReming, RemNum) 
    when NumReming < 0
-> 
    remb(NumReming + RemNum, RemNum) .

%% bakacal/1 define:
bakacal (N) -> remb(N - 1, 9) + 1 .
% bakacal (N + 1) -> remb(N, 9) + 1 . % error, illegal pattern

The Bakacal above is the genius arithmetic. The latter /1 indicates that only one argument is required.

Is it very simple? (• ̀ ⌄ ́)

Next, if you want to use the genius arithmetic machine, just do this on Eshell:

1>c(playfuns).
{ok,playfuns}
2> playfuns:bakacal(10).
1
3> playfuns:bakacal(11).
2
4> playfuns:bakacal(9). 
9
5> playfuns:bakacal(8).
8
6> playfuns:bakacal(0).
9
7> playfuns:bakacal(-1). 
8
8> playfuns:bakacal(-2).
7
9>

Look! So many examples, she can calculate the appropriate results!!

And the logic that goes inside also unifies beautifully!

Good at summarizing the rule of unity this is called wisdom ！！！！ ❄ ❄ ❄ ❄

This poor arithmetic machine, obviously a genius, but nowhere useful, but also be laughed at “hahaha you can only count to nine”. However, who knows, people behind the delicate and beautiful wisdom? You can imagine! Be laughed at by fool only can count to ⑨ of time, this arithmetic machine is how sad ！！！！ You want it to count up to what you want it to count up to…

Anyway, it’s the strongest!

Examples of languages that verify tail-recursion cases

So let’s get back to the business of checking tail recursion. 🐍

Again, using it as a mold is poor performance.

Here’s an example.

Scheme – `Chez - 9.5.4`

(define (rb num rem)
        (if (< num rem) 
            num 
            (rb (- num rem) rem) 
        )
)
;; (rb 3333333333 2) ;; ret: 1

So this is the first one, the middle one is wrong, it should be
(< num rem)That’s what I wrote
(num < rem).

Well, Chez was fast… The speed gap can be clearly compared with the Racket. The main time here, presumably, is the execution of the addition there.

Python :: `3.9.2, GCC 10.2.1`

Def rb(num, rem): if (num < rem): return num else: return rb(num - rem, rem) ### rb(3,2) # ret: 1 ### rb(33333333,2) # err: RecursionError: maximum recursion depth exceeded in comparison

Python defining functions on the REPL should require a few more line breaks at the end. After all, the biggest problem with the vernier caliper language is the wooden end mark…

Hy’s wonderful adventure

There’s a library on Python called HY, and it’s said to be a kind of Lisp.

In general, the definition of Hy is written as follows:

(defn remb [num rem]
  (if (< num rem) num (remb (- num rem) rem) )
)

Try it out and see:

=> (remb 4 2)
0
=> (remb 5 2)
1
=> (remb 3333333 2)
Traceback (most recent call last):
  File "stdin-c205eccd9236cc55bd83a0f3cdcf9af3deb02b56", line 1, in <module>
    (remb 3333333 2)
  File "stdin-97ee98165e108d7d2747d4e423030117a0891754", line 2, in remb
    (if (< num rem) num (remb (- num rem) rem) )
  File "stdin-97ee98165e108d7d2747d4e423030117a0891754", line 2, in remb
    (if (< num rem) num (remb (- num rem) rem) )
  File "stdin-97ee98165e108d7d2747d4e423030117a0891754", line 2, in remb
    (if (< num rem) num (remb (- num rem) rem) )
  [Previous line repeated 986 more times]
RecursionError: maximum recursion depth exceeded in comparison

Ah? ! Isn’t there tail recursion support? Am I wrong?

I looked around, and I found this: basically, they’re using macros, and they’re using things that look like keywords. There’s an example of a factorial that I’m not going to quote, but I wrote an implementation of my own modding, mimicking the error:

(defn rbloop [num_in rem_in]
  (loop [[num num_in] [rem rem_in]]
    (if (< num rem) num (recur (- num rem) rem) )
  )
)
;; (rbloop 33333 2) ;; ret: 1

There are two brackets after the loop. Inside each bracket, the one on the left is the name of the variable that will be used inside the loop, and the one on the right is the value that will be passed to it for the first call. That is, if you write tail recursion in Hy, you have to define the tail recursion structure inside the function.

. I think it’s just a sugar cycle…

The speed of the word, tried, the long number is really a long time did not come out, so it was cancelled.

Py’s wonderful adventures

I don’t know Python, so far there are two ways to do it:

Python Enable Tail Recursion Optimization! – SegmentFault think no
Remember one way to avoid recursive overflow in Python

For both:

The previous post was done using a Python language feature called a decorator;
The latter is addressed through a method called Y Combinator, which should apply to any language that can pass functions as values. As described in the second link, it looks like this: pass the function as a value to complete the call to the outgoing function without starting the call to the inside function, manually avoiding a stack when calling the inside function, then call the outgoing function again, and so on.

By the way, this Python article is really everywhere… The second link here is the one I found when I wrote the tail recursion for the following PowerShell…

Scala :: `2.12.13, its Java 11.0.10`

def rb (num: Long, rem: Long) : Long = { if (num < rem) num else rb(num - rem, rem) } ; // RB (3333333333L,2) // RB (33333333L,2) // RB (33333333L,2) // RB: LONG = 1

Although Scala is actually infinitely tail-recursive and does not have stack overflows, it is still a call function that can push (tree recursion can stack overflows) (this version).

In this respect, perhaps the standards of the same (if impure) functional languages do not quite match. The normal functional standard is that there is no (or can always be equivalent to no) stack crush, so even tree recursion does not have a stack overflow. (The only question is whether it will run out of allocated memory.)

But Scala’s long number is just as fast as Chez’s.

Also, Scala will do better with larger numbers.

I use it in the Scala REPL
rb(9333333333L,2), and the Chez interpreter
(rb 9333333333 2), to do the comparison.

The same Scala I installed directly with DNF in WSL (1) in Feodra. It uses OpenJDK, not GraalVM. The latter is said to be faster than the former.

JPG (2021-06-12) JPG (2021-06-12)

Java :: `Jshell - 11.0.11`

Long rb (Long num, Long rem)
{
    if (num < rem) return num ;
    else return rb(num - rem, rem) ;
}

// rb(3L,2L) // ret: $1 ==> 1
// rb(33333L,2L) // ret: $2 ==> 1
// rb(333333L,2L) // err: java.lang.StackOverflowError

This Jshell is in GraalVM.

If a function defined directly here has a static modifier, you get a warning like this:

The 'static' modifier is not allowed in a top-level declaration and has been ignored

However, the function can still be created successfully.

Of course, even Java11, even GraalVM, even new things like Jshell, will overflow the stack.

It could have been designed that way, or maybe there was a switch somewhere that I didn’t turn on.

Java, however, is said to have a way of doing something similar to tail recursion. Interested can see for yourself:

Tail Recursion in JAVA 8

Erlang :: `Erlang/OTP 24, Eshell V12.0, Windows-Version`

rb (Num, Rem) when Num < Rem -> Num ; Rb (Num, Rem) - > rb (Num - Rem, Rem) % % c (XXX). The XXX: rb (3, 2) % ret: 1% % c (XXX). The XXX: rb (3333333333, 2) % ret: 1

Please add the module header.

A lot less code than the genius arithmetic device above?

Because I don’t care about the negative numbers, and I don’t have a long variable name here, that’s all. 🙂

The long numbers here are a little slower than Chez and Scala.

If you’re just on the Erlang shell, you write anonymous functions. You need one more argument.

Rb = fun (N, R) -> RbIter = fun (N, R, _) when N < R -> N ; (N, R, F) -> F(n-r, R, F) end, RbIter(N, R, RbIter) end. % Rb(3,2). % ret: 1% Rb(3333333333,2). % ret: 1

At first, the syntax of the anonymous function was wrong. When I tested it on ESHELL, I found that the handwritten code on the phone was more pseudo code than pseudo code. There was nothing here or there… 😓

Speed, that long number, in Eshell using an anonymous function, for a long time…

Bash :: `5.0.17, x86_64 - redhat Linux -- gnu`

Bash Function

rb () { num="$1" rem="$2" && ((num < rem)) && { echo "$num" ; } || { rb "$((num - rem))" "$rem" ; }; }; ## rb 3 2 # out: 1 ## rb 33333 2 # exit... no out no err, just exit after few sec. ...

To avoid a lot of problems, writing as explicitly as possible on Bash has become my rule for Bash writing.

Think of standard output as a means of pulling data out, rather than using returns.

. When it comes to crunchy or Bash crunchy, a small number will be lost, nothing will be waiting for a second or two to come back…

Bash Script File

I’m just going to use exec here.

#! /bin/bash num="$1" rem="$2" && ((num < rem)) && { echo "$num" ; } || { exec /bin/bash "$0" "$((num - rem))" "$rem" ; }; ## bash trc.sh 3 2 # out: 1 ## bash trc.sh 33333 2 # out: 1

Here you can check the difference between exec and no exec. Suggest to use a less important machine to check otherwise don’t blame me for anything.

The formatting style in the script is not quite the same as before. Without special reason, actually use which is good, I just change taste 😐. (To be honest, the following branch of the script should be a little clearer…)

Of course, slow or slow. It’s probably mainly because this ((xx+xx)) is slow. I can count them at last, but it’s really slow.

`cd`Script File is a fantastic adventure!

In fact, if you just want to test the difference between Bash and exec, you can use the following:

#! /bin/bash dir0="${1:-0}" && cd $dir0 && { pwd ; } || { exec /bin/bash "$0" "$((dir0 + 1))" ; }; ## bash cdtr.sh # err: cdtr.sh: line 5: cd: (some num will be here): No such file or directory

If it’s executed, it’ll keep saying errors and you can’t find folders, so you can use this to determine how many times you recursed:

Put theexecDelete it, and the script doesn’t go very farSome of the problems ；
There areexecIf it does, it’ll just keep going up and up and up and up and up and up and up and down, unless you create a folder called bigger numbers before it gets to that point, and then it goes to that folder and it goes to that folder and it goes to that folderpwd 。

With a recursive script like this on Bash, some trial-and-error work is straightforward: execute a command, retry if it’s wrong, and don’t retry if it’s right. (Or vice versa?)

`cd`The Wonderful Adventure Function!

This takes advantage of a feature of exec: it discards commands above and below the text it is in, and any commands after it are not executed anyway. (Of course this is limited to the use of exec here)

Based on this, and some other messy ideas, I finally found a way to achieve tail recursion without generating files!!

Praise it ！！！！

A simple example:

tailcd () { count=${1:-0} && cd $count ; exec bash -c "$(declare -f tailcd)"' ; tailcd '"$((count+1))" ; }; ## run: bash -c "$(declare -f tailcd)"' ; tailcd'

Or even better:

tailcd ()
{
    count=${1:-0} &&
    cd $count ;
    exec bash -c 'tailcd '"$((count+1))" ;
} &&
export -f tailcd ;
## you can run,
`# use this:`  bash -c tailcd
`# or this:`  (tailcd)

The code above supports simple compression logic: you can simply replace the newline with a space and delete the consecutive space into one. Then the code can still execute.

It is recommended not to directly execute the tailcd function. The easiest way to write it is to write it with the curly brackets: (tailcd).

Running tailcd directly doesn’t mean it won’t work, you can try it, but if it stops running you’ll probably feel bad.

What’s the bad way? Try it for yourself. Maybe it can also increase experience!
:D

(It’s a process tree thing. Both bash-c tailcd and tailcd are designed to open child processes. Why open child processes? You have to do some research on your own
exec!)

In this way, the front did not succeed can not write a file!!

Bash Function

Why am I so obsessed with using functions on Bash instead of script files?

One of the reasons it’s important is that by defining a function, I can be sure of two things:

It won’t be tampered with, it’s exactly what I defined it to be, and I can easily override it with a new definition without interacting with the disk.
Its life cycle is clear, its reach is limited, and I don’t want a piece of software to just pop up in one place and not get cleaned up if I leave it alone.

rbex () { num="$1" rem="$2" && ((num < rem)) && { echo "$num" ; } || { exec bash -c "$(declare -f rbex)""$(echo '; ' rbex $((num - rem)) $rem)" ; }; }; ## bash -c "$(declare -f rbex)"'; rbex 3 2' # out: 1

So this is kind of a simple way of thinking about it. This will save a little more resources:

rbex () { num="$1" rem="$2" && ((num < rem)) && { echo "$num" ; } || { exec bash -c "$(echo rbex $((num - rem)) $rem)" ; }; } && export -f rbex ; ## bash -c 'rbex 3 2' # out: 1 ## echo rbex 3 2 | bash # out: 1 ## echo rbex 33333 2 | bash # will out 1 , but slow ... ## (rbex 3 2) # out: 1 ## (rbex 128 2) # out: 0

Tail recursion
bash -c "$(echo rbex $((num - rem)) $rem)"Is equivalent to:

bash -c rbex' '$((num - rem))' '$remThe effect of writing it this way.

The former space is automatically changed to one as a delimiter. So this allows me to use the former form and it doesn’t matter how many Spaces are attached to it
bash -cThe content is always consistent.

Here’s a tip:

Through thebash -cTo call a function in theexecTo the role.
$(declare -f rbex); $(declare -f rbex); $(declare -f rbexbash -cThe following orders.
However, I thought that since it isThe child processSo I just need toGlobalize the function I definedWhy don’t you just do it? withexport -f rbexIt will not be invalidated in any child process of the current process.

This way:

The logic that is defined can always exist: it can beexecThe premise of a function;
The life cycle of this always existing definition is reasonable, destroy when it should be destroyed, not destroy when it should not be destroyed;

So both of those things are satisfied.

In addition, these are all parameters
Not containing SpacesNumbers, so I don’t have to write it
"$((num - rem))"Or so
"'""$((num - rem))""'"Like this.

However, as a whole, there should be
"in
"The in
'in
'In the words, can be a little rigorous. For instance,
In the example above, if the content is passed as an argument with Spaces,I don’t know what’s going to happen.

If you believe that Spaces may be included, then quotation marks must be used to indicate that a whole is a whole. I won’t talk about it here, please
Add the necessary single and double quotation marks and test them.

Call the example to give a few more ways to write, you can think about why it can be written this way and choose their own way of writing. (Nobody should have the time to develop things in Bash… 🐌)

I prefer the braces. Because of simplicity. Also, the parentheses, you see it is not very familiar!! Remember Scheme! (Which shouldn’t be such a big deal, because it’s just like. Right now I can’t guarantee that I’ll be able to implement a Lisp on Bash using this approach… But who dare to interest can try) 🐍

Powershell :: `7.1.3`

function Rem-B
([int]$Num, [int]$Rem)
{
    if ($Num -lt $Rem) { return $Num }
    else { return Rem-B -Num ($Num - $Rem) -Rem $Rem }
} ;
## Rem-B 3 2 # ret: 1
## Rem-B 4 2 # ret: 0
## Rem-B 33333 2 # err: InvalidOperation: The script failed due to call depth overflow.

You can see that the return break is also useless.

But since it has pipes, let’s try it:

function Rem-B { process { $Num = $_[0] ; $Rem = $_[1] ; if ($Num -lt $Rem) { ,($Num,$Rem) } else { ,(($Num - $Rem),$Rem) } } } ; # #, (3, 2) | | Rem - B Rem - B | a - B | a - B | Rem called Rem called Rem - B # out: 1 \ n2 # #, (4, 2) | | Rem - B Rem - B | a - B | a - B | Rem called Rem called Rem - B # out: 0 \ n2 # #, (33333, 2) | | Rem - B Rem - B | a - B | a - B | Rem called Rem called Rem - B | a - B | a - B | Rem called Rem called Rem - B | a - B | a - B | Rem called Rem called Rem - B | | Rem - B Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B | Rem-B # out: 33123\n2

Why did I do that?

So if you recurse the pipe, just the (3,2) doesn’t come out.

We’ll have to look at that a little bit. In addition, a similar structure is also seen in some Y combinator papers.

🦑 Endless Y combinators

This section attempts to introduce something that has just been figured out: Y Combinator.

Extended reading on Y Combinator:

Understand the Y combinator from scratch — » Functor
Y Combinator – BAJDCC – Blog Garden
Y Combinator (Y Combinator) | The Little Schemer chapter 9 – zhihu
Functional programming in the Y combinator | not xi
Python Lambda implements the Y combinator – the carriage classmate

And two translations of a good book (an extended reading for an extended reading) :

The Chinese version of The Little Schemer | Lazy_Pig
The Little Schemer Notes 1.0 document

Antecedents feed

The chapter on Remb/rb was added, but by accident I found a Y combinator.

On closer examination, I think this is the essence of tail-recursive stack-free design.

But this combinator seems to be just a way to get anonymous functions to call their own…

I used Erlang’s anonymous functions to implement a RemB that works on Eshell, which is also much faster than the anonymous functions in the previous chapter.

Of course, the purpose of using Erlang here is that its presentation will give you a good idea of how to calculate.

Tempting the left foot on the right foot to heaven

The next part should be the easier part of the Y combinator knowledge.

But there is no Y combinator per se, just a rather silly way to have nameless functions (which are values) call themselves.

Erlang :: `Erlang/OTP 24, Eshell V12.0, Windows-Version`

Instead of following the rules of the lambda calculus, the anonymous functions defined here are bound to the variable name first.

(This is not the function name. The function has no name, it’s just a value. It’s just a name that’s bound to the value. But the call is written just like a normal function.

RembNourisherInsideRemb = fun (FuncNourisherInsideFunc) -> fun (Num, Rem) when Num < Rem -> Num ; (Num, Rem) when Num >= Rem -> FuncGotWithFuncNourisher = FuncNourisherInsideFunc(FuncNourisherInsideFunc) , FuncGotWithFuncNourisher(Num - Rem, Rem) end end , Remb = RembNourisherInsideEmb (RembNourisherInsideEmb). Remb(3,2). % RET: 1 Remb(333333,2). % RET: 1 REB (333333,669). % RET: 171 333333 REM 669. % RET: 171

Erlang does not support curialization, i.e. FuncE(FuncE)(X), which must first Func = FuncE(FuncE) and then Func(X).

But that’s okay, it’s just a matter of missing a pair of parentheses. I’ll give you a different way to write the variable names.

Scheme :: `Chez - 9.5.4`

Here’s how the lambda calculus frees itself up by not binding anonymous functions to variable names:

Not familiar? Take a look at the following to get familiar:
(1 + 1); ret: 2 (+ 1 1 1) ;; ret: 3 ([lambda (x) (+ 1 1 x)] 3) ;; ret: 5 ([lambda (x y) (+ x y)] 3 4) ;; ret: 7 ([lambda (a x y) (+ x y)] + 3 4) ;; ret: 7
After the semicolon is a comment, I have written the results of the semicolon in the comment, of course, it is best to execute the following try. From simple to complex, write it yourself, execute it, and be aware of the errors that trigger it, because that’s where progress is.

Scheme, a Lisp dialect, is bordered by parentheses and separated by Spaces, making it extremely flexible to use. Whitespace characters such as a newline in a row of any number of Spaces are semantically the same.

(
    [lambda (func-nourisher-inside-func)
        [lambda (num rem)
            (if (< num rem) num 
                ((func-nourisher-inside-func func-nourisher-inside-func) (- num rem) rem)
            )
        ]
    ]
    
    [lambda (func-nourisher-inside-func)
        [lambda (num rem)
            (if (< num rem) num 
                ((func-nourisher-inside-func func-nourisher-inside-func) (- num rem) rem)
            )
        ]
    ]
)

All right.

This whole mess up here, it has two little mess up here. If you look closely, they’re exactly the same. In parenthesises, this is to the right of the equal sign of funcgo with funcnourisher = FuncNourisherInsideFunc(FuncNourisherInsideFunc).

That is, the bottom blob is the argument, is substituted into the top blob, and the top blob is inside the parentheses that it’s in, is called, and the argument is the bottom blob.

You can also write this by the way:

(
    [lambda (be-nourishering)
        (be-nourishering be-nourishering)
    ]
    
    [lambda (func-nourisher-inside-func)
        [lambda (num rem)
            (if (< num rem) num 
                ((func-nourisher-inside-func func-nourisher-inside-func) (- num rem) rem)
            )
        ]
    ]
)

If this method were used for Erlang, there should be no need for variable names either. After all, although the fun (X, Y) – > fun (Z) – > X + Y Z end end (1, 2) and (4). (fun (X,Y) -> fun (Z) -> X+ y-z end end(1,2))(4). Fun (X,Y) -> fun (Z) -> X+ y-z end end(1,2)) Fun (X,Y) -> X+Y end(1,2). There’s no problem writing it this way.

When used, it is used like this — the anonymous function definition itself is used as the function name:

((
    [lambda (func-nourisher-inside-func)
        [lambda (num rem)
            (if (< num rem) num 
                ((func-nourisher-inside-func func-nourisher-inside-func) (- num rem) rem)
            )
        ]
    ]
    
    [lambda (func-nourisher-inside-func)
        [lambda (num rem)
            (if (< num rem) num 
                ((func-nourisher-inside-func func-nourisher-inside-func) (- num rem) rem)
            )
        ]
    ]
) 3 2 )

Or:

((
    [lambda (be-nourishering)
        (be-nourishering be-nourishering)
    ]
    
    [lambda (func-nourisher-inside-func)
        [lambda (num rem)
            (if (< num rem) num 
                ((func-nourisher-inside-func func-nourisher-inside-func) (- num rem) rem)
            )
        ]
    ]
) 3 2 )

The result is 1.

The rule of formatting above is that a pair of parentheses must be aligned top to bottom or left to right. Braces are used for the parts that will not be called (that is, the parts that just define the content), and parentheses are used for the parts that will (syntactically any parentheses are lines). Do not wrap the first few items in brackets, depending on the situation, to distinguish between the head and body of the definition. Some say people shouldn’t count parentheses. I agree with you. That’s why parentheses shouldn’t be at the end. While that sounds simple, it defeats the purpose of parentheses. Scheme’s S-expressions make the language flexible and rigorous, which is one of its strengths, and it needs to be used to its full advantage.

Of course, some of the characters added to the call example are not specifically formatted this way. Mainly because I’m lazy, and the new part is easy, so I don’t think it’s necessary.

There are insufficient

The above methods are called poor man’s Y 🙃 in Wang Yin’s slide (which is not necessarily an accessible snapshot). (It could be that one of Wang’s talented teachers calls them that.)

This is obviously not enough if you treat function definitions as determinate values and function calls as indetermalized values, and if you assume that indetermalized values are bound to result in overcrowding.

So, this logic doesn’t really accomplish its purpose: after all, the goal here isn’t just to make anonymous functions tail-recursive.

To move forward

Let’s do a more general Y combinator.

A good set of derivations can be seen from the paper wood city article.

Searching around, including the PPT of Wang Yin, basically did the following things:

To get apoor man's Y
Abstract what appears to be repeating (withlambda )
letThe target function generator inside the target function (func-nourisher-inside-func) takes effect by passing a concrete logical block (takes effect, that is, the call occurs)
thefunc-nourisher-inside-funcThe piece itself is a separate piece and then the recursive part is passed into it and it takes effect.

The identifier for the following code, derived from the comic:

From sprouting niang wikipedia page: https://zh.moegirl.org.cn/%E5%8D%83%E5%A4%9C (A7 E5 A7 E5% % % 90% % % 90)

🦎

Here is a complete example of remb implemented in this way. (With my explanation) This time, I’ll use Scheme first and then Erlang. Because the anonymous function seems to be the S-expression is the most intuitive.

Scheme :: `Chez - 9.5.4`

This part is still implemented in Chez, even if it’s not as convenient as other Scheme implementations, such as pattern matching. Because I thought it was a very concise and ingenious Scheme implementation, I decided to stick with Chez and read the official documentation if I couldn’t get around to it (I already translated and took a copy offline 🐉 anyway).

The following code style is, as I see it, easy for even human visual ability to assist in understanding code. Because I feel this is the hierarchy is clear, and not the boundary is unclear.

I don’t guarantee that it will always benefit anyone’s habits of mind. So, if you’re not used to it, it’s best to format yourself into something you’re comfortable with. 🐚

(
    (
        [lambda (koyuu)
            (
                [lambda (umareru)
                    (umareru umareru)
                ]
                
                [lambda (chiyo)
                    (
                        koyuu
                        
                        [lambda (pakotte)
                            ((chiyo chiyo) pakotte)
                        ]
                    )
                ]
            )
        ]
        
        [lambda (chiyo-oma)
            [lambda (pako-bako)
                (record-case pako-bako
                    [(remb) (num rem)
                        (if (< num rem) num
                            (chiyo-oma [list 'remb (- num rem) rem])
                        )
                    ]
                )
            ]
        ]
    )
    
    '[remb 3 2]
)

The call requires only one argument to be passed. I’m using record-case, so the first item in the list that gets passed in must also be an atomic or symbolic variable, and I’m using remb here of course.

Presumably using pattern matching on Chez seems to be the way to go. Not really, I just went through Chez’s documentation and got the code done in an hour or two. Why is there such a hurry? Because I was so excited to finalize the name of the above variable… 🐚 🐚 🦑 🦑)

In addition, if you are familiar with the above comic, especially the original, you will find that the naming of the above code will probably help you understand the relationship between the anonymous functions. If you don’t know what I’m talking about, you’re a good, healthy kid, so just ignore this. Of course, you can also be a great child full of exploration spirit, before this, please do a good and happy face the abyss of consciousness. 🙃

(laughing, laughing…)

🐍

In the code above, which was originally tail recursion, at the key recursion place, it is essentially just passing in the deterministic value that is obtained without recursion. If you can pass in two arguments ((chiyo chiyo) pako1mata pako2mata), then chiyo-oma has been copied with two definite values, and that’s all.

It can be seen that the realization of the real tail back to rely on a thousand night sister…. 🦀 🦀

Thousand night sister is the best! . 🦀 🦀

Finally, a Racket (V7.9 [CS]) implementation and use is attached:

(
    (
        [lambda (koyuu)
            (
                [lambda (umareru)
                    (umareru umareru)
                ]
                
                [lambda (chiyo)
                    (
                        koyuu
                        
                        [lambda (pakotte)
                            ((chiyo chiyo) pakotte)
                        ]
                    )
                ]
            )
        ]
        
        [lambda (chiyo-oma)
            [lambda (pako-bako)
                (match pako-bako
                    [(list num rem)
                        (if (< num rem) num
                            (chiyo-oma [list (- num rem) rem])
                        )
                    ]
                )
            ]
        ]
    )
    
    '[333333 669]
)
; ret: 171

The purpose of pattern matching is to break up the pako-bako argument list.

Here’s a quick rundown of what’s been going on:

Here’s how to use Chinese as an identifier:

((([lambda (with logic) ([lambda (to be generated) (to be generated))] [lambda (to be generated)) [lambda (to be generated)) [lambda (to be generated))])] )] [lambda (match (list num rem) (if (< num rem) num (list (-num rem) rem))])] ]) '[333333 669]); ret: 171

That seems a little bit more specific.

One obvious fact is that in lambda calculus, there are still names; It’s just like this: My name is in yours, and yours is in mine; What I need is in you and what you need is in me.

Like love 🦀

Erlang :: `Erlang/OTP 24, Eshell V12.0, Windows-Version`

With the Scheme version above, it’s easy to write the Erlang version.

Erlang also does not assign variable names.

The square brackets above are definitions (this is the specification I gave myself), and the brackets are calls, so in Erlang it would be: Move the parentheses down, indent the function name or the anonymous function being defined to the left, replace “end” with “lambda” with “fun” and note that there is -> between the header bodies (in short, there must be -> after every fun) ), remove the extra parentheses and simply patch up the syntax.

( fun (KoYuu) -> fun (UmaReru) -> UmaReru(UmaReru) end ( fun (ChiYo) -> KoYuu ( fun (PakoTTe) -> (ChiYo(ChiYo))(PakoTTe)  end ) end ) end ( fun (ChiYo_OMa) -> fun ({Num, Rem}) when Num < Rem -> Num ; ({Num, Rem}) when Num >= Rem -> ChiYo_OMa({Num - Rem, Rem}) end end ) ) ({333333, 669}) . % ret: 171

There should be no extra parentheses at the top.

And the way that we write it when we call it, the way that we write it, is fun(a,b)(c,d), and whether it’s good or not is a matter of opinion, but I don’t know at this point. It can be used only if it is supported.

But I think it’s not so bad to force it to be (fun(a,b))(c,d) instead of being allowed to write it that way. Because that really emphasizes the essence of Curialization: you get a function out, and then you call it.

Python :: `3.9.5, GCC 10.3.1`

Moving from Scheme to Python is pretty easy.

I use the Chinese variable name in Python. Have found a good proposition:

At the beginning, I hoped that he would contribute more to the maintenance, but I felt that his motivation was not great at that time. It took me a week to make the prototype. To my surprise and delight, she submitted the “copycat” PR on September 28, and continued to improve it. After October, I did nothing but merge the PR.

We can see the role of Chinese naming in encouraging novices to participate in open source projects.

Once the basic architecture of an open source project is in place, users (often non-programmers) should be more motivated to learn the code if the project itself is named in Chinese. It’s not that English naming will necessarily discourage participation, but it will deter a large number of people.

I think that makes sense.

This is what it looked like when I started:

(((lambda with logic: (lambda with logic: (lambda with logic: (lambda with logic))) (lambda with logic: (lambda with logic) (lambda * recursive action parameters: (Generator (Generator)(* Recursive time action parameter)))))))(lambda line logist: (lambda num,rem: (num if (num < REM) else (num -REM, REM))))) (333333, 669)) ## ret: 171

In this case, anonymous functions are enclosed in parentheses to ensure that they can be called without a name. However, this is the operation! This gives Python another clear sign of the end of a definition!!

See! Python is finally not complete
Vernier caliper language!!! 🍾 🍾 🥂 🥂

Who said that the head of a dog is complete
Vernier caliper languageYou can use a bunch of pure ones like this
lambdaBlow up his Python!

🦉 🦉 🦉 🦞 🦞 🦞 🦔 🦔 🦔

And, from that point of view, while Python doesn’t have a match-case yet, it seems like lambda can be used to pretend it does… At least the ability to unpack is possible. But it’s just a split argument list… It’s not unpacking.

Actually,
match-caseIt does in Python, but not yet. It was only allowed at the beginning of this year.

To check the
thisand
thisSay, want to
3.10There is. And now,
2021-07-03) The latest official version of the official website is still
3.9.6. (I also specifically tried to update my own WSL
pythonIf you look closely, you will see that the version I used for this part is different from the one above. A little bit different…

Oh, and that piece of code, if you’re in Python, you can get rid of a lot of Spaces. Correspondingly, the parentheses cannot be called too far from the function name (not to the next line). Then the equivalent can be written:

(lambda with logic: ((lambda to be generated: (to be generated (to be generated))) (lambda to be generated logic: (lambda * Recursive action parameters: (Generator (Generator)(* Recursive time action parameter)))))))(lambda line logist: (lambda num,rem: (num if (num < rem) else (num -rem, rem)))) (333333, 669) # ret: 171

I could keep decreasing the parentheses, but I don’t think I need to. If I lower the parentheses, I won’t be able to see the hierarchy.

In addition, from this simplification, we can actually see that such scalafun(Args1)(Args2)… What is the nature of the Currie tone of writing.

But we haven’t done that yet, although we’ve managed to do it in Python as well.

We wanted Python to be tail-recursive, but now if you replace 669 with 1, you’ll get an error message. I just got an error message.

~~<! We will find out the reason tomorrow (but this may be recursive too) ->~~

Borrows the idea from the link mentioned earlier:

>>> r = ( ... Lambda Logic:... (... (... Lambda to be generated:... (... To be generated (to be generated)...) ...). (... Lambda Generator:... (... The logical (... Lambda * Recursive action parameter:... (... Lambda: Generator (Generator)(* Recursive action parameter)... #^# This part will be passed to the external variable r... # # | so call below (it's just one call) is also empty parentheses) r ()... )... )... ...). (... Lambda line logers:... (... lambda num,rem : ... (... num if (num < rem) ... Else line logic (Num-REM, REM...) ...). ) (33333, 2) >>> r <function <lambda>.<locals>.<lambda>.<locals>.<lambda>.<locals>.<lambda> at 0x7f5215545ee0> >>> r = r() >>> r <function <lambda>.<locals>.<lambda>.<locals>.<lambda>.<locals>.<lambda> at 0x7f5215545e50> >>> while callable(r): R = r() #<-# This part is equivalent to manually running through each level of recursion using while... >>> r 1 >>>

So it doesn’t burst the stack…

So… You end up using Python’s own loop in Python… 🤢

Solve crimes! Python is an imperative language with no problem.

But Python’s imperative style of language is kind of fun: you can do this or that, but it’s still…

Unfortunately, and thousands of nights with the elder sister action can not be carried out automatically… 😭 is essentially a machine instruction loop… Thousand nights sister did not… Damn it… 😭 😭 😭

The echoes

Now, a Y combinator is just a way to pass a generator that generates itself into it, and the generator itself generates its own generator… It’s a little tricky, but it’s also a way to keep a piece of information alive for the duration of execution through recursion.

Now it seems that before genius with a burst stack! The use of exec bash-c and “$(declare -f function name)” mentioned in the ❄ section is similar, but bash is just a bit more clueless, splice together a set of defined code before going somewhere undefined.

Let’s write an example that executes a command and retries after an error. The style of the printed message borrows from Erlang’s return.

redoer () { cnt=${2:-0} cmd="${1:-echo xargs-i is {}}" && bash -c "$cmd" && { echo \{ok, {}, $cnt\} ; } || { echo \{err, {}, $cnt\} ; exec bash -c "$(declare -f redoer)""$(echo ' ; ' redoer "'$cmd'" $((cnt+1)) )" ; }; };

So that’s the definition. Using the example can be a hassle, mainly because I’m not sure what is being batched into the {} position. But it doesn’t matter, I’m sure you can understand it. 😘

This is a use case that should work. You will see from the error message that the download of a branch was wrong and then retried later.

# # this is to create a shallow clone git clone - the depth of 1 - https://ghproxy.com/https://github.com/cisco/ChezScheme cisco/ChezScheme # # Echo 'cisco/ChezScheme rustdesk/rustdesk tsasioglu/ total-uninstaller elixir-lang/ex_doc triska/the-power-of-prolog hashicorp/vagrant' | xargs -P0 -i -- bash -c "$(declare -f redoer) ; redoer 'git clone -q --depth 1 -- https://ghproxy.com/https://github.com/{} {}' "

I wrote here the error message is: whether the success, the content of {} is filled, the number of retry these three.

The example above is pulling a remote Git library. At the same time, pull several.

But generally speaking, this is what this thing is for: you have a bunch of.jpg addresses, and that.jpg is a very simple 1.jpg 2.jpg…. In this case, if you want the computer to load it in bulk as much as it can, and re-execute it as quickly as it fails, but you don’t want to write too much code, then this definition comes in handy.

The above needs can be written as follows. Let’s assume your full URL looks something like this:

https://shenqibaobei.xx.yoo/pics/1.jpg https://shenqibaobei.xx.yoo/pics/2.jpg https://shenqibaobei.xx.yoo/pics/3.jpg ...  https://shenqibaobei.xx.yoo/pics/1024.jpg

And you’ve already created a folder called guigui to hold these lovely images, so, after executing Redoer’s definition, just go to the following code:

seq 1 1024 | xargs -P0 -i -- bash -c "$(declare -f redoer) ; redoer 'wget -q https://shenqibaobei.xx.yoo/pics/{}.jpg -O guigui/{}.jpg' "

Make sure you have this folder, otherwise it will have multiple concurrent processes retrying, and I don’t know what will happen.

🐙 🐙 🐙 🐙

EOF

🐊

Follow the reprinted

This article was reprinted, please indicate the author and the source: https://segmentfault.com/a/1190000040173495

My wonderful adventure of recursion

preface

Why tail recursion?

Why Erlang?

🦑 From recursion to tail recursion

Train of thought

case

factorial

Erlang – Tree

Erlang – Tail

% % % %

Fibonacci sequence

Scheme

Erlang – Tree

Erlang – Tail

% % % %

The list is filtered by condition

Scala

Erlang – Tree

Erlang – Tail

% % % %

🦑 Genius and bursting stack! ❄

Way to

Ice clever genius arithmetic ❄❄❄

Examples of languages that verify tail-recursion cases

Scheme – Chez - 9.5.4

Python :: 3.9.2, GCC 10.2.1

Hy’s wonderful adventure

Py’s wonderful adventures

Scala :: 2.12.13, its Java 11.0.10

Java :: Jshell - 11.0.11

Erlang :: Erlang/OTP 24, Eshell V12.0, Windows-Version

Bash :: 5.0.17, x86_64 - redhat Linux -- gnu

Bash Function

Bash Script File

cdScript File is a fantastic adventure!

cdThe Wonderful Adventure Function!

Bash Function

Powershell :: 7.1.3

🦑 Endless Y combinators

Antecedents feed

Tempting the left foot on the right foot to heaven

Erlang :: Erlang/OTP 24, Eshell V12.0, Windows-Version

Scheme :: Chez - 9.5.4

There are insufficient

To move forward

Scheme :: Chez - 9.5.4

Erlang :: Erlang/OTP 24, Eshell V12.0, Windows-Version

Python :: 3.9.5, GCC 10.3.1

The echoes

EOF

Follow the reprinted

Related Posts

Bash Tips 02: Construct relative paths

-bash: /bin/rm: Argument list too long

Bash Tips 01: Get the path to the script itself

`% % % %`

`% % % %`

`% % % %`

Scheme – `Chez - 9.5.4`

Python :: `3.9.2, GCC 10.2.1`

Scala :: `2.12.13, its Java 11.0.10`

Java :: `Jshell - 11.0.11`

Erlang :: `Erlang/OTP 24, Eshell V12.0, Windows-Version`

Bash :: `5.0.17, x86_64 - redhat Linux -- gnu`

`cd`Script File is a fantastic adventure!

`cd`The Wonderful Adventure Function!

Powershell :: `7.1.3`

Erlang :: `Erlang/OTP 24, Eshell V12.0, Windows-Version`

Scheme :: `Chez - 9.5.4`

Scheme :: `Chez - 9.5.4`

Erlang :: `Erlang/OTP 24, Eshell V12.0, Windows-Version`

Python :: `3.9.5, GCC 10.3.1`