felix-language — Design of t he Felix programming language

Re: [Felix-language] [felix] Set form

[john s. <sk...@us...>]

I am going to investigate set forms now.

There is a serious issue with specialisation and deduction here.
Felix is "less than capable" doing this. It's a hard problem.

C++ is a bit better. It can deduce the T in "vector<T>".
Felix can do that kind of thing too, given a functor constant
such as vector, but it cannot do this given a type U instantiated
as F[U] for some F, that would require polyadic deduction.
Note, it CAN do it for array[T,N] because that's just a typedef
for T^N.

So now, the problem is roughly: to, say, fund the union
of two lists representing a set we can just concatenate the lists.
For two set forms, which are also sets, we just make a set form
whose predicate is the disjunction of the argument set forms.
Note, we cannot actually find these predicates, so we have to use

	A \cup B = { x | x \in A or x \in B }

which is horribly inefficient because it makes an object linked
to two other objects and has to use indirect dispatch, and so
cannot optimise the predicate. Eg not (not A) is A but we can't
do that optimisation with set forms.

Anyhow the purpose of this post is to talk about patterns:

	(?x,?y)

At present you can match against

	Some x

you do not need Some ?x or Some var x. This ONLY works in some
cases, where the variable is explicitly the argument of a constructor,
that is, in a form like

	F x

recursively. The choice is made very early in compilation where
pattern matching is reduced to conditionals, in other words,
it is entirely syntax driven, not type information is available.
no lookups can be done.

The solution is found in ATS. In ATS, all constructors have an argument,
possibly unit.  So universally in the form

	F x

x is a variable and F a constructor. The only exception is literals:

	1.0, "hello"

So for example

	Empty

is NOT allowed, it requires an argument:

	Empty ()

because in ATS there's no such thing as a "constant constructor" other
than literals. Felix copies Ocaml, and allows constant constructors
(even though the idea is basically nonsense).

In particular in theory you would have to write

	true(), false()

everywhere (although the parser could define true -> True () to fix that).

BUT luckily in Felix there's another way:

	#Empty

because that means  Empty () in an expression anyhow. And this notation
is ALREADY available in pattern matching.

So now the BIG question: should I enforce the rule??

It is not necessary to change any unions or whatever at this stage.,
It is not necessary to write

	Empty () or #Empty

in any expressions (YET).  That's because the compiler, at the stage
of binding expressions, has type information and can do lookups,
so it knows Empty is a constant constructor. In fact, #Empty will
not work!!!

The only rule is that you must write

	#Empty

in patterns to tell the compiler it is a constant constructor, not a variable
name.

The impact: EVERY SINGLE PATTERN MATCH including ones generated
by the parser WILL HAVE TO BE CHECKED. Every program, every library
file. 

It may be possible to "hack" more than true/false, for example, Empty, None
could just be "hacked".

Another option would be to get rid of constant constructors entirely.
The edits would be easier -- just replace Empty with #Empty everywhere.
IN fact we could even allow

	union opt = Some of int | #None

to mean

	union opt = Some of int | None of unit

But, I don't want to mess with the compiler at the moment...

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

Re: [Felix-language] [felix] Set form

[john s. <sk...@us...>]

Sometimes it's hard to believe Felix is SOO dang good!
This works now:


var squares = \{ (?x,?y) : int * int | y == x * x \} ;
println$ (3,9) \in squares;
 
The general form is

	\{ pattern : type | predicate \}

A predicate is any expression evaluating to bool, which may use
the variables in the pattern match. We have to specify the type
of the pattern, and our patterns have ugly ? in them sometimes,
but otherwise this is similar to a mathematical set.

A set_form is a real object. Any object with a method

	has_elt: T -> bool

acts like a set courtesy of these definition in std/algebra/set.flx:

interface set_form[T] { has_elt: T -> bool; }
fun \in[T] (elt:T, s:set_form[T]) => s.has_elt elt;

If your object has other methods you can "cast" them away
with a coercion to meet the specification.

It's easy to define the union now:

	fun \cup[T] (A:set_form[T], B:set_form[T]) => \{ ?x : T | x \in A or x \in B \};

I will do some more work on this.

* At present, \{ \} can must be used. It's possible the parser will work with plain {}

* To display it right you need to go into math mode:

	\( \{ (?x,?y) : int * int | y == x * x \} \)

which will also display the \( \) parents ;( I may be able to fix this,
I'm not sure: not all program code looks right in math mode.

* \mid works better than |, whether it should be allowed,
or flx_web should just change the | I don't know (matches
can be used in the expression so it could be confused .. )

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

Re: [Felix-language] [felix] Design issue

[john s. <sk...@us...>]

On 26/03/2015, at 5:30 AM, Martin DeMello wrote:

>>> I believe this is where you went wrong - a set isn't a container with
>>> a membership operator, it's a container with a membership operator and
>>> the property that all elements are distinct.
>> 
>> How would you specify that property?
> 
> You can't without dependent types, certainly. (I'm not even sure you
> can *with* dependent types; I know very little about them). In actual
> code you could always maintain the invariant by simply removing
> duplicates on all set-modifying operations.

I think you're missing the point.

	class Set[C,T] { virtual fun \in : T * C -> bool; }

defines a Set as a data type with a member operator.

Now, an array, even with duplicate values stored,
can satisfy the axiom, because there's no requirement
about duplication of elements in an array. 

Note there's also no requirement for an equality operator,
and no size. This is not your usual mathematical set.
I actually defined a Container as a Set with a length operator.

Consider a regexp: RE2 "(a|b)*abb". That's a set, using the obvious
rule that a string that matches the regexp is in the set.

Consider also:

	class MultiSet[C,T] { virtual fun count: T * C -> int; }

I hope it's clear there is a natural transform from MultiSet to Set
using

	fun non-zero (x:int) => x != 0;

Now also consider this:

	instance[T,N] Set[T^N,T] { fun \in (x:T, a:T^N) => x not-in a; }

That's a perfectly good model of a set too. It's an infinite set,
in this model:

	assert 1 \in (2,3);

That really is the crux of the problem. An array can be used in an
infinite number of ways as a set. You could even use

	9 in (1,2,3)

given by the fact 9 is the square of 3. It's a design fault in the whole
concept of type classes.

The problem is seen to be serious if you then pick one, and then
you inherit Set into a more constrained class and that constraint
can't be met. For example, and this is *the* example at hand,
if you have Eq for equality and Set as above, and you then want
a subset relation, SetOrd, you're screwed, because array equality
and set equality required for SetOrd aren't compatible.

One can certainly DEFINE an array equality that works for sets,
by ignoring duplicates. So we're back to the original point:

	TYPE CLASSES DO NOT WORK  

We can actually fix the problem, just use

	union[T,N] ArrayAsSet_t = ArrayAsSet of T^N;
	instance[T,N] Set[ArrayAsSet_t[T,N],T] { ... }


