john skaller | 13 Oct 01:57 2014
Picon
Picon

Re: [felix] monomorphisation


On 13/10/2014, at 3:53 AM, Shayne Fletcher wrote:

> 
> On Sun, Oct 12, 2014 at 1:04 AM, john skaller <skaller <at> users.sourceforge.net> wrote:
> For example
> 
>         reduce[T] double_rev(x:list[T]) : rev (rev x) => x;
> 
> will not work if list[T] with T->int changes the type to list_of_int
> and the rev functions to rev_of_int
> 
> ​Sorry, maybe not quite getting it. Surely,  T <- int, rev_{1} = rev_{2} <- rev_list_of_int. What's the
problem?​ Is it that the polymorphism of of the reduction rule has been lost?

When rev[T] of list[T] is monomorphised its "name" is changed to a new function

	rev_of_int[] of list_of_int[]

Actually it's integer index in the symbol table is changed.

More precisely, a brand new function is created which reverses
only integer list.

So the pattern matching to find things to reduce is looking for
the old "rev" function index.; It won't see the new rev_of_int index.

To fully see, if you had a reverse of a list of strings, you would get

	rev_of_string[] of (list_of_string[])
(Continue reading)

john skaller | 12 Oct 07:04 2014
Picon
Picon

monomorphisation

I'm stuck at Great Keppel Island. Autopilot has bitten the dust.
No crew. 

Anyhow I just realised monomorphisation, including "cloning"
during inlining, defeats the reduction feature.

For example

	reduce[T] double_rev(x:list[T]) : rev (rev x) => x;

will not work if list[T] with T->int changes the type to list_of_int
and the rev functions to rev_of_int (dummy names for the monomorphic
type and function synthesised by the compiler).

--
john skaller
skaller@...
http://felix-lang.org

------------------------------------------------------------------------------
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://p.sf.net/sfu/Zoho
john skaller | 17 Sep 01:12 2014
Picon
Picon

strings

Consider 

	struct FS { char const *data; int len; }

which is layout compatible with RE2 StringPiece.  Note
the "char" type is most usual but in principle could be any T.
FS are immutable.

Construction:

1. From a NTBS (C char array) literal: 
   	* set the length with strlen

2. From a buffer, NTBS:
    	*set the length with strlen
   	* allocate array on Felix heap
   	* copy buffer to heap

3. From a buffer, length given:
	* allocate on Felix heap
	* copy buffer to heap

4. From a NTBS array, transfer ownership:
	* calculate length with strlen
	* pass ownership to GC (length wrong but not matter)

5. From C array and length, transfer ownership:
	* pass ownership to GC

6. Substring of an FS:
(Continue reading)

john skaller | 16 Sep 11:26 2014
Picon
Picon

Re: [felix] User defined pattern matching


On 16/09/2014, at 6:34 PM, srean wrote:

> You can keep using std:strings but avoid creating intermediate C style char[ ] strings. One could use
ifstream or ofstream to get a std:string directly from the OS buffer (their rdbuff interface one can go
pretty low level), but mixing that with FILE* handle would be messy but do able. Console I/O would work too
if one swaps the rdbuff of cin or cout with that of ifstream or ofstream

But you're only talking about one function (reading a line).

There are other functions that require interfacing: RE2, SDL,
etc etc.

--
john skaller
skaller@...
http://felix-lang.org

------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce.
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
john skaller | 16 Sep 10:24 2014
Picon
Picon

Re: [felix] User defined pattern matching


On 16/09/2014, at 5:14 PM, srean wrote:

> Oh I was aiming much lower, like eliminating copies of C strings to std::string.

Well, varray[char] could be a good base. 

I could implement SubArray (in general). Varrays can't move or be resized.
They're variable length up to a bound. Pass by address, mutable.

SubArray would just be varray with start and end pos.
Or start and length.

There is a cost, getting either a C string in a stack buffer, or,
a C++ string onto the heap. However c_str() already pays that
price for C++ strings and already returns a varray[char] .

The way arrays and pointers work in Felix is still too confusing.
Even I can't figure it out :)

--
john skaller
skaller@...
http://felix-lang.org

------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce.
Perforce version control. Predictably reliable.
(Continue reading)

john skaller | 16 Sep 09:02 2014
Picon
Picon

Re: [felix] User defined pattern matching


On 16/09/2014, at 3:24 PM, srean wrote:

> 
> I think there are enough extra copies and other overheads that can be removed to beat Python at it. Note the
C++ code itself is twice or more faster than the Python code, so passing the buck to C++ wont help.

I haven't seen the C++ version of it.

> One neednt allocate that list upfront although that turned out to be faster.
> There's got to be a way to make Felix yield competitive.

Of course there is, but it doesn't involve copying strings about.
Since Felix is a pass by value language, that seems inevitable,
even with some inlining, if one is using higher level functional
operations like split.

RE2's StringPiece would help if the base char array can be made
to persist. Its basically a struct { length, char const* } thing.

But that raises another deficiency in Felix. When you have a Felix native
structure containing pointers, you can nest it in another Felix native
structure. The compiler traverses the tree when building the array
of pointer offsets for the top level type.

There's no way to do this for any C data type *except* a type that
is already a pointer, you can label that like:

	_gc_pointer type fred = "fred*";

