• Parameter passing (5.2)
  
• call-by-value
  
  -> pass in value
  procedure (3+x)
  procedure (a: integer): this does not change the value of the variable
  3+x, x are actuals
  a: integer is a formal parameter
  
• call-by-reference
  
  parameter is a pointer to actual parameter
  procedure (var a: integer)
  void p (int&a)
  gives you more power, example: swap function directly
  
• call-by-value-result Ada
  
  copy-in, copy-out
  like call-by-reference, except ref is only modified at end
  -> can produce different results
  aliasing: multiple names for same location
  example:
  var i
  proc p (x)
  begin
        i:=0
  end
  
  i:=2
  p(i)
  write(i)
• how this code is interpreted using different call methods?
• call-by-reference
  
  p(2)-> 2 becomes 0 -> 0 is printed
  
• call-by-value-result ???
  
  p(2) ->  creates a x inside the procedure 2 becomes 0 -> 0 -> becomes 2 -> 2 is printed
• call-by-name Algol60
• textual substitution
  proc swap (a, b)
  var t
  t:=a, a:=b, b:=t;
  
  swap (x,y) will be translated as  t:=x; x=y; y:=t
  swap (i, A[i]) will be translated as t:=i; i:=A[i]; A[i]:=t   (i has changed in the last A[i] so it will not give us the intended resluts)
  
  C
  #define SQR(x)   (x*x)
  a=SQR(b); will be translated as a=(b*b);
  b=SQR(b+1); will be translated as a=(b+1*b+1)
  how to avoid this? use parentheses ((x)*(x))
• Scopes (5.4)
  
• static/ lexical scope
• just by looking you can always know which declaration refer to which variable
• example:
  var n
  proc w
      write(n)
  
  proc D
     var n
     w
  
  what happens if we change n to i in proc D? you will have a different effect.
  
  conclusion: dynamic scopes that call by name like algol are not desirable, actually algol60 renames these names for you so to avoid this problem.
  

• Outline
• C
  
• foundations
• arrays,
  
• stacks
  
• C (15.2, 4.8)
• Syntax, [types] like java
• no String type, instead an array of char (char[])
• not OO
• pure C, -ansi -pedantic
• old C, examples
• commenting '//' is not allowed
• mixed declaration of type
  
• declare stuff first, you can not have print'***' and then declare a new variable.
  
• you should get all the warnings
  
• -w: some warnings
• -wall : all the warnings
• pointers
• similar to Pascal, except that pointers in C can point to anything.
• int a; int *a;
  p=&a; *p=5;
  *p=5; p=5
• stimulating pass by reference in C [the trick is to pass the locations as values]
  int a=1, b=2;
  swap (&a, &b);
  void swap( int *p, int *q)
  {
          int temp=*p;
          *p= *q;
          *q=temp;
  }
  
• include <>, include ""
• advantage: splits code in different files
  
• the sub file, compile it using -c and it creates an object file that you can include somewhere else.
• ld -o *.o : link needed o files together
• if silly math was running slowly, turn -o -O optimization levels.
• debugging: -g
• gcc -o [output] -g [filename]
  
• useful for segmentation errors
• creates core file
  
• unlimit -c unlimited
• xemacs bash c
• gdb executable core
• use up/down
• ddb output core
  
• /* division.c
   *
   * Example for CS 313
   *
   * Daniel Scharstein
   *
   * to compile, use  gcc -Wall -o division division.c
   * to test for "pure" (ANSI) C, use -ansi - pedantic
   */
  
  #include <stdio.h>
  
  #include "sillymath.h"
  
  int main ()
  {
      int a, b;
      float c;
  
      a = 5;
      b = 3;
      printf("Hi!\n");
      c = quotient(a, b);
      printf("FYI, %d/%d is %f\n", a, b, c);
  
      return 0;  /* success exit status */
  }
  isadaqah@wilson:/home/schar/cs313/C> more sillymath.c
  float quotient(int a, int b) {
      float c;
  
      c = (float)a / (float)b;
  
      return c;
  }
  
  
• scanf is the opposite of printf
• scanf ("%d",&n)
• reads more than one token
• scanf("%d%s%d",&n,&m,&l)
  
• you have to have &, otherwise it will not read anything
• int[10]
• does 2 things at the same time
• new array
• 10 elements
• in Java int a[] = int[10]
• an array and a pointer are the same
• int b[]; and int *c;
• neither has memory allocated
• graphically showed as two empty boxes
• a[5] is the same as *(a+5)
• 4 bits for each element of an array {side info}
• dispose = free
  new = malloc
  
