Common Lisp Macro to T-Sql Experiment

So just another jump into the unknown, I wondered great wonders about creating a macro in Common Lisp that would just print out what I type between the () into T-Sql. Essentially, I want to type this:

(select user.name age)

And get:

"SELECT user.name, age"

Now there are probably a billion (or slightly less) examples of using keywords like:

(select 'user.name...

or:

(select :user name)

Or whatever.  Not good enough for me. I am more demanding.

So the first stab was something simple;  Just take an arbitrarily (I actually spelled that correctly the first time) long list of names, and create a string from it. And here it was:

(defmacro select (&rest args)
  `(mapcar #'write-to-string (list ,@args)))

Basically, take the parameter “args”, strip the () surrounding it, create a new list, and create a string from every member. A quick macroexpand show the outcome:

(macroexpand-1 '(select 'test 'me)) 
  -> (MAPCAR #'WRITE-TO-STRING (LIST 'TEST 'ME)) 
    -> ("TEST" "ME")

As shown, that is just a list of “test” and “me”. Doesn’t make the cut, mostly because I had to use “APOSTROPHEtest” instead of just “test”. Oh and there’s no string. Time to take care of that:

(defmacro select (&rest args)
  `(concatenate 'string  ,@(mapcar #'write-to-string args)))

So now it should take the list of strings ‘(“TEST” “ME”)’, and make it a nice string. DOES IT?!?!?

