Wednesday, June 29, 2005
Monday, June 27, 2005
Tail-applicative continuations
In a recent discussion on the plt-scheme mailing list, I learned that the application of a captured continuation in tail position--even an escape continuation--is not a tail call. This means, for example, that if you use let/ec to encode constructs from C-like languages such as return, break, and continue, that applications of these continuations will not be tail calls.
Ryan and I came up with a trampoline-like implementation of what I'm calling let-tail-continuation (or let/tc for short), which captures the current continuation, binds it to a local variable, and implements applications of that variable as tail calls. Here's a simplified version:
We can observe that applications of the capture continuation are in tail position using the trick I described the other day:
Update: Thank you Felix for the correction--that's an important point. The salient issue is not whether the application of a continuation itself is in tail position but whether its subexpression is. The let/tc form allows applications of the continuation to evaluate their subexpression in tail position; another way to put this is that continuation applications are tail contexts (or tail context frames).
Ryan and I came up with a trampoline-like implementation of what I'm calling let-tail-continuation (or let/tc for short), which captures the current continuation, binds it to a local variable, and implements applications of that variable as tail calls. Here's a simplified version:
The trampoline evaluates the body, which is required to evaluate to a thunk, and then applies the thunk in tail position. If the body invokes the captured continuation, it wraps the argument to the continuation in a thunk so that it gets evaluated by the trampoline, again in tail position.(define-syntax let/tc
(syntax-rules ()
[(let/tc k body)
(let ([thunk (let/cc return
(let-syntax ([k (syntax-rules ()
[(k e)
(return (lambda () e))])])
(lambda () body)))])
(thunk))]))
We can observe that applications of the capture continuation are in tail position using the trick I described the other day:
Whereas if we apply the recursive call in a non-tail position with respect to the captured continuation, we see the control stack grow:(define (f n)
(let/tc return
(if (zero? n)
(continuation-mark-set->list (current-continuation-marks)
'test)
(return (with-continuation-mark 'test n
(f (sub1 n)))))))
; => (1)
For the more robust version, I've allowed arbitrarily many body expressions and use an identifier macro to allow the continuation variable to be used in operand position as well.(define (g n)
(let/tc return
(if (zero? n)
(continuation-mark-set->list (current-continuation-marks)
'test)
(return (with-continuation-mark 'test n
(values (g (sub1 n))))))))
; => (1 2 3 4 5 6 7 8 9 10)
Update: Thank you Felix for the correction--that's an important point. The salient issue is not whether the application of a continuation itself is in tail position but whether its subexpression is. The let/tc form allows applications of the continuation to evaluate their subexpression in tail position; another way to put this is that continuation applications are tail contexts (or tail context frames).
Saturday, June 25, 2005
Strict Haskell
I just found these notes on improving inefficiencies in Haskell resulting from laziness. They're written by someone who appears to be a bioinformaticist--hence, someone working with very large datasets and computations. (It's always a breath of fresh air to see non-PL people using something other than Fortran, C, or VB.)
Friday, June 24, 2005
Welcome to the future
On the car ride up to NEPLS today, I watched in amazement as Eli used his cell phone's web interface to trigger a script that made the 2005 ICFP programming contest go live exactly at 10am (9am CT). We were lucky -- around Williamstown the reception started getting spotty, but luckily we hit a good patch just as it was striking 10:00.
I was one of three people to witness the activation of this international programming contest. Who'd have guessed it was happening in a beat-up old car bouncing down the back streets of western Mass?
I was one of three people to witness the activation of this international programming contest. Who'd have guessed it was happening in a beat-up old car bouncing down the back streets of western Mass?
Thursday, June 23, 2005
Literate programming
It's tempting to use literate programming to write a little document recording every last implementation decision you made in designing a library, and that kind of dedication to documentation is admirable, but it's ultimately misdirected.
Javadoc has the better idea: couple the documentation of the interface with the code. I'm beginning to believe that lower-level design decisions should be documented elsewhere, and should be written on a by-need basis only. Code is hard enough to maintain, but documenting every last aspect of your code just guarantees the documentation will get out of date. Often the design decisions are global anyway, in which case there isn't any one place in the code where they really belong.
Javadoc has the better idea: couple the documentation of the interface with the code. I'm beginning to believe that lower-level design decisions should be documented elsewhere, and should be written on a by-need basis only. Code is hard enough to maintain, but documenting every last aspect of your code just guarantees the documentation will get out of date. Often the design decisions are global anyway, in which case there isn't any one place in the code where they really belong.
1000th site visit
Got my 1000th reader today! My readership appears to be growing little by little. Thanks for reading!
Wednesday, June 22, 2005
Observing tail calls
Take a simple tail-recursive function:
How can we demonstrate the control behavior of such a procedure? With continuation marks! If we wrap every reference to f with code that saves the current arguments in a continuation mark:(define (f n acc)
(if (zero? n)
acc
(f (sub1 n) (+ n acc))))
then as long as the reference to f is in tail position, this should overwrite the previous mark. Otherwise, it will build a stack of marks, each representing the current arguments at one of the invocations. We can save this control snapshot for posterity so that after the computation finishes, we can check its most recent value:(with-continuation-mark 'snapshot (list n acc)
(f (sub1 n) (+ n acc)))
Here's a macro that abstracts out this transformation:(define (f n acc)
(set! snapshot (current-continuation-marks))
...)
If we take a control snapshot of an invocation of the tail-recursive f, we get(define-syntax (control-snapshot stx)
(syntax-case stx ()
[(_ f e ...)
(identifier? #'f)
(with-syntax ([(x ...) (generate-temporaries #'(e ...))])
#'(let ([original f]
[snapshot #f]
[label (gensym)])
(fluid-let ([f (lambda (x ...)
(set! snapshot (current-continuation-marks))
(with-continuation-mark label (list x ...)
(original x ...)))])
(f e ...)
(continuation-mark-set->list snapshot label))))]))
If we define a non-tail-recursive version like so:> (control-snapshot f 10 0)
((1 54))
we get a full stack history:(define (g n acc)
(if (zero? n)
acc
(let ([result (g (sub1 n) (+ n acc))])
result)))
You can use continuation marks in this manner to write test cases that ensure that something you've written is using bounded control.> (control-snapshot g 10 0)
((1 54) (2 52) (3 49) (4 45) (5 40) (6 34) (7 27) (8 19) (9 10) (10 0))
Monday, June 20, 2005
We have met the enemy, and it is... hidden invariants
A couple well-known encodings have a very nasty property that they are not bijective. For example, a list of pairs can always be transformed into a pair of lists, and a pair of lists can be transformed into a list of pairs, but if the two lists are of different length, you either have to fail, drop some elements, or throw in some dummy elements. (The latter may be impossible for a polymorphic function.)
Similarly, the option type constructor doesn't distribute nicely over tuples. If you have two fields that must both either be present or absent, it's better to represent them as a single field that is an optional tuple, rather than separate optional fields. This is taking advantage of the type system to help keep your datatypes straight. Even without a type system, it's still better because it groups related elements, and it's one less property to document. We're talking datatype abstraction here, folks. It's a Good Thing.
I've noticed that languages that have a kind of built-in option always available--I'm looking at you, Java--encourage the proliferation of this family of hidden invariants. There are many cases where an object has multiple fields that must all be either null or non-null. I realize they needed null in the language because when you create an object, the fields need to have some well-defined value before they're initialized. (Of course, imperative constructors are a whole 'nother world of pain...) But the additional fact that Java discourages the creation of small datatypes deters people from abstracting their datatypes into separate classes, and the result is these extra invariants.
And we know what happens to hidden invariants: they hide away in the back of the programmer's brain until they get metally garbage collected, lost to posterity, and consequently violated.
That means that the "unzipped" representation, i.e., the pair of lists, contains a hidden invariant that's not expressed in the type: that the two lists have the same length. Even in a language with decidable dependent types like Dependent ML, this invariant can only be enforced so far; for example, if you run the filter function over the two lists, the resulting lists will have statically unknown length.unzip : [(t, u)] → ([t], [u])
zip : ([t], [u]) ⇀ [(t, u)]
Similarly, the option type constructor doesn't distribute nicely over tuples. If you have two fields that must both either be present or absent, it's better to represent them as a single field that is an optional tuple, rather than separate optional fields. This is taking advantage of the type system to help keep your datatypes straight. Even without a type system, it's still better because it groups related elements, and it's one less property to document. We're talking datatype abstraction here, folks. It's a Good Thing.
I've noticed that languages that have a kind of built-in option always available--I'm looking at you, Java--encourage the proliferation of this family of hidden invariants. There are many cases where an object has multiple fields that must all be either null or non-null. I realize they needed null in the language because when you create an object, the fields need to have some well-defined value before they're initialized. (Of course, imperative constructors are a whole 'nother world of pain...) But the additional fact that Java discourages the creation of small datatypes deters people from abstracting their datatypes into separate classes, and the result is these extra invariants.
And we know what happens to hidden invariants: they hide away in the back of the programmer's brain until they get metally garbage collected, lost to posterity, and consequently violated.
Thursday, June 16, 2005
Real world PL design
Let's say I have an imperative language, and I can do all kinds of icky things with it: send messages to a server in Norway, create and mutate reference cells, abort and resume captured continuations. But I find there are large subsets of my program that are pure--no mutation, no I/O, no side effects in general, just functions. I'd love to be able to use laziness for these portions of the program. For one thing, it adds a kind of whole-program optimization, avoiding unnecessary computation and fusing traversals of compound data structures. This alleviates me of a whole bunch of manual optimization. Furthermore, it also allows me to operate on infinite data structures like streams.
Now, since the lazy evaluation strategy doesn't have a clear, sequential operational model, I don't want to use any of the side effects in the lazy portions of the program. I'd like the type system to help me make sure that any effects in the language are restricted to the imperative world, and the lazy world is only allowed to use the pure subset of the language. So we add a simple effect system to the language: an imperative expression of type α is given type Effect α. Then all the imperative language features and standard libraries have this type, and the lazy portions of the program, which cannot have type Effect α for any α, can't touch them.
This is preamble, I suppose, to three points.
1. Monads should be introduced as a customizable effect system. My story above is how I think we should introduce monads. If nothing else, as Simon PJ knows, you're bound to scare people if you use terminology from category theory. For crying out loud, it's okay to have a good theoretical model, but you don't have to confuse the language with the theory! Even when you want people to be able to introduce their own effects into the language, you don't have to call them monads. Just call them effects! This also solves the "what exactly is a monad? Can I hold one in my hand? Is it a value? Is it a type?" problem: I bet people are already comfortable with the idea of an effect as an intangible thing, even though it is something you can "add" to a language by extending the core semantics.
2. The imperative part of a language is important. I think it's the wrong way around to treat the pure functional part of the program as the main part. The imperative part is just as fundamental. It's not the gutter where you sweep all the ugly bits. (The addition of forkIO must really be cognitive dissonance for the monks of pure FP...) Especially when you start having things like concurrency, you really want to put as much care and design into the impure part of the language as the pure part. I'd rather think about embedding pure, lazy languages into general-purpose languages than the other way around.
3. Combining effects is both hard and necessary. Monads are a great abstraction for designing effects. Type classes work fine for modelling individual effects on top of a pure core language, if you really only want to dabble with small doses of individual effects here and there. But monads are notoriously hard to combine, as are language features in general. Making the programmer invent a general purpose PL every time they want these effects is a waste of effort. Notice that the IO monad contains mutable state, concurrency, exceptions and non-termination in addition to actual I/O. That's because, as I said, the imperative fragment of a language is important, and all these effects have proven to be useful and important features of impure languages.
Now, if you rid Haskell entirely of monads and put all the effects into the top-level language, you wouldn't be able to experiment with new language features and effects. And I like the idea of a customizable effect system. So I guess I don't dislike Haskell's monads, but I think they're overblown. What I'm saying is, there's real-world PL design hiding in the IO monad. No pun intended.
Now, since the lazy evaluation strategy doesn't have a clear, sequential operational model, I don't want to use any of the side effects in the lazy portions of the program. I'd like the type system to help me make sure that any effects in the language are restricted to the imperative world, and the lazy world is only allowed to use the pure subset of the language. So we add a simple effect system to the language: an imperative expression of type α is given type Effect α. Then all the imperative language features and standard libraries have this type, and the lazy portions of the program, which cannot have type Effect α for any α, can't touch them.
This is preamble, I suppose, to three points.
1. Monads should be introduced as a customizable effect system. My story above is how I think we should introduce monads. If nothing else, as Simon PJ knows, you're bound to scare people if you use terminology from category theory. For crying out loud, it's okay to have a good theoretical model, but you don't have to confuse the language with the theory! Even when you want people to be able to introduce their own effects into the language, you don't have to call them monads. Just call them effects! This also solves the "what exactly is a monad? Can I hold one in my hand? Is it a value? Is it a type?" problem: I bet people are already comfortable with the idea of an effect as an intangible thing, even though it is something you can "add" to a language by extending the core semantics.
2. The imperative part of a language is important. I think it's the wrong way around to treat the pure functional part of the program as the main part. The imperative part is just as fundamental. It's not the gutter where you sweep all the ugly bits. (The addition of forkIO must really be cognitive dissonance for the monks of pure FP...) Especially when you start having things like concurrency, you really want to put as much care and design into the impure part of the language as the pure part. I'd rather think about embedding pure, lazy languages into general-purpose languages than the other way around.
3. Combining effects is both hard and necessary. Monads are a great abstraction for designing effects. Type classes work fine for modelling individual effects on top of a pure core language, if you really only want to dabble with small doses of individual effects here and there. But monads are notoriously hard to combine, as are language features in general. Making the programmer invent a general purpose PL every time they want these effects is a waste of effort. Notice that the IO monad contains mutable state, concurrency, exceptions and non-termination in addition to actual I/O. That's because, as I said, the imperative fragment of a language is important, and all these effects have proven to be useful and important features of impure languages.
Now, if you rid Haskell entirely of monads and put all the effects into the top-level language, you wouldn't be able to experiment with new language features and effects. And I like the idea of a customizable effect system. So I guess I don't dislike Haskell's monads, but I think they're overblown. What I'm saying is, there's real-world PL design hiding in the IO monad. No pun intended.
Eich on Javascript's future
Via Slashdot, I see that Brendan Eich, the original designer of Javascript (and who's still actively involved in the development of Mozilla) is publicly discussing the future of the language. If he's really open to suggestions I want to think about what I'd most like to see put in there.
Usually, my stock complaint for most languages is the lack of support for recursion. But for compiler output, the needs may be quite different. I really need to go to bed, but I'll think about this.
Usually, my stock complaint for most languages is the lack of support for recursion. But for compiler output, the needs may be quite different. I really need to go to bed, but I'll think about this.
ClassicJavascript
I've written up a CEKS machine semantics for the essential core of Javascript, which just for fun I'm calling ClassicJavascript. It demonstrates the strange scoping and store semantics of the language, the confusing meaning of this, and the prototype-based inheritance model. It doesn't correctly treat the primitive types like objects in quite the way it's supposed to, but that wouldn't be too hard to add. Oh, I also don't have a rule for starting up the machine, which I ought to, because it would explain the "global" object and create the initial Object and Function objects. I'll do that at some point.
I imagine you could use this to reason about a compiler that generated Javascript, if you were pretty ambitious, but mostly I just did it to help myself understand the language. It would also make it really easy to write an interpreter. A lot easier than trying to write to the spec, which is written in a combination of English prose and BASIC-like pseudocode (ouch).
If I do say so myself, this turned out to be a whole lot more concise than the 75 or so pages of the spec specifying the core semantics of the language (that's the part without any description of the standard library).
I imagine you could use this to reason about a compiler that generated Javascript, if you were pretty ambitious, but mostly I just did it to help myself understand the language. It would also make it really easy to write an interpreter. A lot easier than trying to write to the spec, which is written in a combination of English prose and BASIC-like pseudocode (ouch).
If I do say so myself, this turned out to be a whole lot more concise than the 75 or so pages of the spec specifying the core semantics of the language (that's the part without any description of the standard library).
Wednesday, June 15, 2005
Too much recursion
Press this to see how even the high-level scripting languages in the mainstream prevent programmers from using recursion.
Different Javascript engines will give you different error messages, but the Mozilla one is the most offensive: "too much recursion." Groan.
Update: I've modified the Javascript so it should work in Safari, too. But I'm not going to spend more time making a broken script work in multiple browsers.
Different Javascript engines will give you different error messages, but the Mozilla one is the most offensive: "too much recursion." Groan.
Update: I've modified the Javascript so it should work in Safari, too. But I'm not going to spend more time making a broken script work in multiple browsers.
Sunday, June 12, 2005
Point for The Economist
I was one of several people who wrote to The Economist correcting their Latin grammar, and it looks like the last laugh was on us--not only were we geeky enough to waste our time on this nonsense, but none of us completely agreed on the correct version. Hah! Well done.
And I don't think my suggestion was quite right. I chose the neuter plural form plura for "many," but plures would probably have been better. I think the neuter is only for things, whereas the masculine is used for people even when the gender is unknown.
Oh well. At least I got to make an idiot of myself in front of millions of readers worldwide.
Update: After conferring with Richard, we decided that a) the neuter plural was OK, since the original slogan uses the neuter, and b) I should've used ex instead of e, since it appears before a word beginning with a vowel. But this also means not one of the suggestions was right! Stupid Latin.
And I don't think my suggestion was quite right. I chose the neuter plural form plura for "many," but plures would probably have been better. I think the neuter is only for things, whereas the masculine is used for people even when the gender is unknown.
Oh well. At least I got to make an idiot of myself in front of millions of readers worldwide.
Update: After conferring with Richard, we decided that a) the neuter plural was OK, since the original slogan uses the neuter, and b) I should've used ex instead of e, since it appears before a word beginning with a vowel. But this also means not one of the suggestions was right! Stupid Latin.
Thursday, June 09, 2005
DHTML resources
Here's a preliminary a collection of resources on Javascript and DHTML with at least some halfway informative content. I'd be happy to receive more suggestions!
Tips, tricks, and best practices
Tips, tricks, and best practices
- http://www.ditchnet.org/wp/?p=2
- http://www.crockford.com/javascript/inheritance.html
- http://www.webreference.com/js/column79/
- http://www.webreference.com/js/column80/
- http://ditchnet.org/wp/
- http://www.crockford.com/javascript/
- http://www.onlinetools.org/articles/unobtrusivejavascript/
- http://www.brainjacked.com/
- http://jsolait.net/
- http://prototype.conio.net/
- http://dojotoolkit.com/
- http://www.walterzorn.com/dragdrop/api_e.htm
- http://www.whitefrost.com/servlet/connector?file=reference/2003/06/17/libXmlRequest.html
- http://sarissa.sourceforge.net/
Javascript surprises
Javascript is not a wholly unpleasant language to work in, but it has its share of surprises.
Lexical scope: Functions are first-class values, and variables declared within the var keyword are sort of lexically scoped with respect to the nesting of functions. However, despite the C-like syntax, there is no block-style scoping. This means that you can write strange-looking functions like
Furthermore, you can assign to variables that have not been declared with var, which is subtly necessary because of the dynamic scope of this (see below). Basically, if you assign to a variable that hasn't been declared lexically with var, the language first searches the dynamically scoped this object for a member of that name, and then up the prototype chain. Somewhat unfortunately, if it doesn't find any member of the given name, it silently generates a new global variable of that name and performs the assignment.
this is everywhere: There is always a special this variable available, but its binding is dynamically scoped. The upshot is that you can create an ordinary function that refers to this in its body, and then later assign that function as a member of an object, and the this automatically gets wired to the new container.
Bizarrely, there is a special "global" object, so that if such a function is not a member of any object, this refers to that special object; even more bizarre is that particular Javascript engines seem to be free to make that global object whatever they want. In DHTML engines it's some kind of window object or something, whereas in Rhino it might be something else (this is hearsay--I haven't tried it). Furthermore, all global variables are actually member variables of this global object.
It gets even weirder: this means that global function declarations of the form
Object system: Javascript is the only prototype-based OO language I've ever worked with, so this was all new to me. To start with, objects are essentially just associative arrays, i.e., tables mapping names to values, much like Python or Lua. But every object is also linked to a "prototype" object, and name resolution searches the chain of prototype references. This is quite different from class-based inheritance, but it does provide a kind of dynamic dispatch, so it serves similar purposes. (It can also be used to simulate class-based inheritance.) The prototype of an object is exposed via its prototype member variable, which is mutable like everything else in Javascript.
Rather than being defined in classes, constructors in Javascript are simply functions that, when called with the new operator, have their new object implicitly available via this. By convention, people usually capitalize the name of constructor functions, which makes it look like Java-style, class-based object creation. But that "class name" is in fact just an ordinary Javascript function.
for ... in: In addition to the ordinary integer-indexed for loops, Javascript has a for ... in syntax. But it's not at all what you'd expect! This special form is only used to range over the keys (i.e., member names) in an object. It has nothing to do with iterating over collections. Specifically, if you use this to try to use this form on an array, you end up iterating over all the names of the member variables of the array object (which includes the elements of the array, because they are also member variables, whose names are integers! wow). That one took some head-scratching the first time I encountered it.
Extension by mutation: It seems an industry standard form of "extension" is to mutate the prototype of an object. Lord help you if you accidentally overwrite an existing method. What, me, namespaces?
IE has "alien" types: All right, this isn't Javascript's fault. But it's annoying. In IE, the elements of the core DOM are not actually derived from the standard Object prototype, and their prototypes are not even visible. So there's no way to extend the behavior of the core DOM prototypes.
Lexical scope: Functions are first-class values, and variables declared within the var keyword are sort of lexically scoped with respect to the nesting of functions. However, despite the C-like syntax, there is no block-style scoping. This means that you can write strange-looking functions like
function f(b) {
if (b) {
var x = 3;
}
alert(x);
}the variable x is always shadowed in the body of g, so that it displays either 3 or undefined, and never 2.var x = 2;
function g(b) {
if (b) {
var x = 3;
}
alert(x);
}
Furthermore, you can assign to variables that have not been declared with var, which is subtly necessary because of the dynamic scope of this (see below). Basically, if you assign to a variable that hasn't been declared lexically with var, the language first searches the dynamically scoped this object for a member of that name, and then up the prototype chain. Somewhat unfortunately, if it doesn't find any member of the given name, it silently generates a new global variable of that name and performs the assignment.
this is everywhere: There is always a special this variable available, but its binding is dynamically scoped. The upshot is that you can create an ordinary function that refers to this in its body, and then later assign that function as a member of an object, and the this automatically gets wired to the new container.
Bizarrely, there is a special "global" object, so that if such a function is not a member of any object, this refers to that special object; even more bizarre is that particular Javascript engines seem to be free to make that global object whatever they want. In DHTML engines it's some kind of window object or something, whereas in Rhino it might be something else (this is hearsay--I haven't tried it). Furthermore, all global variables are actually member variables of this global object.
It gets even weirder: this means that global function declarations of the form
function foo() { ... }foo = function() { ... };Object system: Javascript is the only prototype-based OO language I've ever worked with, so this was all new to me. To start with, objects are essentially just associative arrays, i.e., tables mapping names to values, much like Python or Lua. But every object is also linked to a "prototype" object, and name resolution searches the chain of prototype references. This is quite different from class-based inheritance, but it does provide a kind of dynamic dispatch, so it serves similar purposes. (It can also be used to simulate class-based inheritance.) The prototype of an object is exposed via its prototype member variable, which is mutable like everything else in Javascript.
Rather than being defined in classes, constructors in Javascript are simply functions that, when called with the new operator, have their new object implicitly available via this. By convention, people usually capitalize the name of constructor functions, which makes it look like Java-style, class-based object creation. But that "class name" is in fact just an ordinary Javascript function.
for ... in: In addition to the ordinary integer-indexed for loops, Javascript has a for ... in syntax. But it's not at all what you'd expect! This special form is only used to range over the keys (i.e., member names) in an object. It has nothing to do with iterating over collections. Specifically, if you use this to try to use this form on an array, you end up iterating over all the names of the member variables of the array object (which includes the elements of the array, because they are also member variables, whose names are integers! wow). That one took some head-scratching the first time I encountered it.
Extension by mutation: It seems an industry standard form of "extension" is to mutate the prototype of an object. Lord help you if you accidentally overwrite an existing method. What, me, namespaces?
IE has "alien" types: All right, this isn't Javascript's fault. But it's annoying. In IE, the elements of the core DOM are not actually derived from the standard Object prototype, and their prototypes are not even visible. So there's no way to extend the behavior of the core DOM prototypes.
Monday, June 06, 2005
There and back again
From There and Back Again by Danvy and Goldberg (via Lambda the Ultimate):
The other solution uses a similar generalization, but in CPS:
Update: No, no, no... I described the purpose of convolve' wrong. It produces a pair containing 1) the convolution of a given suffix of the original first list with the corresponding prefix of the second list, and 2) the remaining suffix of the second list.
Computing a Symbolic ConvolutionTheir direct style solution uses a generalization convolve' that produces the convolution of two lists where the first list may be shorter than the second, as well as the extra prefix of the second list. I've written it here in pseudo-Haskell with dependent type annotations representing the lengths of the lists:
Given two lists [x1,x2,...,xn-1,xn] and [y1,y2,...,yn-1,yn], where n is not known in advance, write a function that constructs
[(x1,yn),(x2,yn-1),...,(xn-1,y2),(xn,y1)]
in n recursive calls and with no auxiliary list.
What it's doing is recurring down the first list until it hits the end and then pairing up the elements as it returns; whatever elements are leftover from the beginning of the second list get placed in the second "return register."convolve' :: [a]m → [b]n → ([(a,b)]m, [b]n-m) -- n ≥ m
convolve' [] ys = ([], ys)
convolve' (x:xs) ys =
let (r, (y:ys')) = convolve' xs ys in
((x,y):r, ys')
convolve :: [a]n → [b]n → [(a,b)]n
convolve xs ys = r where (r, []) = convolve' xs ys
The other solution uses a similar generalization, but in CPS:
Same thing, really. The interesting part isn't the direct style vs. CPS, but rather the discovery of the invariant, i.e., the generalization of the problem. Once we know to write a function that a) allows the first list to be shorter than the second, and b) produces both the partial solution and the remaining elements of the second list, the rest is actually not so challenging.convolve' :: [a]m → [b]n → ([(a,b)]m → [b]n-m → c) → c -- n ≥ m
convolve' [] ys k = k [] ys
convolve' (x:xs) ys k =
convolve' xs ys (λr (y:ys') . k ((x,y):r) ys')
convolve :: [a]n → [b]n → [(a,b)]n
convolve xs ys = convolve' xs ys (λr [] . r)
Update: No, no, no... I described the purpose of convolve' wrong. It produces a pair containing 1) the convolution of a given suffix of the original first list with the corresponding prefix of the second list, and 2) the remaining suffix of the second list.
Saturday, June 04, 2005
AOP is...
[Look out: there is hand-waving! -ed.]
I was reading the background on Dylan's condition system, where the author describes exceptions as "situations that must be handled gracefully but that are not conceptually part of the normal operation of the program." Exceptions are a nice example of a linguistic abstraction that strictly increases the expressive power of a programming language. (Stated without proof, but we've all seen the exception monad.) And they introduce the possibility of non-local effects in code that can't in general be detected by local inspection.
AOP is often described as an answer to the problem of "modularizing cross-cutting concerns." Any time you have something that can't be expressed with the abstraction mechanisms of your given language, it ends up being scattered throughout the program in multiple modules. Well, it sounds like they're trying to take credit for all of linguistic abstraction. But nobody is going to come up with the once-and-for-all abstraction mechanism to eradicate all need for new linguistic abstractions.
On the somewhat less over-reaching side, AOP has popularized a set of (relatively) new linguistic abstractions to the lexicon, and they're useful ones. The few that stand out are before/after and around patterns and control flow inspection. These are useful linguistic abstractions, and as usual, they introduce expressive power at some cost of local reasoning.
I wouldn't be upset if history forgot AOP as a field per se and just kept the collection of useful programming mechanisms it's produced. Because the heady claim that AOP "modularizes cross-cutting concerns" is really just hype. Or at least, it doesn't distinguish AOP from any other linguistic abstraction; any language feature that modularizes scattered code--exceptions, for example--helps separate cross-cutting concerns.
I was reading the background on Dylan's condition system, where the author describes exceptions as "situations that must be handled gracefully but that are not conceptually part of the normal operation of the program." Exceptions are a nice example of a linguistic abstraction that strictly increases the expressive power of a programming language. (Stated without proof, but we've all seen the exception monad.) And they introduce the possibility of non-local effects in code that can't in general be detected by local inspection.
AOP is often described as an answer to the problem of "modularizing cross-cutting concerns." Any time you have something that can't be expressed with the abstraction mechanisms of your given language, it ends up being scattered throughout the program in multiple modules. Well, it sounds like they're trying to take credit for all of linguistic abstraction. But nobody is going to come up with the once-and-for-all abstraction mechanism to eradicate all need for new linguistic abstractions.
On the somewhat less over-reaching side, AOP has popularized a set of (relatively) new linguistic abstractions to the lexicon, and they're useful ones. The few that stand out are before/after and around patterns and control flow inspection. These are useful linguistic abstractions, and as usual, they introduce expressive power at some cost of local reasoning.
I wouldn't be upset if history forgot AOP as a field per se and just kept the collection of useful programming mechanisms it's produced. Because the heady claim that AOP "modularizes cross-cutting concerns" is really just hype. Or at least, it doesn't distinguish AOP from any other linguistic abstraction; any language feature that modularizes scattered code--exceptions, for example--helps separate cross-cutting concerns.
Thursday, June 02, 2005
Deep ideas lurking in Object-Oriented Style, part II
The other important Deep Idea in Object-Oriented Style is the connection between object-oriented programming and recursion. He's not the first to notice this by any stretch of the imagination. This was the central idea in Cook and Palsberg's denotational semantics of inheritance. But it's an important idea that isn't well-enough understood, especially since recursion is so poorly understood in the OOP community.
This is a truly beautiful example:
This is a truly beautiful example:
Not only are objects a generalization of recursive functions, but they could serve as a much more accessible explanation of the Y combinator and "tying the knot" than the usual approaches.(define math-object
(vector
(lambda (this n)
(if (zero? n) #t ((vector-ref this 1) this (sub1 n))))
(lambda (this n)
(if (zero? n) #f ((vector-ref this 0) this (sub1 n))))))
> ((vector-ref math-object 0) math-object 5)
#f
Deep ideas lurking in Object-Oriented Style, part I
Object-Oriented Style
Dan Friedman
A style such as CPS or what Dan describes as Object-Oriented Style, is roughly a design pattern begging for linguistic abstraction. He describes a tension between abstracting out the design pattern--which results in all the usual benefits of abstraction--and gaining a better understanding of the semantics of the style by writing it out explicitly.
This is a fundamental tension in language design. A linguistic abstraction that increases the expressive power of the language results in code that is more concise but that masks widespread (global) effects. One example he gives is the semantics of method calls: when is a method call static and when does it involve searching the inheritance chain? It's hard to tell when they just look like ordinary procedure invocation, but when you write the style explicitly, you can see how the method lookup is implemented.
Now, the expressiveness paper talks about true linguistic abstractions being those that aren't macro-expressible (albeit by a very specific definition of macro-expressibility), and Dan's paper implements the linguistic abstraction via macros. So this seems to muddy my point somewhat. But I think they still capture the spirit of global transformations, since they transform the entire class bodies.
(Interesting: I wonder if macro-defining macros allow you to make transformations that are not macro-expressible by Felleisen's formal definition.)
Dan Friedman
A style such as CPS or what Dan describes as Object-Oriented Style, is roughly a design pattern begging for linguistic abstraction. He describes a tension between abstracting out the design pattern--which results in all the usual benefits of abstraction--and gaining a better understanding of the semantics of the style by writing it out explicitly.
This is a fundamental tension in language design. A linguistic abstraction that increases the expressive power of the language results in code that is more concise but that masks widespread (global) effects. One example he gives is the semantics of method calls: when is a method call static and when does it involve searching the inheritance chain? It's hard to tell when they just look like ordinary procedure invocation, but when you write the style explicitly, you can see how the method lookup is implemented.
Now, the expressiveness paper talks about true linguistic abstractions being those that aren't macro-expressible (albeit by a very specific definition of macro-expressibility), and Dan's paper implements the linguistic abstraction via macros. So this seems to muddy my point somewhat. But I think they still capture the spirit of global transformations, since they transform the entire class bodies.
(Interesting: I wonder if macro-defining macros allow you to make transformations that are not macro-expressible by Felleisen's formal definition.)
Curry-Howard, logically
I tend to think of the Curry-Howard correspondence from the point of view of types: I repeat the slogan "types are propositions about programs" in my head, and that helps me remember that the types correspond to logical propositions, and the programs correspond to proofs of those propositions.
But upon reading the introduction to Proofs and Types, I was reminded of the parallel point of view of proofs. If we think of proofs as mathematical objects, then we can give them natural representations: a proof of A ∧ B is representable as a pair of proofs of A and B, respectively; a proof of A ∨ B is represented as a discriminated union of either a proof of A or a proof of B; and most importantly, a proof of A ⇒ B is representable as a function that takes any proof of A and produces a proof of B.
But upon reading the introduction to Proofs and Types, I was reminded of the parallel point of view of proofs. If we think of proofs as mathematical objects, then we can give them natural representations: a proof of A ∧ B is representable as a pair of proofs of A and B, respectively; a proof of A ∨ B is represented as a discriminated union of either a proof of A or a proof of B; and most importantly, a proof of A ⇒ B is representable as a function that takes any proof of A and produces a proof of B.
Multi-stage web programming
Something languages like Links may want to keep in mind: there could be a great deal of benefit from taking a multi-stage approach. For the moment, let's make a simplifying (though utterly wrong) assumption that a web application lives in a single page. Then we can see three stages:
But now reconsider the above assumption. Real web applications involve multiple round trips, and Ajax is popularizing the further complication of allowing semi-secret (let's never forget the back button, though!) round trips to occur within hidden frames. How does this cycle between the server and client sides change the multi-stage architecture?
- The "runtime" is the dynamic aspect of a page that can be scripted with Javascript.
- Before that comes the page-generation logic that happens on the server side.
- Preceding both these phases is the generation of the static content (the "quoted" part of an ASP or JSP page).
But now reconsider the above assumption. Real web applications involve multiple round trips, and Ajax is popularizing the further complication of allowing semi-secret (let's never forget the back button, though!) round trips to occur within hidden frames. How does this cycle between the server and client sides change the multi-stage architecture?
Subscribe to:
Posts (Atom)
