Lambda the Ultimate

An article (draft) titled "ΠΣ: A Core Language for Dependently Typed Programming", an online demo and a Hackage repository with source code for a type checker.

To my big surprise I haven't found it on LtU.

This is a proposal for a language that could serve the role the Haskell Core serves for Haskell - a small in list of features, verbose language in which we can translate higher-level concepts.

This is interesting as PiSigma contains minimum features and one can play with implementation.

Hello everyone, I'm a software developer interested in information retrieval. Currently I'm working on my 3rd search engine project and am VERY frustrated about the amount of boilerplate code that is written again and again, with the same bugs, etc.

Basic search engine is a very simple beast that could be described in a formal language consisting of two "layers":

1. "Layer of primitives" (or axioms, kernel language - don't know how to name them). They consist of several sets (as a set of resources - files, websites), relations on sets (as 'site A links to site B') and simple operations as 'open stream to resource A', 'read record from stream', 'merge N streams', 'index set of records by field F', etc. Also, there is a lot of data conversion, as 'save stream in YAML format', 'load stream from XML format', etc.

2. 'Application layer' - several very high-level operations that form a search engine lifecycle, as 'harvest new resources', 'crawl harvested resources', 'merge crawled resources to the database', 'index crawled resources', 'merge indexes', etc. Every one of this high-level operations could be expressed in the terms of "primitives" from 1.

Such a high-level representation could be easily tested, maybe even proved formally, and implemented (or code-generated) in the programming language of choice.

So, the question: does anybody design systems in this way - formally, rigorously ( maybe even at the level of algebra/group theory), in the strict top-down approach? What can I read to learn about ?

This question was also posted here: http://stackoverflow.com/questions/1796481/how-to-learn-about-formal-top-down-approach-to-software-architecture

Presuming for now that a "module" 1) is a named and managed name space; 2) is a body of definitions, some of which are private and others provided for export to other modules; 3) is also a compilation unit; 4) is, in fact, imported by other modules, with circularity of imports forbidden or permitted based on the language definition; 5) is compiled separately and linked into a standalone "executable program" file; 6) may be a privileged module in an "executable program" linking activity as the "main" module containing either a function that begins program execution or a series of sequential definitions (or "statements") that essentially comprise an equivalent "main" function that begins program execution.

I think that's all grammatical, and in fact, more or less common policy for many programming languages with oodles of variations on this basic theme.

I seek papers that discuss (1) module initialization, such as a variable definition in a module that requires on it's "right hand side" a complex computation, 2) perhaps a computation that requires definitions from other modules, 3) the compile time determination of the "loading" or "initialization" of modules, 4) the wisdom or lack thereof of only allowing function definitions in modules, perhaps with only a special "initialization" section of the module definition (Modula 2, Turbo Pascal...); 5) policies regarding the permission or forbidding of circular module imports.

So I'm looking for the "finest available wisdom" about some fairly prosaic issues surrounding a few aspects - modules, initialization, ordering, separate compilation, etc. - of programming languages designed for static analysis and program compilation. Did anyone "get it just right?" Or has anyone layed out the essential and unavoidable design trade offs showing that "getting it right" is a matter of programming language design 1) taste or 2) intended purpose or 3) implementation complexity or 4) etc. - you get the idea.

I do prefer papers a *little* "closer to the run time," as it were. I happen to suffer the somewhat common "too many pages of Greek symbols shuts down my brain" syndrome :-)

Any and all help and pointers greatly appreciated.

Scott

I haven't heard anyone mention it in the forums yet, so I figured I'd provide a pointer.

Rx is a .NET Library that allows programmers to write succinct declarative code to orchestrate and coordinate asynchronous and event-based programs based on familiar .NET idioms and patterns.

The Rx library provides APIs to create instances of these interfaces from scratch, convert existing asynchronous patterns such as events to these interfaces, query, transform and merge observables.

In the recent past there have been several videos on Channel9 talking about Rx in Depth. We can strongly recommend watching them:

• Kim Hamilton and Wes Dyer: Inside .NET Rx and IObservable/IObserver in the BCL (VS 2010)
• Expert to Expert: Brian Beckman and Erik Meijer - Inside the .NET Reactive Framework (Rx)
• E2E: Erik Meijer and Wes Dyer - Reactive Framework (Rx) Under the Hood 1 of 2
• E2E: Erik Meijer and Wes Dyer - Reactive Framework (Rx) Under the Hood 2 of 2

I particularly recommend the two-part video with Erik and Wes, which provide the most LtU-relevant content.

I've been spinning my wheels on this for awhile, so I'm hoping LtU has an answer: has there been any connection derived between transactions and promises/logic variables? I'm considering here promises as implemented in Alice ML and at least ACI properties of transactions minus the D. The connection is more apparent in a personal project where this came up, so apologies if this seems ridiculous at first.

If you view the store as an immutable pair:

type 'a Store = { current: 'a; future: 'a Store Future }

beginning a transaction consists of starting a computation with the promise for that future:

val begin_trans: 'a Store -> ('a Store Promise -> ()) -> ()

and committing a transaction consists of resolving the promise for that future

val commit_trans: 'a Store Promise -> 'a Store -> ()

