A Type System Equivalent to Flow Analysis

Flow-based safety analysis of higher-order languages has been studied by Shivers, and Palsberg and Schwartzbach. Open until now is the problem of finding a type system that accepts exactly the same programs as safety analysis. In this paper we prove that Amadio and Cardelli's type system with subtyping and recursive types accepts the same programs as a certain safety analysis. The proof involves mappings from types to flow information and back. As a result, we obtain an inference algorithm for the type system, thereby solving an open problem.

I believe it's instructive to see type systems in this light. Did we discuss something like this recently?

Garbage collection has improved greatly over the years, but there are worst cases which are still difficult to avoid without writing your own custom memory management system. For example, let's say you have 128MB of 3D geometry data loaded in Haskell/OCaml/ML-NJ/Erlang/Lisp/YourFavoriteLanguage. This data is in stored in the native format of your language, using lists and tuples and so on. At some point, the GC is going to go through that 128MB of data. Generational collection delays this, but it some point it will still happen. Or do any systems handle this situation gracefully?

The best I've seen in this regard is Erlang, because each process has its own heap, and those heaps are collected individually. But if you put 128MB of data in one heap, there will still be a significant pause. Perhaps Erlang's GC is still better than most in this regard, as there a single-assignment language creates a unidirectional heap which has some nice properties.

And then of course there are the languages with reference counting implementations, which perform better than languages with true GC in this regard.

Thoughts?

There ought to be a word for the sinking realization that, semantically, the language you've been designing and implementing for months is only a small extension over the one you're implementing it in.

(I posted about this language once before. Writing an interpreter for it in Scheme was one thing; but, once I started to compile it down to Scheme, and saw how easy it was--the generated Scheme code was a pretty trivial transform from the ASTs--I realized that meant my semantics offered very little over Scheme's. I'll probably stick with it as an exercise, but that's about all the value it offers at this point.)

The following is from my latest project which is a foray into functional programming. Any comments or suggestions?

The Unimperative Programming Language

by Christopher Diggins

Introduction

Unimperative is a simple programming language, which supports a mix of procedural programming and functional programming. In Unimperative the primary data type is a function. The sequence of evaluation in Unimperative matters somewhat, and function parameters are evaluated left to right.

Unimperative has a surprise twist, which I will save for the end

Comparing to Scheme

Unimperative is quite similar to Scheme. In Scheme we can write a factorial function as:

  (define factorial
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1))))))

In Unimperative we can write the equivalent function as:

  Function factorial =
    (IfZero, _1,
      1,
      (Mult, _1, (Self, (Dec, _1))));

Basic Usage

In many language we call functions by writing:

  MyFxn(x, y)

In the Unimperative programming language we instead write:

  (MyFxn, x, y)

The first element following an open paranthesis, and followed by a comma, is always treated as a function which will be evaluated. The elements which follow are passed as arguments to the function.

Other functions after the first one in a list are not evaluate:

  (MyFxn, OtherFxn)

This evaluates the function MyFxn and passes the OtherFxn as a parameter without evaluating it.

A function must be followed by at least one argument in order to be evaluated. The evaluation operator is the combination of paranthesis and comma:

  (xxx,

The following code does not evaluate MyFxn:

  (MyFxn)

If we wanted to evaluate MyFxn we would have to write:

  (MyFxn, nil)

Alternatively we could also write:

  (Eval, MyFxn)

Defining Functions

To define a function in Unimperative we do so as follows:

  Function MyFxn = (Add, _1, _2);

The _1 and _2 are place holders which refer to the first and second argument respectively.

An Interesting Twist

The Unimperative programming language has a surpise: it is completely legal C++, and doesn't use any macros! An Unimperative library will be available soon as part of the next OOTL ( Object Oriented Template Library ) release from http://www.ootl.org