Lambda the Ultimate

I was just thinking the other day that Javascript / ECMAScript seems to be filling the niche that the GNU project had hoped Lisp would occupy.

Now bokel's post has given me the hare-brained notion that we can head Javascript off at the pass by making a Lisp frontend to the Haxe framework.

Haxe compiles to Neko which has Lisp like semantics, so I'm optimistic that a Lisp frontend is feasible. The Haxe framework supports Apache (via the mod_neko plugin), cross-browser Javascript and Flash. Features of Lisp such as continuations and XML S-Expressions would then come into their own.

Does this make sense, anybody?

Something like this? Also, this paper might be interesting to you.

Quite a bit actually. It's already done, albeit "alpha-state" of just the core. Go nuts!

Of course, we are going to get back to the never-resolved quest for a decent virtual machine with hardware prospects to underlie the XDM-based environments.

-t

It's funny that you bring that up, because I keep on thinking that with frameworks like Echo2 and Google's new GWT, that someone will write a compiler for a subset of Java targetting the Flash 9 VM. In fact, I wouldn't be surprised if Adobe did it themselves. When WPF/E hits the streets, Flash is going to need all the edge it can get.

I know osflash.org has some documentation on what the Flash 9 bytecode is all about, but there are still some questions and I haven't seen official specs from Adobe yet.

The guy that wrote Neko and the open source actionscript compiler posts here regularly. He should have some insight on what the new Flash 9 VM is capable of.

Flash has such a high market penetration rate, that it would be great if we had more choice in languages. With WPF/E you'll be able to have the engine either interpret XAML/Javascript or .NET bytecode - which means you'll be able to write it in any compliant .NET language.

I'm currently working on the Flash 9 compiler for haXe. The AVM2 file format is now completely reverse engineered so I'll try to complete the documentation that I started on osflash.org later.

I don't think that Adobe will try to do something like another language on the VM9 anytime soon. They're really sticking to ActionScript3, for the best and the worse...

Personally I don't like AS3 so much. The language is quite verbose, and the only good advantage is the AVM2 which is a completely new VM with some runtime exceptions that is a lot more efficient than previous one. I actually found that the code produced by the Adobe AS3 compiler was not so good quality so you can expect a faster execution time in haXe.

I think haXe is a great solution for crossplatform development, since it supports Flash 6-9, Javascript and Neko backends, for all browser, server and desktop application programming.

For the record, Scott Peterson has been working on porting languages to run on Flash. Try googling for his demos of getting a (playable) port of Quake 2 and some other things to run. I think this was first announced 3rd or 4th quarter last year. While the demo are gimmicky, the implications are deeper [esp. wrt. the JVM and JS1/2].

I've implemented Lisp in Flash 8 here and am currently working on a version in 9.

What features did you implement? (trace _root) worked, but (list :a 1 :b 2) didn't.

I've been interested in this possibility for awhile, and it seems the design space for data constructors and pattern matching is pretty large. I'd be very curious to see your implementation, if it's available or you're willing to share it.

Incidentally, this same approach seems to be quite popular in Erlang...