(macroexpand-1 '(select 'test 'me))
  -> (CONCATENATE 'STRING "'TEST" "'ME")
    -> OOPS

Go figure, it left the APOSTROPHE on the words. Actually, this is good sign. It means I don need to prefix the names with an APOSTROPHE  anymore. Next attempt:

(macroexpand-1 '(select test me))
  -> (CONCATENATE 'STRING "TEST" "ME")
    -> "TESTME"

Now it’s getting there. Only thing is: There needs to be a separation added. Duh, right? Might as well throw in the “SELECT” part too.

(defmacro select (&rest args)
  `(concatenate 'string "SELECT "
     ,@(mapcar #'(lambda (z) (concatenate 'string (write-to-string z) ", ")) args)))

Big change here was adding the “, ” to the converted keywords, then take the newly created partial string and make one long string.

(macroexpand-1 '(select user.name age))
  -> (CONCATENATE 'STRING "SELECT " "USER.NAME, " "AGE, ")
    -> "SELECT USER.NAME, AGE, "

And there it is. Can’t get much better than that.

Common Lisp and Reader Macros… You Better Sit Down For This

Fair warning: I only learned about reader macros today, so my terminology may suck. Well, most likely it would still even if I had a couple weeks. So it will suck more. Say, 20% more suck.

In case you didn’t get a chance to read my primer on macros (Let’s be honest, you didn’t. It’s ok, I’ll be fine.), this next macro may not look familiar. This is the post of which I type. A quick recap is that the macro would take this:

  (?> (+ 1% 2% 3%) '(4) '(5) '(6))

And create this code:

  (MAPCAR #'(LAMBDA (1% 2% 3%) (+ 1% 2% 3%)) '(4) '(5) '(6))

Essentially it took the original expression, and created a lambda with dynamically created parameters. (The 1% 2% 3% part) The macro “keyword” if you will is the “?>
Here’s the macro minus the helper methods. (The whole thing is the last section of the same post from above.)

  (defmacro ?> (conversion &rest args)
   `(mapcar #'(lambda (,@(create-placeholders args)) (,@conversion)) ,@args))

Now that’s pretty cool and all, but it still has to follow the general rule of Common Lisp: Every statement is encased in parenthesis. After all, the macro starts with “(?>”. What if there was a way to take that and remove any need for outer parenthesis? Turns out there is, and the term is “reader macros”. What’s the big difference between the two types? Glad you asked. Would have been a long, uncomfortable pause if you hadn’t.

Unlike normal macros that are expanded AFTER post read. That is, taking what is on the text file (.lisp file), and converting it to be compiled. So basically, read is pre-compile time. Why does this matter? Because you can instruct the reader on how to “digest” stuff from the .lisp file, and then prepare it for compile time. So like a normal macro that tells the compiler how to expand itself to compile ready lisp code, a reader macro tells the reader how to transform the text into useful pre-compile code. And yes, a reader macro can create a normal macro. In fact, that’s what this example will show.

Ok, so back to the normal macro above; It still has the normal {} encasing. What if I wanted to encase it with something else? Say something like #| |.

 #| (+ 1% 2% 3%) '(4) '(5) '(6) | 

Normally this would cause all sorts of problems, a linguistic middle finger if you will. Don’t worry, lisp won’t get away with that.

(set-macro-character #\| (get-macro-character #\)))
(set-dispatch-macro-character #\# #\|
  #'(lambda (stream char1 char2)
      (let ((pair (read-delimited-list #\| stream t)))
        (cons (read-from-string "?>") pair))))

So as far as I understand it, somewhere there is a table of symbols that are reserved by Common Lisp. For instance, the right parenthesis or ). The “set-macro-character” basically allows the addition of new symbols like ]. It is telling the reader that ] is ).

Next part is the actual macro. If you take away the #\ characters from “#\# #\|” you’re left with “#|“. This is what the reader will look for in order to read the code that follows the “#|“. Essentially this has set up the ability for the reader to take in “#| |” without throwing an error. The in between is what the rest of the code handles.

For whatever reason (Again I’m new to this) the “set-dispatch-macro-character” needs a method that takes in three parameters: “stream” “char1” “char2”, the significance for this I have yet to see. However, the “stream” parameter is important to this macro. The stream is the code that is read in after the reader finds “#|“. The needed code is the start of the stream until it hits “|”. In this example that would be:

  (+ 1% 2% 3%) '(4) '(5) '(6)

To match the original macro, there still needs to be the leading “?>”:

  (?> (+ 1% 2% 3%) '(4) '(5) '(6))

And that’s where the “cons” comes in. I simply appended “?>” to the read in code “(+ 1% 2% 3%) ‘(4) ‘(5) ‘(6)” to give me:

  (?> (+ 1% 2% 3%) '(4) '(5) '(6))

Which is exactly the code I needed to call the original non-reader macro. So not only was it possible to completely ignore lisp syntax, it was also possible to nest a normal macro within the reader macro.

 #| (+ 1% 2% 3%) '(4) '(5) '(6) |
    -> (?> (+ 1% 2% 3%) '(4) '(5) '(6))
      -> (MAPCAR #'(LAMBDA (1% 2% 3%) (+ 1% 2% 3%)) '(4) '(5) '(6))
        -> 15

Euler 3 Just Got Lisped Up

“What is the largest prime factor of the number 600851475143?”

One thing I’ve learned so far from the euler stuff is that if seems too hard, I’m doin’ it rong. What I initially did is go from 2, tried to find any prime number that is a factor 60085…3, and keep updating the highest found. This was silly. In reality, I needed to start from 60085…3, find the largest factor of it, and keep going if it’s not a prime number. After all, the highest possible factor can’t be higher than 60095..3/2, prime or not. If that fails, then increase the divisor by one, and check if the other number is a prime.

600851475143 / n = x where n 2 -> ?
600851475143 / 2 = x
600851475143 / 3 = x
600851475143 / 4 = x

This meant I needed two parts, one to roll through all possible values of n until x was a prime.

(defun lowest-prime-divisor (start &optional (current 2))
  (if (and (= 0 (mod start current)) (is-prime-number (/ start current)))
    (/ start current)
    (lowest-prime-divisor start (+ current 1))))

As I wrote before, this is taking the original number (6800??adf…3), and start with dividing it by 2. What ever the remainder is, take it and check if it’s a prime. If so, return that. If not, divide by 3. I have no clue why I named it lowest-prime-number. Probably a case where my limitless intellect is proving that I am not nearly smart enough to understand it.

Here is the brute force prime number check. Essentially start a 2, use mod, and increase the iteration. This is done until either something mod iteration is 0, or the iteration is the same as the number being checked. It has a special kind of ugliness, and inefficiency.

(defun is-prime-number (start &optional (currentDivisor 2))
  (if (= start currentDivisor)
      T
      (if (= 0 (mod start currentDivisor))
          nil
          (is-prime-number start (+ currentDivisor 1)))))

And I don’t have a macro this time. Mostly because I’m on 8 currently, and this is only the third post.

Common Lisp and How It Conquered the Euler Problem 2

So yesterday I took down Euler problem 1. Yeah, I’m just that good. In fact, only something like 250k of the entire world population (7 billion or so) got it right. That’s not even including people like Santa Clause. Elite level, here I am.

I would tell you what the second question asks, but that would mean I read it correctly the first time around. What I read was something like “Add up all even Fibonacci numbers up to the four millionth Fibonacci number.” Cake! Right off the bat I was going to do this tail recursive style, ’cause that’s the way an elite programmer like me does it. Now, I know I’d seen the cannon version of how to get the Nth Fibonacci number, but I chose to blaze some trails. (And I forgot what the cannon version was) The idea was instead of doing that whole (n – 1) and (n – 2) nonsense.

So to start there is 0 and 1. Then 1 and 1. Then 1 and 2. Then 2 and 3. Every iteration has a sort of shift where the right parameter becomes the left, and the new right was the old left + right. Sounds like a really easy recursion problem. Only thing missing is an iteration used to find the Nth Fibonacci. That will just be reduced by one every iteration until it hits 0.  Once that happens, the last number is returned.

  (defun fib (left right iteration) 
    (if (= 0 iteration) 
      left 
      (fib right (+ right left) (- iteration 1))))

And it would be called by:

  (fib 1 0 37)

Which, by the way, is 24157817.

So now I have a way to get the Nth, it’s time to add up all evens up to the 4 millionth Fibonacci number. Oh yeah.

 ;;This is needed to add the current Fibonacci number to the sum if it's even
  (defun adjust-sum(sum currentNumber)
    (if (evenp currentNumber) (+ sum currentNumber) sum))

 ;;And this is an update that keeps adding up the even Fibonacci numbers and stuff.
 (defun fibo (left right iteration sum)
   (if (= 0  iteration)
     sum
     (fibo right (+ right left)  (- iteration 1) (adjust-sum sum left))))

Now the site gave me the first 10 numbers: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. So adding up the even numbers in that list gets… eh… Oh! 44. Well time to see if the above bit of lisp works.

(fibo 0 1 10 0) ;;44

Yay. Well that’s easy. Next 4 million.

(fibo 0 1 10 4000000)





15 minutes later


Now the fun part about that solution is that I will never get a stack overflow. Bad part is that I have no idea how long it would take to add up 0 -> 4 millionth Fibonacci number. So at that point I was thinking I would have to somehow create a tree structure of parallel operations. Start with 4000000 / 2 and find the total in those two. To do that, I would halve those, and then halve again… ect, and sum up everything while traveling back up the tree. Or is it down? Whatever. I couldn’t believe how *(@#ing hard this second problem was. That was when I re-read the problem. Turns out I was supposed to add up every even up to 4 million. So the Fibonacci number closest to 4 million. Not the 4 millionth Fibonacci number. Then it seemed to be back to what I would expect for the second problem.

  (defun fibos (left right sum)
    (let ((adjustment (adjust-sum sum left)))
      (if (< right 4000000)
        (fibos right (+ right left) adjustment)
        adjustment)))

Basically every number found that is even, add it to the sum. That is until the right number is greater than 4 million. (Which would make the left number too high on the next iteration) At that point, add the left (If even), and return the sum. And guess what? It worked.

Now this wouldn’t be a lisp post if I didn’t add in some macro for over kill. After I failed to add up all even numbers up to the 4 millionth Fibonacci, I thought that maybe if I put them all in a list, and then added them up: magic would happen. Magic did happen, I killed the heap. I mean if adding two really big numbers was killing lisp, having a bunch of lists full of large numbers being added together should be fine, right? Make perfect sense. HOWEVER, one interesting thing did come from that: A macro. Here’s the original function for the array adding, pre massive tree idea. This just puts all into a list. I didn’t even get to the adding part.

  (defun fibl (left right iteration numbers)
    (if (= 0  iteration)
      numbers
      (fibl right (+ right left)  (- iteration 1) (if (evenp left) (append numbers (list left)) numbers))))

Well I figured instead of just having a method call fibl to add all the numbers, just make a macro that would call fibl to get the list, then run an eval to add them all together. Why settle for simple, when a macro can make it way more complex. Although in my defense, when using macroexpand-1, I get to see the whole list of numbers before they are added.

  (defmacro fibl-bibl (a b c)
    `(eval (+ ,@(fibl a b c '()))))

With expansion:

  (macroexpand-1 '(fibl-bibl 1 2 100))

I got:

(EVAL
 (+ 2 8 34 144 610 2584 10946 46368 196418 832040 3524578 14930352 63245986
    267914296 1134903170 4807526976 20365011074 86267571272 365435296162
    1548008755920 6557470319842 27777890035288 117669030460994 498454011879264
    2111485077978050 8944394323791464 37889062373143906 160500643816367088
    679891637638612258 2880067194370816120 12200160415121876738
    51680708854858323072 218922995834555169026))

A list of Fibblenibble numbers. That was a lot for just one problem. Oh and for fun, here is the original golden function when adding all evens up to the 100000th number.

210134635149757719315950255064695756588695785131611725165235804359916786572863811331696923863350683048126683085142916459332058114941110766686678707363430726110258898018010828814604839776532825126899915724751316525031035954444949232180979996323811805415925251187493235192974551234331062086534136805786177582386212877375117620623437303742552667696171935177393500985079313725745197179088900620541323223091163646241337468114147700211796183133392908337016188476611677040521713333083986943297965232600862288054724778303558352715084544785730244200683974569728324692232314945603947032229789125399896443936969649280509005067194130014191019906960046358175606148496241991973176681118479994029681227415747795999136572033230343019483738392331535711939926003061047418009792141434744705747844399720376659431081235302156392379430858982251915271749438857727345183251386080769599191998495894067199070972184404625055740909899201130583052303659016146177688301879324924998727010234689589652398161124306953007370681861516962672162830424285078239244552669896314483208891095985314333206792218890143817628106119467673305141311764463161724418159970207964328041486429941060257374678419608037203240907685335494485955430304182439776700248640864773279209804130107815203595074666252436894851980635269999972922994229316228817842523295140034108168011150940569150560436362656065740205309181537316695861739407779209971100218486739728373214686579514950816073845513802397657286856676531046668500663748143833301204618907223112395593062138681442360586312693005182921398053824358166567360026424432237244893361109213993070525649845617875919021011326149817574499600796480668479299614246073642029837591242910304168518758793534817372587124224044754480947765539973773666516619403727561494805255585195903740965473156483826329176162700309900774052207962720926430456721705920419295629157748986005586754127144175997102510354485314565966185296805934985438370260768324842285912332030181915108852664242572126624872731549974878879155226050609755790730339295164790392508584467954066309414696582480695424863249711810312524443221741471814759761642591927546176444474249387569051116004412758001682082295704641159441424272689037737589652445380001275607073531853320125093627397613857071252531071586306675618824599663218410951341233889913902500614833884066908233398699567328935275637267197347202298538859593997703697713802957906539642606370828416414147810799658734529479109231110665556187176418548476384868832963210485071523013131404475587489246037723764622677791224251854058483148068071872834278461455417690222393581989010116042011804685461127070238504845641024580288388683486518326824941746182412364178381937706647179795904877648631685848537286241780452140116126363436113503233969227750339200404403271385824016244124590198080724853578464251549859567798872700339233328199123293182072219835862411700901312198089085324168018585880297699588552274806528231438637456543897771694662159568469764070690619750679540394911382924413162540130926242538137809271974228796966756307877297146883981035775477003257465643278222185432771988583677109052727922684880948307777590208566505337135736871655930805583340006737117885774782210441102763126560381512377013745064883258066541654232929359000450636792943019366164523868429521535469074034946258620181476030719978796857587893526752267013243359357704275788464983521293250604674874972904203574191004579440328676946195685201217530982857554917402649304912755548774644266805777262869652122134839557928817095037660048000300983583156138998227663706230691350142110382572156360795370566704001744520381292459642329429020643458193257739821488816256213262167854518663999704530401445716210010813920156878484439665966358964075682592874240824755027657575343644672852034918243245446316952102752735068725543566246724899970431874885063985801405302823267128880668375592237892911980938256404473624342563948754159675405491888599705183505124206483194289438402679806151662578956199048579482571884905313726646964715915902481919126863415141459926644007647035716861604316055203082217917719133243245860921910514675871227687275287904537667794101260280122689215877177692659971254050108571563988273142096434551936972388013889468525869265313987202386124454335737401442779149708893730357123453230525472812601106412916497512782130114995296452342079789558396075642943016414842497563577672325443914816380590195336781663311206154684378687331712606758533984749064480897205038658440932747251187171925615932041948405830247876193685033702230130932424171267174008628519670296361919459610294515999453092599210519154108208264305103436934737238114113533578104044878364038805466064185038826829618126068508780524600524532396321751115668117851883641022819256371424253155374856570004090384898320933546043135375879145452469151210230166702462732829179222147648168544388272632793803303122346891630514391171335250309356292095466008088199378325674346357700504254182363476775695790837935514439560228061226354773830823231721171817925342307215071868982885889541475143724812654735837013547431202790870732505233531398825890187747794954413346873325089496704707900879389656488821344562140479083399346311640681278838002510254530994419956170461984422108213527538906614386259246674521029974783963230282955512888041250709653893598294048112482622910077840761873334973198377454635795213978371736970235694420172850166988573277784747359753551788762540593326628753294639877707665080404530665383601082885770093671822607628346295993226276841728411776535299081065042752452287473106250279305015609577612263706122258615273003824478437201890581856024447124072122869194061082349696061506541146882810975740599373902964150305958292734863572211538327420362893741030060918112493319686075487376326876983867697925992238478866107122304899040508647431253037732782392528717428733688046182831729132774784725040247331280034150165198489598636448927438644934585011667241905557181221099862417418669690895727041918337056896533627181530365929210694465523664873064732165456703307561043626687310115887431899952005701851752064305634513236819669863690896215787275155359301452323258424483249574247791813760513919904799453367672688587351772118267772287356372396160702030198472586422560132252593869683043910370213989746468578566913116289689458398973054296570754784174314808120093787794706506020368933585621886459424376006095645540516337457704802032437712446376726098103705121264595688347218451606605177546669112269977919387895237275587948254401392746864976823592328331881845950067569933987319425473420264227457037823974302822896032471480891487098097305485181465226545673335811922107441009472479075151488317678985169434996018295266202368656027482782167093131138853719482321158978983728897817066141539245801340677422731168147452795744266894019921848745903566804479001006155549580727806394856431476422910453397609716348844849887606352116821462340936742691737144466549028005167896114433828324010330732622222173088700586063219910281155121562420408416384427387652289708818083295152927629068305962450984958140124822704302666063753142031169908652700969937967560785599365331808920514154488957336620911995116533849705595812479209241064508087094244537228712955164255338447272814693237786944972817747162992695126655916021555696910288300621111158764772032998163892743242649237104158980565714542878020285536410647945320115296595370947305512788680378113862524317461361104377898340233653765440250113911194734180701435331951303967217221734314727819805156190906849061439718539268419425329956751349030666546704748089678154731359992660080659657693255422636089340707029328611600500872957698125089435060190254908205989007442684601204354306128681811653225112598061698749618332036772594552243139973109440779102119329001540055344504861934352772627605541498252958062267170758050417721581345853192205827455124849694038122424540952113490208003720269622508701810492374185547454640205838677373971255884836178808659477383029849240657152245346957236828601255626545670117515828979636355357010237289609065632163399008313810676989365934339225832320452186973067052917093306509725760336403569400860087523267258884178358312322554843735839611544507427486582585771335956735088950482325185692785684530748994744497094422864864143797723195179954757435410302928616925707931383712057489757701207799996919323616506079812268859145047501530863469235679989559672702217770826479903005058658549708092818077513289356168467776629816164319215465270457262582602493827064947268566585714868977533411971593664133914653747763343228160437188427004775818365599277926000143684854386339411112041507140914711404454127284070064271895340157513116501567771785420553078419525971929246516298920300129180663727392570824792779311312612668016083738349081021091366969260329686954844262639357270307133632913108878682752416413368429863460872892282596218097575256714738390692771125065632039823487232487934816134008137046656159997657704350599552440619655586356167648218951021071029187849742480638340944718834853662025553240185857312911444283841660542935130176492325518542248626959742553708412118992866903849589661592444892326674773575698043679715574196616158748568450383757530991595937631481647034939033650291447159318070426821677259125681086668323496716293016795080464641752217809778007597626795191933481646571059765954320801474588409330216905430892844682932638129957978823154452874202850621093728059168457837220013599499692971762130344115615325995269667250785121954660127785415291473924408415171614813511358905517066018649343142785307691809627637425698725735864130408323368656111884389482769754811960576769415909056295045296535188276050861691547829255173581117186073547261975619158894909018402883026854086197997246977225550369748004330315700368486340493017657401401781958962964775701777837545067311278282560025002019448234788264341968794716332067981937949097609548861654631809646464344213575300476910860746689637212371057494876111459257852148911385967048755465998441364146400022319073769030669486255997867547995222556113671998576983652014900141037588411791395604752605136783160867609748118109236373232248011307499087595417610165317101079602536029939751761961409793458257927122496473727405330252505881260348617548185100987630099263033869211094826230264992746499766937765664767047006915745373423356974983886028631806018605368717143402885871329102564704048497978176595564136999504898026980399221876155825386735988890478521694182263511982214715473315781195200662586608289146076691505127900696857629942816467387762785961640417229457596102193240304059314877424478667842289912208938780134312689210803665796315755850327333239648241364437120059014779223556434771264888962692080320296371365675443041834819783967762151313094344287600324088024886298056503696129538223922486941503288613783288870731822184804697687684051260150598523227085670596698786755189436919638468778275342260526833915914197270020098776736064622519166800190869283946064085690137489511277163716308622192219175958296397500085684126837927336173451686684923202975662385803826521428261798994900934113002497407521439855373833822964723019320494102332671987095211054238025332581283303947523503685018243913424390547185206189041043360160551399181866804529327190930148746439057774213307320757229157969585047879576209642937323116289964490410633199594898960154825688501502166627998287854790244025814015914565894614176980590304824038029416219941692596393563315421871832759822557040046812392613152131516662651071131811697677932327278397600019337002820692075165825022159844139593104475602024359541715915936040280694024136104975224838491512973122332169367004377967404039156085742436134266885110263040401912806482685606546407143416336601227367095920477163288537592301398535052907715237130177064760726499531799400005658598752165833477119918705900029310637497082895816444819618200059170161703470214369422592382641320506101680281216156081778448799318487482379825143559429289217755084375231231826966227624507701607028493277365212297731816558232776081859195320720765487935640845306071293298175978648896121109699931766693640815838766469144414269416881611661901832254474993736903002870444918037696406186096461094396767891407003453281738910144375394090662039131219749613014416244957286368701539109549586816734329366236746259041128698402728540623058249769198276372684574367047631508878368246825155252000604186666175384857635626157366171685799119057749145104626216349054268607435891936118142348404291584681919224938269484894447299275783313866238268605651170354567618500066640828464663845039073553932154895328922389658948027157160251222979894704360571691297862952533805704188878883347493951724921180841678272882101995530922680946787505085500886281017788478168947687933289789265967458335625338880010055835991224103398106910681873999803919447373848842718558974101069467493059087041449542369885578310978786508338476580819501430821887216699397523296232481211068079127848989527274911018295957930245601035781781552015776949331402066548318836070545702259101601202858355941021723239696437490190967646907252717163788218362609765047387412812296570896130256850884470118212380074491599062494090782968188381275032884690293738157030772407788960626763826311786521684459634262702726313120595550807817889783348003295426613850135163759356093858562640172806341511755083377256237743856688685833977571021335173367552139558669231461890051388052084168584309212686328101875686642176681678258161007255939143491156297571055310068227096515002086176644475958915947792826544980920701818638312130673149091618335925811380646453223742132133536011417584230713296025838111560391541436824783737657386591404783962547872759160432036001703664023848862521453258338793133106897041110831983625006829845247141544780274547562798449396105088732940897438717261579517926301609165483354955629169674272424362392449499327755308169464334499835011272786260059623448169962267096528431414363307727748879558583861743513655499714227653314531461547230325298066242977520913896933633425978231755203930891989970693601676641392159782285450394650447351396177405259220091086399878803399037284230150075406946172625105252246743707323586128249768358241061843301856995209716718881119943331925960878386314159192691633628371990365999473324033224660166283362406508472119313013046929763109273691491482783208361952804867618709155359763254784189783537132337034192486723758484296789460982120806248955719901979533349518748800253928816551805010361299912777533130155627166184669776817910914491556108545726579739015553397637872032024840343939020724989466155622700211781395397524802676616039939897330181240843168074214891914751916504821544411228786746871441634365565516782266448300241467948069931858061626078054431628234960332693691868914691195100883613120189661632186182481828827508722120099555633056092701975580830614548967717547124834107408844338075996676965118798713414760398527484510079855409467866187873865171641234435736694892493290285643393962280230933866378605205069640229730086747322559948835347701346316298854270595950784552299777610367564656909358070274954245477742270971746595867221526118823469613170169632325502587230182228537723192376736698335277895419921587983445396504232871929928095633156235885197769500331225291266518088953227966713707787164877369121792584377914564446736202678535672272911148596686537910294857223644454489067037707405536559306146842998665525356136573125169693694886923967734414247683916610832803230551830328329656615597750684742556921964560578078724927390800180947770481117230846398997474232831807416534958691477507232803171451867978795773477926362693036590124982640838421272171294486953694217648730529551119670790362378479165040057727884581718811537409504375754180213357329518840339658857659225472227753910940218573950862702436879531170719059054588899794722642555547715622550383094211836998109622803898475556138968220399520755975722033077348250428810898854659545479156649389371726108262751722270235138158485718438123481002162926100167821842434644145808964390957121673782737814361306217583217184598124487848407570736394438276748884900324043557738088347297955596146371472719244124866695710978580801114611245318214829898604977359790001251837337744732514003227801568532210870981711391593902347140202374989962533922017246308539050932634459280027964473921781011525328104539916639202720496687716273313449817119092654390857956906620484412000245041169243761472435023051769094170910850758938973425167314947084154044967895410170129849078550957606216129957114899698050874439894391514059609561936396117681164751704852351319228847525908033832852224331049094563435794419534196340813328302275203470566275886315079650273405931265702058827312707374247710482760916463127541794836090581772091569435534252008530734238443706779462426747561809295073772989948906690839206749462851068679596295946925255856047917667723409795120929223023568942635473417139817402379357828670784544822226269789762591879865710801484081920604407651804998349809431989752090348608514876630638518621108872119987893037612213788399531244956067024823744464295926421141662355934743056022382942013556145563955739612625216357651684218328907508641093930276516014993979403960868963166273417646322104257657318991066104656039851755604731303550365138945603628337154214247460120272519587532156053928853272059360997202235662983082664787151377470547835077166304969488757406500477091420132564946761388009999150205307085916054009789475189522966304063839406949736916211375628242467064326553552643434482432201764730991631960975879963107928392665409042731125871602886202088963271887832908611559265610937788384690085152310913834573388112507237937730757225715912796153347153130186632328418177766308016585771876766217468711212548383498610478459146019961088987462203396327400295530783739475027149900881772201888789353158601700677782184152573400851186942994078175811891797233717783138006757483715072021020758596443618732393369139098591351799194301830809367863135024667117464305862025311413756063774077713211423576086774857290123690738822518048520949175918815981438611077457489344566987152913956325533160483220764219027004363784496316622361504723876457646422206742143391453606184716462121044180218197530275337938606215705136430264193780692405120326312862385649988784732175002811670077610443264135934777412150018828223954244695050026842052876118164018541944874833774670555994814420671882408288137775812469290989993809529670529829438647687529606774014120319239986257497301032425187103725121654968658239135595585158593925124607814088125454604787206451352483254459291222047592454341812243065137310481737689661315940835763055390630366405531005767248882907865249389338691377250865829483136636108551155102223445510020797415176337695410000496618501795801013486367948364379840004621567554498797988586983536885277281766989388141535482632178393529591983320058577012810211414053003397205458982697084268250263636216226849867255775808792107079985095487774153671231747128545554886268144818502591552230433514295245774489272593082024298356091609395630161222343283728600145481504536639820969054368415028850424427493816321210061288780567589605603485304929240318765007165160314895042800565872673010844927496776724062145035309838535179167338585946480482502304095322690687232463519446532509780903023128865047531103223461741746558159843591973034411569970280749644844477684427221300798945879744261065241666018944132807794398191204384532714659652333888454053602445432009656690476219493586861862650276087376220797396105688332640294421919802707378374349366858367758305227152144956599671541049582507982382810422816218154089085630110850817388778205572090179609654423564462789769682143891222682702408297516161189408903014295279135004336934244187516885749045858222234653015419511298118997313635664488446496836226827661674123289710636701353528269425596810788132814943234221768541178592404212356919876288915506439277672285401338295086910304093675952549924981548295539671618340692698510141069747470306724497622695441545177289389783198167673153308821130110105288781096189097874731485821840767460542853635315821366422678874925699731857970947686041338357356660254628504966783647630558181400040291220487730085425878820572203969786010762422205821077797891437437271211300592243295335783205540143414525910530643020222737525571946127221957193409744066896412724685850198276695031732241655051863572337617886213017558284975788698382145678631876793675083523530665626372542375260667989689193097509441096459016277376089258829001608871316651176241624092467422390421989410935677121376456674284503881285948347811403148308417350334010647129893085265060932398947369906762515000254008951352275939889675264734960540139416482458019250609247002478434809985351376227426552083399686034233737113135721952938073954444792091208018687445435005640893031581207597214528639333548781765175930179702379384879976002408492565223093051749059256

Project Euler: Question One… And A Pointless Macro

So for the something of it I am going to see how far I can get in the Euler Project Problems (Not sure if I should have capitalized “problems”). Basically finding solutions to questions no one has ever asked. If nothing else, this is a way to further my Lisp knowledge… so yes, this is in Lisp. Hide the children.

First problem is simply to add up all the numbers that are multiples of 3 and 5. It’s like a more boring version of FizzBuzz. Apparently that is possible.

So it’s not exactly a difficult problem. Essentially I just went with tail recursion. Don’t know what that is? Well it’s magic. This is typical recursion:

 def someMethod(current, end)
    if current == end
      return end
    else
      return current + someMethod(current+1, end)

Basically the method calls will look like this:

(0 + (1 + (2 + (3 + (4..... end)...)

Because the preceding method depends on the current’s answer, that method call has to sit in memory. If end = 10000000… Stack overflow. Oh yeah.

Now some languages have something called “tail call optimization” which basically means all useful information is passed into the next method. IE the preceding method isn’t waiting for a return, because it supplied the next method with everything.

def someMethod(current, end, final)
  if current == end
    return final
  else
    return someMethod(current+1, end, final + current)

The big difference here is that every iteration sends all information forward… as in there is no return “x + someMethod(…)” call that leaves the previous iteration on the hook for the current function’s return. Yay. Why does that matter? ‘cuz. Fine. Some languages are smart enough to forget about the previous call, because it no longer has a use. Kind of like garbage collection.

So to attack the original problem at hand, I used a simple tail recursion strategy. Every iteration with push the next number to check, and the updated total to the next.

def euler-one(currentNumber, total)
  if currentNumber == 1000
    //At the end, so just return the final tally
    return total
  else
    if(currentNumber % 3 == 0 || currentNumber % 5 == 0) 
       //The currentNumber is divisible by 3 or 5 // so add it to the total, and increase the currentNumber
       return euler-one(currentNumber + 1, total + currentNumber)
    else
       //The currentNumber is not divisible by 3 or 5 // so just increase the currentNumber, and leave the total alone
       return euler-one(currentNumber + 1, total)

Or in a real language:

(defun euler-one (currentNumber total)
  (if (= currentNumber 1000)
    total
    (euler-one (+ currentNumber 1)
      (if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))
        (+ total currentNumber)
        total))))

Of course this wouldn’t be a post by me if I didn’t over complicate it… MACRO TIME!

You might have read my macros primer thing (Most likely not), so this shouldn’t be to hard to understand… right??

What I was shooting for is a macro that would not only do the above, but would allow for as many numbers to check as the divisorable thing… So instead of:

(euler-one 1 0)

Where “1” is the starting number, and “0” is the starting amount. Instead I want to do this:

(euler-go 3 5 7)

Where “3”, “5”, and “7” are the numbers to check if the current number is divisible by. Pretty sure that made sense… Ok, so!

(defmacro euler-go (&rest args)
  `(progn
     (defun euler-one-a (currentNumber total)
       (if (= currentNumber 1000)
         total
         (euler-one-a (+ currentNumber 1)
            (if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))
              (+ total currentNumber)
              total))))
     (eval (euler-one-a 1 0))))

And here’s what it looks like expanded.

(PROGN
 (DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
   (IF (= CURRENTNUMBER 1000)
     TOTAL
     (EULER-ONE-A (+ CURRENTNUMBER 1)
       (IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))
         (+ TOTAL CURRENTNUMBER)
         TOTAL))))
 (EVAL (EULER-ONE-A 1 0)))

Looks pretty much the same right? ‘Cept for the PROGN thing. PROGN basically just runs everything in order, and returns the result of the last section. So this macro actually creates the euler-one-a method, and then calls it with the “(EVAL (EULER-ONE-A 1 0))”. The important part is the section that creates the divisor check:

(IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))

Which looks an awful lot like:

(if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))

From the original method. HOWEVER, the one thing the macro can do is make as many or checks as I want. Say I want to use 3,5,7,9:

(euler-go 3 5 7 9)

The expansion is:

(PROGN
 (DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
   (IF (= CURRENTNUMBER 1000)
       TOTAL
       (EULER-ONE-A (+ CURRENTNUMBER 1)
        (IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5))
                (= 0 (MOD CURRENTNUMBER 7)) (= 0 (MOD CURRENTNUMBER 9)))
            (+ TOTAL CURRENTNUMBER)
            TOTAL))))
 (EVAL (EULER-ONE-A 1 0)))

And the macro creates all four. How is that possible? One line in the macro:

(if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))

Remember, with macros there’s a step where you can create more code BEFORE the final expansion. What that line says is to take all the values in args (3,5,7,9), and create a “(= 0 (MOD CURRENTNUMBER X)” where X is 3,5,7,9. For people more familiar with c#, pretend you are creating a string.

"(if (or (" + args.Select(x => "(= 0 (mod currentNumber " + x + ")) ".Aggregate(new StringBuilder(), (builder, current) => builder.append(current)).ToString() + ")";

Or something like that. The difference is lisp is creating actual code, not strings. Anyways, that’s it. Yeah. This is awkward.

Common Lisp: Intro to Macros… Because I Only Know Enough for an Intro

SPECIAL NOTE:
I am extremely new to Common Lisp, and macros. I’m willing to bet that anything shown here can be improved.

Been reading through Paul Graham’s On Lisp which is probably not a real “Intro to Lisp”, but well within the grasp of my super interlect. Well at least it was today when I had a breakthrough on macros. I had some introductory stuff on macros when I was perusing through various ancient texts of the language of Clojure. However, I never really looked into to macros much since I was trying to figure out things like how to set up a web server in Clojure. For whatever reason, call it divine intervention or maybe vision inducing exhaustion, it dawned on me to read On Lisp. I figured that if I were to learn macros, I might as well learn them from a person who I can only guess is Lisp: Paul Graham. Turns out, this was a good choice.

Now to start, understanding what a macro is, I have to introduce the word “homoiconic”. It’s a really fancy word that means that a Lisp code is compromised of data structures. In simple terms: Lisp is built on lists. For example:

(+ 1 2 3)

Is that code or a list? Yes. Why is this important? Because any code can be from combining lists together, or by taking a smaller list and expanding it out into code. Unlike other languages that might use a method to evaluate a string representation of code, or some kind of preprocessor directive, you are creating real code that needs nothing special to read/evaluate it. A kind of useless example of this is taking a method, and making it into a macro:

  (defun average (x y)
    (/ (+ x y) 2))

And the macro:

  (defmacro average-macro (&rest args)
    `(/ (+ ,@args) ,(length args)))

Completely obvious, am I right? Nothing seems odd or foreign… HRAHARAHRAHAR

Ok sooo… The main thing about macros is what is supposed to be evaluated at the time the macro is expanded, and what to ignore. Essentially when the macro is expanded, you can have method calls to create code to add to the final expanded code, or code that will remain untouched to become a part of the final product. It’s kind of an odd thing to understand. After all, it means you have to think in more than just one dimension. Think of it like you are concatenating a string. In something like c# you might have a string built like this:

string function ReturnFinalString(name) {
  return CreateFormalGreeting(name) + ".  It is nice to meet you on this fine " + RetrieveTheDayName(DateTime.Now);
}

Ignore that I am using the + string concatenation junk instead of string.format, or StringBuilder. Just wanted something easy to read.

As you can see, there are parts of the string that don’t need any changing, because they are in a final state. (Meaning that’s exactly how they will appear in the final string) However, there are other parts that need the result of an evaluated method. Once those method returns are resolved, you get a single string. A macro isn’t too much different in concept. Instead of creating a list of characters, you are creating lists of code.

Ok so now it’s time to break that macro down. Remember, macros are about what to evaluate, and what to ignore.

  (defmacro average-macro (&rest args)

First two parts should be easy to understand, but the third one is misleading somewhat. What looks like two parameters is really just one: args. The &rest is just syntax for “What ever arguments are left.” For instance, say this macro was more generic where it would take in a function (add, subtract, whatever), and also some numbers. The syntax would be:

  (defmacro do-something (methodToUse &rest args)

The call would be like:

  (do-something add 1 2 3 4)

“add” would be the “methodToUse”, and 1 2 3 4 would be “args”. An important point is that anything passed the named parameters gets lumped into a list. So if I was completely stupid (I’m only partially), and didn’t know what I was supposed to sent into “do-something”, I might do this:

  (do-something add 1 "a" someVariable derp)

The “args” would be (1 “a” someVariable derp). Most likely the macro would throw an error if you tried to use it in the REPL, but the point is just to realize how “&rest args” works.

That was the easy part. Now for the weird part.

`(/ (+ ,@args) ,(length args)))

Looks like a dragged my face across the keyboard, or PERL. Either way, the syntax is pretty goofy looking at first… And even after that. However, the idea behind it isn’t that bad.

Remember how I said something about it all being about what to evaluate, and what to ignore? Well right off the bat, the macro is told to ignore everything. Why? The back quote.

`(... stuff here...)

Without any special characters, the macro will just ignore everything within the parenthesis. So if I did this:

  (defmacro add-this ()
    `(+ 1 2))

Everything in there will not change when the macro is expanded. So basically that’s a really stupid macro. What’s the best thing to do with a useless macro? Make it more complex.

  (defmacro add-this ()
    `(+ ,(+ 1 2) 2)) 

New syntax, the comma. The comma is the opposite of the back quote. It basically says not to ignore what’s there, and to evaluate it. Before the final product, the (+ 1 2) will be evaluated, and that result will end up in the final expansion. Without that comma, the final product would be:

(+ (+ 1 2) 2)

But it really is:

(+ 3 2)

The difference is subtle, but it’s everything. What this means is that in the version with the comma, the (+ 1 2) is being evaluated, and its result (3) is then applied to the macro expansion. Given this example, it’s hard to understand what use that could be, but it will be completely obvious when the last part of the original macro is explained.

`(/ (+ ,@args) ...

So the comma is used to make sure that parts are evaluated for the final expansion, but what is @? @ is an interesting concept that also has large implications, despite the textbook explanation being underwhelming. The , followed by the @ means that it will strip the outermost parenthesis off. Yeah, boring BUT critical. I had explained that &rest args dumps all remaining arguments into a list, right? Well what if you needed to use the values in “args”, but not as a list.

What if I created a simple macro like:

  (defmacro add-that(&rest args)
    `(+ ,args))

And the call would be:

  (add-that 1 2 3)

Now + can’t be used with list, because it expects single values like:

  (+ 1 2 3)

Now in this macro, I did this:

  (defmacro add-that(&rest args)
    `(+ ,args))

Which says to ignore the +, and evaluate “args”. Well we know that the macro call stuff 1 2 3 into one list. So as is, if this is expanded, it will look like this:

  (+ '(1 2 3))

Bad. How can that be fixed? The @ sign.

  (defmacro add-that(&rest args)
    `(+ ,@args))

This will expand to:

  (+ 1 2 3)

As you can see, the ‘(1 2 3) “args” was evaluated to just “1 2 3” before the final product.

With that all in mind, time to go back to the original semi-useless macro:

  (defmacro average-macro (&rest args)
    `(/ (+ ,@args) ,(length args)))

Read out loud it says:

1) ignore the /
2) ignore the (+
3) remove the parenthesis from args
4) ignore the )
5) get the length of args
6) ignore the )

