Lambda the Ultimate

I am considering writing a paper about non-applicative functional language with the following abstract:

Non-applicative Functional Languages

Most of today's functional languages are examples of applicative languages. In other words
the operation of function application is generally implied between two consecutive terms.
This paper explores what it means for a language to be non-applicative, and what the implications
are in terms of basic operations such as the Y combinator.

Is this a topic that has already been explored? I only found one reference to "non-applicative languages" on Google scholar. Is anyone else interested in this topic? Any suggestions on how to make the abstract more appealing?

Thanks in advance.

Hi

I was just going thro abt MapReduce for my final year project work.....

I got confused in the middle.... What i thought is "MapReduce deals greatly with key/value pairs only... For fitting a problem into mapreduce we should find the key/value pairs"

I want to know whether im right or wrong....

I got confused after looking at the explanation in wikipedia... The following is the content in wikipedia abt mapreduce...

"Continuing the previous example, what if one wanted to know the average of the test scores? One could define a reduce function which halved the size of the list by adding an entry in the list to its neighbor, recursively continuing until there is only one (large) entry, and dividing the total sum by the original number of elements to get the average."

Here in map function we are simply adding up the test scores.... we are not using any key/value pair..... Im totally confused....

I might be wrong at any point... please someone help me out..... Am i wrong in the basic understanding of MapReduce itself..... Ill be thankful if anyone explains me clearly...

please help me out to successfully complete my final year project....

Jaya

I've completely revised the Cat technical report, based on a lot of valuable feedback from members of Lambda-the-Ultimate.org (and others).

The revised version is posted at cat-language.com/paper.html, and I'd be very grateful for any additional comments or suggestions.

Cat: A Typed Functional Stack-Based Language

Cat is a purely functional stack-based language with very simple semantics and a novel type system, which makes it appropriate for usage as an intermediate language. Cat differs from most other functional languages in that the concatenation of terms implies the operation of function composition instead of the more common operation of function application.

This paper presents the semantics and a type-system for Cat, and briefly discusses some of the interesting properties of the language.

I am hoping to submit to ICFP 2007, but if anyone has any suggestions for other appropriate venues, I'd love to hear them.

Thanks in advance!

Alrighty, another question for which I'm not sure how to start looking for answers. Don't worry, this will probably be the last one for awhile.

The idea for this one is that you have version 1 of a program, and you make a change to it. Now how does version 2 differ from version 1? Or put another way, what inputs/test cases end up returning different results from before?

The purpose of this is to develop a tool that will help to ensure one is not introducing any bugs. I'm aware that there are some computability issues. I'm not asking for anything that solves the halting problem. I think that such a tool could still be useful.

I've been studying static analysis and formal verification. With more study I think I could answer this question for myself, but that's going to take forever :)

And, on a more general note, are there any heuristics for figuring out what to look for when one wants to answer a question like this? Or is it you just keep studying and following leads until you get somewhere? I don't mind the latter, it's just a lot of work that I'd rather avoid if I could :)

An Analytical Approach to Programs as Data Objects (PDF), Olivier Danvy, 2006.

This work presents an analytical approach to programs as data objects, i.e., to programs
whose representation is operated upon by other programs. The approach is analytical in
that a variety of program manipulations is considered and their impact on program understanding,
design, and efficiency is measured.
Most of the programs considered here are language processors, i.e., programs interpreting,
translating, or transforming other programs. As for the program manipulations, they
concern block structure and lexical scope, the representation of functions at run time, and
the representation of control.

A dissertation by Olivier Danvy. I haven't read it yet, but it sounds like a compilation of all the work he has been doing for the past several years. So there is probably not too much that is new, but it should be presented more cleanly and coherently drawing on the connections that join them.

Hi,

I started to read LtU regularly since two or three months ago, and found it is very interesting. I am also very interested in programming languages, and create one named Dao. It is still under active developing, to further improve it, I would like to bring it to the attention of LtU users, and to see if I can get some feedbacks from you;-)

Though no stable version of this language has been made available yet, a number of interesting features have been implemented in this language. In particular, IMHO, there following could be interesting for LtU users:

1. Concurrency: coroutine, thread, asynchronous function call and message passing interface;
2. A macro system that allow defining new syntax in a similar way as writing a BNF-like syntax description;
3. Mixed programming with C language, allowing embedding C codes in Dao scripts.

