Lambda the Ultimate

With all due respect, I beg to differ with the notion that "mucking about with parsing and ASTs, while necessary at some point, is really a serious distraction from getting anything meaningful done".

From a human factors perspective, Syntax matters and is an under appreciated facet of language design. Just look at how easy it is to mangle a C typedef without triggering compile-time errors.

Given that the language design space has been pretty well explored by the major languages, your best bet at creating something that will be widely adopted is to focus like a laser on End User usability and syntax has a critical impact at that level.

...on which we might disagree: that syntax is an underappreciated facet of language design, and on the order in which the design of a language's semantics and syntax are designed.

My assertion based both on the majority of texts I've read and over twenty years of experience in the industry is that the design of a language's syntax is overappreciated relative to the design of its semantics. What I mean by this is that most texts and actual efforts I've observed make the implicit assumption that the language being designed is yet another block-structured lexically-scoped imperative/object-oriented language with Algol-inspired syntax. About the only question that seems to lack a consensus is whether to be statically typed, with explicit annotations, or dynamically typed. Because those design choices are so much a foregone conclusion, it seems like a reasonable idea to design and implement the language's syntax first. And if your language is going to be essentially another C++/Java/Python/Ruby/Smalltalk, that's probably a fair assumption.

My feeling, though, is that the moment you strive to actually do anything new in the language design space, you are, in fact, better off working from the back-end forwards. To give just the most obvious example, deciding to be statically typed but to use type inference is a decision that had to be made very early on, because it has a dramatic impact both on your back-end and your syntax. To give a slightly more exotic example, deciding not to have a boolean type, but instead to have notions of "success" or "failure" a lá Icon, likewise radically affect both your back-end and your syntax.

I don't know that falcon wants to do anything quite so exotic. But I find it interesting that s/he already has the sense that s/he is floundering, just flopping around in the syntax/parsing shallows. I claim that this isn't surprising: when you look at your AST, you need to have a strong sense of what it means, and unless you already have a semantic target in mind, it's too easy to end up flapping around.

Having said all of this, let me emphasize that I wholeheartedly agree that syntax is important, that the design of a "good syntax" is an art form, and that good syntactic design is regretably rare. I am one of those Lisp programmers who eventually came to accept that the human brain seems hardwired to benefit from more syntactic sugar than Lisp encourages, and have largely settled on the ML family has having the best semantic benefits of Lisp and the best syntactic benefits of Algol and its descendants. So there is a sense in which you're preaching to the choir. But I'm afraid that I still see too many language designers rush off to write a parser before having given any thought to the semantics of their language beyond the (unarticulated!) assumptions I've already enumerated.

Excellent reasoning, it looks like we don't dissagree at all on these points!

TAPL is a very good book to understand statically typed languages, their various features, and advanced type systems. But although it has some comments about the efficiency of important algorithms (mostly typechecking) it does not cover realistic implementations.

Essentials of Programming Languages is a nice complement to TAPL, as already noted. Other very interesting book, more geared towards implementing Lisp dialects, is "Lisp in Small Pieces" by Christian Queinnec. In it are developed various interpreters and compilers for Scheme, and many features are characterized by giving a denotational semantics account of them. Even if your objective is not to implement a Lisp dialect, many lessons can be learned from this book.

...EOPL. Also a must-have. Slender but dense. Take advantage of the "EOPL" language in DrScheme and I think you'll find it very pleasant to work through.

It's very good. I am doing a types course at uni, and while programming languages had always been something that I'd been interested in, some of the more theoretical aspects seemed beyond me. :) Pierce's book made it a lot more accessible and seems very thorough (not finished it yet).

Chris

From Using and Porting the GNU Compiler Collection (GCC): RTL:

Most of the work of the compiler is done on an intermediate representation called register transfer language. In this language, the instructions to be output are described, pretty much one by one, in an algebraic form that describes what the instruction does. RTL is inspired by Lisp lists. It has both an internal form, made up of structures that point at other structures, and a textual form that is used in the machine description and in printed debugging dumps. The textual form uses nested parentheses to indicate the pointers in the internal form.