The interesting part to note is step 5. This shows the power of macros, even in a lame example. To make sure the average of x number of er numbers, there has to be a total count of numbers to divide by. When looking at the original function that this macro was based on:

  (defun average (x y)
    (/ (+ x y) 2))

If you want to find the average of 3 numbers, you hosed. BUT since the macro is able to take the length of the args list, and then apply that value to the final expansion; You can easily find the average of however many numbers you want. Remember, the “,(length args)” part is able to resolve that count BEFORE the final expansion is evaluated. This can be shown using macroexpand-1:

  ;; When the macro is expanded
  (macroexpand-1 '(average-macro 1 2 3 4 5))
  ;; Becomes:
  (/ (+ 1 2 3 4 5) 5)

As you can see, the final product has 5 in place of ,(length args). Magic.

  ;; When the macro is expanded
  (macroexpand-1 '(average-macro 1 2 3 4 5))
  ;; Becomes:
  (/ (+ 1 2 3 4 5) 5)

This macro is kind of pointless, because it could be done with a better function than the original one. However, the concepts are what matter.
Now for something more interesting. What if you don’t like the way that functions are declared? I kind of do. I started with Racket (Scheme) before I ended up at Common Lisp. In Racket, there is a uniform definition.

(define (name argument) ...)

But with Common Lisp, the “name” is outside the argument list. Well with macros that can change. And rather easily:

;;(DEFUN X () (+ 1 X))
(defmacro define (head &rest body)
  `(defun ,(car head) ,(cdr head) ,@body))

And it would be called like this:

(define (test-it x y) (+ x y))

Which is syntactically different than the Common Lisp way:

(defun test-it (x y) (+ x y))

How did I do that? There is a little trickery involved, but nothing hackish. Just opinionated. (Or Convention over Configuration as some might call it) Time to break it down.

(defmacro define (head &rest body)

Here’s the start of the trickery. I know that anything that is in “body” is what’s left over after “head” is set. Right off the bat, that could be an issue. After all, “test-it” not only needs the function name, but has two parameters in “x” and “y”. Doesn’t take long to realize that “x” and “y” will somehow have to be accounted for. This means they will end up in “head”, or “body”. In this case, “head”.

`(defun ,(car head) ,(cdr head)....))

And that’s what I mean about opinionated. I expect that “head” is actually a list. A list that starts with the function name, and then has all the parameters. That’s where car and cdr come in. (car means grab the first item in the list, and cdr means grab all BUT the first item in the list) My macro expects that the first item in the “head” list is the function name: “test-it”. It then expects anything else in “head” is a parameter. When the part above is evaluated, it will ignore “defun”, get the first item “test-it”, and the get the list of remaining items. Since cdr returns a list, the function definition doesn’t need anything special done to the parameters.

`(defun ,(car head) ,(cdr head) === (defun test-it (x y )...

After that, the rest is easy.

,@body === (+ x y)

Ok, how about something even more interesting. Say you wanted to completely change the syntax for lambda expressions. This is the normal way:

(mapcar (lambda (x) (+ 1 x))...)

I say, “To hell with that.” I also say, “I want something like this:”

(-> x y z (+ x y z))

Not only did I remove the “lambda” keyword, I removed the parentheses around the parameters. HOW CAN THIS BE?!?! More trickery.

(defmacro -> (&rest arguments)
  (let ((reversed (reverse arguments)))
    (let ((last (car reversed))
          (undone (reverse (cdr reversed))))
    `(lambda ,undone ,last))))

