culibs: cu/bool.h Source File

00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>.
00002  * Copyright (C) 2009--2010  Petter Urkedal <paurkedal@eideticdew.org>
00003  *
00004  * This program is free software: you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation, either version 3 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
00016  */
00017 
00018 #ifndef CU_BOOL_H
00019 #define CU_BOOL_H
00020 
00021 #include <cu/fwd.h>
00022 
00023 CU_BEGIN_DECLARATIONS
00024 /** \defgroup cu_bool_h cu/bool.h: Boolean Functions
00025  ** @{ \ingroup cu_type_mod */
00026 
00027 /** An enumeration of unary boolean functions. */
00028 typedef enum {
00029     CU_BOOL1F_FALSE     = 0x0,  /**< λx. false */
00030     CU_BOOL1F_TRUE      = 0x3,  /**< λx. true */
00031     CU_BOOL1F_IDENT     = 0x2,  /**< λx. x */
00032     CU_BOOL1F_NOT       = 0x1,  /**< λx. ¬x */
00033 } cu_bool1f_t;
00034 
00035 /** Returns -1 if ¬\a x ∧ \a y, 0 if \a x ⇔ \a y, and 1 if \a x ∧ ¬\a y. */
00036 CU_SINLINE int
00037 cu_bool_cmp(cu_bool_t x, cu_bool_t y)
00038 { return x? (y? 0 : 1) : (y? -1 : 0); }
00039 
00040 /** Return the enumerated boolean function corresponding to \a f.  \a f will be
00041  ** called twice upon construction. */
00042 cu_bool1f_t cu_bool1f_from_func(cu_bool_t (*f)(cu_bool_t));
00043 
00044 /** Return the C function which at \e x returns <code>cu_bool1f_apply(\a f, \e
00045  ** x)</code>. */
00046 cu_bool_t (*cu_bool1f_to_func(cu_bool1f_t f))(cu_bool_t);
00047 
00048 /** Evaluate \a f(\a x). */
00049 CU_SINLINE cu_bool_t
00050 cu_bool1f_apply(cu_bool1f_t f, cu_bool_t x)
00051 { return (f >> !!x) & 1; }
00052 
00053 /** Return the constant function, λ\e y. \a x. */
00054 CU_SINLINE cu_bool1f_t
00055 cu_bool1f_konst(cu_bool_t x)
00056 { return (cu_bool1f_t)(3*!!x); }
00057 
00058 /** Return the function λ\e x. ¬\a f(\e x). */
00059 CU_SINLINE cu_bool1f_t
00060 cu_bool1f_not(cu_bool1f_t f)
00061 { return (cu_bool1f_t)(~f & 0x3); }
00062 
00063 /** Return the composition \a f ∘ \a g. */
00064 CU_SINLINE cu_bool1f_t
00065 cu_bool1f_compose(cu_bool1f_t f, cu_bool1f_t g)
00066 { return (cu_bool1f_t)((3*(f & 1) & ~g) | (3*((f & 2) >> 1) & g)); }
00067 
00068 
00069 /** An enumeration of binary boolean functions. */
00070 typedef enum {
00071 
00072     /* Nullary */
00073     CU_BOOL2F_FALSE     = 0x0,  /**< λ(\e x, \e y). false */
00074     CU_BOOL2F_TRUE      = 0xf,  /**< λ(\e x, \e y). true */
00075 
00076     /* Unary */
00077     CU_BOOL2F_LEFT      = 0xa,  /**< λ(\e x, \e y). \e x */
00078     CU_BOOL2F_RIGHT     = 0xc,  /**< λ(\e x, \e y). \e y */
00079     CU_BOOL2F_NOT_LEFT  = 0x5,  /**< λ(\e x, \e y). ¬\e x */
00080     CU_BOOL2F_NOT_RIGHT = 0x3,  /**< λ(\e x, \e y). ¬\e y */
00081 
00082     /* Commutative */
00083     CU_BOOL2F_NOR       = 0x1,  /**< λ(\e x, \e y). ¬(\e x ∨ \e y) */
00084     CU_BOOL2F_XOR       = 0x6,  /**< λ(\e x, \e y). \e x ⊻ \e y */
00085     CU_BOOL2F_NAND      = 0x7,  /**< λ(\e x, \e y). ¬(\e x ∧ \e y) */
00086     CU_BOOL2F_AND       = 0x8,  /**< λ(\e x, \e y). \e x ∧ \e y */
00087     CU_BOOL2F_IFF       = 0x9,  /**< λ(\e x, \e y). \e x ⇔ \e y */
00088     CU_BOOL2F_OR        = 0xe,  /**< λ(\e x, \e y). \e x ∨ \e y */
00089 
00090     /* Non-commutative */
00091     CU_BOOL2F_AND_NOT   = 0x2,  /**< λ(\e x, \e y). \e x ∧ ¬\e y */
00092     CU_BOOL2F_NOT_AND   = 0x4,  /**< λ(\e x, \e y). ¬\e x ∧ \e y */
00093     CU_BOOL2F_OR_NOT    = 0xb,  /**< λ(\e x, \e y). \e x ∨ ¬\e y */
00094     CU_BOOL2F_NOT_OR    = 0xd,  /**< λ(\e x, \e y). ¬\e x ∨ \e y */
00095 
00096 } cu_bool2f_t;
00097 
00098 /** Return the enumerated boolean function which agrees with \a f on its
00099  ** domain.  This samples \a f 4 times. */
00100 cu_bool2f_t cu_bool2f_from_func(cu_bool_t (*f)(cu_bool_t, cu_bool_t));
00101 
00102 /** The C function which agrees with \a f on its domain. */
00103 cu_bool_t (*cu_bool2f_to_func(cu_bool2f_t f))(cu_bool_t, cu_bool_t);
00104 
00105 /** Evaluate \a f(\a x, \a y). */
00106 CU_SINLINE cu_bool_t
00107 cu_bool2f_apply(cu_bool2f_t f, cu_bool_t x, cu_bool_t y)
00108 {
00109     return (f >> ((!!x) | (2*!!y))) & 1;
00110 }
00111 
00112 /** Return the partial evaluation λ\e y. \a f(\a x, \e y). */
00113 CU_SINLINE cu_bool1f_t
00114 cu_bool2f_apply_left(cu_bool2f_t f, cu_bool_t x)
00115 {
00116     int i = f >> !!x;
00117     return (cu_bool1f_t)((i & 1) | ((i >> 1) & 2));
00118 }
00119 
00120 /** Return the partial evaluation λ\e x. \a f(\e x, \a y). */
00121 CU_SINLINE cu_bool1f_t
00122 cu_bool2f_apply_right(cu_bool2f_t f, cu_bool_t y)
00123 {
00124     return (cu_bool1f_t)((f >> (2*!!y)) & 3);
00125 }
00126 
00127 /** The constant function λ(\e x, \e y). \a v. */
00128 CU_SINLINE cu_bool2f_t
00129 cu_bool2f_konst(cu_bool_t v)
00130 {
00131     return (cu_bool2f_t)(v? 15 : 0);
00132 }
00133 
00134 /** Return the function λ(\e x, \e y). ¬\a f(\e x, \e y). */
00135 CU_SINLINE cu_bool2f_t
00136 cu_bool2f_not(cu_bool2f_t f)
00137 {
00138     return (cu_bool2f_t)(~f & 0xf);
00139 }
00140 
00141 CU_SINLINE cu_bool2f_t
00142 cu_bool2f_not_left(cu_bool2f_t f)
00143 {
00144     return (cu_bool2f_t)(((f & 5) << 1) | ((f & 10) >> 1));
00145 }
00146 
00147 CU_SINLINE cu_bool2f_t
00148 cu_bool2f_not_right(cu_bool2f_t f)
00149 {
00150     return (cu_bool2f_t)((f >> 2) | ((f & 3) << 2));
00151 }
00152 
00153 /** Swap the arguments, i.e. λ(\e x, \e y). \a f(\e y, \e x). */
00154 CU_SINLINE cu_bool2f_t
00155 cu_bool2f_swap(cu_bool2f_t f)
00156 {
00157     return (cu_bool2f_t)((f & 9) | ((f & 2) << 1) | ((f & 4) >> 1));
00158 }
00159 
00160 /** Return the composition \a f ∘ \a g, i.e. the function λ(\e x, \e y). \a f
00161  ** (\a g (\e x, \e y)). */
00162 CU_SINLINE cu_bool2f_t
00163 cu_bool2f_compose(cu_bool1f_t f, cu_bool2f_t g)
00164 {
00165     return (cu_bool2f_t)((15*(f & 1) & ~g) | (15*((f & 2) >> 1) & g));
00166 }
00167 
00168 /** Return the composition of \a f on the left operand with \a g, λ(\e x, \e
00169  ** y). \a f (\a g(\e x), \e y). */
00170 CU_SINLINE cu_bool2f_t
00171 cu_bool2f_compose_left(cu_bool2f_t f, cu_bool1f_t g)
00172 {
00173     int gg = g | (g << 2);
00174     int fL = f & 5;
00175     int fH = (f >> 1) & 5;
00176     return (cu_bool2f_t)((3*fL & ~gg) | (3*fH & gg));
00177 }
00178 
00179 /** Return the composition of \a f on the right operand with \a g, λ(\e x, \e
00180  ** y). \a f (\e x, \a g(\e y)). */
00181 CU_SINLINE cu_bool2f_t
00182 cu_bool2f_compose_right(cu_bool2f_t f, cu_bool1f_t g)
00183 {
00184     int gg = 3*(g + (g & 2));
00185     int fL = f & 3;
00186     int fH = f >> 2;
00187     return (cu_bool2f_t)((5*fL & ~gg) | (5*fH & gg));
00188 }
00189 
00190 /** @} */
00191 CU_END_DECLARATIONS
00192 
00193 #endif