I actually read that post and the papers it mentions a few days ago. They are probably interesting but they are a little beyond right now...but I understand more of them now than I did a week or two ago. I also just ordered EOPL. Lisp syntax looks strange to me but the more I look at it better I comprehend it. It'll be disappointing if all this talk of LISP power (specifically for developing compilers) turns out to be dogmatic rants...but I'm looking forward to using EOPL as a 'practical' guide to actually implementing my ideas in code, while other books serve as theoretical preperation.

That the low-abstraction languages get converted to a format similar to the high-abstraction language's.

The irony is that for years C used to be called "ever so slightly higher than assembler".

I don't think the conversion to SSA says anything about C's claim to being only slightly higher-level than assembler — that's still true of C. The conversion to SSA is precisely because of that — it's intended to fix some of C's problems, to make it tractable for automated processing by making it more referentially transparent. It's reasonable to say that SSA is more abstract than C. You could even call it higher-level, although it would probably need some syntactic sugar to really qualify as such.

I read EoPL recently and was massively underwhelmed. Shriram Krishnamurthi's Programming Languages: Application and Interpretation seems to cover much of the same material with a similar approach in more depth and presents it better in my opinion.

As Paul Snively points out, Lisp-looking languages are used as intermediate languages and for GCC no less. However, being good at compiling and interpreting languages is not at all the same as being a good intermediate language. An intermediate language is the output of (the earlier parts of) a compiler, and ideally should make very little assumptions about the environment. Perhaps you meant implementation language, in which case the reasons are, on a case-by-case basis usually either 1) the typical reasons Lisp is not used, or 2) a compiler for a language is typically written in the language it's compiling (for general-purpose languages) as a kind of tradition and rite of passage for the compiler and language.

One of the reasons I originally started learning the innards of computer science was because of languages such as APL, K (Kdb), etc. At my first job, while very highly paid employees and consultants were spending their time tuning the heck out of oracle and sybase, I saw a presentation for vector languages which promised orders of magnitude improvement in performance. I had just gone through 4 years of Comp. Sci. school and couldn't believe that billion dollars companies, with hoards of PhDs were out-done by such languages. Of course I learned that marketing, too much abstraction and simplification and even assumptions about users' needs and priorities leaves a lot of room for technical advances.

