notes-computer-programming-programmingLanguageDesign-programmingConstructs4

row polymorphism:

http://www.cs.cmu.edu/~aldrich/courses/819/slides/rows.pdf

within a conventional type system in which everything has one type, how to represent OOP and subtyping?

The Loss Of Information Problem

if you have an object type A, which is a record with one field, 'a', whose type is Int (for example, "{a: 3}" would be an instance of A); and you have a function f of type A -> (Int, A), whose implementation is "lambda x: (x.a, x)", then what happens when you apply this f to a subtype of A with more fields, e.g. {a: 4, b: 5}?

Since f's return type is (Int, A), the second member of the tuple, which is x in the implementation, that is, {a: 4, b: 5} in the example, will be coerced from type B to type A, that is, {a: 4}.

But what you wanted is {a:4, b:5}. So the formalism must be wrong.

Row polymorphism modifies the formalism to deal with this. It says that the type of f should really be r :: Row(r/a:Int) => r -> (Int, r), where Row(r/a:Int) is a typeclass that contains all types which are records which have at least a field 'a' with type Int.

---

await:

http://tirania.org/blog/archive/2013/Aug-15.html

---

named break and named continue

"long after Dijkstra's essay, we could still occasionally find new places where goto was really the best way to do it: for instance, if you wanted to "break" out of multiple loops at once. So someone invented named break (likewise continue), and removed yet another use of the unconstrained goto in favour of a more constrained, structured construct."

--

prolog's cut

--

first-class environments

--

first-class continuations

--

" We add the procedure up to ProtoLisp? that normalizes its argument and then returns its internal structure. Thus typing in (up (lambda (x) (+ 1 x))) will return a closure. The down procedure is added to ProtoLisp? to turn an internal structure obtained via ' or up into a ProtoLisp? value. E.g. (down '3) returns the \number" 3. "

---

Lambda-reflect

declares a function that gets

"three parameters. When a re ective lambda call is re- solved, they are bound to the expression, the environment and the continuation at that normalization step."

apparently the user subprocedure must actually call the continuation, otherwise the program exits

" The tower model One of the most debated ideas of Smith's account on re ection is the tower model. In this model, 3-Lisp is implemented as an in nite stack of meta circu- lar interpreters running one another. This solves some conceptual and technical problems that arise when implementing procedural re ection in 3-Lisp. One such problem is the following: Consider a re ective lambda where the continuation passed to it is ultimately not called. In a naive implementation of 3-Lisp, eval- uating a call to such a re ective lambda would result in exiting the 3-Lisp repl and falling back to the implementation level, since the passed continuation in- cludes the continuation of the ProtoLisp? repl. Generally speaking, this is not the desired functionality. Using an interpreter that implements the tower model, calling a re ective lambda can be resolved by the interpreter that is running the repl the programmer was interacting with at the time of the call. The only way the programmer will get back to the original interpreter is when the continuation is called inside the re ective lambda's body. When the continuation is not called, then the programmer just stays in the upper interpreter. This is referred to as \being stuck" at a meta level [4]. As such there is no danger the programmer falls back to the implementation level [6]. Problems like those can occur when there is re ective overlap , i.e. when a re- ective language construct renders some part of the implementation explicit, but also relies on it [2]. In our example, re ective lambdas render the continuation explicit, but when it is not called inside its body, then the entire interpreta- tion process is stopped. Tower models are generally believed to solve problems introduced by re ective overlap. However, they are not the only solution. The Scheme language, for example, is not designed as a tower, and though it intro- duces call/cc to capture a continuation, not calling it will not result in exiting Scheme, but it will just be implicitly called, no matter what. "

i think having the continuation called by default is less repetitious to the programmer

---

-- Stepper:

"Reification without evaluation"

this paper gives some more complaints with 3Lisp's infinite tower and continuations:

http://dspace.mit.edu/bitstream/handle/1721.1/6461/aim-946.pdf?sequence=2

basically, they argue that continuations and the infinite tower may both be useful and interesting, but continuations should not have level-shifting properties. continuations should just do stuff within one program, like call/cc in scheme.

