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.
Stack overflow during evaluation (looping recursion?).
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 rOh 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 - 1Well 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 =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 -. )# fact 10 ;; - : int = 3628800 # fact 100 ;; - : int = 0
Comments:
<< Home
> 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
> 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. :)
# posted by 
: 6:04 PM
: 6:04 PM<< Home