More specifically to the current topic. I've been trying to figure out WHY APL/J/K/Q are so much faster (as is claimed). I know they deal with arrays, but how is their manipulation of arrays so much faster than C or C++? It all ends up as the same machine code. I asked the same question on the APL newsgroup but didn't get the answers I was looking for (http://tinyurl.com/58y2v)
I was going the ask the same question on this forum, I guess I'll do it here :)

By your comments about APL, vectors and the relational model, you might want to give a look at vlerq, that was just cited in another thread.

I've gone back and forth over k several times; I flip back and forth between really liking what I see and really not liking it.

Arthur Whitney's focus on character count really does a disservice to the key innovations in the k system. Seeing k made me think of a "multiple representation" programming environment and language, where I could flip k source back and forth between several different forms -- character ultra-compressed "Whitney" notation, expanded function name "McCarthy", and a graphical form. I liked Epigram's notion of sheds, where the dirty, unfinished bits can live.

k's built-in tree structure is interesting too, and plays nice (I think) with many of Epigram's notions.

Pulling back, the real strength of K appears to be the set of verbs (functions) and adverbs it provides. With a couple of characters you can get behavior that takes yards of code in other languages. A second major strength is the top to bottom assumption that _everything_ needs to work with vectors. Writing an operator? Define _exactly_ what it does in dyadic, monadic, atomic, and vector cases, and every combination thereof. This is what k does.

I think Scheme could learn a lot from k. Why doesn't the + function know what to do with properly shaped vectors and lists? (+ (list 1 2 3) 5) should "do the right thing", as should (+ (list 1 2 3)(list 4 5 6)). And the fact that Scheme makes it difficult to write functions that "do the right thing" in these cases should be something the R6 committee considers.

It turns out that in our business looping over bunch of items happens a lot. Providing a good, general, function composition mechanism is important. k goes a step further and provides very high speed, terse notation for many of the most important functions.

I'd suggest that anyone looking for a good set of primitives that should be eligible for special treatment could start with those listed in k's documentation.

I think I read somewhere that when implementing K's core, the first thing Whitney does is create macros that correspond to k's verbs and adverbs. He then writes in terms of those.

I thought the 'map' function allowed operations accross a whole list...no? Wouldn't that be the same as K's 'right thing?'

I think Scheme could learn a lot from k. Why doesn't the + function know what to do with properly shaped vectors and lists? (+ (list 1 2 3) 5) should "do the right thing", as should (+ (list 1 2 3)(list 4 5 6)).

That would be appropriate for one possible level above Scheme's RnRS core. As it is, these examples can be written as:

(map (cut + 5 <>) (list 1 2 3))   ; use srfi-26
(map + (list 1 2 3) (list 4 5 6))

(Assuming I correctly divined "the right thing").
It requires some thought about the shape of the data being operated on. That's not necessarily a bad thing, particularly in the language core where Scheme's philosophy is to provide the flexibility to support all sorts of different idioms. Someone else might come along and claim the "right thing" for (+ (list 1 2 3) 5) is (1 2 3 5).

Peter, thanks for the suggestions (and thanks for a great book!).

My original purpose was to have a language which will allow me to experiment with the relational model (build a relational DB with features I think are missing from oracle,sybase,etc.). I started looking at parsers/compilers to take care of my query language. Since then I've found an amazing world of PLT, logic, basic (fundamental) math. I'm surprised by how much research is being done in this field (I didn't even know such a field existed). It is amazing to see what all these, slightly below the radar, languages can do compared to the so called 'main stream' languages.
Ironically, I think O'Caml might let me skip having to write my own language (it is fast, has tuples/records, first class functions, is FAST!).

Last night I seriously started looking at Oz. It looks fascinating, however I have to figure out how much time I should spend working with it. Right now I need to learn scheme (because smart people think I should), O'Caml (because it's speed and expressive power looks impressive), Haskell (because 'purely' functional language will force me to learn this type of programming). Other than concurrency, are there any reasons I should add Oz to this increasingly congested list? Will it remain an academic language or is it expected to be used in industry (which will have to mean that speed will be improved). Right now I'm more concerned about how 'easy' it is to work with a language (no needless restrictions), how it implements the latest research and best practices, etc. However, if I spend time developing a prototype of this database, it would be great if I could do it in a language which will EVENTUALLY become as fast and reliable as older and more mature languages (which is why developing my own language was actually the last resort).

BTW, I agree with all the suggestions you enumerated. I was thinking about an inferred type system but during implementation my brain would have collapsed under the weight of all this information and I would have switched back to simple, explicit, static typing any way:)

Let me just say that while I disagree with Peter re: type inferencing's value in general, I agree to the extent that if all it gets you is let-polymorphism and recursion, it's probably not enough bang for the buck relative to strong dynamic typing. My points of comparison for this are O'Caml on the static side and SBCL on the dynamic side. I'm plenty pleased with the performance of both of these implementations. It's worth noting that SBCL gets there by doing type inference, too; it's just that it doesn't refuse to compile if it fails to find a nice, specific type that it can compile efficiently.

Where static type inference wins is with a much richer type system: that of GHC 6.4 with its GADTs, or languages with dependent types, linear types, etc.

If you're trying to create a database language a lá Hughes and Date's Tutorial D, well, you should follow what they write about types in whatever edition of The Third Manifesto you have. I'm waiting for their new 2005 edition to be published and have thought about then doing exactly what you're doing: attempting a rigorous implementation of a "D." I'll probably use MetaKit as the back-end engine unless JC gets to performance-tuning vlerq a lot sooner than I expect him to.