• header and body of a function
  function p (n: ... ) <--- header
  kjl
  fdslfjs
  ^ body of function

• structs
• tag
• struct fraction { int num; int dec }
• struct fraction r; <- declare
  
• struct elt { int val; struct elt* next; };
  typedef struct elt * intlist; {means that intlist is a pointer to struct elt}
  struct elt e;
  intlist l;
  e.val=3;
  l=&e;
  
• intlist l;
  l= (intlist)malloc(sizeof(struct elt)) {12 for bst}
  l->val
  l->next
• segmentation faults 
• Strings
• a string is an array of characters
• char *s = 'hello';
• s[] -> [h][e][l][l][o]
• char *t; t[0]=h; t[1]='i'; t[2]='\0'
• segmentation error: because u have not allocated a space for t,
• it is like filling an array with values before initializing it.
• solution char t[10] or t=()malloc()
• strlen goes through the whole string whereas in java it's constant time operation, so calling strelen as a condition in a for loop is not effecient
• I/O
• char c=getchar();
  char s[1000];
  gets(s); why is it dangerous?
  char c;
  int n;
  scanf("%c%d",&c,&n);
  
• why is it dangerous?
  the function has no way to know the length of s
  if someone gives more than 1000 characters then it will over-write memory.
• Python
• dynamically typed interpreted
• everything is an object
• even integers carry a type around
• example:
  a=3
  print a
  a="hi"
  print a
• no need to compile
• double quotes vs single quotes? why??
  

• Python
• List
• you can assign something to a variable, say a={2,3,7}
  
• you can use ??length??
• you can access elements by a[i]
• once you have 2 lists, I can concatenate them using "con??"
• Python does not have a character type, it is actually a string of length 1
• implement game of life or connect 4:=> use list of lists.
• ??3x3 array, is an array of 3 references to the same link.??
• range : gives a list, and you can use it to iterate over a range of values in a for loop.
• ??for n=1 in range (1..10):???
• define a function: def
• how to iterate over  rows and cols
• for r in a:
  
  for c in r:
• have one array and another and then add them to each other]
• Activation records Ch 5.5 5.6 5.2
• = storage for locals and params of procedures
• = stack frame for C, Pascal and other imperative languages
• stack frame:
  

  params

  locals

  return address (location of a machine instruction)

  registers

  return value

  frame pointer (location on stack) so to go back once done with the job.

• binding
• name -> declaration -> memory              --------> value
  printf(a) -> int ->  if local: on stack                     }-> value
  
  if global: somewhere else    }
• python never have declaration!? False
• the first initialization of a variable is considered as declaration
• nested procedures in Pascal
• how does it look on the stack?
• see graph p 193, figure 5.25
  
• static declaration of a variable inside a function
• means that it will be used inside the function
• it will act as if it was global

• OO pardaigm (Ch 7)
  
• Principles
• modular decomposition
• data abstraction
• information hiding
• History:
• started when larger programs started to be written
• having all functions on the global level got messy
• functions were put around the data and called "methods"
• Elements:
• Class
• a blueprint that describes a set of object
  
• Object
• an instance of the class
  
• Instance Variable
• proprieties of an object that describes the object
• declared in the class
  
• Method
• functions of an object
• associated with the object
• types
• access-er methods: give information about the state of the object
• mutators: modifies the state of the object
  
• Message
• a method call: is a message
  
• calling a method === sending a message to the object
• Technical stuff
  
• most modern OO PLs have garbage collectors
• method constructors
• difference between java and c
• if you program in java and make everything static so u end up with something similar to java
• Inheritance:
• the superclass of everything is Object
• you make a class say Goo, Goo is a sub-class of Object
• if you create a new class  SmartGoo that is a sub-class of Goo and Goo is a super-class of SuperGood
• this is done through "extends Goo"
• you can have access to tall methods
• Polymorphism
• same message can be sent to different objects.
• in a dynamically typed language like Python
• if I define the same method say "test()" in different classes, then if i have a variable x and then I say x.test()
  
• how to decide which test
• depending on the type of x
• how is a+b is polymorphic?
• it means:
• addition for ints
• concatentation for strings
• operator overloading: the propriety that you can have different meanings to an operator depending on the type of objects
• Dynamic binding
• means that you dont know the type of an object until runtime
  
