Re: Which programming language is better to start

Jon Harrop wrote:
>Rob Thorpe wrote:
>>> >> Sure, I just want to see an example of some Lisp code (a pattern
>>> >> match) which has its types inferred by the compiler and then
>>> >> statically checked. I am under the impression that this is far from
>>> >> easy with Lisp but am keen to be proved wrong.
>
>>> > As a performance measure a common lisp compiler will assign static
>>> > types at compile time to all variables where this can be done.
>
>>> And where can that be done?
>
>> For the local variables inside functions. And for stretchs of code
>> where the typing is static (which could possibly be the whole program).
>
>Ok. How does Lisp handle monomorphic types? e.g. the array containing the
>empty list: [| [] |] in OCaml.
>
>OCaml and SML resolve this differently. OCaml allows you to create a
>monomorphic type temporarily in a compilation unit, provided it is ossified
>to a specific type before the end of the compilation unit (so the interface
>to the compilation unit is well typed). I think SML disallows the creation
>of monomorphic types, so you have to annotate.

Ah, I see what you mean now. There are two cases:
1. If you specify a variable to have a type, it will have that type.
If the type is suitable for it then the compiler will represent it as a
static type at machine level. It will give you errors if you misuse
it.
2. If you don't specify a variable to have a type then the compiler
may examine it's scope and try to determine a type for it. If it
succeeds in proving that the variable can only have that type then it
becomes a static type at machine level.