[edit: I'd be wary of calling this feature "algebraic types", by the way... "types" is arguably misapplied in this context.]

I'd love to share the code.

Since it's just something I threw together for my own work, it's pretty irregular, and might take a bit of hacking to get it working elsewhere. I'll include instructions.

http://www.panix.com/~mito/swat/

Please let me know of any problems you have, and I'll try to correct them.

I contend that these *are* types. Sure, they're not compile-time, and they aren't even strong -- it's latent typing, just like with scheme.

Although I read a lot of the language papers discussed on this site, I still find type theory to be pretty hard to understand; my eyes glaze over when I see formal specifications, and it's been a while since I really tried to understand one.

I use the following definition of type.

Type: noun. Partial information about a run-time value.

I greatly admire Haskell, including the way it manages to be strongly typed and compile-time-ly typed. However, I also think that Haskell is brilliant because of the elegance of algebraic types, and the simplicity of the syntax. Other languages with some form of algebraic types just don't seem as elegant.

So, I've taken the superficial form of Haskell's syntax for ATs, and added it to Scheme.

I agree with Paul Graham: a good language should let you sketch. I have heard/read that it's tricky to get Haskell programs to typecheck (and that when they do, they probably work on the first try). I've also heard that type errors in Haskell can be tricky to understand, at least for beginners. I've also further been confused by the various variations of Haskell type systems, what with the monomorphism restrction, the occasional need for explicit type annotations, etc.

So I ask: why not defer some of these checks to run-time, rather than making the programmer figure them out? Sure, doing all typing at compile time will produce fast code, but I'm willing to trade this for simplicity, just as people have been willing to use Lisp/Scheme instead of C.

I find that as I code, my types get tighter and tighter. I favor the approach of providing explicit types in the places where I really want the optimizer to succeed. I don't feel that I need a super-amazing type system (read, 'theorem prover') when I can just ignore it until I need to optimize things.

I recognize that this isn't just a speed issue -- the semantics are different. But I maintain that Haskell-ish algebraic types are a HUGE win in general, even in a latently-typed language.

To me, sketching in code is ignoring most details, to work out a few, and especially the feeling that you throw something together and see how it works out.

I don't know how well this applies to large scale architecture, but for small scale things it works nicely to define a few types that capture properties you care about but don't want to worry about, let polymorphism handle the things you don't care about at all, and sketch away.

It seems saves a lot of time and puzzling it might otherwise take to realize what you wrote is nonsense, without the hassle of typing everything. Of course, there's a great danger that your "sketch" will end up being sufficiently polymorphic you'll just add it to your program and run the real data through it!

My experience with 'sketching' is that as long as the project remains small, everything is nice, but if it starts to grow about a certain level of complexity everytimes a complete complete rewrite was neccessary.

But thats the difference between 'production' and 'prototyping'. And it's well known that some languages more appropriate for prototyping while others are better with production code. But I sometimes think that there are lots of people who work only in prototyping or only in production don't know about the other side. And this leads to all those misunderstanding about certain programming languages, or latent/static typing.

The question is if it's possible to have a language/paradigm which allows a smooth transition from prototype- to production-level without requiring a complete reimplementation.

An alternative name for an algebraic type (I think :-) ) is a "union" or "variant record". Since Scheme is type-free (given the definition of types as static), I think you can look at this as adding a new "shape" of value---a variant record rather than a list, number or something. These are indeed a pretty darn useful tool.

Doesn't EoPL use a similar macro system?

As far as sketching goes, one significant difference between a "dynamically typed" language such as Scheme and a statically typed language (with a good type system, anyway) is that when using the latter you have to understand the type system as well as the dynamic behavior of programs in the language. Understanding typechecking errors in Haskell or O'Caml are pretty painful, I suppose, but going at it by just writing code without thinking about the typing is going to really hurt.

On the other hand, sketching with the types can be pretty productive itself, once you understand the type system. Thinking, "I believe this function needs to produce values of this shape" and, "does this code produce the shapes I think it does" are both tolerably fruitful. Asking the same questions in an untyped language can be rather tedious, and I personally hate that nagging worry, "what happens if someone tosses a Bull into my ChinaShop?".

The distinction between "algebraic types" and "tagged union values" was basically what I was getting at. It's admittedly something of a nitpick. No matter what we call it, I don't disagree at all that this is a useful feature and would be welcome in Scheme (hence my request for the implementation).

I also agree with mcguire about the usefulness of sketching with types. It's a different experience than sketching with Scheme or Python, and maybe they have different strengths, but both are worth trying. For a cool and current example of sketching with types, you might want to take a look at Ralf Lämmel's Google's MapReduce Programming Model -- Revisited. I don't think it's been mentioned here before.

For a cool and current example of sketching with types, you might want to take a look at Ralf Lämmel's Google's MapReduce Programming Model -- Revisited.

Cool! Thanks for the pointer; I had not seen it before and it looks very interesting.

You might also like Data Parallel Algorithms.

I don't think it's been mentioned here before.

Right. I don't think I've seen this paper before. I just gave it a quick look, but it seem quite nice. You should post it to the homepage, I think.

Google tell me ...

All the papers I read are mostly coming from LtU, and I had read this one, so I figured it should have been already posted here. Mind you, you even commented on it, Ehud :)

Check the dates. That thread was a result of the comment you replied to. Causality looks different when time is spacialized. ;)

I'm not sure I understand the difference between Algebraic Types (AT) and Discriminated Union (DU). Is the difference mostly to do with the type system -- static/dynamic/latent/whatever?

To me, they are the same thing; but then again, I think a compile-time type error is just a run-time type error found early via partial evaluation.