Note that:

////////////////////
open class Streamable[ContainerType, ValueType] {
  virtual fun iterator : ContainerType -> 1 -> opt[ValueType];

  // check if a streamable x is a subset of a set y.
  fun \subseteq[T with Set[T,ValueType]] (x:ContainerType, y:T) = 
  {
    for v in x do
      if not (v \in y) goto bad;
    done
    return true;
bad:>
    return false;
  }
}
//////////////////////

works fine and is in the library. There's just no way to use THAT
subseteq operator to define an instance of SetOrd[C1, C2] because
it requires a third type (the ValueType], whereas the set comparisons
don't need that.

Ocaml functors just work better because you have to supply a whole
package as an argument, that is, the functor accepts the type
parameters AND the instance functions. With type classes you can
only define one function for each list of type arguments.

So for example you can make array-as-set in 10 different ways
by giving 10 different functions for the membership operator.


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

Re: [Felix-language] [felix] Design issue

[john s. <sk...@us...>]

On 25/03/2015, at 1:26 PM, Martin DeMello wrote:

>> 
>>        Set -- membership operator
>>        Container -- as set with a size operator (i.e. a finite set)
>> 
> 
> I believe this is where you went wrong - a set isn't a container with
> a membership operator, it's a container with a membership operator and
> the property that all elements are distinct.

How would you specify that property?

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

[Felix-language] Design issue

[john s. <sk...@us...>]

I have just run into an interesting problem. 

I like pretty math operators so I've been making the TeX symbols
for set comparisons work. Stuff like \subseteq for example.

Now, at the moment you can write:

	x \in (1,2,3,4)

and it works. This is because "an array is a Set". FYI we have these
basic concepts:

	Set -- membership operator
	Container -- as set with a size operator (i.e. a finite set)

as well as Eq (equivalence relation, equality), Pord (partial order),
and Tord (total order).

I decided to do SubSet, with the nice curvy comparisons for sets from
maths: its just a Set with \subseq and \subseteq defined, the other
operators are derived. I did this:

class SubSet[c] {
   inherit Eq[c];
   virtual fun \subseteq: c * c -> bool;
   virtual fun \subset (x:c, y:c) => x \subseteq y and not x == y;
   fun \subseteqq (x:c,y:c) => x \subseteq y;

and then I realised WHOA! Hold on there!!

These arrays are subsets:

	(1,2) \subset (1,2,3,4)

Sure, but then what about this:

	(1,2) \subseteq (1,1,2)

It's a subset, and as sets, these arrays are equivalent.
But as themselves, as arrays, they're NOT equal.

On the other hand, whilst set operations for a partial order,
arrays with a total order on the element type can also form
a total order with lexicographical comparison.  And that
order is not the same as the setwise ordering!

Unfortunately, we don't have an == operator for sets, distinct
from arrays, even if we can use < and \subset distinctly to
provide two distinct orderings.

In general this is a "bug" in the idea of type classes.
In Haskell too. Ocaml functors are correct, type classes
are canonical functors and so only cover common cases.

Another example is Tord[int]. It's an ascending order.
But there is a perfectly good *descending* total order as well.
We can fix this by using

	union revint = Rev of int;

Now we've made a new type, we can define a reverse order
on it so

	Rev 1 > Rev 2

There's no performance cost (unions of one constructor are downgraded
to the constructor's argument after binding is complete).

But this is not very general .. it only applies to a single type.
[Generalised Algebraic Data types (GADTs) might help, I don't know]

However all this is suggesting the I am confusing an array with 
"an array considered as a set". And that there should be a
*conceptual* meta type "SET" and that we should have
to CAST an array to it to consider it as a set.

	x \in SET (1,2,3,4)

Note that SET is a functor from TYPE to SET, there is no actual
thing SET, it's not a data type (it's a meta type!).

The point is this:

	SET (1,2) == SET (1,1,2)
	(1,2) != (1,1,2)

I have to think what this means exactly .. especially as for some types
there may be more than one way to use that type as a model for
something else, and, because the idea doesn't just apply to a single
type, but perhaps several (eg a tree with labels on edges and nodes
of a distinct type, or, an abstract container C with a value type T).

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

Re: [Felix-language] [felix] pointers

[john s. <sk...@us...>]

On 22/03/2015, at 5:16 AM, Ryan wrote:

> Complicated but interesting problem. I never quite realized how exactly Felix gets rid of lvalues until now, and I like it.

Actually this is the model. The actual compiler terms still use assignment :)

One reason for this is that for compact linear types, there is no pointer.
Which is a serious pain. For example the type

	2 * 3 // read as bool * sign: bool has 2 cases, sign has 3 (-ve, 0, +ve)

as an ordinary tuple would use two * 32bit words (on x86_64). But as
a compact linear type:

	int = 3 * x + y // only uses values 0 upto 5

it only uses 1. C has compact linear types, namely bit fields, but they
only handle types which are powers of 2. The problem is the same:
they're not addressable. But you can still do an assignment with
a get, modify, store.

There's another reason to use assignment internally: if you use pointers
you have an aliasing issue which in general requires dataflow analysis
to solve, which is O(N^3) or worse algo.  But with variables, it's easier,
no flow is needed to know which store is modified.

Conceptually, however, it's simple: pointers represent objects,
everything else is a value (and pointers themselves are values).

Which leads directly to the problem, how to specify an abstract
type is pointer like, that is, it represents a mutable data structure.

In C++ you'd use const to convert a pointer (mutable object)
into a value (immutable object) but this obviously cannot
work because of aliasing. You have to throw in "restrict" to
provide a function local solution. 

In a real language like ATS you'd use linear types.
C++ has rvalue binders now which provide some
of that functionality.

> 
> As for getters/setters, I can agree they're not the best.

They're intractable, that is, completely out of the question.
if you have an array of arrays, and you want to modify an element
of the inner array, with get/set you'd have to do this:

	var inner = get (a,i);
	set (&inner, j, v);
	set (&a,i,inner);

which requires COPYING the whole inner array twice. For an array
of some size this is an unacceptable performance problem.
So get/set is ruled out. It's not acceptable. But at least in this
case it works. 

Note, writing a 2 argument get/set is NOT allowed, because that
defeats combinatorial composition. You have to be able to create
new data functors (generic data types) by composition.

however the performance issue isn't a theoretical blocker,
just a pragmatic one. Using get/set doesn't even work in theory:
just consider an uncopyable data structure for example
a mutable tree. Or, a doubly linked list. You can't use copying
because there are pointers into the data structure elsewhere.

But get/ref works, because it ref gives you a pointer into
the data structure. (In fact you don't need get, if you have ref,
since get is just the deref of a ref).



> Whenever I write C++ code, I just make all the attributes I'll likely need to access public. That has the issue that getters and setters try to resolve where you can no longer change some implementation details because you'll break everything.

