Lambda the Ultimate

It's not taken facetiously... I am somewhat intrigued by Smalltalk from what little I know about it, so maybe I'll check it out. But I was always under the impression that it was firmly in the imperative paradigm. I feel like Scheme does everything right except for the fact that it seems to encourage fragmentation into lots of tiny pieces rather than a coherent, convenient system. Thanks for the suggestion. Thanks also to the pointer to the SLIME Scheme 48 hack. Cool.

I think it will be a lot of fun when I find a chance to really hack some Squeak.

the problem with squeak is the mickeymouse-themed virtual desktop.

Although the most immediately obvious problem is that the UI is designed to appeal to five-year-olds, more problematic is that (as of some 12 months ago) the UI can only be created within the squeak window, as no-one seems to have created any bindings for other windowing systems, the recommended graphical toolkit has no up-to-date documentation, and the editor available is relatively primitive.

It might be possible to learn to use squeak in the context of a non-gui application, such as Seaside, though. I've never used seaside. As an aside, are there any good examples of apps made in seaside, with code available? The documentation and tutorials also don't make it clear how much is already done for the developer, for example in creating AJAX components.

Are why I'm building up Slate: UI architecture flexibility, good documentation, friendly to the command line, evolved libraries, and so on. Basically I'm taking all the good ideas in Smalltalk and Lisp systems and melding them.

nerds, geeks, and what have you, the source of postmodern hipsterism are 5 year olds via nostalgia. Who is not enamoured of cute cartoon figures and the like? I think it will be very difficult to find a programmer who will sniff at oswald the lucky rabbit and say kid's stuff instead of being captured by the pop culture buzz.

The problem with the Squeak UI is they should have tried more consciously to ape a class cartoon style. something like the old fleischer studios would make a great desktop theme I think.

There are some bindings to wxWidgets (formerly wxWindows) at wxSqueak.

To go along with this is Morphic for wxSqueak.

I believe there are some preliminary bindings to Mac OS X's GUI as well.

There has also been significant work on a replacement for Morphic: Tweak (Morphic is the UI "designed to appeal to five-year-olds" that "has no up-to-date documentation"). Tweak also relies on extensions ("method annotations" I think) to the base language.

Squeak is a wonderful tool/environment/Smalltalk implementation. However, its GUI is so orthogonal to every other desktop I've ever used that I've never been able to do anything with it. I'm so used to text editors and code, right-clicking to bring up a context sensitive menu, Windows, KDE, vim, etc. that the whole Squeak desktop is like parachuting into a place where nobody speaks English with only $1.25.

Now I'm sure if I stuck with Squeak, I'd at least be able to function there, and there is always the risk that I'd like it so much I'd be unable to go back to my old ways. :) However, I've recently discovered (perhaps acknowledged is a better word) Ruby, and that's where I'm going.

Ruby is touted as combining the best of Java, Smalltalk, Perl and Lisp, and features closures prominently. It's object-oriented (classes/attributes/methods) rather than functional. And it's a big deal because the "agile" development crowd is moving to Ruby as a replacement for the "traditional" scripting languages Perl, PHP and Python for rapid development of web applications. If you've been under the proverbial rock, do a search for Ruby on Rails. :)

NB These days the "mainstream" Smalltalk implementations are free for non-commercial use.

Squeak is an interesting implementation but sometimes there's an incorrect impression that Smalltalk is Squeak.

I suspect you're on to something here.

One really serious difference between Java (and C++, conceptually) is in modularity. With Java, everything almost has exactly one place it can be, once you at least partially grok Java's version of OO design. Scheme, and many other languages, don't enforce those kinds of limits, and if most of one's experience is with Java or C++, that lack of enforcement would feel sloppy. On the other hand, if it did enforce something that didn't match Java, it would feel restrictive.

How much time has been spent on learning good OO Java design? Hopefully, subsequently learning good Scheme design would be easier, but the work can't totally be avoided. Until someone has a feel for what a good design looks like in an environment, it's hard to know how to organize code. And what defines a good design interacts strongly with the module system.

Thanks for your advice... I had seen MrSpidey when I was just getting started learning Scheme (with PLT) but I didn't really understand what it did back then. I like the idea of a "soft" type system... does MrFlow accept type annotations like Haskell?

But as far as DrScheme, I can't deal with it. I tried. I don't like it. And then I was frustrated that so many of the things I wanted to do (such as debug) required it. If PLT Scheme had better separation of language features from IDE or turned DrScheme into a super-cool Emacs replacement with Scheme scripting in place of warty Elisp I'd probably go back, but as of now I'm looking at Gauche and Chicken. Not meaning this to be a rant or anything... I'm certainly not programming any Scheme implementations just yet (although after I finish EOPL, maybe?). This is more just feedback.

