| Author |
Message |
|
| ftabba |
 Posted: Fri Jun 13, 2008 4:10 am |
 |
|
|
Joined: 17 Jun 2008
Posts: 3
Location: Auckland, New Zealand
|
Hi,
I'm new to Erlang, so I apologize in advance for asking what might be obvious to some.
I've run into problem trying to use functions as guards in Erlang. I looked through the manual, and discovered that this isn't allowed by the language in case those functions have side-effects. The thing is, my functions do not have side effects. Is there a way to convey that message to the compiler and allow my functions to be used as guards? (Something along the lines of #pragma i_swear_this_function_has_no_side_effects).
I know that code can be rewritten to avoid this problem, however, and probably due to my limited experience with Erlang, the particular piece of code I have in mind would look really ugly and really complicated without the ability to do this. Below is a snippet of my code that I'm referring to, if anyone has any suggestions on how to make it work in Erlang and look elegant I'd appreciate it.
This code deals with fixing up a red black tree after a node has been deleted, and here's what I'm trying to do:-
% Algorithm from http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html
% Case B1
delfix({Ky, Vy, Cy, {Kx, Vx, bb, A, B}, {Kz, Vz, b, C, D}}) when (isBlack(C) and isBlack(D)) ->
|
|
|
| Back to top |
 
|
| Guest |
| Posted: Fri Jun 13, 2008 6:29 am |
|
|
|
Guest
|
|
| Back to top |
|
| Guest |
| Posted: Fri Jun 13, 2008 8:38 am |
|
|
|
Guest
|
On Fri, 13 Jun 2008 08:25:29 +0200, Doug Edmunds <dougedmunds@gmail.com>
wrote:
> check out the discussion on
> http://wrongnotes.blogspot.com/2007/09/little-erlang.html
>
> "The solution is to call the function and store it in a
> variable before we use it in the guard conditions."
Yes, but it's a solution to the particular case you hit
working with if/case/fun; not to the general inability
to use custom functions in guards.
Clearly, you can't "store it in a variable" when you're
at toplevel context (which is what Fuad has been asking
about) or when the object you'd like to inspect comes
from the pattern immediately preceding the guard.
-- Jachym
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| ftabba |
| Posted: Fri Jun 13, 2008 9:48 am |
|
|
|
Joined: 17 Jun 2008
Posts: 3
Location: Auckland, New Zealand
|
Thanks Doug and Jachym.
Jachym is right, Doug's suggestion would work if the guard was inside my function rather than at a top level context. I know that I could rewrite my code and convert it to a bunch of if statements, but I can't think of a way to write such code without it looking ugly.
Being able to use a function with a guard seems like it would be the most elegant solution.
Any suggestions?
Cheers,
/Fuad
On Fri, Jun 13, 2008 at 8:35 PM, Jachym Holecek <jachym.holecek@e-fractal.cz (jachym.holecek@e-fractal.cz)> wrote:
Quote: On Fri, 13 Jun 2008 08:25:29 +0200, Doug Edmunds <dougedmunds@gmail.com (dougedmunds@gmail.com)> wrote:
Yes, but it's a solution to the particular case you hit
working with if/case/fun; not to the general inability
to use custom functions in guards.
Clearly, you can't "store it in a variable" when you're
at toplevel context (which is what Fuad has been asking
about) or when the object you'd like to inspect comes
from the pattern immediately preceding the guard.
|
|
|
| Back to top |
|
| Gleber |
| Posted: Fri Jun 13, 2008 10:37 am |
|
|
|
User
Joined: 15 May 2007
Posts: 75
|
2008/6/13 Fuad Tabba <fuad@cs.auckland.ac.nz>:
> I looked
> through the manual, and discovered that this isn't allowed by the language
> in case those functions have side-effects. The thing is, my functions do not
> have side effects. Is there a way to convey that message to the compiler and
> allow my functions to be used as guards?
>
> ...
>
> % Algorithm from
> http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html
>
> % Case B1
> delfix({Ky, Vy, Cy, {Kx, Vx, bb, A, B}, {Kz, Vz, b, C, D}}) when (isBlack(C)
> and isBlack(D)) ->
> blackToken({Ky, Vy, Cy, {Kx, Vx, b, A, B}, {Kz, Vz, r, C, D}});
>
> % Above is one of many clauses for the delfix function. Below is the full
> isBlack function:-
>
> % An empty node (or subtree) or a black node (or subtree) are black (true),
> everything else is red (false).
> isBlack({}) -> true;
> isBlack({_, b, _, _, _}) -> true;
> isBlack(_) -> false.
You may use macros:
-define(is_black(X), ((X =:= {}) orelse (element(2, X) =:= b))).
and
delfix({Ky, Vy, Cy, {Kx, Vx, bb, A, B}, {Kz, Vz, b, C, D}}) when
(?is_black(C) and ?is_black(D)) ->
blackToken({Ky, Vy, Cy, {Kx, Vx, b, A, B}, {Kz, Vz, r, C, D}});
I didn't checked this, but it may work
Best regards,
--
Gleb Peregud
http://gleber.pl/
Every minute is to be grasped.
Time waits for nobody.
-- Inscription on a Zen Gong
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Fri Jun 13, 2008 11:24 am |
|
|
|
Guest
|
On Fri, 13 Jun 2008 11:43:54 +0200, Fuad Tabba <fuad@cs.auckland.ac.nz>
wrote:
> Being able to use a function with a guard seems like it would be the most
> elegant solution.
It could be useful and I admit I don't understand why is that prohibited
(besides
"side effects and infinite loops in guards are Evil" to which one can
reply "the
compiler can refuse a guard function if it can't prove it to be safe").
Anyway,
I'm not a compiler expert, so maybe there's a good reason I'm missing.
> Any suggestions?
Maybe choose different data representation that allows you to pattern-match
node colour? Something along the lines of:
-record(rb_node, {
left, %% Left subtree. :: rb_node()
right, %% Right subtree. :: rb_node()
is_black, %% Red or black? :: bool()
data}). %% Contents. :: term()
Either that, or give up doing all the dispatch in function clauses; ie.
live
with having explicit 'case' statements (there's nothing wrong about them
after
all). Or restructure the code in different way, but it's hard to suggest
how
w/o seeing the rest of the module...
HTH,
-- Jachym
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| Thomas Lindgren |
| Posted: Fri Jun 13, 2008 2:04 pm |
|
|
|
User
Joined: 09 Mar 2005
Posts: 284
|
--- Jachym Holecek <jachym.holecek@e-fractal.cz>
wrote:
> It could be useful and I admit I don't understand
> why is that prohibited
> (besides
> "side effects and infinite loops in guards are Evil"
> to which one can
> reply "the
> compiler can refuse a guard function if it can't
> prove it to be safe").
Arguably, that's already the case 
> Anyway,
> I'm not a compiler expert, so maybe there's a good
> reason I'm missing.
There are some potential compiler gains from having
easy-to-analyze guards (e.g., you can see whether
clauses are mutually exclusive more easily/often and
can easily reorder tests in guards), but I think this
restriction is mostly for historical reasons. Consider
that you can write arbitrary "guards" using standard
Erlang expressions, e.g.:
case catch (E1 andalso E2 andalso ... E3) of
true -> Body;
_ -> <next clause>
end
or even the useful
case catch abstype:is_abstype(X) of
true -> Body;
_ -> <next clause>
end
So, as far as I'm concerned, if you in practice end up
writing your complex tests using case instead of
guards, the guard syntax becomes less and less
relevant. Why hang on to such a restriction when it
just leads to more convoluted programs? Nowadays I'm
thus in favour of allowing arbitrary guards (possibly
disallowing side-effects by dynamic checking, but
perhaps I'm just reluctant to let go entirely .
Best,
Thomas
PS. The concurrent logic languages contemporary with
early Erlang in the 1980s also required flat guards,
but in those cases there was good reason to do so: it
was simply too hard to implement efficient arbitrary guards.
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| warezio |
| Posted: Fri Jun 13, 2008 6:22 pm |
|
|
|
User
Joined: 05 May 2007
Posts: 107
Location: Yahoo
|
Couldn't one implement the "evaluate into in a variable, then match"
strategy with a parse transform?
The resulting error messages might confuse (a call to foo/3 leading to a
bad match in foo/7, but there's no foo/7 explicit in the code). However
the code would look nice.
-- p
On Fri, 13 Jun 2008, Thomas Lindgren wrote:
>
> --- Jachym Holecek <jachym.holecek@e-fractal.cz>
> wrote:
>
> > It could be useful and I admit I don't understand
> > why is that prohibited
> > (besides
> > "side effects and infinite loops in guards are Evil"
> > to which one can
> > reply "the
> > compiler can refuse a guard function if it can't
> > prove it to be safe").
>
> Arguably, that's already the case
>
> > Anyway,
> > I'm not a compiler expert, so maybe there's a good
> > reason I'm missing.
>
> There are some potential compiler gains from having
> easy-to-analyze guards (e.g., you can see whether
> clauses are mutually exclusive more easily/often and
> can easily reorder tests in guards), but I think this
> restriction is mostly for historical reasons. Consider
> that you can write arbitrary "guards" using standard
> Erlang expressions, e.g.:
>
> case catch (E1 andalso E2 andalso ... E3) of
> true -> Body;
> _ -> <next clause>
> end
>
> or even the useful
>
> case catch abstype:is_abstype(X) of
> true -> Body;
> _ -> <next clause>
> end
>
> So, as far as I'm concerned, if you in practice end up
> writing your complex tests using case instead of
> guards, the guard syntax becomes less and less
> relevant. Why hang on to such a restriction when it
> just leads to more convoluted programs? Nowadays I'm
> thus in favour of allowing arbitrary guards (possibly
> disallowing side-effects by dynamic checking, but
> perhaps I'm just reluctant to let go entirely .
>
> Best,
> Thomas
>
> PS. The concurrent logic languages contemporary with
> early Erlang in the 1980s also required flat guards,
> but in those cases there was good reason to do so: it
> was simply too hard to implement efficient arbitrary guards.
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@erlang.org
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
In an artificial world, only extremists live naturally.
-- Paul Graham
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Sat Jun 14, 2008 12:59 am |
|
|
|
Guest
|
Jachym Holecek wrote:
> On Fri, 13 Jun 2008 08:25:29 +0200, Doug Edmunds <dougedmunds@gmail.com>
> wrote:
>
>> check out the discussion on
>> http://wrongnotes.blogspot.com/2007/09/little-erlang.html
>>
>> "The solution is to call the function and store it in a
>> variable before we use it in the guard conditions."
>>
>
> Yes, but it's a solution to the particular case you hit
> working with if/case/fun; not to the general inability
> to use custom functions in guards.
>
> Clearly, you can't "store it in a variable" when you're
> at toplevel context (which is what Fuad has been asking
> about) or when the object you'd like to inspect comes
> from the pattern immediately preceding the guard.
>
>
As similar approach that works for functions is to have two functions.
The first calculates the non-guard conditions, then passes them to the
second function which can pattern match.
e.g.:
delfix({Ky, Vy, Cy, {Kx, Vx, bb, A, B}, {Kz, Vz, b, C, D}}) ->
delfix1({Ky, Vy, Cy, {Kx, Vx, b, A, B}, {Kz, Vz, r, C,
D}},isBlack(A),isBlack(B),isBlack(C),isBlack(D));
delfix1({Ky, Vy, Cy, {Kx, Vx, bb, A, B}, {Kz, Vz, b, C,
D}},_,_,true,true) ->
blackToken({Ky, Vy, Cy, {Kx, Vx, b, A, B}, {Kz, Vz, r, C, D}});
delfix1(...) ->
...
> -- Jachym
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@erlang.org
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
>
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| Thomas Lindgren |
| Posted: Sat Jun 14, 2008 10:59 am |
|
|
|
User
Joined: 09 Mar 2005
Posts: 284
|
--- Paul Mineiro <paul-trapexit@mineiro.com> wrote:
> Couldn't one implement the "evaluate into in a
> variable, then match"
> strategy with a parse transform?
I realize I might have been a bit unclear in the
example. The Ei in a pseudo-guard
catch (E1 andalso E2... andalso En)
would be metavariables standing for expressions. So a
clause
fun({byte, X},Y)
when X >= 0, X =< 16#ff, integer(Y), X < Y -> ...;
...
would become something like
fun(T1, T2) ->
case catch
(begin {byte, X} = T1, Y = T2, true end
andalso X >= 0 andalso X =< 16#ff
andalso integer(Y) andalso X < Y) of
true ->
...
_ ->
<next clause>
end
To answer your question: In principle, yes, but you'd
have to be careful to ensure that the transformation
was efficient. First, there is possible code
duplication. Second, the transform has to play nicely
with the compiler. The example above would probably
confuse the pattern match compiler, for instance,
which might slow things down considerably.
Best,
Thomas
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post received from mailinglist |
|
|
| Back to top |
|
| rvirding |
| Posted: Sat Jun 14, 2008 2:29 pm |
|
|
|
User
Joined: 30 Aug 2006
Posts: 452
Location: Stockholm, Sweden
|
2008/6/13 Fuad Tabba <fuad@cs.auckland.ac.nz (fuad@cs.auckland.ac.nz)>:
Quote: Thanks Doug and Jachym.
Jachym is right, Doug's suggestion would work if the guard was inside my function rather than at a top level context. I know that I could rewrite my code and convert it to a bunch of if statements, but I can't think of a way to write such code without it looking ugly.
Being able to use a function with a guard seems like it would be the most elegant solution.
It would open a can of worms that I would rather see remain closed, specifically side effects and message passing. Just being able to declare something as "guard safe" wouldn't really help as the system would still have to be able to do something sensible in all cases. Otherswise you would be surprised what users can dream up. "It's hard to make a program foolproof because fools are so ingenious".
I used the following macros for just that case:
%% {r,Left,Key,Val,Right}
%% {b,Left,Key,Val,Right}
%% empty
-define(IS_RED(N), (is_tuple(N) andalso element(1, N) == r)).
%% -define(IS_BLACK(N), not (is_tuple(N) andalso element(1, N) == r)).
-define(IS_BLACK(N),
|
|
|
| Back to top |
 
|
| ftabba |
| Posted: Sun Jun 15, 2008 10:37 pm |
|
|
|
Joined: 17 Jun 2008
Posts: 3
Location: Auckland, New Zealand
|
Thanks for everyone for your responses. They were definitely helpful, I now understand Erlang and some of these issues a bit better.
I ended up using macros (as Gleb and Robert suggested; specifically the macro Gleb posted). I think this is a more elegant solution than doing any other transformations of the code, but I could be wrong...
Anyway, I uploaded my code to:-
http://www.cs.auckland.ac.nz/~fuad/rbtree.erl
http://www.altabba.org/2008/06/full-red-black-tree-implementation-in.html (for some background)
If anyone has any comments about my code I would appreciate it.
Robert: I've based my delete algorithm on the one at http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html , would definitely be interested in a faster algorithm. Is it the one you're using for the rbdict you posted?
Thanks again.
Cheers,
/Fuad
On Sun, Jun 15, 2008 at 2:26 AM, Robert Virding <rvirding@gmail.com (rvirding@gmail.com)> wrote:
Quote: 2008/6/13 Fuad Tabba <fuad@cs.auckland.ac.nz (fuad@cs.auckland.ac.nz)>:
Quote: Thanks Doug and Jachym.
Jachym is right, Doug's suggestion would work if the guard was inside my function rather than at a top level context. I know that I could rewrite my code and convert it to a bunch of if statements, but I can't think of a way to write such code without it looking ugly.
Being able to use a function with a guard seems like it would be the most elegant solution.
It would open a can of worms that I would rather see remain closed, specifically side effects and message passing. Just being able to declare something as "guard safe" wouldn't really help as the system would still have to be able to do something sensible in all cases. Otherswise you would be surprised what users can dream up. "It's hard to make a program foolproof because fools are so ingenious".
I used the following macros for just that case:
%% {r,Left,Key,Val,Right}
%% {b,Left,Key,Val,Right}
%% empty
-define(IS_RED(N), (is_tuple(N) andalso element(1, N) == r)).
%% -define(IS_BLACK(N), not (is_tuple(N) andalso element(1, N) == r)).
-define(IS_BLACK(N),
|
|
|
| Back to top |
|
| rvirding |
| Posted: Mon Jun 16, 2008 1:18 am |
|
|
|
User
Joined: 30 Aug 2006
Posts: 452
Location: Stockholm, Sweden
|
2008/6/16 Fuad Tabba <fuad@cs.auckland.ac.nz (fuad@cs.auckland.ac.nz)>:
Looking over my code again, it was a while back I wrote it, it looks like the algorithm in the link you mentioned is the one used in the extra file rbdict1.erl I included in the package. I have a macro DBLACK for the doubly black token so it seems like it. I also see that I don't have any implementation of the deletion algorithm in the first haskell version from http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html. I will have to try this and see how it matches up with the others.
I have a little test program I use for testing various dictionaries which I include here. It is uncommented but generates lots of test cases, compile it with the 'E' option to see what all the macros generate. Macros are really useful but they are much easier in lisp. Should really redo the file in LFE.
Robert
Post received from mailinglist |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
