a golden oldie challenge: Eliza

[Mark Tarver]

Having got 3936 LOC through a 4000 LOC implementation, I thought I'd
do some recreational
hacking and do an old old program I've not looked at for some time -
Eliza. You all know Eliza well enough for me not to have to spell it
out. The challenge is to implement or dig up an Eliza program (you
don't have to write it yourself) in your favourite FPL. Note that the
script that drives Eliza's responses should not be counted towards the
LOC count. Some constraints.

1. The script itself should be changeable by any novice. That is to
say that it should not
be a pile of hard-wired code written in the native language of
the program or require
deep programming skills.

2. The program should receive keyboard input from the user -
including the usual punctuation
and any characters he wants to enter without crashing.

During the Harrop Wars on comp.lang.lisp a lot of stuff was thrown
around about the desirability of pattern matching. The challenge is
interesting because it involves a style of pattern-matching called
'segment pattern matching' that is not hard-wired into most FPLs and
I'd like to see how well different FPLs cope with something outside
the standard.

Oh last thing; don't get too uptight about this. It's only a bit of
fun.

Mark

[Mark Tarver]

Well here is my shot at it in Qi. Total LOC excluding script is 70
LOC. You should run it under Qi 9.2 (latest release) because the
system function 'read-chars-as-stringlist' had a bug that was patched
in that release. My script is very boring ;).

I looked for a Haskell/ML equivalent and found zilch. Norvig's PAIP
contains a Lisp version in two files (eliza and eliza1) that is about
150 LOC excluding comments and script.

Mark
___________________________________________________________
(set *script* [
[[X "like" Y] ["Why" "do" "you" "like" Y "?"]]
[[X "father" Y] ["Tell me about your father."]]
[[X] ["That's very interesting. Do go on."]]])

(define eliza
-> (do (output "hi~%?- ") (eliza-loop (user) (value *script*))))

(define eliza-loop
User Script -> (let Responses (map (/. S (pmatch User S)) Script)
Interesting (remove-if no-match? Responses)
ScriptError (if (empty? Interesting)
(error "script failure!")
_)
Choice (nth (+ (random (length Interesting)) 1)
Interesting)
Response (respond-with Choice)
Output (output "~{~A ~}~%~%?- " Response)
(eliza-loop (user) Script)))

(define respond-with
[[] R] -> R
[[[X V] | B] R] -> (respond-with [B (rep X R V)]))

(define no-match?
[#\Escape _] -> true
_ -> false)

(define user
-> (read-chars-as-stringlist (user-loop (read-char _)) whitespace?))

(define whitespace?
#\Space -> true
#\Tab -> true
#\, -> true
#\. -> true
_ -> false)

(define user-loop
#\Newline -> []
C -> [C | (user-loop (read-char _))])

(define remove-if
_ [] -> []
F [X | Y] -> (if (F X) (remove-if F Y) [X | (remove-if F Y)]))

(define pmatch
User [I R] -> [(pmatch-help I User []) R])

(define pmatch-help
X X B -> B
[X | Y] [X | Z] B -> (pmatch-help Y Z B)
[X | Y] Z B <- (let NilBind (nilbind X B)
ValX (value-in X NilBind)
(pmatch-help (rep X Y ValX) Z NilBind))
where (variable? X)
[X | Y] [W | Z] B <- (pmatch-help [X | Y] Z (consbind X W B))
where (variable?
X)
_ _ _ -> #\Escape)

(define nilbind
X [] -> [[X []]]
X [[X V] | B] -> [[X V] | B]
X [Y | Z] -> [Y | (nilbind X Z)])

(define consbind
X W [] -> [[X [W]]]
X W [[X V] | B] -> [[X (append V [W])] | B]
X W [Y | B] -> [Y | (consbind X W B)])

(define rep
_ [] _ -> []
X [X | Y] V -> (append V (rep X Y V))
X [Y | Z] V -> [Y | (rep X Z V)])

(define value-in
X B -> (head (tail (assoc X B))))

[William James]

I added some features and wrote it in Ruby.

Sample session:

? Hi. I'm going to be your worst nightmare.
Why are you going to be my worst nightmare?
? I think you're full of it.
Why do you think I am full of it?
? My mother told me so.
Tell me about your mother.
? No. You tell me about yours.
We're talking about you, not me.
? You're obviously retarded.
Please don't be so personal.
? Damn your eyes!
I'm not sure that I understand you fully.
? Understand a kick in the pants?
Can you elaborate on that?
? I always ignore idiots.
Why do you always ignore idiots?
? I am afraid of dinosaurs.
Have you always been afraid of dinosaurs?
? quit

Script =
[[:x, ["father",'mother','brother','sister'], :y],
["Tell me about your ", :_, "."]],
[[:x, ["am", "i'm"], :y], [["Why are you", :y, "?"],
["Have you always been", :y, "?"]]],
[[:x, "I", :y], ["Why do you", :y, "?"]],
[[:x, 'you', :y], [["We're talking about you, not me."],
["Please don't be so personal."]]],
[[:x], [["That's very interesting. Do go on."],
["Tell me more."],
["I'm not sure that I understand you fully."],
["Can you elaborate on that?"] ]]

def change_person s
h = { 'I','you', 'my','your', 'myself','yourself',
'you are','I am', "you're", 'I am' }
tmp = s.scan(/you are|you're|\w+|\W+/).map{|s|
h[s] or h.invert[s] or s }
tmp[-1] = "me" if "I" == tmp[-1]
tmp.join
end

patterns, symbols, replies = [], [], []

Script.each{|ary|
syms = []
patterns << Regexp.new( "^" +
ary[0].map{|x|
case x
when Symbol
syms << x
"(.*?)"
when String
"\\b#{ x }\\b"
when Array
syms << :_
"\\b(#{ x.join('|') })\\b"
else
".*?"
end
}.join + "$", true ) # Case-insensitive.
symbols << syms
ary[1] = ary[1].sort_by{ rand } if ary[1][0].is_a? Array
replies << ary[1]
}

while true
print "? "
resp = gets.strip.sub(/[.!?,;]+$/, "")
break if 'quit' == resp
patterns.each_with_index{|pat,i|
if match_data = resp.match( pat )
reply = replies[i]
if reply[0].is_a? Array
# Rotate replies for variety.
reply.push( reply.shift )
reply = reply[0]
end
captures = match_data.captures.map{|s| change_person s}
# Create associative array mapping symbols to values.
t = Hash[ *symbols[i].zip( captures ).flatten ]
puts reply.map{|x| x.is_a?(Symbol) ? t[x] : x }.join
break
end
}
end

[Mark Tarver]

> end- Hide quoted text -
>
> - Show quoted text -

First I've seen Ruby used. Don't understand a damn thing of
course :),
but 55 LOC puts it top.

Mark

[William James]

On Feb 22, 7:12 pm, Mark Tarver <dr.mtar...@ukonline.co.uk> wrote:

> First I've seen Ruby used. Don't understand a damn thing of
> course :),
> but 55 LOC puts it top.
>
> Mark

