subst in Prolog, pt i

The assignment:
"Write subst(A,B,C,D) where list D is list C with element A substituted for all occurrences of element B."

The first case we want to handle is the base case. That is, if we have the empty list, it does not matter what A and B are, because there is nothing to replace. Therefore:
subst(A, B, [ ], [ ]).

Or, because we are using neither A nor B, we can write:
subst(_, _, [ ], [ ]).

The alternative is that we are not dealing with an empty list. In such a situation, we want to define subst recursively, such that we yank out the first element -- the head -- if it is B, and replace it with A. Unless of course the head is not element B, in which case we want to just leave it alone -- that is, put the head back on the list.

The way we pull apart such a list is as [H | T], where H is the head and T is the tail.

More on this later, but hopefully this gets you on the right track. It does not have to work exactly.

8, 9, 10, 13, 15, 16

ch 8 -- control structures p 324 and on
if-fi
do

od

ch 9, ch 10: parameter passing
skip 380-387
focus on coroutines, on page 391

in ch 10, statis links, dynamic links

skip ch 11, 12, 14

do chapter 13

http://docs.google.com/Doc?id=ajbqhgmq9qdz_110cscw9cc7

Common Lisp Tutorial

http://www.notam02.no/internt/cm-sys/cm-2.2/doc/clt.html

Not Equal In Prolog

After consulting with this website, actually connected with pop11. :)

The following interaction from SWI-Prolog when consulting j.pl. Use similar code to make sure sally is not her own sibling.

% c:/j.pl compiled 0.00 sec, -292 bytes
11 ?- listing.


myneq(A, B) :-
A\=B.

Yes
12 ?- myneq(a, a).

No
13 ?- myneq(a, b).

Yes

Download PopLog, a Free Lisp Interpreter

Here

After installing, modify the shortcut to have a +clisp after the +startup. Try out the examples from the Wikipedia page on Lisp,

http://en.wikipedia.org/wiki/Lisp_%28programming_language%29

aside from any Lisp homework I may assign.

Video Solutions for HW 7 and 8

Available here.

Prolog

SW-I Prolog is a Prolog that works.

http://www.swi-prolog.org/

we will work through the examples here:
http://www.ling.helsinki.fi/kit/2004k/ctl272/Bangor/clbook.html

All About Gotos

Read this article from Knuth, "Structured programming with go to statements"

Homework: Implement a CFG

You can watch the video detailing the assignment here:
http://www.girsology.com/proglang/

And as soon as Revver approves the video, I will embed the video in this post as well.
Update: Here it is:

class notes for today

type
colors ( red, blue, green, yellow, orage, white, black);

colorset = set of colors;

var
set1, set2 : colorset;

set1 := [ red, blue, yellow ];
set2 := set1;
set2 := [black, blue ];

if (ch = 'c' or ch = 'r' or ch = 'y')

if (ch in ['c', 'r', 'y'])

if (c in colorset)

as bitset

['a' ... 'p']

foo()
{
int * p, *y;
p = &f;
p = y;

cout *p;

cout p;
p = y;
*p = *y;
p =: y;
p =: f;

int * p = new int [100];

p = new int [100];

*(p + 7);
p[7];
cout 7[p];
*(7 + p);

int &r = t;

r
*r

}

Tombstone
lock and key

int *y;
foo()
{
Int *p;
p = new int;
y = p;
}

eager approach
lazy approach

refernce counting
garbage collection

The Three-Register Garbage Recycler, or Nodes for Free, by David Wise

"The Three-Register Garbage Recycler, or Nodes for Free," by David Wise. Use the links to the image.

Questions to follow, or perhaps I will ask someone to present.

Read this paper on Distributed Cyclic Reference Counting

Read this paper on "Distributed Cyclic Reference Counting" by Frank Dehne, Rafael D. Lins.

Questions on the paper to follow. Or perhaps I will ask someone to summarize the paper.

Some class notes

