[ Posted by urban
Sat, 02 Apr 2005 12:31:36 GMT ]
This is the announcement for NARCL version 0.1.0.
What is NARCL?
NARCL stands for Negative Association Rules in Common Lisp. As the name suggests it is a program to find association rules and it is written in Common Lisp.
Why did you write it?
At the time where I started writing it no program existed that could compute negative association rules. But I may eventually need a program like that in the future.
How mature is the program?
Well, its version is 0.1.0 so you can imagine. What works is the computation of negative and positive association rules on a given set of transactions. But it is very slow, due to the use of rather inefficient data structures. Nonetheless it might be useful to some people, so here it is.
What license does it have?
The code is licensed under the LLGPL which is essentially the LGPL with some Lisp specific additions and clarifications.
Where can I download it?
You can download the source as a compressed tar ball from my web site:
Tags data, learning, lisp, machine, mining, NARCL, project
[ Posted by urban
Sat, 02 Apr 2005 12:29:29 GMT ]
This project is actually two projects at once:
- The implementation of a Common Lisp compiler. Something that I wanted to do for quite a while.
- Adding support for parallel programming to Common Lisp. I’m currently reading Concepts, Techniques, and Models where I will hopefully learn much about parallel programming paradigms.
You may ask why I would want to write yet another Common Lisp implementation. It’s of course true that there are enough implementations already out there and it remains to be seen if I will be able to actually complete the thing. After all Common Lisp is a huge language. But I consider myself a hacker (even though I don’t qualify as a geek :)) and I really want to write a compiler myself.
And that’s where the second goal comes into play. Why not use the virtual machine of a already parallel language? This would probably mean that there is already support for parallelism in the VM. I don’t know how much easier that will make the implementation but it’s a nice excuse :)
The first step is already made. I’ve found a name for it: Hummingbird. It doesn’t have any deeper meaning it’s just a name that I like. The next step will be to finish reading ‘Concepts, Techniques, and Models’ to have a good grounding in parallel programming. Then Lisp in Small Pieces is waiting in one of my shelves to be read. Meanwhile I will look at the VMs of parallel languages out there (like Mozart and Alice, which is based on SEAM) and watch what other Parallel Lispers are doing (like Dirk Gerrits Erlisp project).
Even though my plan might sound nice to you, it has several flaws:
- The book ‘Concepts, Techniques, and Models’ is a 1000 page computer science text book. Far from light reading. I can’t even estimate how long it will take me to finish reading it.
- And the ‘Lisp in Small Pieces’ isn’t light reading, too. At least not for me, who doesn’t have that much experience is writing compilers (i.e. I haven’t written one yet!).
- I’m really bad at actually finishing stuff, especially programming projects.
So why do I write a blog entry about it then? Well, firstly because writing things down helps me to make them more clear and secondly because you might like this idea and start implementing it. Even though I’d like to implement it myself I’d be happy to just play with the result, too.
Tags concurrent, idea, lisp
[ Posted by urban
Sat, 02 Apr 2005 12:25:24 GMT ]
This is my take on the del.icio.us tools. One of the nice features of
del.icio.us is that you can aggregate the new entries of other users
in your inbox. The only problem is actually finding users that post
links that interest you.
My idea is that if other users have posted the same links as you have
they are likely to do so in the future, too. And because they have
many links in common with you they should have similar interests.
Therefore the other links they post should be more likely to interest
you.
So, the idea is to take all your links and look for each link which
other users have posted this link, too. The more links another user
has in common with you the higher is your similarity. Then the top n
users would be recommended to you to add to your inbox.
For a more advanced implementation it would also be nice to weight
each link, i.e. the more other users have this link in common with
you the less weight it should get (as it is less specific). This
would favour more specific links over links that nearly everybody
has.
Tags del.icio.us
[ Posted by urban
Sat, 02 Apr 2005 12:24:19 GMT ]
If you get bored by me making the exercises of the book Concepts, Techniques, and Models of Computer Programming, but like the book anyway you may want to look at the wiki about it.
Tags CTM, wiki
[ Posted by urban
Sat, 02 Apr 2005 12:23:07 GMT ]
The problem
Functions and procedures. If a function body has an if statement with a missing else case, then an exception is raised if the if condition is false. Explain why this behaviour is correct. This situation does not occur for procedures. Explain why not.
My solution
Every function has to return a value. That’s one of the integral parts of functional programming. That’s why the exception is raised when the function tries to return the value from the missing else case. In other functional programming languages like Haskell it’s even not allowed to leave out the else case.
Procedures on the other hand don’t have to return a value. So the if statement might just be executed for it’s side effects. And then it’s no problem when nothing happens in the missing else case.
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 12:19:53 GMT ]
The problem
Contextual environment. Section 2.4 explains how a procedure call is executed. Consider the following procedure MulByN:
declare MulByN in
N=3
proc {MulByN X ?Y}
Y=N*X
end
together with the call
{MulByN A B}. Assume that the environment at the call contains {A -> 10, B -> x
1}. When the procedure body is executed, the mapping
N -> 3 is added to the environment. Why is this a necessary step? In particular, would not
N -> 3 already exist somewhere in the environment at the call? Would not this be enough to ensure that the identifier
N already maps to 3? Give an example where
N does not exist in the environment at the call. Then give a second example where
N does exist there, but is bound to a different value than 3.
My solution
The problem here is to ensure that N is 3 every time MulByN is called. It should not change when N is shadowed between the definition of the procedure and the call to it. That’s why it is necessary to insert N into the environment. This ensures that the call to MulByN is executed in the environment that existed when MulByN was defined. This exercise is probably meant to ensure that you understand the difference between lexical and dynamic scoping. As I’m a bit lazy I won’t write down the examples. It’s left as an exercise to the reader :)
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 12:14:09 GMT ]
The problem
Free and bound identifiers. Consider the following statement:
proc {P X}
if X>0 then {P X-1} end
end
Is the second occurrence of the identifier
P free or bound? Justify your answer.
Hint: this is easy to answer if you first translate to kernel syntax.
My solution
This is my translation into the kernel syntax.
declare P in
P = proc {$ X}
local L in
L=(X>0)
if L then {P X-1} else skip end
end
end
Even though I’m not sure, I assume that the second occurrence of P has to be defined. How else could you do recursive procedures? And it does work in Mozart. If the second P wasn’t defined how could it work?
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 12:11:11 GMT ]
The problem
Explicit state and concurrency. Section 1.15 gives an example using a cell to store a counter that is incremented by two threads.
(a) Try executing this example several times. What results do you get? Do you ever get the result 1? Why could this be?
(b) Modify the example by adding calls to Delay in each thread. This changes the thread interleaving without changing what calculations the thread does. Can you devise a scheme that always results in 1?
(c) Section 1.16 gives a version of the counter that never gives the result 1. What happens if you use the delay technique to try to get an 1 anyway?
My solution
(a) I only ran it 6 times and I always got two. This might be because each time slice given to each of the threads was big enough to execute both statements. It might be different if I run other programs at the same time.
(b) You have to insert the Delay calls after the assignment of the value of the cell to the local variables. When the delays are big enough they should both get the value 0 from the cell. This worked for me:
declare
C={NewCell 0}
thread I in
I=@C
{Delay 100}
C:=I+1
end
thread J in
J=@C
{Delay 100}
C:=J+1
end
(c) This of course won’t work as the threads will just block for the delay time. That’s the whole reason for locks, isn’t it?
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 12:08:20 GMT ]
The problem
Memory store. This exercise investigates another way of introducing state: a memory store. The memory store can be used to make an improved version of FastPascal that remembers previously calculated rows.
(a) A memory store is similar to the memory of a computer. It has a series of memory cells, numbered from 1 up to the maximum used so far. There are four functions on memory stores: NewStore creates a new store, Put puts a new value in a memory cell, Get gets the current value stored in a memory cell, and Size gives the highest-numbered cell used so far. For example:
declare
S={NewStore}
{Put S 2 [22 33]}
{Browse {Get S 2}}
{Browse {Size S}}
This stores [22 33] in memory cell 2, displays [22 33], and then displays 2. Load into the Mozart system the memory store as defined in the supplements file on the book’s Web site. Then use the interactive interface to understand how the store works.
(b) Now use the memory store to write an improved version of FastPascal, called FasterPascal, that remembers previously calculated rows. If a call asks for one of these rows, then the function can return it directly without having to recalculate it. This technique is sometimes called memoization since the function makes a “memo” of its previous work. This improves performance. Here’s how it works:
- First make a store S available to
FasterPascal.
- For the call
{FasterPascal N}, let m_ be the number of rows stored in S, i.e., rows 1 up to _m are in S.
- if n_ > _m, then compute rows m_ + 1 up to _n and store them in S.
- Return the nth row by looking it up in S.
Viewed from the outside, FasterPascal behaves identically to FastPascal except that it is faster.
(c) We have given the memory store as a library. It turns out that the memory store can be defined by using a memory cell. We outline how it can be done and you can write the definitions. The cell holds the store contents as a list of the form [N1|X1 ... Nn|Xn], where the cons Ni|Xi means that cell number Ni has content Xi. This means that memory stores, while they are convenient, do not introduce any additional expressive power over memory cells.
(d) Section 1.13 defines a counter object. Change your implementation of the memory store so that it uses this counter to keep track of the store’s size.
My solution
(b) Here’s my solution:
declare FasterPascal FastPascal2 AddList ShiftLeft ShiftRight in
fun {AddList L1 L2}
case L1 of H1|T1 then
case L2 of H2|T2 then
H1+H2|{AddList T1 T2}
end
else nil end
end
fun {ShiftLeft L}
case L of H|T then
H|{ShiftLeft T}
else [0] end
end
fun {ShiftRight L} 0|L end
% M is the biggest row currently in the store
% N is the row that we want to compute
% S the store to work on
fun {FastPascal2 M N S}
% Finished adding the rows between M and N so just return the Nth row
if M>=N then
{Get S N}
else L in
% Get the previous row to compute the current one
L={Get S M}
% Put it into the store
{Put S M+1 {AddList {ShiftLeft L} {ShiftRight L}}}
% Compute the next bigger missing row
{FastPascal2 M+1 N S}
end
end
local S in
S={NewStore}
{Put S 1 [1]}
fun {FasterPascal N}
M={Size S}
in
{FastPascal2 M N S}
end
end
(c)
declare NewStore Put Get Size in
fun {NewStore}
{NewCell nil}
end
proc {Put S N I}
fun {PutHelper S N I}
case S of Num|Val|T then
if Num==N then
N|I|T
else
Num|Val|{PutHelper T N I}
end
else
N|I|S
end
end
in
S:={PutHelper @S N I}
end
fun {Get S N}
fun {GetHelper S N}
case S of Num|Val|T then
if Num==N then
Val
else
{GetHelper T N}
end
else
nil
end
end
in
{GetHelper @S N}
end
fun {Size S}
fun {SizeHelper S N}
case S of _|_|T then
{SizeHelper T N+1}
else
N
end
end
in
{SizeHelper @S 0}
end
(d)
declare
fun {NewStore}
Cell Put Get Size SizeI in
Cell={NewCell nil}
SizeI={NewCell 0}
proc {Put N I}
fun {PutHelper S N I}
case S of Num|Val|T then
if Num==N then
N|I|T
else
Num|Val|{PutHelper T N I}
end
else
SizeI:=@SizeI+1
N|I|S
end
end
in
Cell:={PutHelper @Cell N I}
end
fun {Get N}
fun {GetHelper S N}
case S of Num|Val|T then
if Num==N then
Val
else
{GetHelper T N}
end
else
nil
end
end
in
{GetHelper @Cell N}
end
fun {Size}
@SizeI
end
store(put:Put get:Get size:Size)
end
declare A in
A={NewStore}
{Browse {A.size}}
{A.put 2 [22 23]}
{A.put 1 [21 243]}
{Browse {A.get 1}}
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 11:49:00 GMT ]
The problem
Explicit state and functions. This exercise investigates how to use cells together with functions. Let us define a function {Accumulate N} that accumulates all its inputs, i.e., it adds together all the arguments of all calls. Here is an example:
{Browse {Accumulate 5}}
{Browse {Accumulate 100}}
{Browse {Accumulate 45}}
This should display 5, 105, and 150, assuming that the accumulator contains zero at the start. Here is a wrong way to write
Accumulate:
declare
fun {Accumulate N}
Acc in
Acc={NewCell 0}
Acc:=@Acc+N
@Acc
end
What is wrong with this definition? How would you correct it?
My solution
The problem is that
Acc is created each time
Accumulate is called. We have to move
Acc out of the definition of
Accumulate. To ensure that it’s not possible to set
Acc from outside we declare it using a
local statement. Here’s the code:
declare
local Acc in
Acc={NewCell 0}
fun {Accumulate N}
Acc:=@Acc+N
@Acc
end
end
Tags book, CTM, oz
