Skip to content

Instantly share code, notes, and snippets.

@luser-dr00g
Last active August 29, 2015 13:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save luser-dr00g/9542998 to your computer and use it in GitHub Desktop.
Save luser-dr00g/9542998 to your computer and use it in GitHub Desktop.
Lukasiewicz Logic Intepreter in C.
//http://www.ams.org/journals/mcom/1954-08-046/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { LOW = -10000, HIGH = 10000 };
char *P = "01";
char *monadic = "N";
char *dyadic = "KA";
char _n(char c){ return c^1; }
char _k(char c, char d){ return c&d; }
char _a(char c, char d){ return c^d; }
char (*mtab[1])(char) = { _n };
char (*dtab[2])(char,char) = { _k, _a };
int S[256];
int Wtab[256];
struct spec { // variable specification
char c;
int v;
};
int initS(struct spec *sp, int n){ // set variables from list
int i;
for (i=0; i < n; i++)
S[ sp[i].c ] = sp[i].v;
}
int initWtab(){ // init the Weight table
int i;
int l;
for (i=0; i < sizeof Wtab/sizeof*Wtab; i++)
Wtab[i] = 1;
l = L(monadic);
for (i=0; i < l; i++)
Wtab[monadic[i]] = 0;
l = L(dyadic);
for (i=0; i < l; i++)
Wtab[dyadic[i]] = -1;
}
int Wc(char c){ // Weight of a char
//printf("Wc(%c)=%d\n", c, Wtab[c]);
return Wtab[c];
}
int Ws(char *s){ // Weight of a string
int a = 0;
int i;
int l = L(s);
for (i=0; i < l; i++)
a += Wc(s[i]);
return a;
}
int L(char *s){return strlen(s);} // length of string
char *T(int i, char *s){ // tail(i) of string
int l;
if (i <= (l=L(s)))
return strdup(s + (l-i));
else
return s;
}
char *H(int i, char *s){ // head(i) of string
int l;
if (i <= (l=L(s)))
return strndup(s, i);
else
return s;
}
int D(char c){ // Degree of operator char
return 1 - Wc(c);
}
int Wmax(char *s){ // Max Weight over substrings
int i;
int l;
int a = LOW;
int w;
l = L(s);
for (i=1; i <= l; i++){
w = Ws(T(i,s));
a = a>w? a: w;
}
return a;
}
int Wmin(char *s){ // Min Weight over substrings
int i;
int l;
int a = HIGH;
int w;
l = L(s);
for (i=1; i <= l; i++){
w = Ws(T(i,s));
a = a<w? a: w;
}
return a;
}
int PF(char *s){ // Is s a Positive Formula?
return Wmin(s) > 0;
}
int WFF(char *s){ // Is s a Well-Formed Formula?
return PF(s) && Ws(s)==1;
}
int itoP(int i){ // decode data char to index
return P[i];
}
int Ptoi(int c){ // encode index as data char
return strchr(P, c) - P;
}
char F(char d, char *s){ // execute function d upon s
int f;
//printf("F(%c,%s)\n", d, s);
char *fbank;
if (D(d)>0){
//printf("D(%c)=%d\n", d, D(d));
fbank = D(d)-1? dyadic: monadic;
//printf("fbank %s\n", fbank);
f = strchr(fbank, d) - fbank;
//printf("f %d\n", f);
if (f)
return itoP(dtab[f](Ptoi(s[0]),Ptoi(s[1])));
else
return itoP(mtab[f](Ptoi(s[0])));
} else {
return d;
}
}
int is_var(char c){ // c is a variable if its Weight is 1 and not data
return (Wc(c)==1) && (strchr(P,c) == NULL);
}
char G(char c){ // perform variable-lookup
if (is_var(c)){
//printf("IS_VAR %c\n", c);
return itoP(S[c]);
} else {
return c;
}
}
char *cat(char *h, char *t){ // catenate two strings
char *s = malloc(L(h)+L(t)+1);
strcpy(s, h);
strcat(s, t);
return s;
}
char *E(char *s){ // Evaluation function
//printf("%s\n",s);
if (L(s)==0)
return s;
else {
if (PF(s)) {
int d;
char *EDel;
char *h;
char *t;
char b[2] = "?";
//printf("PF\n");
d = D(*s);
EDel = E(s+1); // recurse on tails
//printf("%c ", *s);
t = T(L(EDel)-d, EDel); // tail of returned E(Delta)
h = H(d, EDel); // head of E(Delta)
//printf("%s %s\n", h, t);
b[0] = F(G(*s),h); // subst variable and call function
//printf("%s\n", b);
return cat(b,t); // cat result to tail
}
return s;
}
}
int main(int argc, char **argv){
struct spec spec[] = { // variable specs
{ 'p', 1 },
{ 'q', 0 },
{ 'r', 0 } };
char *s[] = { // list of programs to execute
"0",
"p",
"pKpqNr",
NULL };
char **p;
initS(spec, sizeof spec/sizeof*spec);
initWtab();
for (p = s; *p; p++)
printf("%s\n", E(*p));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment