Lambda the Ultimate

Processes are simply better.

i would hazard that as with many design issues, the choice is all about trade-offs. i fully believe that sometimes the language should take a stand on which particular choice to make + yet also that sometimes the language should not. is there really consensus on the Right Abstraction for concurrency? (don't get me wrong, at the very least i think shared mutable state with locking a la mutexen is the worst of all the current choices, so we can at least sorta say which ones should /not/ be considered as the Right Abstraction :-)

Do you know of a language that implements versioning well?

By versioning, do you mean module/library versioning or do you mean something else?

S.

If we can bundle up exceptions with some other "dynamic" features such as "unwind-protect" (syntactically combined with exception handling in some languages), some kind of more specific and elegant resource allocation/guaranteed cleanup language facility, lexically scoped dynamic control flow and maybe fluid variables (in a limited, type safe manner), I may well agree we'd get a big bang-for-the-buck for designing and implementing a set of features in kind of the same "dynamic" semantic family. Overlapping implementation techniques doesn't hurt either.

In case it's not clear, as for "lexically scoped dynamic control flow" I'm thinking of something akin to CL's block special form (but manifestly typed, of course). As in:

foo = block back-here
        let dflt-thunk = fn k:key-type = from back-here return 0 in
          dict-get-dflt(my-int-dict, key, dflt-thunk);

Contrived, but the dictionary implementation applies a function to the key if that key is not found in the dictionary. In our case, our thunk ignores the key argument and dynamically returns 0 "directly" to the "block back-here..." clause. Some kind of typed call/ec (dynamic extent continuation) features would be equivalent, as far as I can tell.

As for resource cleanup, I'm thinking of a language construct that cooperates with user defined data types that fulfill some set of structural and/or procedural interface requirements (like "for x in ..." and user definable "Iterator" types in some languages). Here's just a tiny whack at the idea with a simple fluid bind feature illustrated as well:

  fluid *sin* = os/get-stdin _; -- defined as fluid
  ...
  -- guarantees to close ifil on stack unwind via some standard
  --  procedural (maybe method if OO) interface on cleanup-able
  --  resources.
  cleanup ifil = open-file(path, OIn, ODfltFlags) after
    let *sin* = ifil in -- fluidly/dynamically bind *sin* (stdin)
      do-stuff _;

If I understand you rigjt, delimited continuations plus dynamic binding can implement the behaviors you outline directly, correctly, and efficiently.

Of course with reentrant continuations, unwind-protect is a bit thornier. Flatt et al's ICFP '07 paper goes into all the details.

And yes, delimited continuations are now on my "to learn" list. Thanks much!

Not a LtU search?!

...to mashup

FWIW I wrote a bit about my learning process here: http://wingolog.org/archives/2010/02/14/sidelong-glimpses.

I listed some papers that helped me there.

I wouldn't have mentioned JSON if I thought people would assume that Web applications were of any particular interest. I was just enumerating boring but commonplace text and data formats. I could just as well have said that there was already an x-platform GUI library and basic image file read/writing for most common formats.

Sorry for any misunderstanding.

I'm presuming a fully compile-to-binary implementation, and the ability to both generate and dynamically link .so or Windows .dll libraries is reasonably "par for the course" for a compiled language (and from within the FFI as well, supporting C and Pascal calling conventions, along with the all-too-many variations thereof).

And I liked it! Some interesting ideas. I might have missed a few features/details, such as how different exceptions might be discriminated and the right handler function abstraction applied, but a very elegant and minimalist design! - Scott

Ah great, motivation to get the compiler finished now, finally!

As for your question, you match against the type constructor of what is thrown, so a typical handler would look like

try some_computation_throwing_an_int_or_a_text
catch
  [ n:int   -> print "integer " + (txt n) +" was thrown!"
  | t:text  -> print "text \"" + t +"\" was thrown!"
  | v       -> throw v ]

You may want to consider an alternate exception-handling form which is more well-behaved. Your document seems like a pretty straightforward intro, which is good. No mention of whether your compiler supports type inference (I suspect not), or even if the language is intended to GC'd (I suspect it is).

Your type constructors also seem a little odd, as it's not clear how you specify a type instance, ie. sum:int list -> int. Given some of the examples, it looks like it would be "list int", but I personally think the symmetry between the type and its declaration is nice, ie. "type 'a list" -> "int list" or "type list 'a" -> "list int" , but not as I think you have it, "type list = \a => [ nil | ... ]" -> "list int". I suppose you're trying to expose some symmetry between lambda abstraction "\x -> x" and type abstraction "\a -> a", but not sure if that's helpful here.

Finally, the # symbol in the "interface" construct is not explained. The section itself is clear enough, but # just doesn't jive with any other syntax explained in the doc, so I was curious.

I do the normal HM type interference with type constructor classes. I made no distinction in the checker between type schemes and simple types except for a syntactic one, during parsing, at the moment.

You are right that my types may seem a bit less readable to people who are accustomed that type arguments occur on the lhs of an assignment symbol. But, yes, I aimed at orthogonality, so that, if a name can be an abstraction of a value/value-expression, then a name may also be an abstraction of a type/type-expression. Hence all names are kept simple, and the whole type body occurs at the rhs of the binding assignment.

Was there a typo? A list definition should be recursive and be written as

type list = \t => [ nil | const t (list t)]

A list of integers is written as (list int), and given its definition, it's therefor also structurally equivalent to (\t => [nil | cons t (list t)]) int = [nil, cons int | list int], I use a nominal typing scheme, but of course, that fact is needed during type inference.

The # is the actual interface specification, it is an explicit keyword, types and instances are kind checked, and it makes explicit that the interface Num has kind *->#, i.e., it is something which takes a type, and returns an interface. It also states the formal type to unify against for instances. There is some provisional support for more complex type instances, i.e., you can unify against (f x y), but I don't use that at the moment since I wanted the compiler bootstrapped first.

Some of the decisions may seem a bit odd, but also have to do with keeping the language simple, but also the type checker trivial, i.e, some decisions are also partly implementation driven.

I'll add it to my list of changes [to the document], though. Thanks.

[I looked at the paper you referenced. Thanks again, but sorry, no dice. Anything simple regarding compilers, like handling exceptions, should fit into one a5, or be discarded, IMHO. I use shift/reset, that's good enough. If I can't grok it under 12 seconds, I don't read it anymore.]

[I looked at the paper you referenced. Thanks again, but sorry, no dice. Anything simple regarding compilers, like handling exceptions, should fit into one a5, or be discarded, IMHO. I use shift/reset, that's good enough. If I can't grok it under 12 seconds, I don't read it anymore.]

Here it is in two lines from page 3:

try x ← f(x) in g(x) unless { e ← ye } = g(x)
try x ← raisee in g(x) unless  { e ← ye } = ye
where e ∈ Exceptions

So try is a binding form like let scoped to the expression g(x). This is a generalization of the exception form discussed in Benton and Kennedy's "Exceptional syntax" paper. The rest of the paper is about an algebraic model for effects and effect handling, so it's probably not relevant given you're mandating call-by-value.

Re:shift/reset, that's interesting! I didn't see that mentioned in the paper. Or perhaps it's not accessible to user code?

:)

No, it isn't accessible. I noticed that the catch/try and throw combination are equivalent to a syntactic construct, and deduced some combinators to compile to which make use of runtime features (i.e. they have access to the control pointer). Rc 'saves/memoizes' the control pointer, Sc restores it.

It turned out to be equivalent to shift/reset, which in a LC with those features are of course also syntactic notions.

So, under water you find shift/reset in the runtime, but there's no support in the language itself.

[Btw. Thanks, I noticed I remembered a rule wrong and have been confusing its with it's.]

Minus a generally applicable "introspection" feature, this kind pattern matching over types frankly bothers me.

I love SML, but it's "special case subtyping" feature for exceptions, to me, is simply an outright flaw in the language. Why only exceptions?

OTOH, I'm not so comfortable with the idea of general pattern matching over types either; colloquially, I view this as a sort of "Stupid Scala Trick" to use a Letterman phrase :-)

Has anyone truly shone a very bright light on this issue - exception typing and subtyping, exception handling and general pattern matching over types vs. exception type inspection in dynamic handler discrimination?

S.

I'm somewhat mystified over what you are talking about. Pattern matching is not introspection or discrimination on types, it's case analysis over variant labels/tags - which may look similar but is something quite different. Likewise, ML's exception type does not have anything to do with subtyping, it is merely an extensible sum type (although there have been proposals to generalise it with subtyping). It is admittedly a flaw in MLs that there is only one such type - which happens to be called exn for historic reasons. But that does not really affect either theory or practice.

SML, OML, OCaml. Now I am confused.

It is admittedly a flaw in MLs that there is only one such type - which happens to be called exn for historic reasons.

This is my problem with SML's mechanism - it's a special case. I don't think an aversion to special cases is so completely out of line :-)

Also, in a response to a comment below, discriminating over constructors for one type is not the same as discriminating over types. In other words, these are NOT the same thing at all:

-- Normal discrimination over constructors
len :: List a -> Int
len Nil = 0
len _::xs = 1 + len xs 

-- Totally different animal - unless we have untagged "true union"
-- types we need some kind of "Any" type.
odd-fun :: Any -> Unit
odd-fun v = 
  match v
   | i:Int -> puti i
   | c:Char -> putc c
   | s:Str -> puts v
   | b:Dbl -> putd d
   | a -> puts (tostr a);

Any kind of type "introspection" or "discrimination" feature 1) may well encourage bad software design to start with in the wrong hands but also 2) burdens the runtime system and compiler design with constraints on the representation of values (more so on scalar representation, I'll hazard guess).

I'll freely admit that of the dynamic control flow mechanisms, I'm not sure at all how to design an exception handling language feature that is both usable in practice and completely "clean" with regard to the language design -- Scott

This is my problem with SML's mechanism - it's a special case. I don't think an aversion to special cases is so completely out of line :-)

I agree, which is why we generalized them in Alice ML. ;-) But I don't think that makes too much of a difference in terms of "cleanness".

Any kind of type "introspection" or "discrimination" feature 1) may well encourage bad software design to start with in the wrong hands but also 2) burdens the runtime system and compiler design with constraints on the representation of values (more so on scalar representation, I'll hazard guess).

I agree with (1), but you may be somewhat mistaken about (2). What you need to do is to pass runtime type information, but that does not need to be (and should not be) tied to values. Instead, it's tied to type variables. That still incurs a cost, but it is much smaller and easier to optimize.

Conditionals based on an unbounded set of automatically generated type-like labels is an idea approximately as old as dirt. Why blame it on Scala?

I have a language with values, types and interfaces. I am going towards a language (the only feature I didn't implement, yet) where you can build lists of values with different types, but the same interface - like in Java. Being able to coerce a value back to its type seems natural to me, maybe I programmed to much in Java??

For the moment, matching against a the type of a value is just an extension of pattern matching in general - it's handy in the case of exceptions, but you can do it anywhere you can write a lambda abstraction. Thus, you can build functions on values of type 'list t,' i.e., the concrete type is not known, but you can, in the body of the function, actually see whether you're processing a list of integers or a list of strings.

The list-of-anything, instead of list-of-anything-of-the-same-type, is the last extension I need, but I got around not having it so far for the moment. I just didn't decide on how to handle that yet. I might go existential types, but that doesn't handle the case that I want to reuse all the normal lists definitions.

If anyone has great ideas, please let me know. (Uh, better than union types, existential types, or record subtyping, and-so, because I know that.)

[Hmm, I might have misunderstood your remark. If I read it correctly, you _only_ can do that in SML with exceptions, so, yes, I agree, that might be generalized. In general, as you also remarked, it has its uses, as I showed by an example of processing lists of different types differently.]

[I have some thoughts on it. I.e. I need a quantifier ??, such that a type '??t => list t' is somewhat akin to existential quantification, but states that the list consists of values of different types. I might avoid union typing altogether with a function which just 'erases' the type before it's inserted, not sure.]

[Forget it, problem solved.]

This sounds like a good idea. Syntax might not be too fashionable an issue, but I've always thought it has import (I'm an aging Lisper).

Do you have any pointers to languages whose syntax has the desirable features that you describe? I've always admired Smalltalk's syntax and Forth's simplicity and syntax extension capabilities.

But I'd love to learn about other syntaxes and the nuances that give them the particular benefits you describe. Thanks!

Study REBOL and OMeta for parseable expression grammars. Unfortunately, no books, only manuals, blog posts, mailing lists, and research papers. REBOL does containt tutorials. OMeta does not. REBOL is also more general than OMeta in that its PEG-equivalent functionality (which is referred to as the "parse dialect") is only one if its "dialects" for domain-specific languages.

Study Maude for term rewriting. The book All About Maude is a great place to start, and is a very friendly introduction to the language.

For environments, see MetaCase's MetaEdit+, Xtext, Stratego/XT, JetBrains' MetaProgrammingSystem and Oslo (now called SQL Server Modeling).

Another way to get a feel of a PEG binding is LPeg:

http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html

Although Lua sounds a bit ... conventional in this context, it certainly is a case study on how to fit a modern dynamic language in less than 200K

Yes, please do co-routines. But what I really want is lightweight processes built into each language. (I've written about this some, but not lately.) Constructing Unix-like pipes in a single native OS process is one of the big draws here.

If a cooperatively scheduled lightweight process is a fiber -- ie green thread -- you can represent one as a continuation plus identity. (If you have a slot in which a fiber's continuation can be stored, that slot can be the identity of the fiber.) If you can swap continuations in a fiber, you get co-routines directly in a lightweight process.

Your continuation representation needs to include a value or values returned if you're calling upward when the fiber is pre-empted (say upon return to trampoline).

Unfortunately a FFI for this is hairy in C when you want a stackless model

i'm not totally understanding, but i wonder if others have thoughts on that already.

In pursuit precision and clarity I get verbose, which very few folks like. So I'll only try to expand the ffi (foreign function interface) part. I can add more if you like.

If your C runtime isn't already stackless and/or lacks good coroutine support, but your language depends on constrained use of stack and low CPU use before yielding, then style of C code you can write in a foreign function reached by ffi is so constrained it might be hard to do something useful. (It would be hard to write more than a leaf node that didn't call anything else.)

If you write your language in C, you might follow a very tight and unnatural coding style to achieve your stackless regime and timing requirements. You might need to impose that same style in code reached by ffi, to maintain your invariants. Following the rules would be hairy to a developer adding code via ffi. You'd have trouble using any library already written in C -- it would break the rules.

The Erlang page you cited looked interesting. I expect they have similar issues.

What you want is a virtual processor and a virtual processor context.

out of curiosity, are there (i seem to think there are but can't find references) ways to implement static assurances of isolation so that you don't have to pay the runtime overhead?

(Sorry I didn't nest my last post correctly.) You could follow statically checkable rules to assure isolution, but those rules might rule out a lot of expressiveness. Without rules restricting what you can express, I'd guess the problem is isomorphic to the halting problem.

Even if they worked, static checks would not help me since I want to write code clearly violating isolation (just like threads using each other's state in one native process) because parts of the same continuation call tree are shared and updated. I want lightweight processes to act like cheap threads with lockless synchronization to get parallel and async execution.

seems like (i don't actually know what i'm talking about) some form of effect typing could be used to dial in things the way one wants at compile time? could one see what is/not isolated and "fix" only what needs to be fixed? of course that gets into all the coverity style usability issues if it is even remotely possible.

I was actually referring to Ian Piumarta's paper describing his Virtual Processing Unit (VPU):

Ian Piumarta. The virtual processor: fast, architecture-neutral dynamic code generation. In Proceedings of the 3rd USENIX Virtual Machine Research and Technology Symposium (VM'04), pp. 97-110, San Jose, CA, USA, 2004.

Ian was one of the pioneering researchers in recursive virtual machines and the Virtual Virtual Machine project at INRIA. Currently, he worths for Alan Kay as a co-PI.

Also, I remember first hearing of the argument for this on LtU user Sandro Magi's blog: What's Wrong with .NET. Of course, Ian gives a way better technical argument than Sandro, but Sandro is covering specifically .NET.