Lambda the Ultimate

Capabilities, as I understand them, are essentially keys. In the simplest model, a program presents a cap to the OS with a request to "do something", and the OS checks the cap for validity. If it's valid, (has been issued to the requestor, hasn't been revoked or expired), the OS carries out the request.

Now, these things are divisible and delegatable. If a program (like a command shell interpreter) has a cap that represents the authorities that the OS has issued to a particular user, it can create a cap that represents the user's authority over a particular file or directory or device, and pass that on to another program (like a compiler) when the user invokes a program supplying that filename, directory name, or device name (like the file to compile or the directory to create a file and write the compiled code in) as an argument. The idea is that each program should run with only the priveleges it actually needs.

Implication: programs no longer parse their own command lines, or at least not the parts of them referring to capabilities. Something to which the user's caps have been delegated has to do that, so as to provide the programs directly with the caps they need.

They are also replicable. That is, a program can communicate a cap to another program without itself giving up that cap. Thus, you can delegate the ability to run a camera or something to a remote program across the network, without giving up the ability of local programs to use that camera.

In fact, the "ambient authority" of machine code running directly on hardware is what the OS divides and replicates to provide the set of capabilities that represent the user's authority - or a particular program's authority, or etc.

The OS must know who (or what) owns a capability; when something presents a capability that was issued to something else, the request should be refused. Otherwise, the system could be breached by a program that "guessed" the binary pattern of a capability issued to something else. This means that replicating, delegating, or subdividing a capability can only be done via calls to the OS, so it can keep a current picture of who owns what.

Okay, so far so good. That's the theory as I understand it. But the theory doesn't in general match up with the security claims made for the technology, or at least those claims imply the existence of additional infrastructure, so I feel like I must be missing something.

In the first place, presenting a capability to the OS must also give the OS identity information about what's presenting the cap, so that it can check its ownership and make sure that cap actually belongs to the presenter. But every time a program starts, it has a new process ID. If the OS keeps track of the file from which the program code is loaded and assigns the compiled-in caps to the resulting process ID, then it can be defeated by putting different code into the file in order to hijack the caps.

So this seems to imply a requirement I've never seen discussed; that files with compiled-in capabilities have to be restricted such that no user whose own capabilities are not a superset of those compiled into the file can write it. IOW, if a program has the capability to write /etc/passwd then no user who does not have a capability to write /etc/passwd can be allowed to write to the program file.

A user must have all the capabilities required by any software he or she is installing or modifying. In principle each user priveleged in a certain domain can install software that has his or her priveleges in that domain. But it could easily happen that even where all the capabilities exist, no particular user would have the capabilities to install something.

So in practice, it seems like you'd always need an omnipriveleged root account to do some kinds of software installation and maintenance. Therefore it seems strange to me that the omnipriveleged root account is claimed not to be needed.

Am I missing something?

Haskell spotted in a mobile apps startup?!

And I saw what is probably a snippet of Clojure on a whiteboard in Techshop.

On the other hand, the other day I talked to two practicing software engineers, both intelligent and successful and coming from different backgrounds. Neither of them has ever heard of Clojure or Scala (or, indeed, Ocaml). There's more work to be done!

Our application use a lisp like language as extension language. We'd like to add a module/package/namespace system (chose the name you want, if the choice of name implies difference in characteristics for you, the choice hasn't probably be made yet).

I'd like not to repeat known mistakes, so I'm looking for a critical review of the design space with trade-off to be made, tempting choices that have be proven bad choices, and so on. Obviously, I'm also taker for recommendations on related specific points for which you'd have an experience you want to share.

I'm having zero luck with my Google and CiteSeerX searches.