(Continue reading)

john skaller | 16 Sep 07:15 2014
Picon
Picon

Re: [felix] User defined pattern matching


On 16/09/2014, at 1:57 PM, srean wrote:

> Now I am totally lost, sorry, could you do a redux (to a 5 yr old).

Just see the next post. It's already implemented, I just didn't realise :)

>  I have a vague suspicion that this has been provoked by Ryan's code,

Actually, I was looking at a rope made using RAList (purely functional
random access list, already coded in the library).

The problem is you can't pattern match on it like an ordinary list.

I'm so used to using pattern matching now I can't abide using a language
without it. For example Scheme is used to make the parser, it has no pattern
matching and it sucks doing anything in it which involves translating
S-expressions: I would need an arcane list of comparators applied
like (if (cond) (if (cond) .... to match a term and that is beyond my small 
brain.

So I want to bed worrying about how to make a rope and dreamed
up the general requirements for pattern matching. I think it's
a categorical adjunction but I'm not sure: you basically have to have
a partial inverse function, eg:

	Uncons (Cons (a,b)) = (a,b)

Uncons isn't an inverse for lists: it only "inverts" a list made by Cons.
So if your data type has N constructors you need N matching
(Continue reading)

john skaller | 15 Sep 21:53 2014
Picon
Picon

User defined pattern matching

One of the things which has been puzzling me is how to
pattern match abstract data types. This puzzle reawakened
by considering RAList.

An RAList, like a list, supports functions:

	empty ()
	cons (elt, list)

and it supports

	isempty (list)
	head (list) when not isempty 
	tail (list) 

and also uncons = head,tail.

Now the secret of list pattern matching is that

	empty () => 0, ()
	cons (elt,list) => 1, (elt,list)

in other words, the constructors 

	Empty = 0
	Cons = 1,

and the terms constructed are just tuples:

	constructor, argument
(Continue reading)

john skaller | 15 Sep 10:09 2014
Picon
Picon

Re: [felix] Why is this code so slow?


On 15/09/2014, at 3:31 PM, srean wrote:

> I think rope would be an overkill for simple cases of concatenation.

But not for complex ones: I changed this from concatenation to
using += and reserve .. but the reserve is a guess and I haven't done
this everywhere.

  method fun make_frame (out:string) :string = {
    var o = "";
    reserve(&o,10000+out.len.int);
    var h = #(d.heading.get_headings);

    o+=menu_js;
    o+=menu_style;
    o+=#(d.heading.emit-js);
    o+=#(d.button-factory.get-jscript);
    o+=#(d.fileseq.get-jscript);

    // Whole page defaults and background
    o+='<div style="background-color:'+page_colour+'; font-family:sans-serif; color:'+text_colour+'">';

    // LEFT MARGIN
    // fixed top nav bar 
    o+='<div style="position:fixed; top:10px;  left:10px; width:'+
    (toc_width - 10).str+'px; height:30px;' +
    ' background-color:'+frame_colour+'; padding:4px;'+
    ' border-top-left-radius:10px; border-top-right-radius:10px">';
    o+='</div>\n';
(Continue reading)

john skaller | 15 Sep 07:01 2014
Picon
Picon

Re: [felix] Why is this code so slow?


On 15/09/2014, at 2:35 PM, srean wrote:

> It is creating a a full list whereas the Python code doesnt, so using a generator style might recover even
more ground. But I dont know the cost model of Felix GC at all, so you certainly would know better.

I think you mean iterator, which is a generator closure: readln itself is a generator,
that's just a function with side-effects.

readln would be faster because it just reads lines using fgets.
So there's no need to do a split.

Er ....

for file in split(file_file,"\n") do
  println$ file;
  var f = fopen_input file;
  reading: while true do
    var line = readln f;
    if line == "" do break reading; done
    index.add line (index.get_dflt (line,0)+1);
    ++counter;
  done
  f.fclose;
done

Time elapsed: 1.077088s, 56397 trx,  or 52361 trx/sec

which is SLOWER.

(Continue reading)

john skaller | 15 Sep 05:56 2014
Picon
Picon

Re: [felix] Why is this code so slow?


On 15/09/2014, at 1:34 PM, srean wrote:

> Two questions:
> 
> i) Does Felix de-synchronize C++ I/O from cstdio ? That speed up things quite a bit

No .. but then Felix doesn't use C++ I/O streams. Its all C FILE*.
In any case this program doesn't do much I/O to the console.

> 
> ii) Rather than using the function split, would it be better to use a generator that yields the lines. Felix
has readln for that, correct ?

Dunno. I'm looking at the split function .. and I'm not surprised its horrendously slow.
Not surprised at all. I could speed this up heaps and heaps!!

  fun rev_split (x:string, d:char): List::list[string] = {
    fun aux (x:string,y:List::list[string]) =>
      match find (x, d) with
      | None => Cons (x, y)
      | Some ?n => aux$ x.[n+1 to], List::Cons (x.[to n],y)
      endmatch
    ;
    return aux$ x, List::Empty[string];
  }

So, ok, this is tail recursive. But it works by chopping off the head substring
and pushing it onto a list, then calls itself on the tail substring. 

(Continue reading)


Gmane