Lexical Analysis With F# – Part 2

In the previous post I presented a simple lexical analyzer created purely as a means for me to get deeper into working with the F# language, such projects are a valuable means of subjecting oneself to realistic pressures so that one is compelled to deliver some kind of working solution.

One thing began to dawn on me as I worked on that previous version and that was the intimate relationship between immutability and recursion in these functional languages, this is not something I’d ever considered much before despite that fact that I’m no novice with recursion and have used it many times when manipulating recursive structures like trees.

Several of the books I have recently purchased stress the importance of recursion with functional languages, I can see the basis for this in a book on Lambda Calculus in which it becomes clear very quickly that for some functions we’d need to perform a repeating replacement of lambda terms with instances of themselves – this arises quite naturally from the foundations of lambda calculus.

However in a language that supports iteration (F# certainly does) the question arises – why demand recursion for recursion’s sake? why is it, why must it be something we strive to do when writing code in F#? In fact lambda calculus itself does not incorporate recursion because it does not give names to functions and with no means of referring to a function recursion is not possible.

My own understanding at this stage is that recursion is the only way to perform a limited repeating activity without modifying state. If you try to define an iterative algorithm that does not modify some state then you’ll actually find it impossible.

Combining Recursion with Iteration

Because recursion is essential to avoid changing state but where we aren’t changing state iteration is acceptable, I want to modify the lexical analyzer code from Part 1 so that it only uses recursion when a state change is necessary. If an action following some character being read does not necessitate a change in state then we should be able to iterate


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s