Put another way, I think that static types are somewhat burdened by their history. Is the purpose of a type to partially describe a value, or to tell a compiler how much to add to the stack register? I prefer the former. In which case, it doesn't matter when you find the error -- semantically, it should be the same no matter when you find it.

When your program is mature enough that you want to really tighten the types, then you put in more declarations -- enough to find the type errors at compile time.

According to FOLDOC, Discriminated and Disjoint are pretty much synonyms when it comes to union. A value of a discriminated union has a tag telling you what branch it is, and a value of the appropriate type.
Think of unions in C (undiscriminated), with a tag telling you what branch of the union is present. Also called variants.

Algebraic usually means "Sum of Products", that is each constructor can carry several values, of potentially different types. Of course, this is isomorphic to a union type where each branch carries a tuple. O'Caml uses a syntax pretty much like this (but also allowing nullary constructors).

Algebraic data types are also called algebraic to point out the connection with algebras in math. If you think of an algebraic data type and its constructors as giving the signature of an algebra, then it is an initial algebra over all algebras with that signature. This also applies to sum types, but they only induce signatures that only contain single-argument functions. The name also suggests generalizations like Generalized Algebraic Data Types.

Since Scheme is type-free (given the definition of types as static)

Sorry to repeat myself from elsewhere, but: the Scheme language is type-free in the sense that the language specification says nothing about the types of terms other than literal values. However, the language does implement tags which support reasoning about static types, and working with typed values. The result is that Scheme programs are not necessarily type-free: programmers can assign types to terms and reason about those types. Via tag-checking, Scheme implementations help programmers ensure that they haven't made any mistakes in that process. At the limit, the main distinction here is the degree to which static type inference, proof, and checking is performed by machine, vs. by the programmer. Types can exist either way.

