Hey people, check it out: Attached to this post is a small program I wrote.

(The attached binary works for M$ Windoze only. I'm not sure precisely 
which versions, but it DOES work for XP and DOES NOT work for NT 4.0. In 
principle it could be compiled for Linux or Mac OS X. The program is 
about 20 KB of Haskell source code.)

The program isn't terribly exciting; it's a predicate solver. That is, 
it attempts to solve extremely simple equations.

To run the program, double-click it. You should get a window of 
multicoloured terminal output, including a "Predicate>" prompt.

If you enter, say, "x = 1", then the program will respond that to solve 
this predicate, you have to set x equal to 1. (DUH!)

Alternatively, if you set "4 = 4", the program will find "1 solution", 
and that solution will be empty. This basically means that the predicate 
*always* holds. If you do "1 = 2", the program will report "no solutions 
found", indicating that the predicate can never be satisfied. So far so 
good.

If you say "x = 1 & y = 2" then the program will report a self-evident 
solution. If you say "x = 1 | y = 2" it will report two seperate 
solutions. And if you say "x = 1 & x = 2" it will fail to find any 
solutions (pretty obviously).

You can of course put predicates in brackets; by default, AND has a 
higher priority than OR. You can also prefix anything with "~" to 
indicate NOT (note that the engine doesn't support this quite so well).

The program understands (signed) integers and equality. It also 
understands lists. Try "{1, 2, 3} = {1, 2, 3}" and you will get an empty 
solution (i.e., the predicate always holds). Try "{1, 2, 3} = {3, 2, 1}" 
and you will get no solutions (i.e., the predicate never holds). You can 
also do "{x, y, z} = {1, 2, 3}", which yields a fairly obvious result.

Notice that, mathematically speaking, "x = 1" and "1 = x" are the same 
equation, and the program treats them identically.

The fun part begins when you start using the built-in predicate 
functions. There are currently just 4 of these; I plan to make it 
possible to add your own, but I haven't implemented this yet.

First, the rather dull "Empty" function tests whether a list is empty:

- "@Empty[{}]" will yeild an empty result set.
- "@Empty[{1, 2, 3}]" will give no results.

The "Element" function tests whether a given element is in a list:

- "@Element[5, {1, 2, 3}]" gives no results.
- "@Element[5, {4, 5, 6}]" gives an empty result set.

The weird part is that this works backwards as well as forwards:

- "@Element[x, {1, 2, 3}]" tells you all possible values for x that will 
satisfy the predicate!

Adventurers beware: Attempting to find all possible lists that 5 could 
be an element of will result in an infinite loop from which only Ctrl+C 
will escape.

Also of interest is the "Join" function:

- "@Join[{1, 2, 3}, {4, 5, 6}, {1, 2, 3, 4, 5, 6}]" gives an empty 
result set, indicating that the 3rd list is indeed the first two joined 
together.
- "@Join[{1, 2, 3}, {4, 5, 6}, z]" will set z to the join of the first 
two lists.

This also works backwards:

- "@Join[{1, 2, 3}, y, {1, 2, 3, 4, 5, 6}]" will find the correct value 
for y by stripping the first list off of the 3rd list.
- "@Join[x, {4, 5, 6}, {1, 2, 3, 4, 5, 6}]" works similarly.
- "@Join[x, y, {1, 2, 3}]" will find every possible way of splitting the 
final list into two sublists. How neat is that?!

Again, beware that other combinations may yield an infinite number of 
valid solutions [which will take an infinite amount of time to compute, 
and nothing is displayed until *all* solutions are fully computed].

Finally, there is the "Subset" function, which tells you if one set is a 
subset of another. For example, "@Subset[{1, 2}, {1, 2, 3}]". It 
_should_ also work backwards, but currently doesn't. I'm not sure why.

Anyway, it's an amusing little diversion...

Post a reply to this message

Attachments:
Download 'logic.exe.dat' (182 KB)

Invisible wrote:
> The program isn't terribly exciting; it's a predicate solver. That is,
> it attempts to solve extremely simple equations.

Will it solve simple stuff like "x + 1 = 3" in version 1.5? :)

(or does it already...?)

Post a reply to this message

Everyone loves to design languages.  Parsec?

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailcom> wrote:
> Will it solve simple stuff like "x + 1 = 3" in version 1.5? :)

  Solving equations is an interesting programming task in itself.

  Solving an equation where the variable to be solved appears only once
is fairly trivial. Things become quite a lot more complicated if the
variable can appear more than once...

-- 
                                                          - Warp

Post a reply to this message

Invisible wrote:
> To run the program, double-click it. You should get a window of 
> multicoloured terminal output, including a "Predicate>" prompt.

