## Lisp Lovers, how would you fix Lisp or bring it up to date?

Lately, Joel on Software's discussion forums have been a hotspot for Lisp discussions, probably because Joel's been learning Lisp and hanging out with Paul Graham from time to time. There's a thread today called Lisp Lovers, how would you fix Lisp or bring it up to date?.

I'd like to ask the same question to people who hang out here. I think it would be best to keep the answers to the question at Joel's forum so it's all in one place.

I've posted my reply to Joel's forum. Please comment on it if you have any thoughts.

## Comment viewing options

### implement it on the flash player

Implement lisp on the new Flash player 9 and show everybody what lisp is capable to do.

### That's a great idea

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?

### Sounds like Hop

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

### Make sense?

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

### Java

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

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

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].

### Lisp in Flash 8

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

### feature list ?

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

### Algebraic Types!

I recently went back to using Scheme, after a long hiatus. After a bit, I added algebraic types, like those used in Haskell and its predecessors. This lets you write overloaded functions really elegantly:

(fun (add a b)
(+ a b))

(fun (add (Complex ar ai) (Complex br bi)
(Complex (+ ar br) (+ ai bi))


To my surprise, this works *really well*. The things that used to bother me about writing large programs in Scheme are fixed by the addition of algebraic types.

You'll note that there are no type declarations -- that's because this implementation is latently typed, just like Scheme. It still works well.

Some of the complications in Haskell surrounding polymorphism, the monomorphims restriction, and boilerplate code becomes really simple in Scheme with algebraic types, because Scheme does its type tests at run time. Sure, it's cool when the compiler can remove them, but without requiring this, you get something really powerful and simple.

In a way, this is really just a syntactic idea. There have been proposals for type declarations for lisp/scheme, but I find that adapting Haskell's notation to Scheme makes it quite readable.

After college, I spent years using languages other than Scheme, and spent a lot of time working on a new imperative-style language. But when I added algebraic types to scheme, I took my decade-long language design project and just tossed it away. Coding in scheme with ATs is just really productive.

### Code to share?

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.]

### Sure!

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.

### "algebraic types"

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

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.

### Algebraic types vs. unions?

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?".

### I agree

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.

### Revisiting MapReduce

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.

### Data Parallel Algorithms

You might also like Data Parallel Algorithms.

### I don't think it's been

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.

### It has, actually

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 :)

### Ah, but you've been deceived...

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

### Algebraic Types vs. Discriminated Union

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.

### "Sum of Products" vs "Sum"

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.

### Type-freedom

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.

### Grounding the discussion

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.

### Muck with the semantics

To me, the great practical beauty of the Lisp family of languages has always been their malleability. You can change the semantics of the language without needing to make big changes to the syntax, and for some reason Lisp programmers don't seem to have a problem with this. They learn six new control-flow constructs before breakfast.

I want to see Lisps with lazy evaluation, Lisps with dependant types, Lisps with parallel-programming support built in, Lisps with whatever cool features people want. Greg Travis already pointed out one cool way of fiddling around with Scheme by adding Haskell-style algebraic types; I want to see more innovation like that.

### Real Soon Now.

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.

### I think the macros of Lisp

I think the macros of Lisp are also Lisp's biggest weakness. It's kind of an excuse for the language designers to provide less then needed build-in functionality. And the basic feature-set of Common Lisp simply isn't big enough. With macros everybody can build it's own little language and in fact many Lispers do. While this approach has it's advantages in certain areas, it also has it's weaknesses and with Lisp it's particulary dangerous, because it's so easy.

All those meta-programming-stuff is only needed because the language isn't powerful enough in itself. I don't want a 'language construction kit' to build a applications by building a new language first, I want a language which has all the required functionality already build in.

Lisp is in fact 'un-fixable', because to fix it you need to remove its most acclaimed feature. Why not leave it like it is and accept that it is (and will forever be) only a niche language.

### Why would you have to remove

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

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

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.

### Hmm...

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.

### Rehashing

This conversation sounds familiar. There are also lots of threads on Lisp and macros.

### Bring lisp up to date? Never!

Bring lisp up to date? Never!

Here's why:

(defun learn (a r beta)
(incf (aref n_a a))
(incf (aref Q a) (/ (- r (aref Q a))
(aref n_a a)))
(loop for a below n
do (decf (aref p a) (* beta (aref p a))))
(incf (aref p (arg-max-random-tiebreak Q)) beta))

Nothing against this person's code, but seriously guys... Call that a programming language ('programming' granted, but 'language'??

Oops. forgot the bracket. ;)

### Something against that person's code

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

