Collection of links to monad implementations in various languages. Due to recent discussions here on LtU and on the Haskell mailing lists I've compiled a list of links to implementations of monads in various languages. If you know of any that aren't listed here, please submit them in a comment. * Clean * Haskell * Java * Joy * OCaml * Perl * Prolog * Python * Ruby * Scheme
The abstract: We propose a novel, comonadic approach to dataflow (streambased) computation. This is based on the observation that both general and causal stream functions can be characterized as coKleisli arrows of comonads and on the intuition that comonads in general must be a good means to structure context-dependent computation. In particular, we develop a generic comonadic interpreter of languages for context-dependent computation and instantiate it for stream-based computation. We also discuss distributive laws of a comonad over a monad as a means to structure combinations of effectful and context-dependent computation. If you've ever wondered about dataflow or comonads, this paper is a good read. It begins with short reviews of monads, arrows, and comonads and includes an implementation. One feature that stood out is the idea of a higher-order dataflow language.
Advantages of Soft Typing This is a continuation of this discussion. The main points for soft typing are as follows. * Compile time type checks. Soft typing can catch the same amount of provable errors at compile time as static typing. * Automatic downcasts. Downcasts are done automatically assuming the program passes type checking. The main argument for explicit casts is that it provides the programmer with more information, but this is a misnomer. One does not have to write down information for it to be shown to him, so long as said information is inferrable. Note: whether or not you believe OCaml doesn't have casting is irrelevant, simply assume that, when I refer to casting, I also mean situations in which it's emulated. * Unimposing. Unless a piece of code is provably incorrect at compile time, the compiler can insert runtime checks.
I had mistakenly learned that curry was a form of generalized partial application from the paper : Function Currying in Scheme by Jeffrey A. Meunier In my paper I defined curry in Cat as: define curry : ('b ('A 'b -> 'C) -> ('A -> 'C)) { swap quote swap compose } Whereas this really should have been called "partial-apply", "papply" or something comparable. So the correct definition should have been: define papply : ('b ('A 'b -> 'C) -> ('A -> 'C)) { swap quote swap compose } define curry : (('A 'b -> 'C) -> ('b -> ('A -> 'C)) { quote [papply] compose }
Total Functional Programming Here's an interesting paper recently mention in another thread: Total Functional Programming... Abstract: The driving idea of functional programming is to make programming more closely related to mathematics. A program in a functional language such as Haskell or Miranda consists of equations which are both computation rules and a basis for simple algebraic reasoning about the functions and data structures they define. The existing model of functional programming, although elegant and powerful, is compromised to a greater extent than is commonly recognized by the presence of partial functions. We consider a simple discipline of total functional programming designed to exclude the possibility of non-termination. Among other things this requires a type distinction between data, which is finite, and codata, which is potentially infinite. I presume that the bogus definiton of "fib" is a subtle reminder of the importance of eliminating bottom.
Does anyone know of work done on co-data-types? There has been a lot of work done on co-data and stream programming, but the assumption is usually of a very simple repetitive data stream. Has anyone done any work on highly structured co-data or co-data-types? A data structure passed into a function represents a limit on all of it's constituent types, that is, the structure must be fully constructed (AND logic) before the function can be called. But a co-data structure (co-type) passed into a function represents a co-limit and only needs to be partially constructed (OR logic), perhaps the function can even return partial (co-data) results based upon the co-data-type it receives. This seems to me a very relevant topic for advancing stream programming and the exploitation of multiple layers of data parallelism.
A New Approach to the Functional Design of a Digital Computer by R. S. Barton, 1961. The present methods of determining the functional design of computers are critically reviewed and a new approach proposed. This is illustrated by explaining, in abstracted form, part of the control organization of a new and different machine based, in part, on the ALGOL 60 language. The concepts of expression and procedure lead directly to the use of a Polish string program. A new arrangement of control registers results, which provides for automatic allocation of temporary storage within expressions and procedures, and a generalized subroutine linkage. The simplicity and power of these notions suggests that there is much room for improvement in present machines and that more attention should be given to control functions new designs. "One of the most amazing far reaching 4 page papers in our field" referenced in A Conversation with Alan Kay.
Chuck Thacker is building a new research computer called the BEE3. There was a time, years ago, when computer architecture was a most exciting area to explore. Talented, young computer scientists labored on the digital frontier to devise the optimal design, structure, and implementation of computer systems. The crux of that work led directly to the PC revolution from which hundreds of millions benefit today. Computer architecture was sexy. These days? Not so much. But Chuck Thacker aims to change that.
A Tiny Computer. An unpublished memo by Chuck Thacker, Microsoft Research, 3 September 2007. Posted with permission. Alan Kay recently posed the following problem: "I'd like to show JHS and HS kids 'the simplest non-tricky architecture' in which simple gates and flipflops manifest a programmable computer”. Alan posed a couple of other desiderata, primarily that the computer needs to demonstrate fundamental principles, but should be capable of running real programs produced by a compiler. This introduces some tension into the design, since simplicity and performance sometimes are in conflict. This sounded like an interesting challenge, and I have a proposed design. Presents the design of a complete CPU in under two pages of FPGA-ready Verilog. The TC3 is a Harvard architecture 32-bit RISC with 1KB of instruction memory, 1KB of data memory, and 128 general-purpose registers. This design is an ancestor of the DDR2 DRAM Controller used in the BEE3.