Lambda the Ultimate

I have a great interest in learning more about Domain Specific Languages (DSL) and how to design and implement them. So I though there is no better place to ask for this than here at LtU.

I am primarily interested in building modular language interpreters that will be embedded in other languages such as Java. So I would like to understand the basic semantic building blocks of programmming languages and then different strategies and techniques for implementing them. I am more interested on language semantics and implementation, and less on language syntax.

So if you had to recommend to me a set of books, papers, etc that could walk me through all this from beginning to end, what would that be?

Any info/references would be great.

I am not a number: I am a free variable

Conor McBride, James McKinna

In this paper, we show how to manipulate syntax with binding using a mixed representation of names for free variables (with respect to the task in hand) and de Bruijn indices for bound variables. By doing so, we retain the advantages of both representations: naming supports easy, arithmetic-­free manipulation of terms; de Bruijn indices eliminate the need for alpha-­conversion. Further, we have ensure that not only the user but also the implementation need never deal with de Bruijn indices, except within key basic operations. Moreover, we give a representation for names which readily supports a power structure naturally reflecting the structure of the implementation. Name choice is safe and straightforward. Our technology combines easily with an approach to syntax manipulation inspired by Huet's `zippers'. Without the technology in this paper, we could not have implemented Epigram. Our example---constructing inductive elimination opera­ tors for datatype families---is but one of many where it proves invaluable.

A pretty technical paper, but fun to read.

OT: Is it just me, or the page 7 contains an easter egg? Or rather a pun...

The Sixth IBM Programming Languages Day will be held at the IBM Thomas J. Watson Research Center on Friday, April 22, 2005.

Announced on comp.lang.functional

Atoms are true elements that can not be divided any further into other elements. There exist a finite set of atoms relatively small as compared to a set of all possible physical substances that can be constructed from these atoms.
Can we define a finite set of programming atoms that all existing programming languages can be built from?
Is it possible to build a Periodic Table of Programming Elements similar to the one discovered by Dmitri Mendeleev for physical world?
Will such Periodic Table of Programming Elements allow to envision properties of new programming languages not existing yet?
Chomsky and other linguists have already discovered atoms of natural language. (See for example "The Atoms Of Language, The Mind's Hidden Rules Of Grammar" by Mark C. Baker. Excellent work!)
Using these linguistic atoms any of several thousand human languages existing today or used in the past can be constructed. To say more new natural languages can be fully built from these linguistic atoms.
Atoms of natural language turned to be parameters used in recipes for building all other language constructs.
The following recipe reflects one of these parameters/atoms:

"Heads precede phrases in forming larger phrases in English-type languages".

"Heads follow phrases in forming larger phrases in Japanese-type languages".

Parameter used in these recipes is called "Head Directionality Parameter". This parameter or natural language (atom) defines how more complex phrases are built from simple ones by adding new "heads" to the phrase.

For example, for both language types we can build a complex noun phrase:
"all existing programming languages"

from a simple phrase:
"languages".

Steps to build complex noun phrase in English-type languages:

1) languages
2) programming languages
3) existing programming languages
4) all existing programming languages

Steps to build complex noun phrase in Japanese-type languages:

1) languages
2) languages programming
3) languages programming existing
4) languages programming existing all

There are other atoms / recipes that can be used for natural languages existing today, used in the past or just envisioned and yet to be implemented in future.

But what about programming languages? What are their atoms? Being just another breed of languages programming ones may also have parameters in a role of atoms as their natural brothers and sisters do.
So what finite set of parameters can be used to construct from the same building blocks C++, J, Java, Lisp, ML, Oz, Erlang, Basic, Fortran and Perl ? And what are the building blocks?

For starters I propose these building blocks that any programming language can be built from:
Object, Variable, Program Scope, Closure, Lambda / Function, Template

As for Parameters (atoms) I would start with Assignment, Binding, ... what else?

I realize this may be a dumb question... having had some Abstract/Modern Algebra classes, I understand what an Algebra is, but I have never really understood what defines a "Calculus". What's the common thread between Lambda Calculus, Pi-Calculus, and traditional "Calculus"(and all the other calculi...) that merits them being called a calculus?

I realize this may be an obvious thing, but my tendency is to assume that there is some formal definition of Calculus out there which is being used which I am just unaware of. Again, if I'm just being dumb, someone email me and put me out of my misery :)

...so do not all the PLs based on it, do they? Which systems do have them? Read on:

The essence of principal typings

This paper presents a new general definition of principal typings which does not depend on the details of any particular type system. This paper shows that the new general definition correctly generalizes previous system-dependent definitions. This paper explains why the new definition is the right one. Furthermore, the new definition is used to prove that certain polymorphic type systems using for all-quantifiers, namely System F and the Hindley/Milner system, do not have principal typings.

Am I just overly enthusiastic of finding a new source of interesting reading, or are these 12 pages really a worth reading for anybody designing a new PL?

Following the CTM wiki and GCC wiki announcements, and the expression of interest in all kinds of new PL wikis, a pointer to the wikicities service may be in order: it's essentially an extension of the wikipedia project which is meant to support topic-oriented communities. I guess the Wikicity creation policy is the main thing to bear in mind when thinking whether a wikicity is the best way to launch your ultimate PL enlightenment portal.

Is anyone doing functional programming research on transparent (aka orthogonal) persistence?

I've been reading a lot about the subject (http://c2.com/cgi/wiki?TransparentPersistence) and I've found that promising projects like Eros, Grasshopper, Texas, and others have either died or removed transparent persistence from their projects.

I'm a contributor to an open-source transparent persistent OS (www.torsion.org) that's in the baby stages; I am interested in transparent persistence because of its potential to remove non-pure I/O from functional platforms.

Geoff

There are plenty of academic papers about Haskell, and plenty of informative pages on the Haskell Wiki. But there's not much between the two extremes. The Monad.Reader aims to fit in there; more formal than a Wiki page, but less formal than a journal article.

Want to write about a tool or application that deserves more attention? Have a cunning hack that makes coding more fun? Got that visionary idea people should know about? Write an article for The Monad.Reader!

Contact Shae Erisson ( shae@ScannedInAvian.com ) to become an author, or talk to shapr on the #haskell irc channel on irc.freenode.net.

Check the current roster - http://www.haskell.org/hawiki/TheMonadReader

Publishing Format:

• Input is LaTeX (or just plaintext and images).
• Output is Web and PDF/PS.
• Release once a month.
• Each article in a darcs repo for easy collaboration between author and editor.

License:

• BSD-like, feel free to read it, teach it, hack it, copy it, improve it.

The Monad.Reader: sequencing your input since 2005

I've begun to get interested in a language-based approach to network protocol development. There are some nice ones like Prolac and older ones like Estelle.

I'm systematically boiling down an RFC to an implementation, assuming such a thing is possible, and am looking for all approaches. I'm less interested in formal verification techniques that don't result in a usable piece of software, but all pointers are appreciated. I'd like to hear your experience with such techniques too. I'm looking at whatever google and citeseer spit out for "protocol languages" and "protocol compilers".