This can't arise if the data type is a product.

If the type is a product WITH AN INVARIANT then you need to hide
the product to enforce the invariant. In this case, getting and setting
fields is nonsense anyhow: if there's an invariant the data type
IS NOT a product. Rational numbers, for example, are not products
of integers

	(numerator, denominator)

because the numerator can't be 0. Furthermore, for performance, one
usually applies the invariant that the denominator must be positive,
and the two integers must be relatively prime. That makes the representation
unique so comparisons are O(1) (two rationals are equal if and only 
if their representation is equal).

But with rationals, the very idea of get/set the numerator or
denominator is pure rubbish, because they're not well defined.

> 
> Python and Objective C solve this with properties. Which I like.
> 
> But Felix doesn't have this problem since `x.y` is a function call anyway. Cool.

Yeah. For a product, the attribute is a projection. However you can have
non-projection functions. Also, there can be more than one "basis" for
a product type, that is, more than one pair of projections may exist.

For example a well known one: for a pair of integers, instead of

	first, second

you can use the pair of functions

	first + second, first - second

which is, in fact, how colour analogue television works (RGB is actually
represented as black and white and two difference signals,
which makes it easy for a B/W TV set to decode the signal).

Another "almost" example is complex numbers (cartesian and polar
representations).

It is important to understand that for a product, the chosen canonical
projections ARE the representation. There's no such thing as data.
The names of "member variables" in a class are FUNCTIONS.
Even in C++. Fields are just projection functions.

Lvalues just provide a very bad way to model what Felix finally
does correctly.

More generally,  given isomorphic representations of products,
one might consider an abstraction, with multiple functions.
For example for complex you provide

	get_x, get_y, get_r, get_theta 

as well as anything else. Then you provide axioms which tell you which
combinations form a basis.

This problem, generalised, is a serious issue with type classes.
Consider a total order:

	== <

the problem is we want also

	!= <= >= >

In fact, some times < is fundamental and sometimes <=. So when we
instantiate a total order the requirement SHOULD be to provide
a basis of definitions, and the derived definitions should be generated.

But what Felix (and Haskell) ACTUALLY do is force the basis.
In Felix

	virtual fun < ...  // axiom
	virtual fun == ... // axiom
	fun > (x,y) =>  y < x // derived

Really ALL the functions should be virtual, with defaults, so that if you provide
enough functions the others get defined (by the defaults). If you provide too
many, then that's OK provided they obey the axiomatic relations. You might
do this for performance. And if you don't provide enough, the compiler barks at you.

I have no idea how to do this. Neither do the Haskell people.
You can't even provide defaults, because what works for a derived
function depends on which other functions are specified by the user.

In case you're wondering the relevance: OO is utterly WRONG by thinking
just because you provide functions, you have an abstraction and avoid
representation details.

First, fields (data representation) are ALREADY functions (projections).
And secondly, even if you hide that the set of access methods you
provide are STILL a concrete representation. What hiding does
is hide which functions are axioms and which are derived, they
all become properties (lemmas) which makes the axiomatisation
arbitrary. So it is "more abstract" than before, but that's the end
of it. 

And the real crux of the matter arises when you have a mutable
data type, because you cannot easily set a new value in pieces.
You cannot just "set" the numerator, then the denominator,
of a rational number.


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

Re: [Felix-language] [felix] pointers

[Ryan <ry...@gm...>]

Complicated but interesting problem. I never quite realized how exactly Felix gets rid of lvalues until now, and I like it.

As for getters/setters, I can agree they're not the best. Whenever I write C++ code, I just make all the attributes I'll likely need to access public. That has the issue that getters and setters try to resolve where you can no longer change some implementation details because you'll break everything.

Python and Objective C solve this with properties. Which I like.

But Felix doesn't have this problem since `x.y` is a function call anyway. Cool.

