ML vs. Lisp - Programming Languages

Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:[color=blue]
> Programming in ML feels quite
> different from programming in Scheme.[/color]

Well, ok, Python also feels different from Scheme, but someone used to
one can switch to the other easily. Most of the differences in your
list are comparable to Scheme-vs-Python differences. But some are
not, particularly those dealing with the type system and its
consequences, and that's the part I have no real experience with.

Paul Rubin <http://phr.cx@NOSPAM.invalid> writes:
(snip)[color=blue]
> Sorry, yeah, I meant darcs not Arch. Darcs is well known to be quite
> slow and have scaling problems--I dunno whether a comparable
> implementation in another language would have had similar problems.[/color]

My impression is that it would: it's partly about design decisions and
suchlike, rather than intrinsically-Haskell stuff.
[color=blue]
> Pugs's slowness can't be held against it since it was supposed be a
> prototype, so ok.[/color]

I know nothing about Pugs.
[color=blue]
> The poker guy gave up on Haskell because 1) he
> spent too much time fighting the type system and decided he was more
> productive with dynamic types;[/color]

That's an interesting one. I grew up with static stuff (e.g., I learned
SML before I learned Common Lisp, and always liked languages like
Modula-3) (and also untyped stuff, like assembler) and when writing in
Lisp I think in ML, and I don't feel constrained by that, so I wonder if
my mind is just bent to think of problem solutions that don't need
dynamic types. Rather like, coming from an imperative background, FP is
initially hard because you have to push the obvious imperative solution
out of your head first before you have a chance of seeing the functional
one. I may just be a bad Lisp programmer. (-:
[color=blue]
> and 2) his application (a very highly concurrent, high traffic
> internet server) kept uncovering bugs in the GHC runtime that hadn't
> been subjected to that kind of stress before.[/color]

Mmmm, I can believe that.

