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
destructors to take them apart and get the constructor argument
back.
So fine, but you need to know which constructor was applied,
for a standard variant type its in the value as a integer tag,
and so a match just does a test on the tag to see which
destructor to apply, and how to cast the resulting argument
to the right type.
So basically for a constructor
Ctor: A -> U
you need two functions for union type U:
_match_ctor_Ctor: U -> bool // match checker
_ctor_arg_Ctor : U -> A // extractor
where the understanding is it is only safe to apply the extractor if the
checker returns true. SO basically a match:
match u with
| Ctor ?a => ...
is implemented by:
if _match_ctor_Ctor (u) then
var a :A = _ctor_arg Ctor (u)'
....
elif ...
This is actually implemented already!
For an actual Felix union type
the only difference is the compiler doesn't actually put the
_match_ctor and _ctor_arg functions into the symbol table, it just
generates their definition bodies "on the fly". In fact it USED to put
them into the symbol table (which made the symbol table very big).
Since union is generally:
struct _uctor_ { int variant; void *data; }
the match checker just compares variant with an integer
constant corresponding to the index of the constructor
in the union definition. Eg in a list, Empty=0, Cons=1.
And the argument extractor is just a cast and deref:
*(A*)u.data
where T is the argument type. The argument of Cons is a tuple
T * list[T]
> then its good, because i would rather have that tied up neatly before moving
> to something else. That Python is 3X faster is an unpardonable affront :)
Not really. Python has very good string handling, it evolved over a long time,
and being an actual scripting language, if the string operations are fast
enough the cost of interpreting bytecode is small compared to the string ops,
even with dynamic typing.
Felix can do it faster than Python, but the simple idioms, stuff like
iterators, for example, is coded with the constraint of using C++
underneath, string class in particular, and wanting to be easy
to code. The easy to code stuff isn't necessarily fast and its hard
to optimise because the compiler doesn't know what a string is.
Python doesn't either! So its no excuse. However Python
is object based and strings are immutable so passing them
around has a low cost. C++ strings aren't so the cost is quite high.
Gcc uses COW but that is banned now and not allowed by the
Standard, although now we have move constructors which should
copy rvalue strings at zero cost (i.e. constant time).
So without some work, things like split are going to be expensive
because they return 2 strings from one, so you not only get two new
strings, if you're not careful they get copied in the process of returning
them. And a string will get copied when passing it as an argument too.
This is a really good reason NOT to use eager evaluation!!
It's likely to say:
parameter = argument
which will copy argument to parameter (even if the argument is
already a single variable). Of course in Felix the parameter is then
stored into the functions class as a variable .. that's ANOTHER copy.
You can see why lazy evaluation and inlining are vital for performance:
it elides a lot of copying.
Still, Felix "style" more or less dictates pass by value and don't worry about
it.
When the underlying types are expensive to copy this is going to rub off
if they can't do it smartly: C++ rvalue binders and thus move constructors
should help to fix this to some extent. And they had better, since now
COW strings aren't allowed.
--
john skaller
skal...@users.sourceforge.net
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
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