does MrFlow accept type annotations like Haskell?

Not at the moment, but I believe there's active development on making it understand the type-implications of user-defined contracts. Under that system, if you gave a function the contract (integer -> integer), MrFlow would understand that, and try to prove away the necessity for inserting any contract checks in the generated code or find a circumstance where it appears that the function is used in a way that's not consistent with the contract.

I was frustrated that so many of the things I wanted to do (such as debug) required [DrScheme].

Actually that's not true, though that may not be very well known. mzscheme -M errortrace [other mzscheme arguments afterwards ...] gives you the same error tracing facilities that DrScheme uses. In general you only need DrScheme for things that don't really make sense without a GUI, like the check-syntax binding-occurence/bound-occurence arrows.

Why not actually just write a static type-checker for scheme or lisp?

Because I don't want Lisp with static type checking. I want a new language (with some inspiration from Lisp).

http://caml.inria.fr
Efuns

Let's go through the list:

• "Lispy/Schemey:" Check. O'Caml, like Lisp, is an impure functional language. Also like Lisp, it has extremely powerful syntactic extension mechanisms.
• "Statically typed with type inference:" Check. Like all members of the ML family.
• "Variant types:" Check. In two flavors, traditional and polymorphic.
• "Pattern matching:" Check. Again, like all members of the ML family.
• "A cool system for accomplishing what OO accomplishes:" Check. O'Caml includes an object system with either classes or immediate construction, multiple inheritance, and a clear distinction between inheritance and subtyping. O'Caml remains, as of this writing, the only type-inferred statically-typed object/functional language to have escaped the lab (cf. O'Haskell).
• "Modules:" Check. Again, very much like the rest of the ML family. Modules, functors, and recursive modules are all there.
• "An interface to C:" Check. Actually, there are several.
• "Standard interfaces for sockets & threads & GUIs, etc:" Check, check, check. Sockets and threads are in the standard libraries; Tk support is in the standard libraries and bindings to Gtk+, COM, Win32... are available from third parties.
• "A text editor like Emacs but using this language rather than elisp:" Check. That would be Efuns, linked above.

Q: Does Ocaml have:

• a debugger, a profiler, lex, and yacc?
• array, for loops, printf, and fast I/O?
• generics, modules, and typesafety?
• hashtables, objects, and garbage collection?
• map, fold, lambda, cons, and quote?
• an emacs mode and a free, portable compiler?

A: Yup.

Q: Why am I still coding in C/C++/Java/Lisp?

A: Beats me.

You've really sold me on O'Caml there. Are there any catches I should know about?

Can you really do quoting and evaluating of syntax like you can in Scheme/LISP? I'm curious as to how that could work without S-expressions... I guess I'll go have a look.

It's feature complete. There is some stuff I don't like:

1. Pretty archaic syntax (especially when compared to Haskell), postfix polymorphic type declarations, verbose syntax for named structures, odd syntax for OO constructs, odd syntax for variables, pattern matching needs a lots and lots of superfluous parentheses.
2. Occasional type system oddities. (Sometimes a declared type of a construct is more general than the actual inferred type)
3. Native integer types are tagged 31 bits so you get occasional quirks when binding with native C libraries.
4. Currying functions is supported, but sometimes explicit eta-expansions need to be added.
5. Lacks Haskell's type classes, but this is solvable.

Ocaml feels a lot like ML but with features hacked on top of it at the expense of the syntax. That's no biggy though, there are lots of languages with a lousier syntax.

i too don't dig OCaml's archaic syntax. ;;?? # for attribute access?? ; for list items separator??

it is verbose and odd without much reason. it should be much sweeter for C++ converts if it used the C++ equivalents...

With respect to native integers, while it's true that "int" is a tagged 31-bit value on 32-bit platforms, we should point out that O'Caml also has an "int32" type with its associated functions in the Int32 module. For most purposes, just doing "open Int32" will be sufficient. Also remember that appending "l" to constants will make them int32:

# 3l;;
- : int32 = 3l

# open Printf;;
# printf "%lX\n" (-1641380927l);;
9E2A83C1
- : unit = ()

(** This function writes the int32 passed to the output channel passed in little-endian order.
    @author Paul Snively
    @param out_chan out_channel
    @param n int32
    @return unit *)
let output_int32_le out_chan n =
  let aux n =
    let byte_mask = of_int 0xff in
    let char_of_int32 x = Char.chr (to_int x) in
    let d0 = char_of_int32 (logand n byte_mask) in
    let d1 = char_of_int32 (logand (shift_right_logical n 8) byte_mask) in
    let d2 = char_of_int32 (logand (shift_right_logical n 16) byte_mask) in
    let d3 = char_of_int32 (logand (shift_right_logical n 24) byte_mask) in
    let little_endian = String.make 4 d3 in
      little_endian.[2] <- d2;
      little_endian.[1] <- d1;
      little_endian.[0] <- d0;
      little_endian in
    output_string out_chan (aux n)

(** This function reads an int32 that is encoded in little-endian order from the passed in_channel.
    @author Paul Snively
    @param in_chan in_channel
    @return int32 *)
let input_int32_le in_chan =
  let aux le =
    if String.length le <> 4 then 
      raise (Invalid_argument "int32_from_little_endian");
    let d3 = of_int (Char.code le.[0])
    and d2 = of_int (Char.code le.[1]) 
    and d1 = of_int (Char.code le.[2]) 
    and d0 = of_int (Char.code le.[3]) in
      (logor (shift_left d0 24) 
         (logor (shift_left d1 16) 
            (logor (shift_left d2 8) d3))) in
  let buf = String.create 4 in
    really_input in_chan buf 0 4;
    aux buf

Also, O'Caml is explicitly designed to support high-performance scientific computing: records and arrays consisting entirely of floats store their values unboxed, and the Bigarray module supports multidimensional unboxed arrays of ints or floats laid out in either C or FORTRAN style so that they can be passed directly to existing C or FORTRAN code, a fact that the bindings to popular libraries such as BLAS and LAPACK exploit.

The lack of type classes in the ML family is, as I think you alluded to, often dealt with by the use of phantom types. In O'Caml, polymorphic variants are frequently employed as an alternative to phantom types.

The lack of type classes in the ML family is, as I think you alluded to, often dealt with by the use of phantom types.

How does this work? Could you post an example or a link?

... of phantom types and polymorphic variants in O'Caml can be found here. Please let me know if you need more.

Hmm.. I guess I was looking for an example of encoding Haskell-style type classes using sml or ocaml phantom types. Maybe something simple from the Haskell prelude?

The generizations of phantom types (e.g. First-class phantom types or Guarded Recursive Datatype Constructors) all seem to require extra typechecking machinery, which I don't know how to simulate.

Spend more time translating CTM, but I'm in the middle of section 2.2 for SICP. Section 2.3 has been on the back of my mind though, and since it has to do with quoting, so perhaps I should be an opportunist and take advantage of the current line of thought.


From 2.3.1, SICP gives the following Quotation example:

   (define a 1)
   (define b 2)
   (list a b)
   (1 2)
   (list 'a 'b)
   (a b)

So what's the equivalent in an ML language?

   val a = 1
   val b = 1;
   [a, b];
   ???

Thanks.

And I'll try not to ask too many more of these language specific types of questions here, lest Ehud loses patience. :-)

Since you're working with a list, I will too.

Valhalla:~ psnively$ ocaml
        Objective Caml version 3.09.2

# #load "camlp4o.cma";;
        Camlp4 Parsing version 3.09.2

# #load "q_MLast.cmo";;
# let _loc = Lexing.dummy_pos, Lexing.dummy_pos;; (* Dummy source location *)
val _loc : Lexing.position * Lexing.position =
  ({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
    Lexing.pos_cnum = -1},
   {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
    Lexing.pos_cnum = -1})
# <:expr< [a; b] >>;; (* Quote the expression "[a; b]" *)
- : MLast.expr =
MLast.ExApp
 (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
    Lexing.pos_cnum = -1},
   {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
    Lexing.pos_cnum = -1}),
 MLast.ExApp
  (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
     Lexing.pos_cnum = -1},
    {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
     Lexing.pos_cnum = -1}),
  MLast.ExUid
   (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1},
     {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1}),
   "::"),
  MLast.ExLid
   (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1},
     {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1}),
   "a")),
 MLast.ExApp
  (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
     Lexing.pos_cnum = -1},
    {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
     Lexing.pos_cnum = -1}),
  MLast.ExApp
   (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1},
     {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1}),
   MLast.ExUid
    (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
       Lexing.pos_cnum = -1},
      {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
       Lexing.pos_cnum = -1}),
    "::"),
   MLast.ExLid
    (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
       Lexing.pos_cnum = -1},
      {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
       Lexing.pos_cnum = -1}),
    "b")),
  MLast.ExUid
   (({Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1},
     {Lexing.pos_fname = ""; Lexing.pos_lnum = 0; Lexing.pos_bol = 0;
      Lexing.pos_cnum = -1}),
   "[]")))

