Page 1 of 2

newLISP Challenge: The seemingly simple 'my-or'

Posted: Sat Apr 04, 2009 11:22 pm
by itistoday
A TEST OF YOUR NEWLISP SKILLZ!

Something that spawned from this discussion was an interesting function called 'my-or' that I found in this Scheme tutorial.

my-or is a macro, but not just any macro, it's a safe one. It takes exactly two arguments and evaluates the first argument only once, and it's immune to variable capture. If the result of that evaluation is true, then that value is returned, otherwise, the result of evaluating the second argument is returned.

Sounds simple? Try it, it's not. Here, I'll help you out (evil grin). Here is the solution as written in Scheme:

Code: Select all

(define-macro my-or
  (lambda (x y)
    (let ((temp (gensym)))
      `(let ((,temp ,x))
         (if ,temp ,temp ,y)))))
Once you've written 'my-or', run it against this program to test it:

Code: Select all

(set 'temp 45)
(println "(my-or temp nil) = " (my-or temp nil))
(println "(my-or nil temp) = " (my-or nil temp))
(println "-----------")
(set 'value (my-or (begin (println "first arg") 1) (begin (println "second arg") 2)))
(println "should be 1: " value)
(println "-----------")
(set 'value (my-or (begin (println "first arg") nil) (begin (println "second arg") 2)))
(println "should be 2: " value)
IMPORTANT: In your implementation, make sure to name the symbol that you store the result of evaluating the first argument as 'temp'! Otherwise the variable-capture challenge is moot.

The winner is the first person to get the following output exactly:

Code: Select all

(my-or temp nil) = 45
(my-or nil temp) = 45
-----------
first arg
should be 1: 1
-----------
first arg
second arg
should be 2: 2
PRIZE

Hmm... since I'm also the developer of Espionage (OS X Leopard only), that is something that I can offer to the winner (if they want it). Of course you'll also receive the warm fuzzy feeling that comes with solving such challenges. :-)

Post your solution below if you've got it, I will give the solution on April 11th if no one solves it in that time.

Note: based on the solution presented below by Kazimir, the rules have been modified slightly, read my reply to him for the update.

Update: One solution has been presented by contestant Kazimir! But there's still another, faster solution possible!

Challenge is over! Congrats to Kazimir and newdep!

Posted: Sun Apr 05, 2009 12:05 am
by Kazimir Majorinc

Code: Select all

(load "http://www.instprog.com/Instprog.default-library.lsp") 

(set 'my-or0 (lambda-macro(i j)
               (let ((temp (eval i)))
                    (if temp
                        temp
                       (eval j)))))

(set 'my-or (protect2 'my-or 'my-or0 '(i j temp)))

Code: Select all

(my-or temp nil) = 45
(my-or nil temp) = 45
-----------
first arg
should be 1: 1
-----------
first arg
second arg
should be 2: 2
Described in article "don't fear dynamic scope (2)"

Posted: Sun Apr 05, 2009 12:13 am
by itistoday
Nice, as I'm an avid reader of your blog, I should have anticipated your answer Kazimir. :-)

If you'd like a license to Espionage then send me a PM with your full name and email and I'll send it to you.

However, your solution, although very interesting (and a nice approach to these kinds of problems in newLISP), isn't quite the one that I was looking for, so I'm still leaving the challenge (and an additional license) open, but modifying the rules a little bit:

I'm looking for a single macro function, that gets the job done without any other user-defined functions or macros, and is much shorter than the length of the combined user-defined functions that Kazimir used to solve it. :-D

Edit: Kazimir, even though you've already submitted a working solution to the challenge as stated previously, you are free to try again with the new modifications. :-)

Posted: Sun Apr 05, 2009 2:13 am
by Kazimir Majorinc

Code: Select all

(set 'my-or
  (lambda-macro (x y)
     (eval (let ((temp (sym (string (inc counter)))))
                (expand 
                
                  '(let ((temp (eval x)))
                          (if temp          ; Naive
                              temp          ; version
                              (eval y)))
                  

                 'temp)))))

Posted: Sun Apr 05, 2009 2:36 am
by itistoday
I wish I could declare you the winner, as that is essentially the newLISP equivalent if the Scheme solution (ugly isn't it?), however, because the solution as specified in the contest revision does not allow user-defined functions, you were forced to do this:

Code: Select all

(sym (string (inc counter)))
Whereas the proper solution would have used (gensym) as in the Scheme solution. If newLISP had a gensym function I suppose I would be unable to debate and would be begrudgingly forced to accept this as the winner, but thankfully for the competition it does not. :-)

Because the contest rules forbid the use of a user-defined gensym function, this macro as presented is not safe from variable capture. If I were to replace (set 'temp 45) with (set 'counter 45), your function would not produce the correct output.

Kazimir, you are still a brilliant programmer in my eyes, but it is possible to solve this problem within the scope of the contest rules. That solution remains to be found. :-)

Posted: Sun Apr 05, 2009 3:16 am
by Kazimir Majorinc

Code: Select all

(set 'my-or
  (lambda-macro (x y)
     (first (list (eval (let ((temp (sym (append (string (last (symbols))) "+"))))
                    (expand
               
                     '(let ((temp (eval x)))
                            (if temp          ; Naive
                              temp          ; version
                              (eval y)))
                 

                 'temp)))
                 
             (delete (last (symbols)))    ))))

Posted: Sun Apr 05, 2009 3:26 am
by itistoday
Wow.

I'm shocked and am laughing at the same time, you are incredible Kazimir!

That is a real surprise solution. At the very least this makes for a very intriguing topic. It fits within the contest rules, there's nothing that I can do to argue, so I begrudgingly accept this as the first winner. (Send me a private message if you're interested in two licenses for Espionage).

HOWEVER! That doesn't mean that I can't offer the same prize for a second solution!! :-D

I have a problem with the above solution: it is too slow. I stipulate that it's still possible to find a second solution within the confines of the contest rules that is at least 4 times faster (I've done a quick benchmark, on my computer it's actually over 5x after looping 10000 times) AND shorter than the solution that was just presented.

Posted: Sun Apr 05, 2009 3:48 am
by itistoday
Interesting note, of all the solutions that I have tested (which includes all of those presented here, and the yet-to-be discovered solution), the fastest one is the one using gensym:

Code: Select all

(define (gensym:gensym)
	(sym (string "gensym-" (inc gensym:counter))))

(define-macro (my-or)
   (eval (let ((temp (gensym)))
              (expand
             
                '(let ((temp (eval (args 0))))
                        (if temp          ; Naive
                            temp          ; version
                            (eval (args 1))))
               

               'temp))))
The yet-to-be discovered solution is about as fast as that one, but in my benchmarks it trails it just by a little bit (a couple milliseconds when executed 10000 times, but consistently).

The slowest solution (by far) was the first solution presented in this thread by Kazimir, with the strategy of using his protect function to generate a new function. In my benchmarks it is at least 15x slower than the fastest solution.

Posted: Sun Apr 05, 2009 3:48 am
by Kazimir Majorinc
OK, we'll unite these two of my prices for one, since the second one is just the version of the first one + that little gensym trick. When I'll buy Mac, I'll contact you.

But obviously you have something different (and faster) I cannot see now. I have to take some rest now, it is early morning in Croatia, it was fun session. Thanks for nice words and contribution to genlet library.

Posted: Sun Apr 05, 2009 3:56 am
by itistoday
Good-night, and thank you for your creative solutions! :-)

Posted: Sun Apr 05, 2009 9:06 am
by Lutz
The proper solution in newLISP (not following the contest rules) is to avoid variable capture in the first place by enclosing the 'my-or' in a namespace:

Code: Select all

(define-macro (my-or:my-or) 
	(let (my-or:temp (eval (args 0))) 
		(if my-or:temp my-or:temp (eval (args 1)))))

(my-or 1 nil) => 1
(my-or nil 1) => 1
it is as fast as the naive solution which is prone to variable capture.

Many newLISP versions ago there was this utility function in the manual to define context-enclosed functions:

Code: Select all

(define (def-static s body) 
    (def-new 'body (sym s s)))
the function takes a new function-name symbol in s and the body of the function and creates a new functions enclosed in a namespace. Here 'def-static' is used to define 'my-or:my-or' as above transforming the old naive definition into a new statically scoped one:

Code: Select all

(def-static 'my-or 
    (fn-macro (x y) 
        (let (temp (eval x)) (if temp temp (eval y)))))

(my-or 1 nil) => 1
(my-or nil 1) => 1
we also can omit the (args ...) trick now and name the variables for better readability.

A general comment:

Instead of trying to emulate Scheme or traditional LISPs we should emphasize typical newLISP solutions. Trying to do Scheme in newLISP only leads to in-efficient and often ugly code and newLISP is perceived as a second-class Lisp becuase of that.

Just as Scheme is designed around lexical scope and closures, newLISP is designed around dynamic scoping and namespaces. Both approaches are designed to avoid symbol-name clashes and maintain state. I believe that the newLISP approach is in the end easier to understand and more open to explore future programming paradigms.

Posted: Sun Apr 05, 2009 6:45 pm
by itistoday
Lutz wrote:The proper solution in newLISP (not following the contest rules) is to avoid variable capture in the first place by enclosing the 'my-or' in a namespace:
As I mentioned here, I think there is a strong case to be made for why that is not the proper solution.

Perhaps I'm a lunatic, but I think that all macros should be written in such a way so that they're safe and immune from variable capture. As such, you would quickly run into name conflicts and run out of namespaces if you were to encapsulate each macro in its own namespace. Name conflicts are an issue the C community knows all too well and has therefore adopted various conventions to avoid it.

This wouldn't be such a problem if newLISP supported nested contexts, but since it doesn't great care and caution must be taken when deciding upon the name of a context.

If you're going to recommend that as the "default" method of writing macros, then at the very least there should be a disclaimer somewhere in there about this, and a recommendation to use C-style naming conventions to attempt to avoid name conflicts.

I.e. If my company/organization name was "Pink Flowers" then I would write this as:

Code: Select all

(define-macro (PFmy-or:PFmy-or PFmy-or:x PFmy-or:y) 
	(let (PFmy-or:temp (eval PFmy-or:x)) 
		(if PFmy-or:temp PFmy-or:temp (eval PFmy-or:y))))
IMO, if such naming conventions are ignored, then the proper solution is the one quoted in a post above using gensym.

Edit: I've changed my opinion on this, see the two posts below for why.

Posted: Sun Apr 05, 2009 8:45 pm
by Lutz
As such, you would quickly run into name conflicts and run out of namespaces if you were to encapsulate each macro in its own namespace
There is no such thing as "running out of namespaces". A namespace overhead consists of nothing more than one additional symbol, the context symbol. You can have as much namespaces has you can have symbols.
name conflicts are an issue the C community knows all too well and has therefore adopted various conventions to avoid it.
Yes, any non-trivial programming projects should employ naming conventions of functions and variables in any programming language.

You wouldn't write a bigger macro like this:

Code: Select all

(define-macro (PFmy-or:PFmy-or PFmy-or:x PFmy-or:y) 
   (let (PFmy-or:temp (eval PFmy-or:x)) 
      (if PFmy-or:temp PFmy-or:temp (eval PFmy-or:y))))
But it is handy for smaller functions, to write it this way. For bigger functions you would use this:

Code: Select all

(context 'PFmy-or)

(define-macro (PFmy-or x y) 
   (let (temp (eval x)) 
      (if temp temp (eval y))))

(context MAIN)
Or use a function like 'def-static', as shown earlier. 'x' and 'y' are now part of 'PFmy-or' space. Of course naming conventions for functions and macros are still a good idea. But that has nothing to do with the fact, that a default functor is used to write the macro.

When writing many macros in a row, you could do this:

Code: Select all

(context 'MAIN:Foo)

(define (Foo ...)
...
)

(context 'MAIN:Bar)

(defne (Bar ...)
...
)

; etc ;
This way saving one statement and closing the previous and opening the next namespace at the same time.

Posted: Sun Apr 05, 2009 9:11 pm
by itistoday
Lutz wrote:There is no such thing as "running out of namespaces". A namespace overhead consists of nothing more than one additional symbol, the context symbol. You can have as much namespaces has you can have symbols.
Sorry, that was a bad choice of words, I simply meant that it would be increasingly difficult to pick a name for a context without running into conflict with an existing one.
You wouldn't write a bigger macro like this:

Code: Select all

(define-macro (PFmy-or:PFmy-or PFmy-or:x PFmy-or:y) 
   (let (PFmy-or:temp (eval PFmy-or:x)) 
      (if PFmy-or:temp PFmy-or:temp (eval PFmy-or:y))))
But it is handy for smaller functions, to write it this way. For bigger functions you would use this:

Code: Select all

(context 'PFmy-or)

(define-macro (PFmy-or x y) 
   (let (temp (eval x)) 
      (if temp temp (eval y))))

(context MAIN)
Or use a function like 'def-static', as shown earlier. 'x' and 'y' are now part of 'PFmy-or' space. Of course naming conventions for functions and macros are still a good idea. But that has nothing to do with the fact, that a default functor is used to write the macro.
OK, I have to rescind my earlier statement:
itistoday wrote:IMO, if such naming conventions are ignored, then the proper solution is the one quoted in a post above using gensym.
I now agree with you, that the proper solution to this problem is to use a default function, while making sure to use naming conventions in a large project. The reason is that I realized that even when not using the default function and going the gensym route, you are still affecting the global namespace, just as you would be if you were to place the macro in its own context. Edit: The gensym approach might still be something to keep in mind if your macro lives in some large context and you don't want it polluting the global namespace, but even then, you'd be better off simply using good naming conventions as the context approach is much faster.

Question: in light of this, I think it would be very handy to have the def-static function brought back into the standard library, except could it be changed so that it can be used in the same way that one would use define-macro? Perhaps name it 'define-smacro' for "safe macro":

Code: Select all

(define-smacro (my-or x y)
	(let (temp (eval x))
		(if temp temp (eval y))))
I mean, look at that! That would have the Scheme people jealous! :-)

There's also the more radical option of making *all* macros safe, by making the define-macro behavior create a new context by default, although that might be a bad idea since newLISP doesn't support nested contexts...

Posted: Sun Apr 05, 2009 11:09 pm
by newdep
.aaahhh...I think i just missed this posting... Nice topic!

Posted: Mon Apr 06, 2009 11:32 am
by DrDave
Does this work for you?

Code: Select all

(define-macro (my-or)
   (let (
         temp  (eval (args 0))
         temp1 (eval (args 1))
        )
     (if temp 
         temp
         temp1
     )

    )
)

results:

Code: Select all

(my-or temp nil) = 45 
(my-or nil temp) = 45 
----------- 
first arg 
should be 1: 1 
----------- 
first arg 
second arg 
should be 2: 2

Posted: Mon Apr 06, 2009 12:16 pm
by m i c h a e l
Here's a minimal version:

Code: Select all

(define-macro (my-or) 
   (or (eval (args 0)) (eval (args 1)))
)
m i c h a e l

Posted: Mon Apr 06, 2009 3:01 pm
by itistoday
DrDave wrote:Does this work for you?

results:
How did you get those results? With that code the second argument is always evaluated, therefore producing this result:

Code: Select all

(my-or temp nil) = 45
(my-or nil temp) = 45
-----------
first arg
second arg
should be 1: 1
-----------
first arg
second arg
should be 2: 2

Posted: Mon Apr 06, 2009 3:05 pm
by itistoday
m i c h a e l wrote:Here's a minimal version:

Code: Select all

(define-macro (my-or) 
   (or (eval (args 0)) (eval (args 1)))
)
That's cheating. :-p

I guess I didn't state it, but part of the idea/challenge is that you're supposed to define your own 'or', if you could use the built-in 'or' then it wouldn't really be a challenge..

Posted: Mon Apr 06, 2009 5:33 pm
by DrDave
itistoday wrote: How did you get those results? With that code the second argument is always evaluated, therefore producing this result:

Code: Select all

(my-or temp nil) = 45
(my-or nil temp) = 45
-----------
first arg
second arg
should be 1: 1
-----------
first arg
second arg
should be 2: 2
Ah, my bad. You're right. I didn't look carefully at the results.

Posted: Mon Apr 06, 2009 6:17 pm
by xytroxon
itistoday wrote:
m i c h a e l wrote:Here's a minimal version:

Code: Select all

(define-macro (my-or) 
   (or (eval (args 0)) (eval (args 1)))
)
That's cheating. :-p

I guess I didn't state it, but part of the idea/challenge is that you're supposed to define your own 'or', if you could use the built-in 'or' then it wouldn't really be a challenge..
Inheritance is a powerful (and in 2009), a fundamental programming concept... For OOP, or for LISP, which at it's core "invented" inheritance by it's "functional" programming language nature... Every new function "inherits" code from existing functions... "or" is the base function... "my-or" is the derived functionality that reuses the "or" code and extends it's functionality... Using the "if" function is no more, or no less a valid idiom than using the "or" function...

Michael's version is clear, concise, and I can understand at a glance what it is doing... It is "pure"... It is "beautiful"... The only potential fault with such "beauty" is that it must also work... In real world programming, functionality must always trump beautiful form... When both functional form and beauty come together, it is rare, and profound...

"OR" is this to be an obfuscated newLISP contest? ;-)

-- xytroxon

Posted: Mon Apr 06, 2009 6:30 pm
by itistoday
Not an obfuscated contest, no, just a challenge to see if you can figure out a way to do it. While working on this problem myself I came up with what I thought was a clever little solution and I thought it would make for a fun topic/challenge. :-)

Posted: Mon Apr 06, 2009 6:31 pm
by newdep
(define-macro (my-or)
(not (and (eval (args 0)) (eval (args 1))))
)

but probably thats a sidekick ;-)

Posted: Mon Apr 06, 2009 6:33 pm
by itistoday
newdep wrote:but probably thats a sidekick ;-)
Yeah... but in addition that doesn't produce the correct results:

Code: Select all

(my-or temp nil) = true
(my-or nil temp) = true
-----------
first arg
second arg
should be 1: nil
-----------
first arg
should be 2: true

Posted: Mon Apr 06, 2009 6:35 pm
by newdep
yeah Im still looking into it because I want small code result ;-)
So i like micheal solution but im aming for a more scheme lookalike..