May I suggest that perhaps dark blue on black (and similar color 
schemes) aren't the best choice? Most of it, I can't read. Stick to 
either bright colors on a dark background or vice versa. Or at least 
make things like the prompt dim and the results bright. :-)

> If you say "x = 1 & y = 2" then the program will report a self-evident 
> solution. If you say "x = 1 | y = 2" it will report two seperate 
> solutions. And if you say "x = 1 & x = 2" it will fail to find any 
> solutions (pretty obviously).

And if you say "x = y + 3 & y = 17" it says "x = y", which wouldn't seem 
to be right. Unless I have the syntax wrong or something.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp wrote:

>   Solving an equation where the variable to be solved appears only once
> is fairly trivial. Things become quite a lot more complicated if the
> variable can appear more than once...

...yeah...what he said... ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Darren New wrote:

> May I suggest that perhaps dark blue on black (and similar color 
> schemes) aren't the best choice? Most of it, I can't read.

Oh, OK. It's actually all very readable on my screen; I guess it has a 
higher gamma or something.

> Stick to 
> either bright colors on a dark background or vice versa. Or at least 
> make things like the prompt dim and the results bright. :-)

Actually I made the prompt bright and the input + result dim. :-} Maybe 
I should reverse that?

The mean reasoning behind all this multicoloured madness is so that if a 
predicate produces 6 pages of output, you can easily find the thing you 
typed in, because it's a different colour.

...and then I tried to extend this concept as far as humanly possible, 
possibly resulting in a screen that's a tad too busy. ;-)

BTW, are you impressed that I got this to work? Somebody wrote a small 
Haskell library that invokes windows.h under Windoze or emits ANSI 
escape sequences on POSIX. Neat, eh? Also, notice the window title 
bar... ;-)

> And if you say "x = y + 3 & y = 17" it says "x = y", which wouldn't seem 
> to be right. Unless I have the syntax wrong or something.

Really? That shouldn't - ah, wait, I see what's happening.

Check the second line of output:

   Predicate: x = y

Since "+" isn't a valid token, the parser has ignored everything after 
that point. If the predicate *is* x = y, then the result you got would 
be perfectly correct.

This is one of the irritating things about Parsec. It can silently fail 
to parse all of the input. Like, if some prefix of the input is a valid 
expression but the rest isn't, it returns just the prefix. (Obviously it 
depends how you structure your parser.) I must figure out how to fix that...

Anyway, *this* is why it prints out what it thinks it parsed the 
expression as. (With lots of extra brackets.) In all cases, check that 
the program has parsed something that matches what you intended! o_O

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

nemesis wrote:
> Everyone loves to design languages.  Parsec?

Yeah, Parsec. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Nicolas Alvarez wrote:

> Will it solve simple stuff like "x + 1 = 3" in version 1.5? :)

Probably not.

Logic programming systems like this are more targetted at questions like 
"if Sue is Helen's mother and Helen is Jamie's mother, is James related 
to Helen?" and similar.

Currently the thing has no way to store "facts" and no way to define new 
predicate functions. Once I add that... I will have basically 
reimplemented the Prolog programming language. o_O

(Go look that up on Wikipedia BTW.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Oh, OK. It's actually all very readable on my screen; I guess it has a 
> higher gamma or something.

I actually live where it's sunny during the daytime. ;-)

I have trouble with a lot of video games, too.

> Actually I made the prompt bright and the input + result dim. :-} Maybe 
> I should reverse that?

Couldn't hurt.

> BTW, are you impressed that I got this to work? Somebody wrote a small 
> Haskell library that invokes windows.h under Windoze or emits ANSI 
> escape sequences on POSIX. Neat, eh? Also, notice the window title 
> bar... ;-)

Yep. I'm impressed. :-)

> Since "+" isn't a valid token, 

Ah.

> This is one of the irritating things about Parsec. It can silently fail 
> to parse all of the input. Like, if some prefix of the input is a valid 
> expression but the rest isn't, it returns just the prefix. (Obviously it 
> depends how you structure your parser.) I must figure out how to fix 
> that...

Doesn't it also return the rest of the unparsed string? So if that isn't 
empty, something failed?

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New wrote:
> Orchid XP v8 wrote:
>> Oh, OK. It's actually all very readable on my screen; I guess it has a 
>> higher gamma or something.
> 
> I actually live where it's sunny during the daytime. ;-)
> 
> I have trouble with a lot of video games, too.

Ah, OK. My office at work [where I coded this program] has no sunlight. 
I don't even know if it's day or night or whatever. A bit like caving, 
actually... random...

As for my bedroom at home... I just close the curtains when I want to 
play HL2. ;-)