I'm not looking for some particular language advocate's uninformed criticisms. Instead I'm looking for some at least potentially well grounded critiques based on, just for instance: implementation state of the art, performance or memory footprint, issues regarding separate compilation and link-times and so on for large, multi-developer programs, problem domain applicability, OS integration mismatch, feature/library immaturity of language designs to date, library interoperability difficulties, pedagogical issues (especially training of working programmers), debugging or other programming pragmatics issues, language implementation difficulty related issues, critique of one or more particular features commonly found in (some) functional languages and so forth, awkwardness of implementing/handling certain data structures or very common programming idioms/sub-problems, blah blah blah.

Just some ideas. I can't find much of anything so far.

Quality experience reports along the same lines would also be very welcome, perhaps even more interesting than critiques on more general principles and judgments.

Mucho thanks!

Scott

Last week, the SEC put out a 667 page proposal regarding disclosures for asset backed securities. What I found exciting was this:

We are proposing to require that most ABS issuers file a computer program that gives effect to the flow of funds, or “waterfall,” provisions of the transaction. We are proposing that the computer program be filed on EDGAR in the form of downloadable source code in Python. … (page 205)

http://jrvarma.wordpress.com/2010/04/16/the-sec-and-the-python/

I don't have more time to comment on this, so the post is a bit scrappy. Sorry!

Hi all!

Please guide me to actual hot topics in type theorem, what is researched heavily nowadays? Which are the good online and offline sources of publications in this field?
Thanks,

the ANSWER project:

ANSWER will produce a notation system for describing the creation of multimedia content, thus offering a bridge between digital media production and animation for game design.

with a demo in flash; watching it makes me think it would be nice if the visual language had a textual representation and one could switch back and forth between them.

Laurence Tratt: How can C Programs be so Reliable?

Henry Spencer said, "Those who don't understand UNIX are doomed to reinvent it, poorly." And that's probably why so many of the programs written in C are more reliable than our prejudices might suggest - the UNIX culture, the oldest and wisest in mainstream computing, has found ways of turning some of C's limitations and flaws into advantages.

A nice post about one man's experience with C.

I'm going to be a college senior next year and I want to do an honors thesis related to programming languages. I've been scratching my head for topics but though I have an interest in PL, I don't know enough about the field to be able to tell what the outstanding problems are that are the right size for an undergrad.

One of the ideas I've had is to design and implement a programming language, but I'm not sure if this is a good use of my time. It would probably be only a cousin of SmallTalk/JavaScript and I don't think I'd have the time (1 year, part time) to build substantial libraries or features that would set it apart from the crop.

I also think that VMs are an increasingly important field (especially with the rise of multicore) but I know little about this field. My programming languages was theoretical and interpreter based and my own readings have been along the same lines. I have some experience with program analysis (I worked on blended analysis for Java last summer) again, I don't know enough about the field to know what would be a bite-sized problem to tackle.

I do intend to ask my professors for suggestions and I'm thinking about some non-PL topics as well, but any input you guys have would be appreciated as well. I realize that this isn't strictly a PL-oriented question, so feel free to point me to somewhere else to ask my questions.

Thanks for reading through.

Basu

This is a classic paper, currently up on the scheme repository. It's about implementation strategies for dynamically typed languages, and I wanted to recommend it to LtU members because I found it very helpful.

Dynamic typing is easy to implement, but hard to implement well. Usually you wind up writing some ASM or non-portable C code that goes down to details of the OS that, technically, you should not rely on, like how many of the lowest bits of pointers returned from malloc() are always zero. If you write something portable, the result tends to be both larger and slower than you'd like, unless you learn a lot of tricks for avoiding typechecks in the first place.

So there's a complicated design space with a lot of tradeoffs, and the costs and benefits of each are not necessarily obvious. It would be nice to read a survey of implementation techniques with discussion of the tradeoffs rather than experiment and slowly work out all this stuff on your own, right? Well, here is that survey:

Representing Type Information in Dynamically Typed Languages

It's getting a bit old though; does anybody know where the equivalent paper could be found for modern (multi-core, multi-CPU, pipelining) architectures?