1 4 6 8 5 32 0 -1
1 4 6 8 5 3 2 0 -1
1 8 2 4 5 0 6 3 -1
int list[10];cout list[k];
address(list[k]) = address(list[1]) + (k-lowerbound)*el_size= address(list[1])- lowerbound*el_size + k*el_size
descriptor for arrays_________arrayelem typeindex type# of dimensionsindex upper boundindex lower boundaddress
// using ] in place of greater than because of html%salaries = ("Cedric" =] 75000, "Perry" =]56000);$salaries{"Perry"} = 70000;$s = "Josh";$salaries{$s} = 8000;if exists $salaries{"Shelly"}delete $salaries{"Perry"};%salaries = ();
01 EMPLOYEE-RECORD 02 EMPLOYEE-NAME 05 FIRST PICTURE IS X(20) 05 MID PICTURE IS X(20) 05 LAST PICTURE IS X(20) 02 HOURLY-RATE PICTURE IS 99V99
01 employer-record 02 employer-name 05 FIRST PICTURE IS X(20) 05 LAST PICTURE IS X(20) 05 SSN PICTURE IS X(20)
FIRST OF EMPLOYEE-NAME OF EMPLOYEE-RECORD
FIRST OF EMPLOYEE-RECORD
STRUCT A{ STRUCT B { INT X; INT Y; } J; CHAR Z; } H;
H.J.X
class a{ int i; char * p; string g; a() { p = new char [60]; ~a() { delete [] p; }};
a b, c;
b = c;
b.g = c.g;
move corresponding employer-record to employee-record
dynamic variables as discussed in the papermain(){ int x, y; int z; set z : int = x -4 in { foo(); bar(); } bar();}
foo(){ int a, b; use z : int in { cout z;
}}
bar(){ int q; set z : int = q -4 in { foo(); }}

Homework #11: Variables With Dynamic Scope

Read this article at Microsoft Research about "Dynamic Variables." Do not read the Appendix to the article just yet, only the main body of the article.

Answer the following questions:
1) List two purposes for which they envision using these dynamically scoped variables?
2) Choose one of those two, and motivate it. That is, show what the code would look like when not using dynamic variables, and then what it would look like with dynamic variables.
3) Briefly describe the "simple" and the "novel" implementations.

Homework #10

1. Read this article about regular expressions in Word, and try the find and replace example in the article.

2. Read the Wolfe article posted on blackboard, "Nesting In Ada Programs Is For The Birds," and answer the questions: Give four reasons why nesting in Ada programs is for the birds. What is the authors' suggestion?

class notes from today

some prolog:

father (terach, avraham).
father (avraham, yitzchak).
father (avraham, yishmael).

brother (A, B) :- father(C, A), father (C, B).

?- brother (yitzchak, yishmael)
True

?- brother (yitzchak, Z)
yishmael

floating point:
_______________
sign bit
exponent
fraction

decimal
_____________
part before decimal pt.
part after decimal pt.
1060 = 10.60


integers
______________
sign magnitude notation
two's complement
one's complement

descriptors for:

static length string

--------------
string
length
address
_________________

limited dynamic length string

_-________________________
limited dynamic string
maximum length
current length
address
___________________________

enum temperature { hot, cold, freezing };

enum proximity { near = 6, cold = 7, freezing =8};
proximity::cold

Some Class Notes

int x[6];

int n;
cin >> n;
int x[n];

int * x = new int [n];
Backus-Naur Form
BNF
CFG - Context Free Grammar

Josh
josh

int int;

REAL APPLE;
INTEGER REAL;
REAL INTEGER;

int shakespeare;
shakespencil = 60;


FSA which recognize regular languages
NFA is equivalent to an FSA

regular langs are closed on the Operations of union, concatenation,
and kleene star

E is the input alphabet
G is the output alphabet

PDA = Push Down Automaton
can recognize CFLanguages,
which can be described with CFG, BNF

Getting Fortran to Run

I am still working on getting FORTRAN installed in the labs, for G95. In the meantime, on your own personal machines, you can try installing the Silverfrost FTN95 compiler. It is free for personal use, but has an annoying screen before running any of your programs. And it integrates with the Visual Studio 2005 IDE, with makes it much easier to test out your programs. And it color codes keywords, and lets you step through the code, and so on. I tried it, and it worked with no headaches setting it up.

HW #8, with video intro

Not to be confused with homework #7.

#8:
Using VBA for Excel, implement the first FSA from assignment #5. On the spreadsheet, include a formal description of the FSA. This includes the transition function delta. Rather than using Gotos, keep a variable which maintains the present state, and look up the appropriate transition to the next state, based on the present state and the input, from that lookup table on the Excel worksheet.

You can download the video here.