lethevert should not be capitalized

Clean: Hashtable and Heap

2007-09-17T23:30:00.000+09:00

I implemented hashtables and heaps in clean.
Hashtables are data structures to store pairs of keys and values and to search values with given keys in a efficient way.
Heaps are data structures to store values and retrieve them in a decreasing (or increasing) order.
Both data structures have unique types because they are imperative data structures
repository: https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/AltEnv/Data/

Clean : PartialReader

2007-09-08T21:24:00.000+09:00

I created PartialReader module using Reference type.
https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/AltEnv/IO/

The following program is a program which read each line from a given file and write the first 10 lines to standard output.

module Test
extension for-notation

import File, StdIO, List, System

Start w
  = for w
      ? Pass f <- openFileReader path
      out <- stdio
      (ls,f) = readLines f
      out = loop 1 (take 10 ls) out
      ? PassV <- close out
      ? PassV <- close f
      return
    except (Fail msg)
      return
  where
    path = getCommandLine.[1]

loop n [] out = out
loop n [a:aa] out
  = for out
      ? PassV <- write n $> write " => " $> writeln a
      continue loop (n + 1) aa
    except (Fail msg)
      return

This program works well for a small file. It reads one line, writes the line and repeats the process 10 times. In favor of lazy evaluation strategy, it uses no more memory than to hold only one line.
However, it is not suitable for a large file because it reads not only the first 10 lines but also all of the remaining lines before closing the file handle. PartialReader module is a solution for the problem.
PartialReader module internally uses Reference module and separates a reader handle and a close handle out of the given input stream. The new reader handle is used only for reading bytes and the new close handle only for closing the handle.
PartialReader module defines a useful function 'partialReadLines' that takes an input stream and returns all the lines of the stream and a close handle of the stream. Because both of the return values are lazy ones, unnecessary read actions does not take place.

Start w
  = for w
      ? Pass f <- openFileReader path
      out <- stdio
      (ls,f) = partialReadLines f // <- change only this line and unnecessary read actions will not take place.
      out = loop 1 (take 10 ls) out
      ? PassV <- close out
      ? PassV <- close f
      return
    except (Fail msg)
      return

Clean: Alternative Environment

2007-09-06T09:09:00.000+09:00

I am now working on creating AltEnv library which redefines StdEnv and other libraries so that we can use Clean in some smarter way.

Most of basic value operations are inherited directly from StdEnv. So is Maybe type.
List functions are redefined so that lazy list and strict lists can be manipulated in the same functions.
I defined deque operations and integrate operations for list and array in the same type classes.
Functions of standard IO and file IO are redefined. In the original version those handles are all of the same type but I think the types of those handles should be distinguished and I redefined them in the way.

You can get the library in the subverson repository: https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/AltEnv/

Clean: Finger trees and String2

2007-08-19T21:12:00.000+09:00

I made an implementation of Finger trees algorithm in Clean.
Finger trees are persistent sequence data structures which support access to the ends in amortized constant time and concatenation and splitting in time logarithmic in the size of the smaller piece. see http://www.soi.city.ac.uk/~ross/papers/FingerTree.html.

As an application I also made an alternative implementation for string representation. Its performance of manipulating ordinary size strings is only 1.5 to 2 times slower than that of arrays of chars and that for long strings much more efficient.
The idea of creating an efficient string representation for long strings is inspired by the ICFP contest 2007.

FinterTree module is available at https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/AltEnv/Data/.
String2 module is available at https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/AltEnv/Text/.

Clean : for-notation

2007-08-12T21:37:00.000+09:00

A new extension for CleanX was released. It is for-notation extension.
The extension helps writing programs with unique typing.

Here is a sample program.

hello f =
    for f
      fwrites "your name? "
      s <- freadline
      s = chop s
      fwrites "Hello, " $> s $> newline
      return

This program will be interpreted as the following.

hello f # f = f |> fwrites "your name? "
          (s,f) = f |> freadline
          s = chop s
          f = f |> fwrites "Hello, " $> s $> newline
        = f

See more details at the site: installation of CleanX, features of for-notation

Wrong subversion repository url

2007-08-01T23:14:00.000+09:00

The url I previously wrote in this blog as my subversion repository url was found wrong.
The correct one is https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv.

Clean Wiki

2007-07-31T00:04:00.000+09:00

I posted several issues to Clean Wiki these days.

Installation

Usage of CleanX

Clean Wiki

2007-07-01T14:13:00.000+09:00

I opened a Clean Wiki site which I will accumulate some information related to Clean. Perhaps some will be in Japanese and others in English.
http://cleanoptenv.sourceforge.jp/wiki/
This site is written in Clean. I created some libraries for this purpose, such as

CGI parser
SQLite3 Binding
MySQL5.0 Binding
HTML templating preprocessor

All those libraries are available from my subversion repository.
https://svn.sourceforge.net/svnroot/cleanoptenv
Using HTML templating preprocessor, I can write HTML tags within Clean programs. A sample code below;

vTitles :: ![TitleInfo] -> HtmlData
vTitles tis = body $ HtmlData $ map (\{ti_title} = title ti_title) tis
  where
    body data =
        __HTMLSTART__
        <div id="sidebar">
        <% data %>
        </div>
        __HTMLEND__

    title t = let urlTitle = mkUrlTitle t in
        __HTMLSTART__
        <a href="<% ROOT %>view/<% urlTitle %>"><% HtmlText t %></a><br />
        __HTMLEND__

It makes the code much easier to write, read and maintenance.
I am thinking that such and other syntactic transformation via preprocessing will enables programming much easier. I create CleanX preprocessing framework for this purpose.

Concurrent Clean: Unique Typing, Covariance, Contravariance, and Abstract Type

2007-06-04T23:11:00.000+09:00

We must keep in mind that covariance/contravariance matters are along with unique typing in function types.
Let us think about the following code:

::R a b :== .(a -> b)

createR :: *Char -> *(R Int *Char)
createR c = (\i = c)

f :: u:(R Int *Char) -> u:(R *Int Char)
f r = r

Start = f (createR 'a')

You should look at the type of function 'f' which indicates the covariance of function parameters.
That is why unique abstract type cannot be coerced into non-uniqueness. Look at the following code:

::R

createR :: Int -> *R

f :: *R -> R
f r = r

Start = f (createR 1)

The code is not valid because there are no information deciding whether the abstract type R is covariant or contravariant.

MySQL binding is ready!

2007-05-01T22:56:00.000+09:00

I finished my first work of making MySQL binding. It supports simple operation for MySQL database.
You can get it from subversion repository at https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk. You need to download DB/MySQL as well as OptEnv.
I show a sample program below.

Main.icl

module Main

import MySQL, StdDebug

Start w # (mConn,w) = MySQLOpen host port db user pass [] w
        = case mConn of
            Fail e = trace_n e w
            Pass conn
              # (mStmt,conn) = sqlOpenStatement sql [] conn
                conn = case mStmt of
                         Fail e = trace_n e conn
                         Pass stmt
                           # stmt = run stmt
                             (mErr,conn) = sqlCloseStatement stmt conn
                           = case mErr of
                               Nothing = conn
                               Just e  = trace_n e conn
                (mErr,w) = sqlClose conn w
              = case mErr of
                  Nothing = w
                  Just e  = trace_n e w
  where
    host = "localhost"
    port = 0
    db   = "cleanoptenv"
    user = "lethevert"
    pass = "lethevert"
    sql = "SELECT * FROM TBL1 WHERE STR = ? AND NUM = ?"
    run stmt
        # (mErr,stmt) = sqlBind [SQL_TEXT "Hello", SQL_INT 1] stmt
        = case mErr of
            Just e = trace_n e stmt
            Nothing
              # (mErr,stmt) = sqlQuery stmt
              = case mErr of
                  Just e = trace_n e stmt
                  Nothing
                    # (cols,stmt) = sqlColumns stmt
                      stmt = showCols (size cols) cols stmt
                    = each stmt
    showCols :: !Int !{!String} !*MySQLStmt -> *MySQLStmt
    showCols 0 cols stmt = stmt
    showCols idx cols stmt = let nidx = dec idx
                             in showCols nidx cols (trace_n cols.[nidx] stmt)
    each :: !*MySQLStmt -> *MySQLStmt
    each stmt
        # (mNext,stmt) = sqlFetch stmt
        = case mNext of
            Fail e = trace_n e stmt
            Pass False = stmt
            Pass True # (mData,stmt) = sqlResults stmt
                      = case mData of
                          Fail e = trace_n e stmt
                          Pass data # stmt = showResults (size data) data stmt
                                    = each stmt
    showResults 0 data stmt = stmt
    showResults idx data stmt = let nidx = dec idx
                                in showResults nidx data (trace_n data.[nidx] stmt)