I'm not necessarily looking at their Tutorial D language, but certainly their ideas of uber-capable information manipulation system. I have already pre-ordred Date's new book "Database in Depth " from Oreilly (http://www.oreilly.com/catalog/databaseid/) and I plan on ordering TTM as soon as the next version comes out.

On the documentation page (I was looking at the pdf/ps documentation) there seem to be a large number of almost book length tutorials/refrecenes, etc. I think it will be extremely helpful if there was one 'Start Here' type manual which covered not just the basics (which the Oz Tutorial seems to do) but also includes chapters on how to make use of all this functionality. Obviously I would love a chapter on compiler construction :) If fact, I think it will be a good idea to have introductory articles, HOWTOs, etc. which intorduce the language, the environment, general capabilities as well as specfic features....but do so as self-contained 'article length' write-ups....or more likely I just need to break from googling and reading all this stuff for a few days and get back to it with a fresh mind :)

Other than concurrency, are there any reasons I should add Oz to this increasingly congested list?

There are a few reasons. One is that Oz combines the abilities of many of the others in a well-factored way. Oz gives you more choices than the others in what set of concepts you use. Seeing how all these different choices can live together harmoniously is an eye-opening experience.

This is why CTM is great. It ties everything together and provides unity. The way I was taught was everything in bits and pieces, incremental to a degree but mixed and matched. Like mixing polymorphism and inheritence when learning object orientation. Understanding what the concepts actually are and how they interact gives you more choices and flexibility.

Another reason is constraint programming. And a third reason is distributed computing.

Can't say anything about the constraint programming as I haven't done much thus far, but from my experience Oz distribution model is a lot easier to work with than something like RMI (my final year project evaluated Oz in a distributed setting).

Declarative by default is a good default for distributed systems - managing state in DS is difficult enough without managing it all over the place. Local call semantics for procedures by default is better than RPC - you use message passing for RPC-like calls. Things like that were a real bonus and made things so much simpler than before.

A Dialyzer like tool for Oz might help though! :)

Danx

p.s. QTk is also a good reason to check out Oz!

Dan,
I had even forgotten that I mentioned I was going to use Java/C# for parsing. After 15 or 20 messages on this board, I have started looking at OCaml, Oz and Scheme (I also looked at Haskell since Pugs came out...but OCaml seems to do everything haskell does, but seems faster yet similar to my existing experience in imperative languages).
I thought writing my own compiler might actually work when I saw information about Parrot and how it abstracts away many complexities yet may provide a fast enough and cross platform enough system to be used in industry....unfortunately at this time I don't know how Parrot can be used to implement classes, message passing concurency (what are continuations?), multimethods, etc. In other words, I think you are a guy who could do a few write-ups for us newcomers ;)

Ocaml does not do everything Haskell does. It's missing:
- Lazy evaluation
- Typeclasses
- Monads
- Kinds (higher-order types)

Also, Haskell libraries tend to be rather interesting, in that there's a tendency towards "everything is a combinator" DSLs. The Ocaml libraries I've seen use the language well, but they're still recognizable as libraries, and don't flirt with being languages in their own right like many Haskell libraries do. Haskell follows the Common Lisp tradition in this respect...

I'd recommend learning Ocaml first, if only because I started with Haskell and was very, very lost. Ocaml's more familiar to imperative/OO programmers, so you can learn about functional programming and type inference without completely leaving familiar ground. But I think that Haskell is definitely worth learning if you want to get into language design: it has semantic features worth learning that don't appear in any other language.

Jonathan Tang: Ocaml does not do everything Haskell does. It's missing:

This is almost correct: O'Caml is call-by-value rather than call-by-name or call-by-need, but it has a "Lazy" module and keyword, so you can be lazy on demand. :-)

