Technical Difficulties from on Top of the Mountain
2004-06-24
  Functional programming languages
Ok, so I'm looking at OCaml in addition to Lua. Lua looks like a good scripting language, but so far I haven't found any features that it has that I can't also do in Perl, and it doesn't seem to have a macro language (or generics) which I think is pretty important. While LISP is the ultimate in macro manipulation (since you can manipulate the symbol list of any function since everything is just an expression), I'm not ready to turn to the dark side yet, and I'm still attached to strong typing (from C++), so its time to look at OCAML (Objective Caml) which is a dialect of ML (meta-language), which includes a typing system.

Ok, right off I find an intro text from my alma-matter (Caltech), but I'm starting to wonder about its assembly. Here's one of the first examples of a routine/function they give:

let rec gcd a b =
	let r = a mod b in
		if r = 0 then
			b
		else
			gcd b r
Oh bother, tail recursion. Fine, lets try a different example:
let rec fact n =
	if n = 1 then
		1
	else
		n * fact n - 1
# fact(10) ;;
Stack overflow during evaluation (looping recursion?).

Hmmm. Maybe we better read more of the manual. Ok, so a function is supposed to look like this:
let dbl = fun n -> n * 2 ;;

Hmmm. Now I'm completely confused. Those don't look anything like each other. Lets keep reading and see if it gets any clearer:
let sum = fun i j -> i + j;;
let sum = (fun i -> (fun j -> i + j));; (* same thing *)

Oh that was pretty scary, a function that takes one parameter and then calls another function (which is defined inline) which eats the next parameter. This is getting worse. Ok, lets look at our factorial program again. Maybe we can debug it:

let rec factp n =
	Printf.printf "fact %d\n" n
	if n = 1 then
		1
	else
		n * fact n - 1
Well that won't even compile. Looks like the printf needs some sort of terminator or something. This is starting to look fishy. Ok, maybe its because its not a function (one can always hope). Taking a look at the last line though, I'm starting to suspect that the order of operations is (fact n) -1 not fact (n-1). This is why I almost always put the parenthesis in when writing expressions in C. Ok, try it with parenthesis's.
# let rec fact n =
	if n = 1 then
		1
	else
		n * fact (n - 1)
	;; 
val fact : int -> int = 
# fact 10 ;;
- : int = 3628800
# fact 100 ;;
- : int = 0
Ok, it works for small numbers at least. I guess its overflowing an int. Well, I guess that's ok. I think Lua throws in free bignum support, but this is actually typed as an int function, in fact trying to call it with a float produces an error. (You can't even use + or - with floats, you have to use type safe operators: +. and -. )
 
Comments:
> Oh that was pretty scary, a function that takes one
> parameter and then calls another function (which is
> defined inline) which eats the next parameter.

Actually, it's a bit simpler than that--a function that takes one parameter and returns a new function. That example code was showing off the automatic currying of functions in ML:

# let add a b = a + b;;
val add : int -> int -> int = <fun>

If you say "add 2 3" you get back 5, simple. If you say "add 2", you get back a function:

# add 2;;
- : int -> int = <fun>

This is useful when you want to add 2 to a whole list of numbers, for example:

# List.map (add 2) [5;6;7;8;9];;
- : int list = [7; 8; 9; 10; 11]

The easy way to understand this is that function application is like an operator in ML, and it's left-associative. So:

add 2 3 === ((add 2) 3)

And on the other side, there's syntactic sugar so you can write:

let add x y = x + y

instead of

let add = ( fun x -> (fun y -> x + y) )

(That is, add is the function that takes an argument x and returns another function that takes an argument y that returns the sum of x and y.)

And the other problem you had, with the debugging printf, was:

let rec factp n =
  Printf.printf "fact %d\n" n ==> ; <==
  if n = 1
    then 1
    else n * fact n - 1

You need that semicolon there. Which you wouldn't have known, since that was the first bit of sequential imperative programming that you tried.

It's a bit to wrap your head around--but I think that your intro text is a bit wonky (the error with n * fact n - 1 and all). If you're interested in spending more time at it, take a look at:

http://www.merjis.com/developers/ocaml_tutorial/

Which is an excellent little tutorial to the language that I stumbled across recently.

Sadly, bignums are a pain to work with in O'Caml regardless: primarily because you can't type bignum literals in your source code. Here's an example of fact with bignums, also showing how the +. thing isn't so bad, since you can do it with non-builtin datatypes. This could be a little cleaner, but it's set up so you can type it interactively:

-----------
#load "nums.cma";; (* ask top-level to link in external nums lib *)

open Num

let one = num_of_int 1

let rec fact n =
  if n = one then one else
  n */ fact (n -/ one)
-----------

And finally, to show that O'Caml can be a bit cleaner and nicer than that, a different way to write fact on integers:

let rec fact = function
  | 1 -> 1
  | n -> n * fact (n - 1)

This last looks very much like you might write a definition of the function down on paper. (Sadly you need to be able to write the constant 1 out, so it's no go with the bignums.)

Good luck, wherever you head. Since I just randomly found this on a web search, I think I'll go read over your other blog entries. :)
 
Post a Comment

<< Home
Life in the middle of nowhere, remote programming to try and support it, startups, children, and some tinkering when I get a chance.

ARCHIVES
January 2004 / February 2004 / March 2004 / April 2004 / May 2004 / June 2004 / July 2004 / August 2004 / September 2004 / October 2004 / November 2004 / December 2004 / January 2005 / February 2005 / March 2005 / April 2005 / May 2005 / June 2005 / July 2005 / August 2005 / September 2005 / October 2005 / November 2005 / December 2005 / January 2006 / February 2006 / March 2006 / April 2006 / May 2006 / June 2006 / July 2006 / August 2006 / September 2006 / October 2006 / November 2006 / December 2006 / January 2007 / February 2007 / March 2007 / April 2007 / June 2007 / July 2007 / August 2007 / September 2007 / October 2007 / November 2007 / December 2007 / January 2008 / May 2008 / June 2008 / August 2008 / February 2009 / August 2009 / February 2010 / February 2011 / March 2011 / October 2011 / March 2012 / July 2013 / August 2013 / September 2013 / October 2013 / November 2013 / December 2013 / December 2014 / February 2015 / March 2015 / July 2016 / September 2016 / December 2016 / April 2017 /


Blogroll
Paul Graham's Essays
You may not want to write in Lisp, but his advise on software, life and business is always worth listening to.
How to save the world
Dave Pollard working on changing the world .. one partially baked idea at a time.
SnowDeal
Eric Snowdeal IV - born 15 weeks too soon, now living a normal baby life.
Land and Hold Short
The life of a pilot.

The best of?
Jan '04
The second best villain of all times.

Feb '04
Oops I dropped by satellite.
New Jets create excitement in the air.
The audience is not listening.

Mar '04
Neat chemicals you don't want to mess with.
The Lack of Practise Effect

Apr '04
Scramjets take to the air
Doing dangerous things in the fire.
The Real Way to get a job

May '04
Checking out cool tools (with the kids)
A master geek (Ink Tank flashback)
How to play with your kids

Powered by Blogger