• OR: association of method object occurs at runtime
• SmallTalk
• Python
• Garbage Collection
• Java, Lisp, SmallTalk, Python, C#, ..
• NOT: C (free), Pascal(dispose), C++(delete)
• reaction inaccessible allocated storage
• eager approach
• uses reference counting
• each object keeps track of how many pointers are still pointed,
  
• when the last pointer disappears then you know that it no longer need to be accessed
• hence deallocate it
• send it to garbage when reference count reaches to 0
• examples: SmallTalk
• microsoft: image data type to keep track
  
• lazy approach
• let garbage accumulate
• and when there is a need it runs the garbage collector
• types
• mark and sweep
• goes through objects, mark them and then delete unmarked ones.
  
• takes time of the order of  the size of the memory
• disadvantages
• ????
  
• puppy collector
• when memory runs out
  
• advantage
  
• order of allocated memory, but you have to copy it
  
• disadvantage
• if u do it only once memory runs out, it will take time to collect the garbage
  
• research static meanings?!?
• SmallTalk
• the first purely OO language
• Basics
• everything is an object
• even ints, booleans and classes
• very uniform
• in Java, for effeciency reasons, ints, booleans are not objects
• an Object's data (its instance variables)
• are always private
• in Java (public, private, ..) does not exist
• SmallTalk systems
• are interactive environments ??
  
• Object Hierarchy
• Object
• Magnitude: an value that has ordering on it
• number
• int
• float
• character
• Collection
• ...
• everything that starts with a capital letter is a Class
  
• Basic Types
• 3: Integer
• 41: Float
• $A: Characters
• 'Hello' String
• "Hello" Comment
• Other:
• #(3, 4.1, $X) array of 3 elements
• #apple: symbol
• Variables
  
• are not typed
• a:=3
• statement separators are periods (.)
• local variables (use | and |)
  
• | i |
  i:=1
  i<=10 while True: [
  
  i print CR.
  i := i+1.
  
  ]
•   optional
  
• methods
• 7 sign -> 1
• 4 sqrt -> 2
• 2 + 3 is read like this
• take 2 and send a message + 3 to it
• 2 + 10 * 3
• 2 send it the message +10 becomes 12
  
• 12 send it the message *3 and becomes 36
• #(3 4 5) at:1 -> 3
  

• Review
• 7+4*3-4//2
• because syntax is so uniform, they get rid of precedence rules.
• thus result would be14
  
• some operators
  
• // integer division
• / float division
• \\ integer modulo
• 16 sqrt
• 3 max: 5 -> 5
• 3 max: 2 ->3
• 3 in Between: 2 and:5 -> true
• in Java: int x =3; return (x.inBetween (2,5));
• arrays
• a:= #(2,3,5,7,11)
• indexed starting at 1
• access: a at: 4 -> 7
• modify: a at 1 put: 10
• a:= #(10,3,5,7,11)
• unary binds more strongly
• example: 3+4 sqrt is read 3 + (4 sqrt)
• so to express 7 sqrt in terms of 3 and 4 you must use paranthesis (3 + 4) sqrt
• capitalization
• set (class)
• set new -> new instance of a set???
• 
  
• 3<4
• 3=4  (equal)
• ~= for (not equal)
  
• in java .equals
  
• 3==4 (identical) ---refers to the same reference
• ~~ for (not equal)
  
• in Java: ==
  
• difference between .equals and == in Java
• Blocks
• an if statement
• 3<4 if True:[ 10 ] if False:[ 3+5 ]
• [ ] more code could be put in the brackets
• i  is optional
  
• if true it would return 10
• [ ... ] block (of code)
• [i:=i+1. i printCR]
• example of a block 
• for loop
• code:
  (1 to: 10) do: [ :i | i printCR ]
  b:=[:x :y | x+y]
  b value:3 value:4 -> 7
  #(10 11 12) A0: [:x | x printCR]
  

• implementing an intlist in smalltalk
  ILE: IntList Element
  [[-]-]-> [][-]->[][-]->[][/]
  IntList  ILE     ILE   ILE
  head
  is In-
  side
  
  intListElement (ILE)
  
  val  Integer
  
  next ILE
  
  
  // rest of code is on the website
  
  
• key differences, you can not call intList.next, like you can in Java and Python. this is because instance variables are private.
• way around this, is to create accessor methods.

IntList / IntListElt

CS 313 Smalltalk linked list example

Also serves as an example for how you could organize your code for
the printed submission of homework 5 part 2.


Class IntListElt
================
Object subclass:#IntListElt
 instanceVariableNames:'val next'
 classVariableNames:''
 poolDictionaries:''
 category:'DanielsClasses'