Similarly, while it doesn't have monads as a language feature, you can certainly implement monads in O'Caml. One useful such monad is the O'Caml NAE Reactive I/O monad. A more comprehensive monad library can be found at http://sange.fi/~atehwa/omlib/. There's also this camlp4 syntax extension for a Haskell-style "do" construct.

OCaml can have side effects so it doesn't need monads.

:)

Check out Paul's links :)

Still wrapping my head around monads, but as far as I understand them so far, they're much more than just a way to implement state in a pure language. They seem to be more like aspects for functional programming: they let you weave extra "stuff" into the program without the code needing to know anything other than the fact that it's dealing with a monad. State is one very-specific special case of this, where the extra "stuff" is the explicit state being threaded through the computation. But equating monads and state is like equating the Internet and reading the NYTimes online. It may be a good use, but it's hardly the full potential.

Paul's links look really interesting; I'll have to play with them when I get a chance.

And I'm wondering whether anyone's thought of doing a pure monadic programming language, where monads are the primary structuring mechanism. Or does that not make any sense? It seems like monads are a full abstraction paradigm, like functions or classes or aspects, and one that's been largely ignored outside of Haskell.

Anybody working on a premonoidal category PL?

They seem to be more like aspects for functional programming: they let you weave extra "stuff" into the program without the code needing to know anything other than the fact that it's dealing with a monad.

I recently tried writing a Haskell Su Doku solver and then rewriting it using a state monad, and found that using the monad enabled me to create a sort of stateful execution environment for my Su Doku-solving code.

Monads make it possible to build all sorts of things into an environment, from IO support to continuations, which in turn means that those features can be factored out from the code that runs in that environment. This is a common thing to want to do in any language; monads (plus do notation as sugar) provide an especially elegant way of doing it.

It seems like monads are a full abstraction paradigm, like functions or classes or aspects, and one that's been largely ignored outside of Haskell.

Googling for "monads in scheme" will turn up some wizardly stuff from Oleg, along with LtU discussion of the same. For a laugh, I recently translated some monadic parser combinator code from Hutton and Meijer into Python.

In general, my answer would by YES, this is a very good idea. Naturaly, some features are less suitable for this sort of experimentation than others.

...you can write a compiler in Scheme, and will, if you work through EOPL, SICP, or as an earlier poster reminded me, Programming Languages: Application and Interpretation, which has the distinct advantage of being freely available online.

By working in Scheme, you can also benefit, if you choose, from using the excellent DrScheme environment. Note that both EOPL and PLAI have language-levels for DrScheme: EOPL's is included with the current distro, while PLAI's is available from the home page linked to above.

90 minute Scheme to C compiler. :-)

Here.

very interesting paper. Thanks.

I would suggest browsing through Programming languages bookmarks of Mr. (or Dr? I really miss his posts :-( ) Frank Atanassow, especially the "Experimental" group.

From what I understood, you want a minimalistic language, like Scheme or Pico, which probably means no type inference, and probably no static types (and especially no dependent types).

Regarding pillars - I thought the various calculi supposed to be them? For my job I prefer pi (not the vanila dialects, though), but YMMV.

PS: if you really are at loss, I would recommend to implement some well-known, simple but powerful language (I mean Scheme), and then explore the space of experimental languages to see what you like about them. You might want to implement several of them (no industry strength required) before really designing your own. But of course, nobody does it this way, the temptation is too strong :-)

what are the most basic ingredients for a language?

I'll make the obligatory recommendation of CTM.

They do a great job of breaking down the kernel functionality of various paradigms into small orthogonal sets of "commands". Even if you don't use the exact same basis for your language, they give you a good example of how to do it.

Unless you have a really good grounding in how to build up from a calculus/algebra, their approach is probably closer to where a programmer starts thinking, and will probably be easier for you to start with.

It's useful to approach this via the correspondence between types and logic. In logic you would start with 'and', 'or', and 'implication'. The corresponding PL types are tuples, discriminated union, and function. Basic features required to support these types include element selection, case, lambda expressions, and function application.

