Lambda the Ultimate

There was an insightful discussion recently on the capabilities mailing list about confused deputies, and how various language constructs can inadvertently introduce confused deputies. For instance, Alan Karp devised a confused deputy innocently introduced by Java's package scoping. I then reproduced this confused deputy using OCaml's modules.

In any system with encapsulation of some sort, there is an inherent disconnect between a caller's permissions to an object, and the callee's permission to that same object. Whenever the callee has greater authority over an object it's given than a caller, and this authority is granted implicitly (by the type system, for instance), a Confused Deputy can arise. This authority augmentation is called "rights amplification" in the capability security literature.

For example, the abstract OCaml type Confused.O.t is automatically amplified to an out_channel upon calling a function in module Confused.O. This usage is safe however. The only problems arise with binary functions, where the second parameter is also implicitly amplified. One solution proposed on the list was to forbid such implicit rights amplification for all parameters except the first, thus forcing all amplifications to be explicit (cap-talk is generally object-centric, thus the emphasis on the first parameter only).

I wasn't in favour of placing this burden on all binary functions, so I proposed instead to forbid "package-scoped" functions. By this, I mean that only publicly accessible functions are visible even for modules within the same "package" (or scope/nesting/etc.). The OCaml vulnerability is only introduced because module Confused.B can access the internal Confused.O.write function, which is not publicly accessible outside of the Confused "namespace".

If this lax scoping were forbidden, the compiler writer would have to either

1. expose the Confused.O.write function publicly, in which case its obvious that writing to the billing file is possible outside of the compiler's module,
2. split the functionality for writing the log and the billing file into separate modules (the best solution),
3. parameterize Confused.B with a closure to write into a Confused.O instance, effectively making it a separately wielded capability.

In all cases, the authority being wielded is more explicit, and thus accidental vulnerabilities are minimized. My proposal may complicate abstractions provided as a set of co-operating modules however, so I have three questions:

1. How common is it to have two co-operating modules use each other's private functions?
2. Has there been any research on this or similar topics, or does this problem resemble any others that have been studied?
3. Can anyone think of any other possible solutions to this problem, preferably with a minimal burden on the user?

On a final note, there was also some discussion about creating confused deputies just using shared mutable state, so there is yet more evidence of the safety of purely functional programming.

Can someone confirm, refute, comment on, or point to the literature on my (somewhat inchoate) intuition that the access-control rules of the Bell-LaPadula model (specifically that a subject cannot read from objects of higher privilege, the "simple security property", and that a subject cannot write to objects of lower privilege, the "*-property") are just special cases of the safety of covariant results and contravariant arguments respectively?

Hi,

I am not sure I am entirely happy with the usual structural recursion on sets approaches. They all look like a bit of cheating, i.e. using lists under covers, broadly speaking.

I mean SRI/SRU/powerset/etc tricks (http://citeseer.ist.psu.edu/722866.html).

E.g. in the SRI method (collection insertion representation), we can do matching using the insertion operator that 'disassembles' a non-empty set thereby maing it amenable to something like foldr.

On the other hand, the 'choose' operator is criticised (elsewhere) as 'non-deterministic'. I am aware of various laws and such that make SRI 'work', I just have a feeling that the insertion operator is a kind of deus ex machina as much as 'choose' is !

Please comment.

Thanks.

In the OO languages I'm most familiar with, there's always been the ability to set a variable to null or nil which of course can lead to all sorts of fun problems. What I'm wondering is if there's an actual need for null/nil or not? Anyone know any research about this? I have a sense that null is the kind of thing that'd end up being invented by programmers if it wasn't already in the language to begin with which makes me wonder if it has been shown to be essential somehow in the same way that number systems seem to need zero.

(I suspect I may be way out of my depth in even asking this question... but what the heck :))

I was reading the Wikipedia introduction to Dataflow, and noticed Functional reactive programming was listed as a 'See Also' term. So it seems that Dataflow programming and Functional reactive programming are somewhat related.

Then, while I was working my way through SICP, I came across the section dealing with Constraints; I noticed that these constraint systems are quite similar to Dataflow and FRP systems.

It seems all these systems deal with ways to describe node relations that have values which change continuously based on their inputs.

It seems to me then, that these three fields are dealing with a lot of overlap. Am I correct in this thinking, or are these three fields really a subset into a larger more comprehensive topic which I have presently overlooked?

The topic of exceptions has come up plenty of times on LtU, with concomitant good food for thought discussions. But I'm not sure I've yet to see a real break down of the issue into basic components from which one could consider designs for languages when it comes to not/doing error handling. Does anybody know of some theory or math or something more solid that is an eye on error handling? Unfortunately, even with that, it sounds like good design for error handling also has to take into consideration subjective usability. And, there is a lot of important nuance in how the 'basic components' interact - yay combinatorics.

Random examples of what I mean / am trying to find / understand: Error codes vs. exceptions (dealing with clarity of non-error code flow). Java differentiates between Errors and Exceptions (dealing with the fact that some exceptions are more exceptional than others). C++ advertises RAII (dealing with the fact that you want a sane way of creating-destroying things in light of errors). Erlang eschews threads (dealing with the fact that threads can make exception handling way more complicated). Option types are useful (dealing with the fact that some errors aren't exceptional). D supports scope-exit (dealing with clarity of error code flow).

Is there something which helps us get at all these issues more rigorously and sanely?

Interesting blog post by Chris Okasaki on how indentation-based syntax seemed easier for novice programmers to learn. Reddit also has some discussion of his post. Novice programming has been touched on a few times on LTU, as have usability studies for some languages.

I think Chris raises some good points which apply to experienced developers just as much as novices. In keeping with the "programs are written once, but read many times" principle, I think it's probably good to enforce indentation in some way. How that's done may be open to interpretation however. I'm interested in exploring the possibilities of indentation-based syntax. What other languages use indentation-based syntax and how does the syntax differ from Python?

In C/C++ union types are useful in coding dynamic type systems. Does anyone know if this is possible in Java? I don't see any "union" types in my Java book. Perhaps there is a "work around"? Can a cell in an array be a union?

Edit: Is reflection necessary to discover type information in a dynamic context?

Hi all,

The article "Don't become a scientist" (http://wuphys.wustl.edu/~katz/scientist.html) started a long and interesting discussion on News.YCombinator.com/Hacker News: http://news.ycombinator.com/item?id=122106

Everybody there seems to agree with the general terms with the article... however, considering that the majority of the people there are startup people and not people who works at the academy, such vision on the subject could be very biased. So I wanted to ask what your opinion on the article is, considering that the target on this site is very different than the one at NYC.

Do you agree with it, and is the academy so severely hurt as shown in the article, or is your research experience actually different from it?

Sorry for my English, I'm not a native English speaker...

Best regards,

Hernan

I am reading the paper.But I am lost a bit,by this piece-
"sum = reduce add 0".How author arrived to this statement? What it means? And later,
"(reduce f x) nil = x
(reduce f x) (cons a l) = f a ((reduce f x) l)
Here we have written brackets around (reduce f x) to make it clear that it replaces sum." Again,I am not understanding whats happening.
"A function of 3 arguments such as reduce, applied to
only 2 is taken to be a function of the one remaining argument" How reduce is function of 3 arguments?