I set my cell phone display-up on a flat surface (a table) and I turn on Google Maps. I rotate the phone so that it "points north" (that is, the phone is on its back, the display is facing up, the top edge of the display is facing north, the left and right edges are parallel to rotation of the earth).
On Google Maps there is a little arrow-shaped icon that represents the position and orientation of the phone. Naturally, it points at the top of the map, which is at the top of the display, and therefore the little arrow points north as well.
If I now rotate my phone slightly clockwise, what does the arrow do?
a) move in the same direction as the phone (clockwise)
b) move in the opposite direction as the phone (counter-clockwise)
c) not rotate
and how fast?
a) twice the speed as the phone rotates
b) exactly the same speed as the phone
c) half the speed as the phone rotates
d) it doesn't rotate
Try to solve this in your head, then check with your phone.
Monday, August 20, 2012
Thursday, July 26, 2012
The ability to write nested loops is not a sufficient condition of employment
But it ought to be a necessary one.
Suppose you were helping me write a TicTacToe program. I have this Java code so far:
Can we finish the
Suppose you were helping me write a TicTacToe program. I have this Java code so far:
package com.vaporware.tictactoe;
import com.vaporware.common.logging.FormattingLogger;
class Board {
Piece cells [][];
Board() {
this.cells = new Piece [3][3];
}
boolean xWins () {
return wins(Player.X);
}
boolean oWins () {
return wins(Player.O);
}
boolean wins (Player player) {
// FINISH ME!
return false;
}
}
Assume further that there is a getOwner() method on a Piece that returns a Player.Can we finish the
wins (Player player) method?
Tuesday, June 5, 2012
Curious
(define (fmod numerator denominator)
(- numerator
(* (floor (/ numerator denominator))
denominator)))
(define (test-fmod numerator denominator)
(let ((answer (fmod numerator denominator)))
(if (> answer denominator)
(begin (display "Whoops: ")
(display (list numerator denominator answer))
(newline)))))
1 ]=> (do ((i 0 (+ i 1))) ((>= i 1000)) (test-fmod (random 1.0) (random 1.0)))
; Value: #t
1 ]=> (test-fmod .59 .01)
Whoops: (.59 .01 1.0000000000000009e-2)
;Unspecified return value
Friday, April 27, 2012
Package system horrors
Arcane Sentiment mentioned how the Lisp Machine used to handle package prefixes in this post, and it reminded me of an interesting problem.
When we were building the LMI K-machine we had to cross-compile from the existing Lisp Machine. Naturally, the cross-compiler would read the source code and intern the source code symbols as part of the process. But the K-machine had a different package setup. New packages weren't a particular problem, but the locations of some symbols were. In addition, some things that were implemented as macros in the Lisp Machine were implemented as compiler intrinsic special forms on the K-machine, and vice versa.
The compiler naturally uses symbol identity to determine how to handle a special form. If you want to compile a conditional, for example, the
Well, that's not exactly correct... When the Lisp Machine was built, there was no CL package. There was no Common Lisp. So when the CL package was added, it was necessary to make sure that the symbol named "IF" in the CL package was the same
We wanted to change some of these things on the K-machine, but the cross-compiler was running on the LMI Lambda and when it read the source code it would intern the symbols in the Lambda's packages. Munging the existing Lambda packages was out of the question. The ‘solution’ was to play some nasty tricks with the entire package system. We created two different packages, both named "COMMON-LISP". Some of the symbols were common between them, but others were not. The package inheritance was different, too. The trick was to dynamically switch how package names were resolved to package objects.
So if you have two different “package systems”, how do you refer explicitly to “the symbol
This kind of worked, but it was a horror. Most of the system didn't care, the rest didn't know, but if you accidentally had the wrong package system in place when you read a file, you would definitely trash the entire machine and need to reboot. We had a few helper functions that would try to ensure that the correct package system was selected before doing anything (for instance, when calling the cross-compiler, we'd switch out, and when it returned we'd switch back. Works great until you enter a debug repl...). The big problem was that it was impossible to ‘close’ over the correct context, so you could not in general guarantee seamless operation. (For example, if you referred to the K-machine's CL:READ symbol, you probably wanted to switch to the K-machine package set, but there was no way to do this automatically.)
When we were building the LMI K-machine we had to cross-compile from the existing Lisp Machine. Naturally, the cross-compiler would read the source code and intern the source code symbols as part of the process. But the K-machine had a different package setup. New packages weren't a particular problem, but the locations of some symbols were. In addition, some things that were implemented as macros in the Lisp Machine were implemented as compiler intrinsic special forms on the K-machine, and vice versa.
The compiler naturally uses symbol identity to determine how to handle a special form. If you want to compile a conditional, for example, the
CAR of the form had better be the symbol CL:IF. A symbol named "IF" in a different package won't generally work.Well, that's not exactly correct... When the Lisp Machine was built, there was no CL package. There was no Common Lisp. So when the CL package was added, it was necessary to make sure that the symbol named "IF" in the CL package was the same
EQ symbol as the one the compiler used for conditionals. There are a couple of ways to arrange for this. The symbol could be explicitly interned in the CL package, or it could be visible to the CL package via inheritance.We wanted to change some of these things on the K-machine, but the cross-compiler was running on the LMI Lambda and when it read the source code it would intern the symbols in the Lambda's packages. Munging the existing Lambda packages was out of the question. The ‘solution’ was to play some nasty tricks with the entire package system. We created two different packages, both named "COMMON-LISP". Some of the symbols were common between them, but others were not. The package inheritance was different, too. The trick was to dynamically switch how package names were resolved to package objects.
So if you have two different “package systems”, how do you refer explicitly to “the symbol
IF in the other "COMMON-LISP" package? With a reader hack, of course. We made the triple colon ::: prefix indicate which package system to use to resolve the package name.This kind of worked, but it was a horror. Most of the system didn't care, the rest didn't know, but if you accidentally had the wrong package system in place when you read a file, you would definitely trash the entire machine and need to reboot. We had a few helper functions that would try to ensure that the correct package system was selected before doing anything (for instance, when calling the cross-compiler, we'd switch out, and when it returned we'd switch back. Works great until you enter a debug repl...). The big problem was that it was impossible to ‘close’ over the correct context, so you could not in general guarantee seamless operation. (For example, if you referred to the K-machine's CL:READ symbol, you probably wanted to switch to the K-machine package set, but there was no way to do this automatically.)
Tuesday, April 24, 2012
Another little puzzle
Write a procedure that, given two integers L and R, produces the integer that results from interleaving the binary representation of L and R. For example, suppose L is 23 and R is 13. The binary representation of L is 10111. The binary representation of R is 1101. If we interleave the bits (starting with R and padding with zeros when necessary) we get 1001111011. The answer is therefore 635.
Of course this is easy if you print the numbers and then do string manipulation. Can you do it with arithmetic? Can you extend it to handle negative numbers?
Of course this is easy if you print the numbers and then do string manipulation. Can you do it with arithmetic? Can you extend it to handle negative numbers?
Monday, April 9, 2012
20 minute puzzle
You have a list of names and a list of objects. Each object has 1 unique name. Neither list contains duplicates. Write a procedure that determines if every name in the list corresponds to an object.
(Suppose the list never contains more than four names, would you change your program?)
Thursday, March 15, 2012
Another quick(?) question
I was asked: In your opinion, from a Google perspective, what qualities make up a great CTO?
I'm not sure what a “Google perspective” is, but I can dig up an uniformed opinion or two (or three).
As an officer of a business, a CTO has the primary responsibility of keeping the business going and growing (“maximizing shareholder value”), with particular emphasis on the technological tools the company uses and perhaps creates. A good CTO would be well-informed about where the state-of-the-art is and where it will be in a few years and what tools will give the most advantage with the least cost and risk.
That's the business school answer. I didn't go to business school.
I have been employed by a few companies that were big enough to have a CTO, and I have a different opinion in that context. While I want the company to be successful, and I do my part to help, I don't have the responsibility to consider the “business issues” associated with the technology. I personally take into consideration the effect that the technology has on my job and my co-workers jobs. I went to a tech school because I like technology for its own sake. I like to hang out and work with others that feel the same way. As an employee, I want a CTO that does what is necessary for the business, but also provides sufficient tools and “toys” so that my job is interesting, exciting, and challenging. If the work is dull, tedious, and requires little thought, I start to daydream about something better.
You can see that my desires aren't perfectly aligned with the CTO's responsibilities, so a company with a “great” CTO might be anathema to me, but a CTO that indulges the engineers of a company much more than is strictly necessary for business would make me more interested in being employed there.
I'm not sure what a “Google perspective” is, but I can dig up an uniformed opinion or two (or three).
As an officer of a business, a CTO has the primary responsibility of keeping the business going and growing (“maximizing shareholder value”), with particular emphasis on the technological tools the company uses and perhaps creates. A good CTO would be well-informed about where the state-of-the-art is and where it will be in a few years and what tools will give the most advantage with the least cost and risk.
That's the business school answer. I didn't go to business school.
I have been employed by a few companies that were big enough to have a CTO, and I have a different opinion in that context. While I want the company to be successful, and I do my part to help, I don't have the responsibility to consider the “business issues” associated with the technology. I personally take into consideration the effect that the technology has on my job and my co-workers jobs. I went to a tech school because I like technology for its own sake. I like to hang out and work with others that feel the same way. As an employee, I want a CTO that does what is necessary for the business, but also provides sufficient tools and “toys” so that my job is interesting, exciting, and challenging. If the work is dull, tedious, and requires little thought, I start to daydream about something better.
You can see that my desires aren't perfectly aligned with the CTO's responsibilities, so a company with a “great” CTO might be anathema to me, but a CTO that indulges the engineers of a company much more than is strictly necessary for business would make me more interested in being employed there.
Wednesday, March 14, 2012
Recursion with no base case?
Here's my solution:
This is an example of a well-founded recursive program that does not have an explicit base case.
(define (all-descendants node-children root)
(cons root
(append-map (lambda (child)
(all-descendants node-children child))
(node-children root))))
I wasn't measuring, but it took me more than a minute. I spent most of that time thinking about transitive closures, queues, iterating over elements, etc., before I realized that since I'm working with a tree rather than a directed graph, I need not worry about shared structure or duplicate elements.This is an example of a well-founded recursive program that does not have an explicit base case.
append-map (mapappend in Common Lisp) implicitly does not call the mapped function if the list argument is empty, so the recursion ends at the nodes of the tree that have no children.
Monday, March 12, 2012
1 minute puzzle
Given a procedure that returns a list of the children of a given node of a tree, write a procedure that returns a list of all the descendants of that node.
Wednesday, February 15, 2012
jrm bloviates
I recently received an email asking me, “ Do you know of any good books
about developing software or thinking in abstraction? I have books,
but how did you train your mind?”
I'm not sure I even have a clue. I think that some of the things I've read and worked on were influential, but it isn't clear to me whether anyone else would agree. I've met people that have read the same books and their thought processes are completely alien to me. I know people that are very good at what they do, and reach solid, well-engineered solutions, but I cannot talk with them because they seem to have an insane basic approach to understanding. I've also been on the other end of this where I cannot seem to get the other person to understand a very simple idea on which everything hinges. But since this is a blog, I hardly need to be informed to express an opinion.
College was a huge influence on my thinking. I was fortunate enough to learn from some of the luminaries not only in Computer Science, but also in Math (Gian-Carlo Rota, Alar Toomre), Material Science (August Witt), Physics (I forget), Film (Richard Leacock), etc. What I noticed was that these really smart people spent an awful lot of their time and energy thinking about and talking about the basics and fundamentals. Over and over again they would stress going back to first principles. They invariably would lecture about “creating a model” to help in understanding. In the introductory courses, we'd focus on the commonly used models, but the professors would usually show us alternative models that had interesting properties. In the advanced courses, we would often use several different models. Sometimes the models were apparently contradictory, but were nonetheless useful.
6.001, Structure and Interpretation of Computer Programs, was heavily oriented towards controlling complexity with abstraction. To a large extent, it wasn't a programming course, but a survey course that explored a huge number of abstractions that have been found useful. The fact that it used Scheme as an expository language is irrelevant. The real point of the course was to look at the many different techniques of abstraction and to illustrate the commonalities and differences between them. However, the difficulty of the course tended to obscure this for many students. When you're trying to learn the syntax and semantics of a language, you can easily get bogged down in the minutiae and miss the big picture. For example, the “Triangle Language” problem set made heavy use of higher-order procedures.
The pedagogic goal was twofold: to become comfortable manipulating procedures as first-class objects, but also to be able to create an abstract model of picture composition through triangle-oriented primitives. At the abstract level, we had triangular `pictures' that could be decomposed by cutting larger triangles into sections, or composed by pasting smaller triangles together with scaling and rotation.
The Triangle Language is not a very complex language. It is not very general or useful. It is simply an example of a trivial domain-specific language. It is possible for a student to do the entire problem set, learn a huge amount about higher-order procedures, ace the quiz, and completely miss the point about solving a problem through creating a domain-specific toolkit. Many did. It was ok because every problem set contained some more examples of this. Eventually it will sink in.
6.004 also spent a lot of time talking about different abstractions, but it proceeded differently. We started with the linear model of a transistor, then developed the digital abstraction, from there we had switches. With a couple of more electronic elements, we could implement combinational logic. The combinational logic could be used to implement flip-flops and finite state machines. The state machines, combined with some memory, could implement simple push-down automata and stack machines. A stack machine is a good target for a higher level language, so we could write a compiler. The really interesting part of this course was the lab work where we'd wire these things up. Each week we'd augment the circuits built the previous week and we had built a small computer by the time we got to the end of the course. What was good about this was that you could see all the levels of abstraction at once. The little black transistors over on that side of the board were implementing a gate in a state machine that drove the clock for the microcode unit. You could look at the transistor as switching bits, computing part of a trivial function, or throttling electrons, whichever abstraction was the most relevant at the time.
I guess that the old maxim “practice makes perfect” is true. I trained my mind — They trained my mind by constantly teaching about various abstractions.
As for books, I obviously recommend Structure and Interpretation of Computer Programs, but there aren't many books that just talk about abstractions. It is well worth learning alternative abstractions to things you already know. Hamiltonian and Lagrangian physics has a different view than Newtonian physics, for example. (Unfortunately, it is hard to just get a simple introduction to Lagrangian and Hamiltonian physics.) It unfortunate that many useful alternative abstractions are very poorly taught. Try to find alternative abstractions that make sense to you. Try recasting familiar ideas in different abstractions (this can be fun and bizarre if the abstraction is from an unrelated subject). Rewrite a program based on a completely different abstract model. Try to simplify a complex program to the minimal abstraction possible. Just keep on practicing!
I'm not sure I even have a clue. I think that some of the things I've read and worked on were influential, but it isn't clear to me whether anyone else would agree. I've met people that have read the same books and their thought processes are completely alien to me. I know people that are very good at what they do, and reach solid, well-engineered solutions, but I cannot talk with them because they seem to have an insane basic approach to understanding. I've also been on the other end of this where I cannot seem to get the other person to understand a very simple idea on which everything hinges. But since this is a blog, I hardly need to be informed to express an opinion.
College was a huge influence on my thinking. I was fortunate enough to learn from some of the luminaries not only in Computer Science, but also in Math (Gian-Carlo Rota, Alar Toomre), Material Science (August Witt), Physics (I forget), Film (Richard Leacock), etc. What I noticed was that these really smart people spent an awful lot of their time and energy thinking about and talking about the basics and fundamentals. Over and over again they would stress going back to first principles. They invariably would lecture about “creating a model” to help in understanding. In the introductory courses, we'd focus on the commonly used models, but the professors would usually show us alternative models that had interesting properties. In the advanced courses, we would often use several different models. Sometimes the models were apparently contradictory, but were nonetheless useful.
6.001, Structure and Interpretation of Computer Programs, was heavily oriented towards controlling complexity with abstraction. To a large extent, it wasn't a programming course, but a survey course that explored a huge number of abstractions that have been found useful. The fact that it used Scheme as an expository language is irrelevant. The real point of the course was to look at the many different techniques of abstraction and to illustrate the commonalities and differences between them. However, the difficulty of the course tended to obscure this for many students. When you're trying to learn the syntax and semantics of a language, you can easily get bogged down in the minutiae and miss the big picture. For example, the “Triangle Language” problem set made heavy use of higher-order procedures.
The pedagogic goal was twofold: to become comfortable manipulating procedures as first-class objects, but also to be able to create an abstract model of picture composition through triangle-oriented primitives. At the abstract level, we had triangular `pictures' that could be decomposed by cutting larger triangles into sections, or composed by pasting smaller triangles together with scaling and rotation.
The Triangle Language is not a very complex language. It is not very general or useful. It is simply an example of a trivial domain-specific language. It is possible for a student to do the entire problem set, learn a huge amount about higher-order procedures, ace the quiz, and completely miss the point about solving a problem through creating a domain-specific toolkit. Many did. It was ok because every problem set contained some more examples of this. Eventually it will sink in.
6.004 also spent a lot of time talking about different abstractions, but it proceeded differently. We started with the linear model of a transistor, then developed the digital abstraction, from there we had switches. With a couple of more electronic elements, we could implement combinational logic. The combinational logic could be used to implement flip-flops and finite state machines. The state machines, combined with some memory, could implement simple push-down automata and stack machines. A stack machine is a good target for a higher level language, so we could write a compiler. The really interesting part of this course was the lab work where we'd wire these things up. Each week we'd augment the circuits built the previous week and we had built a small computer by the time we got to the end of the course. What was good about this was that you could see all the levels of abstraction at once. The little black transistors over on that side of the board were implementing a gate in a state machine that drove the clock for the microcode unit. You could look at the transistor as switching bits, computing part of a trivial function, or throttling electrons, whichever abstraction was the most relevant at the time.
I guess that the old maxim “practice makes perfect” is true. I trained my mind — They trained my mind by constantly teaching about various abstractions.
As for books, I obviously recommend Structure and Interpretation of Computer Programs, but there aren't many books that just talk about abstractions. It is well worth learning alternative abstractions to things you already know. Hamiltonian and Lagrangian physics has a different view than Newtonian physics, for example. (Unfortunately, it is hard to just get a simple introduction to Lagrangian and Hamiltonian physics.) It unfortunate that many useful alternative abstractions are very poorly taught. Try to find alternative abstractions that make sense to you. Try recasting familiar ideas in different abstractions (this can be fun and bizarre if the abstraction is from an unrelated subject). Rewrite a program based on a completely different abstract model. Try to simplify a complex program to the minimal abstraction possible. Just keep on practicing!
Tuesday, February 14, 2012
ILC 2012 Call for Papers
+----------------------------------------------------------------------+
| |
| INTERNATIONAL LISP CONFERENCE 2012 |
| |
| http://www.international-lisp-conference.org |
| |
| Campus Plaza Kyoto, Kyoto, Japan - October 21-24, 2012 |
| |
| Sponsored by: The Association of Lisp Users |
| |
+----------------------------------------------------------------------+
General Information:
The Association of Lisp Users is pleased to announce the 2012
International Lisp Conference will be held in Kyoto, Japan at
Campus Plaza Kyoto from October 21st to 24th, 2012.
This year's program consists of tutorials at beginners' and
advanced levels, prominent invited speakers from the Lisp
communities, an excellent technical session, tours of
Jidai-Matsuri: festival enjoyed by people of all ages,
participating in its historical reenactment parade dressed in
authentic costumes representing various periods, and characters
in Japanese feudal history.
General conference announcements are made on a very occasional
basis to the low-volume mailing list
ilc12-announce. http://www.alu.org/mailman/listinfo/ilc12-announce
Technical Program:
Original submissions in all areas related to the conference themes
are invited for the following categories:
Papers: Technical papers of up to 15 pages that describe original
results.
Demonstrations: Abstracts of up to 2 pages for demonstrations of
tools, libraries and applications.
Workshops: Abstracts of up to 2 pages for groups of people who
intend to work on a focussed topic for half a day.
Tutorials: Abstracts of up to 2 pages for indepth presentations
about topics of special interest for 90 - 180 minutes.
Panel discussions: Abstracts of up to 2 pages for discussions about
current themes. Panel discussion proposals must mention panel
member who are willing to partake in a discussion.
Lightning talks: Abstracts of up to one page for talks to last
for no more than 5 minutes.
Important Dates:
Please send contributions before the submission deadline, including
abstracts of 4 pages for technical papers and abstracts of 2 pages
for all other categories.
Deadline for abstract submissions: July 15, 2012
Notification of acceptance or rejection: July 31, 2012
Deadline for final paper submissions: August 31, 2012
Papers to be presented should be submitted electronically at
easychair
(https://www.easychair.org/account/signin.cgi?conf=ilc2012)
and need to use the ACM format
(http://www.acm.org/sigs/publications/proceedings-templates)
Scope:
Lisp is one of the greatest ideas from computer science and a
major influence for almost all programming languages and for all
sufficiently complex software applications.
The International Lisp Conference is a forum for the discussion of
Lisp and, in particular, the design, implementation and
application of any of the Lisp dialects. We encourage everyone
interested in Lisp to participate.
We invite high quality submissions in all areas involving Lisp
dialects and any other languages in the Lisp family, including,
but not limited to, ACL2, AutoLisp, Clojure, Common Lisp,
ECMAScript, Dylan, Emacs Lisp, ISLISP, Racket, Scheme, SKILL, etc.
Topics may include any and all combinations of Lisp and:
* Language design and implementation
* Language integration, inter-operation and deployment
* Applications (especially commercial)
* Reflection, meta-object protocols, meta-programming
* Domain-specific languages
* Programming paradigms and environments
* Parallel and distributed computing
* Theorem proving
* Scientific computing
* Data mining
* Semantic web
Organizing Committee:
General Chair: KURODA Hisao (Mathematical Systems Inc. / ALU)
Members: Daniel Herring (ALU)
Jon L White (ALU)
Rusty Johnson (ALU)
Program Chair: Hiroshi Okuno (Kyoto Univ.)
Members: Keith Corbett (Clozure Associates)
Alex Fukunaga (University of Tokyo)
Antonio Leitao (INESC-ID)
Joe Marshall (MIT)
Scott Mckay (ITA software)
Nancy Reed (University of Hawaii)
Kent Pitman (nhplace.com)
Duane Rettig (Franz Inc.)
Didier Verna (EPITA)
Takuo Watanabe (Tokyo Institute of Technology)
Edi Weitz (weitz.de)
Taiichi Yuasa (Kyoto University)
Local chair: Tetsuya Ogata (Kyoto Univ.)
Members: CHIBA Masaomi
SANO Masatoshi
Contacts:
* General Questions: ilc12-organizing-committee at alu.org
* Program Committee: ilc2012 at easychair.org
For more information, see http://www.international-lisp-conference.org
Thursday, January 19, 2012
A bit more challenging
In my previous post, I gave the puzzle of taking a pattern and generating code that matches it. The tricky part was making sure that the pattern is completely traversed at compile time. If the object to be tested matches the pattern, the pattern variables and their values were to be returned in an alist.
It would be better, however, to generate code where the pattern variables become bindings of Scheme variables. Instead of generating code that stuffs the values into an alist, like this code does at the highlighted points:
It would be better, however, to generate code where the pattern variables become bindings of Scheme variables. Instead of generating code that stuffs the values into an alist, like this code does at the highlighted points:
(make-matcher '((? one) and (? two))) => (lambda (object) (and (pair? object) (let ((left-submatch ((lambda (object) (list (cons 'one object))) (car object))) (right-submatch ((lambda (object) (and (pair? object) (let ((left-submatch ((lambda (object) (and (eqv? object 'and) '())) (car object))) (right-submatch ((lambda (object) (and (pair? object) (let ((left-submatch ((lambda (object) (list (cons 'two object))) (car object))) (right-submatch ((lambda (object) (and (eqv? object '()) '())) (cdr object)))) (and left-submatch right-submatch (append left-submatch right-submatch))))) (cdr object)))) (and left-submatch right-submatch (append left-submatch right-submatch))))) (cdr object)))) (and left-submatch right-submatch (append left-submatch right-submatch)))))We'd generate something more like this:
(make-matcher '((? one) and (? two)) <user code goes here>) => (lambda (object) (and (pair? object) (let ((one (car object)) (tail1 (cdr object))) (and (pair? tail1) (eq? (car tail1) 'and) (let ((tail2 (cdr tail1))) (and (pair? tail2) (let ((two (car tail2))) (and (null? (cdr tail2)) <user code goes here>))))))))This is more challenging for two reasons. First, we need to ensure that the pattern variable names become bound in a scope that encloses the user's code so that free references to pattern variables are correctly captured. In addition, we need to ensure that other “helper” bindings, like
tail1 and tail2 do not capture free references by accident. (That is to say, watch your macro hygiene.) Second, you have to be sure that subpattern bindings are visible to the entire body of the user code. This will throw a monkey wrench into the simple recursive solution.
Sunday, January 15, 2012
Slightly trickier
In my previous post, I gave a small pattern matching problem. It is easily solved by recursively descending the pattern and the object to match. This is analogous to interpreting the pattern because you walk the pattern each time you want to try to match an object.
If the pattern is constant, though, you can walk the pattern once and generate code that can match against an object much more quickly:
If the pattern is constant, though, you can walk the pattern once and generate code that can match against an object much more quickly:
(define my-matcher
(eval (make-matcher '(a (? var1) (nested (c (? var2)))))
user-initial-environment))
(my-matcher '(a b (nested (c d)))) => ((var1 . b) (var2 . d))
I'd rate this as an intermediate puzzle. It isn't very different from the previous one, but you have to pay more attention to the phase of evaluation. As a hint, here are a pair of possible matchers:
(make-matcher '((? car) . (? cdr))) =>
(lambda (object)
(and (pair? object)
(let ((p1 ((lambda (object) (list (cons 'car object))) (car object)))
(p2 ((lambda (object) (list (cons 'cdr object))) (cdr object))))
(and p1
p2
(append p1 p2)))))
(make-matcher '((? one) and (? two))) =>
(lambda (object)
(and (pair? object)
(let ((left-submatch
((lambda (object) (list (cons 'one object))) (car object)))
(right-submatch
((lambda (object)
(and (pair? object)
(let ((left-submatch
((lambda (object)
(and (eqv? object 'and)
'()))
(car object)))
(right-submatch
((lambda (object)
(and (pair? object)
(let ((left-submatch
((lambda (object)
(list (cons 'two object)))
(car object)))
(right-submatch
((lambda (object)
(and (eqv? object '())
'()))
(cdr object))))
(and left-submatch
right-submatch
(append left-submatch
right-submatch)))))
(cdr object))))
(and left-submatch
right-submatch
(append left-submatch right-submatch)))))
(cdr object))))
(and left-submatch
right-submatch
(append left-submatch right-submatch)))))
Astute readers will notice that this latter matcher is doing more work than necessary. If the match against part of the pattern fails, it still attempts to match the rest of the pattern. It only notices just before assembling the final result. Also, using append to assemble the sub-matches is a terrible waste.
Friday, January 13, 2012
A small puzzle
Here's a quick little puzzle that isn't too hard.
A pattern is:
A pattern is:
- A symbol, number, boolean, or null (an atom).
- A pattern variable, which is a two element list where the
first element is the symbol
?and the second is a symbolic (a symbol) name.;; Examples: ;; (pattern-variable? '(? foo)) => #t ;; (pattern-variable? '(? another-pattern-variable)) => #t ;; ;; (pattern-variable? '(not a (pattern variable))) => #f ;; (pattern-variable? '(?)) => #f ;; (pattern-variable? '(foo ?)) => #f ;; (pattern-variable? '(? foo . bar)) => #f ;; (pattern-variable? '(? foo quux)) => #f (define (pattern-variable? thing) (and (pair? thing) (eq? (car thing) '?) (pair? (cdr thing)) (symbol? (cadr thing)) (null? (cddr thing)))) - A pair (a
cons) of two patterns.
alist) of the pattern variable names and
the associated matching elements, or #F if the
pattern does not match.
;; Examples: ;; (pmatch '(foo (? pvar1) (? pvar2) bar) '(foo 33 #f bar)) ;; => ((pvar2 . #f) (pvar1 . 33)) ;; ;; (pmatch '(foo (? pvar) bar) '(quux 33 bar)) ;; => #f ;; ;; (pmatch '(a (? var1) (nested (c (? var2)))) '(a b (nested (c d)))) ;; => ((var2 . d) (var1 . b)) ;; ;; Edge cases: ;; ;; (pmatch '(a b c) '(a b c)) ;; => '() ;; ;; (pmatch '(foo (? pvar1) (? pvar2) bar) '(foo 33 (xyzzy #f) bar)) ;; => ((pvar2 xyzzy #f) (pvar1 . 33)) ;; ;; (pmatch '(foo . (? pvar)) '(foo bar baz)) ;; => ((pvar bar baz)) ;; ;; (pmatch '((? ?) quux) '(foo quux)) ;; => ((? . foo)) ;; ;; (pmatch '(? ?) '(foo quux)) ;; => ((? foo quux)) ;; ;; (pmatch '(? ? ?) '(foo quux)) ;; => #fPlease be careful and obfuscate your solution if you want to post it.