[fexl]

I think the answer is we should have it, but it's just a library.

[hxa7241]

OK. Then I suppose the question is: why should it be library not built-in?

The main thing not addressed in the article is: what are the language implementation implications? What are the pros and cons there?

[fexl]

In my way of thinking, the distinction between "library" and "built-in" is very fluid. That is, if you run an executable which automatically loads a library for you, then voila it is now built-in. If nothing else, you can set up your own local environment that you favor. I realize this has portability implications, but keep in mind that not everyone will want "bignums" or "socket operations" or "openssl" available all the time in every program.

For me, the language implications are nil. I would not change a single thing in Fexl to support name-value "trees" versus lists. It's all programmable using the system as it is. The S, C, Y, I, L, R combinators are what they are, forever and ever, world without end. :) And I'm quite sure the same thing is true of Lisp (i.e. just use defun or maybe defmacro). You'll notice that even in the original article the author didn't propose any new syntax. It's all just more functions.

I mean, even in Perl for goodness sake all you have to do is this:

    # A map is a list of branches.  Each branch is pair(key,data).  The data is
    # pair(val,map).  No two keys in a map have any prefix in common.  A key cannot
    # be null.  If you put a null val at a key, it deletes that key from the map.

    sub map_put
        {
        my $map = shift;
        my $key = shift;
        my $val = shift;

        die if !defined $key || ref($key) ne "" || $key eq "";
        die if !defined $val;

        if (is_atom($map))
            {
            return $map if is_null($val);
            return pair(pair(atom($key),pair($val,null())), $map);
            }

        my $branch = left($map);
        my $old_key = name(left($branch));

        my $cmp = $key cmp $old_key;

        if ($cmp == 0)
            {
            my $sub_map = right(right($branch));

            if (is_null($val))
                {
                return right($map) if is_atom($sub_map);

                if (is_atom(right($sub_map)))
                    {
                    # Combine singleton map upstairs.

                    my $top_key = name(left($branch));
                    my $next_key = name(left(left($sub_map)));

                    my $new_branch = pair(atom($top_key.$next_key),
                        right(left($sub_map)));
                    return pair($new_branch,right($map));
                    }
                }

            my $new_branch = pair(left($branch), pair($val,$sub_map));
            return pair($new_branch,right($map));
            }

        if (substr($key,0,1) eq substr($old_key,0,1))
            {
            my $len_common = len_common_prefix($key,$old_key);

            my $key_suffix = substr($key,$len_common);
            my $old_key_suffix = substr($old_key,$len_common);
            my $common_prefix = substr($key,0,$len_common);

            if ($key_suffix eq "")
                {
                return $map if is_null($val);

                my $sub_map =
                    pair(pair(atom($old_key_suffix),right($branch)),null());
                my $new_branch = pair(atom($common_prefix),pair($val,$sub_map));
                return pair($new_branch,right($map));
                }

            if ($old_key_suffix eq "")
                {
                my $old_sub_map = right(right($branch));
                my $new_sub_map = map_put($old_sub_map,$key_suffix,$val);
                my $old_val_atom = left(right($branch));

                if (name($old_val_atom) eq "")
                    {
                    return right($map) if is_atom($new_sub_map);

                    if (is_atom(right($new_sub_map)))
                        {
                        # Combine singleton map upstairs.
                        # TODO hey wait!  This is the same code as above.  Unify this.

                        my $top_key = name(left($branch));
                        my $next_key = name(left(left($new_sub_map)));

                        my $new_branch = pair(atom($top_key.$next_key),
                            right(left($new_sub_map)));
                        return pair($new_branch,right($map));
                        }
                    }

                my $new_branch = pair(left($branch),
                    pair($old_val_atom,$new_sub_map));
                return pair($new_branch,right($map));
                }

            return $map if is_null($val);

            my $old_branch = pair(atom($old_key_suffix),right($branch));
            my $sub_map = map_put(pair($old_branch,null()),$key_suffix,$val);

            my $new_branch = pair(atom($common_prefix),pair(null(),$sub_map));
            return pair($new_branch,right($map));
            }

        if ($cmp < 0)
            {
            return $map if is_null($val);
            return pair(pair(atom($key),pair($val,null())), $map);
            }

        return pair($branch,map_put(right($map),$key,$val));
        }

    sub map_get
        {
        my $map = shift;
        my $key = shift;

        die if !defined $key || ref($key) ne "" || $key eq "";

        return null() if is_atom($map);

        my $branch = left($map);
        my $old_key = name(left($branch));

        my $cmp = $key cmp $old_key;

        return left(right($branch)) if $cmp == 0;

        if (substr($key,0,1) eq substr($old_key,0,1))
            {
            my $len_common = len_common_prefix($key,$old_key);
            my $key_suffix = substr($key,$len_common);
            my $old_key_suffix = substr($old_key,$len_common);

            return map_get(right(right($branch)),$key_suffix)
                if $old_key_suffix eq "";
            return null();
            }

        return null() if $cmp < 0;
        return map_get(right($map),$key);
        }

That would be a lot cleaner in Fexl or Lisp, but it's totally do-able in any language.