handling numbers with scheme.
john...@my-deja.com
I was introduced to a simple game named math bowling, which I'm sure
many of you know. The game's rules are as follows: you are given 3
random numbers. Using these numbers you have to form a math expression
to equal all the numbers from 1 through 10--you must use all numbers and
you can't use a number more than once. For example, if my 3 random
numbers are 5, 3 and 1, I can do 5 - 3 + 1 to equal 3, and 5 - 3^1 to
equal 2, and so on until I hit all the numbers ('pins') from 1 through
10.
I wanted to write a program that simulates this game, and since I'm
learning Scheme I was eager to use it. I am sure that with all of
Scheme's clever ways of representing data there's probably a neat way of
doing this, but I ran into several problems. To get an idea of how this
will be done, I decided to do a quick-n-dirty implementation in Perl,
and here's the basic procedure:
1. Generate 3 random numbers and ask the user to enter an expression
using these numbers (and also what number between 1-10 the expression is
supposed to equal)
2. Now I have an expression that uses regular math notation, like "3 +
5 - 1". Since Perl has an eval function, all I have to do is pass the
expression to it and see if the result equals the number the user is
trying to solve for. Scheme on the other hand uses the Polish notation
and I can't think of a clean way to convert the user's expression into
that notation.
3. I have to perform tests to see whether the user is cheating by not
using all the numbers, or using certain numbers more than once. To do
this in Perl, I used a regular expression to pull out all the numbers
from the expression and put them in an array. In addition to that
array, I also have an array with the random numbers. All I have to do
now to make sure the user isn't cheating is go through every number used
in the expression and make sure that repeats itself in that array as
many times as it does in the random numbers' array. I can't explain it
very well, so here's the Perl snippet:
@nums_used = split /\D+/, $arith;
for (@nums_used) {
if (count_appears($_, \@rand_nums) !=
count_appears($_, \@nums_used)) {
print "cheater."
last;
}
}
count_appears is a function that returns the number of times an element
appears in an array.
I really want to learn Scheme and see how this would be represented in
it. Can someone give me a few hints or ideas on how to approach this
problem? Also, if you have general improvements to the procedure
described above (which is just a way about solving the problem,
regardless of what language you're using) please let me know.
Thanks a lot!
-- John
Sent via Deja.com
http://www.deja.com/
brl...@my-deja.com
> 2. Now I have an expression that uses regular math notation, like "3 +
> 5 - 1". Since Perl has an eval function, all I have to do is pass the
> expression to it and see if the result equals the number the user is
> trying to solve for.
If this was for a web interface, passing user-supplied strings to eval
would be a security risk. If you restrict operations to +, -, *, /, ^,
then a regexp would work to check it. Spelled-out math functions could
probably also be done with a regexp if you're good with regexps and
careful.
In Scheme it's easy to write an extensible function that reliably checks
for use of certain functions:
(define (illegal-sym? expr)
(cond ((symbol? expr)
(if (memq expr '(+ - * / expt))
#f
expr))
((pair? expr)
(or (illegal-sym? (car expr))
(illegal-sym? (cdr expr))))
(else #f)))
--
(for-each (lambda (str) (display (string-append (make-string (- 40
(quotient (string-length str) 2)) #\space) str)) (newline)) '(""
"Bruce Lewis" "MIT 1990" " http://brl.sourceforge.net/
")) ; I rarely read mail sent to brl...@my-deja.com
ol...@pobox.com
numbers and operations with a whitespace so you can rely on the
standard 'read' procedure), the following simplest recursive descent
parser can convert from an infix to prefix notation. The parser is
designed in such a way that its output can be passed to the 'eval'
function. Alternatively, the parser can be modified to do the
evaluation itself. In the process of evaluation, it can verify that
all the numbers-arguments occurred exactly the right number of times.
BTW, monads could make writing such a generic parser very easy.
; A simple recursive descent parser
; It implements the grammar
; <exp> ::= <term> { (+|-) term }*
; <term> ::= [-]factor { (*|/) factor }*
; <factor> ::= <prim> [^ <prim>]
; <prim> ::= <variable> | <number> | ( <exp> )
(define (variable? x)
(and (symbol? x) (char-alphabetic? (string-ref (symbol->string x)
0))))
; raw-exp is the list of tokens
(define (parse raw-exp)
; Advance the input
(define (next-token)
(set! raw-exp (cdr raw-exp)))
; if the top of the raw-exp contains one of the symbols in symbs,
; advance the input and return the encountered symbol.
; Otherwise, return #f
(define (expect symbs)
(and (pair? raw-exp)
(cond
((memq (car raw-exp) symbs) =>
(lambda (symb) (next-token) (car symb)))
(else #f))))
; + and - associate to the left
(define (parse-exp)
(let loop ((accum (parse-term)))
(cond
((expect '(+ -)) =>
(lambda (symb)
(loop (list symb accum (parse-term)))))
(else accum))))
; * and / associate to the left
(define (parse-term)
(let loop ((accum
(if (expect '(-)) (list '- (parse-factor))
(parse-factor))))
(cond
((expect '(* /)) =>
(lambda (symb)
(loop (list symb accum (parse-factor)))))
(else accum))))
; Note that ^ associates to the right!
; 2^3^4 == 2^(3^4)
(define (parse-factor)
(let loop ((prim (parse-prim)))
(cond
((expect '(^))
(list 'expt prim (loop (parse-prim))))
(else prim))))
(define (parse-prim)
(let ((exp-old raw-exp))
(cond
((null? raw-exp) (error "EOF unexpected"))
((not (pair? raw-exp)) (set! raw-exp '()) exp-old)
((number? (car raw-exp)) (next-token) (car exp-old))
((variable? (car raw-exp)) (next-token) (car exp-old))
((pair? (car raw-exp))
(set! raw-exp (car raw-exp))
(let ((result (parse-exp)))
(set! raw-exp (cdr exp-old))
result)))))
(parse-exp))
(parse '(a + b * c + (- b + d) * e))
==> (+ (+ a (* b c)) (* (+ (- b) d) e))
(parse '(a + b * c - (- b + d) * e))
==> (- (+ a (* b c)) (* (+ (- b) d) e))
(parse '(a + b * c ^ (- d)))
==> (+ a (* b (expt c (- d))))
(parse '(5 - 3 + 1))
==> (+ (- 5 3) 1)
(eval (parse '(5 - 3 + 1)))
==> 3
(parse '(5 - 3 ^ 1))
==> (- 5 (expt 3 1))
(eval (parse '(5 - 3 ^ 1)))
==> 2
(parse '(5 ^ 3 ^ 1))
==> (expt 5 (expt 3 1))
Boris Smilga
> 2. Now I have an expression that uses regular math notation, like "3 +
> 5 - 1". Since Perl has an eval function, all I have to do is pass the
> expression to it and see if the result equals the number the user is
> trying to solve for. Scheme on the other hand uses the Polish notation
> and I can't think of a clean way to convert the user's expression into
> that notation.
You may have the user employ Cambridge-Polish as well. Under R5RS, you
can use the eval procedure [6.5, p.35] with environment-specifier,
say, (scheme-report-environment 5). The main problem here is, as Bruce
pointed out, that a malevolent and/or incompetent user can type in
such an expression that the system gets into some difficulties - so
you need to check it beforehand.
If you want to stick to infix notation, which is pretty possible,
you'll have to supply a parser. CMU repository has some code for
parsing - check out
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/code/parsing/0.html
But, since the syntax for your expressions is pretty straightforward,
you may want to skip all that heavyweight stuff and write your own
parser. The best strategy here would be, IMHO, to
1) generate a list of tokens out of the user's input and normalize
them from strings to symbols/numbers, aborting whenever you see
something non-arithmetical;
2) parse the list of symbols and convert it to s-expression,
validating the syntax;
3) check for missemantics (division by zero etc.);
4) eval as described above - if you've got through all prior steps,
the s-expression is guaranteed to be legal.
You may either divide your honesty checking between steps 3 and 4, or
put them into a separate step 5, which, in my opinion, is more proper.
Hope that helps. Keep in touch.
Yours,
Boris.
David Rush
> I was introduced to a simple game named math bowling,
> I wanted to write a program that simulates this game, and since I'm
> learning Scheme I was eager to use it. I am sure that with all of
> Scheme's clever ways of representing data there's probably a neat way of
> doing this, but I ran into several problems. To get an idea of how this
> will be done, I decided to do a quick-n-dirty implementation in Perl,
Oooh, mistake number 1. ;)
> 2. Now I have an expression that uses regular math notation, like "3 +
> 5 - 1". Since Perl has an eval function, all I have to do is pass the
> expression to it and see if the result equals the number the user is
> trying to solve for. Scheme on the other hand uses the Polish notation
> and I can't think of a clean way to convert the user's expression into
> that notation.
Well that's one of the benefits of formal study. IIRC, we had to solve
the infix->postfix problem (which is isomorphic to the prefix problem)
multiple times in school. The first time was a simple introduction to
stack manipulation, later it was part of a course on compiler design
related to operator-precedence parsing.
This is not actually an intimidating problem, although it can sound
that way. The basic algorithm for evaluating infix (which is embedded
in in the Perl interpreter) goes something like:
given: a table of operator precedence
a list representing an infix expression
a stack of operands
a stack of operators
1) initialize the stacks as empty
2) if the first element of the list is a number,
t) push it on the operand stack
f) if the operator has higher precedence than the top
of the operator stack,
t) push the operator
f) evaluate the top operator stack operator
goto step 2.f
Note: End of the expression list is treated as the lowest
precedence operator
> 3. I have to perform tests to see whether the user is cheating by not
> using all the numbers, or using certain numbers more than once.
This algorithm doesn't include some of the error checking (for stack
underflow) that you would need to include but it should be fairly
obvious where to do it. It should also be fairly obvious where to put
in yor game rules checking, too. I should mention that I *don't* think
that using a built-in eval function makes sense for this in *any*
language. All of the constraint checking can be far more efficiently
integrated into the preceding algorithm than by doing it separately
(since you have to develop most of the information needed to validate
in order to evaluate).
No, it's not a Scheme solution. I've already spent too much time on
this (and probably also made mistakes from hurrying) given my RL
constraints, but really it's not a hard problem in any language. I may
hack up a Scheme solution just for grins, but I suggest that you try
it yourself first.
david rush
--
Next to the right of liberty, the right of property is the most
important individual right ... and ... has contributed more to the
growth of civilization than any other institution established by the
human race.
-- Popular Government (William Howard Taft)
Christophe Rhodes
> No, it's not a Scheme solution. I've already spent too much time on
> this (and probably also made mistakes from hurrying) given my RL
> constraints, but really it's not a hard problem in any language. I may
> hack up a Scheme solution just for grins, but I suggest that you try
> it yourself first.
For this problem, a really rather good solution exists. It's for
Common Lisp, which means that there are more details, but Mark
Kantrowitz' infix notation package (available from the archives at
CMU) is versatile and useful.
From infix.cl
;;; Syntax:
;;;
;;; Begin the reader macro with #I( and end it with ). For example,
;;; #I( x^^2 + y^^2 )
;;; is equivalent to the Lisp form
;;; (+ (expt x 2) (expt y 2))
;;; but much easier to read according to some folks.
;;;
;;; If you want to see the expansion, type a quote before the #I form
;;; at the Lisp prompt:
;;; > '#I(if x<y<=z then f(x)=x^^2+y^^2 else f(x)=x^^2-y^^2)
;;; (IF (AND (< X Y) (<= Y Z))
;;; (SETF (F X) (+ (EXPT X 2) (EXPT Y 2)))
;;; (SETF (F X) (- (EXPT X 2) (EXPT Y 2))))
Converting into scheme is left as an exercise for the reader :)
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 524 842
(FORMAT T "(~@{~w ~}~3:*'~@{~w~^ ~})" 'FORMAT T "(~@{~w ~}~3:*'~@{~w~^ ~})")
ol...@pobox.com
Christophe Rhodes <cs...@cam.ac.uk> wrote:
> From infix.cl
> ;;; Begin the reader macro with #I( and end it with ).
What an excellent suggestion, to show off SRFI-10.
Given a sample reference implementation as outlined in SRFI-10, and
the declaration in the appendix, we can write
; Convert from Kelvins to degree F
(define (K->F x)
#,(I (x - 273.15) * 9 / 5 + 32))
(K->F 273.16)
==> 32.018000000000086 ; The triple point of water
(K->F 70)
==> -333.67 ; Approx. the normal boiling point of Nitrogen
(K->F 0)
==> -459.67 ; The unattainable
> ;;; If you want to see the expansion, type a quote before the #I
> ;;; form at the Lisp prompt:
The same advice holds, only for a Scheme prompt (Gambit's prompt '>'):
> '#,(I x ^ 2 + y ^ 2)
(+ (expt x 2) (expt y 2))
> '#,(I a + b * (- c + d) / f)
(+ a (/ (* b (+ (- c) d)) f))
Appendix
; Gambit-C 3.0
(include "read-apply.scm") ; see SRFI-10
(define (variable? x)
(and (symbol? x) (char-alphabetic? (string-ref (symbol->string x)
0))))
(define-reader-ctor 'I
(lambda raw-exp
... see the previous message on this thread for declarations
... of internal functions
... next-token, expect, parse-exp, parse-term, parse-factor
... which are elided here to save bandwidth
(define (parse-prim)
(let ((exp-old raw-exp))
(cond
((null? raw-exp) (error "EOF unexpected"))
((not (pair? raw-exp)) (set! raw-exp '()) exp-old)
((number? (car raw-exp)) (next-token) (car exp-old))
((variable? (car raw-exp)) (next-token) (car exp-old))
((pair? (car raw-exp))
(set! raw-exp (car raw-exp))
(let ((result (parse-exp)))
(set! raw-exp (cdr exp-old))
result)))))
(parse-exp)))