john skaller <sk...@us...> wrote:
>Hi, I am still grappling with this problem:
>
>Felix has a rule for concrete data types, in particular products.
>We have quite a few product type: tuples, records, structs, arrays.
>
>Products are characterised by projection functions.
>Each product type has a different way of naming them.
>We like for a record type:
>
>	typedef r_t = (p1:int, p2:int);
>	val r : r_t = (p1=1, p2=2);
>
>to express projections like:
>
>	r.p1
>
>in the OO tradition. Felix says p1 is an ordinary function thingo,
>and 
>
>	x . f
>
>means exactly the same as
>
>	f x
>
>so we can also write:
>
>	p1 r
>
>Consequently you can write this too:
>
>	1 (1,2) == 2
>
>because (1,2).1 == 2. Of course 1 isn't a projection but an integer,
>but Felix translates the application of an integer to a tuple to the
>application of the corresponding projection.
>
>So far so good. Now we also have this notation:
>
>	p <- v;
>
>which means, store the value v into the location p.
>We require the type of p and v to be &T and T respectively for some T.
>
>So now if you have
>
>	var x : int;
>
>you can assigned to x like:
>
>	x = 1;
>
>but this is just sugar: Felix translates it to:
>
>	&x <- 1;
>
>It is important to note here that & is NOT an operator. Rather
>
>	&x
>
>is the real name of the variable, that it, it is the machine address
>of the associated storage. &x is a name. The syntax
>
>	x
>
>is actually short hand for 
>
>	*(&x)
>
>Note we could have made "x" the name of the address, but to make Felix
>look like C we don't. Nevertheless there is something very important
>going
>on here:
>
>	WE HAVE GOTTEN RID OF THE CONCEPT OF LVALUES
>
>[Except in C bindings where we still need them but lets gloss over that
>:]
>
>Now, in C you can write:
>
>	s.x = 1;
>
>where s is of a struct type with a field x. In Felix this would
>translate to
>
>	&(s.x) <- 1;
>
>which is nonsense!! Remember, & is not an operator. It is just part of
>the name of a variable. So this would be OK:
>
>	(&s).x <-1
>
>But how do we make that work? Isn't the "x" here a projection?
>And don't projections apply to product types? But &s is not of a
>product
>type, it's a POINTER to a product.
>
>So the solution? Make projections apply to pointers to products as
>well!
>
>In particular, if
>
>	p: P -> V
>
>then
>
>	P: &P -> &V
>
>as well, in other words, if you apply a projection to a pointer to a
>product
>you get a pointer to the corresponding field.
>
>This in turn makes it possible to store a value into a PART of a
>product.
>
>In particular, this makes a GOLDEN RULE (at least for products):
>
>	VALUES ARE IMMUTABLE
>
>If you want to store into a value, stick it into a variable!
>
>	VARIABLES HOLD MUTABLE OBJECTS
>
>The key thing is ALL product values can be made mutable by simply
>sticking them into a variable, then using the required chain of
>projections
>on the variable's address:
>
>	var x = (1,2);
>	1 &x <- 42;
>
>Yep. That works! It has to. The projection 1 applied to the tuple
>object x
>returns a pointer to the second component which can then be stored
>into.
>
>The symmetry is very nice!
>
>THE PROBLEM
>============
>
>This all works just great! For concrete data types. That is,
>one where the compiler knows about the projections.
>
>But for an ABSTRACT data type, it doesn't work automatically.
>
>Suppose you have an array abstraction A,  and some value a
>and a method:
>
>	a.get 1;
>
>to get the second component. So find we can write:
>
>	fun apply (p:int, a:A) => a.get p;
>
>and NOW we can indeed write
>
>	a.1
>
>because that means 1 a, and "apply" methods are a way to teach
>the compiler how to apply non-functions to values. We can even 
>do this: provide a method:
>
>	(&a).get 1; // returns a POINTER
>
>and then an apply function can be used again to allow this:
>
>	(&a).1 <- 42;
>
>But there's a problem! That's not how a varray works.
>
>A varray is literally a pointer underneath. So it is intrinsically
>mutable. Like many mutable data structures, you don't need to
>store it in a variable to store into its parts.
>
>A varray acts like a value AND like an object.
>
>There's also a major safety problem. With a concrete data type
>
>	var x = 1,2;
>	var p = &x.1;
>
>we have a pointer interior to the tuple, which can hang about.
>In this case that's just fine, it cannot dangle, and it can only point
>into a specific variable.
>
>But that's not true for mutable data types. In particular for a varray,
>a pointer into one cannot dangle, but it certainly can point past
>the end of the used part of the array (just point to the last element,
>then pop it off the end with pop_back).
>
>It's much worse if the data structure is hiding a C++ one!
>
>It is essential to use a pointer to store a value.
>
>get/set methods DO NOT WORK.
>This is an OO stupidity. Assignment isn't the only mutator.
>Increment is another one. And if you have say, an array then
>
>	set (a, index, value)
>
>looks fine until you consider that the value could be another product
>which a component that is another product...  you then get a complete
>mess of sets and gets because you have to do a modification to
>a temporary and store it back (because a get returns a value ..).
>
>What works is get/ref: get a value, get a reference. But the reference
>must be transient (linearly typed, so it must only be used once, and
>immediately). Note that get/set DOES enforce this (by hiding the store
>address).
>
>So there's the conundrum. In particular in my recent code I had to
>write:
>
>	set (a,index,v)
>
>even for a varray. The old notation
>
>	a&.index <- v
>
>doesn't work because the &, function is never invoked because now
>the PARSER translates
>
>	x*.y ==> (*x).y // which equals *(x.y)
>	x&.y ==> (&x).y
>
>to enforce the interpretation above. The problem is i want both
>
>	a . 1 // second component of varray a
>	a . 1 <- 42; // assign 42 to first component
>
>to work, the first because that's how ordinary arrays work and the
>second because a is really a pointer already so we do NOT want
>to have to take the address of "a" to store into it.
>
>--
>john skaller
>sk...@us...
>http://felix-lang.org
>
>
>
>-- 
>You received this message because you are subscribed to the Google
>Groups "Felix Language" group.
>To unsubscribe from this group and stop receiving emails from it, send
>an email to fel...@go....
>To post to this group, send email to fel...@go....
>Visit this group at http://groups.google.com/group/felix-language.
>For more options, visit https://groups.google.com/d/optout.

-- 
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
Check out my website: http://kirbyfan64.github.io/

[Felix-language] pointers

[john s. <sk...@us...>]

Hi, I am still grappling with this problem:

Felix has a rule for concrete data types, in particular products.
We have quite a few product type: tuples, records, structs, arrays.

Products are characterised by projection functions.
Each product type has a different way of naming them.
We like for a record type:

	typedef r_t = (p1:int, p2:int);
	val r : r_t = (p1=1, p2=2);

to express projections like:

	r.p1

in the OO tradition. Felix says p1 is an ordinary function thingo,
and 

	x . f

means exactly the same as

	f x

so we can also write:

	p1 r

Consequently you can write this too:

	1 (1,2) == 2

because (1,2).1 == 2. Of course 1 isn't a projection but an integer,
but Felix translates the application of an integer to a tuple to the
application of the corresponding projection.

So far so good. Now we also have this notation:

	p <- v;

which means, store the value v into the location p.
We require the type of p and v to be &T and T respectively for some T.

So now if you have

	var x : int;

you can assigned to x like:

	x = 1;

but this is just sugar: Felix translates it to:

	&x <- 1;

It is important to note here that & is NOT an operator. Rather

	&x

is the real name of the variable, that it, it is the machine address
of the associated storage. &x is a name. The syntax

	x

is actually short hand for 

	*(&x)

Note we could have made "x" the name of the address, but to make Felix
look like C we don't. Nevertheless there is something very important going
on here:

	WE HAVE GOTTEN RID OF THE CONCEPT OF LVALUES

[Except in C bindings where we still need them but lets gloss over that :]

Now, in C you can write:

	s.x = 1;

where s is of a struct type with a field x. In Felix this would translate to

	&(s.x) <- 1;

which is nonsense!! Remember, & is not an operator. It is just part of
the name of a variable. So this would be OK:

	(&s).x <-1

But how do we make that work? Isn't the "x" here a projection?
And don't projections apply to product types? But &s is not of a product
type, it's a POINTER to a product.

So the solution? Make projections apply to pointers to products as well!

In particular, if

	p: P -> V

then

	P: &P -> &V

as well, in other words, if you apply a projection to a pointer to a product
you get a pointer to the corresponding field.

This in turn makes it possible to store a value into a PART of a product.

In particular, this makes a GOLDEN RULE (at least for products):

	VALUES ARE IMMUTABLE

If you want to store into a value, stick it into a variable!

	VARIABLES HOLD MUTABLE OBJECTS

The key thing is ALL product values can be made mutable by simply
sticking them into a variable, then using the required chain of projections
on the variable's address:

	var x = (1,2);
	1 &x <- 42;

Yep. That works! It has to. The projection 1 applied to the tuple object x
returns a pointer to the second component which can then be stored into.

The symmetry is very nice!

THE PROBLEM
============

This all works just great! For concrete data types. That is,
one where the compiler knows about the projections.

But for an ABSTRACT data type, it doesn't work automatically.

Suppose you have an array abstraction A,  and some value a
and a method:

	a.get 1;

to get the second component. So find we can write:

	fun apply (p:int, a:A) => a.get p;

and NOW we can indeed write

	a.1

because that means 1 a, and "apply" methods are a way to teach
the compiler how to apply non-functions to values. We can even 
do this: provide a method:

	(&a).get 1; // returns a POINTER

and then an apply function can be used again to allow this:

	(&a).1 <- 42;

But there's a problem! That's not how a varray works.

A varray is literally a pointer underneath. So it is intrinsically
mutable. Like many mutable data structures, you don't need to
store it in a variable to store into its parts.