Class methods
-------------

none (the accessor methods val: and next: will be used to initialize
 the instance variables)


Instance methods
----------------

val: anInt
 "set the value of the instance variable 'val'"

 val := anInt.


val
 "return the value of the instance variable 'val'"

 ^ val.


next: anIntListElt
 "set the value of the instance variable 'next'"

 next := anIntListElt.


next
 "return the value of the instance variable 'next'"

 ^ next.


lengthR
 "returns length of list (recursive version)"
 "called by IntList's instance method lengthR"

 (next == nil) ifTrue: [ ^ 1 ].
 ^ 1 + (next lengthR).


maxR
 "returns maximum value in list (recursive version)"
 "called by IntList's instance method maxR"

 (next == nil) ifTrue: [ ^ val ].
 ^ val max: (next maxR).



Class IntList
=============
Object subclass:#IntList
 instanceVariableNames:'head'
 classVariableNames:''
 poolDictionaries:''
 category:'DanielsClasses'


Class methods
-------------

none ("new" will initialize "head" to nil, which is just what we want)


Instance methods
----------------

isEmpty
 "returns whether list is empty"

 ^ (head == nil).


add: anInt
 "inserts anInt at the head of the list"

 | e |
 e := IntListElt new.
 e val: anInt.
 e next: head.
 head := e.


remove
 "removes first element in the list and returns its value"
 "assert: list not empty"

 | v |
 self isEmpty ifTrue: [self error: 'cannot remove from empty list'].
 v := head val.
 head := head next.
 ^ v.


length
 "returns length of list"

 | n e |
 n := 0.
 e := head.
 [ e ~~ nil ] whileTrue: [
 n := n + 1.
 e := e next
 ].
 ^n.


lengthR
 "returns length of list (recursive version)"
 "most of the work is done by IntListElt's instance method lengthR"

 self isEmpty ifTrue: [ ^ 0 ].
 ^ head lengthR.


max
 "returns maximum value in list"
 "assert: list not empty"

 | m e |
 self isEmpty ifTrue: [self error: 'cannot compute max of empty list'].
 m := head val.
 e := head next.
 [ e ~~ nil ] whileTrue: [
 (e val > m) ifTrue: [
 m := e val 
 ].
 e := e next
 ].
 ^m.


maxR
 "returns maximum value in list (recursive version)"
 "all of the work is done by IntListElt's instance method maxR"
 "assert: list not empty"

 self isEmpty ifTrue: [self error: 'cannot compute max of empty list'].
 ^ head maxR.



Testing and sample output
=========================

|t| t:= IntList new.
'Testing IntList methods on list (0, 4, 2, 3)' printCR.
t add: 3. t add: 2. t add: 4. t add: 0.
'max: ' print. t max printCR.
'isEmpty: ' print. t isEmpty printCR.
'length: ' print. t length printCR.
'remove: ' print. t remove printCR.
'lengthR: ' print. t lengthR printCR.
'remove: ' print. t remove printCR.
'max: ' print. t max printCR.
'maxR: ' print. t maxR printCR.
'remove: ' print. t remove printCR.
'isEmpty: ' print. t isEmpty printCR.
'remove: ' print. t remove printCR.
'isEmpty: ' print. t isEmpty printCR.


output (produced using "doIt" on the code above):
-------------------------------------------------

Testing IntList methods on list (0, 4, 2, 3)
max: 4
isEmpty: false
length: 4
remove: 0
lengthR: 3
remove: 4
max: 3
maxR: 3
remove: 2
isEmpty: false
remove: 3
/*******************************************/
isEmpty: true

• SmallTalk Wrap-up
• check code on the web, for implementing a list.
• how to evaluate a block
• if it has an argument
• [:n | n printCR] value: 7    output: 7
• if it has more than one argument
• [:n :m | n printCR m printCR] value: 7 value:8
• if it does not have an argument
• ['hi' printCR] value   output: hi
  
  
  // end of material for midterm 1 //
•  (n~=0) & (a/n > 5)
  
  will evaluate both, send (a/n>5) to (n~=0), so will get exception error if we have n=0
• how to get around this?
• using blocks
• using and: instead of &
• (n~=0) and: [(a/n>5)]
• == and = compares references
  
• OO programming in Python
• how to define classes in Python.
  

  class Point:
  

  pass    # empty block to avoid error
  
  

  p= Point ()
  p.x = 7
  p.y = 5
  print p.x, p.y
  
  
  q= Point ()
  q.x = 3
  q.y = 3
  print q.x, q.y
  
  but also:
  
  q= Point ()
  q.s = 3
  q.t = 3
  print p.s, p.t
  
  would give the same output, it is only because you do not have to declare variables in Python, it is like saying
  x =3
  print x
  and then saying
  y =3
  print y