Symbols begin with ":".

Lists (arrays to Rubyists) are enclosed in [], but they
can be omitted sometimes, e.g.:
a = 22,33,44

"<<" appends to a list:
[6,7,8] << 9
==>[6, 7, 8, 9]

The index of the first element in a list is 0:
[6,7,8][0]
==>6

The array method ".join" is almost self-explanatory:
['tip', '-', 'top'].join
==>"tip-top"
['tip', '-', 'top'].join( '***' )
==>"tip***-***top"

Anonymous code blocks are enclosed in {..} or do ... end.

The parameters of the code block are enclosed in |...|.
In this example, the parameter is "n":
[6,7,8].map{|n| n * 2 }
==>[12, 14, 16]

In a different context {...} indicates a hash (associative
array):
h = {'foo',44, 'bar',55, 'boo',66}
==>{"boo"=>66, "foo"=>44, "bar"=>55}
It's clearer but more tedious to separate key-value pairs
with "=>":
h = {'foo'=>44, 'bar'=>55, 'boo'=>66}
==>{"boo"=>66, "foo"=>44, "bar"=>55}

Let's consider two lines:

tmp = s.scan(/you are|you're|\w+|\W+/).map{|s|
h[s] or h.invert[s] or s }

".scan" operates on the string s, producing a list of
substrings that are matched by the regular expression
"/you are|you're|\w+|\W+/". The pipe symbol "|" functions
as OR; "\w" matches a word character; "\W" matches a
non-word character. Example:
"you are willy-nilly, yes?".scan( /you are|you're|\w+|\W+/ )
==>["you are", " ", "willy", "-", "nilly", ", ", "yes", "?"]
Next, ".map" attempts to perform substitutions using the
key-value pairs of the hash "h". It makes good use of the
method ".invert", which swaps each key with its value:
{'foo',22, 'bar',33}
==>{"foo"=>22, "bar"=>33}
{'foo',22, 'bar',33}.invert
==>{33=>"bar", 22=>"foo"}

[John Thingstad]

På Fri, 22 Feb 2008 23:09:58 +0100, skrev William James
<w_a_...@yahoo.com>:

Have you tried ALICE?

--------------
John Thingstad

[Stevan Apter]

in q:

D:(("1 father|mother|brother|sister 2";"tell me about your 0.");
("1 am|i'm 2";"why are you 2|have you always been 2?");
("1 i 2";"why do you 2?");
("1 you 2";"we're talking about you, not me.|please don't be so personal"))

E:"|"vs"that's very interesting. do go on.|
tell me more|
i'm not sure i understand you fully|
can you elaborate on that?"

S:{(`$"|"vs first w where not b;raze w where b:(first each w:" "vs x)in"0123456789")}each D[;0]
R:"|"vs'D[;1]
P:{(y,x,z)(x,y)?z}[`$("you";"your";"yourself";"i'm";"i am");`$("i";"my";"myself";"you are";"you're")]

e:{w:(`$" "vs x except".?")except`; / words except punctuation, blanks
b:w in\:/:S[;0]; / boolean mask: words X rules
if[count[b]=i:(any each b)?1b;:E first 1?count E]; / if no key match on a rule, early exit
p:1_'(0,1+k:b[i]?1b)_`,w; / split input on key
r:{x first 1?count x}R i; / pick a rule
n:r first raze r ss/:"0123456789"; / which part of input to replace
ssr[r;n;" "sv string(),P each(w[k],p)"I"$n]} / construct reply

in k it's about half the size, but i'll spare you.

"William James" <w_a_...@yahoo.com> wrote in message news:c4d42479-42ea-4238...@k2g2000hse.googlegroups.com...

[Ken Tilton]

I'd love to see it, or a link to any other sample K code. I recall
seeing a one page implementation of a spreadsheet, that was wild.

kenny

[Stevan Apter]

thanks for asking ken.

e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?#E
" "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
.q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}

it's just a single eye-watering case statement:

if no keyword match in A, then return a default response from E
else if no substitution in the response c picked from C, return c
else substitute and return