A varray acts like a value AND like an object.

There's also a major safety problem. With a concrete data type

	var x = 1,2;
	var p = &x.1;

we have a pointer interior to the tuple, which can hang about.
In this case that's just fine, it cannot dangle, and it can only point
into a specific variable.

But that's not true for mutable data types. In particular for a varray,
a pointer into one cannot dangle, but it certainly can point past
the end of the used part of the array (just point to the last element,
then pop it off the end with pop_back).

It's much worse if the data structure is hiding a C++ one!

It is essential to use a pointer to store a value.

get/set methods DO NOT WORK.
This is an OO stupidity. Assignment isn't the only mutator.
Increment is another one. And if you have say, an array then

	set (a, index, value)

looks fine until you consider that the value could be another product
which a component that is another product...  you then get a complete
mess of sets and gets because you have to do a modification to
a temporary and store it back (because a get returns a value ..).

What works is get/ref: get a value, get a reference. But the reference
must be transient (linearly typed, so it must only be used once, and
immediately). Note that get/set DOES enforce this (by hiding the store
address).

So there's the conundrum. In particular in my recent code I had to write:

	set (a,index,v)

even for a varray. The old notation

	a&.index <- v

doesn't work because the &, function is never invoked because now
the PARSER translates

	x*.y ==> (*x).y // which equals *(x.y)
	x&.y ==> (&x).y

to enforce the interpretation above. The problem is i want both

	a . 1 // second component of varray a
	a . 1 <- 42; // assign 42 to first component

to work, the first because that's how ordinary arrays work and the
second because a is really a pointer already so we do NOT want
to have to take the address of "a" to store into it.

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

[Felix-language] graph algos

[john s. <sk...@us...>]

I have done Felix version of Skiena's representation of a graph,
and a breadth first search.

As usual i'm less interested in the representation as such than the typing,
abstraction, etc. However, Skiena's representation makes me feel uneasy.

  typedef digraph_t = (vertices: darray[vertex_t], nedges: int);

  // x index implicit, the edge source
  // y index is the edge destination
  typedef edge_t = (elabel:E, y:int, weight:int); 
  typedef vertex_t = (vlabel:V, outedges: list[edge_t]);

1. Skiena uses a flag to tell the difference between an undirected and
directed graph. I have only a digraph here. It's not clear to me the
two things shouldn't be completely distinct, even though an undirected
graph can be represented by a digraph with edge pairs (x,y) and (y,x).

2. The rep is compact, but the edge type doesn't tell the source of the
edge, it's implicit from the position in the array. I don't like that,
the *actual* edge required a pair int * edge_t.

3. Using integers to represent vertices leaves open the problem
of how to properly build the graph. I solved that by adding default
vertices to fill up the list up to the currently specified maximum integer.

My graph has both edge and vertex labels, but these can't be assumed
unique. But identifying by integer is a plain wrong. It may be OK for a static
graph, but even after construction of a graph, one might like to perform
mutations.

IMHO pointers are just plain better. They provide unique if arbitrary
identification. And they allow mutation in a fairly natural way.
Deleting an edge in Skiena's rep is ok, but deleting a vertex
isn't really possible (at best you can isolated it).

4. One of the core things about graphs is that a set of vertices 
and edges can often generate other graphs: search order trees,
parents for them, spanning trees, etc etc. Generally doing this
should not require a modification to the original graph,
but often we would like to share the vertices.

5. Note that one of the most important "theoretical" uses of a graph
is that every graph generates a category, namely the set of all
paths in the graph (with identity paths for each vertex added).




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

[Felix-language] assignment fun

[john s. <sk...@us...>]

I wrote this:

  proc push_front (dl:&dlist_t, v:T) { 
    var oldfirst = dl*.first;
    var node = new (data=v, next=oldfirst, prev=nullptr[dnode_t]); 
    dl.first <- Ptr node;
    match oldfirst with
    | nullptr => dl.last <- Ptr node;
    | Ptr p => p.prev <- Ptr node;
    endmatch; 
  }

This is for a doubly linked list. Now I will show you the beauty of the pointer projection semantics:

   match oldfirst with | nullptr => dl.last | Ptr p => p.prev endmatch <- Ptr node;

In fact we can do better if we like convoluted expressions:

	proc asgn2[T] (p: &T, q:&T) (var v:T) { p <- v; q <-v; }

to save writing "Ptr node" more than once :)

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

[Felix-language] interesting problem

[john s. <sk...@us...>]

I recently changed the parser to ensure:

  x[sfactor_pri] := x[sfactor_pri] "*." sthe_name =># "`(ast_dot ,_sr ((ast_deref ,_sr ,_1) ,_3))";
  x[sfactor_pri] := x[sfactor_pri] "&." sthe_name =># "`(ast_apply ,_sr (,_3 (ast_ref ,_sr ,_1)))";


The first one should actually read like the second. In Felix notation

	p*b == (*p).b
	a&.b == (&a).b

If b is a projection of a product (tuple, struct, record, array) then

	(*p).b == *(p.b)

Ok, so here's the problem. With any ArrayObject such as varray i have overloaded &. to mean

    fun unsafe_get_ref: varray[v] * size -> &v = "$1+$2";

which is invoked by

  fun n"&." [I in ints] (x:t, i:I) : &v = {
    assert i.size < x.len; 
    return unsafe_get_ref (x,i.size); 
  }

but this overload no longer works.

So here's my problem: Classes cannot say 

	"for all products. p&.b means &p.b"

What I mean is you would have to overload, manually, EVERY product
you use: tuples, records, etc etc. you can use a class to do this for 
arrays though. I had done that. But it isn't acceptable that records
and tuples work the same way.

Here's a related issue. For any value type, if you put it in a variable
it is mutable. In particular its *components* should be mutable.
[This is only product types, not functions and at the moment not
unions]

That comes from the compiler support, every projection the
compiler generates for a value extraction:

	v.proj

is overloaded to also provide a pointer extraction:

	(&v).proj

The problem comes with things like varray, and darray, and other
mutable data structures.

Because these data structures are effectively pointers .. in the case
of a varray recall a varray is *precisely* just a pointer to a C array
(with length monitored by the GC), you can store a value or extract
a pointer from a varray VALUE. It doesn't need to be put into a variable.

One has to think that a varray IS a pointer, or at least like one, 
to proceed.

Whatever problems this causes for the programmer conceptually,
they will get a lot worse if we can't use familiar notation.

Many data structures provide get_ and set_ method. 
This solves the problem for whole elements. 

Unfortunately with composed data types, get/set is useless.
Just think of

	// extract 3 deep into product type:
	var v0 = a.get i0;
	var v1 = v0.get i1;
	var v2 = v2.get i2;

	// modify component
	set (&v2,i3 newval);

	// now put it back in place in higher components
	set(&v1,i2,v2);
	set(&v0,i1,v1);
	set(a,i0,v0);