• Methods (important to understand the mechanism, of passing self)
  

  def myadd (x, y):
  

  return x+y
  

  
  class Point:
  

  def setxy (self, myx, myy) :
  

  self.x = myx
  self.y = myy
  

  p = Point()
  p.setxy(3, 4)  # what happens: setxy (p, 3, 4) -> gives error [provided 4 args instead of 3] self is a mandotary argument taken from before the period
  self is not necassary, u can subtitute with any name in the class function
  p.print p.x, p.y, myadd(p.x, p.y)
  
  Output:
  3   4   7

• Constructor methods
  

  class Point:
  

  def __init__(self, x, y):
  

  self.x = x
  self.y = y
  

  p = Point (6, 7)
  print p.x, p.y, myadd(p.x, p.y)
  
  Output:
  6    7    13

• get methods
  

  def getx (self):
  

  return self.x

• exam review

• hws similar

• write grammar

• look at some code and tell me what it outputs/ prints/ computes

• write some code

• parameter passing

• corresponding readings and compare them to notes

• no proofs

• ambiguous grammars
• More Python
• default values for initialization
  

  class Point3(Point2)
  

  def __init__ (self, x=0, y=0):
  

  self.x = x
  self.y = y
  

  q = Point3 ( 12, 10 )  x= 12,   y= 10
  q = Point3 ( 10 )  x= 10, y=0
  q = Point3 ( )  x=0, y=0
  
  what if you want to leave x to default and y to something
  q = Point3 ( y= 10)
  