it's easier to break the q code into smaller chunks. a revised version
here: http://www.nsl.com/k/eliza.q

"Ken Tilton" <kenny...@optonline.net> wrote in message news:47c0813e$0$8080$607e...@cv.net...

[Szabolcs]

I'm not a programmer. I just wanted to have some fun, so I tried to
write a Mathematica version based on the Ruby version (the only one I
actually understood). I'm sure that this can be improved and written
in a nicer way, but here it goes: :-)

script = {
{__, u : "father" | "mother" | "brother" | "sister", ___} :> {"Tell
me about your " <> v <> "."},
{___, "am" | "i'm", u__} :> {"Why are you " <> v <> "?", "Have you
always been " <> v <> "?"},
{___, "i", u__} :> {"Why do you " <> v <> "?"},
{___, "you", ___} :> {"We're talking about you, not me", "Please

don't be so personal."},

{u___} :> {"That's very interesting. Do go on.", "Tell me more.",

"I'm not sure that I understand you fully.",

"Can you elaborate on that?",
"Why do you think that " <> v <> "?"}
};

script = script /. v :> processSegment[{u}];

stripPunct[s_String] :=
FixedPoint[
If[MatchQ[StringTake[#, -1], "!" | "?" | "." | ";" | " "],
StringDrop[#, -1], #] &,
s]

processSegment[s_] :=
StringJoin@Riffle[
s /. {"I" -> "you", "my" -> "your", "your" -> "my", "myself" ->
"yourself",
"you are" -> "I am", "you're" -> "I am", "you" -> "me"},
" "]

While[StringLength[str = InputString[]] > 0,
With[{ss = StringSplit@stripPunct@ToLowerCase@str},
Print@RandomChoice@RandomChoice[ ss /. List /@ Select[script,
MatchQ[ss, First[#]] &] ]
]]

Note: It is recommended to run this from the command line instead of
the Front End, otherwise input will be read through an ugly popup
window.

[Szabolcs]

On Feb 23, 11:12 pm, Szabolcs <szhor...@gmail.com> wrote:
> so I tried to write a Mathematica version

I found a very old (from '92) implementation here:
http://140.177.205.65/infocenter/MathSource/1818/

[Ben Bacarisse]

Szabolcs <szho...@gmail.com> writes:

> On Feb 23, 11:12 pm, Szabolcs <szhor...@gmail.com> wrote:
>> so I tried to write a Mathematica version
>
> I found a very old (from '92) implementation here:

I find it slightly sad that a program from '92 is considered very old!
Especially in this context since Eliza dates from about '66, I think.

--
Ben.

[Ken Tilton]

Stevan Apter wrote:
> thanks for asking ken.
>
> e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?#E
> " "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
> .q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}

Wonderful. I will post this over on the Arc forum, I think they are
headed your way.

So how big a chunk can a K guru toss off without taking a breath, if you
will? I suppose it is like any language, developing bits and pieces
before connecting it all. My suspicion is one can get off more
functionality simply from the lower character count, once they are all
known fluently.

kenny

--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/

"In the morning, hear the Way;
in the evening, die content!"
-- Confucius

[William James]

Here's a shorter Ruby version. Regular expressions are used
in the script.

Script =
[ /father|mother|brother|sister/i, "Tell me about your 0."],
[ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were
1."]],
[ /\bI will (.*)/i, "Do you think it's wise to 1?"],
[ /\bI (.*)/i, "Why do you 1?" ],
[ /\b(you|your|yours)\b/i, ["We're talking about you, not me.",

"Please don't be so personal."]],

[ /.*/, ["That's very interesting. Do go on.",

"Tell me more.",
"I'm not sure that I understand you fully.",

"Can you elaborate on that?" ]]

def change_person s
h = { 'I','you', 'my','your', 'myself','yourself',

'you are','I am', "you're","I am" }

s.scan(/you are|you're|\w+|\W+/).map{|s|

h[s] or h.invert[s] or s }.join.sub( / I$/, " me" )
end

while true
print "? "
break if (resp = gets.strip.sub(/[.!?,;]+$/, "")) == 'quit'
Script.each{|ary|
if (md = resp.match( ary[0] ).to_a) != []
t = Array( ary[1] )
# Replies are rotated for variety.
puts t.push(t.shift)[0].gsub(/\d/){change_person md[$&.to_i]}
break
end }
end

[Szabolcs]

On Feb 24, 1:01 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

It depends on the language. Mathematica came a long way since 1992.

[Mark Tarver]

> e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?#E
>      " "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
>      .q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}
>

Wow, looks like APL - also famous for inscrutable 1 liners.

Nothing from the big players Haskell, O'Caml & ML so far.

So far I've got

Lisp 150 LOC ................ Peter Norvig
Qi (slightly revised) 63 LOC .................Mark Tarver
Ruby 53 LOC .................William James
Q 10 LOC ..................Steven Apter
K 3 LOC ...................Steven Apter

Mark

[Mark Tarver]

Sorry I missed a couple of later attempts

Lisp                       150 LOC  ................ Peter Norvig
Qi (slightly revised)  63 LOC   .................Mark Tarver
Ruby                      53 LOC   .................William James
Q                           10 LOC   ..................Steven Apter
K                             3 LOC  ...................Steven Apter

Ruby (again) 17 LOC ...................William James
Mathematica 20 LOC .................. Szabolcs

Mark

[Stevan Apter]

"Ken Tilton" <kenny...@optonline.net> wrote in message news:47c0cf12$0$8071$607e...@cv.net...

>
>
> Stevan Apter wrote:
>> thanks for asking ken.
>>
>> e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?#E
>> " "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
>> .q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}
>
> Wonderful. I will post this over on the Arc forum, I think they are
> headed your way.
>
> So how big a chunk can a K guru toss off without taking a breath, if you
> will? I suppose it is like any language, developing bits and pieces
> before connecting it all. My suspicion is one can get off more
> functionality simply from the lower character count, once they are all
> known fluently.

i now prefer developing in q, which is k without ambivalence (symbols denote
binary functions only, unary functions have keywords.)

based on what i've seen, my guess is that this problem has a k solution
half the size of mine, given a better representation of the prompt-respond
script. in general, that seems to be the key to good k (and as mark observed,
APL) programming: tune your data to the primitives.

[William James]

The K version doesn't do everything that the Ruby
versions do. It doesn't change "I" in the user's
response to "you" when throwing it back at the user,
for example.

When there are multiple possible replies to a user's
input, the Ruby program rotates those replies so that
not one will be repeated until all have been used.

[Stevan Apter]

yes it does.

prompts:

e"hi. i'm going to be your worst nightmare"
e"i think you're full of it."
e"my mother told me so."
e"no. you tell me about yours."
e"you're obviously retarded."
e"damn your eyes!"
e"understand a kick in the pants?"
e"i always ignore idiots."
e"i am afraid of dinosaurs"

responses:

"have you always been going to be my worst nightmare?
"why do you think i am full of it?"
"tell me about your mother."
"please don't be so personal."

"can you elaborate on that?"
"can you elaborate on that?"

"that's very interesting. do go on."

"why do you always ignore idiots?"
"have you always been afraid of dinosaurs?"

a few observations:

the 'i' function gives you prompt-and-respond in the console by
call 'e' until the user gives no prompt:

i:{while[count r:read0 0;-1"? ",e r;]}

the 'P' function maps first- and second-person:

P:{(y,x,z)(x,y)?z}.`$(("you";"your";"yourself";"i'm";"i am");("i";"my";"myself";"you are";"you're"))

instead of rotating multiple-responses, the k version picks a
response randomly from the set. this is less predictable than
rotation.

but i'm not surprised that the ruby version is so small. it's
a nice language, and i like the enthusiasm of its practitioners.

"William James" <w_a_...@yahoo.com> wrote in message news:a404c407-ac00-4665...@v3g2000hsc.googlegroups.com...

[William James]

Stevan Apter wrote:
> thanks for asking ken.
>
> e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?#E
> " "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
> .q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}
>
> it's just a single eye-watering case statement:
>
> if no keyword match in A, then return a default response from E
> else if no substitution in the response c picked from C, return c
> else substitute and return

This does so little that it should be no more than 2 lines.
In Ruby:

S =

[ /father|mother|brother|sister/i, "Tell me about your 0."],
[ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were
1."]],
[ /\bI will (.*)/i, "Do you think it's wise to 1?"],
[ /\bI (.*)/i, "Why do you 1?" ],

[ /\b(you|your|yours)\b/i, ["We're talking about you, not me.",

"Please don't be so personal."]],

[ /.*/, ["That's very interesting. Do go on.",

"Tell me more.",
"I'm not sure that I understand you fully.",
"Can you elaborate on that?" ]]

(gets;sub(/[.!?,; ]+$/,"");x=Array(S.find{|a|$m=$_.match(a[0])}[1])
puts x[rand(x.size)].gsub(/\d/){$m.to_a[$&.to_i]}) while 9

Although cryptic, it should make more sense to most programmers
than the K code.

[Stevan Apter]

the use of regular expressions can certainly make the code smaller,
as your example demonstrates. i wonder though whether it is entirely
in keeping with the spirit of the exercise, which requires that:

1. The script itself should be changeable by any novice. That is to
say that it should not
be a pile of hard-wired code written in the native language of
the program or require
deep programming skills.

not that it would help make the k code shorter, since regexp isn't
built into k.

"William James" <w_a_...@yahoo.com> wrote in message news:5fd7be4f-8465-44fd...@f47g2000hsd.googlegroups.com...

[William James]

Stevan Apter wrote:
> yes it does.

What does what? Please don't top-post.

>
> prompts:
>
> e"hi. i'm going to be your worst nightmare"
> e"i think you're full of it."
> e"my mother told me so."
> e"no. you tell me about yours."
> e"you're obviously retarded."
> e"damn your eyes!"
> e"understand a kick in the pants?"
> e"i always ignore idiots."
> e"i am afraid of dinosaurs"
>
> responses:
>
> "have you always been going to be my worst nightmare?
> "why do you think i am full of it?"
> "tell me about your mother."
> "please don't be so personal."
> "can you elaborate on that?"
> "can you elaborate on that?"
> "that's very interesting. do go on."
> "why do you always ignore idiots?"
> "have you always been afraid of dinosaurs?"

The K (not the Q) program was:

e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?
#E
" "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
.q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}

I don't see "you", "your", "my", "myself", "yourself", etc.
So how can it change "your" to "my"?
I was talking about the K program; you're talking about the Q program.

>
> a few observations:
>
> the 'i' function gives you prompt-and-respond in the console by
> call 'e' until the user gives no prompt:
>
> i:{while[count r:read0 0;-1"? ",e r;]}

I was talking about the K program; you're talking about the Q program.

>
> the 'P' function maps first- and second-person:
>
> P:{(y,x,z)(x,y)?z}.`$(("you";"your";"yourself";"i'm";"i am");("i";"my";"myself";"you are";"you're"))

So this will change "your" to "my". Will it, like the Ruby program,
change "my" to "your"?

>
> instead of rotating multiple-responses, the k version picks a
> response randomly from the set. this is less predictable than
> rotation.

That has the defect of possibly repeating the same response
immediately instead of cycling through all of the responses
before repeating.

[William James]

On Feb 24, 8:37 am, "Stevan Apter" <encryptednos...@nsl.com> wrote:
> the use of regular expressions can certainly make the code smaller,
> as your example demonstrates. i wonder though whether it is entirely
> in keeping with the spirit of the exercise, which requires that:
>
> 1. The script itself should be changeable by any novice. That is to
> say that it should not
> be a pile of hard-wired code written in the native language of
> the program or require
> deep programming skills.

I understand your misgivings, and I considered that myself.
Regular expressions are used in many programming languages and
Unix utilities (awk, Perl, grep, sed, etc.). All good text
editors support them, so anyone who is serious about using
computers should familiarize himself with them. For example,
say he's editing a large file and wants to find a line that
has "foo" followed later in the line by "bar"; he'd simply
search for "foo.*bar". How would that be done without
regular expressions? I don't think that learning about
regular expressions means learning "deep programming skills".
But yes, using my shorter program would be harder for
a novice.

>
> not that it would help make the k code shorter, since regexp isn't

> built into k."William James" <w_a_x_...@yahoo.com> wrote in messagenews:5fd7be4f-8465-44fd...@f47g2000hsd.googlegroups.com...

[Dimitre Liotev]

Mark Tarver <dr.mt...@ukonline.co.uk> writes:

So K wins the competition in brevity, but does the ability to squeeze
code into illegible character blobs say anything about the suitability
of a programming language for writing readable and understandable
programs? I'd rather follow the principle that "Programs must be written
for people to read, and only incidentally for machines to execute."...

--
Dimitre Liotev
(format t "~{~a~}" (reverse '("et" "n" "in." "a" "zn" "@" "l" "d")))

[Stevan Apter]

i'd rather say: "programs (in L) should be readable by people (who know L)." i have no idea how
to determine absolute readability (except to require that the font-size be within a certain range.)

"Dimitre Liotev" <no...@email.com> wrote in message news:_qqdnckGTcUDG1za...@giganews.com...

[Stevan Apter]

"William James" <w_a_...@yahoo.com> wrote in message news:cfd9901a-3105-43dd...@e60g2000hsh.googlegroups.com...

both the k and the q program use P. did mark have this feature in his
Qi version?

>
>>
>> a few observations:
>>
>> the 'i' function gives you prompt-and-respond in the console by
>> call 'e' until the user gives no prompt:
>>
>> i:{while[count r:read0 0;-1"? ",e r;]}
>
> I was talking about the K program; you're talking about the Q program.

activate the k script with: while[#r:0:0;-1"? ",e r]

>
>>
>> the 'P' function maps first- and second-person:
>>
>> P:{(y,x,z)(x,y)?z}.`$(("you";"your";"yourself";"i'm";"i am");("i";"my";"myself";"you are";"you're"))
>
> So this will change "your" to "my". Will it, like the Ruby program,
> change "my" to "your"?

yes, as should be obvious by inspecting the sample i/o above.

>
>>
>> instead of rotating multiple-responses, the k version picks a
>> response randomly from the set. this is less predictable than
>> rotation.
>
> That has the defect of possibly repeating the same response
> immediately instead of cycling through all of the responses
> before repeating.

unlike humans, who never repeat themselves. :-)

[Dimitre Liotev]

William James <w_a_...@yahoo.com> writes:

> This does so little that it should be no more than 2 lines.
> In Ruby:
>
> S =
> [ /father|mother|brother|sister/i, "Tell me about your 0."],
> [ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
> [ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were

[...]

He, Ruby is so verbose, both K an Q beat it to death when it comes to
brevity. Witness the power, a sudoku solver in K:

f:{$[&/x;,x;,/f'@[x;i;:;]'&27=x[,/p i:x?0]?!10]}

Not that I understand what this eyesore means, but according to this
blog it is supposed to be a sudoku solver:

http://www.wagerlabs.com/blog/2008/02/shortest-sudoku.html

Time to abandon Ruby and move to K?

[Arved Sandstrom]

Stevan Apter wrote:

> i'd rather say: "programs (in L) should be readable by people (who know
> L)." i have no idea how to determine absolute readability (except to
> require that the font-size be within a certain range.)
>

This fellow (http://www.perlmonks.org/?node_id=592616) has some thoughts on
absolute readability. I think it's a sensible article.

AHS
--
* change 'two' to '2' to email me

[Rainer Joswig]

In article
<d27c55f3-4ee0-41a6...@t66g2000hsf.googlegroups.com>,
Mark Tarver <dr.mt...@ukonline.co.uk> wrote:

Below is the Common Lisp version from Norvig.

I have removed the duplicated definitions from his code.
He is developing the code in his book (especially the pattern
matcher), so he has more than one version of several functions.
The code is also written in a very readable style,
to support the educational purpose of his book.

When the comments and the rules are removed, the code
is about 110 lines.

;;; ==============================

;;; -*- Mode: Lisp; Syntax: Common-Lisp; -*-
;;; Code from Paradigms of Artificial Intelligence Programming
;;; Copyright (c) 1991 Peter Norvig

(defun starts-with (list x)
"Is x a list whose first element is x?"
(and (consp list) (eql (first list) x)))

(defun flatten (the-list)
"Append together elements (or lists) in the list."
(mappend #'mklist the-list))

(defun mklist (x)
"Return x if it is a list, otherwise (x)."
(if (listp x)
x
(list x)))

(defun mappend (fn the-list)
"Apply fn to each element of list and append the results."
(apply #'append (mapcar fn the-list)))

(defun random-elt (choices)
"Choose an element from a list at random."
(elt choices (random (length choices))))

(defun variable-p (x)
"Is x a variable (a symbol beginning with `?')?"
(and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

(defconstant fail nil "Indicates pat-match failure")

(defconstant no-bindings '((t . t))
"Indicates pat-match success, with no variables.")

(defun get-binding (var bindings)
"Find a (variable . value) pair in a binding list."
(assoc var bindings))

(defun binding-val (binding)
"Get the value part of a single binding."
(cdr binding))

(defun lookup (var bindings)
"Get the value part (for var) from a binding list."
(binding-val (get-binding var bindings)))

(defun match-variable (var input bindings)
"Does VAR match input? Uses (or updates) and returns bindings."
(let ((binding (get-binding var bindings)))
(cond ((not binding) (extend-bindings var input bindings))
((equal input (binding-val binding)) bindings)
(t fail))))

(defun extend-bindings (var val bindings)
"Add a (var . value) pair to a binding list."
(cons (cons var val)
;; Once we add a "real" binding,
;; we can get rid of the dummy no-bindings
(if (and (eq bindings no-bindings))
nil
bindings)))

(defun pat-match (pattern input &optional (bindings no-bindings))
"Match pattern against input in the context of the bindings"
(cond ((eq bindings fail) fail)
((variable-p pattern)
(match-variable pattern input bindings))
((eql pattern input) bindings)
((segment-pattern-p pattern)
(segment-match pattern input bindings))
((and (consp pattern) (consp input))
(pat-match (rest pattern) (rest input)
(pat-match (first pattern) (first input)
bindings)))
(t fail)))

(defun segment-pattern-p (pattern)
"Is this a segment matching pattern: ((?* var) . pat)"
(and (consp pattern)
(starts-with (first pattern) '?*)))

(defun segment-match (pattern input bindings &optional (start 0))
"Match the segment pattern ((?* var) . pat) against input."
(let ((var (second (first pattern)))
(pat (rest pattern)))
(if (null pat)
(match-variable var input bindings)
;; We assume that pat starts with a constant
;; In other words, a pattern can't have 2 consecutive vars
(let ((pos (position (first pat) input
:start start :test #'equal)))
(if (null pos)
fail
(let ((b2 (pat-match
pat (subseq input pos)
(match-variable var (subseq input 0 pos)
bindings))))
;; If this match failed, try another longer one
(if (eq b2 fail)
(segment-match pattern input bindings (+ pos 1))
b2)))))))

(defun rule-pattern (rule) (first rule))
(defun rule-responses (rule) (rest rule))

(defun use-eliza-rules (input)
"Find some rule with which to transform the input."
(some #'(lambda (rule)
(let ((result (pat-match (rule-pattern rule) input)))
(if (not (eq result fail))
(sublis (switch-viewpoint result)
(random-elt (rule-responses rule))))))
*eliza-rules*))

(defun switch-viewpoint (words)
"Change I to you and vice versa, and so on."
(sublis '((I . you) (you . I) (me . you) (am . are))
words))

(defun read-line-no-punct ()
"Read an input line, ignoring punctuation."
(read-from-string
(concatenate 'string "(" (substitute-if #\space #'punctuation-p
(read-line))
")")))

(defun punctuation-p (char) (find char ".,;:`!?#-()\\\""))

(defun print-with-spaces (list)
(format t "~{~a ~}" list))

(defun eliza ()
"Respond to user input using pattern matching rules."
(loop
(print 'eliza>)
(let* ((input (read-line-no-punct))
(response (flatten (use-eliza-rules input))))
(print-with-spaces response)
(if (equal response '(good bye)) (RETURN)))))

(defparameter *eliza-rules*
'((((?* ?x) hello (?* ?y))
(How do you do. Please state your problem.))
(((?* ?x) I want (?* ?y))
(What would it mean if you got ?y)
(Why do you want ?y) (Suppose you got ?y soon))
(((?* ?x) if (?* ?y))
(Do you really think its likely that ?y) (Do you wish that ?y)
(What do you think about ?y) (Really-- if ?y))
(((?* ?x) no (?* ?y))
(Why not?) (You are being a bit negative)
(Are you saying "NO" just to be negative?))
(((?* ?x) I was (?* ?y))
(Were you really?) (Perhaps I already knew you were ?y)
(Why do you tell me you were ?y now?))
(((?* ?x) I feel (?* ?y))
(Do you often feel ?y ?))
(((?* ?x) I felt (?* ?y))
(What other feelings do you have?))))

;;; ==============================

[Stevan Apter]

"Arved Sandstrom" <asands...@eastlink.ca> wrote in message news:ZOhwj.38548$FO1.4192@edtnps82...

> Stevan Apter wrote:
>
>> i'd rather say: "programs (in L) should be readable by people (who know
>> L)." i have no idea how to determine absolute readability (except to
>> require that the font-size be within a certain range.)
>>
> This fellow (http://www.perlmonks.org/?node_id=592616) has some thoughts on
> absolute readability. I think it's a sensible article.

thanks.

languages make different trade-offs. i was once asked to write a style-manual
for programmers new to k. this is the result: www.nsl.com/papers/style.pdf.

eliza.q mostly follows the rules. eliza.k breaks them all!

now, if you want to see some gorgeous C code ... http://nsl.com/papers/origins.htm.

:-)

[Neelakantan Krishnaswami]

In article
<<d27c55f3-4ee0-41a6...@t66g2000hsf.googlegroups.com>>,
Mark Tarver <dr.mt...@ukonline.co.uk> wrote:

>> e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?#E
>>      " "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
>>      .q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}
>>
>
> Wow, looks like APL - also famous for inscrutable 1 liners.

J and K are descendants of APL that use ASCII as their character set.

--
Neel R. Krishnaswami
ne...@cs.cmu.edu

[Ken Tilton]

Stevan Apter wrote:
>
> "Arved Sandstrom" <asands...@eastlink.ca> wrote in message
> news:ZOhwj.38548$FO1.4192@edtnps82...
>
>> Stevan Apter wrote:
>>
>>> i'd rather say: "programs (in L) should be readable by people (who know
>>> L)." i have no idea how to determine absolute readability (except to
>>> require that the font-size be within a certain range.)
>>>
>> This fellow (http://www.perlmonks.org/?node_id=592616) has some
>> thoughts on
>> absolute readability. I think it's a sensible article.
>
>
> thanks.
>
> languages make different trade-offs. i was once asked to write a
> style-manual
> for programmers new to k. this is the result:
> www.nsl.com/papers/style.pdf.

Looks familiar. We may have met briefly if you were in that office on
the 30th floor at UBS with the Special K carton outside. I wandered in
one day, ended up talking about GC with the K crew, got a free style
guide and K manual for my trouble. Might still have it somewhere.

I was a per diem guy so did not get the K training. :(

[William James]

On Feb 24, 9:56 am, "Stevan Apter" <encryptednos...@nsl.com> wrote:
> "William James" <w_a_x_...@yahoo.com> wrote in messagenews:cfd9901a-3105-43dd...@e60g2000hsh.googlegroups.com...

So what you posted as the k program was not the complete
k program.

> did mark have this feature in his
> Qi version?

No.

>
>
>
> >> a few observations:
>
> >> the 'i' function gives you prompt-and-respond in the console by
> >> call 'e' until the user gives no prompt:
>
> >> i:{while[count r:read0 0;-1"? ",e r;]}

So what you posted as the k program was not the complete
k program.

Mark Tarver was led to believe that the complete program
was 3 lines.

Perhaps the complete k program would be something like

P:{(y,x,z)(x,y)?z}[`$("you";"your";"yourself";"i'm";"i am");`$
("i";"my";"myself";"you are";"you're")]

e:{$[(#b)=i:(|/'b:(w@:&~(w:(`$" "\:x@&~x in".?"))in`)in\:/:A)?1b;E@*1?
#E
" "~n:c@*,/(c:{x@*1?#x}C i)ss/:N;c
.q.ssr[c;n;" "/:$(),P'(w[k],p:1_'(0,1+k:b[i]?1b)_`,w)"I"$n]]}

i:{while[count r:read0 0;-1"? ",e r;]}

> >> instead of rotating multiple-responses, the k version picks a

> >> response randomly from the set. this is less predictable than
> >> rotation.
>
> > That has the defect of possibly repeating the same response
> > immediately instead of cycling through all of the responses
> > before repeating.
>
> unlike humans, who never repeat themselves. :-)

The purpose of having multiple replies is to put off
repetition as long as possible.

[William James]

On Feb 22, 5:49 am, Mark Tarver <dr.mtar...@ukonline.co.uk> wrote:
> Having got 3936 LOC through a 4000 LOC implementation, I thought I'd
> do some recreational
> hacking and do an old old program I've not looked at for some time -
> Eliza. You all know Eliza well enough for me not to have to spell it
> out. The challenge is to implement or dig up an Eliza program (you
> don't have to write it yourself) in your favourite FPL. Note that the
> script that drives Eliza's responses should not be counted towards the
> LOC count. Some constraints.
>

> 1. The script itself should be changeable by any novice. That is to
> say that it should not
> be a pile of hard-wired code written in the native language of
> the program or require
> deep programming skills.
>

> 2. The program should receive keyboard input from the user -
> including the usual punctuation
> and any characters he wants to enter without crashing.
>
> During the Harrop Wars on comp.lang.lisp a lot of stuff was thrown
> around about the desirability of pattern matching. The challenge is
> interesting because it involves a style of pattern-matching called
> 'segment pattern matching' that is not hard-wired into most FPLs and
> I'd like to see how well different FPLs cope with something outside
> the standard.
>

> Oh last thing; don't get too uptight about this. It's only a bit of
> fun.
>
> Mark

Unlike my 2-line Ruby version, this one changes first-person
pronouns to second-person, and vice versa.

S =
[ /father|mother|brother|sister/i, "Tell me about your 0."],
[ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were

1."]],
[ /\bI will (.*)/i, "Do you think it's wise to 1?"],
[ /\bI (.*)/i, "Why do you 1?" ],
[ /\b(you|your|yours)\b/i, ["We're talking about you, not me.",
"Please don't be so personal."]],
[ /.*/, ["That's very interesting. Do go on.",
"Tell me more.",
"I'm not sure that I understand you fully.",
"Can you elaborate on that?" ]]

P=Hash[*"I|you|my|your|myself|yourself|you are|I am|you're|I
am".split('|')]

(gets;sub(/[.!?,; ]+$/,"");x=Array(S.find{|a|$m=$_.match(a[0])}[1])

puts x[rand(x.size)].gsub(/\d/){$m.to_a[$&.to_i].
scan(/you are|you're|\w+|\W+/).map{|s|P[s]||P.invert[s]||s}.join})
while 9

[William James]

On Feb 24, 9:00 am, Dimitre Liotev <no...@email.com> wrote:

> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
> > Sorry I missed a couple of later attempts
>
> > Lisp 150 LOC ................ Peter Norvig
> > Qi (slightly revised) 63 LOC .................Mark Tarver
> > Ruby 53 LOC .................William James
> > Q 10 LOC ..................Steven Apter
> > K 3 LOC ...................Steven Apter
> > Ruby (again) 17 LOC ...................William James
> > Mathematica 20 LOC .................. Szabolcs
>
> > Mark
>
> So K wins the competition in brevity,

I'm not so sure. The three lines of K were not a
complete program. I just posted a 4-line Ruby program
that does everything the Q program does.

> but does the ability to squeeze
> code into illegible character blobs say anything about the suitability
> of a programming language for writing readable and understandable
> programs? I'd rather follow the principle that "Programs must be written
> for people to read, and only incidentally for machines to execute."...

If you really believe that, then you must agree that the
language used in your signature was designed to be easy
for a computer, not a human, to parse.

>
> --
> Dimitre Liotev
> (format t "~{~a~}" (reverse '("et" "n" "in." "a" "zn" "@" "l" "d")))

Ruby:

%w(et n in. a zn @ l d).reverse.join

Now that's easier for a human to read! Of course, Lisp makes
it easy to have macros that generate code, which is a powerful
feature.

[William James]

g**gle split some of the lines in my 4-line code above.
Let's make it 6 lines.

S =
[ /father|mother|brother|sister/i, "Tell me about your 0."],
[ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
[ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were
1."]],
[ /\bI will (.*)/i, "Do you think it's wise to 1?"],
[ /\bI (.*)/i, "Why do you 1?" ],
[ /\b(you|your|yours)\b/i, ["We're talking about you, not me.",
"Please don't be so personal."]],
[ /.*/, ["That's very interesting. Do go on.",
"Tell me more.",
"I'm not sure that I understand you fully.",
"Can you elaborate on that?" ]]

P = Hash[ *"I|you|my|your|myself|yourself|you are|I am|you're|I am".
split('|')]
( gets;sub(/[.!?,; ]+$/,"");x=Array(S.find{|a|$m=$_.match(a[0])}[1])

[Arved Sandstrom]

William James wrote:

> On Feb 24, 9:00 am, Dimitre Liotev <no...@email.com> wrote:

[ SNIP ]

>> Dimitre Liotev
>> (format t "~{~a~}" (reverse '("et" "n" "in." "a" "zn" "@" "l" "d")))
>
> Ruby:
>
> %w(et n in. a zn @ l d).reverse.join
>
> Now that's easier for a human to read! Of course, Lisp makes
> it easy to have macros that generate code, which is a powerful
> feature.

And a succinct but not-quite-so-easy-to-read J version :-) -

; |. ;: 'et n in. a zn @ l d'

[Brian Adkins]

On Feb 24, 11:18 am, Dimitre Liotev <no...@email.com> wrote:

> William James <w_a_x_...@yahoo.com> writes:
> > This does so little that it should be no more than 2 lines.
> > In Ruby:
>
> > S =
> > [ /father|mother|brother|sister/i, "Tell me about your 0."],
> > [ /\b(am|i'm) (.*)/i, ["Why are you 2?","Have you always been 2?"]],
> > [ /\bI was (.*)/i, ["Why were you 1?","I can't believe you were
>
> [...]
>
> He, Ruby is so verbose, both K an Q beat it to death when it comes to
> brevity. Witness the power, a sudoku solver in K:
>
> f:{$[&/x;,x;,/f'@[x;i;:;]'&27=x[,/p i:x?0]?!10]}
>
> Not that I understand what this eyesore means, but according to this
> blog it is supposed to be a sudoku solver:

Boy, I have mixed emotions when reading that. On the one hand, I see
what at first glance appears to be a collection of random characters.
On the other hand, I recognize I have zero knowledge of K, so I'm
slightly curious about a language that seems to take conciseness to an
obscene level.

Here's a question. Would it be easier to add some verbosity and
formatting to make the above K program more readable to those who
don't know K, or to take a readable program in another language and
make it that short? :)

[Stevan Apter]

"Brian Adkins" <lojic...@gmail.com> wrote in message news:ba2f0ce4-9bcc-4de3...@p73g2000hsd.googlegroups.com...

>> He, Ruby is so verbose, both K an Q beat it to death when it comes to
>> brevity. Witness the power, a sudoku solver in K:
>>
>> f:{$[&/x;,x;,/f'@[x;i;:;]'&27=x[,/p i:x?0]?!10]}
>>
>> Not that I understand what this eyesore means, but according to this
>> blog it is supposed to be a sudoku solver:
>
> Boy, I have mixed emotions when reading that. On the one hand, I see
> what at first glance appears to be a collection of random characters.
> On the other hand, I recognize I have zero knowledge of K, so I'm
> slightly curious about a language that seems to take conciseness to an
> obscene level.
>
> Here's a question. Would it be easier to add some verbosity and
> formatting to make the above K program more readable to those who
> don't know K, or to take a readable program in another language and
> make it that short? :)

in k symbols like + are ambivalent: x+y is addition, +x is transposition.
q is k with keywords for the unary case: x+y is addition, flip x is
transposition.

in f we have one instance of a primitive with four arguments: @[x;y;:;w].
so we can define:

amend:{@[x;y;:;z]}

x?y finds y in x. let's cover that as well, and give it infix syntax:

.q.find:?

$[x;y;z;...] is the conditional.

now rewrite f in q like this:

f:{$[all x;enlist x;raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}