mysql.lo

-lmysqlclient

To compile the program, enter the following command:

clm -sl mysql Main -o Main

Concurrent Clean : Reference Type

2007-04-27T22:05:00.000+09:00

Two days ago I was thinking about how to implement lazy IO in general way. I worked out the code below;

    # (ls,inF) = readlines inF
      outF = writelines (take 10 ls) outF

It is sure that this program's input and output are performed in turn. But it has a problem. When closing inF file handle, the remaining input actions will be performed, and it is very inefficient if the input file is very long.
If I change the structure of the program I can achieve disirable characteristics but it reduces the virtue of pure functional programing style.
The reference type is the solution, which I finally reached. The combination of pure functional programming and reference type seems paradoxical but Clean's uniqueness typing enables it.
Reference type has three characteristics;

its value is updated according not to lexical order but to runtime order
it can be copied but not shared
its value is accessed safely in semantics with uniqueness type

The data type is an abstract data type.

::*Ref a

The basic operaions include

refer :: !.a -> *(Ref .a)
copy :: !*(Ref .a) -> (!*(Ref .a), !*(Ref .a))
apply :: !.(.a -> .a) !*(Ref .a) -> *(Ref .a)
access :: !.(.a -> (.b,.a)) !*(Ref .a) -> (!.b, !*(Ref .a))

The program below is a sample of coroutine communicating each other using reference type.

Start w
    # (ri1,ri2) = copy (refer 1)
      ls1 = process 1 ri1
      ls2 = process 2 ri2
      ls = interleave ls1 ls2
    = take 10 ls

process a ri
    # (e,ri) = access f ri
    = [e:process a ri]
  where
    f i = (i,i+a)

interleave [a:aa] bb
    = [a:interleave bb aa]

It produces

[1,2,4,5,7,8,10,11,13,14]

The module of the reference type implementation is OptReference, which is found in the subversion repository at https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/OptEnv.

Concurrent Clean : CGI test

2007-03-21T19:54:00.000+09:00

I am trying to create CGI by Clean.
I succeeded receiving CGI parameters from web pages.
These are samples:

GET method: http://cleanoptenv.sourceforge.jp/form/
POST method: http://cleanoptenv.sourceforge.jp/formpost/

Concurrent Clean : not to wait at the end of the execution of Clean program

2007-03-04T14:46:00.000+09:00

use this patch file.

--- wcon.c 2006-06-07 19:06:02.000000000 +0900
+++ wcon.c.new 2007-03-04 14:34:24.000000000 +0900
@@ -1723,11 +1723,11 @@
 
 #ifdef WINDOWS
 # if 1
- if ( (!(flags & NO_RESULT_MASK) || (flags & SHOW_EXECUTION_TIME_MASK) || execution_aborted || (console_window_visible && !console_allocated) ) && !console_flag)
+// if ( (!(flags & NO_RESULT_MASK) || (flags & SHOW_EXECUTION_TIME_MASK) || execution_aborted || (console_window_visible && !console_allocated) ) && !console_flag)
 # else
- if ( (!(flags & NO_RESULT_MASK) || (flags & SHOW_EXECUTION_TIME_MASK) || execution_aborted) && !console_flag)
+// if ( (!(flags & NO_RESULT_MASK) || (flags & SHOW_EXECUTION_TIME_MASK) || execution_aborted) && !console_flag)
 # endif
-  wait_for_key_press();
+//  wait_for_key_press();
 
  if (std_output_to_file)
   flush_file_buffer (&file_table[1]);

and execute 'build_windows_object_files.sh.'
Not to use makefile, which is broken.

'Practical Random Number Generation in Software'

2006-12-13T08:17:00.000+09:00

http://www.acsac.org/2003/abstracts/79.html

The paper proposes solutions to many of the issues that real software-based random number infrastructures have encountered. It includes two main chapters: 4.PRGN Design and 5.Entropy Harvester Design.

The 4th chapter 'PRNG Design' consists of 3 sections.

The first section of the 4th chapter describes how to reseed a PRNG (pseudo-random number generator). There are two type of reseeding used and each has its own reason. The first type of reseed is called an external reseed whereas the second is called a self-reseed named for the origins of their seed.

The second section alerts the danger of careless usage of fork() function. It also prescribes how to design a library to avoid such a danger.

The third section discusses how to initialize PRNG safely. Some devices can be provided some entropy by users in setup time while others cannot.

The 5th chapter 'Entropy Harvester Design' consists of 4 sections.

The first section of the 5th chapter discusses various hash functions to whitening entropy before seeding to PRNG. It introduces a non-cryptgraphic hash function, hash127, which can also be useful for the purpose.

The second section discusses about entropy estimation. First it points out some problems existing entropy estimators have. Then it discusses the usage of a general-purpose compression function for getting an upper bound on the amount of entropy. Finally it describes some aspects on how to use entropy estimators.

The third section argues how to combine multiple entropy sources to seed PRNG.

The forth section lists other considerations about entropy infrastructures.

'Computing ε-Free NFA from Regular Expressions in O(n log^2(n)) Time'

2006-12-11T08:30:00.000+09:00

http://citeseer.ist.psu.edu/471736.html

This paper shows a sequential algorithm to convert a regular expression of size n to an equivalent ε-free NFA of size O(n log^2(n)) in time O(n log(n) + size of the output) while the previous algorithm takes roughly cubic time. It also shows a paralell algorithm performed in time O(log(n)) using O(n + (size of the output)/log(n)) processors.

'Translating Regular Expressions into Small ε-Free Nondeterministic Finit Automata'

2006-12-11T07:47:00.000+09:00

http://citeseer.ist.psu.edu/hromkovic97translating.html

This paper shows how to convert a regular expression of size n to an equivalent NFA of size O(n(log n)^2) in polynomial time. It also shows this construction is almost optimal by proving a lower bound of Ω(n log n) for a regular expression defined by (a1+ε)(a2+ε)...(aN+ε).

The starting point of this construction is what is called 'position automaton' and this new system is called 'common follow sets automaton.' The idea behind is to decompose the follow set of each position into some subsets. These subsets become the state of this automaton. The common use of subsets in the decomposition of different follow sets will give the desired complexity bounds.

'Modern Information Retrieval' (2)

2006-11-28T08:58:00.000+09:00

http://www.ischool.berkeley.edu/~hearst/irbook/

I have read chapter 6 and 7.

Chapter 6 is rather a short chapter which includes metadata, entropy, text model, similarity model, markup languages (including sgml, html, xml) and multimedia formats.

Chapter 7 introduces text operations. The contents are devided mainly into 2 part: document preprocessing and text compression. There are 5 operations illustrated related to document preprocessing: lexical analysis, stopwords, stemming, indexing and thesauri. The methods of text compressions are devided mainly into 3 part: statistical methods, dictionary methods and inverted file compression.

'Towards a Strongly Typed Functional Operating System'

2006-11-16T07:52:00.000+09:00

http://citeseer.ist.psu.edu/642407.html

Famke is presented in this paper. It is a library for Clean that creates and manages threads and processes on a network of computers and communicates between them in a type sefe manner. Finally an interactive shell is introduced, which uses a functional-style command language and it type-checks the command line before performing it.

Clean has a dynamic type system in addition to its static type system. It provides a type pattern and a run-time unification which helps communicating between different processes sometimes on different machines and reading and writing a file in a type safe manner.

Though Clean has no feature to handle threads, Famke succeeds to implement threads using continuation. The implementation uses a cooperative scheduling and programs should explicitly yield. Then some monadic combinators are defined to hide an explicit yields in functions of return, >>= and >>.

A program using threads or processes may fail because of external conditions. Exception is an elegant solution to deal with such errors. Though there is no exception handling mechanism in Clean, the thread implementation above can easily extend to include exceptions by adding another continuation to handle exceptional state. In addition exceptions are implemented with dynamics to deal with any type of error state in the same expression.

Signals are also introduced for throwing and catching exceptions between different threads.