Although I'm coming from an orientation toward static types, IMO this would provide a solid foundation in any language. These can be taken as the essentials for building program structure. Integer, string, etc. would be viewed as primitive types.

There's no one way to rank the ingredients in order of how basic they are. If your goal is to bootstrap efficiently into your own language, you can pick any tolerable subset.

IMO this would provide a solid foundation in any language

As long as you are shooting for algebraic types, am I wrong?

[tuples, discriminated union, and function] As long as you are shooting for algebraic types, am i wrong?

Of course that just gets you to the stage of algebraic types. The question was, "What's basic?" Starting with those types does not limit what you shoot for.

For one approach to basic ingredients, and building up using the core itself, check out Supercombinators.

--Shae Erisson - ScannedInAvian.com

The biggest decision facing you is whether your language should be statically or latently typed. Once you've made that decision, everything else gets quite a lot easier. If you go for static typing, Types and Programming Languages, as we discussed earlier, is, IMHO, the best launching-off point, bar none. If you go for latent typing, then LISP in Small Pieces is the moral equivalent in that domain. :-)

I have a lot of sympathy for the CTM recommendation—it's head and shoulders the best CS text in the world, IMHO, and definitely follows the pattern you suggest of beginning with a very small kernel language and very judiciously adding features only as they become necessary. The only hesitation I have about it is that it implicitly commits to latent typing from the outset. Yes, there's Alice ML to explore the integration of the major Oz features into a Hindley-Milner type-inferenced regime, but until CTM in Alice ML is done, it might be more difficult than is warranted for your purposes to gain leverage from the observation.

Paul,Mark,
I was thinking of this book when I said that many books offer language features...but not how those features are really just built on top of some basic facilities. But I'll take another look...I might be confusing it with something else.

I was thinking of this book when I said that many books offer language features...but not how those features are really just built on top of some basic facilities.

I suppose it depends on what you mean by facilities.

If you want something concrete, I would suggest learning an assembly language. They are usually fairly small and in practice generate all other semantics. Looking at the assembly generated by, say, some C code can teach you a lot about the "bare metal" supporting PL constructs.

If you want something more abstract, LC is probably your best bet. It has very few primitives and building up more complex stuff from it is the basis for a lot of literature. (Not very practical though)

CTM fits nicely in the middle, which is why I recommended it. It gives you the kernel "elements" of the language that can be used to build up the rest of the language, but it is abstract enough, so that you don't have to know the gory details of implementation for those elements, yet concrete enough that someone who understands programming can see what they do.

I guess, like a lot of things, it all depends on what you want. ;-)

The only hesitation I have about it is that it implicitly commits to latent typing from the outset.

I'm not sure that I agree that this is necessarily a problem. Whether you want a static type system or not, you need to work out your basic semantics, and that will look very similar (maybe identical if you have type erasure) whether you go with static or not.

While I agree that TAPL is a good book, and invaluable if you DO want a static type system, I don't know that it will get you semantically "up and running" as quickly. The two approaches together would probably pay off best in that case.

Besides, everybody here should read both books anyway. ;-)

but until CTM in Alice ML is done

The biggest difference I've found in the languages thus far is that Oz is more firmly grounded in logic/constraint with full support for unification. Alice has some unification built in, but it is not fully transitive - I've been told this was a conscious decision on their part. So far, this hasn't cause too much grief, as most of the examples are one-way unification or can be dissected into two one-way unifications. Will have to see how it plays out in the rest of the book.

Almost finished with chapter 3, only two more sections on Pickling and Components. Alice supports these two features so I just need to learn what's there. Fortunately, I've had help any time I've gotten stuck. The Alice & Oz folks are quite helpful, and could circle me several times if that was their quest, but they have bigger fish to fry. What with kids and working in a startup venture, the translation will take a while (and definitely cuts into my ability to post front page stories on LtU).

Nine times out of ten, I find out that those asking for advice are really interested in syntax, and haven't given much thought to the semantics, by the way...