Dao is an object-oriented language with rich data types and syntax. Though it is not designed to be functional, it supports first class functions, so it may allow certain kind of functional programming. Other features supported include exception handling, numeric array, regular expression matching and automatic memory management etc. It also has a clean interface to C language, and is extendable and embeddable.

The implementation of the language and the mentioned features is by no means perfect, there is still much to be improved. The documentation is still priliminary, but should be enough to get a clear idea of the language. It would nice if you can make some comments, critiques and suggestions on this language. Thank you!

links:
Dao Language Site
SourceForge project for the language

Hi, for awhile now I've been interested in how one can generate a grammar from a corpus of source code. I have a vague idea as to how I might go about it and I was hoping to get pointers to more info.

The basic idea is that we try to find the smallest "regular expression" that can accept samples from our corpus, where "regular expression" actually means "can parse a context-free grammar".

We would start by finding the strings that occur over and over again, and we would match those by a simple string matcher. Then we would attempt to find a regexp that characterises the stuff that occurs between the commonly occuring substrings. I am much less certian how to do this part. the ideas that I have are too vague to describe.

Another thing that I think is important, is that we would address the complexity issue by first running our grammar recoverer on a small sample. The idea is that the small sample would do the bulk of the work in discovering the grammar, while later iterations would do less work because they are only refining the work that was done before. I think this could be done by running the recoverer and seeing how it fails, doing only enough work to refine the recoverer into a working one.

Anyways, I know this is all vague, but can anyone point me to research on how to recover a grammar for a language from samples of text in that language? I am going to a nearby college to check out some books on formal languages but I'm doubtful that I'll find what I'm looking for.

I wonder how you would name a design pattern, where you implement a "module" behaviour by function of the following form

f : State x Command -> State x (array of ExternalCommand)

or (equivalently)

f : State x Command x ([] -> ExternalCommand) -> State

where
- State, Command, and ExternalCommand are purely data (no resources nor functions)
- ExternalCommand is likely to describe operations on (external) resources
- in the second form, ExternalCommand-s should be processed after evaluating f (they could be queued externally)

This might be of interest around here.

I am pleased to announce that twenty-one talks from Dan Friedman's 60th birthday festschrift are now on Google Video. You can find links to the talks on the official DanFest home page. Every LtU reader should find at least several talks of interest:

• Andrew Hanson: Welcome to DanFest
• Mitch Wand: Relating models of backtracking
• Lynn Winebarger: Extending Scheme for bottom-up relational programming
• Bil Lewis: Debugging backwards in time
• Steve Ganz: Monadic Encapsulation of State
• Kent Dybvig: The guaranteed optimization clause of the macro-writer's bill of rights
• David Wise: Introduction for Guy Steele's keynote address
• Guy Steele: Dan Friedman: Cool Ideas (Keynote address)
• Olin Shivers: The anatomy of a loop: a story of scope and control
• Kevin Millikin: Obfuscating transformations via abstract interpretation
• Bob Filman: Poetry in programs: A brief examination of software aesthetics, including some observations on the history of programming styles and some speculations on post-object programming
• Gerald Jay Sussman: The role of programming in the formulation of ideas
• Anurag Mendhekar: Aspect-oriented programming in the real world
• Shriram Krishnamurthi: Verification of web programs
• Jim Marshall: Introductory cognitive science course using Scheme
• Rhys Price Jones: DNA analysis
• Oleg Kiselyov: Normal-order syntax-rules and proving the fix-point of call/cc
• Julia Lawall: On designing a target-independent DSL for safe OS process scheduling components
• Kathi Fisler: Aspect verification using model checking
• Jonathan Sobel: Implementing Categorical Semantics
• Matthias Felleisen and Robby Findler: An investigation of contracts as projections

DanFest was previously mentioned on LtU. In fact, Ehud wrote, "I sure wish that [Guy Steele's] keynote was available online somewhere.". Not only will you enjoy the keynote, Ehud, but you might even find a talk given in the style of The Little Schemer. :-)

In addition to watching the talks online, you can download the videos to your computer and watch them at a higher resolution with Google Video Player.

Enjoy!

--Will