Home > Archive > Functional > May 2007 > ML vs. Lisp
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Paul Rubin 2007-02-09, 7:06 pm |
| 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.
| |
| Joachim Durchholz 2007-02-09, 7:06 pm |
| Paul Rubin schrieb:
> 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 ;).
Lisp has a lot of introspection, and coming with that are various forms
of quoting.
*ML doesn't have or need that.
Lisp allows the construction of executable code at runtime.
ML doesn't have that (whether it would need that is something that MLers
and Lispers probably disagree).
Lisp has macros that work at the syntax tree level.
Macro processors are not available for all *MLs (and they aren't
considered obligatory).
The default data structure for Lisp is the linked list.
The default data structure for *ML is the tagged union (aka algebraic
data type); linked lists are one (important) variant of that class of types.
Also, Lisp lists are by default mutable, while ML lists are not. (This
particular difference isn't as important in practice, because most Lisp
programs don't mutate lists, and because it's possible to have mutable
lists in ML, so the two language groups meet on a middle ground of
"lists are mostly immutable".)
These are just those that come to my mind. I'm pretty sure people with
more direct experience with both systems can enumerate more differences.
Regards,
Jo
| |
| Vesa Karvonen 2007-02-09, 7:06 pm |
| Paul Rubin <http://phr.cx@nospam.invalid> wrote:
> 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?
From a programmer's point of view, I'd say that the big diffence
between the two kinds of language is that the kind of things that one
would do using macros (e.g. http://mlton.org/ForLoops) or dynamic
typing (e.g. http://mlton.org/Printf) in Lisp or Scheme one does with
combinators in ML. It takes some time to learn and master. For
learning, I'd recommend reading articles on combinator libraries.
> Should a Lisp programmer be able to get accustomed to .*ML
[intentionally cut the rest]
Yes.
-Vesa Karvonen
| |
| Steve Schafer 2007-02-09, 10:04 pm |
| On 09 Feb 2007 14:02:39 -0800, Paul Rubin <http://phr.cx@NOSPAM.invalid>
wrote:
>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 ;).
If you find that Haskell wreaks havoc on your brain, then ML probably
will, too, though perhaps to a lesser extent.
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/
| |
| Tim May 2007-02-10, 4:13 am |
| In article <98cqs2hf3m0rkkhgldks2fss038me8n59l@4ax.com>, Steve Schafer
<steve@fenestra.com> wrote:
> On 09 Feb 2007 14:02:39 -0800, Paul Rubin <http://phr.cx@NOSPAM.invalid>
> wrote:
>
>
> If you find that Haskell wreaks havoc on your brain, then ML probably
> will, too, though perhaps to a lesser extent.
ML is not too different from Scheme. Almost not worth the effort.
Haskell is really crazy, elegant, mind-blowing, pure, strange....but
enough so that it's _worth it_ to "break on through to the other side."
--Tim May
| |
| Paul Rubin 2007-02-10, 4:13 am |
| Tim May <timcmay@removethis.got.net> writes:
> ML is not too different from Scheme. Almost not worth the effort.
From a practical standpoint (of trying to escape from godforsaken
languages like C while still writing tight code) I'm hoping that
compile-time type checking can eliminate some debugging, and
similarly, getting rid of dynamic typing makes much better runtime
code.
> Haskell is really crazy, elegant, mind-blowing, pure, strange....but
> enough so that it's _worth it_ to "break on through to the other side."
Yeah, that's why I've been spending time on it and should try to get
back to it. Ultimately though writing real applications in it seems
dodgy, e.g. Arch is very slow, that poker guy gave up on it and
converted his server to Erlang, etc.
| |
| Steve Schafer 2007-02-10, 4:13 am |
| On Fri, 09 Feb 2007 20:05:24 -0800, Tim May <timcmay@removethis.got.net>
wrote:
>ML is not too different from Scheme.
I would think that stuff like type inference would be enough to qualify
as "different enough."
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/
| |
| Paul Rubin 2007-02-10, 4:13 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> From a programmer's point of view, I'd say that the big diffence
> between the two kinds of language is that the kind of things that one
> would do using macros (e.g. http://mlton.org/ForLoops) or dynamic
> typing (e.g. http://mlton.org/Printf) in Lisp or Scheme one does with
> combinators in ML. It takes some time to learn and master. For
> learning, I'd recommend reading articles on combinator libraries.
Thanks, do you recommend any particular articles? I think I
understand the gist of what you're saying, though I don't know ML
syntax enough to really grok those two examples.
| |
| Tim May 2007-02-10, 4:13 am |
| In article <7xsldebq8v.fsf@ruckus.brouhaha.com>, Paul Rubin
<http://phr.cx@NOSPAM.invalid> wrote:
> Tim May <timcmay@removethis.got.net> writes:
>
> From a practical standpoint (of trying to escape from godforsaken
> languages like C while still writing tight code) I'm hoping that
> compile-time type checking can eliminate some debugging, and
> similarly, getting rid of dynamic typing makes much better runtime
> code.
>
>
> Yeah, that's why I've been spending time on it and should try to get
> back to it. Ultimately though writing real applications in it seems
> dodgy, e.g. Arch is very slow, that poker guy gave up on it and
> converted his server to Erlang, etc.
That was _his_ application. Note that nether darcs (the CVS sort of
program) nor Pugs (the language in which Perl 6 is being written) was
written in Erlang.
Popularity is rarely a good measure, in any case.
--Tim May
| |
| Paul Rubin 2007-02-10, 4:13 am |
| Tim May <timcmay@removethis.got.net> writes:
>
> That was _his_ application. Note that nether darcs (the CVS sort of
> program) nor Pugs (the language in which Perl 6 is being written) was
> written in Erlang.
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.
Pugs's slowness can't be held against it since it was supposed be a
prototype, so ok. 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; 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.
I do get the impression that doing anything serious in Haskell
requires fairly deep wizardry not needed for Lisp, Erlang, Python,
etc. However, I continue to fool around with Haskell and I still want
to write something nontrivial in it just for educational purposes,
since I don't think the very tiny things I've tried with it so far
really give the flavor.
> Popularity is rarely a good measure, in any case.
True. But the experiences of actual users count for something.
| |
| Vesa Karvonen 2007-02-10, 8:04 am |
| Tim May <timcmay@removethis.got.net> wrote:
[...]
> ML is not too different from Scheme. Almost not worth the effort.
I disagree. While there are similarities (strict, impure), ML is
quite different (dynamic typing vs static typing with type inference;
no module system or namespaces (R5RS) vs fairly sophisticated module
system; mutable bindings, strings, cons cells, and vectors vs
immutable bindings, cons cells, strings, and vectors and (only)
mutable ref cells and arrays; no standard pattern matching, algebraic
datatypes, or records vs all of them in the standard; no specified
evaluation order vs fully specified evaluation order (SML); no
standard exception handling but call/cc vs no standard call/cc
(available in SML/NJ and MLton) but exception handling; often
interpreted (or bytecode) vs usually compiled; functions take a list
of arguments vs a function always takes a single argument; macros vs
no macros; symbols ('x) vs algebraic datatypes; prefix syntax vs
programmer definable infix operators) from (R5RS+) Scheme (list would
slightly different with Common Lisp). Programming in ML feels quite
different from programming in Scheme. I use both regularly.
-Vesa Karvonen
| |
| Paul Rubin 2007-02-10, 8:04 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> Programming in ML feels quite
> different from programming in Scheme.
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.
| |
| Mark T.B. Carroll 2007-02-10, 8:04 am |
| Paul Rubin <http://phr.cx@NOSPAM.invalid> writes:
(snip)
> 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.
My impression is that it would: it's partly about design decisions and
suchlike, rather than intrinsically-Haskell stuff.
> Pugs's slowness can't be held against it since it was supposed be a
> prototype, so ok.
I know nothing about Pugs.
> 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;
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. (-:
> 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.
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.
> I do get the impression that doing anything serious in Haskell
> requires fairly deep wizardry not needed for Lisp, Erlang, Python,
> etc.
(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 w s 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 http://www.aetion.com/
| |
| Mark T.B. Carroll 2007-02-10, 8:04 am |
| Steve Schafer <steve@fenestra.com> writes:
> On Fri, 09 Feb 2007 20:05:24 -0800, Tim May <timcmay@removethis.got.net>
> wrote:
>
>
> I would think that stuff like type inference would be enough to qualify
> as "different enough."
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 http://www.aetion.com/
| |
| Jon Harrop 2007-02-10, 7:05 pm |
| Paul Rubin wrote:
> 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.
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:
http://curiousprogrammer.wordpress....me-ocaml-and-c/
Compare to my attempt and some optimisations:
http://caml.inria.fr/pub/ml-archive...c95ac28.en.html
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:
http://syn.cs.pdx.edu/~jsnow/glome/
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
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Jon Harrop 2007-02-10, 7:05 pm |
| Paul Rubin wrote:
> 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 ;).
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
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Chris Rathman 2007-02-10, 7:05 pm |
| My long answer can be found in the translations (or lack thereof) of
the SICP examples into ML:
http://www.codepoetics.com/wiki/ind...other_languages
Chris Rathman
On Feb 9, 4:02 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> 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.
| |
| Jon Harrop 2007-02-10, 7:05 pm |
| Chris Rathman wrote:
> My long answer can be found in the translations (or lack thereof) of
> the SICP examples into ML:
>
>
http://www.codepoetics.com/wiki/ind...other_languages
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:
http://www.ocaml.info/ocaml_sources...n-1.0.6/chp5.ml
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:
http://www.ffconsultancy.com/free/ocaml
http://www.codecodex.com/wiki/index...:Objective_Caml
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
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Markus E Leypold 2007-02-11, 4:05 am |
|
Mark.Carroll@Aetion.com (Mark T.B. Carroll) writes:
> Paul Rubin <http://phr.cx@NOSPAM.invalid> writes:
> (snip)
>
> My impression is that it would: it's partly about design decisions and
> suchlike, rather than intrinsically-Haskell stuff.
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 :-).
>
> I know nothing about Pugs.
Nor do I -- is that a typo?
>
>
> 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.
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.
> 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. (-:
>
>
> Mmmm, I can believe that.
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).
> 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.
>
> (snip)
>
> That's quite possible. Even from an FP background Haskell hurts my head
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.
> a lot. I still have much to learn about it. Whereas, with most
> languages, after few ws I'd usually have a good command of things
> that weren't just details.
> "Anything serious" is overstating it a bit, though.
Yes. You can, i.e. write a complete compiler or XML transformation
tool in Haskell w/o much wizadry.
> 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.
:-) 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.
> 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.
ACK.
Regards -- Markus
| |
| Chris Rathman 2007-02-11, 4:05 am |
| On Feb 10, 5:02 pm, Jon Harrop <j...@ffconsultancy.com> wrote:
> 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"
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.
| |
| Chris Rathman 2007-02-11, 4:05 am |
| Not sure why this didn't go through the first time, so apologies in
advance if it ends up being a duplicate.
On Feb 10, 5:02 pm, Jon Harrop <j...@ffconsultancy.com> wrote:
> 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.
The translation is mostly a self-education project. Some might find
it useful in a limited context. Others will find it muddled. It is a
"translation", not a methodical attempt to teach any of the other
languages, nor optimized algorithmic design in those PLs. Being a
translation, it's only natural that a lot of Scheme-isms will permeate
the code (though I can't think of better language to mimic than
Scheme).
That said, I disagree with your last point. SICP is designed to teach
programming, and Scheme just happens to be the vehicle used to
accomplish that goal. Many of the topics in SICP, such as HOFs, are
realized nicely in languages with modern type systems, while others
are not. It's all well and good to say that more modern languages
have emerged in the last 20 years, but SICP is still quite an
approachable introduction to many of the fundamental concepts of FP.
It won't teach you how to program in ML. But it will teach you most
of the ideas that form the basis of modern PLs.
> Is this function ever going to be useful in OCaml? Can you find a single
> OCaml program that uses a function like this?
Perhaps it's because the specific example chosen is demonstrating a
technique that does not translate well into an ML idiom. And perhaps
because there's not an ML idiomatic way to express this particular
technique, most O'Caml code will avoid using it.
> Why car/cdr and not fst/snd?
Are you saying that fst|snd are more meaningful than car|cdr (or my
SML bias that prefers hd|tl)? For the most part, the use of terms car
and cdr in the translation are limited to those functions in SICP that
are trying to directly define car & cdr (though I'll have to recheck
the O'Caml translation). Now most Scheme programmers are not going to
waste time defining car and cdr, as they will use the builtin
primitives. The question is why the authors of SICP waste time
defining these functions in a number of different ways?
> Why dynamic dispatch rather than four separate functions?
Perhaps because dynamic dispatch was the lesson being taught in that
particular example. The original SICP example that you chose to
highlight is about how message dispatch can be used to implement car
and cdr (fst & snd if you prefer). Now the O'Caml person may counter
by saying that no one in their right mind would ever want to define
fst and snd as a dispatched closure (shades of OOP here). But then no
right minded Schemer is ever likely to define car and cdr in that
manner either. So are the authors wasting our time showing us an
implementation that will never be used? Well, if the book were a
recipe book, then yes this little foray would be a waste of time. But
it also happens to teach us a lessons about functions, closures and
dispatch. And that lesson is much more valuable than simply handing
us a recipe about the best way to do something.
Now, I'll be the first to admit that this particular example doesn't
translate well to most other statically typed languages. But then the
original question was about the differences between Lisp and ML. In
that sense, the derivation of car and cdr as a closure in ML may at
least serve as an example (of the negative variety) of what Lisp
idioms to avoid when crossing the border to a typed language.
Personally, I find dynamic dispatch to be a useful programming
technique in dynamic languages. OTOH, I find working with types to be
a much better experience in ML. But then the discussion boils down to
one of tradeoffs. There is much effort put forth by those on both
sides of the aisle to attempt to recover some of that functionality on
the other side of the fence (shades of Oleg). When I get time, I'd
probably have a second less literal translation that uses classes for
this particular example. But I still think the literal translation is
useful for showing a bridge between the two languages.
> Why the catchall pattern at the end?
Because the compiler will complain about non-exhaustive pattern
matching. And it happens to correspond to the SICP example. If you
are dispatching on messages, as the Lisp is doing in the example, then
you may get an unexpected message. Again, you chose an example that
doesn't translate well to ML. The very fact that it corresponds to
message dispatch via functions and closures, tells us that the example
is going to be rather hard to translate. In short, the example is
exactly about message dispatch - not exactly a core strength of ML.
Even though it might be foreign to ML, the question is whether there
is a way to get message dispatch in the language?
Again, I'm not particularly satisfied with the translation of message
dispatch to ML. Most ML people will say that you have to re-educate
yourself to think differently, foregoing these things you happen to be
fond of in other languages. But the question is whether it's possible
to reacquire some of the tools from our toolbox that we have become
accustomed to in other languages? Perhaps not. Of course, this is
just a long-winded way to say that ML is not as dynamic as languages
like Scheme and Smalltalk - but that particular discussion may not be
productive. There is much better material on this particular subject
that other O'Caml users have provided - I just haven't had time to
digest it.
I do however find the overall response rather dismaying in that I
infer (probably incorrectly) that because these techniques are not
available in ML, they should be summarily swept under the rug, never
to be given serious consideration - effectively labelling them as a
distraction (pariah) to the way that ML'ers should think. It makes me
cringe a little when the ML and Haskell advocates (or advocates of any
other language or paradigm for that matter) say that you have to
completely relearn how you think and program. It may well be true,
but I find that having to redefine the craft every couple of years
rather grating. Has the process of thinking about programs really
changed since the release of SICP all those years ago? It was way
ahead of it's time. In some ways, I still think it's ahead.
> 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".
Well, that happens to be the connotation of the quote. The
translation of Scheme to ML is ok in some places, torturous in
others. It could also be said that the implementation of Queues given
in SICP is likely not the actual the implemetation that resides in
most modern Scheme dialects. There's a million ways to implement a
queue. Some are useful. Some are not.
> 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:
If you want to learn how to implement queues (and a number of other
data structures) in ML, then at least send them to the definitive
source: Purely Functional Data Structures by Chris Okasaki, of which
the link you give is a translation to O'Caml. I'd note that much of
chapter #3 of SICP is concerned with state (though I still haven't
figured out why streams was located in this chapter). So, yes, many
of the algorithms and examples are best formulated without state using
a functional approach.
But as long as we're on the subject, and handing out reading
recommendations, there's some interesting material in the book
Concepts, Techniques and Models of Computer Programming by Peter van
Roy and Seif Haridi.
http://www.info.ucl.ac.be/~pvr/book.html
In the book they cover constant time queues using dataflow variables
in chapter #3 (3.4.5 to be exact). But then that book is written
using Oz, much as SICP is written using Scheme. Alice ML can get us
real close - the translation page on SICP also has a link to a
translation of many of the book's examples to CTM. But then if you
just want to live in a single language and learn under a single
paradigm and find recipes for doing things, then SICP and CTM are not
the books to read to learn programming. But I have to agree to
disagree that SICP is out of date. It teaches many things that are
relevent today. It teaches us things we are still striving for. And
it does so quite elegantly. It's not without it's faults (as the HTDP
people and Wadler have pointed out). But if I'm looking for modern
techniques, I'd recommend CTM as the best current offering - a book
that I consider being the closest thing we have to a modern SICP.
That's not to say that the SICP translations are necessarily of high
quality (I spent an entire 4 hours trying to come up to speed on
O'Caml and translating chapters #1 & #2, though I confess it was
mostly a translation of the Alice ML code which I spent much more time
on). They are merely (feable) attempts at making the ideas locked in
SICP a bit more accessible to myself. Perhaps not useful to others,
but then you get what you pay for. And being on a wiki, others more
in tune with these languages can modify it to be more idiomatic and
elegant.
> # 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"
Well, one of the criticisms of ML and Haskell is that they tend to
value terseness in their definitions. Yes, a programmer immersed in
ML can easily understand this code. For those that are not - well it
can look as opaque as APL.
> 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.
And there are examples in SICP that are tedious and error prone to
implement in ML (as you point out above). If you are interested in
programming, I'd highly recommend SICP and CTM - way above most of the
books I've read on any particular PL - whether or not you happen to be
interested in Scheme or Oz. And as long as you happen to be reading
these books (or have read them in the past), perhaps seeing the ideas
expressed in other languages (however un-idiomatic) might help (or
not).
> For anyone wanting to learn OCaml or F# from good code, I recommend:
>
> http://www.ffconsultancy.com/free/ocaml
> http://www.codecodex.com/wiki/index...:Objective_Caml
So the question becomes how one learns ML? The answer is not a simple
- buy this book and you will suddenly possess ML-fu. Indeed, people
learn things in many different ways with different approaches. What
works for one, may not work for another. And learning isn't always a
go-or-no-go situation. People come to ML with different backgrounds
in programming. I happen to think that some of the all time best
introductory programming texts have come from the Scheme community. I
happen to also be naive enough to think that there's got to be a way
to leverage that material to other languages. But in no way do I
think this project amounts to a substitute for a more reasoned
presentation of O'Caml or F# - it's just one more resource in a sea of
resources that's available in the ocean of the internet.
>
> and, of course, my book.
I've heard good things about your O'Caml book, though I haven't read
it myself. I'm actually more interested in your F# book - Any news
you can share on the delivery?
> Look for any examples that leverage pattern matching, higher-order functions
> and so on.
And I would concur if your immediate goal is to learn ML.
| |
| Dirk Thierbach 2007-02-11, 4:05 am |
| Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@andthatm-e-leypold.de>
wrote:
> Mark.Carroll@Aetion.com (Mark T.B. Carroll) writes:
[color=darkred]
[color=darkred]
[color=darkred]
> Nor do I -- is that a typo?
Pugs is a prototype implementation of the "next generation" of the
Perl language, in Haskell. Google for it for more information.
- Dirk
| |
| Tim May 2007-02-11, 4:05 am |
| Paul,
My comment about Haskell was mainly in terms of what woud be the
biggest bang for the buck, not that Haskell would be more popular than
Erlang or OCaml or Scheme, not that it would be faster than C++ or
whatever.
I was a physicist for many years. I started with BASIC in the 1960s.
Boring. Then "FORTRAN IV with WATFIV" in the early 70s. Boring.
Then various forms of BASIC and Pascal on my home computers (Proc.
Tech. SOL) and work computers (HP 9825A then PDP 11/34A then VAX
11/780, our company's second such machine, installed in my lab). We
also ran an early ADA compiler in our lab's VAX.
All very boring, as a physicist. Some of the early Smalltalk-80 stuff,
just appearing, was slightly interesting.
It took until the mid-80s for Lisp Machines to make programmng truly
interesting.
Later, I toyed with Squeak, a Smalltalk implementation. Not much
different from ZetaLisp, in important ways.
ML languages were a new frontier. Haskell is the most revolutionary of
all semi-mainstream languages. (I say semi-mainstream because of course
there are many other less popular languages, from Clean to Charity to
Oz to Coq which compete in various ways, but which have relatively
small communities.)
Personally, I favor lazy languages with things like list compehensions.
This is, I think, a nearly perfect match with set theory and math in
general. I cannot imagine liking a language which does allow
[ n*n | n <- [1..1000] ; n mod 2 = 1]
to succinclty, in set-theoretic terms, list the squares of odd numbers
up to a 1000. ("the set of numbers squared such that the numbers are
elements of the list from 1 to 1000 and such that n mod 2 is 1, that
is, the odd numbers")
(the vertical bar, |, matches usual mathematical notation and means
"such that" or "s.t." or "assuming that. A lot like probability
notation, by the way. the "<-" can be read as "taken from" or "element
of," where the "<-" sort of looks like the element of symbol.)
The treatment of potentially infinite sets is even more elegant.
Likewise, lazy evaluation is more elegant than kludges involving FORCE
and DELAY.
Haskell is almost pure set theory. (I never used SETL, so I can't
compare it.)
Haskell, to me, is just math made for computers.
Whether C++ or Modula-3 or whatever are 2.6 times faster is immaterial.
To me, of course.
--Tim May
| |
| Vesa Karvonen 2007-02-11, 7:07 pm |
| Chris Rathman <Chris.Rathman@comcast.net> wrote:
[...]
> The translation is mostly a self-education project. Some might find
> it useful in a limited context. Others will find it muddled. It is a
> "translation", not a methodical attempt to teach any of the other
> languages, nor optimized algorithmic design in those PLs. Being a
> translation, it's only natural that a lot of Scheme-isms will permeate
> the code (though I can't think of better language to mimic than
> Scheme).
[...]
> Perhaps it's because the specific example chosen is demonstrating a
> technique that does not translate well into an ML idiom. And perhaps
> because there's not an ML idiomatic way to express this particular
> technique, most O'Caml code will avoid using it.
AAAARRGH... Frankly, your translations of Scheme snippets in SICP to
Alice ML suck. I'm not sure that I would describe them as
translations (http://en.wikipedia.org/wiki/Translation). They look
more like transliterations
(http://en.wikipedia.org/wiki/Transliteration) to me. Your
translations contain lots of irritating superfluous parentheses and
semicolons (see sections "Declarations and expressions" and
"Semicolons" on the page http://mlton.org/StandardMLGotchas). Many of
the functions are unnecessarily verbosely written and do not follow ML
idioms. I would definitely NOT RECOMMEND reading your examples if the
goal is to learn how to program in ML.
Here is a note from the pages:
(* Note: The Scheme code is demonstrating both packaging (encapsulation) and
dynamic dispatch. ML can handle encapsulation with no problem using
either functors or records. The dynamic dispatch does present a
challenge for any statically typed PL (at least any that want to be
considered as having a sound type system). *)
That just isn't true. Dynamic dispatch is easy to achieve in ML.
(Subtyping is more challenging.) For example, the below code shows a
simple way to define pairs as ecapsulated, dynamically dispatched,
mutable objects. (This relates to the specific example that you are
talking about above.) First we define an interface for our Pair
objects as a datatype:
datatype ('a, 'b) pair =
Pair of {fst : unit -> 'a,
snd : unit -> 'b,
setFst : 'a -> unit,
setSnd : 'b -> unit}
One could use values of type ('a, 'b) pair directly, but it is more
convenient to define helper functions:
fun fst (Pair c) = #fst c ()
fun snd (Pair c) = #snd c ()
fun setFst (Pair c, a) = #setFst c a
fun setSnd (Pair c, d) = #setSnd c d
A constructor function creates a value (or object) of some interface
type:
fun simplePair (f, s) = let
val f = ref f
val s = ref s
in
Pair {fst = fn () => !f,
snd = fn () => !s,
setFst = fn f' => f := f',
setSnd = fn s' => s := s'}
end
We can, of course, have multiple constructor functions per interface
type. Here is an "verbose pair" that takes a(nother) pair as an
argument:
fun verbosePair p =
Pair {fst = fn () => (print "fst\n" ; fst p),
snd = fn () => (print "snd\n" ; snd p),
setFst = fn f' => (print "setFst\n" ; setFst (p, f')),
setSnd = fn s' => (print "setSnd\n" ; setSnd (p, s'))}
Now, let's create a pair
val aPair = simplePair (1, 2)
and verbose pair
val aVerbosePair = verbosePair aPair
and modify the verbose pair
val () = setFst (aVerbosePair, 10)
As a side-effect, the above prints:
setFst
Now
val 10 = fst aPair
evaluates without an error.
-Vesa Karvonen
| |
| Jon Harrop 2007-02-11, 7:07 pm |
| Chris Rathman wrote:
> That said, I disagree with your last point. SICP is designed to teach
> programming, and Scheme just happens to be the vehicle used to
> accomplish that goal. Many of the topics in SICP, such as HOFs, are
> realized nicely in languages with modern type systems, while others
> are not.
I disagree with your conclusion and I already posted counter examples to
some points. There are very few approaches to problem solving presented in
SICP that cannot be implemented more succinctly and more efficiently in
languages like OCaml and F#.
> It's all well and good to say that more modern languages
> have emerged in the last 20 years, but SICP is still quite an
> approachable introduction to many of the fundamental concepts of FP.
> It won't teach you how to program in ML. But it will teach you most
> of the ideas that form the basis of modern PLs.
We'll have to agree to disagree. I found SICP to be very slim on
generally-applicable information.
>
> Perhaps it's because the specific example chosen is demonstrating a
> technique that does not translate well into an ML idiom. And perhaps
> because there's not an ML idiomatic way to express this particular
> technique, most O'Caml code will avoid using it.
Forget about "expressing techniques" and consider only solving problems. The
OCaml code that I posted solves the same problem much more succinctly and
robustly. There are many other OCaml solutions already out there that will
also be much faster.
>
> Are you saying that fst|snd are more meaningful than car|cdr (or my
> SML bias that prefers hd|tl)?
ML has no car and cdr (they were stipped to improve reliability). OCaml
nomenclature is fst and snd. There are built-in fst and snd functions.
> For the most part, the use of terms car
> and cdr in the translation are limited to those functions in SICP that
> are trying to directly define car & cdr (though I'll have to recheck
> the O'Caml translation).
Yes. Given that car and cdr can be stripped with no adverse effects and were
stripped deliberately, it doesn't make sense (to me) to try to reimplement
them.
> Now most Scheme programmers are not going to
> waste time defining car and cdr, as they will use the builtin
> primitives. The question is why the authors of SICP waste time
> defining these functions in a number of different ways?
This is what I meant about SICP being very Lisp/Scheme specific.
>
> Perhaps because dynamic dispatch was the lesson being taught in that
> particular example.
In OCaml, you would provide both so that users can leverage static typing
when the message being dispatched is known statically. The result would be
faster and more robust but would be cumbersome or impossible to represent
in Lisp or Scheme.
> The original SICP example that you chose to
> highlight is about how message dispatch can be used to implement car
> and cdr (fst & snd if you prefer). Now the O'Caml person may counter
> by saying that no one in their right mind would ever want to define
> fst and snd as a dispatched closure (shades of OOP here).
Indeed. They would use OOP.
> But then no
> right minded Schemer is ever likely to define car and cdr in that
> manner either. So are the authors wasting our time showing us an
> implementation that will never be used? Well, if the book were a
> recipe book, then yes this little foray would be a waste of time. But
> it also happens to teach us a lessons about functions, closures and
> dispatch. And that lesson is much more valuable than simply handing
> us a recipe about the best way to do something.
The result is little more instructive than a Scheme interpreter written in
ML.
> Now, I'll be the first to admit that this particular example doesn't
> translate well to most other statically typed languages. But then the
> original question was about the differences between Lisp and ML. In
> that sense, the derivation of car and cdr as a closure in ML may at
> least serve as an example (of the negative variety) of what Lisp
> idioms to avoid when crossing the border to a typed language.
Those Lisp constructs have been superceded and people should use the modern
variants in modern languages. Unfortunately, SICP spends most of its code
reimplementing them in slightly different ways...
> Personally, I find dynamic dispatch to be a useful programming
> technique in dynamic languages. OTOH, I find working with types to be
> a much better experience in ML. But then the discussion boils down to
> one of tradeoffs. There is much effort put forth by those on both
> sides of the aisle to attempt to recover some of that functionality on
> the other side of the fence (shades of Oleg). When I get time, I'd
> probably have a second less literal translation that uses classes for
> this particular example. But I still think the literal translation is
> useful for showing a bridge between the two languages.
I think a translation from OCaml to Scheme would close the circle.
>
> Because the compiler will complain about non-exhaustive pattern
> matching. And it happens to correspond to the SICP example. If you
> are dispatching on messages, as the Lisp is doing in the example, then
> you may get an unexpected message. Again, you chose an example that
> doesn't translate well to ML.
I chose an example that has not been translated well, not one that cannot be
translated well. Dynamic dispatch is easy to achieve in OCaml, as you have
done.
> The very fact that it corresponds to
> message dispatch via functions and closures, tells us that the example
> is going to be rather hard to translate.
No. This is my point: you found it hard does not imply that it is hard. I
think it would be worth holding off on such comments until the code is peer
reviewed by some expert OCaml programmers.
> the question is whether there is a way to get message dispatch in the
> language?
Message dispatch can be useful, e.g. when writing an XMLRPC interface.
However, imposing message dispatch all the time is insane. This is why it
was deliberately removed from ML when it evolved from Lisp.
> Again, I'm not particularly satisfied with the translation of message
> dispatch to ML. Most ML people will say that you have to re-educate
> yourself to think differently, foregoing these things you happen to be
> fond of in other languages.
If you want to learn new language features (e.g. pattern matching, static
typing, polymorphic variants, OOP) then you have to get educated. There is
no way around it.
What would you say to a C programmer struggling to learn Scheme?
> But the question is whether it's possible
> to reacquire some of the tools from our toolbox that we have become
> accustomed to in other languages?
F# does that without sacrificing reliability. However, it appears to come at
a grave cost in terms of performance for allocation-intensive programs.
> I do however find the overall response rather dismaying in that I
> infer (probably incorrectly) that because these techniques are not
> available in ML, they should be summarily swept under the rug, never
> to be given serious consideration - effectively labelling them as a
> distraction (pariah) to the way that ML'ers should think.
MLers don't sweep those features under the rug. They hold those features up
and shout "hey guys, look at this awful style that used to be taught before
static typing made better approaches easier".
> It makes me
> cringe a little when the ML and Haskell advocates (or advocates of any
> other language or paradigm for that matter) say that you have to
> completely relearn how you think and program.
What would you say to a C programmer struggling to learn Scheme?
This is a pretty accurate parallel actually: Let's say a C programmer writes
Scheme code and cites it. The code uses only a handful of Scheme's
features. He always turns off safety. He starts every program by
reimplementing unsafe pointers and pointer arithmetic. He has difficulty
translating the Sieve of Erasthones into Scheme using only pointers and
concludes, therefore, that the Sieve of Erasthones is an example of
something made much more difficult to write by Scheme's so-called "safety
features".
If you were polite, you'd surely tell him that he must relearn how he thinks
about programs before he can master Scheme?
> It may well be true,
> but I find that having to redefine the craft every couple of years
> rather grating.
ML is over 30 years old. OCaml adds lots of sexy new features but even that
is over 10 years old.
> Has the process of thinking about programs really
> changed since the release of SICP all those years ago?
Beyond the first few pages? Yes, of course.
>
> Well, that happens to be the connotation of the quote. The
> translation of Scheme to ML is ok in some places, torturous in
> others. It could also be said that the implementation of Queues given
> in SICP is likely not the actual the implemetation that resides in
> most modern Scheme dialects. There's a million ways to implement a
> queue. Some are useful. Some are not.
I'd have thought that anyone new to OCaml and wanting to implement a queue
might look at the mutable Queue implementation in the OCaml stdlib first,
and find Markus Mottl's purely functional implementation second.
>
> If you want to learn how to implement queues (and a number of other
> data structures) in ML, then at least send them to the definitive
> source: Purely Functional Data Structures by Chris Okasaki, of which
> the link you give is a translation to O'Caml.
Yes. That is an excellent book.
> But as long as we're on the subject, and handing out reading
> recommendations, there's some interesting material in the book
> Concepts, Techniques and Models of Computer Programming by Peter van
> Roy and Seif Haridi.
>
> http://www.info.ucl.ac.be/~pvr/book.html
>
> In the book they cover constant time queues using dataflow variables
> in chapter #3 (3.4.5 to be exact). But then that book is written
> using Oz, much as SICP is written using Scheme.
For anyone wanting to implement any data structures in any statically typed
languages, I would not recommend any books written entirely in dynamically
typed languages. Data structures are one of the areas most affected by
static typing. In ML, we want to leverage inference whilst having
well-defined and machine-verified interfaces.
> Alice ML can get us
> real close - the translation page on SICP also has a link to a
> translation of many of the book's examples to CTM. But then if you
> just want to live in a single language and learn under a single
> paradigm and find recipes for doing things, then SICP and CTM are not
> the books to read to learn programming.
But those books presumably omit all discussion of static typing, pattern
matching and many other features that are fundamental to many new FPLs?
> But I have to agree to
> disagree that SICP is out of date. It teaches many things that are
> relevent today. It teaches us things we are still striving for. And
> it does so quite elegantly.
SICP cannot leverage any of the many improvements invented or adopted over
the intervening 20 years. Pattern matching, type inference and static
typing are now widely supported.
> That's not to say that the SICP translations are necessarily of high
> quality (I spent an entire 4 hours trying to come up to speed on
> O'Caml and translating chapters #1 & #2, though I confess it was
> mostly a translation of the Alice ML code which I spent much more time
> on). They are merely (feable) attempts at making the ideas locked in
> SICP a bit more accessible to myself. Perhaps not useful to others,
> but then you get what you pay for. And being on a wiki, others more
> in tune with these languages can modify it to be more idiomatic and
> elegant.
Do you mind if I have a go? I think I would start by replacing some of the
data structure examples wholesale.
>
> So the question becomes how one learns ML? The answer is not a simple
> - buy this book and you will suddenly possess ML-fu.
If you want a good book on ML then check out Larry Paulson's "ML for the
Working Programmer".
> Indeed, people
> learn things in many different ways with different approaches. What
> works for one, may not work for another. And learning isn't always a
> go-or-no-go situation. People come to ML with different backgrounds
> in programming. I happen to think that some of the all time best
> introductory programming texts have come from the Scheme community.
There are certainly very few books on ML. There are several on Haskell
though. I bought some recently and am ploughing through them.
> I
> happen to also be naive enough to think that there's got to be a way
> to leverage that material to other languages. But in no way do I
> think this project amounts to a substitute for a more reasoned
> presentation of O'Caml or F# - it's just one more resource in a sea of
> resources that's available in the ocean of the internet.
I'm not convinced. I believe that many people complain about Joshua B.
Smith's book "Practical OCaml" because it stuck too closely to "Practical
Lisp", in that the examples were good for Lisp but not for OCaml.
>
> I've heard good things about your O'Caml book, though I haven't read
> it myself. I'm actually more interested in your F# book - Any news
> you can share on the delivery?
Yes, I was going to publish F# for Scientists this month but Microsoft just
agreed to commission me to write 2 extra chapters and have the book
published by a mainstream publisher (e.g. Wiley).
Robert Pickering is publishing Foundations of F# through APress next month,
I believe.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Paul Rubin 2007-02-11, 7:07 pm |
| Jon Harrop <jon@ffconsultancy.com> writes:
> For anyone wanting to implement any data structures in any statically typed
> languages, I would not recommend any books written entirely in dynamically
> typed languages. Data structures are one of the areas most affected by
> static typing.
I may be missing something here--I thought the classic book on data
structures was still TAOCP whose examples are all in (untyped)
assembly language. Data structures seem to me much more pervasively
affected by functional programming (think of graphs) than by static typing.
> SICP cannot leverage any of the many improvements invented or adopted over
> the intervening 20 years. Pattern matching, type inference and static
> typing are now widely supported.
Er, pattern matching has been done in Lisp programs (including
destructuring-bind in CL) since the dawn of time; SICP itself has
examples. Static typing per se is familiar from the whole
Algol/Fortran family, and dispatch based on static types is implicit
in how most compilers translate arithmetic and explicit in C++ and
Java. What's new and different in ML is its much more extensive type
system with inference. However, extensive reliance on type inference
appears to get hopelessly confusing, thus the customary Haskell
practice of declaring the types of most functions. But even after
that, it's still confusing and reportedly gets in the way (cf. Joel
Reymont's Haskell vs. Erlang posts). I'm trying to keep an open mind.
> Do you mind if I have a go? I think I would start by replacing some
> of the data structure examples wholesale.
That would be  ; it would also be interesting to see Haskell versions.
> If you want a good book on ML then check out Larry Paulson's "ML for the
> Working Programmer".
I have a borrowed copy of this book but found it pretty unhelpful. It
discussed the language's abstract qualities reasonably (though
concentrated a bit much on theorem proving), however it didn't say
much about what working programmers actually concern themselves with,
such as how to do I/O, concurrency, etc.
> There are certainly very few books on ML. There are several on Haskell
> though. I bought some recently and am ploughing through them.
I have "The Haskell School of Expression" which is pretty readable but
IMO too superficial and too limited to get anything done with. I'd be
interested to know what else you find.
| |
| Chris Rathman 2007-02-11, 7:07 pm |
| On Feb 11, 9:27 am, Vesa Karvonen <vesa.karvo...@cs.helsinki.fi>
wrote:
> Here is a note from the pages:
>
> (* Note: The Scheme code is demonstrating both packaging (encapsulation) and
> dynamic dispatch. ML can handle encapsulation with no problem using
> either functors or records. The dynamic dispatch does present a
> challenge for any statically typed PL (at least any that want to be
> considered as having a sound type system). *)
Perhaps not my most lucid comment, but it has to do with apply and
generic selectors in section 2.4.3, not the derivation of car and cdr
in chapter 3.3.1.
> That just isn't true. Dynamic dispatch is easy to achieve in ML.
> (Subtyping is more challenging.) For example, the below code shows a
> simple way to define pairs as ecapsulated, dynamically dispatched,
> mutable objects. (This relates to the specific example that you are
> talking about above.) First we define an interface for our Pair
> objects as a datatype:
Thanks for pointing out a proper method of translating the code in
question. I don't know that this quite captures the dynamic dispatch
that is being referred to in the comments above. It does do
polymorphic dispatch which is what should be emphasized in the code in
3.3.1, but it's not exactly what I'd term as dynamic dispatch that the
comment refers to in 2.4.3.
| |
| Paul Rubin 2007-02-11, 7:07 pm |
| Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> writes:
> 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 :-).
But could be that coding in Haskell naturally leads one to use
badly-scaling algorithms?
Well, his application involved sending a lot of serialized data over
network sockets and he had a lot of object types, so I guess he found
it more straightforward on the receiving end to deserialize the
packets into objects of the appropriate type and dispatch them
dynamically, than to have static selection logic all over the place.
I guess in OCaml one would use OOP, but I always saw OOP as a
workaround to static types.
[color=darkred]
> - 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.
Well, what about functions like liftM2? I understood once what that
did but it escapes me now.
> - 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.
But I think I have to use other monads for arrays, concurrency, etc.
> Yes. You can, i.e. write a complete compiler or XML transformation
> tool in Haskell w/o much wizadry.
OK, but I think of "serious" as meaning concurrent network
applications, programs that do transactions and therefore need to know
exactly when their I/O completes, programs that use complex OS
interfaces, etc. SPJ's article "Tackling the awkward squad" describes
some of the issues.
> :-) 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.
I don't understand what precisely what a GADT is, but in dynamically
typed languages doesn't the whole question go away?
| |
| Joachim Durchholz 2007-02-11, 7:07 pm |
| Paul Rubin schrieb:
> I thought the classic book on data
> structures was still TAOCP whose examples are all in (untyped)
> assembly language.
If you mean Don Knuth's series: it's seriously outdated, particularly on
topics like abstract data types, data structures, etc.
In all, it reflects the topics and choices that were controversial and
important in the fifties. (Similar to reading a book on geometry written
by the old Gr philosophical mathematicians. Even if they contributed
substantially to the state of the art, neither their problems nor much
of their results are very relevant today anymore.)
> Data structures seem to me much more pervasively
> affected by functional programming (think of graphs) than by static typing.
Graphs are even more affected than the usual data structure.
It's easy to model vertices using pointers if the pointers can mutate
and nearly impossible for the cyclic case if they can't mutate.
In comparison to that, most other data structures are only mildly affected.
> Er, pattern matching has been done in Lisp programs (including
> destructuring-bind in CL) since the dawn of time; SICP itself has
> examples.
I think it's the combination of sum types (tagged unions) and pattern
matching.
Lisp doesn't use sum types (if it has them at all); instead, new
primitive data types proliferated, making its type system unnecessarily
complex (from the viewpoint of an ML or Haskell programmer).
> Static typing per se is familiar from the whole
> Algol/Fortran family,
Now that's doing injustice to entire generations of programming languages.
Algol had a type algebra, while Fortran did not. (I'm not sure if it has
today. If so, it's not Fortran anymore *g*)
Then, *ML and Haskell have tagged unions and pattern matching (actually
structure matching), something that none of the Algol language have.
In addition, *ML and Haskell have type inference.
That's very, very far ahead of what Fortran does. For some metrics,
Fortran is farther from the *ML family than the Lisp family!
> and dispatch based on static types is implicit
> in how most compilers translate arithmetic and explicit in C++ and
> Java.
Again, that's dismissing vital differences.
The combination of tagged types and pattern matching is more than its parts.
> What's new and different in ML is its much more extensive type
> system with inference. However, extensive reliance on type inference
> appears to get hopelessly confusing, thus the customary Haskell
> practice of declaring the types of most functions. But even after
> that, it's still confusing and reportedly gets in the way (cf. Joel
> Reymont's Haskell vs. Erlang posts). I'm trying to keep an open mind.
I think Joel tried to do something for which you need to know your tools
well, and exercize them to their limits (I'm assuming we're both talking
about the poker server guy - my recollection of names it generally bad).
He didn't know Haskell well enough, and almost certainly was unable to
exercize it to its limits.
He said he was  by the type errors, but then that seems to be
the norm for the first few months in Haskell. He never got beyond that
stage AFAIR.
In other words, I'd say that type inference can be confusing, but it
seems to be a vast net win after a few months.
Regards,
Jo
| |
| Dirk Thierbach 2007-02-11, 7:07 pm |
| Paul Rubin <http://phr.cx@nospam.invalid> wrote:
> Markus E Leypold
> <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> writes:
I'd like to second this point of view very strongly.
[color=darkred]
> Well, what about functions like liftM2? I understood once what that
> did but it escapes me now.
It lifts a pure function to a function that works in a monad. Just
have a look at the type (that's what types are good for, among other
things they *document* what a function is doing):
liftM2 :: (Monad m) => (a -> b -> c) -> (m a -> m b -> m c)
So you have a function f :: a -> b -> c, i.e., with two arguments,
and you transform this into a function that takes two monadic
values as arguments and return a third monadic value. And there just
one obvious way to do that :-)
But if cannot remember these functions, you don't have to use them -- just
"think imperatively" and start coding. In the same way, if you have a
function that could be elegantly expressed using, say, fold and map,
you can still implement this function with basic pattern matching,
without the HOFs (but of course it's better style of you do).
- Dirk
| |
| Paul Rubin 2007-02-11, 7:07 pm |
| Joachim Durchholz <jo@durchholz.org> writes:
> If you mean Don Knuth's series: it's seriously outdated, particularly
> on topics like abstract data types, data structures, etc.
Well, it says nothing at all about abstract data types, since it
treats all of computing as bit-smashing operations; but I hadn't
thought of it as outdated regarding data structures. Maybe I'm behind
the times myself.
> I think it's the combination of sum types (tagged unions) and pattern
> matching.
You mean objects with tags in the runtime representation? Is that
different from dynamic types with some annotation? I knew ML and
Haskell support (e.g.) numeric types like "Float | Int" but I thought
that eventually the static type system had to resolve what every
instance actually was at compile time.
> Then, *ML and Haskell have tagged unions and pattern matching
> (actually structure matching), something that none of the Algol
> language have.
Am I missing something? I think of pattern/structure matching as
separate from the static type system, since it can be done naturally
in Lisp. I agree that ML and Haskell's type system is richer than
(Algol*)'s and that would include union types.
> The combination of tagged types and pattern matching is more than its parts.
OK, again I'm missing something, is there a simple example?
> I think Joel tried to do something for which you need to know your
> tools well, and exercize them to their limits (I'm assuming we're both
> talking about the poker server guy - my recollection of names it
> generally bad).
Yes, I didn't remember his name either but re-read his post and found
his name there.
> He said he was by the type errors, but then that seems to be
> the norm for the first few months in Haskell. He never got beyond that
> stage AFAIR.
Well, he goes much further, he says the type system actually gets in
the way, giving examples like deserializing packet layouts which can
result in differing record types depending on the packet contents.
Have you seen his post? This is what got me discouraged about
Haskell, though I haven't given up on it, I haven't messed with it as
much since then.
http://wagerlabs.com/2006/01/01/has...erlang-reloaded
> In other words, I'd say that type inference can be confusing, but it
> seems to be a vast net win after a few months.
I keep hearing this and I do know that I spend a lot of time finding
Lisp and Python bugs at runtime that a static type system could have
caught at compile time.
I think the next book I look at should be Pierce's TAPL. There was an
interview with Autrijus (now Audrey) Tang which recommended it highly
and basically said it was the reason Pugs got written. Any thoughts?
| |
| Joachim Durchholz 2007-02-11, 7:07 pm |
| Paul Rubin schrieb:
> Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> writes:
>
> But could be that coding in Haskell naturally leads one to use
> badly-scaling algorithms?
I wouldn't draw that conclusion from the alleged scaling problems of Darcs.
First, making revision control systems scale well is a generally hard
problem. CVS doesn't scale well with the number of branches, for
example. I'm not sure about Subversion (it's generally slow for my
current setup, but I suspect it's not the server that's slow).
Second, Darcs seems to be in the late "we optimize the hell out of it"
phase. At least that's what I gather from
http://darcs.net/DarcsWiki/Frequent...8ada2390
Third, it seems that the scalability problems are either being addressed
or due to some basic design decisions.
None of these things are particularly Haskell-related, I'd say.
In general, I'd say that it's easy to write inefficient software in
Haskell, particularly if you don't (yet) know what lazy evaluation
actually is.
I think that this effect will diminish over time, and it may even
reverse because the programmer has more time to do algorithmic
optimization (compared to the usual imperative languages anyway).
I'm not sure how well an average programmer will be able to work with
Haskell. (Haskell seems to be particularly attractive to people with a
more mathematical inclination, which is definitely not what the average
programmer is. So it's difficult to draw conclusions from experience.)
Regards,
Jo
| |
| Joachim Durchholz 2007-02-11, 7:07 pm |
| Paul Rubin schrieb:
> Joachim Durchholz <jo@durchholz.org> writes:
>
> Well, it says nothing at all about abstract data types, since it
> treats all of computing as bit-smashing operations;
I wasn't sure whether he was entirely blank about ADTs.
> but I hadn't
> thought of it as outdated regarding data structures. Maybe I'm behind
> the times myself.
Well, it's trees and hash tables and queues IIRC.
I don't recall B* trees, tough that may be a lapse of memory. (He dwells
a lot on the problem of sorting when you have too little RAM and several
tape decks. Interesting, but not a serious problem on a modern computer.)
Geographical applications of data structures: blank.
No lazy data structures.
No treatment of immutable data structures.
Garbage collection is severely under-represented.
>
> You mean objects with tags in the runtime representation?
No. Some people name them "discriminated union".
At the C level, these are unions of structs, with a mandatory common
"type" field that discriminates which kind of object this is.
> Is that
> different from dynamic types with some annotation?
Yes.
> I knew ML and
> Haskell support (e.g.) numeric types like "Float | Int"
Float | Int is not a numeric type. It's a type that may *contain* either
a Float or an Int, but you have to deconstruct it via pattern matching
to get at the numeric value inside it.
> but I thought
> that eventually the static type system had to resolve what every
> instance actually was at compile time.
Yes, but in FPLs, the notion of a "static type" is often broader than
what you usually have. E.g.
a -> b -> a
is a function that takes something of types a and b, and returns
something of type a - where a and b can be any types.
The types are ultimately static, but a lot of source code can be very
agnostic of the types that are actually passed through.
>
> Am I missing something? I think of pattern/structure matching as
> separate from the static type system, since it can be done naturally
> in Lisp.
In your typical statically-typed FPL, it's extremely helpful because it
unifies case discrimination, union-of-structs deconstruction and
assigning the struct elements to local variables in a single,
easy-to-grasp operation.
It is also helpful because tagged unions are actually ubiquitous.
E.g. you return a data structure with an error flag? In an FPL, that's a
tagged union of an Error type and the normal return type.
Got several variants of a record, with different fields reinterpreted
depending on circumstances? Tagged unions can handle this kind of
situation just fine, and with none of the "uncleanness" associated with
this kind of structure.
When I last did Lisp (which is several years ago), it didn't use these
idioms at all, so while pattern matching is possible in Lisp, it's not
as useful.
> Well, he goes much further, he says the type system actually gets in
> the way, giving examples like deserializing packet layouts which can
> result in differing record types depending on the packet contents.
From what he wrote, it was a bit unclear to me what his actual problems
were (well, those with the type system at least). I was under the
impression that he simply didn't understand what Haskell's type system
is good for, but it's hard to tell whether that's even remotely true
without taking a look at his actual source code.
> Have you seen his post?
Yes.
Regards,
Jo
| |
| Paul Rubin 2007-02-11, 7:07 pm |
| Joachim Durchholz <jo@durchholz.org> writes:
> No. Some people name them "discriminated union".
> At the C level, these are unions of structs, with a mandatory common
> "type" field that discriminates which kind of object this is.
Oh, ok, this is basically how Lisp works.
> The types are ultimately static, but a lot of source code can be very
> agnostic of the types that are actually passed through.
Right, that's different from something with a type field that's
dispatched on at runtime.
> It is also helpful because tagged unions are actually ubiquitous.
> E.g. you return a data structure with an error flag? In an FPL, that's
> a tagged union of an Error type and the normal return type.
> Got several variants of a record, with different fields reinterpreted
> depending on circumstances? Tagged unions can handle this kind of
> situation just fine, and with none of the "uncleanness" associated
> with this kind of structure.
Aha, this sounds like exactly what the poker guy had trouble with, and
it wasn't clear to me that it was possible to do in Haskell cleanly.
I think I understand what you're getting at now, though I don't know
the Haskell syntax to express it right now, I should be able to figure
it out from the docs. The idea is to select a different pattern match
based on the type field, and use the matched stuff as function args,
so the matched args and the function itself are statically typed and
are type-checked straightforwardly. Thanks!
> When I last did Lisp (which is several years ago), it didn't use these
> idioms at all,
Well of course it's straightforward to write in that style (using
destructuring-bind, for example), but maybe it's more common to use
structure types directly.
> From what he wrote, it was a bit unclear to me what his actual
> problems were (well, those with the type system at least).
Well, he gave some concrete examples where it took much more code to
do something in Haskell than in Erlang, and much more cutting and
pasting using his method. Maybe there's a better way but I'm not
familiar enough with Haskell to know this at the moment.
| |
| Vesa Karvonen 2007-02-11, 10:05 pm |
| Chris Rathman <Chris.Rathman@comcast.net> wrote:
> On Feb 11, 9:27 am, Vesa Karvonen <vesa.karvo...@cs.helsinki.fi>
> wrote:
[color=darkred]
> Perhaps not my most lucid comment, but it has to do with apply and
> generic selectors in section 2.4.3, not the derivation of car and cdr
> in chapter 3.3.1.
Like I said, dynamic dispatch isn't hard to achieve in ML. Below is a
bit ad-hoc and simplistic implementation of generic operations similar
in spirit to the SICP technique. It could be improved significantly
(e.g. O(1) lookup of operations and coercions can be achieved), but I
leave further improvements to the reader.
(* Some general purpose utilities *)
fun pass x f = f x
structure List = struct
open List
fun push rxs x = rxs := x :: !rxs
fun findSome f =
fn [] => NONE
| x::xs =>
case f x of
NONE => findSome f xs
| result => result
end
(* Signature for arithmetic modules *)
signature ARITHMETIC = sig
type t
val + : t * t -> t
val - : t * t -> t
val * : t * t -> t
val div : t * t -> t
end
(* Two "specific" arithmetic modules *)
structure FixedArith : ARITHMETIC = struct open FixedInt type t = int end
structure LargeArith : ARITHMETIC = struct open LargeInt type t = int end
(* Helper *)
functor GenBop (type t) = struct
val cases : (t * t -> t option) list ref = ref []
val add = List.push cases
end
(* Generic arithmetic module - sealed later *)
structure Arithmetic = struct
datatype t = In of {from : t -> t option, value : exn}
fun out (In t) = t
structure Add = GenBop (type t = t)
structure Sub = GenBop (type t = t)
structure Mul = GenBop (type t = t)
structure Div = GenBop (type t = t)
local
fun none () = NONE
fun tryCases args cases =
List.findSome (pass args) (!cases)
fun tryCoerce (l, r) =
case #from (out r) l of
SOME l => SOME (l, r)
| NONE =>
case #from (out l) r of
SOME r => SOME (l, r)
| NONE => NONE
fun mk cases args =
case tryCases args cases of
SOME v => v
| NONE =>
case tryCoerce args of
SOME args => mk cases args
| NONE => raise Domain
in
val op + = mk Add.cases
val op - = mk Sub.cases
val op * = mk Mul.cases
val op div = mk Div.cases
end
end
(* Signature for a "generic" arithmetic module *)
signature GEN = sig
type t
val addCoercion : {unwrap : Arithmetic.t -> 'a option,
coerce : 'a -> t} -> unit
val wrap : t -> Arithmetic.t
val unwrap : Arithmetic.t -> t option
end
(* Installs a specific arithmetic module to the generic arithmetic module *)
functor InstallBops (A : ARITHMETIC) : GEN = struct
open Arithmetic
type t = A.t
exception T of A.t
val coercions : (Arithmetic.t -> t option) list ref = ref []
fun addCoercion {unwrap, coerce} =
List.push coercions
(fn x => case unwrap x of
NONE => NONE
| SOME x => SOME (coerce x))
fun from x =
case List.findSome (pass x) (!coercions) of
NONE => NONE
| SOME x => SOME (wrap x)
and wrap x = In {from = from, value = T x}
val unwrap = fn In {value = T x, ...} => SOME x | _ => NONE
val () = let
fun add adder oper =
adder (fn (In {value = T l, ...}, In {value = T r, ...}) =>
SOME (wrap (oper (l, r)))
| _ => NONE)
in
add Add.add A.+
; add Sub.add A.-
; add Mul.add A.*
; add Div.add A.div
end
end
(* Here we seal the generic arithmetic module *)
structure Arithmetic : ARITHMETIC = Arithmetic
(* Here we install a couple of specific arithmetic modules *)
structure GenFixedArith = InstallBops (FixedArith)
structure GenLargeArith = InstallBops (LargeArith)
(* Here we install a coercion *)
val () = GenLargeArith.addCoercion
{unwrap = GenFixedArith.unwrap,
coerce = FixedInt.toLarge}
(* Here is a simple example of arithmetic *)
val SOME (11 : LargeInt.int) =
GenLargeArith.unwrap
(Arithmetic.+ (GenFixedArith.wrap 10,
GenLargeArith.wrap 1))
| |
| Paul Rubin 2007-02-11, 10:05 pm |
| Jon Harrop <jon@ffconsultancy.com> writes:
> Does it cover concurrent, lazy or immutable data structures?
I'd say not all that much; however, "classic" != "latest and most modern".
> Turing argument and Greenspun.
Eh? Wasn't Mathematica the other example of pattern matching that
you like to cite? It's dynamically typed just like Lisp.
> Numeric towers are rare outside CASs.
Not sure what you're getting at there.
> Don't extrapolate something Joel said about Haskell to the whole of
> type inference.
Well it's still standard practice in Haskell to declare most or all
functions, even though the compiler can infer the types, because the
declarations make things easier on humans and make it easier to locate
errors once the compiler reports them. I don't know whether those
issues apply to ML.
> Many MLs don't support concurrency. F# does.
Ocaml and AliceML (I'm not sure about SML) do support concurrency, but
the implementations aren't parallel.
> I got that and:
> http://www.amazon.com/Algorithms-Fu...3342211-4734423
Thanks, that looks interesting too. I have to say though, that most
real-world programming problems I deal with don't have serious
algorithmic issues (in the CS theory sense); they're mostly about
program organization and about OS interfaces and about choosing good
abstractions.
| |
| Jon Harrop 2007-02-11, 10:05 pm |
| Chris Rathman wrote:
> The translation is mostly a self-education project.
This one was quite funny:
let newton_transform g =
fun x -> x -. ((g x) /. ((deriv g) x))
All of those parentheses are superfluous!
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Chris Rathman 2007-02-11, 10:05 pm |
| On Feb 11, 7:31 pm, Jon Harrop <j...@ffconsultancy.com> wrote:
> Chris Rathman wrote:
>
> This one was quite funny:
>
> let newton_transform g =
> fun x -> x -. ((g x) /. ((deriv g) x))
>
> All of those parentheses are superfluous!
Thanks. My pride takes a hit, but since I'm getting a little help
from those who know ML infinitely better than myself, that's to be
expected. :-)
Chris
| |
| Jon Harrop 2007-02-11, 10:05 pm |
| Paul Rubin wrote:
> Jon Harrop <jon@ffconsultancy.com> writes:
>
> I'd say not all that much; however, "classic" != "latest and most modern".
You said that you were interested in learning modern FPLs like ML. You won't
find any information about that in books that predate modern FPLs, whether
they are classic or not.
>
> Eh?
Turing: you can reimplement anything in Lisp, including pattern matching.
Greenspun: you'll end up with a poor implementation of part of a modern FPL.
> Wasn't Mathematica the other example of pattern matching that
> you like to cite?
Yes. Mathematica's pattern matching is great for symbolic manipulation
whereas ML's pattern matching is great for manipulating general-purpose
data structures.
I was referring specifically to ML's pattern matching though, which offers
static checking and is intimately tied to the type system (it is the only
way to deconstruct sum types).
> It's dynamically typed just like Lisp.
Mathematica isn't statically typed but I'm not sure it is dynamically typed
either. Regardless, like ML, Mathematica comes with pattern matching. Lisp
does not. ML-style pattern matching makes many things easier and you won't
find any of them described in SICP, or any other book on Scheme.
>
> Not sure what you're getting at there.
You said "dispatch based on static types is implicit in how most compilers
translate arithmetic". What did you mean?
>
> Well it's still standard practice in Haskell to declare most or all
> functions, even though the compiler can infer the types, because the
> declarations make things easier on humans and make it easier to locate
> errors once the compiler reports them. I don't know whether those
> issues apply to ML.
MLers add little or no type information beyond definitions (particularly for
sum types). Look at the OCaml stdlib, for example.
One feature that makes a huge difference to usability here is the ability to
get the type inferred for any subexpression. Both OCaml/emacs and F#/VS
support this.
> Thanks, that looks interesting too. I have to say though, that most
> real-world programming problems I deal with don't have serious
> algorithmic issues (in the CS theory sense); they're mostly about
> program organization and about OS interfaces and about choosing good
> abstractions.
I have a lot of data structure related problems and am interested in the
trade-offs involved, e.g. between robustness and performance.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Jon Harrop 2007-02-11, 10:05 pm |
| Paul Rubin wrote:
> Aha, this sounds like exactly what the poker guy had trouble with, and
> it wasn't clear to me that it was possible to do in Haskell cleanly.
> I think I understand what you're getting at now, though I don't know
> the Haskell syntax to express it right now, I should be able to figure
> it out from the docs. The idea is to select a different pattern match
> based on the type field, and use the matched stuff as function args,
> so the matched args and the function itself are statically typed and
> are type-checked straightforwardly. Thanks!
Exactly. For example, you can extract the first or second member of a pair
dynamically using pattern matching:
# let get n t = match n, t with
| `Fst, (x, _) | `Snd, (_, x) -> x;;
val get : [< `Fst | `Snd ] -> 'a * 'a -> 'a = <fun>
For example:
# get `Fst (2, 3);;
- : int = 2
# get `Snd (2, 3);;
- : int = 3
The choice of `Fst and `Snd has been deferred until run-time. This is how
you regain dynamic typing (run-time dispatch) when necessary in ML.
However, you should not write in this style more than is necessary because
it undermines reliability (you're circumventing static typing and forgoing
static checking). Whenever possible, you should use static functions (like
the built-in fst and snd):
# fst (2, 3);;
- : int = 2
# snd (2, 3);;
- : int = 3
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/produc...dex.html?usenet
| |
| Paul Rubin 2007-02-11, 10:05 pm |
| Jon Harrop <jon@ffconsultancy.com> writes:
> However, you should not write in this style more than is necessary because
> it undermines reliability (you're circumventing static typing and forgoing
> static checking).
Well, sure, it's the essence of dynamic typing. But I expected that
the matched args themselves would be statically checked. Can I ask for
another example, the equivalent of
struct {
int type;
union { int ival; float fval; } u;
} x;
if (x.type == 0) /* use the int part of the union */
printf ("%d\n", x.u.ival * 3);
else if (x.type == 1) /* use the float part */
print("%f\n", sqrt(x.u.fval));
else
print ("invalid type tag\n");
I thought the above was | | |