they give an alternative called Stepper, which, when passed program source to evaluate, instead of running the program, returns a tuple representing the first step to take while running the program, the current continuation, and arguments to the first step (this reminds me of a Haskell program, which is lazily 'evaluated'). Stepper also exposes two functions, implementationToProcedure and procedureToImplementation. procedureToImplementation can be called on the first element of the tuple to transform it into a function; that function can then be applied to the rest of the tuple to move forward a step in the computation.

implementationToProcedure can be used to define procedures "by specifying their step-by-step behavior in terms of tuples". For example, call/cc is implemented in terms of manipulating the continuation in the tuple.

internally, procedureToImplementation and implementationToProcedure are basically just tags/wrappers; they just help keep the level of things straight.

but they do allow the implementation of call/cc by going 'outside' the context of the executing program.

this is not much more useful that call/cc in the context of that paper (the other useful things it does are (a) allow you to write a step-until debugging function, and (b) allow you to define a procedure to be run one level up the infinite tower, and have it be exposed to the current level as an atomic instruction), but it does seem interesting.

he notes that two other meta things that he left out was reification of expressions, and reification of the environment. he left those out to prove that he could do an infinite tower just with this.

this is some serious meta. i guess if you had this you'd have all the meta you'd ever need. it may be too much though!

---

need a way to optionally pass the current (lexical scoping local variables) environment into an eval

(if the env is first class that's pretty easy)

--

" Current Lisp dialects, among which Scheme and Common Lisp are the most widely used ones, typically provide only restricted subsets of structural re ec- tion: Scheme's eval and Common Lisp's eval and compile can be used to turn a quoted lambda expression into a function (similar to down ), but they can- not be enclosed in arbitrary lexical environments, only in global or statically 11 In Lisp 1.5, only one such environment exists. prede ned environments. There is also typically no construct corresponding to up available that would allow retrieving the original de nition of a function. In terms of procedural re ection, neither Scheme nor Common Lisp allow de ning functions that receive unevaluated arguments as program text, neither Scheme nor Common Lisp specify operators for reifying lexical environments, and only Scheme provides call/cc for reifying the current continuation. Macros were in- troduced into Lisp 1.5 in the 1960's [11], and are considered to be an acceptable and generally preferrable subset of re ecting on source code [12]. The di erence in that regard to re ective procedures, fexpr , and so on, is that macros cannot be passed around as rst-class values and are typically restricted from access- ing runtime values during macro expansion. This allows compiling them away before execution in compiled systems, as is mandated for example by current Scheme and ANSI Common Lisp speci cations [13, 14]. Useful applications of rst-class lexical environments in Scheme have been described in the literature [15, 16], but the only Scheme implementation that seems to fully support rst- class environments at the time of writing this paper is Guile, and the only Lisp implementation that seems to do so is clisp in interpreted mode. 12 "

suggests:

first-class macros, first-class reified continuations, first-class reified environments, "functions that receive unevaluated arguments as program text", macros that can access runtime environments (current local variables) during macro expansion, a construct 'up' that "would allow retrieving the original definition of a function"

---

http://en.wikipedia.org/wiki/Vienna_Development_Method

---

coroutines, for when fully preemptive multitasking isn't available or is too slow

---

keeping covariance vs contravariance straight:

covariant X means that when you move DOWN to a subtype, the type of X also moves DOWN to a subtype

contravariant X means that when you move DOWN to a subtype, the type of X moves UP to a supertype

e.g. contravariant argument types and covariant return types mean that a subtype must be at least as permissive in what it accepts as the superclass, and at least as constrained in what it emits

times when this stuff comes up:

• a subtype method must be at least as permissive in what it accepts as the superclass, and at least as constrained in what it emits; so it must be contravariant in its arguments and covariant in its return types
• writing to a container, you may only write things that are subtypes of the container's value type; but reading from a container, you may only assume that the value you get will be a supertype of the container's value type. since we think of this in terms of casting the container's value type (rather than casting the value to be read/written), writing to a container is contravariant (you can only pretend that the container's value type is a superclass of what it actually is), and reading from a container is covariant (u can only pretend that the container's value type is a subclass of what it actually i).

---

forwhile loop (my idea)