Of course, transactions can nest stack-like, and one could recreate this by creating more promises down the call chain which get resolved as calls return. Of course, promises also permit non-nested resolution if needed (though I'm sure that sounds ridiculous for transactions).

It seems a little tenuous as I've glossed over many details and LtU isn't the place for detail design discussions, but hopefully it's understandable enough that someone can point out where this has been already been discussed, or tell me how ludicrous the entire idea is.

I would like to track down earliest published (for citation) introduction of the terminology "abstract syntax." At some point prior to 1975 I picked up (and used) the terminology from the literature I surveyed while turning my doctoral dissertation into a monograph. But I can't find any references in my remaining old research notes.

I was mainly looking at articles by Dana Scott, Strachey, Milner, Landin, McCarthy at the time, and the then-existing literature on denotational semantics.

Additionally, also for citation, suggestions to the "best" discussion of abstract syntax, comparing it to concrete syntax.

Thanks.

Hal Levin

I recently completed an extensible Pratt parser in C#. I've only managed to find a single mention of a statically typed Pratt parser, pointing to this Ada library. Most implementations I've found are for dynamic languages, ie. Python, JavaScript, Scheme, and of course, Pratt's original implementation was in Lisp.

Is Pratt parsing, aka "top-down operator precedence parsing", really so little used? Or is its use behind the scenes, perhaps in a parser generator or as part of a post-processing phase to resolve operator precedence when using a parser combinator library? Are there any problems to using a typed Pratt parser as compared to parser combinators?

Regarding research for the design of a module system, my efforts seem to mostly conclude that the term "MODULE" means just about *anything* to *anyone*, therefore next to *nothing* ;)

To keep this message terse, just think yourself of all of the really weird terminology applied to language constructs otherwise all called "module systems" in different programming languages!!!!

I've more or less settled on Scheme's r6rs relatively simple module system, but I have low confidence that this is the right design choice. It *really* has been extremely frustrating.

Is there anything that provides some logical and/or historical overview or survey on the myriad concepts of "module system" in computer programming language design? (The major languages, the historical design "milestones" or whatever).

To each their own language, but am I alone in aspiring a productive, efficient and fun programming language for the advanced programming professional?

Here's a list of 50 items I'd like to see for the basis of a new language:

* runs really fast (compiles to native code) and has a performance profile within 20% of C.
* compiles really fast (have you seen "GO" compile?)
* has an "interpreter" (compiles and runs code on the fly)
* can be used as a systems programming language (ie: you can write device drivers with this stuff)
* supports both functional and imperative programming (leans on the functional)
* functional programming is pure and identifiable at compile time.
* imperative programming is identifiable at compile time.
* passing an imperative function to a higher order pure function renders the pure code impure.
* for/while loops and mutability allowed in pure functions so long as the output is pure (and there's no IO and such)
* Mutability allowed within imperative code, but contained within function body for pure code.
* OOP but no classes (see Haskell Type classes and GO's interfaces)
* Strongly typed and supporting Generic programming
* Soft-realtime GC
* NO null pointers
* Continuations
* Data types can be extended, methods can be specialised.
* No exceptions, but a similar throw/handle mechanism for errors _within_ a single body of code to increase readability.
* Fault-Tolerance built right into the library
* Inner functions
* name spaces
* modules
* neither lazy nor eager evaluation by default, but three distinct function calling operators. CALLER PICKS {lazy, eager, usecallersemantics}
* exception to the above, function arguments -- lazy by default (so you can write your own control loops).
* understandable compiler errors
* efficient pure array programming
* efficient in-memory database structure (multi-index table data structure)
* easily parse binary data (see Erlang's bit syntax)
* compiled regular expression syntax
* extensive message-based concurrency
* multi-core, multi-note runtime environment (can relocate a computation from one box to the next and back again)
* parsable code so an IDE is easy to build
* possible and straightforward provide a contextual method list in the IDE: it's a huge productivity booster
* executable carries meta-data such as dependencies and run-time reflection.
* supports embedding DSLs with code (e.g. so you can declare XML data and have it parsed and turned into code at compile time)
* supports embedded assembly code --automatically marking the code as "unsafe"
* scalable: not declaring a module header imports a standard bunch of stuff that makes it easy to write programs that easily do what Python, Perl, Ruby do.
* must be able to mark an executable as "safe" and indicate dependencies in meta-data so it can be run in a sand-boxed environment
* fast string processing
* UTF-8 support out of the box
* Module split into "public" (on top and default) and "private" section. --no mucking about retyping all the "exported" functions
* Immediate guaranteed collection of objects living on the stack: support for RAII (great for managing resources other than memory)
* Haskell-style indenting
* pattern matching
* guards
* Good debugger which supports back-stepping
* No debug build vs opt build.. Debug info efficiently ignored unless run under a debugger.
* currying possible, but explicit .. e.g: map(someFun,__): Currying can lead to hard-to-figure-out compile errors.
* Scala-style _. i.e. _.moo() creates a lambda on the object. Similarly run(_, 42, _) returns a function with two args.
* no semi-colons at the end of the line

So like 30 years ago in Byte, some cool dude had an m4 clone and an assembler on a CP/M machine and managed to bootstrap a full Pascal development environment.

Ok, I exaggerate, but it's hard to meet an old Forth'er who doesn't have more than one Forth system bootstrap story.

I don't know if there's a formal definition of "bootstrap" (esp. re: prog langs/environments).... So any help here welcome too.

But in this day of compiling to C, the JVM or CLR, LLVM, C--, Boehm's "instant" GC, huge and complex runtime systems and tools + tools + tools, it got me thinking about the days or yore (or current practice, even better) of "bootstrapping" a language and programming environment from "minimal components," to say the least.

I'm also interested if there are *qualities* of various languages/environments that lend themselves to bootstrapping from small parts, while other languages lack these qualities for whatever reasons.

Thanks much in advance.

Scott