|
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
So what does this look like when implemented in Haskell?
> module Logic where
Well, the program basically takes a predicate, and returns an
answer which says either:
- The predicate cannot be satisfied.
- The predicate can be satisfied, and this set of variable
bindings satisfies is.
We can store the variable bindings in a key/value dictionary.
To do that, let's import the requisit Haskell module:
> import qualified Data.Map
Now let's define a variable bindinds table type:
> type Table = Data.Map.Map Var Expression
> empty_table = Data.Map.empty
As I say, an "answer" is either a "no" or a "yes, and here's
the bindings". In Haskell, we can use the pre-defined "Maybe"
type for this.
> type Answer = Maybe Table
Now let's define what an "expression" is. Let's say that an
expression can be a number, a variable, or a list. (I'll
define lists recursively so that predicates can recurse
over them.)
> data Expression =
> Number Integer |
> Variable Var |
> ListNode Expression Expression |
> ListEndNode
> deriving (Eq, Show)
I'm going to have two types of variable - named ones that the
programmer creates, and numbered ones that are auto-generated
by the "exists" predicate later on:
> data Var = Named String | Numbered Integer deriving (Eq, Ord, Show)
Let's continue now by defining the unification algorithm.
Remember, unification takes two expressions and determins
whether it is possible to make them the same by setting
some variable bindings. We start with an empty bindings
table, and proceed by adding new bindings.
> unify :: Table -> Expression -> Expression -> Answer
Firstly, let's apply the current set of bindings to the
two input expressions before proceeding. This ensures that
any variables already bound are eliminated from the
expressions.
> unify t e0 e1 = case (apply t e0, apply t e1) of
Now we take the possibilities case by case. For example,
if we have to unify a number against a number, we check
whether the numbers are equal. If they're not, unification
fails. If they are, unification suceeds (and the table
remains unchanged).
> (Number x, Number y) -> if x == y then Just t else Nothing
A variable matches anything. Well no, not quite. A variable
matches any expression not containing that variable. (E.g.,
you can't unify x = 2*x.) Assuming that condition holds, just
add the binding to the table.
> (Variable x, e) -> if e `contains` x
> then Nothing
> else Just (bind t x e)
> (e, Variable x) -> if e `contains` x
> then Nothing
> else Just (bind t x e)
Lists are slightly more tricky. Obviously an empty list
matches an empty list
> (ListEndNode, ListEndNode) -> Just t
For a non-empty list, we want to unify the list heads,
and then (using the binding table) continue unifying the
list tails. Oh, but if the first part fails, skip
the second part...
Fortunately, Haskell's much-feared "monad" concept implements
exactly this behaviour:
> (ListNode x xs, ListNode y ys) -> do
> t' <- unify t x y
> unify t' xs ys
That is, unify x against y using table t, thus generating a
new table t'. Then unify xs against ys using t' as the table
(thus generating a new table, which is the final result).
Oh, and finally, any combination that doesn't match one of
the above patterns (e.g., unify a number against a list)
causes unification to fail:
> (_, _) -> Nothing
Now we just need to implement that "apply" function:
> apply :: Table -> Expression -> Expression
> apply t (Variable v) = case Data.Map.lookup v t of
> Nothing -> Variable v
> Just e -> e
> apply t (ListNode x xs) = ListNode (apply t x) (apply t xs)
> apply t e = e
And also the "contains" function:
> contains :: Expression -> Var -> Bool
> (Variable v) `contains` v0 = v == v0
> (ListNode x xs) `contains` v0 = x `contains` v0 || xs `contains` v0
> _ `contains` v0 = False
Finally, the "bind" function. In principle this just inserts
a binding into the table - but actually I've made it rescan all
the existing bound expressions and apply any applicable expansions
to them as well to eliminate intermediate temporary variables.
> bind :: Table -> Var -> Expression -> Table
> bind t v e = Data.Map.map (apply t) (Data.Map.insert v e t)
Now we have unification. You can try out an example such as
unify
empty_table
(ListNode (Number 1) (ListNode (Number 2) ListEndNode)
(ListNode (Variable (Named "x")) (ListNode (Number 2) ListEndNode)
which yields the result
Just (fromList [(Named "x",Number 1)]
In other words, "[1,2]" unified against "[x,2]" yields "x=1".
We can implement this as a predicate. But first we need to decide
what a "predicate" actually is. In my implementation, a predicate
is a function that takes a current bindings table and returns
a list of all possible bindings tables (starting from the given
one) that satisfy the predicate:
> type State = (Table,Integer)
> type Predicate = State -> [State]
What the heck is that integer there for? Well, it's used by
"exists", as we'll see a bit later. Let's now write a "run"
function:
> run_pred :: Predicate -> [State]
> run_pred p = p (empty_table, 1)
Anyway, the equality predicate is quite easy:
> pred_equals :: Expression -> Expression -> Predicate
> pred_equals x y (t,n) = case unify t x y of
> Nothing -> []
> Just t' -> [(t',n)]
If unification fails, return an empty list. If unification
succeeds, return a 1-element list containing the new
bindings table.
Implementing an OR predicate is similarly simple:
> pred_OR :: Predicate -> Predicate -> Predicate
> pred_OR p1 p2 (t,n) = p1 (t,n) ++ p2 (t,n)
In other words, run the first predicate, run the second
predicate, and then just JOIN the two answer lists thus
produced!
Implementing AND is moderately harder. We want to run the
first predicate, and then for EVERY result produced, run
the second predicate starting from that answer. Once again,
Haskell's monad structure leaps to the rescue:
> pred_AND :: Predicate -> Predicate -> Predicate
> pred_AND p1 p2 s0 = return s0 >>= p1 >>= p2
And finally, the "exists" predicate. It takes a function
that accepts a temp variable and returns a predicate.
> pred_exists :: (Expression -> Predicate) -> Predicate
> pred_exists fn (t,n) = (fn (Variable (Numbered n))) (t,n+1)
Now, to prove all this works, let's have that "join"
predicate:
> pred_join :: Expression -> Expression -> Expression -> Predicate
> pred_join xs ys zs =
> (
> (xs `pred_equals` ListEndNode) `pred_AND`
> (ys `pred_equals` zs)
> )
> `pred_OR`
> (
> pred_exists $ \t ->
> pred_exists $ \ts0 ->
> pred_exists $ \ts1 ->
> (xs `pred_equals` ListNode t ts0) `pred_AND`
> (zs `pred_equals` ListNode t ts1) `pred_AND`
> (pred_join ts0 ys ts1)
> )
To see it in action, you need to do quite a bit of typing,
unfortunately:
run_pred $
pred_join
(Variable "xs")
(Variable "ys")
(ListNode (Number 1) (ListNode (Number 2) ListEndNode))
Should give you the following:
[(fromList [(Named "xs",ListEndNode),(Named "ys",ListNode (Number 1)
(ListNode (Number 2) ListEndNode))],1),(fromList [(Named "xs",ListNode
(Number 1) ListEndNode),(Named "ys",ListNode (Number 2)
ListEndNode),(Numbered 1,Number 1),(Numbered 2,ListEndNode),(Numbered
3,ListNode (Number 2) ListEndNode)],4),(fromList [(Named "xs",ListNode
(Number 1) (ListNode (Number 2) ListEndNode)),(Named
"ys",ListEndNode),(Numbered 1,Number 1),(Numbered 2,ListNode (Number 2)
ListEndNode),(Numbered 3,ListNode (Number 2) ListEndNode),(Numbered
4,Number 2),(Numbered 5,ListEndNode),(Numbered 6,ListEndNode)],7)]
which, if you unscramble it, translates as
xs = [], ys = [1,2]
xs = [1], ys = [2], ?1? = 1, ?2? = [], ?3? = [2],
xs = [1,2], ys = [], ?1? = 1, ?2? = [2], ?3? = [2], ?4? = 2, ?5? =
[], ?6? = []
Ignoring all the temp variables, that's basically
xs = [], ys = [1,2]
xs = [1], ys = [2]
xs = [1,2], ys = []
Which is, indeed, all possible ways to construct the list [1,2].
Now, to make it properly fun, implement a small parser than can take
an expression such as "[x,y,z]" and construct the appropriate
Haskell data structure, and a pretty printer that takes the
result and prints it in human-readable form. ;-)
Oh, by the way, if you take this entire post and save it to disk as
"Logic.lhs", you can load it into any Haskell-98 compliant compiler
or interpretter and run it. This is actual source code!
[Alternatively, if you want to just delete all lines not starting
with ">", that'll give you the raw Haskell code, so you can
inspect it without my comments interspersed.]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> So what does this look like when implemented in Haskell?
Very cool. Thank you. I'm tempted to try to translate this into Erlang
to see how different it would be. :-)
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Invisible wrote:
>> So what does this look like when implemented in Haskell?
>
> Very cool. Thank you. I'm tempted to try to translate this into Erlang
> to see how different it would be. :-)
Please, be my guest... I've never seen any non-trivial Erlang sources.
[Would you also like to see the parser and pretty printer? They're not
much larger. ;-) ]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Please, be my guest... I've never seen any non-trivial Erlang sources.
OK. Right now I'm working on a Jotto game. That's been my "second
program" since high school on languages where I needed to figure out how
they work. (First being "hello world" of course.)
I'm happy to post that when I finish too.
I'm also trying to figure out in the back of my head how to translate a
bunch of the SQL stuff at work to use Mnesia, which is Erlang's database
system. (Apparently, the name was originally "Amnesia" until one of the
managers pointed out what a bad idea it was to name a database system
"Amnesia." :-)
> [Would you also like to see the parser and pretty printer? They're not
> much larger. ;-) ]
Sure. Erlang has such built in (for Erlang literals, at least), but
sure. :-)
Incidentally, any reason you can see why this with 5600 lines of input
would take 10 seconds and with 100,000 lines of input (20 times as big)
it would take more than an hour? Am I doing something stupidly N^2 or
is it the memory management doing something odd?
load_file_words(IO, Acc) ->
% Read one space-delimited string from the IO chan with no prompt
Read = io:fread(IO, [], "~s"),
case Read of
{ok, [[]]} -> load_file_words(IO, Acc); % blank line
{ok, [Word]} -> load_file_words(IO, [Word|Acc]); % found word
eof -> Acc; % End of file, return accumulated answers
{error, What} -> erlang:error(What) % crash out
end.
Isn't this how you're supposed to do the functional programming loop bit? :)
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> OK. Right now I'm working on a Jotto game. That's been my "second
> program" since high school on languages where I needed to figure out how
> they work. (First being "hello world" of course.)
>
> I'm happy to post that when I finish too.
What is "Jotto"?
> I'm also trying to figure out in the back of my head how to translate a
> bunch of the SQL stuff at work to use Mnesia, which is Erlang's database
> system. (Apparently, the name was originally "Amnesia" until one of the
> managers pointed out what a bad idea it was to name a database system
> "Amnesia." :-)
Er, yes... interesting name choice. (?!)
>> [Would you also like to see the parser and pretty printer? They're not
>> much larger. ;-) ]
>
> Sure. Erlang has such built in (for Erlang literals, at least), but
> sure. :-)
Oh, it's trivial to get the compiler to write a parser for Haskell
literals too. But the problem [in this case] is that the Haskell
expressions are rather verbose and wordy, which makes it hard to type
out non-trivial example expressions and so forth.
> Incidentally, any reason you can see why this with 5600 lines of input
> would take 10 seconds and with 100,000 lines of input (20 times as big)
> it would take more than an hour? Am I doing something stupidly N^2 or
> is it the memory management doing something odd?
>
>
> load_file_words(IO, Acc) ->
> % Read one space-delimited string from the IO chan with no prompt
> Read = io:fread(IO, [], "~s"),
> case Read of
> {ok, [[]]} -> load_file_words(IO, Acc); % blank line
> {ok, [Word]} -> load_file_words(IO, [Word|Acc]); % found word
> eof -> Acc; % End of file, return accumulated answers
> {error, What} -> erlang:error(What) % crash out
> end.
>
> Isn't this how you're supposed to do the functional programming loop
> bit? :)
Without knowing Erlang well enough, I couldn't speculate. It looks to me
light it ought to work, but hey...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
module Display where
import qualified Data.Map
import Logic
class Display d where
display :: d -> String
instance Display Var where
display (Named x) = x
display (Numbered x) = "?" ++ show x ++ "?"
instance Display Expression where
display (Number x) = show x
display (Variable v) = display v
display (ListNode x xs) = "(!" ++ display x ++ display xs ++ ")"
display (ListEndNode) = "#"
print_results :: [State] -> IO ()
print_results = mapM_ (putStrLn . line)
where
line (t,n) = unwords $ map (\(v,e) -> display v ++ " = " ++ display
e ++ ";") $ Data.Map.toList t
module Parse (parse_expression) where
import Text.ParserCombinators.Parsec
import Logic
trim = skipMany space
number = do
ds <- many1 digit
trim
return (Number (read ds))
variable = do
cs <- many1 letter
trim
return (Variable (Named cs))
list_node = do
char '!'
trim
x <- expression
xs <- expression
return (ListNode x xs)
list_end = do
char '#'
trim
return ListEndNode
brackets = do
char '('
trim
e <- expression
char ')'
trim
return e
expression = do
number <|> variable <|> list_node <|> list_end <|> brackets
parse_expression cs = case parse expression "" cs of
Left e -> error (show e)
Right e -> e
Save the first one as Display.hs and the second as Parse.hs. Once you
import Logic, Display and Parse, you should be able to convert a string
such as "!1(!2(!3#))" into a logic expression by passing it to the
parse_expression function. The result can be passed to the display
method to turn it back into a string.
As far as I'm aware there are no bugs in the implementation, but I
haven't tested extensively.
Now, let's try this:
run_pred $
pred_join
(parse_expression "!1(!2(!3#))")
(parse_expression "ys")
(parse_expression "!1(!2(!3(!4(!5(!6)))))")
Unfortunately Haskell's class instance rules won't allow me to pretty
print the predicate results without altering the rest of the code
slightly... so I've written the print_results function instead.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> What is "Jotto"?
It's a word game, http://en.wikipedia.org/wiki/Jotto
Not unlike the "Mastermind" game, if you've ever played that.
I find it helpful as a first program because you have a bunch of things
you need to do - prompt for and take input, remember previous guesses,
store new words in a database or file somewhere, etc.
> Oh, it's trivial to get the compiler to write a parser for Haskell
> literals too. But the problem [in this case] is that the Haskell
> expressions are rather verbose and wordy, which makes it hard to type
> out non-trivial example expressions and so forth.
I think the Haskell expressions are probably longer than the Erlang
expressions would be because you're carrying the type around.
> Without knowing Erlang well enough, I couldn't speculate. It looks to me
> light it ought to work, but hey...
I was just after whether it was a strange logic error or something. It
works, it's just really slow, but the memory usage doesn't keep
climbing. (I can see it GCing every few seconds, but it doesn't grow out
of bounds and start paging or anything.)
Maybe I just haven't initialized the memory management to take advantage
of enough memory to cut down the GCs.
Or maybe the file parsing stuff actually is written in Erlang, in which
case it really *is* that slow.
The program to go thru and pick every 20'th word and write it out after
reading it all in to memory in Tcl was faster by far than simply reading
in the trimmed list in Erlang. Which is a bit worrysome, if I expect to
be using this for production systems.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> I was just after whether it was a strange logic error or something. It
> works, it's just really slow,
It turns out that using the Erlang equivalent of fscanf("%s",...) is
much slower than using the erlang equivalent of fgets(). Like, an hour
versus a couple seconds to read and process the file. I haven't any idea
why yet.
And I figured out what is throwing me about finding documentation. The
language defines "modules" and "functions", where a "module" is all the
functions in one source file.
But the top-level documentation is organized in terms of "applications",
wherein each "application" is a collection of modules distributed
together, but for which there's no real direct equivalent in the
language itself. The runtime interpreter parses configuration values
based on the application name (e.g., you can set the xyz configuration
to pdq for the abc application by starting erlang with
% erl -abc xyz pdq
), so the runtime knows about applications, and the libraries do, but
they're nowhere in the TOC for the language manual.
Sort of like if you had to figure out whether what you want is in
stdlib, stdio, STL, Boost, or POSIX before you could look up strlen or
open() or something like that in the manual.
Yes, there are other indexes in the manual pages, but the documentation
itself refers to the applications, so before you figure this out, it's
way confusing. Especially since "application" doesn't *really* mean just
"application". Like, is spawning a new process in the "erlang"
application, the "kernel" application, or the "stdlib" application? Is
the function to dynamically load code in one of those, or is it in the
"code" application or the "compiler" application or the "primitives"
application? :-)
And then you package up "applications" into "releases", so just because
you have a monitoring program, a database, and a web server, those could
be three "applications" that make up one thing-the-user-runs, whatever
you want to call them.
It doesn't help that you can fiddle with the syntax via macros, not
unlike LISP. Except that the syntax fiddling is apparently (as far as
I've been able to figure out) caused by something outside your modules.
That is, you don't have to say anything inside your source code to get
it modified dynamically during compilation. Instead, the thing that
implements the parsing transformations is apparently configured in
outside the system. The compiler must be reading a file somewhere saying
"this list of modules implements parsing transformations" or some such.
I haven't quite tracked that down yet, but now that I know the words...
Babble mumble mutter. Don't mind me.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|