And that’s it. Good night.

Oh, you want an explanation, so be it. The idea behind this is that I will expect the call to have this: n1 n2 n3 … nx (method call). This means that when all items smashed into “arguments”, everything but the last item in the list is a parameter. So no matter how long the “arguments” list is, the most important thing to remember is that ONLY the last item is the body of the function. I think I just wrote the same thing twice, but whatever. Now to break it down.

(defmacro -> (&rest arguments)

Just the typical start to a macro.

(let ((reversed (reverse arguments)))

Here’s something a bit new. As the other macros I showed didn’t need any fields, I didn’t use let. This time the “arguments” field is taken, and then reversed. Why? So that I can do this:

  (let ((last (car reversed))
    (undone (reverse (cdr reversed))))

I took “reversed” from the original let statement, and then retrieved two things from it: The head (Which is actually the last item of the original “arguments” list, but now it the first in the reversed list), and all the rest re-reversed.

arguments == ‘(x y z (+ x y z))
reversed == ‘((+x y z) z y x)
last == ‘(x y z)
undone == (x y z)

The reason why “undone” has to be reversed it that when the “arguments” list was reversed, the “x y z” ended up as “z y x”. If I hadn’t reversed it, the parameters in the method would be reversed. This would be a large issue.

(z y x (+ x y z))  ;;BAD
(x y z (+ x y z))  ;;GOOD

Last part:

  `(lambda ,undone ,last))))

Oh yea, there was an actual part to be expanded in the macro. Why wasn’t ,@ used? Remember that the lambda syntax is:

(lambda (x y z) (+ x y z))

Meaning that the parenthesis that surround “undone” and “last” are OK to keep.

Done yet? Too bad, because here’s one more. The last macro has room to improve from a structure stand point (as I am new to Lisp), but also on a conceptual level. The next big thing would be to not have to bother with declaring the method parameters for the lambda clause. I want to turn something like this:

(mapcar #'(lambda (x y z) (+ x y z))

Into:

(?> (+ z y z) '(1) '(2) '(3))

Where the ‘(1), ‘(2), and ‘(3) are the values that will be passed into “mapcar”. As you can see, I have no declaration of the lambda or its parameters. Crazy, I know. The idea is to have a macro not only create the needed mapcar and lambda syntax, but to generate one parameter declaration for every argument… no matter how many arguments there are. The caveat here is that the generated argument names shouldn’t be something so common as x, y, or z. For this demo I’ll be using a list of numbers that have the “%” character appended to them. So instead of the “x y z” above, it will be “1% 2% 3%”. The final expansion should be:

(mapcar #'(lambda (1% 2% 3%) (+ 1% 2% 3%))

Before I get to the macro, I need a couple of helper methods.

First I need something that will generate a list of numbers as string. The reason why is that later I will concatenate each number string with the “%” character to have a basis for the created parameter names.

;;This creates a ascending list of numbers as string.  
;;  (numbers 5) == ("1" "2" "3" "4" "5")
(defun numbers (count &optional (finalList '()))
  (if (= 0 count)
      finalList
      (numbers (- count 1) (append (list (write-to-string count)) finalList))))

Now I need something to concatenate the number strings with “%”, AND turn them into legal parameter names.

;;This is used to take two concatenated strings, and turn them into potential parameter names
;;  (create-parameter-name "1" "%") == 1%
(defun create-parameter-name (x y)
  (read-from-string (concatenate 'string x y)))

Finally I need a method to use the other two method to create the needed list of parameters:

;;This is used to dynamically create the needed parameters for a lambda expression
;;  (create-placeholders "a" "b" "c") ==  '(1% 2% 3%)
(defun create-placeholders(arguments)
  (let ((argumentCount (length arguments)))
    (mapcar #'create-parameter-name  (numbers argumentCount) (make-list argumentCount :initial-element "%"))))

And here is the macro:

(defmacro ?> (conversion &rest args)
  `(mapcar #'(lambda (,@(create-placeholders args)) (,@conversion)) ,@args))

;;Expanded
(macroexpand-1 '(?> (+ 1% 2% 3%) '(4) '(5) '(6)))
(MAPCAR #'(LAMBDA (1% 2% 3%) (+ 1% 2% 3%)) '(4) '(5) '(6))

1) Ignore (mapcar #'(lambda(
2) Create the parameters based on the length of args
3) Ignore ) (
d) Evaluate the contents of conversion (the passed in method), and remove the surrounding parenthesis
5) Ignore the )
VI) Evaluate args, and remove the surrounding parenthesis
7) ignore )

Yay. Time to stop for now.