In C++ this is just

	a.i0.i1.i2.i3 = newval;

I hope the problem is clear. For value types you have to store in
a variable to get a pointer:

	&v

Recall & is NOT an operator. It's just a way of saying the name of the
address of a variable.

So the concept is

	v&.p

means

	(&v).p

for a product, but

 	get_ref (v,p) // returns an actual pointer

for an abstract data type which "is" a pointer, i.e. any value
which represents a mutable data structure.

The problem is "get_ref" can't work with a variable.
	
--
john skaller
sk...@us...
http://felix-lang.org

Re: [Felix-language] [felix] New data types

[john s. <sk...@us...>]

On 12/03/2015, at 9:13 AM, Martin DeMello wrote:

> Good luck! Also I'd strongly advise practise implementations in C or
> C++ as well - I nearly blew an interview question because I wasn't
> sure how to build a string in a recursive function.

yes .. well .. I have to study up on algorithms, when first went to uni
I learned Fortran in the maths dept using Mark-Sense cards.
There was no computer science department until my second year.

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

[Felix-language] New data types

[john s. <sk...@us...>]

I am going for a job interview soon where I need to know some
basic algorithms and data structures stuff .. I know about the stuff
using in the Felix compiler but I studied the basics a LONG time ago.

So i need to brush up. I'll have to demo my skills in C++ in the interview..
YUK! And I need to practice and learn the stuff again so ..

I am going to do this stuff in Felix. It will improve Felix, both by
enhancing the library and as usual showing up weaknesses in
the language.

Hopefully it will also improve my rusty knowledge. I hope when the
time comes I can write this stuff in C++... :)

First job: binary search trees. I'm using Skiena as the core
reference. It's very good IMHO. Written for programmers not
computer scientists with examples in C. Very clear and easy
to read.

http://sist.sysu.edu.cn/~isslxm/DSA/textbook/Skiena.-.TheAlgorithmDesignManual.pdf

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

[Felix-language] GUI

[john s. <sk...@us...>]

I have finally found a bug causing Felix GUI code to crash on resizing a window.

It turns out this is a bug in SDL itself.

+1 to Felix. -1 to C.

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

[Felix-language] compact linear types

[john s. <sk...@us...>]

So with the new method, I'd allow

	\times
	*

for multiply, and use \otimes and \oplus for compact linear product and sum.
But I have no idea what to do for exponentiation. The usual ^ has no TeX
analogue. Unless I use \uparrow ..hmm.


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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 13/02/2015, at 3:40 PM, srean wrote:

> In that case let it be. enough of syntax bikeshedding :)

I do not have a good solution for low level loops at the moment.

I do think I have one for compact linear types though.

The problem with compact linear types at the moment is this:
Felix has a *principle* which says mutators require a pointer.
So 

	var x ...
	&x <- v; // assignment

One reason for this is that it gets rid of lvalues as a concept.
More properly, it lays out very clear picture of the relationship
between values and objects, at least for product types.

Given a product object P with projection function j, then

	val P = ..
	j P = P.j

extracts the p component of a value and

	var P = ...
	(&P) . j

is a *pointer* to that component (allowing it to be mutated).

Note that for a variable P is "really" a pointer. The name of the
variable is actually &P, that is, & is NOT an operator. It's just
a part of the variable name, so there's no issue of applying
it to an expression. If you like the variable is an lvalue, but
no other expression is an lvalue.

Instead, projections are overloaded, there are two projections
named j

	j: T -> U
	j: &T -> &U

I hope you see this is quite a beautiful picture.

But compact linear types ruin it! There are certainly
value projections for type

	3 * 2

considered as compact linear, but pointers to these
do not exist. We could have them we need a triple of
to make one:

	address, divisor, modulo

If the type has size only limited by address space.
the divisor and modulo would need to be 67 bits each
on a 64 bit machine (although that's unrealistically large).

In any case such pointers aren't 64 bits like an ordinary
address.

The problem is, a pointer to 3:

	&3

might be an ordinary address is embedded in a non-compact linear type:

	int * 3 * string

but that information is not available just from the type

	&3

It's nonsense. The only way to make it work would be for ALL
addresses to be triples. It's too expensive.

The solution is that we cannot use

	* +

for compact linear type formation. We must use instead:

	\otimes, \oplus

These form compact linear product and sums from compact linear types,
and cannot be applied to non-compact linear types. So for example we
can have

	int * 3 * 6 * string
	int * 3 \otimes 6 * string

The first product has 4 addressable components, the second one
only has 3. Value projections exist for compact linear type component
but either there are no address projections, or, we have a different
type of address such as 

	\oampersand // no such TeX operator but hope you get intent


With this idea, the compiler code for compact linear types is
much simpler because we don't have to pattern match to 
find the boundaries etc. It's also sound. The current method
really isn't sound.

The main issue is that \otimes, \oplus are not combinators.
Their arguments must be compact linear.

There IS a way to handle this and retain parametricity.
Normally an operator is a function from

	TYPE -> TYPE // or
	TYPE * TYPE -> TYPE

All we need to fix it is a new meta-type:

	CLTYPE

for compact linear types. It's a different category.

This means a type variable has to have kind annotation:

	fun f[T:TYPE, CLT: CLTYPE] (x:T, y:CLT) => ....



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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 12/02/2015, at 9:12 PM, srean wrote:

> Vim has syntax highlight files for M4 which has mismatched parenthesis. 
> 
> Felix allows range boundaries to be inclusive or exclusive and I quite like the [ ... ),
> ( ...], [ ...] and ( ... ) syntax for that.
> 
> Web syntax  highlighters would probably break on these, vim does OK, I guess  Emacs would do fine too.

Plain ( ) [] would probably break all the tools and the parser
(in *any* combination, balanced or not).

I'm not sure about \left[ etc (the TeX notation).


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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 12/02/2015, at 8:41 AM, Ryan Gonzalez wrote:

> I wrote a basic Pygments-based IDE in Python + Gtk+. Other than the fact it was really slow when pasting text, it wasn't that bad. It highlighted Felix and Nim out-of-the-box.

Felix *.flx highlights are a bit tricky. My Vim stuff is an ugly mix of C and Python
hilighting code.

*.fdoc's are another story ;(

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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 12/02/2015, at 12:57 AM, Shayne Fletcher wrote:

> 
> On Wed, Feb 11, 2015 at 7:26 AM, john skaller <sk...@us...> wrote:
> Ocaml lacks the ability for the end user to extend it.
> 
> ​In the context of this discussion, I don't think that is entirely correct. As of 4.02, OCaml has "extension points"​ (-ppx). See this post http://www.lexifi.com/blog/ppx-and-extension-points.
> t.

I had an argument with Minsky about this :-)

I do not like it at all. However, it is only a pre-processing feature.
It doesn't allow Ocaml code to be extended.