>> BTW, are you impressed that I got this to work? Somebody wrote a small 
>> Haskell library that invokes windows.h under Windoze or emits ANSI 
>> escape sequences on POSIX. Neat, eh? Also, notice the window title 
>> bar... ;-)
> 
> Yep. I'm impressed. :-)

Heh. Actually I wrote a small library of my own that calls windows.h 
directly. [You've seen the code, haven't you?] But somebody else came up 
with a nice library that works on Windoze *and* POSIX, so now I'm using 
that instead. So I really could compile my program for Linux or 
something if I want.

>> Since "+" isn't a valid token, 
> 
> Ah.
> 
>> This is one of the irritating things about Parsec. It can silently 
>> fail to parse all of the input. Like, if some prefix of the input is a 
>> valid expression but the rest isn't, it returns just the prefix. 
>> (Obviously it depends how you structure your parser.) I must figure 
>> out how to fix that...
> 
> Doesn't it also return the rest of the unparsed string? So if that isn't 
> empty, something failed?

Nope.

Remember, each "parser" can be combined with other parsers to make a 
larger parser at any time. And it might be that the parser is only 
*trying* to parse some prefix of the input.

I just asked about it, and some people recommended adding the "eof" 
parser to the top-level parser. (This causes the parser to fail if the 
entire input is not parsed. The error message is likely to be pretty 
opaque though...)

BTW, have you tried making the parser deliberately fail? It doesn't just 
crash the program, it actually reports a (moderately) friendly message 
to the user. It even hilights where in your input it's upset - in case 
you can't mentally work out where "column 28" is. Neat, eh? ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> Hey people, check it out: Attached to this post is a small program I 
> wrote.

What does the result y <- #2 mean?

Try the two below:

@Element[x,{1,y}]
@Element[x,{y,1}]

The 2nd one contains the "y <- #2" result but the first one doesn't.

Also I agree with what Darren said, the dark blue used for the "<-" is a bit 
too dark (visible, but hard to see, how about dark red instead?).

Post a reply to this message

scott wrote:

> What does the result y <- #2 mean?
> 
> Try the two below:
> 
> @Element[x,{1,y}]
> @Element[x,{y,1}]
> 
> The 2nd one contains the "y <- #2" result but the first one doesn't.

Consider the expression "?x: y = x". This is read as "there exists an x 
such that y = x". What it "really" does is replace x with a unique 
variable name (in this case, "#1").

The only reason you would do this is if you're running a recursive 
predicate, so that successive recursions all get unique variable names. 
Internally, all of the predefined functions except @Empty are recursive 
and so use such variables.

Ordinarily, all these temporary variables either have nothing bound to 
them, or are bound to a specific value. But occasionally they do show up 
in the final result. In the example you give, "y <- #2" actually means 
nothing at all, so the program should probably elide that. (It means 
that y is equal to some temporary variable which itself doesn't have a 
defined value, and hence y has no defined value - which would be the 
same as the result set not mentioning y at all!)

See? This stuff is harder than it looks! ;-)

> Also I agree with what Darren said, the dark blue used for the "<-" is a 
> bit too dark (visible, but hard to see, how about dark red instead?).

Hmm, yes, that *is* a little dark...

Post a reply to this message

>> Everyone loves to design languages.  Parsec?
> 
> Yeah, Parsec. ;-)

Wanna see the code?

Post a reply to this message

Here it is, people: build #70.

Changes since the last released version:

- Fixed: Parser used to silently ignore invalid parts of the input, as 
long as some prefix of it is a valid expression. (E.g., "x = 1 + 1" 
would silently parse 'successfully' as "x = 1".) You should now get an 
error message instead.

- Changed "<-" from dark blue to dark cyan. (On my system, that shows up 
significantly brighter.)

Post a reply to this message

Attachments:
Download 'logic.exe.dat' (183 KB)

Well that didn't last long! Here's build #86. (I promise there won't be 
any more for a while yet...)

Changes:

- The predicate "?x: a = x & b = x" now yields "a <- b" as you'd expect. 
(It's a hack, so it doesn't always work.)

- Fixed a very evil bug where calling functions with certain variable 
names as arguments would cause bizare malfunctions. (Basically the 
variable names used inside the function clashing with the arguments 
passed in. This *should* be fixed now...)

- Functions are no longer hard-wired into the program; you can define 
your own! The Library.txt file (it must be called exactly that) contains 
the definitions. If this file doesn't exist or is not parsable, 
currently the situation isn't handled terribly gracefully.

I've included the hard-wired functions, but feel free to add your own!

Post a reply to this message

Attachments:
Download 'logic.exe.dat' (189 KB) Download 'us-ascii' (1 KB)

Nicolas Alvarez wrote:

> Will it solve simple stuff like "x + 1 = 3" in version 1.5? :)
> 
> (or does it already...?)

