Posted by Daniel Lyons
Fri, 07 Sep 2007 19:12:00 GMT
I have a theory about the respective OO capabilities of Lisp and OCaml, but I’m not quite sure who to ask.
In Lisp, when you make some class and some methods, those methods look like regular functions. In fact, in a sense, they are regular functions which happen to have more than one definition depending on the types of their parameters. So functional-style programming isn’t hampered.
I’m wondering to what extent functional and OO programming styles intermingle in Lisp and OCaml. My suspicion is that OCaml suffers from a lower degree of functional/OO integration because it provides object#method syntax instead of method object syntax which would be analogous to its function call syntax and closer to Lisp’s (method object) syntax.
Tags languages, lisp, ocaml, oop, programming | 1 comment
Posted by Daniel Lyons
Sat, 19 May 2007 03:58:00 GMT
For fun during my meeting with Baird the other day at the Flying Star on Central, I gave him a toy problem I read somewhere on the internet.
Problem: In Prolog, write a predicate len_three/1 which succeeds when its parameter is a list of three items.
A crummy answer looks like this:
len_three(X) :-
length(X, Len),
Len = 3.
Of course there are always many crummy answers. Here’s another crummy one:
len_three(X) :-
length(X, 3).
The best answer is to let the unification algorithm do the work:
len_three([_,_,_]).
Erlang isn’t a far cry from Prolog syntactically, so it’s no surprise that this is valid Erlang:
len_three([_,_,_]) -> true.
To illustrate using the remainder of a list, I showed him how to write head and tail in various languages:
-- Haskell
head (x:_) = x
tail (_:xs) = xs
(* OCaml *)
let head (x::_) = x
let tail (_::xs) = xs
% Prolog
head([X|_], X).
tail([_|T], T).
% Erlang
head([X|_]) -> X.
tail([_|T]) -> T.
So you see these are all pretty analogous to each other, thanks to the pattern matching or unification functionality of the various languages.
So then Baird wanted to see an example of peeling some items off a list but also using the remainder. So I proposed pairs/1, which takes a list as a parameter and returns a list of lists, each sublist containing two items. Implementations:
-- Haskell
two (x:y:xs) = [x,y] : two xs
two [] = []
(* OCaml *)
let rec two = function
| (x::y::xs) -> [x;y] :: two xs
| [] -> []
;;
% Prolog
two([X, Y | Xs], [[X,Y] | Result]) :- two(Xs, Result).
two([], []).
% Erlang
two([X, Y | Xs]) -> [[X, Y] | two(Xs)];
two([]) -> [].
Some observations:
- Notice how much more obfuscation there is going on in the OCaml version than the Haskell version. Taste that sugary sweetness of Haskell’s syntax.
- In theory, the Prolog version should be reversible—in other words, you should be able to unify by calling two(X, [[1,2],[3,4]]) and getting X = [1,2,3,4] back. In practice, I have some trouble writing predicates that have that property, and I’m not sure what I’m doing wrong. I should study Prolog more carefully.
- Notice the Erlang version is shorter than the Prolog version. Shorter and perhaps slightly more readable. I have omitted the module and export declarations, however.
- The Erlang implementation does something funny if you give it 1-10:
2> two:two([1,2,3,4,5,6,7,8,9,10]).
[[1,2],[3,4],[5,6],[7,8],"\t\n"]
Tags erlang, functional, haskell, matching, ocaml, pattern, programming, prolog | 2 comments
Posted by Daniel Lyons
Thu, 22 Feb 2007 09:04:00 GMT
I’m reading a cool book called Understanding Probability. Pretty early on in chapter 2 there is a chart that looks something like this:
| n |
Kn – np |
fn |
| 10 |
1.0 |
0.6000 |
| 25 |
1.5 |
0.5600 |
| 50 |
2.0 |
0.5400 |
and so forth. In this case, the experiment is flipping a coin, n is the number of repetitions of the experiment, Kn is the number of times we get heads, p is the probability of getting heads (0.5), and fn is the relative frequency of getting heads. Obviously, this chart represents one particular set of trials. The author encouraged writing code so I busted out some OCaml on paper in the car, and implemented it from the hotel room a few hours ago.
type face = H | T
That’s just the coin type.
module ProbabilityLab =
struct
let run_experiment experiment times =
Array.init times (fun i -> experiment ())
Here I’m just applying some function over and over again with no parameter to run the experiment, and using that to fill in an array. The experiment gets invoked once for each time we want to do a trial. An array comes out. Simple.
let count_value value result =
float_of_int (Array.fold_right
(fun x y -> y + if x = value then 1 else 0)
result
0)
let count_total result =
float_of_int (Array.length result)
let relative_frequency value result =
count_value value result /. count_total result
These are some utility routines. count_value just counts up the number of times a particular value occurs in an array. count_total gives the length of the array. relative_frequency computes fn for a particular value. Notice that each of these takes the result array as the last parameter and returns a float.
let expected_actual_difference probability value result =
let actual = count_value value result in
let expected = (probability *. count_total result) in
expected -. actual
expected_actual_difference is for the K
n – fp. We’ll use it to see how many more heads we get than half: if the random number generator was completely unrandom and produced heads and then tails always, then this number would fluctuate between zero and either one or negative one.
let collect_summaries summaries result =
List.map (fun f -> f result) summaries
end;;
The last thing in my ProbabilityLab module in a function which takes a list of functions and applies each of them to the result in turn. It’s the opposite of the way you normally map; instead of one function of a simple parameter being invoked across a list, we’re going to invoke each function in the list across the same complex piece of data. This will simplify the table production later.
A simple coin flipping module:
module Coin =
struct
let flip () = match Random.int 2 with
| 0 -> H
| _ -> T
let flip_unfair () = match Random.int 6 with
| 0 -> H
| _ -> T
end;;
As you can see, it just implements two functions: flip and flip_unfair, which represent an unweighted coin and a coin that leans heavily towards tails, only getting heads about 1/6th of the time.
As an example, we can now run a simple experiment such as:
# ProbabilityLab.run_experiment Coin.flip 10;;
- : face array = [|H; T; H; H; H; T; H; T; T; T|]
That’s the experiment result we’re going to have to work with.
let coin_flip_experiment coin times =
begin
Random.self_init ();
let result = ProbabilityLab.run_experiment coin times in
ProbabilityLab.collect_summaries [
ProbabilityLab.count_total;
ProbabilityLab.expected_actual_difference 0.5 H;
ProbabilityLab.relative_frequency H]
result
end;;
This function performs a coin flipping experiment. It takes one of the coins as a parameter (meaning, flip or flip_unfair) and a number of times to flip the coin. It creates the result using the run_experiment function in the ProbabilityLab module and then collects three summaries. The first summary is just n. The second is the number of heads we got beyond 50% (the expected amount), kn – np. The third is the computed relative frequency of obtaining heads with this experiment. Note that they’re all curried function calls that are expecting one more parameter—the result array.
Clearly, coin_flip_experiment does the bulk of the work. But now we need to see what it takes to drive it:
let process () =
let coins = [Coin.flip; Coin.flip_unfair] in
let trials = [ 10; 25; 50; 100; 250; 500;
1000; 2500; 5000; 7500; 10000; 15000;
20000; 25000; 30000] in
List.map (fun coin ->
List.map (fun trial -> coin_flip_experiment coin trial) trials)
coins
;;
Simple. A nested map across the coins and the numbers of trials we want. Here’s the output, unbeautified, for one run on my computer:
# process ();;
- : float list list list =
[[[10.; 0.; 0.5]; [25.; -1.5; 0.56]; [50.; -1.; 0.52]; [100.; -4.; 0.54];
[250.; -2.; 0.508]; [500.; 2.; 0.496]; [1000.; 21.; 0.479];
[2500.; 6.; 0.4976]; [5000.; -20.; 0.504]; [7500.; 30.; 0.496];
[10000.; 23.; 0.4977]; [15000.; 78.; 0.4948]; [20000.; 60.; 0.497];
[25000.; 139.; 0.49444]; [30000.; -53.; 0.501766666666666694]];
[[10.; 4.; 0.1]; [25.; 9.5; 0.12]; [50.; 18.; 0.14]; [100.; 35.; 0.15];
[250.; 88.; 0.148]; [500.; 180.; 0.14]; [1000.; 321.; 0.179];
[2500.; 861.; 0.1556]; [5000.; 1668.; 0.1664];
[7500.; 2516.; 0.164533333333333337]; [10000.; 3268.; 0.1732];
[15000.; 5033.; 0.164466666666666678]; [20000.; 6705.; 0.16475];
[25000.; 8413.; 0.16348]; [30000.; 9916.; 0.169466666666666654]]]
Tags ocaml, probability, programming | 1 comment
Posted by Daniel Lyons
Sun, 24 Dec 2006 11:54:20 GMT
I don’t know to what degree this feature of the CLOS can be exploited, but one thing generally observed about Lisp is that crap like this:
(defun fib (x)
(cond
((eq x 1) 1)
((eq x 2) 1)
(t (+ (fib (1- x)) (fib (- x 2))))))
Is generally less readable and cool than crap like this in other languages (OCaml):
let rec fib = function
| 1 -> 1
| 2 -> 1
| x -> fib (x - 1) + fib (x - 2) ;;
and Haskell:
fib 1 = 1
fib 2 = 1
fib x = fib (x - 1) + fib (x - 2)
But, you can use the CLOS to do primitive pattern matching (primitive, because I don’t think it can be used to do destructuring):
(defmethod fib ((x (eql 1))) 1)
(defmethod fib ((x (eql 2))) 1)
(defmethod fib ((x integer))
(+ (fib (1- x)) (fib (- 2 x))))
Which is a little shorter, but adds a lot of nested parenthesis to the beginning of the method. Hmm.
Of course, only in Haskell can you get the list of all fibonacci numbers like this:
fibs = map fib [1..]
Or the eponymous self-recursive generator:
fibs = 1 : scanl (+) 1 fibs
To do the same thing with a series in Lisp requires some extra magic I don’t currently have.
Tags haskell, languages, lisp, ocaml, programming | no comments
Posted by Daniel Lyons
Sun, 26 Nov 2006 07:59:24 GMT
This last week I got some interesting bad news about my eyes: apparently my pupils over-dilate in darkness or semi-darkness. I have my first old-man disorder at the ripe old age of 25. On long drives at night I will have to turn the dome light on to prevent my eyes from perceiving every light source as a giant luminous splotch with an echo above or below it. This is also why I needed new glasses recently, but why I didn’t notice until I left my job and started working nights. There is no cure for this problem except time; as I age my pupil dilation should get less responsive, which will counteract this problem.
I just finished reading Demian by Hesse. A great book, except for all the cult stuff near the end. There are a number of passages that I really identified with, but the strongest was this:
“Sometimes when I ran through the streets in the evening, unable to return before midnight because I was so restless, I felt that now at this very moment I would have to meet my beloved—as she walked past me at the next street corner, called to me from the nearest window. At other times all of this seemed unbearably painful…”
I was very annoyed that I could identify so thoroughly with a character who goes on to basically endorse Anton LaVey satanism. Tsk-tsk.
I was thinking today about programming in Erlang and how much I enjoy it, but at the same time, though I enjoy my big functional languages, not one of them has a decent Mac library; most of them don’t even have decent Unix GUI libraries or web frameworks. Erlang at least has a promising-sounding web framework but I am tired of web programming for the moment. It’s so very occupational.
I became annoyed thinking about OCaml and how much I had liked it. OCaml is basically the marijuana of functional languages—you start there, and then you get into the heavy stuff like Lisp, Haskell and Erlang. Or else you remain trapped with OCaml, perhaps consuming liters of the Russian vodka of languages—C++—at the same time. “Well, it could be worse.” Yes.
I am disappointed that nobody has anything to say about my quicksort post. I suspect that one is for the ages, and in a couple years, someone will be quite glad it’s there. Nobody pointed out that I am doubling the constant factor in my partition, or that I should use median-of-three for better performance against pre-sorted lists. I expected Lance to show up and demand some merge sorts, which I haven’t coded since my second year of CS.
For myself in response to the Brick Science article, I wrote a small linked list library in C. It turned out to be about 55 lines of code, and it took me about 15 minutes to write, which reassured me after reading that the author expects 155 lines/hour. I would not expect anyone to achieve that in a reasonable language, but with C you can really fluff things up with meaningless brackets and wasted type declarations. Even Lisp, which is the most text-liberal functional language, is a factor of two or three improvement over C. I remember days at Clearwired where I was productively producing about 10 or 20 lines of Python an hour. Of course, HTML is a bit cheaper.
I have become a real dick about movies. Elitism is the opiate of the Dan, but I have tried to be conservative about which things I am an elitist about: heavy metal, programming languages and religion being the primary fields, but also somewhat about politics. I have more-or-less ejected politics as a synonym for theft, graft, stupidity, and waste, no matter the incarnation, so into the open slot I have tossed movies. My brother hasn’t helped, we have been alternating classics I have loved for some time with known-good classics of his interest, and both learning a lot. Plus now we have a lot of pretentious hatred for new movies. It’s a perfect fit with the rest of our hatred set (music and television).
I am now going to attempt to read another classic book, since I usually read about four non-programming books a year and Demian is number one for 2006.
Tags c, demian, erlang, eyes, functional, haskell, hesse, life, lisp, movies, music, ocaml, politics, programming, religion | 2 comments
Posted by Daniel Lyons
Wed, 22 Nov 2006 08:33:00 GMT
If you are interested in implementing quicksort in any reasonable language from scratch, you may not want to read this post.
I had some fun making this post but by all means draw your own conclusions and ignore my commentary.
The OO Languages
Io
List quicksort := method(
(self isEmpty) ifTrue(return List clone) ifFalse(
first := self first
rest := self slice(1)
below := Quicksort quicksort(rest select(i, i < first))
above := Quicksort quicksort(rest select(i, i >= first))
return below appendSeq(list(first) appendSeq(above))
)
)
I’ll be honest: this one took the longest and was the hardest to write. Additionally, it is the not very aesthetically pleasing (though moreso than any of the other OO languages), and I still don’t understand how Io knows when to execute a given piece of code (look at the select portion). It also was pretty unreadable until I separated the above and below variables out. I also didn’t understand why I needed return but it seemed to break the code to not have it there.
That said, it is very whitespacey, which is worth points in my book. This is the implementation I’m the least confident of. Io has changed a lot since I last was using it, and I never became very proficient at it.
Python
def quicksort(l):
if l == []:
return []
else:
x, xs = l[0], l[1:]
return quicksort([ i for i in xs if i < x ]) + \
[x] + quicksort([ i for i in xs if i >= x ])
For some reason, the list comprehensions didn’t do it for me this time. I preferred them in the functional languages where there seems to be less overhead. The parallel assignment helped a bit, but the lack of pattern matching was pretty annoying.
Ruby
def quicksort(l)
if l == [] then
[]
else
x, *xs = l
quicksort(xs.select { |i| i < x }) + [x] +
quicksort(xs.select { |i| i >= x })
end
end
It feels a little tidier than Python. The select was a little tidier than the equivalent list comprehension in Python, and seems to get right to the point a little better whereas with the list comprehension, the meaningful portion is in the if conditional on the far right.
I prefer the x, *xs = l notation, because it reminds me of pattern matching in the functional languages.
The Functional Languages
Haskell
module Quicksort where
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ]
++ [x] ++
quicksort [ i | i <- xs, i >= x ]
quicksort [] = []
Well, you’d expect a winner, and lo, it is a winner.
Erlang
-module(quicksort).
-export([quicksort/1]).
quicksort([H|T]) ->
quicksort([ X || X <- T, X < H ])
++ [H] ++
quicksort([ X || X <- T, X >= H ]);
quicksort([]) -> [].
Looks just like the Haskell to me, albeit with Prolog-esque syntax. But I like Prolog, so that’s worth a couple points. :) Tie with Haskell.
OCaml
let rec quicksort = function
| (x::xs) ->
(quicksort (List.filter (fun i -> i < x) xs))
@ [x] @
(quicksort (List.filter (fun i -> i >= x) xs))
| [] -> []
;;
Naturally, a bit of OCaml noise enters the picture. No nice list comprehension syntax so we get to use the old-fashioned filter function. However, it’s still quite small. I think it is very readable, I’m just wondering whether OCaml is going to wind up being the functional language I use the least.
Lisp
(defun quicksort (l)
(cond
((null l) nil)
(t (let ((x (car l))
(xs (cdr l)))
(concatenate 'list
(quicksort (remove-if #'(lambda (i) (< x i)) xs))
(cons x nil)
(quicksort (remove-if #'(lambda (i) (> x i)) xs)))))))
Wow. That’s… so ugly. By far the wordiest functional language. I could have done it without the let block though, in which case it looks like this:
(defun quicksort (l)
(cond
((null l) nil)
(t (concatenate 'list
(quicksort (remove-if #'(lambda (i) (< (car l) i)) (cdr l)))
(cons (car l) nil)
(quicksort (remove-if #'(lambda (i) (> (car l) i)) (cdr l)))))))
How unpleasant. I would have expected Lisp to do better. Oh well.
Tags erlang, haskell, io, languages, lisp, ocaml, programming, python, ruby | 13 comments
Posted by Daniel Lyons
Mon, 20 Nov 2006 06:19:22 GMT
It occurred to me today that Hebrew pronunciation is very regular and it would not be particularly difficult to implement a program that takes UTF-8 Hebrew text in and transliterates it to English. For example:
”שלום עליכם” -> “shalom aleiḥem” (that should look like an h with a dot underneath it, in case you have a weird browser).
Naturally, I already have a graceful recursive algorithm in mind for doing this, but I actually have no idea which of my permitted languages supports Unicode properly.
Here’s my guess:
- Common Lisp: probably supported, but probably gross, like everything else in CL.
- OCaml: should be supported (Europeans), but isn’t native.
- Haskell: no clue, probably not native at least. Maybe Hugs98?
- Erlang: not supported at all, due to underlying string implementation (lists of integers). I could mess around with the binary directly, using binary pattern matching to grep out the Hebrew and produce, say, atoms. Hmm.
I’ll have to look at this some more. It would be helpful to have in general I think.
Tags erlang, functional, haskell, hebrew, languages, lisp, natural, ocaml, programming | 5 comments
Posted by Daniel Lyons
Mon, 11 Sep 2006 22:46:50 GMT
For my forthcoming master work on programming languages, I’ve decided to disqualify Lisp as a functional programming language. I figure this is a pretty bold move, but I have two reasons for doing it:
- I want to distinguish the Lisp/Scheme family and talk about it independently of the functional programming field, because I think macros are the central feature of Lisp and they are not seen in other functional programming languages, and
- I want the distinguishing characteristic of a functional programming language to be something other than merely functions as first-class citizens, because that admits all sorts of languages that aren’t really functional programming languages into the fray (like Python).
I finally today think I may have found a worthy discriminating attribute: partial applications as curried function calls. For example, in OCaml this is perfectly legitimate code:
# let f x y = x + y;;
val f : int -> int -> int = <fun>
# f 2;;
- : int -> int = <fun>
f 2 returns a function which takes a single argument. That function adds two to its argument. It is identical to this code in OCaml:
(+) 2;;
- : int -> int = <fun>
In Lisp, you get this instead:
? (defun f (x y)
(+ x y))
F
? (f 2)
> Error in process listener(1): Too few arguments in call to
#<Compiled-function F #x83AD6AE>: 1 provided, at least 2 required.
To achieve the same effect I’d have to go to all the trouble of creating a lambda and specifying the arguments.
This little difference I think will prove to be good enough to rend Lisp free of the functional programming shroud so I can talk about it completely separately.
Tags functional, languages, lisp, ocaml, programming | 1 comment