It's also a supreme hack, unreadable crud, all so Minsky could
continue to use his Emacs IDE (because it doesn't actually
change the Ocaml syntax). What Felix does is much better
and bad luck to IDE weanies with weak IDEs that can't be
extended. (I use Vim as a weak IDE and have no problem
extending it, but Ocaml IDE support often does a lot more
like mouse-overs showing function types).

Ocaml does have Dynload, which *does* allow extensions.

However Dynload has some serious limitations since it mandates
preservation of a rigid static typing system. It also requires having
an Ocaml compiler available. And it's only available with either
bytecode or on x86_64 processor with native code.

Felix of course has a similar dynamic loading scenario using
plugins: there are (theoretical) static typing constraints.

However, Felix is "in principle" an interpreter of text.
So extensions on the front end are more like Ocaml
with a pre-processor running bytecode.

The problem is Felix runs Ocaml native code. We can't
afford the compiler to be bytecode, its too slow.

So in practice, extending flxg with library code can't
really be done by Ocaml's extension features.

Dypgen+OCS scheme is much more powerful, natural,
and too bad if you think an IDE is more important than
a language. Felix isn't Java. You don't need a complex IDE
to write, read, or refactor it. In fact flx IS already an IDE.
It's just a command line based one.

If I can get SDL to actually work and get the idiots to put 
mouse capture into it, we might end up with a graphical
IDE for Felix anyhow. I already have a (extremely slow)
syntax colouring editor written.

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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 10/02/2015, at 3:42 PM, Martin DeMello wrote:

> On Mon, Feb 9, 2015 at 2:56 PM, john skaller
> <sk...@us...> wrote:
>> 
>> I would actually like to rework the whole front end of the flxg
>> compiler in scheme. What I mean is that the core workhorse
>> algorithms would still be in Ocaml, but they'd be sequenced
>> by scheme code. OCS Scheme is written in Ocaml and allows
>> extra primitive procedures and data types written in Ocaml to
>> be added to it.
> 
> What is the motivation behind that? OCaml strikes me as a much nicer
> language than scheme to write compilers in (much as I love scheme).

Ocaml lacks the ability for the end user to extend it.

On can't extend the Felix system by separately compiled
dynamically loaded plugins with Ocaml (at least not with the
native code compilers). Yes, Ocaml has dynamic loading but it
is fairly restricted in scope.

At present a lot of constructions were added by me by just writing
a bit of grammar and some scheme that emitted some sequences
of existing terms. The compiler flxg just reads the grammar files
as part of the "library".

I picked scheme because 

(a) it's vaguely functional
(b) it's interpreted (more or less)
(c) its fairly good at producing ASTs 
(d) there was a readily available library for Ocaml (OCS scheme)
(e) scheme is a "standard" language

So I'm not talking about writing the compiler in scheme, but organising
the sequencing of the phases in scheme, and also providing hooks
for users to intervene at appropriate points with library code.

Constant folding is the motivating example. It's done in Ocaml
at the moment. For bool,int,string.

The problem is .. Felix doesn't HAVE these types. They're actually
defined in the library. So the rules for constant folding should
be too. But they're not, they're defined in Ocaml. So its a hack.


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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 10/02/2015, at 1:42 PM, Ryan wrote:
> 
> Text editors with parenthesis highlighting really helps here.

Yep, I have that with Vim. It helps editing, but not reading :)

>> Python is procedural. It can't beat scheme, functional programming
>> technology
>> must be the core of any procedural language. Referential transparency
>> and 
>> persistent data structures and all that.
> 
> I thought Python was OO?

OO is a minor subset of procedural programming
of little real merit.  It was a nice idea but it was soon
proven to be too limited to be worth of serious consideration
in itself. A lot of the principles developed (encapsulation,
blah blah) are good, its just that OO either doesn't actually
provide them or does and fails to be expressive enough
for many uses.

Most Python people would say it is object based,
not object oriented.

However, really, dynamic languages aren't really serious
languages so it doesn't really matter what they are.


> I'd link the Stack Overflow answer about OO vs. functional by Norman Ramsey, but I'm too lazy to close my mail client...

Read his stuff anyhow.

> This would be neat...would Felix have a full web package (like Djano or CppCMS)?

I have no real idea. The core idea is simply that you can write:

	fun f: int * int -> int = JS"$1 * $2";

which is exactly the same as C++ except it says it's a binding to JS.

Obviously there'd be JS statement bindings etc too.
The main trick would be to ensure the JS and C++ code is sanely
separated.

So you'd have, say, "threads" in C++ code which communicate
with "threads" in the JS code on a channel, and the communication
would be done with libraries (AJAX, Websockets, whatever).


> Just PLEASE don't try to make it like Wt (a GUI web library).

Nope, whatever that is .. I'm a core language guy.
We're just talking client/server communications with Felix generating
programs on both ends.

You can do this NOW, C++ to C++ (just write a client and server).
So we need a JS back end. However the language wouldn't be the same,
JS has different capabilities (eg it has garbage collection and closures already).



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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 10/02/2015, at 10:16 AM, Ryan Gonzalez wrote:

> On Mon, Feb 9, 2015 at 4:56 PM, john skaller <sk...@us...> wrote:
> 
> On 10/02/2015, at 6:24 AM, Ryan Gonzalez wrote:
> 
> Lua is a bit of a hack I'm afraid, doesn't even parse cleanly.
> 
> Because it beats Scheme!


Not really. Scheme is well designed .. 

	(not (grok syntax me))