FWIW Haskell people do care about performance and progress is being
made. For example, Strings used to be a common reason why applications
were slow, so just lately we have much shinier ByteString stuff instead.
(Actually, I don't know if this is an issue with darcs.) Similarly, now
we also have Sequences where, unlike lists, we can tolerably efficiently
append to the end of a long one.
[color=blue]
> I do get the impression that doing anything serious in Haskell
> requires fairly deep wizardry not needed for Lisp, Erlang, Python,
> etc.[/color]
(snip)

That's quite possible. Even from an FP background Haskell hurts my head
a lot. I still have much to learn about it. Whereas, with most
languages, after few weeks I'd usually have a good command of things
that weren't just details.

"Anything serious" is overstating it a bit, though. Once you understand
GADTs and monad transformers you can go a very long way. Much of what
I'm learning now, I don't actually /need/, but it's nice to have. It's
like mathematics, where when you understand a new field, you see how you
could have used it in the past, but in the past you did manage muddle
through some other way, you weren't actually hamstrung. Like these
people who don't initially notice when 'design patterns' like unfoldr or
Monoid apply, they just write a little function that does the same
thing.

Mark.

--
Functional programming vacancy at [url]http://www.aetion.com/[/url]

Steve Schafer <steve@fenestra.com> writes:
[color=blue]
> On Fri, 09 Feb 2007 20:05:24 -0800, Tim May <timcmay@removethis.got.net>
> wrote:
>[color=green]
>>ML is not too different from Scheme.[/color]
>
> I would think that stuff like type inference would be enough to qualify
> as "different enough."[/color]

Well, in some ways, it doesn't a lot change how you write the program,
it's more about when you learn about the error ?

Mark.

--
Functional programming vacancy at [url]http://www.aetion.com/[/url]

Paul Rubin wrote:[color=blue]
> Well, ok, Python also feels different from Scheme, but someone used to
> one can switch to the other easily. Most of the differences in your
> list are comparable to Scheme-vs-Python differences. But some are
> not, particularly those dealing with the type system and its
> consequences, and that's the part I have no real experience with.[/color]

Just to underline Vesa's point that Scheme/Python and ML are very different
languages, have a look at this schemer's attempt at solving the n-queens
problem in OCaml:

[url]http://curiousprogrammer.wordpress.com/2006/12/22/speed-comparison-plt-scheme-ocaml-and-c/[/url]

Compare to my attempt and some optimisations:

[url]http://caml.inria.fr/pub/ml-archives/caml-list/2006/12/e13b5ffc31ccffb8b39e822d2c95ac28.en.html[/url]

It is worth looking at the mistakes the schemer made in his ML:

1. He used several pointless types, e.g. type posn = Posn of int * int.
2. He misused pattern matching, e.g. as an explicit replacement for
destructing bind:

let board_ref b x y =
match b with
Board (squares, size) -> Array.get squares (index_of_coord x y size);;

3. He added superfluous parentheses.
4. He didn't understand OCaml's equality:

if c != Safe then c

5. He didn't leverage built-in higher-order functions.
6. He added lots of unnecessary boxing.

let rec placement board posn rem =
match board, posn with
None, _ -> None
| _, None -> None
| Some (Board (squares, size) as b), Some (Posn (x, y) as p) ->

7. His code wasn't factored, e.g. into his own higher-order functions.
8. Finally, he opted for a slower, array-based approach rather than using
the much simpler and faster list-based approach.

There are two main sources of bad OCaml code. The main source is people
coming from a C++ background who try to use objects for everything because
they don't know any better. Look at the Glome ray tracer, for example:

[url]http://syn.cs.pdx.edu/~jsnow/glome/[/url]

The author used objects because he didn't know how to implement mutual
recursion without them. I made exactly the same mistakes when I came to
OCaml from C++.

The other source of bad OCaml code is programmers used to dynamic typing.
They typically define many unnecessary sum types and try to box all values
in terms of these. This results in slow, unreliable code.

While I agree that a Schemer or Python programmer can sit down and knock out
some ML that might work, I can't emphasise enough that there is no point in
writing ML until you understand the trade-offs involved. ML is a superb
family of languages and it lets you solve many problems with remarkable
brevity. People won't realise that if they just try to "switch to ML
easily".

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
[url]http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet[/url]

[email]Mark.Carroll@Aetion.com[/email] (Mark T.B. Carroll) writes:
[color=blue]
> Paul Rubin <http://phr.cx@NOSPAM.invalid> writes:
> (snip)[color=green]
>> Sorry, yeah, I meant darcs not Arch. Darcs is well known to be quite
>> slow and have scaling problems--I dunno whether a comparable
>> implementation in another language would have had similar problems.[/color]
>
> My impression is that it would: it's partly about design decisions and
> suchlike, rather than intrinsically-Haskell stuff.[/color]

I' like to support this point of view. I've been told that the
algorithms Darcs uses are scaling badly in memory and time in certain
cases. So this would be not an implementation issue, not a Haskell
issue and unfixable until the specification would be changed (but I
think the Darcs-people would rather wait for better hardware and I'm
not so sure they would be wrong :-).
[color=blue][color=green]
>> Pugs's slowness can't be held against it since it was supposed be a
>> prototype, so ok.[/color]
>
> I know nothing about Pugs.[/color]

Nor do I -- is that a typo?
[color=blue]
>[color=green]
>> The poker guy gave up on Haskell because 1) he
>> spent too much time fighting the type system and decided he was more
>> productive with dynamic types;[/color]
>
> That's an interesting one. I grew up with static stuff (e.g., I learned
> SML before I learned Common Lisp, and always liked languages like
> Modula-3) (and also untyped stuff, like assembler) and when writing in
> Lisp I think in ML, and I don't feel constrained by that, so I wonder if
> my mind is just bent to think of problem solutions that don't need
> dynamic types.[/color]

I do think that possible. There is a "cultural bias" in the choice of
programming tools -- which is the reason why "I don't have problems"
or "I know someone who never came to grasp with it" usually only have
limited significance for the general case.

[color=blue]
> Rather like, coming from an imperative background, FP is
> initially hard because you have to push the obvious imperative solution
> out of your head first before you have a chance of seeing the functional
> one. I may just be a bad Lisp programmer. (-:
>[color=green]
>> and 2) his application (a very highly concurrent, high traffic
>> internet server) kept uncovering bugs in the GHC runtime that hadn't
>> been subjected to that kind of stress before.[/color]
>
> Mmmm, I can believe that.[/color]

But I also believe that the GHC people are rather cooperative in
fixing those bugs (as compared with certain commercial vendors who
want to sell really expensive support contracts before they even
listento your description of a bug in _their_ product).

