" ___ ____ __ _ ___ __ _ _ ____ ~ " | |_) | |_ / /` | | | | |_) ( (` | | \ \ / | |_ ~ " |_| \ |_|__ \_\_, \_\_/ |_| \ _)_) |_| \_\/ |_|__ ~ " _ __ __ ___ ___ ~ " | |\/| / /\ / /` | |_) / / \ ~ " |_| | /_/--\ \_\_, |_| \ \_\_/ ~ " ____ _ ___ ___ _ __ __ __ _ ~ " | |_ | | | |_) / / \ | |\ | / /\ / /` / /` | | ~ " |_| |_| |_|_) \_\_/ |_| \| /_/--\ \_\_, \_\_, |_| ~ " When sourced, this Vimscript file constructs a macro in the "q register " that will calculate the Nth value in the Fibonacci sequence for the number " under the cursor when the macro is invoked. " +--------------------------------------------------+ ~ " | | ~ " | If you just want to try it out, you can skip | ~ " | all the explanation by simply entering this | ~ " | command: | ~ " | :so % | ~ " | | ~ " +--------------------------------------------------+ ~ " Introduction ~ " ============ ~ " One of my favourite features in Vim is macro recording. I love how the " incredibly simple mechanism of letting you record keystrokes converts the " standard normal mode commands into a RIDICULOUSLY powerful automation tool. " Any macro recording ENTHUSIAST will soon discover a neat little trick: the " RECURSIVE MACRO. By making the last step of a macro be the invoking of " itself, you can run the macro tens or thousands of times with a single |@| " command, performing MASSIVE numbers of laborious edits almost instantly. " After using these for a while it occurred to me that really what this gets " used for isn't a recursive process at all. It's just an iterative loop. " *Syntactically* it's recursion, but *semantically* it's 10 PRINT VIM FTW 20 " GOTO 10. And then I got to thinking, can you implement a more traditionally " recursive algorithm in a macro recording? " And what is the classic Introduction-to-Recursion algorithm that you'll find " in any CompSci 101 course? Okay yeah it's the factorial function, but what's " the one I thought of first when deciding to do this? " La Fibonacci! " The Fibonacci Algorithm ~ " ======================= ~ " The Fibonacci sequence is a series of numbers where each value is calculated " by adding the previous two numbers together: > " 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... " If you google 'recursive fibonacci' and look at the top few results, you're " likely to find an algorithm that looks something like this: > " function fib(N) { " switch (N) { " case 0: return 0 " case 1: return 1 " default: return fib(N - 1) + fib(N - 2) " } " } " UNfortunately, it's IMPOSSIBLE to translate this directly into a recursive " macro, because the only way we have of ending the macro 'function' is to " cause an 'error', and as soon as we do this, ALL computation stops. There is " no way of returning the value from e.g. the call to fib(N - 1) and then " adding something to this value. Weak. " FORtunately, COMPUTER SCIENCE has a solution to this. Instead of using the " algorithm above, we can use a 'tail-recursive' algorithm. This is one where " the recursive call is at the end of the function. i.e. No computation takes " place *after* the recursive call. " Using MATHS, it's actually possible to translate ANY recursive algorithm " into a tail-recusive one. Astounding! " But I just barely scraped through my Computer Science degree, so here's an " example of a tail recursive fibonacci function that I copied off the " internet: > " function _fib(N, left, right) { " switch (N) { " case 0: return 0 " case 1: return right " default: return _fib(N - 1, right, left + right) " } " } " " function fib(N) { " return _fib(N, 0, 1) " } " Basic Method ~ " ============ ~ " What do we need to implement this algorithm as a recursive macro? " Our basic approach is going to be to build little bits of functionality " from normal mode keystrokes, which we are going to store in the alphabetical " registers and invoke via the standard macro run command: |@| . " Each register essentially contains a *tiny* function that you can call with " |@| . " Next, we need to handle that 'switch' statement. The trick here is to write " the keystrokes required to perform each 'case' as a single line in the " buffer. If we place these lines in order at and above the cursor, then we " can move to the line corresponding to the value of N passed in by moving " upwards with |k| the required number of times. Once we're on the correct " 'case' line, we can yank the line's contents and then execute the code by " running the yank register as a macro. Sneaky! " Finally, we need some method of addition and subtraction. Vim's normal mode " provides this via the |CTRL-A| and |CTRL-X| keystrokes. " The RULES of the Game ~ " ===================== ~ " In order to prevent this from being an EVEN MORE pointless endeavour than " SOME would claim it already is, when I started working on it I decided to " disallow certain Vim features: " Reasonable Restrictions: ~ " ------------------------ ~ " - No Ex commands, " " - No expression register, (see |:help| |quote=|) " " - No Vimscript functions, " The above would make this task EASY and therefore BORING. So: no " programmatic scaffolding, and other than the aforementioned " increment/decrement number commands, nothing that facilitates ARITHMETIC. " - Must work regardless of position of number in file (so long as it is a " standard Vim |word|). " This one, on the other hand, is really just a matter of *panache* " Unreasonable Ones. Why Did I Impose These on Myself? ~ " ---------------------------------------------------- ~ " - No searches, " " - No setting or jumping to marks, " " - No storing state in registers: only macros! " " - Avoid CLUTTERING up the buffer with state: only do it when absolutely " necessary and leave it there for the shortest time possible, " " - Other than the fib and _fib functions, no storing macros in " alphabetical registers. " " It's actually possible to encapsulate the entire algorithm within just TWO " macros (Type |622G| to see this version.) But for EDUCATIONAL PURPOSES " only, when constructing the macro in this file, I've used alphabetical " registers to break down the computation into smaller pieces. This is " purely to make it easier to to understand, though. During the running of " the macro, no *further* alphabetical registers may be used for storing " macros (or anything else!) " There's not really a good argument for why any of the above shouldn't be " allowed. They just made me feel FANCY. " Implementation ~ " ============== ~ " Let's build this thing! " " Because I am a Vimscript file and not a person typing at a keyboard, I can't " record the macro with the |q| command, so we're going to build it by " directly setting the register contents with |:let| commands. One little " bit of housekeeping: you can include an *ESC* character or other control " characters in the string that you pass into a |:let| command by using " Vim's angle-bracket notation: a string containing an *ESC* looks like " this: > "\" " And one containing a |CTRL-A| looks like this: > "\" " Fibonacci Function ~ " ------------------ ~ " Let's start with our fib function! We are going to store this in the " "q register, because that is the register I most often use for my macro " recordings. > let @q = "@p@fIFibonacci: \" " What steps does this macro take? " *@p* play back macro "p " *@f* play back macro "f " *IFibonacci:* *\* " insert the label "Fibonacci: " at the start of the line, and then " exit insert mode. " Okay, so what does the macro in register "p do? > " Preamble ~ " -------- ~ " > let @p = "yiwo\pA 0 1\2b" " *yiw* yank the number under the cursor " *o\* add a new line below the cursor " *p* put the number you yanked at the start of the line and then " A 0 1 append the text ' 0 1' " ** leave insert mode, and then " *2b* move back two words to place the cursor back on the first number. " ASTUTE readers will have noticed that the new line now contains the " contents: '[N] 0 1' which looks SUSPICIOUSLY similar to the arguments we " want to pass into the _fib function. COINCIDENCE? Read on to find out! " So, the "p stands for 'preamble'. What do you think the "f might " stand for? " _fib Function ~ " ------------- ~ " "f stands for 'underscore-fib'! > let @f = "@c@j@s@0@d@0" " Okay, so the macro we're storing in "f just plays back a bunch of other, " as yet undefined, macros. Lets define these: " Case-Writing Macro ~ " ------------------ ~ " "c is for 'case'! " First we are going to add three more lines to the buffer, above the current " cursor position, each containing one of the 'cases' from the switch " block in the fib() function. > let @c = "@z@o@n3+" " *@z* play back "z " *@o* play back "o " *@n* play back "n " *3+* move down three lines, placing the cursor on the first non-blank " character. " YAY More macros! Let's continue. " Zero case ~ " --------- ~ " "z stands for 'zero'! > let @z = "Occ0\\\" " Okay, finally we are actually doing something instead of just calling more " and more macros: " *O* create a new line and insert " *cc0* 'cc0' " *\\* " in insert mode, |CTRL-V| tells Vim that the next character " should be inserted literally, so this will insert an *ESC* into " the buffer " *\* leave insert mode " So the "z macro will insert a line above the cursor which contains the " contents *cc0* followed by a literal *ESC* character. These, the " more EAGLE-EYED of you will already have spotted, are the keystrokes " required to |cc| change a line, enter a zero, and then exit insert mode. " This is the code that writes out the result when executing our 'zero' case! " But we're not actually *running* the code here. We're just writing it into " our buffer. " One case ~ " -------- ~ " "o stands for 'one': > let @o = "Od2w\" " *O* again, create a new line above the cursor and insert: " *d2w* 'd2w' " *\* and leave insert mode " RECALL that our three parameters are simply written on the current line. To " 'return right' we just need to delete the first two numbers, which the " keystrokes *d2w* will achieve. " Man, writing recursive macros is EASY. " Default case ~ " ------------ ~ " "n stands for 'N>1'. " This one's a teensy bit longer. > let @n = "O\\g_yiwA \\p2ge\\daw@b@a\\0@f\" " *O* Are you noticing a pattern? Create a new line above the cursor and " insert keystrokes that: " *\\* " same trick as before: we use |CTRL-V| to allow us to insert a " |CTRL-X| command in the macro that will subtract one from *N* " *g_* jump to the last non-blank on the line " *yiw* yank the number the cursor is now on: the 'right' parameter " *A* *\\* " append a space to the end of the line and exit insert mode " *p* put the copy of 'right' that we just yanked " *2ge* jump two words backwards to place the cursor on 'left' " *\\* " We are going to perform addition by passing 'left' as a count to the " normal mode |CTRL-A| command. But 'left' might be zero, which " would BREAK EVERYTHING (or at least, it would break our addition: if " you pass a |count| of 0 to |CTRL-A| , it adds one instead of " doing nothing), so we add one to 'left' now, also by using " |CTRL-A| , and we'll subtract one from the result of our addition " later to account for this. " *daw* delete 'left'. This operation will save the value deleted in the " 'small delete register' "- . (See |:help| |quote-| for more " details.) " *@b@a* run a couple of macros to do *something*. We'll come back to this " in a minute. " *\\* " subtract one from our updated 'right' to balance out the addition we " did a couple of steps ago " *0* move back to the start of the line " *@f* recurse, recurse! " *\* Finally, we leave the insert mode that we started with the |O| " command at the start of the "n macro. " So, ignoring *@b@a* for a second longer, the "n macro writes out a line " of code that, when run as a macro, will change the line the cursor is on " from: " " N left right " " into " " N-1 right right " " leaving 'left' in the small delete register "- . You'll recall that our " goal is to get to: " " N-1 right left+right " " ...so *@b@a* just needs to... " Perform Addition ~ " ---------------- ~ " We now have the value of 'left' stored in the small-delete register "- . " Using normal mode commands, there's no way to add this *directly* to the " copied value of 'right' at the end of the line, so the macro we're going to " store in "b doesn't perform the addition *itself*: instead it writes out " normal mode commands that CAN do this into the buffer, and then it " immediately yanks the commands, storing them in the yank register "0 so " we can execute them as a macro. > let @b = "O\-\s\\\0y$dd" " *O* create a new line above the cursor and enter insert mode " *\-* in insert mode, |CTRL-R| allows you to insert the contents of a " register directly into the buffer. Using it with *-* will enter the " contents of the small delete register "- i.e. the last delete " command that removed less than a line. In this case: the value of " 'left'! " *\* leave insert mode " *s* when we deleted 'left', we did it with the command |daw| , which " will also have deleted the trailing space. We use |s| to delete " this space and enter insert mode " *\\* " insert a literal |CTRL-A| " *\* exit insert mode " *0* move to the very start of the line " *y$* yank the entire contents of the line, saving it in the yank " register " *dd* delete the line we just added. " So when "b is run, if the small delete register contains e.g. the number " 4, the yank register will be populated with a number 4, followed by a " literal |CTRL-A| character. The |CTRL-A| normal mode 'add' command " takes a count, so we now have a macro in "0 that will add the contents " of the small delete register to the number under the cursor! " To perform the addition, we just need a macro that will move to the " correct position in the line, and then run the macro in the yank register: > let @a = "g_@0" " *g_* move to the last non-blank character on the line " *@0* play back the macro in the yank register "0 " (In case you were wondering, "a stands for 'Add', and "b stands for " 'Build a macro that performs addition'. It's hard to name functions when " they all have one-letter names!) " Returning to "c, we can now see more clearly what it does: " *@z* write out a line of code that handles our *zero* case " *@o* write out a line of code that handles our *one* case " *@n* write out a line of code that handles our *N* case " *3+* Move back down to the line we started on " When run, the "c macro writes out code for the three 'cases' into the " three lines in the buffer above the cursor: the zero case is one line up, " the one case is two lines up, and the N case is three lines up. " Select Case ~ " ----------- ~ " Let's presume for the time being that we have the number of lines we need to " move up to get to the correct case stored in the yank register "0 . Then " we need a macro that: " - moves up the number of lines stored in yank register, " - yanks the whole line, " - returns to the home row. " Again, like in the macro we stored in "b , we can't setup the macro we " need directly with a |:let| command, so instead we're going to write an " intermediate macro that writes the macro we *really* need into the " buffer and then yank it for playback. > let @s = "O\0-y$\0+\^y$dd" " *O* Begin a new line above the cursor and start insert mode. " *\0* We use |CTRL-R| again to insert the contents of a register " into the buffer. This time we pass it *0* to access the yank " register, inserting the number of lines we need to move up to get to " the desired 'case'. " *-* The |-| command takes a |count|, so when the macro we're writing " is run, we will move up the number of lines that we just wrote into " the buffer, placing the cursor at the start of the line. " *y$* yank the entire contents of the line " *\0* Write out the number in the yank register again " *+* and move back down " *\* leave insert mode, and stop writing out the new macro " *^* move to the start of the line " *y$* yank the new macro, saving it in the yank register " *dd* now we have the macro saved in the yank register, delete its code " from the buffer. " Now we have the case macro we need to run stored in the yank register, we " can delete the code for the cases from the buffer: > let @d = "3k3dd" " *3k* move up three lines " *3dd* delete three lines " The "s stands for 'select'. I guess it could also stand for 'switch'. " The choice is yours! " Ceiling ~ " ------- ~ " We now have a way to yank the code for the case we want to handle. But wait! " In order to create the "s macro we need to deal with the presumption I " made above: we need some way of setting the yank register to contain the " correct value from 1-3 so that the 'select case' macro will pick the right " case. " Depending on the value of N, we need to yank: " > " N=0: yank 1 " N=1: yank 2 " N>=2: yank 3 " The first two are easy. We can simply add 1 to N temporarily and yank it. " For the third, we can again start by adding 1 to N, but then we'll also need " to create a 'ceiling' macro that caps any result higher than 3 to 3. " I'm afraid at this point I've run out of NIFTY mnemoic names for my macros, " so I'm just going to call the macros I need to implement this "j through " "r (skipping "n , "o , and "p , which we've already used.) " I told you naming these was hard! > let @j = "\yiw@k@l@m@r@l\" " *\* Add one to N (temporarily) " *yiw* yank it " *@k@l@m@r@l* " *waves hands around, theatrically* " *\* subtract one from N again " But how are we going to implement this ceiling without the benefit of any " arithmetic functions?! " *pauses for dramatic effect* " Well, first we'll write out N 3s onto a line. e.g. for N=8: " 33333333 " Then we'll replace the first two characters with 1 and 2: " 12333333 " Then we just move to the Nth character on the line and yank it! Easy-peasy " macro-squeezy! > " We'll start by writing out the 3s > let @k = "OO\\\0a3\\\" " *O* Create a new line above the cursor to write a new macro into, and " start insert mode " *O* The first command of our new macro is ALSO |O| . Macro-ception! " *\\* " insert a literal *ESC* to leave insert mode in our " inner-macro (but remember we're still in insert mode in the outer " macro) " *\0* insert the contents of the yank register. We're going to pass this " as a |count| to our next command: " *a3* append a *3* . Because of the |count|, this will actually append " N 3s. " *\\* " insert an |ESC| to leave the insert mode we started with |a| " *\* and then actually leave insert mode! " So if we run "k with *8* in the yank register, it will write out the " following into the line above the cursor: > " O8a3 " And if we yank *that* and run it, it will write out a line with eight 3s on " it. Next step is to do just that! > let @l = "0y$dd@0" " *0* move to the start of the line " *y$* yank the entire contents of the line " *dd* delete the line " *@0* playback the macro we just yanked > let @m = "2|r2^r1+yiw-" " *2|* move to the 2nd character on the line by using a |count| of *2* " with the normal mode |bar| command " *r2* replace the character under the cursor with a *2* " *^* move to the 1st character on the line " *r1* replace that with a *1* " *+* move downwards to the start of the next line i.e. onto our current " N value " *yiw* re-yank N " *-* move back up to the start of the line above " Now we are at the start of a line with the contents '123333...', and we " have N in the yank register. > let @r = "O\0|vydd\" " *O* You know the drill. " *\0* insert the contents of the yank register " *|* insert a |bar| . Combined with the N |count| we just " inserted, this will jump to the Nth character on the line. " *v* enter visual mode to select a single character " *y* yank it " *dd* delete the line with all the 3s on it " *\* exit insert mode " Armed with the macros above, let's review the middle section of "j : " " *@k* write a macro that adds a line with N 3s on it " *@l* yank it and run it to actually add the 3s-line " *@m* replace the first two characters of that line with *12* " *@r* write a macro that yanks the Nth character of the line and then " tidies up " *@l* yank *that* macro and run it " All done! ~ " --------- ~ " Now we can finally return to our _fib function in register "f and see " what it does: " " _fib function " *@c* write out three lines of code to handle the three cases and return " to our home line " *@j* load yank register with the correct number of lines to move up in " order to get to the correct case for the current value of N " *@s* write select case macro into yank register and return to home line " *@0* select case, (reading its code into the yank register) " *@d* delete cases " *@0* run case > " And that's it! "q now contains a macro that will calculate the Nth value " in the Fibonacci sequence for the number under the cursor! " So! To try this out, type the following, now: " :so % " This will source this file, running all the |:let| commands above, thus " setting up the macro, while ignoring all the explanation (which is formatted " as comments). " Recording It ~ " ============ ~ " "But wait!" I hear you say, "This is a bunch of |:let| commands! That " doesn't answer the question you originally asked! I want to know if you can " really RECORD a macro that does this? " The answer is yes. To *record* a version of this macro, simply type out the " following short sequence of keystrokes: > " q q q q f q q q " y i w o Esc p A Space " 0 Space 1 Esc 2 b @ f " I R e d a c t e " d : Space Esc q q f O " c c 0 Ctrl-V Esc Esc O d " 2 w Esc O Ctrl-V Ctrl-X g _ " y i w A Space Ctrl-V Esc p " 2 g e Ctrl-V Ctrl-A d a w " O Ctrl-V Ctrl-R - Ctrl-V Esc x a " Ctrl-V Ctrl-V Ctrl-V Ctrl-A Ctrl-V Esc 0 y " $ d d g _ @ 0 Ctrl-V " Ctrl-X 0 @ f Esc 3 + Ctrl-A " y i w O O Ctrl-V Esc Ctrl-R " 0 a 3 Ctrl-V Esc Esc 0 y " $ d d @ 0 2 | r " 2 ^ r 1 + y i w " - O Ctrl-R 0 | v y d " d Esc 0 y $ d d @ " 0 Ctrl-X O Ctrl-R 0 - y $ " Ctrl-R 0 + Esc ^ y $ d " d @ 0 3 k 3 d d " @ 0 q " Just be sure not to make any typos. Easy! " The End ~ " ======= ~ " So that's it! Hope you've enjoyed reading about how this macro was built. " If you haven't tried running it yet you can do so now, by entering the " command: > " :so % " If you liked this, why not check out some of my other SCINTILLATING Vim " content at my Vim website: https://normalmo.de/ " Rich Cheng. March, 2023 " Nothing to see here. " Seriously. Show's over. " Okay fine there are a few more bits and bobs below, but it's nothing " exciting, I promise. " -=- Just some housekeeping below. -=- " Reset all options to try to ensure everything runs as expected set all& " And clear maps mapclear mapclear! " Delete the comment markers g/"/norm!xx " Delete the modeline g/vim/d " Delete command to set search register g/Set up search/d g/^let @\//d " Delete everything above this line 1,/DELETE_TO_HERE/d " Set up search register let @/='\d\+' " Press n to place the cursor on any number, and then press @q to " run the macro! " Here's one for you to try: 6 " Here's another! 12 " Hint: to speed the macro up when running it on large numbers or slow " machines, try using the option: > " :set lazyredraw " When you're done fibonacciing, mash the u key or re-read the file with " the ex command :e! to return to the original file and find out how it " works. " vim:tw=78:ts=8:ft=help:nospell:nonu:com=b\:\":cole=2:cocu=nc