Lambda the Ultimate

I am trying to implement heap in CLisp. I have already done it by making a linear data strcuture with no left / right pointers. But now I want to use a nested list format which contains (el () ()) at the highst level.
The problem I am facing with is how to define a recursive case for insertion. Heap requires the tree to be complete.

I approach the issue as follows:

1. I will take a heap and an element
2. I will add the element in the last node keeping it a complete tree
3. I wil swap the child with parent if it is greater than the parent

But I am stuck at the second step i.e. how to add an element without making the tree incomplete? KIndly help me on this!!!!!!!

OMeta: an Object-Oriented Language for Pattern Matching

A new paper by Alessandro Warth and Ian Piumarta, related to the Reinvention of Programming project:

This paper introduces OMeta, a new object-oriented lan-
guage for pattern matching. OMeta is based on a variant of
Parsing Expression Grammars (PEGs) [5]—a recognition-
based foundation for describing syntax—which we have
extended to handle arbitrary kinds of data. We show that
OMeta’s general-purpose pattern matching provides a nat-
ural and convenient way for programmers to implement
tokenizers, parsers, visitors, and tree transformers, all of
which can be extended in interesting ways using familiar
object-oriented mechanisms. This makes OMeta particularly
well-suited as a medium for experimenting with new designs
for programming languages and extensions to existing lan-
guages.

This might be a little bit off topic, as it's hardware related, but radical changes in hardware have a way of trickling up to the software. After listening to Ted Neward's keynote about the future of languages, I had a series of thoughts.

1. We really do have fundamental issues related to multi-core concurrency, distributed programming, and (by implication) emergent behaviors of our software systems.
2. FPGAs are dynamic hardware
3. You could, in theory bundle a CPU with an FPGA so they sit on the same die
4. FPGAs are useful for truly running a Virtual Machine (rather than simulating one on the CPU)
5. This would be incredibly powerful, if, as Ted implied, DSLs expand in popularity, we should use the hardware itself as a VM.

One of the most immediate benefits I could envision was the ability to run a webserver in conjunction with an interpreted language at much faster speeds. Or, in high-performance computing, making a multi-core pipeline specific for your research simulation. I'm sure that you all can think of many others; I'm sure it's one of those technological marriages that spawn unexpectedly useful offspring.

Is this idea out there? Does it have a name? What researchers have explored this area? Are FPGAs currently useful for such applications? How long will we have to wait?

Obviously we'll need a DSL just to program the thing (as if multi-core alone wasn't hard enough), and with it, a good silicon compiler.

Implicit Ownership Types for Memory Management. Tian Zhao, Jason Baker, James Hunt, James Noble, and Jan Vitek. Draft.

The Real-time Specification for Java (RTSJ) introduced a range of language features for explicit memory management. While the RTSJ gives programmers fine control over memory use and allows linear allocation and constant time deallocation, the RTSJ relies upon dynamic runtime checks for safety making it unsuitable for safety critical applications. We introduce ScopeJ, a statically typed, multi-threaded, object calculus in which scopes are first class constructs. Scopes reify allocation contexts and provide a safe alternative to automatic memory management. Safety is the result of our use of an ownership type system that enforces a topology on run-time patterns of references. ScopeJ's type system is novel in that ownership annotations are implicit. This substantially reduces the burden for developers, thus increasing the likelihood of adoption. The notion of implicit ownership is particularly appealing when combined with pluggable type systems, as one can apply different type constraints to components depending on the requirements. In related work we have demonstrated the usefulness of our approach in different applications

An example of a pluggable type system which, unlike previous discussions on LtU, eg. Gilad Is Right and Flexible Addition of Static Typing to Dynamically Typed Programs, adds more type rules to an already statically typed language. It doesn't, however, appear to be an optional type system as it seems to make use of a library and some syntactic rules to encode the region types.

The type system itself seems quite complicated which may be due to building on Java's existing type system as much as the support for first-class and multi-threaded regions, an aspect which seems to be unique in region calculi. Compare the complete type system for F^RGN in Monadic Regions. Not that I can claim to understand all the maths in that paper either but Oleg Kiselyov's implemetation on top of Haskell's ST monad is short and sweet.

"Each chapter describes a particular aspect of the P-code system, each section discussing a particular procedure or group of procedures, sometimes preceded by an explanation of the data-structures used."
Pascal Implementation

Hello,

The Erlang guy Joe Armstrong said: Basically there are two models of concurrency. Shared state concurrency, and Message passing concurrency. (from Dr. Dobbs article www.ddj.com/201001928 )

Which of those two models of concurrency does STM, software transactional memory, fit into?

Thanks.

BBC reports:

The organisation behind the project has launched the "give one, get one" scheme that will allow US residents to purchase two laptops for $399 (£198).

One laptop will be sent to the buyer whilst a child in the developing world will receive the second machine

The G1G1 scheme, as it is known, will offer the laptops for just two weeks, starting on the 12 November.

OLPC is a very worthy project which probably needs your support, and buying a machine is a fun way to support the project while also enjoying a remarkable machine.

The OLPC programming environment includes not only Python etc. but also Squeak, and the firmware uses Forth, so the OLPC will probably be attractive to language hackers.

Version 1.6.1 of the Open Quark Framework for Java has been released.

Open Quark is a BSD-licensed lazy functional runtime for Java, with a native language called CAL.
The motivation for Open Quark is to allow embedding of lazy functional logic within Java applications, including full functional metaprogramming (under Java control) if required. The framework also allows standalone CAL applications to be created.

This release is notable for its inclusion of libraries for parallel programming (the prior version, 1.6.0, having experimental support for this, but without library support).

The full release notes for this release can be found here.

Downloads are available on the main Open Quark site.

Feedback and other contributions to the project are very welcome. Please visit our discussion forum.

My research interest is in design of programming languages, particularly OOPL. I think the obvious journals/conferences are:

- TOPLAS
- POPL
- ECOOP
- OOPSLA
- FOOL
- JOFP

Any other should I pay special attention to?

Certain rules are considered "unsafe" and disallowed in Datalog because they don't restrict all of their variables to a finite domain (and therefore may not have a finite number of solutions). For instance, in:

beef(X) :- lemur(X), not(alice(X, Y)), not(bahnanlagen(Y)).

Y is not restricted to a finite domain, so the rule is unsafe. Additionally, no use of the beef predicate can further restrict the domain of Y. However, a rule may be unsafe only because its distinguished variables are not restricted:

orange(X) :- zorro(Y), X < Y.

A predicate like orange/1 doesn't seem different from a negated relational predicate or an arithmetic predicate, since its otherwise unrestricted variables can be further restricted by the context in which it is used. For instance, a rule like:

fromage(X) :- elephant(X), orange(X).

...appears to be safe (where elephant/1 and zorro/1 are safe relational predicates). After all, the apparently equivalent:

fromage(X) :- elephant(X), zorro(Y), X < Y.

...is safe in that case. Provided their use is restricted in the same fashion as negated and arithmetic predicates, are there any problems with permitting this latter kind of unsafe rule that I'm just not seeing?