As this example makes crystal clear, "[a; b]" is pure syntactic sugar for "a :: (b :: [])".

just wow

is it me or is (list (quote foo) (quote bar)) a lot easier on the eyes and hands? guess meteprogramming with static languages still can't hold a candle for lisp...

*edit*: oops! sorry! that's the _output_ of the command :P

Yeah, sorry not to be clear. "<:expr< [a; b] >>" is the actual quotation. The rest is the result of that quotation, which is dominated by the repetition of the dummy source-code location. If you manage to ignore that, you can see that the AST is basically formed from simple type-constructor/token pairs.

Here's the result of MetaOCaml
session. The sign # is
OCaml's top-level prompt. The interpreter's answer is printed
underneath.

        MetaOCaml version 3.08.0 alpha 016

# let a = 1;;
val a : int = 1
# let b = 2;;
val b : int = 2
# [a;b];;
- : int list = [1; 2]
# let fab = .<fun a b -> [a;b]>.;;
val fab : ('a, 'b -> 'b -> 'b list) code =
  .<fun a_1 -> fun b_2 -> [a_1; b_2]>.
# .! fab;;
- : 'a -> 'a -> 'a list = <fun>
# (.! fab) 3 4;;
- : int list = [3; 4]

As you might have guessed, .! (pronounced `run') is akin
to eval of Scheme or Lisp (only it is far better defined). The run
construct also works in the compiled code. It essentially does
run-time code compilation and linking in. There are versions of
.! that translate the code into C or Fortran, compile,
and link it in. That C or Fortran code is of course usable on its own
(so it can be saved in a file and made a part of a library).

Here's what it looks like in Template Haskell:

Loading package base-1.0 ... linking ... done.
Prelude> :m + Language.Haskell.TH.Syntax
Prelude Language.Haskell.TH.Syntax> let a = 1
Prelude Language.Haskell.TH.Syntax> let b = 1
Prelude Language.Haskell.TH.Syntax> [a,b]
[1,1]
Prelude Language.Haskell.TH.Syntax> let exp = [| [a,b] |]
Loading package haskell98-1.0 ... linking ... done.
Loading package template-haskell-1.0 ... linking ... done.
Prelude Language.Haskell.TH.Syntax> runQ exp
ListE [VarE a_1627395084,VarE b_1627396234]
Prelude Language.Haskell.TH.Syntax> $(exp)
[1,1]
Prelude Language.Haskell.TH.Syntax>

where [| .. |] creates a (computation that yields a) quotation, and $() evaluates a quotation.

in MetaOcaml or Template Haskell are very primitive. Of course that these languages have some advantages over Lisp (or Common Lisp in this case), but I would really not put these metaprogramming systems and CL's defmacro on the same level. Just try to implement something like this in MetaOcaml or Template Haskell:

(defmacro once-only ((&rest names) &body body)
  (let ((gensyms (loop for n in names collect (gensym))))
    `(let (,@(loop for g in gensyms collect `(,g (gensym))))
      `(let (,,@(loop for g in gensyms for n in names collect ``(,,g ,,n)))
        ,(let (,@(loop for n in names for g in gensyms collect `(,n ,g)))
           ,@body)))))

The advantage of Lisp is representing data and code the same way *by default*, and while you surely can implement something like this in other languages, it would be a orders of magnitude less readable.

citylight: You've really sold me on O'Caml there. Are there any catches I should know about?

Sure: if you don't already know any member of the ML family, O'Caml seems really, really weird at first. Some of its syntactic differences from Standard ML are only there for Hysterical Raisins. Function application precedence rules mean that you end up parenthesizing (nested (function applications)) a lot. A lot of O'Caml programmers don't seem to find the standard libraries rich enough. I disagree with them, but it's something you'll hear about if you hang around the community.

citylight: Can you really do quoting and evaluating of syntax like you can in Scheme/LISP? I'm curious as to how that could work without S-expressions... I guess I'll go have a look.

Yes, using the Caml Pre-Processor and Pretty-Printer, known as camlp4, which is included in the O'Caml distribution. There's a very good tutorial on it, too. Basically, it separates the parsing task out from the rest of the compiler and gives you tools for concrete parsing to an AST, and tools for manipulating that AST, including quotation, quasiquotation, and antiquotation, just like Lisp. In addition, unlike Lisp, you can quote any language that you have a printer for. Graydon Hoare wrote a C quoting printer, Cquot, which he used in his One-Day Compilers presentation, in which he implements a very simple DSL by way of camlp4 and Cquot. In other words, his DSL gets compiled as an O'Caml program that prints C source code, the O'Caml program is run, the resulting C source code is compiled with gcc, and the resulting C binary does what the DSL code said to do.

In my experience, it is a pain to set up. I got it sorta working under Windows once, but then when I went to try to use the OpenGL/TK bindings there were bugs that I never got resolved (in particular, it wasn't getting some kind of mouse events, IIRC).

The second time, just recently, was I think on my Debian/Ubuntu Gnu/Linux box at home. It is a PPC machine, and old Mac. Those details might explain why O'Caml couldn't even load any of the 'standard' libraries.

Maybe blame the installer rather than the language, but the whole gestalt has been very frustrating. And even if I got it to work, what if I wanted to give my code to somebody else to use? With Perl or Java (I shudder to think of using either, really) at least it is a lot more likely they will be able to use what I've written.

I have played a little with OCaml. I'll take another look.

Strictly speaking I think an editor like Emacs has to at least compile and run using the normal compiler :-)

Even though everyone loves O'Caml and says it's the answer and what you're looking for, I still sympathize with your desire to make such a Lisp. There's just something innately appealing to me about S-expressions. They feel good.

...but they're also provably sub-optimal from a theoretical point of view.

(Though this could be fixed if you got rid of car, cdr and cons.)

"...but they're also provably sub-optimal from a theoretical point of view."

Could you explain this for me? Or point me to an explanation?

What do S-expressions have to do with car, cdr, and cons?

Besides, even in S-expression based languages which have these operations, getting rid of them makes no more sense than getting rid of the equivalent operations in Haskell and ML.

Lspers conflate the notions of external representation, internal representation and evaluation strategy.

Thus, if you're going to talk about "s-exprs" or "code-as-data", you better well first specify what exactly you mean by "s-exprs" and where they're used.

Anyways, my point is two-fold:

- As external representation, I shouldn't care at all how s-exprs are implemented internaly. It's just convenient syntax.

- As internal representation, linked lists do not work. Do I need to explain exactly why?

- Tying in with the previous point, if your computation model is based on munging linked lists, then your language has serious design problems. (Again, for reasons I shouldn't have to spell out, I hope.)

Yes, if you want to be taken seriously. As I explained before, this isn't a forum for "opinions". It is a forum for informed professional discussion. If you don't have any new ideas or results (or links to new research etc.) to add to the discussion, simply mentioning your opinion is a waste of time.

I ask you personally to keep this in mind. The recent threads you participated in resemble trolls, and do not live up to the standard of discussion we like to have around here.

Lack of comprehension on the part of some readers does not make a "troll"; in any case, I realize that the backlash simply comes from the fact that I had the gall to badmouth Lisp. (Making fun of Java never earns someone a "troll" label, for some reason.)

Back to the topic, though: all modern languages use either parse trees or random-access arrays for internal representation. Using linked lists is stupid because they are equivalent to trees and arrays but with demonstrably poorer algorithmic characteristics. (Precisely because they are "linked", i.e. linear.)

Using linked lists for a computation model is likewise a poor design choice because you will then need a supporting runtime for memory management that is implemented in some other language. In other words, your language isn't self-supporting.

For example, there are Prolog implementations that do not require a garbage collector. (I cite this not to advocate any particular language, but to point out that proper design decouples the computation model from the supporting runtime.)

The data structure used to represent a programming languages terms at compile time in no way imposes any constraints on the runtime representation.

and while we are on the topic of memory management, I'd like to point out Daniel Wang's dissertion, which discusses how to implement a garbage collector in a type safe language.

ftp://ftp.cs.princeton.edu/techreports/2001/640.pdf

In the original message I complained about the fact that Lisp uses the same data structure for parsing and for runtime representation.

Now this is easily fixed in the obvious ways, (just use two different structures) but such a language wouldn't be Lisp anymore. (Because you couldn't use 'cons' and 'cdr' and friends for modifying runtime structures.)

Which is why I complained about the existence of 'cons', 'car' and 'cdr' in the first place.

Thanks for the link, by the way. I haven't had the time to read it through yet, but a much more interesting question to me is whether or not memory management can be done statically at compile time, and if yes -- to which degree and under which conditions.

tkatchev: Thanks for the link, by the way. I haven't had the time to read it through yet, but a much more interesting question to me is whether or not memory management can be done statically at compile time, and if yes -- to which degree and under which conditions.

See the MLKit as a good launching-off point, then Google "region inference." The executive summary seems to be that region inference can work in all cases in the simply-typed lambda calculus with let polymorphism, and that implementation in the full Standard ML is a conservative extension. The downside seems to be that, using region inference alone, memory consumption can go to 5x what is actually required by the algorithm(s) in question, so for memory-constrained environments, a combination of region inference and real-time GC seems to be called for.

Actually, the real question is how space complexity for static memory allocation compares to a runtime GC.

I hope they are big-O comparable, but a paper linked to on the MLKit site states otherwise:

As mentioned in the preface, the present version of the ML Kit supports reference-tracing garbage collection in combination with region memory management [Hal99]. While most deallocations can be effciently performed by
region deallocation, there are some uses of memory for which it is diffcult to predict when memory can be deallocated.

In the original message I complained about the fact that Lisp uses the same data structure for parsing and for runtime representation.

No, Lisp does not. Stop trolling.

You confuse implementation with the abstract computational model that is implied by any programming language.

For example, there are Prolog implementations that do not require a garbage collector.

Interesting, can you indicate a link or a reference?

Linear logic has been proposed as one solution to the problem of garbage collection and providing efficient "update-in-place" capabilities within a more functional language. Linear logic conserves accessibility, and hence provides a mechanical metaphor which is more appropriate for a distributed-memory parallel processor in which copying is explicit. However, linear logic's lack of sharing may introduce significant inefficiencies of its own.

We show an efficient implementation of linear logic called Linear Lisp that runs within a constant factor of non-linear logic. This Linear Lisp allows RPLACX operations, and manages storage as safely as a non-linear Lisp, but does not need a garbage collector. Since it offers assignments but no sharing, it occupies a twilight zone between functional languages and imperative languages. Our Linear Lisp Machine offers many of the same capabilities as combinator/graph reduction machines, but without their copying and garbage collection problems.

Exactly what I was looking for.
(Though I still don't see a way of implementing a satisfactory n-ary tree with this model.)

Why not simply use arrays or structures for nodes? Then you select a child node with AREF. Very simple, and O(1) access with respect to N.

Because Lisp does not include O(1)-access structures in its computational model.

And no, hacking an opaque "array" object into a Lisp compiler does not count. If you do that, you're simply putting a Lispish syntax on top of C, and this isn't a very interesting excercise.

For example, this does not give you any advantages C++ does not already give you, except perhaps some very useful syntactic shortcuts.

Well I would say that a cons-pair have O(1)-access.

And by the way: what Lisp are you talking about?

O(1) in relation to what? :)

Big-O notation is a way of comparing functions, and a single cons-pair doesn't have any free variable you can measure.

In relation to which element you want. ie car or cdr. of course you have to view the cons as a function of the functions car and cdr which then becomes the free variable.

still: What lisp are you talking about?

whats wrong with make-array
and aref ?

(in scheme:
make-vector and vector-ref/vector-set!.)

if your reference to the "computational model" of lisp (which lisp, btw?) is meant to mean the lambda calculus, then even numerical datatypes and cons-cells are "opaque objects" in lisp.

(as far as i now this is even more true for haskell, where 1 is a function that yields a value representing 1...).

if your criticism is targeted at s-expr then #(1 2 3) should be a sufficient answer ;)

ps: regarding lambda-calculus when was the last time you have seen anybody programming a turing maschine, which is the computational modell of most imperative languages? (this is just to show that this comparison is not buying you anything ;) )

(defun kons (kar kdr)
  (lambda (selector)
    (funcall selector kar kdr)))

(defun kar (kons)
  (funcall kons 
           (lambda (kar kdr) kar)))

(defun kdr (kons)
  (funcall kons
           (lambda (kar kdr) kdr)))

just to show you that cons-cells are not the heart of the "computational modell" of lisp, lambdas are :)

Thanks, interesting.

Thus, you're using closures as cons-cells. Fascinating idea, but I'm still not sure whether this ultimately affects anything. (Could you build more complicated data structures on top of closures? I'm guessing that yes, you could.)

a turing maschine, which is the computational modell of most imperative languages

Last time I checked, TM calculated a function from (finite) bitstring to bitstring. What is so imperative in that? There are some attempts to stretch the definition to cover a function from (infinite) bitstream to bitstream, but I still fail to see how it is imperative.

(disclaimer: i have no deep knowledge about turing maschines, in particular not about the mathematical theory underneath them, so this is just how i understand things)

turing maschine:
* a infinite sequential bitstring
* a current position in the bitstring
* a statemaschine
* a current state in the statemaschine

the statemaschine has the following instructions which can be run during statechanges: write position, move position. the state-changes can be influenced by the value of the current position.

the result is calculated by executing state-changes ( == imperativ, one after another) until i reach a final state.

Not true. Most imperative languages model some sort register machine, and register machines have (conceivably) different complexity characteristics from Turing machines. Moreover, even different flavors of register machines have different complexity characteristics, so this is a difficult question that you cannot just dismiss so bluntly.

Back to Lisp, though: I've a hard time buying the notion that Lisp models the lambda calculus; at the very least, I don't see how cons-cells and lambda calculus relate to each other.

In short, my criticism of Lisp boils down to the opinion that any computational model based on cons-cells is broken in many ways. Get rid of cons-cells and I'd take my words back; but this brings up the question of how you can have any sort of Lisp without cons-cells.

Saying "O(1)" is a shortcut for "f(n) inf, C=const".

Saying that "car/cdr" is O(1) is meaningless since there's no f(n) you could conceivably measure here.

BUT: As was clearly explained here time and again, Scheme had vectors, and Lisp has it's version of constant time vectors, so the fact that lists behave differently is besides the point.

Stop beating a dead horse, it's really boring.

Your post amounts to the following: Lisp and Scheme are front-ends to C with annoying syntax.

Fine, if you find that sort of thing exciting, I can understand that. Me, personally, I don't want nor need the existence of a front-end to C with s-expr syntax, I find coding straight C comfortable enough as it is.

The crux: whether Lisp is simply syntactic sugar for list manipulation for those who love parentheses, or whether there is really something fundamentally useful in Lisp after all.

I really tried to keep up with the rules for LtU, but if even Ehud can't stop feeding a troll, neither can I.

"Lisp and Scheme are front-ends to C with annoying syntax."

And you seem to be a front-end to a boring, tireless Turing-machine with really annoying syntax and semantics.

You whole posts against Lisp come down to this: you don't like the syntax. That's it. And here we are wasting our time debating why you should like Lisp's s-exprs...

"I find coding straight C comfortable enough as it is."

So, there you are. You dislike it so much you feel it's fine to give up all its power, flexibility and high level programming in favor of a small, ancient, severely limited imperative language just in order to have O(1) access with a simple syntax like a[number].

yep, that sounds reasonable and very edifying...

"whether there is really something fundamentally useful in Lisp after all."

I take it for granted that just its lifespan and influence over the industry are proof to that. Of course, the same can be said of C. Still, like Paul Graham noticed, languages have been progressively adopted the Lisp model. And like Guy Steele, noticed, Java is halfway there from C++...

rant off. I will ignore your posts about your dislike for Lisp's syntax from now on. Have a nice day.

The question is framed thus: is Lisp/Scheme really more powerful or flexible than C modulo the syntactic sugar?

I'm guessing that it's actually less powerful and flexible, albeit with very convenient and easy-to-use syntax.

N.B. My point wasn't that I don't like the syntax of Lisp. (Quite the opposite, I like it very much.)

"wasn't that I don't like the syntax of Lisp. (Quite the opposite, I like it very much.)"

earlier:
"Lisp and Scheme are front-ends to C with annoying syntax"

yep, a genuine troller who changes the arguments according to the moment.

or perhaps just a masochist who enjoys "annoying syntax" "very much"...

it was fun for a while, mr. robot...

I think it is better for LtU if we just notice that the message is bogus, and stop responding.

[Moved]

Currently, I am at the point I will try anything (and by this I do mean anything). I do not have the time to run around after him, nor do I want to.

I suggest disucssing this (a)in the etiquette thread or (b) in the "site discussions" forum. The current thread really isn't the right place.

Suggestions of the sort "Ehud should do more work" aren't welcome, and will not be accepted. Has the community has indeed stopped working?

"Lisp and Scheme are front-ends to C with annoying syntax"

Your post amounts to the following: Lisp and Scheme are front-ends to C with annoying syntax. Fine, if you find that sort of thing exciting, I can understand that. Me, personally, I don't want nor need the existence of a front-end to C with s-expr syntax, I find coding straight C comfortable enough as it is.

Note that what he actually said is quite different from what you CLAIM he said.

Unfortunately when people cannot follow WHO says WHAT, then misunderstanding is bound to follow.

...I can't see how this line of discourse adds to the sum total of knowledge. Indeed, I think we are all a little dimmer for having followed it through this far.

Get over it.

"Note that what he actually said is quite different from what you CLAIM he said."

Ehud never said "Lisp and Scheme are front-ends to C with annoying syntax", so I guess the credit goes all to tchatkev... he was the one claiming something.

gosh...

Which of the following is your point then (multiple choices are ok)?

1. cons/car/cdr cannot be expressed using only lambda abstractions (see Lambda: the Ultimate Declarative, section 3.2, or the code by slom)
2. cons/car/cdr are so important for Lisp culture (as opposed to computational model) that they must be given the first-class status (for performance reasons? for reasoning reasons?)
3. the computational model of Lisp language (which Lisp? :) ) is based on cons/car/cdr
4. cons/car/cdr, either native or defined via lambda, take more than constant amount of underlying computation medium resources (e.g., processor ticks)

Points 3 and 4, but with the following qualifications: a) you don't need lambda calculus for expressing the Lisp computational model and b) you can't talk about the complexity of car/cdr/cons, since complexity is a property of an algorithm being executed on a computational model, and not of the computational model per se.

As for answering the question of "which Lisp" -- to do that, you'd need a more strict definition of what the Lisp computational model actually implies. This is a fault of the "Lisp culture"; Prolog or C programmers have no problem in that regard.

The last message (the I am replying to) is clearly a troll in my mind, and I suggest ignoring it.

...

Uniqueness type inferencing system?

The ones I've seen blow the stack in certain special cases.

Don't bother asking for examples; it didn't work last time.

I believe most humans deal better with words than with numbers, when it comes to giving things names. Our children are not given binary strings as names, etc. :-)

Yes... I suppose it was a small nitpick but I agree. It's a small issue, but usability seems often to be in the details. I just wish that dealing with the outside universe in Scheme could feel as natural to me as the rest of the language, which I love.

When I first tried Scheme, I used guile, since it was already installed on my workstation. This time I choose scsh because I'm most interesting in finding a replacement for perl & ruby.

I've also been searching for a really good, really fast implementation for OS X/darwin PPC. On my x86 machines I just use MIT Scheme because I never do much non-trivial development on them, but I'm currently on the market for a sexy and fast, R5RS-compliant Scheme that'll compile on OS X.

And, I tried really hard to like Emacs but failed.

Emacs is strange. I've been trying to learn how to use it for a few years now--I even used the much-vaunted SLIME mode when I was teaching myself Common Lisp--and I always find myself going back to TextWrangler or BBEdit or metapad (whatever's installed on the system I'm using)... it seems that once I have a mastery of it it'll be the best editor on Earth, but so far it has twarted my attempts at every turn. What is the best way to learn Emacs? is there some trick I'm missing?

(Not to get off topic too much, but) Emacs comes with a built-in tutorial. I used it when I first starting learning Emacs and I thought it helped. It is described in many web pages, e.g.: this one care of somebody at U Chicago. Basically, you press the Esc key, then x, then type in "help-with-tutorial" and the Enter key (in Emacs speak, that is all "Meta-x help-with-tutorial"), which will launch the tutorial for you.

I've found the key to Emacs fluency (and Lisp fluency via Emacs) is relentless customization and automation. Emacs is designed to be extended and made more friendly in baby steps far more than any other editor I've used. Along these lines, you should spend quality time with:

• "C-h v" (apropos-variable) and "C-h a" (apropos) to look for features you might not know about;
• "C-h k" (describe-key) to find the function names for interactive commands, so you can combine frequent sequences into your own functions;
• "M-x find-function" to see how editing commands are implemented, a wonderful repository of Elisp (and C) best practices.

Here are some life-improving commands: beginning-of-line, exchange-point-and-mark, forward-sexp, transpose-chars, ediff-revision. It's also worth learning these alternatives to harder-to-reach keys: tab = C-i, return = C-m, forward = C-f, backward = C-b, down = C-n, up = C-p, backspace = C-h (requires config). This seems really sick to most people but the ones who practice it love it -- and that's best kind of thing to learn!

If you ride the bus then the Emacs Manual from GNU Press is good too.

Bigloo looks really cool. I noticed that the current version hasn't been updated since about a year ago. Is that because it is really stable? Are you (rkb) an experience Bigloo user, and, if so, can you summarize your opinion?

Bigloo looks really cool. I noticed that the current version hasn't been updated since about a year ago. Is that because it is really stable?

Yes, Bigloo is stable and mature, and it's actively developed and maintained. It's been successfully used in commercial projects, such as for the implementation of the Roadsend PHP compiler.

Bad luck or a forgiving definition of "stable and mature"? :-)

(Subject line refers to this character)

I just tried the following on a Debian machine that didn't have bigloo installed. First, I created a file called hello-world.scm:

(module hello-world)
(display "Hello, World!  Apparently, Luke is unlucky! ;oP")
(newline)

Hello, World!  Apparently, Luke is unlucky! ;oP

There you have it - computers don't lie!

Keep in mind, though, that Bigloo compiles through C, so one way problems could occur is if your C environment isn't set up correctly, or isn't compatible with Bigloo for some reason. I haven't encountered that myself, I'm just speculating as to the reason for your luck.