### Anti-obfuscated language challenge

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

### not necessarily pertitent

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 syntax is always funnier on the other side

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

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.

### Reinforcement Learning?

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.

### macros

I've posted this over in the Joel on Software thread, but it's topical to this discussion, too.

Macros are bad. They're a preprocessor. It doesn't matter that the preprocessor runs in lisp and munges lists, it's still a preprocessor and it breaks the purity of the program.

Everything good you can do with macros, you can do in a more powerful language with higher-order functions.

### Everything good you can do

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

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.

### Macros

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

(trace-function my-function)

(trace-function 'my-function)

### expressive power of macros

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.

### You need a macro to take a derivative?

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

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.

### Common Lisp

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).

### untrue

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


### Better libraries

The major thing wrong with Lisp isn't the language, but the standard library. It's large, yes, but it doesn't come anywhere near the usefulness of what you get out of the box with (dare I say it) Perl or Python.

I still write a lot of Perl simply because I have access to large, standard libraries which work perfectly across platforms: sockets, regular expressions, various internet protocols, database access, binary data packing/unpacking, etc.

### my wishlist...

...for amusement:

1. Optional strong typing (at a function and/or module level) ala Haskell
2. Optional strong functional programming constraints- Be able to mark a function or module as "functional" and have the language enforce lack of side effects
3. Easier currying
4. A smaller core and a more rigorous process for standardizing libraries (ala scheme)
5. Networking/unix interface standard (ala python/ruby)
6. A standard sexp->html conversion (ala Rails rhtml)
7. Optional syntax (ala Arc)
8. Optional hygenic macros (ala scheme)
9. Have an inline pseudo-assembly available and standard (ala Parrot- essentially allow people to write crude but wicked-fast JITed assembly in a platform-agnostic pseudo assembly- Or allow inline C instead if you must)
10. A standard UI toolkit
11. Continuations

and a few crazy ones:

12. A CL-based EMACS-like, fully CL-scriptable ide as part of the CL standard (a true programmer-friendly language would have an editor as part of the standard :)
13. A facility for writing "code crawlers" in a clean manner (see the code crawler stuff in "On Lisp")
14. Allow macros to go not just between sexp->compiler and reader->sexps but also from sexps->display (think about that one for a while)
15. Have a CL-based OS defined by the standard that is pure CL that can be run virtually in a host environment and is used to run the CL code in a highly documented/predictable manner.
16. When the Lisp compiler/interpreter downloads, have it ask you what features you want (down to a very low granularity) and then have it "write" the lisp compiler/interpreter for you on the spot as per your specifications, using some kind of "patch" system- That way, if you only mark the things you want it will generate a minimally complex lisp compiler/interpreter for you that you can easilly understand if you go under the cover. This should include an option for turning off optimizations, so that you have the option of reading compiler/interpreter code that isn't obfuscated by performance enhancements (which greatly obfucate compiler/interpreter source code)

### Check, check, check ... :)

***
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

### Mandate that no computer language be taught before LISP

because of the learning asymmetry.

that asymmetry being that learning LISP does not prejudice one neurologically against other languages,

yet for some reason learning other languages seems to substantially interfere with LISP learning.

LISP/Scheme itself I would not change.

Programmers, being a far more superstitious lot than I believed before becoming one, will or will not flock to LISP/Scheme at some point.

Their refusal to do so isn't a judgement on the language per se (especially when those decisions are being made more and more by business, not technical, types).

### XML'lize it!

The obvious thing to do is to replace all those crappy SEXPs with XML.
XML is better engineered than Sexp

This would enable us to use universally available browser based XSLT processors as the common virtual machine implementation.

The semantics of the language should be entirely transformation oriented, implementing recursion by iteratively transforming the code.

(Hokay Folks, I'm trolling you. It's suppose to be funny. Laugh.)

### More characters

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.

### why not just use newlisp?

http://newlisp.org

I like it a lot.

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.

"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.

### Hmmm... First, have an ABI

Hmmm... First, have an ABI specifying object layout all the way down to fixnums and calling convention. Mandate support for cdecl, stdcall, etc. Standard "lispcall" includes mandating last-call optimization (full stack frame reuse in the general case). Second, compilation is the default, not interpretation. Eval is a feature of the debug system.

Third, semantics are of a strongly typed language, but where variables can be of type 't' (object) and thus hold any value. Assignment to more specific types is like dynamic_cast. Six, mixed feelings about multimethods, but mandate a simpler (than CLOS) standard object system and revamp the type system around this. Type system and structs/classes allow "mapping out memory" like C does. Makes for nearly seemless FFI (which is part of the ABI, hence standard).

