newLISP Challenge: The seemingly simple 'my-or'

[itistoday]

A TEST OF YOUR NEWLISP SKILLZ!



Something that spawned from http://www.alh.net/newlisp/phpbb/viewtopic.php?p=15199#15199">this discussion was an interesting function called 'my-or' that I found in http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-10.html#node_chap_8">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 Expand

(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 Expand

(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 Expand

(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 http://www.taoeffect.com/espionage">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]



Update]



Challenge is over! Congrats to Kazimir and newdep!

[Kazimir Majorinc]

Code Select Expand

(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 Expand

(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)"

[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. :-)

[Kazimir Majorinc]

Code Select Expand

(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)))))

[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 Expand

(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. :-)

[Kazimir Majorinc]

Code Select Expand

(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)))    ))))

[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.

[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 Expand

(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.

[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.

[itistoday]

Good-night, and thank you for your creative solutions! :-)

[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 Expand

(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 Expand

(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 Expand

(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.

[itistoday]

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 http://www.alh.net/newlisp/phpbb/viewtopic.php?p=15199#15199">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 Expand

(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 http://www.alh.net/newlisp/phpbb/viewtopic.php?p=15210#15210">post above using gensym.



Edit]

[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 Expand

(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 Expand

(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 Expand

(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.

[itistoday]

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 Expand

(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 Expand

(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:

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 Expand

(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...

[newdep]

.aaahhh...I think i just missed this posting... Nice topic!