(Above where I said "for stretches of the code where the typing is
static" I meant case 1)

>>> For example, what happens with the equivalent of this OCaml:
>
>>> let f g x = g (g x)
>
>>> The ocamlopt compiler statically types the program based upon the
>>> inferred type. The corresponding run-time implementation then does
>>> dynamic dispatch (a performance hit) in order to handle the run-time
>>> representations of the polymorphic type correctly.
>
>>> In contrast, the MLton SML compiler starts by monomorphising all
>>> applications of this function "f". There is no run-time dispatch because
>>> there is no run-time polymorphism (no performance hit) but there are now
>>> lots of specialised implementations of "f" (theoretically code bloat).
>
>> I think "let f g x = g (g x)" means
>
>> - define a function f taking g and x as arguments
>> - call function g with the arguments g and x return this as the result
>> of f
>> (Though I'm not absolutely sure)
> In
>
> maths, it means:
>
> f(g, x) = g(g(x))
>
> So "f" takes a function "g" and an argument "x" and return "g" applied to
> the result of applying "g" to "x".
>
>> In Lisp that would be
>> (defun f (g x) (funcall 'g g x))
>
> I'm not sure, but I think that is the equivalent of:
>
> let f g x = g g x
>
> in
>
> OCaml.

Yes, I got what it meant eventually, see the post after the one you're
quoting.

>> If the definition of the function is local then all mentions of f can
>> be found and verified. In this case the lisp compiler may take the
>> approach of MLton and create a set of specialised functions. Though I
>> doubt any actually do.
>
> What if the the definition of the function is not local? Does it resort to
> run-time typing?

There's nothing saying it should but the lisp system I use does not
used dynamic typing to handle global function calls. I may be wrong,
I'm sure someone will correct me if I am.

> Also, how strong is the static typing? e.g. will the Lisp
> compiler have inferred the same types as the ML.

I would expect so. It depends on the sophistication of the Lisp
compiler.

>>> I'm more interested in the case of a pattern match (because these are not
>>> native in Lisp). ML does a lot of pattern match optimisations which, I
>>> assume, Lisp cannot do as a consequence.
>
>> There is no concept of pattern matching on data in Lisp as there is in
>> MLs. These operation would be done by representing the data as lists
>> and applying basic list operations.
>
>> I have no idea how this would compare to ML in terms of performance.
>
> Pretty awful. :-)
>
> There have been whole books written on pattern match optimisations. They are
> fantastic constructs in terms of simplicity, expressiveness and providing
> great scope for optimisation. The main downside is that dissecting a data
> structure (e.g. lists) using pattern matches ties you to that data
> structure. In contrast, using maps and folds frees you from the underlying
> data structure.
>
> For example, if you have a string match like:
>
> "ABC" -> 1
> | "ABD" -> 2
> | "ABE" -> 3
> | _ -> 0
>
> then you can clearly just lookup the third character in the incoming string
> and do a little arithmetic (and a branch) to get your answer. Naively
> implementing this requires many branches and many string compares. More
> generally, ML can use hashing (sometimes with optimal hash functions) to
> achieve fantastic performance on much more complicated matches.
>
> There are many other optimisations, particularly decision-tree based
> optimisations which can be applied to data structure pattern matches. This
> lets the ML compiler minimise the number of branches required whilst
> guaranteeing the same result.
>
> I had guessed that you could add pattern matches to Lisp but that the Lisp
> compiler could not achieve anything like the performance of ML pattern
> matches. Also, the pattern matching constructs must be handled by the type
> inference and checker in ML, so I'm not sure how this works in Lisp. I
> think it depends on how your type inference macro handles the type of
> equality generated by the pattern match macro.

A lisp programmer would do the string match above either using
comparisons or using a regular expression. This is fairly simple and
could be done in any language. So I think data-structure pattern
matches are the most interesting thing to talk about.

Lisp supports structured data types through deftype and defstruct,
these are used for things like "struct" in C is used for. For more
complex data types it's normal to use lists.

A text editor for example may represent a piece of text as a list of
lines, and every line by a list of words. Similarly a compiler written
in lisp may represent code given to it as a list of functions, each
function being a list of statements etc. The structure would continue,
reflecting the grammar of the language. The programmer doesn't have to
do things this way, but it's normal.

I don't think these types of dynamic data would be suitable for the
applying pattern matching techniques used by ML. That said, it would
be possible to write into the implementation a fast functions for
finding patterns in structures of lists. As another poster pointed out
Bigloo scheme has this feature.

>>From the speed point of view ML has the edge here.

>>> > This is done by type-inference as in
>>> > MLs. So, if for example a variable always
>>> > stores an integer then this variable have an integer type in the
>>> > machine code, without the associated type information a dynamic
>>> > variable would have. This inference normally allows local variables to
>>> > become static in the implementation but not global variables.
>
>>> So a common Lisp compiler doesn't do monomorphisation?
>
>> No, I don't think any do.
>
> Complete monomorphisation isn't common in the ML world, only MLton does it
> AFAIK. But I think other compilers (e.g. ocamlopt) do some monomorphisation
> via inlining.

Yes, lisp compilers can do that and they do, at least for simple
functions.

>> In general the system of optimization by
>> type-inference is not as wide ranging as it is in ML's.
>
> Right, that was the impression I had.
>
> Thank you for your post!

There are two levels to think about. Typing through defstruct and
deftype which occurs at the high levels of the language, and is very
general. Type inference is an optimization happening deep in the
compiler, which isn't as wide ranging as the type inference of MLs.

.

Relevant Pages

  • Re: Which programming language is better to start
    ... >>> As a performance measure a common lisp compiler will assign static ... How does Lisp handle monomorphic types? ... ML does a lot of pattern match optimisations which, ... Complete monomorphisation isn't common in the ML world, ...
    (comp.programming)
  • Re: ILC2005: McCarthy denounces Common Lisp, "Lisp", XML, and Rahul
    ... SU-AI and run Lisp 1.6 or UCI-Lisp. ... kernel of an operating system or a compiler etc. ... have the power of Lisp instead of only C to manipulate those lists. ... apply so the error message doesn't occur. ...
    (comp.lang.lisp)
  • Re: Lisp for the C21
    ... Every functional language I remember has lists as matter of course, ... Common Lisp has optional and keyword arguments. ... to let the compiler use lists in these cases. ...
    (comp.lang.functional)
  • Re: Java connected Lisp
    ... versions of GNU Classpath and SBCL, ... Invent a nice and fast interface for calls from Lisp to Java and back. ... The trick could be to hack the compiler so that it recognizes accesses ... Rewrite the "compiler" ...
    (comp.lang.lisp)
  • Re: Reflections on a classic Lisp Paper
    ... its Lisp-1 semantics than defmacro, but would not serve CL as well. ... fexprs into those languages. ... this was the Lisp Machine's philosphy that led to offering ... do changes that the compiler cannot know, ...
    (comp.lang.lisp)