[color=blue]
> FWIW Haskell people do care about performance and progress is being
> made. For example, Strings used to be a common reason why applications
> were slow, so just lately we have much shinier ByteString stuff instead.
> (Actually, I don't know if this is an issue with darcs.) Similarly, now
> we also have Sequences where, unlike lists, we can tolerably efficiently
> append to the end of a long one.
>[color=green]
>> I do get the impression that doing anything serious in Haskell
>> requires fairly deep wizardry not needed for Lisp, Erlang, Python,
>> etc.[/color]
> (snip)
>
> That's quite possible. Even from an FP background Haskell hurts my head[/color]

Yeah. And that is, because the language emphasizes _smart_ programming
and there are such a lot of really smart people around in the Haskell
scene. But I think one doesn't have to use all that special stuff. One
is well of with 2 rules:

- The I/O Monad just works like imperative programming: Write your
main and I/O procedures in the I/O monad. Don't bothe what a
"monad" in the theoretical view is. You can just use ut.

- Everything else is pure and lazy. Write your data transformations
pure and lazy (outside the I/O monad).

You don't have to bother about the specialities for a long time.
[color=blue]
> a lot. I still have much to learn about it. Whereas, with most
> languages, after few weeks I'd usually have a good command of things
> that weren't just details.[/color]
[color=blue]
> "Anything serious" is overstating it a bit, though.[/color]

Yes. You can, i.e. write a complete compiler or XML transformation
tool in Haskell w/o much wizadry.
[color=blue]
> Once you understand GADTs and monad transformers you can go a very
> long way. Much of what I'm learning now, I don't actually /need/,
> but it's nice to have. It's like mathematics, where when you
> understand a new field, you see how you could have used it in the
> past, but in the past you did manage muddle through some other way,
> you weren't actually hamstrung.[/color]

:-) Exactly my point, though I'd set the cutoff even earlier: People
don't have GADTs in other languages, so they don't strictly need them
in Haskel to do useful things.
[color=blue]
> Like these people who don't initially notice when 'design patterns'
> like unfoldr or Monoid apply, they just write a little function that
> does the same thing.[/color]

ACK.

Regards -- Markus

Paul Rubin wrote:[color=blue]
> Besides the infix syntax and the static type system, can someone
> describe the difference between ML and Lisp from a programmer's point
> of view? Should a Lisp programmer be able to get accustomed to .*ML
> (insert your favorite dialect prefix for ".*") without a lot of
> adjustment? I can tell you that does NOT happen with Haskell .[/color]

We haven't discussed pattern matching much. IMHO, this is one of the biggest
improvements...

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
[url]http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet[/url]

My long answer can be found in the translations (or lack thereof) of
the SICP examples into ML:

[url]http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages[/url]

Chris Rathman

On Feb 9, 4:02 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:[color=blue]
> Besides the infix syntax and the static type system, can someone
> describe the difference between ML and Lisp from a programmer's point
> of view? Should a Lisp programmer be able to get accustomed to .*ML
> (insert your favorite dialect prefix for ".*") without a lot of
> adjustment? I can tell you that does NOT happen with Haskell .
>
> Thanks.[/color]

Chris Rathman wrote:[color=blue]
> My long answer can be found in the translations (or lack thereof) of
> the SICP examples into ML:
>
>[/color]
[url]http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages[/url]

I'm not sure that is very useful. The OCaml and F# implementations are quite
poor, they fail to leverage the languages' features and, instead, waste
much of their code reimplementing Lisp/Scheme right down to the variable
names and superfluous parentheses. I think this is fundamentally because
you're translating a book designed to teach Scheme into other languages.

Look at this excerpt, for example:

(* Due to the typeful nature of OCaml, we need to define a set of variants
that will allow us to encode the solution shown in SICP. It is a bit
messier
than the scheme version, but sometimes that's the price you pay for type
safety
*)
type ('a,'b) mpair = MLeft of 'a | MRight of 'b | LSet of ('a -> unit) |
RSet of ('b -> unit)

let cons'' x y =
let x = ref x and y = ref y in
let set_x v = x := v
and set_y v = y := v
in function
| `Car -> Mleft !x
| `Cdr -> MRight !y
| `Set_car -> LSet set_x
| `Set_cdr -> RSet set_y
| _ -> raise (Invalid_argument "cons''")

Is this function ever going to be useful in OCaml? Can you find a single
OCaml program that uses a function like this?

Why car/cdr and not fst/snd?

Why dynamic dispatch rather than four separate functions?

Why the catchall pattern at the end?

Again, look at this comment:

Note also that this isn't exactly the most efficient way (or even the
most
intuitive way) of representing a queue in OCaml. But it's a close
translation of
the book.

To me, that says "this is not the way to implement a queue in OCaml".

From my point of view, SICP remains decades out of date and people
interested in learning something modern should look to modern examples.
Take a look at Markus Mottl's queue implementations, for example:

[url]http://www.ocaml.info/ocaml_sources/pure-fun-1.0.6/chp5.ml[/url]

module BatchedQueue : QUEUE = struct
type 'a queue = 'a list * 'a list

let empty = [], []
let is_empty (f, r) = f = []

let checkf (f, r as q) = if f = [] then List.rev r, f else q

let snoc (f, r) x = checkf (f, x :: r)
let head = function [], _ -> raise Empty | x :: _, _ -> x
let tail = function [], _ -> raise Empty | _ :: f, r -> checkf (f, r)
end

This is the first port of call for a queue implementation in ML.

I'll take a quick look at some specifics. Ex 3.56:

(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< s1car s2car)
(cons-stream s1car (merge (stream-cdr s1) s2)))
((> s1car s2car)
(cons-stream s2car (merge s1 (stream-cdr s2))))
(else
(cons-stream s1car
(merge (stream-cdr s1)
(stream-cdr s2)))))))))