Seven, use a C/Pascal style syntax, but where nearly every construct is an expression: foo(1, { doit(); andAgain() }, 34). That kind of thing. Implement AST patmatch style syntax definition. Eight, ditch the convoluted package system in lieu of a simple module system.

Even preserving infix syntax, there's tons that can be and should be changed to meet the expectations of the recent generations of programmers (even the clever ones).

Oh, develop the reference implementation on Mac and Windoze and build an interface with Apache via a "servlet" model right out of the box - get used to high quality GUI support and support for Web programming as real ground zero applications domains in which a language must perform well. Only distribute a full tool suite. You can't require users to debug make files or frob GCC to get the thing running.

Running on old MIPS boxes to build theorem solvers can wait for later :-)

But Lispers always seem to worry really hard about the wrong things :-)

### While we are on syntax

While we are on syntax I would like to remove parenthesis at the top level
Eg.

fun (add a b)
(+ a b);

fun (add (Complex ar ai) (Complex br bi))
(Complex (+ ar br) (+ ai bi));

(the original had a missing parenthesis btw)

### R6RS is the correct

R6RS is the correct direction for me. There is still quite some "left for R7RS".

### R6RS does seem to address

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?

### I know it is a bit of offtopic here

...since it is too hackerish. But, in order to fix what I really did not like about Lisp and Lisp macros, I've just added a way to handle a context. It was sufficient to significantly raise the abstraction level of macro metaprogramming.

The trick is in lexically scoped macros (like in RxRS, but in true CL style) and in control over the order of macro expansion.

This approach is described in this docs (section "Agressive metaprogramming"). With such a feature it is much easier to implement DSLs on top of pure macros.

### Replace it with BitC?

For many purposes BitC preserves the substantive advantages of LISP while eliminating many things that make programs really hard to maintain in practice. Because of the type inference, it's nearly as useful as a prototyping language, but it compiles a lot more efficiently and it provides much stronger error checking.

Admittedly, if you drank the DEFMACRO cool-aid you have a problem, but then, that was true already -- and before somebody jumps me on that, I built the first hashing DEFMACRO implementation for Franz Lisp in my ignorant youth, so I really do know how badly macros are abused. Which just goes to show that ignorance really is BLISS.

Jokes aside, I'm not saying that BitC is a drop-in replacement for LISP, but depending on what you are trying to accomplish it's a potentially interesting alternative.

Since this discussion is religious, shap hereby ducks quickly.

### Defmacro is easy to abuse

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).

### Dangerous language features are dangerous

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.

### Not that C is the ultimate answer but....

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

### C isn't special (technically)

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.

### boring agreement

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

### Manufactured dissent

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. ;)

### Lesson learned

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

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?

### Below the level of LLVM

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

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. :-)

### C's dominance and alternative approach

(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

### Why not go whole-hog

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.

### In its day, LISP was an

In its day, LISP was an incredibly advanced beyond-the-state-of-the-art tour-de-force of a language. I hardly feel that the minor tweaks typically proposed will produce a language in that class as compared to current ones.

My take on what a new language appropriate for AI (which is what LISP was developed for) should be like is detailed in my AGI-08 paper at http://www.agiri.org/variac_hall.pdf

Historically, AI has been the driving force behind many if not most of the advances in programming languages. LISP introduced abstract syntax trees (ASTs) as a basic datatype, and automatic storage management. It was also arguably the ï¬rst functional programming language. PLANNER, PROLOG, and various theorem provers introduced automatic inference, now widely used as the mechanism behind the type systems of most modern languages. SNOBOL (designed for natural language processing) introduced pattern-matching. The â€œobject-orientedâ€ semantics of many modern languages can be traced back to â€œframe-basedâ€ AI systems of the 1970s.
LISP and PROLOG are prime languages for writing programs about programs for two main reasons. First is that they do have ASTs as primitive datatypes, together with a collection of operations on them of which needed functionality can be easily composed. Second is that their semantics are already reasonably abstract, so that neither programs written in them, nor programs written by those programs, need be concerned with details such as register usage, linkage conventions, or storage allocation.
Properly designed and implemented, high-level programming abstractions can reduce the size of programs by an order of magnitude as compared with the same programs in lower-level languages. But the effect is compounded in automatic programming programs (APPs): not only is the APP simpliï¬ed compared to a low-level program doing the same task, but the task itself is simpler, since the object program is also simpliï¬ed. For higher-order APPs, e.g. ones that write APPs themselves, the effect is exponential in order. We will refer to this phenomenon as the recursive simpliï¬cation of the automatic programming problem.

Josh