Recursion

Return to: Chialisp

Important excerpts from the documentaiton: https://chialisp.com/docs/clvm/dive_into_clvm#programs-as-parameters :

The core CLVM does not have an operator for creating user defined functions. It does, however, allow programs to be passed as parameters, which can be used for similar results.

Here is a puzzle that executes the program contained in 2 (the first solution argument) with the solution (12).

brun '(a 2 (q . (12)))' '((* 2 (q . 2)))'

24

Taking this further we can make the puzzle run a new evaluation that only uses parameters from its old solution:

brun '(a 2 1)' '((* 5 (q . 2)) 10)'

20

We can use this technique to implement recursive programs.

Added gneale 20210818:

brun '(a 2 1)' '((+ 5 (q . 3)) 10)'

13

Added gneale 20211119:

brun '(a 2 1)' '((* 4 (q . 2)) 10)'

36

NOTE:This is because position 4 inside ((* 4 (q . 2)) 10) is * which is the same as the number 9.

Explanation Items:

https://chialisp.com/docs/clvm/lang_reference#control-flow

a means "apply" (a P A) 

Evaluate value P as a program with value A as its environment.

Note that this executes P in what is called a new environment. Using integers to reference values in the solution will reference values in A.

Personal NOTE: An environment is essentially just a new binary tree attached to an existing branch of a binary tree. So in the above example P executes in a new environment.