Actually... if you encode "numbers" as lists of 1s of the appropriate 
length, then the @Join[] function essentially implements addition and 
subtraction! o_O

@Join[{1, 1}, {1, 1}, z]
z <- {1, 1, 1, 1}

@Join[{1, 1, 1}, y, {1, 1, 1, 1, 1}]
y <- {1, 1}

etc.

Obviously this isn't an especially intuitive or efficient way to work, 
but hey - Peano integers FTW! :-D

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible wrote:
> - Fixed a very evil bug where calling functions with certain variable 
> names as arguments would cause bizare malfunctions. (Basically the 
> variable names used inside the function clashing with the arguments 
> passed in. This *should* be fixed now...)

And you wondered why Lisp has that funky "gensym" function.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

>> - Fixed a very evil bug where calling functions with certain variable 
>> names as arguments would cause bizare malfunctions. (Basically the 
>> variable names used inside the function clashing with the arguments 
>> passed in. This *should* be fixed now...)
> 
> And you wondered why Lisp has that funky "gensym" function.

What is "gensym", and why does Lisp have it?

Post a reply to this message

Invisible wrote:
>>> - Fixed a very evil bug where calling functions with certain variable 
>>> names as arguments would cause bizare malfunctions. (Basically the 
>>> variable names used inside the function clashing with the arguments 
>>> passed in. This *should* be fixed now...)
>>
>> And you wondered why Lisp has that funky "gensym" function.
> 
> What is "gensym", and why does Lisp have it?

It creates a guaranteed-unique variable name that you can use as a local 
in a macro or a dynamically-scoped function.   What did you *think* it 
might be for, given the bit I quoted and the name of the LISP function?

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

>> What is "gensym", and why does Lisp have it?
> 
> It creates a guaranteed-unique variable name that you can use as a local 
> in a macro or a dynamically-scoped function.   What did you *think* it 
> might be for, given the bit I quoted and the name of the LISP function?

Mmm, OK.

This isn't hard to do in Haskell - it's just that you have to remember 
to do it! (And more subtly, do it at the correct moment.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> This isn't hard to do in Haskell - it's just that you have to remember 
> to do it! (And more subtly, do it at the correct moment.)

Yep. Of course, in LISP, you do this all the time. When you're good at 
it, about 30% of your code winds up being code-generating macros. So 
figuring out where gensym goes is like figuring out whether you need 
global or stack-based variables in a block-structured language. You just 
crash and burn if you don't learn it.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New wrote:
> Orchid XP v8 wrote:
>> This isn't hard to do in Haskell - it's just that you have to remember 
>> to do it! (And more subtly, do it at the correct moment.)
> 
> Yep. Of course, in LISP, you do this all the time. When you're good at 
> it, about 30% of your code winds up being code-generating macros.

Heh. Crazy language... I thought computer science experts concluded, 
like, 30 years ago that self-modifying code is actually an Extremely Bad 
Idea? (Originally of course everybody thought it was "cool"...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Heh. Crazy language... I thought computer science experts concluded, 
> like, 30 years ago that self-modifying code is actually an Extremely Bad 
> Idea? (Originally of course everybody thought it was "cool"...)

  Code generation is not the same thing as self-modifying code.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 wrote:
> Heh. Crazy language... I thought computer science experts concluded, 
> like, 30 years ago that self-modifying code is actually an Extremely Bad 
> Idea? (Originally of course everybody thought it was "cool"...)

It's only "self-modifying code" if you modify it after it has already 
been run.

Computer scientists quite like code-generating macros. They have some 
pretty sophisticated ones, called "compilers".

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

> It's only "self-modifying code" if you modify it after it has already 
> been run.

Well, technically that's true. But Lisp macros run at runtime, not 
compile time, so technically you could run the same macro twice and have 
it generate different code each time...

> Computer scientists quite like code-generating macros. They have some 
> pretty sophisticated ones, called "compilers".

Yeah. And as I understand it, writing one is supposedly the hardest task 
in all of Computer Science. :-P

Sounds like writing one as part of your application is an excellent idea...

Post a reply to this message

Invisible wrote:
>> It's only "self-modifying code" if you modify it after it has already 
>> been run.
> 
> Well, technically that's true. But Lisp macros run at runtime, not 
> compile time, so technically you could run the same macro twice and have 
> it generate different code each time...

But the macro still doesn't modify the code after that code is run, so 
that's OK. Having the same macro generate different code at different 
places is the point of a macro.

> Yeah. And as I understand it, writing one is supposedly the hardest task 
> in all of Computer Science. :-P

Certainly it used to be before the theories were worked out. Writing one 
that generates anything close to optimal code is difficult given the 
complexity of current chips.

> Sounds like writing one as part of your application is an excellent idea...

Yep. ;-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message