In OCaml, this is just:

# let rec merge = parser
| [<'h1; t1>] -> (parser
[<'h2; t2>] ->
if h1<h2 then [<'h1; merge t1 [<'h2; t2>]>] else
[<'h2; merge [<'h1; t1>] t2>]
| [<>] -> [<'h1; t1>])
| [<>] -> (parser [<t>] -> t);;
val merge : 'a Stream.t -> 'b Stream.t -> 'b Stream.t = <fun>

For example:

# let rec f = parser [<'h; t>] -> string_of_int h^f t | [<>] -> "";;
val f : int Stream.t -> string = <fun>
# f(merge [<'1;'3;'5;'7;'9>] [<'2;'4;'6;'8>]);;
- : string = "123456789"

There are many other example functions out there that are prohibitively
tedious or error prone to implement in Scheme, so you won't find them in
SICP.

For anyone wanting to learn OCaml or F# from good code, I recommend:

[url]http://www.ffconsultancy.com/free/ocaml[/url]
[url]http://www.codecodex.com/wiki/index.php?title=Category:Objective_Caml[/url]

and, of course, my book.

Look for any examples that leverage pattern matching, higher-order functions
and so on.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
[url]http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet[/url]

On Feb 10, 5:02 pm, Jon Harrop <j...@ffconsultancy.com> wrote:[color=blue]
> I'll take a quick look at some specifics. Ex 3.56:
>
> (define (merge s1 s2)
> (cond ((stream-null? s1) s2)
> ((stream-null? s2) s1)
> (else
> (let ((s1car (stream-car s1))
> (s2car (stream-car s2)))
> (cond ((< s1car s2car)
> (cons-stream s1car (merge (stream-cdr s1) s2)))
> ((> s1car s2car)
> (cons-stream s2car (merge s1 (stream-cdr s2))))
> (else
> (cons-stream s1car
> (merge (stream-cdr s1)
> (stream-cdr s2)))))))))
>
> In OCaml, this is just:
>
> # let rec merge = parser
> | [<'h1; t1>] -> (parser
> [<'h2; t2>] ->
> if h1<h2 then [<'h1; merge t1 [<'h2; t2>]>] else
> [<'h2; merge [<'h1; t1>] t2>]
> | [<>] -> [<'h1; t1>])
> | [<>] -> (parser [<t>] -> t);;
> val merge : 'a Stream.t -> 'b Stream.t -> 'b Stream.t = <fun>
>
> For example:
>
> # let rec f = parser [<'h; t>] -> string_of_int h^f t | [<>] -> "";;
> val f : int Stream.t -> string = <fun>
> # f(merge [<'1;'3;'5;'7;'9>] [<'2;'4;'6;'8>]);;
> - : string = "123456789"[/color]

Since the O'Caml and F# hadn't translated this particular example, I'd
have to show how the Alice ML was translated:

fun lazy merge (nil, s2) = s2
| merge(s1, nil) = s1
| merge (s1, s2) =
let
val s1car = hd s1
val s2car = hd s2
in
if (s1car < s2car)
then s1car :: (merge(tl s1, s2))
else
if (s1car > s2car)
then s2car :: (merge(s1, tl s2))
else s1car :: (merge(tl s1, tl s2))
end

val result = List.take(merge([1,3,5,7,9], [2,4,6,8,10]), 10);

Not necessarily the way you'd actually want to structure the code for
Alice ML, which has some hangover Scheme terminology. I found it
instructive as it shows a nice correlation with the Scheme code.