Of course, the fact data is the same as code is a major plus
for meta-programming, and that basically fixes the syntax.
[It has to be simple .. I just hate all the parens because I have
a math degree but can't count :]

> As to Python, its the other way: no sense embedding Py in
> Felix, but you can use Felix to make Python modules for
> those unfortunate souls that have to write real applications
> using Python.

> Unless it's one of your favorite programming languages...
> 
> People have implemented pattern matching in Python, and I'm working on a pattern matching library for Hy (Python+Lisp).
> 
> Again, it beats Scheme.

Python is procedural. It can't beat scheme, functional programming technology
must be the core of any procedural language. Referential transparency and 
persistent data structures and all that.

And for the parser, as I mentioned, this is mandatory.

This is one reason Felix is so good. It is a conventional procedural
language on the surface but it embed a very significant functional
subsystem.

> One more thing of interest would be embedding JavaScript or CoffeeScript with something like adt.js.

I'm actually thinking of Felix *generating* Javascript. So you could basically
construct an HTTP based client/server system using a browser as the client,
with Javascript generated, and also generate Felix (C++) plugins for the
webserver (client side code) to make a complete system. Throw in websockets
and it could get interesting.


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

Re: [Felix-language] [felix] Interpreter

[john s. <sk...@us...>]

On 10/02/2015, at 6:24 AM, Ryan Gonzalez wrote:

> Scheme is horrible, not hard.

If you can write Scheme .. please help! 
[Because I can't :]

I am so used to pattern matching in Ocaml and Felix
I can't write the equivalent code in crap languages without
it any more (like Scheme .. C++ .. Python .. err ..)

So one big aim of the interpreter thing is to do pattern matching.
In particular with that .. the existing macro processor could probably
be thrown out.

In particular look at the grammar and especially

	src/lib/grammar/grammar_scheme_support.fsyn

I would actually like to rework the whole front end of the flxg
compiler in scheme. What I mean is that the core workhorse
algorithms would still be in Ocaml, but they'd be sequenced
by scheme code. OCS Scheme is written in Ocaml and allows
extra primitive procedures and data types written in Ocaml to 
be added to it.

One particular goal is that at the moment, I have managed to get
it so that literals and identifiers are actually lexed and parsed
IN the grammar, that is, the Dypgen+Scheme is actually used to
define integer, float, and string literals. So I can say Felix
has no keywords, no grammar, and not even any literals:
its all in the library.

But there are some .. er .. HACKS! :-]

One of them is constant folding. It's done in Ocaml.
So it only works for bool, string, int. It should be done in 
the library, with Scheme.

> This looks great...but I can't help but feel like this would cause confusion in the future involving the interaction between Felix, Scheme, and Schemlix (what I'm calling this :).

And sister Sche-minx?

> Couldn't a simpler solution be used instead? Why not just embed Lua or Python+Hy?

How do I embed Lua or Python in Ocaml code?

And why would I embed such poor languages anyhow?

The parser technology is Generalised LR which works by simultaneously
attempting multiple parses and discarding failures. This means that except
for definite constructions such as top level statements, the action
code MUST be purely functional, since the actions may be discarded.

Sure, you could embed Lua in Felix but why would you bother
when you can write Felix? I actually did it at one stage.
Lua is a bit of a hack I'm afraid, doesn't even parse cleanly.

The thing is you can design and implement a much better interpreter
in Felix in a few lines of code, and the result will integrate with
Felix much better.

As to Python, its the other way: no sense embedding Py in
Felix, but you can use Felix to make Python modules for
those unfortunate souls that have to write real applications
using Python.

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

[Felix-language] Interpreter

[john s. <sk...@us...>]

I am currently working on a small interpreter. Here is the idea:

At the moment, you can extend the grammar by specifying a production
in an EBNF like language and action codes in Scheme.

There are two problems with this: the first is that Scheme is hard to write,
at least for me. And the second is that the Scheme must return s-expressions
matching what the Felix compiler expects: the structure of these terms is
complex, there are a lot of them, and they're not properly documented.

To make it easier the parser supports an alternative method.
Instead of

	non-terminal := production =># "scheme code";l

you can write

	non-terminal := production =># { Felix statements };
	non-terminal := production =># ( Felix expression);

Only statements and expressions can be handled like this.

However, statements in particular are limited. For example
a custom loop like

	stmt :=  "for" sname  "between" expr "and" expr "do" body =>#
	{ var _2 = _4; ... ++_2; ... }

doesn't work because _2 is an sname, which is neither the correct
"part of speech" for a variable definition nor for an expression.

In Scheme, you have to construct the correct AST terms for each,
but merely using Felix code, you can't do it.

SO .. I have decided to make a grammar which allows you to write
generative code which is translated to Scheme, but which is easier to 
write. Here are some examples:

open syntax xscheme;
SCHEME "(define sqr (lambda (x) (* x x)))";
XSCHEME ( sqr 3 );
XSCHEME ( if 1 + (2 - 3) + 4 - 6 < 0 then "negative" else "non-negative" endif );
XSCHEME ( 1 * 2 * 3 * 4 );
XSCHEME ( (fun (x) => x + 3 * x) 23 );
XSCHEME ( (fun (x) (y) (z) => (x+y+z)) 1 2 3 );
XSCHEME ( 1,2,3,"Hello" );
XSCHEME ( let x = 4 in sqr x );
XSCHEME ( let x = 4 in x.sqr );
XSCHEME ( display "HELLO" );
XSCHEME (letrec fact = (fun (x) => if x == 1 then 1 else x * fact (x - 1) endif) in fact 4);
XSCHEME ( { display "Z"; display "A"; 42 } );
XSCHEME ( {var x = 1; var y = x + 1; y = y + 1; x + y } ); // 4

The XSCHEME statement is just a hack to display the result whilst building
the xscheme language. All these examples work. i find the Felix like notation
a bit easier to write than Scheme. The parser translates these code into Scheme though.

I have an issue at the moment though: functions with more than one argument
in Scheme. Felix notation doesn't allow these.


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

Re: [Felix-language] [felix] packages

[john s. <sk...@us...>]

On 01/02/2015, at 10:56 AM, Ryan Gonzalez wrote:
> 
> By consulting the history, the build date can be translated to the packages
> internal "version".
> 
> Is this required for packages, or is it optional? Personally, I like the major.minor.fix scheme better.

It's just an idea. the major.minor.fix scheme has advantages, and on many
Linux (and other Unix) systems, it is enforced by the way links to
shared libraries are maintained.

The problem is that there is no coherent way to interlink such packages.
If packages depend on major.minor, then patches are irrelevant:
packages can be upgraded in isolation.

With major.minor the assumption is you need the same major (no other
will do) but any minor greater or equal to the specified one.

It's all a nice idea. But the reality of the world is continuous ad-hoc integration
and in that scenario the categorical distinctions of the package numbers
are useless UNLESS some human comes along and organises the
dependencies. This works with that, this can replace that, etc etc.

This is what Debian and Ubuntu and ArchLinux and all the other
package managers do and it is a HUGE effort which typically fails
most of the time. The last Debian release took over 2 years to get out.

Using a date YY.MM.DD defines your whole system with a single
number. Packages are comparable by date. They're NOT comparable
by major.minor.patch.

With Git, "working" versions can probably be tagged. Although I have yet
to figure out how to actually tag the repository (the instructions never seem
to work for me).

There's a related problem: how to store the packages. On Github you say.
Well sure, but how? Mike Maul's system used a repository called 
litterbox, which contained the index to the other repositories.

See. at present there are a number of "packages" built into the core,
including the new GUI stuff (which depends on SDL bindings).

That's easy for me to maintain: make changes to anything, run the test
suite, commit. Every now and then do an install for a backup (since I normally
run the build image directly).

With multiple packages it's much harder. I have to decide where to put
them on my computer. I have to cd around doing changes and commits
and pushes.

And then how do the tests get done?

i really HAVE to make the GUI stuff separate because the felix-lang.org server
of course won't run SDL (there's no screen, mouse, or keyboard :)

Similarly, gnu/gmp has to be separate because it doesn't build on Windows
and not everyone will be willing to use GPL libraries.

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