• rectangle class
  

  class rect:
  

  def __init__ (self, x=0, y=0, w=0, h=0):
  

  self.x = x
  self.y = y
  self.w = w
  self.h = h
  

  def __str__(self):
  

  return "rect "%3d x %3d at %3d, %3d" % (self.w, self.h, self.x, self.y)
  # if you run out of space and you have to use multiple lines then use paranthese to the whole expression or use \ at the end of the first line to let the complier know that the next line is part of this line.
  return ("rect "%3d x %3d at %3d, %3d" % (self.w, self.h, self.x, self.y))
  

  
  # sube class of rectangle
  class Square (Rect{,DrawableObject}): #you can multiple inherent,but it's tricky
  

  def __init__(self, x=0, y=0, size=0):
  

  self.x = x
  self.y = y
  self.w = size
  self.h = size

  
  # testing code for Rect
  a = Rect ()
  b = Rect (20, 30)
  c = Rect (100, 100, 30, 10)
  
  # testing code for Square
  d = Square(30, 40, 100)
  print "d = %s, area
  
  #print "a = %s\nb = %s\nc = %s" % ("hi", 34, 3.4)
  print "a = %s\nb = %s\nc = %s" % (a, b, c)
  # if str is not defined it will print the address of the rect in memory
  
  # you can reserve space, just like in C %3s or %2d
  

• Tupals
  

  >>(x, y) =(3, 4)
  >>a =(x, y)
  >>print a
  (3, 4)

• importing
  

  import rect # filename w/o .py
  
  Class Square (rect.Rect):
  
  
  
  print __name__
  
  in rect: it will print  __main__
  if in the subclass (square) it will print:  rect
  
  you can exploit this to run code only if you are in the main class or only if you are in the subclass
  
  if __name__ ="__main__":
  

• print
  

• Pascal not in C

• pass by reference,

• nested functions
• C not in pascal
• arbitrary memory access
• macro processors
• smalltalk not in Java
• dynamically typed
• everything is an object
• variables are private
• blocks
• in python not in c, pascal or java
• indentation
• a < x < c
• Functional Programming CH 8-11 {I slept in class, read from the book}
  
• Scheme CH 10
  
• Like-Lisp
• Not Typed
  
• LM
  
• Typed

• Scheme CH 10.1-3 15.6
• ( > 3 2)
• write in prefix
• #t : true
• #f: false
• define a max function
  

  (define (max a b)
  

  (if (> a b)
  

  a
  b))

• more code
  

  (define x 3)
  x -> 3
  (define f +)
  (f 2 3) -> 5
  ((if #f + *) 3 4)
  ->12

• is not case sensitive
• it needs spaces between the arguments
• comparisons
  =, >, <, >=, <=, not, and, or
• not equal (!= or <>) is not an a operator
  

  (define (ne a b)
  

  (not (< a b))
  

  (define (sign a)
  

  (if (> a 0)
  1
  (if (< a 0)
  

  -1
  0)))

• cond, a generalized version of if
  

  (define (sign a)
  

  (cond (( > a 0)    1)
  

  ((< a 0)   -1)
  (else 0))

• Lists: basic data structure in scheme
• things are either lists or atoms
•  atom
• booleans    #t     #F
• numbers     3     2.5
• symbols     a   b   c
• how is list represented in memory
  like a linked list
  ( a b c)
  [a |  -]--> [b |  -]--> [c | / ]
     *
    / \
  a   *
      / \
     b  *
        / \
       c  () <=== nil/empty list
  
• ( _ . _)
  (a . (b . ( c . ())) === (a b c)
• ( ( a b )  ( c ) d )
        *
     /        \
    *          *
   / \        /    \
  a  *      *      *
     / \     / \    / \
    b  ( ) c  ()  d ()
• car -> first element of par (head)
  
• cdr -> second element (tail, rest)
  example: L = ( a b )
  Tree representation
      *
     / \
    a  *
        / \
       b  ()
  ( car L ) -> a
  ( cdr L) -> (b)
  ( cdr (cdr L)) -> ()
  ( car (cdr L)) -> b

• Control in Prolog ?? (Ch 11.5)
  
• starts with query as current goal G call visit(G)
• visit(G)
• if G=nothing (fi math sign) -> succeed
  else G=G1, .. , Gx
  how?
  for each matching rule for G1
  
  A:-B1, .. Bj
  1- let (sigma) be most general         :not specifiing  # that are not needed
  

  unifier of G1, A -> G1(sigma)=A(sigma)
  

  2- visit( B1(sigma), ... Bj(sigma), G2(sigma), ..., Gx(sigma))
• unify z(X, a) and z(b, X):-f(X)
  X in z does not have be equal to b only because X is unified to b.  ????don't understand
• Cut (Ch 11.6)
• A cut "!" is used to prune part of the search tree.
  -> prevents backtracking
• example:
  

  G:- A, B, !, C, D.
  1- tries to find solution for A
  2- tries to find solution for B if it fails goes back to A
  3- after the cut, it does not go back to find solutions
  
  once you get sol. past "!" backtrack for other solns before "!"
  -> freezes first sols, for A, B

• back of quiz 8 shows how it works
• types of cuts
• green cut: prevents unnecessary search (w/o changing solutions)
  >> added efficiency!
  >> same solutions!
  

  find(X, node(X, _, _)).
  find(X, node(N, L, _)):- X<N, find(X, L).
  find(X, node(N, _, R)):- X>N, find(X, R).
  
  these rules are mutually exclusive, so we add cuts to prevent it to look in the right tree if it is less than N, whether it finds it or not.
  
  find(X, node(X, _, _)):-!.
  find(X, node(N, L, _)):- X<N, !, find(X, L).
  find(X, node(N, _, R)):- X>N, !, find(X, R).

• factorial(0, 1).
  factorial(N, R):-
  

  N1 is N-1,
  factorial(N1, R1),
  R is N*R1
  

  ?- factorial(4, R).
  R=24
  if you hit ; it will run forever because it tries the second rule factorial(0,R)
  
  factorial(0, 1):-!.
  factorial(N, R):-
  

  N>0, !,
  

  N1 is N-1,
  factorial(N1, R1),
  R is N*R1

  
  

• =:= test equality after evaluation

• trysolve(A, B, C, D) :-
   solve(A, B, C, D),
   !. /* the CUT prevents backtracking for more solns */
  
  trysolve(_, _, _, _) :-
   write_ln('---------- no solution').
  
  
  
  ! prevents it from calling solve again if solve is true
  if solve if false it never reaches the ! anyways
  
  if ! is before solve, then whether solve is true or not it will not call the second trysolve so it will give nothing.
  
  

• Red cuts
  >> changes solutions
  >> deviate from pure answers
  >> example on the quiz
  
• not
  

  a(1).
  a(2).
  ?- not(a(1)).
  false.
  ?-not(a(3)).
  true.
  true: implies "given rules statement is provable"
  not: implies "given rules it failed to prove statement"

• implement not using a cut
  

  not(X):- X, !, fail.
  not(_).
  
  >> if x, fail and never backtrack

• general solver prolog for puzzles:
  without cycles
  solve(currentState, Moves):-
  
      finalState(current),
      printSoln(Moves).
  
  solve(Current, Moves):-
      makeMove(Current, New, M),
      solve(New, [M|Moves]).
  
  
  with cycles
  solve(Current, Moves, States).
  solve(Current, Moves, States):-
      makeMove..
      not(member(New, States)
  solve(New, [M|moves], [N|states]).
• specific example:
• PROLOG
  

  /* goat.pl
   *
   * Wolf, Goat, Cabbage Puzzle
   *
   * demonstrates searching a cyclic state space using Prolog
   *
   * demo for CS 313 Daniel Scharstein
   */
  
  
  /* The problem: A man travels with a wolf, a goat, and a cabbage. He
  needs to cross a river in a boat that can at most hold himself and one
  of his three objects. He cannot leave the wolf alone with the goat or
  the goat with the cabbage, because the former would eat the latter in
  each case. How can the river be crossed?
  */
  
  /* represent valid passenger configurations as lists: */
  canBeInBoat([man]).
  canBeInBoat([man, wolf]).
  canBeInBoat([man, goat]).
  canBeInBoat([man, cabbage]).
  
  /* represent groups of objects on either shore as lists: */
  illegal(Group) :-
  	not(member(man, Group)),
  	member(wolf, Group),
  	member(goat, Group).
  illegal(Group) :-
   not(member(man, Group)),
  	member(goat, Group),
  	member(cabbage, Group).
  
  legal(Group) :- not(illegal(Group)).
  
  /* print all solutions */
  printAll :- 
  	solve(Result),
  	nl, /* newline */
  	printList(Result),
  	fail. /* backtrack to find other solutions */
  
  /* print each element of a list on its own line */
  printList([]).
  printList([H|T]) :-
  	write_ln(H),
  	printList(T).
  
  /* we will represent states using the goups on the left shore */
   
  /* this calls the main search routine solve/5 */
  solve(Result) :-
  	/* initial values (makes it easier to read): */
  	Left = [man, wolf, goat, cabbage], /* group on left bank of river */
  	Right = [], /* group on right bank of river */
  	Moves = [], /* moves made so far */
  	States = [Left], /* states been in so far */
  	solve(Left, Right, Moves, States, Result).
  
  /* if left bank empty, done: return moves made in reverse order */
  solve([], _, Moves, _, Result) :-
  	reverse(Moves, Result).
   
  
  /* otherwise, try a move, make sure it doesn't result in a state we've been
   in already, and keep searching recursively */
  solve(L, R, Moves, States, Result) :-
  	makeMove(L, R, NewL, NewR, M),
  	not(member(NewL, States)),
  	solve(NewL, NewR, [M|Moves], [NewL|States], Result).
  
  /* comes up with a legal move */
  makeMove(L, R, NewL, NewR, goRight(Passengers)) :-
  	canBeInBoat(Passengers),
  	remove(Passengers, L, NewL),
  	legal(NewL),
  	add(Passengers, R, NewR).
  
  makeMove(L, R, NewL, NewR, goLeft(Passengers)) :-
  	canBeInBoat(Passengers),
  	remove(Passengers, R, NewR),
  	legal(NewR),
  	add(Passengers, L, NewL).
  
  remove(X, L, NewL) :- 
  	mergeLists(X, NewL, L).
  add(X, L, NewL) :-
  	mergeLists(X, L, NewL),
  	/* make sure that NewL is in unique order */
  	mergeLists(NewL, _, [man, wolf, goat, cabbage]).
  
  mergeLists([], [], []).
  mergeLists([H|A], B, [H|C]) :-
  	mergeLists(A, B, C).
  mergeLists(A, [H|B], [H|C]) :-
  	mergeLists(A, B, C).

• ;;; goat.scm
  ;;;
  ;;; the wolf, goat, cabbage puzzle in scheme
  ;;;
  ;;; demonstrates searching a cyclic state space using Scheme
  ;;;
  ;;; demo for CS 313 Daniel Scharstein
  
  
  ;; the following functions can be used for any puzzle with a cyclic
  ;; state graph
  
  ; the top-level function to start the search
  (define (solveIt)
   (solve (initstate) (list (initstate)) '())
   #t) ; avoid "unspecified return value" message
  
  ; recursively explore all states
  (define (solve currentstate oldstates oldmoves)
   (if (finalstate? currentstate)
   (begin
  	(write 'solution:) (newline)
  	(printlist oldmoves)
  	(newline))
   (makemoves (possiblemoves currentstate)
  	currentstate oldstates oldmoves)))
  
  ; print the list of moves in reverse order
  (define (printlist moves)
   (if (not (null? moves))
   (begin
  	(printlist (cdr moves))
  	(write (car moves))
  	(newline))))
  
  ; tries all moves in movelist; if they are legal and result in a new
  ; state, call solve recursively
  (define (makemoves movelist currentstate oldstates oldmoves)
   (if (not (null? movelist))
   (let* ((move (car movelist))
  	(newstate (makemove move currentstate)))
  	(if (and (legalstate? newstate)
  	(not (member newstate oldstates)))
  	(begin
  ;;	(write 'newstate) ;; useful for debugging
  ;;	(write newstate)
  ;;	(newline)
  	(solve newstate (cons newstate oldstates) (cons move oldmoves))))
  	(makemoves (cdr movelist) currentstate oldstates oldmoves))))
  
  
  ;;; functions below are specific to the current puzzle
  
  ; Represent states as lists with two elements, each a list of the objects
  ; on the left/right river bank. Make sure that representation is unique
  ; by maintaining the relative ordering man < wolf < goat < cabbage.
  
  (define (left state)
   (car state))
  (define (right state)
   (cadr state))
  
  ; the initial state
  (define (initstate)
   '((man wolf goat cabbage) ()))
  
  ; are we done?
  (define (finalstate? state)
   (null? (left state)))
  
  ; return list of possible moves from current state
  ; for example:
  ; > (possiblemoves '((man wolf goat) (cabbage)))
  ; '((goright man) (goright man wolf) (goright man goat))
  (define (possiblemoves state)
   (if (eqv? 'man (car (left state)))
   (mapcons 'goright (makepassengerlist (left state)))
   (mapcons 'goleft (makepassengerlist (right state)))))
  
  ; conses a onto each element in l
  (define (mapcons a l)
   (map (lambda (x)
  	(cons a x))
   l))
  
  ; extracts all possible lists of passengers from a group containing 'man'
  ; for example:
  ; > (makepassengerlist '(man wolf goat))
  ; '((man) (man wolf) (man goat))
  (define (makepassengerlist group)
   (cons '(man) (mapcons 'man (map list (cdr group)))))
  
  ; applies move 'move' to current state and returns new state
  (define (makemove move state)
   (let* ((goright? (eqv? (car move) 'goright))
  	(passengers (cdr move))
  	(from (if goright? (left state) (right state)))
  	(to (if goright? (right state) (left state)))
  	(newfrom (removelist passengers from))
  	(newto (mergelists passengers to)))
   (if goright?
  	(list newfrom newto)
  	(list newto newfrom))))
  
  ; removes all elements in list a from list b
  (define (removelist a b)
   (if (null? a) b
   (remove (car a) (removelist (cdr a) b))))
  
  ; removes first occurence of x from list b
  (define (remove x b)
   (if (null? b) '()
   (if (eqv? x (car b)) (cdr b)
  	(cons (car b) (remove x (cdr b))))))
  
  ; merges ordered lists a and b into ordered result, using predicate 'less?'
  ; to determine order
  (define (mergelists a b)
   (cond ((null? a) b)
  	((null? b) a)
  	((less? (car a) (car b))
  	(cons (car a) (mergelists (cdr a) b)))
  	(else
  	(cons (car b) (mergelists a (cdr b))))))
  
  ; decides whether a is smaller than b
  (define (less? a b)
   (let* ((ranks '((man 1) (wolf 2) (goat 3) (cabbage 4)))
  	(na (cadr (assoc a ranks)))
  	(nb (cadr (assoc b ranks))))
   (< na nb)))
  
  ; is state legal?
  (define (legalstate? state)
   (and (legalgroup? (left state))
   (legalgroup? (right state))))
  
  ; is group legal?
  (define (legalgroup? group)
   (or (null? group)
   (eqv? 'man (car group))
   (and (not (and (member 'wolf group)
  	(member 'goat group)))
  	(not (and (member 'goat group)
  	(member 'cabbage group))))))
  
  ; Sample run:
  ;
  ; > (solveIt)
  ; solution:
  ; (goright man goat)
  ; (goleft man)
  ; (goright man wolf)
  ; (goleft man goat)
  ; (goright man cabbage)
  ; (goleft man)
  ; (goright man goat)
  ;
  ; solution:
  ; (goright man goat)
  ; (goleft man)
  ; (goright man cabbage)
  ; (goleft man goat)
  ; (goright man wolf)
  ; (goleft man)
  ; (goright man goat)