Lucian

Following a productive week of reading, and an extremely useful meeting with my supervisor on Thursday I have been able to get a lot more direction about where I am going with project and how the dataflow extension is going to work.

My supervisor has managed to (temporarily) prize me away from lazy streams for the moment, which is good. I need to get the extension working eagerly first, and that is going to be the main objective.

I have put together a short document detailing the nature of the dataflow extension I will be developing, and also a revision of my project timetable.

Progress and Timetable Revision 1

The current name for my extension is Lucian (a play on Lucid of course, and in reference to Lucian of Samosata and the artist Lucian Freud).
Here is the description of Lucian taken from the above document:-

The nature of the dataflow extension has been further solidified over this week leading to the creation of this document. The current name I am using to label this extension is Lucian.


    The dataflow extension will take the form of a pre-processor that interprets a dataflow language, L, and outputs source code in a target object orientated language, A. The dataflow language will consist of an abstract syntax for expressing dataflow over objects, and will allow the programmer to reference objects that exist within local source code in the language A.


    For example the programmer writes a class definition for an object X, in the language A, along with supplementary code in the dataflow language L, which describes some dataflow involving X. The Lucian pre-processor then generates all the dataflow code in the OOP language A.


    The Lucian pre-processor will also have the ability to parse source code written in the language A that has embedded dataflow code appropriately delimetered within.


    Hence the Lucian language is a meta-programming language, and the pre-processor acts as the generator to the target language A.


    Initially I will be developing Lucian-R, an implementation of Lucian that outputs source code in the Ruby programming language. Due to planned modularity within the pre-processor the ability to output to any other OOP language, e.g. Java, Smalltalk should be fairly straight forward.

Specification, lack of sleep and crushing my mind with lazy concurrent streams

Completed and handed in the specification document for my project last week. The final document can be found here.

The last week has been extremely busy, and so has the weekend, resulting in tangible work being low, although I have managed to press on with reading the Lucid book as well as spent several hours trying to fathom how to produce an efficient system of lazy concurrent streams.

I've made a few attempts at implementing lazy streams with my Ruby Dataflow Extension, but keep getting stumped at the last minute. In my head it seems easy, but when I sit down at the computer to write code I find myself knee deep in partially applied functions, deadlocks and traps. Extending Ruby to allow currying of functions was a definite help.
Here is the lovely code that lets me hack currying and partial application into Ruby:-

# Code based on "Whys" blog post on functional extensions in Ruby.
class PartialFun < Proc
  def call(*args)by
    if args.size < arity.abs and args.size != -arity - 1
       Fun.new{|*a| call(*(args+a)) }
    else
      super
    end
  end

  alias_method :[], :call
end

# CurryFun constructor wrapper

def CurryFun &block
  PartialFun.new &block
end

# Example function
def curry_foo
 CurryFun{|x, y, z| x+(y*z)}
end

One concept in my head is explainable via the examples now laid out.
Lets take the example:-

x = x fby 1
y = next x

This is all fine and dandy in Lucid, where y will be outputting 1 continually on its stream. Lucid is lazy. In my RDE (Ruby Dataflow Extension), dataflow programming occurs via concurrent nodes on top of threads, not on an eduction model (which I presume Lucid works on), and this concurrent system is eager.
Hence the previous example fails as x is nothing, so 'x fby 1' is left trying to read from x, and 'next x' also sees nothing.

My thought is that if the node 'fby' tries to read from x and does not receive anything, then it outputs on its buffer a closed function that attempts to read from buffer x.
The node then continues as normal and reads 1, and outputs that continually to its output buffer.
The next node reads the "next" item on the output buffer of x, hence skipping over the function on the buffer and reading 1.

However, lets say that we don't have this following program:-

a = some_slow_running_node
x = a fby 1
y = next x
z = x

Taking the model of operation as before, fby may try to read from the output buffer of a, but as a is a slow running node, it doesn't read anything immediately, so flags there is no result yet, or writes out a function. This doesn't matter for y as y only requires next x. However we now have z, which replicates all that is coming from x. If x outputs a function, z could try and apply the function. Lets say that fby didn't read anything from a immediately, so wrote a function onto its output buffer. A function whose operation is to read from a. z would read this function, and could apply it to see if we have a value for a yet. Could this work in a more complex situation? I'm not sure yet.
For example the "howfar" program presented in Section 3 of Wadge's Lucid book:-

howfar
where
howfar = if x eq 0 then 0 else 1 + next howfar fi;
end;

This program calculates how many items there are on the input stream before a 0 is encountered.
E.g. If the input stream to howfar is:-
1, 6, 4, 0, 9, 2, 1, 4, 3, 0, 6...
The output would be:-
3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 1...

With the previous model of passing functions onto streams the expression 1 + next howfar could be rolled into a partially applied function, whose opeartion is 1 + reading the next value of the howfar buffer. More formal reasoning or tests are needed to ascertain if this will be a viable solution to producing concurrent lazy streams.

This does leave me with a nasty taste in my mouth though, it feels like I'm destroying the type system for the streams, as now not only can a stream be of type a, it must also be able to hold functions. Perhaps two streams masquerading as one would be better, one stream presenting the strongly typed item stream, and another subversive counterpart, holding any functions partially applied or not.

I have thought about a request system where results are 'pulled' through the system, with nodes making requests for computation to other nodes, but this destroys the whole joy of having a concurrent data flow network in which some nodes could be operating much faster and could do a lot of useful work while other nodes are taking longer.

The thinking continues, along side getting familiar with Lucid. My objectives for this week are to be researching into GLU and Gypsy, I'm hoping that I can do this at the weekend after much reading of the Lucid book this week.

Information on progress over the summer

This is a quick log of what happened in my research over the summer:-

August 21-28 - Reading ISWIM - The Next 700 languages paper + Reading Lucid book
August 28-30 - Playing with HAPPY, Calc example
Sep 2 - Writing Basic ISWIM Parser in Happy
Sep 3 - Reading Concurrent Haskell paper (getting better at Monadic structures in Haskell, and learning concurrency in Haskell) - (working on printab, bubblesort, and threaded-pow2) Only printab works!
Sep 5 - Bubblesort fixed and working
Sep 6 - Threaded pow2 working - Reading Luswim chapter in lucid book + begining work on basic luswim/lucid parser generator, writing LucidNodes module
Sep 9 - Research into ruby threading
Sep 10 - More ruby threading research, writing data flow mixin library
Sep 18 - Working on Ruby threading again
Sep 19 - Got basic 1.fby 2 example working, struggling to get self referential forms working .e.g. i = 1.fby 2.times i working, starting to get the feeling exact lucid will not be possible in this fashion in Ruby directly without writing C extensions
Sep 20 - Self refential and cross variable referencing works! Plus support for finite operations with termination, and list, and strings (whoohoo!)
Sep 21-29 - Finishing off the Ruby Dataflow Extension that uses Eager Streams
Oct 5 - Developing example of Concurrent Lazy Streams on paper

That brings us up to now, this weekend I have poked at a few dataflow papers that I will read later. Have also been mulling over concurrent lazy streams in my head.... Might start trying some code tonight.

Introduction

This blog tracks the progress of my 3rd year undergraduate Computer Science project at Warwick University.
This is the current project abstract

Research and development for integrating data-flow programming into modern programming, such as integration into functional/object-orientated paradigms. Including additional work involving the exploration of data-flow programming in the context of graphical development and programming for distributed environments.