As most here know, there are many excellent, truly enlightening, articles and books (by Cardelli, Pierce, ...) on understanding types and programming languages (try googling for the last few words). So, I was wondering whether you could cite a few really good articles and books (a couple of sentences in the Scheme report doesn't count) that have been cited many times by programming language researchers that would define/prove these properties you are asserting (here and elsewhere on latent types and latently typed languages) in such a way that we can discuss them really productively. I, for one, am not convinced that tag checking provides much of assistance for reasoning about types or that types can exist without a type system (a concept that your post does not mention), and I also do not believe that repeated assertion is the way to go.

That's a fair question, but there's plenty of grounding to be found in, for example, the work on soft typing, some of which I have referenced in the past. I'm rather busy today, but as soon as I get a chance I'll put together a bibliography and a summary.

I don't claim that types can exist without a type system. I do claim it's possible to have a useful informal type system, though, and that such type systems have been successfully formalized by people who've done work on soft typing, for e.g. Erlang and Scheme.

I don't believe in repeated assertion either — I have, in the past, given fairly detailed explanations of my position, with relevant examples and references.

I recently started working on that sort of thing for Common Lisp. I already have partial continuations and a way to denote that certain binding operations (variables let, let* and lambda) should bind a given variable in the function namespace. Since, in order to implement continuations, I had to write a CL -> ~ Monadic form (~ because the monad's representation must be the identity to interface with normal CL code) and wrap every function call (and wrapping every variable access would literally be a 2-minute job), writing a couple macros and functions to dramatically the semantics is easy... and fun! I just have to make dynamic scoping work with continuations first ;) I think that once I provide rewind-protect (guaranteed to be executed before every invocation of the form it wraps) and unwind-protect, it's a simple matter of side-effecting the global value, right?

Note that asking for dependent types or ADTs in CL doesn't really make sense. The type system is as expressive as the concrete language (easy when static checking is not required), and I'm pretty sure that ADTs can be replaced by CLOS's generic functions. One can even shadow the standard functions to, e.g., make mapcar generic.

Why would you have to remove the lisp macros? Even if it were true what you say, that Common Lisp is missing some functionality than can be put in with macros, then the real issue is finding a good implementation of this functionality and standardizing it. Then you have your batteries included, and macros to go along with it.

If there is some kind of 'shortcut' somewhere, somebody will use it and someone else will rely on it. I think that Lisp it rather useful to try out new concepts, but it's not a good production language for the same reason. Language design is not easy and because of this many of those self-made language extensions simply aren't very good and sometimes conflict with similar extensions someone else made.

There's a second point: The Lisp-syntax. Many people simply don't like it and have difficulties to get used to it, but the syntax is also the prime reason why macros work so well in Lisp. To get Lisp 'up-to-date' it has to get a more 'usual' (=algolish for most programmers) syntax and this would conflict with the macros (I know approaches like in Dylan etc., but they failed both for the common programmer and for the Lisp-lover).

That makes some standardization all the more useful, however I still don't see how that would subtract from macros as a whole. I'm sorry, but I still find it very hard to believe that people would choose to roll their own functionality for things that there was all already a standard in place. Even if this were true, it wouldn't be limited to macros alone. Anything that's been implemented already, basically, would be up for grabs, be them libraries, syntax extensions, etc.

And, for your second point, changing the syntax would add very little, if not detract, from the language. Algol-ish syntax looks odd upon first seeing it also. At best, prefix syntax is a small hump, and that's only if you've already programmed in one or two languages with C-like syntax. Changing the syntax might encourage some to learn the language, though I would question the motivation of someone who doesn't want to learn a new language because something about it is obviously different. However, it doesn't add to the language.

Perhaps, but in the "real world" closed-source commercial Lisp app I've recently worked with, which has been around for some while, it's not macros that's the issue -- zero macros were defined. Rather, the problems were the mundane ones of any other similar codebase which grew by accretion.

But we've certainly used other peoples' (stable, battletested) macros. After all, a language designer can't predict all the domains the language is used in. Common Lisp is in particular very general purpose -- apparently one interesting LispOS comes from the bioinformatics world, a fairly unexpected direction.

Someone once mentioned that the problems of macros are similar to (for example) recursion; won't people infinitely recurse? Sure, but there are patterns one learns to avoid it.

Software which allows users to participate in design decisions can lead to problems, just like governments which allow citizens greater input. Maybe if you're in a company where your job is implementing orders from above, a more restrictive tool could be more appropriate.

Common Lisp is my language of choice, and I still can't figure out what's going on here because it's spaghetti code. It's using a bunch of variables (n_a, Q, p, n, beta) that are defined elsewhere and have meaningless names. The a variable used in the loop has nothing to do with the a argument (it's re-bound by the loop). I rewrote it in Javascript so those who don't know Lisp can try to see what's going on:

function learn (a r beta){
  n_a[a]++;
  Q[a] += (r - Q[a]) / n_a[a];
  for (a = 0; a < n; a++){
    p[a] -= beta * p[a];
  }
  p[arg_max_random_tiebreak(Q)] += beta;
}

Edit: fixed typo in for loop

On-topic exercise for the parent poster: design a language in which it's impossible to write obfuscated code.

I don't think that's what he was getting at. (As you know) Designing a language in which the programmer can't write spaghetti code is just as impossible as having the computer generate it from the human language spec. Rather than judging how easily one can obsfucate, it's better to look at how easy it is to write clean, easily understandable code. The main issues I see with s-exprs are that 1) there's a lot of noise due to the parenthesis and 2) most people aren't used to prefix notation. The latter likely diminishes as one continues to use the language, although it's still a barrier to readability nonetheless.

A side-effect of #1 is that, because of the lack of noticeable syntax other than those parenthesis, the number of visual clues as to program structure and operation is diminished. Granted, some of this can be made up for with syntax highlighting and other IDE features.

The OP gave an example of code that's essentially obfuscated, and extracted from a larger context. If he had a real point, he should have made it.

I think everyone can agree that "most people aren't used to prefix notation". You're also correct to assume that this "likely diminishes as one continues to use the language." However, the claim that it's "still a barrier to readability" is speculation on your part, which is refuted by many experienced programmers who don't find that to be the case, any more than the braces, parentheses, brackets, and semicolons are a barrier to readability for C-like syntaxes. At best, you could say it's a barrier to readability for some people, and what proportion of people is unknown, since most haven't tried to learn it.

The same goes for "the number of visual clues": the visual cues are different (indentation, keywords that represent structured constructs, plus IDE features), but it's a matter of getting used to them. If you spend some time learning languages that are truly syntactically different from each other, as opposed to variations on C syntax, you soon realize that they all require learning before you can recognize the cues that are specific to the language. Try reading Erlang, OCaml, or Haskell programs, for example, if you're not already used to them. Not just at the local scale, which can often be straightforward enough, but navigating through and absorbing large bodies of code in an unfamiliar syntax is always more difficult.

It all comes back to the original point: what you're used to, and what you choose to become used to. If you're not familiar with something, it's tempting to claim that it's somehow fundamentally difficult to get used to, because you can use that as an excuse not to learn it, and/or to defend your favorite status quo.

The OP gave an example of code that's essentially obfuscated, and extracted from a larger context. If he had a real point, he should have made it.

Yes, I agree. Clearly the parenthesis don't help, though.

I think everyone can agree that "most people aren't used to prefix notation". You're also correct to assume that this "likely diminishes as one continues to use the language." However, the claim that it's "still a barrier to readability" is speculation on your part

I meant to write "barrier to entry"; not sure why I put that. My mistake :-)

The same goes for "the number of visual clues": the visual cues are different (indentation, keywords that represent structured constructs, plus IDE features), but it's a matter of getting used to them.

The difference lies not in their kinds, but rather in their numbers. One of the most obvious examples of this can be seen in list and dictionary constants. Surely you can agree the the latter example has more visual cues and less overall noise than the former?

(setq val '(("1" 1) ("2" 2) ("3" 3)))


val = {"1":1, "2":2, "3":3}

This doesn't take into account syntax highlighting, so I wouldn't be surprised if the former looked much better with color, but the latter would also look a bit better, as well.

If you spend some time learning languages that are truly syntactically different from each other, as opposed to variations on C syntax, you soon realize that they all require learning before you can recognize the cues that are specific to the language.

I find ML to be much more readable than lisp, even considering that I have much more experience with the latter than the former. This is circumstantial, but interesting still. On the whole, though, you are correct.

It all comes back to the original point: what you're used to, and what you choose to become used to. If you're not familiar with something, it's tempting to claim that it's somehow fundamentally difficult to get used to, because you can use that as an excuse not to learn it, and/or to defend your favorite status quo.

Yes, I agree. I do maintain, however, that s-exprs have a lower readability potential, if you will, than a language like haskell or python.

My guess is that this code implements basic Q-learning, a reinforcement learning technique. a is the action, r the reward, and beta the weight/scale parameter. I agree this code ain't pretty. Comprehensions are the best way I've found for writing this sort of stuff.

Everything good you can do with macros, you can do in a more powerful language with higher-order functions.
There was a very good LtU thread on this topic.

I list three things you can't do without macroes here, though if you are allowing behavioral reflection in "more powerful", you get two of them.

Don't underestimate the usefulness of eliminating even one character of typing, such as

(trace-function my-function)

instead of

(trace-function 'my-function)

If it's easy to express the same concepts with HoFs, you shouldn't have any problem translating a macro written by Guy Steele to your language of choice.

After that, then try rewriting the Common Lisp libraries Iterate, Screamer, or Series without macros.
Macros in Lisp, Dylan, Scheme, and others are quite different from the C preprocessor.

How lame, this can be done with HoFs: http://www.haskell.org/pipermail/haskell/2004-November/014939.html

Well, granted, that Oleg can done these things doesn't mean anyone else could. It also doesn't mean that the macro-free version is as straight forward. On the other hand, Oleg doesn't require a literal lambda expression as argument, he can handle any old function (with the correct type).

Anyway, thinking of Lisp macros as a preprocessor does them injustice. I'd rather view them as compiler extensions. Sometimes, meta-programming is exactly what the doctor ordered, and then you want Lisp macros (or Meta-OCaml, or Template Haskell), not C++ templates (*urgh*).

Nice hack from Oleg as usual.

He says this can't be done in Scheme but I'm not so sure about that. Can't you use a similar trick to what he uses himself?

Suppose your algebraic functions are composed from a closed basis set: +, -, sin, cos, etc. Make these basis functions ad-hoc polymorphic a la the functions defined in Oleg's D typeclass. When passed numbers they behave as usual (i.e. they dispatch to the numeric versions). When passed a symbol or list they should behave symbolically, e.g. the application (sin 'x) should evaluate to (sin x) and the application (+ '(sin x) 'x) should evaluate to (+ (sin x) x). Let's say that we now have an algebraic function f which we want to differentiate. We simply evaluate (f 'x) which gives us back an expression tree that can be symbolically differentiated via pattern matching as usual.

As long as the algebraic basis functions are linked in dynamically from an external module this technique should be applicable even to already compiled functions compiled prior to the implementation of the above technique.

Speaking of Oleg, here's a common lisp version of the program to symbolically differentiate compiled functions (without using macros) and funcall the resulting symbolic expressions (without eval).

Even something trivial like PUSH! can't be done with only HOFs:

(define-syntax push!
  (syntax-rules ()
    ((_ b v) (set! b (cons v b)))))

(let ((xs '()))
  (push! xs 1)
  (push! xs 2)
  (push! xs 3)
  (equal? xs '(3 2 1))) ; #t

***
Semi OT, but I figured some granting in the midst of all the wishing couldn't hurt. I'm also looking for comments on the extensions, especially the aesthetics :) Lispers and people who like quibbling over aesthetics should find the post interesting. For the rest of us, skip to the last paragraph.
***

A good portion of your wishlist is now done or doable, by which I mean that the information is available, and that time and motivation, not expertise, should be the main prerequisites for success.

I begun with 13., a portable codewalker for Common Lisp. Obviously, there are some disadvantage to being completely portable, like having to assume that the original lexical environment is the top level, but it's good enough for my needs. Unfortunately, I can't compare to the code in On Lisp yet.

This let me write 11. (partial continuations), and 3. (extra syntax to bind to the function namespace, and reduce the need for funcall by inserting it when obviously necessary). In order to do that, I had to do 4. (smaller core), by transforming a certain number of special forms, especially those that allow non-local control flow in terms of simpler ones. Unfortunately, "simpler ones" means call/cc here (well, really, throw/catch, and the latter implemented via call/cc). Moreover, the transformer explicits binding (like in monadic style), and user-defined macros or functions can be inserted at such points, making it easier to extend the language.

The results so far: Oleg Kiselyov's example of Y via self-application of call/cc looks like this, in portable CL:

(#'foo binds to foo in the functions's namespace.)

NLI> (defun Y (#'f)
       ((lambda (#'u) (u (lambda (x) (lambda (n)
                                       ((f (u x)) n)))))
        (call/cc (call/cc 'identity))))
Y
NLI> (with-nli (defparameter fact
                 (lambda (#'self)
                   (lambda (n)
                     (if (zerop n)
                         1
                         (* n (self (1- n))))))))
FACT
NLI> (with-nli ((Y fact) 4))
24

It's all transformed to normal CL code, and can interact with normal CL functions meaningfully: the capture of continuations when a normal CL activation record is on the stack is detected and disallowed, calls to and from CL are transparent and generic functions, including method combinations, can be converted to allow capture. However, non-local exits definitely cannot be shared.

The code is currently available in its glorious wartfulness at http://www.discontinuity.info/~pkhuong/lisp.html. I should have much better documentation come October.

On my todo list is the addition of some more syntax (possibly even providing a custom reader to allow for more experiments), especially for anonymous functions and some sort of simple message passing implemented on top of CLOS (~7.). As for your remaining wishes:

1. Is hard, very hard; CL seems to be actively anti-type inference at times. Still, you can have arbitrary runtime-checked types.
2. Might be doable, similarly to the way the continuations code is able to determine when it calls a normal CL function. However, not sure about the gains, especially considering that the checks would definitely be made at runtime.
5. 6. Just pick one, any one. Just pick a single implementation too ;)
(Yes, I agree, having a de facto standard would be neat. However, I think it might be a bit too early for that right now, especially for sexp->xml)
8. Doable. Not sure there's a pressing need, though.
9. Portable assembly is usualled called C these days. There is a library to do inline C in SBCL or CMUCL (cinline). It might be possible to make it portable with CFFI.
10. I'd probably just suggest something tk-based, like ltk, or cello.

Back to something more on topic: How would you make language extensions easier to write? The CLOS MOP makes it easy to write custom method combinations by using generic functions that emit sexps. I think that annotating the semantic elements of the code (e.g. function calls, binding values or accessing values) with calls to what might be macros or functions is helpful. However, I don't think that lists are the right abstraction for this. Even with a meta-level quote, the inability to annotate atoms or sexps is sometimes painful. On the other hand, I tried to use a codewalker based on CLOS in the past, and it felt very awkward. Maybe cons-lookalike objects would be "just right" for lispers?

Paul Khuong

I have often wondered about the relation between XML and Lisp. Way is " imagine an attribute expression in here, the editor won't display it!" ; better than ( attribute . . . ). My guess is that the XML lets me find the end of the list without any counting. We could have this in lisp if we had some "hieroglyphic" looking characters to substitute for parenthesis. Sometimes in Lisp one can do ([{ xyz }]), because ({[ are interchangeable. This lets me identify up to three nested lists. If we only had more characters. There are many other ways to use special characters such as sigels.
Edit: I can also see an argument for making programs look more like mathematics. Of course in that case characters won't do at all.

newLISP has already been discussed here. And it seems to have some problems. Particulary these:

In newLISP, lambda expressions evaluate to themselves. They are a subtype of the list data type, a first-class data object that can be manipulated like any other list. In Common Lisp and Scheme, lambda expressions, when evaluated, return a special function data type with its free variables binding to the current environment and forming a lexical closure.

In newLISP, all variables are dynamically scoped by default.

In newLISP, all arguments to a user-defined function are optional. Unassigned argument variables will assume the value nil inside their function.

Logically, there are no unbound or non-existing symbols in newLISP. Any unbound or non-existing symbol is bound to nil in the current namespace when it is first used.

Anything new about newLISP? Did someone follow it and have more to say than what was discussed in the linked thread?

"lambda expressions are a subtype of the list data type" does not look bad to me, rather convenient. On the other hand doing a lexical closure requires setting up a "context" to capture variables which looks a bit cumbersome.

"all variables are dynamically scoped by default" (Wikipedia) Well that does not matter when using variables that are either local or passed as parameter. Again the answer in other cases seems to be contexts.

"unbound or non-existing symbol is bound to nil" that is a bit of safety removed (compile-time error) for scripting convenience. I suppose that eliminates newLISP from contending for a large project. The authors of the language probably estimated it helps make newLISP a better alternative to Perl than CL.

R6RS does seem to address the multiple implementation problem with Scheme. Are there changes in the library system too?

Anybody has a comment on newScheme?

Since it is the most expressive programming techinque ever existed. It is not defmacro we have to blame for that cases of dramatic misuse, but programmers who do not use macros correctly. There is a methodology suitable for a very maintainable macro metaprogramming: macro must transform one well-defined language to another, in small steps. Even some level of static typing is applicable here (yet within the Lisp framework).

It is not defmacro we have to blame for that cases of dramatic misuse, but programmers who do not use macros correctly.

That's exactly like saying "It is not C we have to blame for pointer errors, but programmers who do not use pointers correctly". While technically true in some sense, it doesn't mean that the language feature in question is above suspicion.

That's exactly like saying "It is not C we have to blame for pointer errors, but programmers who do not use pointers correctly". While technically true in some sense, it doesn't mean that the language feature in question is above suspicion.

So, in your alternative universe... what language will you use to bootstrap? Where in the bootstrap process will you eliminate pointer errors with language-based protection?

Conversely, I'd note that you can have really beautiful C code based on library APIs that are so conservative with how they use pointers that your aim of neutering their dangers is effectively achieved.

-t

I think you may have missed my point. I'm not saying that there's never a need for low-level access to memory. However, C provides such access in a particularly unsafe and uncontrolled way, and the only real justifications for this are historical. The fact that programmers can write safe code in C if they're careful is an apology for C's approach, not an argument for it.

It's certainly possible to improve on the C situation, as e.g. Cyclone and CCured demonstrate. Typed assembly languages are another possibility. The Lisp Machine example shows that it isn't absolutely necessary to have a language like C in the picture. Many other points on the spectrum are possible. But how closely you choose to match your bootstrapping language to the hardware is rather beside the point I was making.

Yeah.

My money would be roughly on a return to something like the lisp machine approach but via a VM that can host JVM and Javascript, XLST, and XQuery (and lisp) all handily -- and that maps onto power-efficient hw that isn't all that hard to fab.

-t

I think this indirectly hits on one of the reasons that C has been successful - that being so minimal and close to the machine, it creates a fairly agnostic environment in which all other languages are equal.

(That's of course not completely true for functional languages which make different fundamental assumptions, but it's still more true than it is for e.g. the JVM.)

C's role could be taken over by a safer systems-level language that retains or even improves on this agnosticism, but the cost/benefit ratio on that is, in some senses, low (despite the howls of protest you may hear).

If a VM takes over this role, it's either going to enforce e.g. an object model on the world, as with .NET and JVM which tend to either force the languages that run on them to conform to their model or else pay a price for not doing so.

Of course you can go for a low-level VM, but that doesn't get you the same benefits of integration and commonality across systems. So there's a fairly fundamental set of tradeoffs here, and the ultimate decision factors will be the usual combination of economic factors, successful marketing, and chance, with a slight nod to technical issues here and there. IOW, it's probably gonna suck. ;)

These are, as usual, excellent points. Probably the biggest lesson I've learned with respect to language installation/adoption issues over the years is that having the C runtime library and memory model "baked in" to every popular operating system available raises the bar tremendously on getting anything else used—to such an extent that even most programmers don't realize that anything else is possible. I've probably spent the last two years or so getting over that.

C's role could be taken over by a safer systems-level language that retains or even improves on this agnosticism, but the cost/benefit ratio on that is, in some senses, low (despite the howls of protest you may hear).

I've been wondering why no one's created a "portable assembly language" that could address the deficiencies of C as a target (support tail calls, etc.). I mean something like TALx86, but for an abstract machine. C-- focuses too much on higher-constructs and language interoperability, and I'm looking for something that operates below the level of LLVM. I've been toying with the idea of a simple TAL targeting the GNU Lightning abstract machine.

force the languages that run on them to conform to their model or else pay a price for not doing so.

A portable TAL-based VM need only enforce memory and control-flow safety. Of course, even these constraints are difficult if you want to run C-like languages, but we can get pretty close. The downside is decreased interoperability, as you mention. Anyone know of any work like this?

naasking: I'm looking for something that operates below the level of LLVM.

In what ways? I just re-read this old thread in which much back-and-forth about LLVM vs. other systems got bandied about. It was interesting to revisit the material that left such an overwhelmingly bad taste in my mouth. This was all in reference to LLVM 1.4; the current version is 2.2, and much has improved since then. I'm also intrigued to see that a first cut at formalizing the specification of the LLVM syntax, semantics, and type system is available. It might be worth attempting to reproduce and extend this in Coq, since LLVM also has OCaml bindings, so LLVM could (in theory) be easily targeted by OCaml code extracted from a Coq development around LLVM's semantics and type system. Imagine such a development as a target of A Very Model Model of a Modern, Major, General Type System or Adam Chlipala's Lambda Tamer tools.

I actually like LLVM very much. I'm beginning get the impression that it's a little too restrictive in some senses though. Intrinsics and arch-specific lowering passes are sometimes needed to efficiently compile certain constructs (see the threads on the GC intrinsics for instance). Adding concurrency constructs isn't at all obvious either.

I conjecture that a portable assembly language, instead of a "low-level C-like language" like LLVM, could avoid some of these problems, though likely at the expense of difficulties elsewhere. Still, I think a simple abstract machine can get you a sufficient fraction of LLVM's advantages, that pulling in the heavy weight LLVM seems less rosy for the a JIT (which is what I'm looking for). Besides, a TAL project would be good learning experience. :-)

(This is really in response to Anton's comment and the two that immediately follow it.)

I think the opportunity in this area is a low-level VM but not quite what people usually mean by that. And, in reference to some of the material above: yes, C's memory model and C's execution model are very much the obstacles to overcome.

Part of the opportunity comes from the trend towards (some eventually stable notion of) multi-core processors -- real concurrency. Part of the opportunity comes from making the memory hierarchy easier to manage. And part of it does come from introducing safety and good object support very low -- but without committing to particular GC strategies or object models. (Hence the "FSB" work-in-progress machine I linked to way above.)

There are, and long shall be, lots of impractical-to-replace libraries that use the C models, but that's no reason to constrain a VM too badly there. Rather, it's an FFI challenge.

A final part of the opportunity is to start trying seriously to influence hardware. For example, I have some serious doubts about the long-term future of memory virtualization hardware (in current forms). The illusion of vast, flat address spaces isn't true at the hardware level and, for most practical purposes where performance matters at all, doesn't hold up at the software level. So, to heck with it: let's treat L2 as the entire address space and bring back segmentation. As a virtual machine, if you can target a VM like this, it should be more straightforward to get good performance on current hardware. As a hardware platform, this approach should simplify a lot resulting in performance wins, gate-count drops, and power consumption wins.

Hope that makes some sense and is worth reading. I "don't talk as good" as you guys who are practiced in having to express yourselves for publication and similar needs. :-)

-t

and abolish the pointer-as-int construct completely?

I'm half serious. I'm not sure what to replace it with, exactly--but one of the more "programmer-friendly" instruction sets over the years was that of the 68k. The 68k, at least initially, had separate register files for data and addresses (though later versions would effectively treat the two as a single register file).

But what if a similar architecture were created, but which enforced a well-grounded-in-type-theory separation between ints and pointers? Quite a few modern processors still maintain a separate register file for floating-point, after all.

Read into typed assembly languages. There is a great deal of literature on typing pointer operations, to the point of safely typing garbage collection.