TLghc version 0.6.0.0
The interpreter (https://github.com/plaice/TLghc) has been updated, with some refactoring of code. The evaluator now stores intensions, and corresponds to the paper.
Recent Updates Toggle Comment Threads | Keyboard Shortcuts
-
cartesianprogramming
-
cartesianprogramming
TransLucid: Higher-order Indexical ISWIM
The paper presenting TransLucid and its semantics is now ready: TransLucid: Higher-order Indexical ISWIM
-
cartesianprogramming
TLghc 0.5.0.0: Working interpreter with many examples.
The TransLucid interpreter, available at https://github.com/plaice/TLghc, has been significantly improved for version 0.5.0.0. The test suite contains a number of examples, found at https://github.com/plaice/TLghc/tree/master/test/tl. For each of those example files, there is an output file at https://github.com/plaice/TLghc/tree/master/test/out.
-
cartesianprogramming
Cartesian Programming with TransLucid
Talk I gave to the Lambda Montreal Meetup group on 11 March 2020.
Slides: lambda-montreal-2020-03-11 -
cartesianprogramming
The TransLucid interpreter is now ready for experimentation
The TransLucid interpreter, available at https://github.com/plaice/TLghc, has been significantly improved for version 0.0.3. There is now some documentation, along with an example TransLucid program.
The implementation of higher-order functions has been greatly simplified, and no longer needs the stack of pairs of environment and context that was described in the previous blog post. There is now a single environment and a single context. When a dimensionally abstract function is applied to a set of dimension actual parameters and a set of actual parameters in a given application environment-context pair, then for each actual parameter, a binding is created. This binding holds the actual parameter, the application environment, and the application context, adjusted so that, as the body of the function is evaluated, should any of the dimension formal parameters be perturbed, then the actual parameter will be evaluated with that changed context.
The paper presenting the semantics of TransLucid will soon be ready.
-
cartesianprogramming
The key to higher-order Cartesian programming
In this post, I will outline the implementation of TransLucid functions. In the TransLucid language, multidimensional arrays of dimensionally-abstract functions can manipulate multidimensional arrays. The problem to be solved is that since TransLucid functions are dimensionally abstract and first-class values, the implementation must avoid any clashes in the use of dimensions.
This blog post will not be easy to read, without a clear exposition of the principles of TransLucid. A further blog post will be written giving a proper introduction to the language as it currently stands in the https://github.com/plaice/TLghc implementation. In the meantime, a cursory introduction to TransLucid and Cartesian programming is given in the next few lines.
In TransLucid, a variable is an array of arbitrary rank (number of dimensions) and extent (number of cells). To refer to a specific cell, the variable is accessed using the current context, which is a set of (dimension, ordinate) pairs. This is exactly the idea behind Descartes’ analytical geometry, so it is appropriate to call this style of programming Cartesian programming.
A useful way to visualise Cartesian programming, initially, is to consider a (hypothetical) spreadsheet based on these ideas. The entire spreadsheet could be considered to be a single TransLucid variable, with dimensions such as
row,column,sheetandtime, and possibly many others. One or more equations would define this variable, and these equations could refer, if necessary, to these dimensions to reach neighbouring cells.Our first TransLucid example is the following:
var A = 2*#x + 3*#yVariable
Ais defined to be a two-dimensional array which looks like the following table (here we only consider non-negative ordinates):y/x 0 1 2 3 ... 0 0 2 4 6 ... 1 3 5 7 9 ... 2 6 8 10 12 ... 3 9 11 13 15 ... ...
In this example, the current ordinates for dimensions
xandyare examined explicitly (extensionally). Most of the time, dimensions are manipulated implicitly (intensionally). For example, the Fibonacci series could be defined as follows:var fib = if #d<2 then #d else next.d(fib) + next.d(next.d(fib))where the
nextfunction shifts its actual argument in parentheses one cell “to the left” in the direction of its actual dimension argument. The definition ofnextis as follows:fun next.d(X) = let d <- #d+1 in XThe Fibonacci series could also be written as follows:
var fib = fby.d (0, fby.d (1, fib + next.d fib))where the
fbyfunction starts with the first actual argument in parentheses, and continues with the second actual argument in parentheses, shifted one cell “to the right” in the direction of its actual dimension argument. The definition forfibis as follows:fun fby.d(X,Y) = if #d < 1 then X else let d <- #d-1 in YAssuming a bit of extra support from the parser (not yet implemented), the definition of
fibcould be written as:var fib = 0 fby.d 1 fby.d (fib + next.d fib)And now we can make a
Fibfunction, using a locally-declared dimension:fun Fib(n) = fib where
dim d <- n
var fib = 0 fby.d 1 fby.d (fib + next.d fib)
endTransLucid is a higher-order language, so arrays of functions can also be created. For example, in the following definition,
fun nextN.d(X) = F(X)
where var F = (lambda X -> X) fby.d (lambda X -> next.d (F X)) endthe variable
Fis an array of functions, corresponding toid,next.d,next.d(next.d), and so on. Hence,nextN.d(#d)will give us
#dat the 0-ordinate, i.e., 0,
next.d(#d)at the 1-ordinate, i.e., 2,
next.d(next.d(#d))at the 2-ordinate, i.e., 4,
next.d(next.d(next.d(#d)))at the 3-ordinate, i.e., 6
and so forth.The difficulty in implementing the higher-order functions is that during execution, the context is queried dynamically. As a result, it is crucial to avoid dimension clashes. The potential for this problem can be illustrated with some small examples.
(\lambda() -> #d) ()
should be the same as
#d(\lambda(X) -> #d + X) (#e)
should be the same as
#d + #eSo far, so good. Now, it gets a bit trickier.
(\lambda(X) -> #d + X) (#d + #e)
should be the same as
#d + (#d + #e)That seems fine. But what if we fix the
d-ordinate inside thelambda?(let d <- 3 in (\lambda(X) -> #d + X)) (#d + #e)
should be the same as
3 + (#d + #e)So it becomes clear that the two occurrences of
#din the previous example are not of the same nature. The first occurrence of#dbelonged to the body of the function, and was subject to the context at the point of abstraction, while the second occurrence of#dbelonged to the actual argument, and was subject to the context at the point of application.Getting all this to work took a long time to understand. Initially, it was thought that a TransLucid expression was evaluated against an environment, mapping identifiers to dimensions, expressions or functions, and a context, mapping dimensions to ordinates. However, this approach fails in function calls, because one cannot distinguish the two different occurrences of
#din the example above.The solution lies in understanding that dimensions in TransLucid play a rôle similar to that of automatic variables do in imperative languages. In those languages, when a function is called, information is placed on the runtime stack, and the automatic variables for the called function are placed on top of the stack. If the TransLucid context is understood to be something akin to the runtime stack in other languages, then the solution becomes clearer.
The Translucid environment and the TransLucid context together form a pair of stacks, one of environment parts, the other of context parts. Each environment part is a mapping from identifiers to dimensions, expressions or functions, while each context part is a mapping from dimensions to ordinates. As a result, in a given context, it becomes possible for the same dimension to be mapped to different ordinates at different levels.
When a function is called, we are combining two contexts: the abstraction context (when the function was created) and the application context (when the function is applied to arguments). If an identifier appearing inside the body of the function does not correspond to any of the formal arguments of the function, then only the abstraction context is of relevance for its evaluation; the application context should have no influence. Should a dimension formal parameter be manipulated inside the body of the function, then the corresponding dimension refers directly to the application context. Should a variable formal parameter be manipulated inside the body of the function, then the relevant context is the application context: the only dimensions that come in from the function call that can be manipulated are those passed in through dimension actual parameters.
When a function is called, the environment stack for the evaluation of the body of the function consists of placing a modified (explained below) version of the environment stack at the point of the application on top of the environment stack at the point of the abstraction. The modification of the top part consists of
- keeping the same depth;
- removing all mappings to variables and functions;
- adding a mapping from formal variable parameters to actual expression parameters;
- for each actual dimension parameter, at the correct level, replacing the mapping from the actual dimension parameter to a mapping from the formal dimension parameter;
- removing all other mappings to dimensions.
The context stack for the evaluation of the body of the function consists of placing the context stack at the point of the application on top of the context stack at the point of the abstraction.
The approach described above ensures that when the body of the function is being evaluated, both the abstraction context and the application context are available. However, the application context can only be manipulated through the formal dimension parameters, which have been judiciously placed in the upper part of the modified environment.
The https://github.com/plaice/TLghc interpreter implements functions as described above. There is ample room for optimisation. For example, most of the TransLucid programs that have been written to date do not take advantage of the abstraction context, so the implementation of function calls in the majority of cases can be simplified. Furthermore, the memoisation of computations, very useful for recursively-defined TransLucid variables, requires the development of a fully-working rank-analysis algorithm.
Given the importance of solving the problem described in this blog post, the release of version 0.0.1 of
TLghcwas warranted. -
cartesianprogramming
New TransLucid interpreter written in Haskell
I just finished version 0.0.1 of a new TransLucid interpreter. It is based on a new semantics for the language, which I will soon post. The interpreter can be found at https://github.com/plaice/TLghc
-
cartesianprogramming
Higher-order Multidimensional Programming
Talk I gave to the Lambda Montreal Meetup group on 7 March 2018.
Slides: lambda-montreal-2018-03-07 -
cartesianprogramming
Static analysis of C++ projects with CodeSonar
Talk I gave to the C++ Montréal Meetup group on 25 July 2017.
Summary: c++-montreal-2017-07-25 -
cartesianprogramming
Release 0.3.1 is out
This release fully supports higher-order functions for TransLucid.
It is available on sourceforge.
TransLucid and Cartesian Programming 
Reply