Preemptive processes are implemented using Windows processes. A process can have multiple threads inside. Ports are introduced to communicate between processes. In contrast with M-vars and channels, ports have only one reader, the thread that create the port, and the restriction lowers complexity of administration and implementation. The actual sending/receiving of messages is done via Windows using the mail slot interface.

Finally a shell is provided to interact with Famke library. It includes functional style commands, type safe redirection and interactive thread/process interfaces.

----
P.S.
The shell implementation reminds me of the interactive shell of Erlang.

CGI by Clean

2006-11-12T23:48:00.000+09:00

I made some CGI programs in Clean.

show environment variables
http://cleanoptenv.sourceforge.net/query/1?query=1

counter
http://cleanoptenv.sourceforge.net/count/

Optional Libraries and Preprocessors for Clean

2006-11-08T22:44:00.000+09:00

Some libraries and preprocessors I made was published as 'Optional Libraries and Preprocessors for Clean' in the site http://sourceforge.net/projects/cleanoptenv.

It includes some text operation functions, a regular expression library, a html templating preprocessor and the like. I am planning to build a wiki-like CMS web application and on the way libraries and preprocessors I make will be added to the site.

'Modern Information Retrieval' (1)

2006-11-08T22:18:00.000+09:00

I am reading a book on information retrieval. What I choosed is http://www.ischool.berkeley.edu/~hearst/irbook/. It is an elementary book presenting an over view of research in IR from a computer scientist's prespective.

I have read chapter 1 thru 5.

Chapter 1 overviews the research field and the contents of the book.

Chapter 2 classifies models of IR system and describes characteristics of each model. The models are 3 classic models (boolean, vector, probabilistic) and 6 alternative models (fuzzy, extended boolean, generalized vector, latent semantic index, neural networks, inference network, belief network) and 2 structured models (non-overlapping lists, proximal nodes) and 3 browsing models (flat, structure guided, hypertext).

Chapter 3 discusses retrieval performance evaluation and covers some test collections.

Chapter 4 classifies query languages. It covers 4 keyword based querying (single-word, context, boolean, natural language) and pattern matching and 3 structural queries (fixed, hypertext, hierarchical).

Chapter 5 discusses query operations which is a combination of two strategies: term weighting and query expansion. Approaches are grouped in 3 categories: user relevance feedback, local analysis and global analysis.

a document for ABC machine instructions

2006-10-25T22:52:00.000+09:00

I have written a document for ABC machine instructions.
http://cleanj.sourceforge.net/abc_inst.html
The document does not describe all the instructions but it is enough to develop such a program as CleanJ.

What does this program means?

2006-10-16T23:30:00.000+09:00

This program can be compiled. But what does this means?

module Synonym

import StdEnv

::Number a | Arith a :== a

Start :: Number String
Start = "aaa"

This is also.

module TypeDef

import StdEnv

::Number a | Arith a = Number a

Start :: Number String
Start = Number "aaa"

generic function for unboxed array

2006-10-15T16:16:00.000+09:00

This is a sample program of generic function for unboxed array:

generic gEq a :: a a -> Bool
gEq{|Int|} a b = a == b
gEq{|Real|} a b = a == b
gEq{|Char|} a b = a == b
gEq{|Bool|} a b = a == b
gEq{|{#}|} f aa bb = eqArray f aa bb

eqArray f aa bb :== sa==sb && eqArray (dec sa)
  where
    sa = size aa
    sb = size bb

    eqArray 0 = f aa.[0] bb.[0]
    eqArray i | f aa.[i] bb.[i] = eqArray (dec i)
    eqArray _ = False

But this program brings compile error.

Overloading error [Eq.icl,22,gEq__#Array]: internal overloading of "size" could not be solved

It is because size function for each unboxed array is separate definition and type specification is needed to identify the corresponding definition. Then the plausible program:

gEq{|{#Int}|} f aa bb = eqArray f aa bb
gEq{|{#Char}|} f aa bb = eqArray f aa bb
gEq{|{#Real}|} f aa bb = eqArray f aa bb
gEq{|{#Bool}|} f aa bb = eqArray f aa bb

will leads to the error:

Parse error [Eq.icl,23:11,generic type, no constructor arguments allowd]:  |} expected

But this is only a syntax matter. To get off this problem the program should be modified as follows:

::IntArray :== {#Int}
::RealArray :== {#Real}
::BoolArray :== {#Bool}

generic gEq a :: a a -> Bool
gEq{|String|} aa bb = eqArray (==) aa bb
gEq{|IntArray|} aa bb = eqArray (==) aa bb
gEq{|RealArray|} aa bb = eqArray (==) aa bb
gEq{|BoolArray|} aa bb = eqArray (==) aa bb

Re: Verious Types

2006-10-15T15:54:00.000+09:00

Map function for Fix type constructor:

module Recursive

::Fix f = In (f (Fix f))
::ListBase a b = NilL | ConsL a b
::List a :== Fix (ListBase a)

mapListBase :: A.a1 a2 b1 b2: (a1 -> a2) (b1 -> b2) (ListBase a1 b1) -> ListBase a2 b2
mapListBase mapa mapb NilL = NilL
mapListBase mapa mapb (ConsL a b) = ConsL (mapa a) (mapb b)

mapFix :: A.f1 f2: (A.a1 a2: (a1 -> a2) -> (f1 a1) -> (f2 a2)) (Fix f1) -> Fix f2
mapFix mapf (In v) = In (mapf (mapFix mapf) v)

mapList :: A.a1 a2: (a1 -> a2) -> ((List a1) -> (List a2))
mapList mapa = mapFix (mapListBase mapa)

add :: !Int !Int -> Int
add a b
    = code inline {
        addI
    }

Start :: (List Int, List Int)
Start = (ls, mapList (add 1) ls)
  where
    ls = In (ConsL 2 (In (ConsL 3 (In (ConsL 5 (In NilL))))))

This sample shows that Clean 2.1.1 has a support for Rank-2 polymorphism.

'Haskell on a Shared-Memory Multiprocessor'

2006-10-14T16:37:00.000+09:00

http://research.microsoft.com/~simonpj/papers/parallel/index.htm

This paper explains how to modify present implementation of GHC which targets an uniprocessor system (Uni-GHC) for a shared-memory multiprocessor system (SMP-GHC), and shows how the performance of the SMP-GHC implementation is.

Threading model in Uni-GHC is, roughly speeking, that many Haskell threads running on a single OS thread, called a worker-thread. Since each Haskell thread is switched by a worker thread at a carefully controlled point, any racing condition of updating thunks occurs.

SMP-GHC creates multiple worker thread to run Haskell code in parallel on separate CPUs and some racing conditions of updating thunks occur. If every thunk is locked to guard thunks from the racing condition, the performance becomes lower and the performance merit of multiprocessor system vanishes.

Instead of locking thunks the approach this paper adopted is evaluating thunks with no locking instructions whatsoever. The key idea is that since a thunk always represents a pure expression it does not matter if two threads evaluate the same thunk. Two points are needed to consider.

The first thing is to ensure that if two threads succeed in entering the same thunk, they do not trip over each other. Thinking about the situation that thread A and thread B simultaneously evaluating the same thunk, it will go wrong if the evaluation will proceed as the following: thread B reads the entry code; thread A reads the entry code; thread A reads the arguments; thread A evaluates the thunk; thread A writes the result; thread B reads the arguments. In the last step thread B will read the result of evaluation of thread A. The solution to this race condition is to separate the memory area for arguments and that for a result.

The second problem occurs if one thread reads a thunk just as another thread is updating it. Thinking about the following process: Thread A writes an end mark in the header of the thunk; Thread B reads the header of the thunk and thinks that the thunk is already evaluated; Thread B tries to read the result but thread A has not write the result yet. If a hardware guarantees the order of instruction this problem is solved by writing a result before an end mark. Otherwise a memory fence is needed before executing update code for thunk.

To run Haskell code on SMP machine the ideas above are sufficient but there are aditional ideas for avoiding a duplicate evalutation of an expensive thunk.

One of these ideas is black-holing. The basic idea is that after starting evaluation of a thunk the thread 'claims the thunk' to gain exclusive access to the thunk. If the thunk is already claimed by another thread the thread will blocked until the evaluating thread completes the evaluation of the thunk. After the evaluation is over the stack of the blocked thread will be truncated to skip the evaluation of the thunk.

Another idea is Grey-holing, where a thread claims the thunk just when entering the thunk without locking.

The STM implementation on SMP system is also described. The basic idea is to implement per-TVar locks using atomic CAS instructions.

To measure the efficiency of the implementation, 88 programs of nofib benchmark suite and GHC itself with --make option are used. The result is satisfactory.

Verious Types

2006-10-12T23:22:00.000+09:00

Follow chapter 1 of the paper of 'Generic haskell: practice and theory' (2003) in the site http://www.cs.uu.nl/~johanj/publications/publications.html.

First, generic Rose type:

module GRose

::GRose f a = GBranch a (f (GRose f a))
::Rose a :== GRose [] a

Start :: Rose Int
Start = GBranch 1 [GBranch 2 [], GBranch 3 [GBranch 4 []]]

Second, recursive type:

module Recursive

::Fix f = In (f (Fix f))
::ListBase a b = NilL | ConsL a b
::List a :== Fix (ListBase a)

Start :: List Int
Start = In (ConsL 2 (In (ConsL 3 (In (ConsL 5 (In NilL)))))

Third, a linear nested type of Perfect type:

module Perfect

::Fork a = Fork a a
::Perfect a = ZeroP a | SuccP (Perfect (Fork a))

Start :: Perfect Int
Start = SuccP (SuccP (SuccP (ZeroP (Fork (Fork (Fork 2 3)
                                               (Fork 5 7))
                                         (Fork (Fork 11 13)
                                               (Fork 17 19))))))

Fourth, another linear nested type of Okasaki's binary random-access liss:

module Sequ

::Fork a = Fork a a
::Sequ a = EndS
         | ZeroS (Sequ (Fork a))
         | OneS a (Sequ (Fork a))

Start :: Sequ Int
Start = ZeroS (OneS (Fork 2 3) (OneS (Fork (Fork 5 7) (Fork 11 13)) EndS))

Fifth, a non-linear nested type:

module Bush

::Bush a = NilB | ConsB a (Bush (Bush a))

Start :: Bush Int
Start = ConsB 1 (ConsB (ConsB 2 NilB)
                (ConsB (ConsB (ConsB 3 NilB) NilB) NilB))

Re: SQLite3 binding for Clean

2006-10-11T00:00:00.000+09:00

Now the package is available here: http://sourceforge.net/project/showfiles.php?group_id=179225
Suversion repository can be browsed here: http://svn.sourceforge.net/viewvc/cleansqlite/trunk/
It is distributed under the modified BSD license.

Re: SQLite3 binding for Clean

2006-10-09T23:16:00.000+09:00

I have finished my first attempt to make SQLite3 binding for Clean. This is for Windows Environment but It can be ported to other OS with a little work.
I applied a new project to sourceforge.net and soon I will register the package there.

This is a sample application:

Start w # (c,w) = sql_open "db" w
          (s,c) = sql_connection_status c
        | s <> SQL_OK = trace (toString s +++ "\n") ({},[],w)
        # (mst,c) = sql_prepare "SELECT i,r,t FROM tbl1" c
          (nml,rsl,c) = case mst of
                          Nothing # (st,c) = sql_connection_status c
                                  = trace (toString st +++ "\n") ({},[],c)
                          Just st # (nml,st) = sql_column_names st
                                    (rsl,st) = each st
                                    c = sql_finalize st c
                                  = (nml,rsl,c)
          w = sql_close c w
        = (nml,rsl,w)
  where
    each st # st = sql_step st
              (mrs,st) = sql_column_values st
            = case mrs of
                Nothing = ([],st)
                Just rs # (rsl,st) = each st
                        = ([rs:rsl],st)

SQLite3 binding for Clean

2006-10-08T22:17:00.000+09:00

I am trying to make SQLite3 binding for Clean now. So, what happend to your plan to write document of ABC machine instruction?
Well well...

Re: deepSeq

2006-10-07T15:31:00.000+09:00

Previously I shown my deepSeq function implementation, but I made an error in it.

I previously write:

gDeepSeq {|{}|}     f     a            w = seqArray f a w
gDeepSeq {|{!}|}    f     a            w = (a,w)
gDeepSeq {|{#}|}    f     a            w = (a,w)

But to think of a strict array of a record with lazy field, this deepSeq function will not work correctly. I should write instead:

gDeepSeq {|{}|}     f     a            w = seqArray f a w
gDeepSeq {|{!}|}    f     a            w = seqArray f a w
gDeepSeq {|{#}|}    f     a            w = seqArray f a w

Transaction

2006-10-06T22:40:00.000+09:00

I devised a function bridging unique type variables and lazy data structures. Transaction is a name I gave to the function. I am not sure the name is appropriate.

Unique type is good to describe an ordered process but is not convenient to combine with list manipulation function or the like. Transaction function is a solution for the problem.

Transaction.icl

definition module Transaction

import DeepSeq

transaction
    generator
    reducer
    unique
    world
    :== transaction world
  where
    transaction world
        # (unique1, unique2) = double unique
          (result, world) = reducer (generator unique1) world
          (result, world) = deepSeq result world
        = (result, unique2, world)

    double :: *v -> *(*v,*v)
    double v
        = code {
            push_a 0
        }

This function is based on the fact that unique type variable is not usually copied but updated imperatively through the whole process.
Double function is a magic function; it takes a pointer to a thunk and return two copy of it. The two copy of the pointer share the same thunk. Then one is passed to the generator function and generator function produces a lazy structure of read data from it. Reducer will reduce the input and return a final value which may contain a lazy thunks related to the original input unique type variable.
DeepSeq function is applied to the final value to sweep out the unevaluated thunks related to the first copy of the unique variable. After that the second copy of the unique variable is returned with the final result of reduce function.

This is an example with Parser Library for parsing a s-expression style text. The Parser Library of Clean needs input data to be in lazy list type. It is not applicable to the File type of Clean I/O library. Then transaction function is usefull for bridging them.

module ParseExpr

import StdEnv, OptEnv, Parsers, Tran2

Start :: *World -> ([(Tree String)],*World)
Start w
    # (f, w) = stdio w
      (r, f, w) = w --> transaction gen_input parse_input f
      (_, w) = trace "fclose" $ fclose f w
    = (r,w)

gen_input f
    # (_,c,f) = trace "freadc" $ freadc f
    = [c:gen_input f]

parse_input input w
    = case parse (first sexpr) input "" "" of
        (Succ ls) = (ls,w)
        _         = ([],w)

sexpr =  symbol '(' &> list <& symbol ')' <@ (\tt = B tt)
     <|> atom                             <@ (\t  = L t )

atom = <+> (satisfy \x = not (isMember x ['()'])
                      && isPrint x
                      && not (isSpace x)) <@ \t = toString t

list =  sexpr          <&> \t  =
        <*> (ds sexpr) <@  \tt = [t:tt]

::Tree a = L a | B [Tree a]
derive gDeepSeq Tree

deepSeq

2006-10-05T23:47:00.000+09:00

I was implemented a 'deepSeq' function which evaluates every thunk in the argument. It can be instantiate for user defined types because it is defined as a generic function.

DeepSeq.dcl

definition module DeepSeq

import StdGeneric, GenBimap

deepSeq :== gDeepSeq{|*|}
generic gDeepSeq a :: !a !.w -> (!a,!.w)
derive gDeepSeq Int, Real, Char, Bool, {}, {!}, {#}
derive gDeepSeq UNIT, PAIR, EITHER, CONS, FIELD, OBJECT
derive gDeepSeq []

DeepSeq.icl

implementation module DeepSeq

import StdEnv, StdGeneric, GenBimap

deepSeq :== gDeepSeq{|*|}

generic gDeepSeq a :: !a !.w -> (!a,!.w)
gDeepSeq {|Int|}          a            w = (a,w)
gDeepSeq {|Real|}         a            w = (a,w)
gDeepSeq {|Char|}         a            w = (a,w)
gDeepSeq {|Bool|}         a            w = (a,w)
gDeepSeq {|UNIT|}         a            w = (a,w)
gDeepSeq {|{}|}     f     a            w = seqArray f a w
gDeepSeq {|{!}|}    f     a            w = (a,w)
gDeepSeq {|{#}|}    f     a            w = (a,w)
gDeepSeq {|PAIR|}   fx fy (PAIR a1 a2) w # (a1,w) = fx a1 w
                                           (a2,w) = fy a2 w
                                         = (PAIR a1 a2,w)
gDeepSeq {|EITHER|} fl fr (LEFT a)     w # (a,w) = fl a w
                                         = (LEFT a,w)
gDeepSeq {|EITHER|} fl fr (RIGHT a)    w # (a,w) = fr a w
                                         = (RIGHT a,w)
gDeepSeq {|CONS|}   f     (CONS a)     w # (a,w) = f a w
                                         = (CONS a,w)
gDeepSeq {|FIELD|}  f     (FIELD a)    w # (a,w) = f a w
                                         = (FIELD a,w)
gDeepSeq {|OBJECT|} f     (OBJECT a)   w # (a,w) = f a w
                                         = (OBJECT a,w)

seqArray f ar w = seqArray 0 ar w
  where
    s = size ar
    seqArray i ar w | i >= s = (ar,w)
    seqArray i ar w          # (_,w) = f ar.[i] w
                             = seqArray (inc i) ar w

derive gDeepSeq []

'Lock Free Data Structures using STM in Haskell'

2006-10-04T22:56:00.000+09:00

http://research.microsoft.com/~simonpj/papers/stm/lock-free.htm

The paper explores the feasibility of lock free data structure using STM (software transactional memory) in Haskell on the aspects of both software engeering and performance. STM is a mechanism for coordinating concurrent threads. STM offers a higher level of abstraction than the tranditional combination of locks and condition variables.

STM is implemented as a STM Monad and 'atomically' function combines a STM Monad and an IO Monad.
'Atomically' executes a received monad atomically - i.e. no concurrent transaction has committed conflicting updates. In addition it is rubust to exceptions. If an exception raised inside the transaction, no update is made.

atomically :: STM a -> IO a

Transactional variables or 'TVars' are used to reading and writing a value.

data TVar a
newTVar :: a -> STM (TVar a)
readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()

A tansaction can block using 'retry.'
The semantics of retry is to abort the current atomic transaction, and re-run it after one of the transactional variables has been updated.

retry :: STM a

The orElse combinator allows two transactions to be tried in sequence. (s1 `orElse` s2) is a transaction that first attemps s1; if it calls retry, then s2 is tried instead; if that retries as well, then the entire call to orElse retries.

The ArrayBlockingQueue class from JSR-166 is selected as the bases for the experiment. The conventional locking implementation uses semaphores and mutexes carefully and its program is rather long while STM implementation uses neither semaphores nore mutexes and its program is simple.

Performances are mesured under conditions which varies on a number of processors (1 to 8) and a number of worker threads (2 to 14). In almost every case the STM version was faster than the locking version running on the same number of processors.

'MapReduce: Simplified Data Processing on Large Clusters'

2006-09-28T22:20:00.000+09:00

http://labs.google.com/papers/mapreduce.html

This paper is an introduction of MapReduce, a library for paralell execution on a large cluster of commodity machines.

The approach of the MapReduce library is providing restricted programming models and using the restrictions to parallelize the computation automatically. The user of the library expresses the computation as two functions: Map and Reduce, both of which are user defined functions. A Map function reads a set of input key/value pairs and produces a set of intermediate key/value pairs while a Reduce function read the intermediate set and produce a set of final output values.

The instances of the Map function and the Reduce function are distributed to machines in the cluster and each instance is executed in parallel. The input files of the Map function and the final output files of Recude function are on GFS while the intermediate files are on each Local Disk of the machine where each Map function allocated. To conserve network bandwidth each instance of the Map function is allocated to the machine where the block of input data is stored. (GFS divides each file into 64 MB blocks, and stored several copies of each block (typically 3 copies) on different machines.)

One of the copies of the program is special - the master. It decides which machine should execute each piece of task of a Map function or a Reduce function. It also detect worker failures and re-schedule their failed tasks. Status informations are available through an internal HTTP server of the master.

'Interpreting the Data: Parallel Analysis with Sawzall'

2006-09-25T23:09:00.000+09:00

http://labs.google.com/papers/sawzall.html

This paper is an introduction of Sawzall, a DSL for processing extremely large data set effectively using masive parallelism.

Sawzall is a statically typed, interpreted scripting language. The most unique feature of the language is that a program source is correspondent with only one record of input data. The interpreter repeats the defined process every record. Parallel execution is enabled because no intermediate state are shared in the repetition.

The first stage of execution steps is to read raw data sets, process each record and emitting the result, while the second stage is to aggregate all the emitted data, collate them and write the result to file. The whole process is executed in a batch style.

Aggregation is done outside the language. A number of aggregators are defined in advance and new aggregators can be created if needed. An aggregator can be indexed so that emitted data are aggregated in each index. For example, 'sum' aggregater indexed by string data is suitable to classify stored web pages by its belonging country and count a number of record of each country.

Sawzall is built upon some Google infrastructure. Protocol Buffers are used to describe the format of permanent records stored on disk. The data sets are often stored in GFS, the Google File System. Software called the Workqueue is handled scheduling a job to run on a cluster of machines. MapReduce is a library for application that run on the Workqueue and Sawzall's data processing system is built on top of it. Its interpreter runs in the map phase.

Most Sawzall jobs do very little processing per record and are therefore I/O bound; for most of the rest, the CPU spends the majority of its time in various run-time operations such as parsing protocol buffers. The key performance metric for the system is how the speed scales as machines are added when processing a large data set. A test shows that it is almost linearly scaled (only 30% degraded) over the range of 50 to 600 machines.

'-->' operator

2006-09-25T08:55:00.000+09:00

'-->' operator which is defined in OptEnv module in CleanJ package is very useful. The definition is the following:

(-->) infixl 0 //:: .a (.a -> .b) -> .b
(-->) a f :== f a

The operator is often used with unique type like

print f = f --> fwrites "Hello "
            --> fwrites "World!"
            --> fwrites "\n"

instead of a common use like

print f # f = fwrites "Hello "
          f = fwrites "World!"
          f = fwrites "\n"
        = f

The operator can be used with '$' operator which corresponds with that of Haskell and is also defined in OptEnv module, whose definition is the following:

($) infixr 1 //:: (a -> z) a -> z
($) f a :== f a

The combination of '-->' and '$' is such that

print :: ![String] !*File -> *File
print ss f = f --> seq $ map fwrites ss

TAPL Chapter 30 thru 32

2006-09-22T23:07:00.000+09:00

In chapter 30, System Fω is discussed. System Fω is a combination of System F which includes unbounded quantification introduced in chapter 23 and 24, and type operators which is introduced in chapter 29.

In chapter 31, Sytem Fω is extended with System F<:, yielding System Fω<:. This interesting feature is the extention of the subtyping relation from kind * to types of higher kinds, that is establishing a subtype relation between not only types but type operators. In this chapter, the description remains to be an introduction and proofs of fundamental properties are omitted.

In chapter 32, the pure functional interpretation of objects in System Fω<: is introduced. To cope with the problem of adding new instance variables in subclasses, a primitive for in-place polimorphic update of record fields is introduced.

The documentation of ABC machine instructions

2006-09-19T22:59:00.000+09:00

I started writing the documentation of ABC machine instructions.

I have published the working document at the web site:
http://cleanj.sourceforge.net/abc_inst.html

One liner by C

2006-09-19T22:05:00.000+09:00

$ echo "main(){printf(\"hello 1 liner.\");}" | gcc -xc -; ./a.exe
hello 1 liner.

needs cygwin.

CleanJ version 0.9 released

2006-09-17T21:49:00.000+09:00

The work of packaging the current project is over and version 0.9 is released.

http://sourceforge.net/projects/cleanj/

Before releasing it, I tested translating cleanj.exe into Java program and then translating some libraries of original clean distribution using the translated cleanj.exe, and I noticed that this translation is totally inefficient that it is not suitable for a practical use.

After the release, I am planning to write some documentation of ABC machine instructions and to improve the efficiency of the translation.

TAPL Chapter 25 thru 29

2006-09-13T23:33:00.000+09:00

I have read chapter 25 through 29.

The chapter 25 explains some implementation of System F which is a symply typed lambda calculus with universal and existential quantifiers.

The chapter 26 introduces bounded quantification which combines polymorphism and subtyping. This chapter ilustrates two type of extentions; one is "kernel F<:" and another is "full F<:."

The chapter 27 is a case study of object encoding with bounded quantification.

The chapter 28 describes the subtyping and typechecking algolithms for both of kernel and full F<: and shows that full F<: type system is undecidable and has no joins and meets.

The chapter 29 introduces type operators and kinging. Kings classify types the same as types classify terms.

Porting basic libraries is completed

2006-09-10T23:25:00.000+09:00

I completed porting basic libraries and checked in the last changes.

The final module is Directory module where I recently working. I also changed the string expresson of boolean values as "True" and "False" instead of "true" and "false" and changed GenParse module of Generic libary according to the change.

Then I finished all the task of my first trial of porting Clean system to Java VM. Ported libraries are

StdEnv
StdLib
ArgEnv
Directory
MersenneTwister
Generics
OptEnv

After completed the final test to port cleanj.exe and test all tests again with the ported cleanj.exe, I will release it as CleanJ version 0.9.

ccall and boolean value

2006-09-10T14:37:00.000+09:00

Clean's Original 'ccall' instruction implementation regards a boolean value as a sort of integer value. However Java VM distinguished these differences strictly. It brings porting ccall intruction difficult without changing the implementation of CleanVM class.

strange behaviour of java.io.File

2006-09-10T00:40:00.000+09:00

I was suffered from some strange behaviour of java.io.File in implementing setCurrentDirectory function of Directory module.

The behaviour is that 'new File(currentDir, relativePath)' creates a strange File object which has both an absolute path of 'currentDir/relativePath' and a canonical path of 'currentDir' at the same time. This behaviour leads to determine a nonexistent directory to exist.

I don't know why this behaviour occured so long, but when I scaned through Directory.icl file today I found the line below;

(errCode, env) = setCurrentDirectoryC (path_string+++"\0") env

This is the cause. The character of '\0' makes Java library wrong. I wrote some code to prove this.

public class test {

  public static void main(String[] args) throws Exception {
    File f;
    f = p(new File("dummy0\0"));
    f = p(new File(f,"dummy1\0"));
    f = p(new File(f,"dummy2\0"));
  }
  
  public static File p(File f) throws Exception {
    System.err.println(f.getAbsolutePath());
    try{
      System.err.println(f.getCanonicalPath());
    }catch(Exception e){ e.printStackTrace();}
    return f;
  }
}

The result is below;

$ java test
c:\test\dummy0
C:\test\dummy0
c:\test\dummy0\dummy1
C:\test\dummy0
c:\test\dummy0\dummy1\dummy2
C:\test\dummy0

creation time and owner

2006-09-09T23:51:00.000+09:00

I don't know how to get a creation time and owner name of some file. I cannot find such a method in class library.

Platform dependency

2006-09-09T23:32:00.000+09:00

Directory module is a platform dependent module. It has a platform id which classifies unix, windows and mac systems. At first I am planning to port Directory module without adding new platform id, but it may not be a good idea and be better to introduce a platform id of java system.

Check-In

2006-09-09T22:25:00.000+09:00

I checked in my cu(ry

ArgEnv module and part of Directory module are ported. 'Ccall' instruction is also ported because Directory module uses 'ccall' instruction.

'Ccall' instruction is these format below;

  ccall [external c procedure name] "[type string]"

I introduced a '*$CCALL.java' file to search procedures called by ccall instructions.

The type string format is '[input value types]:[output value types]:[other value types]' and in the original Clean implementation the head of output value types are interpreted as a return value and the rests are arguments of pointer type. In CleanJ implementation all output value types are interpreted as return values; if no output types are specified the correspondent java return type is void, if only one output type are specified the correspondent java return type is int, double, char[] or Object according to the type, and otherwise it is Object[].

int getCurrentDirectory_SE(CleanString cs)

2006-09-05T23:20:00.000+09:00

The title function uses side_effect to transfer current directory path. It modifies input string elements and sets the whole length of the path name.

When translating it to Java program setting the length of the path name is a challenge because Java array cannot change its length. There are no solution there.

I solved this problem to modiry Directory.icl file itself.

exit_false

2006-09-05T19:35:00.000+09:00

I found new instruction, 'exit_false,' in Directory module. This instruction is found in the format of 'exit_false selector_m_error.'

'Selector_m_error' is defined in '_system.abc' file as below;

.o 0 0
selector_m_error
   print "Run time error, selector does not match"
   halt

This means that when jumping to 'select_m_error' label follows executing 'exit_false' instruction. It seems that 'exit_false' is a alias of 'jmp_false.'

I don't know what sort of programs are compiled to instructions using 'exit_false.'

::A a b = A a
       | B b

Start = (f (A 1), f (B 'a'))

f aa = let (A a) = aa
      in a

will compiled to instructions using 'exit_false.'

ArgEnv

2006-09-03T22:53:00.000+09:00

I completed porting ArgEnv library. This work is rather easy.

I used System.getenv() method to implement getEnvironmentVariable function. This method was marked as deprecated before and is available since Java1.5 released. So the getEnvironmentVariable function of the ported ArgEnv library is not available before Java1.4.

Check-In

2006-09-03T17:47:00.000+09:00

I checked in my current changes. Main changes are enabling GenParse, GenPrint and StdDebug.

see http://svn.sourceforge.net/viewvc/cleanj/

GenParse/GenPrint

2006-09-03T16:25:00.000+09:00

I worked on GenParse/GenPrint today, and fixed Instruction.icl on missing quotation of eqC_b and implementatio of eqAC_a.

Then I tested a test for GenParse/GenPrint and realized that GenParse on Bool values are not working correctly.

I decided previously to use Java convention of printing boolean values instead of Clean one, where true value is printed as "true" and false value is printed as "false" instead of Clean convention of "True" and "False". This decision is because of convenience of connecting CleanJ programs to Java programs.

Because GenParse implementation is expected that Bool values are printed according to Clean convention in input text, when CleanJ prints Bool values in Java convention GenParse failed to parse Bool values correctly.

So I have changed "True" and "False" to "true" and "false" respectively in GenParse.abc. This change makes a test passes but this prescription is certainly ad-hoc and more consideration needed.

TAPL Chapter 23 & 24

2006-09-02T23:33:00.000+09:00

Type quantifiers ∀ and ∃ are discribed for each in chapter 23 and chapter 24. Chapter 23 studies a system of parametric polimorphism, namely System F and introduces a type quantifier ∀. Chapter 24 introduces an existential type and a type quantifier ∃ and studies module systems of Abstract Data Types and Existential Objects.

Clean has a module system with a syntax of abstract data types and class type system in addition to an existential type system. These features are all a kind of abstract data types described in Chapter 23 and no syntax exists that is oriented to an existential object approach. Of course using an existential type system we can manually create those kind of objects but that work is rather elaborate and boring.

I think Clean has ample type features and enough flexibility but is short of syntax sugar and it is better to make some preprocessing system like camlp4 for ocaml.

Check-In

2006-08-31T00:15:00.000+09:00

I checked in the current change on seek/position operations and data file io operations.

I previously stated my next job is to port Directory library and command line argument supporting library, but before doing them I will port the remaining of Generics library that was not ported when porting Generics library before porting File I/O.

The remaining files are GenParse.dcl/icl and GenPrint.dcl/icl.

Implementing file io operations finished

2006-08-30T09:04:00.000+09:00

I finally implemented clean's all file io operations. I am going to create and run several tests for newly implemented data file io operations, and to check in the results in a few days.

The remaining jobs are to port Directory library and to support command line arguments by creating ArgEnvJava library similar to ArgEnvWindows or ArgEnvUnix in clean standard library. When those jobs are completed, I will port cleanj.exe to run on cleanj runtime and test all tests under the metacircular translator.

TAPL Chapter 22

2006-08-29T23:00:00.000+09:00

I have read the chapter. It is on type reconstruction. I have found some familiar terms, especially the name of 'Clean.'

I have heard of Let-polimorphism and value restriction but had no idea what it is before reading it. I also learnt type classes are rooted in type reconstruction of record types and Milner-Mycroft Calculus is an extension to allow polymorphic recursion.

Handling return code on Clean Text IO operations

2006-08-27T21:52:00.000+09:00

Clean Text IO operations convert return code from '\r\n' to '\n' when reading text files. This enables for a programmer to treat any type of text file as uniformly having only one type of return code '\n' and this saves much time of programming.
CleanJ also supports this feature.

TAPL Chapter 21

2006-08-26T23:30:00.000+09:00

I don't proceed CleanJ project for recent 4 days because I have been struggling to understand TAPL Chapter 21.

This chapter describes metatheory of recursive types using coinduction to prove the property of recursive types. It is very hard for me to understand this chapter because I am not familiar with coinduction, and it takes 4 days to read through.

Check-In

2006-08-21T00:10:00.000+09:00

I checked in my current code. Test for exceptional situations of text file IO opetations are added to the previous code.

Applying fshare to a file of FWriteText mode

2006-08-20T20:25:00.000+09:00

Start :: *World -> (Bool, Int, File)
Start w # (_,f,w) = fopen "file/FileShare.test1" FWriteText w
         sf = fshare f
       = sfreadi sf

Against the intuition this code doesn't fail, but outputs as below;

(True,0,(File 0 4254596))

Surprisingly this sfreadi function succeeds. It seems a bug.

I think it should be failed to apply fshare function to a file whose mode is not compatible with share file operations. However, actual fshare function doesn't reject such file objects and sfreadXX functions rejects them.

I am planning for fshare function of CleanJ to reject these file objects.

error pattern

2006-08-20T16:26:00.000+09:00

Summarize error pattern of clean text file io operations.

sfopen in FWriteText/FAppendText mode
fopen/sfopen/freopen in invalid file mode (ie. mode < 0 or 5 < mode)
read file operations to a file of FWriteText/FAppendText mode
write file operations to a file of FReadText mode
fshare function to a file of FWriteText/FAppdnText mode
fshare function to standard input/output/error
share file functions to a non-share file
fseek function to standard input/output/error
freadline to a file of FReadData mode

Additionally, list check point of unknown behaviours.

fend function to a file of FWriteText/FAppendText mode
fend function to a file of standard input/output/error

a bug of freadi function

2006-08-20T15:55:00.000+09:00

Freadi function in FReadText mode may have a bug about the reading error flag.

(ok,i,s) = freadi s

When evaluating this code, a variable 'ok' will always be 'false' even if io operation succeeds and input text format is valid.

Test for Text File IO operation

2006-08-19T23:05:00.000+09:00

Finally I have finished my work to implement Clean Text File IO operations in CleanJ environment. And I am to test them to check its behaviour. Partly I have some tests but they do not have sufficient coverage, especially on file seek operation, standard error output operation, standard input operation, japanese text handling, and exceptional situation handling.

Clean File IO function design doesn't have suitable type design and allows inconsistency, and if a program implemented irregularly it will get stuck and show some error messages. Because CleanJ has a policy to mimic Clean behaviour as possible, I have to check as many error messages as possible.

Besides, Data File IO operations are not implemented yet.

Check-In

2006-08-19T16:50:00.000+09:00

I checked in my current developping code which is changed in its implementation of CleanFile.java from using PushbackReader to using RandomAccessFile.

Implementing normal text file operations finished.

2006-08-19T00:46:00.000+09:00

Using RandomAccessFile, Charset, CharsetDecoder, ByteBuffer and CharBuffer. Additionally I uses Pattern, Matcher, System.getProperty("line.separator") to handle linefeeds properly according to the system environment.

RandomAccessFile and CharsetDecorder

2006-08-16T22:38:00.000+09:00

Using combination of RandomAccessFile and CharsetDecorder seems good but it has essential difficulty in it. In decoding by CharsetDecorder, input byte sequence is copied into ByteBuffer and decoded char sequence is got through CharBuffer. Since these two buffer are put between RandomAccessFile and CleanJ read operations, pinpointing exact file pointer index is far more difficult than when no decorder exist.

One solution is to calculate current file pointer index from RandomAccessFile object's file pointer and remaining chars in CharBuffer and remaining bytes in ByteBuffer. It is a general solution but it has some efficiency overhead.

Another solution is to abandon supporting fposition function and all share file operations, since share file operations uses file pointer to implement them. Fseek function can still be supported but when fposition function is not available, fseek function becomes less important.

I am still torn apart and seeking other solutions.

I may have misunderstood the behaviour of CharsetDecorder. I am now wondering that the decorder retrieve minimal necessary amount of bytes from provided ByteBuffer and the required information to calculate current file pointer index are just RandomAccessFile object's file pointer and number of remaining bytes in ByteBuffer but number of chars of remaining chars in CharBuffer is not required.

I am not sure. I will verify it later.

It was not true.

difference of char type between clean and cleanj

2006-08-16T08:42:00.000+09:00

CleanJ is aimed to behave almost the same as clean do, but in spite of the aim those two have some difference. One of the most significant differences is the representation of char type.

Clean char is one byte, the same as C language. Clean String is a simple array of char and it ignores internationalization. If a program source code is written in Japanese Shift_JIS, then an executable file has Shift_JIS encoded strings. If the executable file read a text file written in Japanese EUC_JP, then a read function offers a EUC_JP encoded string. To resolve this discrepancy is a programmer's responsibility.

On the other hand, CleanJ char is two byte UTF16 char, the same as Java language. CleanJ String is a simple array of this two byte char. Though a program source code is written in Japanese Shift_JIS, an generated class file has UTF16 encoded strings.

Now I am trying to match text file read functions to this charset setting. I am planning to transform input text to UTF16 according to environment locale setting with the help of standard class library. While Reader class equips an appropriate decorder, RandomAccessFile doesn't and is required to implement some additional codes manually for decoding an input text from RandomAccessFile.

One problem exists. This charset policy prevents from handling byte array directly. This is crucial in operating binary data file such as generating Java class file. I don't have final solution to this problem but am thinking these operations are provided by special library of CleanJ distribution.

ByteBuffer

2006-08-15T23:31:00.000+09:00

Charset provides CharsetEncoder/CharsetDecorder which translate chars to bytes anc vice versa. When CharsetDecorder decodes bytes, these bytes are provided by ByteBuffer.
http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/nio/ByteBuffer.html
ByteBuffer are used as below;

byte[] in = new byte[size];
ByteBuffer buf = ByteBuffer.wrap(in);
file.readFully(in);
CharBuffer cbuf = charset.decode(buf);
return cbuf.toString();

This implementation is only an imaginary code and may have flaws.

java.nio.charset.Charset

2006-08-15T09:18:00.000+09:00

http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/nio/charset/Charset.html
This is charset encode/decode library class in standard class library.

RandomAccessFile does not follow locale.

2006-08-15T00:30:00.000+09:00

Since RandomAccessFile does not follow locale, readChar() method is not suitable for reading text file.
To write function to read char from plain text file seems needed, or does any usefull class exist in standard library?

Check-In

2006-08-14T09:22:00.000+09:00

I checked in my recent updates and current snapshot.
http://svn.sourceforge.net/viewvc/cleanj/snapshots/
It enables some File IO operations whose tests are available in a test08 folder.

RandomAccessFile

2006-08-14T00:47:00.000+09:00

I have been implemeted File IO functions corresponding to StdFile in standard library. I uses PrintStream (for output) and PushbackStream (for input) but these are not suitable for random access which is needed to implement share file operations and a seek operation.
Instead I found java.io.RandomAccessFile class right now and it may be better for the purpose.

Current Directory in Java

2006-08-13T19:38:00.000+09:00

While Clean has a problematic function for changing current directory, Java has no method for it.

Current Directory

2006-08-13T18:18:00.000+09:00

Directory library in clean has a function to change current directory, but its behaviour is problematic.
Here is a test program.

Start :: *World -> ([String], [String])
Start w # (s0,w) = accFiles f w
         (s1,w) = accFiles f w
       = (s0,s1)
where
f fs # (cp0,fs) = getCurrentDirectory fs
       (cps0,fs) = pathToPD_String cp0 fs
   
       (_,f,fs) = fopen "file/test.txt" FReadText fs
       (s,f) = freadline f
       (_,fs) = fclose f fs
   
       ((_,p),fs) = pd_StringToPath ".." fs
       (_,fs) = setCurrentDirectory p fs
   
       (cp1,fs) = getCurrentDirectory fs
       (cps1,fs) = pathToPD_String cp1 fs

     = ([cps0,"\n",s,cps1,"\n"],fs)

The result of this program is below;

(["C:\Clean\test\test01","
","abcdefghijklmnopqrstuvwxyz
","C:\Clean\test","
"],["C:\Clean\test","
","abcdefghijklmnopqrstuvwxyz
","C:\Clean","
"])

Apparently the function call 'setCurrentDirectory p fs' affects not only 'fs' but also *World itself. Though this program does not violate the principal of reference transparency but it betrays an intuition.
Moreover, this 'setCurrentDirectory' function does not affect 'fopen' function's current directory. Although 'file/test.txt' does exist only at 'C:\Clean\test\test01\file\test.txt' but not at 'C:\Clean\test\file\test.txt', after the current directory move to 'C:\Clean\test' 'fopen' function for 'file\test.txt' succeeded. This behaviour is also confusing.

_SystemStrictLists.abc

2006-08-12T14:20:00.000+09:00

"_SystemStrictLists.abc" in StdEnv has some instructions for File IO and cleanj cannot compile the original file in itself. So far I modified the file to remove functions which contains those instructions.
Now that File IO instructions are available, cleanj can compile the original "_SystemStrictLists.abc" file and I recover it.

OutputStream/Writer

2006-08-12T00:21:00.000+09:00

Yesterday I stated a question about PrintStream and PrintWriter.
http://lethevert.blogspot.com/2006/08/printstreamprintwiter.html

For now, I understand the difference between them. OutputStream is for binary data sequence output but Writer is for character sequence output.
PrintStream is a subclass of OutputStream and PrintWriter is a subclass of Writer. They have overlapped area of application but Java implementation doesn't provide unified interface of that area. That is a problem.

fshare

2006-08-10T23:46:00.000+09:00

'Fshare' function changes '*File' data to 'File' data.
This function mark current positon of input file and set shared flag. When sfreadX function called, the function will calculate current position from marked position in file descriptor and offset number in B-stack.

Share file operations

2006-08-10T09:14:00.000+09:00

Mark(), reset() and skip() of InputStream may be useful for share file operations. First, mark first point of file and each time share file operation called reset() and skip() to ajust the position of file stream.
It is quite expensive and if better idea exists I will adopt it.

PrintStream/PrintWiter

2006-08-09T23:57:00.000+09:00

I don't know why PrintStream and PrintWriter both exist in java standard library. What is the difference between them.
Some webpage says that PrintWriter is better, but System.out (standard output stream) is PrintStream.
Does anyone know the difference?

DataOutputStream

2006-08-09T23:25:00.000+09:00

File operations of Clean have 6 types

Read from a Text file
Write to a new Text file
Append to a Text file
Read from a Data file
Write to a new Data file
Append to a Data file

Text file operations let programs read and write text data. For instance, an integer value 101 is represented as 3 characters '1' and '0' and '1'.
Data file operations let programs read and write binary data. For instance, an integer value 101 is represented as 4 byte sequence 00000000,00000000,00000000,01100101 as binary number.
There are no standard class library for text file operations but DataOutputStream/DataInputStream are suitable for data file operations.
http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/io/DataOutputStream.html
http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/io/DataInputStream.html

File structure

2006-08-09T09:11:00.000+09:00

'File' structure consists of 2 B-values but its detail is not clear yet.
I make a test program below;

Start :: *World -> (*File, File, File)
Start w # (f,w) = stdio w
         (_,sf,w) = sfopen "FileShare.test1" FReadText w
         (sf1,f) = print 2 sf f
         (sf2,f) = print 5 sf f
       = (f, sf1, sf2)
where
   print 0 sf f = (sf, f)
   print a sf f # (_,c,sf) = sfreadc sf
                  f = fwritec c f
                = print (dec a) sf f

This is to identify behaviour of share file operation and related structure of 'File' type.
The result is;

(ababcde(File -1 4258564),(File 2 4258692),(File 5 4258692))

This imply that 'File' structure consists of 1 Int value and 1 File handler. The first int value indecates offset value of share file operation, and it is not used for unique file operation (shown as -1).

Why am I trying to create CleanJ

2006-08-08T23:43:00.000+09:00

I found Concurrent Clean on June 30 last year. It has been just one year.
Soon after, I realized the language is very flexible and I don't know why at that time. I don't know the reason sure but I think it is partly because its ability to arrange codes independent of the order of execution and I know that is one of main advantages of pure functional languages.
I also noticed its restriction of dealing with side effect in a program is sometimes a heavy pressure in software design and implementation. Libraries and frameworks may be a solution of this restriction. ObjectIO is one of them. But creating such frameworks from scratch are also heavy task for ordinary programers.
While Java is a common object-oriented programming language and it characterized by compiled object portability and its large number of libraries and frameworks. If Clean program can run on Java VM, its program may use those libraries and frameworks and it may cover its shortcoming.
I am planning to build web application framework after CleanJ project comes to a stable version, and examine how to design such framework with the aid of libraries written in other languages.

Strict array and list of File type

2006-08-08T23:01:00.000+09:00

'File' structure consists of 2 B-values and 'buildF_b' instruction makes 1 A-value out of these 2 B-values.
Strict File array '{#*File}' is compiled into such instructions below:

create_array_ _ 1 0

It is the same as ordinary A-value array like '{String}'.
Strict File List '[#*File]' is, however, is compiled into a B-value strict list such as:

fill_r _Consf 1 2 4 0 0

It seems that the clean compiler has a bug in treating strict File array, but I don't know what is correct behaviour of the compiler.

comment and 'jcall' instruction

2006-08-08T09:08:00.000+09:00

In ABC instructions, a line beginning with '|' is a comment line where the CodeGenerator ignore it.
When I introduce some instructions for cleanj, I will make these new instructions begin with '|' so that the original code generator will ignore these new instructions.

Start = f 1

f a = code inline {
   |jcall
}

This program above makes 1 ignoring '|jcall' instruction. Correspondent ABC machine code is below:

s2
.inline f
   |jcall
.end

.d 1 0
   rtn

ABC machine instructions for File I/O

2006-08-07T23:03:00.000+09:00

buildF_b
fillF_b

These two instructions are for File I/O.
'buildF_b' is to build an A-value for File structure from two B-values.
'fillF_b' is to change a node to represent File structure.

StdFile

2006-08-07T22:23:00.000+09:00

StdFile is a file manipulation library of Clean language.
In StdFile.icl, which is implementation module of StdFile, those system functions are called.

openF :: !String !Int -> (!Bool, !*File)
closeF :: !*File -> Bool
stdioF :: *File
openSF :: !String !Int -> (!Bool, !File)
reopenF :: !*File !Int -> (!Bool, !*File)
readFC :: !*File -> (!Bool, !Char, !*File)
readFI :: !*File -> (!Bool,!Int,!*File)
readFR :: !*File -> (!Bool,!Real,!*File)
readFS :: !*File !Int -> (!*String,!*File)
readFString :: !Int !Int !*String !*File -> (!Int,!*String,!*File)
readLineF :: !*File -> (!*String,!*File)
writeFC :: !Char !*File -> *File
writeFI :: !Int !*File -> *File
writeFR :: !Real !*File -> *File
writeFS :: !String !*File -> *File
writeFString :: !Int !Int !String !*File -> *File
endF :: !*File -> (!Bool,!*File)
errorF :: !*File -> (!Bool,!*File)
positionF :: !*File -> (!Int,!*File)
seekF :: !*File !Int !Int -> (!Bool,!*File)
stderrF :: *File
readSFC :: !File -> (!Bool,!Char,!File)
readSFI :: !File -> (!Bool,!Int,!File)
readSFR :: !File -> (!Bool,!Real,!File)
readSFS :: !File !Int -> (!*String,!File)
readLineSF :: !File -> (!*String,!File)
seekSF :: !File !Int !Int -> (!Bool,!File)
shareF :: !*File -> File
endSF :: !File -> Bool
positionSF :: !File -> Int

'File' structure seems to be a basic value of two words.
I don't know the merits of share File functions are defined.

World -> World

2006-08-07T21:52:00.000+09:00

If you create such program that

Start :: *World -> *World
Start w = w

correspondent ABC machine code is

__World_Start
    buildI 65536
    build _ 1 n1
.d 1 0
    jmp _driver

'__World_Start' is an entry point to this program, and Number '65536' is actual value of '*World'.

CleanJ

2006-08-07T09:09:00.000+09:00

Current status of CleanJ is ...

translate .abc file into .java file
support any basic features except file manipulate operations
ported StdEnv except StdFile and StdDebug
ported StdLib
ported MersenneTwister
ported Generics except GenParse and GenPrint

quine of Concurrent Clean

2005-08-07T15:04:00.000+09:00

module m;import StdEnv;Start w#(s,w)=stdio w;#s=fwrites(x+++c+++x+++c)s;#(_,w)=fclose s w;=w;c=toString(toChar 34);x="module m;import StdEnv;Start w#(s,w)=stdio w;#s=fwrites(x+++c+++x+++c)s;#(_,w)=fclose s w;=w;c=toString(toChar 34);x="